diff options
Diffstat (limited to 'stage/article.tex')
| -rw-r--r-- | stage/article.tex | 101 |
1 files changed, 92 insertions, 9 deletions
diff --git a/stage/article.tex b/stage/article.tex index af32985..37761ca 100644 --- a/stage/article.tex +++ b/stage/article.tex @@ -1,7 +1,8 @@ -\documentclass[a4,11pt,titlepage]{article} +\documentclass[a4paper,11pt]{article} \usepackage[T1]{fontenc} -\usepackage[utf8]{inputenc} +\usepackage[utf8x]{inputenc} \usepackage[french]{babel} +\usepackage{graphicx} \usepackage{listings} \lstdefinelanguage{pseudo} @@ -14,14 +15,45 @@ basicstyle=\small, keywordstyle=\bfseries, captionpos=b} \newtheorem{thm}{Theorem} \theoremstyle{remark} -\newtheorem*{rem}{Remark} +\newtheorem*{rem}{Remarque} \title{Pacemaker : un protocole de mesure de disponibilité dans les réseaux pair-à-pair} -\date{Sujet proposé et encadré par Fabrice Le Fessant} +\author{Encadrant : \\ Fabrice Le Fessant \\ INRIA-Saclay \and Étudiant : \\ Thibaut Horel} \begin{document} \maketitle + +\subsection*{Le contexte général} + +Ce rapport se situe dans le domaine des réseaux pair-à-pair. Ces réseaux possèdent des propriétés de passage à l'échelle et de robustesse par opposition aux réseaux centralisés qui en font un sujet d'étude intéressant, à la fois au niveau des applications pratiques (DNS, partage de fichiers, systèmes de fichiers distribués, calcul distribué, \ldots) et de l'étude théorique. Les travaux sur les réseaux pair-à-pair portent généralement sur : +\begin{itemize} +\item la structuration des réseaux pair-à-pair, le plus souvent par la mise en place d'une Table de Hachage Distribuée (DHT). +\item la localisation de ressources dans le réseau. +\item le routage des requêtes dans le réseau. +\end{itemize} + +\subsection*{Le problème étudié} + +Le problème étudié plus spécifiquement ici est celui de la mesure de disponibilité des pairs, c'est-à-dire de la fraction du temps passée par les pairs sur le réseau. Cette information de disponibilité est importante car elle permet de localiser les nœuds qui peuvent être le plus utile au réseau et sur lesquels on peut s'appuyer pour structurer ou stabiliser le réseau. On peut par exemple utiliser cette information pour sélectionner un certain nombre de \emph{super-pairs} dans le réseau, qui seront connectés en une clique, les autres pairs s'organisant autour de chacun des super-pairs. + +L'utilisation que l'on peut faire d'une telle information a déjà été étudiée à plusieurs reprises (REFERENCE). En revanche, la réalisation effective d'une telle mesure est restée sans réponse réellement satisfaisante. À ma connaissance, les deux seuls travaux sur le sujet sont REFERENCE. La solution proposée ici met l'accent sur la non-falsifiabilité de la mesure. En effet, cette information étant calculée de façon distribuée, il est impossible d'avoir une autorité garantissant la validité de l'information. La disponibilité mesurée doit donc être exacte, même en supposant un comportement malveillant de la part des pairs. + +\subsection*{La contribution proposée} + +La solution proposée ici repose sur un système de \emph{preuves} : chaque pair du réseau reçoit à intervalle régulier une preuve de sa présence. L'ensemble des preuves collectées par le pair constitue un historique de sa présence passée et permet donc de connaître sa disponibilité. L'information est non falsifiable au sens où il est impossible pour le pair de fabriquer une preuve de sa présence à un instant donné s'il n'était pas présent sur le réseau à cet instant. + +La solution que l'on trouve dans REFERENCE repose sur le partage d'un secret relatif à un instant donné. Le protocole mis au point dans ce rapport repose sur la même idée. Toutefois il fallait empêcher la transmission du secret après la période à laquelle est associé le secret. L'idée utilisée ici consiste à \emph{figer} la connaissance du secret des nœuds présents par le calcul d'un Arbre de Merkel. Cette structure de donnée contient une information globale sur le réseau et ne peut donc pas être calculé par un seul nœud. La mise au point du protocole repose donc principalement sur le calcul distribué d'un arbre de Merkel. + +\subsection*{Les arguments en faveur de sa validité} + +La solution proposée semble robuste à la fois au niveau théorique (cf. REFERENCE) et expérimental. La simulation réalisée sur un grand nombre de nœuds montre que le protocole étudié fonctionne même à grande échelle. Certaines hypothèses simplificatrices ont éte faites au cours de l'étude (modèle cryptographique sous-jacent, communication simplifiée, \ldots), mais le déploiement effectué sur un réseau réel montre que ces hypothèses sont raisonnables au vu des applications pratiques. + +\subsection*{Le bilan et les perspectives} + +Le protocole étudié dans ce rapport apporte donc une solution effective au problème posé. La simplicité relative du protocole permet une implémentation aisée. Des expériences d'utilisation de ce protocole sur différents réseaux pair-à-pair permettrait de confirmer sa robustesse dans les cas d'application très variés du pair-à-pair. En particulier, l'influence de la topologie sous-jacente n'a pas été réellement étudiée ici. De plus, il serait intéressant d'étudier si l'information de disponibilité fournie par le protocole pourrait elle-même être utilisée pour modifier dynamiquement la structure du réseau et ainsi accroître la performance du protocole. + \tableofcontents + \newpage \section{Introduction} @@ -60,7 +92,11 @@ Le but du présent rapport est donc de présenter et d'étudier le protocole \em Le protocole Pacemaker réalise un compromis entre l'approche individuelle et l'approche centralisée présentée ci-dessus : chaque pair présent dans le réseau reçoit à intervalle régulier une preuve de sa présence calculée par l'ensemble du réseau, celle-ci est stockée par le pair lui-même pour être présentée au besoin à la demande des autres pairs. Cette approche résout donc naturellement le problème de \textbf{durabilité temporelle} : l'information est disponible aussi longtemps qu'elle est utile, c'est à dire, aussi longtemps que le pair est présent sur le réseau. De plus, cette approche conserve la simplicité de l'approche individuelle en évitant la communication avec des tiers pour obtenir l'information de disponibilité. -La section 2. présente le modèle et les hypothèses sur lesquels repose Pacemaker, la section 3. contient la spéficiation complète du protocole, les sections suivantes s'attachent à l'analyse théorique et expérimentale du protocole, à travers une simulation et un déploiement sur PlanetLab\footnote{PlanetLab est un réseau constitués d'ordinateurs fournis par diverses entreprises et universités à travers le monde et mis à la disposition de l'ensemble des membres du réseau.}. +La section 2. présente le modèle et les hypothèses sur lesquels repose Pacemaker, la section 3. contient la spéficiation complète du protocole, les sections suivantes s'attachent à l'analyse théorique et expérimentale du protocole, à travers une simulation et un déploiement sur PlanetLab. + +\subsection*{Remerciements} + +Je tiens à exprimer tout ma gratitude envers Fabrice Le Fessant, pour la qualité et la bienveillance de son encadrement tout au long de stage, qui m'a permis d'apprendre beaucoup sur les réseaux pair-à-pair, envers Tiphaine Turpin, pour avoir patiemment répondu à toutes mes questions sur OCaml et enfin envers mon frère Guillaume pour m'avoir conseillé les outils que j'ai utilisés au cours de la partie expérimentale de ce rapport. \section{Modèle et notations} @@ -113,7 +149,7 @@ Le protocole utilise trois messages différents, correspondant aux trois phases \item $i$ est le numéro de ronde \item \textsf{seed$^i$} est la graine de la $i$-ème ronde \item $T^i$ est la durée de la phase de récolte - \item \textsf{S$^i_{pulse}$} est \textsf{sign($\langle$$i$|seed$^i$|$T^i\rangle$, KS$_{priv}$)} + \item \textsf{S$^i_{seed}$} est \textsf{sign($\langle$$i$|seed$^i$|$T^i\rangle$, KS$_{priv}$)} \end{itemize} \item \textsf{SeedReply($i$, H$_p$)} est utilisé pour construire le graph de hashs pendant la phase de récolte où \textsf{H$_p$} est le hash envoyé par le pair $p$, c'est-à-dire le hash de la table des jetons reçus par le pair $p$. \item \textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)} pour diffuser la pulsation: @@ -142,6 +178,7 @@ Le serveur initialise la ronde en générant la graine aléatoire, en la signant Le serveur attend ensuite pendant une durée $T^i$, au cours de laquelle il reçoit les hashs de ces fils, cf. REFERENCE. +\newpage \begin{lstlisting}[caption=Pair $p$ à la réception de \textsf{Seed($i$, seed$^i$, $T^i$, S$^i_{seed}$)}] if @@ -175,6 +212,8 @@ Le pair initialise les données relatives à la ronde. map$^i$ contiendra les je Le pair envoie le hash de la table des jetons qu'il a collectés tout en stockant l'association hash/table correspondante. Ceci est effectué toutes $\Delta$ secondes pour permettre à l'information de ``remonter'' depuis les feuilles de l'arbre jusqu'à la racine durant la phase de récolte. Plus précisément, si $D$ est le rayon du graphe par rapport à la racine, on doit avoir $D\Delta\leq T^i$. Ceci est nécessaire pour que le hash calculé par la racine à la fin de la phase de récolte constitue effectivement une empreinte de l'ensenble du graphe. +\vspace{1cm} + \begin{lstlisting}[caption={Serveur ou pair à la réception de \textsf{SeedReply($i$, X$_q$)} depuis le pair $q$}] if phase$^i$ = SEEDING then @@ -198,6 +237,8 @@ Le pair $p$ met simplement à jour sa table pair/jeton. Si la table contient dé À la fin de la phase de récolte, le serveur hache la table des jetons de ses fils, signe le résultat et initialise la pulsation avec cette table. +\vspace{1cm} + \begin{lstlisting}[caption={Pair $p$ à la réception de \textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)}}] if verify(S$^i_{pulse}$, $\langle$$i$|seed$^i$|hash(branch$^i$[0])$\rangle$, @@ -237,6 +278,7 @@ Le protocole prévoit trois messages supplémentaires pour la transmission et la \end{itemize} Ces messages sont utilisés comme suit : +\vspace{1cm} \begin{lstlisting}[caption=Pair $p$ transmettant à $q$ son historique de présence au cours des $N$ derniers rounds] let bits$^i$ = new bitfield[$N$]; for $x$ in [1..$N$] @@ -250,6 +292,8 @@ Ces messages sont utilisés comme suit : send($q$, M$^i_{avail}$); \end{lstlisting} +\newpage + \begin{lstlisting}[caption={Pair $p$ envoyant à $q$ la demande de preuve \textsf{Challenge($i$)}}] challenges[$q$] = challenges[$q$]$\oplus${$i\rightarrow$ WAITING}; let M$^i_{challenge}$ = Challenge($i$); @@ -276,6 +320,7 @@ La requête est sauvée en attendant la réponse du pair questionné. challenge[$q$] = challenge[$q$]$\oplus${$i\rightarrow$ WRONG}; end if \end{lstlisting} + La vérification de la preuve est assez similaire à la vérification effectuée au moment de la réception de la pulsation : il faut vérifier la consistance de la branche, mais également que le jeton du pair $p$, \textsf{S$^i_p$} est cohérent avec le hash signé par la racine, \textsf{S$^i_{pulse}$}. \section{Analyse} @@ -313,7 +358,7 @@ En effet, le test 2 nous assure que S$^i_{p}$ a été calculé par $p$. De plus, Par récurrence : -\item le test 1 et l'intégrité du serveur nous assurent que branch$^i$[0] a été calculée avant $t_i + T_i$. En effet, le serveur commence à diffuser branch$^i$[0] à l'instant $t_i+T_i$. +\item Le test 1. et l'intégrité du serveur nous assurent que branch$^i$[0] a été calculée avant $t_i + T_i$. En effet, le serveur commence à diffuser branch$^i$[0] à l'instant $t_i+T_i$. \item Supposons que les tables branch$^i$[0] à branch$^i$[k] aient été calculées avant $t_i+T_i$. Nous savons par le test 3. que $t=$hash(branch$^i$[k+1])$\in$ branch$^i$[k]. Supposons alors par l'absurde que $m=$branch$^i$[k+1] ait été calculée après l'instant $t_i+T_i$ par un certain pair $q$. Alors, étant donné $t$, $q$ a été capable de calculer $m$ tel que hash($m$)$=t$ ce qui serait une attaque contre la première préimage et contredit l'hypothèse faite sur la fonction de hachage. \paragraph{Conclusion} Les deux première étapes de la preuve et le test 4 nous assurent donc que S$^i_{p}$ a été calculé par $p$ après $t_i$ et transmis avant $t_i+T^i$. Donc $p$ a communiqué avec au mois un pair pendant la ronde $i$ pour lui transmettre S$^i_p$, ce qui prouve le résultat annoncé. @@ -325,15 +370,53 @@ Malheureusement nous n'avons pas du tout la garantie que le pair $p$ ait respect \section{Simulation} -N'ayant pas à ma disposition de réseau pair-à-pair de grande échelle, j'ai choisi de réaliser un simulateur de réseau pair-à-pair : il s'agit d'un programme permettant de tester l'efficacité du protocole sur un grand nombre de nœuds (ici 40000). La simulation effectuée est plutôt haut niveau car elle ne simule pas l +N'ayant pas à ma disposition de réseau pair-à-pair de grande échelle, j'ai choisi de réaliser un simulateur de réseau pair-à-pair : il s'agit d'un programme permettant de tester l'efficacité du protocole sur un grand nombre de nœuds (ici 40000). La simulation effectuée est haut niveau : chaque nœud est un élément d'un tableau et peut communiquer instantanément avec les autres nœuds. En particuler, le protocole de communication sous-jacent (IP dans la pratique) n'est pas reproduit. + \subsection{Modélisation de la présence des pairs} -Plusieurs analyes (REFERENCE) ainsi que des analyses que j'ai faites sur des traces de réseaux pair-à-pair réels montrent que la durée des sessions (périodes durant laquelle un pair est connecté) peut être modélisée par une loi géométrique. J'ai donc choisi de modéliser la présence des pairs par une chaine de Markov à deux états, ON et OFF. La matrice de transition de la chaine est entièrement déterminée par deux paramètres, $\lambda$ et $\mu$, respectivement la probabilité de passer de OFF à ON et de OFF à ON. Il est immédiat que la durée d'une session (temps passé dans l'état ON) suit une loi géométrique de paramètre $\mu$. De plus il est connu que les fraction du temps passé dans l'état ON et OFF sont les inverses de la probabilité stationnaire de la chaine : + +Plusieurs analyes (REFERENCE) ainsi que des analyses que j'ai faites sur des traces de réseaux pair-à-pair réels montrent que la durée des sessions (périodes durant laquelle un pair est connecté) peut être modélisée par une loi géométrique. J'ai donc choisi de modéliser la présence des pairs par une chaine de Markov à deux états, ON et OFF. La matrice de transition de la chaine est entièrement déterminée par deux paramètres, $\lambda$ et $\mu$, respectivement la probabilité de passer de OFF à ON et de OFF à ON. Il est immédiat que la durée d'une session (temps passé dans l'état ON) suit une loi géométrique de paramètre $\mu$ (et donc d'espérance $\frac{1}{\mu}$). De plus il est connu que les fractions du temps passé dans l'état ON et OFF sont les probabilités de la loi stationnaire associée à la chaîne : + +\begin{displaymath} +t_{OFF} = \frac{\mu}{\lambda + \mu} \qquad t_{ON} = \frac{\lambda}{\lambda + \mu} +\end{displaymath} + +$t_{ON}$ est la fraction du temps passée dans l'état ON, c'est-à-dire la disponibilité du pair telle que définie en introduction. Pour un pair donné, les deux paramètres $\lambda$ et $\mu$ peuvent donc être choisis de la façon suivante : on fixe l'espérance du temps de session $E$, et la disponibilité du pair $d$ et on résout le système : + +\begin{displaymath} +E = \frac{1}{\mu} \qquad d = \frac{\lambda}{\lambda + \mu} +\end{displaymath} + \subsection{Construction du réseau} +Comme mentionné plus haut, \emph{Pacemaker} peut être utilisé au-dessus d'un réseau pair-à-pair déjà existant, ou comme un service indépendant. Dans ce cas, c'est au protocole qu'il incombe de construire et maintenir les connections entre les pairs. Le protocole choisi dans cette simulation est relativement simple. Chaque nœud du réseau à un de gré égal à 10, c'est-à-dire qu'il peut établir au plus 10 connections avec d'autres pairs du réseau (ce qui semble raisonnable au vu des applications pratiques). Au moment où le pair se connecte, il envoie un message \textsf{Mesh} à la racine. Celle-ci accepte le pair si elle a une place vacante, et envoie au pair la liste de ses fils dans le réseau. Le pair contacte alors les fils en envoyant à chacun un message \textsf{Mesh}. Si le nœud contacté a une place vacante, il accepte le pair, sinon il lui indique un pair choisi au hasard parmi ses fils. Le processus est répeté jusqu'à que le pair ait 10 voisins. + +Le but de ce processus d'insertion est d'avoir un faible rayon par rapport à la racine (cf. REFERENCE), et ainsi permettre une diffusion rapide des messages au cours des rondes. À noter également que le réseau ainsi obtenu est redondant au sens suivant : il existe plusieurs chemins allant d'un nœud à la racine. Ceci est capital pour assurer la robustesse du protocole en cas de déconnection des pairs. + +\begin{center} +\begin{figure}[h] +\includegraphics[scale=0.6]{mesh.eps} +\caption{Rėpartition des pairs dans le réseau. Pour 100,000 pairs, la distance maximale à la racine est de 7.} +\end{figure} +\end{center} + +Une optimisation consiste à arrêter le processus de recherche de voisins à partir d'un certain seuil. L'effet recherché est d'éviter les pairs déjà présent de consistuer des cliques, qui rendrait l'insertion de nouveaux pairs trés difficile. Les tests effectués au cours de la simulation montrent que pour un degré 10, le seuil de 8 (c'est-à-dire qu'un pair stoppe le processus de recherche dès qu'il est connecté à 8 voisins) semble réaliser un bon compromis entre connectivité suffisante et facilité d'insertion. En effet, dans les simulations effectuées, tous les nœuds trouvent au moins un voisin en moins de trois itérations du processus d'insertion dans le réseau. + \subsection{Résultats} +Le simulateur a été écrit en OCaml. Le code final comprend environ 800 lignes, dont 250 pour les définitions des types et des modules servant à représenter les pairs, 150 pour l'implémentation du protocole en lui-même, 70 pour la construction du réseau, 70 pour la simulation de connection des pairs, 150 pour la simulation des actions des pairs, le reste étant les fonctions générales d'entrée/sortie et la journalisation des données. + +La simulation a été effectuée pour 40000 nœuds, sur une période simulée de 10 jours. Le simulateur procéde par itérations successives : à chaque itération, chaque pair traite l'ensemble des messages qu'il a reçus au cours de l'itération précédente conformément à la spécification du protocole. Chaque itération simule une période de 20 secondes, en particulier, les messages envoyés ne sont reçus que 20 secondes plus tard, ce qui est pessimiste comparé à la réalité. + +La disponibilité des pairs a été choisie uniforme sur l'intervalle $[0, 1]$, et la durée moyenne de connection en minutes uniforme sur l'intervalle $[20, 500]$. Les résultats obtenus figurent ci-dessous : + +IMAGE + \section{Implémentation} +L'implémentation réelle a également été écrite en OCaml et comprend envrion 800 lignes de code, dont 250 pour les déclarations de type, 200 pour le protocole lui-même, 150 pour la construction du réseau, le reste étant les fonctions générales d'entrée/sortie et appels systèmes. Le protocole de communication utilisé est UDP et le protocole de construction du réseau est celui décrit en REFERENCE. + +Le déploiement a été fait sur PlanetLab, un réseau d'ordinateurs mis en commun par différentes institutions et universités à travers le monde. Je n'ai malheureusement pu avoir accés qu'à 161 ordinateurs du réseau. Le nombre d'ordinateurs connectés en même temps a varié entre 139 et 161 au cours de l'expérimentation qui a duré 19 jours. + \section{Conclusion, application à la signature de documents} \end{document}
\ No newline at end of file |