Calculation of layered routes in a distributed manner

• US 7,096,251 B2
• Filed: 07/31/2002
• Issued: 08/22/2006
• Est. Priority Date: 01/23/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Yuksel, Murat, Perlman, Radia J., Chiu, Dah Ming, Kadansky, Miriam C.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): NGUYEN, VAN KIM T
• Application Number:
  US10/209,077
• Publication Number:
  US 20030140165A1
• Time in Patent Office: 1,483 Days
• Field of Search: 709/202, 709/238, 709/242, 709/244
• US Class Current: 709/202
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04L 45/44 Distributed routing

Abstract

A distributed system and method generate “layered routes” that reflect a layered representation of a network, which representation provides deadlock-free routes. The layered representation consists of an ordered set of layers, where each layer is a deadlock-free sub-topology of the network. In determining routes, the links used in each route are constrained to be taken from layers of non-decreasing order as the route extends from source to destination. A device that determines a better or equal cost path to a destination node with respect to its current path to that node sends a route information message to its neighbor devices. The receiver of a route information message may then accept the message and begin using the new path described by the message, or reject the message without using the new path.

Claims

1. A method for generating routes in a communication network having a plurality of nodes connected by a plurality of links, comprising:

generating an ordered set of layers, each of said layers including a subset of the links in said communication network, each of said layers associated with a layer number indicating an associated position in said ordered set of layers;

in a first node, determining an outgoing link to a destination node;

determining a layer number associated with said outgoing link to said destination node;

generating in said first node a route information message, wherein said route information message identifies said destination node and said layer number; and

sending said route information message from said first node to at least one neighbor node other than said destination node over a link that differs from said outgoing link.

2. The method of claim 1 wherein said route information message further indicates said at least one neighbor node other than said destination node.

3. The method of claim 1, wherein said route information message further indicates a source node associated with said route information message.

4. The method of claim 1, further comprising placing said route information message onto a processing queue.

5. The method of claim 1, wherein said route information message further comprises a distance value indicating a cost associated with said link to said destination node.

6. The method of claim 3, wherein said source node is a node sending said route information message.

7. The method of claim 1, further comprising:

obtaining a subsequent route information message;

determining a source node associated with said subsequent route information message;

extracting a layer number from said subsequent route information message;

determining a layer number associated with a link to said source node;

comparing said layer number associated with said link to said source node with said layer number extracted from said subsequent route information message; and

rejecting said subsequent route information message in the event that said layer number associated with said link to said source node is greater than said layer number extracted from said subsequent route information message.

8. The method of claim 7, further comprising:

in the event that said layer number associated with said link to said source node is not greater than said layer number extracted from said subsequent route information message, performing the following steps

adding a distance value from said subsequent route information message to a cost associated with said link to said source node to generate a result,

comparing said result with a current cost associated with a current route to a destination node indicated by said subsequent route information message, and in the event that said result is greater than said cost associated with said current route to said destination node indicated by said subsequent route information message, rejecting said route information message.

9. The method of claim 8, further comprising:

in the event that said result is less than said cost associated with said current route to said destination node indicated by said subsequent route information message, accepting said subsequent route information message, wherein said accepting includes

removing indication of at least one higher cost previous route to said destination node indicated by said subsequent route information message, and

storing indication of said link to said source node as an initial portion of a route to said destination node indicated by said subsequent route information message.

10. The method of claim 8, further comprising:

in the event that said result is not greater than said cost associated with said current route to said destination node indicated by said subsequent route information message, accepting said subsequent route information message, wherein said accepting includes sending a route constrain message to said source node, wherein said route constrain message includes a link layer number field indicating said link layer number associated with said link to said source node and said destination node indicated by said subsequent route information message.

11. The method of claim 8, further comprising:

in the event that said result is not greater than said cost associated with said current route to said destination node indicated by said subsequent route information message, accepting said subsequent route information message, wherein said accepting includes

generating at least one new route information message, wherein said new route information message includes indication of said destination node indicated by said subsequent route information message, a distance value equal to said result, and an indication of said layer number associated with said link to said source node, and

sending said at least one new route information message to at least one neighbor node other than said source node.

12. The method of claim 1, further comprising:

receiving a route constrain message, wherein said route constrain message indicates a destination node and a layer number;

marking at least one route to said destination node indicated by said route constrain message having a first link associated with a layer number lower than said layer number indicated by said route constrain message as unusable; and

storing indication of a source node associated with said route constrain message in an unusable list associated with route to said destination node indicated by said route constrain message having a first link associated with a layer number lower than said layer number indicated by said route constrain message.

13. The method of claim 12, further comprising:

receiving a route unconstrain message, wherein said route unconstrain message indicates said destination node;

removing said stored indication of said source node from said unusable list;

determining whether said unusable list is empty; and

responsive to a determination that said unusable list is empty, removing said marking of said at least one route to said destination node indicated by said route constrain message as unusable.

14. A system for generating routing information for devices in a communication network having a plurality of nodes connected by a plurality of links, comprising:

route generation logic operable to

