Technical report detail

Understanding Content-Based Routing Schemes

by Carzaniga, Antonio and Rembert, Aubrey J. and Wolf, Alexander L.

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.

Technical report 2006/05, September 2006

BibTex entry

@techreport{06understanding, author = {Carzaniga, Antonio and Rembert, Aubrey J. and Wolf, Alexander L.}, title = {Understanding Content-Based Routing Schemes}, institution = {University of Lugano}, number = {2006/05}, year = 2006, month = sep }