基于曲线拟合的RED算法改进研究

摘要

在网络拥塞控制中，RED[1](Random Early Drop)算法的应用非常广泛。从经典的TCP/IP协议簇到新兴的无线自组网，RED算法都为网络拥塞控制提供了很好的借鉴。RED算法作为一种主动式队列管理算法[2]，克服了被动式队列管理算法“滞后”的网络响应特征，通过设置阈值使网络发生拥塞之前就采取相应的措施来避免拥塞。但是，RED算法的核心问题是讨论RED算法的参数设置，即阈值问题——怎样在一个相对稳定的网络中平衡各种性能之间的关系。目前的改进方法主要集中在RED算法参数的微调上，即根据某一项网络容忍值进行参数调整，这在容忍网络中可以取得很好的效果。但在实验过程中我们发现，对于MANET(Mobile Ad hoc Network)网络，如果网络交换的分组数比较多，通信流量较大，会有以下两个问题：
　　（1）在通信量比较大的情况下，数据包在传输时就会发生阻塞，有一部分数据包就无法到达目的节点。此时，源节点没有收到目的节点应答，就会重新发起路由查找，这种情况就会造成大量的RREQ报文在网络中传播，引起RREQ报文拥塞，在这种情况下，就会有更多的数据包无法到达目的节点，导致更多重复的RREQ报文产生，RREQ报文队列中就有很多重复的RREQ报文；
　　（2）大量的RREQ报文拥塞就会造成一个假象，即源节点认为目的节点不可达。此时，源节点和中间结点就会认为这条路径不可达，如果出现这种情况，邻居节点再去定期发送Hello消息来检测链路的完整性反而没有意义，因此怎样让Hello消息随着拥塞程度的变化而变化，需要建立一个模型。
　　针对上述两个问题，本文提出了一种新的反应式 MANET路由协议拥塞控制机制DRED(Dynamically Random Early Drop)，主要分为两个部分：
　　（1）根据分组投递率和数据包发送速率的拟合曲线得到一个分组投递率和RREQ报文平均队列长度的近似拟合函数，根据拟合函数计算出最大门限值和最小门限值，决定 RREQ报文发送方式，在平均队列长度超过最大门限值时，以一定概率丢弃队列中的RREQ报文，并根据平均队列长度动态变化扩展环搜索值；
　　（2）根据平均队列长度动态控制Hello包发送周期和生命周期。
　　仿真结果表明，在没有明显增加路由发起频率的情况下，新的机制降低了平均端到端延时和Hello包开销，提高了分组投递率。

目录

封面

声明

目录

中文摘要

英文摘要

第1章 绪 论

1.1研究的背景、目的和意义

1.2国内外研究现状

1.3存在的问题

1.4本文主要研究工作

第2章 主动式队列管理算法

2.1被动式队列管理算法原理

2.2主动式队列管理算法原理

2.3 RED算法及其改进算法

2.4本文的突破方向

第3章 曲线拟合在MANET网络中的应用

3.1 曲线拟合背景

3.2最小二乘法拟合

3.3 曲线拟合在网络中的应用

3.4 本章小结

第4章 基于曲线拟合的RED算法改进

4.1 拥塞问题

4.2 Q_min和Q_max修正

4.3 P_drop修正

4.4 TTL_THRESHOLD和Hello包间隔修正

4.5 本章小结

第5章 RED改进算法仿真及分析

5.1 实验环境及工具

5.2 仿真策略

5.3 仿真算法实现

5.4 仿真结果及性能分析

5.5 本章小结

总结与展望

参考文献

致谢

附录A 攻读学位期间所发表的学术论文目录