Ensuring Connectivity via Data Plane Mechanisms

by Dejan Kostic

Network connectivity is often taken for granted, but ensuring it in the face of failures is a difficult task. Typically, the network control plane is charged with computing the routes the packets are supposed to take through the network, and ultimately installing theforwarding rules into the data plane. The data plane then uses these rules to forward packets at line rates. While it is possible to plan for some failures by pre-computing and installing failover paths, it is very challenging to do so for all possible link failures, for example. This means that there could be cases when there exists physical network connectivity but the data (forwarding) plane does not exploit it under failures, e.g., while the control plane is recomputing the routes.

This paper contains an important result. Namely, it shows that it is possible to achieve the so-called ideal forwarding connectivity strictly in the data plane. Doing so is important because it is substantially quicker than waiting for the control plane to finish its recomputation. The authors' earlier work proves that it is impossible to do so without changing the packet headers. However, the approach described here, data-driven connectivity (DDC), ensures forwarding connectivity by requiring just a few extra bits in the header. The main idea is to emulate the Gafni-Bertsekas link reversal techniquefrom the literature, but strictly in the data plane. Specifically, the nodes execute the algorithm only on a data packet arrival, and it results only in forwarding of that single packet. If needed, a node can modify the forwarding rule (FIB) and flip a bit in the packet header. It is impressive that the authors have formally proven the connectivity guarantees provided by DDC. A feature that the reviewers also found to be very useful is the ability to allow the control plane to influence the paths chosen by DDC.

The authors evaluate DDC using mostly ns3 simulations across a variety of topologies, and include fairly realistic data center scenarios. Concerns with a scheme such as this include excess congestion, extra stretch (longer path) taken by the packets, as wellas potential impact of FIB updates that might not occur at line rates. The experimental results address these issues and demonstrate that DDC performs very well. The authors have an early prototype of DDC implemented in the OpenVSwitch. Additional work on the implementation and further experiments with it could help the algorithm's chances of adoption.