论文部分内容阅读
随着互联网日益普及和规模的急剧扩大,互联网已经成为全球最大的通信基础设施,并且在人们的日常生活中起到了重要的作用。现在互联网部署的域内路由协议采用最短路径和尽力而为的方式传输数据。然而,随着各种新型应用的不断涌现,例如,网上股票交易、流媒体和在线游戏等,这些新型应用对网络的时延和网络的可用性提出了更加严格的要求,因此这种传输方式已经不能满足实时应用对网络时延和网络可用性的要求。多路径路由可以提高网络的可用性和生存性,从而有效提升网络的服务质量。本文的主要研究内容和贡献如下:1、提出了基于路由度量的域内多路径路由的模型,利用该模型可以清晰的分析和高效的解决多路径路由中的环路问题,从而为多路径路由计算提供统一的框架。路由度量的代数模型由五元组(S,?,w,⊕,)组成,其中S是网络中所有路径的集合,?是路径连接操作,w是一个函数,该函数的功能是将路径映射为该路径的简单代价,⊕是一个二元操作符,是一个偏序关系。2、基于路由度量模型,提出了高效的域内多路径路由计算方案DMPA(Dynamic Multipath Algorithm)和LMPA(Lexicographic Multipath Algorithm)。这两种算法都是分布式算法,因此每个结点独立运行上述算法并且不需要彼此交互除链路状态之外的其它信息。它们的正确性和高效性均可根据路由度量模型得到严格证明。3、研究了域内多路径路由的增量部署方案。DMPA和LMPA都支持路由器级别的增量部署,本文提出了分别利用贪心算法、模拟退火算法和遗传算法来实现增量部署,实验结果表明遗传算法的性能是最优的,并且在大部分网络中仅仅需要部署40%左右的关键结点,网络的可用性就可以得到大幅度的提高。4、提出了基于多下一跳和备份路径的混合链路保护方案(HLP:Hybrid Link Protection)。HLP的执行过程分为两个步骤,首先进行多下一跳保护(MNP:Multiple Next-hop Protection):利用扩展的无环路条件(EDC:Extended DownStream Criterion),计算源到目的的多个下一跳。然后,根据MNP的计算结果,进行备份路径保护(BPP:Backup Path Protection):计算出所有结点的关键链路,并根据关键链路的重要性选择必要的链路进行保护,从而使网络的可用性得到最大幅度的提高。