Evaluating DHT-Based Service Placement forStream-Based OverlaysPeter Pietzuch, Jeffrey Shneidman, Jonathan Ledlie,Matt Welsh, Margo Seltzer, and Mema RoussopoulosHarvard University, Cambridge MA 02138, USA,[email protected]. Stream-based overlay networks (SBONs) are one approachto implementing large-scale stream processing systems. A fundamentalconsideration in an SBON is that of service placement, which determinesthe physical location of in-network processing services or operators, insuch a way that network resources are used efficiently. Service placementconsists of two compone nts: node discovery, which selects a candidate setof nodes on which services might be placed, and node selection, whichchooses the particular node to host a service. By viewing the placementproblem as the composition of these two processes we can trade-off qual-ity and efficiency between them.We evaluate the appropriateness of using DHT routing paths for serviceplacement in an SBON, when aiming to minimize network usage. Forthis, we consider two DHT-based algorithms for node discovery, whichuse either the union or intersection of DHT routing paths in the SBON,and compare their performance to other techniques. We show that cur-rent DHT-based schemes are actually rather poor node discovery al-gorithms, whe n minimizing network utilization. An efficient DHT maynot traverse enough hops to obtain a sufficiently large candidate set forplacement. The union of DHT routes may result in a low-quality set ofdiscovered nodes that requires an expensive node selection algorithm. Fi-nally, the intersection of DHT routes relies on route convergence, whichprevents the placement of services with a large fan-in.1 IntroductionA marriage between the database and networking communities has produced aseries of interesting systems for continous queries, large-scale stream processing,and application-level multicast. These systems are examples of a generic class ofstream-based overlay networks (SBONs). SBON applications include real-timeprocessing of financial data (Aurora [1], Borealis [2]), Internet health monitor-ing (PIER [3]) and querying geographically diverse sensor networks (IrisNet [4]).SBONs pose two important challenges. First, a suitable choice of services,such as database operators, multicast points, or stream processors, must beprovided by the system to satisfy user requirements. Second, these services mustbe deployed efficiently in the network according to user queries. Thus far, mostexisting research into SBONs has focused on the former question, with muchless emphasis on efficient service placement. However, network-aware serviceplacement becomes a crucial factor that determines the scalability and impactof an SBON when deployed in a shared network. Therefore, a service placementalgorithm should be scalable and adaptive, and perform well based on severalcost metrics, such as network utilization and application latency.Service placement is actually composed of two mechanisms: node discoveryand node selection. Discovery is the process of identifying a set of nodes capableof hosting a service; we call this set of nodes the candidate set. Selection is the actof selecting a particular member of the candidate set to actually host the service.Traditionally, these two mechanisms have been intertwined, but by viewing themas separable processes, it is possible to gain greater insight into the performanceof existing systems and develop new approaches to placing services.In this paper, we investigate how well-suited current DHTs are to the taskof node discovery with respect to efficient network utilization. We evaluate twoDHT-based placement algorithms in comparison to non-DHT-based approaches,such as a globally optimal placement algorithm and a scheme based on springrelaxation [5]. Our analysis highlights the tight relationship between discoveryand placement. A bad discovery mechanism can sometimes yield a goo d place-ment, but at the cost of an expensive selec tion mechanism. For the topologies wehave considered, DHT-based schemes produce c andidate sets that are marginallydistinguishable from a random sampling. In particular, the union of DHT pathsfrom producers to consumers creates a large collection of nodes and se lecting thebest one does yield a good placement, but we would have done equally well byselecting nodes at random. When considering the intersection of routing paths,services with a large fan-in are always placed at consumer nodes.We conclude that current DHTs are not well-suited to this particular chal-lenge of optimizing network utilization. We suggest that one should turn towardalternate solutions, such as the relaxation-based approach analyzed here, or anew generation of DHTs that are designed to address the needs of SBONs.The outline of paper is as follows. Section 2 summarizes SBONs and describesthe service placeme nt problem. Section 3 introduces several node discovery andselection schemes that are then evaluated in Section 4. In Section 5 we reviewrelated work and Section 6 concludes.2 Stream-based Overlay NetworksAn SBON is an overlay network that streams data from one or more producers toone or more consumers, possibly via one or more operator services that performin-network processing. In an SBON, circuits interconnect multiple services. Acircuit is a tree that specifies the identities and relationships between services ina data stream and corresponds to a query. Services that are part of a circuit areconnected with circuit links.We model a circuit as a logical query statement that is then realized on phys-ical nodes. Some logical elements are constrained when the query is first stated.For example, the destination and data sources are specific physical nodes. Wecall these elements consumer and producer services, respectively, and considerthem pinned because their logical-to-physical mapping is fixed. Other services,e.g., a join operator, might be placed at any appropriate node in the network.We call these unassigned logical services unpinned. Logically, a join operator re-sides between two or more producers and one or more consumers, but its physicalmapping is unassigned, i.e., it is initially unplaced.2.1 Placement ProblemDetermining a placement for unpinned services is the fundamental placementproblem in an SBON. Some placements are better than others: each placementhas a cost and the quality of a placement is revealed by a cost function. Therefore,a solution to the placement