RIFT: Routing in Fat Trees

6.3.2. Southbound and Northbound TIE Representation

A central concept of RIFT is that each node represents itself differently depending on the direction in which it is advertising information. More precisely, a spine node represents two different databases over its adjacencies depending on whether it advertises TIEs to the north or to the south/east-west. Those differing TIE databases are called either south- or northbound (South TIEs and North TIEs) depending on the direction of distribution.¶

The North TIEs hold all of the node's adjacencies and local prefixes while the South TIEs hold only all of the node's adjacencies, the default prefix with necessary disaggregated prefixes and local prefixes. Section 6.5 explains further details.¶

All TIE types are mostly symmetrical in both directions. The (Section 7.3) defines the TIE types (i.e., the TIETypeType element) and their directionality (i.e., direction within the TIEID element).¶

As an example illustrating a database holding both representations, the topology in Figure 2 with the optional link between spine 111 and spine 112 (so that the flooding on an East-West link can be shown) is shown below. Unnumbered interfaces are implicitly assumed and for simplicity, the key value elements which may be included in their South TIEs or North TIEs are not shown. First, in Figure 15 are the TIEs generated by some nodes.¶

        ToF 21 South TIEs:
        Node South TIE:
          NodeTIEElement(level=2,
            neighbors(
              (Spine 111, level 1, cost 1, links(...)),
              (Spine 112, level 1, cost 1, links(...)),
              (Spine 121, level 1, cost 1, links(...)),
              (Spine 122, level 1, cost 1, links(...))
            )
          )
        Prefix South TIE:
          PrefixTIEElement(prefixes(0/0, metric 1), (::/0, metric 1))

        Spine 111 South TIEs:
        Node South TIE:
          NodeTIEElement(level=1,
            neighbors(
              (ToF 21, level 2, cost 1, links(...)),
              (ToF 22, level 2, cost 1, links(...)),
              (Spine 112, level 1, cost 1, links(...)),
              (Leaf111, level 0, cost 1, links(...)),
              (Leaf112, level 0, cost 1, links(...))
            )
          )
        Prefix South TIE:
          PrefixTIEElement(prefixes(0/0, metric 1), (::/0, metric 1))

        Spine 111 North TIEs:
        Node North TIE:
          NodeTIEElement(level=1,
            neighbors(
              (ToF 21, level 2, cost 1, links(...)),
              (ToF 22, level 2, cost 1, links(...)),
              (Spine 112, level 1, cost 1, links(...)),
              (Leaf111, level 0, cost 1, links(...)),
              (Leaf112, level 0, cost 1, links(...))
            )
          )
        Prefix North TIE:
          PrefixTIEElement(prefixes(Spine 111.loopback)

        Spine 121 South TIEs:
        Node South TIE:
          NodeTIEElement(level=1,
            neighbors(
              (ToF 21, level 2, cost 1, links(...)),
              (ToF 22, level 2, cost 1, links(...)),
              (Leaf121, level 0, cost 1, links(...)),
              (Leaf122, level 0, cost 1, links(...))
            )
          )
        Prefix South TIE:
          PrefixTIEElement(prefixes(0/0, metric 1), (::/0, metric 1))

        Spine 121 North TIEs:
        Node North TIE:
          NodeTIEElement(level=1,
            neighbors(
              (ToF 21, level 2, cost 1, links(...)),
              (ToF 22, level 2, cost 1, links(...)),
              (Leaf121, level 0, cost 1, links(...)),
              (Leaf122, level 0, cost 1, links(...))
            )
          )
        Prefix North TIE:
          PrefixTIEElement(prefixes(Spine 121.loopback)

        Leaf112 North TIEs:
        Node North TIE:
          NodeTIEElement(level=0,
            neighbors(
              (Spine 111, level 1, cost 1, links(...)),
              (Spine 112, level 1, cost 1, links(...))
            )
          )
        Prefix North TIE:
          PrefixTIEElement(prefixes(Leaf112.loopback, Prefix112, Prefix_MH))

It may not be obvious here as to why the Node South TIEs contain all the adjacencies of the corresponding node. This will be necessary for algorithms further elaborated on in Section 6.3.9 and Section 6.8.7.¶

For Node TIEs to carry more adjacencies than fit into an MTU-sized packet, the element neighbors may contain a different set of neighbors in each TIE. Those disjointed sets of neighbors MUST be joined during corresponding computation. However, if the following occurs across multiple Node TIEs¶

1. capabilities do not match or¶
2. flags values do not match or¶
3. same neighbor repeats in multiple TIEs with different values¶

The implementation is expected to use the value of any of the valid TIEs it received as it cannot control the arrival order of those TIEs.¶

The miscabled_links element SHOULD be included in every Node TIE, otherwise the behavior is undefined.¶

A ToF node MUST include information on all other ToFs it is aware of through reflection. The same_plane_tofs element is used to carry this information. To prevent MTU overrun problems, multiple Node TIEs can carry disjointed sets of ToFs which MUST be joined to form a single set.¶

Different TIE types are carried in TIEElement. Schema enum `common.TIETypeType` in TIEID indicates which elements MUST be present in the TIEElement. In case of a mismatch between the TIETypeType in the TIEID and the present element, the unexpected elements MUST be ignored. In case of lack of expected element in the TIE an error MUST be reported and the TIE MUST be ignored. The element positive_disaggregation_prefixes and positive_external_disaggregation_prefixes MUST be advertised southbound only and ignored in North TIEs. The element negative_disaggregation_prefixes MUST be propagated according to Section 6.5.2 southwards towards lower levels to heal pathological upper-level partitioning, otherwise traffic loss may occur in multiplane fabrics. It MUST NOT be advertised within a North TIE and MUST be ignored otherwise.¶

6.3.3. Flooding

As described before, TIEs themselves are transported over UDP with the ports indicated in the LIE exchanges and using the destination address on which the LIE adjacency has been formed.¶

TIEs are uniquely identified by the TIEID schema element. The TIEID induces a total order achieved by comparing the elements in sequence defined in the element and comparing each value as an unsigned integer of corresponding length. The TIEHeader element contains a seq_nr element to distinguish newer versions of same TIE.¶

The TIEHeader can also carry an origination_time schema element (for fabrics that utilize precision timing) which contains the absolute timestamp of when the TIE was generated and an origination_lifetime to indicate the original lifetime when the TIE was generated. When carried, they can be used for debugging or security purposes (e.g. to prevent lifetime modification attacks). Clock synchronization is considered in more detail in Section 6.8.4.¶

remaining_lifetime counts down to 0 from origination_lifetime. TIEs with lifetimes differing by less than lifetime_diff2ignore MUST be considered EQUAL (if all other fields are equal). This constant MUST be larger than purge_lifetime to avoid retransmissions.¶

This normative ordering methodology is described in Figure 16 and MUST be used by all implementations.¶

function Compare(X: TIEHeader, Y: TIEHeader) returns Ordering:

    seq_nr of a TIEHeader = TIEHeader.seq_nr

    TIEID of a TIEHeader = TIEHeader.TIEID
    direction of a TIEID = TIEID.direction

    # System ID
    originator of a TIEID = TIEID.originator

    # is of type TIETypeType
    tietype of a TIEID = TIEID.tietype
    tie_nr of a TIEID = TIEID.tie_nr

    if X.direction > Y.direction:
        return X is larger
    else if X.direction < Y.direction:
        return Y is larger
    else if X.originator > Y.originator:
        return X is larger
    else if X.originator < Y.originator:
        return Y is larger
    else:
        if X.tietype == Y.tietype:
            if X.tie_nr == Y.tie_nr:
                if X.seq_nr == Y.seq_nr:
                    X.lifetime_left = X.remaining_lifetime - time since TIE was received
                    Y.lifetime_left = Y.remaining_lifetime - time since TIE was received

                    if absolute_value_of(X.lifetime_left - Y.lifetime_left) <= common.lifetime_diff2ignore:
                        return Both are Equal

                    else:
                        return TIEHeader with larger lifetime_left is larger
                else:
                    return return TIEHeader with larger seq_nr is larger
            else:
                return TIEHeader with larger tie_nr is larger
        else:
            return TIEHeader with larger TIEType is larger

All valid TIE types are defined in TIETypeType. This enum indicates what TIE type the TIE is carrying. In case the value is not known to the receiver, the TIE MUST be re-flooded with scope identical to the scope of a prefix TIE. This allows for future extensions of the protocol within the same major schema with types opaque to some nodes with some restrictions defined in Section 7.¶

6.3.4. TIE Flooding Scopes

In a somewhat analogous fashion to link-local, area and domain flooding scopes, RIFT defines several complex "flooding scopes" depending on the direction and type of TIE propagated.¶

Every North TIE is flooded northbound, providing a node at a given level with the complete topology of the Clos or Fat Tree network that is reachable southwards of it, including all specific prefixes. This means that a packet received from a node at the same or lower level whose destination is covered by one of those specific prefixes will be routed directly towards the node advertising that prefix rather than sending the packet to a node at a higher level.¶

A node's Node South TIEs, consisting of all node's adjacencies and prefix South TIEs limited to those related to default IP prefix and disaggregated prefixes, are flooded southbound in order to inform nodes one level down of connectivity of the higher level as well as reachability to the rest of the fabric. In order to allow an E-W disconnected node in a given level to receive the South TIEs of other nodes at its level, every NODE South TIE is "reflected" northbound to the level from which it was received. It should be noted that East-West links are included in South TIE flooding (except at the ToF level); those TIEs need to be flooded to satisfy algorithms in Section 6.4. In that way nodes at same level can learn about each other using without a lower level except in case of leaf level. The precise, normative flooding scopes are given in Table 3. Those rules also govern what SHOULD be included in TIDEs on the adjacency. Again, East-West flooding scopes are identical to South flooding scopes except in case of ToF East-West links (rings) which are basically performing northbound flooding.¶

Node South TIE "south reflection" enables support of positive disaggregation on failures as described in Section 6.5 and flooding reduction in Section 6.3.9.¶

If the TIDE includes additional TIE headers beside the ones specified, the receiving neighbor must apply the corresponding filter to the received TIDE strictly and MUST NOT request the extra TIE headers that were not allowed by the flooding scope rules in its direction.¶

To illustrate these rules, consider using the topology in Figure 2, with the optional link between spine 111 and spine 112, and the associated TIEs given in Figure 15. The flooding from particular nodes of the TIEs is given in Table 4.¶

6.3.5. RAIN: RIFT Adjacency Inrush Notification

The optional RIFT Adjacency Inrush Notification (RAIN) mechanism helps to prevent adjacencies from being overwhelmed by flooding on restart or bring-up with many southbound neighbors. A node MAY set in its LIEs the corresponding you_are_sending_too_quickly flag to indicate to the neighbor that it SHOULD flood Node TIEs with normal speed and significantly slow down the flooding of any other TIEs. The flag SHOULD be set only in the southbound direction. The receiving node SHOULD accommodate the request to lessen the flooding load on the affected node if south of the sender and should ignore the indication if north of the sender.¶

The distribution of Node TIEs at normal speed even at high load guarantees correct behavior of algorithms like disaggregation or default route origination. Furthermore though, the use of this bit presents an inherent trade-off between processing load and convergence speed since significantly slowing down flooding of northbound prefixes from neighbors for an extended time will lead to traffic losses.¶

6.3.6. Initial and Periodic Database Synchronization

The initial exchange of RIFT includes periodic TIDE exchanges that contain description of the link state database and TIREs which perform the function of requesting unknown TIEs as well as confirming reception of flooded TIEs. The content of TIDEs and TIREs is governed by Table 3.¶

6.3.7. Purging and Roll-Overs

When a node exits the network, if "unpurged", residual stale TIEs may exist in the network until their lifetimes expire (which in case of RIFT is by default a rather long period to prevent ongoing re-origination of TIEs in very large topologies). RIFT does not have a "purging mechanism" based on sending specialized "purge" packets. In other routing protocols such a mechanism has proven to be complex and fragile based on many years of experience. RIFT simply issues a new, i.e., higher sequence number, empty version of the TIE with a short lifetime given by the purge_lifetime constant and relies on each node to age out and delete each TIE copy independently. Abundant amounts of memory are available today even on low-end platforms and hence keeping those relatively short-lived extra copies for a while is acceptable. The information will age out and in the meantime all computations will deliver correct results if a node leaves the network due to the new information distributed by its adjacent nodes breaking bi-directional connectivity checks in different computations.¶

Once a RIFT node issues a TIE with an ID, it SHOULD preserve the ID as long as feasible (also when the protocol restarts), even if the TIE looses all content. The re-advertisement of an empty TIE fulfills the purpose of purging any information advertised in previous versions. The originator is free to not re-originate the corresponding empty TIE again or originate an empty TIE with relatively short lifetime to prevent large number of long-lived empty stubs polluting the network. Each node MUST time out and clean up the corresponding empty TIEs independently.¶

Upon restart a node MUST be prepared to receive TIEs with its own System ID and supersede them with equivalent, newly generated, empty TIEs with a higher sequence number. As above, the lifetime can be relatively short since it only needs to exceed the necessary propagation and processing delay by all the nodes that are within the TIE's flooding scope.¶

TIE sequence numbers are rolled over using the method described in Appendix A . First sequence number of any spontaneously originated TIE (i.e. not originated to override a detected older copy in the network) MUST be a reasonably unpredictable random number (for example [RFC4086]) in the interval [0, 2^30-1] which will prevent otherwise identical TIE headers to remain "stuck" in the network with content different from TIE originated after reboot. In traditional link-state protocols this is delegated to a 16-bit checksum on packet content. RIFT avoids this design due to the CPU burden presented by computation of such checksums and additional complications tied to the fact that the checksum must be "patched" into the packet after the generation of the content, a difficult proposition in binary hand-crafted formats already and highly incompatible with model-based, serialized formats. The sequence number space is hence consciously chosen to be 64-bits wide to make the occurrence of a TIE with same sequence number but different content as much or even more unlikely than the checksum method. To emulate the "checksum behavior" an implementation could choose to compute a 64-bit checksum or hash function over the TIE content and use that as part of the first sequence number after reboot.¶

6.3.8. Southbound Default Route Origination

Under certain conditions nodes issue a default route in their South Prefix TIEs with costs as computed in Section 6.8.7.1.¶

A node X that¶

1. is not overloaded and¶
2. has southbound or East-West adjacencies¶

SHOULD originate in its south prefix TIE such a default route if and only if¶

1. all other nodes at X's' level are overloaded or¶
2. all other nodes at X's' level have NO northbound adjacencies or¶
3. X has computed reachability to a default route during N-SPF.¶

The term "all other nodes at X's' level" describes obviously just the nodes at the same level in the PoD with a viable lower level (otherwise the Node South TIEs cannot be reflected. The nodes in PoD 1 and PoD 2 are "invisible" to each other).¶

A node originating a southbound default route SHOULD install a default discard route if it did not compute a default route during N-SPF. This basically means that the top of the fabric will drop traffic for unreachable addresses.¶

6.3.9. Northbound TIE Flooding Reduction

RIFT chooses only a subset of northbound nodes to propagate flooding and with that both balances it (to prevent 'hot' flooding links) across the fabric as well as reduces its volume. The solution is based on several principles:¶

1. a node MUST flood self-originated North TIEs to all the reachable nodes at the level above which is called the node's "parents";¶
2. it is typically not necessary that all parents reflood the North TIEs to achieve a complete flooding of all the reachable nodes two levels above which we call the node's "grandparents";¶
3. to control the volume of its flooding two hops North and yet keep it robust enough, it is advantageous for a node to select a subset of its parents as "Flood Repeaters" (FRs), which when combined, deliver two or more copies of its flooding to all of its parents, i.e. the originating node's grandparents;¶
4. nodes at the same level do not have to agree on a specific algorithm to select the FRs, but overall load balancing should be achieved so that different nodes at the same level should tend to select different parents as FRs (consideration of possible strategies in an unrelated but similar field can be found in [RFC2991]);¶
5. there are usually many solutions to the problem of finding a set of FRs for a given node; the problem of finding the minimal set is (similar to) a NP-Complete problem and a globally optimal set may not be the minimal one if load-balancing with other nodes is an important consideration;¶
6. it is expected that there will often exist sets of equivalent nodes at a level L, defined as having a common set of parents at L+1. Applying this observation at both L and L+1, an algorithm may attempt to split the larger problem in a sum of smaller separate problems;¶
7. it is expected that there will be from time to time a broken link between a parent and a grandparent, and in that case the parent is probably a poor FR due to its lower reliability. An algorithm may attempt to eliminate parents with broken northbound adjacencies first in order to reduce the number of FRs. Albeit it could be argued that relying on higher fanout FRs will slow flooding due to higher replication, load reliability of FR's links is likely a more pressing concern.¶

In a fully connected Clos Network, this means that a node selects one arbitrary parent as FR and then a second one for redundancy. The computation can be relatively simple and completely distributed without any need for synchronization among nodes. In a "PoD" structure, where the Level L+2 is partitioned into silos of equivalent grandparents that are only reachable from respective parents, this means treating each silo as a fully connected Clos Network and solving the problem within the silo.¶

In terms of signaling, a node has enough information to select its set of FRs; this information is derived from the node's parents' Node South TIEs, which indicate the parent's reachable northbound adjacencies to its own parents (the node's grandparents). A node may send a LIE to a northbound neighbor with the optional boolean field you_are_flood_repeater set to false, to indicate that the northbound neighbor is not a flood repeater for the node that sent the LIE. In that case the northbound neighbor SHOULD NOT reflood northbound TIEs received from the node that sent the LIE. If the you_are_flood_repeater is absent or if you_are_flood_repeater is set to true, then the northbound neighbor is a flood repeater for the node that sent the LIE and MUST reflood northbound TIEs received from that node. The element you_are_flood_repeater MUST be ignored if received from a northbound adjacency.¶

This specification provides a simple default algorithm that SHOULD be implemented and used by default on every RIFT node.¶

• let |NA(Node) be the set of Northbound adjacencies of node Node and CN(Node) be the cardinality of |NA(Node);¶
• let |SA(Node) be the set of Southbound adjacencies of node Node and CS(Node) be the cardinality of |SA(Node);¶
• let |P(Node) be the set of node Node's parents;¶
• let |G(Node) be the set of node Node's grandparents. Observe that |G(Node) = |P(|P(Node));¶
• let N be the child node at level L computing a set of FR;¶
• let P be a node at level L+1 and a parent node of N, i.e. bi-directionally reachable over adjacency ADJ(N, P);¶
• let G be a grandparent node of N, reachable transitively via a parent P over adjacencies ADJ(N, P) and ADJ(P, G). Observe that N does not have enough information to check bidirectional reachability of ADJ(P, G);¶
• let R be a redundancy constant integer; a value of 2 or higher for R is RECOMMENDED;¶
• let S be a similarity constant integer; a value in range 0 .. 2 for S is RECOMMENDED, the value of 1 SHOULD be used. Two cardinalities are considered as equivalent if their absolute difference is less than or equal to S, i.e. |a-b|<=S.¶
• let RND be a 64-bit random number (for example [RFC4086]) generated by the system once on startup.¶

The algorithm consists of the following steps:¶

1. Derive a 64-bits number by XOR'ing 'N's System ID with RND.¶

2. Derive a 16-bits pseudo-random unsigned integer PR(N) from the resulting 64-bits number by splitting it in 16-bits-long words W1, W2, W3, W4 (where W1 are the least significant 16 bits of the 64-bits number, and W4 are the most significant 16 bits) and then XOR'ing the circularly shifted resulting words together:¶

   1. (W1<<1) xor (W2<<2) xor (W3<<3) xor (W4<<4);¶

      where << is the circular shift operator.¶

3. Sort the parents by decreasing number of northbound adjacencies (using decreasing System ID of the parent as tie-breaker): sort |P(N) by decreasing CN(P), for all P in |P(N), as ordered array |A(N)¶

4. Partition |A(N) in subarrays |A_k(N) of parents with equivalent cardinality of northbound adjacencies (in other words with equivalent number of grandparents they can reach):¶

   1. set k=0; // k is the ID of the subarrray¶
   2. set i=0;¶

   3. while i < CN(N) do¶

      i)

      set j=i;¶

      ii)

      while i < CN(N) and CN(|A(N)[j]) - CN(|A(N)[i]) <= S¶

      a.

      place |A(N)[i] in |A_k(N) // abstract action, maybe noop¶

      b.

      set i=i+1;¶

      iii)

      /* At this point j is the index in |A(N) of the first member of |A_k(N) and (i-j) is C_k(N) defined as the cardinality of |A_k(N) */¶

      set k=k+1;¶

   /* At this point k is the total number of subarrays, initialized for the shuffling operation below */¶

