李碩朋，方娟，陳肯

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

1 引言

近年來，5G、云計(jì)算、物聯(lián)網(wǎng)、自動(dòng)駕駛等行業(yè)的快速發(fā)展給未來網(wǎng)絡(luò)提出了新的挑戰(zhàn)。行業(yè)應(yīng)用的新需求催生了諸多網(wǎng)絡(luò)新技術(shù)，也推動(dòng)了未來網(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ù)可以在高帶寬、高可靠性低時(shí)延、高安全性、萬物互聯(lián)等方面賦能未來網(wǎng)絡(luò)。

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

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

三層確定性網(wǎng)絡(luò)[6]采用典型的軟件定義網(wǎng)絡(luò)（SDN,software defined network）架構(gòu)，將控制平面與轉(zhuǎn)發(fā)平面分離，通過對(duì)三層網(wǎng)絡(luò)設(shè)備的集中管理與配置，實(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]作為實(shí)現(xiàn)SDN 的新手段，受到越來越多的關(guān)注。分段路由作為一種源路由技術(shù)，簡(jiǎn)化了協(xié)議，在源路由器對(duì)數(shù)據(jù)報(bào)文進(jìn)行“編碼”，在報(bào)頭中插入有序的列表，用于指示報(bào)文的轉(zhuǎn)發(fā)路徑。分段路由相比傳統(tǒng)的資源預(yù)留和分布式協(xié)議降低了控制的冗余性，操作簡(jiǎn)單，擴(kuò)展性好，具備強(qiáng)大的可編程能力，被視為實(shí)現(xiàn)SDN2.0 的關(guān)鍵技術(shù)。

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

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

本文關(guān)注基于分段路由的確定性網(wǎng)絡(luò)實(shí)現(xiàn)模式，在SRv6 確定性網(wǎng)絡(luò)的條件下，重點(diǎn)討論服務(wù)保護(hù)機(jī)制的策略與算法實(shí)現(xiàn)。本文貢獻(xiàn)有以下3個(gè)方面：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)用平面通常是一個(gè)帶有特定服務(wù)或應(yīng)用請(qǐng)求的用戶，并通過北向接口和控制平面溝通應(yīng)用請(qǐng)求。控制平面接收應(yīng)用平面的請(qǐng)求，利用自身的控制功能，例如路徑計(jì)算單元（PCE,path computation element），完成路徑計(jì)算、網(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)用平面的用戶請(qǐng)求被抽象為確定性網(wǎng)絡(luò)的流和服務(wù)模型。RFC 9016[9]定義了確定性網(wǎng)絡(luò)服務(wù)的三層模型參數(shù)：服務(wù)參數(shù)、流參數(shù)和流-應(yīng)用參數(shù)。一個(gè)確定性網(wǎng)絡(luò)服務(wù)可以包含一個(gè)或多個(gè)確定性網(wǎng)絡(luò)流，一個(gè)確定性網(wǎng)絡(luò)流可以包含一個(gè)或多個(gè)確定性網(wǎng)絡(luò)流-應(yīng)用。服務(wù)參數(shù)包含服務(wù)的類型、特征、連接性、狀態(tài)等。流參數(shù)除了包含服務(wù)的基本信息外，還定義了流的部署方式（IP、MPLS）、流量特征（周期、周期內(nèi)包數(shù)量和負(fù)載）、流優(yōu)先級(jí)、流帶寬時(shí)延需求等。流-應(yīng)用參數(shù)與流參數(shù)類似。

確定性網(wǎng)絡(luò)控制平面[10]統(tǒng)一了網(wǎng)絡(luò)的控制層和管理層?？刂茖又С謩?dòng)態(tài)創(chuàng)建、修改和刪除確定性網(wǎng)絡(luò)流，支持流的聚合和反聚合，支持通過應(yīng)用接口進(jìn)行流的實(shí)例化，支持基于時(shí)間同步的隊(duì)列控制，具備發(fā)布節(jié)點(diǎn)和鏈接資源的能力，能夠處理確定性網(wǎng)絡(luò)域中的大規(guī)模確定性網(wǎng)絡(luò)流。管理平面監(jiān)測(cè)確定性網(wǎng)絡(luò)流的性能，支持流的完整性和連接性檢測(cè)，保證確定性網(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é)議的頭信息實(shí)現(xiàn)確定性網(wǎng)絡(luò)流的標(biāo)記和服務(wù)傳遞。RFC 8964[13]定義了利用偽線（PW,pseudowire）封裝和MPLS流量工程（MPLS-TE）在MPLS 網(wǎng)絡(luò)上實(shí)現(xiàn)確定性網(wǎng)絡(luò)。

基于MPLS 的確定性網(wǎng)絡(luò)數(shù)據(jù)平面包含d-CW（DetNet control word）、S-Label 和L-Label。d-CW表示包的序號(hào)，S-Label 用于確定性網(wǎng)絡(luò)服務(wù)身份識(shí)別，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 上實(shí)現(xiàn)。源節(jié)點(diǎn)利用分段列表（SL,segment list）表示完整的轉(zhuǎn)發(fā)路徑。分段路由在流量工程中有著重要的應(yīng)用[16-19]。

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

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

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

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

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

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ò)控制平面為一個(gè)SDN 控制器，負(fù)責(zé)收集網(wǎng)絡(luò)狀態(tài)，計(jì)算路徑，并下發(fā)指令。

數(shù)據(jù)平面二層（L2）采用TSN，三層（L3）采用SRv6。分段路由頭（SRH,segment routing header）用于實(shí)現(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 通過每個(gè)SL 提供基于源路由的顯性路徑轉(zhuǎn)發(fā)。

數(shù)據(jù)平面設(shè)備由終端設(shè)備（CE,customer equipment）、運(yùn)營(yíng)商邊緣設(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é)果，將整個(gè)路徑通過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é)點(diǎn)或鏈接發(fā)生故障時(shí)，保障網(wǎng)絡(luò)的不中斷和網(wǎng)絡(luò)流的低時(shí)延。

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

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

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

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

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

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

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

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

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

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

3.4 路徑保護(hù)策略

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

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

圖3 給出了路徑保護(hù)的示例。假設(shè)確定性網(wǎng)絡(luò)域由5 個(gè)支持SRv6 的路由器組成，網(wǎng)絡(luò)中有2 個(gè)確定性網(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é)點(diǎn)的故障。例如，若中繼設(shè)備R2出現(xiàn)故障，B1可確保網(wǎng)絡(luò)流不受影響。

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

3.5 帶寬資源共享

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，CT 表示時(shí)隙長(zhǎng)度。

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

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

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

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

5 路徑選擇算法

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

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

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

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

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

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

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

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

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

6.1 環(huán)境配置

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

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

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

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

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

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

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

到達(dá)時(shí)間間隔參數(shù)β反映了網(wǎng)絡(luò)的負(fù)載情況。β越小，網(wǎng)絡(luò)流到達(dá)越密集，網(wǎng)絡(luò)中共存的請(qǐng)求數(shù)越多，網(wǎng)絡(luò)負(fù)載越大。本文設(shè)置到達(dá)時(shí)間間隔參數(shù)β∈[5,20]。圖7～圖9 分別展示了Cost239 中網(wǎng)絡(luò)流接收率、帶寬占用率和網(wǎng)絡(luò)流時(shí)延隨到達(dá)時(shí)間間隔變化的結(jié)果。針對(duì)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ò)請(qǐng)求到達(dá)間隔的增加，由于網(wǎng)絡(luò)平均負(fù)載減少，確定性網(wǎng)絡(luò)流的接收率在逐步上升。通過比較共享保護(hù)算法和非共享保護(hù)算法的曲線可以看到，共享保護(hù)算法在確定性網(wǎng)絡(luò)流接收率方面比非共享保護(hù)算法普遍高10～20 個(gè)百分點(diǎn)。共享保護(hù)算法在提升確定性網(wǎng)絡(luò)流接收率方面作用明顯。

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

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

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

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

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

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

6.3 系統(tǒng)運(yùn)行時(shí)間

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

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

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

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

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

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

圖12 China55 時(shí)延隨系統(tǒng)運(yùn)行時(shí)間的變化

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

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

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

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

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

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

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

圖15 隨機(jī)拓?fù)鋾r(shí)延隨節(jié)點(diǎn)數(shù)的變化

7 結(jié)束語

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