基于拓撲更新算法的向量網絡連接設計

薛念，常珞

（河南醫學高等專科學校河南鄭州451191）

基于拓撲更新算法的向量網絡連接設計

薛念，常珞

（河南醫學高等專科學校河南鄭州451191）

針對向量網絡數據的交換設備盡可能不實現信令處理的問題，通過計算和遍歷網絡拓撲生成樹的方法對網絡拓撲進行檢測和更新，提出了一種基于拓撲更新策略的向量網的連接設計。采用組長探測、節點響應的向量網拓撲發現方法和簡單交換機網絡的拓撲發現方法進行拓撲收集。實證案例分析表明：信源設備遍歷向量網中的17個分量地址，1 s后發送維護信令包對拓撲進行檢測。在遍歷過程中，終端生成葉子節點表Leaf-node和包含虛擬鏈路的非葉子節點表v-node準確地定位向量網的連接效果，從而有效地提供多路徑向量網通信。

向量網；拓撲更新；生成樹；遍歷；網絡連接

隨著網絡技術的發展，網絡規模的不斷擴大和網絡結構的日益復雜［1］，同時，IP網環境下多路徑傳輸的局限性，提供多路徑通信的效果有限［2-3］。因此，性能提升受到限制準確描繪網絡的拓撲結構對網絡的管理、規劃、以及網絡故障的排查具有非常重要的意義［4］。然而網絡拓撲是不斷變化的，比如增加或減少一臺路由設備、修改一條路由設備的配置信息都會導致拓撲結構的變化［5］，為了能夠如實反映網絡真實的拓撲結構，必須及時發現拓撲結構的變化，并對已有的拓撲結構進行更新［6］。目前向量網有關拓撲的研究工作大部分集中在拓撲發現的算法上，網絡拓撲更新方面的研究還不夠成熟［7］。

文中提出了一種基于拓撲更新策略的向量網絡連接，采用組長探測、節點響應的向量網拓撲發現方法和簡單交換機網絡的拓撲，結合拓撲更新中的檢測父子關系和虛擬路徑關系的拓撲進行拓撲收集，最后終端系統通過對網絡拓撲的生成樹進行網絡連接的定位，并對檢測的結果進行分析以實現拓撲數據的向量網絡更新。

1　向量網體系

1.1向量網的地址編碼方法

向量地址是通過向量連接和向量交換的方式，用一種新方法編址得到一種新的交換地址，并利用向量網絡端口標記示意圖來表述向量網的地址編碼方法［8］。如圖1所示。

圖1　向量網絡端口標記示意圖

從A到J是網絡的節點設備，每一個節點設備的輸入輸出端口號都從數字1開始編號，定義為端口號。向量地址利用端口號編碼，描述了數據從信源設備到信宿設備的傳送路徑。這個傳送的通信路徑是由端口號組成的節點序列，端口號指的是路徑中每一個轉發設備的輸出端的端口號，每個電子設備在序列中都有其對應的端口號。序列中的端口號是一個知道目的地的方向標，引導數據包準確無誤的發送給信宿設備，向量地址AV（Vector Address）以端口號為編碼基礎，把端口號稱為分量地址CV（Component Vector）［9］。

信源設備A向信宿設備C發送向量網數據包，序列的第一個分量地址是信源設A及其輸出端口號A1；第二個分量地址是第一個轉發設備G及其輸出端口號G2；第三個分量地址是第二個轉發設備I及其輸出端口號I3；最后一個分量地址則是最后一個轉發設備J及其輸出端口號J2。得到的序列｛A1，G2，I3，J2｝就是向量網絡地址編碼結果，即信源設備A向信宿設備B傳輸數據的向量網絡地址，簡化表示為｛1，2，3，2｝，為了更有效表示向量地址，需要進一步表示成二進制。

1.2組長探測和節點響應

向量網中的C類交換機（包括以太網等效交換機等）和B類交換機（包括硬件交換機等）具有解讀信令及向上一節點返回反饋信令包的功能，在探測這兩種類型交換機組成的網絡拓撲結構時，采用組長主動節點配合的向量網拓撲發現方法NALP（NodeAnswering on Leader Probing）［10］。組長發送探測信令包，節點收到探測包后判斷此數據包是否為關于本節點的探測信令包，若不是則節點切掉轉發出口的分量地址，轉發探測包；若是本節點的探測信令包，節點則進行簡單的信令添加操作，將信令發回探測端。組長根據返回的信令整合分析信息，以便獲取網絡拓撲，實現網絡路由。

