孫續(xù)航 吳宇 孫鳳

摘要：隨著多域光網(wǎng)絡規(guī)模的不斷擴大，跨域路徑計算的需求量會增多、復雜性會提高，并且考慮域間多個資源參數(shù)約束的最小二乘擬合計算策略會造成計算效率降低。針對上述問題，提出在分層路徑計算單元（H-PCE） 架構(gòu)的基礎上，結(jié)合靈活以太網(wǎng)技術（Flexible Ethernet， FlexE） ，通過拓撲聚合將復雜的多域光網(wǎng)絡抽象為簡單的虛擬拓撲，域內(nèi)PCE使用Dijkstra算法來計算域內(nèi)路徑并向父PCE反饋，父PCE根據(jù)FlexE的技術約束執(zhí)行多商品流計算策略計算域間路徑。實驗結(jié)果表明，所提策略可以有效降低大規(guī)模多域光網(wǎng)絡路徑計算時間。

關鍵詞：多域光網(wǎng)絡; 路徑計算單元; 靈活以太網(wǎng); 拓撲聚合; 多商品流

中圖分類號：TN91? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）10-0006-03

1 引言

網(wǎng)絡域是在地址管理或路徑計算共同范圍內(nèi)的網(wǎng)元的集合。 在大規(guī)模的多域光網(wǎng)絡中，由于域內(nèi)的隱私性和網(wǎng)絡的可擴展性，拓撲信息和流量工程不會向其他域公布，路徑計算復雜、路由器計算能力受限并且可能需要特殊的組件完成指定計算，同時還存在需要多域網(wǎng)元相互協(xié)作的問題。在這種背景下，IETF提出路徑計算單元（PCE） ，PCE是一個能夠基于已知的網(wǎng)絡拓撲進行有約束的路徑計算的實體[1]。

隨著光網(wǎng)絡的迅速發(fā)展，傳統(tǒng)的以太網(wǎng)接口漸漸無法滿足光通信的需求，底層光傳輸網(wǎng)絡的鏈路速率、接口和模塊固定，需要調(diào)整以適應各種傳輸需求。FlexE是在傳統(tǒng)以太網(wǎng)技術的基礎上，滿足帶寬配置靈活和高速率傳輸?shù)刃枨筇岢龊桶l(fā)展的。FlexE雖然可以適應靈活多變的大規(guī)模多域光網(wǎng)絡，但是依然存在路由資源分配低效而導致網(wǎng)絡性能低下的問題。文獻[2]考慮在一個DWDM域中利用貪心算法解決長序列整數(shù)線性規(guī)劃問題，從而得到業(yè)務流的最佳分配。文獻[3]提出在多域網(wǎng)絡中利用最小二乘擬合圓的方法，計算域序列并分配業(yè)務流。PCE在上述方案中無法滿足大規(guī)模多域網(wǎng)絡的路徑計算請求，隨著網(wǎng)絡域的增多，PCE性能下降顯著。因此，本文提出采用分層PCE（H-PCE） 架構(gòu)，父PCE（p-PCE） 負責全局路徑計算，其流量工程數(shù)據(jù)庫（TED） 掌握全局拓撲的抽象資源信息，子PCE（c-PCE） 負責域內(nèi)路徑計算，并使用拓撲聚合的方式以減少p-PCE的計算壓力。針對路徑計算提出一種基于多商品流問題（MCFP） 的計算策略，考慮域間鏈路的時延和可用鏈路（PHY） 的個數(shù)，確定最佳域序列，減少FlexE group的候選FlexE tunnel的個數(shù)，進一步提高p-PCE的計算性能。

2 多域光網(wǎng)絡FlexE路由模型

2.1 多域光網(wǎng)絡拓撲聚合

2.1.1 多域光網(wǎng)絡模型

本文采用H-PCE一般架構(gòu)描述多域網(wǎng)絡路徑計算模型，位于編排器中的TED掌握全局拓撲的抽象資源信息，p-PCE負責根據(jù)TED進行全局路徑計算， TED掌握全局拓撲的抽象資源信息，而 c-PCE只負責本域路徑計算，并將本域的抽象資源信息上傳給編排器的p-PCE，如圖1所示。

2.1.2 靈活以太網(wǎng)FlexE

FlexE是OIF組織基于IEEE802.3/1制訂的標準體系架構(gòu)的擴展研究，它基于OSI七層模型在PHY層和MAC層之間增加了shim層，使得MAC層與PHY層的數(shù)量從單一的1：1關系變?yōu)閙：n的關系，實現(xiàn)MAC和PHY的解耦，MAC層帶寬不再受限于單個以太網(wǎng)PHY通道的帶寬。FlexE shim可以將FlexE client（一種基于MAC數(shù)據(jù)速率的以太網(wǎng)流） 映射或反映射到FlexE group中[4]，如圖2所示。

FlexE可提供三種主要的功能：

捆綁（Bonding）：與鏈路聚合相似，F(xiàn)lexE支持將多個PHY捆綁，因此，節(jié)點間多路PHY可以看作是一條大容量的鏈路（FlexE group） 以實現(xiàn)鏈路擴容。例如，將2個100G的PHY捆綁實現(xiàn)200G的FlexE client。

通道化（Channelization）：多路低速率FlexE client共享一路或者多路PHY。例如，在100G PHY上承載25G、35G、20G與 20G的四路FlexE client，或者在三路 100G PHY上復用承載125G、150G與 25G的FlexE client。

子速率（Sub-Rate）：單一低速率FlexE client共享一路或者多路PHY，并通過特殊定義的Error Control Block實現(xiàn)降速工作。例如，在100G PHY上僅僅承載 50G FlexE client。

2.1.3 拓撲聚合

拓撲聚合是解決大規(guī)模多域光網(wǎng)絡可擴展性和安全性問題的動力之一[5]，其基本原理是聚合域內(nèi)的拓撲信息并通知其他域，在減少域間交換信息的同時，有效地保證域內(nèi)隱私性。目前，現(xiàn)有的拓撲聚合方式包括：單節(jié)點聚合、星型聚合、全網(wǎng)格聚合等方式[5]。單節(jié)點聚合可擴展性強，但沒有顯示域內(nèi)可用資源;星型聚合方式中，所有邊界節(jié)點連接到一個域內(nèi)虛擬節(jié)點，星型分支可以描述可用資源及穿越網(wǎng)絡的成本;全網(wǎng)格聚合方式中，域內(nèi)所有邊界節(jié)點互連，每一條域內(nèi)虛擬鏈路可以描述邊界節(jié)點之間的可用資源，但可擴展性差。

本文關注虛擬拓撲的域間鏈路，域間鏈路兩端節(jié)點支持FlexE，而域內(nèi)信息由c-PCE提供，因此選擇單節(jié)點聚合方式。如圖3所示，圖1的多域網(wǎng)絡經(jīng)過單節(jié)點聚合方式得到該虛擬拓撲，p-PCE只需要考慮虛擬域節(jié)點的拓撲結(jié)構(gòu)進行路徑計算，進而提高計算性能。

2.2 多域光網(wǎng)絡路徑計算

跨域路徑計算可通過反向遞歸路徑計算協(xié)議BRPC實現(xiàn)[6]，但是需要在全局域序列的基礎上進行。同樣，經(jīng)過拓撲聚合得到虛擬域拓撲，PCE也需要選擇最優(yōu)的域序列，并考慮鏈路的權值（通常是QoS值） 來優(yōu)化多域光網(wǎng)絡性能。鏈路權值在光網(wǎng)絡領域通常只考慮一個因素（例如，最短鏈路或鏈路的波長數(shù)） [2]。然而，這會導致路徑計算后大量業(yè)務流經(jīng)過相同鏈路，造成網(wǎng)絡擁塞和生存性較差的問題。在多域光網(wǎng)絡中，為了實現(xiàn)網(wǎng)絡業(yè)務的低阻塞率，可以考慮域間鏈路的兩個權值，即：鏈路時延w和域間鏈路可用PHY的數(shù)量n，選擇最優(yōu)域序列，從而降低網(wǎng)絡阻塞率。解決上述問題可以采用基于最小二乘擬合的計算策略[7]或階梯擬合策略[8]，但是隨著網(wǎng)絡域的增多，PCE性能下降顯著。對比上述策略，本文提出線性規(guī)劃方法選取最優(yōu)路徑，并分配業(yè)務流。

2.2.1 最小二乘擬合策略

每一條域間鏈路i都帶有一對權值（wi， ni），所有鏈路的權值可以看作是多個點分布在直角坐標系平面內(nèi)。每個域序列存在一條由域間鏈路組成的FlexE tunnel，pm表示第m個域序列的FlexE tunnel，Im表示第m個域序列包含的域間鏈路集，pm是一個帶有域間鏈路權值的點集，即：

[pm ={（wi， ni）|i∈Im} ]? ? ? ? ? ? ? ? （1）

每一個域序列點集可以近似地落在一個圓上，并且圓的半徑和圓心可以利用點集計算得到，利用最小二乘法分析可以最小化誤差，進而可以將多個點擬合到一個中心點來表示該點集的平均值。例如，一個域序列包含三條域間鏈路（w1， n1）（w2， n2）（w3， n3），可以利用最小二乘擬合圓，得到擬合圓的圓心（wc， nc）。通過公式（2）可以得到每個域序列的wc值并比較，該值最大所表示的域序列是最優(yōu)域序列。

