3. Protokollübersicht

Ziel dieses Abschnitts ist es, RPL im Sinne von [RFC4101] zu beschreiben. Protokolldetails finden sich in weiteren Abschnitten.

3.1. Topologien

Dieser Abschnitt beschreibt die grundlegenden RPL-Topologien, die gebildet werden können, und die Regeln, nach denen diese konstruiert werden, d. h. die Regeln, die die DODAG-Bildung regeln.

3.1.1. Konstruktion von Topologien

LLNs, wie z. B. Funknetzwerke, haben typischerweise keine vordefinierten Topologien, wie z. B. solche, die durch Punkt-zu-Punkt-Drähte auferlegt werden, sodass RPL Verbindungen entdecken und dann Peers sparsam auswählen muss.

In vielen Fällen bildet RPL, da sich Layer-2-Bereiche nur teilweise überlappen, nicht-transitive / Non-Broadcast Multi-Access (NBMA)-Netzwerktopologien, auf denen es Routen berechnet.

RPL-Routen sind für den Verkehr zu oder von einer oder mehreren Wurzeln optimiert, die als Senken für die Topologie fungieren. Infolgedessen organisiert RPL eine Topologie als gerichteten azyklischen Graphen (DAG), der in einen oder mehrere zielorientierte DAGs (DODAGs) unterteilt ist, ein DODAG pro Senke. Wenn der DAG mehrere Wurzeln hat, wird erwartet, dass die Wurzeln durch ein gemeinsames Backbone, wie z. B. eine Transitverbindung, föderiert sind.

3.1.2. RPL-Identifikatoren

RPL verwendet vier Werte, um eine Topologie zu identifizieren und aufrechtzuerhalten:

• Der erste ist eine RPLInstanceID. Eine RPLInstanceID identifiziert eine Menge von einem oder mehreren zielorientierten DAGs (DODAGs). Ein Netzwerk kann mehrere RPLInstanceIDs haben, von denen jede eine unabhängige Menge von DODAGs definiert, die für unterschiedliche Zielfunktionen (OFs) und/oder Anwendungen optimiert sein können. Die Menge der durch eine RPLInstanceID identifizierten DODAGs wird als RPL-Instanz bezeichnet. Alle DODAGs in derselben RPL-Instanz verwenden dieselbe OF.

• Der zweite ist eine DODAGID. Der Geltungsbereich einer DODAGID ist eine RPL-Instanz. Die Kombination aus RPLInstanceID und DODAGID identifiziert einen einzelnen DODAG im Netzwerk eindeutig. Eine RPL-Instanz kann mehrere DODAGs haben, von denen jeder eine eindeutige DODAGID hat.

• Der dritte ist eine DODAGVersionNumber. Der Geltungsbereich einer DODAGVersionNumber ist ein DODAG. Ein DODAG wird manchmal von der DODAG-Wurzel rekonstruiert, indem die DODAGVersionNumber erhöht wird. Die Kombination aus RPLInstanceID, DODAGID und DODAGVersionNumber identifiziert eine DODAG-Version eindeutig.

• Der vierte ist der Rang (Rank). Der Geltungsbereich des Rangs ist eine DODAG-Version. Der Rang etabliert eine Teilordnung über eine DODAG-Version und definiert individuelle Knotenpositionen in Bezug auf die DODAG-Wurzel.

3.1.3. Instanzen, DODAGs und DODAG-Versionen

Eine RPL-Instanz enthält eine oder mehrere DODAG-Wurzeln. Eine RPL-Instanz kann Routen zu bestimmten Zielpräfixen bereitstellen, die über die DODAG-Wurzeln oder alternative Pfade innerhalb des DODAG erreichbar sind. Diese Wurzeln können unabhängig voneinander arbeiten oder sie können sich über ein Netzwerk koordinieren, das nicht unbedingt so eingeschränkt ist wie ein LLN.

Eine RPL-Instanz kann umfassen:

• einen einzelnen DODAG mit einer einzelnen Wurzel

  • Zum Beispiel ein DODAG, der optimiert ist, um die Latenz zu minimieren, verwurzelt an einem einzelnen zentralen Beleuchtungscontroller in einer Hausautomationsanwendung.

• mehrere unkoordinierte DODAGs mit unabhängigen Wurzeln (unterschiedliche DODAGIDs)

  • Zum Beispiel mehrere Datensammelpunkte in einer städtischen Datensammelanwendung, die keine geeignete Konnektivität haben, um sich miteinander zu koordinieren, oder die die Bildung mehrerer DODAGs als Mittel nutzen, um das Netzwerk dynamisch und autonom zu partitionieren.

• einen einzelnen DODAG mit einer virtuellen Wurzel, die LLN-Senken (mit derselben DODAGID) über ein Backbone-Netzwerk koordiniert.

  • Zum Beispiel mehrere Grenzrouter, die mit einer zuverlässigen Transitverbindung arbeiten, z. B. zur Unterstützung einer IPv6 Low-Power Wireless Personal Area Network (6LoWPAN)-Anwendung, die in der Lage sind, als logisch äquivalente Schnittstellen zur Senke desselben DODAG zu fungieren.

• eine Kombination des oben Genannten, wie sie für ein Anwendungsszenario geeignet ist.

Jedes RPL-Paket ist einer bestimmten RPLInstanceID (siehe Abschnitt 11.2) und damit einer RPL-Instanz (Abschnitt 5) zugeordnet. Die Bereitstellung oder automatische Erkennung einer Zuordnung zwischen einer RPLInstanceID und einem Typ oder Dienst des Anwendungsverkehrs liegt außerhalb des Geltungsbereichs dieser Spezifikation (wird in zukünftigen Begleitspezifikationen definiert).

Abbildung 1 zeigt ein Beispiel für eine RPL-Instanz, die drei DODAGs mit den DODAG-Wurzeln R1, R2 und R3 umfasst. Jede dieser DODAG-Wurzeln kündigt dieselbe RPLInstanceID an. Die Linien stellen die Konnektivität zwischen Eltern und Kindern dar.

Abbildung 2 zeigt, wie eine Erhöhung der DODAGVersionNumber zu einer neuen DODAG-Version führt. Diese Darstellung veranschaulicht eine Erhöhung der DODAGVersionNumber, die zu einer anderen DODAG-Topologie führt. Beachten Sie, dass eine neue DODAG-Version nicht immer eine andere DODAG-Topologie impliziert. Um bestimmte Topologieänderungen zu berücksichtigen, ist eine neue DODAG-Version erforderlich, wie später in dieser Spezifikation beschrieben.

In den folgenden Beispielen beachten Sie bitte, dass baumartige Strukturen der Einfachheit halber dargestellt sind, obwohl die DODAG-Struktur es jedem Knoten erlaubt, mehrere Eltern zu haben, wenn die Konnektivität dies unterstützt.

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

                          Abbildung 1: RPL-Instanz

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

                          Abbildung 2: DODAG-Version

3.2. Aufwärts-Routen und DODAG-Konstruktion

RPL stellt Routen nach oben (Up) zu DODAG-Wurzeln bereit und bildet einen DODAG, der gemäß einer Zielfunktion (OF) optimiert ist. RPL-Knoten konstruieren und pflegen diese DODAGs durch DODAG Information Object (DIO)-Nachrichten.

3.2.1. Zielfunktion (OF)

Die Zielfunktion (OF) definiert, wie RPL-Knoten Routen innerhalb einer RPL-Instanz auswählen und optimieren. Die OF wird durch einen Ziel-Codepunkt (OCP) innerhalb der DIO-Konfigurationsoption identifiziert. Eine OF definiert, wie Knoten eine oder mehrere Metriken und Einschränkungen, die selbst in [RFC6551] definiert sind, in einen Wert namens Rang (Rank) übersetzen, der die Entfernung des Knotens von einer DODAG-Wurzel annähert. Eine OF definiert auch, wie Knoten Eltern auswählen. Weitere Details finden sich in Abschnitt 14, [RFC6551], [RFC6552] und verwandten Begleitspezifikationen.

3.2.2. DODAG-Reparatur

Eine DODAG-Wurzel leitet eine globale Reparatur operation ein, indem sie die DODAGVersionNumber erhöht. Dies initiiert eine neue DODAG-Version. Knoten in der neuen DODAG-Version können eine neue Position wählen, deren Rang nicht durch ihren Rang innerhalb der alten DODAG-Version eingeschränkt ist.

RPL unterstützt auch Mechanismen, die für die lokale Reparatur innerhalb der DODAG-Version verwendet werden können. Die DIO-Nachricht spezifiziert die notwendigen Parameter, wie sie von der Richtlinie an der DODAG-Wurzel konfiguriert und gesteuert werden.

3.2.3. Sicherheit

RPL unterstützt Nachrichtenvertraulichkeit und -integrität. Es ist so konzipiert, dass Verbindungsschicht-Mechanismen verwendet werden können, wenn sie verfügbar und angemessen sind; in deren Abwesenheit kann RPL jedoch seine eigenen Mechanismen verwenden. RPL verfügt über drei grundlegende Sicherheitsmodi.

Im ersten, "ungesichert" genannt, werden RPL-Kontrollnachrichten ohne zusätzliche Sicherheitsmechanismen gesendet. Der ungesicherte Modus impliziert nicht, dass das RPL-Netzwerk unsicher ist: Es könnte andere vorhandene Sicherheitsprimitive (z. B. Verbindungsschicht-Sicherheit) verwenden, um die Sicherheitsanforderungen der Anwendung zu erfüllen.

Im zweiten, "vorinstalliert" genannt, haben Knoten, die einer RPL-Instanz beitreten, vorinstallierte Schlüssel, die es ihnen ermöglichen, gesicherte RPL-Nachrichten zu verarbeiten und zu generieren.

Der dritte Modus wird "authentifiziert" genannt. Im authentifizierten Modus haben Knoten vorinstallierte Schlüssel wie im vorinstallierten Modus, aber der vorinstallierte Schlüssel darf nur verwendet werden, um einer RPL-Instanz als Blatt beizutreten. Der Beitritt zu einer authentifizierten RPL-Instanz als Router erfordert den Erhalt eines Schlüssels von einer Authentifizierungsstelle. Der Prozess, durch den dieser Schlüssel erhalten wird, liegt außerhalb des Geltungsbereichs dieser Spezifikation. Beachten Sie, dass diese Spezifikation allein nicht genügend Details bietet, damit eine RPL-Implementierung sicher im authentifizierten Modus arbeiten kann. Damit eine RPL-Implementierung sicher im authentifizierten Modus arbeiten kann, ist es notwendig, dass eine zukünftige Begleitspezifikation die Mechanismen detailliert beschreibt, durch die ein Knoten das Authentifizierungsmaterial (z. B. Schlüssel, Zertifikat) erhält/anfordert, und bestimmt, woher dieses Material bezogen werden soll. Siehe auch Abschnitt 10.3.

3.2.4. Geerdete und schwebende DODAGs

DODAGs können geerdet oder schwebend sein: Die DODAG-Wurzel kündigt an, was der Fall ist. Ein geerdeter DODAG bietet Konnektivität zu Hosts, die zur Erfüllung des anwendungsdefinierten Ziels erforderlich sind. Von einem schwebenden DODAG wird nicht erwartet, dass er das Ziel erfüllt; in den meisten Fällen bietet er nur Routen zu Knoten innerhalb des DODAG. Schwebende DODAGs können beispielsweise verwendet werden, um die Interkonnektivität während der Reparatur aufrechtzuerhalten.

3.2.5. Lokale DODAGs

RPL-Knoten können Routen zu einem Ziel innerhalb eines LLN optimieren, indem sie einen lokalen DODAG bilden, dessen DODAG-Wurzel das gewünschte Ziel ist. Im Gegensatz zu globalen DAGs, die aus mehreren DODAGs bestehen können, haben lokale DAGs einen und nur einen DODAG und daher eine DODAG-Wurzel. Lokale DODAGs können bei Bedarf konstruiert werden.

3.2.6. Administrative Präferenz

Eine Implementierung/Bereitstellung kann festlegen, dass einige DODAG-Wurzeln gegenüber anderen durch eine administrative Präferenz verwendet werden sollten. Die administrative Präferenz bietet eine Möglichkeit, den Verkehr zu steuern und die DODAG-Bildung zu gestalten, um Anwendungsanforderungen oder -bedürfnisse besser zu unterstützen.

3.2.7. Datenpfad-Validierung und Schleifenerkennung

Die stromsparende und verlustbehaftete Natur von LLNs motiviert RPLs Verwendung von On-Demand-Schleifenerkennung unter Verwendung von Datenpaketen. Da Datenverkehr selten sein kann, kann die Aufrechterhaltung einer Routing-Topologie, die ständig mit der physischen Topologie auf dem neuesten Stand ist, Energie verschwenden. Typische LLNs weisen Variationen in der physischen Konnektivität auf, die vorübergehend und für den Verkehr harmlos sind, deren genaue Verfolgung von der Steuerebene aus jedoch kostspielig wäre. Vorübergehende und seltene Änderungen in der Konnektivität müssen von RPL nicht angegangen werden, bis Daten gesendet werden müssen. Dieser Aspekt des RPL-Designs stützt sich auf bestehende, stark genutzte LLN-Protokolle sowie umfangreiche experimentelle und Bereitstellungsnachweise für seine Wirksamkeit.

Die RPL Packet Information, die mit Datenpaketen transportiert wird, enthält den Rang des Senders. Eine Inkonsistenz zwischen der Routing-Entscheidung für ein Paket (aufwärts oder abwärts) und der Rangbeziehung zwischen den beiden Knoten weist auf eine mögliche Schleife hin. Beim Empfang eines solchen Pakets leitet ein Knoten eine lokale Reparatur operation ein.

Wenn ein Knoten beispielsweise ein Paket empfängt, das als in Aufwärtsrichtung bewegend gekennzeichnet ist, und wenn dieses Paket aufzeichnet, dass der Sender einen niedrigeren (geringeren) Rang als der empfangende Knoten hat, kann der empfangende Knoten schlussfolgern, dass das Paket nicht in Aufwärtsrichtung fortgeschritten ist und dass der DODAG inkonsistent ist.

3.2.8. Betrieb des verteilten Algorithmus

Ein allgemeiner Überblick über den verteilten Algorithmus, der den DODAG konstruiert, ist wie folgt:

• Einige Knoten sind so konfiguriert, dass sie DODAG-Wurzeln sind, mit zugehörigen DODAG-Konfigurationen.

• Knoten kündigen ihre Anwesenheit, Zugehörigkeit zu einem DODAG, Routing-Kosten und verwandte Metriken an, indem sie Link-Local-Multicast-DIO-Nachrichten an alle RPL-Knoten (all-RPL-nodes) senden.

• Knoten hören auf DIOs und verwenden deren Informationen, um einem neuen DODAG beizutreten (und somit DODAG-Eltern auszuwählen) oder einen bestehenden DODAG gemäß der angegebenen Zielfunktion und dem Rang ihrer Nachbarn aufrechtzuerhalten.

• Knoten stellen Routing-Tabelleneinträge für die durch die DIO-Nachricht angegebenen Ziele über ihre DODAG-Eltern in der DODAG-Version bereit. Knoten, die beschließen, einem DODAG beizutreten, können einen oder mehrere DODAG-Eltern als nächsten Hop für die Standardroute und eine Reihe anderer externer Routen für die zugehörige Instanz bereitstellen.

3.3. Abwärts-Routen und Zielankündigung

RPL verwendet Destination Advertisement Object (DAO)-Nachrichten, um Abwärts-Routen (Downward) einzurichten. DAO-Nachrichten sind eine optionale Funktion für Anwendungen, die Punkt-zu-Mehrpunkt (P2MP)- oder Punkt-zu-Punkt (P2P)-Verkehr erfordern. RPL unterstützt zwei Modi für Abwärtsverkehr: Storing (vollständig zustandsbehaftet) oder Non-Storing (vollständig quellgeroutet); siehe Abschnitt 9. Jede gegebene RPL-Instanz ist entweder speichernd oder nicht speichernd. In beiden Fällen reisen P2P-Pakete nach oben zu einer DODAG-Wurzel und dann nach unten zum endgültigen Ziel (es sei denn, das Ziel liegt auf der Aufwärtsroute). Im Non-Storing-Fall reist das Paket den ganzen Weg zu einer DODAG-Wurzel, bevor es nach unten reist. Im Storing-Fall kann das Paket von einem gemeinsamen Vorfahren der Quelle und des Ziels nach unten zum Ziel geleitet werden, bevor es eine DODAG-Wurzel erreicht.

Zum Zeitpunkt der Erstellung dieser Spezifikation wird von keiner Implementierung erwartet, dass sie sowohl den Storing- als auch den Non-Storing-Betriebsmodus unterstützt. Von den meisten Implementierungen wird erwartet, dass sie entweder keine Abwärts-Routen, nur den Non-Storing-Modus oder nur den Storing-Modus unterstützen. Andere Betriebsmodi, wie eine hybride Mischung aus Storing- und Non-Storing-Modus, liegen außerhalb des Geltungsbereichs dieser Spezifikation und können in anderen Begleitspezifikationen beschrieben werden.

Diese Spezifikation beschreibt einen grundlegenden Betriebsmodus zur Unterstützung von P2P-Verkehr. Beachten Sie, dass optimiertere P2P-Lösungen in Begleitspezifikationen beschrieben werden können.

3.4. Lokale DODAGs Routenentdeckung

Optional kann ein RPL-Netzwerk die On-Demand-Entdeckung von DODAGs zu bestimmten Zielen innerhalb eines LLN unterstützen. Solche lokalen DODAGs verhalten sich etwas anders als globale DODAGs: Sie werden durch die Kombination von DODAGID und RPLInstanceID eindeutig definiert. Die RPLInstanceID gibt an, ob ein DODAG ein lokaler DODAG ist.

3.5. Rang-Eigenschaften

Der Rang eines Knotens ist eine skalare Darstellung des Standorts dieses Knotens innerhalb einer DODAG-Version. Der Rang wird verwendet, um Schleifen zu vermeiden und zu erkennen, und muss daher bestimmte Eigenschaften aufweisen. Die genaue Berechnung des Rangs bleibt der Zielfunktion überlassen. Auch wenn die spezifische Berechnung des Rangs der Zielfunktion überlassen bleibt, muss der Rang unabhängig von der Zielfunktion generische Eigenschaften implementieren.

Insbesondere muss der Rang der Knoten monoton abnehmen, wenn der DODAG-Version in Richtung des DODAG-Ziels gefolgt wird. In dieser Hinsicht kann der Rang als skalare Darstellung des Standorts oder Radius eines Knotens innerhalb einer DODAG-Version betrachtet werden.

