WSC 2001 Final Abstracts

An Empirical Validation of a Duality Model of TCP and Queue Management Algorithms
Sanjeewa Athuraliya and Steven H. Low (Caltech)

Abstract:
In this paper we validate through simulations a duality model of TCP and active queue management (AQM) proposed earlier. In this model, TCP and AQM are modeled as carrying out a distributed primal-dual algorithm over the Internet to maximize aggregate source utility. TCP congestion avoidance algorithms, such as Reno and Vegas, iterate on source rates, the primal variable. AQM algorithms, such as RED and REM, iterate on marking probability, the dual variable.

Deterministic Fluid Models of Congestion Control in High-Speed Networks
Sanjay Shakkottai and R. Srikant (University of Illinois at Urbana Champaign)

Abstract:
Congestion control algorithms, such as TCP or the closely-related additive increase-multiplicative decrease algorithms, are extremely difficult to simulate on a large scale. The reasons for this include the complexity of the actual implementation of the algorithm and the randomness introduced in the packet arrival and service processes due to many factors such as arrivals and departures of sources and uncontrollable short flows in the network. To make the simulation tractable, often deterministic fluid approximations of these algorithms are used. These fluid approximations are in the form of deterministic delay differential equations. In this paper, we ignore the complexity introduced by the window-based implementation of such algorithms and focus on the randomness in the network. We justify the use of deterministic models for proportionally-fair congestion controllers under a limiting regime where the number of sources in a network is large.

Fluid Model for Window-Based Congestion Control Mechanism
Richard J. La (Motorola Inc.)

Abstract:
We study the stability of two queueing delay-based congestion control algorithms, the (p,1)-proportionally fair algorithm and the global optimization algorithm. We linearize the systems around the intended operating point and show that these algorithms are stable within a range of feedback delay. Based on these linearized systems we study the impact of various (cascade) compensators on the system. We show that the PID control improves the transient behavior of the system. We simulate both the linearized system and non-linear system and illustrate the validity of the analysis and improvement in the system behavior with compensators.

Discrete Event Fluid Modeling of TCP
David M. Nicol (Dartmouth College)

Abstract:
The bulk of Internet traffic is carried using variants of the TCP protocol. A realistic simulation-based performance study of any distributed application run over the Internet (e.g. reliable multicast) must therefore account for the impact that TCP background traffic has upon application behavior. Because TCP flows are shaped by other TCP flows, it is difficult to model TCP and its impact on other traffic other than by explicitly simulating it. This adds a significant computational burden to the simulation. This paper describes how we use fluid-based models of TCP to reduce the computational workload of simulating background TCP traffic. In particular we describe how a number of significant aspects of TCP can be described within a fluid formulation, how fluid models give rise to specific challenges that must be addressed by modeler and simulation kernel, and how we have addressed these in the DaSSF simulator.

On the Impact of Concurrent Downloads
Yong Liu, Weibo Gong, and Prashant Shenoy (University of Massachusetts, Amherst)

Abstract:
Concurrent downloads accelerate information access speed for individual web users. The speed-up comes from multiple connections launched for one subject download, which leads to unfairness at user level. In this paper, we study the impact of concurrent downloads on the network. Particularly, we investigate the fairness between users who employ different downloading concurrency. We also discuss how concurrent downloads affect the transient behavior of the network.

On Improving the Performance of Simulation-Based Algorithms for Average Reward Processes with Application to Network Pricing
Enrique Campos-Náñez and Stephen D. Patek (University of Virginia)

Abstract:
We address performance issues associated with simulation-based algorithms for optimizing Markov reward processes. Specifically, we are concerned with algorithms that exploit the regenerative structure of the process in estimating the gradient of the objective function with the respect to control parameters. In many applications, states which initially have short expected return-times may eventually become infrequently visited as the control parameters are updated. As a result, unbiased updates to the control parameters can become so infrequent as to render the algorithm impractical. The performance of these algorithms can be significantly improved by adapting the state which is used to mark regenerative cycles. In this paper, we introduce such an adaptation procedure, give initial arguments for its convergence properties, and illustrate its application in two numerical examples. The examples relate to the optimal pricing of communication network resources for congestion-controlled traffic.

Towards High Performance Modeling of the 802.11 Wireless Protocol
Jason Liu, David M. Nicol, L. Felipe Perrone, and Michael Liljenstam (ISTS Dartmouth College)

