Journal
2022 IFIP NETWORKING CONFERENCE (IFIP NETWORKING)
Volume -, Issue -, Pages -Publisher
IEEE
Keywords
multi-path routing; Suurballe-Tarjan algorithm; data-plane scalability; incremental deployment
Categories
Funding
- National Research, Development and Innovation Fund of Hungary [134604, 128062]
- NKFIH/OTKA Project [135606]
- MTA-BME Information Systems Research Group
- MTA-BME Network Softwarization Research Group
- Hungarian Ministry of Innovation and Technology NRDI Office
Ask authors/readers for more resources
This paper focuses on the problem of routing along the shortest pairs of disjoint paths over the currently deployed link-state routing architecture. By proposing an efficient tag encoding scheme, it enables multi-path routing in the network without the need for extensive network overhaul.
Recent trends point towards communication networks will be multi-path in nature to increase failure resilience, support load-balancing and provide alternate paths for congestion avoidance. We argue that the transition from single-path to multi-path routing should be as seamless as possible in order to lower the deployability barrier for network operators. Therefore, in this paper we are focusing on the problem of routing along the shortest pairs of disjoint paths between each source-destination pair over the currently deployed link-state routing architecture. We show that the union of disjoint pathpairs towards a given destination has a special structure, and we propose an efficient tag encoding scheme which requires only one extra forwarding table entry per router per destination. Our numerical evaluations demonstrate that in real-world topologies usually only 4 bit tags are sufficient in the packet headers to route on the disjoint path-pairs. Finally, we show that our tags automatically encode additional paths beyond the shortest pair of disjoint paths, including the shortest paths themselves, which enables incremental deployment of the proposed method.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available