Transcript MN_12_Routing_Protocols_For_AdHoc_Networks

Routing Protocols for Ad-Hoc Wireless
Networks
Lecture#12
Traditional Routing
 A routing protocol sets up a routing table in routers
 A node makes a local choice depending on global topology
Routing Table AT 1
2
Traditional Distance Vector Routing
 Based on periodic exchanges of neighbor information
(connectivity and cost)
 Changes at one node propagate slowly through the network
 Strategies needed to avoid the “count to infinity” problem
(problems with fast topology changes)
• Poisoned-reverse
• Split-horizon
 Potential problems …
• Unreachable regions
• Routing loops
3
Tables
A
Dest. Next Metric …
A
A
0
B
B
1
C
B
3
1
B
Dest. Next Metric …
A
A
1
B
B
0
C
C
2
2
C
Dest. Next Metric …
A
B
3
B
B
2
C
C
0
4
Update
B broadcasts the new routing
information to his neighbors
Routing table
is updated
A
Dest. Next Metric …
A
A
0
B
B
1
C
B
3 2
(A, 1)
(B, 0)
(C, 1)
1
(A, 1)
(B, 0)
(C, 1)
B
Dest. Next Metric …
A
A
1
B
B
0
C
C
1
1
C
Dest. Next Metric …
A
B
3 2
B
B
1
C
C
0
5
New Node
broadcasts to update
tables of C, B, A with
new entry for D
(A, 1)
(B, 0)
(C, 1)
(D, 2)
(A, 2)
(B, 1)
(C, 0)
(D, 1)
1
(D, 0)
1
A
B
Dest. Next Metric …
A
A
0
B
B
1
C
B
2
D
B
3
Dest. Next Metric …
A
A
1
B
B
0
C
C
1
D
C
2
1
C
D
Dest. Next Metric …
A
B
2
B
B
1
C
C
0
D
D
1
6
Broken Link
1
1
A
B
Dest. Next Metric …
…
…
…
D
B
3
Dest.c Next Metric …
…
…
…
D
C
2
1
C
D
Dest. Next Metric …
…
…
…
B
1
D
D

7
Loops
(D, 2)
(D, 2)
1
1
A
B
Dest. Next Metric …
…
…
…
D
B
3
Dest. Next Metric …
…
…
…
D
C
2
1
C
D
Dest. Next Metric …
…
…
…
D
B
3
8
Count to Infinity
(D,5)
(D,4)
(D,4)
(D,3)
(D,2)
(D,2)
1
A
Dest. Next
…
…
D
B
1
B
Metric …
…
3, 5, …
Dest.c Next Metric …
…
…
…
D
C
2, 4, 6…
1
C
D
Dest. Next Metric …
…
…
…
D
B
3, 5, …
9
Interaction with Static Internet
 Two network types
• Transit network: a datagram can enter and then leave the network
• Stub network: the network is either the sink or source for all datagrams
 MANETs are envisioned as being only stub network (at least for
now)
• Reduces power and processing demands
• Simplifies routing interaction
• Mobile IP allows connectivity with the traditional static Internet
10
MANET vs.. Traditional Routing
 Traditional routing algorithms are likely to be …
• Inefficient due to slow convergence times (e.g., using distance vector algorithms
as in RIP)
• Non-functional due to large amounts of data or inability to deal with asymmetric
links
 MANET routing must rely on data link information, not just network
layer updates
• Link layer determines connectivity and quality of links




Centralized approaches are too slow and not robust enough for MANET
All (or almost all) nodes in a MANET may be routers
Long-lived circuits cannot be used in MANETs
Path length (hop count) may not be the best metric for routing in
MANETs
11
Routing and Mobility
 Goal of routing protocols
• decrease routing-related overhead
• find short routes
• find “stable” routes (despite mobility)
 Issues
• Frequent route changes
• Amount of data transferred between route changes may be much
smaller than traditional networks
• Route changes may be related to host movement
• Low bandwidth links
12
Issues in Designing a Routing Protocol for Ad
Hoc Wireless Network
 Mobility
• Frequent path loss due to the movement of intermediate nodes or
the end nodes
• Requires faster convergence time
• Wired routing protocols have slow convergence, therefore, not
suitable for ad hoc networks
 Limited bandwidth
