Transcript AODV-BR: Backup Routing in Ad hoc Networks

Adaptive backup routing for
ad-hoc networks
Adviser: Ho-Ting Wu
Speaker: Zen-De Liu
Date:05/14/2007
Outline



Introduction
Related work
Adaptive backup routing
 AODV-ABR
 AODV-ABL



Simulation and analysis
Conclusion
Reference
2007/05/14
2
Introduction


Ad-hoc network is a self-organized,dynamically changing multihop network.
All mobile nodes in an ad-hoc network are capable of
communicating with each other without the aid of any
established infrastructure or centralized controller.
An ad-hoc network.
2007/05/14
3
Introduction(2)

Many routing protocols have been proposed for ad-hoc
networks.These routing protocols can be divided roughly into
two types, table-driven and demand routing protocol.

Table-driven routing protocols: keep a global picture of
network topology and respond to topological changes by
propagating update messages throughout the wireless network.
such as Destination-Sequenced Distance-Vector routing.

On-demand routing protocols:The route is created only when it
is desired by the source node in the on-demand routing protocols.
such as Ad-hoc On-Demand Distance-Vector.
2007/05/14
4
Introduction(3)

The on-demand routing protocol in ad-hoc network have high
route discovery latency and reliable problems.

AODV- BR (backup route) improved on-demand routing
protocols by creating a mesh and providing multiple alternate
routes without transmitting any extra control message.

AODV-BR has to pay extra efforts in the maintenance of
alternate route tables and in route recovery.
2007/05/14
5
Related Work
 AODV:AODV can be simply divided into three parts: route
request, route reply and route maintenance.
 RREQ :



When a source node desires a route to a destination for which it does not already
have a route, it broadcasts a route request (RREQ) packet across the network .
Nodes receiving this packet update their information for the source node and set
up backwards pointers to the source node in the route tables .
In addition to the source node's IP address, current sequence number, and
broadcast ID, the RREQ also contains the most recent sequence number for the
destination of which the source node is aware
2007/05/14
6
Related Work(2)




A node receiving the RREQ may send a route reply (RREP) if it is either the
destination or if it has a route to the destination with corresponding sequence
number greater than or equal to that contained in the RREQ .
Nodes keep track of the RREQ's source IP address and broadcast ID. If they
receive a RREQ which they have already processed, they discard the RREQ
and do not forward it.
RREP:Once the source node receives the RREP, it may begin to forward
data packets to the destination.
If the source later receives a RREP containing a greater sequence number or
contains the same sequence number with a smaller hop count, it may update its
routing information for that destination and begin using the better route .
2007/05/14
7
Related Work(3)



Route maintenance: A route is considered active as long as there are data
packets periodically travelling from the source to the destination along that
path.
Once the source stops sending data packets, the links will time out and
eventually be deleted from the intermediate node routing tables.
If a link break occurs while the route is active, the node upstream of the break
propagates a route error (RERR) message to the source node to inform it of the
now unreachable destination(s).

After receiving the RERR, if the source node still desires the route, it can
reinitiate route discovery .
2007/05/14
8
Related Work(4)


AODV-BR: When establishing the mesh and looking for multipath routes, the algorithm takes advantage of the RREPs (Route
Replies) messages of AODV without generating additional
control messages.
Each neighboring node overhears the RREP packets and records
the source of one of RREP packets as the next hop to the
destination into its alternate route table.
2007/05/14
9
Related Work(5)
2007/05/14
10
Related Work(6)
2007/05/14
11
Related Work(7)




AODV–LR: tries to repair the link error without informing the
source node and without the disruption in the data delivery.
performance can be improved because of that no data
retransmissions from the source are required if link failures can
be repaired locally.
the local link repairs might increase the hop counts of the data
path and then enlarge the end-to-end delays.
a threshold can be used to decide which policy should betaken –
to start a local repair process or to conduct a new route
discovery process.
2007/05/14
12
AODV-Adaptive backup routing
(ABR)

AODV-ABR
In AODV-BR, It’s appropriate to construct the alternate
paths during the route reply phase.
When the topology changes more dramatically,
alternate paths which were constructed during the
reply phase may also be broken.
Adaptive to the topology variations
=>AODV-ABR
2007/05/14
13
AODV-ABR

Constructing alternate routes by overhearing RREP
packet, the mesh structure also can be created by
overhearing the data packets transmitted from
neighbor nodes.
2007/05/14
14
AODV-ABR(2)
Establishment of the
primary and
alternate routes when
the RREP reaches the
source node.
Keeps the information
of hop count in the
routing table and
alternate
route table.
2007/05/14
15
AODV-ABR(3)
2007/05/14
16
Broken link repair

When a node detects a link failure in
AODV-BR, it will perform a onehop data broadcast to its neighbors
which forwards those packets to
destination via alternate route.

