劉 威，黃 萍，孫鳳杰

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

0 引 言

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

混合IP/SR網(wǎng)絡(luò)設(shè)計(jì)的一個(gè)關(guān)鍵問(wèn)題是如何通過(guò)較少的SR節(jié)點(diǎn)來(lái)獲得與完整SR網(wǎng)絡(luò)幾乎相同的TE性能，因?yàn)镾R節(jié)點(diǎn)的部署越少，網(wǎng)絡(luò)升級(jí)就越容易。目前，基于混合IP/SR網(wǎng)絡(luò)的TE研究較少。并且目前的研究不能充分發(fā)揮IP/SRv6網(wǎng)絡(luò)的TE能力。

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

1 問(wèn)題描述

1.1 網(wǎng)絡(luò)場(chǎng)景

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

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

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

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

(1)從s(l)到t(l)的最短路徑在從s(l)到SR節(jié)點(diǎn)的最短路徑上，對(duì)應(yīng)于路由的第一階段。流量從這種子路徑開(kāi)始，通過(guò)OSPF協(xié)議路由，直到到達(dá)SR節(jié)點(diǎn)；

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

(3)從SR節(jié)點(diǎn)(或s(l))到t(l)的最短路徑，對(duì)應(yīng)于路由的第三階段。數(shù)據(jù)包通過(guò)OSPF協(xié)議路由，通過(guò)這種最短路徑到達(dá)目的節(jié)點(diǎn)。

1.2 問(wèn)題表述

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

minUmax

(1)

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

(2)

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

(3)

(4)

式(3)表示變量f和g之間的關(guān)系。式(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)時(shí),gli,t(l)(w)必須等于0，除非i是SR節(jié)點(diǎn)

(8)

在這里1的約束為任意節(jié)點(diǎn)到它自身，任何節(jié)點(diǎn)到s(l)，以及t(l)到任何節(jié)點(diǎn)，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ù)值約束。因?yàn)閣也是這個(gè)公式中的一個(gè)變量，所以它不能用優(yōu)化求解器來(lái)求解。

1.3 問(wèn)題復(fù)雜性

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

2 算 法

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

2.1 ST算法框架

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

綜上可知，ST有兩個(gè)階段：

(1)離線網(wǎng)絡(luò)設(shè)計(jì)：離線網(wǎng)絡(luò)設(shè)計(jì)階段的目的是獲得合適的鏈路權(quán)重和長(zhǎng)時(shí)間的SR節(jié)點(diǎn)部署。考慮到網(wǎng)絡(luò)流量的周期性，利用歷史流量矩陣計(jì)算了一個(gè)具有代表性的TM。然后使用離線DRL算法的深度確定策略梯度(DDPG)來(lái)優(yōu)化鏈路權(quán)重和SR部署。一旦獲得最佳鏈路權(quán)重設(shè)置和SR節(jié)點(diǎn)部署，它們?cè)诰W(wǎng)絡(luò)運(yùn)行時(shí)不會(huì)發(fā)生變化；

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

2.2 離線階段設(shè)計(jì)

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

動(dòng)作：這里的動(dòng)作是鏈接權(quán)重設(shè)置。更具體地說(shuō)，作用是一個(gè)1×|E|向量，at=[w(e)|e∈E]。

回報(bào)：回報(bào)rt按式(13)、式(14)計(jì)算。使用Umax(st)來(lái)表示當(dāng)網(wǎng)絡(luò)流量分布為st時(shí)最小的最大鏈路利用率。首先利用式(13)計(jì)算Umax(s1)與Umax(st)的比率

(13)

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

(14)

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

算法1：ST 離線階段

輸出：w,SRN,Umax

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

用θμ′←θμ,θQ′←θQ初始化目標(biāo)網(wǎng)絡(luò)μ′(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

通過(guò)最小化損失更新Critic網(wǎng)絡(luò)

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

θ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

下面將具體說(shuō)明：①如何獲得所有TMs的代表性TM(get_representative_TM函數(shù))；②如何獲得狀態(tài)st+1，即當(dāng)鏈路權(quán)重設(shè)置為at時(shí)，網(wǎng)絡(luò)流量分布Umax(st+1)和SRNt+1(get_state函數(shù))。

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

(15)

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

(1)選擇SR節(jié)點(diǎn)：為了獲得SR節(jié)點(diǎn)的最優(yōu)部署位置，充分利用部分部署SR網(wǎng)絡(luò)所提供的TE能力，需要考慮3個(gè)拓?fù)鋮?shù)：

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

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

(16)

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

2)中間性：節(jié)點(diǎn)的中間性是指通過(guò)該節(jié)點(diǎn)的最短路徑數(shù)。σst(v)表示從s到t通過(guò)v的最短路徑數(shù)，用當(dāng)前鏈路權(quán)重計(jì)算at

(17)

(18)

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

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

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

圖2 流量路徑計(jì)算示例

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

表1 部分子路徑

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

表2 所有有效子路徑

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

