Agile digital communication network with rapid rerouting

• US 7,362,709 B1
• Filed: 11/04/2002
• Issued: 04/22/2008
• Est. Priority Date: 11/02/2001
• Status: Active Grant

• Current Assignee: Arizona Science and Technology Enterprises LLC
• Original Assignee: Arizona Board of Regents (University of Arizona)
• Inventors: Hui, Joseph Y., Van Emden, Bernard M.
• Primary Examiner(s): Phan, Chi
• Assistant Examiner(s): Phan, Tri H.
• Application Number:
  US10/287,996
• Time in Patent Office: 1,996 Days
• Field of Search: 370229-238, 370216-221, 370/392, 370400-406, 709238-243
• US Class Current: 370/237
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• 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/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

An agile digital communications network has a number of routers that serve as nodes in a mesh network communicating between a user device (e.g., computer, server, etc.) and a target device (e.g., disc storage cabinets, tape, jukebox, etc.). The routers operate on an open shortest path first protocol, each router having two or more interfaces or links to other routers. When a link connected to a router is down and is in the shortest path to another router identified in a communication packet, the packet is forwarded to the identified router on a precalculated alternate route that does not use the unavailable link. IP tunneling assures that routing loops do not occur and send the packet back to the router with the unavailable link because it would have been in the shortest path of an intermediate router. A tunneling technique is provided that maximizes the levels of encapsulation needed at two, regardless of the size or configuration of the network. An unavailable link is not broadcast immediately throughout the network, giving the link an opportunity to be restored before all of the routers are called on to recalculate the shortest paths and alternate paths. During a short interval following the discovery of an unavailable link, then, a router connected to that link is in a state identified as the Use Alternate Path state, and the link is repeatedly checked for availability. Each router calculates and stores the alternative paths to each other router after first calculating the shortest path to each other router. The alternate paths are pulled up and used when an unavailable link is detected. Dijkstra'"'"'s algorithm is used to calculate the shortest paths. A new algorithm called the iterative dynamic Dijkstra'"'"'s algorithm is used to calculate the alternative routes.

Claims

1. A digital storage system comprising:

(a) a digital storage facility;

(b) a mesh network of routers connected to the digital storage facility;

(c) a plurality of access points to the network for connection to a plurality of user computers;

(d) each router in the network having a plurality of links connected between it and a neighboring router;

(e) the network operating on an open shortest path first protocol;

(f) each router being programmed for;

(i) calculating the shortest path to other routers starting with a first hop to a neighboring router along one of the links connecting to a neighboring router;

(ii) storing at least each shortest first path hop of each calculated shortest path;

(iii) calculating alternate paths to other routers, which alternate paths have a first hop on another of the links connecting to a further neighboring router;

(iv) storing the calculated alternate paths;

(v) detecting whether links connected to the router are operable;

(vi) for a limited time interval following detection of a link becoming inoperable, employing a previously calculated one of the alternate paths for communications to those routers for which the first hop on the calculated shortest path was along the now-inoperable link.

2. The digital storage system of claim 1, wherein the routers are further programmed, upon detection of a link being restored to operability, to restore the use of the previously calculated shortest paths for communication to routers for which an alternate path had been employed.

3. The digital storage system of claim 2, wherein the routers are further programmed to flood the remaining routers with a link state advertisement apprising the remaining routers of the detected link inoperability if the inoperability persists beyond the limited time interval.

4. The digital storage system of claim 3, wherein every router has alternate path programming that iteratively assumes failure of the links connected to that router and calculates the alternate paths to all routers connected by a calculated shortest path to that router containing the link assumed to have failed.

5. The digital storage system of claim 4, wherein the alternate path software of each router includes programming that identified a set of invalid node routers with shortest paths to that router that would be broken by failure of the assumed failed link.

6. The digital storage system of claim 5, wherein the alternate path programming calculates alternate paths only to the routers in the identified set of invalid node routers for each assumed link failure.

7. The digital storage system of claim 2, wherein the routers are further programmed to tunnel a communication packet to a router on the alternate path that is closer along the alternate path to a targeted router than along any path employing the link detected to be inoperable.

8. The digital storage system of claim 7, wherein, to tunnel a communication packet, the routers are programmed to encapsulate the packet.

9. The digital storage system of claim 8, wherein to tunnel a communication packet the routers are programmed for:

(a) locating an intermediate router along the alternate path from a first router to an intermediate router from which the communication will not turn back, and

(b) reducing the number of levels of encapsulation needed to reach the intermediate router.

10. The digital storage system of claim 9, wherein the routers have programming for reducing the number of levels of encapsulation by:

(i) when the intermediate router lies in a branch of a shortest path tree of the first router, encapsulating the communication once only with instructions routing the communication to the intermediate router, and