Die Details, wie die Zielfunktion den Rang berechnet, liegen außerhalb des Geltungsbereichs dieser Spezifikation, obwohl diese Berechnung beispielsweise von Eltern, Verbindungsmetriken, Knotenmetriken und der Knotenkonfiguration und -richtlinien abhängen kann. Siehe Abschnitt 14 für weitere Informationen.

Der Rang ist keine Pfadkosten, obwohl sein Wert von Pfadmetriken abgeleitet und beeinflusst werden kann. Der Rang hat eigene Eigenschaften, die nicht unbedingt die aller Metriken sind:

Typ: : Der Rang ist ein abstrakter numerischer Wert.

Funktion: : Der Rang ist der Ausdruck einer relativen Position innerhalb einer DODAG-Version in Bezug auf Nachbarn und ist nicht unbedingt ein guter Indikator oder ein geeigneter Ausdruck einer Entfernung oder Pfadkosten zur Wurzel.

Stabilität: : Die Stabilität des Rangs bestimmt die Stabilität der Routing-Topologie. Eine gewisse Dämpfung oder Filterung wird EMPFOHLEN, um die Topologie stabil zu halten; daher ändert sich der Rang nicht unbedingt so schnell wie einige Verbindungs- oder Knotenmetriken. Eine neue DODAG-Version wäre eine gute Gelegenheit, die Diskrepanzen, die sich im Laufe der Zeit zwischen Metriken und Rängen innerhalb einer DODAG-Version bilden könnten, in Einklang zu bringen.

Eigenschaften: : Der Rang wird streng monoton erhöht und kann verwendet werden, um einen Fortschritt von oder zur Wurzel zu validieren. Eine Metrik wie Bandbreite oder Jitter weist diese Eigenschaft nicht unbedingt auf.

Abstrakt: : Der Rang hat keine physikalische Einheit, sondern eher einen Bereich von Inkrementen pro Hop, wobei die Zuweisung jedes Inkrements durch die Zielfunktion bestimmt wird.

Der Rangwert fließt gemäß der RPL-Schleifenvermeidungsstrategie in die DODAG-Elternauswahl ein. Sobald ein Elternteil hinzugefügt wurde und ein Rangwert für den Knoten innerhalb des DODAG angekündigt wurde, sind die weiteren Optionen des Knotens in Bezug auf die DODAG-Elternauswahl und die Bewegung innerhalb des DODAG zugunsten der Schleifenvermeidung eingeschränkt.

3.5.1. Rangvergleich (DAGRank())

Der Rang kann als Festkommazahl betrachtet werden, wobei die Position des Kommas zwischen dem ganzzahligen Teil und dem gebrochenen Teil durch MinHopRankIncrease bestimmt wird. MinHopRankIncrease ist die minimale Erhöhung des Rangs zwischen einem Knoten und einem seiner DODAG-Eltern. Eine DODAG-Wurzel stellt MinHopRankIncrease bereit. MinHopRankIncrease schafft einen Kompromiss zwischen Hop-Kosten-Genauigkeit und der maximalen Anzahl von Hops, die ein Netzwerk unterstützen kann. Ein sehr großes MinHopRankIncrease ermöglicht beispielsweise eine genaue Charakterisierung der Auswirkung eines bestimmten Hops auf den Rang, kann jedoch nicht viele Hops unterstützen.

Wenn eine Zielfunktion den Rang berechnet, operiert die Zielfunktion auf der gesamten (d. h. 16-Bit) Ranggröße. Wenn der Rang verglichen wird, z. B. zur Bestimmung von Elternbeziehungen oder zur Schleifenerkennung, ist der ganzzahlige Teil des Rangs zu verwenden. Der ganzzahlige Teil des Rangs wird durch das Makro DAGRank() wie folgt berechnet, wobei floor(x) die Funktion ist, die zur größten ganzen Zahl kleiner oder gleich x auswertet:

           DAGRank(rank) = floor(rank/MinHopRankIncrease)

Wenn beispielsweise eine 16-Bit-Ranggröße dezimal 27 ist und MinHopRankIncrease dezimal 16 ist, dann ist DAGRank(27) = floor(1,6875) = 1. Der ganzzahlige Teil des Rangs ist 1 und der gebrochene Teil ist 11/16.

Den Konventionen in diesem Dokument folgend, kann die Verwendung des Makros DAGRank(node) als DAGRank(node.rank) interpretiert werden, wobei node.rank der vom Knoten gepflegte Rangwert ist.

Ein Knoten A hat einen Rang, der kleiner ist als der Rang eines Knotens B, wenn DAGRank(A) kleiner als DAGRank(B) ist.

