于思凡，何鋒，熊華鋼

北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100083

當(dāng)前交換式網(wǎng)絡(luò)利用空分交換結(jié)構(gòu)，能夠在一個(gè)網(wǎng)段同時(shí)進(jìn)行多個(gè)消息并發(fā)處理，提高了整網(wǎng)吞吐量，能夠滿足新一代航空電子綜合技術(shù)對(duì)通信網(wǎng)絡(luò)的需求。應(yīng)用于軍用飛機(jī)F-35的光纖通道(Fibre Channel，F(xiàn)C)和民用飛機(jī)空客A380的航空電子全雙工交換式以太網(wǎng)(Avionics Full Duplex Switched Ethernet，AFDX)都屬于典型交換式網(wǎng)絡(luò)。優(yōu)先級(jí)作為一種調(diào)度機(jī)制廣泛應(yīng)用于交換式網(wǎng)絡(luò)的實(shí)時(shí)通信調(diào)度中，用于滿足不同重要程度的消息對(duì)實(shí)時(shí)性能的要求。為了保障消息的通信訴求，需要對(duì)交換式網(wǎng)絡(luò)中不同優(yōu)先級(jí)的消息進(jìn)行實(shí)時(shí)性能評(píng)估。在交換式網(wǎng)絡(luò)設(shè)計(jì)初期，網(wǎng)絡(luò)具體參數(shù)未知時(shí)，同樣有對(duì)不同優(yōu)先級(jí)占比情況下的整網(wǎng)實(shí)時(shí)性能的預(yù)估需求，目的在于形成反饋機(jī)制，以指導(dǎo)機(jī)載網(wǎng)絡(luò)的具體設(shè)計(jì)。

解析計(jì)算是一種對(duì)網(wǎng)絡(luò)進(jìn)行數(shù)學(xué)建模、計(jì)算得到端到端延遲上界的實(shí)時(shí)性能分析方法。消息端到端的最大延遲刻畫(huà)了消息最難調(diào)度場(chǎng)景，通過(guò)解析計(jì)算獲得的消息延遲上界與消息真實(shí)最壞延遲之間的差異性刻畫(huà)了不同方法的計(jì)算悲觀性。典型的解析計(jì)算方法包括網(wǎng)絡(luò)演算、軌跡法、整體法等。其中網(wǎng)絡(luò)演算基于最小加代數(shù)理論，以流量曲線和服務(wù)曲線為建模目標(biāo)，通過(guò)分析流經(jīng)節(jié)點(diǎn)的數(shù)據(jù)流在節(jié)點(diǎn)處積壓的情況，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的服務(wù)性能分析。軌跡法根據(jù)數(shù)據(jù)流既定路徑軌跡，構(gòu)造數(shù)據(jù)幀沿其傳輸路徑上的最壞情況，從而實(shí)現(xiàn)端到端延遲分析。相比于網(wǎng)絡(luò)演算，軌跡法不是針對(duì)每個(gè)節(jié)點(diǎn)的最壞情況，部分克服了網(wǎng)絡(luò)演算中利用輸出曲線突發(fā)度增大模擬數(shù)據(jù)幀到達(dá)存在的不確定性帶來(lái)的悲觀性。整體法通過(guò)對(duì)數(shù)據(jù)幀到達(dá)時(shí)延抖動(dòng)的迭代計(jì)算實(shí)現(xiàn)數(shù)據(jù)幀在輸出節(jié)點(diǎn)的最壞延遲分析，并通過(guò)對(duì)路徑上各個(gè)節(jié)點(diǎn)的最壞延遲累加得到端到端延遲上界。在數(shù)據(jù)傳輸時(shí)，每個(gè)節(jié)點(diǎn)的最后延遲基本上不會(huì)達(dá)到，導(dǎo)致了整體法的悲觀性。

網(wǎng)絡(luò)演算易于理解與實(shí)現(xiàn)，已成為使用最普遍的解析計(jì)算方法，并發(fā)展出分組網(wǎng)絡(luò)演算、偏置網(wǎng)絡(luò)演算、實(shí)時(shí)網(wǎng)絡(luò)演算、共軛網(wǎng)絡(luò)演算等其他形式的變體。但網(wǎng)絡(luò)演算方法依賴于網(wǎng)絡(luò)拓?fù)浜驮敿?xì)配置參數(shù)，無(wú)法在設(shè)計(jì)初期對(duì)網(wǎng)絡(luò)實(shí)時(shí)性刻畫(huà)，由此發(fā)展出泛化網(wǎng)絡(luò)演算。與已有網(wǎng)絡(luò)演算方法對(duì)具體網(wǎng)絡(luò)實(shí)時(shí)性評(píng)價(jià)不同，泛化網(wǎng)絡(luò)演算無(wú)需組網(wǎng)拓?fù)浜土髁烤唧w配置參數(shù)，利用抽象出的組網(wǎng)特征參數(shù)對(duì)網(wǎng)絡(luò)實(shí)時(shí)性能進(jìn)行預(yù)估，進(jìn)而形成反饋機(jī)制，用于指導(dǎo)網(wǎng)絡(luò)具體設(shè)計(jì)。即使在未知網(wǎng)絡(luò)拓?fù)浜土髁烤唧w配置參數(shù)的情況下，泛化網(wǎng)絡(luò)演算的算法有效性超過(guò)38%，具備網(wǎng)絡(luò)實(shí)時(shí)性預(yù)估的能力。但目前泛化網(wǎng)絡(luò)演算缺乏對(duì)不同優(yōu)先級(jí)數(shù)據(jù)流實(shí)時(shí)性評(píng)價(jià)的能力。

