How to Establish Loop-Free Multipath Routes in Named Data Networking

download Download PDF

Klaus Schneider, Beichuan Zhang
NDN Technical Report NDN-0044, Revision 1

Both IP networks and Named Data Networking (NDN) can be extended to support multipath forwarding. How- ever, since the IP forwarding plane cannot detect loops, IP routing protocols are strictly required to produce loop-free paths. In contrast, NDN can choose between using a loop-free routing protocol and handling loops at the forwarding layer. In this paper, we explore the trade-offs that come with this choice.

It is often useful to split traffic for one destination among multiple paths, for example, to balance the traffic load or to reduce network congestion. This traffic splitting requires the employed paths to be loop-free, lest they waste network resources, and the involved routers to have a high path choice, that is, a high number of potential nexthops to forward traffic to.

We show that we can achieve a higher loop-free path choice than state-of-the-art loop-free routing protocols by combining an almost loop-free routing protocol (ALR) with loop-removal at the forwarding layer. ALR’s advantage comes from exploiting the ability of NDN’s data plane to always exclude the incoming interface from forwarding, which broadens the routing task beyond the traditional goal of creating a Directed Acyclic Graph (DAG). Assuming this incoming interface-exclusion, ALR employs certain heuristics to minimize routing loops while, when possible, giving each router along a path at least two potential nexthops towards the destination. The quality of these nexthops is signaled to the forwarding layer, which then detects and permanently removes all remaining loops. Combined, these two mechanisms result in higher path choice and path quality than current alternatives, while being computationally efficient enough for practical implementation.