軟件定義廣域網中基于IPv6分段路由的雙棧流量調度算法

肖漫漫，劉驥琛，李艷麗，馬 迎

(中國人民大學 信息技術中心， 北京 100872)

近年來，隨著大數據、人工智能、IPv6、在線視頻、移動互聯網等業務的快速發展，網絡流量變得復雜多樣，應用種類也越來越多，互聯網的帶寬資源越來越豐富，企業對網絡的彈性、靈活性和QoS(quality of service)的需求也越來越高。因此業界提出了軟件定義廣域網(SD-WAN, software-defined wide area network)，通過部署SD-WAN，可將網絡資源虛擬化，降低流量成本，提高帶寬利用率，加速網絡服務分發效率[1]，實現廣域網自動網絡部署和流量調度。為保障SD-WAN可靠性及利用率，SD-WAN通過部署多鏈路備份方案，同時接入專線、互聯網、LTE/衛星線路，利用overlay技術將不同線路混合捆綁，從而實現多鏈路間的流量調度和復雜服務質量[2]。而目前業界部署的SD-WAN多鏈路間的流量調度方案均為基于IPv4協議棧技術，支持IPv4/IPv6的雙棧流量調度還沒有統一的解決方案。

另一方面，分段路由(SR, segment routing)技術以及與軟件定義網絡(SDN, software defined network)結合受到了人們的青睞。分段路由支持無狀態源路由，可以減輕控制器和中間節點的開銷，對路徑的管理和控制也十分靈活[3]，因此也有一些工作研究了如何基于分段路由技術解決SDN中的流量調度問題[4-7]。其中文獻[4]將流量路徑進行分解，在考慮2段段列表的情況下，開發了離線和在線的流量調度優化算法。文獻[5]提出了一種基于分段路由路徑變量的數據結構，通過記錄經過節點和可能的下一跳節點，達到流量調度時減小消耗計算資源的目的。文獻[6]分析了基于分段路由技術的網絡流量模型，考慮在流轉發時使用單路徑而不是會加大計算資源消耗的等價多路徑模型。文獻[7]提出了一種SDN網絡中基于分段路由的多路徑流量調度算法，該算法在進行路徑權重計算后，根據路徑權重選擇最優路徑，并基于分段路由技術構造分段流表下發到邊緣交換機。但以上所述流量調度算法僅針對IPv4流量，還不能解決雙棧流量的調度問題。

1 關鍵技術

1.1 SRv6簡介

SRv6是一種基于IPv6數據平面實現的分段路由協議的網絡架構，分段路由技術[8]通過將報文轉發路徑切割為不同的分段，并在路徑的起始點往報文中插入分段信息指導報文轉發。這樣的路徑分段通過SID(段標識符, segment identifier)來標識。路徑的起始節點把這些路徑分段組合起來形成段序列(segment list)，指引報文按照段列表在網絡上將數據包進行轉發。為在IPv6報文中實現SRv6轉發，依據IPv6原有的路由擴展報文頭定義了SRv6擴展報文頭SRH(段路由擴展報文頭, segment routing header)[9]，SRH通過攜帶段列表等信息顯式地指定一條SRv6路徑。由于對雙棧流量進行了調度，與文獻[4-7]針對IPv4的流量調度研究中壓入SID信息引導流量轉發的方式不同，通過在恢復路徑中壓入SRH信息引導流量轉發，進而通過在處理節點指定行為指令對流量報文進行處理，最終實現流量調度。在IETF的SRv6 Network Programming[10]文稿中定義了很多SRv6段端節點(Endpoint)行為的指令，SRv6常見指令功能介紹如表1所示。

表1 SRv6 Endpoint常見指令功能Table 1 Function of SRv6 Endpoint

1.2 FRR技術

快速重路由(FRR, fast reroute)技術是指在鏈路故障發生時，能夠快速切換到備份路由路徑的機制[11]。基于FRR技術，當鏈路狀態失效無法正常傳輸流量數據時， SD-WAN控制器會對備份路徑進行動態計算，并將計算好的備份路徑轉發規則部署到相應的網絡設備上，以調度中斷的流量。

基于以上2種技術原理，由于網絡發生故障時和故障恢復后會產生環路現象，而SRv6通過創建無環的SRv6 段列表就可以有效地消除網絡環路[12]，因此分段路由技術結合FRR技術也越來越多地被用來解決鏈路失效時的路徑恢復問題[13-15]。其中文獻[13] 分別針對單鏈路失效和多鏈路失效提出基于分段路由的快速重路由技術，2種算法都是在檢測到鏈路失效后，計算出拼接路徑，并通過分段路由技術引導業務流量的恢復路徑。文獻[14]提出基于分段路由的主動式鏈路故障恢復策略，該策略利用分段路由的方法，通過將鏈路信息壓入數據包頭部進行數據包的轉發，從而達到鏈路恢復時減少網絡設備消耗流表項資源的目的。

2 DSTS算法

2.1 系統場景

在多園區網絡中，各園區保留獨立的園區接入廣域網的出口鏈路，而當園區網絡支持雙協議棧架構時，各園區接入廣域網出口多部署IPv4/IPv6雙鏈路，多園區雙棧網絡拓撲可以歸結為如圖1所示拓撲模型。

圖1 多園區雙棧網絡拓撲模型Fig. 1 Topology of dual stack in muti-brunches

如圖1所示，園區A任意主機Ha和園區B任意主機Hb分別通過雙棧鏈路接入廣域網，在任意園區IPv4和IPv6鏈路有效狀態下，Ha發往Hb的IPv4流量傳輸路徑為Ha->Ra0->Ra4->WAN->Rb4->Rb0->Hb、IPv6流量傳輸路徑為Ha->Ra0->Ra6->WAN->Rb6->Rb0->Hb。假設園區A IPv4鏈路出現故障，即Ra4->WAN鏈路失效，此時需在Ra4節點進行快速重路由，按照現有拓撲結構，恢復路徑應為Ra4->Ra6->WAN。但是當IPv4數據流到達節點Ra6時，由于沒有匹配的路由轉發表，最終會導致數據包的丟失。同理，當園區A IPv6鏈路出現故障時，當IPv6數據流到達節點Ra4時，仍會面對數據包丟失的問題。

針對上述應用場景提出DSTS算法，該算法在SD-WAN的基礎上，通過觸發SD-WAN控制器為雙棧數據流重新計算一條路徑，實現路由快速恢復，并分為路徑編碼算法和報文處理算法2部分實現雙棧流量調度，進而達到雙棧業務流量快速恢復的效果。

2.2 數學模型

將計算流量路徑描述為單源最短路徑模型，其數學模型描述為帶權有向圖G(N,A)，定義節點s∈N為源節點，其他節點為非源節點，路徑長度為該路徑所包含鏈路長度之和。計算單源最短路徑問題就是找出源節點s到每一個非源節點j的有向最短路徑，由于流量轉發設計僅支持單路徑，進一步將原優化模型轉換為一個整數線性規劃(ILP, inter linear programming)模型，即優化目標是恢復單源路徑長度。該模型用到的變量如表2所示。

表2 符號含義Table 2 Notation meaning

優化目標函數

Minimize∑(i,j)∈Acijxij，

(1)

s.t.

∑{j:(i,j)∈A}xij-∑{j:(j,i)∈A}xij=1,i,j∈A且i=s，

(2)

∑{j:(i,j)∈A}xij-∑{j:(j,i)∈A}xij=-1,i,j∈A且i=t，

(3)

∑{j:(i,j)∈A}xij-∑{j:(j,i)∈A}xij=0,i,j∈A且i≠s,t，

(4)

0≤xij≤1，i,j∈A，

(5)

∑{j:(i,j)∈A}xij≤1，i,j∈A且i≠s,t，

(6)

∑{j:(j,i)∈A}xij≤1，i,j∈A且i≠s,t，

