Providing a notification including location information for nodes in an overlay network

• US 7,483,391 B2
• Filed: 09/19/2003
• Issued: 01/27/2009
• Est. Priority Date: 09/19/2003
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Xu, Zhichen, Tang, Chunqiang
• Primary Examiner(s): Chan; Wing F
• Assistant Examiner(s): ROBERTS, BRIAN S
• Application Number:
  US10/666,620
• Publication Number:
  US 20050063318A1
• Time in Patent Office: 1,957 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1055 involving connection limits involving dynamic management of active down- or uploading connections H04L67/1085
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

An overlay network is used to logically represent an underlying physical network. A network condition is monitored by a node in a target region of the network. If the network condition occurs, the node transmits a notification to a source node including location information for nodes physically close in the physical network. The source node may select a routing node in the target region based on the location information.

Claims

1. A method of maintaining proximity information in an overlay network, wherein the overlay network is a logical representation of a physical network, the method comprising:

determining whether a network condition occurred, the network condition being associated with a region in the overlay network;

determining distances of each of a first plurality of nodes in the physical network to each of a second plurality of landmark nodes in the physical network, the first plurality of nodes comprising a first node, and the landmark nodes being different from the first plurality of nodes;

storing a proximity information in the region, wherein the proximity information includes locations of the first plurality of nodes the physical network;

updating the proximity information stored in the region if a change associated with the first plurality of nodes in the physical network occurred; and

transmitting the proximity information to the first node operable to route a message to the region in response to the network condition occurring, wherein the first node obtains the distances of each of the first plurality of nodes to each of the second plurality of landmark nodes.

2. The method of claim 1, further comprising:

selecting a routing node in the region based on the proximity information transmitted to the first node;

determining whether the selected routing node is different than a previously selected routing node for the region; and

placing the selected muting node in a routing table for the first node in response to the selected routing node being different than the previously selected routing node.

3. The method of claim 2, wherein selecting a routing node comprises identifying a node in the region physically closest to the first node based on the proximity information transmitted to the first node.

4. The method of claim 1, wherein the network condition comprises one or more of a predetermined number of nodes joining the region;

a predetermined number of nodes departing from the region;

a lapsing of a predetermined period of time, a load of a node in the region exceeding a threshold or falling below a threshold, and a forward capacity of the node in the region filling below a threshold.

5. The method of claim 1, further comprising the first node identifying the network condition to be monitored.

6. The method of claim 1, further comprising generating the proximity information stored in the region by determining distances of substantially all the nodes in the overlay network to landmark nodes.

7. The method of claim 1, wherein storing the proximity information further comprises:

determining points in the overlay network used to store the proximity information by mapping the locations of the first plurality of nodes in the physical network to logical points in the overlay network using a space-filling curve.

8. The method of claim 1, wherein transmitting the proximity information further comprises transmitting at least one measured network metric for a node in the region and the proximity information to the first node.

9. The method of claim 8, further comprising selecting a routing node for the region based on one or more of the at least one measured network metric and the proximity information.

10. A. method comprising:

selecting a target node in a region in an overlay network, the overlay network being a logical representation of a physical network;

determining a network condition to be monitored by the target node; and

receiving at a source node a notification front the target node including a map for the region in response to the target node detecting tile network condition, the map including distances of each of a first plurality of nodes in the physical network to each of a second plurality of landmark nodes in the physical network, the first plurality of nodes comprising the source node and the target node and the landmark nodes being different from the first plurality of nodes.

11. The method of claim 10, wherein the notification further comprises at least one network metric associated with the target node.

12. The method of claim 11, wherein the network metric comprises at least one of nodes joining the region;

nodes departing from the region;

a lapsing of a predetermined period of time, a load of the target node, and a forward capacity of the target node.

13. The method of claim 11, further comprising determining a routing node for the region based on at least one of the map and the at least one network metric.

14. The method of claim 13, wherein determining a routing node for the region further comprises:

determining a physically closest node closest to the source node in the physical network based on the map; and

selecting the physically closest node as a routing node for the region.

15. A system comprises a first plurality of nodes connected via at least one physical network, wherein an overlay network logically represents the physical network of the system, the system comprising:

a target node in a target region in the overlay network, the target node being operable to determine whether a predetermined network condition occurred and transmit a notification to a source node in response to the network condition on occurring; and

the source node being operable to receive the notification comprising distances of each of the first plurality of nodes in the physical network to each of a second plurality of landmark nodes in the physical network, the first plurality of nodes comprising the source node, and the target node and the landmark nodes being different from the first plurality of nodes, and the source node being further operable to select a routing node in the target region based on the received notification.

16. The system of claim 15, wherein the routing node is a node in the target region physically closest to the source node.

17. The system of claim 15, wherein the notification comprises at least one network metric measured by the target node, the source node being operable to select the routing node based on the at least one network metric.

18. The system of claim 17, wherein the at least one network metric comprises at least one of nodes joining the target region;

nodes departing from the target region;

a lapsing of a predetermined period of time, a load of the target node, and a forward capacity of the target node.

19. The system of claim 15, wherein the source node is operable to transmit a message to the target node identifying the network condition.

20. The system of claim 15, wherein the overlay network comprises a distributed hash table overlay network.

21. The system of claim 20, wherein the overlay network comprises an cCAN overlay network, and the source node is an expressway routing node operable to select an expressway routing node in the region.

22. A node in an overlay network, wherein the overlay network is a logical representation of a physical network, the node comprising:

means for selecting a target node in a target region in the overlay network;

means for determining a network condition to be monitored by the target node; and

means for receiving a notification from the target node including a map for the region, wherein the map includes distances of each of a first plurality of nodes in the physical network to each of a second plurality of landmark nodes in the physical network, the first plurality of nodes comprising the node and the target node, and the landmark nodes being different from the first plurality of nodes.

23. The node of claim 22, further comprising:

means for determining first proximity information associated with a location of the node in the network;

means for searching through the map using the first proximity information; and

means for identifying a routing node in the target region based on the searching through the map, wherein the routing node is a node in the target region physically closest to the node relative to other nodes in the region.

24. The node of claim 23, wherein the node comprises means for storing a routing table, wherein the routing table includes information identifying the routing node.

25. The node of claim 22, wherein the notification further includes at least one measured network metric, and the means for identifying a routing node is operable to identify the routing node based on the at least one measured network metric.