Clos交换网络的一种基于矩阵分解的路由指派算法.pdf

第 36卷 第 4期 西 华 师 范 大 学 学 报 (自然 科 学 版 ) 2015年 12月 Vo1．36 NO．4 Journal0fChinaWestNormalUniversity(NaturalSciences) Dec．2015 文章编号 ：1673—5072(2015)04-0404-07 Clos交换网络的一种基于矩阵分解的路由指派算法 刘晓锋，吴亚娟 (西华师范大学 计算机学院，四川 南充 637009) 摘 要：CIos交换网络以其低成本优势和良好的可扩展性成为高速大容量交换系统的主流交换结构；另外，随着 数据中心网络(datacenternetwork，DCN)诞生与发展 ，交换节点(路 由器 ／交换机)面临更苛刻的性能需求 ，但相应 的指派算法因各种原因无法很好地服务于数据 中心环境下的路 由与交换．矩阵分解是解决 Clos网络的路 由指派 的 重要途径 ，但 目前 已有 的大多数分解算法被证 明为不完全．因此 ，基于矩阵分解提出一款针对可重排无阻塞 Clos网 络的非常有效的路 由指派算法．该算法采用逐行分解策略，不仅能有效解决同类算法 的不完全性，亦能在 串行时间 0 (nr)内正确地分解任意的业务矩阵，而且避免在调度器与线卡之间产生较长的往返时间，简单易实现于 Clos交 换 网络 ． 关键词 ：路由算法；交换网络；Clos网络；矩阵分解 中图分类号：TP393 文献标识码 ：A DOI：10．3969／j．issn．1673—5072．2015．04．016 0 引 言 Clos交换网络 ¨发展至今 已有 60余年的研究历史，最早是针对电话交换网络 ，随着 IP网络的快速发展 和 Clos网络本身的良好可扩展性及优越的网络性能，它被应用于IP网络的分组交换中，特别是用于高速、大 容量交换机 ／路 由器的设计 中，如 JuniperT1600／TX—MatrixPlus系列．另一方面，随着数据 中心网络 (data centernetworks，DCN) 的诞生和发展，Clos交换网络再次成为研究热点．一个 DCN通常 由成千上万甚至上 百万的服务器和交换机 ／路由器组成 ，如何组织如此之多的服务器和交换机才能满足 DCN的高可扩展性 、低 延迟及低能耗的本质需求是一个极其重要的研究课题．Clos网络或其扩展结构 (如 Folded—Clos结构)作为 DCN的拓扑结构已被广泛研究 儿 ，但很少涉及底层交换节点的体系结构及路 由算法．目前相应于 Clos交 换网络的迭代类路由指派算法因在线卡与调度器之间较长的往返时延而不能很好地适用于 DCN环境下的 数据交换 ，另外矩阵分解类路由指派算法又因分解不完全致使该类算法在某些情况下不能正常工作．因此 ， 本文 旨在对 Clos交换 网络的经典指派算法的研究基础上，给出适合于 DCN环境下的基于矩 阵分解的路由 指派算法． 1 基本 网络结构及条件假设 在宏观上 ，Internet由两类硬件设施组成 ：通信链路 (1ink)及交换节点(node)．通信链路只负责数据分组 的传输 ，不负责分组的转发；交换节点虽然也执行分组的传输 ，但其主要功能是负责分组的转发，即根据 IP 地址在整个 IP网络里转发 IP分组． 为了分组的路 由与转发 ，路 由器 ／交换机主要 由三部分构成 ，即路 由软件 (routingsoftware)、线卡 (1ine card)和交换结构 (switchfabric)，如图1所示 ．路 由软件即路 由算法 ，它控制 IP分组从交换结构的某个输 收稿 日期 ：2015—08—14 基金项 目：西华师范大学科研启动项 目(11B026) 作者简介：刘晓锋 (1972一)，男 ，重庆石柱人 ，副教授 ，博士，主要从事计算机 网络与通信 、路 由与交换研究 ．E-mail：xhxfliu @ 163．tom 第 36卷第4期 刘晓锋 ，等：Clos交换 网络的一种基于矩阵分解 的路 由指派算法 405 人端 口交换到某个合适 的输出端 口以避免在交换结构里发生阻塞而丢包．这个过程是与特定的交换结构相 关 ，本文讨论的路 由指派算法是针对可