Bandwidth On-Demand Adaptive Routing

• US 20140269324A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics International Corporation (Hewlett-Packard Enterprise Company)
• Inventors: Fromm, Eric C., Tietz, Joseph George, Thorson, Gregory Michael
• Granted Patent: US 9,237,093 B2
• Time in Patent Office: Days
• US Class Current: 370/237
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities

Abstract

An adaptive router anticipates possible future congestion and enables selection of an alternative route before the congestion occurs, thereby avoiding the congestion. The adaptive router may use a primary route until it predicts congestion will occur. The adaptive router measures packet traffic volume, such as flit volume, on a primary network interface to anticipate the congestion. The adaptive router maintains a trailing sum of the number of flits handled by the primary network interface over a trailing time period. If the sum exceeds a threshold value, the adaptive router assumes the route will become congested, and the adaptive router enables considering routing future packets, or at least the current packet, over possible secondary routes.

Claims

1. A computer system comprising:

a first computer comprising;

a memory;

a processor coupled to the memory and configured to execute instructions fetched from the memory;

a plurality of network ports, each network port of the plurality of network ports configured to be connectable, via a respective link, to a respective network port on another computer of the computer system;

an adaptive router coupled to the memory, the processor and the plurality of network ports and configured to;

utilizing packets sent via a port of the plurality of network ports and its respective link, provide non-uniform memory access to the memory by a processor on the another computer and provide non-uniform memory access to memory on the another computer by the processor on the first computer;

for each network port of the plurality of network ports, store information associating the network port with at least one of the plurality of network ports as an at least one secondary network port;

accumulate historical information about an amount of data transferred via each port of the plurality of network ports; and

automatically select, per packet, based at least in part on the historical information and independent of any information about congestion related to any port of the plurality of network ports, whether to consider using one of the at least one secondary network port, over which to send the packet.

2. A computer system as recited in claim 1, wherein the stored information associating the at least one secondary network port is programmable.

3. A computer system as recited in claim 1, wherein, if the adaptive router selects to consider using one of the at least one secondary network port, the adaptive router is configured to:

identify a primary network port, based on at least a portion of a destination address within the packet; and

automatically select one port from at least one secondary network port associated with the primary network port, over which to send the packet.

4. A computer system as recited in claim 1, wherein, if the adaptive router selects to consider using one of the at least one secondary network port, the adaptive router is configured to automatically select one port from:

a port (a “

primary network port”

) of the plurality of network ports, based on at least a portion of a destination address within the packet, and

at least one secondary network port associated with the primary network port,

over which to send the packet.

5. A computer system as recited in claim 4, wherein, if the packet contains a routing limitation flag, the adaptive router is configured to select the primary network port.

6. A computer system as recited in claim 4, wherein the adaptive router is configured to select the primary network port, if at least a portion of a destination address within the packet meets a predetermined criterion.

7. A computer system as recited in claim 4, wherein the adaptive router is configured to consider only a subset of the at least one secondary network port associated with the primary network port, if at least a portion of a destination address within the packet meets a predetermined criterion, wherein the subset is based on at least a portion of the destination address within the packet.

8. A computer system as recited in claim 4, wherein during each time unit, at most a portion of a packet (a “

flit”

), less than the entire packet, is sent via the port.

9. A computer system as recited in claim 1, wherein:

the historical information comprises, per port of the plurality of network ports, for each time unit of a plurality of preceding time units, information indicating whether at least a portion of any packet was sent via the port during the time unit; and

the adaptive router is configured to;

identify a primary network port, based on at least a portion of a destination address within the packet; and

if the historical information for the primary network port does not exceed a predetermined threshold value, select the primary network port, over which to send the packet, otherwise consider using an at least one secondary network port associated with the primary network port, over which to send the packet.

10. A computer system as recited in claim 9, wherein, if a port of the at least one secondary network port has become congested, the adaptive router is configured not to select the port.

11. A computer system as recited in claim 1, wherein, if the adaptive router selects to consider using one of the at least one secondary network port, the adaptive router is configured to select which port of the plurality of network ports over which to send the packet, based at least in part on at least one of:

the historical information; and

information about congestion related to a port of the plurality of network ports.

