Handling hot spots in interconnection networks

• US 7,649,845 B2
• Filed: 09/30/2005
• Issued: 01/19/2010
• Est. Priority Date: 09/30/2005
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Mukherjee, Shubhendu S.
• Primary Examiner(s): LY, ANH VU H
• Application Number:
  US11/241,329
• Publication Number:
  US 20070076622A1
• Time in Patent Office: 1,572 Days
• Field of Search: None
• US Class Current: 370/235
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A network may include an interconnection system which allows packets to transit from various sources to various destinations under control of routers. The routers may determine a transit time of packet transit from various sources to a given destination. This information may be used to detect a hot spot within the network. Other embodiments are described and claimed.

Claims

1. A method comprising:

receiving time-stamped packets from at least two sources at a destination of a network;

calculating a transit time for each of the time-stamped packets received from the corresponding source at the destination;

determining if the transit time for at least one of the time-stamped packets exceeds a threshold transit time for a source-destination pair associated with the at least one of the time-stamped packets, the threshold transit time stored in a table of a router of the destination, the table including a plurality of entries each including a source-destination pair and a threshold transit time; and

detecting, at the destination, a hot spot and a location of the hot spot in the network remote to the destination and the at least two sources if at least one of the time-stamped packets from the at least two sources exceeds the corresponding threshold transit time, based on the location of the at least two sources and the corresponding transit times.

2. The method of claim 1, further comprising communicating the hot spot detection to other agents of the network.

3. The method of claim 1, further comprising sending test communications from a source to the destination, the test communications including time stamp information.

4. The method of claim 1, further comprising determining, at the destination, the network location of the hot spot based upon the received time-stamped packets from the at least two sources.

5. The method of claim 1, further comprising setting up a table including threshold transit times for source-destination pairs in distributed routers of a plurality of destinations of the network, and determining congestion in the network via at least one of the distributed routers based on time-stamped packets received by the at least one distributed router.

24. The method of claim 2, further comprising communicating the hot spot detection via a dedicated hot spot indication packet.

25. The method of claim 1, further comprising detecting, at the destination, an imminent hot spot, and informing other agents of the network to route messages to avoid the imminent hot spot.

26. The method of claim 1, further comprising detecting the hot spot location using triangulation.

27. The method of claim 1, further comprising detecting the hot spot location based on the transmit times of a first time-stamped packet from a first source to the destination, the first source and the destination having a first minimum rectangle therebetween, and a second time-stamped packet from a second source to the destination, the second source and the destination having a second minimum rectangle therebetween.

6. An apparatus comprising:

a core to perform instructions; and

a router coupled to the core to receive packets from a plurality of sources of a network and to detect congestion at a location of the network remote to the apparatus via triangulation using transit time information of received packets from at least a first source and a second source, based on the location of the first and second sources and transit times for the received packets, wherein the router includes a table having a plurality of threshold times, each of the plurality of threshold times corresponding to a transit time from a source to the router, and the router is to determine a location of the congestion if at least one of the transit times of the received packets from the at least first and second sources exceeds the corresponding threshold time, based on the location of the at least first and second sources and the corresponding transit times.

7. The apparatus of claim 6, wherein the router is to time stamp outgoing packets.

8. The apparatus of claim 6, wherein the router is to compare the transit time information of a packet from a first source to the router with a threshold time of the table for the first source.

9. The apparatus of claim 6, wherein the apparatus comprises a processor, the processor further comprising a memory controller coupled to the router and to the core, the memory controller to communicate with a memory.

10. The apparatus of claim 9, wherein the router is to couple to a second router of a second processor.

11. A system comprising:

a processor core;

a router coupled to the processor core to determine the transit time of packets received by the router from multiple agents of a network, and to determine if congestion exists at a location remote to the router, wherein the router is to detect the congestion if the transit time of at least one of the packets exceeds a threshold time, and to determine the location of the congestion based upon transit time information of a plurality of packets received from the multiple agents of the network and an intersection of minimum rectangles between an agent including the router and the multiple agents, respectively; and

a dynamic random access memory (DRAM) coupled to the processor core.

12. The system of claim 11, wherein the router is to populate a table with threshold agent-to-router transit times.

13. The system of claim 12, wherein the router is to compare the transit time of a first packet received from a first agent to an entry in the table corresponding to the first agent to determine if the threshold agent-to-router transit time was exceeded.

14. The system of claim 11, wherein the router is to time stamp outgoing packets with a network injection time.

15. The system of claim 11, wherein the router is to send test messages to at least one agent with which it does not communicate data packets.

16. The system of claim 11, wherein each of the multiple agents includes a router, each of the routers is to locally detect a global hot spot in the network.

17. The system of claim 16, wherein the routers are to perform the global hot spot detection in a distributed manner.

18. A network comprising:

a first node having a first processor and a first router;

a second node coupled to the first node, the second node having a second processor and a second router, the second router to compare a transit time for a packet received by the second router to a threshold time for a source of the packet; and

an interconnect to couple to the first node and the second node, wherein the second router is to detect a hot spot in the network if the transit time for the packet exceeds the threshold time, and to determine a location of the hot spot based upon transit time information of a plurality of packets received from a plurality of nodes of the network and an intersection of minimum rectangles between the second node and the plurality of nodes, respectively.

19. The network of claim 18, wherein the network comprises an interconnection network to connect the plurality of nodes including the first node and the second node.

20. The network of claim 19, wherein the interconnection network comprises a torus.

21. The network of claim 19, wherein the interconnection network comprises a plurality of point-to-point interconnects to couple the plurality of nodes to each other.

22. The network of claim 18, wherein the second router is to communicate the hot spot detection to the first node.

23. The network of claim 22, wherein the first router is to transmit a packet to the second node via a different path upon receipt of the communication.