Transcript mobicom_04

Interesting Papers from Mobicom ’04
Vivek Raghunathan
Mobicom ’04
27 papers, 3 days
Paper distribution




15-16 systems (6-7 experimental)
5-6 theory
3 measurement
3 sensor network
I’ll focus on the systems papers in this
talk
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing (Baratto etal, Columbia)
Goal




Use network to decouple user’s desktop
computing session from end-user device
All application logic is moved to hosting providers
End-user devices are dumb devices that accept
user input and display application output
Desktop session is decoupled from hosting server
so that session can be migrated from one server
to another
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Benefits





High availability and reliable application
services
Persistence and continuity of business logic
Transparent user mobility
On-demand access to
application/computational resources
Simple end-user devices may bridge the
gap between haves and have-nots
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Architecture overview



Layer 7 proxy exposes a single entry point to
clients
Users access a completely private and mobile
environment using a thin-client session viewer
MobiDesk virtualizes three resources
 Display
 Operating system
 Network
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Display virtualization


Virtual display driver intercepts display
commands at video hardware layer and
instead sends them over the network to a
remote client
Allows reuse of higher level display level
functionality, as in Xfree86
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Display virtualization

Client hardware resources are exported to the
server and used if possible to reduce latency
 Direct video support
 Cursor drawing support

Latency reduction techniques
 Server push
 Display command scheduling

All client state is soft; all session state is stored at
the respective session server
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Operating system virtualization


Session can be isolated from system,
check-pointed to storage, migrated to
another server and transparently restarted
Each session gets its own virtual private
namespace
 Virtual: all OS resources are accessed through
virtual identifiers
 Private: only processes within session can see
the namespace
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
OS virtualization: session virtualization


Virtualization layer associated a virtual
name with the OS physical name
Traps all calls to OS and translates names
 System call interposition: wrappers around
system calls that translate virtual names to
physical names and prevent accesses across
the session boundary
 chroot and file system stacking to provide each
session with its own file system namespace
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Network virtualization

Issues
 Multiple sessions on the same server may run
the same service
 Ongoing network connections must be
preserved when a session is migrated from one
server to another
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Network virtualization

All servers on same subnet
 each session gets an IP address from the DHCP
server and uses it as an alias on the NIC on the
attached server
 Gratuitous ARP is used to resolve MAC address
change when sessions are migrated
 Proxy re-directs traffic to and from aliased
addresses corresponding to individual sessions
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Network virtualization

Servers on different subnets
 Cannot migrate an aliased address obtained in one
subnet to another (INCONSISTENCY)

Solution: use virtual addresses for proxy mapping and map
these virtual addresses to physical (aliased) addresses
dynamically at the proxy
 The aliased address may be reused in old subnet,
confusing the proxy (CONFLICT)

Solution: each session is bound to a different virtual NIC at
the proxy, and labels in packets are used to identify the
virtual NIC to which the session is bound
Vivek Raghunathan <raghnthn at uiuc dot edu>
MobiDesk: Mobile Virtual Desktop
Computing
Evaluation summary




OS virtualization overhead is negligible except for
ioctl and semget/semctl
Network virtualization overhead is negligible
Display performance of MobiDesk is impressive
compared to Sunray, Citrix, VNC etc. (full motion
video)
All tests run on a high-bandwidth network (even
WAN has 100Mbps bandwidth)
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks (Adya etal, MSR)
Faults in wireless networks




Connectivity problems (RF holes)
Performance problems (ISM band
interference)
Network security (Rogue AP problem)
Authentication problems (missing/expired
IEEE 802.1x certificates)
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks
Requirements




Clients can run monitoring software
Clients can start an infrastructure network
or an ad hoc network of their own
(Atheros, Native Wi-Fi)
A central database keeps track of all AP
locations
Client and AP density is quite high
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks
Architecture

Diagnostic Client (DC)
 Runs on wireless clients
 Monitors RF environment, traffic flow
 Helps disconnected client, performance isolation

Diagnostic AP (DAP)
 Merge DC data and forward to DS
 Offload work from DS

