Multiplex communications – Communication techniques for information carried in plural... – Adaptive
Reexamination Certificate
1999-05-27
2003-09-02
Kizou, Hassan (Department: 2662)
Multiplex communications
Communication techniques for information carried in plural...
Adaptive
C709S251000
Reexamination Certificate
active
06614805
ABSTRACT:
TECHNICAL FIELD
This invention relates to a media access control mechanism for packet transmission over a buffer insertion ring and, in particular, to an algorithm for ensuring local fairness in transmission resource sharing in a buffer insertion ring.
BACKGROUND OF THE INVENTION
Access control in a buffer insertion ring is designed for asynchronous transmission of variable size packets. A node in a buffer insertion ring can transmit a packet as long as its insertion buffer is empty. A packet arriving from an upstream ring access point (AP) is given non-preemptive priority over frames to be added at a downstream AP on a buffer insertion ring. In other words, ring traffic has preemptive priority over node traffic that is to be transmitted on the ring. If a downstream AP is in the process of adding a packet to the ring when a packet arrives from an upstream AP, then the upstream AP's packet is buffered temporarily. When the end of the added packet is transmitted, it is immediately followed by the buffered packet. The buffer insertion scheme can, however, result in a phenomenon known as a “starvation.” An AP suffers from starvation when an upstream AP transmits continuously and blocks a downstream AP from access to the ring. When this occurs, the downstream AP is said to be “covered” by upstream ring traffic sources. The prevention of starvation in a buffer insertion ring requires a media access fairness mechanism to regulate access to the ring. An optimal solution quickly achieves fairness among traffic sources, and maximizes network throughput while maintaining a minimal ring access delay and contributing minimally to operating overhead.
Several fairness algorithms have been developed for controlling traffic in a buffer insertion ring. One such algorithm is the “SAT” algorithm described by Cidon in an article entitled “MetaRing a full-duplex ring with fairness and spatial reuse”, IEEE Transactions on Communications, Vol. 41, No. 1, January 1993, pp. 110-120. The algorithm regulates access to the ring by use of a control signal called, an SAT that circulates in a direction opposite to the data traffic. Each AP in the ring is assigned a fixed transmit quota. The AP forwards the SAT upstream without delay unless it has been unable to satisfy its quota. The SAT is held by the AP until it has satisfied its quota, after which it will forward the SAT upstream. This algorithm suffers from the drawbacks associated with token control in a ring topology. Namely, the algorithm impacts throughput if a small quota allocation is selected. The algorithm also results in degraded access delay if nodes are granted large quotas. The algorithm likewise causes unnecessary losses of throughput in asymmetrically loaded rings.
Another algorithm referred to as the “FULL” algorithm is described by Saito et al in an article entitled “QOS Guarantees for high-speed variable-length packet LANs” available on the web site: www.sail.t.u-tokyo.ac.jp/pisai/research. The FULL algorithm is an enhancement to the SAT algorithm. The enhancement is enabled by assuming that the ring access logic implements a shortest path forwarding policy. Given such a policy, more than one SAT token is simultaneously applied on each half of the ring. The FULL algorithm provides a marginal improvement of about 10% on the performance of the original SAT algorithm but shares its drawbacks noted above.
Another algorithm developed for access control on buffer insertion rings is the REQ/GNT algorithm described in an article by Chen et al entitled “A local fairness algorithm for Gigabit LANs/MANs with spatial reuse”, IEEE Journal on Selected Areas in Communications, Vol. 11, No. 8, October 1993, pp. 1183-1192. In accordance with the REQ/GNT algorithm, each AP operates in two modes: restricted and non-restricted mode. In restricted mode, a node can transmit only a predefined quota of data units. In non-restricted mode, the AP has free access to the ring yielding non-preemptive priority to the upstream traffic. A starved node triggers the fairness mechanism by sending a request message (REQ) upstream. On receipt of such a message, the upstream AP enters a restricted mode. If an AP that receives the REQ message cannot provide silence because it is receiving traffic from upstream sources, it will in turn forward the REQ message upstream. A node in restricted mode is permitted to add a fix quota of traffic to the ring. Once this quota is achieved, the node must cease transmission. After all upstream APs have transmitted their quota, the starved AP has a transmit opportunity. After the starved AP has transmitted its quota of traffic, it releases the upstream nodes from the restricted state by issuing a GNT message. Upon receiving a GNT message, the upstream AP follows similar rules. The upstream AP will in turn forward a GNT message upon satisfaction of its quota. The REQ/GNT algorithm offers better performance than the SAT and FULL algorithms and achieves more optimal throughput in asymmetrically loaded rings. However, the REQ/GNT algorithm falls short of the optimal throughput for certain traffic patterns and suffers from high head of line ring delay.
Each of the above-described algorithms suffers from shortcomings that are well known and acknowledged by their inventors. Specifically, the algorithms throttle throughput and contribute to head of line delay (HOL). HOL delay is defined as the amount of time a first packet in the add buffer of a node has to wait before it is inserted into the ring. Consequently, bandwidth utilization is not optimally achieved using these algorithms. One contributory factor is that high throughput and short HOL delay are often conflicting objectives.
There therefore exists a need for a fairness algorithm that provides both short HOL delay and high bandwidth utilization. There also exists a need for an algorithm that rapidly converges to a fair rate, is simple to implement, and readily scales with growth in ring topology.
OBJECTS OF THE INVENTION
It is therefore an object of the invention to provide a method of media access control for packet transmission over a buffer insertion ring which overcomes the disadvantages of prior art algorithms.
It is a further object of the invention to provide an adaptive rate control (ARC) algorithm that operates on the basis of rate calculations performed at each node in the ring.
It is a further object of the invention to provide an ARC algorithm that performs rate calculations using information available at each node as well as information received from a downstream link partner node.
It is yet a further object of the invention to provide a media access control algorithm in which each node computes its own local fair add rate as well as a rate which the node deems to be a fair add rate for its upstream link partner.
It is yet a further object of the invention to provide a media access control algorithm for packet transmission over a buffer insertion ring which runs continuously on the ring to regulate each node's access to the ring.
It is yet another object of the invention to provide an algorithm for media access control for packet transmission over a buffer insertion ring which contributes little to the operating overhead of the ring.
SUMMARY OF THE INVENTION
These and other objects of the invention are realized in a method of media access control for packet transmission over a buffer insertion ring, comprising steps performed by each node in the buffer insertion ring of:
computing at regular intervals a local packet add rate and an advertised packet add rate for an upstream link partner node;
communicating the advertised add rate to the upstream link partner node; and
adding packets to the ring at a rate that does not exceed the local packet add rate until a new add rate is computed.
In accordance with a further aspect of the invention, there is provided a method of media access control for packet transmission over a buffer insertion ring in which a packet arriving from an upstream node in the ring is given non-preemptive priority over packets to be added to the ring,
Cottreau Peter Martin Kenneth
Khan Lutful
Raahemi Bijan
Kizou Hassan
Levitan Dmitry
Nortel Networks Limited
Renault Ogilvy
Wood Max R.
LandOfFree
Method and apparatus for media access control for packet... 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 media access control for packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for media access control for packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3063721