Order of FIB Updates Seldom Matters: Fast Reroute and Fast Convergence with Interface-Specific Forwarding

Abstract 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.

@article{PenPec+22,
  author = {Phani Krishna Penumarthi and Aaron Pecora and Sanjib Sur and
            Jason M. O'Kane and Srihari Nelakuditi},
  doi = {https://doi.org/10.1016/j.hcc.2022.100072},
  journal = {High-Confidence Computing},
  number = {3},
  pages = {100072},
  title = {Order of FIB Updates Seldom Matters: Fast Reroute and Fast
           Convergence with Interface-Specific Forwarding},
  volume = {2},
  year = {2022}
}