More Web Proxy on the site http://driver.im/

research-article

Efficient content-based routing with network topology inference

Authors:

Muhammad Adnan Tariq,

Boris Koldehofe,

Kurt RothermelAuthors Info & Claims

DEBS '13: Proceedings of the 7th ACM international conference on Distributed event-based systems

Pages 51 - 62

https://doi.org/10.1145/2488222.2488262

Published: 29 June 2013 Publication History

Abstract

Content-based publish/subscribe has gained high popularity for large-scale dissemination of dynamic content. Yet it is highly challenging to enable communication-efficient dissemination of content in such systems, especially in the absence of a broker infrastructure. This paper presents a novel approach that exploits the knowledge of event traffic, user subscriptions and topology of the underlying physical network to perform efficient routing in a publish/subscribe system. In particular, mechanisms are developed to discover the underlay topology among subscribers and publishers in a distributed manner. The information of the topology and the proximity between the subscribers to receive similar events is then used to construct a routing overlay with low communication cost. Our evaluations show that for internet-like topologies the proposed inference mechanisms are capable of modeling an underlay in an efficient and accurate manner. Furthermore, the approach yields a significant reduction in routing cost in comparison to the state of the art.

References

[1]

R. Campos and M. Ricardo. A fast algorithm for computing minimum routing cost spanning trees. Comput. Netw., 2008.

Digital Library

[2]

C. Cheng, I. Cimet, and S. Kumar. A protocol to maintain a minimum spanning tree in a dynamic topology. SIGCOMM Comput. Commun. Rev., 1988.

Digital Library

[3]

A. K. Y. Cheung and H.-A. Jacobsen. Green resource allocation algorithms for publish/subscribe systems. In Intl. conf. on distributed computing systems, 2011.

Digital Library

[4]

K. L. Clarkson. Nearest-neighbor searching and metric space dimensions. In Nearest-neighbor methods for learning and vision: theory and practice. 2006.

[5]

M. Costa, M. Castro, A. Rowstron, and P. Key. PIC: Practical Internet coordinates for distance estimation. In Intl. conf. on distributed computing systems, 2004.

Digital Library

[6]

B. Donnet and T. Friedman. Internet topology discovery: A survey. IEEE Comm. Surv. Tuts., 2007.

Digital Library

[7]

B. Donnet, P. Raoult, T. Friedman, and M. Crovella. Deployment of an algorithm for large-scale topology discovery. IEEE J.Sel. A. Commun., 2006.

[8]

C. Esposito, D. Cotroneo, and A. Gokhale. Reliable publish/ subscribe middleware for time-sensitive Internet-scale applications. In DEBS, 2009.

Digital Library

[9]

M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the Internet topology. SIGCOMM Comput. Commun. Rev., 1999.

Digital Library

[10]

C. T. C. A. for Internet Data Analysis. http://www.caida.org/home/, 2012.

[11]

M. Goyal, M. Soperi, E. Baccelli, G. Choudhury, A. Shaikh, H. Hosseini, and K. Trivedi. Improving convergence speed and scalability in OSPF: A survey. IEEE Commun. Surveys Tuts., 2011.

[12]

M. H. Gunes and K. Sarac. Resolving anonymous routers in Internet topology measurement studies. In IEEE INFOCOM, 2008.

[13]

A. Gupta, O. D. Sahin, D. Agrawal, and A. E. Abbadi. Meghdoot: Content-based publish/subscribe over P2P networks. In Intl. conf. on middleware, 2004.

Digital Library

[14]

M. A. Jaeger, H. Parzyjegla, G. Muehl, and K. Herrmann. Self-organizing broker topologies for publish/subscribe systems. In ACM sympos. on appl. comput. (SAC), 2007.

Digital Library

[15]

S. Jain, R. Mahajan, D. Wetherall, and G. Borriello. Scalable self-organizing overlays. Technical Report UW-CSE 02-02-02, University of Washington, 2002.

[16]

M. Jelasity, W. Kowalczyk, and M. v. Steen. An approach to massively distributed aggregate computing on peer-to-peer networks. In Workshop on parallel, distributed and network-based processing (PDP), 2004.

[17]

M. Jelasity, A. Montresor, G. P. Jesi, and S. Voulgaris. PeerSim: A peer-to-peer simulator. http://peersim.sourceforge.net/.

[18]

