OpenFlow交換機流表溢出緩解技術研究綜述

謝升旭 邢長友 張國敏 宋麗華 胡谷雨

(陸軍工程大學指揮控制工程學院 南京 210007)

自從Mckeown等人[1]提出后，軟件定義網絡(soft-ware defined networking， SDN)技術得到了學術界和產業界的廣泛關注，其架構也在不斷地發展完善.近些年來，隨著云環境的大量部署使用，SDN的熱度進一步增加，并出現了許多較為成熟的商業應用，如谷歌的B4項目[2]，Facebook的開放計算項目(open compute project， OCP)[3]等.得益于其控制平面與數據平面相分離的特點，SDN技術相較于傳統網絡的發展更加具有優勢.然而，作為一種新興的網絡架構，SDN在帶來便利性的同時也引入了新的安全問題[4-5].數據平面[6]、安全通道[7]、控制平面[8]等都存在著大量的安全隱患.在各類安全威脅中，交換機的流表溢出問題是SDN面臨的一個重要挑戰.

現階段，網絡管理和流量調度越來越趨向于細粒度化，同時，SDN大量部署于數據中心網絡和核心網中[9]，這勢必會導致交換機中的流表項數目大幅度地增加.然而SDN硬件交換機受限于有限的流表資源，很容易出現流表溢出問題，使得網絡吞吐量、時延等受到嚴重影響.本文通過深入分析SDN環境中流表溢出問題，詳細介紹了流表溢出造成的影響以及目前緩解流表溢出的相關技術，為有效降低該問題對網絡性能的影響提供支持.

1 背 景

本節主要介紹SDN與OpenFlow協議、三態內容尋址存儲器(ternary content addressable memory， TCAM)的特點及其局限性.同時，通過實驗驗證并分析流表溢出對SDN網絡性能的影響.

1.1 SDN與OpenFlow協議

在當今網絡快速發展的時代，網絡規模不斷擴大，網絡復雜度也持續增加.SDN作為一種全新的網絡架構被提出，用以解決傳統網絡中存在的網絡協議多且實現復雜、流管理靈活度不足以及網絡新業務部署周期長等問題.

SDN被定義為一種轉發與控制分離、軟件可編程的新型網絡體系架構.它將傳統控制平面功能從各個網絡節點中抽象出來，將原來分布式控制的網絡架構重構為集中控制的網絡架構.其基本架構如圖1所示，主要包含3個平面和2個接口：應用平面(application plane)、控制平面(control plane)、數據平面(data plane)、北向接口(northbound interface)以及南向接口(southbound interface).

Fig. 1 Basic architecture of SDN圖1 SDN的基本架構

在SDN架構中，網絡用戶可以通過編程的方式制定網絡管理策略應用，并部署到SDN應用平面.這些SDN應用通過北向接口將網絡行為請求交給控制平面.SDN控制器(SDN controller)在接收到SDN應用的請求后，通過南向接口交給數據平面中的網元(network element)，使得網元能夠正確地處理和轉發數據.同時，控制平面為SDN應用提供底層網絡的抽象模型，包含全局的網絡拓撲視圖狀態以及網元連接事件等.

在眾多南向接口協議中，OpenFlow已經成為既定的標準.OpenFlow作為一種通信協議，將對等的數據平面轉發設備和SDN控制器連接起來，其架構如圖2所示.在OpenFlow v1.3版本中，支持該協議的SDN交換機主要包含3個部分：組表(group table)、流水線(pipeline)以及安全通道(secure channel).其中流水線上的流表(flow table)可以看作為一組策略表項(即流表項)的集合，數據分組在流水線上的多張流表間跳轉進行匹配；組表用來聚合具有相同指令的不同流表項以提高流表的資源利用率；而安全通道則是連接OpenFlow交換機與控制器的接口，用來保護兩者之間的通信不受干擾.

Fig. 2 Architecture of OpenFlow v1.3圖2 OpenFlow v1.3架構圖

圖3描述了基于OpenFlow的SDN環境下網絡流的基本轉變過程，Pkt0和Pkt1是同一條流(首部字段相同)的前2個數據包.當OpenFlow交換機S收到主機1發往主機2的新流的第1個數據包時，該流的處理過程如圖3中點劃線箭頭所示.首先交換機S接收到該新流并進行匹配；在未匹配到相應流表項后，向控制器發送封裝有該流首部信息的packet_in消息；控制器接收到packet_in消息后根據網絡管理策略生成相應的流規則，并向交換機S發送flow_mod消息以下發該流規則對應的流表項；最后，交換機S根據該流表項對流進行轉發等操作.而當交換機收到主機1發往主機2的一條舊流(指交換機中已經安裝有對應的流表項)的數據分組時，該數據分組的轉發過程如圖3中虛線箭頭所示.即交換機匹配到該分組對應的流表項，并根據該流表項的動作對分組進行轉發等操作.

Fig. 3 Forwarding process of flow in SDN environment圖3 網絡流在SDN環境中轉發過程

1.2 TCAM原理及其局限性

線性查找法(linear search, LS)、二叉樹查找法(binary search tree， BST)、散列表(Hash table)查找等傳統的表項查找方法都是基于靜態隨機存取存儲器(static random access memory， SRAM)的軟件查找方法，共同特點是查找速度慢.在這種背景下，基于硬件的TCAM查找方法被提出.在進行TCAM查找時，整個表項空間的所有數據在同一時刻被查詢，查找速度不受表項空間數據大小影響，每個時鐘周期可以完成一次查找.相較于典型的內存搜尋算法，TCAM電路的方式由于平行比對所有儲存數據，從而有效縮短了搜尋的時間.

