Transcript Three Challenges in Reliable Data Transport over Heterogeneous

Ad hoc Routing: Issues and Algorithms
• Why we study this paper
identify the issues of routing support in mobile
ad hoc networks
 understand some design options for ad hoc
routing support schemes
 algorithm overviews of a few algorithms

• New trends in ad hoc routing
Mobile Ad Hoc Networking (MANET)
• No backbone infrastructure, typically operate over a single
wireless channel
• dynamic topologies: nodes are free to move arbitrarily
• bandwidth-constrained, variable capacity links
• energy-constrained operation
• limited physical security
• may have both unicast and multicast/broadcast traffic
• typically assume reliable broadcast at the MAC/link layer
• in the near term, MANET functions


as stub networks (RFC2501): all traffic carried by MANET nodes
will either be sourced or sinked within the MANET
NOT as transit networks carrying traffic that enters and then leaves
MANET
Goals for Ad Hoc Routing
• Near-term goal (RFC2501):



provides for effective operation over a wide range of mobile
networking “contexts” (i.e. a set of MANET characteristics)
supports connectionless IP service: IP layer mobile routing
reacts efficiently to topological changes and traffic demands
while maintaining effective routing in a MANET context
• Qualitative properties of MANET routing protocols:





distributed operation: no centralized solution
loop-freedom: avoid problems such as a small fraction of
packets spinning around in the net for arbitrary time periods
demand-based operation: routing algorithms adapt to the traffic
pattern in the net on a demand or need basis
proactive operation: flip-side of demand-based operation
security, sleep period operation, unidirectional link support.
Goals for Ad Hoc Routing (contd)
• Network context

