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

• US 6,628,670 B1
• Filed: 10/29/1999
• Issued: 09/30/2003
• Est. Priority Date: 10/29/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Villaflor, Marcel, Galand, Claude
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): Ferris, Derrick W
• Application Number:
  US09/429,796
• Time in Patent Office: 1,432 Days
• Field of Search: 370/351, 370/352, 370/353, 370/389, 370/391, 370/392, 370/400, 370/409, 370/410, 370/229, 370/230, 370/232, 370/235, 370/464, 370/465, 370/468, 370/477
• US Class Current: 370/468
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/726 Reserving resources in multiple paths to be used simultaneously by balancing the load H04L47/125
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/828 Allocation of resources per group of connections, e.g. per group of users
• CPC Class Codes: H04L 47/829 Topology based

Abstract

The present application discloses a method and system of sharing reserved bandwidth among several connections issuing from a same physical port in an origin node of a packet switching communication network comprising a plurality of nodes interconnected with transmission links. At each request for establishing a connection i from an origin node to a destination node, the dependent connection management process:

selects for connection i a routing path comprising one or a plurality of links from the origin node to the destination node:

identifies on the selected path all consecutive links starting from the origin node and shared with another connection issuing from the same physical port;

reserves on each link of these identified consecutive links an aggregate bandwidth for all connections issuing from the same physical port, said aggregate bandwidth being less than the sum of the bandwidth reserved for each connection considered individually.

Claims

1. A method of sharing reserved bandwidth among several connections issuing from a same physical port in an origin node of a packet switching communication network comprising a plurality of nodes (201 . . . 208) interconnected with transmission links (209), said method characterized in that at each request for establishing a connection i from an origin node to a destination node it involves the steps of:

selecting for connection i a routing path comprising one or a plurality of links from the origin node to the destination node;

identifying on the selected path all consecutive links starting from the origin node and shared with another connection issuing from the same physical port;

reserving on each link of said identified consecutive links an aggregate bandwidth for all connections issuing from the same physical port, said aggregate bandwidth being less than the sum of the bandwidth reserved for each connection considered individually.

2. The method as recited in claim 1, wherein the step of identifying all consecutive links comprises the further step of defining for each port:

a Dependent Connection Table DCT_p comprising for each link in the network, information required to manage the bandwidth and the dependency of connections issuing from the port;

a Path Table PT_p with the links comprised in the selected routing path of each connection issuing from the port.

3. The method as recited in claim 1, wherein the aggregate bandwidth for all connections issuing from a same port with a given access rate does not exceed said port access rate.

4. The method as recited in claim 1, wherein the bandwidth reserved for each connection i considered individually is equal to an equivalent capacity, function of:

R_i the access bit rate of said connection,

m_i the average bit rate of said connection,

b_i the average burstiness of said connection.

5. The method according to claim 4 wherein the bandwidth reserved for each connection i considered individually is equal to:

${\hat{c}}_i=f<br><br>\left(R_i,m_i,b_i,X,\mathrm{\varepsilon <br><br>}\right)=R_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{y_i-X+\sqrt{{\left[y_i-X\right]}^2+4<br><br>X<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\rho <br><br>}}_i<br><br>y_i}}{2<br><br>y_i}$

where;

X is the buffer size where packets are queued while waiting transmission on the trunk.

ε

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

y_i=ln(1/ε

)b_i(1−

p_i)R_i.

p_i=m_i/R_i.

6. The method as recited in claim 1, wherein the aggregate bandwidth on link k for all N_k connections issuing from a same physical 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.

7. The method according to claim 6 wherein

the mean bit rate of the aggregation of the N_k connections issued from port p is equal to:

$M_k=\underset{i=1}{\overset{N_k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>m_i$

the mean burst duration of the aggregation of the N_k connections issued from port p is equal to;

$B_k=\frac{\underset{i=1}{\overset{N_k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>m_i\times <br><br>b_i}{\underset{i=1}{\overset{N_k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>m_i}$

 

where

m_i is the average bit rate of connection i,

b_i is the average burstiness of connection i.

8. The method according to claim 7 wherein the aggregate bandwidth on link k for all N connections issuing from a same physical port p is equal to:

$E_k^{\left(N_k\right)}=f<br><br>\left(R,M_k,B_k,X,\mathrm{\varepsilon <br><br>}\right)=R<br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{Y_k-X+\sqrt{{\left[Y_k-X\right]}^2+4<br><br>X<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\rho <br><br>}}_k<br><br>Y_k}}{2<br><br>Y_k}$

where;

R is the port access rate,

Y_k=ln(1/ε

)B_k(1−

p_k)R, and

p_k=M_k/R.

9. The method as recited in claim 1, wherein the step of reserving on a link an aggregate bandwidth for all connections issuing from a same physical port is processed only on said identified consecutive links.

10. A system for carrying out the method according to anyone of the preceding claims.