此外，與傳統的基于內容尋址寄存器(content addressable memory, CAM)相比，TCAM在每個比特位上的狀態不僅包含“0”和“1”，還有另一個由掩碼來實現的“don’t care”狀態.正是由于TCAM的第3種狀態，使得其既能夠進行精確匹配查找，又能夠進行模糊匹配查找，因此被廣泛應用于SDN硬件交換機中[10].

雖然TCAM在匹配能力上比較靈活高效，但相較于傳統隨機存取存儲器(random access memory， RAM)，價格昂貴且耗電量大[11].這導致當前商用OpenFlow交換機只擁有幾千至上萬條流表項的空間[12]，在大規模網絡中部署時SDN交換機容易出現流表溢出現象，進而對網絡性能造成影響.目前網絡安全服務鏈[13]、路由故障恢復[14]等典型SDN應用場景都會受到流表空間不足的影響.

1.3 流表溢出對網絡性能的影響

為了進一步說明流表溢出對網絡性能的影響，我們使用如圖4(a)所示的網絡拓撲，通過主機1至主機4相互之間發送流量造成流表空間溢出.同時，通過主機5和主機6互ping來驗證流表溢出對網絡性能的影響.控制器匹配五元組(源IP地址，源端口，目的IP地址，目的端口，協議),當流表溢出時，采取由控制器packet_in和packet_out機制轉發未能匹配到流表項的新流.

圖4(b)為實驗結果，從圖4(b)中實線可以看出，當流表未發生溢出時，ping時延幾乎為0.而從圖4(b)中虛線可以看出，當流表發生溢出時，ping時延始終在50 ms上下浮動.由此可知，當交換機流表發生溢出時，SDN網絡性能將有所下降.

除上述處理機制外，在SDN硬件交換機發生流表溢出時，控制器也可以采取其他類型的策略，如直接丟棄新流，不下發對應流表項也不進行數據轉發；或者刪除已有流表項來為下發新的流表項騰出空間等.然而，這些方法都會對網絡中的流量造成影響，使得網絡性能下降.本文后續將著重分析目前有效緩解流表溢出而導致網絡性能下降的方法.

2 面向正常網絡流的流表溢出緩解機制

在部署SDN網絡的域間骨干或大型數據中心網絡中往往運行著龐大的流量，而OpenFlow交換機有限的流表空間很可能無法安裝控制器下發的大量流表項條目數.尤其在出現短時間內突然有大量流經過網絡的情況下，流表項更容易出現溢出問題.由于這些流都是網絡中的合法流量，SDN網絡必須高效地進行轉發處理.對于該情況下的流表溢出緩解問題，研究人員主要從2個方面進行了考慮：1)優化交換機流表空間架構及利用率，以避免交換機頻繁發生流表項溢出；2)當發生流表溢出時，設計合理的流表項替換算法，選擇性地剔除舊的流表項，進而為新流表項的下發騰出空間.

2.1 交換機流表空間及利用率優化

2.1.1 流表空間架構優化

SDN硬件交換機流表溢出的根本原因在于受限的TCAM空間大小.因此，通過優化交換機的流表空間，有助于提高支持流表項數量的上限.研究人員提出了一種結合SRAM的串行多級流表架構[15].如圖5所示，該架構在使用TCAM實現流表的基礎上，通過在TCAM尾部增加SRAM，以串行的方式使流表空間得到大大增加.使用該流表架構的交換機在處理到達的新流時，首先在TCAM流表中查找匹配，若沒有對應匹配流表項，則進一步在SRAM的流表中查找.這種串行架構的好處在于，當流量較小時，能優先使用TCAM來快速查找，使流表空間具有很好的伸縮性.

Fig. 5 Multi-level flow table architecture combining TCAM and SRAM圖5 結合TCAM和SRAM的多級流表架構

然而，在該串行架構中，當流數量較多的情況下，平均查表速度將顯著下降.與串行架構不同的是，一種利用TCAM與RAM構造的雙流表空間并行架構CacheFlow被提了出來[16].如圖6所示，該架構基于網絡流量往往遵循Zipf分布的特點(即絕大多數流量與相對較少的規則匹配)[17]，將最常見流的規則存儲在容量較小的TCAM中以達到快速查找、匹配、更新流規則，而將其余的流規則存儲在使用RAM的軟件交換機(硬件交換機中的一部分)中.存儲在TCAM中的流規則相較于RAM中的流規則具有更高的優先級，能優先被匹配.

Fig. 6 CacheFlow architecture diagram圖6 CacheFlow架構圖

由于CacheFlow沒有考慮到在流表溢出時對流表項存儲位置的處理，一種新的MMS(memory management system)架構被提出[18].此外，與Cache-Flow使用位于SDN交換機上虛擬內存機制不同的是，MMS使用的是控制器上的RAM.MMS通過Swap out的方式在流表空間溢出時將最新被匹配了的流表項置換到控制器上的RAM中以及通過Swap in的方式將需要再次匹配的流表項重新安裝在交換機的TCAM中.MMS在有效地擴大流表空間的同時，提高了TCAM流表空間的利用率，但平均查表速度值得通過實驗進行進一步分析.

2.1.2 流表項匹配規則優化

對于OpenFlow交換機來說，流表溢出直接原因在于控制器下發的流表項超過了交換機所能支持的上限.因此，通過對流表項匹配規則的優化，能夠起到減少下發流表項數量的作用.

