bluuebunny/crossref_metadata_2025 huggingface dataset:
Analyzing stability in wide-area network performance
Authors: Balakrishnan Hari , Stemm Mark , Seshan Srinivasan , Katz Randy H.
Published: January 2007

The Internet is a very large scale, complex, dynamical system that is hard to model and analyze. In this paper, we develop and analyze statistical models for the observed end-to-end network performance based on extensive packet-level traces (consisting of approximately 1.5 billion packets) collected from the primary Web site for the Atlanta Summer Olympic Games in 1996. We find that observed mean throughputs for these transfers measured over 60 million complete connections vary widely as a function of end-host location and time of day, confirming that the Internet is characterized by a large degree of heterogeneity. Despite this heterogeneity, we find (using best-fit linear regression techniques) that we can express the throughput for Web transfers to most hosts as a random variable with a log-normal distribution. Then, using observed throughput as the control parameter, we attempt to quantify the
spatial
(statistical similarity across neighboring hosts) and
temporal
(persistence over time) stability of network performance. We find that Internet hosts that are close to each other often have almost identically distributed probability distributions of throughput. We also find that throughputs to individual hosts often do not change appreciably for several minutes. Overall, these results indicate that there is promise in protocol mechanisms that cache and share network characteristics both within a single host and amongst nearby hosts.
Performance issues of enterprise level web proxies
Authors: Maltzahn Carlos , Richardson Kathy J. , Grunwald Dirk
Published: January 2007

Enterprise level web proxies relay world-wide web traffic between private networks and the Internet. They improve security, save network bandwidth, and reduce network latency. While the performance of web proxies has been analyzed based on synthetic workloads, little is known about their performance on real workloads. In this paper we present a study of two web proxies (CERN and Squid) executing real workloads on Digital's Palo Alto Gateway. We demonstrate that the simple CERN proxy architecture outperforms all but the latest version of Squid and continues to outperform cacheless configurations. For the measured load levels the Squid proxy used at least as many CPU, memory, and disk resources as CERN, in some configurations significantly more resources. At higher load levels the resource utilization requirements will cross and Squid will be the one using fewer resources. Lastly we found that cache hit rates of around 30% had very little effect on the requests service time.
Queue management for explicit rate based congestion control
Authors: Ma Qingming , Ramakrishnan K. K.
Published: January 2007

Rate based congestion control has been considered desirable, both to deal with the high bandwidth-delay products of today's high speed networks, and to match the needs of emerging multimedia applications. Explicit rate control achieves low loss because sources transmit smoothly at a rate adjusted through feedback to be within the capacity of the resources in the network. However, large feedback delays, presence of higher priority traffic, and varying transient situations make it difficult to ensure
feasibility
(i.e., keep the aggregate arrival rate below the bottleneck resource's capacity) while also maintaining high resource utilization. These conditions along with the "fast start" desired by data applications often result in substantial queue buildups.We describe a scheme that manages the queue buildup at a switch even under the most aggressive patterns of sources, in the context of the Explicit Rate option for the Available Bit Rate (ABR) congestion control scheme. A switch observes the buildup of its queue, and uses it to reduce the portion of the link capacity allocated to sources bottlenecked at that link. We use the concept of a "virtual" queue, which tracks the amount of queue that has been "reduced", but has not yet taken effect at the switch. We take advantage of the natural timing of "resource management" (RM) cells transmitted by sources. The scheme is elegant in that it is simple, and we show that it reduces the queue buildup, in some cases, by more than two orders of magnitude and the queue size remains around a desired target. It maintains max-min fairness even when the queue is being drained. The scheme is scalable, and is as responsive as can be expected: within the constraints of the feedback delay. Finally, no changes are needed to the ATM Forum defined source/destination policies.
TCP over ATM
Authors: Ott Teunis J. , Aggarwal Neil
Published: January 2007

This paper reports on a simulation study of the relative performances of the ATM ABR and UBR service categories in transporting TCP/IP flows through an ATM Network. The objective is two-fold: (i) to understand the interaction between the window - based end-to-end flowcontrol TCP and the rate based flowcontrol ABR which is restricted to the ATM part of the network, and (ii) to decide whether the greater complexity of ABR (than UBR) pays off in better performance of ABR (than UBR).The most important conclusion is that there does not seem to be strong evidence that for TCP/IP workloads the greater complexity of ABR pays off in better performance.
Scalable reliable multicast using multiple multicast groups
Authors: Kasera Sneha K. , Kurose Jim , Towsley Don
Published: January 2007

We examine an approach for providing reliable, scalable multicast communication, using multiple multicast groups for reducing receiver processing costs in a multicast session. In this approach a single multicast group is used for the original transmission of packets. Retransmissions of packets are done to separate multicast groups, which receivers dynamically join or leave. We first show that by using an infinite number of multicast groups, processing overhead at the receivers are substantially reduced. Next, we show that, for a specific negative acknowledgment (NAK)-based protocol, most of this reduction can be obtained by using only a small number of multicast groups for a wide range of system parameters. Finally, we present a local filtering scheme for minimizing join/leave signaling when multiple multicast groups are used.
Performance debugging shared memory parallel programs using run-time dependence analysis
Authors: Rajamony Ramakrishnan , Cox Alan L.
Published: January 2007

We describe a new approach to performance debugging that focuses on automatically identifying computation transformations to reduce synchronization and communication. By grouping writes together into
equivalence classes
, we are able to tractably collect information from long-running programs. Our performance debugger analyzes this information and suggests computation transformations in terms of the source code. We present the transformations suggested by the debugger on a suite of four applications. For Barnes-Hut and Shallow, implementing the debugger suggestions improved the performance by a factor of 1.32 and 34 times respectively on an 8-processor IBM SP2. For Ocean, our debugger identified excess synchronization that did not have a significant impact on performance. ILINK, a genetic linkage analysis program widely used by geneticists, is already well optimized. We use it only to demonstrate the feasibility of our approach to long-running applications.We also give details on how our approach can be implemented. We use novel techniques to convert control dependences to data dependences, and to compute the source operands of stores. We report on the impact of our instrumentation on the same application suite we use for performance debugging. The instrumentation slows down the execution by a factor of between 4 and 169 times. The log files produced during execution were all less than 2.5 Mbytes in size.
Informed multi-process prefetching and caching
Authors: Tomkins Andrew , Patterson R. Hugo , Gibson Garth
Published: January 2007

Informed prefetching and caching based on application disclosure of future I/O accesses (hints) can dramatically reduce the execution time of I/O-intensive applications. A recent study showed that, in the context of a single hinting application, prefetching and caching algorithms should adapt to the dynamic load on the disks to obtain the best performance. In this paper, we show how to incorporate adaptivity to disk load into the TIP2 system, which uses
cost-benefit analysis
to allocate global resources among multiple processes. We compare the resulting system, which we call TIPTOE (TIP with Temporal Overload Estimators) to Cao et al's LRU-SP allocation scheme, also modified to include adaptive prefetching. Using disk-accurate trace-driven simulation we show that, averaged over eleven experiments involving pairs of hinting applications, and with data striped over one to ten disks, TIPTOE delivers 7% lower execution time than LRU-SP. Where the computation and I/O demands of each experiment are closely matched, in a two-disk array, TIPTOE delivers 18% lower execution time.
Adaptive page replacement based on memory reference behavior
Authors: Glass Gideon , Cao Pei
Published: January 2007

As disk performance continues to lag behind that of memory systems and processors, virtual memory management becomes increasingly important for overall system performance. In this paper we study the page reference behavior of a collection of memory-intensive applications, and propose a new virtual memory page replacement algorithm, SEQ. SEQ detects long sequences of page faults and applies most-recently-used replacement to those sequences. Simulations show that for a large class of applications, SEQ performs close to the optimal replacement algorithm, and significantly better than Least-Recently-Used (LRU). In addition, SEQ performs similarly to LRU for applications that do not exhibit sequential faulting.
Size-limited batch movement in product-form closed discrete-time queueing networks
Authors: Woodward Michael E.
Published: January 2007

Existing models for product-form closed discrete-time queueing networks with batch movement of customers implicitly assume that batch sizes are unrestricted. In many practical modelling situations however, it is necessary to impose restrictions on the batch sizes, and this paper examines the repercushions of such restrictions on the product-form properties of the networks. It is shown that when batch sizes are restricted independently then, in general, the resulting networks cannot have a product-form equilibrium distribution. Sufficient conditions to retain a product-form are derived in the cases when batch sizes are either correlated or depend on the state of the network. Examples of applying the results to obtain product-form networks with both correlated and state dependent batch movement are given.
On the characterization of VBR MPEG streams
Authors: Krunz Marwan , Tripathi Satish K.
Published: January 2007

We present a comprehensive model for variable-bit-rate MPEG video streams. This model captures the bit-rate variations at multiple time scales. Long-term variations are captured by incorporating scene changes, which are most noticeable in the fluctuations of
I
frames. The size of an
I
frame is modeled by the sum of two random components: a scene-related component and an AR(2) component that accounts for the fluctuations within a scene. Two random processes of
i.i.d.
rvs are used to model the sizes of
P
and
B
frames, respectively. The complete model is then obtained by intermixing the three sub-models according to a given GOP pattern. It is shown that the composite model exhibits long-range dependence (LRD) in the sense that its autocorrelation function is non-summable. The LRD behavior is caused by the repetitive GOP pattern which induces periodic cross-correlations between different types of frames. Using standard statistical methods, we successfully fit our model to several empirical video traces. We then study the queueing performance for video traffic at a statistical multiplexer. The results show that the model is sufficiently accurate in predicting the queueing performance for real video streams.
The utility of exploiting idle workstations for parallel computation
Authors: Acharya Anurag , Edjlali Guy , Saltz Joel
Published: January 2007

In this paper, we examine the utility of exploiting idle workstations for parallel computation. We attempt to answer the following questions. First, given a workstation pool, for what fraction of time can we expect to find a cluster of
k
workstations available? This provides an estimate of the opportunity for parallel computation. Second, how stable is a cluster of free machines and how does the stability vary with the size of the cluster? This indicates how frequently a parallel computation might have to stop for adapting to changes in processor availability. Third, what is the distribution of workstation idle-times? This information is useful for selecting workstations to place computation on. Fourth, how much benefit can a user expect? To state this in concrete terms, if I have a pool of size
S,
how big a parallel machine should I expect to get for free by harvesting idle machines. Finally, how much benefit can be achieved on a real machine and how hard does a parallel programmer have to work to make this happen? To answer the workstation-availability questions, we have analyzed 14-day traces from three workstation pools. To determine the equivalent parallel machine, we have simulated the execution of a group of well-known parallel programs on these workstation pools. To gain an understanding of the practical problems, we have developed the system support required for adaptive parallel programs and have used it to build an adaptive parallel computational fluid dynamics application.
Group-guaranteed channel capacity in multimedia storage servers
Authors: Tsiolis Athanassios K. , Vernon Mary K.
Published: January 2007

One of the open questions in the design of multimedia storage servers is in what order to serve incoming requests. Given the capability provided by the disk layout and scheduling algorithms to serve multiple streams simultaneously, improved request scheduling algorithms can reduce customer waiting times. This results in better service and/or lower customer loss. In this paper we define a new class of request scheduling algorithms, called Group-Guaranteed Server Capacity (GGSC), that preassign server channel capacity to groups of objects. We also define a particular formal method for computing the assigned capacities to achieve a given performance objective. We observe that the FCFS policy can provide the precise time of service to incoming customer requests. Under this assumption, we compare the performance of one of the new GGSC algorithms, GGSC
W
-FCFS, against FCFS and against two other recently proposed scheduling algorithms: Maximum Factored Queue length (MFQ), and the FCFS-n algorithm that preassigns capacity only to each of the
n
most popular objects. The algorithms are compared for both
competitive market
and
captured audience
environments.Key findings of the algorithm comparisons are that: (1) FCFS-n has no advantage over FCFS if FCFS gives time of service guarantees to arriving customers, (2) FCFS and GGSC
W
-FCFS are superior to MFQ for both competitive and captive audience environments, (3) for competitive servers that are configured for customer loss less than 10%, FCFS is superior to all other algorithms examined in this paper, and (4) for captive audience environments that have objects with variable playback length, GGSC
W
-FCFS is the most promising of the policies considered in this paper. The conclusions for FCFS-n and MFQ differ from previous work because we focus on competitive environments with customer loss under 10%, we assume FCFS can provide time of service guarantees to all arriving customers, and we consider the distribution of customer waiting time as well as the average waiting time.
REDLOG
Authors: Dolzmann Andreas , Sturm Thomas
Published: January 2007

REDLOG
is a package that extends the computer algebra system
REDUCE
to a computer logic system, i.e., a system that provides algorithms for the symbolic manipulation of first-order formulas over some temporarily fixed language and theory. In contrast to theorem provers, the methods applied know about the underlying algebraic theory and make use of it. We illustrate some applications of
REDLOG
, describe its functionality as it appears to the user, and explain the design issues and implementation techniques.
REDLOG
is available on the WWW.
Book review: Logic Programming: Proceedings of the Elev- enth International Conference on Logic Programming. Pascal van Hentenryck (Ed.) (The MIT Press 1994)
Authors: Posthoff Christian
Published: January 2007

The field of logic programming has seen tremendous growth in the last several years, both in depth and in scope. This book arose from the Eleventh International Conference on Logic Programming. The efforts of MIT Press to make this book available, and through it recent research results, deserve much credit.
Conservative synchronization in object-oriented parallel battlefield discrete event simulations
Authors: Hiller James B. , Hartrum Thomas C.
Published: January 2007

We present a conservative strategy for spatially decomposed parallel discrete event battlefield simulation. The traditional null message algorithm provides a foundation from which a mapping to generic simulation attributes can be made. We informally discuss preservation of logical correctness and freedom from deadlock. Experimental results demonstrate the potential execution time savings when load imbalance is not dominant; more importantly, they highlight improvement opportunities in spite of potential load imbalance. The net result is that a very reasonable performance gain can be delivered for little effort in a way that supports good simulation system design principles. The approach is straightforward and can be easily implemented as part of a more general sequential or parallel simulation support environment. While the approach is expressed in terms of battlefield simulation, its essence applies to many simulation applications.
A multidimensional study on the feasibility of parallel switch-level circuit simulation
Authors: Chen Yu-an , Jha Vikas , Bagrodia Rajive
Published: January 2007

This paper presents the results of an experimental study to evaluate the effectiveness of multiple synchronization protocols and partitioning algorithms in reducing the execution time of switch-level models of VLSI circuits. Specific contributions of this paper include: (i) parallelizing an existing switch-level simulator such that the model can be executed using conservative and optimistic simulation protocols with minor changes, (ii) evaluating effectiveness of several partitioning algorithms for parallel simulation, and (iii) demonstrating speedups with both conservative and optimistic simulation protocols for seven circuits, ranging in size from 3K transistors to about 87K transistors.
A new approach for partitioning VLSI circuits on transistor level
Authors: Fröhlich Norbert , Schlagenhaft Rolf , Fleischmann Josef
Published: January 2007

For parallel simulation of VLSI circuits on transistor level a sophisticated partitioning of the circuits into subcircuits is crucial. Each net connecting the subcircuits causes additional communication and computation effort. As the slave processors simulating the subcircuits advance synchronously in time, the computation effort for each subcircuit should be approximately the same. In this paper a new approach for partitioning VLSI circuits on transistor level yielding a low number of interconnects between the subcircuits and balanced subcircuit sizes is presented. Simulation of industrial circuits using this partitioning is up to 41% faster than with other known partitioning approaches for parallel analog simulation.
State saving for interactive optimistic simulation
Authors: Franks Steve , Gomes Fabian , Unger Brian , Cleary John
Published: January 2007

Time Warp's optimistic scheduling requires the maintenance of simulation state history to support rollback in the event of causality violations. State history, and the ability to rollback the simulation, can provide unique functionality for human-in-the-loop simulation environments. This paper investigates the use of Time Warp to output valid simulation state in a near real-time manner, re-execute portions of the simulation, and interactively probe simulation values to ascertain underlying causes of transient behavior.A shared-memory, multi-threaded interactive simulation architecture is presented and the additional state saving requirements imposed by interactivity are examined. The shortcomings of existing state saving schemes lead us to propose Multiplexed State Saving (MSS). By interleaving checkpointing and incremental state logs MSS provides bounded rollback costs and asynchronous access to prior simulation state. The interaction algorithms and MSS form a scalable, bounded cost component suitable for use in a real-time interactive Time Warp system.
SQTW
Authors: Fabbri Alessandro , Donatiello Lorenzo
Published: January 2007

In this paper we address the problem of efficiently performing parallel discrete-event simulation in the case that events elaboration is dependent of other processes' local states. We propose a parallel simulation policy, called State Query Time Warp (SQTW), based on the Time Warp mechanism. We present experiments performed by means of a SQTW-based parallel simulator on a T-800 transputer machine for solving performance models based on state-dependent routing queueing network models. The experiments are used for assessing overheads and efficiency involved by SQTW; results show that high efficiency is achievable, and surprisingly reveal SQTW is able to globally reduce rollback overheads with respect to corresponding Time Warp simulations.
Optimistic distributed simulation based on transitive dependency tracking
Authors: Damani Om P. , Wang Yi-Min , Garg Vijay K.
Published: January 2007

In traditional optimistic distributed simulation protocols, a logical process (LP) receiving a straggler rolls back and sends out anti-messages. The receiver of an anti-message may also roll back and send out more anti-messages. So a single straggler may result in a large number of anti-messages and multiple rollbacks of some LPs. In the authors' protocol, an LP receiving a straggler broadcasts its rollback. On receiving this announcement, other LPs may roll back but they do not announce their rollbacks. So each LP rolls back at most once in response to each straggler. Anti-messages are not used. This eliminates the need for output queues and results in simple memory management. It also eliminates the problem of cascading rollbacks and echoing, and results in faster simulation. All this is achieved by a scheme for maintaining transitive dependency information. The cost incurred includes the tagging of each message with extra dependency information and the increased processing time upon receiving a message. They also present the similarities between the two areas of distributed simulation and distributed recovery. They show how the solutions for one area can be applied to the other area.
Using agents for simulating and implementing Petri nets
Authors: Holvoet Tom , Verbaeten Pierre
Published: January 2007

This paper presents a software architecture for simulating and implementing Petri nets. It is based on object-oriented techniques and autonomous agents. Object-orientation enables the adaptation and extension of the software architecture with new or alternatively defined features. Agents allow to model a net as a set of autonomous, cooperating entities. The result is a flexible and extendible framework of reusable components for efficiently implementing a large family of Petri net classes.The execution can be performed on a mono-processor, a parallel or distributed system. This is the result of using the XENOOPS execution environments for parallel applications.
Tolerant synchronization for distributed simulations of interconnected computer networks
Authors: Martini Peter , Rümekasten Markus , Tölle Jens
Published: January 2007

This paper presents the tolerant, hybrid synchronization schema and its benefits for the parallel and distributed simulation of interconnected computer networks. The hybrid schema combines conservative and optimistic synchronization approaches by using lookahead for scheduling special events and using the flexibility of Time Warp in certain cases. In addition to these classical approaches the introduction of the |tolerance| allows the distributed modules to simulate further ahead than guaranteed by the conservative synchronization schema. This results in significantly smaller simulation runtimes and many other benefits.
Performance of a conservative simulator of ATM networks
Authors: Cleary John G. , Tsai Jya-Jang
Published: January 2007

This paper describes an implementation of a conservative parallel distributed simulator that has been used to simulate a high fidelity model of ATM networks. Important optimisations of the simulator for this application are described. The performance of the simulator is reported on up to 12 processors and compared with a sequential implementation. It is seen that the simulator gives good speedup and better performance than the sequential implementation. It is noted that the low overhead of the simulator relies on there being good lookahead in realistic models of ATM networks. Some situations where this lookahead is significantly reduced are described together with future extensions to fix these problems.
Hierarchical modeling and distributed simulation with HIT
Authors: Warda A. M. , Sczittnick M.
Published: January 2007

The Hierarchical Tool HIT is a software tool for hierarchical modeling and performance evaluation of discrete event systems. Besides analytical and numerical solution techniques HIT provides the evaluation of models by sequential simulation. Here we present concepts for optimistic distributed simulation of HIT-models by partitioning them with respect to subhierarchies. The main goals of the concept being presented are the preservation of model structure even in lower levels of the realization (e.g. use of the process view of simulation throughout all levels of abstraction) and distribution transparency on the modeling level (homogeneous model specification for all solution techniques).
MRE
Authors: Natrajan Anand , Reynolds Paul F. , Srinivasan Sudhir
Published: January 2007

Multi-resolution representation of simulated entities is considered essential for a growing portion of distributed simulations. Heretofore, modelers have represented entites at just one level of resolution, or have represented concurrent representations in an inconsistent manner. We address the question of the cost of maintaining multiple, concurrent representations. We present a brief overview of our concept of a Multiple Resolution Entity (MRE) and Attribute Dependency Graph (ADG) both originally described elsewhere, and then compare simulation and consistency costs of some approaches, including our own MRE/ADG-based approach, to multi-resolution modeling. The cost analysis presented here is the first known analysis of its type, and will provide a basis for simulation designers to determine the best, and most cost-effective approach to supporting simulation of entities at different levels of resolution concurrently.
Support of VBR video streams under disk bandwidth limitations
Authors: Papadopouli Maria , Golubchik Leana
Published: January 2007

We present scheduling techniques for a
scalable
video server in a multi-disk environment. The scheduling of the retrieval is introduced in a dynamic rate-distortion context that exploits both the multiresolution property of video and replication techniques.
Prefetching over a network
Authors: Rochberg David , Gibson Garth
Published: January 2007

We discuss CTIP, an implementation of a network filesystem extension of the successful TIP informed prefetching and cache management system. Using a modified version of TIP in NFS client machines (and unmodified NFS servers). CTIP takes advantage of application-supplied hints that disclose the application's future read accesses. CTIP uses these hints to aggressively prefetch file data from an NFS file server and to make better local cache replacement decisions. This prefetching hides disk latency and exposes storage parallelism. Preliminary measurements that show CTIP can reduce execution time by a ratio comparable to that obtained with local TIP over a suite of I/O-intensive hinting applications. (For four disks, the reductions in execution time range from 17% to 69%). If local TIP execution requires that data first be loaded from remote storage into a local scratch area, then CTIP execution is significantly faster than the aggregate time for loading the data and executing. Additionally, our measurements show that the benefit of CTIP for hinting applications improves in the face of competition from other clients for server resources. We conclude with an analysis of the remaining problems with using unmodified NFS servers.
Algebraic methods for computing a generalized inverse
Authors: Noda Matu-Tarow , Makino Isao , Saito Toshiaki
Published: January 2007

Generalized inverses have many applications in engineering problems, such as data analysis, electrical networks, character recognitions, and so on. The most frequently used generalized inverse is a Moore-Penrose type's one. Let
A
be
m
x
n
matrix. The Moore-Penrose generalized inverse of
A,
i.e.,
n
x
m
matrix
G,
satisfies the following definitions:
AGA = A
GAG = G
(
AG
)

T
= AG

(
GA
)

T
= GA

where
I
shows a unit matrix. The Moore-Penrose generalized inverse is uniquely determined for a given matrix
A.
We denote the Moore-Penrose generalized inverse of
A
as
G = A
+
. Some properties of it are1. If
A
is regular, then
A
+
=
A
-1
2. If
A
= 0, then
A
+
= 03. If
A
is an
m
x
n
matrix and its rank is
m,
then
A
+
=

A
T

(

AA
T

)
-1
The problem is how to obtain
G
efficiently. Thus we wish to find a
fast
and
stable
method for the problem. The singular value decomposition (SVD) algorithm is well known numerical method which gives results quickly. However, on the accuracy of solutions, it is evident that an error-free method is preferable. Thus, here, we consider algebraic or symbolic methods for obtaining the Moore-Penrose generalized inverse.
Creating lifelike characters in
Toy Story
Authors: Porter Tom
Published: January 2007

As Visual Effects Supervisor on
Toy Story,
I led a technical group working on all the surface appearances in the film, along with certain visual effects outside the mainstream of Pixar's character animation process.
TED models for ATM internetworks
Authors: Perumalla Kalyan , Andrews Matthew , Bhatt Sandeep
Published: January 2007

We describe our experiences designing and implementing a virtual PNNI network testbed. The network elements and signaling protocols modeled are consistent with the ATM Forum
PNNI
draft specifications. The models will serve as a high-fidelity testbed of the transport and network layers for simulation-based studies of the scalability and performance of PNNI protocols.Our models are written in the new network description language
TeD
which offers two advantages. First, the testbed design is transparent; the model descriptions are developed separately from, and are independent of, the simulation-specific code. Second,
TeD
is compiled to run with the GTW (Georgia Tech Time Warp) simulation engine which is supported on shared-memory multiprocessors. Therefore, we directly obtain the advantages of parallel simulation.This is one of the first complex tests of the
TeD
modeling and simulation software system. The feedback from our experiences resulted in some significant improvements to the simulation software. The resulting
PNNI
models are truly transparent and the performance of the simulations is encouraging. We give results from preliminary simulations of call admission, set-up and tear-down in sample
PNNI
networks consisting of two hundred nodes and over three hundred edges. The time to simulate ten thousand call requests decreases significantly with the number of processors; we observe a speedup factor of 5.05 when 8 processors are employed compared to a single processor. Our initial implementations demonstrate the advantages of
TeD
for parallel simulations of large-scale networks.
The SIGSAM challenges
Authors: Flajolet Philippe , Salvy Bruno
Published: January 2007

We present answers to 5 out of 10 of the "Problems, Puzzles, Challenges" proposed by G. J. Fee and M. B. Monagan in the March 1997 issue of the
Sigsam Bulletin.
In all cases, the answer to a seemingly numerical problem is obtained via series expansions and asymptotic methods. This illustrates more generally the crucial rôle played in the presence of singular behaviours by symbolic asymptotics as a bridge between symbolic computation and numerical computations.All our computations have been performed using MapleV.4 on a Dec Alpha (255/233). The timings indicated correspond to executions on this machine.
Implementing cooperative prefetching and caching in a globally-managed memory system
Authors: Voelker Geoffrey M. , Anderson Eric J. , Kimbrel Tracy , Feeley Michael J. , Chase Jeffrey S. , Karlin Anna R. , Levy Henry M.
Published: January 2007

This paper presents
cooperative prefetching and caching
--- the use of network-wide global resources (memories, CPUs, and disks) to support prefetching and caching in the presence of hints of future demands. Cooperative prefetching and caching effectively unites disk-latency reduction techniques from three lines of research: prefetching algorithms, cluster-wide memory management, and parallel I/O. When used together, these techniques greatly increase the power of prefetching relative to a conventional (non-global-memory) system. We have designed and implemented PGMS, a cooperative prefetching and caching system, under the Digital Unix operating system running on a 1.28 Gb/sec Myrinet-connected cluster of DEC Alpha workstations. Our measurements and analysis show that by using available global resources, cooperative prefetching can obtain significant speedups for I/O-bound programs. For example, for a graphics rendering application, our system achieves a speedup of 4.9 over a non-prefetching version of the same program, and a 3.1-fold improvement over that program using local-disk prefetching alone.
The impact of I/O on program behavior and parallel scheduling
Authors: Rosti Emilia , Serazzi Giuseppe , Smirni Evgenia , Squillante Mark S.
Published: January 2007

In this paper we systematically examine various performance issues involved in the coordinated allocation of processor and disk resources in large-scale parallel computer systems. Models are formulated to investigate the I/O and computation behavior of parallel programs and workloads, and to analyze parallel scheduling policies under such workloads. These models are parameterized by measurements of parallel programs, and they are solved via analytic methods and simulation. Our results provide important insights into the performance of parallel applications and resource management strategies when I/O demands are not negligible.
Asymptotic behavior of global recovery in SRM
Authors: Raman Suchitra , McCanne Steven , Shenker Scott
Published: January 2007

The development and deployment of a large-scale, wide-area multicast infrastructure in the Internet has enabled a new family of multi-party, collaborative applications. Several of these applications, such as multimedia slide shows, shared whiteboards, and large-scale multi-player games, require
reliable
multicast transport, yet the underlying multicast infrastructure provides only a best-effort delivery service. A difficult challenge in the design of efficient protocols that provide reliable service on top of the best-effort multicast service is to maintain acceptable performance as the protocol
scales
to very large session sizes distributed across the wide area. The Scalable, Reliable Multicast (SRM) protocol [6] is a receiver-driven scheme based on negative acknowledgments (NACKs) reliable multicast protocol that uses randomized timers to limit the amount of protocol overhead in the face of large multicast groups, but the behavior of SRM at extremely large scales is not well-understood.In this paper, we use analysis and simulation to investigate the scaling behavior of global loss recovery in SRM. We study the protocol's control-traffic overhead as a function of group size for various topologies and protocol parameters, on a set of simple, representative topologies --- the cone (a variant of a clique), the linear chain, and the binary tree. We find that this overhead, as a function of group size, depends strongly on the topology: for the cone, it is always linear; for the chain, it is between constant and logarithmic; and for the tree, it is between constant and linear.
Queueing-based analysis of broadcast optical networks
Authors: McKinnon Martin W. , Rouskas George N. , Perros Harry G.
Published: January 2007

We consider broadcast WDM networks operating with schedules that mask the transceiver tuning latency. We develop and analyze a queueing model of the network in order to obtain the queue-length distribution and the packet loss probability at the transmitting and receiving side of the nodes. The analysis is carried out assuming finite buffer sizes, non-uniform destination probabilities and two-state MMBP traffic sources; the latter naturally capture the notion of burstiness and correlation, two important characteristics of traffic in high-speed networks. We present results which establish that the performance of the network is a complex function of a number of system parameters, including the load balancing and scheduling algorithms, the number of available channels, and the buffer capacity. We also show that the behavior of the network in terms of packet loss probability as these parameters are varied cannot be predicted without an accurate analysis. Our work makes it possible to study the interactions among the system parameters, and to predict, explain and fine tune the performance of the network.
Predicting MPEG execution times
Authors: Bavier Andy C. , Montz A. Brady , Peterson Larry L.
Published: January 2007

This paper reports on a set of experiments that measure the amount of CPU processing needed to decode MPEG-compressed video in software. These experiments were designed to discover indicators that could be used to predict how many cycles are required to decode a given frame. Such predictors can be used to do more accurate CPU scheduling. We found that by considering both frame type and size, it is possible to construct a linear model of MPEG decoding with
R
2
values of 0.97 and higher. Moreover, this model can be used to predict decoding times at both the frame and packet level that are almost always accurate to within 25% of the actual decode times. This is a surprising result given the large variability in MPEG decoding times, and suggests that it is feasible to design systems that make quality of service guarantees for MPEG-encoded video.
Self-similarity in file systems
Authors: Gribble Steven D. , Manku Gurmeet Singh , Roselli Drew , Brewer Eric A. , Gibson Timothy J. , Miller Ethan L.
Published: January 2007

We demonstrate that high-level file system events exhibit self-similar behaviour, but only for short-term time scales of approximately under a day. We do so through the analysis of four sets of traces that span time scales of milliseconds through months, and that differ in the trace collection method, the filesystems being traced, and the chronological times of the tracing. Two sets of detailed, short-term file system trace data are analyzed; both are shown to have self-similar like behaviour, with consistent Hurst parameters (a measure of self-similarity) for all file system traffic as well as individual classes of file system events. Long-term file system trace data is then analyzed, and we discover that the traces' high variability and self-similar behaviour does not persist across time scales of days, weeks, and months. Using the short-term trace data, we show that sources of file system traffic exhibit ON/OFF source behaviour, which is characterized by highly variably lengthed bursts of activity, followed by similarly variably lengthed periods of inactivity. This ON/OFF behaviour is used to motivate a simple technique for synthesizing a stream of events that exhibit the same self-similar short-term behaviour as was observed in the file system traces.
Performance measurements for multithreaded programs
Authors: Ji Minwen , Felten Edward W. , Li Kai
Published: January 2007

Multithreaded programming is an effective way to exploit concurrency, but it is difficult to debug and tune a highly threaded program. This paper describes a performance tool called Tmon for monitoring, analyzing and tuning the performance of multithreaded programs. The performance tool has two novel features: it uses "thread waiting time" as a measure and constructs thread waiting graphs to show thread dependencies and thus performance bottlenecks, and it identifies "semi-busy-waiting" points where CPU cycles are wasted in condition checking and context switching. We have implemented the Tmon tool and, as a case study, we have used it to measure and tune a heavily threaded file system. We used four workloads to tune different aspects of the file system. We were able to improve the file system bandwidth and throughput significantly. In one case, we were able to improve the bandwidth by two orders of magnitude.
An analytic behavior model for disk drives with readahead caches and request reordering
Authors: Shriver Elizabeth , Merchant Arif , Wilkes John
Published: January 2007

Modern disk drives read-ahead data and reorder incoming requests in a workload-dependent fashion. This improves their performance, but makes simple analytical models of them inadequate for performance prediction, capacity planning, workload balancing, and so on. To address this problem we have developed a new analytic model for disk drives that do readahead and request reordering. We did so by developing performance models of the disk drive components (queues, caches, and the disk mechanism) and a workload transformation technique for composing them. Our model includes the effects of workload-specific parameters such as request size and spatial locality. The result is capable of predicting the behavior of a variety of real-world devices to within 17% across a variety of workloads and disk drives.
Inter-receiver fairness
Authors: Jiang Tianji , Ammar Mostafa H. , Zegura Ellen W.
Published: January 2007

In a multicast ABR service, a connection is typically restricted to the rate allowed on the bottleneck link in the distribution tree from the source to the set of receivers. Because of this, receivers in the connection can experience
inter-receiver unfairness
, when the preferred operating rates of the receivers are different. In this paper we explore the issue of improving the inter-receiver fairness in a multicast ABR connection by allowing the connection to operate at a rate higher than what is allowed by the multicast tree's bottleneck link. Since this can result in cell loss to some receivers, we operate with the knowledge of each receiver's application-specific loss tolerance. The multicast connection rate is not allowed to increase beyond the point where the cell loss on a path to a receiver exceeds this receiver's loss tolerance. Based on these ideas we develop an inter-receiver fairness measure and a technique for determining the rate that maximizes this measure. We show possible switch algorithms that can be used to convey the parameters needed to compute the function to the connection's source. In addition we develop a global network measure that helps us assess the effect of increasing inter-receiver fairness on the total network delivered throughput. We also briefly explore improving inter-receiver fairness through the use of multiple virtual circuits to carry traffic for a single multicast session. A set of examples demonstrate the use of the inter-receiver fairness concept in various network scenarios.
Scheduling with implicit information in distributed systems
Authors: Arpaci-Dusseau Andrea C. , Culler David E. , Mainwaring Alan M.
Published: January 2007

Implicit coscheduling
is a distributed algorithm for time-sharing communicating processes in a cluster of workstations. By observing and reacting to implicit information, local schedulers in the system make independent decisions that dynamically coordinate the scheduling of communicating processes. The principal mechanism involved is
two-phase spin-blocking
: a process waiting for a message response spins for some amount of time, and then relinquishes the processor if the response does not arrive.In this paper, we describe our experience implementing implicit coscheduling on a cluster of 16 UltraSPARC I workstations; this has led to contributions in three main areas. First, we more rigorously analyze the two-phase spin-block algorithm and show that spin time should be increased when a process is receiving messages. Second, we present performance measurements for a wide range of synthetic benchmarks and for seven Split-C parallel applications. Finally, we show how implicit coscheduling behaves under different job layouts and scaling, and discuss preliminary results for achieving fairness.
Modeling and optimizing I/O throughput of multiple disks on a bus (summary)
Authors: Barve Rakesh , Shriver Elizabeth , Gibbons Phillip B. , Hillyer Bruce K. , Matias Yossi , Vitter Jeffrey Scott
Published: January 2007

For a wide variety of computational tasks, disk I/O continues to be a serious obstacle to high performance. The focus of the present paper is on systems that use multiple disks per SCSI bus. We measured the performance of concurrent random I/Os, and observed bus-related phenomena that impair performance. We describe these phenomena, and present a new I/O performance model that accurately predicts the average bandwidth achieved by a heavy workload of random reads from disks on a SCSI bus. This model, although relatively simple, predicts performance on several platforms to within 12% for I/O sizes in the range 16-128 KB. We describe a technique to improve the I/O bandwidth by 10-20% for random-access workloads that have large I/Os and high concurrency. This technique increases the percentage of disk head positioning time that is overlapped with data transfers, and increases the percentage of transfers that occur at bus bandwidth, rather than at disk-head bandwidth.
Task assignment in a distributed system (extended abstract)
Authors: Crovella Mark E. , Harchol-Balter Mor , Murta Cristina D.
Published: January 2007

We consider the problem of task assignment in a distributed system (such as a distributed Web server) in which task sizes are drawn from a heavy-tailed distribution. Many task assignment algorithms are based on the heuristic that balancing the load at the server hosts will result in optimal performance. We show this conventional wisdom is less true when the task size distribution is heavy-tailed (as is the case for Web file sizes). We introduce a new task assignment policy, called Size Interval Task Assignment with Variable Load (SITA-V). SITA-V purposely operates the server hosts at different loads, and directs smaller tasks to the lighter-loaded hosts. The result is that SITA-V provably decreases the mean task slowdown by significant factors (up to 1000 or more) where the more heavy-tailed the workload, the greater the improvement factor. We evaluate the tradeoff between improvement in slowdown and increase in waiting time in a system using SITA-V, and show conditions under which SITA-V represents a particularly appealing policy.