Method and apparatus for adaptive route selection in communication networks

• US 5,452,294 A
• Filed: 07/05/1994
• Issued: 09/19/1995
• Est. Priority Date: 07/05/1994
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Natarajan, Kadathur S.
• Primary Examiner(s): Safourek, Benedict V.
• Application Number:
  US08/270,976
• Time in Patent Office: 441 Days
• Field of Search: 370/13, 370/16, 370/54, 370/60, 340/825.01, 340/826, 340/827, 379/113, 379/220, 379/221
• US Class Current: 370/351
• 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 45/22 Alternate routing

Abstract

An apparatus and method for adaptive route selection between a source and a destination node where multiple routes are available. Link state variables are monitored and updated when call termination requests or call arrival requests are received. When a call arrival request is received, a list of potential routes between the source and destination nodes is determined. A best route is selected by evaluating the link states for each potential route. A call is attempted on the best route and if the attempt is not successful, a call is attempted using the next best route and so on.

Claims

1. In a communication system, a method for establishing a communication path over a route between a source node and a destination node that is non-adjacent to the source node, wherein the route comprises a series of nodes connected by communication links through which information may be transferred from the source node to the destination node, wherein the communication system has one or more route selection controllers and multiple nodes that are capable of establishing the communication links with adjacent nodes, the method performed by a route selection controller comprising steps of:

a. updating link state variables when call termination requests and call arrival requests are received, wherein the link state variables describe numbers of calls being supported by the communication links, and the call termination requests and the call arrival requests indicate that the numbers of calls are changing;

aa. receiving a call arrival request which indicates that the source node wishes to establish the communication path between the source node and the destination node;

b. based on the call arrival request, establishing a route list of one or more potential routes between the source node and the destination node, wherein each of the potential routes comprises a set of the communication links;

c. determining a best route from the route list based on the link state variables for the set of communication links comprising each of the potential routes; and

d. making an attempt to establish the communication path between the source node and the destination node along the best route.

2. The method as claimed in claim 1 wherein step (a) comprises a step of updating the link state variables based on received telemetry from the multiple nodes that describe current link state variables.

3. The method as claimed in claim 1 wherein the link state variables comprise a busy counter, and step (a) comprises a step of updating the link state variables by incrementing the busy counter when a new communication path is requested and decrementing the busy counter when an existing communication path is terminated.

4. The method as claimed in claim 1 wherein step (b) comprises a step of establishing the route list based on a predefined set of routes between the source node and the destination node.

5. The method as claimed in claim 1 wherein step (b) comprises steps of:

b.1. generating a list of the potential routes between the source node and the destination node; and

b.2. establishing the route list as a subset of the list of the potential routes.

6. The method as claimed in claim 1 wherein step (c) comprises steps of:

c.1. identifying a list of links for each of the potential routes in the route list;

c.2. extracting the link state variables for the communication links in the list of links for each of the potential routes;

c.3. determining linking probabilities for the communication links in the list of links for each of the potential routes, wherein a linking probability equals one minus a current ratio of blocked call attempts to total call attempts for a link;

c.4. computing route probabilities for the potential routes by multiplying the linking probabilities for each of the potential routes; and

c.5. identifying the best route as the route that has a highest route probability.

7. The method as claimed in claim 1 wherein step (c) comprises steps of:

c.1. determining link residual capacities of the communication links for the potential routes in the route list based on the link state variables, wherein the link residual capacities describe quantities of available resources on each of the communication links;

c.2. determining mute bottleneck values for the potential routes based on the link residual capacities for each of the potential routes, wherein a route bottleneck value is a smallest link residual capacity currently along a potential route; and

c.3. identifying the best route as the potential route with a highest route bottleneck value.

8. The method as claimed in claim 7 wherein step (c.3) comprises steps of:

c.3.1. creating a rearranged route list where the potential routes are arranged such that a highest sequenced route is the route with the highest route bottleneck value and a lowest sequenced route is the route with a lowest route bottleneck value; and

c.3.2. identifying the best route as the highest sequenced route.

9. A method as claimed in claim 1 further comprising the steps of:

e. determining whether the attempt to establish the communication path is successful;

