论文研究-基于商空间粒度计算方法的OSPF网络路由研究 .pdf

所需积分/C币:6 2019-08-17 15:37:09 589KB .PDF
收藏 收藏
举报

基于商空间粒度计算方法的OSPF网络路由研究,李旸,张铃,本文把人类在不同粒度层次上对现实世界的观察、抽象、求解方法应用到计算机网络的路由选择问题求解,探讨研究了利用商空间粒度计
山国科技论文在线 http:/www.papcr.cdu.cn 记X=X0,X中的元素用x表示。本文对各商空间P(x)=P2(y),于是有x=y X中的元素均排成序,记为 证毕。 X={x,…,x},i=1,…,k 32X1空间的矩阵表示法 现将X上的元素用分层结构表示: 对(X,E)的每个元素xn,作矩阵P,设x是由X1 设z∈X,现用k+1维整数表示如下: 中s个元素构成,则作sxy维矩阵P m()=f( (x,x),、(x2,x)∈E 设P:X→>x是自然投影,令P1(2)=x1,则令x的 d,其它 第i个坐标为:z,=t,即若z在中属于第t个元素,则m 令z,=t 于是X的拓扑结构可由{P,=1,…,m表示 对X定义边集合E0: e=(x,x)∈D台,(x,x)≥d1,其边以 )=(x),x)表示,得(X0,E) 8 对X定义边集合E1 (x,x)∈E1 X ∈x,1(xC,x)≥d2 且这条边有 e(x},x)={(x,1(x9),(x,1(x),vx 图2、拓扑结构的商空间粒度表示 ∈,x∈x},x∈x,(x,x)≥d2 e(x,x)是X中边的集合,标记为en 如图最大一个圆表X上的一元素x,它是由若干个 得商空间(X1,E1) X21上的点连接而成,当点x2,x之间有边相连,按定 般对X定义边集合F: 义存在X,上的点x2,x2,有边相连,所以路径 (x1,x)∈E分丑x∈x,x∈x,1(x,x)2d1 (x,x2)是由若干条X1的边构成 且这条边有 33求连通道路的分层递阶方法 )={(x,1(x9)…,p(x)=x)、(x,p(x9) 问题:给定x=(x0,x1,…,x),y=(y,y1…,yv),设 ,P(x)=x),x∈x,x∈x,(x,x)≥d1 x=y,x≠y,j<,求x,y在X中d连通路径。 算法(求路径): 标记为e,。 先将点x表成 得到商空间记为:(x1,E),=0,1,…,k-1。 x=(P0(x),P1(x),…,pP1(x),P1x→X 定义14:Yx,y∈,dl,称x,y是d连通的台在Xi=01…,k,X=X 中存在由x到y的权值≥d1的道路。 给定起点x=(x0,x2,…,xk),y=(y,y1,y2…,y),设 定理1: x=yk,故两点在(X1,E1)上是连通的,即两点在X Wx=(x,x,x2,…,x)y=(y,y1,y2,…,y)∈,1, 中是等价的。 x,y是d,连通的兮x=y1,其中 1)取P,求得由x1到y1的路径e(x1,y-),将 x=(x0,x1,…,xk),y=(yo,y,…,yk)是其分层表示。 求到的路径(节点序列,设有ak节点),将这a个节点按 证:设x=y,按定义x,y属于x的同一连通成份 顺序插入x,y之间,得由a+2个节点组成的序列。这 故得p1(x),P21(y)在(x=1,E1)上是d连通。另一方面, 序列中第2i点到第2i+1点之间有(dk型)边相连,第 P-2(x),P-2(y)在X2中是d1连通集,由保真原理得 P2(x)P2(y)在X2上是d连通。连续利用商空间的保2-1点与第2点还没有边相连,但其第k-1坐标相同, 故在(X2,E∠2)中两点是连通的,氵=1,…,a14+1。令 真原理得,x,y在Ⅹ上是d连通。 反之,设x在X上是d连通,显然在上有k←k-1,回第1步,求对应的点对的连通路径。 2)直到第2i-1点与第2i点的第0坐标相同为止,最 中国科技论文在线 http://www.paper.edu.cn 后得到的第0坐标序列即为所求的路径。 2=(5.9),x2=(7:.10} 例1:给定起点x=(x,x2…,x)和终点 共有三个元素,其对应的矩阵如下: y=(υ,1,y2…,y),设x=ν求连接x,y的路径 分(1(2,),(4,2) 1(6,3),(9,4)) 解:在(X1,Ek1)上求连接x,y(即连接x1,yk=1) 的路径,设为e(xk-1,y),端点为: 10((7,5),(10,7) x=(x,,xk21=x1,x2=(x2,…,x21=y-),将 1((8,6),(10,7) x,x2插入得(x,x,x2,y)。 由于x与x,x2与y的第k-1坐标是相同的,故可求 得商空间(X2,E2)(图示如下) 它们在(x2,E-2)上的连通路径……这样一直求下去直 到(X0,E0)上的连通路径为止。 例2:求图3网络的商粒度空间表示 图5、网络的商粒度空间拓扑3 10 5 R(3)等价类:x=(1,34,56,7:9,10) 只有一个元素其知阵如下 (2,1,1),(5.3.2)(3,2,1)(7,5,3) (5,3,2),(8,6,3)) 图3、网络的商粒度空闫拓扑1 得商空间(X3,E3)(图示如下): 如图3共有10个点记为{12,34,5,6,7,8,9,10 边上的权为:{1,3,5,10} (X0,E0) x→x,x3→>x,x6→>x0,x,x,x8,x0(共有10个元 图6、网络的商粒度空间拓扑4 素)。 各矩阵P是反对称的,即p=(a,b),则p=(b,a) R(10)等价类:得商集 节点分层编号 (3,4) 1=(1,1,1,1),2=(2,1,1,1)3=(3,2,1,1),4=(4,2,1,1) =(7,x6=(8,x2=(10) 5=(5,4,2,1),6=(6.3,2,1).7=(7,5,3,1),8=(8,6,4,1) 共有7个元素,其对应的矩阵如下: 9=(9,3,2,1),10=(10,7,3,1) 1(1,2) 4 1(6,9 例3:在图3中,求从点1到点10的路径。 解:将起点用分层表示:x=(1,1,1,1),y=(10,7,3,1) 4==b6=P=(1) 因为x3=y3所以从1到10最大的路径容量为d3=3 得商空间(X1,E1)(图示如下) 作起终点序列:((1,11,1),(10,7,3,1),因x3=y3=1, 故在矩阵P3中求路径 求x,y在P中的连通路径:(3,2,1)(7,5,3),现将它插 入x,y之间得: (1,1,1,1)3,2,1)(7,5,3),(10,7,3,1)→[3.7 由(1,1,1,1)、(3,2,1)和(7,5,3),(10,7,3),的第2个坐标 图4、网络的商粒度空间拓扑2 相同,故分别在P和P2中求各自的连通路径,由P2,P R(5)等价类:得商集X2={x2=(1,2,34) 得:(2,1),(4,2)和(7,5)(10,7),插入上述序列得 中国技论文在线 http://www.paper.edu.cn (1,1,1,1)、(2,1)、(4,2)、3,2,1),(7,5,3).(7,5).(10,7)、(10,7,3,1) 路由器 debug ip ospf events命令给出。 →[2.413.7],7.10 可靠性与传输时延:判断网络是否发生丢包现象,用 由(1,1,1,1),(2,1)、(4,2),(3,2,1)、(7,5,3),(7,5)、(10,7),PNG命令给出。 (10,731)第1个坐标是相同的,故分别在,P,P中求 带宽利用率:使用流量产生软件(SEND发包机)在 各自的连通路径得: 稳定发包的情况下,利用流量测试软件米检测网络带宽的 (1,2),(43),(7,7)、(10,10)插入上述序列得 利用率的问题。 (1,1,1,1)、(1,2)、(2,1)、4,2)4,3),(3,2,1)、(7,5,3)(7,7),(7,5),( 采用试验的网络拓扑结构如图1所示,具有21个路由 10,7).(10,10)、(10,7,3,1) 器节点。考虑到计算机的试验承载能力,所有链路设为相 →[1,2][2.4],4,3],[3.7],[7,7][710],[10,10] 同,粒度分层的依据属性为网络的拓扑结构。 最后得 试验对比如下图所示 (1,2,4,3,7,10). 例4:在图3中,求点1到点3的路径 11318151.203: cPP: SeNd Melle te 2t.0.0.s eree I es Serial/ fron 19 解:x=(1,1,1,1)y=(3,2,1,1,即其第2个坐标相同,所 w: MMJateney forged te rset 9216.2,140eFia115;eq2200 以按P2得路径[24 14:48:54.a7:osrF state is less shan INII 48154.7551 ostI Rrw helle from 112. 168.2.17 area B fron Serial/4 (1,1,1,1).(2,1)、4,2),(3,2,1,1)→(2.1)、(4,2)=[2,4] 2,1 由(1,1,1,1)、(2,1)(4,2)、3,2,1,1)第1个坐标相同,由 an s 14148154 822: (: 2 uav Cemmaicat ian te 5.5.5.5 oa serial/, state P,P得连通路径[,2]-(1,2,4,3]-(4,3)得 0148154. Krt osTi send ouD te 5.5.5.5 an ferial/t eeg wos to ept Hws 4154,y1 .5.5. 5 on serial1/a se wxl54B ep as (1,1,1,1)(1,2),(2,1),(4,2),(4,3),(3,2,1,1) 61q148154.y5oF paD fron 5.5.5.5 on Sewall seg wxzsot →[1,2][2,4]4,3 1唱::14,O Repet tat inn on, e ave th四丰 最后得路径:(1,2,4,3)。 6 14148154Y551 osrI Send DBD to 5.5.5.5 an Serial/ seu wxzs t ept Hs5 5. s.s. an sewall/a seg HesDs ape 注1:这样得到的路径只是分层最优,一般不是全局 len32mtu15ma出te上OCHw an614148:54.9%s:0sPF: Send DaD.65.5.5.5ni11/8当e2E85 最优。 1148155B7r org se p3D fron 5.5.5.5 on serial/ tea exes 这样求到的路径一般也不是唯一的,这是因为在各P it加.5,s⊥5aE111∥ ≤1414815.2D0P asl2 e wlth S.s.5.56ep1a11/8.自毫 . jULL PF5“真c种G: Preess s4.Hh..5,5n客P411A《P得 中即使是求最优路径其解也不是唯一的。 6 14149155.742 osPt Bew hlle fron 192. 148 2.173 area 0 fron Sewial1/2 2.168,2,154 注2:上面给岀按带宽进行聚类的网络商空间模型, 414:13.:r: Ind or I11 当然也可以按其它原则进行聚类(只要各等价连通的即 图7、不分层次网络与粒度化网络收敛情况 可),建立相应的商空间模型。 an 6 16:B?:55.275: OSPF: Send hello to 224.0.8.5 area 1 on Scriall/1. from 112 从上述的讨论可知,复杂网络中的路由可归结为商空 55.307: SPF: Hcv DiD from 192.168.2.161 on serial1/1 间的构造,而商空间中的结杓特征和属性函数为繁尔问题 15:5:30.and.pto19 1 seq @xd39B op 的描述提供了一种方法,从而使的这类问题的求解成为可 09:55.307: OSPF: NER Negotiation Done. We are the SLAVE nR≈in11/1 rr AxRFF nnt 能,本文提出的递归构造商粒度空间的路由算法,对此类 y52 55.315: osPF: Rcv DED from 192.168.2.10 ial/1 EKBEF 问题的描述具有一定的普适性。 g adR opt :09: 55.347: OSPF: Rcv DID from 192-168.2.161 on Seriall/1 seq OxBFB op 4算法仿真结果 OSPF: Exc hange Done with 192.168.2.161 on Seriall/1 我们设计使用了五台计算机来模拟试验环境。每个计 lan 6 16:09:55-347: OSPF: Synchron ized with 192.16 算机上都安装上 Winpcap4.0并且安装上21个 Cisco7200 PP-5-ADJCHG: Process 64, Nbr 192.168.2.161 on Serial1/1 系列的路由器镜象。配置好基本配置文件(I地址等)并 图8、粒度亿网终收敛情况 且把网终整个收敛 试验使用OSPF利用上述算法描述实现粒度拓扑分层 的模型。 1?#ping 122.1t 主要从以下几个方面来考虑试验对比网络的性能: Sending 5, 100-byte IcMP Echas to 192.168.2. 2, time out is Z seconds 收敛时间:路由器从开机到整个网络收敛所需要的时 uccess rate is 8g percent (4/5), round-trip min/aug/max =860/1036/1404 ns 间或者网络链路发生变化后整个网络收敛的时间。主要由 图9、不分层次网络丢包现象 中国技论文在线 http://www.paper.edu.cn C: \WINDOHS\ Xcmd. exe 需要关注研究的几个重要的方面在于利用商空问粒度计算 ucce 理论实现计算机网络路由表项的减少(路由汇总)以及链 Sending 5, 100-byt P Echp 3 to 192.168.2.2. timco 路状态通告的减少和快速收敛的特性: 1dK-52/144/252us 1.降低SPF计算频凇-因为详细的路由信息限制在 图10、粒度化网终无丢包现象 每个区域内,不必将所有的链路状态的变化都泛洪到每个 区域。只有受变化的路由器才需要运行SPF算法 点日黑三·.,【 DLAawinos n 2.减少路由表--.用粒度多区域时,区域内特定的 网络详细的路由条目被限制在区域内。这些路由就可以被 t8000数 1600b FrYr个r汇总成一条或多条汇总的粒度路由 3.降低LSU的开销--LSU可以包含多种LSA类型, 目1200bh 包括链路状态和汇总信息,可以不必向整个区域都发送关 sudo btt 于每个网络的LSU,目的是降低传输LSU到多个区域之间 4000bt 的开销。 178011712141021742321744214517472217485215022175152 4.采用粒度分层路由控制进出一个粒度空间区域的路 由信息类型,提高网络的收敛速度以及网络的路由效率。 四图 135轴Q9 参考文献 图11、不分层次网络带宽利用率 [!]张铃.张钹.模糊商空间理论(模糊粒度计算方法)卬J.软件学 日,H品盖·m■ 报,2003,14(4):770-776 [2]李旸陈万里,张铃,粒度计算的商闭包空间模型研究,[C].IEE 06EX358C, WCICA2006论文集2006年6月,p1430-1433 筧六届全球智能控制与自动化大会论文 [3] Yang Li, GuoDong Wu, GuoPin Zhang, The Research of smart Oie routing strategy based on Multi-agent systems, [C].IEEE 06EX1359,SPCA2006论文集2006年8月,p333-336, The first International Symposium on Pervasive Computing and Applications,IEEE会议论文 图12、粒度化网终带宽利用率 [41 Li Layuan. A routing algorithm for distributed optimal double computer networks, J Computer Science and 从试验数据可以看出,粒度分层网络的收敛时间为 0.1s,明显比不分层的OSPF15s要少,网终收敛性能有较 Technology, 1987, 2(2): 92-98 5 Tsai W T Control and management of large and dynamic networks 大的优化。 粒度分层网络的可靠性较不分层的网络有了较大的改 [D Dep eecs, UC Berkeley, CA, 1985 观,没有丢包现象,并且PING的时延也比较小 [6]Li Layuan. A new formal technique for communication protocol [C] specification. In: Proc IEEE INFOCOM, Ottawa, 1989, 74-81 粒度分层网络带宽利用率较不分层的网络也有了较大 的提高,从18 Kbit/s达到近30Kbts [7] Srikantakumar P RA learning model for routing in telephone networks. SIAM [J Control Optimization, 1982, 20(1): 34-55 试验结果明显体现出分层粒度路由的优势所在。 [8 Kamoun D, Klcinrock L. Stochastic performance cvaluation of hierarchical routing for large networks. [M Computer Networks 5小结 1979,3(5):337~353 本文探讨研究了对传统OSPF路由选择算法改进的粒 度路由方法,表述了粒度分层路由的研究思想,利用建模 与算法仿真给出了基于商空间理论的粒度分层路由的描述 及算法改进的试验结果 总结对OSPF路由选择算法改进思想,我们认为今后

...展开详情
试读 6P 论文研究-基于商空间粒度计算方法的OSPF网络路由研究 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840914 你的留言是对我莫大的支持
2019-08-17
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
最新推荐
论文研究-基于商空间粒度计算方法的OSPF网络路由研究 .pdf 6积分/C币 立即下载
1/6
论文研究-基于商空间粒度计算方法的OSPF网络路由研究 .pdf第1页
论文研究-基于商空间粒度计算方法的OSPF网络路由研究 .pdf第2页

试读结束, 可继续阅读

6积分/C币 立即下载 >