為了在未知網(wǎng)絡(luò)拓?fù)渑c消息詳細(xì)配置參數(shù)的情況下，對(duì)采用優(yōu)先級(jí)調(diào)度策略的交換式網(wǎng)絡(luò)進(jìn)行實(shí)時(shí)性能預(yù)估，本文提出優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算，研究貢獻(xiàn)在于：抽象出網(wǎng)絡(luò)中端口發(fā)送高、低優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率兩個(gè)特征參數(shù)分別對(duì)網(wǎng)絡(luò)中高、低優(yōu)先級(jí)數(shù)據(jù)流的分布進(jìn)行抽象，進(jìn)而對(duì)高、低優(yōu)先級(jí)占比進(jìn)行刻畫(huà)與預(yù)估；基于抽象出的優(yōu)先級(jí)調(diào)度策略交換式網(wǎng)絡(luò)的組網(wǎng)特征參數(shù)，分別對(duì)高、低優(yōu)先級(jí)數(shù)據(jù)流的服務(wù)曲線進(jìn)行泛化，并分別得到高、低優(yōu)先級(jí)數(shù)據(jù)流的端到端延遲上界；對(duì)高、低優(yōu)先級(jí)延遲確界變化進(jìn)行分析與對(duì)比，給出優(yōu)先級(jí)占比推薦方案，用于指導(dǎo)優(yōu)先級(jí)調(diào)度策略交換式航電網(wǎng)絡(luò)的設(shè)計(jì)。

1 泛化網(wǎng)絡(luò)演算

泛化網(wǎng)絡(luò)演算無(wú)需組網(wǎng)拓?fù)浜土髁烤唧w配置參數(shù)，利用抽象出的組網(wǎng)特征參數(shù)對(duì)網(wǎng)絡(luò)實(shí)時(shí)性能進(jìn)行預(yù)估。本節(jié)對(duì)交換式網(wǎng)絡(luò)和最壞延遲分析進(jìn)行總結(jié)，并對(duì)網(wǎng)絡(luò)演算和泛化網(wǎng)絡(luò)演算進(jìn)行介紹。

1.1 交換式網(wǎng)絡(luò)

為了滿足新一代航空電子系統(tǒng)對(duì)綜合化互連在帶寬、實(shí)時(shí)性、可靠性等方面更高的性能要求，機(jī)載網(wǎng)絡(luò)逐步發(fā)展為具有靈活性的交換式拓?fù)浣Y(jié)構(gòu)。交換式網(wǎng)絡(luò)中利用空分交換結(jié)構(gòu)，計(jì)算節(jié)點(diǎn)之間存在多條通信鏈路，節(jié)點(diǎn)之間的通信可以并發(fā)進(jìn)行，大大提高了整網(wǎng)通信吞吐量。光纖通道和航空電子全雙工交換式以太網(wǎng)作為典型交換式網(wǎng)絡(luò)被新型機(jī)載互連系統(tǒng)所采用。由8個(gè)交換機(jī)和12個(gè)端系統(tǒng)組成的交換式網(wǎng)絡(luò)如圖1所示。

圖1 交換式網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Switch-based network structure

考慮到機(jī)載網(wǎng)絡(luò)實(shí)時(shí)性傳輸需求，應(yīng)用于機(jī)載環(huán)境的交換式網(wǎng)絡(luò)需要通過(guò)流量控制機(jī)制保障網(wǎng)絡(luò)的實(shí)時(shí)性。例如AFDX網(wǎng)絡(luò)的實(shí)時(shí)性主要體現(xiàn)在基于虛擬鏈路的調(diào)度、尋址、路由等過(guò)程中。AFDX網(wǎng)絡(luò)中虛擬鏈路按照給定的帶寬分配間隔(Bandwidth Allocation Interval，BAG)進(jìn)行整形，使得每條虛擬鏈路都有規(guī)定的最大帶寬，并提供了其端到端延遲上界可計(jì)算的基礎(chǔ)，從而保障了數(shù)據(jù)流的實(shí)時(shí)性。AFDX網(wǎng)絡(luò)中虛擬鏈路的流量整形過(guò)程如圖2所示。

圖2 AFDX網(wǎng)絡(luò)虛擬鏈路流量整形機(jī)制Fig.2 Traffic shaping mechanism of virtual links in AFDX

1.2 最壞延遲分析

交換式網(wǎng)絡(luò)的實(shí)時(shí)性指網(wǎng)絡(luò)中通信任務(wù)的傳輸必須在指定的時(shí)間內(nèi)完成，即消息的端到端延遲必須不能大于規(guī)定的截止期限。消息的端到端延遲為消息從源端系統(tǒng)到目的端系統(tǒng)傳輸時(shí)間的總和。消息的端到端延遲主要分為3個(gè)部分：物理鏈路上的傳輸延遲，消息幀從交換機(jī)輸入端口發(fā)送到輸出端口的時(shí)間(不包含消息在輸出端口排隊(duì)的時(shí)間)，消息在端系統(tǒng)或交換機(jī)輸出端口等待排隊(duì)調(diào)度的時(shí)間。

物理鏈路上的傳輸延遲取決于幀的傳輸時(shí)間，即消息幀長(zhǎng)與物理鏈路傳輸帶寬的比值。消息經(jīng)過(guò)多條物理鏈路時(shí)，物理鏈路上的傳輸總延遲是單個(gè)幀傳輸延遲與經(jīng)過(guò)物理鏈路數(shù)量的乘積。消息幀從交換機(jī)輸入端口發(fā)送到輸出端口的時(shí)間稱為交換機(jī)固有技術(shù)時(shí)延，具有確定的上界。當(dāng)消息經(jīng)過(guò)多個(gè)交換機(jī)時(shí)，該部分傳輸延遲是交換機(jī)固有技術(shù)時(shí)延與經(jīng)過(guò)交換機(jī)個(gè)數(shù)的乘積。消息在端系統(tǒng)或交換機(jī)輸出端口等待排隊(duì)調(diào)度的時(shí)間取決于消息輸出排隊(duì)的過(guò)程，具有高度不確定性，是本文研究的重點(diǎn)。

