CMPE 257 Wireless Networking SET 5 Unicast Routing in MANETs Jan 14 2019 UCSC CMPE252 1 Proactive Approaches Jan 14 2019 UCSC CMPE252 2 Optimized Link State Routing OLSR Jacquet00ietf Overhead of flooding link state information reduced by having fewer nodes forward the information Broadcast from X only forwarded by its multipoint relays MPRs Jan 14 2019 UCSC CMPE252 3 Proactive Approaches Schemes Topology broadcast OLSR Partial topology information or path information Distance vectors with some constraint typically a sequence number Techniques Same three types of termination detection Jan 14 2019 UCSC CMPE252 4 OLSR OLSR is proactive It floods information through MPRs Flooded information contains links connecting nodes to respective MPRs I e node sends info on nodes that selected it as their MPR Periodic HELLO messages inform nodes which other nodes selected it as their MPR Routes used by OLSR only include multipoint relays as intermediate nodes Jan 14 2019 UCSC CMPE252 5 MPRs Multipoint relays of node X are its neighbors such that each two hop neighbor of X is a one hop neighbor of at least one multipoint relay of X Each node transmits its neighbor list in periodic beacons so that all nodes know their 2 hop neighbors MPRs of X are 1 hop neighbors of X covering X s 2 hop neighbors Jan 14 2019 UCSC CMPE252 6 Optimized Link State Routing OLSR C and E are multipoint relays of A F B A C G J E H K D Node that has broadcast state information from A Jan 14 2019 UCSC CMPE252 7 Optimized Link State Routing OLSR Nodes C and E forward information received from A F B A C G J E H K D Node that has broadcast state information from A Jan 14 2019 UCSC CMPE252 8 Optimized Link State Routing OLSR E and K are multipoint relays for H K forwards information received from H E has already forwarded the same information F B once J A C G E H K D Node that has broadcast state information from A UCSC CMPE252 Jan 14 2019 L 9 Termination Detection over Cycles Jan 14 2019 UCSC CMPE252 10 Motivation Topology broadcast and distance flooding incur too many updates Diffusing computations may incur too many update messages when nodes need to synchronize over many hops Objective Have the same information regarding paths available with topology broadcast algorithms without the communication overhead Jan 14 2019 UCSC CMPE252 11 Basic Approach Each router maintains the entire path to each destination Update for destination j report the length and node constituency of path to j Complete path information is used to detect loops A router can always adopt a path to a destination that does not already include the router itself and has the shortest length among all valid paths Example BGP Jan 14 2019 UCSC CMPE252 12 Detecting Loops Using Path Information 5 A B D j A 10 2 C j C 1 2 2 6 S A B D j X 2 10 S j 0 j 2 5 B 3 B D j Jan 14 2019 UCSC 1 D 2 D j CMPE252 13 Detecting Loops Using Path Information 5 A B D j A 10 5 C B D j C 1 2 6 S A B D j 2 10 S 5 B 3 B D j Jan 14 2019 UCSC 1 D 12 D C j CMPE252 14 Detecting Loops Using Path Information 5 A B D j A 10 5 C B D j C 1 2 6 S A B D j 2 10 S LOOP 5 B 3 B D j Jan 14 2019 UCSC 1 D 12 D C j CMPE252 15 Detecting Loops Using Path Information 5 A B D j A 10 5 C B D j C U j 5 C B D j 1 2 6 S A B D j 2 10 S 5 B 3 B D j Jan 14 2019 UCSC 1 D U j 12 D C j 12 D C j CMPE252 16 Detecting Loops Using Path Information 5 A B D j A 10 5 C B D j C 1 2 6 S A B D j 2 10 S 5 U j 13 B D C j B 1 13 B D C j D 12 D C j Update from D forces B to update its path to j Jan 14 2019 UCSC CMPE252 17 Detecting Loops Using Path Information 5 A B D j A 10 5 C B D j C 1 2 6 S A B D j 2 10 S 5 U j 13 B D C j B 1 D U j oo 13 B D C j Update from C makes D detect and break loop l paths reported to D include D and it must set j as unreachable Jan 14 2019 UCSC CMPE252 18 Detecting Loops Using Path Information 15 A B D j U j 15 A B D j A 10 oo C U j oo 1 2 6 S A B D j 2 10 S 5 B 1 D 13 B D C j Update from B makes A update its path to j update all reported paths include Jan 14 2019 from D makes UCSC CMPE252 19 C Detecting Loops Using Path Information 5 A B D j U j 15 A B D j A 10 oo C 1 2 6 S A B D j 2 10 S 5 U j oo B 1 D oo oo After update from D all finite length paths reported to B include B and it must set j as unreachable Jan 14 2019 UCSC CMPE252 20 Detecting Loops Using Path Information 5 A B D j A 10 oo C 1 16 S A B D j 2 2 10 S U j 16 S A B D j 5 B oo 1 D oo Update from A makes S change its path to j Jan 14 2019 UCSC CMPE252 21 Detecting Loops Using Path Information oo U j oo A oo 10 C 1 2 16 S A B D j 2 10 S 5 B 1 D oo oo After update from B all finite length paths reported to A include A and it must set j as unreachable Jan 14 2019 UCSC CMPE252 22 Detecting Loops Using Path Information oo A oo 10 C 1 U j oo 2 oo 2 10 S 5 B oo 1 D oo No counting to infinity but temporary loops exist Jan 14 2019 UCSC CMPE252 23 Limitations of Basic Approach Temporary loops occur Complete path information is not necessary in updates Loop detection based on reported paths exclusively is not very efficient A router can believe a neighbor whose reported path includes a neighbor that has just reported an updated path that is invalid Fixing these limitations leads to the LoopFree Path Finding Algorithm LPA Jan 14 2019 UCSC CMPE252 24 Path Finding A tree rooted at s can be represented by specifying the nodes in the path traversed from s to each other node …
View Full Document
Unlocking...