A Novel Hypercube-based Approach to Overlay Design Algorithms on Topic Distribution Networks

Year 2022, Volume: 25 Issue: 4, 1535 - 1552, 16.12.2022

Semih Yumuşak Sina Layazali Kasım Öztoprak Reza Hassanpour

https://doi.org/10.2339/politeknik.823124

Abstract

Data communication in peer-to-peer (P2P) network requires a fine-grained optimization for memory and processing to lower the total energy consumption. When the concept of Publish/subscribe (Pub/Sub) systems were used as a communication tool in a P2P network, the network required additional optimization algorithms to reduce the complexity. The major difficulty for such networks was creating an overlay design algorithm (ODA) to define the communication patterns. Although some ODAs may perform worse on a high-scale, some may have better average/maximum node degrees. Based on the experimentation and previous works, this study designed an algorithm called the Hypercube-ODA, which reduces the average/maximum node degree for a topic connected Pub/Sub network. The Hypercube-ODA algorithm creates the overlay network by creating random cubes within the network and arranging the nodes with the cubes they belong to. In this paper, the details of the proposed Hypercube algorithm were presented and its performance was compared with the existing ODAs. Results from the experiments indicate that the proposed method outperforms other ODA methods in terms of lower average node degree (lowering the average node degree by up to 60%).

Keywords

Peer-To-Peer Networks, Publisher/Subscriber Systems, Overlay Network Diameter, Maximum Node Degree

Hiperküp Tabanlı Konu Dağıtım Ağlarında Yeni Bir Katman Tasarım Algoritması

Abstract

Peer-to-peer (P2P) ağda veri iletişimi, toplam enerji tüketimini azaltmak için bellek ve işleme için ayrıntılı bir optimizasyon gerektirir. Yayınlama / abone olma (Pub / Sub) sistemleri kavramı bir P2P ağında bir iletişim aracı olarak kullanıldığında, ağ karmaşıklığını azaltmak için ek optimizasyon algoritmaları gerektirmektedir. Bu tür ağlar için en büyük zorluk, iletişim modellerini tanımlamak için bir katman tasarım algoritması (ODA) oluşturmaktı. Bazı ODA'lar yüksek ölçekte daha kötü performans gösterse de, bazıları daha iyi ortalama / maksimum düğüm derecelerine sahip olabilir. Deney ve önceki çalışmalara dayanarak, bu çalışmada, Pub / Sub ağına bağlı bir konu için ortalama / maksimum düğüm derecesini azaltan Hypercube ODA adı verilen bir algoritma tasarlandı. Hypercube-ODA algoritması katman ağını yaratmak için rastlantısal küp yapıları kullanarak, küp komşuluklarının düzenlenmesi ile ağı oluşturur. Bu çalışmada, önerilen Hypercube algoritmasının ayrıntıları sunuldu ve performansı mevcut ODA'lar ile karşılaştırıldı. Deneylerden elde edilen sonuçlar, önerilen yöntemin daha düşük ortalama düğüm derecesi açısından diğer ODA yöntemlerinden daha iyi performans gösterdiğini göstermektedir (ortalama düğüm derecesinin %60’a kadar iyileştirildiği gözlemlenmiştir).

Keywords

Peer-To-Peer Ağ, Publisher/Subscriber Sistemler, Overlay Network, Maximum Node Degree

References

