Abstract:
In general, in one aspect, the disclosure describes a method of, at different times, comparing multiple reachability measures of a remote device, and if the reachability measures of the remote device differ, setting the reachability measures to the same value.

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; an application entitled “DISTRIBUTING TIMERS ACROSS PROCESSORS”, filed on Jun. 30, 2004, and having attorney/docket number 42390.P19610; and an application entitled “NETWORK INTERFACE CONTROLLER INTERRUPT SIGNALING OF CONNECTION EVENT”, filed on Jun. 30, 2004 , 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. That is, 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 application data sent across a network by an application. A receiver can restore the original stream of data by reassembling the payloads of 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). 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]      FIGS. 1A and 1B  illustrate a sample system that maintains reachability measures.  
         [0007]      FIGS. 2A-2C  illustrate synchronizing and aging of reachability deltas.  
         [0008]      FIG. 3  is a flow-chart of a process to reset a reachability delta.  
         [0009]      FIG. 4  is a flow-chart of a process to synchronize and age reachability deltas. 
     
    
     DETAILED DESCRIPTION  
       [0010]     In a connection, a pair of end-points may both act as senders and receivers of packets. Potentially, however, one end-point may cease participation in the connection, for example, due to hardware or software problems. In the absence of a message explicitly terminating the connection, the remaining end-point may continue transmitting and retransmitting packets to the off-line end-point. This needlessly consumes network bandwidth and compute resources. To prevent such a scenario from continuing, some network protocols attempt to gauge whether a communication partner remains active. After some period of time has elapsed without receiving a packet from a particular source, an end-point may terminate a connection or respond in some other way.  
         [0011]     As an example, some TCP/IP implementations maintain a table measuring the reachabillity of different media access controllers (MACs) transmitting packets to the TCP/IP host. This table is updated as packets are received and consulted before transmissions to ensure that a packet is not transmitted if a connection has “gone dead”. However, in a system where multiple processors of a host handle traffic, coordinating access between the processors to a monolithic table can degrade system performance, for example, due to locking and cache invalidation issues.  
         [0012]      FIG. 1A  illustrates a scheme that features state data  108   a - 108   n  associated with different processors  102   a - 102   n . As shown, the state data  108   a - 108   n  lists multiple neighboring devices (e.g., by media access controller (MAC) address) and a corresponding reachability measure (e.g., a timestamp or delta). In this case, the reachability measure is a delta value that is periodically incremented. Each processor  102   a - 102   n  can update its corresponding neighbor state data  108   a - 108   n  for packets handled. For example, a processor  108   a  may reset the delta value for a particular neighbor after receiving a packet from the device. By each processor  102   a  having its own associated set of neighbor state data  108   a , the state data  108   a  can be more effectively cached by the processor  102   a . Additionally, the scheme can reduce inter-processor contention issues.  
         [0013]     In greater detail, the sample system of  FIG. 1A  includes multiple processors  102   a - 102   n , 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.  
         [0014]     The processors  102   a - 102   b , memory  106 , and network interface controller(s) are interconnected by a chipset  120  (shown as a line). The chipset  120  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 .  
         [0015]     The sample scheme shown in  FIG. 1A  does not include a TCP off-load engine. Instead, the system distributes different TCP operations to different components. While the NIC  100  and chipset  201  may perform and/or aid some TCP operations (e.g., the NIC  100  may compute a segment checksum), most are handled by processor&#39;s  102   a - 102   n.    
         [0016]     As shown, different connections may be mapped to different processors  102   a - 102   n . For example, operations on packets belonging to connections (arbitrarily labelled) “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.    
         [0017]      FIG. 1B  illustrates receipt of a packet  114  transmitted via remote MAC “Q”. As shown, the NIC  100  determines which of the processors  102   a - 102   n  is mapped to the packet&#39;s connection, for example, by hashing data in the packet&#39;s  114  header(s) (e.g., the IP source and destination addresses and the TCP source and destination ports). In this example, the packet  114  belongs to connection “c”, mapped to processor  102   a . The NIC  100  may queue the packet  114  for the mapped processor  102   a  (e.g., in a processor-specific Receive Queue (not shown)).  
         [0018]     As shown, the neighbor state data  108   a  associated with processor  102   a  may be updated to reflect the packet  114 . That is, as shown, the processor  102   a  may determine the neighbor, “Q”, that transmitted the packet  114 , lookup the neighbor&#39;s entry in the processor&#39;s  102   a  associated state data  108   a  and set the neighbor&#39;s reachability delta to 0.  
         [0019]     Periodically, a process ages the neighbor state data, for example, by incrementing each delta. For example, in  FIG. 1B , at least “3” increment operations have occurred since the last packet was received from neighbor “R”. The delta can, therefore, provide both a way of determining when activity has occurred (because the delta has been reset) and a way of determining whether a particular neighbor is “stale”. Again, if the delta exceeds some threshold value, a processor may prevent further transmissions to the neighbor and/or initiate connection termination. For example, a processor may lookup a neighbor&#39;s delta before a requested transmit operation.  
         [0020]     Potentially, the neighbors monitored by the different processors  102   a -  102   n  may overlap. For example, in  FIG. 1A , an entry for neighbor “Q” is included in both the state data  108   a  associated with processor  102   a  and the state data  108   b  associated with processor  102   b . One reason for this overlap is that, potentially, multiple connections may travel through the same remote device. For example, multiple connections active on a remote host may travel through the same remote MAC but be processed by different processors  102   a - 102   n . Phrased differently, two packets may travel through the same neighboring MAC but be mapped to different processors  102   a - 102   n . In the scheme illustrated above, these two different packets will cause each processor to update its reachability measure for this neighbor. If these packets are received at different times, however, this will cause an inconsistency between the different reachability measures for a given neighbor in the different sets of data. That is, at time “x”, one processor  102   a  may reset its measure for a neighbor in its associated state data  108   a  while, at time “y”, a different processor  102   b  subsequently resets its measure for the same neighbor.  
         [0021]     To maintain consistency across the different sets of data  108   a - 108   n ,  FIGS. 2A-2C  illustrates a process that can synchronize the different measure values. As shown, the same process may also be used to age the measures.  
         [0022]     To synchronize, the process can access the different deltas for a given neighbor and set each to the lowest delta value. For example, as shown in  FIG. 2A , the process compares the different values for neighbor “Q”. In this example, the reachability measure for “Q” in the data  108   b  associated with processor  102   b  has been aged twice while processor  102   a  recently received a packet from neighbor “Q” and reset “Q”-s delta. As shown in  FIG. 2B , to reflect the most recent neighbor activity detected by any of the processors  102   a -  102   n , the process sets both delta values for “Q”to the lesser of the two current delta values (“ 0 ”). As shown, in  FIG. 2C , the process then ages each of the reachability measures of each neighbor in the data  108   a  associated with each participating processor  102   a - 102   n.    
         [0023]     The process illustrated in  FIGS. 2A-2C  may be scheduled to periodically execute on one of the processors  102   a -  102   n . Because protocols are often tolerant of some degree of connection staleness, the time period between executions may be relatively large (e.g., measured in seconds or even minutes).  
         [0024]      FIG. 3  depicts a reachability measure update process  200  each processor handling packets can perform. As shown in response to a received  202  packet, the process  200  can update  206  the reachability measure for the neighbor transmitting the packet. Potentially, the process  200  may only update the measure in certain circumstances, for example, if  204  the packet updates the connection&#39;s receive window (e.g., the packet includes the next expected sequence of bytes).  
         [0025]      FIG. 4  depicts a process  210  used to synchronize and age the reachability measures across the different sets of state data  108   a - 108   n . As shown, for each neighbor  220 , the process  210  compares  212  the reachability delta for the neighbor across the different sets of state data associated with the different processors. If the deltas differ  214 , the process  210  can set each delta to the same value (e.g., the lowest of the delta values). The process  210  also ages  218  each measure. The process  210  shown is merely an example and a wide variety of other implementations are possible.  
         [0026]     The techniques described above may be used in a variety of computing environments such as the neighbor aging specified by Microsoft TCP Chimney (see “Scalable Networking: Network Protocol Offload—Introducing TCP Chimney” WinHEC 2004 Version). In the Chimney scheme, before transmitting a segment, an agent (e.g., a processor or TOE) accesses a neighbor state block to ensure that a neighbor has some receive activity that advanced a TCP window within a certain threshold amount of time (e.g., Network Interface Control (NIC) Reachabilty Delta&lt;‘NCEStaleTicks’). If the neighbor is stale, the offload target must notify the stack before transmitting the data.  
         [0027]     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.  
         [0028]     Additionally, while  FIGS. 1A and 1B  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. Such TOEs may participate in the scheme described above (e.g., a TOE processor may have its own associated state data). Further, the different processors  102   a - 102   n  illustrated in  FIGs. 1A and 1B  can be different central processing units (CPU), different programmable processor cores integrated on the same die, and so forth.  
         [0029]     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.  
         [0030]     Other embodiments are within the scope of the following claims.