Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 3801/14/19 UbiNet@UCONN 1Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks--Zheng Guo01/14/19 UbiNet@UCONN 2OutlineIntroductionRelated WorkSpray and Wait RoutingOptimization under Performance ConstrainsSimulation ResultConclusionsOpen Issues01/14/19 UbiNet@UCONN 3IntroductionWhat is Intermittently Connected Networks (ICNs)?What is Delay/Disruption Tolerant Networks (DTNs)?Examples:Inter-Planetary network (IPN)Networks of animal tags: ZebraNetMilitary applications01/14/19 UbiNet@UCONN 4Illustration of DTN01/14/19 UbiNet@UCONN 5ZebraNet01/14/19 UbiNet@UCONN 6IntroductionConventional ad hoc network routing protocols like DSR or AODV are not practical in these networks.It does not mean a packet can not be delivered to its destination.New routing protocols are required.01/14/19 UbiNet@UCONN 7Related Work (Prototype)01/14/19 UbiNet@UCONN 801/14/19 UbiNet@UCONN 9Related WorkDeterministic If all the future topology of the network (as a time-evolving graph) is deterministic and known, or at least predictable.StochasticThe future topology of network is totally unknown, or just could be estimated.01/14/19 UbiNet@UCONN 10Related WorkDeterministic caseSpace time routingTree approachStochastic caseEpidemic/random spray History or predication-based approachProbabilistic routing Control movementCoding-based approaches01/14/19 UbiNet@UCONN 11EPIDEMIC ROUTING--Flooding•When a message arrives at an intermediate node, the node floods the message to all its neighbors.BASEFHJDCGIKMNL01/14/19 UbiNet@UCONN 12EPIDEMIC ROUTING--FloodingBASEFHJDCGIKMNLRepresents transmission of packet PRepresents a node that receives packet P forthe first time01/14/19 UbiNet@UCONN 13EPIDEMIC ROUTING--Flooding• Node H receives packet P from two neighbors:• potential for collisionBASEFHJDCGIKMNL01/14/19 UbiNet@UCONN 14Probabilistic RoutingOnly forward to nodes who has a higher probability (Utility function) to reach the destination according to encounter history.01/14/19 UbiNet@UCONN 15Concept DTN01/14/19 UbiNet@UCONN 16Illustrate of DTN01/14/19 UbiNet@UCONN 17DTN nodes01/14/19 UbiNet@UCONN 18Delay Isolation01/14/19 UbiNet@UCONN 19Illustrate of Delay Isolation01/14/19 UbiNet@UCONN 20Internet vs. DTN Routing01/14/19 UbiNet@UCONN 21Spray and Wait RoutingSpray phase: for every message originating at a source node, L message copies are initially spread – forwarded by the source and possibly other nodes receiving a copy to L distinct “relays”.Wait phase: if the destination is not found in the spraying phase, each of the L nodes carrying a message copy performs direct transmission01/14/19 UbiNet@UCONN 22Spray HeuristicSource spray and wait: the source node forward all L copies to the first L distinct nodes it encounters.Binary spray and wait: The source of a message initially starts with L copies; any node A that has n > 1 message copies (source or relay), and encounters another node B (with no copies), hands over to B n/2 and keeps n/2 for itself; when it is left with only one copy, it switches to direct transmission.01/14/19 UbiNet@UCONN 23Spray Heuristic•Source spray and wait •Binary spray and wait01/14/19 UbiNet@UCONN 24Spray Heuristic01/14/19 UbiNet@UCONN 25Direct Transmission and Optimization Scheme01/14/19 UbiNet@UCONN 26Optimization under Constrains01/14/19 UbiNet@UCONN 27Scalability under constrains01/14/19 UbiNet@UCONN 28Simulation ResultsCompared with:Epidemic routingRandom epidemic routingUtility-floodSeek and focus (single copy)Spray and forwardMeasuring metricsDelivery ratioEnergy consumption (transmissions)Delay01/14/19 UbiNet@UCONN 29Effect of Traffic LoadSet up:100 nodes500*500 gridRandom waypoint movement modelTransmission range 10Traffic from 200 to 1000 packets01/14/19 UbiNet@UCONN 30Effect of Traffic Load (energy consumption)01/14/19 UbiNet@UCONN 31Effect of Traffic Load (delay)01/14/19 UbiNet@UCONN 32Effect of ConnectivitySet up:100 nodes200*200 torusRandom waypoint movement modelMedium traffic load01/14/19 UbiNet@UCONN 33Effect of Connectivity01/14/19 UbiNet@UCONN 34Effect of Connectivity (energy consumption)01/14/19 UbiNet@UCONN 35Effect of Connectivity (delay)01/14/19 UbiNet@UCONN 36ConclusionsEpidemic routing provides shortest delay and highest delivery ratio but consumes too much energy.One copy forwarding has low energy consumption but low delivery ratio.Spray and wait routing is simple and efficient and reaches good trade off.01/14/19 UbiNet@UCONN 37Open IssuesThis protocol is simple and requires few information, but some information, like encounter history, may be helpful to determine which L nodes to spray to.The wait phase only depends on the encounter with destination, wasting possible routing paths.No buffer constrains are considered.01/14/19 UbiNet@UCONN