Forwarding in a Content-Based NetworkAntonio CarzanigaDepartment of Computer ScienceUniversity of ColoradoBoulder, Colorado 80309-0430 [email protected] L. WolfDepartment of Computer ScienceUniversity of ColoradoBoulder, Colorado 80309-0430 [email protected] paper presents an algorithm for content-based forward-ing, an essential function in content-based networking. Un-like in traditional address-based unicast or multicast net-works, where messages are given explicit destination ad-dresses, the movement of messages through a content-basednetwork is driven by predicates applied to the content of themessages. Forwarding in such a network amounts to eval-uating the predicates stored in a router’s forwarding tablein order to decide to which neighbor routers the messageshould be sent. We are interested in finding a forwardingalgorithm that can make this decision as quickly as possiblein situations where there are numerous, complex predicatesand high volumes of messages. We present such an algorithmand give the results of studies evaluating its performance.Categories and Subject DescriptorsC.2.2 [Computer-Communication Networks]: Net-work Protocols—Routing protocols ; C.2.1 [Computer-Communication Networks]: Network Architectureand Design—Distributed networks; C.2.4 [Computer-Communication Networks]: Distributed Systems—Dis-tributed applicationsGeneral TermsAlgorithms, Measurement, Performance, ExperimentationKeywordsContent-based network, forwarding, matching, overlay, pub-lish/subscribe1. INTRODUCTIONContent-based communication is a novel communicationservice whereby the flow of messages from senders to re-ceivers is driven by the content of the messages, rather thanby explicit addresses assigned by senders and attached to thePermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SIGCOMM’03, August 25–29, 2003, Karlsruhe, Germany.Copyright 2003 ACM 1-58113-735-4/03/0008 ...$5.00.messages [9]. Using a content-based communication service,receivers declare their interests by means of selection pred-icates, while senders simply publish messages. The serviceconsists of delivering to any and all receivers each messagethat matches the selection predicates declared by those re-ceivers.In a content-based service model, message content isstructured as a set of attribute/value pairs, and a selectionpredicate is a logical disjunction of conjunctions of elemen-tary constraints over the values of individual attributes. Forexample, 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”]An ideal application for a content-based communicationservice is a publish/subscribe event notification service [4, 5,7], where a selection predicate represents a subscription anda message represents a published event. Other applicationsthat can directly benefit from a content-based communi-cation service include 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 through a content-based net-work. A content-based network is an overlay network whoserouters perform specialized routing and forwarding func-tions. Routing in a content-based network amounts to syn-thesizing distribution paths from a combination of the topo-logical features of the overlay network and the selectionpredicates declared by applications. The routing functioncompiles two forwarding tables: the first contains topolog-ical constraints, and is conceptually identical to a forward-ing table of an IP router, while the second contains selectionpredicates, and is the result of combining the selection predi-cates declared by applications. The forwarding function de-termines the set of next-hop destinations by applying theappropriate topological constraints found in the first table,and by matching the content of the message against the setof selection predicates found in the second table.Our concern in this paper is with the design of a fast for-warding function for a content-based network. In particular,we focus on the predicate-matching algorithm, since this isthe novel aspect of the forwarding function in a content-based network. Notice that the properties of the forwardingtable used by this algorithm (the second table mentioned163above) result directly from the characteristics of end-userapplications, as opposed to characteristics of the network it-self. We seek an algorithm that can scale well in situationswhere there are numerous, complex predicates and high vol-umes of messages generated by end-user applications.In this paper we present a forwarding algorithm and givethe results of studies evaluating its performance. Becauseour goal is fast forwarding, our primary metric for successis how well we minimize, for a given message, the time ittakes to identify the set of neighbors to which the messageshould be forwarded. Intuitively, the main scale factor ofthe algorithm is the total number of constraints resident inthe forwarding table.Our evaluation shows that the algorithm has good abso-lute performance under heavy loads and in a variety of net-work configurations, including the extreme case of a single,centralized router. It also shows that the algorithm scalessublinearly in the number of conjunctions, with almost nodegradation of throughput, in the context of a network ofrouters with a fixed number of neighbor nodes. For exam-ple, a software implementation of our algorithm, runningon a 950Mhz computer, is able to forward a 10-attributemessage in 3 milliseconds in a situation where there are 20predicates (i.e., neighbors) consisting of 250000 conjunctionsformed from 5 million individual constraints over an alpha-bet of 1000 attributes. In this experiment, the message wentto 18 of the 20 neighbors, but we observed in other exper-iments that the
View Full Document
Unlocking...