• Imposes constraint on routing protocols in maintaining the
topological information
• Frequent changes in topology makes it difficult to maintain a
consistent view of the topological information
• Require more control overhead which results in more BW wastage
13
Issues in Designing a Routing Protocol for Ad
Hoc Wireless Network
 Error-Prone Shared Broadcast Radio Channel
• Wireless links have time varying characteristics in terms of link capacity
and link error probability
• Requires that routing protocols to interact with the MAC layer to find an
alternate routes through better quality links
• Transmission results in collision of data packets and control packets
• Required to find paths with less congestion
 Hidden and exposed terminal problems
• Collision of data and control packets and under utilization of BW is
attributed to hidden and exposed node problems
 Resource constraints
• Battery life and processing power
• Routing protocols must optimally used these resource
14
Qualitative Characteristics of an Ideal Routing Protocol
 Fully distributed
• Centralized routing involves high control overhead and are not scalable
• Distributed routing more tolerant
• Avoids the risk of single point failure
 Adaptive to frequent topology changes
 Minimum route computation and maintenances
 Localized
• Global state involves a huge state propagation control overhead








Loop free
Free from stale route
Unidirectional link support
Packet collision minimum by limiting the broadcast
Convergence must be quick
Optimally use the resources
Each node should try to store the stable route information only
Provide certain level of QoS
15
Quantitative Performance Metrics
 End-to-end throughput
• External measure of routing effectiveness
 End-to-end delay
• External measure of routing effectiveness
 Route acquisition time
• Of particular concern with on-demand routing algorithms
 Percentage of out-of-order datagram deliveries
• Affects performance of higher-layer protocols like TCP
 Efficiency (internal measures)
• Ratio of average number of data bits transmitted to average number of data
bits delivered
• Ratio of average number of control bits transmitted to average number of data
bits delivered
• Ratio of average number of control and data packets transmitted to average
number of data packets delivered
16
Performance Factors
 Network size
• Number of nodes
 Network connectivity
• Average degree of a node
 Rate of change of the topology
• Speed at which the network topology is changing
 Link capacity
• Effective data rate (bits/second) after affects of packet loss, coding, multiple access
overhead, etc
 Fraction of unidirectional links
 Traffic patterns
• Uniform versus non-uniform destinations
• Bursty versus non-bursty traffic
 Mobility
• Model for node mobility
 Fraction and frequency of sleeping nodes
17
Classification of Routing Protocols
 Based in routing information update mechanisms
• Proactive or table driven protocols
• Reactive or on-demand routing protocols
• Hybrid routing protocols
 Based on the use of temporal information on routing
• Use the temporal information regarding the lifetime of wireless links
and the lifetime of the paths selected
• Routing protocols using past temporal information
• Use past status of the link or the status of the link at the time of routing
• Routing protocols that use future temporal information
• Life time of wireless links, remaining battery life, prediction of location,
and prediction of link availability
18
Classification of Routing Protocols
 Based on the routing topology
• Internet use hierarchical routing topology in order to reduce the state information
maintained at the core routers
• Flat topology routing protocols
• Use flat addressing scheme
• Presence of a unique addressing scheme in an ad hoc network
• Hierarchical topology routing protocols
• Make use of a logical hierarchy in the network and an associated addressing scheme
• Could be based on geographical information or it could be based on hop distance
 Based on the utilization of specific resource
• Power aware routing
• Aims at minimizing the battery power, routing decisions are based on either globally
or locally
• Geographical information assisted routing
• Reduce the control overhead by effectively utilizing the geographical information
available
19
Classification of Routing Protocols
20
Based in Routing Information
Update Mechanisms
Table Driven Routing Protocols
(Proactive Protocols)
DSDV, WRP, CGSR, STAR
Protocol Trade-offs
 Proactive protocols
• Always maintain routes
• Little or no delay for route determination
• Consume bandwidth to keep routes up-to-date
• Maintain routes which may never be used
 Reactive protocols
• Lower overhead since routes are determined on demand
• Significant delay in route determination
• Employ flooding (global search)
• Control traffic may be bursty
 Which approach achieves a better trade-off depends on the
