Analysez un réseau fermé avec MVA

Au chapitre 3, les bornes asymptotiques nous ont appris qu’avec un disque SSD, les 400 utilisateurs attendus au pic de la billetterie restaient sous le point de saturation. Mais une borne est optimiste : elle suppose qu’aucune requête n’attend jamais. Le vrai temps de réponse sera-t-il de 0,1 s, de 0,3 s ou de 2 s ? Le chef de projet veut un chiffre.

Pour l’obtenir, il faut tenir compte des files d’attente à chaque ressource, dans un système où le nombre d’utilisateurs est fixé. C’est exactement ce que fait l’analyse par valeurs moyennes (Mean Value Analysis, MVA), un algorithme d’une dizaine de lignes qui donne des résultats exacts.

Pourquoi un modèle fermé ?

Au chapitre 4, nous avons traité la billetterie comme un réseau ouvert : les requêtes arrivent de l’extérieur à un taux $\lambda$ fixé, quel que soit l’état du système. Ce n’est pas tout à fait réaliste pour un site interactif. Quand le site ralentit, les utilisateurs attendent leur réponse avant de cliquer à nouveau : ils envoient donc moins de requêtes. Le système se régule tout seul.

Un réseau fermé capture ce comportement. On fixe le nombre $N$ d’utilisateurs, qui tournent en boucle :

ils réfléchissent pendant un temps moyen $Z$ (un centre de délai, sans file) ;
ils envoient une requête, qui visite les ressources (des files d’attente, avec leurs demandes $D_i$ ) ;
ils reçoivent la réponse, et recommencent.

Le débit $X$ n’est plus une donnée : c’est un résultat, qui dépend de $N$ .

	Réseau ouvert	Réseau fermé
Donnée d’entrée	taux d’arrivée $\lambda$	nombre de clients $N$ , temps de réflexion $Z$
Débit	$X = \lambda$ (imposé)	calculé, $X(N)$
Saturation	la file grandit sans limite si $\lambda \geq 1/D_{\max}$	le débit plafonne à $1/D_{\max}$ , le temps de réponse grandit
Exemples	API publique, capteurs	site interactif, traitement par lots, pool de connexions

Dans le réseau ouvert, le débit est imposé de l'extérieur ; dans le réseau fermé, les N utilisateurs attendent leur réponse avant de recliquer, et le débit devient un résultat du modèle.

L’idée de MVA : le théorème d’arrivée

Au chapitre 4, nous avons raisonné ainsi pour une file M/M/1 : un client qui arrive trouve en moyenne $Q$ clients devant lui, et son temps de réponse vaut $S(1 + Q)$ . Dans un réseau fermé, il y a une subtilité. Le client qui arrive sur une ressource ne peut pas se voir lui-même dans la file ! Le théorème d’arrivée (arrival theorem) précise ce qu’il voit : dans un réseau fermé à $n$ clients (de forme produit, voir plus bas), un client qui arrive sur une ressource voit en moyenne l’état du réseau à $n - 1$ clients.

C’est ce qui rend possible une récurrence : si l’on connaît les longueurs de file moyennes avec $n - 1$ clients, on en déduit tout avec $n$ clients. On part de $Q_i(0) = 0$ (réseau vide) et on ajoute les clients un par un.

L’algorithme, en trois lois

Pour $n = 1, 2, \dots, N$ , on applique successivement trois relations.

1. Temps de résidence sur chaque ressource (théorème d’arrivée) :

R_i(n) = D_i \,\big(1 + Q_i(n - 1)\big)

où $R_i(n)$ est le temps total qu’une requête passe sur la ressource $i$ (attente et service, toutes visites comprises), $D_i$ sa demande de service et $Q_i(n - 1)$ la longueur moyenne de sa file avec un client de moins. Pour un centre de délai, il n’y a pas d’attente : $R_i(n) = D_i$ .

2. Débit du système (Little sur la boucle complète) :

X(n) = \frac{n}{Z + \sum_i R_i(n)}

3. Longueur de chaque file (Little sur chaque ressource) :

Q_i(n) = X(n) \, R_i(n)

Le temps de réponse du système est $R(n) = \sum_i R_i(n)$ , et les utilisations se déduisent par $U_i = X(n) \, D_i$ .

