System for selecting routes for retransmission in a network

• US 20050243725A1
• Filed: 04/30/2004
• Published: 11/03/2005
• Est. Priority Date: 04/30/2004
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Gardner, Edward A., Helliwell, Richard Perham, Wrenn, Richard Fitzhugh
• Granted Patent: US 7,801,029 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A system and method for selecting a route, from within the set of network routes between the source and destination end-points, for retransmission of information initially sent via a suspected failed route such that the selected route has a minimum number of network components in common with the suspected failed route. In one aspect, the routes between source and destination end-points are grouped into a route set and placed in order in a circular list by the destination end-point. When the source end-point deems it necessary to retransmit information sent via a suspected failed route, it selects the next acceptable route following the suspected failed route from the circular list. The circular list order is determined such that adjacent routes have few common network components.

Claims

1. A system for selecting a route for retransmission of information initially sent via a suspected failed route in a network including two end-points connected by at least one fabric, wherein a plurality of routes in the network are grouped into a route set, the system comprising the steps of:

selecting the route for retransmission from one of the routes, in the route set, having a minimum number of network components in common with the suspected failed route.

2. The system of claim 1, wherein said network components include fabrics, I/O buses, adapters, and ports.

3. The system of claim 1, including the step of selecting the route for subsequent retransmissions such that all acceptable routes of the route set are tried for sending a retransmission before any route is retried for sending the retransmission.

4. The system of claim 1, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next acceptable route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set.

5. The system of claim 1, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next acceptable route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set, to create a first route ordering;

when the first route ordering includes a first group of adjacent routes that have a common fabric component, then reordering the routes in the first group by selecting routes, whose local I/O bus component is rotated in round-robin fashion, among available unselected routes of the first group, to create a final route ordering of the circular list.

6. The system of claim 1, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set, to create a first route ordering;

when the first route ordering includes a first group of adjacent routes that have a common fabric component, then reordering the routes in the first group by selecting routes, whose local I/O bus component is rotated in round-robin fashion, among available unselected routes of the first group, to create a second route ordering;

when the second route ordering includes a second group of adjacent routes that have common fabric and I/O bus components, then reordering the routes in the second group by selecting routes, whose local adapter component is rotated in round-robin fashion, among available unselected routes of the second group, to create a final route ordering of the circular list.

7. The system of claim 1, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next acceptable route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set, to create a first route ordering;

when the first route ordering includes a first group of adjacent routes that have a common fabric component, then reordering the routes in the first group by selecting routes, whose local I/O bus component is rotated in round-robin fashion, among available unselected routes of the first group, to create a second route ordering;

when the second route ordering includes a second group of adjacent routes that have common fabric and I/O bus components, then reordering the routes in the second group by selecting routes, whose local adapter component is rotated in round-robin fashion, among available unselected routes of the second group, to create a third route ordering;

when the third route ordering includes a third group of adjacent routes that have common fabric, I/O bus, and adapter components, then reordering the routes in the third group by selecting routes, whose local port component is rotated in round-robin fashion, among available unselected routes of the third group, to create a final route ordering of the circular list.

8. A system for selecting a route for retransmission of information initially sent via a suspected failed route in a network including two end-points connected by at least one fabric, wherein each of the end-points includes one or more I/O buses, adapters, and ports, wherein a plurality of routes in the network are grouped into a route set, the system comprising the steps of:

selecting the route for retransmission from an acceptable route in the route set that uses a different fabric than the failed route;

otherwise, if no acceptable route in the route set exists that uses a different said fabric, then selecting the route for retransmission from an acceptable route in route set that uses a different one of the I/O buses than the failed route;

otherwise, if no acceptable route in the route set exists that uses a different one of the I/O buses, then selecting the route for retransmission from an acceptable route in route set that uses a different one of the adapters than the failed route;

otherwise, if no acceptable route in the route set exists that uses a different one of the adapters, then selecting the route for retransmission from an acceptable route in route set that uses a different said port than the failed route.

9. The system of claim 8, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next acceptable route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set, to create a first route ordering;

when the first route ordering includes a first group of adjacent routes that have a common fabric component, then reordering the routes in the first group by selecting routes, whose local I/O bus component is rotated in round-robin fashion, among available unselected routes of the first group, to create a second route ordering;