traffic and mobility patterns !!
22
Destination Sequenced Distance Vector (DSDV)
 Each route table at each of the nodes, lists all available destinations
and the number of hops to each
 Contains the shortest distance and the first node on the shortest
path to every other node in the network
 Each entry is tagged with a sequence number that is originated by
the destination node
 Each node periodically transmits updates
• These updates indicate which nodes are accessible from each node and
number of hops to reach them
 It incorporates table updates with increasing sequence number tags
to prevent loops, to counter the count-to-infinity problems, and for
faster convergence
 Routing information is advertised by broadcasting or multicasting
• Packets are transmitted periodically and incrementally
23
Route Advertisements
 Data is kept for a length of time between the arrival of the first and
the arrival of the best route
• Advertisement of possibly unstable routes is delayed to reduce the number of
rebroadcasts (damping fluctuations)
 DSDV requires each mobile node to advertise its own routing table
to each of its current neighbors
 Entries may change fairly dynamically
 Each mobile computer agrees to relay data packets to other
computers upon request
 Mobile computer may exchange data with any other computer in a
group
• Even if the target is not within the range of direct communication
24
Route Establishment in DSDV
25
Route Maintenance in DSDV
26
Route Advertisements
 Advertise to each neighbor own routing information
•
•
•
•
Destination Address
Metric = Number of Hops to Destination
Destination Sequence Number
Other info (e.g. hardware addresses)
 Rules to set sequence number information
• On each advertisement increase own destination sequence
number (use only even numbers)
• If a node is no more reachable (timeout) increase sequence
number of this node by 1 (odd sequence number) and set
metric = .
27
Route Table Entry Structure
 Data broadcast by each mobile computer contains its
new sequence number and
• Destination’s address
• Number of hops required to reach destination
• Sequence number of the information received regarding that
destination
 Within the header of the packet, the transmitted route
tables will also contain
• Hardware address of transmitting node
• Network address of transmitting node
28
Table Entries
Destination
Next
Metric
Seq. Nr
Install Time
Stable Data
A
A
0
A-550
001000
Ptr_A
B
B
1
B-102
001200
Ptr_B
C
B
3
C-588
001200
Ptr_C
D
B
4
D-312
001200
Ptr_D
 Sequence number originated from destination
• Ensures loop freeness
 Install time when entry was made
• Used to delete stale entries from table
 Stable data pointer to a table holding information on how stable
a route is
• Used to damp fluctuations in network
29
Route Table Entry Structure
 Routes with more recent sequence numbers are always
preferred as the basis of forwarding decisions
• But they are not necessarily advertised
 Problem
• One way links
• Receiving a packet does not indicate the existence of path back to that
neighbor
 To avoid one way links
• No mobile node inserts routing information received from a
neighbor unless that neighbor shows that it can receive packets
from the mobile node
30
Responding to Topology Change
 Mobile nodes cause broken links as they move
• Broken link is described by a metric of ∞
 Any route through the broken link is immediately assigned
an ∞ and an updated sequence number
• Sequence number is incremented by one
• Information describing a broken link is the only scenario in which
sequence number is generated by any node other than destination
 Such a route change is immediately disclosed in broadcast
routing information
31
DSDV (New Node)
2. C inserts entry for D with
sequence number D-000, then
immediately broadcast own table
1. D broadcast for first time
Send Sequence number D-000
(D, 0, D-000)
A
Dest. Next Metric
A
A
0
B
B
1
C
B
2
B
Seq.
A-550
B-104
C-590
Dest. Next Metric Seq.
A
A
1
A-550
B
B
0
B-104
C
C
1
C-590
C
Dest. Next Metric
A
B
2
B
B
1
C
C
0
D
D
1
D
Seq.
A-550
B-104
C-590
D-000
32
DSDV (New Node cont.)
3. C increases its sequence
number to C-592 then
broadcasts its new table.
4. B gets this new information
and updates its table…….
(A, 2, A-550)
(B, 1, B-102)
(C, 0, C-592)
(D, 1, D-000)
………
………
A
Dest. Next Metric
A
A
0
B
B
1
C
B
2
B
Seq.
A-550
B-104
C-590
Dest. Next Metric Seq.
A
A
1
A-550
B
B
0
B-102
C
C
1
C-592
D
C
2
D-000
(A, 2, A-550)
(B, 1, B-102)
(C, 0, C-592)
(D, 1, D-000)
C
Dest. Next Metric
A
B
2
B
B
1
C
C
0
D
D
1
D
Seq.
A-550
B-102
C-592
D-000
33
DSDV (no loops, no count to infinity)
2. B does its broadcast
-> no affect on C (C knows that B
has stale information because C has
higher seq. number for destination D)
1. Node C detects broken Link:
-> Increase Seq. Nr. by 1
-> no loop
-> no count to infinity
(only case where not the destination
sets the sequence number -> odd
number)
(D, 2, D-100)
(D, 2, D-100)
1
A
B
Dest. Next Metric
…
…
…
D
B
3
Seq.
D-100
C
Dest.c Next Metric
…
…
…
D
C
2
Seq.
D-100
Dest. Next Metric
…
…
…
D
D

