MgdFlow：微電網場景下的多粒度數據流管理算法

荊有波，曹清越，朱瑞

（1.鄭州大學河南先進技術研究院，河南 鄭州 450003；2.中國科學院微電子研究所，北京 100029）

0 引言

微電網是指由分布式電源、儲能裝置、能量轉換裝置等組成的小型配電系統，它以分布式電源為主，利用儲能和控制裝置進行調節，實現網絡內部的電力平衡。微電網的出現豐富了傳統電網的運行模式，提高了供電系統的靈活性和可靠性[1]。由于其發電設備多為分布式[2]，具有分布稀疏、發電不連續且不確定、運行隨機性大等缺陷，傳統的集中式優化方式難以揭示多主體之間的交互行為[3]，因此對微電網運行情況的調度控制需要全局動態信息，同時還要保證在電網災變等特殊情況下供電不受影響。

軟件定義網絡（SDN,software defined network）是一種網絡虛擬化方法，被譽為下一代網絡的關鍵技術[4]，其通過OpenFlow 分離網絡的控制平面和數據平面，從而實現對網絡的可編程性。近年來，隨著網絡應用的迅速發展，SDN 逐漸在學術界和工業界備受關注[4-6]。SDN 通過將網絡設備的控制平面與數據平面分離，以及邏輯上的集中控制，可以實現對網絡流量的靈活控制，促使網絡資源得到更充分的利用，推動網絡創新的進一步發展。

SDN 的控制轉發分離技術能很好地滿足微電網全局調度、及時處置突發情況的需求，通過集中控制特性，能夠感知全局網絡拓撲結構及通信資源使用情況，具有合理分配帶寬、靈活調度業務、改善服務質量（QoS,quality of service）的功能[7]，突發的、不在預設方案內的網絡情況會觸發packet-in 消息，從而通過控制器下發流表解決實際網絡問題，但在SDN 應用中這種OpenFlow被動式插入流表項[6]的控制方式容易導致存儲占用和調度資源過頻，從而影響微電網中網絡的健康狀況。

在SDN 中，通常在網絡的初始化階段采用主動式放置流表項以滿足對網絡帶寬和網絡時延方面有要求的應用，而被動式放置流表項的方式通常被側重負載均衡的應用所采用，2 種方式結合起來能夠讓SDN 充分調整網絡中的負載壓力，讓擁擠的路由得到及時的緩解，讓空閑的設備得到更充分的利用。然而，每臺OpenFlow 交換機所能存儲的流表項數目和流條目處理能力有限[8]，導致現有的流量調度方案存在以下問題。1) 負載均衡得不到保證：目前商用OpenFlow 交換機至多能支持存儲數萬條流表項，突發流量的激增、流處理能力的不足和流表溢出[9]會導致活動路由的流量分布不均，部分路由過分擁擠甚至堵塞，影響負載均衡的實現。2) 服務質量產生波動：隨著涌入網絡的流量增加，丟包率也不斷提升，那些沒有主動式配置流表項的流量會促發packet-in 消息風暴，導致控制器不得不做出大量響應處理這些攜帶流信息的數據包，與此同時，交換機設備的流表項也無法及時進行增刪改操作，進一步延緩了后續流量的處理，惡化了網絡服務質量。

為了解決以上問題，實現微電網中活動路由的負載均衡和服務質量，SDN 控制器需要考慮每條路由的鏈路負載和每個流帶來的負載，并且主動式地插入引導式流表項使瞬間大量涌入的流量可以按照網絡中的已有路由均勻分發，在多個節點對這些流量進行引導將極大提升網絡的負載均衡性能以及網絡服務質量，最后階段利用細粒度的被動式調度插入相應流表項完成流的運輸任務。

1 相關工作

