基于段路由的IPv6網絡優化算法

劉 威，黃 萍，孫鳳杰

(1.深圳供電局有限公司 信息中心，廣東 深圳 518000；2.華北電力大學 電氣與電子工程學院，北京 102206)

0 引 言

流量工程(TE)被網絡運營商廣泛應用于提高網絡性能和效率[1,2]。軟件定義網絡(SDN)為流量工程提供了一種更靈活的方法[3]。網絡運營商可以通過集中式控制器在控制平面上實現路由算法或策略，靈活地將任意比例的流量分流到SDN交換機的任何出站鏈路，突破了最短路徑路由限制。在SDN中實現TE通常需要大量的流表項，因為業務路徑上的每個交換機都必須有一個對應的流條目。當需求量很大時，商品交換機的流量輸入能力往往不足。段路由(SR)[4,5]是一種新興的源路由范式。SR不需要路徑信令，每流狀態只在入口SR節點維護，所以它具有可伸縮性和靈活性。然而，從傳統的IP網絡遷移到完整的SR網絡對于Internet服務提供商(ISP)網絡來說存在許多挑戰。首先，由于現有網絡中的傳統路由器并支持SR，所以可能會被新設備取代。其次，雖然軟件升級可以使一些高級路由器運行SR，但大規模升級所有網絡設備仍可能導致網絡服務不穩定甚至網絡中斷。所以在IP網絡中部分部署SR節點的混合SR網絡是一種可能的過渡網絡場景。

混合IP/SR網絡設計的一個關鍵問題是如何通過較少的SR節點來獲得與完整SR網絡幾乎相同的TE性能，因為SR節點的部署越少，網絡升級就越容易。目前，基于混合IP/SR網絡的TE研究較少。并且目前的研究不能充分發揮IP/SRv6網絡的TE能力。

在本文中，針對部分部署的SRv6網絡提出了一種TE算法(ST)，以最小化網絡的最大鏈路利用率為目標。本文的主要創新如下：①針對分散部署IP/SRv6網絡中的SR-TE問題，利用SRv6與普通IPv6節點之間的無縫互操作性，放寬SRD的限制，并假設支持SRv6的節點可能不構成原始網絡拓撲的任何連通子圖。它可以提供更大的靈活性。②ST算法不僅考慮了SR節點的部署，而且考慮了鏈路權重的設置。該方法利用IGP的TE能力來彌補部分部署SR網絡中TE能力的不足。③考慮到流量變化，將ST分為兩個階段：離線網絡設計和在線路由優化。在離線階段，確定了網絡運行時不易改變的鏈路權值設置和SR節點部署，并提出了以一天內歷史流量矩陣(TMs)上的重心作為代表流量矩陣(TM)的初步設想。在在線階段，用線性規劃來確定每一個新TM的段列表。

1 問題描述

1.1 網絡場景

在提出的IP/SRv6混合網絡場景中，所有節點都運行傳統的網絡協議棧并支持IPv6和OSPFv3協議，而其中只有一部分節點支持SRv6。假設支持SR的節點分散部署，這意味著它們可能不構成原始網絡拓撲的任何連通子圖。每個IPv6節點將為任何前綴維護一個FIB(forward information base)條目，無論前綴是否代表一個段[5]。因此，可以通過不支持SR的節點將數據包轉發給擁有SID的節點，而且OSPFv3支持處理和洪泛未知的LSA類型[6]，因此SRv6控制消息可以通過非SRv6節點進行交換[7,8]。

