Transcript Computer Science 848 Presentation

CS848:
Pervasive and Mobile Computing
Mobile Computing Models
April 15, 2002
<My Name Here>
Department of Computer Science
The University of Western Ontario
Outline


Agile Application-Aware Adaptation for Mobility
Mobile Agents for Mobile Computing
Agile Application-Aware
Adaptation for Mobility
B. Noble, M.Satyanarayanan, D. Narayanan, J.
Tilton, J. Flinn, K. Walker
Motivation: Mobile Clients

Many Problems:
 unpredictable variation in network quality (jitter)
 inconsistent availability of remote services
 limitations on local resources
 battery power
 less reliable
Adaptation is key to mobility.
What is Odyssey?

A set of extensions to NetBSD to support adaptation for
mobile information access applications.

Minimalist

“..smallest set of interface and code extensions… necessary
for agile adaptation in mobile environments”
A Brief History of NetBSD





First Version (0.8) dates back to 1993
Originally from the 4.3 BSD Lite OS
University of California, Berkeley
Open source.
Latest Version 1.5.2.
Philosophy of NetBSD




A stable and complete base system without redundancy
Not to be satisfied with partial implementations.
Other systems have the philosophy of "If it works, it's right".
NetBSD has the philosophy "It doesn't work unless it's right".
Digital Alpha (64bit)
Commodore Amiga,
MacroSystem DraCo
Acorn RiscPC/A7000,
CATS, Digital Shark,
EBSA-285, VLSI
RC7500
The PC532
Hewlett-Packard
9000/300 and 400
i386 family IBM PCs
and clones
Apple Macintosh
Apple Power
Macintosh
Motorola MVME 68k
SBCs
NeXT 68k 'black'
hardware
Sun SPARC
Sun 3 and Sun3x
Digital VAX
Atari TT030, Falcon, Hades
Digital MIPS-based
DECstations and
DECsystems
Sharp X680x0
Playstation2, Dreamcast (!)
Basic Features of NetBSD





Portability (over 20 platforms are supported)
Code quality and correctness
Adherence to the standards
Research and innovation
A good (according to them, only) choice for a Unix
system that runs consistently on a variety of
platforms.
Fidelity

Definition: The degree to which data presented at a client
matches the reference copy at the server.

Many dimensions to Fidelity, varies depending on application.
Consistency = Universal dimension.
Examples of Application-specific dimensions:
 Video: frame rate, image quality of frames.
 Spatial Data: resolution
 Telemetry: sampling rate, timeliness


Concurrency






Vital
Taken for granted on desktop OS.
Is it useful for mobile clients?
Yes, because users will want to run stuff in background.
 For example information filtering applications, (stock
prices, SMS, emergency response)
Support: control use of limited resources
 Need centralized monitoring and coordinated resource
management on a mobile client.
Makes many applications less effective.
Agility

Definition: The speed and accuracy in detecting and
responding to changes in resource availability.

Complicated with many components:
 Differing sensitivity for different resources
 Different causes for changes in availability of the same
resource
Application Aware Adaptation




Ideally, mobile client has perfect knowledge of current
resource levels.
Odyssey model is best characterized as application-aware
adaptation. Essentially a collaborative partnership between
the system and individual applications.
Attempts to address application diversity and concurrency.
Challenge is to support this separation without compromising
agility.
Models of Adaptation
Realizing the Model

Obvious Implementation:
 directly address previous issues on an individual basis
 system code treats data generically
 individual applications responsible for differential handling
of data types

Can't Do This Because:
 disparity in the properties of the various data types
 E.g. Video can drop data, but with FTP that's bad.
 Needs system-level knowledge of type
Realizing the Model

Solution: a more sophisticated architecture with two
responsibilities.

(1) Must be aware of shared access to remote data by
concurrent applications.
To properly manage resources.


(2) Must have type-specific knowledge.

For resource management actions.
Wardens

Odyssey incorporates type-awareness via specialized code
components called wardens.

Wardens encapsulate the system-level support at a client
 to effectively manage a data type.

A warden has to be incorporated into Odyssey at each client
for each new data type.

Subordinate to Viceroy
Viceroy


Responsible for centralized management
Type independent component
A Collaborative Relationship

Two Parts:
 Data-centric (Viceroy and Wardens).
Get fidelity level for each data type
Factors them into resource management.



