Les standards pour les réseaux sans fil a forts besoins de trafic

Télécharger le fichier pdf d’un mémoire de fin d’études

Les standards pour les réseaux sans fil a forts besoins de trafic

La problématique de l’énergie touche tous les types de réseaux, cependant certaines applications sont plus préoccupées par d’autres critères de qualité de service (débit, delai, gigue, couverture). C’est le cas des réseaux mobiles, véhiculaires, locaux, ou encore multimédias.
L’alliance WiMedia est parvenue `a standardiser le domaine des r´eseaux personnels `a haut d´ebit l`a o`u l’IEEE 802.15.3a s’est essou✏´ee. Elle d´eveloppe un standard pour des communications a 3,1 GHz et 10,6 GHz pour des d´ebits allant de 53,3 `a 1024 Mb/s. Sa synchronisation fine o↵re également des propri´et´es d’´evaluation de distance entre les ´equipements. Ce sont les standards IEEE 802.11 qui structurent le domaine des r´eseaux locaux sans fil, l’alliance WiFi se base essentiellement sur ces normes. En mode infrastructure, une station se connecte de point d’acc`es en point d’acc`es (ou BSS pour Basic Service Set) au sein d’un mˆeme ESS (Extended Service Set). Un mode pair-`apair existe ´egalement. Un grand nombre d’amendements a ´et´e apport´e afin de couvrir : une augmentation du d´ebit (n), la gestion de la qualit´e de service (e), ou encore les r´eseaux v´ehiculaires (p). Le standard actuel IEEE 802.11-2012 regroupe une partie de ces amendements. Il poss`ede d´ej`a cinq amendements dont le plus connu est celui de 2013 (ac) qui porte son d´ebit maximum `a 1300Mb/s pour une port´ee de 70 `a 250 m`etres selon l’environnement (int´erieur ou espace libre).
Enfin, la bataille du haut d´ebit pour les r´eseaux mobiles et m´etropolitains 4G-LTE semble avoir ´et´e gagn´ee par les standards du groupe 3GPP au profit de ceux du forum Wimax. La communaut´e r´efl´echit d´ej`a `a la 5G dont l’enjeu principale est la densification massive du r´eseau. `A ce titre, les ondes millim´etriques sont envisag´ees, mais `a 60GHz, la  ´ealisation du moyen de transmission constitue un verrou technologique. S’il est difficile d’ˆetre exhaustif sur le domaine, ce tour d’horizon rapide montre combien les technologies radio sont diverses, avec des sch´emas de communication di↵´erents des r´eseaux filaires. On pourra ´egalement garder un oeil sur des technologies compl`etement alternatives comme des techniques de modulation `a bande ´etroite [58], le Lifi [59], ou encore la modulation du champ ´electromagn´etique ambiant [60].

Un modèle de supervision pour l’Internet des objets

Comme nous l’avons constat´e dans les sections pr´ec´edentes, la mesure et la supervision des r´eseaux sont n´ecessaires `a leur bonne ´evolution et `a leur bon fonctionnement. Ce sont des proc´ed´es qui d’une part permettent d’adapter les standards aux nouveaux besoins de communication, mais c’est ´egalement une phase primordiale en terme d’autonomie des syst`emes. Nous avons aussi vu que les communications sans fil repr´esentent une part importante des technologies de communication. Ce type d’acc`es `a l’information change la donne dans le domaine de la supervision pour plusieurs raisons :
— Les noeuds sont mobiles et la topologie du graphe de communication peut ´evoluer fortement au cours du temps.
— Les besoins applicatifs se diversifient, au mˆeme titre que les ressources disponibles pour chaque noeud.
— L’acc`es `a de nouvelles m´etriques environnementales et sociales est devenu possible.
— L’acc`es `a de nouvelles m´etriques physiques sur le m´edium est devenu n´ecessaire.
— Les piles protocolaires se complexifient et se sp´ecialisent.
— Le trafic au niveau des liens d’acc`es d´epend de ph´enom`enes tr`es locaux.
Afin de prendre en consid´eration ces changements, nous proposons d’int´egrer le maximum de technologies dans l’infrastructure de supervision de nos futurs syst`emes de communication. Pour ce faire nous devrons composer avec les di↵´erentes capacit´es et les attentes de chacun des ´equipements depuis la plus petite puce RFID jusqu’au serveur de calcul. L’architecture devra donc ˆetre modulaire et int´egrer les objets du quotidien.

Intégrer l’objet lambda : lorsque le contexte devient une métrique

L’interconnexion des objets du quotidien est souvent laiss´ee pour compte, car le fait d’ˆetre connect´e ne leur donne pas une valeur ajout´ee imm´ediate. C’est e↵ectivement le cas si l’on consid`ere qu’un objet communique uniquement pour am´eliorer ses propres fonctionnalit´es. N´eanmoins, un objet peut communiquer pour assister ses voisins, par exemple en signalant simplement sa pr´esence et en partageant les mesures dont il a la connaissance. En enrichissant les m´etriques, il est possible de migrer peu `a peu d’un simple d´elai, vers une m´etrique plus complexe telle qu’un contexte de communication.
Premi`erement, ´echanger sur le contexte permet de mutualiser certaines ressources de calcul. Par exemple un ´emetteur radio n’aurait pas besoin d’inf´erer les bandes de fr´equences libres si son plus proche voisin poss`ede d´ej`a l’information. Deuxi`emement, en permettant aux objets de mesurer leur contexte, nous leur permettons de mieux r´epondre `a nos besoins : lorsque nous nous promenons dans la rue, nous sommes en permanence inform´es par de la signalisation, des panneaux publicitaires, des post-it, etc. Nos terminaux mobiles pourraient faire de mˆeme en balayant par exemple des ´etiquettes RFID.
Enfin la motivation sans doute la plus actuelle, est de pouvoir analyser le fonctionnement de notre soci´et´e en fouillant une masse de donn´ees issue de ces mesures. Les objets qui nous entourent ´etant la plupart du temps le reflet de nos vies, les observer peut alors s’av´erer ˆetre pertinent. Avant d’atteindre ce stade, nous pourrons sans doute mieux comprendre le fonctionnement de nos syst`emes en terme de performance. Dans le cas des r´eseaux, le trafic g´en´er´e par un noeud d´epend de son contexte d’utilisation. Surveiller le changement de contexte pour chaque noeud peut permettre `a un op´erateur de mieux pr´edire le trafic `a venir et de mieux comprendre le comportement de son infrastructure.
Une telle d´emarche passe par une bonne formalisation du contexte et de ses m´etriques, un partage efficace de ces informations, et enfin des outils d’analyse permettant de faire le lien entre la performance (notion que nous d´efinirons) et les mesures e↵ectu´ees.

Une architecture modulaire adaptable `a des ressources h´et´erog`enes

De par l’´etude que nous avons men´ee jusqu’`a pr´esent, nous avons d´egag´e plusieurs grandes taches autour de la mesure :
1. l’acquisition
2. la synchronisation des horloges
3. la repr´esentation et le stockage
4. la di↵usion et le partage efficace
5. l’analyse
En fonction des besoins de mesures et des ressources disponibles, les fonctionnalit´es pr´ec´edemment d´ecrites pourront avoir des impl´ementations tr`es di↵´erentes. Les param` etres impactant grandement les choix de solutions sont :
a. la granularit´e de l’information
b. la pr´ecision temporelle des mesures
c. la topologie du r´eseau
d. les destinataires de l’information
e. la capacit´e d’analyse et de stockage des noeuds
Par exemple, le cas d’une campagne de mesure sur un r´eseau fixe, dont les r´esultats seront exploit´es a posteriori par une seule machine di↵`ere totalement d’une op´eration de supervision de r´eseau mobile sans fil pour laquelle chacun des noeuds doit ˆetre inform´e en temps r´eel de l’´etat du r´eseau. Pour pouvoir faire face `a des situations aussi di↵´erentes tout en gardant un bon niveau de compatibilit´e, nous nous appuierons sur ce qui a fait la r´eussite des mod`eles de communication actuels : une conception modulaire.
Les fonctionnalit´es ´enonc´ees peuvent ˆetre s´epar´ees en di↵´erents services. L’impl´ementation d’un service peut ˆetre sp´ecialis´ee pour r´epondre `a un besoin particulier. En associant plusieurs services, nous serons `a mˆeme de construire la solution de mesure ou de supervision adapt´ee `a la situation. L’architecture que nous proposons est structur´ee comme dans la figure 2.1.

Travaux similaires

Le probl`eme de la mesure distribu´ee dans lequel un ensemble de mesures sont agr´eg´ees et transmises `a un sous-ensemble de noeuds est globalement motiv´e par deux types de travaux. Les premiers du genre, issus de la supervision des r´eseaux, cherchent `a v´erifier l’´etat d’un ensemble de machines afin de s’assurer de leur bon fonctionnement. Les seconds sont issus du domaine des r´eseaux de capteurs sans fil qui communiquent des mesures physiques afin de caract´eriser un environnement. Si les hypoth`eses de travail sont souvent di↵´erentes, dans les deux cas, le probl`eme est similaire. Certains noeuds du r´eseau sont `a la recherche d’un consensus et souhaitent converger vers un r´esum´e de leurs ´etats. `A ces fins, l’´etat de l’art propose di↵´erentes solutions algorithmiques, mais aussi des ´etudes plus formelles issues de la th´eorie du contrˆole. Cette section vise `a couvrir ces di↵´erents aspects .

Arbre de communication et supervision

Une partie des solutions existantes traitent de cas o`u la topologie du r´eseau est relativement statique. Ils s’adaptent aussi bien `a des r´eseaux filaires que des r´eseaux sans-fil dans la mesure o`u la topologie ´evolue peu au cours du temps (noeuds fixes et liens fiables). Le principe repose sur l’organisation du r´eseau en un arbre afin d’optimiser le transfert de l’information. Il existe di↵´erents sch´emas de communication pour couvrir divers types de besoins. Un point di↵´erenciant va ˆetre le nombre de superviseurs.

Algorithmes asynchrones et mod`eles ´epid´emiques

Lorsque la constitution d’un arbre n’est pas possible ou est jug´ee trop coˆuteuse, il est possible d’organiser le monitoring du r´eseau sans aucune hi´erarchie, notamment en utilisant un mod`ele ´epid´emique (ou protocole gossip). Ce type de protocole tient son nom de la fa¸con dont une information ou un virus a tendance `a se propager au sein d’un r´eseau de personnes. Lorsqu’un noeud du r´eseau poss`ede une information, il la communique de mani`ere spontan´ee `a un (ou plusieurs) de ses pairs. Au bout d’un certain temps, l’information a atteint tous les noeuds ou bien est devenue obsol`ete. Comme illustr´e dans la figure 3.3. Le comportement de ce type de mod`ele est ´etroitement li´e `a ceux des chaines de Markov et des marches al´eatoires. De nombreux travaux utilisent ces protocoles [72– 76]. Ils rentrent n´eanmoins tous dans le cadre algorithmique propos´e par [77] et [78] illustr´es dans les Algorithmes 1, 2 et 3 que nous avons volontairement simplifi´es.

Mod´elisation alg´ebrique de la couche de partage

Dans la section pr´ec´edente, nous avons vu di↵´erentes techniques pour r´esoudre un probl`eme de supervision dans lequel un ensemble de noeuds doit obtenir un r´esum´e des informations mesur´ees sur le r´eseau. Ces techniques sont adapt´ees `a di↵´erents cas de figure selon si le r´eseau est dynamique ou statique, avec ou sans infrastructure, ou encore respectant ou non une certaine hi´erarchie. Dans cette section, nous proposons un cadre alg´ebrique inspir´e de celui du consensus permettant de formaliser et de comparer ces diverses techniques de supervision et de mesure distribu´ees.

Le mod`ele de communication

