技术中心
 
 

基于人工蜘蛛网的路由算法

   日期:2006-05-01     作者:管理员    

  在自然界中,蜘蛛大都是靠结网捕食为生。绝大多数蜘蛛网都可以近似看作是一个中心对称的结构。它包括由中心点辐射向外的丝线,称为辐(spoke),用来作为蛛网的框架;称辐上的螺旋线为弦spiral。

    蜘蛛主要是通过感受蛛网的震动来判断是否有猎物,以及猎物在网上的位置。蛛网中的每一条辐会把震动传导到中心点,所以蜘蛛通常会守在中心点等待信息。但有时候蜘蛛会隐藏在其他位置,这时,蜘蛛会从中心点引出一根丝线,并将一只腿放在线上,以便随时掌握蛛网的信息。这根线是传导蛛网震动的通讯信号线。蜘蛛通过这根传导线会确定哪根辐传导了震动信息,并很快通过辐到达猎物跟前。
           
    受蜘蛛织网捕食行为的启发,尝试将原本由各个节点无序互联而成的物理网络拓扑结构转化成逻辑上中心点对称的类似蜘蛛网的结构。由于对网络进行了重新规划,脱离了不规则物理拓扑的束缚,同时对每个点赋予了坐标,而且由于从源节点到目的点的寻路引入了坐标定位机制,使

得重路由区域的划分和区域内两点之间路径的计算变得简单。本文正是基于蛛网,提出了一种新的路由算法。
  
重路由区域的划分
  
    为了解决流量工程中的快速重路由问题。获得重路由的最优路径,就需要计算蛛网任意两点之间的路径,有必要对蛛网各条辐、弦进行编号。辐、弦的编号应该具有方向性。给定蛛网中两条辐x1和x2,则这两条辐把蛛网划分成两个互补的区域,分别称为正区域(x1到x2的顺时针区域)和负区域(x1到x2的逆时针区域)。
  
    在正、负区域的基础上,给出重路由区域的定义:重路由区域A(x1,x2,h)是蛛网内由两条辐x1和x2所夹区域,包括辐x1、x2以及它们之间的所有辐、弦。由于蛛网的结构特性,重路由区域同时存在互补的两个区域:从x1到x2的正区域(h=1)和负区域(h=-1)。
  
    路由区域的确定关键是确定辐x1、x2,即路由区域的边界,如果对于一个业务繁忙的网络区域,我们应修改x1和x2,使得区域修改或者扩展。无论是路由区域的修改还是扩展,都应该保证被选择的路径完全在区域内部。确定了区域边界之后,蛛网自然的被分割成两个互补的区域,重路由首先面临的是选择哪个区域的问题。可以依据区域内的负载轻重,选择相对空闲区域;也可以依据区域的大小,就是包含的辐弦数目的多少,尽量选择小区域。因为如果将重路由区域限制在较小的区域内有利于精确的考虑区域内网络的负载等状态,而且使得计算重路由路径更加容易。
  
    区域划分之后,边界辐称为骨干路径,区域内其它路径称为枝叶路径,下面CRASW(Centralized Reroute Algorithm based-on Spider-Web)算法就能获得区域内到达目的节点的所有路径。
  
区域内路由路径的计算
  
    骨干路径在重路由区域确定的同时也被确定,即区域的边界辐。重点在于得到区域内的枝叶路径。这里基于重路由区域A的坐标矩阵Sa,在区域内构造一棵以目的节点为根的树Tree,通过这棵树找到枝叶路径集合Pt。

    下面对于树中的三类节点做如下定义:第一类是station-point,它代表网络中节点(路由器),用圆圈表示,圆圈内部标记节点的编号;第二类是spoke-point,代表蛛网中的辐,用矩形方框表示,方框内部标记辐编号;第三类是spiral-point,代表蛛网中的弦路,用菱形方框表示,方框内部标记弦路编号。
  
    对这三类点的孩子节点的规定分别是:station-point的孩子为spoke-point或者spiral-point,表示这个station-point点代表节点在蛛网中位于的辐或者弦路编号,一个station-point可以有多个孩子,表示处于多条辐或者弦的交汇处;spoke-point的儿子为station-point,可以有多个,表示这个辐所包含的节点集合,但不包括它的祖先节点;spiral-point的儿子为station-point,可以有多个,表示这个弦路包含的节点集合,但不包括它的祖先节点。
  
    构造路径树过程就是不断的添加孩子节点的过程,下面给出其中需要用到的规则:首先是,一个station点加入到树T中后,随即在它所在的辐、弦集合中删除自己;其次是,





















spoke或者spiral点的孩子只能在自己的辐路或者弦路集合中查找,若集合由于规则1变为空,则不添加;接着是,station点的祖先不能成为此点的孩子;最后是,若所有的辐、弦路都变为空集,则构造树T结束。
  
    构造路径树的算法第一步要初始化树T为空,添加目的点t到树T,作为根节点;然后要依据三类点孩子的规定,执行上述4条规则,给每一层节点添加孩子;最后,若路径树T构造完毕,删除最低层所有叶子节点,将具有相同编号的station-point用虚线连起来。至此,路径树的构造完毕。从路径树中提取路径的基本思想是station-point执行求助祖父、兄弟、孙子节点的操作,直到到达根为止。

