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

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. Keywords: Peer-To-Peer Network, Publish/Subscribe Systems, Overlay Network Diameter, Node Degree, Decentralized / Centralized Topology, Minimum Maximum Node Degree.