Clos交换结构的基于相异代表组的路由控制算法.pdf

第 3 7 卷第 3 期 西 华 师 范 大 学 学 报 （自 然 科 学 版 ） 2016 年 9 月 Vol . 37 No . 3 Journal of China West Normal University (Natural Sciences) Sep .2016 文章编号 ：1673-5072(2016)03-0354-07 Clos父换结构的基于相异代表组的路由控制算法 刘晓锋 (M 平 师 范 大 学 计 箅 机 学 院 J-L 丨川*允 637009) 摘 要 ：Clos交换结构作为多级结构的典讀代表在以大数据、数据中心网络为特征的云计算时代再次受到业界的 关注，但目前应用于 Clos交换结构的分组控制算法（或调度算法）却较难以适应大数据及数据中心网络的低延迟， 低能耗等的性能霸求。因此，根 据 Clos交换结构中分组调度的本质，利用相异代表组（SDR)基本思想为每个分组 分配不同中间级交换模块，从而实现无阻塞交换，同时以示例和理论上证明了该算法的可行性及算法实现。由于 该控制算法有效避免了大量的仲裁信息，因此能有效降低交换延迟，提高交换吞吐率。 关键词 ：分组交换；相异代表组；Clos网络；控制算法 中图分类号：TP393 文献标志码：A D01：10. 16246/j . iss . 1673-5072.2016.03.022 〇 引 言 Clos 网络[1]作为电话交换网络的产物， 却在分组交换中扮演了非常重要角色，特别 是在以大数据、数据中心网络为特征的云计 算成为主流运维模式的背景下，它作为数据 中心网络的物理架构再次成为企业及学术 界的研究焦点。一个 C lo s 交换网络是由输 入级、输出级和中间级连接而成的3 级结 构，级与级之间由通信链路通过部分互连的 方式连接而成，如图1所示s 输入级的交换 模块称为输入模块（ input m odule ，I M ) ，输出 级的交换模块称为输出模块（ output mod- u le ，0 M ) ，中间级的交换模块称为中间模块 (center m odule ，CM )。 每个 IM ( 0M )是一^ 个 ^^爪 （爪乂〃）的交换矩阵，每个0^[是一 图 1 Clos交换结构 个 r x r 的交换矩阵，而且每个 IM (O M )模 块都有唯一链路连接一个C M 模块，因此一个Clos交换网络的相关属性完全由参数〃，m ，r 来决定。当 此网络严格无阻塞[1];当 为 可 重 排 无 阻 塞 [气 交换网络的一个指派（assignment)是所有输入/输出端口组成有序对 输入端口，输出端口 的集合，而 且每个端口只能出现在一个有序对中2 有序对输入端口，输出端口 指明了分组在交换结构中的入口和 出口 e 在交换结构内部如果存在不相交（即不产生冲突）的路由路径来链接指派中的每个有序对，则称此指 派是可行的（realizable) s 对 Clos交换网络来说 ，一 个指派是否可行与C M 的分配策略紧密相关。如果 CM 分配不合理，则其内部的路由路径可能会产生冲突，最终致使分组丢失，交换吞吐率降低e 为了确保一个指 派是可行的，通常需要相应的路由控制算法来控制每个有序对输入端口，输出端口 的路由路径。在设计 收稿日期=2016-01-18 基金项目 ：西华师范大学博士启动基金项目（15E013 ，11B 026); 四川省教育厅重点项目（16ZA0174) 作者简介:刘晓锋（1972 —），男 ，重庆石柱人，副教授，博士，主要从事计算机网络体系条结构、路由与交换等相关研究 s 通讯作者：刘晓锋，E-mail :xhxfliu@ 163. com 第 37卷第3 期 刘晓锋 ：Cl〇s交换结构的基于相异代表组的路由控制算法 355 交换网络内部的路由控制算法时，可将路由问题转化矩阵分解（ matrix decomposition )问题，二分图匹配 （bi­ partite m atching) 问题及边着色 （ edge