Churn handling has become an active area of research due to increased complexity, high dynamicity of participating nodes and its effect on the performance of overlay network. In this paper, we systematically analyse churn, its causes and implications along with churn handling strategies employed in various state of the art structured overlay network. These churn handling strategies are classified into two main categories based on addressing effects of churn: Churn Resilience and Dynamic repair strategies. These techniques are further classified into sub categories based on their inherent mechanism for addressing a particular concern. In addition, this paper pinpoints various concerns related to the future research for handling participant’s churn.
ZhaoB.Y.KubiatowiczJ. and JosephA.D., Tapestry: An infrastructure for fault-tolerant wide-area location and routing, Technical Report UCB//CSD-01-1141, U C Berkeley (2001), 1–28.
2.
KimG., Spectrum Future, Accessed 4 April 2017, https://spectrumfutures.org/5g-requires-virtualization-of-network-core-and-edge/.
3.
ZhaoB.Y.KubiatowiczJ. and JosephA.D., Tapestry: An infrastructure for fault-tolerant wide-area location and routing, U C Berkeley, Technical Report (2001), 1–28.
4.
RowstronA. and DruschelP., Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems, in: IFIP/ACM International Conference on Distributed Systems Platforms and Open Distributed Processing, Springer (2001), 329–350.
5.
StoicaI.MorrisR.Liben-NowellD.KargerD.R.KaashoekM.F.DabekF. and BalakrishnanH., Chord: A scalable peer-to-peer lookup protocol for internet applications, IEEE Transactions on Networking (TON)11(1) (2003), 17–32.
6.
KaashoekM.F. and KargerD.R., Koorde: A simple degree-optimal distributed hash table, in: International Workshop on Peer-to-Peer Systems, Springer (2003), 98–107.
7.
AlimaL.O.El-AnsaryS.BrandP. and HaridiS., DKS (N, k, f): A family of low communication, scalable and fault-tolerant infrastructures for P2P applications, in: 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid, IEEE (2003), 344–350.
8.
AbererK.Cudré-MaurouxP.DattaA.DespotovicZ.HauswirthM.PuncevaM. and SchmidtR., P-Grid: A self-organizing structured P2P system, ACM SIGMOD Record32(3) (2003), 29–33.
9.
CastroM.DruschelP.HuY.C. and RowstronA., Topology-aware routing in structured peer-to-peer overlay networks, in: Future Directions in Distributed Computing, Springer (2003), 103–107.
10.
GhodsiA.AlimaL.O. and HaridiS., Low-bandwidth topology maintenance for robustness in structured overlay networks, in: Proceedings of the IEEE 38th Annual Hawaii International Conference on System Sciences, IEEE (2005), 302a-312a.
11.
LeongB.LiskovB. and DemaineE.D., Epichord: Parallelizing the chord lookup algorithm with reactive routing state management, Computer Communications29(9) (2006), 1243–1259.
12.
PorterB.TaianiF. and CoulsonG., Generalized repair for overlay networks, in: 25th IEEE Symposium on Reliable Distributed Systems, IEEE (2006), 132–142.
13.
GhinitaG. and TeoY.M., An adaptive stabilization framework for distributed hash tables, in: IEEE 20th International Parallel and Distributed Processing Symposium, IEEE (2006), 10–20.
14.
KrishnamurthyS.El-AnsaryS.AurellE. and HaridiS., Comparing maintenance strategies for overlays, in: The 16th IEEE Euro Micro Conference on Parallel, Distributed and Network-Based Processing, IEEE (2008), 473–482.
15.
KurianJ. and SaracK., A survey on the design, applications, and enhancements of application-layer overlay networks, ACM Computing Surveys (CSUR)43(1) (2010), 5–39.
16.
LuaE.K.CrowcroftJ.PiasM.SharmaR. and LimS., A survey and comparison of peer-to-peer overlay network schemes, IEEE Communications Surveys & Tutorials7(2) (2005), 72–93.
17.
MalatrasA., State-of-the-art survey on P2P overlay networks in pervasive computing environments, Journal of Network and Computer Applications55(1) (2015), 1–23.
18.
WallachD.S., A survey of peer-to-peer security issues, in: Software Security-Theories and Systems, Springer (2003), 42–57.
19.
SaroliyaA. and ShrivastavaV., Security problems and their upshots in routing protocols of DHT based overlay networks, Journal of Theoretical and Applied Information Technology1(1) (2005), 19–23.
20.
DingJ.BalasinghamI. and BouvryP., Management of overlay networks: A survey, in: Third International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies, IEEE (2009), 249–255.
21.
PathanA.M.K. and BuyyaR., A taxonomy and survey of content delivery networks, Grid Computing and Distributed Systems Laboratory, University of Melbourne, Technical Report (2007), 4–48.
22.
PallisG. and VakaliA., Insight and perspectives for content delivery networks, in: Communications of the ACM49(1) (2006), 101–106.
23.
LiuY.GuoY. and LiangC., A survey on peer-to-peer video streaming systems, Peer-to-peer Networking and Applications1(1) (2010), 18–28.
24.
ChuJ.C.LabonteK.S. and LevineB.N., Availability and locality measurements of peer-to-peer file systems, in: ITCom: The Convergence of Information Technologies and Communications (2002), 310–321.
25.
BhagwanR.SavageS. and VoelkerG., Understanding availability, in: International Workshop on Peer-to-Peer Systems II, Springer (2003), 256–267.
26.
DouceurJ.R., Is remote host availability governed by a universal law? in: ACM SIGMETRICS Performance Evaluation Review31(3) (2003), 25–29.
27.
CastroM.CostaM. and RowstronA., Performance and dependability of structured peer-to-peer overlays, in: IEEE International Conference on Dependable Systems and Networks, IEEE (2004), 9–18.
28.
GuhaS.DaswaniN. and JainR., An experimental study of the Skype peer-to-peer voip system, in: Proceedings of the 5th International Workshop on Peer-to-Peer Systems (IPTPS ’06), ACM (2006), 1–6.
29.
MickensJ.W. and NobleB.D., Exploiting availability prediction in distributed systems, in: Proceedings of the 3rd conference on Networked Systems Design & Implementation, ACM (2006), 6–6.
30.
JavadiB.KondoD.VincentJ.M. and AndersonD.P., Mining for availability models in large-scale distributed systems: A case study of seti@ home, in: IEEE International Symposium on Modelling, Analysis & Simulation of Computer and Telecommunication Systems, IEEE (2009), 276–283.
31.
LingaP.GuptaI. and BirmanK., A churn-resistant peer-to-peer web caching system, in: Proceedings of the ACM workshop on Survivable and Self-regenerative Systems: In association with the 10th ACM Conference on Computer and Communications Security, ACM (2003), 1–10.
32.
SaroiuS.GummadiP.KrishnaP. and StevenD., Measurement study of peer-to-peer file sharing systems, in: Electronic Imaging International Society for Optics and Photonics4673(1) (2002), 156–171.
33.
StutzbachD. and RejaieR., Understanding churn in peer-to-peer networks, in: Proceedings of the 6th ACM SIGCOMM Conference on Internet Measurement, ACM (2006), 189–202.
34.
Le BlondS.FessantF.L. and MerrerE.L., Finding good partners in availability-aware P2P Networks, Anglais, Technical Report (2009), 472–484.
35.
PaceA.QuemaV. and SchiavoniV., Exploiting node connection regularity for DHT replication, in: IEEE Symposium on Reliable Distributed Systems, IEEE (2011), 111–120.
36.
SongG.KimS. and SeoD., Replica placement algorithm for highly available peer-to-peer storage systems, in: Proceedings of the First International Conference on Advances in P2P Systems (AP2PS), ACM (2009), 160–167.
37.
MonneratL.R. and AmorimC.L., D1HT: A distributed one hop hash table, in: 20th IEEE International Parallel and Distributed Processing Symposium, IEEE (2006), 1–10.
38.
RatnasamyS.FrancisP.HandleyM.KarpR. and ShenkerS., A scalable content-addressable network, in: Proceedings of the ACM SIGCOMM Computer Communication Review31(4) (2001), 161–172.
39.
GummadiK.GummadiR.GribbleS.RatnasamyS.ShenkerS. and StoicaI., The impact of DHT routing geometry on resilience and proximity, in: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM (2003), 381–394.
40.
LoguinovD.KumarA.RaiV. and GaneshS., Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience, in: Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM (2003), 395–406.
41.
MaymounkovP. and MazieresD., Kademlia: A peer-to-peer information system based on the XOR metric, in: International Workshop on Peer-to-Peer Systems, Springer (2002), 53–65.
42.
ChunB.G.ZhaoB.Y. and KubiatowiczJ.D., Impact of neighbour selection on performance and resilience of structured P2P networks, in: International Workshop on Peer-to-Peer Systems, Springer (2005), 264–274.
43.
MankuG.S.NaorM. and WiederU., Know the neighbour’s neighbour: The power of look ahead in randomized P2P networks, in: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, ACM (2004), 54–63.
44.
GodfreyP.ShenkerS. and StoicaI., Minimizing churn in distributed systems, in: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM (2006), 147–158.
45.
Liben-NowellD.BalakrishnanH. and KargerD., Analysis of the evolution of peer-to-peer systems, in: Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing, ACM (2002), 233–242.
46.
LiJ.StriblingJ.MorrisR. and KaashoekM.F., Bandwidth-efficient management of DHT routing tables, in: Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation, ACM (2005), 99–114.
47.
ZhangH.GoelA. and GovindanR., Incrementally improving lookup latency in distributed hash table systems, in: ACM SIGMETRICS Performance Evaluation Review31(1) (2003), 114–125.
48.
MengX.ChenX. and DingY., Using the complementary nature of node joining and leaving to handle churn problem in P2P networks, Computers & Electrical Engineering39(2) (2013), 326–337.
49.
WuD.TianY. and NgK.W., An analytical study on optimizing the lookup performance of distributed hash table systems under churn, Concurrency and Computation: Practice and Experience19(4) (2007), 543–569.
50.
HildrumK.KubiatowiczJ.D.RaoS. and ZhaoB.Y., Distributed object location in a dynamic network, in: Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, ACM (2002), 41–52.
51.
RheaS.GeelsD.RoscoeT. and KubiatowiczJ., Handling churn in a DHT, in: Proceedings of the USENIX Annual Technical Conference (2004), 127–140.
52.
SaiaJ.FiatA.GribbleS.D.KarlinA.R. and SaroiuS., Dynamically fault-tolerant content addressable networks, in: Peer to Peer Systems1 (2002), 270–279.
53.
BustamanteF.E. and QiaoY., Designing less-structured P2P systems for the expected high churn, IEEE/ACM Transactions on Networking (TON)16(3) (2008), 617–627.
54.
SitE. and MorrisR., Security considerations for peer-to-peer distributed hash tables, in: International Workshop on Peer-to-Peer Systems, Springer (2002), 261–269.
55.
SrivatsaM. and LiuL., Vulnerabilities and security threats in structured overlay networks: A quantitative analysis, in: 20th Annual Computer Security Applications Conference, IEEE (2004), 252–261.
56.
PretreB., Attacks on peer-to-peer networks, Department of Computer Science, Swiss Federal Institute of Technology (ETH) Zurich, 2005.
57.
KwokY.K., Autonomic peer-to-peer systems: Incentive and security issues, in: Autonomic Computing and NetworkingDenkoM.K.YangL.T. and ZhangY., eds, Springer, 2009, pp. 205–236.
58.
KuhnF.SchmidS. and WattenhoferR., Towards worst-case churn resistant peer-to-peer systems, in: Distributed Computing22(4) (2010), 249–267.
59.
LiX.MisraJ. and PlaxtonC.G., Active and concurrent topology maintenance, in: International Symposium on Distributed Computing, Springer (2004), 320–334.
60.
DickM.E.PacittiE.AkbariniaR. and KemmeB., Building a peer-to-peer content distribution network with high performance, scalability and robustness, in: Information Systems36(2) (2011), 222–247.
61.
YangB.B. and Garcia-MolinaH., Designing a super-peer network, in: Proceedings of the 19th IEEE International Conference on Data Engineering, IEEE (2003), 49–60.
NejdlW.WolpersM.SiberskiW.SchmitzC.SchlosserM.BrunkhorstI. and LöserA., Super-peer-based routing and clustering strategies for RDF-based peer-to-peer networks, in: Proceedings of the 12th International Conference on World Wide Web, ACM (2003), 536–543.
64.
SachaJ.DowlingJ.CunninghamR. and MeierR., Discovery of stable peers in a self-organising peer-to-peer gradient topology, in: IFIP International Conference on Distributed Applications and Interoperable Systems, Springer (2006), 70–83.
65.
ZölsS.HofstätterQ.DespotovicZ. and KellererW., Achieving and maintaining cost-optimal operation of a hierarchical DHT system, in: Proceedings of the IEEE International Conference on Communications, IEEE (2009), 2194–2199.
66.
TrifaZ. and KhemakhemM., A novel replication technique to attenuate churn effects, in: Journal of Peer-to-Peer Networking and Applications9(2) (2016), 344–355.
67.
KorzunD. and GurtovA., Hierarchical architectures in structured peer-to-peer overlay networks, in: Journal of Peer-to-Peer Networking and Applications7(4) (2014), 359–395.
68.
KoskelaT.HarjulaE.KassinenO. and YlianttilaM., Robustness of a P2P community management system based on two-level hierarchical DHT overlays, in: IEEE Symposium on Computers and Communications (ISCC), IEEE (2011), 881–886.
69.
MarielaJ.RocamoraB.RhodetteJ. and PedrasaI., Evaluation of hierarchical DHTs to mitigate churn effects in mobile networks, Computer Communications85(1) (2016), 41–57.
70.
GanesanP.GummadiK. and Garcia-MolinaH., Canon in G major: Designing DHTs with hierarchical structure, in: Proceedings of the 24th International Conference on Distributed Computing Systems, IEEE (2004), 263–272.
71.
FreedmanM.J.LakshminarayananK. and StoicaI., Non-transitive connectivity and DHTs, in: WORLDS5(1) (2005), 10–10.
72.
GhodsiA., Distributed k-ary system: Algorithms for distributed hash tables, Doctoral Dissertation, The Royal Institute of Technology, 2006.
73.
ShafaatT.M., Partition tolerance and data consistency in structured overlay networks, Doctoral Dissertation, KTH, School of Information and Communication Technology, 2013.
74.
PaulR.R.RoyP.V. and VlassovV., Interaction between network partitioning and churn in a self-healing structured overlay network, in: 21st International Conference on Parallel and Distributed Systems (ICPADS), IEEE (2015), 232–241.
75.
KaurR.SangalA.L. and KumarK., Modelling and simulation of adaptive neuro-fuzzy based intelligent system for predictive stabilization in structured overlay networks, Engineering Science and Technology, An International Journal20(1) (2017), 310–320.
76.
KaurR.SangalA.L. and KumarK., Performance analysis of predictive stabilization for churn handling in structured overlay networks, in: Proceedings of the International Conference on Big Data and Advanced Wireless Technologies, ACM (2016), 39–45.
77.
KaurR.SangalA.L. and KumarK., A persistent structured hierarchical overlay network to counter intentional churn attack, in: Journal of Computer Networks and Communications (2016), 1–15.
