【作者】 李清；

【导师】 徐明伟；

【作者基本信息】 清华大学 ， 计算机科学与技术， 2013， 博士

【摘要】 随着规模的膨胀，互联网面临越来越多的问题，其中来自路由扩展性和可用性的挑战尤为艰巨和迫切。由于多宿主、流量工程、不合理的地址分配等原因，越来越多不可聚合的提供商独立地址从边缘网络传播到核心网络。这直接导致核心网路由表急剧增加，使互联网路由面临严重的扩展性问题。此外，网络故障不可避免，一方面，故障导致的路由更新会直接影响核心网路由表，加剧路由扩展性问题；另一方面，故障发生时，路由协议需要一定的时间来完成路由收敛，在此期间，路由信息不一致将导致网络传输服务中断，影响路由可用性。本文提出NSFIB（Nexthop-Selectable Forwarding Information Base）路由模型与框架来解决互联网路由可用性及扩展性问题。该框架及相关算法有以下五个设计目标：1）支持路由器级别的增量部署；2）缓解网络服务提供商面临的路由扩展性压力；3）提高网络故障期间的路由可用性；4）具有较低的算法复杂度；5）不影响域间路由行为。本文研究内容和贡献主要包括：1.提出基于弱转发的互联网路由模型。基于严格偏序转发条件及泛化下一跳的概念，本文提出弱转发路由模型，并设计了NSFIB路由框架，从而为路由可用性及扩展性的解决提供统一的平台。2.提出基于隧道的IP快速重路由方案MPCT（Minimum Protection Cost Tree）。首先，MPCT证明任意目的节点可以通过其保护入节点实现保护，并提出计算保护入节点的有效算法；其次，MPCT将直接转发、二次保护和保护路径长度量化为保护代价，从而优化了保护路径。3.提出NSFIB聚合方案及相关聚合算法。NSFIB聚合采用了自底向上的动态规划算法，该算法以多项式时间复杂度计算得到最优聚合FIB。实验表明，NSFIB聚合算法能够将FIB压缩到原来的5%-20%，而传统单下一跳FIB聚合算法仅能将FIB压缩到40%-70%。4.提出严格偏序NSFIB构造方案及构造算法。网络拓扑动态变化，因此路由器需要高效的NSFIB构造算法。本文提出严格偏序NSFIB构造算法，该算法能够以一次最短路径优先算法的复杂度完成NSFIB的构造。同时，本文证明严格偏序NSFIB的聚合性能和拓扑密度正相关。大规模高密度的ISP网络更加需要压缩FIB，故该构造算法拓展了NSFIB聚合的应用空间。更多还原

【Abstract】 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.更多还原