Method and apparatus for mapping peers to an overlay network

• US 20040143666A1
• Filed: 01/17/2003
• Published: 07/22/2004
• Est. Priority Date: 01/17/2003
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Zhang, Zheng, Xu, Zhichen
• Granted Patent: US 7,953,858 B2
• Time in Patent Office: Days
• US Class Current: 709/227
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• 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/1046 Joining mechanisms
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

In a method of mapping peers in a peer-to-peer network to an overlay network, network coordinates are determined for a selected peer. The logical coordinates in the overlay network are determined based on the network coordinates. A zone is determined based on the logical coordinates. The network coordinates, a network address of the selected peer and the zone is stored as an object at a peer owning the zone, where associated information is stored in the peer that has the network coordinate and using the network coordinate as a key.

Claims

1. A method of mapping peers in a peer-to-peer network to an overlay network;

said method comprising;

determining network coordinates for a selected peer;

determining logical coordinates in said overlay network based on said network coordinates;

determining a zone based on said logical coordinates; and

storing an object comprising said network coordinates, a network address of said selected peer, and said zone in a peer owning said zone, whereby associated information is stored in said peer that has said network coordinates and using said network coordinates as a key.

2. The method according to claim 1, further comprising:

storing a plurality of objects at said peer owning said zone; and

forming a coordinate map based on said plurality of objects.

3. The method according to claim 2, further comprising:

receiving said coordinate map from said peer owning said zone in response to a routing request from a candidate peer.

4. The method according to claim 3, further comprising:

determining a closest peer in a neighboring zone based on said received coordinate map, said candidate peer being physically closest to said candidate peer.

5. The method according to claim 1, wherein said determination of said plurality of network coordinates further comprises:

determining a plurality of landmark vectors based on a set of landmark peers, each network coordinate based on a respective landmark vector.

6. The method according to claim 1, wherein said determination of said plurality of network coordinates further comprises:

determining a plurality of landmark vectors based on a global positioning system, each network coordinate based on a respective landmark vector.

7. The method according to claim 5, further comprising:

hashing said plurality of landmark vectors into logical coordinate space with a hash function configured to maintain physical relationships of said plurality of landmark vectors.

8. The method according to claim 1, further comprising:

forming a plurality of coordinate maps, each coordinate map based on a respective group of network coordinates; and

searching said plurality of coordinate maps with said network coordinate as a search index key.

9. The method according to claim 8, further comprising:

retrieving a candidate coordinate map of said plurality of coordinate maps based on said network coordinates matching said candidate coordinate map.

10. The method according to claim 8, further comprising:

forming a time-to-live packet in response to said network coordinates not matching said plurality of coordinate maps; and

transmitting said time-to-live packet.

11. An apparatus for mapping peers in a peer-to-peer network to an overlay network, said apparatus comprising:

means for determining a network coordinate of a peer;

means for hashing said network coordinate to a target coordinate in the logical space of said overlay network; and

means for determining a target zone based on said target coordinate.

12. The apparatus according to claim 11, further comprising:

means for forming an object comprising of said target zone, said network coordinate, and an address for said peer; and

means for storing said object in a owner peer that owns said target zone.

13. The apparatus according to claim 12, further comprising:

means for forming coordinate maps based on stored objects.

14. The apparatus according to claim 13, further comprising:

means for searching said coordinate maps with candidate network coordinates; and

means for retrieving matching coordinate maps based on said candidate network coordinates.

15. The apparatus according to claim 14, further comprising:

means for selecting a candidate peer based on said retrieved coordinate maps.

16. A computer readable storage medium on which is embedded one or more computer programs, said one or more computer programs implementing a method of mapping peers in a peer-to-peer network to an overlay network, said one or more computer programs comprising a set of instructions for:

determining a network coordinate of a peer;

hashing said network coordinate to a target coordinate in the logical space of said overlay network; and

determining a target zone based on said target coordinate.

17. The computer readable storage medium in according to claim 16, said set of instructions further comprises:

forming a triple comprising of said target zone, said network coordinate, and an address for said peer; and

storing said triple in a owner peer that owns said target zone.

18. The computer readable storage medium in according to claim 17, said set of instructions further comprises:

forming coordinate maps based on stored triples.

19. The computer readable storage medium in according to claim 18, said set of instructions further comprises:

receiving a destination peer;

hashing an address of said destination peer to a target key; and

routing said target key to a target peer.

20. The computer readable storage medium in according to claim 19, said set of instructions further comprises:

retrieving associated coordinate maps of said target peer.

21. The computer readable storage medium in according to claim 20, said set of instructions further comprises:

selecting a candidate peer based on said retrieved coordinate maps.

22. A system for mapping peers in a peer-to-peer network to an overlay network, said system comprising:

a network; and

a plurality of peers interconnected by said network and configured to implement said overlay network, wherein each peer is configured to store coordinate maps based on a hashing of a network position of a selected peer to a logical space of said overlay network.

23. The system according claim 22, further comprising:

a routing module stored and executed by each peer of said plurality of peers, wherein said routing module is configured to receive a destination peer, to hash an address of said destination peer to a target key and to route said target key to a target peer.

24. The system according to claim 23, wherein said routing module is further configured to retrieve associated coordinate maps of said target peer.

25. The system according to claim 24, wherein said routing module is further configured to select a candidate peer based on said retrieved coordinate maps.