Transcript Ad Hoc Network Protocols1

Ad Hoc Network Protocols
Project/Thesis Outline
Paul J. Fong – Sept 2002
What is an Ad Hoc Network?
IEEE Std 802.11: “A
network composed
solely of stations
within mutual
communications
range of each other
via the wireless
medium (WM).”
Hacker: Multi-hop
self-configuring
wireless network
Mobile Ad Hoc Networks
(MANETs)
Military vehicles on a battlefield with no
existing infrastructure.
A fleet of ships at sea.
Emergency workers at an earthquake
that destroyed the infrastructure.
A gathering of people with notebook
computers in an area lacking 802.11.
Scientific field networks.
The Challenge
“We’ll have infinite
bandwidth in a decade’s
time.” – Bill Gates, PC
Mag, 11/11/94.
“computer
communications will
break down into two
domains - the
fibersphere and the
atmosphere.” - George
Gilder, Forbes, 3/29/93.
Timothy J. Shepard, MIT Thesis
“A single-channel radio
system can scale to
millions or billions of
stations within a
metropolitan area…
“..packets can be
transferred to nearby
neighbors without any
loss due to collisions.”
Objectives
Discuss IEEE Standard 802.11(b)
Analyze scalability of wireless networks
Obtain perspective of industry
Look at commercial wireless networks
Examine wireless layer 3 protocols
Origins: Hedy Lamarr
UNITED STATES
PATENT OFFICE
2,292,387
SECRET
COMMUNICATION
SYSTEM
Hedy Kiesler Markey,
Los Angeles, and George
Antheil, Manhattan
Beach, Cakif.
Application June 10,
1941, Serial No. 397,412
Unlicensed Bands
IEEE 802.11 – Transmission Modes
Infrared: 0.85u or 0.95u, 1 or 2 Mbps
Frequency Hopping Spread Spectrum (FHSS)
Direct Sequence Spread Spectrum (DSSS)
802.11a: Orthogonal Frequency Division
Multiplexing (OFDM) – 54 Mbps/5 GHz
802.11b: High Rate Direct Sequence Spread
Spectrum (HR-DSSS) – 11 Mbps/2.4 GHz
802.11g: OFDM with 54 Mbps/2.4 Ghz
Basic & Extended Service Sets
Roaming
Reassociation
Response
Reassociation
Request
Roaming
Independent Basic Service Set
Peer-to-peer
No servers
Time
Synchronization
Function (TSF)
based on latest time
in a beacon
No standards for
relay
802.11b Channels
14 (22 MHz) frequency channels (11 in US)
3 non-overlapping channels
11 Mbps data rate
Code Division Multiple Access
Station A (8-bit chip sequence)
1-bit (+A): -1 -1 -1 +1 +1 -1 +1 +1
0-bit (-A): +1 +1 +1 -1 -1 +1 -1 -1
Normalized Inner Product:
X * Y = 1/m [(x1)(y1) +…+ (xm)(ym)]
Receiver extracts data:
A * A = 1
(-A) * A = -1
Walsh Codes (orthogonal chip sequences)
for X not = Y:
X * Y = 0
CDMA (con’t)
4 stations (orthogonal chip sequences)
A:
-1 -1 -1 +1 +1 -1 +1 +1
B:
-1 -1 +1 -1 +1 +1 +1 -1
C:
-1 +1 -1 +1 +1 +1 -1 -1
D:
-1 +1 -1 -1 -1 -1 +1 -1
4 stations transmit, receiver hears:
A+B+C+D: -4 0 -2 0 +2 0 +2 -2
A+B-C+D: -2 -2 0 -2 0 -2 +4 0
CDMA (con’t)
4 stations transmitting
S1=A+B+C+D:
S2=A+B-C+D:
-4 0 -2 0 +2 0 +2 -2
-2 -2 0 -2 0 -2 +4 0
Extract C:
-1 +1 -1 +1 +1 +1 -1 –1
S1 * C = 1/8(+4
+2
+2
-2 +2)= 1
S2 * C = 1/8(+2 -2
-2
-2 -4
)=-1
802.11b Range
FCC 1w power limit
(4w EIRP for fixed)
Omnidirectional:
150-300 feet
Directional antenna:
up to 25 miles
Attenuated by walls
& glass
Hidden Station Problem
A is transmitting to B
C is out of range of A
C transmits to B causing collision
802.11 attempts to solve this problem
Exposed Station
B is transmitting to A
C wants to transmit to D
C senses transmission & declines
No 802.11 solution
Channel Contention
Distributed
Coordination
Function (DCF) uses
CSMA/CA (2 modes)
Physical Channel
Sensing (~Ethernet)
Virtual Channel
Sensing (RTS/CTS)
Point Coordination
Function (PCF)
Polling by base
station
Periodic beacon
frames
No collisions
Virtual Channel Sensing:
Request to Send
Virtual Channel Sensing:
Clear to Send
Virtual Channel Sensing: Timing
A
B
C
Network Allocation Vector
RTS
DATA
CTS
D
ACK
Network Allocation Vector
Time
Interframe Spacing
ACK
SIFS
PIFS
DIFS
EIFS
Time
Short Interframe
Spacing
PCF Interframe
Spacing
DCF Interface
Spacing
Extended Interframe
Spacing
Virtual Channel Sensing:
Fragment Burst
A
B
C
D
Network Allocation Vector (NAV)
RTS
Fragment 1
CTS
Fragment 2
ACK
NAV
Time
Fragment 2
ACK
ACK
Point Coordination Function
(PCF)
Base station polls
clients in cell
Beacon frames sent
for synchronization
No collisions within
cell
Allows guaranteed
Quality of Service
Dynamic Rate Shifting
Data Rate
Code
Modulation
Symbol Rate Bits per
(Mpbs)
Length
(MSps)
Symbol
1
11 (Barker Sequence)
Binary Phase Shift Keying
1
1
2
11 (Barker Sequence)
Quadrature Phase Shift Keying
1
2
5.5
8 (Complementary Code Keying) Quadrature Phase Shift Keying
1.375
4
11
8 (Complementary Code Keying) Quadrature Phase Shift Keying
1.375
8
Data rate readjusts for noise and
distance
Scalability Analysis
Physical Layer
Data Link Layer
Environment, Broadcast,
Half-duplex
Collisions, Bridging Loops
Network Layer
Scalability, Convergence,
Aggregation, Routing Loops
Transport Layer
Reliability & Error recovery
Upper Layers
Policies & Services
Pitfalls
Broadcast medium -> interference
Collisions -> retransmissions
Loops -> reduced bandwidth
Flooding -> broadcast storms
Link flapping -> route recalculations
Routing updates -> slow convergence
Going Exponential
“You don’t want to go
exponential.”
“If you are not careful
with a distributed
algorithm, you can go
exponential in a hurry.”
Radia Perlman,
NetWorld InterOp,
9/25/1995.
Data Link: Wired vs. Wireless
Reliable links
Few neighbors &
links
Specialized
infrastructure
Unreliable links
Many neighbors &
links
Node/LAN/router are
packaged
Loops: Transparent Bridging
A
B
D
C
E
H
F
I
J
G
K
M
L
Spanning Tree
Protocol (STP)
Define spanning tree
to each node
Recalculate when
topology changes
Susceptible to link
flapping
Loops: Source Route Bridging
A
B
D
C
E
H
F
I
J
G
K
M
L
To find optimal A-M
route, explorer
packets flood
network.
Hops put in header:
ADIM, ACHM,
ACGM, ADHM, etc.
1st explorer to reach
M is echoed back.
Spanning Tree vs. Source Routing
Computed once until
network changes
Plug and Play
End nodes don’t
participate
Loop-free topology
Compute as needed
Link flapping
Exponential flooding
for each src/dest
Configuration req’d
End nodes must
participate
“Optimal” routes
On demand
Variable header size
Network Layer: Route Propagation
Routers share
routing tables
Access “routers”
have limited
functionality
Routers execute
distance-vector &
link-state protocols
Network Layer: DVP Scalability
Distance Vector
Protocols
Periodic routing
table updates sent
to all neighbors
Neighbors propagate
routes
Peer-to-peer
Network Layer: LSP Scalability
Link State Protocols
Updates sent as
needed to all routers
Less susceptible to
link flapping
Area border routers
Hierarchical
segmentation
Distance Vector vs. Link State
Periodic updates
Full distance vector
sent to neighbors
Slower convergence
Peer-to-peer
Triggered updates
Changes sent to
entire area
Faster convergence
Hierarchical
Transport Layer
Error recovery at
layer 4 assumes
reliable links
Layer 2 error
recovery needed for
wireless networks
Performance
consequences
Upper Layer Issues
IP address
administration
Routing policy
control
Lack plug ‘n play
Security
IP Address Aggregation
Discontiguous Network
Very Discontiguous Network
Routing Policy Control
Routing policies can
keep an AS from
being a transit
Can ad hoc
networks enforce
policy?
Not self configuring
Wireless Security
Wired Equivalent
Privacy (WEP)
40 or 120 bit encryption
based on RC4 algorithm
“War Driving”
www.wardriving.com
IEEE response: 802.11i
will have better security
802.1x extends
authentication servers
Industry: Reliable Links
No need for layer 2
error recovery (X.25,
SNA)
Error recovery takes
place at layer 4 for
performance
Industry: Limited Hops
1 hop to wired access point is the norm
Wireless bridging but no wireless routing
Industry: 1-Layer LAN Segments
Switches
Buffered I/O
Full Duplex I/O
No collisions
Limited broadcast
No shared links
Industry: Hierarchical WANs
Hierarchical
organization: core,
distribution, access
Each area contains
approximately 50
routers
Backbone areas
Problems isolated to
an area
Industry: Centralization
Centralized network
management
Centralization vs.
Decentralization
DNS & DHCP
administration
IP address
administration
Wireless Relay Networks:
Rooftop
Nokia Rooftop
“Airhead”
aggregation points
within cells
Hierarchical with a
limited number of
wireless hops.
Wireless Relay Networks:
Ricochet
Metricom Ricochet
900 MHz spread spectrum: (1)modem –
(2)poletop radio – (3)access point
Fixed vs. Ad Hoc
Reliable links
Collision free
Few neighbors
Efficient
infrastructure
Address aggregation
Centralized services
Policy enforcement
Unreliable links
Contention
Many neighbors
Node/LAN/router are
packaged
No aggregation
Distributed services
No enforcement
Desired Ad Hoc Routing
Characteristics
“Fish-Eye” view
Distributed services
Fast convergence
Link-layer reliability
Low overhead
Ad Hoc Routing Protocols
Geographical routing (GRID)
Destination-Sequenced Distance Vector
(DSDV)
Temporally-Ordered Routing Algorithm
(TORA)
Dynamic Source Routing (DSR)
Ad Hoc On-Demand Distance Vector
(AODV)
Geographical Routing
Longitude & Latitude
Grid Location
Service
Packet forwarded to
neighbor nearest to
destination
Ad Hoc On-Demand Distance
Vector (AODV)
Related to BellmanFord algorithm
On-demand route
calculation
No periodic
broadcasts of
routing table
Only changes are
propagated
Route Discovery
A
Node A wants to
send a packet to I
Node A broadcasts a
B
C
D
E
F
G
H
I
route request.
Route Discovery (2)
A
B & D propagate
B
C
D
E
F
G
H
I
route requests
Duplicate route
requests discarded
Route Discovery (3)
A
C, F & G propagate
B
C
D
reaches node I
E
F
G
H
route requests
1st route request
I
Route Discovery (4)
A
Node I sends route
B
C
D
E
F
G
H
I
reply
Route Maintenance
A
B
C
D
E
F
H
I
Periodic hello
messages are sent
Node G goes offline
Routes for node G
are pruned
Future Work
Evaluate proposed ad hoc routing
protocols
Select an ad hoc routing protocol for
small scale wireless network
Demonstrate current industry wireless
equipment
References
Hedy Lamarr: www.hedylamarr.at
Nokia Rooftop:
www.wbs.nokia.com/download/paper.ht
ml
802.11: www.drizzle.com/~aboba/IEEE
RF Calculator: www.ydi.com/calc.php
TEC Embedded Library:
www.tinyos.com