Browsing by Author "Abrams, Marc"
Now showing 1 - 20 of 74
Results Per Page
Sort Options
- Adapting Protocols to Massively Interconnected SystemsKafura, Dennis G.; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1991-05-01)This paper describes ongoing research focused on two critical problems posed by the interconnection of a massive number of computer systems. The interconnection may be achieved through wide area or local area networks. The two problems considered in this research are as follows: (1) performance analysis of the protocols used in an internetwork connecting thousands to millions of nodes, and (2) application development in a massively distributed, heterogeneous environment where components implemented in different programming languages must be integrated and/or reused. The performance analysis problem is addressed by employing large-scale parallel simulation, extended finite state machines and objected-oriented simulation techniques. The approach to solving the application development problem is based on an environment which exploits the synergism between object-oriented programming and layered communication protocols (specifically, OSI).
- Analysis and Modeling of World Wide Web TrafficAbdulla, Ghaleb (Virginia Tech, 1998-04-27)This dissertation deals with monitoring, collecting, analyzing, and modeling of World Wide Web (WWW) traffic and client interactions. The rapid growth of WWW usage has not been accompanied by an overall understanding of models of information resources and their deployment strategies. Consequently, the current Web architecture often faces performance and reliability problems. Scalability, latency, bandwidth, and disconnected operations are some of the important issues that should be considered when attempting to adjust for the growth in Web usage. The WWW Consortium launched an effort to design a new protocol that will be able to support future demands. Before doing that, however, we need to characterize current users' interactions with the WWW and understand how it is being used. We focus on proxies since they provide a good medium or caching, filtering information, payment methods, and copyright management. We collected proxy data from our environment over a period of more than two years. We also collected data from other sources such as schools, information service providers, and commercial aites. Sampling times range from days to years. We analyzed the collected data looking for important characteristics that can help in designing a better HTTP protocol. We developed a modeling approach that considers Web traffic characteristics such as self-similarity and long-range dependency. We developed an algorithm to characterize users' sessions. Finally we developed a high-level Web traffic model suitable for sensitivity analysis. As a result of this work we develop statistical models of parameters such as arrival times, file sizes, file types, and locality of reference. We describe an approach to model long-range and dependent Web traffic and we characterize activities of users accessing a digital library courseware server or Web search tools. Temporal and spatial locality of reference within examined user communities is high, so caching can be an effective tool to help reduce network traffic and to help solve the scalability problem. We recommend utilizing our findings to promote a smart distribution or push model to cache documents when there is likelihood of repeat accesses.
- Analysis of Bottlenecks in International Internet LinksAhsan Habib, Md; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1998-12-01)We report on preliminary results of analysis into the sources of congestion in international Internet routes from the United States to several countries: Brazil and South Africa. Using the pathchar and traceroute tools, we identified which links in a variety of routes are a bottleneck. The measures used were throughput, round trip delay, and router queueing delays. Measurements with ping were used to validate the round trip times obtained with pathchar.
- Approximate Time-Parallel Simulation of Queueing Systems with LossesWang, Jain J.; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)This paper presents a guideline of a partial state matching approach for time-parallel simulation. Two algorithms using this approach to simulate FCFS G/G/1/K and G/D/1/K queues in which arriving customers that find the queue full are lost are proposed. Experiments with M/M/1/K and M/D/1/K models show that the performance of the algorithms in terms of convergence speed and accuracy is good in general cases. The worst performance of the algorithms occurs when traffic intensity approaches one. An argument is made to explain this phenomenon.
- Beyond Software Performance VisualizationAbrams, Marc; Lee, Timothy; Cadiz, Horacio; Ganugapati, Krishna (Department of Computer Science, Virginia Polytechnic Institute & State University, 1994-02-01)Performance visualization tools of the last decade have yielded new insights into the new behavior of sequential, parallel, and distributed programs. However, they have three inherent limitations: (1) They only display what happened in one execution of a program. (This is dangerous when analyzing concurrent applications, which are prone to non-deterministic behavior.) (2) A human uses one or more bandwidth-limited senses with a visualization tool. (This limits the scalability of a visualization tool.) (3) The relationship of "interesting" program events are often separated in time by other events; thus discerning time dependent behavior often hinges on finding the "right" visualization - a possibly time-comsuming activity. CHITRA93 complements visualization systems, while alleviating these limitations. CHITRA93 analyzes a set (or ensemble) of traces by combining the visualization of a few traces with a statistical analysis of the entire ensemble (overcoming (1)); and reduces the ensemble to empirical models that capture the time dependent relationships of "interesting" program events through application, programming language, and computer architecture independent analysis tools (addressing (2) and (3)). CHITRA93 incorporates: transforms, such as aggregation, that simplify the ensemble and reduce the state space size of the models generated; a user interface that allows some transforms to be selected by editing the visualization with a mouse; homogeneity tests that allow partitioning of an ensemble; an efficient semi-Markov model generation algorithm whose computation time is linear in the sum of the lengths of the traces comprising the ensemble; and a CHAID-based model that can fathom non-Markovian relationships among transitions in the traces. The use of CHITRA93 is demonstrated by partitioning ten parallel database traces with nearly 8,000 states into two homogeneous subsets, each modeled by a 20 state irreducible, periodic (non-Markovian) stochastic process.
- Caching Proxies: Limitations and PotentialsAbrams, Marc; Standridge, Charles R.; Abdulla, Ghaleb; Williams, Stephen; Fox, Edward A. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1995-07-01)As the number of World-Wide Web users grow, so does the number of connections made to servers. This increases both network load and server load. Caching can reduce both loads by migrating copies of server files closer to the clients that use those files. Caching can either be done at a client or in the network (by a proxy server or gateway). We assess the potential of proxy servers to cache documents retrieved with the HTTP protocol. We monitored traffic corresponding to three types of educational workloads over a one semester period, and used this as input to a cache simulation. Our main findings are (1) that with our workloads a proxy has a 30-50% maximum possible hit rate no matter how it is designed; (2) that when the cache is full and a document is replaced, least recently used (LRU) is a poor policy, but simple variations can dramatically improve hit rate and reduce cache size; (3) that a proxy server really functions as a second level cache, and its hit rate may tend to decline with time after initial loading given a more or less constant set of users; and (4) that certain tuning configuration parameters for a cache may have little benefit.
- Cater: An Opportunistic Medium Access Control Protocol for Wireless Local Area NetworksMullins, Barry E. (Virginia Tech, 1997-06-23)An adaptive MAC protocol is developed and analyzed that offers a "best case" scenario by allowing the MAC to control medium parameters thereby fully exploiting the channel of an ad hoc wireless LAN. This new, opportunistic medium access control protocol is called CATER (Code Adapts To Enhance Reliability) and is based on the proposed MAC standard for wireless local area networks (WLAN)-IEEE 802.11 [IEE96]. As currently proposed, IEEE 802.11 uses a fixed pseudo-noise (PN) code for spreading the information signal, implying a fixed process gain at the receiver. When the channel degrades, IEEE 802.11 offers only retransmissions at the MAC layer to combat a corrupt medium. However, CATER allows communicating stations to reconfigure their transceivers to use a longer PN code after a prescribed number of failed retransmissions. This longer code increases the process gain of the receiver and reduces the error rate. After the two stations are reconfigured, the source station sends the frame in question. Immediately after that frame is acknowledged, the source station may send additional frames during the reconfigured period. Simulation and emulation are used to demonstrate and validate the adaptive protocol's capabilities. Results show that this new protocol offers substantial improvement in system throughput when the channel degrades to a point that reliable transmission of frames is not feasible in a standard IEEE 802.11 WLAN. Specifically, CATER continues to function, permitting up to 14 percent normalized aggregate throughput at times when IEEE 802.11 permits no frames to pass through the WLAN. In addition, throughput experiences only a small decrease due to protocol overhead during periods when stations experience a good channel with few bit errors. Moreover, CATER does not adversely affect the predominate transport layer protocol (i.e., TCP), and provides equitable service to all stations within the network.
- CATY: an ASN.1-C++ translator in support of distributed object-oriented applicationsLong, Wendy (Virginia Tech, 1994-04-15)When heterogeneous computers exchange data over a network, they must agree on a common interpretation of the data. The OSI suite of protocols includes a standard notation, Abstract Syntax Notation One (ASN.1), for describing the structure ("abstract syntax") of data. Previous work has shown that C++ is a good language for work with layered network architectures and specifically with ASN.1: the inheritance and polymorphism features of C++ are nicely suited for work with layered protocols, which can be seen and used in object-oriented terms; a C++ class hierarchy, designed to capture the language concepts of ASN.1, successfully separates the abstract syntax (or application level) from the encoding used during transfer (the "transfer syntax" at presentation level); and the class construct and scoping rules of C++ and the design of the class hierarchy much better preserve the structure and content of ASN.1 than do past attempts with C. This report presents CATV (Class-oriented ASN.1 Translator, Yacc-based), a translator from ASN.1 to a corresponding C++ abstract syntax class hierarchy. It is shown in this report that the translations produced by CATV are preferable to those produced by other translators based on the following criteria: preservation of names and types, consistent access to elements, support of modularity and subtypes, resolution of forward references, flexibility of encoding, and generality of use. Furthermore, it is shown that CATV has better throughput than PEPSY, an ASN.1 to C translator from ISODE.
- Characterizing Web Response TimeLiu, Binzhang M.S. (Virginia Tech, 1998-04-22)It is critical to understand WWW latency in order to design better HTTP protocols. In this study we characterize Web response time and examine the effects of proxy caching, network bandwidth, traffic load, persistent connections for a page, and periodicity. Based on studies with four workloads, we show that at least a quarter of the total elapsed time is spent on establishing TCP connections with HTTP/1.0. The distributions of connection time and elapsed time can be modeled using Pearson, Weibul, or Log-logistic distributions. We also characterize the effect of a user's network bandwidth on response time. Average connection time from a client via a 33.6 K modem is two times longer than that from a client via switched Ethernet. We estimate the elapsed time savings from using persistent connections for a page to vary from about a quarter to a half. Response times display strong daily and weekly patterns. This study finds that a proxy caching server is sensitive to traffic loads. Contrary to the typical thought about Web proxy caching, this study also finds that a single stand-alone squid proxy cache does not always reduce response time for our workloads. Implications of these results to future versions of the HTTP protocol and to Web application design also are discussed.
- CHITRA94: A Tool to Dynamically Charaterize Ensembles of Traces for Input Data Modeling and Output AnalsisAbrams, Marc; Batongbacal, Alan; Ribler, Randy; Vazirani, Devendra (Department of Computer Science, Virginia Polytechnic Institute & State University, 1994-06-01)CHITRA94 is the third generation of a comprehensive system to visualize, transform, statistically analyze, and model ensembles of trace data and validate the resultant models. The tool is useful for deriving input data models from trace data as well as for analysis of trace data output by a simulation. The tool uses an stochastic (possibly no-Markovian) process as its fundamental modeling component. The tool is unique in several respects. First, it focuses on the dynamic characterization of systems. Consequently it includes tests for homogeneity of ensembles, stationarity of individual traces, and the ability to partition ensembles into transient and stationary pieces. Second, CHITRA94 is a scalable performance tool: its methods are designed to work with an arbitrary number of traces in an ensemble so that a user can examine the variability of system behaviors across different traces (representing different observation periods, different system configurations, etc.). To analyze multiple traces, the user can either (1) map the traces to a model that characterizes the dynamic behavior or (2) use a novel visualization, the mass evolution graph, that shows the probability mass distribution evolution of one or more traces. A mass evolution graph is easily constructed from trace data, and the derivative of the paths it contains yield an estimate of probability mass as a function of time. Third, it analyzes categorical, not just numerical, time series data. Categorical data arises naturally in many computer and communication system modeling problems. Fourth, it includes a library of transforms that reduce the state space of the stochastic process generated. Fifth, CHITRA94 is implemented as a user extensible collection of small programs, organized as a library, which allows the user to write new library modules that use existing modules to automate analysis procedures. Instead, CHITRA94 may be invoked from command line, under a GUI, or integrated with another tool (e.g., a simulation model development or CASE tool). The use of CHITRA94 is illustrated on a variety of trace data, and the extensibility is illustrated on the problem of partitioning an ensemble of 60 traces of compressed entertainment video into mutually exclusive, exhaustive, and homogeneous subsets from which a hierarchical workload model is derived.
- Chitra: Visual Analysis of Parallel and Distributed Programs in the Time, Event, and Frequency DomainsAbrams, Marc; Doraswamy, Naganand; Mathur, Anup (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)Chitra analyzes a program execution sequence (PES) collected during execution of a program and produces a homogeneous, semi-Markov chain model fitting the PES. The PES represents the evolution of a program state vector in time. Therefore Chitra analyzes the time-dependent behavior of a program. The paper describes a set of transforms that map a PES to a simplified PES. Because the transforms are program-independent, Chitra can be used with any program. Chitra provides a visualization of PES's and transforms, to allow a user visually to guide transform selection in an effort to generate a simple yet accurate semi-Markov chain model. The resultant chain can predict performance at program parameters different than those used in the input PES, and the chain structure can diagnose performance problems.
- Computational Geometric Performance Analysis of Limit Cycles in Timed Transition SystemsAbrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993-09-01)Certain parallel software performance evaluation problems are equivalent to computational geometric problems. Consider a timed transition system representing a parallel program: a set of variables, a set of states, an initial state, a transition function mapping a set to a set of successor states, and a description of the time between transitions. Given a timed transition system, the paper solves four problems: (1) state the necessary and sufficient conditions for a TES to contain a LCES; (2) given the initial starting time of each process, find a representation of the set of all possible TESs; (3) determine if any initial process starting times exist that lead to a LCES in which no process ever blocks; and (4) find the set of all possible LCESs.
- The Cost of Terminating Optimistic Parallel Discrete-Event SimulationsSanjeevan, Vasant; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)In a previous paper, we proposed seven algorithms for mechanically adding an arbitrary termination condition to a conservative-synchronous, non-terminating parallel simulation. Informal arguments about the performance of each algorithm were made, and the arguments were confirmed through measurement for four of these algorithms. The benchmark used was the simulation of a Torus network using the Bounded Lag protocol on a shared memory multiprocessor. In this paper, we report on the performance of the simulation of the same Torus network benchmark with the same four termination conditions using an optimistic protocol on a message-passing multiprocessor. We also report on the performance of a colliding pucks simulation with three additional termination conditions.
- A data analysis software tool for the visual simulation environmentTuglu, Ali (Virginia Tech, 1995)The objective of the research described herein is to develop a prototype data analysis software tool integrated within the Visual Simulation Environment (VSE). The VSE is an integrated set of software tools that provide computer-aided assistance throughout the development life cycle of visual discrete-event simulation models. Simulation input and output data analyses are commonly needed in simulation studies. A software tool performing such data analysis is required within the VSE to provide automated support for input data modeling and output data analysis phases of the model development life cycle. The VSE DataAnalyzer provides general statistics. histograms, confidence intervals, and randomness tests for the data sets. It can also create C modules for generating random variates based on a collected set of data. Furthermore, the VSE DataAnalyzer possesses the basic file management, editing, printing, and formatting functionalities as well as a complete help feature. It has been used in a senior-level Simulation and Modeling course, and the feedback from the students has been positive. New functionalities can easily be added to the VSE DataAnalyzer due to its object-oriented software structure. The VSE DataAnalyzer is yet another software tool created to provide more comprehensive automated support throughout the visual simulation model development.
- The design and implementation of CHITRA92, a system to empirically model concurrent software performanceGanugapati, Krishna (Virginia Tech, 1993-04-15)With parallel and distributed computing entering the mainstream of computer science, it is important to ensure that parallel application codes are optimized to achieve the best possible performance. This thesis describes the design and implementation of CHITRA92, the second generation of a performance analysis system for parallel programs. CHITRA92 is unique in that it uses visualization techniques to analyze the dynamic activity of a program and produces a semi-Markov chain model of the program's behavior. This model can be parameterized to predict behavior of a program and identify the performance bottlenecks in the program. The important contributions of the CHITRA92 system are: • The dynamic activity of a program is represented through a program execution sequence (PES) and a set of program parameters. A PES description language has been defined to allow users to describe the structure of a PES state vector and instances of the state vector. • A PES is reduced to a semi-Markov chain model via a set of transformations. • Visualization is used to assist in selecting which transforms to apply to a PES. • The presence of periodic behavior in PES's can be identified using spectral analysis techniques.
- Design Issues in General Purpose, Parallel Simulation LanguagesAbrams, Marc; Lomow, Greg (Department of Computer Science, Virginia Polytechnic Institute & State University, 1989)This paper addresses the topic of designing general purpose, parallel simulation languages. We discuss how parallel simulation languages differ from general purpose programming languages. Our thesis is that the issues of distribution, performance, unusual implementation mechanism, and the desire for determinism are the dominant considerations in designing a simulation language today. We then discuss the separate roles that special and general purpose simulation languages play. Next we use the two languages, Sim++ and CPS, to illustrate these issues. Then we discuss eight design considerations: process versus event oriented-view, basic program structure, I/O, making implementation cost explicit to the programmer, providing dynamic facilities, memory management, the semantics of false messages in time warp, and program development methodology considerations. A number of conclusions are drawn from our experiences in language design.
- Determining Initial States for Time-Parallel SimulationsWang, Jain J.; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)In this paper, we propose a time-parallel simulation method which uses a pre-simulation to identify recurrent states. Also, an approximation technique is suggested for approximate Markovian modeling for queueing networks to extend the class of simulation models which can be simulated efficiently using our time-parallel simulation. A central server system and a virtual circuit of a packet-switched data communication network modeled by closed queueing networks are experimented with the proposed time-parallel simulation. Experiment results suggest that the proposed approach can exploit massive parallelism while yielding accurate results.
- The development of a CHAID-based model for CHITRA93Cadiz, Horacio T. (Virginia Tech, 1994-02-14)The complexity of the behavior of parallel and distributed programs is the major reason for the difficulties in the analysis and diagnosis of their performance. Complex systems such as these have frequently been studied using models as abstractions of such systems. By capturing only the details of the system which are considered essential, a model is a replica of the complex system which is simpler and easier to understand than the real system. CHITRA92, the second generation of the performance analysis tool CHITRA, builds a continuous time semi-Markov chain to model program behavior. However, this model is limited to representing relationships between states which are only immediate predecessors or successors of each other. This project introduces and implements a new empirical model of the behavior of software programs which is able to represent dependencies between nonsequential program states. The implementation combines deterministic and probabilistic modeling and is based on the Chi Automatic Interaction Detection (CHAID) statistical technique designed for investigating categorical data. The empirical model, constructed by analyzing an ensemble of program execution sequences, is stochastic and non-Markovian in the form of an N -step Transition Matrix. The algorithm is integrated as one of the modeling subsystems of CHITRA93, the third generation of CHITRA.
- The Effectiveness of Cache Coherence Implemented on the WebDoswell, Felicia; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 2000-08-01)The popularity of the World Wide Web (Web) has generated so much network traffic that it has increased concerns as to how the Internet will scale to meet future demand. The increased population of users and the large size of files being transmitted have resulted in concerns for different types of Internet users. Server administrators want a manageable load on their servers. Network administrators need to eliminate unnecessary traffic, thereby allowing more bandwidth for useful information. End users desire faster document retrieval. Proxy caches decrease the number of messages that enter the network by satisfying requests before they reach the server. However, the use of proxies introduces a concern with how to maintain consistency among cached document versions. Existing consistency protocols used in the Web are proving to be insufficient to meet the growing needs of the World Wide Web population. For example, too many messages are due to caches guessing when their copy is inconsistent. One option is to apply the cache coherence strategies already in use for many other distributed systems, such as parallel computers. However, these methods are not satisfactory for the World Wide Web due to its larger size and range of users. This paper provides insight into the characteristics of document popularity and how often these popular documents change. The frequency of proxy accesses to documents is also studied to test the feasibility of providing coherence at the server. The main goal is to determine whether server invalidation is the most effective protocol to use on the Web today. We make recommendations based on how frequently documents change and are accessed.
- Efficient parallel simulations and their application to communication networksWang, Jain-Chung J. (Virginia Tech, 1994)Simulation is one of the most important tools for system performance evaluation in communication networks as well as many other areas. However, simulation is computationally intensive. A traditional sequential simulation of a complex model or a rare-event system may require days or even weeks of computer execution time. Therefore, simulation often becomes a bottleneck of a performance study. With the growing availability of multiprocessor computing systems (e.g., tightly-coupled parallel computers or distributed networks of workstations), parallel simulation, which parallelizes a simulation program for execution on multiple processors, becomes an attractive means to reduce simulation execution time. With few exceptions, existing parallel simulation algorithms can be broadly classified into four methods: multiple replication, time-parallel, parallel regenerative, and space-parallel. Each method is associated with some advantages and limitations. We study these methods and propose a number of parallel simulation algorithms for a class of communication network systems modeled by queueing systems. In multiple replication simulation, each processor simulates a replication of the target simulation model independently. Due to the lack of a prior: knowledge about the steady state conditions, an arbitrarily selected initial state is often used for each simulation run. This can result in significant bias in the simulation outcome. To reduce this initial transient bias, we propose a polling initialization technique, in which a pilot simulation is used to find 'good' initial states that are representative of the steady-state conditions. Time-parallel simulation obtains parallelism by partitioning the time domain of the simulation model into a number of batches. Each batch is computed by a processor independently. Time-parallel simulation has not been fully explored by the research community partly because finding the exact initial states for the batches is often challenging and problem dependent. We develop two approximation time-parallel simulation algorithms for acyclic networks of loss G/G/1/K and G/D/1/K queues. These algorithms exploit unbounded parallelism and can achieve near-linear speedup when the number of arrivals is large. Two other time-parallel approaches are also proposed for Markov chains. For more general simulation models, an approximation approach that uses a substate matching technique is presented. Parallel regenerative simulation exploits parallels in by partitioning the simulation trajectory into a number of regeneration cycles. The amount of parallelism relies on the regeneration frequency of the model. In practice a regeneration state that has a short expected regeneration cycle length often does not exist in the target simulation model. As a result, a sufficient number of observations can not be obtained in a finite simulation interval. To overcome this constraint, we propose a partial regeneration algorithm that uses a substate matching technique to increase the number of observations. When the memory requirement of the target simulation models exceeds the storage capacity of a single processor, space-parallel simulation is an appropriate method. In space-parallel simulation, the target simulation model is decomposed into a number of components such that each component contains a disjoint subset of the model state variables. Each component is mapped into a logical process which is responsible for computing the trajectory corresponding to the component over the simulation time interval. An important class of space-parallel simulation is the conservative simulation, in which each logical process can proceed processing an event only if the process ensures that no event. will arrive later with a smaller timestamp. A number of previous experimental studies have suggested that lookahead, a capability that allows a simulation to look into the simulation time future, plays an important role in the performance of the conservative simulation. Although the performance of conservative simulation has been the interest in many previous studies, there has been a lack of formal arguments to quantify the impact of lookahead to conservative simulation performance. To address this question, we develop stochastic models to study the relationship between the amount of lookahead and the simulation performance with respect to different model topologies. We show that for closed simulation models, the simulation execution time is proportional to the amount of lookahead. For open models, on the other hand, lookahead is effectively useless when the simulation length is long.