A routing scheme for content based networkingINFOCOM04

A Routing Scheme for Content-Based Networking Antonio Carzaniga, Matthew J. Rutherford, and Alexander L. Wolf Department of Computer Science University of Colorado Boulder, Colorado 80309-0430 USA Email: {carzanig,rutherfo,alw}@cs.colorado.edu Abstract— This paper proposes a routing scheme for content- based networking. A content-based network is a communication network that features a new advanced communication model where messages are not given explicit destination addresses, and where the destinations of a message are determined by matching the content of the message against selection predicates declared by nodes. Routing in a content-based network amounts to propagating predicates and the necessary topological information in order to maintain loop-free and possibly minimal forwarding paths for messages. The routing scheme we propose uses a combination of a traditional broadcast protocol and a content- based routing protocol. We present the combined scheme and its requirements over the broadcast protocol. We then detail the content-based routing protocol, highlighting a set of optimization heuristics. We also present the results of our evaluation, showing that this routing scheme is effective and scalable. I. INTRODUCTION Content-based communication is a communication service whereby the flow of messages from senders to receivers is driven by the content of the messages, rather than by explicit addresses assigned by senders and attached to the mes- sages [4]. Using a content-based communication service, re- ceivers declare their interests by means of selection predicates, while senders simply publish messages. The service consists of delivering to any and all receivers each message that matches the selection predicates declared by those receivers. In the content-based service model, message content is structured as a set of attribute/value pairs, and a selection predicate is a logical disjunction of conjunctions of elemen- tary constraints over the values of individual attributes. For example, a message might have the following content [class=“alert”, severity=6, device-type=“web-server”, alert-type=“hardware failure”] which would match a selection predicate such as this: [alert-type=“intrusion” ∧ severity>2 ∨ class=“alert” ∧ device-type=“web-server”] Content-based communication is ideally suited for a va- riety of application domains, including news distribution, publish/subscribe event notification, system monitoring and management, network intrusion detection, service discovery, data sharing, distributed electronic auctions, and distributed games. We believe that the best way to provide a content-based communication service is as a datagram, connectionless ser- vice, through a content-based network. We envision a content- based network as an overlay point-to-point network. Similarly to other traditional network services, routing in a content-based network amounts to synthesizing distribution paths throughout the network, while forwarding amounts to determining at each router the set of next-hop destinations of a message. content−based "physical" overlay complete message broadcast tree actual message forwarding path source source matching predicates nodes advertising Fig. 1. Network Overlay and High-Level Routing Scheme In this paper we present a combined broadcast and content- based (CBCB) routing scheme for a content-based network. This scheme consists of a content-based layer superimposed over a traditional broadcast layer. The broadcast layer handles each message as a broadcast message, while the content- based layer prunes the broadcast distribution paths, limiting the propagation of each message to only those nodes that advertised predicates matching the message. This strategy is illustrated in Figure 1. To implement this two-layer scheme, a router runs two distinct routing protocols: a broadcast routing protocol and a content-based routing protocol. The first protocol processes topological information and maintains the forwarding state necessary to send a message from each node to every other node. As it turns out, CBCB requires a broadcast layer that exhibits a specific topological property. Fortunately, this topological property can be satisfied by the most common broadcast schemes, with minimal modifications or with no modifications at all. In this paper we detail the requirements for the broadcast layer, and discuss how this layer can be implemented using protocols based on a global spanning tree, per-source minimal-paths spanning trees, or reverse-path broadcasting. The second protocol processes predicates advertised by nodes, and maintains the forwarding state that is necessary to decide, for each router interface, whether a message matches the predicates advertised by any downstream node reachable through that interface. This second protocol, which is the main focus of this paper, is based on a dual “push–pull” mechanism that guarantees robust and timely propagation of content-based routing information. These are the contributions of this paper: • We present a routing protocol specifically designed for a content-based network. To the best of our knowledge, this is the first protocol that realizes a content-based commu- nication service over a generic point-to-point network. • We show that (1) the protocol is scalable to large net- works, (2) the protocol realizes the content-based service with minimal missed deliveries and minimal unnecessary traffic, and (3) the protocol exhibits a stable behavior with respect to its control traffic. In the next section we describe the basics of the content- based service model and the general architecture of a content- based network. We then detail the routing scheme, with particular attention to the mechanisms that realize the content- based layer. Following that, we present the main results of the experimental evaluation we conducted. We then discuss related work. We conclude indicating some future plans. II. CONTENT-BASED NETWORKING A content-based network is a point-to-point, application- level overlay consisting of client nodes and router nodes, connected by communication links. By analogy with a physical network, we use the term interface to refer to the endpoint of a link. A content-based network accepts messages for delivery, and is connectionless and best-effort in nature. In a content-based network, nodes are not assigned unique network addresses, nor are messages addressed to any specific node. Instead, each node advertises a predicate that defines messages of interest for that node and, thus, the messages that the node intends to receive. The content-based service consists of delivering a message to all the client nodes that advertised predicates matching the message. The abstract concept of a content-based network service is independent of the form of messages and predicates. To instantiate this concept, we define messages and predicates using the concrete syntax and semantics embodied in the Siena event notification service [3]. Note that in this regard, Siena is largely consistent with other publish/subscribe systems [2], [9], [15] and with existing standards for application-level publish/subscribe services [11], [13]. Thus, a message is a set of typed attributes. Each attribute is uniquely identified within the message by a name, and has a type and a value. For purposes of this paper, we consider the common types string, integer, double, and boolean. For example, [string carrier = UA; string dest = ORD; int price = 300; bool upgradeable = true;] would be a valid message. A predicate is a disjunction of conjunctions of constraints on individual attributes. Each constraint has a name, a type, an operator, and a value. A constraint defines an elementary condition over a message. A message matches a constraint if it contains an attribute with the same name and type, and if the value matches the condition defined by the operator and value of the constraint. For example, [string dest = ORD ∧ int price < 400] is a valid predicate matching the message of the previous example. In our model of content-based network, each node imple- ments a service interface consisting of a send message(m) function and a set predicate(p) function. These functions are used by applications to send messages and to declare messages of interest respectively. The set predicate function defines the content-based address of the node, overwriting any previous setting. Our choice of a “stateless” set predicate function has two motivations: First, the resulting interface is simple and unam- biguous. Second, it is easy to implement other value-added interface models as higher layer services. For example, one such layer might support multiple applications running on a single node, mediating access to the set predicate function by maintaining and combining separate predicates for each application. A similar service layer could provide a “stateful” interface, supporting the incremental construction and modi- fication of the selection predicate. Examples of this kind of interface are implemented in many current publish/subscribe systems, where applications can issue and revoke individual subscriptions. III. THE CBCB ROUTING SCHEME A content-based network can be thought of as a dyna- mically-configurable broadcast network, where each message is treated as a broadcast message whose broadcast tree is dynamically pruned using content-based addresses. This ob- servation forms the basis of the high-level design of the CBCB routing scheme. CBCB consists of a content-based routing protocol imple- mented on top of a broadcast layer. The broadcast layer is necessary to make sure that a message flows from its source to all its destinations through loop-free and possibly minimal paths. The content-based layer is necessary to avoid sending a message towards nodes that are not interested in it. The broadcast layer is also used by the content-based protocol to propagate routing information. The high-level routing strategy of CBCB is to establish content-based routes by advertising predicates from their is- suer towards every other node, along the broadcast tree rooted at the issuer. This process produces forwarding state that “at- tracts” each message towards nodes that advertise predicates matching the message. In order to avoid loops, this forwarding state is used in combination with the broadcast tree rooted at the source of the message. Thus, the forwarding function proceeds by forwarding a message along the broadcast tree rooted at the sender, following only the branches that have matching predicates. A. Broadcast System CBCB uses a broadcast layer in combination with both its forwarding and routing functions. Without loss of generality, we will abstract this layer by assuming the availability of a broadcast function B : N × I → I∗ that, at each router, given a source node s and an input interface i, returns a set of output interfaces B(s, i). (Thus, N is the set of all the nodes in the network, and I is the set of the interfaces of the current router.) The obvious requirement for the broadcast layer is to define a broadcast tree for each source node s through the recursive application of B(s, ·). The broadcast layer can be implemented using a global spanning tree (e.g., minimal spanning tree), per-source trees (e.g., shortest-paths trees), or other broadcast methods such as reverse-path forwarding [7]. For example, in the case of per- source shortest-paths trees, B(s, i) would give the interfaces that are downstream from the current router, on the directed shortest-paths tree rooted in s, whereas, in the case of a reverse-path broadcast system, B(s, i) would give either the complete set of interfaces, if i is on the unicast (reverse) path to s, or the empty set otherwise. In addition to this basic requirement, the broadcast function B must satisfy a property that we call all-pairs path symmetry. This property is required by the high-level routing strategy of CBCB. In particular, the forwarding path of a message, from a sender to a receiver, is determined by the intersection of the broadcast tree rooted at the sender with the broadcast tree rooted at the receiver. Therefore, intuitively, the broadcast function must assure that such an intersection exists for each sender-receiver pair. Formally, a broadcast layer satisfies the all-pairs path symmetry property when, for each pair of nodes u and v, the broadcast function defines two broadcast trees Tu and Tv, rooted at nodes u and v respectively, such that the path u � v in Tu is congruent to the reverse of the path v � u in Tv . Notice that this property is immediately satisfied by a broadcast layer based on a global spanning tree T , because for each u and v, Tu = Tv = T . A broadcast layer based on per-source shortest-paths trees can also immediately exhibit all-pairs path symmetry in all cases in which shortest paths are unique. This is because the shortest-paths trees Tu and Tv will contain the same (unique) shortest path between u and v. In the presence of multiple shortest paths between two nodes u and v, the broadcast function can be easily adapted to unambiguously select one of the paths (see Section IV-A for some details). Similarly, a broadcast layer based on reverse- path forwarding will exhibit all-pairs symmetry as long as the underlying unicast routing protocol produces symmetric routes. B. Preliminary Definitions Before proceeding with the description of the content-based routing protocol, we briefly review the concept of content- based address [4] and that of covering relation between content-based addresses [3]. We define the content-based ad- dress of a node as a predicate—a total boolean function— that identifies the messages of interest for that node. In the following, we will use the terms content-based address and predicate interchangeably. In the following, we will also need to refer to the messages and sets of messages that are selected by a content-based address. Thus, we write p(m) to refer to the evaluation of a content-based address p over a message m, and we say that a content-based address p selects a message m when p(m) = true. Similarly, we refer to the set of all messages selected by a content-based address p as the selection of p (or selection(p)). We also define a covering relation between content-based addresses: we say that content-based address p1 covers con- tent-based address p2 iff ∀m : p2(m) ⇒ p1(m), or, in other words, p1 covers p2 iff selection(p2) ⊆ selection(p1). Notice that this covering relation defines a partial order between content-based addresses. For the sake of brevity, we also use the ‘≺’ symbol to indicate this relation. For example, p2 ≺ p1 indicates that p1 covers p2. C. Forwarding Scheme The content-based part of CBCB maintains forwarding state in the form of a content-based forwarding table. This forwarding table associates a content-based address to each external interface and to the local application interface. From the router’s perspective, it is convenient to represent the local application interface uniformly as an external interface. So, in the following, we will use interface I0 as the link to local applications, and interfaces I1 . . . Ik as the links to adjacent routers. source attribute1 attribute2 . . . Fig. 2. High-Level Structure of a Message Packet The content-based forwarding table is used by a content- based forwarding function FC that, given a message m, selects the subset of interfaces associated with predicates matching m. The result of FC is then combined with the broadcast function B, computed for the original source of m. (As shown in Figure 2, each message carries the identifier of the source node.) A message is therefore forwarded along the set of interfaces defined by the following formula: (B(source(m), incoming if(m)) ∪ {I0}) ∩ FC(m) We describe an efficient implementation of this formula else- where [5]. D. Routing State The content-based routing module of a CBCB router main- tains a routing table that associates a content-based address px to each interface Ix. Consistently with the forwarding table, we use interface I0 to represent applications running on the router (therefore, p0 is the content-based address set by local applications through set predicate), and I1 . . . Ik to represent actual network links. The information stored in this routing table is conceptually identical to that stored in the content-based forwarding table. In fact, the forwarding table is constructed and updated by mirroring the routing table. We will however treat the two tables as separate objects because in reality they might be implemented by two independent, specialized data structures. It makes sense to separate these two tables also because the routing protocol might allow for them to be out of sync at times. E. Content-Based Routing Protocol The content-based routing protocol of CBCB consists of two mechanisms for the propagation of routing information. The first is a “push” mechanism based on receiver advertisements. The second one is a “pull” mechanism based on sender requests and update replies. In this section, we will initially present the main features of these two mechanisms, and then detail their behavior and discuss options and optimizations. 1) Receiver Advertisements: Receiver advertisements (RAs) are issued by nodes periodically and/or when the node changes its local content-based address p0. RAs carry this content-based address as well as the identifier of their issuer. Their purpose is to push routing information from a receiver out to all potential senders, thereby setting up the forwarding state necessary to deliver messages of interest to the receiver. issuer predicate . . . Fig. 3. A Receiver Advertisement (RA) The structure of an RA packet is shown in Figure 3. RAs are propagated throughout the network using the following combined broadcast and content-based protocol: • Content-based RA ingress filtering: a router receiving through interface i an RA issued by node r and carrying content-based address pRA first verifies whether or not the content-based address pi associated with interface i covers pRA. If pi covers pRA, then the router simply drops the RA. • Broadcast RA propagation: if pi does not cover pRA, then the router computes the set of next-hop links on the broadcast tree rooted in r (i.e., B(r, i)) and forwards the RA along those links. • Routing table update: if pi does not cover pRA, then the router also updates its routing table, adding pRA to pi, computing pi ← pi ∨ pRA. The example of Figure 4 illustrates the propagation of RAs. Intuitively, nodes in the graph represent routers, and light- colored edges represent direct (physical or overlay) links. Initially (Figure 4a) node 6, which is assigned content-based address p6 by its local applications, issues the RA [6, p6]. That RA propagates through the network following the broadcast tree rooted at node 6. The propagation path is represented in the figure by thick black arrows. The table attached to (a) 1 2 3 4 5 6 p6 [6,p 6 ] [6,p 6 ] [6,p6] [6,p 6 ] [6,p 6 ] i p 6 p6 (b) 1 2 3 4 5 6 p2 (p2 ≺ p6) p6 [2,p 2 ] i p 4 p6 i p 2 p2 6 p6 Fig. 4. Receiver Advertisement Protocol (RA) node 4 in Figure 4a represents the routing table of node 4 after node 4 has processed the RA. After this first RA gets distributed, node 2 issues another RA carrying its content- based address p2, which happens to be covered by p6 (see Figure 4b). This second RA follows the broadcast tree rooted at node 2, however, using the ingress filtering rule, node 3 drops the RA. The result is that this second RA does not leave any trace at node 3, and is never forwarded along to node 5, as represented in Figure 4b by the thick dotted arrow. Figure 4b also shows the routing tables of node 4 and node 3 updated after the propagation of the secon