cs525-rachit.pdfRouting in Ad-hoc networksAd-hoc networksFlooding at the Data-planeFlooding at the Data-planeFlooding at the Data-planeFlooding at the Data-planeFlooding at the Data-planeAdvantages of flooding at the data-planeDisadvantages of flooding at the data-planeDestination-Sequenced Distance-Vector (DSDV)DSDV Routing tablesDSDV Routing TablesDSDV Link FailuresSlide Number 14Advantages of flooding at control planeDisadvantages of flooding at control planeClusterhead Gateway Switch Routing (CGSR) Clusterhead Gateway Switch Routing (CGSR) Advantages of CGSRDisadvantages of CGSRDynamic Source Routing (DSR)Route Discovery in DSRRoute Discovery in DSRRoute Discovery in DSRRoute Discovery in DSRRoute Discovery in DSRRoute Discovery in DSRRoute Reply in DSRData Delivery in DSRAdvantages of DSRDisadvantages of DSRAODVRoute Requests in AODVRoute Requests in AODVRoute Requests in AODVReverse Path Setup in AODVReverse Path Setup in AODVReverse Path Setup in AODVRoute Reply in AODVData Delivery in AODVAdvantages of AODVDisadvantages of AODVLink Reversal Algorithm (Simplified TORA)Link Reversal AlgorithmLink Reversal AlgorithmLink Reversal AlgorithmLink Reversal AlgorithmLink Reversal AlgorithmLink Reversal AlgorithmLink Reversal AlgorithmAdvantages of Link Reversal AlgorithmDisadvantages of Link Reversal AlgorithmWhat we did not cover?Looking forward …. Looking forward …. bdLOF-oLearn on the Fly: Data-driven Link Estimation and Routing in Sensor Network BackbonesSensor Network RoutingFundamental QuestionsTraditional ApproachProblems with traditional approach (I)Problems in traditional approach (II)Problems with traditional approach (III)Problems with traditional approach (IV)Idea 1. Data-plane link estimationIdea 2. ELD metric# data packets required for selecting next-hopExperiment design: protocols studiedExperiment design: evaluation methodLOF End-to-end MAC latencyLOF transmission reliabilityLOF path lengthSummaryPRESENTED BY-LEWIS TSENGRACHIT AGARWALRouting in Ad-hoc networksAd-hoc networks Infrastructure-less networks No fixed routers (potentially) mobile nodes Dynamically and arbitrarily located Desired routing requirements High connectivity Low overhead (how to characterize overhead?)Flooding at the Data-plane3BASEFHJDCGIKRepresents that connected nodes are within each other’s transmission rangeRepresents a node that has received packet PFlooding at the Data-plane4BASEFHJDCGIKRepresents transmission of packet PRepresents a node that receives packet P forthe first timeBroadcast transmissionFlooding at the Data-plane5BASEFHJDCGIKFlooding at the Data-plane6BASEFHJDCGIKFlooding at the Data-plane7BASEFHJDCGIK• Nodes J and K both broadcast packet P to node D• Since nodes J and K are hidden from each other, their transmissions may collide•Packet P may not be delivered to node D at all, despite the use of flooding• Welcome to the world of wireless networksAdvantages of flooding at the data-plane8 Simplicity Potentially higher reliability of data delivery No routing tables – just need to store neighborsDisadvantages of flooding at the data-plane9 Potentially, very high overhead Potentially lower reliability of data delivery hard to implement reliable broadcast Packet collisions10Destination-Sequenced Distance-Vector (DSDV)CBADest. Next Metric Seq.A A 0 A-550B B 1 B-104C B 2 C-590Dest. Next Metric Seq.A A 1 A-550B B 0 B-104C C 1 C-590Dest. Next Metric Seq.A B 2 A-550B B 1 B-104C C 0 C-590B• Routing tables:• Each node stores, for each destination:• next-hop• cost•sequence number• Control plane:• periodically broadcast routing tables to neighbors(D, 0, D-000)DSDV Routing tablesCBA DDest. Next Metric Seq.A A 0 A-550B B 1 B-104C B 2 C-590Dest. Next Metric Seq.A A 1 A-550B B 0 B-104C C 1 C-590Dest. Next Metric Seq.A B 2 A-550B B 1 B-104C C 0 C-590D D 1 D-0001. D broadcast for first time – sends sequence number D-0002. Insert entry for D with sequence number D-0003. Immediately broadcast own tableB(A, 2, A-550)(B, 1, B-102)(C, 0, C-592)(D, 1, D-000)(A, 2, A-550)(B, 1, B-102)(C, 0, C-592)(D, 1, D-000)DSDV Routing TablesCBA DDest. Next Metric Seq.A A 1 A-550B B 0 B-102C C 1 C-592D C 2 D-000Dest. Next Metric Seq.A A 0 A-550B B 1 B-104C B 2 C-590Dest. Next Metric Seq.A B 2 A-550B B 1 B-102C C 0 C-592D D 1 D-000………………3. C increases its sequence number to C-592 and broadcasts its new table.4. B gets this new information and updates its table…….B(D, 2, D-100)(D, 2, D-100)DSDV Link FailuresCBADDest.c Next Metric Seq.… … …D C 2 D-100Dest. Next Metric Seq.… … …D B 3 D-100Dest. Next Metric Seq.… … …D D∞D-101Node C detects broken link2. B does its broadcast –no affect on C (old sequence number)BCBADDest.c Next Metric Seq.… … …D C 3 D-100Dest. Next Metric Seq.… … …D B 4 D-100Dest. Next Metric Seq.… … …D B1D-100Dest. Next Metric Seq.… … …D D1D-100D D∞D-101Dest.c Next Metric Seq.… … … ...D C2D-100D C∞D-101Dest. Next Metric Seq.… … … ...D B3D-100D B∞D-101BDSDV Link FailuresAdvantages of flooding at control plane15 Overhead due to data plane flooding avoided Nodes maintain (almost) consistent network map If the network is stable, loop-free routing very easy Resulting paths are shortest pathsDisadvantages of flooding at control plane16 Scalability does not scale to large networks Even for small networks, large overhead if network is dynamic #Data packets versus #control packets?Clusterhead Gateway Switch Routing (CGSR) CA1B DE23• Flood the control plane within a cluster• Flood the control plane among the cluster leaders1. Partition the network2. Assign cluster leadersClusterhead Gateway Switch Routing (CGSR) CAB DE123Potentially longer pathsAdvantages of CGSR19 Improved Scalability Scales for large networks Scales even for small, highly dynamic networks Failure reaction is more localized compared to DSDVDisadvantages of CGSR20 Inflated Path lengths May not route along shortest possible paths (Price for improved scalability?) Failures adversely effect CGSR #Data packets versus #control packets? If #data packets per unit time << 1 ?Dynamic Source Routing (DSR)21 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 own identifier when forwarding RREQRoute Discovery in
View Full Document
Unlocking...