(7)

目標函數是最小化單源恢復路徑長度，公式(1)表示i,j為鏈路(i,j)的上下游節點，如果鏈路(i,j)是在業務最短路徑上，則為1，否則為0。公式(2)(3)(4)表示鏈路流量守恒，若限制數據流轉發僅支持單路徑，則遵守式(2)(4)。公式(5)表示如果鏈路(i,j)在最短路徑上，則值為0，否則為1。公式(6)(7)可防止產生環路。

優化目標函數求解算法流程如下：

1)SD-WAN控制器記錄有向圖G(N,A)，記錄各鏈路權重cij，并采用Dijkstra算法計算最短路徑并保存。

2)當出現鏈路故障時，更新失效鏈路權重cst=0，控制器刪除故障節點和失效鏈路，更新網絡拓撲為G(N,A′)。

3)重復步驟1) ，根據更新后的網絡拓撲，采用最短路徑算法重新計算最優路徑并保存。

2.3 DSTS算法設計與分析

在快速重路由的應用基礎上，基于SRv6提出雙棧流量調度算法。設計思路是在園區網絡拓撲中單協議棧出口鏈路失效的場景下，對于受影響的業務流量，SD-WAN控制器分別以失效鏈路2端的上下游節點為源節點和目的節點計算一條恢復路徑，通過路徑編碼算法計算出并壓入SRH的內容、通過報文處理算法計算出雙棧流量的報文轉發方式，進而將業務流量繞過失效鏈路引導至下游節點?；赟Rv6的雙棧流量調度算法如表3所示。

表3 DSTS算法Table 3 Algorithm of DSTS

在該場景下，SD-WAN控制器監控整個網絡拓撲狀態，當鏈路失效后，控制器更新網絡拓撲，將失效鏈路刪除，進而根據最短路徑算法計算出恢復路徑。如圖2所示，當鏈路Ra4->WAN鏈路失效時，園區間IPv4流量會切換到重新計算的恢復路徑Ha->Ra0->Ra4->Ra6->Rb6->Rb4->Rb0->Hb。假設園區網絡內所有網絡節點均支持SRv6，可以把節點Ra4作為入口節點、節點Rb4作為出口節點。SD-WAN控制器監控整個網絡拓撲狀態，當鏈路失效后，控制器更新網絡拓撲，將失效鏈路刪除，在園區出口Ra4節點通過Segment List引導流量繞過失效鏈路，并通過SRv6作為underlay技術穿越廣域網，在出口節點(即故障鏈路的下游節點)彈出所有路徑分段并恢復原始報文進行轉發，保證雙棧流量通過快速重路由生成的替代路由進行轉發。采用基于編碼算法的方式進行路徑編碼，以此確定段列表壓入哪些Segment。

圖2 DSTS算法拓撲Fig. 2 Topology of DSTS algorithm

2.4 DSTS算法實現

針對圖2所示場景的恢復路徑，設計的DSTS算法包括路徑編碼算法和報文處理算法2部分，算法偽代碼描述分別如表4、表5所示，表6為報文處理算法使用的符號及其含義。

表4 路徑編碼算法Table 4 Algorithm of path coding

表5 報文處理算法Table 5 Algorithm of packet

表6 報文處理算法符號及其含義Table 6 Notation meanings of algorithm 2

表4描述了圖2場景所示的恢復路徑編碼算法。針對不同協議流量類型，在該網絡拓撲中，每條鏈路的權重值cij是不均等的，采用逆向遍歷解法。從失效鏈路下游節點開始，其中恢復路徑源節點S(即圖2中Ra4)為失效鏈路上游節點、目的節點T(即圖2中Rb4)為失效鏈路下游節點，節點X為恢復路徑的中間節點。逆向遍歷恢復路徑直到找到節點X使其路徑權重和滿足公式(8)，CTX為節點T到節點X的路徑權重和，而CXT為節點X到節點T的路徑權重和，Y為X下一跳節點，其他變量同理。

