System and method for efficient network reconfiguration in fat-trees

A system for supporting efficient reconfiguration of an interconnection network having a pre-existing routing comprising:

• one or more computers, each computer comprising a microprocessor;
• a subnet, the subnet comprising:
• a plurality of switches, each switch comprising a linear forwarding table, of a plurality of linear forwarding tables, configured according to the pre-existing routing and
• a plurality of end nodes, wherein each of the plurality of end nodes is connected to the subnet via a link, of a plurality of links, wherein each of the plurality of links is assigned a maximum count;
• wherein a reconfiguration triggering event is detected, the reconfiguration triggering event comprising an addition of a new end node to the subnet,
• wherein a new routing for the interconnection network is computed, wherein the computing of the new routing for the interconnection network takes into consideration the pre-existing routing, and wherein the computing the new routing ensures that the maximum count is not exceeded for any of the plurality of links;
• and
• wherein at least one linear forwarding table is updated according to the new routing for the interconnection network.

A non-transitory computer readable storage medium, including instructions stored thereon for supporting efficient reconfiguration of an interconnection network having a pre-existing routing, which when read and executed by one or more computers cause the one or more computers to perform steps comprising:

• providing, the one or more computers, including one or more microprocessors, the subnet, the subnet comprising:
• a plurality of switches, each switch comprising a linear forwarding table, of a plurality of linear forwarding tables, configured according to the pre-existing routing and
• a plurality of end nodes, wherein each of the plurality of end nodes is connected to the subnet via a link, of a plurality of links, wherein each of the plurality of links is assigned a maximum count;
• detecting a reconfiguration triggering event, the reconfiguration triggering event comprising an addition of a new end node to the subnet,
• computing a new routing for the interconnection network, wherein the computing of the new routing for the interconnection network takes into consideration the pre-existing routing, and wherein the computing the new routing ensures that the maximum count is not exceeded for any of the plurality of links;
• and
• updating at least one linear forwarding table according to the new routing for the interconnection network.