• [1] Chen J., Arumaithurai M., Jiao L., Fu X,Ramakrishnan K.K., “COPSS: An Efficient Content Oriented Publish/Subscribe System”, ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems (ANCS ’11), 99-110 (2011).
• [2] Pham, V.-N., Nguyen, V., Nguyen, T.D.T., Huh, E.-N., “Efficient Edge-Cloud Publish/Subscribe Broker Overlay Networks to Support Latency-Sensitive Wide-Scale IoT Applications”, Symmetry, 12(3), (2020).
• [3] Oztoprak K., Kilic H., "Protocol and Connectivity Based Overlay Level Capacity Calculation of P2P Networks," IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology Workshops, 447-450, (2006)
• [4] Feldmann M., Scheideler C.,Schmid S.,“Survey on Algorithms for Self-stabilizing Overlay Networks”, ACM Comput. Surv. 53(4): Article 74, (2020)
• [5] Yumusak S., Layazali S., Oztoprak K., Hassanpour R., “Low-diameter topic-based pub/sub overlay network construction with minimum–maximum node degree.”, PeerJ Computer Science, 7(e538), (2021)
• [6] Alsultan M., Oztoprak K., Hassanpour R., “Power aware routing protocols in wireless sensor network”, IEICE Transactions on Communications 99 (7): 1481–1491, (2016)
• [7] Oztoprak, K., "fCDN:A Novel-Energy Efficient Content Delivery Architecture over Next Generation Systems", Politeknik Dergisi, 21(4): 999-1006, (2018)
• [8] Layazali S., Oztoprak K., Dogdu E., “Topic Distribution Constant Diamater Overlay Design Algorithm (TD-CD-ODA)”, IEEE 11th International Conference on Semantic Computing, 482–487, (2017).
• [9] Eugster P. T., Felber P. A., Guerraoui R., Kermarrec A.-M., “The many faces of publish/subscribe”, ACM Computing Surveys (CSUR), 35 (2): 114–131, (2003).
• [10] Costa, P. Á., Fouto, P., Leitão, J., "Overlay Networks for Edge Management." IEEE 19th International Symposium on Network Computing and Applications (NCA), 2020.
• [11] Chockler G., Melamed R., Tock Y., Vitenberg R., “Spidercast:a scalable interest-aware overlay for topic-based pub/sub communica-tion,” Inaugural international conference on Distributed event-based systems, ACM, 14–25, (2007)
• [12] Li G., Muthusamy V., Jacobsen H.-A., “A distributed service-oriented architecture for business process execution”, ACM Transactions on the Web (TWEB), 4 (1), (2010).
• [13] Happ D., Bayhan S., Handziski V.. "JOI: Joint placement of IoT analytics operators and pub/sub message brokers in fog-centric IoT platforms." Future Generation Computer Systems, 119: 7-19 (2021).
• [14] Lasse O, , Gehrke O., Bindner H., "Applying overlay networks to the smart grid and energy collectives.", Electric Power Systems Research, 192: 106702, (2021).
• [15] Li, W., Sun, P., Han, R., "Path Segmentation-Based Hybrid Caching in Information-Centric Networks.", Future Internet, 13.1:16, (2021).
• [16] Naik, A. R., Keshavamurthy, B. N., "Next level peer-to-peer overlay networks under high churns: a survey." Peer-to-Peer Networking and Applications, 13.3: 905-931, (2020).
• [17] Triantafillou P., Aekaterinidis I., “Content-based publish-subscribe overstructured p2p networks”, Third International Workshop on Distributed Event-based Systems (DEBS), 104–109, (2004).
• [18] Onus M.,Richa A. W., “Minimum maximum-degree publish-subscribe overlay network design,”, IEEE/ACM Transactions on Networking (TON), 19(5):1331–1343, (2011).
• [19] Castro M., Druschel P., Kermarrec A.-M., Rowstron A. I., “Scribe: Alarge-scale and decentralized application-level multicast infrastructure”, IEEE Journal on Selected Areas in communications, 20 (8):1489–1499, (2002).
• [20] Chockler G., Melamed R., Tock Y., Vitenberg R., “Construct-ing scalable overlays for pub-sub with many topics,” Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing, 109–118, (2007).
• [21] Carzaniga A., Rosenblum D. S., Wolf A. L., “Design and evaluation ofa wide-area event notification service”, ACM Transactions on Computer Systems (TOCS), 19 (3): 332–383, (2001).
• [22] Terpstra W. W., Behnel S., Fiege L., Zeidler A., Buchmann A. P., “A peer-to-peer approach to content-based publish/subscribe”, 2nd International Workshop on Distributed Event-based Systems, ACM, 1–8, (2003).
• [23] Tam, D., Azimi, R., Jacobsen, H.-A., “Building content-based publish/subscribe systems with distributed hash tables”, International Workshop on Databases, Information Systems, and Peer-to-Peer Computing, Springer, 138–152, (2003).
• [24] Khatibi E., Sharifi M.. "Resource discovery mechanisms in pure unstructured peer-to-peer systems: a comprehensive survey." Peer-to-Peer Networking and Applications, 1-18, (2020).
• [25] Chen C., Jacobsen H.-A., Vitenberg R., “Algorithms based on divide and conquer for topic-based publish/subscribe overlay design”, IEEE/ACM Transactions on Networking, 24 (1): 422–436, (2016).
• [26] Cao Y., Lung C.-H., Majumdar S., “Efficient message delivery models for xml-based publish/subscribe systems”, Computer Communications, 85(30):58–73, (2016)
• [27] Bozdagi G., Oztoprak K., “Hybrid fault tolerant peer to peer videostreaming architecture, IEICE Transactions on Communications, 91 (11): 3627–3638, (2008).
• [28] Oztoprak, K. ,Akar, G. B., "Two-Way/Hybrid Clustering Architecture for Peer to Peer Systems”, Second International Conference on Internet and Web Applications and Services (ICIW'07),11-11, (2007)
• [29] Zhao Y., Kim K., Venkatasubramanian N., “Dynatops: a dynamic topic-based publish/subscribe architecture”, 7th ACM International conference on Distributed event-based systems, ACM, 75–86, (2013).
• [30] Havet, F., Mazauric D., Nguyen V. , Watrigant R., “Overlaying ahypergraph with a graph with bounded maximum degree,” Research Report, RR-9258, Inria Sophia Antipolis, hal-02025469, (2019).
• [31] Diestel R., Graph Theory, Springer-Verlag, 2nd edition, New York, (2000).
• [32] Onus M., Richa A. W., “Minimum Maximum Degree Publish-Subscribe Overlay Network Design”, 28th Annual IEEE Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, (2009).
• [33] Onus M., Richa A. W., “Parameterized maximum and average degree approximation in topic-based publish-subscribe overlay network de-sign,” , IEEE 30th International Conference on Distributed Computing Systems (ICDCS), 644–652, (2010).
• [34] R. Baldoni, R. Beraldi, V. Quema, L. Querzoni, and S. Tucci-Piergiovanni, “Tera: Topic-based event routing for peer-to-peer archi-tectures,”, Inaugural International Conference on Distributed Event-based Systems, 2–13, (2007).
• [35] L. C. Lau, J. S. Naor, M. R. Salavatipour, and M. Singh, “Survivable network design with degree or order constraints” , The Thirty-ninth annual ACM symposium on Theory of computing - STOC’07, 651–660, (2007).
• [36] E. De Santis, F. Grandoni, A. Panconesi, Fast low degree connectivityof ad-hoc networks via percolation, European Symposium on Algorithms, Springer, 206–217, (2007).
• [37] M. Onus and A. W. Richa, “Parameterized maximum and average de-gree approximation in topic-based publish-subscribe overlay network design,” Computer Networks, 94:307-317, (2016).