OpenFlow v1.3作為重要的一個穩定版本，在設計架構上相較于v1.0版本增加了多級流表(multiple flow tables， MFT)的結構[19].MFT在一定程度上減輕了單一流表臃腫的問題，同時也為流表管理帶來了新的途徑.Agg-Extable作為一種多級流表管理方法，能在一定程度上減少流表中流表項數量[20].該方法主要基于2個算法：1)利用剪枝算法剪去流表中的冗余項；2)基于TCAM任意掩碼，利用Quine-McCluskey算法定期聚合多級流表中具有相同動作(action)的流表項.如圖7所示，流表項E1，E2和E4，E5被聚合的同時，掩碼位也進行了調整.與之相類似的工作包括FTRS機制，通過聚合流表項的相同action和匹配域中相同的地址來節省流表空間[21].同時，在SDN網絡中如何快速進行流表聚合[22-23]以及如何確保流表項聚合時保證流表項的依賴[24]都被廣泛的研究.

Fig. 7 Example of aggregation of flow entries based on mask圖7 基于掩碼聚合流表項的示例

相較于流表的管理，Compact TCAM方法在保持SDN交換機對流的動態處理等特性的情況下，能夠通過改變流表項結構而優化流表空間使用[25].如圖8所示，該方法對流的轉發主要分為3步：首先，當流F1:P1到達入口交換機Sin時，控制器根據流的首部信息生成一個特定的FLOW-ID并存儲在控制器的FLOW-ID Table中，然后用FLOW-ID替換該流的首部信息進行轉發；其次，對處在中間鏈路上的交換機Smid下發匹配域為FLOW-ID的流表項，對流進行處理；最后在出口交換機Sout處，將FLOW-ID換回該流原來的首部信息.由于FLOW-ID使用比原始流表項匹配域比特數更短的標記來標識流，因此大大提高了TCAM的利用率.文獻[26]也采用了類似在邊緣交換機上對流首部字段進行改變的思想，提出了一種按需目標地址轉換和源端口轉換的機制.它基于地址修改和端口重寫，主動創造更多可以聚合的流表項.

Fig. 8 Compact TCAM method for new flow processing圖8 Compact TCAM方法對新流處理的流程

此外，Palette方案在保留SDN原有整體語義的情況下，根據匹配域掩碼將流表分解為多個子表并分布式地部署在網絡的不同位置上，同時保證每條流在路徑中對每種類型的子表至少能匹配一次[27]，如圖9所示.Palette方案能夠平衡跨網絡的流表大小，并在不同連接之間共享資源，進而達到降低流表項數量的作用.文獻[28]則提出了一種針對異構流表(不同的控制器應用程序會有不同的流策略，導致所有流的流規則集不盡相同)的流規則劃分和分配算法，同時保證了語義不變.SA(sub-table allocation)和SSP(size-balancing sub-table partition)算法，則被用于平衡子表以及減少規則開銷[29].

Fig. 9 Flow table separation deployment圖9 流表分解部署

2.1.3 流表項超時時間優化

為了能夠使交換機主動且適時地刪除流表項，OpenFlow協議規定了每條流表項都包含一個超時時間(timeouts)組件，用來指明交換機中的流表項在過期之前的最大生存時間量以及最長空閑時間量.控制器需要在向交換機安裝流表項時設置超時時間，包含2個值：hard_timeout和idle_timeout.hard_timeout表示流表項自安裝時起至該時間結束時，交換機會主動刪除該流表項.idle_timeout表示流表項在匹配到數據包后的這段時間內如果未匹配到后續數據包，則會被交換機刪除.

超時時間設置一般分為如表1所示的4種情況，其中a，b為正常數.當hard_timeout和idle_timeout都設置為0時，該流表項不會因超時而刪除；而當hard_timeout和idle_timeout其中一個設置為0另一個設置為正常數時，該流表項的生存時間取決于非零項超時時間；若2個超時時間都設置為正常數時，該流表項的生存時間取決于2個超時時間誰先到期.

Table 1 4 Types of Timeout of Flow Entries表1 4種流表項超時時間設置 s

由于超時時間設置的長短決定了流表項在交換機中存儲的時間，因此，過長會降低流表利用率，過短又會因頻繁的packet_in事件導致控制器-交換機之間的交互增加，如圖10所示.此外，較長的超時時間設置將更容易導致流表項溢出[30].一種簡單的方法是在P4交換機上，通過識別TCP數據包的FIN標記位來判斷TCP連接的最后一個數據包，進而在最后一個數據包得到轉發后，將相應的流表項刪除以減少無效時間，從而提高流表利用率[31].

Fig. 10 Impact of timeout configuration圖10 超時時間配置影響示意圖

在智能動態優化流表項超時時間設置方面，HQTimer機制實現了為不同的流規則分配不同的超時時間[32].該機制包含2個部分：混合超時時間機制和基于Q-learning的適應邏輯.其中混合超時時間機制負責流表項的下發和刪除，而基于Q-learning的適應邏輯負責超時時間的動態決策.HQTimer的實現包含3個模塊：超時決策模塊、流規則下發模塊、流規則刪除模塊.超時決策模塊實現了基于Q-learning的適應邏輯，以流規則下發模塊提供的table-miss規則作為輸入，通過運行神經網絡，為table-miss規則獲取一個適當的超時時間；同時，以流規則刪除模塊提供的已刪除的流規則信息來計算獎勵，在此基礎上對模型進行訓練，該機制的具體實現如圖11所示.文獻[33]則基于Markov模型推測流表項的到期時間，并通過超時時間設置使該流表項在相同的時間內刪除.

Fig. 11 HQTimer architecture diagram and Q-learning logic圖11 HQTimer架構圖和Q-learning邏輯

雖然智能預測算法精確度相對較高，但設計復雜度以及對控制器性能影響都比較大.因此，一些較為簡單的啟發式方法也被用來動態地優化流表項的超時時間.基于網絡中99%的流都是短流(活躍時間不超過0.4 s)這一特點[34]，一種動態超時機制(dynamic hybrid timeout method， DHTM)被設計出來[35].DHTM包含2個方法：動態Hard Timeout方法和動態Idle Timeout方法.默認使用動態Hard Timeout方法，而當不滿足：1)流表空間利用率超過90%；2)沒有足夠的流歷史信息；3)平均持續時間小于2 s；4)已經分類為短流或者非頻繁流這4條件之一時，則使用動態Idle Timeout方法.2個方法設置的動態時間都在基于最小時間(1 s和2 s)的情況下，依據后續流的到達情況以1 s為步進增加或減少超時時間.

IHTA(dynamic Idle-Hard Timeout allocation)算法通過分析分組到達時間的分布也得出了以1 s為初始idle_timeout值[36].不同的是，IHTA對2個超時時間的動態調整考慮了流表空間利用率同時設置了最大超時時間.類似的工作還有，自適應硬超時的方法(adaptive Hard Timeout method， AHTM)[37]以及根據可預測流和不可預測流來分配不同的硬超時時間[38].

與預測流實際生存時間來動態配置流表項超時時間不同的是，根據網絡負載變化情況來動態配置流表項的超時時間.一種是通過預測下一時刻新增流表項數量，再結合網絡當前負載情況，對流表項的超時時間進行動態優化配置，如利用動態指數平滑(DES)模型進行預測的DTO算法[39]以及使用AR進行預測的方法[40]等.另一種則是依據交換機流表使用率變化情況來動態的調整空閑超時時間[41].

2.1.4 基于網絡流路徑優化的交換機流表均衡

網絡一般依賴于嚴格的路由策略(比如最短路徑路由)，這會使網絡中的部分鏈路成為核心鏈路，而核心鏈路上的交換機因流量匯聚導致流表空間使用率大大增加.相反，不依賴于嚴格的路由策略可以更好地利用網絡容量，同時能夠減少帶寬浪費和擁塞事件[2].因此，對網絡流路徑優化可以在一定程度上緩解流表溢出問題.目前該研究主要分為2類，即基于全網流的路徑優化和基于核心節點流的重定向.

1) 基于全網流的路徑優化

如圖12所示，1個網絡共有8個交換機、2個出口鏈路(南北)和2個入口鏈路(東西).當A，B這2個流需要到北向出口而其他流需要到南向出口時，3個子圖分別代表了3種路由策略下的流表項數量情況.圖12(a)使用最短路徑路由策略，在網絡中共安裝了15條流表項.圖12(b)則使用最小化流表項數量策略，共安裝了9條流表項，但帶來的是A，B流的路由跳數增加.圖12(c)則表示在每個交換機僅僅只有2個流表項空間大小的約束下，網絡仍能對流進行路由轉發.由此可以看出，在交換機流表空間大小的約束條件下，可以通過網絡流路徑優化來減少交換機中流表項數量.

Fig. 12 Example of the routing policy圖12 路由策略示意圖

基于這種全網流的路徑優化思想，軟件定義自適應路由(software-defined adaptive routing， STAR)策略利用SDN具有全網拓撲視圖以及靈活的網絡控制特性對網絡流量進行路由規劃[42].該策略通過全網所有SDN交換機流表利用率的實時檢測，對于入網的新流根據交換機流表利用率情況選擇合適的路徑通過網絡，以避免因流表溢出帶來的網絡性能下降.而多項式時間的啟發式算法OFFICER被提出用來找出不同的路徑以滿足在不顯著增加路徑長度的情況下提升網絡流的承載能力[43].此外，文獻[44]提出的“big switch”概念，將全局的高級策略映射到網絡中每個交換機的等價低級流規則集，來對交換機的流表資源進行整體分配.

然而，在結合路徑優化和流表項聚合問題上，由于采取去中心化路由(decentralized routing， DR)(DR表示路由分布在整個網絡中，且大多數路由經過的鏈路不重合)可以實現流表均衡，使平均時延最小化，但不利于流表項的聚合.而采取中心化路由(centralized routing， CR)(CR表示路由集中在網絡中，大部分路由都經過相同的鏈路)會導致平均傳輸時延增加，但可以聚合更多的流表項以節省流表空間.對此，文獻[45]提出了一種整型線性規劃方案(integer linear program， ILP)，用來均衡傳輸時延和流表空間利用率，同時提出快速啟發式ORWFA算法來實現最優折中.

2) 基于核心節點流的重定向

