| 1. |
- Andersson, Mikael, et al.
(författare)
-
Admission control with service level agreements for a web server
- 2005
-
Ingår i: Proceedings of the IASTED International Conference on Internet and Multimedia Systems and Applications, EuroIMSA 2005 : February 21 - 23, 2005, Grindelwald, Switzerland. - 0889864845
-
Konferensbidrag (refereegranskat)abstract
- One problem with web servers is that they are sensitive to overload. The servers may become overloaded during temporary traffic peaks when more requests arrive than the server is designed for. Because overload usually occurs rather seldom, it is not economical to overprovision the servers for these traffic peaks, instead admission control mechanisms can be implemented in the servers. This pa per investigates two overload control strategies with per formance bounds for a web server. In service level agree ments, we bound average response times and throughputs for all service classes. Each request is sorted into a class, where each class is assigned a weight representing the in come for the web site owner. Then a linear optimization algorithm is applied so that the total revenue for the web site during overload is maximized.
|
|
| 2. |
- Andersson, Mikael, et al.
(författare)
-
Design and evaluation of an overload control system for crisis-related Web server systems
- 2006
-
Ingår i: 2006 International Conference on Internet Surveillance and Protection. - 0769526497
-
Konferensbidrag (refereegranskat)abstract
- During recent years we have seen several large-scale crises. The 9/11 terror attacks, tsunamis, storms, floods and bombings have all caused a great deal of damage. A common factor in these crises has been the need for information and one important source of information is usually Web sites. In this work we investigate and design an overload control system for Web sites that are vital in crises. The overload control system uses content adaption to dynamically control Web site performance
|
|
| 3. |
- Andersson, Mikael, et al.
(författare)
-
Performance modeling of an Apache web server with bursty arrival traffic
- 2003
-
Ingår i: IC'03 : proceedings of the international conference on internet computing. - 1932415025 ; , s. 508-511
-
Konferensbidrag (refereegranskat)abstract
- Performance modeling is an important topic in capacity planning and overload control for web servers. We present a queueing model of an Apache web server that uses bursty arrival traffic. The arrivals of HTTP requests is assumed to be a Markov Modulated Poisson Process and the service discipline of the server is processor sharing. The total number of requests that can be processed at one time is limited to K. We obtain web server performance metrics such as average response time, throughput and blocking probability by simulations. Compared to other models, our model is conceptually simple. The model has been validated through measurements and simulations in our lab. The performance metrics predicted by the model fit well to the experimental outcome.
|
|
| 4. |
- Cao, Jianhua, et al.
(författare)
-
A monotonic property of the optimal admission control to an M/M/1 queue under periodic observations with average cost criterion
- 2004
-
Ingår i: Seventeenth Nordic Teletraffic Seminar, NTS 17, Fornebu, Norway, 25-27 August 2004. - 8242305951
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- We consider the problem of admission control to an M/M/1 queue under periodic observations with average cost criterion. The admission controller receives the system state information every ø :th second and can accordingly adjust the acceptance probability for customers who arrive before the next state information update instance. For a period of ø seconds, the cost is a linear function of the time average of customer populations and the total number of served customers in that period. The objective is to Ønd a stationary deterministic control policy that minimizes the long run average cost. The problem is formulated as a discrete time Markov decision process whose states are fully observable. By taking the control period ø to 0 or to 1, the model in question generalizes two classical queueing control problems: the open and the closed loop admission control to an M/M/1 queue. We show that the optimal policy is to admit customers with a non-increasing probability with respect to the observed number of customers in the system. Numerical examples are also given.
|
|
| 5. |
- Cao, Jianhua, et al.
(författare)
-
An approximate analysis of load balancing using stale state information for servers in parallel
- 2003
-
Ingår i: Proceedings of the Second IASTED International Conference on Communications, Internet, and Information Technology : November 17 - 19, 2003, Scottsdale, AZ, USA. - 0889863989
-
Konferensbidrag (refereegranskat)abstract
- That a load balancing strategy using stale information care lessly will incur system performance degradation is easy to verify. However it is not so obvious that routing a customer to the expected shortest queue has the same problem when information for decision is stale. We consider a queueing system with a load balancer and a pool of identical FCFS queues in parallel. The arrival process is assumed to be Poisson and the service times have identical independent exponential distributions. The pool of servers informs the load balancer the number of customers in each server at some regularly spaced time instances. The load balancer routes each customer to the expected shortest queue based on available stale information and elapsed time since the last time instance of system sate information updating. The system performance analysis of this type of model is usu ally difficult because the involved state space is very large. However when taking the number of servers to the infinite limit, we have a set of differential equations which is easier to handle than the finite case. Using the approximation of infinite number of severs, we show that the average wait ing time for the system is not always minimized by routing each customer to the expected shortest queue when infor mation for decision is stale.
|
|
| 6. |
- Cao, Jianhua, et al.
(författare)
-
Linear programming relaxations and a heuristic for the buffer sharing model - Discounted case
- 2005
-
Ingår i: Performance Challenges for Efficient Next Generation Networks, Vols 6A-6C. ; 6A-6C, s. 939-948
-
Konferensbidrag (refereegranskat)abstract
- We investigate a model for buffer management of multi-class traffic into a finite shared buffer. A hierarchy of increasingly stronger linear programming relaxations for this model is proposed. The number of hierarchies equals the number of job classes. Each relaxation in the hierarchy is constructed by projecting the original achievable performance region into a polytope with fewer variables and fewer constraints. Based on the first order LP relaxation, we propose a heuristic buffer management policy which can be obtained efficiently and is applicable to a wide range of reward functions including weighted sum of throughputs and weighted sum of buffer utilization. According to our simulations, the proposed heuristic performs close to optimum in all traffic conditions when the objective is to maximize the weighted sum of throughputs.
|
|
| 7. |
- Cao, Jianhua, et al.
(författare)
-
Linear programming relaxations and marginal productivity index policies for the buffer sharing problem
- 2008
-
Ingår i: Queueing Systems. - : Springer Science and Business Media LLC. - 0257-0130 .- 1572-9443. ; 60:3-4, s. 247-269
-
Tidskriftsartikel (refereegranskat)abstract
- We study the dynamic admission control for a finite shared buffer with support of multiclass traffic under Markovian assumptions. The problem is often referred to as buffer sharing in the literature. From the linear programming (LP) formulation of the continuous-time Markov decision process (MDP), we construct a hierarchy of increasingly stronger LP relaxations where the hierarchy levels equal the number of job classes. Each relaxation in the hierarchy is obtained by projecting the original achievable performance region onto a polytope of simpler structure. We propose a heuristic policy for admission control, which is based on the theory of Marginal Productivity Index (MPI) and the Lagrangian decomposition of the first order LP relaxation. The dual of the relaxed buffer space constraint in the first order LP relaxation is used as a proxy to the cost of buffer space. Given that each of the decomposed queueing admission control problems satisfies the indexability condition, the proposed heuristic accepts a new arrival if there is enough buffer space left and the MPI of the current job class is greater than the incurred cost of buffer usage. Our numerical examples for the cases of two and eight job classes show the near-optimal performance of the proposed MPI heuristic.
|
|
| 8. |
- Cao, Jianhua
(författare)
-
Marginal Productivity Indices and Linear Programming Relaxations for Dynamic Resource Allocation in Queueing Systems
- 2008
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Many problems concerning resource management in modern communication systems can be simplified to queueing models under Markovian assumptions. The computation of the optimal policy is however often hindered by the curse of dimensionality especially for models that support multiple traffic or job classes. The research focus naturally turns to computationally efficient bounds and high performance heuristics. In this thesis, we apply the indexability theory to the study of admission control of a single server queue and to the buffer sharing problem for a multi-class queueing system. Our main contributions are the following: we derive the Marginal Productivity Index (MPI) and give a sufficient indexability condition for the admission control model by viewing the buffer as the resource; we construct hierarchical Linear Programming (LP) relaxations for the buffer sharing problem and propose an MPI based heuristic with its performance evaluated by discrete event simulation. In our study, the admission control model is used as the building block for the MPI heuristic deployed for the buffer sharing problem. Our condition for indexability only requires that the reward function is concavelike. We also give the explicit non-recursive expression for the MPI calculation. We compare with the previous result of the indexability condition and the MPI for the admission control model that penalizes the rejection action. The study of hierarchical LP relaxations for the buffer sharing problem is based on the exact but intractable LP formulation of the continuous-time Markov Decision Process (MDP). The number of hierarchy levels is equal to the number of job classes. The last one in the hierarchy is exact and corresponds to the exponentially sized LP formulation of the MDP. The first order relaxation is obtained by relaxing the constraint that no buffer overflow may occur in any sample path to the constraint that the average buffer utilization does not exceed the available capacity. Based on the Lagrangian decomposition of the first order relaxation, we propose a heuristic policy based on the concept of MPI. Each one of the decomposed subproblems corresponds to the admission control model we described above. The link to the decomposed sub-problems is the Lagrangian multiplier for the relaxed buffer size constraint in the first order relaxation. Our simulation study indicates the near optimal performance of the heuristic in the (randomly generated) instances investigated.
|
|
| 9. |
- Cao, Jianhua
(författare)
-
Some topics in web performance analysis
- 2004
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis consists of four papers on web performance analysis. In the first paper we investigate the performance of overload control through queue length for two different web server architectures. The simulation result suggests that the benefit of request prioritization is noticeable only when the capacities of the sub-systems match each other. In the second paper we present an M/G/1/K*PS queueing model of a web server. We obtain closed form expressions for web server performance metrics such as average response time, throughput and blocking probability. The model is validated through real measurements. The third paper studies a queueing system with a load balancer and a pool of identical FCFS queues in parallel. By taking the number of servers to infinite, we show that the average waiting time for the system is not always minimized by routing each customer to the expected shortest queue when the information used for decision is stale. In the last paper we consider the problem of admission control to an M/M/1 queue under periodic observations with average cost criterion. The problem is formulated as a discrete time Markov decision process whose states are fully observable. A proof of the existence of the average optimal policy by the vanishing discounted approach is provided. We also show that the optimal policy is nonincreasing with respect to the observed number of customers in the system.
|
|
| 10. |
- Cao, Jianhua, et al.
(författare)
-
Web Server Performance Modeling using an M/G/1/K*PS Queue
- 2003
-
Ingår i: ICT'2003 : 10th international conference on telecommunications. Volume 2. - 0780376617 ; , s. 1501-1506
-
Konferensbidrag (refereegranskat)abstract
- Performance modeling is an important topic in capacity planning and overload control for web servers. We present an M/G/1/K*PS queueing model of a web server. The arrival process of HTTP requests is assumed to be Poissonian and the service discipline is processor sharing. The total number of requests that can be processed at one time is limited to K. We obtain closed form expressions for web server performance metrics such as average response time, throughput and blocking probability. The average of the service time requirement and the limit of the number of requests being served are model parameters. The parameters are estimated by maximizing the log-likelihood function of the measured average response time. Compared to other models, our model is conceptually simple and it is easy to estimate model parameters. The model has been validated through measurements in our lab. The performance metrics predicted by the model fit well to the experimental outcome.
|
|
