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 southbound 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 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. 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, Figure 15 shows the TIEs generated by some nodes.¶

ToF 21 South TIEs:
South Node 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(...))
    )
  )
South Prefix TIE:
  PrefixTIEElement(prefixes(0/0, metric 1), (::/0, metric 1))

Spine 111 South TIEs:
South Node 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(...))
    )
  )
South Prefix TIE:
  PrefixTIEElement(prefixes(0/0, metric 1), (::/0, metric 1))

Spine 111 North TIEs:
North Node 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(...))
    )
  )
North Prefix TIE:
  PrefixTIEElement(prefixes(Spine 111.loopback)

Spine 121 South TIEs:
South Node 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(...))
    )
  )
South Prefix TIE:
  PrefixTIEElement(prefixes(0/0, metric 1), (::/0, metric 1))

Spine 121 North TIEs:
North Node 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(...))
    )
  )
North Prefix TIE:
  PrefixTIEElement(prefixes(Spine 121.loopback)

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

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

For Node TIEs to carry more adjacencies than fit into an MTU-sized packet, the neighbors element 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. the 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 TIEElement. In case of a mismatch between TIETypeType in the TIEID and the present element, the unexpected elements MUST be ignored. In case of the lack of an expected element in the TIE, an error MUST be reported and the TIE MUST be ignored. The positive_disaggregation_prefixes and positive_external_disaggregation_prefixes elements MUST be advertised southbound only and ignored in North TIEs. The negative_disaggregation_prefixes element 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 multi-plane 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 use the destination address on which the LIE adjacency has been formed.¶

TIEs are uniquely identified by the TIEID schema element. 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 the same TIE.¶

TIEHeader can also carry an origination_time schema element (for fabrics that utilize precision timing) that 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 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 reflooded with the scope identical to the scope of a prefix TIE. This allows for future extensions of the protocol that are within the same major schema and that have types that are opaque to some nodes; some restrictions are 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 South Node TIEs, consisting of all node's adjacencies and South Prefix 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 South Node 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 the algorithms described in Section 6.4. In that way, nodes at same level can learn about each other without using 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 southern flooding scopes, except in case of ToF East-West links (rings), which are basically performing northbound flooding.¶

South Node TIE "south reflection" enables support of positive disaggregation on failures, as described in Section 6.5, and flooding reduction, as described 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. In its LIEs, a node MAY set 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 it is south of the sender and should ignore the indication if it is 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 descriptions of the LSDB and TIREs, which perform the function of requesting unknown TIEs as well as confirming the reception of flooded TIEs. The content of TIDEs and TIREs is governed by Table 3.¶

6.3.7. Purging and Rollovers

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 reorigination 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 bidirectional 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 reoriginate the corresponding empty TIE again or originate an empty TIE with a relatively short lifetime to prevent a 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 . The 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³⁰-1], which will prevent otherwise identical TIE headers to remain "stuck" in the network with content different from the TIE originated after reboot. In typical 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, which is 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 the 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 such a default route in its South Prefix TIE 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" obviously describes just the nodes at the same level in the PoD with a viable lower level (otherwise, the South Node 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) an 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 sets of equivalent nodes at a level L will often exist, 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; and¶
7. it is expected that there will be a broken link between a parent and a grandparent from time to time, 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 the 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' South Node 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 you_are_flood_repeater is absent or 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 FRs;¶
• let P be a node at level L+1 and a parent node of N, i.e., bidirectionally 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, and 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, as described in [RFC4086]) generated by the system once on startup.¶

The algorithm consists of the following steps:¶

1. Derive a 64-bit number by XORing N's System ID with RND.¶

2. Derive a 16-bit pseudo-random unsigned integer PR(N) from the resulting 64-bit number by splitting it into 16-bit-long words W1, W2, W3, W4 (where W1 are the least significant 16 bits of the 64-bit number, and W4 are the most significant 16 bits) and then XORing 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 a tie-breaker): sort |P(N) by decreasing CN(P), for all P in |P(N), as the 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 subarray¶
   2. set i=0;¶

   3. while i < CN(N) do¶

      1. set j=i;¶

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

         1. place |A(N)[i] in |A_k(N) // abstract action, maybe noop¶
         2. set i=i+1;¶

      3. /* 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 each subarrays |A_k(N) of cardinality C_k(N) within |A(N) individually using the Durstenfeld variation of the Fisher-Yates algorithm that depends on N's System ID:¶

   1. while k > 0 do¶

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

         1. set j to PR(N) modulo i;¶
         2. exchange |A_k[j] and |A_k[i];¶
      2. set k=k-1;¶

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

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

7. Finally, only keep FRs as 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):¶

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

         1. place P in FR set;¶
         2. for all adjacencies ADJ(P, G') in |NA(P) increment c(G')¶
8. 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 an 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 at possible transient reduction in flooding propagation speeds. The election can use the LIE FSM FloodLeadersChanged event to notify LIE FSMs of the 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 the rules described 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 a flood repeater, it SHOULD ignore such requests on only the 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 inrushing 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 North Node TIEs (since if the node is a leaf, it may not have generated a South Node TIE) when starting SPF. Observe that N-SPF is really just a one-hop variety since South Node TIEs are not reflooded 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 South Node 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 links MAY be used if and only if¶

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

That is, the E-W link can be used as a gateway of last resort for a specific prefix only. Using south prefixes across an 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 South Node 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 North Node TIEs to verify backlink connectivity by checking for the presence of the link beside the 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 a 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. The set of those prefixes is referred to as |R; for each prefix r in |R, its set of next hops is referred to as |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. An 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 southbound 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 a 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 that 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. The overload flag as introduced in Section 6.8.2 and carried in the overload schema element has 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 South Prefix TIEs are not "reflected" by the lower level. Nodes within the same level do not need to be aware of 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 unsynchronized nature of the algorithm, the nodes may issue the necessary disaggregated prefixes at different points in time. For a short time, this can lead to an "incast" behavior where the first advertising router based on the nature of the 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 that allow nodes without a 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". The TOP_OF_FABRIC flag and CONFIGURED_LEVEL cannot be defined at the same time as this flag. It implies a 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 the 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 reconvergence 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. The 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. The 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, the 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 the level value of leaf_level do not constitute VOLs (since no valid DERIVED_LEVEL can be obtained from those and consequently the 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 these 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 the numerically highest available level in all VOLs.¶
3. Then, it chooses 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 the HAL value MUST holddown computation of the 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 re-advertise 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 TIEs of all other nodes from its LSDB; 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 this additional procedure:¶

1. It computes HAT per the 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 this modified procedure:¶

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 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.¶