System and method of computing ethernet routing paths

1. A method of routing in a computational grid arranged in a fat-tree, the method comprising:

performing preprocessing by processing circuitry, including:

determining a type of topology of the fat-tree, the fat-tree having a plurality of levels, each level including a plurality of switches and a bottom level of switches having attached hosts,

storing a switch level and a switch group for each switch,

storing links between the switches,

storing links between the switches and the hosts, and

storing fat-tree type of the fat-tree;

performing base path routing, by the processing circuitry, to determine rules for routing in switches based on the stored switch level, switch group, links between switches, links between switches and hosts, and fat-tree type; and

performing run-time processing by the processing circuitry, including:

detecting a path fault, and

determining at least one redundant path for the path fault,

wherein the base path routing determines a first rule that specifies a certain destination in every switch,

wherein the run-time processing further performs searching for a first match between a packet and a source-destination pair, and when the first match is not found, performs searching for a second match between the packet and the first rule that specifies the certain destination, and

wherein the determining at least one redundant path further includes:

determining an ideal port counter for an expected number of traversals for each port in a switch;

removing all paths affected by the path fault:

removing other paths when an actual general port counter is greater than the ideal port counter;

decreasing an actual general port counter as a result of removing all the paths affected by the path fault;

comparing the actual general port counter and the ideal port counter in bottom switches of the fat-tree;

removing paths in the bottom switches of the fat-tree until the actual general port counter is equal to the ideal port counter, the removing paths including

removing first paths in the bottom switches when the general port counter in a next hop is lower than the ideal port counter in a present hop, and

removing second paths in other switches rather than a bottom switch until the actual general port counter is equal to the ideal port counter; and

adding new paths through different switch ports to replace the removed second paths.

2. The method of claim 1 , wherein the determining redundant paths further includes:

determining an ideal port counter for a number of traversals of a given port after at least one fault;

comparing the ideal port counter with an actual general port counter; and

replacing the faulty path with a new path through a different switch-port based on the comparison between the ideal port counter and the actual general port counter,

wherein the new path includes non-faulty paths.

3. The method of claim 1 , wherein the processing circuitry determines the ideal port counter based on differences in a number of upwards ports for different switches in a same switch level and based on a number of hosts in every different destination switch in the same switch level.

4. The method of claim 1 , wherein the processing circuitry performs the base path routing by searching in order of switches having largest to smallest number of hosts, and

wherein the searching is by order of port number in a destination switch.

5. The method of claim 4 , wherein a general port counter is increased as the base path routing is performed by the searching of switches having largest to smallest number of hosts in three level fat-trees when routing between different subgroups.

6. The method of claim 1 , wherein the fat-tree is a three-level fat-tree that includes a plurality of different subgroups, and

wherein the processing circuitry performs base path routing in accordance with two-level fat-tree routing in each subgroup.

7. The method of claim 4 , wherein the processing circuitry performs the base path routing such that the searching from a source switch having a largest number of hosts includes matching only a destination of a packet, and

wherein the base path routing is performed such that searching from a source switch having less than the largest number of hosts includes matching both a source and the destination of the packet in three level fat-trees when routing between different subgroups.

8. The method of claim 1 , wherein the adding new paths through different switch ports further includes:

comparing real port counters, ideal port counters, and a best next port counter, and

wherein the best next port counter is a best port counter in a next switch reached through a current port.

9. The method of claim 8 , wherein the adding new paths through different switch ports further includes:

selecting a port as a best port in which a real port counter is not larger than the ideal port counter by a percentage of the real port counter.

10. A device for routing in a computational grid arranged in a fat-tree, the device comprising:

processing circuitry configured to

perform preprocessing including:

determining a type of topology of the fat-tree, the fat-tree having a plurality of levels, each level including a plurality of switches and a bottom level of switches having attached hosts,

storing a switch level and a switch group for each switch,

storing links between the switches,

storing links between the switches and the hosts, and

storing fat-tree type of the fat-tree;

perform base path routing to determine rules for routing in switches based on the stored switch level, switch group, links between switches, links between switches and hosts, and fat-tree type; and

perform run-time processing, including:

detecting a path fault, and

determining at least one redundant path for the path fault,

wherein the base path routing determines a first rule that specifies a certain destination in every switch,

