Defense Advanced Research Projects Agency
John Baras, Armand Makowski, Prakash Narayan
Objective
The principal objective of the research is the development of robust multi-models of network traffic of minimum complexity for network control and planning. The model classes under investigation are rich enough to allow a variety of on-line network measurements to be used to select the appropriate models and adjust its parameters on-line. Innovative analytical and experimental methods will be developed to assess the incremental utility of various network traffic models and classes with respect to speed, complexity and performance of the network control or management function that uses them. Part of the main goal is to systematically design model aggregation hierarchies where finer and coarser representations are communicating as frequently as needed to maintain consistency, and the network functions select and utilize automatically models of the needed granularity. We will investigate a variety of aggregation hierarchies based on time scale, on geographical/topology scale, network state, as well as values and distribution of values of various quality and performance metrics of interest.
A key objective of this research program is the development of self-organized algorithms and systems that automatically select the appropriate models and scale for the function requesting their use. This self-organization is essential in the context of the polymorphic models for network traffic and control. Self-organization is needed for both off-line and the on-line processing. It is also necessary because it is not possible to predict or simulate all the scenaria that will be encountered in the operation, management and control of complex heterogeneous networks. Our methods incorporate learning and adaptation as essential components.
Approach
This research program consists of three closely interrelated and coordinated thrusts: Network Traffic Models for Control and Planning; Adaptive Hierarchical Modeling Incorporating On-Line Measurements; Simulation Experimentation and Validation.
Under Network Traffic Models for Control and Planning, we will pursue several innovative ideas. We will develop robust multi-models of network traffic of minimum complexity for network control and planning. There is great need to link modeling and simulation with network control and management. Models and simulations are used to analyze traffic load, network behavior, to predict traffic load, network behavior, and to select high performance control and management strategies and policies. For such an effort to be successful, different models should be used at different time and size scales and for different functionalities of the network control and management system.
Specifically we will investigate self-similar and multi-fractal models of network traffic with the objective to understand the deeper reasons for such phenomena and discover and understand the "new laws" of network behavior. We will examine traffic models for three distinct time scales, motivated by different network problems of importance in each. In the "fast" time scale, times less than 100 ms protocol dynamics dominate and the important problems are dynamic queue control. In the "slow" time scale, times larger than 100 ms and shorter than 10 min, where user dynamics dominate and the important problems are aggregate flow control and resource allocation. In the even slower time scale of times longer than 10 min the important problems are network planning and dimensioning. We will develop statistical methodologies for network traffic data analysis including: analysis of measured traffic traces, traffic model fitting and parameter estimation, model parameter tuning and adaptation, wavelet and multiresolution methods, properties of estimators (bias, confidence intervals, consistency), discrete operations with uniform and non-uniform sampling, tests for fractality and multi-fractality. Models, parameter estimators and tests will be evaluated from a complexity perspective using appropriate extensions of Minimum Description Length (MDL) complexity analysis.
The development of good strategies for controlling queues with such traffic models is an important component of our approach. In this area we will investigate large buffer asymptotics for packet loss and other performance metrics for fractal and multi-fractal models, the impact of short-time fluctuations, fast approximations for performance estimations, performance of RED and variations, impact on MAC design, impact on dynamic bandwidth allocation
Network models should be robust in several ways: they should be usable for heterogeneous networks, for heterogeneous services, for heterogeneous quality of service (QoS) requirements. The models classes we are investigating are rich enough to allow a variety of on-line network measurements to be used to select the appropriate models and adjust model parameters on-line. To address this challenge we are developing innovative analytical and experimental methods to assess the incremental utility of various network traffic models and classes with respect to speed, complexity and performance of the function that uses them. A critical innovation of the approach is the development of systematic methodologies for evaluating the impact of various network traffic models (fitted to measured network traffic data) on control performance (e.g. response time, fairness, priority fidelity, packet loss), on allocation of network resources (e.g. buffer sizes, capacities), on network performance predictability (e.g. QoS predictions vs actuals, proactive fault management, network availability).
Under Adaptive Hierarchical Modeling Incorporating On-Line Measurements our approach is based on a systematic investigation of hierarchies, adaptation and self-organization within the context of large networks viewed as complex systems. Model classes will be arranged in carefully designed aggregation hierarchies where finer and coarser representations are communicating as frequently as needed to maintain consistency, and the network functions select and utilize automatically models of the needed granularity. We will investigate a variety of aggregation hierarchies based on time scale, on geographical/topology scale, network state, as well as values and distribution of values of various quality and performance metrics of interest. The latter is based on some particularly innovative ideas from dynamic control based on compressed information incorporated in the research program. Specifically we will develop: adaptive aggregation methods; trade-offs between prediction/estimation accuracy vs aggregation level/resolution; convergence, robustness, domain of validity in relation to specific control and/or management function. We will investigate minimum complexity hierarchical traffic modeling. We will also investigate hierarchical approximation models for performance evaluation including loss network models, and the impact of new traffic models on such approximations. In our approach we incorporate multiple objectives and innovative methods for linking trade-off analysis via multi-objective optimization to traffic models and simulations and to automatic differentiation techniques for sensitivity analysis.
A key ingredient of the proposed research program is the investigation of self-organized algorithms and systems that automatically select the appropriate models and scale for the function requesting the use of models. This self-organization is essential in the context of the polymorphic models proposed for network traffic and control. Self-organization is needed for both off-line and the on-line processing. It is also necessary because it is not possible to predict or simulate all the scenaria that will be encountered in the operation, management and control of complex heterogeneous networks. Our proposed methods incorporate learning and adaptation as essential components. This is accomplished partly through the structure of the models proposed, and partly through a combination of innovative ideas utilizing learning algorithms in graphical structures, reinforcement learning and its implementation through neuro-dynamic programming, and belief network methodologies.
Under Simulation, Experimentation and Validation we will investigate Importance Sampling Techniques using methods beyond large deviations (due to Long Range Dependence) with focus on the evaluation of blocking probabilities in M|G|¥ fractal or multi-fractal models, as well as in models involving the aggregation of many ON/OFF processes. Regarding software implementation we will use a mixture of UML-CORBA-JAVA environment with COTS scientific computation tools such as MATALAB, SPLUS, ILOG SOLVER and CPLEX.
Accomplishments
FY 2000 -- "New Start"
Plans for FY 2001
Our plan for FY 01 focuses on:
Self-similar traffic models and wavelet-based hypothesis testing algorithms for self-similar models and their MDL assessment. Discover mechanisms for generating and explaining self-similar characteristics in network data and their natural scales. Complexity analysis of models.
Wavelet-based estimators for Hurst parameter, and other parameters, associated with self-similar models; MDL assessment of resulting model estimators. Develop properties of parameter estimators. Complexity analysis of parameter estimators and model selection given real network traffic traces.
Development of workload models with multi-fractal characteristics. Discover natural explanations for multi-fractal behavior using cascades and protocol behaviors. Discover "new laws" of network behavior at the "fast scale".
Wavelet-based statistical inference techniques for workload models with multi-fractal characteristics and MDL assessment of model tests and estimators. Develop statistical properties and performance analysis of estimators. Complexity analysis of models, parameter estimators and tests given real network traffic.
Queuing Theory and control of finite buffer systems. Discover new "queuing theory", control and dynamic resource allocation schemes when the inputs are self-similar or multi-fractal processes. Develop asymptotic estimates for loss probabilities. Investigate interactions with random cascade models.
Technology Transition
"New Start"
Web Site
This project is sponsored by the Defense Advanced Research Projects Agency (DARPA).