Network Routing II Slides borrowed from Richard Y Yang Yale Recap Network routing Protocol DSDV Link reversal Today DSR Non conventional routing for wireless networks 2 Recap DSDV Motivation 1 1 1 1 3 Why Count to Infinity Routing loop a loop is a global state consisting of the nodes local states at a global moment observed by an oracle such that there exist nodes A B C such that A locally thinks B as down stream B thinks C as down stream C thinks A as down stream 1 1 1 1 4 Destination sequenced distance vector protocol DSDV Basic idea DSDV tags each route with a sequence number Invariants For any node sequence number is non decreasing for the same sequence number distance is nonincreasing 5 Recap Link Reversal Motivations maintain a mesh hopefully local adaptation Full link reversal Partial link reversal 6 Link Direction Through Heights A node i contains a triple i i i i an integer the major integer i another integer the minor integer i node index to impose a total order The triple of a node is called the height of the node Suppose there is a link from node i to node j the direction is determined by their heights i j if i i i j j j For destination D the height is 0 0 D 7 Illustration of Heights 8 Analysis The state of a node its height as well as its neighbors potentially obsolete heights An invariant over the state of a node is non decreasing 9 Summary Link Reversal Algorithms Advantages the DAG provides many hosts the ability to send packets to a given destination beneficial when many hosts want to communicate with a single destination Disadvantages paths may not be the best loops before convergence hurt performance 10 Summary Routing Algorithms Global information Routers maintain complete topology link cost info link state algorithm Distributed Routers maintain distance to each dest Iterative process of computation exchange of info with direct neighbors distance vector algorithm 5 B 3 C 5 2 A 2 1 3 D F 1 E 2 1 Partial global information Routers maintain partial topology mesh for each dest link reversal algorithm 11 Outline Today DSR Non conventional routing for wireless networks 12 DSR Concepts On demand route discovery DSDV link state and link reversal protocols are proactive they continuously maintain routes topology DSR is a reactive protocol maintaining active routes only Source routing no need to maintain information at intermediate nodes 13 Dynamic Source Routing DSR When node S wants to send a packet to node D but does not know a route to D node S initiates a route discovery Source node S floods Route Request RREQ Each node appends its own identifier when forwarding RREQ 14 Route Discovery RREQ Y Z S E F B C M J A L G H K I D N Represents a node that has received RREQ for D from S 15 Route Discovery RREQ Y Broadcast transmission S S Z E F B C M J A L G H K I D N Represents transmission of RREQ X Y Represents list of identifiers appended to RREQ 16 Forwarding RREQ A request is forwarded by a node if the node is not destination the node has not seen RREQ with the same sequence number from the same source When forwarding RREQ use a random delay to avoid collision 17 Route Discovery RREQ Y Z S S B E S E F B C A M J S C H L G K D I N Node H receives RREQ from two neighbors B and C Node C and E send RREQ to each other 18 Route Discovery RREQ Y Z S E F B S E F C M J A L G H I S C G K D N Node C receives RREQ from G and H but does not forward it again because node C has already forwarded RREQ once 19 Route Discovery RREQ Y Z S E S E F J F B C M J A L G H K I D S C G K N 20 Route Discovery RREQ Y Z S E S E F J M F B C M J A L G H K D I N Node D does not forward RREQ because node D is the intended target of the route discovery 21 Route Reply RREP Destination D on receiving the first RREQ sends a Route Reply RREP RREP includes the route from S to D on which RREQ was received by node D Question how to send RREP from D back to S 22 Route Reply in DSR Route Reply is sent by reversing the route in Route Request RREQ this requires bi directional link to ensure this RREQ should be forwarded only if it received on a link that is known to be bidirectional this also necessary for IEEE 802 11 MAC is used to send data then links have to be bi directional since Ack is used If unidirectional asymmetric links are allowed then RREP may need a route discovery from D back to S 23 Route Reply Y Z S E RREP S E F J D F B C M J A L G H K I D N Represents RREP control message 24 Data Delivery in DSR Y DATA S E F J D S Z E F B C M J A L G H K I D N When node S sends a data packet to D the entire route is included in the packet header hence the name source routing 25 DSR Optimization Route Caching Each node caches a new route it learns by any means e g when node S finds route S E F J D to node D node S also learns route S E F to node F when node K receives Route Request S C G node K learns route K G C S to node S when node F forwards Route Reply RREP S E F J D node F learns route F J D to node D a node may also learn a route when it overhears data packets 26 Using Route Cache Advantages using route cache can speed up route discovery and reduce RREQ propagation check route cache before issues RREQ intermediate nodes can send Route Reply using route cache Disadvantages stale caches can adversely affect performance e g a sender may try several stale routes obtained from local cache or replied from cache by other nodes before finding a good route 27 DSR Summary Advantages reactive routes maintained only between nodes who need to communicate route caching can further reduce route discovery overhead a single route discovery may yield many routes to the destination due to intermediate nodes replying from local caches Disadvantages packet header size grows with route length due to source routing flood of route requests may potentially reach all nodes in the network care must be taken to avoid collisions between route requests and route reply propagated by neighboring nodes 28 Ad Hoc On Demand Distance Vector Combination of ideas in …