Transcript Ad Hoc Routing and Mobility in the Internet Emmanuel

Ad Hoc Routing
and Mobility
in the Internet
Emmanuel Baccelli
April 6th 2006
INRIA Hitachi
Ecole Polytechnique
1
Agenda
1. Background on Mobile Ad Hoc Networks
2. MANET routing overhead reduction
schemes
3. MANET integration in the Internet
4. MANET scaling to large topologies
INRIA Hitachi
Ecole Polytechnique
2
Internet & Wireless
• Since the 1990’s, two telecom. revolutions in “parallel” :
• Internet
• Mobile wireless communication
(hundreds of millions of users worldwide)
●
●
Recently: desire to
merge the advantages
of the two
scalable,
“cheap”,
1rst step:
wireless
Internet edge
multimedia network
access
●
●
●
●
●
Internet
access
point
wireless
mobility,
802.11 wLAN (popular, cheap)
ubiquitous access
3G cell services (deploying, expensive)
2nd step: desire to use wireless
connectivity beyond edge access
with mobile ad hoc networking
INRIA Hitachi
Ecole Polytechnique
3
Traditional Networking
vs
Ad Hoc Networking
non-directional
radio connectivity
user devices
(hosts)
A both user
and router
A
E
C
shared access
medium
B
D
routing Mobile ad hoc networks:
routers
protocol → different characteristics
(ex: OSPF)
•Onerouting
device type
•Traditional
protocols fail
•Medium
(radio) not needed
fully shared
•New levels
of performance
•Interferences, less bandwidth
potential router
+ host
→ new•Nodes
routing=mechanisms
must
be used
•Nodes are mobile
INRIA Hitachi
4
Ecole Polytechnique
1.
2.
The Main MANET Routing
Solution Families
Proactive routing
•
•
Nodes maintain routes to all destinations
Most protocols: link-state
→ Adaptation of traditional Internet
routing, predictable performance
Reactive routing
link ROUTE
state flooding
REQUEST
(global
scope)
(global
scope)
S
HELLO
(local scope)
•
•
Nodes discover routes only on-demand
Based on route request flooding and route
ROUTE D
reply messaging
REPLY
→ Departure from traditional Internet
neighborhood
discover
neighborhood
routing, unpredictable performance distribute
description to all the nodes
INRIA Hitachi
Ecole Polytechnique
5
MANET Routing in the
Internet
●
Focus on proactive link-state MANET routing
●
●
Every MANET node potentially generates control
traffic
●
●
easier integration in the Internet
Difference with traditional networks (only routers)
Overhead reduction mechanisms are needed
INRIA Hitachi
Ecole Polytechnique
6
Agenda
1. Background on Mobile Ad Hoc Networks
2. MANET routing overhead reduction
schemes
►Comparison of optimized flooding
schemes
Comparison of partial topology
schemes
3. MANET integration in the Internet
4. MANET scaling to large topologies
INRIA Hitachi
Ecole Polytechnique
7
Overhead Reduction:
Optimized Flooding
• Def: Reducing the number of
(re)transmissions needed to distribute
some information network-wide
►Classical flood: every node retransmits once
→ network covered, but redundantly
(especially when the network is dense)
►Optimized flood: only some nodes retransmit
→ network efficiently covered
- reduced bandwidth use
- reduced amount of interferences
- reduced number of packet collision
INRIA Hitachi
Ecole Polytechnique
this node was
covered 4 times
8
Dominating Set Flooding
Algorithm: MPR Flooding
MPR (Multi-Point Relay) selection:
each node selects a subset its
neighbors, covering all the
neighbors of its neighbors
MPR
[P. Jacquet, P. Minet, et al. HiperLAN, 1996]
S
Flooding: only MPRs retransmit
and the network is efficiently covered
MPR
[L. Viennot, A. Laouiti, A. Qayyum, 2000]
INRIA Hitachi
Ecole Polytechnique
9
Tree Flooding Algorithm:
Gateway Flooding
1. Automatic tree formation:
each node selects its neighbor
which has the max number
of neighbors as parent in the tree
R
[C. Bonnet, H. Labiod,
N. Nikaein, 2000]
2. Network = forest of trees
roots = local degree maxima
R
Gateway Flooding: retransmission
happens only along tree vertices
(and between trees)
INRIA Hitachi
Ecole Polytechnique
10
Flooding Algorithms
Comparison & Analysis
number of retransmitters
Retransmitters %
MPR Flooding Simulations (1D)
the proportion of
retransmitters
is inversely
proportional to the
number of nodes
~ 2
ν
Gateway Flooding Simulations (1D)
classical flooding
> 2 + o( 1)
3
ν
Gateway flooding
the proportion of
retransmitters
is approx. 70%
of the number
of nodes
MPR
flooding
→ more efficient
number of nodes in the area
Node density (ν)
[E. Baccelli, P. Jacquet, 2004]
→ analitycal results confirm this
behaviour when the network is dense
INRIA Hitachi
Ecole Polytechnique
11
Agenda
1. Background on Mobile Ad Hoc Networks
2. MANET routing overhead reduction
schemes
Comparison of optimized flooding
schemes
► Comparison of partial topology
schemes
3. MANET integration in the Internet
4. MANET
scaling
to
large
topologies
INRIA Hitachi
Ecole Polytechnique
12
Overhead Reduction:
Partial Topology
●
Def: Reducing the amount of
routing information that needs
network-wide flooding
Link state routing can still
provide routes with partial
link state advertizement
J
I
K
C
L
P
O
A
N
- using only links towards nodes in
a connected dominating set (CDS)
→ route stretching
- using only MPR selection links
→ no route stretching
[P. Jacquet, L. Viennot et al., 2002]
INRIA Hitachi
Ecole Polytechnique
MPR
H
B
G
MPR
M
Note: reactive protocols have
partial topology as main ideal
13
Partial Topology Algorithm
Simulations
Number of advertized links
Blue: full link state
Purple: CDS links
Light blue: MPR links
MPR topology
reduction is
efficient while
keeping routes
optimal
Number of nodes in the network
[E. Baccelli, T. Clausen, P. Jacquet, 2004]
INRIA Hitachi
Ecole Polytechnique
14
Overhead Reduction Summary
●
●
MPR flooding and MPR partial topology: simple & efficient
MPR techniques are extracts from OLSR (Optimized Link State
Routing):
●
OLSR = standard (the IETF’s MANET proactive routing protocol)
●
RFC 3626 [T. Clausen, P. Jacquet, 2003]
●
Link state routing, enhanced with MPR techniques
●
Proven, robust MANET routing solution (up to ~70 nodes with 802.11)
→focus on OLSR
INRIA Hitachi
Ecole Polytechnique
15
Agenda
1. Background on Mobile Ad Hoc Networks
2. MANET routing overhead reduction
schemes
3. MANET integration in the Internet
►OSPF on wireless
Address Autoconfiguration
4. MANET scaling to large topologies
INRIA Hitachi
Ecole Polytechnique
16
OSPF: Open Shortest Path
First
●
OSPF is the Internet’s traditional routing protocol
Backbone (Area 0)
Area 3
Area 1
Internet routers
Area 2
Advantages
Drawbacks
Scalable: address area hierarchy
•Heavy: complexity, overhead
Generic: modularity for
heterogeneous subnetwork tech.
•Not dynamic: slow to converge,
change in the routing → alarm
●
●
INRIA Hitachi
Ecole Polytechnique
17
OSPF Evolution
Internet growth:
–
more links
–
more mobile wireless
devices
OSPF challenged by:
–
More dynamics
–
Wired/wireless
heterogeneity
→IDEA: design an
OLSR-based module
for OSPF
FACTS:
1. OLSR is close to OSPF (proactive, link state)
2. OLSR is adapted to wireless & dynamics
3. OSPF is modular
INRIA Hitachi
Ecole Polytechnique
18
Designing OSPF’s Mobile
Ad Hoc Module
●
OSPF shortcomings on
wireless:
–
–
Overhead scalability
Database synchronization
Area 1
wOSPF
C
Area 2
ACK
B
D
A
PACKET
B retransmits
in vain
• Heavy:
new
neighbors
OSPF control
traffic is too big,
●
exchange
whole
databases
overhead
saturates
wireless
Positive
ACK links
fails
If
A
entered
a
new
area,
reconfiguration
– Cross-area mobility
of the• Not
nodeadapted
is needed
→ new address
to wired/wireless
B sends a packet to
A A movessynch. needs
heterogeneous
[J. Ahrenholz, E. Baccelli et al., IETF 2003] designs a new OSPF
extension (called wOSPF) based on OLSR techniques using:
- MPR flooding and partial topology
- A new database synchronization mechanism
●
Acknowledgements
Database exchange
INRIA Hitachi
Ecole Polytechnique
19
Wired/Wireless
Heterogeneity
●
●
wOSPF: potential mix of large numbers of fixed &
mobile nodes in the Internet
Heterogeneous needs for synchronization in the
network
Mobile wireless nodes generate
frequent updates (~1 second):
synchronization is wasteful
●
Traditional fixed nodes do not
generate frequent updates (30min):
synchronization is desireable
●
→ Need for a new heterogeneous synchronization scheme
INRIA Hitachi
Ecole Polytechnique
20
Database Signatures
(DbX) Synchronization
●
[E. Baccelli, T. Clausen, P. Jacquet, 2004]
1. Each node periodically emits hash of different
parts of its link state database (signature)
SYNCH A
2. Neighbors compare their respective
signatures & detect discrepancies
B
Signature
=?
New
Context
Signature
node ≠
Db
Independent
exchange
ACK
3. Nodes synchronize when
discrepancies are detected
Light-weight synchronization mechanism, for:
–Packet loss recovery (replacing ACK)
–Heterogeneous database synchronization
INRIA Hitachi
Ecole Polytechnique
21
number of exchanged IP addresses
Analytical Performance
Evaluation of DbX
traditional OSPF
database scanning
→light
weight
synch.
database signatures
proportional to log(n)
Size of the database (n) size of the network
[E. Baccelli, T. Clausen, P. Jacquet, 2004]
INRIA Hitachi
Ecole Polytechnique
22
wOSPF in a Nutshell
•wOSPF supports MANET techniques in OSPF framework
•MPR flooding & partial topology provides efficient
overhead reduction
•DbX provides an efficient database synchronization scheme
adapted to the wired/wireless heterogeneity
wOSPF
OSPF
overhead
scalability
INRIA Hitachi
Ecole Polytechnique
ACK issue
solved
Wired/wireless
synchronization
Area
mobility
23
Agenda
1. Background on Mobile Ad Hoc Networks
2. MANET routing overhead reduction
schemes
3. MANET integration in the Internet
OSPF on wireless
►Address Autoconfiguration
4. MANET scaling to large topologies
INRIA Hitachi
Ecole Polytechnique
24
IP Address Autoconfiguration
Nodes
123.12.134.53
●
123.12.134.110
123.12.134.23
MANET
Internet
123.12.134.54
●
123.12.134.45
123.12.134.78
N
New node.
Address?
●
Prior to routing: nodes
should be uniquely
identified
In the Internet:
identity is given by IP
address
MANET characteristics
challenge Internet
addressing
→ Need for new autoconfiguration
schemes, adapted to MANETs
●
INRIA Hitachi
Ecole Polytechnique
●
a “new” node must be
configured
traditional autoconf. tools fail 25
Light
Autoconf
for
OLSR
[E. Baccelli, T. Clausen, 2005]
1. Configured nodes advertize
ADDR-BEACON periodically
OLSR Nodes
Proxy
Autoconf
C
ADDR-CONFIG
HELLO
2. A new node listens for
ADDR-BEACON
3. A new node registers with
a configurating node
NN N
NOA-OLSR
4.
Temporary
address
assignment
Light
[K.
Mase,
new New Node
+ HELLO tracking C. Adjih, 2005]
OLSR
OLSR
Autoconf
node
5. The configurating node uses OLSR
connectivity to act as autoconf proxy
6. Permanent
address
assignment,
the
Manual Auto.
Connected Connected
Disconnected
Partition
Merge
DHCP
nodeone
cannode
take part in the network
config
with
without newwith
DHCP
DHCP
configured
INRIA Hitachi
Ecole Polytechnique
26
Conclusions on MANET
Integration in the Internet
●
●
A suite of new protocols is needed to
integrate MANETs in the Internet
{wOSPF or OLSR} + autoconfiguration
provides a solution for local MANET mobility
integration
MANET
integration
standalone
MANET
INRIA Hitachi
Ecole Polytechnique
connected
MANET
connected
scalable
MANET
27
Agenda
1. Background on Mobile Ad Hoc Networks
2. MANET routing overhead reduction
schemes
3. MANET integration in the Internet
4. MANET scaling to large topologies
►Introduction to MANET scaling
Horizontal scaling with OLSR Fisheye
Vertical
Scaling
with
OLSR
Trees
INRIA Hitachi
Ecole Polytechnique
28
Scaling with Mobility in the
Internet
●
●
●
●
Internet scaling: tied to IP address location & low
mobility
Integrating mobile devices: a challenge for Internet
scaling
MANETs can integrate fixed & wireless mobile
devices
MANET theoretical
practical
theoretical
testing
OLSR
Internet
(802.11) dolimit
scalability
But MANETs
not scale yet
1 ~26
nodes
INRIA Hitachi
Ecole Polytechnique
~212
nodes
size of the
Internet
~230
~2128
nodes
nodes
29
Agenda
1. Background on Mobile Ad Hoc Networks
2. MANET routing overhead reduction
schemes
3. MANET integration in the Internet
4. MANET scaling to large topologies
Introduction to MANET scaling
►Horizontal scaling with OLSR Fisheye
Vertical
Scaling
with
OLSR
Trees
INRIA Hitachi
Ecole Polytechnique
30
MANET Horizontal
Scaling
• Theory: optimal network capacity is O(√n)
[P. Gupta, P. Kumar, 1999]
Total network capacity
• Real protocols: network capacity tends to crumble when
the numbers of nodes/users increases in the network
OLSR
Network population (n)
[E. Baccelli, P. Jacquet, C. Adjih et al, 2004]
→ overhead limits the number of nodes in a MANET
INRIA Hitachi
Ecole Polytechnique
31
Fishey OLSR
e
Fisheye: a simple function periodically
updating the scope of flooded messages
[G. Pei, M. Gerla, T. Chen, 2000]
●
●
[C. Adjih, E. Baccelli, P. Jacquet et
al, 2004] combines OLSR with a
simple Fisheye strategy →
Fisheye OLSR
• with Fisheye OLSR routing:
network capacity continues to grow
with more nodes in the network!!!!
INRIA Hitachi
Ecole Polytechnique
S
32
Total network capacity (nominal)
Analysis of
Fisheye OLSR Capacity
capacity continues to grow!!
with Fisheye OLSR
O(√n)
OLSR
Network size (n)
INRIA Hitachi
Ecole Polytechnique
[C. Adjih, E. Baccelli, P. Jacquet et al, JCN 2004]
33
ZOOM: why does Fisheye
OLSR scale? Where does √n
come from?
Fisheye bounding overhead
• Basic OLSR’s overhead
proportional to n
Overhead
• Fisheye strategy bounds
OLSR’s overhead
Distance (hop count)
INRIA Hitachi
Ecole Polytechnique
• Similar to Gupta & Kumar
minus overhead “tax”
34
Agenda
1. Background on Mobile Ad Hoc Networks
2. MANET routing overhead reduction
schemes
3. MANET integration in the Internet
4. MANET scaling to large topologies
Introduction to MANET scaling
Horizontal scaling with OLSR Fisheye
►Vertical
Scaling
with
OLSR
Trees
INRIA Hitachi
Ecole Polytechnique
35
MANET
Vertical
OLSR
Trees Scaling
●
Fact: the main MANET
solutions don't use
clustering, hierarchical
networking
R
→ Clustering and hierarchical
routing can scale
[E. Baccelli, 2005] tree-based
dynamic clustering (similar to
Gateway trees)
●
Hierarchical routing
●
INRIA Hitachi
Ecole Polytechnique
R
“super” OLSR
between trees
(between roots)
36
Short on MANET Scaling
●
●
Currently: MANETs are limited in the number of
nodes they can manage
OLSR + specific scaling techniques (OLSR Trees,
Fisheye OLSR) can scale to much bigger
topologies
Fisheye OLSR
+ trees scalability
1
26
nodes
INRIA Hitachi
Ecole Polytechnique
?
2128
nodes
37
Perspective on
Internet & Wireless
●
ubiquitous
wireless
Internet
We can anticipate:
–
Massive ad hoc topologies
–
Hybrid networks
–
Ubiquitous network
►A new suite of protocols is
needed for ubiquitous wireless
Internet
INRIA Hitachi
Ecole Polytechnique
mobile
ad hoc
nodes
traditional
Internet
fixed
core
Research challenges:
•MANET Scalability
•MANET Security
•MANET Multicast
•MANET Integration
38
Related Publications
IETF
Publications:
Academic Publications:
●
●
●
●
●
●
E. Baccelli, T. Clausen, P. Jacquet,
``Ad-hoc and Internet Convergence:
Adapting OSPF-style Database
Exchanges for Ad-hoc Networks,''
HET-NET, 2004.
C. Adjih, E. Baccelli, P. Jacquet,
``Link State Routing in Wireless Ad
Hoc Networks,'' MILCOM, 2003.
●
●
E. Baccelli, R. Rajan, ``Monitoring
OSPF Routing,'' IM, 2001.
E. Baccelli, P. Jacquet, ``Diffusion
Mechanisms for Multimedia
Broadcasting in Mobile Ad Hoc
Networks,'' IMSA, 2004.
E. Baccelli, ``OLSR Trees: A Simple
Clustering Mechanism for OLSR,''
MED-HOC-NET, 2005.
C. Adjih, E. Baccelli, T. Clausen, P.
Jacquet, R. Rodolakis, ``Fish Eye
OLSR Scaling Properties,'' IEEE
Journal of Communication and
Networks, 2004.
INRIA Hitachi
Ecole Polytechnique
●
●
●
J. Ahrenholz, E. Baccelli, T.
Clausen, T. Henderson, P.
Jacquet, P. Spagnolo,
``OSPFv2 Wireless Interface
Type,'' IETF I-draft, 2004.
E. Baccelli, F. Baker, M.
Chandra, T. Henderson, J.
Macker, R. White, ``Problem
Statement for OSPF
Extensions for Mobile Ad Hoc
Routing,'' IETF I-draft, 2003.
E. Baccelli, T. Clausen, R.
Wakikawa, ``NEMO Route
Optimisation Problem
Statement,'‘ IETF I-draft, 2004.
E. Baccelli, T. Clausen, P.
Jacquet, ``DB Exchange for
OSPFv2 Wireless Interface
Type,'‘ IETF I-draft, 2004.
E. Baccelli, T. Clausen,
``Simple MANET Address
Autoconfiguration,'‘ IETF Idraft, 2005.
39
Thank you.
INRIA Hitachi
Ecole Polytechnique
40