Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-11-30
2004-09-21
Phunkulh, Bob A. (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S252000, C710S052000
Reexamination Certificate
active
06795397
ABSTRACT:
REFERENCE TO A MICROFICHE APPENDIX
Not Applicable
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention pertains generally to the analysis of the variability of multimedia traffic sources and the provisioning of the Quality-of-Service parameters and more particularly to a method of determining burstiness, and burstiness curves, for a multimedia source.
2. Description of the Background Art
The explosive growth of the Internet has spawned demand for new applications whose traffic has been traditionally carried over switched networks. These new applications include audio telephony, video conferencing and video-on-demand (VoD) services. New standards are emerging to support these applications in the context of both connectionless and connection-oriented packet-switched networks.
The rate variability of traffic sources, especially video, have introduced the need for characterizing the traffic so that the appropriate resources may be allocated by the network when handling the traffic, for instance, during the call admission control (CAC) process. Numerous resources may require allocation, including bandwidth, and buffer space. Traffic characterization may also be applied to facilitate policing of the traffic on the packet-switched network.
Characterization of video sources has become increasingly important as a result of transporting video over packet-switched networks. One method that provides characterization of a traffic source is through employing a time-invariant traffic constraint function in which bounds are determined for the maximum number of bits that may be generated by the source over any arbitrary interval of time. The least upper bound of the time constraint function is also referred to as the minimum envelope process or empirical envelope. Accurate traffic characterization can be performed for a source by the minimum envelope process, however, such a process requires the use of a large number of “leaky buckets” to effectively police the traffic, and the practical significance of the process is thereby compromised. Since current packet-switched networks employ simple leaky-bucket mechanisms for traffic policing, the use of the minimum envelope process does not facilitate traffic policing.
Another method of characterizing a traffic source is by means of its burstiness curve. The points (&sgr;,&rgr;) along the burstiness curve correspond to maximum queue size &sgr; that is necessary when said traffic source is fed into a server having a deterministic service rate &rgr;. Consequently, if the traffic source is sent to a leaky bucket with parameters (&sgr;,&rgr;), none of its packets will be tagged as non-conformant. The burstiness curve, therefore, provides an attractive metric for use in policing current packet-switched networks and for allocating resources.
Burstiness curves are typically characterized by means of a token-bucket mechanism. The input of the token-bucket is the traffic generated by the source whereas the output is the corresponding token-bucket constrained traffic. The output of the token bucket is sometimes referred to as a (&sgr;,&rgr;,r) conformant traffic stream, where &sgr; is the number of tokens in the token bucket, &rgr; the rate of the incoming tokens, and r the peak rate of the server. If A(t
1
, t
2
) is the amount of traffic that leaves the token bucket during an interval (t
1
, t
2
), then the following constraint holds:
A
(
t
1
, t
2
)≦min{
r
(
t
1
−t
2
),&sgr;+&rgr;(
t
2
−t
1
)} (1)
A traffic source is said to be (&sgr;,&rgr;,r) conformant if its traffic can go through a token-bucket shaper with bucket size &sgr; and rate &rgr;, at peak rate r with the queue size never exceeding &sgr;. In the context of ATM networks, (&sgr;,&rgr;,r) enforcement is provided by utilizing the Generalized Cell-Rate Algorithm (GCRA).
Specifying an appropriate (&sgr;,&rgr;,r) tuple for the traffic source is critical to the proper allocation of resources, for instance bandwidth and buffer space, in providing a desired level of service to the traffic stream. However, there is no single tuple that uniquely characterizes a source. For any given peak rate r, it is evident from Eq. (1) that, for any value of &rgr;, there is a corresponding value of &sgr; such that the source is conformant. Hence, the set of conformant (&sgr;,&rgr;) pairs describe a curve which is referred to as the burstiness curve. Complete characterization of a source can be provided by plotting a set of burstiness curves for different values of the peak rate r. The burstiness curve of a video source is useful in determining the level of resources necessary to achieve any desired QoS level. It will be appreciated that both the delay and packet-loss rate in the network are functions of &sgr; and &rgr;. Knowledge of the burstiness curve of the source, therefore, enables the admission control process to allocate the minimum level of resources to achieve a desired QoS level.
In addition, the delay calculation in the network depends on the burstiness curve of the source. A properly configured packet-switched network scheduler based on burstiness curves allows for the specification of a maximum end-to-end guaranteed delay time. The specification of end-to-end delay of a traffic source requires utilizing algorithms configured for adherence to a strict upper bound on the delay of a session. It will be appreciated, however, that in order for a scheduling discipline to guarantee a worst-case delay bound to a session, the burstiness of the source traffic must be bounded. Analysis of worst-case delay is typically considered in relation to a token-bucket constrained traffic model. Different frameworks have been developed to formalize the characterization of schedulers and obtain the worst-case boundaries of delay. One such framework is that of “Latency-rate” (LR) which provides a general model for computation of the worst-case delay bound of several schedulers. Schedulers that fall into this classification are often referred to as Latency-Rate (LR) servers.
In utilizing the LR model it is assumed that the bandwidth allocated by the network to the session is equal to the average rate of the source &rgr;. According to the LR model, the worst-case delay bound d
M
of a tandem network consisting of K schedulers belonging to the LR class is given by:
ⅆ
M
=
σ
ρ
+
∑
i
=
1
K
Θ
i
(
2
)
where &sgr;, &rgr; are the parameters of the source, and &THgr;
i
is a parameter of the scheduler, called latency. Solving for &sgr;, the following constraint for &sgr; and &rgr; is obtained which satisfies a specified worst-case delay bound:
σ
=
(
ⅆ
M
-
∑
i
=
1
K
Θ
i
)
ρ
(
3
)
Upon considering the result it will be recognized that the optimum (&sgr;,&rgr;) pair is obtained at the intersection between the line defined by Eq. (3) and the burstiness curve.
Determination of the burstiness curve typically relies on simulation based techniques, with results obtained subsequent to a lengthy simulation session. Simulation techniques are considered especially onerous when fine rate granularity is required. Conventional methods are unable to readily determine burstiness, and burstiness curves to any desired level of granularity.
Therefore, a needs exists for an improved method of determining burstiness and burstiness curves wherein both exact determinations and approximations can be performed in less time while preferably utilizing fewer processing resources. The present invention satisfies those needs, as well and others, and overcomes the deficiencies of prior solutions.
BRIEF SUMMARY OF THE INVENTION
The present invention provides methods for determining burstiness and burstiness curves for traffic streams, typified by multimedia streams such as video and audio. By way of example and not of limitation, the detailed embodiments describe burstiness computation methods tailored for use with both elementary video streams and MPEG-2 transport streams. These burstiness computation methods exploit the
Tryfonas Christos
Varma Anujan
O'Banion John P.
Phunkulh Bob A.
The Regents of the University of California
LandOfFree
Method for determining burstiness or a burstiness curve of a... 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 for determining burstiness or a burstiness curve of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining burstiness or a burstiness curve of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3244993