Optimal operation of hierarchical peer-to-peer networks

• US 20090234917A1
• Filed: 08/28/2008
• Published: 09/17/2009
• Est. Priority Date: 08/29/2007
• Status: Abandoned Application

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Despotovic, Zoran, Hofstaetter, Quirin, Zoels, Stefan, Kellerer, Wolfgang
• Application Number:
  US12/229,970
• Publication Number:
  US 20090234917A1
• Time in Patent Office: Days
• US Class Current: 709/204
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms
• CPC Class Codes: H04L 67/1051 Group master selection mechanisms
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053

Abstract

A Network capable entity, having an estimator for estimating a superpeer number of required superpeers in a hierarchical peer-to-peer network, the number depending on an actual network situation, and for estimating an existing superpeer number of actually existing superpeers in the hierarchical peer-to-peer network, and a controller for promoting a different networking capable entity to become a superpeer in case the superpeer number is greater than the existing superpeer number.

Claims

1. Networking capable entity, comprising:

an estimator for estimating a superpeer number of necessitated superpeers in a hierarchical peer-to-peer network, the superpeer number depending on a result of a comparison of an estimate for an actual system load factor and a desired system load factor, wherein the desired system load factor is set to a value smaller than 100%, and wherein the estimate for the actual system load depends on an estimate for an existing superpeer number of actually existing superpeers in the hierarchical peer-to-peer network; and

a controller for promoting a different networking capable entity to become a superpeer in case the superpeer number is greater than the estimate for the existing superpeer number.

2. Networking capable entity according to claim 1, wherein the networking capable entity is part of a hierarchical peer-to-peer system with load balancing for balancing load that is generated in the hierarchical peer-to-peer system uniformly over participating superpeers.

3. Networking capable entity according to claim 1, wherein superpeers of the hierarchical peer-to-peer system are a arranged in a Chord network.

4. Networking capable entity according to claim 1, wherein the estimator is configured to estimate the existing number of superpeers based on a geometrically distribution parameter p of a length of an interval between an ID of the networking capable entity and an ID of a direct successor of the networking capable entity.

5. Networking capable entity according to claim 1, wherein the estimator is configured to use a system load factor as the actual network situation, wherein the system load factor denotes a ratio between an average peer cost and a maximum peer cost in a load balanced hierarchical peer-to-peer system.

6. Networking capable entity according to claim 1, wherein the estimator is adapted to estimate an average number of look-up messages generated by a superpeer, to estimate a mean number of maintenance messages generated by a superpeer and to estimate an average number of REPUPLISH messages per superpeer.

7. Networking capable entity according to claim 6, wherein the estimator is adapted to estimate the average number of generated look-up messages per superpeer based on the estimated existing superpeer number and an estimated look-up rate.

8. Networking capable entity according to claim 7, wherein the estimator is adapted to estimate the average number of generated look-up messages per superpeer according to

$\lambda$

= ( 2 + log 2 

N SP ) ·

R N SP .

9. Networking capable entity according to claim 6, wherein the estimator is adapted to estimate the average number of maintenance messages per superpeer based on the estimated existing superpeer number and an estimated group size referring to an average ratio of peers connected to a superpeer.

10. Networking capable entity according to claim 9, wherein the estimator is adapted to estimate the average number of maintenance messages according to

$\mu$

= 3 T stab + 2 

log 2 

N sp T fix + M - 1 T ping .

wherein T_stab denotes the time period of a Chord'"'"'s STABILIZE algorithm, T_fix denotes the time period of the Chord'"'"'s FIXFINGER algorithm and T_ping denotes the time period of the Chord'"'"'s PING-PONG algorithm.

11. Networking capable entity according to claim 6, wherein the estimator is adapted to estimate the average number of REPUPLISH messages per superpeer, based on an estimate of a number of shared objects in the hierarchical peer-to-peer network and the existing superpeer number.

12. Networking capable entity according to claim 11, wherein the estimator is adapted to estimate the number of REPUPLISH messages according to

$\rho$

= ( 2 + log 2 

N sp ) ·

F ( T rep ·

N sp ) .

