Luận án tiến sĩ: Topology and routing in overlay networks

Topology and Routing in Overlay Networks by Kishore Kothapalli A dissertation submitted to The Johns Hopkins University in conformity with the requirements for the degree of Doctor of Philosophy. Baltimore, Maryland June, 2006 © Kishore Kothapalli 2006 All rights reserved UMI Number: 3240749 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.

Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3240749 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Abstract In this age of information, new models of information exchange methodologies based on overlay networks are gaining popular attention. Overlay networks provide a logical interconnection topology over an existing physical network. Overlay networks offer bene- fits such as ease of implementation, flexibility, adaptability, and incremental deployability.

Due to the wide range of applications and advantages, formal study of overlay networks is required to understand the various research challenges in this context. In this thesis, we study two classes of overlay networks namely peer-to-peer networks and wireless ad hoc networks. Our focus will be along two central issues in overlay net- works: how to arrive at efficient topologies and how to provide efficient routing strategies. Peer-to-peer networks have gaineda lot of research attention in recent years for various reasons.

Despite many advances however, fundamental questions such as how to design deterministic constructions, and how to organize peers of non-uniform bandwidth have remained open. In this thesis, we answer these questions by providing a deterministic overlay topology, Pagoda, that can be used for efficient routing, data management and multicasting. Given the difficulty of arriving at good deterministic topologies in a purely decentralized manner, we also propose a unified methodology to create a large class of H overlay topologies via an approach called the supervised overlay networks. We show that this approach also has other advantages such as support for rapid peer join/leave and rapid repair.

For the case of wireless ad hoc networks, we start by providing a model for wireless communication that is much more realistic than the models that are being used in the theo- retical community. Using this model, we show how to arrive a sparse spanner construction based on dominating sets. We then use the spanner construction to provide efficient algo- rithms for broadcasting and information gathering in wireless ad hoc networks. All our algorithms are simple, self-stabilizing and require only a constant amount of storage at any node.

Thus, our algorithms are also applicable in a wide variety of scenarios such as simple sensor devices. Advisor: Professor Christian Scheideler Readers: Professor Rao Kosaraju and Professor Andreas Terzis 1H Dedicated to the memory of my mother Acknowledgements First and foremost I express my gratitude to my advisor Dr. Christian Scheideler for supporting me, and sharing many of his insights. His clarity of thought and expression, timely and sound advice have been of immense help and a huge inspiration.

Thanks are also due to the members of my thesis committee, Prof. Rao Kosaraju, Prof. James Fill, Prof. Jin Kung, and Prof.

Andreas Terzis for their valuable feedback. I wish to take this opportunity to thank my teachers, Prof. Rao Kosaraju, Prof. James Fill, Prof.

Sanjeev Saxena, and many others from whom I have benefited immensely during the course of my education. It was a rewarding experience to work with Prof. Andrea Richa, Prof. Christian Schin- delhauer, Ankur Bhargava, Chris Riley, Mark Thober, and Melih Onus.

I wish to thank Prof. Hager for his advice while working towards a qualifier project. I was lucky to have made some good friends at the Johns Hopkins University Ankur Kapoor, Paritosh Shroff, Sandeep Sarat, Debraj Ghosh, and many others. For all the good times, thank you all.

Thanks also to friends from my earlier days at Warangal and Kanpur, especially Kiran Tati, Sriram Gorti, Sreekanth Bharatham, and Subbarao Denduluri. Last but not the least, thanks are also due to my family members whose constant sup- port and encouragement could always be counted upon even under difficult circumstances. VI Contents Abstract ii Acknowl edgements FUABKDWNHe List of Figures 1 Introduction 1.1 Models of Computing © 6. ee ee ha l.hà kh kia 1.2 Client-server computing.

