Routing in delay tolerant networking

Routing in delay tolerant networking

Routing in Delay Tolerant Networking concerns itself with theability to transport, or route, data from a source to adestination is a fundamental ability all communication networks musthave. Delay and disruption-tolerant networks(DTNs), arecharacterized by their lack of connectivity, resulting in a lack ofinstantaneous end-to-end paths. In these challenging environments,popular ad hoc routing protocols such as AODV [C. E. Perkins andE. M. Royer. Ad-hoc on-demand distance vector routing. In The SecondIEEE Workshop on Mobile Computing Systems and Applications, February1999.] and DSR [D. B. Johnson and D. A. Maltz. Mobile Computing,chapter Dynamic source routing in ad hoc wireless networks, pages153–181. Kluwer Academic Publishers, February 1996.] fail to establish routes. This is due to these protocols trying to first establish a complete route and then, after the route has been established, forward the actual data. However, when instantaneous end-to-end paths are difficult or impossible to establish, routingprotocols must take to a "store and forward" approach, where data isincrementally moved and stored throughout the network in hopes that it will eventually reach its destinationJohn Burgess,Brian Gallagher, David Jensen, and Brian Neil Levine. MaxProp: Routing for vehicle-based disruption-tolerant networks. In Proc. IEEE INFOCOM, April2006.] [Philo Juang, Hidekazu Oki, Yong Wang, Margaret Martonosi,Li Shiuan Peh, and Daniel Rubenstein. Energy-efficient computingfor wildlife tracking: design tradeoffs and early experiences withzebranet. SIGOPS Oper. Syst. Rev., 36(5):96–107, 2002.] [AugustinChaintreau, Pan Hui, Jon Crowcroft, Christophe Diot, Richard Gass,and James Scott. Impact of human mobility on opportunistic forwardingalgorithms. IEEE Transactions on Mobile Computing, 6(6):606–620,2007.] . A common technique used tomaximize the probability of a message is successfully transferred is toreplicate many copies of the message in hopes that one will succeed inreaching its destinationAmin Vahdat andDavid Becker. Epidemic routing for partially connected ad hocnetworks. Technical Report CS-2000-06, Department of Computer Science,Duke University, April 2000.] .

Routing considerations

There are many characteristics DTN protocols, including routing, musttake into consideration. A first consideration is if informationabout future contacts is readily available. For example, in
interplanetary communications, many times a planet or moonis thecause of contact disruption, and large distance is the cause ofcommunication delay. However, due to the laws of physics, it ispossible to predict the future in terms of the times contacts will beavailable, and how long they will last. These types of contacts areknown as "scheduled" or "predictable contacts"SushantJain, Kevin Fall, and Rabin Patra. Routing in a delay tolerant network. InProc. ACM SIGCOMM, 2004.] . On the contrary, indisaster recovery networks the future location of communicatingentities, such as emergency responders, may not be known. These typesof contacts are known as "intermittent" or "opportunistic contacts".