在網絡中，流表溢出大部分時間都發生在部分核心節點上，因此解決核心節點上交換機流表空間的利用問題不失為一種有效的緩解方法.FTS架構的提出可以用來緩解網絡中部分交換機流表溢出問題[46-47].該架構針對流分布不均勻的現象，將流表負載過重的交換機中觸發table-miss事件的流(新流)隨機轉發給鄰近負載較輕的交換機進行精確匹配處理.如圖13所示，圖13(a)展示了經典架構下當S2交換機流表空間已滿時對新流的處理情況，圖13(b)則展示了FTS架構處理情況.在經典架構下，當一條新流到達流表空間已滿的S2交換機，packet_in消息將觸發控制器刪除交換機已有的流表項進而下發針對該流的流表項，這會導致原本活躍的流的轉發被迫中斷.而在FTS架構下，當新流到達S2交換機，如果流表沒有溢出，則轉發至控制器；若流表溢出則將新流隨機轉發至源端口以外的某一端口.由此可見，FTS在交換機發生流表溢出的情況下保證了原有活躍流的通信質量.

Fig. 13 Normal architecture and FTS architecture圖13 經典架構和FTS架構

在FTS架構的基礎上，采用路由松弛策略可以最大化流量效率[48].即在流表空間已滿的交換機中，保留大流的流表項，而將小流通過默認(default)流表項轉發至其他交換機進行精確匹配.

雖然將流從飽和的交換機中重定向至有足夠空余流表空間的空閑交換機可以有效地緩解流表溢出問題.但是，該方法的性能依賴于空閑資源的數量，當沒有足夠的空閑交換機來滿足大量流時，容易導致全網交換機受流表溢出的影響.

2.2 流表項替換策略優化

在不改變網絡其他配置的情況下，為了緩解因交換機流表空間緩存溢出而導致網絡性能下降的問題，研究人員提出了多種流表項替換策略，即按照特定的規則刪除交換機中已有流表項，以便為新流表項的下發騰出空間.

2.2.1 被動替換策略

被動替換策略的核心思想在于，只有在交換機流表處于飽和狀態且發生新流到達事件時，控制器才會選擇刪除一條已有流表項并為該新流下發對應的流表項.最典型的工作是OpenFlow協議1.4版本[49]增加了對流表滿載情況的處理機制，控制器對下發的流表項設置不同的重要度(important)值，進而允許OpenFlow交換機在流表發生溢出時可以刪除那些重要度值較低的流表項.

典型的流表項刪除策略，包括最近最少使用(least recently used, LRU)、先進先出(first in first out, FIFO)和隨機(random)[50].研究發現FIFO刪除策略比LRU要差，但優于隨機策略[51].

在流表溢出時，為了更好地選擇出最適合刪除的流表項，結合近些年較為熱門的機器學習思想，一種基于機器學習的剔除方法(machine learning based eviction approach， MLBEA)被用來找出并剔除不活躍的流表項[52].該方法以五元組(源IP地址，源端口，目的IP地址，目的端口，協議)定義流，通過數據流的協議、流表項未匹配時間長度、平均包間隔以及最后N個數據包的長度4個特征組成的向量，使用UNIV，UNIBS等網絡數據集進行離線訓練隨機森林分類器，并將訓練結果通過在線仿真的方式進行驗證.結果顯示，基于機器學習選擇合適流表項進行刪除的方法要遠好于LRU方法.

與MLBEA高復雜度相比，短流優先策略(short flow first， SFF)要簡單得多[53].SFF動態標記流表項是長流還是短流，在流表發生溢出時，選擇短流表項進行刪除替換，并使長流能夠提供更長時間的匹配.具體動態標記的方法如圖14所示.①首先將到達交換機的新流所對應的流表項標記為短流.②如果該流表項在被刪除之前與第2個到達的包匹配，則將該流表項標記為長流，同時設置最大等待時間(maximum waiting time， MWT)，其中t為2次匹配的時間間隔，α為權重因子.③在最大等待時間內若沒有再匹配到數據包，則將該流表項重新標記為短流.④被重新標記為短流后，如果再次匹配到數據包，則重新將流表項標記為長流，同時更新匹配時間為t′.實驗顯示，SFF策略比FIFO，LRU的替換刪除策略都要好.

Fig. 14 Flow identification in SFF scheme圖14 短流優先策略中流的鑒定方法

2.2.2 主動替換策略

被動替換策略具有實現簡單等優點，但由于流表項的替換發生在交換機流表溢出時，此時需要消耗大量時間來找出相應需要刪除的流表項，因此會大大增加新流的處理時延，導致網絡性能不太理想[54].為了解決溢出時替換造成的時延增大問題，需在流表項將要發生溢出之前，通過流的篩選策略，提前剔除流表空間中的一部分流表項，以供即將到達的新流使用.一般分為2種方式：

1) 設定流表空間使用閾值

即當流表空間使用率超過一定閾值時，刪除特定流表項.如一種基于隱Markov模型(hidden Markov model, HMM)的流表項主動剔除方案，在流表空間超過閾值時通過HMM選出最低匹配概率的流表項并刪除，直到流表利用率下降到閾值以下[55].此外，研究發現閾值大小的設定會對網絡性能帶來一定的影響.當閾值設置較低時，流表可用空間增加，但會導致頻繁地用新流表項替換舊的流表項而帶來額外的開銷，因此閾值可以與數據包的到達速率成反比；同樣的，在一段時間內到達的數據包數量增加是因為網絡中主機增加導致，因此閾值可以與主機數量成反比[56].

2) 對流表溢出進行預測

即當預測到流表即將要發生溢出時，刪除特定流表項.如，基于流表項溢出預測的CPD架構[57].如圖15所示，該架構包含3個模塊：流表狀態采集模塊(flow table state collection)、新流預測模塊(predict module)、流表項刪除模塊(delete module).流表狀態采集模塊負責采集各個周期內流表空間使用情況，包括流表空間總大小和剩余流表空間大小.新流預測模塊負責使用泰勒級數通過各周期內統計的packet_in數量預測下一個采樣周期新流到達的數量.流表項刪除模塊則是根據預測新流數量與流表空間使用情況判斷下一周期內是否會出現流表溢出問題，若流表會出現溢出，則刪除最不可能再被匹配到的流表項.

