Network and Communication
以太网快速环网保护算法的设计和实现
李 富，程子敬，李 周
(北京卫星信息工程研究所，北京 100086)
摘 要 ：在 STP基础上提 出了一种快速的环路保护算法。该算法能够提供毫秒级 的环路 消除和
故障恢复能力且开销小。最后介绍 了该算法在硬 件上 的实现。 ，
关键词 ：冗余链路 ；环路 保护 ；STP
中图分 类号 ：TN915 文献标识 码 ：A 文章 编号 ：1674—7720(2012)13—0058—03
Research and implementation on a rapid ring protection algorithm
Li Fu，Cheng Zijing，Li Zhou
(Beijing Institute of Satellite Infomlation Engineering，Beijing 1 00086，China)
Abstract： This paper presents a rapid ring protection algorittin based on STP which can provide capabilities of ms loop
elimination，recovery and low overhead．FinallY，the paper describes the hardware implementation of this algorithHi．
Key words：redundant link；ring protection；STP
交换 式 以太 网 已广 泛应 用 到 工厂 、煤 矿 、电力 等 场
所 为了提高网络可靠性 ，网络需要具备冗余链路。交换
网络 环路 为交换 网络提 供冗 余链路 ，消除 了 由于单点 故
障而引起 的网络 中断，但 同时形成数据环路 ，会引发二
层交换 网络 的广 播风 暴 ，导 致 网络 瘫痪I”。
为了解决冗余链路引起的问题 ，环路保护技术应运
而 生 。生 成 树 协 议 STP (IEEE 802．1D，Spanning Tree
Protoco1)通 过阻 塞冗 余 端 口进 行链 路 备份 ，使 得 网络 中
断 后可 在 30 S～60 s内恢 复 。为 了缩 短 网络 自愈时 间 ，
IEEE又提 出 了与 STP兼 容 的快速 生成 树协 议 RSTP
(Rapid Spanning Tree Protoco1)，其收敛 时间 为秒级[21。
本 文在 分 析 STP这 种 主流 的环 路 保护 技 术 的基 础
上 ，提 出 了快 速 环 路保 护 技 术 (RRP)。针 对 环 型拓 扑 ，
RRP克服 了传统 STP 自愈时 间长 的缺点 ，可达 到毫秒 级
的 网络 自愈 时间 ，而且 复杂 度低 ，便 于实现 。
1 生成树 工作原理 及其缺 点
STP是将一个存在物理环路的交换网络变成一个没
有环路的逻辑树型 网络 ，实现在逻辑 上裁剪冗余环路 ，
同时 在 物 理 上 实现 链路 备份 和 路 径 最 优化 。STP通 过
Config—BPDU数 据包 来 构造 树 型 网络 ，通 过 Tcn—BPDU
来 通告 网络 拓扑变 化 。STP算 法 步骤如 下 ：
(1)选 举根 节点 。拥 有最 小标识 的节 点将 成 为根节
58
点 。选举 过程 开始时 ，所有 节点都 声 明 自己是 根 。当节 点
的一个端 口收到高优先级的 Config—BPDU时，就在该端
口保存这些信息 ，同时向所有端 口更新并传播信息。如
果收到比自己低优先级的 Config—BPDU，节点就丢弃该
信息 。根节 点 的所 有端 口置为转 发状 态 。
(2)确定根 端 口。对 每个 非根节 点 ，选择一 个到根 节
点路 径最短 的端 口作为此 节点 的根端 口。所有 根端 口置
为转 发状态 。
(3)确定指 定端 口。多个 节点连 接到 同一 网段 时 ，代
价最 小 的节 点被称 为指定 节点 ，取 指 定节点 在此 网段 上
的一个端 口作为指定端 口。指定端 口通过逐个考查与端
口相 连的 网段来确 定 ，选 择 指定端 口的依据 首先 是路 径
成本 ．路 径成本 低 的端 口将 成为 指定 端 口。所有 指定 端
口置为转 发状态 。
(4)等待拓扑变化。若根节点故障，其余各节点的每
个 端 口都 收 不 到 Config—BPDU数 据包 ，则 等 待 Config—
BPDU数据包 的计 时器都超 时 ，都认 为 自己是根节 点 ，开
始重新构建树型网络，重复步骤(1)～(3)。
通过 对 STP工作 原 理 的分析 ，找到 STP自愈 时 间长
的几个 原 因 ：
(1)每个节点端 口角色确定复杂。节点有根端口、指
定端 口和 阻塞端 口 3种角 色 。各节 点 的端 口不 停地发 送
《微型机与应用》2012年第 31卷第 13期
Network and Communication
和接收 Config—BPDU。每个端口根据收到的 BPDU数据
包不断更新端 口配置信息 ，计算 出根端 口、指定端 口和
阻 塞 端 口 。根 端 口和 指 定 端 口还 要 经 过 2个 Forward
Delay Time才 能进入 转发状 态 。
(2)根节点 没有主动的故障侦测能力 ，这导致 STP
对拓扑 结构 的改变 响应缓慢 。拓 扑变 化 时 ，发 现拓 扑变
化 的节点 向根节点 方 向发 送 Ten—BPDU，通 告过程 中存
在多次应答 ，等到根节点收到 Tcn—BPDU后发送携带拓
扑改 变标 志位 的 Config-BPDU．通 知其 他节 点 刷新 MAC
地址表 ，确 立新路 径 。新 选 出的根 端 口和指定 端 口也要
经过 2个 Forward Delay Time才能进 入转 发状态 。
2 RRP算法设计及实现
交换机端 口对数据的处理无非是丢弃或转发 ，因此
可以将交换机端口状态分为阻塞和转发两种。根交换节
点是网络的逻辑中心而非物理中心 ，为了提高拓扑改变
的反应速度 ，根交换节点需要 自发故障检测 ，而不依赖
其他 交换节点 的故 障通告 。
2．1 快速 环路保 护算法 (RRP)
(1)选择根节点。根节点是环网状态主动检测机制
的发 起 者 ，也是 网络拓 扑 发生 改 变后 执 行操 作 的 决策
者 。初始 时 ，各 交换 节 点在 hello—timer的作 用 下定 时从
两个级联端 口发送环路健康检测报文，即 hello报文 ，交
换节 点收 到报文后 ，进行优先级判断 ，选择出根交换机 ．
ID越小，优先级越高。如果收到报文的ID比自己的ID小．
表明自己为传输节点，从另一端1：3转发收到的报文 。自己
不再发送 hello报 文 ；如果收到报文 的 ID比自己的 ID大 ．
就丢弃此报文 ；如果 收到 自己的报文 ，说 明 自己为根节点 ，
表明有环 ，阻塞 自己一个端 口，定 时发送 hello报文 。
(2)根节点环路检测。根节点定时从两个级联端 口
发送 hello报文来 检 测环 路健 康状 况 。若根 节点 能 收到
自己的 hello报文 ，则表明环路是完整的；如果在 wait—
timer内收不到 hello报文，就认为环网发生链路故障。
(3)故障发现。若设备或链路发生故障 ，与故障链路
相连 的 端 口置 为 阻塞状 态 。根 节 点收 不 到 自己发 出 的
hello报文，wait—timer超时，表明环路不完整 ，出现故障，
根节 点把 之前 阻塞 的端 口打开 ，同时发 送 flush报 文 ．通
知其 他传输 节点更新 地址 转发 表。传 输节 点收到 根节点
的 flush报文后 ，刷新地址转发表，重新进行地址学习。
(4)故 障恢 复 。故 障消除后 ，根 节点重 新收 到 自己发
出 的 hello报 文 ，表 明环路 存在 ，根节点 阻 塞 自己一 个级
联端 口。由于拓 扑发 生变 化 ，根节 点发 出 flush报 文 ，通
知其他交换节点刷新地址表 ，与恢复链路相连的两端 El
置为转发状态。
(5)根节点失效检测。若根节点发生故障，传输节点
收不到 hello报文，wait—timer超时，各传输节点均阻塞端
口，开始 发送 hello报文 ，重新 选 出一 个根 节点 。
图 1描 述 了 RRP算 法 的实现 过程 。 图 l(a)中各 节
《微型机与应用》2012年第31卷第 13期
点 向两个 方 向发送 hello报 文 。图 1(b)中由 于 B1的 ID
最小 ，被选 为根 节点 ，(B1，P1)阻塞 ，环 路消 除 。图 1(c)
中节 点 B3和 B4问 发生 故 障 ，(B3，P1)和 (B4，P0)阻
塞 ，根节 点收 不到 hello报文 ，wait—timer超 时 ，(B1，P1)
置为转发，并向两方向发送 flush报文 。图 1(d)中各节
点收到 flush报文后 ，刷新地址表，B1定时发送 hello报
文。图 1(e)中节点 B3和 B4间故障修复，(B3，P1)和
(B4，PO)仍保持阻塞 ，B1收到 自己的 hello报文 ，意识到
环路 的存 在 ，重新 阻塞 端 口(B1，P1)，并 向两 方 向发 送
flush报 文 。图 1(f)中节 点 B3和 B4收 到根 节点 的 flush
报文 后 ，把 (B3，P1)和 (B4，P0)置为转发 态 ，根节 点定 时
发送 hello报 文 。网络拓 扑重新 收敛 。
Root Root
(a)
R0ot
(b)
Root
(c)
Root
(d) (e) (f)
图 1 RRP算法描述(◆表示端13阻塞，×表示故障)
2．2 RFIP算 法的硬 件实现
本 文基 于 稳 定拓 扑 的 以太 环 网 保护 切 换 方 案 定 义
了 2种端 口状 态 、9种 节点 状 态和 8类 事件 ．使 用状 态
机可 以灵 活实现状 态 的转移和 事件 的处理 。
(1)端 口状 态
PS0：阻 塞 ，端 V1只 处理 协 议控 制报 文 ，不 接 收 或 转
发数 据 ，不进行 地址学 习 ；
PSI：转 发 ，端 口接 收并 转 发 数 据 ，处 理 协议 控 制 报
文 ，开始 地址学 习 。
(2)节点状 态
SO：IDLE，环上端 口阻塞 ；
S1：根 节点 ，环上 端 口一个 转 发 ，一 个 阻塞 ，未 成 环
状态 ．发送 flush报文 ：
S2：根节点 ，环上端 口一个转发 ，一个阻塞 ，成环状
态 ，发送 flush报 文 ；
S3：非根 节点 ，环上 端 口转 发 ：
S4：根 节点 ，环 上端 口一个 转 发 ，一 个 阻塞 ，未 成 环
状态 ：
S5：根节点 ，环上端 口一个转发 。一个阻塞 ，成环状态 ：
欢 迎 网上投 稿 www．pcaehina．tom 59
S6：根节 点 ，环 上 端 口一 个转 发 ，一个 阻 塞 ，未成 环
状 态 ，发送 hello报 文 ：
S7：根节 点 ，环上 端 口一 个转 发 ，一个 阻塞 ，成 环状
态 ，发 送 hello报文 ；
S8：根 节点 ，环上 端 口阻塞 ，发送 hello报 文 。
(3)事 件
E1：收到低 优先级 的 hello报文 ：
E2：收到 同优先级 的 hello报文 ：
E3：收到高优先级的 hello报文；
E4：收到 flush报文 ：
E5：heHo—timer超 时 ：
E6：wait—timer超 时 ：
E7：flush报文 发送完 毕 ；
E8：hello报文 发送完 毕 。
(4)RRP算法的实现框图如图2所示。
交换机将收到的 RRP报文存放在缓冲队列中。有高
优先级 、低 优先 级和 同优 先级 3种类 型 。接收 报文 的 同
时，计时器超时事件也可能同时发生 ，对于发生的组合
事件 ，需要 判断 事件优先 级再进 行 相应处 理 。报文 处理
模块将要发送 的 RRP报文写入端 口的 FIFO中，同时控
制地址 转发表 的刷新 、端 口的阻塞和转 发控 制 。
两个计时器的值可调 ，其 中hello—timer设为 10 ms。
wait—timer设为 20 ms。Modelsim仿真结果表明，消除数
据环路的时间和单点故障后的保护切换时间均在 40 ms
等待读取的RRP
报文队列
J
报文类型判断
E1 E2
图2 RRP算法的实现框图
内。Synpli~综合结果表明，在 150万门的芯片上实现该
算法需要占用 2％的资源。这说明 RRP能够提供快速的
保 护切换 能力 且开销 小 。
报 文处 理模块 的状态机 如 图 3所示 。
图3 报文处理模块的状态转移图
(下转 第 64页)
(上接 第 57页)
f．updateDatastream(1，ControlCode)；
，／发 送 控制 指 令
} catch (PachubeExce plion e) {
System．out．pfinfln(e．errorMessage)；
}
(a)获取智能家居信息流程图 (b)执行远程控制指令流程图
图4 远程控制端系统流程图 ’
本 文 设 计 了 一种 基 于 Android和 Pachube的智 能 家
居远 程监 控系 统 。基于 Netduino Plus的智 能家居 网关 对
整个家居系统进行控制 ，同时提供 了远程访问的功能 ，
通过 ZigBee网络进行设备的控制和信息的传送 ，基于
Android系 统 设 计 远程 控 制 端 通 过 Pachube和 智 能 家 居
网关通信。此外 ，本系统的可扩展性强，可以将 Pachube
嵌入到网站中，不同操作系统的智能终端可以通过访问
60
网站实现对智能家居的监控 ，这也是本系统进一步研究
的 方 向 。
参考 文献
【1】余炽业．一种智能家居远程监控 系统设计【J J．电测与仪
表 ，2011，48(542)：36—39．
【2】郭渊博 ，杨 奎武．ZigBee技术与应用一CC2430设计 、开发
与实践[M】．北京 ：国防工业 出版社，2010．
【3】吴文忠，李万磊．基于 ARM和 ZigBee的智能家居系统【J】．
计 算机 工 程 与设 计 ，2011，32(6)：1987—1990．
[4】PRISTER C．Getting started with the Interact of things[M]．
America：0 Reilly Media，Inc，2011．
[5】WALKER C．Getting started with Netduino[M]．America：O
Reilly Media，Inc，2012．
【6】 欢 迎 来 到 Paehube【EB／OL]．http：／／www．pachube．cn／，
2012—03一O1．
【7】农丽萍 ，王力虎 ，黄一平．Android在 嵌入式车载导 航系
统的应用研究[J]．计算机工程与设计，2010，31(11)：2473—
2476．
[8】张魏 ，李卉．Android移动应用开发从入门到精通【M】．北
京：人民邮电出版社 。2010．
(收 稿 日期 ：2012—03—08)
作 者简 介 ：
叶红卫 ，男 ，1979年生 ，硕士 ，CCF会员 ，讲师 ，主要研究
方向 ：计算 机网络技术 、计算机应用技术。
《微型机与应用》2012年第 31卷第 13期
Network and Communication
时阃|s f ’ ’
· |
＼ ／
＼
V 坡特翠，(kh，s)
^
／＼
◆．- ． 1．—～ · ．— ··
全网单线程 子网多线程 表格多线程
① ② ③ ① ② ③ ① ② ③
图 3 扫描方法性能对比图
采集被管理设备的各项 MIB信息 ，因此 ，发现 网络结构
的变化与异常的及时性取决于扫描采集的频率。在一个
较 大规模 的 网络 内 ，轮询过 于频 繁会 产生 大量 不必要 的
通信量 ，容易引起网络拥塞；轮询周期过长 ，则不能保证
网络故 障被 及 时发 现 ，严 重影 响 了系统 的 实时性[61。而
SNMP陷阱使用事件驱动机制 ，在被监控设备上设置陷
阱．一旦被监控设备出现异常情况 ，立 即向管理工作站
发送陷阱消息，因此能够在最短的时间内发现异常 ，避
免 由设备异常而带来的经济损失。
在 SNMP的管理模型中，管理代理会 向管理工作站
发送一些重要事件的异步通告 ，其 中包括设备的冷启
动 、热启动 、接 口上线和接 口下线等几种消息，而这些消
息将由代理主动通知 SNMP管理器 ，而不是等到管理工
作站为获得这些错误情况而轮询的时候才会报告 ，这将
有 助 于 系统 以最 快 的速 度 接 收到来 自于 被管 理设 备 的
异 常通 知 。系统 在收到 这些消 息后可 以通过 单独查 询这
个设备或查询其周边的相关设备来获得这个事件更加
详细的情况并向管理人员发送告警，以便对异常情况作
出正确 的判 断和处 理 。
当然，使用 SNMP陷阱也需要消耗一定的系统资源，
如果该陷阱需要传输大量的数据，则被管设备就要消耗更
多的时间来处理这些数据 ，从而降低了设备的运行速度。
此外 ，如果 接连发生相 同类型 的陷 阱 ，每次都要报 告给管
理站，这样又造成了资源的浪费，可能会造成网络拥堵甚
至瘫痪。因此，本系统仅仅使用了设备启动、接口上线和接
口下线这几种与 网络结构和边 界安全监测 关系最 为密切
的陷阱事件，以减轻网络压力，提高系统的实时性能。
网络 规模 大 、涉及 范 围广 、设 备 种类 多 以及 用 户数
量 大是 目前 网络的基 本特点 。因此 网络 的维护 管理 和安
全 防护便 成为 了一个难 题 。本 系统在保 障 网络 出 口安全
的同时，重点加强 了网络边界 的安全监测与防护 ，使网
络管理人员能及时全面地了解实时的网络结构和边界
接入变化情况，并通过使用多线程和 SNMP陷阱技术来
提高网络结构扫描的效率，从而有效解决 了目前网络使
用 过 程 中 比较 常见 的用 户 随意 更 改接 人状 态 和 非法 接
入网络设 备 的问题 ，避免 了 由此 产生 的 网络运 行不稳 定
问题 ，消除了网络安全监管盲 区和网络安全隐患 ，保障
了网络运行的可靠与安全。
参考文 献
[1】孙延涛 ，吴志美 ，石志强 ．基于地址转 发表的交换式 以
太 网拓 扑发现方法【J]．软件 学报 ，2006，17(12)：2565—
2576。
【2】 BREITBART Y， GAROFAI．~KIS M， JAI B， et a1．
Topology discovery in heterogeneous IP networks：the net
inventory system[J]．IEEE／ACM Transactions on Networking，
2004，12(3)：401—414．
【31杨安义 ，朱华清 ，王继龙．一种改进 的基于 SNMP的网络
拓扑发现算法及实现 [J】．计算机应用 ，2007，27(10)：
2412-2419．
【4】李琳 ，李杰．基于 SNMP的网络拓扑发现算法【J】．计算机
工程 与 设计 ，2008，29(6)：1345—1347．
[5】贺英杰 ，王慧强 ，周仁杰．面 向网络 态势感知的 实时网
络拓扑发现【J】．计算机工程，2009，35(24)：127—129．
【6】蔡道家 ，侯秀红 ，汪国安 ，等．基于 SNMP的 自陷的传递
轮询算法[J]．计算机工程 ，2007，33(11)：273—275．
(收稿 日期 ：2012—02—09)
作者简 介 ：
屈 立 成 ，男 ，1976年 生 ，硕 士 ，工 程 师 ，主 要 研 究 方 向 ：
计算机网络 、信息安全。
(上接 第 60页)
局域网中的冗余链路提高了网络可靠性 ，但引起 了
数据环路。本文在分析传统 STP算法缺点及其原因的基
础 上 ，提 出了一种快 速环 路保 护方法 ，其 实现复 杂度低 ，
可提供毫秒级的保护切换。该算法已用硬件实现。实验
表明，该算法能够提供快速的保护倒换能力且开销小 ，
具 有 良好 的 应用前景 。
参 考文 献
【1】IEEE 802．1D 2004．Media Access Control (MAC)Bridges[S】．
2oo3．
【2】 IEEE Std 802．1W 2001．Media Access Control(MAC)
Bridges Amendment 2：Rapid Reeonfiguration[S]．2001．
64
【3】宋烨 ，朱杰．STP协议实验测试与仿真测试的 比较和研
究【J】．电子测量技术 ，2007，30(5)：129—132．
【41沈一波 ，石旭 刚 ，张胜 ，等．基 于稳定拓扑 的以太环 网保
护[J】．微型机与应用 ，2009，28(21)：53--56．
【51吉萌 ，詹翊春 ，余少华．以太环 网的路 径保护和恢 复算
法的研究和实现fJ】．小型微型计算机系统 ，2006，27(4)：
596—599．
(收稿 日期 ：2012—03—04)
作者简 介 ：
李 富 ，男 ，1987年 生 ，硕 士 研 究 生 ，主要 研 究 方 向 ：空 间
信 息 系 统 。
《微型机与应用》2012年第 31卷第 13期
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ O
9 8 7 6 5 4 3 2 1