Ein Knoten A hat einen Rang, der gleich dem Rang eines Knotens B ist, wenn DAGRank(A) gleich DAGRank(B) ist.

Ein Knoten A hat einen Rang, der größer ist als der Rang eines Knotens B, wenn DAGRank(A) größer als DAGRank(B) ist.

3.5.2. Rangbeziehungen

Rangberechnungen halten die folgenden Eigenschaften für alle Knoten M und N aufrecht, die Nachbarn im LLN sind:

DAGRank(M) ist kleiner als DAGRank(N):

: In diesem Fall ist die Position von M näher an der DODAG-Wurzel als die Position von N. Knoten M kann sicher ein DODAG-Elternteil für Knoten N sein, ohne das Risiko, eine Schleife zu erzeugen. Ferner müssen für einen Knoten N alle Eltern im DODAG-Elternsatz einen Rang haben, der kleiner als DAGRank(N) ist. Mit anderen Worten, der von einem Knoten N präsentierte Rang MUSS größer sein als der von einem seiner Eltern präsentierte Rang.

DAGRank(M) ist gleich DAGRank(N):

: In diesem Fall sind die Positionen von M und N innerhalb des DODAG und in Bezug auf die DODAG-Wurzel ähnlich oder identisch. Das Routing über einen Knoten mit gleichem Rang kann eine Routing-Schleife verursachen (d. h., wenn dieser Knoten ebenfalls über einen Knoten mit gleichem Rang routet).

DAGRank(M) ist größer als DAGRank(N):

: In diesem Fall ist die Position von M weiter von der DODAG-Wurzel entfernt als die Position von N. Ferner kann sich Knoten M tatsächlich im Sub-DODAG von Knoten N befinden. Wenn Knoten N Knoten M als DODAG-Elternteil auswählt, besteht das Risiko, eine Schleife zu erzeugen.

Als Beispiel könnte der Rang so berechnet werden, dass er ETX (Expected Transmission Count, eine ziemlich gebräuchliche Routing-Metrik, die in LLN verwendet und in [RFC6551] definiert ist) eng verfolgt, wenn die Metrik, die eine Zielfunktion minimiert, ETX oder Latenz ist, oder auf eine kompliziertere Weise, wie es für die im DODAG verwendete Zielfunktion angemessen ist.

3.6. Von RPL verwendete Routing-Metriken und Einschränkungen

Routing-Metriken werden von Routing-Protokollen verwendet, um kürzeste Pfade zu berechnen. Interior Gateway Protocols (IGPs) wie IS-IS ([RFC5120]) und OSPF ([RFC4915]) verwenden statische Verbindungsmetriken. Solche Verbindungsmetriken können einfach die Bandbreite widerspiegeln oder auch gemäß einer Polynomfunktion mehrerer Metriken berechnet werden, die unterschiedliche Verbindungseigenschaften definieren. Einige Routing-Protokolle unterstützen mehr als eine Metrik: In der überwiegenden Mehrheit der Fälle wird eine Metrik pro (Sub-)Topologie verwendet. Seltener kann eine zweite Metrik als Tiebreaker bei Vorhandensein von Equal Cost Multiple Paths (ECMPs) verwendet werden. Die Optimierung mehrerer Metriken ist als NP-vollständiges Problem bekannt und wird manchmal von einer zentralisierten Pfadberechnungs-Engine unterstützt.

Im Gegensatz dazu erfordern LLNs die Unterstützung sowohl statischer als auch dynamischer Metriken. Darüber hinaus sind sowohl Verbindungs- als auch Knotenmetriken erforderlich. Im Fall von RPL ist es praktisch unmöglich, eine Metrik oder sogar eine zusammengesetzte Metrik zu definieren, die alle Anwendungsfälle erfüllt.

Darüber hinaus unterstützt RPL Constraint-basiertes Routing, bei dem Einschränkungen sowohl auf Verbindungen als auch auf Knoten angewendet werden können. Wenn eine Verbindung oder ein Knoten eine erforderliche Einschränkung nicht erfüllt, wird sie/er aus dem Kandidaten-Nachbarsatz "beschnitten", was zu einem eingeschränkten kürzesten Pfad führt.

Eine Zielfunktion spezifiziert die Ziele, die zur Berechnung des (eingeschränkten) Pfads verwendet werden. Darüber hinaus sind Knoten so konfiguriert, dass sie eine Reihe von Metriken und Einschränkungen unterstützen und ihre Eltern im DODAG gemäß den in den DIO-Nachrichten angekündigten Metriken und Einschränkungen auswählen. Upstream- und Downstream-Metriken können je nach OF und Metriken zusammengeführt oder separat angekündigt werden. Wenn sie separat angekündigt werden, kann es vorkommen, dass der Satz von DIO-Eltern sich vom Satz von DAO-Eltern unterscheidet (ein DAO-Elternteil ist ein Knoten, an den Unicast-DAO-Nachrichten gesendet werden). Dennoch sind alle DODAG-Eltern in Bezug auf die Regeln für die Rangberechnung.

