Abstract:
The present invention encompasses methods, apparati, and computer-readable media for detecting and removing unwanted loops in communications networks having host processors ( 10 ), nodes ( 16 ), and segments ( 14 ) connecting the nodes ( 16 ). A method embodiment of the present invention comprises the steps of collecting and storing a set of steady state data regarding direction of network ( 1 ) traffic flow through the nodes ( 16 ) and segments ( 14 ) for at least one network flow; comparing newly sampled flow with stored steady state data to detect flows whose paths contradict their steady state direction; and identifying a network loop when a segment ( 14 ) carries such contradictory flows.

Description:
TECHNICAL FIELD 
       [0001]    This invention pertains to the field of communications networks, such as digital packet networks, and, in particular, to the problem of unwanted network loops. 
       BACKGROUND ART 
       [0002]    Unwanted network loops are a common problem in large and small communications networks. Such loops can cause network broadcast storms, resulting in significant deterioration of network bandwidth and performance. Such storms can flood the host processors with duplicate packets, resulting in wasted CPU utilization on said hosts. These problems are addressed by the present invention. 
       DISCLOSURE OF INVENTION 
       [0003]    The present invention encompasses methods, apparati, and computer-readable media for detecting and removing unwanted loops in communications networks having host processors ( 10 ), nodes ( 16 ), and segments ( 14 ) connecting the nodes ( 16 ). A method embodiment of the present invention comprises the steps of collecting and storing a set of steady state data regarding direction of network ( 1 ) traffic flows through the nodes ( 16 ) and segments ( 14 ) for at least one network flow; comparing newly sampled flow with stored steady state data to detect flows whose paths contradict their steady state direction; and identifying a network loop when a segment ( 14 ) carries such contradictory flows. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0004]    These and other more detailed and specific objects and features of the present invention are more fully disclosed in the following specification, reference being had to the accompanying drawings, in which: 
           [0005]      FIG. 1  is topological sketch of a typical network  1  of the prior art that can fruitfully employ the teachings of the present invention. 
           [0006]      FIG. 2  is a sketch of the network  1  of  FIG. 1  showing a broadcast flow emanating from host processor  10 (A). 
           [0007]      FIG. 3  is a sketch of the network  1  of  FIG. 2  in which a loop is present due to a new segment  14 ( 5 , 6 ) arising between switches  12 ( 5 ) and  12 ( 6 ). 
           [0008]      FIG. 4  illustrates the network of  FIG. 3  in which loop pointers  17  of the present invention collectively point to the loop. 
           [0009]      FIG. 5  is a flowchart showing a method embodiment of the present invention in which intentional network  1  reconfigurations are distinguished from unwanted loops. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0010]    This invention allows unwanted network loops to be precisely detected and identified. The obtained network loop information can be used to instigate remedial action to remove the loop. This procedure can be automated, resulting in a self-healing as well as a self-diagnosing network. 
         [0011]    This invention is applied to a Layer 2 data network for purposes of illustration. The applicability of the present invention is not limited to Layer 2 digital networks. It can also be used with L3 digital networks, digital networks other than L2 and L3 networks, and analog networks. For digital networks, the data does not have to be packetized, as long as the flows can be differentiated by observing the data. 
         [0012]    This invention can correctly distinguish between intentional network reconfigurations and network loops (see  FIG. 5 ). This capability minimizes false positives. 
         [0013]    In the embodiments of the invention illustrated herein, packet sampling is used to collect information about the real-time state of the network  1 . The packet samples can be obtained via any existing mechanisms that allow for the sampling of flows, such as the processes (programs) sflow, netflow, or others. As used herein, “traffic flows” are streams of traffic (moving data) that share similar characteristics (for example, source  10  and destination  10 ). The flow information collected from the samples over a period of time when no loop exists is called the “steady state information”. 
         [0014]    In this steady state, the network  1  can be represented as a tree, with no closed data paths (loops), as illustrated in  FIG. 2 . For every flow of traffic, a path can be traced from source  10  to destination  10 . This path can be broken into individual segments  14  that connect nodes  16  (each port of a switch  12  present in the network  1  is a network node  16 ). For each traffic flow, traffic can legitimately flow only in a single direction along each segment  14 . This direction is learned and recorded in the steady state. 
         [0015]    In a centralized embodiment of the present invention, this recorded state is collected and stored on a network management computer (processing entity) which processes the sampled packets. A host processor  10  can perform the duties of the processing entity. In an alternative embodiment, the processing entity can be a separate collector  11 , in which case the collector  11  can be connected to the network  1  via any type of connection. 
         [0016]    A network storm can occur when an unwanted closed loop path is created in the network  1 . Packets can travel in a closed loop along this path indefinitely. This is more fully described below in conjunction with  FIGS. 3 and 4 . When an unwanted loop arises, the uni-directional nature of flows in many segments  14  gets violated: these segments  14  carry bidirectional flows for the same overall network flow. The flows start taking paths that contradict their steady state direction. This violation of direction of flows can be detected by using the stored steady state information and comparing it with the newly sampled packet information, which is sampled for every port (node)  16  in both the ingress and egress directions. 
         [0017]    This invention introduces the concept of a loop pointer  17 . A loop pointer  17  is a directional pointer which is local to every segment  14 . All pointers  17  point to the direction of the loop in the network  1 . 
         [0018]    Every time a contradictory packet sample is detected, i.e., one which violates the stored steady state direction of that particular flow on a particular segment  14 , a loop pointer  17  is created for that segment  14 . This loop pointer  17  points in the direction opposite to the direction of transit of the contradictory packet sample. 
         [0019]    Over the course of time, unwanted loops in the network  1  result in creation of a set of loop pointers  17 . These loop pointers  17  form a sequential linked list which passes through nodes  16  in the network  1 . The loop pointers  17  get generated all across the network  1 . All the loop pointers  17  in network  1  always point to the direction of the loop, regardless of the number of flows being analyzed, and regardless of where in the network  1  the pointers  17  are located. In these multi-flow scenarios, the loop pointers  17  always point and lead to the loop, in spite of being created by different traffic flows. 
         [0020]    Note that loop pointers  17  get created only for flow information that contradicts the steady state information, not for flow information that agrees with existing steady state information. 
         [0021]    In the centralized embodiment of the present invention, the loop location information is collected from the distributed nodes  16  (or from the routers or switches  12  associated with said nodes), but is stored and processed collectively by a single network management entity (processing entity)  10 ,  11 . 
         [0022]    In an alternative embodiment (the “distributed” embodiment), the storing and processing of the steady state information is performed in a distributed fashion. In this embodiment, a software, firmware, and/or hardware module associated with each node  16  determines whether there is a bidirectional flow on a segment. A loop pointer  17  is hence generated on that segment. The module can declare the presence of a loop pointer  17  and pass the information in the direction of the loop pointer  17  to the peer node  16  at the other end of the segment  14 . Furthermore, once the span of the loop is identified, any of the nodes  16  present in the loop can break the loop and thereby end the storm. 
         [0023]    Using predefined rules, the network management host  10  or collector  11  (in the centralized embodiment), or the networking nodes  16  (in the distributed embodiment), can diagnose and terminate the network  1  loop in a completely autonomous manner. This invention is therefore self-healing as well as self-diagnosing. 
         [0024]    The centralized and distributed embodiments are not mutually exclusive; they can operate simultaneously. 
         [0025]      FIG. 1  shows an exemplary prior art network  1  having six switches  12  and eight host processors  10 .  FIG. 1  shows a L2 digital packet switching network, for purposes of illustration only. All ports  16  in all six switches  12  have sampling enabled in both the ingress and egress direction. All samples are sent to a single collector  11  in this example. Collector  11  is shown with just a single dashed lead line, even though it is connected to all nodes  16 , to avoid cluttering the drawings. For this special case where collector  11  is used, typically all the method steps described herein are performed by collector  11  as the processing entity. 
         [0026]    Each port  16  is referred to as a node in the network  1 , and a link connecting two nodes  16  is referred to as a segment  14 . Segments  14  can be physically embodied through any current or future means, including copper wires, microwave signals, optical cables, etc.  FIG. 1  shows segments  14  as solid lines to indicate that the paths exist, regardless of whether any actual traffic is flowing on the paths. Segments  14  can also be a logical connection between two nodes  16 , rather than a physical link. For example, one embodiment of the invention detects loops within individual VLANs. 
         [0027]      FIG. 2  shows (by means of dashed lines) the steady state direction of traffic flow for a broadcast frame (single flow) from source host processor  10 (A). The broadcast message is sent to all hosts  10  in the network  1 . The packets for this flow are sampled at a preselected sampling rate by the nodes  16 , which send these samples to the collector  11 . The information collected from the samples gets recorded in the collector  11 . This body of information is called the steady state information. The collector  11  records the direction of flow in each segment  14  for a particular traffic flow. 
         [0028]      FIG. 3  shows that a new unwanted connection  14 ( 5 , 6 ) has arisen between switches  12 ( 5 ) and  12 ( 6 ). This can occur by virtue of a bad design or human error, or a combination of the two, e.g., a software error, and creates a new closed loop path. The unwanted loop goes via switches  12 ( 4 ),  12 ( 5 ), and  12 ( 6 ), with the newly formed connection  14 ( 5 , 6 ) completing the loop. In  FIG. 3 , note the new dashed lines between ports  16 ( 6 , 1 ) and  16 ( 6 , 2 ), and between ports  16 ( 5 , 1 ) and  16 ( 5 , 2 ), which complete the loop. 
         [0029]      FIG. 4  shows that the newly introduced loop causes the broadcast traffic from host  10 (A) to be looped back into the network  1  for this particular flow. In  FIG. 4 , this contradictory flow is indicated by dashed lines having shorter dashes than the dashes in the lines that indicate the original flow. This contradictory flow originates at two places:
       At switch  12 ( 5 ) port  16 ( 5 , 2 ).   At switch  12 ( 6 ) port  16 ( 6 , 2 ).       
 
         [0032]    Only one flow is illustrated in  FIG. 4 , to avoid cluttering the drawing, but in practice, a loop can be detected by observing one network flow or several network flows. During the preselected sampling period, just one host  10 , or more than one host  10 , can be sending data over the network  1 . 
         [0033]    Switches  12 ( 5 ) and  12 ( 6 ) treat the looped-back traffic as broadcast traffic entering the switch  12 ( 5 ),  12 ( 6 ), and hence send the looped-back traffic all over the network  1 . The broadcast traffic not only gets sent all over the network  1 , but also keeps looping in the path connecting switches  12 ( 4 ),  12 ( 5 ), and  12 ( 6 ). This results in a packet storm. 
         [0034]    During the storm, the contradictory direction of flow on the sampled packets collected on the segments  14 , when compared by processing entity  10 ,  11 ,  16  with the direction of flow from the saved steady state, results in the processing entity  10 ,  11 ,  16  generating a set of loop pointers  17 . 
         [0035]    After a certain period of time (based upon system parameters such as sampling rate), the loop pointers  17  will trace one or more paths starting from host  10 (A) and leading to the loop. In the  FIG. 4  example, the loop pointers  17  trace two paths that end at the loop: 
         [0000]    PATH 1: Switch  12 ( 1 )→Switch  12 ( 3 )→Switch  12 ( 4 ) (port  16 ( 4 , 1 ))→Switch  12 ( 6 ) (port  16 ( 6 , 1 ))→Switch  12 ( 5 ) (port  16 ( 5 , 2 ))
 
