Method and apparatus for indicating congestion in a source routed network

Abstract

A packet header in a source routed network is augmented to include, with each hop identifier, at least one bit for indicating congestion at the particular hop. As the packet traverses from the source to the destination, when congestion is detected at a hop, a congestion bit associated with the hop is set in the header. At the destination, when another packet is forwarded from the destination to the source on the same path, the congestion bits are reflected back to the source. When the source receives the congestion bits, it has the option of re-routing subsequent communications between the source and destination nodes by generating a new hop list, which routes around one or more of the congested hops.

Description

RELATED APPLICATIONS[0001]This application is a continuation of co-pending U.S. patent application Ser. No. 10 / 827,181, entitled “Method and Apparatus for Indicating Congestion in a Source Routed Network,” which was filed on Apr. 19, 2004, and which is hereby incorporated herein by reference in its entirety.FIELD OF THE INVENTION[0002]This invention relates generally to the field of networking and more specifically to a method and apparatus for congestion detection and management in a source routed network.BACKGROUND OF THE INVENTION[0003]In a network communications system, generally a packet forwarded from a source node traverses numerous intermediate nodes before the desired destination node is reached. Along the way, the packet may be delayed by congestion at various ones of the intermediate nodes. Various mechanisms exist for signaling the source node that the packet is being delayed on its path to the destination. For example, in a frame relay network, FECN (forward explicit co...

AI Technical Summary

Benefits of technology

"The invention relates to a network system called a source routed network, which allows for congestion detection and avoidance. The invention includes adding congestion bits to the header of each packet transmitted between a source and a destination. These bits indicate the level of congestion at each link or node in the network. The congestion bits can be set when congestion is detected at a particular node, and the source can re-route the communication to avoid the congested node. The invention also includes a method for generating a list of hops to traverse in the network, based on the state of congestion at each link. Overall, the invention improves network efficiency and reduces delays in data transmission."

Problems solved by technology

Likewise, if the destination generates frequent BECN bits, it means the available network bandwidth (at that time) is not as great as can be supported by the source.

In either case, the root cause is lack of available bandwidth at the times during which FECN or BECN bits are generated.

This can occur because of outdated or inadequate network infrastructure, heavy network traffic through at least a portion of the path, high levels of line noise, or portions of the system going down.

However, while the FECN and BECN bits may be used to identify that congestion exists in a path, they do little to indicate exactly where in the path the congestion is occurring.

For example, an overloaded intermediate node in the path has the effect of delaying communication over the entire path, thus causing the FECN / BECN bits to be set to regulate delays and packet loss.

Backing off on the transmission bandwidth may reduce congestion at the one overloaded node, but it does not fully utilize the capacity of the remaining nodes in the path.

Images