面向互联网流量工程的网络测量及路由调整算法研究

摘要

近年来，随着互联网的飞速发展，网络性能面临严峻挑战，流量工程成为互联网进一步发展的关键性问题。由于网络传输速度日益加快，新业务不断出现，目前的流量工程技术已经不能满足高速网络性能优化的要求，更无法满足未来网络发展的需要。本文重点研究了TCP往返时延测量、高速网络中的大流检测、高速网络中的路由调整，为解决流量工程中的一系列问题提供基础，从而改善网络的性能和服务质量。本文主要研究工作及内容如下： (1)被动测量TCP连接往返时延(RTT)对网络设计、流量工程、p2p网络性能优化等方面都有重要作用。本文针对现有被动测量方法的不足之处，提出一种在TCP连接的非发送端被动测量PTT的CROSS算法。CROSS算法通过互相关函数判断数据分组与ACK分组之间的对应关系，继而获得TCP连接的RTT值。通过PlanetLab网络上的实验数据验证，CROSS算法不但能够在TCP连接建立后的任意阶段计算该连接的RTT，并且可以在网络性能较差导致RTT变化较大时准确测量。 (2)互联网中大流数目少但流量大，因此在网络拥塞发生时快速准确地找出网络中的大流并对其路由做出调整，就能够有效地提高网络性能，同时避免了处理大量小流导致的系统开销。传统上基于采样或Filter结构的大流检测算法存在准确率不够高的问题。不能满足互联网应用的需要。本文提出一种基于两级LRU结构的大流检测算法LRU2，其中第一级LRU用于小流过滤，第二级LRU用于对大流的准确计数。文章推导了最坏情况下LRU2算法对大流统计的误差上限。并且通过分析证明算法具有10Gbps的线速处理能力。基于实际互联网数据的实验表明：与现有算法相比，LRU2算法具有更高的准确性和实用性。 (3)互联网流量分布的不均衡会导致拥塞的发生，此时对某些造成拥塞的关键大流进行路由调整能够有效地改善网络的性能。本文提出一种针对单条流的路由调整算法，一方面降低了网络最大带宽利用率，另一方面把被调整流的路径长度限制在可接受的范围之内，从而保证了该流的服务质量。基于真实网络拓扑和流量的实验表明：新算法能够有效缓解骨干网拥塞，最多可降低最大带宽利用率近50％。仿真实验显示：与现有算法相比，新算法能够同时满足关键流路径长度和降低最大链路带宽利用率两方面的要求。此外，算法复杂度为O(N2logN)，好于现有的大部分路由调整算法。 (4)互联网中发生多链路拥塞的概率虽然较小，但也会时常出现，并且难于处理，给网络性能优化带来了困难。针对这一问题，本文提出了一种基于概率选择下一跳的关键流路由调整算法。当网络中出现多链路拥塞时，算法通过同时调整多条关键流路由的方式改善网络性能，使流量分布更加均衡。仿真实验表明，新算法有效地提高了网络吞吐量，很好地实现负载均衡，同时通过控制路径长度保证了服务质量。

目录

文摘

英文文摘

论文说明：缩略语、图表目录

声明

第1章绪论

1.1 引言

1.2 本文主要贡献

1.3 本论文的结构和安排

1.4 本章参考文献

第2章 非发送端被动测量TCP往返时延

2.1 引言

2.2 相关工作

2.3 问题

2.4 算法

2.4.1 互相关函数

2.4.2 d2的测量

2.5 实验

2.6 结论

2.7 参考文献

第3章 基于两级LRU机制的大流检测算法

3.1 引言

3.2 相关工作

3.3 LRU2算法

3.3.1 LRU算法及其缺点

3.3.2 基本LRU2算法LRU2_V1

3.3.3 算法分析

3.3.4 参数之间的关系

3.3.5 算法实现

3.3.6 改进的LRU2算法LRU2_V2

3.4 实验及算法比较

3.5 极端情况下的算法改进LRU2_V3

3.6 结论

3.7 参考文献

第4章 保证时延的关键流路由调整算法

4.1 引言

4.2 相关工作

4.3 问题建模

4.3.1 网络模型

4.3.2 问题描述

4.4 算法

4.4.1 定理

4.4.2 算法描述

4.4.3 复杂度分析

4.4.4 实现

4.5 实验仿真

4.5.1 Abilene2数据仿真

4.5.2 MIRANet拓扑仿真

4.6 结论

4.7 参考文献

第5章 自适应的关键流路径全局调整算法

5.1 引言

5.2 相关工作

5.3 问题建模

5.3.1 网络建模

5.3.2 问题描述

5.4 算法

5.4.1 关键流干扰问题

5.4.2 选路算法

5.5 仿真实验

5.6 结论

5.7 参考文献

第6章 结语

致谢

个人简历及参加的科研工作

附录：在攻博期间撰写的论文