高性能三级Clos交换网络结构及调度算法研究

《高性能三级Clos交换网络结构及调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、高性能三级Clos交换网络结构及调度算法研究张茂森西安电子科技大高性能三级Clos交换网络结构及学调度算法研究作者姓名张茂森导师姓名、职称邱智亮教授2014一级学科信息与通信工程二级学科通信与信息系统年9月申请学位类别工学博士提交学位论文日期2014年9月学校代码10701学号1008110084分类TN82号TN919密级公开西安电子科技大学博士学位论文高性能三级Clos交换网络结构及调度算法研究作者姓名：张茂森一级学科：信息与通信工程二级学科：通信与信息系统学位类别：工学博士指导教师姓名、职称：邱智亮教授提交日期：2014年9月StudyofStructuresandDispatchi

2、ngSchemesforHighPerformanceThree-StageClosSwitchingFabricsAdissertationsubmittedtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofDoctorofPhilosophyByZhangMaosen(InformationandCommunicationEngineering)Supervisor:Prof.QiuZhiliangSeptember2014西安电子科技大学学位论文独创性(或创新性)声明秉承学校严谨的学风和优良的科学

3、道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文若有不实之处，本人承担一切法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。学校有权保留送交论文的复印件，允许查阅

4、、借阅论文；学校可以公布论文的全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，获得学位后结合学位论文研究成果撰写的文章，署名单位为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要以分组交换为基础的Internet已经成为通信网络的重要组成部分。随着光纤通信技术以及光传送网络的快速发展，Internet中现有路由器、交换机等网络设备的容量及可扩展性已无法满足要求。另一方面，分组交换逐渐被用于在卫星通信中替代传统的弯管式转发、以及承载电路交换中的实时话音等其它业务，这对网络设备的硬件复杂度、吞吐率、时延及时延抖动等方面提出

5、了新的要求。以crossbar为代表的单级交换网络由于在容量、扩展性等方面受到限制，无法用于构建大容量交换网络。Clos交换网络使用小规模交换芯片互联组成，具有模块化、可扩展、无内部阻塞等优点，是下一代大容量路由器和交换机的主要解决方案。本文在三级Clos交换网络的基础上针对上述需求进行了研究，论文主要工作和取得的创新性成果如下：1.针对memory-space-memory(MSM)型三级Clos交换网络在不均衡业务输入时吞吐率下降的问题，提出了在多种业务模型下都具有较高吞吐率的分治调度算法。该算法首先把输入级的队列划分为若干个冲突域，分别对应于每个输出级模块，则MSM型Clos交换网络

6、中的调度问题就可以被分解为不同冲突域内的信元选择问题；然后采用串行匹配的策略，限制了冲突发生的范围，达到了较高的吞吐率，同时减少了仲裁器和级间连线的数目，简化了交换网络的硬件设计。仿真表明，该算法可以在多种业务输入时均达到较高的的吞吐率，并具有较低的平均时延；2.针对MSM型三级Clos交换网络中调度算法执行时间较长的问题，提出了一种基于流水线操作的逆向调度算法，以及一种可以降低计算复杂度的LGMSM(Line-GroupingMSM)交换结构。与传统调度算法按模块排列顺序执行匹配操作不同，逆向调度算法首先按固定的轮转顺序将信元请求发送到各中间级模块并分别进行内部匹配，然后将中间级的匹配结

7、果返回给输入级，用于指导后续信元的转发。调度过程中信元请求的发送不依赖于前一次匹配的结果，从而实现了整个调度过程的流水线操作，同时将三级Clos交换网络的调度问题简化为了单级crossbar结构的匹配问题。理论分析证明，逆向调度算法在不增加硬件开销的前提下，有效地减少了完成一次调度所需要的时间。LGMSM结构通过将连接两个交换单元的一条链路扩展为多条并行链路，在交换规模相同的情况下有效减少了交换网络中仲裁器的数目以及每个