軟件定義網絡中一種快速無循環路徑遷移策略

燕昺昊，劉勤讓,2，沈劍良，湯先拓，梁棟

（1.信息工程大學信息技術研究所，河南 鄭州 450001；2.國家數字交換系統工程技術研究中心，河南 鄭州 450001）

0 引言

軟件定義網絡（SDN,software defined network）通過集中式的控制邏輯實現了對流量的細粒度管理[1]。運營商可利用SDN 根據自身需求或網絡狀態隨時調整策略部署而不需要考慮轉發設備之間存在的硬件差異。因此，傳統網絡中需要復雜操作才可實現的路由優化、故障恢復等功能均可靈活實現。

路徑遷移作為一種有效的性能優化機制及故障恢復手段，在SDN 管理中發揮了關鍵性作用[2]。網絡中流的轉發路徑受突發情況影響無法時刻保持最佳傳輸狀態。因此，為保證數據流正確傳輸，路徑遷移技術通常為數據流同時規劃多條轉發路徑。當原始轉發路徑發生擁塞或故障時，控制器將同時下發新的轉發規則至新舊路徑上的交換機，以引導數據流遷移至新路徑傳輸。

然而，由于鏈路及設備狀態差異，發往不同交換機的指令將經歷不同的傳輸時延以及生效時間[3-4]。這種異步更新機制造成了流轉發行為的不一致，導致包括更新循環、黑洞以及擁塞在內的一系列問題[5-6]，嚴重影響端到端服務質量，特別是在大規模網絡環境下。其中，更新循環是路徑遷移過程中頻繁出現且易造成網絡故障的關鍵問題之一，已經成為當前關注重點[2,7-8]。更新循環是指當遷移過程的新舊路徑存在反向重疊時，不正確的節點更新順序將導致數據包在節點之間往返，更新循環示例如圖1 所示。圖1 中，如果交換機v4在交換機v3之前更新，則將產生v3→v4→v6→v3的循環。對于交換機(v2,v3)同理。這種循環行為將極大地消耗鏈路帶寬資源，進而影響正常數據流的傳輸，嚴重時可導致鏈路癱瘓。

圖1 更新循環示例

為避免路徑遷移過程出現轉發循環，研究人員深入探究了循環產生的原因并提出了許多代表性的工作。最早提出的代表性方法稱為兩階段提交法[6,9]。在流更新期間，具有不同匹配標識的新轉發規則被發送到交換機來替代舊規則。新到的數據包因為在頭字段中具有不同于舊數據包的標簽，如虛擬局域網（VLAN,virtual local area network）可被新規則識別并轉發。舊規則最終將由于超時被刪除。然而，同時保持新舊規則在交換機中會降低存儲空間的利用率，且需要付出一個無關的包頭字段的代價。

為解決利用率的問題，Zhou 等[10]提出了倒序更新機制。當新舊路徑存在反向重疊時，一個節點的更新需要保證其在舊路徑的上游節點先被更新。然而，倒序更新本質上給網絡施加了強一致性約束，可能會導致不必要的更新時間。同樣考慮圖1所示的拓撲，交換機在新舊路徑上處于反向重疊狀態。因此，為滿足循環更新依賴，倒序更新機制使交換機按照的順序進行更新，更新時間為然而，本文通過觀察發現，如果v2先被更新，則v3和v4處于“孤立”狀態，因為此時沒有任何流通過v3和v4。顯然，在下一時刻，v3和v4可被同時更新而不會造成循環。此時，更新時間可縮減為

為加快更新過程，Wang 等[7]提出了基于分段的并行更新機制Cupid。通過將新路徑上的節點分割為不存在依賴關系的更新片段并在段內施行倒序更新，可在保證無轉發循環的同時實現多節點并行更新。在此基礎上，Li 等[11]進一步改進了Cupid 并提出了新的更新方式RU。RU 的優勢在于其實現了對段內節點的同步更新，即保證段內的第一個循環節點最后更新，且多段可以同時并行更新。然而，盡管2 種方法都使用了不同的約束機制加速了更新過程，但對于路徑循環的檢測依賴于求解有向無環圖的強連通分量，時間復雜度為 O (E+V)。V 和E分別為新舊路徑構成的有向無環圖中節點和連邊的數量。當待更新流的數量急劇增加時，時間開銷將顯著增加。

