Transcript slides - SmartLab

RUBI
Adaptive Resource Discovery for Ubiquitous Computing
Rae Harbird
[email protected]
MPAC 2004
Stephen Hailes
[email protected]
Rae Harbird
Cecilia Mascolo
[email protected]
1
RUBI
• Resource discovery for Ubiquitous computing
• Autonomic, encapsulating overarching adaptive process
• Few assumptions are made about the network environment
• Operational over a wide range of network conditions
MPAC 2004
Rae Harbird
2
Outline
• Ubiquitous computing and resource discovery
• Review of existing protocols
• RUBI, design and evaluation
• Future work
• Conclusions and questions
MPAC 2004
Rae Harbird
3
Ubiquitous Computing
• Weiser’s vision becoming reality
– 250 million microprocessors sold monthly, < 2 % destined for PCs
• Ubicomp revenue
– Provision of novel services, low / no ROI from connectivity alone
• Environmental implications
– Huge heterogeneity, immense scale, dynamic operation and
volatility
MPAC 2004
Rae Harbird
4
Communications Paradigm
MPAC 2004
Rae Harbird
5
Communications Paradigm
MPAC 2004
Rae Harbird
6
Previous Work
• Global, central index of resources
– Jini
• Global, distributed index
– Distributed hash tables
• Resources discovered as needed
– Konark, UPnP, SLP
• Resource discovery based on ad hoc routing protocols
MPAC 2004
Rae Harbird
7
Proactive Resource Advertisement
MPAC 2004
Rae Harbird
8
Proactive Resource Advertisement
MPAC 2004
Rae Harbird
9
Proactive Resource Advertisement
MPAC 2004
Rae Harbird
10
Requests & Replies
MPAC 2004
Rae Harbird
11
Reactive Resource Requests & Replies
MPAC 2004
Rae Harbird
12
Reactive Resource Requests & Replies
MPAC 2004
Rae Harbird
13
Reactive Resource Requests & Replies
MPAC 2004
Rae Harbird
14
Reactive Resource Requests & Replies
MPAC 2004
Rae Harbird
15
Varying level of node mobility
MPAC 2004
Rae Harbird
16
RUBI
• RUBI based on two routing algorithms:
– proactive (OLSR) and reactive (AODV)
• Assumptions:
– IP level connectivity over any type of wireless link
– Assume nodes can create or obtain an IP address
– Operates at the network layer or at the application layer
MPAC 2004
Rae Harbird
17
Algorithm Selection
• How does a node determine the type of region it belongs to?
• Link duration is used as a mobility feedback mechanism
• Neighbour establishment used to assess stability of local
links
• Select routing algorithm based on perceived stability
– Proactive algorithm: stable enough to elect relay nodes
– Reactive algorithm: in all other cases
MPAC 2004
Rae Harbird
18
Proactive Request to Reactive Region
MPAC 2004
Rae Harbird
19
Proactive Request to Reactive Region
MPAC 2004
Rae Harbird
20
Response Implosion
• Problem:
– A large number of replies may be returned to the source of the
query
• Solutions:
– Introduce delay for nodes on the reply path
• Wait for a period and evaluate replies received before sending one onwards
• Evaluation can be difficult
– Use request cancellation message from source when reply received
MPAC 2004
Rae Harbird
21
Ensure Loop Free Operation
• Problem
– For composite requests, a node may satisfy only part of it
– Will forward a request for remaining (unfulfilled) resources
– Must ensure that new request is not processed by nodes that have
already seen it
• Solution
– Preserve original message ID
MPAC 2004
Rae Harbird
22
Experiment Design
• Choose simple scenarios to test different aspects of protocol behaviour
• Fixed characteristics
• Network size, density
• Relative node mobility
• Mobility model
• Node: Bandwidth, Power, Speed
• Varying characteristics
• Cache size and caching period
• Request rate
MPAC 2004
Rae Harbird
23
Measuring Performance
• Request success rate
• Protocol message overhead per resource request
• Latency of replies
– Showing where congestion exists in the network
• Amount of state maintained per node
• Request path length
– Number of hops a query must traverse in order to obtain a response
MPAC 2004
Rae Harbird
24
Discussion
• RUBI represents trade-off between:
– Context-aware operation
– Efficiencies gained by assuming stability
• Greater overhead than some approaches reviewed
– Neighbour establishment and monitoring
• More suitable for ubiquitous computing
– Adaptive in an uncertain network environment
MPAC 2004
Rae Harbird
25
Conclusions
• Resource discovery
– Key factor in realisation of ubicomp vision
• RUBI designed with ubicomp environment in mind
– Routing algorithms ensure the efficient dissemination of
information
– Autonomously adapts using locally obtained information
– More suitable than other ‘single algorithm’ approaches
MPAC 2004
Rae Harbird
26