基于关键节点路由保护的域内路由可用性研究

Lots of related researches have shown that network failures occur inevitably and frequently on the Internet. When network failures occur, the current deployed intra-domain routing protocol need to re-convergence. During the process of re-convergence, the packets may be lost due to inconsistent routing information, greatly reducing the Internet routing availability, seriously affecting the ISP’s service quality and reputation. Therefore, improving the Internet routing availability has become an urgent problem. In order to improve the intra-domain route availability, the routing protection algorithm is usually adopted in the industry. However, the existing routing protection algorithms are confronted with two problems: (1) they do not take into account the implementation of efficiency and route availability (2) they do not deal with network congestion during failover. Therefore, the project first builds a route availability model which is based on routing protection. And then an Efficient Algorithm for Computing Critical Nodes is proposed. Based on this, an Intra-domain Routing Protection Algorithm Based on Critical Nodes is studied, where the efficiency and routing availability are considered. Then, we study how to implement link load balancing to reduce the network congestion during fault recovery. Finally, an experimental platform will be established and key technology testing and verification be carried out on it. The objective of this project is to provide a theoretical foundation and demonstration platform for the deployment of routing protection scheme in the intra-domain routing.

研究表明，网络中的故障频繁发生。当网络出现故障时，目前互联网部署的域内路由协议需要经历收敛过程，在此期间将有大量报文丢失，导致用户体验下降，严重影响了因特网服务提供商（ISP，Internet Service Provider）的服务质量。因此，提高域内路由可用性成为亟待解决的一个科学问题。业界通常采用路由保护算法来提高域内路由可用性，然而已有的路由保护面临两个问题：（1）没有兼顾执行效率和路由可用性（2）没有很好解决故障恢复期间的网络拥塞问题。因此，本项目首先建立基于路由保护的路由可用性模型；然后设计高效的计算关键节点的算法，在此基础上研究基于关键节点的路由保护算法，兼顾执行效率和路由可用性；接着研究如何实现链路负载均衡，从而降低故障恢复期间的网络拥塞程度；最后搭建实验平台，进行关键技术的验证。项目可以为ISP解决域内路由可用性提供一种兼顾执行效率、路由可用性和链路负载均衡的解决方案。

随着互联网规模的膨胀，大量的实时应用部署在互联网上，这些实时应用对网络时延提出了更加严格的要求。然而目前互联网部署的域内路由协议无法满足实时应用对网络时延的要求，因此提高域内路由可用性成为一项亟待需要解决的关键科学问题。学术界和工业界提出利用路由保护方案来提高路由可用性，从而减少由于网络故障造成的网络中断和报文丢失。已有的路由保护方案将网络中的节点同等对待，没有考虑节点在网络中的重要程度，然而实际情况并非如此。因此，本项目提出了一种基于关键节点的域内路由保护算法，首先，建立了基于路由保护的路由可用性模型，从而可以定量衡量路由可用性；其次，建立了节点关键度模型，从而定量衡量网络中节点的重要程度；然后，基于路由可用性模型和节点关键度模型，提出了基于关键节点的域内路由保护方案。本项目利用LFA计算网络中的关键节点，然而，已有的LFA实现方式算法时间复杂度大，需要消耗大量的路由器CPU资源。针对该问题，本项目严格证明，当网络中出现单故障时，只需要为特定的节点计算备份下一跳，其余受该故障影响的节点的备份下一跳和该特定节点的备份下一跳是相同的。基于上述性质，分别讨论了对称链路权值和非对称链路权值中对应的路由保护算法。. 在采用路由保护算法应对网络故障时，受故障影响的流量将被切换到备份路径上进行传输，这可能导致网络拥塞，造成报文传输时延增加，违背了路由保护方法设计的初衷。但是已有的负载均衡算法都需要完整的流量矩阵，并且需要集中式方法求解。我们研究如何在没有流量矩阵的前提下实现一种基于逐跳计算的分布式负载均衡算法。该算法首先为所有节点设置虚拟流量，然后根据虚拟流量计算所有链路的代价，最后采用分布式算法计算最优路由。该算法采用分布式方法解决网络拥塞问题。本项目的研究成果为ISP解决路由可用性和网络拥塞问题提供一种全新的高效解决方案。