I'm a newcomer to the realm of queueing theory, so please bear with me :)

I'd like to model web server traffic with a modified M/M/1 queue. In the simple case we have two parameters - $\lambda$ for the arrival rate and $\mu$ for the departure (or service) rate.

If I understand correclty, the general way to get the performance evaluation equations (average number of requests in the queue, for example) is to draw a flow diagram, and solve the equlibrium equation system, namely for the M/M/1 model:

$0 = -\lambda p_{0}$ + $\mu p_{1}$

$0 = \lambda p_{n-1} - (\lambda + \mu) p_{n} +\mu p_{n+1}$, n = 1, 2, ...

I don't know how I could extend the model the fit the real-world scenario the most. Each normal request induces a number of image requests, for example, let it be $u$ on average, and let it's service rate be $\sigma$. How can I factor these into the equations?


Just introduce extra states. The total description of a state will include the length of the queue and the stage of service for the current customer. For instance, if each initial service may result in the second stage service with probability $q$ and the departure rate for this second stage service is $\sigma$, then you'll get 2 equations corresponding to 2 possible states with queue length $n$: $\mu p_n(1)+\lambda p_n(1)-\mu p_{n+1}(1)(1-q)-\sigma p_{n+1}(2)-\lambda p_{n-1}(1)=0$ and $\sigma p_n(2)+\lambda p_n(2)-\mu p_{n+1}(1)q-\lambda p_{n-1}(2)=0$ (Just look at how you can depart from the state and put the corresponding terms with plus and then look at how you can arrive to the state and put the corresponding terms with minus. For instance, the terms in the first equation correspond to having been served at stage 1, new arrival to the queue serving a stage 1 customer, completely finishing serving a stage 1 customer in a queue with $n+1$ customers, finishing serving a stage 2 customer in that queue, and arrival of a new customer to the queue of length $n-1$ serving a stage 1 customer).

Sometimes you can simplify resulting big systems to smaller ones but the general idea is always to start with the set of states that fully describes everything that may happen in the system, not just the parameters you want in the end.

  • $\begingroup$ Okay, I get the general idea, thanks. What is a bit misleading is that I don't need two "stages": the induces/generated requests should be the same "type" as a newly arrived one. if I undestand correctly, you used p_{n}(1) and p_{n}(2) to essentially split it into two queues. $\endgroup$
    – Zoltan
    Apr 20 '10 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.