ch hư hà ha 1.3 Peer-to-peercompUng.2 Why Logical Network§?. gi kh hư Ha. Provisioning Special Featife$S.2 Virtual Private Networks (VPNs). 6-0 he —¬oCŒ*`2xœ©) 1.4 Internet Transparency and Symmetry ee.

Overlay Networks - A Brief HistOrV.1 Peer-to-Peer Networks 2. kh hà ha 1.2 Wireless Ad Hoc Networks.5 Relation to other areas ww.2 Content Distribution Network (CDN) .6 Organization of the theSÌS. Q Q Q Q HH hở 2 Terminology and Notation 2.2 Basic Probability kh kh 2.3 Basic Graph Theory. 0 gi hà Kha 2.4 Basic Network Topologies 2.5 Basic Routing Theory.

gà gà kh ưa Vii 3 Our Contributions 35 3.1 Key Qu€eSULONS.2 Vertex COlOFÌNE. cuc Q HQ ee ko ta 37 3.1 Deterministic Construction for Heterogeneous Pees.2 Supervised Peer-to-peer Systems.4 Wireless Ad Hoc Networks «00. ee ee ee ơn kg 42 Vertex Coloring 45 Vertex Coloring 46 4. nh HH hà kg gà ki va 47 4.

Model and Defniions. ch Hà Hà kg kg va xa 52 4. Quà kh at 53 4.4 Summary of ourapproach .5 Organization of the Chapter. gà kg ga kia tia 56 4.3 Upper Bound for Constant Degree Oriented Graphs.4 Upper Bound for Arbitrary Oriented Graphs.3 FurtherImprovements hà kia kia .5 Chapter Summary and Acknowledgements.

ee ee ee es 74 II Peer-to-peer Overlay Networks P2P Networks: Deterministic Constructions 5.1 Overlay networks for uniform p€ETS.2 Overlay networks for non-uniform peerSs.3 Overlay networks for multicasting .5 ee Restofthe Chapter.2 kh kh kg The static Pagoda network 2.3 The dynamic Pagoda network for uniform nodes.1 Isolated Join and Leave operations. ee ee he 5.2 Concurrent Join and Leave OperalonS.4 The dynamic Pagoda network for non-uniform nodes.1 Join and Leave operations 2. cu eeki ki ha vii 5.1 The concurrent multicast problem. cv vu ee ee 5.2 Routing SHA[BY.

Q Q Q HQ HH ee 5.4 Tuming multicast flows into trees 2. ee ee ee 5.6 Multicasting in a dynamic setting: vitualhomes.6 Chapter summary and acknowledgem€nñtS. eee et eee ees P2P Networks: Supervised P2P Systems 115 6. cv kg Q kg k va 115 6.

cv ru ee 116 6. 0Q Q LH ng ee 118 6.2 A general framework for supervised peer-to-peer systems .1 The hierarchical decomposition technique.2 The continuous-discrete technique.3 The recursive labeling technique. ee ee ee ee ee 122 6.4 Putting all pieces together. cu gi kh k k kg 128 6.

Q Dynamic Hypercube NetwOorkK. ee he ee ee ee.2 Dynamic de Bruijn Network ©. gà kh kh ki k kg 131 6.1 Concurrent Join/Leave ÔperatOnS.5 Robustness against Random Faults.1 The Random FautModel.6 Robustness against Adaptive Adversarial Attaeks.1 The Semi-adaptive Model .2 The Fully Adaptive Model. ee ee ee 146 6.

ch ee ee 149 6. Massive Multi-player Online Gaming. kh hà kh ki ai Hi. ch 151 III Wireless Ad hoc Networks 7 Wireless Ad Hoc Networks: Model and Spanner 7.

c c c c c c vu gà kg gà VN k VN xà sa 7.2 Models of Wireless NetfWOTKS. 0L Q Q Q LH vn ng kg k kg va 7.1 Unit Disk Graph (UDG) model.2 Packet Radio Network (PRN) model.3 A new model for wireless communication. ee ee ix 7.2 Transmission range, interference range, and physical carrier sensing range. kg kh à kà Ha 163 7.

Constant density dominating S€L.2 Constant density SDAnDET. Q Q Q HQ ee ee 169 7.6 Overview of spanner protOCol.7 Phase I: dominating SeE. gà na 182 ra.8 Constant density SDARRET. uc Q Q ee ko 183 7.1 Phase II - Distributed Leader Coloing.2 Phase III - Gateway Discovery.9 Chapter Summary and Acknowledgements.

193 8 Wireless Ad Hoc Networks: Broadcasting and Gathering 195 8. kg cà kg cv kg kg ki kg RA 196 83 RelatedwOrK. cà kg kg xà kia ky va 199 1° 6. uc co cu gà k ki KT VY 204 8.

ee ee va 207 8.6 Broadcasting Multiple Messages. cà kh KV 209 8. co cu HH HQ hà gi. ch HH HH HQ ga kg 212 8.1 ee eee Stage 1: Building Gathering TreeT(s) .2 Stage 2: Gathering on T(s) 2.3 Self-stabilization HQ kg ©.8 Chapter Summary and Acknowledgements 222 9 Conclusions 223 Bibliography 225 Vita 244 List of Figures 1] A logical (overlay) netWOTK.2 Figure (a) shows a client-server model of computing where the server handles all the requests of the clients.

Figure (b) shows a supervised peer-to-peer system where the server has certain limited functionality and clients (peers) are allowed to com- municate with each other. The bold lines indicate the client-client communication links. Figure (c) shows a pure peer-to-peer system where there is no central server. The figure is based on Figure 2.

ee ee ees 1.3 A CDN in operation. The figure is based on [120, Figure 9. 21 The structure of atree, 2.2 The structure of M(m,1), T(4,2), and M(2,3).3 The structure of BF(3).4 The structure of DB(2,2) and DB(2,3).1 Figure shows that edge orientations can be provided naturally in many scenarios.2 Orientation helps in symmetry breaking. In Figure (a) both v and w choose the same color.

In (b), for existing algorithms both remain uncolored whereas in (c), when using orientation, node v may getcolored.3 Coloring constant degree oriented graphs by random choices.4 Connected component of uncolored nodes. The number at the uncolored nodes within the connected component gives the layer number they belongto.5 Algorithm for any node u.6 Improved algorithm for Phasel. es ee ee 70 5.1 kg ki va The structure of 2B(3).2 The structure of PG(2) consisting of DXN(0), DXN(1) and DXN(2). The tree edges are shown in dashed lines and the shortcut edges are shown in dotted lines.3 Figure (a) shows the operation of stage | and (b) shows the operation of stage 2.1 The decomposition tree ford = 2.2 Logical organization of nodes into five sets.

The number against node position indicates the set to which the node belongsto,.3 Physical organization of nodes into five SE. ee es 7Ì Neighborhood of node u according to UDG model.2 Neighborhood of node u according toPRN model.3 The general transmission, interference model.4 Figure in (a) shows the hidden node problem where nodes A and C cannot send to B at the same time and (b) shows the exposed node problem where C’ cannot sent packets to 2 while B is sending to A as Ở senses busy medium though A is out of the transmission rangeofC.5 Properties of the new model for wireless communication.6 Two consecutive rounds of the spanner protocol. ee ee es 77 The spanner of the original network, ©.1 An example network with node s the source of the broadcast.- Xii Chapter 1 Introduction As the age of information has dawned upon us, it has become imperative that efficient informa- tion exchange methodologies be studied. While traditional network models certainly broadened the knowledge and understanding of information exchange, new and emerging paradigms require a dif- ferent approach.

Overlay networks, which are logical networks over an existing network, are becom- ing more common. Overlay networks supporting a range of functionality such as grid computing, file sharing, sensor networks, and wireless ad hoc networks are being studied heavily. Evidenced by the success of early applications using overlay networks such as Gnutella [50], and distributed.