可扩展多级多平面交换网络及调度算法研究

发布时间：2018-05-01 00:27

本文选题：路由算法 + 可扩展性　；参考：《电子科技大学》2015年博士论文

【摘要】：随着Internet的快速发展,数据流量与网络应用呈爆炸式增长,传输系统的传输速率随着DWDM技术的成熟提高很快,而交换技术(包括交换结构及调度算法)发展却相对滞后,日渐成为通信网络的性能瓶颈。单级结构(crossbar)在核心路由器/交换机中占有非常重要的位置,其研究成果十分丰富,对交换结构的发展起到了举足轻重的推动作用,但它的不足在如今的网络环境中也是致命的。由于单级结构先天缺乏可扩展性,因其实现成本随交换容量N呈平方增长,很难在有限的芯片上实现大容量交换系统。Log2N网络与Clos网络是两种完全不同的多级结构,无论是拓扑结构还是路由属性都有很大的区别,但有一点却是相同的,那就是它们都具有良好的可扩展性,很容易构建高速、大容量交换结构。本论文以多级多平面交换结构(包括log2N,Multi-log2N,Clos,Multi-Clos)为研究重点,主要的研究内容及研究成果包括以下几个方面:分析研究了单级结构(crossbar)及相应的调度算法因可扩展性原因,单级结构无法适应信息容量急剧膨胀和网络应用复杂多样的实际需求,但它是其它可扩展交换结构的基础,无论从拓扑结构,还是从调度算法都如此。因此,我们首先分析研究了单级结构及相应的调度算法,主要分析讨论各种形式的单级结构及各自的优缺点,包括OQ,IQ和CIOQ等。其次,分析研究了针对单级结构的经典的调度算法,如PIM算法,iSLIP算法等。分析研究了多级结构Log2N,Multi-log2N及调度算法就拓扑结构而言,log2N网络的相邻级采用部分连接,这导致log2N网络的路由路径唯一性。路径唯一性产生两个方面的结果:自选路由和内部阻塞。自选路由简化了路由控制,而内部阻塞却影响了交换性能。为了解决内部阻塞,通过将多个log2N网络构建Multi-log2N结构来破坏路径唯一性。由于HC型(水平级连)的Multi-log2N增加了网络直径,不利于光交换,因此我们在论文中重点研究VS(垂直堆叠)型Multi-log2N结构。为了实现真正的无阻塞路由,本论文提出了基于冲突链路集的控制算法(CA-CLS)。CA-CLS算法解决了内部阻塞的问题,但未解决SE的共享问题,以至于在光交换过程产生光串扰,严重影响交换性能,于是又提出基于置换多重分解的控制算法(CA-MDP),并详细分析了CA-MDP算法性能及解决光串扰问题的有效性。分析研究Clos,Multi-Clos结构及调度算法Clos网络的相邻级采用完全互连模式,因此Clos是多路径网络,任意输入-输出之间都存在多条路由路径,因此路由控制较log2N复杂,当然可通过适当的网络配置来实现严格无阻塞,可重排无阻塞等的无阻塞结构。Clos网络中输入-输出之间的路径条数是由中间级(CS)的交换模块(CM)数来决定的,即Clos网络中路径的选择(或分配)问题可等价地转化为CM的分配问题,于是本文提出基于矩阵分解的并行路由控制算法(PRD-MD)。PRD-MD算法不同于已有的矩阵分解算法,它采用了逐行分解,不仅实现路径的选择,而且解决了其它同类算法的不完全性,能彻底分解满足条件的任意业务矩阵。另外,针对CRRD算法存在的不足,本论文提出了主动授权的CRRD算法(CRRD-AG)。CRRD-AG不仅能有效降低额外的仲裁信息量,而且充分利用CS级的链路带宽,可提高吞吐率。Multi-Clos结构具有很强的可扩展性,很容易通过添加平面来实现大容量交换系统。我们在TrueWay的基础上也提出了关于Multi-Clos的一些基本思路,目前虽无成熟的研究成果,但将是我们后续的研究目标。
[Abstract]:With the rapid development of Internet , data traffic and network application are exploding , the transmission rate of transmission system increases rapidly with the maturity of DWDM technology , and the switching technology ( including switching fabric and scheduling algorithm ) is very important . In this paper , we propose a control algorithm ( CA - MDP ) based on permutation multiple decomposition , and analyze the performance of the CA - MDP algorithm and the effectiveness of solving the problem of optical crosstalk . The path number between the input - output in the Clos network is determined by the number of switching modules ( CM ) of the intermediate stage ( CS ) .

【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP393.01

【参考文献】