论文部分内容阅读
互联网中传统的尽力而为传送机制和最短路径路由算法实质上存在导致拥塞的可能。随着互联网规模的日益扩大和用户端接入带宽的不断增加,骨干网发生拥塞的几率也日益提高。网络拥塞不仅会降低网络性能,而且会使得服务提供商难以完成对客户的服务水平的承诺。因此该问题引起了研究者们的广泛关注。流量工程是一种具有重要价值的网络优化技术,它通过优化网络资源的利用效率来避免网络拥塞。多协议标签交换提供的约束路由技术是流量工程的重要工具之一。约束路由机制能够显式地指定数据传输路径,使得路由选择算法能够根据QoS约束和流量工程优化目标进行路径选择。在路由选择阶段结合流量工程优化目标,能够从根本上克服当前互联网所使用的最短路径路由带来的拥塞问题,有效提高网络资源利用率,具有重要的理论意义和应用价值。本文主要针对流量工程中的最小干涉、负载均衡、最小化网络资源耗费等优化目标,对单路径的在线和预计算型约束路由算法,多路径约束路由算法这三类算法进行了研究,取得的主要成绩有:1.面向流量工程优化的在线约束路由算法针对MIRA算法的一个变种I-MIRA算法单纯考虑是否存在干涉的特点,提出了结合负载均衡原则的改进算法IMIRA-LB;针对MIRA的关键链路划分过于简单化的特点,提出了反映干涉程度的链路干涉关键度函数和相应的路由算法MINCF;并提出了综合考虑最小干涉、负载均衡和最小化网络资源耗费(最短路径)三个要素,易于动态调节的混合算法HORA。上述三种算法在路由请求成功率上较之NewMIRA等算法而言都有明显提高。IMIRA-LB算法在KL或者ISPNet等含有常数个入出口对的拓扑中,性能表现较好。但若入出口对数目快速增长时,甚至所有结点都可能是入出口结点时,干涉过于复杂,IMIRA-LB和NewMIRA等算法性能下降的比较明显,甚至下降到最短路径算法的水平。而MINCF和HORA算法在这种情况下通过参数设置实现对算法行为的调节,可以达到较好的性能水平,表现出对不同的网络拓扑和请求序列更强的适应性。2.面向流量工程优化的预计算型约束路由算法针对在线算法对复杂度有严格限制,良好的优化效果和低复杂度往往难以兼顾的问题分别提出了两种预计算算法:预计算链路关键度函数的PreMINCF算法和预计算K条路径的PreKMIP算法。PreMINCF算法具有适用范围广的优点,通过预计算链路关键度使得算法在具有良好优化效果的前提下,在线复杂度降低,执行时间较一般在线算法大为缩短。PreKMIP算法则预计算K条路径,然后输入真实请求序列,按照存各路径上增加该流量负载后网络入出口对最大流之和的变化情况打分排序。PreKMIP算法以运行时间作为折衷,在请求成功率等性能指标上取得了进一步的提高。3.面向流量工程优化的多路径约束路由算法针对现有多路径路由算法大多以负载均衡为目的,较少考虑最小干涉这一问题,提出了两种考虑了最小干涉的启发式多路径约束路由算法。一种是最小化路径数目及干涉算法MPN-MI,该算法能够寻找极小数量的最小干涉路径,从而减轻多路径之间的干涉,以及减轻过多路径带来的信令消息负载压力。另一种算法最大K路径最小干涉多路径路由算法MKP-MITS则更好的兼顾了负载均衡,并能够在分配路径流量时按照最小干涉和负载均衡目标进行流量分配的优化。论文对面向流量工程进行优化的约束路由技术进行了深入细致的研究和探索。所提出的几种约束路由算法在保证请求带宽的前提下,能够根据最小干涉、负载均衡、最小化网络资源占用等优化目标对路由选择进行优化,从而提高请求成功率和吞吐量,并实现均衡负载,提高网络资源的使用效率。其研究成果对于下一代互联网具有良好的理论价值和应用前景。