Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1997-10-29
2001-03-13
Nguyen, Chau (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S255000
Reexamination Certificate
active
06201791
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to networking in general and specifically for dynamically estimating the idle bandwidth capacity of a packet switched communications channel in a communications network for purposes such as bandwidth reservation and allocation. Once the idle capacity of a channel is determined, it is possible to estimate the optimal window size at which the channel should operate and to further improve the operation of the channel, while at the same time reducing the possibility that the bandwidth measurements will push the channel into congestion and packet loss. The idle capacity is used to make bandwidth guarantees to applications; the optimal window size is used to help achieve maximum throughput of the channel.
BACKGROUND OF THE INVENTION
There is a need to determine dynamically the idle capacity of a packet communication channel in which the actual network nodes and links which form the channel cannot be predicted or controlled apriori. The Internet is such a network. The set of Internet nodes and links that form an Internet channel between a source node and a destination node anywhere in the world is unpredictable and depends on a number of variables such as the time the channel is formed and the state of spanning trees located in the various nodes that are selected as the channel is formed. Knowledge of the idle channel bandwidth at any given time is needed, for example, to allocate or reserve the bandwidth for different applications or for various purposes. It is also desirable to determine this idle bandwidth and the optimal window size on a channel that is in use, without significantly increasing the probability of channel overload and packet loss.
The effective bandwidth of a channel depends on the window size that is in use on the channel. Window size is defined as the maximum number of packets that can be in transit on a channel at any given time. One can think of the operation of a channel as a source node initially transmitting N packets, where N equals the window size, and thereafter transmitting one packet for each packet acknowledgment that is received from the destination node. In this way, one window's worth of packets are maintained in transit on the channel.
There is an optimal window size for every channel and this optimal size varies depending on channel load, among other things. When a channel is operating at below its optimal window size, queuing is not occurring at the nodes that form the channel and there is idle bandwidth available. A channel operating at above its optimal window size is experiencing queuing at the channel nodes. If the channel load is pushed too far, the queue of the worst performing node (the bottleneck node) in the channel will overflow and packet loss will be experienced.
To my knowledge, there is no known feasible way at the present time of dynamically determining the idle capacity of a channel. However, there are known methods of estimating idle capacity over a relatively large period of time by sending a large number of packets much greater that a typical window size. This characteristic of transmitting many windows worth of packets is what makes the known methods undesirable for dynamic use. Early methods of measuring idle channel capacity rely on sending packets from a source node at a constant rate and estimating performance from the arrival rate of acknowledgments and the number of packets lost. However, these methods are unreliable. At packet rates less than the processing rate of the bottleneck node in the channel, no queue is formed and performance is measured at less than the optimal performance of the channel. At packet rates even slightly greater than the processing rate of the bottleneck node, the queue quickly overloads and there is not a sustained queue in the channel from which reliable data can be obtained by use of these algorithms. Further, as mentioned, large numbers of packets are required, which detracts from their use dynamically.
Mathew Mathis addressed the problem of overload in the measuring process as described in his 1994 paper “Windowed Ping: An IP Layer Performance Diagnostic”. Mathis uses a sliding window size control to plot the performance of a channel in terms of packets in transit (window size) versus packets delivered and lost. However, Mathis's method also requires the transmission of large numbers of packets at different window sizes to plot the static performance of the channel.
Both of these methods of estimating idle capacity require the transmission of many windows worth of packets. This consumes resources and may further the tendency of a channel to congest. Thus, the known methods are not suitable for dynamically determining or estimating channel bandwidth. Further, if the optimal window size is not being used, then there is idle channel time introduced at the bottleneck node of the channel as illustrated in FIG.
3
and this tends to worsen the accuracy of bandwidth estimates.
SUMMARY OF THE INVENTION
In accordance with the invention, it has been determined that the idle capacity of a channel can be reliably estimated by transmitting only a single window of packets at whatever window size is presently in use on the channel and by measuring the time intervals between acknowledgments of adjacent packets. Preferably, an average value for the inter-acknowledgment time interval is calculated from all of the acknowledgment intervals associated with the window of packets. The idle capacity of the channel is then calculated from the formula C=1/I
Avg
, where C is the idle capacity in packets per second and I
Avg
is the average acknowledgment time between packets. This method of determining idle capacity is effective, even though the channel is presently operating at less than or greater than its optimal window size. This is important, since in real situations, the window size actually in use on a channel and for which a window of test packets is transmitted is usually arbitrarily selected and is usually less than the optimal bandwidth of the channel.
Preferably, all of the window of test packets is transmitted in immediate succession and results are calculated after acknowledgments are received for each of the test packets. However, even though this transmits far less than the number of packets onto the channel than prior known methods, it still introduces traffic into a channel already in use and may lead in some cases to undesirable congestion and packet loss. An alternative method may be used in some cases to meter the window of test packets over short intervals to further reduce the tendency to congest and interfere with real traffic. For example, if a window size happened to be ten packets, it would be satisfactory in most circumstances to meter the ten packets in groups of 2 or more over a number of relatively short intervals.
The same parameters that are collected to calculate the idle capacity are also used to calculate the optimal window size on a dynamic basis and each value of optimal window size is used by the protocol components of the system that controls the actual window in use to improve the performance of a channel. Since the idle channel capacity and optimal window size changes over time, preferably the estimates are periodically updated and refined.
REFERENCES:
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 5063562 (1991-11-01), Barzilai et al.
patent: 5274625 (1993-12-01), Derby et al.
patent: 5680326 (1997-10-01), Russ et al.
patent: 5708656 (1998-01-01), Noneman et al.
patent: 5923849 (1999-07-01), Venkatraman
patent: 6125363 (1994-05-01), None
Chen et al. “The Analysis of the Application of ARQ Mechanism in ATM Network” Communication Technology Proceedings. ICCT'96., 1996, pp.263-266.
“An Appoximation Method for Capturing Complex Traffic Behavior in High-speed Networks”, Special Issue of the Performance Evaluation Journal (1994) by: L. Gun.
“Windowed Ping: An IP Layer Performance Diagnostic”, Proc. INET 94'/JENC5, By: M. Mathis.
“Window Based Bandwidth Adjustments”, IBM Technical Disclosure Bullet
Herndon Jerry W.
International Business Machines Corp.
Kwoh Jasper
Nguyen Chau
LandOfFree
Method and apparatus for measuring flow capacity of and... 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 measuring flow capacity of and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for measuring flow capacity of and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2510789