generate an ordered set of layers, each of said layers including a subset of the links in said communication network, each of said layers associated with a layer number indicating an associated position in said ordered set of layers,

in a first node, determine an outgoing link to a destination node,

determine a layer number associated with said outgoing link to said destination node,

generate in said first node a route information message, wherein said route information message dentifies said destination node and said layer number; and

send said route information message from said first node to at least one neighbor node other than said destination node over a link that differs from said outgoing link.

15. The system of claim 14, wherein said route information message further indicates said at least one neighbor node other than said destination node.

16. The system of claim 14, wherein said route information message further indicates a source node associated with said route information message.

17. The system of claim 14, wherein said route generation logic is further operable to place said route information message onto a processing queue.

18. The system of claim 14, wherein said route information message further comprises a distance value indicating a cost associated with said link to said destination node.

19. The system of claim 16, wherein said source node is a node sending said route information message.

20. The system of claim 14, wherein said route generation logic is further operable to:

obtain a subsequent route information message;

determine a source node associated with said subsequent route information message;

extract a layer number from said subsequent route information message;

determine a layer number associated with a link to said source node;

compare said layer number associated with said link to said source node with said layer number extracted from said subsequent route information message; and

reject said subsequent route information message in the event that said layer number associated with said link to said source node is greater than said layer number extracted from said subsequent route information message.

21. The system of claim 20, wherein said route generation logic is further operable, in the event that said layer number associated with said link to said source node is not greater than said layer number extracted from said subsequent route information message, perform the following steps:

add a distance value from said subsequent route information message to a cost associated with said link to said source node to generate a result;

compare said result with a current cost associated with a current route to a destination node indicated by said subsequent route information message; and

in the event that said result is greater than said cost associated with said current route to said destination node indicated by said subsequent route information message, reject said route information message.

22. The system of claim 21, wherein said route generation logic is further operable, in the event that said result is less than said cost associated with said current route to said destination node indicated by said subsequent route information message, to accept said subsequent route information message by performing the following steps:

removing indication of at least one higher cost previous route to said destination node indicated by said subsequent route information message, and

storing indication of said link to said source node as an initial portion of a route to said destination node indicated by said subsequent route information message.

23. The system of claim 21, wherein said route generation is further operable, in the event that said result is not greater than said cost associated with said current route to said destination node indicated by said subsequent route information message, to accept said subsequent route information message by sending a route constrain message to said source node, wherein said route constrain message includes a link layer number field indicating said link layer number associated with said link to said source node and said destination node indicated by said subsequent route information message.

24. The system of claim 21, wherein said route generation logic is further operable, in the event that said result is not greater than said cost associated with said current route to said destination node indicated by said subsequent route information message, to accept said subsequent route information message by performing the following steps:

generating at least one new route information message, wherein said new route information message includes indication of said destination node indicated by said subsequent route information message, a distance value equal to said result, and an indication of said layer number associated with said link to said source node, and

sending said at least one new route information message to at least one neighbor node other than said source node.

25. The system of claim 14, wherein said route generation logic is further operable to:

receive a route constrain message, wherein said route constrain message indicates a destination node and a layer number;

mark at least one route to said destination node indicated by said route constrain message having a first link associated with a layer number lower than said layer number indicated by said route constrain message as unusable; and

store indication of a source node associated with said route constrain message in an unusable list associated with route to said destination node indicated by said route constrain message having a first link associated with a layer number lower than said layer number indicated by said route constrain message.

26. The system of claim 25, wherein said route generation logic is further operable to:

receive a route unconstrain message, wherein said route unconstrain message indicates said destination node;

remove said stored indication of said source node from said unusable list;

determine whether said unusable list is empty; and

responsive to a determination that said unusable list is empty, remove said marking of said at least one route to said destination node indicated by said route constrain message as unusable.

27. A system for generating routes in a communication network having a plurality of nodes connected by a plurality of links, comprising:

means for generating an ordered set of layers, each of said layers including a subset of the links in said communication network, each of said layers associated with a layer number indicating an associated position in said ordered set of layers;

in a first node, means for determining an outgoing link to a destination node;

means for determining a layer number associated with said outgoing link to said destination node;

means for generating in said first node a route information message, wherein said route information message identifies said destination node and said layer number; and

means for sending said route information message from said first node to at least one neighbor node other than said destination node over a link that differs from said outgoing link.

28. A computer program product including a computer readable medium, said computer readable medium having a computer program stored thereon, said computer program for generating routing information in a communication network having a plurality of nodes connected by a plurality of links, said computer program comprising:

program code for generating an ordered set of layers, each of said layers including a subset of the links in said communication network, each of said layers associated with a layer number indicating an associated position in said ordered set of layers;

program code, operable in a first node, for determining an outgoing link to a destination node;

program code for determining a layer number associated with said outgoing link to said destination node;

program code for generating in said first node a route information message, wherein said route information message identifies said destination node and said layer number; and

program code for sending said route information message from said first node to at least one neighbor node other than said destination node over a link that differs from said outgoing link.