Mobile Agents in Networking and Distributed Computing

Chapter 6

Network Routing

ANDRE COSTA

ARC Centre of Excellence for Mathematics and Statistics of Complex Systems, University of Melbourne, Melbourne, Australia

NIGEL BEAN

Applied Mathematics, University of Adelaide, Adelaide, Australia

6.1 INTRODUCTION

Since the early days of the ARPANET [1], adaptive decentralized routing algorithms for communications networks have been in demand. This has driven the development of a variety of autonomous systems, where routing decisions are made by a collection of agents that are spatially distributed and where each agent communicates only local information with is nearest neighbors. The first such algorithm was the distributed Bellman–Ford algorithm [1] originally developed for the ARPANET, whereby a routing “agent” resides at each network node and implements the local dynamic programming operations that are required to solve the network shortest path problem.

Recent advances in the fields of multiagent systems, ant colony optimization, and reinforcement learning have led to the proposal of mobile agent-based algorithms for the task of network routing. The majority of mobile agent-based routing algorithms extend the basic distance–vector framework [1], whereby each node maintains a measure of the cost associated with reaching each possible destination node, via each available outgoing link. However, while traditional distance–vector algorithms (such as the distributed Bellman–Ford) take administrator-assigned link weights, mobile agent-based ...