1.3向量網的地址交換

向量網中采用向量交換實線地址交換［11］，即數據包攜帶了向量地址到達了交換設備某個輸入端口，首先交換設備根據自己端口號數目確定需檢查的分量地址長度，接著交換機從向量地址比特流中提取并分析向量地址，根據分析結果把該數據包發送到分量地址所指定的輸出端口，并把該分量地址從向量地址中刪除，即傳送出去的數據包向量地址少一個分量地址。數據從每個端口輸出到達信宿設備，完成整個數據傳輸過程。

向量網絡是一種分組交換網，傳輸的數據以數據包的形式出現。數據包的格式框架如下［12］：Head表示數據包頭的固定部分的信息集合，包括數據包格式的版本號、傳輸優先級等信息；VA是從信源到信宿的向量地址；Data為數據包承載的數據信息。轉發程序運行在向量傳送面的每個向量交換機中，當向量交換機的輸入端口收到一個數據包時，該轉發程序就執行一次，實現一次交換操作，它只有3步基本操作：

Step1：從數據包的向量地址VA中分離出當前轉發操作的輸出端口號，即向量地址VA的第一個分量（記為To）；

Step2：修改數據包把To從數據包中刪除；

Step3：把修改后的數據包發到輸出端口To，直到To為空。

2　拓撲更新算法

2.1拓撲更新生成樹

網絡鏈斷路引起拓撲變化在于改變了原有拓撲的邊結構，因此可以通過驗證邊的方法進行檢測網絡連接效果［13］。鏈路拓撲的檢測實際上為拓撲圖中邊的檢測，即利用向量網的檢測父子關系和虛擬路徑關系的拓撲發現方法可收集拓撲模型的拓撲信息，假設拓撲結構已被保存到拓撲信息表（ElemInfoTGa-temp）中，探測端利用Prim算法和拓撲信息可將拓撲圖生成唯一的生成樹，并把生成樹信息保存到生成樹信息表（NodeTreeInfo）中，使得拓撲圖變成樹狀結構。另外，各條虛擬路徑信息包括路徑連接的父子節點身份標識和端口信息被保存到擴展路徑表（RepeatLinkList）中。

在生成樹的結構中，對每一個節點的遍歷實際上就等同于對每一條邊進行遍歷［14］。探測組長利用生成樹信息表、擴展路徑信息表及樹的順序遍歷算法構造拓撲維護包，由根節點開始，按照由父節點到子節點、由節點的低端口號到高端口號的順序和檢測包含虛擬鏈路的節點時優先遍歷虛擬鏈路的順序來遍歷拓撲。如此可以將樹中全部邊遍歷到，若探測端發出的維護包能回到探測端，則認為鏈路狀態良好。在生成遍歷路徑的過程中，樹的葉子節點被存放葉子節點表（Leaf-node）中，包含虛擬路徑的非葉子節點被存放含虛擬路徑的非葉子節點表v-node，Leaf-node和v-node為先進后出的數據結構［15］。

生成向量網維護信令需要用到生成樹信息表Node Tree Info、拓撲信息表ElemInfoTGa-temp，NodeTreeInfo主要存放拓撲中各節點在樹模型中的父子關系。生成樹信息表有［16］：backport，number，bits，parentnumber，vlink，childinfo。其中，backport是由當前節點返回到父節點的返回端口號；number存放當前節點在拓撲信息表TGa-temp中的下標號；bits是該節點對應向量交換機的分量地址位數；parentnumbe存放該節點的父節點在拓撲信息表TGa-temp中的下標號；vlink保存該節點的虛擬路徑信息；Childinfo保存該節點的子節點信息。

2.2拓撲更新算法

本文提出的拓撲更新算法是基于向量網自身的數據轉發特性，因此不需要任何特殊額外的協議支持，具有通用性。具體算法如下：

Step1：從Leafnode取出第一個葉子節點，向該節點維護信令包。若A沒有收到返回包，執行Step3，若收到返回包，則執行Step2；

Step2：取出Leafnode的下一個節點，向該節點發送維護信令包，若A沒有收到返回包，執行Step4，若收到返回包，繼續執行Step2，當Leafnode為空時，執行Step5；

Step3：依次向該路徑上的節點發送維護信令，更新拓撲信息表TGa-temp拓撲信息，直到確定斷開鏈路；