Que ce soit dans le cas d’une organisation en arbre, d’un algorithme ´epid´emique asynchrone ou d’un algorithme de consensus synchrone, il est possible de d´ecrire la situation par le mˆeme mod`ele alg´ebrique. Nous consid´erons un graphe G = (N, E) pour un ensemble N = [1, n] de n noeuds (ou agents) et un ensemble E 2 N2 d’arˆetes. Une arˆete mat´erialise la possibilit´e pour le noeud j de recevoir une information de mesure du noeud i. Il est important de noter que le graphe de communication dont nous parlons est le graphe de communication au niveau des agents de mesure. Ce graphe peut reposer sur un r´eseau de communication d´ej`a existant et dans ce cas ˆetre consid´er´e comme un sur-r´eseau (ou r´eseau overlay). Dans le cas d’une topologie dynamique, le graphe de communication ´evolue au cours du temps (avec la mobilit´e des agents par exemple). Certains agents pouvant communiquer `a un instant donn´e peuvent potentiellement ne plus se joindre `a l’instant suivant, alors que de nouveaux liens de communication peuvent apparaitre. Nous consid´ererons que l’ensemble des liens peut changer au cours du temps alors que l’ensemble des noeuds reste inchang´e, ainsi, G(t) = (N, E(t)) d´esigne le graphe du r´eseau `a l’instant t. Toutefois, si N est constant, nous pouvons toujours mod´eliser l’arriv´ee d’un noeud en ajoutant des arˆetes `a un noeud isol´e, et le d´epart d’un noeud en enlevant ses arˆetes incidentes. Sauf mentionn´e explicitement, les graphes que nous consid´erons sont des graphes simples (sans boucle ni arˆetes multiples).
Nous d´esignons par xi 2 I la mesure du noeud i et x 2 In le vecteur de mesure dans le graphe. Dans le cas d’une mesure ´evoluant dans le temps, xi(t) 2 I d´esigne l’´echantillon de i au temps t 2 R. Nous mod´elisons une op´eration de mesure distribu´ee par une fonction f : In ! In qui associe au vecteur x de mesure un vecteur image : y = f(x). Suite `a l’op´eration de mesure, chaque noeud i poss`ede une image yi du r´eseau. Cette image d´epend des mesures de chaque noeud et de la fonction f d´efinie par un administrateur.

D´ecomposition du probl`eme en di↵´erents services

Pr´ec´edemment, nous avons vu que pour un r´eseau fixe il est pr´ef´erable de suivre une organisation en arbre et que lorsque la construction d’un arbre ´etait trop coˆuteuse, une approche de type gossip ou consensus devait ˆetre privil´egi´ee. Il sera donc n´ecessaire de composer di↵´erentes strat´egies en fonction des propri´et´es du r´eseau sous-jacent. Une architecture de mesure distribu´ee devra donc ˆetre modulaire.
Afin de pouvoir participer `a une op´eration (ou campagne) de mesure, les agents doivent pouvoir ˆetre capables de r´ealiser trois grandes tˆaches qui consistent `a :
— Transmettre leur mesure `a d’autres agents
— D´ecomposer f (et dans notre cas 11T n ) en un produit de matrice
— E↵ectuer le calcul d’une combinaison lin´eaire de mesures.
En terme de conception orient´ee objet, nous avons r´eparti ces tˆaches au sein de deux interfaces de services s’articulant autour d’une classe de donn´ee appel´ee Mesure. Nous nommerons les interfaces de services respectivement Transport, et Distribution. Chacune de ces interfaces peut poss´eder di↵´erentes strat´egies d’impl´ementations afin de s’adapter au mieux `a la technologie de communication et au r´eseau sous-jacent.

Heuristiques sym´etriques et le paradoxe de l’´etoile

Le d´efi lors de la construction d’une nouvelle heuristique est de lui donner un pouvoir de contraction meilleur que ses concurrentes, tout en se basant sur des informations acquises localement. Comparer deux heuristiques n’est pas trivial. Une heuristique peut avoir un meilleur pouvoir de contraction qu’une autre sur un graphe donn´e sans pour autant la dominer (il existe un graphe pour lequel l’autre heuristique a un meilleur pouvoir de contraction). Intuitivement, on peut dire qu’une heuristique est adapt´ee `a certains types de graphes. Comme nous l’avons vu, il existe un lien ´etroit entre le spectre d’un graphe et le poids constant optimal (BCW). Pour les mˆemes raisons, une heuristique ne tenant pas compte de ce spectre lui sera plus ou moins adapt´ee. Trouver une bonne heuristique revient `a trouver un moyen pratique et simple de calculer le poids wij(= wji) que deux noeuds voisins i et j s’attribuent respectivement. Pour cette raison nous focalisons notre int´erˆet sur l’heuristique MW qui d´efinit sa pond´eration sur la base de son voisinage local seulement. En d´epit de bonnes performances globales, on peut remarquer que l’heuristique MW se comporte de mani`ere contre-intuitive vis-`a-vis des noeuds dont le degr´e est bien sup´erieur `a ceux de leurs voisins. En e↵et, plus le degr´e d’un noeud est ´elev´e, plus celui-ci a acc`es `a de l’information, et moins celui-ci re¸coit d’importance de la part de ses voisins (voir table 3.1). Pour illustrer ce ph´enom`ene particulier, nous utilisons le cas extrˆeme qui est la topologie en ´etoile. La figure 3.14 illustre la pond´eration MW pour un tel graphe de 5 noeuds.

D´découpler contrôle de congestion et ordonnancement

Dans cette section, nous montrons qu’il est possible d’ordonnancer les segments d’un ensemble de mesures ou flux applicatifs partageant la mˆeme route, sans modifier la bande passante qu’une impl´ementation standard de TCP aurait acquise. Dans ce qui suit, nous utiliserons le terme tcp pour faire r´ef´erence `a une impl´ementation standard du protocole, sans tenir compte d’une version sp´ecifique.

