電力通信網絡中高效的OSPF流量負載均衡協議

李祝紅，趙燦明，周 方，張信明

(1.國網安徽電力公司 蕪湖供電公司，安徽 蕪湖 241000； 2.中國科學技術大學 計算機科學與技術學院，合肥 230027) (*通信作者電子郵箱xinming@ustc.edu.cn)

電力通信網絡中高效的OSPF流量負載均衡協議

李祝紅1，趙燦明1，周 方2，張信明2*

(1.國網安徽電力公司 蕪湖供電公司，安徽 蕪湖 241000； 2.中國科學技術大學 計算機科學與技術學院，合肥 230027) (*通信作者電子郵箱xinming@ustc.edu.cn)

針對基于開放式最短路徑優先(OSPF)協議的電力通信網絡中的流量負載不均衡問題，提出兩級優化的OSPF(TSO-OSPF)算法，分別對OSPF區域內和區域間進行流量均衡。算法采用帶寬利用率和時延作為鏈路權重，根據路由器的進出總流量，將流量過大的分支分解到多個路由器，實現最大流最小化，從而解決電力通信網區域內部和邊界路由器的流量不均衡問題。仿真實驗表明：與OSPF算法相比，TSO-OSPF算法有效均衡了網絡的流量，并且降低了10%左右的丟包率。

負載均衡；開放最短路徑優先協議；智能電網；電力通信網絡

0 引言

開放式最短路徑優先(Open Shortest Path First, OSPF)協議[1-3]作為內部網關協議，采用層次化路由，因其收斂速度快，工程較為成熟，在大型的電力通信網絡中應用廣泛[4-6]。同時OSPF將整個網絡劃分成若干區域，主干區域都會與其他區域交互大量的各種信息，其中包括調度信息、路由信息、用戶的用電信息等[7-8]。由于OSPF協議根據每條鏈路的權重，采用最短路徑(Dijkstra)算法，因此會出現多個路由器同時選擇一條鏈路權重較好的鏈路，而當這些路由器選擇了這條鏈路并路由時，則會導致這條鏈路的流量過大；又由于每條鏈路的帶寬是固定的，故在該鏈路上會產生擁塞，甚至丟包。電力通信網中流量均衡是提高電力通信網服務質量的前提，也是提高電力通信網穩定性的必要因素，因此本文致力于解決在電力通信網中的流量不均衡問題。

在OSPF協議上，Fortz等[9]提出如何確定權重向量的問題，使得在網絡流量為一個確定的值時，區域內的鏈路不會出現流量過載，而且此時的網絡性能最好,并證明這是一個完全的NP問題。Su等[10]通過在流量矩陣中人為設定鏈路權值從而達到流量均衡，在這個基礎上，Sridharan等[11]提出基于鏈路剩余容量的啟發式算法和動態獲得權重的啟發式路由算法；但是并不能很好地解決邊界路由器上的流量不均衡問題，而且這些權值都需要人為預先設定。雖然文獻[12-13]致力于利用已知的流量需求和帶寬，設置邊界路由器的殘樁域的門限，動態地選擇較好的一個邊界路由器作為這個區域的邊界路由器；這樣既可以很好地避免鏈路擁塞，又可以保證不頻繁切換區域邊界路由器(Area Border Route, ABR)，但是沒有考慮流量分流的問題。

目前在電力通信網中存在以下兩個關鍵問題：

1)區域邊界流量不均衡。在電力通信網中，邊界路由器負責區域間流量的發送。在OSPF協議中，一般按照帶寬作為衡量權重，使得邊界路由器流量不均衡，導致某些區域邊界路由器(ABR)成為瓶頸。在可靠的電力通信網中，一般會采用更換路由器的方式，這樣下一個路由器又會由于負載過重而崩潰。在不止一個邊界路由器的情況下，也會出現頻繁切換ABR，導致整個電力通信網絡不穩定。

