（通信与信息系统专业论文）多级多平面交换结构的交换机制研究.pdf

c i p 独创性声明 19166s7 i i r ljr l ji ii ii i i i ir lj piil y 1815 5 4 0 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：褪丛生 日期：月矿年门月刀日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盟亟垒 导师签名：= 回砧 2 7 i 二 j p ； i n l嗲洲 n 图2 1 交换结构参考模型 交换结构可以进行不同方法的分类，包括：时分与空分、阻塞特性、单级与 多级等等。其中时分和空分划分的是交换对象的处理领域，时分结构的基本特征 是所有输入输出端口共享同一信道，而对帧结构内时隙信息时序做出调整；空分 结构指多对输入输出端口间的信息交互可以并发进行，基本特征是分布式的存储 和输入、输出端口。 阻塞特性是指交换结构处理内部数据竞争( 数据链接对内部连接资源的争夺) 的能力，一般分为阻塞和无阻塞，无阻塞还可以具体分为严格无阻塞、重置无阻 塞等。严格无阻塞是交换结构中已有的通信链路建立情况上可以无障碍的添加新 的链路直至满负载，在这个过程中不需要对已有的链路做任何操作；重置无阻塞 是指在不采取任何操作的情况下无法达到严格无阻塞，但通过对已有业务重新分 配链路，可以不断添加任意业务直到满负载，又称为广义无阻塞；而阻塞结构则 是指使用任何操作都无法达到无阻塞增加新业务要求。单级与多级是指交换结构 的结构组成是单级还是多级，单级顾名思义就是指只有一级交换体系。多级结构 通常也称为多级互连网络( m i n ：m u l t i s t a g ei n t e r c o n n e e t i o nn e t w o r k ) ，由多个交换 4 第二章多级交换结构简介 单元( s e ：s w i t c h i n ge l e m e n t ) 组成若干交换级，再以一定的拓扑结构互连而成，s e 可以由单级交换结构来担当，也可以由小的m i n 来担当，即多级m i n 的嵌套【l 0 1 。 在实际应用中，这些分类并不是绝对的，通常情况下多种类型交叉混杂使用 以达更高的交换效能，比如在单纯的空分交换结构中引入缓存机构，则在一般的 空分交换能力上添加了时序调整能力，可以在同时实现避免竞争的机制，这一点 在后面将会又进一步介绍。以下对单级和多级交换交换结构做分别介绍。 2 2 单级交换结构 单级交换结构的特点是在每个输入端口和输出端口之间只有一条路径可达， 是早期交换系统中较常见的交换结构，它具有结构简单，组织灵活，实现方便等 优点。但在网络流量和容量急剧增长的今天，其容量小、扩展性差等缺点使其渐 渐不适合在核心交换系统中使用，但是在小型的交换机路由器中仍有使用。单级 交换结构可分为时分和空分两类，时分结构包括共享总线结构和共享缓存结构两 类，而空分结构最典型的就是单c r o s s b a r 结构。 1 共享总线交换结构 图2 - 2 共享总线交换结构 共享总线交换结构包括共享环和共享总线两种实现形式。输入出处端口使用 一条共享的线路交换数据分组，而处理器实现总线上的数据流控制。这种结构和 5 电子科技大学硕士学位论文 计算机系统内部的总线结构类似。图2 2 所示为共享总线交换结构模型。 最开始的以太网交换就是构建在这种共享总线的基础之上的。但是共享总线 结构所能提供的交换容量有限，一方面是因为共享总线会产生不可避免的内部冲 突：另一方面共享总线的负载效应使得高速总线的设计难度相对较大。假设总线的 带宽为b ，共有n 个输入输出端口，则每个输入输出端口的平均带宽上限为b n ， 显而易见这样的带宽是无法满足大规模交换系统要求的。随着用户对“独享带宽” 的渴求，这种共享总线的交换结构很快被共享缓存交换结构取代。 2 共享缓存交换结构 共享缓存是交换机中比较常用的一种结构。如图2 3 所示，在这种交换结构中， 所有的输入和输出端口共享一个存储器，所有需要经过交换机的数据都在共享的 存储器中存储转发。该结构的优点是各端口可以并发在存储器中进行读写操作， 缓存资源可以得到充分使用，较大提高交换效率，获得更佳的时延和吞吐率性能。 同时，共享存储结构还充分利用了静态存储器的优势，在内部流量较大时，尤其 是当针对某一目的端口的多个数据流发生冲突后，通过存储来缓冲无法发送的数 据流，这样就不再存在数据丢失，而且不会出现阻塞和冲突。 图2 3 共享存储交换结构 然而，共享缓存型交换结构的瓶颈在于其交换容量极大受限于存储器位宽、 读写速度。因为每个入线或出线可同时访问存储器，因此存储器的访问时间等于 w m r ( w 为双端口存储器的位宽，n 为端口数，v 为链路速率) 。所以它的缺点在于 整个交换结构的容量( 端口数及链路速率) 不可能太大，一般典型的情况是使用 1 6 1 6 的设计，它受到存储器访问速度的限制i l 。目前共享缓存的平均前向读取速 6 第二章多级交换结构简介 率最大可以达到数百g b p s ，这与t b p s 的要求还相差甚远，因而存储器的速率限制 成为这种交换结构的瓶颈。 3 c r o s s b a r 结构 c r o s s b a r 是一种空分无阻塞结构，是目前通信网络中使用较为广泛的一种交换 技术，通过配置交换矩阵，c r o s s b a r 能够使任何一个输入端和输出端相连，因此在 c r o s s b a r 内部不会出现阻塞，从而能够方便地进行数据交换。c r o s s b a r 型交换结构 通常采用高速交叉开关电路来实现，每个开关用来控制一个输入端口到一个输出 端口的通道。c r o s s b a r 可以采用输入、输出或者混合缓冲型交换结构，具有费用低、 可伸缩性强和交换无阻塞等特点，还可以根据不同的实现方式扩展到非常高的带 宽。 一直以来，被业界公认为是单级交换机中的最好结构。一个简单的c r o s s b a r 结 构由n * n 交叉矩阵构成，如图2 4 所示为一个4 * 4 的单c r o s s b a r ，具有4 4 = 1 5 个交叉 点( c r o s s p o i n 0 。 交叉点 入 端 口 2 3 4 c r o s s 状态 b a 状态 l23 4 出端口 图2 - 4c r o s s b a r 基本结构示意图 图2 _ 4 中c r o s s b a r 的每个交叉点是一个2 输入2 输出的传送门。传送门的2 个输入 称为横向输入与纵向输入，2 个输出称为横向输出与纵向输出。传送门的两个状态 称为c r o s s 状态和b a r 状态，也是c r o s s b a r 结构名称由来。如图2 - 4 右边所示，b a r 状态， 是指纵向输入连到横向输出，横向输入连到纵向输出。c r o s s 状态是指纵向输入连 7 电子科技大学硕士学位论文 到纵向输出，横向输入连到横向输出。交叉矩阵初始化时，交叉点均处于c r o s s 状 态。当数据开始传输时，由调度器控制交叉点按照信息头部的目的端口进行c r o s s 和b a r 的选择，从而完成入端到出端的交换。 当c r o s s b a r 交换结构不同输入端出现发往相同输出端口的数据时，就会产生输 出端口竞争现象。竞争中，只能有一个端口的数据竞争成功到达所要求的输出端 口，其它竞争失败的端口需使用缓存将数据存储排队，等待下一个时隙再次竞争。 缓存排队位置可以在交换单元的输入端，也可以在交换单元的输出端，还可以在 交换单元内部的交叉连接点处。一般选择输入排队( i q ) 和输出排队( o q ) 两种排队缓 存策略。 c r o s s b a r 结构是可以支持高带宽的无阻塞网络，支持高带宽的原因主要有两个： 1 线卡到交换结构的物理连接简化为点到点连接，这使得该连接可以高速运行。2 它的结构可以支持多个连接同时以最大速度传输数据，这一点极大的提高了整个 系统的吞吐率，只要调度器控制好交叉点的连接选择，多个输入输出端口间可以 同时传输信息。而只要一个出端口和入端口同时空闲，我们一定能找到一条路径 将它们相连，这样称为无阻塞，由此可见c r o s s b a r 结构是内部无阻塞的结构【l 2 。 c r o s s b a r 结构也有其难以避免的缺点，概括如下： ( 1 ) c r o s s b a r 结构的速度要取决于调度器的速度。调度器是c r o s s b a r 交换结构的核 心，它在每个调度时隙内收集各输入端口有关数据包队列的信息，经过一定的调 度算法得到输入端口和输出端口之间的一个匹配，提供输入端1 ：3 到输出端口的通 路，这需要设计性能良好、实现简单的调度算法。 r 2 ) c r o s s b a r 结构的复杂度随端口数n 的平方增长，t l p n 个输入端口的c r o s s b a r 结 构需要n 2 个中间交叉点。随着规模的扩大，其成本增长非常快，尤其是在输入输 出端加入缓存以后。所以大规模的交换系统很难采用这种结构。 2 3 多级交换结构 早期对电路话务网络的研究就致力于寻找一种无阻塞的多级交换系统，要求 这种系统使用比单级c r o s s b a r 交换结构少的交叉开关点来实现无阻塞性能。多级交 换结构多数情况下用来实现空分交换功能，由一系列的交换单元( s e ) 按一定的连接 规律组成，通过s e 间的连接实现全连通等特性，和c r o s s b a r - - 样可以对端口的数据 包进行并发操作，而且一方面增强了扩展性，可以在原先基础上扩建更大规模的 交换系统，另一方面和c r o s s b a r 相比使用较少的交换开关，具有更少的成本耗费。 8 第二章多级交换结构简介 目前，多级交换网络( m i n ) 被广泛使用在大规模的分组交换系统和a t m 交换结 构的设计中【1 3 】。其中使用比较多的几种典型多级结构有b a n y a n 网络及其相关改造 系统和c l o s 网络等等。 b a n y a n 网络是一种基于2 * 2 交叉开关的交换结构，结构相对比较简单，可以实 现自路由等性能，但由于依然是单路径结构，在解决阻塞问题上能力不够，因而 在此基础上发展了更多的改良结构，如b e n e s 、o m e g a 等，因为这些新结构基本上 都借鉴t b m y m 的连接方式，或者直接在b a n y a n 基础上进行级联或者嵌套生成的， 所以在后面统称为一类进行介绍。 2 3 ib a n y a n 交换结构及其变形 ( c ) ( d ) 图2 - 5b a n y a n 的基本形态和简单变形 b 锄y 粗交换网络最早由g o k e 和l i p o v s k i 提出【1 4 1 ，几种b 觚y 距网络如图2 5 所示。 其中图( c ) 为基本的b 锄y 觚网络，每对输入、输出端口之间只有一条路径可达，我 们称这种网络为单路径网络。图( a ) 和图( b ) 分别是一个o m e g a 网络( 又称为s h u m r e x c h a n g e l n 络) 和一个翻转o m e g a n 络，将( c ) 中阴影模块反转后就得到了( a ) 中的 9 电子科技大学硕士学位论文 o m e g a 网络。图( d ) 中的b a s e l i n e 网络则是b a n y a n 网络第一级端口做一定顺序变换得 来，可以发现，无论做如何的模块顺序变化，b 雒y a n 网络及其变形都是单路径网络。 b a n y a n 类网络的基本特性可以归纳为以下几点： 1 ) 当输入和输出级有n 个端口时，网络结构一定有n = l 0 9 2 n 级，且每级都有n 2 个节点，按照其连接规律可由小规模扩展成大规模。 2 ) 具有自组织路由的特点，当给地址编上特定的n 位2 进制代码后，从输入端到 来的数据分组可以按照此地址编码自行在中间各模块选择路径。图2 - 6 表示了一个 8 * 8b a n y a n 网络内部进行自组织路由的方法。经过对输出端口地址的特殊编码后， 只需在输入端口对数据分组标记上目的端口的地址码，就可以按照每位的数字自 行在各级交换单元选择路径，具体为每级单元对应的地址码为o 就选择上面的出 口，为1 选择下面的出口，图中两条粗线是两个数据分组的选路过程。 1 1 0 0 0 l 图2 - 6 b a n y a n 交换网络内自组织路由示意图 3 ) 由于使用简单的2 2 交换单元，整个结构比较容易用v l s i 实现。 b a n y a n 交换网络虽然能够实现全连通，并允许多个链路的同时通信。但因为 是单路径网络，每对输入输出端口之间只有一条路径。这样b a n y a n 交换结构内部阻 塞将不可避免，而且也很难实现多播和组播。图2 7 所示是一个8 * 8b a n y a n 网络内 部发生阻塞的情况。目的地址为0 1 0 和1 0 0 的两个分组需要在第二级和第三级间经 过同一路径，冲突就产生了。 1 0 咖姒 咖叭 姗埘 m 第二章多级交换结构简介 0 l l 0 1 0 内部冲突 图2 - 7b a n y a n 交换网络内部冲突不例 当内部拥塞产生以后，我们可以对内部通信连接排列做一些调整来避免拥塞， 但是不能从根本上解决拥塞问题。为了从根本结构上解决拥塞问题，b e n e s 网络被 设计了出来，如图2 8 所示，b c n e s 网络结构是由一个b a n y a n 网络和一个反扃 b a n y a n 网络首尾相连得到。可以看出，b e n e s 网络中任意两个输入输出端口之间都有两条 路径可达，减少了内部发生拥塞的可能性。 2 3 2c l o s 交换结构 图2 - 8 b e n e s 网络示例 c l o s 结构最早由c l o s 博士在1 9 5 3 年提出，后被广泛应用于t d m 网络【15 1 。近二 十年来，随着通信技术的发展，对大容量和优异扩展性的交换架构的需要，使得 c l o s 结构在分组交换系统中再次得到大量的应用，很多a t m 交换结构的设计也参照 咖咖 啪 啪m m 电子科技大学硕士学位论文 了d o s 结构的模型。除此之外，e l o s 网络结构还被广泛用于多处理器系统、高速计 算机网络等多个方面。 c l o s 交换网络单c r o s s b a r 相比，将硬件实现复杂度由n 2 减小为n 扔，实现大容量 交换系统时比单级c r o s s b a r 交换结构有更好的经济性，而且因为任意两个输入输出 端口间有多条通路，使系统有了更佳的容错性。此外，d o s 结构还具有信道阻塞率 低、输入输出信号延时短和扩容升级能力较好等优势。通过管道控制算法( p c a ： p i p e l i n e de o n l r o la l g o r i t h m ) ，可以快速方便地建立输入输出端口之间的同步和异步 通信链路。此外由于电路和光路交换的相似性，随着光互连网络技术的快速发展， e l o s 交换网络这种最初应用于电路交换的结构也在逐渐被引入光互连网络领域，有 实验表明引入光交换器件的d o s 结构在光网络交换中也体现了很好的实验效果。因 而可见e l o s 交换网络在今后交换系统设计方面的应用前景也很好。 以下介绍c l o s 交换网络的结构和阻塞特性。 如图2 9 所示为一个三级e l o s 结构基本模型，我们用c ( i n ，n k ) 来表示，其中n 为 输入模块每个模块的输入端口数，m 为输入模块的输出端口数，k 为中间模块端口 数。这样c ( m ，n ，k ) 结构就由k 个输入模块，k 个输出模块和m 个中间模块组成。其中 输入模块为n * m 交换单元，中间模块为k * k 交换单元，输出模块为m * n 交换单元。 整个结构共有n * k = n 个输入输出端口，形成一个n * n 规模的三级e l o s 网络。各模块 的连接规律可以归结如下： ( 1 ) 每一级的每个交换模块都要与下一级的每个交换模块相连，且和每个模块 只有一条路径相连。这样各级模块数目和模块的输入、输出规格存在这样一个关 系：每个模块的输入端口数目和上一级所有模块数目相等，而每个模块的输出端 口数目和下一级所有模块数目相等。 ( 2 ) 每一级的交换模块都是一个独立的全连通结构，可以是一个单级的交换结 构如e r o s s b a r 模块，也可以是一个小的多级结构如较小规模的c l o s 交换模块。 1 2 第二章多级交换结构简介 图2 - 9 三级c l o s 交换结构示意图 应用在分组交换网络中的c l o s 结构按照结构的不同可分为m m m ( m e m o r y - m e m o r y - m e m o r y ) ，m s m ( m e m o r y - s p a c e m e m o r y ) 和s s s ( s p a c e - s p a c e s p a c e ) - - - 类。其中应用最广泛的是m s m 结构，在此结构中采用基于分 组的选路方法，它要求在一个时隙内，交换网络要完成对该时隙需要处理的所有 分组的路由选择，选择的路由仅在该时隙有效，下一时隙起对所有分组重新路由。 图2 8 所示的5 级b e n e s 结构实际上也是一种c l o s 结构的变形。只需要将b e n e s 网 络的中间三级上下6 个模块分别当做一个模块处理，就会成为一个三级8 * 8 规模的 c l o s 网络，并可用c ( 2 ，2 ，4 ) 表示。而现在实际中采用的五级、七级等c l o s 交换结构实 际都是由三级c l o s 结构层层嵌套而来，由此可见，对三级c l o s 结构特别是对称三级 d o s 结构的研究具有一般性。 当交换结构中有输入端口和输出端口同时空闲时，一定可以在他们之间建立 起一条连接，而且不会影响其他已经建立成功的连接，这样的结构称为严格无阻 塞结构( s n b ) 。如果这样的连接有可能影响其他已经建立的连接，我们就称这种结 构为重置无阻塞结构( r n b ) 。而如果在这个结构中有可能无法在两个空闲的端口间 找到一条可用连接，那么我们称这种结构为阻塞结构。 单c r o s s b a r 结构为严格无阻塞结构，而设计c l o s 交换网络业是为了提供一种可 以替代c r o s s b a r 结构的无阻塞交换结构，虽然c l o s 结构的各输入输出端口间可以有 多条连接选择，比b a n y a n 结构的阻塞性能有很大提高。但是实现c l o s 结构的无阻塞 还需要满足一定的条件。 1 3 电子科技大学硕士学位论文 图2 1 0 所示三级对称c l o s 交换网络c ( m ，1 3 ，k ) 其无阻塞条件如下。 1 1 当n 、r n 满足关系m ， 2 n - - 1 时，整个c o s 结构为严格无阻塞( s n b ) 结构； 2 1 当n 、m 满足关系2 n 1 m n 时，整个d o s 结构为重置无阻塞( r n b ) 结构； 3 1 当n 、r n 满足关系n m 时，整个c l o s 结构为阻塞结构【1 6 1 。 本文仿真搭建的多级多平面交换结构模型中，中间级各交换平面使用c ( 3 ，3 ，4 ) 的三级对称c l o s 网络，并使用带缓存的c r o s s b a r 结构作为基本交换单元，为重置无 阻塞结构。 2 3 3 多级多平面交换结构 为了进一步扩充交换系统的容量、降低阻塞几率，还可以采用多平面结构对 单级或多级交换结构进行扩展。如图2 1 0 所示，将多个交换结构输入、输出线卡并 联接入，就可以组成一个更大规模的多平面交换结构。在这个结构中，输入线卡 根据当前连接情况将数据流分配到各个交换平面内进行交换处理，并在输出线卡 进行汇总输出。这样一方面提高了整体容量，可以承受更大的数据业务，另一方 面降低了单个交换平面内的交换强度，降低了各个交换平面内的阻塞几率，同时 提高了整个系统的容错能力。 图2 1 0 多平面交换结构示意图 1 4 第二章多级交换结构简介 2 4 多级交换网络中的p u l l 调度机制 当前的高性能核心路由器大多采用了多级多平面的交换结构，这些交换结构 具有易扩展强，可靠性高等特点，但是也因为巨大的端口数目和容量以及内部结 构复杂度，使其存在交换结构内部拥塞的可能。为了防止拥塞的产生，通常采用 “p u s h 调度机制( 也称为反压机制) 或“p u l l 调度机制( 也称为令牌机制) 产 生控制消息来控制发往输出模块的数据流量。本文仿真搭建的平台中借鉴了d u n e 公司的s a n d 芯片所采用的p u n 调度机制，以下做简要介绍。 图2 1 1 多级多平面交换结构示意图 图2 1 是一个简单的多级多平面交换结构示意图，它由输入模块( 蹦) 、交换 结构模块( 多个由s e l s e 3 组成的交换平面) 、输出模块( o m ) 三部分组成，交 换结构采用的是三级d o s 网络架构。其中，i m 模块和o m 模块的数目均为1 2 个， 每个i m 模块有3 个输出端口，分别连接交换结构中的三个交换平面，每个交换平 面是一个三级d o s 网络，第一级和第三级由4 个3 x 3 的交换单元组成，第二级由3 个4 4 的交换单元。 1 5 电子科技大学硕士学位论文 p u l l 调度机制的拥塞控制主要由令牌和状态信令完成，各级模块主要完成功能 如下： 1 输入模块( 蹦) i m 中维持1 2 个输入排队队列( v o q ) ，并为每个队列设立一个令牌( c r e d i t ) 计数器，当v o q 中有从输入端口进入的分组数据或信元数据要发送时，先查看 v o q 对应的令牌计数器，如果为正则表示有令牌，可以选择空闲端口向中间级交 换结构发送数据，如为零则表示没有令牌，需等待o m 模块的令牌到达后再发送 数据。i m 的另一项工作是发送数据状态信令给o m 模块，即每隔一定时间统计1 2 个v o q 的数据长度和令牌数，如果发现令牌数低于一定值后，则发送状态信令， 向v o q 对应的o m 模块请求令牌。此外，i m 还需要转发目的地是其他i m 的令 牌信令。 2 交换结构模块( s e l ，s e 2 ，s e 3 ) 负责数据和信令的转发，信令( 包括状态信息和令牌) 具有更高的转发优先 级。 3 输出模块( o m ) o m 接收由交换结构发来的信元和分组，对信元进行重组。同时维持一个各 i m 中对应v o q 的状态计数器，当收到来自i m 的状态信令后及时更新。并根据这 个状态计数器和网络负载情况，向各i m 模块发送令牌信令。和i m 一样，o m 也 需要转发从交换结构中到达的令牌信令【1 7 1 。 p u l l 调度机制是实现拥塞控制的重要算法，也是本文仿真过程的重要组成，但 并不是本文的研究重点，在此只做概述，第四章的仿真设计中会阐述p u l l 调度机 制的实现方法。 2 5 本章小结 与单级交换结构相比，多级交换结构具有更强的交换能力和扩展能力，更适 应于组建大规模高速核心交换系统，目前大部分的交换系统产品都是使用了多级 交换结构或在多级交换结构基础上建立多平面系统。本章介绍了从单级交换结构 到多级多平面交换结构的发展，并简要介绍了多级交换结构中的p u l l 调度机制，作 为以后各章的背景和理论基础。 1 6 度算法研究 3 1 单级交换结构中基于信元的交换机制 调度算法研究 在分组交换网络中有定长信元交换和变长分组交换两种基本的交换机制。在 现有的高速、大容量分组交换网络中，为了实现简单，都采用了基于时隙的同步 调度方式，因此，采用定长信元交换机制是分组交换网络交换机制的主流。在现 有大容量路由器产品中，几乎都采用定长信元交换机制。 一个典型的采用定长信元交换机制的交换网络结构如图3 1 所示。在交换网络 输入端需要一个输入分割模块i s m ( i n p u ts e g m e n t a t i o nm o d u l e ) ，将到达网络的变长 分组分割为定长信元，在每个信元前面加一定的标记以表明信元目的端口号及所 属的分组。在交换过程中，每一个信元是一个独立的单元，通过调度器采用一定 的调度算法进行转发。信元经过交换网络到达输出端口后，需要经过输出重组模 块o r m ( o u t p mr e a s s e m b l ym o d u l e ) ，将定长信元重组为变长分组。只有当属于同 一分组的所有信元全部到达，经过重组后分组才能输出。 图3 - 1 定长信元交换网络结构示意图 在近年的大容量交换机研究中，基于定长信元的交换机制已经被公认为一种 较有效率的方法，现有的路由器产品也大多采用将变长的p 分组切割为等长信元再 进行转发的方式。而这种切割分组的交换结构根据缓存的位置不同，又可分为输 出排队( o u t p u tq u e u i n g ) 交换网络，输入排队( i n p u tq u e u i n g ) 交换网络两类。 1 7 一 一 电子科技大学硕士学位论文 3 1 1 基于v o q 的输入排队策略 在较早的研究中，输出排队交换网络( o q ) 因为其较简单的控制方式，良好 的吞吐率和q o s 性能，得n t 较多的重视，这种交换网络的特点是：信元( 由分 组切割而成) 到达交换网络输入端口后，直接将其交换到输出端口，只在输出端 排队，不在输入端排队，如图3 2 所示。 s w i t c h i n g f a b r i c i n p u t 皿o u - p u t x 皿 - 工田 - 皿 ， 图3 - 2 输出排队交换网络模型 在交换网络容量仅有数m 至数g b p s 的情况下，o q 交换网络能够具有较好的 性能表现，较早的小规模路由器中也多采用这种模式。但是随着核心路由器交换 容量快速增长，以至于达到数t b i t s 的情况下，o q 网络的缺陷也愈发明显，那就 是在交换网络中具有n 个输入端口时，需要转发速率和输出缓存的输入速率达到 交换网络输入端口速率的n 倍，即需要n 倍加速。产生这种情况的原因可以理解 为，在极端情况下，一个时隙内所有n 个入端口都有信元发往同一个出端口j ，这 样j 端口必须在这个时隙内接收n 个信元，也就是接收速率要达到入端口速率的n 倍。然而，现有技术中，缓存输入速率的发展又恰恰远低于路由器交换容量和端 口速率的发展，几乎不可能满足n 倍加速的要求【l 引。所以现在的大规模交换网络 研究中，o q 已经很少使用，而输入排队交换网络( i q ) 成为了研究热点。 i q 网络的特点是：信元到达交换网络后，首先储存在输入端口的缓存中，再 由调度器根据不同的调度算法通过交换结构发往输出端口。模型如图3 3 所示。i q 网络相对于o q 网络的最大优点是输出端口的到达速率和输入端口的到达速率相 同，不用进行网络加速，规避了缓存输入速率较慢的瓶颈。 1 8 第三章不同交换机制的调度算法研究 s w i t c h i n g f a b r i c i n p u t ，蛊b o u t p u t ，工b x r - - _ i 7 - 工b一 -lr - 工b 一- i 7 图3 3 输入排队交换网络模型 在i q 网络中，如果每个输入端口仅有一个先入先出( f i f o ) 队列，目的地为 任意输出端口的信元都存入此队列的话，就会产生所谓头阻塞( h o l ) 问题，如 图3 _ 4 所示： r 一一头阻塞h o l 产生 i 0 - l 。 图3 - 4 头阻塞( h o l ) 不蒽 在交换网络中，输入端口0 的队列中有两个信元，分别发往2 号和1 号出端 口，在当前时隙，1 号出端口空闲，但是发往此端口的信元却无法发送，因为排在 前面的信元的目的端口被占用，这样造成交换网络资源的浪费。研究表明，当输 入端到达满足伯努利分布，输出端口等概的情况下，h o l 可以使交换结构的吞吐 率限制在5 8 6 ，而如果采用不能立即发送则丢弃的算法，可以使网络吞吐率达到 6 3 2 。 为了解决h o l 问题，一般采用虚拟输出排队策略( v o q ) ，即在输入端口中， 按照到达信元的目的端口来划分队列，如交换结构有n 1 个输入端口，n 2 个输出端 口，则在每个输入端口中保留n 2 个队列，分别对应每个输出端口，当有目的端口 1 9 电子科技大学硕士学位论文 为j 的信元到达端口i 后，存入队列q ( i d ) ，如图3 - 5 所示。采用v o q 后，再使用 合适的调度算法，可以使交换结构的吞吐量达到1 0 0 t 1 9 1 。 f a b r i c 岫：囝 o u t p u t 一乜型 - 压斗一 一l 兰到 ，囝 一乜到 ，压斗一 一i - r t - n l 图3 5 虚拟输出排队策略 3 1 2 迭代轮询( i s l i p ) 调度策略 交换结构中，输入输出级之间的匹配调度算法有很多种类，包括最大匹配 ( m a x i m u ns i z em a t c h i n g ，m s m ) ，最大权重匹配( m a x i m u mw e i g h t m a t c h i n g ，m w m ) ，稳定婚姻型匹配，确定型匹配等。其中m s m 和m w m 理论上可 以在可容许到达流量情况下，达到1 0 0 的吞吐率，但是这两种算法的复杂度较高， 硬件实现难度很大，所以在实际应用中，多采用极大匹配算法，来达到近似的最 大匹配。所谓极大匹配，就是在当前已经匹配过的情况下，无法再增加新的匹配 来使匹配数更大或者权重数更高。而极大匹配条件下，由m c k e o w n 提出的迭代轮 询( i t e r a t i v er o u n d r o b i nw i t hs l i p ，i s l i p ) 算法最为常用【2 0 1 ，这种算法的特点是 实现较为简单，同时也可以在可容许到达流量下，实现近似的最大匹配。 i s l i p 算法思想是，在建立匹配之前，输入端口和输出端口之间交互请求和应 答信息，通过输入端请求一输出端选择一输出端应答一输入端选择一建立匹配的 步骤来建立极大匹配。而输入( 输出) 端的选择是建立在他们各保留一个指针， 来指示当前最优先服务的输出( 输入) 端的基础上的。以一个4 输入4 输出的交换 结构为例，具体的实现步骤如下： 第三章不同交换机制的调度算法研究 i n p u t1 2 3 4 i n p u to u 巾a t 请求 2 3 4 准许指针 图3 6 ai s l i p 算法请求步骤 ( a ) 请求( r e q u e s t ) ：如图3 - 6 a 所示，交换结构的4 个输入端口中，端口l 的v o q 中有发往1 、2 号端口的信元，记为l ( 1 ，1 ) 、l ( 1 ，2 ) ，同理3 、4 号端口中有l ( 3 2 ) 、 l ( 3 ，4 ) 、l ( 4 ，4 ) ，则1 、3 、4 号输入端口分别根据需求向1 、2 、4 号出端口发送连 接请求，2 号端口没有需求则不发送。初始阶段，所有端口的服务优先指针均指向 1 。 i n p u t3 2 3 4 准诲 图3 6 bi s l i p 算法准许步骤 2 1 3 4 准许指针 一 萝萝萝虱 固移 一 雪蓼蓼虱 电子科技大学硕士学位论文 ( b ) 准许( g r a n t ) ：如图3 6 b 所示，输出端口1 、2 、4 接收到来自输入端口的请 求信息后，查询当前的服务优先指针，其中1 、2 号输出端口查询得知服务优先级 最高的为1 号输入端口，同时也接受到了来自1 号端口的请求信息，则他们都向l 号输入端口发送应答信息，并不再向其他端口发送。4 号输出端口的服务优先指针 指向的是1 ，但是收到的是来自3 、4 号输入端口的请求，则从1 向后查询，累加 并与4 取模，查询得知3 号端口具有较高的优先级，则向3 号输入端口发送应答 信息。 i n p u t 1 i n p u t 2 i n p u t 3 i n p u to u t p u t 一1 2 接受 准许指针 图3 6 ci s l i p 算法匹配步骤 ( c ) 接受( a c c 印t ) ：如果3 6 c 所示，此时，输入端口1 、3 接收到了来自输出端 的应答信息，其中1 号输入端口接受到两个分别来自1 、2 号输出端的应答，则查 询服务优先指针，查询得知1 号出端口具有较高优先级，则与1 号建立匹配。3 号 输入端口只收到一个来自4 号输出端口的应答信号，则与4 号建立匹配。这样， 本轮共建立了2 个匹配，分别是l ( 1 ，1 ) 和l ( 3 ，4 ) 。匹配建立完毕后，各参与匹配的 端口根据匹配情况修改服务优先指针，分别将指针修改为本轮所服务的端口号的 下一个。没有参与匹配的端口不修改指针。 以上( a ) ( b ) ( c ) 过程迭代若干次后，即可完成极大匹配。有研究表明在b e r n o u l l i 独立同分布( i i d ) 到达流量情况下，i s l i p 算法可以达到1 0 0 的吞吐率1 2 l 】【冽。 i s l i p 算法作为单c r o s s b a r 结构中最常用的调度算法，本文所进行的仿真中有 使用，但是根据仿真情况的不同，做了一些改变和近似处理。 移一移一 虱萝雪萝 第三章不同交换机制的调度算法研究 3 2 单级交换结构中基于分组的交换机制 3 1 节介绍了基于信元的交换机制以及这种机制的排队策略和调度策略。可以 看出，在单级交换结构中，基于信元的交换机制性能能够得到较好的发挥，但是 在交换结构从单级向多级发展的过程中，采用定长信元交换机制会带来一系列的 问题，其中最为突出的问题是，在多级交换网络中，属于同一分组的不同信元会 产生乱序现象，信元乱序是因为分组的各信元独立路由，从不同的交换单元到达 目的端口，会因为各交换单元的交换时延不同而产生较大的到达时间差异，顺序 也会与切割时的顺序不同。乱序问题的解决需要增加更为复杂的排序算法，以及 在交换结构的输出端增加更多的信元重组缓存( p a c k e tr e s s e m b l eb u f f e r ) ，带来了交 换网络实现成本和调度算法复杂性的增加。 基于信元的交换机制的另一个问题是会造成一定的网络带宽的浪费，这是因 为交换的所有信元都是固定长度，而实际d 网络中传输的分组长度却不一定是这个 固定长度的整数倍，例如，如果交换结构中切割的信元长度为6 4 b y t e s ，而分组长 度为8 0 b y t e s ，每个分组需要被切割为两个6 4 b y t e s 的信元，这样实际利用带宽只有 8 0 ( 2 * 6 4 ) = 6 2 5 ，另外的3 7 5 的带宽被浪费在传输冗余信息上。 因为以上原因，现在的研究中对基于分组的交换机制进行了关注。基于分组 的交换有两种实现方式： ( 1 ) 逻辑切割交换分组：同基于信元的交换方式相同，依然对变长分组进行切 割，切割成固定长度的信息单元，一个信息单元的长度是交换网络中一个时隙可 发送比特数。所不同的是交换网络不再对同一个分组的不同信息单元进行单独的 路由选择，而是让他们沿同一路径先后到达目的端口。基本实现方法是将一个分 组p 切割为n 个信息单元后，只在第一个单元p l 和最后一个单元p n 分别加上一个头单 元标记h e a d 和尾单元标记t a i l ( 或者仅仅只有头单元标记或者尾单元标记) ，中间各 单元不做任何处理。各交换单元通过识别头单元标记和尾单元标记来实现对同一 分组各单元的统一路由。因为这样的切割分组方式实际上并没有改变分组中数据 在交换网络中的传输顺序，中间各单元也没有增加额外的开销，所以也称为逻辑 切割。 ( 2 ) 直接交换分组：这种交换方式不再对分组进行任何的切割，直接在交换结 构中传输分组，但是因为m 网络中分组长度不固定，而现有交换结构几乎都采用固 定时隙的结构，每个时隙发送数据量都相等，所以在这种同步交换结构下很难实 现。要实现直接的交换分组，必须使交换结构的各输入输出端口不再需要在相同 电子科技大学硕士学位论文 的时隙发送和接收数据。即实现交换结构的异步交换，带中间交叉节点缓存的 c r o s s b a r 结构可以实现这样的异步交换。 多级交换网络中，变长分组交换相对于定长信元交换的最大优点是，同一个 分组的所有比特都是按顺序连续在结构中发送，各输入端的分组不会发生交织混 乱，到达输出端口后不会产生乱序现象，分组重组的复杂度也会有较大降低。但 是因为这种交换机制的调度算法与口分组的长度有密切的关系，这样就降低了交换 网络对业务的适应能力。 近年来单级交换结构中的变长分组交换机制已经有了较多的研究，并形成了 一些较完善的调度算法可以实现变长分组的交换。下面分别总结逻辑切割交换分 组和直接交换分组的调度算法。 3 2 1 逻辑切割交换分组算法 逻辑切割分组的交换机制和基于信元的交换机制有较大的相似性，调度算法 也有很多都是从基于信元的交换机制调度算法改进而来，根据连续传送同一个分 组的信元的特点，进行部分的改进。包括i p p 1 m 、p b i s l i p 、s o l 、p b m w m 等 算法，以下分别做简要介绍。 1 i p - p i m 算法 最早将定长信元调度算法应用于变长领域的称为i p p l m 算法【2 3 ，包括四个步 骤： ( a ) 保持前一个时隙仍然处于服务状态的端口匹配不变。 ( b ) 每个有信元发送需求的入端口，如果还没有匹配，则向所有对应出端口发 送请求 ( c ) 如果一个出端口收到多个请求，则随机选择一个进行准许，通告给入端口。 ( d ) 如果一个入端口收到多个准许，则随机选择一个进行接受，并通告给出端 口。 可以看出i p p i m 主要采用随机方式完成匹配，这种方式的问题是：每个调度 器必须在一个变化的集合里做随机的选择，而在高速交换条件下，每个时隙通常 只有几十纳秒，这样很短的时间内实现随机的选择将会比较困难。同时，对于不 稳定的流量，随机方式还会导致匹配的不公平性。 2 p b i s l i p 算法 对3 1 2 节所述的i s l i p 算法进行改进后的算法称为p b i s l i p ( p a c k e t - b a s e d 2 4 第三章不同交换机制的调度算法研究 i s l i p ) 算法【2 4 1 。 p b i s l i p 算法所服务的数据是经过逻辑切割的分组，每个分组切割后的最后 一个信息单元打上t a i l 标记，称为e o p ( e n do fp a c k e t ) 单元。因为这样的分组仍然 要进行切割，并按照固定时隙发送，所以p b i s l i p 算法仍可以使用3 1 1 节所述基 于v o q 的输入排队策略，只是需要对i s l i p 算法的端口匹配过程做出一些改变。 同i s l i p 算法一样，p b i s l i p 的迭代过程也需要经历请求、准许、接受三个步骤。 具体如下： ( a ) 请求：所有入端1 2 查看自己的v o q ，并向所有有数据发送的出端口发送请 求连接信息，与i s l i p 不同的是，还需要通告出端口所请求的数据单元是否是e o p 单元。 ( b ) 准许：这一步骤基本与i s l i p 基本相同，所有出端口接收到来自入端口的 请求后，查询自己的服务优先级指针，并从收到的所有请求中选择具有最高优先 级的入端口发回应答信息。 ( c ) 接受：入端口收到来自出端口的应答信息后，也查询自己的服务优先级指 针，从所有应答信息中选择一个优先级最高的做出回应，即为接受信息，接受信 息发出后，就表示一条匹配建立了。这个过程与i s l i p 相同，不同的是，i s l i p 算 法建立一个匹配后，匹配成功的入端口和出端口的服务优先级指针总是要做出改 变，指向当前匹配端口的下一个端口。而p b i s l i p 算法则是要判断当前建立的匹 配所服务的数据单元是不是e o p 单元，如果是，则按照i s l i p 算法的指针修改方 案进行修改，如果不是，则不对服务优先级指针做修改，输入端和输出端都是如 此。 以上( a ) ( b ) ( c ) 为一次迭代过程，进行若干次迭代后，匹配完成，这个迭代次数 要小于i s l i p 的迭代次数。每次迭代成功的出端口号，在以后迭代中的入端口服务 优先级指针中将被锁定，排除在可服务端口之外，即不再发送请求信息。 p b i s l i p 算法的特点是一旦一个分组的第一个信息单元在交换结构中被服务， 发往出端口以后，他后面的所有信息单元就会连续的从相同路径发往相同出端口， 中间不会夹有其他分组的信息单元。这种算法也有一个问题是，如果一个数据分 组较长，那么交换结构连续发送它所需的时间就较长，同时在v o q 中等待的其他 较短的分组就无法得到服务，传输时延增大，总体传输时延也会增加。 3 s o l 算法 针对不同长度数据分组服务不公平的情况，一种称为s o l ( s e l f - o p t i m i z e d l a t 既c y ) 的算法对p b i s l i p 算法进行了进一步的修改【2 5 】，主要是给各v o q 赋予一个 2 5 电子科技大学硕士学位论文 信誉度( 翻耐i d ，并在第二步准许阶段时，出端调度器根据信誉度来选择服务哪