Evaluating DHT-Based Service Placement for

Stream-Based Overlays

Peter Pietzuch, Jeffrey Shneidman, Jonathan Ledlie,

Matt Welsh, Margo Seltzer, Mema Roussopoulos
Harvard University
[email protected]

Abstract tive, and should perform well based on several cost met-
Stream-based overlay networks (SBONs) are one approach to imple- rics, such as network utilization and application latency.
menting large-scale stream processing systems. A fundamental con- Service placement is actually composed of two mech-
sideration in an SBON is that of service placement, which determines anisms: node discovery and node selection. Discovery is
the physical location of in-network processing services or operators, in
such a way that network resources are used efficiently. Service place- the process of identifying a set of nodes capable of hosting
ment consists of two components: node discovery, which selects a can- a service; we call this set of nodes the candidate set. Selec-
didate set of nodes on which services might be placed, and node selec- tion is the act of selecting a particular member of the can-
tion, which chooses the particular node to host a service. By viewing the didate set to actually host the service. Traditionally, these
placement problem as the composition of these two processes we can
trade-off quality and efficiency between them. A bad discovery scheme two mechanisms have been intertwined, but by viewing
can yield a good placement, but at the cost of an expensive selection them as separable processes, it is possible to gain greater
mechanism. insight into the performance of existing systems and de-
Recent work on operator placement [3, 9] proposes to leverage rout- velop new approaches to placing services.
ing paths in a distributed hash table (DHT) to obtain a set of candidate
nodes for service placement. We evaluate the appropriateness of using In this paper, we investigate how well-suited current
DHT routing paths for service placement in an SBON, when aiming to DHTs are to the task of node discovery with respect to ef-
minimize network usage. For this, we consider two DHT-based algo- ficient network utilization. We evaluate two DHT-based
rithms for node discovery, which use either the union or intersection
of DHT routing paths in the SBON, and compare their performance to placement algorithms in comparison to non-DHT-based
other techniques. We show that current DHT-based schemes are actu- approaches, such as a globally optimal placement algo-
ally rather poor node discovery algorithms, when minimizing network rithm and a scheme based on spring relaxation [11]. Our
utilization. An efficient DHT may not traverse enough hops to obtain analysis highlights the tight relationship between discov-
a sufficiently large candidate set for placement. The union of DHT
routes may result in a low-quality set of discovered nodes that requires ery and placement. A bad discovery mechanism can some-
an expensive node selection algorithm. Finally, the intersection of DHT times yield a good placement, but at the cost of an expen-
routes relies on route convergence, which prevents the placement of sive selection mechanism. For the topologies we have con-
services with a large fan-in. sidered, DHT-based schemes produce candidate sets that
are marginally distinguishable from a random sampling. In
1 Introduction particular, the union of DHT paths from producers to con-
sumers creates a large collection of nodes and selecting the
A marriage between the database and networking com- best one does yield a good placement, but we would have
munities has produced a series of interesting systems done equally well by selecting nodes at random. When
for continous queries, large-scale stream processing, and considering the intersection of routing paths, services with
application-level multicast. These systems are exam- a large fan-in are always placed at consumer nodes.
ples of a generic class of stream-based overlay net- We conclude that current DHTs are not well-suited to
works (SBONs). SBON applications include real-time pro- this particular challenge of optimizing network utilization.
cessing of financial data streams (Aurora [2], Borealis [1]), We suggest that one should turn toward alternate solutions,
Internet health monitoring (PIER [9]) and querying geo- such as the relaxation-based approach analyzed here, or a
graphically diverse sensor networks (IrisNet [8]). new generation of DHTs that are designed to address the
SBONs pose two important challenges. First, a suitable needs of SBONs.
choice of services, such as database operators, multicast The outline of paper is as follows. Section 2 summa-
points, or stream processors, must be provided by the sys- rizes SBONs and describes the service placement problem.
tem to satisfy user requirements. Second, these services Section 3 introduces several node discovery and selection
must be deployed efficiently in the network according to schemes that are then evaluated in Section 4. In Section 5
user queries. Thus far, most existing research into SBONs we review related work and Section 6 concludes.
has focused on the former question, with much less em-
phasis on efficient service placement. However, network-
aware service placement becomes a crucial factor that de- 2 Stream-based Overlay Networks
termines the scalability and impact of an SBON when de- An SBON is an overlay network that streams data from one
ployed on a shared networking infrastructure. Therefore, a or more producers to one or more consumers, possibly via
service placement algorithm should be scalable and adap- one or more operator services that perform in-network pro-
1
cessing. In an SBON, circuits interconnect multiple ser- as a possible candidate set for service placement, and node
vices. A circuit is a tree that specifies the identities and selection chooses a suitable node for the actual placement.
relationships between services in a data stream and corre- An optimal node selection would consider all nodes in the
sponds to a query. Services that are part of a circuit are SBON, but requiring global knowledge is clearly not feasi-
connected with circuit links. ble for a scalable system. Even in a moderately-sized net-
We model a circuit as a logical query statement that is work, such as PlanetLab, up-to-date node characteristics
then realized on physical nodes. Some logical elements for 500 nodes cannot be gathered in a resource efficient
are constrained when the query is first stated. For exam- manner. Therefore, most placement algorithms use the re-
ple, the destination and data sources are specific physical sults of a node discovery scheme as the input for node se-
nodes. We call these elements consumer and producer ser- lection to cope with the complexity of the placement prob-
vices, respectively, and consider them pinned because their lem. Other placement algorithms, such as the Relaxation
logical-to-physical mapping is fixed. Other services, e.g., placement scheme described below, reverse the ordering of
a join operator, might be placed at any appropriate node in the two steps or coalesce them into one.
the network. We call these unassigned logical services un-
pinned. Logically, a join operator resides between two or 3.1 Node Discovery
more producers and one or more consumers, but its physi- The goal of node discovery is to generate a list of phys-
cal mapping is unassigned, i.e., it is initially unplaced. ical nodes on which an unpinned service can be placed.
2.1 Placement Problem This list is known as the candidate set. The quality of the
candidate set, in terms of the placement cost, is an im-
Determining a placement for unpinned services is the fun- portant consideration: if no nodes with a low placement
damental placement problem in an SBON. Some place- cost are part of the candidate set, a good placement cannot
ments are better than others: each placement has a cost and be found even with an optimal node selection algorithm.
the quality of a placement is revealed by a cost function. The size of the candidate and the distribution of placement
Therefore, a solution to the placement problem calculates costs for the included nodes determines the amount of flex-
a valid placement for all unplaced services that minimizes ibility that the node selection algorithm has when the best
the total incurred cost in the SBON. choice from the set cannot support the placement due to
Cost functions in an SBON can be categorized into two resource limitations. In this section, we describe several
classes. Minimizing application-specific costs, such as cir- possible candidate sets.
cuit delay and jitter, addresses the application’s desire for All. Setting the candidate set to be the entire overlay net-
quality of service in the SBON. Global cost functions, such work gives the node selection algorithm the most flexibil-
as network utilization and resource contention, attempt to ity to make a good placement. However, it is infeasible
capture the impact of a placement decision on other partic- to maintain global knowledge about all nodes in a large-
ipants of the SBON. scale distributed system and process a large set of candi-
In this paper, we concentrate on the global cost of utiliz- date nodes efficiently.
ing the network when streaming data through the SBON, Consumer. This algorithm returns the node hosting the
which is important in cooperative network environment, consumer service as the placement location, which mod-
such as PlanetLab. One way to capture overall network uti- els a centralized data warehouse system. While it trivially
lization is the bandwidth-latency (BW-Lat) product, which solves the placement problem, it makes no attempt to opti-
is the sum of the data rates consumed by circuit links mul- mize the placement decision.
tiplied by their communication latencies calculated over all Producer. Since data producers are pinned services in the
circuit links. The BW-Lat product captures network uti- circuit, one can select these nodes as the candidate set. Us-
lization as the amount of in-transit data in the network at a ing known producer nodes solves the discovery problem,
particular point in time. but can result in a small, badly-chosen candidate set.
The rationale behind this cost function is that the less Random. A candidate set of k random nodes can be dis-
data is put into the network by a placed circuit, the more covered through some mechanism. However, the average
network capacity is available to other circuits or applica- quality of this set may be worse than that of any other
tions. The BW-Lat cost function makes the assumption scheme that favors nodes with lower placement costs.
that high latency network links are more costly to use than DHT Routing Path. A natural way to build a candidate
low latency ones. Often high latency indicates network set is to route a message between pinned services through
congestion or long geographical distance that means higher an overlay network, such as a DHT. In a DHT setting, a
network operating costs. In both cases, the utilization of message will traverse dlogb (N )e hops in the worst case,
such links should be reduced. By factoring in the used where N is the number of nodes in the DHT and b is the
bandwidth of a circuit link into the BW-Lat metric, the cost numeric base used for hash keys during routing. There are
is proportional to the amount of network traffic used by a two obvious ways to generate a candidate set when a circuit
circuit. In other words, overall network utilization can be contains a consumer and multiple producers:
reduced more when good placement decisions are chosen
for circuits with a high data rate. 1. DHT Union takes the total set of overlay nodes in the
paths from producers to the consumer as the candidate set.
The service is then placed at one of these nodes.
3 Placement Algorithms 2. DHT Intersection takes the intersection of overlay
Many service placement algorithms can be viewed as con- nodes in the routing path from producers to the consumer.
sisting of two steps: node discovery and node selection. The service is then placed at one of these ordered nodes,
Node discovery identifies a subset of all nodes in the SBON such as the node closest to the producers.
2
 100
