軟件定義廣域網(wǎng)中多控制器故障下的路徑可編程性恢復(fù)方法

中圖分類號：TP393 文獻標(biāo)志碼：A DOI： 10.19907/j. 0490-6756. 240337

Path programmability recoveryunder multiple controller failuresinSoftware-DefinedWAN

WANG Kun1，CHENLiang-Yin2，XU Lin，XIEJi-Feng，LIU Min1，TAN Le-Tingl （1.SchoolofComputer Science and Software Engineering，Southwest Petroleum University，Chengdu 61O50o，China; 2.College ofComputer Science，SichuanUniversity，Chengdu 6lOO65，China）

Abstract：The path programmability recovery mechanism is an effective strategy for ensuring the quality of service under controller failure in a Software-Defined Wide Area Network （SD-WAN）.To address the problemof improving the recovery capability of ofline flows and determining their recovery priority under the limited control capacity of active controllers，a priority-based path programmability recovery scheme is proposed. First，the online flows passing through the domains adjacent to thefailed controllers are rerouted，therebyimproving the available controlcapacity of these active controllrs.Then，the priority of ofline flows is defined by considering their flow size and the number of ofline switches required for recovery，and a heuristic algo rithm is designed to maintain high path programmability for high-priority flows.Experiments conducted on the ATamp;T network topology show that the proposed method increases the recovery rate of high-priority flows and enhances the path programmability of recovered flows by 80% and 287% ，respectively，compared to the benchmark algorithm.

Keywords： SDN; Controller failure;Path programmability;Ofline flows; Flow priority

1引言

軟件定義網(wǎng)絡(luò)（Software-DefinedNetworking，SDN）的流量控制靈活性源于其路徑的可編程性，使其成為當(dāng)前廣受關(guān)注的下一代網(wǎng)絡(luò)架構(gòu).當(dāng)數(shù)據(jù)流進入SDN交換機時，該流會被轉(zhuǎn)化為可編程流，并且其轉(zhuǎn)發(fā)路徑會根據(jù)網(wǎng)絡(luò)狀態(tài)動態(tài)調(diào)整．當(dāng)前，SDN技術(shù)已成功應(yīng)用于各類廣域網(wǎng)（WideAreaNetwork，WAN）中，稱為SD-WAN（Software-DefinedWAN）[2]，例如微軟SWAN3]和谷歌 B4^[4] .SD-WAN通常將WAN劃分為多個控制域，一個控制域由一個SDN控制器及其多個SDN交換機構(gòu)成.控制器根據(jù)網(wǎng)絡(luò)實時狀態(tài)，通過下發(fā)流表項至交換機，實現(xiàn)流的路徑可編程性，完成流量的靈活調(diào)度.然而，控制器故障是SD-WAN中不可避免的問題.一旦某個控制器發(fā)生故障，其所管理的交換機處于脫機狀態(tài)，導(dǎo)致流經(jīng)這些交換機的流量無法進行路徑編程，形成離線流[5].這使得網(wǎng)絡(luò)無法通過動態(tài)路由來適應(yīng)網(wǎng)絡(luò)變化，降低了整個網(wǎng)絡(luò)的可編程性，尤其是在多個控制器同時故障的情況下，這一問題尤為嚴(yán)重，因此，如何在SD-WAN中恢復(fù)網(wǎng)絡(luò)的可編程性以應(yīng)對潛在的多控制器故障情景，成為了一個極具研究價值的問題.

