Method, apparatus, and system for expressway routing among peers

• US 20040098502A1
• Filed: 11/20/2002
• Published: 05/20/2004
• Est. Priority Date: 11/20/2002
• 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,289,520 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1059 Inter-group management mechanisms, e.g. splitting, merging or interconnection of groups
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

In a method for creating expressway for overlay routing, an existing peer-to-peer network is organized into a plurality of zones. A neighboring zone to a destination peer is selected. A plurality of residents of the neighboring zone are retrieved. A candidate peer is selected from the plurality of residents based a physical distance value and an estimated distance value.

Claims

1. A method of expressway routing to peers, comprising:

selecting a neighboring zone to a destination zone;

retrieving a plurality of residents of said neighboring zone; and

selecting a candidate peer from said plurality of residents based on a physical distance value and an estimated distance value.

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

forming a communication channel to said candidate peer; and

forwarding said request to said candidate peer.

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

determining a plurality of physical distance values, each physical distance value based on a physical distance to each resident of said plurality of residents.

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

determining a plurality of logical distance values, each logical distance value determined from each resident of said plurality of residents to said destination peer;

determining a ratio based on an average physical distance between a source peer to each resident of said plurality of residents to an average logical distance between said source peer to each resident of said plurality of residents; and

determining a plurality of estimated distance values, each estimated distance value being a product of a respective logical distance value and said ratio.

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

determining a plurality of distance values, each distance value based on a respective physical distance value added to respective estimated distance value.

6. The method according to claim 5, wherein said selection of said candidate peer is based on said candidate peer having a smallest value among said plurality of distance values.

7. An apparatus for routing to peers, comprising:

means for selecting a neighboring zone to a destination peer based on a request;

means for retrieving a plurality of residents of said neighboring zone; and

means for selecting a candidate peer from said plurality of residents based on a physical distance value and an estimated distance value.

8. The apparatus according to claim 7, further comprising:

means for forming a communication channel to said candidate peer; and

means for forwarding said request to said candidate peer.

9. The apparatus according to claim 7, further comprising:

means for determining a plurality of physical distance values, each physical distance value based on a physical distance to each resident of said plurality of residents.

10. The apparatus according to claim 9, further comprising:

means for determining a plurality of logical distances, each logical distance determined from each resident of said plurality of residents to said destination peer;

means for determining a ratio based on an average physical distance between a source peer to each resident of said plurality of residents to an average logical distance between said source peer to each resident of said plurality of residents; and

means for determining a plurality of estimated distances, each estimated distance being a product of a respective logical distance value and said ratio.

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

means for determining a plurality of distance values, each distance value based on a respective physical distance value added to a respective estimated distance value.

12. The apparatus according to claim 11, wherein said means for selection of said candidate peer is based on said candidate peer having a smallest value among said plurality of distance values.

13. A method of expressway routing among peers, comprising:

receiving a request to forward data;

determining a destination from said request;

searching a routing table for an expressway route to said destination;

selecting a zone from said routing table based on said zone not encompassing said destination;

retrieving a plurality of residents of said zone; and

selecting a candidate from said plurality of residents based on a physical distance value and an ideal distance value.

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

forming said expressway route to a zone representative of said largest zone that does not encompass said destination.

15. The method according to claim 13, further comprising:

terminating said searching of said routing table in response to said destination being a peer receiving said request to forward said data.

16. The method according to claim 13, further comprising:

forming a TCP/IP connection to build said expressway route to said destination.

17. The method according to claim 13, further comprising:

determining a plurality of intermediate zones in response to said search of routing table for said expressway; and

selecting an intermediate zone from said plurality of intermediate zones.

18. The method according to claim 17, wherein said selection of said intermediate zone of said plurality of intermediate zones based on said intermediate zone being closest to said destination.

19. A system for expressway routing among peers in a peer-to-peer network, said system comprising:

a peer-to-peer module configured to implement said peer-to-peer network;

a routing module adapted to interface with said peer-to-peer module; and

a routing table adapted to interface with said routing module, wherein said routing module is configured to select a neighboring zone of a destination peer based on a received request, to retrieve a plurality of residents of said neighboring zone, and to select a candidate peer from said plurality of residents based on a physical distance value and an estimated distance value.

20. The system according to claim 19, further comprising:

an operating system configured to manage said peer-to-peer module and said routing module; and

an operating system interface adapted to connect said operating system and said routing table.

21. The system according to claim 20, further comprising:

a network interface adapted to interface said peer-to-peer module with a network through said operating system.

22. The system according to claim 19, wherein the routing module is further configured to determine a largest zone that does not encompass said destination.

23. The system according to claim 19, wherein said logical distance is an Euclidean distance in Cartesian space.

24. The system according to claim 19, wherein said physical distance is a roundtrip time value.

25. The system according to claim 19, wherein said physical distance is a number of hops.