Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1998-12-03
2003-01-07
Olms, Douglas (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
C370S235000, C370S230000, C370S231000, C370S395210, C370S395410
Reexamination Certificate
active
06504818
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to resource management techniques in data networks and, more particularly, to resource management techniques that control network congestion and guarantee fairness to customers.
Data networks are in common use. Conventional networks include frame relay, packet relay and cell relay networks. Typically, such networks receive data from a plurality of data sources and format the data into data “elements,” which may be frames, packets or cells of data depending upon the network type. The data elements are routed through the data network to one or more destinations. A destination is commonly referred to as an “egress port” because by consuming, storing or otherwise disposing of data, data elements exit from the data network. An exemplary data network is disclosed in U.S. Pat. No. 5,335,224, entitled “Service Guarantees/Congestion Control in High Speed Networks;” the entirety of the patent's disclosure is incorporated herein by reference.
Data networks are subject to capacity (“bandwidth”) limitations. Network proprietors typically contract with each source to route a certain amount of data from the source to a destination. Thus, each source is associated with a “contract rate” (CR) of data representing a minimum data rate that the data network should accept from the source. However, each source may be capable of providing data at a much higher rate. Each source also is associated with an “availability rate” (A) representing a rate at which the source may furnish data to the network.
Not all sources are active at the same time. At times the aggregate contracted rates of the active sources may not consume the network's capacity. When this occurs, the data network distributes the excess bandwidth to the active sources. The data network, in effect, accepts more data from one or more sources than it is required to accept. It is an object of data networks to allocate excess bandwidth to the active sources fairly. No known control scheme for data networks provides a fair share queuing scheme in data networks to distribute excess bandwidth to data sources.
Control schemes for data networks are known to allocate excess bandwidth and moderate network congestion. Network congestion occurs when data is developed to a particular egress port at a rate that exceeds the egress port's data capacity. Without such control schemes, the excess data would be lost. Sources would have to retransmit the data once the sources and egress ports determined that data loss occurred. Control schemes may provide for global congestion detection in which an egress port monitors the rate at which it receives data. If a global congestion threshold is exceeded, the egress port generates a feedback control signal to all sources causing the sources to reduce the rate at which they deliver data to the network for delivery to the egress port. Other control schemes provide for local congestion detection, in which the egress port identifies individual sources from which it receives data. If data received from any one source exceeds a local congestion threshold associated with the source, the egress port generates a second type of feedback control signal to the source causing it to reduce the rate at which it generates data for the egress port.
Global congestion detection does not provide for fair share of excess bandwidth. Consider the example illustrated in
FIG. 1
, where three sources route data to a single egress port. The egress rate of the egress port is 128 Kbps. The contracted rates and availability rates of the sources are as follows:
Source
Contracted Rate (CR
i
)
Availability rate (A
i
)
Source 1
8 Kbps
64 Kbps
Source 2
8 Kbps
64 Kbps
Source 3
4 Kbps
128 Kbps
The control signal of the global congestion detection causes the sources to reduce the delivery of data equivalently. If all sources delivered data at the availability rate, the sources would exceed the capacity of the egress port by 128 Kbps.
(
∑
S
1
S
3
A
i
=
256
Kbps
)
.
The egress port would cause the sources to decrease delivery of data in equal amounts until the total amount of data delivered to the egress port matched the egress port's egress rate. Experimental results demonstrate that the actual rate of data delivery from the sources in the above example would be:
Source
Actual Data Rate (ADR
i
)
Ratio of ADR
i
to CR
i
Source 1
21 Kbps
2.625
Source 2
21 Kbps
2.625
Source 3
86 Kbps
21.5
Although source
3
has the lowest CR of any source and caused most of the congestion at the egress port, the data network allocates an overwhelming majority of its excess bandwidth to it. This is unfair.
Local congestion control also fails to allocate excess bandwidth fairly. In this scheme, data elements received by the egress port are segregated by source and entered into local buffers associated with each source. When an amount of data in one of the local buffers becomes too large, the egress port sends a control signal to the associated source causing the source to throttle down. The following example demonstrates how this control scheme is unfair as well.
Consider the three source example of FIG.
1
. In this example, the egress port has an egress data rate of 1536 Kbps. The contracted rates and availability rates of the sources are as follows:
Source
Contracted Rate (CR
i
)
Availability Rate (A
i
)
Source 1
4 Kbps
1536 Kbps
Source 2
4 Kbps
1536 Kbps
Source 3
1024 Kbps
1536 Kbps
Egress ports typically drain data from each local buffer at a rate proportional to the amount of data in the respective local buffer. The drain rate and the size of the local thresholds contribute to the throughput from each source. Although the local thresholds may be set to reflect the contracted rate of the respective source, the contribution of the drain rate causes the throughput to deviate from the contracted rate. Experimental data run on a known local congestion control scheme using the above figures demonstrates that the local congestion control system is unfair. It results in the following throughput:
Source
Actual Data Rate (ADR
i
)
Ratio of ADR
i
to CR
i
Source 1
−
300 Kbps
75
Source 2
−
300 Kbps
75
Source 3
−
800 Kbps
0.78
To meet its contracted rate, the ADR
i
to CR
i
ratio should be at least 1 for each source. Thus, local congestion control causes the network to fail to meet the contracted rate with respect to Source
3
. It is not delivering the data rate that the network is obligated to deliver even though the contracted rate to the egress port is less than the capacity of the egress port. Local congestion control schemes are not fair.
No known control scheme for data networks includes both global congestion control and local congestion control.
Accordingly, there is a need in the art for a data network control scheme that fairly allocates excess bandwidth in the network to active sources. Further, there is a need in the art for such a control scheme that guarantees conformance to data rates that the network is obligated to carry from individual sources.
SUMMARY OF THE INVENTION
The disadvantages of the prior art are alleviated to a great extent by a method of controlling congestion in data networks, wherein when data is buffered at an egress port, it is buffered in a local buffer associated with a source of the element. For each data element received, the egress port determines whether a global threshold is exceeded and, if so, requests all data sources to reduce their rate of data delivery to the egress port. Similarly, the egress port determines whether a local threshold is exceeded and, if so, requests the one source associated with the local buffer to reduce the data delivery rate to the egress port.
Optionally, if the data delivery rate of the one source falls below a predetermined minimum rate, the one source may refuse the request. In response, the egress port requests all other data sources to reduce their rate of data delivery to the egress port.
REFERENCE
AT&T Corp.
Nguyen Van
LandOfFree
Fair share egress queuing scheme for data networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fair share egress queuing scheme for data networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair share egress queuing scheme for data networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3014807