為研究在保持網絡設備正常負載的情況下，減少各設備的存儲占用和冗余損耗，國內外的諸多學者已經做了大量的研究。Shirali-Shahreza 等[10]提出了延遲安裝與加速驅逐2 種技術，通過使用TCP RST/FIN 數據包預測TCP 流何時終止來模擬及時驅逐流表規則以及利用延遲安裝來彌補針對非TCP 流方案的缺陷，從而極大地減少了流表項占用率。Guo 等[11]提出了動態流調度方案（AggreFlow），通過流集路由、延遲重路由和自適應重路由3 種技術靈活地對流進行調度，并且將大量同時進行的重路由操作分攤在一段相對較長的時間內，實現了在較低開銷內活動路由的負載均衡和較低功耗與延遲。Soliman 等[12]提出了一種基于多協議標簽交換（MPLS）標簽的轉發方案，交換機根據這些攜帶路由信息的MPLS 標簽來轉發數據包，從而降低了對流表項的占用，但也帶來了額外的損耗，尤其在小數據流情況下更加明顯。文獻[13]提出利用數據包包頭的可用VLAN 標識符（VID）來攜帶路由信息，并且在指定的交換機上放置流表項減少了SDN 中流表的使用，在不同新流量到達的單播和多播場景，降低了流拒絕率，極大地推遲了第一次流量拒絕時間。李佳[14]提出的自適應兩級流表超時機制，采用了兩級流表架構，根據流的到達時間特征不斷修改流表項中主流表的空閑超時與次級流表的硬超時，從而減少了packet-in 消息的產生，并且提高了流表空間的利用率。劉振鵬等[15]提出了基于時序與集合的SDN 流表更新策略，將網絡中的交換機按照新舊路由分類，分類集合按次序分別更新流表，保證了流表更新的一致性，并且減少了流表空間的占用。曾友雯等[16]采用OpenFlow 交換機的服務器負載均衡策略，利用多地址定向流表對服務請求進行分類，通過蟻群算法求解最佳負載重定向方案，降低了流表項數目規模，比傳統負載策略的性能更優越。馬曉航[17]通過動態調節流表項的超時時間和超時方式，對控制通道占用率、流表項存活數、大象流偵測精度3個目標進行聯立優化，其設計的混合超時機制的優化效果優于硬超時和空閑超時。嚴可意[18]提出的區分大象流和老鼠流的檢測算法以及動態預測并設置流表項超時時間，不僅減少了交換機與控制器的頻繁通信開銷，還提升了流表利用率。齊嬋等[19]針對SDN 配置更新所引起的數據包處理不一致問題，提出一種基于分類和時序的SDN 流表更新一致性方案，有效控制了交換機存儲空間的占用率并降低了控制器的負載。

以上方案在微電網場景下的應用中都存在不足。Shirali-Shahreza 等[10]提出的方案針對TCP 流具有良好的節省表項占用效率，但對于非TCP 流的處理方案不能滿足微電網設備運行間歇性大、具有隨機性的需求。Guo 等[11]提出的AggreFlow對微電網設備出現的隨機性流進行聚合不夠高效。Soliman 等[12]提出的方案處理分布稀疏的設備產生的小流量時會導致更大的資源損耗。李佳[14]提出的方案能夠減少重定向流的調度資源，但比傳統OpenFlow 方式又增加了流表項數量。劉振鵬等[15]提出的流表更新一致性策略減少了控制負載和流表項占用，但不適于微電網場景下復雜的網絡環境。曾友雯等[16]提出的負載均衡策略較傳統算法有更優的性能，但是要求預先部署多地址定向流表；文獻[17-19]分別提出的動態優化機制和流表更新一致性能夠提升流表的利用率，但對具備相同特征的流表項沒有聚合利用。

針對微電網設備容易帶來的調度指令過頻和存儲占用問題，本文提出了一種通過延遲排序和多重聚合分流的數據流（MgdFlow,multi-granularity data flow）管理算法，在保證良好網絡通暢的情況下，比傳統OpenFlow方案[6]和自適應兩級流表方案[14]減少了交換機中平均流表項的安裝數目和調度指令下發次數，在負載均衡和降低流表項占有率方面的性能更優越。

2 系統模型

2.1 目標函數

1) 負載均衡。負載均衡主要考慮2 個指標：交換機的平均負載情況和交換機的平均表項占有率[20-22]。交換機的最大負載均衡路由決定了自身負載均衡表項的上限，而通過粗粒度聚合的流表劃分，將路由盡可能均勻地發送到網絡中的各臺交換機，避免極端情況下交換機超出最大負載利用率。由網絡平均負載與各交換機負載的均方根誤差（RMSE）來評估網絡中整體負載均衡，計算式為

交換機的硬件條件限制了其存儲空間的大小，因而對流表項的存儲存在著嚴重的限制[8-9,23]。通過聚合與分流可以極大限度地減少交換機中流表項的插入，以交換機平均表項占有率衡量該算法的效果，計算式為

