Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-12-06
2004-02-10
Marcelo, Melvin (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S412000
Reexamination Certificate
active
06690645
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to congestion control in a network and more particularly to Active Queue Management based on desired queue occupancy.
2. Description of Related Art
With the proliferation of internet and data communications, communication networks are being used to carry an increasing amount of traffic. At the same time, user expectations for network speed and reliability are also increasing.
In a packet network such as the Internet for example, packets of information are conveyed between a packet source and a packet sink. The source may be any device that transmits data on the network and the sink may be any device that receives data from a network. Typically, a sink will send an acknowledgement signal to a source of a packet to indicate that a packet has been received.
Between a source and a sink, data packets pass through intermediate elements on the network, for example routers, switches and gateways, which receive and queue data packets for transmission on one or more communications channels. To avoid overloading any given channel, packet transmission on each channel must be managed and controlled.
One technique for managing traffic on a network is to control transmissions from the sources. Typically, a source will have a packet queue and the rate at which packets are transmitted from the packet queue is determined by a sliding window operating on the packet queue, which prevents the source from transmitting a new packet onto the network whenever more than a specified number of transmitted packets remain unacknowledged by the corresponding sink. Each time a transmitted packet is acknowledged by the sink, the window advances, permitting the source to transmit a new packet onto the network. The size of the window may be varied by the source, depending on the capacity of the channel and the ability of the sink to accept packets. These two factors are measured by receiving acknowledgements at the source. Generally if acknowledgements are received, the rate of transmission is increased by increasing the size of the window and if acknowledgements are not received or duplicate acknowledgements are received, i.e. packet loss is occurring, then the rate of transmission is decreased by decreasing the size of the window. Hence, there exists a relationship in which packet loss causes a packet source to reduce its transmission rate, which in turn reduces network congestion.
Effectively, the rate at which a source provides packets to the network is dependent upon receiving acknowledgements. An important consequence of this relationship is that an intermediate network element can intentionally discard or drop packets to prevent them from reaching the sink, thereby eliminating any acknowledgement back to the source, resulting in the source failing to receive an acknowledgement, in which case it reduces its window size and packet transmission rate. In this manner, an intermediate network element can change packet transmission rates of any source from which it receives packets.
This intentional discarding or dropping of packets is referred to as active queue management. Using this technique, the intermediate element responds to increasing traffic by selectively dropping packets from a queue of the intermediate element well before the queue overflows, causing the sources of the dropped packets to reduce their transmission rates to ease queue congestion.
One form of active queue management is Random Early Detection (RED). A RED queue manager maintains a weighted average of the queue length and detects when the average queue length increases beyond a threshold. In response, it causes randomly selected packets to be dropped from the queue. The act of dropping randomly selected packets from the queue is spaced out in time to cause only some sources to decrease transmission rate while other sources continue to send packets at their previous rates.
The probability that a packet arriving at the queue is dropped depends on, among other things, the average queue length, the time elapsed since the last packet was dropped, and a maximum drop probability parameter. However, the weighting that each of these factors has on the probability of being dropped depends on network conditions including the number of active source-sink pairs (“connections”), for example. Consequently the probability that a packet will be dropped changes as network conditions change, resulting in a less than optimal packet drop probability over a wide range of network conditions.
Thus, there is a need for a queue management technique that can make optimum use of a queue by randomly discarding packets with an optimal drop probability that reflects network conditions to better utilize the queue. Additionally, it would be desirable for the technique to make optimum use of the queue without the need to estimate a number of active network connections to the queue and without collecting or analyzing state information on individual connections.
SUMMARY OF THE INVENTION
The present invention addresses the above needs by providing an apparatus and method for controlling a rate at which packets are transmitted to a network element having a queue, involving generating a probability value in response to queue occupancy and desired queue occupancy and controlling the packet in response to the probability value and a reference value to cause a source of the packet to change its transmission rate. Advantageously, this arrangement can be applied over a wide range of load levels and, network conditions and stabilizes queue occupancy at a level independent of the number of active network connections.
Generating the probability value preferably includes generating a current error value in response to the queue occupancy and the desired queue occupancy. In particular, the current error value may be time-filtered to produce a filtered current error value. Such filtering might be accomplished through producing a weighted sum of present and past current error values. This arrangement is desirable because data transmissions generally include uneven bursts of data and as a result, the amount of data stored in a queue may fluctuate significantly. The filtered current error value may further be weighted as a function of a pre-defined control gain factor and queue capacity and the probability value may be calculated as a function of the filtered current error value and a previous probability value.
In one embodiment, the reference value may be a random number generated by a random number generator.
In one embodiment a controller controls admission of the packet into the queue in response to the probability value and the reference value. More particularly, the probability value is compared to the reference value, and if the probability value is greater than or equal to the reference value then the packet is discarded, otherwise the packet is admitted into the queue.
In a variation of the above embodiment, an inter-drop/mark value, representing a number of packets to be accepted into the queue between dropped or marked packets, is generated as a function of the drop probability value and admission of a packet to the queue or marking of a packet is controlled in response to the inter-drop/mark value. In particular, the inter-drop/mark value may be generated as the floor of the reciprocal of the probability value. Use of the inter-drop/mark value to admit or reject packets permits a specific probability, for example 25%, to be achieved by regularly dropping packets or marking packets, for example every fourth packet arriving at the queue. In such an embodiment, the reference value used by the controller may be generated by producing a representation of a count of packets arriving at the queue. The admission of a packet into the queue or marking of a packet may be controlled in response to the probability value in the form of an inter-drop/mark value and the reference value in the form of a count. More particularly, the inter-drop/mark value may be compared to the reference value, and if the inte
Aweya James
Montuno Delfin Y.
Ouellette Michel
Marcelo Melvin
Nortel Networks Limited
LandOfFree
Method and apparatus for active queue management based on... 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 active queue management based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for active queue management based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335104