PATH 2: Switch  12 ( 1 )→Switch  12 ( 3 )→Switch  12 ( 4 ) (port  16  ( 4 , 1 ))→Switch  12 ( 5 ) (port  16  ( 5 , 1 ))→Switch  12 ( 6 ) (port  16  ( 6 , 2 ))
 
         [0036]    A characteristic of this invention is that a flow&#39;s loop pointers  17  split when they enter the loop and meet again to complete the loop. So in the above case, the loop pointers  17  in PATH 1 and PATH 2 split at switch  12 ( 4 ) (port  16 ( 4 , 1 )) and join back to complete the loop at switch  12 ( 5 ) (port  16 ( 5 , 2 )) and switch  12 ( 6 ) (port  16 ( 6 , 2 )). Using this information, the processing entity  10 ,  11 ,  16  detects the loop. 
         [0037]    The processing entity  10 ,  11 ,  16 , whether in the centralized or distributed embodiment, is able to autonomously detect the new segment  14  that caused the loop. In the present example, the link  14 ( 5 , 6 ) connecting ports  16 ( 5 , 2 ) and  16 ( 6 , 2 )) is automatically identified as the cause of the loop. The attributes that identify the bad segment  14  are:
       The bad segment  14  sends samples with contradicting direction information for a traffic flow.   The bad segment  14  does not have a steady state.       
 
         [0040]    These two conditions are met only in the case of a new segment  14  which creates a loop, and result in two loop pointers  17  for said new segment  14  that point in opposite directions. These attributes allow the locational cause of the loop to be uniquely identified. 
         [0041]    During a storm, there is a high likelihood of packet loss, and hence reliable transport of sample packets to the collector  11  is needed. This can be accomplished by two methods:
       1. Use of an out-of-band management VLAN (virtual local area network) to send the sampled data to the collector  11 . Since this VLAN is not part of the storm, it should be unaffected. The VLAN monitors the network  1  in the form of a software overlay.   2. Prioritization of the sampled packets based upon information contained in the packet headers. This increases the likelihood of the sampled packets surviving the storm and reaching the collector  11 .       
 
         [0044]    The loss of a few samples will not affect the ability of the algorithm to detect the loop; the only effect will be to delay the detection process. 
         [0045]    In the distributed loop detection embodiment, loop detection is performed at each individual networking node  16  (whether associated with a router or switch  12 ), or by the associated router or switch  12  itself. The elements  16  in this embodiment are thus all contained within the network  1 , and there is no single point of failure. This embodiment requires no external collector  11  or other entity, and implements a network  1  that can self-heal. 
         [0046]    In a preferred distributed embodiment, a process (normally a software module) on or associated with each networking node  16  collects the samples, and extracts the flow and direction information. The process detects events that result in loop pointer  17  creation, as described in conjunction with  FIG. 4 , and communicates with peer processes running on directly connected (peer) nodes  16 . The instant the process detects a contradictory flow, it sends a message to the peer  16 . This loop pointer message contains information regarding the flow that resulted in loop pointer  17  creation. This message is sent only on the link  14  in which the loop pointer  17  was observed. These messages are sent in the direction of the loop pointers  17 . 
         [0047]    Every loop pointer  17  results in a message being sent to the connected peer node  16 . Eventually the message will reach a node  16  that also has a loop pointer  17  in the opposite direction for a particular segment  14 . In  FIG. 4 , this event happens only on port  16 ( 6 , 2 ) and port  16 ( 5 , 2 ). The existence of loop pointer messages in both directions for a segment  14  indicates a complete loop. The steps up to this point constitute a loop detection mechanism. 
         [0048]    For all centralized and distributed embodiments described herein, the processing entity  10 ,  11 ,  16  can remove the network loop in two different ways:
       Link down (break) the newly created link  14  that caused the loop.   Link down on the lowest bandwidth link segment  14  of the loop. This stops the loop, but advantageously keeps the high bandwidth part of the network  1  active. For this purpose, “lowest bandwidth” refers to the bandwidth of the segment  14  without regard to the amount of traffic that is actually carried by this segment  14 .       
 
         [0051]    The processing entity  10 ,  11 ,  16  can differentiate an unwanted network loop from an intentional network reconfiguration, as illustrated in  FIG. 5 . 
         [0052]    When a network  1  is reconfigured by the system administrator, a host  10  connection could be changed to a different switch  12 . Therefore, the host  10  could send traffic in a different direction, which could be the opposite direction in which it sent traffic originally. We don&#39;t want this phenomenon to trigger a false positive declaration of a network loop. 
         [0053]    The processing entity  10 ,  11 ,  16  differentiates between an intentional network reconfiguration and a network loop using the following rules. An intentional network reconfiguration is diagnosed when:
       1. New samples of a flow in the steady-state direction reduce to zero over a preselected period of time, and   2. New samples of a flow in the opposite (to steady-state) direction increase over said preselected period of time.       
 
         [0056]    A network loop is diagnosed when the following contradiction continues:
       1. New samples of a flow in the steady-state direction continue to be recorded at the end of a preselected period of time, and   2. New samples of a flow in the opposite (to steady-state) direction also continue to be recorded at the same point in time as in criterion (1); and   3. Criteria (1) and (2) samples persist as long as the loop exists in the network  1 .       
 
         [0060]    When the above three conditions are met, a network loop is indicated. Using the above described rules, the processing entity  10 ,  11 ,  16  differentiates a network loop from an intentional network reconfiguration.  FIG. 5  illustrates method steps that accomplish this. 
         [0061]    The method steps illustrated in  FIG. 5 , as well as all the other methods illustrated and described in this specification, are performed by one or more modules associated with the processing entity  10 ,  11 ,  16 . The modules are implemented in hardware, software, firmware, or any combination thereof. When the modules are implemented in software, said modules can reside on one or more computer-readable media as a series of computer program instructions. The computer-readable media can be any means for storing computer program instructions, including hard disks, floppy disks, optical disks, CD&#39;s, DVD&#39;s, thumb drives, etc. 
         [0062]    The method of  FIG. 5  begins at step  51 , where the processing entity  10 ,  11 ,  16  receives a sample of a particular flow, which, for purposes of illustration, is called flow X. 
         [0063]    At step  52 , the processing entity  10 ,  11 ,  16  makes a determination as to whether the sample is flowing in the same direction as recorded previously in the steady state. If the answer to this is “yes”, the processing entity  10 ,  11 ,  16 , at step  53 , sets a parameter called Regular_Flow_Received to TRUE. If the answer to the question posed in step  52  is “no”, a parameter called Contradictory_Flow_Received is set to TRUE, and the parameter Regular_Flow_Received is set to FALSE. 
         [0064]    The method then proceeds to step  55 . The processing entity  10 ,  11 ,  16  inquires as to whether the parameter Regular_Flow_Received is TRUE and whether the parameter Contradictory_Flow_Received is also TRUE. If both of these answers are “yes”, signifying the presence of a loop, the method proceeds to step  56 . Otherwise, the method loops back to step  51 . 
         [0065]    At step  56 , the counter Loop_Detect_Count is incremented, Regular_Flow_Received is set to FALSE, Contradictory_Flow_Received is set to FALSE, and the method proceeds to step  57 . 
         [0066]    At step  57 , the processing entity  10 ,  11 ,  16  inquires as to whether the counter Loop_Detect_Count exceeds a preselected threshold. This threshold is set empirically, and is set sufficiently high to minimize false positive determinations of network loops. If the answer to the question raised in step  57  is “yes”, the method proceeds to step  58 , where it is verified that there was, in fact, a network loop. At this point, appropriate self-healing steps can be taken to eliminate the loop. 
         [0067]    If the answer to the question posed in step  57  is “no”, the method circles back to step  51 . 
         [0068]    The above description is included to illustrate the operation of the preferred embodiments, and is not meant to limit the scope of the invention. The scope of the invention is to be limited only by the following claims. From the above discussion, many variations will be apparent to one skilled in the art that would yet be encompassed by the spirit and scope of the present invention.