5. shuffle individually each subarrays |A_k(N) of cardinality C_k(N) within |A(N) using the Durstenfeld variation of Fisher-Yates algorithm that depends on N's System ID:¶

   1. while k > 0 do¶

      i)

      for i from C_k(N)-1 to 1 decrementing by 1 do¶

      a.

      set j to PR(N) modulo i;¶

      b.

      exchange |A_k[j] and |A_k[i];¶

      ii)

      set k=k-1;¶

6. For each grandparent G, initialize a counter c(G) with the number of its south-bound adjacencies to elected flood repeaters (which is initially zero):¶

   1. for each G in |G(N) set c(G) = 0;¶

7. Finally keep as FRs only parents that are needed to maintain the number of adjacencies between the FRs and any grandparent G equal or above the redundancy constant R:¶

   1. for each P in reshuffled |A(N);¶

      i)

      if there exists an adjacency ADJ(P, G) in |NA(P) such that c(G) < R then¶

      a.

      place P in FR set;¶

      b.

      for all adjacencies ADJ(P, G') in |NA(P) increment c(G')¶

   2. If any c(G) is still < R, it was not possible to elect a set of FRs that covers all grandparents with redundancy R¶

Additional rules for flooding reduction:¶

1. The algorithm MUST be re-evaluated by a node on every change of local adjacencies or reception of a parent South TIE with changed adjacencies. A node MAY apply a hysteresis to prevent excessive amount of computation during periods of network instability just like in the case of reachability computation.¶
2. Upon a change of the flood repeater set, a node SHOULD send out LIEs that grant flood repeater status to newly promoted nodes before it sends LIEs that revoke the status to the nodes that have been newly demoted. This is done to prevent transient behavior where the full coverage of grandparents is not guaranteed. Such a condition is sometimes unavoidable in case of lost LIEs but it will correct itself though at possible transient reduction in flooding propagation speeds. The election can use the LIE FSM FloodLeadersChanged event to notify LIE FSMs of necessity to update the sent LIEs.¶
3. A node MUST always flood its self-originated TIEs to all its neighbors.¶
4. A node receiving a TIE originated by a node for which it is not a flood repeater SHOULD NOT reflood such TIEs to its neighbors except for rules in Section 6.3.9, Paragraph 10, Item 6.¶
5. The indication of flood reduction capability MUST be carried in the Node TIEs in the flood_reduction element and MAY be used to optimize the algorithm to account for nodes that will flood regardless.¶
6. A node generates TIDEs as usual but when receiving TIREs or TIDEs resulting in requests for a TIE of which the newest received copy came on an adjacency where the node was not flood repeater it SHOULD ignore such requests on first and only first request. Normally, the nodes that received the TIEs as flooding repeaters should satisfy the requesting node and with that no further TIREs for such TIEs will be generated. Otherwise, the next set of TIDEs and TIREs MUST lead to flooding independent of the flood repeater status. This solves a very difficult incast problem on nodes restarting with a very wide fanout, especially northbound. To retrieve the full database they often end up processing many in-rushing copies whereas this approach load-balances the incoming database between adjacent nodes and flood repeaters and should guarantee that two copies are sent by different nodes to ensure against any losses.¶

