Multiplex communications – Communication techniques for information carried in plural... – Adaptive
Reexamination Certificate
1998-03-06
2001-11-06
Chin, Wellington (Department: 2664)
Multiplex communications
Communication techniques for information carried in plural...
Adaptive
C370S404000, C370S358000
Reexamination Certificate
active
06314110
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to methods and apparatuses for allocating bandwidth to nodes in a bi-directional ring network. More specifically, the invention relates to a method and apparatus for implementing spatial and local reuse as well as fairness in a bi-directional ring network which may extend over a large distance even when a significant communication time delay may exist between nodes of the network.
DESCRIPTION OF THE RELATED ART
In the past, multi-node communication systems, such as local area networks, have implemented ring topologies that require some type of management scheme for managing node access to the ring. Ring networks such as FDDI networks or Token Ring networks use a single token circulating around the ring to grant access to the ring medium by the various nodes on the ring. This allows orderly access to the medium; however, the use of one token means that only one node may transmit onto the ring at any given time and requires methods for ensuring the presence of one and only one token on the ring.
In an extended high speed ring, if only one packet is being transmitted on the ring, portions of the ring will be idle. In order for the full bandwidth of the ring to be utilized, it is desirable that any node access management scheme implemented on the ring allow for both spatial and local reuse. Ring networks such as FDDI and Token Ring which use a single token to grant access to the ring medium provide for orderly access to the ring do not allow either spatial reuse or local reuse, although in some cases, it is possible to have spatial reuse by allowing the circulation of multiple tokens. Also, the reconfiguration required when nodes are inserted or removed from the ring will cause the entire ring to stop operation until the presence of exactly one token on the ring is assured.
Spatial reuse means that nodes in sections of the ring on which packets are being forwarded may also transmit their own packets onto the ring while they are forwarding packets so long as there is sufficient bandwidth. Local reuse means that nodes in a local section of the ring where there is not congestion may use the ring for local traffic even though congestion may exist in another section of the ring.
FIG. 1
is a block diagram illustrating a ring
100
with six nodes for the purpose of demonstrating spatial and local reuse. Ring
100
includes nodes
101
,
102
,
103
,
104
,
105
, and
106
. Links
111
,
112
,
113
,
114
,
115
, and
116
connect the various nodes.
If, when packets are being transmitted from node
101
to node
104
node
105
can also simultaneously transmit packets to node
106
, then the ring allows spatial reuse. Different parts of the ring “space” are used simultaneously. Once spatial reuse in a ring is allowed, the amount of throughput available to the nodes will vary depending on the traffic patterns. If node
101
sends to node
102
, and node
103
sends to node
104
, the total throughput would be twice the basic bandwidth of the links. If node
101
sends to node
104
, then node
102
sends to node
103
, the total throughput available is only the basic bandwidth of the link
112
. There is congestion at this link, with potential “starvation” of node
102
.
Resolving the contention for this resource is the object of ring quota schemes. Such schemes generally limit the transmission from node
101
so that node
102
has some bandwidth available on link
112
left for its traffic after forwarding the traffic from node
101
. Typically, a ring quota scheme would limit the transmission from “upstream” nodes to one half the basic bandwidth. Local reuse would allow node
106
in this situation to send to node
101
at the full link bandwidth in spite of the one half constraint elsewhere in the ring.
Various quota schemes for managing node access to a ring network have been developed which allow for spatial and local reuse of the ring. One such scheme is described in U.S. Pat. No. 5,467,352, issued to Cidon, et al. on Nov. 14, 1995. “METHOD AND APPARATUS FOR IMPROVED THROUGHPUT IN A MULTI-NODE COMMUNICATION SYSTEM WITH A SHARED RESOURCE” (hereinafter the '352 patent), which is incorporated herein by reference for all purposes. The '352 patent describes a quota allocation system which allocates to each node a certain quota of bandwidth which that node is allowed to use for transmitting information onto the ring. Since each node may transmit packets up to its quota at any given time, nodes may simultaneously put packets on the ring and therefore spatial reuse is achieved.
In addition, a scheme for allowing a non-quota traffic on the network is disclosed. Nodes which are “satisfied”, that is, nodes that have either no quota remaining to transmit packets or no more packets to transmit notify other nodes of the fact that they are “satisfied.” Other nodes are allowed to send non-quota traffic through the “satisfied” nodes. This scheme provides some flexibility since there is both quota and non-quota access to the ring network. Non-quota access frees up bandwidth on the ring that is assigned to a node as part of its quota but which is not being used by the node.
Although the quota scheme with additional non-quota access enables some spatial and local reuse of the ring, such a scheme does not optimally allocate all of the ring bandwidth to nodes that wish to transmit as quickly as is desired in some cases. Specifically, in a very large network where signals take a long time to travel between nodes, the performance of such a scheme may not be satisfactory because nodes would have to wait for signals to circulate entirely around the ring. Sometimes twice that time would be required for the bandwidth request to circulate and that bandwidth grant to be returned. Furthermore, it would be desirable if the quota assigned to each node that wishes to transmit could be determined based on the amount of traffic on the network at the time when the various nodes need to transmit instead of on an a priori basis in the form of a preassigned quota. What is needed is a bandwidth allocation scheme that would allow spatial and local reuse of the ring media and that would more quickly and flexibly allocate the ring bandwidth among nodes that wish to transmit so that bandwidth is not wasted.
In addition, it is important in many networks that preference be given to high priority traffic such as audio traffic which requires a certain amount of consistently available bandwidth so that an audio or video transmission is able to continuously stream between nodes without interruption. Therefore, what is also needed is a bandwidth allocation scheme that can insure that a certain amount of bandwidth is reserved for high priority communication between network nodes. Finally, it would be desirable if the distributed bandwidth allocation scheme could use a minimal amount of processing overhead in making the calculations necessary to determine how much bandwidth each node should be allocated and a minimal amount of network bandwidth to send any required control messages on the ring network.
SUMMARY OF THE INVENTION
Accordingly, a bandwidth allocation scheme is disclosed that allows the bandwidth of the ring to be statistically multiplexed among the nodes on the ring. No a priori bandwidth allocation scheme is necessary, since each node senses the amount of traffic that it is forwarding, reports to other nodes the amount of bandwidth that it is receiving when necessary, and adjusts its own bandwidth based on received reports from other nodes. In addition, no ring master needs to be designated or negotiated. The bandwidth allocation on the ring is therefore adapted to the distribution of traffic that is on the ring at any given time. This adaptability is described as statistical multiplexing.
A management scheme is provided for allowing nodes on a bi-directional ring network to access the ring network in a fair manner without an a priori assignment of a quota to each node. Each node determines independently how much of the ring bandwidth it should us
Bates Anthony J.
Broberg Robert M.
Chin Hon Wah
Tsiang David J.
Wilford Bruce A.
Chin Wellington
Cisco Technology Inc.
Pham Brenda
Van Pelt & Yi LLP
LandOfFree
Method and apparatus for distributed bandwidth allocation... 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 distributed bandwidth allocation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for distributed bandwidth allocation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2580663