SDN 中基于時延優化的多控制器部署方案

張聯鎮，黃傳河＋，曾毓瓏，張 海，賈永宏

（1.武漢大學 計算機學院，湖北 武漢430072；2.華為技術有限公司，廣東 深圳518129）

0 引 言

軟件定義網絡［1］（software－defined networking，SDN）技術將網絡的控制平面與數據平面分離開來，其可編程特性使我們能夠動態地配置并管理整個網絡。在SDN 中，控制器負責整個網絡的集中化控制，對于把握全網資源視圖、改善網絡數據交付都具有非常重要的作用。隨著SDN 在大規模網絡中的部署［2］，單一集中式的控制器已無法滿足來自全網所有交換機的流處理請求，SDN 在大規模網絡中的部署面臨著來自控制平面擴展性方面的嚴峻挑戰［3］。目前，解決SDN 面向大規模網絡部署的趨勢是，通過分布式的方式，將多個控制器部署到多個控制域內，形成一個分布式的管理控制平面，各控制器之間進行協同式工作［4］。然而，這樣一來也帶來了一些新的問題：對于一個給定的網絡拓撲，需要部署多少個控制器，以及如何部署這些控制器才能在優化流表建立時間的同時獲得較小的控制器之間的同步時間開銷。

1 相關工作

關于多控制器的部署問題，國內外已有相關的研究，文獻 ［5］中提出基于平均時延和最壞情況傳播時延的控制器部署衡量指標，并在真實的網絡環境中分析了其對控制器部署的影響。文獻 ［6］提出了一系列的控制器部署算法，以最大化SDN 的可靠性作為控制器部署標準。文獻［7］分析了SDN 中，影響多控制器部署的不同類型的彈性衡量指標之間的權衡問題，并提出了一個彈性的基于帕累托分布的控制器優化配置構架方案，以解決多控制器的部署問題。在所有以上提出的解決方案中，并沒有直接考慮到控制器與控制器之間的同步時延開銷。控制器之間需要定期進行信息同步，以便各控制器維持一個全局的網絡狀態信息，當網絡規模較大，控制器數目較多時，控制器之間的同步開銷將是控制器部署過程中需要考慮的重要因素之一。

與上述方案相比本文首先評估對于給定的網絡拓撲其所需部署的控制器的個數，在使用基于聚類思想的控制器部署方法，根據最小平均時延的原則將控制器初步部署到網絡中之后，向網絡中輸入動態數據流，通過最小化網絡的流表建立時間和控制器間的同步時延開銷來進一步優化控制器的部署。我們將這一優化問題看作是整型線性規劃問題，并提出了一種元啟發式搜索算法來解決這一問題，以便在優化流表建立時間的同時獲得較小的同步時延開銷，從而實現對兩者的權衡，并確定控制器的最終部署位置。

2 控制器部署模型描述

在SDN 中，當一個新的數據包到達交換機時，交換機首先檢查其流表，看是否有匹配的流表項，如果查找到匹配的流表項，交換機根據流表項規定的操作進行相應的轉發，如果沒有查找到匹配項，交換機便會向控制器發送一個packet－in路徑請求消息，以獲取轉發路徑。控制器通過其維持的網絡拓撲信息，為該數據包計算本域范圍內的轉發路徑，并將轉發規則下發安裝到與該路徑相關的交換機的流表中。此時存在兩種情況，當此數據包的目的地 （這里所說的目的地指的是交換機，另外，下文所提到的源目的地址除特別說明之外，都指的是交換機）在本控制域范圍內時，與該轉發路徑相關的各交換機按照指定的轉發操作將數據包轉發至目的地；而當目的地不在本域范圍內時將涉及到跨域通信問題，如圖1所示，當控制域D1內的交換機i收到一個新的目的地址為控制域D2內的交換機l的數據包時，如果沒有相應的匹配項，交換機i就向控制器c1發送一個路徑請求消息。控制器c1為此數據包計算本域內的轉發路徑，這里我們假定轉發路徑為i→j，然后將轉發規則下發給交換機i和j。此時數據包由交換機i轉發至交換機j，最終由交換機j轉發至交換機k。交換機k收到此數據包后，檢查其流表，如果沒有匹配項，交換機k就向控制器c2發送路徑請求消息，控制器c2以同樣的方式為此數據包計算轉發路徑，并將轉發規則下發給交換機k和l，最終該數據包被轉發至目的交換機l。整個轉發過程中經歷了兩次路徑請求，4次流表下發的過過程。

