Runtime detection of network loops

Details Runtime detection of network loops Runtime detection of network loops

1998-09-24

2001-10-02

Myers, Paul R. (Department: 2181)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

Reexamination Certificate

active

06298456

ABSTRACT:

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.


REFERENCES:
patent: 5034945 (1991-07-01), Kimoto et al.
patent: 5084870 (1992-01-01), Hutchison et al.
patent: 5321812 (1994-06-01), Benedict et al.
patent: 5506838 (1996-04-01), Flanagan
patent: 5511168 (1996-04-01), Perlman et al.
patent: 5535335 (1996-07-01), Cox et al.
patent: 5727157 (1998-03-01), Orr et al.
patent: 5729528 (1998-03-01), Salingre et al.
patent: 5790522 (1998-08-01), Fichou et al.
patent: 5790808 (1998-08-01), Seaman
patent: 5944798 (1999-08-01), McCarty et al.
patent: 5959968 (1999-09-01), Chin et al.
patent: 6021116 (2000-02-01), Chiussi et al.
patent: 6044090 (2000-03-01), Grau et al.

Affiliated with

Also associated with

Rating

Runtime detection of network loops does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Runtime detection of network loops, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Runtime detection of network loops will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2573900