System and Method for Handling Indirect Routing of Information Between Supernodes of a Multi-Tiered Full-Graph Interconnect Architecture

• US 20090063445A1
• Filed: 08/27/2007
• Published: 03/05/2009
• Est. Priority Date: 08/27/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Arimilli, Ravi K., Rajamony, Ramakrishnan, Arimilli, Lakshminarayana B.
• Granted Patent: US 7,769,892 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

Abstract

A method, computer program product, and system are provided for selecting, from a plurality of routes through the data processing system, an indirect route for transmitting data. Data that includes address information is received at a first processor that is to be transmitted to a destination processor. Using routing table data structures, indirect route entries are identified that correspond to indirect routes for transmitting data. An accessed priority table data structure comprises a priority entry for each entry in the routing table data structures. The priority entry specifies a priority of a corresponding entry in the routing table data structures. An indirect route entry is selected that corresponds to an indirect route from the routing table data structures, based on specified priorities. Then the data is transmitted from the first processor to the destination processor using a path corresponding to the selected indirect route entry.

Claims

1. A method, in a data processing system, for selecting, from a plurality of routes through the data processing system, an indirect route for transmitting data, the method comprising:

receiving data at a first processor within a set of processors that is to be transmitted to a destination processor, wherein the data includes address information;

identifying, in one or more routing table data structures, indirect route entries corresponding to a plurality of indirect routes for transmitting data from a first processor to a destination processor;

accessing a priority table data structure associated with the one or more routing table data structures, wherein the priority table data structure comprises a priority entry for each entry in the one or more routing table data structures, the priority entry specifying a priority of a corresponding entry in the one or more routing table data structures;

selecting an indirect route entry corresponding to an indirect route in the plurality of indirect routes from the one or more routing table data structures, based on specified priorities in priority entries of the priority table data structure corresponding to the indirect route entries of the plurality of indirect routes; and

transmitting the data from the first processor to the destination processor using a path corresponding to the selected indirect route entry.

2. The method of claim 1, wherein the one or more routing table data structures comprise an entry for each route in the plurality of routes, and wherein the plurality of routes comprises the plurality of indirect routes and at least one direct route.

3. The method of claim 1, wherein the entries in the one or more routing table data structures comprise a pointer field that stores a pointer to a priority entry in the priority table data structure corresponding to the entry in the one or more routing table data structures, and wherein accessing the priority table data structure comprises using a pointer in a first indirect route entry to identify a corresponding priority entry in the priority table data structure.

4. The method of claim 3, wherein the entries in the one or more routing table data structures comprise a last used field that identifies whether an entry in the one or more routing table data structures was previously used to route data.

5. The method of claim 4, wherein the first indirect route entry used to identify a corresponding priority entry in the priority table data structure is an indirect route entry in the indirect route entries whose last used field identifies the indirect route entry as having been previously used to route data.

6. The method of claim 3, wherein selecting the indirect route entry comprises:

identifying a next priority entry in the priority table data structure having a next higher priority ranking from the priority entry corresponding to the first indirect route entry;

identifying an indirect route entry in the indirect route entries corresponding to the next priority entry; and

selecting the identified indirect route entry corresponding to the next priority entry as the indirect route entry whose path is used to transmit the data.

7. The method of claim 1, wherein the priority entries are assigned by at least one of a random selection, an adaptive real-time selection, a round-robin selection, or a selection that is identified with the data.

8. The method of claim 1, wherein the indirect route for transmitting the data is determined by at least one of software, hardware, a combination of software and hardware, or determined by an administrator.

9. The method of claim 1, wherein the method is implemented by a switch integrated in the first processor.

10. A computer program product for selecting, from a plurality of routes through the data processing system, an indirect route for transmitting data, comprising a computer useable medium having a computer readable program, wherein the computer readable program, when executed in a first processor in a set of processors of a data processing system, causes the first processor to:

receive data that is to be transmitted to a destination processor, wherein the data includes address information;