6.4.1. Northbound Reachability SPF

N-SPF MUST use exclusively northbound and East-West adjacencies in the computing node's node North TIEs (since if the node is a leaf it may not have generated a Node South TIE) when starting SPF. Observe that N-SPF is really just a one hop variety since Node South TIEs are not re-flooded southbound beyond a single level (or East-West) and with that the computation cannot progress beyond adjacent nodes.¶

Once progressing, the computation uses the next higher level's Node South TIEs to find corresponding adjacencies to verify backlink connectivity. Two unidirectional links MUST be associated to confirm bidirectional connectivity, a process often known as `backlink check`. As part of the check, both Node TIEs MUST contain the correct System IDs and expected levels.¶

The default route found when crossing an E-W link SHOULD be used if and only if¶

1. the node itself does not have any northbound adjacencies and¶
2. the adjacent node has one or more northbound adjacencies¶

This rule forms a "one-hop default route split-horizon" and prevents looping over default routes while allowing for "one-hop protection" of nodes that lost all northbound adjacencies except at the ToF where the links are used exclusively to flood topology information in multi-plane designs.¶

Other south prefixes found when crossing E-W link MAY be used if and only if¶

1. no north neighbors are advertising same or a supersuming non-default prefix and¶
2. the node does not originate a non-default supersuming prefix itself.¶