The goal of this paper is to explore the performance of
these two DHT routing schemes in comparison with the 90

Cumulative Distribution Function

other schemes and to determine their applicability for ser- 80
vice placement in an SBON. 70

3.2 Node Selection 60

For each unplaced service in a circuit, the node selection 50

algorithm must place the service on some node in the can- 40
didate set. In this paper, we consider three general selec- 30
tion algorithms. Other selection schemes are possible, but All / Opt
will produce placements no better than optimal selection. 20 All / Relaxation
Producer / Random
Of course, no selection algorithm is necessary when the 10 Consumer / -
candidate set contains only a single node. All / Random
0
Random selects a node out of the candidate set with uni- 0 500 1000 1500 2000
form probability. This is a trivial scheme to implement, BW-Lat product (in kb)
and may do well with a well-chosen candidate set. How- Figure 1: Non-DHT: CDF of the BW-Lat product on the
ever, it does not attempt to optimize the placement deci- PlanetLab topology.
sion.
Optimal chooses the best node from the candidate set with Node Topology
respect to some metric, such as network utilization or ap- Discovery Selection PlanetLab Transit-Stub
plication latency. In this paper, we consider the BW-Lat b=2 b=64 b=2 b=64
product from Section 2.1. If the candidate set is well- All Optimal 1.00 1.00
chosen or large, optimal may find a globally-optimal place- All Relax. 1.24 1.09
ment. However, an efficient implementation of optimal se- RandomSet(6) Optimal 1.26 1.36
lection is hard. An exhaustive search over all possibilities Producer Random 1.60 1.43
may result in a large amount of network probing and com- Consumer — 1.70 1.63
putational overhead for non-trivial circuits. All Random 1.96 1.84
Relaxation [11] places services using a spring-relaxation DHTUnion Optimal 1.13 1.13 1.14 1.18
model in an artificial coordinate space [7], in which dis- DHTUnion-NoProd Optimal 1.17 1.31 1.16 1.31
tance corresponds to latency between physical nodes in DHTUnion Random 1.60 1.63 1.56 1.52
the SBON. The placement coordinate is then mapped back DHTIntersec. — 1.68 1.67 1.63 1.63
DHTIntersec.-Split — 1.61 1.55 1.59 1.54
to physical network space to perform the actual service DHTIntersec.-Data — 2.82 1.96 3.31 2.25
placement. Prior work has shown that relaxation place-
ment performs well compared to other algorithms and sup-
ports scalable and dynamic cross-circuit optimization de- Table 1: 80th percentile of the BW-Lat product as a ratio
cision [11]. However, relaxation requires additional over- of the 80th percentile of All/Opt after placing 1000 circuits
head in calculating the latency space in a distributed fash- for two topologies with DHT bases 2 and 64.
ion and maintaining a mapping back to physical space.
circuits produce streams with a data rate of 2 kb/s each,
4 Evaluation which are then aggregated into a single 1 kb/s stream by
In this section we present our evaluation of DHT-based ser- the unpinned service.
vice placement compared to other, non-DHT-based place- Two separate DHT implementations were used for the
ment schemes. The goal is to determine the performance DHT-based placement schemes. We leverage a recent
of the DHTUnion and DHTIntersection algorithms when DHT implementation by crawling the OpenHash [10] rout-
applied to different topologies and DHT parameters. Our ing tables running on PlanetLab, which uses the Bam-
evaluation focuses on the efficiency of network utilization, boo [12] routing algorithm. OpenHash has a DHT key
as captured by the BW-Lat product. Throughout this sec- base of 2 and a leaf set size of 8. We performed latency
tion, we refer to a placement algorithm by its discovery measurement with Scriptroute [14] to fill in the missing
and selection schemes, e.g., All/Random. The Optimal se- Bamboo nodes in the all-pair pings data. We also imple-
lection scheme uses the BW-Lat product as its metric. mented our own Pastry-like DHT, called Pan, which al-
lowed us to vary the key base. A comparison of Pan and
4.1 Experimental Set-up Bamboo routing with key base 2 shows that the average
To evaluate the placement efficiency for a large num- routing hop count of Pan is within 2 % of Bamboo’s value.
ber of circuits, we implemented a discrete-event simula- Both DHTs used are proximity-aware because otherwise
tor that operates either on the PlanetLab [16] topology the DHT routing paths would be essentially random. The
with 186 nodes generated from all-pairs-ping measure- Pan implementation follows Pastry’s approach to achieve
ments [15], or an artificial 600-node transit-stub topol- proximity awareness by prefering DHT nodes for its rout-
ogy created by the GATech topology generator [17]. Af- ing tables that are close in terms of latency.
ter placing 1000 circuits each consisting of 4 pinned pro-
ducers, 1 unpinned service, and 1 pinned consumer, the 4.2 Network Utilization
simulator calculates the placement cost per circuit for each The experiment in Figure 1 depicts the efficiency of net-
of the placement algorithms. The four producers in the work utilization in terms of the amount of data in the
3
 100 100

