Method and system for sharing reserved bandwidth between several dependent connections in high speed packet switching networks

• US 7,324,552 B1
• Filed: 01/21/2003
• Issued: 01/29/2008
• Est. Priority Date: 12/19/1997
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Galand, Claude, Villaflor, Marcel
• Primary Examiner(s): Duong; Frank
• Application Number:
  US10/348,301
• Time in Patent Office: 1,834 Days
• Field of Search: None
• US Class Current: 370/468
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket

Abstract

A method is given for sharing reserved bandwidth between a plurality of connections issuing from a port of a node. A connection bandwidth is determined for each connection of the plurality of connections. An aggregate bandwidth is determined for all connections of the plurality of connections issuing from the port, the aggregate bandwidth being less than a sum of the connection bandwidth for all connections. The aggregate bandwidth is compared with a maximum access rate for the port, and in the event that the aggregate bandwidth does not exceed the maximum access rate, reserving the aggregate bandwidth for the port.

Claims

1. A method for sharing reserved bandwidth between a plurality of connections issuing from a port of a node, comprising:

determining a connection bandwidth for each connection of said plurality of connections;

determining an aggregate bandwidth for all connections of said plurality of connections issuing from said port, said aggregate bandwidth less than a sum of said connection bandwidth for all connections; and

further computing an equivalent capacity for each said connection “

i”

in determining said aggregate bandwidth, where said equivalent capacity is a function of,

a. R_i the access bit rate of said connection,

b. m_i the average bit rate of said connection,

c. b_i the average burstiness of said connection,

and

comparing said aggregate bandwidth with a maximum access rate for said port, and in the event that said aggregate bandwidth does not exceed said maximum access rate, reserving said aggregate bandwidth for said port.

2. The method according to claim 1 further comprising:

computing said connection bandwidth for an individual connection as,

Ĉ

_i=f(R_i,b_i,X,ε

)

where;

X is the buffer size where packets are queued while waiting transmission on a link connected to said port;

ε

is the proportion of packets that can be lost due to the buffer overflowing;

Y_i=ln(1/ε

)b_i(1−

ρ

_i)R_i;

ρ

=m/R_i.

3. The method according to claim 2, further comprising:

computing said equivalent capacity as,

4. The method according to claim 1, further comprising:

computing the aggregate bandwidth on a link k connected to said port for all N_k connections issuing from said port p is a function of,

M_k the mean bit rate of the aggregation of the N_k connections issued from said port,

B_k the mean burst duration of the aggregation of the N_k connections issued from said port.

5. The method according to claim 4, further comprising:

calculating,

the mean bit rate of the aggregation of the N_k connections issued from port p as equal to,

6. The method according to claim 5, further comprising:

calculating said aggregate bandwidth for link k for all connections N issuing from physical port p as,

E_k^Nk=f(R,M_k,B_k,X,ε

)

where

R is the maximum access rate for the port,

Y_k=ln(1/ε

)B_k(1−

ρ

_k)R, and

ρ

_k=M_k/R.

7. The method according to claim 6, further comprising:

calculating said aggregate bandwidth as,

8. The method according to claim 1, further comprising:

processing an aggregate bandwidth for all connections issuing from a port to a trunk only if a path from the node to said trunk is common to said all connections.

9. The method according to claim 1, further comprising:

receiving a request for a new connection through said port;

establishing said new connection only if an aggregate bandwidth including said new connection is less than said maximum access rate for the port.

10. The method according to claim 1, further comprising:

determining a plurality of intermediate nodes and intermediate links for a path from said node to a destination node; and

reserving a connection in each link of said path only if for each intermediate port in said path an aggregate bandwidth including said new connection is less than a maximum access rate for said intermediate port.

11. The method according to claim 10, further comprising:

determining a plurality of said paths through said network;

choosing a selected path from said plurality of said paths in response to comparisons between an aggregate bandwidth and a maximum access rate for each port in said plurality of said paths.

12. The method according to claim 1, further comprising:

receiving control messages from other nodes in a network; and

establishing, in response to said control messages, a Dependent Connection table DCT_p for each port “

p”

of any other node from which a control message was received, the table having an entry for each link in the network, and information required to manage the bandwidth of the link.

13. The method according to claim 12, further comprising:

transmitting connection messages to other nodes of said network to manage bandwidth of ports of said other nodes.

14. The method according to claim 12, further comprising:

storing alternate paths in said node, said alternate paths from said node to said other nodes.

15. A method for sharing reserved bandwidth between a plurality of connections issuing from a port of a node, comprising:

A. receiving a request for an additional connection through said port, said port having a plurality of connections, said request having a committed information rate (CIR), connection bit rate and connection burst duration for said additional connection;

B. summing a reserved bandwidth for each present connection to compute a total present reserved bandwidth for said port;

C. summing connection mean bit rates to obtain a present aggregate connection bit rate;

D. performing a weighted sum of connection mean burst durations to obtain a present aggregate mean burst duration;

E. computing, using said aggregate connection bit rate and said aggregate mean burst duration as input parameters, a present equivalent capacity for said port;

F. repeating steps C, D, and E including said additional connection to compute an additional equivalent capacity;

G. computing, using a minimum of a Gaussian approximation and said additional equivalent capacity, a new bandwidth; and

