Transcript CS219: Advanced Topics in Internet Research

Overview of Wireless
Networking
• Wireless Link Characteristics
• Services and Applications
Overview
• Fundamental issues and impact
– wireless
– mobility
• For each layer in the protocol stack
– A subset of design requirements
– Design challenges/constraints
– Possible design options
Wireless Channel Characteristics
• Radio propagation
– Multipath, fade, attenuation, interference &
capture
– Received power is inversely proportional to the
distance: distance-power gradient
• Free space: factor 2
• Inbuilding corridors or large open indoor
areas: <2
• Metal buildings: factor 6
• Recommended simulation factors: 2~3 for
residential areas, offices and manufacturing
floors; 4 for urban radio communications
Wireless Channel
• Wireless transmission is error prone
• Wireless error and contention are
location dependent
• Wireless channel capacity is also
location dependent
Link-Level Measurements
• Measurements taken from 802.11b-based
MIT Roofnet
• Focus:
– Explore reasons for loss
– mainly on long outdoor links
Roofnet: multihop wireless mesh
1 kilometer
Using omni-direction antenna
+ Easy to deploy
+ Provide high
connectivity
- Don’t allow
engineered link
quality
Lossy radio links are common
Broadcast packet
delivery probability
70-100%
30-70%
1-30%
1 kilometer
Broadcast Packet
Delivery Probability
Delivery prob. uniformly distributed
> two-thirds of links
Node Pair
deliver less
than 90%
Implications
Protocols should exploit intermediate-quality
links
• Link-quality-aware routing (ETX, LQSR)
• 802.11 transmit bit-rate selection
• Multicast data distribution
• Opportunistic protocols (OMAC, ExOR)
• An emerging research direction
Hypotheses for intermediate
delivery probability
1.
2.
3.
4.
Marginal signal-to-noise ratios
Interference: Long bursts
Interference: Short bursts (802.11)
Multi-path interference
Methodology: Link-level
measurements of packet loss
•
•
•
•
Goal: all-pairs loss rates
Each node broadcasts for 90 seconds
All other nodes listen
Raw link-level measurements:
– No
– No
– No
– No
ACKs, retransmissions, RTS/CTS
other Roofnet traffic
802.11 management frames
carrier sense
Hypothesis 1: Marginal S/N
• Simplified model for packet loss:
– P(delivery) = f(signal/noise)
– Signal strength reflects attenuation
– Noise reflects interference
• Perhaps marginal S/N explains
intermediate delivery probabilities
Broadcast packet
delivery probability
Delivery vs. S/N with a cable
and attenuator
Laboratory
Signal-to-noise ratio (dB)
Broadcast packet
delivery probability
Delivery vs. S/N on Roofnet
Laboratory
Roofnet
Signal-to-noise ratio (dB)
S/N does not predict delivery probability
for intermediate-quality links
Hypothesis 2: long bursts of
interference
A
B
Bursty noise might corrupt packets
without affecting S/N measurements
Delivery probability
Loss over time on two different
Roofnet links
avg: 0.5
stddev: 0.28
avg: 0.5
stddev: 0.03
Time (seconds)
The top graph is consistent with bursty
interference. The bottom graph is not.
Cumulative fraction
of node pairs
Most links aren’t bursty
Std dev of one-second
delivery averages
Hypothesis 3: short bursts of
interference (802.11)
A
B
• MAC doesn’t prevent all concurrent xmits
• Outcome depends on relative signal levels
• Hypothesis: When a nearby AP sends a
packet, we lose a packet.
Methodology: record
non-Roofnet 802.11 traffic
• Goal: measure non-Roofnet traffic
• Before the broadcast experiments
• Each node records all 802.11 traffic
Experiment packets lost
per second
No correlation between foreign
traffic observed and packets lost
Non-Roofnet packets observed
per second (before the experiment)
Hypothesis 4:
Multi-path interference
B
A
Reflection is a delayed and
attenuated copy of the signal
A channel emulator to investigate
multi-path effects
Sender
Receiver
delay
attenuation
Delivery probability
Reflection causes intermediate
packet loss
Delay of second ray
(nanoseconds or feet)
Cumulative fraction
of links
Roofnet links are long
Link distance (feet or nanoseconds)
It’s reasonable to expect delays >500 ns
Summary
• Most Roofnet links have intermediate
loss rates
• S/N does not predict delivery probability
• Loss is not consistent with bursty
interference
• Multi-path is likely to be a major cause
Satellites
• Geostationary Earth Orbit (GEO) Satellites
– example: Inmarsat
SAT
ground stations
Satellites
• Low-Earth Orbit (LEO) Satellites
– example: Iridium (66 satellites, 2.4 Kbps)
constellation
SAT
SAT
SAT
ground stations
Satellites
• GEO
– long delay: 250-300 ms propagation delay
• LEO
– relatively low delay: 40 - 200 ms
– large variations in delay - multiple
hops/route changes, relative motion of
satellites, queueing
Wireless Connectivity - Characteristics
• Transmission errors
– Wireless LANs - 802.11, Hyperlan
– Cellular wireless
– Multi-hop wireless
– Satellites
• Low bandwidth
– Cellular wireless
– Packet radio (e.g., Metricom)
• Long or variable latency
– GEO, LEO satellites
– Packet radio - high variability
• Asymmetry in bandwidth, error characteristics
– Satellites (example: DirectPC)
Mobility
• Why mobility?
– 30~40% of the US workforce is mobile
(Yankee group)
– Hundreds of millions of users are already
using portable computing devices and
more than 60% of them are prepared to
pay for wireless access to the backbone
information
Mobility
• Four types of activities for a typical office work
during a workday:
– Communication (fax, email)
– Data manipulation (word processing, directory
services, document access & retrieval)
– Information access (database access and
update, internet access and search)
– Information share (groupware, shared file
space)
• Question: how does mobility affect each of the
above activities?
Possible scenarios of mobility
• Scenario 1: user logs out from computer 1, moves
to computer 2 and logs in
– Should the user see the same workspace?
• Scenario 2: different devices for different networks
• Scenario 3: user docks a laptop, works in a
networked mode for a while, then disconnects and
works in the standalone mode for a while, and then
docks back
– In stand-alone mode
• What kind of activities can the user do?
• What cannot be done?
• Can we provide an illusion of connectivity in this case?
• Can we automatically re-integrate the work he has
done while disconnected when he finally reconnects to
the network server?
Impact of Mobility
• Scenario 4: a user has a notebook with a
wireless connection, connects to a remote host
via network 1, shuts down connections,
connects to the remote host via network 2,
continues to work
– Is the disconnection between network migration
necessary?
– When can we make the disconnection transparent to
users? When we cannot?
– What are the key issues to ensure seamless network
migration?
– Is it really important or users do not care about the
automatic process? For what applications? What to
change for the applications?
Protocol Stack
Application Layer
Look at:
1. Applications/Services
Middleware and OS
Transport Layer
Network Layer
Link Layer & Below
2. OS issues
3. Middleware (skip):
1. Transcoding
Issues in building services in mobile
networking environments
• Mobility induced issues:
– Seamless services: service migration
– Location services: location itself is a service
• Heterogeneity induced issues:
– Hardware diversity
• Client devices & different networks
– Software diversity
• System software: OS, networking protocols
• Application software
• Wireless induced issues:
– Time-varying network connectivity: disconnection, partial
connection, full connection
Possible services for mobile environments
• Location service
• Location transparent services
– Hide locations from users
• Location dependent services
– Services “local” to a geographic location
– Not available globally
• Location aware services
– Services are globally available, but multiple
instantiations of the same service are a function of
locations
– Service adapts to a location
Issues in Operating Systems
• Energy-efficient scheduler
• File systems for disconnected operation due to
mobility and disconnected wireless links
– access the same file as if connected
– retain the same consistency semantics for shared files
as if connected
– availability and reliability as if connected
– ACID (atomic/recoverability, consistent, isolated/
serializablity, durable) properties for transactions
• Constraints:
–
–
–
–
disconnection and/or partial connection
low bandwidth connection
variable bandwidth and latency connection
connection cost
Next Step:
Networking Issues
Physical/MAC Layer
• Requirements:
– Continuous access to the channel to transmit a frame
without error
– Fair access to the channel: how is fairness quantified?
– Low power consumption
– Increase channel throughput within the given
frequency band
• Constraints:
– Channel is error prone
– Channel contention and error are location dependent
– Transmission range is limited (but also enables
channel reuse)
– Shared channel (hidden/exposed station problem)
Physical/MAC Layer
• Possible options:
– Physical layer:
• Narrow band vs wide band: direct sequence,
frequency hopping, OFDM
• Antenna technology: smart antenna, directional
antenna, MIMO
• Adaptive modulation
– MAC layer
• Multiple access protocols (CSMA/CA, MACAW, etc.)
• Frame reservation protocols (TDMA, DQRUMA, etc.)
Link Layer
• Requirements:
– Error sensitive application
• A reliable link abstraction on top of errorprone physical channels
– Delay sensitive application
• A bounded delay link abstraction on top of
error-prone channels
• Constraints:
– Errors in the channel
– Spatial congestion
– Link capacity is changing (PHY multi-rate
option)
Link Layer
• Possible options at the link layer
– Windowing to provide error and flow control
– Combating error:
• Proactive: error correction via e.g. FEC
• Reactive: error detection+retransmission, ARQ
• Channel-state prediction+channel swapping
– Fairness options: long term vs short term,
deterministic vs probabilistic, temporal vs
throughput
• All links are treated equal
• Users in error prone or congested location
suffer
Network Layer
• Requirements:
– Maintain connectivity while user roams
– Allow IP to integrate transparently with roaming
hosts
• Address translation to map location-independent
addressing to location dependent addressing
• Packet forwarding
• Location directory
– Support multicast, anycast
– Ability to switch interfaces on the fly to migrate
between failure-prone networks
– Ability to provide quality of service: what is QoS
in this environment?
Network Layer
• Constraint:
– Unaware hosts running IP
– Route management for mobile hosts needs
to be dynamic
– A backbone may not exist (ad-hoc
network)
Network Layer
• Possible options:
– Mobile IP and its variants
• Two-tier addressing (location independent
addressing <-> location dependent addressing)
• A smart forwarding agent which encapsulates
packets from unware host to forward them to MH
• Location directory for managing location updates
– Ad hoc routing
• Shortest path, source routing, multipath
routing
Transport Layer
• Requirements:
– Congestion control and rate adaptation
• Doing the right thing in the presence of different
packet losses
– Handling different losses (mobility-induced
disconnection, channel, reroute)
– Improve transient performance
• Constraints:
– Typically unware of mobility, yet affected by mobility
– Packet may be lost due to congestion, channel error,
handoffs, change of interfaces, rerouting failures
– Link-layer and transport layer retransmit interactions
Transport Layer
• Options:
– Provide indirection
– Make transport layer at the end hosts ware
of mobility
– Provide smarts in intermediate nodes (e.g.
BS) to make lower-layer transport aware
– Provide error-free link layers