disaggregated_prefixes = {empty }
  nodes_same_layer = { empty }
  for each S-TIE
     if S-TIE.layer == X.layer
       add S-TIE.originator to nodes_same_layer
       end if
     end for

  for each next-hop-set NHS
      isolated_nodes = nodes_same_layer
      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 S-TIE
  if X's S-TIE is different
    schedule S-TIE for flooding
    end if
 
     

Figure 3: Computation to Disaggregate Prefixes

Each disaggregated prefix is sent with the accurate path_distance. This allows a node to send the same S-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:

1. all the lower level nodes are flooded the disaggregated prefixes since we don't want to build an S-TIE per node to not complicate things unnecessarily. The PoD containing the prefix will prefer southbound anyway.
2. 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 only.
3. disaggregated S-TIEs are not "reflected" by the lower layer, i.e. nodes within same level do NOT need to be aware which node computed the need for disaggregation.
4. The fabric is still supporting maximum load balancing properties while not trying to send traffic northbound unless necessary.

4.2.5. Policy-Guided Prefixes

In a fat tree, it can be sometimes desirable to guide traffic to particular destinations or keep specific flows to certain paths. In RIFT, this is done by using policy-guided prefixes with their associated communities. Each community is an abstract value whose meaning is determined by configuration. It is assumed that the fabric is under a single administrative control so that the meaning and intent of the communities is understood by all the nodes in the fabric. Any node can originate a policy-guided prefix.

Since RIFT uses distance vector concepts in a southbound direction, it is straightforward to add a policy-guided prefix to an S-TIE. For easier troubleshooting, the approach taken in RIFT is that a node's southbound policy-guided prefixes are sent in its S-TIE and the receiver does inbound filtering based on the associated communities (an egress policy is imaginable but would lead to different S-TIEs per neighbor possibly which is not considered in RIFT protocol procedures). A southbound policy-guided prefix can only use links in the south direction. If an PGP S-TIE is received on an east-west or northbound link, it must be discarded by ingress filtering.

Conceptually, a southbound policy-guided prefix guides traffic from the leaves up to at most the northmost layer. It is also necessary to to have northbound policy-guided prefixes to guide traffic from the northmost layer down to the appropriate leaves. Therefore, RIFT includes northbound policy-guided prefixes in its N PGP-TIE and the receiver does inbound filtering based on the associated communities. A northbound policy-guided prefix can only use links in the northern direction. If an N PGP TIE is received on an east-west or southbound link, it must be discarded by ingress filtering.

By separating southbound and northbound policy-guided prefixes and requiring that the cost associated with a PGP is strictly monotonically increasing at each hop, the path cannot loop. Because the costs are strictly increasing, it is not possible to have a loop between a northbound PGP and a southbound PGP. If east-west links were to be allowed, then looping could occur and issues such as counting to infinity would become an issue to be solved. If complete generality of path - such as including east-west links and using both north and south links in arbitrary sequence - then a Path Vector protocol or a similar solution must be considered.

If a node has received the same prefix, after ingress filtering, as a PGP in an S-TIE and in an N-TIE, then the node determines which policy-guided prefix to use based upon the advertised cost.

A policy-guided prefix is always preferred to a regular prefix, even if the policy-guided prefix has a larger cost.

The set of policy-guided prefixes received in a TIE is subject to ingress filtering and then regenerated to be sent out in the receiver's appropriate TIE. Both the ingress filtering and the regeneration use the communities associated with the policy-guided prefixes to determine the correct behavior. The cost on re-advertisement MUST increase in a strictly monotonic fashion.

4.2.5.1. Ingress Filtering

When a node X receives a PGP S-TIE or N-TIE that is originated from a node Y which does not have an adjacency with X, such a TIE MUST be discarded. Similarly, if node Y is at the same layer as node X, then X MUST discard PGP S- and N-TIEs.

Next, policy can be applied to determine which policy-guided prefixes to accept. Since ingress filtering is chosen rather than egress filtering and per-neighbor PGPs, policy that applies to links is done at the receiver. Because the RIFT adjacency is between nodes and there may be parallel links between the two nodes, the policy-guided prefix is considered to start with the next-hop set that has all links to the originating node Y.