(8)

若X節點與源節點重合，則壓入目的節點Segment，若X節點與源節點不重合，則壓入該節點與目的節點Segment，之后各節點依據表5所示的報文處理算法進行報文調度，最終遵循路由協議在網絡中進行最短路徑轉發，圖6為報文處理處理算法的符號及含義。

通過上述解決方案，可以基于SRv6實現受影響的廣域網雙棧流量的快速恢復，該方案主要解決了在單協議棧廣域網鏈路失效的網絡場景下，基于繞過失效鏈路的原則，以失效鏈路的上游節點作為源節點針對受影響數據流計算一條恢復路徑，并利用路徑編碼算法得到Segment List壓入數據包首部，進而依據報文處理算法對數據流報文及其轉發方式進行處理，然后通過Segment的引導將受影響的數據流通過恢復路徑調度至失效鏈路的下游節點，以此實現在盡可能減少網絡重新配置的前提下，數據流仍沿著原有廣域網鏈路進行傳輸。

3 實驗驗證與分析

通過實驗環境下的仿真與驗證，得出該方案可以解決SD-WAN單協議棧鏈路失效時的雙棧流量調度問題，采用仿真平臺mininet搭建測試拓撲，使用iproute2進行節點配置，控制器基于Python2.7開發實現，實驗平臺選擇Ubuntu18.04(Linux內核4.15.0)，流量發生和性能測試工具采用Iperf和Wireshark軟件。

3.1 系統仿真驗證園區IPv4出口鏈路失效場景

場景仿真網絡拓撲如圖3所示。

圖3 “園區IPv4出口鏈路失效場景”仿真拓撲Fig. 3 Simulation topology of IPv4 link failure scenario

如圖3所示，“園區IPv4出口鏈路失效場景”的仿真拓撲由Ha和Hb2臺主機、6臺路由器和10條鏈接通過運行生成在mininet中，其中2臺主機、6臺路由器均支持IPv4/IPv6雙協議棧，10條鏈接中除Ra4和Rb4鏈接構成IPv4廣域網鏈路、Ra6和Rb6鏈接構成IPv6廣域網鏈路外，其他均為雙棧鏈路。

在該仿真場景中，斷開Ra4和Rb4之間鏈接，Ha執行至Hb的Ping命令，數據包在Ra4處進行SRv6的T.Encaps壓入Segment，通過仿真IPv6廣域網后，向Ra6發送，并轉發至Rb4進行END.DX4處理彈出Segment，還原為IPv4報文，向Hb進行轉發，Hb收到來自Ha的ICMP-Echo-Request，向Ha發送ICMP-Echo-Reply。同理，Reply報文按相反方向進行處理轉發，Ra4收到ICMP-Echo-Reply，即收到正確的Ping回復。通過在Ra4、Rb4進行Wireshark抓包分析驗證了恢復路徑的可行性，并驗證了恢復路徑流量引導和報文處理，實現了流量調度的目標。

為驗證恢復路徑網絡轉發的性能，在Ha和Hb之間通過iperf對網絡進行測速，如圖4測量結果顯示鏈路失效時，基于SRv6的恢復路徑的網絡吞吐率約為19Gbps，滿足中型企業園區間的網絡需求。

圖4 “園區IPv4出口鏈路失效場景”iperf吞吐率Fig. 4 Throughput of IPv4 link failure scenario

3.2 系統仿真驗證園區IPv6出口鏈路失效場景

場景仿真網絡拓撲如圖5所示。

圖5 “園區IPv6出口鏈路失效場景”仿真拓撲Fig. 5 Simulation topology of IPv6 link failure scenario