(3)解決LP問(wèn)題：在獲得所有可用路徑之后，需要嘗試獲得狀態(tài)st+1，即流量分布，以及用于計(jì)算回報(bào)的Umax(st+1)。如何最大限度地減少網(wǎng)絡(luò)中鏈路的利用率。SR的一個(gè)特性是可以為同一個(gè)業(yè)務(wù)流定義多個(gè)SL，并且源節(jié)點(diǎn)將根據(jù)可配置的分割比率在可用SLs上分割業(yè)務(wù)。用線性規(guī)劃(LP)來(lái)尋找最佳分裂比和對(duì)應(yīng)的st+1和Umax(st+1)。式(19)～式(22)為L(zhǎng)P的計(jì)算公式

minUmax

(19)

(20)

(21)

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

(22)

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

(23)

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

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

3 實(shí)驗(yàn)與評(píng)估

為了更好評(píng)估ST算法在部分部署的SR網(wǎng)絡(luò)中的性能，在此進(jìn)行實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)設(shè)置與數(shù)據(jù)集

3.1.1 設(shè)置

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

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

(1)拓?fù)浣Y(jié)構(gòu)：在評(píng)估中，對(duì)3種小型網(wǎng)絡(luò)拓?fù)溥M(jìn)行了實(shí)驗(yàn)：美國(guó)研究與教育網(wǎng)絡(luò)(Abilene)、中國(guó)教育研究網(wǎng)絡(luò)(CERNET)和歐洲研究與教育網(wǎng)絡(luò)(GEANT)。此外，還使用了文獻(xiàn)[17]提供的3種更大的拓?fù)洌簉f3967、rf1755和rf1221。

(2)流量矩陣：Abilene的TMs由TOTEM提供[18]。文獻(xiàn)[19]驗(yàn)證了CERNET的TMs。GEANT的TMs數(shù)據(jù)集由Uhling提供[20]。Abilene和CERNET的TMs每5 min測(cè)量一次，所以一天有288次TMs。對(duì)于GEANT的TMs每15 min測(cè)量一次，所以一天有96次TMs。文獻(xiàn)[17]提供了3種較大拓?fù)涞腡Ms，每個(gè)拓?fù)渲挥幸粋€(gè)TM。對(duì)于Abilene、CERNET和GEANT，使用相同的初始鏈路權(quán)重設(shè)置和鏈路容量，并使用拓?fù)鋽?shù)據(jù)提供的鏈路權(quán)值設(shè)置和鏈路容量，用于3種較大的拓?fù)洹?/p>

3.2 實(shí)驗(yàn)結(jié)果評(píng)估

3.2.1 離線網(wǎng)絡(luò)設(shè)計(jì)性能

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

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

圖3 最大鏈路利用率與SR部署比率之間的關(guān)系

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

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

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

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

此外，可以看出，在除rf1221外的所有拓?fù)渲?，使用ST(MLL)升級(jí)20%到40%具有SR能力的節(jié)點(diǎn)將獲得與全SR網(wǎng)絡(luò)相同的TE性能。在rf1221中，使用這5種方法中的任何一種，僅升級(jí)10%的節(jié)點(diǎn)就足夠了，而且即使使用ST(MLL)時(shí)SR_Ratio=0.25，Umax仍然很低。綜合考慮TE性能和計(jì)算成本，認(rèn)為0.3、0.3、0.3、0.4、0.2和0.05分別是ST(MLL)最合適的SR_Ratio。如果采用其它方法進(jìn)行選擇，則配置比例應(yīng)更高，以獲得相同的結(jié)果。然而，如果使用SRD-1ss或SRD-2方法，則需要分別對(duì)Abilene、CERNET和GEANT中的50%、30%、40%的節(jié)點(diǎn)進(jìn)行SR特性升級(jí)，以獲得與所有具有SR特性的節(jié)點(diǎn)升級(jí)所獲得的Umax相當(dāng)?shù)闹?。在CERNET中，即使SR_Ratio=1.0，ST和SRD的Umax之間也存在明顯的差距。這是因?yàn)楸疚牡乃惴ㄔ诙鄠€(gè)路徑上路由一個(gè)需求，而SRD只對(duì)一個(gè)需求使用一個(gè)單獨(dú)的路徑。

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

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

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

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

圖5 最大鏈路利用率與WA之間的關(guān)系

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

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

圖6 不同學(xué)習(xí)階段的Umax和回報(bào)

最后，ST(K=1)在SR_Ratio=0.1的情況下，仍優(yōu)于OSPF權(quán)重優(yōu)化。盡管OSPF權(quán)重優(yōu)化在3種小拓?fù)渲械男阅軆?yōu)于擁有較小SR_Ratio的SRTE(K=1)和SRTE(K=2)，但在3種較大的拓?fù)渲校男阅軒缀跏亲畈畹?，這意味著文獻(xiàn)[13]中的局部搜索方法可能不能很好地伸縮。

SRTE的結(jié)果比SRD-1和SRD-2差，因?yàn)镾RD方法不限制每條路徑使用的段數(shù)。但由于硬件的限制和數(shù)據(jù)包的開(kāi)銷，必須考慮這種段列表長(zhǎng)度的限制。

3.2.3 流量變化時(shí)的在線性能

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

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

4 結(jié)束語(yǔ)

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