Computing disjoint paths for reactive routing mesh networks

• US 8,578,054 B2
• Filed: 03/07/2008
• Issued: 11/05/2013
• Est. Priority Date: 03/07/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Vasseur, Jean-Philippe, Ribiere, Vincent Jean
• Primary Examiner(s): Blair, April Y
• Application Number:
  US12/044,526
• Publication Number:
  US 20090228575A1
• Time in Patent Office: 2,069 Days
• Field of Search: 709/243, 709/203, 709/242, 370/351, 370/338, 370/225, 370/352, 370/255
• US Class Current: 709/243
• CPC Class Codes: H04L 45/128 for finding disjoint paths
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

In one embodiment, a reactive routing computer network may be partitioned into diverse logical topologies, and a source node may transmit route request (RREQ) messages toward a destination node on each logical topology. In response, the source node may receive route reply (RREP) messages indicating routes to the destination node in each logical topology. The source node may thus select a route for each logical topology to reach the destination node, accordingly. In another embodiment, if partitioned logical topologies do not produce two or more routes or as a standalone embodiment, the source node may transmit RREQ messages toward the destination node without any corresponding logical topology. The destination node receives RREQ messages, and two or more routes from the source node to the destination node may be determined (e.g., by the destination or source node) based on the received RREQ messages at the destination node and path selection criteria.

Claims

1. A method, comprising:

transmitting, from a source node, route request (RREQ) messages toward a destination node of a reactive routing computer network, each RREQ message including an indication that the RREQ message should be transmitted all the way to the destination node even when an intermediate node en-route to the destination node already has a route to the destination node;

recording, at one or more intermediate nodes, a traversed path of the RREQ messages within the RREQ messages;

receiving one or more of the RREQ messages at the destination node during a configured time period after receiving an initial RREQ message of the RREQ messages at the destination node; and

determining two or more routes from the source node to the destination node based on the received RREQ messages at the destination node and one or more path selection criteria.

2. The method as in claim 1, further comprising:

determining the two or more routes at the destination node; and

sending a route reply (RREP) message for each determined route from the destination node to the source node.

3. The method as in claim 1, further comprising:

sending a route reply (RREP) message having the received RREQ messages from the destination node to the source node; and

determining the two or more routes at the source node based on the RREQ messages of the RREP message.

4. The method as in claim 1, further comprising:

configuring the time period based on a time taken for the initial RREQ message to reach the destination node from the source node.

5. The method as in claim 1, wherein the path selection criteria are selected from a group consisting of:

a degree of diversity;

a degree of intersection;

a cost ratio;

a sum of costs;

a number of paths;

a selection of preferred nodes; and

an exclusion of non-preferred nodes.

6. The method as in claim 1, wherein the indication that the RREQ message should be transmitted all the way to the destination node even when an intermediate node en-route to the destination node already has a route to the destination node is a flag in the RREQ message.

7. A method, comprising:

logically partitioning a reactive routing computer network into two or more diverse logical topologies, wherein a differing set of nodes of the reactive routing computer network is associated with each of the logical topologies;

transmitting, from a source node, one or more route request (RREQ) messages toward a destination node on each of the logical topologies, each RREQ message having an indication of a corresponding logical topology and an indication that it should be transmitted all the way to the destination node even when an intermediate node en-route to the destination node already has a route to the destination node;

receiving, at the source node, one or more route reply (RREP) messages, each RREP message indicating a route to reach the destination node using a subset of the set of nodes associated with a corresponding logical topology; and

selecting a route for each logical topology for which a RREP message was received, to reach the destination node from the source node, based on the received one or more RREP messages.

8. The method as in claim 7, further comprising:

processing the one or more RREQ messages at one or more receiving intermediate nodes and the destination node based on the indication of the corresponding logical topology.

9. The method as in claim 8, further comprising:

receiving, at an intermediate node, a particular RREQ message of a logical topology that does not correspond to the intermediate node; and

in response, discarding the particular RREQ message.

10. The method as in claim 8, further comprising:

determining to which downstream nodes to send a particular RREQ message based on the downstream nodes belonging to a logical topology corresponding to the particular RREQ message.

11. The method as in claim 7, further comprising:

logically partitioning the network prior to transmitting the one or more RREQ messages; and

configuring the logical partitions on nodes of the network.

12. The method as in claim 7, further comprising:

logically partitioning the network by transmitting the one or more RREQ messages with a partitioning algorithm; and

determining the logical partitions on nodes of the network based on the partitioning algorithm as the one or more RREQ messages are received.

13. The method as in claim 7, wherein the logical partitioning is based on a hashing algorithm that defines nodes as corresponding to one logical topology.

