26-04-2012, 10:40 AM
Selfish Overlay Network Creation and Maintenance
Selfish Overlay Network Creation and Maintenance.pdf (Size: 455.74 KB / Downloads: 62)
Abstract
A foundational issue underlying many overlay network
applications ranging from routing to peer-to-peer file
sharing is that of the network formation, i.e., folding new arrivals
into an existing overlay, and re-wiring to cope with changing
network conditions. Previous work has considered the problem
from two perspectives: devising practical heuristics for the case of
cooperative peers, and performing game theoretic analysis for the
case of selfish peers. In our work, we unify the aforementioned
thrusts by defining and studying the Selfish Neighbor Selection
(SNS) game and its application to overlay routing. At the heart of
SNS stands the restriction that peers are allowed up to a certain
number of neighbors. This makes SNS substantially different
from existing network formation games that impose no bounds
on peer degrees. Having bounded degrees has important practical
consequences as it permits the creation of overlay structures that
require O(n) instead of O(n2) link monitoring overhead.
We show that a node’s “best response” wiring strategy amounts
to solving a k-median problem on asymmetric distance. Best
response wirings have substantial practical utility as they permit
selfish nodes to reap substantial performance benefits when
connecting to overlays of non-selfish nodes. A more intricate
consequence is that even non-selfish nodes can benefit from
the existence of some selfish nodes since the latter, via their
local optimizations, create a highly optimized backbone, upon
which even simple heuristic wirings yield good performance. To
capitalize on the above properties we design, build and deploy,
EGOIST, an SNS-inspired prototype overlay routing system for
PlanetLab. We demonstrate that EGOIST outperforms existing
heuristic overlays on a variety of performance metrics, including
delay, available bandwidth, and node utilization, while it remains
competitive with an optimal, but unscalable full-mesh overlay.
Index Terms—Overlay networks, overlay routing, selfish
neighbor selection, network formation.
I. INTRODUCTION
Motivation: Overlay networks [3] are used for a variety
of popular applications including routing [4], content distribution
[5], [6], peer-to-peer (P2P) file sharing [7], [8] and
streaming [9], [10], [11], data-center applications [12], and online
multi-player games [13]. A foundational issue underlying
many such overlay network applications is that of connectivity
management. Connectivity management is called upon when
having to wire a newcomer into the existing mesh of nodes
(bootstrapping), or when having to rewire the links between
overlay nodes to deal with churn and changing network conditions.
Connectivity management is particularly challenging
for overlay networks because overlays often consist of nodes
† Deutsche Telekom Laboratories and Technical University of Berlin, Germany.
‡ Telef´onica Research, Barcelona, Spain.
§ Computer Science dpt., Boston University, MA, USA.
G. Smaragdakis is supported by a Strategic Research grant from Deutsche
Telekom Labs. N. Laoutaris is supported by the NANODATACENTERS EU
project. A. Bestavros and J. Byers are supported by a number of NSF awards,
including CISE/CSR #0720604, ENG/EFRI #0735974, CISE/CNS #0952145,
#1012798, #1040800 and CISE/CCF #0820138. Parts of this work appeared in
the proceedings of the IEEE INFOCOM ’07 [1] and ACM CoNEXT ’08 [2].
that are distributed across multiple administrative domains, in
which auditing or enforcing global behavior can be difficult or
impossible. As such, these nodes may act selfishly and deviate
from the default protocol, by utilizing knowledge they have
about the network, to maximize the benefit they receive from
it. Selfish behavior has been reported in studies relating to
selfish (source) routing [14] and free riding [15] in P2P filesharing
networks. Selfish behavior also has many implications
for connectivity management. In particular, it creates additional
incentives for nodes to rewire, not only for operational
purposes (bootstrapping and substituting nodes that went offline),
but also for seizing opportunities to incrementally maximize
the local connection quality to the overlay. While much
attention has been paid to the harmful downsides of selfish
behavior in different settings [14], [16], [17], the impact of
adopting selfish connectivity management techniques in real
overlay networks has been an open problem [18].
Selfish Neighbor Selection: In a typical overlay network, a
node must select a fixed number (k) of immediate overlay
neighbors for routing traffic. Previous work has considered
this problem from two perspectives: (1) Devising practical
heuristics for specific applications in real deployments, such as
bootstrapping by choosing the k closest links (e.g., in terms of
TTL or IP prefix distance), or by choosing k random links in a
P2P file-sharing system. Notice here that DHTs like Chord [8]
solve a different problem. They route queries, not data traffic.
The latter is left to a separate subsystem [19] that typically
opens a direct connection to the target host. (2) Providing
abstractions of the underlying fundamental neighbor selection
problem that are analytically tractable, especially via gametheoretic
analysis [20], [21], [22]. To date, however, the bulk
of the work and main results in this area have centered on
strategic games where edges are undirected, access costs are
based on hop-counts, and nodes have potentially unbounded
degrees [20], [23], [21], [24], [22]. While this existing body of
work is extremely helpful for laying a theoretical foundation
and for building intuition, it is not clear how or whether the
guidance provided by this prior work generalizes to situations
of practical interest, in which underlying assumptions in these
prior studies are not satisfied. Another aspect not considered in
previous work is the consideration of settings in which some
or even most players do not play optimally – a setting which
we believe to be typical. Interesting questions along these
lines include an assessment of the advantage to a player from
employing an optimizing strategy, when most other players
do not, or more broadly, whether employing an optimizing
strategy by a relatively small number of players could be
enough to achieve global efficiency.
Paper Scope and Contributions: In this paper, we formulate
and answer such questions using a combination of modeling,
analysis, and extensive simulations using synthetic and real
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, APR 2011
2
datasets. Our starting point is the definition of a network
creation game that is better suited for settings of P2P and
overlay routing applications – settings that necessitate the
relaxation and/or modification of some of the central modeling
assumptions of prior work. In that regard, the central aspects
of our model are bounded degree, directed edges, non-uniform
preference vectors, and representative distance functions.
Our first technical contribution within this model is to
express a node’s “best response” wiring strategy as a k-median
problem on asymmetric distance [25], and use this observation
to obtain pure Nash equilibria through iterative best response
walks via local search. We then experimentally investigate the
properties of stable wirings using link weights obtained from
PlanetLab and the AS-level topologies maps. Here, we find
that selfish nodes can reap substantial performance benefits
when connecting to overlay networks composed of non-selfish
nodes. On the other hand, in overlays that are dominated by
selfish nodes, the resulting stable wirings are already so highly
optimized that even non-selfish newcomers can extract nearoptimal
performance through heuristic wiring strategies.
Motivated by the above positive results, we design, implement,
and deploy EGOIST, a prototype overlay routing
network built around best response wiring strategies. EGOIST
serves as a building block for the construction of efficient and
scalable overlay applications consisting of (potentially) selfish
nodes. We first demonstrate through real measurements on
PlanetLab that overlay routing atop EGOIST is significantly
more efficient than systems utilizing common heuristic neighbor
selection strategies under multiple performance metrics,
including delay, system load and available bandwidth. Second,
we demonstrate that the performance of EGOIST approaches
that of a (theoretically-optimal) full-mesh topology, while
achieving superior scalability, requiring link announcements
proportional to nk compared to n2 for a full mesh topology.
Our experimental results show that EGOIST remains highly
effective under significant churn and incurs minimal overhead.
Our evaluation includes among others, a case study in which
EGOIST is used for routing the traffic generated by an online
multi-player P2P game.
II. OVERLAY NETWORK MODEL AND DEFINITIONS
Previous work on overlay network creation [20], [23], [21],
[24], [22] has focused on physical telecommunication networks
and primarily the Internet. Overlay networks are substantially
different [26], [27] which prompts us to consider the
following overlay network model.
A. Overlay Network Model
We start by relaxing and modifying some of the central
modeling assumptions of previous work. In that regard, the
central aspects of our model are:
Bounded Degree: Most protocols used for implementing
overlay routing or content sharing impose hard constraints on
the maximum number of overlay neighbors. For example, in
popular versions of BitTorrent a client may select up to 50
nodes from a neighbors’ list provided by the Tracker of a
particular torrent file [28]. In overlay routing systems [29],
the number of immediate nodes has to be kept small so as
to reduce the monitoring and reporting overhead imposed by
the link-state routing protocol implemented at the overlay
layer. Hard constraints on the number of first hop neighbors
are also imposed in most P2P systems to address scalability
issues, up-link fragmentation, and CPU consumption due to
contention [30]. Motivated by these systems, we explicitly
model such hard constraints on node degrees. Notice that in
the prior studies cited above, node degrees were implicitly
bounded (as opposed to explicitly constrained) by virtue of
the trade-off between the additional cost of setting up more
links and the decreased communication distance achieved
through the addition of new links. We also note that some
of these earlier network creation games were proposed in the
context of physical communication networks [20], [23]. In
such networks, the cost of acquiring a link is instrumental
to the design and operation of a critical infrastructure. Such
concerns do not apply in the case of overlay networks such as
those we consider in this paper.
Directed Edges: Another important consideration in the settings
we envision for our work relates to link directionality.
Prior models have generally assumed bi-directional (undirected)
links [20], [23], [21], [24], [22]. This is an acceptable
assumption that fits naturally with the unbounded node degree
assumption for models that target physical telecommunication
networks because actual wire-line communication links are almost
exclusively bidirectional. In overlay settings we consider,
this assumption needs to be relaxed since the fact that node
v forwards traffic or requests to node u does not mean that
node u may also forward traffic or requests to v. Undirected
links are created by the establishment of two directed links.
Non-uniform preference vectors: In our model, we supply
each node with a vector that captures its local preference for
all other destinations. In overlay routing such preference may
capture the percentage of locally generated traffic that a node
routes to each destination, and then the aggregation of all
preference vectors would amount to a origin/destination traffic
matrix. In P2P overlays such preference may amount to speculations
from the local node about the quality of, or interest
in, the content held by other nodes. Other considerations may
also include subjective criteria such as the perceived capacity
of the node, its geographic location, or its availability profile.
B. Definitions
Let V = {v1, v2, . . . , vn} denote a set of nodes. Associated
with node vi is a preference vector pi =
{pi1, pi2, . . . , pii−1, pii+1, . . . , pin}, where pij ∈ [0, 1] denotes
the preference of vi for vj , i 6= j: Pn
j=1,j6=i pij =
1. Node vi establishes a wiring si = {vi1 , vi2 , . . . , viki
}
by creating links to ki other nodes (we will use the terms
link, wire, and edge interchangeably). Edges are directed
and weighted, thus e = (vi, vj) can only be crossed in the
direction from vi to vj , and has cost dij (dji 6= dij in the
general case). Let S = {s1, s2, . . . , sn} denote a global wiring
between the nodes of V and let dS(vi, vj) denote the cost of
a shortest directed path between vi and vj over this global
wiring; dS(vi, vj) = M ≫ n if there’s no directed path
connecting the two nodes. If the links are also annotated,
then M ≫ maxi,j dij . For the overlay networks discussed
here, the above definition of cost amounts to the incurred
end-to-end delay when performing shortest-path routing along
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, APR 2011
3
the overlay topology S, whose direct links have weights that
capture the delay of crossing the underlying IP layer path that
goes from the one end of the overlay link to the other. Let
Ci(S) denote the cost of vi under the global wiring S, defined
as the weighted (by preference) summation of its distances to
all other nodes, i.e., Ci(S) = Pn
j=1,j6=i pij · dS(vi, vj).
Definition 1: (The SNS Game) The selfish neighbor selection
game is defined by the tuple hV, {Si}, {Ci}i, where:
• V is the set of n players, which in this case are the nodes.
• {Si} is the set of strategies available to the individual
players. Si is the set of strategies available to vi. Strategies
correspond to wirings and, thus, player vi has