举例说明CRASW算法
                      
    蛛网的重路由区域的坐标矩阵为hub:<

;x1,0,0,0> <x2,0,0,0> ;c1:<x2,1,y2,1>;c2:<x2,2,y1,2>;c3:<x1,1,y2,0>;c4:<x1,2,y1,0>;c5:<0,0,y1,1>;辐x1:{c3,c4};辐x2:{c1,c2};弦y1:{c4,c5,c2};弦y2:{c3,c1}。求所有节点到达c2的路径。
  
    首先添加station-point c2;然后,依据c2的坐标,给c2添加孩子x2和y1,删除辐x2与弦路y1中的元素c2;接着,给x2添加孩子c1,给y1添加孩子c4、c5;依据c1、c4、c5的坐标给他们添加孩子c1孩子为y2,在弦y2中删除c1;c4孩子为x1,在辐x1中删除c4,c5不添加;接着再给y2添加孩子c3,给x1添加孩子c3;最后给c3添加孩子x1、y2,但是由于x1、y2集合都已经为空,故算法结束,将c3的孩子删除,并将两个c3用虚线连接起来。
  
    在路径树的基础之上采用广度优先遍历,从根root开始,目的是搜索出所有station点到达root可以经过得路径集合。搜索过程中将station-point作为基本单位,spoke-point以及spiral-point只是作为station-point之间的桥梁,逐层搜索每一个station-point到达根的上行、下行以及横行路径。
  
    路径搜索算法是先从上到下依次搜索各层station-point到达root得上行路径,搜索的办法是获得到达祖父station-point的路径,然后将这部分路径与祖父station-point到达root的路径进行合并。然后,在搜索完最后一层station-point之后,从下到上搜索各层station-point的下行路径,即到达孙子station-point的路径与孙子station-point到达root的路径合并。最后,在搜索完所有station-point的上行,下行路径后,再搜索各层station-point的横行路径,即到达兄弟station-point的路径与兄弟station-point到达root路径的合并。最后得到的搜索结果是:c1到c2的路径为c1-x2-c2(上行),c1-y2-c3-x1-c4-y1-c2(下行);c3到c2的路径为c3-y2-c1-x2-c2(上行),c3-x1-c4-y1-c2(下行);c4到c2的路径为c4-y1-c2(上行),c4-x1-c3-y2-c1-x2-c2(下行);c5到c2的路径为c5-y1-c2(上行),c5-y1-c4-x1-c3-y2-c1-x2-c2(横行)。
  
路由实验比较
 
    我们用CRASW来实现重路由备份路径的计算。主路径上其他节点(PSL)向主路径的边缘节点提出路径保护需求,边缘节点将计算结果返回给PSL,PSL依此建立备份路径。依靠边缘节点集中计算符合MPLS网络将各项功能推到网络边缘去完成的原则。在基于节点失效的多业务保护模式下同经典的最短路由算法(SPF)进行比较,失效类型是节点失效(节点1),隐含着是多条链路失效;保护的业务不是一个,即主路径不是一条。有三个业务T1、T2和T3,他们路由的主路径分别是:9—4—hub—11—1—6;8—3&













#8212;hub—11—1—6;7—2—1—5—10。
             
    在正常情况下三个业务的路由走向。用黄绿蓝三种颜色表示。考虑节点1失效情况下利用SPF算法计算出的重路由路径,可以看出业务1、2都选择了11—hub—2—7—6作为重路由路径,业务3选择了2—hub—5作为重路由路径。

    对于业务T3,PSL是2,PML是5。重路由区域的边界x1是辐hub—2—7,边界x2是幅hub—5—10,由于负区域失效链路很多,所以选择正区域。重路由路径优先选择了不通过hub的路径:2—3—4—5。对于业务1和2,PSL是11,PML是6。P

SL是辐分点,则依据PSL修改机制令hub为新的PSL。PSL和PML二者在同一个辐上,依据重路由区域的扩展机制,选择辐x1=hub—2—7,x2=hub—5—10,由于PML只在负区域内,故选择负区域作为重路由路径。计算得到重路由路径,业务1选择了hub—2—7—6;业务2选择了hub—5—10—6。
 
    显然在SPF重路由算法中业务1,2选择了相同的重路由路径,业务1,2,3都选择了通过节点hub。而蛛网算法选择中,首先正确的选择了重路由区域,然后在区域内又正确选择了重路由路径。使得业务1,2重路由路径没有重合,业务3选择了跳数相对较多的2—3—4—5。因为hub点作为PSL有意识的将各个业务的重路由分开,以免造成新的拥塞,并且蛛网算法优先选择通过弦路的路径,所以业务3没有通过hub点。在实验中SPF算法会造成hub—2链路发生拥塞,说明节点失效下不恰当的路由可能带来新的失效。
 






 
  
  
  
  
 
更多>同类技术
 
全年征稿 / 资讯合作
 
推荐图文
推荐技术
可能喜欢