Staub Seminar Mai 2006

8/22/2019 Staub Seminar Mai 2006

1/16

RVS SeminarPath Diversity in Wireless Mesh Networks

Thomas Staub

Universitt Bern


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?


3/16

May 17, 2006


3

Wireless Mesh Networks


4/16

May 17, 2006


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


5/16

May 17, 2006


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)


6/16

May 17, 2006


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


7/16

May 17, 2006


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/16

May 17, 2006


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


9/16

May 17, 2006


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)


10/16

May 17, 2006


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


11/16

May 17, 2006


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)


12/16

May 17, 2006


12

ABR: Route Deletation

- Route delete if discovered route is no longer needed (-> RDmessage, full broadcast)


13/16

May 17, 2006


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.


14/16

May 17, 2006


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


15/16

May 17, 2006


15

Questions?


16/16

May 17, 2006


16

> Thank you very much for your attention.

Documents

Staub Seminar Mai 2006