Multi-class connection admission control method for Asynchronous Transfer Mode (ATM) switches

• US 6,046,981 A
• Filed: 02/28/1997
• Issued: 04/04/2000
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: NEC USA Inc (NEC Corporation)
• Inventors: Ramamurthy, Gopalakrishnan, Ren, Qiang
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Tran, Maikhanh
• Application Number:
  US08/808,128
• Time in Patent Office: 1,131 Days
• Field of Search: 370/230, 370/232, 370/233, 370/234, 370/468, 370/413, 370/414, 370/412
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A multi-class connection admission control (CAC) method that supports cell loss and delay requirements. In this model-based CAC, the source traffic is described in terms of the usage parameter control (UPC) parameters. Through analysis and approximations, simple closed-form methods to calculate the bandwidth required to meet guarantees on quality of service (QoS) are used. In addition to being robust, the CAC achieves a high level of resource utilization and can be easily implemented for real-time admission control.

Claims

1. A multi-class connection admission control method for admitting a new constant bit rate (CBR) connection to an ATM switch situated within a telecommunications network, said method comprising:

a first step of converting heterogeneous variable rate CBR connections into a number of homogeneous CBR connections, each of which has a same rate, called the basic rate;

a second step of using an algorithm to compute an additional capacity that must be added to a current capacity of a particular CBR class such that all quality of service (QoS) requirements for all CBR connections including existing CBR connections and a new incoming CBR connection are met;

wherein said quality of service requirements include a stability requirement, a cell delay variation (CDV) requirement and a cell loss ratio (CLR) requirement.

2. The multi-class connection admission control method according to claim 1 wherein said additional capacity is obtained according to the following relationship:

space="preserve" listing-type="equation">j=λ

.sub.p */R.sub.b,

where λ

_p * is a peak bit rate for the new connection and R_b is the bit rate of the equivalent sources; and

K, the total number of equivalent basic rate CBR sources, including the contribution from the new connection is determined according to;

##EQU61## where n is the number of CBR connections that are already admitted by the switch and λ

_pⁱ is the peak bit rate for the CBR connection i (i=1, 2, . . . n).

3. The multi-class connection admission control method according to claim 2 wherein said additional capacity, Δ

_cbr, is determined according to the following relationship;

space="preserve" listing-type="equation">Δ

.sub.cbr =C.sub.cbr.sup.new -C.sub.cbr.sup.old,

wherein C_cbr^new is the capacity required for the particular CBR class after the new connection is accepted and C_cbr^old, is the capacity of the particular CBR class before the new connection is accepted and

space="preserve" listing-type="equation">C.sub.cbr.sup.new =max(K*R.sub.b,C.sub.cbr.sup.delay,C.sub.cbr.sup.loss)

wherein ##EQU62## and α

=-1.15*log₁₀ (ε

₂), K is the total number of equivalent sources with a rate R_b and ##EQU63## such that the QoS requirements of all CBR connections, including the new connection, are met.

4. The multi-class connection admission control method according to claim 1 further comprising the step of:

determining a sum of the peak rates for all existing connections according to the following;

##EQU64##

26. The multi-class connection admission control method according to claim 1 further comprising the steps of:

accepting said incoming CBR connection if the additional capacity is available in a free pool of available capacity and if a total capacity allocated to a particular CBR class does not exceed a maximum capacity limit for said particular CBR class established by a network management system; and

reducing the free pool of available capacity by an amount of the additional capacity added to the current capacity for said particular CBR class.

5. A multi-class connection admission control method for admitting a new constant bit rate (CBR) connection to an ATM switch supporting a plurality of generic traffic classes, said switch having a plurality of inputs and a plurality of outputs;

a plurality of input buffers, connected to said input ports and said output ports wherein said input buffers are further divided into a plurality of buffer regions such that there is a particular buffer region associated with a particular one of said plurality of traffic classes and each one of said particular buffer regions are further divided into sub-regions, such that there is a particular sub-region within each buffer region associated with a particular input;

a free pool of buffers connected to said input buffers; and

a connection admission controller for managing said buffers and said free pool of buffers;

