RFD 347 Delay Driven Multipath

The Oxide platform is built on multipath networks at the physical layer. The Oxide rack contains a pair of switches and each compute sled is connected to both switches in the rack. This means for any packet going from one compute sled to another both switches are a viable nexthop destination and a choice must be made as to which one to use. When racks are interconnected the nexthop choice must also be made at the switch level e.g., what switch in an adjacent rack is the best nexthop for a given compute sled in that rack?

This situation is generally known as the multipath routing problem. A solution to this problem is a path from source to destination across a graph representation of a network. Routing protocols that implement solutions to this problem come in both distributed and centralized forms.

Distributed solutions such as the [BGP] protocol often take the form of what are called distance vector (DV) algorithms. Routers running a DV protocol announce destination prefixes to their peers along with a distance metric. Peers receiving DV announcements add a routing entry to their local tables for each prefix in the announcement with a nexthop set to the announcing router. If there are multiple paths the distance metric and a weight for that metric are combined to determine which path to use when making forwarding decisions. Weights are typically determined out of band by measuring networks and forming traffic matrices.

Centralized solutions such as the [OSPF] protocol often take the form of what are called link state (LS) algorithms. Routers running an LS protocol announce destination prefixes to their peers along with a graph representation of links in the network they have direct observability of or have learned from others. Peers receiving LS announcements combine link state information from peers to form a complete graph representation of the network. When making routing decisions, each router runs a local shortest path first (SPF) algorithm such as Dijkstra or Bellman Ford using a combination of link distance metrics and weights to determine the best bath. Like the DV protocols, determining a traffic matrix to form a system of weights is typically an out of band activity.

Some routing protocols combine DV and LS approaches. Early on at Oxide, we were considering implementing [RIFT] as our primary intersled routing protocol along side ECMP. RIFT stands for Routing In Fat Trees. As the name suggests, this is a routing protocol specific to so called Fat Tree or Folded [Clos] type topologies. These topologies are hierarchical and have an explicit notion of directionality. Routers higher in the hierarchy are northbound, routers lower in the hierarchy are southbound and routers in the same level of the hierarchy are east/west. RIFT combines LS and DV by having all northbound announcements be LS and all southbound announcements be DV. With this scheme every router has a complete view of the topology below it to make optimal routing decisions, while not having to worry about specific details of the broader network above.

What all of these protocols have in common is that they are dynamic routing protocols. This means that routers implementing these protocols are able to combine information from peer routers and operators as they are running to adapt to changing network conditions. Examples of adaptation include adding or removing routes in response to announcements from peers, removing routes due to a peer session failure or expiration or, updating link weights because an operator has provided a new traffic matrix.

All of the protocols described above also separate the notion of network structure determination from forwarding path decision making. Network structure as perceived by any router in a network is observed through announcements from peers describing network reachability and some notion of topological structure associated with that reachability information, whether it be a distance metric or a collection of links each with their own metrics. Forwarding path decision making is made based on distance or link weights from a traffic matrix that is supplied by an operator within the context of observed network structure. Simply put, network structure informs a router of what its options are for forwarding a packet to the next hop and link/distance weights allow the router to determine the best choice from those options.

The mechanics of how network reachability and path weight information is propagated and processed in a routing protocol are determined in part by the timescale at which the protocol must observe and adapt to changing network conditions. The BGP and OSPF protocols were designed to support routing in the Internet (capital I). The network structure of the Internet is based on peering agreements between organizations that move at the speed of legal contracts. Path selection in the Internet is mostly an economic/business decision based on contracts that assign monetary costs to forwarding decisions. Organizations operating with a large Internet footprint engage in an activity called traffic engineering which boils down to measuring and predicting traffic flows to calculate traffic matrices that minimize (maximize) operating costs (revenues).

RIFT is a protocol designed specifically to operate in the data center context. Similar to BGP and OSPF, RIFT propagates network structure through announcements. Unlike BGP and OSPF, RIFT only supports specific topological structures. RIFT leverages that specificity to define a valley free routing (VFR) model that always prefers southbound routing based on centralized SPF computations. Rift has its own built in notion of distance metric calculation that can be combined with an external weighting mechanism to determine optimal paths.

Given the background on routing protocols above, let’s describe what our goals are for an intersled routing protocol for the Oxide platform. Note that the intersled routing protocol is not the only routing protocol we must implement for the product. We must also implement protocols such as BGP, OSPF and IS-IS that allow Oxide racks to be connected to upstream networks. But those protocols are a part of Boundary Services described in [RFD63] and are not the subject of this RFD, we are specifically concerned with intersled routing here.

Our goals for intersled routing are the following.

