Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1999-07-01
2003-11-18
Cangialosi, Salvatore (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
C370S235000
Reexamination Certificate
active
06650618
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the management of communications between nodes in a network, and more particularly to schemes for managing data flow between nodes in a bi-directional ring network.
BACKGROUND OF THE INVENTION
Congestion occurs in a network when the bandwidth requirements of the nodes exceed the bandwidth of the network. Fairness schemes may be used to allocate bandwidth among the nodes in the network.
Global fairness schemes, such as those applied in token ring networks, consider the entire ring network regardless of where congestion may be occurring in the network. Global fairness schemes are inefficient in terms of bandwidth utilization as they do not apply spacial reuse. Spacial reuse is achieved when destination nodes remove their packets from network. This provides a doubling effect of the available ring bandwidth. By contrast, local fairness schemes augment spacial reuse and manage congestion more effectively.
Local fairness schemes isolate a congested section or span of the ring network and are thus more efficient. By considering only a span in a ring network, the problem of allocating bandwidth among nodes in the network is reduced to a linear model. Local fairness schemes are thus equally applicable to linear networks. A linear network will be considered herein as a type of ring network, i.e., a special case of a ring network which may be termed a broken ring network.
Local fairness schemes may involve the allocation of quotas to allow nodes limited access to the ring network and to give priority to ring traffic at any given node over its own transmissions. Access to the ring by each node may be regulated by circulating a control message around the ring. The message indicates to each node the maximum number of packets that it may transmit during the interval from the reception of one control message to the forwarding of a subsequent control message. In a sustained congested state, a quota scheme requires a fairness decision to be made and executed for each round of quota. Such schemes are associated with delay and jitter.
Local fairness schemes may apply algorithms that periodically modify and advertise target rates to upstream nodes based on the tandem rate or data flow through the node. Target rates are advertised regardless of whether congestion actually exists in the network. Such schemes generally do not scale effectively due to oscillation in the scheme. Such local rate control algorithms are limited to networks below a certain size. Adaptive rate control mechanisms gather data based on statistics, and quickly adapt to changes in the collected data. Inaccuracy in the data will causes misbehaviour in the fairness algorithm, thus limiting its scalability.
Thus, there is a need for a local fairness scheme for managing data flow between nodes in a bi-directional ring network having superior performance that utilizes bandwidth more effectively.
SUMMARY OF THE INVENTION
The present invention is directed to a scheme for managing data flow between nodes in a bi-directional ring network.
According to one aspect of the present invention, there is provided a method for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the method comprising the steps of: identifying the node as being part of a congested span; adjusting the output bandwidth of the node as a function of the congestion in the span.
According to a further aspect of the present invention, there is provided a method for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the method comprising the steps of: receiving at the node a DS rate from a downstream node in a congested span of which the node is a part; determining whether the downstream link of the node is congested; adjusting the output bandwidth of the node as a function of the DS rate and the congestion in the downstream link; adjusting the output bandwidth of one or more upstream nodes contributing to congestion in the downstream link as a function of the DS rate and the congestion in the downstream link.
According to a further aspect of the present invention, there is provided a method for managing the access of nodes to a bi-directional ring network, the method comprising the steps of: identifying a congested span comprising a head node having a congested downstream link, and a plurality of chain nodes contributing to the congestion in the downstream link; adjusting the output bandwidth of the head node as a function of the congestion in the downstream link; adjusting the output bandwidth of the chain nodes as a function of the congestion in the downstream link.
According to a further aspect of the present invention, there is provided an apparatus for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the apparatus comprising: means for identifying a congested span comprising a plurality of nodes: means for adjusting the output bandwidth of the nodes in the congested span as a function of the congestion in the span.
According to a further aspect of the present invention, there is provided computer executable software code stored on a computer readable medium, the code for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the code comprising: code to identify the node as being part of a congested span; code to adjust the output bandwidth of the node as a function of the congestion in the span.
According to a further aspect of the present invention, there is provided a programmed computer for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, comprising: a memory having at least one region for storing computer executable program code; and a processor for executing the program code stored in the memory: wherein the program code includes: code to identify the node as being part of a congested span; code to adjust the output bandwidth of the node as a function of the congestion in the span.
According to a further aspect of the present invention, there is provided a computer readable medium having computer executable software code stored thereon, the code for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, comprising: code identify the node as being part of a congested span; code to adjust the output bandwidth of the node as a function of the congestion in the span.
According to a further aspect of the present invention, there is provided a computer data signal embodied in a carrier wave comprising, for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth: identify the node as being part of a congested span; code to adjust the output bandwidth of the node as a function of the congestion in the span.
According to a further aspect of the present invention, there is provided an apparatus managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the apparatus comprising: an identifier to identify the node as being part of a congested span; and adjuster to adjust the output bandwidth of the node as a function of the congestion in the span.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.
REFERENCES:
patent: 4926418 (1990-05-01), Cidon et al.
patent: 5179548 (1993-01-01), Sandesara
patent: 5297137 (1994-03-01), Ofek et al.
patent: 5477530 (1995-12-01), Ahmadi et al.
patent: 5748900 (1998-05-01), Scott et al.
patent: 6285679 (2001-09-01), Dally et al.
patent: 6314110 (2001-11-01), Chin et al.
patent: 6389015 (2002-05-01), Huang et al.
Improved Fairness Algorithms fo
Lee Yang Sup
Peng Wang-Hsin
Cangialosi Salvatore
Nortel Networks Limited
LandOfFree
Method and apparatus for managing communications between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for managing communications between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for managing communications between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3157873