2) ImproveQoS。通常QoS 考慮的指標為可用性、吞吐量、時延變化等，在本文SDN 應用場景下，主要考慮2 個指標：丟包率、控制器下發消息總數量。一是因為控制器下發控制新流消息的開銷會帶來路由開銷，在聚合與分流策略的作用下，可以盡可能減少新流加入時控制器的相應消息，在入口交換機中用于粗粒度聚合的流表項增多時效果更明顯。二是因為丟包率與流集匹配路由有關，更多的流能夠直接匹配流集路由進入網絡中，而不需要等待控制器下發指令，網絡的處理能力更好。因此本文提出一種新的考量指標ImproveQoS，即需要重路由的流占所有流的比例為

其中，f表示進入網絡中的任意一個流，fsn表示對網絡中的流聚合成的第n個流集?！苀表示進入網絡的所有流，用其減去在流集中匹配處理的流后得到需要控制器指令下發調度的流數量。

2.2 限制條件

1) 交換機負載限制。S表示交換機的集合，si∈S表示每臺交換機，Routei表示在時間t經過交換機si的路由，每臺交換機處理流的總速率不能超過上限v，則有

2) 交換機存儲空間限制。SO 表示所有交換機流表項的集合，每臺交換機存儲的流表項soi∈SO不能超過上限r，則有

3) 交換機數量限制。粗粒度聚合階段交換機總數和細粒度分流階段交換機總數之和等于網絡總交換機數，則有

2.3 問題描述

針對當前微電網場景下的實際問題，通過減少交換機平均流表項占有率和減小交換機的平均負載，從而達到網絡整體負載均衡；同時還需要減少丟包率和控制消息的下發數目，從而提高ImproveQos 整體表現。因此，針對這3 個優化目標，問題可以被量化為

3 MgdFlow 算法設計

3.1 主要思想

以單個數據包為粒度，將進入網絡的流先重定向加入一個200 μs 的緩沖隊列，設置隊列中可以緩沖的最大數據包個數為16 個，在該緩沖時間內對隊列中的數據包進行排序，初步聚合屬于同一流的數據包，從而降低同一流的數據包中交換機中匹配表項的miss 概率，減少CPU 調度指令的數量進而增加吞吐量、提高網絡的負載均衡性能。針對加入一段時延緩沖隊列排序是否會對整體時延造成更大影響的問題，Hamid 等[24]所構建的reframer 工具中已經充分驗證了數據包排序能夠極大地提高服務器內存層次的利用率，從而提升了時延、CPU 利用率等性能指標，因此在后續的求解算法中不再考慮這一問題。

圖1 展示了一個延時排序的簡單示例。在設定的200 μs 的緩沖隊列中，充斥著屬于不同流A、B、C 的數據包，通過對亂序數據包打上不同的標簽進行分類，隨后將這三類標簽對于流的處理規則寫入入口交換機中，從而完成了不同流中交織的亂序數據包的處理。

圖1 延時排序示例

以主要業務功能為條件，將經過初步時延排序的不同流再次進行基于流的粗粒度聚合和細粒度分流。在粗粒度聚合階段，以目的IP 地址為分流依據，將不同的流分為N個流集，分別指向N個中轉交換機，同時在入口邊緣交換機處插入N個用作粗粒度聚合流的流表項，從入口交換機到N個不同的交換機之間共存在M條路由，并在這些路由經過的交換機上插入指向相應中轉交換機的流表項，從而實現粗粒度聚合階段流到達中轉交換機的功能。在細粒度分流階段，以源IP 地址為分流依據，將所需大業務下的不同小業務流進行分發，在中轉交換機處插入細粒度分流的流表項；同時，對于中轉交換機可能存在的流表項占用率高以及網絡中mice flow 占據了絕大多數的流表項的情況[18,25]，將所有中轉交換機的流表項的idle_time 從一般的5 s 修改為1 s，達到快速淘汰mice flow 對應表項。

圖2 展示了聚合與分流示例，在經過初步時延排序處理后，當前網絡的處理對象由有各種具備不同屬性（如源IP 地址、目的IP 地址、源MAC地址、目的MAC 地址等）的屬于不同流A、B、C、D、E、F 的數據包組成，通過主動式放置在入口交換機的流表項粗粒度聚合成流集，在本例中，流集a包括流A、C、D，流集b包括流B、E、F，在第一步的粗粒度聚合中，根據流集分成兩大類；在第二步的細粒度分流中，由交換機響應式細粒度地插入流表項完成轉發到終端的任務，經過N次粗粒度聚合的篩選，最終流集中的其他流也發送到了終端。