近年來，相關(guān)學(xué)者從控制器故障[6.7]、鏈路故障[8.9]等方面對控制器部署進行了優(yōu)化，以提高網(wǎng)絡(luò)在控制器故障時的彈性控制能力.Mtawa等從節(jié)點可達性、網(wǎng)絡(luò)連接性和邊緣分離路由的角度評估了可靠性，提出了一種在鏈路故障情況下使用邊緣不相交路徑部署控制器的方法.Naser等[7]考慮了控制數(shù)據(jù)包的最低設(shè)置成本和最小延遲因數(shù)，通過交換機的位置、控制器的處理容量以及每個控制器的設(shè)置成本來確定所需控制器的類型、位置和最小數(shù)量.Thiruvengadam等8提出了一種基于流量工程的動態(tài)控制器部署方法，采用K-Medoid算法部署控制器，并建立了人工神經(jīng)網(wǎng)絡(luò)模型進行流量分析和預(yù)測. Hu 等9通過分析真實鏈路數(shù)據(jù)得到了鏈路故障的特征，提出了魯棒的控制器布局方案來應(yīng)對鏈路故障．然而，上述靜態(tài)恢復(fù)方案忽略了網(wǎng)絡(luò)狀態(tài)的動態(tài)性，研究人員進一步從交換機遷移[10.11]、離線流重映射[12-15]等動態(tài)策略入手，以恢復(fù)路徑的可編程性.Wei等1提出了一種基于節(jié)點排除和預(yù)算的多周期交換機遷移啟發(fā)式算法，揭示了關(guān)鍵節(jié)點對收益遞減的影響，并指出關(guān)鍵節(jié)點可以提高網(wǎng)絡(luò)的穩(wěn)定性.Thangaraj等[11]提出了一種用于交換機遷移的條件感知機制，解決了控制器過載問題，通過動態(tài)交換機遷移有效修復(fù)控制器負(fù)載.RetroFlow利用SDN交換機中的混合路由功能，在控制器故障期間保持流量可編程性和低通信開銷，而不會中斷活動控制器的正常處理[12].Matchmaker根據(jù)主動控制器給定的控制能力，改變一些離線流的路徑，調(diào)整脫機交換機的控制成本，以增加流的恢復(fù)數(shù)量[13].F1-exPM利用SDN交換機支持的混合SDN和傳統(tǒng)路由近似實現(xiàn)流量控制器映射，通過在每個脫機交換機上為每個離線流細粒度地選擇路由模式來恢復(fù)可編程性[14].TEACHER引人了流量感知路徑可編程性度量，評估控制器故障對流量工程的影響，實現(xiàn)流量工程感知的控制器到交換機重映射[15].

然而，上述研究仍存在一些不足：首先，忽略了故障控制器的相鄰控制器可用控制能力的動態(tài)調(diào)整；其次，在恢復(fù)離線流時未對流的優(yōu)先級進行討論，尤其是流量較大的離線流對網(wǎng)絡(luò)恢復(fù)的影響更加顯著.針對以上問題，本文提出了一種新的解決方案，具體如下：（1）通過對流經(jīng)故障控制域的相鄰控制域中的在線流進行重新路由，降低這些流經(jīng)相鄰控制器的可能性，從而增強其恢復(fù)能力.（2）引入離線流的流量大小和流經(jīng)的脫機交換機數(shù)量作為衡量離線流優(yōu)先級的指標(biāo)，提出一種基于優(yōu)先級的離線流恢復(fù)的啟發(fā)式算法.（3）使用ATamp;T網(wǎng)絡(luò)驗證算法.實驗結(jié)果表明，相比于現(xiàn)有方案，本文提出的方法在控制器故障時的網(wǎng)絡(luò)恢復(fù)能力具有一定優(yōu)勢．

2 模型構(gòu)建

2.1 問題描述

在SD-WAN中，部署多個SDN控制器協(xié)同管理網(wǎng)絡(luò)SDN交換機，控制器之間同步信息確保網(wǎng)絡(luò)的一致性，如圖1a所示.圖1b中，當(dāng) c₃ 故障時，脫機交換機 s₃₁ 和 s₃₂ 需要與 c₃ 的相鄰控制器 c₂、c₄ 重新映射．此時， c₂ 和 c₄ 的可用控制能力決定恢復(fù)離線流的數(shù)量，影響整個網(wǎng)絡(luò)故障的恢復(fù)性能．因此，為了提高 c₂ 的可用控制能力，將在線流 f¹ 的路由從 調(diào)整為 s₂₁s₁₁s₁₂ .此時，流經(jīng)c₂ 的交換機減少 1 個， c₂ 可用控制能力增加1.從而，通過重路由流經(jīng) c₂ 的在線流以提高 c₂ 的離線流的恢復(fù)能力．對于圖 1c，c₃ 故障使得 s₃₁，s₃₂ 處于脫機狀態(tài)，流經(jīng)它們的流 f²，f³ 成為離線流.在活動控制器 c₂，c₄ 控制能力有限情況下優(yōu)先恢復(fù) f² 還是f³ 相比較 f³，f² 的流量值更小，對網(wǎng)絡(luò)負(fù)載均衡性能影響小于 f³ 的[5]，同時 f² 需要同時恢復(fù) s₃₁ 和 s₃₂ ，對網(wǎng)絡(luò)恢復(fù)要求更高.如果恢復(fù) f²，c₂ 和 c₄ 的可用控制能力減少1.而恢復(fù) f³ ，只需要 c₄ 的控制能力減少1.因此，在離線流恢復(fù)時需要考慮流量大小以及可恢復(fù)脫機交換機數(shù)量，即優(yōu)先恢復(fù) f³ 綜上，通過調(diào)整在線流的路由以提升故障控制域相鄰活動控制器的控制能力，以及在離線流恢復(fù)時考慮優(yōu)先級問題，是解決控制器故障情況下恢復(fù)網(wǎng)絡(luò)性能的有效途徑.