上述大部分工作只關注具體的實施方案及策略，而忽略了時間開銷對路徑遷移的重要性程度?？焖俚木W絡狀態轉移可有效減少數據包在交換機內的等待時長，進而節省交換機內部存儲空間且避免數據包長時間等待而被超時丟棄。此外，即使部分工作涉及快速更新機制[7,11]，但并沒有充分探索解空間，例如如何快速檢測遷移過程中可能出現的循環問題。因此，在已有研究基礎上，本文關注快速實現無循環路徑遷移，包括檢測和執行，以應對現有方案在實時性上的不足。具體地，本文提出了一種快速無循環路徑遷移策略。該策略可同時縮短路徑遷移中檢測階段和更新階段的完成時間，進而實現整體遷移性能優化，提升網絡收斂速度以及抗振蕩能力。本文主要貢獻如下。

1) 提出一種基于節點排序的快速循環檢測（NRLD,node ranking-based loop detection）算法。NRLD 通過對新舊路徑上的公共交換機進行編號并對比相鄰交換機序號位置差異，實現了對路徑遷移過程中是否發生循環及循環發生位置的快速檢測。

2) 提出并分析了路徑遷移過程中待更新交換機之間存在的松弛依賴關系，并基于NRLD 實現了松弛依賴關系的快速檢測。

3) 提出一種基于節點松弛依賴關系的貪婪更新（RDGU,relaxation dependency-based greedy update）機制。基于獲得的松弛依賴關系，RDGU 機制構建貪婪更新機制以保證每輪中可同時更新的節點數量最大化。

4) 通過仿真實驗驗證了提出的快速無循環路徑遷移策略。相比于已有路徑遷移中的循環避免方案，所提策略在不同網絡環境下均可顯著降低時間開銷，有效提升路徑遷移效率。

1 網絡模型

本節首先對網絡進行建模并給出路徑遷移的相關形式化定義，然后建立優化目標函數并分析約束條件。

本文提出了流更新方案基于SDN實現。在SDN中，位于控制平面的控制器C負責為每個新到達的流f計算轉發路徑p并發送相關的規則r至交換機v。對于數據平面，使用無向圖 G=(V ,E)表示由交換機集合和交換機之間的鏈路集合構成的網絡拓撲。給出如下定義來描述路徑遷移。

定義1路徑遷移。對于任意流f，其轉發路徑從具有相同起始點sf和終點df的舊路徑po遷移到新路徑pn。

定義2無循環更新。對于po和pn中所有公共節點構成的有向圖Gd，任意節點vc∈Gd的更新不得使流f經過的路徑形成有向環，即流f不能經過同一節點兩次。

因此，定義2 可表示為如下約束

假設流f從舊路徑po遷移到新路徑pn在輪之內完成。因此期望找到一組遷移調度序列可以在滿足定義2 的前提下使k最小化。因此，首先給出如下優化目標函數

2) 對于任意節點vi，進入交換機的流f只能匹配新規則rn或舊規則ro二者中的一個。

3) 對于任意節點vi，所有待更新流f所需新規則總數不得超過交換機剩余可用容量Rvi。

4) 對于任意節點vi，滿足流守恒約束，即流入的流數量與流出的流數量相等。

此外，本文中假設所有交換機vi∈V均由同一個控制器C進行管理。交換機之間的任意鏈路ej∈E容量充足，不會導致擁塞。表1 給出了網絡模型相關參數及含義。

表1 網絡模型相關參數及含義

2 算法設計

2.1 概述

本文提出的快速無循環路徑遷移策略主要由基于節點排序的快速循環檢測算法以及基于節點松弛依賴關系的貪婪更新機制構成，且均部署于控制器端。對于每個需要進行路徑遷移的流，控制器首先調用循環檢測算法判斷其新舊路徑是否可能發生循環。若不滿足發生循環的條件，則直接將新規則下發至相應的交換機來實施路徑遷移；否則，再次調用循環檢測算法來發掘節點之間存在的松弛依賴關系。基于松弛依賴關系，控制器調用貪婪更新模塊獲得路徑遷移更新序列并分步下發規則至相應的交換機?？焖贌o循環路徑遷移流程如圖2 所示。

圖2 快速無循環路徑遷移流程

2.2 基于節點排序的快速循環檢測算法

在實施路徑遷移時，需要以有效的方式來檢測遷移過程是否會發生循環，以避免數據包對鏈路帶寬的無效重復占用?，F有方案[7,11]均通過構建新舊路徑之間的有向圖并求解強連通分量來實現循環檢測，多流處理時間開銷較高。而本文所提快速循環檢測算法NRLD 僅需通過對比相鄰節點在新舊路徑上的位置關系即可實現對循環的檢測。檢測步驟如下。

