Method and apparatus for deadlock-free routing around an unusable routing component in an N-dimensional network

• US 5,898,826 A
• Filed: 11/22/1995
• Issued: 04/27/1999
• Est. Priority Date: 11/22/1995
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Pierce, Paul R., Ernst, Linda C., Dunning, David S.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Elmore, Stephen C.
• Application Number:
  US08/562,200
• Time in Patent Office: 1,252 Days
• Field of Search: 395/182.02, 395/200.15, 395/311, 395/312, 370/400, 370/406, 370/351, 370/352, 370/353, 370/354, 370/355, 370/356, 370/237, 370/238, 370/217, 370/218, 370/225, 370/389, 370/401
• US Class Current: 714/4.2
• 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/28 using route fault recovery

Abstract

A method and apparatus for deadlock-free routing around an unusable routing component in a network reroutes paths between source and destination nodes by initially identifying an unusable routing component. A shadow direction within the network is then determined, the shadow direction being from the unusable routing component to an edge of the network. The paths between nodes are then rerouted so that the paths bypass the unusable routing component and limit the use of any routing components in the network between the unusable routing component and the edge in the shadow direction.

Claims

1. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:

determining a first direction from the unusable routing component to an edge of the network; and

routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the network between the unusable routing component and the edge in the first direction.

2. The method of claim 1, wherein the unusable routing component is a routing device.

3. The method of claim 1, wherein the unusable routing component is a communication link.

4. The method of claim 1, wherein the step of routing comprises the step of routing the path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of each routing component in the network between the unusable routing component and the edge in the first direction.

5. The method of claim 1, wherein the step of determining comprises the steps of:

determining an edge of the network which is closest to the unusable routing component; and

identifying the first direction as being a direction from the unusable routing component to the edge of the network which is closest to the unusable routing component.

6. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:

identifying the unusable routing component;

determining a first direction from the unusable routing component to an edge of the network;

identifying a plurality of shadow routing components; and

routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction.

7. The method of claim 6, wherein the plurality of shadow routing components are located within the network between the unusable routing component and the edge of the network in the first direction.

8. The method of claim 6, wherein the step of determining comprises the steps of:

determining an edge of the network which is closest to the unusable routing component; and

identifying the first direction as being a direction from the unusable routing component to the edge of the network which is closest to the unusable routing component.

9. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:

identifying the unusable routing component;

determining a first direction from the unusable routing component to an edge of the network; and

routing a path for the data from the source router to the destination router in a second direction away from the edge which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction.

10. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:

identifying the unusable routing component;

determining a first direction from the unusable routing component to an edge of the network; and

routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction, wherein the routing includes routing the data through a first router, wherein the first router is located in the network between the unusable routing component and the edge in the first direction, provided the first router is not the destination router, and provided the path does not turn at the first router.

11. A method for deadlock-free routing of data around an unusable routing component in a network, the method comprising the steps of:

(a) determining a shadow direction from the unusable routing component to an edge of the network;

(b) determining whether the data can progress according to an original path;

(c) routing the data along the original path, provided the data can progress according to the original path; and

(d) moving the data in a first direction, provided the data cannot progress according to the original path, wherein the first direction is opposite the shadow direction.

12. The method of claim 11, further comprising the step of:

(e) decrementing a counter associated with the data to indicate that the data has moved in the first direction.

13. The method of claim 11, wherein the step of determining a shadow direction comprises the steps of:

determining an edge of the network which is closest to the unusable routing component; and

identifying the shadow direction as being a direction from the unusable routing component to the edge of the network which is closest to the unusable routing component.

14. An apparatus for deadlock-free routing of data around an unusable routing component in a network, wherein the data is originally routed from a source router to a destination router, wherein the apparatus comprises:

an unusable router register which stores an identifier of the unusable routing component; and

control logic, communicatively coupled with the unusable router register, to determine a first direction from the unusable routing component to an edge of the network and to route the data to the destination router via a path which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the network between the unusable routing component and the edge in the first direction.

15. The apparatus of claim 14, wherein the control logic is further operative to update the unusable router register responsive to a routing component in the network becoming faulty.

16. The apparatus of claim 14, wherein the unusable routing component is a router.

17. The apparatus of claim 14, wherein the unusable routing component is a communication link.

18. The apparatus of claim 14, wherein the control logic is operative to route the data from the source router to the destination router via a path which bypasses the unusable routing component and limits use of each routing component in the network between the unusable routing component and the edge in the first direction.

19. The apparatus of claim 14, wherein the control logic is further operative to determine the first direction by determining an edge of the network which is closest to the unusable routing component and identifying the first direction as being a direction from the unusable routing component to the edge of the network which is closest to the unusable routing component.

20. A system comprising:

a plurality of processing nodes, wherein each of the plurality of processing nodes includes a processor and a memory device; and

