THESE DE DOCTORAT CONJOINT TELECOM SUDPARIS et L’UNIVERSITE PIERRE ET MARIE CURIE Spécialité: Télécommunications Ecole Doctorale EDITE: Informatique, Télécommunications et Electronique de Paris Présentée par Arshad ALI Pour obtenir le grade de DOCTEUR DE TELECOM SUDPARIS Transport Fiable, Estimation et Poursuite dans les Réseaux Delay Tolerant Networks (DTNs) Soutenue le 12 novembre, 2012 devant le jury composé de : Rapporteurs : Konstantin AVRACHENKOV Inria Sophia Antipolis, France Tamer BASAR Université d’Illinois, USA Examinateurs : Guy PUJOLLE Université Pierre et Marie Curie, France Lucile SASSATELLI Université Nice Sophia Antipolis, France Directeurs : Eitan ALTMAN Inria Sophia Antipolis, France Tijani CHAHED Telecom SudParis, France Thèse numéro: 2012TELE0038 JOINT DOCTORATE OF TELECOM SUDPARIS AND PIERRE & MARIE CURIE UNIVERSITY Speciality: Telecommunications Doctoral School EDITE: Computer Science, Telecommunications and Electronics (Paris) presented by Arshad ALI To obtain the Degree of DOCTORATE OF TELECOM SUDPARIS Topics in Delay Tolerant Networks (DTNs): Reliable Transport, Estimation and Tracking Defended on November 12, 2012 in front of the jury composed of: Reviewers : Konstantin AVRACHENKOV Inria Sophia Antipolis, France Tamer BASAR University of Illinois, USA Examiners : Guy PUJOLLE Université Pierre et Marie Curie, France Lucile SASSATELLI Université Nice Sophia Antipolis, France Directors : Eitan ALTMAN Inria Sophia Antipolis, France Tijani CHAHED Telecom SudParis, France Thesis number: 2012TELE0038 To My Parents My Wife and My Daughters 3 4 Acknowledgements I can honestly state that my journey for obtaining a doctorate degree would not have been possible without the support of many people. First of all, I thank to Prof. Tijani Chahed for his excellent guidance, support and dedication during all the time I spent working on this PhD thesis. It is my great fortune to carry out my PhD studies under his guidance. His vision, direction, and significant feed- back was the most beneficial to my doctoral research. I am grateful to him for everything, particularly, for granting me the freedom of developing my ideas. His suggestions, recom- mendations and ability to manage several diverse things together was, indeed, remarkable. I would like to take this opportunity to express my heartiest gratitude to Prof. Tijani Chahed for being such a great advisor. Iwouldliketosayspecialthankstomyco-adviser, honorableDr. EitanAltman, whose motivation and ideas, throughout my thesis research, were the real driving force towards completion of my PhD thesis. He has highly inspired me for his ideas, and whose guidance helped me a lot towards technical quality of the thesis. I am also grateful to honorable Prof. Tamer Baser, Prof. Konstantin Avrachenkov, Prof. Guy Pujolle and Prof. Lucile Sassatelli for being members of my thesis evaluation committee and providing their valuable comments through forming my thesis work. I would like to express my sincere gratitude to Prof. Lucile Sassatelli for her technical support, pleasant and precise guidance at every step of my thesis. I really learned a lot of things by working with her and benefited from her experience as well as her excellent research and technical skills. I would like to thank my friend Manoj for his continuous technical support and en- couragement throughout my thesis. Especially, his friendly company and guidance made my study more enjoyable. I liked the long discussions with him a lot. With his profound knowledge, he supported me throughout my PhD study . I am highly grateful for all the suggestions and advises he made to improve the quality of this document. I want to thank all my friends and doctoral colleagues whose friendly company and support, during my PhD work, was a source of great pleasure. I am grateful to Higher Education Commission (HEC) of Pakistan for providing gener- ousgrantstohavepursuedmyPhDstudyinFrance. IamalsogratefultoInstituteTelecom SudParis for providing excellent research facilities. I would like to thank administrative and technical staff members of Telecom SudParis who have been kind enough to help in their respective roles. Finally, my deep gratitude goes to my parents, my wife and lovely daughters. I am deeplygratefultomyparentsfortheirprayersandstandingbymeineverythingIhavedone 5 6 and giving me whatever they can. I thank to my brothers and sisters for their continuous support, encouragement and love. Last but certainly not the least, I am indebted to my wife, for her love, patience and generous support through all tough times. Thanks to my lovely and cute Ayesha, Maira and Hafsa who are a great source of peace in my life. I dedicate this thesis to them. Thanks a lot. Abstract MobileAdhocNETworks(MANETs)aimatmakingcommunicationbetweenmobilenodes feasible without any infrastructure support. If the spatial density of mobile nodes in a MANET is low, then an end-to-end path between a source and a destination almost never exists; two mobile nodes can communicate only when they come within the radio range of each other. During the last few years, motivation for development of MANETs has increased with the entry of intelligent devices with short range wireless communication methods. Sparse MANETs fall into the class of Delay Tolerant Networks (DTNs) which are intermittently connected networks and where there is no contemporaneous end-to-end path at any given time. The major or core research in DTNs addresses routing aspects while relatively fewer works exist on reliable transport; and when they do, they are mainly oriented towards deep space communication. In this thesis, we first, propose a new reliable transport scheme for DTNs based on the use of ACKnowledgments (ACKs) as well as random linear coding. We model the evolutionofthenetworkunderourschemeusingafluid-limitapproach. Weobtainmeanfile transfer times based on certain optimal parameters obtained through differential evolution approach. We account for the buffer expiry time-out, quantify its impact on the optimal values of our protocol parameters and also demonstrate the adaptability of our optimal procedure to variations in expiry time-out. Secondly, contact opportunities in DTNs are quite infrequent. This observation mo- tivates the need to take the maximum benefit of these rare contacts. We thus propose and study a novel enhanced ACK approach called Global Selective ACKnowledgment (G- SACK) to improve reliable transport for DTNs covering both unicast and multicast flows. We make use of random linear coding at relays so that packets can reach the destination faster. We obtain reliability based on the use of so-called G-SACKs that can potentially contain global information on receipt of packets at all destinations. We obtain significant improvement through G-SACKs and coding at relays. Finally, we tackle the problem of estimating file-spread in DTNs with direct delivery and epidemic routing. We estimate and track the degree of spread of a message/file in the network. We provide analytical basis to our estimation framework alongwith insights validated with simulations. We observe that the deterministic fluid model can indeed be a goodpredictorwithalargenumberofnodes. Moreover,weuseKalmanfilterandMinimum- Mean-Squared-Error (MMSE) to track the spreading process and find that Kalman filter provides more accurate results as compared to MMSE. Keywords: Delay Tolerant Networks, Transport, Linear Network Coding, Acknowledgements, Fluid and Diffusion Approximation, Kalman Filtering 7 8 Re´ sume´ Les réseaux mobiles Ad hoc (MANETs) visent à permettent à des nœuds mobiles de com- muniquer sans aucun support d’infrastructure. Si la densité spatiale des nœuds mobiles dans un MANET est faible, un chemin continu entre une source et une destination n’existe presque jamais; deux nœuds mobiles peuvent communiquer uniquement quand ils entrent dans la zone de couverture radio les uns des autres. Au cours des dernières années, la motivation pour le développement des MANETs a augmenté avec l’entrée en jeu des dis- positifs intelligents qui utilisent les communications dédiées à courte portée. Les MANETs dispersés entrent dans la catégorie des réseaux tolérants aux délais (DTN), qui sont des réseauxconnectésparintermittenceetoùiln’yaaucunchemindebout-en-bout persistant à n’importe quel temps donné. La recherche majeure dans les DTNs traite des aspects de routage tandis que les travaux sur le transporont relativement faibles; ceux qui existent sont principalement orientées vers la communication dans l’espace. Dans cette thèse, nous proposons, d’abord, un nouveau protocole de transport fiable pour les DTNs basé sur l’utilisation d’accusés de réception (ACK) ainsi que le codage linéaire aléatoire. Nous modélisons l’évolution du réseau conformément à notre plan en utilisant l’approche fluide. Nous obtenons le temps de transfert d’un fichier en fonction de certains paramètres optimaux obtenus par l’approche d’évolution différentielle. Nous tenons compte de l’expiration du délai d’attente dans le tampon, et quantifions son impact sur les valeurs optimales de nos paramètres de protocole. Nous démontrons l’adaptabilité de notre procédure de optimisation aux variations de l’expiration du délai d’attente. Deuxièmement, les occasions de contact dans les DTNs sont peu fréquentes. Cette observation motive le besoin de prendre un avantage maximal de ces contacts rares. Nous proposons ainsi et étudions un nouveau mécanisme d’ACK augmenté, que nous appelons Global Sélective ACKnowledgement (G-SACK), pour améliorer le transport fiable pour les DTNs,pourlescasunicastetmulticast.Nousnousservonsducodagelinéairealéatoireaux relaispourquelespaquetspuissentatteindreladestinationplusrapidement.Nousobtenons la fiabilité basée sur l’utilisation des G-SACKs qui peuvent potentiellement contenir des informations globales sur les paquets reçus à toutes les destinations. Nous obtenons une amélioration significative par les G-SACKs et le codage dans les relais. Enfin, nous abordons le problème de l’estimation de propagation des fichiers dans les DTNs avec livraison directe et le routage épidémique. Nous estimons et suivons le degré de propagation d’un message/fichier dans le réseau. Nous fournissons la base analytique à notre cadre d’évaluation avec des aperçus validés en se basant sur des simulations. Nous observons que le modèle déterministe fluide peut en effet être un bon prédicateur dans le cas d’un grand nombre de nœuds. En plus, nous utilisons le filtre de Kalman et Minimum- Mean-Squared Error (MMSE) pour suivre le processus de propagation et trouvons que le filtre de Kalman fournit des résultats plus précis par rapport à MMSE. mots clés : Réseaux Tolérants aux Délais (DTNs), Transport, codage linéaire aléatoire, Accusés de réception (ACK), Approximation de Fluid et Diffusion , filtre de Kalman 9 10