MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks

By J. Burgess, Brian Gallagher, David D. Jensen, Brian Neil Levine. Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications, 2006

2,313 citations recorded by the source corpus.

Disruption-tolerant networks (DTNs) attempt to route network messages via intermittently connected nodes. Routing in such environments is difficult because peers have little information about the state of the partitioned network and transfer opportunities between peers are of limited duration. In this paper, we propose MaxProp, a protocol for effective routing of DTN messages. MaxProp is based on prioritizing both the schedule of packets transmitted to other peers and the schedule of packets to be dropped. These priorities are based on the path likelihoods to peers according to historical data and also on several complementary mechanisms, including acknowledgments, a head-start for new packets, and lists of previous intermediaries. Our evaluations show that MaxProp performs better than protocols that have access to an oracle that knows the schedule of meetings between peers. Our evaluations are based on 60 days of traces from a real DTN network we have deployed on 30 buses. Our network, called UMassDieselNet, serves a large geographic area between five colleges. We also evaluate MaxProp on simulated topologies and show it performs well in a wide variety of DTN environments.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/ebe6a12fd8ff4525d1694580039a8c59c9bb2121

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Zhili Sun
2. Rui Zhang
3. Yong Zeng
4. Guohong Cao
5. Qinghua Li
6. Brian Neil Levine
7. Sencun Zhu
8. Qingqing Wu

Citations in the corpus

• Multicasting in delay tolerant networks: a social network perspective (2009, background): “Some works make efforts on improving data forwarding performance by either determining the data delivery likelihood [2] or spraying data to relays waiting for contacts with destinations [19], which is similar with our SDM scheme.”
• The ONE simulator for DTN protocol evaluation (2009, background): “While a few testbeds for (c) exist (such as DieselNet [3]) their flexibility is usually limited, large-scale operation " expensive " , and their use is typically limited to those running the testbed.”
• GeOpps: Geographical Opportunistic Routing for Vehicular Networks (2007, neutral): “Moreover, projects that employ vehicular DTN routing protocols like CarTel [2], DieselNet [ 1 ], Drive Through Internet [16], FleetNet [11] are available.”
• Routing in Socially Selfish Delay Tolerant Networks (2010, result): “Earlier works [2], [4] evaluate the forwarding capability of a node by the”
• Time-varying graphs and dynamic networks (2010, background): “, see [7, 10, 11, 19, 27, 29, 30]), have in common that the assumption of connectivity does not”
• Encounter: based routing in DTNs (2009, methodology): “One of the major flooding-based protocols for DTNs is MaxProp [4].”
• Directional routing and scheduling for green vehicular delay tolerant networks (2012, background): “There are some routing schemes that limit the packet replication with the consideration of storage constraints [13–16].”
• DTN routing as a resource allocation problem (2007, methodology): “We have built and deployed rapid on a vehicular DTN testbed, DieselNet [6], that consists of 40 buses covering a 150 square-mile area around Amherst, MA.”
• PeopleRank: Social Opportunistic Forwarding (2010, background): “Such information includes historical contacts with other devices [ 3 ], [4], [1], [12], [10], information about device mobility patterns [16], or, most relevant to this work, information about the social interaction between the participants [7], [11], [14].”
• Survey of Important Issues in UAV Communication Networks (2016, background): “The priorities are based on the path likelihoods to peers [60], [61].”
• Social network analysis for routing in disconnected delay-tolerant MANETs (2007, background): “Such metrics are typically based on either direct or indirect observed encounters [4, 6, 13, 18, 24].”
• Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges (2013, background): “Similar to MaxProp, the acknowledgement function is integrated for redundancy reduction.”
• Throughput Maximization for UAV-Enabled Mobile Relaying Systems (2016, background): “Note that while node mobility has been well studied for upper layer designs in communication networks [15]–[17], its exploitation for more efficient physical layer designs has only received limited attention recently [18]–[25].”
• Practical Routing in Delay-Tolerant Networks (2005, background): “Similar metrics are used in a number of epidemic protocol variants [11], [12], [13], [15], [16].”
• MORA routing and capacity building in disruption-tolerant networks (2008, methodology): “…experimentally that the addition of agents can have significant improvements to network performance; for example, in the case where it is paired with Max-Prop [4], MORA increases average delivery rates from 67% to 88% while simultaneously reducing average delivery latency from 120 min to 76 min.”
• Prioritized epidemic routing for opportunistic networks (2007, background): “Several works make use of contact history to predict future contacts to guide routing decisions, including [13] (PROPHET), [2] (MV), [4] (MaxProp), and [7].”