Defense Advanced Research Projects Agency 


John Baras, Armand Makowski, Prakash Narayan ObjectiveThe principal objective of the research is the development of robust multimodels of network traffic of minimum complexity for network control and planning. The model classes under investigation are rich enough to allow a variety of online network measurements to be used to select the appropriate models and adjust its parameters online. 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 selforganized algorithms and systems that automatically select the appropriate models and scale for the function requesting their use. This selforganization is essential in the context of the polymorphic models for network traffic and control. Selforganization is needed for both offline and the online 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. ApproachThis research program consists of three closely interrelated and coordinated thrusts: Network Traffic Models for Control and Planning; Adaptive Hierarchical Modeling Incorporating OnLine Measurements; Simulation Experimentation and Validation. Under Network Traffic Models for Control and Planning, we will pursue several innovative ideas. We will develop robust multimodels 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 selfsimilar and multifractal 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 nonuniform sampling, tests for fractality and multifractality. 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 multifractal models, the impact of shorttime 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 online network measurements to be used to select the appropriate models and adjust model parameters online. 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 OnLine Measurements our approach is based on a systematic investigation of hierarchies, adaptation and selforganization 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; tradeoffs 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 tradeoff analysis via multiobjective 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 selforganized algorithms and systems that automatically select the appropriate models and scale for the function requesting the use of models. This selforganization is essential in the context of the polymorphic models proposed for network traffic and control. Selforganization is needed for both offline and the online 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 neurodynamic 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 MG¥ fractal or multifractal models, as well as in models involving the aggregation of many ON/OFF processes. Regarding software implementation we will use a mixture of UMLCORBAJAVA environment with COTS scientific computation tools such as MATALAB, SPLUS, ILOG SOLVER and CPLEX. AccomplishmentsFY 2000  "New Start" Plans for FY 2001Our plan for FY 01 focuses on: Selfsimilar traffic models and waveletbased hypothesis testing algorithms for selfsimilar models and their MDL assessment. Discover mechanisms for generating and explaining selfsimilar characteristics in network data and their natural scales. Complexity analysis of models. Waveletbased estimators for Hurst parameter, and other parameters, associated with selfsimilar 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 multifractal characteristics. Discover natural explanations for multifractal behavior using cascades and protocol behaviors. Discover "new laws" of network behavior at the "fast scale". Waveletbased statistical inference techniques for workload models with multifractal 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 selfsimilar or multifractal processes. Develop asymptotic estimates for loss probabilities. Investigate interactions with random cascade models. Technology Transition"New Start" Web SiteThis project is sponsored by the Defense Advanced Research Projects Agency (DARPA). 
Send questions or comments about this web site to the Center for Satellite and Hybrid Communication Networks, Institute for Systems Research, University of Maryland. 