Apparatus and method for routing a communication in a network

• US 6,044,075 A
• Filed: 08/13/1996
• Issued: 03/28/2000
• Est. Priority Date: 12/15/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Przygienda, Antoni B, Le Boudec, Jean-Yves
• Primary Examiner(s): Horabik, Michael
• Assistant Examiner(s): PHAN, MAN U
• Application Number:
  US08/669,569
• Time in Patent Office: 1,323 Days
• Field of Search: 370/354, 370/351, 370/229, 370/235, 370/234, 370/252, 370/352, 370/488, 395/200.71, 395/200.68, 395/200.69, 395/200.7, 340/825.02, 340/825.03, 340/825.5, 340/826, 340/827, 369/488
• US Class Current: 370/351
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• 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: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and apparatus creates a set of routes for use in assigning the optimum route for a communication in an ATM digital broadband communication network consists of one or more links, each link connecting one node in the network to one other node. Assignment of a route is made from a set of. Each optimum route in the set is that route offering the best possible value of an additive attribute of the network, such as signal delay, number of nodes or route cost, for a particular minimum acceptable value of a restrictive attribute of the network, such as bandwidth of the route. The calculation of the optimum route involves finding the best route with respect to the value of the additive attribute for a model or representation of the network containing only those links in the network having at least a particular value of the restrictive attribute. The network model is then further reduced to one having only links with a more limiting value of the restrictive attribute, and the optimum route for this network model is calculated. Thus a set of optimum routes is computed, each for a model of the network with successively fewer links which satisfy successively more stringent requirements on the restrictive attribute. More than one list may be used, each list ranking the links in the network in order of a different restrictive attribute. The set of optimum routes is preferably calculated prior to receipt of a request for a route.

Claims

1. An apparatus for deriving the optimum routes between a first node and other nodes in a communications system, starting from a model of the whole system and a list of the internodal links available in the system, said link list having the links ranked in order of decreasing severity of a limitation imposed by a characteristic of the link on its use, comprising:

a) means which apply to the model of the system a so-called Spanning Tree Algorithm for finding the shortest spanning tree in terms of an additive route characteristic between said first node and each of said other nodes in the system;

b) means for storing resulting routes if they are either strictly better than or not comparable to all previously stored routes, and discarding any previously stored routes which are strictly worse than said resulting routes;

c) means for eliminating the first link, and any links equivalent to it, from said link list;

d) means for removing from the model of the system the link or links removed from said link list;

e) whereby the various means specified under a)-d) above are such as to repeat their said functions in the sequence a)-d) until there are no more links left on said link list.

2. The apparatus of claim 1, wherein:

two lists of internodal links are set up, the links on each said list being ranked in order of decreasing severity of limitation imposed by a characteristic of the link on its use, the characteristic being different for each list; and

the means of features a) to d) of claim 1 repeat their functions such that when a link is eliminated from the first of the said lists and removed from the network model, the Spanning Tree Algorithm is applied repeatedly, each of these repetitions being for a network model reduced by the next link on said second link list.

3. The apparatus of claim 2, wherein there are more than two link lists, and the shortest spanning tree is calculated for all possible permutations of partially reduced link lists in the manner outlined in claim 2.

7. The apparatus of claim 1 or the method of claim 4, wherein the said characteristic of the link is a restrictive attribute of the link.

8. The apparatus of claim 1, wherein the additive route characteristic is the delay of the signal transfer within a link, the sum of the delays over the links of a route is that route'"'"'s total delay and the route with the lowest total delay is the optimum route with respect to signal delay.

9. The apparatus of claim 1, wherein the additive route characteristic is the number of nodes existing along a route, the route with the lowest total number of nodes being the optimum route.

10. The apparatus of claim 1, wherein the additive route characteristic is the cost of transfer along a route, the route with the lowest total cost being the optimum route.

4. A method for deriving the optimum routes between a first node and other nodes in a system, starting from a model of the whole system and a list of the internodal links available in the system, this link list having the links ranked in order of decreasing severity of a limitation imposed by a characteristic of the link on its use, comprising the following repeatedly executed sequence of steps:

a) applying to the model of the system a so-called Spanning Tree Algorithm for finding the shortest spanning tree in terms of an additive route characteristic between said first node and each of said other nodes in the system;

b) storing resulting routes if they are either strictly better than or not comparable to all previously stored routes, and discarding any previously stored routes which are strictly worse than said resulting routes;

c) eliminating the first link, and any links equivalent to it, from said link list;

d) removing from the model of the system the link or links removed from said link list;

e) repeating steps a)-d) until there are no more links left on said link list.

5. The method of claim 4, wherein:

two lists of internodal links are set up, the links on each said list being ranked in order of decreasing severity of limitation imposed by a characteristic of the link on its use, the characteristic being different for each list; and

steps a) to d) of claim 4 are repeated such that when a link is eliminated from the first of the said lists and removed from the network model, the Spanning Tree Algorithm is applied repeatedly, each of these repetitions being for a network model reduced by the next link on said second link list.

6. The method of claim 5, wherein there are more than two link lists, and the shortest spanning tree is calculated for all possible permutations of partially reduced link lists in the manner outlined in claim 5.

11. The method of claim 4 wherein the additive route characteristic is the delay of the signal transfer within a link, the sum of the delays over the links of a route is that route'"'"'s total delay and the route with the lowest total delay is the optimum route with respect to signal delay.

12. The method of claim 4 wherein the additive route characteristic is the number of nodes existing along a route, the route with the lowest total number of nodes being the optimum route.

13. The method of claim 4 wherein the additive route characteristic is the cost of transfer along a route, the route with the lowest total cost being the optimum route.