H. establishing said additional connection if said new bandwidth is less than or equal to a total capacity for said port.

16. The method of claim 15 further comprising:

computing, from a currently reserved bandwidth on said port, said new bandwidth, and said total capacity, an updated port weight value; and

associating said updated port weight value with said port.

17. The method of claim 15 further comprising:

evaluating said Gaussian approximation as a function of said aggregate connection bit rate including said additional connection, an additional connection bit rate, a variance of said additional connection bit rate, and a packet loss probability.

18. A method for sharing reserved bandwidth between a plurality of connections issuing from a port of a node, comprising:

determining a required capacity for said plurality of network connections;

computing, from mean bit rates of said plurality of connections, a mean aggregate bit rate over said aggregation of connections;

computing, from burst durations from said plurality of connections, a mean aggregate burst duration over said plurality of connections;

computing an equivalent capacity required through said port by said plurality of connections, said equivalent capacity being a function of said mean aggregate bit rate and said mean aggregate burst duration;

computing an aggregate equivalent capacity, said aggregate equivalent capacity being a function of said equivalent capacity and said required capacity of said plurality of connections;

computing a bandwidth that would be reserved through said port after establishing said connection, said bandwidth being a minimum of a Gaussian approximation and said aggregate equivalent capacity; and

establishing said connection if said bandwidth is less than or equal to a total capacity for said port.

19. The method of claim 18 wherein said computing an equivalent capacity further comprises:

multiplying a port access rate by a solution to a quadratic equation, said solution computed through coefficients, said coefficients being “

a”

, “

b”

, and “

C”

, said “

a”

being a burst size factor, said “

b”

being the difference between a burst size factor and a packet buffer size, said “

c”

being said packet buffer size multiplied by said mean aggregate bit rate divided by said port access rate.

20. The method of claim 19 further comprising:

computing said burst size factor as a function of a packet loss probability, said mean aggregate burst duration, and said port access rate.

21. The method of claim 20 further comprising:

evaluating said Gaussian approximation as a function of said required capacity, a variance of a bit rate, and a packet loss probability.

22. The method of claim 19 further comprising:

determining if one link from a set of possible links can accommodate an additional network connection by,

computing link aggregation metrics for a link having a plurality of connections and a total capacity, said link aggregation metrics being derived through summation and averaging metrics for said plurality of connections;

computing connection metrics from characteristics of said additional network connection;

computing new aggregation metrics as functions of said link aggregation metrics and said connection metrics, said new aggregation metrics characterized by a combination of said plurality of connections and said additional network connection, said combination forming a new aggregation;

computing a bandwidth that would be reserved on said link after said additional connection is accommodated, said bandwidth being a function of said new aggregation metrics; and

comparing said bandwidth with said total capacity for said link, said link being able to accommodate said additional network connection if said bandwidth is less than or equal to said total capacity for said link.

23. The method of claim 22 further comprising:

evaluating said bandwidth as a minimum of a Gaussian approximation for said new aggregation and an equivalent capacity for said new aggregation.

24. The method of claim 22 further comprising

computing a link weight for each of said set of possible links, said link weight being a function of said total capacity, said connection metrics, and said new aggregation metrics;

associating said link weight to said link; and

choosing said one link from said set of possible links based on said link weight.

25. An apparatus comprising:

a port for maintaining a plurality of connections;

a route controller operable to,

determine a connection bandwidth for each connection of said plurality of connections;

determine an aggregate bandwidth for all connections on said port, said aggregate bandwidth less than a sum of said connection bandwidths for all connections on said port, said aggregate bandwidth determined from an equivalent capacity of each connection on said port, said equivalent capacity a function of at least an access bit rate of said connection, an average bit rate of said connection, and an average burstiness of said connection; and

compare said aggregate bandwidth with a maximum access rate for said port, and if said aggregate bandwidth does not exceed said maximum access rate, reserve said aggregate bandwidth for said port.

26. The apparatus of claim 25 wherein the route controller is further operable to receive a request for a new connection through said port and to establish said new connection only if an aggregate bandwidth including said new connection is less than said maximum access rate for the port.

27. The apparatus of claim 25 wherein the route controller is further operable to determine a plurality of paths through a network connected to the apparatus and to choose a particular path in response to comparisons of aggregate bandwidth and maximum access rate for ports in each of said plurality of paths.

28. A computer-readable media encoded with software and when the software executed operable to:

determine a connection bandwidth for each connection of a plurality of connections on a port;

determine an aggregate bandwidth for all connections on said port, said aggregate bandwidth less than a sum of said connection bandwidths for all connections on said port, said aggregate bandwidth determined from an equivalent capacity of each connection on said port, said equivalent capacity a function of at least an access bit rate of said connection, an average bit rate of said connection, and an average burstiness of said connection; and

compare said aggregate bandwidth with a maximum access rate for said port, and if said aggregate bandwidth does not exceed said maximum access rate, reserve said aggregate bandwidth for said port.

29. The computer-readable media of claim 28 further operable to receive a request for a new connection through said port and to establish said new connection only if an aggregate bandwidth including said new connection is less than said maximum access rate for the port.

30. The computer-readable media of claim 28 further operable to determine a plurality of paths through a network connected to the apparatus and to choose a particular path in response to comparisons of aggregate bandwidth and maximum access rate for ports in each of said plurality of paths.