DDC
DDC
Ensuring basic connectivity in the network is generally handled by the control plane. However control plane convergence times are several orders of magnitude larger than the rate at which switches forward packets, which means that after a failure the network might be disrupted for a while, even though the network is not partitioned. Traditionally, networks have handled this problem by precomputing a set of backup paths, over which traffic can be redirected in the case of link failures. The most widely deployed example of such a mechanism is MPLS FRR, however MPLS fast-reroute can only handle a limited number of link failures. A natural question that arises is whether one could design a static mechanism, capable of dealing with any arbitrary set of link failures? We have shown that a static mechanism cannot handle an arbitrary set of failures. Given this result, one must rely on a dynamic mechanism to guarantee ideal connectivity (i.e. packets are delivered as long as a network is connected, and barring congestion related drops). Previous work in this area, has resulted in algorithms that both require unbounded space in packet headers, and NP-complete computations to provide this guarantee. We propose a new algorithm, Data Driven Connectivity, which guarantees ideal connectivity, uses a single bit in the packet header, and can be carried out at line rate.