（a）Collaborative management of four controllers；（b）Rerouting of online flow f¹ ;（c）Preferred recovery flow ?f²vs.f³ 業(yè)

2.2 相關(guān)定義

整個SD-WAN表示為圖 G=（S，E），S 為所有交換機集合， E 為鏈路集合.活動控制器集合表示為 C^active={c_j|j∈[1，N]} ，故障控制器集合表示為C^fault={c_j|j∈[N+1，K^′]} ，脫機交換機集合表示為 S^offine={s_i|i∈[1，M]} ，在線交換機集合表示為 ，離線流集合表示為（204號 F^offine={f^l|l∈[1，L]} ，在線流集合表示為 F^online= {f^l|l∈[L+1，K^′′]}. 用 x_ij=1 表示脫機交換機 s_i （204號映射到控制器 c_j ，否則 x_ij=0 .如果離線流 f^l 流經(jīng)交換機 s_i， ，且 s_i 到 f^l 目的交換機的路徑數(shù)大于1，則y_i^l=1 ，否則 y_i^l=0 .如果離線流 f^l 流經(jīng)交換機 s_i ，且 s_i 所屬控制器為 c_j ，則 z_ij^l=1 ，否則 z_ij^l=0

（1）相鄰控制域.當(dāng)某個控制器故障時，需要將其脫機交換機映射到相鄰活動控制器，以恢復(fù)流經(jīng)這些脫機交換機的離線流.如果兩個控制域的域內(nèi)交換機之間存在一條鏈路時，那么這兩個控制域相鄰．用 η_ij 表示為

從而，與故障控制器相鄰的活動控制器集合表示為 C^near ，

同時，與故障控制器不相鄰的活動控制器集合 C^remote .如下式.

C^remote=c_j|η_ij=0，i∈[N+1，K^′]，j∈[1，N]

（2）控制器的控制能力.當(dāng)部分控制器發(fā)生故障時，主動控制器應(yīng)在不影響在線流工作的前提下，盡可能地接管脫機交換機，最大程度上恢復(fù)離線流.控制器的控制能力是指控制器能夠正常處理的操作流數(shù)量，定義為流經(jīng)該控制器所管理的控制域內(nèi)的流數(shù)量[13].控制器 c_j 的已用控制能力 A_j^used 如式（4）所示，

A_j^max 表示控制器 c_j 的控制能力上限，則控制器 c_j 的可用控制能力表示為 A_j^rest 如式（5）所示.

A_j^rest=A_j^max-A_j^used

（3）離線流優(yōu)先級.在離線流恢復(fù)過程中，大流量的恢復(fù)對整個網(wǎng)絡(luò)的負(fù)載均衡性能有顯著影響.優(yōu)先恢復(fù)大流量的離線流能夠更好地滿足用戶需求，提升服務(wù)質(zhì)量5.此外，離線流恢復(fù)時所需恢復(fù)的脫機交換機數(shù)量少，對相鄰控制器可用控制能力的需求也更少，恢復(fù)難度較低．因此，流量較大且所需脫機交換機數(shù)量少的離線流應(yīng)具有較高的優(yōu)先級，即流 f^l 的優(yōu)先級定義為：

其中 表示流 f^l 的大小，且 表示恢復(fù)流 f^l 最少需要恢復(fù)的脫機交換機數(shù)量． ω^l 反映流 f^l 在所有離線流的大小占比，其值越大表示 f^l 恢復(fù)的優(yōu)先程度越高. ψ^l 說明恢復(fù)流 f^l 的所需控制能力占比，其值越小說明優(yōu)先恢復(fù)程度越高.式（6）中 ω^l 值越大， ψ^l 值越小，pri^l 值越大，且取值范圍為 （0，1） ，符合離線流的優(yōu)先級定義．

