IEC62439 PRP冗余丢弃算法设计

张宪军，刘 颖，余华武，陈新之

(国电南京自动化股份有限公司，江苏 南京210003)

0 引言

智能变电站在GOOSE、SV、MMS三网合一测试中，核心交换机冗余备份较引人注目。通信备份双向网络，故障恢复通常需要时延。PRP（并行冗余协议）以零丢包、零切换时间在智能变电站众多设备厂商中获得高支持，文献[1-3]介绍了PRP/HSR（高可靠性无缝冗余）是理想智能变电站网络冗余方案。文献[4-9]使用基于序列号双窗口丢弃算法，文献[10]使用基于源MAC、目的MAC、序列号表查找算法，对设备重启、老化、时序异常情形考虑较少。文献[11]未具体指定，说明节点表、哈希表、FIFOs、基于序列踪迹均可，同时改进PRP与HSR装置双网序列号共用；在RCT（冗余控制尾缀）引入新后缀字段更好标识PRP协议帧；针对丢弃算法删除所有实现上约束，特别是连接方向限制，这个连接方向字段在哈希算法中未使用；删除重复表清除代之以任何老化旧表项的机制都可以，保障装置恰当重启。实现过滤丢弃算法需满足：不能丢弃任何合法报文；容忍偶尔接收个别重复包；面向无连接序列号；序号按递增顺序但不必连续；过滤丢弃重复报文；乱序报文正常接收；效率高逻辑简单；超时老化处理；本地设备重启处理；对端设备重启处理；单条链路断开处理。

图1显示丢弃算法时间约束，twrapMin是最小可能时间在序列号65536回滚之后两个相同序列号重复合法报文接收之间。在100 Mbit/s以太网络，twrapMin大约是400 ms理论上从相同源接收到帧重复最小时间。tskew是同一个帧的两份拷贝到达的时间差。tresideMax是一个表项保留在重复表中的最大驻留时间，应不大于EntryForgetTime(表项老化时间，缺省为400 ms)。taliasRepMin是别名帧重复接收最小时间，应不大于twrapMin和对端系统重启加等待时间两者最小值。可靠丢弃原则是tskew＜ tresideMin，安全接收原则是tresidenceMax＜taliasRepMin。装置重启避免产生别名帧在EntryForgetTime时间之内不要发送报文，在这个时间之后，接收方将老化重复表中表项。别名帧是指序列号相同但帧数据内容不同。实际上支持嵌入式操作系统的装置重启时间一般在5～10 s，功能复杂装置约在15 s，缺省重启约定时间是500 ms,EntryForgetTime足够小这些装置重启之后是可以直接发送数据包的。为避免别名帧产生，无软件或启动时间极短系统重启需等待约定时间不发送数据报文然后才开始工作。

图1 重复丢弃算法边界Fig.1 Duplicate discard algorithm boundaries

1 PRP协议

图2是PRP帧格式，RCT（6字节）扩展：16位序列号（SeqNr），4位LAN ID，12位帧长度（LSDU长度），16位PRP类型。SeqNr 由发送方按递增顺序标识重复数据包，同一份报文序列号相同，接收方通过序列号来区分报文是否重复。LAN ID用来区分端口连接LAN方向。LSDU长度是原来数据长度加上6个字节后缀。类型后缀为0x88FB常值。发送时在原有报文基础上增加RCT，对不支持PRP原始报文按接收模式处理。DANP（双连接支持PRP节点）中LRE（链路冗余实体）负责发送和接收冗余处理，两个端口使用相同IP和MAC地址，参见图3。DANH（双连接支持HSR节点）LRE增加了非本设备接收报文转发功能，包含发送和接收过滤丢弃。文献[12-13]对智能变电站网络可靠性进行分析，在装置中合理采用PRP/HSR能够满足智能变电站的可靠性需求。

图2 PRP帧RCT扩展Fig.2 PRP frame extended by an RCT

图3 PRP双DANP通信Fig.3 PRP with two DANPs communicating

对双HSR环网拓扑，本方法是基于点对点，当QB处于两个节点中间位置时，需配置节点（基于MAC地址识别）路径转发信息，在接收端要过滤掉重复报文，在发送端按新序列号加入HSR标签向环网两侧发送，此时QB是代理角色，性能相对较低，但端口故障处理方式灵活。代理模式是缺省必须支持的HSR标签转发模式；模式N是非转发模式，两个环网各自独立转发环内数据；模式T是透明转发，删去HSR标签，向另一个环的两个端口未经重复过滤转发非标签数据；模式M是混合模式，基于HSR标签报文处理同代理模式，非HSR标签报文是否加入标签依据本地配置，若不加入HSR标签则根据IEEE802.1D规则转发；模式U是单播转发模式，处理同代理模式仅转发单播数据报文。

