Traffic management in packet communications networks

• US 5,434,848 A
• Filed: 07/28/1994
• Issued: 07/18/1995
• Est. Priority Date: 07/28/1994
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gun, Levent, Chimento, Philip F. Jr., Kulkarni, Vidyadhar G.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Blum, Russell W.
• Application Number:
  US08/281,947
• Time in Patent Office: 355 Days
• Field of Search: 370/17, 370/60, 370/60.1, 370/79, 370/85.6, 370/94.1, 370/94.2
• 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/5637 Leaky Buckets
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

A packet communications network is adapted for efficiently handling of multi-priority traffic (such as multi-media traffic) by defining an access algorithm that not only ensures the requested loss probabilities for both priorities of traffic, but also optimizes the bandwidth required to carry both priority classes. A buffer having a properly sized occupancy threshold admits high priority traffic if there is room in the buffer, but admits lower priority traffic only if the buffer occupancy is below the occupancy threshold. The resulting consolidated multi-priority traffic can then be characterized by an effective bandwidth which increases the packet network capacity substantially. The multi-priority access mechanisms require little or no changes in the prior art access mechanisms and utilize pre-existing leaky bucket, route selection and link metric mechanisms of the prior art.

Claims

1. A packet communications network comprising

a plurality of switching nodes interconnected by a larger plurality of transmission links,

at least one source of traffic connected to one of said nodes and producing data packets having differing quality of service requirements,

a data buffer in said one of said nodes,

means for accepting data packets into said network with a first quality of service requirement only if the occupancy of said data buffer is less than a pre-defined threshold defined for said first quality of service requirement;

means for characterizing said traffic from said source by an effective bandwidth which simultaneously satisfies said quality of service requirements for all of said packets having different quality of service requirements,

means for reserving a connection through said network for said traffic having a bandwidth equal to said effective bandwidth;

means for transmitting the combined data stream from said data buffer on said connection through said network; and

means for selecting said pre-defined threshold such that the bandwidth required to meet all of said quality of service requirements is minimized.

2. The packet communications network according to claim 1 further comprising

means for minimizing said effective bandwidth.

3. The packet communications network according to claim 1 further comprising

means for generating a traffic vector including said effective bandwidth and the mean and variance of said traffic from said at least one source;

and

means for utilizing said traffic vector for reserving said connection.

4. The packet communications network according to claim 3 further comprising

means for adding said traffic vector to the link traffic vector for each link in said connection when said connection is set up;

and

means for subtracting said traffic vector from the link traffic vector for each link in said connection when said connection is taken down.

5. The packet communications network according to claim 2 further comprising

means for determining the effective bandwidth c₁ for one of said data packets having a first quality of service requirement in accordance with the relationship ##EQU33## λ

₀ is the rate at which a second different quality of service data packets are produced;

λ

₁ is the rate at which said first quality of service data packets are produced;

B₁ is said pre-defined threshold;

ε

₁ is the desired probability of loss of said first quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming an exp(α

) exponential distribution of said times;

β

is the average amount of time said source of traffic stays on, assuming an exp(β

) exponential distribution of said times;

means for determining the effective bandwidth c₀ for data packets having said second quality of service requirement, where c₀ is the maximum real root of the cubic equation ##EQU34## where ε

₀ is the probability of loss of packets with said second quality of service requirements;

B₀ is the size of said data buffer; and

means for utilizing the maximum of c₁ and c₀ as said effective bandwidth.

6. The packet communications network according to claim 1 further comprising

binary searching means for determining the size of said pre-determined threshold, said binary search means comprising

means for initilizing the upper and lower bounds on said threshold at the size B₀ of said data buffer and zero;

means for determining the average B of said upper and lower bounds on said threshold;

means for determining a temporary variable T₁ according to the formula ##EQU35## λ

₀ is the rate at which a second quality of service data packets are produced;

λ

₁ is the rate at which said first quality of service data packets are produced;

ε

₁ is the desired probability of loss of said first quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming and exp(α

) exponential distribution of said times;

β

is the average amount of time said source of traffic stays off, assuming an exp(β

) exponential distribution of said times;

means for determining a second temporary variable T₂ according to the formula ##EQU36## λ

₀ is the rate at which said second quality of service data packets are produced;

ε