定義1 為了便于描述，將網絡拓撲等效為一個連通圖

圖1 跨域數據包轉發流程

G （V，E），V＝ ｛1，2……，N｝表示交換機集合，E 為交換機之間的鏈路集合，N＝｜V｜為交換機個數，m 為所需部署的控制器數，C ＝ ｛c1，c2，…cm｝表示控制器集合，d （i，j）表示交換機i與交換機j之間的最短路徑時延。Tv表示交換機流表的生存時間，Pc表示控制器c每秒能夠處理的最大路徑請求次數，我們假定所用到的各個控制器的處理能力是相同的。

在向G 中部署控制器時，我們假定每一個交換機所在的位置都有可能成為控制器的部署位置，即控制器部署在交換機所處的位置上，但控制器與交換機并不重合放置，且控制器部署位置所對應的交換機在該控制器所管理的交換機范圍內，它們之間的時延忽略不計。

定義2 δ表示控制器與交換機之間正常通信所允許的最大通信時延，Mc＝ ［［Miij］］N×N表示T 時間內控制器c收到的平均路徑請求矩陣，其中Mij表示T 時間內交換機i與交換機j進行通信時產生的平均路徑請求次數。Lij表示交換機i與交換機j通信時所經過的交換機的集合，交換機i與交換機j也包括在內。R ＝ ［Ric］N×k表示交換機分配矩陣，其中Ric＝1表示交換機i被分配給控制器c，否則Ric＝0。

在向網絡中部署多控制器時，會產生很多類型的時延開銷，本文主要考慮流表建立時間和控制器之間的同步時延開銷。我們將流表建立時間分為兩個部分：請求路徑時延，如圖1中①和④所示；流表下發時延，如圖1 中②、③、⑤和⑥所示。對于控制器c來說，T 時間內其域內的總的請求路徑時延Dcreq為

其中k為第一個滿足k∈Lij且Rkc＝1的交換機，則整個網絡的路徑請求時延Dreq為

T 時間內，控制器c所在域內的流表下發時延Dcdis為

則整個網絡的流表下發時延Ddis為

通過式 （2）和式 （4）可以得到總的流表建立時間Df

在多控制器環境下，控制器之間需要進行信息同步，以便各控制器維持一個全局的網絡狀態信息。我們假定控制器間每隔Ta時間進行一次同步更新，則控制器之間進行同步的時延Dsyn為

通常，在控制器的部署過程中，為了提高整個網絡的性能，我們總希望網絡的流表建立時間盡可能短，控制器之間的同步時延開銷盡可能的小。因此，本方案需要實現流表建立時間與控制器之間的權衡，我們將這一問題看成是一個求最小值的優化問題，待優化的目標函數Fmin為

式中：λ——常量系數，且滿足0≤λ≤1，其值可以根據網絡對各時延的要求比重不同進行設定。優化過程中必須滿足的約束條件如下

其中式 （8）表示每一個交換機都只由一個控制器控制，式（9）表示任意交換機與控制器之間的時延必須在其上界之內，式 （10）表示確保每一個控制器都能夠處理來自本域內的所有交換機產生的路徑請求數，式 （11）表示交換機k是否分配給控制器c，若是，則為1，否則為0。

3 控制器部署方案

本部分首先評估給定網絡拓撲所需部署的控制器的個數，然后通過基于聚類思想的控制器部署方法，根據平均時延最小的原則將控制器初步部署到網絡中，再向網絡中輸入動態數據流，分析各控制域內控制器收到的平均路徑請求次數，對請求次數超過控制器所能處理的域進行調整，最后運用蜂群算法思想以最小化Fmin為目標進一步優化控制器的部署，從而確定控制器的最佳部署位置。

