Computing disjoint paths for reactive routing mesh networks

• US 9,608,912 B2
• Filed: 11/04/2013
• Issued: 03/28/2017
• 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): Alriyashi, Abdulkader M
• Application Number:
  US14/071,585
• Publication Number:
  US 20140068105A1
• Time in Patent Office: 1,240 Days
• Field of Search: 709/238, 709/239, 709/240, 709/241, 709/243, 370/351
• US Class Current: 1/1
• 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, by a source node, a first route request (RREQ) message toward a destination node of a reactive routing computer network, the first RREQ message having an indication that the first RREQ message is to be transmitted all the way to the destination node, wherein one or more intermediate nodes traversed by the first RREQ message record a traversed path of the first RREQ message within the first RREQ message;

transmitting, by the source node, a second RREQ message toward the destination node, the second RREQ message having an indication that the second RREQ message is to be transmitted all the way to the destination node, wherein one or more intermediate nodes traversed by the second RREQ message record a traversed path of the second RREQ message within the second RREQ message;

receiving, by the source node, a route reply (RREP) message from the destination node, the RREP message including at least the first RREQ message and the second RREQ message; and

determining, by the source node, based on at least the first RREQ message and the second RREQ message included in the RREP message, at least a first route and a second route from the source node to the destination node, wherein the first route and the second route are determined based on the traversed path recorded within the first RREQ message and the traversed path recorded within the second RREQ message.

2. The method of claim 1, further comprising:

after receiving the RREP message, transmitting a data packet to the destination node via the first route.

3. The method of claim 1, wherein the RREP message is transmitted by the destination node to the source node after the destination node received both the first RREQ message and the second RREQ message.

4. The method of claim 3, wherein the destination node received both the first RREQ message and the second RREQ message within a predetermined time period.

5. The method of claim 1, wherein the traversed path of the first RREQ message is different than the traversed path of the second RREQ message.

6. The method of claim 1, wherein the first RREQ message is transmitted to the destination node via a first logical topology of the reactive routing computer network and the second RREQ message is transmitted to the destination node via a second logical topology of the reactive routing computer network.

7. The method of claim 6, further comprising:

partitioning the reactive routing computer network into at least the first logical topology and the second logical topology.

8. A source node, comprising:

one or more computer processors; and

a memory storing instructions that, when executed by the one or more computer processors, cause the source node to;

transmit a first route request (RREQ) message toward a destination node of a reactive routing computer network, the first RREQ message having an indication that the first RREQ message is to be transmitted all the way to the destination node, wherein one or more intermediate nodes traversed by the first RREQ message record a traversed path of the first RREQ message within the first RREQ message;

transmit a second RREQ message toward the destination node, the second RREQ message having an indication that the second RREQ message is to be transmitted all the way to the destination node, wherein one or more intermediate nodes traversed by the second RREQ message record a traversed path of the second RREQ message within the second RREQ message;

receive a route reply (RREP) message from the destination node, the RREP message including at least the first RREQ message and the second RREQ message; and

determine, based on at least the first RREQ message and the second RREQ message included in the RREP message, at least a first route and a second route from the source node to the destination node, wherein the first route and the second route are determined based on the traversed path recorded within the first RREQ message and the traversed path recorded within the second RREQ message.

9. The source node of claim 8, wherein the instructions further cause the source node to:

after receiving the RREP message, transmit a data packet to the destination node via the first route.

10. The source node of claim 8, wherein the RREP message is transmitted by the destination node to the source node after the destination node received both the first RREQ message and the second RREQ message.

11. The source node of claim 10, wherein the destination node received both the first RREQ message and the second RREQ message within a predetermined time period.

12. The source node of claim 8, wherein the traversed path of the first RREQ message is different than the traversed path of the second RREO message.

13. The source node of claim 8, wherein the first RREQ message is transmitted to the destination node via a first logical topology of the reactive routing computer network and the second RREQ message is transmitted to the destination node via a second logical topology of the reactive routing computer network.

14. The source node of claim 13, wherein the instructions further cause the source node to:

partition the reactive routing computer network into at least the first logical topology and the second logical topology.

15. A non-transitory computer-readable medium storing instructions that, when executed by a source node, cause the source node to:

transmit a first route request (RREQ) message toward a destination node of a reactive routing computer network, the first RREQ message having an indication that the first RREQ message is to be transmitted all the way to the destination node, wherein one or more intermediate nodes traversed by the first RREQ message record a traversed path of the first RREQ message within the first RREQ message;

transmit a second RREQ message toward the destination node, the second RREQ message having an indication that the second RREQ message is to be transmitted all the way to the destination node, wherein one or more intermediate nodes traversed by the second RREQ message record a traversed path of the second RREQ message within the second RREQ message;

receive a route reply (RREP) message from the destination node, the RREP message including at least the first RREQ message and the second RREQ message; and

determine, based on at least the first RREQ message and the second RREQ message included in the RREP message, at least a first route and a second route from the source node to the destination node, wherein the first route and the second route are determined based on the traversed path recorded within the first RREQ message and the traversed path recorded within the second RREQ message.

16. The non-transitory computer-readable medium of claim 15, wherein the instructions further cause the source node to:

after receiving the RREP message, transmit a data packet to the destination node via the first route.

17. The non-transitory computer-readable medium of claim 15, wherein the RREP message is transmitted by the destination node to the source node after the destination node received both the first RREQ message and the second RREQ message.

18. The non-transitory computer-readable medium of claim 17, wherein the destination node received both the first RREQ message and the second RREQ message within a predetermined time period.

19. The non-transitory computer-readable medium of claim 15, wherein the traversed path of the first RREQ message is different than the traversed path of the second RREQ message.

20. The non-transitory computer-readable medium of claim 15, wherein the first RREQ message is transmitted to the destination node via a first logical topology of the reactive routing computer network and the second RREQ message is transmitted to the destination node via a second logical topology of the reactive routing computer network.