DM EP BOUSQUET Thomas INFO4

Step 0

Question 1 : Identify the set of testing times that make the scheduler stable (finite mean response time).

The queue is stable if the arrival rate is less than or equal to the service rate. This scheduler follow the principles of a M/M/1 queue which we studied during classes. The arrival rate of this queue is : \[ \begin{aligned} Λ=λN \end{aligned} \] The service rate is : \[ \begin{aligned} μ=\frac{1}{σ} \end{aligned} \] As I said before the arrival rate must be less than or equal to the service rate so we must verify the following inequality : \[ \begin{aligned} Λ \le μ \end{aligned} \] We can also write it like this : \[ \begin{aligned} λN \le \frac{1}{σ} \end{aligned} \]

This mean the set of testing times that make the scheduler stable is \[ \begin{aligned} σ ∈ [0,\frac{1}{λN}] \end{aligned} \] ### Question 2 : Provide a mathematical formula for the mean delay (waiting + service time) of jobs at the scheduler.

To answer this question we’ll use the little’s law

\[ \begin{aligned} L=\frac{ρ}{ρ-1} \end{aligned} \] L is the mean number of jobs Therefore ρ=Λσ and following little’s law L = λD where D is the mean response time

\[ \begin{aligned} D = \frac{Λσ}{1-Λσ}*\frac{1}{Λ}=\frac{σ}{1-Λσ} \end{aligned} \] Knowing that μ = 1/σ and Λ = λN

\[ \begin{aligned} D = \frac{1}{μ-λN} \end{aligned} \]

Question 3 : For p = 1, 2, provide a mathematical formula for E[Xp| Yσ = xm] as a function of the profile matrix Px,y(σ), x, y ∈ {xm, xM} and σ ≥ 0.

on a : \[ \begin{aligned} E[X^p|Yσ=xm] = \sum_{i}^{} xi^p P(X=xi|Yσ=xm) \end{aligned} \] for i = m or M \[ \begin{aligned} E[X^p|Yσ=xm] = xm^p P(X=xm|Yσ=xm)+xM^p P(X=xM|Yσ=xm) \end{aligned} \] using conditional probability \[ \begin{aligned} E[X^p|Yσ=xm] = xm^p \frac{P(X=xm ∩ Yσ=xm)}{P(Yσ=xm)}+xM^p \frac{P(X=xM ∩ Yσ=xm)}{P(Yσ=xm)} \end{aligned} \] \[ \begin{aligned} E[X^p|Yσ=xm] = \frac{xm^pP(X=xm ∩ Yσ=xm)+xM^pP(X=xM ∩ Yσ=xm)}{P(Yσ=xm)} \end{aligned} \] We know that P(Yσ = xm) = P(Yσ = xm ∩ X = xm) + P(Yσ = xm ∩ X = xM) = PxM,xm(σ) + Pxm,xm(σ). \[ \begin{aligned} E[X^p|Yσ=xm] = \frac{xm^pPxm,xm(σ)+xM^pPxM,xm(σ)}{Pxm,xm(σ) + PxM,xm(σ)} \end{aligned} \] p is replaced by 1 then by 2 \[ \begin{aligned} E[X^1|Yσ=xm] = \frac{xmPxm,xm(σ)+xMPxM,xm(σ)}{Pxm,xm(σ) + PxM,xm(σ)} \end{aligned} \] \[ \begin{aligned} E[X^2|Yσ=xm] = \frac{xm^2Pxm,xm(σ)+xM^2PxM,xm(σ)}{Pxm,xm(σ) + PxM,xm(σ)} \end{aligned} \]

LB_SITAc <- function(N, K, mu, InterArrival, JobSize, c, xm, sigma, pxM, pxm) {
  WaitingTime = rep(0, K)
  
  WaitingTimeCum = rep(0, K)
  
  for (n in 1:N)
    #for each job
  {
    # Dispatching decision of SITA-c with predictions
    k_win = sample(x = (c + 1):K)

    sim_xm = (1 - exp(-10 * sigma)) * (pxm) + (1 - exp(sigma)) * (pxM)
    
    if (sim_xm > runif(1))
    {
      # job n is predicted to be short
      k_win = sample(x = 1:c)
    }
    
    # for each server
    for (k in 1:K)
    {
      # Update the waiting time of server k (Lindley's recursion)
      WaitingTime[k] = max(WaitingTime[k] + ifelse(k_win == k, 1, 0) * JobSize[n] /
                             mu[k_win] - InterArrival[n],
                           0)
      
    }
    WaitingTimeCum[k_win] = WaitingTimeCum[k_win] + WaitingTime[k_win]
    
  }
  return(sum(WaitingTimeCum) / N)
}
################################################################################
N=1e8; # number of jobs to simulate
K=35; # number of servers
mu = sample(x=1:1, K+1, replace = TRUE); # service rates
set.seed(14); # Set seed for reproducibility
beta=0.6;
xM=1e9;
xm=1;
JobSize=sample(c(xm,xM),N,replace=T,prob=c(1-1/xM^beta,1/xM^beta)); # Job sizes
EX=xm*(1-1/xM^beta) + xM^(1-beta); # Expected value of job sizes
B=10;
rho = 0.8
c = seq(0,K,1)
simu=rep(0,K+1);
lambda=K * rho/EX; #"overall arrival rate"<"overall service rate"=(mu[1]+...+ mu[K])/EX
InterArrival = rexp(n=N, rate = lambda); # Inter-arrival times
sigma = 0.5
pxM = 1 / xM^beta
pxm = 1 - pxM

Step 3

Question 2

If increasing sigma , mean waiting time also increase in a linear way, there is no σ > 0 such that it is convenient to test job sizes

plot(pressure)

Note that the echo = FALSE parameter was added to the code chunk to prevent printing of the R code that generated the plot.