D
Seq.
D-101
34
DSDV (Immediate Advertisement)
3. Immediate propagation
B to A:
2. Immediate propagation
C to B:
(update information has higher
Seq. Nr. -> replace table entry)
(update information has higher
Seq. Nr. -> replace table entry)
1. Node C detects broken Link:
-> Increase Seq. Nr. by 1
(only case where not the destination
sets the sequence number -> odd
number)
(D, , D-101)
A
B
Dest. Next Metric Seq.
…
…
…
...
D
B
4
D-100
3
D
B
(D, , D-101)

D-101
D
C
Dest.c Next Metric
…
…
…
Seq.
...
D
C
3
2
D-100
D
C

D-101
Dest. Next Metric Seq.
…
…
…
D
B
D-100
D
1
D
D

D-101
35
Full/Incremental Update
 Full Update
• Send all of the routing information from own table
• Requires multiple Network Protocol Data Units (NPDU)
 A full update is scheduled
• When movements become frequent and the incremental update size
approaches the size of a NPDU
• To make the next incremental update smaller
 Incremental Update
• Send only entries that have changed since last full Update
• Make it fit into one single packet
36
Route Selection Criteria
 On receiving a new routing information
• Information is compared to the information already available
• Metric is incremented by one
• New information is scheduled for advertisement
 Any route with more recent sequence number is used
• Routes with older sequence numbers are discarded
 A route with sequence number equal to an existing route is chosen
if it has a better metric
• Older route may be discarded or stored as less preferable
37
Operating DSDV at Layer 2
 Addresses stored in the route tables correspond to the layer
at which the DSDV is operated
• e.g., Operation at layer 3 uses network layer addresses
 For operation at layer 2
• Layer 3 protocol information along with layer 2 information should
be included
• Each destination node would advertise which layer 3 protocols it
supports
• Each node advertising reachability would also include the
supported layer 3 protocols
• Changes would be part of incremental update
38
DSDV (Problem of Fluctuations)
A
P
What are Fluctuations
Q
11 Hops
10 Hops
(D,0,D-102)
D
• Entry for D in A: [D, Q, 14, D-100]
• D makes Broadcast with Seq. No. D-102
• A receives from P Update (D, 15, D-102)
-> Entry for D in A: [D, P, 15, D-102]
A must propagate this route immediately
• A receives from Q Update (D, 14, D-102)
-> Entry for D in A: [D, Q, 14, D-102]
A must propagate this route immediately
This can happen every time D or any other
node does its broadcast and lead to
unnecessary route advertisements in the
network, so called fluctuations
39
DSDV (Damping Fluctuations)
How to damp fluctuations
P
A
Q
11 Hops
10 Hops
D
• Record last and avg. Settling Time of every Route in a
separate table. (Stable Data)
Settling Time = Time between arrival of first route and
the best route with a given seq. no
• A still must update his routing table on the first arrival
of a route with a newer seq. no., but it can wait to
advertising it. Time to wait is proposed to be 2*(avg.
Settling Time)
• Like this, fluctuations in larger networks can be
damped to avoid unnecessary advertisement, thus
saving bandwidth
40
Summary
 Advantages