a plurality of routing devices coupled to the plurality of processing nodes, wherein each of the plurality of routing devices transfers data to other routing devices, and wherein each of the plurality of routing devices includes,

an unusable router register which contains an identifier of an unusable routing component, and

control logic, communicatively coupled with the unusable router register, to determine a first direction from the unusable routing component to an edge of the system and to route the data via a path which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the system between the unusable routing component and the edge in the first direction.

21. The system of claim 20, wherein the control logic is further operative to update the unusable router register responsive to a routing component in the system becoming faulty.

22. The system of claim 20, wherein the unusable routing component is one of the plurality of routing devices.

23. The system of claim 20, wherein the control logic is operative to route the data via a path which bypasses the unusable routing component and limits use of each routing component in the system between the unusable routing component and the edge in the first direction.

24. The system of claim 20, wherein the control logic is further operative to determine the first direction by determining an edge of the system which is closest to the unusable routing component and identifying the first direction as being a direction from the unusable routing component to the edge of the system which is closest to the unusable routing component.

25. An apparatus for deadlock-free routing of data around an unusable routing component, wherein the data is routed from a source router to a destination router in a network, the apparatus comprising:

an unusable router register to store an identifier of the unusable routing component; and

control logic, communicatively coupled to the unusable router register, to determine a first direction from the unusable routing component to an edge of the network, to identify a plurality of shadow routing components, and to route the data from the source router to the destination router bypassing the unusable routing component and limiting use of any routing components between the unusable routing component and the edge in the first direction.

26. An apparatus for deadlock-free routing around an unusable routing component, wherein the data is routed from a source router to a destination router in a network, the apparatus comprising:

an unusable router register to store an identifier of the unusable routing component; and

control logic, communicatively coupled to the unusable router register, to determine a first direction from the unusable routing component to an edge of the network, and to route the data from the source router to the destination router bypassing the unusable routing component and limiting use of any routing components in the network between the unusable routing component and the edge in the first direction, wherein the routing includes routing the data through a first router located between the unusable routing component and the edge in the first direction, provided the first router is not the destination router, and provided the routing does not turn at the first router.

27. A system comprising:

a plurality of processing nodes, wherein each of the plurality of processing nodes includes a processor and a memory device; and

a plurality of routing devices coupled to the plurality of processing nodes, wherein each of the plurality of routing devices transfers data to other routing devices, and wherein each of the plurality of routing devices includes,

an unusable router register to store identifiers of one or more unusable routing components; and

control logic, communicatively coupled to the unusable router register, to determine a first direction from one of the one or more unusable routing component to an edge of the system, to identify a plurality of shadow routing components, and to route the data from a first routing device of the plurality of routing devices to a second routing device of the plurality of routing devices bypassing the one of the one or more unusable routing components and limiting use of any routing components in the system between the one of the one or more unusable routing components and the edge in the first direction.

28. A system comprising:

a plurality of processing nodes, wherein each of the plurality of processing nodes includes a processor and a memory device; and

a plurality of routing devices coupled to the plurality of processing nodes including a first routing device, a second routing device, and a third routing device, wherein each of the plurality of routing devices transfers data to other routing devices, and wherein each of the plurality of routing devices includes,

an unusable router register to store identifiers of one or more unusable routing components; and

control logic, communicatively coupled to the unusable router register, to determine a first direction from a first unusable routing component of the one or more unusable routing components to an edge of the system, and to route the data from the first routing device to the second routing device bypassing the first unusable routing component, limiting use of any routing components in the system between the first unusable routing component and the edge in the first direction, and routing the data through the third routing device located between the first unusable routing component and the edge in the first direction, provided the second routing device and the third routing device are different routing devices, and provided the routing does not turn at the third routing device.

29. A machine-readable storage medium having stored therein a plurality of programming instructions for use by a processor, wherein the plurality of programming instructions implements the method steps of:

determining a first direction from an unusable routing component to an edge of a network; and

routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the network between the unusable routing component and the edge in the first direction.

30. The machine-readable storage medium of claim 29, wherein the step of routing comprises the step of routing the path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of each routing component in the network between the unusable routing component and the edge in the first direction.

31. A machine-readable storage medium having stored therein a plurality of programming instructions for use by a processor, wherein the plurality of programming instructions implements the method steps of:

determining a first direction from an unusable routing component to an edge of a network;

identifying a plurality of shadow routing components; and

routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction.

32. A machine-readable storage medium having stored therein a plurality of programming instructions for use by a processor, wherein the plurality of programming instructions implements the method steps of:

determining a first direction from an unusable routing component to an edge of the network; and

routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction, wherein the routing includes routing the data through a first router, wherein the first router is located in the network between the unusable routing component and the edge in the first direction, provided the first router is not the destination router, and provided the path does not turn at the first router.