Handling hot spots in interconnection networks

• US 20070076622A1
• Filed: 09/30/2005
• Published: 04/05/2007
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Mukherjee, Shubhendu
• Granted Patent: US 7,649,845 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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; and

determining if the transit time for at least one of the time-stamped packets exceeds a threshold for a source-destination pair associated with the at least one of the time-stamped packets.

2. The method of claim 1, further comprising detecting, at the destination, a hot spot in a network location remote to the destination if at least one of the time-stamped packets exceeds the threshold.

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

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

5. The method of claim 2, further comprising determining, at the destination, the network location of the hot spot based upon the received time-stamped packets.

6. 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.

7. The method of claim 6, further comprising 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.

8. 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 using time stamp information of at least selected ones of the received packets.

9. The apparatus of claim 8, wherein the router is to time stamp outgoing packets.

10. The apparatus of claim 8, 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.

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

12. The apparatus of claim 8, 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.

13. The apparatus of claim 12, wherein the router is to couple to a second router of a second processor.

14. The apparatus of claim 8, wherein the router is to determine location of the congestion via triangulation.

15. 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; and

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

16. The system of claim 15, wherein the router is to report the congestion to the multiple agents of the network.

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

18. The system of claim 17, 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.

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

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

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

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

23. 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.

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

25. The network of claim 24, wherein the interconnection network comprises a torus.

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

27. The network of claim 23, wherein the second router is to detect a hot spot in the network if the packet exceeds the threshold time.

28. The network of claim 27, wherein the second router is to determine a location of the hot spot based upon time stamp information of a plurality of packets received from multiple nodes in the network.

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

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

31. An article comprising a machine-readable storage medium including instructions that if executed by a machine enable the machine to perform a method comprising:

receiving packets in a plurality of routers of a network; and

determining congestion in the network in a distributed manner using at least one of the plurality of routers.

33. The article of claim 31, wherein the method further comprises calculating the transit time information using time stamp information in the packets.

32. The article of claim 32, wherein the method further comprises comparing transit time information regarding the packets received in each of the plurality of routers to corresponding threshold time information in each of the plurality of routers.

34. The article of claim 32, wherein the method further comprises triangulating a location of the congestion via the transit time information.

35. The article of claim 32, wherein the method further comprises communicating information regarding the congestion to source agents of the network.