Delay Tolerant Networks Protocols and Applications Edited by Athanasios Vasilakos Yan Zhang Thrasyvoulos V. Spyropoulos (cid:105) (cid:105) “K10552˙FM” — 2011/9/8 — 13:18 — page vi — (cid:105) (cid:105) CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2012 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free paper Version Date: 20110831 International Standard Book Number: 978-1-4398-1108-5 (Hardback) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information stor- age or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copy- right.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that pro- vides licenses and registration for a variety of users. For organizations that have been granted a pho- tocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com (cid:105) (cid:105) (cid:105) (cid:105) i i “Book” — 2011/10/7 — 17:34 — page iii — i i Contents Preface v List of Contributors ix 1 Delay Tolerant Networking 1 Maode Ma, Chao Lu, and Hui Li 2 DTN Routing: Taxonomy and Design 31 ThrasyvoulosV. Spyropoulos,RaoNaveed Bin Rais, ThierryTurletti, Katia Obraczka, and Athanasios Vasilakos 3 Energy-AwareRoutingProtocolforDelayTolerantNetworks 69 Seung-Keun Yoon and Zygmunt J. Haas 4 A Routing-Compatible Credit-Based Incentive Scheme for DTNs 101 Haojin Zhu, Xiaodong Lin, Rongxing Lu, Yanfei Fan, and Xuemin (Sherman) Shen 5 R-P2P: a Data-Centric Middleware for Delay Tolerant Applications 127 CorradoMoiso, Antonio Manzalini, Francesco De Pellegrini, Iacopo Carreras,Daniele Miorandi, and Athanasios Vasilakos 6 Mobile Peer-to-Peer Systems over Delay Tolerant Networks159 Angela Sara Cacciapuoti, Marcello Caleffi, and Luigi Paura 7 Delay Tolerant Monitoring of Mobility-Assisted WSN 189 Abdelmajid Khelil, Faisal Karim Shaikh, Azad Ali, Neeraj Suri, and Christian Reinl 8 Message Dissemination in Vehicular Networks 223 Shabbir Ahmed and Salil S. Kanhere iii i i i i i i “Book” — 2011/10/7 — 17:34 — page iv — i i iv Contents 9 Delay Tolerant Networking (DTN) Protocols for Space Communications 261 Ruhai Wang, Xuan Wu, Tiaotiao Wang, and Tarik Taleb 10 DTN and Satellite Communications 283 Carlo Caini and Rosario Firrincieli Index 319 i i i i i i “Book” — 2011/10/7 — 17:34 — page v — i i Preface The standardizationof the IP protocoland its mappinginto network-specific link-layer data frames at each router as required supports interoperability usingapacket-switchedmodelofservice.Althoughoftennotexplicitlystated, a number of key assumptions are made regarding the overall performance characteristics of the underlying links in order to achieve smooth operation: • an end-to-end path exists between a data source and its peers, • themaximumround-triptimebetweenanynodepairsinthenetworkis not excessive, and • the end-to-end packet drop probability is small. Unfortunately, a classof Delay TolerantNetworks(DTN), which may violate one or more of the assumptions, is becoming important and may not be well served by the current end-to-end TCP/IP model. DTN ariseprimarilyasaresultofvariousformsofhostandroutermobil- ity, but may also come into being as a result of disconnection due to power management or interference. Examples of such networks include: • Terrestrial Mobile Networks: In many cases, these networks may become unexpectedly partitioned due to node mobility or RF interference. In other cases, the network may never have an end-to-end path and may be expected to be partitioned in a periodic and predictable manner. For exam- ple, imagine a commuter bus acting as a store and forward message switch with only limited RF communication capability. As it travels from place to place, it provides a form of message switching service to its nearby clients to communicate with distant parties it will visit in the future. •Exotic Media Networks:Exoticcommunicationmediaincludesnear- Earthsatellitecommunications,verylong-distanceradiolinks(e.g.,deepspace RFcommunicationswithlightpropagationdelaysinthesecondsorminutes), communicationusingacousticmodulationinairorwater,andsomefree-space opticalcommunications.Thesesystemsmaybesubjecttohighlatencieswith predictable interruption (e.g., due to planetary dynamics or the passing of a scheduled ship), may suffer outage due to environmental conditions (e.g., weather), or may provide a predictably available store-and-forward network v i i i i i i “Book” — 2011/10/7 — 17:34 — page vi — i i vi Preface service that is only occasionally available (e.g., low-earth orbiting satellites that “pass by” one or more times each day). •Ad-Hoc Networks:Thesesystemsmaybeexpectedtooperateinhos- tile environments where mobile nodes, environmental factors, or intentional jamming may be cause for disconnection. In addition, data traffic on these networks may have to compete for bandwidth with other services at higher priority. As an example, data traffic may have to unexpectedly wait several secondsormorewhile high-priorityvoicetrafficiscarriedonthesameunder- lying links. Such systems also may also have especially strong infrastructure protection requirements. • Sensor Networks: These networksare frequently characterizedby ex- tremely limited end-node power, memory, and CPU capability. In addition, they are envisioned to exist at tremendous scale, with possibly thousands or millions ofnodes pernetwork.Communicationwithin thesenetworksis often scheduled to conserve power, and sets of nodes are frequently named (or ad- dressed)onlyinaggregate.Theyareofteninterfacedtoothernetworksbyway of one or more “proxy” nodes that provide protocol translation capabilities. Given the large accumulated experience and number of systems compatible with the TCP/IPprotocols,it is natural to applythe highly successful Inter- net architectural concepts to these new or unusual types of networks. While such an application is conceivable, the effects of very significant link delay, non-existence of end-to-end routing paths, and lack of continuous power or large memory at end nodes present substantial operational and performance challenges to such an approach. In an effort to adapt the Internet to unusual environments, one class of approachesattempts to engineer problem links to appearmore similar to the types of links for which TCP/IP was designed. In effect, these approaches, which we term “link repair approaches,” “fool” the Internet protocols into believing they are operating over a comparatively well-performing physical infrastructure. They strive to maintain the end-to-end reliability and fate sharing model of the Internet, and generally require the use of IP in all par- ticipating routers and end nodes. Another common approach to deal with challenged networks is to attach them to the edge of the Internet only by means of a special proxy agent. This provides access to and from challenged networks from the Internet, but does not provide a general way to use such networks for data transit. Without supportingtransit, the full capabilitiesof these networkswill goun- derutilized. Indeed, supporting transit is often of particular interest because remotely-deployedconventionalnetworks(e.g., Intranets) mayonly be acces- sible through challenged intermediate networks. The bookis written for abroadaudience ofresearchersand practitioners. Thebookcouldbeausefulreferencematerialforgraduatestudentsandsenior undergraduate students in courses of networking, wireless, and mobile com- munications. Furthermore, because the book is targeted towards the latest developments in the aforementioned domains, as well as towards the visions i i i i i i “Book” — 2011/10/7 — 17:34 — page vii — i i Preface vii for our middle- and long-term future, it is expected to be useful also to se- niorresearchersandtechnologyanalystswho wantaglimpseon the future of networking. i i i i i i “Book” — 2011/10/7 — 17:34 — page viii — i i i i i i i i “Book” — 2011/10/7 — 17:34 — page ix — i i List of Contributors Shabbir Ahmed Iacopo Carreras School of Computer Science and CREATE-NET Engineering Trento, Italy The University of New South Wales Sydney, Australia Francesco De Pellegrini Azad Ali CREATE-NET Dependable Embedded Systems and Trento, Italy Software Group Darmstadt University of Technology Darmstadt, Germany Yanfei Fan University of Waterloo Angela Sara Cacciapuoti Waterloo, Ontario, Canada Department of Biomedical, Electronics, and Telecommunications Engineering Rosario Firrincieli (DIBET) Department of Electronics, University of Naples Federico II Computer Science, and Systems Naples, Italy University of Bologna Bologna, Italy Carlo Caini Department of Electronics Computer Zygmunt Haas Science and Systems University of Bologna The School of Electrical and Bologna, Italy Computer Engineering Cornell University Marcello Caleffi Ithaca, New York Department of Biomedical, Electronics, and Salil S. Kanhere Telecommunications Engineering School of Computer Science and (DIBET) Engineering University of Naples Federico II The University of New South Wales Naples, Italy Sydney, Australia ix i i i i