Diagnostic Server (DS)
 Diagnose global faults
 Detect rogue AP
 Locate disconnected client
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks
Client Conduit

Mechanism to diagnose a disconnected
client using a nearby connected client as a
gateway
 Could use MultiNet all the time and take the
performance hit
 Instead use IEEE 802.11 beaconing to detect
problem and start MultiNet only when needed
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks
Client Conduit





DC on D goes promiscuous and scans for a client connected
to infrastructure and starts an AP on the same channel
Newly formed AP at D broadcasts beacon
SOS_HELP_<num> like a regular AP
On hearing SOS_HELP_<num> beacon, C uses IEEE 802.11
active scanning to send a Probe Request of the form
SOS_ACK_<num>:
 Stays connected to infrastructure while doing this
 Informs D that C has heard the request.
When D hears Probe Request, it stops sending
SOS_HELP_<num> beacons and instead sends a Probe
Response to C indicating that it would like to use C
D starts an ad hoc network and C uses MultiNet to join it.
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks
Locating disconnected clients



If client hears no beacons, it becomes an AP and
starts beaconing
Nearby clients measure RSSI of beacons and
inform DS
DS uses a two-step procedure:
 locates nearby clients using AP location information and
RSSI measurements from nearby clients
 Locates disconnected client using RSSI from it and
location information of nearby client
 Location error is around 10-12 meters
Vivek Raghunathan <raghnthn at uiuc dot edu>
Architecture and Techniques for
Diagnosing Faults in IEEE 802.11
Infrastructure Networks
Performance monitoring



Monitor TCP RTT, loss rate
Isolate wireless from wired
Diagnose wireless network problems
Rogue AP detection


Detect compliant APs
DC uses active scanning to detect all APs
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning (Badrinath etal, Rutgets)
Borrowed from the presentation at
http://www.winlab.rutgers.edu/pub/doc
s/iab/2004Spring/16_Niculescu_Dragos.
pdf
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning
Existing indoor positioning systems:

Extra infrastructure (Active Badge)
 good accuracy
 specialized badges/beacons, LOS

Signal strength map (RADAR)
 Works with IEEE 802.11 Aps
 Centralized database
 Have to construct SS map off-line
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning
RADAR (MSR)


Build SS map by measuring signal strength
from each point in the building to five base
stations
When a node moves, base stations use
measured SS to query the centralized
database for the nearest match
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning
Goals



No SS map
Move complexity to the 802.11 base
station
Use
 Angles
 Ranges
 Angles and Ranges
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning
Idea: from VOR (VHF Omnidirectional
Ranging) used for navigation in aircraft
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning
Idea
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning
Experimental setup
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning
Angles only positioning
Vivek Raghunathan <raghnthn at uiuc dot edu>
VOR Base Stations for Indoor 802.11
Positioning
Issues with angles only positioning


With multiple peaks: which direction is the peak
direction?
90% of time, it is the strongest or second
strongest peak
Use range based trilateration to augment the
angles only positioning


Correlate measured SS with distance using limited
SS map (unlike RADAR)
Achieves 2.1m – 4m median error, comparable to
RADAR
Vivek Raghunathan <raghnthn at uiuc dot edu>
Denial of Service Resilience in Ad Hoc
Wireless Networks (Hubaux etal, EPFL)
DOS attacks in wireless networks

Jellyfish: protocol compliant, attacks
congestion control
 Jellyfish Reorder Attack
 Jellyfish Periodic Drop Attack
 Jellyfish Delay Variance Attack


Black hole attack: not protocol compliant
Both reduce throughput to zero
Vivek Raghunathan <raghnthn at uiuc dot edu>
Denial of Service Resilience in Ad Hoc
Wireless Networks
Jellyfish Reorder Attack
Vivek Raghunathan <raghnthn at uiuc dot edu>
Denial of Service Resilience in Ad Hoc
Wireless Networks
Jellyfish Periodic Drop Attack
Vivek Raghunathan <raghnthn at uiuc dot edu>
Denial of Service Resilience in Ad Hoc
Wireless Networks
DOS increases wireless network capacity!
Vivek Raghunathan <raghnthn at uiuc dot edu>
Denial of Service Resilience in Ad Hoc
Wireless Networks
Attack detection using neighbor information
(Passive ACKs) does not work


