Skip to main content

7. Sequence Counters

This section describes the general scheme for bootstrap and operation of sequence counters in RPL, such as the DODAGVersionNumber in the DIO message, the DAOSequence in the DAO message, and the Path Sequence in the Transit Information option.

7.1. Sequence Counter Overview​

This specification utilizes three different sequence numbers to validate the freshness and the synchronization of protocol information:

  • DODAGVersionNumber: This sequence counter is present in the DIO Base to indicate the Version of the DODAG being formed. The DODAGVersionNumber is monotonically incremented by the root each time the root decides to form a new Version of the DODAG in order to revalidate the integrity and allow a global repair to occur. The DODAGVersionNumber is propagated unchanged Down the DODAG as routers join the new DODAG Version. The DODAGVersionNumber is globally significant in a DODAG and indicates the Version of the DODAG in which a router is operating. An older (lesser) value indicates that the originating router has not migrated to the new DODAG Version and cannot be used as a parent once the receiving node has migrated to the newer DODAG Version.

  • DAOSequence: This sequence counter is present in the DAO Base to correlate a DAO message and a DAO ACK message. The DAOSequence number is locally significant to the node that issues a DAO message for its own consumption to detect the loss of a DAO message and enable retries.

  • Path Sequence: This sequence counter is present in the Transit Information option in a DAO message. The purpose of this counter is to differentiate a movement where a newer route supersedes a stale one from a route redundancy scenario where multiple routes exist in parallel for the same target. The Path Sequence is globally significant in a DODAG and indicates the freshness of the route to the associated target. An older (lesser) value received from an originating router indicates that the originating router holds stale routing states and the originating router should not be considered anymore as a potential next hop for the target. The Path Sequence is computed by the node that advertises the target, that is the Target itself or a router that advertises a Target on behalf of a host, and is unchanged as the DAO content is propagated towards the root by parent routers. If a host does not pass a counter to its router, then the router is in charge of computing the Path Sequence on behalf of the host and the host can only register to one router for that purpose. If a DAO message containing the same Target is issued to multiple parents at a given point in time for the purpose of route redundancy, then the Path Sequence is the same in all the DAO messages for that same target.

7.2. Sequence Counter Operation​

RPL sequence counters are subdivided in a 'lollipop' fashion [Perlman83], where the values from 128 and greater are used as a linear sequence to indicate a restart and bootstrap the counter, and the values less than or equal to 127 used as a circular sequence number space of size 128 as in [RFC1982]. Consideration is given to the mode of operation when transitioning from the linear region to the circular region. Finally, when operating in the circular region, if sequence numbers are detected to be too far apart, then they are not comparable, as detailed below.

A window of comparison, SEQUENCE_WINDOW = 16, is configured based on a value of 2^N, where N is defined to be 4 in this specification.

For a given sequence counter:

  1. The sequence counter SHOULD be initialized to an implementation defined value, which is 128 or greater prior to use. A recommended value is 240 (256 - SEQUENCE_WINDOW).

  2. When a sequence counter increment would cause the sequence counter to increment beyond its maximum value, the sequence counter MUST wrap back to zero. When incrementing a sequence counter greater than or equal to 128, the maximum value is 255. When incrementing a sequence counter less than 128, the maximum value is 127.

  3. When comparing two sequence counters, the following rules MUST be applied:

    1. When a first sequence counter A is in the interval [128..255] and a second sequence counter B is in [0..127]:

      1. If (256 + B - A) is less than or equal to SEQUENCE_WINDOW, then B is greater than A, A is less than B, and the two are not equal.
      2. If (256 + B - A) is greater than SEQUENCE_WINDOW, then A is greater than B, B is less than A, and the two are not equal.

      For example, if A is 240, and B is 5, then (256 + 5 - 240) is 21. 21 is greater than SEQUENCE_WINDOW (16); thus, 240 is greater than 5. As another example, if A is 250 and B is 5, then (256 + 5 - 250) is 11. 11 is less than SEQUENCE_WINDOW (16); thus, 250 is less than 5.

    2. In the case where both sequence counters to be compared are less than or equal to 127, and in the case where both sequence counters to be compared are greater than or equal to 128:

      1. If the absolute magnitude of difference between the two sequence counters is less than or equal to SEQUENCE_WINDOW, then a comparison as described in [RFC1982] is used to determine the relationships greater than, less than, and equal.
      2. If the absolute magnitude of difference of the two sequence counters is greater than SEQUENCE_WINDOW, then a desynchronization has occurred and the two sequence numbers are not comparable.

  4. If two sequence numbers are determined not to be comparable, i.e., the results of the comparison are not defined, then a node should consider the comparison as if it has evaluated in such a way so as to give precedence to the sequence number that has most recently been observed to increment. Failing this, the node should consider the comparison as if it has evaluated in such a way so as to minimize the resulting changes to its own state.

Last updated on