基于节点多样性的域内路由保护算法

已有的路由保护方案都没有考虑网络中节点的重要程度,然而在实际网络中不同节点在网络中的重要程度是不相同的。针对该问题,提出一种基于节点多样性的域内路由保护算法（intra-domain routing protection algorithm based on node diversity,RPBND）。计算节点构造以目的为根的最短路径树（shortest path tree,SPT）,从而保证RPBND算法和目前互联网部署的路由算法的兼容性;在该最短路径树的基础上构造特定结构的有向无环图（directed acyclic graph,DAG）,从而最大化路由可用性。实验结果表明,RPBND极大地提高了路由可用性,降低了故障造成的网络中断时间,为ISP部署域内路由保护方案提供了充分的依据。     

基于关键网络状态的域内路由可用性研究

业界通常采用路由保护方案来提高域内路由可用性.然而已有的路由保护方案存在下面两个方面的问题:a)没有考虑网络中链路的失效概率,同等对待网络中所有的链路,事实上在互联网中,不同链路的失效概率是不同的,因此应该在路由保护方案中考虑链路的失效概率;b)将保护链路的数量作为设计目标,事实上方面某些链路出错的概率非常低,保护这些链路反而会增加开销,而另一方面某些链路出错的概率非常高,需要重点保护这些链路.因此应该将路由可用性作为路由保护方案的设计目标.针对上述两个问题,提出了一种基于关键网络状态的域内路由保护方案(RPBCNS),该算法首先通过链路失效概率计算出所有的关键网络状态,然后在每种关键网络状态下计算节点对之间相应的路径,保证节点对之间路径的多样性,从而使得尽可能多的节点对满足路由可用性需求.仿真实验将RPBCNS算法与主流算法ECMP、DC、path splicing分别在三个真实网络中进行对比,在网络可用性和节点对可用性满足率上RPBCNS的性能明显优于其他三种算法.仿真结果表明,RP-BCNS不仅具有较高的网络可用性,并且能够使得尽可能多的节点对满足路由可用性目标,更符合实时应用的实际需求.     

基于节点偏序关系的路由可用性框架研究

为了维护路由可用性,需要采取一定的路由保护策略来防止网络故障可能对网络造成的影响。因此,提出了一种基于节点偏序关系的路由可用性框架,该框架首先利用节点之间的偏序关系构造有向无环图,然后根据构造的有向无环图为每个节点计算备份下一跳节点。在此框架基础上,根据节点之间的偏序关系提出了四种路由保护方法。实验结果表明,四种路由保护算法都拥有较高的故障保护率,能有效降低故障造成的网络中断,在真实拓扑中故障保护率可以到达89.76%,在模拟拓扑中故障保护率达到98.995%,几乎接近100%。     

基于关键节点的域间路由安全机制

BGP作为Internet域间路由的基本协议, 其安全问题一直受到学界的关注, 特别是安全性与实现难度之间的折中。针对传统解决方案S-BGP(secure BGP)的不足, 在定义关键节点KN(key node)的基础上, 利用KN对路由信息安全验证的特殊功能, 提出了更加轻量级的解决方案——基于关键节点的域间路由安全机制 SR-KN(secure routing based on key node)。通过对比分析表明, SR-KN在保证BGP安全的前提下, 减少了全网证书规模及存储量, 且具有更好的收敛性能。     

基于传播动力学的域间路由系统关键节点识别方法

域间路由系统是互联网的关键基础设施,对域间路由系统中的关键节点实施保护具有重要意义。针对现有关键节点识别方法识别出的关键节点不能反映节点在失效传播过程中起到关键作用的问题,提出了基于传播动力学的关键节点识别方法。该方法通过综合考虑节点失效后引发的负载重分配和UPDATE报文传播对周围节点和边产生的影响,提出了基于DDF-CFM模型的节点重要性评估模型。实验结果表明,该方法相比已有方法识别关键节点的准确程度至少提高7.3%。同时,在10 000个网络的规模下,仅5个关键节点失效就将导致大规模的域间路由系统级联失效。     

基于逐跳方式的单链路故障保护算法

当网络中的某条链路出现故障时,互联网部署的域内路由协议需要重新收敛,在收敛过程中经过该链路的报文将会被丢弃。针对该问题,IETF(the Internet Engineering Task Force)提出了快速重路由保护框架,利用该框架可以有效地解决网络中单链路故障造成的报文丢失问题,然而该方案并不能完全保护网络中所有可能的单链路故障。基于该框架研究者提出了一种基于隧道的解决方案,该方案虽然可以提供100%的单链路故障保护,但是需要辅助机制的协助,开销较大,难以实际部署。因此,提出了一种基于逐跳方式的针对单链路故障的全保护方案,该方案可以解决网络中任意的单链路故障造成的报文丢失问题。     

基于关键节点时延约束低代价组播路由算法

针对时延约束下低代价组播树的构建方法,提出了一种基于关键节点的时延约束低代价组播路由算法.该算法对已有的动态时延优化的链路选择函数进行改进,并加入关键节点和关键次数的概念.在首次选择目的节点时,重点考虑关键节点和关键次数因素,降低了选择低代价链路的时间复杂性,再利用改进后的链路选择函数依次选择节点加入树中,进而产生满足要求的组播树.实验仿真结果表明,该算法不仅能正确构建出时延约束低代价组播树,且与其他算法相比,构成组播树所需平均时间更少.     