f. when the attempt is not successful, determining whether further attempts have been made on all the potential routes on the route list;

g. when the further attempts have been made on all the potential routes, ceasing any attempt to establish the communication path; and

h. when the further attempts have not been made on all the potential routes, making the attempt to establish the communication path on a next best route and, repeating steps e-h.

10. In a communication system, a method for establishing a communication path over a route between a source node and a destination node that is non-adjacent to the source node, wherein the route comprises a series of nodes connected by communication links through which information may be transferred from the source node to the destination node, wherein the communication system has one or more route selection controllers and multiple nodes that are capable of establishing the communication links with adjacent nodes, the method performed by a route selection controller comprising steps of:

a. receiving a request to establish the communication path between the source node and the destination node;

b. establishing a route list of one or more potential routes between the source node and the destination node as a result of the request;

c. identifying a list of links for the potential routes in the route list;

d. extracting link state variables for the communication links in the list of links, wherein the link state variables are based on call requests received by the nodes and the link state variables describe quantities of calls being handled on the communication links;

e. determining linking probabilities for the communication links in the list of links based on the link state variables, wherein a linking probability equals one minus a current ratio of blocked call attempts to total call attempts for a link;

f. computing mute probabilities for the potential routes by multiplying the linking probabilities for communication links in the potential routes;

g. identifying the best route as the potential route that has a highest route probability; and

h. making an attempt to establish the communication path between the source node and the destination node along the best route.

11. The method as claimed in claim 10 wherein step (b) comprises a step of establishing the route list where the route list is predetermined.

12. The method as claimed in claim 10 wherein step (b) comprises a step of utilizing one or more route selection criteria in establishing the route list.

13. The method as claimed in claim 10 further comprising steps of:

i. determining whether the attempt to establish the communication path is successful;

j. when the attempt is not successful, determining whether further attempts have been made on all the potential routes on the route list;

k. when the further attempts have been made on all the potential routes, ceasing any attempt to establish the communication path; and

l. when the further attempts have not been made on all the potential routes, making the attempt to establish the communication path on a next best route and, repeating steps i-l.

14. In a communication system, a method for establishing a communication path over a route between a source node and a destination node that is non-adjacent to the source node, wherein the route comprises a series of nodes connected by communication links through which information may be transferred from the source node to the destination node, wherein the communication system has one or more route selection controllers and multiple nodes that are capable of establishing the communication links with adjacent nodes, the method performed by a route selection controller comprising steps of:

a. receiving a request to establish the communication path between the source node and the destination node;

b. establishing a route list of one or more potential routes between the source node and the destination node as a result of the request;

c. identifying a list of links for each Of the potential routes in the route list;

d. determining link residual capacities for the communication links in the list of links for each of the potential routes based on link state variables, wherein the link residual capacities describe quantities of available resources on each of the communication links, and wherein the link state variables are based on call requests received by the nodes and the link state variables describe quantities of calls being handled on the communication links;

e. determining route bottleneck values for the potential routes based on the link residual capacities for each of the potential routes, wherein a route bottleneck value is a smallest link residual capacity currently along the route;

f. identifying a best route as the route with a highest route bottleneck value; and

g. making an attempt to establish the communication path between the source node and the destination node along the best route.

15. The method as claimed in claim 14 wherein step (b) comprises a step of establishing the route list where the route list is predetermined.

16. The method as claimed in claim 14 wherein step (b) comprises a step of utilizing one or more route selection criteria in establishing the route list.

17. The method as claimed in claim 14 wherein step (f) comprises steps of:

f.1. creating a rearranged route list where the potential routes are arranged such that a highest sequenced route is the route with the highest route bottleneck value and a lowest sequenced route is the route with a lowest route bottleneck value; and

f.2. identifying the best route as the highest sequenced route.

18. A method as claimed in claim 14 further comprising the steps of:

h. determining whether the attempt to establish the communication path is successful;

i. when the attempt is not successful, determining whether further attempts have been made on all the potential routes on the route list;

j. when the further attempts have been made on all the potential routes, ceasing any attempt to establish the communication path; and

k. when the further attempts have not been made on all the potential routes, making the attempt to establish the communication path on a next best route and, repeating steps h-k.

