System and method of computing ethernet routing paths

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.

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.