Abstract:
In general, in one aspect, the disclosure describes a method of maintaining network protocol timers in data structures associated with different respective processors in a multi-processor system. The timers accessed by a respective one of the processors include timers of connections mapped to the processor.

Description:
REFERENCE TO RELATED APPLICATIONS  
       [0001]     This relates to U.S. patent application Ser. No. 10/815,895, entitled “ACCELERATED TCP (TRANSPORT CONTROL PROTOCOL) STACK PROCESSING”, filed on Mar. 31, 2004; this also relates to an application filed the same day as the present application entitled “NETWORK INTERFACE CONTROLLER INTERRUPT SIGNALING OF CONNECTION EVENT” naming Sujoy Sen, Anil Vasudevan, and Linden Cornett, as inventors and having attorney/docket number 42390.P19608. 
     
    
     BACKGROUND  
       [0002]     Networks enable computers and other devices to communicate. For example, networks can carry data representing video, audio, e-mail, and so forth. Typically, data sent across a network is divided into smaller messages known as packets. By analogy, a packet is much like an envelope you drop in a mailbox. A packet typically includes “payload” and a “header”. The packet&#39;s “payload” is analogous to the letter inside the envelope. The packet&#39;s “header” is much like the information written on the envelope itself. The header can include information to help network devices handle the packet appropriately.  
         [0003]     A number of network protocols cooperate to handle the complexity of network communication. For example, a transport protocol known as Transmission Control Protocol (TCP) provides “connection” services that enable remote applications to communicate. TCP provides applications with simple commands for establishing a connection and transferring data across a network. Behind the scenes, TCP transparently handles a variety of communication issues such as data retransmission, adapting to network traffic congestion, and so forth.  
         [0004]     To provide these services, TCP operates on packets known as segments. Generally, a TCP segment travels across a network within (“encapsulated” by) a larger packet such as an Internet Protocol (IP) datagram. Frequently, an IP datagram is further encapsulated by an even larger packet such as an Ethernet frame. The payload of a TCP segment carries a portion of a stream of data sent across a network by an application. A receiver can restore the original stream of data by reassembling the received segments. To permit reassembly and acknowledgment (ACK) of received data back to the sender, TCP associates a sequence number with each payload byte.  
         [0005]     Many computer systems and other devices feature host processors (e.g., general purpose Central Processing Units (CPUs)) that handle a wide variety of computing tasks. Often these tasks include handling network traffic such as TCP/IP connections. The increases in network traffic and connection speeds have placed growing demands on host processor resources. To at least partially alleviate this burden, some have developed TCP Off-load Engines (TOEs) dedicated to off-loading TCP protocol operations from the host processor(s). 
     
    
     DESCRIPTION OF THE DRAWINGS  
       [0006]      FIG. 1  is a diagram of a timer data structure  
         [0007]      FIG. 2  is a diagram of multiple processor-specific timer data structures.  
         [0008]      FIGS. 3A-3D  are diagrams illustrating transfer of a timer across processors.  
         [0009]      FIGS. 4 and 5  are flow-charts of processes implementing timer transfer across processors.  
     
    
     DETAILED DESCRIPTION  
       [0010]     Many network protocols use timers to mark points in time. For example, Transmission Control Protocol (TCP) uses a number of different timers including a retransmit timer, keep-alive timer, persistence timer, and so forth. For instance, a retransmit timer identifies a time that an acknowledgment for transmitted data should be received before a retransmit occurs.  
         [0011]      FIG. 1  depicts a sample data structure that manages timers. As shown, the data structure features a series of time buckets (labeled “time N”, “time N+1”, “time N+2”). Attached to each bucket is a list of timers associated with a given time. For example, time “N” has three associated timers: one for connections labeled “a”, “d”, and “l”. Though not shown, a particular connection may have multiple timers associated with a given time (e.g., a connection may have both an acknowledgment timer and a keep-alive timer armed for the same time). At a given time, the timers associated with a bucket are processed and appropriate actions (e.g., segment retransmission) are performed.  
         [0012]     Potentially, a given host system may have multiple processors performing TCP operations. Providing each processor with access to a monolithic data structure like that shown in  FIG. 1  to arm, disarm, and/or process timers can substantially degrade overall system performance. For example, potential access contention by the different processors may necessitate locking schemes. Additionally, access by different processors may prevent efficient caching of the data structure by the processors.  
         [0013]      FIG. 2  depicts the same set of timers depicted in  FIG. 1 . However, in  FIG. 2  these timers are distributed into multiple processor-specific data structures  120   a - 120   n . In the example shown, the timers are distributed in accordance with a scheme that maps handling of received packets for a given connection to a processor. For example, in the example shown, packets received for connections (arbitrarily labeled) “a”-“g” are handled by processor  102   a , while packets received for connections “q”-“z” are handled by processor  102   n . As shown, the per-processor data structures  120   a - 120   n  includes those timers associated with connections mapped to a given processor. For example, the timer data structure  120   a  for processor  102   a  includes timers associated with connections “a”-“g while the data structure  120   n  for processor  102   n  includes timers associated with connections “q”-“z”.  
         [0014]     Distributing timers can, potentially, eliminate access contention issues to the timers between processors. Additionally, many timer operations result in access of a connection&#39;s TCP Control Block (TCB) and/or other connection-specific data for a connection. By adhering to the same distribution of connections used to process received packets, the likelihood that a given connection&#39;s TCB will be in a processor&#39;s cache when a processor process handles the timers increases.  
         [0015]     The processor-specific timer structures  120   a - 120   n  can be implemented in a wide variety of ways. For example, timer data structure  120   a  may be implemented as a circular linked list of buckets where each bucket can represent the root of a linked list of timers. A given timer can identify the connection, the type of timer, and other information. At a regular interval (e.g., 10 ms), a timer process on the processor  102   a  associated with a data structure  120   a  is triggered that “walks through” the list of timers associated with elapsed buckets. That is, the timer process can handle each timer entry in a bucket&#39;s list in turn, for example, by updating a processor&#39;s TCB, causing a retransmit operation, and so forth.  
         [0016]     To illustrate operation of a sample system using per-processor timer data structures,  FIG. 3A  depicts a multi-processor  102   a - 102   n  system that includes memory  106  and one or more network interface controllers  100  (NICs). The NIC  100  includes circuitry that transforms the physical signals of a transmission medium into a packet, and vice versa. The NIC  100  circuitry also performs de-encapsulation, for example, to extract a TCP/IP packet from within an Ethernet frame.  
         [0017]     The processors  102   a - 102   b , memory  106 , and network interface controller(s) are interconnected by a chipset  114  (shown as a line). The chipset  114  can include a variety of components such as a controller hub that couples the processors to I/O devices such as memory  106  and the network interface controller(s)  100 .  
         [0018]     The sample scheme shown does not include a TCP off-load engine. Instead, the system distributes different TCP operations to different components. While the NIC  100  and chipset  114  may perform some TCP operations (e.g., the NIC  100  may compute a segment checksum), most are handled by processor&#39;s  102   a - 102   n.    
         [0019]     Again, as shown, different connections may be mapped to different processors  102   a - 102   n . For example, operations on packets belonging to connections “a” to “g” may be handled by processor  102   a , while operations on packets belonging to connections “h” to “n” are handled by processor  102   b . This mapping may be explicit (e.g., a table) or implicit.  
         [0020]     In this system, in response to a received packet, the network interface controller  100  can determine which processor  102   a - 102   n  is mapped to the packet&#39;s connection, for example, by hashing packet data (the packet&#39;s “tuple”) identifying the connection (e.g., a TCP/IP packet&#39;s Internet Protocol source and destination address and a TCP source and destination port). The network interface controller  100  can then enqueue packet or a packet descriptor (e.g., using Direct Memory Access (DMA)) to a processor or connection-specific receive queue corresponding to processor  102   a . To alert the processor  102   a  of the arrival of a packet, the network interface controller  100  can signal an interrupt. Potentially, the controller  100  may use interrupt moderation which delays an interrupt for some period of time. This increases the likelihood multiple packets will have arrived before the interrupt is signaled, enabling a processor to work on a batch of packets and reducing the overall number of interrupts generated. In response to an interrupt, the processor  102   a  may dequeue and process the next entry (or entries) in its receive queue  110   a . Processing can include navigating the TCP state machine for a connection, performing segment reordering and reassembly, tracking acknowledged bytes in a connection, managing connection windows, and so for (see The Internet&#39;s Engineering Task Force (IETF), Request For Comments #793). Since the processor  102   a  only processes packets for a limited subset of connections, the likelihood that the TCB for a connection remains in the processor&#39;s  102   a  cache increases.  
         [0021]     As shown in  FIG. 3A , each processor  102   a - 102   n  has its own associated timer data structure  120   a - 120   n . These structures  120   a - 120   n  may reside in memory  106  and/or the cache of the associated processor  102   a - 102   n.    
         [0022]     For an on-going connection, timers are frequently armed and/or disarmed. When a timer originates on the “right” processor  102   a  (i.e., the processor mapped to the timer&#39;s connection), the processor  102   a  can modify its timer data structure  120   a  accordingly. However, a timer may originate or be handled by the “wrong” processor (i.e., a processor other than the processor mapped to the connection). For example, as shown in  FIG. 3A , a timer  124  for connection “a” originates at processor  102   n  instead of the processor  102   a . For instance, processor  102   n  may initiate a transmit operation that requires a corresponding retransmit timer to be scheduled.  
         [0023]     Potentially, in response to a new timer  124 , the “wrong” processor  102   n  can modify the “right” processor&#39;s  102   a  timer data structure accordingly. However, such an approach may reintroduce many contention issues. Alternately, as shown in  FIG. 3B , the “wrong” processor  102   n  can transfer the timer to the “right” processor  102   a  by enqueuing an entry for the timer  124  in a processor-specific  112   a  (labeled “TimerQ”) or connection-specific queue. The entry may include timer data and/or include a reference to the timer data.  
         [0024]     The processors  102   a - 102   n  may poll their processor-specific queues  112   a  (or the queues of mapped connections) for enqueued timer entries. Alternately, instead of polling, as shown in  FIG. 3C , the “wrong” processor can schedule an interrupt on the network interface controller  100  and write data that enables the processors to identify the interrupt cause, for example, to distinguish the interrupt from a NIC  100  interrupt signaling arrival of received packets. For instance, processor  102   n  can set a software interrupt flag in an interrupt cause register maintained by the network interface controller  100 . As shown in  FIG. 3D , in response to the interrupt request, the network interface controller  100  signals an interrupt to the processors  102   a - 102   n  servicing connections. The network interface controller drivers operating on the processors  102   a - 102   n  respond to the interrupt by checking the data (e.g., flag(s)) indicating the interrupt cause.  
         [0025]     As shown in  FIG. 3E , the “right” processor  102   a  can dequeue timer entries and modify its timer data structure  120   a  accordingly. Dequeuing entries from a processor&#39;s timer queue  112   a  may require a lock on the timer queue  112   a . This lock, however, may be amortized over multiple packets and minimally affect the TCP fast path that processes segments with an application payload. Since modification of a given timer data structure  120   a  may be handled by the same instructions handling received packets, there is no need for locks on the timer data structure  120   a  during the modifications.  
         [0026]     Timer entries can specify not only timer arming that causes insertion of a timer into a timer data structure  120   a , but also timer disarming. Disarming may occur frequently. For example, a keep-alive timer may be disarmed after a packet is received for a previously dormant connection. Timer disarming may be split into two stages. For example, in response to a request to disarm a timer, the processor  102   a  may find and flag the timer entry as disarmed without actually removing the timer from the data structure  120   a . The timer process that walks through the timers associated with a bucket can skip processing of timers flagged as disarmed. Like other timers, the disarmed timers are deleted from the data structure  120   a  during the “walk through” and the memory allocated to the disarmed timer may be freed. Thus, the flagging enables the complexity of extraction of a disarmed timer from a timer data structure to both be deferred and simplified.  
         [0027]      FIG. 4  and  FIG. 5  illustrate processes implemented by the processors  102   a - 102   n  to transfer timers. In  FIG. 4 , a processor  102   n  determines  152  if the connection associated with a timer is mapped to a different processor  102   a . If so, the processor  102   n  can enqueue  154  an entry for the timer. As shown in  FIG. 5 , the “right” processor can dequeue  162  the event data and perform the appropriate arming/disarming operations  164 .  
         [0028]     Though the description above repeatedly referred to TCP as an example of a protocol that can use techniques described above, these techniques may be used with many other protocols such as protocols at different layers within the TCP/IP protocol stack and/or protocols in different protocol stacks (e.g., Asynchronous Transfer Mode (ATM)). Further, within a TCP/IP stack, the IP version can include IPv4 and/or IPv6.  
         [0029]     While  FIGS. 3A-3E  depicted a typical multi-processor host system, a wide variety of other multi-processor architectures may be used. For example, while the systems illustrated did not feature TOEs, an implementation may nevertheless feature them. Additionally, the term processor can include a CPU or other processor or programmable processor core.  
         [0030]     The techniques above may be implemented using a wide variety of circuitry. The term circuitry as used herein includes hardwired circuitry, digital circuitry, analog circuitry, programmable circuitry, and so forth. The programmable circuitry may operate on computer programs disposed on a computer readable medium.  
         [0031]     Other embodiments are within the scope of the following claims.