1.3 泛化網(wǎng)絡(luò)演算

網(wǎng)絡(luò)演算是一種基于最小加代數(shù)理論的端到端延遲上界分析方法。網(wǎng)絡(luò)演算中定義了到達(dá)曲線和服務(wù)曲線，分別表示網(wǎng)絡(luò)節(jié)點(diǎn)處到達(dá)數(shù)據(jù)流的上包絡(luò)和網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)具有不同服務(wù)質(zhì)量需求的數(shù)據(jù)流的最小服務(wù)能力。到達(dá)曲線與服務(wù)曲線之間的最大水平距離表示網(wǎng)絡(luò)節(jié)點(diǎn)處數(shù)據(jù)流的最壞時(shí)間延遲，最大垂直距離表示網(wǎng)絡(luò)節(jié)點(diǎn)處數(shù)據(jù)流的最大數(shù)據(jù)積壓。對(duì)數(shù)據(jù)流傳輸路徑上各節(jié)點(diǎn)處的最壞延遲求和，得到端到端延遲上界。

網(wǎng)絡(luò)演算依據(jù)詳細(xì)配置參數(shù)計(jì)算數(shù)據(jù)流延遲上界，但存在根據(jù)組網(wǎng)特征參數(shù)進(jìn)行實(shí)時(shí)性評(píng)價(jià)的需求，用于指導(dǎo)網(wǎng)絡(luò)設(shè)計(jì)。目前研究中存在對(duì)保證速率(Guaranteed Rate，GR)網(wǎng)絡(luò)通過(guò)網(wǎng)絡(luò)特征計(jì)算確定性端到端延遲上界的方法。該方法通過(guò)流量的最大跳數(shù)、帶寬利用率、突發(fā)度等得到端到端延遲上界。對(duì)于AFDX和FC等交換式網(wǎng)絡(luò)，由于虛擬鏈路的流整形或其他整形過(guò)程，不能保證每個(gè)流在輸出端口按照給定的速率服務(wù)，這種方法并不適用，由此文獻(xiàn)[20]提出泛化網(wǎng)絡(luò)演算。與已有網(wǎng)絡(luò)演算方法對(duì)具體網(wǎng)絡(luò)實(shí)時(shí)性評(píng)價(jià)不同，泛化網(wǎng)絡(luò)演算在未知組網(wǎng)拓?fù)浜土髁吭敿?xì)配置參數(shù)的情況下，依據(jù)網(wǎng)絡(luò)規(guī)模、帶寬利用率、數(shù)據(jù)比特流速率等組網(wǎng)特征參數(shù)，分別得到基本延遲上界和考慮分組的延遲上界，如圖3所示。相比于網(wǎng)絡(luò)演算，即使在數(shù)據(jù)幀長(zhǎng)顯著變化的情況下，2種延遲上界的有效性均超過(guò)38%，具備對(duì)網(wǎng)絡(luò)實(shí)時(shí)性預(yù)估的能力，得到的結(jié)果可以指導(dǎo)網(wǎng)絡(luò)設(shè)計(jì)。

圖3 泛化網(wǎng)絡(luò)演算Fig.3 Generalized network calculus

2 優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算

優(yōu)先級(jí)作為一種調(diào)度機(jī)制廣泛應(yīng)用于實(shí)時(shí)通信調(diào)度中，用于解決不同重要程度消息對(duì)實(shí)時(shí)傳輸?shù)男枨?。例如現(xiàn)有AFDX交換機(jī)支持高、低2級(jí)優(yōu)先級(jí)。目前泛化網(wǎng)絡(luò)演算缺乏對(duì)不同優(yōu)先級(jí)數(shù)據(jù)流實(shí)時(shí)性評(píng)價(jià)的能力。

為了實(shí)現(xiàn)優(yōu)先級(jí)驅(qū)動(dòng)的泛化性能分析，對(duì)采用優(yōu)先級(jí)調(diào)度策略的交換式網(wǎng)絡(luò)進(jìn)行實(shí)時(shí)性預(yù)估，首先分析優(yōu)先級(jí)調(diào)度機(jī)制，抽象出交換式網(wǎng)絡(luò)優(yōu)先級(jí)調(diào)度策略的特征參數(shù)，進(jìn)而基于特征參數(shù)對(duì)源節(jié)點(diǎn)和交換機(jī)端口處對(duì)高、低優(yōu)先級(jí)服務(wù)曲線進(jìn)行泛化，之后在突發(fā)度包絡(luò)函數(shù)的邊界約束下對(duì)高、低優(yōu)先級(jí)數(shù)據(jù)流在源節(jié)點(diǎn)和交換機(jī)處延遲的最壞情況進(jìn)行建模，得到延遲上界，累加得到端到端延遲上界。

2.1 優(yōu)先級(jí)調(diào)度機(jī)制