90 90

80 80

70 70

60 60

50 50

40 40
All / Opt
30 30 All / Relaxation
All / Opt DHTUnion / Opt
All / Relaxation 20 DHTUnionNoProd / Opt
20 DHTUnion / Opt DHTUnion / Random
DHTUnion / Random 10 RandomSet(6) / Opt
10 RandomSet 6 / Opt Random
All / Random 0
0 500 1000 1500 2000 2500 3000 3500
0 200 400 600 800 1000 1200 1400
BW-Lat product (in kb)
BW-Lat product (in kb)
Figure 3: DHT-Union: CDF of the BW-Lat product with
Figure 2: DHTUnion: CDF of the BW-Lat product with Pan (base=64) on 600-node transit-stub topology.
Bamboo (base=2) on the PlanetLab topology.
network for five different, non-DHT placement schemes. ment node must be found through an expensive exhaustive
Each curve shows the BW-Lat distribution as a CDF after search.
placing 1000 circuits. As expected, All/Opt performs best The DHT contributes little to placement efficiency,
and All/Random worst. All/Relaxation is close to optimal, which is supported by the fact that RandomSet(6)/Opt
and outperforms the random selection of a producer (Pro- (1.26) performs similarly to DHTUnion/Opt (1.13). Ran-
ducer/Random) and consumer placement (Consumer/—). domSet uses a node size of six because this is close to
We will use these placement schemes as baselines for com- the average number of nodes in the DHTUnion candidate
parison to DHT-based placement. All our experimental re- set. A random choice of six nodes out of 186 is likely
sults for DHT-based service placement are summarized in to include a good placement candidate. This is especially
Table 1. The data is listed as the ratio of the 80th percentile the case for the PlanetLab network, which mainly inter-
of the BW-Lat product compared to the 80th percentile of links well-provisioned educational institutions [4]. In gen-
All/Opt after placing 1000 circuits using various placement eral, performing optimal node selection on large candidate
schemes. In the next two sections, we discuss the results sets is not desirable because of the probing and computa-
for two DHT-based node discovery schemes, DHTUnion tional overheads when placing complex circuits with mul-
and DHTIntersection, using several topologies and DHT tiple unpinned services. The DHTUnion/Random algo-
parameters. rithm (1.60) has a similar cost as Producer/Random (1.60)
and Consumer/— (1.70) because of the probability that ei-
4.2.1 DHTUnion ther the producer or consumer nodes are chosen randomly.
The DHTUnion scheme for node selection uses the DHT We study the effect of a more efficient DHT deploy-
routing paths from the producers to the consumer in a cir- ment on PlanetLab by simulating a DHT with a larger key
cuit to obtain a set of candidate nodes for service place- base of 64. For this DHT, the average routing path length
ment. The size and the quality of the set with respect to the drops to 1.6 hops. Table 1 shows that the performance
placement cost function, will depend on the network topol- of DHTUnion/Opt is still good (1.13) when compared to
ogy and the specifics of the particular DHT, such as its net- All/Opt. Although the DHT routing paths are shorter due
work awareness, key base and leaf set size. Most DHTs to the larger key base, the candidate set now becomes dom-
are optimized for efficient key retrieval, which means that inated by the 5 nodes hosting either pinned producers or
the number of routing hops is kept low by choosing a large consumers. We verify this claim with the DHTUnion-
key base. However, this reduces the size of the candidate NoProd scheme: when the producer nodes are removed
set for node selection when using a DHT, potentially miss- from the candidate set in DHTUnion-NoProd/Opt place-
ing good placement nodes from the set. In terms of quality, ment, the placement cost increases to 1.31. This means
the choice of the routing path by the DHT will determine that the in-network DHT routing path is not long enough
the suitability of the candidate set for service placement. to contribute a good placement node.
PlanetLab Topology. In Figure 2, we plot the distri- Transit-Stub Topology. The problem of a small, low-
bution of the BW-Lat product for three variations of the quality candidate set, as returned by DHTUnion, is even
DHTUnion scheme on the PlanetLab topology using the more pronounced in larger topologies. In Figure 3,
Bamboo DHT. For such a small topology, many nodes are we consider an efficient DHT deployment with a key
included in the candidate set because the Bamboo deploy- base of 64 deployed on a 600-node transit-stub topol-
ment on PlanetLab has a large average routing path length ogy. The average DHT path length here is 1.89 hops.
of 3.18 hops due to its binary key base. Therefore, the fig- In this topology, DHTUnion/Opt (1.18) performs worse
ure shows that DHTUnion/Opt placement performs well than All/Relaxation (1.09). Removing the producer
compared to All/Opt: the candidate set covers a significant nodes (DHTUnion-NoProd/Opt) reduces the efficiency to
fraction of all nodes and therefore is likely to include at 1.31, resulting in only a small gain when compared to
least one good placement node. However, this good place- RandomSet(6)/Opt (1.36).
4
 3000 Consumer/— reveal that DHTIntersection performs only