2 丢弃算法设计

接收报文目的地址分单播、组播、广播，在环网内组播和广播转发没有本质区别。当接收到是自己所发送报文必须要丢弃避免风暴。接收到目的地址是自身MAC或是自身订阅了的组播（或广播），节点会根据源MAC地址表建立节点表。因这些表在数据收发路径上频繁查找，建议初始化时分配一定空间，老化删除时设置标志为无效，新建只需使能标志为即可。可以基于MAC地址作一次哈希（HASH）处理再查找，如基于最后一个字节分类，这样可大大减少顺序查找耗时，提高传输性能。本发明算法是在节点表之内，占用一定空间记忆序列号的接收状态，利用固定丢弃窗口进行老化，（源MAC，序列号SeqNr）是唯一标识报文信息，与之一一对应的状态信息可以有效防止重复报文的接收。超过一定时限，序列号相同，报文内容未必相同。在同一个时限内，FCS（帧校验序列）完全一样，报文内容未必相同。

序列号范围0～65535，起始是0，终点是65535（SEQNUM），中间点是32767，对于节点发送起始序列号没有任何影响。基于每个MAC定义一个整型数组，每个成员是一个32位或64位（SEQBITS）变量，利用每一个位存储一个序列号的状态，1表示首报文新近接收到（重复丢弃），0表示未接收到首报文，接收到首报文上传本地上层应用处理。SeqNr和状态位之间是通过HASH进行索引，具体的就是从开始的第0个字节的0位算起，SeqNr的状态位正好对应SeqNr个总数位的值，例如SeqNr/SEQBITS是对应位所在的整数在数组中的位置，SeqNr%SEQBITS是对应位在所在整数的具体位的位置，便于索引、查找、设置、清除状态信息。滑动窗口设置是为了减少窗口内阻塞的序列号个数，通常是在当前接收数据序列号附近的报文重复较多，丢弃窗口大小（DWS）可配置，缺省设置为64，范围1～65535。在窗口外的将作为新报文处理，直接上传报文到应用层。窗口内的驻留时间为256 ms，每隔这个时间间隔，将强制老化窗口内的所有已设置位为0，此时所有接收到的报文将按照新报文来处理，窗口大小固定不变。窗口设置三个变量，MinSeq是当前窗口中接收到的最小序列号；MaxSeq是窗口上限至少比当前窗口中接收到的最大值大1个，这是方便计算窗口大小；CurSeq是当前接收到的序列号。若不设置这个滑动窗口，按照固定周期（如256 ms）老化也能满足要求，要老化整个位状态表，老化占用时间相对稍长且不利于将来扩展。本方法增加了这个滑动窗口，使其具有HASH算法的快捷和滑动窗口的优点，老化DWS窗口占用时间相对很小，缺陷是每次接收到报文增加了判断和计算的时间。

对接收到的序列号分三种情形：在窗口内、小于MinSeq、大于等于MaxSeq，而对于丢弃窗口也有两种情形，起始序列0和终点序列65535在窗口内和不在窗口，判断的依据稍有不同。如图4，起止序列不在窗口内，CurSeq在窗口内，则依据记录的序列号对应的状态位进行判断，已接收则丢弃，否则接收报文然后序列号状态置位为1。按照约定序列号是递增顺序增加的，当CurSeq大于等于MaxSeq时，窗口向前移动Δf = MaxSeq-CurSeq，CurSeq位状态置为1，MinSeq同步向前移动Δf，同时在这个Δf内的所有序列号对应的位清0。当CurSeq小于MinSeq时，此时有可能是窗口大小设置较小网络延时很大、网络拥塞、或是对端设备重新启动，同时向后移动固定丢弃窗口大小DWS，可以保留原来窗口中位状态但不建议这样做，本方法清除窗口中保留的位状态使所有报文都进入新报文接收状态。图5为起止序列在窗口内的处理情形。

3 伪码

常量及变量定义：

图4 起止序列不在窗口中丢弃算法Fig.4 Beginning and end sequence number not in the window discard algorithm

图5 起止序列在窗口中丢弃算法Fig.5 Beginning and end sequence number in the window discard algorithm

位清除函数描述：参数beginpos是数组中的起始位位置，endpos是结束位位置，本函数实现数组prpseqbits[SEQLEN]中两个位（含beginpos，endpos这两位本身）中间位的清零工作。同样分起始序列0和终点序列65535是否在这个区间。在两个位置都在同一个SEQBITS位整数中，可以定义常量二维数组掩码，数组大小为SEQBITS * SEQBITS，例如，（10，20），值为0xff801fff（32位为例），中间第10～20位是0的掩码，借助这个掩码可以快速清零，然后再分beginpos，endpos是在1、2、多个整数情形中处理。可不写成函数，在伪码中利用已有的判断做宏定义，就是位清零分段宏来实现。最简单是通过For循环位清零，位宽较大时计算量稍大。

4 健壮性

基于序列号双丢弃窗口算法，当发送端单网口发送时（假定另一个端口故障），或者另一侧网络连续丢包若干个，此时重启，若不增加老化机制，将产生别名报文连续丢弃；针对乱序报文将不断产生重复报文接收；超过两路报文将难于处理。当多端口中仅有一个在接收状态，此时关闭冗余丢弃算法，降低接收延时，当检测到仅有一个端口可发送时，关闭冗余发送处理。检测到两条链路同时连接正常接收报文时，开始运行算法。基于端口状态检测宜采用较快方式，如中断处理。当两个HSR环网通过QB连接时，单装置故障将彻底断开两个环的连接，一般推荐采用两个QB互相冗余备份，但这不能提高性能可提高可靠性。本地设备重新启动，序列号从初始状态重新开始，丢弃窗口最低序列号从零开始，任何一个报文都是首包直接进入冗余丢弃算法处理。

HASH表的老化，约定每隔256 ms进行窗口内所有状态老化，这也是报文在这个表中的最大驻留时间，当数据接收时若老化正在处理则按首包处理，此轮状态信息不记录。可设置标识来检查，不建议使用信号量，系统调用花费较多时间。当检查到上次老化与本次老化之间没有数据包接收将不必老化。老化时间与滑动窗口大小可配置，方便根据流量大小进行调整。目前所有装置的数据处理是CPU完成的，不具备全千兆发送和接收的处理能力，本算法在装置处理器具有百兆带宽处理能力时适用，此处指CPU处理能力而不是发送和接收带宽。具备全千兆数据通信处理能力的处理器算法需改进，如增加特定流量的报文（或唯一特征）记录以便进行HASH比对，或考虑使用报文接收时间参数作间隔，或在发送端加入基于发送时间的随机数作为报文的唯一关键特征等。

文献[14]中2.2“基于双重哈希的监测和过滤算法”一节，指出“要找到散列为同一个值的两个不同的输入，在计算上是不可能的”是错误的，就是整篇文章的理论依据不正确。文献[15]第一节“循环冗余校验码（CRC）”指出，CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于K（K为g(x)的阶数）的突发错误，通信中K取值32。这个问题不需复杂高深证明，根据抽屉原理，32位的校验和如何保障1 500字节（12 000位）的数据报文内容完全不同，一定会有不同的输入数据报文内容产生相同的32位校验和。

在智能变电站中丢弃任何一个合法报文的严重程度比多接收几个重复报文的危害性要大得多，使用HASH算法采用的关键字理论上需证明是准确无误的，体现技术严谨可用性。

5 结语

本文发明算法可在32位、64位字节设备上实现，在满足可靠性基础上做性能优化，在接收报文路径上处理占用时间越少越好。不仅支持接收两路报文，四路报文同样可以过滤接收。对重复风暴报文有免疫力。基于存储转发无连接报文乱序是交换网络一个固有问题，本方法能对乱序报文做过滤处理。检测到单链路断开、恢复进行处理。对本地、对端设备重启进行处理。短暂不运行过滤丢弃算法是全数据报文都接收，对正常运行影响不会很大。需从理论上证明重复丢弃算法是可靠的才能提高智能变电站冗余可靠性，HASH算法关键字FCS需谨慎选用。本文发明方法为智能变电站电力装置快速实现PRP/HSR奠定坚实算法基础，为改善智能变电站高可靠性冗余提供设计参考。

[1] 易永辉, 王雷涛, 陶永健.智能变电站过程层应用技术研究[J].电力系统保护与控制, 2010, 38(21): 1-5.