network size (# of nodes), network connectivity (avg degree of a node),
topological rate of change, link capacity, fraction of unidirectional links,
traffic patterns, mobility (more on topological correlation), fraction &
frequency of sleeping nodes
• Quantitative metrics to assess ad hoc routing protocols:




end-to-end data throughput and delay
route acquisition time: of particular concern with on demand
routing algorithms
percentage of out-of-order delivery
efficiency: internal measure of its effectiveness
• average number of data bits transmitted/data bit delivered
• average number of control bits transmitted/data bit delivered
• average number of control and data packets transmitted/data packet
delivered
Some Architectural Considerations
• Link level operation

ability to detect link appearances & failures in the
presence of changing topology:
• periodic probing using overhead packets (faster link status
sensing)
• lack of link-level ACKs of transmitted message packets (slower
sensing, no overhead)
• shortest path routing: is it worth the cost ?



changing topology: slow versus fast
congested network: light versus heavy
how to handle the gray area ? adaptive
• hard state versus soft state
Brief Review on Shortest-path Routing
• Internet supports shortest-path routing
• Properties for shortest path:


subpaths of shortest paths are shortest paths
the weight of a shortest path is the sum of the weights of its subpaths
• Dijkstra’s algorithm: builds up a shortest path tree by
computing the weighted breadth first tree from the source
• Bellman Ford algorithm: builds a shortest-path tree by
incrementally expanding the permissible set of nodes that are
allowed to be intermediate hops
• Distributed Bellman Ford Algorithm
• distance vector and link state routing


distance vector: exchange vectors of distance estimates to
destinations (e.g. RIP)
link state: maintain the entire network topology at all routers (OSPF)
Design Options in Ad Hoc Routing
• Who serve as routers:



every mobile host is a router
a subset of the nodes are routers (e.g., due to energy concerns)
every host is a router but only a subset of routers are used to generate
routes (virtual backbone concept)
• what is the neighborhood info to propagate

link state, distance vectors, known routes
• metrics for route computation

weighted shortest path, interference metrics, congestion metrics,
power/energy metrics, throughput metrics
• how many routes are maintained


single route for a source-destination pair
multiple routes for a src-dest pair
• when to generate routes

static versus on demand
Destination-Sequenced Distance-Vector Routing
(DSDV)
• Based on the Bellman Ford routing algorithm with
improvements such as freedom from loops in routing table
• each node maintains a routing table


recording all of the possible destinations and the distance to each
destination
each entry is marked with a sequence number assigned by the
destination node
• routing tables are periodically transmitted throughout the
network
• route updates via two types of packets:
 full dump packets carrying all available routing info
 incremental packets carrying the change only since last
full dump
Destination-Sequenced Distance-Vector Routing
(DSDV)
• Operations using sequence number

associate monotonically increasing sequence number with the
neighborhood update information. When info about a destination is
being passed, the latest sequence number generated by that
destination is used. This enables source nodes to distinguish fresh
info from stale info

use sequence numbers to make routing loop-free

• each node generates an even sequence number every time it
propagates its neighborhood update
• whenever a node detects a loss of connectivity with a neighbor, it
creates a neighborhood update, with an odd sequence number
that is generated by incrementing the known seq number for the
neighborhood by 1
• if the destination generates a new neighborhood update, it
receives precedence over the loss of connectivity update
reduce the frequency of updates by using some stability heuristics:
damping route update propagation by an amount of time it takes for a
route to settle once a change has been advertised.
Temporally-Ordered Routing Algorithm (TORA)
• Basic ideas:







source initiated routing based on link reversal
decouples the generation of potentially far-reaching control message
propagation from the rate of topological changes: localizing
messaging to a small set of nodes near the change
its operation can be biased towards high reactivity and bandwidth
conservation rather than routing optimization
routes established only when necessary by constructing a directed
acyclic graph rooted at the destination using a “query/reply” process
reaction to link failure only when necessary (i.e., when a node loses
its last downstream link)
scope of failure reactions minimized (i.e., the # of nodes that must
participate)
no reaction to link activation
Temporally-Ordered Routing Algorithm (TORA)
• Detailed operations



each router is assigned a “height”, links are directed from a higher
router to a lower router, always set a UPSTREAM router with height
higher than the DOWNSTREAM routers
link reversal: each node i other than the destination keeps a list of its
neighboring nodes j that have reversed the direction of the
corresponding links (i, j). At each iteration, each node i that has no
outgoing links reverses the directions of the links (i,j) for all j that do
not appear on the list, and empties the link
when a failure happens (a node loses its last downstream link &
becomes a local minimum), the node selects a new height such that it
becomes a global maximum. Then, the failure propagates outward
from the point of the original failure.
Ad Hoc On-Demand Distance Vector (AODV)
• Key features



builds upon DSDV, thus a distance vector algorithm
using destination sequencing for route updates
improves DSDV by generating routes on demand (instead
of maintaining a complete list of routes), thus reducing
the number of required broadcasts
authors classify it as a pure on-demand route acquisition
system, since nodes that are not on a selected path do not
maintain routing info or participate in routing table
exchanges
Ad Hoc On-Demand Distance Vector (AODV)
• Path discovery process -- when a src does not have a route to
the desired destination:

limited range broadcast used for neighborhood discovery: source
broadcasts a route request (RREQ) packet to its neighbors, which
then forward RREQ to its neighbors, until either the destination or a
“fresh enough” route to the destination is located
• routes are cached by intermediate nodes for some time since
last use


reply to RREQ only if they have a route to the destination whose
corresponding destination sequence number is greater or equal to that
contained in the RREQ
When forwarding RREQ, record in their route tables the address
from which the 1st copy of the broadcast packet is received, thereby
establishing a reverse path
AODV
• When RREQ reaches destination or an intermediate node
with fresh enough route:




responds with a route reply packet back to the neighbor from which it
first receives RREQ
When RREQ is routed back along the reverse path, nodes along this
path set up forward route entries in their route tables which point to
the node from which RREQ came.
A route timer is associated with each route entry: if it is not used in
its lifetime, delete the entry
AODV only supports symmetric link (RREP and RREQ follow the
same route, but in reverse directions)
• link failure management:



infinite metric assigned to broken links
if a node along the route moves, its upstream neighbor detects it and
forwards a notification message (RREQ with infinite metric)
link breakage triggers notification back to uses of formerly active
links (further upstream nodes) until the src is reached. The src may
re-initiate route discovery
Dynamic Source Routing (DSR)
• An on-demand routing protocol based on source routing
• Designed for the scenario where traffic flows only from a
few source nodes to a few destination nodes
• source and destination (as well as participating nodes) gather
routing info into caches which is used to compute source
routes to the desired dest., through the exchange of flooded
query and reply packets containing full path information
• once discovered, routes are used until they fail as determined
by the failure of attempted message transmissions
• appropriate for communication with infrequently accessed
destinations and makes sense when maintaining continuous
routing from many sources is not necessary
Dynamic Source Routing (DSR)
• Route discovery: the source





checks whether it has a valid route entry in its cache
if no, broadcast a route request packet
each intermediate node checks whether it knows of a route to the
destination. If NO, adds its own address to the route record of the
packet and forwards the packet along its outgoing links
“route request” packet contains a route record yielding the sequence
of hops taken.
“route reply” is generated when the request reaches either the
destination or an intermediate node that has a valid route to the
destination; route record is placed in the reply message.
• once discovered, routes are used until they fail as determined
by the failure of attempted message transmissions
Further Discussions
• Goals revisited
route optimality, fast route reactivity, scalability
 topological changes: slow versus fast

• flooding, multi-path forwarding, single shortest path
• other approaches ?

“virtual backbone”, hierarchical design,
landmarks, geographic routing...
New Trends in Ad Hoc Routing
• New requirements for routing protocols
Energy efficiency
 Security
 Quality of service
 Multicast or anycast

• Changes in technology
Location information
 No mobility (sensor network)
