Bee-inspired protocol engineering : from nature to networks

Honey bee colonies demonstrate robust adaptive efficient agent-based communications and task allocations without centralized controls - desirable features in network design. This book introduces a multipath routing algorithm for packet-switched telecommunication networks based on techniques observed in bee colonies. The algorithm, BeeHive, is dynamic, simple, efficient, robust and flexible, and it represents an important step towards intelligent networks that optimally manage resources.

The author guides the reader in a survey of nature-inspired routing protocols and communication techniques observed in insect colonies. He then offers the design of a scalable framework for nature-inspired routing algorithms, and he examines a practical application using real networks of Linux routers. He also utilizes formal techniques to analytically model the performance of nature-inspired routing algorithms. In the last chapters of the book, he introduces an immune-inspired security framework for nature-inspired algorithms, and uses the wisdom of the hive for routing in ad hoc and sensor networks. Finally, the author provides a comprehensive bibliography to serve as a reference for nature-inspired solutions to networking problems.

This book bridges the gap between natural computing and computer networking. What sets this book apart from other texts on this subject is its natural engineering approach in which the challenges and objectives of a real-world system are identified before its solution, nature-inspired or otherwise, is discussed. This balanced exposition of the book makes it equally suitable for telecommunication network designers and theorists, and computer science researchers engaged with artificial intelligence, agents, and nature-inspired techniques.

