并行QoS路由预计算及链路负载问题研究

摘要

随着网络应用的飞速发展，为保证网络的可靠性，多数园区网采用多重ISP(Internet Service Provider)链路接入因特网。这些园区网中有着大量的客户群，网络拓扑结构错综复杂。在当今网络固有带宽不能实时满足客户需求的情况下，针对多链路网络，研究路由优化及链路负载问题具有非常现实的意义。
　　 作者基于服务质量QoS(Quality of Service)多目标路由优化的理论，采用并行路由寻优的思想对多链路网络的QoS 路由优化问题进行了研究。并在此基础上，采用链路时延和剩余带宽二元目标优化思想对多链路网络的流量负载均衡问题进行了研究。本文主要贡献如下：
　　 (1) 有限节点网络的复杂QoS 路由预计算问题将路由问题分成与实际请求无关的可行路径计算和与实际请求相关的路由优化选择两部分。提出并设计了QPAS(QoS metrics Parallel Algorithmbased on Shortest path)并行算法和基于网络分区的两级并行算法。模拟实验结果表明，采用并行算法后，寻优复杂度降低，最大加速比明显提高，说明并行算法能够在很短的时间复杂度内处理QoS 路由预计算问题，适用于有限节点网络的QoS 路由寻优。同时通过多目标优化分析得到了两级并行算法的最大加速比，以及分区处理器和QoS 度量处理器的基本配置规律。
　　 QoS 路由预计算主要解决了多链路网络的QoS 路由优化问题，但链路负载问题却并未得到有效解决，这是本文的另外一个研究内容。
　　 (2) 多链路网络流量负载均衡问题链路时延和剩余带宽是负载均衡问题重点考虑的两个QoS 度量。基于这两个QoS 度量二元目标优化的思想，提出并设计了多链路负载均衡算法DBCTIA(Delay and residual Bandwidth's Covariance Target IterationAlgorithm)。在原始的切割调度样本中，基于链路时延和剩余带宽的协方差值，对IP路由表的大小和数量进行二次分割调整，使得多重链路达到时延及剩余带宽在一定程度上的均衡。模拟实验结果显示，在网络重载情况下，DBCTIA对多链路时延和剩余带宽的均衡效果较为显著。