Incremental Topology Transformation for Publish/Subscribe Systems Using Integer Programming

Abstract

Distributed overlay-based publish/subscribe systems provide a selective, scalable, and decentralized approach to data dissemination. Due to the dynamic communication flows between data producers and consumers, the overlay topology of such systems can become inefficient over time and therefore requires adaptation to the existing load. Existing studies propose algorithms to design overlay topologies which are optimized for specific workloads. However, the problem of generating a plan to incrementally transform the current topology to an optimized one has been largely ignored. In this paper, we present IPITT, an approach based on integer programming for the incremental topology transformation (ITT) problem. Given the current topology and a target topology, IPITT generates a transformation plan with a minimal number of steps in order to lessen service disruption. Furthermore, we introduce a plan execution mechanism and evaluate our approach on an existing publish/subscribe system. Based on our evaluation, IPITT can reduce plan computation time by a factor of 10 and generates plans with an execution time up to 55% shorter than those of existing approaches.