Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-11-05
2003-05-06
Ton, Dang (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S230000, C370S412000
Reexamination Certificate
active
06560198
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention generally relates to congestion control in communication networks, and more particularly, to a method and system for buffer management in communication networks.
Communication networks transport information in the form of packets, frames, and/or cells from source nodes to destination nodes over transmission links. The Internet, for example, uses routers for routing packets to their respective destination nodes. Routers typically have buffers at their input and output ports for buffering the packets during the periods when the number of packets in the routers exceeds the bandwidth capacity at the output ports.
The Internet uses a variety of protocols for transporting packets including congestion control and error recovery. One widely used protocol is the Transmission Control Protocol (TCP), which uses a dynamic window based congestion control method. In the TCP congestion control method, the source and destination nodes are the only active participants in controlling traffic congestion in the network. A source node using the TCP congestion control method uses information about packet losses as congestion indicators. The TCP congestion control method is different from other congestion control techniques, for example DECBIT, where the network actively participates in controlling congestion by setting congestion indicator bits in packets when the network detects congestion.
A node, for example a router or a switch, which uses a TCP unaware buffer management scheme, simply discards arriving packets when its buffer is full. Unless the node buffer has a large capacity, such buffer management schemes generally reduce the network throughput. Also, the network allocates less bandwidth to connections that have long round-trip times than to connections with short round-trip times.
S. Floyd and V. Jacobson, “Random Early Detection Gateways For Congestion Avoidance,” IEEE/ACM Transactions On Networking, vol. 1, no. 4, pp. 397-413, August 1993, describes a Random Early Detection (RED) technique, which uses a TCP aware buffer management scheme. With the RED technique, when the average buffer content is beyond a predetermined threshold, a node randomly discards packets according to a probability, which is based on the recent behavior of the buffer content. When a node discards a packet, the source node eventually detects this packet loss, infers that the network is congested, and decreases its transmission window (also referred to as congestion window). Hence, by decreasing the size of its congestion window and thus reducing the number of outstanding packets in the network, the source node reduces the buffer occupancy of nodes in the network.
One of the problems associated with the RED technique is that the impact of discarding a packet strongly depends on the window size of the TCP connection associated with the source node. Generally, when the source node detects a packet loss, it decreases its congestion window size by one-half and then under most circumstances, as long as the source node does not detect any more packet losses, it increases its congestion window by one Maximum Segment Size (MSS), for example one packet, once every one or two round-trip times.
For example, when a discarded packet belongs to a connection with a congestion window of, for example, 6 MSSs, the congestion window decreases by 3 MSSs to 3 MSSs, and after 3 to 6 round-trip times, the congestion window is back to its original size of 6 MSSs. On the other hand, when a discarded packet belongs to a connection with a congestion window of 1000 MSSs, the congestion window decreases by 500 MSSs to 500 MSSs, and it takes 500 to 1000 round-trip times before the congestion window is back to its original size of 1000 MSSs.
Therefore, to enhance the network throughput, a node would need to know whether a specific high buffer content is caused by a few connections with large congestion windows or by a large number of connections with small congestion windows. The former requires a small packet discard rate, whereas the latter requires a high packet discard rate.
One known solution is to maintain at each node a list of the currently active connections that are supported by the node. This solution requires per connection state information, which would be impractical when the number of connections is large or when it is desired to keep the cost of the node low while providing tolerable network performance.
Therefore, it is desirable to have a method and system for stabilizing buffer occupancy in communication networks, and thus, to overcome the disadvantages of the prior art.
DESCRIPTION OF THE INVENTION
Methods and systems consistent with the present invention estimate the number of active connections (or flows) in a node in a communications network without maintaining state information on each connection by sampling one or more packets in a buffer in the node when the node receives a packet, determining the number of the sampled packets that are associated with the same connection as the received first packet, and estimating the number of the active connections in the node based on the determined number of the sampled packets.
Furthermore, such methods and systems stabilize the buffer occupancy by estimating the number of active connections in the node based on a sampling of the packets in the buffer when the node receives the packet, determining a probability for discarding the received packet based on the estimated number of the active connections and the recent buffer occupancy, and discarding the received packet according to the determined probability. The buffer occupancy may be expressed in terms of, for example, the fraction of the buffer space that is occupied by packets.
In addition, when the buffer occupancy exceeds a first predetermined threshold and the determined number of sampled packets that are associated with the same connection as the received first packet is greater than zero, such methods and systems may collect certain state information associated with that connection, and monitor the connection based on the collected state information. When the state information collected over a predetermined interval of time is less than a second predetermined threshold, such methods and systems terminate the collection of state information associated with the connection.
Such methods and systems have several advantages over the prior art. With the present invention, the number of packets at which the buffer occupancy of a node stabilizes becomes less dependent on the number of active connections in the node. Furthermore, the present invention reduces the amount of state information that the node has to maintain for each connection. Finally, by stabilizing the buffer occupancy of the node, the amount of jitter in the network is reduced.
The description of the invention and the following description for carrying out the best mode of the invention should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. The accompanying drawings, which form part of the description for carrying out the best mode of the invention, show several embodiments of the invention, and together with the description, explain the principles of the invention.
REFERENCES:
patent: 5430709 (1995-07-01), Galloway
patent: 5938749 (1999-08-01), Rusu et al.
patent: 5995486 (1999-11-01), Illadis
patent: 6034945 (2000-03-01), Hughes et al.
patent: 6122252 (2000-09-01), Aimoto et al.
patent: 6141323 (2000-10-01), Rusu et al.
Lakshman Tirunell V.
Ott Teunis J.
Falk James W.
Giordano Joseph
Phan Tri
Telcordia Technologies Inc.
Ton Dang
LandOfFree
Method and system for stabilized random early detection... 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 system for stabilized random early detection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for stabilized random early detection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3002229