當(dāng)消息端到端延遲不滿足既定要求時(shí)，有以下3個(gè)解決方案：① 限制數(shù)據(jù)流的數(shù)量；② 增加額外的交換機(jī)或物理鏈路；③ 將數(shù)據(jù)流劃分為高、低優(yōu)先級(jí)，不滿足要求的消息采用高優(yōu)先級(jí)。由于應(yīng)用的限制一般不能減少數(shù)據(jù)流的數(shù)量，增加額外的交換機(jī)或物理鏈路會(huì)增加網(wǎng)絡(luò)成本，因此可以將數(shù)據(jù)流劃分為高、低優(yōu)先級(jí)以減少高優(yōu)先級(jí)數(shù)據(jù)流延遲上界。由此可以看出，優(yōu)先級(jí)調(diào)度機(jī)制在實(shí)時(shí)通信調(diào)度中廣泛應(yīng)用。

ARINC667 P7協(xié)議中規(guī)定的優(yōu)先級(jí)調(diào)度算法為基于靜態(tài)優(yōu)先級(jí)的非搶占式隊(duì)列調(diào)度(Static Priority Un-interrupt Scheduling, SPUS)。該算法規(guī)定：在數(shù)據(jù)流發(fā)送過(guò)程中，只要高優(yōu)先級(jí)隊(duì)列非空，高優(yōu)先級(jí)數(shù)據(jù)流優(yōu)先發(fā)送；但低優(yōu)先級(jí)數(shù)據(jù)流正在發(fā)送時(shí)，高優(yōu)先級(jí)數(shù)據(jù)流不能打斷正在傳輸?shù)牡蛢?yōu)先級(jí)數(shù)據(jù)流，必須等到發(fā)送完成后再進(jìn)行發(fā)送。基于靜態(tài)優(yōu)先級(jí)的非搶占式隊(duì)列調(diào)度如圖4所示。

圖4 基于靜態(tài)優(yōu)先級(jí)的非搶占式隊(duì)列調(diào)度Fig.4 Static priority un-interrupt scheduling

2.2 服務(wù)曲線模型

在基于靜態(tài)優(yōu)先級(jí)的非搶占式隊(duì)列調(diào)度策略中，高優(yōu)先級(jí)數(shù)據(jù)流的傳輸受限于交換機(jī)端口的輸出速率，同時(shí)高優(yōu)先級(jí)數(shù)據(jù)流不能打斷正在傳輸?shù)牡蛢?yōu)先級(jí)數(shù)據(jù)流。因此在確定性網(wǎng)絡(luò)演算中，端口port對(duì)高優(yōu)先級(jí)數(shù)據(jù)流的服務(wù)曲線()為

(1)

由于交換機(jī)端口優(yōu)先對(duì)高優(yōu)先級(jí)數(shù)據(jù)流服務(wù)，因此低優(yōu)先級(jí)數(shù)據(jù)流的傳輸受限于交換機(jī)端口的輸出速率和交換機(jī)端口對(duì)高優(yōu)先級(jí)數(shù)據(jù)流的服務(wù)。在確定性網(wǎng)絡(luò)演算中，端口port對(duì)低優(yōu)先級(jí)數(shù)據(jù)流的服務(wù)曲線()為

(2)

式中：為高優(yōu)先級(jí)數(shù)據(jù)流集合；flow為經(jīng)過(guò)端口port的任意數(shù)據(jù)流；為數(shù)據(jù)流flow的比特流速率；為數(shù)據(jù)流flow的突發(fā)度。

2.3 交換式網(wǎng)絡(luò)特征參數(shù)

在交換式網(wǎng)絡(luò)設(shè)計(jì)初期，只能依賴組網(wǎng)特征參數(shù)對(duì)網(wǎng)絡(luò)實(shí)時(shí)性評(píng)價(jià)。本文抽象出物理鏈路速率,網(wǎng)絡(luò)中數(shù)據(jù)幀長(zhǎng)度上界,網(wǎng)絡(luò)中數(shù)據(jù)流的比特速率,網(wǎng)絡(luò)中端口發(fā)送高、低優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率、網(wǎng)絡(luò)中數(shù)據(jù)流經(jīng)過(guò)交換機(jī)跳數(shù)的最大值6個(gè)特征參數(shù)對(duì)網(wǎng)絡(luò)進(jìn)行刻畫(huà)。參數(shù)具體含義如下：

：物理鏈路速率?？梢圆皇б话阈缘丶僭O(shè)網(wǎng)絡(luò)中物理鏈路速率一致，例如網(wǎng)絡(luò)中物理鏈路速率均為=100 Mbit/s。物理鏈路速率刻畫(huà)網(wǎng)絡(luò)中鏈路傳輸情況。

：網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率。假設(shè)網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率相等，均為。網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率刻畫(huà)網(wǎng)絡(luò)中流量規(guī)模。

：網(wǎng)絡(luò)中端口發(fā)送低優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率，即flow。其中：port,L為輸出端口port發(fā)送低優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率。同樣利用實(shí)現(xiàn)網(wǎng)絡(luò)初期設(shè)計(jì)者對(duì)低優(yōu)先級(jí)流量占比的刻畫(huà)和預(yù)估。

2.4 高優(yōu)先級(jí)數(shù)據(jù)流延遲上界分析

基于高低優(yōu)先級(jí)流量占比的預(yù)估，可以在泛化網(wǎng)絡(luò)演算角度下進(jìn)行不同優(yōu)先級(jí)流量的延遲分析。關(guān)鍵在于如何實(shí)施突發(fā)度包絡(luò)函數(shù)約束下的不同優(yōu)先級(jí)流量的約束。相對(duì)來(lái)說(shuō)，高優(yōu)先級(jí)流量的約束可以考慮低優(yōu)先級(jí)的最大幀長(zhǎng)的影響，但是低優(yōu)先級(jí)的約束就需要將高優(yōu)先級(jí)占比的整體情況進(jìn)行考慮。

2.4.1 高優(yōu)先級(jí)數(shù)據(jù)流在源節(jié)點(diǎn)處延遲

