American Institute of Mathematical Sciences

Advanced
2011, 1(4): 593-610. doi: 10.3934/naco.2011.1.593

Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach

Kazuhiko Kuraya 1, , Hiroyuki Masuyama 2, and  Shoji Kasahara 2,

1. 

Graduate School of Informatics, Kyoto University, Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan
2. 

Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501

Received  May 2011 Revised  August 2011 Published  November 2011

Voice over Internet protocol (VoIP) services using peer-to-peer (P2P) technology have become popular in recent years. In P2P-based VoIP networks such as Skype and P2P session initiation protocol (P2PSIP), super nodes are chosen from among all ordinary end-user nodes and handle particular tasks such as the management of user information, call establishment, and traffic relay. Future communication networks based on P2P technology must support a huge number of user nodes. A fundamental analysis of the load distribution in decentralized user-information management is needed to develop efficient and robust communication networks. In this paper, we analyze the performance of the P2P-based dynamic load distribution. In our analytical model, new nodes join the network according to a nonstationary Poisson process, and the stochastic behavior of the number of online nodes is analyzed approximately with an M($t$)/M/$\infty$ queue. We focus on two performance measures that significantly affect the quality of service (QoS) provided to the users: the churn rate and the load of super nodes. Numerical examples show that the performance of the P2P-based VoIP networks is sensitive to the sojourn time of super nodes and the maximum number of nodes managed by a super node.
Keywords: nonstationary queue, VoIP., nonstationary Poisson process, Decentralized user information management system, nonstationary Markov chain, online node process, QoS, P2P.
Mathematics Subject Classification: Primary: 68M20; Secondary: 60K25, 68M2.
Citation: Kazuhiko Kuraya, Hiroyuki Masuyama, Shoji Kasahara. Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 593-610. doi: 10.3934/naco.2011.1.593
References:
[1]

K. A. Alnowibet and H. Perros, The nonstationary loss queue: a survey, in "Modelling of Computer Systems and Networks"(ed. J. Barria), Imperial College Press, (2005), 105-125. Google Scholar

[2]

S. A. Baset and H. G. Schulzrinne, An analysis of the Skype peer-to-peer Internet telephony protocol, Proceedings of the 25th International Conference on Computer Communications, IEEE INFOCOM, (2006), 1-11. Google Scholar

[3]

D. A. Bryan, B. B. Lowekamp and C. Jennings, SOSIMPLE: a serverless, standards-based, P2P SIP communication system, Proceedings of International Workshop on Advanced Workshop and Algorithms for Internet Delivery and Applications, AAA-IDEA 2005, 42-49. Google Scholar

[4]

G. Caizzone, A. Corghi, P. Giacomazzi and M. Nonnoi, Analysis of the scalability of the overlay Skype system, Proceedings of the IEEE International Conference on Communications, (2008), 5652-5658. Google Scholar

[5]

K. Chen, C. Huang, P. Huang and C. Lei, Quantifying Skype user satisfaction, Proceedings of ACM SIGCOMM, (2006), 399-410. Google Scholar

[6]

S. G. Eick, W. A. Massey and W. Whitt, M$_t$/G/$\infty$ queues with sinusoidal arrival rates, Management Science, 39 (1993), 241-252. doi: 10.1287/mnsc.39.2.241.  Google Scholar

[7]

Z. Ge, D. R. Figueiredo, S. Jaiswal, J. Kurose and D. Towsley, Modeling peer-peer file sharing systems, Proceedings of the 22th International Conference on Computer Communications, IEEE INFOCOM, (2003), 2188-2198. Google Scholar

[8]

L. Green, P. Kolesar and A. Svoronos, Some effects of nonstationarity on multiserver Markovian queueing systems, Operations Research, 39 (1991), 502-511. doi: 10.1287/opre.39.3.502.  Google Scholar

[9]

S. Guha, N. Daswani and R. Jain, An experimental study of the Skype peer-to-peer VoIP system, Proceedings of the 5th International Workshop on Peer-to-Peer Systems, (2006), 1-6. Google Scholar

[10]

D. P. Heyman and W. Whitt, The asymptotic behavior of queues with time-varying arrival rates, Journal of Applied Probability, 21 (1984), 143-156. doi: 10.2307/3213672.  Google Scholar

[11]

D. L. Jagerman, Nonstationary blocking in telephone traffic, The Bell System Technical Journal, 54 (1975), 625-661.  Google Scholar

[12]

V. G. Kulkarni, "Modeling and Analysis of Stochastic Systems," Chapman $ & $ Hall, 1995.  Google Scholar

