Transcript slideshow - Nikolaos Laoutaris

Northeastern University, 10 Dec. 2007 – Boston, MA
On the Many Facets of Neighbor Selection
for Overlay Networks
Nikolaos Laoutaris
Researcher (aka “Investigador”)
Telefonica Research, Barcelona, Spain
Email: [email protected]
Homepage: http://research.tid.es/nikos/
Joint work with:
 Georgios Smaragdakis
 Azer Bestavros
 John Byers
 Shang-Hua Teng
 Ravi Sundaram
 Rajmohan Rajaraman
 Mema Roussopoulos
 Pietro Michiardi
 Damiano Carra
Documented in:
-- Swarming on Optimized Graphs for N-way Broadcast
IEEE INFOCOM 2008
-- Implications of Selfish Neighbor Selection in Overlay Networks
IEEE INFOCOM 2007
-- A Bounded-Degree Network Formation Game
arXiv-CoRR cs.GT/0701071
-- EGOIST: Overlay Routing using Selfish Neighbor Selection
BUCS-TR-2007-013, Oct. 2007
-- Uplink Allocation Beyond Choke/Unchoke or Why Divide Does Not Always Conquer Best
submitted, Nov. 2007
Neighbors are important
1. net admin
2. business development
4. London Internet Exchange
3. lawyers
in other situations neighbors
can be changed … but it has
5. net engineer
a cost …

Telco’s can
change
neighbors
just find a way to get along and move on … it only takes 1-2
years
3/33
Patching the Internet using
Overlay Networks

for routing (RON, Detour, QRON)

for file sharing (Napset, Gnutella, KaZaA, BitTorrent)

for Internet telephony (Skype)

for IP TV (Joost)

Online Games
4/33
Neighbors can be switched
fast in an overlay net
O2
An overlay network:
 nodes & (logical) overlay links
 weight ~ physical dist.
 messages routed on the overlay
Neighbor selection: choose
overlay nodes for the
establishment of direct links
Goal: use neighbor selection
 handle network dynamics
 handle participation dynamics
O1
overlay
link
overlay
node
O3
R3
R1
R2
R4
physical
link
physical node (e.g., end-systems,
router or AS) 5/33
5 case studies
1. Overlay routing with selfish nodes
2. Unstructured P2P with selfish nodes
3. BitTorrent-like (swarming) P2P
4. All-to-all broadcasting of bulk data
5. Network-initiated redirection of P2P
6/33
A design plane for neighbor selection
scope of
communication
available
information
routing
routing
1-to-1
P2P
broadcasting
1-to-many
many-to-many
no information
bootstrapping
no routing
Flooding/BitTorrent
scope of utility
decision maker
cooperative nodes
the node
local
network wide
pings
link-state protocol
imperfect
perfect
Chord
Shortest-path
selfish nodes
the network
7/33
Case study 1: Overlay Routing
8/33
Neighbor selection for Overlay Routing
scope of
communication
available
information
routing
scope of utility
decision maker
routing
no information
no routing
cooperative nodes
the node
P2P
broadcasting
local
network wide
imperfect
perfect
selfish nodes
the network
9/33
A selfish node in a (n choose k) situation
vi wants to minimize:
Ci ( S ) 
p
v j Vi
ij
vi’s preference for vj
 d S (vi , v j )
over all siSi
pick k
neighbors
u
vi
individual wiring
global wiring
w
si={u,w}
S=S-i+{si}
residual wiring
G-i=(V-i,S-i)
vi’s residual network
vi’s residual wiring
10/33
How do you select neighbors optimally?

How is the optimal comparing with simple heuristics?


k-Random does not use any link information
2
w
k-Closest uses only local information
wrong
right

cheap
Under uniform overlay link1weights (hop-count
distance):


3
4
Optimal selection  asymmetric k-median
on the reversed distance
expensive
function of the residual graph G-i :
u
since these
w,u
can
be
cost
the
same
Consequently:
obtained from
d12<d13<d14

Best-response is NP-hard
2-median on

Const. factor approx for metric k-median don’t apply here
reversed distances


O(1)-approx with O(logn) blow-up in # medians (Lin and Vitter,’92)
Most likely the best we can do (Archer, 2000)
11/33
Existence of pure Nash equilibria and performance
uniform game  uniform preference, link budget (k), and link weights (1)

Theorem: All (n,k)-uniform games have pure Nash equilibria.

Theorem: There exist non-uniform games with no pure Nash equilibria.

there exist asymmetric non-uniform games that have no pure Nash (we “implemented” on a graph the
cost-structure of the matching-pennies game)

there exists an equivalent symmetric non-uniform game for each one of them

Theorem: Strong connectivity in O(n2) turns from any initial state.

Lemma: In any stable graph for the (n, k)-uniform game, the cost of any node is at
most 2 + 1/k + o(1) times the cost of any other node.

Social Cost(ourEQ) < 2 * Social Cost(SO)
Lemma: The diameter of any stable graph for an (n, k)-uniform game is
O(sqrt(n logkn)). [don’t know if it is tight]

Theorem: For any k ≥ 2, no Abelian Cayley graph with degree k and n nodes is stable,
for n ≥ c2k, for a suitably large constant c.
12/33
check it out live at: http://csr.bu.edu/sns/
EGOIST:
n3
n2
n4
Connecting a newcomer node vi

bootstrap

listen to overlay link-state
protocol to get dG-i

get dij’s through active
(ping) or passive measurmnt
(Pyxida,pathChirp)

wire according to (hybrid)
Best-Response

monitor and announce your
links
Our prototype overlay
routing system for
n1
n5
n7 n8
n9
n6
50 nodes around the world using the infrastructure of
n10
n11
13/33
EGOIST: Features

supported metrics:




supported wiring strategies:






delay (active/passive monitoring with ping/Pyxida)
available bandwidth (monitoring with pathChirp)
node load (monitoring with loadavg)
k-Random
k-Closest
k-Regular
Best-Response (delay and AvailBw formulations)
Hybrid Best-Response
BR-computation based on


the full residual graph
or just samples of it
14/33
Case study 2: Unstructured P2P
(aka Gnutella or 1st generation P2P)
15/33
The 1-slide intro to Gnutella

random list of neighbors from bootstrap server

flooding of queries

first node that “hits” sends back the file
16/33
Neighbor selection for unstructured P2P
scope of
communication
available
information
routing
scope of utility
decision maker
routing
no information
no routing
P2P
broadcasting
local
network wide
imperfect
perfect
flooding
cooperative nodes
the node
selfish nodes
the network
17/33
Current Gnutella
in Gnutella neighbors are picked
randomly or with local info
Bootstrap
1
Server
if the TTL of scoped flooding is 2
2
3
4
randomly
this wiring will give you access to 4 nodes
18/33
Gnutella with selfish nodes
IDEA: we select neighbors to maximize the
foothold of our scoped flooding
Bootstrap
Server
4
1
3
6
5
2
for each candidate we compute the number
of distinct nodes we can reach with TTL 2
connect to those candidates that maximize the overall sum of uniques
this wiring gives us access to 6 nodes
19/33
Case study 3: BitMax
(our hacked BitTorrent; 2nd generation P2P)
20/33
The 1-slide intro to BitTorrent

file broken to 256Kbyte chunks

a tracker knows all the peers of a torrent and the seed


new leacher peers get 40 random neighbors



neighbors know each other’s chunks
help each other with missing ones
chunk selection: the Least Replicated First (LRF) algorithm


1 torrent  1 file
request a missing chunk that is less represented
uplink allocation: the choke/unchoke algorithm



unchoke
k=4 neighbors assigning equal share of the uplink capacity
… the ones that have been uploading fastest to you
rate-based tit-for-tat
21/33
WHY 4 ???

ask its inventor Bram Cohen


http://stanford-online.stanford.edu/courses/ee380/050216-ee380-100.asx
… anyway, people



