8/22/2019 Staub Seminar Mai 2006
1/16
RVS SeminarPath Diversity in Wireless Mesh Networks
Thomas Staub
Universitt Bern
8/22/2019 Staub Seminar Mai 2006
2/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
2
Table of Contents
> Wireless Mesh Networks (WMN)
> Path diversity (multi-path routing)
> Multi-Path Routing Protocols
> AODV-BR
> Multi-Path DSR
> MPABR
ABR
Multipath Enhancements ABR -> MPABR
> Future work / ideas
> Questions?
8/22/2019 Staub Seminar Mai 2006
3/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
3
Wireless Mesh Networks
8/22/2019 Staub Seminar Mai 2006
4/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
4
Path diversity, multi-path routing
> Transmission over multiple path can compensate the dynamic andunpredictable nature of the wireless medium
Different path have different error characteristics, different delays etc.
> Bottleneck prevention (e.g. gateways)
> Reducing the effect of node mobility
> Node-disjoint paths, Link-disjoint paths
8/22/2019 Staub Seminar Mai 2006
5/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
5
Multi-Path Routing Protocols
> Based on AODV AOMDV
AODVM
Node-Disjoint Multipath Routing (NDMR)
Similiar Node-disjoint Multipath Routing (SNDMR)
AODV-BR> Based on DSR
Split Multi-Path Routing (SMR)
Multi-Path DSR (MP-DSR)
Multipath Source Routing (MSR)
> CacHing And Multipath routing Protocol (CHAMP)
> Based on Associativity Based Routing (ABR) Multipath Associativity Based Routing (MPABR)
8/22/2019 Staub Seminar Mai 2006
6/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
6
Ad hoc On-demand Distance Vector -Backup Routing (AODV-BR)
> Same route construction process as AODV
Flooding route request (RREQ) with unique ID
If intermediate node receives RREQ, it records previous hopand source node info, broadcast RREQ or sends route reply if aroute to destination is known.
Destination sends RREP when it receives the first RREQ orlater RREQs (better routes)
> Alternate route table
> Alternate route creation during RREP phase
Nodes that overhear RREP(s) not directed to themselves,record the neighbor node as next hop to the destination in theiralternate route table
8/22/2019 Staub Seminar Mai 2006
7/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
7
Ad hoc On-demand Distance Vector -Backup Routing (AODV-BR)
> Multiple routes form a fish bone structure
> Alternative routes (backup routes) used when primary fails
> No multiple complete routes available
> No complete route information known at source
8/22/2019 Staub Seminar Mai 2006
8/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
8
MultiPath Dynamic Source Routing (MP-DSR)
> QoS-aware (QoS metric = e2e reliability)
> Source routing
> Application supplies minimum end-to-end reliabilityrequirement
Number of paths
Lowest path reliability
> Intermediate nodes compare received RREQs with requiredend-to-end reliability and determine whether they forward ordiscard them.
> Destination selects multiple node-disjoint paths from the
received RREQ, RREP are sent along these paths
8/22/2019 Staub Seminar Mai 2006
9/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
9
CacHing And Multipath routing Protocol(CHAMP)
> Route discovery
Flooding of RREQ -> DAG rooted at the source
Destination sends back RREP
Multiple route of equal length are established
> Temporal caching to reduce packet losses
> Cached routes for backup (in case of route fails)
> Delivers non-disjoint multiple paths
> Traffic is distributed among multiple paths (round-robin)
8/22/2019 Staub Seminar Mai 2006
10/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
10
Multipath Associativity Based Routing(MPABR): ABR
> Associativity Based Routing New routing metric = degree of associativity stability
Periodic beaconing of each node
Increments associativity tick for current node when receiving a beacon
Reset associativity tick to 0, if 3 consecutive beacons are not received
Route discovery Flooding Broadcast Query (BQ) (similiar to DSR)
Intermediate node appends its address and associativity ticks to BQ If BQ arrives at destination, destination waits a period of time, selects thebest route accorriding to associativity ticks, and return RREP
8/22/2019 Staub Seminar Mai 2006
11/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
11
ABR: Route Reconstruction / Repair
Route Repair /Reconstructionusing local querymessage (LQ)
Broken link detectionthrough beacons by theneighbor nodes
Neighbor node closestto source starts localrepair (-> LQ)
If local repair fails, thenext upstream nodestarts local repair (newBQ if node in the middleof the broken path fails)
8/22/2019 Staub Seminar Mai 2006
12/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
12
ABR: Route Deletation
- Route delete if discovered route is no longer needed (-> RDmessage, full broadcast)
8/22/2019 Staub Seminar Mai 2006
13/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
13
Multi-Path ABR
> Addition of multipath number Unique identifier for each multipath route
Included in header (Packet, RREP) and routing tables
> Different multipath criteria Node-disjoint
Partial node-disjoint Disjoint
Intermediate node-disjoint
> When the destination node BQ Collect Replies timer expires,it determines the most stable routes, and selects multiplepaths based on the multipath criteria.
> The destination responds for each selected multipath routewith a route reply.
8/22/2019 Staub Seminar Mai 2006
14/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
14
Future work / ideas:
> Simulations with different multi-path routing protocols, routingmetrics
Comparison of different multi-path routing protocols (AOMDV,AODVM, SRM, NDMR, CHAMP, MPABR, AODV-BR ...)
Influence of multi-radio / multi-channel communication on multi-
path routing Analysis of interference between two paths
> Real world experiments
Implementation of AODVM
Experiments with notebooks, WRAP nodes
Evaluation of interference of 2 wireless cards
8/22/2019 Staub Seminar Mai 2006
15/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
15
Questions?
8/22/2019 Staub Seminar Mai 2006
16/16
May 17, 2006
Path Diversity in Wireless Mesh Networks
16
> Thank you very much for your attention.