₀ is the desired probability of loss of said second quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming an exp(α

) exponential distribution of said times;

β

is the average amount of time said source of traffic stays on, assuming an exp(β

) exponential distribution of said times;

means for utilizing said average value as said threshold value when the difference between said temporary variables T₁ and T₂ is less than a pre-selected error value;

means for setting said lower value of said threshold at said average value when said first temporary variable T₁ is greater than said second temporary variable T₂ and said difference is not less than said pre-selected error value;

means for setting said upper value of said threshold at said average value when said first temporary variable T₁ is not greater than said second temporary variable T₂ and said difference is not less than said pre-selected error value; and

means for re-determining said average B of said upper and lower bounds, for re-comparing said first and second temporary variables T₁ and T₂, and for readjusting said upper or lower bounds when said difference is not less than said pre-selected error value.

7. A method for operating a packet communications network comprising the steps of

interconnecting a plurality of switching nodes by a larger plurality of transmission links,

connecting at least one source of traffic to one of said nodes, said source producing data packets having differing quality of service requirements,

admitting data packets with a first quality of service requirement to a data buffer only if the occupancy of said data buffer is less than a pre-defined threshold defined for said given quality of service requirement;

characterizing said traffic from said source by an effective bandwidth which simultaneously satisfies said quality of service requirements for said packets having different quality of service requirements,

reserving a connection through said network for said traffic having a bandwidth equal to said effective bandwidth;

transmitting the data stream from said data buffer on said connection through said network; and

selecting said pre-defined threshold such that the bandwidths required to meet all of said quality of service requirements individually are equal to each other.

8. The method according to claim 7 further comprising the step of minimizing said effective bandwidth.

9. The method according to claim 7 further comprising the steps of

generating a traffic vector including said effective bandwidth and the mean and variance of said traffic from said at least one source;

and

utilizing said traffic vector for reserving said connection.

10. The method according to claim 9 further comprising the steps of

adding said traffic vector to the link traffic vector for each link in said connection when said connection is set up;

and

subtracting said traffic vector from the link traffic vector for each link in said connection when said connection is taken down.

11. The method according to claim 8 further comprising the steps of

determining the effective bandwidth c₁ for one of said data sources having a first quality of service requirement in accordance with the relationship ##EQU37## λ

₀ is the rate at which a second different quality of service data packets are produced;

λ

₁ is the rate at which said first quality of service data packets are produced;

B₁ is said pre-defined threshold;

ε

₁ is the desired probability of loss of said first quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming an exp(α

) exponential distribution of said times;

β

is the average amount of time said source of traffic stays on, assuming an exp(β

) exponential distribution of said times;

determining the effective bandwidth c₀ for another of said data packets having a second quality of service requirement, where c₀ is the maximum real root of the cubic equation ##EQU38## where ε

₀ is the probability of loss of packets of said second quality of service requirements;

B₀ is the size of said data buffer; and

means for utilizing the maximum of c₁ and c₀ as said effective bandwidth.

12. The method according to claim 8 further comprising the steps of

utilizing binary searching means for said step of determining the size of said pre-determined threshold, said step of utilizing binary search means comprising the steps of

initializing the upper and lower bounds on said threshold at the size B₀ of said data buffer and zero;

determining the average B of said upper and lower bounds on said threshold;

determining a temporary variable T₁ according to the formula ##EQU39## λ

₀ is the rate at which a second quality of service data packets are produced;

λ

₁ is the rate at which said first quality of service data packets are produced;

ε

₁ is the desired probability of loss of said first quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming an exp(α

) exponential distribution of said times;

β

is the average amount of time said source of traffic stays on, assuming an exp(β

) exponential distribution of said times;

determining a second temporary variable T₂ according to the formula ##EQU40## λ

₀ is the rate at which said second quality of service data packets are produced;

ε

₀ is the desired probability of loss of said second quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming an exp(α

) exponential distribution of said times;

β

is the average amount of time said source of traffic stays on, assuming an exp(β

) exponential distribution of said times;

utilizing said average value as said threshold value when the difference between said temporary variables T₁ and T₂ is less than a pre-selected error value;

setting said lower value of said threshold at said average value when said first temporary variable T₁ is greater than said second temporary variable T₂ and said difference is not less than said pre-selected error value;

