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

Parameterized heuristics offers an elegant and powerful theoretical framewo rk 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 propert ies of heuristic routing agents through a simulation study within a large n etwork with grid topology. A formal analysis of the underlying principles i s presented through the incremental design of a set of autonomous agents th at 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 pa per carefully derives the properties of such heuristics under a set of simp lifying assumptions about the network topology and load dynamics and identi fy the conditions under which they are guaranteed to route messages along a n optimal path, so as to avoid hotspots in the load landscape of the networ k. The paper concludes with a discussion of the relevance of the theoretica l results to the design of intelligent autonomous adaptive communication ne tworks and an outline of some directions of future research. (C) 2001 Elsev ier Science Inc. All rights reserved.