基于有向无环图的互联网域内节能路由算法

互联网在快速发展的过程中面临新的挑战,其中网络能耗问题尤为突出。学术界提出了大量用于 解决网络能耗问题 的方案,然而这些方案都考虑了网络中的实时流量数据,计算复杂度较高,不利于实际部署。对此,提出一种基于有向无环图的互联网域内节能路由算法(Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph,EEBDAG),该方法 利用有向无环图来解决因链路关闭造成的路由环路和网络性能下降等问题, 仅须考虑网络拓扑结构,不需要考虑网络中的实时流量数据 。实验结果表明,EEBDAG不仅具有较低的节能比率,而且具有较低的链路利用率,为ISP解决互联网节能问题提供了一种全新的方案。     

基于最小路径交叉度的域内路由保护方案

已有的路由保护方案面临下面两个问题:(1)默认路径和备份路径包含的公共边数量较高,如ECMP和LFA等;(2)为了计算两条包含公共边数量较少的路径,限制默认路径不能使用最短路径,如红绿树方案等.针对上述两个问题,首先将计算默认路径和备份路径描述为一个整数规划问题,然后提出采用启发式方法求解该问题,接着介绍了转发算法,最后通过仿真实验和真实实验对算法进行了测试.实验结果表明,该算法不仅具有较低的计算复杂度,而且可以降低默认路径和最短路径包含的公共边的数量,提升网络可用性.     

基于优化链路权值的域内路由保护方案

目前,互联网部署的域内链路状态路由协议,如开放最短路径优先(Open Shortest Path First,OSPF)和中间系统到中间系统(Intermediate System-to-Intermediate System,IS-IS),采用被动恢复方案应对网络故障。随着网络的发展,大量的实时应用部署在互联网上,OSPF的收敛时间无法满足这些实时应用对收敛时间的需求。因此,学术界和工业界提出采用路由保护方案来应对网路中出现的故障。然而,已有的路由保护方案存在两个方面的问题:1)默认路径和备份路径的交叉度较高,如LFA；2)为了计算两条交叉度低的路径,对默认路径加以限制,即默认路径不采用最短路径,如Color Tree。为了解决上述两个问题,首先将上述问题归结为整数规划模型,接着利用启发式方法计算近似最优解,最后在实际网络和模拟网络中对所提算法进行了大量实验。实验结果表明,所提算法可以降低默认路径和备份路径的交叉度,极大地提高网络的可用性。     

基于代数连通度的域内节能路由算法

通过节能路由算法减少网络能耗是网络中需要解决的一个关键性的科学问题。如今已有的节能方案都是在已知流量矩阵的前提下研究网络节能,由于实时流量难以获取,使得这些方案都难以在实际中部署。因此,文中提出一种基于代数连通度的域内节能方案(Intra-domain Energy Efficient Routing Scheme Based on Algebraic Connectivity,EERSBAC)。EERSBAC不需要网络中的实时流量矩阵,仅依靠网络中的拓扑结构就可以实现节能。首先,提出链路关键度模型,利用链路关键度模型计算出网络中所有链路的重要程度;然后,提出代数连通度模型,利用代数连通度模型可以定量的衡量网络的连通性能。实验结果表明,EERSBAC不仅能够降低网络能耗,而且具有较小的路径拉伸度。     

基于混合软件定义网络的单节点故障保护方法

软件定义网络(Software Defined Network,SDN)是由美国斯坦福大学Clean Slate课题组提出的一种新型网络体系架构,该架构通过解耦控制平面和转发平面的功能来实现网络流量的灵活转发.但是,由于经济开销和技术条件的限制,互联网服务提供商的骨干网必定长期处于传统设备和SDN设备共存的混合SDN状...     

一个基于增强学习算法的路由模型

由于Internet的不断发展，现有的路由算法为适应不同的网络要求，从一开始的RIP、OSPF、BGP等几种，衍生出很多新的适用于特殊网络的路由协议。本文提出一种基于增强学习算法的路由模型。将每个路由节点看作一个Agent，利用增强学习算法的思想使得每个节点在不了解网络拓扑结构的情况下从向邻居转发的概率获得网络的信息，这样路由节点可以选择一个较优的转发方向。同时，节点能对网络的拥塞等情况作出调整。该模型为一些具体网络的路由协议，特别是QoS类路由算法提出了一个新的路由思想。     

基于全分布式分组无线网络的蚂蚁路由算法

该文介绍了全分布式分组无线网络中路由算法。当前广泛运用的OSPF路由算法在网络的链路发生阻塞时，不能及时探测到链路状况。当链路发生拥塞时，在发包率继续增大的时候，只能简单地丢弃数据包。就此该文在分布式的无线网络中应用了蚂蚁算法。该算法由发送探测包来担任“觅食蚂蚁”在短时间内找出最优路径，分散流量，避免网络的拥塞。通过仿真结果表明：该算法在网络利用率和数据包传送时延上有较好的改善。     

基于遗传算法的QoS多播路由优化算法

研究了带宽、延时、延时抖动和分组丢失率约束以及费用最小的QoS多播路由优化问题,提出了一种启发式遗传算法、该算法采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题。交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性。该算法采用简单维护操作维护好所有的不可行的染色体,交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性。计算机仿真实验证明该算法快速有效,可靠性高。