COMPUTING DISJOINT PATHS FOR REACTIVE ROUTING MESH NETWORKS

• US 20140068105A1
• Filed: 11/04/2013
• Published: 03/06/2014
• 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
• Granted Patent: US 9,608,912 B2
• Time in Patent Office: Days
• US Class Current: 709/239
• 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, one or more route request (RREQ) messages toward a destination node of a reactive routing computer network, each RREQ message having an indication that it should be transmitted all the way to the destination node;

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

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

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