Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1997-03-21
2001-10-16
Marcelo, Melvin (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S252000
Reexamination Certificate
active
06304551
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a device and method for real-time estimation and dynamic renegotiation of usage parameter control (UPC) parameters for arbitrary traffic sources in asynchronous transfer mode (ATM) networks, and more particularly, to a device and method for dynamically renegotiating UPC parameters whenever a predetermined change in traffic characteristics is detected.
2. Discussion of the Prior Art
In networks based on asynchronous transfer mode (ATM), traffic sources are subjected to a usage parameter control (UPC) function which employs a deterministic algorithm to control or shape a cell stream emitted from a source. In a UPC-based traffic control framework, the UPC parameters constitute a traffic descriptor used to allocate network resources to the traffic source.
BACKGROUND OF INVENTION
One key feature of ATM networks is their potential for efficiently supporting variable bit rate (VBR) traffic sources, such as video. Applications such as video have stringent requirements on the guarantee of the quality-of-service (QoS) provided by the network. An ATM network, however, can guarantee QoS only if it has a reasonably good description of the characteristics of the offered traffic. Hence, a traffic descriptor that describes the characteristics of the offered traffic, and a policing mechanism that ensures conformance with the declared traffic parameters, are essential.
A single leaky bucket has been studied extensively as a means of open-loop control of a traffic stream at the network edge. Since a constant bit rate (CBR) traffic or data stream has a well-defined rate, the single leaky bucket provides an adequate description of the stream. However, for variable bit rate (VBR) streams, peak rate allocation via a single leaky bucket is wasteful of network resources. Hence, a dual leaky bucket mechanism has been proposed for policing and characterizing the more general VBR source.
It is recognized that VBR streams such as video may be transmitted over an ATM network as a CBR stream. However, video sources naturally produce variable bit rate streams. Transmitting video as a CBR stream may result in variable quality and/or lower network utilization. This is because the statistical multiplexing feature of ATM is not exploited in this case.
The dual leaky bucket UPC offers a better means of characterizing VBR traffic, but introduces the problem of selecting the appropriate parameter values for a given stream. This problem has been recognized as important for providing efficient VBR service in ATM networks.
Despite the recognition of this important problem, to date, most of the methods devised for selecting UPC parameters have been ad-hoc, without having a sound theoretical basis.
Some approaches have assumed specific models for the user traffic, namely the on-off Markov fluid model, in order to obtain UPC values. This approach, however, is not robust for traffic streams that behave much differently from the on-off model. Accordingly, there is a need to characterize efficiently an arbitrary ATM traffic stream and select optimal dual leaky bucket UPC values with respect to minimizing network resource requirement and subject to QoS constraints for an arbitrary traffic source.
SUMMARY OF THE INVENTION
The object of the present invention is to provide a device and a method for real-time characterization of an arbitrary asynchronous transfer mode (ATM) data traffic that eliminates the problems of conventional data traffic control methods.
The present invention relates to a method of characterizing, in real-time, an asynchronous transfer mode (ATM) traffic stream by a set of usage parameter control (UPC) values to be negotiated with a network provider for the purposes of resource allocation and traffic policing with respect to the said traffic stream. Moreover, the invention provides a method for detecting predetermined changes in the relevant statistical characteristics of the traffic stream and subsequently, dynamically renegotiating the UPC values with the network. The invention is an important component in a UPC-based traffic control framework for ensuring quality-of-service (QoS) while maintaining high network resource efficiency.
The UPC traffic descriptor based on the dual leaky bucket algorithm provides a mechanism to describe the offered traffic. The dual leaky bucket UPC is implemented by a deterministic algorithm which maps an input arrival process to an output arrival process that conforms to the characteristics specified in four parameters. In the UPC-based approach to traffic control, the UPC values for a source are taken as a traffic descriptor to be used by a connection admission control (CAC) function for making admission decisions.
The four-parameter dual leaky bucket provides control for two rates: the peak rate and sustainable rate with burst tolerances on both rates. By contrast, the two-parameter single leaky bucket controls only the peak rate (with burst tolerance) of a stream. While the single leaky bucket is suitable for controlling constant bit rate (CBR) traffic, it does not provide an efficient means of controlling VBR traffic, which behaves as a random traffic source. Characterizing a VBR stream by its peak rate could result in very poor network resource utilization.
The present invention includes a method for statistically characterizing an arbitrary traffic stream together with a method of mapping the characterization to dual leaky bucket parameters. Furthermore, the present invention provides a means of detecting when UPC values should be renegotiated with respect to source QoS constraints.
The present invention provides a method for determining, in real-time, optimal dual leaky bucket UPC values for an arbitrary ATM traffic stream. The UPC values selected by the inventive method are optimal in the sense of minimizing the network resource requirement implied by UPC values, taking into account the statistical properties of the traffic stream and the QoS constraints of the source. Further, the invention adapts to significant changes, in traffic characteristics by dynamically renegotiating UPC values with the network.
One embodiment of the present invention includes a method of characterizing an arbitrary asynchronous transfer mode traffic stream in real-time comprising the steps of:
characterizing the traffic stream statistically over an observation interval T;
mapping the statistically characterized traffic stream to usage parameter control (UPC) values of a dual leaky bucket which minimize a cost function subject to predetermined constraints of a user, the dual leaky bucket including a peak rate leaky bucket and a sustainable rate leaky bucket, and the UPC values including a peak rate &lgr;
p
, a sustainable rate &lgr;
s
, and a sustainable bucket size B
s
;
detecting a predetermined change in the traffic stream; and
renegotiating the UPC values with a network when the predetermined change is detected.
Another embodiment includes a device for managing an arbitrary asynchronous transfer mode (ATM) cell stream from a source comprising:
a usage parameter control selector which characterizes the cell stream statistically over an observation interval T and maps the statistical characterization to dual leaky bucket usage parameter control (UPC) values once every observation interval T, in response to observations of the cell stream and source shaping constraints received from the source; and
a usage parameter control shaper that shapes, in accordance with the UPC values, the cell stream received from the source and outputs shaped stream data.
REFERENCES:
patent: 5448567 (1995-09-01), Dighe et al.
patent: 5524006 (1996-06-01), Hluchyj et al.
patent: 5530695 (1996-06-01), Dighe et al.
patent: 5559798 (1996-09-01), Clarkson et al.
patent: 5629937 (1997-05-01), Hayter et al.
patent: 5636212 (1997-06-01), Ikeda
Mark Brian Lai-Bue
Ramamurthy Gopalakrishnan
Lee Chiho Andrew
Marcelo Melvin
NEC USA Inc.
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Real-time estimation and dynamic renegotiation of UPC values... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Real-time estimation and dynamic renegotiation of UPC values..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time estimation and dynamic renegotiation of UPC values... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2606934