3.1 控制器個數的確定

根據式 （12）我們可以近似地得到所需部署的控制器個數m 為

式中：α——一個常量系數，網絡管理人員可以根據需求進行相應的設定。

3.2 基于聚類的控制器部署方法

我們將控制器部署問題類比為聚類分析問題，每一個聚類好比一個控制域。本文假定每一個域內有且只有一個控制器。我們使用基于聚類的控制器部署方法將控制器初始的部署到網絡中，把每一個聚類的中心作為控制器的部署位置，使用平均時延作為選取聚類中心的評判標準，每一個聚類的平均時延Lavg為

其中j表示聚類的中心位置，Rij＝1，表示交換機i屬于以j為聚類中心的聚類，Rij＝0，表示交換機i不屬于該聚類。

為最大限度消除初始控制器部署位置對最終聚類結果的影響，加快其收斂速度，將交換機集合V 按照度的大小進行降序排列，選擇度較大且距離相對較遠的m 個交換機所在位置作為控制器的初始部署位置，執行步驟如下：

步驟1 將選好的m 個交換機所在位置作為集合C 中控制器的初始部署位置；

步驟2 遍歷剩下的N－m 個交換機，根據距離最短原則將交換機分配給距其較近的控制器，形成m 個控制域；

步驟3 遍歷每個控制域內的所有交換機，根據式（14）計算Lavg的值；

步驟4 選取使得Lavg值最小的交換機所在位置作為域內控制器的新的部署位置，形成新的控制器集合C；

步驟5 不斷重復步驟2～步驟4，直到控制器集合C不再發生變化。

3.3 控制器部署優化

在基于聚類的控制器部署方法的基礎上，向網絡中輸入動態數據流，根據蜂群算法［8］思想，以最小化式 （7）為目標，進一步優化控制器的部署。由于使用基于聚類的控制器部署方法得到的結果可能存在某些域，其域內交換機產生的總的路徑請求次數超過控制器能夠處理的數目，因此在進一步優化前，需要對每一個域進行檢測，對超出控制器處理能力的域作出相應的調整。對于路徑請求次數超過控制器處理能力的控制域，不斷將域內產生路徑請求次數最多的交換機分配給其它能夠處理這些請求的控制器，直到域內的路徑請求總數在控制器的處理能力范圍之內，其域內的每一個交換機i所產生的路徑請求次數Sireq為

具體的調整策略步驟如下：

步驟1 分析每一個控制器收到的平均路徑請求矩陣，將不滿足約束條件式 （10）的控制器加入到控制器集合Cu中；

步驟2 初始化鏈表list為空，從集合Cu中取出一個控制器c，將控制器c所在域內的所有交換機按照式 （15）計算后進行降序排序，并放入list中；

步驟3 從list中依次選擇交換機i，將i分配給剩余處理能力與i所產生的路徑請求次數相近的且i與其之間的時延小于δ的控制器；

步驟4 重復步驟3，直到控制器c能夠滿足約束條件式 （10）為止；

步驟5 重復步驟2～步驟4，直到集合Cu為空。

用調整好后的交換機分配信息來初始化交換機分配矩陣R，并重新計算每一個域內的路徑請求矩陣，為進一步優化工作做好準備。多控制器部署優化問題與蜜蜂采蜜行為對應關系見表1。

表1 多控制器部署優化問題與蜜蜂采蜜行為對應關系

假 定 初 始 蜂 群 B 的 總 數 為Z， 則 有 B ＝（b1，b2，…，bi，…，bZ），其中bi＝ （ci1，ci2，…cim），稱其為第i個可行的控制器部署解，每一個解都是一個m 維向量，m 為所需部署控制器的個數。為加快算法的收斂速度，首先根據基于聚類的控制器部署算法得到的控制器的初始部署位置初始化蜂群B，即將初始控制器部署的位置集來初始化B 中的一個解，并依次從每一個控制器c的初始部署位置附近隨機選取一個位置作為B 中的下一個解，直到B中的Z 個解都被初始化。B 中每一個解的收益度函數為