wherein the run-time processing further performs searching for a first match between a packet and a source-destination pair, and when the first match is not found, performs searching for a second match between the packet and the first rule that specifies the certain destination, and

wherein the determining of at least one redundant path for the path fault in the run-time processing further includes:

determining an ideal port counter for an expected number of traversals for each port in a switch;

removing all paths affected by the path fault;

removing other paths when an actual general port counter is greater than the ideal port counter;

decreasing an actual general port counter as a result of removing all the paths affected by the path fault;

comparing the actual general port counter and the ideal port counter in bottom switches of the fat-tree;

removing paths in the bottom switches of the fat-tree until the actual general port counter is equal to the ideal port counter, the removing paths including

removing first paths when the actual general port counter in a next hop is lower than the ideal port counter in that hop, and

removing second paths in other switches rather than a bottom switch until the actual general port counter is equal to the ideal port counter; and

adding new paths through different switch-ports to replace the removed second paths.

11. The device of claim 10 , wherein the processing circuitry determining redundant paths further includes:

determining an ideal port counter for a number of traversals of a given port after at least one fault;

comparing the ideal port counter with an actual general port counter; and

replacing the faulty path with a new path through a different switch-port based on the comparison between the ideal port counter and the actual general port counter,

wherein the new path includes non-faulty paths.

12. The device of claim 10 , wherein the processing circuitry performs the base path routing by searching in order of switches having largest to smallest number of hosts, and

wherein the searching is by order of port number in a destination switch.

13. The device of claim 12 , wherein a general port counter is increased as the base path routing is performed by the searching of switches having largest to smallest number of hosts in three level fat-trees when routing between different subgroups.

14. The device of claim 10 , wherein the fat-tree is a three-level fat-tree that includes a plurality of different subgroups, and

wherein the processing circuitry performs base path routing in accordance with two-level fat-tree routing in each subgroup.

15. The device of claim 12 , wherein the processing circuitry performs base the path routing such that the searching from a source switch having a largest number of hosts includes matching only a destination of a packet, and

wherein the base path routing is performed such that searching from a source switch having less than the largest number of hosts includes matching both a source and the destination of the packet in three level fat-trees when routing between different subgroups.

16. The device of claim 10 , wherein the adding new paths through different switch-ports further includes:

comparing real port counters, ideal port counters, and a best next port counter, and

wherein the best next port counter is a best port counter in the next switch reached through a current port.

17. The device of claim 16 , wherein the adding new paths through different switch-ports further includes:

selecting a port as a best port in which an actual general port counter is not larger than the ideal port counter by a percentage of the actual general port counter.

18. A non-transitory computer readable medium having stored thereon a program that when executed by a computer causes the computer to implement a method of routing in a computational grid arranged in a fat-tree, the method comprising:

performing preprocessing by processing circuitry, including:

determining a type of topology of the fat-tree, the fat-tree having a plurality of levels, each level including a plurality of switches and a bottom level of switches having attached hosts,

storing a switch level and a switch group for each switch,

storing links between the switches,

storing links between the switches and the hosts, and

storing fat-tree type of the fat-tree;

performing base path routing to determine rules for routing in switches based on the stored switch level, switch group, links between switches, links between switches and hosts, and fat-tree type; and

performing run-time processing by the processing circuitry, including:

detecting a path fault, and

determining at least one redundant path for the path fault,

wherein the base path routing determines a first rule that specifies a certain destination in every switch,

wherein the run-time processing further performs searching for a first match between a packet and a source-destination pair, and when the first match is not found, performs searching for a second match between the packet and the first rule that specifies the certain destination, and

wherein the determining at least one redundant path further includes:

determining an ideal port counter for an expected number of traversals for each port in a switch;

removing all paths affected by the path fault;

removing other paths when an actual general port counter is greater than the ideal port counter;

decreasing an actual general port counter as a result of removing all the paths affected by the path fault;

comparing the actual general port counter and the ideal port counter in bottom switches of the fat-tree;

removing paths in the bottom switches of the fat-tree until the actual general port counter is equal to the ideal port counter, the removing paths including

removing first paths in the bottom switches when the general port counter in a next hop is lower than the ideal port counter in a present hop, and

removing second paths in other switches rather than a bottom switch until the actual general port counter is equal to the ideal port counter; and

adding new paths through different switch ports to replace the removed second paths.