2)電力通信網內部流量不均衡。在一個區域內部，由于某條鏈路的鏈路權值小，導致頻繁地使用這條鏈路，致使鏈路兩端的路由器負載過重，同時還會存在一些節點上沒有負載的情況。整個區域或者網絡會因為這種流量的分配不均衡導致網絡擁塞或者是丟包，需要頻繁地切換選擇新的路徑來維持整個網絡的運行。

本文為很好地解決這兩個問題提出“兩級優化”算法，改進了傳統的OSPF協議，定義為TSO-OSPF(Two-Step Optimized OSPF)協議。在TSO-OSPF協議中，本文的兩級優化算法指的是先解決在每個區域內的流量不均衡問題，再考慮解決邊界路由器的流量不均衡問題。首先，在解決每個區域內的流量不均衡問題時，本文采用最大流最小化的思想，考慮帶寬利用率和時延的綜合因素給整個網絡帶來的影響，將它們加入到鏈路權值中進行計算，將流量按照新的權值進行分流，以保證區域內的負載均衡。其次，本文考慮解決邊界路由器的流量不均衡問題。由于邊界路由器承擔著連接區域的流量的分配，所以本文按照新定義的權值和區域內流量的分布，給邊界路由器動態的分配流量，并通過實驗部分驗證采用TSO-OSPF協議可以使整個網絡達到高效負載均衡。

1 模型與問題

1.1 OSPF流量模型

圖1 電力通信網OSPF流量模型

1.2 OSPF問題描述

在劃分區域的OSPF區域中，如圖2所示，會出現以下兩種情況，這兩種情況的出現會嚴重影響整個電力通信網的可靠性和穩定性，同時也會使電力通信網的總體性能下降。

情況1 選定ABR1和ABR2作為區域M1的暫定邊界路由器，ABR6和ABR7作為區域M3的暫定邊界路由器，假設ABR7 ? ABR1的流量需求是50 Mb/s，ABR6 ? ABR1的流量需求是100 Mb/s，ABR7 ? ABR2的流量需求是200 Mb/s，ABR6 ? ABR2的流量需求是100 Mb/s。在M1區域，傳統的OSPF協議根據帶寬這個鏈路權值會選擇ABR1路由器為邊界路由器。但是，當ABR6 ? ABR1和ABR7 ? ABR1實際流量在增大時，ABR1將會不堪重負，因帶寬不足導致丟包。此時如果選擇ABR2作為最終的邊界路由器，不會因為帶寬不足而丟包；但是如果ABR2后面有且僅有一個路由器承擔下一跳(詳見情況2)則又會因為路由器的帶寬容量滿足不了實際的流量而丟包。所以在動態分配邊界路由器時應考慮4個因素：帶寬利用率、鏈路質量、流量進出的均衡以及時延。

圖2 電力通信網中OSPF出現的問題描述

情況2 如圖2所示，在M2區域中，選定邊界路由器ABR5，同時ABR3是連通另一個區域的邊界路由器，假設ABR5→ R1的流量需求是80 Mb/s，ABR3→ R1的流量需求是160 Mb/s，但是R1的流量容量是160 Mb/s。當ABR6和ABR3產生流量，并通過R1路由給下一條進行路由的情況下，R1會因為帶寬不足，160 Mb/s的帶寬無法承擔以180 Mb/s的流量速度進行路由，從而發生丟包現象。通常研究會認為這是有關最大流的問題，一般解決方法是多協議標簽交換(Multi-Protocol Label Switching， MPLS)流量工程將最大流分解，在源和目的節點之間預留出許多微分支，如果遇到最大流，則把流量往微分支上分解；但是這并不適應流量情況變化快的網絡，即當流量不穩定，突然增大時，微分支的鏈路將不能滿足流量需求，且微分支的鏈路質量不一定好，這樣會大大增加丟包率，增加時延。

針對這兩種情況，本文最終要達到在時延和丟包率比較小的情況下，整個電力通信網流量均衡的效果。