步驟1NRLD 按照流在舊路徑上的傳輸順序對各節點依次編號，獲得節點編號集合seq_po，即

步驟2NRLD 根據新路徑上流傳輸順序獲得新的編號順序集合seq_pn，即

步驟3最后通過逐項比較新路徑編號序列seq_pn中相鄰節點編號值的大小即可在完成檢測的同時輸出循環位置loop_loc，即

基于節點排序的快速循環檢測算法示例如圖3所示。圖3 中，新舊路徑拓撲一共包含7 個公共節點，起始節點為v1，終止節點為v7。首先根據步驟1 獲得舊路徑節點編號seq _po為[1-7]。然后根據步驟 2 獲得新路徑相對應的節點編號seq _pn為[1,4,3,2,6,5,7]。最后，通過對比seq _pn中相鄰節點的編號大小，可知新舊路徑存在循環且可能發生循環的位置為[4,3,2]和[6,5]。

圖3 基于節點排序的快速循環檢測算法示例

NRLD 偽代碼如算法1 所示。

算法1基于節點排序的快速循環檢測算法

輸入新路徑pn，舊路徑po

輸出節點循環關系loop_loc

2.3 基于節點排序的松弛依賴關系檢測

為便于理解，在介紹具體算法之前先給出節點依賴關系相關定義并證明相關結論。

定義3節點依賴性。如果節點在節點之前更新，將導致之間產生循環，稱節點vn依賴于節點vm，表示為vn＜vm。

已有方法通過搜索有向圖中的強連通分量可找到節點之間滿足的依賴關系。需要說明的是，求解強連通分量獲得的是節點之間的強依賴關系。強依賴關系定義如下。

定義4強依賴關系。在任意更新輪ui中，節點vn必須在節點vm之前完成更新以避免循環，稱vn和vm之間滿足強依賴關系。

強依賴關系表現在有向圖中即存在從節點vn指向節點vm的與舊路徑po相反的有向邊。以圖1為例，通過求解可知為新舊路徑組成的有向圖中的一個強連通分量。因此，根據定義4，節點集須按照順序逐個進行更新?，F有工作已經證明了根據強依賴關系進行節點更新可以避免循環[7]。

事實上，盡管基于強連通分量以及強依賴關系進行節點更新保證了嚴格避免循環，但更新時間因此將同時受到有向圖規模以及依賴鏈長度的嚴重影響。同時，通過觀察發現，在一定條件下，滿足強依賴關系的節點可同時更新而不造成循環。如圖1所示，如果交換機v1先更新將消除 [v2,v3]之間存在的強依賴關系而使之可以實現同時更新。本文稱這種更新關系為松弛依賴關系，定義如下。

定義5松弛依賴關系。在新舊路徑組成的有向圖Gd中，節點vn的更新將使節點集Vr=中任意節點所具有的強依賴關系消失，稱Vr中節點之間滿足松弛依賴關系。其中，vn稱為松弛依賴觸發點，vm+1稱為松弛依賴終止點。根據定義5 可得以下結論。

結論1松弛依賴觸發點vn與其在新路徑pn和舊路徑po上的后繼節點具有相同排列順序。

證明假設松弛依賴觸發點vn與其在新路徑pn和舊路徑po上的后繼節點具有不同排列順序，即在有向圖中存在從節點vn出發的具有相反方向的2 條有向邊，如圖4 所示。此時，節點vn與其在舊路徑上的直接祖先節點形成強連通分量。根據定義3，此時vn的更新依賴于將取代vn成為新的松弛依賴觸發點?？芍c前提假設矛盾，因此結論1 成立。證畢。

圖4 結論1 參考示意

結論2 由vn觸發松弛依賴的節點集Vr必包含在vn與其在新路徑上的下一跳節點之間。

圖5 結論2 參考示意

結論3松弛依賴節點集Vr內節點可同時更新且避免循環。

證明由轉發唯一性（式(5)約束3）可知，松弛依賴觸發點vn在同一時刻只能保留一條輸出邊用于流量轉發。因此，vn在t時刻的更新將導致vn與其在舊路徑po上下一跳節點之間不再存在有向邊，如圖6 所示。再由流守恒約束（式(7)約束5）可得，在vn更新后，vn與其在新路徑上的下一跳節點之間的所有節點之間均不存在組成舊路徑po的有向邊。顯然，此時vn與之間的節點可以同時更新而不違反循環依賴。同時根據結論2 可知，vn與之間的節點即滿足松弛依賴的節點集Vr，故結論3 成立。證畢。

