Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
2000-11-10
2004-12-07
Follansbee, John (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
Reexamination Certificate
active
06829649
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of congestion control in communication networks and more specifically to congestion control of dataflows at Internet gateways.
BACKGROUND
Numerous dataflows may pass through Internet gateways of fixed outgoing bandwidth at any given time. The dataflows may cumulatively require data to be sent at a rate which could be considerably less or more than the available bandwidth, resulting in a fluctuating load at a gateway. Consequently, congestion control is necessary to ensure good bandwidth utilization and low queue occupancy at the gateway. An additional advantage of congestion control is that certain dataflows are protected against bandwidth monopolisation by other more dominant and aggressive dataflows.
Internet traffic may broadly be classified into two categories, namely adaptive and non-adaptive traffic. Adaptive, or responsive, connections have built-in congestion control mechanisms which reduce the flow rate on detection of congestion. Transport layer protocols, like Transport Control Protocol (TCP) are used by adaptive connections to implement a congestion avoidance mechanism. In the Internet, dropped packets are considered an indication and measure of network congestion. Accordingly, TCP senders adjust the rate at which data is sent in accordance with the number of packets dropped in the network.
On the other hand, non-adaptive connections do not implement any congestion control mechanisms. In other words, non-adaptive applications do not attempt to assess congestion in the network and adapt accordingly. While adaptive connections reduce flow rates upon detecting congestion, non-adaptive flows, such as User Datagram Protocol (UDP) and Constant Bit Rate (CBR), do not reduce flow rate and consequently contribute to increased congestion. As a result, adaptive connections are disadvantaged by the more aggressive non-adaptive connections which monopolise more than a fair share of the fixed available bandwidth. This gives rise to heavily congested networks characterised by large numbers of dropped packets and leads to a large proportion of wasted traffic.
Since application sources cannot be relied upon to co-operate in congestion control, mechanisms must be provided to implement congestion control and equitable bandwidth allocation from within the network, preferably by providing an incentive for applications to employ end-to-end congestion control. Such mechanisms can only be employed at the Internet gateways, as it is there that the different flows interact. Furthermore, the mechanisms should be easy to implement at the hardware level as the volume of traffic at gateways is extremely large and the available processing time per packet is extremely limited.
A number of approaches to queue management at gateways have been studied. Providing a gateway keeps a separate queue for each dataflow, Round-Robin Scheduling (RRS) can be used to ensure fair distribution of bandwidth amongst the dataflows. This further provides an incentive for adaptive applications. Another approach is for a gateway to provide Explicit Congestion Notification to sources (ECN). Although such systems ensure improved allocation and utilization of bandwidth, implementation is more difficult as a separate queue for each flow is required to be maintained by the gateway.
Droptail gateways are currently employed almost universally in the Internet. A droptail gateway drops arriving packets when the gateway buffer is full. While simple to implement, this technique tends to arbitrarily distribute losses among the dataflows and also tends to penalize bursty connections.
Early Random Drop (ERD) and Random Early Detection (RED) are methodologies that address some of the drawbacks of droptail gateways. These techniques employ randomization of dropped packets and early detection of congestion, based on buffer usage, to avoid congestion and buffer overflow. Accordingly, these are primarily techniques of congestion avoidance as opposed to congestion control. Whilst these techniques exhibit many advantages over droptail gateways, fair allocation of bandwidth amongst dataflows is still not ensured. Specifically, Random Early Detection (RED) drops packets of a dataflow in proportion to the current occupancy of the queue by that dataflow. This does not always lead to a fair allocation of bandwidth.
To ensure fairer allocation of bandwidth amongst dataflows and to identify and penalize misbehaving sources, some sort of status indication must be maintained for each individual dataflow. Many approaches based on per-flow queuing have been suggested. In Longest Queue Drop (LQD), whenever the buffer is full, a packet from the dataflow with the greatest number of packets in the queue is dropped. Other similar algorithms, such as Approximated Longest Queue Drop (ALQD) and random LQD (RND) have been proposed. However, these algorithms are complex to implement, may cause frequent buffer overflows, and act as congestion control mechanisms rather then congestion avoidance mechanisms.
Yet another approach is that of per-flow accounting whilst maintaining a single queue. Flow Random Early Drop (FRED) incorporates changes to the RED algorithm and attempts to penalize misbehaving dataflows by the use of a ‘strike’ variable. This is achieved by imposing minimum and maximum limits on the number of packets a dataflow can have in the queue. However, through simulation FRED has been shown to fail to ensure fair allocation of bandwidth in many instances. Furthermore, FRED requires a relatively high level of implementation complexity and is not considered to be easily extendible to provide differentiated services.
Thus, a need clearly insists for a method and a system for allocating bandwidth to dataflows that substantially overcomes or at least ameliorates one or more deficiencies of existing arrangements.
SUMMARY
An aspect of the present invention provides a method of allocating bandwidth of a limited bandwidth link to dataflows containing packets. The method includes adaptively adjusting the number of buckets dependent upon the number of active dataflows, where each bucket has a number of allocated tokens for use by a corresponding dataflow. The number of tokens allocated is dependent upon a weighted value for the corresponding dataflow and queuing of packets for utilization of the limited bandwidth link is dependent upon the tokens in the corresponding bucket. Tokens are adaptively reallocated to one or more buckets according to a weighted value for each of the dataflows.
Another aspect of the present invention provides a system for allocating bandwidth of a limited bandwidth link to dataflows containing packets. The system includes means for adaptively adjusting the number of buckets dependent upon the number of active dataflows, where each bucket has a number of allocated tokens for use by a corresponding dataflow. The number of tokens allocated is dependent upon a weighted value for the corresponding dataflow, and queuing of packets for utilization of the limited bandwidth link is dependent upon the tokens in the corresponding bucket. Tokens are adaptively reallocated to one or more buckets according to a weighted value for each of the dataflows.
A further aspect of the present invention provides a computer program product including a computer readable medium with a computer program recorded therein for allocating bandwidth of a limited bandwidth link to dataflows containing packets. The computer product includes program code for adaptively adjusting the number of buckets dependent upon the number of active dataflows, where each bucket has a number of allocated tokens for use by a corresponding dataflow. The number of tokens allocated is dependent upon a weighted value for the corresponding dataflow, and queuing of packets for utilization of the limited bandwidth link is dependent upon the tokens in the a corresponding bucket. Tokens are adaptively reallocated to one or more buckets according to a weighted value for each of the dataflows.
REFERENCES:
patent: 559247
Kamra Abhinav
Kapila Sundeep
Khurana Varun
Saran Huzur
Shorey Rajev
Coca, Esq. T. Rao
Follansbee John
McGinn & Gibb PLLC
Patel Haresh
LandOfFree
Method an congestion control system to allocate bandwidth of... 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 an congestion control system to allocate bandwidth of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method an congestion control system to allocate bandwidth of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326579