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, xe2x80x9cRandom Early Detection Gateways For Congestion Avoidance,xe2x80x9d IEEE/ACM Transactions of 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 r 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.
Another solution, which is disclosed in a pending U.S. patent application Ser. No. 09/186,241, entitled xe2x80x9cMethod And System For Stabilized Random Early Detection Using Packet Samplingxe2x80x9d and filed concurrently with the present application, estimates the number of active connections in each node without maintaining state information on each connection. Each node samples one or more packets in its buffer when the node receives a packet. The node then determines the number of sampled packets that are associated with the same connection as the received first packet, and estimates the number of active connections in the node based on the determined number of sampled packets. This solution, however, has a disadvantage that a node cannot compare arriving packets that are more than one buffer drain time apart.
Methods and systems consistent with the present invention determine the number of active connections in a node in a communications network by sampling a list of recently active connections in the node when the node receives a packet, and estimating the number of active connections based on whether the packet is associated with a sampled entry in the list, where each entry comprises a connection identifier and a count. Such methods and systems also identify a connection associated with the received packet, increment the count of the sampled entry when the identified connection is associated with the connection identifier of the sampled entry, and based on a predetermined probability, modify the sampled entry to correspond to the identified connection when the identified connection is not associated with the connection identifier.
Furthermore, the methods and systems stabilize the buffer occupancy of the node by estimating the number of active connections in the node based on a sampling of a list of recently active connections in the node when the node receives a packet, determining a probability for discarding the packet based on the estimated number of active connections and the recent buffer occupancy, and discarding the 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.
Finally, such methods and systems monitor the identified connection when the identified connection is associated with the connection identifier, the count exceeds a first predetermined threshold, and/or a total occurrences of the connection identifier in the list exceeds a second predetermined threshold.
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.