Agent-Based Approaches to Cooperative Traffic Management in Large Communication Networks
Personnel
Dr. Johnny Wong , Professor of Computer Science
Dr. Vasant Honavar, Professor of Computer Science and of Bioinformatics and Computational Biology
Dr. Armin Mikler
Summary
With the unprecedented growth in size and complexity of modern communication networks, the development of intelligent and adaptive approaches to system management (including such functions as routing, congestion control, traffic and load management, etc.) present several research challenges. Routing in a communication network refers to the task of propagating a message from its source towards its destination. Such a routing algorithm may be required to meet a diverse set of often conflicting performance requirements (e.g., average message delay, network utilization, etc.), thus making it an instance of a multi-criterion optimization problem. In practice, routing decisions in large communication networks are based on imprecise and uncertain knowledge of the current network state. This imprecision is a function of the network dynamics, the memory available for storage of network state information at each node, the frequency of, and propagation delay associated with, update of such state information. Motivated by these considerations, we set out to investigate efficient strategies for routing in very large networks that do not rely on the maintenance and update of a global network state. This research draws on techniques in knowledge representation, decision-theoretic methods, heuristics, as well as techniques of adaptive control to develop powerful tools for the design of intelligent, adaptive, and autonomous communication networks. Some specific results of this research include (Mikler, Honavar, and Wong, 1996; Mikler, Honavar, and Wong, 2001):
- A novel knowledge representation scheme which enables each node in the network to maintain and update a small knowledge base of constant size (independent of the size of the network). This knowledge base summarizes the state of the network from the point of view of the routing agent for that node. It provides an accurate picture of the network in the immediate neighborhood of the agent and a spatio-temporally averaged summary of the network state in distant neighborhoods.
- A utility-theoretic approach to routing that allows flexible tradeoff between delay for a specific message and the overall network load (and hence expected delay for all routed messages). This mechanism takes advantage of the fact that the number of available paths (and hence the flexibility of routing decisions) grows as a function of distance between the source and destination
- Theoretical and experimental results demonstrating several desirable properties of the proposed approach including minimization of delay and load balancing over the entire network without access to accurate global network state information.
Representative Publications
- Mikler, A., Honavar, V. and Wong, J. Autonomous Agents for Coordinated Distributed Parameterized Heuristic Routing in Large Dynamic Communication Networks. Journal of Systems and Software. Vol. 56. pp. 231-246, 2001.
- Mikler, A., Wong, J. and Honavar, V. An Object-Oriented Approach to Simulating Large Communication Networks. Journal of Systems and Software. Vol. 40. pp. 151-164, 1998.
- Mikler, A., Wong, J., & Honavar, V. QuoVadis - A Framework for Intelligent Routing in Large High Speed Communication Networks. Journal of Systems and Software. Vol. 37. pp. 61-73, 1997.
- Mikler, A., Honavar, V., and Wong, J. Utility-Theoretic Heuristics for Intelligent Adaptive Routing in Large Communication Networks. Thirteenth National Conference on Artificial Intelligence (AAAI-96), Portland, OR, AAAI Press. pp. 96-102, 1996.
