Gossip-Based Ad Hoc RoutingContentsAd Hoc NetworkFlooding and GossipingGossip – Bimodal BehaviorGossip – Bimodal Behavior (cont.)Slide 7GOSSIP1(p)GOSSIP1(p, k)Theorem II.1Cont.For GOSSIP1(p, k)Bimodal BehaviorExperiment – Probability variesExperiment - Probability variesExperiment – Degree of networkExperiment - θkS(p) with pExperiment - θkS(p) and θkR(p) with kGOSSIP1(p, k) - ConclusionSlide 20A two-threshold schemeGOSSIP2(p1, k, p2, n)Comparison of GOSSIP2 with GOSSIP1Prevent premature gossip deathGOSSIP3(p, k, m)Comparison of GOSSIP3 with GOSSIP1Slide 27Overview of AODVAODV + G (AODV using GOSSIP3)Comparison of AODV+G and AODVComparison of AODV+G and AODV (cont.)Slide 32Slide 33Parametric Probabilistic Sensor Network RoutingNotationDESTINATION ATTRACTORDESTINATION ATTRACTOR (cont.)DIRECTED TRANSMISSIONDIRECTED TRANSMISSION (cont.)Retransmission Probability ContourExperimentExperiment (cont.)Sample Snapshot of DIRECTED TRANSMISSIONSample Snapshot of DESTINATION ATTRACTORSample Snapshot of PURE GOSSIPExperiment ResultExperiment Result (cont.)Slide 48ConclusionSlide 50SummaryReferencesSlide 531Gossip-Based Ad Hoc RoutingYulin ZhuNov. 18, 20042ContentsIntroductionPure GossipOptimization of GossipIncorporate Gossip in AODVParametric Probabilistic Sensor Network RoutingSummary3Ad Hoc NetworkAd Hoc Network is a multi-hop wireless network with no fixed infrastructure.Applications include disaster relief, tetherless classrooms, and battlefield.Power supply of individual nodes is limited, wireless bandwidth is limited, channel condition varies greatly, and routes may constantly change for node mobility.Robust routing protocols must be developed. Some variant of flooding is usually used.4Flooding and GossipingFloodingEvery node that receives a packet retransmits the packet to all of its neighbors.Many routing messages are propagated unnecessarily.GossipEach node forwards a message with some probability.Overhead is reduced.5Gossip – Bimodal BehaviorLet the gossip probability be p. Then, in sufficiently large nice graphs, there are fractions θS(p) and θR(p) such that the gossip quickly dies out in 1 − θS(p) of the executions and, in almost all of the fraction θS(p) of the executions where the gossip does not die out, a fraction θR(p) of the nodes get the message. Moreover, in many cases of interest, θR(p) is close to 1.6Gossip – Bimodal Behavior (cont.)In almost all executions of the algorithm, either hardly any nodes receive the message, or most of them do.By making the fraction of executions where the gossip dies out relatively low while also keeping the gossip probability low, we can reduce the message overhead.7ContentsIntroductionPure GossipOptimization of GossipIncorporate Gossip in AODVParametric Probabilistic Sensor Network RoutingSummary8GOSSIP1(p)A source sends the route request with probability 1. When a node first receives a route request, with probability p it broadcasts the request to its neighbors and with probability 1 – p it discards the request; if the node receives the same request again, it is discarded.Problem with initial condition of the source having very few neighbors.9GOSSIP1(p, k)For the first k hops, we gossip with probability 1. From the hop k + 1, the gossip probability is p.GOSSIP1(1, 1) is equivalent to flooding.GOSSIP1(p, 1) is equivalent to GOSSIP1(p).10Theorem II.1For all p ≥ 0, for almost all infinite graphs, if GOSSIP1(p,0) is used by every node to spread a message, then there is a well-defined probability θ0S(p) < 1 that the message reaches infinitely many nodes. Moreover, the probability θ0F (p) that a node receives the message and forwards it in an execution where the message reaches infinitely many nodes is equal to θ0S (p).11Cont.θ0S(p) = θ0F (p) =def θ0(p) In an execution where the message does not die out, the probability that a random node receives the message is θ0(p)/p.12For GOSSIP1(p, k)θkS(p) – Probability that a message reaches infinitely many nodes.θ1S(p) = θ0(p) / pGiven that a message doesn’t die out, the probability that a node receives and forwards the message is still θ0(p).13Bimodal BehaviorEither hardly any nodes get the message, or a fraction θ0(p) / p receive the message.In cases of interest, θ0(p) is quite close to p. Thus, in almost all executions of the algorithm in sufficiently large graphs, either hardly any nodes receive the message, or most do.14Experiment – Probability variesGossiping on a random network of average degree 8.The higher the probability, the higher the fraction of nodes receive the message.15Experiment - Probability variesGossiping on a random network of average degree 8.The higher the probability, the higher the fraction of nodes receive the message.16Experiment – Degree of networkIn a 20 × 50 regular network of degree 6, gossiping with probability .65 ensure that almost all nodes get the message in almost all executions.for a 20 × 50 regular network of degree 3, we need to gossip with probability .86 to ensure that almost all nodes get the message in all executions.Conclusion: the higher the degree, the better the gossiping effect.17Experiment - θkS(p) with p A critical probability p can be chosen so that almost all the executions don’t die out.18Experiment - θkS(p) and θkR(p) with k θkR(p) = θ0(p) / p – doesn’t change with a fixed p.θ1S(p) = θ0S(p) / p. θ1S(.65) = .95, θ2S(.65) = .98, θ5S(.65) = 1.θ1S(.6) = .53, θ4S(.6) = .67, θ10S(.6) = .73.Conclusion:- As k goes from 0 to 1, there is a significant increase of θkS(p).- As k increases beyond 1, there is increase in θkS(p), but it is not significant.19GOSSIP1(p, k) - ConclusionWith p sufficiently high, we can guarantee that almost all nodes will receive the message in almost all executions. Practically, we can guarantee that the destination node receives the message, while saving a fraction of 1 – p of messages.In cases of interest, the probability is about .65 - .75. All nodes get the message using 25-35% fewer messages than flooding.20ContentsIntroductionPure GossipOptimization of GossipIncorporate Gossip in AODVParametric Probabilistic Sensor Network RoutingSummary21A two-threshold schemeWhy? In a random network, a node may have very few neighbors, thus the probability that none of the node’s neighbors will propagate