A policy-guided prefix has or is assigned the following attributes:

cost:

This is initialized to the cost received

community_list:

This is initialized to the list of the communities received.

next_hop_set:

This is initialized to the set of links to the originating node Y.

4.2.5.2. Applying Policy

The specific action to apply based upon a community is deployment specific. Here are some examples of things that can be done with communities. The length of a community is a 64 bits number and it can be written as a single field M or as a multi-field (S = M[0-31], T = M[32-63]) in these examples. For simplicity, the policy-guided prefix is referred to as P, the processing node as X and the originator as Y.

Prune Next-Hops: Community Required:

For each next-hop in P.next_hop_set, if the next-hop does not have the community, prune that next-hop from P.next_hop_set.

Prune Next-Hops: Avoid Community:

For each next-hop in P.next_hop_set, if the next-hop has the community, prune that next-hop from P.next_hop_set.

Drop if Community:

If node X has community M, discard P.

Drop if not Community:

If node X does not have the community M, discard P.

Prune to ifIndex T:

For each next-hop in P.next_hop_set, if the next-hop's ifIndex is not the value T specified in the community (S,T), then prune that next-hop from P.next_hop_set.

Add Cost T:

For each appearance of community S in P.community_list, if the node X has community S, then add T to P.cost.

Accumulate Min-BW T:

Let bw be the sum of the bandwidth for P.next_hop_set. If that sum is less than T, then replace (S,T) with (S, bw).

Add Community T if Node matches S:

If the node X has community S, then add community T to P.community_list.

4.2.5.3. Store Policy-Guided Prefix for Route Computation and Regeneration

Once a policy-guided prefix has completed ingress filtering and policy, it is almost ready to store and use. It is still necessary to adjust the cost of the prefix to account for the link from the computing node X to the originating neighbor node Y.

There are three different policies that can be used:

Minimum Equal-Cost:

Find the lowest cost C next-hops in P.next_hop_set and prune to those. Add C to P.cost.

Minimum Unequal-Cost:

Find the lowest cost C next-hop in P.next_hop_set. Add C to P.cost.

Maximum Unequal-Cost:

Find the highest cost C next-hop in P.next_hop_set. Add C to P.cost.

The default policy is Minimum Unequal-Cost but well-known communities can be defined to get the other behaviors.

Regardless of the policy used, a node MUST store a PGP cost that is at least 1 greater than the PGP cost received. This enforces the strictly monotonically increasing condition that avoids loops.

Two databases of PGPs - from N-TIEs and from S-TIEs are stored. When a PGP is inserted into the appropriate database, the usual tiebreaking on cost is performed. Observe that the node retains all PGP TIEs due to normal flooding behavior and hence loss of the best prefix will lead to re-evaluation of TIEs present and readvertisement of a new best PGP.

4.2.5.4. Regeneration

A node must regenerate policy-guided prefixes and retransmit them. The node has its database of southbound policy-guided prefixes to send in its S-TIE and its database of northbound policy-guided prefixes to send in its N-TIE.

Of course, a leaf does not need to regenerate southbound policy-guided prefixes.

4.2.5.5. Overlap with Disaggregated Prefixes

PGPs may overlap with prefixes introduced by automatic de-aggregation. The topic is under further discussion. The break in connectivity that leads to infeasiblity of a PGP is mirrored in adjacency tear-down and according removal of such PGPs. Nevertheless, the underlying link-state flooding will be likely reacting significantly faster than a hop-by-hop redistribution and with that the preference for PGPs may cause intermittant blackholes.

4.2.6. Reachability Computation

A node has three sources of relevant information. A node knows the full topology south from the received N-TIEs. A node has the set of prefixes with associated distances and bandwidths from received S-TIEs. A node can also have a set of PGPs.

4.2.6.1. Specification

