research-article

Delegation forwarding

Authors:

Vijay Erramilli,

Augustin Chaintreau,

Christophe DiotAuthors Info & Claims

MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing

Pages 251 - 260

https://doi.org/10.1145/1374618.1374653

Published: 26 May 2008 Publication History

Abstract

Mobile opportunistic networks are characterized by unpredictable mobility, heterogeneity of contact rates and lack of global information. Successful delivery of messages at low costs and delays in such networks is thus challenging. Most forwarding algorithms avoid the cost associated with flooding the network by forwarding only to nodes that are likely to be good relays, using a quality metric associated with nodes. However it is non-trivial to decide whether an encountered node is a good relay at the moment of encounter. Thus the problem is in part one of online inference of the quality distribution of nodes from sequential samples, and has connections to optimal stopping theory. Based on these observations we develop a new strategy for forwarding, which we refer to as delegation forwarding.

We analyse two variants of delegation forwarding and show that while naive forwarding to high contact rate nodes has cost linear in the population size, the cost of delegation forwarding is proportional to the square root of population size. We then study delegation forwarding with different metrics using real mobility traces and show that delegation forwarding performs as well as previously proposed algorithms at much lower cost. In particular we show that the delegation scheme based on destination contact rate does particularly well.

References

[1]

Ajtai, M., Megiddo, N., and Waarts, O. Improved Algorithms and Analysis for Secretary Problems and Generalizations. In IEEE FOCS (1995), pp. 473--482.

Digital Library

[2]

Balasubramanian, A., Levine, B., and Venkataramani, A. DTN Routing as a Resource Allocation Problem. In ACM SIGCOMM '07.

Digital Library

[3]

Broder, A., Kirsch, A., Kumar, R., Mitzenmacher, M., Upfal, E., and Vassilvitskii, S. The Hiring Problem and Lake Wobegon Strategies. In ACM-SIAM SODA 08.

Digital Library

[4]

Burgess, J., Gallagher, B., Jensen, D., and Levine, B. N. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proc. IEEE INFOCOM (April 2006).

[5]

Cai, H., and Eun, D. Y. Crossing over the bounded domain: from Exponential to Power-law inter-meeting time in MANET. In ACM MobiCom '07.

Digital Library

[6]

Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R., and Scott, J. Pocket Switched Networks: Real-world mobility and its consequences for Opportunistic Forwarding. Tech. Rep. UCAM-CL-TR-617, University of Cambridge, 2005.

[7]

Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R., and Scott, J. Impact of Human Mobility on Opportunistic Forwarding Algorithms. IEEE Trans. on Mobile Computing 6, 6 (2007), 606--620.

Digital Library

[8]

Daly, E. M., and Haahr, M. Social network analysis for routing in disconnected delay-tolerant MANETs. In ACM MobiHoc '07 (2007), pp. 32--40.

Digital Library

[9]

Dubois-Ferriere, H., Grossglauser, M., and Vetterli, M. Age matters: efficient route discovery in mobile ad hoc networks using encounter ages. In ACM MobiHoc '03, pp. 257--266.

Digital Library

[10]

Eagle, N., and Pentland, A. Reality mining: Sensing complex social systems. Journal of Personal and Ubiquitous Computing 10, 4 (2005), 255--268.

Digital Library

[11]

Erramilli, V., Chaintreau, A., Crovella, M., and Diot, C. Diversity of forwarding paths in pocket switched networks. In ACM/SIGCOMM IMC (Oct. 2007), pp. 161--174.

Digital Library

[12]

Garetto, M., Giaccone, P., and Leonardi, E. Capacity scaling in delay tolerant networks with heterogeneous mobile nodes. In ACM MobiHoc '07 (2007), pp. 41--50.

Digital Library

[13]

Jain, S., Fall, K., and Patra, R. Routing in a Delay Tolerant Network. In ACM SIGCOMM '04, pp. 145--158.

Digital Library

[14]

Jones, E. P. C., Li, L., and Ward, P. A. S. Practical routing in delay-tolerant networks. In WDTN '05 (2005), pp. 237--243.

Digital Library

[15]

Karagiannis, T., Boudec, J.-Y. L., and Vojnovic, M. Power law and Exponential decay of inter contact times between mobile devices. In MobiCom '07 (2007), ACM, pp. 183--194.

Digital Library

[16]

Leguay, J., Friedman, T., and Conan, V. DTN routing in a Mobility Pattern Space. In ACM WDTN '05, pp. 276--283.

Digital Library

[17]

Lindgren, A., Doria, A., and Schelen, O. Probabilistic routing in intermittently connected networks. SIGMOBILE Mob. Comput. Commun. Rev. 7, 3 (2003), 19--20.

Digital Library

[18]

Liu, C., and Wu, J. Scalable routing in delay tolerant networks. In MobiHoc '07 (2007), ACM, pp. 51--60.

Digital Library

[19]

McNett, M., and Voelker, G. M. Access and mobility of wireless pda users. SIGMOBILE Mob. Comput. Commun. Rev. 7, 4 (2003), 55--57.

Digital Library

[20]

Sarafijanovic-Djukic, N., Pidrkowski, M., and Grossglauser, M. Island hopping: Efficient mobility assisted forwarding in partitioned networks. In IEEE SECON '06.

[21]

Shiryaev, A. N. Optimal Stopping Rules. Springer, 2008.

[22]

Spyropoulos, T., Psounis, K., and Raghavendra, C. Efficient routing in intermittently connected mobile networks: The multi copy case. IEEE/ACM Trans. Netw. 2, 2 (2008), 477--486.

Digital Library

[23]