在該仿真拓撲中，仿真網絡節點設備與圖3相同，在該仿真場景中，斷開Ra6和Rb6之間鏈接，Ha執行至Hb的Ping命令，數據包在Ra6處進行SRv6的T.Encaps壓入Segment，轉發至Ra4節點后，通過6over4隧道封裝，最外層以IPv4報文頭向Rb4發送,通過仿真IPv4廣域網后，在Rb4節點對6over4報文頭解封裝，還原為SRv6報文，轉發至Rb6后進行END.DX4彈出Segment，還原為IPv4報文，向Hb進行轉發，Hb收到來自Ha的ICMP-Echo-Request請求，向Ha發送ICMP-Echo-Reply，即收到正確的Ping回復。通過在Ra6、Rb6進行Wireshark抓包分析驗證了恢復路徑的可行性，并驗證了恢復路徑流量引導和報文處理的處理流程實現了流量調度的預期目標。

為驗證恢復路徑網絡轉發的性能，在Ha和Hb之間通過iperf對網絡進行測速，如圖6測量結果顯示鏈路失效時，基于SRv6的恢復路徑的網絡吞吐率約為1.4Gbps，保障了單協議棧鏈路失效時企業園區間的雙棧網絡需求。

圖6 “園區IPv6出口鏈路失效場景”iperf吞吐率Fig. 6 Throughput of IPv6 link failure scenario

3.3 實驗分析

在Mininet系統仿真實驗中，不同路徑和處理方式的報文轉發或封裝轉發吞吐率如圖7所示、數據包往返時延如圖8所示、流量丟包率如圖9所示，仿真數據分析得出如下結論：

圖7 不同方式下iperf吞吐率對比Fig. 7 Throughput comparison of different forward method

圖8 不同方式下往返時延對比Fig. 8 RTT comparison of different forward method

圖9 不同方式下丟包率對比Fig. 9 Packet loss rate comparison of different forward method

1)鏈路失效時恢復路徑只使用SRv6處理報文的轉發速率與鏈路正常時IPv6路由轉發的吞吐率接近，而鏈路失效時恢復路徑通過SRv6over4處理轉發的吞吐率低于另2種方式，但也基本滿足中型企業園區的網絡需求。

2)鏈路失效時恢復路徑的3種報文處理方式的往返時延差異不大，經SRv6處理報文的往返時延與鏈路正常時IPv6路由轉發的往返時延非常接近，甚至略優，而通過SRv6over4處理轉發的往返時延稍大于其他兩種，但平均值在0.25 ms以下，在合理范圍內。

3)鏈路失效恢復路徑的3種報文處理方式的丟包率均為0，測試數據表明單協議棧鏈路失效時，恢復路徑的流量引導和報文處理達到了流量調度的目的，提高了雙棧SD-WAN鏈路的服務質量。

由于報文處理流程會導致數據流報文IP報頭長度增加，可能存在報文長度超過路徑最大傳輸單元(PMTU, path maximum transfer unit)的問題，進而導致報文在傳輸中被分片，大幅影響傳輸速率。因此，可以在網絡接入層對MTU進行適當限制，或通過G-SRv6(SRv6頭壓縮, Generalized-SRv6)[15]技術對SID長度進行壓縮，以減小處理后的報文長度。

4 結 語

針對現有園區SD-WAN網絡架構下，單協議棧廣域網鏈路失效時園區雙棧流量的互聯互通問題，提出了一種SD-WAN架構下基于SRv6的雙棧流量調度算法，該算法基于快速重路由機制，結合SRv6技術分為路徑編碼算法和報文處理算法兩部分實現。在鏈路失效時，通過快速重路由機制確定恢復路徑，在恢復路徑的基礎上，首先通過路徑編碼算法得出數據流添加Segment的類型，引導數據流在恢復路徑正確轉發傳輸，然后在網絡各節點根據數據流報文信息利用報文處理算法確定報文的轉發方式，最終保證雙棧流量通過快速重路由生成的替代路由進行轉發。最終，在Mininet中運行仿真實驗，并使用Iperf工具進行性能測試，實驗仿真結果表明，提出的DSTS算法實現了鏈路失效時的雙棧流量調度，增加了企業園區廣域網的冗余度和可靠性，提升了企業帶寬利用率和服務質量。