Method and apparatus for a dynamic call admission control algorithm

• US 6,771,648 B1
• Filed: 03/31/1999
• Issued: 08/03/2004
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Marconi Communications, Inc. (Marconi Holdings Company Limited)
• Inventors: Kim, Hyong S., Basak, Debashis
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Phan, Tri H.
• Application Number:
  US09/282,980
• Time in Patent Office: 1,952 Days
• Field of Search: 370/360, 370/229-236, 370/395.21, 370/395.41, 370/395.42, 370/395.43, 370/236.1, 370/395.1, 370/395.2, 370/410, 370/468
• US Class Current: 370/395.2
• 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/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A switch for a network. The switch includes an input port mechanism which receives traffic of connections from the network. Each connection has a priority. The switch includes an output port mechanism which sends traffic of connections to the network. The switch includes a controller which serves connections and which monitors the connections received by the input port mechanism and sent by the output port mechanism and releases connections according to a connection'"'"'s priority when a predetermined condition exists in the switch. The controller is connected to the input port mechanism and the output port mechanism. Each connection requests a specific bandwidth from the controller. A method for switching connections. The method includes the steps of monitoring traffic of connections received by a switch. Then there is the step of releasing connections from the switch according to the connection'"'"'s priority when a predetermined condition in the switch exists.

Claims

1. A switch for a network which switches traffic of connections admitted by the switch comprising:

an input port mechanism which receives traffic of connections on at least one link from the network, each connection having a priority;

an output port mechanism which sends traffic of admitted connections to the network;

a controller which serves connections, which computes a dynamic estimate of an effective bandwidth of the link, and which monitors the admitted connections received by the input port mechanism and sent by the output port mechanism and releases admitted connections according to a priority of an admitted connection when an overload condition exists in the switch, said controller connected to the input port mechanism and the output port mechanism, each connection requesting a specific bandwidth from the controller, the overload condition includes receiving more traffic on admitted connections received by the input port mechanism than the controller can process at a given time, the controller determines excess bandwidth associated with the overload condition, and the controller releases the admitted connection, for a given priority, with the closest match to the excess bandwidth, the controller releases admitted connections according to the admitted connections'"'"' traffic class, where UBR connections are released first, then ABR connections are released next, then VBR connections are released next and then CBR connections are released from the switch, the input port mechanism comprises I input ports connected to the controller, where I is an integer and greater than or equal to 1; and

wherein the output mechanism comprises O output ports connected to the controller, where O is an integer greater than or equal to 1, the controller releases the admitted connection with the lowest priority; and

a buffer mechanism connected to the output port mechanism and wherein the overload condition exists if the sum of requested bandwidths of admitted connections on an output port is greater than the output port'"'"'s bandwidth and buffer resources associated with it are being exceeded,

2. A switch as described in claim 1 wherein the controller releases admitted connections whose sum of requested bandwidths most closely matches the excess bandwidth.

3. A method for switching admitted connections comprising:

monitoring traffic of admitted connections received by a switch with a controller;

releasing admitted connections from the switch according to a priority of an admitted connection when an overload condition in the switch exists; and

taking periodic measurements with the controller at intervals of an actual aggregate measured traffic on link l on the network connected with the switch; and

admitting a new connection to the output port mechanism of the switch if

4. A method as described in claim 3 wherein the monitoring step includes the step of monitoring traffic of admitted connections received by and sent out from the switch.

5. A method as described in claim 4 wherein the releasing step includes the step of releasing admitted connections when the predetermined condition of overload exists in the switch where there is more traffic of admitted connections received by the switch than the switch can process.

6. A method as described in claim 5 wherein the releasing step includes the steps of determining, when the overload condition exists, the excess bandwidth associated with the overload condition;

choosing an admitted connection, for a given priority, with the closest match to the excess bandwidth; and

releasing the admitted connection with the closest match to the excess bandwidth.

7. A method as described in claim 6 wherein the choosing step includes the step of choosing the admitted connection with the lowest priority.

