Network Routing Acknowledgement Slides borrowed from Richard Y Yang Yale Recap Network Layer Services Transport packets from source to dest Network layer protocol in every host router S1 B Major components Control plane A E D2 C S2 G I K J M D1 L N addressing scheme is crucial for usability mobility compute routing from sources to destinations Data plane forwarding move packets from input interface to appropriate output interface s 2 Recap Key Problems Location management B Routing with lossy and dynamic wireless links C A F D E Broadcast wireless channels 3 Routing Overview The problem of routing is to find a good path for each source destination pair B C A F D E A typical measure for a good path is that it is the shortest path according to some metric 4 Link Metric B C A One possibility is to assign each link a metric D E of 1 hop count based routing maximizes the distance traveled by each hop F low signal strength high loss ratio uses a higher TxPower interference different links have different qualities 5 Performance of Shortest Hop Count B C A F D E 6 Example Metric ETX ETX The predicted number of data transmissions required to successfully transmit a packet over a link the ETX of a path is the sum of the ETX values of the links over that path Examples ETX of a 3 hop route with perfect links is 3 ETX of a 1 hop route with 50 loss is 2 A High Throughput Path Metric for Multi Hop Wireless Routing by D De Couto D Aguayo J Bicket R Morris Mibicom 2003 http meraki com about 7 Acquiring ETX Measured by broadcasting dedicated link probe packets with an average period jittered by 0 1 Delivery ratio count t w t is the of probes received during window w w is the of probes that should have been received 8 ETX Example 9 ETX Advantage Tends to minimize spectrum use which can maximize overall system capacity reduce power too each node spends less time retransmitting data ETX has problems and is not the only link metric We will revisit link metrics next class 10 Outline Routing overview computing shortest path routing 5 B 3 C 2 A 2 1 3 D F 1 E 1 5 2 11 Link State Routing Algorithms Separation of topology distribution from route computation Used in OSPF the dominant intradomain routing protocol used in the Internet Net topology link costs are distributed to all nodes Link state distribution accomplished via link state broadcast Each node locally computes its paths to all destinations 12 Link State Broadcast S E F B C M J A L G H K I D N represents a node that has received update represents link 13 Link State Broadcast S E F B C M J A L G H K I D N 14 Link State Broadcast S E F B C M J A L G H K I D N To avoid forwarding the same update multiple times each update has a sequence number If an arrived update does not have a higher seq discard The packet received by E from C is discarded The packet received by C from E is discarded as well Node H receives packet from two neighbors and will discard one of them 15 Summary of Link State Routing Separation of topology distribution from route computation Whenever a link metric changes the node broadcasts new value Q Does link state routing work well in a network with dynamic link status 16 Distance Vector Routing Algorithm Based on the Bellman Ford algorithm at node X the distance or any additive link quality metric to Y is updated by d X Y min Z N X d X Z d Z Y where dX Y is the current distance at node X from X to Y N X is the set of the neighbors of X and d X Z is the distance of the direct link from X to Z Implemented in the RIP routing protocol and some wireless mesh networks 17 7 Distance Table Example A Below is just one step The algorithm repeats for ever 1 distance tables E computation from neighbors E s distance B 1 C 2 8 E D 2 distance table E sends d A B D A B D forwarding table A 0 7 1 15 1 A A 1 B 7 0 8 8 8 B B 8 C 1 2 9 4 4 D C 4 D 0 2 2 D D 2 1 8 2 d E A d E B d E D to its neighbors E 0 18 Distance Vector in the Presence of Topology Dynamics Good news propagate fast Link AB is up 19 Distance Vector in the Presence of Topology Dynamics Bad news propagate slowly the count toinfinity problem Link AB is down or cost increases substantially 20 The Reverse Poison Split horizon Hack A 7 If the path to a dest is through neighbor h report 1 to neighbor h for dest E s distance tables computation distance from neighbors forwarding dE A B D A B D table A 0 7 1 15 1 A B 1 C 2 8 E D 2 distance table E sends to its neighbors To A To B To D A A 1 A 1 B 7 0 8 8 8 B B 8 B B 8 C 1 2 9 4 4 D C 4 C 4 C D 2 D 2 D E 0 E 0 E 0 D 1 8 d E A d E B 0 2 d E D 2 2 D distance through neighbor 21 An Example Where Split Horizon Fails 1 1 1 1 When the link between C and D fails C will set its distance to D as However unfortunate timing can cause problem A receives a new update from C then a previous update from B when B thought C was good arrives then A will use B to go to D A sends the good news to C C sends the good news to B 22 Destination sequenced distance vector protocol DSDV There are optimizations but we present the base protocol Only handle the case when link is broken Let s assume the destination node is D Basic idea DSDV tags each route with a sequence number Each destination node D periodically advertises monotonically increasing even sequence numbers When a node realizes that the link that it uses to reach destination D is broken the node increases the sequence number for D to be one greater than the previous one odd number 23 DSDV Details Periodical and triggered updates periodically D increases its seq SD by 2 and broadcasts with SD 0 if A is using B as next hop to D and A discovers that the link AB is broken A increases its sequence number SA by 1 odd sets dA to and sends SA dA to all neighbors 24 DSDV Details Update after receiving a message Assume B sends to A the information …
View Full Document
Unlocking...