Une premi`ere intuition

Afin de mieux ´etablir la notion d’ordonnancement non intrusif par route nous proposons l’exemple illustr´e par la figure 4.1. Dans cet exemple, deux stations sources communiquent avec deux stations destinations di↵´erentes et partagent un mˆeme goulot d’´etranglement. La premi`ere station transf`ere une mesure (flux 1) d’une taille de 40 unit´es de donn´ees. Pour l’exp´erience, la seconde station transf`erera deux mesures (flux 2 et 3) respectivement de taille 15 et 4 unit´es. Le goulot d’´etranglement ne peut transmettre que 2 unit´es de donn´ees par unit´e de temps et les sources d´emarrent de mani`ere s´equentielle (1, 2 puis 3). Pour l’illustration nous n´egligerons les phases de contrˆole de congestion. Dans le cas de TCP, `a l’arriv´ee de chaque flux, la bande passante est divis´ee et une part ´egale est donn´ee `a chaque flux. Cette situation est illustr´ee dans le cadre sup´erieur droit. Une premi`ere erreur serait d’ordonnancer les flux applicatifs de la station 2 au travers d’une seule socket, c’est le cas illustr´e dans le cadre inf´erieur gauche. En e↵et, la bande passante acquise par la source 2 diminue avec le nombre de flux g´en´er´es par la source 1 utilisant le goulot d’´etranglement. Au contraire, un ordonnancement non intrusif par route est illustr´e dans le cadre inf´erieur droit de la figure 4.1. Comme on peut le constater, la bande passante allou´ee au flux 1 est inchang´ee tout le long de son transfert. N´eanmoins, nous avons transf´erer la mesure 3 avant la mesure 2 ce qui a r´eduit le temps moyen de transfert pour la source 2.

Table des matières

