Auteur:
BOEY Lionel & GUO Tianming
L'objectif de notre algo est d'analyser les performance d'une file d'attente simple en fonction de la loi des inter-arrivées et des services.
On utilisent les paramètres suivantes:
*t1[n] = date d'arrive du nème noeud
*t2[n] = date d'arrive du nème noeud
*{Sn} = la séquence des temps de service
*{An} = la séquence des inter-arrivée
*{Rn} = temps de reponse(t1[n]-t2[n])
On fait l'equation de récurrence suivante quand i>=1:
t1[i] = t1[i-1] + A[i]
t2[i] = max(t1[i],t2[i-1]) + S[i]
Principe de la simulation:
Pour pouvoir comparer les differents files, on fixe l'unité de temps(μ:mu=1) au temps moyen de service(sur 4 lois).On fait varier le taux d'arrivé(λ:lambda=nb de client/s) de 0.1 à 0.9 pour observer la réponse de la file à la charge.
library(ggplot2)
library(plyr)
set.seed(15)
service <- function(loi, mu = 1) {
# Loi Exponentielle de paramètre mu(μ)
if (loi == "exp") {
return(rexp(1, mu))
}
# Loi Uniforme sur l'intervalle[0,1]
if (loi == "unif") {
return(runif(1, 0, mu))
}
# Déterministe
if (loi == "dete") {
return(runif(1, mu, mu))
}
# Loi Erlang
if (loi == "erlang") {
return(rgamma(1, shape = 1, rate = mu))
}
}
interarrivee <- function(lambda) {
return(rexp(1, lambda))
}
# Fonction simulation() pour generer le tableau de dataframe
simulation <- function(N, lamb, loi) {
t1 <- c(1:N)
t2 <- c(1:N)
S <- c(1:N)
A <- c(1:N)
R <- c(1:N)
for (i in 1:N) {
S[i] <- service(loi)
A[i] <- interarrivee(lamb)
}
# Comme condition initiale on prendra t1[1]=t2[1]=0
t1[1] <- 0
t2[1] <- t1[1] + S[1]
for (i in 2:N) {
t1[i] <- t1[i - 1] + A[i]
t2[i] <- max(t1[i], t2[i - 1]) + S[i]
}
# Calculer le temps de réponse R, le temps moyenne de réponse mean(R) et
# l'intervalle de confiance ci à 95%.
for (i in 1:N) {
R[i] <- t2[i] - t1[i] #temps de sortie - temps d'entrée
}
data.frame(lambda = lamb, R = mean(R), A = mean(A), S = mean(S), ci = 2 *
sd(R)/sqrt(N), loi = loi)
}
tracelambda <- function(loi) {
df = data.frame()
for (lambda in seq(0.1, 0.9, by = 0.1)) {
df = rbind(df, simulation(100, lambda, loi))
}
df
}
loi <- c()
loi[1] = "exp"
loi[2] = "unif"
loi[3] = "dete"
loi[4] = "erlang"
dataframe = data.frame()
for (i in 1:4) {
set.seed(10)
dataframe = rbind(dataframe, tracelambda(loi[i]))
}
ggplot(data = dataframe, aes(x = lambda, y = R, ymin = R - ci, ymax = R + ci,
color = factor(loi))) + geom_point() + geom_line() + geom_errorbar(width = 0.01)
Si la fonction set.seed(10) est dans la bonne position de la boucle for, les courbes seront correctes.
dataframe
## lambda R A S ci loi
## 1 0.1 1.0441 11.333 0.9822 0.20428 exp
## 2 0.2 1.2438 4.618 0.9973 0.26396 exp
## 3 0.3 1.3433 3.335 0.9512 0.22447 exp
## 4 0.4 2.0324 2.702 1.1170 0.39307 exp
## 5 0.5 2.6523 1.766 1.1608 0.40551 exp
## 6 0.6 1.8713 1.804 0.9426 0.32686 exp
## 7 0.7 2.6555 1.421 1.0898 0.39788 exp
## 8 0.8 3.6877 1.139 0.9398 0.52142 exp
## 9 0.9 2.4461 1.293 0.9934 0.44908 exp
## 10 0.1 0.5098 8.585 0.4905 0.05992 unif
## 11 0.2 0.5011 4.987 0.4638 0.06819 unif
## 12 0.3 0.6274 3.112 0.5597 0.06727 unif
## 13 0.4 0.5724 3.175 0.5288 0.06956 unif
## 14 0.5 0.5886 1.987 0.4879 0.07574 unif
## 15 0.6 0.4743 1.672 0.4335 0.06500 unif
## 16 0.7 0.6878 1.417 0.5232 0.08261 unif
## 17 0.8 0.6355 1.244 0.4792 0.08300 unif
## 18 0.9 0.8892 1.211 0.5325 0.15320 unif
## 19 0.1 1.0401 10.161 1.0000 0.03064 dete
## 20 0.2 1.0916 5.497 1.0000 0.04292 dete
## 21 0.3 1.1715 3.456 1.0000 0.07272 dete
## 22 0.4 1.5716 2.210 1.0000 0.18136 dete
## 23 0.5 1.7437 1.817 1.0000 0.18910 dete
## 24 0.6 1.4424 1.739 1.0000 0.13239 dete
## 25 0.7 1.6453 1.651 1.0000 0.16809 dete
## 26 0.8 1.9347 1.303 1.0000 0.20130 dete
## 27 0.9 2.9612 1.249 1.0000 0.41534 dete
## 28 0.1 1.1544 8.485 1.0794 0.22984 erlang
## 29 0.2 1.3432 4.778 1.1004 0.21037 erlang
## 30 0.3 1.5972 3.582 1.1814 0.28093 erlang
## 31 0.4 1.0443 2.601 0.8517 0.16115 erlang
## 32 0.5 2.8806 2.160 1.1331 0.57387 erlang
## 33 0.6 2.0092 1.767 0.9721 0.38590 erlang
## 34 0.7 2.0376 1.461 0.9372 0.38258 erlang
## 35 0.8 2.1993 1.159 0.8539 0.31938 erlang
## 36 0.9 1.9191 1.235 0.8555 0.40976 erlang
Au debut, on a défini λ in [0.1:0.9], μ = 1, λ < μ. Dans le tableau dataframe, on peut bien voir que pour tous les loi, le temps moyen de service(mean(S)) est toujours petit que le temps moyen d'inter-arrivée(mean(A)), le system est stable.
En général, temps de reponse
R=t2[i]-t1[i]
*t1[i] = t1[i-1] + A[i]
*t2[i] = max(t1[i],t2[i-1]) + S[i]
donc,
R[i]= max(t1[i],t2[i-1]) + S[i] - t1[i-1] - A[i]
= max(R[i-1]+S[i]-A[i],S[i])
Pour la loi uniforme, le temps de service S est toujours dans [0,1], la reponse R est très rapide, donc, le temps moyen de reponse et l'intervalle de confiance sont toujours petits.
Concernant les autres trois courbes, dans notre cas, les durées des services sont constantes pour la loi deterministe, son temps de reponse R est décidé par l'inter-arrivée A. Loi de Erlang peut être considérée comme la somme de N variables aléatoires indépendantes de même loi exponentielle de paramètre λ. Pour la loi exponentielle, les S=rexp(1,0.X) sont probablement grande que les A=rexp(1,1), alors le paramètre λ sur loi exponentielle a bien influencé les temps moyen de reponse R dans ce trois cas, donc, pour la taille de l'intervalle de confiance ci=2*sd®/sqrt(N), elle est bien influencé par λ aussi.