多业务网络中插入式分组调度算法研究

论文摘要

现有的分组调度算法都是基于数据分组,分组的发送过程不可中断。对于变长分组发送,如果有一个比较长的非实时业务（低优先级）分组已经开始发送,同时收到一个急需发送的实时业务（高优先级）分组,那么实时业务分组只好等待发送,这就增加了实时业务分组的延时,并且非实时业务分组的长度越长,数目比例越高,实时业务的时延和抖动性能越差。针对上述问题,为满足实时业务的QoS要求,降低非实时业务分组传输对实时业务的时延和时延抖动的影响,本文提出插入式的分组调度算法。实现此种算法的关键在于:分组插入和恢复控制信息的创建与解析、实时业务插入发送开始和结束时刻的确定。本文选用千兆以太网1000BASE-X PCS子层的8B/10B编码预留的特殊控制码作为分组插入和恢复控制信息。对于插入发送开始和结束时刻的确定,共提出了三种插入式分组调度方法,它们有着不同的优劣。基于优先级的插入式分组调度算法,类似于“中断”,优先级作为判断发送的唯一依据。当需要发送高优先级分组时,挂起正在发送的低优先级分组,等待发送完插入的高优先级分组后,激活挂起的低优先级分组。高优先级的分组在发送的过程中感觉不到低优先级队列的存在,只要它处于高优先级队列的头部就可以发送,而不必等待低优先级队列中的分组发送完毕。通过创建以VoIP和IPTV为代表的实时业务和WWW为代表的非实时业务业务源模型搭建OPNET仿真平台,构建同等条件下的插入式和非插入式分组调度仿真模型,分析比较插入和非插入模式下的仿真结果定量地验证此种算法的可行性和有效性,但同时也发现它在公平性和独立性方面存在一些缺点。为更好地安排实时业务和非实时业务发送机会的顺序和时间长度,提出基于调度表的插入式分组调度算法。该算法根据实时业务队列的预约带宽和最大分组长度建立调度表,然后利用调度表对变长分组的业务流进行整形和调度。实时业务不同的QoS要求和业务特性决定了在调度表中为其安排的发送机会的间隔和长度,但基本原则是尽量让业务发送机会的安排和业务流的属性一致,这样可以保证实时业务不同的时延或时延抖动要求。调度表在连接到队列的业务流建立或释放连接时,进行更新。如果业务流建立和释放连接频繁,那么调度表的更新就会很频繁,这就加大了交换节点的工作量,并且基于调度表的插入式分组调度算法需要和DRR一起处理变长分组的问题,对于分组长度变化范围比较大的业务,可能会凸现DRR的一些固有缺点,所以提出基于ShVC的插入式分组调度算法。这种算法首先对业务流进行流分类,粗略划分为实时业务队列组和非实时业务队列组。对实时业务队列组采用ShVC算法,决定了实时业务队列的发送机会,在没有实时业务分组发送的时候,发送非实时业务队列的分组,而非实时业务队列采用保证带宽的调度方法（比如WFQ）等效于一个队列。这种算法在降低ShVC算法复杂度和开销的同时,真正意义上达到实时业务的发送基本不受非实时业务的影响。对于基于调度表和ShVC的插入式分组调度算法,采用相同的业务源模型搭建不同的OPNET仿真平台,验证算法的可行性和有效性。通过上述三种算法的仿真可以看出,插入式分组调度算法不仅较大幅度降低了高优先级分组的时延和时延抖动,同时不会降低带宽利用率,具有很强的实用性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 经典的分组调度算法简介
• 1.2.1 基于轮循的分组调度算法
• 1.2.2 基于GPS 模型的PFQ 分组调度算法
• 1.2.3 基于时延的分组调度算法
• 1.3 业务源建模
• 1.3.1 常见的业务源模型介绍
• 1.3.2 VoIP 业务源特性
• 1.3.3 IPTV 业务源特性
• 1.4 本文主要研究内容
• 1.5 论文章节安排
• 第二章 基于优先级的插入式分组调度算法
• 2.1 插入式分组调度算法简介
• 2.2 基于优先级的插入式分组调度算法技术方案
• 2.2.1 两队列的插入式分组调度算法
• 2.2.2 两队列的插入式分组调度算法实现
• 2.2.3 非插入式分组调度算法
• 2.2.4 三队列的插入式分组调度算法
• 2.3 基于优先级的插入式分组调度算法OPNET 仿真
• 2.3.1 OPNET 仿真操作对象
• 2.3.2 OPNET 仿真结构模型
• 2.3.3 OPNET 仿真场景
• 2.3.4 业务源节点模型
• 2.4 基于优先级的插入式分组调度算法OPNET 仿真结果
• 2.4.1 业务源模型为VoIP 和WWW
• 2.4.2 业务源模型为IPTV 和WWW
• 2.4.3 三队列的调度之单队列业务源
• 2.4.4 三队列的调度之多队列业务源
• 2.4.5 单队列业务源和多队列业务源统计结果比较
• 2.5 本章小结
• 第三章 基于调度表的插入式分组调度算法
• 3.1 整形公平轮循（SHFRR）算法简介
• 3.1.1 公平轮循调度算法
• 3.1.2 ShFRR 算法的缺点
• 3.2 基于调度表的插入式分组调度算法技术方案
• 3.2.1 调度表的生成
• 3.2.2 数据分组的发送
• 3.2.3 技术方案带来的有益效果
• 3.3 基于调度表的插入式分组调度算法OPNET 仿真
• 3.3.1 OPNET 仿真目的
• 3.3.2 OPNET 仿真思路
• 3.3.3 OPNET 仿真场景
• 3.3.4 OPNET 仿真核心节点模型
• 3.4 OPNET 仿真结果
• 3.5 本章小结
• 第四章 基于SHVC 的插入式分组调度算法
• 4.1 整形虚拟时钟（SHVC）算法简介
• 4.1.1 整形虚拟时钟技术方案
• 4.1.2 整形虚拟时钟优缺点
• 4.2 基于SHVC 的插入式分组调度算法技术方案
• 4.2.1 基于ShVC 方案的具体实现
• 4.2.2 技术方案带来的有益效果
• 4.3 基于SHVC 的插入式分组调度算法OPNET 仿真
• 4.3.1 OPNET 仿真目标
• 4.3.2 OPNET 仿真模型
• 4.3.3 OPNET 仿真核心节点模型
• 4.4 OPNET 仿真结果
• 4.5 本章小结
• 第五章 全文总结
• 致谢
• 参考文献
• 个人简介
• 在学期间的研究成果