圖6 結論3 參考示意

根據上述結論可知，并非所有待更新節點均可同時滿足松弛依賴更新條件。因此，如何快速找到滿足松弛依賴的節點集Vr成為進一步所關注的內容。通過分析發現，基于NRLD 同樣可實現對松弛依賴關系的快速檢測。不同之處在于，NRLD 步驟3中的相鄰節點大小關系需進一步約束。

此時，滿足松弛依賴的節點集為

對于圖3，新路徑pn相鄰節點編號[1,4]和[2,6]滿足式(12)給出順序遞增關系。因此可知舊路徑po節點集即滿足松弛依賴的節點集。結合已有結論，給出并證明如下定理來說明算法有效性。

定理1基于NRLD 獲得的松弛依賴關系進行路徑遷移不產生任何循環。

由于松弛依賴關系檢測與NRLD 僅在步驟3 的判別條件上存在差異，因此不再重復給出NRLD 偽代碼。

2.4 貪婪更新算法

節點之間的松弛依賴關系本質上表征了節點實施并行更新的局部約束條件。因此，對松弛依賴集內的節點進行同步更新只能滿足部分優化需求。為了進一步減少整體更新時間，需要提出一種更高效的更新調度機制，在每輪操作中更新更多的節點以減少控制器與交換機交互的次數，從而符合式(1)給出的目標函數?？紤]2 種不同的更新方式。

方式1在每輪更新中選擇可并行更新的最大數量松弛節點集

方式2在每輪更新中選擇具有最多松弛節點的集合

然而，通過分析網絡拓撲結構發現，單獨執行二者中任意一個都無法滿足優化目標。對于方式1，可能并不存在可并行更新的松弛節點集。如圖7(a)所示，節點對 (v1,v4)和 (v2,v5)可分別導出松弛依賴集 [v2,v3]和 [v3,v4]。顯然，二者存在重疊部分，即公共更新節點v3。因此，觸發點v1和v2無法同時進行更新以導出松弛依賴集。原因在于，如果v2先完成更新，此時流的轉發路徑為v1→v2→v5。節點v3和v4上的轉發規則可能會因為在有效時間內沒有匹配數據包被超時刪除。因此，當v1更新后，流的轉發路徑v1→v4→v5就會成為斷路而導致丟包。

因此，結合上述示例，本文提出了貪婪更新機制RDGU。在每輪更新開始之前，RDGU 首先檢測是否存在無重疊松弛依賴集。若存在，則根據可并行更新的松弛依賴集中節點數與中節點數的比較結果選擇不同方式進行更新。

其中，方式1 更新流程如圖7 所示，方式2 更新流程如圖8 所示。當存在多個包含相同數量節點的Vr時，任意選擇其中一個進行更新。

圖7 方式1 的更新流程

本文給出并證明如下定理來說明RDGU的有效性。

定理2無重疊松弛依賴集中節點更新是相互獨立的。

圖8 方式2 的更新流程

定理3基于RDGU 算法進行節點更新不產生任何循環。

RDGU 偽代碼如算法2 所示。

算法2基于松弛依賴關系的貪婪更新機制

2.5 時間復雜度分析

由于循環檢測算法以及松弛依賴關系檢測算法具有相同的執行過程，因此二者具有相同的時間復雜度。其中，節點編號可以O(1)的時間復雜度完成，相鄰節點編號對比的時間復雜度為O(n)，n為新舊路徑公共節點數量。因此，檢測過程總的時間復雜度為O(n)。相比于求解強連通分量，檢測過程不再需要遍歷邊。

對于貪婪更新機制，由于一個具有n個公共節點的有向圖至少包括2 個松弛依賴集合，因此判斷松弛依賴節點集中是否存在無重疊集合的時間復雜度為O(n2)。對于節點更新過程，最壞情況下需要n輪完成更新，即每次只更新單一節點。因此其時間復雜度為O(n)。綜上可知，提出的貪婪算法的總體時間復雜度為O(n2)，且整體路徑遷移算法的時間復雜度為 O (n2+n )～ O (n2)。

3 實驗及分析

本節通過仿真實驗驗證了所提路徑遷移機制的有效性并與已有的代表性方案進行了對比。

