EPFTS平台上基于服务质量的调度算法研究

摘要

随着网络应用的普及和多媒体业务在网络上的剧增，因特网同时面临着高速交换、服务质量、安全和移动性四个方面的严峻挑战。由于基于现有网络的增强措施难以从根本上解决以上问题，人们逐渐认识到实现下一代因特网的关键在于网络体系结构。本论文的研究背景是西南交通大学四川省网络通信技术重点实验室提出的下一代Internet体系结构——单层用户数据交换传输平台的体系结构(Single-layer User-data switching Platform Architecture，SUPA)及其关键技术——面向以太网的物理帧时槽交换技术(Ethernet-oriented Physical Frame Timeslot Switching，EPFTS)。 基于带外信令思想，SUPA将用户数据交换平台与控制管理平台分离。通过EPFTS技术，SUPA将用户数据交换平台简化为单层结构，有利于提高用户数据交换效率和提供服务质量保障。SUPANET(指支持SUPA的网络)在第一阶段的目标是成为服务质量可保障的高速交换传输网络。SUPANET中服务质量保障框架是由信控管理平台和用户平台的上的QoS机制共同构成。本文以SUPA用户平台上提供服务质量保障为主要目标，集中研究了用户平台上的主要QoS机制-业务调度机制。 传统网络上业务突发是引起网络拥塞和性能急剧下降的重要原因。为了在SUPANET中提供服务质量保障服务，本文试图引入基于速率控制的业务调度机制来控制业务流服务质量，如时延和时延抖动，研究结果表明这是一个可行的路线。本文研究过程中始终以具备实现可行性和扩展能力为两个前提条件，首先从为EPFTS交换平台设计基于速率控制的服务策略开始，然后研究了单个交换机内基于速率控制的分组调度机制及其特点；最后扩展到多节点互联的网络，研究了网络中在相邻节点之间通过速率控制实现网络QoS保障的机制。 论文主要研究内容和结论如下： (1)根据EPFTS技术特点，本文研究了SUPANET中业务流速率控制方法，提出了一种基于盈余时槽的速率控制策略(Surplus Timeslot based Rate Controlling，STRC)。STRC利用了业务预留时槽对业务流输出进行速率控制。本文在STRC的基础之上提出了两种调度原则——MASF(Most Available Surplus timeslot First)和STRR(Surplus Timeslot Round-Robin)。性能分析和仿真实验结果表明这两种调度原则均具有带宽保证和业务流输出速率受限的特征。 (2)由单个交换节点出发，研究IQ(Input Queuing)交换机和CICQ(CombinedInout and Crosspoint Queuing)交换机中基中速率控制的分组调度问题。基于STRC策略和以端口对为服务对象，本文先后针对IQ交换机提出了分组调度机制TRWFS(Timeslot Reservation Weighted Fair Scheduling)，针对CICQ交换机提出了“MASF/RR”和“STRR/RR”两种调度方案。研究结果表明虽然增加了业务流时延，STRC策略可以提高交机的吞吐能力，而且业务输出被平滑。 (3)面向多节点互联的网络环境，设计了一种新的GR(Guaranteed Rate)服务器--TRSFS(Smoothed Fair Scheduling based on nmeslot Reservation)。TRSFS是一种基于速率控制的非持续工作的GR服务器，通过平滑业务输出的方式限制业务输出的突发程度，而且TRSFS完全基于整数运算，易于通过软硬件实现高速处理。TRSFS的提出为在多节点互联环境下研究端到端的QoS保障机制奠定了基础。 (4)以支持网络扩展的方式提出一种业务流端到端的QoS保障解决方案一PPFAS (Port-Pair Fair Aggregation and Scheduling)。PPFAS基于“同一端口对上交换的所有微流视为一个宏流”的策略，解决了业务流扩展问题，并通过输入输出组合排队和用TRSFS作为各端口上的信元调度器，实现了一种完全分布式的CIOQ(Combined Input and Output Queuing)交换机。仿真实验结果表明PPFAS以稍许增加时延为代价，获得以下性能点：①交换路径不完全相同的业务流之间影响减弱；②业务流的端到端时延抖动减小；③通过适当控制交换机各端口负载，交换机吞吐能力可达100％。 本文研究工作表明基于速率控制的分组调度机制虽然增加业务流时延，但更多地提升了其它服务质量性能指标。本文相关研究成果对于SUPA交换机的设计具有参考意义和实际应用价值，特别是PPFAS方案中提出的分布式CIOQ交换机对实现SUPANET端到端的服务质量保障具有可行性。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究背景

1.1.1下一代网络体系结构研究

1.1.2基于BSF-OES的NGI研究策略

1.1.3 SUPA与SUPANET

1.1.4 EPFTS交换技术

1.2 SUPANET的服务质量保障体系

1.2.1网络QoS和流的定义

1.2.2一般QoS实现框架

1.2.3 SUPANET中QoS机制

1.3本文研究内容及贡献

1.4论文结构安排

第2章相关研究工作

2.1交换机结构和交换结构

2.2分组排队和调度算法

2.2.1输出排队调度算法

2.2.2输入排队调度算法

2.2.3输入输出组合排队的调度算法

2.3分组调度算法QoS性能分析

2.4本章小结

第3章SUPANET中基于速率控制的业务调度策略

3.1下一代网络需要流量控制

3.2速率控制服务器的概念

3.3基于速率控制的EPF调度策略

3.3.1理想的流体调度模型

3.3.2基于STRC的分组调度机制

3.4基于STRC的分组调度算法

3.4.1有效盈余优先的调度原则-MASF

3.4.2基于盈余时槽轮询的调度规则-STRR

3.4.3仿真实验

3.5本章小结

第4章STRC在可扩展交换机中的应用

4.1 STRC在IQ交换机中的应用

4.1.1IO交换机与分组调度机制

4.1.2TRWFS调度策略

4.1.3仿真实验与仿真结果

4.1.4小结

4.2 STRC在CICQ交换机中的应用

4.2.1 CICQ交换机与分组调度机制

4.2.2信元调度算法MASF/RR和STRR/RR

4.2.3调度算法性能和实现复杂度分析

4.2.4仿真实验结果

4.2.5小结

4.3本章小结

第5章TRSFS—基于预定时槽平滑输出的公平调度机制

5.1业务平滑输出调度相关研究

5.2TRSFS调度机制

5.2.1 GR服务器理论参考模型

5.2.2TRSFS工作原理与实现机制

5.3TRSFS性能分析

5.3.1TRSFS下请求队列长度有界

5.3.2TRSFS是GR服务器

5.3.3业务流输出受限特性

5.3.4算法公平性能分析

5.3.5算法实现复杂度分析

5.3.6阈值D的界定与分析

5.4仿真实验结果

5.4.1仿真配置

5.4.2仿真实验结果

5.5本章小结

第6章基于TRSFS的流聚集调度方案

6.1流聚集调度相关研究

6.2.流聚集调度方案PPFAS

6.2.1交换机结构和信元排队方式

6.2.2基于TRSFS的信元调度机制

6.3聚集调度方案PPFAS性能分析

6.3.1本地时延上限

6.3.2缓存容量需求分析

6.3.3输出突发性

6.3.4实现复杂度分析

6.4仿真实验

6.4.1单节点仿真实验

6.4.2多节点互联仿真实验

6.5本章小结

总结与展望

致谢

参考文献

附录

攻读博士学位期间发表的论文及科研成果