Research Article
BibTex RIS Cite

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

Year 2022, , 1535 - 1552, 16.12.2022
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%).

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).

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

Year 2022, , 1535 - 1552, 16.12.2022
https://doi.org/10.2339/politeknik.823124

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).

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).
There are 37 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Research Article
Authors

Semih Yumuşak 0000-0002-8878-4991

Sina Layazali This is me 0000-0002-9721-312X

Kasım Öztoprak 0000-0003-2483-8070

Reza Hassanpour This is me 0000-0001-8649-9671

Publication Date December 16, 2022
Submission Date November 8, 2020
Published in Issue Year 2022

Cite

APA Yumuşak, S., Layazali, S., Öztoprak, K., Hassanpour, R. (2022). A Novel Hypercube-based Approach to Overlay Design Algorithms on Topic Distribution Networks. Politeknik Dergisi, 25(4), 1535-1552. https://doi.org/10.2339/politeknik.823124
AMA Yumuşak S, Layazali S, Öztoprak K, Hassanpour R. A Novel Hypercube-based Approach to Overlay Design Algorithms on Topic Distribution Networks. Politeknik Dergisi. December 2022;25(4):1535-1552. doi:10.2339/politeknik.823124
Chicago Yumuşak, Semih, Sina Layazali, Kasım Öztoprak, and Reza Hassanpour. “A Novel Hypercube-Based Approach to Overlay Design Algorithms on Topic Distribution Networks”. Politeknik Dergisi 25, no. 4 (December 2022): 1535-52. https://doi.org/10.2339/politeknik.823124.
EndNote Yumuşak S, Layazali S, Öztoprak K, Hassanpour R (December 1, 2022) A Novel Hypercube-based Approach to Overlay Design Algorithms on Topic Distribution Networks. Politeknik Dergisi 25 4 1535–1552.
IEEE S. Yumuşak, S. Layazali, K. Öztoprak, and R. Hassanpour, “A Novel Hypercube-based Approach to Overlay Design Algorithms on Topic Distribution Networks”, Politeknik Dergisi, vol. 25, no. 4, pp. 1535–1552, 2022, doi: 10.2339/politeknik.823124.
ISNAD Yumuşak, Semih et al. “A Novel Hypercube-Based Approach to Overlay Design Algorithms on Topic Distribution Networks”. Politeknik Dergisi 25/4 (December 2022), 1535-1552. https://doi.org/10.2339/politeknik.823124.
JAMA Yumuşak S, Layazali S, Öztoprak K, Hassanpour R. A Novel Hypercube-based Approach to Overlay Design Algorithms on Topic Distribution Networks. Politeknik Dergisi. 2022;25:1535–1552.
MLA Yumuşak, Semih et al. “A Novel Hypercube-Based Approach to Overlay Design Algorithms on Topic Distribution Networks”. Politeknik Dergisi, vol. 25, no. 4, 2022, pp. 1535-52, doi:10.2339/politeknik.823124.
Vancouver Yumuşak S, Layazali S, Öztoprak K, Hassanpour R. A Novel Hypercube-based Approach to Overlay Design Algorithms on Topic Distribution Networks. Politeknik Dergisi. 2022;25(4):1535-52.
 
TARANDIĞIMIZ DİZİNLER (ABSTRACTING / INDEXING)
181341319013191 13189 13187 13188 18016 

download Bu eser Creative Commons Atıf-AynıLisanslaPaylaş 4.0 Uluslararası ile lisanslanmıştır.