（4）路徑可編程性.離線流在某個交換機處的路徑可編程性衡量網(wǎng)絡(luò)的可恢復(fù)能力.該值越高，表明網(wǎng)絡(luò)的彈性和適應(yīng)性越強．用 ρ_i^l 表示離線流 f^l 在交換機 s_i 處可行的路徑數(shù)，流 f^l 在 s_i 的路徑可編程性表示為（7）所示．

離線流 f^l 的路徑可編程性表示流經(jīng)所有脫機交換機的可編程性之和，即（8）.

2.3 優(yōu)化目標(biāo)

相關(guān)符號定義如表1所示.

本文旨在最大化高優(yōu)先級離線流的恢復(fù)以及已恢復(fù)離線流的路徑可編程性，從而定義一個新的綜合指標(biāo)——優(yōu)先級路徑可編程性（PriorityPathProgrammability，PPP），即離線流 f^l 的

PPP^l=pro^l×pri^l.

綜上，優(yōu)化目標(biāo)為

其中，式（11）表示脫機交換機最多映射到一個活動控制器；式（12）要求每個控制器能恢復(fù)該控制域內(nèi)的離線流的成本不超過其可用控制能力.

3算法設(shè)計

算法包括兩階段：重路由在線流（RerouteOnlineFlows，ROF）算法和基于優(yōu)先級的離線流恢復(fù)（Priority-based OfflineFlow Recovery，POFR）算法.ROF算法旨在提升故障控制器的相鄰活動控制器的可用控制能力，使得它們能恢復(fù)更多的離線流．基于此，POFR算法引入離線流的優(yōu)先級，根據(jù)優(yōu)先級恢復(fù)離線流，最大化網(wǎng)絡(luò)的路徑可編程性.

3.1 ROF算法

使用深度優(yōu)先（DeepFirstSearch，DFS）算法對流經(jīng)相鄰活動控制域的在線流重新路由，選擇新的路由使得它在相鄰活動控制域中流經(jīng)的交換機數(shù)量減少，流經(jīng)不相鄰活動控制域的交換機數(shù)量增加，以提升相鄰活動控制器的可用控制能力.在確保不影響不相鄰活動控制域的離線流恢復(fù)能力的前提下，可以將其一定比例的控制容量用于在線流的重新路由．因此，ROF算法首先計算不相鄰活動控制器所需的最小控制能力，以確保能夠恢復(fù)流經(jīng)該區(qū)域的離線流.其次，對于所有新生成的可行路由，需要評估其是否滿足不相鄰控制器的最小可用控制能力要求.最后，算法選擇最合適的路由作為在線流的新轉(zhuǎn)發(fā)路徑，從而提高相鄰活動控制器的可用控制能力.

算法1ROF

輸入：活動控制器集合 C^acuve 、故障控制器集合 C^fault 、在線流集合 F^online

輸出：所有活動控制器的 A_j^rest

1）計算故障控制器的相鄰控制器集合 C^near 不相鄰控制器集合Cremote.

2）如果 C^remote 為空，選擇 C^near 中 A_j^rest 最小的加人 C^remote 中.

3）計算控制器 c_j∈C^remote 的可用控制能力 A_j^rest 與流經(jīng)該控制器的離線流所需要最小的控制能力 A_j^offine

如果滿足 A_j^restj^offline ，則從 C^remote 中刪除 c_j 4）遍歷 f^l∈F^online ，使用DFS算法計算 f^l 的可行路徑集合 P ，且可行路徑 Ψ_Pk∈P 的交換機均屬于 S^online ：5）遍歷 ρ_k∈P ，如果同時滿足3個條件：經(jīng)過 C^remote 的交換機數(shù)量增加；經(jīng)過 C^near 的交換機數(shù)量減少；所有經(jīng)過的控制器的 A_j^rest 不低于 A_j^offline .從中找到一條傳播時延最短的路徑作為 ρ_best 6）若 ρ_best 存在，則更新相應(yīng) C^active 的負(fù)載 ，f^l 的轉(zhuǎn)發(fā)路徑．7）若 f^l∈F^online 遍歷沒有結(jié)束，繼續(xù)執(zhí)行步驟4）.8）算法結(jié)束，輸出所有活動控制器的 A_j^rest

3.2 POFR算法