These goals are in rough order of priority. First and foremost our networks must be reliable. Our customer’s workloads must continue without the need for manual operator mitigation in the presence of link and switch faults. Here N-1 means that for any given Oxide topology, if we look along the path between two servers and count the critical components to make that path work from phy-to-phy we denote that as N. N-1 fault tolerance means we can lose any one of those components without an outage. So we can loose any phy, any transceiver, any cable, or even any switch. However, once we are in an N-1 state, that is considered a contingency state and there is risk that another failure could lead to an outage. Another outage could happen and we could find ourselves operational in N-2, but now the risk of the next failure creating an outage is even higher. This terminology comes from power grid operations.

Putting our customers in the driver’s seat for topology construction means that we cannot assume a particular topology structure. This rules out the use of protocols like RIFT. While we cannot guarantee any topology is in play, we should strive to give our customers the maximum possible freedom in deciding how they want to interconnect their Oxide racks.

Our customers are paying for 6.4 tbps of bisection bandwidth per rack with nodes that are microseconds apart in latency. We intend to give them every last ounce of that available bandwidth at snappy round trip times, independent of the characteristics of the traffic they run through Oxide powered interconnects. That means instrumenting, observing and adapting to network dynamics well inside the timescale at which microcongestion starts to degrade effective capacity. Microcongestion is a short-lived congestion event comes and goes within sub-millisecond intervals. These events, often called microbursts have been shown to be responsible for the majority of data center packet loss and performance degradation. See the [DRILL] paper for a good survey of the research in this space. Optimizing the network at this speed means in-band instrumentation and continual distributed optimal path approximation. This also rules out RIFT-like approaches as centralized SPF computations can’t keep up.

Finally, our routing protocols should not impose scaling limits on the number of racks a customer can interconnect. As a distance-vector type protocol, ddm scales well in terms of the routing table size any particular node has to keep. The largest routing tables will be on rack switches that are connected to a large number of other rack switches. An upper bound on routing table size for rack switches is given in the P4 Considerations section. That discussion assumes racks that are directly connected sidecar-to-sidecar. As DDM evolves and Oxide starts to produce networking racks, we’ll need to consider intermediary switches which implies the need for aggregation and route summarization. This should fit in naturally with DDM being a distance vector protocol. But at the point we start stretching across true intermediary routers, we need to graduate from pure distance vector, to path vector (e.g. like BGP) to be account for asymmetric topology conditions and to not aggregate in a way that would inhibit optimal delay calculation. Lots of fun an interesting challenges there, but for now this is an open question / future work.

At face value there is also concern for blowing up packet sizes, as extension headers add 4 bytes per hop on every packet. However, modern hyperscale topologies such as Facebook’s multi-plane folded clos and topologically similar networks from other hyperscalers have shown that even for extraordinarily large networks with hundreds of thousands of servers, the number of hops involved are relatively small, and very likely to fit within the 15-hop limit (described later) of a single IPv6 extension header.

Delay driven multipath (ddm) is a routing protocol that aims to provide network-layer load balancing and fault tolerance inside flow round-trip-times on networks where multiple physical paths exist between hosts. Ddm takes inspiration from the micro load balancing ideas in [DRILL] and the notion of using delay as a leading indicator of congestion from [Swift]. We bring these ideas together in a routing protocol that has a distance-vector control plane for out-of-band route distribution, with an in-band IPv6 extension header based data plane for carrying destination-delay values between nodes in the network as they send packets. The result is a continuously evolving distributed approximation of a Dijkstra forest where link weights are destination delays, there is a root for every node in the network, and the radial fanout for each root node corresponds to the destination nodes the root is communicating with. A Dijkstra forest is an extension the shortest-path tree that results from running Dijkstra’s Algorithm over a graph. In Dijkstra’s algorithm if we select one node in the graph as the root, then the result is a tree that contains the shortest path from every other node in the graph to the root. A Dijkstra forest results from selecting each node in the graph independently as a root node, computing the shortest-path tree for that node, and calling the collection of all such trees a forest. In the case where all nodes in a network are communicating, the distributed graph formed among the nodes solves a time-varying form of the all pairs shortest path (APSP) problem continuously.

In addition to tracking delay, ddm also tracks outstanding acknowledgement time. By incorporating this information into routing decisions we can not only load balance and avoid congestion, but also react to faults within the same sub-round-trip-time (RTT) timescale.

A notable aspect about ddm is that it exists purely at the internet layer (L3). Many of the multipath mechanisms in production today include transport layer information in routing decisions to achieve path affinity for connection flows. This is an explicit non-goal of ddm as we are trying to avoid the elephant flow issues inherent to these approaches. An elephant flow is a long lived high-volume flow. Because ECMP decisions are based on address/port hashing, elephant flows are pinned to a particular path independent of congestion considerations and cause head-of-line blocking issues for short-lived mice-flows. A nice summary of these issues can be found in the Tiny Flow paper. The motivating factor for transport layer flow affinity is ensuring packet order within flows. If consecutive packets within a flow traverse different paths on the way to their destination, they may arrive out of order if the latency difference across the paths is large enough. Out-of-order delivery can have a significant detrimental impact on performance if it occurs frequently. The first order objective of ddm is to optimize for latency, but we will show that this has the side effect of implicitly optimizing for ordering as a second order objective. Pragmatically speaking this can be phrased as: optimizing per-packet delay typically maintains ordering, except when delay measurements indicate that maintaining ordering comes at the cost of increased congestion.

