0% ont trouvé ce document utile (0 vote)

10 vues186 pages

Dimensionnement des Réseaux Mobiles

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

10 vues186 pages

Dimensionnement des Réseaux Mobiles

Transféré par

fortunerichesse807

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Dimensionnement de réseaux

[Link]́ et [Link]

Master IRS
Mars 2005
2
Préface

Un réseau de télécommunication requiert en amont une conception précise et

en aval une gestion rigoureuse pour être en mesure de satisfaire la demande
variées des utilisateurs de ce réseau (services en mode circuit, téléphonie, ser-
vices de données, . . . ). Lors de la phase de conception du réseau, l’opérateur
doit calculer la quantité nécessaire de ressources à déployer (points d’accès,
routeurs, couverture cellulaire, commutateurs, . . . ) pour répondre d’une
manière appropriée à la demande courante ou à venir des utilisateurs. Or la
demande est aléatoire : le nombre d’appels entrants générés par les utilisa-
teurs mobiles dans une cellule, le nombre de paquets émis par un terminal
qui interroge un serveur via un routeur de transit, . . . Ainsi la théorie des files
d’attente joue un rôle important dans la phase de conception du réseau car
elle permet au concepteur d’élaborer de bons modèles de représentation afin
de prédire correctement le comportement aléatoire du système et de calculer
la quantité de ressources nécessaires à un bon dimensionnement du réseau.

Cet ouvrage est une tentative de formalisation des problèmes pertinents

qui existent dans les réseaux de données et les réseaux mobiles. Ainsi, nous
essayons d’évaluer les performances des réseaux à travers les lois des files
d’attente. Ceci permettra notamment de tirer des règles de dimensionnement
et du contrôle d’admission dans les réseaux. Les environnements visés dans
ce poly sont les réseaux mobiles (GSM, UMTS), les réseaux satellitaires, les
réseaux à commutation par paquets et les réseaux X25.

Au premier chapitre, nous commençons par introduire la théorie des files

d’attente et les principaux résultats qui nous serviront par la suite.

Les chapitres suivants évaluent les performances dans les réseaux mobiles
et les réseaux de paquets. Il est difficile dans un seul ouvrage d’épuiser une
4

matière aussi vaste que le dimensionnement ou la conception et la gestion

des réseaux. Nous avons ainsi limité nos études à certaines problématiques
de base, telles le routage ou le contrôle de flux, que nous illustrons par des
exemples concrets.
D’une manière plus précise, les études de cas posées dans ce poly concer-
nent les techniques de multiplexage, le routage, le contrôle de flux, le partage
de bande passante dans le réseaux et le dimensionnement dans les réseaux.
Contents

1 Introduction aux modèles d’attente dans les réseaux 11

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Introduction au télétrafic . . . . . . . . . . . . . . . . . . . . . 14
1.2.1 Processus de Poisson . . . . . . . . . . . . . . . . . . . 14
1.2.2 Validité de l’hypothèse Poisson dans le cas de trafic réel 17
1.2.3 Superposition de n processus de Poisson indépendants 18
1.2.4 Décomposition d’un processus de Poisson . . . . . . . . 19
1.2.5 Autres modèles de trafic . . . . . . . . . . . . . . . . . 19
1.3 Description d’une file d’attente . . . . . . . . . . . . . . . . . 21
1.3.1 La file générique . . . . . . . . . . . . . . . . . . . . . 21
1.3.2 Remarques générales . . . . . . . . . . . . . . . . . . . 22
1.4 Les principaux résultats de la file M/M/1 et de ses dérivées . 23
1.4.1 Le processus de naissance et de mort . . . . . . . . . . 24
1.4.2 La file M/M/1 . . . . . . . . . . . . . . . . . . . . . . 25
1.4.3 La file M/M/m . . . . . . . . . . . . . . . . . . . . . . 29
1.4.4 La file M/M/∞ . . . . . . . . . . . . . . . . . . . . . . 31
1.4.5 La file M/M/m/m avec perte . . . . . . . . . . . . . . 32
1.5 Les principaux résultats de la file M/GI/1 . . . . . . . . . . . 33
1.5.1 La chaı̂ne incluse . . . . . . . . . . . . . . . . . . . . . 33
1.5.2 Les formules de Pollaczek-Khinchin . . . . . . . . . . . 34
1.5.3 La période d’activité et le cycle de fonctionnement . . . 38
1.6 Les réseaux de files d’attente à forme produit . . . . . . . . . 39
1.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 39
1.6.2 Les réseaux de Jackson . . . . . . . . . . . . . . . . . . 41
1.6.3 La généralisation des réseaux de Jackson : les réseaux
BCMP . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6 CONTENTS

2 La file M/GI/1 multiclasse 49

2.1 La chaı̂ne incluse . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2 Etude du nombre d’arrivées durant le service d’un client . . . 50
2.3 La fonction génératrice du nombre de clients dans le système . 52
2.4 Les formules de Pollaszek-Khintchine . . . . . . . . . . . . . . 53
2.5 Analyse de la distribution du délai . . . . . . . . . . . . . . . 55

3 Files de Priorité 57
3.1 Le modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Analyse du délai d’attente . . . . . . . . . . . . . . . . . . . . 59
3.2.1 Calcul du délai moyen d’attente . . . . . . . . . . . . . 59
3.2.2 Cycle de délai . . . . . . . . . . . . . . . . . . . . . . . 60
3.3 Formule de conservation . . . . . . . . . . . . . . . . . . . . . 62
3.3.1 Exemples de grandeurs insensibles à la politique de ser-
vice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.3.2 Formule de conservation pour la file M/GI/1 . . . . . 63
3.4 Analyse de la politique de service LIFO . . . . . . . . . . . . . 65
3.4.1 La politique LIFO non préemptive . . . . . . . . . . . 65
3.4.2 La politique LIFO préemptive resume . . . . . . . . . . 67
3.5 Analyse de la politique ”Head Of the Line” HOL . . . . . . . 67
3.5.1 Service non préemptif . . . . . . . . . . . . . . . . . . . 69
3.5.2 Service ”preemptive resume” . . . . . . . . . . . . . . . 71

4 Comparaison des différentes techniques de multiplexage 73

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 Architecture du réseau GSM . . . . . . . . . . . . . . . . . . . 75
4.2.1 Architecture matérielle du sous-système radio . . . . . 77
4.2.2 Architecture matérielle du sous-système fixe . . . . . . 77
4.2.3 Sous-système d’exploitation et de maintenance . . . . 78
4.3 Architecture du réseau UMTS . . . . . . . . . . . . . . . . . . 79
4.4 Accès Multiple à Répartition dans les Fréquences . . . . . . . 80
4.4.1 Caractéristiques de la technique FDMA . . . . . . . . . 80
4.5 Accès Multiple à Répartition dans le Temps . . . . . . . . . . 81
4.5.1 La synchronisation avec la technique TDMA . . . . . . 82
4.5.2 Dimensionnement de l’intervalle de garde dans un réseau
mobile . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
CONTENTS 7

4.5.3 Dimensionnement de l’intervalle de garde dans un réseau

non hiérarchique . . . . . . . . . . . . . . . . . . . . . 84
4.5.4 Caractéristiques de la technique TDMA . . . . . . . . 86
4.5.5 Partage des ressources radio dans le réseau GSM . . . 87
4.5.6 Exemple d’attribution de fréquences dans un réseau GSM 90
4.6 Accès Multiple à Répartition par les Codes . . . . . . . . . . . 91
4.6.1 Etalement du spectre . . . . . . . . . . . . . . . . . . . 91
4.6.2 Caractéristiques de la technique CDMA . . . . . . . . 94
4.6.3 Contrôle de puissance . . . . . . . . . . . . . . . . . . . 95
4.6.4 Capacité des systèmes CDMA . . . . . . . . . . . . . . 96
4.6.5 Allocation du spectre dans le réseau UMTS . . . . . . 99
4.7 Comparaison des différentes techniques de multiplexage . . . . 100
4.7.1 Les hypothèses de modélisation . . . . . . . . . . . . . 100
4.7.2 L’analyse du multiplexage en fréquence FDMA . . . . 101
4.7.3 Le multiplexage temporel synchrone . . . . . . . . . . . 104
4.7.4 Le multiplexage temporel asynchrone (statistique) . . . 104
4.8 Quelques conclusions . . . . . . . . . . . . . . . . . . . . . . . 106

5 Gestion de la mobilité 109

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2 Handover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.2.1 Raisons de l’initiation du Handover . . . . . . . . . . . 113
5.2.2 Procédure du Handover . . . . . . . . . . . . . . . . . 113
5.2.3 Stratégies de priorité des appels Handover . . . . . . . 116
5.3 Handover dans les réseaux hiérarchiques . . . . . . . . . . . . 120
5.4 Comparaison des performances du schéma standard NPS et
de la stratégie RCS . . . . . . . . . . . . . . . . . . . . . . . . 124
5.4.1 Modélisation du schéma NPS . . . . . . . . . . . . . . 126
5.4.2 Modélisation du schéma RCS . . . . . . . . . . . . . . 129

6 Performances de protocole en présence d’erreurs de trans-

mission 133
6.1 Relation entre les probabilités d’erreur sur l’élément binaire et
sur la trame . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.2 Le modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.3 Analyse du débit utile . . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Calcul de la distribution de Tv . . . . . . . . . . . . . . 135
8 CONTENTS

6.3.2 Cas particuliers . . . . . . . . . . . . . . . . . . . . . . 137

6.3.3 Les moyennes . . . . . . . . . . . . . . . . . . . . . . . 138
6.4 Influence de la longueur de la trame sur le débit . . . . . . . . 139
6.5 Calcul du délai . . . . . . . . . . . . . . . . . . . . . . . . . . 140

7 Les principes du routage dans les réseaux 143

7.1 Le routage dans le contexte de gestion du réseau . . . . . . . . 143
7.2 Les hypothèses statistiques simplifiées . . . . . . . . . . . . . . 144
7.3 Retour sur quelques principes de routage dans un réseau à
commutation de circuit . . . . . . . . . . . . . . . . . . . . . . 147
7.4 Les principaux objectifs du routage dans les réseaux à com-
mutation de paquets . . . . . . . . . . . . . . . . . . . . . . . 149
7.5 Un modèle simplifé du transit dans un réseau à commutation
de paquets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.5.1 Formulation simplifiée du problème du routage dans
un réseau à commutation de paquets . . . . . . . . . . 156
7.5.2 Les principaux algorithmes de calcul de plus court chemin157
7.5.3 Le cas particulier du routage orienté circuit virtuel . . 159

8 Les principes du contrôle de flux 163

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.2 La congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
8.3 Les principaux objectifs du contrôle de flux . . . . . . . . . . . 164
8.3.1 Discussion autour du premier objectif : Compromis
capacité-délai . . . . . . . . . . . . . . . . . . . . . . . 165
8.3.2 Discussion autour du deuxième objectif : Compromis
allocation des ressources-équité entre les utilisateurs . . 166
8.3.3 Discussion autour du troisième objectif: Prévention
contre la saturation de la mémoire . . . . . . . . . . . 167
8.4 Les méthodes de contrôle de flux dans les réseaux à commu-
tation par paquet . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.4.1 La méthode globale . . . . . . . . . . . . . . . . . . . . 171
8.4.2 Les méthodes basées sur le mécanisme de la fenêtre . . 172
8.4.3 Insuffisances de la méthode de la fenêtre . . . . . . . . 178
8.5 Le contrôle de flux au niveau de l’ETTD . . . . . . . . . . . . 182
8.6 Modèle de la fenêtre d’anticipation . . . . . . . . . . . . . . . 182
List of Figures

1.1 Réseaux de Jackson . . . . . . . . . . . . . . . . . . . . . . . . 42

3.1 Politique HOL avec π priorités . . . . . . . . . . . . . . . . . . 68

4.1 Architecture du réseau GSM . . . . . . . . . . . . . . . . . . . 76

4.2 Architecture de l’UTRAN . . . . . . . . . . . . . . . . . . . . 79
4.3 Topologie d’un réseau non hiérarchique . . . . . . . . . . . . . 84
4.4 Exemple de transmission avec TDMA . . . . . . . . . . . . . . 84
4.5 Transmission dans un réseau non hiérarchique . . . . . . . . . 85
4.6 Les canaux physiques dans le réseau GSM . . . . . . . . . . . 87
4.7 Duplexage en fréquence dans le réseau GSM . . . . . . . . . . 89
4.8 Etalement du spectre . . . . . . . . . . . . . . . . . . . . . . . 92
4.9 Désétalement du spectre . . . . . . . . . . . . . . . . . . . . . 93
4.10 Exemple d’un signal pouvant être restitué . . . . . . . . . . . 93
4.11 Exemple d’un signal ne pouvant être restitué . . . . . . . . . . 93
4.12 Problème du Near-far . . . . . . . . . . . . . . . . . . . . . . . 96
4.13 Contrôle de puissance . . . . . . . . . . . . . . . . . . . . . . . 96
4.14 n files M/GI/1 . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5.1 Processus du Handover . . . . . . . . . . . . . . . . . . . . . . 112

5.2 Organigramme du schéma NPS . . . . . . . . . . . . . . . . . 116
5.3 Organigramme du schéma RCS pour les nouveaux appels :
N et Ch désignent le nombre de canaux dans la cellule et le
nombre de canaux de garde . . . . . . . . . . . . . . . . . . . 117
5.4 Organigramme du schéma RCS pour les appels handover . . . 118
5.5 Organigramme de la stratégie de mise en queue des requêtes
handover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.6 Organigramme de la stratégie SRS . . . . . . . . . . . . . . . 120
5.7 Réseau hiérarchique de l’UMTS . . . . . . . . . . . . . . . . . 122
10 LIST OF FIGURES

5.8 le graphe associé au générateur infinitésimal de la chaı̂ne de

Markov pour le schéma NPS . . . . . . . . . . . . . . . . . . . 126
5.9 le graphe associé au générateur infinitésimal de la chaı̂ne de
Markov pour le schéma RCS . . . . . . . . . . . . . . . . . . . 129

7.1 Relation entre Routage et Contrôle de Flux . . . . . . . . . . 150

7.2 Modèle simplifié d’un nœud de transit . . . . . . . . . . . . . 151
7.3 Exemple d’un modèle simplifié de circuit virtuel . . . . . . . . 153
7.4 Fonction de coût . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.5 Exemple de choix de route . . . . . . . . . . . . . . . . . . . . 161

8.1 Un problème d’équité . . . . . . . . . . . . . . . . . . . . . . . 166

8.2 Un réseau inéquitable . . . . . . . . . . . . . . . . . . . . . . . 168
8.3 Conséquences de la saturation . . . . . . . . . . . . . . . . . . 169
8.4 Interblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.5 Cas où d ≤ w ∗ X . . . . . . . . . . . . . . . . . . . . . . . . . 174
8.6 Cas où d > w ∗ X . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.7 Effet du contrôle de flux . . . . . . . . . . . . . . . . . . . . . 176
8.8 Méthode de la fenêtre de proche en proche . . . . . . . . . . . 178
8.9 Contrôle de flux dans une liaison terre-satellite . . . . . . . . . 179
8.10 Insuffisance par rapport à l’équité . . . . . . . . . . . . . . . . 181
8.11 Modèle de la fenêtre par un réseau fermé . . . . . . . . . . . . 184
Chapter 1

Introduction aux modèles

d’attente dans les réseaux

1.1 Introduction
Les réseaux de télécommunication actuels sont multiservices et offrent plusieurs
services capables de transporter aussi bien les flux temps réel (voix, vidéo,
VoIP, . . . ) que les flux non temps réel (WEB, transfert de fichier, courriel,
. . . ). Les réseaux 2G de deuxième génération possèdent deux technologies
de commutation (paquet, circuit). L’évolution prévisible de ces réseaux dans
le cadre de la 3G troisième génération et au-delà conduit au choix d’une
technologie unique de commutation de paquets basée sur les protcoles (TCP,
UDP)/IP. La raison fondamentale derrière cette évolution vers le mode pa-
quet partout dans le réseau c’est que d’une part les flux d’information à
tranporter sont sporadiques et d’autre part la commutation de paquets est le
mode le plus approprié pour tranporter les flux sporadiques en permettant
au fournisseur de service et à l’utilisateur de bénéficier du gain statistique de
multiplexage dans les nœuds qui commutent les paquets. Ainsi, dans le cadre
de ce cours nous analysons systématiquement les performances des réseaux
utilisant la commutation de paquets ou la commutation de circuits.
Pour bien dimensionner un réseau à commutation de paquets ou à commu-
tation de circuit, le concepteur s’intéresse à plusieurs paramètres importants
comme
• Le débit utile offert par le réseau (en bits/s, paquets/s, Erlang . . . )

• La charge des différents éléments du réseau (liens, commutateurs, fais-

12 Introduction aux modèles d’attente dans les réseaux

ceaux . . . )

• Le délai de transit de bout en bout dans le réseau (service de données)

• La probabilité de perte d’une unité de données, d’un appel (service de

données, service circuit)

• La gigue du délai (service de données)

• ...

Dans un réseau à commutation de paquets, une unité de donnée (trame,

paquet, . . . ) peut être perdue pour différentes raisons. Par exemple cela ar-
rive à cause d’une erreur de transmission ou encore à cause d’une congestion
du réseau. Dans le premier cas la couche 2 de gestion de la liaison (HDLC,
LAP-B,...) se charge de corriger l’erreur en répétant la trame. Généralement
quand une congestion arrive dans un réseau (malgré les mécanismes de prévention),
les unités de données qui se trouvent dans la zone congestionnée sont per-
dues et c’est la responsabilité du protocole de bout en bout (de transport)
de répéter les unités perdues.
Dans un réseau à commutation de circuit, le blocage d’un d’une demande
d’établissement d’un appel entrant est consécutif à un risque potentiel de
saturation du réseau. Dans ce cas le traitement d’appel va refuser d’ouvrir
un circuit pour prévenir le blocage du réseau à cause d’un taux d’occupation
important des commutateurs et/ou des faisceaux.
En général, les flux de paquets de données sont sensibles aux erreurs
de transmission. La probabilité d’erreur sur un bit est liée directement à la
probabilité d’erreur sur la trame. Nous verrons plus loin que cette relation est
linéaire, sous certaines conditions, avec une bonne approximation. Le taux
d’erreur par bit ou par paquet est une donnée du point de vue du concepteur
du réseau.
D’autres données importantes du problème de conception sont

• la matrice du trafic qui traverse le réseau,

• certains paramètres topologique du réseau comme le diamètre (la plus

courte distance entre les deux nœuds les plus éloignés du réseau) ou
encore le degré de connectivité d’un nœud qui ont un impact direct sur
les performances (délai, probabilité de blocage d’un appel . . . )
1.1 Introduction 13

• le temps de réponse à une requête

La liste de ces données n’est pas exhaustive.

Dans un réseau à commutation de paquets, nous allons distinguer le temps
de transit du temps de réponse qui est égal à la somme des trois termes
suivants

• Le temps de transit de la requête

• Le temps de traitement de la requête dans le système destination

• Le temps de transit de la réponse à la requête

Donc le temps de réponse implique à la fois le réseau et le terminal desti-

nataire. Considérons en particulier le problème de la conception du routage
que nous allons le poser de la manière suivante

• Etant donné

– la matrice de trafic
– la topologie
– la capacité du réseau (vitesse des liaisons, capacité de commuta-
tion des noeuds,...)

• Trouver les meilleurs chemins à allouer à chaque flux de trafic

• Sous la contrainte que le délai de transit maximum reste inférieur à une

valeur fixée d’avance.

Ainsi la conception des tables de routage se pose en terme d’un problème

d’attente dont la solution relève des techniques de la recherche opérationnelle.
En comparaison, dans un réseau à commutation de circuit, les ressources
seront allouées à la communication d’une manière dédiée. Donc la route sera
choisie parmi les plus courts chemins. En plus, l’algorithme de routage doit
minimiser la probabilité de blocage des appels dans le réseau.
Dans les paragraphes suivants, nous allons introduire quelques outils de
recherche opérationnelle qui sont utilisés pour calculer une topologie (com-
mutation de circuit, commutation de paquets) ou encore dimensionner des
mécanismes sous-jacents au contrôle d’admission, tels que le routage ou le
contrôle de flux. D’une manière générale, ces mécanismes sont à la base des
méthodes de dimensionnement et d’optimisation des réseaux.
14 Introduction aux modèles d’attente dans les réseaux

1.2 Introduction au télétrafic

A la base des problèmes de dimensionnement du réseau, il faut avoir une
connaissance assez précise des lois statistiques qui gouvernent l’arrivée des
unités de données du trafic qui traversent le réseau. Cette connaissance est
importante pour la modélisation. Dans le domaine des télécommunications,
l’étude de la statistique du flux de trafic est le problème central du télétrafic.
Les modèles classiques bien connus en théorie des files d’attente supposent
que le trafic suit une loi de Poisson. Nous allons montrer dans cette section
sous quelles hypothèses cette supposition est valide. Le télétrafic est une
discipline où il existe de nombreux problèmes ouverts sur lesquels travaillent
plusieurs équipes de chercheurs dans le monde.
Nous allons d’abord introduire les processus de Poisson.

1.2.1 Processus de Poisson

A la base de ces processus stochastiques se trouvent des processus plus sim-
ples.

Processus de comptage

Ce processus qui sera noté N = {Nt ; t ≥ 0} représente un compteur qui

s’incrémente à chaque arrivée d’un client (paquet, unité de donnée, ...) dans
le système, avec Nt une variable aléatoire discrète positive qui représente le
nombre de clients arrivés dans l’intervalle (0, t] et t est une variable déterministe
réelle positive qui représente le temps. Le processus de comptage est dit sim-
ple si les arrivées sont simples. Dans ce cas le compteur s’incrémente d’une
unité juste après chaque arrivée. Les instants d’arrivée T = {Ti ; i = 1, 2, · · · }
sont supposés être aléatoires.

Processus de comptage à accroissements indépendants

Le processus de comptage N est dit à accroissements indépendants (ou encore

sans mémoire) si pour tout instant t et tout temps s, le nombre d’arrivées
dans l’intervalle (t, t + s] : Nt+s − Nt est indépendant du passé avant l’instant
t.
1.2 Introduction au télétrafic 15

Processus de comptage à accroissements stationnaires

Le processus de comptage N est dit à accroissements stationnaires si le nom-
bre d’arrivées dans un intervalle de durée s ne dépend que de la durée de
cet intervalle et non de la position de cet intervalle sur l’axe du temps. En
d’autres termes, la distribution statistique de Ns est la même que celle de
Nt+s − Nt pour tout t ≥ 0, en posant N0 = 0.

Définition d’un processus de Poisson

On appelle processus de Poisson N = {Nt ; t ≥ 0} de paramètre λ un proces-
sus de comptage simple à accroissements indépendants et stationnaires tel
que

(λt)k −λt
P{Nt = k} = e
k!

Intensité d’un processus de Poisson

Le paramètre λ est dit l’intensité du processus de Poisson. Pour interpréter
ce paramètre λ nous allons calculer le nombre moyen d’arrivées dans un
intervalle de temps (0, t]
∞
X
E[Nt ] = nP{Nt = n} = λt
n=0

Donc λ est le nombre moyen d’arrivées par unité de temps.

La variance du processus de Poisson

Nous pouvons calculer la variance des variables Nt qui se trouve être égale à
la moyenne

2
= E Nt2 − (E[Nt ])2 = λt

σN t

En d’autres termes, l’amplitude de la variation du nombre d’arrivées au-

tour de la moyenne est du même ordre que celle-ci.

Propriétés élémentaires du processus de Poisson

En utilisant la définition du processus de Poisson il est assez facile de prouver
les résultats suivants
16 Introduction aux modèles d’attente dans les réseaux

1. La probabilité qu’il n’y ait pas d’arrivée dans l’intervalle (0, t] est

P{Nt = 0} = e−λt

Pour le voir, il suffit de prendre k = 0 dans la définition du processus

de Poisson.
Par la stationnarité ce résultat est valable pour tout intervalle de temps
(s, s + t] pour tout s.

2. La probabilité qu’il ait au moins une arrivée dans l’intervalle (0, t] est

P{Nt ≥ 1} = 1 − e−λt

Par la stationnarité ce résultat est valable pour tout intervalle de temps

(s, s + t] pour tout s.

3. La probabilité qu’il y ait une seule arrivée dans un intervalle de temps

infinitésimal de durée dt est de l’ordre de λdt.

4. La probabilité qu’il y ait plus qu’une arrivée dans un intervalle de temps

infinitésimal de durée dt est de l’ordre de dt2 .

Ces deux derniers résultats traduisent le caractère ponctuel (ie arrivées

simples) du processus de Poisson.

Processus des temps inter-arrivées

Considérons à nouveau T = {Ti ; i = 1, 2, · · · } la suite des instants d’arrivée

des unités de données d’un trafic Poissonnien d’intensité λ où Ti est l’instant
de la ième arrivée. Il est possible de montrer le résultat important suivant
La distribution de probabilité des Ti+1 − Ti suivent toutes une
même loi exponentielle de paramètre λ

P{Ti+1 − Ti ≤ t} = 1 − e−λt pour i = 0, 1, 2, · · ·

En prenant par définition T0 = 0 comme instant d’origine du temps.
Partant de l’expression de la fonction de répartition, il est possible de
calculer la moyenne de l’intervalle inter-arrivée
1.2 Introduction au télétrafic 17

1
E[Ti+1 − Ti ] =
λ
De plus, il est possible de montrer que ce résultat définit le processus de
Poisson d’une manière équivalente à celle donnée ci-haut. En d’autres termes,
étant donné un processus d’arrivée dont les intervalles inter-arrivées sont
indépendants et identiquement distribués suivant une même loi exponentielle
de paramètre λ, alors le processus de comptage associé suit à son tour une
loi de Poisson d’intensité λ.

Distribution de probabilité d’Erlang d’ordre n

Nous venons de voir que la distribution de probabilité des intervalles inter-

arrivées est exponentielle de moyenne λ−1 . Il est alors possible de montrer
que la distribution de probabilité de l’instant de la nième arrivée Tn suit une
loi d’Erlang d’ordre n

n−1
X (λt)k
P{Tn ≤ t} = 1 − e−λt
k=0
k!

Pour le voir, il suffit de remarquer que

{Nt ≥ n} = {Tn ≤ t}

1.2.2 Validité de l’hypothèse Poisson dans le cas de

trafic réel
Nous allons voir que le processus de Poisson modélise bien le trafic transac-
tionnel ou encore le trafic d’appel téléphonique qui arrive sur un commutateur
de circuit.
En effet considérons n terminaux (resp postes téléphoniques) indépendants
émettant chacun avec une probabilité p une transaction (resp un appel) par
unité de temps (seconde , minute . . . ). Cette probabilité p peut être regardée
comme le taux d’activité moyen du terminal (resp du poste téléphonique) par
unité de temps. Une telle probabilité est généralement déterminée à l’heure
de pointe. Elle est en plus correctement prévisible car ce type de trafic peut
être bien décrit : nature des transactions en terme de question/réponse, durée
moyenne d’un appel téléphonique, . . .
18 Introduction aux modèles d’attente dans les réseaux

Remarquons que les hypothèses de l’indépendance des terminaux et de

l’activité moyenne identique des différents terminaux sont donc raisonnables
dans notre contexte en question : arrivées transactionnelles, appels téléphoniques.
Posons N1 = le nombre d’arrivées par unité de temps (t = 1) venant des
n terminaux
Calculons la distribution de probabilité de N1

P{N1 = k} = Cnk pk (1 − p)n−k

avec

n!
k = 1, 2, · · · , n et Cnk =
(n − k)!k!
le nombre de manières de choisir k parmi n.
En d’autres termes, la distribution de probabilité des arrivées N1 suit une
loi binomiale de paramètre p.
Supposons maintenant que le nombre de sources de trafic n augmente,
et afin d’éviter que le trafic total tende vers l’infini, nous allons supposer de
plus que l’activité individuelle p de chaque source diminue de telle manière
que trafic moyen total np reste constant np = λ.
Alors il est bien connu en théorie des probabilités que la distribution de
probabilité de la loi binomiale converge vers la distribution de Poisson de
paramètre λ. L’approximation d’une distribution binomiale par une distri-
bution de Poisson est bonne à partir de n = 20.

1.2.3 Superposition de n processus de Poisson indépendants

Soient Nj = {N(j,t) ; t ≥ 0}, j = 1, · · · , n une suite finie de n Processus de
Poisson indépendants d’intensités λj .
Posons M = {Mt ; t ≥ 0} le processus somme des n précédents :

Mt = N(1,t) + · · · + N(n,t) ; ∀t ∈ R+

Nous allons nous poser la question suivante : quelle est la distribution de

probabilité du processus M. Nous pouvons montrer que le processus M est
encore un processus de Poisson d’intensité

λ = λ1 + · · · + λn
1.2 Introduction au télétrafic 19

Donc si dans un nœud de transit d’un réseau il arrive n flux de trafic de

type Poisson, alors le flux agrégé suit aussi une loi de Poisson avec comme
intensité la somme des intensités des flux individuels.

1.2.4 Décomposition d’un processus de Poisson

Il s’agit ici du contexte dual du précédent. Supposons que le trafic de sortie N
d’un nœud de transit du réseau soit un processus de Poisson d’intensité λ et
supposons, pour fixer les idées, que ce trafic est routé vers n nœuds suivants
avec statistiquement un pourcentage de trafic p1 vers le nœud 1, · · · , et un
pourcentage de trafic pn vers le nœud n.
Bien entendu : p1 + ... + pn = 1.
En théorie de file d’attente on appelle cette opération : “échantillonnage”
ou encore “amincissement” d’un processus de Poisson par un processus de
Bernouilli.
Nous voulons déterminer la distribution de probabilité du trafic routé vers
le noeud j, j = 1, · · · , n .
Il est possible de montrer que ce trafic suit aussi une loi de Poisson
d’intensité λpj .

1.2.5 Autres modèles de trafic

Il est clair que si à la place du trafic transactionnel nous avions considéré le
trafic de transfert de fichier, par nature beaucoup plus sporadique, l’hypothèse
Poisson risque de ne pas être valable.
En réalité, l’hypothèse Poisson n’est plus bonne dès que le trafic devient
sporadique (dit ”bursty” en anglais). D’autres travaux de recherche contin-
uent à développer d’autres modèles mathématiques qui représentent mieux
les trafics sporadiques. Citons, à titre d’exemple, deux modèles importants
de source :

• Processus ON/OFF

• Processus MMPP

Processus ON/OFF
Un processus ON/OFF X est un processus de Markov {Xt ; t ∈ R+ } à temps
continue et à 2 états discrets 0, 1. Le temps de séjour de la trajectoire Xt dans
20 Introduction aux modèles d’attente dans les réseaux

l’état 0 est distribuée suivant une loi exponentielle de paramètre λ. Le temps

de séjour de la trajectoire dans l’état 1 est exponentiellement distribuée de
paramètre µ.
D’une manière intuitive, une source ON/OFF est un générateur de trafic
qui émet à débit constant pendant un temps aléatoire D1 et qui cesse toute ac-
tivité pendant un temps aléatoire D2 . La distribution de ces temps aléatoires
suivent des lois exponentielles de paramètres µ et λ. Le temps D1 est appelé
la durée d’une ”rafale” (ou encore ”burst” en anglais). Ce processus modélise
une source de voix à la sortie du décodeur.
Les études portent sur la superposition d’un nombre variable de sources
ON/OFF homogènes (distribuées suivant la même loi) ou encore hétérogènes.
On peut montrer que la superposition de n processus ON/OFF homogènes
est un processus de Markov de type “naissance et mort” à n + 1 états et on
sait calculer son générateur infinitésimal.
Des études ont montré que la superposition de sources ON/OFF peut être
utilisée pour représenter le trafic de données à faibles contraintes temporelles
(TELNET, FTP, WEB . . . ) entrant dans un multiplexeur statistique d’accès
à un réseau à commutation de paquets.

Processus MMPP
Un processus MMPP est un processus de Poisson modulée {NJt ; t ∈ R+ }
par un processus de Markov à état finis {Jt ; t ∈ R+ } appelé processus de
phase du MMPP. Soit n le nombre de phases. Quand Jt = i; i = 1, · · · , n le
processus de Poisson Ni est d’intensité λi . Les sauts d’intensité du Poisson
sont commandés par les sauts du prosessus de Markov Jt . Soit {A(i,j) ; i, j ∈
{1, · · · , n}} le générateur infinitésimal du processus Jt . Nous savons que

• A(i, i) = −qi où qi est le paramètre de la durée exponentielle de séjour

de la trajectoire Jt dans l’état i.

• A(i, j) = q(i)Q(i, j) où Q(i, j) est la probabilité de transition de Jt

entre la phase i à l’instant 0 et la phase j à l’instant T1 Q(i, j) =
P{JT1 = j|J0 = i} où T1 est le premier instant de saut de Jt après
t = 0.

Certaines études ont montré que ce modèle mathématique peut représenter

la superposition de flux voix/données à l’entrée d’un multiplexeur statistique
d’un réseau à intégration de services. D’autres études montrent l’importance
1.3 Description d’une file d’attente 21

de ce modèle pour représenter le trafic de débordement dans un réseau à

commutation de circuits.

Autres travaux
D’autres travaux récents se sont focalisés sur la caractérisation du flux de
paquets qui circulent dans le réseau dorsal de l’Internet. Ces études qui ont
été menées par des spécialistes de “BELL Labs” ont montré que le flux de
paquets IP présente un caractère très sporadique et que cette sporadicité
est visible sur différentes échelle de temps. Observée à l’échelle de temps
de la minute, de la seconde ou encore de la dizaine de milliseconde, le flux
agrégé de données présente une sporadicité similaire, d’où le terme “trafic au-
tosimilaire” pour qualifier cette caractéristique. Les modèles mathématiques
développés pour représenter ce caractère sporadique autosimilaire utilisent la
théorie des processus stochastiques de mouvements browniens fractionnaires.

1.3 Description d’une file d’attente

1.3.1 La file générique
Nous allons introduire la notation de Kendall qui représente la file d’attente
générique A/B/C/d : e. Dans ce 5-uplet

1. A représente le processus d’arrivée des unités de données (clients), il

est noté

• M (comme Markov) quand le processus suit une loi de Poisson

• D quand le processus suit une loi constante (arrivée Déterministe
ou synchrone)
• GI quand le processus suit une loi Générale Indépendante (pro-
cessus de renouvellement)
• ...

2. B représente le processus de service requis par chaque unité de donnée

(le client) au niveau du serveur, il est noté

• M (comme Markov) quand le processus suit une de loi exponen-

tielle
22 Introduction aux modèles d’attente dans les réseaux

• D quand le processus suit une loi constante (service déterministe)

• GI quand le processus suit une loi générale indépendante
• ...

3. C représente le nombre de serveurs dans la file d’attente. Ce nombre

entier varie entre 1 et l’infini.

4. d représente la capacité mémoire du système d’attente, c’est donc le

nombre maximum de clients pouvant être présents simultanément dans
le système. Ce nombre entier varie entre 1 et l’infini. Quand la capacité
mémoire de la file est considérée comme illimitée (infinie), ce paramètre
est omis.

5. e représente la discipline de service, par exemple :

• F IF O : premier arrivé premier servi (appelée aussi First Come

First Serve F CF S)
• LIF O : dernier arrivé premier servi (appelée aussi Last Come
First Serve LCF S)
• SJF : Shortest Job First ou encore servir le travail le plus court
d’abord
• SRO : Service in Random Order ou encore servir en ordre aléatoire
• ...

Ce paramètre est omis si la politique est F IF O.

1.3.2 Remarques générales

• Il existe d’autres lois d’arrivée ou de service (Erlang, hyper-exponentielle,
. . . ). Nous allons nous intéresser principalement au service M ou D.
En effet, Ces processus représentent assez raisonnablement ce qui se
passe dans les réseaux de données où le trafic échangé est principale-
ment de type transactionnel. De plus, en utilisant ces lois, nous avons
les résultats analytiques les plus complets. Notons enfin que seuls les
modèles en M sont entièrement résolus dans le cadre des réseaux de
files d’attente.
1.4 Les principaux résultats de la file M/M/1 et de ses dérivées 23

