多级交换网络如何控制
摘要：路由器（交换机）的内部交换网络作为网络结点的核心部件，是目前高性能宽带信息网络研究的热点之一。采用多级交换结构是构建大容量分组交换网络的常用途径。
关键词多级交换网络三级 CLos网络分布式调度交换机制
1引言
多级交换结构与单级交换结构的区别在于一个报文穿过整个交换网络所经历的选路次数。交换结构中，两个节点之间往往不会直接相连，在多级报文由源端口到达目的端口可能需要多次选路过程。所交换网络是路由器和交换机内部的核心部件。交换网络可以分为时分交换网络和空分交换网络。时分结构的基本特征是，所有的输入与输出端口分时共享单一的通信通路，具有时隙交换功能。空分结构的基本特征是，可以在多对输入端口与输出端口同时并行地传送信息，具有空间交换的功能，Clos网络与banyan网络属于典型的空分交换网络。
交换网络的成本与网络的交叉点数密切相关，而交叉点数是随着网络的入线和出线数快速增长的。多年来，研究构成交换网络的交叉点数随入线、出线数增长较慢的方法，一直是交换领域研究的重点课题，这些方法的基本思想是，采用多个较小规模的交换单元按照某种方式连接起来从而构成多级交换网络。Clos 网络就是其中的一种。路由器（交换机）的内部交换网络作为网络结点的核心部件，是目前高性能宽带信息网络研究的热点之一。采用多级交换结构是构建大容量分组交换网络的常用途径。直接连接网络和间接连接网络是空分多级交换网络的两种主要拓扑类型。直接连接网络虽然具有良好的可扩展性，但是网络性能难以控制，只是在大容量分组交换网络研究初期得到应用；间接连接网络是目前多级分组交换网络研究的重点。目前对多级间接连接网络（如三级Clos网络，并行分组交换和两级交换网络等）的研究是对单Crossbar交换网络研究的简单推广，从本质上说是一种集中式控制方式，这种方式会带来调度算法实现困难，交换网络性能难以控制和无法充分发挥多级交换网络拓扑优势等问题。
交换网络包括以下三个功能模块:
l)输入端口，从输入接口接收信元;
2)输出端口，向输出接口发送信元;
3)连接网络，提供所有输入端口和输出端口之间的可控的连通性。
2 三级Clos网络简介
Clos网络是由Charles Clos 在1953年提出，后来以他名字命名的。目前关于交换网络拓扑结构方面的研究主要集中在Clos网络、Benes网络和Banyan网络等上，其中，三级Clos网络由于其模块化性强和良好的可扩展性以及能够在交换网络内部实现严格无阻塞而在大容量路由器交换系统设计中受到了人们越来越多的青睐。
在Clos 网络中主要有三种无阻塞定义：严格无阻塞、广义无阻塞和重配置无阻塞，它们的定义如下：
◆严格无阻塞交换网络资源可保证在任何已建连接情况下都可以建立一对
空闲输入输出端口对间的连接。
◆广义无阻塞：交换网络采用适当的路由算法，不需要对网络已建连接进
行重新配置，就可以保证网络的无阻塞性。
◆重配置无阻塞：交换网络能够保证网络的无阻塞性，但是有可能需要对
现有的已建连接进行重新配置。
在面向连接网络应用背景下，Clos网络的研究取得了丰硕的成果，但是对分组交换Clos 网络的研究目前才刚刚起步。由于应用背景、衡量标准、研究重点等的不同（见表 2.1），使得许多在面向连接网络背景下Clos 网络的研究成果在分组交换Clos 网络中不再适用。从表 2.1 可以看出在分组交换Clos 网络的研究中，调度算法是研究的重点问题。
表 2.1 Clos 网络不同应用背景研究差异对比表
3三级Clos 网络分布式调度思想
用多级间接连接网络代替单Crossbar交换网络来实现高速、大容量交换网络，要充分发挥多级间接连接网络的优势，适应高速、大容量的应用环境，理想多级间接连接网络结构和调度算法应该符合以下原则：
（1）从多级交换网络的结构来看，交换网络应该用空分交换单元（Crossbar）来构架，Crossbar 应采用输入排队方式。缓存器接入速度的发展是网络设备发展的瓶颈，因此，在高速网络应用环境下，不适于采用共享缓存方式；在单Crossbar 交换单元中，输入排队方式是高速环境下应用的常用方式。
（2）调度算法不能要求组成交换网络的多个机架间需要进行大量的控制信息交换。
（3）调度算法要充分发挥多级交换网络的扩展能力，调度算法的复杂度不能随交换网络的端口数增加而急剧增加。用多级交换网络代替单Crossbar 交换网络就是为了克服当网络端口数很大时，交换网络的调度算法复杂度会急剧上升的问题。在多级交换网络中如果无法克服这个问题（如bl-Clos 网络中的 MAC 算法），那么就不能充分发挥多级交换网络的结构优势，使得调度算法的复杂度成为交换网络发展的瓶颈。
前面指出在大容量多级交换网络中需要以输入排队的单Crossbar交换单元为网络的基本构建单元。因此，如果交换网络的调度算法可以完全分布式，以Crossbar交换单元为基本调度单位，那么由于Crossbar 交换单元的端口数和整个交换网络相比要小得多；而且随着交换网络端口数的增加，Crossbar端口数不会随着增加，这样调度算法复杂度就不会上升，充分发挥了多级交换网络的优势。同时，由于在多级间接连接网络中级间连接关系是一定的，可以通过调度控制的就是单Crossbar 内部的连接，因此，从网络特性考虑以单Crossbar 交换单元为基本调度单位是可行的。交换单元的级间连接特性可以根据交换网络的拓扑特进行分析，进而采用不同的处理方式，这样就可以实现多级交换网络的分布式调度。
在分布式调度多级交换网络的分析中，主要考虑两方面的问题：（1）均衡级交换单元采用何种负载均衡算法可以保证调度级交换单元的良好性能。（2）保证网络算法性能良好最少需要的网络交换单元数，也就是需要的网络最低成本。在网络性能的研究中，由于单Crossbar 交换网络在业务是允许的条件下，有大量的调度算法可以保证良好的网络性能，因此，在本文研究中均衡级交换单元负载均衡的目标就是使到达调度级交换单元的业务是允许的。
4 具有信元保序能力的三级 Clos 网络分布式调度算法
三级Clos 网络分布式调度算法---LDVSA（Load Dispatched and V olleyed Scheduling Algorithm）算法分为三部分：输入级的负载分配算法，中间级解决输出单元竞争的调度算法以及输出级解决输出端口竞争的调度算法。LDVSA 结构如图4.1 所示.
图4.1 LDVSA算法示意图
在输入级采用输入排队，每个输入端口对到达各个OM的信元独自建立队列，每个队列又分为n个子队列，对应IM的n个输出端口（也就是网络的n个中间级）；中间级的RRnP 算法在一个时隙内对n个中间级采用同样的调度安排。调度算法首先按照轮询方式选择一个CM，然后根据该CM的排队情况进行计算得到本时隙的调度匹配。在每个CM 的一个输出端口只需要一个容量为N（N ＝n×r）个信元的缓存就可以将同一分组的各个信元以不乱序的方式送到OM级。原则上讲每个OM采用任何适用于单Crossbar，保证信元FIFO（First In First Out
