Transcript Ad Hoc Wireless Routing

Wireless Ad hoc networks
– Routing
Proposed ad hoc Routing Approaches
• Conventional wired-type schemes (global
routing, proactive):
– Distance Vector; Link State
• Proactive ad hoc routing:
– OLSR, TBRPF
• On- Demand, reactive routing:
– DSR (Source routing), MSR, BSR
– AODV (Backward learning)
• Scalable routing :
– Hierarchical routing: HSR, Fisheye
– OLSR + Fisheye
– LANMAR (for teams/swarms)
• Geo-routing: GPSR, GeRaF, etc
– Motion assisted routing
– Direction Forwarding
Wireless multihop routing challenges
• mobility
• need to scale to large numbers (100’s to
1000's)
• need to support multimedia applications
(QoS)
• unreliable radio channel (fading, external
interference, mobility, etc)
• limited bandwidth
• limited power
Conventional wired routing limitations
• Distance Vector (eg, Bellman-Ford, BGP):
– Tables grow linearly with # nodes
– routing control O/H linearly increasing with
network size
– convergence problems (count to infinity);
potential loops (mobility?)
• Link State (eg, OSPF):
– link update flooding O/H caused by network size
and frequent topology changes
CONVENTIONAL ROUTING DOES NOT SCALE TO
SIZE AND MOBILITY
Intra-AS
Inter-AS
DV
RIP
BGP
LS
OSPF
Proactive ad hoc schemes
– OLSR and TBRPF
• Link State explodes because of Link State update
overhead
• Question: how can we reduce the O/H?
• Answer: Link State with “Topology reduction”
– (1) if the network is “dense”, use fewer
forwarding nodes
– (2) if the network is dense, advertise only a
subset of the links
• Two leading IETF Link State schemes enhance
scalability in large scale networks:
– OLSR : Optimal Link State Routing
– TBRPF: Topology Broadcast Reverse Path
Routing
LSR (Link State Routing)
• In LSR protocol a lot
of control msg
unnecessary
duplicated
24 retransmissions to diffuse a
message up to 3 hops
Retransmission node
OLSR (Optimal Link State Routing)
• In OLSR only a
subset of neighbors
(MPR-Multipoint
Relay Selectors)
retransmit control
messages:
– Reduce size of
control message;
– Minimize flooding
11 retransmission to diffuse a
message up to 3 hops
Retransmission node
OLSR Overview
• RFC 3626, October 2003
• In LSR protocol a lot of control messages
unnecessarily duplicated
• In OLSR only a subset of neighbors (MPR-Multipoint
Relay Selectors) retransmit control messages
– Reduce flooding overhead
– Adapted for dense network
• OLSR retains all the advantages of LSR:
– stable;
– Does not depend upon any central entity;
– Tolerates loss of control messages;
– Supports nodes mobility
On-Demand Routing Protocols
• Routes are established “on demand” as
requested by the source
• Only the active routes are maintained by
each node
• Channel/Memory overhead is minimized
• Two leading methods for route discovery:
source routing and backward learning
(similar to LAN interconnection routing)
Existing On-Demand Protocols
•
•
•
•
•
•
•
•
•
•
Dynamic Source Routing (DSR) -- CMU
Multipath Source Routing (MSR) – TJU
Backup Source Routing (BSR) – UofO+TJU
Ad-hoc On-demand Distance Vector (AODV)
Associativity-Based Routing (ABR)
Temporarily Ordered Routing Algorithm (TORA)
Zone Routing Protocol (ZRP)
Location assisted routing (LAR, DREAM)
Signal Stability Based Adaptive Routing (SSA)
On Demand Multicast Routing Protocol
(ODMRP) – UCLA
Dynamic Source Routing (DSR)
• RFC 4728 – February 2007
• Forwarding: source route driven instead of
hop-by-hop route table driven
– Mobility ?
• No periodic routing update message is sent
• The first path discovered is selected as the
route
• Two main phases
– Route Discovery
– Route Maintenance
DSR - Route Discovery
• To establish a route, the source floods a Route
Request message with a unique request ID
• The Route Request packet “picks up” the node
ID numbers
• Route Reply message containing path
information is sent back to the source either by
– the destination, or
– intermediate nodes that have a route to the
destination
• Each node maintains a Route Cache which
records routes it has learned and overheard
over time
DSR - Route Maintenance
• Route maintenance performed only while
route is in use
• Monitors the validity of existing routes by
passively listening to acknowledgments of
data packets transmitted to neighboring
nodes
• When problem detected, send Route Error
packet to original sender to perform new
route discovery
MSR - Multipath Source Routing
• Direct Descendant of DSR
• On-demand + Source Routing + Multipath
• Probing-based adaptive load balancing among
multiple paths
• Motivation of MSR
– Efficiently using the network resource
– Alleviate the oscillation in adaptive single
path routing
– Fast re-routing
– Reducing computing & storage requirement
– Exploiting computing power of host instead
of link capacity
Distributing Traffic among Multiple
Paths
• Quantities: A heuristic equation
• Probing-based adaptive control
– Decoupling between transport layer and
network layer: SRPing
– Cost effective
• Scheduling: Packet Weighted Round Robin
• TCP out-of-order (re-sequencing) problem
Distributing Traffic among
Multiple Paths
• Heuristic equation
– Rationale: Autonomous system, homogeneous
assumption, bandwidth-delay product constant
j




j
d
max


min
,U   R

j 
Wi
 d  
i 


where ,
j
d i is the delay of route with index i,
j
dmax
is the maximum delay of all the routes to the
same destination,
R is a factor to control the switching frequency
between routes.
U is a bound value to insure that should not to be
too large.
MSR Summary
• Reduce network congestion
• Improve throughput, delay, mobility, fault
tolerance (CBR & FTP)
• Acceptable routing overhead?
– Little more than that of DSR
– Route discovery
– Route maintenance
• Probing (unicast) add little O/H
• Good candidate for QoS support
– QoS-MSR, reliable-MSR
• Acceptable packet out-of-order level ?
Backup Source Routing (BSR)
• Establish and maintain backup routes that
can be utilized after the primary path breaks
• Define a new routing metric - route
reliability, and use it to provide the basis for
the backup path selection
• Reduce the frequency of route discovery
flooding, which is a major overhead in ondemand protocols
• Can improve the performance significantly
in more challenging situations of high
mobility
Simulation Methodology
• ns – Wireless extensions by CMU
• Adopt methods used in [Broch98, Johnson99]
• Two major files:
– Movement pattern file
– Communication pattern file
• 50 mobile hosts placed randomly within a
1500m×300m area
• 20 connections
• Different traffic types: CBR & FTP
• Two set of simulations: Max speed 20m/s &
1m/s
Performance Evaluation
• MSR vs. DSR vs. BSR
• Performance Metrics
– Packet delivery ratio
– Data throughput
– End-to-end delay
– Packet drop probability
– Queue size
Simulation Results with UDP Traffic
-- Packet delivery ratio for 20 sources
8
Simulation Results – CBR
• End-to-end throughput
200
Throughput, packets/second
DSR
MSR
150
100
50
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Connection No.
Simulation Results with UDP Traffic
-- Average end-to-end delay for 20 sources
11
Simulation Results - CBR
• Packets dropped at each node
DSR
MSR
# of drops
15
10
5
0
1
3
5
7
9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
Node No.
Previous Work on Using Multiple Paths
• Alternate use (primary and backup)
– It works OK for CBR traffic (BSR, Bypass DSR, Node Disjoint M-path AODV, etc)
– TCP does not get much benefit. Backup path
is used only after timeout; not efficient in
mobility/errors.?
• Concurrent use (ie, packet scattering)
– MSR
– TCP does well in a static, error free net with
long paths (up to 50% improvement)
– With mobility & errors, TCP suffers out-oforder problems because of RTT difference
on the two paths
“TCP Performance on multiple paths
in ad hoc nets..” Liaw et al ICC 2004
Static net, no errors, opt W: max improvement 50%;
typical improvement between 8% and 18%
Multiple Path TCP with Packet Replicas
• TCP data packet duplication on multiple paths
– May introduce less O/H than repeated end
to end retransmissions
• Improve end-to-end route robustness when
single route is not stable:
– Replicate packet on multiple paths
– Combat random, non correlated link losses
– Combat path breakage
Total Throughput(bits/s)
Variable Loss Rate [ 0.05; 0.1; 0.15; 0.2]
Mobility(m/s)
Original TCP
Multipath TCP
Where do we stand?
• OLSR and TBRPF can dramatically reduce
the “state” sent out on update messages
• They are very effective in “dense”
networks.
• However, the state still grows with O(N)
• Neither of the above schemes can handle
large scale nets from 10’s to thousands of
nodes
• What to do?
Hierarchical Routing
The previous schemes reduce control traffic
O/H but do not significantly reduce routing
table size
Solution: use hierarchical routing to reduce
table size
In the process, reduce also control traffic O/H
Proposed hierarchical schemes include:
– Hierarchical State Routing (HSR)
– Fisheye State Routing (FSR)
– Landmark Routing
– Zone routing (hybrid scheme)
Routing
• Current MANET solutions have limitations:
– (a) proactive routing solutions (eg, Optimal
Links State -OLSR) do not scale because
of table size and control traffic overhead
– (b) on demand routing cannot handle high
mobility and dense traffic patterns
– (c) explicit hierarchical routing introduces
excessive address maintenance O/H in
high mobility
• MANET protocols do not scale
• UCLA approach: LANMAR
– Exploit implicit hierarchy induced by
group mobility
Solution: Landmark Routing Overlay
• Main assumption: nodes move in groups
• Groups are predefined or dynamically
recognized
• Node address: < group ID , Host address>
• Landmark elected in each group
• Landmarks advertisements maintain the
landmark overlay
Landmark
Logical Subnet
LANMAR Overlay Routing (cont)
• Builds upon existing MANET protocols
– (1) “local ” routing algorithm that keeps
accurate routes within local scope < k hops
(e.g., OLSR)
– (2) Landmark routes advertised to all
mobiles using DSDV Landmark
Logical Subnet
LANMAR Overlay Routing (cont)
• Packet Forwarding:
– A packet to “local” destination is routed
directly using local tables
– A packet to remote destination is routed to
Landmark corresponding to logical addr.
– Once the landmark is “in sight”, the direct
route to destination is found in local tables
• Benefits: low storage, low update traffic O/H
Landmark
Logical Subnet
Landmark Routing In action
LM1
Landmark LM2
LM3
Logical Subnet
dest
local routing
Long haul routing
source
1. Node address = {subnet ID, Host ID}
2. Look up local routing table to locate dest  fail
3. Look up landmark table to find destination subnet  LM1
4. Send a packet toward LM1
Link Overhead of LANMAR
• Dramatic O/H reduction from linear to O(N) to O (sqrtN)
LANMAR enhances MANET routing
schemes
We compare:
(a) MANET routing schemes: DSDV, OLSR and
FSR; and
(b) same MANET schemes, BUT with LANMAR
overlay on top
Delivery Ratio
LANMAR-DSDV
LANMAR-FSR
OLSR
LANMAR-OLSR
FSR
DSDV
• DSDV
and FSR decrease quickly when number of nodes
increases
• OLSR generates excessive control packets, cannot
exceed 400 nodes
Georouting - Key Idea
• Each node knows its geo-coordinates (eg,
from GPS or Galileo)
• Source knows destination geo-coordinates; it
stamps them in the packet
• Geo-forwarding: at each hop, the packet is
forwarded to the neighbor closest to
destination
• Options:
– Each node keeps track of neighbor
coordinates
– Nodes know nothing about neighbor
coordinates
Greedy Perimeter Stateless Routing
for Wireless Networks (GPSR)
• Greedy forwarding
– Each nodes knows own coordinates
– Source knows coordinates of destination
– Greedy choice – “select” the most forward
node
Finding the most forward neighbor
• Beaconing: periodically each node
broadcasts to neighbors own {MAC ID, IP ID,
geo coordinates}
• Each data packet piggybacks sender
coordinates
• Alternatively (for low energy, low duty cycle
ops) the sender solicits “beacons” with
“neighbor request” packets
Greedy Perimeter Forwarding
D is the destination; x is the node where the
packet enters perimeter mode; forwarding
hops are solid arrows;
Got stuck? Perimeter forwarding
> Greedy forwarding failure. x is a local maximum
in its geographic proximity to D; w and y are
farther from D.
> Node x’s void with respect to destination D
GPSR vs DSR
Throughput (Kbps)
TCP over GPSR, AODV, DSR and DSDV
Speed(m/s)
GPSR commentary
• Very scalable:
– small per-node routing state
– small routing protocol message complexity
– robust packet delivery on densely deployed,
mobile wireless networks
• TCP is extremely sensitive to path breakage
(timeout) -- It does very well with georouting
• Outperforms DSR and AODV
• Drawback: it requires knowledge of dest geo
coordinates (explicit forwarding node address)
– Beaconing overhead
– nodes may go to sleep (on and off)