式中：Fimin——第i個解所對應的Fmin的值，收益度越高，Fmin的值越小。我們使用輪盤賭的方式來決定跟隨蜂轉變為引領蜂的概率，其概率公式為

偵查蜂根據以下3種方式進行蜜源的搜索：

方式1：從 ［1，m／2］中隨機選取一個整數作為隨機選取解的分量個數，在每一個被選分量對應的控制器所部署位置的h跳范圍內隨機選取一個控制器部署位置，形成一個新的蜜源位置，計算新的蜜源的收益度，如果大于原來的收益度，則用新的位置代替原來的位置，否則什么也不做。

方式2：從 ［m／2，m］中隨機選取一個整數作為隨機選取解的分量個數，在每一個被選分量對應的控制器所在的控制域范圍內隨機選取一個控制器部署位置，形成一個新的蜜源位置，計算新的蜜源的收益度，如果大于原來的收益度，則用新的位置代替原來的位置，否則什么也不做。

方式3：在解的每一個分量對應的控制器所在的控制域范圍內隨機選取一個控制器部署位置，形成一個新的蜜源位置，用新的位置代替原來的位置。

算法的基本步驟如下：

步驟1 根據式 （16）計算每一個蜜源 （可行多控制器部署位置）所對應的收益度值，并將其降序排列，將前半部分指定為引領蜂，后半部分指定為跟隨蜂；

步驟2 對每只引領蜂，按照方式1在其鄰域內搜索新的蜜源；

步驟3 對于每一只跟隨蜂，以式 （17）得到的概率轉變為引領蜂，并根據方式1在其鄰域內搜索新的蜜源，而對于剩下的跟隨蜂，根據方式2的方式搜索新的蜜源；

步驟4 如果某只引領蜂在連續limit次迭代后都沒有任何變化，且其所對應的收益度在整個蜂群B 中不是全局最優的，則根據方式3產生新的蜜源；

步驟5 若當前迭代次數小于規定的最大迭代次數MAX，則轉到步驟1，否則停止迭代；

步驟6 輸出全局最優的蜜源位置，該蜜源位置即為控制器的部署位置。

4 仿真與結果

為了驗證本文所提方案的有效性，我們建立了一個模擬器來模擬交換機與交換機、交換機與控制器和控制器與控制器之間的傳播時延。該模擬器是事件驅動的，每當產生一個新的路徑請求時，相應的控制器立即響應該請求。通過文獻 ［9］提供的NOX 控制器參數來模擬控制器的處理能力。實驗中用到的拓撲為ISP 拓撲集中選取的一個節點個數為157鏈路條數為341的拓撲。我們假定拓撲中的每一個節點都為OpenFlow 交換機。本文采用iperf發包工具產生TCP數據包并輸入到網絡拓撲中，數據包的源目的地址都是隨機的，為了使得模擬更接近于真實，在產生TCP數據包流時，我們根據文獻 ［10］中提供的方式來確定數據流的大小，數據流的發送間隔以及并發流的數量。為更好的優化流表建立時間，本文引入文獻 ［11］中提出的一個控制器監測工具OFSim，它能夠記錄各控制器收到的來自各交換機發出的路徑請求次數、每一次請求的源目的地址以及控制器為此次請求計算出的路徑所包含的交換機集合等信息。在仿真實驗中，我們通過計算平均流表建立時間和控制器之間的同步時延開銷來評估本文所提控制器部署方案的性能。

我們根據λ的不同取值進行仿真實驗，觀察平均流表建立時間和控制器間同步時延情況，仿真結果如圖2所示，其中圖2 （a）表示的是λ的取值與平均流表建立時間之間的關系圖，圖2 （b）表示的是λ的取值與控制器間進行一次信息同步時的同步時延開銷之間的關系圖。

圖2 λ取不同值對應的平均流表建立時間和控制器間同步時間