2800
marginally better than consumer selection. In most cases
the intersection of the four routing paths from the produc-
2600 ers to the consumer contains only the node hosting the
BW-Lat product (in ms)

consumer. This means that DHTIntersection is not a good

2400
scheme for unpinned services with a large fan-in. Since the
2200 candidate set returned by DHTIntersection contains a sin-
gle node in most cases, varying the node selection scheme
2000 is unnecessary.
RandomSet k / Opt
1800
The DHTIntersection-Split scheme recognizes this lack
All/Relaxation
of convergence of multiple routes by assuming that an
1600
All/Opt
unpinned service can be split into sub-services. These
sub-services can then be placed independently. A sub-
1400
0 10 20 30 40 50 60 service is created at the intersection between any two rout-
RandomSet size (in nodes) ing paths from producers to consumer. This is similar to
the setup of multicast trees in DHT-based systems, such as
Figure 4: RandomSet/Opt: BW-Lat product with Scribe [5], where a multicast node is created at the node
Pan (base=64) on 600-node transit-stub topology. joining the path from a new subscriber to the root of the
100
multicast tree. The graph shows that splitting services im-
90 proves the fraction of cases, in which services are placed
80 in-network. However, it does not reach the performance of
All/Relaxation, which optimizes for the BW-Lat product.
70
Moreover, it is not applicable if services cannot be decom-
60 posed into sub-services.
50 Application-level multicast schemes based on DHTs of-
40
ten send data along DHT routing hops. This has the ad-
All / Opt vantage that the data flows benefit from the resilience and
30 All / Relaxation load-balancing properties of the DHT but it also incurs the
DHTIntersection / -
20 DHTIntersectionSplit / - penalty of more network traffic in the system. To evaluate
DHTIntersectionData / - this effect, the final placement scheme is DHTIntersection-
10 Consumer / -
All / Random Data, as shown in Figure 5, which in addition to using
0 the DHT for service placement, also routes the data itself
0 500 1000 1500 2000
BW-Lat product (in kb )
through the DHT. The last row in Table 1 suggests that
the penalty is directly related to the key base, which de-
Figure 5: DHT-Intersection: CDF of the BW-Lat product termines the number of hops in the routing path. For the
with Bamboo (base=2) on the PlanetLab topology. Bamboo DHT on PlanetLab, the penalty of routing data
through the DHT compared to All/Opt placement is almost
An obvious way to enlarge the candidate set is to con- a factor of 3. We suggest that many applications would
sider the round-trip DHT routing path. However, increas- benefit from including their own resilience mechanisms at
ing the size of candidate set without picking good nodes the application-level without paying the price for using the
does not lead to efficient service placement in a large topol- DHT for data routing.
ogy. The experiment in Figure 4 with the same 600-node
transit-stub topology investigates the minimum size of a 4.3 Summary
randomly chosen candidate set (RandomSet(k)) that is nec- Our experiments suggest that DHTs are less efficient than
essary to perform a good node selection with an exhaus- non-DHT alternatives, such as Relaxation placement, for
tive search (Opt). Even when the candidate set includes service placement in SBONs. DHTs are designed for effi-
10 % of all nodes, it does not achieve the performance of cient key lookup, but this yields small candidate set sizes
All/Relaxation placement. Note that RandomSet performs for service placement. Using a small key base increases
worse on the transit-stub topology than before because this the number of routing hops thus helping node discovery
network is not as homogeneous as PlanetLab. but also reduces the efficiency of key lookup for other ap-
plications sharing the DHT. A large key base, such as in
4.2.2 DHTIntersection one-hop routing, may not return enough useful nodes for
The DHTIntersection discovery scheme considers the service placement.
nodes in the intersection of all DHT routing paths between Another drawback is the low quality of the obtained
the producers and the consumer as the candidate set. It re- candidate set from the DHT, which makes it necessary to
lies on the route convergence property of DHT routing [5], perform a costly exhaustive search through all placement
which states that routing paths to the same destination are possibilities. Fundamentally, DHTs are not designed to
likely to converge. A service is then placed on the farthest optimize stream-based processing in the overlay network.
node along the path that is shared by all other routing paths. A topology-aware DHT uses only latency to optimize its
In this case, node discovery is equivalent to selection, so overlay routing paths. Since DHTs are connection-less by
the selection scheme is represented by —. nature and thus unaware of the data streams in the SBON,
In Figure 5, we evaluate three types of DHTIntersec- they cannot easily optimize their routing tables for efficient
tion. The overlapping curves of DHTIntersection/— and service placement. Algorithms, such as Relaxation place-
5
 Node Intersection tends to reduce to Consumer placement, re-
