Availability And Scalability Issues In Internet Routing: A Weak Forwarding Correctness Approach

With the ever-increasing users, the current Internet is facing a lot of issues, amongwhich the challenges of routing scalability and routing availability are especially urgent.Due to multi-homing, traffic engineering, unreasonable address allocation, etc., massiveinaggregatable provider-independent address fragments are continuously pouring into thecore Internet. The consequent explosion of the core-net routing tables causes the prob-lem of routing scalability. Besides, network failures are inevitable in the Internet. On onehand, allthe routing protocols requirea long timetoconvergeafternetworkfailures. Dur-ingroutingconvergence,theinconsistencyofroutinginformationmaycausetransmissionservice disruption, which affects the Internet routing availability. On another hand, routeupdates caused by failures would exacerbate the problem of routing scalability.To solve the above problems, we propose the routing model of Nexthop-SelectableFIB (NSFIB) based on weak forwarding correctness. NSFIB routing model and the cor-responding algorithms have the five primary goals of1) the support of router-level in-cremental deployability,2) the high performance of FIB shrinking,3) a decrease in thetime of transmission service disruption during network failures,4) the lower computationcomplexity and5) no impact on the inter-domain routing. The main contributions of thispaper are summarized as follows:1. Designing the NSFIB routing model. Based on weak forwarding correctness andgeneralized next hops, NSFIB routing model establishes a platform to solve theproblems of routing availability and routing scalability.2. Proposing the routing protection scheme of Minimum Protection Cost Tree(MPCT). Based on the algorithm of incremental shortest path first, MPCT algo-rithm finds the available tunnel end points for all intra-domain destinations. Be-sides, by transforming direct forwarding, re-protection and protection path lengthinto the unified protection cost according to their different priorities, MPCT avoidsthe use of unnecessary direct forwarding and re-protection.3. Proposing the scheme of Nexthop-Selectable FIB (NSFIB) aggregation. Althoughthetraditionalsingle-nexthopFIBaggregationiseasytodeploy,itcannotsatisfytherequirements of ISPs in FIB shrinking. By allocating multiple selectable next hopsfor each IP prefix, a bottom-up dynamic algorithm of NSFIB-Aggr computes a min- imized aggregated FIB with no new prefix inserted. The experiment results showthat NSFIB aggregation algorithms shrink the FIB to5%-20%of its original size,which is a great improvement over the traditional single-nexthop FIB aggregation.4. DesigningNSFIBconstructionalgorithmbasedonthenexthopofstrictpartialorder(SPO). The SPO NSFIB construction algorithm computes all the SPO next hops foreach intra-domain destinations with the complexity less than the shortest path firstalgorithm. Both of the theoretical analysis and the experiment results show thatthe performance of SPO NSFIB aggregation algorithms improves as the topologydensity increases.