Autonomous agents for coordinated distributed parameterized heuristic routing in large dynamic communication networks

Parameterized heuristics offers an elegant and powerful theoretical framework for design and analysis of autonomous adaptive traffic management agents in communication networks. Routing of messages in such networks presents a real-time instance of a multi-criterion optimization problem in a dynamic and uncertain environment; This paper describes the analysis of the properties of heuristic routing agents through a simulation study within a large network with grid topology. A formal analysis of the underlying principles is presented through the incremental design of a set of autonomous agents that realize heuristic decision functions that can be used to guide messages along a near-optimal (e.g., minimum delay) path in a large network. This paper carefully derives the properties of such heuristics under a set of simplifying assumptions about the network topology and load dynamics and identify the conditions under which they are guaranteed to route messages along an optimal path, so as to avoid hotspots in the load landscape of the network. The paper concludes with a discussion of the relevance of the theoretical results to the design of intelligent autonomous adaptive communication networks and an outline of some directions of future research. (C) 2001 Elsevier Science Inc. All rights reserved.