Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #4045

Re: Queuing theory...

Cross-posted to 2 groups.

Show all headers | View raw

I correct: infini in french means infinity..



On 12/17/2013 4:48 PM, aminer wrote:
>
> Hello,
>
> I want to talk about the mathematical modeling of
> queuing networks , if you have noticed in a webserver
> that uses a distributed database  , the database
> have to be modeled as a queuing system with an
> hyperexponential service, but this will complicate the
> mathematical modeling of the  webserver since the
> database  have to be modeled as an M/G/1 queuing system,
> so we have to simplify the mathematical modeling , so if
> for exemple the database's write transactions takes in average
> much more time than a database's read transaction so we have
> to choose the worst case scenario , that means we have to choose
> the rate of the database's write transactions as the rate
> of the arrival to the  queuing system of the database  so
> that  the database can be modeled as an M/M/1 queuing system
>   (M: means markovian), so that the webserver can finally be
> modeled as two M/M/1  queuing system in series, one for
> the database and one for the internet network.
>
> But there is still a problem, if we want to also resolve the
> worst case scenario when for exemple thousands of custumers
> arrive at the same time to the webserver.. so the webserver
> have to be modeled taking into acount this worst case scenario...
>
> Here is the matematical modeling of an M/M/1 queuing system:
>
> We already know that to satisfy a Poisson process we must
> have that N(t1)- N(t0), N(t2)- N(t1) etc. must be independant
> that means the counting increments must be independant.
>
> We have the following relation between the Poisson law
> and Exponential law:
>
> the expected value E(X exponential) = 1 / E(X poisson)
>
> so f the arrival is poissonian then the interarrivals are
> exponential..
>
> Now i will calculate the expected mean waiting time and
> mean number of custumers in the queuing system:
>
> The Little law says that the waiting time in the queuing system:
>
> Ws = Ls/lambda
>
> And the waiting time in the queue of the queuing system is:
>
> Wq = Ws - 1/Mu
>        =  Ls/lambda - 1/Mu
>
> And the Little law gives us the expected mean number of custumers in the
> queue:
>
> Lq = Wq*lambda =  Ls - Phi  et Phi = lamda/Mu
>
> That implies:
>
> Ls - Lq = Phi
>
>
> When the system is in a stationary state , the balance equations gives:
>
> State                          rate in = rate out
>
> state 0:                       Mu * P1 = lambda*P0
> state 1:  lambda*P0 + Mu*P2 = lambda*P1 + Mu*P1
> state 2:  lambda*P1 + Mu*P3 = lambda*P2 + Mu*P2
> ...
> state n:  lambda*Pn-1 + Mu*Pn+1 = lambda*Pn + Mu*Pn
>
>
> And that gives us the following balance equations:
>
> lambda * P0 = Mu*P1   <=>  P1 = (lambda/Mu)*P0
>
> lambda * P1 = Mu*P2    <=>  P1 = (lambda/Mu)^2*P0
>
> lambda * P2 = Mu*P3    <=>  P1 = (lambda/Mu)^3*P0
>
> ...
>
> lambda * Pn-1 = Mu*Pn    <=>  P_n = (lambda/Mu)^k*P0  [1]
>
>
>
> Note: P0 means the probality of having zero custumer in the queuing system.
>           and ^ means power.
>
>
> And we have also that:
>
> Sum(n=0 -> infini) (Pn) = 1  that means the sum of probabilities equal 1
>
> And  [1] gives us:
>
> Sum(n=0 -> infini) (Phi^n*P0) =1
>
> And by resolving the sum if a geometric series that gives us:
>
> P0 * 1/(1-Phi) = 1 => P0 = 1 - Phi  and Phi < 1
>
> And [1] gives us:
>
> Pn = (1-Phi) Phi^n
>
> And we have that means the mean expected number iof custumer in the
> queing system is:
>
> Ls = Sum(n=0 -> infini) (n*Pn)
>
> That implies:
>
> Ls = Sum(n=0 -> infini) (n*(1-Phi)*Phi^n) = Phi/1-Phi   et Phi<1
>
> and we have the mean expected number of custumer in the queue of the
> queing system is :
>
> Lq = Ls -Phi = Phi^2/ (1-Phi)  et Phi<1
>
>
> Little law gives us the mean waiting time in the system and in the queue:
>
> Ws = 1/lambda * Phi/(1-Phi)  and Phi<1
>
> et
>
> Wq= 1/lambda * Phi^2/(1-Phi)  and Phi<1
>
>
> I have just read the following page, look at the the USL
>
> (Universal Law of Computational Scalability) of Dr. Gunther,
> he wrote this: (See: http://en.wikipedia.org/wiki/Neil_J._Gunther )
>
> --------------
>
> The relative capacity C(N) of a computational platform is given by:
>
> C(N)  =              N
>              ------------------------------------------
>            1 + α (N - 1) + ß N (N - 1)
>
> where N represents either the number of physical processors
> in the hardware configuration or the number of users driving the
> software application. The parameters α and ß represent respectively
> the levels of contention (e.g., queueing for shared resources) and
> coherency delay (i.e., latency for data to become consistent) in the
> system. The ß parameter also quantifies the retrograde throughput
> seen in many stress tests but not accounted for in either Amdahl's law
> or event-based simulations.
>
> ----------
>
> His website: http://www.perfdynamics.com/
>
> If you read carefully , you will see that Dr. Gunther is using this
> model to predict scalability after he simulates a relatively small
> number of vusers in LoadRunner ( because of licensing costs, it's
> cost-effective)  and after that he finds the coefficients of the
> 2nd-degree polynomial (quadratic equation) and then transform
> those coefficients back to the USL parameters using the α = b - a
> and ß = a.
>
> And then he is extrapolating with the USL model to higher loads
> to predict scalability.
>
> He is also applying the model to webservers  with heterogeneous
> workloads. like in the following page:
>
> http://perfdynamics.blogspot.com/2009/04/assessing-usl-scalability-wi...
>
> Now  my question follows:
>
> Suppose we have obtained a small number of  measured load-points
> with Loadrunner or others tools, and we calculated the USL equation
> to predict scalability of a webserver , how the USL model can predict
> if the scalability/performance is limited by the network bandwidth
> and not the server ?  I think USL can not predict this.
>
> When we are modeling webservers , we  have to include
> the network node in our network queuig model (that includes
> the computer server queue) , and since the service in the
> computer server is comprised of multiple services (when we
> are using htmls , databases etc.) the network queue will not
> be markovian in its service , and we have to model the network
> queue as an M/G/1 and this will complicate the mathematical
> analytical modeling...
>
> So,  i think the best way is to use a webserver stress tool
> like  http://fwptt.sourceforge.net/
>
> You can even test the webserver  with an heterogeneous
> workloads by starting multiple fwtpp processes, and
> you should increase the number of threads to 5 and after
> that to 10 threads, 15 ... and so on until the webserver
> applications stops responding propperly(and this will inform
> on the maximum number of users that you can have in the same time...)
> and as you are stress testing you can even see (by testing/measuring
> it) if the network bandwidth is not the bottleneck... and this can
> not be done by the USL model.
>
> We already know that to satisfy a Poisson process we must
> have that N(t1)- N(t0), N(t2)- N(t1) etc. must be independant
> that means the counting increments must be independant.
>
> We have the following relation between the Poisson law
> and Exponential law:
>
> the expected value E(X exponential) = 1 / E(X poisson)
>
> and if the arrival is poissonian then the interarrivals are
> exponential..
>
> Now what about a webserver ?
>
> I have read the following paper:
>
> http://docs.google.com/viewer?a=v&q=cache:JFYCp_dSPP4J:citeseerx.ist....
>
> And it says that a simple model with M/M/1/k with FCFS discipline
> can predict webserver performance quite well..
>
> Hence,  i think we can model our webserver over internet
> with 3 queues connected as a Jackson Network like this
>
> A ->  M/M/1 Server Queue -> M/M/1 Network queue -> M/M/1 Client -> A
>
> A: is the arrival rate
>
> and we have the following:
>
> Ni: number of jobs in each queue
> Ui: utilization of each  queue
>
> Ni =  Ui / (1-Ui)
>
> Adding all the Ni in each individual queue will give the
> average number of jobs in  the entire queuing network.
>
> After that we apply the Little formula:
>
> A: network arrival rate
> T: average response time
>
> N = A*T  => T = N / A
>
> And after that from the mathematical analytical equation
> we can simulate the jackson queuing network that model our
> webservers...
>
> Now there is still an important question that i have:
>
> Our analytical jackson network model can give us insight
> on the webservers behavivior.. but the difficulty  that i find in
> practice is that: suppose we have found the right parametters
> that we want to choose, like for example the service rate of
> the M/M/1 Server Queue , how , from this service rate, can
> we buy the right computer that satisfies the service rate
> that we want ?
>
> We say in OR that:
>
> "Understanding the behavior of a system is what Queueing Theory
> and Little’s Law is all about. But, managing a Queue requires not
> just understanding the behavior of a system, but also in-depth
> knowledge of how to improve a system - improving both aspects
> of Queueing will mean a better, more efficient and cost-effective
> system and, more importantly, a much better customer experience."
>
> I wrote before that:
>
> ---
>
> "It says that a simple model with M/M/1/k with FCFS discipline
> can predict webserver performance quite well..
> Hence,  i think we can model our webserver over internet
> with 3 queues connected as a Jackson Network like this
> A -> M/M/1 Server Queue -> M/M/1 Network queue -> M/M/1 Client -> A
>
> A: the arrival rate
> and we have the following:
> Ni: number of jobs in each queue
> Ui: utilization of each  queue
>
> Ni =  Ui / (1-Ui)
>
> Adding all the Ni in each individual queue will give the
> average number of jobs in  the entire queuing network.
> After that we apply the Little formula:
>
> A: network arrival rate
> T: average response time
>
> N = A*T  => T = N / A
>
> And after that from the mathematical analytical equation
> we can simulate the jackson queuing"
>

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Queuing theory... aminer <aminer@toto.net> - 2013-12-17 16:48 -0800
  Re: Queuing theory... aminer <aminer@toto.net> - 2013-12-17 17:08 -0800
  Re: Queuing theory... aminer <aminer@toto.net> - 2013-12-17 17:19 -0800
  Re: Queuing theory... aminer <aminer@toto.net> - 2013-12-17 17:31 -0800

csiph-web