[13]

K. Kuraya, H. Masuyama, S. Kasahara and Y. Takahashi, Performance analysis of decentralized user information management system for peer-to-peer real-time communication services, Proceedings of the 6th Symposium on Communication Systems, Networks and Digital Signal Processing, (2008), 520-524. doi: 10.1109/CSNDSP.2008.4610821.  Google Scholar

[14]

L. Le and G. Kuo, Hierarchical and breathing peer-to-peer SIP system, Proceedings of the IEEE International Conference on Communications, (2007), 1887-1892. doi: 10.1109/ICC.2007.314.  Google Scholar

[15]

P. A. W. Lewis and G. S. Shedler, Simulation of nonhomogeneous Poisson processes by thinning, Naval Research Logistics Quarterly, 26 (1979), 403-413. doi: 10.1002/nav.3800260304.  Google Scholar

[16]

W. A. Massey and W. Whitt, Stationary-process approximation for the nonstationary Erlang loss model, Operations Research, 44 (1996), 976-983. doi: 10.1287/opre.44.6.976.  Google Scholar

[17]

J. Rosenberg, R. Mahy and P. Matthews, Traversal using relay around NAT (TURN): relay extensions to session traversal utilities for NAT (STUN), IETF Internet draft, Work in progress, 2008. Google Scholar

[18]

J. Rosenberg, R. Mahy, P. Matthews and D. Wing, Session traversal utilities for NAT (STUN), IETF RFC (2008), http://www.ietf.org/rfc/rfc5389.txt. Google Scholar

[19]

S. Saroiu, P. K. Gummadi and S. D. Gribble, A measurement study of peer-to-peer file sharing systems, Technical Report, UW-CSE-01-06-02, University of Washington, 2001. Google Scholar

[20]

H. Schulzrinne and J. Rosenberg, The session initiation protocol: Internet-centric signaling, IEEE Communications Magazine, 38 (2000), 134-141. doi: 10.1109/35.874980.  Google Scholar

[21]

K. Singh and H. Schulzrinne, SIPpeer: a session initiation protocol (SIP)-based peer-to-peer Internet telephony client adaptor,, , ().   Google Scholar

[22]

K. Singh and H. Schulzrinne, Peer-to-peer Internet telephony using SIP, Proceedings of ACM NOSSDAV, (2005), 63-68. Google Scholar

[23]

X. Yang and G. de Veciana，, Performance of peer-to-peer networks: service capacity and role of resource sharing policies, Performance Evaluation, 63 (2006), 175-194. doi: 10.1016/j.peva.2005.01.005.  Google Scholar

[24]

, P2PSIP working group,, , ().   Google Scholar

[25]

, Skype,, , ().   Google Scholar

[26]

, Skype statistics,, , ().   Google Scholar

show all references

References:
[1]

K. A. Alnowibet and H. Perros, The nonstationary loss queue: a survey, in "Modelling of Computer Systems and Networks"(ed. J. Barria), Imperial College Press, (2005), 105-125. Google Scholar

[2]

S. A. Baset and H. G. Schulzrinne, An analysis of the Skype peer-to-peer Internet telephony protocol, Proceedings of the 25th International Conference on Computer Communications, IEEE INFOCOM, (2006), 1-11. Google Scholar

[3]

D. A. Bryan, B. B. Lowekamp and C. Jennings, SOSIMPLE: a serverless, standards-based, P2P SIP communication system, Proceedings of International Workshop on Advanced Workshop and Algorithms for Internet Delivery and Applications, AAA-IDEA 2005, 42-49. Google Scholar

[4]

G. Caizzone, A. Corghi, P. Giacomazzi and M. Nonnoi, Analysis of the scalability of the overlay Skype system, Proceedings of the IEEE International Conference on Communications, (2008), 5652-5658. Google Scholar

[5]

K. Chen, C. Huang, P. Huang and C. Lei, Quantifying Skype user satisfaction, Proceedings of ACM SIGCOMM, (2006), 399-410. Google Scholar

[6]

S. G. Eick, W. A. Massey and W. Whitt, M$_t$/G/$\infty$ queues with sinusoidal arrival rates, Management Science, 39 (1993), 241-252. doi: 10.1287/mnsc.39.2.241.  Google Scholar

[7]

Z. Ge, D. R. Figueiredo, S. Jaiswal, J. Kurose and D. Towsley, Modeling peer-peer file sharing systems, Proceedings of the 22th International Conference on Computer Communications, IEEE INFOCOM, (2003), 2188-2198. Google Scholar

