输入队列交换机迭代调度算法研究设计

发布时间：2017-08-27 00:01

  本文关键词：输入队列交换机迭代调度算法研究设计

  更多相关文章： 输入队列交换机 迭代调度算法 分布式调度 往返时间 数据包时延

【摘要】：互联网向云计算的持续转变进一步加剧了提高网络带宽的需求。在云计算架构中,业务和数据存放于一个共享的数据中心,并通过互联网被用户所获取。用户和数据中心之间以及在一个数据中心的不同服务器间需要传输大量的流量。为了满足互连高速低时延交换等要求,为多种流量需求设计一个统一的交换机架构是非常可取的。数据交换机通常有两种架构,输入队列交换机和输出队列交换机。由于输入队列交换机每个时隙仅允许每个输入/输出端口发送/接受一个数据包,无需加速,更适合于高速实现,因此也是目前应用最广泛的交换机架构。输入队列交换机的调度算法是实现低时延、高吞吐量性能的关键。另外随着交换机规模的增大,分布式调度也应运而生。本文主要对输入队列交换机的集中式和分布式迭代调度算法两大方面进行了探讨。首先,本文研究了输入队列交换机的集中式迭代调度算法。迭代调度算法能取得极大尺寸匹配(Maximal Size Matching, MSM),是当前应用最广泛的调度算法。迭代调度算法通常由请求、授权和接受三个阶段组成,虽然有些迭代调度算法能取得很好的性能,但是依然存在提升的空间。本文首先对已有算法RR/LQF(Round Robin with Longest Queue First)进行了两方面的改进。一方面,对请求阶段进行了调整,极大程度地降低了时延,提升了性能。另一方面,在复杂度上,提出了一种流水线更新数据包计数器的机制,将其复杂度从O(NlogN)降低为O(logN),更适合于高速扩展。其次,本文提出了一种最大-最小公平的集中式迭代调度算法GRR/LRR (Global Round Robin with Local Round Robin)。GRR/LRR首先采用全局轮询调度,即优先输入-输出对,来最大化匹配尺寸,当全局轮询失败时,进一步通过每个端口的局部轮询指针来进行调度。GRR/LRR的复杂度仅为0(1)。当GRR/LRR执行一次迭代时,能获得比其他相同复杂度和通信开销的算法更好的性能。当GRR/LRR执行多至N次迭代时,我们证明它只需2-1/N倍加速即可达到稳定。最重要的是,GRR/LRR在任何数据源下均能满足最大-最小公平性规则。最后,本文研究了输入队列交换机的分布式迭代调度算法。当交换机的单边端口数目超过64时,集中式调度器受其I/O接口的限制已无法实现。因此需要采用多芯片设计,在每个输入输出端口分布独立的调度器/选择器,即分布式调度器。此时,不同芯片之间的传播时延导致输入输出端口之间存在很大的往返时间(Round Trip Time, RTT),通常为多个时隙。在大部分现存的分布式调度算法中,数据包的最低排队时延总是大于RTT。为了打破这一瓶颈,本文提出了一种请求预测(Request Prediction, RP)机制,当其应用于很多迭代调度算法时,能将低负载时延降低至RTT以下。这种请求预测的思想非常简单,复杂度仅为O(1),而且应用于不同的调度算法时可进行不同的调整以获取更好的性能。
【关键词】：输入队列交换机 迭代调度算法 分布式调度 往返时间 数据包时延
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TN915.05
【目录】：

• 致谢4-6
• 摘要6-8
• Abstract8-13
• 第1章 绪论13-21
• 1.1 高速单芯片交换机设计13
• 1.2 交换机架构13-15
• 1.3 输入队列交换机的迭代调度算法15-19
• 1.3.1 单比特单次迭代算法16-17
• 1.3.2 单比特多次迭代算法17
• 1.3.3 多比特单次迭代算法17-18
• 1.3.4 多比特多次迭代算法18
• 1.3.5 迭代调度算法的设计18-19
• 1.4 本文的工作19-20
• 1.5 本文的结构20-21
• 第2章 集中式迭代调度算法RR/LQF的优化21-29
• 2.1 RR/LQF21-22
• 2.2 RR/LQF的优化22-24
• 2.2.1 时延吞吐量性能的优化22-23
• 2.2.2 流水线重排序机制降低复杂度23-24
• 2.3 仿真结果24-28
• 2.3.1 均匀数据源25
• 2.3.2 突发数据源25-26
• 2.3.3 热点数据源26-28
• 2.3.4 流水线重排序机制对比28
• 2.4 本章总结28-29
• 第3章 一种最大-最小公平的集中式迭代调度算法GRR/LRR29-44
• 3.1 迭代调度算法GRR/LRR30-31
• 3.1.1 GRR/LRR30-31
• 3.1.2 GRR/LRR与其他算法的比较31
• 3.2 GRR/LRR的稳定性研究31-37
• 3.2.1 建立流体模型31-33
• 3.2.2 100%吞吐量证明33-37
• 3.3 GRR/LRR的最大-最小公平性研究37-39
• 3.4 仿真结果39-42
• 3.4.1 均匀数据源39-40
• 3.4.2 突发数据源40-42
• 3.4.3 热点数据源42
• 3.5 本章小结42-44
• 第4章 分布式迭代调度算法研究44-61
• 4.1 现存分布式调度算法45-47
• 4.2 请求预测机制RP47-53
• 4.2.1 RP基本思想47-48
• 4.2.2 RP的具体实现48-49
• 4.2.3 RP应用于RR/LQF49-50
• 4.2.4 RP应用于HRF/RC50-52
• 4.2.5 RP应用于其他的调度算法52-53
• 4.3 仿真结果53-56
• 4.3.1 均匀数据源53
• 4.3.2 突发数据源53-55
• 4.3.3 热点数据源55-56
• 4.4 理论分析56-60
• 4.4.1 均匀数据源57-58
• 4.4.2 热点数据源58-59
• 4.4.3 理论分析结果与仿真结果对比59-60
• 4.5 本章小结60-61
• 第5章 总结与展望61-64
• 参考文献64-67
• 个人简历、在学期间的研究成果及发表的论文67