Action-centric (Applications and Odyssey)
Applications control selection of fidelity levels
Supported by the wardens.


Odyssey Client Architecture
Operating on Odyssey Objects






Built upon NetBSD file system calls
Implemented in user space, instead of kernel.
Operations on Odyssey objects are redirected to the viceroy
by a small in-kernel interceptor module.
All other system calls handled directly by NetBSD
Wardens statically linked with the viceroy
Wardens entirely responsible for communicating with servers

Odyssey and the file system are integrated
Integration

Pros:
 Well-understood framework
 Simplified implementation
 Can provide small amount of type-awareness without new
system calls.

Cons:
 Some data types don't fit
 No standard operations for changing fidelity
Expressing Resource
Expectations

Applications communicates resource expectations to Odyssey
using the request system call.
Resource Negotiation Operations
Request(in path, in resource-descriptor, out
request-id)
Cancel(in request-id)
Expressing Resource
Expectations
Application
Decides on New
Fidelity Level
Sends
request
Return Error Code and
Current Resource Level
Odyssey receives
request.
Tolerance
OK
Send ID to
Application
Application happy, life
goes on.
Viceroy
registers
request
Tolerance
NOT OK
Sorry
Expressing Resource
Expectations



Each resource is named by a unique resource identifier
Window of Tolerance indicated by upper/lower bounds.
Resource descriptor also specifies the name of a procedure
that will be called to notify the application that the resource
has left the window.
resource-id
lower bound
upper bound
name of upcall handler
Resource Descriptor Fields
Generic Resources in Odyssey
Network Bandwidth
Network Latency
Disk Cache Space
CPU
Battery Power
bytes/second
microseconds
kilobytes
SPECint95
minutes
Notifying Applications



When availability of resource strays outside registered
window of tolerance, viceroy generates an upcall
Application adjusts its fidelity.
Makes another request call to register a revised window of
tolerance appropriate to the new fidelity.
handler(in request-id, in resource-id, in
resource-level)
Upcall Handler
Notifying Applications

Upcalls closely resemble UNIX signals but with more features

Like signals:
 can be sent to one or more processes
 can be blocked or ignored
Unlike signals:
 offer exactly-once, in-order semantics for each receiver of
a particular upcall
 parameters can be passed to target process
 results returned

Changing Fidelity


Not supported easily by NetBSD file system interface
 untyped byte stream model
General purpose mechanism, tsop (type specify an
operation).
tsop(in path, in opcode, in insize, in
inbuf, inout outsize, out outbuf)
Example Applications

Three types:
 Video Player
 Web Browser
 Speech Recognizer

Each have different fidelity requirements
Video Player
Video Player







Using Xanim
Split monolithic implementation into client and server
Wrote a Warden to handle client request and fetch data from
server
Three levels of fidelity (99, 50, 0.01).
Warden supports two tsop's, to read movie meta data and get
specific frame from track
When player opens a movie, it calculates the bandwidth
requirements
When notified of bandwidth change, determines new fidelity
level and switches to that track
Web Browser
Web Browser





Redirect all Netscape requests to module called Cellophane
 uses Odyssey API to select fidelity level
 transforms HTTP requests into file operations
Web warden forwards requests to a distillation server
Distillation server provides multiple levels of fidelity
 fetches request objects from appropriate web server
 distills them to the requested fidelity level
Transparent to web server and Netscape.
Code interpositioning is solution for non-open source
applications.
Speech Recognizer
Speech Recognizer






Using Janus
Split into client and server and speech warden constructed
Front end captures raw speech and writes it to an object
Warden decides if it is faster to perform first pass of the
recognition on local, slower CPU or ship it raw to the server
Server can accept raw or partially processed speech
Recognized speech converted into text
Evaluation

Three Questions:
 How agile is Odyssey in the face of changing network
bandwidth?
 How beneficial is it for applications to exploit the dynamic
adaptation made possible for Odyssey?
 How important is centralized resource management for
concurrent applications?
Agility Metrics

Generate sharp discontinuities in network bandwidth
 120kB/s for high
 40 kB/s for low
How Agile Is Odyssey?




Viceroy looks at log entries
 round trip entries for small exchanges
 throughput entries for bulk transfers
