Understanding content-based routing schemes

  • Carzaniga, Antonio Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
  • Rembert, Aubrey J. Department of Computer Science, University of Colorado, USA
  • Wolf, Alexander L. Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera

14 p.

English Content-based networking is a message-oriented communication service in which a message is delivered to all destinations that have declared a selection predicate matching the content of that message. Analogous to that of a traditional address-based network, a routing scheme in a content-based network defines the router-local matching, forwarding, and header functions that collectively realize the delivery function. Several such routing schemes have been proposed in the literature, but they have been evaluated only qualitatively or in simulation. In this paper we abstract from those previous results in an effort to place them in a general theoretical framework. This framework allows us to rigorously define notions of correctness, minimality, and complexity. In particular, we prove the correctness and characterize the complexity of two existing content-based routing schemes, propose a new latency-minimal scheme, and provide the results of a Monte Carlo simulation that serves as the basis for estimating the space requirements of any given scheme.
  • English
Computer science and technology
License undefined
  • RERO DOC 10715
  • ARK ark:/12658/srd1317925
Persistent URL

Document views: 41 File downloads:
  • ITR0605.pdf: 59