Transcript June 10, 2002 - UCSB Computer Science

Supporting Rapid Mobility via
Locality in an Overlay Network
Ben Y. Zhao
Anthony D. Joseph
John D. Kubiatowicz
Sahara / OceanStore
Joint Session
June 10, 2002
Intro Algorithms Evaluation Conclusion
Ubiquitous Computing to the Edge

Trends
–
–
–

Network infrastructure growing fast (802.11b, 3G)
Edge devices getting smaller, more powerful
Edge devices increasing in storage capacity
Legacy mobility support not enough
–
–
Mobile IP focused on single roaming nodes
# of mobile devices reaching critical mass


–
ZXL
E.g. ~400 million Cellphones, PDAs
Sheer volume can overwhelm mobility infrastructure
Devices need object location support for P2P
applications (IM, file sharing, directory services)
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Pushing the Limits of Mobility


What is the next step?
Scenario I
–
–

Scenario II
–
–
ZXL
UCB Professor roaming to MIT, directing streaming
media to his laptop, participating in video-conference
Need: persistent connection with low latency delivery,
and fast handover between proxies
Morning ride on BART, 100-1000 wired commuters
switching from proxy to proxy in tandem
Need: scalable solution to proxy handover for large
mobile groups (tourist groups, airplane passengers,
etc…)
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Legacy Mobility Support

Mobile IP review
–
–

Issues
–
–
–
ZXL
Mobile Host (MH), Correspondent Host (CH)
Home Agent (HA), Foreign Agent (FA)
Path: CH  HA  FA  MH
Triangle routing (High RDP)
More fault-prone
Higher BW
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
What Do We Need and Why?

Mobile IP weakness: triangle routing
–
–
–

Key insight: scalability via locality-awareness
–
–
–

Client requests result in load on overall network
Dampen / confine the impact of network operations:
reduce wide-area storage / communication costs, faults
In practice: minimize routing and update latency by localizing
communication
Strategy:
–
ZXL
High latency for messages and location updates
Messages / updates incur high costs in wide-area
Messages / updates susceptible to wide-area routing failures
Leverage locality-aware overlay infrastructure: Tapestry
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Tapestry Review

Decentralized object location and routing overlay
–
–

Routing infrastructure based on prefix routing
–

Route to nearest node increasing prefix match by 1
AA93  4A6D  4361  437A  4378
Locality-aware design:
–
–
–
ZXL
Related to approach in PRR97
Related projects: Pastry, Chord, CAN, Kademlia
Proximity routing: local traffic confined to local network
Object location: replicate Log(N) pointers to object, place
disproportionate more replicates near object
Result: RDP of routing to node is small
Finds closest copy of object with low RDP
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Object Location and Routing
ZXL
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Mobile Tapestry
ZXL

Reduce mobility problem to object location

Register (MN) = Proxy “publish” object MN with
reverse forwarding path

Routing to MN = Find object MN + forward by
proxy

No HA, no FA, no triangle routing
The Internet is your home network!
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Registration and Routing





Mobile node mn registers with
nearby proxy P
RegisterMsg R publishes object
named mn at
node P
Nodes store location
mapping <mn, P>
Message for mn routes
to P, then to mn
Object location locality 
distance traveled by message
proportional to actual distance
between CH and P
R(mn)
A
B
CH
P2
P1
mn
RegisterMsg
Message to mn
ZXL
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Location Updates






mn moves from P1 to P2
sends ProxyHandoverMsg U
mn sets up forward link from
P1 to P2
Update message U routes
up until intersects old
route at B
U backtracks to P1 to
delete old references
Message M forwarded
as RouteObjMsg to
proxy P2, then to mn
Routing locality  distance traveled
by update “proportional” to distance
between proxies
R(mn)
A
B
CH
P2
P1
mn
UpdateMsg
Message to mn
ZXL
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Mobile Objects

Extending object location to mobile nodes
–

Mobile object location
–

Extra step of indirection
CH routes message to mobile object MO
–
–
–
ZXL
Access data on roaming devices
Route msg to MO, find <MO, MN>
Route msg to mobile address MN, find <MN, P>
Route msg to proxy P, then forward
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Mobile Objects
R(mn)
R(mo)
B
A
P
mn
CH
<mo, mn>
location update
forwarding pointer
ZXL
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Hierarchical Mobility

Scenario:
–
–

Train server is node in mobile Tapestry
–
–

Server publishes MDi as local object
<MDi, S> for all i
CH sends message to a device
–
–
ZXL
Server registers with nearby proxies Px as node S
Each proxy Px updates location of S
Each mobile device registers with train as MDi
–