2 算法描述

2.1 解決思路

為改進情況1和情況2，本文提出了基于“兩級優化”算法的TSO-OSPF協議。本研究發現兩種情況下，針對區域內部路由器或者是邊界路由器都存在流量不均衡問題，因此，在TSO-OSPF協議中，本文先統一解決區域內所有鏈路的流量不均衡問題。首先，將其抽象成一個最大流的最小化問題，這樣先保證沒有本質的“內憂”；其次，最大流的最小化的約束條件發生變化，傳統的OSPF遵循的約束代價是帶寬的大小，即考慮到帶寬的代價，本文需要考慮的代價是綜合代價。其次考慮解決邊界路由器的動態分配選擇的問題，這個問題也將會考慮最大流的最小化問題以及傳輸代價和帶寬利用率等因素的影響。

2.2 方法描述

在TSO-OSPF協議中，要使得整個Mi區域內的流量達到負載均衡，那么首先要考慮的是區域內最大流的問題，之前會用保留微分支的方法來解決負載不均衡問題，也只適用于每個區域內部。現在本文整體考慮流量的問題。采用微分支的目的在于將最大流分流，減小最大的流量，使得流量均衡，但分支只能減小流量，不能準確地說明最大流的分流是有效的，因此本文使用“最大流最小化”，保證了分流的有效性。同時在解決“最大流最小化”這個問題所利用的約束條件和權值本文給予了新的調整。考慮到一個簡化分析，如圖3所示。

圖3 OSPF有效流量均衡分析模型

對于每一個節點都呈圖3的屬性，由于丟包損失的流量遠小于其他的流量，因此這里不考慮由于丟包損失的流量。根據1.1節中提到的流量性質，針對i節點，所有的進入i節點的流量加上自身產生的流量應等于最終從i節點流出的流量，即：

在流量為q的前提下目標函數可表示為：

式子表示在Mi區域，先找到有通過流量最大的節點j，將這個節點的流最小化，從而使整個區域負載均衡。

目標：最小化Uarea(q)。

2.3 算法描述

在2.2節中本文抽象出來一個最小化區域中最大流的方法同時利用約束條件得到較好的結果。除此之外，TSO-OSPF協議需要考慮的是一個全區最優的解。本文抽象出來了一個最大流最小化的新權值的問題，從而保證流量均衡的算法。這個算法是全局適用的，但是還要考慮OSPF區域劃分的情況。如果用上述2.2節的算法進行均衡整體的流量，那么會帶來的問題是傳統OSPF大多面臨的問題:交換信息過于龐大，所以在TSO-OSPF協議中，應該繼續考慮邊界節點的負載均衡。

3)在其余節點中，若流量有超過邊界流量閾值的，按照2.2節的情況動態地處理。

①若在{Aarea_t}和{ABRarea_i}集合中只有極少量的節點流量負載過重，而且它們是這些節點中的核心節點，那么只能采用2)中的核心算法，將其負載的流量均衡化。

在上面算法的基礎上借助OPNET和Matlab完成仿真實驗。

3 實驗

3.1 實驗設置

本實驗的仿真平臺是基于Matlab和OPNET Modeler 14.5，并在此仿真平臺上進行區域劃分和TSO-OSPF及OSPF路由協議的仿真和計算。拓撲規模設定為100 km×100 km大小，取用蕪湖市電力通信網作為網絡拓撲，其中包括了44臺路由器和54條有線鏈路，并分成了5層，每一層就是OSPF的一個區域。路由器間節點鏈接設置為100BaseT局域網鏈路，默認每個節點為3個100Base_TLAN邏輯子網的出口。本文在帶寬為50 000 bit/s的情況下，取α=1,β=1的情況下對電力通信網路徑(節點39至節點18)的時延、流量變化和丟包率進行仿真。

3.2 實驗結果及分析

從圖4可以看出，由于TSO-OSPF采用兩級優化，動態調整區域內和區域間的流量，所以會比傳統的OSPF的時延更小。