A second consideration is if mobility can be exploited and, if so,which nodes are mobile. There are three major cases, classifying thelevel of mobility in the network. First, it is possible that thereare no mobile entities. In this case, contacts appear and disappearbased solely on the quality of the communication channel between them.For instance, in interplanetary networks, large objects in space, suchas planets, can block communicating nodes for a set period of time.Second, it is possible that some, but not all, nodes in the networkare mobile. These nodes, sometimes referred to as data "MULES" [Jea D.,Somasundara A. A, and Srivastava M. B. Multiple Controlled Mobile Elements(Data Mules) for Data Collection in Sensor Networks. In Proc. IEEE/ACMInternational Conference on Distributed Computing in Sensor Systems(DCOSS), June 2005.] [Rahul C. Shah, Sumit Roy, Sushant Jain,and Waylon Brunette. Data MULEs: Modeling a Three-tier Architecture forSparse Sensor Networks. In Proc. IEEE SNPA Workshop, May 2003.] ,are exploited for their mobility. Since they are the primarysource of transitive communication between two non-neighboring nodesin the network, an important routing question is how to properlydistribute data among these nodes. Third,it is possible that the vast majority, if not all, nodes in thenetwork are mobile. In this case, a routing protocol will mostlikely have more options available during contact opportunities, andmay not have to utilize each oneAruna Balasubramanian, Brian NeilLevine, and Arun Venkataramani. DTN routing as a resourceallocation problem. In Proc. ACM SIGCOMM, August 2007.] Thrasyvoulos Spyropoulos, Konstantinos Psounis,and Cauligi S. Raghavendra. Spray and wait: An efficient routing schemefor intermittently connected mobile networks. In WDTN ’05: Proceeding ofthe 2005 ACM SIGCOMM workshop on Delaytolerant networking, 2005.] Thrasyvoulos Spyropoulos, Konstantinos Psounis,and Cauligi S. Raghavendra. Spray and focus: Efficient mobility-assistedrouting for heterogeneous and correlated mobility. In Fifth AnnualIEEE International Conference on Pervasive Computing and CommunicationsWorkshops, 2007.] . An example of thistype of network is a disaster recovery network where all nodes(generally people and vehicles) are mobile [Samuel C. Nelson,Albert F. Harris, and Robin Kravets. Event-driven, role-based mobilityin disaster recovery networks. In CHANTS 07: Proceedings of the secondworkshop on Challenged Networks, 2007.] . A second example is avehicular network where mobile cars, trucks, and buses act ascommunicating entities.

A third consideration is the availability of network resources. Manynodes, such as mobile phones, are limited in terms of storage space,transmission rate, and battery life. Others, such as buses on theroad, may not be as limited. Routing protocols can utilize thisinformation to best determine how messages should be transmitted andstored to not over-burden limited resources. As of April 2008, only recently has thescientific community started taking resource management intoconsideration, and this is still an active area of research.

Routing protocol classifications

While there are many characteristics of routing protocols, one of themost immediate ways to create a taxonomy is based on whether or notthe protocol creates replicas of messages. Routing protocols thatnever replicate a message are considered forwarding-based, whereasprotocols that do replicate messages are consideredreplication-based. This simple, yet popular, taxonomy was recentlyused by Balasubramanian et al. to classify a large number of DTNrouting protocols.

There are both advantages and disadvantages to each approach, and theappropriate approach to use is probably dependent on the scenario athand. Forwarding-based approaches are generally much less wasteful ofnetwork resources, as only a single copy of a message exists instorage in the network at any given time [DanHenriksson, Tarek F. Abdelzaher, and Raghu K. Ganti. A caching-basedapproach to routing in delay-tolerant networks. In Proceedings of16th International Conference on Computer Communications and Networks,2007. ICCCN 2007, 2007.] . Furthermore, whenthe destination receives the message, no other node can have a copy.This eliminates the need for the destination to provide feedback tothe network (except for, perhaps, an acknowledgments sent to thesender), to indicate outstanding copies can be deleted.Unfortunately, forwarding-based approaches do not allow for sufficientmessage delivery rates in many DTNs.Replication-basedprotocols, on the other hand, allow for greater message deliveryrates, since multiple copies exist in thenetwork, and only one (or insome cases, as with erasure coding, a few) must reach the destination.However, the tradeoff here is that these protocols can waste valuablenetwork resources. Furthermore, manyflooding-based protocols areinherently not scalable. Some protocols, such as Spray and Wait,attempt to compromise by limiting the number of possible replicas of agiven message.

It is important to note that the vast majority of DTN routingprotocols are heuristic-based, and non-optimal. This is due tooptimality being, in the general DTN case, NP-hard. Morespecifically "online algorithms without complete future knowledge andwith unlimited computational power, or computationally limitedalgorithms with complete future knowledge, can be arbitrarily far fromoptimal".

Replication-based routing

Replication-based protocols have recently obtained much attention inthe scientific community, as they can allow for substantially bettermessage delivery ratios than in forwarding-based protocols. Thesetypes of routing protocols allow for a message to be replicated; eachof the replicas, as well as the original message itself, are generallyreferred to as message copies or message replicas. Possible issues withreplication-based routing include:
# network congestion in clustered areas,
# being wasteful with network resources (including bandwidth, storage, and energy), and
# network scalability.