Déroulons les deux premières étapes pour la billetterie : $D_{\text{web}} = 0{,}020$ s, $D_{\text{CPU}} = 0{,}030$ s, $D_{\text{disque}} = 0{,}060$ s, $Z = 15$ s.

$n = 1$ . Les files sont vides : $R_i(1) = D_i$ , donc $R(1) = 0{,}110$ s. Le débit vaut $X(1) = 1/15{,}110 \approx 0{,}06618$ req/s. Les files : $Q_{\text{web}} \approx 0{,}00132$ , $Q_{\text{CPU}} \approx 0{,}00199$ , $Q_{\text{disque}} \approx 0{,}00397$ .

$n = 2$ . Le disque : $R_{\text{disque}}(2) = 0{,}060 \times 1{,}00397 \approx 0{,}060238$ s. De même $R_{\text{web}}(2) \approx 0{,}020026$ s et $R_{\text{CPU}}(2) \approx 0{,}030060$ s. Donc $R(2) \approx 0{,}110324$ s et $X(2) = 2/15{,}110324 \approx 0{,}13236$ req/s.

Avec si peu d’utilisateurs, les files sont presque vides et le temps de réponse reste collé à $D = 0{,}110$ s. Les choses deviennent intéressantes autour du point de saturation.

Une itération de MVA : les files avec n − 1 clients donnent les temps de résidence, puis le débit, puis les nouvelles files. Au centre, les chiffres de la billetterie pour n = 1 et n = 2.

En Python, l’algorithme tient en quelques lignes :

def mva(D, Z, N):
    """MVA exacte, une classe de clients. D : demandes de service (s), Z : temps de réflexion (s)."""
    Q = [0.0] * len(D)                         # files vides au départ
    for n in range(1, N + 1):
        R = [d * (1 + q) for d, q in zip(D, Q)]   # 1. théorème d'arrivée
        X = n / (Z + sum(R))                      # 2. Little sur la boucle
        Q = [X * r for r in R]                    # 3. Little sur chaque ressource
    return X, sum(R), R

D = [0.020, 0.030, 0.060]                      # web, processeur, disque
for N in (50, 100, 152, 200, 250, 300, 400):
    X, R, _ = mva(D, Z=15, N=N)
    print(f"N = {N:3d} : X = {X:5.2f} req/s, R = {R:5.3f} s")

Le coût est de l’ordre de $N \times K$ opérations pour $K$ ressources : quelques microsecondes pour des centaines d’utilisateurs.

Ce que MVA nous apprend sur la billetterie

Comparons les résultats exacts aux bornes du chapitre 3 :

$N$	Borne sur $X$ (req/s)	$X$ exact (MVA)	Borne sur $R$ (s)	$R$ exact (MVA)	$U_{\text{disque}}$
50	3,31	3,30	0,11	0,129	0,20
152	10,06	9,99	0,11	0,214	0,60
200	13,24	13,04	0,11	0,334	0,78
250	16,55	15,80	0,11	0,827	0,95
300	16,67	16,66	3,00	3,005	1,00
400	16,67	16,67	9,00	9,000	1,00

Plusieurs choses sautent aux yeux :

Avec 152 utilisateurs, MVA prédit $X \approx 9{,}99$ req/s et $R \approx 0{,}21$ s. C’est exactement ce que l’on avait mesuré l’an dernier au chapitre 2 (10 req/s et 0,2 s). Le modèle est validé par la mesure : on peut lui faire confiance pour extrapoler.
Loin de la saturation (50 utilisateurs) ou très au-delà (400), les bornes sont presque exactes. C’est autour de $N^* \approx 252$ que l’écart est le plus grand : à 250 utilisateurs, la borne promet 0,11 s, la réalité est 0,83 s.
Presque tout le temps de réponse se passe sur le disque : à 200 utilisateurs, 0,258 s sur les 0,334 s.

La tranche du disque (magenta) fait presque tout le temps de réponse. À 152 utilisateurs, le modèle retrouve les 0,2 s mesurés ; à 250, la borne promet 0,11 s quand la réalité est 0,83 s.