Networked bullet train in motion
Carrying passengers with 1000 networked devices
Message routes to Di, finds mapping for S
Message routes towards S, routes to P, then S, then Di.
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Hierarchical Mobility
R(S)
R(md1)
B
A
P2
P1
bullet train S
md1
md2 md3
md4
ZXL
md5
[email protected]
CH
<md1, S>
location update
forward pointer
June 10, 2002
Intro Algorithms Evaluation Conclusion
Levels of Type Indirection





ZXL
Functionality enabled by
multiple levels of indirection
Mobile node = object on
static node (proxy)
Mobile object = object on
mobile node
Mobile child = object on
mobile node (proxy)
Potentially limitless levels
of indirection for hierarchy
of mobile devices
[email protected]
Proxy Node
residing on
Mobile Node
Indirection as
residing on
Mobile Child
Object on
Static Node
Object on
Mobile Node
Indirection as
residing on
Object on
Mobile Child
June 10, 2002
GUID Aliasing


Utilize redundancy for performance and stability
Each node gets several aliases
–

Usage
1.
2.
ZXL
Generated by SHA-1(nodeID, int i) for (0 < i < 5)
CH sends message to ALL aliases
MN receives first, drops duplicates
On initializing connection, CH sends message to ALL
aliases. MN responds and indicates preferred alias.
All subsequent communication uses chosen alias.
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Simulation Framework

Packet level simulation
–
–

Experiments on GT-ITM topology
–
–

Aggregated over 9 topologies
Each run over 3 random overlay placements
GUID aliasing
–
–
ZXL
Simulation of network topologies
(5000 nodes, 4096 Tapestry nodes,
6 digit base 4 IDs for nodes / objects)
No simulation of congestion or network-level traffic flow
Initiate connection by using 3 parallel aliases
Quickly measure and pick alias for good performance
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
GUID Aliasing vs. Mobile IP
GUID Aliasing vs. Mobile IP
MIP Distant HA
45
MIP Closeby HA
Tapestry (2 GUIDs)
Tapestry (5 GUIDs)
40
Latency RDP
35
30
25
20
15
10
5
0
0
100
200
300
400
500
600
Shortest Path Latency from CH to MN (ms)
ZXL
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Update Latency w/ Rapid Mobility
Update Latency under Rapid Mobility
Distant Home Agent
Nearby Home Agent
2 GUIDs
5 GUIDs
2000
Location Update Latency (ms)
1800
1600
1400
1200
1000
800
600
400
200
0
0
ZXL
100
[email protected]
200
300
400
Latency Between Proxies (ms)
500
600
June 10, 2002
Intro Algorithms Evaluation Conclusion
Router Load vs. Mass Mobility
Maximum Router Load from Location Binding Updates
Mobile IP
Mobile Tapestry
Max Load per Router (Msgs/min)
2500
2000
1500
1000
500
0
100
200
300
400
500
600
700
800
900
1000
# of Mobile Nodes Roaming at 1 Proxy/minute
ZXL
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Summing It Up…

Mobility via indirection
–
–


Distinctions from ROAM: all based on locality-awareness
Performance
–

–
Localize traffic around shortest path, stabilize wide-area
Use multiple levels of indirection for hierarchical mobility
Fault-tolerance
–
ZXL
Tapestry routes with locality  low RDP for routing (even with
indirection), fast location updates
Extreme scalability
–

Mobile nodes register as “objects” in infrastructure
Messages to mobile node redirect through location pointer
Reduce susceptibility to wide-area faults by localizing wide-area
traffic
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
For More Information…


Tapestry / Bayeux / Brocade
–
http://www.cs.berkeley.edu/~ravenben/tapestry
–
Locality-awareness Mechanisms for Large-scale Networks
Zhao, Joseph, Kubiatowicz. Proc. of FuDiCo 2002
OceanStore
–

Other relevant material:
–
ZXL
http://oceanstore.cs.berkeley.edu
http://www.cs.berkeley.edu/~ravenben
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Backup slides follow…
ZXL
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
GUID Aliasing
ZXL
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Towards Uniquitous Computing

Applications driving force
–
–
–

How close are we?
–

Networking, Hardware scaling down, HCI,
management, …
Some issues getting closer with time
–
–
–
ZXL
Leveraging resources on a global scale
Storage: file sharing, multimedia  Rio, I-Pod
Connectivity: decentralized communication  AIM/ICQ
Devices decreasing in size
Increasing in power (Moore’s law)
Network connectivity expanding
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Ongoing Issues I

Enabling edge devices
–
–

ZXL
Less resources
Disconnected / mobile operation
Need infrastructure support
[email protected]
June 10, 2002
Intro Algorithms Evaluation Conclusion
Ongoing Issues II

Extending scale
–
–
ZXL
Network increasing in size and complexity
Faults, misconfiguration, flash-crowds result in loss of
availability
[email protected]
June 10, 2002