• Nous supposons toujours que les variables aléatoires en questions (inter-

arrivée, service requis) sont indépendantes identiquement distribuées
iid, et que les inter-arrivées et les services requis sont mutuellement
indépendantes. L’hypothèse iid veut dire que la théorie s’intéresse
uniquement aux comportements stationnaires dans le temps. En réalité,
l’approche adoptée va partir de l’hypothèse que le système d’attente est
stable, à savoir qu’il possède un régime stationnaire de fonctionnement
obtenu en faisant tendre le temps t vers l’infini, et d’en déduire les
conditions qui assurent la stabilité du système.

• Dans les réseaux, si l’hypothèse du trafic d’arrivée suivant une loi de

Poisson est bonne dans certains cas précis (trafic transactionnel), en
revanche la loi de service est moins bien connues. En effet, quand on
s’intéresse au temps de transmission des unités de données, très souvent
ce temps est constant ou assez peu variable pour un flux de trafic fixé
car dans la quasi totalité des réseaux un mécanisme de frangmentation
des unités de données est toujours implémenté pour découper les unités
de données en fragments de longueur constante. En revanche, si l’on
s’intéresse au temps de traitement dans l’ETTD (pour calculer par
exemple le temps de réponse), ou bien à la durée d’une communication
téléphonique, dans ces cas il n’existe pas des résultats généraux pour
caractériser la statistique du temps de service requis. Ceci étant, il est
courant de supposer que la durée d’une communication téléphonique
suit une loi exponentiellement distribuée de moyenne assez connue,
cette durée moyenne dépend de la tarification.

1.4 Les principaux résultats de la file M/M/1

et de ses dérivées
Dans toute la suite nous posons :

• λ = l’intensité du processus de Poisson des arrivées/unité de temps

(λ−1 = temps moyen inter-arrivée).

• µ = l’intensité du processus de Poisson des services/unité de temps

(µ−1 = temps de service requis moyen).
24 Introduction aux modèles d’attente dans les réseaux

△
• ρ = λ/µ = c’est le produit du taux moyen d’arrivée par le temps de
service moyen, c’est donc un facteur de charge de la file avec un seul
serveur.

L’analyse de la file M/M/1 se fait à l’aide du processus de naissance et

de mort. Nous allons nous contenter de présenter uniquement la démarche
sans rentrer dans les détails techniques.

1.4.1 Le processus de naissance et de mort

C’est un processus de Markov à états discrets dont le générateur infinitésimal
est donné par

 
−λ0 λ0 0 0 0 ···
 µ
 1 −(λ1 + µ1 ) λ1 0 0 ··· 

 0 µ2 −(λ2 + µ2 ) λ2 0 ···
 

 
 0 0 µ3 −(λ3 + µ3 ) λ3 0 
 
A= 0 0 0 µ4 −(λ4 + µ4 ) λ4 

 0 0 0 0 µ5 −(λ5 + µ5 ) 
 
 0 0 0 0 0 µ6
 

 0 0 0 0 0 0
 

. . . . . .
(1.1)
Le générateur infinitésimal est utilisé pour calculer la loi de probabilité
stationnaire du système d’attente solution du système linéaire

πA = 0
ou encore

λ0 π0 = µ1 π1
(λi + µi )πi = λi−1 πi−1 + µi+1 πi+1 avec i ≥ 1

On montre que si les conditions suivantes sont vérifiées

∞
X λ0 · · · λi−1
<∞
i=1
µ1 · · · µi
1.4 Les principaux résultats de la file M/M/1 et de ses dérivées 25

∞
X µ1 · · · µi
=∞
i=1
λ1 · · · λi
alors le processus de naissance et de mort possède une probabilité sta-
tionnaire de la forme

λ0 · · · λi−1
πi = π0 avec (1.2)
µ1 · · · µi
∞
X λ0 · · · λi−1 −1
π0 = (1 + ) (1.3)
i=1
µ1 · · · µi

Remarque 1.1. Dans toute la suite, chaque fois que l’on parle de régime per-
manent ou stationnaire du système d’attente, cela veut dire que l’on suppose
que le système d’attente possède une distribution de probabilité stationnaire
non dégénérée et que cette distribution stationnaire est supposée être prise
comme la distribution de probabilité initiale qui gouverne le comportement
dynamique du système. Intuitivement cela correspond à l’état du système
observé en faisant tendre t −→ ∞.

1.4.2 La file M/M/1

Dans ce cas

λi = λ avec i = 0, 1, · · ·
µi = µ avec i = 1, 2, · · ·

Calcule de la distribution de probabilité du nombre de client dans

le système N

La résolution du système linéaire de Kolmogorov nous permet d’obtenir la

forme analytique de la solution ainsi que la condition nécessaire et suffisante
CNS pour que cette solution existe et soit strictement positive. Cette CNS
est que ρ = λ/µ < 1. Dans ce cas cette solution stationnaire est donnée par

πk = P{N = k} = ρk (1 − ρ)
où N représente le nombre de clients dans le système en régime station-
naire. Ce qui permet de calculer la fonction génératrice de N :
26 Introduction aux modèles d’attente dans les réseaux

△
Q(z) = E z N

∞
X
= z k P{N = k}
k=0
∞
X
= z k ρk (1 − ρ)
k=0
1−ρ
=
1 − ρz

Calcul de la distribution de probabilité du temps de séjours S

Un client qui arrive dans le système en état stationnaire va donc statis-

tiquement rencontrer N clients déjà présents. Il va donc attendre un temps
W = NX correspondant au service de ces clients où X désigne le temps de
service d’un client. Il sera servi à son tour puis il quittera le système. Donc
le temps de séjour du client dans le système est :

N
X +1
S = X + NX = Xi = X + W
i=1

où les Xi sont iid suivant celle de X.

Pour calculer la distribution de probabilité de S on passe par la trans-
formée de Laplace de la densité de S :

△
S ∗ (s) = E e−sS

On commence par évaluer

h Pk+1 i
E e−sS |N = k = E e−s i=1 Xi = (X ∗ (s))k+1

En déconditionnant par rapport à N on obtient la distribution de S

1.4 Les principaux résultats de la file M/M/1 et de ses dérivées 27

S ∗ (s) = E e−sS

X∞
E e−sS |N = k P{N = k}

=
k=0
X∞
= ρk (1 − ρ)(X ∗ (s))k+1
k=0
1
= X ∗ (s)(1 − ρ)
1 − ρX ∗ (s)

Comme

µ
X ∗ (s) =
s+µ
Alors

µ(1 − ρ)
S ∗ (s) =
s + µ(1 − ρ)

Ce qui montre que S est distribuée suivant une loi exponentielle de

paramètre µ(1 − ρ) :

P{S ≤ t} = 1 − e−(µ(1−ρ)t

Comme le temps de service X est indépendant du temps d’attente dans

la file W alors :

S ∗ (s) = X ∗ (s)W ∗ (s)

Ce qui permet d’obtenir la distribution de probabilité du temps d’attente

dans la file :

1−ρ
W ∗ (s) =
1 − ρX ∗ (s)
(1 − ρ)(s + µ)
=
s + µ(1 − ρ)
28 Introduction aux modèles d’attente dans les réseaux

Calcul des moments du premier ordre

Connaissant la distribution de probabilité stationnaire de N et de S nous
pouvons calculer les moyennes suivantes :

• A partir de la fonction génératrice Q(z) ou en utilisant directement la

distribution de probabilité de N on peut calculer le nombre moyen
de clients dans le système

∞
d X
E[N] = − Q(z) |z=1= kP{N = k}
dz k=0

Ce qui donne

ρ
E[N] =
1−ρ
• En utilisant la transformée de Laplace, on peut calculer le premier
moment de S et W :

Z ∞
E[S] = tdP{S(t)}
t=0
d ∗
= − S (s) |s=0
ds
1
=
µ−λ

Z ∞
E[W ] = tdP{W (t)}
t=0
d ∗
= − W (s) |s=0
ds
ρ
=
µ−λ

• Le théorème de Little lie le nombre moyen de clients dans le système

à l’intensité du processus d’arrivée des clients et au temps de séjour
moyen du client dans le système :

E[N] = λE[S]
1.4 Les principaux résultats de la file M/M/1 et de ses dérivées 29

Ce qui permet également de calculer le temps de séjour moyen E[S].

• Le théorème de Little permet de lier également le nombre moyen de

clients en attente dans la file E[NQ ] à l’intensité du processus d’arrivée
des clients et au temps d’attente moyen du client dans la file :

E[NQ ] = λE[W ]

• Il est parfois intéressant de normaliser les délais ci-haut par rapport à

un service moyen égal à l’unité. Cela revient à diviser E[S] et E[W ]
par le temps de service moyen 1/µ. ce qui donne :

E[S] 1
=
1/µ 1−ρ
E[W ] ρ
=
1/µ 1−ρ

• Quand la charge ρ tend vers 1 le nombre moyen de clients dans le

système tend vers l’infini, il en est de même du temps d’attente moyen.

• En inversant la transformé de Laplace W ∗ (s), nous pouvons calculer la

distribution de probabilité du temps d’attente dans le système

P{W ≤ t} = 1 − ρe−µ(1−ρ)t

• Sous la condition de stabilité du système ρ < 1, et en régime permanent

le processus de sortie d’une file M/M/1 est un processus de Poisson de
paramètre λ (le même que celui du processus d’arrivée). Ce résultat
est connu comme le théorème de Burke.

1.4.3 La file M/M/m

C’est la file ayant m serveurs identiques où

λi = λ avec i = 0, 1, · · · et
µi = iµ pour i ≤ m
= mµ pour i > m
30 Introduction aux modèles d’attente dans les réseaux

La condition nécessaire et suffisante de stabilité de la file est la même

que dans le cas précédent en prenant en compte l’existence de m serveurs
identiques de même capacité µ:
λ
ρ= <1
mµ
La distribution stationnaire du nombre de clients dans le système est :
(mρ)n
P{N = n} = p0 pour n ≤ m
n!
(mm ρn )
= p0 pour n > m
m!
avec
m−1
X (mρ)k (mρ)m 1
p0 = [ +( )( )]−1
k=0
k! m! 1−ρ
qui est la probabilité que le système soit vide.
Un client qui arrive dans le système et qui trouve un nombre de client
n < m sera immédiatement servi. En revanche ce client va attendre quand
n ≥ m. Cette remarque permet de calculer la probabilité d’attente d’un
client en sommant sur toutes les probabilités stationnaires ci-dessus pour
n ≥ m. On obtient ainsi la probabilité d’attente connue sous le nom de
formule d’Erlang C

(mρ)m
P{attente} = p0
(1 − ρ)m!
nous notons cette probabilité PQ
Avec un démarche similaire à celle présentée ci-haut pour la file élémentaire
nous pouvons calculer
Le nombre moyen de clients dans le système
PQ ρ
E[N] = mρ +
1−ρ
Le temps de transit moyen dans le système E[S] et le temps d’attente
moyen dans la file E[W ]

1 PQ 1
E[S] = + = + E[W ]
µ mµ − λ µ
Les théorèmes de Little et de Burke s’appliquent également à la file
M/M/m.
1.4 Les principaux résultats de la file M/M/1 et de ses dérivées 31

Cas particulier
Considérons le cas particulier de la file M/M/2. Alors

λ
ρ=
2µ
P{N = 0} = p0
P{N = 1} = p0 2ρ = p1
P{N = k} = p0 2ρk = pk
1 1−ρ
p0 = 2 1 = < p0 |M/M/1 = (1 − ρ)
1 + 2ρ + 2ρ 1−ρ 1+ρ

1−ρ k 2ρk
pk = 2ρ = (1 − ρ) > pk |M/M/1 = (1 − ρ)ρk
1+ρ 1+ρ
D’où

1 − ρ (2ρ)2 2ρ2
PQ |M/M/2 = = < PQ |M/M/1 = ρ
1 + ρ (1 − ρ)2 1+ρ
En revanche

2ρ2 ρ 2ρ 2 ρ ρ
E[N] |M/M/2 = 2ρ+ = = > = E[N] |M/M/1
1+ρ1−ρ 1 − ρ2 1+ρ1−ρ 1−ρ

Et par la formule de Little

E[N]
E[S] |M/M/2 = |M/M/2 > E[S] |M/M/1
λ

1.4.4 La file M/M/∞

Chaque client qui arrive dans le système trouve toujours un serveur disponible
(puisqu’il en existe une infinité). Donc le client n’attend jamais. Il s’agit donc
d’un modèle de retard pur où chaque client va séjourner dans le système un
temps aléatoire qui coı̈ncide avec son propre service. Ainsi, un tel modèle
peut très bien servir pour décrire le phénomène de perte de séquence des
unités de données du trafic dans les réseaux.
Les principaux résultats de cette file s’obtiennent en partant de la file
M/M/m et en faisant tendre m vers l’infini. Ceci permet d’avoir :
32 Introduction aux modèles d’attente dans les réseaux

La loi stationnaire du nombre de clients dans le système : pour tout entier

n
( µλ )n
P{N = n} = p0
n!
En sommant sur tous les entiers et en remarquant que cette somme doit
être égale à l’unité nous pouvons déduire la probabilité p0 que le système soit
vide
λ
p0 = e−( µ )
Cela veut dire que la distribution stationnaire du nombre de clients dans
le système suit une loi de Poisson de paramètre λ/µ.
Donc le nombre moyen de clients dans le système est
λ
E[N] =
µ
et par le théorème de Little on obtient le temps de séjour moyen d’un
client
1
E[S] =
µ
qui n’est que le temps de service moyen (comme nous l’avons remarqué
au début).

1.4.5 La file M/M/m/m avec perte

Il s’agit en réalité d’un système similaire à celui de la file M/M/m à l’exception
que quand le client arrive dans le système et que le celui-ci soit plein, le client
est considéré comme perdu.
Donc la distribution de probabilité stationnaire de la file M/M/m est
la même pour les m premières probabilités, et les autres probabilités sont
identiquement nulles :

( µλ )n
P{N = n} = p0 pour n ≤ m
n!
= 0 sinon

la somme de ce probabilités doit être égale à 1 d’où

m
X ρk −1
p0 = [ ]
k=0
k!
1.5 Les principaux résultats de la file M/GI/1 33

avec ρ = λ/µ.
Le concepteur de réseau s’intéresse particulièrement à la probabilité de
perte d’un client (perte d’un appel téléphonique par exemple). Ceci a lieu
quand, lors son l’arrivée, le client trouve le système saturé. La probabilité
de cet événement est :
ρm
pm = p0
m!
Cette formule fondamentale est connue sous le nom formule Erlang B.
Elle est à la base du dimensionnement des réseaux à commutation de circuits.
En effet, le problème de dimensionnement d’un commutateur de circuits est
le suivant :

• Etant donné le trafic en nombre de communications/unité de temps

λ/µ en Erlang

• Trouver le nombre d’unités de service m tel que

• La probabilité de perte d’un appel pm soit inférieure à une certaine

valeur

La probabilité de perte pm représente la qualité de service offerte par

le réseau du point de vue de l’usager. Quant au trafic λ/µ il est estimé en
fonction de nombre de postes téléphoniques existants et/ou à venir sur la base
d’une activité moyenne par poste et par application (telephone, télécopieur,
terminal vidéotex, terminal informatique . . . ).
La formule Erlang B est un véritable outil de base pour dimesionner
réseaux qui offrent les services en mode circuit (comme la téléphonie par
exemple). Elle existe sous la forme d’abaque appelée abaque d’Erlang ou de
tables dites “tables de Palm”.

1.5 Les principaux résultats de la file M/GI/1

1.5.1 La chaı̂ne incluse
L’analyse de file d’attente M/GI/1 est plus complexe que celle de la file
M/M/1. En effet, si dans les files M/M/. nous avons pu montrer que le
nombre de clients dans le système est un processus de Markov à temps con-
tinu, ici il n’en est rien.
Notons
34 Introduction aux modèles d’attente dans les réseaux

• Yn le nombre de clients dans le système juste après le départ du nième

client.

• Xn le temps de service du nième client. Nous supposons que Xn est un

processus de renouvellement (les Xn sont iid suivant une loi générale).
En particulier, si le service est exponentiel de paramètre µ (ie nous
sommes dans le cas de la file M/M/1) alors E[Xn ] = 1/µ pour tout n.

• δk ; k ∈ N une variable entière à valeurs dans {0, 1} telle que δk = 0 si

k = 0 et δk = 1 si k = 1, 2, · · · .

• λ l’intensité du processus de Poisson d’arrivée At ; t ∈ R+ des clients

dans la file.

Alors il est facile de voir que Yn+1 et Yn sont liés par une équation de
récurrence

Yn+1 = Yn − δYn + AXn+1

Où AXn+1 est le nombre d’arrivées dans la file pendant la durée de service
du nième client. L’équation précédente montre également que Yn est une
chaı̂ne de Markov. En effet, le futur Yn+1 de la chaı̂ne après le nième départ et
son passé Yk ; k < n sont conditionnellement indépendants à la connaissance
du présent Yn de la chaı̂ne. Ainsi, le nombre de clients dans le système
juste après les instants de départ de clients est une chaı̂ne de Markov à états
discrets appelée la chaı̂ne incluse de la file M/GI/1.
L’analyse de l’équation de récurrence sur Yn permet de déterminer la
matrice de transition de la chaı̂ne incluse et de conclure que la condition
nécessaire et suffisante de stabilité du système est que ρ < 1 avec ρ = λE[X].

1.5.2 Les formules de Pollaczek-Khinchin

Les résultats importants de la file M/GI/1 sont connus sous le nom des
formules de Pollaczek-Khinchin (P-K). Ces résultats analytiques sont obtenus
directement à partir de l’analyse basée sur l’équation de récurrence de Yn et
en faisant tendre n −→ ∞.
La première série des formules de P-K donne les principaux paramètres
moyens de la file (nombre moyen de clients dans le système, les délais moyens
de transit et d’attente). Les autres formules de P-K donnent les distributions
1.5 Les principaux résultats de la file M/GI/1 35

de probabilité du nombre de clients dans le système ainsi que les transformées

de Laplace des temps d’attente et de séjour dans le système.

Les valeurs moyennes

On montre que sous la condition de stabilité ρ < 1 que le nombre moyen
de clients dans le système est

λ2 E[X 2 ]
limn−→∞ E[Yn ] = E[Y ] = ρ +
2(1 − ρ)
Par la formule de Little nous obtenons le temps de séjour moyen d’un
client dans le système

λE[X 2 ]
E[S] = E[X] +
2(1 − ρ)
Et en remarquant que ce délai se décompose en une somme du délai de
service moyen plus le délai d’attente moyen dans la file on en déduit que

λE[X 2 ]
E[W ] =
2(1 − ρ)
Il existe une autre forme utile de la formule P-K
2
ρE[X] (1 + CX )
E[S] = E[X] +
2(1 − ρ)
où
2
2 σX
CX =
(E[X])2
est le coefficient de variation de la loi de service X. En particulier, si
2
la loi de X est exponentielle alors σX = (E[X])2 = (1/µ)2 ce qui donne un
2
CX = 1.

Remarque 1.2. Nous pouvons noter une différence importante dans la for-
mule de P-K entre la file M/GI/1 et la file M/M/1. En effet, la formule de
P-K fait intervenir explicitement le moment du second ordre E[X 2 ] du service
requis. Dans le cas de la file M/M/1, seul le premier moment E[X] = 1/µ
intervient par le biais du facteur de charge ρ.

Cas Particuliers
36 Introduction aux modèles d’attente dans les réseaux

1. Service exponentiel de paramètre µ

Il est facile de montrer que dans ce cas particulier :
2
E X2 = 2

µ
Ce qui permet de retrouver les résultats de la file M/M/1, et en parti-
culier
E[W ] ρ
=
E[X] 1−ρ
2. Service constant et file M/D/1
Dans ce cas
E[X] = X = constante
et
E X2 = X2

Utilisant l’autre forme de la formule de P-K, le service étant déterministe

2 2
σX = 0 d’où CX =0
D’où

E[W ] ρ
=
E[X] 2(1 − ρ)
Cela veut dire que le délai d’attente dans la file M/D/1 est moitié
moins grand que dans une file M/M/1.
On peut aussi montrer qu’il en est de même pour le nombre de clients
dans le système ou dans le file d’attente.
La deuxième forme de la formule de P-K montre que parmi toutes les
files M/GI/1 c’est la file M/D/1 qui minimise E[S] (donc E[N]) car
2
c’est la file pour laquelle CX = 0 (est minimum).
Ce résultat a une portée plus générale : ”pour diminuer le délai il faut
diminuer l’aléa”. Les systèmes qui sont entièrement déterministes (la
file D/D/1) n’ont pas d’attente du tout !... Ces systèmes sont ceux
rencontrés en transmission audio sur des réseaux à commutation de
circuit.
Une des conséquences de cette remarque est que la file M/M/1 peut
être regardée comme une approximation pessimiste d’une file M/D/1.
1.5 Les principaux résultats de la file M/GI/1 37

La distribution du nombre de clients dans le système

En notant
∞
△ X
Qn (z) = E z Yn = P{Yn = k}z k
k=0

Q(z) = limn−→∞ Qn (z)

alors il est possible de prouver que

(1 − ρ)(1 − z)
Q(z) = X ∗ (λ − λz)
X ∗ (λ − λz) − z
avec X ∗ (s) la transformée de Laplace de la loi (densité) du temps de
service.
En particulier, pour la file M/M/1
µ
X ∗ (λ − λz) = |(s=λ−λz)
µ+s
Ce qui donne
1−ρ
Q(z) =
1 − ρz

La distribution des délais dans le système

La politique de service étant de type FIFO et en supposant toujours que
ρ < 1, alors le nombre de clients en régime stationnaire Y dans le système
qui restent après le départ d’un client générique (ie quand n −→ ∞) coı̈ncide
avec le nombre d’arrivées pendant la durée de séjour S du client générique
dans le système. D’où

E z AS = Q(z)

Or il est facile de voir que

E z AS = S ∗ (λ − λz)

ce qui donne après un changement de variable l’expression analytique de

la transformée de Laplace du temps de séjour dans le système
38 Introduction aux modèles d’attente dans les réseaux

s(1 − ρ)
S ∗ (s) = X ∗ (s)
s − λ + λX ∗ (s)
Pour obtenir l’expression de la distribution du temps d’attente W en
régime stationnaire on part de

S =W +X
or W ⊥⊥ X donc S ∗ (s) = W ∗ (s)X ∗ (s) ce qui donne

s(1 − ρ)
W ∗ (s) =
s − λ + λX ∗ (s)

1.5.3 La période d’activité et le cycle de fonctionnement

Nous allons noter BP(n) et BP respectivement la période d’activité de
condition initiale n et la période d’activité élémentaire définies par

Inf {t > 0, Yt = 0 | Y0− = n + 1, Y0 = n} si ρ < 1
BP(n) =
∞ si ρ ≥ 1

Inf {t > 0, Yt = 0 | Y0− = 0, Y0 = 1} si ρ < 1
BP =
∞ si ρ ≥ 1
Intuitivement, une période d’activité élémentaire représente le temps qui
sépare l’instant d’arrivée d’un client dans un système vide de l’instant de
départ du dernier client du système laissant derrière lui une file d’attente
vide.
Alors

• Il est possible de prouver que la distribution de probabilité de BP(n)

est un produit de convolution d’ordre n de celle de BP . Donc la con-
naissance de la distribution de BP suffit pour calculer celle de BP(n)
pour tout n.

• En notant par G∗ (s) la transformée de Laplace de la loi (densité) de

BP , on peut montrer que

G∗ (s) = X ∗ [s + λ − λG∗ (s)]

1.6 Les réseaux de files d’attente à forme produit 39

D’où la transformée de Laplace de la loi (densité) de BP(n)

G∗(n) (s) = (X ∗ [s + λ − λG∗ (s)])n

La période d’activité joue un rôle fondamental dans l’étude des systèmes

(files) de priorité.
On définit une période d’inactivité comme l’intervalle de temps I
séparant l’instant de départ du dernier client du système (laissant derrière
lui une file d’attente vide) de l’instant d’arrivée du prochain client qui com-
mence une nouvelle période d’activité. Dans une file M/GI/1, le processus
du temps interarrivée des clients est exponentiel de paramètre λ, donc

P{I ≤ t} = 1 − e−λt
On définit un cycle de fonctionnement C comme la somme

C = I + BP
Ce qui permet de calculer la transformée de Laplace de la loi de C.
Compte tenu du fait que le processus d’arrivée est indépendant de l’état
de la file d’attente, alors I ⊥⊥ BP et

C ∗ (s) = I ∗ (s)G∗ (s)

Soit

λ
C ∗ (s) = X ∗ [s + λ − λG∗ (s)]
λ+s
Remarque 1.3. Malheureusement il n’y a pas l’équivalent du théorème de
Burke pour les files M/GI/1 qui ne garantissent absolument pas la conser-
vation du caractère Poissonnien des flux entrants.

1.6 Les réseaux de files d’attente à forme pro-

duit
1.6.1 Introduction
Nous allons étudier une classe importante de réseaux de files d’attente très
utilisée dans les applications des problèmes d’optimisation des réseaux. Cette
40 Introduction aux modèles d’attente dans les réseaux

classe est appelée Réseaux de Jackson du nom du mathématicien qui les

a étudié à la fin des années cinquante.
Plus tard au milieu des années soixante dix quatre spécialistes de files
d’attente : [Link], [Link], [Link] et [Link], dans un
article paru dans le Journal of ACM ont généralisé les resultats de Jack-
son en relaxant certaines contraintes sur les lois de service. Ces réseaux
généralisés sont appelés Réseaux BCMP suivant les initiales des quatre
mathématiciens.
Les réseaux de Jackson et leur généralisation avec les réseaux BCMP
appartiennent à la classe des réseaux Markoviens à forme produit basés pric-
ipalement sur les files d’attente M/M/. , avec éventuellement des variantes
particulières de service pour les réseaux BCMP. En ce sens que leur comporte-
ment, en terme du nombre de clients dans le réseau, et sous la condition de
stabilité du système, est décrit par une distribution de probabilité discrète
qui se factorise en produit de probabilités marginales. Chacune de ces prob-
abilité marginale est celle d’une file M/M/. qui représente chaque nœud du
réseau. Cette factorisation traduit donc une indépendance statistique en-
tre les différents nœuds du réseau. Tout se passe donc, sous la condition
de stabilité du réseau, comme si chaque nœud se comporte indépendament
de l’autre. La distribution de probabilité du vecteur aléatoire du nombre
de client dans le réseau s’obtient en composant les probabilités marginales
des différentes composantes du vecteur. La conséquence importante de cette
factorisation est de simplifier considérablement le problème numérique.
Nous avons vu au paragraphe précédent que la file M/M/1 est ”pes-
simiste” en terme de nombre de clients dans le système ou en terme de délai.
Comme le service de transmission des unités de données dans un réseau
téléinformatique manipule très souvent des unités de données de longueur
constante, alors la modélisation des réseaux de données à l’aide des réseaux
de Jackson donne une ”estimation pessimiste” du comportement du réseau.
Cette conclusion a été validée par des simulations et par l’observation des
réseaux réels existants. Par ailleurs, comme la file M/D/1 ne préserve pas
le caractère Poissonnien, nous tombons vite dans le cadre de la théorie des
réseaux de file d’attente de type GI/GI/1 où nous n’avons pas de résultats
généraux.
En conclusion, le modèle de type ”réseau de Jackson ou encore BCMP”
va être un outil pour étudier analytiquement les réseaux à commutation de
paquets. Ces modèles donneront des résultats pessimistes en termes de temps
1.6 Les réseaux de files d’attente à forme produit 41

de transit ou de nombre de clients dans le réseau. Pour affiner l’étude, on

peut recourir dans un deuxième temps à la simulation. Tous les logiciels
d’optimisation des réseaux de commutation de paquets (et de circuits) sont
basés sur ces modèles à forme produit.

1.6.2 Les réseaux de Jackson

Nous allons d’abord décrire les réseaux de Jackson. Nous donnerons ensuite
la forme de la distribution de probabilité du nombre de clients dans le réseau.
Il existe deux classes de réseaux de Jackson :

• Les réseaux ouverts

• Les réseaux fermés

Les réseaux fermés ne communiquent pas avec le monde extérieur et contien-

nent une nombre fini de clients qui tournent en permanence dans le réseau.
Nous verrons dans le chapitre consacré au contrôle de flux une modélisation
du mécanisme de la fenêtre utilisant un réseau fermé.
En télécommunication, les réseaux ouverts sont largement utilisés pour
modéliser le routage. En effet, ces réseaux communiquent avec le monde
extérieur, et peuvent potentiellement contenir un nombre illimité de clients.
Pour décrire les réseaux de Jackson nous devons spécifier

1. Le nombre de nœuds du réseau

Soit n le nombre de nœuds, quand nous considérons un réseau de Jack-
son ouvert le monde extérieur sera considéré comme un n + 1 ième
nœud et sera désigné par o

2. Description de chaque nœud

Chaque nœud i est une file d’attente avec un service exponentiel de
moyenne 1/µi . Le nœud peut contenir mi serveurs, mi = 1, 2, · · · ∞,
qui seront supposés avoir une capacité de service identique.

3. La topologie du réseau en termes de règles de routage entre

les nœuds
Elle est définie par une matrice qui donne pour chaque nœud i la prob-
abilité pij de router une unité de donnée (en d’autres termes le pour-
centage de trafic qui sera routé . . . ) vers chaque nœud j du réseau.
42 Introduction aux modèles d’attente dans les réseaux

pio 6
pjo
6

λoj 6
pij -
-
? - -
j

- i -
λoi 6
@
@
@
pik @
6 @
pko @
6 @R
@

?
- -

- k
pno
? 6
λon
-
? -
- n -

-
6
pmn

λom 6
-
- -
- m
-
6
6 pmo

?
pjm

Figure 1.1: Réseaux de Jackson

1.6 Les réseaux de files d’attente à forme produit 43

Dans le cas d’un réseau ouvert, le routage vers l’extérieur du réseau

sera effectué avec la probabilité pio . Donc, les règles de routage sont
données par une matrice stochastique (ie une matrice où, pour un indice
de ligne fixé, la somme des colonnes est égale à 1)

 
p11 p12 ··· · · · p1n p1o

 p21 p22 ··· · · · p2n p2o 

M = ··· ··· ··· ··· ··· ···
 

 
 . . . . . . 
pn1 pn2 ··· · · · pnn pno

avec

n
X
pio + pij = 1; avec i = 1, · · · , n
j=1

On suppose que les règles de routage sont indépendantes de l’état du

réseau. Cette supposition est valable en régime stationnaire, ie en de-
hors du fonctionnement à forte charge (congestion) ou des pannes des
nœuds ou des liaisons.

4. La statistique du trafic qui vient de l’extérieur du réseau

(réseau ouvert)
Chaque nœud i peut recevoir un trafic extérieur suivant une loi de
Poisson de paramètre λoi

Ayant précisé toutes ces hypothèses, il est clair que le réseau de files
d’attente sera stable si et seulement si chacun des n nœuds du réseau l’est.
Pour vérifier la stabilité d’un nœud nous avons besoin de calculer le trafic
total qui le traverse venant de l’extérieur (si le réseau est ouvert) et en transit
à partir des autres nœuds.

Les équations de trafic

Etant donnée la matrice de routage M et le trafic extérieur éventuel

arrivant sur le nœud, nous pouvons écrire les équations de trafic pour un
réseau ouvert en chaque nœud i
44 Introduction aux modèles d’attente dans les réseaux

n
X
λi = λoi + λj pji avec i = 1, · · · , n
j=1

Bien entendu dans le cas d’un réseau fermé nous avons λoi ≡ 0 pour
tous les nœuds i. Les équations de trafic pour un réseau fermé expriment
donc simplement que pour chaque nœud i il y a la conservation du flux entre
le trafic qui sort du nœud (premier membre) et trafic qui arrive au nœud
(second membre)
X X
λi pij = λj pji
j6=i j6=i

Connaissant le trafic total qui arrive à un nœud, la condition de stabilité

du nœud s’énonce simplement comme :

λi
∀i = 1, · · · , n; <1
mi µi
avec mi = 1, 2, · · · (éventuellement si le nœud contient plusieurs serveurs)
Il existe un théorème qui décrit le processus de sortie d’un réseau de file
d’attente ouvert.

Proposition 1.1. théorème de Burke pour les réseaux de file d’attente

ouverts
Sous la condition de stabilité du réseau de Jackson ouvert, en régime
permanent, le processus de sortie du réseau est Poissonnien.

Posons N = (N1 , · · · , Nn ) le vecteur aléatoire représentant le nombre de

clients dans les n nœuds du réseaux.
Nous avons le résultat important suivant

Proposition 1.2. Théorème de Jackson

Sous la condition de stabilité du réseau de file d’attente : ρi < 1 ∀i

• Réseaux ouverts
La distribution de probabilité stationnaire du nombre de clients dans le
réseau se factorise en un produit de probabilités marginales

P{N1 = k1 , · · · , Nn = kn } = P{N1 = k1 } · · · P{Nn = kn }

1.6 Les réseaux de files d’attente à forme produit 45

chacune de ces probabilités marginales P{Ni = ki } étant définie par

bi λki i
P{Ni = ki } =
µi(1) · · · µi (ki )

avec bi une constante de normalisation satisfaisant

∞
1 X λki
=
bi k=0
µi (1) · · · µi(k)

et µi(l) la capacité de service offerte par le nœud i quand le nombre de

clients présents dans le nœud est l, le trafic entrant λi dans les nœuds
i est donné par les équations de trafic definies ci-dessus.

• Réseaux fermés
La distribution de probabilité stationnaire se met sous la forme

λk11 λknn
P{N1 = k1 , · · · , Nn = kn } = BK ···
µ1 (1) · · · µ1 (k1 ) µn (1) · · · µn (kn )

où BK est une constante de normalisation définie par

X λk11 λknn
BK = [ ··· ]−1
K
µ1 (1) · · · µ1 (k1 ) µn (1) · · · µn (kn )

avec K = k1 + · · · + kn représentant le nombre fini de clients dans le

réseau fermé.

Remarque 1.4. Dans le cas d’un réseau fermé, comme le nombre de clients
dans le réseau est fini, les longueurs de files d’attente ne sont pas indépendante.
Donc, stricto senso, nous n’avons pas une forme produit car la loi ne se fac-
torise pas en produit de probabilités marginales.

Cas particulier du théorème de Jackson (réseau ouvert)

Supposons pour simplifier l’écriture que toutes les files d’attente sont de
type M/M/1 dans le réseau alors ∀i µi (k) = µi ∀k,
∞
X λk X ∞
1 i 1
= k
= ρki =
bi µ
k=0 i k=0
1 − ρi
46 Introduction aux modèles d’attente dans les réseaux

Alors la distribution marginale est donnée par

P{Ni = k} = ρki (1 − ρi ); i = 1, · · · , n
A partir de la distribution marginale de la file i nous pouvons calculer le
nombre moyen de client dans la file et, par le théorème de Little, le délai de
transit moyen dans le nœud i. Ainsi, pour une route donnée dans le réseau,
il est possible, en sommant sur les délais de transit des nœuds de la route,
de calculer le temps de transit moyen le long de cette route.

1.6.3 La généralisation des réseaux de Jackson : les

réseaux BCMP
[Link], [Link], [Link] et [Link] ont montré que la dis-
tribution de probabilité du nombre de paquets dans le réseau se factorise en
forme produit sous des conditions plus générales que dans le théorème de
Jackson :

1. Nombre fini de classes k de paquets, chaque classe suit un service expo-

nentiel de paramètres {µji }; i = 1, · · · , n; j = 1, · · · , k pour un réseau à
n nœud et k classes.

2. Dans le cas d’une seule classe de paquets les files d’attentes suivantes :

• M/GI/1 avec la politique ”processor sharing”

• M/GI/∞
• M/GI/m avec la politique LIF O et priorité ”preemptive resume”

On impose également une contrainte mathématique technique sur la trans-

formée de Laplace du service requis.
Nous appelons politique ”processor sharing” une politique de partage du
serveur entre les clients présents dans le système. Pour fixer les idées, si dans
le système, à un instant t il y a x clients présents, alors sur une seconde de
temps chaque client va recevoir un service de 1/x secondes. Les clients sont
servis cycliquement. Il est donc clair que cette politique est du type ”partage
du temps”, et le temps du processeur alloué à un client par unité de temps
est variable en fonction du nombre de clients présents dans le système.
Nous appelons politique LIF O ”preemtive resume” une politique où la
priorité est donnée au dernier client qui arrive. Le client le plus prioritaire
1.6 Les réseaux de files d’attente à forme produit 47

va interrompre le client en cours de service. Mais le service déjà alloué à un

client n’est pas perdu. Le service du client interrompu reprend au point où
l’interruption a eu lieu.
En guise de commentaire sur ces services généraux, il est clair qu’ils ne
sont pas très adaptés à la modélisation des réseaux de commutation par
paquets. En revanche la possibilité de prendre en compte plusieurs classes
de clients permet de modéliser des trafics (de service exponentiellement dis-
tribué) de natures différentes (par exemple trafic paquets X25 et trafic data-
gramme).
48 Introduction aux modèles d’attente dans les réseaux
Chapter 2

La file M/GI/1 multiclasse

2.1 La chaı̂ne incluse

Dans ce qui suit, supposons qu’il y a n classe de clients qui arrivent dans la file
et que ce nombre n est fini. Nous supposons le processus d’arrivée de la classe
i est Poisson d’intensité λi , i = 1, · · · , n. Nous supposerons que les processus
de Poisson des différentes classes i sont mutuellement indépendants. Ce qui
permet de déduire que le processus agrégé des arrivées suit également une
P
distribution de Poisson d’intensité λ = i λi . On note Xi le service requis
par la classe i. Ce service suit une distribution GI de moyenne E[Xi ] = µ1i .
On pose

λi
pi =
λ

ρi = λi E[Xi ]

n
△
X
E[X] = pi E[Xi ]
i=1
n n
△
X X
ρ= ρi = λi E[Xi ] = λE[X]
i=1 i=1

pi s’interpête comme la probabilité qu’une arrivée oit de type i. X est

une variable aléatoire auxiliaire qui a une espérance égale au service moyen
pondéré de toute les classes.
Dans ce qui suit, nous désignons par
50 La file M/GI/1 multiclasse

• Y la variable aléatoire “nombre de clients dans le système” en régime

stationnaire.
△
• Q(z) = E z Y la fonction génératrice de Y .

• W le temps d’attente dans la file d’un client en régime stationnaire,

notons que ce délais est le même pour toutes classes à cause de la
politique de service FIFO.

• Si le temps de séjour d’un client de la classe i. Ce temps est égal

S i = W + Xi .

• W ∗ (s) = E e−sW la transformée de Laplace de la distribution de W .

• Si∗ (s) = E e−sSi la transformée de Laplace de la distribution de Si .
Il est clair que la file d’attente admet un régime stationnaire ssi ρ < 1.
Soit Yk le nombre de clients dans la file d’attente juste après le départ du
ieme
k client. Le nombre de clients dans la file d’attente après le départ du
client (k + 1), Yk+1, est donné par l’équation d’état suivante : (figure ??):

Yk+1 = Yk − δYk + AXk+1

où :
• δYk avec k ∈ N est une variable entière à valeurs dans {0, 1} telle que
δYk = 0 si Yk = 0 et δYk = 1 si Yk = 1, 2, · · · .

• AXk+1 est le nombre d’arrivées dans la file pendant la durée de service

du (k+1)ième client.
Conditionnellement à la connaissance du présent Yk juste après le départ
d’un client, le futur Yk+1 est indépendant du passé Yk−1 à cause de caractère
Markovien du processus de Poisson des arrivé[Link] Yk est bien une chaı̂ne
de Markov dite lla chaı̂ine incluse de la file M/GI/1 multiclasse.

2.2 Etude du nombre d’arrivées durant le ser-

vice d’un client
Dans la variable AX il y a trois aléas : la classe de service, la
durée du service et le nombre d’arrivées. Le calcul de la fonction
génératrice E z Ax se fera en deux étapes.

2.2 Etude du nombre d’arrivées durant le service d’un client 51

La première étape consiste à calculer la probabilité que le nom-

bre d’arrivées dans la file durant la durée de service du client (k +1)
soit égal à m :

n
X
P (AXk+1 = m) = P (Xk+1 de type Xi )P (AXi = m)
i=1

Or
∞
(λt)m −λt
Z
P{AXi = m} = e dXi (t)
0 m!
et

P{Xk+1 detype Xi } = pi

d’où

n ∞
(λt)m −λt
X Z
P{AXk+1 = m} = pi e dXi (t)
i=1 0 m!

A partir de ces probabilités, il est possible de calculer directe-

ment le nombre
h moyen
i d’arrivées E AXk+1
ainsi que la fonction
génératrice E z AXk+1 .

∞ n ∞
(λt)m −λt
X X Z

E AXk+1 = m pi e dXi (t) (2.1)
m=1 i=1 0 m!
n ∞ ∞
λi (λt)m −λt
X Z X
= m e dXi (t)
i=1 0 m=1
λ m!
n Z ∞ ∞
X λi X (λt)m−1
= (λt)e−λt ( )dXi(t)
i=1 0 λ m=1
(m − 1)!
Xn Z ∞ n
X
= λi tdXi (t) = λi E[Xi ] = ρ
i=1 0 i=1

Comme dans la file M/GI/1, le nombre moyen d’arrivées pendant

un service est égale à ρ. La stabilité de la file requiert que ce
nombre soit < 1.
52 La file M/GI/1 multiclasse

D’autre part, fonction génératrice de AXk+1

∞ n Z ∞
h
AXk+1
i X
m
X (λt)m −λt
E z = z pi e dXi (t) (2.2)
m=0 i=1 0 m!
n Z ∞ ∞ m
m (λt)
X X
−λt
= pi e z dXi (t)
i=1 0 m=0
m!
X n Z ∞
= pi e−t(λ−λz) dXi (t)
i=1 0

Xn
= pi Xi∗ (λ − λz)
i=1

2.3 La fonction génératrice du nombre de clients

dans le système
Revenons maintenant à l’équation d’état de la chaı̂ne incluse pour
calculer la fonction génératrice du nombre de clients dans le système
en régime stationnaire.
h i
E z Yk+1 = E z Yk −δYk E z AXk+1

Or,
∞
X
Y −δ 0
E z k Yk
= z P{Yk = 0} + z m−1 P{Yk = m} (2.3)
m=1
Yk

− P{Yk = 0}
E z
= P{Yk = 0} +
z
En faisant tendre k −→ ∞, et sous la condition que ρ < 1 on
obtient :

Q(z) = limk−→∞ E z Yk+1 = limk−→∞ E z Yk

(2.4)
n
Q(z) − π0 X
= [π0 + ] pi Xi∗ (λ − λz)
z i=1

avec π0 = 1 − ρ Finalement, nous obtenons :

(1 − ρ)(1 − z) ni=1 pi Xi∗ (λ − λz)

P
Q(z) = Pn ∗
i=1 pi Xi (λ − λz) − z
2.4 Les formules de Pollaszek-Khintchine 53

2.4 Les formules de Pollaszek-Khintchine

Pour calculer le nombre moyen de clients dans le système, il suffit
de calculer
d
Q(z) |z=1= E[Y ]
dz
On peut aussi partir directement de l’équation d’état de la
chaı̂ne incluse en passant les deux membres au carré et en prenant
l’espérance de chaque membre.

2 h i
E Yk+1 = E Yk2 + δY2k + A2Xk+1 − 2Yk δYk + 2Yk AXk+1 − 2δYk AXk+1

Lorsque k tend vers l’infini, Yk et Yk+1 tendent vers Y . D’autre

part,
E[δYk ] = P (Yk > 0) = 1 − π0 = ρ
En simplifiant, on obtient :
h i
E A2Xk+1 − ρ
E[Y ] = ρ +
2(1 − ρ)
h i h i
A
Calculons maintenant E A2X(k+1) . Pour ce faire, évaluons E z X(k+1) .
h i Xn
AX(k+1)
E z = pi Xi∗ (λ − λz)
i=1

d 2 AX.
|z=1 = E A2X. − ρ

2
E z (2.5)
dz
n
X d2
= pi 2 Xi∗ (λ − λz) |z=1
i=1
dz
n
X
= pi λ2 (σX
2
i
+ (E[Xi ])2 )
i=1
Xn
2
= λλi (σX i
+ (E[Xi ])2 )
i=1

Ce qui donne la formule de Pollaszek-Khintchin pour la longueur

moyenne de la file :
54 La file M/GI/1 multiclasse

Pn 2 Pn
λ i=1 λi (σX + (E[Xi ])2 ) i=1 λi E[Xi2 ]
E[Y ] = ρ + i
=ρ+λ
2(1 − ρ) 2(1 − ρ)

Or, le temps de séjour moyen E[Si ] d’un client de classe i s’exprime

comme :

E[Si ] = E[Xi ] + E[W ]

En décomposant E[Y ] :

n Pn
X λi E[Xi2 ]
i=1
E[Y ] = ρi + λ (2.6)
i=1
2(1 − ρ)
n Pn
X λi E[Xi2 ]
= λ pi E[Xi ] + λ i=1
i=1
2(1 − ρ)
n P n 2
i=1 λi E[Xi ]
X
= λ( pi E[Xi ] + )
i=1
2(1 − ρ)
n Pn
X λi E[Xi2 ]
= λ( pi (E[Xi ] + i=1 ))
i=1
2(1 − ρ)
n
X
= λ( pi E[Si ])
i=1

Définissons
n
△
X
E[S] = pi E[Si ]
i=1
avec
Pn
λi E[Xi2 ]
i=1
E[Si ] = E[Xi ] + (2.7)
2(1 − ρ)
= E[Xi ] + E[W ]

Ce qui fait apparaı̂tre la formule de Little

E[Y ] = λE[S]
et
2.5 Analyse de la distribution du délai 55

Pn 2
i=1 λi (σX + (E[Xi ])2 )
E[S] = E[X] + i
(2.8)
2(1 − ρ)
= E[X] + E[W ]
Xn
= pi E[Si ]
i=1

et donc le temps d’attente moyen dans la file :

Pn 2
i=1 λi (σX + (E[Xi ])2 )
E[W ] = i
(2.9)
2(1 − ρ)

2.5 Analyse de la distribution du délai

Soit AS le nombre d’arrivées pendant la durée de séjour S du paquet
générique (c-à-d quand n −→ ∞) dans le système.
La politique de service étant de type FIFO et en supposant tou-
jours que ρ < 1, alors le nombre de paquets en régime stationnaire
Y dans le système qui restent après le départ d’un paquet générique
coı̈ncide avec le nombre d’arrivées pendant la durée de séjour S du
paquet générique dans le système, AS . D’où :

AS = Y (2.10)
Exprimée avec les fonctions génératrices
Pn ∗
A (1 − ρ)(1 − z) i=1 pi Xi (λ − λz)
E z S = Q(z) = Pn ∗
i=1 pi Xi (λ − λz) − z

En procédant de la même manière que celle utilisée lors du calcul

de la fonction génératrice de AX , on obtient

E z Y = E z AS

(2.11)
Xn
E Z AS | S de type i pi

=
i=1
Xn
pi E Z A S i

=
i=1
56 La file M/GI/1 multiclasse

E z ASi = Si∗ (λ − λz)

Donc,
n
X
Y
pi E z A S i

E z = (2.12)
i=1
Xn
= pi Si∗ (λ − λz)
i=1
(1 − ρ)(1 − z) ni=1 pi Xi∗ (λ − λz)
P
= Pn ∗
i=1 pi Xi (λ − λz) − z

Pour obtenir l’expression de la distribution du temps d’attente

W en régime stationnaire, on part de

S i = W + Xi
Or, W ⊥⊥ Xi . Ce qui donne ∀i :

Si∗ (s) = W ∗ (s)Xi∗ (s)

Faisons un changement de variable en remplaçant s par λ − λz.
L’équation 2.13 devient :

Si∗ (λ − λz) = W ∗ (λ − λz)Xi∗ (λ − λz)

Donc,
n
X n
X
pi Si∗ (λ − λz) = pi W ∗ (λ − λz)Xi∗ (λ − λz) (2.13)
i=1 i=1

(1 − ρ)(1 − z) ni=1 pi Xi∗ (λ − λz)

P
= Pn ∗
(2.14)
i=1 pi Xi (λ − λz) − z
Donc,
(1 − ρ)(1 − z) ni=1 pi Xi∗ (λ − λz)
P
∗ 1
W (λ − λz) = Pn ∗
Pn ∗
(2.15)
i=1 pi Xi (λ − λz) i=1 pi Xi (λ − λz) − z

Exprimons W ∗ en fonction de s, nous obtenons alors :

s(1 − ρ)
W ∗ (s) = (2.16)
s − λ + ni=1 λi Xi∗ (s)
P
Chapter 3

Files de Priorité

3.1 Le modèle
On suppose que les paquets arrivant à un nœud appartiennent à
des classes de priorité numérotées 1, 2, · · · , π < ∞ , et que la priorité
entre les classes est une fonction croissante du numéro de classe.
On suppose aussi que les paquets appartenant à une même classe
p soient servis sur une base FIFO.
Le processus d’arrivée des paquets est supposé être Poisson, et
le service requis être de type GI. Ainsi, le nœud de service est
modélisé par une file M/GI/1.
Soient :

• λp = l’intensité du processus d’arrivée des paquets de priorité

• Xp = le service requis par un paquet de priorité p,

On suppose que les processus d’arrivée et de service, pour les

différentes priorités, soient indépendants entre eux.
Ainsi on définit :

π
X
λ= λp
p=1

qui représente l’intensité du trafic total entrant,

58 Files de Priorité

π
X λp
E[X] = E[Xp ]
p=1
λ

π
X
ρ = λE[X] = ρp
p=1

où ρp = λp E[Xp ]
Dans un système stable ρ < 1, le trafic moyen entrant par unité
de temps est égal au trafic moyen sortant du système par unité de
temps. ρ s’interprête comme la fraction moyenne par seconde de
temps où le serveur est occupé. Ou encore, 1 − ρ est la probabilité
que le serveur soit libre. Ceci permet d’interprêter ρp comme la
fraction moyenne par unité de temps allouée par le serveur à la
priorité p.
Nous allons distinguer deux politiques de service de priorité :

• Politique non préemptive : le paquet en cours de service n’est

pas interrompu par les paquets de priorité supérieure qui ar-
rivent au cours de son service,

• Politique préemptive : le paquet en cours de service est inter-

rompu par les paquets de priorité supérieure qui arrivent au
cours de son service. Dans ce cas nous distinguons deux pos-
sibiliés pour le paquet ayant subi une interruption de service
:

Politique ”preemptive resume” : Le service du

paquet interrompu reprend au point d’interruption,
Politique ”preemptive repete” : Le service du pa-
quet interrompu reprend dès de début, le service déjà
alloué est perdu. Cette politique ne conserve pas le
travail.

Dans toute la suite, nous allons considérer uniquement les poli-

tiques de service qui conserve le travail.
3.2 Analyse du délai d’attente 59

3.2 Analyse du délai d’attente

L’analyse du délai d’attente, qui sera faite dans ce paragraphe, est
valable pour une classe de services plus large que celle des systèmes
de priorité.
Soient :

• Wp = le délai d’attente d’un paquet dans la file de classe p,

• Sp = le temps de séjour dans le système d’un paquet de classe

p. Nous avons Sp = Wp + Xp .

Dans le cas général, Wp se décompose en 3 parties :

• le délai dû au paquet en cours de service à l’instant d’arrivée

: W0 ,

• le délai dû aux paquets déjà présents dans la file à l’instant

d’arrivée,

• le délai dû aux paquets arrivant dans la file après l’instant

d’arrivée (i.e. les paquets de priorité supérieure);

3.2.1 Calcul du délai moyen d’attente

Nous allons d’abord calculer le délai moyen d’attente d’un paquet
de classe p dans la file.
La loi de service étant de type GI, nous savons, grâce à la théorie
de renouvellement, que le temps de service résiduel moyen d’un
client de priorité i est donné par

E[Xi2 ]
2E[Xi ]
D’autre part, ρi s’interprête également comme la probabilité que
le serveur soit occupé par un paquet de classe i, donc nous pouvons
écrire : π π
X E[Xi2 ] X λi E[Xi2 ]
E[W0 ] = ρi = (3.1)
i=1
2E[X i ] i=1
2
Considérons un paquet générique de classe p qui arrive dans le
système. Soient :
60 Files de Priorité

• Nip = nombre de paquets de classe i dans la file et recevant le

service avant le paquet de classe p,

• Mip = nombre de paquets de classe i arrivant dans la file après

l’instant d’arrivée du paquet de classe p et recevant le service
avant celui-ci.
Nous pouvons donc écrire :
π
X
E[Wp ] = E[W0 ] + E[Xi ] (E[Nip ] + E[Mip ]) (3.2)
i=1

Pour déterminer E[Wp ] on procède en deux temps : on com-

mence d’abord par calculer E[Nip ] et E[Mip ], puis, connaissant E[W0 ],
on en déduit E[Wp ]. En général E[Nip ] et E[Mip ] s’expriment en fonc-
tion de E[Wi ]. Les moment d’ordre supérieur sont généralement
difficiles à obtenir.

3.2.2 Cycle de délai

Nous allons effectuer l’analyse du cycle de délai qui généralise celle
de la période d’activité.
Nous allons noter ce cycle par Yc qui sera par définition composé
comme la somme de

• Y0 = délai initial correspondant à la complétion de services

partiellement effectués,

• Yb = délai correspondant à la période d’activité engendrée par

Y0 .

En somme :

Yc = Y0 + Yb (3.3)
Yc est bien une généralisation de la période d’activité élémentaire
que nous avons analysée lors de l’étude de la file M/GI/1/./F IF O.
En effet dans le cas de la période d’activité élémentaire, Y0 n’est
autre que le temps de service X d’un client.
Soient Y0 (y) ,Yb (y) et Yc (y) les fonctions de répartition de Y0 ,
Yb et Yc ; Y0∗ (s) , Yb∗ (s) et Yc∗ (s) respectivement les transformées de
3.2 Analyse du délai d’attente 61

Laplace (TL) des densités. Soient X ∗ (s) et G∗ (s) respectivement les

TL des densités de la loi de service X et de la période d’activité
élémentaire BP .
Nous allons calculer Yb∗ (s) et Yc∗ (s) en fonction de Y0∗ (s). Rap-
pelons que G∗ (s) et X ∗ (s) sont liées par

G∗ (s) = X ∗ (s + λ − λG∗ (s))

Pour calculer Yc∗ (.) et Yb∗ (.) on procède de la même manière que
dans le cas de G∗ (s).
Soit N0 le nombre de paquets arrivés pendant l’intervalle initial
Y0 , alors

E e−sYb | Y0 = y, N0 = n = [G∗ (s)]n

Alors

∞
−sY X
E e−sYb | Y0 = y, N0 = n P{N0 = n | Y0 = y}

E e b
| Y0 = y =
n=0

donc égale à
∞
X (λy)n −λy
= [G∗ (s)]n e
n=0
n!
En déconditionnant par rapport à y nous obtenons
Z ∞
−sY ∗
E e−sYb | Y0 = y dY0 (y)

E e b
= Yb (s) =
0

∞ ∞ n Z ∞
n (λy)
Z X
∗ −λy
e−[λ−λG (s)]y dY0 (y)
∗
= [ [G (s)] e ]dY0 (y) =
0 n=0
n! 0

En définitive :

Yb∗ (s) = Y0∗ [λ − λG∗ (s)]

De la même manière nous allons procéder pour Yc∗ (s) :

E e−sYc | Y0 = y, N0 = n = e−sy [G∗ (s)]n

62 Files de Priorité

d’où :

∞ ∞ n
n (λy)
Z X
E e−sYc = −sy ∗
e−λy ]dY0 (y)

e [ [G (s)]
0 n=0
n!
soit

Yc∗ (s) = Y0∗ (s + λ − λG∗ (s)) (3.4)

Cette forme est similaire à celle de G∗ (s) où la distribution de
X coı̈ncide avec celle de Y0 .

3.3 Formule de conservation

Des formules de conservation existent pour les files M/GI/1 et
GI/GI/1 ayant des politiques de service qui conservent le travail.
Ces formules déterminent des relations entre des grandeurs insen-
sibles à la politique de service. Nous allons commencer ce para-
graphe par donner quelques exemples de tels paramètres.

3.3.1 Exemples de grandeurs insensibles à la politique

de service
• La période d’activité élémentaire. Celle-ci commence par
l’arrivée d’un paquet dans une file d’attente vide et se ter-
mine au moment où le système d’attente redevient vide.

• Le travail non terminé Ut à l’instant t. En effet ce paramètre

est égal au temps nécessaire au serveur pour vider la file
d’attente en supposant que l’arrivée des paquets est bloquée.

• Le nombre de paquets dans une file M/GI/1/./.. En effet, soit

Yn le nombre de paquets dans le système juste après le nième
départ, peu importe l’ordre de service de ces paquets. Alors
nous pouvons écrire :

Yn − 1 + AXn+1 si Yn > 0
Yn+1 =
AXn+1 si Yn = 0
3.3 Formule de conservation 63

où Xn+1 est le (n+1)ième service (tous les temps de service

sont i.i.d.), et At est le nombre d’arrivée (processus de Pois-
son) dans un intervalle de temps de durée t. Les équations qui
viennent d’être établies pour n’importe quelle politique de ser-
vice (qui conserve le travail) identifient une chaı̂ne de Markov
qui coı̈ncide avec celle de la file standard M/GI/1/./F IF O.
Ainsi nous retrouvons la même fonction génératrice qui donne
le nombre de clients dans le système :

(1 − ρ)(1 − z)
Q(z) = X ∗ (λ − λz)
X ∗ (λ − λz) − z

Utilisant la formule de Little, nous obtenons que le temps de

transit moyen (et le temps d’attente moyen dans la file) d’un
paquet est insensible à la politique de service.

3.3.2 Formule de conservation pour la file M/GI/1

Proposition 3.1. Pour toute file M/GI/1 et toute politique non préemptive
de service conservant le travail nous avons :
π
(
ρE[W0 ]
X
1−ρ
si ρ < 1
ρp E[Wp ] =
p=1
∞ si ρ ≥ 1

W0 représentant le service résiduel du paquet en cours de service en

régime stationnaire.

Preuve :
En effet, soit U(t) le travail non terminé à l’instant t. Nous
pouvons donc écrire :
π
X
U(t) = W0 (t) + Np (t)Xp
p=1

où Np (t) = nombre de paquets de priorité p dans le système à

l’instant t, W0 (t) le service résiduel du paquet en cours de service à
l’instant t et Xp est le temps de service d’un paquet de priorité p.
Comme U(t) est une grandeur insensible à la politique de service, on
peut la calculer dans un contexte de politique sans priorité comme
64 Files de Priorité

le temps d’attente dans la file et donc utiliser la formule de P-K

pour le calcul de sa moyenne.
Nous allons d’abord faire tendre t −→ ∞. Comme nous avons
supposé que ρ < 1, les variables aléatoire que nous avons considérées
vont tendre vers les variables en régime stationnaire. Ainsi, W0 (t) −→
W0 , Ut −→ U et Np (t) −→ Np .
Utilisant donc la formule de Pollaczek-Khintchine pour le calcul
de E[U] on peut écrire

λE[X 2 ]
E[U] = E[W ] =
2(1 − ρ)
où
π
2 X λp 2
E X = E Xp
p=1
λ

Donc
π π
1 X E Xp2

1 X λp 2
E[U] = E Xp = ρp
1 − ρ p=1 2 1 − ρ p=1 2E[Xp ]

Ainsi

1
E[U] = E[W0 ]
1−ρ
Utilisant maintenant le second membre de l’équation qui détermine
U et tenant compte que par la formule de Little appliquée à la
longueur moyenne de la file en attente nous avons E[Np ] = λp E[Wp ]
π
X π
X
E[U] = E[W0 ] + E[Np ] E[Xp ] = E[W0 ] + ρp E[Wp ]
p=1 p=1

Donc sous la condition ρ < 1 :

π
X ρE[W0 ]
ρp E[Wp ] =
p=1
1−ρ

Remarque 3.1. Le second membre de l’équation précédente est insensi-

ble à la politique de service non préemptive. En d’autres termes, entre
deux politiques différentes, si dans l’une certains E[Wp ] sont plus grands,
3.4 Analyse de la politique de service LIFO 65

les autres sont obligatoirement plus petits de telle manière que πp=1 ρp E[Wp ]
P

reste constante. Donc si une politique privilégie certaines classes, ceci se fait
nécessairement au détriment des autres classes de priorité.

Remarque 3.2. Prenons comme cas particulier E[Xp ] = E[X] un service

de paquet indépendant de la classe. La formule de conservation devient
π
X λE[W0 ]
λp E[Wp ] =
p=1
1−ρ

Par la formule de Little λp E[Wp ] = E[Np ] on obtient

π
X λE[W0 ]
E[Np ] =
p=1
1−ρ

Le premier membre n’est autre que le nombre moyen de paquets dans la

file qui est donc insensible à la politique de service. Utilisant la formule de
Little à nouveau pour la file M/GI/1/./F IF O standard nous avons :

E[W0 ]
E[W ] =
1−ρ
qui est aussi insensible à la politique de service, mais ce résultat nous est
déjà connu.

3.4 Analyse de la politique de service LIFO

3.4.1 La politique LIFO non préemptive
Avec cette politique de service, le paquet qui arrive n’est retardé
que par le service du paquet en cours, au moment de son arrivée,
ainsi que par les paquets qui arrivent après lui. En d’autres termes,
le délai subi par le paquet n’est autre que la période d’activité
engendrée par le temps de service résiduel.
Les résultats sur les processus de renouvellement donnent la TL
de la densité de la distribution du service résiduel

1 − X ∗ (s)
Y0∗ (s) =
sE[X]
66 Files de Priorité

Donc le délai d’attente coı̈ncide avec le cycle de délai associé au

service résiduel

E e−sW | système actif = Yc∗ (s) = Y0∗ (s + λ − λG∗ (s))

1 − X ∗ (s + λ − λG∗ (s))
=
(s + λ − λG∗ (s))E[X]
Sachant que G∗ (s) = X ∗ (s + λ − λG∗ (s)) alors

1 − G∗ (s)
Yc∗ (s) =
(s + λ − λG∗ (s))E[X]
En déconditionnant, on trouve deux termes. Le premier, à mul-
tiplier par la probabilité 1 − ρ, correspond au cas du système vide
où le client qui arrive ne subit aucune attente. Le second terme est
celui que nous venons de calculer, à pondérer par la probabilité ρ
que le système soit actif

E e−sW = E e−sW | système actif P{système actif} +

E e0 | système inactif P{système inactif}

Donc
E e−sW = W ∗ (s) = Yc∗ (s)ρ + 1(1 − ρ)

Soit en définitive :

λ[1 − G∗ (s)]
W ∗ (s) = (1 − ρ) + (3.5)
s + λ − λG∗ (s)
Notons que cette forme est très différente de celle de Pollaczek-
Khintchine pour la file FIFO qui nous rappelons :

s(1 − ρ)
W ∗ (s) = (3.6)
s − λ + λX ∗ (s)
Connaissant la TL de la densité, il est possible de calculer les
premiers moments :
d ∗ λE[X 2 ]
E[WLIF O ] = − W (s) |s=0 = = E[WF IF O ] (3.7)
ds 2(1 − ρ)

2 2
σW |F IF O = (1 − ρ)σW |LIF O −ρ(E[W ])2 (3.8)
3.5 Analyse de la politique ”Head Of the Line” HOL 67

avec
2 λE[X 3 ]
σW |F IF O = (E[W ])2 + (3.9)
3(1 − ρ)
Donc :
2 2
σW |F IF O < σW |LIF O

3.4.2 La politique LIFO préemptive resume

Dans cette politique nous allons considérer le temps de séjour dans
le système.
Un paquet qui arrive va interrompre le service du paquet en
cours, et, à son tour, sera interrompu par tous les paquets qui
arrivent pendant son séjour dans le système.
Donc, le temps de séjour de ce paquet coı̈ncide avec le cycle de
délai composé du service du paquet, suivi de la période d’activité
engendrée par ce service. Ce cycle de délai est donc la période
d’activité élémentaire d’une file M/GI/1/./F IF O donné par

S ∗ (s) = G∗ (s) = X ∗ (s + λ − λG∗ (s)) (3.10)

3.5 Analyse de la politique ”Head Of the Line”

HOL
Dans ce paragraphe, nous supposons que les priorités sont fixées
d’avance. Les clients de la classe p sont prioritaires sur ceux de la
classe p − 1 ,p − 2, · · · , 1. Les clients appartenant à la même classe
sont servis dans un ordre FIFO. Cette politique est appelée HOL,
voir 3.1.
Considérons toujour un paquet générique de priorité p qui arrive
dans le système en régime stationnaire. Ce paquet n’est pas affecté
par les paquets de classes 1, · · · , p − 1 en attente dans le système, ni
par les paquets de classe p arrivant après lui. Donc

π
X π
X
E[Wp ] = E[W0 ] + E[Xi ] E[Nip ] + E[Xi ] E[Mip ] (3.11)
i=p i=p+1
68 Files de Priorité

-
S
S
λπ S
S
S
S
S
S
- S
HH
S '$
HH S
HH
λπ−1 HH S
Hw
S
j
H
&%
7

-

λ1

Figure 3.1: Politique HOL avec π priorités

3.5 Analyse de la politique ”Head Of the Line” HOL 69

Cependant, le paquet est susceptible de subir un délai dû aux

priorités 1, · · · , p − 1 dans le cas non préemptif par le biais de W0 du
paquet en cours de service.
Nous allons étudier la politique HOL dans deux variantes de
service : le non préemptif et le ”preemptive resume”.

3.5.1 Service non préemptif

Calculons d’abord le délai d’attente moyen dans la file. Utilisant
la formule de Little :

E[Nip ] = λi E[Wi ]
pour i = p, · · · , π.
Quant aux paquets de classe p + 1, · · · , π arrivant après le paquet
en question et servis avant le client p durant le délai d’attente Wp :

E[Mip ] = λi E[Wp ]
pour i = p + 1, · · · , π. D’où :
π
X π
X
E[Wp ] = E[W0 ] + ρi E[Wi ] + ρi E[Wp ]
i=p i=p+1

Donc : Pπ
E[W0 ] + i=p+1 ρi E[Wi ]
E[Wp ] =
1 − πi=p ρi
P

Cette équation peut être résolue d’une manière récursive :

E[W0 ]
E[Wπ ] =
1 − ρπ
Cette forme ressemble à celle de P-K. Le délai moyen pour la
haute priorité est sensible au trafic de basse priorité par le biais de
E[W0 ], donc des moments du second ordre E[Xi2 ] , i ≤ π.
Connaissant E[Wπ ] on peut calculer E[Wπ−1 ] , · · · Finalement on
montre, par récurrence, que

E[W0 ]
E[Wp ] = (3.12)
(1 − rp )(1 − rp+1 )
Pπ
avec p = 1, 2, · · · , π et rp = i=p ρi
70 Files de Priorité

Considérons maintenant la distribution de probabilité du délai

d’attente, précisément la TL de la densité de Wp∗ (s). En reprenant
l’analyse du cycle de délai adaptée à ce contexte, le délai initial Y0
coı̈ncide avec le travail non terminé à l’instant d’arrivée, et Yb est
la période d’activité engendrée par Y0 due au trafic de priorité > p.
L’intensité de ce trafic de priorité > p est :
π
X
λH = λi
i=p+1

D’une manière symétrique, l’intensité du trafic de priorité < p est

:
p−1
X
λL = λi
i=1

Posons :
π
∗
X λi ∗
XH (s) = Xi (s)
i=p+1
λ H

p−1
X λi ∗
XL∗ (s) = Xi (s)
i=1
λ L

G∗H (s) = XH
∗
(s + λH − λH G∗H (s))
Alors on peut montrer que :

(1 − ρ)(s + λH − λH G∗H (s)) + λL (1 − XL∗ (s + λH − λH G∗H (s)))

Wp∗ (s) =
s − λp + λp Xp∗ (s + λH − λH G∗H (s))
(3.13)

Remarque 3.3. Cas particuliers

∗
• Si π = 1 alors λH = 0, λL = 0, XH = XL∗ = G∗H ≡ 0, λπ = λ
D’où :
s(1 − ρ)
W1∗ (s) =
s − λ + λX ∗ (s)

qui n’est autre que la formule de P-K.

∗
• Si π > 1 alors pour p = π : λH = 0, XH = G∗H ≡ 0
D’où :
3.5 Analyse de la politique ”Head Of the Line” HOL 71

s(1 − ρ) + λL (1 − XL∗ (s))

Wπ∗ (s) =
s − λπ + λπ Xπ∗ (s)
Encore une fois, nous remarquons le terme λL (1 − XL∗ (s)) qui traduit
quantitativement l’influence du trafic de basse priorité sur le trafic de
la plus haute priorité π.

3.5.2 Service ”preemptive resume”

La différence importante par rapport au cas non préemptif est que
le paquet peut être retardé par le trafic des paquets de priorité
supérieure tant que le paquet n’a pas fini son service.
Ainsi l’analyse du retard dû aux paquets entrant après l’instant
d’arrivée doit s’étendre à la durée de séjour du paquet Sp dans le
système au lieu de la durée d’attente Wp du paquet dans la file.
Nous allons donc décomposer Sp en trois parties :

• Le temps de service Xp du paquet (de priorité p),

• Le retard dû au travail non terminé U à l’instant d’arrivée

et correspondant au service des paquets déjà présents dans le
système de priorité ≥ p,

• Le retard dû au service des paquets de priorité > p, arrivant

après l’instant d’arrivée du paquet p et ceci pendant la durée
de séjour du paquet dans le système;

En termes d’analyse du cycle de délai : Yc = Y0 + Yb avec Y0 =

Xp + U, et Yb est la période d’activité engendrée par Y0 .
On va se contenter, ici, de l’étude de E[Sp ].
Considérons la deuxième partie dans la décomposition de Sp .
Comme le travail non terminé est insensible à la politique de ser-
vice, nous pouvons le calculer, en particulier, comme celui d’une
file M/GI/1/./F IF O standard avec comme trafic entrant celui de
toutes les priorités ≥ p. Les paquets de priorité < p n’ont aucune
influence sur la priorité p. Donc la moyenne du travail non terminé
est Pπ 2
i=p λi E[Xi ]
2(1 − πi=p ρi )
P
72 Files de Priorité

La troisième partie dans la décomposition de Sp correspond aux

paquets de priorité > p arrivant dans le système entre l’instant
d’arrivée du paquet de priorité p et son instant de départ. Pour
une priorité i ≥ p + 1, il y a en moyenne λi E[Sp ] arrivées pendant le
séjour du paquet p qui va, donc, subir un retard total moyen de :
π
X π
X
λi E[Sp ] E[Xi ] = ρi E[Sp ]
i=p+1 i=p+1

Finalement, en rajoutant aux deux parties qui viennent d’être

calculées E[Xp ] nous obtenons exactement E[Sp ] :
Pπ 2 π
i=p λi E[Xi ]
X
E[Sp ] = E[Xp ] + Pπ + ρi E[Sp ]
2(1 − i=p ρi ) i=p+1

Pour p = π nous retrouvons la formule de P-K :

λπ E[Xπ2 ]
E[Sπ ] = E[Xπ ] +
2(1 − ρπ )
Une différence importante avec le cas non préemptif est que les
priorités < π n’ont aucune influence sur la priorité la plus haute.
Tout se passe pour cette priorité π comme s’il s’agit d’une file
M/GI/1/./F IF O standard chargée par un trafic d’intensité λπ .
Partant de E[Sπ ] nous pouvons calculer E[Sπ−1 ] et de proche en
proche d’obtenir E[Sp ] :

E[X 2 ]
E[Xp ] (1 − πi=p ρi ) + πi=p λi 2 i
P P
E[Sp ] = (3.14)
(1 − πi=p ρi )((1 − πi=p+1 ρi )
P P
Chapter 4

Comparaison des différentes

techniques de multiplexage

4.1 Introduction
Avec l’augmentation du nombre d’utilisateurs mobiles et l’évolution
rapide des réseaux mobiles sans fil, les demandes des utilisateurs
en terme de qualité de service (QoS) deviennent de plus en plus
exigeantes. Ceci nécessite l’introduction des méthodes avancées de
gestion de la ressource radio, d’autant plus que l’interface radio
représente le goulet d’étranglement des réseaux mobiles.
Le partage des ressources radio entre les différents usagers mo-
biles est de loin le problème critique dans les réseaux mobiles et
devrait être réalisé au moyen des techniques de multiplexage. Le
multiplexage est l’un des mécanismes fondamentaux à la base du
fonctionnement des réseaux de télécommunication.
Les techniques d’accès multiple ou les techniques de multiplex-
age devraient être les plus judicieuses possibles afin d’écouler le
maximum de communications. Trois principales techniques d’accès
multiple sont à étudier :

• L’Accès Multiple à Répartition dans les Fréquences (AMRF)

ou Frequency Division Multiple Access (FDMA). Elle est courante
dans le monde de la communication sur voie radio comme les
réseaux radio-mobile ainsi que les réseaux satellitaires. Elle
est également utilisée dans les réseaux optique à très haut
74 Comparaison des différentes techniques de multiplexage

débit (≥ 10 Gbit/s).

• L’Accès Multiple à Répartition dans le Temps (AMRT) ou

Time Division Multiple Access (TDMA). TDMA est à la base
du RNIS bande étroite. Cette technique est aussi utilisée dans
les systèmes de transmission basés sur la hiérarchie numérique
synchrone (SDH) et la hiérarchie numérique plésiochrone (PDH).

• L’Accès Multiple à Répartition par les Codes (AMRC) ou

Code Division Multiple Access (CDMA)

Notons que ces techniques de multiplexage existent à deux échelles:

l’échelle de l’appel et l’échelle du paquet. En effet, à l’échelle de
l’appel, le contrôle d’admission (CAC) est basé sur le multiplexage
statitique afin d’accepter des nouveaux appels. Plus précisément,
le CAC profite de l’inactivité de certains utilisateurs pour faire
passer les communications des autres utilisateurs. C’est le principe
de base du multiplexage statistique.
Le multiplexage statistique ou encore temporel asynchrone ou
statistique a été développé pour répondre aux exigences du monde
de communication de données où la trafic échangé est sporadique
par nature. Cette technique est donc très courante dans les réseaux
à commutation par paquets. Elle a été choisie pour être à la base du
mode de transfert asynchrone ATM qui sera utilisé dans le RNIS
large bande.

L’activité des utilisateurs est exprimée par le facteur de charge

ρ qui vaut 0.1 ou 0.05 Erlangs dans les réseaux téléphoniques. Rap-
pellons que ρ dépend du taux moyen d’arrivée et du temps moyen
de service. Notons que le temps de service est exponentiellement
distribué de moyenne 2 à 3 minutes pour le traffc voix.

D’autre part, le multiplexage apparaı̂t au niveau du paquet.

A cette échelle, plusieurs sources émettent des paquets dont le
processus d’arrivée est poissonnien. Afin de servir ces sources,
deux cas de figure se présentent:

• Un serveur est alloué par source. Ce cas se résume à n files

4.2 Architecture du réseau GSM 75

d’attente M/M/1, où n est le nombre de sources qui émettent

des paquets.

• Un seul serveur est alloué pour toutes les sources. Le serveur

en question aura une capacité n fois plus grande que celle d’un
serveur utilisé au premier cas. Puisque l’agrégation des pro-
cessus de Poisson est un processus de Poisson, la modélisation
de ce système donne une file d’attente M/M/1. Ainsi, nous
retrouvons le multiplexage statistique dans ce cas.
Afin de servir les paquets ainsi agrégés, un ordonnanceur ef-
ficace doit être mis en place afin de servir les flux de paquets
d’une manière judicieuse.

Dans ce chapitre, nous ciblons l’étude des différentes techniques

d’accès multiple dans les réseaux mobiles. En effet, ces méthodes
de multiplexage sont déployées dans les réseaux GSM et UMTS.
Avant d’étudier ces différentes techniques d’accès multiple, nous
commençons le chapitre par une présentation de l’architecture des
réseaux mobiles GSM et UMTS. Ceci permettra de bien définir le
contexte de notre étude.
Ensuite, nous examinons ces différentes techniques d’accès mul-
tiple. Les principales caractéristiques de chaque technique sont
présentées avec des exemples concrets d’application dans les réseaux
mobiles.
En seconde partie du chapitre, nous comparons les performances
de ces techniques en introduisant des modèles Markoviens simples.
Chacune des techniques de multiplexage présente ses avantages et
ses inconvénients. Il est donc fort probable qu’aucune des trois
techniques ne viendra remplacer l’autre ou les deux autres dans
l’évolution prévisible de la technologie des réseaux.

4.2 Architecture du réseau GSM

La deuxième génération des mobiles est introduite avec le réseau
GSM.
76 Comparaison des différentes techniques de multiplexage

BSS NSS

BTS

HLR
BTS BSC

BTS
VLR

BSC MSC
BTS

BTS
VLR

BSC MSC
BTS

signalisation
parole

Figure 4.1: Architecture du réseau GSM

Un réseau GSM se découpe en trois sous-ensembles (figure 4.1)

1. Le sous-système radio ou Base Station Sub-System (BSS)

qui assure les transmissions radioélectriques et qui gère la
ressource radio.

2. Le sous-système d’acheminement ou Network Sub-System

(NSS), appelé réseau fixe qui comprend l’ensemble des fonc-
tions nécessaires à l’établissement des appels et à la mobilité.

3. Le sous-système d’exploitation et de maintenance ou Operat-

4.2 Architecture du réseau GSM 77

ing Sub-System (OSS) qui permet à l’exploitant d’administrer

le réseau.

4.2.1 Architecture matérielle du sous-système radio

Le sous-système radio BSS comprend :
• Les Base Transceiver Station (BTS) qui sont des émetteurs-
récepteurs ayant un minimum d’intelligence. Une BTS a la
charge de la transmission radio. Elle gère toute la couche
physique ; multiplexage TDMA, saut de fréquence, etc. Elle
réalise l’ensemble des mesures radio nécessaires pour vérifier
qu’une communication en cours se déroule correctement. La
BTS gère également la couche liaison de données pour l’échange
de signalisation entre les mobiles et l’infrastructure. Enfin,
elle gère la liaison de données avec le BSC afin d’assurer la
fiabilité du dialogue.

• Le Base Station Controller (BSC) qui contrôle un ensemble

de BTSs et permet une première concentration des circuits. Il
a pour fonction principale de gérer la ressource radio. Il com-
mande l’allocation des canaux, utilise les mesures effectuées
par la BTS pour contrôler les puissances d’émission du mo-
bile et/ou de la BTS, prend la décision de l’exécution d’un
handover qui permet le transfert d’une communication d’un
canal à un autre.

4.2.2 Architecture matérielle du sous-système fixe

Le sous système fixe NSS comprend:
• Les Mobile-services Switching Center (MSC) sont des com-
mutateurs mobiles associés aux bases de données Visitor Lo-
cation Register (VLR). Le VLR est une base de données
qui mémorise les données d’abonnement des abonnés présents
dans une zone géographique.
Le MSC gère l’établissement des communications entre un
mobile et un autre MSC, la transmission des messages courts
78 Comparaison des différentes techniques de multiplexage

et l’exécution du handover lorsqu’il y est impliqué. Il dialogue

avec le VLR pour gérer la mobilité des usagers.
Plusieurs MSC peuvent être reliés au même VLR. En général,
il y en a un seul par VLR.

• Le Home Location Register (HLR) est une base de données

qui gère les abonnés. D’une part, il mémorise les caractéristiques
de chaque abonné (l’identité internationale de l’abonné utilisée
par le réseau, le numéro d’annuaire de l’abonné et le profil de
l’abonnement). D’autre part, le HLR est une base de données
de localisation. Il mémorise pour chaque abonné le numéro
du VLR où il est enregistré.

4.2.3 Sous-système d’exploitation et de maintenance

L’administration du réseau (Network Management) comprend les
activités qui permettent de mémoriser et de contrôler les perfor-
mances et l’utilisation des ressources de façon à offrir un certain
niveau de qualité aux usagers. Les différentes fonctions d’administration
comprennent :

• l’administration commerciale qui consiste à déclarer les abonnés,

les terminaux, les facturations et les statistiques.

• la gestion de la sécurité.

• l’exploitation et la gestion des performances (observations du

trafic et de la qualité de service, changement de configuration
pour s’adapter à la charge du réseau).

• le contrôle de la configuration du système (mise à niveau de

logiciel, introduction de nouveaux équipements et de nouvelles
fonctionnalités).

• la maintenance (détection des défauts, tests d’équipements).

Le système d’administration du réseau GSM est proche du con-

cept TMN (Telecommunication Management Network) qui définit
les conditions techniques d’une supervision efficace et économique
4.3 Architecture du réseau UMTS 79

de la qualité de service.

Outre le service de la voix, le réseau GSM offre des services de

données à des débits relativement faibles. Le réseau de troisième
génération UMTS vient ajouter au service voix des services de
données variés et à des débits élevés.

4.3 Architecture du réseau UMTS

C o re N e tw o rk
Iu

R N S Iu r R N S
R N C R N C

Iu b Iu b

U T R A N
Iu b Iu b

N o d e B N o d e B N o d e B N o d e B

Figure 4.2: Architecture de l’UTRAN

Le réseau Universal Mobile Telecommunications Systems (UMTS)

définit la troisième génération de mobiles. Le réseau UMTS of-
fre des services de données à des débits élevés, une efficacité de
l’utilisation du spectre radio, de multiples services simultanés par
utilisateur et des services avec différentes qualités de service.
Le réseau d’accès de l’UMTS, Universal Terrestrial Access Net-
work (UTRAN), est similaire à celui du réseau GSM. Les différents
éléments de l’UTRAN sont les suivants (figure 4.2) :

• Le Radio Network Controller (RNC) est responsable de l’établissement,

la maintenance et le relâchement de la connexion radio avec
l’utilisateur. Le RNC a également la charge du contrôle d’admission
et la gestion du handover.
80 Comparaison des différentes techniques de multiplexage

• Le Node B est similaire à la BTS dans GSM. Il est respons-

able de la transmission des données et de la signalisation sur
l’interface radio.

• Le Radio Network Subsystem (RNS) comprend un RNC et

un ou plusieurs Node Bs. Le RNS constitue l’accès au réseau
UMTS et permet l’allocation et la libération des ressources
radio spécifiques à un ensemble de cellules
Les différentes interfaces de l’UTRAN sont les suivantes :
• Iu est l’interface entre un RNS et le réseau coeur.

• Iub est l’interface entre un RNC et un Node B.

• Iur est l’interface entre deux RNCs.

Maintenant que les architectures des réseaux mobiles ont été
définies, nous présentons les techniques de multiplexage utilisées
dans ces réseaux.

4.4 Accès Multiple à Répartition dans les Fréquences

La méthode la plus conventionnelle pour l’accès multiple est la
technique de multiplexage en fréquence FDMA. Avec FDMA, chaque
canal (ou porteuse) est utilisé pour véhiculer un appel unique et
dans un sens à la fois (sens montant: de la station mobile vers la
station de base BTS ou sens descendant: de la station de base BTS
vers la station mobile).
Parmi les canaux disponibles, certains sont dédiés au contrôle.
En fonction de la capacité du système et des besoins en signalisa-
tion, un ou plusieurs canaux de contrôle sont utilisés.

4.4.1 Caractéristiques de la technique FDMA

La technique FDMA possède les caractéristiques suivantes :
1. Transmission continue : Une fois alloués, les canaux sont
utilisés sans partage dans le temps. Ainsi, les stations mobiles
et les stations de base utilisent les canaux simultanément et
d’une manière continue.
4.5 Accès Multiple à Répartition dans le Temps 81

2. Bande passante de largeur faible : Puisque chaque canal est

utilisé par une seule station, les canaux FDMA sont étroits.
Les systèmes cellulaires analogiques utilisent des canaux de
25-30 kHz de largeur de bande. Les systèmes FDMA digi-
taux utilisent des techniques de codage de la voix à des débits
faibles afin de réduire la largeur de bande des canaux.

3. Faible en-tête : Les canaux voix utilisent des messages d’en-

tête pour le contrôle. Puisque ces canaux sont utilisés d’une
manière continue, moins de bits sont utilisés pour le contrôle
en comparaison avec les canaux TDMA.

4. Faible complexité ”Hardware” : La transmission en mode

FDMA ne nécessite pas de tramage complexe et de synchro-
nisation associée à la transmission des rafales comme dans le
cas des systèmes TDMA puisque les informations sont émises
sans interruption d’une manière synchrone.

5. Coût élevé des équipements : Un des inconvénients de la

technique FDMA vient du fait qu’elle nécessite l’installation
de plus d’équipements au niveau de la station de base que
dans le cas de la technique TDMA.

6. Handover perceptible : La continuité de la transmission sur

les canaux FDMA rend perceptible la transition d’un canal
à un autre, lorsqu’un handover a lieu. Dans les systèmes
TDMA, certains intervalles de temps sont utilisés pour le han-
dover. Ainsi, l’interruption de la transmission est mieux gérée
avec TDMA.

4.5 Accès Multiple à Répartition dans le Temps

La technique TDMA permet un multiplexage temporel synchrone.
Contrairement à FDMA qui permet d’allouer une partie de la
bande passante à chaque station, toutes les stations avec TDMA
peuvent utiliser la totalité de la bande passante à des intervalles
de temps distincts.
82 Comparaison des différentes techniques de multiplexage

Ainsi, la porteuse (fréquence radio) est partagée en N inter-

valles de temps ou ”time slots” (appelés slots). Ces slots sont
alloués aux stations d’une manière cyclique. Le nombre de slots
dans un cycle ou trame dépend de plusieurs facteurs tels que la
technique de modulation, la bande de fréquence, etc.
Il est à noter que l’information transmise avec TDMA devrait
avoir une représentation discrète dans le temps. Ainsi, TDMA est
une technique d’accès convenable à la transmission digitale.

4.5.1 La synchronisation avec la technique TDMA

La technique TDMA nécessite une bonne synchronisation. En ef-
fet, chaque station devrait distinguer les slots qui lui sont alloués.
La synchronisation est d’autant plus difficile que les délais de prop-
agation sont importants. La synchronisation devrait alors résoudre
deux problèmes :

1. La détermination du slot attribué à chaque station.

2. La transmission et la réception des signaux dans les slots cor-

respondants afin d’empêcher le chevauchement des signaux.
En effet, dans les réseaux mobiles, les signaux transmis par les
mobiles utilisant une porteuse commune, doivent être reçus
par la station de base dans le slot défini. Sinon, les signaux
vont chevaucher entre eux.

Afin de résoudre le problème de chevauchement des signaux,

une solution consiste à garder une partie du slot inutilisée ou en
d’autres termes à prévoir des ”intervalles de garde”. L’intervalle
de garde est un temps de silence entre la fin de la rafale (burst)
synchronisée et la fin du slot pendant lequel il n’y a pas de trans-
mission. Ceci induit une perte du temps prévu pour chaque station
et réduit le débit utile. Par conséquent, l’intervalle de garde doit
être dimensionné d’une manière appropriée.
4.5 Accès Multiple à Répartition dans le Temps 83

4.5.2 Dimensionnement de l’intervalle de garde dans

un réseau mobile
Supposons qu’une station mobile est à 35 Km de distance d’une
station de base. Calculons alors l’intervalle de garde à prévoir afin
d’empêcher le chevauchement des signaux.
Le temps mis à un signal radio pour traverser 70km (aller-retour)
est de 70.103/(3.108 ) = 0.23ms. Par conséquent, l’intervalle de garde
est de 0, 23ms dans chaque slot.

Les différents utilisateurs d’un système cellulaire sont à des dis-

tances variables de leur station de base et endurent des délais de
propagation τp variables. Dans le contexte TDMA, deux mobiles
utilisant deux slots consécutifs ne devraient pas envoyer des rafales
qui se chevauchent au niveau du récepteur de la station de base.
Pour ce faire, nous envisageons deux approches:

1. Augmenter le temps de garde.

2. Compenser le temps de propagation aller-retour en gérant un

paramètre TA correspondant au temps de propagation aller-
retour. Le mobile éloigné doit avancer l’émission de chacun
de ses slots d’une durée τp par rapport à l’instant nominal de
début de slot (c’est-à-dire 2τp par rapport à l’horloge slot telle
qu’il la perçoit).

En utilisant cette procédure, les stations émettent plus tôt leurs

messages afin que la station de base reçoive le message durant le
slot prédéfini. Ainsi, l’intervalle de garde est considérablement
réduit.
Cette procédure ne pourrait pas s’appliquer si le réseau n’est
pas hiérarchique, c-à-d, si le réseau ne possède pas un contrôle
centralisé au niveau de la station de base par exemple.
Le délai de propagation est très faible par rapport à celui qu’on
rencontre dans les systèmes satellitaires où il peut atteindre quelques
centaines de ms. Cependant, il ne peut être négligé dans un
système comme celui du GSM qui admet des cellules de 35Km.
Si la première approche avait été adoptée dans le réseau GSM, il
84 Comparaison des différentes techniques de multiplexage

aurait fallu prévoir des intervalles de garde de 0.23ms, durée cor-

respondante à plus d’un tiers de la durée de slot. C’est pourquoi,
la seconde approche est envisagée dans le système GSM. Ainsi
l’intervalle de garde a été réduit à 30µs.

4.5.3 Dimensionnement de l’intervalle de garde dans

un réseau non hiérarchique
Un système radio comprend trois stations ayant la topologie il-
lustrée à la figure 4.3. Le système utilise la technique TDMA en
mode half-duplex (la transmission et la réception des messages ne
sont pas simultanées). Chaque station transmet dans son propre
slot et reçoit des messages des deux autres stations dans les deux
slots restants (figure 4.4). Les stations utilisent une référence de
temps fixe et commencent leur transmission exactement au début
de chaque slot.

4.5 Km 3 Km

2 3
6 Km

Figure 4.3: Topologie d’un réseau non hiérarchique

1 2 3 1 2 3
t

Figure 4.4: Exemple de transmission avec TDMA

Afin d’éviter le chevauchement entre les messages, calculons

l’intervalle de garde minimum τg requis.
4.5 Accès Multiple à Répartition dans le Temps 85

15 10

Station 1 1 2 3 1

5 10 t
15 20 15

1 2 3 1
Station 2
15 5 t
10 20

1 2 3
Station 3
20 t

Figure 4.5: Transmission dans un réseau non hiérarchique

Soit τij le délai de propagation entre deux stations i et j avec

1 ≤ i ≤ 3 et 1 ≤ j ≤ 3. Etant donné la topologie illustrée à la figure
4.5, il est facile de calculer ces délais comme suit :

τ12 = τ21 = 15µs

τ13 = τ31 = 10µs
τ23 = τ32 = 20µs

Schématisons la réception des messages à la figure 4.5. Comme

le montre la figure 4.5, le cas de chevauchement le plus sévère est
obtenu avec la station 3 lorsqu’elle transmet durant la réception
d’un message de la station 2. Le message reçu dans le slot 2
chevauche sur le slot 3 de 20µs. Donc l’intervalle de garde au début
(ou à la fin) de chaque slot devrait être au moins égal à 20µs.
D’une manière générale, τg est donné par :

τg ≥ max(τij )
86 Comparaison des différentes techniques de multiplexage

4.5.4 Caractéristiques de la technique TDMA

La technique TDMA possède les caractéristiques suivantes :

1. Plusieurs canaux par porteuse : Une porteuse permet de

multiplexer plusieurs canaux. Ainsi, le nombre de canaux de
voix par porteuse dans le système GSM est égal à 8 et est égal
à 3 dans le système américain.

2. Transmission par rafales : Une porteuse permet de partager

le temps entre plusieurs canaux. Ainsi, la transmission des
données a lieu durant des slots bien définis.

3. Bande passante de faible ou grande largeur : Le choix de

la largeur de la bande passante dépend de plusieurs facteurs,
entre autres la technique de modulation. Cette largeur est de
200 kHz dans le système GSM avec un débit de transmission
de 271Kb/s et de 30kHz dans le système américain avec un
débit de transmission de 48.6 Kb/s.

4. Large en-tête : Le mode de transmission par rafales nécessite

une synchronisation importante. Par conséquent, certains bits
sont dédiés à la synchronisation. Les en-têtes de messages
émis dans les systèmes TDMA peuvent aller jusqu’à 20 à 30%
du nombre total des bits émis.

5. Complexité ”Hardware” : L’utilisation de la technologie dig-

itale augmente la complexité du terminal.

6. Coût réduit des stations de base : L’utilisation de plusieurs

canaux par porteuse réduit le coût des équipements au niveau
de la station de base.

7. Handover efficace : La station mobile étant inactive pendant

certains slots, elle peut réaliser le handover de façon plus ef-
ficace que dans un système FDMA. En outre, pendant son
inactivité, la station mobile peut scruter les canaux des sta-
tions de base voisines pendant la phase de préparation du
handover.
4.5 Accès Multiple à Répartition dans le Temps 87

4.5.5 Partage des ressources radio dans le réseau GSM

Canal physique plein- débit

Fréquences

Canal physique demi- débit

200kHz

Porteuse C3

0 1 2 3 4 5 6 7 temps
577 µs
Trame TDMA

Figure 4.6: Les canaux physiques dans le réseau GSM

Afin de fixer les idées, nous donnons ci-suit une application à

l’utilisation de TDMA et FDMA. En effet, nous étudions le partage
des ressources dans le réseau GSM.

Un système radio mobile a besoin d’une partie du spectre radio

pour fonctionner. Avant de le spécifier en détail, les concepteurs
du système doivent demander une bande de fréquence auprès de
l’instance officielle chargée de la gestion du spectre. Si le système
opère au niveau international, la bande doit être allouée au niveau
de l’union internationale de télécommunication (IUT). La bande
allouée à GSM dans le sens montant s’étend entre 890 MHz et 915
MHz. La bande allouée dans le sens descendant s’étend entre 935
MHz et 960 MHz. Ce qui fait une largeur de bande de 2x25 MHz.
88 Comparaison des différentes techniques de multiplexage

Partage en fréquence

La bande dédiée au système GSM est divisée en canaux fréquentiels

ou fréquences de largeur 200 kHz. Les fréquences sont allouées
d’une manière fixe aux différentes stations de base et sont désignées
souvent par le terme de porteuses. Deux stations de base voisines
ne devraient pas utiliser des porteuses identiques ou proches.

Partage en temps

Chaque porteuse est divisée en intervalles de temps ou slots. La

durée d’un slot a été fixée pour GSM à Tslot = 0.5769ms. Sur une
même porteuse, les slots sont regroupés par paquets de 8. La durée
d’une trame TDMA est donc :

TT DM A = 8Tslot = 4.6152ms

Chaque utilisateur utilise un slot par trame TDMA. Les slots

sont numérotés par un indice TN qui varie de 0 à 7.
Dans le système GSM, on définit un ”canal physique” par la
répétition périodique d’un slot dans la trame TDMA sur une fréquence
particulière. En fait, un canal physique correspond à la ressource
radio qu’il faut utiliser pour supporter une communication téléphonique.

Les concepteurs de GSM ont prévu la possibilité de n’allouer

à un utilisateur qu’un slot toutes les deux trames TDMA. Cette
allocation constitue un canal physique demi-débit par opposition
au canal physique plein débit (figure 4.6).

Nous pouvons constater que le système GSM est un système

utilisant à la fois les techniques FDMA et TDMA, puisque les
ressources radio sont partagées en fréquence et en temps. Dans
le contexte radio mobile, il est d’usage de réserver le sigle FDMA
aux systèmes où chaque porteuse est dédiée à un seul utilisateur.
C’est pourquoi, GSM est répertorié comme un système TDMA.
4.5 Accès Multiple à Répartition dans le Temps 89

Duplexage en fréquence (FDD)

Dans le système GSM, la bande totale allouée au système est

séparée en deux sous-bandes d’égale importance. Ces deux sous-
bandes sont séparées par un ”écart duplex” de 45 MHz (figure 4.7).
Cette séparation est connue sous le nom de duplexage en fréquence
ou FDD (Frequency Division Duplex).
Un canal physique simplex se rapporte à un slot par trame
TDMA sur une porteuse. Un canal physique duplex correspond
à deux canaux physiques simplex. Dans le système GSM, un mo-
bile émet et reçoit à des instants différents. Au niveau du mobile,
l’émission et la réception sont décalées dans le temps d’une durée
de trois slots. Pour conserver la même numérotation TN de 0 à
7 des slots, la synchronisation de la trame TDMA montante est
décalée aussi de 3 ∗ Tslot . Ce décalage permet de simplifier le filtre
duplex présent dans chaque mobile. Son rôle se réduit à rejeter
le signal provenant d’une éventuelle autre station proche émettant
pendant une phase de réception du mobile.

Fréquences

Trame TDMA
Voie descendante 0 1 2 3 4 5 6 7

Ecart
Duplex

Voie montante

0 1 2 3 4 5 6 7

temps
577 µs

Figure 4.7: Duplexage en fréquence dans le réseau GSM

90 Comparaison des différentes techniques de multiplexage

4.5.6 Exemple d’attribution de fréquences dans un réseau

GSM
Supposons qu’un opérateur cherche à dimensionner les cellules d’un
réseau GSM. Cet opérateur veut alors déterminer le nombre de
fréquences et de canaux physiques à attribuer à chaque cellule dans
une planification cellulaire homogène.
Cette planification prévoit une taille k du motif égale à 10. Rap-
pelons que les porteuses allouées à une cellule sont réutilisées par
d’autres cellules si celles-ci sont suffisamment éloignées. La réutilisation
de fréquences permet à un opérateur de couvrir une zone géographique
d’étendue illimitée en ayant recours à une bande de fréquences de
largeur limitée. Le motif de réutilisation est le plus petit groupe
de cellules contenant l’ensemble des canaux une et une seule fois.
Ce motif est répété sur toute la surface à couvrir.

Supposons maintenant que l’opérateur possède une bande de

fréquence Wop = 2 ∗ 8MHz à allouer. Cette bande concerne les deux
sous-bandes montante et descendante.

Etant donné la largeur de bande Wc égale à 200 kHz, le nombre

de fréquences duplex est alors :

Nf = Wop /(2Wc ) = 2 ∗ 8000/(2 ∗ 200) = 40

Par suite, le nombre de fréquences duplex attribué à chaque
cellule est :

Nc = Nf /k = 40/10 = 4
Or, il existe 8 canaux physiques par trame TDMA. En d’autres
termes, chaque fréquence duplex multiplexe 8 canaux physiques
duplex. Par conséquent, le nombre de canaux physiques par cel-
lule est :

Ncanaux = 8 ∗ 4 = 32
Notons que certains de ces canaux physiques sont dédiés pour
le contrôle.
4.6 Accès Multiple à Répartition par les Codes 91

4.6 Accès Multiple à Répartition par les Codes

Cette technique de l’accès multiple est employée dans certains
réseaux de téléphonie sans fil comme les réseaux IS-95, CDMA2000
et UMTS.
CDMA est une technique d’accès qui permet à toutes les sta-
tions de transmettre simultanément, d’utiliser les mêmes fréquences
et d’utiliser la totalité de la bande passante. Puisque toutes les sta-
tions peuvent transmettre simultanément à travers toute la bande
passante, un code doit être alloué à chaque utilisateur afin que sa
transmission soit identifiée.

4.6.1 Etalement du spectre

La technique CDMA repose sur la modulation à étalement de spec-
tre (spread spectrum).
L’idée de l’étalement de spectre découle de la formule de Shan-
non:
S
C = Bw log2 (1 + ) (4.1)
N
où

• C est la capacité du canal de communication

• Bw est la bande passante en Hertz

• S est la puissance du signal

• N est la puissance du bruit

L’équation 4.1 peut être écrite comme suit :

C S
= 1.44ln(1 + )
Bw N
A des valeurs réduites de S/N, nous avons :

C S
= 1.44
Bw N
ou
92 Comparaison des différentes techniques de multiplexage

NC
Bw = 0.7 (4.2)
S
L’équation 4.2 calcule la bande passante nécessaire pour une
transmission d’information avec un rapport signal sur bruit (SNR)
très réduit. Cette équation démontre que lorsque le niveau du
bruit augmente, une transmission fiable est possible en augmen-
tant la bande passante. Ce qui introduit l’idée de l’étalement du
spectre.

L’étalement de spectre est défini comme une technique de com-

munication avec laquelle le signal est étalé sur une bande pas-
sante plus grande que celle requise pour la transmission de ce sig-
nal. En effet, la séquence de données est multipliée par un code
d’étalement. Les bits du code sont appellés ”chips” afin de les dis-
tinguer des bits de la séquence de données appelés symboles (figure
4.8).

Signal

Code d’étalement

Signal étalé

Figure 4.8: Etalement du spectre

Chaque utilisateur a son propre code d’étalement. Ce même

code est utilisé pour l’étalement du signal original afin de produire
le signal à large bande, et pour le désétalement du signal étalé afin
de restituer le signal original (figure 4.9).
Le rapport entre la bande passante transmise et la bande pas-
sante originale est appelé facteur d’étalement (spreading factor) ou
”procesing gain”. Ce rapport indique le nombre de chips utilisés
4.6 Accès Multiple à Répartition par les Codes 93

Signal étalé

Code d’étalement

Signal

Figure 4.9: Désétalement du spectre

pour transmettre un symbole de données. Dans le réseau UTRAN

de l’UMTS, les valeurs du facteur d’étalement varient entre 4 et
512.
La corrélation entre les codes d’étalement est faible. La corrélation
entre des codes dits orthogonaux est nulle. Ceci implique que
plusieurs signaux à large bande peuvent coexister sur la même
fréquence sans interférence mutuelle.
Le signal original est reconstitué au récepteur si la puissance du
signal désétalé est plus grande de quelques décibels que la puissance
des bruits d’interférence. Cela revient à dire que le rapport sig-
nal sur interférence (carrier-to-interference) “C/I” est assez grand
(figures 4.10 et 4.11).

Energie
Energie

Signal Désétalé
A Signal Désétalé
Signaux étalés
C Signaux étalés
B
B A
C I
C I
C D
D
E
E

Fréquence Fréquence

Figure 4.10: Exemple d’un signal pou- Figure 4.11: Exemple d’un signal ne
vant être restitué pouvant être restitué

Dans un réseau mobile utilisant la technique CDMA, le facteur

94 Comparaison des différentes techniques de multiplexage

de réutilisation k est égal à 1. Alors que dans le réseau GSM, k

est égal à 4. Ceci montre que les réseaux mobiles utilisant CDMA,
comme le réseau UMTS, fournissent un gain en capacité par rap-
port aux systèmes à bande étroite, comme le réseau GSM.

4.6.2 Caractéristiques de la technique CDMA

La technique CDMA possède plusieurs caractéristiques. Nous présentons
quelques-unes :

1. Protection contre les interférences des trajets multiples “mul-

tipath”: En communications radio mobiles, les signaux ra-
dioélectriques reçus par les stations comprennent un certain
nombre de composantes. Un signal comporte éventuellement
l’onde émise en trajet direct mais également les contribu-
tions sur la même fréquence de toutes les ondes réfléchies et
réfractées par l’environnement (immeuble, arbre, montagne,...).
Il est rare que l’émetteur et le récepteur soient en visibilité
directe. Un récepteur ne reçoit très souvent qu’un ensemble
d’ondes réfléchies correspondant à des “trajets multiples”. Le
signal est donc affecté par des distorsions de fréquence (ef-
fet Doppler), d’amplitude (évanouissement ou “fading”) et de
phase. Avec la technique CDMA, un signal étalé peut résister
à ces interférences multipath.

2. Confidentialité : Un intrus ne peut reconstituer le signal origi-

nal s’il ne connaı̂t pas le code d’étalement. En outre, certaines
procédures de cryptage sont utilisées dans les systèmes util-
isant WCDMA ; Ces procédures résistent aux attaques. Le
cryptage est optionnel dans le réseau UTRAN mais est obli-
gatoire au niveau du terminal ou du ”User Equipment” (UE).

3. Complexité au niveau du mobile : Le traitement des infor-

mations reçues et émises est plus important que dans les
autres types de systèmes puisqu’il faut implanter un niveau
de codage supplémentaire.

4. Soft Handover : La technique CDMA permet théoriquement

à chaque station de base de disposer de toute la bande de
4.6 Accès Multiple à Répartition par les Codes 95

fréquences. Egalement, elle permet aux mobiles de capter en

même temps deux stations de base. Pendant l’établissement
du handover, le mobile établit un nouveau lien avec la station
de base cible alors qu’il maintient son ancien lien. Ceci permet
d’améliorer les performances du handover.

5. Grande capacité de l’accès multiple : Puisque les codes d’étalement

utilisés ont une faible corrélation, plusieurs utilisateurs actifs
peuvent coexister et partager la même bande de fréquences.
Cependant, l’augmentation du nombre d’utilisateurs augmente
les interférences. D’où la nécessité d’implémenter un contrôle
de puissance assez efficace, comme nous allons voir à la section
suivante.

4.6.3 Contrôle de puissance

Puisque tous les utilisateurs utilisent la même bande spectrale,
chaque utilisateur émet un signal qui ressemble à un bruit pour les
autres utilisateurs. La puissance de chaque signal émis doit être
contrôllée afin qu’aucun utilisateur n’interfère sur les autres util-
isateurs.

Considérons une cellule ayant deux utilisateurs 1 et 2. Nous

proposons d’étudier la liaison montante dans cette cellule.
L’utilisateur 2 est plus proche de la station de base que l’utilisateur
1. Si le contrôle de puissance n’est pas implémenté, les deux util-
isateurs vont émettre avec une puissance Pt (figure 4.12).
Puisque les deux utilisateurs sont à des distances différentes de
la station de base, la puissance reçue de l’utilisateur 2 au niveau
de la station de base (P r2) est plus grande que la puissance reçue
de l’utilisateur 1 (P r1 ). Supposons que la différence de distance
est telle que P r2 est 10 fois plus grande que P r1 et que le rapport
signal sur bruit (SNR)requis = (S/N)requis = 1/10.
Si on ignore le bruit thermique, le SNR de l’utilisateur 2 est
(S/N)2 = 10 et celui de l’utilisateur 1 est (S/N)1 = 1/10.
Nous remarquons que sans le contrôle de puissance, il n’y a pas
d’équité entre les utilisateurs. C’est le problème du “near-far”.
96 Comparaison des différentes techniques de multiplexage

Pt
Pr1 P r2 Pr Pr
Pt Pt
Pt Pt

Pr
Pr
Utilisateur 2
BTS BTS
Utilisateur 1 Pt

Figure 4.12: Problème du Near-far Figure 4.13: Contrôle de puissance

A ce stade là, un troisième utilisateur ne pourra pas être admis

dans le réseau puisqu’il ne pourra pas avoir son S/N requis et in-
duira une baisse du rapport S/N de l’utilisateur 2 en dessous du
S/Nrequis . Donc, le système a atteint sa capacité avec deux utilisa-
teurs.

Afin de maximiser la capacité du système et de résoudre le

problème su “near-far”, le contrôle de puissance devrait être implémenté.
Ainsi, la puissance transmise de chaque utilisateur dans la cellule
est contrôlée de telle manière que la puissance reçue à la station
de base est identique pour tous les utilisateurs et est égale à Pr
(figure 4.13). De cette manière, le nombre d’utilisateurs admis
au système sera maximisé. Ainsi, pour un (S/N)requis = 1/10, 11
utilisateurs seront admis dans la cellule.

4.6.4 Capacité des systèmes CDMA

La capacité du système CDMA est limitée par l’interférence alors
qu’elle est limitée en bande passante dans les systèmes FDMA et
TDMA. Il est à noter que la réduction en interférence dans le
système CDMA cause une augmentation en capacité.

Dimensionnement d’un système CDMA : évaluation de la capacité

Considérons un système à une seule cellule ayant plusieurs utilisa-

teurs communiquant à une seule station de base. Si le contrôle de
puissance est implémenté, tous les signaux sur la voie montante
sont reçus à égale puissance au niveau de la station de base.
4.6 Accès Multiple à Répartition par les Codes 97

Soit N le nombre d’utilisateurs dans la cellule. Chaque démodulateur

au niveau de la station de base reçoit le signal désiré de puissance
S et N − 1 signaux interférents de puissance S. Donc, le rapport
signal sur bruit est :

S 1
SNR = =
(N − 1)S N −1
En plus du rapport SNR, le rapport (Eb/N0) est un paramètre
important dans les systèmes de communication. Notons que Eb
est l’énergie d’un bit transmis et N0 est la densité du bruit. Il est
obtenu en divisant la puissance du signal sur le débit R en bande
de base et la puissance d’interférence sur la bande passante totale
W . Ainsi,

Eb S/R W/R
= =
N0 (N − 1)S/W N −1
Cette équation ne prend pas en compte le bruit thermique η en
bande étalée. Afin de prendre ce bruit en compte, nous écrivons:

Eb W/R
= (4.3)
N0 (N − 1) + η/S
Donc, le nombre d’utilisateurs dans une cellule est:

W/R η
N = 1+ − (4.4)
Eb/N0 S
Il est à noter que la réduction en interférence dans le système
CDMA cause une augmentation en capacité. Afin de réduire les
interférences, deux techniques sont utilisées :

• L’utilisation des antennes directives. Les antennes directives

,”multi-sectorized antennas”, couvrent plusieurs secteurs et
induisent une isolation spatiale des utilisateurs. Notons que
dans les ouvrages américains, la surface couverte par une an-
tenne est appelée “secteur”. Ces antennes directives reçoivent
des signaux émanant d’une fraction des utilisateurs actifs dans
une cellule. Ce qui réduit l’interférence au niveau de la sta-
tion de base. Ainsi, une cellule ayant trois antennes directives
recouvrant chacune un angle de 120 degrés a une interférence
98 Comparaison des différentes techniques de multiplexage

N ′ 0 égale au tiers de l’interférence obtenue avec une antenne

omnidirectionnelle. Ceci permet d’augmenter approximative-
ment la capacité d’un facteur égal à 3.

• La transmission en mode discontinu (DTX). Il est rare que

deux intervenants parlent en même temps. De plus les car-
actéristiques de parole font apparaı̂tre des silences très courts
entre les mots.
La transmission discontinue ou DTX consiste à interrompre
l’émission pendant les silences de parole pour diminuer l’énergie
émise sur la voie montante. Ceci permet, d’une part de réduire
la consommation des stations mobiles et d’allonger la période
d’autonomie du mobile, et d’autre part de diminuer le niveau
d’interférence généré et donc d’augmenter la capacité du système.

L’activité de la voix est exprimée par un facteur α. Le terme

d’interférence dans l’équation 4.3 devient (Ns − 1)α où Ns est
le nombre d’utilisateurs par secteur.

En utilisant ces deux techniques, le rapport Eb/N ′ 0 dans chaque

secteur devient alors :

Eb W/R
′
= (4.5)
N0 (Ns − 1)α + η/S
Dans un système limité par l’interférence plutôt que par le bruit,
le nombre d’utilisateurs est :
1 W/R
Ns = 1 + ( ) (4.6)
α Eb/N ′ 0

Si le facteur d’activité de voix α = 3/8 et s’il existe 3 secteurs

par cellule, l’équation 4.6 montre que le nombre d’utilisateurs aug-
mente de 8% par rapport à un système ayant une antenne omnidi-
rectionnelle et sans le mode DTX.

A titre d’exemple, supposons que W = 1.25MHz, R = 9600bps

et le minimum Eb/N0 acceptable est 10db. Déterminons alors le
4.6 Accès Multiple à Répartition par les Codes 99

nombre maximum d’utilisateurs admis dans un réseau mobile à une

cellule adoptant la technique CDMA en utilisant :

1. une station de base avec une antenne omnidirectionnelle sans

détection de l’activité voix.

2. trois secteurs par station de base et une détection d’activité

de voix avec α = 3/8.

Nous supposons que le système est limité uniquement en in-

terférence.

Pour un système ayant une antenne omnidirectionnelle et sans

détection de l’activité voix, l’équation 4.4 donne :

W/R 1.25 ∗ 106 /9600

N = 1+ =1+ = 1 + 13.02 = 14
Eb/N0 10
Pour un système ayant trois secteurs par station de base et une
détection d’activité de voix, l’équation 4.6 donne :

1 1.25 ∗ 106 /9600

Ns = 1 + ( ) = 35.7
0.375 10
Dans ce cas, le nombre total d’utilisateurs est égal à [Link] puisqu’il
y a trois secteurs par cellule. Donc, le nombre d’utilisateurs par
cellule est :

N = 3 ∗ Ns = 3 ∗ 35.7 = 107
Nous remarquons que la sectorisation et l’emploi du mode DTX
permettent d’augmenter la capacité du réseau.

4.6.5 Allocation du spectre dans le réseau UMTS

L’ITU a essayé d’harmoniser les technologies des réseaux de troisième
génération afin d’obtenir une interface radio commune. Deux can-
didats ETSI et ARIB ont décidé de faire un standard commun de
l’UMTS sous le contexte du projet Third Generation Partnership
Project 3GPP. Ces candidats ont adopté la technique WCDMA
qui repose sur CDMA à large bande.
100 Comparaison des différentes techniques de multiplexage

Le CDMA utilisé dans le cadre de l’UTRAN (réseau d’accès

de l’UMTS), est le WCDMA (Wide band CDMA) qui, comme
son nom l’indique, utilise une bande de fréquences plus large que
d’autres systèmes CDMA (IS-95 par exemple).

L’objectif de l’UMTS est de proposer,en plus du transport de la

voix, un grand nombres de services comme le transport de données
multimédias ou l’acheminement de données informatiques à haut
débit. Plusieurs services peuvent donc être utilisés à un même
instant sur un même émetteur, ce qui fait apparaı̂tre un deuxième
niveau de multiplexage qui est le multiplexage inter-services. Ainsi,
la modulation d’un signal d’information s’effectue en deux étapes :
• l’étalement des signaux d’informations issus des services d’un
utilisateur (multiplexage inter-services).

• le brouillage (ou scrambling), du signal résultant, par une

séquence aléatoire propre à chaque utilisateur (multiplexage
inter-utilisateurs).

La séquence résultante est alors envoyée sur l’interface radio.

WCDMA utilise une trame radio de 10ms et est divisée en 15
slots. Chaque slot dure 0.667ms. Pour un débit de 3.84Mcps, il y
a 38400 chips par trame et 2560 chips par slot.

4.7 Comparaison des différentes techniques

de multiplexage
A ce stade du chapitre, nous allons comparer les performances des
trois techniques de multiplexage.

4.7.1 Les hypothèses de modélisation

Nous allons comparer à l’aide d’un modèle intermédiaire, basé sur
la file M/GI/1, les performances des trois techniques de multiplex-
ages considéreées dans la section précédente. Dans certaines situa-
tions, nous allons prendre des cas particuliers comme la file M/M/1
ou la file M/D/1.
4.7 Comparaison des différentes techniques de multiplexage 101

Nous allons considérer une liaison qui relie deux multiplexeurs

M1 et M2 . La vitesse de la liaison est supposée être de c bit/s.
Sans limiter la généralité de l’exposé, nous allons principale-
ment analyser le cas d’un système symétrique ce qui permet de
restreindre les calculs au transfert de l’information dans une seule
direction. Le nombre de terminaux connectés est supposé être égal
à n sur chaque multiplexeur extrêmité.
Pour limiter la complexité mathématique du chapitre, nous sup-
posons que chaque terminal génère un trafic d’unités de données
(paquets, trames) suivant une loi de Poisson d’intensité λi ; i =
△ P
1, · · · , n unités de données par seconde. Notons Λ = ni=1 λi l’intensité
du trafic total qui arrive dans le système.
Soit Li la longueur en octets d’une unité de données de la classe
i. La distribution de Li est supposée être de type GI. Soit E[Li ] = li
la longueur moyenne (en octets) d’un paquet de la classe i. Notons

• ρi = (λi 8li /c) le facteur de charge de la liaison dû à la classe i,

• ρ = ni=1 ρi la charge totale de la liaison due à toutes les classes.

Il est clair que la condition nécessaire et suffisante de stabilité

du système est que ρ < 1. Nous allons supposer par la suite que le
système est stable.
Le temps de service de la classe i est noté Xi , i = 1, · · · , n. Ce
temps dépend du schèma du multiplexage choisi. De toute manière,
la distribution de Xi est de type GI. Si la bande passante allouée à
la classe i est ci bit/s, alors la relation entre Li et Xi est donnée par
Xi = 8Li /ci donc E[Xi ] = 8li /ci . Nous notons Xi∗ (s) la transformée de
Laplace de la loi (densité) de Xi .
Nous allons négliger les erreurs de transmission sur la liaison.

4.7.2 L’analyse du multiplexage en fréquence FDMA

Dans cette technique, le multiplexeur alloue une partie de la bande
passante à une communication établie entre les deux ETTDs qui
vont donc utiliser un schèma de modulation (fréquence, phase)
pour échanger leurs données. Le schèma d’allocation est statique.
La bande passante allouée est dédiée à la communication. Dans
102 Comparaison des différentes techniques de multiplexage

'$
- -

λ PDU/s c/n bit/s

..
.

λ PDU/s c/n bit/s

'$
- -

Figure 4.14: n files M/GI/1

une système symétrique, si l’on suppose qu’il y a n communica-

tions établies, il est courant de fixer la bande passante allouée à
la communication i à ci = c(ρi /ρ) bit/s pour i = 1, · · · , n. En parti-
culier, quand le trafic échangé entre les terminaux extrêmités est
de même nature (transactionnel, email, . . . ) et quand l’intensité
des arrivées est la même λi = λ on peut choisir ci = c/n. Donc le
modèle de file d’attente du système est composé de n files M/GI/1
en parallèle, où le taux moyen d’arrivée par file est λi unités de
données par seconde, et la capacité de service du serveur d’une file
est de ci bit/s, i = 1, · · · , n (voir figure 4.14).
La charge du système induite par une communication est:

8li
ρi,F DM A = λi E[Xi ] = λi
ci
Utilisant les résultats de la file M/GI/1 on obtient que le nombre
moyen d’unités de données dans le canal i est

λ2i E[Xi2 ]
E[Yi] = ρi,F DM A +
2(1 − ρi,F DM A )
D’où un nombre moyen total d’unité de données dans le système
4.7 Comparaison des différentes techniques de multiplexage 103

est égal à
n
X
E[Y ] = E[Yi ]
i=1

Le délai de transit d’une unité de données de la classe i dans le

système est

2
λi E[Xi2 ] ρi,F DM A E[Xi ] (1 + CX )
E[Si,F DM A] = E[Xi ] + = E[Xi ] + i

2(1 − ρi,F DM A ) 2(1 − ρi,F DM A )

Deux cas particuliers peuvent être considérés

2
• le cas d’un service exponentiellement distribué, où CX i
= 1,
2
• le cas d’un service constant où CX i
= 0.

Dans un système symétrique où λi = λ1 , Li = L1 , li = l1 et ci = c/n,

on obtient

8l1 n
E[Xi ] =
c
8l1 n
ρi,F DM A = ρ1,F DM A = λ1 pour i = 1, · · · , n
c
ρ1,F DM A étant la charge due à une seule communication et ρF DM A =
nρ1,F DM A la charge totale du multiplexeur due à toutes les commu-
nications.
A partir de la fonction génératrice du nombre de paquets dans
la file i

(1 − ρi )(1 − z)
E z Yi = Xi∗ (λi − λi z) ∗

Xi (λi − λi z) − z
il est possible d’avoir analytiquement (mais la forme est com-
pliquée) et numériquement la distribution de probabilité du nom-
bre de clients dans chaque file i. Cela permet, par exemple, de
calculer la probabilité de dépassement de seuil et donc d’estimer la
probabilité de perte par congestion. Considérons en particulier le
cas simple d’un service exponentiel (files M/M/1). Soit Φ la taille
de la mémoire disponible dans le multiplexeur. Notons par mi,max
104 Comparaison des différentes techniques de multiplexage

la taille maximale de mémoire pouvant être allouée à une commu-

nication i. Alors la probabilité de perte par dépassement de seuil
est liée à la charge du canal et à la mémoire disponible par

m
pi,F DM A = P{Yi ≥ mi,max } = ρi,Fi,max
DM A

La somme des mi,max correspondant à toutes les communications

ne doit pas dépasser un certain pourcentage de Φ, par exemple
n
X
mi,max ≤ αΦ avec 0.8 ≤ α < 0.95
i=1

4.7.3 Le multiplexage temporel synchrone

Si dans le système il y a n communications actives, le multiplexeur
alloue, sur une unité de temps de fonctionnement, et pour une
communication établie i, toute la bande passante du canal pendant
P
une fraction αi de l’unité de temps avec i αi = 1. Donc tout se
passe comme si seulement αi c = ci bit/s sont alloués à la communi-
cation i. Ainsi, le modèle de file d’attente du système est identique
à la technique FDMA précédente.
Donc les performances de la technique FDMA et TDMA vont
être identiques. En particulier :

E[Si,F DM A ] = E[Si,T DM A ]

4.7.4 Le multiplexage temporel asynchrone (statistique)

Dans cette technique, les n flux des n communications seront su-
perposés dans une même file d’attente d’un système où la capacité
totale de service est de c bit/s. Le modèle de file d’attente du
système est composé d’une file M/GI/1 multiclasse où le processus
P
d’arrivée est Poisson d’intensité λ = i λi , et le serveur (unique)
est de capacité totale c bit/s
Nous allons effectuer l’analyse de la superposition de n flux de
trafic, chacun étant modélisés par un processus de Poisson. Nous
allons supposer que ces flux sont mutuellement indépendants. La
superposition a lieu dans une file d’attente où chaque flux recquiert
4.7 Comparaison des différentes techniques de multiplexage 105

un service distribué suivant un processus de renouvellement noté

Xi pour le flux i avec i = 1, · · · , n. Dans le contexte présent, le
service requis Xi par un client de la classe i est lié à la longueur Li
du paquet de la classe et à la vitesse de sortie du multiplexeur c
par Xi = 8Li /c.
En posant

λi
pi =
λ
n
△
X
E[X] = pi E[Xi ]
i=1
n n
△
X X
ρST AT = ρ = ρi = λi E[Xi ] = λE[X]
i=1 i=1
On rappelle l’équation d’état de la chaı̂ne incluse

Yk+1 = Yk − δYk + AXk+1

qui lie le nombre de clients laissés dans le système après le kieme
départ et celui laissé après le (k + 1)ieme départ.
Nous avons étudié cette chaı̂ne incluse dans le chapitre qui
présente la file M/GI/1 multiclasse où nous avons montré que sous
l’hypothèse ρ < 1, elle est est récurrente positive et possède une dis-
tribution de probabilité stationnaire. Nous avons calculé sa fonc-
tion génératrice et montré que :

λ ni=1 λi (σX
2
+ (E[Xi ])2 )
P
E[Y ] = ρ + i

2(1 − ρ)
Nous avons également montré que le temps de séjour moyen
d’un client de la classe i donné par :
Pn 2
i=1 λi (σX + (E[Xi ])2 )
E[Si ] = E[Xi ] + i
(4.7)
2(1 − ρ)
= E[X] + E[W ]
et le temps d’attente moyen dans la file qui est indépendant de
la classe est donné par :
Pn 2
λi (σX + (E[Xi ])2 )
E[W ] = i=1 i

2(1 − ρ)
106 Comparaison des différentes techniques de multiplexage

Cas particulier d’un système symétrique

Dans un système symétrique, la charge du multiplexeur statis-
tique induite par l’ensemble des communications

8l1 8l1 n
ρ = ρST AT = nλ1 = ρ1,F DM A = λ1
c c
Donc cette charge est égale à celle induite par une seule com-
munication dans les deux cas précédents.
Posons :

ρST AT = ρF DM A = ρT DM A = ρ
Le délai de transit moyen dans le multiplexeur statistique dans
le cas symétrique se simplifie compte tenu de Xi = X1 = X, i =
1, · · · , n

2
λ(σX + (E[X])2 )
E[S] = E[X] + (4.8)
2(1 − ρ)
λE[X 2 ]
= E[X] +
2(1 − ρ)

Comme E[X] est n fois inférieur dans le multiplexeur statistique

et que le ρ est le même, le temps de transit dans le multiplexeur
statistique est inférieur à celui du multiplexeur FDMA et TDMA.
D’autre part, le taux global d’arrivée étant le même dans les
trois cas (FDMA, TDMA, STAT), utilisant la formule de Little, on
obtient que le nombre moyen de clients dans dans le multiplexeur
statistique est inférieur à celui trouvé dans le multiplexeur FDMA
et TDMA. il en est de même de la probabilité de perte d’une unité
de données qui est inférieure dans le multiplexeur statistique que
dans les deux autres multiplexeurs.

4.8 Quelques conclusions

La modélisation précédente est basée sur un processus d’arrivée de
type Poisson. La généralisation au cas de processus d’arrivée de
type GI n’est pas tractable analytiquement. En effet, il est possible
de montrer que la somme de deux processus de renouvellement
4.8 Quelques conclusions 107

n’est un processus de renouvellement que dans le cas des processus

de Poisson.
Les résultats obtenues montrent que, par rapport aux deux
autres techniques et dans le cas d’un trafic aléatoire qui suit une
loi de Poisson, avec une loi de service requis de type Poisson, le
multiplexage statistique présente des avantages en terme de per-
formances au niveau du délai, de l’occupation mémoire et de la
probabilité de perte par dépassement de seuil. Les résultats restent
valables quand la statistique du trafic et du service requis suivent
des lois plus générales. En effet, il est possible de montrer en util-
isant la formule de P-K pour la file GI/GI/1 que le délái moyen
dans une file diminue quand la puissance de traitement augmente
en même temps que l’intensité du trafic pour un même facteur de
charge ρ. En concentrant la puissance de traitement on gagne sur
le délai.
Malheureusement, ces performances ont un prix : la non con-
servation de la nature statistique du trafic après le transit dans le
multiplexeur. En effet, il est possible de voir que la superposition
de trafic de type GI ne donne du GI que pour les processus de Pois-
son. De plus, même quand le trafic entrant est Poisson, il perdra
cette caractéristique dès qu’il traverse le multiplexeur dont la loi
de service n’est pas de type Poisson. Ainsi, la superposition d’un
trafic déterministe avec un trafic Poisson altèrera la statistique des
deux trafics en question.
Si le trafic de données est généralement assez tolérant relative-
ment à un certain délai ainsi qu’à la variation de ce délai, il n’en
est pas de même pour le trafic audio qui est exigeant sur ces deux
points. Ceci explique que la technique du multiplexage statistique
soit plutôt utilisée dans les réseaux à commutation de paquets,
tandis que la téléphonie utilise la commutation de circuit basée sur
les deux autres techniques du multiplexage. Il apparaı̂t néanmoins
que les avantages du multiplexage statistique soient suffisamment
importants pour que le monde des télécommunications ait retenu
cette technique comme mode de transfert dans le futur RNIS large
bande. En effet, ce réseau est sensé transporter un volume impor-
tant de trafic sporadique la vidéo à haute définition où encore la
transmission de données à haute vitesse.
108 Comparaison des différentes techniques de multiplexage
Chapter 5

Gestion de la mobilité

5.1 Introduction
Avec l’avènement des réseaux de troisième génération et la con-
ception des réseaux de quatrième génération, le déploiement des
services s’avère d’une importance cruciale pour les réseaux mo-
biles. En effet, les réseaux actuels sont en train d’évoluer vers une
architecture où différents types de services avec des exigences en
qualité de service différentes coexistent.
Parmi les services proposés par les opérateurs, nous relevons un
service indispensable au bon fonctionnement des réseaux mobiles:
la mobilité. La fourniture du service de mobilité constitue l’élément
clé dans les communications sans fil et fait toute l’originalité des
réseaux mobiles.
Nous pouvons distinguer entre deux types de mobilité:

1. La mobilité de l’utilisateur: Ce type de mobilité fournit à

l’utilisateur la possibilité de communiquer avec d’autres ter-
minaux en différentes localisations tout en se déplaçant d’une
cellule à une autre.
Cette mobilité est caractérisée par trois fonctionnalités impor-
tantes : le nomadisme, la mobilité horizontale et la mobilité
verticale.

• Nomadisme: Le nomadisme permet à l’utilisateur d’avoir

accès au réseau à partir de plusieurs points d’accès. Il
110 Gestion de la mobilité

inclut la fourniture de service à un abonné en itinérance

dans des réseaux différents.
Lorsqu’il se déplace d’un réseau à un autre, l’utilisateur
mobile s’attend à trouver ses services requis, et ceci même
s’il change de terminal. Le réseau devrait fournir des
informations relatives à l’existence, la localisation et la
configuration des services.
• La mobilité horizontale: Elle caractérise la mobilité en-
tre des réseaux de même technologie. Pour des réseaux
basés sur la technologie IP, la mobilité horizontale cor-
respond à la mobilité avec laquelle l’interface du noeud
mobile ne change pas du point de vue IP. Pour ce type de
réseaux, la mobilité concerne la mobilité entre des réseaux
de même technologie. D’autre part, elle peut caractériser
la mobilité entre des réseaux de technologie différente si
le noeud mobile effectue un handover sans changement
d’adresse IP. Dans ce cas, ce type de mobilité ne nécessite
pas l’intervention du réseau coeur.
• La mobilité verticale: Elle caractérise la mobilité entre
des réseaux de technologie différente. Pour des réseaux
basés sur la technologie IP, la mobilité verticale corre-
spond à la mobilité avec laquelle l’interface du noeud mo-
bile change du point de vue IP. Pour les réseaux IP, la
mobilité verticale concerne la mobilité entre des réseaux
de technologie différente. Cependant, elle peut également
caractériser la mobilité entre des réseaux de même tech-
nologie si le noeud mobile effectue un handover en changeant
d’adresse IP. Dans ce cas, ce type de mobilité nécessite
l’intervention du réseau coeur.

2. La mobilité du réseau: Ce type de mobilité concerne la mo-

bilité de certains noeuds du réseau. A titre d’exemple, citons
les réseaux ad hoc qui sont des réseaux sans infrastructure
et où tous les noeuds bougent. D’autres types de réseaux où
ce type de mobilité se manifeste seraient les réseaux satelli-
taires LEO (Low Earth Orbiting) ou MEO (Medium Earth
Orbiting).
5.2 Handover 111

Dans ce chapitre, nous traitons la mobilité de l’utilisateur. C’est

pourquoi, nous désignons par mobilité la mobilité de l’utilisateur.
Deux types de problèmes apparaissent lors de la gestion de la
mobilité de l’utilisateur. Le premier problème concerne la localisa-
tion des terminaux inactifs afin de réagir rapidement aux requêtes
provenant du réseau et afin d’établir des communications avec ces
terminaux en un temps optimal.
Le deuxième problème réside dans le fait qu’un utilisateur actif
en mouvement quitte la zone où son réseau d’accès est capable de
lui fournir un certain niveau de qualité de service. Ce problème est
à caractère temps réel et devrait assurer la fourniture de qualité
de service à certaines classes de service exigeant une faible perte
de paquets, des délais et des gigues réduits.

Ce chapitre traite les problématiques du processus du Handover

(HO) dans les réseaux mobiles sans fil. La gestion du handover con-
stitue un important défi à relever et détermine la performance des
réseaux mobiles. En effet, un appel d’un utilisateur fixe ou mo-
bile doit être transféré d’une cellule à une autre lorsque l’appel en
progrès ne peut bénéficier d’un canal de communication conven-
able dans la cellule courante à cause de la mobilité de l’utilisateur,
du mouvement du satellite ou pour des raisons de propagation. Le
handover établit le transfert de liaison de communication du canal
courant à un autre canal.
Comme l’échec du handover est moins souhaitable que le re-
jet d’un nouvel appel, nous effectuons une étude poussée sur les
différentes stratégies de priorité des requêtes de handover sur les
nouveaux appels.

5.2 Handover
Le handover concerne le changement du canal radio utilisé par un
terminal mobile. Le nouveau canal alloué peut être dans la même
cellule que celle de l’utilisateur ou dans une cellule différente.
Le handover est initié lorsque le mobile traverse la région de
Handover formée par l’entrelacement de deux régions de recou-
112 Gestion de la mobilité

R a tio o f p o w e r
r e c e iv e d fr o m c u r r e n t
B S to n e x t B S H a n d o v e r th re s h o ld

R e c e iv e r th re s h o ld

t0 t1 tim e

Figure 5.1: Processus du Handover

vrement. Dans cette région, un appel peut être traité par deux
stations. Le temps mis par le mobile dans la région de handover
est appelé ”intervalle de dégradation”.
Le processus du handover est initié lorsque la puissance reçue
par le mobile de la station de base d’une cellule voisine est plus
grande que celle reçue par la station de base courante d’un certaine
valeur. Cette valeur est appelée le handover threshold.

Pour que le handover s’établisse avec succès, un canal devrait

être alloué à la requête handover avant que le rapport des puis-
sances reçues par le mobile atteigne le receiver threshold. Ce
dernier est le seuil du rapport de puissances reçues au dessous
duquel une communication acceptable avec la station de base de la
cellule courante n’est plus possible.
La région du handover est la région où le rapport des puis-
sances reçues par la station de base courante et voisine est entre
le handover threshold et le receiver threshold (figure 5.1). Si ce
rapport de puissances devient inférieur au receiver threshold et si
aucun canal n’est alloué à l’appel handover dans la cellule candi-
date, l’appel en cours est alors forcé à se terminer. Dans ce cas, le
handover a échoué.
5.2 Handover 113

5.2.1 Raisons de l’initiation du Handover

La raison majeure de l’initiation du handover est la dégradation de
la qualité de liaison. Néanmoins, le handover peut être initié pour
d’autres raisons. Citons entre autres:

• La réduction de la congestion. Dans le cas où une congestion

a lieu dans la cellule courante, un appel peut être servi par
une cellule alternative.

• La satisfaction de la QoS exigée. Si la cellule courante ne

peut satisfaire la qualité de service exigée par l’utilisateur,
l’appel est servi par une autre cellule pouvant satisfaire les
paramètres de QoS requis.

• L’itinérance ou roaming. Un fournisseur de service pourrait

empêcher les abonnés de passer à certains réseaux particuliers.

• Le handover hiérarchique. La politique des opérateurs peut

consister à diriger les appels générés par les utilisateurs à
faible vitesse vers les cellules de faible dimension. Ainsi, les
utilisateurs ayant une grande vitesse sont acceptés dans les
cellules de grande dimension. Ceci réduit la fréquence des
handovers et par conséquent le trafic de signalisation. Nous
abordons le handover hiérarchique à la section 5.3.

5.2.2 Procédure du Handover

L’établissement du handover passe par trois phases:

1. L’initiation/décision du Handover: Durant cette phase, une

décision est prise afin d’initier le handover. Cette décision est
basée sur les mesures de la qualité de liaison effectuées par le
terminal ou par le réseau. Quatre stratégies de handover sont
proposées suivant que le terminal ou la station de base décide
d’initier le handover. Ces quatre stratégies sont:

• Le ”Network Controlled HandOver” (NCHO): Le réseau

mesure périodiquement la puissance du signal dans le sens
114 Gestion de la mobilité

montant et initie le processus du handover suivant les

mesures effectuées. Les avantages de cette méthode sont
la signalisation réduite et la faible complexité du terminal.
Cependant, cette méthode manque de fiabilité puisqu’elle
est basée uniquement sur les mesures radio de la liai-
son montante et puisqu’elle ne prend pas en compte les
mesures sur la liaison descendante.

• Le ”Mobile Controlled HandOver” (MCHO): Le termi-

nal mobile mesure la puissance du signal dans le sens
descendant ainsi que la puissance des signaux en prove-
nance des cellules adjacentes. Compte tenu des mesures
effectuées, le mobile décide d’effectuer le handover à la
station de base estimée comme étant la meilleure can-
didate pour le handover. La stratégie MCHO garan-
tit l’établissement du handover en un temps optimal et
réduit la complexité des terminaux mobiles. Cependant,
cette stratégie n’est pas fiable puisqu’elle est uniquement
basée sur les mesures effectuées sur la liaison descendante.

• Le ”Mobile Assisted HandOver” (MAHO): Dans ce cas, le

réseau et le mobile effectuent conjointement des mesures
des liaisons radio dans le sens montant et descendant.
Les mesures effectuées sur la liaison descendante par le
terminal mobile sont envoyées périodiquement au réseau.
La décision du handover est prise alors par le réseau.
Cette décision est basée sur les mesures effectuées sur
les liaisons descendante et montante. La fréquence des
mesures effectuées est un paramètre important qui de-
vrait être bien calibré.
Si les mesures de fréquence sont très fréquentes, une
charge de signalisation très importante sera générée. D’autre
part, les mesures devraient être assez fréquentes pour
avoir une réponse rapide en cas de handover.

• Le ”Network Assisted HanOver” (NAHO): Avec cette

5.2 Handover 115

stratégie, la décision d’initiaion du handover est prise

par le terminal mobile. Cette décision est basée sur les
mesures sur les liaisons dans les sens montant et descen-
dant. Le réseau informe le terminal mobile des mesures
effectuées sur le sens montant. Ainsi, le mobile effectue
la décision du handover avec l’aide du réseau. Avec cette
méthode, le handover est établi dune manière plus fiable
aux dépens de la complexité du terminal et de l’augmentation
du trafic de signalisation.

2. Détermination de la cellule cible et déclenchement: Lorsque

la décision d’initier le handover est effectuée, une cellule cible
devrait être déterminée afin d’offrir le service à l’appel en
cours. Le problème d’allocation de ressources devrait être
réglé par le réseau à ce stade là.

3. Exécution du handover : Cette phase constitue le transfert

effectif de liens. En effet, une fois que la station de base est
sélectionnée, une procédure de signalisation est nécessaire afin
d’établir le handover et afin d’informer le terminal et la station
de base du transfert des liens et de l’allocation de ressources.
La procédure de signalisation devrait être assez rapide et fi-
able afin de réduire la perte des paquets.

Pour l’exécution du handover, nous distinguons entre le hard

handover et le soft handover suivant que la technologie TDMA/FDMA
ou CDMA est préconisée par le réseau mobile.
Avec la technologie CDMA, un terminal mobile peut capter
deux stations de base en même temps. Par conséquent, la
liaison avec la station de base courante est maintenue lors du
handover vers la station de base choisie. Ce type de handover
est connu sous le nom de soft handover
Avec la technologie TDMA/FDMA, un terminal mobile ne
peut capter deux stations de base en même temps. Par conséquent,
la liaison avec la station de base courante est coupée lors du
handover vers la station de base choisie.
116 Gestion de la mobilité

Nouvel appel ou HO

Oui Canal Appel en

Canal Canal Libéré
Libre ? Alloué progression

Non

Appel Bloqué

Figure 5.2: Organigramme du schéma NPS

5.2.3 Stratégies de priorité des appels Handover

Dans les réseaux mobiles sans fil, il est particulièrement utile de
réduire le nombre d’appels forcés à se terminer. En effet, la termi-
naison forcée de l’appel est un phénomène gênant à l’utilisateur. En
outre, la terminaison forcée de l’appel établi est moins souhaitable
que le rejet d’un nouvel appel. Dans cette optique, plusieurs
stratégies de priorité des appels handover sur les nouveaux appels
ont été proposées dans les travaux de recherche. Ces stratégies
réduisent l’échec du Handover tout en augmentant le blocage des
nouveaux appels.
Nous distinguons entre trois stratégies de priorité :

1. La Réservation des canaux de garde ou RCS (Reserved Chan-

nel Scheme).

2. La mise en queue des requêtes Handover.

3. La technique de Sub-rating.

Ces stratégies de priorité permettent d’améliorer les perfor-

mances du réseau mobile contrairement au shémas standard connu
sous le nom du ”Non-Prioritized Scheme” ou NPS.
Avec NPS, les appels handover sont traités de la même manière
que les nouveaux appels comme illustré à la figure 5.2. C’est
5.2 Handover 117

Nouvel appel

Nombre de Canal Appel en Canal

Oui
canaux occupés Alloué progression Libéré
<N-Ch ?

Non

Appel Bloqué

Figure 5.3: Organigramme du schéma RCS pour les nouveaux appels : N et

Ch désignent le nombre de canaux dans la cellule et le nombre de canaux de
garde

pourquoi la probabilité de blocage des appels handover est égale à

celle des nouveaux appels.

Réservation des canaux de garde (RCS) La stratégie RCS est une

méthode simple qui consiste à réserver des canaux pour les appels
handover dans chaque cellule. Ainsi les canaux disponibles dans
chaque cellule sont divisés en deux ensembles. Le premier ensemble
de canaux est utilisé aussi bien par les nouveaux appels que par
les appels handover. Le second ensemble de canaux est dédié aux
appels handover. Ces canaux réservés sont appelés canaux de garde
(figures 5.3 et 5.4).
La stratégie RCS améliore les performances du réseau en terme
de probabilité de blocage des appels handover tout en réduisant
la capacité totale du système et en augmentant la probabilité du
blocage des nouveaux appels.

La mise en queue des requêtes Handover La technique de mise en

queue des appels handover est une stratégie de priorité qui permet
de réduire la probabilité de terminaison forcée des appels. Cette
technique est basée sur l’existence de l’intervalle de dégradation
pendant lequel la station mobile traverse la région du handover.
Durant cet intervalle de dégradation, la qualité de la communica-
118 Gestion de la mobilité

Requête HO

Oui
Canal Canal Alloué Appel en Canal Libéré
Libre ? progression

Non

Appel Bloqué

Figure 5.4: Organigramme du schéma RCS pour les appels handover

tion se dégrade avec le déplacement du mobile. La station mobile

génère une requête handover et continue à être servie par la station
de base courante.
S’il n’y a pas de canaux libres dans la cellule voisine, la requête
handover est insérée dans une file d’attente. Dans le cas où un
canal dans la cellule voisine devient disponible avant l’expiration de
l’intervalle de dégradation, le handover peut avoir lieu avec succès
(figure 5.5). Si la station mobile traverse la région du handover et
ne trouve pas de canal disponible, l’appel en cours est forcé à se
terminer.
Dans la file d’attente allouée aux appels handover, les requêtes
handover peuvent être servies selon la discipline First-In-First-Out
(FIFO). Ainsi, la requête handover servie est la première qui arrive
à la file.
Avec la discipline Measurement-Based Priority Scheme (MBPS),
les requêtes handover sont servies suivant une discipline dynamique
non préemptive. L’objectif de cette discipline est de servir en
premier lieu les appels ayant une qualité de liaison dégradée. La
qualité de la liaison est contrôlée pour chaque requête Handover
insérée dans la queue afin de mettre à jour les positions des requêtes
dans la file. Ainsi la requête ayant la qualité de liaison la plus faible
a la plus grande priorité et est placée en tête de la file.
Plus précisément, les niveaux de puissance sont mesurées régulièrement
et les priorités des mobiles changent dynamiquement avec le niveau
5.2 Handover 119

Requête
Handover

Canal Oui Canal Alloué Appel en

Libre? progression
Oui

Non
Y-a-t-il un Non
Appel inséré dans la canal libre Terminaison
file d’attente avant la fin de forcée de l’appel
l’appel?

Figure 5.5: Organigramme de la stratégie de mise en queue des requêtes

handover

de puissance qu’ils reçoivent. Les mobiles attendant un canal

disponible dans la cellule voisine, changent de position dans la file
handover suivant leur priorité. Lorsqu’un canal est libre, il est
alloué à la station mobile ayant la plus grande priorité.

Subrating Scheme (SRS) La stratégie SRS consiste à créer un

nouveau canal dans le cas où la cellule ne dispose pas de canaux
libres. Ce canal créé est obtenu en diminuant le débit d’un appel
en cours.
En effet un canal plein-débit ou ”full-rate” est temporairement
divisé en deux canaux à demi-débit : un canal pour servir l’appel
courant et un autre pour la requête Handover (figure 5.6). Cette
technique est réservée pour les appels urgents, les appels de main-
tenance et les appels prioritaires comme les requêtes de Handover.
La technique SRS améliore la terminaison forcée de l’appel. Cepen-
dant, elle introduit de la complexité au niveau de l’implémentation
et induit de la dégradation des appels courants.
120 Gestion de la mobilité

Requête HO

Oui Canal Alloué Appel en

Canal Canal Libéré
progression
Libre ?

Non
Oui

Canal libre
pour le Terminaison Forcée
subrating ? Non de l’appel

Figure 5.6: Organigramme de la stratégie SRS

5.3 Handover dans les réseaux hiérarchiques

Un des objectifs importants dans les réseaux mobiles consiste à
servir des utilisateurs ayant des profils de mobilité différents. Dans
un premier temps, il faudrait gérer la mobilité des utilisateurs
à faible vitesse qui génèrent un taux relativement faible de han-
dover contrairement aux utilisateurs se déplaçant à grande vitesse.
C’est pourquoi, nous sommes amenés à distinguer entre deux types
d’utilisateurs mobiles:

1. Lorsqu’il est piéton dans la rue ou dans un bâtiment, l’utilisateur

se déplace à faible vitesse, de l’ordre de 3 Km/h.

2. Avec son véhicule, il se déplace à vitesse moyenne typique-

ment de 30 km/h.

Le réseau devrait minimiser la terminaison forcée des appels

des différents types d’utilisateurs tout en réduisant la signalisation
associée au processus handover. D’autre part, le trafic écoulé dans
un réseau mobile devient de plus en plus grand. D’où la nécessité
d’augmenter la capacité mesurée en Erlang/MHz/km2 .
5.3 Handover dans les réseaux hiérarchiques 121

Nous identifions ainsi deux objectifs contradictoires. Le premier

objectif consiste à réduire la signalisation du handover. Ainsi, les
cellules de large dimension sont favorisées.
Quant au deuxième objectif, il vise à maximiser la capacité du
réseau. Ceci préconise de déployer des cellules de faible dimension.
Afin de réaliser ces deux objectifs, une solution consiste à adopter
les réseaux hiérarchiques ou les réseaux multi-couches. Pour un
réseau à deux couches, on définit un espace avec l’ensemble des
micro-cellules et des macro-cellules.
Les premières n’offrent pas nécessairement une couverture con-
tinue, au contraire des secondes. En effet, le déploiement des
micro-cellules suit la distribution du trafic et en premier lieu, les
micro-cellules sont surtout présentes dans les régions à forte den-
sité de trafic.
Les micro-cellules sont recouvertes par les macro-cellules. Les
micro-cellules sont les plus adaptées aux demandes de trafic des ter-
minaux quasi-statiques ou à faible vitesse dans les régions denses.
Le système micro-cellulaire offre une bonne qualité de service aux
terminaux à faible vitesse puisque le taux d’appels Handover est
faible.
Quant aux terminaux à grande vitesse, ils sont de préférence
servis par les macro-cellules. Cette approche maintient le taux
généré des handovers à un niveau acceptable pour les deux types
de mobiles. Il est à noter que les macro-cellules peuvent offrir le
service aux utilisateurs à faible vitesse dans le cas où les requêtes
handover générées aux frontières micro-cellulaires ne peuvent avoir
lieu. Dans ce cas, les macro-cellules agissent comme des ”overflow
recipient”.
Dans les systèmes réversibles, un appel peut être repris par la
couche micro-cellulaire dès qu’une ressource est disponible à nou-
veau.

Les réseaux de troisième génération prévoient plusieurs couches

(figure 5.7) : les home-cellules, les pico-cellules, les micro-celllules
et les macro-cellules. En outre, une cinquième couche est prévue
pour le recouvrement par satellites.
122 Gestion de la mobilité

G lo b a l

S a te llite
S u b u rb a n U rb a n

M ic r o c e ll
H o m e -c e ll

M a c r o c e ll P ic o-C e ll

Figure 5.7: Réseau hiérarchique de l’UMTS

Nous associons les personnes qui travaillent dans les environ-

nements ”indoor” aux home-cellules et aux pico-cellules, les util-
isateurs roulant dans des voitures à des vitesses faibles aux micro-
cellules et les utilisateurs se déplaçant à des vitesses élevées aux
macro-cellules. Enfin, les utilisateurs voyageant dans les avions ou
navires sont associés au niveau hiérarchique le plus élevé, à savoir
le niveau satellitaire.

Les réseaux hiérarchiques présentent certains problématiques

qui méritent d’être étudiées. Dans les paragraphes suivants, nous
identifions ces problématiques.

Détermination du type des utilisateurs. Généralement, le réseau

ne connaı̂t pas le type de l’utilisateur. Ce dernier peut alternative-
ment être en voiture ou un piéton.
Il est difficile de prédire quand un utilisateur appartient à un
groupe particulier d’usagers. Des seuils sont proposés par les opérateurs
afin de différentier les utilisateurs. Ces seuils dépendent de la den-
sité de probabilité des vitesses, du temps requis pour l’établissement
du handover et du rayon de la cellule.
La classification des utilisateurs dans les réseaux hiérarchiques
aide à réduire la terminaison forcée des appels dans les cellules de
faible dimension. Cette classification réduit également la charge de
signalisation.
5.3 Handover dans les réseaux hiérarchiques 123

Détermination de la taille des micro-cellules et de la position des

stations de base dans la couche micro-cellulaire. En diminuant la
taille des cellules, il y a une augmentation de la capacité. Or, cette
diminution des tailles de cellules ne peut être répétée à l’infini.
Au-delà d’un certain seuil, la distance entre les sites devient très
faible et il n’est pas rare qu’un mobile soit en visibilité directe des
stations de base interférentes lorsque les antennes sont montées au
dessus des toits des immeubles. L’interférence subie par un mobile
devient alors très forte.
Le motif de réutilisation des fréquences doit alors être augmenté,
ce qui limite le gain en capacité. Afin de résoudre ce problème, les
opérateurs installent des stations de base micro-cellulaires avec des
puissances de transmission limitées (250 mW) et dont les antennes
sont largement au dessous des toits, typiquement à 5 mètres de
hauteur. Ainsi, la visibilité directe entre deux stations de base
diminue et il est possible de définir des motifs micro-cellulaires de
taille égale à la taille du motif macro-cellulaire, voire plus petits.
La réduction de la taille de cellule est limitée par la complexité
du système et par le coût des équipements. Par conséquent, le
choix de la taille du rayon de la cellule est un compromis entre la ca-
pacité et la complexité. Les recommandations de l’ETSI prévoient
un rayon de cellule hexagonale inférieure à 100 m pour la pico-
cellule, entre 100 et 1000 m pour la micro-cellule et supérieure à
1000 m pour la macro-cellule.

Répartition des ressources. Un des problèmes importants dans

les réseaux hiérarchiques est le partage des ressources radio rares
entre les différentes couches. La répartition spectrale s’avère très
importante afin de diminuer les interférences générées par les util-
isateurs appartenant à des couches différentes. En effet, deux types
d’interférence existent dans les réseaux à deux couches. En plus
des interférences causées par les utilisateurs appartenant à une
même couche, il existe aussi une interférence macro-micro et micro-
macro. Trois solutions existent.

1. La première consiste à partager la bande passante entre les

deux couches. Dans ce cas, chaque couche dispose de ses pro-
124 Gestion de la mobilité

pres ressources spectrales (orthogonal sharing).

2. Une solution alternative consiste à allouer les mêmes fréquences

aux différents types de cellules (spectrum sharing). Dans
ce cas, les puissances de transmission sont adaptées de telle
manière à fournir un rapport C/I acceptable, où C est la
puissance du signal reçu utile et I la puissance totale des in-
terférences reçues.
Dans ce cas, les abonnés lents se déplaçant loin de leurs sta-
tions de base dans la micro-cellule seront amenés à émettre à
des puissances élevées. Ce qui pourrait induire de grandes in-
terférences à la couche macro-celulaire. Donc, l’approche qui
semble la plus simple est celle qui consiste à effectuer un ”or-
thogonal sharing” entre les deux couches cellulaires du réseau
hiérarchique.

3. Avec la troisième solution, les différentes couches utilisent les

mêmes fréquences radio à des instants différents. Ce partage
dynamique peut être réalisé à travers une allocation dynamique
des canaux.

Les stratégies du contrôle d’admission. Une fois les fréquences

réparties entre les couches micro et macro, les terminaux peuvent
être servis par deux cellules appartenant à deux couches différentes.
La question qui se pose est de choisir la technique la plus ef-
ficace d’allocation de ressources entre les utilisateurs de mobilité
différente. C’est le rôle du contrôle d’admission.

5.4 Comparaison des performances du schéma

standard NPS et de la stratégie RCS
Dans ce qui suit, nous cherchons à comparer les performances du
schéma standard (NPS) et de la stratégie de réservation des canaux
garde (RCS). Pour ce faire, nous modélisons l’état d’une cellule
par une chaı̂ne de Markov à temps continu et à états discret. Nous
5.4 Comparaison des performances du schéma standard NPS et de la
stratégie RCS 125

résolvons alors les équations de Kolmogorov et nous sortons les

paramètres de performance pour les deux schéma.

Hypothèses et Paramètres
Avant de présenter le modèle analytique relatif à chaque stratégie,
nous présentons dans cette section les hypothèses adoptées pour
les deux stratégies.

Nous considérons une cellule dans un système homogène com-

prenant plusieurs cellules. Chaque cellule est supposée avoir une
bande passante offrant des services à des utilisateurs écoulant du
trafic voix. Ces derniers génèrent des nouveaux appels ou des ap-
pels handover.

Nous supposons que:

• g est le nombre de canaux de garde réservés exclusivement
pour les requêtes handover avec la stratégie RCS. Il est clair
que g est nul pour le schéma standard NPS.

• m est le nombre de canaux disponibles dans la cellule.

La durée d’un appel voix Tcv est supposée être exponentiellement

distribuée de moyenne 1/µcv .
Soit Tdwell le temps de séjour des utilisateurs mobiles dans une
cellule. Tdwell est supposée être exponentiellement distribué de
moyenne 1/µdwell.
Un canal occupé est libéré par un utilisateur à la fin d’un ap-
pel (c-à-d après l’expiration de la durée de l’appel) ou suite à un
handover (c-à-d après la durée du séjour dans la cellule courante).
Par conséquent, le temps d’occupation d’un canal dans une cellule
est égal à la valeur minimale de Tdwell et de Tcv .
Nous pouvons alors déduire que le temps d’occupation d’un
canal par un appel voix est exponentiellement distribué de moyenne
E[Tv ] = 1/µv tels que:
1 1
E[Tv ] = = (5.1)
µv µcv + µdwell
126 Gestion de la mobilité

n+ h n+ h n_+_ _h n+ h n+ h +
_ _n _ h

0 1 2 i-1 i i+1 m
___ ___
uv 2 uv 3 uv i uv (i+1) uv m uv

Figure 5.8: le graphe associé au générateur infinitésimal de la chaı̂ne de

Markov pour le schéma NPS

Par ailleurs, nous supposons que les processus d’arrivée des nou-
veaux appels voix et des appels Handover sont Poissonien d’intensité
λn et λh respectivement.

L’hypothèse Markovienne du trafic Handover est adoptée afin

de rendre l’analyse mathématique tractable. En effet, on peut
montrer que dans un système à blocage, le modèle poissonien du
trafic handover est raisonnable. En outre, les résultats obtenus par
simulation sont très concordants avec ceux du modèle analytique.

5.4.1 Modélisation du schéma NPS

L’état de la cellule est défini au temps t ∈ IR+ par la variable
aléatoire Xt tels que Xt est le nombre de canaux occupés par les
nouveaux appels et les appels Handover.
Le processus d’arrivée des nouveaux appels et des appels HO
dans une cellule est poissonien. D’autre part, le temps d’occupation
d’un canal est exponentiellement distribué.
L’espérance conditionnelle E(Xt+δt |Xt ) est indépendante de la
tribu σ(Xu ; u < t) où δt ∈ IR+ . Cette indépendance découle de la
propriété sans mémoire de la distribution exponentielle.
Par conséquent, (Xt ) est une chaı̂ne Markov (processus de nais-
sance et de mort) à temps continu et à états discrets. De plus, il
est facile de constater que cette chaı̂ne de Markov est irréductible
(voir le graphe associé au générateur infinitésimal de la chaı̂ne il-
lustré à la figure 5.8) et est à états finis. Par suite, la chaı̂ne ainsi
considérée est ergodique. Il en résulte que lorsque t tend vers ∞,
la chaı̂ne de Markov (Xt ) tend vers l’état stationnaire (X).
5.4 Comparaison des performances du schéma standard NPS et de la
stratégie RCS 127

Nous supposons que X prend les valeurs de i tels que i ∈ [0, .., m].
Pour faciliter le calcul des probabilités stationnaires, nous il-
lustrons dans la figure 5.8 le graphe associé au générateur in-
finitésimal de la chaı̂ne de Markov.
Le passage de l’état i à l’état i + 1 avec 0 ≤ i ≤ m − 1 se fait suite
à une arrivée d’un nouvel appel dont le processus est poissonien
d’intensité λn ou suite à l’arrivée d’un appel Handover dont le
processus est poissonien d’intensité λh .
D’autre part, le passage de l’état i + 1 à l’état i avec 0 ≤ i ≤ m − 1
se fait suite au départ de l’un des i + 1 appels servis avec un temps
de service exponentiellement distribué de moyenne 1/µv .
A ce stade là, nous nous focalisons sur le calcul des probabilités
stationnaires. Pour ce faire, nous devons résoudre les équations de
Kolmogorov à l’état stationnaire. Ces équations sont données par
l’équation µA = 0, où A est le générateur infinitésimal de la chaı̂ne
de Markov et µ est la distribution stationnaire.
Les équations de Kolmogorov s’écrivent comme suit:

(λn + λh )π0 = µπ1

(λn + λh )π0 + 2µπ2 = (λn + λh + µ)π1
.. ..
. .
(λn + λh )πm−1 = mµπm

Aux équations de Kolmogorov, nous ajoutons l’équation de nor-

malisation suivante:
m
X
πi = 1
i=0

Définissons la charge ρ telle que:

λn + λh
ρ=
µ

Les équations écrites ci-dessus nous permettent de calculer les

probabilités stationnaires qui sont telles que:
128 Gestion de la mobilité

ρi
πi = π0 pour 0 ≤ i ≤ m
i!
1
avec π0 = Pm ρk
k=0 k!

Paramètres de performance
Etant donné les probabilités stationnaires, nous essayons de tirer
les paramètres qui permettent d’évaluer la performance du système.
Les paramètres de performance visés sont la probabilité de blocage
des nouveaux appels Bnv et la probabilité de blocage des appels
Handover Bhv .

• Un nouvel appel voix est bloqué si le nombre total de canaux

occupés i est égal à N. La probabilité de blocage des nouveaux
appels voix Bnv est alors:

ρm
m!
Bnv = πm = Pm ρk (5.2)
k=0 k!

Il est facile de constater que la probabilité de blocage des nou-

veaux appels n’est autre que la probabilité obtenue par la loi
d’Erlang-B.

• Un appel handover est bloqué s’il n’y a pas de canaux disponibles.

Par conséquent, La probabilité de blocage des appels handover
voix Bhv est: m ρ
Bhv = πm = Pmm! ρk
(5.3)
k=0 k!

Donc, nous pouvons constater que les probabilités de blocage

sont égales pour les nouveaux appels et les appels handover
voix. Ce résultat résulte du fait que le schéma NPS ainsi
étudié ne préconise aucune priorité des appels handover sur
les nouveaux appels. Ainsi, les appels handover sont traités
de la même manière que les nouveaux appels.
5.4 Comparaison des performances du schéma standard NPS et de la
stratégie RCS 129

n+ n+ _n_+_ n+ h
h h h h
_ _h_ _ _h _
0 1 2 m- g-1 m- g m- g+1 m

_ _ ___

uv 2 uv 3 uv (m-g) uv (m-g+1) uv (m-g+2) uv m uv

Figure 5.9: le graphe associé au générateur infinitésimal de la chaı̂ne de

Markov pour le schéma RCS

5.4.2 Modélisation du schéma RCS

L’état de la cellule est défini au temps t ∈ IR+ par la variable
aléatoire Xt tels que Xt est le nombre de canaux occupés par les
nouveaux appels et les appels Handover du trafic voix.
Le processus d’arrivée des nouveaux appels et des appels HO
dans une cellule est poissonien. D’autre part, le temps d’occupation
d’un canal est exponentiellement distribué.
L’espérance conditionnelle E(Xt+δt |Xt ) est indépendante de la
tribu σ(Xu ; u < t) où δt ∈ IR+ . Cette indépendance découle de la
propriété sans mémoire de la distribution exponentielle.
Par conséquent, (Xt ) est une chaı̂ne Markov (processus de nais-
sance et de mort) à temps continu et à états discrets. De plus, il
est facile de constater que cette chaı̂ne de Markov est irréductible
(voir le graphe associé au générateur infinitésimal de la chaı̂ne il-
lustré à la figure 5.9) et est à états fini. Par suite, la chaı̂ne ainsi
considérée est ergodique. Il en résulte que lorsque t tend vers ∞,
la chaı̂ne de Markov (Xt ) tend vers l’état stationnaire (X).

Nous supposons que X prend les valeurs de i tels que i ∈ [0, .., m].
Pour faciliter le calcul des probabilités stationnaires, nous il-
lustrons dans la figure 5.9 le graphe associé au générateur in-
finitésimal de la chaı̂ne de Markov.
Le passage de l’état i à l’état i + 1 avec 0 ≤ i ≤ m − g − 1 se
fait suite à une arrivée d’un nouvel appel dont le processus est
poissonien d’intensité λn ou suite à l’arrivée d’un appel Handover
dont le processus est poissonien d’intensité λh .
D’autre part, la stratégie RCS préconise le seuil de blocage m−g
pour les nouveaux appels. Donc, le passage de l’état i à l’état i + 1
130 Gestion de la mobilité

avec m − g ≤ i ≤ m − 1 se fait suite à l’ arrivée d’un appel Handover

dont le processus est poissonien d’intensité λh .
D’autre part, le passage de l’état i + 1 à l’état i avec 0 ≤ i ≤ m − 1
se fait suite au départ de l’un des i + 1 appels servis avec un temps
de service exponentiellement distribué de moyenne 1/µv .
A ce stade là, nous nous focalisons sur le calcul des probabilités
stationnaires. Pour ce faire, nous devons résoudre les équations de
Kolmogorov à l’état stationnaire. Ces équations sont données par
µA = 0, où A est le générateur infinitésimal de la chaı̂ne de Markov
et µ est la distribution stationnaire.
Les équation de Kolmogorov s’écrivent comme suit:

(λn + λh )π0 = µπ1

.. ..
. .
(λn + λh )πm−g−1 + (m − g + 1)µπm−g+1 = (λh + (m − g)µ)πm−g
λh πm−g + (m − g + 2)µπm−g+2 = (λh + (m − g + 1)µ)πm−g+1
.. ..
. .
λh πm−1 = mµπm

Aux équations de Kolmogorov, nous ajoutons l’équation de nor-

malisation suivante:

m
X
πi = 1
i=0
5.4 Comparaison des performances du schéma standard NPS et de la
stratégie RCS 131

Nous pouvons alors écrire les probabilités stationnaires:

ρi
πi = π0 pour 0 ≤ i ≤ m − g
i!

ρm−g λh
πm−g+j = ( )j π0 pour 1 ≤ j ≤ g
(m − g + j)! µ
1
avec π0 = Pm−g ρi
+ ρm−g g−1 1
( λh )j
P
i=0 i! j=1 (m−g+j)! µ

Paramètres de performance
Etant donné les probabilités stationnaires, nous allons calculer les
paramètres qui permettent d’évaluer les performances du système.
Les paramètres de performance visés sont la probabilité de blocage
des nouveaux appels Bnv et la probabilité de blocage des appels
Handover Bhv .

• Un nouvel appel voix est bloqué si le nombre total de canaux

occupés i est plus grand ou égal à m − g. La probabilité de
blocage des nouveaux appels voix Bnv est alors:

g
X
Bnv = πm−g+i = πm−g + πm−g+1 + . . . + πm (5.4)
i=0

• Un appel handover est bloqué s’il n’y a pas de canaux disponibles.

Par conséquent, la probabilité de blocage des appels handover
voix Bhv est:

ρm−g λh g
Bhv = πm = ( ) π0 (5.5)
m! µ
Donc, nous pouvons constater que la probabilité de blocage
des nouveaux appels est nettement supérieure à celle des ap-
pels handover. Ce résultat prouve que le schéma RCS améliore
les performances du réseau mobile; en effet, il permet de
réduire la terminaison forcée de l’appel qui est un phénomène
assez gênant pour les utilisateurs.
132 Gestion de la mobilité
Chapter 6

Performances de protocole en
présence d’erreurs de
transmission

6.1 Relation entre les probabilités d’erreur

sur l’élément binaire et sur la trame
Les liaisons grande distance sont fournies aux usagers avec un taux
d’erreur par élément binaire garanti : par exemple 10−7 . Or, pour
pouvoir faire la détection et la reprise sur erreur, les protocoles
de liaisons travaillent sur une information structurée en trame.
Regardons d’abord la relation entre la probabilité d’erreur sur
l’élément binaire et celle sur la trame. Nous allons supposer que la
couche physique va transmettre les éléments binaires d’une trame
séquentiellement sans utilisation a priori de mécanisme d’entrelacement.

Posons

• p = probabilité d’erreur sur la trame

• q = probabilité d’erreur sur un bit

• l = la longueur de l’unité de données en bit

Nous allons supposer que la probabilité d’erreur par bit est uni-
formément distribuée. Cette hypothèse est valable quand les er-
134 Performances de protocole en présence d’erreurs de transmission

reurs ont lieu aléatoirement indépendament de toute panne sur la

liaison.

Calculons la probabilité d’erreur sur la trame en fonction de

celle sur le bit.

• Un bit est bien transmis avec la probabilité : 1 − q

• Une trame est bien transmise si tous ses bits le sont donc avec
une probabilité : (1 − q)l

• Donc la probabilité d’erreur sur la trame est : 1 − (1 − q)l

En particulier quand q est faible (ce qui est généralement le cas)

on peut approximer (1 − q)l par 1 − lq donc

p = 1 − (1 − q)l ≈ 1 − (1 − lq) = lq

En somme, et avec une bonne approximation, la relation entre

p et q est linéaire.

Dans la section suivante nous verrons comment modéliser le

protocole de reprise sur erreur dans un mode de fonctionnement
simplifié rencontré dans HDLC ou TCP.

6.2 Le modèle
Soit une connexion grande distance de vitesse C bit/s reliant deux
stations A et B. Le temps de traversé de la connexion est supposé
être égal à τ . On pose

• Ti la durée d’émission de la ième trame et E[Ti ] = ti sa moyenne.

On supposera que les Ti sont iid,

• X le nombre de trames émise entre la dernière (bonne) émission

d’une trame et la dernière (bonne) émission de la trame suiv-
ante, donc X = 1 s’il n’ y a pas d’erreurs sur le canal,
6.3 Analyse du débit utile 135

• le temps de service virtuel Tv est par définition

X
X
Tv = Ti
i=1

Ainsi, tout comme la durée d’émission d’une trame, la longueur

de la trame suit une loi générale indépendante GI.

On considérera une procédure de reprise sur erreur sans SREJ,

ie, en cas d’erreur sur la trame numéro N, on demandera la re-
transmission de toutes les trames à partir de N. Cette classe de
procédure est aussi appelée GO BACK N. On supposera que chaque
trame sera acquittée explicitement, et que la station émettrice (A
par exemple) aura toujours une trame à émettre, ce qui correspond
à un fonctionnement à forte charge.

Posons

tacq = durée jusqu’à la réception de l’acquittement dans le cadre

d’un mode de fonctionnement nominal du réseau.

Pour bien utiliser le mécanisme du contrôle de flux (voir le

chapitre correspondant pour une discussion approfondie) la valeur
minimale de la fenêtre glissante est

tacq
w=[ ]+1
E[T ]
où [α] = partie entière de α qui est l’entier le plus proche de α
par défaut. Ainsi choisie, la réponse de la destination sera reçue
par l’émetteur juste avant l’expiration de la fenêtre.

6.3 Analyse du débit utile

6.3.1 Calcul de la distribution de Tv
Compte tenu du choix de w il est facile de voir que la variable
aléatoire discrète X prend les valeurs de la forme kw + 1 avec k =
136 Performances de protocole en présence d’erreurs de transmission

0, 1, 2 · · · qui représente le nombre d’erreurs consécutives sur une

trame donnée, donc

P{X = kw + 1} = pk (1 − p)

Calculons la distribution de probabilité de Tv . Partant de l’expression

de Tv

X
X
Tv = Ti
i=1

Utilisant la transformée de Laplace Tv∗ (s) = E e−sTv

∞
X
E e−sTv = E e−sTv | X = kw + 1 P{X = kw + 1}

k=0
∞
X h Pkw+1 i
= E e−s i=1 Ti P{X = kw + 1}
k=0

Les Ti étant iid

h Pkw+1 i
E e−s i=1 Ti = [E e−sTi ]kw+1 = [T ∗ (s)]kw+1

où T ∗ (s) est la transformée de Laplace de la distribution de Ti .

D’où
∞
X
((T ∗ (s))w )k T ∗ (s)pk (1 − p)
−sTv
E e =
k=0
∞
X
∗
= (1 − p)T (s) (p(T ∗ (s))w )k
k=0

Finalement

(1 − p)T ∗ (s)
Tv∗ (s) =
1 − p(T ∗ (s))w

On remarque que quand p = 0 alors Tv∗ (s) = T ∗ (s).

6.3 Analyse du débit utile 137

6.3.2 Cas particuliers

T exponentiellement distribuée

Soit µ le paramètre de la loi exponentielle, alors

µ
T ∗ (s) =
µ+s

D’où

(1 − p)µ(µ + s)w−1
Tv∗ (s) =
(µ + s)w − pµw

Les zéros du dénominateurs sont les solutions en s de (µ + s)w =

pµw . Comme p < 1 ces solutions ont forcément ℜe(s) < 0 donc Tv∗ (s)
(tout comme T ∗ (s)) est bien analytique dans le domaine ℜe(s) > 0.

En particulier quand w = 1 correspondant au cas du feedback

instantanné, alors

(1 − p)µ
Tv∗ (s) =
s + (1 − p)µ

qui est la distribution d’une loi exponentielle de paramètre (1 −

p)µ. Du point de vue des trame, tout se passe comme si une fraction
pµ de la capacité de la liaison est perdue à cause des erreurs de
transmission, le serveur travaillant avec une capacité utile égale à
1 − p)µ.

T constante = t

Dans ce cas, Tv est une variable aléatoire discrète distribuée suivant

la loi de X. Ainsi sa fonction génératrice est donnée par
138 Performances de protocole en présence d’erreurs de transmission

∞
X
Tv
E z Tv | X = kw + 1 P{X = kw + 1}

E z =
k=0
∞
X
E z t(kw+1) pk (1 − p)

=
k=0
∞
X
= (z t )kw z t pk (1 − p)
k=0
∞
X
t
= (1 − p)z (pz tw )k
k=0

Finalement

(1 − p)z t
E z Tv =

1 − p(z t )w

6.3.3 Les moyennes

Le temps de transmission virtuel moyen est donc

d ∗
E[Tv ] = − T (s) |s=0
ds v
1 + (w − 1)p
= E[T ]
1−p

Quand T = t est constant

d Tv
E[Tv ] = E z |z=1
dz
1 + (w − 1)p
= t
1−p

En réalité dans les deux expressions ci-dessus

1 + (w − 1)p
E[X] =
1−p
et

E[Tv ] = E[T ] E[X]

6.4 Influence de la longueur de la trame sur le débit 139

En particulier si p = 0, ie en absence d’erreur, E[Tv ] coı̈ncide

avec E[T ].

Connaissant E[Tv ] on peut calculer le débit utile moyen de la

liaison exprimé en trames/s:
1 (1 − p)
α= =
E[Tv ] E[T ] (1 + (w − 1)p)

6.4 Influence de la longueur de la trame sur

le débit
On va supposer dans ce paragraphe que T = t = constante.
Pour une analyse plus fine de la transmission, nous allons dis-
tinguer dans la trame le champ des données venant de la couche
supérieure des champs des entêtes qui servent à assurer la bonne
réception de la trame. Soit l le nombre de bit d’information de la
trame, et h le nombre de bit de l’entête (6, 7 ou 8 octets dans les
trames HDLC).

Suite à la discussion dans la première section p est liée à q par

p = 1 − (1 − q)l+h
Quand q est petit (1 − q)l+h ≈ 1 − (l + h)q d’où p ≈ (l + h)q.

Si l’on exprime le débit moyen utile en trames/s en prenant en

compte l’existence de l’entête

αl
D=
l+h
Utilisant C la vitesse de la liaison, on obtient
l+h
t=
C
Le débit utile normalisé δ (compris entre 0 et 1) de la liaison est
donc

αl D(l + h) l 1−p
δ= = =( )[ ]
C C l + h 1 + (w − 1)p
140 Performances de protocole en présence d’erreurs de transmission

δ est maximum pour une certaine longueur de trame.

Pour les liaisons terrestres ayant q de l’ordre de 10−5 , une entête

de 48 bits, et une vitesse C de 48 kbit/s, on trouve une longueur
de l’ordre de 1000 bits qui maximise δ à 0.9 environ. C’est la raison
pour laquelle on trouve souvent une longueur de trame de 128 octets
sur les liaisons terrestres.

6.5 Calcul du délai

Nous allons calculer le délai de transit S subi par une trame jusqu’à
ce qu’elle soit bien reçue, à l’exclusion du temps de propagation sur
la liaison. Ce délai S se décompose en deux parties, une correspond
à l’attente dans la file associée à la liaison, et une à la transmission
proprement dite incluant les répétitions éventuelles, i.e. Tv .

Dans une approche simplifiée, nous supposons que la file est de

type M/GI/1, où l’approximation consiste à supposer que le trafic
arrivant sur la liaison est Poissonnien de moyenne λ, la loi de service
est de type GI suivant la distribution de Tv .

Utilisant la formule de Pollacek-Khinchin, la distribution du

temps de transit dans le système est

s(1 − ρ)
S ∗ (s) = Tv∗ (s)
s − λ + λTv∗ (s)
(1 − p)T ∗ (s)s(1 − ρ)
=
s(1 − p(T ∗ (s))w ) − λ(1 − T ∗ (s)) − λpT ∗ (s)(1 − (T ∗ (s))w−1 )
(1 − p)T ∗ (s)s(1 − ρ)
=
(s − λ)(1 − p(T ∗ (s))w ) + λ(1 − p)T ∗ (s)
avec ρ = λE[Tv ].
De l’expression de la distribution on peut obtenir le délai moyen

d ∗
E[S] = − S (s) |s=0
ds
λE[Tv2 ]
= E[Tv ] +
2(1 − λE[Tv ])
6.5 Calcul du délai 141

Nous avons calculé E[Tv ], il reste à déterminer E[Tv2 ] qui sera

calculé à partir de la transformée de Laplace de la distribution de
Tv

d2 ∗
E Tv2 =

T (s) |s=0
ds2 v
wp 2 wp w 2 (p + p2 )
= E T2 + (E[T ])2 + (E[T ])2

E T + 2
1−p 1−p (1 − p)

Numériquement, on trouve que pour une de longueur constante

de trame de 128 octets (≈ 103 bits) et un taux d’erreur de 10−8 , par
élément binaire, ce qui correspond à un taux d’erreur par trame
d’environ p ≤ 10−5 , une vitesse de liaison de 64000 bit/s, un temps
de propagation de 250 ms (liaison satellite) le délai de transit moyen
E[S] = 23 millisecondes augmente moins que 0.1 millisecondes, ce
qui correspond à une augmentation du temps de transit < 0.5% en
valeur relative.
142 Performances de protocole en présence d’erreurs de transmission
Chapter 7

Les principes du routage dans

les réseaux

7.1 Le routage dans le contexte de gestion du

réseau
La gestion opérationnelle d’un grand réseau de télécommunication
requiert la mise en œuvre d’un système d’information qui représente
d’une manière synthétique l’état des composants de ce réseau

• les composants physiques comme les liaisons, les mutiplexeurs,

les routeurs, et plus généralement de tous les équipements qui
composent le réseau

• les composants logiques comme les différentes entités protoco-

laires dans les trois plans : usager, contrôle et gestion assurant
le bon fonctionnement de l’ensemble du réseau,

• les bases de données du réseau pour la gestion des états des

composants, la gestion des utilisateurs (profil, facturation . . . ),
les tables de routage, . . .

Le routage est une des fonctions importantes du réseau. Elle

est activée lors du traitement d’appel pour le choix d’une route à
l’ouverture d’une communication (quand le service de communica-
tion offert est de type orienté connexion). Elle est de toute manière
144 Les principes du routage dans les réseaux

indispensable pour l’acheminement de l’information au cours de la

communication.
Les tables de routage sont mises à jour dynamiquement en fonc-
tion de l’état du réseau de la dynamique de la demande des util-
isateurs. Cette mise à jour est sous la responsabilité de la ges-
tion du réseau (plan gestion). Une mise à jour fréquente des
tables de routage permet au traitement d’appel et à la fonction
d’acheminement de l’information de suivre de près l’état du réseau
en utilisant au mieux les ressources du réseau. Mais une mise à jour
fréquente nécessite beaucoup de traitement dans les nœuds ainsi
qu’un volume de trafic de gestion échangé qui peut devenir vite
assez important. De plus, une modification fréquente des routes
peut induire une certaine instabilité du routage ainsi que des in-
cohérences transitoires dans les tables pouvant provoquer une cir-
culation en “boucle” des paquets.
Une bon routage est obtenu à travers un compromis entre

• une mise à jour fréquente des tables des routes permettant

une bonne utilisation des ressources du réseau

• un trafic de gestion échangé entre les nœuds qui doit rester

raisonnable afin de limiter la consommation de la bande pas-
sante par les protocoles de gestion et maintenir une certaine
stabilité dans le temps du routage

7.2 Les hypothèses statistiques simplifiées

Le routage est une fonction complexe présente à la fois dans les
réseaux à commutation de paquets et à commutation de circuits.
Elle est nécessaire à partir du moment où deux ou plusieurs util-
isateurs ne sont pas directement connectés par une liaison directe.
Comme nous avons vu dans les chapitres précédents du cours,
le modèle de trafic de source peut être assez complexe. Dans une
première approximation, nous allons considérer le cas Markovien
qui va nous permettre d’obtenir des résultats analytiques exacts.
Ainsi nous supposons satisfaites les hypthèses statistiques suivantes

• le processus d’arrivée dans le réseau

7.2 Les hypothèses statistiques simplifiées 145

– les appels dans le cas d’un réseau à commutation de cir-

cuit,
– les paquets d’information appartenant à un même circuit
virtuel,
– les datagrammes

suivent une loi de Poisson

• le processus de service

– la durée d’un appel téléphonique

– le temps de transmission d’un paquet ou datagramme sur
le canal

suit une loi exponentiellement distribuée

• dans le cas d’un réseau à commutation par paquet, la capacité

de mémoire des nœuds du réseau est illimitée, ce qui revient
à négliger le phénomène de perte des unités de données par
congestion

Ainsi, les modèles de performance (files d’attente) du routage

des réseaux à commutation de paquets sont basés sur les réseaux
de Jackson (ou BCMP). Dans ces réseaux, le problème de base,
en absence du phénomène de congestion, est de choisir une route
qui minimise le délai. La présence de la congestion implique des
pertes de paquets. Dans ce chapitre, nous supposerons qu’il n’y a
pas de congestion dans le réseau. Les mécanismes de préventions
de la congestion seront étudiés dans les chapitres suivants.
Cette approche markovienne donne une solution plutôt “pes-
simiste” du problème d’attente dans le réseau à commutation par
paquet.
En effet, considérons d’abord le délai d’émission de la trame
sur le liaison comme une première composante du temps de tran-
sit d’un paquet dans le réseau. Comme généralement la longueur
des paquets est constante ou variant peu, utilisant la formule de
Pollaczek-Khinchin
146 Les principes du routage dans les réseaux

ρE[X] (1 + Cb2 )
E[S] = E[X] +
2(1 − ρ)
où intervient le coefficient de variation de la loi du temps d’émission
d’une trame

2
σX
Cb2 =
(E[X])2
Ce coefficient de variation de la loi de service est souvent nul
(service constant) ou petit devant 1. En effet, les unités de données
arrivent souvent découpées par la couche transport ou la couche
réseau. La longueur que prendra une trame au niveau 2 est donc
constante ou quasi-constante d’où une valeur de Cb petite devant 1.
En supposant que le temps de service exponentiellement distribué
fixe Cb = 1 et aura donc comme conséquence de majorer le délai
moyen au niveau de la couche 2.
Cette même argumentation est aussi valable en considérant le
délai au niveau de la couche 3. En effet, que le service offert soit ori-
enté connexion ou encore sans connexion, le délai subit par un pa-
quet dans cette couche est dû à la consultation des tables de routage
pour l’identification de la liaison sortant en fonction de l’adresse
de la destination (et éventuellement de l’adresse de l’origine) codée
(s) dans l’entête du paquet (numéro de circuit virtuel, adresses IP-
origine/IP-destination). Une bonne implémentation de la fontion
de niveau 3 doit induire une très faible variance du temps de traite-
ment au niveau de la couche. En d’autres termes, le coefficient de
variation de la loi de service au niveau 3 doit aussi être assez petit,
idéalement nul.
Comme le temps de transit dans un nœud se compose d’un délai
de traitement pour la couche 2 et d’un délai similaire pour la couche
3, les hypothèses markoviennes sur le caractère exponentiel des
temps de service aux niveaux 2 et 3 induiront une sur-estimation
du délai de transit dans le réseau.
Le problème du routage dans un réseau à commutation de cir-
cuit est différent car le choix de la route est fait avec comme objectif
de minimiser la probabilité de blocage du réseau. Les hypothèses
statistiques ci-dessus font que le modèle obtenu est markovien
7.3 Retour sur quelques principes de routage dans un réseau à
commutation de circuit 147

présentant une solution à forme produit mathématiquement simi-

laire au cas du réseau paquet.

7.3 Retour sur quelques principes de routage

dans un réseau à commutation de circuit
Dans le réseau téléphonique analogique, chaque fois qu’une route
passe par un commutateur de transit, le signal vocal subit une
atténuation de -3 dB. De plus cette atténuation va être cumulée
avec celle induite par la traversée de coupleur 2 fils/4 fils.
C’est l’une des raisons derrière la règle du choix de la route
la plus courte, si possible directe, entre les commutateurs orig-
ine OLEX et destination TLEX. Une autre raison importante est
de nature économique, à savoir que quand une communication en
mode commutation de circuit occupe une route de longueur 3 par
exemple, elle va bloquer 3 ressources dédiées (des intervalles de
temps sur les faisceaux, de la mémoire dans les commutateurs)
pendant la durée de la communication. Contrairement avec ce qui
se passe lors d’une communication en mode commutation de pa-
quets où les ressources allouées à la communication sont partagées
dynamiquement avec les autres communications qui empruntent le
même chemin grâce au multiplexage statistique (voir le chapitre
correspondant) et donc potentiellement utilisables par toutes ces
communications.
Ainsi, la conception de la topologie du réseau à commutation de
circuit a été guidée par le principe de favoriser la présence des liens
directs entre tout couple de commutateurs chaque fois que le trafic
échangé en erlang était “suffisant”. Ainsi, les topologies obtenues
sont assez maillées afin de trouver “assez souvent” une route di-
recte dans les conditions nominales de fonctionnement entre les
sites qui échangent “suffisamment de trafic”.
Le problème du routage dans les réseaux à commutation de cir-
cuit peut avoir la formulation simplifiée suivante : la route choisie
est celle de longueur minimale, en termes de nombre de commuta-
teurs de transit et de liaisons traversées, qui minimize la probabilité
de blocage d’appels du réseau d’infrastructure. Comme l’allocation
148 Les principes du routage dans les réseaux

de la bande passante est statique et de durée assez longue (durée

d’un appel téléphonique) par rapport au temps d’émission d’un
paquet sur une liaison de données, la route qui sera choisie sera
celle qui a la longueur la plus courte parmi les routes admissibles
minimisant la probabilité de blocage du réseau.
Deux classes d’algorithmes de routages ont été implémentées.
La première est basée sur un routage hiérarchique fixe : c’est
la route directe qui est choisie en premier et seulement quand
le faisceau direct est saturé qu’une route alternée passant par
un seul commutateur de transit sera recherchée. L’appel est re-
jeté si aucune route alternée n’est disponible. La deuxième classe
d’algorithmes est basée sur un choix plus ou moins dynamique
en fonction du trafic qui arrive sur le réseau et sans a priori une
hiérarchie fixe entre les routes.
Nous citons quelques exemples d’algorithmes dynamiques

• Le routage dynamique non hiérarchique, Dynamic Non-Hierarchical

Routing DNHR, utilisé par ATT dès la fin des années 80 dans
son réseau grande distance.

• Le routage dynamique alterné, The Dynamic Alternative Rout-

ing DAR, utilisé par British Telecom sur son réseau interur-
bain. Il est basé sur le concept de Sticky Random Routing
où à chaque couple de commutateurs correspond un couple
de routes, la directe et l’alternée. Quand la route directe
est saturée, l’algorithme choisit la route alternée. Quand la
route alternée devient saturée, l’algorithme choisit une nou-
velle route alternée aléatoirement parmi un certain de routes
fixées d’avance.

• Le Least Loaded Routing LLR, où quand la route directe est

saturée, l’algorithme choisira la route alternée qui possède
la plus grande capacité résiduelle parmi toutes les route de
longueur deux (admissibles).
7.4 Les principaux objectifs du routage dans les réseaux à commutation
de paquets 149

7.4 Les principaux objectifs du routage dans

les réseaux à commutation de paquets
Deux services sont disponibles au niveau 3 dans les réseaux à com-
mutation de paquets

• Service orienté connexion (circuit virtuel)

• Service sans connexion (datagramme)

Dans tous les cas, le routage assure deux fonctions principales

• Le choix de la route qui va relier les utilisateurs qui cherchent

à communiquer entre eux

• Le tranfert de l’information durant la vie de la communication

Dans le cas d’un service orienté connexion, le choix de la route

est généralement fait dynamiquement au moment de l’arrivée d’un
appel entrant pour l’ouverture d’une connexion. La route sera
maintenue jusqu’à la fermeture du circuit virtuel. Dans le cas d’un
service datagramme, il n’y a pas d’ouverture ni de fermeture de
connexion. Les datagrammes sont routés indépendamment les uns
des autres sur la base des adresses (origine, destination) incluses
dans l’entête du paquet.
Le routage et le contrôle de flux visent les même objectifs globaux

• Maximiser le débit utile du réseau

• Tout en satisfaisant les contraintes de qualité de service de l’utilisateur,

essentiellement

– la probabilité de perte des paquets

– le délai de transit dans le réseau et éventuellement ses variations
(la gigue)
– la disponibilité du réseau (d’une route pour atteindre une desti-
nation)
– l’équité entre les utilisateurs
150 Les principes du routage dans les réseaux

• Avec un coût économique le plus faible possible

• Tout en évitant la congestion

Delay feedback

Offered load Throughput Path Choice

Flow Control Routing

Rejected Load

Interaction between the Routing function and the the Flow Control Function

Figure 7.1: Relation entre Routage et Contrôle de Flux

Certains des points précédents sont corrélés. En effet, la théorie

des réseaux de files d’attente montre que, pour un trafic entrant
et une topologie du réseau fixés, les politiques de routage et de
contrôle de flux qui maximisent le débit utile du réseau vont également
minimiser la probabilité de perte des paquets ainsi que le délai de
transit dans le réseau, voir la figure 7.1.
Pour satisfaire la contrainte de disponibilité du réseau, la solu-
tion courante souvent choisie par les concepteurs du réseau consiste
à réaliser un maillage de la topologie de manière que chaque nœud
du réseau soit relié à au moins deux nœuds adjacents. Ce qui per-
met à la fonction du routage de disposer au moins de deux routes
différentes entre n’importe quel couple d’utilisateurs connectés au
réseau.
7.5 Un modèle simplifé du transit dans un réseau à commutation de
paquets 151

7.5 Un modèle simplifé du transit dans un

réseau à commutation de paquets
L’approche markovienne permet l’obtention d’une solution analy-
tique exacte de la distribution de probabilité du temps de transit
dans le réseau et de la longueur des files d’attente dans les nœuds.

Routage Couche 3

Liaison
Couche 2

Couche 1

Reception Emission
Chemin des donnees

Figure 7.2: Modèle simplifié d’un nœud de transit

Le modèle le plus simple généralement adopté est un réseau de

Jackson ouvert où un nœud de transit de la route est modélisée
par deux files d’attente en série, comme le montre la figure 7.2. La
première représente la fonction de routage du paquet (le niveau 3
de la pile protocolaire de l’ISO). La deuxième file d’attente représente
la fonction du protocole de liaison (le niveau 2 de la pile des pro-
tocoles). La politique de service au niveau de chaque file est faite
selon la politique FIFO, et l’on néglige l’intensité du trafic de su-
pervision du réseau, qui est prioritaire non préemptif devant celle
du trafic de données des utilisateurs quand ce trafic emprunte les
mêmes liaisons que le trafic des usagers. Autrement, il arrive sou-
vent que, pour des raisons de sécurité et de performance, le trafic
152 Les principes du routage dans les réseaux

de supervision emprunte une infrastructure dédiée indépendante

de l’infrastructure réservée aux usagers.
Donc dans ce modèle ”on néglige le temps de traitement du
niveau 2 à la réception de la trame. Ce temps est gén’eralement
beaucoup plus faible que les autres temps ci-dessus car il est dû
à des opérations sur les entêtes réalisées par du “matériel” plus
éventuellement l’opération de copie de la trame à partir de la
mémoire du contrôleur de liaison vers la mémoire de la fonction
de routage.
Quand le réseau à commutation de paquets est de type “bande
étroite”, on peut parfois négliger le délai dans la couche 3 par
rapport au délai de la couche 2 et simplifier ainsi le modèle en
supprimant les files d’attente associées au niveau 3.
Mentionnons deux hypothèse sous-jacentes à la modélisation à
l’aide d’un réseau Markovien ouvert à forme produit

• Les liaisons sont indépendantes entre elles, ie ce qui se passe

dans une file est indépendant de ce qui se passe dans l’autre
(service demandé, taux d’arrivée, . . . ).

• Les circuits virtuels sont indépendants entre eux.

La deuxième hypothèse est plutôt naturelle. La première se

justifient moins dans la réalité.
On va noter E[Si ] le temps de transit moyen d’un paquet dans la
couche 3 du nœud i. Ce temps depend directement de l’intensité
des flux de trafic qui arrivent au nœud i et qui sont routés par la
couche 3 de ce nœud.
Soit λij l’intensité totale des flux de paquets qui traverse le lien
(i, j) qui relie les nœuds i et j. Si l est la longueur moyenne de
paquet en octets et Cij la vitesse du lien (i, j), alors le temps de
transit moyen sur la liaison (i, j) est

1
E[Sij ] = + τij
µ − λij
avec

1 8l
=
µ Cij
7.5 Un modèle simplifé du transit dans un réseau à commutation de
paquets 153

et τij le temps de propagation sur la liaison (i, j)

Ainsi, quand un paquet de type datagramme ou appartenant à
un circuit virtuel traverse les nœuds 1,2,. . . ,n, alors le temps de
transit moyen sur la route est
n−1
X
E[S] = [E[Si ] + E[Si,i+1 ] + E[Si+1 ]]
i=1

Exemple numérique
Considérons un flux de données, entre deux ETTDs, reliés par
un réseau X25 tels que (voir figure 7.3)

L1 n2
n1
64 kbit/s

48 kbit/s L2
n4

64 kbit/s
n3

Liaison Lj, j=1,...,3

Couche 3 Couche 2

Noeud i , i=1,..., 4

Figure 7.3: Exemple d’un modèle simplifié de circuit virtuel

• la source est poissonnienne de moyenne α = 10 paquets/s,

• la longueur de paquet est exponentiellement distribuée de

moyenne l = 128 octets,

• la route utilisée par le flux est de longueur trois, traversant 4

nœuds n1 , n2 , n3 , n4 reliés par trois liaisons (L1 , L2 , L3 ), on sup-
posera que les liaisons Li , i = 1, 2, 3, soient terrestres où nous
allons négliger le temps de propagation des paquets,
154 Les principes du routage dans les réseaux

• la vitesse de L1 est de v1 = 64 kbits/s,

• la vitesse de L2 est de v2 = 48 kbits/s,

• la vitesse de L3 est de v3 = 64 kbits/s,

• la capacité de service du routage au niveau 3 des nœuds est ex-

ponentiellement distribué de moyenne µi = µ = 2000 paquets/s
pour les quatre nœuds n1 , n2 , n3 , n4 .

En plus du flux en question traversant les couches 3 et 2, il

y a aussi d’autres flux indépendants qui empruntent ces mêmes
couches et qui se superposent à ce flux

• les flux additionnels dans la couche 3 des 4 nœuds de la route

sont Poisson d’intensités identiques λi = λ = 500 paquets/s,
i = 1, 2, 3, 4,

• le flux additionnel dans L1 est supposé être poissonnien de

moyenne α1 = 15 paquets/s, la longueur des paquets est sup-
posée être distribuée exponentiellement de moyenne l = 128
octets,

• le flux additionnel dans L2 est poissonnien de moyenne α2 = 12

paquets/s de longueur distribuée exponentiellement de moyenne
l = 128 octets,

• le flux additionnel dans L3 est poissonnien de moyenne α3 = 14

paquets/s de longueur distribuée exponentiellement de moyenne
l = 128 octets

Vérifions d’abord la stabilité du réseau.

C’est au moment de l’ouverture du CV qu’on cherche à choisir
une route telle que le réseau reste stable suite à l’admission de cette
nouvelle connexion. On va donc vérifier l’absence de congestion
réseau.

• Pour la liaison L1 nous avons :

(α + α1 ) ∗ l ∗ 8 (10 + 15) ∗ 128 ∗ 8

ρ1 = = = 0.4 < 1
v1 64000
7.5 Un modèle simplifé du transit dans un réseau à commutation de
paquets 155

• Pour la liaison L2 nous avons :

(α + α2 ) ∗ l ∗ 8 (10 + 12) ∗ 128 ∗ 8

ρ2 = = = 0.469 < 1
v2 48000

• Pour la liaison L3 nous avons :

(α + α3 ) ∗ l ∗ 8 (10 + 14) ∗ 128 ∗ 8

ρ3 = = = 0.384 < 1
v3 64000

• Pour la couche 3 dans les quatres nœuds traversés

(α + λi ) (10 + 500)
ρni = = = 0.255 < 1; i = 1, 2, 3, 4
µi 2000

donc il n’y a pas de congestion car toutes les files d’attente qui
composent la route sont chargées en dessous de 1. Le réseau admet
un régime permanent.
Calculons le nombre moyen de paquets sur chaque liaison, en
attente ou en cours de transmission.

• Pour la liaison L1 nous avons :

ρ1
E[NL1 ] = = 0.666 paquets
1 − ρ1

• Pour la liaison L2 nous avons :

ρ2
E[NL2 ] = = 0.914 paquets
1 − ρ2

• Pour la liaison L3 nous avons :

ρ3
E[NL3 ] = = 0.623 paquets
1 − ρ3

Le nombre de paquets au niveau de la couche 3 dans les nœuds

n1 , n2 , n3 , n4 est

ρni 0.255
E[Nni ] = = = 0.34 paquets
1 − ρni 1 − 0.255
156 Les principes du routage dans les réseaux

Le fait que le nombre moyen de paquets sur la liaison soit, en

moyenne, inférieur à 1 veut dire, qu’en moyenne, un paquet entrant
trouve disponible le serveur de transmission.
Pour calculer la valeur de la fenêtre d’anticipation qui laisserait
l’émet-teur travailler en moyenne en continu , il est nécessaire de
déterminer le délai moyen de transit dans le réseau. Utilisant le
théorème de Little

• le temps de séjour moyen dans le premier contrôleur de liaison

est E[SL1 ] = 0.666/25 = 0.026 s.

• le temps de séjour moyen dans le deuxième contrôleur de li-

aison est E[SL2 ] = 0.914/22 = 0.041 s.

• le temps de séjour moyen dans le troisième contrôleur de liai-

son est E[SL3 ] = 0.623/24 = 0.025 s.

• le temps de séjour moyen dans chaque file de routage des

quatre nœuds de transit est E[Sni ] = 0.34/510 = 0.67 ∗ 10−3 s.

D’où le délai moyen de transit dans le réseau E[T ] = 0.094 s. Le

choix de la route à l’ouverture de la connexion doit minimiser ce
temps de transit.

7.5.1 Formulation simplifiée du problème du routage

dans un réseau à commutation de paquets
Par la suite du chapitre, nous allons nous contenter d’une formu-
lation simplfiée du problème du choix de la route pour un paquet
entrant dans le réseau : la route choisie est celle qui minimise une
fonction de coût généralisée positive d.. . Cette fonction dépend du

• délai moyen de transit dans le réseau. Ce délai moyen de

transit est le cumul des délais moyens rencontrés par le pa-
quet dans les différentes files d’attentes des commutateurs et
contrôleurs de communication des différents nœuds traversés
composant la route, ainsi que les délais de propagations sur
les liaisons (attention au délai de propagation induit par une
liaison satellite ou grande distance terrestre . . . ).
7.5 Un modèle simplifé du transit dans un réseau à commutation de
paquets 157

• coût d’utilisation des différentes ressources qui composent la

route

Le coût d’utilisation des ressources peut, en particulier, être

le même pour les différents éléments de la route. Dans ce cas
particulier, ce coût est pris, par convention, comme égal à l’unité
ce qui, en d’autres termes, se traduit par un choix de route de
longueur topologique minimum.
Il est souvent possible de supposer dans le cas des réseaux
grande distance à bande étroite que le délai dû à la transmission sur
une liaison est beaucoup plus grand que celui dû à la commutation
dans le nœud.
Comme le trafic de données est fondamentalement sporadique,
le délai de transit moyen le long d’une route est variable dans le
temps suivant la variation de la charge des différents éléments du
chemin.
la fonction de contrôle, en charge du choix de la route et généralement
localisée dans le centre de contrôle du réseau (Network Control
Center NCC), doit suivre l’évolution de la charge de chaque élément
du réseau afin de choisir à tout moment et dynamiquement la
meilleure route à utiliser par les paquets qui circulent dans le
réseau.

7.5.2 Les principaux algorithmes de calcul de plus court

chemin
Soit dij le coût généralisé entre les nœuds i et j. Nous notons que le
nœud destination 1. Nous allons calculer l’ensemble des plus court
chemins entre tous les nœuds du réseau et le nœud destination 1.

Algorithme de Bellman-Ford

On note Dih comme le coût généralisé du plus court chemin entre

le nœud i et le nœud destination 1 de longueur topologique au plus
égale à h.
En posant D1h = 0 pour tout h, alors Dih peut être calculé avec
l’itération
158 Les principes du routage dans les réseaux

Dih+1 = Minj [dij + Djh ]

pour tout i 6= 1.

Algorithme de Dijsktra
L’algorithme de Dijsktra suppose que la fonction de coût généralisée
est non négative. Dans la kième itération, si l’on note P l’ensemble
des kième nœuds les plus proches de 1. Parmi tous les chemins
reliant un nœud j qui n’est pas dans P au nœud 1, il en existe au
moins un plus chemin passant par P ( car dij ≥ 0). D’où l’agorithme
• Initialisation : P = {1}, D1 = 0, et Dj = dj1
• Etape 1 Trouver i qui n’est pas dans P et qui est le plus proche
de 1 (Di minimum).
S
Soit P ← P {i}.
Test d’arrêt : si P contient tous les nœud du réseau, alors
arrêt de l’algorithme.
• Etape 2 : mise à jour : pour tous les j qui ne sont pas dans P
calculer
Dj ← Mini∈P [Dj , dji + Di ]
Revenir à l’Etape 1.

Algorithme de Floyd-Warshall
Cette algorithme trouve les plus courts chemins entre tous couple
de nœud du réseau.
Notons Dijn le coût du plus court chemin entre les nœuds i et
j avec la contrainte que seuls les nœuds 1, · · · , n peuvent être em-
pruntés comme nœuds intermédiaires.
• Initialisation : Dij0 = dij pour tout i et j, avec i 6= j
• Pour n = 0, 1, · · · , N − 1,

Dijn+1 = Min[Dijn , Di,n+1

n n
+ Dn+1,j ]
pour tous i 6= j, N étant le nombre de nœuds du réseau
7.5 Un modèle simplifé du transit dans un réseau à commutation de
paquets 159

7.5.3 Le cas particulier du routage orienté circuit virtuel

Considérons, en particulier, le cas d’un réseau offrant un service de
couche 3 de type “circuit virtuel”. Désignons par {F1 , F2 , · · · , Fn }
un ensemble de flux de trafic correspondant à n appel entrant qui
arrive au centre de contrôle du réseau (NCC).
Supposons pour simplifier les notations que {F1 , F2 , · · · , Fn } soient
ordonnés par intensité décroissante. L’intensité des différents flux
est généralement prédite ou définie à partir d’un contrat de trafic
entre le fournisseur de service (Service Provider) et le client (Ser-
vice Subscriber).
La démarche consiste à trouver les meilleures routes en prenant
séquentiel-lement les flux Fi par ordre décroissant d’intensité i =
1, · · · , n. Le choix de la route est fait une fois pour toute à l’ouverture
de la connexion. La route choisie doit être admissible dans le sens
que la fonction de coût de la route doit être inférieure à une borne
supérieure (généralement déduite à partir du contrat de trafic).
L’algorithme du choix de la route peut être l’un des algorithmes
présentés ci-dessus.
Si aucune route n’est admissible, alors l’appel est rejeté.
Autrement, la route choisie sera marquée à l’ouverture et des
ressources , en terme de mémoire, seront réservées dans chaque
nœud pour le flux en question. Ces ressources seront libérés lors
de la fermeture du circuit virtuel.

Le cas du réseau TRANSPAC

On note

• L le lien reliant les nœuds a et b

• Ca (L) = le coût de L vu par le nœud a

• Cb (L) = le coût de L vu par le nœud b

• C(L) = Sup{Ca (L), Cb (L)}

Ca (L) et Cb (L) sont calculés par les nœuds a et b, ces coûts de-
pendent de
• la vitesse de L
160 Les principes du routage dans les réseaux

Ca (L)
6 6

Fonction de coût (L’échelle dépend de la vitesse L)

-
6

? -
6

? -
Charge
-
Ma (L)

Figure 7.4: Fonction de coût

• l’occupation de la mémoire des nœuds

La figure 7.4 donne l’allure générale d’une telle fonction de coût.

On pose
–
• mia (L) = le nombre maximum de buffers qui peuvent être
alloués dans le nœud a au circuit virtuel V Ci qui utilise la
liaison L
P
• Ma (L) = i [mia (L)] = la taille maximum de la mémoire qui
puisse être allouée à tous les V Cs passant par le nœud a et la
liaison L

Le NCC va calculer C(L) utilisant Ca (L) et Cb (L) envoyés par les

nœud a et b, C(L) est renvoyé par le NMC aux nœud a et b.
7.5 Un modèle simplifé du transit dans un réseau à commutation de
paquets 161

N2
J
]
J
J
J
J
J
L1 J
C(2, 5)
S
S
N3 S
@
I S
@ S
DT E1 @ S DT E2
C(3, 5) w
S
L2 @
@
N1 @ N5
R
@

*

L3 N4 C(4, 5)

Le réseau de transport

Figure 7.5: Exemple de choix de route

– Les nœuds a et b envoient de nouvelles valeurs de Ca (L) et Cb (L)

chaque fois que ces valeurs changent en fonction de la variation de
la charge des éléments du réseau.
La grandeur C(k, n) désigne le coût du plus court chemin entre
les nœuds k et n.
Dans l’exemple suivant, voir 7.5 nous allons supposer que

• le terminal DT E1 est connecté au nœud DCE1 = N1 du réseau

TRANSPAC,

• N1 est relié directement aux nœuds N2 , N3 et N4 par les liaisons

L1 , L2 et L3 ,

• le coût de plus court chemin entre N2 , N3 , N4 et N5 = DCE2 ,

auquel est directement relié DT E2 , est donné respectivement
162 Les principes du routage dans les réseaux

par C(2, 5), C(3, 5), C(4, 5).

N1 (le DCE1 ) va choisir le lien Li qui vérifie la condition suivante

Inf {C(L1 ) + C(2, 5), C(L2 ) + C(3, 5), C(L3) + C(4, 5)}
N1 va envoyer (si c’est nécessaire) la nouvelle valeur C1 (Li ) au
NCC où les nouvelles valeurs C(Li ) et C(k, n) vont être recalculées
et renvoyées aux nœuds directement reliés à Li .
Ainsi, le nœud 1 doit avoir une table par nœud de transit adja-
cent

• C(2, n)

• C(3, n)

• C(4, n)

où sont mémorisés les coût des plus courts chemins entre ces
nœuds adjacents et tous les nœuds de sortie DCEi = n du réseau
TRANSPAC.
L’existence de l’hystérésis et le choix d’un petit nombre de
niveau de quantification de la fonction de coût Ca (L) a pour ob-
jectif de limiter le trafic de gestion échangé entre les nœuds a et le
NCC, voir la figure 7.4.
Chapter 8

Les principes du contrôle de

flux

8.1 Introduction

Il arrive souvent dans les réseaux que le trafic instantané entrant

soit supérieur à la capacité de traitement disponible. Ce phénomène
est une conséquence de la nature aléatoire du trafic. Il est parti-
culièrement visible dans les réseaux de transmission de données à
commutation de paquets, où les données arrivent à des instants
aléatoires. Il en est de même dans les réseaux à commutation de
circuit où le nombre instantané d’appels entrants varie en fonction
du temps. Traditionnellement, le contrôle de flux a été développé
pour les réseaux de données. Les réseaux à commutation de circuit
sont de type “à perte” : l’appel qui arrive dans un réseau où il y
a suffisamment de ressources disponibles est accepté, autrement,
l’appel sera rejeté. Les ressources allouées à un appel qui a été
admis seront exclusivement réservées à l’appel pendant la durée
de la communication. Dans un réseau à commutation par paquet
offrant un service orienté connexion, bien que le réseau réserve des
ressources au moment de l’admission de l’appel, il y a toujour un
risque de dépassement de capacité (congestion) à cause de la na-
ture variable du trafic (sporadicité) et du multiplexage statistique
de ces flux.
164 Les principes du contrôle de flux

8.2 La congestion
Lorsque le trafic entrant dans un réseau augmente, nous consta-
tons généralement qu’au-delà d’une charge limite, les performances
du réseau s’écroulent: le débit utile diminue et le temps moyen
de transit dans le réseau augmente. On est en présence d’un
phénomène de congestion du réseau : le débit utile du réseau
diminue quand le trafic entrant augmente. Ce phénomène est en
rapport avec la saturation des ressources qui ne peut être évitée
qu’en diminuant le débit des sources.
La congestion apparaı̂t donc comme un phénomène ”boule de
neige”. Le réseau doit disposer de mécanisme de prévention, en vue
de résorber les surcharges temporaires. La fonction du contrôle
de flux est de réguler le trafic entrant, à savoir le ralentir dès
l’apparition de la surcharge puis permettre l’écoulement total dès
le retour au fonctionnement normal.

8.3 Les principaux objectifs du contrôle de

flux
Le contrôle de flux est nécessaire chaque fois qu’il y a une contrainte
sur le débit du trafic entre deux sources qui communiquent. Cette
contrainte peut être due à la limitation de la capacité du canal, du
matériel de communication ou encore des ETTD (mémoires dans
les interfaces, capacité de traitement...). De ce fait, le contrôle de
flux est nécessaire dans les trois cas suivants

• Entre l’ETTD et l’ETCD d’entrée du réseau,

• Entre deux noeuds du réseau,

• Entre les deux ETTDs qui communiquent à travers le réseau.

La prévention de la congestion est un compromis entre les trois

objectifs suivants

1. Trouver un bon compromis entre la capacité de traitement des

utilisateurs (nombre de mémoires tampon disponibles, temps
de calcul) et le délai moyen de transit du message.
8.3 Les principaux objectifs du contrôle de flux 165

2. Assurer la meilleure utilisation des ressources disponibles tout

en maintenant une certaine équité entre les utilisateurs.

3. Prévenir la dégradation du débit du réseau due à la saturation

de la mémoire dans les noeuds de commutation, en assurant
la meilleure répartition de charge possible entre les noeuds.
Cet objectif sera atteint si le premier l’est. En effet, le délai
moyen de transit dépend de la longueur des files d’attente.
En minimisant ce délai, on diminue le risque de saturation de
la mémoire.

Il s’agit donc d’un problème d’optimisation multicritère. Il

n’existe pas, généralement, de solution optimale à ces problèmes.
De plus on verra tout le long du chapitre que certains de ces ob-
jectifs sont même contradictoires les uns par rapport aux autres.

8.3.1 Discussion autour du premier objectif : Compro-

mis capacité-délai
Minimiser le délai de transit va dans le sens de soulager le réseau,
donc de minimiser le délai de communication de tous les utilisateurs
simultanés de ce réseau. Cela ne diminue pas pour autant la charge
des ETTDs. En d’autres termes, la minimisation du temps de
transit n’implique pas nécessairement celle du temps de réponse,
puisque celui-ci dépend aussi des ETTD terminaux. Ceci étant,
en minimisant le délai dans le réseau, on diminue la probabilité
de retransmission, due à une congestion locale ou à un délai de
retour d’acquittement trop long, dont la conséquence est une baisse
partielle du débit utile du réseau.
Ainsi, le schéma de contrôle de flux sera associé à un fonction-
nement par palier

• En dessous d’une certaine charge critique du réseau corre-

spondante à un seuil de longueur de files d’attente dans les
noeuds, le mécanisme de contrôle de flux ne doit pas agir sur
la source de trafic et doit donc être mis hors service.
166 Les principes du contrôle de flux

• Au dessus de ce seuil critique, le mécanisme de contrôle de

flux doit entrer en action en régulant le flux de trafic entrant
pour garder le délai de transit en dessous d’un certain seuil.

8.3.2 Discussion autour du deuxième objectif : Com-

promis allocation des ressources-équité entre les
utilisateurs
Il peut arriver que la maximisation du débit utile du réseau soit in-
compatible avec l’objectif d’équité entre les utilisateurs. La Figure
8.1 en donne un exemple.

6
'$ '$ '$ '$ '$
? - - - ... - -
1 ... N −1 2N 3
6&%6&%6&%6&%6&%
- - - ... - -

? ? ? ? ?

Figure 8.1: Un problème d’équité

En effet, il s’agit d’un réseau de N+1 noeuds dont les liaisons

inter-noeuds sont de capacité de 1 unité/seconde de trafic, et qui
est traversé par N + 1 flux de 1 unité/seconde de trafic en moyenne,
les N premiers empruntent chacun une route de longueur 1, le
N + 1 -ième une route de longueur N. Un tel réseau est instable en
absence d’un mécanisme de contrôle de flux.
Soit x la part de la capacité de la route allouée au flux le plus
long. Donc le débit utile du réseau est

N(1 − x) + x = N

Un contrôle de flux qui maximise le débit du réseau, imposera

x = 0 donc bloquera le flux (long) qui emprunte la route de longueur
N ce qui permettra aux N flux (court) qui restent de passer et au
réseau de passer un débit utile total de N unités/seconde de trafic.
Cette stratégie n’est pas équitable car elle favorise les flux qui
empruntent les chemins les plus courts.
8.3 Les principaux objectifs du contrôle de flux 167

Un contrôle de flux parfaitement équitable donnera le même

débit à chacun des N + 1 flux. Soit x = 0.5 unités/seconde de
trafic. Ce qui permet à tous les flux de traverser le réseau sans
créer de congestion. Le débit utile du réseau sera égal à N + 1/2
unités/seconde de trafic.
Un compromis consisterait donc de choisir x entre 0.5 correspon-
dant à un politique parfaitement équitable et x = 0 correspondant
à une politique qui maximise le débit utile du réseau.

8.3.3 Discussion autour du troisième objectif: Prévention

contre la saturation de la mémoire
On a vu, lors de l’explication du phénomène de congestion, que
la saturation de la mémoire a pour conséquence une dégradation
du débit utile du réseau. De plus, cette diminution ne touche pas
tous les flux de trafic d’une manière homogène et peut diminuer
l’équité. L’exemple suivant nous montre comment cela se traduit
dans un cas précis.
La Figure 8.2 présente un réseau à cinq noeuds A, B, C, D et
E. Le noeud E, qui est un noeud de transit, effectue le relai pour
les flux de trafic entre A et B d’un coté, et C et D de l’autre. La
mémoire du noeud de transit E est supposée être de capacité finie,
telle que la capacité de commutation de ce noeud en transit soit
de 200 paquets/s au maximum. On suppose que le flux entre A
et B suit un processus de Poisson d’intensité 100 paquets/s et que
celui entre C et D suit aussi un processus de Poisson d’intensité η
paquets/s. Ces flux sont supposés être indépendants. On suppose
de plus que la liaison reliant A à E est de capacité 10 fois supérieure
à celle reliant C à E.
Tant que la mémoire de E n’est pas saturée, le flux qui traverse
le noeud de transit E, suit une loi de Poisson d’intensité η + 100
paquets/s de trafic.
Quand le trafic entre A et B croit et reste longtemps autour
d’une grande valeur (ie au voisinage de η = 100 ), le phénomène
de saturation de la mémoire de E apparaı̂t, et se traduit par des
répétitions d’émission de paquets venant des noeuds A et C.
Comme la vitesse de la liaison AE est 10 fois supérieures à celle
168 Les principes du contrôle de flux

de CE, un paquet venant de A aura 10 fois plus de chance de

trouver une mémoire disponible qu’un paquet venant de C. Donc
en cas de congestion de E, le débit utile du réseau va diminuer
pour tendre vers 110 paquets/s de trafic, au lieu de 200 en absence
de congestion. De plus, le noeud C va être beaucoup plus pénalisé
que le noeud A. Ce phénomène est représenté par la Figure 8.3.
La saturation de la mémoire dans les noeuds peut aussi engen-
drer un phénomè-ne d’interblocage. La Figure 8.4 illustre cette
situation.
Chacun des noeuds A et B ne peut pas recevoir de paquets de
l’autre noeud parce que toute la mémoire disponible du noeud est
occupée par les paquets en attente de transmission vers le noeud
suivant. Cette situation peut se présenter dans le cas de plusieurs
noeuds en cycle A1 A2 ... An de longueur n où chaque noeud attend
la disponibilité de la mémoire du noeud suivant. Pour résoudre ce
problème, la méthode utilisée consiste à affecter dans un noeud à un
paquet entrant une priorité qui dépend du nombre de noeuds déjà

C
&%

capacité c

'$ '$ '$

capacité 10c 100 paquets/s
A - B
&% &% &%
E

η paquets/s

'$
?

D
&%

Figure 8.2: Un réseau inéquitable

8.3 Les principaux objectifs du contrôle de flux 169

traversés, d’où une meilleure utilisation des ressources du réseau.

Généralement ce schéma de fonctionnement est complété, dans les
réseaux à routage adaptatif, par un mécanisme de purge des pa-
quets qui ont traversé trop de noeuds de transit. Car dans ce cas
on considère qu’il s’agit de paquets ayant bouclé dans le réseau, un
phénomène susceptible d’apparaı̂tre dans des réseaux munis de ce
type de routage.
Regardons maintenant comment dimensionner la mémoire en
fonction de l’intensité du trafic entrant.
Posons

• p = probabilité de perte d’une unité de données. Cette prob-

abilité est un paramètre de qualité de service,

• k = la taille de la mémoire en terme de nombre maximum de

places (1 place = 1 unité de données) pouvant être allouées
aux différentes communications traversant le système,

• N = nombre d’unités de données présentes dans le système

en régime stationnaire.

débit utile en paquets/s

200

110
100

η
-

100 paquets/s
Figure 8.3: Conséquences de la saturation

Figure 3
170 Les principes du contrôle de flux

Nous considérons que la congestion débute quand N dépasse k.

Pour mener le calcul nous allons supposer que le système d’attente
est Markovien ce qui est une approximation pessimiste de la réalité
(voir le chapitre 1).
Donc
∞
X
p = P{N > k} = ρi (1 − ρ) = ρk+1
i≥k+1

d’où

logp
k+1=
logρ
Numériquement, pour p = 10−10 et ρ = 0.90 on obtient une valeur

Situation d’interblocage entre A, B,'$

C et D

I
@
B
&%
@
@
@ @
@ @
@ @
@ @
@ @
@ @
@ @
@ @
@
'$ '$
@
@ @
@
@R
@
A
I
@
C
&% &%
@
@
@ @
@ @
@ @
@ @
@ @
@ @
@ @
@ @
@
'$
@
@ @
@
@R
@ D
&%

Figure 8.4: Interblocage

8.4 Les méthodes de contrôle de flux dans les réseaux à commutation
par paquet 171

de k +1 = 219 places. La taille de la mémoire k +1 passe à 450 places

quand le facteur de charge ρ passe à 0.95.
Il est donc possible de bien dimensionner la mémoire avec un
objectif de taux de perte par congestion qui soit borné. Le corol-
laire des grandes tailles de mémoire qui permettent un très faible
taux de perte est d’induire des grandes variations de délais de
transit. En effet, dans l’exemple précédent (avec un ρ = 0.95 et
un p = 10−10 ) le temps de transit varie entre l’unité (0.016 secon-
des pour une trame de 128 octets sur une liaison à 64 000 bit/s)
et 450 unités (450*0.016 = 7.2 secondes). Cette grande variation
du temps de transit peut ne pas être acceptable pour un trafic de
donnée ayant des contraintes fortes de type temps réel.
Il n’est pas possible de gagner sur le délai et sur le taux de perte sans payer
le prix d’une augmentation de la capacité de traitement afin de diminuer ρ.
En guise de conclusion notons que la prévention contre la satu-
ration de la mémoire est un problème assez complexe qui n’a pas
de solution générale. Ce phénomène de saturation est toutefois
relativement moins critique dans les réseaux actuels compte tenu
de la baisse du coût du matériel. Il ne faut toutefois pas négliger
l’impact des grandes mémoires sur le temps de transit.

8.4 Les méthodes de contrôle de flux dans les

réseaux à commutation par paquet
Nous allons présenter les principales méthodes utilisées pour prévenir
la congestion. Nous commençons par présenter une méthode glob-
ale (dite aussi isarithmique) qui vise à réguler le nombre total de
paquets qui circulent dans le réseau. Nous insisterons après sur
les méthodes basées sur le mécanisme de la fenêtre, ces méthodes
étant très utilisées dans les réseaux existants. Nous finirons par
parler brièvement du contrôle de flux dans les ETTD.

8.4.1 La méthode globale

La méthode globale, dite ”Isarithmic Method” en anglais, vise le
contrôle du nombre total de paquets présents dans le réseau à un
172 Les principes du contrôle de flux

instant donné. Pour qu’un paquet puisse entrer dans le réseau, il

faut qu’il dispose d’un permis d’entrée. Les permis sont gérés de
façon centralisée si le réseau possède un centre de gestion, ou bien
distribuée dans le cas contraire. Le paquet traverse le réseau en
gardant son permis, puis le rend à la sortie.
Les principaux problèmes à résoudre dans le cadre de la méthode
sont

• la gestion des permis d’accès

• la manière de les faire circuler dans le réseau sans génération

excessive de trafic de supervision

• la reprise sur erreur comme la perte de permis.

Le principal avantage de cette méthode est son caractère dy-

namique. En effet, dans les méthodes suivantes, basées sur le
mécanisme de la fenêtre, la régulation opère sur les flux de trafic
individuels. Même si le réseau est très peu chargé, le mécanisme
de contrôle de flux n’acceptera pas à un moment donné plus qu’un
nombre maximum de paquets venant d’un flux donné. Cette con-
trainte ne se présente pas dans la méthode globale. A la limite,
quand la charge du réseau est faible, un flux de trafic ne sera limité
que par les ETTD extrémités. Cette flexibilité doit néanmoins être
associée à une politique d’allocation de ressources (ie les permis)
entre les différents usagers du réseau afin d’assurer une certaine
équité entre ces utilisateurs en répartissant la “pénurie” quand la
charge du réseau augmente. Enfin, la méthodes s’adapte bien aux
réseaux offrant un service sans connexion.

8.4.2 Les méthodes basées sur le mécanisme de la fenêtre

Il s’agit des méthodes de contrôle de flux les plus répandues.
On dit que la communication, entre deux noeuds A et B, ad-
jacents ou non, est réglée par un contrôle de flux par fenêtre de
taille w si chacun des noeuds A et B peut envoyer par anticipation
au plus w paquets consécutifs sans recevoir d’acquittement.
Ce mécanisme de contrôle de flux suppose que les unités de
données échangées (les paquets ou les trames) soient numérotées
8.4 Les méthodes de contrôle de flux dans les réseaux à commutation
par paquet 173

de 0 jusqu’à w − 1. L’acquittement s’effectue à l’aide de cette

numérotation. Par exemple dans HDLC, la réception de l’acquittement
de la trame numéro i par le noeud A ouvre à celui-ci une possi-
bilité d’émettre les trames de numéro i + 1 à i + w et d’attendre si
l’acquittement de i + 1 n’est pas encore arrivé. L’idée sous-jacente
du mécanisme de fenêtre est que le noeud émetteur doit ralentir
son rythme d’émission si la réponse du récepteur tarde à venir.
Dans le cas d’un procédure de liaison, un absence d’acquittement
signifie généralement que le noeud récepteur est saturé (il n’y a
plus de mémoires tampon disponibles pour mémoriser les trames).
Dans le cas d’un réseau, cela signifie que celui-ci est saturé par
la présence de trop de paquets. Il faut enfin noter que la taille
de la fenêtre peut dépendre du flux de trafic considéré (couple de
noeuds, circuit virtuel, ...).
On va commencer par distinguer deux applications du mécanisme
de contrôle de flux par fenêtre : de bout en bout entre l’entrée et la
sortie du réseau, et de proche en proche entre les noeuds consécutifs
dans le réseau.

Fenêtre de bout en bout

Soit w la taille de la fenêtre. Pratiquement, les paquets, de taille

fixe, sont numérotés, modulo m, m étant une puissance de 2. Ce
numéro, noté P (S), ainsi que le numéro du prochain paquet attendu
P (R) se trouvent dans l’en-tête du paquet. La réception d’un pa-
quet avec P (R) = i représente l’acquittement de tous les paquets
envoyés jusqu’au numéro i − 1, et donc une possibilité d’envoyer les
paquets numéro i, i + 1, · · · , i + w − 1 mod m .
Soit X le temps d’émission d’un paquet (que l’on suppose con-
stant), et d le délai moyen jusqu’à la réception de l’acquittement
d’un paquet envoyé.
Premier cas: d ≤ w ∗ X (Figure 8.5)
L’émetteur reçoit l’acquittement avant d’atteindre la valeur max-
imale de sa fenêtre d’anticipation. Il va pouvoir envoyer d’une
façon continue ses paquets, et le mécanisme de contrôle de flux
reste inactif.
Alors le taux moyen d’émission en paquets par seconde de l’émetteur
174 Les principes du contrôle de flux

est r = 1/X

Second cas : d > w ∗ X (Figure 8.6)

La valeur maximale de la fenêtre est atteint avant de recevoir

l’acquittement attendu. Le mécanisme de contrôle de flux entre en
action. L’émetteur arrête son émission au bout de w ∗ X secondes.
Dans ce cas, le taux moyen d’émission en paquets par seconde r
de l’émetteur est w/d. Ce retard du retour de l’acquittement peut
vouloir dire que le noeud destination est saturé, ou bien que la
route vers la destination et/ou celle de retour sont saturées.
En conclusion, la formule générale qui donne le taux moyen
d’émission en paquets par seconde de l’émetteur est :

w=6

d≤w∗X

XX
6 6 6 XXX
X XX
XXX
? XXX XX
XXX
XXX XXz
XX
XXX
d XXX XX
XX XXX
XXX Xz

XXX
XX
X
XXX
XXX XX
X z

XXX
? 9
XX
XX XXX
XXX
XXX

X
XXX z
9
XX
XXX XXX
XXX XXX
z
XX
XXX
? 9

XXX XXX
XX XX
w∗X XXX Xz
XXX
XX
XXX
Xz
? ?

Temps (émetteur) Temps (récepteur)

Figure 8.5: Cas où d ≤ w ∗ X
8.4 Les méthodes de contrôle de flux dans les réseaux à commutation
par paquet 175

1 w
r = Inf {, }
X d
Lorsque le contrôle de flux ne fonctionne pas, le taux d’émission
de paquet vaut r = 1/X paquets/s. En revanche, dès que d > w ∗ X,
alors r = w/d. C’est ce que montre la courbe r(.) = r(d) de la figure
8.7.
Il reste le problème du dimensionnement de W dont la valeur
va fixer le seuil de délai d = W ∗ X en dessous duquel le mécanisme
de contrôle de flux est inactif (tranparent). Généralement il existe
un contrat entre l’usager et le réseau qui doit garantir un temps
de séjour moyen maximum d’une unité de données dans le réseau.
Soit E[Tg ] ce temps de transit garanti dans le réseau. Notons E[t]

w=3

d>w∗X

XX
6 6 6 XXX
X XX
XXX
? XXX XX
XXX
XXX XX
z
XX
XXX
d XXX XX
XX XXX
XXX X
z

XXX
? XX X
XXX XXX
X XX
z
w∗X
XXX
? 9
X X
XXX
XXX
z

9

XXX
XXX

XXXX
9

XXX X
X
X
XX XX
XX
z
XXX
XXXX
9
XXX
XX
z
? ?

Temps (émetteur) Temps (récepteur)

Figure 8.6: Cas où d > w ∗ X
176 Les principes du contrôle de flux

le temps de traitement de la réponse correspondant à une unité de

donnée envoyée. Alors si l’on dimensionne w de manière à satisfaire
l’inégalité suivante

E[Tg ] + E[t] + E[Tg ]

w≥ +1
X
le mécanisme sera transparent (inactif), du point de vue de la
source, dans les conditions nominales de fonctionnement du réseau.
Bien entendu, cette valeur de la fenêtre est sensible à E[t] qui
dépend de la charge du récepteur.

Fenêtre de proche en proche pour les circuits virtuels

Avant d’expliquer ce mécanisme, rappelons qu’un circuit virtuel

permet pendant une période de communication entre deux ETTD

r
6

1
X
6

w
d
w∗X
d
? -

Figure 8.7: Effet du contrôle de flux

8.4 Les méthodes de contrôle de flux dans les réseaux à commutation
par paquet 177

de transmettre, en mode paquet, les données provenant d’un même

message sur une même route à travers le réseau. Tous les paquets
sont acheminés dans le réseau sur la même route, et livrés à la
destination dans l’ordre dans lequel elles ont été reçus par le réseau.
Revenons maintenant à l’étude du contrôle de flux par fenêtre de
proche en proche sur les circuits virtuels.
Cette stratégie suppose que le contrôle de flux pour chaque cir-
cuit virtuel se fait de proche en proche, entre les noeuds adjacents
de la route explicite, avec une fenêtre par couple de noeuds et par
circuit virtuel. Typiquement la taille de la fenêtre prend la valeur
2 ou 3 sur une liaison terrestre. Dans le cas d’un routage sur un
circuit virtuel, la stratégie précédente, de contrôle de flux de bout
en bout, ne permet pas d’éviter qu’un noeud de transit, ralenti par
une surcharge temporaire, ne devienne un goulet d’étranglement
pour tous les circuits virtuels qui le traversent. En effet, le contrôle
de flux s’effectue uniquement entre l’entrée et la sortie du réseau.
La stratégie de proche en proche, plus compliquée à mettre
en oeuvre, aura tendance à répartir les paquets de chaque circuit
virtuel qui traverse un noeud congestionné, sur tous les noeuds en
amont de celui-ci. En effet, considérons trois noeuds successifs i−1,
i et i + 1. Supposons que la liaison entre i et i + 1, traversée par les
circuits virtuels F1 , · · · , Fk , soit saturée. Ceci a pour conséquence
que le noeud i va avoir en mémoire w1 + ... + wk paquets, avec
wj = 2 ou 3, j = 1, · · · , k, au bout d’un certain temps. Ces paquets
correspondent respectivement aux flux F1 , · · · , Fk .
Le noeud i ne va donc plus donner d’autorisation au noeud i − 1
pour envoyer des paquets et pour chacun des circuits virtuels Fj le
traversant en transit vers i. Le noeud i − 1 à son tour va tomber
dans la même situation que celle de i pour les circuits virtuels
Fj le traversant en transit, et ne va plus donner d’autorisation
aux noeuds adjacents pour lui envoyer des paquets. De proche en
proche, les paquets des différents flux F1 , · · · , Fk vont se répartir
uniformément sur tous les noeuds entre l’entrée du réseau et le
noeud i.
Avec une politique de fenêtre de bout en bout, le noeud i aurait
accumulé w1 + · · · + wk paquets avec wj = la valeur de la fenêtre de
bout en bout qui est beaucoup plus grande que 2 ou 3. La Figure
178 Les principes du contrôle de flux

8.8 résume cette discussion.

ETTD1 ETTD2
6
A
'$ '$
?
S A
S

Congestion '$ '$
w AU
S
=
-
w w
&% &% &%
)
&%
'$ '$
@ @
@ @
@ @
R
@ w R
@

&% &%

Figure 8.8: Méthode de la fenêtre de proche en proche

La distribution uniforme des paquets le long de la route favorise

une répartition équitable des ressources entre les flux de trafic, à
condition que ces flux empruntent les mêmes types de liaisons. En
effet, considérons un noeud connecté à la fois à des liaisons satellites
et à des liaisons terrestres. Les fenêtres de contrôle de flux étant
plus larges sur les liaisons satellites, le noeud a tendance à contenir
d’avantage de paquets en provenance des liaisons satellites que des
liaisons terrestres. Une solution possible à ce problème est de
servir les circuits virtuels à base d’une politique cyclique, associée
ou non à un système de priorité qui dépend de la longueur de la
route empruntée. La Figure 8.9 illustre ce phénomène.

8.4.3 Insuffisances de la méthode de la fenêtre

Dans sa version courante avec une taille de fenêtre fixe, le mécanisme
de bout en bout décrit ci-dessus est simple à implémenter. Il
est couramment utilisé dans les réseaux. Cependant il présente
quelques insuffisances que nous allons présenter.

Insuffisance par rapport au délai

Considérons d’abord le problème du délai. Supposons qu’à un

instant donné, il existe dans le réseau n flux de trafic contrôlés
8.4 Les méthodes de contrôle de flux dans les réseaux à commutation
par paquet 179