Et avec le SSD ( $D_{\text{disque}} = 30$ ms) ? Pour 400 utilisateurs, MVA donne $X \approx 26{,}1$ req/s et $R \approx 0{,}31$ s, avec le processeur et le disque à 78 % d’utilisation. Voilà le chiffre que voulait le chef de projet : l’objectif est tenable, mais avec peu de marge.

Avec le SSD, les 400 utilisateurs obtiennent 26,1 req/s et 0,31 s, au lieu de 9 s avec le disque actuel. Mais la courbe du SSD commence déjà à se redresser : la marge est faible.

Les hypothèses, et quand elles tombent

MVA est exacte pour les réseaux dits à forme produit (théorème BCMP), dont les conditions principales sont :

une seule classe de clients (tous les utilisateurs ont les mêmes demandes) ;
des ressources indépendantes de la charge (load independent) : le temps de service ne dépend pas du nombre de clients présents ;
des disciplines compatibles : FCFS avec services exponentiels de même moyenne pour tous, partage de processeur, LCFS avec préemption, ou centre de délai.

Dans la réalité, ces hypothèses sont souvent un peu fausses : plusieurs types de requêtes (consultation et paiement), des verrous en base de données, des serveurs multicœurs. On dispose alors d’extensions (MVA multiclasse, centres dépendants de la charge) et d’approximations. La plus connue, l’approximation de Schweitzer, évite la récurrence en supposant $Q_i(n - 1) \approx \frac{n - 1}{n} Q_i(n)$ et en itérant jusqu’à convergence. Pour la billetterie à 200 utilisateurs, elle donne 13,03 req/s et 0,346 s, contre 13,04 req/s et 0,334 s pour MVA exacte.

En résumé

Un réseau fermé fixe le nombre d’utilisateurs $N$ et leur temps de réflexion $Z$ ; le débit devient un résultat, qui plafonne à $1/D_{\max}$ .
Le théorème d’arrivée : un client qui arrive voit le réseau tel qu’il est avec $n - 1$ clients.
MVA : $R_i(n) = D_i(1 + Q_i(n - 1))$ , $X(n) = n/(Z + \sum_i R_i(n))$ , $Q_i(n) = X(n) R_i(n)$ , en partant de $Q_i(0) = 0$ . Coût en $O(NK)$ .
Les résultats de MVA se placent sous les bornes asymptotiques, et s’en écartent le plus autour du point de saturation $N^*$ .
MVA est exacte pour les réseaux à forme produit (une classe, ressources indépendantes de la charge) ; sinon, on utilise des extensions ou des approximations comme celle de Schweitzer.
Un modèle se calibre et se valide sur des mesures avant de servir à extrapoler.

Exercices

Exercice · Dérouler MVA à la main

facile

Un système de traitement par lots (sans temps de réflexion, $Z = 0$ ) a deux ressources : un processeur de demande 0,2 s et un disque de demande 0,1 s. Déroulez MVA pour $N = 1, 2, 3$ et donnez à chaque fois le débit et le temps de réponse.

Voir la solution

$N = 1$ : $R_{\text{CPU}} = 0{,}2$ , $R_{\text{disque}} = 0{,}1$ , $R = 0{,}3$ s, $X = 1/0{,}3 \approx 3{,}33$ lots/s. $Q_{\text{CPU}} = 3{,}33 \times 0{,}2 \approx 0{,}667$ , $Q_{\text{disque}} \approx 0{,}333$ .

$N = 2$ : $R_{\text{CPU}} = 0{,}2 \times 1{,}667 \approx 0{,}333$ , $R_{\text{disque}} = 0{,}1 \times 1{,}333 \approx 0{,}133$ , $R \approx 0{,}467$ s, $X = 2/0{,}467 \approx 4{,}29$ lots/s. $Q_{\text{CPU}} \approx 1{,}429$ , $Q_{\text{disque}} \approx 0{,}571$ .

$N = 3$ : $R_{\text{CPU}} = 0{,}2 \times 2{,}429 \approx 0{,}486$ , $R_{\text{disque}} = 0{,}1 \times 1{,}571 \approx 0{,}157$ , $R \approx 0{,}643$ s, $X = 3/0{,}643 \approx 4{,}67$ lots/s.

Le débit tend vers $1/D_{\max} = 5$ lots/s : le processeur est le goulot.

