Due to the popularity of mobile computing devices, 802.11-based wireless networks have become common place. A critical but unspecified component of 802.11 is transmission rate adaptation. Rate adaptation is difficult to do because it requires accurately estimating channel conditions while experiencing distinctly different wireless phenomena such as multi-path fast fading, nodal mobility, environmental mobility and hidden terminal interference. Rate adaptation algorithms use various methods to estimate channel conditions but these methods can be inaccurate in complex wireless environments causing incorrect adaptations. In this paper, we investigate the impact of inaccurate channel estimation methods by studying two rate adaptation algorithms, CHARM and SampleRate. We emulate high fidelity versions of both algorithms, using QualNet and evaluate their performance under environmental mobility and hidden terminal interference conditions. We found that the performance of both algorithms degrade dramatically due to inaccurate estimations caused by stale channel information. We propose two optimization techniques, REGS SINR and IntRec, to counteract these inaccuracies and implement them for CHARM and SampleRate. The proposed optimization techniques increase the performance dramatically for CHARM, up to 340% for environmental mobility and more than 290% for hidden terminal interference. We saw similar improvements of 220% and 88% for SampleRate.

Simulating the behavior of sensor applications in a heterogeneous network or under diverse environmental conditions is particularly challenging. In this paper, we present the design and implementation of TiQdagger, a scalable framework that allows unmodified TinyOS applications to be evaluated in a diverse set of operating conditions, including heterogeneous networks. We validate TiQ against MoteLab, a physical sensor network testbed, and show that TiQ can predict the behavior of the real network with less than 4% error. Through several case studies, we demonstrate the key benefits of TiQ: (1) it supports a diverse set of scenarios involving heterogeneous networks, mobile data mules, and multiple operating systems, (2) it scales to over a thousand nodes and can simulate such large networks up to 6X faster than comparable simulators, (3) it provides a system to easily validate TinyOS applications, evaluate network designs, and optimize design parameters (e.g., beacon rate) based on individual criteria, and (4) it leverages existing physical layer models in network simulators to provide more accurate simulations.

This paper presents the design and implementation of TMACS – a distributed middleware framework for Mobile Ad-hoc Network (MANETs). TMACS leverages type-based group communication paradigm in which type is used as a first-class abstraction for iden-tifying groups and provides a novel group-based RPC

The broadcast nature of existing wireless LANs can produce excessive radio coverage which is often undesirable for applications like wireless IPTV or location-based service. To address this issue, we utilize the characteristics of signal attenuation common to all wireless communications and implement apoint-castingservice1(PCast) over existing wireless networks that can significantly restrict the coverage for transmissions. The principle of PCast is to split and encode the downlink traffic and deliver it to the client via a few surrounding access points (APs). Hence, an unintended client cannot decode a packet without all its fragments. Equivalently, the service area is bounded within the intersection of communication coverage of all APs. The result coverage area can be further reduced via rate and power control at the APs. In this paper, we present our design and implementation of the PCast service on top of an 802.11a wireless LAN. Experiments conducted in a lab environment show that PCast can bound the service region to be within 2 meters around a client, while incurring jitter of less than 1ms, and bandwidth capacity loss of less than 10%.

Environmental mobility refers to the ambient motion of people, vehicles and other objects in the vicinity of wireless communication. Whereas the effect of mobility of transmitting and receiving radios has been widely researched, the impact of environmental mobility has been relatively unexplored in wireless networks. In this paper, we present a systematic study to analyze the effect of environmental mobility on wireless link behavior and protocol performance using measurement, analysis, and simulations. Measurement data from channel traces was collected to isolate and quantify the effects of environmental mobility on the channel performance. Efficient models were developed to explain the observed behavior and integrated with network simulation to enable protocol level analysis under such dynamics. We found that the class of protocols that maintain state or have memory but are otherwise agnostic of the channel operations fare poorly by acquiring incorrect information about the channel and are not able to adequately exploit durations where channel conditions are good. Two case studies at different layers of protocol stack are used to quantify such behavior to show that protocol perform maybe as much as 20-50% below their expected performance. To remedy this situation we present a cross layer optimization scheme, called Recovery from Earlier Good State (REGS), that allows protocols to become aware of the underlying channel operations. We show that use of REGS together with existing optimizations can improve throughputs in the presence of EM by more than 100%.

Although there is growing interest in the use of physical testbeds to evaluate the performance of applications and protocols for sensor platforms, such studies also encounter significant challenges that include the lack of scalability and repeatability, as well as the inability to represent a diverse set of operational scenarios. On the other hand, simulators can typically address the preceding problems but of-ten lack the high degree of fidelity available to the analysts with physical testbeds. In this paper, we present the design and implementation of SenQ - an accurate and scalable evaluation framework for sensor networks that effectively addresses the preceding challenges. In particular, SenQ integrates sensor network operating systems with a very high-fidelity simulation of wireless networks such that sensor network applications and protocols can be executed, without modifications, in a repeatable manner under a diverse set of scalable environments. SenQ extends beyond the existing suite of simulators and emulators in four key aspects: first, it supports emulation of sensor network applications and protocols in an efficient and exible manner; second, it provides an efficient set of models of diverse sensing phenomena; third, it provides accurate models of both battery power and clock drift effect which have been shown to have a significant impact on sensor network studies; and finally it provides an efficient kernel that allows it to run experiments that provide substantial scalability in both the spatial and temporal contexts.

In this paper, we present a high fidelity and efficient emulation framework called TWINE, which combines the accuracy and realism of emulated and physical networks and the scalability and repeatability of simulation in an integrated testbed, for evaluation of real protocols and applications. Our measurements show that the TWINE emulation kernel has a memory footprint of less than 100KB, and occupies no more than 3.5 % CPU cycles. Thanks to such small overhead and the accurate modelling of physical layer events(at microseconds level), application throughput measured in TWINE is within 5 % of the measured throughput from an equivalent physical wireless LAN. A single commodity PC in TWINE can emulate at least four wireless hosts or simulate sixty nodes in real time at microseconds granularity. This paper also illustrates TWINE’s novel capabilities via two case studies: a protocol to maintain fairness in mesh networks and an adaptive streaming media application operating in heterogeneous wireless networks. The results from the case studies clearly show the benefit of the TWINE evaluation methodology, by identifying a mismatch between the performance of the protocol or application based on actual user experience versus its performance as measured using traditional network performance metrics such as application throughput. 1.

Type-based communication is proposed as an effective paradigm to enable group communication in wireless ad-hoc networks (MANETs). In this paradigm, type is used as the fundamental construct for addressing and routing messages. Type hierarchies are used to dynamically control group size; and object-oriented principles such as subtyping and multiple inheritance are utilized to construct new groups from existing ones. We present the design of TypeCast, a routing protocol that directly supports type-based communication. TypeCast leverages efficiency and mobility management provided by MANET multicast protocols and extends them by adding a Bloom filter-based type encoding and routing mechanism. TypeCast is fully decentralized and supports subtyping and type-composition. We implement TypeCast on top of ODMRP and conduct a detailed performance and scalability study of TypeCast through simulation. The results show that TypeCast demonstrates good resiliency to mobility and group size. When the number of types in the network increases, TypeCast achieves good scalability thanks to type aggregation provided by Bloom filters

In this paper we address the effects of environmental mobility, that is, the ambient motion of entities like people and vehicles in the vicinity of wireless communication, on the channel characteristics and wireless network performance. We present a three step process of measurements, modeling and network simulations to quantify the significance of environmental mobility. Our field experiments show that presence of people not only cause deep fades but also distorts the fading distribution. We model the shadowing loss by three knife-edge diffraction model and propose a two-state Markov process channel fading behavior. The models are validated against measurement data and implemented in a network simulator. The models are scalable and incur execution overhead less than 15%. We also show the impact of environment mobility on protocol performance by means of two simulation case studies. We show that MAC layer data rate adaptation behavior is sensitive to environmental mobility and can result in 40% packets being delivered at lower rates. Second study on ad-hoc network performance show the throughput is decreased by 20%. We have identified that with environmental mobility the links are more sensitive to interference and the routes are less stable

We consider the impact of system-related overheads on the performance of two reliable transport protocols (TCP and XCP) over wireless links. Our measurement results indicate that various components providing networking support at a wireless host collectively have significant impact on transport layer performance. Furthermore, the relative performance of protocols is dependent on the host's network subsystem configuration. These results highlight the importance of considering system-dependent behaviors in wireless network protocol evaluations

We examine the impact of physical layer rate adaptation mechanisms on the performance of real applications over 802.11 wireless links in diverse channel environments. Our evaluations are based on a testbed with real wireless devices equipped with commodity 802.11 hardware and a hardware channel emulator. We consider two different and well-known 802.11 rate adaptation mechanisms (Onoe and SampleRate) and study their performance under several realistic workloads, including multimedia streaming and Web browsing. We observe that the application performance with different rate adaptation mechanisms is dependent on the specific tradeoffs these mechanisms make at the link layer in an application-oblivious manner between improving throughput and limiting frame loss. More importantly, their relative performance for a given workload is quite sensitive to the channel quality and environment. These observations highlight the importance of choosing the rate selection strategy adaptively in an application and channel aware manner

No abstract available.

Recent years have seen the growing popularity of multi-rate wireless network devices (e.g., 802.11a cards) that can exploit variations in channel conditions and improve overall network throughput. Concurrently, rate adaptation schemes have been developed that selectively increase data transmissions on a link when it offers good channel quality. In this paper, we propose a Medium Access Diversity (MAD) scheme that leverages the benefits of rate adaptation schemes by aggressively exploiting multiuser diversity. The basic mechanism of MAD is to obtain instantaneous channel condition information from multiple receivers and selectively transmit data to a receiver that improves the overall throughput of the network, while maintaining temporal fairness among multiple data flows. We identify and address the challenges in the design and implementation of MAD's three phases: channel probing, data transmission, and receiver scheduling. We also use analytical models to examine the tradeoff between network performance improvement and overhead of channel probing, and derive an asymptotic performance bound for the receiver scheduling algorithms used by MAD. Results from the analysis and the extensive simulations demonstrate that, on average, MAD can improve the overall throughput of IEEE 802.11 wireless LANs by 50% as compared with the best existing rate adaptation scheme.

In mobile Internet applications, data can be transcoded, updated, and transferred across heterogenous clients. The problem then arises where updates made in the context of an initial transcoding results in content too stringently transcoded for subsequent clients, thereby causing loss of semantic value. We solve this problem by suggesting that the updates themselves can be transformed so that they can be applied directly to the original data instead of to the transcoded data; this approach allows the data to preserve as much semantic value as possible across all heterogeneous clients without unnecessary transcoding artifacts. We define reconciliation rules that can govern the interaction between client updates and transcoding, demonstrate a complete middleware architecture that supports our methodology, and provide two case studies using content-transferring applications. We show that our resulting middleware system executes our reconciliation approach with acceptable latency (under 5 seconds for 200 kbytes of layered content), good scalability, and well-organised modularity.

Discrete event network simulators have emerged as popular tools for verification and performance evaluation for various wireless networks. Nevertheless, the desire to model such networks at high fidelity implies high computational costs, prohibiting most researchers from simulating wireless networks with thousands of nodes. There have been attempts on performance optimizations for large-scale wireless network simulation, but they have not appropriately modeled accumulation of weak interference, thereby suffering inaccuracies which may be magnified by upper layer protocols. This paper presents analysis of the effects of common optimization techniques for large-scale wireless network simulation on the overall network performance and also proposes modifications and novel techniques that introduce only limited inaccuracies or no additional inaccuracy at all. The study quantifies the effects of those optimizations on the simulation results for given thresholds and network parameters, and also identifies thresholds tolerable to most network studies. The experimental results show that these optimizations can improve the runtime performance of an already efficient wireless network simulator substantially, by a factor of up to 55 for wireless networks with 3200 nodes without compromising accuracy of the simulation results.

Recent trends in sensor network simulation can be divided between less flexible but accurate emulation based approach and more generic but less detailed network simulator models. We offer an approach with the flexibility of network simulators and provides the accuracy comparable to emulation based approaches. We describe the design and architecture of sensor network simulator which provides a rich suite of following models: sensing stack to model wave and diffusion based sensor channels, an accurate battery model, processor power consumption model, energy consumption model and sensor network based traffic model. We also present our study on the effects of detailed modeling on the performance of higher layer protocols. We describe the impact of using accurate models for battery, processor power consumption and traffic models on the network layer statistics as network lifetime and availability, throughput and routing overhead. Our results show there is high sensitivity of model accuracy on network and application level statistics. In extreme cases we have noticed an inversion of results with our accurate models as compared with previous generation of abstract models.

Mobile computing research has often focused on untethering an in-use computing device, rather than enabling the mobility of the computation task itself. This paper presents an architecture, implementation, and experimental evidence that together validate a new continuous computing concept, application session handoff. The iMASH architecture leverages previous work on proxies, content adaptation, and client awareness to provide a unique, middleware-enable capability for continuous computing. Implementation in both socket- and RPC-based environments shows that very fast, secure session handoff of non-trivial client/server applications across heterogeneous client devices and network is feasible: experiments on a number of applications yielded handoff latencies ranging from 0.5s to 2s.

This paper presents ARC (Adaptive Range Control), a communication range control mechanism using directional antennas to be implemented across multiple layers. ARC uses directional reception for range control rather than directional transmission such that extended communication links do not increase interference to other ongoing communications. It adaptively controls the communication range by estimating dynamically changing local network density based on the transmission activities around each network node. The experimental results using simulation with detailed physical layer, IEEE 802.11 DCF MAC, and AODV protocol models have shown the successful adaptation of communication range with ARC for varied network densities and traffic loads. ARC improves the packet delivery ratio by a factor of 9 at the maximum for sparse networks while it maintains the increased network capacity for dense networks.

Ubiquitous computing across a variety of wired and wireless connections still lacks an effective security architecture. In our research work, we address the specific issue of designing and building a security architecture for application session handoff, a functionality which we envision will be a key component enabling ubiquitous computing. Our architecture incorporates a number of proven approaches into the new context of ubiquitous computing. We employ the Bell-LaPadula (1976) and capability models to realise access control and adopt public key infrastructure (PKI)-based approaches to provide efficient and authenticated end-to-end security. To demonstrate the effectiveness of our design, we implemented an application enabled with this security architecture and showed that it incurred low latency.

The importance of middleware and content adaptation has previously been demonstrated for pervasive use of Web-based applications. In this paper we propose a modular extensible, and scalable middleware component called the Content Adaptation Pipeline that performs content adaptation on arbitrarily complex data types not limited to text and graphic images. Furthermore, the architecture can be used as part of many client-server applications, not just Web browsers. In our work we leverage the XML language as a uniform means to describe all the elements in our architecture, including the client device and user profiles, the data characteristics, the transcoding operations performed on the data, and the resultant adapted data. We illustrate the flexibility of our architecture to support new data types and adaptation operations by first showing its use with data from a real-world medical application and then extending its capabilities to handle animated graphics and also real-time streaming RTP data. Finally, we demonstrate scalability in our architecture by executing the Content Adaptation Pipeline over a distributed set of servers running an efficient protocol.

This paper presents a new carrier sensing mechanism called DVCS (Directional Virtual Carrier Sensing) for wireless communication using directional antennas. DVCS does not require specific antenna configurations or external devices. Instead it only needs information on AOA (Angle of Arrival) and antenna gain for each signal from the underlying physical device, both of which are commonly used for the adaptation of antenna pattern. DVCS also supports interoperability of directional and omni-directional antennas. In this study, the performance of DVCS for mobile ad hoc networks is evaluated using simulation with a realistic directional antenna model and the full IP protocol stack. The experimental results showed that compared with omni-directional communication, DVCS improved network capacity by a factor of 3 to 4 for a 100 node ad hoc network.

Personal computing on mobile platforms such as laptops and personal digital assistants, rather than in a traditional desktop environment, is becoming increasingly more common. We address the issue of application session transfer for uninterrupted data access across this diverse range of platforms. This work is part of the iMASH project, a multi-year, multi-discipline collaborative effort focused on enabling mobile client platforms and incorporating them into existing legacy networked systems for use by medical practitioners. We have developed a tiered architecture that includes a middleware server layer positioned between existing application servers and multiple clients to make session transfer transparent to the user. Any client application executing our middleware-aware remote code library can save and restore its session by interacting with a middleware server. As a proof of concept, we have implemented the transfer of bookmarks, history, Web cache, and user preferences with the Mozilla open source Web browser, from this effort we have established baseline performance metrics and have found that the overhead is within reasonable bounds of just a few seconds of latency.

In most studies on mobile ad hoc networks (MANET), simulation models are used for the evaluation of devices and protocols. Typically, such simulations focus on the specific higher layer protocols that are being proposed, and tend to ignore details of models at other layers, particularly the interactions with physical layer models. In this paper, we present the set of factors at the physical layer that are relevant to the performance evaluations of higher layer protocols. Such factors include signal reception, path loss, fading, interference and noise computation, and preamble length. We start the discussion with the comparisions of physical layer models in ns-2 and GloMoSim, two commonly used simulators for MANET studies, and then quantify the impact of the preceding factors under typical scenarios used for the performance evaluation of wireless ad hoc routing protocols. Our experimental results show that the factors at the physical layer not only affect the absolute performance of a protocol, but because their impact on different protocols is non-uniform, it can even change the relative ranking among protocols for the same scenari

In this paper we investigate the performance of multicast routing protocols in wireless mobile ad hoc networks. An ad hoc network is composed of mobile nodes without the presence of a wired support infrastructure. In this environment, routing/multicasting protocols are faced with the challenge of producing multihop routes under host mobility and bandwidth constraints. In recent years, a number of new multicast protocols of different styles have been proposed for ad hoc networks. However, systematic performance evaluations and comparative analysis of these protocols in a common realistic environment has not yet been performed. In this study, we simulate a set of representative wireless ad hoc multicast protocols and evaluate them in various network scenarios. The relative strengths, weaknesses, and applicability of each multicast protocol to diverse situations are studied and discussed.

Parallel discrete event simulation with conservative synchronization algorithms has been used as a high performance alternative to sequential simulation. In this paper, we examine the performance of a set of parallel conservative algorithms that have been implemented in the Maisie parallel simulation language. The algorithms include the asynchronous null message algorithm, the synchronous conditional event algorithm, and a new hybrid algorithm called Accelerated Null Message that combines features from the preceding algorithms. The performance of the algorithms is compared using the Ideal Simulation Protocol. This protocol provides a tight lower bound on the execution time of a simulation model on a given architecture and serves as a useful base to compare the synchronization overheads of the different algorithms. The performance of the algorithms is compared as a function of various model characteristics that include model connectivity, computation granularity, load balance, and lookahead.

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.

Parallel simulation of parallel programs for large datasets has been shown to offer significant reduction in the execution time of many discrete event models. The paper describes the design and implementation of MPI-SIM, a library for the execution driven parallel simulation of task and data parallel programs. MPI-SIM can be used to predict the performance of existing programs written using MPI for message passing, or written in UC, a data parallel language, compiled to use message passing. The simulation models can be executed sequentially or in parallel. Parallel execution of the models are synchronized using a set of asynchronous conservative protocols. The paper demonstrates how protocol performance is improved by the use of application-level, runtime analysis. The analysis targets the communication patterns of the application. We show the application-level analysis for message passing and data parallel languages. We present the validation and performance results for the simulator for a set of applications that include the NAS Parallel Benchmark suite. The application-level optimization described in the paper yielded significant performance improvements in the simulation of parallel programs, and in some cases completely eliminated the synchronizations in the parallel execution of the simulation model.

In this study we investigate the interaction between TCP and MAC layer in a wireless multi-hop network. This type of network has traditionally found applications in the military (automated battlefield), law enforcement (search and rescue) and disaster recovery (flood, earthquake), where there is no fixed wired infrastructure. Wireless "ad-hoc" multi-hop networks have previously been proposed for nomadic computing applications. Key requirements in all the above applications are reliable data transfer and congestion control, features that are generally supported by TCP. Unfortunately, TCP performs on wireless in a much less predictable way than on wired protocols. Using simulation, we provide new insight into two critical problems of TCP over wireless multi-hop. The first is the conflict between data packets and ACKs, which causes TCP performance to degrade for window sizes greater than 1 packet. The second is the interaction between MAC and TCP layer backoff timers which causes severe unfairness and capture conditions. In the paper, we identify these problems in several representative simulation runs on various topologies and traffic patterns and indicate possible remedies to improve TCP efficiency over a wireless multi-hop network.

Optimistic replication of data is becoming increasingly popular in mobile environments, but its performance and scaling characteristics are not well understood. This paper presents a simulation evaluation of optimistic replicated filing in a mobile environment. We first compare full and selective optimistic replication systems to capture the properties required for scaling. We then show that the presence of portable computers in optimistically replicated filing systems achieves a 60-percent cost reduction (e.g., computing resources) with only a 10-percent degradation of service quality (e.g., consistency of data perceived by users). This finding reveals certain similarities between the network disconnection interval and frequency of data synchronization. The research suggests new guidelines for design of optimistic replication systems.

Accurate simulation of large parallel applications can be facilitated with the use of direct execution and parallel discrete event simulation. This paper describes the use of COMPASS, a direct execution-driven, parallel simulator for performance prediction of programs that include both communication and I/O intensive applications. The simulator has been used to predict the performance of such applications on both distributed memory machines like the IBM SP and shared-memory machines like the SGI Origin 2000. The paper illustrates the usefulness of COMPASS as a versatile performance prediction tool. We use both real-world applications and synthetic benchmarks to study application scalability, sensitivity to communication latency, and the interplay between factors like communication pattern and parallel file system caching on application performance. We also show that the simulator is accurate in its predictions and that it is also efficient in its ability to use parallel simulation to reduce its own execution time which, in some cases, has yielded a nearlinear speedup.

In this paper, we propose and evaluate practical, automatic techniques that exploit compiler analysis to facilitate simulation of very large message-passing systems.We use a compilersynthesized static task graph model to identify the control-flow and the subset of the computations that determine the parallelism, communication and synchronization of the code, and to generate symbolic estimates of sequential task execution times.This information allows us to avoid executing or simulating large portions of the computational code during the simulation.We have used these techniques to integrate the MPI-Sim parallel simulator at UCLA with the Rice dHPF compiler infrastructure.The integrated system can simulate unmodified High Performance Fortran (HPF) programs compiled to the Message-Passing Interface standard (MPI) by the dHPF compiler, and we expect to simulate MPI programs as well.We evaluate the accuracy and benefits of these techniques for three standard benchmarks on a wide range of problem and system sizes.Our results show that the optimized simulator has errors of less than 17% compared with direct program measurement in all the cases we studied, and typically much smaller errors.Furthermore, it requires factors of 5 to 2000 less memory and up to a factor of 10 less time to execute than the original simulator.These dramatic savings allow us to simulate systems and problem sizes 10 to 100 times larger than is possible with the original simulator.

In this paper we address the evaluation of speech quality through a wireless network as perceived by the user. User perceived evaluation (in addition to the usual network metrics including delay, throughput, packet loss statistics, etc.) is critical in the design of wireless multimedia networks where speech and video play a key role and are affected by several factors, such as network performance and encoding scheme. We use two approaches for our evaluation: small scale testbed implementation and hybrid simulation. The testbeds are implemented either by UDP (user datagram protocol) connection or UCLA talk connection. The hybrid simulation is event driven and is based on the Maisie parallel simulation language. It uses speech traces for inputs and plays back the speech outputs off-line. There are several advantages in using the simulation tool, mainly from the point of view of scalability and new protocol feature testing. At the same time, the real life testbed provides verification of the simulator assumptions, albeit on a small scale.

Simulation of large sets of mobile computers or other wireless communication devices is difficult because of the computationally intensive models of wireless channels. Parallel simulation would seem to be applicable here because of the large computation granularity, but the location based communication topology makes conservative methods difficult to implement. This paper considers a novel approach to improving lookahead in conservative parallel simulations by differentiating between data flow paths in the simulation. An experimental study shows that for this application, the technique produces a 70% reduction in null message traffic, with only a 25% increase in null message computation overhead, and a consistent improvement in parallel performance.

Efficient I/O implementations can have a significant impact on the performance of parallel applications. This paper describes the design and implementation of PIOSIM, a parallel simulation library for MPI-IO programs. The simulator can be used to predict the performance of existing MPI-IO programs as a function of architectural characteristics, caching algorithms, and alternative implementations of collective I/O operations. This paper describes the simulator and presents the results of a number of performance studies to evaluate the impact of the preceding factors on a set of MPI-IO benchmarks, including programs from the NAS benchmark suite.

In this paper; we describe an advanced simulation environment which is used to examine, validate, andpredict the performance of mobile wireless network systems.This simulation environment overcomes many of the limitations found with analytical models, experimentation, and other commercial network simulators available on the market today We identify a set of components which make up mobile wireless systems and describe a set offlexible modules which can be used to model the various components and their integration.These models are developed using the Maisie simulation language.By modeling the various components and their integration, this simulation environment is able to accurately predict the performance bottlenecks of a multimedia wireless network system being developed at UCLA, determine the trade-offpoint between the various bottlenecks, andprovide performance measurements and validation of algorithms which are not possible through experimentation and too complexfor analysis.

We explore the use of UNITY logic in specifying and verifying fairness properties of UNITY and UNITY-like programs whose semantics can be modeled by weakly fair transition systems. For such programs, strong fairness properties in the form of “if p holds infinitely often then q also holds infinitely often □◊p⇒□◊q, can be expressed as conditional UNITY properties of the form of “Hypothesis: true→p Conclusion:true→q”. We show that UNITY logic is relatively complete for proving such properties; in the process, a simple inference rule is derived. Specification and verification of weak fairness properties are also discussed.

Acyclic partitioning on combinational boolean networks has wide range of applications, from multiple FPGA chip partitioning to parallel circuit simulation.In this paper, we present two efficient algorithms for the acyclic multi-way partitioning.One is a generalized FMbased algorithm.The other is based on the theory of maximum fanout-free cone (MFFC) decomposition.The acyclic FM-algorithm usually results in larger cut-size, as expected, compared to the undirected FM-algorithm due to the acyclic constraint.To our surprise, however, the MFFC-based acyclic partitioning algorithm consistently produces smaller (50% on average) cut-sized solutions than the conventional FM-algorithm.This result suggests that considering signal directions during the process can lead to very natural circuit decomposition and clustering, which in turn results in better partitioning solutions.We have also implemented parallel gate level simulators in Maisie and applied our partitioning algorithms to evaluate their impact on circuit simulation.

The implementation of nondeterministic pairwise synchronous communication among a set of asynchronous processes is modeled as the binary interaction problem. The paper describes an algorithm for this problem that satisfies a strong fairness property that guarantees freedom from process starvation. This is the first algorithm for binary interactions with strong fairness whose message cost and response time are independent of the total number of processes in the system. The paper also describes how the fair algorithm may be extended to tolerate detectable fail-stop failures. Finally, we show how any solution to the dining philosophers problem can be embedded to design a fair algorithm for binary interactions. In particular, this embedding is used to derive a fair algorithm that can cope with undetectable fail-stop failures.>

Maisie is a C-based discrete-event simulation language that was designed to cleanly separate a simulation model from the underlying algorithm (sequential or parallel) used for the execution of the model. With few modifications, a Maisie program may be executed by using a sequential simulation algorithm, a parallel conservative algorithm or a parallel optimistic algorithm. The language constructs allow the run-time system to implement optimizations that reduce recomputation and state saving overheads for optimistic simulations and synchronization overheads for conservative implementations. This paper presents the Maisie simulation language, describes a set of optimizations, and illustrates the use of the language in the design of efficient parallel simulations.>

A methodology for the derivation of parallel implementations from program specifications is developed. The goal of the methodology is to decompose a program specification into a collection of module specifications via property refinement, such that each module may be implemented independently by a subprogram. The correctness of the implementation is then deduced from the correctness of the property refinement procedure and the correctness of the individual subprograms. The refinement strategy is based on identifying frequently occurring control structures such as sequential composition and iteration. The methodology is developed in the context of the UNITY logic and the UC programming language, and illustrated through the solution of diffusion aggregation in fluid flow simulations.>

The comprehensive article by Fujimoto clearly outlines the path that parallel simulation must follow in the future. To paraphrase a winning slogan from the recent presidential elections—“The tools, stupid.” This paper elaborates on Fujimoto's insightful observations on what is required to make parallel simulation more accessible to the discrete event simulation community and presents experiences derived from the author's research to reinforce the conclusions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The implementation of nondeterministic pairwise synchronous communication among a set of asynchronous processes is modeled as a binary interaction problem. An algorithm for this problem, which satisfies a strong fairness property that guarantees freedom from process starvation, is described. The message and time complexities are independent of the total number of processes in the system. The ways in which the algorithm may be extended to cope with fail-stop process failures are discussed.>

The efficiency of a parallel program is related to the implementation of its data structures on the distributed (or shared) memory of a specific architecture.This paper describes a declarative approach that may be used to modify the mapping of the program data on a specific architecture.The ideas are developed in the context of a new language called UC and its implementation on the Connection Machine.The paper aim contains measurements on sample programs to illustrate the effectiveness of data mappings in improving the execution efficiency of example programs.

The goal of this research is to develop a design methodology that allows performance characteristics of a system to be monitored through all stages of its development, from initial design to system deployment. The use of partially implemented performance specifications (PIPS) as the design paradigm for real-time systems is proposed. A PIPS model is a partially implemented system where some system components exist as simulation models and others as operational subsystems. The model may be executed in an appropriate operating environment to determine stochastic performance of a proposed design. Proof axioms have also been defined for the modeling primitives to allow absolute timing constraints to be verified for the model.>

An approach called MIDAS is described that supports the design of distributed systems via iterative refinement of hybrid models. A hybrid model is a partially implemented design where some components exist as simulation models and others as operational subsystems. It is an executable model and may be used to determine the stochastic performance characteristics of a partially elaborated design. MIDAS enhances the applicability of hybrid models in system design with its support for interrupts and its inclusion of distributed components in the partially implemented design. The authors describe how an existing simulation language may be extended to program hybrid models, and show how simulation algorithms may be adapted to execute hybrid models. A prototype MIDAS implementation is operational and was used to develop a set of applications. The experimental results of the exercise are also described.>

In designing parallel languages, the concern for defining a simple virtual machine must be balanced against the need to efficiently map a program on a specific architecture. UC addresses this problem by separating the programming task from efficiency considerations. UC programs are designed using a small set of constructs that include reduction, parallel assignment, and fixed-point computation. The language also provides a map section that may optionally be used by a programmer to specify data mappings for the program. The authors describe the UC constructs and their implementation on the Connection Machine. They also present measurements of the compiler for simple benchmarks.>

Many concurrent programming languages including CSP and Ada use synchronous message-passing to define communication between a pair of asynchronous processes. Suggested primitives like the generalized alternative command for CSP and the symmetric select statement for Ada allow a process to nondeterministically select one of several communication statements for execution. The communication statement may be either an input or an output statement. We propose a simple algorithm to implement the generalized alternative command and show that it uses fewer messages than existing algorithms.

The author presents a simple solution for the committee coordination problem, which encompasses the synchronization and exclusion problems associated with implementing multiway rendezvous, and shows how it can be implemented to develop a family of algorithms. The algorithms use message counts to solve the synchronization problem, and they solve the exclusion problem by using a circulating token or by using auxiliary resources as in the solutions for the dining or drinking philosophers' problems. Results of a simulation study of the performance of the algorithms are presented. The experiments measured the response time and message complexity of each algorithm as a function of variations in the model parameters, including network topology and level of conflict in the system. The results show that the response time for algorithms proposed is significantly better than for existing algorithms, whereas the message complexity is considerably worse.>

This paper develops a message-based approach to discrete-event simulation. Although message-based simulators have the same expressive power as traditional discrete-event simulation lanuages, they provide a more natural environment for simulating distributed systems. In message-based simulations, a physical system is modeled by a set of message-communicating processes. The events in the system are modeled by message-communications. The paper proposes the entity construct to represent a message-communicating process operating in simulated time. A general wait until construct is used for process scheduling and message-communication. Based on these two notions, the paper proposes a language fragment comprising a small set of primitives. The language fragment can be implemented in any general-purpose, sequential programming language to construct a message-based simulator. We give an example of a message-based simulation language, called MAY, developed by implementing the language fragment in Fortran. MAY is in the public domain and is available on request.