13. Networking capable entity according to claim 1, wherein the estimator is adapted to estimate a mean capacity per superpeer of the hierarchical peer-to-peer network and to estimate the actual network situation based on the estimated average number of generated look-up messages per superpeer, the estimated average number of maintenance messages per superpeer, the estimated average number of REPUPLISH messages per superpeer and the estimated mean capacity.

14. Networking capable entity according to claim 13, wherein the estimator is adapted to estimate the actual network situation according to

$L=\frac{\lambda }{}$

+ μ

+ ρ

C .

15. Networking capable entity according to claim 1, wherein the controller is adapted to compare a system load factor depending on the actual network situation to a desired system load factor and to increase the superpeer number compared to the existing superpeer number in case the current system load factor is larger than the desired system load factor, and to decrease the superpeer number is compared to the existing superpeer number in case the current system load factor is lower than the desired system load factor.

16. Networking capable entity according to claim 1, wherein the estimator is adapted to estimate values for an average look-up rate, an average group size (M), an average number of shared items and an average capacity of superpeers based on values specific for the said networking capable entity.

17. Networking capable entity according to claim 1, wherein the estimator is adapted to estimate for an average look-up rate, an average group size, an average number of shared items and an average capacity of superpeers using related values of neighboring networking capable entities being superpeers additionally to own values for determining mean values for said values.

18. Network capable entity, comprising:

an estimator for estimating a superpeer number of necessitated superpeers in a hierarchical peer-to-peer network, the superpeer number depending on a result of a comparison of an estimate for an actual system load factor and a desired system load factor, wherein the desired system load factor is set to a value smaller than 100%, and wherein the estimate for the actual system load depends on an estimate for an existing superpeer number of actually existing superpeers in the hierarchical peer-to-peer network; and

a controller for terminating superpeer characteristics of the network capable entity, in case the superpeer number is smaller than the estimate for the existing superpeer number.

19. Method for operating a networking capable entity, the method comprising:

estimating an existing superpeer number of actually existing superpeers in a hierarchical peer-to-peer network;

estimating an actual system load factor based on the estimated existing superpeer number;

comparing the estimate for the actual system load factor to a desired system load factor, wherein the desired system load factor is set to a value smaller than 100%,

estimating a superpeer number of required superpeers in the hierarchical peer-to-peer network based on a result of the comparison; and

promoting a different networking capable entity to become a superpeer in case the superpeer number is greater than the estimate for the existing superpeer number.

20. Method for operating a networking capable entity, the method comprising:

estimating an existing superpeer number of actually existing superpeers in a hierarchical peer-to-peer network;

estimating an actual system load factor based on the estimated existing superpeer number;

comparing the estimate for the actual system load factor to a desired system load factor, wherein the desired system load factor is set to a value smaller than 100%,

estimating a superpeer number of required superpeers in the hierarchical peer-to-peer network based on a result of the comparison; and

terminating superpeer characteristics of the network capable entity, in case the superpeer number is smaller than the estimate for the existing superpeer number.

21. Computer-program for performing a method for operating a networking capable entity, the method comprising:

estimating an existing superpeer number of actually existing superpeers in a hierarchical peer-to-peer network;

estimating an actual system load factor based on the estimated existing superpeer number;

comparing the estimate for the actual system load factor to a desired system load factor, wherein the desired system load factor is set to a value smaller than 100%;

estimating a superpeer number of required superpeers in the hierarchical peer-to-peer network based on a result of the comparison; and

promoting a different networking capable entity to become a superpeer in case the superpeer number is greater than the estimate for the existing superpeer number;

when the computer-program runs on a computer and/or microcontroller.

22. Computer-program for performing a method for operating a networking capable entity, the method comprising:

estimating an existing superpeer number of actually existing superpeers in a hierarchical peer-to-peer network;

estimating an actual system load factor based on the estimated existing superpeer number;

comparing the estimate for the actual system load factor to a desired system load factor, wherein the desired system load factor is set to a value smaller than 100%;

estimating a superpeer number of required superpeers in the hierarchical peer-to-peer network based on a result of the comparison; and

terminating superpeer characteristics of the network capable entity, in case the superpeer number is smaller than the estimate for the existing superpeer number;

when the computer-program runs on a computer and/or microcontroller.