8. A method as described in claim 7 wherein the choosing step includes the step of choosing the admitted connections whose sum of requested bandwidths most closely matches the excess bandwidth.

9. A method as described in claim 8 wherein the choosing step includes the step of choosing an admitted connection according to traffic class for release, where UBR connections are released first, then ABR connections are released next, then VBR connections are released next and then CBR connections are released.

10. A switch for a network comprising:

an input port mechanism which receives traffic of connections from the network;

an output port mechanism which sends traffic of admitted connections to the network; and

a controller which provides service to traffic of admitted connections received at the input port mechanism and which are to be sent out the output port mechanism, said controller dynamically monitoring the traffic of admitted connections received by the input port mechanism and sent out the output port mechanism and adjusting the service provided to the admitted connections based on the traffic of admitted connections received by the input port mechanism and sent out the output port mechanism, said controller connected to the input port mechanism and the output port mechanism, the controller takes periodic measurements at intervals of the actual aggregate measured traffic on link l on the network connected with the switch and admits a new connection to the output port mechanism of the switch if

11. A switch for a network comprising:

an input port mechanism which receives cells of connections from the network;

an output port mechanism which sends cells of admitted connections to the network;

a buffer mechanism for storing cells, said buffer mechanism connected to the input port mechanism and the output port mechanism; and

a controller which provides service to traffic of admitted connections received at the input port mechanism and which are to be sent out the output port mechanism, said controller dynamically monitoring the change in the number of cells in the buffer mechanism and adjusting the service provided to the admitted connections based on the change in the number of cells in the buffer mechanism, said controller connected to the buffer mechanism, the controller also monitors the number of cells of admitted connections received by the input port mechanism and sent out the output port mechanism and adjusting the service provided to the admitted connections based also on the number of cells of admitted connections received by the input port mechanism and sent out the output port mechanism, the controller takes periodic measurements at intervals of an actual aggregate measured traffic on link l on the network connected with the switch and admits a new connection to the output port mechanism of the switch if

12. A switch as described in claim 11 wherein the controller updates B^int_eff during an interval if the connection B^c_eff is admitted by

13. A switch as described in claim 12 wherein B_act is based on current link utilization, variation in link utilization, buffer occupancy, and rate of change of buffer occupancy.

14. A method for switching admitted connections by a switch of a network comprising the steps of:

monitoring the traffic of admitted connections received by the switch and sent out the switch with a controller, including monitoring the change in the number of cells in a buffer mechanism of the switch;

adjusting the service provided to the admitted connections by the switch based on the traffic of admitted connections received by the switch and sent out the switch and the change in the number of cells in the buffer mechanism; and

taking periodic measurements with the controller at intervals of an actual aggregate measured traffic on link l on the network connected with the switch; and

admitting a new connection to the output port mechanism of the switch if

15. A switch for a network which switches traffic of connections admitted by the switch comprising:

an input port mechanism which receives traffic of connections on at least one link from the network, each connection having a priority;

an output port mechanism which sends traffic of admitted connections to the network; and

a controller which serves connections, which computes a dynamic estimate of an effective bandwidth of the link, and which monitors the admitted connections received by the input port mechanism and sent by the output port mechanism and releases admitted connections according to a priority of an admitted connection when a predetermined condition exists in the switch, said controller connected to the input port mechanism and the output port mechanism, each connection requesting a specific bandwidth from the controller, the controller takes periodic measurements at intervals of the actual aggregate measured traffic on link l on the network connected with the switch and admits a new connection to the output port mechanism of the switch if

 

B^c_eff+B^int_eff+B^l_act≦

B_link

where B^c_eff is the effective bandwidth of the new connection, B_inteff is the aggregate effective bandwidth of connections admitted within a current measurement interval int, B^l_act reflects the actual aggregate measured traffic on link l on the network connected with the switch determined at the beginning of the current interval, and B_link is the maximum link capacity or line rate of 1.