Vahdat, A., and Becker, D. Epidemic Routing for Partially Connected Ad Hoc Networks. Tech. Rep. CS-200006, Duke University, 2000.

Cited By

Hasan SSharifi Sani MIranmanesh SAl-Bayatti AKhan SRaad R(2023)Enhanced Message Replication Technique for DTN Routing ProtocolsSensors10.3390/s2302092223:2(922)Online publication date: 13-Jan-2023
https://doi.org/10.3390/s23020922
Seong HKim JShin WLee H(2023)FiFo: Fishbone Forwarding in Massive IoT NetworksIEEE Internet of Things Journal10.1109/JIOT.2022.321694710:5(4339-4352)Online publication date: 1-Mar-2023
https://doi.org/10.1109/JIOT.2022.3216947
Yuwei ZSatoshi F(2023)Acceleration of Sociality-Aware Message Routing in Opportunistic Networks2023 Eleventh International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW60564.2023.00016(45-51)Online publication date: 27-Nov-2023
https://doi.org/10.1109/CANDARW60564.2023.00016
Show More Cited By

Index Terms

Delegation forwarding
1. Networks
  1. Network types

Recommendations

Forwarding in opportunistic networks with resource constraints
CHANTS '08: Proceedings of the third ACM workshop on Challenged networks

Effective forwarding in mobile opportunistic networks is a challenge, given the unpredictable mobility of nodes, short contact durations between nodes, wireless interference and limited buffer sizes.

Most forwarding algorithms aim at decreasing costs (...
Exploiting Contact Spatial Dependency for Opportunistic Message Forwarding

The movement of real users often follows patterns that can be characterized by certain statistical metrics of the contacts. Such metrics are useful for routing decisions, especially in sparse mobile ad hoc networks where node connectivity is ...
An Opportunistic Network Coding Routing for Opportunistic Networks

In opportunistic networks (OppNets), instead of assuming a complete path, messages are exchanged opportunistically when two nodes encounter. To support efficient and reliable end-to-end messaging in OppNets, a number of routing protocols based on ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing

May 2008

474 pages

ISBN:9781605580739

DOI:10.1145/1374618

General Chair:
Xiaohua Jia
City University of Hong Kong, Hong Kong
,
Program Chairs:
Ness B. Shroff
Ohio State University, USA
,
Peng-Jun Wan
Illinois Institute of Technology, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc08

Sponsor:

MobiHoc08: The Ninth ACM International Symposium on Mobile Ad Hoc Networking and Computing

May 26 - 30, 2008

Hong Kong, Hong Kong, China

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

292
Total Citations
View Citations
1,252
Total Downloads

Downloads (Last 12 months)56
Downloads (Last 6 weeks)42

Reflects downloads up to 24 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hasan SSharifi Sani MIranmanesh SAl-Bayatti AKhan SRaad R(2023)Enhanced Message Replication Technique for DTN Routing ProtocolsSensors10.3390/s2302092223:2(922)Online publication date: 13-Jan-2023
https://doi.org/10.3390/s23020922
Seong HKim JShin WLee H(2023)FiFo: Fishbone Forwarding in Massive IoT NetworksIEEE Internet of Things Journal10.1109/JIOT.2022.321694710:5(4339-4352)Online publication date: 1-Mar-2023
https://doi.org/10.1109/JIOT.2022.3216947
Yuwei ZSatoshi F(2023)Acceleration of Sociality-Aware Message Routing in Opportunistic Networks2023 Eleventh International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW60564.2023.00016(45-51)Online publication date: 27-Nov-2023
https://doi.org/10.1109/CANDARW60564.2023.00016
Ahmad KFathima MHossen MAhamed JAhmad K(2023)Opportunistic Networks: An Empirical Research of Routing Protocols and Mobility ModelsSN Computer Science10.1007/s42979-023-02054-y4:5Online publication date: 28-Aug-2023
https://doi.org/10.1007/s42979-023-02054-y
Xu GSong MFu HHuang BWei FSi Q(2022)An Energy-equilibrium Opportunity network routing algorithm based on Game theory and Historical similarity rate2022 18th International Conference on Mobility, Sensing and Networking (MSN)10.1109/MSN57253.2022.00026(76-83)Online publication date: Dec-2022
https://doi.org/10.1109/MSN57253.2022.00026
Soelistijanto B(2022)Construction of Optimal Membership Functions for a Fuzzy Routing Scheme in Opportunistic Mobile NetworksIEEE Access10.1109/ACCESS.2022.322721310(128498-128513)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3227213
Dalal RKhari MAnzola JGarcia-Diaz V(2022)Proliferation of Opportunistic Routing: A Systematic ReviewIEEE Access10.1109/ACCESS.2021.313692710(5855-5883)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2021.3136927
Papapetrou ELikas A(2022)A replication strategy for mobile opportunistic networks based on utility clusteringAd Hoc Networks10.1016/j.adhoc.2021.102738125:COnline publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1016/j.adhoc.2021.102738
Savita Verma A(2022)Eigen Vector Centrality (EVC) Routing for Delay Tolerant Networks: A Time Associated Matrix-Based ApproachWireless Personal Communications10.1007/s11277-022-09996-1128:2(1217-1233)Online publication date: 12-Sep-2022
https://doi.org/10.1007/s11277-022-09996-1
Mishra SGupta R(2022)Routing Protocols in an Opportunistic Network: A SurveyComputer Networks, Big Data and IoT10.1007/978-981-19-0898-9_14(185-195)Online publication date: 22-May-2022
https://doi.org/10.1007/978-981-19-0898-9_14
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents