Leipzig
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Leipzig as PDF for free.
More details
- Words: 1,102
- Pages: 28
Routing in Mobile Adhoc Networks
Dr. Miguel Sánchez López Computer Engineering Department Universidad Politécnica de Valencia, Spain November 2008
Outline
Mobile adhoc networks on IETF: MANET
Problem statement
Routing survey
Sensor networks
Mobile Adhoc Networks
Selfconfiguring network of mobile routers
Wireless communications
Nodes are both: host & routers
No other infrastructure available
Nodes may or may not be mobile
Standard routing protocols do not fit well
A new group (MANET) was created on IETF (1997)
Different protocols have been proposed ever since
Infrastructure Mobile Networks
Mobile Adhoc Networks
MANET
Mobile: not necessary
Multihop
Adhoc: no other infrastructure present
Collaborative routing compensates the lack of existing infrastructure:
Selfcreated or spontaneous network
Hostile environment, disaster recovery, exploration
Each node is a [mobile] router and host
Why existing protocols do not work?
Existing protocols assume a fixed infrastructure:
May include wireless links
Routers can come and go, but few changes
Hosts do not move and routers do not move
Mobile IP solves host mobility (not routers')
Routers uptime is expected to be high
Problem statement
Mobile adhoc networks need ...
Unicast routing.
Multicast and broadcast routing
Wireless links exhibit poorer BER than wired
Nodes may have power limitations
Fully distributed solutions
Energy awareness:
Maximize network survivability
Unicast routing
Any host to any host communication
Two basic approaches for route discovery:
Ondemand (reactive)
Proactive
Several ”borrowed” ideas:
Distance vector algorithm
Source routing
Link state routing
Hierarchical routing
Broadcast routing
Different problem than unicast Wireless may make it easier:
Broadcast nature of physical media
Flooding is not efficient Multicast is similar
Ondemand routing
Routes are ”discovered” when they are needed Special probe packet is broadcasted by source node
Which route will use the answer?
Eventually, it will reach the destination, who will reply back Backward learning or source routing
Examples:
AODV or DSR
DSR: Dynamic Source Routing
RFC 4728
It's ondemand
Route request are broadcasted
Data is routed using source routing:
Sender lists the sequence of routers
Replies to route requests are received ”backwards”
AODV: Ad hoc OnDemand Distance Vector
RFC 3561
Similar approach than DSR:
Ondemand route discover
No source routing though:
Routing tables are used instead
Route discovery fills the routing tables
Distance vector:
Avoids routing loops & count to infinity
Route entries have a limited lifetime
Backward learning
You learn by listening, not by asking Route discovery packets may store forwarding sequence
Use the route request path backwards
It is the ONLY technique of ECMF:
Explicit Control Message Free protocol
Both DSR and AODV use it too
Routes maintenance
How do you know a neighbor is still active?
Overhear other transmissions
Acknowledgments on forwarded packets
Neighbor sensing protocol (Hello packets)
What to do if a route is broken?
Detect
Fix
Link state routing
Key concept is Dijkstra algorithm
Algorithm needs to know the cost of each link
Information not available at nodes, it needs to be transmitted from those who know it
Wireless links are created and destroyed
Chicken and egg: how to route link state?
Best routes to reach each possible destination inside a graph
Flooding / Multipoint relays
OLSR: Optimized Link State Routing
RFC 3626
It's a proactive routing protocol
It's based on link state routing
It maintains a set of multipoint relays:
Optimization over flooding link state information
Periodic advertisement
Table driven
OLSR
HELLO messages for topology update
Neighbor list
Link ”quality”
Detection of link symmetry
Election of MPR nodes
Periodic link state data flooded by MPRs
May also be triggered by link failures
DSDV: Destination Sequenced Distance Vector
Based on BellmanFord algorithm Destination node route is stored with a sequence number to tell apart old information
Proactive
Avoid routing loops It's a precursor of AODV
FSR: Fisheye State Routing
It's a proactive unicast routing protocol
It uses links state approach
FSR reduces the link state information exchange to the local neighborhood
Same as fisheye lenses, detail high is in the close neighborhood, distant links details are not known
Link state information exchange has different rates
TORA: Temporally Ordered Routing Algorithm
TORA is based on link reversal concept
It's a reactive protocol
It creates a set of routes so traffic always flows “downstream” for a given destination node Message exchanges help create a Directed Acyclic Graph of the network
This DAG is used for routing later
ZRP: Zone Routing Protocol
Hybrid approach: proactive + reactive
Intrazone Routing Protocol (proactive)
Interzone Routing Protocol (reactive)
Zones are dhops around each node It's more like a framework as different protocols may be used for each behavior.
Hierarchical Routing
Instead of a flat space of node there are several levels:
For example: clusters with clusterheads
Different levels may use different routing protocols
Power management
Battery operated systems have limited energy source st
Network metric: time for 1 dead node
Power management is a crosslayer task:
Transmission power control
Timed mediaaccess
Sleep or hibernated nodes
Poweraware routing
Adhoc networks security
Fully distributed security?
Central or replicated authentication database
Secure routing
Secure data exchange
Secure peer authentication
Threshold cryptography
toutofn
Multicasting
Not the same thing as unicasting:
Flooding can work but inefficiently
Treebased multicast more efficient:
Tree building/maintenance process
Examples: AMRoute, AMRIS, MAODV
Others are based on a mesh
Different protocols are needed
ODMRP, CAMP
Sensor networks
Special case of adhoc networks
Some nodes may be mobile
Many nodes tied to fixed infrastructure (i.e: buildings, containers, etc)
Monitoring use
Batteryoperated, energy scavenging
Long sleep times
Small size, small processing power
Geocasting
It's possible to base addressing on location
It means node address will change when moved to a new location There are several routing algorithms built on the idea of using location information:
Then messages can be sent to certain areas of the network
LAR, DREAM, GLS
Dr. Miguel Sánchez López Computer Engineering Department Universidad Politécnica de Valencia, Spain November 2008
Outline
Mobile adhoc networks on IETF: MANET
Problem statement
Routing survey
Sensor networks
Mobile Adhoc Networks
Selfconfiguring network of mobile routers
Wireless communications
Nodes are both: host & routers
No other infrastructure available
Nodes may or may not be mobile
Standard routing protocols do not fit well
A new group (MANET) was created on IETF (1997)
Different protocols have been proposed ever since
Infrastructure Mobile Networks
Mobile Adhoc Networks
MANET
Mobile: not necessary
Multihop
Adhoc: no other infrastructure present
Collaborative routing compensates the lack of existing infrastructure:
Selfcreated or spontaneous network
Hostile environment, disaster recovery, exploration
Each node is a [mobile] router and host
Why existing protocols do not work?
Existing protocols assume a fixed infrastructure:
May include wireless links
Routers can come and go, but few changes
Hosts do not move and routers do not move
Mobile IP solves host mobility (not routers')
Routers uptime is expected to be high
Problem statement
Mobile adhoc networks need ...
Unicast routing.
Multicast and broadcast routing
Wireless links exhibit poorer BER than wired
Nodes may have power limitations
Fully distributed solutions
Energy awareness:
Maximize network survivability
Unicast routing
Any host to any host communication
Two basic approaches for route discovery:
Ondemand (reactive)
Proactive
Several ”borrowed” ideas:
Distance vector algorithm
Source routing
Link state routing
Hierarchical routing
Broadcast routing
Different problem than unicast Wireless may make it easier:
Broadcast nature of physical media
Flooding is not efficient Multicast is similar
Ondemand routing
Routes are ”discovered” when they are needed Special probe packet is broadcasted by source node
Which route will use the answer?
Eventually, it will reach the destination, who will reply back Backward learning or source routing
Examples:
AODV or DSR
DSR: Dynamic Source Routing
RFC 4728
It's ondemand
Route request are broadcasted
Data is routed using source routing:
Sender lists the sequence of routers
Replies to route requests are received ”backwards”
AODV: Ad hoc OnDemand Distance Vector
RFC 3561
Similar approach than DSR:
Ondemand route discover
No source routing though:
Routing tables are used instead
Route discovery fills the routing tables
Distance vector:
Avoids routing loops & count to infinity
Route entries have a limited lifetime
Backward learning
You learn by listening, not by asking Route discovery packets may store forwarding sequence
Use the route request path backwards
It is the ONLY technique of ECMF:
Explicit Control Message Free protocol
Both DSR and AODV use it too
Routes maintenance
How do you know a neighbor is still active?
Overhear other transmissions
Acknowledgments on forwarded packets
Neighbor sensing protocol (Hello packets)
What to do if a route is broken?
Detect
Fix
Link state routing
Key concept is Dijkstra algorithm
Algorithm needs to know the cost of each link
Information not available at nodes, it needs to be transmitted from those who know it
Wireless links are created and destroyed
Chicken and egg: how to route link state?
Best routes to reach each possible destination inside a graph
Flooding / Multipoint relays
OLSR: Optimized Link State Routing
RFC 3626
It's a proactive routing protocol
It's based on link state routing
It maintains a set of multipoint relays:
Optimization over flooding link state information
Periodic advertisement
Table driven
OLSR
HELLO messages for topology update
Neighbor list
Link ”quality”
Detection of link symmetry
Election of MPR nodes
Periodic link state data flooded by MPRs
May also be triggered by link failures
DSDV: Destination Sequenced Distance Vector
Based on BellmanFord algorithm Destination node route is stored with a sequence number to tell apart old information
Proactive
Avoid routing loops It's a precursor of AODV
FSR: Fisheye State Routing
It's a proactive unicast routing protocol
It uses links state approach
FSR reduces the link state information exchange to the local neighborhood
Same as fisheye lenses, detail high is in the close neighborhood, distant links details are not known
Link state information exchange has different rates
TORA: Temporally Ordered Routing Algorithm
TORA is based on link reversal concept
It's a reactive protocol
It creates a set of routes so traffic always flows “downstream” for a given destination node Message exchanges help create a Directed Acyclic Graph of the network
This DAG is used for routing later
ZRP: Zone Routing Protocol
Hybrid approach: proactive + reactive
Intrazone Routing Protocol (proactive)
Interzone Routing Protocol (reactive)
Zones are dhops around each node It's more like a framework as different protocols may be used for each behavior.
Hierarchical Routing
Instead of a flat space of node there are several levels:
For example: clusters with clusterheads
Different levels may use different routing protocols
Power management
Battery operated systems have limited energy source st
Network metric: time for 1 dead node
Power management is a crosslayer task:
Transmission power control
Timed mediaaccess
Sleep or hibernated nodes
Poweraware routing
Adhoc networks security
Fully distributed security?
Central or replicated authentication database
Secure routing
Secure data exchange
Secure peer authentication
Threshold cryptography
toutofn
Multicasting
Not the same thing as unicasting:
Flooding can work but inefficiently
Treebased multicast more efficient:
Tree building/maintenance process
Examples: AMRoute, AMRIS, MAODV
Others are based on a mesh
Different protocols are needed
ODMRP, CAMP
Sensor networks
Special case of adhoc networks
Some nodes may be mobile
Many nodes tied to fixed infrastructure (i.e: buildings, containers, etc)
Monitoring use
Batteryoperated, energy scavenging
Long sleep times
Small size, small processing power
Geocasting
It's possible to base addressing on location
It means node address will change when moved to a new location There are several routing algorithms built on the idea of using location information:
Then messages can be sent to certain areas of the network
LAR, DREAM, GLS
Related Documents
Leipzig
November 2019 19
Leipzig Paper
April 2020 33
Https___webmail.imn.htwk-leipzig
June 2020 11
Oper Leipzig Er+te
June 2020 7
Bmw Planta Leipzig
June 2020 7