基于拓扑更新算法的向量网络连接设计

薛念，常珞

（河南医学高等专科学校河南郑州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—），男，河南信阳人，讲师。研究方向：计算机网络。