Order of FIB updates seldom matters:Fast reroute and fast convergence with interface‐specific forwarding  

作　　者：Phani Krishna Penumarthi Aaron Pecora Sanjib Sur Jason M.O’Kane Srihari Nelakuditi 

机构地区：[1]Gigamon,Santa Clara,CA,USA [2]US Army,Tampa,FL,USA [3]Department of Computer Science and Engineering,University of South Carolina,Columbia,SC,USA

出　　处：《High-Confidence Computing》2022年第3期40-49,共10页高置信计算（英文）

摘　　要：During convergence,after a link state change in traditional networks with a distributed control plane,packets may get caught in transient forwarding loops.Such loops can be avoided by imposing a certain order among the routers in updating their forwarding information bases(FIBs),but it requires some form of coordination among routers.As an alternative,a progressive link metric increment method has been proposed for loop-free forwarding without ordered FIB updates,but it takes longer to converge to the target state.In this paper,we show that the order of updates rarely matters for loop-free convergence when the failure inference-based fast reroute(FIFR)scheme with interface-specific forwarding is employed for dealing with link failures.The key insight is to have each router install the traditional interface-independent forwarding entries as soon as they are recomputed during convergence and install the recomputed interface-specific backwarding entries post-convergence.Our evaluation of 280 real and random topologies confirms that the order of updates does not matter with the proposed approach for 17336 out of 17339 links in those topologies.To handle such rare cases where the order matters,it can be coupled with progressive link metric increments to ensure loop-freedom with unordered FIB updates.Thus,the proposed approach,referred to as FIFR++,makes it possible to achieve disruption-free fast convergence and fast reroute without requiring any modification to the IP datagram and without needing any coordination between routers.

关 键 词：Packet loss Failure resilience Fast reroute Transient forwarding loops Convergence delay IP networks 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]