Step4：計算當前路徑與前一條路徑的重合鏈路數，依次向路徑上非重合的節點發送維護信令，更新拓撲信息表TGa-temp拓撲信息，當收不到返回信令包時，確定斷開鏈路；

Step5：依次向v-node中的節點發送維護信令包，檢測節點的各條虛擬路徑，直到收不到返回包，確定斷開鏈路，當vnode為空時，無鏈路斷開，完成連接。

3　實證分析

3.1向量網的拓撲探測

由于向量網中的A類交換機只具備基本的數據轉發功能，拓撲探測時采取最小代價分層的掃描法進行探測。假設通過NALP方法已經探測到終端A通過某條鏈路與s1節點設備連接，s1是B類交換機，進一步探測其端口1011時無回應，則假設s2是A類交換機，節點信息未知且不具備響應組長功能。在這種情況下探測端A通過猜測s2的分量地址位數，并且依次掃描端口號的方法進行探測，只有當猜測s2的分量地址位數為3、返回端口為001時，A才能收到符號要求的返回包，并獲知的返回端口號和端口號位數。則向量地址采用二進制編碼方式進行轉發：｛1，2，3，2｝轉發為11001110，具體的如表數據包變換如表1所示。

表1　數據包的變化

3.2向量網的拓撲更新連接

利用向量網的檢測父子關系和虛擬路徑關系的拓撲發現方法可收集終端A的拓撲信息。a節點與b、c節點為父子關系，d節點與h節點為父子關系，b節點與d、e節點為父子關系；在生成生成樹過程中，節點a，b，e，f，c之間的路徑可形成環路，其中至少一條路徑會被標記成虛擬路徑。如圖2所示。

圖2　終端A的拓撲模型

如圖2所示，鏈路節點遍歷虛擬鏈路來實現遍歷拓撲，鏈路信令包的經由節點順序為a，b，d，h，d，b，e，b，e，f，c，f，i，f，e，b，a，c，g，c，a。同時，結合圖1中的向量網絡端口，探測端A根據拓撲信息及生成樹信息生成維護信令包由A的唯一端口發送出去。分量地址為：3，0，1，0，2，3，1，1，2，2，0，1，1，3，0，5，0。信源設備A遍歷整個拓撲的向量地址，其由17個分量地址：011，0000，001，000，010，0011，001，0001，0010，010，000，001，001，011，000，0101，000組成，當終端發送出帶有如上向量地址的維護向量包后，會依次遍歷各條鏈路，若沒有鏈路斷開信令包最后回到終端A，1s后終端A繼續發送維護信令包對拓撲進行檢測。檢測遍歷路徑如表2所示。

表2　各節點之間的路徑集合

在生成遍歷路徑的過程中，終端A生成葉子節點表Leaf-node和包含虛擬鏈路的非葉子節點表v-node。其中，存放的節點如表2的第二列所示，且兩者為先進后出的數據結構類型，第三列為根節點A到表中各節點的路徑集合。

若由終端B進拓撲檢測，其在檢測過程中生成的生成樹模型如圖3左邊的模型所示，B為根節點，第二個模型為終端A生成的生成樹模型。終端B生成的葉子節點表Leaf-nodeb和包含虛擬鏈路的非葉子節點表v-node-b存放的節點分別為｛s5，A，s1，s4｝和｛s3，s2｝中。根據先進后出的存取原則，B在定位鏈路時，首先取出葉子節點集合中的節點4生成路徑B，3，4的信令包并發送，判斷該條路徑有故障后，只需在向節點3發送一次維護信令就可以判斷出節點3與節點4之間的鏈路斷開，所以相對于終端A，終端B會以更少的時間定位出斷開鏈路的位置。

比較圖3中左右兩邊由終端B和終端A生成的生成樹模型，對于同一個網絡模型，兩個終端遍歷拓撲的順序不同，標記的虛擬鏈路也不同，同時兩端生成的葉子節點表和包含虛擬鏈路的非葉子節點表中存放的節點順序也不同，所以檢測和定位不同的斷開鏈路時，兩個終端在效率上具有一定的互補性。那么實際在維護網絡拓撲時，終端B可協助終端A同時對拓撲進行檢測，若終端B提前定位到網絡故障位置，鏈路斷開信息，并向A發送網絡包，A根據B發來的斷開鏈路信息，停止檢測并A更新拓撲，連接結束。