圖1顯示了混合IP/SRv6網絡的示例。在這種拓撲中，節點B、節點D和節點F支持SRv6，其它節點是傳統的IPv6節點。請注意，SR節點(B、D和F)不是直接連接的。節點ID用于表示它們的SID和相應的IPv6地址。從節點A發送并定向到節點G的分組遵循最短路徑直到到達節點B，即入口SR節點。從這里開始，包由SRv6路由(用虛線表示)。節點B有兩個選擇：①它可以在IPv6報頭和有效載荷之間插入一個帶有Clear標志的SRH，并且由于Clear標志，SRH將在節點F處被刪除；②它可以使用SRH將接收到的包封裝在外部IPv6報頭中，并且包將在節點F處解封裝[9]。在圖1中展示了封裝方式。節點B將數據包封裝在外部IPv6報頭中，SRH指定段列表 〈D,F〉。數據包通過節點C，沿著從節點B到節點D的最短路徑到達節點D。節點C不會檢查或更改SRH，因為它不是外部IPv6報頭的DA字段中標識的目標節點。它根據IPv6的DA字段將數據包轉發給D。節點D減小SRH的Segment Left字段，并將外部IPv6的DA字段設置為F。然后數據包通過節點E到達節點F，即出口SR節點。根據OSPF協議，數據包在節點F處解封裝，并沿最短路徑轉發到節點G。

圖1 一個混合IP/SRv6網絡

根據上述描述，部分部署的SRv6網絡中的路由有3個階段：①從源節點s(l)到入口SR節點；②從SR節點到另一個SR節點；③從出口SR節點(如果不涉及SR路由，則為s(l))到目的節點t(l)。一條完整的流量路徑可以看作是由3種類型的子路徑組成：

(1)從s(l)到t(l)的最短路徑在從s(l)到SR節點的最短路徑上，對應于路由的第一階段。流量從這種子路徑開始，通過OSPF協議路由，直到到達SR節點；

(2)任意兩個SR節點之間的最短路徑，對應到路由的第二階段。包由SR在這類子路徑上路由，每個子路徑代表一個節點段；

(3)從SR節點(或s(l))到t(l)的最短路徑，對應于路由的第三階段。數據包通過OSPF協議路由，通過這種最短路徑到達目的節點。

1.2 問題表述

這里的TE問題可以表述如式(1)～式(12)所示

minUmax

(1)

式(1)是問題的目標函數。在這里打算盡量減少網絡的最大鏈路利用率。它是SR-TE[1,10]中的一個經典目標，它均衡地提高了鏈路的利用效率

(2)

在式(2)中，c(e)以及后面的w(e)代表鏈路e的頭/尾的容量和權重，d(l)是需求l的目標節點。式(2)限制了鏈路所承載的業務量不能超過其容量

(3)

(4)

式(3)表示變量f和g之間的關系。式(4)是流量守恒約束，s(l),t(l)表示為需求l的流量

x(s(l))·x(j)}=0, ?l∈L,j∈V{t(l)}

(5)

?l∈L,i∈V{s(l)},j∈V{t(l)}

(6)

(7)

式(7)約束為i不是s(l)時,gli,t(l)(w)必須等于0，除非i是SR節點

(8)

在這里1的約束為任意節點到它自身，任何節點到s(l)，以及t(l)到任何節點，g都必須等于0

(9)

式(9)為SR部署比約束

i,j∈V,e∈E

(10)

(11)

1≤w(e)≤216-1∧w(e)∈?e∈E

(12)

式(10)～式(12)是一些瑣碎的數值約束。因為w也是這個公式中的一個變量，所以它不能用優化求解器來求解。

1.3 問題復雜性

當OSPF權重設置固定且SR_Ratio=1時，問題被簡化為MCF問題，并且可以在多項式時間內解決[11]。然而，在這里只有某些節點具有SR功能。因此，需要確定OSPF鏈路權重來優化Umax，這增加了問題的復雜性。OSPF權重設置問題被驗證是NP難度問題[12]。OSPF權重設置問題可以在多項式時間內歸結為本文的問題，因為在SR_Ratio設置為0的情況下解決這個問題可以得到相應OSPF權重設置問題的解決方案。所以整個問題的復雜性是NP難的。

2 算 法

在本節中，將介紹ST算法。采用DRL算法對鏈路權值設置和SR配置進行離線優化，采用線性規劃方法在線優化流量路徑和分流比。

2.1 ST算法框架

