Network Routing IISlides borrowed from Richard Y. Yang @ YaleRecap• Network routing– Protocol• DSDV•Link reversal•Link reversal• Today– DSR– Non-conventional routing for wireless networks2Recap: DSDV Motivation1113111Why 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 B thinks C as down stream, C thinks A as down stream41111Destination-sequenced distance vector protocol (DSDV)• Basic idea:– DSDV tags each route with a sequence number• Invariants:–For any node–For any node• sequence number is non-decreasing• for the same sequence number, distance is non-increasing5Recap: Link Reversal• Motivations– maintain a mesh– (hopefully) local adaptation•Full link reversal•Full link reversal• Partial link reversal6Link 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 heightof the •The triple of a node is called the heightof 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)7Illustration of Heights8Analysis• The state ofa node– its height as well as its neighbors’ (potentially neighbors’ (potentially obsolete) heights• An invariant over the state of a node– α is non-decreasing9Summary: 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 destinationwith a single destination• Disadvantages– paths may not be the best– loops before convergence hurt performance10Summary: Routing AlgorithmsGlobal information:• Routers maintain complete topology, link cost info• “link state” algorithmDistributed:•Routers maintain distance to ACBF2231535•Routers maintain distance to each dest. • Iterative process of computation, exchange of info with direct neighbors• “distance vector” algorithmPartial global information:• Routers maintain partial topology (mesh) for each dest.• “link reversal” algorithm11ED1312Outline• Today– DSR– Non-conventional routing for wireless networks12DSR 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 –DSR is a reactive protocol, maintaining active routes only• Source routing– no need to maintain information at intermediate nodes13Dynamic 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 RREQ14Route Discovery: RREQBSEFCZYML15AHJDCGIKRepresents a node that has received RREQ for D from SMNLRoute Discovery: RREQBSEFCZYBroadcast transmissionML[S]16AHJDCGIKRepresents transmission of RREQMNL[X,Y] Represents list of identifiers appended to RREQForwarding 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)sequence number (from the same source)• When forwarding RREQ, use a random delay to avoid collision17Route Discovery: RREQBSEFCZYML[S,E][S,B]18AHJDCGIK• Node H receives RREQ from two neighbors B and C• Node C and E send RREQ to each otherMNL[S,C]Route Discovery: RREQBSEFCZYML[S,E,F]19AHJDCGIK• Node C receives RREQ from G and H, but does not forwardit again, because node C has already forwarded RREQ onceMNL[S,C,G]Route Discovery: RREQBSEFCZYML[S,E,F,J]20AHJDCGIKMNL[S,C,G,K]Route Discovery: RREQBSEFCZYML[S,E,F,J,M]21AHJDCGIK• Node D does not forward RREQ, because node Dis the intended target of the route discoveryMNLRoute Reply (RREP)• Destination D on receiving the first RREQ, sends a Route Reply (RREP)•RREP includes the routefrom S to D on which •RREP includes the routefrom S to D on which RREQ was received by node D• Question: how to send RREP from D back to S?22Route 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 bi-if it received on a link that is known to be bi-directional• 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 S23Route ReplyBSEFCZYMLRREP [S,E,F,J,D]24AHJDCGIKMNLRepresents RREP control messageData Delivery in DSRBSEFCZYMLDATA [S,E,F,J,D]25AHJDCGIKMNLWhen node S sends a data packet to D, the entire route is included in the packet header, hence the name source routingDSR 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 Fnode 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 packets26Using 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 route27DSR: Summary• Advantages– reactive: routes maintained only between nodes who need to communicate– route caching can further reduce route discovery overhead•asingle route discovery may yield many routes to the destination, •asingle route discovery may yield many routes to the destination, due to intermediate nodes replying from local caches• Disadvantages– packet