在恢復(fù)脫機交換機時，優(yōu)先恢復(fù)流經(jīng)脫機交換機離線流比例較高的脫機交換機.定義脫機交換機的關(guān)鍵度為流經(jīng)該交換機的離線流數(shù)量與總離線流數(shù)量的比值，其值越大說明交換機的優(yōu)先恢復(fù)的可能性越大.POFR算法先恢復(fù)關(guān)鍵度高的脫機交換機，然后計算流經(jīng)該交換機的離線流，從中選擇一定比例的、路徑可編程性高且優(yōu)先級高的離線流進行恢復(fù)，這一過程重復(fù)執(zhí)行，直至所有交換機恢復(fù)，最后，根據(jù)控制器的可用控制情況，依次恢復(fù)剩余的PPP值較高的離線流.

算法2 POFR

輸入：活動控制器集合 C^active 、離線流集合 F^offine 、脫機交換機集合 S^offline 、在線交換機集合 S^online （20

輸出：映射關(guān)系 恢復(fù)離線流

1）執(zhí)行ROF算法更新活動控制器的 A_j^rest 業(yè)

2）依據(jù)優(yōu)先級對流 f^l∈F^offine 降序排序.

3）依據(jù)關(guān)鍵度對脫機交換機 s_i∈S^offine 降序排序.

4）初始化標(biāo)志FLAG L= TRUE，當(dāng)前恢復(fù)比例 #

5）循環(huán)執(zhí)行步驟6）～12），直到FLAG為FALSE.

6）遍歷 s_i∈S^offine ，F(xiàn)LAG °eq FALSE，當(dāng)前可恢復(fù)流 ：

7）遍歷 c_j∈C^active ，使用非遞歸DFS算法判斷 s_i 到 c_j 是否存在一條路徑，且路徑上的交換機均屬于 S^online ：

8）若存在，計算 A_j^rest 和流經(jīng) s_i 的離線流的數(shù)量差值 Δ_ij

9）將 Δ_ij 值最大的活動控制器 c_j 作為 s_i 新的控制器，即（204號 x_ij=1. 將 s_i 加入 S^online ，從 S^offine 移除.

10）遍歷 f^l∈F^offine ，且 y_i^l=1 ，如果可行路徑所在的所有交換機 s_i∈S^online ，則該流可恢復(fù)，加入到 計算其轉(zhuǎn)發(fā)路徑：滿足 ρro^l 最大且路徑上控制器均滿足 A_j^used?A_j^max 二：

11）否則，使用非遞歸DFS算法判斷流 f^l 的起點 u 到

終點 v 是否存在一條路徑，且路徑上的交換機均屬于 S^online ，若不存在，則繼續(xù)10）.

12）若存在，從當(dāng)前路徑集合中找到 p_k∈P ，尋找這樣一條路徑 ρ_best ：使得經(jīng)過的所有控制器的 A_j^used? Aax且pro最大.若pbest存在，則f‘加人到Ffine.繼續(xù)10）.

13）遍歷 ，選擇PPP值最大的不超過 比例的 恢復(fù)，并從 F^offine 刪除，更新 的轉(zhuǎn)發(fā)路徑，F(xiàn)LAG TRUE.繼續(xù)6）.

14）若 F^offine 為空，跳轉(zhuǎn)到17）.

15）遍歷 f^l∈F^offine .計算 f^l 是否存在路徑：滿足 ρro^l 最大且路徑上控制器均滿足 A_j^used?A_j^max 若存在，則從Foffine移除 f^l ，更新 z_ij^l，A_j^rest，f^l 的轉(zhuǎn)發(fā)路徑.

16）若 f^l∈F^offine 遍歷沒有結(jié)束，繼續(xù)15）.

17）算法結(jié)束，輸出 X，r

4實驗分析

4.1 實驗設(shè)置

本文使用來自Topology Z₀₀^[16] 的ATamp;T網(wǎng)絡(luò)拓?fù)鋪碓u估算法和模型的性能.該網(wǎng)絡(luò)拓?fù)溆?5個節(jié)點和112條鏈路組成.選擇ATamp;T網(wǎng)絡(luò)拓?fù)涞脑蛟谟?，已有關(guān)于控制器故障恢復(fù)的研究[12-15.17.18]將其作為代表性 SD-WAN拓?fù)溥M行分析.ATamp;T網(wǎng)絡(luò)中每個節(jié)點代表一個城市，都有一個唯一的ID及其緯度和經(jīng)度，節(jié)點對之間總是有一個流．因此，在實驗仿真中，每個節(jié)點都是一個