首先介紹了ST的框架。這里所考慮的問題不僅是一個TE問題，也是一個網絡設計問題。一旦在網絡設計階段確定了SR節點的部署，則長時間內不能改變。OSPF重配置可能會引起諸如micro-loop等問題[13]，因此OSPF鏈路權重在網絡運行階段不能快速變化，以保證轉發的一致性。更新SR規則不會產生這樣的問題，因此SR控制的流量路徑可以更容易地改變。

綜上可知，ST有兩個階段：

(1)離線網絡設計：離線網絡設計階段的目的是獲得合適的鏈路權重和長時間的SR節點部署。考慮到網絡流量的周期性，利用歷史流量矩陣計算了一個具有代表性的TM。然后使用離線DRL算法的深度確定策略梯度(DDPG)來優化鏈路權重和SR部署。一旦獲得最佳鏈路權重設置和SR節點部署，它們在網絡運行時不會發生變化；

(2)在線路由優化：在這個階段，確定了鏈路權重和SR節點部署，并且只針對每個新的TM在線優化路由路徑。使用線性規劃來決定適當的SR節點分割比率，以最小化每個TM的最大鏈路利用率。

2.2 離線階段設計

由于前文描述的優化問題不能在多項式時間內求解，因此采用強化學習。強化學習是機器學習的一個分支。RL不再依賴于人工設計的啟發式算法或從預先收集的訓練數據(如監督學習)中學習，而是直接與網絡交互并從中學習。在RL中，有一個代理通過狀態(觀察)，行為和獎勵與環境反復交互[40]。在每個步驟t中，代理從環境中觀察一個狀態st并選擇一個操作at。根據at，狀態轉移為st+1，環境向代理發送獎勵rt。代理的行為基于一個確定性策略π，它從一個狀態映射到一個特定的操作。RL的目標是從起始狀態J=其中γ∈(0,1]稱為折扣因子)開始，學習使期望累積折扣報酬最大化的最優策略。直觀地說，網絡就是環境，提出的算法就是代理。將問題轉化為RL公式，如下所示：

動作：這里的動作是鏈接權重設置。更具體地說，作用是一個1×|E|向量，at=[w(e)|e∈E]。

回報：回報rt按式(13)、式(14)計算。使用Umax(st)來表示當網絡流量分布為st時最小的最大鏈路利用率。首先利用式(13)計算Umax(s1)與Umax(st)的比率

(13)

比率α反映了最大鏈路利用率Umax的改善程度。然后根據式(14)計算回報

(14)

回報告訴代理它的行為有多好，所以基本思想是當α<1時給予負回報，當α>1時給予正回報。使用指數函數的目的是在代理表現良好時給予很大的回報，反之亦然。

算法1：ST 離線階段

輸出：w,SRN,Umax

用隨機θμ,θQ初始化Actor網絡μ(s|θμ)和Critic網絡Q(s,a|θQ)

用θμ′←θμ,θQ′←θQ初始化目標網絡μ′(s|θμ′)，Q′(s,a|θQ′)

初始化重播緩沖區R

form=1,2,…Mdo

fort=1,2,…Tdo

rt=get_reward(Umax(s1),Umax(st+1))

R.store(st,at,rt,st+1)

minibatchR′=R.sample(N′)

fortransition(si,ai,ri,si+1)∈R′do

yi=ri+γQ′(si+1,μ′(si+1|θμ′)|θQ′)

endfor

通過最小化損失更新Critic網絡

按采樣策略梯度更新Actor網絡

θQ′←τθQ+(1-τ)θQ′

θμ′←τθμ+(1-τ)θμ′

ifUmax(st+1)=MCFOPTthen

break

endif

endfor

endfor

w,SRN,Umax=aT,SRNT+1,Umax(sT+1)

returnw,SRN,Umax

下面將具體說明：①如何獲得所有TMs的代表性TM(get_representative_TM函數)；②如何獲得狀態st+1，即當鏈路權重設置為at時，網絡流量分布Umax(st+1)和SRNt+1(get_state函數)。