(3)

(4)

式中：port為源節(jié)點(diǎn)的輸出端口；max,為數(shù)據(jù)流flow中數(shù)據(jù)幀的最大長(zhǎng)度。

(5)

(6)

(7)

2.4.2 高優(yōu)先級(jí)數(shù)據(jù)流在交換機(jī)處延遲

在交換機(jī)輸出端口，高優(yōu)先級(jí)數(shù)據(jù)流同樣受限于端口的服務(wù)速率和對(duì)正在傳輸?shù)牡蛢?yōu)先級(jí)數(shù)據(jù)幀的服務(wù)。因此在交換機(jī)輸出端口，高優(yōu)先級(jí)數(shù)據(jù)流的服務(wù)曲線()仍為

(8)

(9)

式中：port為第1個(gè)交換機(jī)輸出端口。

(10)

(11)

(12)

為了得到統(tǒng)一的高優(yōu)先級(jí)數(shù)據(jù)流延遲上界，對(duì)網(wǎng)絡(luò)中高優(yōu)先級(jí)數(shù)據(jù)流包絡(luò)函數(shù)的上界進(jìn)行定義。定義網(wǎng)絡(luò)中高優(yōu)先級(jí)數(shù)據(jù)流在第hop個(gè)節(jié)點(diǎn)處突發(fā)度的包絡(luò)函數(shù)的上界為(hop)，則可以得出

(13)

(14)

(15)

(16)

(17)

(18)

根據(jù)計(jì)算得到的高優(yōu)先級(jí)數(shù)據(jù)流在第個(gè)節(jié)點(diǎn)處的突發(fā)度表達(dá)式可以得到

(19)

由此可以解出(hop)表達(dá)式為

(20)

2.4.3 高優(yōu)先級(jí)數(shù)據(jù)流端到端延遲

(21)

2.5 低優(yōu)先級(jí)數(shù)據(jù)流延遲上界分析

對(duì)于低優(yōu)先級(jí)，消息的傳輸受高優(yōu)先級(jí)數(shù)據(jù)流的傳輸?shù)募s束。延遲上界分析的關(guān)鍵在于依據(jù)組網(wǎng)特征參數(shù)對(duì)低優(yōu)先級(jí)數(shù)據(jù)流在源節(jié)點(diǎn)、交換機(jī)處服務(wù)曲線進(jìn)行泛化，進(jìn)而通過(guò)泛化網(wǎng)絡(luò)演算理論得到低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界公式。

2.5.1 低優(yōu)先級(jí)數(shù)據(jù)流在源節(jié)點(diǎn)處泛化服務(wù)曲線

(22)

2.5.2 低優(yōu)先級(jí)數(shù)據(jù)流在交換機(jī)處泛化服務(wù)曲線

(23)

2.5.3 低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲

(24)

其中的表達(dá)式為

(25)

低優(yōu)先級(jí)數(shù)據(jù)流突發(fā)度的包絡(luò)函數(shù)()的表達(dá)式為

()=

(26)

3 算法驗(yàn)證

依據(jù)優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算模型，以具備輸入流量漏桶整形的交換式網(wǎng)絡(luò)為例，對(duì)高、低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界隨帶寬利用率、比特流速率、網(wǎng)絡(luò)中數(shù)據(jù)流經(jīng)過(guò)交換機(jī)的最大跳數(shù)、高優(yōu)先級(jí)占比的變化進(jìn)行分析與對(duì)比，驗(yàn)證算法的正確性與合理性，并給出優(yōu)先級(jí)占比分配推薦方案。

3.1 高優(yōu)先級(jí)數(shù)據(jù)流延遲上界分析

選取交換式網(wǎng)絡(luò)的典型參數(shù)，假設(shè)物理鏈路的傳輸速率為100 Mbit/s，網(wǎng)絡(luò)中數(shù)據(jù)幀的最大長(zhǎng)度為1 000 Bytes。當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流經(jīng)過(guò)交換機(jī)的最大跳數(shù)為3時(shí)，高優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界如圖5所示?？梢钥闯?，當(dāng)網(wǎng)絡(luò)中端口發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率一定時(shí)，數(shù)據(jù)流的比特流速率越大，網(wǎng)絡(luò)中高優(yōu)先級(jí)數(shù)據(jù)流的數(shù)目越少，在交換機(jī)輸出端口排隊(duì)造成的延遲越小，端到端延遲上界越小。當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率一定時(shí)，端口發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率越大，網(wǎng)絡(luò)中高優(yōu)先級(jí)數(shù)據(jù)流的數(shù)目越多，在交換機(jī)輸出端口排隊(duì)造成的延遲越大，端到端延遲上界越大。

圖5 不同高優(yōu)先級(jí)數(shù)據(jù)流延遲上界μH隨ρ變化曲線Fig.5 Gurve of μH changing with ρ under different upper bound delays for high-priority streams

當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率為0.5 Mbit/s 時(shí)，高優(yōu)先級(jí)數(shù)據(jù)流延遲上界如圖6所示。可以看出，當(dāng)網(wǎng)絡(luò)中端口發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率相同時(shí)，高優(yōu)先級(jí)數(shù)據(jù)流經(jīng)過(guò)交換機(jī)的個(gè)數(shù)越多，端到端延遲上界越大，這與基本網(wǎng)絡(luò)演算的結(jié)論一致。

圖6 不同高優(yōu)先級(jí)數(shù)據(jù)流延遲上界μH隨h變化曲線Fig.6 Curve of μH changing with h under different upper bound delays for high-priority streams

3.2 低優(yōu)先級(jí)數(shù)據(jù)流延遲上界分析

假設(shè)物理鏈路傳輸速率為100 Mbit/s，網(wǎng)絡(luò)中數(shù)據(jù)幀的最大長(zhǎng)度為1 000 Bytes，網(wǎng)絡(luò)中端口發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率為15%。當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流經(jīng)過(guò)交換機(jī)的最大跳數(shù)為3時(shí)，低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界如圖7所示。與高優(yōu)先級(jí)數(shù)據(jù)流的分析相同，當(dāng)網(wǎng)絡(luò)中端口發(fā)送低優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率一定時(shí)，數(shù)據(jù)流比特流速率越大，低優(yōu)先級(jí)數(shù)據(jù)流的端到端延遲上界越小。當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率一定時(shí)，端口發(fā)送低優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率越大，低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界越大。

圖7 不同低優(yōu)先級(jí)數(shù)據(jù)流延遲上界μL隨ρ變化曲線Fig.7 Curve of μL changing wiht ρ under different upper bound delays for low-priority streams

當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流比特流速率為0.5 Mbit/s時(shí)，低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界如圖8所示。同理，低優(yōu)先級(jí)數(shù)據(jù)流經(jīng)過(guò)交換機(jī)的個(gè)數(shù)越多，端到端延遲上界越大，與基本網(wǎng)絡(luò)演算結(jié)論一致。

圖8 不同低優(yōu)先級(jí)數(shù)據(jù)流延遲μL隨、h變化曲線Fig.8 Curve of μL changing with h under different upper bound for low-priority streams

3.3 高、低與不區(qū)分優(yōu)先級(jí)數(shù)據(jù)流延遲上界對(duì)比

基于優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算模型，分析當(dāng)網(wǎng)絡(luò)中端口最大帶寬利用率之和一致時(shí)，高、低優(yōu)先級(jí)數(shù)據(jù)流延遲上界變化趨勢(shì)，能夠?qū)W(wǎng)絡(luò)設(shè)計(jì)中分配高、低優(yōu)先級(jí)數(shù)據(jù)流占比進(jìn)行指導(dǎo)。同時(shí)與泛化網(wǎng)絡(luò)演算得到的相同端口最大帶寬利用率，但不區(qū)分優(yōu)先級(jí)的延遲上界結(jié)果進(jìn)行對(duì)比，驗(yàn)證算法的正確性與合理性。

與空客A380網(wǎng)絡(luò)規(guī)模相似的網(wǎng)絡(luò)中端口發(fā)送數(shù)據(jù)流的帶寬利用率約為25%。設(shè)定網(wǎng)絡(luò)中端口處發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流最大帶寬利用率和低優(yōu)先級(jí)數(shù)據(jù)流最大帶寬利用率之和為定值0.25，即+=025，得出高、低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界隨網(wǎng)絡(luò)中端口處發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率、數(shù)據(jù)流的比特流速率變化曲線如圖9所示。

從圖9中可以看出，對(duì)于高優(yōu)先級(jí)數(shù)據(jù)流，網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率一定時(shí)，網(wǎng)絡(luò)中端口發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率越高，網(wǎng)絡(luò)中高優(yōu)先級(jí)數(shù)據(jù)流越多，在交換機(jī)端口處排隊(duì)造成的延遲越大，高優(yōu)先級(jí)數(shù)據(jù)流的端到端延遲上界越大。除正在傳輸?shù)牡蛢?yōu)先級(jí)數(shù)據(jù)幀外，低優(yōu)先級(jí)數(shù)據(jù)流的傳輸不對(duì)高優(yōu)先級(jí)數(shù)據(jù)流產(chǎn)生影響。

圖9 高優(yōu)先級(jí)、低優(yōu)先級(jí)和不區(qū)分優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界Fig.9 Upper bound on end-to-end delay of high priority, low priority and un-priority streams

對(duì)于低優(yōu)先級(jí)數(shù)據(jù)流，網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率一定時(shí)，低優(yōu)先級(jí)數(shù)據(jù)流的延遲上界隨著網(wǎng)絡(luò)中端口處發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率的增大先減小再增大。網(wǎng)絡(luò)中端口處發(fā)送高優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率增大導(dǎo)致高優(yōu)先級(jí)數(shù)據(jù)流對(duì)低優(yōu)先級(jí)數(shù)據(jù)流延遲影響增大。同時(shí)網(wǎng)絡(luò)中端口發(fā)送低優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率減小，導(dǎo)致網(wǎng)絡(luò)中低優(yōu)先級(jí)數(shù)據(jù)流數(shù)量減少，低優(yōu)先級(jí)數(shù)據(jù)流間排隊(duì)延遲減少。這2種影響相互平衡形成圖9所示結(jié)果，可以看出雖然比特流速率的不同會(huì)導(dǎo)致低優(yōu)先級(jí)延遲轉(zhuǎn)折點(diǎn)的稍許變化，但基本上圍繞在高優(yōu)先級(jí)流量占整個(gè)流量的40%左右。

因此，圖9所示的高、低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界曲線展示了網(wǎng)絡(luò)中高、低優(yōu)先級(jí)數(shù)據(jù)流的數(shù)量對(duì)延遲上界的影響。當(dāng)網(wǎng)絡(luò)中端口處發(fā)送高、低優(yōu)先級(jí)數(shù)據(jù)流最大帶寬利用率之和+及數(shù)據(jù)流的比特流速率一定時(shí)，可以選擇圖中圓點(diǎn)位置(相同數(shù)據(jù)流的比特流速率，低優(yōu)先級(jí)數(shù)據(jù)流延遲最小)處的高優(yōu)先級(jí)數(shù)據(jù)流最大帶寬利用率。在保證高優(yōu)先級(jí)數(shù)據(jù)流延遲上界的基礎(chǔ)上，可以最大程度降低低優(yōu)先級(jí)數(shù)據(jù)流延遲上界。在與空客A380網(wǎng)絡(luò)規(guī)模相似的機(jī)載網(wǎng)絡(luò)中，選擇高優(yōu)先級(jí)數(shù)據(jù)流占比40%左右，低優(yōu)先級(jí)數(shù)據(jù)流占比60%左右，以實(shí)現(xiàn)高低優(yōu)先級(jí)流量端到端傳輸延遲的最佳平衡。因此基于優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算，給出了優(yōu)先級(jí)占比推薦方案。