14. The method as in claim 7, wherein certain nodes of the network correspond to a plurality of logical topologies.

15. The method as in claim 14, wherein one or more of the certain nodes are non-battery powered nodes.

16. The method as in claim 7, wherein the logical topology of a node is based on whether an address of the node contains a 1 or 0 at a particular bit position of the address.

17. The method as in claim 7, further comprising:

initializing the logical partitioning of the network as a comparatively larger number of diverse logical topologies;

determining whether two or more diverse routes exist from the source node to the destination node based on the comparatively larger number of diverse logical topologies; and

when two or more diverse routes do not exist, logically partitioning the network as a comparatively smaller number of diverse logical topologies to determine whether two or more diverse routes exist from the source node to the destination node based on the comparatively smaller number of diverse logical topologies.

18. The method as in claim 7, further comprising:

initializing the logical partitioning of the network as a number of diverse logical topologies;

determining whether two or more diverse routes exist from the source node to the destination node based on the number of diverse logical topologies; and

when two or more diverse routes do not exist;

transmitting, from the source node, one or more second RREQ messages toward the destination node, each second RREQ message having an indication that it should be transmitted all the way to the destination node even when an intermediate node en-route to the destination node already has a route to the destination node and not having any corresponding logical topology;

recording, at one or more intermediate nodes, a traversed path of the second RREQ messages within the second RREQ messages;

receiving one or more of the second RREQ messages at the destination node during a configured time period after receiving an initial second RREQ message of the second RREQ messages at the destination node; and

determining two or more routes from the source node to the destination node based on the received second RREQ messages at the destination node and one or more path selection criteria.

19. An apparatus, comprising:

one or more network interfaces adapted to interface with a reactive routing computer network logically partitioned into two or more diverse logical topologies, wherein a differing set of nodes of the reactive routing computer network is associated with each of the logical topologies;

a processors coupled to the network interfaces and adapted to execute one or more processes; and

a memory adapted to store a reactive routing process executable by each processor, the process when executed operable to transmit one or more route request (RREQ) messages toward a destination node on each of the logical topologies, each RREQ message having an indication of a corresponding logical topology and an indication that it should be transmitted all the way to the destination node even when an intermediate node en-route to the destination node already has a route to the destination node; and

further operable to receive one or more route reply (RREP) messages, each RREP message indicating a route to reach the destination node using a subset of the set of nodes associated with a corresponding logical topology, and to select a route for each logical topology for which a RREP message was received, to reach the destination node from the apparatus, based on the received RREP message.

20. The apparatus as in claim 19, wherein the logical partitioning of the network is initialized as a comparatively larger number of diverse logical topologies, and

wherein the process is further operable to determine whether two or more diverse routes exist from the apparatus to the destination node based on the comparatively larger number of diverse logical topologies, and when two or more diverse routes do not exist, to logically partition the network as a comparatively smaller number of diverse logical topologies to determine whether two or more diverse routes exist from the apparatus to the destination node based on the comparatively smaller number of diverse logical topologies.

21. A system, comprising:

a reactive routing computer network initially logically partitioned into two or more diverse logical topologies, wherein a differing set of nodes of the reactive routing computer network is associated with each of the logical topologies;

a destination node of the network;

one or more intermediate nodes of the network, the intermediate nodes each corresponding to a particular logical topology;

a source node of the network, the source node configured to transmit one or more route request (RREQ) messages toward the destination node on each of the logical topologies, each RREQ message having an indication of a corresponding logical topology and an indication that it should be transmitted all the way to the destination node even when an intermediate node en-route to the destination node already has a route to the destination node, the source node further configured to receive one or more route reply (RREP) messages, each RREP message indicating a route to reach the destination node using a subset of the set of nodes associated with a corresponding logical topology, and to select a route for each logical topology for which a RREP message was received, to reach the destination node from the source node, based on the received RREP message; and

wherein the source node is further configured to determine whether two or more diverse routes exist from the source node to the destination node based on a number of diverse logical topologies, and when two or more diverse routes do not exist, to transmit second RREQ messages toward the destination node, each second RREQ message having an indication that it should be transmitted all the way to the destination node even when an intermediate node en-route to the destination node already has a route to the destination node and not having any corresponding logical topology, and

wherein the intermediate nodes are configured to record a traversed path of the second RREQ messages within the second RREQ messages; and

wherein the destination node is configured to receive one or more of the second RREQ messages during a configured time period after receiving an initial second RREQ message of the second RREQ messages at the destination node, and to determine two or more routes from the source node to the destination node based on the received second RREQ messages at the destination node and one or more path selection criteria.