Abstract:
The IEEE 802.11 standard is a widely used protocol for wireless communications. It is a moderately complex algorithm involving collision detection, dynamic backoffs, channel reservations, and acknowledgments. Detailed simulation of 802.11 requires some care, and considerable execution time. We are interested in developing a rapidly executable model of 802.11's effect on network behavior. Our interest in this derives from investigations into routing algorithms for large scale ad-hoc networks, executing on parallel architectures. As our interest is in routing and not the MAC layer, a rapidly executed model of 802.11 will accelerate simulations focused on routing issues while giving us ``good enough'' estimates of packet latency, throughput, and loss.

Use of DaSSF in a Scalable Multiprocessor Wireless Simulation Architecture
Trefor J. Delve and Nathan J. Smith (Motorola Labs)

Abstract:
The problem of efficient load distribution and scaling of large-scale wireless communication system simulation on multiprocessor architectures (both shared memory and cluster arrangements) is considered. A flexible architecture based upon DaSSF, the Dartmouth Scalable Simulation Framework discrete event engine, is presented and evaluated. The architecture is designed to deal with the computationally intensive aspects of radio communication simulation in a distributed environment. Results are presented that show how the architecture scales on a shared memory multiprocessor SGI Origin with increasing problem size and available processors.

Simulating Networks of Wireless Sensors
Sung Park, Andreas Savvides, and Mani B. Srivastava (University of California Los Angeles)

Abstract:
Recent advances in low-power embedded processors, radios, and micro-mechanical systems (MEMs) have made possible the development of networks of wirelessly interconnected sensors. With their focus on applications requiring tight coupling with the physical world, as opposed to the personal communication focus of conventional wireless networks, these wireless sensor networks pose significantly different design, implementation, and deployment challenges. In this paper, we present a set of models and techniques that are embodied in a simulation tool for modeling wireless sensor networks. Our work builds up on the infrastructure provided by the widely used ns-2 simulator, and adds a suite of new features and techniques that are specific to wireless sensor networks. These features introduce the notion of a sensing channel through which sensors detect targets, and provide detailed models for evaluating energy consumption and battery lifetime.

Benefits From Semi-Asynchronous Checkpointing for Time Warp Simulations of a Large State PCS Model
Andrea Santoro and Francesco Quaglia (Dipartimento di Informatica e Sistemistica)

Abstract:
Checkpointing overhead is a major obstacle for the effectiveness of Time Warp parallel discrete event simulators. Semi-asynchronous checkpointing is a recent solution to tackle this obstacle for Time Warp simulations on distributed memory systems based on Myrinet. In this solution, checkpoint operations are offloaded from the host CPU and are charged to a DMA engine on board of Myrinet network cards. In this paper we report an empirical evaluation of the benefits from semi-asynchronous checkpointing for Time Warp simulations of a large state Personal Communication System (PCS) model. PCS simulation models are typically characterized by high communication locality among the LPs hosted by the same machine, therefore the hardware on board of the Myrinet cards is typically underutilized if used to support exclusively communication. We show that the execution speed of Time Warp simulations of a large state PCS model can be increased when semi-asynchronous checkpointing is adopted.

Satellite Communications Representation in Network Simulation
Kenneth Y. Jo (Defense Information Systems Agency)

Abstract:
This paper presents methodologies to represent satellite communications (SATCOM) behaviors in network simulation. This paper is based on tasks being performed for generic network warefare simulation that employs traditional network simulation models. The methodologies also include the integration issues of SATCOM tools and the network simulation models. We first characterize space segments and assets involved in warfare operations and exercises, and then analyze system behaviors to measure space-link performance design results. The techniques adopted in effect will augment traditional network models with SATCOM capabilities through specialized satellite analysis models. The SATCOM tools produce detailed satellite orbit characteristics and radio frequency (RF) performance analyses for puvlic and commercial satellites with multiple microwave bands. Automated interface mechanisms between the SATCOM and network simulation models are being developed to provide more interactive model collaboration.

Experiences Parallelizing a Commercial Network Simulator
Hao Wu, Richard M. Fujimoto, and George Riley (Georgia Institute of Technology)

Abstract:
Most current approaches to parallel simulation focus on building new parallel simulation engines that require the development of new models and software. An alternate, emerging approach is to extend sequential simulators to execute on parallel computers. We describe a methodology for realizing parallel simulations in this manner. This work is specifically concerned with parallelization of commercial simulators where source code for some or all of the sequential simulator is not available. We describe our experiences in applying this methodology to realize a parallel version of the OPNET simulator for modeling computer networks. We show significant speedup can be readily obtained for some OPNET models if proper partitioning strategies are applied and the simulation attributes are tuned appropriately. However, we observe that substantial modifications to other OPNET models are needed to achieve efficient parallel execution because of their extensive use of global variables and zero lookahead events.