The ‘‘one-hop data broadcast’’ will
result in poor effectiveness under
heavy traffic networks because it will
create some unnecessary and
duplicated data packets delivered
through the alternate routes.
2007/05/14
17
Broken link repair(2)


2007/05/14
When a node detects a link failure in AODV-ABR, it will
perform a handshake process with its immediate
neighbors to repair the broken route. The handshake
process is accomplished by two one-hop control signals:
BRRQ and BRRP.
according to the hop count, the upstream node of the
broken link (originator) can select a shorter alternate route.
18
Re-route in AODV-ABR
2007/05/14
19
Re-route in AODV-ABR(2)
2007/05/14
20



















Algorithm : Procedure for Handling Link Break in
AODV-ABR. Procedure for link-break handling
{
Broadcast BRRQ to neighbors with TTL=1;
Wait for receiving BRRP packets;
If (BRRP packet received before timeout) {
Compare the hop count fields of all received BRRP
packets;
Choose the BRRP with the smallest hop count;
Update the next-hop field in the routing table with
the neighbor which transmitted the BRRP with the
smallest hop count;
Update the hop count field in the routing table with
the smallest hop count;
Relay data packets to the next hop;
}
Else
Send RERR back to the source;
}
2007/05/14
21












Algorithm : Procedure for Receiving BRRQ in AODV-ABR.
Procedure for receiving BRRQ
{
If (There exists an entry to the destination in its alternate
route table)
If (BRRQ packet is not received from the next hop to
the destination) {
Reply BRRP packet to the initiator of BRRQ;
Copy the routing information from the alternate
route table to the routing table;
}
}
2007/05/14
22
AODV-ABL

Combination of ABR and Local repair.

When the distance between the broken link and the
destination is not farther than MAX_REPAIR_TTL
hops, try to repair the link by broadcasting a RREQ
control signal,just as AODV-LR.

if the broken link is far away from the destination ,repair
the link by a handshake process with immediate
neighbors.
2007/05/14
23
Algorithm 4. Procedure for Handling Link Break in
 AODV-ABL.
 Procedure for link-break handling in
 AODV-ABL
{
 If (The destination is not farther than MAX_REPAIR_
 TTL hops away)
 Start local repair;
 Else {
 Broadcast BRRQ to neighbors with TTL=1;
 Wait for receiving BRRP packet;

2007/05/14
24















If (BRRP packet received before timeout) {
Compare the hop count fields of all received
BRRP packets;
Choose the BRRP with the smallest hop count;
Update the next-hop field in the routing table with
the neighbor which transmitted the BRRP with the
smallest hop count;
Update the hop count field in the routing table
with the smallest hop count;
Relay data packets to the next hop;
}
Else
Send RERR back to the source;
}
}
2007/05/14
25
Simulation and analysis

2007/05/14
Simulation environment
26
Simulation and analysis

Compare the five schemes: AODV, AODV-BR (Backup
Route), AODV-ABR (Adaptive Backup Route),
AODV–LR (Local repair), and AODV-ABL
(combination of ABR and LR) in different pause time.

Longer pause time implies less mobility.
2007/05/14
27
Simulation and analysis
2007/05/14
28
Simulation and analysis
2007/05/14
29
Simulation and analysis
2007/05/14
30
Simulation and analysis
2007/05/14
31
Simulation and analysis
The impact of traffic load :transmission rate of 6
2007/05/14
32
Simulation and analysis
The impact of traffic load :transmission rate of 8
2007/05/14
33
Simulation and analysis
under heavy loads by doubling the traffic to 20 session
2007/05/14
34
Conclusion




AODV-ABL has the highest throughput ,followed by AODV-LR or AODVABR and then AODV or AODV-BR.
AODV-LR is more suitable for high loads.
AODV-BR performs better in light loads and decreases in heavy traffic
situation because of the increase in packet collisions when there are more and
more traffic.
AODV-ABR utilizes the alternative routes of AODV-BR and the concept of
AODV–LR. It can repair the failing route by only inquiring the immediate
neighbor nodes that have alternate routes.
2007/05/14
35
Conclusion

AODV-ABR is not only adaptive to the variations of
network topology ,but also has small control overhead
then AODV-LR.

AODV-ABL provide more stability for connections and
retain highest performance under a high node mobility
ad-hoc network.

In the future, will improve the proposed schemes by
taking the Qos issues into account.
2007/05/14
36
Reference

Wei Kuang Lai,Sheng-Yu Hsiao,Yuh-Chung Lin，"Adaptive
backup routing for ad-hoc networks"，ScienceDirect Computer
Communications 30 (2007) 453–464.

Sung-Ju Lee ,Mario Gerla，“ AODV-BR: Backup Routing in
Ad hoc Networks”, Proceedings of IEEE WCNC 2000.
2007/05/14
37
Q&A
2007/05/14
38