Scalable Online Network Modelling and Simulation

Scalable Online Network Modelling and Simulation
This is a project funded by DARPA-ITO. Contract number: F30602-00-2-0537

Project Summary

Objectives
Approach
Recent Accomplishments
Technology Transfer

Principal Investigators

Research Assistans

Publications

Presentations

Project Synopsis

This project has started on July 1, 2000.

Objectives

The main objective of this project is to advance fundamentally network modeling and simulation and network experiment design to enable automated network management and control.

A single simulation-run only measures the performance of a single scenario. A set of simulations together may be required to envision the breadth of future scenarios. The maximum potential of the online simulation approach is to address network management automation issues in large-scale networks. The goal of this project is to provide twin technology breakthroughs and understanding in the domain of online simulation and scalability of this approach to large networks that together enable to fulfill the full potential of online simulation in network management.

Approach

The scalability problem of large-scale online simulation for network management has to be tackled in several dimensions, and the scalability gains achievable in these several dimensions have to be closely integrated. The development of this integrated, scalable online simulation system is the core of our approach.

The dimensions in which we propose to address the scalability problem of online simulation are as follows:

Fundamental advances in online collaborative simulation and development of the theory and algorithms for a fast (hopefully logarithmic) convergence of such a simulation to its fixed-point solution.
Fundamental advances in modeling and abstraction, especially in the context of on-line operation and interfacing with an online simulation. The purpose of modeling and abstraction is to dramatically reduce model complexity within well-defined validation guidelines.
Development of intelligent parameter state space search and experiment design techniques to optimize the number of experiments required to come up with statistically sound, and presumably ``better'' parameter prescriptions for the underlying protocols.

These multiple dimensions will be tightly integrated in the final system because each dimension dictates the requirements of the others, and a number of optimizations can be made by innovations which might cross-cut multiple dimensions. Since the scope and number of innovations is vast, we will also adopt a pragmatic approach of incorporating ideas and infrastructure developed by other DARPA projects (e.g., simulation work done at Rutgers, USC/ISI, Georgia Tech, UCLA) as far as possible into our approach.

Recent Accomplishments

Demonstrated superlinear speedup for simulations of decomposed network for UDP traffic in large networks under ns.
Implemented ns extension supporting domain definition and network decomposiinteroperability lators enabling tion. Developed algorithm for iterating over simulation time intervals to converge to the fixed point solution in a time logarithmic in the simulation accuracy.
Developed a standard interface between net of different simulators as well as some analytical network models.
Demonstrated on-line simulation scheme on a network configuration with 4 routers and a number of hosts in a space of than 10 parameters (for 4 RED queues).
Designed a new search algorithm that takes advantage of the statistical properties of pure random search to achieve high efficiency without imposing extra restriction, e.g., differentiability, on the objective function. The new algorithm is also robust to noise in the evaluation of objective functions.
Implemented a preliminary version of an unified search framework in Java, that can operate upon any OS platform and use any type of computing resource. The framework maintains a pool of computing resources and a pool of search methods, such as deepest descent, random sampling etc. Multiple experiment designers are run simultaneously in a multi-threaded manner.
Demonstrated a scheme to achieve stable routing using Online Simulation in a test network of linux routers running OSPF which uses a new routing metric.
Developed analytic models for the throughput and latency of TCP Tahoe, Reno and SACK.
Investigated the performance of TCP versions under independent and correlated losses as well as the contribution of TCP to the self-similarity of network traffic. Showed that the degree of self-similarity is directly proportional to the loss rates and TCP's timeout an mechanisms are causes for self-similarity.
Developed a lightweight simulator for TCP traffic which accurately models the throughput and fractal behavior of TCP traffic.

The results of the research have been presented in nine papers published or submitted for publication in FY00.

Technology Transfer

The current and past DARPA grants were the basis for three patent applications filed by RPI in December 2000. These patent applications were transferred to the Premonitia, Inc, a startup company in Waltham, MA in which the Principal Investigators of this grant are co-ecse rks.founders. The company is working on products based on these patents.

Java RMI-based Farmer-Worker and Experiment Design Modules
If the global optimization is considered as a resouce ge the resourcesampling procedure to find the global optimum in the shortest time, an optimization algorithm is just a combination of sampling methods and a strategy to allocate the finite supply of computing resources among these methods to achieve high efficiency. Unified Search Framework (USF) is a general JAVA platform to support the above concept. The USF includes various sampling methods as the building blocks, and any optimization algorithm can be easily built upon and thus integrated into the USF platform by simply combining several building blocks. To make best of the available computing resources, the USF can also run multiple optimization algorithms at the same time. In the framework, the computing resources are typical composed of a network of work stations and PCs, the USF includes the facility to utilize these resources and auto allocation among the running algorithms. Since based on No Free Lunch Theorem, no single algorithm is the best for all optimization problems, the USF also tries to identify the features of the optimization problem and adjust the resource allocation among the algorithms to achieve high efficiency.