Patent Publication Number: US-8116229-B2

Title: Reducing packet drops in networks guaranteeing in-order delivery

Description:
BACKGROUND OF THE INVENTION 
     A data network is said to guarantee In-Order Delivery (IOD) if the packets sent by a source host are received in the same order at the destination host. 
     Most data networks are not required to guarantee in-order delivery. For example, in IP networks, the packets sent by a source host can be received out of order at a destination host. Such networks typically employ a higher layer protocol like Transmission Control Protocol (which uses a re-sequencing buffer at the destination host), to guarantee in-order delivery of packets to the host applications. 
     However, there are some networks (primarily Layer 2 (L2) networks) that are required to guarantee In-Order Delivery (IOD). Fibre Channel (FC) is an example of such an L2 network. Some FC capable end host devices expect the FC network to deliver packets in order. Out-of-order delivery of packets to such hosts can result in catastrophic failures. With Input/Output (IO) consolidation, newer L2 networks like Data Centre Ethernet (DCE) also need to guarantee IOD. Hence, IOD is a very important feature of new L2 networks. 
     TECHNICAL FIELD 
     The present disclosure relates generally to reducing the number of packet drops in a network guaranteeing in-order delivery due to the addition of a new equal cost path between a source and a destination. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an example of network topology with only a single path between source and destination switches; 
         FIG. 2  illustrates the example network topology of  FIG. 1  with a new link added and having two equal cost paths between source and destination; 
         FIG. 3  illustrates an example where the addition of a new equal cost path could cause out-of-order packet delivery; 
         FIG. 4  illustrates pseudocode of an example procedure for determining the convergence nodes of a destination node in a network topology; and 
         FIG. 5  illustrates an example of a network device. 
     
    
    
     DESCRIPTION OF EXAMPLE EMBODIMENTS OVERVIEW 
     Reference will now be made in detail to various embodiments of the invention. Examples of these embodiments are illustrated in the accompanying drawings. While the invention will be described in conjunction with these embodiments, it will be understood that it is not intended to limit the invention to any embodiment. On the contrary, it is intended to cover alternatives, modifications, and equivalents as may be included within the spirit and scope of the invention as defined by the appended claims. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the various embodiments. However, the present invention may be practiced without some or all of these specific details. In other instances, well known process operations have not been described in detail in order not to unnecessarily obscure the present invention. Further, each appearance of the phrase “an example embodiment” at various places in the specification does not necessarily refer to the same example embodiment. 
     One example embodiment is a method that identifies a set of convergence node switches of a destination switch in a network including an interconnected group of switches when a new equal cost path is added to the network between a source switch and the destination switch, with the network having a plurality of equal cost paths connecting the source switch and the destination switch, where the set of convergence node switches includes those switches which are common to all equal cost paths between the source switch and the destination switch. 
     In the following, the term switch is utilized broadly to include any network device such as a router, bridge, switch, layer 2 or layer 3 switch, gateway, etc., that is utilized to implement connectivity within a network or between networks. 
     The number of hops between the source switch and each convergence node switch is calculated and packets are dropped at the source switch for a selected time interval when the new equal cost path is added, where the time interval has a value equal to the sum of switch lifetimes of the packet for each switch disposed up to the convergence node switch having the least number of hops from the source switch. 
     DESCRIPTION 
       FIG. 1  depicts an example network having five switches, s 1  (source switch), . . . s 5  (destination switch) and two hosts (source host and destination hosts). Links between switches will be referred to by utilizing two equivalent descriptions. For example, in  FIG. 1  the link between s 1  and s 2  is labeled L 1 . Alternatively, the same link can be referred to by the tuple (s 1 ,s 2 ) which sets forth the end points of the link. In  FIG. 2  there are first and second equal cost paths, {L 1 ,L 2 ,L 4 ,L 5 } and {L 6 ,L 3 ,L 4 ,L 5 } respectively, between the source and the destination hosts. The cost of a path is determined by a metric assigned to each link in the path by a routing protocol. It is assumed that all links in this network have the same value for link cost. 
     Out-of-Order Delivery (OOO) can occur when there are multiple paths between a source and a destination. Equal Cost Multi-Paths (ECMP) between a source and a destination are commonly built using link state routing protocols like Fabric Shortest Path First (FSPF) in FC networks and Intermediate System-Intermediate System Protocol (IS-IS) in DCE networks. Most switches in an L2 network do not, by themselves, cause packets of a flow to be transmitted out of order. Hence, in steady state, when there are no network topology changes, most L2 networks do guarantee IOD of packets of various flows. This is because the switches use flow based hashing to map individual flows to unique paths between source and destination. Hence, though there are multiple paths between source and destination, a given flow uses only one path and IOD is guaranteed for all packets within a flow. For example, in the topology example of  FIG. 2 , at s 1  the cost to reach the destination is the same whether a packet is sent on L 1  or L 6 . However, for a particular flow, a hash algorithm executed on s 1  hashes designated fields in each packet and selects an outgoing link based on the hashed value. Thus, for a given flow all packets will be directed to the same outgoing link, e.g., L 1 , and IOD is assured during the steady state. 
     But IOD is not guaranteed during network topology changes. This condition will now be described in more detail with reference to  FIG. 2 .  FIG. 2  depicts the same network topology as  FIG. 1  except that a new link, L 6 , is added between s 1  and s 3 . This leads to the formation of two equal cost paths between the source and destination hosts denoted by: ECP 1 ={L 1 ,L 2 ,L 4 ,L 5 }, ECP 2 ={L 6 ,L 3 ,L 4 ,L 5 }. 
     The possible out-of-order condition can be illustrated by considering two packets, p 1 , p 2 , in the same flow where p 1  is prior to p 2  in the flow. Assume that p 1  is transmitted when the topology is as depicted in  FIG. 1  so that it will be forwarded to s 2  over link L 1  and to s 4  over link L 2 . Also, assume that p 2  is transmitted after the network is reconfigured to the topology as depicted in  FIG. 2  and that p 2  is rehashed to be forwarded to s 3  on link L 6  and to s 4  over link L 3 . 
     As will now be described with reference to  FIG. 3 , it is possible for p 2  to arrive at s 4  before p 1  arrives at s 4  so that the packets are delivered out of order. 
     First, every switch has a defined maximum switch lifetime (typically 500 ms) for each packet. A packet that is queued in a switch for more than the switch lifetime is simply dropped. Similarly, the maximum network lifetime of a packet is D×(maximum switch lifetime) where D is the maximum number of switches between any source and destination. In other words, D is the network diameter. For example, in  FIG. 2 , D=4. Hence, a packet cannot be in the network for a time greater than the maximum network lifetime equal to about 2.0 seconds. 
     In  FIG. 3  p 1  is transmitted from s 1  at time t and p 2  is transmitted from 1 at time t+dt so the packets are transmitted from s 1  in order. In the following it is assumed transmission over the links is instantaneous and that delays are caused due to queuing at the switches. The delay at s 2  is dt(s 2 ) and the delay at s 3  is dt(s 3 ). Accordingly, as depicted in  FIG. 3 , p 1  arrives at s 4  at time t+dt(s 2 ) and p 2  arrives at s 4  at time t+dt+dt(s 3 ). If dt(s 2 ) is greater than (dt+dt(s 3 )) then p 2  will arrive at s 4  before p 1  and the packets in the flow will be out of order. 
     Packets in the flow subsequent to p 2  will be transmitted on the same path. The simple solution essentially drops traffic at s 1  for the maximum network lifetime before making the change in the set of equal cost multi-paths (ECMP) to the destination during network topology changes. This ensures that all “old packets” carried on older sets of ECMPs are ‘flushed’ out of the network before newer packets are carried on the newer set of ECMPs. 
     For example, when a new link, e.g., L 6 , is added to the topology depicted in  FIG. 1  (as depicted in  FIG. 2 ) s 1  will drop all packets arriving in the next 2.0 seconds. This simple solution causes a large number of packet drops for every route change for a duration of D×500 ms. While D is typically only 4 in FC networks, it is expected to be much higher in DCE networks. Dropping of such a high number of packets can cause problems like unnecessary network resource usage due to packet retransmissions and increased latency. 
     An example of an embodiment that flushes packets only up to a first convergence node instead of for the entire network will now be described. The set of convergence nodes of a destination includes the nodes (switches) that are common to all equal cost multi-paths (ECMPs) from the source. For example, in  FIG. 2  the convergence nodes for the destination from s 1  are s 4  and s 5 . 
     In the topology depicted in  FIG. 2 , packets have to be flushed only up to s 4 , the convergence node closest to the switch where the new link is added (in this case s 1 ). This is because once packets in the flow arrive at s 4  (the first convergence node) the later packets cannot overtake the earlier packets. So packets are dropped at s 1  until previously transmitted packets in the flow have arrived at s 4 . From s 4 , packets take the same path as before and cannot overtake each other. The time period for dropping packets is only the maximum switch lifetime of s 1  plus either s 2  or s 3  instead of the sum of the maximum switch lifetimes for all switches between the source and destination. Accordingly, in the example topology of  FIG. 2  the time period of dropping packets is reduced from 2.0 seconds to 1.0 second. 
     In an example embodiment a modification of the Dijkstra Shortest Path First (SPF) algorithm, E. W. Dijkstra. “ A Note on Two Problems in Connexion with Graphs .” Numerische Mathematik, Vol. 1, 1959, pp. 269-271, is utilized to calculate the set of convergence nodes. For each destination this modified algorithm gives: 1) the set of next hops (for the various equal cost paths); 2) the set of convergence nodes; and 3) the convergence node that is closest to the source (as determined by the number of hops). 
     Pseudocode for the modified Dijkstra algorithm is depicted in  FIG. 4 . An example calculation will now be presented for switch s 1  for the topology depicted in  FIG. 2 . In this example the graph (G) includes vertices (v) which are switches s 1 -s 5  and the weights (w) for links L 1 , L 6 , L 2 , L 3 , L 4 , and L 5  are equal to 1. 
     Q is initialized with all the vertices (switches) in the graph (network) and the while loop is executed until Q is equal to the empty set. The first vertex extracted is u=s 1  and the edges (links) are (s 1 ,s 2 ) and (s 1 ,s 3 ), or equivalently, L 1  and L 6 . The first if statement is true because d[s 2 ] and d[s 3 ] are initialized to infinity. Therefore for edge (s 1 ,s 2 ): v=s 2 ; d[s 2 ]=1; nh[s 2 ]=1; cv[s 2 ]={s 2 }; and mp[s 2 ]={L 1 }. For edge (s 1 ,s 3 ): v=s 3 ; d[s 3 ]=1; nh[s 3 ]=1, cv[s 3 ]={s 3 }; and mp[s 3 ]={L 6 }. 
     Next the second vertex extracted is u=s 2  and the edge (link) is (s 2 ,s 4 ), or equivalently, L 2 . The first if statement is true because d[s 4 ] is initialized to infinity. Therefore for edge (s 2 , s 4 ): v=s 4 ; d[s 4 ]=2; nh[s 4 ]=2; cv[s 4 ]={s 2 ,s 4 }; and mp[s 4 ]={L 1 }. After this, edge (s 2 , s 1 ) or link L 1  is selected. But since both the if conditions fail, this link is ignored. 
     Next the third vertex extracted is u=s 3  and the edge (link) is (s 3 ,s 4 ), or equivalently, L 3 . The first if statement is not true because d[s 4 ]=2. The second if statement is true indicating the existence of two equal cost paths to s 4 . For edge (s 3 , s 4 ): v=s 4 ; d[s 4 ]=2; nh[s 4 ]=2; cv[s 4 ]:=cv[s 4 ] intersection (cv[s 3 ] union {v})={s 2 ,s 4 } intersection ({s 3 } union {s 4 })={s 2 ,s 4 } intersection {s 3 ,s 4 }={s 4 }; and mp[s 4 ]=mp[s 4 ] union mp[s 3 ]={L 1 } union {L 8 }={L 1 ,L 6 }. After this, edge (s 3 , s 1 ) or link L 6  is selected. But since both if conditions fail, this link is ignored. 
     Accordingly, the modified algorithm has computed the identity of the first entry in the set of convergence nodes, i.e., s 4 , the multiple-path set to reach s 4 , i.e., {L 1 , L 6 }, and the number of hops to the convergence node, i.e., 2. 
     Next the fourth vertex extracted is u=s 4  and the edge (link) is (s 4 ,s 5 ) or equivalently, L 4 . The first if statement is true because d[s 5 ] is initialized to infinity. Therefore for edge (s 4 , s 5 ): v=s 5 ; d[s 5 ]=3; nh[s 5 ]=3; cv[s 5 ]={s 4 , s 5 }; and mp[s 5 ]={L 1 , L 6 }. After this, edge (s 4 , s 2 ) or link L 2  is selected. But since both if conditions fail, this link is ignored. Similarly, link L 3  or (s 4 ,s 3 ) is also ignored since it fails both if conditions. 
     Next the fifth vertex u=s 5  is extracted and the edge (link) (s 5 ,s 4 ) or equivalently, L 4  is selected. However, since both if conditions fail for this link, it is ignored. 
     At this point the algorithm has processed all the vertices and has computed convergence nodes towards the destination switch (cv[s 5 ]={s 4 , s 5 }). Since, from s 1  to destination, the number of hops towards convergence node s 4  (nh[s 4 ]=2) is less than number of hops towards convergence node s 5  (nh[s 5 ]=3), s 4  is the closest convergence node. Hence packets will be dropped at node s 1  for time 500 ms×(nh[s 4 ])=500 ms×(2)=1000 ms=1.0 second. 
       FIG. 5  depicts an example of a network device including a motherboard  10  having shared DRAM  12 , DRAM  14 , NVRAM  16 , ROM  18  and a CPU  20 . (Other components on the motherboard not relevant to the present description are not depicted). The DRAM  14  is the working storage utilized by the CPU and the shared DRAM  12  is dedicated to handling the network device&#39;s packet buffer. The NVRAM (non-volatile RAM) is used to store the network device&#39;s configuration file and also includes flash memory for storing an image of the Operating System. The ROM  18  holds a boot-start program which holds a minimum configuration state needed to start the network device. Alternatively, other configurations of the motherboard can be used. For example, the motherboard may not have separate ROM or NVRAM and the configuration file and operating system image may be stored and executed out of flash memory. 
     In an example embodiment, software for implementing the modified Dijkstra SPF algorithm is included as a part of the operating system stored in memory and is executed by the CPU  20 . Alternatively, parts of the algorithm could be implemented as hard-wired logic. 
     The invention has now been described with reference to the example embodiments. Alternatives and substitutions will now be apparent to persons of skill in the art. Accordingly, it is not intended to limit the invention except as provided by the appended claims.