论文部分内容阅读
当前的互联网络路由算法主要针对尽力发送(best-effort)和基于服务质量(Quality ofService Based)两种数据传输模型，路由的设计正是基于现有的网络数据传输模型来考虑，以如何保证公平性、满足约束、优化性能、减少阻塞为目标并在当前的网络环境下选择最佳路径。目前的网络优化主要依靠增加网络资源来实现。由于网络的动态性，节点对全局网络服务质量状态的了解不精确、而实际的链路状态不仅与链路本身的条件有关，而且受当前网络流量的影响，使得链路状态信息的概率模型难以确定，预计算不够准确，更新路由不实时，路由算法计算复杂度过高而不能在实际网络中应用，算法性能过低而找不到实际存在的可行路径。大部分算法都只能针对路由问题中的某些特殊情况，缺乏普遍性。由于因特网拓扑的复杂性，目前多数路由算法缺少理论和路由模型支持，理论研究困难。此外，路由算法评价标准尚不全面，在性能分析上缺少与多个算法的对比。路由算法仍停留在算法阶段，它必须被写入通信协议才能被实际应用。静态路由中的策略路由规划使数据包按照用户指定的策略进行转发，这种方法对于网络的应用效率、可维护性和可扩展性等方面都有很大影响且不能灵活参考网路状况进行路由调度，不能有效地自动平衡链路负载。
本文主要针对因特网上非常普遍的具有多重链路上联拓扑结构的边缘网络的路由和负载问题进行了较为全面的分析和研究。本文主要贡献如下：
(1)．提出了一种最佳路径MCOP(Multi-Constraints Optimal Path)调度算法。证明了多重链路上联网络中流量和代价博弈是一个非线性互补NCP(Nonlinear ComplementarityProblem)问题，提出了多重链路上联网络中流量和代价的博弈调度模型，给出了链路状态二元组(带宽、时延)多目标优化的路由调度方案，根据代价比率大小决定路由，并用权威的Power公式评价路由算法性能，仿真实验结果显示MCOP在重载时其性能超过了目前公认的最好算法HMCOP。
(2)．提出了一种多重链路上的N元非合作性路由切割调度算法，将地址空间切割为若干个碎片再根据负载状况决策映射，设计了两个辅助算法进一步优化路由切割调度。由于目前尚未发现对比算法，所以作者分别做了算法模拟、NS2网络环境仿真和工程应用实测，所有实验都证明，在静态路由环境中，N元非合作性路由切割调度算法收到了较好路由优化和负载平衡效果。
(3)．实现了IP分组重组的集群调度和并行计算，设计了节点负载平衡算法，开发了基于MPICH共享存储的二级并行计算IP分组重组的并行软件，并投入实际的工程应用，基本解决这一普遍的工程技术难题。
(4)．将路由问题分成与路由请求无关的可行路径计算和与路由请求相关的路由优化选择两部分。提出了基于代价可加性原则的多重QoS度量综合性能代价定义，设计了基于QoS度量的SSAQ串行算法、QPAS并行算法、QPAS和分区并行的两级并行QoS路由快速预计算方法。模拟实验结果表明并行路由预计算方法使时间复杂度大大降低，可快速计算有限节点网络复杂QoS路由，具有较强的普遍适用性。
(5)．提出了基于DTBF的流量整形模型，根据逻辑链路的令牌缓冲分配情况在各个逻辑链路间动态分配令牌，使得各个逻辑链路的平均带宽利用率有较大的提高，有效保证了用户占用资源的公平性，该方法已经投入大规模的工程应用。