A cluster-based server consists of a front-end dispatcher and multiple back-end servers. The dispatcher receives incoming jobs, and then decides how to assign them to back-end servers, which in turn serve the jobs according to some discipline. Cluster-based servers have been broadly deployed as they combine good performance with low cost. Several assignment policies have been proposed for cluster-based servers, most of which aim to balance the load among back-end servers. There are two main strategies for load balancing: The first strategy aims at balancing the amount of work at back-end servers, while the second strategy aims at balancing the number of jobs assigned to back-end servers. Example of policies using these strategies are JSQ (join shortest queue) and LC (least connected), respectively. We propose a policy, called LC*, which combines the two aforementioned strategies. The paper shows experimentally that when preemption is admitted (i.e. jobs are executed concurrently by back-end servers), LC substantially outperforms both JSQ and LC. This improved performance is achieved by using only information readily available to the dispatcher, and therefore LC* is a practical policy in regards to implementation.

Cluster-based server architectures combine good performance and low cost, and are commonly used for applications that generate heavy loads. Essentially, a cluster-based server consists of a front-end dispatcher and several back-end servers. The dispatcher receives incoming requests, and then assigns them to back-end servers, which are responsible for request processing. The many benefits of cluster-based servers make them a good choice for e-commerce applications as well. However, applying this type of architecture to e-commerce applications is hindered by the fact that e-commerce clusters have additional task verifying that requests comply with contract terms. The problem is further complicated by the fact that contract terms may be expressed as functions of dynamic, mutable states. The problem addressed in this paper is the effective assignment of e-commerce requests, such that the load is balanced among back-end servers and request validation is efficient. To this end, we propose a policy called TDA (type dependent assignment), which takes account of the type of contracts. Under TDA, stateless contracts are replicated on all back-end servers. In contrast, a stateful contract, C, is preassigned to a designated back-end server, called the base of C, which is responsible for maintaining the state of C. The operations of TDA may be broadly outlined as follows. A request governed by a stateless contract is assigned to the least loaded server. In contrast, a request governed by a stateful contract is assigned to its base, if the base is not overloaded, and to the least loaded server, otherwise.

Abstract In collaborative information finding systems, evaluations provided by users assist other users with similar needs. This article examines the problem of getting users to provide evaluations, thus overcoming the so‐called “free‐riding” behavior of users. Free riders are those who use the information provided by others without contributing evaluations of their own. This article reports on an experiment conducted using the “AntWorld,” system, a collaborative information finding system for the Internet, to explore the effect of added motivation on users' behavior. The findings suggest that for the system to be effective, users must be motivated either by the environment, or by incentives within the system. The findings suggest that relatively inexpensive extrinsic motivators can produce modest but significant increases in cooperative behavior.

No abstract available.

This paper describes a general methodology for constructing accurate source models of long sequences (full-length movies) of full-motion compressed VBR (variable bit rate) video, directly from empirical data sets of observed bit rate (frame size) records. The main idea is to first cluster scenes into classes and use TES (transform-expand-sample) processes to carefully model their duration and bit rate processes, and then modulate these scene class models by a Markov-renewal process that governs scene transitions. The resulting model is a Markov-renewal-modulated TES (MRMT) process. The fidelity criteria imposed are relatively stringent in that they call for the simultaneous capture of empirical histograms and autocorrelation functions, as well as the qualitative appearance of the empirical data, including burstiness. To illustrate the methodology, the paper provides a detailed description of the modeling procedure, using a JPEG-like coding trace of the "Star Wars" movie as a working example. The resulting MRMT model was validated by comparing its simulation-based statistics to their empirical counterparts, and by a performance study of the corresponding loss rates for various buffer sizes. The results support the efficacy of the modeling methodology and suggest that suites of realistic and compact source models can be developed for other types of movies under a variety of coding schemes. These may be used to drive realistic Monte Carlo simulations of broadband telecommunications networks.

One limitation on the operating speed of electronic circuits is the rate at which the packaging can dissipate heat. In CMOS technology, the heat generated by a processor is approximately proportional to its clock rate. The paper examines the idea of using a variable speed processor (VSP) that can be operated at a high clock speed, and then slowed down to a lower speed before heat accumulation destroys the circuit. Under a workload consisting of bursts of work alternating with idle periods (corresponding to cache misses or other delays), this results in a higher average operating speed. The paper shows the optimality of a bang bang control for the clock rate. It also examines an easier to implement policy that estimates the junction temperature through an upper bound, and uses this to control the clock rate. Closed form expressions are derived for the mean rate of instructions executed by a VSP using each control method. Numerical studies show that both policies give substantial improvements in performance over a single speed processor. Furthermore, the studies suggest that a VSP with a maximum clock rate of 2-4 times that of the single speed processor would suffice to obtain the bulk of the performance improvement. In many cases, the average throughput gain is on the order of 40-60%, without exceeding thermal limits.

Network traffic measurement and workload characterization are key steps in the workload modeling process. Much has been learned through network measurement and workload modeling in the last ten years, but new challenges are now at the forefront: measuring network traffic in the Internet environment, understanding the implications of network traffic structure (e.g., self-similarity, autocorrelation, long range dependence), and accurate modeling of network traffic workloads for high speed network environments.This "hot topic" session brings together three prominent speakers to address each of these topics, in turn.

This paper studies the spectral properties of a class of stochastic sequences generated by basic TES (Transform-Expand-Sample) methods, as well as transformed TES sequences. A TES sequence is obtained as a marginally uniform process from an autoregressive scheme with modulo-1 reduction, followed by additional transformations. We derive formulas for the spectral density function and the spectral distribution function which are suitable for efficient numerical computation. A set of examples is calculated and exhibited for TES processes with uniform and exponential marginals. The results contribute to the understanding of TES sequences as models of autocorrelated sequences, particularly in a Monte Carlo simulation context. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The letter considers modeling methodologies of variable bit-rate (VBR) video sources for performance evaluation of integrated networks. The authors consider an example in which compressed H.261 standard VBR video is transmitted over a local area network carrying both video and data. A group-of-block (GOB) level source model has been constructed using TES (transform-expand-sample)-a new general methodology for generating stationary autocorrelated time series, which can simultaneously capture a prescribed marginal distribution and autocorrelation function. The TES model is used to drive CSMA/CD network simulations for a performance evaluation study. Numerical comparisons with a conventional autoregressive (AR) modeling approach are given.>

A variable-bit-rate (VBR) MPEG video compression encoder is introduced, and the performance of a statistically multiplexed asynchronous transfer mode (ATM) network supporting a number of such VBR video sources is evaluated. Bit-rate characteristics obtained from a detailed simulation are provided for a VBR MPEG encoder for CCIR601 video (operating in the 5-10 Mb/s regime) appropriate for medium-quality multimedia or broadcasting applications. The results presented include bit-rate traces and signal-to-noise-ratio data for typical test sequences, along with summary statistics such as the marginal distribution of frame rate. Data from a study of statistical multiplexing on an ATM network are also given. Simulation results for an ATM statistical multiplexer with N>>1 VBR MPEG sources are presented in terms of key performance measures such as cell loss rate and delay versus throughput. The results confirm that ATM channel efficiencies of approximately 80-90% can be obtained at reasonable cell loss rate and delay levels.>

The authors consider modeling methodologies of variable-bit-rate video sources for performance evaluation of integrated networks. They consider an example in which compressed video is transmitted over a local area network carrying both video and data. A new modeling methodology called transform-expand-sample (TES) which is a method for generating autocorrelated variates, is used. TES is a nonparametric method which can accurately capture the histogram and approximate autocorrelation function of any data set. The TES model was used to drive a network simulation for performance measures.>

This paper introduces a class of methods called TES (Transform-Expand-Sample) for generating autocorrelated variates with uniform marginals and Markovian structure. TES methods are readily implemented on a computer and have generation complexity comparable to that of the i.i.d. uniform sequence which they transform to an autocorrelated uniform sequence. For any prescribed correlation coefficient ρ, there is a TES method generating a uniform sequence with the 1-lag autocorrelation ρ, and the resultant autocorrelation is monotonic quadratic in two structural TES parameters. A simulation study reveals that TES methods give rise to autocorrelation functions with monotone decreasing as well as oscillating magnitude, bounded by monotone envelopes. The structural parameters were found to control the “amplitude” and “frequency” of the resultant autocorrelation function. A third parameter can be used to transform a TES sequence into more continuous-looking versions and to control the skewness of sample path cycles. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Sojourn time distributions in queuing networks seldom possess closed-form analytical solutions.When overtaking is permitted, the sojourn times at indlwdual nodes are usually dependent, in which case the attendant distribution is mathematically intractable.In a previous paper the authors proposed a methodology utihzing randomization procedures to approximate sojourn time distributions in arbitrary discrete-state Markovian queuing networks.Th~s paper addresses the computational aspects of the methodology pertaining to implementation.Ways of improving the accuracy ofthe approximated distribution functions are also discussed.