圖4 既定路徑平均時延變化曲線

圖5描述了在既定路徑上流量的變化趨勢。可以看出當流量到達不同節點時，虛線表示的流量忽大忽小，很不均衡。TSO-OSPF由于采用了最大流的分流技術，將其轉化成一個在多項式可解的問題，將最大流減小，因此，流出的流量比較均衡，有利于整個系統的穩定。

圖5 既定路徑流量變化曲線

如圖6所示，在330 s時既定路徑經過的節點13流量達到峰值，此時傳統的OSPF丟包率也達到了峰值，即流量的突然增大的節點，丟包率也急劇增大。TSO-OSPF協議由于采用不同的可選路徑，盡量避免了流量的堆積，這樣在整個的過程中丟包率較傳統的OSPF協議減小了10%左右。

圖6 既定路徑丟包率變化曲線

表1展示了TSO-OSPF協議和OSPF協議下，從既定路徑(節點39到節點18)的數據分析。從表1中可以看出，在代價上由于傳統的OSPF采用最短路徑，所以路徑代價比較小，但是在其他指標方面TSO-OSPF協議表現出了良好的性能。從流量的方差上看，顯然TSO-OSPF協議比較穩定，結合圖7可以看到流量是均衡的，而且還減小了時延，這樣的變化會使得在小的丟包率的情況下，信息傳遞更快速。

表1 從節點39到節點18的代價

4 結語

為了均衡電力通信網的流量，避免由于流量不均造成的路由器負載過重的現象，同時為了提高整個網絡的效率，包括吞吐率、時延和丟包率3個方面，本文提出了兩級優化算法的TSO-OSPF協議，將一個NP完全問題轉化成在多項式時間內可解的算法，并優化配置了邊界路由器。經實驗與傳統的OSPF協議進行對比，獲得了很好的效果。

References)

[1] MOY J. IETF RFC 2328: OSPF version 2 [EB/OL]. [2016- 12- 20]. http://www.ietf.org/rfc/rfc2328.txt.