(1)代表性TM：希望找到最佳和最合適的OSPF鏈路權重設置和SR節點部署，以在相對較長的時間內最大限度地降低SR-TE的鏈路利用率。因此，不使用任意TM，而是使用過去一段時間內的歷史TMs來計算具有代表性的TM。

(15)

(2)獲取表示網絡的狀態：在步驟t中，鏈路權重設置固定為at，需要得到狀態為st+1的網絡流量分布。與以往文獻[15]和文獻[16]的網絡場景簡單不同，本文主要研究分散部署的IP/SRv6網絡。為了得到st+1的狀態，需要確定SR節點集SRNt+1和轉發路徑。此外，還需要得到最小的最大鏈路利用率Umax(st+1)用來計算rt。這里解決這個問題共有3步：選擇SR節點；計算流量路徑；求解LP問題。

(1)選擇SR節點：為了獲得SR節點的最優部署位置，充分利用部分部署SR網絡所提供的TE能力，需要考慮3個拓撲參數：

1)度：節點的度數(DEG)是指與該節點相關的鏈接數，可以通過式(16)計算得到

DEG(v)=|{e|es(e)=v∨et(e)=v}|

(16)

在這里，es(e)和et(e)分別代表鏈路e的頭和尾。

2)中間性：節點的中間性是指通過該節點的最短路徑數。σst(v)表示從s到t通過v的最短路徑數，用當前鏈路權重計算at

(17)

(18)

根據這3個參數分別選擇SR節點。對于每個參數，都希望值越大的節點成為SRN中支持SR的節點。所以將對不同的SR配置比進行實驗。

(2)計算流量路徑：在確定了SR節點的鏈路權重和位置之后，計算出可用于每個流l的完整路徑集。如前所述，每個完整的流量路徑可被視為由3種類型的子路徑組成。網絡設備每個路徑只支持有限數量的SID，大的SLD也會增加包開銷，因此每個路徑使用的節點段(中間點)的數量應該受到限制。在這里設置一條路徑最多可以使用K個段，即第二類子路徑，然后用一個普通的DFS(深度優先搜索)得到每個流l的子路徑。請注意，在DFS時消除了重復的路徑和循環。

如圖2所示，從節點A到節點H有8個節點，并且顯示了它們之間的鏈接。每條邊上的數字表示該鏈路的權重，SR節點集SRN為 {B,D,G}。從節點A到節點H有一個業務需求。

圖2 流量路徑計算示例

首先，計算所有可用于流量需求的子路徑。表1展示了部分結果：從A到H的最短路徑是A-B-C-D-E-H，并且在這條路徑上支持SR的節點為B和 D，所以第一類的子路徑是A與B,D之間的最短路徑，同理，第二類的子路徑是節點B、D或G之間的最短路徑。第三類的子路徑是從節點A到H或從SR節點到H的最短路徑。

表1 部分子路徑

然后計算子路徑形成的路徑，每個路徑最多只能使用兩個節點段，并需要去掉一些重復的子路徑，結果見表2。圖2中還展示了4條路徑P1-P4。以P2為例。數據包遵循從節點A到節點H的最短路徑，直到到達節點B。從這里開始，它由SR路由，段列表為[G，D]。數據包依次經過子路徑(B，G)和(G，D)，到達節點D，然后通過OSPF協議路由到達目的節點H。在這里，路徑(A，B)(B，D)(D，G)(G，H)被消除，因為它與P3重復。

表2 所有有效子路徑

再使用Floyd-Warshall算法來計算所有的子路徑。然后遍歷每個SR節點，得到每個流的第一類和第三類子路徑。最后通過所有的SR節點對得到所有的分段。因此，計算所有子路徑的時間復雜度為O(|V|3+|L|·|SRN|+|SRN|2)。具有|V|節點和|E|邊的圖中DFS的時間復雜性為O(|V|+|E|)[44]。用于搜索流量路徑的圖有|SRN|+2個節點(所有SR節點加上s(l)和t(l))和|SRN|·|SRN|+2)邊(考慮任意兩個SR節點之間的子路徑，s(l)和SR節點，以及SR節點和t(l))。DFS是為每個|L|需求運行的。因此DFS的時間復雜度是O(|L|·[|SRN|+2+|SRN|·(|SRN|+2)])=O(|L|·|SRN|2))。

