Transcript Rapid Mobility via Type Indirection

Rapid Mobility via
Type Indirection
Ben Y. Zhao, Ling Huang,
Anthony D. Joseph, John D. Kubiatowicz
Computer Science Division, UC Berkeley
IPTPS 2004
Rapid Mobility
 large-scale mobile deployment becoming a reality
wired network
IPTPS 2004
[email protected]
2
Our Approach
 Warp: mobility infrastructure on structured P2P overlay

route using in-network indirection

directory service API (DOLR): RouteMsgToObject(ObjectID, Data)

treat mobile nodes as objects on their proxy
 Flexible hierarchy for fast handoff

layers of overlay forwarding hops


longer hops in wide-area, shorter hops in LAN
implicit hierarchy: only modify short hops if moving locally
 Aggregate control traffic for mobile crowds

“elect” mobile trunk node to tunnel traffic for others

reduce control traffic to one handoff per crowd
 Routing, hierarchy, aggregation all managed by P2P protocol
IPTPS 2004
[email protected]
3
Decentralized Object Location & Routing

Decentralized directory API on structured peer to peer overlays

Server “publishes” object: overlay distributes location pointers to log(n) nodes

Clients route message towards object’s ID, redirect when location pointer found

Performance from locality-aware routing and local convergence properties
IPTPS 2004
[email protected]
4
Registration / Routing
IPTPS 2004
[email protected]
5
Fast Proxy Handover
IPTPS 2004
[email protected]
6
Mobile Crowds
mp
mp
mp
mp
IPTPS 2004
[email protected]
7
Type Indirection
Proxy node
Overlay Node
object on
static node
Register / Handoff
…
Mobile Node
Mobile Node
Mobile Node
trunk
Type Indirection
object on
mobile node
Join/Leave
…
Mobile Node
leaf
… Mobile node
Mobile Node
Mobile Node
leaf
leaf
Mobile node
Mobile Crowd
 Leverage built-in indirection in object location layer of DOLR
 Can further iterate type indirection: e.g. PDAs on train passenger
IPTPS 2004
[email protected]
8
Routing Performance
 compare warp to Mobile IP
 add redundant root to reduce end to end latency
45
MIP far
Routing Latency RDP
40
MIP close
35
MIP medium
30
Warp
25
Warp 2 roots
20
15
10
5
0
0
50
100
150
200
250
300
350
400
Shortest Path Latency between MN and CH
IPTPS 2004
[email protected]
9
Handoff Latency
 compare time for Mobile IP, Warp and Warp full convergence
MIP Far
MIP Close
Warp Conv.
Warp
Time to complete handoff (ms)
2000
1800
1600
1400
1200
1000
800
600
400
200
0
0
50
100
150
200
250
300
Distance between Handover proxies (ms)
IPTPS 2004
[email protected]
10
Related Work
 Fast handoffs

hierarchical handoff (Caceres96)

hierarchical Mobile IP (Perkins96)

incremental route establishment (Keeton93)
 Session mobility (Snoeren00)
 ROAM (I3) (Zhuang03)

in-network traffic redirection pointers (triggers)

can do hierarchical mobility, node aggregation

placement of triggers up to mobile node
IPTPS 2004
[email protected]
11
Summary
 Flexible name-based hierarchical mobility

treat mobile nodes as “objects” on overlay proxy

routing protocol manages traffic redirection points

virtual paths eliminate home agent and triangle routing

no notion of “home network”
 Aggregation to reduce control traffic

treat leaf nodes as “objects” on mobile trunks
 Self-managing network redirection

rely on self-organizing protocol for aggregation, hierarchical
handoff, fast route establishment

protocol adapts to node failures, topology changes
IPTPS 2004
[email protected]
12
Thanks…
Comments, questions?
http://www.cs.berkeley.edu/~ravenben/tapestry
Handoff Load
Handoff Messages in Warp
100000
No aggregation
Uniform Dist.
Exponential Dist.
Binomial Dist.
10000
1000
100
10
1
1
IPTPS 2004
10
100
1000
Number
of Mobile Hosts
[email protected]
10000
100000
14