基于段路由的IPv6網(wǎng)絡優(yōu)化算法

劉 威，黃 萍，孫鳳杰

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

0 引 言

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

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

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

1 問題描述

1.1 網(wǎng)絡場景

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

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

圖1 一個混合IP/SRv6網(wǎng)絡

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

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

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

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

1.2 問題表述

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

minUmax

(1)

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

(2)

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

(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節(jié)點

(8)

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

(9)

式(9)為SR部署比約束

i,j∈V,e∈E

(10)

(11)

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

(12)

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

1.3 問題復雜性

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

2 算 法

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

2.1 ST算法框架

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

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

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

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

2.2 離線階段設計

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

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

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

(13)

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

(14)

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

算法1：ST 離線階段

輸出：w,SRN,Umax

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

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

初始化重播緩沖區(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網(wǎng)絡

按采樣策略梯度更新Actor網(wǎng)絡

θ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函數(shù))；②如何獲得狀態(tài)st+1，即當鏈路權重設置為at時，網(wǎng)絡流量分布Umax(st+1)和SRNt+1(get_state函數(shù))。

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

(15)

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

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

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

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

(16)

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

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

(17)

(18)

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

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

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

圖2 流量路徑計算示例

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

表1 部分子路徑

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

表2 所有有效子路徑

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

(3)解決LP問題：在獲得所有可用路徑之后，需要嘗試獲得狀態(tài)st+1，即流量分布，以及用于計算回報的Umax(st+1)。如何最大限度地減少網(wǎng)絡中鏈路的利用率。SR的一個特性是可以為同一個業(yè)務流定義多個SL，并且源節(jié)點將根據(jù)可配置的分割比率在可用SLs上分割業(yè)務。用線性規(guī)劃(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)是目標函數(shù)。式(20)約束每個流量需求i在其路徑上完全路由。式(21)鏈路所承載的業(yè)務量不能超過其容量的限制。式(22)是非負約束。在變量和約束條件相對較少的情況下，該LP問題可以快速求解。這樣就可以得到Umax并用fl(P)計算st+1，如式(23)所示

(23)

2.3 在線路由優(yōu)化

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

3 實驗與評估

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

3.1 實驗設置與數(shù)據(jù)集

3.1.1 設置

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

3.1.2 數(shù)據(jù)集

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

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

3.2 實驗結果評估

3.2.1 離線網(wǎng)絡設計性能

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

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

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

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

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

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

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

此外，可以看出，在除rf1221外的所有拓撲中，使用ST(MLL)升級20%到40%具有SR能力的節(jié)點將獲得與全SR網(wǎng)絡相同的TE性能。在rf1221中，使用這5種方法中的任何一種，僅升級10%的節(jié)點就足夠了，而且即使使用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%的節(jié)點進行SR特性升級，以獲得與所有具有SR特性的節(jié)點升級所獲得的Umax相當?shù)闹?。在CERNET中，即使SR_Ratio=1.0，ST和SRD的Umax之間也存在明顯的差距。這是因為本文的算法在多個路徑上路由一個需求，而SRD只對一個需求使用一個單獨的路徑。

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

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

3.2.2 重量調(diào)整的必要性

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

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

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

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

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

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

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

3.2.3 流量變化時的在線性能

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

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

4 結束語

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