Transcript 3-1-3_Scalable

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
– 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
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)
Hierarchical State Routing (HSR)
• Loose hierarchical routing in Internet
• Main challenge in ad hoc nets: maintain/update the
hierarchical partitions in the face of mobility
• Solution: distinguish between “physical” partitions
and “logical” grouping
– physical partitions are based on geographical
proximity
– logical grouping is based on functional affinity
between nodes (e.g., tanks of same battalion,
students of same class)
• Physical partitions enable reduction of routing
overhead
• Logical groupings enable efficient location
management strategies using Home Agent concepts
HSR - physical multilevel partitions
3
1
Level = 2
HSR table at node 5:
DestID Path
2
3
1
Level = 1
4
1
5-1
6
5-1-6
7
5-7
<1-2-> 5-1-6
<1-4-> 5-7
2
6
3
1
Level = 0
(MAC addresses)
8
5
11
7
4
9
10
<1-3>
5-7
Hierarchical HID(5): <1-1-5>
addresses HID(6): <3-2-6>
HSR - logical partitions and location
management
• Logical (IP like) type address <subnet,host>
– Each subnet corresponds to a particular user
group (e.g., tank battalion in the battlefield,
search team in a search and rescue
operation, etc)
– logical subnet spans several physical
clusters
– Nodes in same subnet tend to have common
mobility characteristic (i.e., locality)
– logical address is totally distinct from MAC
address
HSR - logical partitions and location
management (cont’d)
• Each subnetwork has at least one Home
Agent to manage membership
• Each member of the subnet registers its own
hierarchical address with Home Agent
– periodical/event driven registration; stale
addresses are timed out by Home Agent
• Home Agent hierarchical addresses
propagated via routing tables; or queried at
a Name Server
• After the source learns the destination’s
hierarchical address, it uses it in future
packets
• Example: Landmark Routing
Fisheye State Routing (FSR)
2
8
5
3
1
9
9
4
6
Hop=1
7
13
10
12
11
36
14
21
Hop>2
15
16
17
22
23
20
29
27
25
24
Hop=2
19
18
26
30
28
34
32
31
Scope of Fisheye
35
Fisheye State Routing (FSR)
• Topology data base at each node
- similar to link state (e.g., OSPF)
• Routing information is periodically exchanged with
neighbors only ( “Global” State Routing)
– similar to distance vector, but exchange entire
topology matrix
• Routing update frequency decreases with distance
to destination
– Higher frequency updates within a close zone
and lower frequency updates to a remote zone
– Highly accurate routing information about the
immediate neighborhood of a node;
progressively less detail for areas further away
from the node
Message Reduction in FSR
TC (Topology Control) message
LST
0:{1}
1:{0,2,3}
2:{5,1,4}
3:{1,4}
4:{5,2,3}
5:{2,4}
HOP
1
0
1
1
2
2
0
1
3
2
4
5
LST
0:{1}
1:{0,2,3}
2:{5,1,4}
3:{1,4}
4:{5,2,3}
5:{2,4}
LST
0:{1}
1:{0,2,3}
2:{5,1,4}
3:{1,4}
4:{5,2,3}
5:{2,4}
HOP
2
1
2
0
1
2
HOP
3
2
1
1
0
1
Optimized “Fisheye” Link State Routing (OFLSR)
• Based on Optimized Link State Routing (OLSR)
• Borrows idea from Fisheye State Routing (FSR)
• Different frequencies for propagating the Topology
Control (TC) message of OLSR to different scopes
(e.g. different hops away)
scope width
scope 4
scope 1
scope 2
scope 3
Scalability Property of OFLSR
• Scalability to Node Mobility
Data Packet Delivery Ratio
–
–
–
–
100 nodes, 1600mX1600m field, 367m Tx range
IEEE 802.11 radio, 2Mbps channel rate, 10 CBR flows
OLSR confign: hello interval = 1s, TC interval = 2s
OFLSR confign: 4 scopes, each scope is 2 hops
except last one
OLSR
OLSR + FSR (scope)
OLSR + FSR (probability)
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
5
10
Node mobility speed (m/s)
Data Packet Delivery Ratio
15
20
Scalability Property of OFLSR
OLSR
OLSR + FSR (scope)
OLSR + FSR (probability)
0
5
10
15
20
Node Mobility (m/s)
Total # of TC relayed
message
received
500000
450000
400000
350000
300000
250000
200000
150000
100000
50000
0
TC
# of TC messages relayed
• Scalability to Node Mobility
9000000
8000000
7000000
6000000
5000000
4000000
3000000
2000000
1000000
0
OLSR
OLSR + FSR (scope)
OLSR + FSR (probability)
0
5
10
15
node mobility (m/s)
20
Total # of TC received
Scalability Property of OFLSR
• Scalability to Network Size
Data Packet Delivery Ratio
– Keep node density, increase # of nodes, no mobility
– OLSR confign: hello interval = 2S, TC interval = 4S
– OFLSR confign: 4 scopes, each scope is 2 hops
except last one
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
OLSR
OLSR + FSR
100
200
300
400
Network Size (# of nodes)
Delivery rate vs Network Size
500
Scalability Property of OFLSR
• Scalability to Network Size
60000000
OLSR
OLSR + FSR
received
5000000
4000000
OLSR
OLSR + FSR
50000000
40000000
30000000
1000000
of
2000000
#
of
TC
3000000
#
TC
relayed
6000000
0
20000000
10000000
0
100
200
300
400
Network Size (# of nodes)
Total # of TC relayed
500
100
200
300
400
Network Size (# of nodes)
500
Total # of TC received
Scalable Ad Hoc Routing using
Landmarks and Backbones
• The challenge
– Tens of thousands of nodes
– Nodes move in various patterns
– QoS communications requirements
– Hostile environment – jamming
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 in high mobility
• Our approach:
– Exploit implicit hierarchy induced by group
mobility
Solution: Landmark Routing Overlay
• Main assumption: nodes move in groups
(battlefield)
• 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
– Like Internet: LS + DV
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: Local Scope Optimization
• Goal: find local routing scope size that minimizes
routing overhead
– size of landmark distance vector: O ( N / G)
– size of local Link State topology map: O ( m * d )
H (Routing overhead)
N: total # of nodes; d: avg # of one-hop neighbors (degree)
Total O/H H  H  H
lm
local
Local route O/H
H
local
 (h2d 1 ),0    1
Landmark O/H
h*
H
lm
 ( N )
h 2d
h (scope size)
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
Mobile Backbone Overlay
• Landmark Overlay provides routing
scalability
• However the network is still flat - paths
have many hops  poor TCP and QoS
performance!!
• Solution: Mobile Backbone Overlay (MBO)
• MBO is a physical overlay – ie long links
• MBO provides performance scalability
• LANMAR extends “transparently” to the
MBO
UAV
Backbone Node
Landmark
Logical Subnet
source
dest.
Landmark routing concept extends transparently to the
multilevel backbone
Fast BB links are “advertised” and immediately used
When BB link fails, the many hop alternate path is chosen
Backbone Network and LANMAR
• Why a Backbone “physical” hierarchy?
– To improve coverage, scalability and reduce
hop delays
• Backbone deployment
– automatic placement: Relocate backbone
nodes from dense to sparse regions (using
repulsive forces)
• Key result: LANMAR automatically adjusts to
Backbone
• Combines low routing O/H (LANMARK logical
hierarchy) + low hop distance and high
bandwidth (Backbone physical hierarchy)
Extending Landmark to Hierarchical
Network
• Backbone nodes are independently
elected
• All nodes (including backbone nodes) are
running the original LANMAR
• In addition, backbone nodes re-broadcast
landmark information via higher level links
• Backbone Routes preferred by landmark
(they are typically shorter)
Extending Landmark (cont)
• If backbone node is lost, Landmark routing
“fills the gap” while a replacement
backbone node is elected
• Advantages
– Seamless integration of “flat” ad hoc
landmark routing with the backbone
environment provides instant backup in
case of failures
– Easy deployment, simple changes to
ordinary ground nodes
– Remove limitations of strictly hierarchical
routing
Variable number of Backbone Nodes
• Decrease of average end-to-end delay while increasing
# of backbone nodes
60
Average end-end delay(sec)
50
40
30
20
10
Hierarchical Landmark
Flat Landmark
0
0
9
18
# of back bone node s
27
36
Variable number of Backbone Nodes
• Increase of delivery fraction while increasing # of
backbone nodes
1
Delivery Fraction
0.9
0.8
0.7
Hierarchical Landmark
0.6
Flat Landmark
0.5
0
9
18
# of backbone nodes
27
36
Variable Speed with 1000 nodes
Delivery fraction while increasing mobility speed
1.1
Hierarchical Landmark
Flat Landmark
1
Delivery fraction
AODV
0.9
0.8
0.7
0.6
0.5
0.4
0
2
4
6
Mobility speed(m /sec)
8
10
LANMAR implementation in IPv6
LINUX environment
• Use IPv6’s Group ID to distinguish groups
• Support many more members in each group
(than IPv4)
• A packet to remote destination is routed to
corresponding Landmark based on IPv6
address lookup
IPv6:
48 bits
Network ID
Subnet
Mask
0000 … 000
16 bits
GroupID
11…11
64 bits
Node ID
00000000 … 0000000