3.1 實驗設置

實驗環境。本文所有算法均在Ubuntu 18.04 LTS 環境中使用Python 3.8 編程實現。硬件配置為AMD Ryzen 7-4800H 處理器，16 GB 內存。

網絡拓撲。使用了一個隨機拓撲和取自The Internet Topology Zoo[12]2 個不同規模的真實網絡拓撲來評估提出的算法：1) 隨機拓撲，包括17 個節點和31 條邊；2) GEANT2 拓撲，包括24 個節點和38 條邊；3) INS-INC 拓撲，包括33 個節點和40 條邊。實驗拓撲如圖9 所示。

圖9 實驗拓撲

路徑生成。從拓撲中隨機選擇節點來模擬流轉發的源節點和目的節點。然后計算并選擇節點之間的任意一條簡單路徑（不存在重復節點的路徑）作為流轉發的舊路徑。進一步，隨機排列舊路徑上除源節點和目的節點之外的其他節點來構造出存在轉發循環的新路徑。

實驗參數?？紤]到典型的真實網絡拓撲平均直徑約為log(n)[13]，結合計算開銷及實際情況（如生成樹協議計時器的默認值將最大網絡直徑限制為7），實驗中最大公共節點數量設為規則基準更新時間設為0.5 ms。同時考慮到規則更新時間受交換機性能如流表占用率、隊列長度等指標影響，因此將該時間乘以[0,1)內的隨機數來模擬真實規則更新時間?？刂破鞯浇粨Q機的信道時延為0.5 ms。每組實驗運行10 次取平均值保證無偏性。

3.2 循環檢測算法性能對比及分析

首先驗證所提NRLD 算法與已有算法在不同條件下對于循環的檢測時間差異。為保證公平性，所有算法結果被轉換為相同輸出形式。對比算法如下。

深度優先搜索（DFS,depth-first search）。從源節點開始對新舊路徑形成的有向圖進行遍歷。

Tarjan[7,11]。通過尋找強連通分量，發現有向圖中存在的環路。

不同的循環檢測算法在不同更新路徑數量下的循環檢測時間對比如圖10 所示，其中新舊路徑的公共節點數設置為6，包括源節點和目的節點。

圖10 不同更新路徑數量下的循環檢測時間對比

從圖10 中可以看出，NRLD 在不同拓撲上均取得了最佳性能。這里以GEANT2 拓撲上路徑數為500 時的結果為例來進行分析。對于DFS 和Tarjan，NRLD 可將檢測時間分別減少64.58%和55.81%。原因在于，一方面，NRLD 是通過對比相鄰節點的序號來進行循環檢測的，避免了DFS 和Tarjan 在循環檢測過程中基于堆棧的節點逐項對比操作。另一方面，DFS 對有向圖遍歷的輸出結果為有向邊的形式，需要更多時間將輸出結果處理為節點之間的依賴關系。而Tarjan 所涉及的退棧以及修改時間戳操作影響了其檢測性能。

不同的循環檢測算法在不同公共節點數量下的循環檢測時間對比如圖11 所示，其中路徑數量設為 500。根據前文所述，實驗中隨機拓撲、GEANT2拓撲和INS-INC拓撲的最大公共節點分別為7、9、10。從圖11 中可以看出，在給定的節點數量范圍內，NRLD 在3 個不同的拓撲上均獲得最小的檢測時間。特別地，當公共節點數量越多時，NRLD 優勢更加明顯。例如，在GEANT2 拓撲上，相比于DFS 和Tarjan，當節點數量為6 時，NRLD將檢測時間分別減少了34.41 ms 和19.35 ms；當節點數量為9 時，NRLD 將檢測時間分別減少了82.98 ms 和29.89 ms。產生這一現象的主要原因是當公共節點數量增多時，新舊路徑之間形成循環的數量將同步增加，這將導致DFS 和Tarjan 產生更多的入棧以及退棧操作。而每次入棧后的節點逐項對比又進一步增加了時間開銷。注意到，3 種算法的檢測時間增長均呈現非線性趨勢。這也對具有低時延需求的相關路徑優化方案（如多路徑轉發）以及故障恢復策略帶來了一定的啟發，即新舊路徑應盡可能地避免重疊。

3.3 整體方案性能對比及分析

本節進一步驗證提出的路徑遷移策略整體性能與已有遷移更新方案在多項指標上的差異。對比方案如下所示。