圖2 聚合與分流示例

本文將微電網場景下的負載、存儲占用和指令調度抽象為一個多目標優化問題，MgdFlow 模型的符號及含義如表1 所示。使用N=(S,L)來描述網絡，其中，S表示交換機集合包含h臺交換機，并將其分別劃分給j個粗粒度階段網絡和k個細粒度階段網絡，故；L表示S中交換機之間的q條鏈路，故。

表1 MgdFlow 模型的符號及含義

3.2 算法描述

其中，x=1表示流集被分配給routem，x=0表示流集沒有被分配給routem。

在細粒度分流階段，在n臺中轉交換機處，對已經粗粒度過濾的流集再進行細粒度的劃分，將其分為g個流集，并在每臺中轉交換機處將g個用于進一步分流的流表項插入，此時將有ng個流表項插入；網絡中所有設備和鏈路組成了m′條傳輸路由，即Route′=。

對流集 fsn進行再次劃分，則有。

細粒度分流階段的所有交換機流表項數量SO=[so1,so2,…,sok]，任一臺交換機中流表項數量表示為

3.3 算法求解

根據微電網場景下整體路由建立的過程，可以概括如下。

1) SDN 控制器根據流表項占用和網絡鏈路負載更新粗粒度聚合節點的表項和整體動態視圖拓撲。

2) 粗粒度聚合節點發出路由請求，轉到步驟3)，否則轉到步驟1)。

3) SDN 控制器依次響應插入流表項引導達到每一跳的節點并記錄該條路由的表項數量。

4) 重復步驟1)～步驟3)，直至獲取所有鏈路和路由的流表項占用和負載情況。

5) 更新粗粒度聚合節點的流表項并生成新的流集。

6) 當表項空間不足或負載指標達到閾值時，增大粗粒度聚合節點的范圍并在損耗多的鏈路路由進行再次聚合與分流。

7) 網絡節點根據插入的表項完成路由。

4 實驗仿真及分析

4.1 實驗環境與配置

為模擬微電網場景下的SDN 設備情況，研究在ubuntu 環境下利用2.3.0 版本的Mininet 網絡仿真器搭建SDN 仿真環境，并且采用基于Java 的15.0.0 版本的OpenDayLight（ODL）作為SDN 控制器，Open vSwitch 作為虛擬交換機，軟件版本和硬件配置如表2 和表3 所示。

表2 軟件版本

表3 硬件配置

構建實驗網絡拓撲如圖3 所示。實驗網絡由18 個節點組成，其中包含9 臺交換機、8 臺終端主機和一臺控制器c0。網絡拓撲中的s1為入口交換機，插入了不同粗粒度的聚合流集的流表項，用來對進入流量進行初步聚合發送；s4、s5、s6為中轉交換機，插入了進行第二次聚合的粗粒度的流表項，用來對進入的流量進行二次分流發送；s7、s8、s9為出口交換機，插入了精確的細粒度流表項，完成最后的傳輸任務。h8主機以固定速率向h1～h7主機發送數據包，網絡的傳輸速率控制在500～800 Mbit/s，對實驗節點進行10 次仿真測試，并利用Wireshark 在各個節點進行抓包分析與記錄。

4.2 評估指標

1) 交換機平均負載RMSE。交換機與鏈路的負載決定了整個網絡的最大流量的容載上限，每條鏈路和交換機的負載都影響到整體的最大容載率，某條鏈路的過載可能導致某條路由甚至幾條路由的擁塞和崩潰，因此針對已有網絡中的交換機負載和鏈路承載上限，本文通過計算每條路由上的交換機平均負載情況，并計算整體的RMSE 來評估網絡中整體鏈路的承載狀態。

