System and Method for Dynamically Supporting Indirect Routing Within a Multi-Tiered Full-Graph Interconnect Architecture

• US 20090063443A1
• 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,840,703 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• 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/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A method, computer program product, and system are provided for dynamically routing data through the data processing system. Data is received at a first processor that is to be transmitted to a destination processor. The data that is received includes address information. A lookup is performed in routing table data structures based on the address information to identify candidate paths through which the data is routed to the destination processor. A determination is made as to whether any of the candidate paths are not able to be used to route the data to the destination processor based on a setting of at least one identifier. A path is selected from the identified candidate paths for routing of the data based on a setting of the at least one identifier. Then, the data is transmitted from the first processor along the selected path toward the destination processor.

Claims

1. A method, in a data processing system, of dynamically routing data through the data processing system, 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;

performing a lookup operation in one or more routing table data structures based on the address information to identify one or more candidate paths through which the data is routed to the destination processor;

determining if any of the one or more candidate paths are not able to be used to route the data to the destination processor based on a setting of at least one identifier in at least one field of one or more entries of the one or more routing table data structures corresponding to the identified one or more candidate paths, wherein the at least one identifier is at least one of a no-direct identifier or a no-indirect identifier;

selecting a path from the identified one or more candidate paths for routing of the data to the destination processor based on a setting of the at least one identifier in the one or more entries corresponding to the one or more candidate paths and whether a candidate path corresponding to an entry is to be used for direct or indirect routing of the data to the destination processor; and

transmitting the data from the first processor along the selected path toward the destination processor.

2. The method of claim 1, wherein if a candidate path is to be used for direct routing of data to the destination processor, and a no-direct identifier in an entry of the one or more routing table data structures corresponding to the candidate path is set to indicate that direct routing of data across the candidate path is prohibited, then the candidate path is not considered for selection as the selected path to be used to transmit the data from the first processor to the destination processor.

3. The method of claim 1, wherein if a candidate path is to be used for indirect routing of data to the destination processor, and a no-indirect identifier in an entry of the one or more routing table data structures corresponding to the candidate path is set to indicate that indirect routing of data across the candidate path is prohibited, then the candidate path is not considered for selection as the selected path to be used to transmit the data from the first processor to the destination processor.

4. The method of claim 1, wherein each entry in the one or more routing table data structures comprises both a no-direct identifier field and a no-indirect identifier field, and wherein a no-indirect identifier field is set to indicate that a corresponding path cannot be used for indirect routing of data while the no-direct identifier field is not set indicating that the corresponding path can be used for direct routing of data.

5. The method of claim 1, wherein selecting a path from the identified one or more candidate paths for routing of the data to the destination processor further comprises determining if a setting is designated with header information included with the data, wherein the header information designates at least one of only using an indirect path or only using a direct path.

6. The method of claim 1, wherein selecting the path is determined by at least one of software, hardware, a combination of software and hardware, or predetermined by an administrator.

7. The method of claim 1, wherein path selection uses at least one of random selection, adaptive real-time selection, round-robin selection, or selection that is identified with the data.

8. A computer program product, for dynamically routing data through the data processing system, 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;

perform a lookup operation in one or more routing table data structures based on the address information to identify one or more candidate paths through which the data is routed to the destination processor;

determine if any of the one or more candidate paths are not able to be used to route the data to the destination processor based on a setting of at least one identifier in at least one field of one or more entries of the one or more routing table data structures corresponding to the identified one or more candidate paths, wherein the at least one identifier is at least one of a no-direct identifier or a no-indirect identifier;

select a path from the identified one or more candidate paths for routing of the data to the destination processor based on a setting of the at least one identifier in the one or more entries corresponding to the one or more candidate paths and whether a candidate path corresponding to an entry is to be used for direct or indirect routing of the data to the destination processor; and

transmit the data from the first processor along the selected path toward the destination processor.

9. The computer program product of claim 8, wherein if a candidate path is to be used for direct routing of data to the destination processor, and a no-direct identifier in an entry of the one or more routing table data structures corresponding to the candidate path is set to indicate that direct routing of data across the candidate path is prohibited, then the candidate path is not considered for selection as the selected path to be used to transmit the data from the first processor to the destination processor.

10. The computer program product of claim 8, wherein if a candidate path is to be used for indirect routing of data to the destination processor, and a no-indirect identifier in an entry of the one or more routing table data structures corresponding to the candidate path is set to indicate that indirect routing of data across the candidate path is prohibited, then the candidate path is not considered for selection as the selected path to be used to transmit the data from the first processor to the destination processor.

11. The computer program product of claim 8, wherein each entry in the one or more routing table data structures comprises both a no-direct identifier field and a no-indirect identifier field, and wherein a no-indirect identifier field is set to indicate that a corresponding path cannot be used for indirect routing of data while the no-direct identifier field is not set indicating that the corresponding path can be used for direct routing of data.

12. The computer program product of claim 8, wherein selecting a path from the identified one or more candidate paths for routing of the data to the destination processor further comprises determining if a setting is designated with header information included with the data, wherein the header information designates at least one of only using an indirect path or only using a direct path.

13. The computer program product of claim 8, wherein selecting the path is determined by at least one of software, hardware, a combination of software and hardware, or predetermined by an administrator.

14. The computer program product of claim 8, wherein path selection uses at least one of random selection, adaptive real-time selection, round-robin selection, or selection that is identified with the data.

15. A system for dynamically routing data through the data processing system, 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;

perform a lookup operation in one or more routing table data structures based on the address information to identify one or more candidate paths through which the data is routed to the destination processor;

determine if any of the one or more candidate paths are not able to be used to route the data to the destination processor based on a setting of at least one identifier in at least one field of one or more entries of the one or more routing table data structures corresponding to the identified one or more candidate paths, wherein the at least one identifier is at least one of a no-direct identifier or a no-indirect identifier;

select a path from the identified one or more candidate paths for routing of the data to the destination processor based on a setting of the at least one identifier in the one or more entries corresponding to the one or more candidate paths and whether a candidate path corresponding to an entry is to be used for direct or indirect routing of the data to the destination processor; and

transmit the data from the first processor along the selected path toward the destination processor.

16. The system of claim 15, wherein if a candidate path is to be used for direct routing of data to the destination processor, and a no-direct identifier in an entry of the one or more routing table data structures corresponding to the candidate path is set to indicate that direct routing of data across the candidate path is prohibited, then the candidate path is not considered for selection as the selected path to be used to transmit the data from the first processor to the destination processor.

17. The system of claim 15, wherein if a candidate path is to be used for indirect routing of data to the destination processor, and a no-indirect identifier in an entry of the one or more routing table data structures corresponding to the candidate path is set to indicate that indirect routing of data across the candidate path is prohibited, then the candidate path is not considered for selection as the selected path to be used to transmit the data from the first processor to the destination processor.

18. The system of claim 15, wherein each entry in the one or more routing table data structures comprises both a no-direct identifier field and a no-indirect identifier field, and wherein a no-indirect identifier field is set to indicate that a corresponding path cannot be used for indirect routing of data while the no-direct identifier field is not set indicating that the corresponding path can be used for direct routing of data.

19. The system of claim 15, wherein selecting a path from the identified one or more candidate paths for routing of the data to the destination processor further comprises determining if a setting is designated with header information included with the data, wherein the header information designates at least one of only using an indirect path or only using a direct path.

20. The system of claim 15, wherein path selection uses at least one of random selection, adaptive real-time selection, round-robin selection, or selection that is identified with the data.