respectivement par n fenêtres de tailles w1 , · · · , wn . Si l’on note par

N le nombre (aléatoire) total de paquets dans le réseau, alors le
nombre total moyen E[N] de paquets traversant le réseau est de la
forme

i=n
X
E[N] = bi wi
i=1

où bi est un facteur réel positif compris entre 0 et 1, proportion-

nel au temps de transit dans le réseau. En particulier si le réseau
est très chargé, tous les bi vont être très proches de 1.
'$

S
&%
@
@
@ S
@
@
@ S Liaison satellite : w = 15
@ ...
@
@ '$
@ S
@
@ T *

@ S &%
'$
@
@
R
@ Liaison terrestre : w = 3

Y
HHH
&% HH

File d’attente de la liaison terrestre

T

T S S T S S T S

'$
y
X
XX
Liaison terrestre : w = 3

Figure 8.9: Contrôle de flux dans une liaison terre-satellite

180 Les principes du contrôle de flux

Utilisant le théorème de Little, le nombre total moyen de pa-

quets E[N] présents dans le réseau est le produit du temps de
séjours moyen E[S] d’un paquet dans le réseau, par le taux moyen
global d’arrivée de paquets, λ, dans le réseau E[N] = λE[S].
Le trafic global entrant dans le réseau n’est limité que par la ca-
pacité des liaisons dans une plage de fonctionnement stable. Quand
le trafic entrant augmente, le taux global α va donc croitre pour
enfin tendre vers une constante. Cette constante dépend de la
topologie du réseau (capacité des liaisons, connectivité, ...), des
points d’entrée des flux de trafic, et du volume de chacun de ces
flux.
Pour une valeur fixée du taux global moyen λ d’arrivée des pa-
quets, le résultat précédent nous montre que le temps de transit
moyen dans le réseau est proportionnel au nombre moyen de pa-
quets E[N] présents dans le réseau, ie de w1 , · · · , wn . Quand le nom-
bre n de flux actifs dans le réseau croit, le taux global moyen λ croit
pour tendre vers une constante. Et comme E[S] = E[N] /λ, le temps
de transit moyen E[S] va ainsi croitre avec E[N] et peut devenir suff-
isamment grand pour que le contrôle de flux ne puisse plus prévenir
la congestion. Ce problème est surtout visible dans les réseaux ori-
entés datagramme. Un réseau de type X25 se protège en refusant
d’ouvrir le circuit virtuel dès que l’occupation de la mémoire dans
les noeuds de commutation, donc le nombre de CV actifs, dépasse
un certain seuil.
Pour remédier à cette situation, on peut imaginer de réduire
la taille de la fenêtre w dynamiquement en fonction de la charge
globale du réseau. Mais la gestion n’est pas facile à faire car on ne
peut pas trop diminuer la fenêtre sans bloquer involontairement
l’émetteur. En effet, le délai de transit dépend, entre autre, de
la longueur de la route empruntée, et de la nature des liaisons
traversées: câble, satellite ... Plus la route est longue, plus le pa-
quet doit traverser de files d’attente en cascade (liaison, noeuds
de commutation). Pour une longueur de chemin fixée à l par ex-
emple, le délai de transit est au moins égal à l ∗ X, X étant le
temps d’émission d’un paquet (on néglige généralement le temps
de traitement de l’acheminement qui est réalisé par l’unité centrale
devant le temps d’émission d’une trame qui est réalisé par l’unité
8.4 Les méthodes de contrôle de flux dans les réseaux à commutation
par paquet 181

d’entrée/sortie). Pour permettre un fonctionnement continu de