Each entry measures TIME it takes to receive a window's
worth of data
Viceroy estimates bandwidth available per connection
Estimate composed of two parts:
 competed-for (proportional to recent use)
 fair-share (expected lower bound)
Varying Supply



Ran an application that consumed data as fast as possible
through a streaming warden
Available Bandwidth varied
Results:
 Works very well with sudden increases
 Not so good for sudden decreases
Varying Supply
Varying Supply
Varying Supply
Varying Supply
Varying Demand




Client given 30 seconds alone
Second identical client added
Three experiments: 10%, 45% and 100%
Results:
 immediate reaction for low utilization
 slower for higher demand ones
 give preference to first client (until second one establishes
itself)
Results: Video Player



Goal: play highest quality without dropping frames
Three fidelity levels:
 1.0
 0.5
 0.01
Run Xamin for each of the three levels, then run Odyssey
Results: Video Player

Results:
 Drop less frames then going at JPEG(99) alone
 Manages to drop fewer frames by reverting to JPEG(50)
frames at lower bandwidth
 Since this means more JPEG(99) frames shown, therefore
meets self-described goals...
Results: Web Browser


Goal: Fetch 22kB image as fast as possible
Cellophane chooses from four fidelity levels:
 1.0
 0.5
 0.25
 0.05
Results: Web Browser

Results:
 "Meets our performance goal in all cases"
 Faster than static strategies
 In Impulse-Up case, fooled into fetching better quality
images
Results: Speech Recognizer

Goal: Speed of Recognition

Three fixed strategies:
 Always Hybrid
 Always Remote
 Adaptive
Results: Speech Recognizer

Results
 Hybrid best (for when speech is only application running)
 Odyssey copies Hybrid
 Unconfirmed: Adaptive better for higher bandwidths
Importance of Centralized
Resource Management

Method: Compare Odyssey to laissez-faire and blindoptimism.

Laissez-fair: No resource management
 simulated by looking at logs in isolation

Blind-optimism: networking layer of OS notifies applications
when switching between network technologies.
 simulated by passing the theoretical bandwidth to the
viceroy at each transition. Viceroy then notifies any
interested applications.
Importance of Centralized
Resource Management

Results:
 Odyssey better
 Drops less frames
 Able to do so because it correctly accounts for bandwidth
competition
Importance of Centralized
Resource Management

Most real-time systems use a resource reservation system

Odyssey does not, tries keep things transparent to application
 uses feedback driven adaptation
 no need to calibrate resource to specific applications

Author's argue that installation of pieces of code at low levels
already done in databases for improved performance.
Future of Odyssey

Full support for deciding between dynamic function and data
shipping

Support the searching of distributed repositories by using
dynamic sets.

Better techniques for analyzing agility and stability
Summary of Odyssey




Need adaptation for mobile information access
Application-aware adaptation most general approach
Odyssey does this
 Through collaboration between application and system
Experiment supposed to show prototype is feasible.
Issues/Discussion

Needs warden for every application

Application must be aware of its own fidelity
 What if all applications took a selfish approach?
 Everyone has to play nice.

Does network bandwidth really have so much variance as to
require this?
Mobile Agents For Mobile
Computing
R. Gray, D. Kotz, S. Nog, D. Rus, and G. Cybenko
Research in AI community


Single-agent systems:
 Action selection (planning)
 Knowledge representation and inference
 Agent learning and adaptation
Multi-agent systems:
 Communication and collaboration
 Emergent properties of group behavior
Motivation

People want access at all times but...
 Mobile computers often disconnected
 Connection often has low bandwidth and high latency
and is prone to sudden failure
 Network connection varies
 May be assigned a different IP address every time it
connects.

Unreliable
What is an Agent?

A program (“software agent”), e.g.,
Personal assistant (mail filter, scheduling)
Information agent (tactical picture agent)
E-commerce agent (stock trader, bidder)
 Recommendation agent (Firefly, Amazon.com)
A program that can:
 interact with users, applications, and agents
 collaborate with the user
Software agents help with repetitive tasks





What is an Agent?

Not all programs are agents

Agents are:
 customized
 persistent
 autonomous
 adaptive
What is a mobile agent?
Search
engine
Machine A

Machine B
An Agent is something that:
 migrates from machine to machine
 in a heterogeneous network
 at times of its own choosing
Why Mobile Agents?