En code

Python
R

D, Z = [0.2, 0.1], 0            # processeur, disque (s) ; pas de temps de réflexion
Q = [0.0, 0.0]                  # files vides au départ
for n in range(1, 4):
    R = [d * (1 + q) for d, q in zip(D, Q)]    # théorème d'arrivée
    X = n / (Z + sum(R))                       # Little sur la boucle
    Q = [X * r for r in R]                     # Little sur chaque ressource
    print(f"N = {n}: R = {sum(R):.3f} s, X = {X:.2f} lots/s, Q = {[round(q, 3) for q in Q]}")
# N = 1: R = 0.300 s, X = 3.33 lots/s, Q = [0.667, 0.333]
# N = 2: R = 0.467 s, X = 4.29 lots/s, Q = [1.429, 0.571]
# N = 3: R = 0.643 s, X = 4.67 lots/s, Q = [2.267, 0.733]

D <- c(0.2, 0.1); Z <- 0        # processeur, disque (s) ; pas de temps de réflexion
Q <- c(0, 0)                    # files vides au départ
for (n in 1:3) {
  R <- D * (1 + Q)              # théorème d'arrivée
  X <- n / (Z + sum(R))         # Little sur la boucle
  Q <- X * R                    # Little sur chaque ressource
  cat(sprintf("N = %d : R = %.3f s, X = %.2f lots/s, Q = %.3f %.3f\n", n, sum(R), X, Q[1], Q[2]))
}
# N = 1 : R = 0.300 s, X = 3.33 lots/s, Q = 0.667 0.333
# N = 2 : R = 0.467 s, X = 4.29 lots/s, Q = 1.429 0.571
# N = 3 : R = 0.643 s, X = 4.67 lots/s, Q = 2.267 0.733

Exercice · Borne ou valeur exacte ?

moyen

Pour le système de l’exercice précédent, calculez les bornes asymptotiques sur $X$ et $R$ pour $N = 1, 2, 3$ et comparez aux valeurs exactes. Pour quel $N$ l’écart relatif sur le débit est-il le plus grand ?

Voir la solution

$D = 0{,}3$ s, $D_{\max} = 0{,}2$ s, $Z = 0$ , donc $N^* = 0{,}3/0{,}2 = 1{,}5$ .

$N$	Borne $X$	$X$ exact	Borne $R$	$R$ exact
1	$\min(3{,}33 \, ; \, 5) = 3{,}33$	3,33	$\max(0{,}3 \, ; \, 0{,}2) = 0{,}3$	0,3
2	$\min(6{,}67 \, ; \, 5) = 5$	4,29	$\max(0{,}3 \, ; \, 0{,}4) = 0{,}4$	0,467
3	$\min(10 \, ; \, 5) = 5$	4,67	$\max(0{,}3 \, ; \, 0{,}6) = 0{,}6$	0,643

Pour $N = 1$ , la borne est exacte (un client seul n’attend jamais). L’écart relatif sur le débit est le plus grand pour $N = 2$ (5 contre 4,29, soit environ 17 %), c’est-à-dire juste après le point de saturation $N^* = 1{,}5$ . Ensuite, l’écart se réduit à mesure que le processeur approche 100 % d’utilisation.

En code

Python
R

def mva(D, Z, N):
    Q = [0.0] * len(D)
    for n in range(1, N + 1):
        R = [d * (1 + q) for d, q in zip(D, Q)]
        X = n / (Z + sum(R))
        Q = [X * r for r in R]
    return X, sum(R)

D, Z = [0.2, 0.1], 0
for N in (1, 2, 3):
    X, R = mva(D, Z, N)
    X_borne = min(N / (sum(D) + Z), 1 / max(D))
    R_borne = max(sum(D), N * max(D) - Z)
    ecart = (X_borne - X) / X                  # écart relatif sur le débit
    print(f"N = {N}: X {X_borne:.2f} / {X:.2f}   R {R_borne:.2f} / {R:.3f}   écart {ecart:.1%}")
# N = 1: X 3.33 / 3.33   R 0.30 / 0.300   écart 0.0%
# N = 2: X 5.00 / 4.29   R 0.40 / 0.467   écart 16.7%
# N = 3: X 5.00 / 4.67   R 0.60 / 0.643   écart 7.1%