【相似文献】

中国期刊全文数据库 前10条

1 向哲,钟玉琢,冼伟铨;一种基于周期合并策略的流调度算法[J];软件学报;2001年08期

2 伊鹏,张兴明,郭云飞;基于输入排队的调度算法[J];计算机工程;2003年19期

3 易云山,桂志波;分组网络中包调度算法研究[J];江苏通信技术;2004年03期

4 任艳颖,张文军,王彬;无线调度算法[J];计算机工程;2004年15期

5 刘越洋,席裕庚;基于两步滚动的单机调度算法研究[J];计算机工程;2004年24期

6 杨梅樾;马祥杰;;输入排队中调度算法的研究[J];信息工程大学学报;2006年02期

7 曾东海;刘海;金士尧;;集群负载调度算法性能评价[J];计算机工程;2006年11期

8 孙力娟;李超;张登银;王汝传;;低速网络中实时补偿型差额循环调度算法的设计和实现[J];电子与信息学报;2006年10期

9 刘东;张春元;;软件容错模型中反向与正向调度算法研究[J];计算机工程与科学;2007年09期

10 何琨;赵勇;黄文奇;;基于任务复制的分簇与调度算法[J];计算机学报;2008年05期

中国重要会议论文全文数据库 前10条

1 彭洪;涂凍生;;面向操作的调度算法[A];1994中国控制与决策学术年会论文集[C];1994年

2 罗豪杰;许都;;IEEE 802.16 MAC层上行调度算法[A];四川省通信学会2007年学术年会论文集[C];2007年

3 张遵福;李乐民;;支持QoS的调度算法设计[A];2006中国西部青年通信学术会议论文集[C];2006年

4 姚建波;竺小松;李晶晶;;非对称通信环境中两种广播调度算法的分析与比较[A];中国通信学会第六届学术年会论文集（上）[C];2009年

5 景维鹏;吴智博;刘宏伟;董剑;;一种支持任务依赖关系容错调度算法[A];第十四届全国容错计算学术会议(CFTC'2011)论文集[C];2011年

6 李琪林;甄威;周明天;;一种适用于Master-Worker应用的动态统一调度算法的研究[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

7 吕锋;涂晓东;;高性能交换结构调度算法的研究[A];四川省通信学会2006年学术年会论文集（二）[C];2006年

8 赵尔敦;肖静;;无线网络中基于信道状态预测的调度算法[A];2006全国复杂网络学术会议论文集[C];2006年

9 殷洁;;城市光网光纤自动调度算法研究和应用[A];中国通信学会信息通信网络技术委员会2011年年会论文集（下册）[C];2011年

10 陈平;王柏;徐六通;吴斌;王艳辉;;电信社群网络中介度的网格并行算法及调度算法[A];2006年全国通信软件学术会议论文集[C];2006年

中国重要报纸全文数据库 前1条

1 张建辉 吴松;TD—SCDMA积跬步 HSDPA以致千里[N];通信产业报;2005年

中国博士学位论文全文数据库 前10条

1 刘晓锋;可扩展多级多平面交换网络及调度算法研究[D];电子科技大学;2015年

2 沈文枫;CPU-GPU异构高性能计算中的负载预测调度算法研究及应用[D];上海大学;2016年

3 马丹;任务间相互依赖的并行作业调度算法研究[D];华中科技大学;2007年

4 田冲;无线网络跨层调度算法研究[D];山东大学;2009年

5 黄平;分布式交换系统队列结构及调度算法研究[D];华中科技大学;2006年

6 刘惠;嵌入式系统节能调度算法研究[D];西安电子科技大学;2011年

7 赵明宇;集群系统的调度算法研究[D];哈尔滨工业大学;2007年

8 吴刚;对低功耗进程调度算法的研究[D];复旦大学;2006年

9 牛进平;3G长期演进系统中调度算法和干扰抑制技术研究[D];西安电子科技大学;2014年

10 罗威;分布式实时容错调度算法研究[D];华中科技大学;2008年

中国硕士学位论文全文数据库 前10条

1 丁雪飞;纯电动车整车CAN网络实时调度算法的研究[D];辽宁大学;2015年

2 王德龙;Hadoop平台下作业调度算法的研究与改进[D];南京信息工程大学;2015年

3 袁林伟;载波聚合资源分配及调度算法研究[D];西南交通大学;2015年

4 景木均;3GPP LTE系统中基于多目标决策的下行资源调度算法研究与实现[D];西南交通大学;2015年

5 刘盼红;大数据环境下Hadoop作业调度算法的研究[D];河北工程大学;2015年

6 杨轩;高铁无线通信VoIP业务与多业务共存的资源调度算法[D];西南交通大学;2015年

7 陈传庆;基于衰落信道的无线链路调度算法研究[D];曲阜师范大学;2015年

8 陈文龙;Hadoop平台下作业调度方法研究[D];南京理工大学;2015年

9 陈瑜;针对Hadoop集群的节能调度算法研究[D];电子科技大学;2015年

10 朱新新;网络端到端流量的QoS优化技术研究[D];电子科技大学;2014年

，

本文编号：743367