said method comprising;

a first step of determining an equivalent number of basic rate CBR sources admitted to the ATM switch;

a second step of determining any additional capacity that must be added to a current capacity of a particular CBR class such that quality of service (QoS) requirements for all CBR connections are met;

accepting the new connection, if the additional capacity is available in a free pool of available capacity and the total capacity allocated to the particular CBR class does not exceed a maximum capacity limit for this particular CBR class established by a network management system; and

reducing the free pool of available capacity by amount of additional capacity added to the current capacity for the particular CBR class.

6. The multi-class connection admission control method according to claim 5 wherein said additional capacity is obtained according to the following relationship:

space="preserve" listing-type="equation">j=λ

.sub.p */R.sub.b,

where λ

_p * is a peak bit rate for the new connection and R_b is the bit rate of the equivalent sources; and

K, the total number of equivalent basic rate CBR sources, including the contribution from the new connection is determined according to;

##EQU65## where n is the number of CBR connections that are already admitted by the switch and λ

_pⁱ is the peak bit rate for the CBR connection i (i=1, 2, . . . n).

7. The multi-class connection admission control method according to claim 6 wherein said additional capacity, Δ

_cbr, is determined according to the following relationship;

space="preserve" listing-type="equation">Δ

.sub.cbr =C.sub.cbr.sup.new -C.sub.cbr.sup.old,

wherein C_cbr^new is the capacity required for the particular CBR class after the new connection is accepted and C_cbr^old, is the capacity of the particular CBR class before the new connection is accepted and

space="preserve" listing-type="equation">C.sub.cbr.sup.new =max(K*R.sub.b,C.sub.cbr.sup.delay,C.sub.cbr.sup.loss)

wherein ##EQU66## and α

=-1.15*log₁₀ (ε

₂), K is the total number of equivalent sources with a rate R_b and ##EQU67## such that the QoS requirements of all CBR connections, including the new connection, are met.

8. The multi-class connection admission control method according to claim 5 further comprising the step of:

determining a sum of the peak rates for all existing connections according to the following;

##EQU68##

9. A multi-class connection admission control method for admitting a new available bit rate (ABR) connection to an ATM switch situated within a telecommunications network, said method comprising:

a first step of determining a minimum cell rate (MCR) requirement for the ABR connection;

a second step of determining, based upon the ABR connection'"'"'s MCR requirement, whether there is sufficient available bandwidth in a bandwidth free pool for the connection in a forward direction;

a third step of determining whether there is sufficient available bandwidth for resource management (RM) cell transmission for the connection in a reverse direction;

a fourth step of admitting the new connection to the telecommunications network if there is sufficient bandwidth for the connection in the forward direction and reverse direction as determined in the second and third steps, respectively, else rejecting the connection; and

a fifth step of assigning, if the connection is admitted, a peak cell rate (PCR), an initial cell rate (ICR), and a rate increase factor (RWF) for the new connection.

10. The multi-class connection admission control method according to claim 9 wherein said sufficient available bandwidth for resource management (RM) cell transmission for the connection in a reverse direction is obtained according to the following relationship:

##EQU69##

11. The multi-class connection admission control method according to claim 10 wherein said PCR is obtained according to the following relationship:

12. The multi-class connection admission control method according to claim 11 wherein said ICR is obtained according to the following relationship:

13. The multi-class connection admission control method according to claim 12 wherein said RIF is obtained according to the following relationship:

14. A multi-class connection admission control method for admitting a new variable bit rate (VBR) connection to an ATM switch situated within a telecommunications network, said method comprising:

a first step of determining UPG descriptors and QoS requirements for the VBR connection wherein said QoS requirements include GLR and GDV;

a second step of constructing, from the UPC descriptors an on/off process for the VBR connection;

a third step of constructing, based upon the on/off process, a modified source model;

a fourth step of determining, based upon a statistical multiplexing model, any additional capacity required to support the VBR connection;

a fifth step of determining, in parallel with above third and fourth steps and based upon a buffered lossless multiplexing model, any additional capacity required to support the VBR connection; and