The ddm control plane protocol (which is an entity unto itself independent of the Oxide platform control plane) is responsible for neighboring router discovery and network reachability distribution through prefix announcements. It is only responsible for determining what routes exist, when multiple paths for a particular destination exist the control plane protocol does not participate in that decision. It only creates the choice space for such decisions to be made. Ddm peers discover each other through IPv6 link-local multicast. This means peers must be on a common layer-2 broadcast domain. Ddm is an IPv6 only protocol. When a ddm router is started, it is given a set of interfaces it should attempt to discover peers on. The router will send out send out periodic solicitations on the configured interfaces and respond to solicitations with advertisements on those interfaces.

When a ddm router receives an advertisement in response to a solicitation, it starts a prefix exchange server, listening on the link-local source address the remote peer was discovered with. Prefix exchange messages between peers take place over http(s), optionally employing TLS client authentication. While the exchange server for an interface is running, periodic solicitations continue to be sent out at a configurable rate. Ddm defines a configurable threshold for the number of solicitations that may be missed before considering a peer expired. When a peer expires the exchange server started for that peer is torn down and any routes imported from that peer are removed.

Ddm defines two kinds of routers, server routers and transit routers. In the Oxide platform, Gimlets run server routers and Scrimlets run transit routers. The difference between server and transit routers is redistribution behavior. Any time a transit router receives an announcement, it redistributes that announcement to all of the other peers it has sessions with (not including the router from which the announcement came). Similarly, transit routers also redistribute any changes in network reachability due to peer expiration. Server routers do not redistribute any reachability information. They only send announcements for prefixes that they originate.

The ddm control plane may be viewed conceptually as a state machine instance per configured interface. This state machine is depicted in the diagram below.

The state machine begins in the solicit state. In this state peer discovery is performed. When an advertisement is received, the state machine transitions to the exchange state. From exchange, if an announce or withdraw event is fired in response to prefixes being added or removed through the local administration API, the state machine transitions to the push state where the announced or withdrawn prefixes are propagated to neighbors. The push state is also transitioned to upon receiving a pull request from a peer. A pull request is a peer asking for all the prefixes the router has. From exchange if a sync event is fired in response to an admin API call for the local router to synchronize with all its peers, the pull state is entered where a pull request is send to each active peer. Finally from exchange if a push event is fired in response to a remote peer pushing an update to this router, the update state is entered where the local routing table is updated according to the announcement and withdraw prefixes in the update message. Optionally, if the router is a transit router, the update is redistributed to active peers.

Once a router has entered the exchange state and the push/pull handlers are online, an synchronization process is started called the initial pull request. For this process, ddm routers asynchronously pull prefixes from a newly established peer as a one-shot operation (operators or control plane software can always initiate ad-hoc pull requests later). This allows the peers to synchronize any prefixes that may have existed prior to their peering. It’s important that this initial pull process does not block establishment of push/pull handlers or event handlers such as expiration timers. Establishing these handlers first ensures that requests and events cannot get lost during the initial synchronization. For example, if a router is performing an initial sync with a peer, and during that time the peer also sends a new announcement or withdraw, if the exchange handlers are not running, the result of the pull will be stale and we will have lost the message required to update to the current state.

The ddm data plane implementation has four primary responsibilities.

At a high level what ddm is doing for instrumentation is building a stack of stack of timestamps as packets flow from source to destination across a network.

When server nodes emit packets, they add a timestamp to an extension header on that packet. When an acknowledgement packet comes back with that timestamp in it, the sending node updates its local delay table with the following for the source address of the acknowledgement packet.

This information is used when determining where to send subsequent packets. For each outgoing packet the delay table entry for the destination address is consulted. When there are multiple paths, there are multiple matching table entries. For each entry returned a pick function is evaluated over the delay value, its derivatives and the time since the last acknowledgement.

The pick function p(…​) is the defining logical component of ddm. It determines nexthop routing decisions based delay information. Like transport protocols such as TCP, there may be multiple variants of the pick function. The pick function may use past, present and projected delay information. There may be different pick functions running and different parts of a ddm network. The following subsections describe pick functions that are either currently implemented or are under development.

Traditional routing techniques will not allow us to realize the potential the physical networks of the Oxide platform have to offer. Out-of-band traffic engineering has no hope of keeping up with microcongestion and other fast moving traffic dynamics typical of data center network traffic flows. Centralized link state protocols also have no hope of keeping up. We are building a distance-vector control plane with in-band network instrumentation that builds a distributed delay matrix in real-time as a means to load balance and provide fault tolerance inside flow round trip times.