Patent Publication Number: US-7219157-B2

Title: Application programming interface for network applications

Description:
BACKGROUND OF THE INVENTION 
     1. Technical Field of the Invention 
     This invention generally relates to operating systems and, more particularly, to an apparatus and method for providing an application programming interface (API) for network applications. 
     2. Discussion of the Background Art 
     Broadly, Application Programming Interfaces (APIs) are those language and messaging formats that define how applications interact with an operating system, and with functions in other applications, communication systems, and hardware drivers. Network applications are those applications that, unlike host applications, process packets whose source and destination are network nodes different from that where the application runs. Network programming is the development of network applications. 
     Existing networks typically lack platforms that are well suited for network programming. Network hosts usually support only host applications. On the other hand, network bridges, switches, and routers usually execute fixed or configurable network applications and do not provide an API that would enable users to develop new applications. 
     Without network programming platforms, it can be difficult to prototype or realistically test many desirable new protocols or services. Several protocol enhancements can be demonstrated by analysis or simulation before, e.g., manufacturers implement them and include them among router configuration options. However, certain new services, such as billing (charging users for their network usage), may not be similarly amenable to analysis or simulation. Because the adequacy of a billing strategy depends on how users react to it, and such reaction is difficult to predict or model before observation, simulations may not be convincing. To test such new services, actual deployment and observation in the field are necessary. 
     Within the context of a network programming API implemented on a personal computer (PC) platform, several features are deemed to be desirable; namely (1) support for configuring the platform as a bridge, router or host; (2) general purpose functionality; (3) support for user-level applications; (4) the ability to pass packets between applications and the operating system without copying; and (5) reducing the number of system calls and interrupts generated per packet. 
     Unfortunately, existing PC operating systems do not provide APIs that meet all the above requirements. These and other disadvantages associated with the prior art are described in more detail in a paper authored by Blott et al. entitled “NetTap: An Efficient and Reliable PC-Based Platform for Network Programming” published on Mar. 26, 2000 in the Institute of Electrical and Electronic Engineers (IEEE) Proceedings of OPENARCH &#39;2000. 
     SUMMARY OF THE INVENTION 
     An application programming interface (API) is described that allows creating or destroying one or more pairs of data structures for asynchronously passing between the operating system and a network application pointers to packet buffers mapped to both parties. A network application may use such a pair to: (1) input packets received from a specified network interface, and output packets to be processed by the operating system&#39;s network layer as received packets; (2) input packets output by the operating system&#39;s network layer to a specified network interface, and output packets to be actually sent by that interface; (3) input packets received and output packets to be sent by a specified network interface; or (4) input allocated and output deallocated packet buffers. The operating system automatically reclaims buffers allocated to a network application when the latter terminates. The API also allows a network application to sleep until the operating system inserts or removes a packet buffer pointer into or from one said data structure. The API may be used in systems configured as host, bridge, switch, or router. 
     An API according to an embodiment of the invention comprises first and second data structures associated with a network interface in communication with a network, the first and second data structures being mapped to an operating system and a network application, wherein: packets to be passed from the operating system to the network application are stored in a buffer and referenced via respective pointers within the first data structure, the first data structure pointers being inserted into the first data structure by the operating system prior to network layer processing, the first data structure pointers being removed by the network application, insertion and removal of the first data structure pointers being asynchronous with respect to each other; and packets to be processed as received packets by the network layer of the operating system are stored in a buffer and referenced via respective pointers within the second data structure, the second data structure pointers being inserted into the second data structure by the network application, the second data structure pointers being removed by said operating system, insertion and removal of the second data structure Dointers being asynchronous with respect to each other. 
     An API according to another embodiment of the invention for network applications, which applications can process packets whose source and destination nodes are nodes different from that where the application runs, the API comprising a primitive for creating a first and a second data structures associated with a specified network interface, if the data structures do not exist, and mapping the data structures both to the operating system and a specified network application, wherein the specified network interface receives and sends packets from and to a network, each packet is stored in a buffer mapped both to the operating system and the specified network application, the operating system inserts into and the specified network application may remove from the first data structure a pointer to each buffer containing a packet that the operating system&#39;s network layer outputs to the specified network interface, before the network interface sends the packets, the insertions and removals being asynchronous with respect to each other, and the specified network application may insert into and the operating system removes from the second data structure a pointer to each buffer containing a packet that the specified network interface sends to the network, the insertions and removals being asynchronous with respect to each other. 
     An API according to an embodiment of the invention for network applications, which applications can process packets whose source and destination nodes are nodes different from that where the application runs, the API comprising a primitive for creating a first and a second data structures associated with a specified network interface, if the data structures do not exist, and mapping the data structures both to the operating system and a specified network application, wherein the specified network interface receives and sends packets from and to a network and does not require a coprocessor, the specified network application requires supervisor privileges, every packet is stored in a buffer mapped both to the operating system and every network application, the operating system&#39;s network and higher protocol layers do not process any packets that the specified network interface receives or sends, the operating system inserts into and the specified network application may remove from the first data structure a pointer to each buffer containing a packet that the specified network interface receives from the network, the insertions and removals being asynchronous with respect to each other, and the specified network application may insert into and the operating system removes from the second data structure a pointer to each buffer containing a packet that the specified network interface sends to the network, the insertions and removals being asynchronous with respect to each other. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which: 
         FIG. 1  depicts the organization of an application programming interface (API) according to the invention; 
         FIG. 2  depicts a program segment written in the C programming language including an API according to the invention; 
         FIG. 3  illustrates the data structures used for allocating and deallocating packets according to the invention; 
         FIG. 4  depicts an mbuf data structure useful in understanding the invention of  FIG. 1 ; 
         FIG. 5  depicts a block diagram of an illustrative embodiment of a computer system suitable for implementing the invention of  FIG. 1 ; 
         FIG. 6  depicts a block diagram of an illustrative alternate embodiment of a computer system suitable for implementing the invention of  FIG. 1 ; and 
         FIG. 7  depicts an example of an application utilizing an API according to the invention. 
       To facilitate understanding, identical reference numerals have been used, wherever possible, to designate identical elements that are common to the figures. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     An illustrative embodiment (herein referred to as “NetTap”) of a network programming API suitable for efficiently prototyping, field-testing, and deploying new network protocols and services is disclosed below. NetTap was implemented by the inventors on low-cost PC (Personal Computer) hardware and the freely available FreeBSD operating system. See, e.g., G. Lehey, The Complete FreeBSD, Walnut Creek CD ROM Books (2d ed. 1997), all relevant portions of which are herein incorporated by reference. 
     Like FreeBSD&#39;s network programming APIs, the NetTap API can be used by a system administrator. Unlike FreeBSD&#39;s APIs, however, the NetTap API supports the desirable features enumerated above for network programming APIs for PCs. 
     Various discussions associated with the prior art and information related to the present invention may be found in a paper by Blott et al. entitled “NetTap: An Efficient and Reliable PC-Based Platform for Network Programming” published on Mar. 26, 2000 in the Institute of Electrical and Electronic Engineers (IEEE) Proceedings of OPENARCH &#39;2000, which paper is incorporated herein by reference in its entirety. 
       FIG. 1  depicts the organization of an application programming interface (API) according to the invention. Specifically,  FIG. 1  illustrates data structure used for sending and receiving packets according to the invention. More specifically,  FIG. 1  comprises a kernel level portion comprising a Transmission Control Protocol/Internet Protocol (TCP/IP) implementation  112  and a network interface  114  coupled to a network  116 . An operating system  102  e.g., FreeBSD, operates at the kernel level and includes the NetTap API. A user level portion comprises a network application  108  and a host application  110 . The host application  110  is coupled to the TCP/IP implementation  112  of the kernel level portion. 
     A circular queue comprises a first data structure and a second data structure. Specifically, first and second data structures comprise a detour and revert queue respectively which are mapped to both the operating system  102  and network application  108 . More specifically, an input tap  118  comprises a detour queue  104 A and a revert queue  106 A. Detour queue  104 A is coupled to the network interface  114  and network application  108 . Revert queue  106 A is coupled to network application  108  and TCP/IP implementation  112 . 
     An output tap  120  comprises a detour queue  104 B and a revert queue  106 B. Detour queue  104 B is coupled to TCP/IP implementation  112  and network application  108 . Revert queue  106 B is coupled to network application  108  and to the network interface  114 . 
     It will be appreciated by those in the art that the invention can be practiced with a plurality of revert and detour queues. In addition the invention can also be practiced with a plurality of network interfaces and network applications. 
     The above mentioned queues can contain packet pointers  410  (See  FIG. 4 ) which point to a location in memory where packets are stored. Specifically, the packet pointers  410  point to mbufs  402  (see  FIG. 4 ) which comprise input buffers for storing received packets and output buffers for storing packets processed by the network application  108 . Each mbuf  402 , in the header  404 , has a process identifier “pid” field  406 . All mbufs  402  are assigned from a single unpageable region. Mbufs  402  will be described in more detail below with reference to  FIG. 4 . 
     It should be noted that network applications are those applications that, unlike host applications, process packets whose source and destination nodes are different from those where the application runs. 
     As incoming packets arrive, the packets are stored in memory. Data structures are created wherein pointers are placed in the data structures by the operating system  102 . Specifically, pointers that point to the location of the incoming packets in memory are placed in detour queue  104 A and taken out of detour queue  104 A by the network application  108 . After the network application  108  has processed a packet, the network application  108  can insert a pointer  410  to the packet buffer  402  in one of three queues. First, the network application  108  can insert the pointer  410  in revert queue  106 A. In this case, the operating system&#39;s TCP/IP implementation processes the packet as received from the network  116 . Second, the network application  108  can insert the pointer  410  in revert queue  106 B. In this case, the network interface  114  sends the packet to the network  116 . Third, the network application  108  can insert the pointer  410  in the mbuf_dealloc queue  304 . In this case, the operating system deallocates the packet buffer  402 . 
     The main characteristics of the NetTap API are: (i) all packet buffers are mapped both to the system and to network applications; (ii) instead of passing copies of packets to one another, system and network applications exchange pointers to packets; and (iii) system and network applications communicate asynchronously via a number of circular queues, thus avoiding system call overheads in normal cases. The system accesses queues asynchronously when a network interface interrupt occurs or returns, a NetTap system call returns, the system preempts or puts to sleep a NetTap application, or the system is idle. Because each queue contains only pointers that are enqueued by the system and dequeued by a network application, or vice-versa, there is no risk of conflict between system and application accesses. Therefore, system accesses do not have to be synchronized with respect to application accesses. 
       FIG. 2  depicts a program segment written in the C programming language including an API according to the invention. Specifically, program  200  is written in the C programming language and comprises a circular queue representation  202 , inline functions for enqueueing  204  and dequeueing  206  a pointer to or from a circular queue, system calls including mbuf map  208  mbuf_unmap  210 , mbuff_pull  212 , mbuf_push  214 , interface_tap  216  and interface_untap  218 . For a better understanding of the invention, program  200  should be read in view of  FIG. 3  and  FIG. 1  together. 
     In systems derived from BSD Unix (see M. McKusick, et al., the Design and Implementation of the 4.4 BSD Operating System, Addison-Wesley (1996), all relevant portions of which are herein incorporated by reference), including FreeBSD, network interfaces and protocols hold packets in buffers known as “mbufs”, as illustrated in  FIG. 4 . 
     As previously discussed above with reference to  FIG. 1 , all mbufs  402  are allocated from a single unpageable region. NetTap&#39;s “mbuf_map” primitive  208  maps this region to the application&#39;s address space. Specifically, the primitive “mbuf_map”  208  creates two circular queues, “mbuf alloc”  302  and “mbuf_dealloc”  304 , and maps them to the application&#39;s address space, as shown in  FIG. 3 . The “mbuf_unmap” primitive  210  unmaps the mbuf region and destroys the application&#39;s mbuf_alloc  302  and mbuf_dealloc  304  queues. 
     NetTap network applications  108  allocate mbufs by dequeueing the mbufs&#39; pointers  410  from mbuf_alloc  302  using the dequeue routine  206 , and deallocate mbufs by enqueueing the mbufs&#39; pointers  410  in mbuf_dealloc  304  using the enqueue routine  204 . The mbuf_map primitive  208  includes an argument, “mbuf_prealloc” (not shown), that specifies the minimum number of mbuf pointers  410  that should be enqueued in the application&#39;s mbuf_alloc queue  302 . The operating system  102  asynchronously replenishes queue  302 , making mbufs  402  available to the network application  108 . When necessary (e.g., mbuf_alloc  302  is empty), however, applications  108  may use the mbuf_pull primitive  212  to force the system  102  to enqueue a specified (strictly positive) number of mbuf pointers  410  synchronously into mbuf_alloc  302 , subject to a timeout interval specified in microseconds (infinite if set to 0). The system  102  asynchronously dequeues pointers  410  from the applications&#39; 108  mbuf_dealloc queues  304  and deallocates the respective mbufs. If necessary (e.g., mbuf_dealloc  304  is full), however, an application  108  may use the “mbuf_push” primitive  214 , with the tap descriptor argument equal to −1, to force the system  102  to dequeue any pointers  410  from mbuf_dealloc  304  synchronously and deallocate the respective buffers. The primitives mbuf_map  208 , mbuf_unmap  210 , mbuf_push  212 , and mbuf_pull  214  return 0 if successful, or an error code otherwise. 
     It will be appreciated by those skilled in the art that packets may have fixed or variable length. Although mbufs have a fixed length, a packet of any length can be stored in mbufs. Additionally, a plurality of mbufs can be concatenated to hold a packet that is larger than a single mbuf. 
     The “interface_tap” primitive  216  allows a NetTap application to open a tap on a specified network interface, as illustrated in  FIG. 1 . This function returns pointers to two queues: “detour”  104 A or  104 B, for passing packet pointers  410  from operating system  102  to the network application  108 , and “revert”  106 A or  106 B, for passing packet pointers  410  from the network application  108  back to the operating system  102 . After dequeueing a packet pointer  410  from detour  104 A or  104 B and processing the respective packet, the network application  108  may enqueue the packet pointer  410  in revert  106 A or  106 B. The detour and revert queues returned by interface_tap are called an input tap  118  or output tap  120  on the network interface  114 . 
     If the interface_tap primitive&#39;s  216  “mode” argument is TAP_INPUT, the system  102  enqueues in detour  104 A, instead of the regular IP input queue of the system&#39;s TCP/IP implementation  112 , pointers  410  to packets received by the network interface  114  from the network  116 . The system  102  dequeues packet pointers  410  from revert  106 A and enqueues them in the regular IP input queue of the system&#39;s TCP/IP implementation  112 , so that, e.g., a host application  110  may use the system&#39;s regular API (e.g., sockets) to receive packets destined to the host, and the system may firewall and forward packets destined to other hosts. 
     Conversely, if the interface_tap primitive&#39;s  216  mode is TAP_OUTPUT, a host application  110  may use the system&#39;s regular API to send packets, but the system enqueues in detour  104 B packet pointers  410  that TCP/IP implementation  112  would normally pass to the network interface  114  for transmission to the network  116 . The system  102  dequeues packet pointers  410  from revert  106 B and passes them to the network interface  114  for transmission to the network  116 . 
     Finally, if the interface_tap primitive&#39;s  216  mode is TAP_BYPASS, host applications  110  cannot use the system&#39;s regular API to send or receive packets via the network interface  114  and the system&#39;s firewalling and IP forwarding become inoperative on the network interface  114 . The system  102  enqueues in detour  104 A pointers  410  to packets received by the network interface  114  from the network  116 , and dequeues packet pointers  410  from revert  106 B and passes them to the network interface for transmission to the network  116 . As shown in  FIG. 1 , a given network interface  114  can have both TAP_INPUT  118  and TAP_OUTPUT  120  taps. However, a given network interface  114  cannot have a TAP_INPUT  118  or TAP_OUTPUT  120  tap and also have a TAP BYPASS tap (not shown). 
     The interface_tap primitive  216  returns a tap descriptor, i.e., a file descriptor (small non-negative integer) that corresponds to the input tap  118  or output tap  120 . The “interface_untap” primitive  218  reverts a previous interface_tap  216 , and returns 0 if successful, or an error code otherwise. Between corresponding interface_tap  216  and interface_untap  218  calls, the respective tap  118  or  120  is said to be open by the application  108 . 
     Network applications  108  input packets by dequeueing respective pointers  410  from a detour queue  104 A or  104 B, without system calls. If desired (e.g., detour  104 A is empty), however, applications  108  may use the mbuf_pull primitive  212  (with a null number of mbufs) to wait for the system  102  to enqueue a packet pointer  410  in some detour queue  104 A or  104 B mapped to the application, subject to a specified timeout interval. While the application  108  waits for a packet, the system may run other applications or poll the network interfaces, thereby possibly reducing the number of interrupts. 
     Conversely, network applications  108  output packets by enqueueing in revert queues  106 A or  106 B pointers  410  to the mbufs containing the packets. The system  102  asynchronously dequeues mbuf pointers  410  from revert queues  106 A and  106 B and processes the respective packets (in the TAP_INPUT case, passes them to the IP input queue of the system&#39;s TCP/IP implementation  112 ; in the TAP_OUTPUT and TAP_BYPASS cases, passes them to the network interface  114  for transmission to the network  116 ). If necessary (e.g., a revert queue  106 B is full), however, applications  108  may use the mbuf_push primitive  214  to wait for the system  102  to dequeue a specified number of pointers  410  from a specified revert queue  106 A or  106 B. 
       FIG. 4  depicts an mbuf data structure useful in understanding the invention of  FIG. 1 . Specifically, mbuf  402  comprises a header  404  field and a data  408  field. Included in the header field  404  is a process identifier field (pid)  406 . Pointers  410  point to a respective mbuf  402 . 
     NetTap prevents mbuf leakage as follows. Mbuf headers  404  gain a “pid” field  406  containing the identifier of the process that holds the mbuf  402  (if any). The system  102  updates an mbuf&#39;s pid field  406  whenever the system  102  enqueues the mbuf&#39;s pointer  410  in an application&#39;s mbuf_alloc queue  302  or in a tap&#39;s detour queue  104 A or  104 B. If multiple processes open the same tap, each process must update an mbuf&#39;s pid field  406  before dequeueing the mbuf&#39;s pointer  410  from detour  104 A or  104 B. When the system  102  dequeues an mbuf&#39;s pointer  410  from an mbuf_dealloc  304  or revert  106 A or  106 B queue, the system  102  clears the mbuf&#39;s pid field  406 . Processes gain a flag indicating whether the process has mapped mbufs  402 . When a process with such a flag set exits, the system  102  scans the mbuf region to find and deallocate mbufs  402  held by that process. 
     NetTap uses reference counting for maintaining an interface tap open while at least one process has that tap open. NetTap also keeps a list of taps open by each process. When a process exits, the system automatically untaps any taps that the process still has open. 
       FIG. 5  depicts a computer system  500  in accordance with the present invention. In this embodiment of the invention, the computer system  500  may be a desktop computer. However, a person skilled in the art will recognize that a laptop computer, server, hand-held device or the like may alternatively be utilized. The computer  500  comprises at least one system interconnect, e.g., bus  501  to which various components are coupled and communicate with each other. Specifically, a processor  502 , storage device  508 , memory such as random access memory (RAM)  504 , read only memory (ROM)  510 , input/output (I/O) ports  512 , and other support circuits  506  are coupled to the system bus  501 . Furthermore, one or more output devices  516 , such as display, as well as one or more input devices  514  such as a keyboard and/or pointing device are respectively coupled to the I/O ports  512 . In addition a the network interface  114  is also coupled to I/O port  512 . The network interface  114  is illustratively shown as being coupled to a first network interface card  520 ; and a second network interface is connected to a second network interface card  522 . The input and output devices  514  and  516  permit user interaction with the computer system  500  e.g., a system administrator in the preferred embodiment. 
     The processor  502  sends and receives information to and from each of the computer components coupled to the system bus  501  and performs system operations based upon the requirements of the computer system&#39;s operating system  102 , the NetTap API and network application  108  programs that are installed thereon. The processor  502  may be an INTEL PENTIUM® type microprocessor or the like. 
     The ROM  510  typically includes a Basic Input-Output system (BIOS) program, which controls basic hardware operations such as the interaction of the microprocessor  502  with the keyboard/mouse of input device  514 , the hard disk of storage device  508 , or a video display of output devices  51 G, and the like. The storage device  508  is a permanent storage medium such as a hard disk, CD-ROM. tape, or the like, which stores the operating system  102 , the NetTap API, network application  108  and application program files  518 . 
     The RAM  504  is volatile memory (e.g., SRAM, DRAM and the like). The contents of the RAM  504  may be retrieved from the storage device  508  as required. Illustratively, the RAM  504  is shown with the NetTap API, operating system  102  and network application  108  program concurrently operating. 
     It will be appreciated by those skilled in the art that although one network application is depicted, more than one network application can be depicted and be within the scope of the invention. 
     The NetTap API is sent to the RAM  504  for temporary storage and subsequent execution by the processor  502 . 
     The I/O port  512  includes various controllers (not shown) for each input device  514  such as a keyboard, mouse, joystick, and the like, as well as the output devices  516  such as the plurality of network interface  114 , adapter, infrared device (not shown) and display  516 . Typically, other support circuits  506  include controllers for the storage device  508 , floppy drive, graphics display, and the like (not shown). 
     The operating system  102  may be FreeBSD® or the like. FreeBSD is a stable operating system with mature protocol implementations, state of the art development tools, and a good track record for up to date peripheral support. The operating system is capable of interfacing with all of the hardware components of the computer  500 . 
     In order to oversee the execution of all the files opened, a kernel  524  is stored in the RAM  504 . The kernel  524  is installed at dedicated addresses in the RAM  504  and is responsible for memory management, process and task management, and disk management. The kernel  524  manages one or more files that are open during the course of operation. 
     The RAM  504  further comprises a portion of memory for storing detour queue queues  104 A,  104 B and revert queues  106 A and  106 B and mbuf  402  which comprises mbuf_alloc  302 , mbuf dealloc  304 . 
       FIG. 6  depicts a block diagram of an illustrative alternate embodiment of a computer system suitable for implementing the invention of  FIG. 1 . Although in this embodiment of the invention, the computing system  600  is a personal computer (PC). However, a person skilled in the art will recognize that another type of computer or a network bridge, switch, or router may alternatively utilized. The components of system  600  include a processor  602 , a main memory  604 , a system control and bridging circuitry  606 , a video card  608 , a keyboard interface  610 , a mouse  612 , a parallel port  614 , a serial port  616 , a floppy disk controller  618 , a hard disk controller  620 , and the network interface  114  which illustratively is coupled to network interface card  520  or network interface card  522  is coupled to a different network interface. The processor  602 , main memory  604 , and system control and bridging circuitry  606  are connected by a memory bus  626 . The system control and bridging circuitry  606  is also connected to: (1) the video controller  608  via video bus  628  (e.g., AGP); (2) other fast input/output (I/O) devices (e.g., the network interface card  114 ; illustratively depicted as being coupled to network interface cards  520  and  522 ) via a fast I/O bus  630  (e.g., PCI); and (3) slower I/O (e.g., keyboard  606 ) via a slow I/O bus  632  (e.g., ISA). The system control and bridging circuitry  606  and buses  620 ,  618 ,  630 , and  632  provide the interconnections through which the various components communicate with each other. 
     The processor  602  may be, e.g., an Intel PENTIUM® microprocessor, and executes instructions from the operating system  102  and application  108  and programs  518 . The operating system may be, e.g., FreeBSD, and incorporates the NetTap API. Network applications  108  use the NetTap API to send or receive packets. Programs and data are stored in main memory  604  while being processed. In particular, mbufs  402 , mbuf_alloc queues  302 , mbuf_dealloc queues  304 , detour queues  104 A,  104 B, and revert queues  106 A,  106 B are stored in main memory  604 . The processor  602  typically copies programs and initial data from hard disk  620  to main memory  604  during system or application initialization. The video  608 , keyboard  610 , and mouse  612  provide system interaction with a user, e.g. a system administrator. Network applications  108  must be executed by a system administrator. The network interface cards  520  and  522  transfer packets between the respective networks and mbufs in main memory  604 . The network interface cards  520  and  522  may be controlled by processor  602  and need not have a coprocessor. The number of network interface cards in a system may vary from the two shown in  FIG. 6 . 
     It will be appreciated by those skilled in the art that NetTap applications can tap any number of network interfaces and therefore can implement host, bridge or router configurations. Moreover, NetTap applications  108  can be written in any language and implement arbitrary functionality. 
       FIG. 7  depicts an example of an application utilizing an API according to the invention within the context of a bridge configuration. In the bridge configuration, two instances of the API are utilized, one for each network interface. It should be noted that if no host applications  110  use a bridged network interface, then the program  700  can be considerably simplified by tapping interfaces in TAP_BYPASS mode. 
     Router or host configurations may need additional protocol support, provided, e.g., by user-level libraries for TCP/IP protocols, IP security, or output link scheduling. Such libraries can run on top of the NetTap API. Applications may easily specialize or modify user-level libraries. For example, applications such as NAT (network address translation) or LSNAT (load sharing using IP network address translation) might modify a user-level IP implementation. 
     NetTap applications  108  may run with real-time priority to obtain guaranteed performance regardless of other load (e.g., host applications) on the system. Real-time priorities are always greater than time-sharing priorities. FreeBSD has supported real-time priorities since version 3.0. NetTap applications  108  that need multiple threads of control may use POSIX (user-level) threads on top of a single real-time process, so as to avoid context switch overheads. Single-thread event-driven implementations can be expected to outperform multiple-thread implementations, however. 
     On the other hand, if a single processor  602  is unable to keep up with network traffic tapped by an application  108 , it may be useful to run multiple instances of the application  108  on a shared-memory multiprocessor system, with one application instance per processor. Multiple applications  108  can map mbufs  402  and tap each one of the same plurality of network interface  114 . In addition, mbuf_alloc  302  and mbuf_dealloc  304  queues are private to each application  108  currently being run. However, detour  104 A and  104   b  and revert  106 A and  106 B queues are shared by all applications  108  that open the respective taps  118  or  120 . Concurrent accesses to tapping queues or other shared data structures must be synchronized. Because NetTap is PC-based, synchronization can be achieved at user level, without system call overheads. The concurrent applications  108  can define a shared integer to be a lock that guards certain shared data structures. Each application  108  uses, for example, “i486” (or later) CPU&#39;s CMPXCHG (compare and exchange) instruction to acquire or release the lock respectively before or after accessing the shared data structures. The system  102  keeps a list of locks used by each application  108 . When the application  108  exits, the system  102  automatically releases any locks still held by the application. 
     While the foregoing description represents preferred embodiments, it will be obvious to those skilled in the art that various changes and modifications may be made, without departing from the spirit and scope of the invention pointed out by the following claims: