Transcript timeout-free mobile DHT

Mobile DHTs
Hung-Chang Hsiao
蕭宏章
Computer & Communication Research Center
National Tsing-Hua University
The Talk is About and is not About…

DHT is a type of peer-to-peer (P2P) systems



Mobile DHT = DHT + mobile devices


P2P in mass-markets: unstructured p2p, e.g., Gnutella, KaZaA,
Bittorrent and Skype
DHT probably is not implemented by mass-market systems
Practical issues: impact of mobility churn, handle mobility
churn, …
This talk is NOT about how to do file swapping in the
Internet
H.C. Hsiao, CCRC/NTHU
2/55
System Model in This Talk

Is a P2P model like Gnutella, eDonkey, Bittorrent,
etc.
Kuro

Is Not a P2P such as Akamai, a content delivery
network
H.C. Hsiao, CCRC/NTHU
3/55
Outline

P2P & DHT
15 min

Mobile DHT

Related studies
35 min
5 min

Summary
H.C. Hsiao, CCRC/NTHU
5 min
4/55
Peer-to-Peer (P2P) Overlay Network
End systems
one link
(end-to-end comm.)
a TCP thru the Internet
Internet
H.C. Hsiao, CCRC/NTHU
5/55
P2P Overlay
•Focus at application layer
•Multihop routing with
end nodes as routers
Internet
H.C. Hsiao, CCRC/NTHU
6/55
Characteristics of P2P

Multiple peers participating in the network



The number of peers is typically large
Every peer owns some resources and pays its
participation by providing access to its resources
No distinguished roles (IETF/IRTF, June 2004)




The number of roles is small
Autonomous, self-control, ad hoc participation
Dynamic (e.g., come and go freely)
Rely very little on the underlay infrastructure
 Do most things on their own
H.C. Hsiao, CCRC/NTHU
7/55
Hash Tables: Review

Given a hash key, return an entry corresponding
to that key
0
1
2
1063

Op.: lookup, insert, delete
H.C. Hsiao, CCRC/NTHU
8/55
Distributed Hash Tables (DHT)
0
1
2
1063
H.C. Hsiao, CCRC/NTHU
9/55
Popular DHTs: Chord, Pastry, Tapestry, etc.
Routing table
5
9
17
30
IP5
IP9
0
0+20 = 1
0+21 = 2
0+22 = 4
27
IP17
5
25
0+23 = 8
23
17
H.C. Hsiao, CCRC/NTHU
0+24 = 16
9
12
10/55
Routing
O(logN) hops, average ½ O(logN) hops
H.C. Hsiao, CCRC/NTHU
11/55
DHT is a Directed Interconnect
destination
source
H.C. Hsiao, CCRC/NTHU
12/55
DHT is an Exciting Technology Since…

More than “search”


Applications


DHT is a routing network: lookup path = routing path
Distributed file system, DNS, web caching, multicast,
anycast, broadcast, media streaming, service
composition, information retrieval, DDOS prevention,
NetNews, archive, search engine, …
In contrast, mass-market P2P--Gnutella

A searching network
H.C. Hsiao, CCRC/NTHU
13/55
App. I: Broadcast

Gnutella is a flooding-based protocol

May introduce redundant traffics
H.C. Hsiao, CCRC/NTHU
14/55
How to Broadcast a Message to k Nodes
Using k-1 Messages?

H.C. Hsiao and C.T. King. “A Tree Model for Structured
Peer-to-Peer Protocols,” Proc. IEEE/ACM CCGRID’03
H.C. Hsiao, CCRC/NTHU
15/55
App II: Multiplayer Game

Game company requires to deploy a large number of severs to serve
game players



This often requires to estimate the maximal # of online players
Costly and often underutilized if game severs are excessively deployed
C.W. Wang, H.C. Hsiao, W.H. Sun, C.T. King and M.T. Sun. “Building
a Tuple Space on Structured Peer-to-Peer Networks,” The Journal of
Supercomputing, 2005. (invited)
H.C. Hsiao, CCRC/NTHU
16/55
DHT in NTHU: Tornado

Finished the design: Sept. 2001

A practical design:



References


Enable handling peer heterogeneity
Exploit network proximity
H.C. Hsiao and C.T. King. “Tornado: A Capability-Aware Peer-toPeer Storage Overlay,” JPDC, 2004.
 An enabling architecture to take advantage of heterogeneity
 ScienceDirect top-25 most requested articles
A prototype, so far

Runs in a room having a 64-node cluster
H.C. Hsiao, CCRC/NTHU
17/55
DHT: Summary

DHT is a directed graph


Targeted environment




Nodes have unique IDs and hosts disjoint hash tables
Nodes can join, leave and fail at any time
Comm. links among nodes are unstable in terms of delays and
success route rates
The scale can be very large
Design principle


Correctness: nodes cooperatively maintain a ring
Performance: depend on shortcuts
H.C. Hsiao, CCRC/NTHU
18/55
Outline

DHT
10 min

Mobile DHT
35 min

Related studies
5 min

Discussions
H.C. Hsiao, CCRC/NTHU
5 min
19/55
Mobile DHT

Motivation




Several legacy applications built on DHT
 Apps.: multicast, DNS, RON, anti-spam mail, search
engine, backup, media streaming, resilient net, …
Toward a wireless Grid: locate and allocate resources
in wireless devices
 Some teams initiated wireless grid research
projects (e.g., Dr. Andrew Chien, UCSD) recently
Wireless devices want to access resources in DHT
However, DHT is for wired networks (i.e., Internet)

DHT + mobile devices?
H.C. Hsiao, CCRC/NTHU
20/55
DHT + Mobile Devices

Idea 1: Is a DHT servicing mobile devices




Mobile devices as dumb clients access DHT
 E.g., mobile devices share image files using DHT
 Each mobile device knows an entry point of DHT
 Put and get images of interests via a entry point
Mobile nodes are not DHT peers
Imply, we have some proxy- or portal-like DHT peers
 How? Where? Who?
Idea 2: Remain a DHT


Treat resources in wired and wireless sides as a whole
Support legacy apps.
H.C. Hsiao, CCRC/NTHU
21/55
DHT + Mobile Devices = Mobile DHT = DHT

Assumptions

No mobile IP infrastructure
 Lack of wide deployment
 Performance, reliability and management issues


Will mobile IP become another IP multicast?
DHCP is available, providing a unique Internet address
H.C. Hsiao, CCRC/NTHU
22/55
Mobile DHT
DHT
Wired-line network
H.C. Hsiao, CCRC/NTHU
23/55
Mobile DHT
DHT
New
IP addr.
H.C. Hsiao, CCRC/NTHU
Change
Network
attachment
point
New
IP addr.
24/55
Mobility vs. Ordinary Churns

Mobile DHT introduces an additional type of churn—
mobility churn

Mobility churn
 Peers change locations, creating stale routing states to the
overlay
 Moving peers are still alive
Hash ID

IP addr.
Ordinary churns


Type 1: Fail-stop model
 Peers join once
Type 2:
 If peers rejoin, they are treated as “new” peers
 A node joins without using the same ID (but may with the
same network address)
H.C. Hsiao, CCRC/NTHU
25/55
Research Methodology

Study the impact of mobility churn


Identify sources of inefficiency


In terms of delay and bandwidth
Timeout, imperfect of geometry, resilience, …
Define the problems and propose solutions

Partial results
H.C. Hsiao, CCRC/NTHU
26/55
Timeout and Redundant Traffic

Route experiences timeout
• Delay += timeout * k
• Traffic += k
A route message


Can we have a timeout-free mobile DHT?
Timeout-free mobile DHT: any route experiences
zero timeout
H.C. Hsiao, CCRC/NTHU
27/55
Why Timeout-Free?

DHT:



Lookup, node joining and maintenance depend on
routing
Performance
ISP:





Each peer allocates 100 bytes/sec to maintain a DHT
10% of traffics are due to timeouts
10 bytes/sec is wasted
If a DHT has 500,000 peers, than 500,000 x 10
bytes/sec = 5 Mbytes/sec is wasted
How about x DHTs? x = 1, 10, 100, 1000, …
H.C. Hsiao, CCRC/NTHU
28/55
Problem Definition
For each peer:
Maintenance bandwidth
B
t1
t2
time
Route requests

Goal:

a “cost-effective” timeout-free design
H.C. Hsiao, CCRC/NTHU
29/55
Is Rudimentary Sol. Timeout-Free?

Rudimentary peer joining and departure algo.


Assumptions


When a peer joins, it sets up its routing table
 Discover nearby ring neighbors
 Discover shortcut neighbors
Mobile peer invoke joining and leaving op. when it is
reattaching and detaching the net, respectively
Does rudimentary sol. work well? If yes (or no),
what are the scenarios?
H.C. Hsiao, CCRC/NTHU
30/55
An Ideal, but Impractical Design

When a peer moves,



Assumptions



The system is frozen: no activity is allowed
Clear all states regarding the peer
Each node know who caches the state of a moving peer
The system can be frozen
Impractical


May not be realized: how to freeze a system?
Cannot be realized if T > t
 T: the delay the system takes to clear a stale state of

peer A
t: the delay between two route requests received by A
H.C. Hsiao, CCRC/NTHU
31/55
Experimental Setting

Event-driven simulator
H.C. Hsiao, CCRC/NTHU
32/55
Workload

Route request traffics


Ordinary churns types 1 & 2



Nodes have the lifetime equal to x minutes
x = 10, 150
Mobility churn



Each node issue 0.3 route requests per minute (typical query rate
in Gnutella)
Nodes change their locations every y minutes
y = 50~480
Nodes perform failure detection and recovery
H.C. Hsiao, CCRC/NTHU
33/55
Results (B = 110 bytes/sec)

PHT: Percentage of hop count due to timeout
PBT: Percentage of traffics due to timeout

Rudimentary impl. does not work well


Increase delay (+100%) for each route req. and traffics (+15%)
for each peer
H.C. Hsiao, CCRC/NTHU
34/55
Rudimentary Sol. Works Fairly When…

Effects of failure detection period 

Effects of failure recovery period 

Effects of the number of mobile nodes 

Effects of stationary period 

Effects of peer lifetime 

Effects of route request rate 
H.C. Hsiao, CCRC/NTHU
35/55
Effects of Peer Lifetime
H.C. Hsiao, CCRC/NTHU
36/55
Why Rudimentary Sol. Cannot Work Well?
Maintenance in DHT
N80 ring member
Lifetime
+20 IP addr
N16
N112
80 + 25
+21 IP addr
80 + 26
N80 backup ring member
N96
+23 IP addr
80 + 24
80 + 23
80 + 22
80 + 21
80 + 20
Stabilization
every 5 min
+24 IP addr
+25 IP addr timeout
+26 IP addr
N80
Stabilization
every 0.5 sec
H.C. Hsiao, CCRC/NTHU
37/55
If Peers Move, …
N80 ring member
Lifetime
+20 IP addr
+21 IP addr
80 + 25
80 + 26
N80 backup ring member
+23 IP addr
80 + 24
80 + 23
80 + 22
80 + 21
80 + 20
Stabilization
every 5 min
+24 IP addr timeout
+25 IP addr
+26 IP addr timeout
Stabilization
every 0.5 sec
H.C. Hsiao, CCRC/NTHU
38/55
DHT Protocol Design Considerations

Failure detection mechanisms


Any mechanism to identify and remove a stale state
If s is a stale state in peer ni, then
state(ni )  state(ni )  {s}

Failure recovery mechanisms

Any mechanism to include a fresh state into peer ni
state(ni )  state(ni )  {s}

Peer joining and departure algo.

Designate which of states should be included/excluded
into/from peer ni
H.C. Hsiao, CCRC/NTHU
39/55
A Framework
Joining/Departure
N
Timeout-free Mobile DHT
logN
C
Periodic Cooperative
Periodic
Reactive
Cooperative
Detection mechanism
Recovery mechanism
H.C. Hsiao, CCRC/NTHU
40/55
Solution
(Remind that each peer has a given maintenance bandwidth budget B)

Know your reverse neighbors



DHT is asymmetric
We are not creating a symmetric DHT
 Symmetric DHT means we pay extra cost!
Listen the ping; keep a list of who are pinging me
Pong
a ping
{a, b, c, d}
b
RN(p) = {a, b, c, d}
p
d
c

Let reverse neighbors know each other, effortlessly

Take advantage of ring structure
H.C. Hsiao, CCRC/NTHU
41/55
Prioritizing Maintenance Traffics

Given a maintenance bandwidth B



B1: failure detection and recovery for “nearby” ring
fingers
 B – B1
B2: failure detection for remaining ring fingers
 B – B1 – B2
B3: failure recovery for remaining ring fingers
H.C. Hsiao, CCRC/NTHU
42/55
Results
H.C. Hsiao, CCRC/NTHU
43/55
Route Length



Timeout-free design highly ensures a route to experience zero
timeout
Route delay also depends on failure recovery mechanisms
When a peer reattaches, update its state to peers that are
interested in its current location
Joining/Departure
N
Timeout-free Mobile DHT
logN
Periodic Cooperative
Detection mechanism
Periodic
Reactive
Improve timeout-free design
Cooperative
C
H.C. Hsiao, CCRC/NTHU
Recovery mechanism
44/55
Results
H.C. Hsiao, CCRC/NTHU
45/55
Mobile DHT: Bristle

Timeout-free route

Keep the route length low



Failure route


Aggressive push the state of a peer
At the expense of introducing traffics
Stationary layer as a last resort
Preclude mobile nodes involving routing


Neighbor selection: pick fingers that are stationary
How many stationary nodes are sufficient?
H.C. Hsiao, CCRC/NTHU
46/55
Bristle
subscribe
Stationary Layer
Publish
H.C. Hsiao, CCRC/NTHU
47/55
Routing in Bristle
Source
Destination
H.C. Hsiao, CCRC/NTHU
48/55
Stationary Layer as a Last Resort
Source
Retrieve
Publish
Destination
H.C. Hsiao, CCRC/NTHU
49/55
Bristle is Robust

Effects of varying the number of mobile nodes 

Effects of network topology and proximity 

Effects of node heterogeneity 

Effects of stabilization period 

Effects of stationary period 

Effects of system size 

Effects of system dynamics (under very dynamic )
H.C. Hsiao, CCRC/NTHU
50/55
References




H.C. Hsiao and C.T. King. “Bristle: A Mobile Structured
P2P Overlays,” Int’l Parallel and Distributed Processing
Symposium (IPDPS), 2003.
H.C. Hsiao and C.T. King. “State Management in DHT
with Last-Mile Wireless Extension,” a chapter in the book
Theoretical and Algorithmic Aspects of Sensor, Ad Hoc
Wireless and Peer-to-Peer Networks, CRC press, 2004.
H.C. Hsiao and C.T. King. “Mobility Churn in DHT,” Int’l
Workshop on Mobility in P2P Systems (MPPS), 2005.
H.C. Hsiao, C.T. King, and C.-W. Wang. “Mobile
Distributed Hash Tables,” JPDC, Feb. 2005.
H.C. Hsiao, CCRC/NTHU
51/55
Outline

DHT
15 min

Mobile DHT

Related studies
35 min
5 min

Discussions
H.C. Hsiao, CCRC/NTHU
5 min
52/55
Related Work

Mobile IP


Internet Indirection Infrastructure (i3), UC Berkeley







From the perspective of service providers
Mobile nodes are not parts of DHT
DHT on top wireless mobile ad hoc networks, Purdue Uni.


Should mobility management be done in the network layer?
State consists of ID and “routing path” (instead of simply IP
address)
ns-2 does not scale
DHT in sensor networks, UC Berkeley
 CAN (coordinate space) over sensor nets
Measurement study: eDonkey in GRPS/UMTS
Gnutella-like file sharing in wireless, ad hoc networks
…
H.C. Hsiao, CCRC/NTHU
53/55
Some Interesting Issues

Timeout-free design may overkill



How to keep each route with O(logN)? Or, ½ O(logN) in
average?
ID assignment




Cross layer design may slow the deployment of mobile DHT
Study mobile DHT in the presence of mobile IP


Mobile peers keep routing tables in smaller sizes
Have risks
Take the condition of air links into design consideration


Effects of traffic patterns?
How to deploy home and foreign agents?
In general, is DHT (mobile DHT) a service or a library?
Broader aspect: mobility churn in not unique to mobile
DHT

DHT with virtual nodes
H.C. Hsiao, CCRC/NTHU
54/55


P2P, DHT and mobile DHT
Mobile DHT






cost
Investigation of design space


Mobility churn (vs. ordinary churn)
Timeout, route length, failure route, …
performance
Summary
Propose simple, but effective solutions for complex systems
Thoroughly understand the performance of proposed solutions.
Performance vs. cost (probably a unique problem in p2p
overlays)
Develop different failure detection and recovery
mechanism for different types of churns
Long way to go toward our envision—wireless Grid!
H.C. Hsiao, CCRC/NTHU
55/55
Any Comments or Questions?
Thank you