Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-06-30
2004-03-16
Vincent, David (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S395200
Reexamination Certificate
active
06707790
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to allocation of network resources and Quality of Service (QoS) management for regulated traffic flows.
2. Description of the Related Art
A key challenge for future packet networks is to efficiently multiplex bursty traffic flows while simultaneously supporting Quality of Service (QoS) objectives in terms of throughput, loss probability, and end-to-end delay. At one extreme, performance can be assured even in the worst case via deterministic service. In addition to its absolute guarantee, deterministic service also has the advantage of enforceability: when the network guarantees QoS based on the client's worst-case descriptions of their traffic, the network can easily verify that these traffic specifications are satisfied. On the other hand, the most important drawback of a deterministic service is that, by its very nature, it must reserve resources according to a worst-case scenario, and hence has fundamental limits in its achievable utilization.
To overcome the utilization limits of deterministic service, statistical multiplexing is introduced to exploit the fact that the worst-case scenario will occur quite rarely. To account for such statistical resource sharing, the traffic flows' rate fluctuations and temporal correlation must be characterized. In the literature, such properties are often represented via stochastic traffic models, including Markov Modulated, Self-Similar, and others. However, in a shared public network with misbehaving or malfunctioning users, provisioning resources according to such stochastic source characterizations incurs a significant risk, as the underlying assumptions of the model are inherently difficult for the network to enforce or police.
Various disadvantageous attempts to address the fundamental conflicting requirement for deterministic traffic models to isolate and police users, and statistical multiplexing to efficiently utilize network resources, have considered network services only for single time scale flows. When traffic flows have rate variations over even two time scales, significant inaccuracies are encountered when applying a single time scale solution. Consequently, for traffic flows more complex than periodic on-off, new techniques are needed for enforcing network services.
Providing statistical services for deterministically policed traffic flows encounters the problem of statistical characterization based on deterministic policing parameters. Specifically, one usually needs to compute the marginal distributions of the flows' rate in different time scales in order to perform the call admission control.
There are competing considerations in a network. The network needs to carry as much traffic as possible, and it must support the QoS requirements of each individual flow. In other words, while as much traffic as possible is multiplexed together, the traffic is policed or regulated such that the traffic flows do not interfere with each other. As such, there continues to be a need for a solution to the aforementioned problems.
SUMMARY OF THE INVENTION
The invention provides a solution to the problem of allocating network resources and maintaining a level of Quality of Service (QoS) such that traffic flows in the network do not interfere with each other, and the network can provide an efficient statistical multiplexing operation. According to the principles of the invention, an admission control operation characterizes the statistical behavior of every flow using a maximum entropy function. If the traffic envelope, or the upper bound of the traffic rates of all time scales, are known, but nothing else about the traffic is known, the distribution of the traffic flow can be approximated by maximizing the entropy. An upper bound of the mean rate, which can be derived from the traffic envelope, and a lower bound of the traffic rates, which is zero, are always known. The entropy of the distribution is maximized subject to the considerations of mean rate, minimum rate, and maximum rate.
In accordance with an illustrative embodiment of the invention, a network element is deployed in a network of interconnected elements, such as the Internet. The network element includes a shared buffer multiplexer connected to a link, a set of regulators connected to the shared buffer mulitplexer, and an admission control unit communicatively coupled to the set of regulators and the shared buffer multiplexer. Each of the set of regulators has an input traffic flow policed by the regulator. Each traffic flow to a regulator has a varying rate of flow at different time scales.
In order to control admission of the traffic flow through the regulator to the link in the network element, the admission control unit evaluates each traffic flow. For each traffic flow, the admission control unit performs a series of process steps. Each traffic flow signals its traffic envelope to its regulator and to the admission control unit. The traffic envelope varies over different time scales. The admission control unit determines the maximum-entropy distribution for the flow at different time scales by maximizing the entropy of the distribution of the rate of the flow at each time scale. The admission control unit then approximates the rate variance of the maximum-entropy distribution for a given maximum rate. The admission control unit decides whether the flow should be admitted into the network using the approximated rate variance.
REFERENCES:
patent: 6061556 (2000-05-01), Rahman
patent: 6359877 (2002-03-01), Rathonyi et al.
patent: 983 7708 (1998-08-01), None
Gelenbe, Erol; Bandwidth Allocation and CAC in H-S Networks; 1997; IEEE; pp. 122-129.*
Guaranteeing Statistical QoS to Regulated Traffic: The Single Node Case; Martin Reisslein, Keith W. Ross and Srini Rajagopal; 1999; pp. 1061-1072.
Buffering vs. smoothing for end-to-end QoS: Fundamental issues and comparison; Tao Wu and Edward W. Knightly; Aug. 1999; 10 pages.
A New Approach for Allocating Buffers and Bandwidth to Heterogeneous, Regulated Traffic in an ATM Node; Anwar Elwalid, Debasis Mitra and Robert H. Wentworth; Aug. 1995; pp. 1115-1127.
Enforceable Quality of Service Guarantees for Bursty Traffic Streams; Edward W. Knightly; 1998; pp. 1-8.
T. Wu, et al, “Enforceable and Efficient Service Provisioning”,Computer Communications 23(2000)1377-1388.
A. Skliros, “A Connection Admission Control Algorithm for ATM Traffic Distorted by Cell Delay Variation”,Fundamen tal Role of Teletraffice in Evolution of Telecommunications Networks, Proceedings of the 14thInternational Teletraffic Congress, ITC 14, Tele traffic Science and Engineering Amsterdam, Elsevier, NL, vol. 1B, Jun., 1994, pp. 1385-1394.
Dixit Sudhir
Knightly Edward
Wu Tao
Nokia Internet Communications Inc.
Vincent David
LandOfFree
Enforceable and efficient service provisioning does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enforceable and efficient service provisioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enforceable and efficient service provisioning will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3254365