setting said upper value of said threshold at said average value when said first temporary variable T₁ is not greater than said second temporary variable T₂ and said difference is not less than said pre-selected error value; and

re-determining said average B of said upper and lower bounds, re-comparing said first and second temporary variables T₁ and T₂, and readjusting said upper or lower bounds when said difference is not less than said pre-selected error value.

13. An access node in a packet communications network comprising

means for connecting at least one source of traffic to said access nodes, said source producing data packets having differing quality of service requirements,

a data buffer,

means for combining said data packets into a single data stream by selectively introducing packets from each of said source of traffic into said data buffer,

said means for combining data packets including means for admitting data packets with a first quality of service requirement only if the occupancy of said data buffer is less than a pre-defined threshold defined for said first quality of service requirement;

means for characterizing said traffic from said source by an effective bandwidth which simultaneously satisfies said quality of service requirements for said packets having different quality of service requirements,

means for transmitting a request for reserving a connection through said network for said traffic having a bandwidth equal to said effective bandwidth;

means for transmitting the combined data stream from said data buffer into said network; and

means for selecting said pre-defined threshold such that the bandwidth required to meet all of said quality of service requirements is minimized.

14. The access node according to claim 13 further comprising

means for minimizing said effective bandwidth.

15. The access node according to claim 13 further comprising

means for generating a traffic vector including said effective bandwidth and the mean and variance of said traffic from said at least one source;

and

means for utilizing said traffic vector for reserving said connection.

16. The access node according to claim 15 further comprising

means for adding said traffic vector to the link traffic vector for each link in said connection when said connection is set up;

and

means for subtracting said traffic vector from the link traffic vector for each link in said connection when said connection is taken down.

17. The access node according to claim 14 further comprising

means for determining the effective bandwidth c₁ for one of said data sources having a first quality of service requirement in accordance with the relationship ##EQU41## λ

₀ is the rate at which a second different quality of service data packets are produced;

λ

₁ is the rate at which said first quality of service data packets are produced;

B₁ is said pre-defined threshold;

ε

₁ is the desired probability of loss of said first quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming an exp(α

) exponential distribution of said times; and

β

is the average amount of time and source of traffic stays on, assuming an exp(β

) exponential distribution of said times;

means for determining the effective bandwidth c₀ for another of said data packets having a second quality of service requirement, where c₀ is the maximum real root of the cubic equation ##EQU42## where ε

₀ is the probability of loss of packets of said second quality of service requirements;

B₀ is the size of said data buffer; and

means for utilizing the maximum of c₁ and c₀ as said effective bandwidth.

18. The packet communications network according to claim 13 further comprising

binary searching means for determining the size of said pre-determined threshold, said binary search means comprising

means for initializing the upper and lower bounds on said threshold at the size B₀ of said data buffer and zero;

means for determining the average B of said upper and lower bounds on said threshold;

means for determining a temporary variable T₁ according to the formula ##EQU43## λ

₀ is the rate at which a second quality of service data packets are produced;

λ

₁ is the rate at which said first quality of service data packets are produced;

ε

₁ is the desired probability of loss of said first quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming an exp(α

) exponential distribution of said times; and

β

is the average amount of time said source of traffic stays on, assuming an exp(β

) exponential distribution of said times;

means for determining a second temporary variable T₂ according to the formula ##EQU44## λ

₀ is the rate at which said second quality of service data packets are produced;

ε

₀ is the desired probability of loss of said second quality of service data packets;

α

is the average amount of time said source of traffic stays off, assuming an exp(α

) exponential distribution of said times; and

β

is the average amount of time said source of traffic stays on, assuming an exp(β

) exponential distribution of said times;

means for utilizing said average value as said threshold value when the difference between said temporary variables T₁ and T₂ is less than a pre-selected error value;

means for setting said lower value of said threshold at said average value when said first temporary variable T₁ is greater than said second temporary variable T₂ and said difference is not less than said pre-selected error value;

means for setting said upper value of said threshold at said average value when said first temporary variable T₁ is not greater than said second temporary variable T₂ and said difference is not less than said pre-selected error value; and

means for re-determining said average B of said upper and lower bounds, for re-comparing said first and second temporary variables T₁ and T₂, and for readjusting said upper or lower bounds when said difference is not less than said pre-selected error value.