Fig. 15 The architecture of CPD圖15 CPD架構示意圖

3 面向攻擊行為的流表溢出緩解機制

由于流表溢出對網絡性能會產生重要影響，因此越來越多的研究開始關注于流表溢出攻擊及其防御策略.網絡攻擊者可以通過網絡探測手段獲取SDN交換機的相關配置、控制器網絡管理策略以及網絡拓撲等信息.基于這些信息，攻擊者可以設計發起針對SDN交換機的流表溢出攻擊.從攻擊流的角度區分，這類攻擊主要分為2種形式：一般性攻擊流和精心設計的低速率攻擊流.與正常網絡下的優化技術相比，針對流表溢出的攻擊，必須能夠有效地檢測出攻擊并進行遏制，否則即使再優的方案，攻擊者也總能使流表空間被攻擊流占滿.本節將以流表溢出攻擊為背景，首先介紹相關網絡探測手段，進而分別介紹一般性攻擊流和低速率攻擊流情況下的緩解方案.

3.1 網絡配置信息探測

在SDN網絡環境中，網絡配置信息探測一般分為2種方式：1)控制器感染，即攻擊者通過病毒、SQL注入等形式獲得SDN控制器的相關權限來獲取相關配置信息；2)網絡測量，即攻擊者通過向網絡中發送特定的探測流來獲取相關配置信息.控制器作為SDN網絡的核心部件，被感染則意味著攻擊者可以獲取網絡的任意信息[58].相較于控制器感染，通過網絡測量獲取網絡配置信息具有實現較為容易、不易被發現等優點，已經成為攻擊者獲取網絡配置信息的主要手段.本節主要介紹通過網絡測量的方法獲取流表項生存時間配置、流規則配置、流表容量及其使用情況等信息.

3.1.1 流表項超時時間及流規則配置探測

若流表項超時時間設置較長，攻擊者將有足夠的時間通過惡意流量使交換機流表空間占滿.因此，文獻[59]研究了攻擊者如何通過向網絡發送構建的數據包，來探測控制器對流表項idle_timeout和hard_timeout的配置以及流規則配置情況.探測示意圖如圖16所示，由于新的數據流(控制器流規則下的不同流)在SDN網絡中沒有對應流表項，需要通過packet_in和flow_mod消息下發對應流表項，這就使得新流的往返時延(round-trip time， RTT)要遠大于直接匹配到流表項的流.因此攻擊者通過控制發送數據包的間隔以及每個數據包的RTT時間大小來判斷超時時間設置，如圖17所示.圖18則給出了匹配域的掩碼推測示例.

Fig. 16 The processing of probing timeout configuration圖16 探測流表項超時時間配置示意圖

Fig. 17 Inference of timeout period圖17 超時時間推測示意圖

Fig. 18 Inference of match field of flow entry圖18 流表項匹配域掩碼推測

3.1.2 流表容量及使用情況探測

交換機支持的最大流表項數量直接決定了攻擊者短期內需要發送攻擊流數量的下限，因此流表容量探測對于攻擊者來說顯得尤為重要.一種利用流RTT大小變化情況進行推測的方法，可以推斷出在流表溢出時使用基于FIFO和LRU的流表刪除規則的OpenFlow交換機的流表容量以及使用情況[60].圖19給出了該方法基于FIFO的流表空間推測示意圖，其中ABCD為流表空間的4種狀態，菱形填充的小矩形為正常流占用的流表空間，斜線填充的小矩形為攻擊者發送的探測數據流占用的流表空間，空白部分為剩余未使用的空間.探測分為3個步驟，首先在起始狀態A的情況下，向網絡中不斷注入探測流到狀態B；其次，當發現發送的新流的RTT增加時，說明控制器進行了流表項FIFO的刪除動作，因此可以判斷到達狀態C，即流表空間已被占滿；最后，隨著探測流的不斷注入，當有已經注入的流的后續包出現RTT突然增大時，說明到達狀態D，即流表空間全部被探測流的流表項給占滿.在整個探測過程中，攻擊者始終記錄著探測流的數量，因此在到達狀態D時可以推斷出流表空間大小，再結合狀態C可以推斷出流表空間的使用情況.

Fig. 19 Inference of flow table space based on FIFO圖19 基于FIFO的流表空間推測示意圖

3.2 一般性攻擊

若攻擊者需要消耗整個網絡的流表資源而不是單個交換機的流表資源，則意味著它們必須提高攻擊流的請求速度或延長攻擊的持續時間，這2種方法通常代價都非常高.利用該攻擊特點而設計出的基于QoS感知的緩解策略(即對等支持策略)可以有效地緩解這種類型的流表溢出攻擊[61].該策略在交換機流表空間滿狀態時，通過向交換機下發帶有通配符的流表項，引導流量到對等的路徑上.因此該策略集成了整個SDN系統可用的空閑流表資源，能夠在遭受流表溢出攻擊時，使網絡可以維持更長的時間以及更易檢測流表溢出攻擊.