CCG[10]。對滿足循環依賴的節點逐個進行倒序更新。

Cupid[7]/FCFU[2]。將節點集分割為不存在依賴關系的更新片段并在段內施行倒序更新。

RU[11]。在Cupid/ FCFU 基礎上，段內的第一個循環節點最后更新，其余節點同步更新。

圖11 不同公共節點數量下的循環檢測時間對比

首先在不考慮循環檢測時間的情況下，驗證了提出的基于貪婪算法的更新機制相比于上述方案的優勢。各方案在不同公共節點數量下的平均歸一化路徑遷移更新時間對比如圖12 所示，其中更新路徑數量設為500。為更好地體現方案之間的性能差異，將實驗結果以CCG 為基準進行歸一化。當公共節點數量為4 時，所有算法的更新時間相同。這是因為此時新舊路徑只存在單一形式的循環，并不滿足松弛依賴以及并行更新執行的條件。而當公共節點數量逐漸增加時，所提更新機制的優勢開始顯現，而且隨著節點數量的增加，其性能優勢更加明顯。例如，在GEANT2 拓撲上，相比于其他方案，所提貪婪更新機制在公共節點數為6 時分別降低了17.5%和7.5%（Cupid/FCFU和RU 在此時的時間開銷是相同的）的時間開銷。而當公共節點數為9 時分別降低了54.8%、17.8%和14.7%。這是因為當公共節點數量較多時，新舊路徑之間開始出現較長的松弛依賴節點集以及并行集。這些集合使所提算法可以在更少的輪數內完成節點更新。

圖12 不同公共節點數量下的平均歸一化路徑遷移更新時間對比（更新路徑數為500）

需要說明的是，當公共節點數量不超過7 時（圖12(a)所示），Cupid/FCFU 和RU 兩類算法的更新時間是一致的。這是因為此時新舊路徑形成的循環中的更新片段并不存在可同步更新的節點。因此RU 算法退化為與Cupid/FCFU 算法一致。而當公共節點數量超過7 時，RU 算法展現出了一定的優勢。

進一步，各方案在不同更新完成時間下的路徑遷移更新完成率如圖13 所示。

圖13 不同更新完成時間下的路徑遷移更新完成率（更新路徑數為100）

對于CCG 算法，使用了DFS 來檢測其循環。而Cupid/FCFU 和RU 則按照原文獻描述均使用了Tarjan 來求解強連通分量。對于本文所提出的貪婪更新機制，則使用NRLD 來檢測節點松弛依賴關系。實驗中更新路徑數量設定為100 且其中公共節點數的比例如表2 所示。同時，規定單一交換機上規則更新是逐個進行的。從圖13 中可以看出，算法運行前期4 種方案在不同拓撲上的路徑遷移完成率相差不大。隨著運行時間的增加，本文方案展現出了明顯的優勢。這主要是因為在運行前期完成更新的均為較短路徑，即公共節點數較少的路徑。因此4 種方案的性能差異僅表現在循環檢測時間上。在運行后期，長路徑的遷移需要CCG、Cupid/FCFU和RU 運行更多的輪數。而本文方案得益于長路徑節點之間普遍存在的松弛依賴關系以及貪婪更新機制，因此可在同一輪中更新更多的節點。更少的更新輪數意味著更少的更新時間。同時，該實驗結果也表明，當網絡面臨由于鏈路故障而導致的大量路徑并發遷移需求時，本文更新機制同樣也可具有快速收斂性能。這是由于一方面，本文機制并不依賴于網絡狀態，而只與網絡規模有關；另一方面，不同流之間的遷移過程在循環檢測和更新策略的計算中并不存在依賴關系。因此遷移過程類似于流水線操作，先完成遷移計算的流可以先執行遷移。

表2 3 種拓撲中不同公共節點的路徑比例

4 結束語

本文對軟件定義網絡架構下的流路徑遷移緩慢及故障等問題進行了研究，提出了一種快速無循環路徑遷移策略。該策略首先基于節點排序實現了路徑循環的快速檢測。在此基礎上，通過發掘節點之間的松弛依賴關系并構建貪婪更新機制，保證了節點更新過程的快速實施。仿真結果表明，相比于現有路徑遷移機制，本文所提策略在保證路徑遷移無循環的前提下，實現了更快的檢測及遷移速度，且在不同拓撲及網絡條件下均具有良好的穩定性。即使面臨網絡鏈路故障導致的大量并發路徑遷移操作，同樣具有較好的收斂性。