Constructing low diameter topic-based Pub/Sub overlay network with minimum maximum node degree

Abstract

Publish/subscribe communication systems, where a large number of nodes (publishers and subscribers) are interested in variety of topics, have received more attention in recent years. Constructing an efficient overlay network that connects the nodes interested in several topics is an important issue in these systems. In constructing effective and scalable overlay networks, pub/sub network designers prefer to keep the diameter and maximum degree of the network low. This is in addition to lower running time cost and higher scalability. However, the existing algorithms seem to fail in decreasing maximum node degree and reducing diameter. To address these issues for a given set of nodes with variety of topics, we present a heuristic algorithm known as Constant Diameter Minimum Maximum Degree (CD-MAX) which decreases the maximum node degree and maintains the diameter of the overlay at most at two. The new algorithm improves the maximum node degree, by 64 percent. The CD-MAX algorithm selects the node with the lowest node degree and connects it to its neighbors. For more than two nodes with an equal highest node degree, this algorithm selects the node with the highest density. The CD-MAX algorithm has a refinement version that decreases the maximum node degree even further. The algorithm is validated and analyzed through simulations.

Birçok abonelik içeren, Yayınla / Abone Ol iletişim sistemleri giderek daha yaygınlaşmaktadır. Konuların her birine ayrı ayrı abone olmuş düğüm iletişimlerini birbirine bağlayan etkin bir bindirmeli ağ tasarımı yapmak bu sistemlerin temel problemidir. Bir bindirmeli ağ tasarlamak için ideal olan, yalnızca maksimum düğüm derecesinin düşük tutulması değil, aynı zamanda ağın düşük çaplı ve ölçeklenebilir olması da önemlidir. Mevcut algoritmalar maksimum düğüm derecesi ve çapını düşürmekte başarısız bulunmaktadır. Bu çalışmada, maksimum düğüm derecesini düşüren ve ağ çapını en fazla ikide sabitleyen, Sabit Çap Minimum Maksimum Dereceli (CD-MAX) adı verilen yeni bir algoritma sunulmaktadır. CD-MAX algoritması maksimum düğüm derecesini yaklaşık %64 iyileştiren bir algoritmadır. Ölçeklenebilir bir ağ kurabilmek için, CD-MAX algoritması en düşük düğüm dercesine sahip düğümü seçer ve bu düğümü bitişik düğülmelere bağlar. Eşit düğüm derecesine sahip birden fazla düğüm varsa, algoritma en yüksek yoğunluğa sahip düğümü seçer. CD-MAX algoritmasının düğüm derecesini daha da aşağı çeken bir versiyonu da bu çalışmaya dahil edilmiştir. Algoritmanın doğrulanması ve analizi simülasyon ortamında gerçekleştirilmişti