Abstract | ||
---|---|---|
Content-based publish/subscribe overlay is gaining popularity in large-scale content distribution applications for its flexibility and anonymity. Since such overlays are built on top of diverse infrastructures, minimizing the cost of using bandwidth in the overlays is a complicated task. In this paper, we tackle this task using a combinatorial optimization approach. We assume that each user can simultaneously be publisher and subscriber, and brokers are dedicated servers. We first formulate a two-stage optimization problem, which captures the cost of routing traffic in different parts of the overlay. Our solution is obtained by separately approximating the problem of each stage and then combining the results of sub-problems. In order to achieve better results, we further propose a novel formulation based on sub-channeling and Steiner tree/star problem, which simplifies the analysis of content-based routing and facilitate an intuitive randomized approximation algorithm. This algorithm is then translated into a decentralized one that dynamically adjusts the overlay connections when the network undergoes dynamisms. Simulation results demonstrate that our algorithms substantially reduce the cost of constructing content-based publish/subscribe overlay. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1109/SAHCN.2011.5984933 | SECON |
Keywords | Field | DocType |
optimisation,content based routing,combinatorial optimization,content-based publish/subscribe overlay,data communication,routing traffic,steiner tree/star,integer programming,two stage optimization problem,large scale content distribution application,approximation algorithm,minimum cost content based publish/subscribe overlays,computer networks,intuitive randomized approximation algorithm,middleware,subchanneling,message passing,telecommunication network routing,np-complete,steiner tree/star problem,steiner trees,bandwidth,approximation algorithms,clustering algorithms,indexing terms,optimization problem,publish subscribe,np complete,optimization,dynamic simulation,steiner tree | Middleware,Approximation algorithm,Steiner tree problem,Computer science,Server,Computer network,Combinatorial optimization,Overlay,Optimization problem,Message passing,Distributed computing | Conference |
ISSN | ISBN | Citations |
2155-5486 | 978-1-4577-0094-1 | 3 |
PageRank | References | Authors |
0.43 | 11 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yaxiong Zhao | 1 | 115 | 7.18 |
Jie Wu | 2 | 8307 | 592.07 |