（通信与信息系统专业论文）网络设备中分组调度算法的研究

《（通信与信息系统专业论文）网络设备中分组调度算法的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、摘要摘要构造支持各种多媒体业务的宽带综合业务网络是电信运营商的重要任务。需要支持的业务包括话音、视频会议、网页浏览和虚拟专用网等。这就要求电信设备制造商提供支持端到端QoS(QualityofService：服务质量)的网络设备和解哮方案。／对于一个业务流来说，QoS的指标包括端到端的分组时延(delay)、时延抖动(delayjitter)、通过速率(throughput)以及丢失率(10ssrate)等。分组调度就是以一定的规则在等候服务的分组中选择服务对象的过程，是一种至关重要的支持QoS的技术。J本论文研究在网络设备中进行分组调度的各种有效方法。份组调度主娄包括两种技术，流调度(fl

2、owscheduling)和交换矩阵调度(switchmatrixscheduling)。前者依据公平性决定对各个流服务的顺序，后者将交换机的输入端和输出端匹配，解决交换结构(switchfabric)中的竞争，用于交换结构为crossbar(交叉连接矩阵)的情况。通常，网络设备中的分组调度方案要综合这两种技术同时加上“反压”等手段。从二十世纪九十年代初以来，在分组调度这一研究领域出现了一系列的研究成果，包括_i『FQ、GPS、VirtualClock、wF2Q、∥Q+、$PFQ、再RR、DRR等多种流调度算法和iSLIP等多种交换矩阵调度算法J本文第一章对各种调度算法进行了综述，并指出有待

3、解决的问题。7／随着Web上多媒体应用的布断增多，在终端设备上实现QoS的需求也日益迫切：基于ATM终端应用背景Z本文第二章提出了一种解决VC带宽分配的信元调度算法FNVST(fairlqeB．rvirtualsendtime)，可以使多个应用程序同时以不同的信元速率发送数据，适用于ATM网卡。lGPS类型的调度算法(被称为PFQ：PacketFairQueuing)的实现复杂性之一是夯组时标的计算和存储。以往文献中的方法是当每一个分组到达时为其计算并PerSession)。相对于OTPP，它可以节省大量的存储及处理时标的开销．分析和计算机仿真表明0TPS是一种有效的实现PFQ的方法。本文第

4、四章研究了按调度表轮循的调度方法．，在第四章第一节中，我们将分组公平排队算法中基于时标排序的特点应用于基于调度表的周期性轮循算法，提出了一类基于调度表的公平轮循算法(越rroundrobin：FRR)oFRR中的一种算法ShapedFairRoundRobin(ShFRR：整形公平轮循)既具有PFQ保证连接的带宽和时延的特性，又具有轮循类算法实现简单的优点。FP．R适用于分组定长的ATIvI设备，能否使这种基于调度表的调度方法支持变长分组的调度昵?在第四章第二节中，在ShFRR的基础上，结合亏空轮循(DRR)算法采用服务量定额和亏空电子科技大学博士论文计数器支持变长分组的特性，提出了一种新的

5、适用于变长分组的调度算法，低时延亏空轮循(LowLatencyDeficitRoundRobin：LL-DRR)。仿真和理论分析表明，在时延性能上LL-DRR比DRR有显著的改善。分组公平排队算法WF心从原理上可以支持变长分组的调度，由于实现复杂性随连接数增加而增大，当连接数很多时，实现相当困难．能够用按速率分组(G时oupmgPerRate)方法实现的分组调度算法需要具备LBT00canybounded血嘲她n妫和OBT(globallybounded血acstamp)性质．当w—廿在ATM环境下调度分组时，具备LBT和GBT性质，能够用GroupingPerPate方法实现。当wF2Q+

6、在分组变长环境下调度分组时，不具备LBT和GBT性质，不能用C椭upingPerRate方法实现，而需要甩按服务间隔分组(GroupingPerServiceImerval)方法，我们认为CⅡoapmgPerServiceInterval比OroupingPerRate实现复杂。在第五章我们提出了一种新的算法Deficit-WFb-(Dw产Q+)，它既含有DRR算法利用Quantum寄存器支持变长分组的特性又利用wPQ+算法做到在服务量分配上尽量公平。DWPam的显著特点是可以用按服务频率分组(GroupingPerServiceFrequency)的方法实现，而此方法实现难度与Oroupm

7、gPerRam相当，比C_rmupingPerScfvi∞Int㈣l简单。理论分析和仿真实验表明，DWF2Q+具有良好的性能，能够保证业务流盼预约带宽和时延。在研究流调度算法时，我们都假设交换机是输出排队的，实际的交换机大多需要在输入端排队，当前的主流交换式路由器的交换结构(switchfabric)主要有两种．一种是Sha．redMemory(共享缓存)。一种是crossbar(交叉连接矩阵)。针对这两种情