mva <- function(D, Z, N) {
  Q <- rep(0, length(D))
  for (n in 1:N) {
    R <- D * (1 + Q)
    X <- n / (Z + sum(R))
    Q <- X * R
  }
  c(X = X, R = sum(R))
}

D <- c(0.2, 0.1); Z <- 0
for (N in 1:3) {
  exact <- mva(D, Z, N)
  X_borne <- min(N / (sum(D) + Z), 1 / max(D))
  R_borne <- max(sum(D), N * max(D) - Z)
  ecart <- (X_borne - exact[["X"]]) / exact[["X"]]   # écart relatif sur le débit
  cat(sprintf("N = %d : X %.2f / %.2f   R %.2f / %.3f   écart %.1f %%\n",
              N, X_borne, exact[["X"]], R_borne, exact[["R"]], 100 * ecart))
}
# N = 1 : X 3.33 / 3.33   R 0.30 / 0.300   écart 0.0 %
# N = 2 : X 5.00 / 4.29   R 0.40 / 0.467   écart 16.7 %
# N = 3 : X 5.00 / 4.67   R 0.60 / 0.643   écart 7.1 %

Exercice · Choisir l'amélioration avec MVA

difficile

Reprenez la billetterie à 200 utilisateurs ( $Z = 15$ s, demandes 20, 30 et 60 ms). En réutilisant la fonction mva du chapitre, comparez le temps de réponse obtenu avec :

un processeur deux fois plus rapide ;
un disque deux fois plus rapide.

Sans calculer, laquelle des deux options réduit le plus le temps de réponse ? Vérifiez ensuite.

Voir la solution

Intuitivement, c’est le disque : c’est le goulot, et il concentre l’essentiel du temps de réponse (0,258 s sur 0,334 s à 200 utilisateurs).

for nom, D in [("CPU x2", [0.020, 0.015, 0.060]), ("disque x2", [0.020, 0.030, 0.030])]:
    X, R, _ = mva(D, Z=15, N=200)
    print(f"{nom:<10} X = {X:.2f} req/s, R = {R:.3f} s")

On obtient environ 0,305 s avec le processeur deux fois plus rapide, contre 0,334 s au départ : un gain de 9 % seulement. Avec le disque deux fois plus rapide, on obtient environ 0,126 s : le temps de réponse est divisé par plus de 2,6. C’est la confirmation, cette fois avec les files d’attente, de la règle du chapitre 3 : on améliore d’abord le goulot.

En code

Python
R

def mva(D, Z, N):
    """MVA exacte à une classe : renvoie le débit et le temps de réponse."""
    Q = [0.0] * len(D)
    for n in range(1, N + 1):
        R = [d * (1 + q) for d, q in zip(D, Q)]
        X = n / (Z + sum(R))
        Q = [X * r for r in R]
    return X, sum(R)

options = {"départ": [0.020, 0.030, 0.060],      # web, processeur, disque (s)
           "CPU x2": [0.020, 0.015, 0.060],
           "disque x2": [0.020, 0.030, 0.030]}
for nom, D in options.items():
    X, R = mva(D, Z=15, N=200)
    print(f"{nom:<10} X = {X:.2f} req/s, R = {R:.3f} s")
# départ     X = 13.04 req/s, R = 0.334 s
# CPU x2     X = 13.07 req/s, R = 0.305 s
# disque x2  X = 13.22 req/s, R = 0.126 s

# MVA exacte à une classe : renvoie le débit et le temps de réponse
mva <- function(D, Z, N) {
  Q <- rep(0, length(D))
  for (n in 1:N) {
    R <- D * (1 + Q)
    X <- n / (Z + sum(R))
    Q <- X * R
  }
  c(X = X, R = sum(R))
}

options <- list(depart    = c(0.020, 0.030, 0.060),   # web, processeur, disque (s)
                CPU_x2    = c(0.020, 0.015, 0.060),
                disque_x2 = c(0.020, 0.030, 0.030))
round(sapply(options, mva, Z = 15, N = 200), 3)
#   depart CPU_x2 disque_x2
# X 13.043 13.068    13.222
# R  0.334  0.305     0.126