3. Aperçu du protocole

Le but de cette section est de décrire RPL dans l'esprit de [RFC4101]. Les détails du protocole se trouvent dans les sections suivantes.

3.1. Topologies

Cette section décrit les topologies RPL de base qui peuvent être formées, et les règles par lesquelles elles sont construites, c'est-à-dire les règles régissant la formation du DODAG.

3.1.1. Construction de topologies

Les LLN, tels que les réseaux radio, n'ont généralement pas de topologies prédéfinies, par exemple, celles imposées par des fils point à point, de sorte que RPL doit découvrir des liens, puis sélectionner les pairs avec parcimonie.

Dans de nombreux cas, parce que les plages de la couche 2 ne se chevauchent que partiellement, RPL forme des topologies de réseau non transitives / à accès multiple sans diffusion (NBMA) sur lesquelles il calcule des routes.

Les routes RPL sont optimisées pour le trafic vers ou depuis une ou plusieurs racines qui agissent comme des puits pour la topologie. En conséquence, RPL organise une topologie sous la forme d'un graphe orienté acyclique (DAG) qui est partitionné en un ou plusieurs DAG orientés destination (DODAG), un DODAG par puits. Si le DAG a plusieurs racines, on s'attend alors à ce que les racines soient fédérées par une dorsale commune, telle qu'une liaison de transit.

3.1.2. Identifiants RPL

RPL utilise quatre valeurs pour identifier et maintenir une topologie :

• La première est un RPLInstanceID. Un RPLInstanceID identifie un ensemble d'un ou plusieurs DAG orientés destination (DODAG). Un réseau peut avoir plusieurs RPLInstanceID, chacun définissant un ensemble indépendant de DODAG, qui peuvent être optimisés pour différentes fonctions objectives (OF) et/ou applications. L'ensemble des DODAG identifiés par un RPLInstanceID est appelé une instance RPL. Tous les DODAG de la même instance RPL utilisent la même OF.

• La seconde est un DODAGID. La portée d'un DODAGID est une instance RPL. La combinaison de RPLInstanceID et DODAGID identifie de manière unique un seul DODAG dans le réseau. Une instance RPL peut avoir plusieurs DODAG, chacun ayant un DODAGID unique.

• La troisième est un DODAGVersionNumber. La portée d'un DODAGVersionNumber est un DODAG. Un DODAG est parfois reconstruit à partir de la racine DODAG, en incrémentant le DODAGVersionNumber. La combinaison de RPLInstanceID, DODAGID et DODAGVersionNumber identifie de manière unique une version DODAG.

• La quatrième est le rang (Rank). La portée du rang est une version DODAG. Le rang établit un ordre partiel sur une version DODAG, définissant les positions individuelles des nœuds par rapport à la racine DODAG.

3.1.3. Instances, DODAG et versions DODAG

Une instance RPL contient une ou plusieurs racines DODAG. Une instance RPL peut fournir des routes vers certains préfixes de destination, accessibles via les racines DODAG ou des chemins alternatifs au sein du DODAG. Ces racines peuvent fonctionner indépendamment ou peuvent se coordonner sur un réseau qui n'est pas nécessairement aussi contraint qu'un LLN.

Une instance RPL peut comprendre :

• un seul DODAG avec une seule racine

  • Par exemple, un DODAG optimisé pour minimiser la latence enraciné à un seul contrôleur d'éclairage centralisé dans une application domotique.

• plusieurs DODAG non coordonnés avec des racines indépendantes (DODAGID différents)

  • Par exemple, plusieurs points de collecte de données dans une application de collecte de données urbaine qui n'ont pas de connectivité appropriée pour se coordonner les uns avec les autres ou qui utilisent la formation de plusieurs DODAG comme moyen de partitionner le réseau de manière dynamique et autonome.

• un seul DODAG avec une racine virtuelle qui coordonne les puits LLN (avec le même DODAGID) sur un réseau dorsal.

  • Par exemple, plusieurs routeurs de bordure fonctionnant avec une liaison de transit fiable, par exemple, à l'appui d'une application de réseau personnel sans fil à faible puissance IPv6 (6LoWPAN), qui sont capables d'agir comme des interfaces logiquement équivalentes au puits du même DODAG.