19. A communication system comprising multiple nodes that are capable of establishing communication links with adjacent nodes, and one or more route selection controllers, each of the route selection controllers comprising:

means for receiving a request to establish a communication path between a source node and a destination node;

means, coupled to the means for receiving the request, for establishing a route list of one or more potential routes between the source node and the destination node based on the request, identifying a list of links for each of the potential routes in the route list, extracting link state variables for the communication links in the list of links for each of the potential routes, wherein the link state variables are based on call requests received by the nodes and the link state variables describe quantities of calls being handled on the communication links, determining linking probabilities for the communication links in the list of links for each of the potential routes, wherein a linking probability equals one minus a current ratio of blocked call attempts to total call attempts for a link, computing route probabilities for the potential routes by multiplying the linking probabilities for the communication links in the potential routes, identifying a best route as the route that has a highest route probability, and attempting to establish the communication path between the source node and the destination node along the best route;

means, coupled to the means for establishing the route list, for storing the link state variables; and

means, coupled to the means for storing, for attempting call setup.

20. A communication system comprising multiple nodes that are capable of establishing communication links with adjacent nodes, and one or more route selection controllers, the route selection controllers comprising:

means for receiving a request to establish a communication path between a source node and a destination node;

means, coupled to the means for receiving the request, for establishing a route list of one or more potential routes between the source node and the destination node based on the request;

means for identifying a list of links for each of the potential routes in the route list;

means for determining link residual capacities for the communication links of the list of links for each of the potential routes based on link state variables, wherein the link residual capacities describe quantities of available resources on each of the communication links, and wherein the link state variables are based on call requests received by the nodes and the link state variables describe quantities of calls being handled on the communication links;

means for determining route bottleneck values for the potential routes based on the link residual capacities for each of the potential routes, wherein a route bottleneck value is a smallest link residual capacity currently along the route;

means for identifying a best route as the route with a highest route bottleneck value, and attempting to establish the communication path between the source node and the destination node along the best route;

means, coupled to the means for establishing the route list, for storing the link state variables; and

means, coupled to the means for storing, for attempting call setup.

21. A communication system comprising multiple nodes that are capable of establishing communication links with adjacent nodes, and one or more route selection controllers, the one or more route selection controllers comprising:

a receiver that receives a request to establish a communication path between a source node and a destination node;

a processor, coupled to the receiver, that establishes a route list of one or more potential routes between the source node and the destination node based on the request, identifies a list of links for each of the potential routes in the route list, extracts link state variables for the communication links in the list of links for each of the potential routes, wherein the link state variables are based on call requests received by the nodes and the link state variables describe quantities of calls being handled on the communication links, determines linking probabilities for the communication links in the list of links for each of the potential routes, wherein a linking probability equals one minus a current ratio of blocked call attempts to total call attempts for a link, computes route probabilities for the potential routes by multiplying the linking probabilities for the communication links in the potential routes, identifies a best route as the route that has a highest route probability, and makes an attempt to establish the communication path between the source node and the destination node along the best route;

a memory device, coupled to the processor, that stores the link state variables; and

a transmitter, coupled to the processor, that the processor uses to attempt to establish the communication path.

22. A communication system comprising multiple nodes that are capable of establishing communication links with adjacent nodes, and one or more route selection controllers, the one or more route selection controllers comprising:

a receiver that receives a request to establish a communication path between a source node and a destination node;

a processor, coupled to the receiver, that establishes a route list of one or more potential routes between the source node and the destination node based on the request, identifies a list of links for each of the potential routes in the route list, determines link residual capacities for the communication links of the list of links for each of the potential routes based on link state variables, wherein the link residual capacities describe quantities of available resources on each of the communication links, and wherein the link state variables are based on call requests received by the nodes and the link state variables describe quantifies of calls being handled on the communication links, determines route bottleneck values for the potential routes based on the link residual capacities for each of the potential routes, wherein a route bottleneck value is a smallest link residual capacity currently along the route, identifies a best route as the route with a highest route bottleneck value, and makes an attempt to establish the communication path between the source node and the destination node along the best route;

a memory device, coupled to the processor, that stores the link state variables; and

a transmitter, coupled to the processor, that the processor uses to attempt to establish the communication path.