[Ac = nc - α · wc]? ? ? ? ? ? （2）

α是一個調(diào)節(jié)因子，用來調(diào)節(jié)PHY的數(shù)量與鏈路時延的比例，實現(xiàn)鏈路兩個權值的比例公平。選擇Ac值最大的域序列作為最佳FlexE tunnel。

由此，同時考慮了域間鏈路時延和可用PHY的數(shù)量，能夠更好地降低域間發(fā)生阻塞的概率。

2.2.2 多商品流優(yōu)化策略

多域光網(wǎng)絡選擇最佳路徑可以看作是多商品流優(yōu)化問題（Multiple Commodity Flow， MCF） [9]，即為FlexE group中的FlexE client選擇FlexE tunnel。考慮FlexE tunnel的兩個權值，最佳FlexE tunnel需要盡量保證最大域間PHY數(shù)量的同時降低鏈路時延。MCF如下：

[Maximize? ?∑p∈P[ （1-θ） · fp - θ · fp · wp]]? ? ? ? （3）

[S.t.? ?minj∈Jd{dj}≤ ∑p∈P fp? ≤ ∑j∈Jd dj]? ? ? ? ? ? （4）

[?i∈Im： 0 ≤ ∑p∈P fp? ≤ cphy · niphy ]? ? ? ? ? ? ?（5）

fp 表示第p個tunnel的業(yè)務流分配;wp表示第p個tunnel的時延（第p個tunnel內(nèi)每條域間鏈路的時延和） ;θ是一個常數(shù)，且0 < θ < 1;cphy表示每個PHY的容量，niphy表示第p個FlexE tunnel內(nèi)第i條域間鏈路的PHY的數(shù)量。約束（4）表示第p個FlexE tunnel內(nèi)的流量不能超過總業(yè)務流需求，避免對PHY數(shù)量過度預定。約束（5）表示第p個FlexE tunnel內(nèi)的流量不能超過每條域間鏈路的容量。

2.2.3 FlexE client分配算法

選取FlexE tunnel后，需要為每個FlexE client分配tunnel，由于接收端FlexE shim無法補償不同光路的PHY帶來的時延偏差，因此FlexE client必須執(zhí)行共路約束[8]，即：每一個FlexE client只可以分配給一個FlexE tunnel。但是由于FlexE通道化特性，一個FlexE tunnel可以承載多個FlexE client。算法1描述了FlexE client的分配，保證了FlexE的共路約束。

[算法1：FlexE client分配算法 輸入：候選FlexE tunnel，F(xiàn)lexE client，鏈路集Im

輸出：FlexE client分配

1. s_Client ← 按大小對FlexE client降序排序

2. Cp ← 求得每一個FlexE tunnel的容量

3. for s∈ s_Client do

4. ? ? for t∈ FlexE tunnel do

5. ? ? ? ? if? s≤ Cp then

6. ? ? ? ? ? ? s分配給t;

7. ? ? ? ? ? ? rp，i ← 求出p對應鏈路的剩余容量;

8. ? ? ? ? ? ? if? rp，i ≤ 0 then

9. ? ? ? ? ? ? ? ? 刪除鏈路i對應的所有候選FlexE tunnel;

10. ? ? ? ? ? ? end if

11. ? ? ? ? end if

12. ? ? end for

13. end for ]

2.2.4 PCE路徑計算算法

（1） 源節(jié)點的路徑計算客戶端（PCC） 收到業(yè)務連接請求后，將此請求轉(zhuǎn)給本域的c-PCE，判斷目的節(jié)點是否在同一域。如果是，使用Dijkstra算法來計算域內(nèi)路徑。否則，c-PCE將該請求轉(zhuǎn)移到p-PCE。

（2） p-PCE收到路徑計算的請求后，將拓撲聚合機制的請求轉(zhuǎn)給所有c-PCE。在收到請求后，c-PCE將虛擬域節(jié)點信息和域間鏈路的狀態(tài)發(fā)送給p-PCE。p-PCE根據(jù)上述信息更新TED。

（3） p-PCE找到目的節(jié)點的域并向源域和目的域的c-PCE發(fā)送路徑計算指令。p-PCE根據(jù)TED維護的虛擬拓撲信息和本地計算策略，計算出一個最佳域序列。p-PCE根據(jù)域序列的信息向各個域的c-PCE發(fā)送路徑請求信息，并分別計算出各域的詳細路徑信息。當每個域的路徑計算完成后，每個路徑片段被發(fā)送到p-PCE。p-PCE根據(jù)本地策略和約束條件選擇符合條件的最優(yōu)路由，并將其發(fā)送給源域的c-PCE。