X. Jin, W. Tu, and S. H. G. Chan. Scalable and efficient end-to-end network topology inference. IEEE Trans. Parallel Distrib. Syst., 2008.

Digital Library

[19]

X. Jin, W. Tu, and S.-H. G. Chan. Traceroute-based topology inference without network coordinate estimation. In IEEE intl. conf. on commun., 2008.

[20]

X. Jin, Y. Wang, and S.-H. G. Chan. Fast overlay tree based on efficient end-to-end measurements. In IEEE intl. conf. on commun. (ICC), 2005.

[21]

X. Jin, W. P. Yiu, S. H. Chan, and Y. Wang. On maximizing tree bandwidth for topology-aware peer-to-peer streaming. IEEE Transactions on Multimedia, 9:1580--1592, 2007.

Digital Library

[22]

S. Kanchi and D. Vineyard. An optimal distributed algorithm for ALL-pairs shortest-path. Intl.J.on Information Theories & App., 11:141--146, 2004.

[23]

S. Kandula, D. Katabi, S. Sinha, and A. Berger. Dynamic load balancing without packet reordering. ACM SIGCOMM Comput. Commun. Rev., 2007.

Digital Library

[24]

M. Kwon and S. Fahmy. Path-aware overlay multicast. Comput. Netw., 47:23--45, 2005.

Digital Library

[25]

A. Majumder, N. Shrivastava, R. Rastogi, and A. Srinivasan. Scalable content-based routing in pub/sub systems. In IEEE INFOCOM, 2009.

[26]

A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: Universal topology generation from a user's perspective. Technical report, Boston University, 2001.

Digital Library

[27]

O. Papaemmanouil, Y. Ahmad, U. Cetintemel, J. Jannotti, and Y. Yildirim. Extensible optimization in overlay dissemination trees. In Proc. of ACM SIGMOD intl. conf. on management of data, 2006.

Digital Library

[28]

O. Papaemmanouil and U. Cetintemel. SemCast: Semantic multicast for content-based data dissemination. In Intl. conf. on data engineering (ICDE), 2005.

Digital Library

[29]

I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for Internet applications. IEEE/ACM Transactions on Networking, 11:17--32, 2003.

Digital Library

[30]

M. A. Tariq, G. G. Koch, B. Koldehofe, I. Khan, and K. Rothermel. Dynamic publish/subscribe to meet subscriber-defined delay and bandwidth constraints. In Proc. of Intl. conf. on parallel computing (Euro-Par), 2010.

Digital Library

[31]

M. A. Tariq, B. Koldehofe, G. G. Koch, I. Khan, and K. Rothermel. Meeting subscriber-defined QoS constraints in publish/subscribe systems. Concurrency and Computation: Practice and Experience, 2011.

Digital Library

[32]

M. A. Tariq, B. Koldehofe, G. G. Koch, and K. Rothermel. Distributed spectral cluster management: A method for building dynamic publish/subscribe systems. In Intl. conf. on dist. event-based systems (DEBS), 2012.

Digital Library

[33]

B. Y. Wu and K.-M. Chao. Spanning Trees and Optimization Problems. Chapman and Hall, 2004.

[34]

E. W. Zegura, K. L. Calvert, and S. Bhattacharjee. How to model an internetwork. In IEEE intl. conf. on comp. commun. (INFOCOM), 1996.

Digital Library

[35]

X. Zhang and C. Phillips. A survey on selective routing topology inference through active probing. IEEE Communications Surveys & Tutorials, 2011.

[36]

Y. Zhu, B. Li, and K. Q. Pu. Dynamic multicast in overlay networks with linear capacity constraints. IEEE Trans. Parallel Distrib. Syst., 2009.

Digital Library

Cited By

Shi YWong JJacobsen HZhang YChen J(2020)Topic-Oriented Bucket-Based Fast Multicast Routing in SDN-Like Publish/Subscribe MiddlewareIEEE Access10.1109/ACCESS.2020.29942688(89741-89756)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2994268
Kim YKim YYoon HYeom I(2019)Peer-assisted multimedia delivery using periodic multicastInformation Sciences: an International Journal10.1016/j.ins.2014.11.033298:C(425-446)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2014.11.033
Chen CTock YGirdzijauskas S(2018)BeaConveyProceedings of the 12th ACM International Conference on Distributed and Event-based Systems10.1145/3210284.3210287(64-75)Online publication date: 25-Jun-2018
https://dl.acm.org/doi/10.1145/3210284.3210287
Show More Cited By

