Evaluating the Available Bandwidth between Leaf Switches in a Fat-Tree Network

A method for estimation, bandwidth the method comprising:

• receiving topology information indicative of a current topology of a fat-tree (FT) network, the FT network comprising a plurality of switches comprising (i) multiple leaf switches belonging to a bottom level, (ii) multiple spine switches belonging to a top level and (iii) multiple intermediate switches belonging to one or more intermediate levels between the top level and the bottom level, and multiple links connecting between selected ones of the switches;
• and
• based on the topology information, estimating an available bandwidth between first and second leaf switches, by:
• from among a plurality of bottom-to-top sub-trees of the FT network each extending from a leaf switch to the top level, identifying a first bottom-to-top sub-tree to which the first leaf switch belongs, and a second bottom-to-top sub-tree to which the second leaf switch belongs;
• determining path counts for at least some of the switches in the intermediate levels, wherein a path count for a switch is indicative of a number of paths that each (i) passes via the switch, (ii) reaches the first leaf switch via the first bottom-to-top sub-tree and (iii) reaches the second leaf switch via the second bottom-to-top sub-tree;
• and
• estimating the available bandwidth between the first and second leaf switches based on the path counts.

A computer software product, the product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a processor, cause the processor to:

• receive topology information indicative of a current topology of a fat-tree (FT) network, the FT network comprising a plurality of switches comprising (i) multiple leaf switches belonging to a bottom level, (ii) multiple spine switches belonging to a top level and (iii) multiple intermediate switches belonging to one or more intermediate levels between the top level and the bottom level, and multiple links connecting between selected ones of the switches;
• and
• based on the topology information, estimate an available bandwidth between first and second leaf switches, by:
• from among a plurality of bottom-to-top sub-trees of the FT network each extending from a leaf switch to the top level, identifying a first bottom-to-top sub-tree to which the first leaf switch belongs, and a second bottom-to-top sub-tree to which the second leaf switch belongs;
• determining path counts for at least some of the switches in the intermediate levels, wherein a path count for a switch is indicative of a number of paths that each (i) passes via the switch, (ii) reaches the first leaf switch via the first bottom-to-top sub-tree and (iii) reaches the second leaf switch via the second bottom-to-top sub-tree;
• and
• estimating the available bandwidth between the first and second leaf switches based on the path counts.