Efficiency: consume fewer network resources by moving the
computation to the data rather than the data to the
computation.
Fault tolerance: do not require a continuous connection
between machines.
Convenient paradigm: hide the communication channels but
not the location of the computation.
Customization: allow clients and servers to extend each
other's functionality by programming each other.
Why Mobile Agents?



There are many alternative techniques -- queued RPC, proxy
servers, etc. -- that have many of these same advantages.
The problem with these alternative techniques is that each one
is only suitable for certain applications.
A mobile-agent system is a single, unified framework in
which a wide range of distributed applications can be
implemented easily and efficiently.
Reason: Uses Less Bandwidth
Database
Server
Client/Proxy
Database
Server
Client/Proxy
Reason: Bandwidth Conservation
Database
Database
Dynamically selected
proxy site
Database
Reason: Reduce Latency
Server Agent
1. Observe
high average
latency to
clients
2. Move to
better location
Reason: Reduce Completion Time
Efficiency
1. Send code with unique query
Low bandwidth channel
Mobile user
3. Return requested data
2. Perform multi-step
queries on large, remote,
heterogeneous databases
Reason: Load balancing
Jobs/Load
Jobs/Load migrate in a heterogeneous network of machines
Agent Tcl

Reduce migration to a single instruction. (Programmer should
not have to explicitly collect state information)

Provide transparent communication among agents.

Provide a simple scripting language as the main agent
language and allow the straightforward addition of a new
language or transport mechanism.

Provide effective security
Architecture of Agent Tcl
Architecture of Agent Tcl

The Agent server:
 keeps track of the agents that are running on its machine
 provides inter-agent communication facilities
 accepts and authenticates agents arriving from other host
and restarts these agents in their own interpreter.

All other services are provided by agents.
Agents themselves are separate processes executing the
appropriate language interpreter.

Mobile Computing

Agent system must support disconnected operation

To be effective, an agent must be able to:
 jump off a partially connected computer and return to it
 navigate through the internet to find the services it needs
 sense and react to the network environment
 communicate effectively with other agents
Laptop Docking System

Each laptop is paired with a dock machine
Jumping To or From a Laptop
2. If laptop
unreachable,
go to dock
Queue of agents
waiting to go to M
1. Jump directly
to laptop
Queue of agents
waiting to leave
4. Notify dock of
new location
M (laptop)
M_dock
(permanently
connected
machine)
5. Transfer waiting
agents in both
directions
3. Change in
network status
Laptop to Laptop Jump

Both laptops could be never be connected simultaneously!
Multi-destination Jumps




For when agent:
 wishes to visit multiple hosts in no particular order
 is to search all sites for information
 is visiting one of a replicated set of servers
Dock-master on S tries to transfer the agent to one of the final
destinations by trying each one in order
If all destinations are unreachable, agent goes to S_dock. The
dock-master at S_dock repeatedly tries to reach the
destinations until it succeeds.
Agent wakes up knowing it has arrived at one of the
destinations.
Hooks


More control over jumping process
allow agents to:
 query the status of the network connection
 request a failure notification
 request that the jump go as far as possible then be awoken
Agent Navigation and Adaptation

World is dynamic and uncertain
 Machines go up and down
 data changes
 steps to complete a task often not completely known

An autonomous agent is crippled with no without external
state
An agent needs sensors for adaptive navigation

Network Sensing



Ability for a laptop to detect the state of its network
connection
Enables agents to adapt to changing network conditions
For example: an agent that needs to visit information
resources at several sites.
 A smart agent should be able to adapt if some sites
currently unreachable and visit others first.
 A smarter agent may be able to plan a sequence of visits
given an estimate of the current network delay to each site.
 Maybe tailor their behaviour to the current bandwidth
Network Sensing Tools

So agent can get info about the network status
 A tool to determine whether the local host is physically
connected. (Pings the broadcast address on the local
subnet)
 A tool to determine whether a specific host is reachable
(just standard ping)
 A tool to determine the expected bandwidth to a remote
host
Bandwidth is predicted from experience, not measured
Weighted average of all communications


Navigation Agents

Agents need a dynamic index of service agents to locate other
agents

Virtual Yellow Pages contain listing of services and their
locations.
 distributed database of service locations
 maintained by navigation agents
Navigation Agents