[8]

L. Green, P. Kolesar and A. Svoronos, Some effects of nonstationarity on multiserver Markovian queueing systems, Operations Research, 39 (1991), 502-511. doi: 10.1287/opre.39.3.502.  Google Scholar

[9]

S. Guha, N. Daswani and R. Jain, An experimental study of the Skype peer-to-peer VoIP system, Proceedings of the 5th International Workshop on Peer-to-Peer Systems, (2006), 1-6. Google Scholar

[10]

D. P. Heyman and W. Whitt, The asymptotic behavior of queues with time-varying arrival rates, Journal of Applied Probability, 21 (1984), 143-156. doi: 10.2307/3213672.  Google Scholar

[11]

D. L. Jagerman, Nonstationary blocking in telephone traffic, The Bell System Technical Journal, 54 (1975), 625-661.  Google Scholar

[12]

V. G. Kulkarni, "Modeling and Analysis of Stochastic Systems," Chapman $ & $ Hall, 1995.  Google Scholar

[13]

K. Kuraya, H. Masuyama, S. Kasahara and Y. Takahashi, Performance analysis of decentralized user information management system for peer-to-peer real-time communication services, Proceedings of the 6th Symposium on Communication Systems, Networks and Digital Signal Processing, (2008), 520-524. doi: 10.1109/CSNDSP.2008.4610821.  Google Scholar

[14]

L. Le and G. Kuo, Hierarchical and breathing peer-to-peer SIP system, Proceedings of the IEEE International Conference on Communications, (2007), 1887-1892. doi: 10.1109/ICC.2007.314.  Google Scholar

[15]

P. A. W. Lewis and G. S. Shedler, Simulation of nonhomogeneous Poisson processes by thinning, Naval Research Logistics Quarterly, 26 (1979), 403-413. doi: 10.1002/nav.3800260304.  Google Scholar

[16]

W. A. Massey and W. Whitt, Stationary-process approximation for the nonstationary Erlang loss model, Operations Research, 44 (1996), 976-983. doi: 10.1287/opre.44.6.976.  Google Scholar

[17]

J. Rosenberg, R. Mahy and P. Matthews, Traversal using relay around NAT (TURN): relay extensions to session traversal utilities for NAT (STUN), IETF Internet draft, Work in progress, 2008. Google Scholar

[18]

J. Rosenberg, R. Mahy, P. Matthews and D. Wing, Session traversal utilities for NAT (STUN), IETF RFC (2008), http://www.ietf.org/rfc/rfc5389.txt. Google Scholar

[19]

S. Saroiu, P. K. Gummadi and S. D. Gribble, A measurement study of peer-to-peer file sharing systems, Technical Report, UW-CSE-01-06-02, University of Washington, 2001. Google Scholar

[20]

H. Schulzrinne and J. Rosenberg, The session initiation protocol: Internet-centric signaling, IEEE Communications Magazine, 38 (2000), 134-141. doi: 10.1109/35.874980.  Google Scholar

[21]

K. Singh and H. Schulzrinne, SIPpeer: a session initiation protocol (SIP)-based peer-to-peer Internet telephony client adaptor,, , ().   Google Scholar

[22]

K. Singh and H. Schulzrinne, Peer-to-peer Internet telephony using SIP, Proceedings of ACM NOSSDAV, (2005), 63-68. Google Scholar

[23]

X. Yang and G. de Veciana，, Performance of peer-to-peer networks: service capacity and role of resource sharing policies, Performance Evaluation, 63 (2006), 175-194. doi: 10.1016/j.peva.2005.01.005.  Google Scholar

[24]

, P2PSIP working group,, , ().   Google Scholar

[25]

, Skype,, , ().   Google Scholar

[26]

, Skype statistics,, , ().   Google Scholar

[1]

Helmut Abels. Nonstationary Stokes system with variable viscosity in bounded and unbounded domains. Discrete & Continuous Dynamical Systems - S, 2010, 3 (2) : 141-157. doi: 10.3934/dcdss.2010.3.141
[2]

Shunfu Jin, Yuan Zhao, Wuyi Yue, Lingling Chen. Performance analysis of a P2P storage system with a lazy replica repair policy. Journal of Industrial & Management Optimization, 2014, 10 (1) : 151-166. doi: 10.3934/jimo.2014.10.151
[3]

Janne M.J. Huttunen, J. P. Kaipio. Approximation errors in nonstationary inverse problems. Inverse Problems & Imaging, 2007, 1 (1) : 77-93. doi: 10.3934/ipi.2007.1.77
[4]