Die Zielfunktion ist von den von RPL verwendeten Routing-Metriken und Einschränkungen entkoppelt. Während die OF Regeln wie DODAG-Elternauswahl, Lastausgleich usw. vorgibt, basieren der Satz der verwendeten Metriken und/oder Einschränkungen und damit diejenigen, die den bevorzugten Pfad bestimmen, auf den Informationen, die innerhalb der DAG-Container-Option in DIO-Nachrichten übertragen werden.

Der Satz der unterstützten Verbindungs-/Knoteneinschränkungen und -metriken ist in [RFC6551] spezifiziert.

Beispiel 1: Kürzester Pfad: Pfad, der die kürzeste Ende-zu-Ende-Verzögerung bietet.

Beispiel 2: Kürzester eingeschränkter Pfad: der Pfad, der keinen batteriebetriebenen Knoten durchquert und der die Pfadzuverlässigkeit optimiert.

3.7. Schleifenvermeidung

RPL versucht, das Erzeugen von Schleifen bei Topologieänderungen zu vermeiden, und enthält rangbasierte Datenpfad-Validierungsmechanismen zum Erkennen von Schleifen, wenn sie auftreten (siehe Abschnitt 11 für weitere Details). In der Praxis bedeutet dies, dass RPL weder eine schleifenfreie Pfadauswahl noch enge Verzögerungskonvergenzzeiten garantiert, aber es kann eine Schleife erkennen und reparieren, sobald sie verwendet wird. RPL verwendet diese Schleifenerkennung, um sicherzustellen, dass Pakete innerhalb der DODAG-Version Fortschritte machen, und um bei Bedarf Reparaturen auszulösen.

3.7.1. Gier und Instabilität

Ein Knoten ist gierig, wenn er versucht, sich tiefer (Rang erhöhen) in die DODAG-Version zu bewegen, um die Größe des Elternsatzes zu erhöhen oder eine andere Metrik zu verbessern. Sobald ein Knoten einer DODAG-Version beigetreten ist, verbietet RPL bestimmte Verhaltensweisen, einschließlich Gier, um daraus resultierende Instabilitäten in der DODAG-Version zu verhindern.

Angenommen, ein Knoten ist bereit, eine DIO-Nachricht von einem Knoten in seinem eigenen Sub-DODAG und im Allgemeinen von einem Knoten, der tiefer als er selbst ist, zu empfangen und zu verarbeiten. In diesem Fall besteht die Möglichkeit, dass eine Rückkopplungsschleife entsteht, in der zwei oder mehr Knoten weiterhin versuchen, sich in der DODAG-Version zu bewegen, während sie versuchen, gegeneinander zu optimieren. In einigen Fällen führt dies zu Instabilität. Aus diesem Grund beschränkt RPL die Fälle, in denen ein Knoten DIO-Nachrichten von tieferen Knoten verarbeiten kann, auf eine Form der lokalen Reparatur. Dieser Ansatz schafft einen "Ereignishorizont", wodurch ein Knoten nicht über eine bestimmte Grenze hinaus durch die Aktion von Knoten, die sich möglicherweise in seinem eigenen Sub-DODAG befinden, in eine Instabilität beeinflusst werden kann.

3.7.1.1. Beispiel: Gierige Elternauswahl und Instabilität

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

              -1-                    -2-                    -3-

                  Abbildung 3: Gierige DODAG-Elternauswahl

Abbildung 3 zeigt einen DODAG in drei verschiedenen Konfigurationen. Eine nutzbare Verbindung zwischen (B) und (C) existiert in allen drei Konfigurationen. In Abbildung 3-1 ist Knoten (A) ein DODAG-Elternteil für die Knoten (B) und (C). In Abbildung 3-2 ist Knoten (A) ein DODAG-Elternteil für die Knoten (B) und (C), und Knoten (B) ist auch ein DODAG-Elternteil für Knoten (C). In Abbildung 3-3 ist Knoten (A) ein DODAG-Elternteil für die Knoten (B) und (C), und Knoten (C) ist auch ein DODAG-Elternteil für Knoten (B).

Wenn ein RPL-Knoten zu gierig ist, indem er versucht, für eine zusätzliche Anzahl von Eltern über seine bevorzugtesten Eltern hinaus zu optimieren, kann dies zu einer Instabilität führen. Betrachten Sie den in Abbildung 3-1 dargestellten DODAG. In diesem Beispiel bevorzugen die Knoten (B) und (C) möglicherweise Knoten (A) als DODAG-Elternteil am meisten, aber wir werden den Fall betrachten, in dem sie unter der gierigen Bedingung arbeiten, dass sie versuchen werden, für zwei Eltern zu optimieren.

