Traffic management in packet communications networks

• US 5,289,462 A
• Filed: 08/19/1992
• Issued: 02/22/1994
• Est. Priority Date: 08/19/1992
• Status: Expired due to Term

• Current Assignee: Toshiba Global Commerce Solutions Holdings Corporation (Toshiba Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Guerin, Roch, Gun, Levent, Ahmadi, Hamid
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US07/932,440
• Time in Patent Office: 552 Days
• Field of Search: 370/79, 370/60, 370/94.1, 370/17, 370/60.1
• 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/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5637 Leaky Buckets

Abstract

In a packet communications network, the addition or deletion of a connection to the network by a user is governed by a link traffic metric which represents the effective capacity of each link in the network which participates in the packet connection route. The link metric is calculated in real-time and updated by simple vector addition or subtraction. Moreover, this link metric is also used to calculate leaky bucket parameters which govern the access of packets to the network once the connection is set up. A packet network using these link metrics and metric generation techniques provides maximum packet throughput while, at the same time, preserving grade of service guarantees.

Claims

1. A packet communications network including a plurality of switching nodes interconnected by transmission links, and in which data packets are transmitted over multilink paths between a source node and a destination node, said packet communications network comprising

means for storing, at each said node, a representation of the traffic load reserved for all connections on each transmission link terminating in said node, said representation comprising a vector including the mean of the bit rate for all of said connections, the variance of said bit rate around said mean bit rate, and the sum of the equivalent bandwidths required to carry said connections if each said connection were offered in isolation,

said equivalent bandwidth of a connection having a first value when the number of connections sharing one of said transmission links exceeds a predetermined value and having a second different value when said number of connections does not exceed said predetermined value, where said predetermined value is equal to or greater than ten.

means for initiating a new connection in said network by propagating a connection request along the route selected for that connection, said connection request including a vector representing the mean, variance and equivalent bandwidth of said new connection,

means responsive to said connection request for updating said representations of traffic load by vector addition at each of said nodes along said route.

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

means responsive to said connection request for denying said connection request when the updated representation of the traffic load on any of said transmission links exceeds the capacity of said transmission link.

3. The packet communications network according to claim 1 wherein said means for updating said representations of traffic load comprises

means for determining the value t₁ of a first variable given by

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

means utilizing said representations for determining the token rate and pool size of a leaky bucket mechanism to control the access of said packets to said network.

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

means for estimating the bandwidth required for carrying said new connection on each link of said route,

means for selecting the minimum estimated bandwidth for carrying said new connection on said links of said route as the token rate of said leaky bucket mechanism, and

means for determining the pool size of said leaky bucket mechanism to reduce the probability of delaying a packet by said leaky bucket mechanism below some preselected value.

6. The packet communications network according to claim 5 wherein said token rate is given by ##EQU16## where ##EQU17## and wherein said pool size is given by ##EQU18##

7. A method for establishing new connections in a packet communications network including a plurality of switching nodes interconnected by transmission links, and in which data packets are transmitted over multilink paths between a source node and a destination node, said method comprising the steps of

storing, at each said node, a representation of the traffic load reserved for all connections on each transmission link terminating in said node, said representation comprising a vector including the means of the bit rate for all of said connections, the variance of said bit rate around said mean bit rate, and the sum of the equivalent bandwidths required to carry said connections if each said connection were offered in isolation,

said equivalent bandwidth of a connection having a first value when the number of connections sharing one of said transmission links exceeds a predetermined value and having a second different value when said number of connections does not exceed said predetermined value, where said predetermined value is equal to or greater than ten,

initiating a new connection in said network by propagating a connection request along the route selected for that connection, said connection request including a vector representing the mean, variance and equivalent bandwidth of said new connection, and

updating, in response to said connection request, said representations of traffic load by vector addition at each of said nodes along said route.

8. The method according to claim 7 further comprising the step of denying, in response to said connection request, said connection request when the updated representation of the traffic load on any of said transmission links exceeds the capacity of said transmission link.

9. The method according to claim 7 wherein said step of updating said representations of traffic load comprises

determining the value t₁ of a first variable given by

10. The method according to claim 7 further comprising the step of

utilizing said representations for determining the token rate and pool size of a leaky bucket mechanism to control the access of said packets to said network.

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

estimating the bandwidth required for carrying said new connection on each link of said route,

selecting the minimum estimated bandwidth for carrying said new connection on said links of said route as the token rate of said leaky bucket mechanism, and

determining the pool size of said leaky bucket mechanism to reduce the probability of delaying a packet by said leaky bucket mechanism below some preselected value.

12. The method according to claim 11 wherein including the steps of

calculating said token rate γ

_j from ##EQU20## where ##EQU21## and calculating said pool size M from ##EQU22##

13. A node for a packet communications network including a plurality of switching nodes interconnected by transmission links, and in which data packets are transmitted over multilink paths between a source node and a destination node, said packet communications network node comprising

means for storing at said node a representation of the traffic load reserved for all connections on each transmission link terminating in said node, said representation comprising a vector including the mean of the bit rate for all of said connections, the variance of said bit rate around said mean bit rate, and the sum of the equivalent bandwidths required to carry said connections if each said connection were offered in isolation,

said equivalent bandwidth of a connection having a first value when the number of connections sharing one of said transmission links exceeds a predetermined value and having a second different value when said number of connections does not exceed said predetermined value, where said predetermined value is equal to or greater than ten,

means for initiating a new connection in said network by propagating a connection request from said node along the route selected for that connection, said connection request including a vector representing the mean, variance and equivalent bandwidth of said new connection, and

means in said node responsive to a connection request from other nodes in said network for updating said representation of traffic load by vector addition at said node.

14. The packet communications network node according to claim 13 further comprising

means responsive to said connection request for denying said connection request when the updated representation of the traffic load on a transmission link in said route exceeds the capacity of said transmission link.

15. The packet communications network node according to claim 13 wherein said means for updating said representations of traffic load comprises

means for determining the value t₁ of a first variable given by

16. The packet communications network node according to claim 13 further comprising

means utilizing said representations for determining the token rate and pool size of a leaky bucket mechanism to control the access of said packets to said network at said node.

17. The packet communications network node according to claim 13 further comprising

means at said node for estimating the bandwidth required for carrying said new connection on each link of said route,

means at said node for selecting the minimum estimated bandwidth for carrying said new connection on said links of said route as the token rate of said leaky bucket mechanism, and

means at said node for determining the pool size of said leaky bucket mechanism to reduce the probability of delaying a packet by said leaky bucket mechanism below some preselected value.

18. The packet communications network node according to claim 17 wherein said token rate is given by ##EQU24## where ##EQU25## and wherein said pool size is given by ##EQU26##