Method and system for selecting path according to reserved and not reserved connections in a high speed packet switching network

• US 5,940,372 A
• Filed: 07/12/1996
• Issued: 08/17/1999
• Est. Priority Date: 07/13/1995
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Bertin, Olivier, Levy-Abegnoli, Eric
• Primary Examiner(s): NGUYEN, CHAU T
• Application Number:
  US08/678,939
• Time in Patent Office: 1,131 Days
• Field of Search: 370/235, 370/238, 370/254, 370/255, 370/351, 370/389, 370/392, 370/256, 370/400, 370/428, 370/237, 370/253, 395/200.68, 395/200.69, 395/200.71
• US Class Current: 370/238
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The present invention is related to high speed packet switching networks and, more particularly, to a process for selecting an optimal path for packets transmission without bandwidth reservation in communication systems supporting both bandwidth-reserved and non-bandwidth-reserved connections. Non-reserved network connections do not have bandwidth set aside either implicitly or explicitly. The lowest delay priority is assigned to non-reserved traffic and the networks drops non-reserved packets when their buffer overflow at intermediate links. Because the data profile over the connections is bursty and non deterministic, reserved traffic does not lead to a full links utilization except on peaks. Therefore, non-reserved traffic can be transmitted when some bandwidth is available on the links. The purpose of an efficient bandwidth management is to reserve on the links as many bandwidth as possible with a guaranteed quality of service, and to use the inherent remaining bandwidth to transport traffic from the users who are just expecting a "best effort" service. The Path Selection algorithm for non-reserved connections comprises the step of weighing each transmission link with a weighing function dependent of both reserved non-reserved traffic.

Claims

1. For use in a packet switching communication network comprising a plurality of nodes interconnected with transmission links, said network carrying both reserved data traffic on connections to which network resources have been allocated and non-reserved data traffic on connections to which no network resources are allocated, a method of determining a route for non-reserved data traffic between an origin node and a destination node, said method comprising the steps of:

assigning a weight to each transmission link, said weight being directly related to both the existing allocation of resources on the link for reserved data traffic connections and the existing, actual utilization of the link for carrying both reserved and non-reserved data traffic; and

selecting an optimal path by determining the combined weights of feasible paths between the origin node and the destination node and selecting the least weight path from the set of feasible paths.

2. The method of determining a route between an origin node and a destination node, according to claim 1, wherein said step of assigning a weight is dependent of both reserved and non-reserved traffic, so that the more traffic exceeding the reservable bandwidth, the higher the weight.

3. The method of determining a route between an origin node and a destination node, according to claim 2 by assigning a weight to each transmission link comprises the step of determining a Bounded Total Traffic Weight w_BT,ij :

When both C_T,ij.sup.(1) and C_T,ij.sup.(2) are below the maximum link reservable bandwidth R_ij, the Bounded Total Traffic Weight is equal to;

##EQU10## Whenever C_T,ij.sup.(1) or C_T,ij.sup.(2) exceed the maximum link reservable bandwidth R_ij given by R_ij =rfx then C_T,ij.sup.(1) or C_T,ij.sup.(2) is replaced by the value R_ij ;

When both C_T,ij.sup.(1) and C_T,ij.sup.(2) exceed the maximum link reservable bandwidth R_ij, the Bounded Total Traffic Weight is limited to the maximum value;

##EQU11## where;

C_ij is the total bandwidth of the link between nodes i and j;

C_T,ij.sup.(1) is the bandwidth C_R,ij.sup.(1) reserved on the link between nodes i and j by all the existing reserved connections plus the average bandwidth M_NR,ij.sup.(1) (bps) used by all the existing non-reserved connections;

C_T,ij.sup.(2) is equal to the bandwidth already reserved C_T,ij.sup.(1) plus the average bandwidth m_NR,k (bps) requested by the new non-reserved connection k.

4. The method of determining a route between an origin node and a destination node according to claim 3 wherein the step of assigning a weight comprises the step of determining a Reserved Traffic Weight w_R,ij according to the expression:

##EQU12## with;

w_R,ij =1 when no bandwidth is reserved (C_R,ij =0), ##EQU13## when all reservable bandwidth is reserved (C_R,ij =R_ij);

where;

C_ij is the total bandwidth of the link between nodes i and j;

C_R,ij is the bandwidth reserved on the link between nodes i and j by all the existing reserved connections with a maximum value of R_ij.

5. The method of determining a route between an origin node and a destination node, according to claim 4, wherein said step of assigning a weight each link as a function of the traffic exceeding the reservable bandwidth comprises the step of determining an Excess Traffic Weight w_E,ij according to the equation:

##EQU14## where;

C_T,ij.sup.(2) is equal to the bandwidth C_R,ij.sup.(1) reserved on the link by all the existing reserved connections plus the average bit rate M_NR,ij.sup.(2) used by all the existing non-reserved connections and the new estimated non-reserved connection k;

space="preserve" listing-type="equation">M.sub.NR,ij.sup.(2) =M.sub.NR,ij.sup.(1) +m.sub.NR,k

R_ij is the reservable bandwidth of the link.

6. The method of determining a route between an origin node and a destination node, according to claim 5, wherein assigned weight w'"'"'_ij is the result of the product of:

the Bounded Total Traffic Weight w_BT,ij,

the Excess Traffic Weight w_E,ij, and

the Reserved Traffic Weight w_R,ij.

7. The method for determining a route between an origin node and a destination node according to claim 6, wherein said step of selecting an optimal path includes the step of minimizing the total weight over the route, or minimizing both hop count and total weight over the route.