To compute reachability, a node runs conceptually a northbound and a southbound SPF. We call that N-SPF and S-SPF and when progressing Dijkstra we use only the according direction of adjacencies. In both cases we are using the N-TIEs to find according adjacencies but in case of N-SPF we use the adjacent node's S-TIE to validate backlinks since as in IS-IS or OSPF, unidirectional links are associated together to confirm bidirectional connectivity. This enforces the requirement that a packet traversing in a southbound direction must not go take any northbound links since a node has topological visibility only south of itself and vice versa. As well, there are no links at the computing node's level that go to a northbound level and will find a backlink (except the next higher level providing node S-TIE). All paths computed in an southbound SPF will contain only east-west and southbound links.

A node runs such standard shortest path first (SPF) algorithms on the network graph. If a node is minimized to have a cost of COST_INFINITY, then it is not reachable.

Since neither computation cannot "loop" (with exception of E-W links), it is relatively simple to compute non-equal-cost paths and "saturate" the fabric to the extent desired.

4.2.6.1.1. Attaching Prefixes

After the SPF is run, it is necessary to attach according prefixes. For S-SPF, prefixes from an N-TIE are attached to the originating node with that node's next-hop set and a distance equal to the prefix's cost plus the node's minimized path distance. The RIFT route database, a set of (prefix, type=spf, path_distance, next-hop set), accumulates these results.

In case of N-SPF prefixes from each S-TIE need to also be added to the RIFT route database. The N-SPF is really just a stub so the computing node needs simply to determine, for each prefix in an S-TIE that originated from adjacent node, what next-hops to use to reach that node. Since there may be parallel links, the next-hops to use can be a set; presence of the computing node in the associated Node S-TIE is sufficient to verify that at least one link has bidirectional connectivity. The set of minimum cost next-hops from the computing node X to the originating adjacent node is determined.

Each prefix has its cost adjusted before being added into the RIFT route database. The cost of the prefix is set to the cost received plus the cost of the minimum cost next-hop to that neighbor. Then each prefix can be added into the RIFT route database with the next_hop_set; ties are broken based upon distance and type. Prefixes obtained from prefix N-TIEs (southbound routes) are prefered over prefixes from S-TIEs (northbound routes).

  for each S-TIE
     if S-TIE.layer > X.layer
        next_hop_set = set of minimum cost links to the S-TIE.originator
        next_hop_cost = minimum cost link to S-TIE.originator
        end if
     for each prefix P in the S-TIE
        P.cost = P.cost + next_hop_cost
        if P not in route_database:
          add (P, type=DistVector, P.cost, next_hop_set) to route_database
          end if
        if (P in route_database) and 
             (route_database[P].type is not PolicyGuided):
          if route_database[P].cost > P.cost):
            update route_database[P] with (P, DistVector, P.cost, next_hop_set)
          else if route_database[P].cost == P.cost
            update route_database[P] with (P, DistVector, P.cost, 
               merge(next_hop_set, route_database[P].next_hop_set))
          else
            // Not prefered route so ignore
            end if
          end if
        end for
     end for
 
     

    for each policy-guided prefix P:
      if P not in route_database:
         add (P, type=PolicyGuided, P.cost, next_hop_set)
         end if
      if P in route_database :
          if (route_database[P].type is not PolicyGuided) or
             (route_database[P].cost > P.cost):
            update route_database[P] with (P, PolicyGuided, P.cost, next_hop_set)
          else if route_database[P].cost == P.cost
            update route_database[P] with (P, PolicyGuided, P.cost, 
               merge(next_hop_set, route_database[P].next_hop_set))
          else
            // Not prefered route so ignore
            end if
          end if
      end for
 
     

.  |   |              |   |
.+-+---+-+          +-+---+-+
.|       |          |       |
.|Node111|          |Node112|
.+-+---+-+          ++----+-+
.  |   |             |    |
.  |   +---------------+  X
.  |                 | |  X Failure
.  |   +-------------+ |  X
.  |   |               |  |
.+-+---+-+          +--+--+-+
.|       |          |       |
.|Leaf111|          |Leaf112|
.+-------+          +-------+
.      +                  +
.     Prefix111     Prefix112
                    
                    