Index Terms

Efficient content-based routing with network topology inference

Recommendations

Trustworthiness of acquaintances in Peer-to-Peer overlay networks

Various types of applications manipulate objects distributed in Peer-to-Peer overlay networks. An acquaintance peer of a peer p is a peer whose service the peer p knows and with which the peer p can directly communicate. We discuss types of acquaintance ...
Towards a lightweight content-based publish/subscribe services for peer-to-peer systems

Peer-to-peer networks are unmanaged systems, where all participants cooperate in order to maintain the network structure and the services they provide. Particularly, structured peer-to-peer networks provide efficient, logarithmic communication cost ...
Routing algorithms for content-based publish/subscribe systems

In content-based publish/subscribe systems, messages target a dynamic group of participants whose expressed interests match the contents of the messages. In this generalization of multicasting communication, also dubbed content-based networking, naming, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DEBS '13: Proceedings of the 7th ACM international conference on Distributed event-based systems

June 2013

360 pages

ISBN:9781450317580

DOI:10.1145/2488222

General Chairs:
Sharma Chakravarthy
The University of Texas at Arlington, USA
,
Susan D. Urban
Texas Tech University, USA
,
Program Chairs:
Peter Pietzuch
Imperial College, UK
,
Elke Rundensteiner
Worcester Polytechnic Institute, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DEBS '13

Sponsor:

DEBS '13: The 7th ACM International Conference on Distributed Event-Based Systems

June 29 - July 3, 2013

Texas, Arlington, USA

Acceptance Rates

DEBS '13 Paper Acceptance Rate 16 of 58 submissions, 28%;

Overall Acceptance Rate 145 of 583 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
268
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shi YWong JJacobsen HZhang YChen J(2020)Topic-Oriented Bucket-Based Fast Multicast Routing in SDN-Like Publish/Subscribe MiddlewareIEEE Access10.1109/ACCESS.2020.29942688(89741-89756)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2994268
Kim YKim YYoon HYeom I(2019)Peer-assisted multimedia delivery using periodic multicastInformation Sciences: an International Journal10.1016/j.ins.2014.11.033298:C(425-446)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2014.11.033
Chen CTock YGirdzijauskas S(2018)BeaConveyProceedings of the 12th ACM International Conference on Distributed and Event-based Systems10.1145/3210284.3210287(64-75)Online publication date: 25-Jun-2018
https://dl.acm.org/doi/10.1145/3210284.3210287
Tudoran RCostan ANano OSantos ISoncu HAntoniu G(2018)JetStreamFuture Generation Computer Systems10.1016/j.future.2015.01.01654:C(274-291)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1016/j.future.2015.01.016
Bhowmik STariq MKoldehofe BDurr FKohler TRothermel K(2017)High Performance Publish/Subscribe Middleware in Software-Defined NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2016.263297025:3(1501-1516)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1109/TNET.2016.2632970
Weisenburger PLuthra MKoldehofe BSalvaneschi GGarlan DNuseibeh B(2017)Quality-aware runtime adaptation in complex event processingProceedings of the 12th International Symposium on Software Engineering for Adaptive and Self-Managing Systems10.1109/SEAMS.2017.10(140-151)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1109/SEAMS.2017.10
Hakiri AGokhale AGal AWeidlich MKalogeraki VVenkasubramanian N(2016)Data-centric publish/subscribe routing middleware for realizing proactive overlay software-defined networkingProceedings of the 10th ACM International Conference on Distributed and Event-based Systems10.1145/2933267.2933314(246-257)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2933267.2933314
Chen CJacobsen HVitenberg R(2016)Algorithms based on divide and conquer for topic-based publish/subscribe overlay designIEEE/ACM Transactions on Networking10.1109/TNET.2014.236934624:1(422-436)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TNET.2014.2369346
Huanyang Zheng Jie Wu (2016)NSFA: Nested Scale-Free Architecture for scalable publish/subscribe over P2P networks2016 IEEE 24th International Conference on Network Protocols (ICNP)10.1109/ICNP.2016.7784413(1-10)Online publication date: Nov-2016
https://doi.org/10.1109/ICNP.2016.7784413
Wang NWu J(2016)Minimizing the Subscription Aggregation Cost in the Content-Based Pub/Sub System2016 25th International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2016.7568544(1-9)Online publication date: Aug-2016
https://doi.org/10.1109/ICCCN.2016.7568544
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents