李碩朋，方娟，陳肯

（1.北京工業(yè)大學(xué)信息學(xué)部，北京 100124；2.法國索邦巴黎北大學(xué)伽利略理工學(xué)院，維爾塔納斯 93430）

1 引言

近年來，5G、云計算、物聯(lián)網(wǎng)、自動駕駛等行業(yè)的快速發(fā)展給未來網(wǎng)絡(luò)提出了新的挑戰(zhàn)。行業(yè)應(yīng)用的新需求催生了諸多網(wǎng)絡(luò)新技術(shù)，也推動了未來網(wǎng)絡(luò)的發(fā)展。其中，天地一體化網(wǎng)絡(luò)、智能網(wǎng)絡(luò)、區(qū)塊鏈和確定性網(wǎng)絡(luò)等關(guān)鍵技術(shù)代表著未來網(wǎng)絡(luò)的發(fā)展方向[1]。這些關(guān)鍵技術(shù)可以在高帶寬、高可靠性低時延、高安全性、萬物互聯(lián)等方面賦能未來網(wǎng)絡(luò)。

高可靠性低時延[2]作為5G 的三大目標(biāo)之一，在工業(yè)互聯(lián)網(wǎng)、自動駕駛等領(lǐng)域有著極其迫切的需求。確定性網(wǎng)絡(luò)（DetNet,deterministic network）[3]作為實現(xiàn)高可靠性低時延的手段之一，旨在解決傳統(tǒng)網(wǎng)絡(luò)上，交換和路由過程中欠缺服務(wù)質(zhì)量保障的問題。不同于傳統(tǒng)的基于盡力而為的網(wǎng)絡(luò)，確定性網(wǎng)絡(luò)需要保障服務(wù)的端到端時延和抖動以及數(shù)據(jù)的完整性，保證網(wǎng)絡(luò)不會因故障導(dǎo)致數(shù)據(jù)分組丟失、亂序等問題發(fā)生。

確定性網(wǎng)絡(luò)需要在二層和三層上實現(xiàn)。二層的確定性網(wǎng)絡(luò)主要由時延敏感網(wǎng)絡(luò)（TSN,time sensitive network）[4]實現(xiàn)。TSN 利用循環(huán)隊列和轉(zhuǎn)發(fā)（CQF,cyclic queuing and forwarding）[5]協(xié)議實現(xiàn)全局時間同步、確定性轉(zhuǎn)發(fā)和幀保護(hù)。

三層確定性網(wǎng)絡(luò)[6]采用典型的軟件定義網(wǎng)絡(luò)（SDN,software defined network）架構(gòu)，將控制平面與轉(zhuǎn)發(fā)平面分離，通過對三層網(wǎng)絡(luò)設(shè)備的集中管理與配置，實現(xiàn)確定性轉(zhuǎn)發(fā)[7]。

確定性網(wǎng)絡(luò)可以部署在IP（Internet protocol）、MPLS（multi-protocol label switching）等網(wǎng)絡(luò)上。目前，基于MPLS 的確定性網(wǎng)絡(luò)標(biāo)準(zhǔn)和草案較多。但是，MPLS 網(wǎng)絡(luò)協(xié)議較復(fù)雜，特別是流量工程、資源預(yù)留等確定性網(wǎng)絡(luò)需求較多的功能中，MPLS的諸多協(xié)議增加了網(wǎng)絡(luò)的復(fù)雜性。

近年來，分段路由（SR,segment routing）[8]作為實現(xiàn)SDN 的新手段，受到越來越多的關(guān)注。分段路由作為一種源路由技術(shù)，簡化了協(xié)議，在源路由器對數(shù)據(jù)報文進(jìn)行“編碼”，在報頭中插入有序的列表，用于指示報文的轉(zhuǎn)發(fā)路徑。分段路由相比傳統(tǒng)的資源預(yù)留和分布式協(xié)議降低了控制的冗余性，操作簡單，擴展性好，具備強大的可編程能力，被視為實現(xiàn)SDN2.0 的關(guān)鍵技術(shù)。

SRv6（segment routing over IPv6）綜合了分段路由和IPv6 的優(yōu)勢，能夠大大減輕網(wǎng)絡(luò)復(fù)雜度，為確定性網(wǎng)絡(luò)的部署實現(xiàn)帶來便利性，在提供服務(wù)保護(hù)等確定性網(wǎng)絡(luò)關(guān)鍵功能上具有前景。

服務(wù)保護(hù)是確定性網(wǎng)絡(luò)的重要功能。服務(wù)保護(hù)旨在自主地處理網(wǎng)絡(luò)故障。網(wǎng)絡(luò)故障包括節(jié)點故障和鏈接故障。服務(wù)保護(hù)通過配置備份路徑，為網(wǎng)絡(luò)流提供抵御網(wǎng)絡(luò)故障的能力，保障端到端傳輸?shù)耐暾浴?/p>

本文關(guān)注基于分段路由的確定性網(wǎng)絡(luò)實現(xiàn)模式，在SRv6 確定性網(wǎng)絡(luò)的條件下，重點討論服務(wù)保護(hù)機制的策略與算法實現(xiàn)。本文貢獻(xiàn)有以下3個方面：1) 提出了基于SRv6的面向服務(wù)的確定性網(wǎng)絡(luò)服務(wù)保護(hù)框架；2) 提出了基于帶寬資源共享的確定性網(wǎng)絡(luò)保護(hù)系統(tǒng)模型；3) 提出了啟發(fā)式的共享保護(hù)路徑選擇算法，優(yōu)化了網(wǎng)絡(luò)資源的利用率。

2 相關(guān)工作

IEEE 802.1 TSN工作組致力于為二層確定性服務(wù)制定標(biāo)準(zhǔn)（RFC,request for comment）。IETF（Internet engineering task force）確定性網(wǎng)絡(luò)工作組同TSN 工作組協(xié)作為三層確定性服務(wù)制定標(biāo)準(zhǔn)。確定性網(wǎng)絡(luò)工作組已完成若干標(biāo)準(zhǔn)，并提出了諸多草案。這些標(biāo)準(zhǔn)和草案定義了確定性網(wǎng)絡(luò)的架構(gòu)、流模型、部署方式和網(wǎng)絡(luò)互聯(lián)等。

確定性網(wǎng)絡(luò)架構(gòu)[6]由應(yīng)用平面、控制平面和數(shù)據(jù)平面構(gòu)成。應(yīng)用平面通常是一個帶有特定服務(wù)或應(yīng)用請求的用戶，并通過北向接口和控制平面溝通應(yīng)用請求。控制平面接收應(yīng)用平面的請求，利用自身的控制功能，例如路徑計算單元（PCE,path computation element），完成路徑計算、網(wǎng)絡(luò)管理，并通過南向接口將指令下發(fā)給數(shù)據(jù)平面。數(shù)據(jù)平面由網(wǎng)絡(luò)轉(zhuǎn)發(fā)設(shè)備構(gòu)成，根據(jù)控制平面的指令執(zhí)行轉(zhuǎn)發(fā)操作，并將網(wǎng)絡(luò)狀態(tài)通過南向接口傳遞給控制平面。

應(yīng)用平面的用戶請求被抽象為確定性網(wǎng)絡(luò)的流和服務(wù)模型。RFC 9016[9]定義了確定性網(wǎng)絡(luò)服務(wù)的三層模型參數(shù)：服務(wù)參數(shù)、流參數(shù)和流-應(yīng)用參數(shù)。一個確定性網(wǎng)絡(luò)服務(wù)可以包含一個或多個確定性網(wǎng)絡(luò)流，一個確定性網(wǎng)絡(luò)流可以包含一個或多個確定性網(wǎng)絡(luò)流-應(yīng)用。服務(wù)參數(shù)包含服務(wù)的類型、特征、連接性、狀態(tài)等。流參數(shù)除了包含服務(wù)的基本信息外，還定義了流的部署方式（IP、MPLS）、流量特征（周期、周期內(nèi)包數(shù)量和負(fù)載）、流優(yōu)先級、流帶寬時延需求等。流-應(yīng)用參數(shù)與流參數(shù)類似。

確定性網(wǎng)絡(luò)控制平面[10]統(tǒng)一了網(wǎng)絡(luò)的控制層和管理層?？刂茖又С謩討B(tài)創(chuàng)建、修改和刪除確定性網(wǎng)絡(luò)流，支持流的聚合和反聚合，支持通過應(yīng)用接口進(jìn)行流的實例化，支持基于時間同步的隊列控制，具備發(fā)布節(jié)點和鏈接資源的能力，能夠處理確定性網(wǎng)絡(luò)域中的大規(guī)模確定性網(wǎng)絡(luò)流。管理平面監(jiān)測確定性網(wǎng)絡(luò)流的性能，支持流的完整性和連接性檢測，保證確定性網(wǎng)絡(luò)性能達(dá)到要求。

確定性網(wǎng)絡(luò)數(shù)據(jù)平面[11]由服務(wù)層和轉(zhuǎn)發(fā)層構(gòu)成。服務(wù)層提供包的復(fù)制、去重和排序功能（PREOF,packet replication,elimination and ordering function）。轉(zhuǎn)發(fā)層提供轉(zhuǎn)發(fā)保證，包括顯性路徑、流量工程和擁塞控制。

確定性網(wǎng)絡(luò)數(shù)據(jù)平面可以部署在多種環(huán)境中。RFC 8939[12]定義了使用IP 層和高層協(xié)議的頭信息實現(xiàn)確定性網(wǎng)絡(luò)流的標(biāo)記和服務(wù)傳遞。RFC 8964[13]定義了利用偽線（PW,pseudowire）封裝和MPLS流量工程（MPLS-TE）在MPLS 網(wǎng)絡(luò)上實現(xiàn)確定性網(wǎng)絡(luò)。

基于MPLS 的確定性網(wǎng)絡(luò)數(shù)據(jù)平面包含d-CW（DetNet control word）、S-Label 和L-Label。d-CW表示包的序號，S-Label 用于確定性網(wǎng)絡(luò)服務(wù)身份識別，F(xiàn)-Label 用于提供顯性路由。

確定性網(wǎng)絡(luò)數(shù)據(jù)平面的多種部署方式都可以承載在TSN 上。MPLS-TSN 草案[14]提出MPLS 和TSN 需要協(xié)同提供服務(wù)保護(hù)、資源分配和顯性路由，但并未提供具體的網(wǎng)絡(luò)互聯(lián)方法。

SRv6-TSN 草案[15]討論了通過SRv6 網(wǎng)絡(luò)連接TSN 的基礎(chǔ)架構(gòu)。分段路由是一種源路由方法，可以在IP 或MPLS 上實現(xiàn)。源節(jié)點利用分段列表（SL,segment list）表示完整的轉(zhuǎn)發(fā)路徑。分段路由在流量工程中有著重要的應(yīng)用[16-19]。

SRv6 利用IPv6 地址128 bit 的可編程能力，豐富了SRv6 指令表達(dá)的范疇，使其不僅可以表達(dá)轉(zhuǎn)發(fā)路徑，也可以在其他場景（例如網(wǎng)絡(luò)功能虛擬化[20]）中實現(xiàn)網(wǎng)絡(luò)的可編程性。但是，現(xiàn)有的SRv6-TSN草案并未針對SRv6 確定性網(wǎng)絡(luò)數(shù)據(jù)平面的服務(wù)層、轉(zhuǎn)發(fā)層和路由保護(hù)等提出具體方案。盡管如此，我們依舊可以看到，SRv6 可以作為確定性網(wǎng)絡(luò)的數(shù)據(jù)平面，在確定性網(wǎng)絡(luò)的場景中發(fā)揮不可或缺的重要作用。

確定性網(wǎng)絡(luò)的服務(wù)保護(hù)機制是實現(xiàn)網(wǎng)絡(luò)確定性的重中之重。保護(hù)機制包含網(wǎng)絡(luò)故障的監(jiān)測和路由保護(hù)。DetNet-OAM 草案[21]提出了利用ACH 實現(xiàn)確定性網(wǎng)絡(luò)流異常探測和性能測試。

現(xiàn)有的時延敏感網(wǎng)絡(luò)/確定性網(wǎng)絡(luò)的路由保護(hù)機制都是基于簡單的幀/流的復(fù)制。例如，TSN 在IEEE 802.1CB 中定義了保護(hù)機制FRER（frame replication and elimination for redundancy）。PREOF在確定性網(wǎng)絡(luò)數(shù)據(jù)平面實現(xiàn)類似FRER 的功能?；趶?fù)制的路由保護(hù)需要雙倍的網(wǎng)絡(luò)帶寬的需求，網(wǎng)絡(luò)中有大量重復(fù)無效的包傳輸，導(dǎo)致網(wǎng)絡(luò)帶寬利用率低。因此，確定性網(wǎng)絡(luò)需要更加靈活、高效的服務(wù)保護(hù)機制。本文認(rèn)為路由保護(hù)策略是實現(xiàn)服務(wù)保護(hù)機制的重要方法。

路由保護(hù)策略[22]根據(jù)是否預(yù)留資源分為被動和主動保護(hù)策略。被動保護(hù)不預(yù)留資源，當(dāng)監(jiān)測到網(wǎng)絡(luò)故障時，重新計算和配置可用路由；主動保護(hù)預(yù)先計算并預(yù)留網(wǎng)絡(luò)資源，當(dāng)監(jiān)測到網(wǎng)絡(luò)故障時，直接使用備份路由。

根據(jù)備份路由的選擇[23]，路由保護(hù)策略又分為鏈接保護(hù)（本地保護(hù)）和路徑保護(hù)（全局保護(hù)）。鏈接保護(hù)針對網(wǎng)絡(luò)中每一個鏈接選擇一條備份路徑；路徑保護(hù)針對一條端到端的路徑，提供一條不相交的備份路徑。

3 基于SRv6 的確定性網(wǎng)絡(luò)服務(wù)保護(hù)架構(gòu)

本節(jié)提出了基于SRv6 的確定性網(wǎng)絡(luò)服務(wù)保護(hù)架構(gòu)。

3.1 基于SRv6 的確定性網(wǎng)絡(luò)架構(gòu)

基于SRv6 的確定性網(wǎng)絡(luò)架構(gòu)如圖1 所示。SRv6 確定性網(wǎng)絡(luò)控制平面為一個SDN 控制器，負(fù)責(zé)收集網(wǎng)絡(luò)狀態(tài)，計算路徑，并下發(fā)指令。

數(shù)據(jù)平面二層（L2）采用TSN，三層（L3）采用SRv6。分段路由頭（SRH,segment routing header）用于實現(xiàn)確定性網(wǎng)絡(luò)數(shù)據(jù)平面的服務(wù)層和轉(zhuǎn)發(fā)層。本文將SRH 中的分段表（SL,segment list）分為服務(wù)層分段表（S-SL）和轉(zhuǎn)發(fā)層分段表（F-SL）。S-SL定義了服務(wù)層必需的PREOF 功能。F-SL 通過每個SL 提供基于源路由的顯性路徑轉(zhuǎn)發(fā)。

數(shù)據(jù)平面設(shè)備由終端設(shè)備（CE,customer equipment）、運營商邊緣設(shè)備（PE,provider edge）和中繼設(shè)備（R,relay node）構(gòu)成。二層終端設(shè)備作為TSN 的Talker 和Listener，發(fā)送和接收TSN 流。三層包含接入設(shè)備和中繼設(shè)備。在圖1 中，接入設(shè)備1 根據(jù)發(fā)送端TSN 流的需求特征和SDN 控制器的路徑結(jié)果，將整個路徑通過SRv6 封裝到F-SL 中。中繼設(shè)備根據(jù)F-SL執(zhí)行轉(zhuǎn)發(fā)。接入設(shè)備2解除SRv6封裝并將TSN 流轉(zhuǎn)發(fā)給終端設(shè)備。

圖1 基于SRv6 的確定性網(wǎng)絡(luò)架構(gòu)

接入設(shè)備和中繼設(shè)備需要在三層提供服務(wù)保護(hù)，以便在網(wǎng)絡(luò)節(jié)點或鏈接發(fā)生故障時，保障網(wǎng)絡(luò)的不中斷和網(wǎng)絡(luò)流的低時延。

3.2 服務(wù)區(qū)分

本文將確定性網(wǎng)絡(luò)服務(wù)分成三類，嚴(yán)格確定性服務(wù)、一般確定性服務(wù)和盡力而為服務(wù)。針對不同的服務(wù)，基于SRv6 的確定性網(wǎng)絡(luò)將提供不同的服務(wù)保護(hù)策略。

嚴(yán)格確定性服務(wù)是針對具有嚴(yán)格的低時延、高可靠性需求的服務(wù)，在確定性網(wǎng)絡(luò)層提供基于流復(fù)制的服務(wù)保護(hù)機制，利用源點復(fù)制和終點重排序函數(shù)，在網(wǎng)絡(luò)中傳遞兩份同樣的網(wǎng)絡(luò)流。

一般確定性服務(wù)適用于有低時延、高可靠性需求，但服務(wù)等級低或不愿付出雙倍帶寬成本的用戶。對此，本文采用主動保護(hù)策略，預(yù)先計算備份路徑并預(yù)留帶寬，但只在主路徑中傳輸流，不在備份路徑中傳輸流。當(dāng)主路徑發(fā)生故障時，切換到備份路徑，保障服務(wù)不中斷和低時延。

盡力而為服務(wù)不提供備份路徑，可利用鏈路的閑置帶寬（包括備份路徑的預(yù)留帶寬）傳輸流。在高等級服務(wù)到來或備份路徑預(yù)留帶寬需要被啟用時，盡力而為服務(wù)將被緩存或丟棄，所占用的資源將被釋放。

圖2 解釋了三類服務(wù)在鏈接上的帶寬分布。在此鏈接中，嚴(yán)格確定性服務(wù)a 的主路由和c 的備份路由分別占據(jù)一部分的帶寬；一般確定性服務(wù)b 的主路由占據(jù)一部分的帶寬；一般確定性服務(wù)d 的備份路由和盡力而為服務(wù)共享一部分帶寬。

圖2 三類服務(wù)在鏈接上的帶寬分布

3.3 SR Policy 實現(xiàn)服務(wù)保護(hù)

本文利用SR Policy 實現(xiàn)針對不同服務(wù)的路由保護(hù)。SR Policy 定義了三元組（headend,color,endpoint），其中headend 為頭節(jié)點，endpoint 為流的終點，color 可以用來定義優(yōu)先級不同的服務(wù)。每種color 可以攜帶多個帶有優(yōu)先級的候選路徑。

為了實現(xiàn)確定性網(wǎng)絡(luò)的保護(hù)機制，本文將嚴(yán)格確定性服務(wù)、一般確定性服務(wù)和盡力而為服務(wù)定義為3 種color。對于一般確定性服務(wù)，每個color 攜帶一個主路徑和一個備份路徑。當(dāng)主路徑發(fā)生故障時，借助SR Policy 實現(xiàn)備份路徑的切換。

3.4 路徑保護(hù)策略

根據(jù)備份路由選擇策略，本文發(fā)現(xiàn)，鏈接保護(hù)的缺點是容易產(chǎn)生重復(fù)路徑，導(dǎo)致路徑變長。路徑保護(hù)通過選擇不相交路徑，可以保證路徑長度，具有較低的端到端時延。不相交路徑保護(hù)也可同時實現(xiàn)點的保護(hù)。

在確定性網(wǎng)絡(luò)中，需要保證路徑盡可能短，以滿足服務(wù)的時延需求。長路徑會使時延變大，抖動變大。因此，在確定性網(wǎng)絡(luò)中，本文采用不相交路徑保護(hù)。

圖3 給出了路徑保護(hù)的示例。假設(shè)確定性網(wǎng)絡(luò)域由5 個支持SRv6 的路由器組成，網(wǎng)絡(luò)中有2 個確定性網(wǎng)絡(luò)流D1=(CE1→CE2)和D2=(CE3→CE2)。D1的主路徑為P1=(CE1→PE1→R2→PE2→CE2)，備份路徑為B1=(CE1→PE1→R1→PE2→CE2)；D2的主路徑為 P2=(CE3→PE3→PE2→CE2)，備份路徑為B2=(CE3→PE3→R1→PE2→CE2)。B1和B2用于保護(hù)P1和P2上的鏈接，也可以保護(hù)節(jié)點的故障。例如，若中繼設(shè)備R2出現(xiàn)故障，B1可確保網(wǎng)絡(luò)流不受影響。

圖3 不相交路徑保護(hù)策略

3.5 帶寬資源共享

由于嚴(yán)格確定性網(wǎng)絡(luò)和盡力而為服務(wù)的保護(hù)機制比較明確，而一般確定性網(wǎng)絡(luò)的保護(hù)配置更靈活，因此本文在這里深入討論一般確定性網(wǎng)絡(luò)的保護(hù)策略。

針對一般確定性服務(wù)，鏈接上僅預(yù)留備份帶寬資源。由于網(wǎng)絡(luò)中很少同時發(fā)生多個故障，單鏈接故障是網(wǎng)絡(luò)中最普遍的故障。注意到，在單鏈接故障的情況下，在同一條鏈接上的、用于保護(hù)不同主路徑的備份路徑上的帶寬可以被共享。這種資源共享可以最大限度地減少備份帶寬的占用率，進(jìn)而提升整個網(wǎng)絡(luò)的效率。

例如，在圖3 中，(R1→PE2)用于同時保護(hù)D1和D2。在P1和P2不同時發(fā)生故障的情況下，(R1→PE2)上的備份帶寬資源可以被共享。

4 共享保護(hù)系統(tǒng)模型

本節(jié)給出了基于SRv6 的確定性網(wǎng)絡(luò)服務(wù)共享保護(hù)機制的數(shù)學(xué)模型。

4.1 網(wǎng)絡(luò)模型

設(shè)確定性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有向圖G=(V,E)，其中V代表點的集合，E代表鏈接的集合。每個鏈接上總的可用帶寬為BWij。確定性網(wǎng)絡(luò)流由七元組d=(id,source,destination,bandwidth,time,duration,delay)表示，其中id 為確定性網(wǎng)絡(luò)流標(biāo)識符，source 為源點，destination 為終點，bandwidth 為帶寬需求，time為流的到達(dá)時間，duration 為持續(xù)時間，delay 為最大時延。

確定性網(wǎng)絡(luò)流請求隨機到達(dá)網(wǎng)絡(luò)，共享保護(hù)模型的目標(biāo)是根據(jù)網(wǎng)絡(luò)現(xiàn)有流的主路由和備份路由的情況，給出當(dāng)前請求的主路由和備份路由的方案，在滿足網(wǎng)絡(luò)資源、請求時延限制條件的前提下，減少鏈接帶寬的占用率，提升資源利用率，進(jìn)而提升確定性網(wǎng)絡(luò)流的整體接收率。

4.2 優(yōu)化問題模型

共享保護(hù)系統(tǒng)模型的實質(zhì)是一個優(yōu)化問題，對此建立如下模型。

4.2.1路徑限制條件

根據(jù)路徑保護(hù)理論，主路徑和備份路徑不相交

式(3)保證了在一條鏈接上，有且僅有主路由或備份路由。式(1)～式(3)共同保證確定性網(wǎng)絡(luò)流d具有2 條不相交的路徑，分別作為主路徑和備份路徑。

4.2.2共享保護(hù)帶寬限制條件

圖4 給出了鏈接ij上的共享保護(hù)帶寬示意。其中，F(xiàn)d表示確定性網(wǎng)絡(luò)流d的帶寬需求，PBij表示在該鏈接上已使用的主路徑帶寬（PB,primary bandwidth）之和，BBij表示最大備份路徑帶寬（BB,backup bandwidth），BBij(mn)表示主路徑在mn上、備份路徑在ij上的所有網(wǎng)絡(luò)流的帶寬之和。

圖4 鏈接ij 上的共享保護(hù)帶寬示意

在圖4 中，mn和m'n'的備份路徑同時經(jīng)過ij，兩者的備份帶寬資源在ij上被共享，ij上只需預(yù)留兩者的最大值，即可滿足備份帶寬資源的要求。當(dāng)有新的網(wǎng)絡(luò)流d到達(dá)時，將被添加到BBij(mn)上，同時更新BBij。因此鏈路上的備份帶寬需滿足

由圖4 也可以看出，任意鏈路上的主路由帶寬和備份路由帶寬之和需小于鏈路總帶寬，即滿足限制條件

式(4)～式(6)實現(xiàn)了確定性網(wǎng)絡(luò)共享保護(hù)模型的核心思想，通過對網(wǎng)絡(luò)中帶寬資源的共享，提升了資源利用率。

4.2.3確定性網(wǎng)絡(luò)時延限制條件

TSN 的循環(huán)隊列轉(zhuǎn)發(fā)機制（CQF,cyclic queuing and forwarding）[24]定義了保證TSN 確定性傳輸?shù)哪Ｐ?。在確定性網(wǎng)絡(luò)共享保護(hù)模型中，本文采用基于CQF 的時延限制條件，即CQF 模型的最大時延需小于確定性網(wǎng)絡(luò)的時延條件。因此，主路由和備份路由都需滿足

其中，CT 表示時隙長度。

4.2.4優(yōu)化目標(biāo)

為了保證網(wǎng)絡(luò)時延并提高資源利用率，優(yōu)化目標(biāo)同時考慮了主路徑、備份路徑和鏈路帶寬。優(yōu)化目標(biāo)為

其中，λ1表示路徑優(yōu)化權(quán)重，其值決定主路徑和備份路徑的時延；λ2表示備份帶寬優(yōu)化權(quán)重，由于備份路徑共享特征的存在，較長的路徑也有可能提升路徑共享效率，進(jìn)而降低整體帶寬占用消耗。

因此，優(yōu)化主路徑和備份路徑是保證網(wǎng)絡(luò)低時延的關(guān)鍵。同時，優(yōu)化備份帶寬對于提升網(wǎng)絡(luò)資源的利用率也具有重要意義。

5 路徑選擇算法

上述優(yōu)化問題為典型的整數(shù)線性規(guī)劃問題，屬于NP 完全問題。為解決上述優(yōu)化問題，本文提出基于最短路徑的啟發(fā)式算法，偽代碼如算法1 所示。

算法1共享資源路徑選擇算法

算法的輸入為確定性網(wǎng)絡(luò)流和網(wǎng)絡(luò)帶寬的狀態(tài)，輸出為該流的主路徑和備份路徑。

算法1)～3)行用于計算主路由。為了優(yōu)化鏈路帶寬利用率，將鏈路權(quán)重設(shè)為剩余帶寬，此權(quán)重用于計算主路由。第2)行根據(jù)確定性網(wǎng)絡(luò)流帶寬需求，刪除不滿足帶寬限制條件的鏈接。第3)行利用Dijkstra 最短路徑算法預(yù)計算主路徑。

算法4)～8)行用于計算備份路由。如果主路徑存在，為了計算不相交備份路徑，在第5)行刪除主路徑。第6)行根據(jù)網(wǎng)絡(luò)備份帶寬狀態(tài)，刪除不滿足備份帶寬限制條件的鏈接。第7)行設(shè)置鏈接權(quán)重為1/γij，其中γij為備份帶寬參數(shù)，計算方法為

其中，path 為已計算的主路徑；ε是一個較小的數(shù)，防止結(jié)果為0。式(10)對于主路徑path 上的所有鏈接mn，計算備份路徑的剩余帶寬均值。事實上，這個值反映了帶寬資源共享的程度。例如，在的情況下，結(jié)合式(5)可以得出，F(xiàn)d部署后不會增加備份帶寬BBij的值，即帶寬共享被最大化利用。隨后，第8)行利用Dijkstra 最短路徑算法預(yù)計算備份路徑。

如果備份路徑存在，則在第9)和第10)行保存主路徑和備份路徑，并更新帶寬參數(shù)，確定性網(wǎng)絡(luò)流部署成功。若主路徑或備份路徑不存在，都會導(dǎo)致確定性網(wǎng)絡(luò)流部署失敗。

算法1 復(fù)雜度由第11)行“更新BBij(mn)”決定，故算法復(fù)雜度為O(E2)。

6 實驗評估

6.1 環(huán)境配置

本文設(shè)計了一個離散模擬器用于評估確定性網(wǎng)絡(luò)共享保護(hù)模型的性能。模擬器使用python 開發(fā)。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)采用真實的歐洲網(wǎng)絡(luò)Cost239 和中國網(wǎng)絡(luò)China55[25]。Cost239 包含11 個節(jié)點和26 個鏈接。China55 包含55 個節(jié)點和104 個鏈接。每個鏈接的帶寬為100 Mbit/s，時隙長度為1 ms。Cost239 和China55 的拓?fù)浣Y(jié)構(gòu)如圖5 和圖6 所示。此外，在評估網(wǎng)絡(luò)節(jié)點數(shù)影響的實驗中，采用隨機生成拓?fù)浣Y(jié)構(gòu)。

圖5 歐洲網(wǎng)絡(luò)Cost239 拓?fù)?/p>

圖6 中國網(wǎng)絡(luò)China55 拓?fù)?/p>

確定性網(wǎng)絡(luò)流隨機產(chǎn)生，到達(dá)間隔符合參數(shù)為β的指數(shù)分布。每個確定性網(wǎng)絡(luò)流參數(shù)為七元組(id,source,destination,bandwidth,time,duration,delay)。確定性網(wǎng)絡(luò)流源點和目標(biāo)點在節(jié)點中隨機選擇，流帶寬需求為[20,40]Mbit/s，到達(dá)時間間隔服從參數(shù)為β的指數(shù)分布，持續(xù)時間服從β'=200的指數(shù)分布，時延需求為10 ms，模擬總時間為1 000 時間單位。

本文使用確定性網(wǎng)絡(luò)流接收率、網(wǎng)絡(luò)帶寬占用率和網(wǎng)絡(luò)流時延3 個評價指標(biāo)考察算法性能。確定性網(wǎng)絡(luò)流接收率為已接收網(wǎng)絡(luò)流與網(wǎng)絡(luò)流總數(shù)的比值，網(wǎng)絡(luò)帶寬占用率為各鏈接上已使用帶寬的平均值，單個網(wǎng)絡(luò)流的時延用跳數(shù)表示，網(wǎng)絡(luò)流時延為所有已接收網(wǎng)絡(luò)流時延的平均值。

在下面的實驗中，本文對比共享保護(hù)方案和非共享保護(hù)方案的性能，非共享保護(hù)方法的備份路由帶寬在備份路徑上直接疊加，分別觀察上述3 個評價指標(biāo)隨網(wǎng)絡(luò)流到達(dá)時間間隔、系統(tǒng)運行時間以及網(wǎng)絡(luò)節(jié)點數(shù)的變化。所有實驗結(jié)果為20 次實驗的平均值。

6.2 確定性網(wǎng)絡(luò)流到達(dá)時間間隔

到達(dá)時間間隔參數(shù)β反映了網(wǎng)絡(luò)的負(fù)載情況。β越小，網(wǎng)絡(luò)流到達(dá)越密集，網(wǎng)絡(luò)中共存的請求數(shù)越多，網(wǎng)絡(luò)負(fù)載越大。本文設(shè)置到達(dá)時間間隔參數(shù)β∈[5,20]。圖7～圖9 分別展示了Cost239 中網(wǎng)絡(luò)流接收率、帶寬占用率和網(wǎng)絡(luò)流時延隨到達(dá)時間間隔變化的結(jié)果。針對Cost239，本文定義β∈[5,10]為網(wǎng)絡(luò)高負(fù)載區(qū)，β∈[10,15]為網(wǎng)絡(luò)中負(fù)載區(qū)，β∈[15,20]為網(wǎng)絡(luò)低負(fù)載區(qū)。值得注意的是，上述負(fù)載區(qū)的定義不僅與β相關(guān)，也與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相關(guān)。

由圖7 可知，隨著網(wǎng)絡(luò)請求到達(dá)間隔的增加，由于網(wǎng)絡(luò)平均負(fù)載減少，確定性網(wǎng)絡(luò)流的接收率在逐步上升。通過比較共享保護(hù)算法和非共享保護(hù)算法的曲線可以看到，共享保護(hù)算法在確定性網(wǎng)絡(luò)流接收率方面比非共享保護(hù)算法普遍高10～20 個百分點。共享保護(hù)算法在提升確定性網(wǎng)絡(luò)流接收率方面作用明顯。

圖7 Cost239 接收率隨到達(dá)間隔的變化

圖8 中，在高負(fù)載區(qū)，共享保護(hù)方法的帶寬占用率比非共享保護(hù)方法高，共享保護(hù)方法利用較高的帶寬占用率實現(xiàn)了較高的請求接收率，因此資源利用率更高。在中負(fù)載區(qū)，共享保護(hù)方法和非共享保護(hù)方法的帶寬占用率相似。在低負(fù)載區(qū)，請求接收率在90%以上，共享保護(hù)方法的帶寬占用率低于非共享保護(hù)方法，共享保護(hù)仍有富余的帶寬用于接受更多請求，因此資源利用率較高。綜上所述，共享保護(hù)算法可以提升網(wǎng)絡(luò)帶寬的利用率。

圖8 Cost239 帶寬占用率隨到達(dá)間隔的變化

圖9 中，在高負(fù)載區(qū)，非共享保護(hù)主路由的平均時延明顯小于共享保護(hù)主路由。這個現(xiàn)象產(chǎn)生的原因是共享保護(hù)方法接收了更多較長的網(wǎng)絡(luò)流請求，使平均時延升高；而非共享保護(hù)方法由于資源不足，拒絕了較長的網(wǎng)絡(luò)流請求，使平均時延降低。隨著網(wǎng)絡(luò)負(fù)載變小，接收率升高，上述差異減小，2 種方法的主路由趨于相等。在低負(fù)載區(qū)，共享保護(hù)方法對主路由時延幾乎沒有影響。

圖9 Cost239 時延隨到達(dá)間隔的變化

與此同時，可以觀察到，共享保護(hù)備份路由時延始終小于非共享保護(hù)備份路由時延，這說明共享保護(hù)方法對于縮短備份路由的時延效果顯著。

6.3 系統(tǒng)運行時間

本節(jié)固定β=14，選取China55 網(wǎng)絡(luò)，比較3 個評價指標(biāo)隨運行時間的變化。此實驗反映了網(wǎng)絡(luò)從啟動到逐漸穩(wěn)定的過程。

圖10 展示了網(wǎng)絡(luò)流接收率隨時間的變化。從圖10 可以看到，在0～200 時間單位，確定性網(wǎng)絡(luò)流在網(wǎng)絡(luò)中處于建立階段，共享模型和非共享模型的請求接收率差別較小。隨著時間的推移，網(wǎng)絡(luò)中的帶寬資源趨于飽和，共享模型的接收率開始高于非共享模型，且這種差距逐漸拉大。在800 時間單位之后，兩者的接收率趨于穩(wěn)定。

圖10 China55 接收率隨系統(tǒng)運行時間的變化

圖11 為帶寬占用率隨系統(tǒng)運行時間的變化。從圖11 可以看到，由于網(wǎng)絡(luò)中不斷有新的網(wǎng)絡(luò)流進(jìn)入和舊的網(wǎng)絡(luò)流離開，在800 時間單位后，帶寬占用率圍繞0.3 呈波動穩(wěn)定狀態(tài)。同時，由于網(wǎng)絡(luò)處于中負(fù)載區(qū)，共享保護(hù)和非共享保護(hù)的帶寬占用率始終相似，差距很小。

圖11 China55 帶寬占用率隨系統(tǒng)運行時間的變化

圖12 展示了網(wǎng)絡(luò)流時延隨時間的變化。同圖10相似，隨著時間的推移，4 個時延的值逐漸穩(wěn)定。其中共享保護(hù)主路由時延大于非共享保護(hù)主路由時延，共享保護(hù)備份路由時延小于非共享保護(hù)備份路由時延。此現(xiàn)象與圖9 的中負(fù)載區(qū)現(xiàn)象一致。

圖12 China55 時延隨系統(tǒng)運行時間的變化

綜上所述，隨著系統(tǒng)運行時間的變化，2 種方法的各評價指標(biāo)在China55 網(wǎng)絡(luò)中逐漸穩(wěn)定，且最終結(jié)果與Cost239 一致。

6.4 網(wǎng)絡(luò)節(jié)點數(shù)

在這個實驗中，本文關(guān)心共享保護(hù)模型在隨機生成的網(wǎng)絡(luò)中的效果。本節(jié)固定β=16，采用隨機生成的拓?fù)浣Y(jié)構(gòu)，節(jié)點數(shù)量在20～50 內(nèi)變化。實驗結(jié)果如圖13～圖15 所示。

由圖13 可知，網(wǎng)絡(luò)接收率普遍大于90%，網(wǎng)絡(luò)處于低負(fù)載區(qū)，且隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加，網(wǎng)絡(luò)負(fù)載降低，請求的接收率升高。在此種條件下，圖14 印證了前述結(jié)論，即共享保護(hù)帶寬占用率低于非共享保護(hù)。

圖13 隨機拓?fù)浣邮章孰S節(jié)點數(shù)的變化

圖14 隨機拓?fù)鋷捳加寐孰S節(jié)點數(shù)的變化

從圖15 可以看出，當(dāng)網(wǎng)絡(luò)處于低負(fù)載區(qū)時，共享保護(hù)主路由和非共享保護(hù)主路由的時延幾乎一致，即2 種方法都能保證主路由的時延。因此，共享保護(hù)對主路由的影響很小。時延區(qū)別較大的是備份路由。共享保護(hù)方法的備份路由時延要明顯低于非共享保護(hù)方法的備份路由時延。因此，共享保護(hù)策略在保證備份路徑的時延上優(yōu)勢明顯。產(chǎn)生此現(xiàn)象的原因是非共享保護(hù)方法的資源較緊張，必須采用更長的備份路徑，導(dǎo)致備份路徑時延增大。從這個角度也可以看出，共享保護(hù)策略對網(wǎng)絡(luò)資源的利用率較高。

圖15 隨機拓?fù)鋾r延隨節(jié)點數(shù)的變化

7 結(jié)束語

針對確定性網(wǎng)絡(luò)的部署實現(xiàn)問題，本文提出了基于SRv6 的確定性網(wǎng)絡(luò)服務(wù)保護(hù)架構(gòu)，利用SRv6的可編程性簡化了確定性網(wǎng)絡(luò)的部署實現(xiàn)。針對確定性網(wǎng)絡(luò)服務(wù)保護(hù)問題，本文提出了面向服務(wù)的路由保護(hù)方案。通過服務(wù)區(qū)分，本文對不同的確定性網(wǎng)絡(luò)服務(wù)采取不同的保護(hù)策略?；谠摲桨?，對基于帶寬資源共享的保護(hù)系統(tǒng)進(jìn)行了建模，提出了啟發(fā)式的共享保護(hù)路徑選擇算法，優(yōu)化了網(wǎng)絡(luò)帶寬的利用率。實驗表明，相比于非共享保護(hù)算法，共享保護(hù)算法在網(wǎng)絡(luò)流接收率、帶寬占用率和網(wǎng)絡(luò)流時延上具有明顯優(yōu)勢。