.                +--------+          +--------+   S-TIE of Spine21
.                |        |          |        |   received by
.                |Spine 21|          |Spine 22|   reflection of
.                ++-+--+-++          ++-+--+-++   Nodes 112 and 111
.                 | |  | |            | |  | |
.                 | |  | |            | |  | 0/0
.                 | |  | |            | |  | |
.                 | |  | |            | |  | |
.  +--------------+ |  +--- XXXXXX +  | |  | +---------------+
.  |                |    |         |  | |  |                 |
.  |    +-----------------------------+ |  |                 |
.  0/0  |           |    |         |    |  |                 |
.  |    0/0       0/0    +- XXXXXXXXXXXXXXXXXXXXXXXXX -+     |
.  |  1.1/16        |              |    |  |           |     |
.  |    |           +-+    +-0/0-----------+           |     |
.  |    |             |   1.1./16  |    |              |     |
.+-+----++          +-+-----+     ++-----0/0          ++----0/0
.|       |          |       |     |    1.1/16         |   1.1/16
.|Node111|          |Node112|     |Node121|           |Node122|
.+-+---+-+          ++----+-+     +-+---+-+           ++---+--+
.  |   |             |    |         |   |              |   |
.  |   +---------------+  |         |   +----------------+ |
.  |                 | |  |         |                  | | |
.  |   +-------------+ |  |         |   +--------------+ | |
.  |   |               |  |         |   |                | |
.+-+---+-+          +--+--+-+     +-+---+-+          +---+-+-+
.|       |          |       |     |       |          |       |
.|Leaf111|          |Leaf112|     |Leaf121|          |Leaf122|
.+-+-----+          ++------+     +-----+-+          +-+-----+
.  +                 +                  +              +
.  Prefix111    Prefix112             Prefix121     Prefix122
.                                       1.1/16
                    
                    

//! Thrift file for RIFT, routing for fat trees
//! @note: all numbers are implementation co'erced to unsigned versions using the highest bit

/// represents protocol major version
const i32 CURRENT_MAJOR_VERSION = 1
const i32 CURRENT_MINOR_VERSION = 0

typedef i64    SystemID
typedef i32    IPv4Address
/// this has to be of length long enough to accomodate prefix
typedef binary IPv6Address
typedef i16    UDPPortType
typedef i16    TIENrType
typedef i16    MTUSizeType
typedef i32    SeqNrType
typedef i32    LifeTimeType
typedef i16    LevelType
typedef i16    PodType
typedef i16    VersionType
typedef i32    MetricType
typedef i64    KeyIDType
typedef i32    LinkIDType
typedef string KeyNameType
typedef bool   TieDirectionType
typedef byte   PrefixLenType

const LevelType   DEFAULT_LEVEL    = 0
const PodType     DEFAULT_POD      = 0
const LinkIDType  UNDEFINED_LINKID = 0
const MetricType  DEFAULT_DISTANCE = 1
/// any distance larger than this will be considered infinity
const MetricType  INFINITE_DISTANCE= 0x70000000
/// any element with 0 distance will be ignored
const MetricType  INVALID_DISTANCE = 0

/// RIFT packet header
struct PacketHeader {
    1: required VersionType major_version = CURRENT_MAJOR_VERSION;
    2: required VersionType minor_version = CURRENT_MINOR_VERSION;
    // this is the node sending the packet, in case of TIE/TIRE/TIDE also the originator
    3: required SystemID  sender;
    4: optional LevelType level = DEFAULT_LEVEL;
}

struct ProtocolPacket {
    1: required PacketHeader header;
    2: required Content content;
    }

union Content {
    1: optional LIE          hello;
    2: optional TIDEPacket   tide;
    3: optional TIREPacket   tire;
    4: optional TIEPacket    tie;
}

// serves as community for PGP
struct Community {
    1: required i32          top;
    2: required i32          bottom;
}

// @todo: flood header separately in UDP ?
// to allow caching to TIEs while changing lifetime?
struct TIEPacket {
    1: required TIEHeader  header;
    2: required TIEElement element;
}