a sixth step of determining, based upon the additional capacity requirements determined in steps four and five, additional capacity required to support the VBR connection.

15. The multi-class connection admission control method according to claim 14 wherein said UPC descriptors are λ

_p, λ

_s, B_s, where λ

_p ≧

λ

_s, and B_s ≧

1 and the QoS requirements are cell loss ratio CLR and cell delay variation CDV which are determined according to the following relationships;

space="preserve" listing-type="equation">CLR<

ε

.sub.1, and

space="preserve" listing-type="equation">Prob[CDV>

t.sub.max ]<

ε

.sub.2.

16. The multi-class connection admission control policy according to claim 15 wherein said on/off process is an equivalent source traffic model determined according to:

##EQU70##

17. The multi-class connection admission control policy according to claim 16 wherein said modified source model is determined according to the following:

18. The multi-class connection admission control policy according to claim 17 wherein said fourth step determination of additional capacity is determined according to:

19. The multi-class connection admission control policy according to claim 18 wherein said fifth step determination of additional capacity is determined according to:

20. The multi-class connection admission control policy according to claim 19 wherein said sixth step determination of the additional capacity is determined according to:

space="preserve" listing-type="equation">Δ

.sub.vbr =min[δ

.sub.1, δ

.sub.2 ], where

δ

₁ =C_vbr^new -C_vbr^old, is the additional capacity determined in step four and δ

₂ =C_vbr^new -C_vbr^old is the additional capacity determined in step five.

21. A multi-class connection admission control method for admitting a new, measurement based, variable bit rate (VBR) connection to an ATM switch situated within a telecommunications network, said method comprising:

a first step of determining UPC descriptors and QoS requirements for the VBR connection wherein said QoS requirements include CLR and CDV;

a second step of constructing, from the UPC descriptors an on/off process for the VBR connection;

a third step of constructing, based upon the on/off process, a modified source model;

a fourth step of determining, based upon a statistical multiplexing model, any additional capacity required to support the VBR connection;

a fifth step of determining, in parallel with above third and fourth steps and based upon a buffered lossless multiplexing model, any additional capacity required to support the VBR connection;

a sixth step of determining, based upon the additional capacity requirements determined in steps four and five, additional capacity required to support the VBR connection; and

a seventh step of measuring, once the connection is admitted, a current cell arrival rate and cell loss ratio periodically and updating a parameter at that period according to the following relationship;

##EQU71## where A₁, A₂, . . . , A_n, A_n+1, . . . , are the measurement periods, CLRⁿ_mes is a cell loss ratio measured during period A_n, k_n is a smoothing parameter chosen after period A_n, and CLR_tar is a QoS required by the connections and ε

<

1, α

, /3>

1.

22. The multi-class connection admission control method according to claim 21 further comprising:

an eighth step of updating a measured mean and variance of the cell arrival rate after a certain number of measurement periods.

23. The multi-class connection admission control method according to claim 22 further comprising:

a ninth step of determining a new mean and variance of the aggregate arrival process due to all existing VBR connections according to the following relationships;

space="preserve" listing-type="equation">M.sub.new =kM.sub.old (cac)+(1-k)M.sub.old (mes)+λ

.sub.s *, σ

.sub.new.sup.2 =(1-k)σ

.sub.old.sup.2 (mes)+KT.sub.old.sup.2 (cac)(λ

.sub.H *-λ

.sub.L *).sup.2 P.sub.on *),

where 0≦

k≦

1, M_old (cac) and σ

_old² (cac) are the mean and variance in the aggregate arrival rate of existing connections as computed from the declared UPC parameters, M_old (mes) and σ

_old² (mes) are the mean and variance in the aggregate arrival rate of existing connections obtained from measurements, and k is a smoothing parameter.

24. The multi-class connection admission control method according to claim 23 further comprising:

a tenth step of determining a required bandwidth for the VBR connection according to the following relationships;

##EQU72##

25. The multi-class connection admission control policy according to claim 24 further comprising the step of:

Admitting the VBR connection, if a sufficient bandwidth is available in a bandwidth free pool and ##EQU73##