Preprint

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
    2006

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.
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
  • RERO DOC 10715
Persistent URL
https://susi.usi.ch/usi/documents/317925
Statistics

Document views: 8 File downloads:
  • ITR0605.pdf: 3