Since network resources may quickly become constrained, deciding whichmessages to transmit first and which messages to drop first playcritical roles in many routing protocols.

Epidemic routing

Epidemic routing is flooding-based in nature,as nodes continuously replicate and transmit messages to newlydiscovered contacts that do not already possess a copy of themessage. In the most simple case, epidemic routing is flooding;however, more sophisticated techniques can be used to limit thenumber of message transfers. Epidemic routing has its roots inensuring distributed databases remain synchronized, and many ofthese techniques, such as rumor mongering, can be directly appliedto routing.

PRoPHET routing protocol

Epidemic routing is particularly resource hungrybecause it deliberately makes no attempt to eliminate replicationsthat would be unlikely to improve the delivery probability of messages.This strategy is effective if the opportunistic encounters between nodesare purely random, but in realistic situations, encounters are rarely totally random. Data Mules (mostly associated with a human) move in a society andaccordingly tend to have greater probabilities of meeting certain Mules than others. The Probabilistic Routing Protocol using History of Encounters and Transitivity (PRoPHET) protocol uses an algorithm that attempts to exploitthe non-randomness of real-world encounters by maintaining a set of probabilitiesfor successful delivery to known destinations in the DTN ("delivery predictabilities") and replicating messages during opportunistic encounters only if the Mule that does not have the messageappears to have a better chance of delivering it. This strategy was first documented in a paper from 2003 A. Lindgren, A. Doria, and O. Scheln. Probabilistic routing in intermittently connected networks. In Proceedings of the Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2003), 2003.] .

An adaptive algorithm is used to determine the delivery predictabilities in each Mule. The Mule "M" stores delivery predictabilities "P"("M","D") for each known destination "D". If the Mule has not stored a predictability value for a destination "P"("M","D") is assumed to be zero. The delivery predictabilities used by each Mule are recalculated at each opportunistic encounter according to three rules:
# When the Mule "M" encounters another Mule "E", the predictability for "E" is increased: "P"("M","E")"new" = "P"("M","E")"old" + (1 - "P"("M","E")"old") * "Lencounter" where "Lencounter" is an initialisation constant.
# The predictabilities for all destinations "D" other than "E" are 'aged': "P"("M","D")"new" = "P"("M","D")"old" * "γK" where "γ" is the aging constant and "K" is the number of time units that has elapsed since the last aging.
# Predictabilities are exchanged between "M" and "E" and the 'transitive' property of predictability is used to update the predictability of destinations "D" for which "E" has a "P"("E","D") value on the assumption that "M" is likely to meet "E" again: "P"("M","D")"new" = "P"("M","D")"old" + (1 - "P"("M","D")"old") * "P"("M","E") * "P"("E","D") * "β" where "β" is a scaling constant.