I.e., the E-W link can be used as a gateway of last resort for a specific prefix only. Using south prefixes across E-W link can be beneficial e.g., on automatic disaggregation in pathological fabric partitioning scenarios.¶

A detailed example can be found in Appendix B.4.¶

6.4.2. Southbound Reachability SPF

S-SPF MUST use the southbound adjacencies in the Node South TIEs exclusively, i.e. progresses towards nodes at lower levels. Observe that E-W adjacencies are NEVER used in this computation. This enforces the requirement that a packet traversing in a southbound direction must never change its direction.¶

S-SPF MUST use northbound adjacencies in node North TIEs to verify backlink connectivity by checking for presence of the link beside correct System ID and level.¶

6.4.3. East-West Forwarding Within a non-ToF Level

Using south prefixes over horizontal links MAY occur if the N-SPF includes East-West adjacencies in computation. It can protect against pathological fabric partitioning cases that leave only paths to destinations that would necessitate multiple changes of forwarding direction between north and south.¶

6.4.4. East-West Links Within ToF Level

E-W ToF links behave in terms of flooding scopes defined in Section 6.3.4 like northbound links and MUST be used exclusively for control plane information flooding. Even though a ToF node could be tempted to use those links during southbound SPF and carry traffic over them this MUST NOT be attempted since it may, in anycast cases, lead to routing loops. An implementation MAY try to resolve the looping problem by following on the ring strictly tie-broken shortest-paths only but the details are outside this specification. And even then, the problem of proper capacity provisioning of such links when they become traffic-bearing in case of failures is vexing and when used for forwarding purposes, they defeat statistical non-blocking guarantees that Clos is providing normally.¶

6.5.1. Positive, Non-transitive Disaggregation

Under normal circumstances, a node's South TIEs contain just the adjacencies and a default route. However, if a node detects that its default IP prefix covers one or more prefixes that are reachable through it but not through one or more other nodes at the same level, then it MUST explicitly advertise those prefixes in a South TIE. Otherwise, some percentage of the northbound traffic for those prefixes would be sent to nodes without corresponding reachability, causing it to be dropped. Even when traffic is not being dropped, the resulting forwarding could 'backhaul' packets through the higher level spines, clearly an undesirable condition affecting the blocking probabilities of the fabric.¶

This specification refers to the process of advertising additional prefixes southbound as 'positive disaggregation'. Such disaggregation is non-transitive, i.e., its effects are always constrained to a single level of the fabric. Naturally, multiple node or link failures can lead to several independent instances of positive disaggregation necessary to prevent looping or bow-tying the fabric.¶

A node determines the set of prefixes needing disaggregation using the following steps:¶

1. A DAG computation in the southern direction is performed first. The North TIEs are used to find all of the prefixes it can reach and the set of next-hops in the lower level for each of them. Such a computation can be easily performed on a Fat Tree by setting all link costs in the southern direction to 1 and all northern directions to infinity. We term set of those prefixes |R, and for each prefix, r, in |R, its set of next-hops is defined to be |H(r).¶
2. The node uses reflected South TIEs to find all nodes at the same level in the same PoD and the set of southbound adjacencies for each. The set of nodes at the same level is termed |N and for each node, n, in |N, its set of southbound adjacencies is defined to be |A(n).¶
3. For a given r, if the intersection of |H(r) and |A(n), for any n, is empty then that prefix r must be explicitly advertised by the node in a South TIE.¶
4. Identical set of disaggregated prefixes is flooded on each of the node's southbound adjacencies. In accordance with the normal flooding rules for a South TIE, a node at the lower level that receives this South TIE SHOULD NOT propagate it south-bound or reflect the disaggregated prefixes back over its adjacencies to nodes at the level from which it was received.¶

To summarize the above in simplest terms: if a node detects that its default route encompasses prefixes for which one of the other nodes in its level has no possible next-hops in the level below, it has to disaggregate it to prevent traffic loss or suboptimal routing through such nodes. Hence, a node X needs to determine if it can reach a different set of south neighbors than other nodes at the same level, which are connected to it via at least one common south neighbor. If it can, then prefix disaggregation may be required. If it can't, then no prefix disaggregation is needed. An example of disaggregation is provided in Appendix B.3.¶

Finally, a possible algorithm is described here:¶