(3)解決LP問題：在獲得所有可用路徑之后，需要嘗試獲得狀態st+1，即流量分布，以及用于計算回報的Umax(st+1)。如何最大限度地減少網絡中鏈路的利用率。SR的一個特性是可以為同一個業務流定義多個SL，并且源節點將根據可配置的分割比率在可用SLs上分割業務。用線性規劃(LP)來尋找最佳分裂比和對應的st+1和Umax(st+1)。式(19)～式(22)為LP的計算公式

minUmax

(19)

(20)

(21)

0≤fl(p)≤1?l∈L,p∈Pl

(22)

在這里，Pl表示流量需求l的所有可用路徑的集合，p是其中的路徑。Sp是路徑p使用的子路徑集，s是Sp中的子路徑。Is,e是表示鏈路e是否屬于子路徑s的二進制表達。fl(P)表示路徑p上需求l的分流比。式(19)是目標函數。式(20)約束每個流量需求i在其路徑上完全路由。式(21)鏈路所承載的業務量不能超過其容量的限制。式(22)是非負約束。在變量和約束條件相對較少的情況下，該LP問題可以快速求解。這樣就可以得到Umax并用fl(P)計算st+1，如式(23)所示

(23)

2.3 在線路由優化

在這個階段，離線階段的輸出w和SRN作為鏈路權重的設置和SR節點的部署。而只為每個新TM在線優化路由路徑。當w和SRN固定時，所有可用的業務路徑也都是固定的。因此，只需要為每個需求確定最佳的分割比率。并且只需針對每個新TM解決LP問題，并獲得分流比和Umax。

3 實驗與評估

為了更好評估ST算法在部分部署的SR網絡中的性能，在此進行實驗。

3.1 實驗設置與數據集

3.1.1 設置

算法實現是基于Python 3.0和Keras實現的，整個實驗是在一臺Ubuntu系統的臺式電腦上進行，CPU 為英特爾I7 36 Ghz，內存為16 GB。顯卡為英偉達RTX 3080。DDPG訓練集個數為100，每集500步，前80%使用OU過程噪聲。重播緩沖區N設置為3200。minibatchN’為128。折現因子γ為0.9。τ設為0.001。

3.1.2 數據集

(1)拓撲結構：在評估中，對3種小型網絡拓撲進行了實驗：美國研究與教育網絡(Abilene)、中國教育研究網絡(CERNET)和歐洲研究與教育網絡(GEANT)。此外，還使用了文獻[17]提供的3種更大的拓撲：rf3967、rf1755和rf1221。

(2)流量矩陣：Abilene的TMs由TOTEM提供[18]。文獻[19]驗證了CERNET的TMs。GEANT的TMs數據集由Uhling提供[20]。Abilene和CERNET的TMs每5 min測量一次，所以一天有288次TMs。對于GEANT的TMs每15 min測量一次，所以一天有96次TMs。文獻[17]提供了3種較大拓撲的TMs，每個拓撲只有一個TM。對于Abilene、CERNET和GEANT，使用相同的初始鏈路權重設置和鏈路容量，并使用拓撲數據提供的鏈路權值設置和鏈路容量，用于3種較大的拓撲。

3.2 實驗結果評估

3.2.1 離線網絡設計性能

(1)SR節點選擇方法：首先嘗試確定最佳SR節點選擇方法。

結果如圖3所示，其中SRD-1和SRD-2是具有一個或兩個SRD的SRD方法，如文獻[1]所述，其它3條曲線對應于的ST算法，它有3種SR節點選擇方法DEG、BTW和MLL。將每個路徑K使用的最大節點段數設為1，并在不同的SR節點部署率下進行了實驗。在圖3(a)和圖3(b)中，當SR_Ratio=0.1時，沒有顯示ST和SRD-2 的Umax，因為網絡中只有一個SR節點。但是SRD-1方法仍然可以處理鄰接段，因為它可以指導流通過SR節點的特定接口。SRD-1和SRD-2的Umax在圖3(d)和圖3(e)中沒有顯示，因為文獻[1]提出的混合整數線性規劃(MILP)無法在300小時內求解。

