Autonomic Formation of Large Scale Wireless Mesh Networks 公开

Abstract

A Wireless Mesh Network (WMN) is an appealing network architecture for low-cost and wide geographical coverage. It serves as a potential alternative solution to improve worldwide connectivity in low to high-income countries. Theoretical studies predict, however, insufficient capacity for such network architecture at larger scales. Moreover, the inherently distributed nature of WMNs and their typical distributed network control mechanisms turned them hardened and inflexible to adapt to specific and varying control customization demands.

We propose the modernization of the WMN architecture by allowing the general applicability of Software Defined Networking (SDN) on the implementation of WMN control planes for increased control flexibility while also enforcing frequency diversity to promote throughput capacity. To achieve this, we devised autonomic agents that induce the formation of WMN topologies as a set of interconnected partitions, supporting a cooperative, multi-domain SDN-based WMN control plane able to operate at large-scales and low-cost for increased control flexibility. Moreover, the nature of this autonomic network based on WMN partitions also allows the enforcement of frequency diversity at low-cost and low-complexity for improved throughput capacity. The partitioned topology format is the result of the concurrent and distributed operation of our autonomic agents that manipulate the formation of the WMN using local information, without relying on any central controlling entity, characterizing a scalable and resilient solution. Partitions hold as invariants their maximum diameter and their maximum per node interface degree. These two induce an additional invariant: the maximum partition size in mesh nodes. Finally, the three properties permit limiting control latency and workload on Software Defined Network (SDN) control plane domains. Our agents have different objectives such as organize, heal, optimize; thus, they cooperate and compete to determine final WMN topologies. We show that the competitive/cooperative behavior of these agents converge to stable formations in bounded time even under extreme mesh node churn conditions. The solution relies on an in-network leader election and stochastic delays to achieve the eventual stabilization of formed WMN topologies.

Table of Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.1 The scaling of complex systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2 On the definition of WMNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Factors affecting the capacity and control of WMNs . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 Analytical capacity scaling of single frequency WMNs . . . . . . . . . . . . . . . . . . . . . . 9

2.4.1 Degree manipulation through directional antennas and power control . . . . . 10

2.4.2 Concentrated traffic pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.5 Capacity scaling under node clustering and multiple diversity mechanisms . . 12

2.6 Multi-channel, multi-radio WMNs (MRMC). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.7 Autonomic Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.8 Partitioned WMNs: reduced overhead and hierarchical routing . . . . . . . . . . . . . 19

2.9 Packet routing and scheduling techniques on WMNs . . . . . . . . . . . . . . . . . . . . . . 20

2.10 Community Wireless Networks and their application of WMNs . . . . . . . . . . . 24

2.10.1 The nature of CWNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.10.2 The topology structure of CWNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.11 Experimentation platforms and challenges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 An experimentation platform for the evaluation of autonomic agents . . . . . . . . 35

3.1 Agent Simulator - ASim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.1.1 ASim parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2 Network Simulator - NetSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.3 Nodes’ Containers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.4 Inter-module messaging API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.5 Time synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4 WMN capacity scaling under autonomic topology manipulation . . . . . . . . . . . . 44

4.1 Operational cycle of autonomic agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2 Autonomic behavior of agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.2.1 Manual node agent design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.2.2 Smart node agent design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.3 Visual outcome of the behavior of agents in atomic settings . . . . . . . . . . . . . 48

4.4 Scaling results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.4.1 Experimentation settings for scaling results . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.4.2 Capacity scaling results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5 Self-Organizing WMN nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.1 Design of Self-Organizing WMN nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.2 Autonomic behavior of agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.2.1 Smart node agent design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.3 Agent information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.4 Convergence of the Smart agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.4.1 Triggers for slow convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.4.2 Optimizations to improve convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.4.3 Modeling divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.5 Visual outcome of Self-Organizing agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.6.1 Experimentation settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.6.2 Experiments evaluating convergence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.6.3 Effort to convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.6.4 Resulting WMN partitioning structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6 Integrated Self-Organizing, Self-Healing WMN nodes . . . . . . . . . . . . . . . . . . . 78

6.1 Design principles for the integrated Self-Organizing, Self-Healing WMN nodes . . 78

6.2 Integrated autonomic behavior of agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.2.1 Smart-based: reference design of agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.2.2 SmartOrg: Self-Organizing agent design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.2.3 SmartHeal: Self-Healing agent design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.3 Agent information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.4 Convergence of the Smart-based agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6.4.1 New divergence scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.4.2 Pseudo-orderings for convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

6.5 Visualizing the outcome of the behavior of the integrated agents . . . . . . . . . . . . . . 87

6.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.6.1 Experimentation settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.6.2 Time to convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.6.3 Recovering global connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.6.4 Converging to defined properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6.6.5 Effort to convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6.6.6 Topology structure under integrated organizing and healing . . . . . . . . . . . . . . . . 98

7 Explorations with SDN control planes into WMNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

7.1 A reference architecture for SDN-based WMNs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

7.2 Centralized SDN-based WMN TDMA scheduler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

7.3 Contention aware multi-path mesh routing based on centralized control . . . . . . 104

7.4 WMN contention minimization: a current-flow betweenness centrality application . . 106

7.4.1 About graph centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

7.4.2 Proposed solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

7.4.3 Simulated evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

7.4.4 Section conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

8 Conclusion and future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

8.1 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

A Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

A.1 Additional information about CWNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

A.1.1 VillageTelco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

A.1.2 Replicating Internet content locally: World Possible’s projects . . . . . . . . . . . . . 123

A.1.3 The Serval Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

A.1.4 Gulfi.net . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

A.1.5 Athens Wireless Metropolitan Network. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Computer Science and Informatics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Engineering, Computer Computer Science
关键词	Programmable Networks Software-Defined Networks Autonomic Computing Wireless Networks
Committee Chair / Thesis Advisor	Avani Wildani, Emory University
Committee Members	Shun Yan Cheung, Emory University Christian Maciocco, Intel Inc. Vaidy Sunderam, Emory University

最新修改

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Autonomic Formation of Large Scale Wireless Mesh Networks ()	2020-04-16 18:54:41 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions