Modeling the Communication Costs of Content-based Routing: The Case of Subscription Forwarding

Content-based routing (CBR) provides the core distribution support of several middleware paradigms, most notably content-based publish/subscribe. Despite its popularity, however, the performance of content-based routing protocols is typically evaluated through simulation, and analytical models are extremely rare in the literature. Analytical models capture formally the characteristic of the analyzed system, and are therefore worth pursuing on their own. However, they also provide very practical advantages in that they allow one to evaluate tradeoffs extensively (i.e., across many parameter combinations and across all the interesting values) without the lengthy computation times required by simulations. These benefits are particularly welcome when large-scale networks are considered. In this paper, we provide an analytical model for subscription forwarding, arguably the most common content-based routing protocol in use today and one that is often used as a baseline against which to compare new approaches. We provide closed analytical expressions for the overall network traffic required to disseminate subscriptions and propagate notifications, as well as for the message forwarding load on individual nodes. The analytical model we present is validated through simulation for networks with more than 100,000 nodes and against several combinations of the relevant parameters. Results show that our model remains within 3\% of the simulated traffic (and in most scenarios well below 1\%), therefore indicating that our model can effectively replace simulations. The paper is completed by some examples of how our analytical model can be used in practice, including a precise characterization of the tradeoffs between subscription forwarding and event forwarding.