Discovery Selection SBON Examples sulting in highly restricted and poor placement. If services
All Random PIER[9] can be split, we found that DHT Intersection still does not
All Relaxation Hourglass[13] perform as well as a dedicated mechanism like Relaxation.
All Other (Human Decision) GATES[6] These results suggest a number of areas for further re-
Consumer — Typ. Warehouse search. First, it remains an open question of whether it is
Con. & Prod. Varies (Random, Heuristic) Typ. CQ System possible to construct a DHT that is sufficiently network-
DHTUnion Greedy Heuristic on Opt Borealis, SAND[1, 3] aware such that it could be used to easily construct a good
DHTIntersec. — Scribe[5], Bayeux[18] candidate set for node placement. How might we construct
such a DHT? What does it mean for a DHT to be dynam-
Table 2: SBONs classified by their placement techniques. ically aware of network conditions? Second, should we
declare that DHTs are not the correct abstraction on top
ment [11], designed specifically to minimize the amount of which to construct service placement algorithms? What
of traffic in the SBON do not suffer from the same restric- alternative structures are possible? Third, is it necessary to
tions. globally optimize streaming applications? Do we believe
The intersection of DHT routing paths avoids the issue that there will be sufficiently large amounts of streaming
of a large, low-quality candidate set but has the problem traffic to warrant building a system that does cross-circuit
that routing paths between pinned services may not con- optimization instead of just local optimization? Answer-
verge. This is especially the case for services with a large ing these questions is crucial for successful deployment of
number of incoming circuit links. Splitting services into stream-based applications.
sub-services addresses this problem but is not applicable
in general. Routing data along DHT hops, as done by cer- References
tain application-level multicast schemes, carries a large ef- [1] D. Abadi, Y. Ahmad, H. Balakrishnan, et al. The Design of the
Borealis Stream Processing Engine. Technical Report CS-04-08,
ficiency penalty. Brown University, July 2004.
[2] D. Abadi, D. Carney, U. Cetintemel, et al. Aurora: A New Model
5 Related Work and Architecture for Data Stream Management. VLDB, Aug.
2003.
We suspect that the optimization of service placement de- [3] Y. Ahmad and U. Çetintemel. Network-Aware Query Processing
cision in SBONs will be a growing research area, as can be for Stream-based Applications. In VLDB, Aug. 2004.
seen from the wide-range of related work. [4] S. Banerjee, T. G. Griffin, and M. Pias. The Interdomain Connec-
tivity of PlanetLab Nodes. In Passive and Active Measurement
New continuous query (CQ) work breathes life into Workshop, Antibes Juan-les-Pins, France, Apr. 2004.
questions that arose in distributed database optimization. [5] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron.
Most related to our work is SAND [3] in the context of the Scribe: A Large-scale and Decentralized Application-level Multi-
cast Infrastructure. JSAC, 20(8), Oct. 2002.
stream-processing system Borealis [1]. In our terminology, [6] L. Chen, K. Reddy, and G. Agrawal. GATES: A Grid-Based Mid-
they use DHTUnion to pick the candidate set, and a greedy dleware for Processing Distributed Data Streams. In HPDC-13,
heuristic on optimal for node selection. Their scheme can Honolulu, Hawaii, June 2004.
do no better than a DHTUnion/Opt placement. [7] F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: A De-
centralized Network Coordinate System. In Proc. of the ACM
The location of operators and corresponding relational SIGCOMM’04 Conference, Portland, OR, Aug. 2004.
tables in PIER [9], a distributed database system built on [8] P. B. Gibbons, B. Karp, Y. Ke, S. Nath, and S. Seshan. IrisNet:
top of a DHT, is determined through random hash selec- An Architecture for a World-Wide Sensor Web. IEEE Pervasive
tion from all overlay nodes and explicitly recognizes the Computing, 2(4), Oct. 2003.
[9] R. Huebsch, J. M. Hellerstein, N. Lanham, et al. Querying the
possible inefficiency in such a service placement scheme, Internet with PIER. In VLDB), Berlin, Germany, Sept. 2003.
and is essentialy an All/Random placement. [10] B. Karp, S. Ratnasamy, S. Rhea, and S. Shenker. Spurring Adop-
Overlay routing and application level multicast systems tion of DHTs with OpenHash, a Public DHT Service. In Proc. of
IPTPS’04, San Diego, CA, Feb. 2004.
consider where to place multicast services to best optimize [11] P. Pietzuch, J. Shneidman, M. Welsh, M. Seltzer, and M. Rous-
an expanding array of metrics. For example, Scribe [5] sopoulos. Path Optimization in Stream-Based Overlay Networks.
uses a DHT to produce a multicast tree to connect pub- Technical Report TR-26-04, Harvard University, October 2004.
lishers to subscribers. In our terminology, Scribe uses [12] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling
Churn in a DHT. In USENIX ’04, Boston, MA, June 2004.
DHTIntersection-Split as its discovery mechanism and a [13] J. Shneidman, P. Pietzuch, J. Ledlie, M. Roussopoulos, M. Seltzer,
“farthest common ancestor” heuristic as its selection mech- and M. Welsh. Hourglass: An Infrastructure for Connecting Sen-
anism. sor Networks and Applications. Technical Report TR-21-04, Har-
vard University, Sept. 2004.
Grid users are recognizing the need to use in-network [14] N. Spring, D. Wetherall, and T. Anderson. Scriptroute: A Public
services to help process massive data streams. For in- Internet Measurement Facility. In USITS’02, Mar. 2003.
stance, GATES [6] provides a way of introducing process- [15] J. Stribling. All-Pairs-Pings for PlanetLab. http://www.pdos.lcs.-
ing services but requires these services be pre-placed by a mit.edu/˜strib/pl app/, Sept. 2004.
[16] The Planetlab Consortium. http://www.planet-lab.org, 2004.
system administrator. [17] E. W. Zegura, K. L. Calvert, and S. Bhattacharjee. How to Model
an Internetwork. In Proc of IEEE Infocom’96, volume 2, pages
6 Conclusions 594–602, San Francisco, CA, Mar. 1996.
[18] S. Q. Zhuang, B. Y. Zhao, A. D. Joseph, R. H. Katz, and J. Kubi-
In this paper, we have shown that current DHTs do not atowicz. Bayeux: An Architecture for Scalable and Fault-tolerant
produce a particularly good candidate set of nodes for ser- Wide-Area Data Dissemination. In NOSSDAV, June 2002.
vice placement. DHT Union does not provide significant
discovery value beyond that of selecting a random set of
nodes from the overlay. If services cannot be split, DHT
6