l’émetteur, il faut que la fenêtre d’anticipation w soit telle que
w ∗ X ≥ l ∗ X. Le membre de droite représente le temps minimal de
transit que met l’acquitte-ment pour atteindre l’émetteur. On ne
peut donc pas diminuer arbitrairement la fenêtre. Généralement,
on affecte à W une valeur entre 2 ∗ l et 3 ∗ l dans le cas où le délai
de propagation est négligeable devant le temps d’émission, et une
valeur nettement plus grande que 3 ∗ l si la route contient une ou
plusieurs liaisons satellite géostationnaire. Toute cette discussion
sous-entend que la route est choisie une fois pour toute (l fixée).
Cette hypothèse est vraie dans un réseau où le routage est basé sur
un service de type circuit virtuel avec une route fixée à l’ouverture
du circuit. La gestion de la fenêtre et du délai devient, en revanche,
beaucoup plus difficile dans un réseau orienté datagramme avec un
routage adaptatif (le réseau INTERNET par exemple). Dans ce
type de réseau, les routes changent régulièrement en fonction de la
charge, et ces changements s’effectuent d’une manière transparente
aux utilisateurs (ETTD) du réseau.

Insuffisance par rapport à ”l’équité”

Comme nous l’avons remarqué plus haut, plus la route empruntée
par un flux est longue, plus la taille de la fenêtre d’anticipation
associée à ce flux est grande. De même, on donne la priorité au
trafic en transit par rapport au trafic extérieur entrant dans un
noeud du réseau.
'$
F1 '$ '$ '$ '$
-

