Method for allocating internodal link bandwidth in a packet oriented communication network to guarantee delay quality-of-service

• US 5,432,790 A
• Filed: 09/17/1993
• Issued: 07/11/1995
• Est. Priority Date: 09/17/1993
• Status: Expired due to Term

• Current Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Bhargava, Amit, Hluchyj, Michael G., Humblet, Pierre A.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/123,457
• Time in Patent Office: 662 Days
• Field of Search: 370/95.1, 370/94.1, 370/94.2, 370/60, 370/60.1, 370/95.3, 370/58.1, 370/58.2
• US Class Current: 370/412
• 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/5649 Cell delay or jitter
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags

Abstract

A device and method allocate bandwidth on internodal links in a communiation network such that worst case maximum delays and worst case average delays in a packet oriented network are guaranteed while providing statistical gains in maintaining predetermined end-to-end delay QOS objectives for different traffic types.

Claims

1. A device for allocating bandwidth on an internodal link in a communication network for guaranteeing worst case maximum delays and worst case average delays in a packet oriented network while providing statistical gains, comprising:

A) an enqueuer, operably coupled to receive packets from a switch output port, for enqueueing the packets in a queue,

B) queues, operably coupled to the enqueuer, for storing the enqueued packets,

C) a dequeuer, operably coupled to the queues and to a delay guarantee controller, for dequeuing the enqueued packets in accordance with a predetermined delay guarantee and transmitting cells from the packets on the internodal link, and

D) the delay guarantee controller, operably coupled to the dequeuer, for providing predetermined worst case maximum delays and worst case average delays while providing statistical gains in maintaining predetermined end-to-end delay Quality of Service, QOS, objectives for different traffic types.

2. The device of claim 1 wherein the delay guarantee controller provides the predetermined worst case maximum delays and worst case average delays while providing statistical gains in maintaining predetermined end-to-end delay QOS objectives for different traffic types by utilizing a method comprising the steps of:

2A) receiving a connection setup request,

2B) determining connection parameters, CP, from the connection request,

2C) determining system parameters, SP, from a current state of the system,

2D) updating real time, B1, and non-real time, B2, bandwidths for guaranteeing delays while providing statistical gains,

2E) determining whether a sum of real time and non-real time bandwidths, B1+B2, is less than a predetermined internodal link capacity, and one of;

2E1) where the sum of the real time and non-real time bandwidths, B1+B2, is less than the predetermined internodal link capacity, accepting the connection and updating the system parameters, SP, and

2E2) where the sum of the real time and non-real time bandwidths, B1+B2, is greater than or equal to the predetermined internodal link capacity, rejecting the connection.

3. The device of claim 2 where the real time and non-real time bandwidths are one of:

3A) the real time bandwidth, B1, equals a maximum of [C1,F1(CP,SP)] and the non-real time bandwidth, B2, equals C2 plus F2(CP,SP), where C1 represents the minimum bandwidth allocated to the real time traffic, C2 represents the minimum bandwidth allocated to the non-real time traffic, F1(CP, SP) and F2(CP, SP) are predetermined functions of connection parameters (CP) and system parameters (SP), and

3B) the real time bandwidth, B1, equals a maximum of {C1,F1(CP,SP)], R1/U1, C1_-- Blocking} and the non-real time bandwidth, B2, equals max {C2+F2(CP,SP)], R2/U2, C2_-- Blocking}, where C1 represents the minimum bandwidth allocated to the real time traffic, C2 represents the minimum bandwidth allocated to the non-real time traffic, F1(CP, SP) and F2(CP, SP) are predetermined functions of connection parameters (CP) and system parameters (SP), R1 is the sum of the average rates of all real time connections multiplexed on the internodal link, R2 is the sum of the average rates of all non-real time connections multiplexed on the internodal link, C1_-- Blocking and C2_-- Blocking represent preselected minimum bandwidths, and U1 and U2 represent maximum allowed utilizations of the real time and non-real time queues, respectively.

4. The device of claim 3 wherein the system parameters (SP) and the predetermined functions F1(CP, SP) and F2(CP, SP) represent at least one of:

4A) the existing connections on the internodal link,

4B) the statistics of the traffic,

4C) the queueing discipline used (if multiple queues are used within a traffic class.

5. The device of claim 4 where F2(CP, SP) is equal to K*R2, where K is a constant greater than or equal to 1.

6. A method for allocating bandwidth on internodal links in an integrated communication network for guaranteeing worst case maximum delays and worst case average delays in a packet oriented network system while providing statistical gains, comprising the steps of:

6A) receiving a connection setup request,

6B) determining connection parameters, CP, from the connection request,

6C) determining system parameters, SP, from a current state of the system,

6D) updating real time, B1, and non-real time, B2, bandwidths for guaranteeing worst case maximum delays and worst case average delays while providing statistical gains,

6E) determining whether a sum of real time and non-real time bandwidths, B1+B2, is less than a predetermined internodal link capacity, and one of;

6E1) where the sum of the real time and non-real time bandwidths, B1+B2, is less than the predetermined internodal link capacity, accepting the connection and updating the system parameters, SP, and

6E2) where the sum of the real time and non-real time bandwidths, B1+B2, is greater than or equal to the predetermined internodal link capacity, rejecting the connection.

7. The method of claim 6 where the real time and non-real time bandwidths are one of:

7A) the real time bandwidth, B1, equals a maximum of [C1,F1(CP,SP)] and the non-real time bandwidth, B2, equals C2 plus F2(CP,SP), where C1 represents the minimum bandwidth allocated to the real time traffic, C2 represents the minimum bandwidth allocated to the non-real time traffic, F1(CP, SP) and F2(CP, SP) are predetermined functions of connection parameters (CP) and system parameters (SP), and

7B) the real time bandwidth, B1, equals a maximum of {C1,F1(CP,SP)], R1/U1, C1_-- Blocking} and the non-real time bandwidth, B2, equals max {C2+F2(CP,SP)], R2/U2, C2_-- Blocking}, where C1 represents the minimum bandwidth allocated to the real time traffic, C2 represents the minimum bandwidth allocated to the non-real time traffic, F1(CP, SP) and F2(CP, SP) are predetermined functions of connection parameters (CP) and system parameters (SP), R1 is the sum of the average rates of all real time connections multiplexed on the internodal link, R2 is the sum of the average rates of all non-real time connections multiplexed on the internodal link, C1_-- Blocking and C2_-- Blocking represent preselected minimum bandwidths, and U1 and U2 represent the maximum allowed utilizations of the real time and non-real time queues, respectively.

8. The method of claim 7 wherein the system parameters (SP) and the predetermined functions F1(CP, SP) and F2(CP, SP) represent at least one of:

8A) the existing connections on the internodal link,

8B) the statistics of the traffic,

8C) the queueing discipline used (if multiple queues are used within a traffic class.

9. The method of claim 8 where F2(CP, SP) is equal to K*R2, where K is a constant greater than or equal to 1.