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

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.

Segment routing for traffic engineering and effective recovery in low-earth orbit satellite constellations

Low-Earth Orbit Satellite Constellations(LEO-SCs)provide global,high-speed,and low latency Internet access services,which bridges the digital divide in the remote areas.As inter-satellite links are not supported in initial deployment(i.e.the Starlink),the communication between satellites is based on ground stations with radio frequency signals.Due to the rapid movement of satellites,this hybrid topology of LEO-SCs and ground stations is time-varying,which imposes a major challenge to uninterrupted service provisioning and network management.In this paper,we focus on solving two notable problems in such a ground station-assisted LEO-SC topology,i.e.,traffic engineering and fast reroute,to guarantee that the packets are forwarded in a balanced and uninterrupted manner.Specifically,we employ segment routing to support the arbitrary path routing in LEO-SCs.To solve the traffic engineering problem,we proposed two source routings with traffic splitting algorithms,Delay-Bounded Traffic Splitting(DBTS)and DBTS+,where DBTS equally splits a flow and DBTS+favors shorter paths.Simu-lation results show that DBTS+can achieve about 30%lower maximum satellite load at the cost of about 10%more delay.To guarantee the fast recovery of failures,two fast reroute mechanisms,Loop-Free Alternate(LFA)and LFA+,are studied,where LFA pre-computes an alternate next-hop as a backup while LFA+finds a 2-segment backup path.We show that LFA+can increase the percentage of protection coverage by about 15%.

A New Selection Criterion of Loop-free Alternate Interface for IP Fast Rerouting

As the technology of IP Fast Rerouting (FRR) become mature and the related methods and specifi cation such as RFC5286 accepted as standard, it is expected that IP FRR will be deployed gradually and will enhance the survivability of IP network. This paper presents a different method for computing the Loop-free Alternate Interfaces. The new algorithm can be referred as "Next-Hop Cost Decrease (NHCD)" criterion. Compared with the RFC5286 LFA method, NHCD can handle both the simultaneous link failure and node failure, including multi-link failures. It has less computational complexity and can be used uniformly in the Traffi c Engineering and Network Recovery. However, NHCD is somewhat lower than the LFA method on recovery ratio of single link failure. After a formal description of NHCD criterion and a proof of loopfree alternates, the paper presents the simulation results of NHCD.

Toward software defined AS-level fast rerouting

Network failures are common on the Internet, and with mission-critical services widely applied, there grows demand for the Internet to maintain the performance in possibilities of failures. However, the border gateway protocol（BGP） can not react quickly to be recovered from them, which leads to unreliable packet delivery degrading the end-to-end performance. Although much solutions were proposed to address the problem, there exist limitations. The authors designed a software defined autonomous system（AS）-level fast rerouting（SD-FRR） to efficiently recover from interdomain link failures in the administrative domain. The approach leverages the principle of software defined networking（SDN） to achieve the centralized control of the entire network. By considering routing policies and BGP decision rules, an algorithm that can automatically find a policy-compliant protection path in case of link failure was proposed. The OpenF low forwarding rules are installed on routers to ensure data forwarding. Furthermore, to deactivate the protection path, how to remove flow entries based on prefixes was proposed. Experiments show that the proposal provides effective failure recovery and does not introduce significant control overhead to the network.