胖树网络路由算法的研究

胖树网络路由算法的研究

1不同网络链路算法的研究这是1985年提出的一个典型的多层面交换网络（m）。胖树结构具有等分带宽高、网络直径低、扩展性好等优点,因此广泛应用于超级计算系统和数据中心的互连网络,例如中国国家超算天津中心(NSCC-TJ)的“天河一号(Tianhe-1A)”、美国洛斯阿拉莫斯国家实验室(LANL)的“走鹃(Roadrunner)”、德国于利希研究中心(FZJ)的“于利希蓝色基因(Jugene)”和部署在中国国家超算广州中心(NSCC-GZ)的“天河二号(Tianhe-2)”等。胖树结构通常采用最短路由,即报文先从源处理节点上行到源和目的处理节点的最近公共祖先交换器(Switch),然后再从公共祖先交换器下行到目的处理节点。胖树结构的路径多样性体现在任意的源和目的处理节点间可能存在多个最近公共祖先交换器。各种胖树路由算法的差异主要体现于选择最近公共祖先交换器的依据和方法不同。现有胖树路由缺乏良好的对称性,即从任意处理节点A到B的路径所包含的链路不一定等于从B到A的路径所包含的链路。这不利于通过基于网络应用层的通信测试快速定位网络链路故障,因此链路故障的可诊断性较差。为此,本文考虑到网络链路故障的易诊断性需求,在不降低路由算法性能的前提下,针对胖树结构提出了一种新型路由算法BT-OSRM(Back-TrackObliviouSRoutingalgorithM)。2规定了运动路由及其算法在胖树拓扑结构研究方面,常用的胖树拓扑模型有两种,一种是k-aryn-tree模型,另一种是m-portn-tree模型。k-aryn-tree模型提出较早,其来源于k-aryn-flies多级交换网络,先前的大量胖树方面的研究都是基于该模型的。与k-aryn-tree模型相比,m-portn-tree模型定义所有交换器相连端口数目相同,这更合乎胖树结构的实际应用,因此最近在胖树方面的研究越来越多地采用该模型。在胖树确定性路由算法研究方面,MLID(MultipleLocalIDentifier)路由算法针对的是基于分布式查表路由的胖树,其特点是为每个处理节点分配多个本地标识LID(LocalIDentifier),具体算法由处理节点寻址、路径选择和转发表赋值等机制组成。DESTRO算法根据目的处理节点编号从源和目的处理节点的多个最近公共祖先交换器进行选择,其作者认为该算法比根据源处理节点编号选择最近公共祖先交换器的算法性能更优。OSRM(ObliviouSRoutingAlgorithM)算法综合考虑源和目的处理节点编号选择最近公共祖先交换器,已经被证明是确定性能比率(ObliviousPerformanceRatio)最高的路由算法之一。在胖树路由算法的实现方面,FIR对传统的区间路由IR(IntervalRouting)进行了扩展,在交换器的每个端口除了设置IR的区间首寄存器(First-Interval-Register)和区间尾寄存器(Last-Interval-Register)外,还额外地设置掩码寄存器(Mask-Register)和路由限制寄存器(Routing-Restrictions-Register),以避免路由死锁。不同于传统的源路由和分布式查表路由实现方法,FIR是一种较为新颖的胖树路由实现方法。3问题描述3.1交换器端口c,n-2,b本文采用m-portn-tree模型描述胖树结构,其描述方法与文献[4,5,10]相似。定义1FT(m,n)胖树模型可完整地描述为:(2)分级特点:FT(m,n)胖树共分为n级,分别编号为第0、1、…、n-1级。第0级包含的交换器数目为(m/2)n-1,其余各级包含的交换器数目均为2×(m/2)n-1。(3)交换器的标记:交换器标记为switch(cn-2,cn-3,…,c1,c0,l),其中l∈{0,1,…,n-1},表示该交换器在胖树中所在的级数;如果l=0或i≠n-2,则ci∈{0,1,…,(m/2)-1},否则如果l∈{1,2,…,n-1}或i=n-2,则ci∈{0,1,…,m-1},其中i∈{0,1,…,n-3,n-2}。(4)交换器端口标记:交换器switch(cn-2,cn-3,…,c1,c0,l)的第k个端口标记为switch(cn-2,cn-3,…,c1,c0,l)k,其中k∈{0,1,…,m-1}。(5)处理节点的标记:处理节点标记为node(pn-1,pn-2,…,p1,p0),其中如果j=n-1,则pj∈{0,1,…,m-1},否则如果j∈{0,1,…,n-2},则pj∈{0,1,…,(m/2)-1}。(6)交换器间连接规则:交换器端口switch(cn-2,cn-3,…,c1,c0,l)k与switch(c′n-2,c′n-3,…,c′1,c′0,l′)k′相连,当且仅当如下等式同时成立:①l′=l-1;②∀i(i≠n-l-1),则c′i=ci;③k′=cn-l-1;④k=c′n-l-1+m/2。(7)处理节点与交换器的连接规则:处理节点node(pn-1,pn-2,…,p1,p0)与交换器端口switch(cn-2,cn-3,…,c1,c0,l)k相连,当且仅当如下等式同时成立:①l=n-1;②∀i(i∈{0,1,…,n-3,n-2}),则ci=pi+1;③k=p0。图1所示为FT(4,3),即4-port3-tree胖树拓扑。其中,圆形和正方形分别代表处理节点和交换器,其标记只显示了括号中的关键信息。3.2基于路由路径的双向路径为了描述胖树原路返回路由问题,需要基于FT(m,n)的定义(定义1)进一步定义链路、路由路径、反向路由路径和原路返回路由。定义2(链路)处理节点与交换器的端口或者交换器端口之间的无向连接称为链路,链路标记为link〈nodei,switchportp〉或link〈switchports,switchportd〉,其中nodei表示处理节点,switchportp、switchports和switchportd表示不同的交换器端口。注意,本文定义的链路是无方向的,即link〈nodei,switchportp〉与link〈switchportp,nodei〉,以及link〈switchports,switchportd〉与link〈switchportd,switchports〉对链路的标记是等价的。定义3(路由路径)处理节点间传输数据时报文(网络层数据传输单元)所经过的链路序列。假设路由算法为R,nodes向noded传输数据时报文共经过n条链路,它们依次为link0、link1、…、linkn-1,则从nodes到noded的路由路径标记为path{R|nodes→noded},且path{R|nodes→noded}=link0→link1→…→linkn-1。可见,虽然链路是没有方向性的,但是路由路径是具有方向性的。通常,称路由路径的起始节点为源处理节点或源节点,路由路径的终止节点为目的处理节点或目的节点。定义4(反向路由路径)处理节点间反向传输数据时报文(网络层数据传输单元)所经过的链路序列。假设路由算法为R,从nodes到noded的路由路径为path{R|nodes→noded},则从nodes到noded的反向路由路径标记为Reverse(path{R|nodes→noded}),且Reverse(path{R|nodes→noded})=path{R|noded→nodes}。定义5(路由路径的反向)对路由路径所包含的链路序列取逆序的操作称为该路由路径的反向。假设路由算法为R,则从nodes到noded的路由路径path{R|nodes→noded}的反向标记为BackTrack(path{R|nodes→noded})。定义6(原路返回路由路径和算法)对于特定的拓扑结构T及其路由算法R而言,如果两个处理节点间的反向路由路径等于路由路径的反向,则称这两个处理节点间的路由路径是原路返回路由路径。如果任意两个处理节点间的路由路径都是原路返回路由路径,则称该路由算法R为拓扑结构T的原路返回路由算法。可见,对于特定的拓扑结构T中的两个处理节点nodes和noded,其路由路径由其路由算法R确定。如果Reverse(path{R|nodes→noded})=BackTrack(path{R|nodes→noded}),则nodes和noded间的路由路径为原路返回路由路径。如果T中的任意两节点nodes和noded间的路由路径都满足Reverse(path{R|nodes→noded})=BackTrack(path{R|nodes→noded}),则称R为T的原路返回路由算法。3.3原路返回路由算法定义7(胖树原路返回路由问题)对于任意的胖树FT(m,n),寻找其原路返回路由算法R。定义7所描述的问题就是本文算法所要解决的问题。本文没有针对任意拓扑结构研究其原路返回路由算法,这是因为在某些拓扑结构条件下,原路返回路由会造成死锁。以二维Torus网络为例,该拓扑结构通常采用维序路由DOR(DimensionOrderRouting)算法,而如果允许原路返回路由,则意味着网络的通道依赖图CGD(ChannelDependencyGraph)会出现环,从而导致死锁发生。4bt-osrm路由算法4.1b-osrm3算法的改进针对FT(m,n)胖树模型,文献已经提出了OSRM(包括OSRM2和OSRM3两种)路由算法。同时,当前主流交换器均采用高阶实现技术,其端口数通常为32、48或64。对于32端口的交换器而言,FT(32,2)和FT(32,3)最多可支持的处理节点数目分别为512和8192个;如果交换器的端口数为48,则FT(48,2)和FT(48,3)最多分别可支持1152和27648个处理节点;对于64端口的交换器而言,FT(64,2)和FT(64,3)最多可支持处理节点数目分别达到2048和65536个;而当前世界上运算性能最高的超级计算系统“天河二号”由16000个处理节点构成。所以,FT(m,2)和FT(m,3)几乎可涵盖所有实际应用的胖树结构。基于上述分析,本文对OSRM2和OSRM3算法进行了改进,形成了支持原路返回路由的新型算法BT-OSRM(Back-TrackOSRM)。BT-OSRM算法在为两处理节点确定路由路径时,不仅要利用OSRM算法所产生的路由路径,而且还需要比较处理节点间的大小关系。处理节点间的大小关系定义如下:4.2bt-osrm算法描述BT-OSRM路由算法就是依据源处理节点与目的处理节点大小关系选择路由路径,即如果源处理节点大于或等于目的处理节点,则直接依据OS-RM路由算法计算从源到目的处理节点间的路由路径;反之,首先依据OSRM路由算法计算从目的处理节点到源处理节点间的路由路径,再对该路由路径进行反向,则获得从源到目的处理节点间的路由路径。BT-OSRM算法的另一种描述如下所示:算法1BT-OSRM路由算法此外,如果改变BT-OSRM中节点大小比较结果与路由路径选择的对应关系,即如果源处理节点小于或等于目的处理节点,则直接依据OSRM路由算法计算从源到目的处理节点间的路由路径;反之,对依据OSRM路由算法计算从目的处理节点到源处理节点间的路由路径进行反向以获得从源到目的处理节点间的路由路径,该方法与BT-OSRM算法并无本质区别,因此也可视为BT-OS-RM算法。4.3bt-osrm2路由算法描述FT(m,2)结构共包含3×(m/2)个交换器和m2/2个处理节点。FT(m,2)中所有交换器和处理节点可分别标记为switch(c0,l)和node(p1,p0),其中l为交换器所在的级数。BT-OSRM2路由算法是BT-OSRM算法针对2级胖树FT(m,2)结构的具体化,其描述如下所示:算法2FT(m,2)的BT-OSRM2路由算法FT(m,3)结构共包含5×(m/2)2个交换器和m2个处理节点。在FT(m,3)结构中,FT(m,3)中所有交换器和处理节点可分别标记为switch(c1,c0,l)和node(p2,p1,p0),其中l为交换器所在的级数。BT-OSRM3路由算法是BT-OSRM算法针对3级胖树FT(m,3)结构的具体化,其描述如下所示:算法3FT(m,3)的BT-OSRM3路由算法5特征分析本节将理论分析BT-OSRM路由算法的一些特性,如原路返回、无死锁、负载均衡和最优化等。5.1b-osrm函数定理1BT-OSRM是FT(m,n)胖树拓扑的原路返回路由算法。证明假设nodei和nodej为FT(m,n)胖树中任意两个处理节点,根据节点大小关系共分为三种情况讨论:(1)如果,又因为,所以path{BT-OS-RM|nodej→nodei}=BackTrack(path{OSRM|nodei→nodej}),故Reverse(path{BT-OSRM|nodei→nodej})=BackTrack(path{OSRM|nodei→nodej})=BackTrack(path{BT-OSRM|nodei→nodej})成立。(2)如果nodei=nodej,此与的情况证明相同。(3)如果则,所以根据对情况(1)的证明结果,可知Reverse(path{BT-OSRM|nodej→nodei})=BackTrack(path{BT-OSRM|nodej→nodei})成立。所以,BackTrack(Reverse(path{BT-OSRM|nodej→nodei}))=BackTrack(BackTrack(path{BT-OSRM|nodej→nodei}))成立,即BackTrack(path{BT-OSRM|nodei→nodej})=path{BT-OSRM|nodej→nodei}=Reverse(path{BT-OSRM|nodei→nodej})成立。而且,由于nodei和nodej的任意性,所以根据本文定义6可知,BT-OSRM是FT(m,n)胖树拓扑的原路返回路由算法。故定理1得证,证毕。5.2b-osrm2路由算法对均匀流量模式的负载均衡定理2BT-OSRM路由算法是无死锁的。证明已知OSRM采用的是最短路径的UP-DOWN路由策略,即从源节点到目的节点通信时分为上行和下行两个阶段,在上行阶段时,先将数据从源处理节点传输到源和目的处理节点的最近公共祖先交换器;在下行阶段时,将数据从该最近公共祖先交换器传输到目的处理节点。尽管BT-OSRM对SROM选择最近公共祖先交换器的方法进行了修改,但并没有修改其TOP-DOWN路由策略,所以BT-OSRM路由算法是无死锁的。故定理2得证,证毕。对于路由算法的负载均衡问题,文献明确给出了多级交换网络中路由算法负载均衡定义。其定义指出:对于给定的胖树FT(m,n)及其路由算法R和流量模式F,如果胖树中属于同一级的各条单向链路承载的路由路径数目相等,则称路由算法R在流量模式F下是负载均衡的。定理3BT-OSRM2和BT-OSRM3路由算法对于均匀流量模式(UniformTrafficPattern)是负载均衡的。证明已知OSRM2和OSRM3路由算法对于均匀流量模式是负载均衡的,下面首先证明BT-OSRM2路由算法对于均匀流量模式是负载均衡的。假设nodei和nodej为FT(m,2)中的任意两个处理节点,则分析如下:(1)根据定理1可知,对于path{BT-OSRM|nodei→nodej}中的任意链路linkk,其一个方向承载了从nodei到nodej的路由路径,另一方向承载了从nodej到nodei的路由路径。所以,由nodei和nodej选取的任意性可知,FT(m,2)中任意链路的上行和下行方向所承载的路由路径数目必相等。(2)根据OSRM2算法定义可知,为nodei选择上行链路时只考虑了nodei和nodej在FT(m,2)中的位置信息,而与它们之间的编号的相对大小无任何关系。根据OSRM2路由算法是负载均衡的可知,BT-OSRM2路由算法在为任意nodei选择到nodej的上行链路也是均匀的。所以,综合(1)和(2)的分析可知,BT-OSRM2路由算法对于均匀流量模式是负载均衡的。同理,可以证明BT-OSRM3路由算法对于均匀流量模式是负载均衡的。故定理3得证,证毕。5.4生成n,n2-采用bt-osr2路由,a在特征交换器,有多个d确定性能比率反映了路由算法对不同流量模式的适应能力,有关性能比率、确定性能比率、最优化路由算法的定义详见文献。为方便起见,本文沿用文献对确定性能比率的标记方法,即路由算法R的确定性能比率为PRRF(R)。定理4如果为整数,则;如果m/2为整数,则PRRF(BT-OSRM3)=m/2。证明首先证明PRRF(BT-OSRM2)的相关结论。为此,需要对BT-OSRM2和OSRM2两种路由算法进行对比。令,则OSRM2路由算法将每个级数为1的交换器所连接的m/2个处理节点分为Z组(group)。具体而言,假设0≤i≤m-1且0≤j≤Z-1,则switch(i,1)的groupj包括的节点构成的集合为{node(i,j*Z),node(i,j*Z+1),…,node(i,j*Z+Z-1)}。假设nodes和noded为FT(m,2)中的任意两个处理节点,可分两种情况讨论。(1)如果或者nodes=noded,则path{BT-OSRM2|nodes→noded}=path{OSRM2|nodes→noded},所以该情况下由OSRM2修改为BT-OSRM2路由方式并不影响其确定性能比率的计算。(2)如果,则path{BT-OSRM2|nodes→noded}=BackTrack(path{OSRM2|noded→nodes})。(2.1)如果从nodes到noded的路由路径只经过switch(i,1)一级交换,即nodes和noded连接同一交换器,则BackTrack(path{OSRM2|noded→nodes})=path{OSRM2|nodes→noded},该情况下由OSRM2修改为BT-OSRM2路由方式也并不影响其确定性能比率的计算。(2.2)如果从nodes到noded的路由路径需要经过switch(i,1)和switch(k,0)两级交换(0≤k≤m/2-1),即nodes和noded连接在不同交换器,则假设nodes=node(i1,j1*Z+x)且noded=node(i2,j2*Z+y),其中0≤i1、i2≤m-1,0≤j1、j2≤Z-1,0≤x、y≤Z-1。(2.2.1)如果nodes和noded属于相同分组,即j1=j2,则path{OSRM2|nodes→noded}和path{OSRM2|noded→nodes}经过同一顶层交换器switch(j1,0),则path{BT-OSRM2|nodes→noded}=BackTrack(path{OSRM2|noded→nodes})=path{OSRM2|nodes→noded},该情况下由OSRM2修改为BT-OSRM2路由方式也并不影响其确定性能比率的计算。推论1BT-OSRM2和BT-OSRM3路由算法是最优(Optimal)的。证明假设R2和R3分别是FT(m,2)和FT(m,3)拓扑结构的路由算法,且PRRF(R2)和PRRF(R3)分别是R2和R3的确定性能比率。根据文献引理12(Lemma12)可知,路由算法R2和R3的确定性能比率取值范围分别为和PRRF(R3)≥m/2。而定理4已经证明了BT-OSRM2和BT-OSRM3路由算法的确定性能比率分别为和m/2,所以BT-OSRM2和BT-OSRM3路由算法是最优的。故推论1得证,证毕。6研究工作展望BT-OSRM路由算法是对OSRM路由算法的改进算法,该新型路由算法不仅继承了OSRM算法性能最优和负载均衡等优点,而且通过简单的定义和利用处理节点间的大小关系,使得任意处理节点对间的往返路径所包含的网络链路相同,从而提高了网络故障链路的易诊断性。BT-OSRM路由算法的实现也较为简单———如果胖树网络采用源路由,则在静态生成系统的路由表时直接实现即可;如果胖树网络实现采用分布式查表路由,则需要增加节点编号比较的机制并修改查表流程。基于本文研究基础,未来研究工作可在如下三个方面展开:(1)深入研究原路返回路由算法对网络链路故障定位的影响;(2)进一步为胖树网络提出更通用的原路返回路由算法;(3)考虑其它拓扑结构中的原路返回路由问题及其可解性。(1)基本构成:FT(m,n)胖树由(2n-1)×(m/2)n-1个m端口的交换器和m×(m/2)n-1个处理节点构成。可见,如果path{R|nodes→noded}=link0→link1→…→linkn-1,则BackTrack(path{R|nodes→noded})=linkn-1→linkn-2→…→link0。5.3节点面图2所示为FT(8,2)胖树结构,OSRM路由算法将其32个处理节点分为两组,即group0和group1。顶层的四个交换器分别负责的路由路径(表示从groupi中的处理节点到groupj中的处理节点)。定理4证明过程中的各种情况可举例如下:(1)path{BT-OSRM2|node(6,0)→node(1,0)}=path{OSRM2|node(6,0)→node(1,0)};(2.1)path{BT-OSRM2|node(1,0)→node(1,2)}=path{OSRM2|node(1,0)→node(1,2)};(2.2.1)path{BT-OSRM2|node(1,0)→node(6,1)}=path{OSRM2|node(1,0)→node(6,1)};(2.2.2)path{BT-OSRM2|node(1,0)→node(