Real-time estimation and dynamic renegotiation of UPC values for arbitrary traffic sources in ATM networks

• US 6,304,551 B1
• Filed: 03/21/1997
• Issued: 10/16/2001
• Est. Priority Date: 03/21/1997
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC USA Inc (NEC Corporation)
• Inventors: Mark, Brian Lai-Bue, Ramamurthy, Gopalakrishnan
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US08/821,864
• Time in Patent Office: 1,670 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/238, 370/236, 370/252, 370/253, 370/395, 370/468
• US Class Current: 370/232
• CPC Class Codes: H04L 2012/563 Signalling, e.g. protocols, reference model
• CPC Class Codes: H04L 2012/5637 Leaky Buckets
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A scheme for determining the usage parameter control (UPC) values for an arbitrary traffic source from observations of its emitted cell stream is disclosed. The UPC values are used in a traffic shaping mechanism based on a dual leaky bucket, which shapes the cell stream by either discarding or delaying cells. The choice of UPC values is a function of the statistical characteristics of the observed cell stream; the user'"'"'s tolerance for delay prior to the network access point; and the cost incurred on the network side. The chosen UPC values are then negotiated with the network. The source traffic characteristics may change dramatically over time, making the initially negotiated UPC descriptor inappropriate for the entire traffic stream. Hence, a method is disclosed for dynamically renegotiating UPC parameters whenever a predetermined change in traffic characteristics is detected. This method for real-time estimation and dynamic renegotiation of UPC parameters is the basis for a self-contained module which allows the source to make efficient use of the network resources.

Claims

1. A method of characterizing an arbitrary asynchronous transfer mode (ATM) 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, said dual leaky bucket including a peak rate leaky bucket and a sustainable rate leaky bucket, and said UPC values including a peak rate λ

_p, a sustainable rate λ

_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 said predetermined change is detected.

2. The method of claim 1, wherein the characterizing step further comprise the steps of:

offering the traffic stream to a bank of N constant service rate queues with spaced rates that are spaced between an estimated mean rate {circumflex over (λ

)}_m and an estimated peak rate {circumflex over (λ

)}_p, said spaced rates being candidates for sustainable rates; and

approximating a tail waiting time distribution for each of said queues by an exponential equation having a form of

3. The method of claim 2, wherein the offering step comprises the step of choosing rates for the bank of N queues, said choosing step comprising the steps of:

dividing the N queues into a set of N_c coarse queues each having a coarse rate, N_f fine queues each having a fine rate, and a queue having a rate equal to a current sustainable rate;

assigning the coarse rates to be spaced between a current estimated mean rate {circumflex over (λ

)}_m(n) and a current estimated peak rate {circumflex over (λ

)}_p(n) according to a coarse rate resolution given by ${\mathrm{\Delta <br><br>}}_c<br><br>\left(n\right)=\left[\frac{{\widehat{\mathrm{\lambda <br><br>}}}_p<br><br>\left(n\right)-{\widehat{\mathrm{\lambda <br><br>}}}_m<br><br>\left(n\right)}{N_c+1}\right];<br><br>\mathrm{and}$

assigning the fine rates to be spaced symmetrically about a current sustainable rate according to the fine rate resolution given by ${\mathrm{\Delta <br><br>}}_f<br><br>\left(n\right)=\frac{{\mathrm{\Delta <br><br>}}_c<br><br>\left(n\right)}{\left(N_f/2\right)+\left(1\right)}.$

4. The method of claim 2 further comprising the step of estimating the parameters a(μ

) and b(μ

) in the tail waiting time distribution for each queue of constant service rate μ

, said estimating step comprising the steps of;

estimating an average remaining service time, T_r(μ

), for a customer in service as seen by an arriving customer conditional on there being a customer in service;

estimating a probability that an arbitrary arriving customer sees a customer in service, and setting a(μ

) equal to said probability;

estimating q(μ

), which is an expected number of customers in a queue seen by the arbitrary arriving customer; and

computing b(μ

) according to $b<br><br>\left(\mathrm{\mu <br><br>}\right)=\frac{a<br><br>\left(\mathrm{\mu <br><br>}\right)<br><br>\mathrm{\mu <br><br>}}{{\mathrm{\mu <br><br>\tau <br><br>}}_r<br><br>\left(\mathrm{\mu <br><br>}\right)<br><br>a<br><br>\left(\mathrm{\mu <br><br>}\right)+q<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\mu <br><br>}}.$

5. The method of claim 2 further comprising computing a smallest sustainable bucket size B_s(μ

) for a predetermined sustainable rate μ

, such that a sustainable rate leaky bucket with parameters (μ

,B_s(μ

)) satisfies a constraint on one of a violation probability and a mean shaping delay according to $B_s<br><br>\left(\mathrm{\mu <br><br>}\right)=\frac{\mathrm{\mu <br><br>}}{b<br><br>\left(\mathrm{\mu <br><br>}\right)}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\frac{a<br><br>\left(\mathrm{\mu <br><br>}\right)}{\mathrm{\epsilon <br><br>}}\right)$

when the violation probability is constrained to be no larger than a predetermined violation probability ε