此外，通過網絡拓撲分析最有可能被攻擊的目標交換機(中間節點交換機Smid)可以在保證檢測精度的情況下提高檢測效率.例如，文獻[62]通過使用外部流消耗增長(growth of foreign flow consump-tion， GFFC)、流量偏差(deviation of amount， DFA)、流進入的共性(commonness of flow entry， CFE) 3個指標對攻擊進行檢測，并使用令牌桶模型(token bucket model， TBM)進行限速.對于檢測出的攻擊端，通過令牌桶限制控制器下發流表項的速度，以避免流表空間被占滿.如圖20所示，當Smid這個中間交換機通過3個指標檢測出攻擊端Sattack時，通過控制器中的令牌桶限制從Sattack到達的流的對應流表項的下發速度.

Fig. 20 Limit the speed of flow entries installation圖20 限制流表項下發速度示意圖

該緩解方法的不足在于，當網絡中惡意用戶的數據流不斷增加，整個流表空間會被耗盡，使得正常用戶的數據流可能會遭受流表不足的問題.為此，一種基于行為優先級感知的防御策略——FTGuard被設計提出[63].如圖21所示，FTGuard架構中流量特征采集(traffic feature collection)模塊用于采集數據信息，包括新流的到達頻率、每個流的包數量，然后再通過評價分值計算(evaluation score calcu-lation)模塊計算分值，最后通過優先級配置(priority encapsulation)模塊依據分值對不同用戶的流分配不同的優先級.當流表滿時，優先級最低的流條目會被刪除，為下發新流的流表項提供空間.

Fig. 21 The architecture of FTGuard圖21 FTGuard架構示意圖

此外，文獻[64]分析了流表溢出攻擊的2種攻擊手段：控制器中惡意APP和網絡數據包，并提出了基于事件處理的剔除模型.該模型實現了對每一個新的數據包的分析，并通過日志驗證源地址，對于黑名單中的源地址，將刪除超過一定流量閾值的流，以保證正常用戶數據流的正常通信.

3.3 低速率攻擊

相較于一般性的流表溢出攻擊，低速率流表溢出攻擊的攻擊流是經攻擊者精心策劃過，即以最少的攻擊流造成交換機流表溢出，相對于傳統的攻擊方式進一步增加了檢測難度.

基于低速率拒絕服務攻擊(low-rate denial-of-service， LDoS)特點以及OpenFlow流規則特性，研究人員提出了低速率流表溢出攻擊機制(low-rate flow table overflow attack， LOFT)[59].攻擊方式如圖22所示，假設其中Pi表示第i條攻擊流的數據包，idle_timeout為10 s，hard_timeout為15 s，交換機最多能夠支持5條流表項.圖22(a)中對于特定的idle_timeout設置，攻擊者通過每隔2 s在idle_timeout內發送足夠使交換機流表發生溢出的攻擊流數量(圖22中5條新流，分別為P0至P4)，這些流再以idle_timeout為周期進行發送，則會始終導致交換機流表空間處于溢出狀態.圖22(b)中，若同時設置了idle_timeout和hard_timeout，則攻擊者可以在idle_timeout時間內發送足夠的攻擊流的同時以hard_timeout為周期，重復發送攻擊流.對于該方式的攻擊，作者提出了2種可行的防御方案：1)在數據流的頭幾個包的傳遞過程中加入適當的時間抖動，例如控制器在接收到packet_in消息后不立即為新流下發流表項；2)使用動態的超時時間值.

Fig. 22 Diagram of LDoS attack in two cases圖22 2種情況下的LDoS攻擊示意圖

4 分析及研究展望

4.1 分 析

面對OpenFlow交換機流表溢出問題，雖然已經從流表空間架構、流表項匹配規則、流表項刪除替換等眾多方面進行研究，但都不可避免地對網絡性能造成影響，或是對OpenFlow相關軟硬件進行了修改，這在一定程度上削弱了SDN網絡的能力.在此，本節對幾類代表性的交換機流表溢出緩解方法進行比較分析.

由于不同的流表溢出緩解方法的效果評估方式具有差異性，例如有些使用網絡數據集[49]，有些則使用自定義的仿真環境[36]等.因此，為了更加直觀分析各流表溢出緩解方法的特點，我們從網絡性能(通信時延、鏈路負載)、對交換機額外的修改、控制器模塊、控制器負載影響、OpenFlow協議更改等多個方面做了統計，結果如表2所示(比較是在正常通信且流表未發生溢出的情況下進行的).

分析表2可以發現，流匹配規則優化中的流表聚合方法(Agg-Extable， FTRS)會因流表項匹配域字段的掩碼位數增加而導致流管理精細度下降，而更改匹配字段(Compact TCAM， Palette)需要對OpenFlow協議規定的流表項匹配域進行修改；流路徑優化機制中流的重路由實現方法(FTS，STAR)，都會因為流需要經過的鏈路數增加而導致網絡時延增加同時平均鏈路負載加重；而在使用主動/被動流表項刪除、針對流表溢出攻擊的緩解機制實現中，因需要采集交換機中統計字段信息以判斷流表空間是否將要溢出、流表項是否活躍以及網絡中的流是否是攻擊流，這些都會因為頻繁數據請求增加控制器與交換機之間的通信量使得安全通道負載加重，從而影響SDN網絡性能.

4.2 研究展望

隨著SDN網絡的大量應用部署以及網絡流量不斷增多的趨勢，OpenFlow交換機流表溢出是一個迫切需要解決的問題.結合SDN特點、新技術發展以及應用部署等方面，未來工作可以考慮5個問題：

1) 應用感知的流表溢出緩解機制設計

