Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Réseaux de télécommunication

Théorie des files d'attente : loi de Little, la file M/M/1 et le multiplexage statistique

Utilisation, loi de Little avec démonstration, la file M/M/1 avec distribution et délai démontrés, croissance du délai avec la charge, un exemple numérique, l'avantage du multiplexage statistique démontré.

https://www.electronics-engineering.com/fr/theorie-des-files-d-attente-loi-de-little-m-m-1/

Pas encore de vote : soyez le premier à noter cette page.

Dans un réseau à commutation de paquets, les délais les plus grands et les plus variables naissent dans les files d’attente : un routeur reçoit des paquets de nombreuses directions et doit les transmettre un par un. Combien de temps attend-on en moyenne ? Jusqu’à quel point peut-on charger une liaison avant que les délais n’explosent ? La théorie des files d’attente répond par des formules simples et étonnamment utiles. Dans cette leçon, nous regardons la loi de Little avec sa démonstration, la file M/M/1 avec la démonstration de la distribution du nombre de paquets, la croissance du délai avec la charge, et l’avantage du multiplexage statistique démontré.

Le modèle

Une file se décrit par la façon dont les clients (paquets) arrivent, la durée du service (transmission) et le nombre de serveurs. Soit \lambda le taux d’arrivée (paquets par seconde) et \mu le taux de service (paquets par seconde que la liaison transmet quand elle est occupée). Le rapport

    \[ \rho = \frac{\lambda}{\mu} \]

est l’utilisation : la fraction du temps où la liaison est occupée. Pour que la file ne croisse pas sans limite, il faut \rho \lt  1.

La loi de Little

Théorème (Little). Dans un système à l’équilibre, le nombre moyen de clients présents E[N], le taux d’arrivée \lambda et le temps moyen passé dans le système E[T] sont liés par

    \[ E[N] = \lambda\,E[T] \]

Démonstration (idée). On observe le système pendant un long temps \tau. On trace le nombre de clients présents en fonction du temps et l’on calcule l’aire sous la courbe. On peut la calculer de deux façons : en intégrant le nombre de présents dans le temps, \int_0^\tau N(t)dt = \tau\,E[N] ; ou en additionnant le temps que chaque client a passé dans le système, parce que chacun apporte à l’aire une bande de hauteur 1 et de longueur égale à son séjour. Pendant le temps \tau, il arrive environ \lambda\tau clients, de séjour moyen E[T], soit une aire \lambda\tau\,E[T]. En égalant et en divisant par \tau, on obtient la loi. ∎

Elle vaut pour n’importe quelle distribution d’arrivées et de services, et pour n’importe quelle partie du système : la file seule, le serveur seul, tout un réseau. Si un routeur contient en moyenne 50 paquets et qu’il en arrive 10 000 par seconde, chacun y reste en moyenne 5 ms.

La file M/M/1

Le modèle le plus simple a des arrivées de Poisson (indépendantes, avec des temps entre arrivées exponentiels), des temps de service exponentiels et un seul serveur : on l’écrit M/M/1. L’état est le nombre n de paquets présents.

Théorème. À l’équilibre, la probabilité de trouver n paquets est p_n = (1 - \rho)\rho^n, et

    \[ E[N] = \frac{\rho}{1 - \rho},\qquad E[T] = \frac{1}{\mu - \lambda} \]

Démonstration. L’état passe de n à n + 1 avec une arrivée, au taux \lambda, et de n + 1 à n avec un départ, au taux \mu. À l’équilibre, le flux de probabilité entre deux états adjacents s’équilibre : \lambda p_n = \mu p_{n+1}, c’est-à-dire p_{n+1} = \rho\,p_n, d’où p_n = \rho^n p_0. Les probabilités doivent avoir pour somme 1 : p_0\sum\rho^n = p_0/(1 - \rho) = 1, donc p_0 = 1 - \rho. La moyenne d’une distribution géométrique de ce type est \sum n(1-\rho)\rho^n = \rho/(1 - \rho). Enfin, par la loi de Little, E[T] = E[N]/\lambda = \frac{\rho}{\lambda(1-\rho)} = \frac{1}{\mu - \lambda}. ∎

Délai moyen dans la file M/M/1 en fonction de l'utilisation
Le temps moyen dans le système, mesuré en temps de service, vaut 2 avec la liaison occupée à 50 %, 5 à 80 % et 10 à 90 %, et croît sans limite en approchant 100 %.

La leçon du graphique

Le délai, mesuré en temps de service 1/\mu, vaut 1/(1 - \rho) : 2 à 50 % d’utilisation, 5 à 80 %, 10 à 90 %, 100 à 99 %. La croissance est douce jusqu’à la moitié de la charge et violente au-delà de 80 %.

Exemple. Une liaison à 10 Mb/s avec des paquets de 1000 octets a \mu = 1250 paquets par seconde, soit 0,8 ms par paquet. Avec \lambda = 1000 paquets par seconde (\rho = 0.8), le temps moyen dans le système est 1/(1250 - 1000) = 4 ms : cinq fois le temps de transmission. C’est pourquoi les opérateurs de réseau ajoutent de la capacité bien avant que les liaisons ne soient saturées, et pourquoi un réseau « lent » n’est souvent pas lent mais chargé.

Le trafic réel n’est pas exactement de Poisson : il est plus en rafales, et les délais à charge égale sont plus grands. Mais l’allure de la courbe, qui explose près de \rho = 1, demeure.

Le multiplexage statistique

Théorème. Une seule liaison de capacité C partagée par N flux de débit \lambda chacun donne un délai moyen N fois plus petit que N liaisons séparées de capacité C/N, chacune dédiée à un flux.

Démonstration. Avec des liaisons séparées, chacune a un taux de service \mu/N (où \mu correspond à la capacité C) et des arrivées \lambda : E[T] = 1/(\mu/N - \lambda) = N/(\mu - N\lambda). Avec la liaison partagée, le service est \mu et les arrivées N\lambda : E[T] = 1/(\mu - N\lambda). Le rapport est N. L’utilisation est la même dans les deux cas. ∎

C’est la justification quantitative de la commutation de paquets (leçon sur l’architecture) : mettre les ressources en commun réduit l’attente, parce qu’un flux peut utiliser la capacité laissée libre par les autres. Le même principe, mutualiser les ressources, explique pourquoi dans un supermarché une seule file qui alimente plusieurs caisses fonctionne mieux que des files séparées.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x