圖3 最大鏈路利用率與SR部署比率之間的關系

根據實驗結果可知，最佳的SR節點選擇方法是MLL。這是因為MLL與網絡中的業務流有關，而DEG和BTW只描述拓撲特性。當SR_Ratio=0.1或0.2時，ST(MLL)的Umax不是最低的。然而，通過MLL選擇可以通過較低的部署率實現幾乎與全SR網絡中相同的TE性能。在Abilene中，當根據MLL選擇SR節點時，只有30%的具有SR特性的節點可以獲得與全SR網絡相同的性能，而按BTW或DEG進行選擇時，部署率應為0.6或0.8。GEANT、rf3967、rf1755和rf1221也有類似的結論。在CERNET中，3種SR節點選擇方法的Umax差距很小。

圖4顯示了SRD-1、SRD-2和ST(MLL)在GEANT上，SR_Ratio=0.3，K=1時的SR部署。圖中的每條邊代表兩個方向上的單向鏈接。很明顯，節點0和14是關鍵節點，因為這3種算法都選擇了它們。一個有趣的事實是SRD-1和SRD-2選擇相同的SR節點，即0、10、11、12、14和16。雖然SRD-2的輸出顯示10、14、16是一個SRD，0、11、12是另一個SRD，但是所有SR節點形成一個連通子圖。ST(MLL)選擇MLL最大的SR節點，不考慮連通性，選擇節點0、2、3、4、14、18，盡管2、3、4、14仍然是連通的。ST(MLL)放寬了SRD限制，可以提供更大的路由靈活性。

圖4 GEANT的SR部署(SR_Ratio=0.3)

(2)SR節點部署率：結果如圖3所示。首先可以看出，更多支持SR的節點可以提高TE性能。很明顯，Umax隨著SR_Ratio=0.1的增加而減小。網絡中更多的SR節點將提供更好的TE能力，因為業務流的路由將更加靈活。當網絡中SR節點較多時，該算法有機會讓網絡中的業務進行更好地繞行，從而避免擁塞鏈路。然而，隨著部署比例的增加，改進變得微不足道。

此外，可以看出，在除rf1221外的所有拓撲中，使用ST(MLL)升級20%到40%具有SR能力的節點將獲得與全SR網絡相同的TE性能。在rf1221中，使用這5種方法中的任何一種，僅升級10%的節點就足夠了，而且即使使用ST(MLL)時SR_Ratio=0.25，Umax仍然很低。綜合考慮TE性能和計算成本，認為0.3、0.3、0.3、0.4、0.2和0.05分別是ST(MLL)最合適的SR_Ratio。如果采用其它方法進行選擇，則配置比例應更高，以獲得相同的結果。然而，如果使用SRD-1ss或SRD-2方法，則需要分別對Abilene、CERNET和GEANT中的50%、30%、40%的節點進行SR特性升級，以獲得與所有具有SR特性的節點升級所獲得的Umax相當的值。在CERNET中，即使SR_Ratio=1.0，ST和SRD的Umax之間也存在明顯的差距。這是因為本文的算法在多個路徑上路由一個需求，而SRD只對一個需求使用一個單獨的路徑。

(3)每個路徑K可以使用的節點段數：以前的實驗是在K=1的情況下進行的。現在分析不同K值對結果的影響。結果見表5，將6種拓撲的SR_Ratio分別設置為0.3、0.3、0.3、0.4、0.2和0.05，并根據MLL選擇SR節點。然后在K=1和2時用3種拓撲進行了實驗。為了進一步驗證ST的TE能力，還給出了用Gurobi求解MCF問題的最優解。