SDN通過在集中的控制器上部署各種SDN應用程序來實現對網絡的靈活管理.在流表溢出緩解機制的方案實現中，大多需要在SDN應用平面安裝相應的SDN應用，以對數據平面的相關信息進行采集和實現相應的流表管理，如信息采集包括流表空間使用率[57]、流表項匹配信息[63]等，流表管理包括進行流表項的修改以實現流表項聚合[20]、流的重路由[47]、刪除不活躍流表項[55]等.而SDN應用平面上安裝流表溢出緩解應用時，需要考慮與其他各種SDN應用程序(如QoS、流量工程等)有無策略沖突.例如QoS應用將某流設定為高優先級，而流表溢出緩解應用判斷其為不重要的流從而優先刪除或重定向.在以后的工作中需要解決這類策略不一致性問題.

Table 2 Comparison of Flow Table Overflow Mitigation Methods表2 流表溢出緩解方法比較

2) 降低流表溢出緩解機制對網絡的整體影響

已有的優化方案在實現過程中或多或少對SDN網絡都有一定的影響，如通過流表項聚合減少流表空間占用的同時會使網絡流管理的細粒度降低[20]、路由優化中的流重定向以均衡流表空間負載的同時增加了鏈路負載和時延[44]等.以后的研究中，可以綜合考慮流管理細粒度、鏈路帶寬、時延、安全通道負載等性能的影響，并結合多種機制提出新的緩解方案.在緩解OpenFlow交換機流表溢出問題的同時進一步降低對SDN網絡整體性能的影響.

例如，從網絡拓撲的角度出發，通常情況下，流表溢出發生在網絡中的核心節點交換機上，因此研究網絡中不同位置的交換機使用不同細粒度的流匹配規則，使網絡既能保證相應流能夠獲得精確的統計信息，又能減輕核心節點交換機流表負載，同時不影響網絡通信性能.

3) 運用新技術解決流表溢出問題

OpenFlow交換機容易發生流表溢出問題的根本原因在于其使用了TCAM從而導致流表空間嚴重不足.而若嚴格按照OpenFlow協議標準，流表的實現只能使用TCAM.因此，提高單位功耗單位價格的TCAM容量是一個值得研究的方向.

結合P4等技術的發展[65]，未來可以研究改進OpenFlow相關協議，例如在使用P4交換機時，增加交換機流表項主動刪除判定條件以便及時刪除無效流表項；增加交換機相關統計字段主動上報，以便分析相應流的特性，從而在進行流表優化的同時能夠減少信息采集量.

此外，可以利用機器學習相關算法來應對流表溢出問題.在正常網絡環境中，機器學習算法已經有了很好的應用，如通過強化學習算法判斷流表項合適的超時時間值[32]、使用隨機深林算法選出最不活躍的流表項進行刪除[52]等.未來，可以研究智能算法用在流表空間溢出預測、流表空間溢出攻擊流識別等其他領域.

4) 針對流表溢出的攻擊行為進行研究

在正常網絡中，流表空間可以通過優化方案提升承載能力，但在面向流表溢出攻擊的情形下，優化方案只能治標不能治本.這部分的研究目前整體偏少.未來研究可以從2個方面出發：

首先，可以在網絡配置信息探測層面進行阻斷或提高探測難度.包括：①通過SDN網絡拓撲混淆技術[66]，阻止攻擊者通過分布式攻擊流使某些核心節點交換機流表發生溢出；②使用動態隨機的流表項超時時間以及不同粒度的流處理規則，可以有效增加攻擊者發送針對性攻擊流難度，從而使攻擊更容易被檢測出來；③由于流表容量和使用情況探測是基于RTT時間變化進行推測，因此可以對網絡流適當增加時延抖動，以提升攻擊者的分析難度.

其次，需要研究針對流表溢出的攻擊流典型模式，尤其是低速率攻擊.包括：①不同流占用多個流表項空間的情況，可以從流首部信息、流路徑分布、新流到達速率等角度考慮；②相同流占用一個流表項空間的情況，可以從流的不同數據包大小分布、到達時間分布等角度考慮.這部分研究有利于在未來提出更有效的攻擊檢測方案，進而可以有效抑制攻擊.

5) 在實際環境中部署進行效果驗證

目前大多數流表溢出緩解機制都只停留在學術研究上，或者在實驗仿真環境中進行了實現，如使用非SDN網絡的流量數據集進行流匹配預測、使用Mininet工具生成仿真SDN環境等.這些實驗方法雖然可以在理論上對方案效果進行驗證，但在真實SDN網絡環境中會存在各種難以預知的情況，尤其是在網絡節點數量、網絡流總量都十分巨大的場景下.如何保證所提出的流表溢出方案在真實SDN環境中能夠平穩有效運行，在未來是值得驗證評估的.

5 總 結

在SDN網絡環境中，若OpenFlow交換機流表發生溢出，會導致網絡時延、吞吐量等性能下降.而商用OpenFlow交換機考慮到TCAM的功耗、價格等原因，其能夠支持的流表空間大小十分有限，導致OpenFlow交換機面臨嚴重的流表溢出問題.同時，隨著近些年來SDN的廣泛部署，OpenFlow交換機流表溢出問題在TCAM架構、流表均衡、OpenFlow機制以及流表溢出攻擊等方面得到廣泛的研究.本文對本領域目前的相關工作進行了綜述分析，對SDN環境下OpenFlow硬件交換機基于TCAM的流表溢出問題進行了深入探討，并對下一步的研究趨勢進行了展望，以期為解決交換機的流表溢出問題提供進一步的研究支撐.