1. Create partial_neighbors = (empty), a set of neighbors with partial connectivity to the node X's level from X's perspective. Each entry in the set is a south neighbor of X and a list of nodes of X.level that can't reach that neighbor.¶
2. A node X determines its set of southbound neighbors X.south_neighbors.¶
3. For each South TIE originated from a node Y that X has which is at X.level, if Y.south_neighbors is not the same as X.south_neighbors but the nodes share at least one southern neighbor, for each neighbor N in X.south_neighbors but not in Y.south_neighbors, add (N, (Y)) to partial_neighbors if N isn't there or add Y to the list for N.¶
4. If partial_neighbors is empty, then node X does not disaggregate any prefixes. If node X is advertising disaggregated prefixes in its South TIE, X SHOULD remove them and re-advertise its South TIEs.¶

A node X computes reachability to all nodes below it based upon the received North TIEs first. This results in a set of routes, each categorized by (prefix, path_distance, next-hop set). Alternately, for clarity in the following procedure, these can be organized by next-hop set as ((next-hops), {(prefix, path_distance)}). If partial_neighbors isn't empty, then the procedure in Figure 17 describes how to identify prefixes to disaggregate.¶

            disaggregated_prefixes = { empty }
            nodes_same_level = { empty }
            for each South TIE
              if (South TIE.level == X.level and
                  X shares at least one S-neighbor with X)
                add South TIE.originator to nodes_same_level
                end if
              end for

            for each next-hop-set NHS
              isolated_nodes = nodes_same_level
              for each NH in NHS
                if NH in partial_neighbors
                  isolated_nodes =
                    intersection(isolated_nodes,
                                 partial_neighbors[NH].nodes)
                  end if
                end for

              if isolated_nodes is not empty
                for each prefix using NHS
                  add (prefix, distance) to disaggregated_prefixes
                  end for
                end if
              end for

            copy disaggregated_prefixes to X's South TIE
            if X's South TIE is different
              schedule South TIE for flooding
              end if

Each disaggregated prefix is sent with the corresponding path_distance. This allows a node to send the same South TIE to each south neighbor. The south neighbor which is connected to that prefix will thus have a shorter path.¶

Finally, to summarize the less obvious points partially omitted in the algorithms to keep them more tractable:¶

1. all neighbor relationships MUST perform backlink checks.¶
2. overload flag as introduced in Section 6.8.2 and carried in the overload schema element have to be respected during the computation. Nodes advertising themselves as overloaded MUST NOT be transited in reachability computation but MUST be used as terminal nodes with prefixes they advertise being reachable.¶
3. all the lower-level nodes are flooded the same disaggregated prefixes since RIFT does not build a South TIE per node which would complicate things unnecessarily. The lower-level node that can compute a southbound route to the prefix will prefer it to the disaggregated route anyway based on route preference rules.¶
4. positively disaggregated prefixes do not have to propagate to lower levels. With that the disturbance in terms of new flooding is contained to a single level experiencing failures.¶
5. disaggregated Prefix South TIEs are not "reflected" by the lower level. Nodes within same level do not need to be aware which node computed the need for disaggregation.¶
6. The fabric is still supporting maximum load balancing properties while not trying to send traffic northbound unless necessary.¶

In case positive disaggregation is triggered and due to the very stable but un-synchronized nature of the algorithm the nodes may issue the necessary disaggregated prefixes at different points in time. This can lead for a short time to an "incast" behavior where the first advertising router based on the nature of longest prefix match will attract all the traffic. Different implementation strategies can be used to lessen that effect, but those are outside the scope of this specification.¶

It is worth observing that, in a single plane ToF, this disaggregation prevents traffic loss up to (K_LEAF * P) link failures in terms of Section 5.2 or, in other terms, it takes at minimum that many link failures to partition the ToF into multiple planes.¶

6.5.2. Negative, Transitive Disaggregation for Fallen Leaves

As explained in Section 5.3 failures in multi-plane ToF or more than (K_LEAF * P) links failing in single plane design can generate fallen leaves. Such scenario cannot be addressed by positive disaggregation only and needs a further mechanism.¶

6.7.1. Terminology

The interdependencies between the different flags and the configured level can be somewhat vexing at first and it may take multiple reads of the glossary to comprehend them.¶

Automatic Level Derivation:

Procedures which allow nodes without level configured to derive it automatically. Only applied if CONFIGURED_LEVEL is undefined.¶

UNDEFINED_LEVEL:

A "null" value that indicates that the level has not been determined and has not been configured. Schemas normally indicate that by a missing optional value without an available defined default.¶

LEAF_ONLY:

An optional configuration flag that can be configured on a node to make sure it never leaves the "bottom of the hierarchy". TOP_OF_FABRIC flag and CONFIGURED_LEVEL cannot be defined at the same time as this flag. It implies CONFIGURED_LEVEL value of leaf_level. It is indicated in the leaf_only schema element.¶

TOP_OF_FABRIC:

A configuration flag that MUST be provided on all ToF nodes. LEAF_FLAG and CONFIGURED_LEVEL cannot be defined at the same time as this flag. It implies a CONFIGURED_LEVEL value. In fact, it is basically a shortcut for configuring same level at all ToF nodes which is unavoidable since an initial 'seed' is needed for other ZTP nodes to derive their level in the topology. The flag plays an important role in fabrics with multiple planes to enable successful negative disaggregation (Section 6.5.2). It is carried in the top_of_fabric schema element. A standards conforming RIFT implementation implies a CONFIGURED_LEVEL value of top_of_fabric_level in case of TOP_OF_FABRIC. This value is kept reasonably low to allow for fast ZTP re-convergence on failures.¶

CONFIGURED_LEVEL:

A level value provided manually. When this is defined (i.e. it is not an UNDEFINED_LEVEL) the node is not participating in ZTP in the sense of deriving its own level based on other nodes' information. TOP_OF_FABRIC flag is ignored when this value is defined. LEAF_ONLY can be set only if this value is undefined or set to leaf_level.¶

DERIVED_LEVEL:

Level value computed via automatic level derivation when CONFIGURED_LEVEL is equal to UNDEFINED_LEVEL.¶

LEAF_2_LEAF:

An optional flag that can be configured on a node to make sure it supports procedures defined in Section 6.8.9. It is a capability that implies LEAF_ONLY and the corresponding restrictions. TOP_OF_FABRIC flag is ignored when set at the same time as this flag. It is carried in the leaf_only_and_leaf_2_leaf_procedures schema flag.¶

LEVEL_VALUE:

With ZTP, the original definition of "level" in Section 3.1 is both extended and relaxed. First, level is defined now as LEVEL_VALUE and is the first defined value of CONFIGURED_LEVEL followed by DERIVED_LEVEL. Second, it is possible for nodes to be more than one level apart to form adjacencies if any of the nodes is at least LEAF_ONLY.¶

Valid Offered Level (VOL):

A neighbor's level received in a valid LIE (i.e. passing all checks for adjacency formation while disregarding all clauses involving level values) persisting for the duration of the holdtime interval on the LIE. Observe that offers from nodes offering level value of leaf_level do not constitute VOLs (since no valid DERIVED_LEVEL can be obtained from those and consequently not_a_ztp_offer flag MUST be ignored). Offers from LIEs with not_a_ztp_offer being true are not VOLs either. If a node maintains parallel adjacencies to the neighbor, VOL on each adjacency is considered as equivalent, i.e. the newest VOL from any such adjacency updates the VOL received from the same node.¶

Highest Available Level (HAL):

Highest defined level value received from all VOLs received.¶

Highest Available Level Systems (HALS):

Set of nodes offering HAL VOLs.¶

Highest Adjacency ThreeWay (HAT):

Highest neighbor level of all the formed ThreeWay adjacencies for the node.¶

6.7.4. Level Determination Procedure