&% &%6 &% &% &%

6 -

Liaison

Figure 8.10: Insuffisance par rapport à l’équité

Considérons le cas de la figure 8.10 d’une liaison dans le réseau

traversée par deux flux F1 et F2 . F1 emprunte une route longue,
182 Les principes du contrôle de flux

et F2 une route courte. Statistiquement, F1 va avoir plus de pa-

quets présents dans le réseau que F2 , car sa fenêtre est plus grande.
Comme de plus le trafic de F1 va être prioritaire sur celui de F2 au
niveau de la liaison, F1 va disposer de plus de ressources que F2 .

8.5 Le contrôle de flux au niveau de l’ETTD

Il arrive dans un couple d’ETTD qu’il y ait plusieurs applications
qui communiquent entre elles, générant un trafic assez faible (par
exemple transactionnel) pour justifier la fonction de multiplexage-
démultiplexage de ces flux de trafic sur le même circuit virtuel.
Il arrive aussi, inversement, qu’un couple d’applications échange
un trafic suffisamment important (par exemple une communication
multimédia interactive) pour justifier l’utilisation de plusieurs con-
nexions en parallèle pour l’acheminement de ce flux de trafic.
Dans les deux cas de figure ci-dessus, il devient souhaitable que
chaque ETTD dispose de son propre mécanisme de contrôle de
flux indépendamment de celui qui existe au niveau du routage à
l’intérieur du réseau. Un tel mécanisme opère de la même manière
que la fenêtre de bout en bout du routage.

