Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
\section{Fondements Théoriques}
\subsection{Introduction à la Théorie des Files d'Attente}
La théorie des files d'attente, initiée par A.K. Erlang en 1909 pour l'analyse des réseaux téléphoniques, est un outil mathématique puissant pour modéliser et analyser les systèmes avec arrivées aléatoires et temps de service variables.
\subsubsection{Notation de Kendall}
Un système de files d'attente est caractérisé par la notation \textbf{A/S/c/K/N/D} où:
\begin{itemize}
\item \textbf{A}: Distribution des inter-arrivées (M = Markovienne/exponentielle)
\item \textbf{S}: Distribution des temps de service (M = Markovienne/exponentielle)
\item \textbf{c}: Nombre de serveurs
\item \textbf{K}: Capacité du système (omis si $\infty$)
\item \textbf{N}: Taille de la population (omise si $\infty$)
\item \textbf{D}: Discipline de service (FIFO par défaut)
\end{itemize}
Dans ce projet, nous utilisons des files \textbf{M/M/1} (arrivées Markoviennes, service Markovien, 1 serveur).
\subsection{File M/M/1}
\subsubsection{Hypothèses}
Une file M/M/1 repose sur les hypothèses suivantes:
\begin{enumerate}
\item \textbf{Arrivées}: Processus de Poisson de taux $\lambda$ (inter-arrivées $\sim \text{Exp}(\lambda)$)
\item \textbf{Service}: Temps de service $\sim \text{Exp}(\mu)$ indépendants
\item \textbf{Un seul serveur}: $c = 1$
\item \textbf{Capacité infinie}: Pas de limite sur la longueur de la file
\item \textbf{FIFO}: Premier arrivé, premier servi
\item \textbf{Indépendance}: Arrivées et services indépendants
\end{enumerate}
\subsubsection{Métriques Fondamentales}
\begin{definition}[Utilisation]
L'utilisation (ou taux d'occupation) est définie par:
\begin{equation}
\rho = \frac{\lambda}{\mu}
\end{equation}
où $\lambda$ est le taux d'arrivée et $\mu$ le taux de service.
\end{definition}
\begin{theorem}[Condition de Stabilité]
Une file M/M/1 est stable si et seulement si:
\begin{equation}
\rho < 1 \quad \Leftrightarrow \quad \lambda < \mu
\end{equation}
\end{theorem}
\begin{proof}
Si $\rho \geq 1$, le taux d'arrivée est supérieur ou égal au taux de service, donc la file croît indéfiniment. Si $\rho < 1$, la file atteint un régime stationnaire.
\end{proof}
\subsubsection{Formules Analytiques en Régime Permanent}
Pour une file M/M/1 stable ($\rho < 1$), les métriques en régime permanent sont:
\begin{align}
L &= \frac{\rho}{1-\rho} \quad &&\text{(Nombre moyen de clients dans le système)} \label{eq:L} \\
L_q &= \frac{\rho^2}{1-\rho} \quad &&\text{(Nombre moyen de clients en attente)} \label{eq:Lq} \\
W &= \frac{1}{\mu - \lambda} = \frac{1}{\mu(1-\rho)} \quad &&\text{(Temps moyen dans le système)} \label{eq:W} \\
W_q &= \frac{\rho}{\mu - \lambda} = \frac{\rho}{\mu(1-\rho)} \quad &&\text{(Temps moyen d'attente)} \label{eq:Wq}
\end{align}
\subsection{Loi de Little}
\begin{theorem}[Loi de Little, 1961]
Pour un système en régime stationnaire:
\begin{equation}
L = \lambda W
\label{eq:little}
\end{equation}
où $L$ est le nombre moyen de clients dans le système, $\lambda$ le taux d'arrivée effectif, et $W$ le temps moyen passé dans le système.
\end{theorem}
Cette loi fondamentale relie trois quantités importantes et s'applique à tout système stable, indépendamment des distributions des arrivées et services.
\subsection{Théorème de Jackson}
\subsubsection{Réseaux de Files d'Attente}
Un réseau de files d'attente est un ensemble de $N$ stations (files) où les clients peuvent se déplacer d'une station à une autre selon des probabilités de routage.
\begin{definition}[Réseau Ouvert de Jackson]
Un réseau ouvert de Jackson est caractérisé par:
\begin{itemize}
\item $N$ stations de service
\item Arrivées externes à la station $i$ selon un processus de Poisson de taux $\gamma_i \geq 0$
\item Chaque station $i$ a un seul serveur avec temps de service $\sim \text{Exp}(\mu_i)$
\item Probabilité $p_{ij}$ de routage de la station $i$ vers la station $j$
\item Probabilité $p_{i0}$ de quitter le système depuis la station $i$
\end{itemize}
\end{definition}
\subsubsection{Taux d'Arrivée Effectifs}
Les taux d'arrivée effectifs $\lambda_i$ à chaque station satisfont les équations d'équilibre:
\begin{equation}
\lambda_i = \gamma_i + \sum_{j=1}^{N} \lambda_j p_{ji}, \quad i = 1, \ldots, N
\label{eq:equilibre}
\end{equation}
Ces équations forment un système linéaire qui peut être résolu pour obtenir les $\lambda_i$.
\subsubsection{Théorème Principal}
\begin{theorem}[Théorème de Jackson, 1957]
Pour un réseau ouvert de Jackson avec $\rho_i = \lambda_i / \mu_i < 1$ pour tout $i$:
\begin{enumerate}
\item Chaque station se comporte comme une file M/M/1 indépendante
\item La distribution stationnaire du nombre de clients est:
\begin{equation}
\pi(n_1, \ldots, n_N) = \prod_{i=1}^{N} (1-\rho_i)\rho_i^{n_i}
\end{equation}
\item Les métriques de performance pour la station $i$ sont:
\begin{align}
L_i &= \frac{\rho_i}{1-\rho_i} \\
W_i &= \frac{1}{\mu_i - \lambda_i}
\end{align}
\item Les métriques globales du réseau sont:
\begin{align}
L_{\text{total}} &= \sum_{i=1}^{N} L_i \\
W_{\text{total}} &= \frac{L_{\text{total}}}{\lambda_{\text{externe}}}
\end{align}
\end{enumerate}
\end{theorem}
\subsubsection{Implications Pratiques}
Le théorème de Jackson a des conséquences importantes:
\begin{itemize}
\item \textbf{Décomposition}: Un réseau complexe peut être analysé en décomposant chaque station individuellement
\item \textbf{Indépendance}: Les stations sont statistiquement indépendantes en régime permanent
\item \textbf{Simplicité}: Les formules M/M/1 s'appliquent directement à chaque station
\item \textbf{Validation}: Permet la validation analytique de simulations complexes
\end{itemize}
\subsection{Application à Notre Système}
Dans le contexte de notre base de données distribuée:
\begin{itemize}
\item \textbf{Station 1}: Coordinateur (arrivées externes $\lambda$, service $\mu_c$)
\item \textbf{Stations 2 à $N+1$}: Serveurs (pas d'arrivées externes, services $\mu_1, \ldots, \mu_N$)
\item \textbf{Routage}: Depuis le coordinateur:
\begin{itemize}
\item Probabilité $p$ de sortie du système
\item Probabilité $q_i$ de routage vers le serveur $i$ (avec $p + \sum_i q_i = 1$)
\end{itemize}
\item \textbf{Feedback}: Tous les serveurs retournent au coordinateur ($p_{i,\text{coord}} = 1$)
\end{itemize}
Les équations d'équilibre deviennent:
\begin{align}
\lambda_{\text{coord}} &= \lambda + \sum_{i=1}^{N} \lambda_i \label{eq:coord-equilibre} \\
\lambda_i &= \lambda_{\text{coord}} \cdot q_i, \quad i = 1, \ldots, N \label{eq:server-equilibre}
\end{align}
En substituant \eqref{eq:server-equilibre} dans \eqref{eq:coord-equilibre}:
\begin{equation}
\lambda_{\text{coord}} = \lambda + \lambda_{\text{coord}} \sum_{i=1}^{N} q_i = \lambda + \lambda_{\text{coord}}(1-p)
\end{equation}
D'où:
\begin{equation}
\lambda_{\text{coord}} = \frac{\lambda}{p} \quad \text{et} \quad \lambda_i = \frac{\lambda q_i}{p}
\label{eq:lambda-final}
\end{equation}
Ces relations seront utilisées pour calculer les métriques analytiques de notre système.