Abstract:
Runtime detection of network loops is performed. It is detected when for a network segment a ratio of duplicate packets to total packets exceeds a first predetermined threshold. Also it is detected when traffic load on the network segment exceeds a second predetermined threshold. When the ratio of duplicate packets to total packets exceeds the first predetermined threshold and the traffic load on the network segment exceeds the second predetermined threshold, a network loop has been detected.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
     This application is a continuation-in-part of application Ser. No. 08/986,077, filed Dec. 5, 1997, by Craig A. VanZante, Robert L. Faulk, Jr. and Douglas E. O&#39;Neil for HUB-EMBEDDED SYSTEM FOR AUTOMATED NETWORK FAULT DETECTION AND ISOLATION. 
    
    
     BACKGROUND 
     The present invention concerns computer networks and pertains particularly to runtime detection of network loops. 
     A local area network (LAN) segment can include repeaters, end stations, and network cabling. For example, the Ethernet protocol operates using a carrier sense, multiple-access with collision detect (CSMACD) protocol by which end stations (e.g., workstations or other computers) first listen for carrier and wait for the network to become idle, then transmit the data, retransmitting the data if collisions are detected. Data is transferred in the form of packets, which contain the address of the sending station (the source address), the address of the intended recipient (the destination address) and a Cyclic Redundancy Check (CRC) of the packet. For more information on the Ethernet protocol, see the standard ISO/IEC 8802-3. 
     For higher bandwidth networks, multiple network segments are often used. These network segments can be interconnected through the use of one or more bridges or switches. The core functionality of switches and bridges are similar and the terms are often used interchangeably. Bridges contain two or more ports, each of which connect to an network segment. When two stations on different network segments communicate with each other, the bridge will forward the packets between the two segments. When the stations are on the same segment, the bridge will not forward the packets to any other segment. 
     Bridges learn on which port each station is connected by examining the source address of packets as the packets are received, and storing this address-port association in a filtering database. Bridges operate by examining the destination address of packets received on a given port, and forwarding the packet out the port on which the destination station is connected. If the destination station is on the port from which the packet was received, the packet is not forwarded (i. e., is filtered). For more information on bridges see the standard ISO/IEC 10038. 
     Network loops can be formed in many ways. For example, when two or more ports on a bridge become connected to the same network segment, a network loop exists. While in this configuration, all packets forwarded by the bridge to any one of its ports on a network segment will be received by all of the other ports that the bridge has on that network segment. The bridge will continue to re-forward and re-receive these packets, the rate and duration of which is bounded only by the limitations of the bridge and the network. Network loops can also be formed, for example, by two repeaters being improperly connected together. Regardless of how a network loop is formed, the result is wasted network bandwidth and wasted bridge resources. 
     The Spanning Tree Algorithm is the current method most often used to protect user networks from network bridge loops. The Spanning Tree Algorithm defines an algorithm and a protocol that network bridges can use to intercommunicate and then adjust their configurations such that a network is spanned, but does not cause network loops. For more information on the Spanning Tree algorithm, see the standard ISO/IEC 10038. 
     The Spanning Tree Algorithm adds additional traffic to the network and can only be implemented on network bridges/switches. Further, to be effective the Spanning Tree algorithm must be implemented in all of the network bridges in the network. This is due to the Spanning Tree algorithm not offering protection against network loops that exist on bridges that do not support the Spanning Tree Algorithm (i.e. many unmanaged bridges/switches). This limitation makes it impractical to incrementally implement the Spanning Tree Algorithm on an existing network that contains bridges that do not already support the Spanning Tree Algorithm. 
     Additionally, when a network administrator makes network connections within a network closet which results in an immediate and heavy increase in network traffic, as indicated by the activity/utilization light emitting diodes (LEDs) for the network, this indicates to the network administrator that potentially a network loop has been formed. 
     BRIEF SUMMARY OF THE INVENTION 
     In accordance with the preferred embodiment of the present invention, runtime detection of network loops is performed. It is detected when for a network segment a ratio of duplicate packets to total packets exceeds a first predetermined threshold. Also it is detected when traffic load on the network segment exceeds a second predetermined threshold. When the ratio of duplicate packets to total packets exceeds the first predetermined threshold and the traffic load on the network segment exceeds the second predetermined threshold, a network loop has been detected. 
     For example, in the preferred embodiment, the ratio of duplicate packets to total packets is detected by acquiring sampled packets from all network packets sent over the network segment. The sampled packets are used to generate packet identification statistics. The ratio of duplicate packets to total packets is calculated using the packet identification statistics. 
     For example, a cyclical redundancy check (CRC) is used to identify packets when generating packet identification statistics. Alternatively, the entire contents of each sampled packet are used to identify packets when generating packet identification statistics. In the preferred embodiment, only error free packets are eligible to be sampled packets. 
     In the preferred embodiment, the first predetermined threshold is equal to one half and the second predetermined threshold is equal to one half bandwidth for the network segment. 
     In alternate embodiments, instead of, or in addition to using a ratio of duplicate packets and traffic load to detect a network loop, other symptoms of network loop may be monitored. For example, broadcast and multicast traffic levels can be used as an indicator that a network loop is present. Also, a high collision rate level can be used as an indicator that a network loop is present. The present invention allows detecting of network loops which facilitates keeping a network operational in the event of a miss-configuration that results in a network loop. Such a miss-configuration resulting in a network loop can be catastrophic and result in significant down time for the network until the network loop can be discovered and ameliorated. 
     The present invention is superior over prior art solutions such as the Spanning Tree Algorithm because the present invention does not add traffic to a network and is thus unobtrusive. Devices that utilize network loop detection in accordance with the present invention can be incrementally implemented across a network, offering increasingly more benefits as more devices with network loop detection are installed. It is not necessary to implement network loop detection in accordance with the present invention on the device that contains the network loop for effectiveness. A device which incorporates network loop detection in accordance with the present invention can protect itself, and any nodes attached to it from a network loop induced on it, or on another device. 
     Also, the start-up delays resulting from the learning mode of the Spanning tree are obviated by the present invention. Further, operation of the present invention is completely transparent to the network administrator/user who does not even need to know that the network loop protection exists. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a simplified example of connections in a network illustrating a network bridge loop. 
     FIG. 2 illustrates the implementation of runtime detection of network loops in accordance with a preferred embodiment of the present invention. 
     FIG.  3  and FIG. 4 illustrate network loops arising from various network connection configurations within a network. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     FIG. 1 shows a bridge  10 . Bridge  10  includes a port  11 , a port  12  and a filtering database  13 . Bridge  10  learns the port on which each station is connected by examining the source address of packets as they are received, and storing this address-port association in filtering database  10 . Bridge  10  operates by examining the destination address of packets received on a given port, and forwarding the packet out the port on which the destination station is connected. If the destination station is on the port from which the packet was received, the packet is not forwarded. 
     A repeater station  15  includes a repeater  16 . Repeater is connected to an intelligent agent  17  within repeater station  15 , an end station  14 , port  11  of bridge  10  and port  12  of bridge  10 . Since two ports of bridge  10  are connected to the same repeater, a network bridge loop exists. While in this configuration, all packets transmitted by bridge  10  on port  11  will be received on port  12  and re-transmitted on port  11 . Likewise, all packets transmitted by bridge  10  on port  12  will be received on port  11  and re-transmitted on port  12 . Bridge  10  will continue to re-receive these packets and to re-transmit these packets. The rate and duration of these transmissions is bounded only by the limitations of bridge  10  and repeater station  15 . The result is wasted network bandwidth, wasted bridge resources, and likely the loss of network usefulness. 
     FIG. 2 illustrates the implementation of runtime detection of network loops such as those illustrated by FIG.  1 . In order to detect loops, the network loop detection illustrated by the flowchart shown in FIG. 2 looks for two symptoms of a network loop. The first symptom is packets that have been transmitted multiple times. Such a high number duplicate packets will occur when there is a network loop. The second symptom is high network traffic load. While these are the two symptoms searched for by the preferred embodiment of the present invention, other symptoms may be searched for as well. For example, other symptoms of a network loop which can be searched for include high broadcast and multicast traffic levels and high collision rates. 
     In order to look for duplicate packets, an acquire sample packets process  21  samples network traffic. As input, sample packets process  21  receives all packets (Network_Traffic) which appears on the network segment. As output, sample packets process  21  produces sampled packets (Sampled_Packets). The algorithm sample packets process  21  performs is to select a portion of error-free packets from the packets (Network_Traffic) transferred over to be used as sample packets (Sampled_Packets). In alternative embodiments of the present invention, packets with errors can still be used as sample packets. 
     The sampled packets (Sampled_Packets) are forwarded to an update packet identification (ID) statistics process  22 . Update packet identification statistics process  22  derives a packet identifier for each sampled packet. In the described preferred embodiment, update packet identification statistics process  22  uses the Cyclic Redundancy Check (CRC) within each sampled packet as the packet ID. Other data from the packet or even the entire packet could also be used as a packet ID. 
     Update packet identification statistics process  22  generates packet identification statistics (Packet_ID_Statistics) for the sampled packets. Table 1 below sets out pseudo-code which implements update packet identification statistics process  22 : 
     
       
         
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
             
             
               
                 Process: 
                 Update packet identification statistics process 22 
               
               
                 Inputs: 
                 Sampled_Packets 
               
               
                 Outputs: 
                 Packet —  ID —  Statistics 
               
             
          
           
               
                 Algorithm: 
               
             
          
           
               
                   
                 FOR each Sampled —  Packet DO 
               
             
          
           
               
                   
                 IF sample —  count is below MAX —  SAMPLES 
               
             
          
           
               
                   
                 increment sample —  count by 1 
               
               
                   
                 SET Packet ID to Packet CRC 
               
               
                   
                 scan Packet —  ID —  Statistics to see if ID has 
               
               
                   
                 already been sampled 
               
               
                   
                 IF not already sampled 
               
             
          
           
               
                   
                 WITH Packet —  ID —  Statistics DO 
               
             
          
           
               
                   
                 insert ID 
               
               
                   
                 set occurrences of ID to 1 
               
             
          
           
               
                   
                  END —  WITH 
               
             
          
           
               
                   
                 END —  IF 
               
               
                   
                 ELSE 
               
             
          
           
               
                   
                 WITH Packet —  ID —  Statistics DO 
               
             
          
           
               
                   
                  increment occurrences of ID 
               
             
          
           
               
                   
                 END - WITH 
               
             
          
           
               
                   
                 END —  ELSE 
               
             
          
           
               
                   
                 END —  IF 
               
             
          
           
               
                   
                 END —  FOR 
               
               
                   
                   
               
             
          
         
       
     
     Update packet identification statistics process  22  passes packet identification statistics (Packet_ID_Statistics) to a duplicated packet analysis process  23 . Duplicated packet analysis process  23  analyzes the packet identification statistics to see if there exists a reasonable expectation that a significant number of packets have been sampled more than once. If so, duplicated packet analysis process  23  sends notification (High_Duplicate_Packet_Ratio) to a top level loop detect process  25 . Table 2 below sets out pseudo-code which implements duplicated packet analysis process  23 : 
     
       
         
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
             
             
               
                 Process: 
                 Duplicated packet analysis process 23 
               
               
                 Inputs: 
                 Packet_ID Statistics 
               
               
                 Outputs: 
                 High —  Duplicate —  Packet —  Ratio 
               
             
          
           
               
                 Algorithm: 
               
             
          
           
               
                   
                 IF not collected enough samples to be valid 
               
             
          
           
               
                   
                 SET High —  Duplicate —  Packet —  Ratio to FALSE 
               
             
          
           
               
                   
                 END —  IF 
               
               
                   
                 ELSE 
               
             
          
           
               
                   
                 set num —  duplicates to 0 (zero) 
               
               
                   
                 FOR each Packet ID in Packet —  ID —  Statistics DO 
               
             
          
           
               
                   
                 IF occurrences of ID is greater than 1 
               
             
          
           
               
                   
                 increment num —  duplicates by number of 
               
               
                   
                 occurrences of ID 
               
             
          
           
               
                   
                 END —  IF 
               
             
          
           
               
                   
                 END —  FOR 
               
             
          
           
               
                   
                 END —  ELSE 
               
               
                   
                 IF num —  duplicates is greater than 1/2 of sample —  count 
               
             
          
           
               
                   
                  SET High —  Duplicate —  Packet —  Ratio to TRUE 
               
             
          
           
               
                   
                 ENDIF 
               
               
                   
                 ELSE 
               
             
          
           
               
                   
                 SET High —  Duplicate —  Packet —  Ratio to FALSE 
               
             
          
           
               
                   
                  END —  ELSE 
               
               
                   
                   
               
             
          
         
       
     
     A traffic load analysis process  24  looks for high network traffic loads. To do so, traffic load analysis process  24  reads, on a periodic basis, segment counters (Network_Octet_Counter) that measure the number of octets (bytes) that have been transmitted on a network segment. From the count in the network counters traffic load analysis process  24  derives a measure of traffic load (traffic_rate). When traffic load on the network segment is above a pre-determined threshold, traffic load analysis process  24  forwards a high traffic indication (High_Traffic_Load) to top level loop detect process  25 . 
     Table 3 below sets out pseudo-code which implements traffic load analysis process  24 : 
     
       
         
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                 TABLE 3 
               
               
                   
               
             
             
               
                 Process: 
                 Traffic load analysis process 24 
               
               
                 Inputs: 
                 Network_Octet_Counter 
               
               
                   
                 System_Time 
               
               
                 Outputs: 
                 High —  Traffic —  Load 
               
             
          
           
               
                 Algorithm: 
               
             
          
           
               
                   
                 SET delta —  octets to 
               
             
          
           
               
                   
                 Network —  Octet —  Counter - Prev —  NetworkOctetCounter 
               
             
          
           
               
                   
                 SET Prev —  NetworkOctetCounter to Network —  Octet —  Counter 
               
               
                   
                 SET delta —  time to System —  Time - Prev —  System —  Time 
               
               
                   
                 SET Prev —  System —  Time to System - Time 
               
               
                   
                 SET traffic —  rate to delta —  octets / delta —  time 
               
               
                   
                 IF traffic —  rate is greater than 50% of network bandwidth 
               
             
          
           
               
                   
                 SET High —  Traffic —  Load to TRUE 
               
             
          
           
               
                   
                 END —  IF 
               
               
                   
                 ELSE 
               
             
          
           
               
                   
                 SET High —  Traffic —  Load to FALSE 
               
             
          
           
               
                   
                 END —  ELSE 
               
               
                   
                   
               
             
          
         
       
     
     Top level loop detect process  25  will declare (Loop_Detected=TRUE) that a network loop exists whenever a network segment has a significant number of duplicate packets and is also experiencing high traffic loads. When network loop detection is implemented on bridge  10 , and in the event that a network loop does exist, and the network loop exists on bridge  10 , bridge  10  can reconfigure itself to eliminate the network loop. If the network loop exists on some other device, bridge  10  can disconnect itself from the offending device to protect itself and any other devices connected to bridge  10  from the effects of the network loop. Network loop detection can also be implemented on repeater station  15  to protect repeater station  15  and any other devices connected to repeater station  15  from the effects of a network loop. 
     Table 4 below sets out pseudo-code which implements top level loop detect process  25 : 
     
       
         
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                 TABLE 4 
               
               
                   
               
             
             
               
                 Process: 
                 Top level loop detect process 25 
               
               
                 Inputs: 
                 High —  Traffic —  Load 
               
               
                   
                 High —  Duplicate —  Packet —  Ratio 
               
               
                 Outputs: 
                 Loop —  Detected 
               
             
          
           
               
                 Algorithm: 
               
             
          
           
               
                   
                 IF High —  Traffic —  Load is TRUE and 
               
               
                   
                 High —  Duplicate —  Packet —  Ratio is 
               
             
          
           
               
                   
                 TRUE 
               
               
                   
                 SET Loop —  Detected to TRUE 
               
             
          
           
               
                   
                 ENDIF 
               
               
                   
                 ELSE 
               
             
          
           
               
                   
                 SET Loop —  Detected to False 
               
             
          
           
               
                   
                 END —  ELSE 
               
               
                   
                   
               
             
          
         
       
     
     In an alternative embodiment, a Loop_Detect_Procedure and a Duplicate_Detect_Procedure monitors network traffic and the ratio of duplicate packets to detect network loops. Pseudo code for this embodiment is set out in Table 5 below. 
     
       
         
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
               
               
             
               
             
               
               
             
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
               
               
             
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                  TABLE 5 
               
               
                   
               
             
             
               
                 Loop_Detect —  Procedure: 
               
               
                 While forever Do 
               
             
          
           
               
                   
                 For all segments being analyzed 
               
             
          
           
               
                   
                 If transmitted octets on this segment in the last 
               
             
          
           
               
                   
                 second is greater than programmable 
               
               
                   
                 threshold (70-100%) 
               
             
          
           
               
                   
                 Call Duplicate —  Detect —  Procedure 
               
               
                   
                 If High —  Duplicate —  Packet —  Ratio 
               
             
          
           
               
                   
                 Declare loop 
               
             
          
           
               
                   
                 End —  While 
               
               
                   
                 Duplicate —  Detect —  Procedure: 
               
             
          
           
               
                 Inputs: 
                 Segment 
               
               
                 Outputs: 
                 High —  Duplicate —  Packet —  Ratio 
               
             
          
           
               
                 //***Note:  This example is configured for 10 megabit ***// 
               
               
                 Set Max —  Run —  Time to 8 sec. 
               
               
                 Set Min —  Loop —  Rate to 812 Packets/sec 
               
               
                 Set Max —  Packets —  To —  Analyze to 16384 
               
               
                 Set Max —  IDs —  To —  Track —  In —  Data —  Base to 128 
               
               
                 Set Min —  Certainty —  Ratio —  To —  Declare —  Duplicates To ⅛ 
               
               
                 Set Min —  Analyzed —  Packets —  To —  Form —  A —  Conclusion to 
               
             
          
           
               
                   
                  (Max —  Run —  Time * Min —  Loop —  Rate)/2 
               
             
          
           
               
                 Clear all packet statistics in Data Base 
               
               
                 //*** Collect consecutive packets from the network***// 
               
             
          
           
               
                 While 
                 Run —  Time is less than Max —  Run —  Time and 
               
               
                   
                 Number —  of —   Analyzed —  Packets is less than 
               
             
          
           
               
                   
                 Max —  Packets —  To —  Analyze 
               
             
          
           
               
                 Do 
               
             
          
           
               
                   
                 Collect the next packet from the segment to be analyzed 
               
               
                   
                 Increment Number —  of —  Analyzed —  Packets 
               
               
                   
                 Set Packet —  ID to the packets CRC 
               
               
                   
                 If Packet —  ID is already in Data —  Base 
               
             
          
           
               
                   
                 Increment the occurrences for this Packet —  ID in the 
               
             
          
           
               
                   
                 Data —  Base 
               
             
          
           
               
                   
                 Else —  If Number —  Of —  IDs —  In —  Data —  Base is less than 
               
             
          
           
               
                   
                 Max —  IDs —  To —  Track —  In —  Data —  Base 
               
             
          
           
               
                   
                 Store Packet ID in Data —  Base and set its number of 
               
             
          
           
               
                   
                 occurrences to 1 
               
             
          
           
               
                 End While 
               
               
                 //*** Analyze duplicate data ***// 
               
               
                 If Number —  of —  Analyzed —  Packets is less than 
               
             
          
           
               
                   
                 Min —  Analyzed —  Packets —  To —  Form —  A —  Conclusion 
               
             
          
           
               
                   
                 Set High —  Duplicate —  Packet —  Ratio to FALSE 
               
             
          
           
               
                 Else 
               
             
          
           
               
                   
                 Set Number —  Of —  Duplicate —  Packets —  Seen to 0 
               
               
                   
                 Set Number —  Of —  Duplicate —  IDs —  In —  Data —  Base to 0 
               
               
                   
                 For each Packet —  ID in Data —  Base 
               
             
          
           
               
                   
                 If Occurrences of Packet —  ID is greater than 1 
               
             
          
           
               
                   
                 Add Occurrences of Packet —  ID to 
               
             
          
           
               
                   
                 Number —  Of —  Duplicate —  Packets —  Seen 
               
             
          
           
               
                   
                 Increment 
               
             
          
           
               
                   
                 Number —  Of —  Duplicate —  IDs —  In —  Data —  Base 
               
             
          
           
               
                   
                 End —  For 
               
               
                   
                 Set Packet —  Based —  Certainty to the ratio of 
               
             
          
           
               
                   
                 Number —  Of —  Duplicate —  Packets —  Seen to 
               
               
                   
                 Number —  of —  Analyzed —  Packets 
               
             
          
           
               
                   
                 Set ID —  Based —  Certainty to the ratio of 
               
             
          
           
               
                   
                 Number —  Of —  Duplicate —  IDs —  In —  Data —  Base to 
               
               
                   
                 Number —  Of —  IDs —  In —  Data —  Base 
               
             
          
           
               
                   
                 If Packet —  Based —  Certainty + ID —  Based —  Certainty is 
               
             
          
           
               
                   
                 greater than or equal to 
               
               
                   
                 Min —  Certainty —  Ratio —  To —  Declare —  Duplicates 
               
             
          
           
               
                   
                 Set High —  Duplicate —  Packet —  Ratio to TRUE 
               
             
          
           
               
                   
                 Else 
               
             
          
           
               
                   
                 Set High —  Duplicate —  Packet —  Ratio to FALSE 
               
               
                   
                   
               
             
          
         
       
     
     Network configurations can be very complex as hundreds of devices can be connected together in a network using a single network closet. Network loops can arise from a variety of different types of network connections. 
     For example, a network loop can arise when two ports of a network bridge are connected together through one or more repeaters. This is illustrated, for example, by FIG. 3 which shows a port  31  of a bridge  30  being connected in a network loop with a port  32  through a repeater station  33  and a repeater station  34 . 
     A network loop can also arise when two ports of a network bridge are connected together even when no repeater stations are included in the network loop. This is illustrated, for example, by FIG. 4 which shows a port  42  of a bridge  40  being directly connected with a port  43  of bridge  40  to form a network loop. A repeater station  44 , connected to a port  41  of bridge  40 , is not part of the network loop. Connected to repeater station  44  are an end station  45 , an end station  46 , an end station  47  and an end station  48 . In accordance with the preferred embodiment of the present invention, repeater station  44  can detect the network loop caused by port  42  and port  43  of bridge  40  being connected together. Upon detection of the network loop, repeater station  44  can isolate itself from the loop by shutting off a port  49 . By isolating itself from the network loop, repeater station  44  also isolates end stations  45  through  48  from the network loop. 
     The foregoing discussion discloses and describes merely exemplary methods and embodiments of the present invention. As will be understood by those familiar with the art, the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. For example, bridge  10  and repeater station  15  can operate with networks other than local area networks which operate in accordance with the Ethernet protocol. For example, in alternate embodiments of the present invention, the loop occurs in a network that operates in accordance with the FDDI protocol or any other network protocol set out in the IEEE 802 family of networking standards (e.g., 802.3, 802.5, etc.). Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.