Method and system for connection admission control

• US 6,459,681 B1
• Filed: 11/13/1998
• Issued: 10/01/2002
• Est. Priority Date: 11/13/1998
• Status: Expired due to Fees

• Current Assignee: Sprint Communications Company LP (Deutsche Telekom AG)
• Original Assignee: Sprint Communications Company LP (Deutsche Telekom AG)
• Inventors: Oliva, Stephen Arthur
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): SPAFFORD, TIMOTHY J
• Application Number:
  US09/192,034
• Time in Patent Office: 1,418 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/395, 370/396, 370/397, 370/468
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5629 Admission control
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/765 triggered by the end-points
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data

Abstract

A method and system for Connection Admission Control (CAC) in a communications network, such as an ATM formatted B-ISDN network, is provided. Using end-to-end virtual path structures and class-of-service separation, various network virtual connections may be administered using a connection server based on a weighted round robin or similar connection-serving algorithm. Network users aware of the network structure and the means by which queue lengths are determined may easily calculate a Sustainable Cell Rate (SCR) for the traffic they wish to introduce into the network path for transmission to a given destination. The user declared SCR, in addition to other user declared traffic parameters, determines the queue lengths allocated in the network switches, such that a required level of Quality of Service is maintained. A measurement of certain types of transmitted cells in a virtual path, such as idle, unassigned, or low-priority cells, is made at any single point along the virtual path, such as at the source switch. This measurement of cells that may be considered to be “empty”, i.e., available for use by high-priority cells, is used as the basis for a determination of the allowable connections that can be admitted to a virtual path. A relationship between the mean number of “empty” cells per scheduled cycle of the connection server and the cell rate bandwidth in cells-per-second that may be allowed to enter a virtual path that is already considered to be “full”, based on the sum of the sustainable cell rates of its existing component connections, is used as the basis of CAC. Virtual connections may be admitted to a “full” virtual path if the cell rate of the requested connection is less than the allowable cell rate statistically determined from the mean number of “empty” cell timeslots in the path available for use by high-priority cells.

Claims

1. A method for connection admission control in a communication network, the method comprising the steps of:

(a) establishing a virtual path associated with at least one virtual connection from a source switch to a destination switch;

(b) scheduling cells associated with the at least one virtual connection into the virtual path;

(c) measuring a number of empty cell time slots in the virtual path; and

(d) determining an allowable bandwidth as a function of the number of empty cell time slots;

(e) admitting to the virtual path an additional virtual connection associated with an additional connection bandwidth that is less than or equal to the allowable bandwidth.

2. The method of claim 1 wherein step (a) comprises establishing the virtual path for variable and constant bit rate data, the virtual path separate from a path for unspecified and available bit rate data.

3. The method of claim 1 wherein step (a) comprises establishing an end-to-end virtual path.

4. The method of claim 1 wherein step (b) comprises weighted round robin scheduling.

5. The method of claim 1 wherein step (c) comprises measuring the number of unused and low priority cell time slots.

6. The method of claim 1 wherein step (c) comprises measuring the number at a virtual connection server associated with the at least one virtual connections and a source of the virtual path.

7. The method of claim 4 wherein:

step (c) comprises measuring the number during a plurality of weighted round robin cycles; and

step (d) comprises statistically determining the allowable bandwidth.

8. The Method of claim 7 wherein a number of the plurality of weighted round robin cycles is a function of traffic descriptions and statistical evaluation of the mean number of empty cell time slots.

9. The method of claim 1 wherein step (e) comprises admitting the additional connection as a function of the allowable bandwidth and user parameters.

10. The method of claim 1 wherein step (d) comprises determining the allowable bandwidth associated with the number of empty cell time slots using parameter estimation.

11. The method of claim 2 further comprising steps:

(f) determining the additional connection bandwidth as a function of a sustainable cell rate for variable bit rate data and as a function of a peak cell rate for constant bit rate data;

(g) determining a virtual path available bandwidth as a function of a virtual path bandwidth, a sum of sustainable cell rates for each of the at least one virtual connection associated with variable bit rate data and a sum of peak cell rates for each of the at least one virtual connection associated with constant bit rate data; and

(h) determining that the additional connection bandwidth is less than the virtual path available bandwidth.

12. The method of claim 11 further comprising step (i) of simultaneously solving for the sustainable cell rate and a maximum queue length.

13. The method of claim 1 further comprising step (f) of policing each of the at least one virtual connection with a generic cell rate algorithm.

14. A system for connection admission control in a communications network, the system comprising:

at least a source switch and a destination switch comprising a virtual path associated with a plurality of virtual connections to the source switch;

a switch server for scheduling cells associated with the plurality of virtual connections into the virtual path;

a processor for measuring a number of empty cell timeslots in the virtual path and determining an allowable bandwidth as a function of the number; and

a plurality of queues operatively connected to the first source switch server and each of the plurality of virtual connections;

wherein the switch server is operable to admit to the virtual path an additional virtual connection associated with an additional connection bandwidth that is less than the allowable bandwidth.

15. The system of claim 14 wherein the virtual path comprises variable and constant bit rate data, the virtual path separate from a path for unspecified and available bit rate data.

16. The system of claim 14 wherein the switch server schedules cells from the plurality of queues with weighted round robin scheduling.

17. The system of claim 14 wherein the processor measures the allowable bandwidth as a function of idle and low priority cells.

18. The system of claim 14 wherein the processor and switch server comprise a same virtual connection server operatively connected to the plurality of queues and a source of the virtual path.

19. The system of claim 16 wherein the processor is operable to statistically determine the allowable bandwidth as a function of the number measured in each of a plurality of weighted round robin cycles.

20. The system of claim 14 wherein the switch server is operable to admit the additional connection associated with the additional connection bandwidth that is less than a fraction of the allowable bandwidth.

21. The system of claim 15 wherein the switch server is operable to determine the additional connection bandwidth as a function of a sustainable cell rate for variable bit rate data and as a function of a peak cell rate for constant bit rate data, to determine a virtual path available bandwidth as a function of a virtual path bandwidth, a sum of sustainable cell rates for each of the plurality of virtual connections associated with variable bit rate data and a sum of peak cell rates for each of the plurality of virtual connections associated with constant bit rate data, and to determine that the additional connection bandwidth is less than the virtual path available bandwidth.

22. The system of claim 14 further comprising a policing processor for each of the plurality of queues, each policing processor operable to police each of the plurality of virtual connections with a generic cell rate algorithm.