Muriel Boulakia. Quantification of the unique continuation property for the nonstationary Stokes problem. Mathematical Control & Related Fields, 2016, 6 (1) : 27-52. doi: 10.3934/mcrf.2016.6.27
[5]

A. Katok and R. J. Spatzier. Nonstationary normal forms and rigidity of group actions. Electronic Research Announcements, 1996, 2: 124-133.

[6]

Erik M. Bollt, Joseph D. Skufca, Stephen J . McGregor. Control entropy: A complexity measure for nonstationary signals. Mathematical Biosciences & Engineering, 2009, 6 (1) : 1-25. doi: 10.3934/mbe.2009.6.1
[7]

Jie Huang, Marco Donatelli, Raymond H. Chan. Nonstationary iterated thresholding algorithms for image deblurring. Inverse Problems & Imaging, 2013, 7 (3) : 717-736. doi: 10.3934/ipi.2013.7.717
[8]

Antti Lipponen, Aku Seppänen, Jari Hämäläinen, Jari P. Kaipio. Nonstationary inversion of convection-diffusion problems - recovery from unknown nonstationary velocity fields. Inverse Problems & Imaging, 2010, 4 (3) : 463-483. doi: 10.3934/ipi.2010.4.463
[9]

Vinay Aggarwal, Anja Feldmann. Locality-aware P2P query search with ISP collaboration. Networks & Heterogeneous Media, 2008, 3 (2) : 251-265. doi: 10.3934/nhm.2008.3.251
[10]

Charles Amorim, Miguel Loayza, Marko A. Rojas-Medar. The nonstationary flows of micropolar fluids with thermal convection: An iterative approach. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2509-2535. doi: 10.3934/dcdsb.2020193
[11]

David González-Sánchez, Onésimo Hernández-Lerma. On the Euler equation approach to discrete--time nonstationary optimal control problems. Journal of Dynamics & Games, 2014, 1 (1) : 57-78. doi: 10.3934/jdg.2014.1.57
[12]

Takayuki Kubo, Ranmaru Matsui. On pressure stabilization method for nonstationary Navier-Stokes equations. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2283-2307. doi: 10.3934/cpaa.2018109
[13]

Yu-Ting Lin, John Malik, Hau-Tieng Wu. Wave-shape oscillatory model for nonstationary periodic time series analysis. Foundations of Data Science, 2021  doi: 10.3934/fods.2021009
[14]

Norimichi Hirano, Wieslaw Krawcewicz, Haibo Ruan. Existence of nonstationary periodic solutions for $\Gamma$-symmetric Lotka-Volterra type systems. Discrete & Continuous Dynamical Systems, 2011, 30 (3) : 709-735. doi: 10.3934/dcds.2011.30.709
[15]

Hideaki Kim, Shigeru Shinomoto. Estimating nonstationary inputs from a single spike train based on a neuron model with adaptation. Mathematical Biosciences & Engineering, 2014, 11 (1) : 49-62. doi: 10.3934/mbe.2014.11.49
[16]

Changjie Fang, Weimin Han. Well-posedness and optimal control of a hemivariational inequality for nonstationary Stokes fluid flow. Discrete & Continuous Dynamical Systems, 2016, 36 (10) : 5369-5386. doi: 10.3934/dcds.2016036
[17]

Reinhard Farwig, Ronald B. Guenther, Enrique A. Thomann, Šárka Nečasová. The fundamental solution of linearized nonstationary Navier-Stokes equations of motion around a rotating and translating body. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 511-529. doi: 10.3934/dcds.2014.34.511
[18]

Jian Su, Yinnian He. The almost unconditional convergence of the Euler implicit/explicit scheme for the three dimensional nonstationary Navier-Stokes equations. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3421-3438. doi: 10.3934/dcdsb.2017173
[19]

Matteo Ludovico Bedini, Rainer Buckdahn, Hans-Jürgen Engelbert. On the compensator of the default process in an information-based model. Probability, Uncertainty and Quantitative Risk, 2017, 2 (0) : 10-. doi: 10.1186/s41546-017-0017-4
[20]

Donglei Du, Tianping Shuai. Errata to:''Optimal preemptive online scheduling to minimize $l_{p}$ norm on two processors''[Journal of Industrial and Management Optimization, 1(3) (2005), 345-351.]. Journal of Industrial & Management Optimization, 2008, 4 (2) : 339-341. doi: 10.3934/jimo.2008.4.339

 Impact Factor: 

Tools

Metrics

  • PDF downloads (43)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences