Provisioning computing resources for a web application poses a challenge due to the time-varying nature of the application workload. We consider an environment where a subscriber acquires computing resources from an infrastructure provider to deploy a transactional web application. The objective is to acquire sufficient resources to meet a performance target given by Pr[response time ≤ x] ≥ β. Markov-modulated Poisson process (MMPP) has been shown to effectively model time-varying traffic. It has also been shown that service times can be characterized by a hyper-Erlang (HE) distribution. HE is a special case of the phase-type (PH) distribution. We model the application by an MMPP/PH/1 queue and use analytic results of this model to determine the required capacity to meet a given performance target over an extended period of time. An implementation of the TPC-W benchmark is used to verify the effectiveness of the model. We also investigate the relationship between the required capacity and workload parameters.

Web application traffic has been shown to exhibit burstiness. The traditional model based on Poisson process is unable to capture the burstiness in traffic. On the other hand, the Markov-modulated Poisson process (MMPP) has been successfully used to model bursty traffic in a variety of computing environments. In this paper, we conduct experiments to investigate the effectiveness of MMPP as a traffic model in the context of resource provisioning in web applications. We first extend an available workload generator to produce a synthetic trace of job arrivals with controlled burstiness. We next consider an existing algorithm, as well as a variant of this algorithm, to fit an MMPP to the synthetic trace; each of them is used to obtain values for the MMPP parameters. The effectiveness of MMPP is then evaluated by comparing the performance results through simulation, using as input the synthetic trace and job arrivals generated by the estimated MMPP.

A distributed virtual environment (DVE) is a shared virtual environment where multiple users at their workstations interact with each other over a network. Some of these systems may support a large number of users, for example, multiplayer online games. An important issue is how well the system scales as the number of users increases. In terms of scalability, a promising system architecture is a two-level hierarchical architecture. At the lower level, multiple servers are deployed; each server interacts with its assigned users. At the higher level, the servers ensure that their copies of the virtual environment are as consistent as possible. Although the two-level architecture is believed to have good properties with respect to scalability, not much is known about its performance characteristics. In this paper, we develop a performance model for the two-level architecture and obtain analytic results on the workload experienced by each server. Our results provide valuable insights into the scalability of the architecture. We also investigate the issue of consistency and develop a novel technique to achieve weak consistency among copies of the virtual environment at the various servers. Simulation results on the consistency/scalability trade-off are presented.

Dynamic resource allocation in a server cluster has received much attention in recent years. We have developed heuristic algorithms for autonomic server provisioning for a cluster that executes batch jobs. These jobs have a common, or shared, completion deadline. External factors that may affect the decision to allocate servers are modeled as a time-varying cost function. The provisioning goal is to ensure that all jobs are completed on time while minimizing the total cost of server usage. Two heuristic algorithms which adapt to changing workload are presented. The merit of these algorithms is evaluated by simulation. Our results show that the proposed algorithms can successfully use fewer servers during the high cost period while ensuring that all jobs meet their deadline. They also perform far better than static server allocation

In our deadline-based network resource management framework, each application data unit (ADU) is characterized by a (size, deadline) pair, which can be used to convey the resource and QoS requirements of the ADU. Specifically, the ADU's bandwidth requirement can be implicitly estimated by the ratio: size / (deadline - current time), and the time at which the ADU should be delivered is specified by the deadline. The ADU deadline is mapped onto deadlines at the network layer, which are carried by packets and used by routers for channel scheduling. In an earlier work, we have shown that deadline-based channel scheduling achieves good performance in terms of the percentage of ADUs that are delivered on-time. However, when a network is under heavy load, congestion may occur, and deadline-based scheduling alone may not be sufficient to prevent performance degradation. The level of congestion can be reduced by admission control. In this paper, two application-layer admission control algorithms are developed. The performance of these two algorithms is evaluated by simulation.

An experimental prototype for server selection using an independent brokerage service is described This prototype is composed of four main components: instrumented Apache Web servers, monitoring agents, a QoS broker, and client emulator. The role of the broker is to distribute client sessions to a set of replicated servers. It is designed to support different types of selection policies and hay the capability to collect performance data from the servers. We include in our description the technique used to instrument Apache servers and our implementation of the server-broker protocol that we have developed. Our implementation of the QoS broker and the technique used to collect data for the performance parameters of interest are also described. We use our prototype to study the performance of server selection algorithms under realistic conditions. The experimental environment and an analysis of the experimental results are presented.

The use of deadline based channel scheduling in support of real time delivery of application data units (ADU's) is investigated. Of interest is priority scheduling where a packet with a smaller ratio of delivery deadline over number of hops to destination is given a higher priority. It has been shown that a variant of this scheduling algorithm, based on head-of-the-line priority, is efficient and effective in supporting real time delivery of ADU's. In this variant, packets with a ratio smaller than or equal to a given threshold are sent to the higher priority queue. We first present a technique to select this threshold dynamically. The effectiveness of our technique is evaluated by simulation. We then study the performance of deadline based channel scheduling for large networks, with multiple autonomous systems. For this case, accurate information on number of hops to destination may not be available. A technique to estimate this distance metric is presented. The effectiveness of our algorithm with this estimated distance metric is evaluated. In addition, we study the performance of a multi-service scenario where only a fraction of the routers deploy deadline based channel scheduling.

A novel approach to supporting real time applications in packet-switched networks is proposed. The key element of this approach is the use of a tuple (size, deadline) to characterize the performance requirements of a document. This tuple is mapped to deadline information at the network layer, which is carried in packets and used by routers for channel scheduling purposes. A new deadline based scheduling algorithm is developed. Simulation results show that this algorithm is superior to FCFS (first come first served) with respect to the percentage of documents that are delivered on time. Our scheduling algorithm is also efficient as far as implementation is concerned.

Technology for local ATM is currently being offered in a number of devices, such as routers, switches, and switching hubs. These devices provide the capability for an ATM switched internetwork. In general, a switched internetwork consists of an ATM backbone and a number of hubs. The hubs, by providing ATM adaptation functionality, serve as access points to the ATM backbone for servers and clients. The objective of our study is to evaluate alternative strategies for migrating towards an ATM switched internetwork. Our investigation is based on a local area network providing interconnection for a group of clients and servers in a campus environment. A number of different configurations may, at various stages of migration, comprise the interconnection media for this local area network. The network components that are considered in this migration process are Ethernets, both shared and dedicated, multiplexers, hubs, ATM switches, and ATM-equipped end devices. A simulation model is developed to study the performance of the different configurations. Simulation results for end-to-end delay and loss are presented for each alternative configuration.

The distributed queue dual bus (DQDB) protocol, which has been specified by the IEEE 802.6 as the metropolitan area networks (MANs) standard, has an undesirable feature that busy slots that have been already received (i.e. read) continue to propagate downstream unnecessarily. The use of special nodes, known as erasure nodes, allows conversion of read slots to empty, so that downstream nodes may reuse these slots. This should result in an increase of the total throughput of the network. In the paper, the authors introduce and evaluate the performance of an erasure node algorithm. The algorithm keeps track of past activities on both buses to effectively balance the slot erasure and the request cancellation functions. They show that this algorithm possesses a number of features which make it superior to existing algorithms.>

With the availability of high-speed local-area networks, file migration becomes an attractive option in a distributed file system. However, certain limitations may exist which restrict the movement of files. One such limitation is that storage space is finite and thus, storage sites (file servers) can only store a limited number of files. We use simulation to show that for a homogeneous distributed file system which transfers whole files, migrating files from congested to uncongested storage sites can result in significant performance gains over a system without file migration even in the case of finite storage. Our file migration policy is based on an instantaneous performance gain analysis: a file is migrated only if it leads to a decrease in the overall response time of the file requests currently in the system. Our results indicate that as the system load or coefficient of variation of the file request interarrival times increase, so does the percentage improvement of our file migration policy over a system without file migration. The degradation in performance caused by limited storage space is only significant when the storage restrictions are extreme.>

A network model is developed for studying the effect of multiplexing and switching on broadband network performance. Emphasis is placed on the queuing behavior in the network and the impact of multiplexing and switching on the burstiness of the various traffic streams. The three parameters commonly used to characterize traffic (peak bit rate, mean bit rate, and mean burst length) are also considered, and the dependence of the queuing behavior on these parameters is investigated. The performance of three congestion control schemes based on the leaky bucket algorithm is evaluated. The results provide insight into how call acceptance, bandwidth allocation, and bandwidth enforcement should be implemented in a broadband integrated services digital network (BISDN).>

Distributed-queue multiple-access (DQMA) and cyclic-reservation multiple-access (CRMA) access schemes for gigabit-per-second local and metropolitan area networks are described. These schemes are based on a slotted unidirectional bus structure, with both folded and dual-bus configurations. Like the distributed-queue dual-bus (DQDB) scheme, both the DQMA and the CRMA access schemes achieve full throughput independent of network speed and distance. They have two significant advantages over DQDB. They provide throughput fairness even at high speeds and large distances, where DQDB exhibits dramatic unfairness, and, by allowing reservation of multiple consecutive slots, they make segment labeling unnecessary and facilitate packet reassembly significantly.>

The authors consider a videotex system architecture where user requests are processed by a service computer, and the requested information pages are broadcast to all users. Due to the large volume of information that is typically available, a secondary storage device, such as a disk, is used to hold the database. However, a small fraction of the information pages may be kept in main memory. A detailed simulation model is used to study the performance of this system architecture. Features such as scheduling page broadcasts, memory management, and disk scheduling are represented explicitly in the model. Simulation results are presented to show the response-time performance of various memory-management and disk scheduling strategies.>

The issue of routing in interconnected local area networks (LAN's) is considered. Of particular interest is Source routing where the source station specifies, in an inter-LAN frame, the complete path traversed by that frame. In source routing, a mechanism is needed for the source station to determine a path to any given destination. A pathfinding algorithm has been proposed by Sy, Pitt, and Donnan. In this paper, we evaluate the performance of that algorithm using a simulation model of interconnected token rings. Our evaluation is based on a connection-oriented environment and the assumption that the pathfinding algorithm is used each time a new connection is established. Our results indicate that the algorithm selects paths with good delay and throughput performance for the new connection. As to the existing connections, the algorithm yields good throughput behavior, but may not perform well as far as delay is concerned.

Teletext is a one-way information delivery system where pages of information are broadcast to all users in a continuous manner. System response time is an important consideration in the design of teletext systems. One factor contributing to response time is the order in which pages are transmitted. In this paper, we formulate the problem of determining the sequence of page transmissions as a Markovian decision process. Using this formulation we show that, from a response time point of view, a cyclic order of page transmissions is optimal. We also describe two algorithms for designing a teletext broadcast cycle.

Videotex is an interactive information system which provides a variety of services to its users. Examples of such services are information retrieval, software distribution, transaction processing, and message handling. An important aspect of the quality of service experienced by a videotex user is the response time. We consider the use of mixed individual/broadcast delivery to enhance the response time performance. Broadcast delivery is attractive for information retrieval applications where several users may be requesting the same information page, and a single broadcast of this page will satisfy all requests simultaneously. Individual response, however, is required for transaction-oriented services and for the retrieval of confidential information. A queueing model is developed to study the performance of videotex systems under mixed delivery. Analytic results are derived for the mean response time. Numerical examples are presented to show the performance characteristics of mixed delivery, and how it can be used to enhance the response time performance without increasing the processing capacity of the system.

Videotex is a system which provides users with low-cost real-time access to information. In such a system, user requests are forwarded to a service computer where the desired information is retrieved and sent back to the user. In this study, we investigate the response time behavior of a videotex system where information requested by one user is broadcast to all users. A novel queueing model for broadcast delivery is developed. Using this model, we first obtain an analytic expression for the mean response time, and then we develop an efficient algorithm for its computation. Numerical results illustrating the performance characteristics of broadcast delivery are presented.

A model of an adapter to a local area network is used to study the timing problem associated with the reception of back-to-back frames from a multiaccess transmission medium. The conditions under which frames are received successfully are presented. Analytic results are also obtained for the probabilities that frames are lost and a given number of back-to-back frames is successfully received. Numerical results illustrating the effect of the various design parameters on adapter performance are discussed.

The performance characteristics of a reliable broadcast protocol in a local-area network environment are analyzed. This protocol involves a source broadcasting a message to all destinations and collecting replies from these destinations. Reliability is achieved by using Send-and-Wait protocols for transmitting broadcast and reply messages. A queueing model is developed and results on the throughput and delay of the broadcast operation are obtained by approximate analysis. Numerical results showing the effect of model parameters on throughput are provided.

The use of channel scheduling to improve a measure of fairness in packet-switching networks is investigated. This fairness measure is based on mean end-to-end delays derived from Kleinrock's classical model. The network designer can incorporate any desired relative delay among user classes into this fairness measure. It is found that scheduling is helpful in reallocating delay among user classes and can be used to improve the fairness of a network. It is also shown that a parameterized queueing discipline can be used to further improve fairness. A conservation theorem characterizing the effects of scheduling on overall mean end-to-end delay is established. The results are applicable to both fixed and random routing and are found to be relatively insensitive to fluctuations in traffic.

Broadcast addressing is the capability to send a packet from a source node to all other nodes in the network. Store-and-forward, packet-switching networks are not inherently designed to carry broadcast packets, and broadcasting has to be implemented by some sort of routing algorithm. In this paper, the source based forwarding algorithm is considered. With this algorithm, a spanning tree is defined for each node, and broadcast packets are sent along the branches of these trees. Approximation methods are presented to obtain a lower bound and estimates of the mean broadcast time. The accuracy of these methods is evaluated by comparison with simulation.

In many applications, parallelism inherent in a computation can be exploited by using a parallel computer organization. Such organizations may suffer throughput degradation because of data dependencies. The case of no data dependencies is considered. In this case, the throughput realized is dependent on the actual manner in which the parallel computer system is organized. A comparative performance study of four models of two-processor organizations is presented. The performance evaluation is through queueing analysis or simulation, the aim being to compare their response times under different workloads. This study also indicates the possibility of switching between alternate organizations in a dynamically reconfigurable system.

The choice of collision control algorithm has an effect on the performance of Ethernet. A linear incremental backoff algorithm is proposed and its performance is compared to the binary exponential backoff algorithm. Two variations of Ethernets are used in the comparison: one treats data and acknowledgement packets equally; the other gives priority to acknowledgement packets. The maximum throughputs achieveable by both variations are derived. The performance of both variations is then evaluated by discrete simulation. The evaluation is based on a Ethernet model with uniform or biased traffic.