A node starting up with UNDEFINED_VALUE (i.e. without a CONFIGURED_LEVEL or any leaf or TOP_OF_FABRIC flag) MUST follow those additional procedures:¶

1. It advertises its LEVEL_VALUE on all LIEs (observe that this can be UNDEFINED_LEVEL which in terms of the schema is simply an omitted optional value).¶
2. It computes HAL as numerically highest available level in all VOLs.¶
3. It chooses then MAX(HAL-1,0) as its DERIVED_LEVEL. The node then starts to advertise this derived level.¶
4. A node that lost all adjacencies with HAL value MUST hold down computation of new DERIVED_LEVEL for at least one second unless it has no VOLs from southbound adjacencies. After the holddown timer expired, it MUST discard all received offers, recompute DERIVED_LEVEL and announce it to all neighbors.¶
5. A node MUST reset any adjacency that has changed the level it is offering and is in ThreeWay state.¶
6. A node that changed its defined level value MUST readvertise its own TIEs (since the new PacketHeader will contain a different level than before). The sequence number of each TIE MUST be increased.¶
7. After a level has been derived the node MUST set the not_a_ztp_offer on LIEs towards all systems offering a VOL for HAL.¶
8. A node that changed its level SHOULD flush from its link state database TIEs of all other nodes, otherwise stale information may persist on "direction reversal", i.e., nodes that seemed south are now north or east-west. This will not prevent the correct operation of the protocol but could be slightly confusing operationally.¶

A node starting with LEVEL_VALUE being 0 (i.e., it assumes a leaf function by being configured with the appropriate flags or has a CONFIGURED_LEVEL of 0) MUST follow those additional procedures:¶

1. It computes HAT per procedures above but does not use it to compute DERIVED_LEVEL. HAT is used to limit adjacency formation per Section 6.2.¶

It MAY also follow modified procedures:¶

1. It may pick a different strategy to choose VOL, e.g. use the VOL value with highest number of VOLs. Such strategies are only possible since the node always remains "at the bottom of the fabric" while another layer could "invert" the fabric by picking its preferred VOL in a different fashion rather than always trying to achieve the highest viable level.¶

6.8.1. Route Preferences

Since RIFT distinguishes between different route types such as e.g. external routes from other protocols and additionally advertises special types of routes on disaggregation, the protocol MUST tie-break internally different types on a clear preference scale to prevent traffic loss or loops. The preferences are given in the schema type RouteType.¶

Table 5 contains the route type as derived from the TIE type carrying it. Entries are sorted from the most preferred route type to the least preferred route type.¶

6.8.2. Overload Bit

Overload attribute is specified in the packet encoding schema (Section 7) in the overload flag.¶

The overload flag MUST be respected by all necessary SPF computations. A node with the overload flag set SHOULD advertise all locally hosted prefixes both northbound and southbound, all other southbound prefixes SHOULD NOT be advertised.¶

Leaf nodes SHOULD set the overload attribute on all originated Node TIEs. If spine nodes were to forward traffic not intended for the local node, the leaf node would not be able to prevent routing/forwarding loops as it does not have the necessary topology information to do so.¶

6.8.4. Mobility

The RIFT control plane MUST maintain the real time status of every prefix, to which port it is attached, and to which leaf node that port belongs. This is still true in cases of IP mobility where the point of attachment may change several times a second.¶

There are two classic approaches to explicitly maintain this information, "timestamp" and "sequence counter" as follows:¶

timestamp:

With this method, the infrastructure SHOULD record the precise time at which the movement is observed. One key advantage of this technique is that it has no dependency on the mobile device. One drawback is that the infrastructure MUST be precisely synchronized in order to be able to compare timestamps as the points of attachment change. This could be accomplished by utilizing Precision Time Protocol (PTP) IEEE Std. 1588 [IEEEstd1588] or 802.1AS [IEEEstd8021AS] which is designed for bridged LANs. Both the precision of the synchronization protocol and the resolution of the timestamp must beat the shortest possible roaming time on the fabric. Another drawback is that the presence of a mobile device may only be observed asynchronously, such as when it starts using an IP protocol like ARP [RFC0826], IPv6 Neighbor Discovery [RFC4861], IPv6 Stateless Address Configuration [RFC4862], DHCP [RFC2131], or DHCPv6 [RFC8415].¶

sequence counter:

With this method, a mobile device notifies its point of attachment on arrival with a sequence counter that is incremented upon each movement. On the positive side, this method does not have a dependency on a precise sense of time, since the sequence of movements is kept in order by the mobile device. The disadvantage of this approach is the need for support for protocols that may be used by the mobile device to register its presence to the leaf node with the capability to provide a sequence counter. Well-known issues with sequence counters such as wrapping and comparison rules MUST be addressed properly. Sequence numbers MUST be compared by a single homogenous source to make operation feasible. Sequence number comparison from multiple heterogeneous sources would be extremely difficult to implement.¶

RIFT supports a hybrid approach by using an optional 'PrefixSequenceType' attribute (that is also called a monotonic_clock in the schema) that consists of a timestamp and optional sequence number field. In case of a negatively distributed prefix this attribute MUST NOT be included by the originator and it MUST be ignored by all nodes during computation. When this attribute is present (observe that per data schema the attribute itself is optional but in case it is included the 'timestamp' field is required):¶

• The leaf node MAY advertise a timestamp of the latest sighting of a prefix, e.g., by snooping IP protocols or the node using the time at which it advertised the prefix. RIFT transports the timestamp within the desired Prefix North TIEs as [IEEEstd1588] timestamp.¶
• RIFT MAY interoperate with "Registration Extensions for 6LoWPAN Neighbor Discovery" [RFC8505], which provides a method for registering a prefix with a sequence number called a Transaction ID (TID). In such cases, RIFT SHOULD transport the derived TID without modification.¶
• RIFT also defines an abstract negative clock (ASNC) (also called an 'undefined' clock). The ASNC MUST be considered older than any other defined clock. By default, when a node receives a Prefix North TIE that does not contain a 'PrefixSequenceType' attribute, it MUST interpret the absence as the ASNC.¶
• Any prefix present on the fabric in multiple nodes that have the same clock is considered as anycast.¶
• RIFT specification assumes that all nodes are being synchronized within at least 200 milliseconds or less. This is achievable through the use of NTP [RFC5905]. An implementation MAY provide a way to reconfigure a domain to a different value, and provides for this purpose a variable called MAXIMUM_CLOCK_DELTA.¶

6.8.6. Interactions with BFD

RIFT MAY incorporate BFD [RFC5881] to react quickly to link failures. In such case, the following procedures are introduced:¶

• After RIFT ThreeWay hello adjacency convergence a BFD session MAY be formed automatically between the RIFT endpoints without further configuration using the exchanged discriminators that are equal to the local_id in the LIEPacket. The capability of the remote side to support BFD is carried in the LIEs in LinkCapabilities.¶
• In case an established BFD session goes Down after it was Up, RIFT adjacency SHOULD be re-initialized and subsequently started from Init after it receives a consecutive BFD Up.¶
• In case of parallel links between nodes each link MAY run its own independent BFD session or they MAY share a session. The specific manner in which this is implemented is outside the scope of this document.¶
• If link identifiers or BFD capabilities change, both the LIE and any BFD sessions SHOULD be brought down and back up again. In case only the advertised capabilities change, the node MAY choose to persist the BFD session.¶
• Multiple RIFT instances MAY choose to share a single BFD session, in such cases the behavior for which discriminators are used is undefined. However, RIFT MAY advertise the same link ID for the same interface in multiple instances to "share" discriminators.¶
• The BFD TTL follows [RFC5082].¶