(ii) when the intermediate router lies in a branch of a shortest path tree for which a link has become unavailable, encapsulating the communication twice, with a first outer level of encapsulation routing the communication to a router that is the last in a path to the intermediate router before reaching the intermediate router, and with a second inner level of encapsulation routing the communication to the intermediate router.

11. The digital storage system of claim 10, wherein locating an intermediate router includes:

(a) calculating iteratively for each router along the alternate path and until the intermediate router is identified;

(i) Cost 1, which is the length along the alternate path from each router to a desired router, and

(ii) Cost 2, which is the length of a path each router along the alternate path back through the first router and along the previously calculated shortest path to the desired router, and

(b) identifying as the intermediate router the first router in the path for which Cost 1<

Cost 2.

12. The digital storage system of claim 9, wherein locating an intermediate router includes:

(a) calculating iteratively for each router along the alternate path and until the intermediate router is identified;

(i) Cost 1, which is the length along the alternate path from each router to a desired router, and

(ii) Cost 2, which is the length of a path each router along the alternate path back through the first router and along the previously calculated shortest path to the desired router, and

(b) identifying as the intermediate router the first router in the path for which Cost 1<

Cost 2.

13. A method of communicating between at least one initiator and at least one target comprising:

(a) providing a mesh network of routers connected to a digital storage facility;

(b) providing a plurality of access points to the network for connection to one or more initiators and one or more targets;

(c) providing each router in the network with a plurality of links connected between it and neighboring routers;

(d) operating the network on an open shortest path first protocol;

(e) for each router;

(i) calculating the shortest path to other routers starting with a first hop to a neighboring router along one of the links connecting to a neighboring router;

(ii) storing at least each shortest first path hop of each calculated shortest path;

(iii) calculating alternate paths to other routers, which alternate paths have a first hop on another of the links connecting to a further neighboring router;

(iv) storing the calculated alternate paths;

(v) detecting whether links connected to the router are operable;

(vi) for a limited time interval following detection of a link becoming inoperable, employing a previously calculated one of the alternate paths for communications to those routers for which the first hop on the calculated shortest path was along the now-inoperable link.

14. The method according to claim 13, further comprising upon detection of a link being restored to operability, restoring the use of the previously calculated shortest paths for communication to routers for which an alternate path had been employed.

15. The method according to claim 14, further comprising flooding the remaining routers with a link state advertisement apprising the remaining routers of the detected link inoperability if the inoperability persists beyond the limited time interval.

16. The method according to claim 14, further comprising tunneling a communication packet to a router on the alternate path that is closer along the alternate path to a targeted router than along any path employing the link detected to be inoperable.

17. The method according to claim 16, wherein tunneling comprises encapsulating the packet with a maximum two layers of encapsulation and stripping from a received packet an outer layer of encapsulation.

18. The method according to claim 16, wherein tunneling comprises encapsulating the packet.

19. The method according to claim 18, wherein tunneling further comprises:

(a) locating an intermediate router along the alternate path from a first router to an intermediate router from which the communication will not turn back, and

(b) reducing the number of levels of encapsulation needed to reach the intermediate router.

20. The method according to claim 19, further comprising reducing the number of levels of encapsulation by:

(i) when the intermediate router lies in a branch of a shortest path tree of the first router, encapsulating the communication once only with instructions routing the communication to the intermediate router, and

(ii) when the intermediate router lies in a branch of a shortest path tree for which a link has become unavailable, encapsulating the communication twice, with a first outer level of encapsulation routing the communication to a router that is the last in a path to the intermediate router before reaching the intermediate router, and with a second inner level of encapsulation routing the communication to the intermediate router.

21. The method according to claim 20, wherein locating an intermediate router includes:

(a) calculating iteratively for each router along the alternate path and until the intermediate router is identified;

(i) Cost 1, which is the length along the alternate path from each router to a desired router, and

(ii) Cost 2, which is the length of a path each router along the alternate path back through the first router and along the previously calculated shortest path to the desired router, and

(b) identifying as the intermediate router the first router in the path for which Cost 1<

Cost 2.

22. The method according to claim 19, wherein locating an intermediate router includes:

(a) calculating iteratively for each router along the alternate path and until the intermediate router is identified;

(i) Cost 1, which is the length along the alternate path from each router to a desired router, and

(ii) Cost 2, which is the length of a path each router along the alternate path back through the first router and along the previously calculated shortest path to the desired router, and

(b) identifying as the intermediate router the first router in the path for which Cost 1<

Cost 2.

23. The method according to claim 13, wherein calculating alternate paths comprises iteratively assuming failure of the links connected to a router and calculating the alternate paths to all routers connected by a calculated shortest path to that router containing the link assumed to have failed.

24. The method according to claim 23, wherein calculating alternate paths further comprises identifying a set of invalid node routers with shortest paths to a router that would be broken by failure of the assumed failed link.

25. The method according to claim 24, wherein calculating alternate paths further includes calculating alternate paths only to routers in the identified set of invalid node routers for each assumed link failure.