when the second route ordering includes a second group of adjacent routes that have common fabric and I/O bus components, then reordering the routes in the second group by selecting routes, whose local adapter component is rotated in round-robin fashion, among available unselected routes of the second group, to create a third route ordering;

when the third route ordering includes a third group of adjacent routes that have common fabric, I/O bus, and adapter components, then reordering the routes in the third group by selecting routes, whose local port component is rotated in round-robin fashion, among available unselected routes of the third group.

10. A system for determining route ordering for retransmission of information in a network including two end-points, wherein each of the end-points comprises a plurality of network components, and wherein a plurality of routes in the network are grouped into a route set, the system comprising the steps of:

assigning a weight to each of a plurality of network components, wherein the weight is indicative of the relative importance of the corresponding component;

determining route-pair weight sums, relative to a local one of the end-points, for each pair of routes in the route set, by summing the weights for each network component of interest that is not included in both of the routes in a particular said pair of routes;

determining the complete route-order set containing every non-equivalent ordering of routes, in the route set, between the two endpoints;

determining a route-order weight sum for each said non-equivalent ordering of routes by summing the individual route-pair weights for each ordering of routes in the route-order set; and

determining the route ordering for retransmission at a remote one of the end-points by ordering the routes in the route-order set according to the route-order weight sum.

11. The system of claim 10, wherein the route selected for retransmission is the next acceptable route following the suspected failed route in the route-order having the largest route-order weight sum in the route-order set.

12. The system of claim 10, wherein a complete undirected graph is constructed in which the vertices thereof correspond to the routes of the route set and the arc distances correspond to the route-pair weight sums;

wherein the route ordering is determined by finding the longest circuit through the graph that visits each one of the vertices exactly once.

13. The system of claim 12, wherein the longest circuit through the complete graph of route pairs that visits each one of the vertices exactly once is determined by applying a traveling salesman problem solution to the graph.

14. The system of claim 12, wherein the longest circuit through the complete graph of route pairs that visits each one of the vertices exactly once is determined from a comparison of all possible non-equivalent route orderings.

15. The system of claim 12, wherein the network components are selected from the group consisting of a fabric, an I/O bus, an adapter, and a port:

16. The system of claim 10, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next acceptable route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set.

17. The system of claim 10, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next acceptable route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set, to create a first route ordering;

when the first route ordering includes a first group of adjacent routes that have a common fabric component, then reordering the routes in the first group by selecting routes, whose local I/O bus component is rotated in round-robin fashion, among available unselected routes of the first group, to create a final route ordering of the circular list.

18. The system of claim 10, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next acceptable route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set, to create a first route ordering;

when the first route ordering includes a first group of adjacent routes that have a common fabric component, then reordering the routes in the first group by selecting routes, whose local I/O bus component is rotated in round-robin fashion, among available unselected routes of the first group, to create a second route ordering;

when the second route ordering includes a second group of adjacent routes that have common fabric and I/O bus components, then reordering the routes in the second group by selecting routes, whose local adapter component is rotated in round-robin fashion, among available unselected routes of the second group, to create a final route ordering of the circular list.

19. The system of claim 10, wherein the routes of the route set are placed in a circular list and the route selected for retransmission is the next acceptable route in the circular list following the suspected failed route, wherein ordering of the circular list is determined by performing the steps of:

selecting routes, whose fabric component is rotated in round-robin fashion, among available unselected routes of the route set, to create a first route ordering;

when the first route ordering includes a first group of adjacent routes that have a common fabric component, then reordering the routes in the first group by selecting routes, whose local I/O bus component is rotated in round-robin fashion, among available unselected routes of the first group, to create a second route ordering;

when the second route ordering includes a second group of adjacent routes that have common fabric and I/O bus components, then reordering the routes in the second group by selecting routes, whose local adapter component is rotated in round-robin fashion, among available unselected routes of the second group, to create a third route ordering;

when the third route ordering includes a third group of adjacent routes that have common fabric, I/O bus, and adapter components, then reordering the routes in the third group by selecting routes, whose local port component is rotated in round-robin fashion, among available unselected routes of the third group, to create a final route ordering of the circular list.

20. The system of claim 10, including the step of selecting the route for subsequent retransmissions such that all acceptable routes of the route set are tried for sending a retransmission before any route is retried for sending the retransmission.