Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-08-07
2002-08-20
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S237000, C370S395100, C370S395410, C370S429000, C370S468000, C709S234000
Reexamination Certificate
active
06438104
ABSTRACT:
Interconnected wide area networks, such as the Internet, use a predefined transport protocol to communicate data packets over network links. Typically, the transported data packets are formatted in accordance with any one of a number of different internet protocols (IPs). For example, since its introduction in the ARPANET in the 1970s, the Transmission Control Protocol (TCP) has become the most widely used transport protocol, due largely to the explosive growth of the TCP/IP Internet in recent years. In addition to TCP, other IPs include the user datagram protocol (UDP) and the real-time transport protocol (RTP) which are used primarily by applications requiring real-time data transfer requirements.
The IP data packets are further formatted in accordance with a point-to-point protocol (PPP) that provides a standard format for multi-protocol data packets over point-to-point links. With the recent popularity of Asynchronous Transfer Mode (ATM), a standard asynchronous-data PPP that offers a wide variety of network services, efforts have been underway to adopt various IP layers over ATM-based networks. The ATM protocol communicates data in fixed size data packets known as ATM cells. Each ATM cell has a singular format comprising a 48 octet payload portion and a 5 octet header portion. Through ATM servers, the ATM cells are routed through packet switches over virtual circuits (VCs) that are set up between endpoints. Using proper scheduling algorithms in the packet switches, the ATM protocol is capable of handling multiple classes of traffic, with each class requiring a corresponding quality-of-services (QOS). For transferring real-time video data, for example, a QOS capable of handling real-time deadlines is required. Another QOS is known as “best effort,” which is the type of service employed for transferring data packets in the Internet. For the “best effort” type of QOS, there is no real-time deadline and no guarantees on the available bandwidth, delay, or cell loss rate.
For improving data throughput over network links, some transport layers, such as TCP, include congestion control and recovery algorithms. An important characteristic of TCP congestion control is that it assumes no support from the underlying network and lower layers to indicate or control congestion. Instead, implicit feedback signals such as acknowledgment, timeouts, and duplicate acknowledgments, are used to infer the state of the network. The feedback signals control the amount of traffic injected into the network by modifying the window-size used by a sender.
Although TCP is designed to work in networks with no congestion control mechanism below the transport layer, for various reasons, ATM link-level flow control schemes are used over each VC. For example, one link-level congestion control scheme notifies a packet source directly upon congestion by sending a special ATM cell in reverse direction towards the higher level transport protocol.
Most link-level congestion control schemes buffer the ATM cells arriving at the ATM servers. In wide-area-networks (WANs), where hundreds or thousands of VCs may share the same link, it is customary to share the buffers in order to avoid prohibitive amount of buffering. In such WANs, a conventional link-level congestion control approach is known as ATM Early Packet Discard (ATM-EPD). The ATM-EPD operates on the assumption that once an ATM cell belonging to an IP packet is discarded, all other ATM cells which belong to the same IP packet should be discarded, since the IP packet cannot be reassembled at the destination node. Under the conventional ATM-EPD algorithm, once the buffer occupancy at an ATM switch increases over a pre-defined threshold, the next new IP packet arriving into the buffer is selected and the entire block of constituent ATM cells of that packet are discarded. In this way, the ATM-EPD algorithm effectively prevents fragments of packets from consuming network resources and contributing to further congestion.
Although the conventional EPD algorithm is able to differentiate between the ATM cells of different IP streams that enter a shared buffer, it does not guarantee a predefined share of the available bandwidth amongst different IP packet sources. As a result, in a multi-service network that, for example, supports both TCP and UDP packet sources, the end-to-end TCP congestion control algorithms could decrease sending rate, making more than a fair share of the bandwidth available for the UDP packet sources. In this situation, the UDP packet sources could utilize the bandwidth to the detriment of the TCP packet sources.
In order to provide bandwidth utilization balance among different IP packet sources, it is desirable for the underlying ATM layer to provide a mechanism by which the individual IP sources receive a predefined share of the available bandwidth. This is especially the case in IP/ATM type networks, where certain QOS guarantees should be given to some IP packet sources, while others may be given no guarantee under the best effort QOS. Therefore, there is a need for a simple link-level congestion control method that takes into account fairness amongst various protocols of the IP packet sources, while maximizing link bandwidth utilization and applying corresponding bandwidth guarantees.
SUMMARY OF THE INVENTION
Briefly, the present invention is embodied in a link-level flow control method for an ATM network that receives indications of requested link bandwidth for a plurality of ATM cell streams having corresponding IPs. The received ATM cells are queued in a shared FIFO buffer having a predefined buffer capacity providing specified total link bandwidth to an ATM server. Based on the number of ATM cells queued during a predefined time period, a maximum number of ATM cells to be served for a corresponding internet protocol is determined, with the determined maximum number corresponding to the requested link bandwidth from the plurality of packet sources.
The method of the invention is implemented in the ATM server, which has a FIFO buffer with a predefined buffer size for serving the arriving ATM cells. The ATM server controls the flow of ATM cell streams arriving from a number of packet sources, with each packet source providing cell streams according to one or more of the IPs. Each packet source indicates the requested link bandwidth to the ATM server. Based on the requested link bandwidth, a requested bandwidth share of the total link bandwidth for each packet source is determined. The packet sources that during the pre-defined time period have transmitted ATM cells equal to or below their requested bandwidth share are identified as non-violating packet sources, and those packet sources that during the same time period have transmitted ATM cells in excess of their fair share of the total link bandwidth are identified as violating packet sources. The non-violating sources are granted a share of the link bandwidth that is no more than their requested share of the link bandwidth. The violating packet sources are granted a share of the link bandwidth that is less than their requested share of the link bandwidth, such that the remaining bandwidth share is fully utilized.
According to the some of the more detailed features of the invention, the violating and non-violating packet sources are identified repetitively on a stop-and-go basis at the end of the pre-defined time period. Under another arrangement, the violating and non-violating packet sources are identified on a sliding time window basis, when a congestion condition is indicated during, for example, when the number of arriving ATM cells in the FIFO buffer exceeds a predefined threshold.
According to yet other more detailed features of the present invention, the violating and non-violating sources are identified by ordering the packet sources based on the corresponding number of ATM cells received from them during the predefined period. Then, a total number of overflow ATM cells beyond the server capacity is determined. Based on the total number of overflow ATM cells, the bandwidth granted
Fodor Gabor
Rácz András
Burns Doane Swecker & Mathis L.L.P.
Hsu Alpus H.
Telefonaktiebolaget L M Ericsson (publ)
LandOfFree
Link-level flow control method for an ATM server does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Link-level flow control method for an ATM server, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Link-level flow control method for an ATM server will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2923699