• Simple (almost like Distance Vector)
• Loop free through destination seq. numbers
• No latency caused by route discovery
 Disadvantages
•
•
•
•
No sleeping nodes
Bi-directional links required
Overhead: most routing information never used
Scalability is a major problem
41
Source Tree Adaptive Routing(STAR)
 A bandwidth efficient routing protocol for ad hoc networks
 A variation of table-driven routing protocols, with the Least
Overhead Routing Approach (LORA) as the key concept rather
than the Optimum Routing Approach (ORA) that was employed
by the most of the table-driven routing protocols
 LORA provides all the feasible paths with respect to some metric
which may not be guaranteed optimal but with much less control
overhead
 Every node broadcasts its source tree information
• The set of links used by a router in its preferred path to a destination is
called a source tree
 Routers in STAR communicate their source routing trees to
neighbors for all possible destinations
42
Source Tree Adaptive Routing(STAR)
 Every node using its adjacent links, and the source tree broadcast
by its neighbor links, builds a partial graph of its topology
 During initialization, a node sends its update messages about new
destinations, the chances of routing loops, and costs of paths
exceeding a given threshold
 Hence, each node will have a path to every destination node
• The path, in most cases, would be sub-optimal
 Such updates are communicated only when:
• Routers determine long-term loops can be created
• New destinations are found
• When a destination becomes unavailable
43
Source Tree Adaptive Routing(STAR)
 The basic update unit used to communicate changes to source trees
is the Link State Update (LSU)
 STAR uses sequence numbers to validate the LSUs
 A sequence number associated with a link consists of a counter that
can only be incremented by the head node (originator) of that link
 As LSUs for operational links never age out, there is no need for
the head node of a link to send periodic LSUs to update link’s
sequence number
44
Path Finding Approach
 When a nodes s has data packets to send to a particular destination
d, for which no path exists in its source-tree, its originates an
update message to all its neighbors indicating the absence of a path
to d
 This update message triggers another update message from a
neighbor which has path to d
 Node s retransmits the update message as long as it does not have a
path to d with increasing intervals between successive
retransmissions
 After getting the source-tree update from a neighbor, the node s
updates its source-tree and, using this, finds a path to all nodes in
the network
 The data path contains information about the path to be traversed in
order to prevent the possibility of routing loop formation
45
Route Maintenance
 In the presence of a reliable broadcast mechanism,
START assumes implicit route maintenance
 Path breaks
• The link update message about the unavailability of a next-hop
node triggers an update message from a neighbor which has an
alternate source tree indicating and alternate next-hop node to
the destination
46
Route Maintenance
 Handling the routing loops
• When an intermediate node k receives a data packet to destination d,
and one of the nodes in the packet`s traversed is present in node k`s
path to the destination d, then it discards the packet and a
RouteRepair update message is reliably sent to the node in the head
of the route repair path
• The route repair path corresponds to the path k to x, where x is the last
router in the data packet`s traversed path that is first found in the path
k to d, that belongs to the source tree of k
• The RouteRepair packet contains the complete source tree of node k
and the traversed path of the packet
• When an intermediate node receives a RouterRepair update message,
it removes itself from the top of the route repair path and reliably
sends it to the head of the route repair path
47
STAR Exchanging Update Messages
 Update messages exchange depends on the routing approach
used(ORA or LORA)
 For ORA to be supported in STAR, a router must send an update
message whenever its source tree changes
 For LORA in STAR, a router reports updates to its source trees in
event of unreachable nodes, new destinations, loops or cost
exceeding a given threshold
 If the new source tree includes neighbors other than those present
in the source tree that was last updated, the router must send its
entire source tree in the update
 If the two source trees contain the same neighbors, the router sends
only the updates needed to obtain the new tree from the old one
48
STAR Impact of the Link Layer
 If the underlying MAC protocol does not provide collision-free
transmission for reliable broadcasting, then in STAR, the router
broadcasts to neighbors unreliably
 A packet must specify the path it has traversed
 A router must send its update reliably to the neighbor that caused it
to change its source routing tree
49
Advantages
 Low communication overhead among all the table-driven routing
protocols
 The use of LORA approach in this table-driven routing protocol
reduces the average control overhead compared to several other ondemand routing protocols
50