identify, in one or more routing table data structures, indirect route entries corresponding to a plurality of indirect routes for transmitting data from a first processor to a destination processor;

access a priority table data structure associated with the one or more routing table data structures, wherein the priority table data structure comprises a priority entry for each entry in the one or more routing table data structures, the priority entry specifying a priority of a corresponding entry in the one or more routing table data structures;

select an indirect route entry corresponding to an indirect route in the plurality of indirect routes from the one or more routing table data structures, based on specified priorities in priority entries of the priority table data structure corresponding to the indirect route entries of the plurality of indirect routes; and

transmit the data from the first processor to the destination processor using a path corresponding to the selected indirect route entry.

11. The computer program product of claim 10, wherein the one or more routing table data structures comprise an entry for each route in the plurality of routes, and wherein the plurality of routes comprises the plurality of indirect routes and at least one direct route.

12. The computer program product of claim 10, wherein the entries in the one or more routing table data structures comprise a pointer field that stores a pointer to a priority entry in the priority table data structure corresponding to the entry in the one or more routing table data structures, and wherein accessing the priority table data structure comprises using a pointer in a first indirect route entry to identify a corresponding priority entry in the priority table data structure.

13. The computer program product of claim 12, wherein the entries in the one or more routing table data structures comprise a last used field that identifies whether an entry in the one or more routing table data structures was previously used to route data.

14. The computer program product of claim 13, wherein the first indirect route entry used to identify a corresponding priority entry in the priority table data structure is an indirect route entry in the indirect route entries whose last used field identifies the indirect route entry as having been previously used to route data.

15. The computer program product of claim 12, wherein the computer readable program further causes the first processor to:

identify a next priority entry in the priority table data structure having a next higher priority ranking from the priority entry corresponding to the first indirect route entry;

identify an indirect route entry in the indirect route entries corresponding to the next priority entry; and

select the identified indirect route entry corresponding to the next priority entry as the indirect route entry whose path is used to transmit the data.

16. The computer program product of claim 10, wherein the computer readable program is executed in a switch integrated in the first processor.

17. A data processing system for selecting, from a plurality of routes through the data processing system, an indirect route for transmitting data, comprising:

a set of processors; and

a memory coupled to the set of processors, wherein the memory comprises instructions which, when executed by a first processor in the set of processors, cause the first processor to;

receive data that is to be transmitted to a destination processor, wherein the data includes address information;

identify, in one or more routing table data structures, indirect route entries corresponding to a plurality of indirect routes for transmitting data from a first processor to a destination processor;

access a priority table data structure associated with the one or more routing table data structures, wherein the priority table data structure comprises a priority entry for each entry in the one or more routing table data structures, the priority entry specifying a priority of a corresponding entry in the one or more routing table data structures;

select an indirect route entry corresponding to an indirect route in the plurality of indirect routes from the one or more routing table data structures, based on specified priorities in priority entries of the priority table data structure corresponding to the indirect route entries of the plurality of indirect routes; and

transmit the data from the first processor to the destination processor using a path corresponding to the selected indirect route entry.

18. The data processing system of claim 17, wherein the one or more routing table data structures comprise an entry for each route in the plurality of routes, and wherein the plurality of routes comprises the plurality of indirect routes and at least one direct route.

19. The data processing system of claim 17, wherein the entries in the one or more routing table data structures comprise a pointer field that stores a pointer to a priority entry in the priority table data structure corresponding to the entry in the one or more routing table data structures, and wherein accessing the priority table data structure comprises using a pointer in a first indirect route entry to identify a corresponding priority entry in the priority table data structure.

20. The data processing system of claim 19, wherein the entries in the one or more routing table data structures comprise a last used field that identifies whether an entry in the one or more routing table data structures was previously used to route data, and wherein the first indirect route entry used to identify a corresponding priority entry in the priority table data structure is an indirect route entry in the indirect route entries whose last used field identifies the indirect route entry as having been previously used to route data.