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

for each TIEPacket:
    TIEHeader = TIEPacket.TIEHeader
    TIEElement = TIEPacket.TIEElement

    seq_nr = TIEHeader.seq_nr

    TIEID = TIEHeader.TIEID
    direction = TIEID.direction

    # System ID
    originator = TIEID.originator

    # TIETypeType
    tietype = TIEID.tietype
    tie_nr = TIEID.tie_nr

    if X.direction > Y.direction:
        return X.direction
    else if X.direction < Y.direction:
        return Y.direction
    else if X.originator > Y.originator:
        return X.originator
    else if X.originator < Y.originator:
        return Y.originator
    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 equal

                    else:
                        return TIE with largest lifetime_left
                else:
                    return X.seq_nr compared to Y.seq_nr
            else:
                return X.tie_nr compared to Y.tie_nr
        else:
            return X.TIEType compared to Y.TIEType

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 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 timeout 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 combined together 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 amongst 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 together 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 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.¶