ROSA: Un Réseau de Recouvrement Adaptable, Auto-Organisant et Extensible

Récemment, il est devenu possible de faire tourner un système d’exploitation sur une architecture matérielle pour laquelle il n’était pas destiné. Cette technologie s’appelle la virtualisation. La virtualisation fait tourner chacun des OS invités dans un environnement fermé. Ces environnements virtualisés sont gérés par la couche de virtualisation qui doit être implémentée pour beaucoup de systèmes hôtes. Il doit également être en mesure d’exécuter un grand nombre d’OS. Par conséquent, la virtualisation peut se décomposer en trois couches, la couche host (ou la couche physique), la couche de virtualisation et de la couche guest.

Ce concept de virtualisation peut également être appliqué aux réseaux. Aujourd’hui, il existe une grande disparité dans les réseaux: Internet, le réseau GSM, les réseaux ad hoc, etc. Chacun de ces réseaux est basé sur différents supports physisques et différents protocoles. Il serait intéressant d’avoir un réseau virtuel qui unifie tous ces réseaux. En outre, la convergence des appareils électroniques numériques facilite le développement d’un tel réseau virtuel. En effet, les appareils, tels que les téléphones de nouvelle génération, sont à cheval sur plusieurs réseaux physiques (IP, WiFi et GSM/GPRS) et peuvent servir de passerelles entre ces différents réseaux physiques. Le modèle de ce réseau virtuel global est definit en trois couches: la couche physique, la couche virtuelle, et la couche de services. La couche physique est un ensemble de réseaux physiques et les différents dispositifs qui les composent. La couche virtuelle est un réseau virtuel construit au-dessus de ces réseaux physiques ainsi que l’interfaçage avec chacun de ces réseaux. La couche de services consiste en un ensemble de services fournis au dessus du réseau virtuel. Les services peuvent être des services de routage résilient, services de stockage fiable .

Une des principale conditions qu’un tel réseau virtuel doit respecter est l’extensibilité. Si l’on considère que beaucoup de dispositifs sont susceptibles de participer, il faut que le trafic supplémentaire généré soit le plus bas possible et si possible que ce traffic ne dépende pas du nombre de participants. Le réseau virtuel doit également avoir les mêmes qualités (résistance, etc.) que les réseaux sur lesquels il est déployé. Pour finir, ce réseau virtuel doit être facilement adaptable à un grand nombre de réseaux physiques différents.

Les réseaux de recouvrement sont de très bons candidats pour être utilisé comme un réseau virtuel. Un réseau overlay est un réseau construit sur un autre réseau. Pour chaque nœud du réseau overlay correspond un nœud du réseau sous-jacent. Ces réseaux de recouvrement ont été popularisés par les réseaux pair-à-pair dans les années 2000. Il existe de nombreux types de réseaux de recouvrement, certains sont extensibles, certains assurent une topologie résiliente, certains offrent un service d’acheminement fiable, etc. Néanmoins, aucun de ces réseaux existants ne peut être utilisé pour être le réseau virtuel, puisque ces réseaux sont généralement dédiés à un seul service et ne peuvent être déployées que sur un seul type de réseau physique. Afin d’utiliser un réseau de recouvrement en tant que réseau virtuel, celui-ci doit être facilement adaptable à un grand nombre de réseaux physiques différents et proposer de nombreux services. C’est suite à ces observations, que les objectifs de cette thèse ont été définis:
• concevoir et construire un réseau de recouvrement adaptable et facile à déployer sur de nombreux types des réseaux physiques;
• proposer un ensemble de services au dessus de ce réseau de recouvrement.

Les nœuds de ROSA sont organisés en clusters appelés grumeaux. Un grumeau est un ensemble de noeuds entièrement connectés. En théorie des graphes de tels objets sont appelés cliques. Une clique dans un graphe non orienté est un sous-ensemble de l’ensemble des sommets, tel que pour chaque pair de sommets du sous-ensemble, il existe une arête reliant les deux sommets. ROSA peut être représenté par un enchevêtrement de grumeaux. Chaque noeud de ROSA appartient à au moins un des grumeaux. A chacun des grumeaux de ROSA est associé une mesure appelée densité. Il y a plusieurs types de densités et c’est le choix de cette densité qui définit les caractéristiques de ROSA.

Chaque nœud de ROSA a un identifiant, une liste des voisins et une liste de grumeaux. L’identifiant d’un nœud est un entier appartenant à [1, 2¹²⁸ − 1]. Nous considérerons pour l’instant, que l’identificateur d’un nœud est choisi au hasard. La liste des grumeaux d’un nœud est une liste de grumeaux auquel le nœud appartient. La liste des voisins d’un nœud est une liste des identifiants et des adresses physiques des noeuds auxquels il est lié. Chaque noeud possède aussi un indicateur ’connecté’. Cet indicateur est défini à true si le noeud est connecté à ROSA et mis à false sinon. Pour compléter la représentation d’un nœud nous ajoutons une liste de grumeaux de faible densité et une liste des identificateurs des derniers messages reçus. Ces deux listes sont initialisées à vide. La premiere sera utilisée pour stocker la connaissance que chaque noeud a à propos des grumeaux de faibles densités dans son entourage. La seconde sera utilisée pour permettre à tous les nœuds d’un grumeau de recevoir un message, malgré les échecs de transmission .

Un voisin d’un nœud est représenté par le couple (id, phy) où id est l’identifiant de ce voisin dans ROSA et phy son adresse physique sur le réseau sur lequel ROSA est déployé. Un indicateur ’vivant’ complète cette représentation. Cet indicateur est défini sur true par défaut et sera utilisé pour la détection des pannes.

Un grumeaux possède un identifiant, la liste des identifiants des noeuds qui le composent et toutes les informations permettant à chacun de ces nœud de calculer sa densité. Les informations nécessaires pour calculer la densité dépendent de la définition de la densité choisie. L’identifiant d’un grumeau est un entier appartenant à [1, 2¹²⁸ − 1]. Un lump possède aussi une liste des adresses physiques des noeuds qui le composent.