Directional antennas
Power control
Need an end-to-end approach


Detect new routes disjoint from bad routes
Use probabilistic routing over multiple paths
Diagnosis timescale of the order of multiple
RTTs
Vivek Raghunathan <raghnthn at uiuc dot edu>
Denial of Service Resilience in Ad Hoc
Wireless Networks
TCP Reorder attack


TCP assumes in-order delivery while IP does not
guarantee that
Solutions:
 Receiver: delay the DUPACK timer
 Sender: wait for a higher number of DUPACKs before
triggering congestion control

Maybe we need to do away with congestion
control using DUPACKs to detect loss … (modified
TCP SACK?)
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks (Padhye etal, MSR)
Shortest-path is not always the best
path (MIT Roofnet)
lossy link
good link



good link
Link characteristic is not ON-OFF
Links have i.i.d. packet loss
A few HELLO packets get through and the
lossy 1-hop path.
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
ETX metric for a link = expected
number of retransmissions on that link
 Successful packet transmission = DATA + ACK
 Measure packet loss rate pf, pr using broadcast
packets
 Then,

ETX = 1/[1 – (1- pf).(1-pr)]
ETX metric for a path = sum of ETX
metrics for links along the path
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
ETX and multiple radios


ETX does not consider bandwidth while
selecting paths, so it will choose 802.11b
over 802.11a if the loss rates are the same
(longer range 802.11b links).
ETX does not give any preference to
“channel-diverse” paths (more on this
later)
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Idea: if we use multiple radios at every node,




node can simultaneously transmit and receive
node can simultaneously transmit on multiple
channels
“self-interference” in routes can be reduced
can improve robustness to channel variation, noise
by using different parts of the spectrum
(802.11a/b)
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Model

Stationary nodes with one or more radios tuned
to different non-interfering channels
Design goals for a new path metric
1.
2.
3.
Takes bandwidth and loss rates on each link into
account
Adding a link to the path does not decrease the
path metric
Explicitly accounts for reduction in throughput
due to interference among links that operate on
the same channel
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Suppose we know ETTi = expected
transmission time on a link.
ETTi takes the bandwidth and loss rate on
the link into
account (Property 1)
n
WCETT   ETT i



i 1
Adding a link to the path increases the
metric (Property 2)
Does not distinguish between hops on
different channels (no Property 3)
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Instead, define for channel j,
Xj 
 ETT
i
i on channel j
Path throughput is dominated by the
bottleneck channel, i.e. by max Xj
Consider WCETT = max Xj


As more hops are added, the path metric may stay
the same (weak Property 2)
Metric favors channel-diverse paths (Property 3)
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Combine both the metrics using a
tunable parameter 
n
WCETT  (1 -  )* ETT i  * max Xj
i 1
ETT = ETX * S/B, where S = size of
packet and B = bandwidth of link
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Other issues


How to measure bandwidth if IEEE 802.11
autorate is being used? (packet-pairs)
Broadcasts sent at 1Mbps, so loss rate may
not correspond to actual unicast packet
loss
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Implementation summary



Implemented on top of LQSR, a link-state
source routed protocol
Layer 2 routing: higher layers only see a
single virtual device
All higher layer stuff (arp, broadcast) works
unmodified
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Evaluation summary



In single radio environments, WCETT
provides 15-20% improvement over ETX
In two radio environments, provides a
factor of two improvement over ETX
Does well!
Vivek Raghunathan <raghnthn at uiuc dot edu>
Routing in Multi-Radio Multi-Hop Wireless
Mesh Networks
Open issues