8.6 Modèle de la fenêtre d’anticipation

Nous allons considérer la situation d’une connexion qui traverse
plusieurs nœud de transit. C’est le cas d’une connexion de la
couche 3 au dessus de la couche 2, ou encore de la couche 4
au dessus d’une couche 3 offrant un service orienté connexion.
Le cas d’une couche 4 au dessus d’une couche trois sans connex-
ion peut être étudié comme un cas particulier où le réseau peut
être modélisé par une seule file d’attente unique de type M/M/n
représentant la traversée totale du réseau. Cette classe de file
provoque un phénomène de déséquencement des paquets suscepti-
ble d’apparaı̂tre dans un réseau de type datagramme.
Nous allons reprendre le modèle du circuit virtuel du chapitre
précédent où chaque nœud va être modélisé par deux files d’attente
en série. La première représente la fonction de routage au niveau 3
8.6 Modèle de la fenêtre d’anticipation 183

tandis que la deuxième le délai dû au passage dans le contrôleur de

liaison. L’entrée en action du mécanisme de la fenêtre aura pour
conséquence de limiter le nombre de paquets qui empruntent le
circuit virtuel à une valeur maximale fixée d’avance. Quand ce seuil
est atteint, le CV devient saturé, et la source émettrice va devoir
bloquer son émission, tant que le nombre de paquets qui circulent
ne descend pas au dessous de ce seuil. C’est la destination qui
informe la source de la bonne réception des paquets en renvoyant
des paquets d’acquittement.

Première approximation : négliger le blocage

Aux paragraphes précédents, nous avons discuté les diverses

causes possibles de l’activation de la fenêtre de contrôle de flux.
Chacune de ces causes peut être représentée par un modèle mathématique
permettant d’estimer les performances du réseau. Dans le cadre
de notre étude, on va négliger la saturation de la mémoire dans
les noeuds, un phénomène qui engendre le blocage et qui n’est pas
facile à modéliser.

Modèle retenu : réseau de Jackson fermé

Sous ces hypothèses, on peut donc modéliser le mécanisme de

la fenêtre par un réseau de file d’attente qui représente la route du
paquet d’acquittement et qui forme avec le réseau de file d’attente
(ie la route) du CV aller un cycle fermé (figure 8.11).
Les politiques de l’acquittement: on peut considérer deux poli-
tiques

• La première consiste à acquitter paquet par paquet,

• La deuxième consiste à acquitter plusieurs paquets à la fois.

Discussion autour de la deuxième politique

La deuxième politique est celle qui semble la plus intéressante

quand le récep-teur a peu de choses à dire à l’émetteur. Elle est
184 Les principes du contrôle de flux

- - - ... - -
6

File n1 File n2 ... File ni

α paquets/s

α3

... ?

File nk ... File ni+2 File ni+1

Figure 8.11: Modèle de la fenêtre par un réseau fermé

celle qui risque d’induire une attente supplémentaire de l’émetteur.

Elle n’est donc pas favorable en terme de performances.
On peut également montrer que cette deuxième politique aboutit
à un réseau de file d’attente qui ne peut pas être à forme produit.
En effet, un acquittement permet à l’émetteur d’envoyer plusieurs
paquets par anticipation, ce qui se traduit au niveau du réseau
de file d’attente par une arrivée groupée au niveau de l’émetteur.
Ce qui fait que le réseau n’est pas à forme produit. Or seuls les
réseaux à forme produit ont des résultats analytiques complets.
A la rigueur, on peut encore simuler le phénomène et estimer les
paramètres (longueur de file, temps de transit, ...). Il existe aussi
des techniques d’approximation d’un réseau n’ayant pas la forme
produit par des réseaux à forme produit. Malheureusement, ces
modèles approchés à forme produit ne sont réellement valables que
si la route est de longueur inférieure ou égale à trois.

Discussion autour de la première politique:

La première politique est celle qui est utilisée quand le trafic en-
8.6 Modèle de la fenêtre d’anticipation 185

tre les ETTD est symétrique. Elle minimise l’attente de l’émetteur

et favorise donc les performances. Elle conduit à un réseau à forme
produit fermé où il circule exactement autant de paquets que per-
met la fenêtre d’anticipation. Bien entendu, l’acquittement ex-
plicite paquet par paquet engendre plus de trafic. Mais quand le
trafic est quasi-symétrique ces acquittements seront intégrés dans
les paquets d’information. La forme mathématique de la distribu-
tion de probabilité du nombre de paquets le long du circuit virtuel
est donnée au chapitre 1. Cette forme se simplifie dans le cas
présent

(α)w
P{n} = Bw
µn1 1 .µn2 2 · · · µnk k
où

• α = le taux d’arrivée des paquets dans le CV,

• n = (n1 , n2 , · · · , nk ) le vecteur qui représente le nombre de pa-

quets dans les noeuds 1, 2, · · · , k qui forment le CV,

• w = n1 + n2 + · · · + nk étant le nombre maximum de paquets qui

peuvent circuler dans le CV,

• et

X (α)w
Bw = [ ]−1
n
µn1 1 .µn2 2 ...µnk k

la constante de normalisation qui assure que

X
P{n} = 1
n

pour tous les vecteurs n

n = (n1 , n2 , ..., nk )

satisfaisant w = n1 + n2 + ... + nk .
186 Les principes du contrôle de flux

Regardons maintenant comment prendre en compte des autres

flux de trafic.
En effet, pour prendre en compte la présence des autres flux
de trafic la technique consiste à réduire la capacité de service des
contrôleurs de liaison d’autant. Dans l’exemple précédent cela re-
vient à multiplier la vitesse

• v1 de la liaison L1 par α/(α + α1 ),

• v2 de la liaison L2 par α/(α + α2 ),

• ...

La figure 8.11 représente le modèle de la fenêtre d’anticipation

en terme de réseau fermé de files d’attente.

En conclusion, nous avons considéré une modèle simplifié où

deux ETTD s’échangent un trafic symétrique et utilisent le mécanisme
d’acquittement paquet par paquet. Nous avons également sup-
posé que l’effet de la saturation de la mémoire des noeuds est
négligeable. Alors le CV et le mécanisme d’anticipation associée
constituent un réseau à forme produit fermé. Ce qui permet d’utiliser
les résultats analytiques exacts des réseaux de Jackson fermés pour
avoir la distribution (marginale) du nombre de paquets dans cha-
cune des files du réseau. Connaissant ces lois de probabilité marginales
on peut calculer la longueur moyenne de chaque file. Il reste à
utiliser le théorème de Little (voir le paragraphe précédent) pour
déduire le temps de transit dans chaque file, donc en particulier du
délai de retours de l’acquittement.

Vous aimerez peut-être aussi

Analyse Quantitatives de Réseaux
100% (1)
Analyse Quantitatives de Réseaux
220 pages
Modèles d'attente pour réseaux mobiles
Pas encore d'évaluation
Modèles d'attente pour réseaux mobiles
220 pages
Modélisation du Trafic Routier
Pas encore d'évaluation
Modélisation du Trafic Routier
110 pages
Optimisation Réseaux MPLS: Modélisation
Pas encore d'évaluation
Optimisation Réseaux MPLS: Modélisation
102 pages
Modélisation des Systèmes Complexes
Pas encore d'évaluation
Modélisation des Systèmes Complexes
55 pages
Polycopié ASR Version 2 2024-1-10
Pas encore d'évaluation
Polycopié ASR Version 2 2024-1-10
10 pages
23440
Pas encore d'évaluation
23440
107 pages
L'ingénierie Des Réseaux Cellulaires
Pas encore d'évaluation
L'ingénierie Des Réseaux Cellulaires
27 pages
Exercices sur les Files d'Attente
100% (2)
Exercices sur les Files d'Attente
56 pages
Contrôle intelligent des flux dans MANETs
Pas encore d'évaluation
Contrôle intelligent des flux dans MANETs
107 pages
Answers INF7345 HomeWork
Pas encore d'évaluation
Answers INF7345 HomeWork
10 pages
Abboud Khodor DLE
Pas encore d'évaluation
Abboud Khodor DLE
185 pages
Mi06 M2lessons-Reseaux 2
Pas encore d'évaluation
Mi06 M2lessons-Reseaux 2
41 pages
PFE REZGUI Ramzi
100% (1)
PFE REZGUI Ramzi
92 pages
Suivi Performance Réseau GSM
0% (1)
Suivi Performance Réseau GSM
102 pages
Cours Complet
Pas encore d'évaluation
Cours Complet
57 pages
Support-Cours de Réseaux M1
Pas encore d'évaluation
Support-Cours de Réseaux M1
98 pages
Cours Réseaux Informatiques ESG2E
Pas encore d'évaluation
Cours Réseaux Informatiques ESG2E
99 pages
Support KHATIR2021AMELIORE 1 37
Pas encore d'évaluation
Support KHATIR2021AMELIORE 1 37
37 pages
Contrôle de congestion dans les protocoles de transport
Pas encore d'évaluation
Contrôle de congestion dans les protocoles de transport
231 pages
These Important
Pas encore d'évaluation
These Important
200 pages
Cours Eval Perf 2020 PDF
Pas encore d'évaluation
Cours Eval Perf 2020 PDF
105 pages
Introduction aux Réseaux Informatiques
Pas encore d'évaluation
Introduction aux Réseaux Informatiques
89 pages
Thème: Présidente: Examinatrice: Encadrant: Co-Encadrante: Invitée
Pas encore d'évaluation
Thème: Présidente: Examinatrice: Encadrant: Co-Encadrante: Invitée
65 pages
PFE Final
0% (1)
PFE Final
87 pages
Modelisation - TP Ramy Et Omar
Pas encore d'évaluation
Modelisation - TP Ramy Et Omar
26 pages
Main
Pas encore d'évaluation
Main
33 pages
Cours Réseaux Informatique
Pas encore d'évaluation
Cours Réseaux Informatique
76 pages
Systèmes Informatiques Temps Réel
Pas encore d'évaluation
Systèmes Informatiques Temps Réel
158 pages
Mémoire - HOUNMENOU - Ange - Mikaël
Pas encore d'évaluation
Mémoire - HOUNMENOU - Ange - Mikaël
97 pages
Allocation des Ressources Radio en WLAN OFDM
Pas encore d'évaluation
Allocation des Ressources Radio en WLAN OFDM
85 pages
Rapport Simulation Reseaux Yahya Mohamed
Pas encore d'évaluation
Rapport Simulation Reseaux Yahya Mohamed
18 pages
SANNER Jean Michel
Pas encore d'évaluation
SANNER Jean Michel
232 pages
Optimisation Réseau 3G à Maroua
Pas encore d'évaluation
Optimisation Réseau 3G à Maroua
98 pages
Simulation de Réseaux avec OPNET Modeler
Pas encore d'évaluation
Simulation de Réseaux avec OPNET Modeler
61 pages
Gestion du Spectre en Télécommunication
Pas encore d'évaluation
Gestion du Spectre en Télécommunication
87 pages
Réseaux GSM : Guide Complet
67% (3)
Réseaux GSM : Guide Complet
19 pages
Reseaux GSM TDM Ocr
Pas encore d'évaluation
Reseaux GSM TDM Ocr
19 pages
Yankam Thesis
Pas encore d'évaluation
Yankam Thesis
167 pages
2001 TH Medina Carvajal
Pas encore d'évaluation
2001 TH Medina Carvajal
158 pages
Leçon 3 Chapitre 3 Dimensionnement
100% (4)
Leçon 3 Chapitre 3 Dimensionnement
13 pages
Poly
Pas encore d'évaluation
Poly
147 pages
213617553
Pas encore d'évaluation
213617553
161 pages
Cours Ac
Pas encore d'évaluation
Cours Ac
188 pages
Cours Réseaux Informatiques ESG2E
100% (1)
Cours Réseaux Informatiques ESG2E
125 pages
Generalites Files D'attentes
Pas encore d'évaluation
Generalites Files D'attentes
23 pages
Contribution Ã L'etude Et Au Dimensionnement D'un Reseau D'entreprise
Pas encore d'évaluation
Contribution Ã L'etude Et Au Dimensionnement D'un Reseau D'entreprise
107 pages
Technologie des ordinateurs et réseaux
Pas encore d'évaluation
Technologie des ordinateurs et réseaux
2 pages
9782402635318
Pas encore d'évaluation
9782402635318
23 pages
Smb5722 Configure Vlan Interface Ipv4 Address On An Sx350 or Sg350x
Pas encore d'évaluation
Smb5722 Configure Vlan Interface Ipv4 Address On An Sx350 or Sg350x
11 pages
1-TP N°1 - Devpt - Web - Coté - Serveur
Pas encore d'évaluation
1-TP N°1 - Devpt - Web - Coté - Serveur
4 pages
7ST20TEWB0623 Devoir3
0% (1)
7ST20TEWB0623 Devoir3
2 pages
Liste Doublement Chaînée: Syntaxe et Manipulation
Pas encore d'évaluation
Liste Doublement Chaînée: Syntaxe et Manipulation
27 pages
Expressions régulières en JavaScript
Pas encore d'évaluation
Expressions régulières en JavaScript
13 pages
Relatif Au:module: Armee de L'Air Tunisienne
Pas encore d'évaluation
Relatif Au:module: Armee de L'Air Tunisienne
9 pages
CV Intelligence D Affaires FR VF2
Pas encore d'évaluation
CV Intelligence D Affaires FR VF2
2 pages
Inot Actes: La Signature Numérique
Pas encore d'évaluation
Inot Actes: La Signature Numérique
27 pages
Levolution Des Effets Speciaux Dans Les Films de Science-Fiction
Pas encore d'évaluation
Levolution Des Effets Speciaux Dans Les Films de Science-Fiction
13 pages
Diagrammes de Bode et systèmes linéaires
100% (1)
Diagrammes de Bode et systèmes linéaires
2 pages
Formation EBP Compta PRO 2018
Pas encore d'évaluation
Formation EBP Compta PRO 2018
20 pages
Microsoft PowerPoint 2019 Fundamentals
Pas encore d'évaluation
Microsoft PowerPoint 2019 Fundamentals
41 pages
Cours de Systemes Asservis
Pas encore d'évaluation
Cours de Systemes Asservis
78 pages
Rapport de stage chez SAGEMCOM 2019
Pas encore d'évaluation
Rapport de stage chez SAGEMCOM 2019
27 pages
TP 1 Brute Force SN1SIO
Pas encore d'évaluation
TP 1 Brute Force SN1SIO
2 pages
Java TP
100% (1)
Java TP
5 pages
SupportLinux Admin
Pas encore d'évaluation
SupportLinux Admin
225 pages
Optimisation linéaire avancée
Pas encore d'évaluation
Optimisation linéaire avancée
6 pages
TP02
Pas encore d'évaluation
TP02
13 pages
Algo Chap4 TABLEAU
Pas encore d'évaluation
Algo Chap4 TABLEAU
16 pages
Objets Communicants
100% (1)
Objets Communicants
6 pages
E-Madina Le Livre Blanc de LAPEBI Pour Les Villes Intelligentes Au Maroc
Pas encore d'évaluation
E-Madina Le Livre Blanc de LAPEBI Pour Les Villes Intelligentes Au Maroc
36 pages
Electronique Analogique
Pas encore d'évaluation
Electronique Analogique
56 pages
Guide d'installation Somfy
Pas encore d'évaluation
Guide d'installation Somfy
18 pages
L'impact de La Communication Digitale Sur La Fidélisation de La Clientèle
84% (32)
L'impact de La Communication Digitale Sur La Fidélisation de La Clientèle
57 pages
Guide des Termes de Topographie et Géodésie
100% (1)
Guide des Termes de Topographie et Géodésie
7 pages
Histoire et Impact d'Instagram
Pas encore d'évaluation
Histoire et Impact d'Instagram
9 pages
Initiation à Python par le Jeu
Pas encore d'évaluation
Initiation à Python par le Jeu
3 pages
Correction TD 1
Pas encore d'évaluation
Correction TD 1
5 pages
EXCEL INITIATION Avec Certif
Pas encore d'évaluation
EXCEL INITIATION Avec Certif
1 page
Modèle Dynamique et Amplificateurs EC
Pas encore d'évaluation
Modèle Dynamique et Amplificateurs EC
35 pages