《WeakStateRoutingforLargeScaleDynamicNetwork》由会员分享，可在线阅读，更多相关《WeakStateRoutingforLargeScaleDynamicNetwork（28页珍藏版）》请在金锄头文库上搜索。
1、Weak State Routing for Large Scale Dynamic NetworksUtku Gnay Acer, Shivkumar Kalyanaraman, Alhussein A. AbouzeidRensselaer Polytechnic InstituteDepartment of Electrical, Computer & Systems Engineeringq Which area should we NOT be working on in MOBICOM anymore? qAns: Routing ! - Victor Bahl, Mobicom
2、2007 panelRouting in Large-scale Dynamic NetworksqRouting table entries: “state” = indirections from persistent names (ID) to locatorsqDue to dynamism, such indirections breakqProblematic on two dimensionsDynamism/mobility = frequent update of stateDynamism + large scale = very high overhead, hard t
3、o maintain structure qWe propose constructing routing table indirections using probabilistic and more stable state: WEAK STATENumber of NodesNode MobilityA new class of StateqStrong StateDeterministicRequires control traffic to refreshRapidly invalidated in dynamic environmentsqWeak StateProbabilist
4、ic hintsUpdated locallyExhibits persistenceSTATEBSTATEBHard, Soft and Weak StateabINSTALLSTATEASTATEAREMOVEHard StateSoft StateUPDATETime elapsed since state installed/refreshedWeak StateConfidence in state informationWeak State is natural generalization of soft stateRandom Directional WalksqBoth us
5、ed to announce location information (“put”) and forward packets (“get”)OutlineqOur Weak State RealizationqDisseminating Information and Forwarding PacketsqSimulation ResultsqDiscussion & ConclusionAn Instance of Weak StateqThe uncertainty in the mappings is captured by locally weakening/decaying the
6、 stateqOther realizations are possibleProphet, EDBF etca,b,c,d,e,fProbabilistic in terms of membershipSetofIDsGeoRegionProbabilistic in terms of scopeqConsider a node aqWhere is node a?(i): It is in region ABwith probability 1(ii) It is in region B with probability 2(1 2)Example: Weak State 128.113.
7、128.113.62.128.113.50.xnHow to “Weaken” State?Larger Geo-RegionAggregationSetofIDs - GeoRegionAggregation: setofIDsqsetofIDs: We use a Bloom filter, denoted by B. m1m2.0 1 0 0 0000 1111 11uhj(m1).kkhi(m1)hj(m2)hi(m2)Decaying/Weakening the setofIDsqRandomly reset 1s to 0. Same as EDBF Kumar et al. In
8、focom05qLet (m)=i=1m B(hi(m)qLarge (m) ! fresh mappingq(m)/k is a rough measure of Pxm 2 2 A.0 1 0 0 0000 1111 11hj(m)hk(m)h1(m)hi(m).0 1 0 0 0000 111 11.0 1 0 0 0000 1111 11.0 1 0 0 0000 111 11.0 1 0 0 0000101 11Weakening State (Contd)xnsetofIDs small, time passes:Decay GeoRegionxnxnEither setofIDs
9、 large ORGeoRegion Large =Decay SetofIDsRandom Directional WalksqBoth used to announce location information (“put”) and forward packets (“get”)Dissemination/Proactive Phase: (put)qWhen a node receives a location announcement, it creates a ID-to-location mapping aggregates this mapping with previousl
10、y created mappings if possibleABCForwarding Packets(get)Forwarding decision: similar to longest-prefix-match. “strongest semantics match” to decide how to bias the random walk.SDABCEWSR involves unstructured, flat, but scalable routing ; no flooding !Simulation ObjectivesqHow does WSR perform? Large
11、-scale High MobilityqComparisons: DSR: works well for small scale, high mobilityGLS+GPSR: works well for large scale, low mobilityq Short answer: 98%+ packet delivery despite large scale AND high mobility.qTradeoffs: longer path lengths, (N3/2) state overheadSimulation SetupqBenchmarksDSR and GLS-GP
12、SRqRandom waypoint mobility model with vmin=5 m/s and vmax=10 m/sWSR is robust against dynamism (please see the paper for details)qPerformance MetricsPacket delivery ratioControl packet overheadNumber of states maintained Normalized path lengthEnd-to-end DelayPacket Delivery RatioGLS breaks down due
13、 to overheadsDSR only delivers a small fraction of packets WSR achieves high delivery ratioControl Packet OverheadMaintaining structure requires superlinearly increasing overhead in GLSNumber of States MaintainedThe total state stored in the network increases as (N3/2) instead of (NlogN)Per-Node Sta
14、te DynamicsState generation rate matches state removal rate. Distribution of Per-Node State in the NetworkThe states are well distributed with a C.o.V 0.101Normalized Path LengthGLS sends packets only to destinations that are successfully locatedPackets take longer paths with WSRBut, E2E Delay is Lo
15、wer!WSR uses random walks for discovery & dissemination = end-to-end delay is smaller Discussion/Future WorkqWeak State Routing also relates toDTN routingUnstructured rare object recall in P2P networksDistributed HashingqFuture work: Such extensions (especially DTNs)Theoretical analysisConclusionqWe
16、ak state is soft, updated locally, probabilistic and captures uncertaintyqRandom directional walks both for location advertisement and data forwarding. qWSR provides scalable routing in large, dynamic MANETsqWSR achieves high delivery ratio with scalable overhead at the cost of increased path lengthThank youQuestions?
