Method for distributing multipath flows in a direct interconnect network

1 . A method of routing a flow of packets from a source node to a destination node, the method comprising:

(a) commencing routing packets in a flow of packets from a source node to a destination node along multiple pathways, and including metadata with the packets describing the routing distribution of the packets along the multiple pathways, said metadata comprising a number of packets sent on each pathway within the multiple pathways, a Last Round Distribution (LRD) vector indicating paths used in a previous round of packet distribution, and a Round Sequence Number (RSN) that is incremented with each new round;

(b) monitoring relative packet skew between the multiple pathways at the destination node, wherein the destination node counts the number of packets that arrive on each pathway within the multiple pathways, compares the number of packets that arrive on each pathway to the number of packets sent on each pathway as per the metadata, and determining path skew status based on this comparison, wherein the path skew status comprises per-path skew counter values that are incremented based on the LRD for packets sent on each path and decremented for packets arriving on each path;

(c) using a backwards multipath control flit mechanism to send the path skew status from the destination node to the source node; and

(d) implementing a weighted path distribution mechanism at the source node to dynamically reduce the use of or avoid any skewed pathways in the multiple pathways when routing packets from the source node to the destination node along multiple pathways.

2 . The method of claim 1 , wherein the LRD vector is a bit vector comprising one bit per pathway within the multiple pathways, each bit being set to indicate that a packet was sent on the corresponding pathway during the previous round of packet distribution and unset to indicate that no packet was sent on that pathway during the previous round.

3 . The method of claim 1 , wherein the destination node maintains an RSN tracking window comprising a bitmap in which each bit corresponds to a respective RSN value, wherein, upon receipt of a packet carrying an LRD for a given round, the destination node:

(a) marks the round as accepted for the corresponding RSN in the tracking window,

(b) consumes only the first LRD received for each round regardless of which pathway it arrived on, and

(c) ignores any subsequently received LRDs carrying the same RSN.

4 . The method of claim 1 , wherein determining path skew status further comprises, upon detection by a lost-packet mechanism that a packet has been lost on a given pathway, decrementing the per-path skew counter for that pathway, such that a declared lost packet is treated as equivalent to an arriving packet for purposes of skew counter accounting.

5 . The method of claim 1 , further comprising resetting all per-path skew counters at the destination node to an initial value when a reorder window is first allocated for the flow of packets.

6 . The method of claim 1 , wherein using a backwards multipath control flit mechanism to send the path skew status further comprises periodically transmitting the current per-path skew counter values from the destination node to the source node in successive multipath control flits.

7 . The method of claim 1 , wherein implementing a weighted path distribution mechanism comprises:

(a) maintaining a per-path weight value for each pathway within the multiple pathways; comparing the per-path skew counter value received from the destination node for each pathway to a programmable minimum skew threshold; and

(b) setting the per-path weight value for a pathway to zero when the per-path skew counter value for that pathway exceeds a programmable maximum skew threshold, such that the source node ceases routing packets on that pathway.

8 . The method of claim 7 , wherein maintaining a per-path weight value further comprises:

(a) ramping the per-path weight value upward toward a maximum weight on each successive multipath control flit update when the per-path skew counter value for that pathway is at or below the programmable minimum skew threshold; and

(b) ramping the per-path weight value downward toward a minimum weight on each successive multipath control flit update when the per-path skew counter value for that pathway exceeds the programmable minimum skew threshold.

9 . The method of claim 1 , further comprising:

(a) monitoring at the destination node whether the per-path skew counter value for any pathway within the multiple pathways exceeds a programmable excessive skew threshold; and

(b) upon determining that the per-path skew counter value for a pathway exceeds the programmable excessive skew threshold, transmitting a restart request from the destination node to the source node via the backwards multipath control flit mechanism to reset the multipath flow.

10 . The method of claim 1 , wherein the backwards multipath control flit mechanism additionally carries a Credit Packet Sequence Number (CPSN) from the destination node to the source node, said CPSN indicating the packet sequence number of the last packet read from a receive packet buffer memory at the destination node.

11 . The method of claim 10 , further comprising:

(a) at the source node, comparing the CPSN received from the destination node to a latest packet sequence number for packets sent from the source node to the destination node; and

(b) using the difference between the CPSN and the latest packet sequence number as a measure of the number of packets queued in the source node, in-flight in the network, or queued in a destination node reorder window, to limit the total number of packets committed to be routed along the multiple pathways and prevent overflow of the reorder window at the destination node.