enum TIETypeType {
    Illegal              =   0,
    TIETypeMinValue      =   1,
    NodeTIEType          =   2,
    PrefixTIEType        =   3,
    PGPrefixTIEType      =   4,
    KeyValueTIEType      =   5,
    TIETypeMaxValue      =   6,
}

/// RIFT LIE packet
struct LIE {
    1: optional string          name;
    // UDP port to which we can flood TIEs, same address
    // as the hello TX this hello has been received on
    2: required UDPPortType     flood_port;
    3: optional Neighbor        neighbor;
    4: optional PodType         pod = DEFAULT_POD;
    // this node's level is already included on the packet header
}

struct LinkID {
    1: required LinkIDType      local_id;
    2: required LinkIDType      remote_id;
    // more properties of the link can go in here
}

struct Neighbor {
    1: required SystemID        originator;
    2: required UDPPortType     flood_port;
}

/// ID of a TIE
/// @note: TIEID space is a total order achieved by comparing the elements in sequence defined
struct TIEID {
    /// indicates whether N or S-TIE, True > False
    1: required TieDirectionType    northbound;
    2: required SystemID            originator;
    3: required TIETypeType         tietype;
    4: required TIENrType           tie_nr;
}

struct TIEHeader {
    2: required TIEID        tieid;
    3: required SeqNrType    seq_nr;
    // in seconds
    4: required LifeTimeType lifetime;
}

// sorted, otherwise protocol doesn't work properly
struct TIDEPacket {
    /// all 00s marks starts
    1: required TIEID           start_range;
    /// all FFs mark end
    2: required TIEID           end_range;
    /// sorted list of headers
    3: required list<TIEHeader> headers;
}

struct TIREPacket {
    1: required set<TIEHeader> headers;
}

struct NodeNeighborsTIEElement {
    /// if neighbor systemID repeats in set or TIEs of same node
    /// the behavior is undefined
    1: required SystemID        neighbor;
    2: required LevelType       level;
    3: optional MetricType      cost = DEFAULT_DISTANCE;
    // can carry description of multiple
    // parallel links in a TIE
    4: optional set<LinkID>     link_ids;
}

/// capabilities the node supports
struct NodeCapabilities {
    1: required bool         flood_reduction = true;
}

/// flags the node sets
struct NodeFlags {
    1: required bool         overflow = false;
}

struct NodeTIEElement {
    1: required LevelType                    level;
    2: optional NodeCapabilities             capabilities;
    3: optional NodeFlags                    flags;
    4: required set<NodeNeighborsTIEElement> neighbors;
}

struct IPv4PrefixType {
    1: required IPv4Address    address;
    2: required PrefixLenType  prefixlen;
}

struct IPv6PrefixType {
    1: required IPv6Address    address;
    2: required PrefixLenType  prefixlen;
}

union IPPrefixType {
    1: optional IPv4PrefixType   ipv4prefix;
    2: optional IPv6PrefixType   ipv6prefix;
}

struct PrefixWithMetric {
    1: required IPPrefixType   prefix;
    2: optional MetricType     cost = 1;
}

struct PrefixTIEElement {
    /// if the same prefix repeats in multiple TIEs of same node
    /// or with different metrics, behavior is unspecified
    1: required set<PrefixWithMetric> prefixes;
}

struct KeyValue {
    1: required KeyIDType keyid;
    2: optional KeyNameType key;
    3: optional string value = "";
}

struct KeyValueTIEElement {
    /// if the same key repeats in multiple TIEs of same node
    /// or with different values, behavior is unspecified
    1: required set<KeyValue>    keyvalues;
}

/// single element in a TIE
union TIEElement {
    /// hinges of enum TIETypeType::NodeTIEType
    1: optional NodeTIEElement            node;
    /// hinges of enum TIETypeType::PrefixTIEType
    2: optional PrefixTIEElement          prefixes;
    /// ignored in S-TIEs
    3: optional KeyValueTIEElement        keyvalues;
    /// @todo: policy guided prefixes
}