Bandwidth on-demand adaptive routing

• US 9,237,093 B2
• Filed: 03/14/2013
• Issued: 01/12/2016
• 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: Tietz, Joseph George, Thorson, Gregory Michael, Fromm, Eric C.
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US13/830,432
• Publication Number:
  US 20140269324A1
• Time in Patent Office: 1,034 Days
• Field of Search: None
• US Class Current: 1/1
• 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 to execute instructions fetched from the memory;

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

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

utilizes 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 provide non-uniform memory access to memory on the another computer by the processor on the first computer;

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

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

automatically determines, 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 sending the packet via one of the at least one secondary network port.

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 the adaptive router performs the following, if the adaptive router selects to consider using one of the at least one secondary network port:

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 the adaptive router automatically selects 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, if the adaptive router selects to consider using one of the at least one secondary network port.

5. Currently amended) A computer system as recited in claim 4, wherein the adaptive router selects the primary network port, if the packet contains a routing limitation flag.

6. A computer system as recited in claim 4, wherein the adaptive router selects 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 considers 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;

identifies 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, selects the primary network port, over which to send the packet, otherwise considers 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 the adaptive router does not select the port, if a port of the at least one secondary network port has become congested.

11. A computer system as recited in claim 1, wherein the adaptive router selects, if the adaptive router selects to consider using one of the at least one secondary network port, 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 uses 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 the adaptive router automatically selects which port of the plurality of network ports over which to send the packet according to a round-robin selection scheme, if the adaptive router selects to consider using one of the at least one secondary network port.

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

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

16. A method for routing packets, the method comprising:

by a computer system that includes a first computer having a memory, a processor coupled to the memory to execute instructions fetched from the memory, a plurality of network ports, each network port of the plurality of network ports being connectable, via a respective link, to a respective network port on another computer of the computer system, wherein the first computer utilizes 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, for at least one network port of the plurality of network ports, storing information associating the network port with at least one other network port 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 sending the packet via one of the at least one secondary network port.

17. A method according to claim 16, further comprising, 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, 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 if consideration of using one of the at least one secondary network port has been selected.

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

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, further comprising not selecting the port, if a port of the at least one secondary network port has become congested.

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

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

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