he’ll give an amusing answer:
say “4 is good” …
measurement studies: “90+% uplink utilization”
theory works: “some contact process was asymptotically optimal under a
ton of simplifications”
our simulations were showing otherwise … especially under real
constraints:


and we fixed most of our bugs
and verified against a second simulator
22/33
Since when tit-for-tat became socially OPT?
seed

the 3 node example



1 seed, 2 leachers, 1 chunk of size 1, all upload rates=1
splitting gets the chunk delivered after 2 time slots
focusing and then switching achieves the same


… but the first leacher can start contributing earlier
leachers
A
0.5
0.5
B
A
1
Lesson learned : you must saturate your uplink


B
but partition it minimally
allocated shares don’t have to be equal
23/33
Using a fractional knapsack to get rid of the magic 4

a knapsack with capacity u(v)

“item” vi \in V(v) with



“weight” u(v,vi)
“value” U(vi,h)
the value of unchoking vi for a horizon h
24/33
simulator and scripts
(will be)
available online
us
them
Here:

median download time is halved

worse case reduced by a fact. of 3
25/33
Case study 4: N-way broadcast
26/33
A native n2 application

each node has a large file




n independent overlays is a BAD idea




upload it to all others
download their respective ones
bulk synchronous parallel processing
race conditions
redundant re-monitoring
should use one optimized overlay for all exchanges
random neighborhoods is a BAD idea


scale is small/mid
should use more global info
27/33
Neighbor selection for N-way broadcast
scope of
communication
available
information
routing
routing
no information
no routing
P2P
broadcasting
local
network wide
imperfect
perfect
swarming
scope of utility
decision maker
cooperative nodes
the node
selfish nodes
the network
28/33
Neighbor selection & broadcasting

W=k= 4, 6, 8…

node vi and a flow network G-i


vi selects neighbor set V(vi) to maximize its broadcast
bandwidth (its minimum maxflow to any vj \in G-i)
cooperative node:


 we did this before BitMax 
forwards own and in-transit chunks indiscriminately
selfish node:


forwards its own nodes preferentially
we have ways to detect and punish
29/33
Case study 5: P2P redirection at ISP
peering points
(only 2 slides left!)
30/33
P2P traffic can go through unwanted links
SPRINT/LEVEL3
Transit ISP
P2P
Transit ($$$)
Backbone
Other ISP
Backbone
Telefonica Backbone
Peering (zero cost)
Access ISPs
Tel
Brasil
Tel
Spain
P2P
Access
ISP
P2P
31
The “box” (codename Athena project)

intercept BitTorrent’s signalling

re-write the neighbor lists returned by the tracker

can we both


lower the cost for the ISP
And improve the download times
?
32/33
Thank you
Q ?
33/33
k
t’
…
Nash equilibria
utopian
…
… and performance
t
uniform game  uniform preference,
(k), and link weights (1)
… link budget
…
• t=n-nk,h of pure
Existence
• t’=t+1 mod k

unstable for large n
Theorem: All (n,k)-uniform games have pure Nash equilibria.
1
2
3
4
5
k-1
h Theorem:hThere exist non-uniform games with no pure Nash equilibria.



there exist asymmetric non-uniform games that have no pure Nash (we “implemented” on a graph the
6 of the
7 matching-pennies
8
9game)
cost-structure
there exists an equivalent
… symmetric…non-uniform game for each one of them

Theorem: Strong connectivity in O(n2) turns from any initial state.

disconnection
Lemma: In any stable
graph for the (n, k)-uniform
game, the cost of any node is at
k
most 2 + 1/k + o(1) times the cost of any other node.

Social Cost(ourEQ) < 2 *
Cost(SO)
. Social
.… .
. .….
…
…
…
…
Lemma: The diameter of any stable graph for an (n, k)-uniform game is
O(sqrt(n logkn)). [don’t know if it is tight] utopian+1
disconnection
k

getskeither k roots
or the k hubs
gets t’ roots
and k-t’ heaviest hubs
Theorem: For any k ≥ 2, no Abelian Cayley graph with degree k and n nodes is stable,
for n ≥ c2k, for a suitably large constant c.
34/33