- 1 -
单向链路的网络拓扑获取及在向量网中的
应用 #
闫敏1,2，梁满贵1,2**
（1. 北京交通大学信息科学研究所，北京 100044； 5
2. 北京交通大学现代信息科学与网络技术北京市重点实验室，北京 100044）
摘要：当前 IP 网中，链路都是双向传输的，双向链路假设虽然一定程度简化了网络模型，
但是失掉了一般性。现实世界中，很多网络场景并不适合用双向链路的网络模型来表示，如
广播电视网，因此针对单向链路的网络拓扑研究就有了现实的意义。向量网是一种新型网络10
架构，向量网数据面与控制面分离，为了最大限度地简化网络，有一种只具有数据转发功能
的简单交换设备，本文将研究这种交换机组成网络的拓扑收集问题。本文提出单向链路网络
中交换节点通过洪泛主动探测网络拓扑的方法，给出向量网中单向链路拓扑探测协议。具体
方法为节点主动进行发送 hello 包探测，将链路状态信息发送给组长，组长收集信令更新网
络拓扑结构。这种拓扑发现方法优点是收集拓扑速度快，适用于大规模网络。 15
关键词：向量网；单向链路；拓扑发现；信令处理
中图分类号：
Unidirectional Link Network Topology Acquisition and Its
Application in Vector Network 20
YAN Min
1,2
, LIANG Mangui
1,2
(1. Institute of Information Science, Beijing Jiaotong University, Beijing 100044;
2. Key Laboratory of Information Science and Network Technology, Beijing Jiaotong University,
Beijing, 100044)
Abstract: In the current IP network, all links are two-way link hypothesis 25
simplifies the network model, it loses the generality. In the real world, many network scenarios are not
suitable for the two-way link network model, such as broadcast television network, so the study of the
network topology for unidirectional links has an importantly practical significance. Vector network is a
new kind of network architecture, in which data layer and control layar are separated. in order to
simplify the network, there is a simple device which can only transmit data. In this paper, the author 30
will study the topology collection of this network. In this paper, a method detecting network topology
in a one-way link network by nodes flooding is proposed. The specific method is that nodes detect
neighbours, and send the link state information to the group leader collects signaling packets
to update network topology. This kind of topology discovery method has the advantage of fast
collection speed and is suitable for large-scale networks. 35
Key words: vector network; unidirectional link ; topology discovery;signaling procedure
0 引言
IP 网是当前应用最广泛的数据通信网，网络设备都有唯一的 IP 地址作为通信地址。在40
IP 网中，转发设备具有数据面和控制面两个功能，维护的路由表中保存大量路由信息，为
了使数据包在设备间正确传输，转发设备通过查询路由表将数据转发出去。而随着网络规模
- 2 -
的不断扩大，路由表规模也逐渐增长，路由信息维护变得更加复杂，设备硬件造价上升，关
键节点设备功耗增加。
向量网是一种新型的网络架构，是依托于“一种向量网络地址编码方法”[1]和“向量数
据通信网上建立向量连接的方法”[2]两项发明专利而建立起的。在向量网中，向量地址是向
量网通信的理论基础，向量地址是由数据包转发路径中经过交换设备的转发端口号循序排列5
编码而成，转发设备将向量地址第一个转发端口删掉，将向量包按转发端口号转发。因此，
在向量网中，数据面和控制面分离，交换设备只完成数据面的功能（转发数据和基本信令控
制），控制面功能由向量网控制器完成，因此简化了转发设备，降低了设备造价[3]。
同时，当前的 IP 网络中，所有的通信线路都是双向通信的，而这样的结构并不适合所
有的网络模型，一些网络只适合单向链路网络模型表示了，例如广播电视网，下行流量远高10
于上行流量。而且单向链路网络是双向链路网络的更一般情况，单向链路的网络模型更具有
普遍性，因此需要研究单向链路网络中拓扑的收集方法。
然而，向量网有其自身特点，如何获取网络拓扑，需要设计专门协议。本文提出了一种
在单向链路网络中交换节点通过广播 Hello包主动探测网络拓扑的方法，设计了向量网中单
向链路的拓扑探测协议。交换节点将链路信息发送给组长，组长将收集到的数据处理，最终15
获得单向链路网路拓扑结构，收集拓扑速度更快。
1 网络模型介绍
本节中，我们将对向量网的网络模型和相关的概念进行介绍和定义，以更清晰的说明单
向链路的网络拓扑探测方法。
20
图1 基本网络模型示例
Basic Network Model Example
图1是向量网的一个例子，以此简单的网络模型说明网络拓扑探测的方法，其中方块表
示的 A, B, C代表终端节点，圆圈表示的1，2，3，4，5代表交换节点，交换节点旁的数字
代表节点的转发端口号。下面具体说明模型中各个设备的功能。 25
向量网交换机 VS：图中圆圈表示的节点为向量网交换设备，主要功能是判断向量包，
将其转发，同时对信令包进行相应的处理，如添加和删除向量地址，添加和修改向量包标识
位，每个向量网交换机都知道返回组长 LD的向量地址，可以将邻居节点与自身节点的链接
关系信息返回给组长 LD供其探测和收集拓扑。
端系统 ES：图中方形表示端系统，代表当前网络的边界，当信令包转发到这种节点时，30
不再继续转发和处理。
- 3 -
中国科技论文在线
探测组长 LD：图中并没有标识出探测组长的节点，组长是特殊的向量网交换机 VS，由
具有竞选能力的交换节点通过竞选产生，负责收集网络中返回的信令包所包含的拓扑信息，
逐渐形成完整的网络拓扑结构，并将交换机到 LD的向量地址发送给对应交换机。
在向量网中，交换设备的输出端口从0开始用数字编号（如果0保留它用，则从1开始），
称为端口号。每个交换设备都对应序列中的一个端口号，也是数据通过该设备的输出端口号，5
称为分量地址。向量地址（Vector Address,简称 VA）以端口号为编码基础，描述了从信源
设备到信宿设备传送数据的通信路径。
向量网的数据包格式如下：
Head VA Data
其中：
向量地址 VA[1]：一种相对的地址，由若干分量地址组成，标识了一个信源设备到信宿10
设备的路径，格式为 VA = FF CV CV CV ……，CV的个数随需而定。
分量地址 CV[1]：转发设备的输出端口号，是组成向量地址的元素，二进制编码。
填充标志位 FF：用于将 VA 地址填充至整字节，并找到第一个分量地址 CV 的起始位
置。
图1中信源设备 A 到信宿设备 C 的向量地址（从左到右表示由高位到低位，且不考虑 A15
出口的分量地址）具体如下：
Byte1 Byte0
1010 10 01 0011 1000
填充标志位 FF，即 1000（斜体字部分）位于数据最低位地址，4个 CV：011、010、10、
1010由低到高依次排列。当 A发出带有如上向量地址的向量包后，交换设备 1从端口 1收
到此网络数据包，检查第一个分量地址，得到 CV1=011，把第一个分量地址 011从向量地址20
中删除后将该网络数据包发送到 3 端口。随后，数据包会依次从 3,4,5 转发设备的 2,2,10
号端口转发数据，最后到达 C设备。以上就是在向量网中，数据转发的具体过程[4]。
2 向量网单向链路拓扑收集
适用范围
通常网络模型中，交换节点之间都是双向链接的，而在某些现实场景中，并不适合用双25
向链路网络表示，只能通过单向链路表示。其实，所谓双向链路网络也是由两根单向链路组
成的，如双绞线，所以单向链路网络是双向链路网络的更一般、更普遍的情况，并且比双向
链路更经济。
向量网中，转发设备只有数据转发功能，而只靠控制器用逐层遍历的方法探测网络拓扑，
耗费信令包多，收集拓扑速度慢。所以我们在交换设备中添加了一些信令控制和包处理功能，30
将收集拓扑的工作分布到各个节点中。向量网中的 C 类交换机就具有信令控制和探测拓扑
信令处理等功能；组长 LD 具有处理来自节点的链路状态信息和构建网络拓扑的功能。通过
单向链路的拓扑探测协议收集网络拓扑的方法要求网络为 C类交换机和控制器组成。
- 4 -
中国科技论文在线
单向链路拓扑探测机制
双向链路的网络拓扑中，两相邻节点互相发送 Hello包探测对方是否存在，是非常容易
的事情，然而单向链路和双向链路中探测邻居节点的区别在于被探测节点不能按原路返回。
因此，如下图所示，A 节点向 B节点发送 Hello包后，B节点需要寻找另一条路径回应 A节
点。 5
图 2 两个节点之间的单向链路探测
Unidirectional Link Detection Between Two Node
符号定义
为了方便描述，给出以下符号定义。 10
设 A 和 B 是两个相邻的节点，a和 b是网络中任意两个节点，定义以下符号，
LD：leader ，组长；
VA：vector address 向量地址；
A->B：A到 B 的有向链路；
a->b：a到 b 的有向的通信连接； 15
VA(a->b)：a节点到 b节点的向量地址集合，最大地址个数为 3；
LSI：Link-State Information 链路状态信息；
LSI(A->B)：A 节点到 B 节点的链路状态信息（信息主要包含 Aloc,Bloc,Apin,Bpin），
链路的方向为 A指向 B；
NBL：neighbor list，存储于一般节点的邻居 LSI表； 20
TPDB：Topology Information Database，存储于 LD的拓扑信息数据库，包含网络中所
有节点的相互连接信息。
信令包表示格式
LSP(SigType, LD_VA, A->B)：传递 LSI的链路状态信息包，SigType 是 2位信令码，
表示 LSP 类型，如下： 25
11 ---- Hello 包，用来探测邻居节点。
00 ---- Forward 包，LD_VA 未知，用来中转链路状态信息包。
01 ---- Report包，用来将链路状态信息发送给 LD，以便收集拓扑。其中 LD_VA 是到
达 LD 的向量地址。
NoticeP(VA，VA(A->LD))：LD 向 A 发送的通告包，其中 VA 是 LD 到达 A 的向量地30
址， VA(A->LD）是 A到 LD 的向量地址。
- 5 -
中国科技论文在线
收集拓扑过程
以下讨论的拓扑有以下特点：
（1）拓扑的初始收集和更新，一致的看成是序贯的、增量的网络拓扑信息收集。以下
讨论的拓扑探测均为增量拓扑，即在基本拓扑存在的情况下增加节点和删除节点。
（2）每个增加的节点，均与已知拓扑是互通的，孤岛节点无意义。 5
（3）假设 LD 保存有现有网络的拓扑结构，因此可以获得 LD 到所有已知交换节点的
路径和所有交换节点返回 LD 的路径。
以图 3为例说明拓扑探测过程。图中，B 和 X是已有节点，均和 LD 互通，均保存有到
达 LD 的地址，即 VA(B->LD)和 VA(X->LD)。A 为新加入的节点，它至少有一条到达链路
和至少有一条发出信息的链路，为简单起见，图 3 中只有单向链路 A->B 和 X->A。探测过10
程分三步：
（1）将 LSI(A->B)传给 LD，
（2）将 LSI(X->A)传给 LD，
（3）A获取 VA(A->LD)并保存。
15
图 3 增量收集拓扑信息过程
Collecting Topology Information Procedure
图 3 中，LSP 中第一个字段表示意义如下，11：hello 包，00：forward 包，01：report
包，其中包括 LD_VA，是到达 LD 的向量地址。
A->B的建立 20
该阶段目的是确认 A->B的存在，并将 LSI(A->B)发送到 LD，保存在 LD 的 TPDB中。
首先，A 向邻居 B 广播发送 hello 消息即 LSP(11，A->B)，B 收到后将 LSI(A->B)写入
本地邻接表NBL。B作为已有节点，拥有VA(B->LD)， B可向LD传递发送LSP(01,LD,A->B)，
LD 收到后将 LSI(A->B)写入 TPDB，拓扑得到更新，并触发 LD 通告事件。
X->A的建立 25
该阶段目的是将 LSI(X->A)发送到 LD，并保存在 LD 的 TPDB 中。其中 X 是已知网络
中与 A连接的一个节点，方向为 X 指向 A。
X 向 A 以广播形式发出 hello消息即 LSP(11，X->A)，A 收到后将 LSI(X->A)写入本地
的邻接表 NBL。
- 6 -
中国科技论文在线
A 为新加入节点，如果还未拥有 VA(A->LD)，A 将向各个端口广播发送 LSP(00,X->A)，
目的是通过拥有返回 LD 地址的节点将 LSI(X->A)中转发送到 LD。
就图 3的例子，此时 B 会收到 LSP(00,X->A)， 并向 LD 发送 LSP(01,LD_VA,X->A)，
LD 收到 LSI(X->A)后写入 TPDB，拓扑得到更新。
LD通告 A 5
LD 通告 A 由两种事件触发，（1）当新增 A 节点时，产生针对 A的 LD 通告事件；（2）
LD 的主动通告定时器到时，产生针对所有节点的 LD 通告事件。事件发生，将触发通告 A
到 LD 的 VA(A->LD)，方法是查询 TPDB，找到一条到达 A 节点的向量地址 VA 和 A 节点
到 LD 的向量地址 VA(A->LD), 构成通告包 NoticeP(VA,VA(A->LD))，并发出。A收到后，
获得了返回 LD 的向量地址 VA(A->LD)，并将其保存。 10
至此，经过以上探测和反馈过程，三个任务完成，增量地动态更新网络拓扑，新拓扑包
含了新节点 A，并且 A 获得了返回 LD 的向量地址。以上只说明了增加一个节点的过程，其
它节点所有节点可以用同样的方法动态增加。
3 向量网拓扑探测收集协议
配置网络参数 15
根据用户需求，通过设置交换节点个数来确定探测网络的范围，这样可以忽略探测网络
范围外的网络设备。同时，向量网内的向量交换机的最大端口数为 255。
网络探测信令报文格式
向量控制包
发送格式为：Head10 Cmd Information 20
Head10 是（T, Fecn）=（1，0）的 H；
Information 为向量控制包的内容；
Cmd 为控制包的类型码，1字节，包括 DCBA、y、x和 type四个子字段，其中
type 取值：
00 ---- H32 向量数据包 25
01 ----向量信令包
10 ----向量协议支持包
11 ----保留
拓扑探测信令包属于向量协议支持包[1]，所以 Type=10，这样 Cmd 字节的格式为：
30
- 7 -
中国科技论文在线
图 4 向量协议支持包的命令字段
Command of Vector Networt Protocol Support Packet
对于拓扑探测信令，以下是字段定义：
BA=10， 5
DC：11 ---- Hello
00 ---- Forward，LD_VA未知
01 ---- Report，Cmd 之后是 LD_VA.
信令包分为上行和下行两种，上行包指网络中 LSP信令包，包括Hello、Forward和 Report
三种信令包，下行包指 LD 向网络中各节点发送的 NoticeP包。用 y表示信令的上下行特征。 10
y：0 ----上行
1 ----下行
x：置零
对于下行 NoticeP 包，设置 y=1，x和 DCBA置为 0。
拓扑探测信令包格式 15
1、LSP链路状态信息包
表 1 链路状态信息包
Tab. 1 Packet of Link State Information
Head10 cmd LD_VA srcLoc srcPin desLoc desPin
向量包头 命令字段 节点到 LD
的向量地址
源节点标识 源节点转发
端口号
目的节点标
识
目的节点收包
端口号
以下是 LSP 包[5]的三种类型：Hello、Forward和 Report。
Hello类型 20
图 5 Hello 包示意图
Diagram of Hello Packet
Hello 包目的是探测节点邻居是否工作，同时将与邻居的链接状态信息传输给邻居。以
下是 Hello类型 LSP 的 Cmd 字段。 25
表 2 Hello 包命令字段
Tab. 2 Command of Hello packet
type xy para
10 00 1100
向量协议支持包 上行信令 Hello 类型
A B
Hello
- 8 -
中国科技论文在线
Forward类型
图 6 Forward 包示意图
Diagram of Forward Packet 5
Forward 类型 LSP 包目的是针对刚加入的节点 A，无返回组长 LD 的向量地址，所以 A
需要向各邻居广播发送 Forward类型 LSP，承载 X与 A 的链路状态信息 LSI(X->A)，通过有
返回 LD 地址的邻居 B 中转，将 LSI(X->A)封装在 Report类型 LSP 包中发送到组长 LD中。
以下是 Forward类型 LSP 的 Cmd 字段。
表 3 Forward 包命令字段 10
Tab. 3 Command of Forward packet
type xy para
10 00 0000
向量协议支持包 上行信令 Forward 类型
Report类型
图 7 Report 包示意图 15
Diagram of Report Packet
Report 类型 LSP 目的是 B 节点将获取的 Forward 和 Hello 类型 LSP 包中的链路状态信
息发送给组长 LD，更新拓扑。
以下是 Report 类型 LSP 的 Cmd 字段，注意这种信令的 Cmd 之后是到达 LD 的向量地
址。 20
表 4 Report 包命令字段
Tab. 4 Command of Report packet
type xy para
10 00 0100
向量协议支持包 上行信令 Report 类型
2、NoticeP通告包
NoticeP 包目的是 LD 将节点返回 LD 地址发送给对应节点，以下是 NoticeP 包格式： 25
表 5 通告包结构
Tab. 5 Notice packet
Head10 Cmd VA LD_VA LD_LOC
向量包头 命令字段 LD 到节点向量地
址
节点到 LD 的向量
地址
组长 LD 标识
B LD
Report
B LD
Report
A
Forward
X
Hello
- 9 -
中国科技论文在线
其中，Cmd 格式：
表 6 通告包命令字段
Tab. 6 Command of NoticeP packet
type xy para
10 01 0000
向量协议支持包 下行信令 NoticeP 包
报文协议及节点行为
报文协议 5
（1）节点向各邻居定时发送 Hello包。
（2）如果任何节点收到 NoticeP包，则将返回 LD的 VA保存记录在本地。
（2）任何一个节点收到邻居发来的 Hello包，则将与邻居之间的 LSI记录在本地。
（3）如果收到 Hello包的节点没有到达 LD 的 VA，则向所有邻居广播发送封装了 Hello
包中 LSI 的 Forward 包；如果节点有到达 LD 的 VA，则将 Hello 包中的 LSI 封装到 Report10
包，转发给 LD。
（4）任何节点收到邻居发来的 Forward 包，查看是否有到达 LD 的 VA，如果有，将
Forward 中的 LSI封装到 Report包中，发送给 LD；如果没有，不处理。
（5）LD 周期性的定时计算本地的拓扑信息数据库 TPDB，如果发现有新添加节点，并
且能找到往返该节点的两条向量地址，则向该新添加节点发送 NoticeP 通告包，将该节点返15
回 LD 的向量地址发送给该节点。同时，LD 定期的向所有节点发送 NoticeP 包。
交换节点行为
下面参照图 3分析信令包，用 CmdDCy表示信令包类型。
上行信令（LSP）：
情况一： 20
（1）X节点向所有邻居广播发送 Hello类型 LSP 包
X: H10 Cmd110 Xloc, Xpin; 0,0
（2）A节点收到后向所有邻居发送 Forward 类型 LSP 包
A: H10 Cmd000 Xloc, Xpin; Aloc,Apin
（3）B 节点收到后向 LD发送 Report类型的 LSP 包 25
B: H10 Cmd010 LD_VA Xloc, Xpin; Aloc,Apin
情况二：
（1）节点 A向所有邻居广播发送 Hello类型 LSP 包
A: H10 Cmd110 Aloc, Apin; 0,0
（2）B 节点收到后向 LD发送 Report类型的 LSP 包 30
B: H10 Cmd010 LD_VA Aloc, Apin; Bloc,Bpin
以下是交换节点状态图：
- 10 -
中国科技论文在线
图 4 交换节点状态
Switching Node Status
组长 LD行为
下行信令（Notice）： 5
LD 收到 Report类型的 LSP 包后，找到拓扑新增节点 A，将 VA(A->LD)封装在 NoticeP
包中发送给节点 A。
LD: H10 Cmd001 VA LD_VA LD_loc,
以下是组长 LD 状态图：
10
图 5 组长状态
Leader Status
- 11 -
中国科技论文在线
4 实验验证与分析
作者已经通过程序实现了以上的向量网拓扑探测算法，主要实现的功能如下：
（1）在已有的网络内，所有的交换设备均保存有返回 LD 的向量地址。
（2）在 LD 中保存有整个网络的拓扑结构。
（3）各交换设备均能判断收到的向量信令包的类型，并且对其作出相应的处理。 5
在该拓扑探测算法中，由于依赖各交换节点设备有处理信令的功能，所以能够处理更大
规模的网络的拓扑探测问题，这样就比从终端出发，用猜测的方法层层探测网络拓扑的方法
更减少了信令包的转发次数，探测性能只跟交换设备的个数有关。
5 结论
本文提出了一种基于向量地址编码和 C 类交换机的网络拓扑收集的算法，该算法可以10
有效的提高向量网拓扑收集的速度并且可以有效减少网络中探测拓扑产生的信令包数量，通
过所有交换设备多次运行拓扑探测算法直到收敛，组长 LD 逐渐获得稳定的拓扑结构图。
该算法可以广泛应用于中小型网络，降低了网络建设成本，提高了网络收集拓扑的速度，
基于此算法设计的高性能硬件交换设备可以提高处理向量包的处理速度。
[参考文献] (References) 15
[1] 梁满贵. 一种向量网络地址编码方法[P]. 中国发明专利 200610089302，
[2] 梁满贵 . 一种向量数据通信网上建立向量连接的方法 [P]. 中国发明专利
，
[3] 甄茂松.LAN上建立向量网络技术研究与协议实现[D].北京：北京交通大学，2008
[4] 黄照阳. 简单向量交换机网络的拓扑发现方法[D]. 北京：北京交通大学，2012. 20
[5] 田萌. 一种探测网络拓扑的新方法及其在向量网的应用[D]. 北京：北京交通大学，2014.
