Department of Computer Science
Iowa State University
|
|
Artificial Intelligence Research Laboratory Department of Computer Science Iowa State University |
Agent-Based Approaches to Intelligent Traffic Management in Large Communication Networks
Personnel
Project Summary
Funding
Publications
Additional Information
Projects
AI Lab
With the unprecedented growth in size and complexity of modern distributed systems such as communication networks, the development of intelligent and adaptive approaches to system management (including such functions as routing, congestion control, traffic/load management, etc.) have assumed considerable theoretical as well as practical significance. Knowledge representation and heuristic techniques of artificial intelligence, decision-theoretic methods, as well as techniques of adaptive control offer a broad range of powerful tools for the design of intelligent, adaptive, and autonomous communication networks.
Routing in a communication network refers to the task of propagating a message from its source towards its destination. For each message received, the routing algorithm at each node must select a neighboring node to which the message is to be sent. 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.
For a network node to be able to make an optimal routing decision, as dictated by the relevant performance criteria, it requires not only up-to-date and complete knowledge of the state of the entire network but also an accurate prediction of the network dynamics during propagation of the message through the network. This, however, is impossible unless the routing algorithm is capable of adapting to network state changes in almost real time. 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 have developed a multi-agent system of agents each of which maintains and updates 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 agent's point of view. 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. 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.
Experimental and theoretical analysis of this approach demonstrate that this approach has several desirable properties including minimization of delay and load balancing over the entire network without access to accurate global network state information.
A long-term objective of this research is the design of completely autonomous self-managing, intelligent, low-overhead, robust and adaptive traffic management mechanisms for very large high speed communication networks of the future. Towards this objective, mechanisms that dynamically adapt network management policies in response to changes in network dynamics are of interest. This, however, requires an understanding of the complex interactions that exist between different measures of network performance and resource requirements and the development of a coherent framework that facilitates a smooth tradeoff of some of the performance measures and resource requirements against others on demand.
To appear.
© Vasant Honavar, 1999.