[2] 馬素剛.路由協議OSPF的研究與仿真[J].計算機系統應用,2016,25(5):228-231.(MA S G. Research and simulation of OSPF routing protocol [J]. Computer Systems and Applications, 2016, 25(5): 228-231.

[3] 徐明偉,夏安青,楊芫,等.天地一體化網絡域內路由協議OSPF+[J].清華大學學報(自然科學版),2017,57(1):12-17.(XU M W, XIA A Q, YANG Y, et al. Intra-domain routing protocol OSPF+for integrated terrestrial and space networks [J]. Journal of Tsinghua University (Science and Technology), 2017, 57(1): 12-17.)

[4] 張勇,張劍,吳玉成.智能電網述評[J].科技信息,2011(29):379.(ZHANG Y, ZHANG J, WU Y C. Smart grid and its implementations [J]. Science and Technology Information, 2011(29): 379.)

[5] 鄧松,岳東,朱力鵬,等.電力大數據智能化高效分析挖掘技術框架[J].電子測量與儀器學報,2016,30(11):1679-1686.(DENG S, YUE D, ZHU L P, et al. Framework of intelligent and efficient analysis and mining technology for power big data [J]. Journal of Electronic Measurement and Instrumentation, 2016, 30(11): 1679-1686.)

[6] 高杰璋.面向廣電IP城域網的可擴展路由設計與優化[D].上海:復旦大學,2014:1-59.(GAO J Z. The radio and television services providers oriented design and optimization of scalable routing [D]. Shanghai: Fudan University, 2014: 1-59.)

[7] 劉志丹,孫琳.OSPF多區域分析與應用[J].中國科技博覽,2012(37):210-211.(LIU Z D, SUN L. Analysis of OSPF and its application[J]. China Science and Technology Review, 2012(37): 210-211.)

[8] 趙燦明,李祝紅,閆凡,等.電力通信網絡中負載均衡的路由協議[J].計算機應用,2016,36(11):3028-3032.(ZHAO C M, LI Z H, YAN F, et al. Load balanced routing protocol in electric power communication networks [J]. Journal of Computer applications, 2016, 36(11): 3028-3032.)[9] FORTZ B, THORUP M. Internet traffic engineering by optimizing OSPF weights [C]// Proceeding of the 2001 International Conference on Computer Communications. Piscataway, NJ: IEEE, 2001: 519-528.

[10] SU B, YU H, LU J, et al. Traffic optimization on the dynamic switching of ABR for OSPF networks [C]// ITCS 2009: Proceeding of the 2009 International Conference on Information Technology and Computer Science. Piscataway, NJ: IEEE, 2009: 429-432.

[11] SRIDHARAN A, GUERIN R, DIOT C. Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks [J]. IEEE/ACM Transactions on Networking, 2005, 13(2): 234-247.

[12] 姚林燕.IGP-OSPF路由協議網絡優化技術[J].電腦與電信,2012(z1):39-41.(YAO L Y. IGP-OSPF routing protocol network optimization technology [J]. Computers and Telecommunications, 2012(z1): 39-41.)

[13] 楊振啟,楊云雪.OSPF協議ABR動態選舉研究[J].計算機工程,2011,37(13):80-82.(YANG Z Q, YANG Y X. Dynamic appointment research of ABR in OSPF protocol [J]. Computer Engineering, 2011, 37(13): 80-82.)

This work is partially supported by the National Natural Science Foundation of China (61672485, 61379130).

LIZhuhong, born in 1974, M. S., senior engineer. His research interests include smart grid, electric power information network.

ZHAOCanming, born in 1983, M. S., engineer. His research interests include smart grid, electric power information network.

ZHOUFang, born in 1993, M. S. candidate. Her research interests include wireless network, smart grid.

ZHANGXinming, born in 1964. Ph. D., professor. His research interests include wireless networks, smart grid.

Efficientandloadbalancedopenshortestpathfirstprotocolinelectricpowercommunicationnetwork

LI Zhuhong1, ZHAO Canming1, ZHOU Fang2, ZHANG Xinming2*

(1.WuhuPowerSupplyCompany,AnhuiElectricPowerCompanyofStateGrid,WuhuAnhui241000,China;2.SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,HefeiAnhui230027,China)

To solve the traffic load-imbalance problem in electric power communication networks based on Open Shortest Path First (OSPF) protocol, an efficient Two-Step Optimized OSPF Protocol (TSO-OSPF) algorithm was proposed to balance the traffic in intra-area and inter-area of OSPF respectively. The bandwidth utilization and delay were adopted as link weights, the inward and outward traffic of a router was considered, the overloaded branches were decomposed into multiple routers to minimize the maximum traffic flow, thus the traffic-imbalance problem of internal and boundary router in the electric power communication networks was solved. The simulation results show that the TSO-OSPF algorithm can effectively balance the traffic in the network and reduce the packet loss rate by about 10% compared with the OSPF algorithm.

load balance; Open Shortest Path First (OSPF) protocol; smart grid; electric power communication network

TP393.071

:A

2017- 01- 24;

:2017- 03- 14。

國家自然科學基金資助項目(61379130, 61672485)。

李祝紅(1974—)，男，安徽懷寧人，高級工程師，碩士，主要研究方向：智能電網、電力信息網絡； 趙燦明(1983—)，男，安徽太湖人，工程師，碩士，主要研究方向：智能電網、電力信息網絡； 周方(1993—)，女，安徽宿州人，碩士研究生，主要研究方向：無線網絡、智能電網；張信明(1964—)，男，安徽天長人，教授，博士，CCF高級會員，主要研究方向：無線網絡、智能電網。

1001- 9081(2017)07- 1873- 04

10.11772/j.issn.1001- 9081.2017.07.1873