Resilient network

• US 7,961,626 B2
• Filed: 09/06/2006
• Issued: 06/14/2011
• Est. Priority Date: 09/27/2005
• Status: Expired due to Fees

• Current Assignee: ROKE Manor Research Limited (Chemring Group PLC), International Development Corporation (Global Earth Energy, Inc.)
• Original Assignee: ROKE Manor Research Limited (Chemring Group PLC)
• Inventors: Reeve, Andrew
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Sloms; Nicholas
• Application Number:
  US11/515,904
• Publication Number:
  US 20070070909A1
• Time in Patent Office: 1,742 Days
• Field of Search: None
• US Class Current: 370/238
• 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
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A network resilient to at least two points of failure comprises a plurality of nodes. A first path between a source node and a destination node is determined and a second path between a source node and a destination node is determined. The first and second paths are node-disjoint.

Claims

1. A method of determining a shortest path in a network comprising a plurality of nodes, the method comprising:

broadcasting a path request message from the source node; and

propagating the path request message through the network from node to node,

wherein, on first receipt of the path request message at each node, a hop count and broadcast identifier are stored,

wherein, when a path request message is received a second time at any node, it is only propagated if the new hop count is less than the stored hop count,

wherein the destination node replies to the source node along the path with the lowest hop count to set up the shortest path,

wherein the network is a mobile ad-hoc network operating distributed routing, using an ad-hoc on-demand resilient path protocol, and

wherein at least one of the nodes in the first and second paths does not have a fixed geographical location.

2. A method according to claim 1, wherein the method further comprises setting bypasses at each node and if the bypass is determined to be shorter, then converting the bypass to be the primary link at that node.

3. A method of forming a pair of node disjoint paths in a network comprising a plurality of nodes using a method of determining a shortest path including broadcasting a path request message from the source node;

and propagating the path request message through the network from node to node, wherein, on first receipt of the path request message at each node, a hop count and broadcast identifier are stored, wherein, when a path request message is received a second time at any node, it is only propagated if the new hop count is less than the stored hop count, wherein the destination node replies to the source node along the path with the lowest hop count to set up the shortest path, wherein the network is a mobile ad-hoc network operating distributed routing, using an ad-hoc on-demand resilient path protocol, and wherein at least one of the nodes in the first and second paths does not have a fixed geographical location;

the method further comprising determining a first shortest path and allocating each link in the path a cost of +1;

determining a second shortest path and allocating to each link in that path which is also in the first shortest path a cost of −

1;

sending a path reply from the destination node back to the source node to create the disjoint pair from links belonging to the first and second shortest paths, but which do not belong to both paths.

4. A method of operating a network resilient to at least two points of failure;

the method comprising setting first and second node-disjoint paths between a source node and a destination node;

wherein the first and second node-disjoint paths are determined according to the method of claim 3;

setting a primary link and a bypass at each node in the paths;

propagating a message packet from the source node;

at each subsequent node, checking validity of the primary link; and

if the primary link is not valid, switching the message packet to the bypass.

5. A method according to claim 3, wherein the first and second node-disjoint paths are determined.

6. A method according to claim 4, wherein the message packet includes a label and each node switches the message packet to the primary link or the bypass, according to the label.

7. A method according to claim 6, wherein the label is used to derive an address in a memory store;

and the node reads data from the memory store relating to the primary link or the bypass according to the label.