We ask if the ubiquity of WiFi can be leveraged to provide cheap connectivity from moving vehicles for common applications such as Web browsing and VoIP. Driven by this question, we conduct a study of connection quality available to vehicular WiFi clients based on measurements from testbeds in two different cities. We find that current WiFi handoff methods, in which clients communicate with one basestation at a time, lead to frequent disruptions in connectivity. We also find that clients can overcome many disruptions by communicating with multiple basestations simultaneously. These findings lead us to develop ViFi, a protocol that opportunistically exploits basestation diversity to minimize disruptions and support interactive applications for mobile clients. ViFi uses a decentralized and lightweight probabilistic algorithm for coordination between participating basestations. Our evaluation using a two-month long deployment and trace-driven simulations shows that its link-layer performance comes close to an ideal diversity-based protocol. Using two applications, VoIP and short TCP transfers, we show that the link layer performance improvement translates to better application performance. In our deployment, ViFi doubles the number of successful short TCP transfers and doubles the length of disruption-free VoIP sessions compared to an existing WiFi-style handoff protocol.

Using measurements from VanLAN, a modest-size testbed that we have deployed, we analyze the fundamental characteristics of WiFi-based connectivity between basestations and vehicles in urban settings. Our results uncover a more complex picture than previous work which was conducted in more benign settings. The interval between a vehicle coming into and going out of range of a basestation is often marred by intermittent periods of very poor connectivity. These "gray periods" are hard to reliably predict because their arrival is not signaled by metrics such as signal strength, loss rate, speed or distance from the basestation. At the same time, they also do not consistently occur at the same spot. Our analysis suggests that gray periods are not caused by the motion of the vehicle per se but by the variability in the urban radio environment combined with the vehicle traversing locations that are poorly covered by the basestation. We also find that knowledge of past connectivity can be used to identify regions where gray periods are more likely to occur as well as regions where the vehicle is likely to experience good connectivit.

We present Wit, a non-intrusive tool that builds on passive monitoring to analyze the detailed MAC-level behavior of operational wireless networks. Wit uses three processing steps to construct an enhanced trace of system activity. First, a robust merging procedure combines the necessarily incomplete views from multiple, independent monitors into a single, more complete trace of wireless activity. Next, a novel inference engine based on formal language methods reconstructs packets that were not captured by any monitor and determines whether each packet was received by its destination. Finally, Wit derives network performance measures from this enhanced trace; we show how to estimate the number of stations competing for the medium. We assess Wit with a mix of real traces and simulation tests. We find that merging and inference both significantly enhance the originally captured trace. We apply Wit to multi-monitor traces from a live network to show how it facilitates 802.11 MAC analyses that would otherwise be difficult or rely on less accurate heuristics.

We present practical models for the physical layer behaviors of packet reception and carrier sense with interference in static wireless networks. These models use measurements of a real network rather than abstract RF propagation models as the basis for accuracy in complex environments. Seeding our models requires N trials in an N node network, in which each sender transmits in turn and receivers measure RSSI values and packet counts, both of which are easily obtainable. The models then predict packet delivery and throughput in the same network for different sets of transmitters with the same node placements. We evaluate our models for the base case of two senders that broadcast packets simultaneously. We find that they are effective at predicting when there will be significant interference effects. Across many predictions, we obtain an RMS error for 802.11a and 802.11b of a half and a third, respectively, of a measurement-based model that ignores interference.

The availability of a P2P service is a function of the individual peers' availabilities, and it is often desirable to estimate how available a particular P2P service will be given the availability of its peers. Prior work in this area has widely used the fraction of time the average peer is available as the basis for this estimate. It is shown that this approach has serious drawbacks. The authors developed a different measure, which is called presence-based availability, which takes into account the availability of the individual peers. Using traces of live P2P systems taken from the literature, the authors demonstrated that presence-based availability is a more reliable indicator of potential performance than prior methods. It is shown that this metrics successfully estimate the availability of a P2P file-sharing system. Then, using presence-based measures to make a better estimate of a parameter in a highly-available system, we achieve a 75% decrease in resource usage relative to an existing technique relying on traditional metrics.

Peer-to-peer (P2P) file sharing accounts for an astonishing volume of current Internet traffic. This paper probes deeply into modern P2P file sharing systems and the forces that drive them. By doing so, we seek to increase our understanding of P2P file sharing workloads and their implications for future multimedia workloads. Our research uses a three-tiered approach. First, we analyze a 200-day trace of over 20 terabytes of Kazaa P2P traffic collected at the University of Washington. Second, we develop a model of multimedia workloads that lets us isolate, vary, and explore the impact of key system parameters. Our model, which we parameterize with statistics from our trace, lets us confirm various hypotheses about file-sharing behavior observed in the trace. Third, we explore the potential impact of locality-awareness in Kazaa.Our results reveal dramatic differences between P2P file sharing and Web traffic. For example, we show how the immutability of Kazaa's multimedia objects leads clients to fetch objects at most once; in contrast, a World-Wide Web client may fetch a popular page (e.g., CNN or Google) thousands of times. Moreover, we demonstrate that: (1) this "fetch-at-most-once" behavior causes the Kazaa popularity distribution to deviate substantially from Zipf curves we see for the Web, and (2) this deviation has significant implications for the performance of multimedia file-sharing systems. Unlike the Web, whose workload is driven by document change, we demonstrate that clients' fetch-at-most-once behavior, the creation of new objects, and the addition of new clients to the system are the primary forces that drive multimedia workloads such as Kazaa. We also show that there is substantial untapped locality in the Kazaa workload. Finally, we quantify the potential bandwidth savings that locality-aware P2P file-sharing architectures would achieve.

Sloop-SMOK is a toolkit designed to improve the student design experience in a machine organization course taken by undergraduates in their first year as computer science majors. Students in this course have had some programming experience, and may have taken a one-quarter digital design course. Before Sloop-SMOK, assignments in this course were typically assembly language program implementations of functions related to architecture. The major goals in building Sloop-SMOK were to improve the relevance of homework assignments to machine organization and to emphasize some fundamental concepts of modern processors not easily addressed previously.Sloop-SMOK has two components. The Sloop is a machine architecture designed to allow implementation of a modern version of the 6502, the processor used in one of the early Atari game stations. The Sloop defines a RISC ISA and a set of on-the-fly translations from the original 6502 CISC ISA into Sloop instructions. The Sloop Machine Organization Kit (SMOK) is a general-purpose software machine organization simulator. The components of a SMOK model are at the level of detail found in typical machine organization texts: ALUs, register files, logic gates, and the like. SMOK provides a graphical interface to construct and debug models.As homework assignments, students use SMOK to build Sloop machines that successfully run most original 6502 games. Extensions to SMOK provide specific help with these Sloop models. Of particular importance is support for debugging: SMOK, when used to build a Sloop machine, runs a software 6502 simulator and compares the behavior of the student's Sloop machine against the simulator on a per-memory-operation basis. This feature simplifies debugging of Sloop machine organization by raising an error at the earliest cycle at which the student's machine is known to deviate from correct behavior.Sloop-SMOK, including downloadable software, documentation, and course assignments, is available at http://www.cs.washington.edu/software/SMOK

We describe DDDDRRaW, a prototype toolkit for distributed real-time rendering on commodity clusters. In constrast to most work on cluster computing, DDDDRRaW supports a repeated, low-latency computation, the drawing of frames which must take place on a time scale of 30-100 ms. DDDDRRaW employs image layer decomposition, a rendering-specific work partitioning algorithm described and evaluated using simulation. In this paper we address implementation issues. In particular, one important issue we explore is how to exploit the potential parallelism afforded by the multiple hardware resources of each node: the CPU, the network adapter and the video card. We evaluate DDDDRRaW's live performance on two small workstation clusters representing different points in the technology spectrum. Our results show that DDDDRRaW effectively exploits cluster resources to improve real-time rendering performance and should scale well to moderately sized clusters.

Two recent techniques for multicast or broadcast delivery of streaming media can provide immediate service to each client request, yet achieve considerable client stream sharing which leads to significant server and network bandwidth savings. The paper considers: 1) how well these recently proposed techniques perform relative to each other and 2) whether there are new practical delivery techniques that can achieve better bandwidth savings than the previous techniques over a wide range of client request rates. The principal results are as follows: First, the recent partitioned dynamic skyscraper technique is adapted to provide immediate service to each client request more simply and directly than the original dynamic skyscraper method. Second, at moderate to high client request rates, the dynamic skyscraper method has required server bandwidth that is significantly lower than the recent optimized stream tapping/patching/controlled multicast technique. Third, the minimum required server bandwidth for any delivery technique that provides immediate real-time delivery to clients increases logarithmically (with constant factor equal to one) as a function of the client request arrival rate. Furthermore, it is (theoretically) possible to achieve very close to the minimum required server bandwidth if client receive bandwidth is equal to two times the data streaming rate and client storage capacity is sufficient for buffering data from shared streams. Finally, we propose a new practical delivery technique, called hierarchical multicast stream merging (HMSM), which has a required server bandwidth that is lower than the partitioned dynamic skyscraper and is reasonably close to the minimum achievable required server bandwidth over a wide range of client request rates.

We propose a novel work partitioning technique, image layer decomposition (ILD), designed specifically to support distributed real-time rendering on commodity clusters. ILD has several advantages over previous partitioning algorithms for our targeted environment, including its compatibility with the use of hardware graphics accelerators, decoupling of communication bandwidth requirement from scene complexity, and reduced communication bandwidth growth as the system size increases. Furthermore, ILD tries to optimize the rendering of a sequence of frames (of an interactive application) instead of only individual frames. We simulate ILD using traces taken from a VRML viewer Our results show that ILD can be expected to work well up to moderately sized clusters and to outperform sort-last, a common partitioning approach, because of its smaller communication bandwidth requirement.

The simplest video-on-demand (VOD) delivery policy is to allocate a new media delivery stream to each client request when it arrives. This policy has the desirable properties of “immediate service ” (there is minimal latency between the client request and

We consider the problem of scheduling the rendering component of 3D multimedia applications on a cluster of workstations connected via a local area network. Our goal is to meet a periodic real-time constraint.In abstract terms, the problem we address is how best to schedule tasks with unpredictable service times on distinct processing nodes so as to meet a real-time deadline, given that all communication among nodes entails some (possibly large) overhead. We consider two distinct classes of schemes, static, in which task reallocations are scheduled to occur at specific times, and dynamic, in which reallocations are triggered by some processor going idle. For both classes we further examine both global reassignments, in which all nodes are rescheduled at a rescheduling moment, and local reassignments, in which only a subset of the nodes engage in rescheduling at any one time.We show that global dynamic policies work best over a range of parameterizations appropriate to such systems. We introduce a new policy, Dynamic with Shadowing, that places a small number of tasks in the schedules of multiple workstations to reduce the amount of communication required to complete the schedule. This policy is shown to dominate the other alternatives considered over most of the parameter space.

We consider the problem of multiprocessor scheduling of jobs whose memory requirements place lower bounds on the fraction of the machine required in order to execute. We address three primary questions in this work:1. How can a parallel machine be multiprogrammed with minimal overhead when jobs have minimum memory requirements?2. To what extent does the inability of an application to repartition its workload during runtime affect the choice of processor allocation policy?3. How rigid should the system be in attempting to provide equal resource allocation to each runnable job in order to minimize average response time?This work is applicable both to parallel machines and to networks of workstations supporting parallel applications.

When multiple jobs compete for processing resources on a parallel computer, the operating system kernel's processor allocation policy determines how many and which processors to allocate to each. In this paper we investigate the issues involved in constructing a processor allocation policy for large scale, message-passing parallel computers supporting a scientific workload.

When the inter-iteration dependency pattern of the iterations of a loop cannot be determined statically, compile time parallelization of the loop is not possible. In these cases, runtime parallelization [8] is the only alternative. The idea is to transform the loop into two code fragements: the inspector and the executor. When the program is run, the inspector examines the iteration dependencies and constructs a parallel schedule. The executor subsequently uses that schedule to carry out the actual computation in parallel.

Parallel computing is increasingly important in the solution of large-scale numerical problems. The difficulty of efficiently hand-coding parallelism, and the limitations of parallelizing compilers, have nonetheless restricted its use by scientific programmers. In this paper we propose a new paradigm,chores, for the run-time support of parallel computing on shared-memory multiprocessors. We consider specifically uniform memory access shared-memory environments, although the chore paradigm should also be appropriate for use within the clusters of a large-scale nonuniform memory access machine. We argue that chore systems attain both the high efficiency of compiler approaches for the common case of data parallelism, and the flexibility and performance of user-level thread approaches for functional parallelism. These benefits are achieved within a single, simple conceptual model that almost entirely relieves the programmer and compiler from concerns of granularity, scheduling, and enforcement of synchronization constraints. Measurements of a prototype implementation demonstrate that the chore model can be supported more efficiently than can traditional approaches to either data or functional parallelism alone.

We propose and evaluate empirically the performance of a dynamic processor-scheduling policy for multiprogrammed shared-memory multiprocessors. The policy is dynamic in that it reallocates processors from one parallel job to another based on the currently realized parallelism of those jobs. The policy is suitable for implementation in production systems in that: We have evaluated our scheduler and compared it to alternatives using a set of prototype implementations running on a Sequent Symmetry multiprocessor. Using a number of parallel applications with distinct qualitative behaviors, we have both evaluated the policies according to the major criterion of overall performance and examined a number of more general policy issues, including the advantage of “space sharing” over “time sharing” the processors of a multiprocessor, and the importance of cooperation between the kernel and the application in reallocating processors between jobs. We have also compared the policies according to other criteia important in real implementations, in particular, fairness and respone time to short, sequential requests. We conclude that a combination of performance and implementation considerations makes a compelling case for our dynamic scheduling policy.

The authors analyze three approaches to scheduling mixed batch and interactive workloads on a supercomputer: (i) fixed partition, in which memory resources are statically allocated between the workloads: (ii) no partition, in which the interactive workload preempts resources as needed from the batch workload, and (iii) no partition with grouped admission, in which the interactive workload preempts resources only when the number of waiting interactive jobs reaches a threshold value. The authors also investigate the potential benefits of using virtual memory to perform the automatic overlay of jobs too large to fit in the amount of real memory instantaneously available to them. Using analytic tools, they compare the different policies according to the average speedup achieved by the batch workload given that a mean interactive job response time objective must be met by each. They show that, under a wide variety of conditions, fixed partition performs better than the other policies.>

In a shared memory multiprocessor with caches, executing tasks develop "affinity" to processors by filling their caches with data and instructions during execution. A scheduling policy that ignores this affinity may waste processing power by causing excessive cache refilling.Our work focuses on quantifying the effect of processor reallocation on the performance of various parallel applications multiprogrammed on a shared memory multiprocessor, and on evaluating how the magnitude of this cost affects the choice of scheduling policy.We first identify the components of application response time, including processor reallocation costs. Next, we measure the impact of reallocation on the cache behavior of several parallel applications executing on a Sequent Symmetry multiprocessor. We also measure, the performance of these applications under a number of alternative allocation policies. These experiments lead us to conclude that on current machines processor affinity has only a very weak influence on the choice of scheduling discipline, and that the benefits of frequent processor reallocation (in response to the changing parallelism of jobs) outweigh the penalties imposed by such reallocation. Finally, we use this experimental data to parameterize a simple analytic model, allowing us to evaluate the effect of processor affinity on future machines, those containing faster processors and larger caches.

Spinning, or busy waiting, is commonly employed in parallel processors when threads of execution must wait for some event, such as synchronization with another thread. Because spinning is purely overhead, it is detrimental to both user response time and system throughput. The effects of two environmental factors, multiprogramming and data-dependent execution times, on spinning are discussed, and it is shown how the choice of scheduling discipline can be used to reduce the amount of spinning in each case.>

The demands on a heterogeneous distributed file system are outlined, and the design and implementation of a prototype to meet these demands are described. This prototype, the heterogeneous computer systems file system (HFS), provides a network-wide file system supporting a simple record-oriented file model. Through this standard file model, the HFS provides global access to files stored locally in many different file types. The HFS is implemented as a set of HFS servers, one running on each participating host. Each HFS server extends its host's local file system by fielding remote requests for files stored locally, translating those requests into the appropriate local file system calls, and returning any information so obtained. This prototype HFS implementation is used on a network composed of VAX systems running Unix, Sun systems running 4.2BSD Unix, and Xerox Dandelions running XDE.>

Existing work indicates that the commonly used “single queue of runnable tasks” approach to scheduling shared memory multiprocessors can perform very poorly in a multiprogrammed parallel processing environment. A more promising approach is the class of “two-level schedulers” in which the operating system deals solely with allocating processors to jobs while the individual jobs themselves perform task dispatching on those processors.

The authors take efficient kernel-level support as a given, and study the performance implications of design alternatives one level up-in the stubs, which insulate the client and server from details about network communication. These alternatives represent a collection of approaches to achieving standard remote procedure call of semantics. Consideration is given to the performance implications of compiled vs. interpreted stubs, procedural vs. inline code for moving data to/from packet buffers, block copy vs. individual data item copy moving data to/from packet buffers, and the presence or absence of byte swapping.>

The problem of sharing jobs among a set of parallel queues is discussed. The system is heterogeneous in the sense that different servers may have different speeds. Socially optimal policies that minimize the mean response time of all jobs ar of interest. Using semi-Markov decision processes, it is shown that an optimal policy that uses the instantaneous queue length independent of system utilization does not exist. Rather, the optimal decision of assigning a job to a server depends on the workload intensity. At light loads, the optimal policy tends to assign most jobs to fast servers. At heavy loads, slower servers are used to offload fast ones. Simulation results indicate that a simple heuristic, i.e., a generalization of the optimal policy for homogeneous systems derived from the analytic results, yields substantial performance improvement compared with no load sharing and outperforms the join-shortest-queue policy.>

As VLSI technology continues to improve, circuit area is gradually being replaced by pin restrictions as the limiting factor in design. Thus, it is reasonable to anticipate that on-chip memory will become increasingly inexpensive since it is a simple, regular structure than can easily take advantage of higher densities.

The tradeoff between speedup and efficiency that is inherent to a software system is investigated. The extent to which this tradeoff is determined by the average parallelism of the software system, as contrasted with other, more detailed, characterizations, is shown. The extent to which both speedup and efficiency can simultaneously be poor is bound: it is shown that for any software system and any number of processors, the sum of the average processor utilization (i.e. efficiency) and the attained fraction of the maximum possible speedup must exceed one. Bounds are given on speedup and efficiency, and on the incremental benefit and cost of allocating additional processors. An explicit formulation, as well as bounds, are given for the location of the knee of the execution time-efficiency profile, where the benefit per unit cost is maximized.>

A family of dynamic cache-consistency-protocols for shared-bus multiprocessor systems is considered. A modeling approach, based on the specification and the iterative solution of sets of equations that express the mean values of interesting performance measures in terms of the mean values of certain model inputs, is presented. The equations are intuitive, in the sense that each can be explained simply in terms of the mechanics of the architecture being modeled. The solution technique is extremely efficient, requiring on the order of one second of CPU time for systems of arbitrary size. This makes it possible to explore a large design space quickly and interactively. The results are essentially as accurate as those of the previously existing techniques, which took hours on I-MIPS processors.>

Load sharing in a distributed system is the process of transparently sharing workload among the nodes in the system to achieve improved performance. In non-migratory load sharing, jobs may not be transferred once they have commenced execution. In load sharing with migration, on the other hand, jobs in execution may be interrupted, moved to other nodes, and then resumed.

A prototype implementation has been built as part of the Heterogeneous Computer Systems project at the University of Washington. This service supports RPC binding and other applications in our heterogeneous environment. Measurements of the performance of this prototype show that it is close to that of the underlying name services, due largely to the use of specialized caching techniques.

This paper studies the performance of single-user workstations that access files remotely over a local area network. From the environmental, economic, and administrative points of view, workstations that are diskless or that have limited secondary storage are desirable at the present time. Even with changing technology, access to shared data will continue to be important. It is likely that some performance penalty must be paid for remote rather than local file access. Our objectives are to assess this penalty and to explore a number of design alternatives that can serve to minimize it. Our approach is to use the results of measurement experiments to parameterize queuing network performance models. These models then are used to assess performance under load and to evahrate design alternatives. The major conclusions of our study are: (1) A system of diskless workstations with a shared file server can have satisfactory performance. By this, we mean performance comparable to that of a local disk in the lightly loaded case, and the ability to support substantial numbers of client workstations without significant degradation. As with any shared facility, good design is necessary to minimize queuing delays under high load. (2) The key to efficiency is protocols that allow volume transfers at every interface (e.g., between client and server, and between disk and memory at the server) and at every level (e.g., between client and server at the level of logical request/response and at the level of local area network packet size). However, the benefits of volume transfers are limited to moderate sizes (8-16 kbytes) by several factors. (3) From a performance point of view, augmenting the capabilities of the shared file server may be more cost effective than augmenting the capabilities of the client workstations. (4) Network contention should not be a performance problem for a lo-Mbit network and 100 active workstations in a software development environment.

Rather than proposing a specific load sharing policy for implementation, the authors address the more fundamental question of the appropriate level of complexity for load sharing policies. It is shown that extremely simple adaptive load sharing policies, which collect very small amounts of system state information and which use this information in very simple ways, yield dramatic performance improvements. These policies in fact yield performance close to that expected from more complex policies whose viability is questionable. It is concluded that simple policies offer the greatest promise in practice, because of their combination of nearly optimal performance and inherent stability.

One goal of locally distributed systems is to facilitate resource sharing. Most current locally distributed systems, however, share primarily data, data storage devices, and output devices; there is little sharing of computational resources. Load sharing is the process of sharing computational resources by transparently distributing the system workload. System performance can be improved by transferring work from nodes that are heavily loaded to nodes that are lightly loaded.

Queueing network performance modelling technology has made tremendous strides in recent years. Two of the most important developments in facilitating the modelling of large and complex systems are hierarchical modelling, in which a single load dependent server is used as a surrogate for a subsystem, and approximate mean value analysis, in which reliable approximate solutions of separable models are efficiently obtained. Unfortunately, there has been no successful marriage of these two developments; that is, existing algorithms for approximate mean value analysis do not accommodate load dependent servers reliably.

There are two basic representations of workload populations in load independent, separable queueing network models. These correspond to the notions of open and closed classes, an open class being one in which customers may arrive and depart the model, and a closed class being one in which the number of customers is fixed. This paper examines the effect on mean system performance measures of the workload representation chosen. Open and closed representations are compared under the equivalency constraints that they result in identical system throughput or mean system population level for the class being considered. It is shown formally for a limited class of networks that the open representation results in larger system response times than equivalent closed representations, and that one of the closed representations results in the smallest system response time of those considered. Extensive numerical results show for a more general class of models that there is a strict ordering (in terms of system response time) of the natural class representations considered.

This is a summary of a tutorial presented during the conference discussing a number of approaches to representing disk I/O subsystems in analytic models of computer systems.

Applications of queueing network models to computer system performance prediction typically involve the computation of their equilibrium solution. When numerous alternative systems are to be examined and the numbers of devices and customers are large, however, the expense of computing the exact solutions may not be warranted by the accuracy required. In such situations, it is desirable to be able to obtain bounds on the system solution with very little computation. Asymptotic bound analysis (ABA) is one technique for obtaining such bounds. In this paper, we introduce another bounding technique, called balanced job bounds (BJB), which is based on the analysis of systems in which all devices are equally utilized. These bounds are tighter than ABA bounds in many cases, but they are based on more restrictive assumptions (namely, those that lead to separable queueing network models).

Because it is more intuitively understandable than the previously existing convolution algorithms, Mean Value Analysis (MVA) has gained great popularity as an exact solution technique for separable queueing networks. However, the derivations of MVA presented to date apply only to closed queueing network models. Additionally, the problem of the storage requirement of MVA has not been dealt with satisfactorily. In this paper we address both these problems, presenting MVA solutions for open and mixed load independent networks, and a storage maintenance technique that we postulate is the minimum possible of any “reasonable” MVA technique.

In this paper we present a convolution algorithm for the full class of closed, separable queueing networks. In particular, the algorithm represents an alternative method to those already known for the solution of networks with class changes, and is the first efficient algorithm to deal with Lam-type networks [11].