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和對端系統重啟加等待時間兩者最小值?？煽縼G棄原則是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地址表建立節點表。因這些表在數據收發路徑上頻繁查找，建議初始化時分配一定空間，老化刪除時設置標志為無效，新建只需使能標志為即可?？梢曰贛AC地址作一次哈希（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是對應位在所在整數的具體位的位置，便于索引、查找、設置、清除狀態信息?；瑒哟翱谠O置是為了減少窗口內阻塞的序列號個數，通常是在當前接收數據序列號附近的報文重復較多，丟棄窗口大?。―WS）可配置，缺省設置為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 健壯性

基于序列號雙丟棄窗口算法，當發送端單網口發送時（假定另一個端口故障），或者另一側網絡連續丟包若干個，此時重啟，若不增加老化機制，將產生別名報文連續丟棄；針對亂序報文將不斷產生重復報文接收；超過兩路報文將難于處理。當多端口中僅有一個在接收狀態，此時關閉冗余丟棄算法，降低接收延時，當檢測到僅有一個端口可發送時，關閉冗余發送處理。檢測到兩條鏈路同時連接正常接收報文時，開始運行算法?；诙丝跔顟B檢測宜采用較快方式，如中斷處理。當兩個HSR環網通過QB連接時，單裝置故障將徹底斷開兩個環的連接，一般推薦采用兩個QB互相冗余備份，但這不能提高性能可提高可靠性。本地設備重新啟動，序列號從初始狀態重新開始，丟棄窗口最低序列號從零開始，任何一個報文都是首包直接進入冗余丟棄算法處理。

HASH表的老化，約定每隔256 ms進行窗口內所有狀態老化，這也是報文在這個表中的最大駐留時間，當數據接收時若老化正在處理則按首包處理，此輪狀態信息不記錄?？稍O置標識來檢查，不建議使用信號量，系統調用花費較多時間。當檢查到上次老化與本次老化之間沒有數據包接收將不必老化。老化時間與滑動窗口大小可配置，方便根據流量大小進行調整。目前所有裝置的數據處理是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位字節設備上實現，在滿足可靠性基礎上做性能優化，在接收報文路徑上處理占用時間越少越好。不僅支持接收兩路報文，四路報文同樣可以過濾接收。對重復風暴報文有免疫力?；诖鎯D發無連接報文亂序是交換網絡一個固有問題，本方法能對亂序報文做過濾處理。檢測到單鏈路斷開、恢復進行處理。對本地、對端設備重啟進行處理。短暫不運行過濾丟棄算法是全數據報文都接收，對正常運行影響不會很大。需從理論上證明重復丟棄算法是可靠的才能提高智能變電站冗余可靠性，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.