4　結論

文中提出了一種基于拓撲更新策略的向量網的連接設計，該方法采用組長探測、節點響應的向量網拓撲發現方法和簡單交換機網絡的拓撲，結合拓撲更新中的檢測父子關系和虛擬路徑關系的拓撲進行拓撲收集，并設計了一種向量網拓撲獲取更新系統來檢測拓撲鏈路連接情況。通過實證案例表明：依據更新策略探測網絡變化，信源設備遍歷向量網中的17個分量地址，1 s后發送維護信令包對拓撲進行檢測，最后實現向量網絡連接檢測。該拓撲更新策略可應用中小型網絡，提高網絡拓撲結構的可靠性，有效地提供多路徑向量網通信。

圖3　終端生成樹的拓撲模型：左B、右A

［1］許偉，婁松濤.VPN技術在計算機網絡中的應用研究［J］.電子技術與軟件工程，2014（4）:239-240.

［2］陽旺，李賀武，吳茜，等.互聯網端到端多徑可靠傳輸協議研究［J］.計算機研究與發展，2012，49（2）:261-269.

［3］許德力，宋飛，高德云，等.無線環境下基于SCTP的并行多路徑傳輸［J］.計算機應用，2010，30（9）:2515-2518.

［4］李洪兵，熊慶宇，石為人.無線傳感器網絡非均勻等級分簇拓撲結構研究［J］.計算機科學，2013，40（2）:49-52.

［5］蔡巍，趙海，王進法，等.能源互聯網宏觀結構的統一網絡拓撲模型［J］.中國電機工程學報，2015（14）:3503-3510.

［6］鐘成.電力通信網中雙鏈路故障的一種共享段保護算法研究［J］.電氣應用，2013（2）:55-61.

［7］閆興篡，殷建平，蔡志平.網絡拓撲發現算法綜述［J］.計算機工程與應用，2007，43（14）:131-135.

［8］王哲，梁滿貴，及曉萌，等.源端控制的OpenFlow數據面［J］.通信學報，2015（3）:181-187.

［9］及曉萌，梁滿貴.一種向量網可編程交換機實現［J］.軟件. 2013（7）:95-99.

［10］吳文甲，楊明，羅軍舟，等.干擾約束和負載均衡的無線Mesh網絡網關部署策略［J］.計算機學報.2012，35（5）: 883-897.

［11］吳金哲，紀靜，屈濤.基于MicroTCA系統的AMC以太網交換板設計與實現［J］.計算機與現代化，2014（3）:131-135.

［12］陳昕，向旭東，張磊，等.網絡演算理論及其在分組交換網中的應用［J］.北京信息科技大學學報：自然科學版，2011，26（1）:11-16.

［13］李洪鑫，李世民，王坤.基于拓撲變化預計算的多層衛星網絡路由協議［J］.現代防御技術，2013，41（2）:46-50.

［14］林濟鏗，潘光，潘毅，等.基于矩陣環和操作的Mayeda生成樹實用算法［J］.中國電機工程學報，2014（31）:5659-5667.

［15］常旭，李義杰，劉萬軍.CDC與REP結合的決策樹剪枝優化算法［J］.計算機工程，2012，38（14）:32-34.

［16］陳曦，王純，王晶.一種信令數據高效檢索方案［J］.計算機系統應用.2012，21（6）:59-63.

Design of vector network connectivity based on topology update algorithm

XUE Nian，CHANG Luo
（Henan Medical College，Zhengzhou 451191，China）

In view of the vector network data exchange equipment as far as possible don't realize the problem of signal processing，by calculating and traverse the network topology spanning tree method to test the network topology and update，this paper proposes a vector network connection design based on topology updating strategy.Detected by the team leader，node response vector network topology discovery method and the simple switch network topology discovery method for topological collection，source equipment through 17 component in the vector network address，1 s after send to maintain signaling packet to test the topology.In the process of traversal，terminal to generate the Leaf-node and Leaf nodes table contains the Leaf node of the virtual link table v-node accurately positioning vector network connection effect，effectively providing multipath vector network communication.

vector network；topology update；spanning tree；traverse；network connection

TN915.6

A

1674－6236（2016）12-0014-04

2016-03-15稿件編號：201603177

國家自然科學基金（61372180）

薛念（1981—），男，河南信陽人，講師。研究方向：計算機網絡。