Brief announcement: parameterized maximum and average degree approximation in topic-based publish-subscribe overlay network design

ABSTRACT

Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions connect the nodes into a graph which has low average and maximum degree and in such a way that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial time parameterized sublinear approximation algorithm for this problem.

REFERENCES

• 1: Gregory Chockler , Roie Melamed , Yoav Tock , Roman Vitenberg, Constructing scalable overlays for pub-sub with many topics, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281118]
• 2: M. Onus and A.W. Richa. Parameterized Maximum and Average Degree Approximation in Topic-based Publish-Subscribe Overlay Network Design. In Technical Report, Arizona State University, Department of Computer Science and Engineering, TR-09-006, 2009.
• 3: M. Onus and A.W. Richa. Minimum maximum Degree Publish-Subscribe Overlay Network Design. In INFOCOM, 2009.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Experimentation, Theory

Keywords:
multicast, optimization, overlay networks, peer-to-peer, pub/sub