SDN交換機，任何兩個節(jié)點都基于最短傳播時延轉(zhuǎn)發(fā)流量.使用半正弦公式計算兩點距離，并使用距離除以傳播速度表示兩個節(jié)點之間的傳播延遲[18].ATamp;T網(wǎng)絡(luò)包括6個控制器，每個控制器的控制能力上限為500，結(jié)合文獻[17]生成100個流量矩陣用于驗證，實驗所展示的為其平均結(jié)果．表2顯示ATamp;T網(wǎng)絡(luò)中交換機與控制器之間的映射關(guān)系，以及流經(jīng)該交換機的流數(shù)量[13].本文算法使用Java實現(xiàn)，并在如下環(huán)境中進行測試：Intel（R）Core（TM）i7-10510U處理器、16GBRAM和Windows11操作系統(tǒng).

選擇LA-GWBM、Matchmaker、PG作為比較算法.LA-GWBM[18針對多個控制器故障的情況，提出了一種貪心策略來實現(xiàn)交換機的分配.Matchmaker[13通過改變流的路徑，自適應(yīng)調(diào)整脫機交換機的控制代價，以實現(xiàn)脫機交換機重新映射.PG[19]通過細粒度的流級重新映射，在多個控制器故障情況下以較低的通信開銷提高恢復(fù)流的路徑可編程性.本文從相鄰活動控制器的可用控制能力增量、恢復(fù)的離線流比例、恢復(fù)高優(yōu)先級離線流比例、恢復(fù)脫機交換機數(shù)量、已恢復(fù)流的路徑可編程性這4個指標(biāo)比較，其中優(yōu)先級前 50% 的離線流定義為高優(yōu)先級流.考慮到多個控制器故障相對單個控制器故障的路徑可編程性性能更嚴(yán)重，因此本文分別討論2個和3個控制器故障情景.

4.2 結(jié)果分析

4.2.12個控制器故障圖2展示了2個控制器故障的15種故障情景.圖2a中，通過執(zhí)行ROF方法，每種情景下相鄰活動控制器的可用控制能力平均增加91.在情景ID[6，20]中，控制器 C₂ 和 C₂₂ 的可用控制資源增加198.圖2b比較4種算法在離線流恢復(fù)比例.POFR和PG能恢復(fù)所有離線流，而LA-GWBM的恢復(fù)比例最低，Matchmaker次之.這是由于LA-GWBM要求交換機需要控制器恢復(fù)流經(jīng)其所有離線流才能被恢復(fù)，而這些控制器的可用控制能力卻不滿足，影響了大部分流的恢復(fù).相比之下，POFR通過重路由在線流機制，使得故障控制器的相鄰控制器的可用控制能力平均提升了 18.4% ，增強了這些活動控制器的恢復(fù)能力，特別是在故障情景ID[13，22]中，活動控制器 C₂ 的可用控制能力比例增加了 37.9% .圖2c顯示，POFR和PG恢復(fù)了全部高優(yōu)先級流量，這是因為它們已恢復(fù)所有離線流.LA-GWBM由于恢復(fù)離線流的比例較低，導(dǎo)致高優(yōu)先級流量的恢復(fù)效果大部分低于Matchmaker.對于故障情景ID[13，22」，由于較多的高優(yōu)先級離線流就近活動控制器 C₂ 恢復(fù)，從而LA-GWBM的貪婪決策在此情景中表現(xiàn)略優(yōu)于Matchmaker.圖2d顯示，LA-GWBM未能恢復(fù)所有脫機交換機，而其他3種方案均成功恢復(fù)了所有脫機交換機.這是因為在LA-GWBM的恢復(fù)策略中，活動控制器必須能夠恢復(fù)流經(jīng)該交換機的所有離線流，這導(dǎo)致部分脫機交換機無法直接恢復(fù)．圖2e中的結(jié)果以LA-GWBM為基準(zhǔn).Matchmaker的路徑可編程性較差，因為Matchmaker關(guān)注最大化離線流的恢復(fù)數(shù)量，而未考慮路徑的可編程性.POFR和PG在路徑可編程性方面表現(xiàn)最佳，且兩者表現(xiàn)接近，是因為PG額外考慮了在線流的路徑可編程性.對于故障情景ID[13，2O]，POFR相比LA-GWBM提升了 215% .由于LA-GWBM恢復(fù) s₁₃ 所需控制能力為213，而相鄰控制器的最大可用能力僅為154，導(dǎo)致其無法恢復(fù)這些離線流，從而它們的路徑可編程性較低.

（a）相鄰活動控制器的可用控制能力增量；（b）離線流的恢復(fù)比例；（c）高優(yōu)先級離線流的恢復(fù)比例；（d）脫機交換機的恢復(fù)數(shù)量；（e）已恢復(fù)離線流的路徑可編程性比例.

（a）Incrementalavalableapaityfjacntactivetrollrs；）eretaoffinfoecoeed;erceagori offlineflowsrecovered;d）Numberofofineswitchesrecovered；（e）Percentageofpathprogrammablityofrecoveredoflineflows.

4.2.23個控制器故障圖3展示了3個控制器故障的20種故障情景.圖3a中，由于故障控制器增加，使得可重路由在線流減少，但活動控制器的可用控制能力平均增加了35.圖3b顯示POFR和PG在離線流恢復(fù)比例上均優(yōu)于LA-GWBM和Matchmaker.其中PG在11種情景中恢復(fù)了 100% 的流，而POFR在18種情景中恢復(fù)了 100% 的流，最低恢復(fù)比例為 96% .是因為ROF算法增加了相鄰活動控制器的可用控制能力，從而也驗證了控制器故障情況更為嚴(yán)重情況下POFR的優(yōu)勢.圖3c中，由于POFR優(yōu)先考慮高優(yōu)先級流恢復(fù)，所以是4種方案中唯一恢復(fù)了 100% 的高優(yōu)先級流．而Matchmaker和LA-GWBM由于恢復(fù)離線流的比例較低，影響了高優(yōu)先級流的恢復(fù)效果，對于故障情景ID[2，5，20]，PG由于未考慮高優(yōu)先級流量的恢復(fù)機制，導(dǎo)致僅恢復(fù)了 77% 的高優(yōu)先級流量.LA-GWBM在故障情景ID[5，6，20]中恢復(fù)高優(yōu)先級比例僅為 20% .圖3d中LA-GWBM的平均恢復(fù)脫機交換機比例為 46.2% ，其他3種方案的恢復(fù)比例為 100% .特別是ID[5，6，20]情景，10個脫機交換機只恢復(fù)了2個，這也說明LA-GWBM交換機級映射解決方案的局限性.圖3e中的結(jié)果以

LA-GWBM為基準(zhǔn).在大多數(shù)情景中，POFR與PG的路徑可編程性相近.然而，當(dāng)PG未能完全恢復(fù)所有離線流時，POFR在恢復(fù)流的路徑可編程性方面表現(xiàn)更優(yōu).特別是在故障情景ID[5，6，20]中，POFR相比PG提高了 20.9% ，相比LA-GWBM提高了 287% .原因在于PG恢復(fù)離線流的比例僅為 60% ，而LA-GWBM的恢復(fù)比例僅為18% ：

（a）相鄰活動控制器的可用控制能力增量；（b）離線流的恢復(fù)比例；（c）高優(yōu)先級離線流的恢復(fù)比例；（d）脫機交換機的恢復(fù)數(shù)量；（e）已恢復(fù)離線流的路徑可編程性比例.

（a）Increentallablepacityfacetactieotrolers（b）ercetaofflinfoecoeed;erceagfgity ofineflowsrecovered;（d）Numberofofliswihesrecovered;（e）erentageofpathprogammabiltyfrecoveredoflineflows.

5結(jié)論

參考文獻：

本文探討了如何提高故障控制器相鄰活動控制器的可用控制能力，以及如何優(yōu)先選擇離線流進行恢復(fù)，以確保在多控制器故障情況下網(wǎng)絡(luò)的可恢復(fù)性.活動控制器的可用控制能力決定了允許恢復(fù)的離線流數(shù)量，而高優(yōu)先級離線流的恢復(fù)對整個網(wǎng)絡(luò)的負(fù)載性能影響顯著．為此，本文提出了一種啟發(fā)式算法，旨在最大化離線流的路徑可編程性.實驗結(jié)果表明，所提出的解決方案能夠在控制器故障時有效滿足離線流的可編程性需求.未來的工作將研究如何在主備控制架構(gòu)中實現(xiàn)離線流到備份控制器映射.

[1] ZhangSJ，LanJL，HuYX，etal.Surveyonscalability ofcontrol plane in software-defined networking[J].JSoftw，2018，29：160.[張少軍，蘭巨龍， 胡宇翔，等.軟件定義網(wǎng)絡(luò)控制平面可擴展性研究 進展［J].軟件學(xué)報，2018，29：160.]

[2] ZhangY.Research on key technologiesof softwaredefined wide areanetwork performance optimization[D].Beijing：Beijing University of Posts and Telecommunications，2022.[張藝.軟件定義廣域網(wǎng) 服務(wù)效能優(yōu)化關(guān)鍵技術(shù)研究[D].北京：北京郵電 大學(xué)，2022.]

[3] HongCY，Kandula S，MahajanR，et al.Achieving highutilizationwith software-driven WAN[J]. SIGCOMMComput CommunRev，2013，43：15

[4] Jain S，Kumar A，Mandal S，et al.B4：Experience with a globally deployed software defined WAN[J]. Association for ComputingMachinery，2Ol3，43，3.

[5] Guo Z H，Dou S S，QiL，et al.A survey of maintaining the path programmability in software-defined widearea networks[J].JElectron Inf Tech，2023， 45：1899.[郭澤華，竇松石，齊力，等．面向軟件定 義廣域網(wǎng)的路徑可編程性保障研究綜述[J].電子與 信息學(xué)報，2023，45：1899.]

[6] Al Mtawa Y，Haque A，Lutfiyya H. Migrating from legacy to software defined networks：A network reliability perspective［J].IEEE Trans Reliab，2021， 70：1525.

[7] Naseri A，Ahmadi M，PourKarimi L. Placement of SDN controllers based on network setup cost and latency of control packets [J]. Comput Commun， 2023，208：15.

[8] Thiruvengadam H，Gopalakrishnan R，Rajendiran M.Dynamic controllerdeployment in SDN networks using ML approach [M]//Sustainable Communication Networks and Application. Cham：Springer International Publishing，2O19：311.

[9] Hu T，Ren Q，YiP，et al. An effcient approach to robust controllerplacement forlink failuresin Software-Defined Networks[J].Future Gener Comput Syst，2021，124：187.

[10]Wei S H，Chin T S，KwangL C.Cost-location aware heuristic algorithm for hybrid SDN deployment[J].Ann Math Artif Intell，2021，89：875.

[11]Ethilu T，Sathappan A，Rodrigues P.An efficient switch migration scheme for load balancing in software defined networking[J].Int J Electr Comput Eng Syst，2023，14：443.

[12」Guo Z，F(xiàn)engW，LiuS，et al.RetroFlow：Maintainingcontrol resiliency and flow programmabilityfor software-defined WANs [C]//2019IEEE/ACM 27th International Symposium on Quality of Service （IWQoS）.Phoenix：IEEE，2019：1.

[13]Dou S，Miao G，Guo Z，et al.Matchmaker：MaintainingnetworkprogrammabilityforSoftwareDefined WANs under multiple controller failures[J]. ComputNetw，2021，192：108045.

[14]Guo Z，Dou S，Wu W，et al. Toward flexible and predictable path programmability recovery under multiple controller failures in software-defined WANs[J]. IEEE/ACMTransNetw，2023，31：1965.

[15]Guo Z，QiL，Dou S，et al.Maintaining control resiliency for traffic engineering in SD-WANs[J]. IEEE/ ACM Trans Netw，2024，32：3485.

[16]Knight S，Nguyen HX，F(xiàn)alkner N，et al. The Internet topology zoo[J]. IEEE J Sel Areas Commun， 2011，29：1765.

[17]Ye M， Zhang J，Guo Z，et al.Federated trafic engineering with supervised learning in multi-region networks[C]//2021 IEEE 29th International Conference on Network Protocols（ICNP）.Dallas：IEEE， 2021： 1.

[18] He F，Oki E.Main and secondary controller assignment with optimal priority policy against multiple failures[J]. IEEE Trans Netw Serv Manag，2O21，18： 4391.

[19]Guo Z，Dou S，JiangW，et al. Toward improved path programmability recovery for software-defined WANs under multiple controller failures[J]. IEEE/ ACM TransNetw，2024，32：143.

（責(zé)任編輯：伍少梅）