The protocol has been incorporated into the reference implementation maintained by the [http://www.dtnrg.org/ IRTF DTN Research Group] and the current version is documented in an [http://www.watersprings.org/pub/id/draft-irtf-dtnrg-prophet-00.txt Internet Draft] [A. Lindgren and A. Doria, Probabilistic Routing Protocol for Intermittently Connected Networks, Internet Draft - draft-irtf-dtnrg-prophet-00.txt, February 2008] (now expired). The protocol has been trialled in real world situations during the [http://www.snc.sapmi.net/ Sámi Network Connectivity (SNC)] project and is being further developed during the EU Framework Programme 7 project [http://www.n4c.eu Networking for Communications Challenged Communities (N4C)] .

MaxProp

MaxProp was developed at the University ofMassachusetts, Amherst andwas, in part, funded by DARPA and the National Science Foundation.The original paper is found in the IEEE INFOCOM 2006 conference.MaxProp is flooding-based in nature, in that if a contact isdiscovered, all messages not held by the contact will attempt to bereplicated and transferred. The intelligence of MaxProp comes indetermining which messages should be transmitted first and whichmessages should be dropped first. In essence, MaxProp maintainsan ordered-queue based on the destination of each message, orderedby the estimated likelihood of a future transitive path to thatdestination.

MaxProp core

To obtain these estimated path likelihoods, each node maintains avector of size n-1 (where n is the number of nodes in the network)consisting of the likelihood the node has ofencountering each of the other nodes in the network. Each ofthe n-1 elements in the vector is initially set to frac{1}{|n|-1},meaning the node is equally likely to meet any other node next.When the node meets another node, j, the j^ ext{th} element of itsvector is incremented by 1, and then the entire vector is
normalized such that the sum of all entries add to 1. Note thatthis phase is completely local and does not require transmittingrouting information between nodes.

When two nodes meet, they first exchange their estimatednode-meeting likelihood vectors. Ideally, every node will havean up-to-date vector from every other node. With these nvectors at hand, the node can then compute a shortest path via adepth-first search where path weights indicate the probabilitythat the link does not occur (note that this is 1 minus thevalue found in the appropriate vector). These path weights aresummed to determine the total path cost, and are computed overall possible paths to the destinations desired (destinations forall messages currently being held). The path with the leasttotal weight is chosen as the cost for that particulardestination. The messages are then ordered by destinationcosts, and transmitted and dropped in that order.

MaxProp additions

In conjunction with the core routing described above, MaxPropallows for many complementary mechanisms, each helping the messagedelivery ratio in general. First, acknowledgements areinjected into the network by nodes that successfully receive amessage (and are the final destination of that message). Theseacknowledgements are 128-bit hashes of the message that areflooded into the network, and instruct nodes to delete extracopies of the message from their buffers. This helps free spaceso outstanding messages are not dropped as often. Second,packets with low hop-counts are given higher priority. Thishelps promote initial rapid message replication to give newmessages a "head start". Without this head start, newermessages can be quickly starved by older messages, since thereare generally less copies of new messages in the network.Third, each message maintains a "hop list" indicating nodes ithas previously visited to ensure that it does not revisit a node.

RAPID

RAPID, which is an acronym for "ResourceAllocation Protocol for Intentional DTN" routing, was developed at the University ofMassachusetts, Amherst. It was first introduced in the SIGCOMM
2007 publication, DTN Routing as a Resource Allocation Problem.The authors of RAPID argue as a base premise that prior DTN routingalgorithms incidentally effect performance metrics, such as averagedelay and message delivery ratio. The goal of RAPID is tointentionally effect a signal routingmetric. At the time of publication, RAPID has been instrumented tointentionally minimize one of three metrics: average delay, misseddeadlines, and maximum delay.

RAPID protocol

The core of the RAPID protocol is based around the concept of autility function. A utility function assigns a utility value,U_i, to every packet i, which is based on the metric beingoptimized. U_i is defined as the expected contribution ofpacket i to this metric. RAPID replicates packets first thatlocally result in the highest increase in utility. For example,assume the metric to optimize is average delay. The utilityfunction defined for average delay is U_i = -D(i),basically thenegative of the average delay. Hence, the protocol replicatesthe packet that results in the greatest decrease in delay.RAPID, like MaxProp, is flooding-based, and will thereforeattempt to replicate all packets if network resources allow.

The overall protocol is composed of four step:
* Initialization: Metadata is exchanged to help estimate packet utilities.
* Direct Delivery: Packets destined for immediate neighbors are transmitted.
* Replication: Packets are replicated based on marginal utility (the change is utility over the size of the packet).
* Termination: The protocol ends when contacts break or all packets have been replicated.

Spray and Wait

Spray and Wait is a routing protocol that attempts to gain thedelivery ratio benefits of replication-based routing as well as thelow resource utilization benefits of forwarding-based routing.Spray and Wait was developed by researchers at the University of Southern California. It was first presented at the 2005 ACMSIGCOMM conference, under the publication "Spray and Wait: AnEfficient Routing Scheme for Intermittently Connected MobileNetworks". Spray and Wait achieves resource efficiency by settinga strict upper bound on the number of copies per message allowed inthe network.

Spray and Wait protocol overview

The Spray and Wait protocol is composed of two phases: the sprayphase and the wait phase. When a new message is created in thesystem, a number L is attached to that message indicating themaximum allowable copies of the message in the network. Duringthe spray phase, the source of the message is responsible for"spraying", or delivery, one copy to L distinct "relays". Whena relay receives the copy, they enter the wait phase, where therelay simply holds that particular message until the destinationis encountered directly.

Spray and Wait versions

There are two main versions of Spray and Wait: vanilla and
binary. The two versions are identical except for how the Lcopies reach L distinct nodes during the spray phase. Thesimplest way to achieve this, known as the vanilla version, isfor the source to transmit a single copy of the message to thefirst L distinct nodes it encounters after the message iscreated.

A second version, referred to as Binary Spray and Wait. Here,the source starts, as before, with L copies. It thentransfers ext{floor}(L/2) of its copies to the first node it encounters.Eachof these nodes then transfers half of the total number of copiesthey have to future nodes they meet that have no copies of themessage. When a node eventually gives away all of its copies,except for one, it switches into the wait phase where it waitsfor a direct transmission opportunity with the destination. Thebenefit of Binary Spray and Wait is that messages aredisseminated faster than the vanilla version. In fact, theauthors prove that Binary Spray and Wait is optimal in terms ofminimum expected delay among all Spray and Wait schemes,assuming node movement is IID.

References

External links

* [http://www.dtnrg.org IRTF DTN Research Group website]
* [http://www.ietf.org/rfc/rfc4838.txt Bundle Protocol Specification]
* [http://www.isi.edu/nsnam/ns/ Network simulator (ns2)]
* [http://www.netlab.tkk.fi/tutkimus/dtn/theone/ Opportunistic network environment ONE]
* [http://www.ir.bbn.com/projects/spindle/elevatornet/ BBN's ElevatorNet (from SPINDLE project)]
* [http://www.snc.sapmi.net/ Sámi Network Connectivity (SNC) project website]
* [http://www.n4c.eu Networking for Communications Challenged Communities (N4C) project website]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Delay-tolerant networking — (DTN) is an approach to computer network architecture that seeks to address the technical issues in heterogeneous networks that may lack continuous network connectivity. Examples of such networks are those operating in mobile or extreme… …   Wikipedia

  • Delay Tolerant Networking — (DTN) is an approach to computer network architecture that seeks to address the technical issues in heterogeneous networks that may lack continuous network connectivity. Examples of such networks are those operating in mobile or extreme… …   Wikipedia

  • Delay Tolerant Networking — Das Delay Tolerant Networking (DTN) ist eine Protokollarchitektur zur Überwindung der technischen Schwierigkeiten spärlich verbundener und heterogener Kommunikationsnetzwerke. Die Architektur basiert auf dem von der NASA entwickelten… …   Deutsch Wikipedia

  • History of delay tolerant networking — The history of delay tolerant networking examines the bulk of the technologies that began the field that is known today as Delay Tolerant Networking. Research began as projects under United States government grants relating to the necessity of… …   Wikipedia

  • Mesh networking — For other meanings of the word mesh, see Mesh (disambiguation). Illustration of a mesh network Mesh networking (topology) is a type of networking where each node must not only capture and disseminate its own data, but also serve as a relay for… …   Wikipedia

  • Mobile ad hoc network — MANET redirects here. For other uses, see Manet (disambiguation). A mobile ad hoc network (MANET) is a self configuring infrastructureless network of mobile devices connected by wireless links. ad hoc is Latin and means for this purpose . [1] [2] …   Wikipedia

  • DTN — (англ. Delay Disruption Tolerant Networking) подход к построению архитектур сетей, толерантных к задержкам и частым обрывам связи. Используется NASA для сетей дальней космической связи IPN. Под задержками в DTN понимаются не только задержки …   Википедия

  • Interplanetary Internet — [ Earth to the Moon, limits the speed at which Interplanetary Internet messages would be able to travel. Due to the vast distances involved, much longer delays are incurred than in the Earth bound Internet.] The Interplanetary Internet, as… …   Wikipedia

  • History of the Internet — Main article: Internet The history of the Internet starts in the 1950s and 1960s with the development of computers. This began with point to point communication between mainframe computers and terminals, expanded to point to point connections… …   Wikipedia

  • Mobile ad-hoc network — A mobile ad hoc network (MANET) is a kind of wireless ad hoc network, and is a self configuring network of mobile routers (and associated hosts) connected by wireless links – the union of which form an arbitrary topology. The routers are free to… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”