DOC PREVIEW
UConn CSE 3300 - Performance modeling of epidemic routing

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Performance modeling of epidemic routingIntroductionBasic epidemic routingODE models for basic epidemic routingDelay under epidemic routingRecovery from infectionExtended modelTrade-off schemesK-hop forwardingProbabilistic forwardingLimited-time forwardingHandling anti-packets: global timeout schemeSignaling overheadModel validationPerformance trade-offsPerformance trade-off under IMMUNEPerformance improvement by VACCINEEpidemic routing under constrained bufferRelated workSummaryAcknowledgementsDerivation of ODEs that consider recovery processesDerivation of the total number of copiesDerivation of ODEs from Markov chain through moment closure techniquesDelay asymptotic resultsNumber of copiesReferencesPerformance modeling of epidemic routingXiaolan Zhanga,*, Giovanni Negliab, Jim Kurosea, Don TowsleyaaDepartment of Computer Science, University of Massachusetts, Amherst, MA 01003, United StatesbUniversita`degli Studi di Palermo, ItalyReceived 1 October 2006; accepted 20 November 2006Available online 19 December 2006Responsible Editor: I.F. AkyildizAbstractIn this paper, we develop a rigorous, unified framework based on ordinary differential equations (ODEs) to study epi-demic routing and its variations. These ODEs can be derived as limits of Markovian models under a natural scaling as thenumber of nodes increases. While an analytical study of Markovian models is quite complex and numerical solutionimpractical for large networks, the corresponding ODE models yield closed-form expressions for several performance met-rics of interest, and a numerical solution complexity that does not increase with the number of nodes. Using this ODEapproach, we investigate how resources such as buffer space and the number of copies made for a packet can be tradedfor faster delivery, illustrating the differences among various forwarding and recovery schemes considered. We performmodel validations through simulation studies. Finally we consider the effect of buffer management by complementingthe forwarding models with Markovian and fluid buffer models. 2006 Elsevier B.V. All rights reserved.Keywords: Delay tolerant networks; Disruption tolerant networks; Wireless ad hoc networks; Epidemic routing; Performance modeling;Ordinary differential equations1. IntroductionEpidemic routing [28] has been proposed as anapproach for routing in sparse and/or highly mobilenetworks in which there may not be a contempora-neous path from source to destination. It adopts aso-called ‘‘store-carr y-forward’’ paradigm – a nodereceiving a packet buffers and carries that packetas it moves, passing the packet on to new nodes thatit encounters. Analogous to the spread of infectiousdiseases, each time a packet-carrying node encoun-ters a node that does not have a copy of that packet,the carrier is said to infect this new node by pa ssingon a packet copy; newly infected nodes, in turn,behave similarly. The destination receives the packetwhen it first meets an infected node. W hen the trafficload is very low, epidemic routing is able to achieveminimum delivery delay at the expense of increaseduse of resources such as buffer space, bandwidth,and transmission power. However this also leadsto link and/or storage congestion when the network1389-1286/$ - see front matter  2006 Elsevier B.V. All rights reserved.doi:10.1016/j.comnet.2006.11.028*Corresponding author. Tel.: +1 413 545 3179.E-mail addresses: [email protected] (X. Zhang), [email protected] (G. Neglia), [email protected] (J. Kur-ose), [email protected] (D. Towsley).Computer Networks 51 (2007) 2867–2891www.elsevier.com/locate/comnetis loaded. Variations of epidemic routing haverecently been proposed that exploit the tradeoffbetween delivery delay and resource consumption,including K-hop schemes [23,6], probabilistic for-warding [17,8], and spray-and-wait [26,25]. Thesedifferent schemes differ in their ‘‘infection process’’,i.e., the spreading of a packet in the network. Theyneed to be combined with a so-cal led ‘‘recovery pro-cess’’ that deletes copies of a packet at infectednodes, following the successful delivery of thepacket to the destination. Different reco veryschemes have been proposed: some are simply basedon timers, others actively spread in the network theinformation that a copy has been delivered to thedestination [8].Early efforts evaluating the perfor mance of epi-demic routing schemes used simulation [28,10,17].More recently, M arkovian models have been devel-oped to study the performance of epidemic routing[24,6,8], 2-hop forwarding [6], and spray-and-wait[26,25]. Recognizing the similarities between epi-demic routing and the spread of infectious diseases,[24,8] used ordinary differential equation (ODE)models adapted from infectious disease-spreadmodeling [3] to study the source-to-destinationdelivery delay under the basic epidemic routingscheme, and then adopted Markovian models tostudy other performance metrics.In this paper, we develop a rigorous, unifiedframework, based on ordinar y differential equations(ODE), to study epidemic routing and its variations.The starting point of our work is [6], where theauthors consider common node mobility models(e.g., random waypoint and random directionmobility) and show that nodal inter-meeting timesare nearly exponentially distributed when transmis-sion ranges are small compared to the network area,and node velocity is sufficiently high. This observa-tion suggests that Markovian models of epidemicrouting can lead to quite accurate performance pre-dictions; indeed [6] develops Markov chain modelsfor epidemic routing and 2-hop forwarding, deriv-ing the average source-to-desti nation delivery delayand the number of extant copies of a packet at thetime of delivery. An analytical study of suchMarkov chain models is quite complex for even sim-ple epidemic models, and more complex schemeshave defied analysis thus far. Moreover, numericalsolution of such models becomes impractical whenthe number of nodes is large.We develop ODEs as a fluid limit of Markovianmodels such as [6], under an appropriate scaling asthe number of nodes increases. Through the paperwe show that ODE is a valid tool for investigatingepidemic style routing. In fact this approach allowsus to derive closed-form formulas for the perfor-mance metrics considered in [6], obtaining matchingresults. More importantly, we are also able to usethe ODE framework to further model the


View Full Document

UConn CSE 3300 - Performance modeling of epidemic routing

Download Performance modeling of epidemic routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Performance modeling of epidemic routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Performance modeling of epidemic routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?