论文摘要
下一代核心路由器除了应具有极大的交换容量以外,还应具有灵活经济的可扩展性与极高的可靠性。作为路由器的核心部件,分组交换结构（Packet SwitchingFabrics,PSF）对路由器在上述各方面的表现具有决定性的作用。传统的分组交换结构技术由于受到crossbar规模、总线带宽、缓存读写速率以及集中仲裁调度方式等方面的限制,在实现极大交换容量与端口数量时面临着较大的技术难度,而且其可扩展性不理想。同时,集中仲裁调度方式所带来的单点失效（single pointfailure）问题降低了系统的可靠性。另一方面,在过去的二十年里,以torus网络为代表的直接网络技术被广泛应用于高性能计算系统中,主要作为处理器/存储器之间的连接。torus网络具有大容量、易扩展、高可靠性等优点,正好满足下一代核心路由器对分组交换结构技术的要求。然而作为分组交换结构的torus网络（Torus networks used as PSF,T-PSF）与高性能计算系统中的torus网络在网络规模、业务的特性、交换性能要求等方面都有着较大差异。如何有效地采用torus网络构建大容量可扩展分组交换结构仍然是一项充满挑战的、有待深入研究的课题。本论文致力于研究这一课题中的关键技术,主要研究内容包括:torus网络中的自适应路由算法,T-PSF的负载模式及其对网络性能的影响,针对恶性负载模式的解决方法,T-PSF的扩展方案。描述torus网络的特征与研究其性能需要用到一些基本概念。本论文的第二章集中介绍了这些概念,并给出了必要的数学定义与形式化表示方式。根据作者自己的理解,对一些概念之间的联系进行了说明。对已有文献（尤其是一些较早期的研究工作）中使用比较混乱、容易造成误解的术语进行了解释和澄清。本论文的第三章研究torus网络中的无死锁自适应路由算法。首先概述并比较了已有的两种解决死锁问题的策略:死锁避免与死锁恢复。然后提出了一种采用死锁避免策略的完全自适应路由算法的设计方案DALD（Deadlock-Avoidance withLocal Detection）。采用DALD方案所设计的路由算法只需要每个物理通道上具有两个虚通道（Virtual Channel,VC）即可实现无死锁（deadlock-free）,并且具有不错的性能。这是所有torus网络的路由算法中对缓存资源需求最少的,并且已经达到了缓存需求的事实上的最小极限。本章还提出了一种自适应路由算法的设计方案PDR（Path-Division Routing）,并且给出了采用该方案的路由算法的两种设计方法:分解法与合成法。然后详细描述了一种采用分解法所设计的路由算法ELadder。ELadder以增加虚通道为代价,在保持算法非常简单、易于实现的同时,能够达到不错的性能。torus网络的性能在很大程度上受其负载模式的影响。然而已有的负载模式模型是针对应用于高性能计算系统中的torus网络或传统分组交换结构所设计的,并不适用于T-PSF。本论文的第四章首先简述了已有最好的分组交换结构的负载模式模型——ZD（Zipf Distribution）模型。通过理论分析与仿真结果,阐明了ZD模型不适用于T-PSF的原因是因为它不包含关于分组的源、目的节点之间距离的信息。然后提出了两种适用于T-PSF的负载模式模型,分别采用不同的方法,把关于源、目的节点之间距离的信息与ZD模型结合起来。通过设置参数的值,可以控制模型中负载分布的均匀程度与源、目的节点之间的平均距离。这是业界首次提出的适用于T-PSF的负载模式模型。这两个模型都对网络的拓扑与节点总数不敏感,因而可以适用于不同拓扑与规模的网络。不少实际应用要求torus网络对于各种负载模式都能达到较高的吞吐量,包括所谓恶性负载模式（即可能造成负载不均衡的模式）。目前针对这一问题的最佳解决方法是采用全局自适应负载均衡路由算法。本论文的第五章提出了一种全局自适应负载均衡路由算法GALME（Globally Adaptive Load-balanced routing withMutual Exclusion）。GALME根据节点转发分组的历史信息来达到全局负载均衡,根据虚通道的当前状态来达到局部负载均衡。GALME还使用了基于“互斥性”的死锁避免方案,具有很强的路由自适应性,从而对于各种负载模式所能达到的吞吐量都超过了已有的最佳算法。T-PSF的负载模式与节点的具体位置无关,本章还针对这一特点,提出了一种适用于T-PSF的负载配置算法。通过把彼此之间有较大通信流量的节点配置到邻近位置,能够有效地减小分组源、目的节点之间的平均距离,从而提高网络性能。这是业界首次提出的针对T-PSF特点的恶性负载模式的解决方法。本论文的第六章研究T-PSF的扩展方案。首先总结了构建T-PSF时所应遵循的原则,然后提出了一种模块化的子网结构——可配置单板（Configurable Board,CB）。每个CB上集成有16个节点。通过逐渐增加CB的数量,并合理配置其板内、板间连接方式,可以方便地实现从4×4 torus到16×16×16 torus的扩展（即从16个节点到4096个节点的扩展）。通过合理选择各维节点数与板内、板间连接的带宽,可以保证在扩展过程中,T-PSF的交换容量始终大于其端口容量,从而保证T-PSF的性能不会随着扩展而下降。本论文的第七章介绍了使用OPNET Modeler系统与C++语言自行开发的torus网络软件仿真平台。该仿真平台可以支持从1维到4维的任意规模的torus/mesh拓扑、多种分组到达模型、多种负载模式模型、多种长度分布的变长分组、多种路由算法与调度算法,并且支持多优先级业务,支持组播/广播。在设计该仿真平台时重点考虑了其扩展能力,在该平台上可以较为方便地实现新的路由、调度算法与负载模式模型等。最后一章对全文进行了总结。