论文部分内容阅读
随着规模的膨胀，互联网面临越来越多的问题，其中来自路由扩展性和可用性的挑战尤为艰巨和迫切。由于多宿主、流量工程、不合理的地址分配等原因，越来越多不可聚合的提供商独立地址从边缘网络传播到核心网络。这直接导致核心网路由表急剧增加，使互联网路由面临严重的扩展性问题。此外，网络故障不可避免，一方面，故障导致的路由更新会直接影响核心网路由表，加剧路由扩展性问题；另一方面，故障发生时，路由协议需要一定的时间来完成路由收敛，在此期间，路由信息不一致将导致网络传输服务中断，影响路由可用性。本文提出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聚合的应用空间。