Transcript Training
CSCI 6361: Topics in Mobile
Computing
Dept. of Computer Science
University of New Orleans
Fall 2004
Dr. Golden G. Richard III
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
2
Intro to Mobile Computing: READ
READ: ParcTab paper to get a feel for
the challenges/potential of
mobile/pervasive computing
READ: Chapter 1 of Richard book
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
3
Ubiquitous, Mobile, Nomadic
Terminology not always consistent
– Nomadic computing: “portable”; no
mobility while connected
– Mobile computing: “on-the-go”, e.g., while
sitting on a train; possibility of network
connections remaining open
– Pervasive or Ubiquitous computing:
• computing everywhere… OR
• computers everywhere…most of them invisible
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
4
Computers Everywhere
Marc Weiser
Vision of ubiquitous computing: hundreds of
computers per person, various sizes and
capabilities
Tabs
–
–
–
–
very small--smart badge w/ user info, etc.
allow personalized settings to follow a user
leave bios behind at meetings
attached to virtually everything--e.g., books,
car keys, etc.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
5
Ubiquitous Computing: Reality
Pads
– “scrap computer” -- grab and use anywhere
– arrange on a desk as you would sheets of paper
– can project onto larger “computers” with a wave of
your hand
– Write on pad, draw on it, pull up documents
Liveboards
– Larger displays: whiteboard, personalized bulletin
board, etc.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
6
Reality (2)
Some of Weiser’s H/W predictions
– Large displays, a fraction of a centimeter thick,
powered continuously for days on a small battery
(no, no, no!)
– 1GHz processors (yes, yes, yes)
– 16MB of memory on a single unit (easy, memory is
far cheaper than we could have imagined in 1991)
– Several GB of storage easily available (yes: we’ve
done better than this)
So, we’re behind in displays, batteries
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
7
What does Mobile Computing Offer?
A choice of work environments
– In your garden (but watch out for birds!)
– Coffee shops
– In the field
Remote access to important data
– Client’s office (no: "can I borrow your computer")
– Meetings (e.g., quick access to statistics, reports)
– Repair manuals, books, etc.
– Translation facilities
– In the grocery store!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
8
Offerings (2)
Electronic note-taking
While touring a new city
– Where am I? What is this building? How
do I get to Lane Avenue? I’m hungry!
Diversion
– E-books: stored, downloadable
– Games: e.g., chess, solitaire, poker
Ubiquitous communication
– email, Web
– voice
– video
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
9
What About the Toys?
A variety of computing and
more computing power
communication devices for mobile users
– Watch-sized devices (and usually a watch!)
– PDA (Personal Digital Assistants)
– Multifunction cellular phones
– Palm-sized computers
– Wearable computers
– Pads
– Notebook computers
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
(This slide courtesy of Sumi Helal @ The University of Florida)
10
Portable Information Appliances
Car Stereo-Phone
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
11
Case Study: Palm VII
Interfaces: serial, IR, 8Kb/sec Mobitex wireless
Protocols: HTTP transactions only, through Palm.net proxy
Processor: 16MHz Motorola Fireball (~ 68000 + video controller,
etc.)
Memory: 2/8MB
No expansion slots
Screen: 160x160 pixels, monochrome
Built-in applications: typical PDA (notes, calendar, etc.)
Simple character-based handwriting recognition
Runs PalmOS
Software development: C, Java, various scripting languages
Dimensions: 5.25” X 3.25” X 0.75”, 6.7oz
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
12
Palm VII
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
13
Case Study: Palm M515
Interfaces: USB, IR
Processor: Faster: 33MHz
Networking via IR or cable to a cellular phone
Memory: 16MB
Secure Digital (SD) expansion slot
Screen: 160x160 pixels, 16bit color
Built-in applications: typical PDA (notes, calendar, etc.)
Simple character-based handwriting recognition
Runs PalmOS 4.1
Software development: C, Java, various scripting languages
Dimensions: 4.5” X 3.1” X 0.5”, 4.9oz
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
14
Palm M505
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
15
Palm Accessories
~$30/each
Memory
Games
Books
Wireless LAN module ($$$$)
Portable keyboards
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
16
Handspring Visor (Palm Derivative)
cellular
“springboard” modules
for expansion
MP3 player
camera
voice recorder
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
17
Case Study: Palm Tungsten T3
Interfaces: USB, IR
Processor: 400MHz ARM-compatible
Networking via IR or cable or Bluetooth to a cellular phone
Memory: 64MB
Secure Digital (SD) expansion slot
Screen: 320x480 pixels, color
Built-in applications: typical PDA (notes, calendar, etc.)
Simple character-based handwriting recognition
Runs PalmOS 5.2.1
Software development: C, Java, various scripting languages
Dimensions: 4.3” X 3” X 0.6”, 5.5oz
Price: ~$399
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
18
Case Study: HP/Compaq IPAQ
Interfaces: USB, IR, Bluetooth, CF, Secure Digital, PCMCIA
Processor: 206+MHz StrongARM CPU
Networking via CF or PCMCIA or Bluetooth interfaces
Memory: 32MB ROM + 64MB RAM + CF or SD expansion
Screen: 320x240 pixels, 16bit color
Built-in applications: typical PDA (notes, calendar, etc.) +
Pocket Word, Excel, Internet Explorer, etc.
Character-based or script handwriting recognition
Runs Windows CE or Linux
Software development: VB, C, Java, various scripting languages
Dimensions: 5.3" x 3.3" x .62“, 6.7oz
Devices like this: $300-$1000 + lots of expansion options
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
19
Case Study: Sony VAIO Picturebook
733MHz Crusoe (Pentium-compatible)
256MB / 20GB
8.9” 1280x600 screen
Built-in digital camera, 1394 interface
¾ size keyboard
1 PCMCIA slot
Windows/Linux, etc.
~$2000 when last available
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
20
Tiny Computers
16MB 66MHz 486SX
used as a web server
See http://wearables.stanford.edu/
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
21
M1/M2 Displays
320x240 (M1, $500)
800x600 (M2, ~$5000)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
22
Wearable Computing
The inventor of wearable computing: Steve Mann.
See http://wearcam.org/mann.html
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
23
Today
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
24
Batteries Suck: Network Cables
or Power cables?
And bird poop is bad.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
25
Characteristics of Mobile Devices
Resource-poor compared to their
desktop counterparts
– Limited processing power
– Limited battery life
– Limited network connectivity
– Poor availability…they sleep a lot!
– Poor display resolution (except
notebooks)
– Tedious data input (except notebooks)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
26
Characteristics (2)
Resource poor...
– Not very expandable
• Our condolences to the landfills...
– Peripherals traded for mobility, so...
– One device typically doesn’t do it all…
• Poor compatibility between devices
• Functionality is often duplicated
• “work belt” syndrome for the mobile computing
nerd
• Bluetooth will help, but bandwidth limited
Service discovery and better device
cooperation to overcome poverty
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
27
Characteristics (3)
Limitations are a result of tradeoffs between
portability and horsepower:
– Very small size limits traditional I/O methods
• New ones: handwriting recognition, voice input
• Must work well or extreme frustration...
• Must work with other people present!!
– Batteries weigh more than any other component in
most mobile devices
• Smaller batteries, less power
• CPU speeds reduced to conserve power
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
28
Characteristics (4)
Notebook computers fare better in the
comparison with desktops because form
factor isn’t so restrictive
–
–
–
–
Reasonable screen size
Decent keyboards
Mouse substitutes
Ample memory
But even a 4lb notebook is too tedious to
carry everywhere--and too inconvenient to
use quickly
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
29
Mobile Computing Challenges
Challenges in mobile computing directly related
to the resource-poor nature of the devices…
Mobile computing isn’t a simple extension of
distributed computing
–
–
–
–
–
–
–
Hostile environment
Power-poor
Poor (or no) network bandwidth
Higher error rates
Evil for network protocols
Variable latency
built for traditional wired
Frequent disconnection
networks
Mobility
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
30
Challenges (2)
Result: Must rethink many issues; can’t just
“plug in” classic distributed systems theory
Disconnection <> Crashed!
Adaptability to deal with varying conditions
– Transcoding proxies--scale content (e.g., images)
to match available bandwidth
– Mobile proxies to convert content (e.g., Postscript
ASCII)
– Agent systems for information access
– More clever ways of checking for data consistency
– Application callbacks to monitor conditions
(network, battery power, etc.)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
31
Proxies, Proxies
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
32
Adaptation
system/application cooperation
level of application adaptability
application entirely
responsible for reacting
(or not) to
changing conditions
system entirely
responsible for reacting
(or not) to changing conditions;
“protects” application
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
33
More Challenges
Cache! Cache! Cache!
When possible, allow the risk of inconsistent data
– even if it requires human intervention to fix
Prevalent network protocols require work to give
good performance for wireless
– Schemes for mobility
– TCP hacks
Schemes for intelligent handoff between network
interfaces
– Tradeoffs between cost, bandwidth, availability
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
34
Wireless Networking
Issues:
– Technologies
•
•
•
•
What makes the bits fly?
Can we afford it?
Currently, no single technology will cut it
Handoff seems essential
– How do we run traditional applications over these
technologies?
– What works well?
– What needs more work?
WAN: Wide Area Network
MAN: Metro Area Network
LAN: Local Area Network
PAN: Personal Area Network
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
35
Wireless Networking Technologies
Satellite (WAN)
Microwave (MAN)
Broadband Wireless (MAN)
Laser (MAN)
Cellular (WAN)
Bluetooth (Wireless PAN)
IrDA (Wireless point-to-point PAN)
Wireless LANs
– 802.11 standards (e.g., Lucent WaveLAN)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
36
Global Wireless Infrastructure
Slide courtesy of Sumi Helal @ UFL
Global
Satellite
Suburban
Urban
In-Building
Micro-Cell
Macro-Cell
Pico-Cell
dik ©
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
37
Wireless: Problems
Typically much slower than wired networks
– “State of the art” wireless LAN: 54Mb/sec
– Wired LAN: 10000Mb/sec+
Higher transmission bit error rates (BER)
Uncontrolled population
Difficult to ensure Quality of Service (QoS)
Asymmetric bandwidth
Limited communication bandwidth aggravates
the problem of limited battery life
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
38
Satellite
GEO (Geosynchronous/Geostationary)
– Remains "stationary" relative to equator
– Deployed @ 36,000 km—requires a big rocket!
– Need only 3 to cover earth
– High latency (1/4 sec or so round trip)
– Need high-power transmitter to reach satellite
Arthur C. Clarke: 'How I lost a billion dollars in
my spare time‘
XM Satellite radio uses GEOs (only 2, tho)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
39
Satellite (2)
LEO (Low Earth Orbit)
– Much lower orbits—less than 1000 km
– Must have handoff mechanism—don't
appear stationary to earthbound base
stations
– Lower power transmitter than GEO
– Lower latency, but handoff delay…
– Space junk!
MEO (Middle Earth Orbit)
– ~10,000 km
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
40
Satellite: DirecPC/DirecWAY
~400Kb/sec downlink from GEO
Previously, modem uplink, but now 2-way
Dish must see the sky (typical of satellite)
Blech…169MB (1-4 hours) threshold (at last check??)
HUGE latency compared to DSL or cable modems
Last resort only!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
41
Microwave
Range: 20 miles or more, typically less
Line of sight only, point to point
Rain causes problems, because rain absorbs
microwave energy
Ethernet speeds
Ducks won't fry
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
42
Laser
High-speed systems exist: 155Mb/sec
Line of sight only, ~300m for Jolt
Relatively high cost
(One complete 155Mb/sec system for $24K,
last time I checked)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
43
Brief Survey of "Cellular"
CDPD – Cellular Digital Packet Data
– Transmit digital data over existing cellular network
– 19.2Kb/sec
– Uses idle channels in the cellular network
Mobitex – Ericsson technology
– ~8Kb/sec, fairly high latency (4-8s RTT!)
– Systems exist in US, Europe but Palm VII is US-only
– Migrating to 19.2Kb?
GSM
– Most European
– 9600bps
– Limited coverage in U.S.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
44
UMTS
Universal Mobile Telecom System
International
Initially up to 2Mb/sec
Support for IP
Quality of Service (QoS) guarantees
Enables mobile multimedia, other bandwidth-
intensive applications
Widespread deployment by 2005
See http://www.umts-forum.org for more info
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
45
Sprint PCS plans
Late 2002
2004+??
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
46
Don’t Throw Away Your DSL Yet!
Bandwidth is shared by users within a
particular cell (1-4 miles across)
For Sprint, I’m currently getting
~90Kb/sec.
Cost?
Depends on who you talk to and if the
rules hold up
$30-$100 per month for unlimited data
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
47
128Kb "Everywhere": Metricom
Ricochet by Metricom
– 128Kb/sec service in select areas
– In practice, ~70Kb ?
– Frequency-hopping system
– Shoebox-sized units mounted on street lights
– Draws power from light
– One pole-mounted unit every ¼ to ½ mile, checkerboard pattern
Rest In Peace (RIP) in 2001 but now it’s back
$75/month flat during initial lifetime, now $24.95/month flat
Modem is now free
Ricochet purchased by Aerie networks, now YDI?
Network is mostly dark, but alive again in Denver and San Diego
Cost has decreased substantially, but limited availability
~7000 customers in 2004
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
48
Wireless LANs
One example: IEEE 802.11 standard
CSMA/CA instead of CSMA/CD, as in Ethernet
Ethernet: detect collision during transmission
Wireless: impossible: can only hear own signal during
transmission
Current speeds 1Mb/sec – 54Mb/sec
Access point / NIC prices have recently dropped
substantially
802.11b: 2-11Mb/sec (we have this) in 2GHz range
802.11a: 54Mb/sec in 5GHz range (incompatible with
802.11b, very dependent on line of sight)
802.11g: ~20Mb/sec, compatible with 802.11b
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
49
802.11a Faster…but line of sight-sensitive!
Source: WWW
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
50
802.11 Details
Medium-range wireless local area network technology
2.45GHz Industrial, Scientific, Medical (ISM) Band
Old: 1Mb/sec , now: 2 - 54Mb/sec transmission speeds
Older 1Mb/sec spec used Frequency Hopping Spread Spectrum
(FHSS)
– Units change frequency rapidly according to an agreed
channel hopping sequence
– Helps to reduce interference
Higher data rates use Direct Sequence Spread Spectrum
(DSSS) Radio
– Units broadcast a broad, redundant signal that is resistant to
interference
US: 11 distinct channels (partially overlapping)
Three channels (1, 6, 11) do not overlap at all
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
51
Representative Products
Orinico (Lucent) Silver cards
– < $100
Orinoco (Lucent) Access Point
– ~ $300-700 per AP
Residential wireless routers w/o bridging
– Under $100
– No roaming, for single AP (e.g., home) deployment
Apple Airport products
– Under $150
– Newest supports streaming audio
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
52
802.11: The Big Picture
"Distribution System" == wired network
Access Point
Laptop computer
Laptop computer
Access Point
Basic Service Set (BSS) ==
area served by one access point
Laptop computer
Laptop computer
Laptop computer
Extended Service Set (ESS) == service area provided by multiple
access points
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
Or…Ad-hoc Mode
Laptop computer
Laptop computer
Laptop computer
Laptop computer
Basically, just one BSS with direct, broadcastbased communication--no access point
53
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
54
How Far? 802.11b Wavelan Specs
Environment
11Mb/sec
5.5Mb/sec
2Mb/sec
Completely
Open
Environment
525 ft
885 ft
1300 ft
Semi-open
Environment
165 ft
230 ft
300 ft
Closed (floorto-ceiling brick)
80 ft
115 ft
130 ft
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
Card/Access Point Communication:
Joining a BSS
55
Passive
Beacons from AP
(periodic synchronization transmission,
contains info to synchronize clocks,
supported data rates,
Traffic Indication Map [TIM])
Probe Request
(request for synchronization information
for a desired ESS identifier)
Active
Probe Response
(response with synchronization information)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
56
Authentication/Association
Authentication: “Always allow” or
challenge/response and/or “is your MAC
address OK?” (security issues later)
Association Request/Response:
negotiation to allow a mobile host to “join”
an access point
Reassociation disassociates with
“current” access point and moves to
another (allows roaming)
Card can listen for beacons from other
access points to determine stronger
signals
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
57
Moving Packets
Access points act as bridges that serve
their set of mobile hosts
If packet is addressed to a mobile
host that is served by this access point,
then broadcast it.
Otherwise, drop it on the “distribution system”
network for delivery to another access
point or another destination.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
58
Distributed Coordination Function
Ethernet uses CSMA/CD (Carrier Detect Multiple
Access/Collision Detection)
– Listen to medium
– If quiet, begin transmission, but listen
– If transmission is garbled, backoff and retry
Not feasible with wireless
Not all stations can hear each other!
Transmission drowns out signal of other radios
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
59
Distributed Coordination Function (2)
802.11 uses CSMA/CA (Carrier Detect
Multiple Access/Collision Avoidance)
– Wait, then listen to medium
– If quiet for specified duration, begin transmission, otherwise
wait again
– After transmission, wait for explicit ACK, if no response, wait,
retransmit
– Can also use RTS/CTS to combat hidden terminal problem
– RTS contains source, destination, duration info
– Request To Send reserves near sender, Clear To Send
reserves medium near receiver
– RTS/CTS functionality rarely used in production systems
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
60
802.11: Future
Revisions to standards for security
802.1X / 802.11i (later)
We were looking at 802.11b
802.11a: 54Mb/sec, 5GHz
802.11g: ~20Mb/sec, compatible w/ 802.11b
802.11a has more non-overlapping channels
than 802.11b
– 802.11b 3 non-overlapping channels
– 802.11a channels do not overlap
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
61
Hiperlan
European standard: Hiperlan/2
Operates in 5GHz range of 802.11a
“Problem”: 5GHz currently reserved for Hiperlan
Same access point-oriented topology as 802.11
30-50m (~90-150ft) range
~25Mb/sec peak data rate
Connection oriented—AP governs data rates, etc. so QoS
guarantees can be made (unlike 802.11)
DES/Triple DES encryption
Supports digital certificates for authentication
Time Division Multiple Access (TDMA)—units transmit in
certain slots
Info source: Hiperlan/2 Forum Whitepaper: “HiperLAN/2 – The Broadband Radio
Transmission Technology Operating in the 5 GHz Frequency Band”
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
802.11a, 802.11b, … Hiperlan
Does it matter for a particular user?
A bit.
For general purpose computing, user would need
cards for any wireless network she is likely to
encounter
At worst:
– 802.11a/b/g card for US
– Many laptops now have integrated a/b/g
– In US, 802.11b is currently the most important 802.11
protocol your devices should support
– Hiperlan for Europe??
Other differences affect applications…
E.g., no QoS in 802.11, but do have it in Hiperlan
62
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
63
Bluetooth: Goals
Provide small, inexpensive, power-
conscious radio system
Short range
Bluetooth says, “…cables! Bah!”
Personal (short-range) ad-hoc networks
Device communication and cooperation
Not really intended as a wireless LAN
technology, but it’s being used as such
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
64
Who is Bluetooth?
Danish king Bluetooth II (940-981)
Lived to a ripe old age (~ 70 years)
First baptized Danish king
Significance in this context?
The "Blue" in IBM?
– Deep Blue
– Deeper Blue
– Big Blue…
The Ericsson Scandinavian connection?
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
65
Bluetooth Hardware
Predicted long term cost: < $5/unit
(in the short term, more)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
66
Bluetooth Hardware
Low-cost radio operates in the 2.4GHz band
Maximizes international acceptance…
…except in France?!
Well…
Bluetooth ~1Mb/sec over several meters
Range can be extended with an external
power amplifier
Up to 7 simultaneous links
~75 hours voice – 3 months standby w/
600mAh battery
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
67
Bluetooth Protocol Stack
vCard, etc.
TCS
OBEX
SDP
RFCOMM
Audio
L2CAP
Baseband
Radio
LMP
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
68
The Cordless Desktop
!!!!
Ummm..no.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
69
Goodbye Cables…Hello Cooperation
X
X
Joe: 555-1287
Gotta remember to
tell the pager Joe’s
number changed...
X
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
“Send” and Forget...
70
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
71
"Last hop" Network Access
TDK's 8 node
Bluetooth Access Point
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
72
Piconets / Scatternets
piconet A
piconet B
Max eight active devices per piconet—one master
Parking allows more devices to be addressed
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
73
Bluetooth Kills Trees...
$200 for a paper copy + $50 shipping…
1500+ pages!
Quite readable, but loooooooooong!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
74
Aside: Bluetooth vs. IrDA
IrDA: Line of sight vs. omnidirectional BT
– IrDA has advantages and disadvantages
– Low-tech security for data transfer…
• E.g., business cards
– Inconvenient for Internet bridge solutions
– Connected IrDA devices must remain relatively
stationary
– Higher bandwidth than Bluetooth (4-16Mb/sec)
– Similar high-level standards (e.g., OBEX)
– But Bluetooth supports multipoint communication
– Current costs for deployment of IrDA are much
cheaper (< $2/unit)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
75
Bluetooth Device Connection States
Standby – waiting to join a piconet
Inquire – looking for other Bluetooth devices
Page – connecting to a specific device
Connected – actively involved in a piconet
Hold – power conservation state
– Internal timer runs, connection maintained
Park – power conservation state
– Connection "broken" – forgets member address,
but can be reactivated
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
76
Bluetooth States
idle
Standby
Inquiry
Connected
Park
Hold
Page
Transmit
power conservation
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
77
Bluetooth Security
Authentication
– Prevents unauthorized access to data on a
Bluetooth device
Encryption
– Secure transfers, prevent eavesdropping
Frequency Hopping
– Makes snooping more difficult...
Limited Range
– Makes snooping more obvious!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
78
Bluetooth Security (2)
Each Bluetooth device:
– 48 bit 802-style unique identifier
– 128 bit private authentication keys
– 8 to128 bit private encryption keys (configurable in
hardware)
– 128 bit random number per transaction
Radios negotiate encryption strength
No governmental restrictions on
authentication…
Encryption is a different story
Link-level security in Bluetooth authenticates
the device, not the user
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
79
Bluetooth Security (3)
Pairing installs a common secret key for
authentication
Assumes access to both devices at the
same time
Can also enter PIN at connection setup
Challenge/response for authentication
Encryption keys generated from
authentication keys
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
80
Bluetooth: Concerns
Frequencies overlap 802.11 standard
"Always on" may cause problems, worries FAA
(Take the train!)
Definitely need integration with software, not just
hardware compatibility
1Mb/sec isn't fast enough for some
applications…
…and it definitely isn’t enough to replace all
cables (monitor, USB, SCSI, etc.)
But next generation spec may hit 2-20Mb/sec
Bluetooth SDP (Bluetooth’s service discovery
protocol) isn’t very sophisticated
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
81
Wireless Networking: Systems Issues
It’s not all about the hardware
Extensions to support mobility
– Mobile IP
Wireless network protocols
– Primarily hacking TCP
– Brief review of TCP, then what breaks under
wireless
• Without mobility
• With mobility
This sets the stage..then we’ll look at
the theory behind location management
in detail
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
82
TCP/IP Issues
Application
Layer
Telnet, FTP, etc.
Transport
Layer
TCP, UDP
Network
Layer
IP
Link
Layer
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
83
Why Mobile IP?
Need a protocol which allows network connectivity
across host movement
Protocol to enable mobility must not require massive
changes to router software, etc.
Must be compatible with large installed base of IPv4
networks/hosts
Confine changes to mobile hosts and a few support
hosts which enable mobility
Just hacking DNS won’t work
– DNS updates take time
– Hooks for normal users to update DNS won’t be accepted by
administrators
– After DNS lookup, raw IP address is used by TCP, UDP, …
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
84
Mobile IP Discussion Overview
Will cover:
– Why IP routing breaks under mobility
– Mobile IPv4 basics
– Some Mobile IP security issues
Won't cover:
– Details of IP routing
– IPv6 in detail
– Low-level protocol details (message formats,
headers, etc.)
– All of the Mobile IP-related security issues
Lots more detail in the specifications
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
85
Internet Protocol (IP)
Network layer, "best-effort" packet delivery
Supports UDP and TCP (transport layer
protocols)
IP host addresses consist of two parts
– network id + host id
By design, IP host address is tied to home
network address
– Hosts are assumed to be wired, immobile
– Intermediate routers look only at network address
– Mobility without a change in IP address results in
un-route-able packets
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
86
IP Routing Breaks Under Mobility
.50
.52
.53
router
137.30.2.*
.200
router
139.20.3.*
Why this hierarchical approach? Answer: Scalability!
Millions of network addresses, billions of hosts!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
87
Mobile IP: Basics
Proposed by IETF (Internet Engineering Task
Force)
– Standards development body for the Internet
Mobile IP allows a mobile host to move about
without changing its permanent IP address
Each mobile host has a home agent on its
home network
Foreign agents on remote networks also
assist
Mobile host establishes a care-of address
when it's away from home
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
88
Mobile IP: Basics (2)
Correspondent host is a host that wants to
send packets to the mobile host
Correspondent host sends packets to the
mobile host’s IP permanent address
These packets are routed to the mobile host’s
home network
Home agent forwards IP packets for mobile
host to current care-of address
Mobile host sends packets directly to
correspondent, using permanent home IP as
source IP
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
89
Aside: IP-in-IP Tunneling
Packet to be forwarded is encapsulated in
a new IP packet
See RFC 2003 for details
In the new header:
– Destination = care-of-address
– Source = address of home agent
– Protocol number = IP-in-IP
IP header
data
IP header
IP header
data
data area
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
90
Mobile IP: Basics (3)
Home LAN
correspondent host
home agent
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
91
Protocol Messages
Extensions to ICMP
Agent advertisement
– “I’m a foreign agent…”
– “I’m a home agent”
– Agent advertisements seen by mobile hosts on
their home network welcome them back…home
Agent solicitation
– Mobile host actively seeks foreign agent
– Elicits agent advertisement message
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
92
Protocol Messages (2)
Registration Request
– Sent to home agent
– New IP address
– Flags to indicate whether broadcast traffic
should be delivered
– Security information to prevent remote
redirects/replay attacks (more soon)
Registration Reply
– ACK or an error
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
93
Mobile IP: Care-of Addresses
Whenever a mobile host connects to a
remote network, two choices:
– care-of can be the address of a foreign agent on
the remote network
• foreign agent delivers packets forwarded from
home agent to mobile host
– care-of can be a temporary, foreign IP address
obtained through, e.g., DHCP
• home agent tunnels packets directly to the
temporary IP address
Regardless, care-of address must be
registered with home agent
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
94
At the Other End...
Depending on type of care-of address:
– Foreign agent’s IP or
– Mobile host’s IP (obtained via DHCP)
… someone strips outer IP header of tunneled
packet, which is then fed to the mobile host
Decapsulation can be performed by agent or mobile
host
Aside: Any thoughts on advantages of foreign agent
vs. co-located (using foreign agent’s IP) address?
Which has less overhead for mobile host?
Which consumes fewer IP addresses (still a concern
with IPv4)?
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
95
Routing Inefficiency
Mobile host and correspondent host
might even be on the same
network!!
correspondent host
home agent
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
96
Route Optimizations
Possible Solution:
– Home agent sends current care-of address to
correspondent host
– Correspondent host caches care-of address
– Future packets tunneled directly to care-of
address
– Problems when mobile host moves…
– Care of address becomes stale, needs to be
updated
– Requires that correspondent hosts understand
Mobile-IP
– Requires security relationship between
correspondent hosts and home agent of roaming
mobile host
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
97
The Devil is in the Details...
How does the mobile host get a remote IP?
– Router advertisements, DHCP, manual...
– Agent advertisement if remote network is
Mobile-IP enabled
How can a mobile host tell where it is?
– Am I at home?
– Am I visiting a foreign network?
– Have I moved?
– One way: by listening for advertisements from
its home agents
– Presence indicates home
– Absence tends to indicate not home…
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
98
Devil (2)
Redundancy: What if the home agent doesn't answer
a registration request? Or is dead?
– Registration request to broadcast address of home network
– All available home agents will hear and reply, but will reject
service because message received via broadcast
– Error in Registration Reply (a rejection) carries new home
agent ID
– Now can request help from a specific new home agent
"Ingress" filtering
– Routers which see packets coming from a direction from
which they would not have routed the source address are
dropped
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
99
Packets Dropped: "Ingress" Filtering
Correspondent, home agent on
same network.
Packet from mobile host is deemed
"topologically incorrect“
correspondent host
home agent
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
100
Another Devil: Security Issues
We'll look at one of several security issues:
Bogus registration (denial of service)
attacks
– Malicious host sends fake registration
messages to home agent "on behalf" of the
mobile host
– Packets could be forwarded to malicious
host or to the bit bucket
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
101
Bogus Registration Attack
????
Send packets to me!!
Hehehehe!!
registration request
Madame Evil
home agent
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
102
Authentication
To fix this problem, authenticate
registration attempts
Use keyed message hashing to generate a
message digest
– MD5: see RFC 1321
Home agent generates hash using shared
private key to message to see if message
digest is identical
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
103
Authentication (2)
… care-of address…
private key
digest
???
home agent
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
104
Ooops. Replay Attacks!
home agent
captured registration is retransmitted
"…mooohahahahahahahaha!!!!!"
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
105
Avoiding Replay Attacks
Avoid replay attacks by making registration
requests unique
Add time or a pseudo-random number to
registration request/reply
If time or random number is out of sync,
provide info to resync in rejection
Insufficient information to help malicious host
Counter instead of time/random number not
as good
Would allow storing a ‘set’ of registration
requests
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
106
Random Number Avoids Replay
… care-of address +
random number...
private key
digest
???
home agent
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
107
Deployment Scenarios
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
108
Another Devil: ARP
Address Resolution Protocol
Allows hosts to broadcast an IP address and
retrieve the MAC address of the host
Home agent must perform “proxy ARP” for
registered mobile hosts that are away
Home agent must perform “gratuitous ARPs”
when mobile host leaves home network to
update ARP caches of local hosts
Mobile agent, on returning home, must issue
gratuitous ARPs for the same reason
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
109
Mobile IP: Conclusions...
Great potential for mobile application
deployment using Mobile IP
Minimizes impact on existing Internet
infrastructure
Security issues are important
(Complicated) firewall solutions proposed
Several working implementations (e.g.,
Monarch project at CMU)
Some things still need work: e.g., integration
of Mobile IP and 802.11 wireless LANs
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
110
The Most Popular Transport Protocol: TCP
TCP (Transmission Control Protocol)
–
–
–
–
–
Connection-oriented
Byte stream-oriented
Slower setup
Consumes file handles: one per connection
Flow control, automatic retransmission
• No packet reordering (delivery is FIFO)
• No packet loss
• No duplication
– Theoretically “no” limit on size of objects that
can be dumped into a TCP stream
– In practice, limits exist
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
111
Worried? Networking Background
References:
– RFC 793 (TCP)
– Network programming
• Internetworking with TCP/IP by Comer
• Unix Network Programming by Stevens
– Protocol details
• Computer Networks: A Systems Approach by
Peterson and Davie
• IBM redbook on TCP/IP (free, online)
(publib-b.boulder.ibm.com/Redbooks.nsf/RedbookAbstracts/gg243376.html?Open)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
112
More Background on TCP
TCP developed for wired, low latency networks
Full-duplex, reliable, byte-oriented (stream) protocol
Highly optimized
Adaptive retransmission to deal with varying round trip times
(RTTs), but max of 60 secs
Flow control and congestion control
– Flow control: Don’t overwhelm receiver
– Congestion control: Don’t overwhelm network
Sliding Window Protocol…
– Window sizes are variable
– Resources dedicated to a connection can vary on either side
of the connection
– Must negotiate to determine resources allocated
– Don’t want to retransmit packets that are still in transit!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
113
TCP Header Format
Source port/IP + Destination port/IP unique define TCP connection
Sequence number is for first byte of data carried in this segment
Flags: (S)YN, (F)IN, (R)ESET, (P)USH, (A)CK, (U)RGENT
PUSH == transfer w/o waiting for buffer fill (e.g., for telnet)
URGENT == allow sending urgent data “out of band”
RESET == “abort connection immediately”
Window is size of sliding window at sender of packet
Checksum provides error checking for the packet
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
114
TCP Connection Establishment
SYN (“synchronize”) indicates
connection establishment
Initial sequence number is
larger than previous sequence
numbers to prevent data from
old connections to the same
host/port from being accepted
Poor choice for initial seq #
allows nasty attacks
Final ACK establishes
connection
For connection teardown, a FIN
is transmitted by one side and
this is ACKed by the other side
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
115
Sliding Window Protocols
Sliding Window Protocols are typically
used to provide connection-oriented
communication; they naturally provide:
– Flow control
– Retransmission capability
– Buffering for out-of-order packets
Receive Window @ the receiver
Send Window @ the sender
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
116
Sliding Window: Sender
Every packet has an associated sequence number
(corresponding to first byte of data in TCP)
Send window: packets which have been transmitted but
no ACK has been received; unacknowledged packets
must be buffered
2
ACK
3
tap..tap..tap..
4
tap..tap..tap..
5
tap..tap..tap..
6
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
117
Sliding Window: Receiver
Receive window: packets receiver is willing to
receive; when the lowest numbered packet is
received, then becomes willing to accept next
packet in the sequence
Msg # 2
2
3
tap..tap..tap..
Msg # 4
5
tap..tap..tap..
6
tap...
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
118
Sliding Window: Thoughts
Flow control is guaranteed
Messages corrupted in transit are always
available at the sender for retransmission
Lost packets are retransmitted
Out of order messages are handled correctly
In TCP, windows change size—our simplified
view didn’t show this
Each ACK includes a window size
advertisement, indicating how much data the
sender can currently buffer
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
119
Naïve TCP
SENDER
Determine receiver’s
window size, adjust & send
SEND
WINDOW
RECEIVER
RECEIVE
WINDOW
Receiver’s
advertised
window size
This allows flow control: Don’t overwhelm the receiver
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
120
The Problem?
SENDER
Even after adjusting for receiver, RECEIVER
data can still overwhelm intervening
routers...packets dropped!
SEND
WINDOW
RECEIVE
WINDOW
Router
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
122
Slow Start
SENDER
Start by sending just one
segment, every time you get an
ACK, increase cwnd by one
segment
SEND
WINDOW
RECEIVER
RECEIVE
WINDOW
cwnd is
initially 1
segment
packet
Router
ACK
Results in exponential increase, despite the name...
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
123
Slow Start == Exponential Increase
SENDER
1
ACK
2
4
RECEIVER
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
124
The End of Slow Start...
SENDER
Send window cwnd doubles during
each RTT until packets are lost or a
threshold ssthresh is hit.
SEND
WINDOW
RECEIVER
RECEIVE
WINDOW
pa.c..ket
Router
ssthresh is initially 64K
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
125
Congestion Avoidance
When slow start is terminated because
cwnd exceeds ssthresh, increase cwnd by
a smaller amount on each ACK
Congestion avoidance phase increases
send window more slowly than slow start
When a packet is lost, TCP assumes it is
caused by network congestion (!)…
Then set ssthresh to cwnd / 2, set cwnd to
1, restart slow start
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
126
Fast Recovery
Two ways to detect (possible) packet loss:
– (1) Timeout
• Result: restart slow start
– (2) Duplicate ACKS
• Data must still be flowing, because out-of-order
packets are being received…
• Receiver sends duplicate of last in-order ACK
Fast recovery enters congestion avoidance
without re-starting slow start for case (2)
Attempt to keep the pipe full under moderate
congestion
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
127
What About Lost Packets?
SENDER
RECEIVER
If the receiver got packets
1,2,4,5,6,7,8,9, what does it do to get
the missing packet 3?
SEND
WINDOW
RECEIVE
WINDOW
packet
Router
ACKS
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
128
Lost/Reordered Packets...
SENDER
A round trip timer is kept, so
sender will eventually resend. But
we know what’s missing...
RECEIVE
WINDOW
SEND
WINDOW
packets
Router
ACKS
RECEIVER
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
129
Fast Retransmit
SENDER
Send another ACK for highest
in-order packet when out-oforder received...
SEND
WINDOW
RECEIVER
RECEIVE
WINDOW
ACK, ACK, ACK!!!
Router
THREE duplicate ACKs received will result in retransmission—
three to avoid possibility of just out-of-order packets
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
130
Wireless: What Breaks?
Packet loss in wired networks very low, so
assumption that
– packet loss == network congestion is valid
Not necessarily valid in wireless networks, where
error rates are higher
– packet loss can occur when the network is only
lightly loaded
– resetting size of cwnd on packet loss seriously
affects throughput
– Think: tree…tree…tree….tree…tree…tree…
– high latency makes this worse--even more time to
ramp up (because cwnd size changes only on an
ACK)!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
131
What Breaks (2)
High latency (e.g., space-bound hosts)
and handoffs can cause timers to expire
Poor use of available bandwidth when
periodic loss of service causes slow
start to be reinitiated
Asymmetric links can overwhelm the
return path, even when it's mostly
carrying ACKs
– (e.g., for satellite connections)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
132
What Breaks (3)
Problems with header compression techniques
Idea: Header compression allows sending only
changes in, e.g., a TCP header
Less overhead than transmitting full header
Problems with wireless, tho:
– Error rates higher—more likely to lose packets
– Lost packet means differential header info in subsequent
packets is unusable…
– This causes many packets to be discarded, requires
resynchronization of sender/receiver
– Reduces the usefulness of header compression
– Some recent work on fixing this problem
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
133
What Breaks (4)
Might want TCP connections to remain
open even if a host is mobile
Roaming out of range of the wireless
network to take a water sample
“Be back later” functionality
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
134
Hacking TCP for Wireless
Major concerns:
– Changes must be largely compatible with
deployed TCP implementations
– Infeasible to insist on changes to millions of
installed TCP suites
– (We saw these restrictions when considering
Mobile IP)
– Means:
• Proxies on the base stations serving mobile hosts
• Changes on the mobile end
• Negotiable changes (use TCP options)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
135
Hacking, Cont.
Can higher error rates be hidden from TCP?
Would allow assumption …
packet loss == network congestion
… to remain unchanged in TCP/IP stack
– Problem: TCP timers may go off, causing spurious
retransmission…
– 60 second rule
Now some formal solutions
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
136
Ramon Caceres paper
“Improving the Performance of Reliable Transport
Protocols in Mobile Computing Environments”
See:
http://www.cs.uno.edu/~golden/6990MC/MobilePapers/ramon1.ps
Measure performance of TCP in presence of
handoffs
2Mb/sec 802.11
Mobile-IP environment from Columbia
4.3BSD Tahoe (fast retransmit, exponential
retransmit backoff)
10Mb/sec wired network
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
137
Caceres: Testbed
Initiate TCP connections between MH (mobile host)
and SH (stationary host)
MH moves between cells
In experiments, mobility is actually handled in software—the
MH can really see both base stations, but software forces the
MH to “forget” that it can see one base and handoff to another
Much easier to setup,
as you can imagine…
Doesn’t require experimenters
to physically move equipment
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
138
Scenarios
NO HANDOFF
– Mobile unit stays in one place
– Base case
OVERLAPPING CELLS
– Mobile unit moves between access points, but remains in contact
with “old” base station until relationship with “new” is established
NON-OVERLAPPING, 0-second RENDEZVOUS DELAY
– Mobile unit loses contact with “old” base station during movement,
but does not need to wait for beacon from “new” base station
– Base case for non-overlapping coverage
NON-OVERLAPPING, 1-second RENDEZVOUS DELAY
– Mobile unit loses contact with old base station during movement
and must wait 1 second for a beacon before establishing
connection with new base station
– Base case for scattered coverage
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
139
Initial Observations
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
140
Seq #s
Connection frozen for 3 seconds!
(1 second rendezvous delay case)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
141
Congestion Window
Non-overlapping cells with 1sec rendezvous delay, movement
every 8sec
Dips are a result of the slow-start algorithm being triggered
Delays == BAD for interactive users!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
142
Idea: Force Fast Retransmit
Hack network stack to force fast retransmission immediately after
handoff is complete. Makes connection resume operation almost 0.6sec faster!!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
143
More Dramatic w/ 1sec Delay
Exponential backoff of retransmission timer can be a killer. Forcing fast
retransmit really helps for longer handoff delay.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
144
Delay Drops, Too
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
Throughput Improves…
145
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
146
Thoughts
TCP is a jumble of elegant hacks to
improve performance
Caceres paper illustrates that other very
simple, elegant hacks may offer help for
wireless
Major problem is wide deployment of
older TCP/IP stacks that can’t be
hacked
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
147
READING ROADMAP
Adaptation: Chapters 1 and 6
More location management: Chapter 2
Data dissemination: Chapter 3
Context-aware computing: Chapter 4
Mobile agents: Chapter 6
Service discovery: Chapter 7
Adaptation
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
149
Adaptation
Mobile applications must adapt to
changing resource levels to provide an
acceptable computing experience to
users
Can:
– Adapt functionality
– Adapt data
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
150
Functional Adaptation
Change the way the application
operates as resources change
Use cached copies of data instead of
making remote procedure calls against
a server
Render low resolution images rather
than relying on an (unreachable)
rendering farm
…
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
151
Data Adaptation
Change the quality or timeliness of data
streams
Higher or lower resolution video
Change bitrate of streaming audio
Use out-of-date temperature or stock
market data rather than current values
when disconnected
…
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
152
Adaptation
Odyssey is one point on this spectrum
level of application adaptability
application entirely
responsible for reacting
(or not) to
changing conditions
system entirely
responsible for reacting
(or not) to changing conditions;
“protects” application
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
153
Application-Aware Adaptation
In most cases, adaptation is application-
specific
e.g., if network bandwidth becomes scarce,
need to do different things for applications
dealing with…
–
–
–
–
–
Video
Audio
Still images
Stock quotes
individual applications (data type etc.)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
154
Application-Aware (2)
Applications are in better position to perform
needed adaptations
In client/server scenarios, may need to adapt
at both the client and server ends
Possible approaches:
–
–
–
–
–
–
Purely internal to application
Layer under application
Using special OS features and/or libraries
Use application-specific (but general purpose?) proxies
Web browsers can use last approach
Can have any sort of “adaptation” as long as an
appropriate proxy exists
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
"Agile Application-Aware …"
155
Paper:
– "Agile Application-Aware Adaptation for
Mobility"
See:
http://www.cs.uno.edu/~golden/6990MC/MobilePapers/satya3.ps
Describes the Odyssey system
Prototype that allows mobile applications to
adapt to changing conditions
– Network bandwidth
– Battery / CPU power, etc.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
156
"Fidelity"
Mobile clients may access a number of data
stores
– Databases
– WWW
– Files
Ideally, want data accessed by mobile host to
be identical to "reference" copy
Might be unrealistic
Fidelity measures degree to which copies
match
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
157
"Fidelity" (2)
Odyssey provides a framework for developing
diverse fidelity guarantees
Largely depends on type of data
– Video
• Color depth, resolution, frames per second
– Audio
• # of bits per sample, encoding scheme
– Web data
• Age: latest copy of page vs. a slightly older one
Generally, must also depend on application
Different applications may choose different
tradeoffs
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
158
"Concurrency"
Palm pilots typically execute only one
application at a time
Likely that users of more powerful mobile
computers (IPAQs, laptops) will want to run
multiple applications
Background monitoring applications
Means OS must manage network resources,
battery power, cache space, …
“All resources are not just for you!”
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
159
"Agility"
System should react quickly and accurately to
changes in availability of resources
Changes may result because of a physical
reason
– Battery is draining
– Network access is curtailed because of
interference
…or because of increased application
demands
– Additional applications are now running…
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
160
Odyssey: Goals
Allow application-aware adaptation
– Each application will decide how to adapt to changing
conditions
– Can register its interest in various resource levels
– System informs applications when resource levels deviate
from certain tolerances
Support application diversity and concurrency
– Applications decide how resource level map to fidelity levels
– Odyssey controls resource monitoring
Application can either adapt functionality or data
quality
Odyssey examples concentrate on data adaptation
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
161
Application Aware Adaptation
Wardens support type-awareness
Supporting a new type involves writing a
warden
Viceroy is responsible for centralized
resource management
application
viceroy
video warden
…
battery warden
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
162
Application Aware Adaptation (2)
Applications access resources through Odyssey…
All data to and from server flows through Odyssey
Wardens communicate with data servers, handle
caching
Applications never contact wardens directly
request() system call allows applications to express
windows of tolerance
Viceroy uses an upcall [callback] to notify application
that resource level has strayed
Application then adjust expectations, does another
request()
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
163
Adaptation Example
Video application requests enough bandwidth to
receive high resolution,15fps in color
Odyssey says “Umm, no.”
Application drops requirements to low resolution,
10fps in black and white
– Specifies both min and max bandwidth
Scenario # 1:
– Bandwidth drops
– Odyssey informs application that bandwidth has fallen
below specified limit
– Application makes another request (e.g., 3fps or still
images) or decides video isn’t feasible and informs the
user
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
164
Adaptation Example (2)
Scenario # 2:
– Bandwidth increases substantially
– Odyssey informs application that bandwidth
has risen above upper limit
– Application makes another attempt 15fps color
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
165
Odyssey Architecture (from paper)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
166
"Fidelity"
Mobile clients may access a number of data
stores
– Databases
– WWW
– Files
Ideally, want data accessed by mobile host to
be identical to "reference" copy
Might be unrealistic
Fidelity measures degree to which copies
match
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
167
Sample Applications (1)
Video Player: Xanim
– For evaluation, split into client/server
– Store three formats at server: high quality, low
quality, black and white
– Not too much magic: application calculates
bandwidth requirement
– Registers requirement,
asks for a change in
format if bandwidth
changes
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
168
Sample Applications (2)
Netscape
– More challenging, source code is not available
– Solution uses Netscape proxy facility
– Proxy interfaces with Odyssey and selects fidelity
– Web warden chooses image quality
– Multiple image formats stored on a server
Handles
different
image
formats
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
169
Odyssey: Evaluation
Experiments help determine:
– How agile is Odyssey in the face of
changing network bandwidth?
– How beneficial is it for (some) applications
to exploit the adaptation that Odyssey
offers?
Bandwidth is controlled by modifying
network stack
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
170
"Waveforms"
Increase in bandwidth
Decrease in bandwidth
Brief, sharp increase in bandwidth Brief, sharp decrease in bandwidth
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
171
Agility Measurements (1)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
172
Agility Measurements (2)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
173
Agility Measurements (3)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
174
Agility Measurements (4)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
175
Evaluation of Adaptation (1)
How much does it help?
Table below summarizes for video player
Bandwidth is always sufficient for B/W frames
Interested in lowest drop rates @ highest
fidelity
static strategies
(Numbers in parentheses are standard deviations)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
176
Evaluation of Adaptation (2)
Table below summarizes for web browser
Experiment repeatedly retrieves the same image until
time is up
Interested in best fidelity within twice Ethernet's load
time
fooled
static strategies
(Numbers in parentheses are standard deviations)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
177
More on Adaptation
Odyssey allows applications to register
interest in resource levels and adapt
accordingly
For multitasking operating systems, need
more…
When multiple applications compete for
resources:
–
–
–
–
Need prioritization of applications
Prioritization will likely require interaction w/ user
Middleware might “learn” what’s important?
Adaptation interface should allow applications to
know about existence of other competing
applications
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
178
Final Word on Adaptation
Although proxies can be used, Odyssey really
aimed at systems for which source code is
available
Other systems geared toward applications
which can’t easily be modified
e.g., Puppeteer targets applications which
provide a data manipulation API
(That is, some way to “feed” data to an
application programmatically)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
179
Final Picture on Adaptation
Location Management
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
181
Location Management (Ch2)
Fundamental ideas:
Mobile hosts (MH) are served by base stations (BS) (also
called access points (AP)
Mobile hosts can roam about the network
Mobile hosts (or other parties) must locate mobile hosts to
communicate with them
– Involves finding the base station currently serving the
mobile host
– Search operation
When a mobile host moves, must let the system know
where it is
– Update operation (also called registration)
Must allow mobile hosts to switch between base stations
to support roaming
– Handoff operation
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
182
Location Information
MH will be served by one BS at a time
BS coverage is one cell
Location information can be maintained at
various granularities
– One cell—requires MH to update location every
time it moves from one cell to another
• Tradeoff: more accurate location info vs. a large number
of updates, which may overwhelm the system
– Cell group—organize cells into groups, only
update when leaving current group
• Tradeoff: less accurate location info, which will require
paging every BS in the group, fewer updates, so less
load on the system
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
183
Tradeoffs
There will be always be tradeoffs
between cost of search and update
operations
More updates == more accurate
location info == less cost for search
Fewer updates == less accurate
location info == more cost for search
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
184
Handoff
Handoffs between BSs are required to
support roaming
There isn’t necessarily a one-to-one
correspondence between handoffs and
updates
Issues:
–
–
–
–
When to handoff?
Selecting a new BS
Allocation of resources such as channels
Informing old BS so that packets destined for MH
can be forwarded
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
185
Handoff (2)
Mobile controlled handoff
vs.
Network controlled handoff
Handoff may be necessary because:
– Mobile host is moving
– Current BS is overloaded
– Quality of communication with current BS
is poor
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
186
Handoff (3)
Choosing a new BS:
– Based on signal strength
– Base on predicted movement of MH
– Based on resources available at BS
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
187
Location Registrars
Location Registrars (LR) are databases
containing location information for MHs
Can be one or many
To get the idea, consider a system with
only one LR, a Home Location
Registrar
Location is maintained at single-cell
granularity
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
188
Single LR Scheme: Switching ON
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
189
Single LR Scheme: Handoff
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
190
Single LR Scheme: Search
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
191
Single LR Scheme: Search Failure
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
192
Enhancements to Single LR Scheme
Can add a timestamp and time-to-live to
registration information
If time-to-live expires, then location for
mobile host is assumed out of date
Can expand the search to neighboring
cells when attempting to locate a MH
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
Registration Area-Based
Location Management
193
Registration area == a group of cells; update only when crossing a registration
area boundary
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
194
Other Optimizations
Movement-based update
– Update location when MH crosses a specified
number of cell boundaries
Distance-based update
– Update location when MH moves a specified
distance away from the last point of update
Forwarding pointers
– When maintaining multiple location registrars, use
a chain of forward pointers to track the MH
Replication of location registrars
– Flat
– Hierarchical
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
195
Flat Replication
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
196
Hierarchical Replication
Non-leaf nodes cache all info in attached subtrees
Data Dissemination
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
198
Communications Asymmetry
Network asymmetry
– In many cases, downlink bandwidth far exceeds
uplink bandwidth
Client-to-server ratio
– Large client population, few servers
Data volume
– Small requests for info, large responses
– Again, downlink bandwidth more important
Update-oriented communication
– Updates likely affect a number of clients
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
199
Disseminating Data to Wireless Hosts
Broadcast-oriented dissemination
makes sense for many applications
Can be one-way or with feedback
– Sports
– Stock prices
– New software releases (e.g., Netscape)
– Chess matches
– Music
– Election Coverage
– Weather…
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
200
Dissemination: Pull
Pull-oriented dissemination can run into
trouble when demand is extremely high
– Web servers crash
– Bandwidth is exhausted
client
client
client
server
client
client
client
client
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
201
Dissemination: Push
Server pushes data to clients
No need to ask for data
Ideal for broadcast-based media (wireless)
client
client
client
server
client
client
client
client
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
202
Broadcast Disks
2
3
1
4
5
6
Schedule of data blocks
to be transmitted
server
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
203
Broadcast Disks: Scheduling
2
3
1
Round Robin Schedule
4
5
6
1
2
1
Priority Schedule
1
3
1
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
204
Priority Scheduling (2)
Random
– Randomize broadcast schedule
– Broadcast "hotter" items more frequently
Periodic
Allows mobile hosts to sleep…
– Create a schedule that broadcasts hotter items more
frequently…
– …but schedule is fixed
– "Broadcast Disks: Data Management…" paper uses
this approach
– Simplifying assumptions
• Data is read-only
• Schedule is computed and doesn't change…
• Means access patterns are assumed the same
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
205
"Broadcast Disks: Data Management…"
Order pages from "hottest" to coldest
Partition into ranges ("disks")—pages in a range
have similar access probabilities
Choose broadcast frequency for each "disk"
Split each disk into "chunks"
– maxchunks = LCM(relative frequencies)
– numchunks(J) = maxchunks / relativefreq(J)
Broadcast program is then:
for I = 0 to maxchunks - 1
for J = 1 to numdisks
Broadcast( C(J, I mod numchunks(J) )
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
206
Sample Schedule, From Paper
Relative frequencies
4 2
1
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
207
Broadcast Disks: Research Questions
From Vaidya:
– How to determine the demand for various
information items?
– Given demand information, how to
schedule broadcast?
– What happens if there are transmission
errors?
– How should clients cache information?
• User might want data item immediately after
transmission…
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
208
Hot For You Ain't Hot for Me
Hottest data items are not necessarily the ones
most frequently accessed by a particular client
Access patterns may have changed
Higher priority may be given to other clients
Might be the only client that considers this data
important…
Thus: need to consider not only probability of
access (standard caching), but also broadcast
frequency
A bug in the soup: Hot items are more likely to be
cached! (Reduce their frequency?)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
209
Broadcast Disks Paper: Caching
Under traditional caching schemes, usually
want to cache "hottest" data
What to cache with broadcast disks?
Hottest?
Probably not—that data will come around
soon!
Coldest?
Ummmm…not necessarily…
Cache data with access probability
significantly higher than broadcast frequency
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
210
Caching, Cont.
PIX algorithm (Acharya)
Eject the page from local cache with the
smallest value of:
probability of access
broadcast frequency
Means that pages that are more frequently
accessed may be ejected if they are
expected to be broadcast frequently…
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
211
Broadcast Disks: Issues
User profiles
– Provide information about data needs of particular
clients
– "Back channel" for clients to inform server of needs
– Either advise server of data needs…
– …or provide "relevance feedback"
Dynamic broadcast
– Changing data values introduces interesting
consistency issues
– If processes read values at different times, are the
values the same?
– Simply guarantee that data items within a particular
broadcast period are identical?
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
212
Hybrid Push/Pull
"Balancing Push and Pull for Data
Broadcast" (Acharya, et al SIGMOD '97)
"Pull Bandwidth" (PullBW) – portion of
bandwidth dedicated to pull-oriented
requests from clients
PullBW = 0%
"pure" Push
Clients needing
a page simply wait
PullBW = 100%
Schedule is totally request-based
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
213
Interleaved Push and Pull (IPP)
Mixes push and pull
Allows client to send requests to the server for
missed (or absent) data items
Broadcast disk transmits program plus requested
data items (interleaved)
Fixed threshold ThresPerc to limit use of the
back channel by a particular client
Sends a pull request for p only if # of slots before
p will be broadcast is greater than ThresPerc
ThresPerc is a percentage of the cycle length
Also controls server load–as ThresPerc 100%,
server is protected
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
214
CSIM-based Simulation
Measured Client (MC)
– Client whose performance is being measured
Virtual Client (VC)
– Models the "rest" of the clients as a single entity…
– …chewing up bandwidth, making requests…
Assumptions:
– Front channel and back channel are independent
– Broadcast program is static—no dynamic profiles
– Data is read only
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
215
Simulation (1)
No feedback to clients!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
216
Simulation (2)
Can control ratio of VC to MC requests
Noise controls the similarity of the access
patterns of VC and MC
Noise == 0 same access pattern
PIX algorithm is used to manage client cache
VC's access pattern is used to generate the
broadcast (since VC represents a large
population of clients)
Goal of simulation is to measure tradeoffs
between push and pull under broadcast
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
217
Simulation (3)
CacheSize pages are maintained in a local
cache
SteadyStatePerc models the # of clients in
the VC population that have “filled” caches—
e.g., most important pages are in cache
ThinkTimeRatio models intensity of VC
request generation relative to MC
ThinkTimeRatio high means more activity on
the part of virtual clients
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
218
Simulation (4)
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
219
Experiment 1: Push vs. Pull
At PullBW = 10%, reduction in bandwidth hurts push, is insufficient for pull requests!
server death!
Light loads: pull better
Important! PullBW set at 50% in 3a – if
server's pull queue fills, requests are dropped!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
220
Experiment 2: Cache Warmup Time for MC
Low server load: pull better.
High server load: push better.
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
221
Experiment 3: Noise: Are you (VC) like
me (MC)?
!!!
On the left, pure push vs. pure pull.
On the right, pure push vs. IPP
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
222
Experiment 4: Limiting Greed
On the other hand…
If there’s plenty of bandwidth, limiting greed isn’t a good idea
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
223
Experiment 5: Incomplete Broadcasts
Server overwhelmed—requests are being dropped!
Not all pages broadcast—non-broadcast pages must be explicitly pulled
Lesson: Must provide adequate bandwidth or response time will suffer!
In 7b, making clients wait longer before requesting helps…
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
224
Incomplete Broadcast: More
Lesson: Careful! At high server loads with lots of pages not
broadcast, IPP can be worse than push or pull!
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
225
Experimental Conclusions
Light server load: pull better
Push provides a safety cushion in case a pull request is
dropped, but only if all pages are broadcast
Limits on pull provide a safety cushion that prevents the
server from being crushed
Broadcasting all pages can be wasteful
But must provide adequate bandwidth to pull omitted
pages…
Otherwise, at high load, IPP can be worse than pull!
Overall: Push and pull tend to beat IPP in certain
circumstances
But IPP tends to have reasonable performance over a wide
variety of system loads…
Punchline: IPP a good compromise in a wide range of
circumstances
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
226
Mobile Caching: General Issues
Mobile user/application issues:
– Data access pattern (reads? writes?)
– Data update rate
– Communication/access cost
– Mobility pattern of the client
– Connectivity characteristics
• disconnection frequency
• available bandwidth
– Data freshness requirements of the user
– Context dependence of the information
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
227
Mobile Caching (2)
Research questions:
– How can client-side latency be reduced?
– How can consistency be maintained among all caches and
the server(s)?
– How can we ensure high data availability in the presence of
frequent disconnections?
– How can we achieve high energy/bandwidth efficiency?
– How to determine the cost of a cache miss and how to
incorporate this cost in the cache management scheme?
– How to manage location-dependent data in the cache?
– How to enable cooperation between multiple peer caches?
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
228
Mobile Caching (3)
Cache organization issues:
– Where do we cache? (client? proxy? service?)
– How many levels of caching do we use (in the case of
hierarchical caching architectures)?
– What do we cache (i.e., when do we cache a data item and
for how long)?
– How do we invalidate cached items?
– Who is responsible for invalidations?
– What is the granularity at which the invalidation is done?
– What data currency guarantees can the system provide to
users?
– What are the (real $$$) costs involved? How do we charge
users?
– What is the effect on query delay (response time) and
system throughput (query completion rate)?
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
229
Weak vs. Strong Consistency
Strong consistency
–
–
–
–
–
Value read is most current value in system
Invalidation on each write can expire outdated values
Disconnections may cause loss of invalidation messages
Can also poll on every access
Impossible to poll if disconnected!
Weak consistency
– Value read may be “somewhat” out of date
– TTL (time to live) associated with each value
Can combine TTL with polling
e.g., Background polling to update TTL or retrieval of
new copy of data item if out of date
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
230
Disconnected Operation
Disconnected operation is very desirable for
mobile units
Idea: Attempt to cache/hoard data so that
when disconnections occur, work (or play)
can continue
Major issues:
–
–
–
–
What data items (files) do we hoard?
When and how often do we perform hoarding?
How do we deal with cache misses?
How do we reconcile the cached version of the
data item with the version at the server?
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
231
One Slide Case Study: Coda
Coda: file system developed at CMU that
supports disconnected operation
Cache/hoard files and resolve needed
updates upon reconnection
Replicate servers to improve availability
What data items (files) do we hoard?
– User selects and prioritizes
– Hoard walking ensures that cache contains the
“most important” stuff
When and how often do we perform
hoarding?
– Often, when connected
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
232
Coda (2)
(OK, two slides)
How do we deal with cache misses?
– If disconnected, cannot
How do we reconcile the cached version of the data
item with the version at the server?
–
–
–
–
When connection is possible, can check before updating
When disconnected, use local copies
Upon reconnection, resolve updates
If there are hard conflicts, user must intervene (e.g., it’s
manual—requires a human brain)
Coda reduces the cost of checking items for
consistency by grouping them into volumes
If a file within one of these groups is modified, then
the volume is marked modified and individual files
within can be checked
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
233
WebExpress
Housel, B. C., Samaras, G., and Lindquist, D. B., “WebExpress:
A Client/Intercept Based System for Optimizing Web Browsing
in a Wireless Environment,” Mobile Networks and Applications
3:419–431, 1998.
System which intercepts web browsing, providing sophisticated
caching and bandwidth saving optimizations for web activity in
mobile environments
Major issues:
–
–
–
–
–
Disconnected operation
Verbosity of HTTP protocol Perform Protocol Reduction
TCP connection setup time Try to re-use TCP connections
Low bandwidth in wireless networks Caching
Many responses from web servers are very similar to those seen
previously Use differencing rather than returning complete
responses, particularly for CGI-based interactions
Slides © Prof. Golden G. Richard III, Department of Computer Science, University of New Orleans, 2004
234
WebExpress (2)
Reduce redundant
HTTP header info
One TCP connection
Reinsert removed
HTTP header info on server side
Caching on both client and on wired network + differencing
Two intercepts: both on client side and in the wired network
END OF SET # 1
MIDTERM REVIEW Oct 14
MIDTERM EXAM Oct 19