Services register with a navigation agent
Each machine has special agent that knows the location of
some of the navigation agents
By consulting the local specialist agent and then visiting one
or more navigation agents, an application agent can get a list
of services and their locations.
Adaptive learning methods are used to keep the virtual yellow
pages up-to-date.
An Example of Navigation
Navigation Agents





After visiting the services listed, the application agent returns
to the navigation agent to provide feedback on the usefulness
of the sites.
Navigation agents use this info to prioritize their lists.
Application agents that discover services accidentally report
the corresponding sites to the navigation agents.
Relevant services might be discovered while handling a
different but related task.
If agent receives different site information from two
navigation agents it will tell it to them
Adaptive Agent Navigation

Application agents use the prioritized list of services they
receive from the navigation agents as their initial plan.

Most applications want to visit either one or all sites on the
list.

Using network sensing tools they may want to skip some sites
that are unreachable to too slow (and go to them later).
Inter-Agent Communication


Low-level: agents communicate through message passing or
through a direct connection
Higher level: agent remote procedure call mechanism adds
structure and higher-level abstraction.
 Server agents in the system register with the local "nameserver”using a flexible definition language interface
 Client agents search for a service by providing a similar
interface and having the "name-server" find a match
 Flexible interface matching technique helps agents
communicate even if they share only a subset of complex
interface
Mobile node setup
Linux
laptop
Cabletron/
Digital
Roamabout
GPS
Unit
Metricom
Ricochet
Experiment






Laptop called Bond
Started an agent on Bond
Agent jumps off to remote server
Bond disconnected, moved to another lab
Meanwhile agent finished task and tried to jump back to
Bond.
Jump failed so transferred to Bond_dock, where its state was
saved
Experiment





Bond reconnected to different subnet with new IP
Bond's dock-master discovered new connection and new
address; sent message to Bond_dock in old lab
Bond_dock then sent waiting agent to Bond
Experiment repeated, carrying Bond back to old lab
Agent was able to leave laptop and return home twice, despite
disconnect, reconfiguration and new IP address
Future of Agent Tcl





Re-named to D’Agent (Dartmouth Agent)
www.cs.dartmouth.edu/~agent
Support for multi-destination jumps
Support for Persistent Storage
Refined bandwidth-prediction tools
Current trends lead to mobile agents
Information
overload
Diversified
population
Bandwidth
gap
Server-side
“Customization”
Increased need
for personalization
Too many unique,
dispersed clients to handle
Proxy-based
Multiple
sites to visit
Mobile
Agents
Avoid large
transfers
Mobile code
to client
Mobile users
and devices
Disconnected
Operation
Mobile code
to server
or proxy
Avoid
“star”
itinerary
High
latency
Conclusion: Pros

A unifying framework for making many applications more
efficient

Treats data and code symmetrically

Multiple-language support possible

Supports disconnected networks in a way that other
technologies cannot

Cleaner programming model
Conclusion: Acknowledged
Limitations




If agent is running on a machine and machine goes down,
agent is lost
If agent is running on machine and machine is disconnected
for very long time, agent stuck on machine
If laptop connected for only brief period of time, dock-master
agent won't detect connection
Cannot handle some environments, like nameless hosts (e.g.
PC with dynamically assigned IP addresses).
Issues/Discussion




Security is big a concern
 Malicious Agents
 Bad Machines
 etc.
Overhead for moving code is high
Not backward compatible with current code
Networks will be fast, performance may not be an issue
Mike and Sue Scenarios

Agile Application-Aware Adaptation
 device that measures the glucose level and transmits this
information to his doctor’s office.
 accepting verbal orders (the conference call: “Connect me
with John Robinson and Tom Smith at 9”)
 Sue wants to know if the price of XYZ reaches a certain
point so that she may buy it.
Mike and Sue Scenarios

Mobile Agents for Mobile Computing
 electronic shopping list
 doctor’s office keeps track of the measures
 Mike’s personal electronic agent negotiates with the dental
office-computing environment for an alternative time
 Mike selects a PRINTER for Tom’s message
 contents of the whiteboard are transmitted
 news delivered and personalized
Mike and Sue Scenarios

Mobile Agents for Mobile Computing Continued
 charts of patients downloaded to PDA
 computer in the hospital which may find that the supply of
medication is not enough, orders more
 personalized financial advisor agent, Fred
 Fred asked to check to see if enough $ to cover purchase