2) 交換機平均流表項占有率。在具備一定規模的SDN 中，OpenFlow 交換機需要通過存儲大量的流表項來應對處理進入網絡的流量，受限于三態內容尋址存儲器（TCAM,ternary content addressable memory）內存容量，流表所能存儲的流表項數目也是有限的，而TCAM 造價昂貴且耗能，所以通過增加TCAM 容量來應對大流量的流表項數目是不現實的[8-9,26]，因此針對一臺OpenFlow 交換機的存儲空間十分有限的現狀，聚焦于通過盡可能減少流表項占用，以最精簡的存儲策略來完成網絡流量的處理。交換機流表項的占用空間反映了維持一個網絡正常運行下該節點所需要占用的空間代價，平均流表項占用率則反映了整個網絡設備中所有節點的平均存儲空間占用情況，這一指標不同于最大流表項占用率和中位數流表項占用率可能受制于極大值或者極小值存儲占用的影響，而是由整體設備的存儲占用所決定，能夠真實地反映出網絡各設備的存儲情況。

3) ImproveQoS。隨著網絡負載的增加，涌入的流量逐漸增多，超過了原本設定的閾值，導致丟包率增大，流量因得不到及時的處理而阻塞在各個節點。同時，沒有匹配流表項的流量會激發table-miss表項，使交換機向控制器發送packet-in 消息并將這種類型的數據包發給控制器處理，導致控制器調度信息的下發[27]，增加了資源的損耗與負載。通過關注丟包率與控制器下發消息的數目，并將其歸結為需要重定向處理消息的流占總流的比例，從而衡量在不同策略下網絡的服務質量。

4.3 多目標優化結果與分析

1) 負載均衡性能

通過對比傳統OpenFlow 方案[6]、自適應兩級流表方案[14]以及本文提出的MgdFlow，得到3 種方案下網絡鏈路負載情況，如圖4 所示。其中，RMSE 越小則性能越好。箱線圖的上橫線和下橫線分別代表第三四分位數（Q3）和第一四分位數（Q1），也就是數據的上下分位，箱線圖的高度表示數據的分位；同時，每個箱線圖數據的平均數用三角形標出，可以看出不同方案下得出的指標數據的總體分布。

圖4 3 種方案不同方案下網絡鏈路負載情況

2) 平均流表項占有率

通過對比傳統OpenFlow 方案、自適應兩級流表方案以及MgdFlow，得到3 種方案在不同路由節點數量下的網絡所需流表項，如圖5 所示。從圖5可知，隨著網絡規模逐漸擴大，路由節點數量逐漸增多，被添加到各臺交換機中的流表項數量不斷增加，自適應兩級流表方案對流表項的損耗最多，傳統OpenFlow 方案其次，MgdFlow 方案損耗的流表項數始終低于這2 種方案。

圖5 3 種方案在不同路由節點數量下的網絡所需流表項

3) ImproveQoS

通過對比傳統OpenFlow 方案、自適應兩級流表方案以及MgdFlow，得到3 種方案在不同路由節點數量下出現網絡擁塞時需要重定向流量占比，如圖6 所示。從圖6 可知，MgdFlow 的ImproveQoS指標始終低于另外2 種方案。當流量激增時，網絡的丟包率增加，對交織在不同流中的數據包進行訪問就會反復調用線程，此時會增加對調度信息的需求，在需要重定向的流中，大象流占比越少、老鼠流占比越多，則同一丟包率下的ImproveQoS 越高。

圖6 3 種方案在不同路由節點數量下出現網絡擁塞時需要重定向流量占比

3 種方案對比如表4 所示。從表4 可以看出，與傳統OpenFlow 方案和自適應兩級流表方案相比，在負載均衡方面，MgdFlow 分別提升了25%和18%；在平均流表項占有率方面，MgdFlow 分別提升了9%和16%；在ImproveQoS 方面，MgdFlow分別提升了24%和12%。

表4 3 種方案對比

5 結束語

針對微電網需要全局調度、及時處理突發情況的需求，結合SDN 的控制轉發分離技術，提出了針對微電網業務場景下的多粒度數據管理算法MgdFlow，通過對數據包進行延時排序和對數據流完成聚合與分流，在SDN 中有效提高負載均衡性能和服務質量，降低平均交換機流表項的占有率和調度指令的下發次數，提高整體網絡對于流量的處理能力。對比傳統OpenFlow 方案和自適應兩級流表方案，本文方案在負載均衡性能、存儲表項利用和調度指令占用方面都有明顯的改進和較高的可用性。雖然延時緩沖隊列排序會增加一段時延，但對整體網絡性能的提升卻是巨大的，本文中加入的緩沖隊列是靜態設置的，未來的工作將研究在微電網場景下的自適應延時緩沖隊列排序，從而進一步提升性能。