1 Introduction générale 
1.1 Motivations
1.2 Positionnement et contributions
1.3 Structure du manuscrit
2 Contexte et problématique 
2.1 Perspective générale
2.1.1 Un bref historique d’Internet
2.1.2 Une estimation des années a venir
2.2 Mesure distribuée et supervision des réseaux
2.2.1 Métrique, m´méthodologies et outils standards
2.2.2 Plateforme et architectures
2.2.3 Techniques d’analyse et de supervision
2.3 Internet des Objets et radiocommunications
2.3.1 Architecture des liaisons de communication sans fil
2.3.2 Les acteurs de l’Internet des Objets et leurs standards
2.4 Un mod`ele de supervision pour l’Internet des objets
2.4.1 Int´egrer l’objet lambda : lorsque le contexte devient une m´etrique
2.4.2 Une architecture modulaire adaptable `a des ressources h´et´erog`enes
3 Agr´egation et di↵usion des mesures dans un r´eseau
3.1 Motivation
3.2 Travaux similaires
3.2.1 Arbre de communication et supervision
3.2.2 Algorithmes asynchrones et mod`eles ´epid´emiques
3.2.3 Algorithmes synchrones et consensus
3.3 Mod´elisation alg´ebrique de la couche de partage
3.3.1 Le mod`ele de communication
3.3.2 Pr´ecision d’une mesure
3.3.3 Coˆut d’une mesure
3.3.4 Latence d’une mesure
3.4 Cas d’´etudes
3.4.1 Topologie compl`ete et superviseur unique
3.4.2 Topologie en arbre et traitement dans le r´eseau
3.4.3 Topologie mobile et superviseurs multiples
3.5 D´ecomposition du probl`eme en di↵´erents services
3.5.1 La classe de Mesure
3.5.2 Service de Distribution
3.5.3 Service de Transport
3.6 Une nouvelle heuristique pour le consensus de la moyenne
3.6.1 Heuristiques sym´etriques et le paradoxe de l’´etoile
3.6.2 Comparaison des pouvoirs de contraction
3.7 Importance des conditions initiales
3.7.1 La d´eviation standard des mesures
3.7.2 Assortativit´e des mesures et biais d’´echantillonnage
3.8 Conclusion et r´esum´e des contributions
4 Non-intrusivit´e et ordonnancement des mesures sur un lien 
4.1 Motivations
4.2 Travaux similaires
4.3 D´ecoupler contrˆole de congestion et ordonnancement
4.3.1 Une premi`ere intuition
4.3.2 Une Approche algorithmique : maintenir l’´etat de bu↵ers virtuels
4.3.3 Conditions de faisabilit´e d’un ordonnancement arbitraire
4.4 Ordonnancement par taille de flux : optimalit´e de politiques
4.4.1 ´Equivalence avec un serveur `a capacit´e variable dans le temps
4.4.2 Politiques d’ordonnancement
4.4.3 R´esultat d’optimalit´e
4.5 Quelques consid´erations techniques
4.5.1 Les possibilit´es d’ordonnancement du trafic
4.5.2 La capacit´e des bu↵ers
4.5.3 L’interface de programmation et option TCP
4.5.4 La taille des segments
4.5.5 Absence de pertes et de d´es´equencement
4.6 Impl´ementation et r´esultats exp´erimentaux
4.6.1 SCHED TCP, une impl´ementation de gtcp
4.6.2 R´esultats exp´erimentaux et comparaison de politiques
4.7 Conclusions et travaux futurs
5 ´Evaluation et analyse distribu´ee de la performance 
5.1 Motivations
5.2 Mod´elisation et ´evaluation des syst`emes distribu´es
5.2.1 Agent et utilit´e
5.2.2 Syst`eme multi-agents et performance
5.2.3 Observations et contexte
5.3 ´Evaluation distribu´ee de la performance dans les r´eseaux dynamiques
5.3.1 Estimation param´etrique et non param´etrique de densit´e de probabilit
5.3.2 Estimation d´ecentralis´e d’une distribution `a temps variable
5.4 Cas d’´etudes
5.4.1 Mesure du contexte et de la performance
5.4.2 Analyse de flux d’observation
5.5 Conclusion
6 Conclusion et perspectives 
6.1 Rappel du contexte
6.2 M´ethodologie et approche adopt´ee
6.3 R´esum´e des contributions
6.4 Pistes de recherches et derni`eres remarques
A Heuristiques non paracontractante et topologies cyclique
B Compl´ement du chapitre 5

Télécharger le rapport complet