• Lassen Sie Abbildung 3-1 die Anfangsbedingung sein.

• Angenommen, Knoten (C) kann zuerst den DODAG verlassen und mit einem niedrigeren Rang wieder beitreten, wobei er sowohl Knoten (A) als auch (B) als DODAG-Eltern nimmt, wie in Abbildung 3-2 dargestellt. Jetzt ist Knoten (C) tiefer als beide Knoten (A) und (B), und Knoten (C) ist zufrieden, zwei DODAG-Eltern zu haben.

• Angenommen, Knoten (B) ist in seiner Gier bereit, eine DIO-Nachricht von Knoten (C) zu empfangen und zu verarbeiten (gegen die Regeln von RPL), und dann verlässt Knoten (B) den DODAG und tritt mit einem niedrigeren Rang wieder bei, wobei er sowohl Knoten (A) als auch (C) als DODAG-Eltern nimmt. Jetzt ist Knoten (B) tiefer als beide Knoten (A) und (C) und ist mit zwei DAG-Eltern zufrieden.

• Dann wird Knoten (C), da er auch gierig ist, verlassen und tiefer wieder beitreten, um wieder zwei Eltern zu bekommen und einen niedrigeren Rang als beide zu haben.

• Als nächstes wird Knoten (B) wieder verlassen und tiefer wieder beitreten, um wieder zwei Eltern zu bekommen.

• Wieder verlässt Knoten (C) und tritt tiefer wieder bei.

• Der Prozess wird sich wiederholen, und der DODAG wird zwischen Abbildung 3-2 und Abbildung 3-3 oszillieren, bis die Knoten bis unendlich zählen und den Zyklus erneut starten.

• Dieser Zyklus kann durch Mechanismen in RPL abgewendet werden:

  • Die Knoten (B) und (C) bleiben auf einem Rang, der ausreicht, um sich an ihren bevorzugtesten Elternteil (A) anzuhängen, und suchen nicht nach tieferen (schlechteren) alternativen Eltern (Knoten sind nicht gierig).

  • Die Knoten (B) und (C) verarbeiten keine DIO-Nachrichten von Knoten, die tiefer sind als sie selbst (da sich solche Knoten möglicherweise in ihren eigenen Sub-DODAGs befinden).

Diese Mechanismen werden in Abschnitt 8.2.2.4 näher beschrieben.

3.7.2. DODAG-Schleifen

Eine DODAG-Schleife kann auftreten, wenn sich ein Knoten vom DODAG löst und wieder an ein Gerät in seinem vorherigen Sub-DODAG anhängt. Insbesondere kann dies passieren, wenn DIO-Nachrichten verpasst werden. Die strikte Verwendung der DODAGVersionNumber kann diese Art von Schleife eliminieren, aber diese Art von Schleife kann möglicherweise bei der Verwendung einiger lokaler Reparaturmechanismen auftreten.

Betrachten Sie beispielsweise den lokalen Reparaturmechanismus, der es einem Knoten ermöglicht, sich vom DODAG zu lösen, einen Rang von INFINITE_RANK anzukündigen (um seine Routen zu vergiften / seinen Sub-DODAG zu informieren) und sich dann wieder an den DODAG anzuhängen. In einigen dieser Fälle kann sich der Knoten wieder an seinen eigenen vorherigen Sub-DODAG anhängen, was eine DODAG-Schleife verursacht, da die Vergiftung fehlschlagen kann, wenn die INFINITE_RANK-Ankündigungen in der LLN-Umgebung verloren gehen. (In diesem Fall würden die rangbasierten Datenpfad-Validierungsmechanismen die Schleife schließlich erkennen und eine Korrektur auslösen).

3.7.3. DAO-Schleifen

Eine DAO-Schleife kann auftreten, wenn der Elternteil beim Empfang und der Verarbeitung einer DAO-Nachricht von einem Kind eine Route installiert hat, das Kind jedoch anschließend den zugehörigen DAO-Zustand bereinigt hat. Diese Schleife tritt auf, wenn ein No-Path (eine DAO-Nachricht, die ein zuvor angekündigtes Präfix ungültig macht, siehe Abschnitt 6.4.3) verpasst wurde und bestehen bleibt, bis der gesamte Zustand bereinigt wurde. RPL enthält einen optionalen Mechanismus zur Bestätigung von DAO-Nachrichten, der die Auswirkungen einer einzelnen verpassten DAO-Nachricht mildern kann. RPL enthält Schleifenerkennungsmechanismen, die die Auswirkungen von DAO-Schleifen mildern und deren Reparatur auslösen. (Siehe Abschnitt 11.2.2.3.)