對(duì)于不區(qū)分優(yōu)先級(jí)網(wǎng)絡(luò)中的數(shù)據(jù)流，當(dāng)網(wǎng)絡(luò)中端口發(fā)送數(shù)據(jù)流的最大帶寬利用率同樣為25%時(shí)，依據(jù)文獻(xiàn)[20]中的泛化網(wǎng)絡(luò)演算模型，得到延遲上界隨網(wǎng)絡(luò)中數(shù)據(jù)流的比特流速率變化的圖像如圖9中不區(qū)分優(yōu)先級(jí)曲線所示。由高優(yōu)先級(jí)與不區(qū)分優(yōu)先級(jí)曲線對(duì)比可以看出，設(shè)置高、低優(yōu)先級(jí)降低了高優(yōu)先級(jí)數(shù)據(jù)流的延遲上界，且高優(yōu)先級(jí)數(shù)據(jù)流占比越低，降低效果越顯著。相比于不區(qū)分優(yōu)先級(jí)，低優(yōu)先級(jí)延遲先減小后增大，這是增大導(dǎo)致端口對(duì)低優(yōu)先級(jí)服務(wù)速率減少與減小導(dǎo)致低優(yōu)先級(jí)數(shù)據(jù)流數(shù)目減少相平衡的結(jié)果。同時(shí)通過(guò)圖9可發(fā)現(xiàn)，當(dāng)高優(yōu)先級(jí)數(shù)據(jù)流的占比為0時(shí)，低優(yōu)先級(jí)與不區(qū)分優(yōu)先級(jí)的延遲上界結(jié)果一致。對(duì)于優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算模型，當(dāng)為0時(shí)，低優(yōu)先級(jí)延遲上界計(jì)算模型退化為文獻(xiàn)[20]中的泛化網(wǎng)絡(luò)演算模型，因此延遲上界結(jié)果一致，驗(yàn)證了算法的正確性與合理性。

4 案例分析

基于隨機(jī)生成的實(shí)驗(yàn)案例，對(duì)比采用優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算和具備詳細(xì)參數(shù)的網(wǎng)絡(luò)演算得到的端到端延遲上界結(jié)果，從而分析優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算的算法性能。通過(guò)2種算法對(duì)比高、低優(yōu)先級(jí)數(shù)據(jù)流延遲上界，用于具體指導(dǎo)網(wǎng)絡(luò)設(shè)計(jì)。

案例采用12個(gè)端系統(tǒng)和4個(gè)交換機(jī)，每個(gè)交換機(jī)與3個(gè)端系統(tǒng)以及另外3個(gè)交換機(jī)通過(guò)100 Mbit/s 的物理鏈路相連，拓?fù)浣Y(jié)構(gòu)如圖10所示。案例中采用120條數(shù)據(jù)流，數(shù)據(jù)流通過(guò)虛擬鏈路承載，數(shù)據(jù)流的配置信息隨機(jī)生成。數(shù)據(jù)流的源節(jié)點(diǎn)與目的節(jié)點(diǎn)從12個(gè)端系統(tǒng)中隨機(jī)選取(源節(jié)點(diǎn)與目的節(jié)點(diǎn)不相同且之間經(jīng)過(guò)交換機(jī))，數(shù)據(jù)流的最大幀長(zhǎng)從84～1 538 Bytes中隨機(jī)選取。選定網(wǎng)絡(luò)中數(shù)據(jù)流的比特速率為0.1 Mbit/s，并由此計(jì)算出數(shù)據(jù)流的帶寬分配間隔。網(wǎng)絡(luò)中虛擬鏈路路徑通過(guò)負(fù)載均衡策略自動(dòng)生成。

圖10 案例分析拓?fù)浣Y(jié)構(gòu)Fig.10 Topology of case study

對(duì)于實(shí)驗(yàn)案例，分別分配高優(yōu)先級(jí)數(shù)據(jù)流的數(shù)目占端口發(fā)送數(shù)據(jù)流數(shù)目的百分比為10%～90%，并以10%為間隔。通過(guò)具備詳細(xì)參數(shù)的網(wǎng)絡(luò)演算分別計(jì)算高、低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界；此外，通過(guò)統(tǒng)計(jì)的方法得到組網(wǎng)特征參數(shù)，并通過(guò)優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算分別計(jì)算高、低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界，如圖11所示。

圖11 基本網(wǎng)絡(luò)演算與泛化網(wǎng)絡(luò)演算對(duì)比Fig.11 Comparison of basic network calculus and generalized network calculus

