RIFT: Routing in Fat Trees

4.2.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 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 4.2.5 explains further details.¶

All TIE types are mostly symmetrical in both diredctions. The (Appendix B.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 considered. 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 4.2.3.9 and Section 4.3.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 disjoint sets of neighbors MUST be joined during corresponding computation. Nevertheless, in case 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¶

Since the receiving node cannot control the arrival order of TIEs, it is expected that an implementation will use the value of any of the valid TIEs it received.¶

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

A ToF node MUST include 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 mismatch 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 4.2.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 ignored otherwise.¶

4.2.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. `TIEID` space is 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).¶

`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. This allows for future extensions of the protocol within the same major schema with types opaque to some nodes with some restrictions.¶

4.2.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 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 level from which it was received. It should be noted that East-West links are included in South TIE flooding (except at ToF level); those TIEs need to be flooded to satisfy algorithms in Section 4.2.4. In that way nodes at same level can learn about each other without a lower level except in case of leaf level. The precise, normative flooding scopes are given in Table 3. Those rules govern as well 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" allows to support positive disaggregation on failures as described in in Section 4.2.5 and flooding reduction in Section 4.2.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.¶

As an example 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.¶

4.2.3.5. 'Flood Only Node TIEs' Bit

RIFT includes an optional ECN (Explicit Congestion Notification) mechanism to prevent "flooding inrush" on restart or bring-up with many southbound neighbors. A node MAY set on its LIEs the corresponding `you_are_sending_too_quickly` flag to indicate to the neighbor that it should temporarily only flood Node TIEs to it and slow down the flooding of any other TIEs. It SHOULD only set it 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.¶

This mechanism is most useful in the southbound direction. The distribution of Node TIEs 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 suppressing flooding of northbound prefixes from neighbors permanently will lead to traffic loss.¶

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

4.2.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 however not have a "purging mechanism" in the traditional sense based on sending specialized "purge" packets. In other routing protocols such 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 `purge_lifetime` constant and relies on each node to age out and delete such 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 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 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 e.g. choose to compute 64-bit checksum over the TIE content and use that as part of the first sequence number after reboot.¶

4.2.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 4.3.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 and the nodes in e.g. 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.¶

4.2.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 choose to 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;¶
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 be often 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 another expectation 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 seems to be 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 kept relatively simple and completely distributed without any need for synchronization amongst nodes. In a "PoD" structure, where the Level L+2 is partitioned in silos of equivalent grandparents that are only reachable from respective parents, this means treating each silo as a fully connected Clos Network and solve 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, i.e. 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 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 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 hit 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 4.2.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 should guarantee that two copies are sent by different nodes to ensure against any losses.¶

4.2.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 bi