, and according to $B_s<br><br>\left(\mathrm{\mu <br><br>}\right)=\frac{\mathrm{\mu <br><br>}}{b<br><br>\left(\mathrm{\mu <br><br>}\right)}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\frac{a<br><br>\left(\mathrm{\mu <br><br>}\right)}{b<br><br>\left(\mathrm{\mu <br><br>}\right)<br><br>\stackrel{\_}{D}}\right)$

when the mean shaping delay is constrained to be no more than a predetermined mean shaping delay {overscore (D)}.

6. The method of claim 1 further comprising computing an approximate required resource as a cost function, c(λ

_p, λ

_s, B_s) of a predetermined UPC set (λ

_p, λ

_s, B_s) according to $c<br><br>\left({\mathrm{\lambda <br><br>}}_p,{\mathrm{\lambda <br><br>}}_s,B_s\right)=\min <br><br>\left({\mathrm{\lambda <br><br>}}_p,{\mathrm{\lambda <br><br>}}_s+K<br><br>\frac{{\mathrm{\lambda <br><br>}}_s<br><br>\left({\mathrm{\lambda <br><br>}}_p-{\mathrm{\lambda <br><br>}}_s\right)<br><br>B_s}{{\mathrm{\lambda <br><br>}}_p}\right)$

where K is a parameter used to match approximately a connection admission control function of the network.

7. The method of claim 2, wherein the mapping step comprises the steps of:

computing, for each of the candidate sustainable rates μ

used in the characterizing step, a corresponding value B_s(μ

) for a smallest sustainable bucket size such that a sustainable rate leaky bucket with parameters (μ

,B_s(μ

)) satisfies a constraint which bounds one of a cell violation probability and a mean shaping delay;

computing, for each of the candidate sustainable rates μ

used in the characterizing step, a corresponding value c(λ

_p, μ

, B_s(μ

)) of the cost function that determines cost to the network;

selecting, among the candidate sustainable rates, an optimal sustainable rate μ

=λ

*_s that minimizes the cost function c(λ

_p, μ

, B_s(μ

)); and

choosing new UPC values that include the peak rate λ

_p, the optimal sustainable rate λ

_s*, and the sustainable bucket size B_s(λ

_s*).

8. The method of claim 1, wherein the detecting step comprises the steps of:

estimating a mean cell delay, {circumflex over (d)}, for a leaky bucket parameterized by the sustainable rate λ

_s and the sustainable bucket size B_s;

estimating the peak rate μ

_p to obtain an estimated peak rate {circumflex over (λ

)}_p;

signaling a change when the mean cell delay {circumflex over (d)} falls outside a range of values in a neighborhood of a user-specified tolerable mean delay {overscore (D)}, or when the estimated peak rate {circumflex over (λ

)}_p falls outside a range of values in a neighborhood of the peak rate λ

_p.

9. The method of claim 8, wherein said leaky bucket is a sustainable rate leaky bucket of a dual leaky bucket that includes a peak rate leaky bucket connected in series to said sustainable rate leaky bucket.

10. 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;

a usage parameter control shaper that shapes, in accordance with said UPC values, the cell stream received from the source and outputs shaped stream data; and

a change detector which receives the cell stream, source shaping constraints, and the UPC values, and outputs a change signal indicative of whether an update of the UPC values stored in a memory is required.

11. The device of claim 10 further comprising a current usage parameter control module which stores the UPC values.

12. The device of claim 11 further comprising a signaling module which receives the UPC values and the change signal, and provides updated UPC values received from the usage parameter control selector to the memory when the change signal indicates said update is required.

13. The device of claim 11 further comprising a signaling module which receives the UPC values and the change signal, and outputs a UPC renegotiation request to the network, said signaling module providing said update of UPC values to the memory when said signaling module receives an accept signal from the network indicating acceptance of said UPC renegotiation request.

14. The device of claim 11, wherein the change detector estimates a peak rate {circumflex over (λ

)}_p and a mean cell delay, {circumflex over (d)}, for a sustainable rate leaky bucket parameterized by current negotiated UPC values (λ

_s,B_s); and

wherein the change detector outputs a change signal that indicates update of the UPC values is required when the mean cell delay {circumflex over (d)} falls outside a range of values in a neighborhood of a user-specified tolerable mean delay {overscore (D)}, or when the peak rate {circumflex over (λ

)}_p falls outside a range of values in a neighborhood of a current negotiated peak rate λ

_p.

16. The device of claim 11, wherein said usage parameter control shaper provides a shaper overload signal to said source when a buffer of said shaper overloads.

17. The device of claim 16, wherein said source reduces said cell stream data in response to said shaper overload signal.

15. 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;

a usage parameter control shaper that shapes, in accordance with said UPC values, the cell stream received from the source and outputs shaped stream data; and

a signaling module which receives said UPC values from said usage parameter control selector and outputs a UPC renegotiation request to the network, said usage parameter control shaper providing a shaper overload signal to said source when an accept/reject signal from the network provided in response to the UPC renegotiation request indicates a rejection of said renegotiation request.

18. The device of claim 15 further comprising a current usage parameter control module which stores the UPC values.

19. The device of claim 15, wherein said usage parameter control shaper provides a shaper overload signal to said source when a buffer of said shaper overloads.

20. The device of claim 19, wherein said source reduces said cell stream data in response to said shaper overload signal.