PARALLEL COMPUTING LABORATORY

MAYA: Next Generation Performance Prediction Tools for Global Networks

To develop Maya, a multi-paradigm network modeling framework, together with a characterization of tradeoffs between speed and accuracy for multiple modeling approaches, as a function of different types and scales of networks, protocols, traffic and application types, and metrics. The network properties to be studied include performance (measured in latency, throughput, and related application or protocol-specific properties) of global network configurations, as well as the stability properties of the network, including fault localization and recovery.

Approach:

This research will leverage recent advances in parallel simulation, fluid flow network models, and model reduction techniques to devise a unified framework for efficient analysis of large-scale networks. The
goal is to use a combination of analytical models and detailed packet level parallel simulation when necessary, together with abstract models based on the emerging paradigm of fluid flow models where feasible, to obtain efficiency with known bounds on the inaccuracy introduced in the system. The proposed methodology is based on using an iterative approach where an initial analytical model is developed, with components refined iteratively to detailed representations as needed. The framework will allow subsystems to be modeled at different granularities, as well as allow subsystems to be modeled using different modeling paradigms. Important components of the proposed work include the following:

1) A multi-resolution, multi-paradigm capability for network analysis: This will be done using a combination of novel techniques including parallel simulation models using fluid flow abstractions and
other aggregation techniques, analytical models of large networks in conjunction with detailed simulation models of subnetworks, emulations, emulations running real applications on simulated networks, and novel algorithms that use event timestamps and deadline-based scheduling together with parallel simulation for real-time simulations. The objective is to permit performance prediction of networks with millions of nodes with bounded inaccuracy, while providing the capability for online analysis of smaller networks.

2) Theory of network control and stability: A number of adaptive protocols have been designed to manage QoS requirements of multiple application classes in heterogeneous networks. The protocols at different layers interact in a decentralized manner while trying to optimize local objectives (throughput, delay, fairness . . .) creating a concatenation of nested closed-loop controls. An understanding of regions of stability and safe operation of the protocols in various scenarios will be developed, as well as a methodology for prevention or recovery from instability and other pathologies. This research will also explore the impact of structural properties such as graph connectivity in failure analysis of such networks, as well as the use of transient system analysis for traffic models that display self-similarity and long-range dependence characteristics.

3) Model validation: The design of detailed and abstract models in a common framework will provide a direct opportunity for validation of abstract models. Further, detailed measurements will be used for
qualitative validation of trends as well as development of error bounds.

4) Real-time simulations: Simulation is traditionally used to compare the outcome of different strategies in an offline manner. However, if the time scale of the control implementation is of the same
order as that of the simulator, it is possible to run simulations in real time within the loop, so that control parameters are dynamically steered by simulator results. Analytic performance and optimization models can be continuously run in the background to verify consistency and modify the allocation strategy when necessary. A number of novel techniques for real-time performance prediction will be explored and will include a combination of analytical, simulation and hybrid models. An important component will be the design of novel scheduling algorithms that use event timestamps and deadline-based scheduling algorithms together with parallel simulation algorithms. Characterization of accuracy measures for on-line versus off-line operation will be an important objective.

5) Heavy-tailed distributions: Recent statistical analysis on empirical data has shown strong indication of the self-similar nature of network traffic. Measurement data from web transfers showed
that web traffic distribution has an upper tail which declines like a power law with exponent close to 1, i.e., a heavy tail. Heavy-tailed distributions are common in many complex bio-/eco-/techno-/socio-logical systems (CBETS). This ubiquity of power laws has motivated some researchers to suggest that they have a common origin in self-organized criticality (SOC). Recently, a radically different theory for the nature of complexity and the origin of power laws and phase transitions in complex systems called Highly Optimized Tolerance (HOT) has been proposed. The first application of the HOT theory to this proposal is an explanation for origin of power laws in web file transfers. The eventual goal is to produce a more unified treatment of information, control, and computation, having found that the standard theories are too fragmented and brittle to provide a foundation for more systematic design of network protocols. A central goal of this research program is to use the problem of mixed wired and wireless communication as a testbed for the development of new theory and tools, both for the analysis of existing protocols and the design of new ones.