• une combinaison de ce qui précède adaptée à un scénario d'application.

Chaque paquet RPL est associé à un RPLInstanceID particulier (voir section 11.2) et, par conséquent, à une instance RPL (section 5). Le provisionnement ou la découverte automatisée d'un mappage entre un RPLInstanceID et un type ou un service de trafic d'application est hors de portée de cette spécification (à définir dans de futures spécifications d'accompagnement).

La figure 1 illustre un exemple d'instance RPL comprenant trois DODAG avec les racines DODAG R1, R2 et R3. Chacune de ces racines DODAG annonce le même RPLInstanceID. Les lignes illustrent la connectivité entre les parents et les enfants.

La figure 2 illustre comment une incrémentation de DODAGVersionNumber conduit à une nouvelle version DODAG. Cette représentation illustre une incrémentation de DODAGVersionNumber qui aboutit à une topologie DODAG différente. Notez qu'une nouvelle version DODAG n'implique pas toujours une topologie DODAG différente. Pour s'adapter à certains changements de topologie, une nouvelle version DODAG est requise, comme décrit plus loin dans cette spécification.

Dans les exemples suivants, veuillez noter que les structures arborescentes sont représentées par souci de simplicité, bien que la structure DODAG permette à chaque nœud d'avoir plusieurs parents lorsque la connectivité le prend en charge.

     +----------------------------------------------------------------+
     |                                                                |
     | +--------------+                                               |
     | |              |                                               |
     | |     (R1)     |            (R2)                   (R3)        |
     | |     /  \     |            /| \                  / |  \       |
     | |    /    \    |           / |  \                /  |   \      |
     | |  (A)    (B)  |         (C) |  (D)     ...    (F) (G)  (H)    |
     | |  /|\     |\  |         /   | / |\             |\  |    |     |
     | | : : :    : : |        :   (E)  : :            :  `:    :     |
     | |              |            / \                                |
     | +--------------+           :   :                               |
     |      DODAG                                                     |
     |                                                                |
     +----------------------------------------------------------------+
                                Instance RPL

                          Figure 1 : Instance RPL

            +----------------+                +----------------+
            |                |                |                |
            |      (R1)      |                |      (R1)      |
            |      /  \      |                |      /         |
            |     /    \     |                |     /          |
            |   (A)    (B)   |         \      |   (A)          |
            |   /|\   / |\   |    ------\     |   /|\          |
            |  : : (C)  : :  |           \    |  : : (C)       |
            |                |           /    |        \       |
            |                |    ------/     |         \      |
            |                |         /      |         (B)    |
            |                |                |          |\    |
            |                |                |          : :   |
            |                |                |                |
            +----------------+                +----------------+
                Version N                        Version N+1

                          Figure 2 : Version DODAG

3.2. Routes montantes et construction DODAG

RPL provisionne des routes vers le haut (Up) vers les racines DODAG, formant un DODAG optimisé selon une fonction objective (OF). Les nœuds RPL construisent et maintiennent ces DODAG via des messages d'objet d'information DODAG (DIO).

3.2.1. Fonction objective (OF)

La fonction objective (OF) définit comment les nœuds RPL sélectionnent et optimisent les routes au sein d'une instance RPL. L'OF est identifiée par un point de code objectif (OCP) dans l'option de configuration DIO. Une OF définit comment les nœuds traduisent une ou plusieurs métriques et contraintes, qui sont elles-mêmes définies dans [RFC6551], en une valeur appelée rang (Rank), qui se rapproche de la distance du nœud par rapport à une racine DODAG. Une OF définit également comment les nœuds sélectionnent les parents. D'autres détails peuvent être trouvés dans la section 14, [RFC6551], [RFC6552] et les spécifications d'accompagnement connexes.

3.2.2. Réparation DODAG

Une racine DODAG institue une opération de réparation globale en incrémentant le DODAGVersionNumber. Cela lance une nouvelle version DODAG. Les nœuds de la nouvelle version DODAG peuvent choisir une nouvelle position dont le rang n'est pas contraint par leur rang dans l'ancienne version DODAG.

RPL prend également en charge des mécanismes qui peuvent être utilisés pour la réparation locale au sein de la version DODAG. Le message DIO spécifie les paramètres nécessaires tels que configurés et contrôlés par la politique à la racine DODAG.

3.2.3. Sécurité

RPL prend en charge la confidentialité et l'intégrité des messages. Il est conçu de telle sorte que les mécanismes de couche de liaison puissent être utilisés lorsqu'ils sont disponibles et appropriés ; cependant, en leur absence, RPL peut utiliser ses propres mécanismes. RPL a trois modes de sécurité de base.

Dans le premier, appelé « non sécurisé », les messages de contrôle RPL sont envoyés sans aucun mécanisme de sécurité supplémentaire. Le mode non sécurisé n'implique pas que le réseau RPL n'est pas sécurisé : il pourrait utiliser d'autres primitives de sécurité présentes (par exemple, la sécurité de la couche de liaison) pour répondre aux exigences de sécurité de l'application.

Dans le second, appelé « préinstallé », les nœuds rejoignant une instance RPL ont des clés préinstallées qui leur permettent de traiter et de générer des messages RPL sécurisés.

Le troisième mode est appelé « authentifié ». En mode authentifié, les nœuds ont des clés préinstallées comme en mode préinstallé, mais la clé préinstallée ne peut être utilisée que pour rejoindre une instance RPL en tant que feuille. Rejoindre une instance RPL authentifiée en tant que routeur nécessite l'obtention d'une clé auprès d'une autorité d'authentification. Le processus par lequel cette clé est obtenue est hors de portée de cette spécification. Notez que cette spécification seule ne fournit pas suffisamment de détails pour qu'une implémentation RPL fonctionne de manière sécurisée en mode authentifié. Pour qu'une implémentation RPL fonctionne de manière sécurisée en mode authentifié, il est nécessaire qu'une future spécification d'accompagnement détaille les mécanismes par lesquels un nœud obtient/demande le matériel d'authentification (par exemple, clé, certificat) et détermine d'où ce matériel doit être obtenu. Voir aussi la section 10.3.

3.2.4. DODAG ancrés et flottants

Les DODAG peuvent être ancrés ou flottants : la racine DODAG annonce lequel est le cas. Un DODAG ancré offre une connectivité aux hôtes nécessaires pour satisfaire l'objectif défini par l'application. Un DODAG flottant n'est pas censé satisfaire l'objectif ; dans la plupart des cas, il ne fournit que des routes vers les nœuds au sein du DODAG. Les DODAG flottants peuvent être utilisés, par exemple, pour préserver l'interconnectivité pendant la réparation.

3.2.5. DODAG locaux

Les nœuds RPL peuvent optimiser les routes vers une destination au sein d'un LLN en formant un DODAG local dont la racine DODAG est la destination souhaitée. Contrairement aux DAG globaux, qui peuvent être constitués de plusieurs DODAG, les DAG locaux ont un et un seul DODAG et donc une seule racine DODAG. Les DODAG locaux peuvent être construits à la demande.

3.2.6. Préférence administrative

Une implémentation/déploiement peut spécifier que certaines racines DODAG doivent être utilisées par rapport à d'autres via une préférence administrative. La préférence administrative offre un moyen de contrôler le trafic et de concevoir la formation de DODAG afin de mieux répondre aux exigences ou aux besoins de l'application.

3.2.7. Validation du chemin de données et détection de boucles

La nature à faible puissance et à pertes des LLN motive l'utilisation par RPL de la détection de boucles à la demande à l'aide de paquets de données. Étant donné que le trafic de données peut être peu fréquent, le maintien d'une topologie de routage constamment à jour avec la topologie physique peut gaspiller de l'énergie. Les LLN typiques présentent des variations de connectivité physique qui sont transitoires et inoffensives pour le trafic, mais qu'il serait coûteux de suivre de près depuis le plan de contrôle. Les changements transitoires et peu fréquents de connectivité n'ont pas besoin d'être traités par RPL tant qu'il n'y a pas de données à envoyer. Cet aspect de la conception de RPL s'inspire des protocoles LLN existants et très utilisés ainsi que de nombreuses preuves expérimentales et de déploiement de son efficacité.

Les informations de paquet RPL qui sont transportées avec les paquets de données incluent le rang de l'émetteur. Une incohérence entre la décision de routage pour un paquet (vers le haut ou vers le bas) et la relation de rang entre les deux nœuds indique une boucle possible. À la réception d'un tel paquet, un nœud institue une opération de réparation locale.

Par exemple, si un nœud reçoit un paquet marqué comme se déplaçant dans la direction vers le haut, et si ce paquet enregistre que l'émetteur est d'un rang inférieur (moindre) à celui du nœud récepteur, alors le nœud récepteur est capable de conclure que le paquet n'a pas progressé dans la direction vers le haut et que le DODAG est incohérent.

3.2.8. Fonctionnement de l'algorithme distribué

Un aperçu de haut niveau de l'algorithme distribué, qui construit le DODAG, est le suivant :

• Certains nœuds sont configurés pour être des racines DODAG, avec des configurations DODAG associées.

• Les nœuds annoncent leur présence, leur affiliation à un DODAG, leur coût de routage et les métriques associées en envoyant des messages DIO multidiffusion lien-local à tous les nœuds RPL (all-RPL-nodes).

• Les nœuds écoutent les DIO et utilisent leurs informations pour rejoindre un nouveau DODAG (sélectionnant ainsi les parents DODAG), ou pour maintenir un DODAG existant, selon la fonction objective spécifiée et le rang de leurs voisins.

• Les nœuds provisionnent des entrées de table de routage, pour les destinations spécifiées par le message DIO, via leurs parents DODAG dans la version DODAG. Les nœuds qui décident de rejoindre un DODAG peuvent provisionner un ou plusieurs parents DODAG comme saut suivant pour la route par défaut et un certain nombre d'autres routes externes pour l'instance associée.

3.3. Routes descendantes et annonce de destination

RPL utilise des messages d'objet d'annonce de destination (DAO) pour établir des routes descendantes (Downward). Les messages DAO sont une fonctionnalité optionnelle pour les applications qui nécessitent un trafic point à multipoint (P2MP) ou point à point (P2P). RPL prend en charge deux modes de trafic descendant : stockage (entièrement avec état) ou non-stockage (entièrement routé à la source) ; voir la section 9. Toute instance RPL donnée est soit de stockage, soit de non-stockage. Dans les deux cas, les paquets P2P voyagent vers le haut vers une racine DODAG puis vers le bas vers la destination finale (sauf si la destination est sur la route montante). Dans le cas du non-stockage, le paquet voyagera jusqu'à une racine DODAG avant de voyager vers le bas. Dans le cas du stockage, le paquet peut être dirigé vers le bas vers la destination par un ancêtre commun de la source et de la destination avant d'atteindre une racine DODAG.

Au moment de la rédaction de cette spécification, aucune implémentation ne devrait prendre en charge à la fois les modes de fonctionnement de stockage et de non-stockage. La plupart des implémentations devraient ne prendre en charge aucune route descendante, le mode non-stockage uniquement ou le mode stockage uniquement. D'autres modes de fonctionnement, tels qu'un mélange hybride de mode de stockage et de non-stockage, sont hors de portée de cette spécification et peuvent être décrits dans d'autres spécifications d'accompagnement.

Cette spécification décrit un mode de fonctionnement de base à l'appui du trafic P2P. Notez que des solutions P2P plus optimisées peuvent être décrites dans des spécifications d'accompagnement.

3.4. Découverte de route DODAG locaux

En option, un réseau RPL peut prendre en charge la découverte à la demande de DODAG vers des destinations spécifiques au sein d'un LLN. De tels DODAG locaux se comportent légèrement différemment des DODAG globaux : ils sont définis de manière unique par la combinaison de DODAGID et RPLInstanceID. Le RPLInstanceID indique si un DODAG est un DODAG local.

3.5. Propriétés de rang

Le rang d'un nœud est une représentation scalaire de l'emplacement de ce nœud au sein d'une version DODAG. Le rang est utilisé pour éviter et détecter les boucles et, en tant que tel, doit démontrer certaines propriétés. Le calcul exact du rang est laissé à la fonction objective. Même si le calcul spécifique du rang est laissé à la fonction objective, le rang doit implémenter des propriétés génériques quelle que soit la fonction objective.

En particulier, le rang des nœuds doit diminuer de manière monotone à mesure que la version DODAG est suivie vers la destination DODAG. À cet égard, le rang peut être considéré comme une représentation scalaire de l'emplacement ou du rayon d'un nœud au sein d'une version DODAG.

Les détails de la manière dont la fonction objective calcule le rang sont hors de portée de cette spécification, bien que ce calcul puisse dépendre, par exemple, des parents, des métriques de liaison, des métriques de nœud et de la configuration et des politiques du nœud. Voir la section 14 pour plus d'informations.

Le rang n'est pas un coût de chemin, bien que sa valeur puisse être dérivée et influencée par des métriques de chemin. Le rang a des propriétés qui lui sont propres et qui ne sont pas nécessairement celles de toutes les métriques :

Type : : Le rang est une valeur numérique abstraite.

Fonction : : Le rang est l'expression d'une position relative au sein d'une version DODAG par rapport aux voisins, et ce n'est pas nécessairement une bonne indication ou une expression appropriée d'une distance ou d'un coût de chemin vers la racine.

Stabilité : : La stabilité du rang détermine la stabilité de la topologie de routage. Un certain amortissement ou filtrage est RECOMMANDÉ pour maintenir la topologie stable ; ainsi, le rang ne change pas nécessairement aussi vite que certaines métriques de liaison ou de nœud. Une nouvelle version DODAG serait une bonne occasion de concilier les écarts qui pourraient se former au fil du temps entre les métriques et les rangs au sein d'une version DODAG.

Propriétés : : Le rang est incrémenté de manière strictement monotone, et il peut être utilisé pour valider une progression depuis ou vers la racine. Une métrique, comme la bande passante ou la gigue, ne présente pas nécessairement cette propriété.

Abstrait : : Le rang n'a pas d'unité physique, mais plutôt une plage d'incrément par saut, où l'attribution de chaque incrément doit être déterminée par la fonction objective.

La valeur de rang alimente la sélection du parent DODAG, selon la stratégie d'évitement de boucle RPL. Une fois qu'un parent a été ajouté et qu'une valeur de rang pour le nœud au sein du DODAG a été annoncée, les options supplémentaires du nœud concernant la sélection du parent DODAG et le mouvement au sein du DODAG sont restreintes en faveur de l'évitement de boucle.

3.5.1. Comparaison de rang (DAGRank())

Le rang peut être considéré comme un nombre à virgule fixe, où la position du point de base entre la partie entière et la partie fractionnaire est déterminée par MinHopRankIncrease. MinHopRankIncrease est l'augmentation minimale de rang entre un nœud et l'un de ses parents DODAG. Une racine DODAG provisionne MinHopRankIncrease. MinHopRankIncrease crée un compromis entre la précision du coût de saut et le nombre maximum de sauts qu'un réseau peut prendre en charge. Un très grand MinHopRankIncrease, par exemple, permet une caractérisation précise de l'effet d'un saut donné sur le rang mais ne peut pas prendre en charge de nombreux sauts.

Lorsqu'une fonction objective calcule le rang, la fonction objective opère sur la quantité de rang entière (c'est-à-dire 16 bits). Lorsque le rang est comparé, par exemple pour la détermination des relations parentales ou la détection de boucles, la partie entière du rang doit être utilisée. La partie entière du rang est calculée par la macro DAGRank() comme suit, où floor(x) est la fonction qui évalue au plus grand entier inférieur ou égal à x :

           DAGRank(rank) = floor(rank/MinHopRankIncrease)

Par exemple, si une quantité de rang de 16 bits est décimale 27, et que le MinHopRankIncrease est décimal 16, alors DAGRank(27) = floor(1.6875) = 1. La partie entière du rang est 1 et la partie fractionnaire est 11/16.

Suivant les conventions de ce document, l'utilisation de la macro DAGRank(node) peut être interprétée comme DAGRank(node.rank), où node.rank est la valeur de rang maintenue par le nœud.

Un nœud A a un rang inférieur au rang d'un nœud B si DAGRank(A) est inférieur à DAGRank(B).

Un nœud A a un rang égal au rang d'un nœud B si DAGRank(A) est égal à DAGRank(B).

Un nœud A a un rang supérieur au rang d'un nœud B si DAGRank(A) est supérieur à DAGRank(B).

3.5.2. Relations de rang

Les calculs de rang maintiennent les propriétés suivantes pour tous les nœuds M et N qui sont voisins dans le LLN :

DAGRank(M) est inférieur à DAGRank(N) :

: Dans ce cas, la position de M est plus proche de la racine DODAG que la position de N. Le nœud M peut être en toute sécurité un parent DODAG pour le nœud N sans risque de créer une boucle. De plus, pour un nœud N, tous les parents de l'ensemble de parents DODAG doivent être d'un rang inférieur à DAGRank(N). En d'autres termes, le rang présenté par un nœud N DOIT être supérieur à celui présenté par l'un de ses parents.

DAGRank(M) est égal à DAGRank(N) :

: Dans ce cas, les positions de M et N au sein du DODAG et par rapport à la racine DODAG sont similaires ou identiques. Le routage via un nœud de rang égal peut provoquer une boucle de routage (c'est-à-dire si ce nœud choisit de router via un nœud de rang égal également).

DAGRank(M) est supérieur à DAGRank(N) :

: Dans ce cas, la position de M est plus éloignée de la racine DODAG que la position de N. De plus, le nœud M peut en fait être dans le sous-DODAG du nœud N. Si le nœud N sélectionne le nœud M comme parent DODAG, il existe un risque de création d'une boucle.

À titre d'exemple, le rang pourrait être calculé de manière à suivre de près l'ETX (nombre de transmissions attendu, une métrique de routage assez courante utilisée dans les LLN et définie dans [RFC6551]) lorsque la métrique qu'une fonction objective minimise est l'ETX, ou la latence, ou d'une manière plus compliquée appropriée à la fonction objective utilisée au sein du DODAG.

3.6. Métriques de routage et contraintes utilisées par RPL

Les métriques de routage sont utilisées par les protocoles de routage pour calculer les chemins les plus courts. Les protocoles de passerelle intérieure (IGP) tels que IS-IS ([RFC5120]) et OSPF ([RFC4915]) utilisent des métriques de liaison statiques. De telles métriques de liaison peuvent simplement refléter la bande passante ou peuvent également être calculées selon une fonction polynomiale de plusieurs métriques définissant différentes caractéristiques de liaison. Certains protocoles de routage prennent en charge plus d'une métrique : dans la grande majorité des cas, une métrique est utilisée par (sous-)topologie. Moins souvent, une seconde métrique peut être utilisée comme départage en présence de chemins multiples à coût égal (ECMP). L'optimisation de plusieurs métriques est connue comme un problème NP-complet et est parfois prise en charge par un moteur de calcul de chemin centralisé.

En revanche, les LLN nécessitent la prise en charge de métriques statiques et dynamiques. De plus, des métriques de liaison et de nœud sont requises. Dans le cas de RPL, il est pratiquement impossible de définir une métrique, ou même une métrique composite, qui satisfera tous les cas d'utilisation.

De plus, RPL prend en charge le routage basé sur les contraintes où des contraintes peuvent être appliquées à la fois aux liens et aux nœuds. Si un lien ou un nœud ne satisfait pas une contrainte requise, il est « élagué » de l'ensemble de voisins candidats, conduisant ainsi à un chemin le plus court contraint.

Une fonction objective spécifie les objectifs utilisés pour calculer le chemin (contraint). De plus, les nœuds sont configurés pour prendre en charge un ensemble de métriques et de contraintes et sélectionner leurs parents dans le DODAG en fonction des métriques et des contraintes annoncées dans les messages DIO. Les métriques amont et aval peuvent être fusionnées ou annoncées séparément selon l'OF et les métriques. Lorsqu'elles sont annoncées séparément, il peut arriver que l'ensemble des parents DIO soit différent de l'ensemble des parents DAO (un parent DAO est un nœud auquel des messages DAO unicast sont envoyés). Pourtant, tous sont des parents DODAG en ce qui concerne les règles de calcul de rang.

La fonction objective est découplée des métriques de routage et des contraintes utilisées par RPL. Alors que l'OF dicte des règles telles que la sélection des parents DODAG, l'équilibrage de charge, etc., l'ensemble des métriques et/ou contraintes utilisées, et donc celles qui déterminent le chemin préféré, sont basées sur les informations véhiculées dans l'option de conteneur DAG dans les messages DIO.

L'ensemble des contraintes et métriques de liaison/nœud prises en charge est spécifié dans [RFC6551].

Exemple 1 : Chemin le plus court : chemin offrant le délai de bout en bout le plus court.

Exemple 2 : Chemin contraint le plus court : le chemin qui ne traverse aucun nœud fonctionnant sur batterie et qui optimise la fiabilité du chemin.

3.7. Évitement de boucle

RPL essaie d'éviter de créer des boucles lors de changements de topologie et inclut des mécanismes de validation de chemin de données basés sur le rang pour détecter les boucles lorsqu'elles se produisent (voir la section 11 pour plus de détails). En pratique, cela signifie que RPL ne garantit ni la sélection de chemin sans boucle ni des temps de convergence de retard serrés, mais il peut détecter et réparer une boucle dès qu'elle est utilisée. RPL utilise cette détection de boucle pour s'assurer que les paquets progressent vers l'avant au sein de la version DODAG et déclencher des réparations si nécessaire.

3.7.1. Avidité et instabilité

Un nœud est avide s'il tente de se déplacer plus profondément (augmenter le rang) dans la version DODAG afin d'augmenter la taille de l'ensemble parent ou d'améliorer une autre métrique. Une fois qu'un nœud a rejoint une version DODAG, RPL interdit certains comportements, y compris l'avidité, afin d'éviter les instabilités résultantes dans la version DODAG.

Supposons qu'un nœud soit prêt à recevoir et à traiter un message DIO d'un nœud de son propre sous-DODAG et, en général, d'un nœud plus profond que lui-même. Dans ce cas, il existe une possibilité qu'une boucle de rétroaction soit créée, dans laquelle deux nœuds ou plus continuent d'essayer de se déplacer dans la version DODAG tout en essayant de s'optimiser l'un contre l'autre. Dans certains cas, cela entraînera une instabilité. C'est pour cette raison que RPL limite les cas où un nœud peut traiter les messages DIO de nœuds plus profonds à une certaine forme de réparation locale. Cette approche crée un « horizon des événements », par lequel un nœud ne peut pas être influencé au-delà d'une certaine limite dans une instabilité par l'action de nœuds qui peuvent être dans son propre sous-DODAG.

3.7.1.1. Exemple : Sélection de parent avide et instabilité

         (A)                    (A)                    (A)
          |\                     |\                     |\
          | `-----.              | `-----.              | `-----.
          |        \             |        \             |        \
         (B)       (C)          (B)        \            |        (C)
                                  \        |            |        /
                                   `-----. |            | .-----'
                                          \|            |/
                                          (C)          (B)

              -1-                    -2-                    -3-

                  Figure 3 : Sélection de parent DODAG avide

La figure 3 illustre un DODAG dans trois configurations différentes. Un lien utilisable entre (B) et (C) existe dans les trois configurations. Dans la figure 3-1, le nœud (A) est un parent DODAG pour les nœuds (B) et (C). Dans la figure 3-2, le nœud (A) est un parent DODAG pour les nœuds (B) et (C), et le nœud (B) est également un parent DODAG pour le nœud (C). Dans la figure 3-3, le nœud (A) est un parent DODAG pour les nœuds (B) et (C), et le nœud (C) est également un parent DODAG pour le nœud (B).

Si un nœud RPL est trop avide, en ce sens qu'il tente d'optimiser pour un nombre supplémentaire de parents au-delà de ses parents les plus préférés, alors une instabilité peut en résulter. Considérez le DODAG illustré à la figure 3-1. Dans cet exemple, les nœuds (B) et (C) peuvent préférer le nœud (A) comme parent DODAG, mais nous considérerons le cas où ils fonctionnent sous la condition avide qui tentera d'optimiser pour deux parents.

• Soit la figure 3-1 la condition initiale.

• Supposons que le nœud (C) soit d'abord capable de quitter le DODAG et de rejoindre à un rang inférieur, prenant à la fois les nœuds (A) et (B) comme parents DODAG comme illustré à la figure 3-2. Maintenant, le nœud (C) est plus profond que les nœuds (A) et (B), et le nœud (C) est satisfait d'avoir deux parents DODAG.

• Supposons que le nœud (B), dans son avidité, soit prêt à recevoir et à traiter un message DIO du nœud (C) (contre les règles de RPL), et ensuite le nœud (B) quitte le DODAG et rejoint à un rang inférieur, prenant à la fois les nœuds (A) et (C) comme parents DODAG. Maintenant, le nœud (B) est plus profond que les nœuds (A) et (C) et est satisfait avec deux parents DAG.

• Ensuite, le nœud (C), parce qu'il est également avide, quittera et rejoindra plus profondément, pour obtenir à nouveau deux parents et avoir un rang inférieur aux deux.

• Ensuite, le nœud (B) quittera à nouveau et rejoindra plus profondément, pour obtenir à nouveau deux parents.

• Encore une fois, le nœud (C) quitte et rejoint plus profondément.

• Le processus se répétera et le DODAG oscillera entre la figure 3-2 et la figure 3-3 jusqu'à ce que les nœuds comptent jusqu'à l'infini et redémarrent le cycle à nouveau.

• Ce cycle peut être évité grâce à des mécanismes dans RPL :

  • Les nœuds (B) et (C) restent à un rang suffisant pour s'attacher à leur parent le plus préféré (A) et ne vont pas chercher d'autres parents plus profonds (pires) (les nœuds ne sont pas avides).

  • Les nœuds (B) et (C) ne traitent pas les messages DIO provenant de nœuds plus profonds qu'eux-mêmes (car de tels nœuds sont peut-être dans leurs propres sous-DODAG).

Ces mécanismes sont décrits plus en détail dans la section 8.2.2.4.

3.7.2. Boucles DODAG

Une boucle DODAG peut se produire lorsqu'un nœud se détache du DODAG et se rattache à un appareil dans son sous-DODAG antérieur. En particulier, cela peut se produire lorsque des messages DIO sont manqués. L'utilisation stricte du DODAGVersionNumber peut éliminer ce type de boucle, mais ce type de boucle peut éventuellement être rencontré lors de l'utilisation de certains mécanismes de réparation locale.

Par exemple, considérez le mécanisme de réparation locale qui permet à un nœud de se détacher du DODAG, d'annoncer un rang de INFINITE_RANK (afin d'empoisonner ses routes / informer son sous-DODAG), puis de se rattacher au DODAG. Dans certains de ces cas, le nœud peut se rattacher à son propre sous-DODAG antérieur, provoquant une boucle DODAG, car l'empoisonnement peut échouer si les annonces INFINITE_RANK sont perdues dans l'environnement LLN. (Dans ce cas, les mécanismes de validation de chemin de données basés sur le rang finiraient par détecter et déclencher la correction de la boucle).

3.7.3. Boucles DAO

Une boucle DAO peut se produire lorsque le parent a une route installée lors de la réception et du traitement d'un message DAO d'un enfant, mais que l'enfant a ensuite nettoyé l'état DAO associé. Cette boucle se produit lorsqu'un No-Path (un message DAO qui invalide un préfixe précédemment annoncé, voir la section 6.4.3) a été manqué et persiste jusqu'à ce que tout l'état ait été nettoyé. RPL inclut un mécanisme optionnel pour accuser réception des messages DAO, ce qui peut atténuer l'impact d'un seul message DAO manqué. RPL inclut des mécanismes de détection de boucle qui atténuent l'impact des boucles DAO et déclenchent leur réparation. (Voir la section 11.2.2.3.)