1 Introduction	p. 1
1.1 Motivation of the Work	p. 2
1.2 Problem Statement	p. 4
1.2.1 Hypotheses	p. 5
1.3 An Engineering Approach to Nature-Inspired Routing Protocols	p. 6
1.4 The Scientific Contributions of the Work	p. 7
1.4.1 A Simple, Disributed, Decentralized Multi-Agent System	p. 8
1.4.2 A Comprehensive Routing System	p. 9
1.4.3 An Empirical Comprehensive Performance Evaluation Framework	p. 9
1.4.4 A Scalability Framework for (Nature-Inspired) Agent-Based Routing Protocols	p. 9
1.4.5 Protocol Engineering of Nature-Inspired Routing Protocols	p. 9
1.4.6 A Nature-Inspired Linux Router	p. 10
1.4.7 The Protocol Validation Framework	p. 10
1.4.8 The Formal Framework for Nature-Inspired Protocols	p. 10
1.4.9 A Simple, Efficient, and Scalable Nature-Inspired Security Framework	p. 10
1.4.10 Emerging Mobile and Wireless Sensors Ad Hoc Networks	p. 11
1.5 Organization of the Book	p. 11
2 A Comprehensive Survey of Nature-Inspired Routing Protocols	p. 19
2.1 Introduction	p. 19
2.1.1 Organization of the Chapter	p. 20
2.2 Network Routing Algorithms	p. 20
2.2.1 Features Landscape of a Modern Routing Algorithm	p. 21
2.2.2 Taxonomy of Routing Algorithms	p. 22
2.3 Ant Colony Optimization (ACO) Routing Algorithms for Fixed Networks	p. 26
2.3.1 Important Elements of ACO in Routing	p. 26
2.3.2 Ant-Based Control (ABC) for Circuit-Switched Networks	p. 28
2.3.3 Ant-Based Control (ABC) for Packet-Switched Networks	p. 30
2.3.4 AntNet	p. 31
2.3.5 Ant Colony Routing (ACR) and AntNet+SELA QoS-Aware Routing	p. 33
2.3.6 A Brief History of Research in AntNet	p. 34
2.4 Evolutionary Routing Algorithms for Fixed Networks	p. 37
2.4.1 Important Elements of EA in Routing	p. 38
2.4.2 GARA	p. 39
2.4.3 ASGA and SynthECA	p. 41
2.4.4 DGA	p. 43
2.5 Related Work on Routing Algorithms for Fixed Networks	p. 44
2.5.1 Artificial Intelligence Community	p. 45
2.5.2 Networking Community	p. 46
2.6 Summary	p. 52
3 From The Wisdom of the Hive to Routing in Telecommunication Networks	p. 53
3.1 Introduction	p. 53
3.1.1 Organization of the Chapter	p. 54
3.2 An Agent-Based Investigation of a Honeybee Colony	p. 55
3.2.1 Labor Management	p. 55
3.2.2 The Communication Network of a Honeybee Colony	p. 55
3.2.3 Reinforcement Learning	p. 56
3.2.4 Distributed Coordination and Planning	p. 56
3.2.5 Energy-Efficient Foraging	p. 56
3.2.6 Stochastic Selection of Flower Sites	p. 56
3.2.7 Group Organization	p. 57
3.3 BeeHive: The Mapping of Concepts from Nature to Networks	p. 57
3.4 The Bee Agent Model	p. 58
3.4.1 Estimation Model of Agents	p. 62
3.4.2 Goodness of a Neighbor	p. 62
3.4.3 Communication Paradigm of Agents	p. 65
3.4.4 Packet-Switching Algorithm	p. 65
3.5 BeeHive Algorithm	p. 66
3.6 The Performance Evaluation Framework for Nature-Inspired Routing Algorithms	p. 69
3.7 Routing Algorithms Used for Comparison	p. 73
3.7.1 AntNet	p. 73
3.7.2 DGA	p. 73
3.7.3 OSPF	p. 74
3.7.4 Daemon	p. 74
3.8 Simulation Environment for BeeHive	p. 75
3.8.1 simpleNet	p. 75
3.8.2 NTTNet	p. 76
3.8.3 Node150	p. 76
3.9 Discussion of the Results from the Experiments	p. 76
3.9.1 Congestion Avoidance Behavior	p. 76
3.9.2 Queue Management Behavior	p. 91
3.9.3 Hot Spots	p. 93
3.9.4 Router Crash Experiments	p. 97
3.9.5 Bursty Traffic Generator	p. 99
3.9.6 Sessionless Network Traffic	p. 103
3.9.7 Size of Routing Table	p. 106
3.10 Summary	p. 107
4 A Scalability Framework for Nature-Inspired Routing Algorithms	p. 109
4.1 Introduction	p. 109
4.1.1 Existing Work on Scalability Analysis	p. 110
4.1.2 Organization of the Chapter	p. 113
4.2 The Scalability Model for a Routing Algorithm	p. 114
4.2.1 Cost Model	p. 114
4.2.2 Power Model of an Algorithm	p. 115
4.2.3 Scalability Metric for a Routing Algorithm	p. 117
4.3 Simulation Environment for Scalability Analysis	p. 117
4.3.1 simpleNet	p. 117
4.3.2 NTTNet	p. 117
4.3.3 Node150	p. 117
4.3.4 Node350	p. 118
4.3.5 Node650	p. 118
4.3.6 Node1050	p. 118
4.4 Discussion of the Results from the Experiments	p. 119
4.4.1 Throughput and Packet Delivery Ratio	p. 120
4.4.2 Packet Delay	p. 124
4.4.3 Control Overhead and Suboptimal Overhead	p. 125
4.4.4 Agent and Packet Processing Complexity	p. 128
4.4.5 Routing Table Size	p. 131
4.4.6 Investigation of the Behavior of AntNet	p. 131
4.5 Towards an Empirically Founded Scalability Model for Routing Protocols	p. 134
4.5.1 Scalability Matrix and Scalability Analysis	p. 139
4.5.2 Scalability Analysis of BeeHive	p. 140
4.5.3 Scalability Analysis of AntNet	p. 141
4.5.4 Scalability Analysis of OSPF	p. 141
4.6 Summary	p. 144
5 BeeHive in Real Networks of Linux Routers	p. 147
5.1 Introduction	p. 147
5.1.1 Organization of the Chapter	p. 149
5.2 Engineering of Nature-Inspired Routing Protocols	p. 149
5.2.1 Structural Design of a Routing Framework	p. 149
5.2.2 Structural Semantics of the Network Stack	p. 153
5.2.3 System Design Issues	p. 154
5.3 Natural Routing Framework: Design and Implementation	p. 155
5.3.1 Algorithm-Independent Framework	p. 156
5.3.2 Algorithmic-Dependent BeeHive Module	p. 157
5.4 Protocol Verification Framework	p. 162
5.5 The Motivation Behind the Design and Structure of Experiments	p. 167
5.6 Discussion of the Results from the Experiments	p. 167
5.6.1 Quantum Traffic Engineering	p. 167
5.6.2 Real-World Applications Traffic Engineering	p. 178
5.6.3 Hybrid Traffic Engineering	p. 181
5.7 Summary	p. 184
6 A Formal Framework for Analyzing the Behavior of BeeHive	p. 185
6.1 Introduction	p. 185
6.1.1 Organization of the Chapter	p. 186
6.2 Goodness	p. 186
6.3 Analytical Model	p. 189
6.3.1 Node Traffic	p. 191
6.3.2 Link Flows	p. 192
6.3.3 Calculation of Delays	p. 192
6.3.4 Throughput	p. 194
6.4 Empirical Verification of the Formal Model	p. 194
6.4.1 Example 1	p. 194
6.4.2 Example 2	p. 197
6.5 Summary	p. 201
7 An Efficient Nature-Inspired Security Framework for BeeHive	p. 205
7.1 Introduction	p. 205
7.1.1 Organization of the Chapter	p. 206
7.2 Robustness and Security Analysis of a Routing Protocol	p. 206
7.2.1 Security Threats to Nature-Inspired Routing Protocols	p. 207
7.2.2 Existing Works on Security of Routing Protocols	p. 208
7.3 BeeHiveGuard: A Digital Signature-Based Security Framework	p. 208
7.3.1 Agent Integrity	p. 209
7.3.2 Routing Information Integrity	p. 209
7.3.3 Architecture of BeeHiveGuard	p. 210
7.4 BeeHiveAIS: an Immune-Inspired Security Framework for BeeHive	p. 211
7.4.1 Artificial Immune Systems (AISs)	p. 211
7.4.2 Behavioral Analysis of BeeHive for Designing an AIS	p. 213
7.4.3 The AIS Model of BeeHiveAIS	p. 216
7.4.4 Top-Level BeeHiveAIS	p. 218
7.5 Simulation Models of Our Security Frameworks	p. 220
7.5.1 Attack Scenarios on Simple Topologies	p. 220
7.5.2 Analysis of Attacks and Effectiveness of Security Frameworks	p. 221
7.5.3 NTTNet	p. 225
7.5.4 Node150	p. 230
7.6 Summary	p. 233
8 Bee-Inspired Routing Protocols for Mobile Ad Hoc and Sensor Networks	p. 235
8.1 Introduction	p. 235
8.1.1 Existing Works on Nature-Inspired MANET Routing Protocols	p. 236
8.1.2 Organization of the Chapter	p. 237
8.2 Bee Agent Model	p. 237
8.2.1 Packers	p. 237
8.2.2 Scouts	p. 237
8.2.3 Foragers	p. 238
8.2.4 Beeswarm	p. 238
8.3 Architecture of BeeAdHoc	p. 238
8.3.1 Packing Floor	p. 239
8.3.2 Entrance	p. 239
8.3.3 Dance Floor	p. 240
8.4 Simulation Framework	p. 242
8.4.1 Metrics	p. 243
8.4.2 Node Mobility Behavior	p. 243
8.5 BeeAdHoc in Real-World MANETs	p. 247
8.5.1 A Performance Evaluation Framework for Real MANETs in Linux	p. 247
8.6 Results of Experiments	p. 252
8.7 Security Threats in BeeAdHoc	p. 257
8.8 Challenges for Routing Protocols in Ad Hoc Sensor Networks	p. 258
8.8.1 Existing Works on Routing Protocols for Wireless Sensor Networks	p. 258
8.9 BeeSensor: Architecture and Working	p. 260
8.9.1 BeeSensor Agent's Model	p. 260
8.9.2 Protocol Description	p. 261
8.10 A Performance Evaluation Framework for Nature-Inspired Routing Protocols for WSNs	p. 264
8.10.1 Metrics	p. 265
8.11 Results	p. 266
8.12 Summary	p. 269
9 Conclusion and Future Work	p. 271
9.1 Conclusion	p. 271
9.2 Future Research	p. 274
9.2.1 Quality of Service (QoS) Routing	p. 274
9.2.2 Cyclic Paths	p. 275
9.2.3 Intelligent and Knowledgeable Network Engineering	p. 277
9.2.4 Bee Colony Metaheuristic	p. 281
9.3 Natural Engineering: The Need for a Distinct Discipline	p. 281
References	p. 283
Index	p. 299

Available:*

On Order

Summary

Summary

Table of Contents