YI Yong-hui, WANG Lei-tao, TAO Yong-jian.Process level application scheme in smart substation[J].Power System Protection and Control, 2010, 38(21): 1-5.

[2] 谢志迅, 邓素碧, 藏德扬.数字化变电站通信网络冗余技术[J].电力自动化设备, 2011, 31(9): 100-103, 120.

XIE Zhi-xun, DENG Su-bi, ZANG De-yang.Redundancy technique of digital substation communication network[J].Electric Power Automation Equipment, 2011, 31(9):100-103, 120.

[3] 何钟杰, 黄险峰, 崔春, 等.几种智能变电站冗余通信协议分析比较[J].广东电力, 2011, 24(4): 5-8.

HE Zhong-jie, HUANG Xian-feng, CUI Chun, et al.Analysis and comparison of redundancy communication protocols for smart substations[J].Guangdong Electric Power, 2011, 24(4): 5-8.

[4] IEC-62439 high availability automation networks[S].2008.

[5] IEC 62439-3-2010 high availability automation networkspart 3: parallel redundancy protocol (PRP)and highavailability seamless redundancy (HSR)[S].

[6] 程子敬, 李富, 李周.一种高可靠并行环网的研究与实现[J].电子设计工程, 2011, 19(23): 99-101.

CHENG Zi-jing, LI Fu, LI Zhou.Research and implementation of a high available parallel ring ethernet[J].Electronic Design Engineering, 2011, 19(23):99-101.

[7] 李俊刚, 宋小会, 狄军峰, 等.基于IEC 62439-3的智能变电站通信网络冗余设计[J].电力系统自动化,2011, 35(10): 70-73.

LI Jun-gang, SONG Xiao-hui, DI Jun-feng, et al.Communication network redundancy design of intelligent substation based on IEC 62439-3[J].Automation of Electric Power Systems, 2011, 35(10): 70-73.

[8] 李俊刚, 张爱民, 宋小会, 等.并行冗余协议在智能变电站网络的应用[J].南方电网技术, 2013, 7(4): 92-96.

LI Jun-gang, ZHANG Ai-min, SONG Xiao-hui, et al.The application of parallel redundancy protocol in smart substation network[J].Southern Power System Technology, 2013, 7(4): 92-96.

[9] 陈原子, 徐习东.基于并行冗余网络的数字化变电站通信网络构架[J].电力自动化设备, 2011, 31(1):105-108.

CHEN Yuan-zi, XU Xi-dong.Communication network structure of digital substation based on parallel redundancy[J].Electric Power Automation Equipment,2011, 31(1): 105-108.

[10] 许铁峰, 徐习东.高可用性无缝环网在数字化变电站通信网络的应用[J].电力自动化设备, 2011, 31(10):121-125.

XU Tie-feng, XU Xi-dong.Application of high-availability seamless ring in substation communication network[J].Electric Power Automation Equipment, 2011, 31(10):121-125.

[11] IEC 62439-3-2012 high availability automation networks part 3 parallel redundancy protocol (PRP)and highavailability seamless redundancy (HSR)[S].

[12] 侯伟宏, 张沛超, 胡炎.数字化变电站系统可靠性与可用性研究[J].电力系统保护与控制, 2010, 38(14):34-38.

HOU Wei-hong, ZHANG Pei-chao, HU Yan.Reliability and availability study of the digital substation system[J].Power System Protection and Control, 2010, 38(14):34-38.

[13] 孙晓明.智能变电站自动化系统网络可靠性分析及优化[J].水电能源科学, 2012, 30(10): 167-171.

SUN Xiao-ming.Reliability analysis and optimization strategy for smart substation SAS communication network[J].Water Resources and Power, 2012, 30(10):167-171.

[14] 黄曙, 马文霜, 陈炯聪, 等.智能变电站网络风暴的监测和过滤算法研究[J].电力系统保护与控制, 2013,41(18): 68-72.

HUANG Shu, MA Wen-shuang, CHEN Jiong-cong, et al.Research on the network storm monitoring and filtering algorithm in smart substation[J].Power System Protection and Control, 2013, 41(18): 68-72.

[15] 邱继涛.循环冗余校验码(CRC)[C] // 第八届工业仪表与自动化学术会议, 2007.

QIU Ji-tao.Cyclic redundancy code (CRC)[C] // The Eighth Industrial Instrumentation and Automation Conference, 2007.