Method, apparatus, and system for expressway routing among peers

• US 7,289,520 B2
• Filed: 11/20/2002
• Issued: 10/30/2007
• Est. Priority Date: 11/20/2002
• 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: Zhang, Zheng, Xu, Zhichen
• Primary Examiner(s): Yao; Kwang Bin
• Assistant Examiner(s): Wong; Warner
• Application Number:
  US10/299,907
• Publication Number:
  US 20040098502A1
• Time in Patent Office: 1,805 Days
• Field of Search: None
• US Class Current: 370/400
• 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;

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

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

determining a plurality of logical distance values, each logical distance value determined from each resident of said plurality of residents to a 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.

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

forming a communication channel to said candidate peer; and

forwarding a request to forward data to said candidate peer.

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

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

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

5. 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;

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

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;

means for determining a plurality of logical distances, each logical distance determined from each resident of said plurality of residents to a 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.

6. The apparatus according to claim 5, further comprising:

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

means for forwarding said request to said candidate peer.

7. The apparatus according to claim 5 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.

8. The apparatus according to claim 7, 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.

9. 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;

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

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

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

determining a ratio based on an average physical distance between a source of the data to each resident of said plurality of residents to an average logical distance between said data source 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.

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

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

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

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

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

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

13. The method according to claim 9, 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.

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

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

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

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

a routing table operates 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;

to select a candidate peer from said plurality of residents based on a physical distance value and an estimated distance value;

to determine a plurality of physical distance values, each physical distance value based on a physical distance to each resident of said plurality of residents;

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

to determine 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

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

16. The system according to claim 15, further comprising:

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

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

17. The system according to claim 16, further comprising:

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

18. The system according to claim 15, wherein the routing module is further operates to determine a largest zone that does not encompass said destination.

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

20. The system according to claim 15, wherein said physical distance value is a round-trip time value.

21. The system according to claim 15, wherein said physical distance value is a number of hops.