Channel diversity metric merely takes into
account number of links on a particular
channel, while the position of those links
could be significant.
Jointly select channels dynamically +
multiple radio routing
WCETT + distance vector
Vivek Raghunathan <raghnthn at uiuc dot edu>
SSCH: Slotted Seeded Channel Hopping in
IEEE 802.11 Ad-Hoc Wireless Networks
(Chandra, MSR)
Vivek Raghunathan <raghnthn at uiuc dot edu>
SSCH: Slotted Seeded Channel Hopping
for Capacity Improvement in IEEE 802.11
Ad-Hoc Wireless Networks
Goal

Use frequency diversity to improve wireless
network capacity
Assumptions




One radio per node
In any particular channel, IEEE 802.11 is used
Traffic patterns (flow start/end) change less
frequently than hopping schedules are propagated
Should not cause logical partition, i.e., nodes in
communication range are unable to communicate
Vivek Raghunathan <raghnthn at uiuc dot edu>
SSCH: Slotted Seeded Channel Hopping
for Capacity Improvement in IEEE 802.11
Ad-Hoc Wireless Networks
Idea



Nodes are aware of each others channel
hopping schedules
However, any node can change its
schedule at any time
Node A with traffic to send to node B
changes its schedule to synchronize with
node B in the common case where
schedule is available.
Vivek Raghunathan <raghnthn at uiuc dot edu>
SSCH: Slotted Seeded Channel Hopping
for Capacity Improvement in IEEE 802.11
Ad-Hoc Wireless Networks
Packet scheduling




Packets are maintained in per-neighbors
FIFOs
FIFOs kept in a priority queue based on
perceived neighbor reachability
Transmissions are attempted in a roundrobin manner among all flows
If transmission to a neighbor fails, the flow
is reduced in priority
Vivek Raghunathan <raghnthn at uiuc dot edu>
SSCH: Slotted Seeded Channel Hopping
for Capacity Improvement in IEEE 802.11
Ad-Hoc Wireless Networks
Packet scheduling

Broadcast = repeated retransmissions on
different channels (nearly 6)
 Does this change the semantics (a neighbor
could get a broadcast packet twice …)
 Protocols that use broadcast to synchronize fail
Vivek Raghunathan <raghnthn at uiuc dot edu>
SSCH: Slotted Seeded Channel Hopping
for Capacity Improvement in IEEE 802.11
Ad-Hoc Wireless Networks
Channel scheduling



4 (channeli, seedi) pairs – one per slot
Slots repeat as slot 1, slot 2, slot 3, slot 4, slot 1,
slot 2, …
In slot i, channeli is used, and then channeli is
updated using the seed
 channeli = (channeli + seedi mod 13)



After 4*13 slots, a parity slot with channel = seed1
is used.
Slot time = 10ms = 35 max length packet tx times
Nodes exchange their schedules periodically in
broadcast packets once per slot
Vivek Raghunathan <raghnthn at uiuc dot edu>
SSCH: Slotted Seeded Channel Hopping
for Capacity Improvement in IEEE 802.11
Ad-Hoc Wireless Networks
Channel scheduling details



Nodes attempt to synchronize their slots to their
neighbors (loose synchronization)
Nodes change their schedule to overlap nodes for
which they have traffic
Need to be careful since we also want to receive
packets – use a heuristic
 Receiving slot = slot that receives more than 10 packets
during previous iteration
 If some slots are receiving and some not, then change
schedule by changing a non-receiving slot
 De-synchronization to reduce congestion
Vivek Raghunathan <raghnthn at uiuc dot edu>
SSCH: Slotted Seeded Channel Hopping
for Capacity Improvement in IEEE 802.11
Ad-Hoc Wireless Networks
Evaluation summary



Single hop UDP: SSCH leads to improvement over
IEEE 802.11a by a factor of 4 when number of
flows is high
Single hop TCP: SSCH delay jitter affects TCP
performance, but as number of flows increases,
outperforms IEEE 802.11a
Multi hop: DSR over SSCH chooses longer routes
because of broadcast problem, but still improves
performance
Vivek Raghunathan <raghnthn at uiuc dot edu>
Fairness and Load Balancing in Wireless
LANs using Association Control
(Bejerano etal, Bell Labs)
Model






