《大容量交换机多级交换结构及其调度算法的研究和设计.docx》由会员分享，可在线阅读，更多相关《大容量交换机多级交换结构及其调度算法的研究和设计.docx（54页珍藏版）》请在金锄头文库上搜索。
1、随着因特网和宽带通信技术的高速发展，因特网的信息流量和设备的数量以惊人 的速度增长，同时传输技术的长足发展使得传输容量大幅度提高。交换机和路由器 是架构因特网的主要互连设-备，因而对交换机和路由器提出了更高的要求。高速、 高性能的交换机和路由器是实现高速骨干网并决定其性能的关键所在。本文首先介绍了三级Clos网络的应用以及无阻塞条件，在此基础上提出了基于 三级Clos网络大容量分组交换机的体系结构，并且分析了交换机的数据流程，输入 控制器和输出控制器的帧处理，以及集中调度器的功能结构。本文详细讨论了集中调度器的逻辑结构以及分组调度策略的设计。集中调度器在 交换机设计中处于中心位置，是整个交换机
2、协调工作的关键。本文提出了一种基于 帧的双重匹配调度策略，该策略分为模块级匹配和端口级匹配两部分，采用启发式 并行匹配算法进行路由，采用本文根据iSLIP输入排队调度算法提出的E-iSLIP算法 进行调度。E-iSLIP算法采用竭力服务策略和优先级概念，可以改善算法在突发流量 下的性能。在这些设计思想的指导下，本文对E-iSLIP算法进行了性能仿真，仿真结 果表明，与iSLIP算法相比，E-iSLIP算法在突发流量下的性能有明显改善，在均匀 流量下是稳定的，而且采用了优先级的E-iSLIP算法比未采用优先级之前具有更好的 公平性。关键词：交换机，Clos网络，调度，iSLIP,突发流量2多级交
3、换机系统结构设计2.1前言交换结构的选取对路由器的性能有很大的影响，由于多级交换结构良好的扩展性， 目前的大容量路由器和交换机多采用基于多级交换网络的交换结构，例如Bayern, Benes, Clos网络等都在交换结构设计中发挥了重要作用。本章提出用三级Clos网络构造大容量交换机的方案，首先提出了基于三级Clos 网络的多级交换机体系结构，然后分别分析了交换机的数据包流程，信元和帧的数据 格式，输入控制模块和输出控制模块中的帧处理过程，以及集中调度器的逻辑结构。2.2多级交换机体系结构网络交换背景三级Clos网络牌是采用基本交换单元来搭建大型交换结构的最常用的拓扑。Clos 网络可以用来有
4、效实现低延退，高带宽，面向连接的ATM交换。Clos类型的交换结 构还有经济和技术上的吸引力。根据他们的内在容错和多径路由的特性，是提供可靠 的宽带交换的非常有吸引力的一个选择。三级Clos网络由于其模块化和可扩展性被广泛用于商用多处理器互连网络和交换 阵列。例如IBM GF-11并行系统Memphis交换机，NEC的ATOM, Hitachi的超级 分布式交换系统OPTIMA,和TORUS电光混合T比特交换机-ATMOS光交换机, Lucent的Atlanta套片，Myrinet的Myrinet-2000系列光纤通道交换机等等。分组交换三级Clos网络目前流行两种结构，SSS(Space-S
5、pace-Space,S3)结构采用 无缓存的空分交换单元实现。MSM(Memory-Space-Memory)结构采用第一级和第三级 为共享缓存单元，第二级为无缓存空分交换单元实现。我们提出的是采用SSS结构的 Clos网络。欲将任意一个输入单元的输入端连向任意一个输出单元的的输出端时，有的多级 互连网络会产生阻塞，有的则不会产生阻塞。对于产生阻塞的多级互连网络，有的可 以通过重新调整现有的连接而避免之，有的则不能。多级互连网络处于阻塞状态是指 对于存在空闲的输入级输入端点和输出级输出端点时，多级互连网络找不到一条空闲 的链路将它们连接起来。根据阻塞情况的不同可以将Clos型多级互连网络细分
6、为以下三种：(1) 严格无阻塞Clos型多级互连网络是指多级互连网络不管处于什么状态，对于任意 的空闲输入级输入端点和输出级输出端点，总存在空闲的链路将它们连接起来。而不 需调整多级互连网络中己建立起来的连接。(2) 广义无阻塞Clos型多级互连网络是指多级互连网络中存在发生阻塞的可能性，但 是可以通过路由控制算法避免阻塞的发生，且不必重新调整多级互连网络中己建立起 来的连接。(3) 可重排无阻塞Clos型多级互连网络是指多级互连网络发生阻塞时，通过路由控制 算法重新调整现有的连接，从而在输入级输入端和输出级输出端之间，找到一条空闲 的链路建立起连接。对于以上三种不同类型的Clos多级互连网络
7、，其体系结构是不同的。在此给出三 级Clos型互连网络在各种情况下的无阻塞的条件： 对三级Clos网络C(m,n,k),如果m 8 1,则此网络是严格无阻塞的，即只要一 条连接的起点和终点是空闲的，任意时刻都可以在交换结构中建立这条连接而不 影响网络中己经建立的连接。(2) 如果ms3n/2 ,则此多级互连网络是广义无阻塞的。(3) 如果槌，则此网络是可重排无阻塞的，即只要一条连接的起点和终点是空闲的, 任意时刻都可以在交换结构中直接或对己有的连接重选路由来建立这条连接。以上是适用于电路交换的三级Clos网络的无阻塞条件。对于分组交换结构，如果 将每个内部信元视为一个呼叫，以信元为单位进行路由
8、选择。在信元到达之前建立通 路，在信元过去后释放该连接，则上述结论也适用于分组交换的三级Clos网络。由以上的条件可以看出，如果中间级交换单元的数量越少，则多级互连网络产生 阻塞的可能性就越大，因此，就越要求优良的路由控制算法来实现无阻塞的连接。对 于多级互连网络而言，我们总希望使用最少的交换单元来实现连接。这样可以降低成 本。由于在输入、输出交换单元数，和输入交换单元的输入端口、输出交换单元的输 出端口数在相对固定的情况下。唯有减少中间交换单元数来降低成本。这就意味着必 须提高路由控制算法的复杂度来避免发生阻塞。从以上的三种阻塞情况来看，可重排无阻塞多级互连网络所需要的中间级交换单 元数最少
9、，所以我们以下将研究基于三级可重排无阻塞Clos型互连网络的交换机体系 结构。多级交换机系统结构PS：集中调度器LC：线卡IPC：输入控制器PS：集中调度器LC：线卡IPC：输入控制器OPC：输出控制器VOQ：虚拟输出队列FIFO：先入先出队列FD：解帧模块FA：组帧模块IM：输入单元CM：中间单元0M：输出单元Switch Fabric：交换结构图2.1多级交换机系统结构如图2.1所示是多级交换机的系统结构119.22b基本模块包括线卡(linecard),输 入端口控制器(IPC, input port controller),输出端口控制器(OPC, output port contro
10、ller),交换结构(switch fabric),集中调度器(PS, centralized packet scheduler), 系统时钟分配单元(system clock distribution unit) 0交换结构是三级Clos网络结构， 由输入交换单元(IM, input switch module)，中间交换单元(CM, central switch module)， 输出交换单元(OM, output switch module)组成，每个交换单元都是crossbar交换芯 片。我们假设交换网络规模为128-128(128个输入端，128个输出端)，交换单元为 16-16的交
11、换芯片，则根据可重排无阻塞条件，IM, CM, 0M的数目分别为8, 8,8,若输入和输出端口线速为IGb/s,则可以达到128Gb/s的交换容量。所有的输入数 据包都在线卡中分解成等长的信元，存在线卡缓存中。所有的信元都在IPC和OPC 中缓存，中间的交换结构是无缓存的。IPC上的虚拟输出队列(VOQ, virtual output queue) 和集中调度器为交换机提供冲突解决。在输入端，输入数据包缓存在线卡中，然后被 分割成信元并且根据目的端口存入相应的VOQ中，相同目的端口的信元存在同一个 VOQ。IPC上的VOQ作为线卡上VOQ缓存结构的“镜像”，只要能保持信元在线卡 和IPC之间的
12、流动，IPC上的VOQ相比线卡上对应的“镜像”VOQ就可以小得多。 在信元发送给目的端口线卡之前，OPC中的缓存用来存储这些信元。在输出端口线卡 中有虚拟输入队列(VIQ, virtual input queue)用来缓存从交换结构传来的信元，把它 们重组成数据包。图2.2表示了数据是如何流经系统的。在输入端口线卡中，不定长的数据包被分割成定长为64B的信元(包括信元头开销)，然后把信元从线卡发给IPC,在IPC中, 每一个VOQ都采用并行缓存结构，使得每次同时可以读取r个信元。这r个信元在 IPC里面的组帧模块中组成一帧。当线卡端口速率为IGb/s时，一个信元时隙为T = 512ns,假设r
13、=8,则每一帧的周期为f = r T = 4096nso在交换网络的每一级，相应的 帧头被提取出来进行处理，控制交换单元。由于集中调度器已经解决了竞争冲突，在 交换网络的每一级，通过选择交换单元相应的输出链路，数据帧可以找到一条合适的 路径通过交换网络。当帧到达目标OPC后，通过OPC解帧模块，帧被分解成相应的 r个信元，然后OPC把信元发给线卡。载荷入端口出端口 图2.3数据结构图图2.3描述了在交换每一级的数据结构。每一个输入信元的载荷前面都包含两个 头部域，OL表示信元的输出端口号，IL表示信元的输入端口号。信元头部的有效位 表示信元是否有效。如果是NN的三级Clos交换网络C(m,n,
14、k),则信元头部长度为 l+logzN+logzN bits, N=128,则信元头部大小为15bils。帧的头部域包含CM号，0M 号，输出端口号,有效位四部分,帧的头部长度为l+log2k+log2m+log2n bits,因为 m=n=k=8,所以帧的头部长度为1 Obitso有效位表示帧是否包含有效信元。图2.4描 述了信元如何经过IPCo数据包A来自输入端口 1,要到目的端口 1。在到达IPC之 前，A已经被分割成定长的信元，存在相应的线卡中。在这个例子里，A被分解成16 个信元(Ao到A.5),所有的信元都以轮转方式存在r(r=8)个帧缓存中。图2.4 IPC中的帧处理信元到达IP
15、C中的帧缓存，立即发送请求信号给集中调度器。若是128-128的交 换规模，则每个IPC在每个时隙发送给集中调度器的信息为2log2128= 14bils。设集 中调度器与IPC的通信总线位宽为20bits,频率62.5MHZ,则发送14bits信息大约需 要15ns,发送128个端口的请求信息约需要3个信元周期T。调度器返回给IPC组帧 模块的帧头信息为lObits,通过总线传送约需要15ns,发送给128个端口同样需要3 个信元周期T,因为我们的调度方式是基于帧调度，每一帧有8个信元，所以总共留 给调度器的调度时间为2个T,即1024nso集中调度器采用基于帧的双重匹配策略进 行调度，再把
16、允许信号返回给允许发送的IPC, Ao到A7组成第一帧，As到Ai5组成 第二帧。图2.5描述了数据帧如何在OPC中进行处理以及在线卡中如何将信元重组成 数据包。帧首先在解帧模块被拆成信元，然后根据信元头，在第一个帧周期，Ao到A7进入OPC缓存中的8个FIFOs,在第二个帧周期，As到Ai5进入相同的8个FIFOs然后将这些信元从FIFO中读到线卡。线卡中的VIQ将信元重组成数据包Ao选择器F2 FlOPCI图2.5 OPC中的帧处理为了保持时钟同步，一个系统帧时钟将提供给系统的各个模块。每一个交换动作， 包括读写缓存，拆组数据帧，都要根据相同的帧时钟信号同步。还有一个基准时钟用 来进行比特同步，该时钟频率1GHZ。集中调度器的结构如图2.6所示，它由k个SIMs和k个SOMs组成，每一个对应 于三级Clos网络相应的IM和OM。每一个SIM都有n个