從圖2中可以看出，在控制器部署優化前，平均流表建立時間和控制器間的同步時延是一個固定值，因為控制器部署位置并不隨動態流的輸入而進行相應調整，它們是固定的。優化處理后，當λ向0趨近即優先考慮控制器與控制器之間的同步時延時，網絡中的流表建立時間逐漸增大，控制器之間的部署位置更加趨近，而當λ向1趨近即優先考慮流表建立時間時，控制器間同步時延開銷逐次增加，控制器之間的部署位置更分散一些。兩者之間的比重可以根據網絡拓撲規模以及對網絡各性能指標需求不同來設定，具有較強的靈活性。

圖3表示的是當λ＝0.7時，平均流表建立時間與各控制器間進行一次信息同步時的同步時延開銷之間的關系圖。從圖3中可以看出，經過優化后所得到的平均流表建立時間和控制器間同步時延都比基于聚類的控制器部署方法所得到的對應值要小。控制器間同步時延相差較大是因為前者在優化平均流表建立時間的同時將控制器之間的同步時延開銷考慮在內。平均流表建立時間比用基于聚類的控制器部署方法所得到的值小，充分體現了基于蜂群算法思想的優越性，它能夠有效的跳出局部最優解，而得到全局的最優解，進而在優化平均流表建立時間的同時獲得較小的控制器間的同步時延開銷。

圖3 平均流表建立時間和控制器間同步時延

5 結束語

本文首先使用基于聚類的方法將控制器部署到網絡中，然后向網絡中輸入動態數據流，通過蜂群算法思想來權衡流表建立時間與控制器間同步開銷時延，從而進一步優化控制器的部署。研究發現，更注重流表建立時間時，控制器部署的位置相對分散，而優先考慮控制器間同步時延時，控制器之間的部署位置更加集中。在參數λ確定的情況下，本文多控制器方案能夠很好地權衡流表建立時間與控制器間同步時延開銷，使整個時延開銷最小。

［1］McKeown N.Software－defined networking ［J］.INFOCOM Keynote Talk，2009，418 （1）：1－12.

［2］McCauley J，Panda A，Casado M，et al.Extending SDN to large－scale networks［J］.ONS，2013，58 （2）：50－51.

［3］Yeganeh SH，Tootoonchian A，Ganjali Y.On scalability of software－defined networking ［J］.Communications Magazine，IEEE，2013，51 （2）：136－141.

［4］Yazici V，Sunay MO，Ercan AO.Controlling a software－defined network via distributed controllers［C］／／Proceedings of the NEM Summit，2012：16－20.

［5］Heller B，Sherwood R，McKeown N.The controller placement problem ［C］／／Proceedings of the First Workshop on Hot Topics in Software Defined Networks.ACM，2012：7－12.

［6］Hu Y，Wendong W，Gong X，et al.Reliability－aware controller placement for software－defined networks ［C］／／IFIP／IEEE International Symposium on Integrated Network Management.IEEE，2013：672－675.

［7］Hock D，Hartmann M，Gebert S，et al.Pareto－optimal resilient controller placement in SDN－based corenetworks［C］／／25th International Teletraffic Congress.IEEE，2013：1－9.

［8］Karaboga D，Akay B.A comparative study of artificial bee colony algorithm ［J］.Applied Mathematics and Computation，2009，214 （1）：108－132.

［9］Tootoonchian A，Gorbunov S，Ganjali Y，et al.On controller performance in software－defined networks ［C］／／USENIX Workshop on Hot Topics in Management of Internet，Cloud，and Enterprise Networks and Services，2012：8－14.

［10］Gebert S，Pries R，Schlosser D，et al.Internet access traffic measurement and analysis ［M］／／Traffic Monitoring and Analysis.Berlin：Springer Berlin Heidelberg，2012：29－42.

［11］Kong X，Wang Z，Shi X，et al.Performance evaluation of software－defined networking with real－life ISP traffic ［C］／／IEEE Symposium on Computers and Communications.IEEE，2013：541－547.