6.8.7. Fabric Bandwidth Balancing

A well understood problem in fabrics is that, in case of link failures, it would be ideal to rebalance how much traffic is sent to switches in the next level based on available ingress and egress bandwidth.¶

RIFT supports a light-weight mechanism that can deal with the problem based on the fact that RIFT is loop-free.¶

6.8.8. Label Binding

A node MAY advertise in its LIEs, a locally significant, downstream assigned, interface specific label. One use of such a label is a hop-by-hop encapsulation allowing forwarding planes to be easily distinguished among multiple RIFT instances.¶

6.8.9. Leaf to Leaf Procedures

RIFT implementations SHOULD support special East-West adjacencies between leaf nodes. Leaf nodes supporting these procedures MUST:¶

• advertise the LEAF_2_LEAF flag in its node capabilities and¶
• set the overload flag on all leaf's Node TIEs and¶
• flood only a node's own north and south TIEs over E-W leaf adjacencies and¶
• always use E-W leaf adjacency in all SPF computations and¶
• install a discard route for any advertised aggregate routes in a leaf's TIE and¶
• never form southbound adjacencies.¶

This will allow the E-W leaf nodes to exchange traffic strictly for the prefixes advertised in each other's north prefix TIEs since the southbound computation will find the reverse direction in the other node's TIE and install its north prefixes.¶

6.8.11. One-Hop Healing of Levels with East-West Links

Based on the rules defined in Section 6.4, Section 6.3.8 and given the presence of E-W links, RIFT can provide a one-hop protection for nodes that have lost all their northbound links. This can also be applied to multi-plane designs where complex link set failures occur at the ToF when links are exclusively used for flooding topology information. Appendix B.4 outlines this behavior.¶

6.9.1. Security Model

An inherent property of any security and ZTP architecture is the resulting trade-off in regard to integrity verification of the information distributed through the fabric vs. provisioning and auto-configuration requirements. At a minimum the security of an established adjacency should be ensured. The stricter the security model the more provisioning must take over the role of ZTP.¶

RIFT supports the following security models to allow for flexible control by the operator.¶

• The most security conscious operators may choose to have control over which ports interconnect between a given pair of nodes, such a model is called the "Port-Association Model" (PAM). This is achievable by configuring each pair of directly connected ports with a designated shared key or public/private key pair.¶
• In physically secure data center locations, operators may choose to control connectivity between entire nodes, called here the "Node-Association Model" (NAM). A benefit of this model is that it allows for simplified port sparing.¶
• In the most relaxed environments, an operator may only choose to control which nodes join a particular fabric. This is denoted as the "Fabric-Association Model" (FAM). This is achievable by using a single shared secret across the entire fabric. Such flexibility makes sense when servers are considered as leaf devices, as those are replaced more often than network nodes. In addition, this model allows for simplified node sparing.¶
• These models may be mixed throughout the fabric depending upon security requirements at various levels of the fabric and willingness to accept increased provisioning complexity.¶

In order to support the cases mentioned above, RIFT implementations supports, through operator control, mechanisms that allow for:¶

1. specification of the appropriate level in the fabric,¶
2. discovery and reporting of missing connections,¶
3. discovery and reporting of unexpected connections while preventing them from forming insecure adjacencies.¶

Operators may only choose to configure the level of each node, but not explicitly configure which connections are allowed. In this case, RIFT will only allow adjacencies to establish between nodes that are in adjacent levels. Operators with the lowest security requirements may not use any configuration to specify which connections are allowed. Nodes in such fabrics could rely fully on ZTP and only established adjacencies between nodes in adjacent levels. Figure 33 illustrates inherent tradeoffs between the different security models.¶

Some level of link quality verification may be required prior to an adjacency being used for forwarding. For example, an implementation may require that a BFD session comes up before advertising the adjacency.¶

For the cases outlined above, RIFT has two approaches to enforce that a local port is connected to the correct port on the correct remote node. One approach is to piggy-back on RIFT's authentication mechanism. Assuming the provisioning model (e.g. YANG) is flexible enough, operators can choose to provision a unique authentication key for the following conceptual models:¶

1. each pair of ports in "port-association model" or¶
2. each pair of switches in "node-association model" or¶
3. the entire fabric in "fabric-association model".¶

The other approach is to rely on the System ID, port-id and level fields in the LIE message to validate an adjacency against the expected cabling topology, and optionally introduce some new rules in the FSM to allow the adjacency to come up if the expectations are met.¶

         ^                 /\                  |
        /|\               /  \                 |
         |               /    \                |
         |              / PAM  \               |
     Increasing        /        \          Increasing
     Integrity        +----------+         Flexibility
         &           /    NAM     \            &
    Increasing      +--------------+         Less
    Provisioning   /      FAM       \     Configuration
         |        /                  \         |
         |       +--------------------+       \|/
         |      /  Zero Configuration  \       v
               +------------------------+

6.9.2. Security Mechanisms

RIFT Security goals are to ensure:¶

1. authentication¶
2. message integrity¶
3. the prevention of replay attacks¶
4. low processing overhead¶
5. efficient messaging¶

unless no security is deployed by means of using `undefined_securitykey_id` as key identifiers.¶

Message confidentiality is a non-goal.¶

The model in the previous section allows a range of security key types that are analogous to the various security association models. PAM and NAM allow security associations at the port or node level using symmetric or asymmetric keys that are pre-installed. FAM argues for security associations to be applied only at a group level or to be refined once the topology has been established. RIFT does not specify how security keys are installed or updated, though it does specify how the key can be used to achieve security goals.¶

The protocol has provisions for "weak" nonces to prevent replay attacks and includes authentication mechanisms comparable to [RFC5709] and [RFC7987].¶

6.9.3. Security Envelope

A serialized schema ProtocolPacket MUST be carried in a secure envelope illustrated in Figure 34. The ProtocolPacket MUST be serialized using the default Thrift's Binary Protocol. Any value in the packet following a security fingerprint MUST be used by a receiver only after the fingerprint generated based on acceptable, advertised key ID has been validated against the data covered by it bare exceptions arising from operational exigencies where, based on local configuration, a node MAY allow for the envelope's integrity checks to be skipped and for behavior specified in Section 6.9.6. This means that for all packets, in case the node is configured to validate the outer fingerprint based on a key ID, an unexpected key ID or fingerprint not validating against expected key ID will lead to packet rejection. Further, in case of reception of a TIE, and the receiver being configured to validate the originator by checking the TIE Origin Security Envelope Header fingerprint against a key ID, an incorrect key ID or inner fingerprint not validating against the key ID will lead to the rejection of the packet.¶

For reasons of clarity it is important to observe that the specification uses the word fingerprint and signature interchangeably since the specific properties of the fingerprint part of the envelope depend on the algorithms used to insure the payload integrity. Moreover, any security chosen never implies encryption due to performance impact involved but only fingerprint or signature generation and validation.¶

An implementation MUST implement at least both sending and receiving HMAC-SHA256 fingerprints as defined in Section 10.2 to ensure interoperability but MAY use `undefined_securitykey_id` by default.¶

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

   UDP Header:
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Source Port         |       RIFT destination port   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           UDP Length          |        UDP Checksum           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Outer Security Envelope Header:
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           RIFT MAGIC          |         Packet Number         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Reserved   |  RIFT Major   | Outer Key ID  | Fingerprint   |
   |               |    Version    |               |    Length     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   ~       Security Fingerprint covers all following content       ~
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Weak Nonce Local              | Weak Nonce Remote             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Remaining TIE Lifetime (all 1s in case of LIE)     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   TIE Origin Security Envelope Header:
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |              TIE Origin Key ID                |  Fingerprint  |
   |                                               |    Length     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   ~       Security Fingerprint covers all following content       ~
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Serialized RIFT Model Object
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   ~                Serialized RIFT Model Object                   ~
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