對(duì)于具備詳細(xì)參數(shù)的網(wǎng)絡(luò)演算下的高優(yōu)先級(jí)數(shù)據(jù)流，隨高優(yōu)先級(jí)數(shù)據(jù)流占比增大，其端到端延遲上界增大。而隨著高優(yōu)先級(jí)數(shù)據(jù)流占比增大，低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界略微增大，在圖11 中變化不明顯。對(duì)于優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算下的高優(yōu)先級(jí)數(shù)據(jù)流，變化趨勢(shì)與基本網(wǎng)絡(luò)演算相同，但延遲高于基本網(wǎng)絡(luò)演算。由于實(shí)驗(yàn)案例的組網(wǎng)特征參數(shù)由統(tǒng)計(jì)得出，不能保證在不同高優(yōu)先級(jí)數(shù)據(jù)流占比下網(wǎng)絡(luò)中端口發(fā)送高、低優(yōu)先級(jí)數(shù)據(jù)流最大帶寬利用率之和+為定值，因此優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算計(jì)算出的低優(yōu)先級(jí)數(shù)據(jù)流端到端延遲上界并非一直增長(zhǎng)趨勢(shì),但趨勢(shì)變化不大。

定義同一網(wǎng)絡(luò)配置下具備詳細(xì)配置參數(shù)的網(wǎng)絡(luò)演算得到的延遲上界占優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算得到的延遲上界的比例為優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算的算法有效性。分別對(duì)比高、低優(yōu)先級(jí)數(shù)據(jù)流在具備詳細(xì)配置參數(shù)的網(wǎng)絡(luò)演算和優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算下的延遲上界?？梢钥闯觯c具備詳細(xì)配置參數(shù)的網(wǎng)絡(luò)演算依賴網(wǎng)絡(luò)拓?fù)?、流量詳?xì)配置參數(shù)和優(yōu)先級(jí)不同，優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算依據(jù)抽象出的端口發(fā)送高、低優(yōu)先級(jí)數(shù)據(jù)流帶寬利用率等組網(wǎng)特征參數(shù)，進(jìn)行采用優(yōu)先級(jí)調(diào)度機(jī)制網(wǎng)絡(luò)的實(shí)時(shí)性能分析。在不同高優(yōu)先級(jí)數(shù)據(jù)流占比下，高優(yōu)先級(jí)數(shù)據(jù)流延遲上界算法有效性均高于39%，低優(yōu)先級(jí)數(shù)據(jù)流延遲上界算法有效性均高于33%。由此可以得出，在未知組網(wǎng)拓?fù)湟约傲髁烤唧w配置參數(shù)和優(yōu)先級(jí)的情況下，優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算具備對(duì)采用高、低優(yōu)先級(jí)調(diào)度機(jī)制的交換式網(wǎng)絡(luò)實(shí)時(shí)性預(yù)估的能力。

分別對(duì)比具備詳細(xì)參數(shù)的網(wǎng)絡(luò)演算和優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算下高、低優(yōu)先級(jí)數(shù)據(jù)流延遲上界，均可以得出高優(yōu)先級(jí)數(shù)據(jù)流延遲上界小于低優(yōu)先級(jí)數(shù)據(jù)流延遲上界的結(jié)論。因此區(qū)分優(yōu)先級(jí)可以改善高優(yōu)先級(jí)數(shù)據(jù)流延遲上界，適合實(shí)時(shí)性要求高的消息應(yīng)用。并且通過(guò)具備詳細(xì)參數(shù)的網(wǎng)絡(luò)演算和優(yōu)先級(jí)驅(qū)動(dòng)的泛化網(wǎng)絡(luò)演算2種，都可以得出降低高優(yōu)先級(jí)數(shù)據(jù)流占比可以明顯改善高優(yōu)先級(jí)數(shù)據(jù)流延遲上界，但對(duì)低優(yōu)先級(jí)數(shù)據(jù)流延遲上界影響不大的結(jié)論。因此在網(wǎng)絡(luò)設(shè)計(jì)中可以將對(duì)實(shí)時(shí)性要求高的消息設(shè)置為高優(yōu)先級(jí)，且消息實(shí)時(shí)性要求越高，網(wǎng)絡(luò)中高優(yōu)先級(jí)數(shù)據(jù)流占比應(yīng)越小。

5 結(jié) 論

本文提出了優(yōu)先級(jí)驅(qū)動(dòng)的泛化航電網(wǎng)絡(luò)實(shí)時(shí)性能分析方法：

1) 分析優(yōu)先級(jí)調(diào)度策略，抽象出網(wǎng)絡(luò)中端口發(fā)送高、低優(yōu)先級(jí)數(shù)據(jù)流的最大帶寬利用率2個(gè)組網(wǎng)特征參數(shù)，用于網(wǎng)絡(luò)中高、低優(yōu)先級(jí)數(shù)據(jù)流占比的刻畫(huà)。

2) 分別對(duì)高、低優(yōu)先級(jí)數(shù)據(jù)流的服務(wù)曲線進(jìn)行泛化，得出基于組網(wǎng)基本特征的高、低優(yōu)先級(jí)延遲上界計(jì)算公式，彌補(bǔ)了現(xiàn)有泛化網(wǎng)絡(luò)演算缺乏對(duì)不同優(yōu)先級(jí)數(shù)據(jù)流實(shí)時(shí)性預(yù)估的能力。

3) 將高、低優(yōu)先級(jí)延遲分析結(jié)果與不區(qū)分優(yōu)先級(jí)泛化網(wǎng)絡(luò)演算得到的結(jié)果進(jìn)行對(duì)比，驗(yàn)證算法正確性與合理性，并給出優(yōu)先級(jí)占比推薦方案。

4) 利用網(wǎng)絡(luò)典型拓?fù)潆S機(jī)生成實(shí)驗(yàn)案例，得出對(duì)于高、低優(yōu)先級(jí)算法有效性均超過(guò)33%，實(shí)現(xiàn)了基于組網(wǎng)特征參數(shù)對(duì)采用優(yōu)先級(jí)調(diào)度策略交換式網(wǎng)絡(luò)的實(shí)時(shí)性能預(yù)估。