A = set of m access points
U = set of n quasi-static users
For user r, access point a, rau = effective average
bit rate at which they can communicate
For each access point a, Ra = rate at which it can
communicate with the infrastructure
User u has weight wu
Users are greedy
Vivek Raghunathan <raghnthn at uiuc dot edu>
Fairness and Load Balancing in Wireless
LANs using Association Control
Problem



We wish to associate the users to the access
points in order to satisfy some optimality criterion
Centralized solution
Two kinds of association
 (Idealized) fractional association: users can associate
with multiple access points
 Integral association: users can only associate with a
single access point
Vivek Raghunathan <raghnthn at uiuc dot edu>
Fairness and Load Balancing in Wireless
LANs using Association Control
Problem


Bandwidth allocation bau specifies average
bandwidth allocated to user u by AP a.
Optimality criterion
 Max-min fairness: in the bandwidth received by
a user (normalized by its weight)
 Min-max load balancing: in the load
Vivek Raghunathan <raghnthn at uiuc dot edu>
Fairness and Load Balancing in Wireless
LANs using Association Control
Fairness group = users with the same
normalized bandwidth allocation
Load group = access points with the same
(scaled) load
Max-min fairness => all users served by an
AP belong to the same fairness group
Min-max load balancing => all access points
serving a user have the same load
Vivek Raghunathan <raghnthn at uiuc dot edu>
Fairness and Load Balancing in Wireless
LANs using Association Control
Main Theorem

In the fractional association case, a minmax load balanced association defines a
max-min fair bandwidth allocation and vice
versa
Vivek Raghunathan <raghnthn at uiuc dot edu>
Fairness and Load Balancing in Wireless
LANs using Association Control
Fractional association control for greedy
users
Vivek Raghunathan <raghnthn at uiuc dot edu>
Fairness and Load Balancing in Wireless
LANs using Association Control
Bottleneck detection(A, U)



Use a linear program LP1 to calculate an
association that minimizes the maximal load Y on
all APs
Use another linear program LP2 to minimize the
sum of load on all APs given bottleneck load Y (to
determine which APs are in the bottleneck load
group)
Build a directed graph representing whether load
can be shifted from one AP to another and use it
to determine bottleneck load group
Vivek Raghunathan <raghnthn at uiuc dot edu>
Fairness and Load Balancing in Wireless
LANs using Association Control
Integral association control for greedy
users


Problem is NP-hard
Use a rounding method to generate an
integral association from the fractional
association
 2-approximation algorithm for unweighted
users
 3-approximation algorithm for weighted users
Vivek Raghunathan <raghnthn at uiuc dot edu>
Other papers
Measurement

Wireless wide-area networks (GPRS) performance
(Computer Lab, Cambridge)
 Benchmark application performance
 Examine performance optimizations at every layer of the
stack




HTTP (content compression, pipelining GETs)
Session (varying number of TCP connections, server-side
push)
Transport layer (TCP-WWAN)
Link layer
Vivek Raghunathan <raghnthn at uiuc dot edu>
Other papers
Measurement

Changing Usage of a Mature Campus-Wide
Wireless Network (David Kotz, Dartmouth)
 566 APs, 7000 users, 17 weeks, same SSID
 188 buildings with APs, 115 subnets, same
SSID
 Trace collection: snmp, Ethernet sniffers, VoIP
CDR, syslog, p0f for OS detection,
 No authentication/encryption anywhere
Vivek Raghunathan <raghnthn at uiuc dot edu>
Other papers
Localization

Practical Robust Localization over Large-Scale
802.11 (Haeberlen etal, Rice)
12000 sq. m
Granularity at the office-room/corridor level, 512 cells
28 man-hours of data collection (2 minutes per region)
Signal intensities at each base station fitted to a
Gaussian (works well in practice)
 Use Markov localization
 95% correct location
 Cool demo!




Vivek Raghunathan <raghnthn at uiuc dot edu>