RIFT MAGIC:

16 bits. Constant value of 0xA1F7 that allows easy classification of RIFT packets independent of the UDP port used.¶

Packet Number:

16 bits. An optional, per adjacency, per packet type number set using the sequence number arithmetic defined in Appendix A. If the arithmetic in Appendix A is not used the node MUST set the value to undefined_packet_number. This number can be used to detect losses and misordering in flooding for either operational purposes or in implementation to adjust flooding behavior to current link or buffer quality. This number MUST NOT be used to discard or validate the correctness of packets. Packet numbers are incremented on each interface and within that for each type of packet independently. This allows parallelizing packet generation and processing for different types within an implementation if so desired.¶

RIFT Major Version:

8 bits. This value MUST be set to `protocol_major_version` defined in the schema and used to serialize the object contained. It allows checking whether protocol versions are compatible on both sides, i.e., which schema version is necessary to decode the serialized object. An implementation MUST drop packets with unexpected values and MAY report a problem. The specification of how an implementation may negotiate the schema's major version is outside the scope of this document.¶

Outer Key ID:

8 bits. A simple, unstructured value acting as indirection into a structure holding an algorithm and any related secrets necessary to validate any provided outer security fingerprint or signature. Value undefined_securitykey_id means that no valid fingerprint was computed or is provided, otherwise one of the algorithms in Section 10.2 MUST be used to compute the fingerprint. This Key ID scope is local to the nodes on both ends of the adjacency.¶

TIE Origin Key ID:

24 bits. A simple, unstructured value acting as indirection into a structure holding an algorithm and any related secrets necessary to validate any provided inner security fingerprint or signature. Value undefined_securitykey_id means that no valid fingerprint was computed, otherwise one of the algorithms in Section 10.2 MUST be used to compute the fingerprint.. This Key ID scope is global to the RIFT instance since it may imply the originator of the TIE so the contained object does not have to be de-serialized to obtain the originator.¶

Length of Fingerprint:

8 bits. Length in 32-bit multiples of the following fingerprint (not including lifetime or weak nonces). It allows the structure to be navigated when an unknown key type is present. To clarify, a common corner case when this value is set to 0 is when it signifies an empty (0 bytes long) security fingerprint.¶

Security Fingerprint:

32 bits * Length of Fingerprint. This is a signature that is computed over all data following after it. If the significant bits of fingerprint are fewer than the 32 bits padded length then the significant bits MUST be left aligned and remaining bits on the right padded with 0s. When using PKI (Public Key Infrastructure) the Security fingerprint originating node uses its private key to create the signature. The original packet can then be verified provided the public key is shared and current. Methodology to negotiate, distribute, or roll over keys are outside the scope of this document.¶

Remaining TIE Lifetime:

32 bits. In case of anything but TIEs this field MUST be set to all ones and Origin Security Envelope Header MUST NOT be present in the packet. For TIEs this field represents the remaining lifetime of the TIE and Origin Security Envelope Header MUST be present in the packet.¶

Weak Nonce Local:

16 bits. Local Weak Nonce of the adjacency as advertised in LIEs.¶

Weak Nonce Remote:

16 bits. Remote Weak Nonce of the adjacency as received in LIEs.¶

TIE Origin Security Envelope Header:

It MUST be present if and only if the Remaining TIE Lifetime field is not all ones. It carries through the originators Key ID and corresponding fingerprint of the object to protect TIE from modification during flooding. This ensures origin validation and integrity (but does not provide validation of a chain of trust).¶

Observe that due to the schema migration rules per Section 7 the contained model can be always decoded if the major version matches and the envelope integrity has been validated. Consequently, description of the TIE is available to flood it properly including unknown TIE types.¶

6.9.4. Weak Nonces

The protocol uses two 16-bit nonces to salt generated signatures. The term "nonce" is used a bit loosely since RIFT nonces are not being changed in every packet as often common in cryptography. For efficiency purposes they are changed at a high enough frequency to dwarf practical replay attack attempts. And hence, such nonces are called from this point on "weak" nonces.¶

Any implementation using outer key ID different from `undefined_securitykey_id` MUST generate and wrap around local nonces properly and SHOULD do it even if not using any algorithm in Section 10.2. When a nonce increment leads to undefined_nonce value, the value MUST be incremented again immediately. All implementations MUST reflect the neighbor's nonces. An implementation SHOULD increment a chosen nonce on every LIE FSM transition that ends up in a different state from the previous one and MUST increment its nonce at least every nonce_regeneration_interval if using any algorithm in Section 10.2 (such considerations allow for efficient implementations without opening a significant security risk). When flooding TIEs, the implementation MUST use recent (i.e. within allowed difference) nonces reflected in the LIE exchange. The schema specifies in maximum_valid_nonce_delta the maximum allowable nonce value difference on a packet compared to reflected nonces in the LIEs. Any packet received with nonces deviating more than the allowed delta MUST be discarded without further computation of signatures to prevent computation load attacks. The delta is either a negative or positive difference that a mirrored nonce can deviate from local value to be considered valid. If nonces are not changed on every packet but at the maximum interval on both sides this opens statistically a maximum_valid_nonce_delta/2 window for identical LIEs, TIE and TI(x)E replays. The interval cannot be too small since LIE FSM may change states fairly quickly during ZTP without sending LIEs and additionally, UDP can both loose as well as misorder packets.¶

In cases where a secure implementation does not receive signatures or receives undefined nonces from a neighbor (indicating that it does not support or verify signatures), it is a matter of local policy as to how those packets are treated. A secure implementation MAY refuse forming an adjacency with an implementation that is not advertising signatures or valid nonces, or it MAY continue signing local packets while accepting a neighbor's packets without further security validation.¶

As a necessary exception, an implementation MUST advertise the remote nonce value as undefined_nonce when the FSM is not in TwoWay or ThreeWay state and accept an undefined_nonce for its local nonce value on packets in any other state than ThreeWay.¶

As an optional optimization, an implementation MAY send one LIE with previously negotiated neighbor's nonce to try to speed up a neighbor's transition from ThreeWay to OneWay and MUST revert to sending undefined_nonce after that.¶

6.9.5. Lifetime

Reflooding same TIE version quickly with small variations in its lifetime may lead to an excessive number of security fingerprint computations. To avoid this, the application generating the fingerprints for flooded TIEs MAY round the value down to the next rounddown_lifetime_interval on the packet header to reuse previous computation results. TIEs flooded with such rounded lifetimes only will limit the amount of computations necessary during transitions that lead to advertisement of same TIEs with same information within a short period of time.¶

6.9.6. Security Association Changes

No mechanism is specified to convert a security envelope for the same Key ID from one algorithm to another once the envelope is operational. The recommended procedure to change to a new algorithm is to take the adjacency down, make the necessary changes to the secret and algorithm used by the according key ID, and bring the adjacency back up. Obviously, an implementation MAY choose to stop verifying security envelope for the duration of algorithm change to keep the adjacency up but since this introduces a security vulnerability window, such roll-over SHOULD NOT be recommended. Other approaches, such as accepting multiple algorithms for same key ID for a configured time window are possible but in the realm of implementation choices rather than protocol specification.¶