（通信与信息系统专业论文）torus交换结构中对多优先级业务交换性能的研究.pdf

中文摘要 中文摘要 随着互联网络的应用逐步深入人们工作和生活，各类基于网络的服务发展迅 速。这对i p 核心网络中的路由器提出了更高的要求：一方面要求路由器具备大容 量数据交换能力；另一方面，各种不同的业务( 如个人、企业级的不同应用) 对 服务质量有着不同的需求，要求路由器能进行区分服务。t o r u s 多维交换结构是一 种灵活的、可扩展的大容量交换结构，是对新一代大容量核心路由器一t 比特路由 器的交换结构的研究方向之一。 在传统的交换结构研究领域，对多优先等级业务的区分服务主要依赖交换结 构中的优先资源调度。由于t o m s 交换结构的特殊性，内部路由算法在系统的交换 性能( 吞吐量和时延) 上起着决定性作用。本文主要研究了t o m s 交换结构中支持 多优先等级业务的内部路由算法及其对交换性能的影响。 文中提出了优先象限路f 1 3 ( p q r ，p r i o r i t yq u a d r a n tr o u t i n g ) 算法。它是一种在 t o m s 交换结构中支持多优先等级业务的无死锁的内部路由算法，能支持对时延有 不同要求的多种业务。在n 维的t o m s 交换结构中，p q r 算法可以支持n + 1 个不 同优先等级的业务。算法的核心思想是根据分组的源目节点对的坐标，将n 维t o r u s 交换网络分成n + 1 个不同优先等级的象限，对不同的业务根据其优先等级进行区 分路由。算法中规定高优先等级业务( 实时业务) 只能在最短路径上路由，而低 优先等级业务( 准实时业务和非实时业务) 则可以绕开热点资源，在较长路径上 路由到达目的节点。p q r 算法能保证实时业务的短时延要求。同时，由于业务可 以分散到非最短路径上，提高了交换结构的吞吐量。 同时，为了保证在不同业务模式( t r a f f i cp a t t e r n ) 下交换结构的吞吐量，文中还 提出了业务均衡的优先象限路由( p r i o r i t yq u a d r a n tr o u t i n gw i t hl o a db a l a n c e ， p q r l b ) 算法。该算法的核心思想是，可以根据当前的网络负载状态对较低优先等 级的业务进行自适应路由，使业务路由到负载相对较低的链路上。该算法相比于 p q r 算法，在不均衡的业务模式下也能达到较高的吞吐量，并保证实时业务的短 时延。 文章的结构如下。 第一章介绍了t 比特路由器和t o m s 交换结构，说明了虫孔路由交换方式和虚 通道流控制方式，以及多虚网络的概念。 中文摘要 第二章分析了在t o m s 交换结构模型下的内部路由和路由死锁问题。 第三章中提出p q r 算法的核心思想和流程。描述了p q r 算法所支持的多优先 级业务模型，说明了优先象限的划分方法，并给出了p q r 算法的选路约束条件和 路由方程，以及p q r 的无死锁证明。根据路由方程，说明了不同优先级业务的区 分路由和p q r 算法的流程。 第四章中提出了p q r l b 算法。分析了不均衡的业务模式对t o m s 的负载和交 换性能的影响，提出了根据当前业务负载进行自适应选路的p q r l b 算法，并说 明了算法对阻塞业务的处理以及流程；说明了p q r l b 算法所采用的两级调度机 制，并给出了对多优先等级业务的区分调度策略。 第五章对两种算法的仿真数据进行了分析。与现有算法进行了比较，分析了 它们对系统的吞吐量、时延以及业务均衡的影响，分析了不同优先等级业务在不 同算法下的吞吐量、时延及均衡性。在第2 节给出了搭建的仿真平台的结构和模 块。 第六章对全文进行了总结。 关键词：t o r u s 交换结构，多优先级业务，负载均衡，p q r 路由算法，p q r l b 路 由算法。 a b s t r a c t a b s t r a c t a l o n gw i t h t h ed e v e l o p m e n to fi n t e m e ta p p l i c a t i o n ，t h ew e b b a s e ds e r v i c e s b e c o m em o r ea n dm o r ew i d e l yu s e d o no n eh a n d ，i tr e q u i r e st h ec o r en e t w o r kr o u t e rb e a b l et os w i t c hl a r g ea m o u n to fd a t a o nt h eo t h e rh a n d ，i ta l s or e q u i r e st h en e t w o r k r o u t e rs u p p o r tp r i o r i t i z e dt r a f f i c t h et o m ss w i t c h i n gf a b r i c ，a sa l la g i l ea n de x t e n s i b l e s w i t c h i n gf a b r i cw i t hh i g ht h r o u g h p u t ，h a sb e c o m eo n eo ft h eo p t i o n a ls t r u c t u r e so f t e r a b i tr o u t e r , an e wg e n e r a t i o nh i g hc a p a c i t yr o u t e rf o r t h ec o r en e t w o r k t r a d i t i o n a l l y , t h e d i f f e r e n t i a t e ds e r v i c e sf o rp r i o r i t i z e dt r a f f i cd e p e n do nt h e p r i o r i t i z e ds c h e d u l i n go fr e s o u r c e si n t h es w i t c h i n gf a b r i c h o w e v e r ，b e c a u s eo ft h e s p e c i a lt o p o l o g yo ft o r u ss w i t c h i n gf a b r i c ，t h er o u t i n ga l g o r i t h mh a sm o r ei m p a c to n t h ep e r f o r m a n c eo ft h es w i t c h i n gf a b r i cr a t h e rt h a nt h es c h e d u l i n gs c h e m et h e r e f o r e ， t h em a i np u r p o s eo fo u rw o r ki st of i n dar o u t i n ga l g o r i t h mt os u p p o r tp r i o r i t i z e dt r a f f i c a n da n a l y z ei t si n f l u e n c eo nt h ep e r f o r m a n c eo f t o m s p r i o r i t yq u a d r a n tr o u t i n g ( p q r ) i sp r o p o s e d i ti sad e a d l o c k - f l e ea d a p t i v e r o u t i n ga l g o r i t h ms u p p o r t i n gp r i o r i t i z e dt r a f f i cf o rt o m s p q rc a l ls u p p o r t3d i f f e r e n t p r i o r i t i e so ft r a f f i ci n2 - d i m e n s i o nt o r u s ，a n d4i n3 - d i m e n i s o nt o m s i np q r ，a n n - d i m e n s i o nt o r u sn e t w o r ki sd i v i d e di n t oq u a d r a n t sf o re a c hs o u r c e d e s t i n a t i o n n o d e - p a i r ( s dp a i r ) ，a n daq u a d r a n tp r i o r i t y ( q p ) i sa s s i g n e dt o e a c hq u a d r a n tf o r r o u t i n gs t r a t e g i e so fd i f f e r e n tp r i o r i t yt r a f f i c p q rp r o v i d e sb o t hm i n i m a lp a t ha n d n o n m i n i m a lp a t hf o rl o wp r i o r i t yt r a f f i ct oa v o i do c c u p y i n gh o tr e s o u r c e s ，w h i l et h e h i g hp r i o r i t yt r a f f i cc a no n l yr o u t eo nm i n i m a lp a t hf o rl o wl a t e n c y i nt h i sw a y ，p q r c a na c h i e v eh i g h e rt h r o u g h p u tt h a nm i n i m a lr o u t i n ga l g o r i t h m s ，a n dp r o v i d eal o w l a t e n c yo fh i g hp r i o r i t yt r a f f i c t h e nt h ep r i o r i t yq u a d r a n tr o u t i n gw i t hl o a db a l a n c e ( p q r - l b ) a l g o r i t h mi s p r o p o s e di nt h i sa l g o r i t h m ，a c c o r d i n gt os t a t u so fc u r r e n tt r a f f i cl o a d ，t h el o w e rp r i o r i t y t r a f f i cc a l lr o u t et ot h el i n kw i t hc o m p a r a t i v e l y1 0 wt r a f f i cl o a df o rs o m et i m e t h e t r a f f i cs e n tt oe v e r yl i n kc a nb eb a l a n c e d t h u s ，t o m sw i t hp q r - l bc a na c h i e v eh i g h t h r o u g h p u te v e no nt h ea d v e r s a r i a lt r a f f i cp a t t e r n s i i i a b s t r a c t t h i st h e s i si so r g a n i z e da sf o l l o w s ： c h a p t e r1 i n t r o d u c e st h eb a c k g r o u n dk n o w l e d g eo ft e r a b i tr o u t e ra n dt o m s s w i t c h i n gf a b r i c ，a n de x p l a i n st h ew o r m h o l ea n dv i r t u a lc h a n n e ls c h e m e sa n dc o n c e p t o fv i r t u a ln e t w o r k c h a p t e r2c l a r i f i e st h er o u t i n gc l a s s i f i c a t i o na n dd e a d l o c kp r o b l e mi n t o r u s ， a n a l y z e st w oc l a s s i c a ld e a d l o c k - f l e ea l g o r i t h m sa n do n eq o ss u p p o r t i v es t r a t e g y c h a p t e r3g i v e st h ek e yi d e a a n dp r o c e s so fp q ra l g o r i t h mi td e s c r i b e st h e p r i o r i t i z e dt r a f f i cm o d e lp q rs u p p o r t s ；e x p l a i n sh o wp r i o r i t i z e dq u a d r a n t sa r ed i v i d e d t h e n ，t h ec o n s t r a i n t sa n dr o u t i n gf u n c t i o na r eg i v e n ，a c c o r d i n gt ot h er o u t i n gs t r a t e g y , w ec a np r o v et h a tp q ri sd e a d l o c k - f r e e ，a l s o ，h o wt h ep r i o r i t i z e dt r a f f i ci sr o u t e da n d t h ep r o c e s so fp q ri sd e s c r i b e d c h a p t e r4p r o p o s e st h ep q r l ba l g o r i t h m i tf i r s ta n a l y z e st h eu n b a l a n c e dt r a f f i c p a t t e r n si m p a c to nt h ep e r f o r m a n c eo fs w i t c h i n gf a b r i c ，a n dt h e nt h em a i ni d e ao f p q r l b i s g i v e nt h a tt h ea l g o r i t h mc a na d a p t i v e l y s e l e c tt h e p a t hw h i c hh a s c o m p a r a t i v e l yl o wt r a f f i cl o a d t h e nt h e2l e v e lo fs c h e d u l i n gs t r a t e g yi si n t r o d u c e d ， a n dt h ei m p r o v e m e n to nt h es c h e d u l i n gs c h e m et o s u p p o r tp r i o r i t i z e dt r a f f i c i s d e s c r i b e d c h a p t e r5a n a l y z e s t h es i m u l a t i o nd a t ao ft h e s e2a l g o r i t h m s i tc o m p a r e st h e o v e r a l lt h r o u g h p u t ，e n d t o e n dl a t e n c ya n dl o a db a l a n c eb e t w e e nt h e2a l g o r i t h m s a l s o ， t h et h r o u g h p m ，l a t e n c ya n dl o a db a l a n c eo fd i f f e r e n tp r i o r i t yo ft r a f f i ca r ec o m p a r e da n d a n a l y z e d t h e nt h e 6 t hc h a p t e rg i v e sas u m m a r yo ft h ew h o l et h e s i s k e y w o r d s ：t o r u s ，p r i o r i t i z e dt r a f f i c ，l o a db a l a n c e ，p q r ，p q r l b i v 图目录 图目录 图1 - 1a v i c i 的4 3 x 2t o r u s 结构 图1 2b r i g h t l i n k 的4 元4 方t o m s 结构 图1 32 元4 维h y p e r c u b e 图1 - 44 3 x 3m e s h 交换网络 图1 54 x 3 2t o r u s 交换网络 图1 - 6 虫孔路由 图1 7 物理通道空闲的时候分组a 后面的分组b 仍被阻塞 图1 - 8 虚通道提供了额外的缓存以允许分组b 超越被阻塞的分组 图1 - 9 传统节点的缓存组织形式 图1 1 0f o l d e d t o m s 示意图 图2 - 1 通道死锁 图2 - 2 二维m e s h 中的可能的抽象环和拐角 图2 3 在x y 路由算法中允许的四个拐角 图2 - 4 六个拐角形成的环并可能产生死锁 图2 5 二维t o r u s 交换结构中的路由 图2 - 63 7 t o r u s 与4 7 t o r u s 中4 一c h a n n e l 的路由图 图2 78 节点环 图2 8 最短路径的龙卷风模型，逆时针链路负载为o 图2 9r l b 中间节点位置的概率分布 图2 1 0 使用r l b 路由算法的一个示例 图3 - 1 二维t o m s 交换结构的象限划分图 图3 - 25 5 的t o m s 交换结构中，源目节点分别为( 1 ，1 ) 和( 2 ，3 ) 的路径图 图3 3p q r 算法的资源请求拐角模型 图3 - 4 采用p q r 算法的t o r u s 交换结构中的节点模型 图3 55 7 的t o m s 交换结构中，源目节点分别为( 1 ，3 ) 和( 5 ，1 ) 的路径图 图3 6p q r 算法实现流程 图3 7 不同优先等级业务在交换结构中路由的跳数 1 0，0；，00 0 m b b h螺堪蜉斟拍勰凹砣 图目录 图3 。8p q r 算法中不同优先等级业务的平均时延 图3 - 9 多种算法的业务平均时延 图3 1 0 多种算法在r p 业务模式下随输入业务量变化的吞吐量 图4 1 滑动时间窗口内节点在x 一方向上的三日陋j i 值 图4 2 节点工与相连的四个子网络 图4 3p q r l b 算法流程图 图4 - 4 支持虚通道流控制的逻辑图 图4 5 两级调度流程图 图4 6r p 业务下p q r l b 与p q r 的随输入业务量变化的吞吐量 图4 7 多种业务下p o r l b 与p q r 的业务吞吐量 图5 1 多在u r 业务模式下随输入业务量变化多优先等级的业务吞吐量 图5 2 不同优先等级业务比例下系统吞吐量 图5 3 不同算法在r p 业务模式下所有节点吞吐量的标准差 图5 4 不同算法在r p 业务模式下随输入业务量变化的吞吐量 图5 5p q r l b 算法在随着不同滑动时间窗口大小变化的吞吐量 图5 - 18 x 8t o r u s 交换结构拓扑 图5 2 节点工作流程图 图5 3 交换节点示意图 图5 - 4 源模块状态转换图 图5 5 注入模块状态转换图 图5 - 6 交换模块状态转换图 图5 7 路由与仲裁模块状态转换图 图5 7 接收模块状态转换图 v l i | 弭弭硝卯舵钙甜牾们锣如豇豇亚驺弭巧卯船趵 表目录 表目录 表1 - 1 多虚网络t o m s 框架简要描述 表4 - 1 某滑动时间窗v i 内节点l 在所有方向上的l b ( l ) i 值 表6 - 1 多维分组交换结构简要描述 i n 9 3 8 4 6 简略字表 简略字表 d o rd i m e n s i o no r d e rr o u t i n g维序路由 i s u pn e r a t i v er o u n dr o b i nm a t c h i n gw i t hs l i p 使用s l i p 的迭代轮询 匹配 l bl o a db a l a n c e 负载均衡 p p p a c k e tp r i o r i t y 分组优先等级 p o r f r i o r r yq u a d r a n tr o u t i n g优先象限路由 p q r l b p r i o r i t yq u a d r a n tr o u t i n g w i t hl o a d 负载均衡的优先象限路 b a l a n c e 由 q o s q u a l i t yo fs e r v i c e服务质量 q p q u a d r a n tp r i o r i t y象限优先等级 v c v i s u a lc h a n n e l虚通道 8 一c h a n n e ls t a rc h a n n e l 星通道 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：捌1 5 辱笔日期：础7 年斗月圬目 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：趔! ! 鱼导师签名 日期：钞吖年4 月1 厂日 第一章t o r u s 交换结构概述 第一章t o m s 交换结构概述 1 1t 比特路由器与多维交换结构 随着全球交流与合作的加剧，各个行业对快速、可靠和多样化的通信需求越 加强烈。上个世纪末期，互联网企业用户的迅速增多，网上商务活动的频繁进行， 标志着互联网络经济时代的到来。网络互联、1 p 电话及电子商务是这个阶段中的 主要业务，突破了通信的时问空间的限制。进入2 1 世纪之后，新的互联网络经济 呈现出更加巨大的市场。据预测，全球互联网用户将在2 0 1 0 年超过1 0 亿；同时， 互联网络所提供的w e b 服务也将更加广泛融入企业应用，支持企业跨流程、跨平 台的远程或者托管运作，促进企业对互联网交易平台的需求；网络用户也对丰富 的增值网络服务更加感兴趣，如视频通信，应用共享等；越来越多的网络高端消 费也刺激了网络服务供应商提供越来越多的网络服务，并寻求更为优质的网络环 境。 新的需求对网络通信提出了更高的要求，除了丰富的网络带宽，高速的网络 接入之外，更需要网络具备高可靠性和高安全性，保证不同业务的服务质量需求。 面对网络的需求，业界首先关注的是全球口骨干网的容量。全球i p 骨干宽带网发 展一直保持高速发展。据电信业调查机构t e l e g e o g r a p h y 在2 0 0 4 年的b r o a d b a n d y e a rb o o k 中指出，美国和欧洲等成熟市场的骨干网在2 0 0 3 年增加了3 0 一4 0 。 亚洲的骨干网2 0 0 3 年扩大了7 0 。以中国为例，我国的光缆总长度即将达到2 5 0 万公里，其中教育网c e r n e t 目前拥有3 0 0 0 0 多公里的光纤资源，骨干网带宽达 到了1 0 g b p s ，地区网带宽也达到了2 5 g b p s 。 同时，网络中的用户数量、业务量、链路数、单条链路的带宽，或是服务提 供商网络都迅速增长。网上数据流量的高速增长，对互联网节点核心设备骨 干网路由器不断提出挑战。这不仅要求能够提高带宽及业务的吞吐量，拥有足够 大的数据交换带宽和数据包处理和转发能力，而且还要具备丰富的软件功能及控 制特性，以保证不同业务的服务质量。 于是，t 比特骨干网路由器开始进入了路由器的前沿市场1 1 】。目前全球主要的 路由器生产厂商，如j u n i p e rn e t w o r k s ，a v i c is y s t e m s “，c i s c os y s t e m s 和华为都 电子科技大学硕士学位论文 已有了t 比特级交换容量的路由器产品。业界对t 比特路由器的要求并不局限于 其t 级的交换容量，还要求它具备可扩展的转发性能和机制，提供较高的容错性 能，并能保证各种业务的服务质量( q u a l i t yo fs e r v i c e s ) 6 】州 8 i 。随着t 比特路由器 的不断演变和发展4 ，性能不断的完善，为互联网更进一步的发展提供了可能， 推动了网络服务供应商们提供更高质量的网络服务，以满足全球社会对网络个人 和企业业务不断增长的需求。 本文中对路由算法的研究将基于t 比特核心路由器的交换结构和交换技术。 下面介绍在t 比特路由器交换结构中常用的多维互联结构。 多维互联结构f 也称为多维交换结构1 是一种互联网络结构( i n t e r c o n n e c t i o n n e t w o r k ) ，互联网络结构多应用于大型多处理器系统、多个计算机间的互联，具 有很高的并行处理能力和扩展性。当互联网落的拓扑维度大于2 时，则称为“多 维互联网络”。互联网爆炸性的增长，导致了网络中交换的数据量的不断增多，单 平面的交换矩阵将很难满足核心骨干路由器的需求。多维交换结构系统能将业务 流分散于多个独立路由平面，具备很高的交换容量和良好冗余性；同时，具备多 维交换结构的核心路由器中支持软控制机制，使之具备更高的可控性，以保证不 同业务的服务需求。所以，多维交换结构在分组交换结构中的应用引起了业界的 兴趣。 对多维交换系统的研究主要集中在大学、研究机构和路由器产品公司，主要 的研究方向包括实现技术、体系结构、性能分析等。其中包括：j u n i p e rn e t w o r k s 卅 的t 6 4 0 平台采用矩阵互连技术( m a t r i xt e c h n o l o g y ) 来实现核心交换结构，其交换 节点间采用无源光互连设备1 9 】【1 4 】。矩阵互连技术是指由小型交换模块f 在本文中称 为交换单元或节点1 以一定的拓扑互连方式构建成一个易扩展的交换矩阵。a v i c i s y s t e m s 2 】的t s r 路由器的核心结构采用了三维交换矩阵技术。它的交换结构不同 于传统意义上的分布式交换结构，可实现真正的线性升级。其多维交换平台是完 全分布式和可扩展的，节点的连接方式采用3 维t o m s 拓扑( t o r u s 拓扑特性请见 1 2 节) ，系统最大交换容量可达5 6 t b p s 。图1 - 1 是t s r 路由器的3 维t o m s 结构 示意图，它是个2 4 2 4 的交换结构。2 0 0 2 年，b r i g h t l i n k n e t w o r k s 1 2 】使用4 元 n 方t o m s 实现的系统还能支持t d m 电路业务，代价是使用了更多的节点间连接。 图1 2 是一个4 元4 方结构，由4 个基本交换单元构成一个大单元，而4 个大单元 又构成一个更大的单元，依次往上叠加，n 为叠加的次数。交换单元的总数为4 “。 图中所示的拓扑构成一个2 5 6 2 5 6 的交换结构。p l u r i s 公司的t n r 系列t 比特路 由器采用了超立方结构( h y p e r c u b e ) ( 图1 3 ) ，这是一种特殊的m e s h 直接互连结 第一章t o r u s 交换结构概述 构。但由于每维只有2 个节点，实际上各节点也就没有位于网络边缘或中心的区 别，每一节点在每一维上只有一个邻居，故每节点共有栉个邻居，h y p e r c u b e 结构 也具有全网对称性，可称为2 元, t 方结构。 一 门 - f”- 灸 f 5 ， f 。 ；： 目 乃。： 莎c 彭： 图1 - 1 a v i c i 的4 3 2 t o r u s 结构 图1 - 2 b r i g h t l i n k 的4 元4 方t o r u s 结构 图1 - 32 兀4 维h y p e r c u b e 对一个交换结构的研究，主要包括拓扑结构、交换技术、流控制方式、路由 算法4 个方面。同时，当多维交换结构用于分组交换结构时，因为结构中节点数 量较多，对资源的调度变得复杂，所以调度算法的性能也会影响整个网络的能力。 在本文中，多维交换结构的框架结构包括多维互联网的拓扑、交换存储机制和流 控制方式，而其软件实现技术包括路由算法和调度算法。软件实现技术往往受到 系统框架结构的限制，本文所关注的重点是在相对确定的框架结构上找到合适的 路由策略，实现对不同优先等级业务的区分服务，使高优先等级业务占用优势资 源，保证业务的所需服务质量，同时能达到较高的系统交换性能。 下节将讨论多维交换结构的框架结构，包括拓扑特性、交换机制和流控方式。 电子科技大学硕士学位论文 1 2 多维交换结构的框架结构 1 2 1 多维交换结构的常见拓扑 多维交换结构的一个重要特性是其拓扑结构。拓扑的结构、维数和节点数量 与结构的性能密切相关。由于对多维交换结构拓扑的研究已进行了多年，很多文 献 1 3 【1 4 1 都详细做了研究，本节只做简单的介绍。 n 维m e s h 结构( 如图1 - 4 ) 和n 维t o m s 结构( 如图1 5 ) 都是常见多维互联 网络拓扑。对一n 维网络，设第i 维度上共有岛个节点，k i 2 ，f = 0 ，1 ，2 ，n 1 ， 显然： 全网共有岛x k i 胤2 x x k , 1 个节点； 节点x 可用h 维向量( j 柚d 谚s n - 2 白囊s n - 3 0 吐，s l d | j js o ) 来表示，其中 0s ( 7 i 0 ) s k f 4a 一个n 维网络，当且仅当其中任意两节点x 和y ，满足以下命题： x 与y 相邻，当且仅当对所有f - 0 ，1 ，2 ，z lf 希，有s i 俐= s i 劬， 其中s j = 5 j 俐1 。 则该n 维网络为一个n 维m e s h 。如果对所有维度i ，都有k i = k ，即每一维度 上的节点数都为k 个，则称该n 维m e s h 为k 元n 维m e s h 。 由以上定义可知，m e s h 网络中各节点由于处于网络中的位置不同，与其所相 邻的节点的个数也不同，为范围m ，2 n 区间上的某一整数。由此可知，m e s h 网络 结构不具有全网对称性。 一个n 维网络，当且仅当其中任意两节点x 和y ，满足以下命题： 工与y 相邻，当且仅当对所有f ，f 二o ，1 ，2 ，l - - 1 , f 习，有s i = s 。纠，其 中s i o ) = s j ( x ) 1m o dk i 。 如果对所有维度i ，都有岛= 咄，即每一维度上的节点数都为k 个，则称该h 维 t o m s 为k 元n 维t o r u s 。 从上可以看出，t o m s 结构的定义中由于有取模运算，因此比m e s h 结构有更 多的边。这些边通常称为w r a p a r o u n dc h a n n e l s ，其作用是使t o m s 结构中任意个 节点在每一个维度上均有两个相邻节点，一共有2 ，1 个邻居，没有中心或者边缘节 点的区别。因此，t o r u s 结构具有全网对称性。 第一章t o m s 交换结构概述 一髯 图1 - 4 4 3 x 3 m e s h 交换网络图1 - 54 x 3 x 2 t o m s 交换网络 交换结构的性能与其拓扑特性有密切的关系，如交换结构中节点对之间的平 均距离、所能提供的带宽大d 、连接度和对称性等都对性能有影响【3 5 】。本文中的 研究将基于t o r u s 交换结构。 1 2 2虫子l 路由交换技术 为了解决多跳网络中分组端到端的传输时延过大的问题，d a l l y 和s e i t z 提出 了虫孔路由交换存储策略【”】。在采用虫孔路由的网络结构中，进入网络的分组为 p a c k e t ，每个p a c k e t 在网络边缘节点处被切分为若干个f l i t ，而f l i t 的长度由系统参 数决定。 切分后的f l i t s 中，第一个n “为头n i t ( h f ，h e a df l i t ) ，其中包含路由信息和其 它控制信息，而其他f l i t 中只包含源分组中切分后的数据和少量的标示信息，为 b o d yf l i t ( b f l 。根据网络中的控制需要，有时也会将最后一个b f 称为t a i lf l i t ( t f ) ， 用于释放网络资源。在网络中进行路由时，所有的路由、控制过程仅针对h f 。当 h f 沿着一定的路径传送后，同个分组中的b f 就沿着h f 经过的路径，以隧道 方式( p i p e l i n e ) ，一个接着一个依次传送，类似于一个火车头带着整列火车前进，如 图1 5 。也可想象为一条蠕虫，其头部钻出一个孔，头部后面的部分沿着由头部钻 出的孔前进，同时虫的尾部又把这个孔填满，这也是虫孔路由名称的由来。 从虫孔路由的机制可以看出中间的f l i t 在传送时，是不允许被别的分组阻断的。 在传送时如果h f 被阻塞，则同一个分组中的其他f l i t 分别在其当前所在节点存储， 见图1 6 。这样在每个节点上的缓存只需要存储f l i t ，而不需要存储整个分组，这就 降低了对节点缓存器空间的要求。此外，虫孔路由还具有传输时延小，路由长度 对时延影响不大的优点。另外还有两种经常使用的交换技术是存储转发( s t o r ea n d f o r w a r d ) 1 6 1 和虚穿通( v i r t u a lc u tt h r o u g h ) b 7 技术。文献 9 1 对三种技术进行了比较， 电子科技大学硕士学位论文 发现采用虫孔路由技术传送分组的时延最短。由于虫孔路由不需要在中间节点提 供较大的存储容量，降低了硬件实现难度，同时保证了分组在多跳结构中的较小 时延，所以多维交换网络中多采用虫孔路由作为交换策略。我们在t o r u s 交换结构 中也采用虫孑l 路由。 1 2 3虚通道流控制机制 图1 - 6 虫孔路由示意图 交换结构的资源主要包括结构中节点的存储资源和物理链路带宽。在实际应 用中，多维交换结构的吞吐量限制在他们容量的2 0 一5 0 。一般来说，每个单 向物理通道对应一个缓存，即如果节点i 的缓存6 ，分配给分组a ，别的分组就不 能使用缓存6 i 对应的通道c ，直到分组a 释放抚。假设每个节点都在入端缓存， 且在每个输入队列处都有独立的缓存。在使用f l i t 级流控制的网络中，分组a 在占 有缓存b 的时候由于输出队列资源拥塞而被阻塞。在这种情况下，即使网络中有 别的分组，通道c j 也会被闲置。这种情况可以见如图1 7 所示，圆形框代表一个节 点，实箭头代表两个节点间的通道，长方形框代表f l i t 缓存，虚箭头代表前进的路 由方向。分组a 在持有缓存4 w ( 节点4 的西侧输入队列) 和6 n ( 节点6 的北侧输 入队列1 的时候被阻塞。由于分组a 占用了缓存3 w ，即使分组b 可以获得所需要 的所有物理通道( 3 w 到4 w ，4 w 到5 w ) 也不能转发。这是由于仅当分组同时拥 有物理通道和对应的缓存才有可能被转发。 第一章t o r u s 交换结构概述 裕j 埴 一锄艘漪赫 一 舒魏b 1 1 ，列驰燃存 图葑媸a lo l 增阳缀藩 空潮罐襻 牡点5 琴分数a i 塞 图1 7 物理通道空闲的时候分组a 后面的分组b 仍被阻塞 同时，由于一些自适应路由算法要求在相邻节点对问有多对通道( 请见第三 章) ，用物理线路来实现这样的交换结构是相当昂贵的，而且在大多数的情况下这 些通道的使用率不高。解决这些问题的一个办法就是使用多个虚通道( v c ，v i r t u a l c h a n n e l ) 复用一个物理通道，每个虚通道有自己的n i t 缓存。通过虚通道的使用， 一个物理结构可以划分成多个互不相连的逻辑结构，方便了白适应路由算法的设 计。 虚通道的优势可以体现在以下两个方面。一方面，通过提高网络的连接度可 以绕过网络中的拥塞热点和失效的节点。另一方面，虚通道可以为某些类的分组 保证通信带宽，例如，为支持一些系统相关的功能( 如调试，监视，诊断等) 保 留一些带宽是非常有意义的。 虚通道可以包括容纳某个分组的一个或多个f l i t 的缓存以及相应的状态信息。 几个虚通道可以共享同一个物理通道的带宽。通过为网络中的物理通道提供多个 对应的缓存，可以减弱缓存分配和通道分配间的耦合关系。如果阻塞的分组a 持 有一个与通道c i 相关的缓存b 加另外一个缓存b i ，仍然允许别的分组超过分组a 。 相对图1 - 6 中的网络，图1 - 8 给出了实现虚通道后的情形。分组a 在持有缓存4 w 2 和缓存6 n 2 被阻塞，因为4 w 1 可用，允许分组b 使用3 w 到4 w 的通道，从而 分组b 可以超过分组a 继续前进。 7 电子科技大学硕士学位论文 节点l 诲点2墨t i 3蓉j 曩4诤出5 图1 - 8 虚通道提供了额外的缓存以允许分组b 超越被阻塞的分组a 交换网络中的每个节点都包括一系列缓存和一个交换单元。对于个物理通 道配置多个输入缓存的情况，通常每个输入缓存对应一个虚通道。一个输入缓存 节点如图1 - 9 所示。传统网络通道对应的f l i t 缓存是按先进先出队列的方式来组织 的，见图1 - 9 ，这种结构严格限制了一个n i t 缓存只能包括某个分组的f l i t s ，如 果这个分组被阻塞，这条物理通道就闲置了，因为别的分组不能得到需要的缓存 资源以利用这条物理通道。 l 图1 - 9 ( a ) 传统节点的缓存组织形式 佟j ( b ) 采用虚通道流控制网络的缓存组织形式 使用虚通道流控制的网络把每个通道对应的f l i t 缓存按虚通道数分成了多组， 见图1 - 9 c o ) 。每组缓存的分配独立于其他组缓存的分配。这种分配的灵活性提高了 通道的使用率，相应地也提高了系统的吞吐量。一个被阻塞的分组，只会在路由 经过的节点上占用一个虚通道，而其他分组可以使用别的虚通道提高物理通道的 使用率。 第一章t o m s 交换结构概述 1 3可实现的多维交换结构一多虚网络t o m s 框架 本文的研究工作所使用的多维交换结构的框架参照了a v i c it s r 2 的设计方 案，该框架的最大特征在于构建了很多虚网络，且采用t o m s 拓扑，故称其为多虚 网络t o r u s 框架( m u l t i - v i r t u a ln e t w o r k t o r u sa r c h i t e c t u r e ，m v n ta r c h i t e c t u r e ) ，而基 于该框架的多维交换结构也就称为多虚网络t o r u s 结构。该框架可简要描述如下： 表1 - 1 多虚网络t o m s 框架简要描述 项目描述 拓扑采用3 维t o m s 结构；具可扩展性。 交换技术 采用虫孔路由的交换方式。 流控制采用使用虚通道的流控制方式。虚通道独占缓存，但共享物理通道资 源。虚通道组成虚网络( v i r t u a ln e t w o r k ，v n ) 。 本节中将主要说明多虚网络t o r u s 框架的物理实现方式。 多虚网络t o m s 的每个节点包括一个连接路由器与外链路的i ，o 端口，以及连 接交换结构内部物理通道的，采用输入缓存方式的交换模块。从拓扑的数学描述 上讲，该结构采用的是普通的3 维t o r u s 结构，因而每个节点连接了6 条物理通道。 当i o 端口带宽为2 5 g b s 时，每条物理通道的带宽为1 0 g b s ，即该结构具有4 倍 ( 1 0 2 5 ) 的内部提速。 多虚网络t o m s 的具体物理实现采用了所谓f o l d e dt o m s 的方式，即：将5 个 节点集成为1 个q u a d r a n t ，彼此互联为1 维t o m s 结构( 即一个环) ，作为三维t o m s 的一个维度；将4 个q u a d r a n t 集成在一个背板( b a c k p l a n e ) 上，但q u a d r