高性能大容量多级交换结构与调度算法研究

摘要

随着因特网(Internet)应用的日益广泛，音视数据逐渐成为网络应用数据的主体，对等(P2P)关系也因此成为继浏览器朋艮务器(B/S)模式之后的新型应用模式。加上网络应用的种类和数量不断增加，网络用户数呈指数规律剧增，网络应用数据量有多个数量级的增长。网络应用环境的上述变化，加上安全问题日益恶化，对通信子网(特别是骨干通信子网)及其核心设备提出严峻挑战。人们期待未来的通信子网更加安全可靠、易管理，可用性高，能够根据用户需求和服务性质提供不同质量的数据传输服务；要求骨干通信子网的核心交换设备具有更大容量(端口数与单口速率的乘积)、更优的交换性能(转发速率、传输时延、抖动等)。
　　以密集波分复用为代表的光通信技术，将单个波长的数据传输速率提高到160Gbps以上，为构建高速率的交换机提供了良好的通信条件。但是，由于缺少可用的光存储器件和光处理器，在全光域内实现分组交换尚不现实，现代的交换机的交换结构的构建还只能在电域内实现，或采用光电相结合的方式。然而电子器件的毫微秒级的门传输时延和存储器访问时间的制约，以及印制板工艺等方面的原因，构建单波长100Gbps速率和多端口的大容量高性能的交换机仍然是交换机设计中的难题。2010年发布IEEE802.3ba标准就因为受电器件的限制，不得不采用10个10 Gbps的波长合成100Gbps的端口速率，而未能直接利用光纤100 Gbps的波长速率。因此，高光纤通信速率与电域内相对较长门传输时延及存储器访问时间之间的反差正是构建大容量、高性能的交换结构(Switch fabric)的难点，也正是本论文研究工作的大背景。
　　多年以来，网络中继设备(路由器、交换机)的核心部件--“交换结构”经历了总线结构、共享存储器结构和交叉连接(Crossbar)三大阶段。尽管Crossbar仍然是当今交换机使用的核心交换结构，但由于受电子技术和工艺水平的限制，“单级crossbar交换”在交换速率和端口数量方面已经达到现有技术的极限，难以适应现代和未来交换机对容量和性能的需要，于是出现了多级crossbar交换结构。典型的多级交换结构包括“负载均衡交换结构”(LB switch fabric)和“Clos网络互联结构”两种，也正是本文研究的主题。
　　LB交换结构利用多个交换单元(交叉开关或阵列波导光栅)组成多级交换机以改进其性能，单个交换单元的调度采用简单但严格的时分复用调度，即可获得100％的吞吐率。其代价是总交换的时延增加，还可能出现信元(Cell)错序的问题。作者在本论文中对LB交换结构的贡献主要两方面：1)提出了增强型LB交换结构以解决其时延大的问题，即用适应性时分复用(ATDM)取代严格的TDM调度，避免时槽利用不充分问题(称为“连接浪费”)；2)提出用虚拟中间级队列(VCQ)和虚拟输入队列集(VIQ set)相结合的方式，保证交换信元不失序，首次将整个交换机的调度时间复杂度降低为O(1)，并且保证了100％的吞吐率和良好的时延性能。作者还分别探讨了用交叉开关电子器件和阵列波导光栅光器件作为基本交换单元的可行性和利弊。
　　对LB交换结构的严重的批评是：为了改进交换机的性能或扩容，与另一类多级交换结构(Clos)相比，它使用的基本交换单元过多。论文中作者对Clos结构的研究包括三个方面：
　　首先，本文提出了一种在无缓存的Clos网络结构中实现100％吞吐率的调度算法StablePlus。利用StablePlus的特点，作者将Clos网络中的Karol路径分配的算法的复杂度降低为O(1)，可以方便地利用笔者设计的专用硬件来实现。StablePlus是首个在O(1)的调度复杂度下，使Clos网络交换机达到100％吞吐率和良好时延性能的调度算法。通过对StablePlus执行过程和执行顺序的进一步优化，交换机整体的调度时间大大缩短，尽管StablePlus能够在较大范围内适应较大容量和高性能交换的需要，但是受无缓存Clos网络结构的局限性的影响，进一步扩大超大容量交换受到制约，需要探索新的技术。本文的其余部分将聚焦于带存储的Clos网络结构。
　　作者对于带缓存的Clos网络交换机的贡献主要在于提出了创新的“模块级匹配”的概念。作者首先将这个概念应用于MSM(Memory-Space-Memroy)的Clos网络交换机之中，它将传统“端口级匹配”的调度方式转变为“模块级匹配”的调度，这个转变带来的优势有：减少了调度器需要处理的请求和相应的数量，并且避免了在Clos网络中复杂的路径分配问题。因此，这样的一个调度器可以在单个电路板、甚至是单个芯片当中实现，这对于实现大容量交换机是非常必要的，而这个优势在无缓存的交换机当中是无法实现的。使用“模块级匹配”所带来的另外一大好处在于可以避免信元错序的问题。因为每次都有一个帧的信元同时穿过Clos网络的所有中间级。此外，在MSM的Clos网络交换机中应用“模块级匹配”可以应用大量文献中成熟的单级输入排队交换机的调度算法，并且如果选择稳定的调度算法，Clos网络便可达到100％的吞吐率。为了弥补基于帧的调度所带来的较长的等待成帧时间的问题，作者提出了静态信元分发和动态信元分发两种各有特点的解决方案，并通过仿真实验验证了他们的有效性。
　　然后，作者尝试将“模块级匹配”的概念应用到三级带缓存(MMM，Memory-Memory-Memory)的Clos网络结构中，获得了很好的效果。MMM的Clos网络可以完全模拟一个单级CICQ(Combined Input and Crosspoint Queued)交换机。因此所有CICQ交换机的优点都可以被继承，例如其仅使用简单调度即可达到的高性能以及仅需要较小的缓存即可达到很高的吞吐率。并且文献中关于CICQ交换机的大量的成熟调度算法都可以直接应用到Clos网络中。作者试图在Clos网络中应用CICQ交换机中的经典算法SQUISH，并达到了100％的吞吐率。更加重要的是，使用SQUISH的Clos网络表现出了极强的抗突发性，在极大的突发流量下，仍然可以达到95％以上的吞吐率。而在低负载下，和MSM的模块级匹配交换机类似，可以使用静态或者动态信元分发的方法弥补以帧为单位调度的不足。
　　最终，对于所有有缓存的多级交换机都会遇到的拥塞控制的问题，本论文提出了一种在输入模块中限制信元数，而在输出模块的队列中设置拥塞阈值的方法，有效地解决了MSM和MMM两种Clos网络在所集成的存储器有限的情况下，因队列拥塞而产生的溢出和队首阻塞问题。