（4） 信令協(xié)議RSVP-TE從源節(jié)點開始，逐跳為連接保留資源。如果所有鏈路都有足夠的可用波長，則建立路徑。否則，業(yè)務被阻斷。

3 實驗結(jié)果與分析

3.1 多域光網(wǎng)絡拓撲實驗模型

實驗選擇將多域網(wǎng)絡進行網(wǎng)格化處理，c-PCE掌握域內(nèi)拓撲信息并將本域虛擬為一個單節(jié)點反饋給p-PCE。如圖4所示，一個4階多域網(wǎng)格拓撲，p-PCE掌握源域S和目的域D以及全局域拓撲的資源信息。

3.2 結(jié)果與分析

實驗將網(wǎng)格階數(shù)作為變量，在各個階數(shù)網(wǎng)格虛擬拓撲上，記錄并對比最小二乘擬合策略和多商品流計算策略的p-PCE計算時間，實驗結(jié)果如圖5所示。隨著網(wǎng)格階數(shù)的增加，最小二乘擬合圓計算策略的計算時間增長趨勢近似于指數(shù)型，而多商品流策略的計算時間增長趨勢近似于線性增長。小規(guī)模多域網(wǎng)絡（Mesh order ≤ 5） 中，執(zhí)行兩種策略的p-PCE計算效率大致相同;而對于大規(guī)模多域光網(wǎng)絡，多商品流計算策略可以滿足超低時延的計算需求。

4 總結(jié)

本文提出了基于分層PCE架構(gòu)下，利用可以提供高帶寬的靈活以太網(wǎng)FlexE技術，進行多域光網(wǎng)絡路徑計算，并對比最小二乘擬合策略，提出多商品流優(yōu)化策略。通過對不同規(guī)模的多域光網(wǎng)絡進行建模實驗，發(fā)現(xiàn)對于大規(guī)模多域光網(wǎng)絡，多商品流計算策略可以滿足超低時延的計算需求，隨著網(wǎng)絡規(guī)模的不斷擴大，最小二乘擬合策略計算時間呈指數(shù)型增長，p-PCE計算效率下降，網(wǎng)絡阻塞率會迅速升高。實驗并未給出網(wǎng)絡阻塞率的對比結(jié)果，此將會在未來工作中進行。

參考文獻：

[1] Farrel A，Vasseur J P，Ash J.A path computation element （PCE）-based architecture[EB/OL].https：//www.ietf.org/rfc/rfc4655.txt.

[2] Eira A，Pereira A，Pires J，et al.On the efficiency of flexible Ethernet client architectures in optical transport networks[J].Journal of Optical Communications and Networking，2018，10（1）：A133-A143.

[3] Zhou H S，Song X Q，Lin L，et al.Multi-domain routing technology based on PCE for intelligent optical networks[C]//2017 6th International Conference on Computer Science and Network Technology （ICCSNT），2017：415-419.

[4] The Optical Internetworking Forum. Flex Ethernet 2.1 Implementation Agreement [EB/OL]. https：//www.oiforum.com.

[5] Chamania M，Jukan A.A survey of inter-domain peering and provisioning solutions for the next generation optical networks[C]//IEEE Communications Surveys & Tutorials.IEEE，2009：33-51.

[6] Vasseur JP. A Backward-Recursive PCE-Based Computation （BRPC） Procedure to Compute Shortest Constrained Inter-Domain Traffic Engineering Label Switched Paths [EB/OL]. https：//www.ietf.org/rfc/rfc5441.txt.

[7] 吳大鵬，張磊，呂翊，等.大規(guī)模多域光網(wǎng)絡中帶有多參數(shù)擬合的跨域路徑計算策略[J].上海交通大學學報，2015，49（2）：209-213.

[8] The Optical Internetworking Forum. FlexE neighbor discovery implementation agreement [EB/OL]. https：//www.oiforum.com.

[9] Koulougli D，Nguyen K K，Cheriet M.Efficient routing using flexible Ethernet in multi-layer multi-domain networks[J].Journal of Lightwave Technology，2020，39（7）：1925-1936.

【通聯(lián)編輯：代影】

收稿日期：2021-11-17

基金項目：南京信息職業(yè)技術學院校級基金項目資助（YK20200802）

作者簡介：孫續(xù)航（1995—） ，男，山東煙臺人，碩士研究生，主要研究方向為軟件定義網(wǎng)絡與網(wǎng)絡功能虛擬化;吳宇（1986—） ，男，助教，碩士;孫鳳（1986—） ，女，講師，博士。