很明顯，K值越大，鏈路利用率越高。但Umax在所有拓撲中沒有差異，即使結果精確到小數點后5位。MCF問題假設任何網絡節點都可以以任意比例對流進行分餾，這在現實中是不可行的。仍然接近最優解。但是，K越大，計算時間就越長。這是因為K值越大，LP問題中的可用路徑和變量越多，從而增加了求解問題的時間。因此，最多使用一條路徑K=1提供足夠的能力。

3.2.2 重量調整的必要性

算法的一個關鍵思想是權值調整(WA)。現在用實驗來強調它的必要性，結果如圖5所示。將結果與WA(用ST(MLL)表示)和沒有WA的結果進行了比較，這意味著采用初始權重設置而不改變它(SRTE(MLL，K=1)和SRTE(MLL，K=2)。此外，還展示了一個經典的OSPF網絡TE工作的結果，只優化了OSPF權重[21](用OSPF權重優化表示)。為了進一步展示WA方法的性能，在這里展示了使用文獻[21]中的局部搜索(LS)作為權重調整方法，并且仍然使用SRTE來獲得每個搜索節點的Umax(LS-SRTE(MLL))的結果。

圖5 最大鏈路利用率與WA之間的關系

首先，認為WA是必要的和關鍵的，它比使用大K值更有效。ST(MLL，K=1)獲得的Umax顯著優于SRTE(MLL，K=1)的結果。當使用SRTE(MLL，K=1)時，超過一半的節點需要使用SR特性進行升級，以在大多數拓撲中獲得較低的Umax。特別是當SR_Ratio≤0.3時，大多數拓撲結構的WA-ST(MLL，K=1)與SRTE(MLL，K=1)的Umax有很大的差距。然而，SRTE(MLL，K=1)和SRTE(MLL，K=2)的Umax非常接近，甚至在大多數情況下是相同的，因此將K提高到2并不能顯著改善結果。繼續提高K值可能會得到更好的結果，但請注意，網絡設備只支持有限數量的SID。

其次，使用的WA方法比文獻[21]中的LS方法更有效。在所有拓撲中，使用ST(MLL，K=1)獲得的Umax優于LS-SRTE(MLL，K=1)的結果。SR_Ratio=0.3，K=1，MLL的Abilene訓練進度如圖6所示。Umax通過訓練得到了明顯的改善。第10個集之前的Umax有時甚至大于2，但在第80個集之后，即OU過程噪聲未被添加時，Umax幾乎是穩定的。

圖6 不同學習階段的Umax和回報

最后，ST(K=1)在SR_Ratio=0.1的情況下，仍優于OSPF權重優化。盡管OSPF權重優化在3種小拓撲中的性能優于擁有較小SR_Ratio的SRTE(K=1)和SRTE(K=2)，但在3種較大的拓撲中，它的性能幾乎是最差的，這意味著文獻[13]中的局部搜索方法可能不能很好地伸縮。

SRTE的結果比SRD-1和SRD-2差，因為SRD方法不限制每條路徑使用的段數。但由于硬件的限制和數據包的開銷，必須考慮這種段列表長度的限制。

3.2.3 流量變化時的在線性能

圖7 使用不同算法的所有TM的最大鏈路利用率

表3 GEANT中的Umax的平均值和方差

4 結束語

本文研究了部分部署的SRv6網絡中，SRv6節點分散部署時的TE問題。該算法結合了OSPF網絡和全SR網絡的TE思想。采用強化學習算法DDPG對鏈路權值和SR節點配置進行優化，并通過求解一個線性規劃來確定最佳業務分流比。實驗和評估結果表明，該算法在實驗拓撲和TMs上表現良好。ST算法可以實現幾乎與部署了20%～40%的SR節點的完整SR網絡中相同的TE性能。此外，進一步的實驗驗證了在混合IP/SR網絡中進行權值調整的必要性。提出的方法在流量變化時表現良好。在未來，將進一步研究更大規模的混合IP/SR網絡的在線TE算法，包括流量變化、公平性考慮和故障恢復。