12. A computer system as recited in claim 11, wherein the adaptive router is configured to use at least a portion of a destination address in the packet to determine which of the historical information and the information about congestion is used to select which port of the plurality of network ports over which to send the packet.

13. A computer system as recited in claim 1, wherein, if the adaptive router selects to consider using one of the at least one secondary network port, the adaptive router is configured to automatically select which port of the plurality of network ports over which to send the packet according to a round-robin selection scheme.

14. A computer system as recited in claim 1, wherein, if the adaptive router selects to consider using one of the at least one secondary network port, the adaptive router is configured to automatically select which port of the plurality of network ports over which to send the packet according to a congestion avoidance scheme.

15. A computer system as recited in claim 1, wherein the historical information comprises a trailing sum.

16. A method for routing packets within a computer system that includes a first computer having a memory, a processor coupled to the memory and configured to execute instructions fetched from the memory, a plurality of network ports, each network port of the plurality of network ports being configured to be connectable, via a respective link, to a respective network port on another computer of the computer system, wherein the first computer is configured to utilize packets sent via a port of the plurality of network ports and its respective link to provide non-uniform memory access to the memory by a processor on the another computer and to provide non-uniform memory access to memory on the another computer by the processor on the first computer, the method comprising:

for each network port of the plurality of network ports, storing information associating the network port with at least one of the plurality of network ports as an at least one secondary network port;

accumulating historical information about an amount of data transferred via each port of the plurality of network ports; and

automatically selecting, per packet, based at least in part on the historical information and independent of any information about congestion related to any port of the plurality of network ports, whether to consider using one of the at least one secondary network port, over which to send the packet.

17. A method according to claim 16, wherein if consideration of using one of the at least one secondary network port has been selected:

identifying a primary network port, based on at least a portion of a destination address within the packet; and

automatically selecting one port from at least one secondary network port associated with the primary network port, over which to send the packet.

18. A method according to claim 16, if consideration of using one of the at least one secondary network port has been selected, selecting one port from:

a port (a “

primary network port”

) of the plurality of network ports, based on at least a portion of a destination address within the packet, and

at least one secondary network port associated with the primary network port,

over which to send the packet.

19. A method according to claim 18, further comprising, if the packet contains a routing limitation flag, selecting the primary network port, over which to send the packet.

20. A method according to claim 18, further comprising selecting the primary network port, if at least a portion of a destination address within the packet meets a predetermined criterion.

21. A method according to claim 18, further comprising considering only a subset of the at least one secondary network port associated with the primary network port, if at least a portion of a destination address within the packet meets a predetermined criterion, wherein the subset is based on at least a portion of the destination address within the packet.

22. A method according to claim 18, further comprising, during each time unit, sending at most a portion of a packet (a “

flit”

), less than the entire packet, via the port.

23. A method according to claim 16, wherein the historical information comprises, per port of the plurality of network ports, for each time unit of a plurality of preceding time units, information indicating whether at least a portion of any packet was sent via the port during the time unit;

and further comprising;

identifying a primary network port, based on at least a portion of a destination address within the packet; and

if the historical information for the primary network port does not exceed a predetermined threshold value, selecting the primary network port, over which to send the packet, otherwise consider using an at least one secondary network port associated with the primary network port, over which to send the packet.

24. A method according to claim 23, wherein if a port of the at least one secondary network port has become congested, not selecting the port.

25. A method according to claim 16, wherein, if consideration of using one of the at least one secondary network port has been selected, selecting which port of the plurality of network ports over which to send the packet, based at least in part on at least one of:

the historical information; and

information about congestion related to a port of the plurality of network ports.

26. A method according to claim 25, using at least a portion of a destination address in the packet to determine which of the historical information and the information about congestion is used to select which port of the plurality of network ports over which to send the packet.

27. A method according to claim 16, wherein if consideration of using one of the at least one secondary network port has been selected, automatically selecting which port of the plurality of network ports over which to send the packet according to a round-robin selection scheme.

28. A method according to claim 16, wherein if consideration of using one of the at least one secondary network port has been selected, automatically selecting which port of the plurality of network ports over which to send the packet according to a congestion avoidance scheme.

29. A method according to claim 16, wherein accumulating the historical information comprises accumulating a trailing sum.