面向算力網絡的多路徑時敏優先調度機制

夏華屹/XIA Huayi，權偉/QUAN Wei，張宏科/ZHANG Hongke

（北京交通大學，中國 北京 100044）

數字經濟已成為中國經濟發展不可或缺的驅動力，而算力作為數字經濟的重要部分，在信息數據處理、智能算法優化等方面起著關鍵作用[1]。截至2023年3月底，中國累計建成5G基站超過264萬個，算力總規模達到每秒180運算次數（EFLOPS）；算力規模快速增長，梯次優化的算力供給體系初步構建，算力規模排名全球第二，年增長率近30%。以OpenAI推出的智能對話模型ChatGPT為代表的人工智能（AI）技術的爆發讓全球算力大盤中的智能算力占比提升，第三方數據分析機構IDC在《2021—2022全球計算力指數評估報告》指出：算力指數平均每增加1%，國家數字經濟和國內生產總值（GDP）則分別增長3.5‰和1.8‰[2]。據國家發展改革委與工業和信息化部等部門聯合實施的“東數西算”工程，中國將重點發展算力全產業鏈的自主可控建設，形成一體化的新型算力網絡體系。該工程對國家政治、經濟以及各行業的發展有著重要意義[3]。

為提升數據通信質量，邊緣計算中心、高性能數據中心等算力基礎設施在生活中的應用逐漸增多。但同時這也逐漸暴露出算力設施在面對多樣化服務流量時，計算節點的計算任務分配機制不完善、無法合理使用算力資源等問題。這使得算力設施在使用場景中有了局限性[4]。為解決上述問題，研發者們提出了算力網絡的概念，即一種以算為中心、網為根基，網、云、數、智、安、邊、端、鏈（ABCD-NETS）深度融合的一體化信息服務基礎設施[5]。算力網絡可以保證用戶體驗的一致性，使用戶可以基本忽略基礎設施資源的分布位置與調動狀態，為多樣化服務流量的分配與調度提供了解決思路[6]。對此，互聯網研究工作組（IRTF）設立了網內計算研究組（COIN），研究算力網絡新型傳輸架構；中國通信標準化協會網絡與業務能力技術工作委員會（CCSA TC3）已完成《算力網絡需求與架構》等研究。算力網絡的發展已取得部分進展，但仍面臨著諸多技術挑戰。其中，算力網絡下的低時延調度機制問題亟待解決。

面對算力網絡的低時延傳輸需求，研究者從不同角度進行了方案與機制的研究。文獻[7]設計了一種以服務器為中心、網絡構造遞歸的數據中心模式以提供低延遲調度，支持延遲敏感數據的傳輸，但其部署模式不易拓展，較難根據算力調用需求進行網絡規模的迭代。文獻[8]設計了一種異構分布式數據中心場景下的工作流調度算法，提出了低負載、低成本與低延遲的多目標優化模型，但暫未考慮多樣化服務的算力調用需求，較難滿足不同用戶的復雜需求。文獻[9]提出了一種按需分配的算力資源的聯合優化路由控制與資源分配調度模型，旨在降低算力網絡的確定性時延，但這種以最短路徑為指向的任務調度較難滿足多樣化服務流中的差異化調度優先級需求。文獻[10]提出了一種基于動態三向決策的任務調度算法，為任務分配不同的權重，并結合工作模式和任務期限進行優先級規劃，其調度算法能滿足單一計算中心的高優先級任務調度需求，但沒有考慮結合算力網絡進行拓撲級的宏觀調度調控。文獻[11]根據算力網絡不同層次的特性和各種應用的不同需求，提出一種多層次算力網絡模型和計算卸載系統以降低確定性時延。該模型考慮了單一模型的任務調度場景，在面對多樣化服務時，較難實現差異化調度服務需求。

綜上所述，目前業界對算力網絡多樣化服務的低時延傳輸機制的研究尚不成熟。為此，本文設計面向算力網絡的多路徑時敏優先調度機制，通過基于強化學習的多路徑轉發調度以及優先級隊列調度，降低算力網絡中低時延需求數據包傳輸及排隊時延，實現算力網絡傳輸時延的相對確定性。

1 系統設計

1.1 機制總體設計

本文設計了面向算力網絡的多路徑時敏優先調度機制，其系統架構如圖1所示。該機制保障算力網絡中多樣化服務的低時延通信需求：

▲圖1 多路徑時敏優先調度系統架構

1）多路徑轉發調度（作用于數據包轉發過程）。通過基于強化學習的路徑選擇算法，該機制對算力網絡中各路徑的傳輸價值進行量化，動態更新各路徑的價值量，并做出路徑選擇；對路徑時延進行隨機變量數學建模，在一定置信概率內利用主從備份傳輸機制，實現時延性能的提升。

2）優先級隊列調度（作用于算力路由設備出端口數據包排隊過程）。該機制設計了包等級與優先隊列映射算法：當優先隊列數量小于包等級范圍時，數據包將近似按等級順序出隊，擬合數據包推入先出行為，從而減少算力網絡中時延敏感型網絡數據包在隊列緩沖區的排隊時延。

1.2 多路徑轉發調度

本文所提的多路徑轉發調度指通過強化學習，探索與學習路徑特征并做出相應決策。它是一種通過智能體與環境的交互來獲取最優決策的方法。本模塊將算力網絡控制器抽象為智能體，將其所處各路徑的算力網絡狀態定義為環境，將路徑選擇算法每次做出的決策定義為回合迭代，并將回合迭代中所選取的傳輸路徑定義為動作。在選擇該動作的情況下，本文所設計的多路徑轉發調度以所探測到的網絡信息作為狀態，將路徑時延定義為獎賞。

由于在算力網絡中存在排隊、擁塞等問題，我們假設第k路徑的時延變量Xk服從對數正態分布， 即ln (Xk)～N(μ,δ2)。當給定xk＞0 時，其概率分布函數如公式（1）所示：

其中，對數正態分布的最大似然估計如公式（2）和公式（3）所示。其中，Nk表示選擇路徑k的次數。

對數正態分布隨機變量的均值和方差如公式（4）和公式（5）所示：

由于對數正態分布，其隨機變量分布較為復雜。若將其長尾部分省略，則近似認為第k路徑的時延變量Xk服從均值為μk、方差為的高斯隨機變量，且各路徑的時延變量Xk相互獨立。Xk的概率密度函數如公式（6）所示：

對于對數正態分布其統計意義上的期望及方差無偏估計如公式（7）和公式（8）所示：

在路徑選擇算法中，每一輪次的路徑選擇會根據實時網絡數據來更新每一條路徑的價值量，并對價值量進行排序，選取最大的路徑作為主傳輸路徑。路徑選擇算法的價值量計算如公式（9）所示：

其中，S表示路徑選擇的總次數；代表第k條路徑選擇次數與選擇總數之間的關系，它可以表征這條路徑時延的置信區間。當一條路徑探索次數較其他路徑較少時，可以認為該路徑有較為寬泛的置信區間，即具備較大的探索價值。當一條路徑反復被選取時，可以近似認為其置信區間變小，探索價值變低。我們設計的是樂觀的選路算法，即在選路時認為置信區間對于選路的決策呈現正向作用。

本文中我們通過基于強化學習的路徑選擇算法，選取當前最大價值量路徑作為主傳輸路徑。然而，考慮路徑時延抖動與路徑探索等因素的影響，價值量最大的路徑可能并不是算力網絡中時延敏感型傳輸服務的最優選擇，因此我們設計了一種多路主從傳輸機制，利用冗余發包選取備份傳輸路徑，犧牲了部分帶寬，以換取時延性能的提升。

經以上分析，我們可近似將各路徑時延分布Xk作相互獨立的高斯正態分布處理，并假定基于最大價值量選取的路徑為i，時延分布為Xi，則，即兩獨立路徑的時延隨機變量相減仍為高斯正態分布，路徑k傳輸時延優于最大價值量路徑i的概率可表示為：

假定P{Xk-Xi≥0}≥α，該條路徑可以作為備選次優路徑。若有多條路徑均符合上述概率條件，則選取置信概率最大的路徑進行傳輸，以避免占用過多帶寬資源。

多路徑低時延轉發調度算法的具體流程如算法1所示。

1.3 優先隊列調度模塊設計

當路徑選擇模塊選定具體的傳輸路徑后，算力網絡中多種網絡業務并存且需求帶寬大于出口帶寬時，時延敏感型算力服務會產生較大的排隊時延，難以滿足用戶需求。因此，本文中我們在可編程交換設備出端口設計了優先級隊列調度模塊，設計包等級與隊列自適應映射算法擬合數據包推入先出行為，減少低時延需求數據包的排隊時延。我們基于P4數據平面實現的自適應隊列調度機制簡稱為P4-APQ。

包等級與隊列自適應映射算法的示意如圖2所示，其作用場景為數據包等級范圍大于優先隊列數量。該調度算法可利用有限嚴格優先級隊列來擬合數據包的推入先出過程，即數據包近似按等級順序出隊列（本文中，我們約定等級越小，調度優先度越高）。自適應映射算法誤差定義為較大等級數據包數量小于較小等級數據包出隊的數據包數量，我們將這種誤差的現象稱為“反轉”。由于利用了嚴格優先級隊列擬合推入先出行為即按等級順序出隊，因此當數據包等級范圍大于嚴格優先級隊列數量時，有一定概率在調度過程中會出現“反轉”現象。對于本文所設計的包等級-隊列映射，設計目的為在保證小等級數據包優先調度的前提下，盡可能按等級順序出隊，減少“反轉”現象。

▲圖2 包等級與隊列自適應映射算法示意圖

針對算力網絡時敏型業務低時延需求，包等級與隊列自適應映射機制設計了高優先級預留隊列，避免最小等級的數據包因優先級“反轉”現象而出現較高的排隊時延。具體地，首先判定數據平面傳入數據包的等級；若等級最小，數據包將直接進入具有最高優先級的預留隊列，從而避免等級隊列的動態映射帶來的“反轉”損失。

當數據包等級不是最小時，為保證隊列調度結果近似按等級順序出隊，我們設計了自適應映射算法，動態改變各隊列的邊界值，以最小化擬合損失。自適應映射算法的損失函數可以描述為公式（11）：

其中，L表示為擬合損失，P表示所有入隊數據包，q表示一組動態變化的隊列邊界向量，p表示屬于P的一個入隊數據包。單個數據包的損失可以表示為公式（12）：

其中，r(p)表示為給定的數據包p的等級，rp(p,q)表示為給定數據包所映射的隊列自適應調整后的邊界值，cost表示單個數據包產生的誤差，即出現“反轉”的情況。包等級與隊列自適應映射算法通過動態調整數據包等級與各優先隊列的映射關系，在兼顧數據平面的算法復雜度基礎上，降低損失函數L。

包等級與隊列自適應映射算法可分為兩個階段：

1）“上推”階段。在該階段，通過增加進入數據包所映射隊列的邊界值，減少數據包分組等級與隊列邊界值的差值，從而減少映射中出現的誤差值。具體地，傳入的數據包將從較低優先級的隊列開始匹配。當數據包等級r(p)大于等于隊列邊界qi時，數據包進入該隊列，同時將隊列邊界qi增加到等于該數據包等級r(p)。該過程可以盡量保證數據包實現零誤差映射，并防止等級小于隊列邊界值的數據包映射到當前隊列。以上設計僅針對非最高優先級隊列。當映射過程匹配到最高優先級隊列（不包括預留隊列），即使r(p)＜q1時，當前數據包會進入最高優先級隊列。這將出現“反轉”現象，并帶來較大的映射損失。這時，我們將根據公式（12）來計算誤差損失，并更新最高優先級隊列邊界值為該數據包等級。

2）“下推”階段。由于“上推”階段可能導致最高優先級隊列出現“反轉”現象，“下推”階段將減少“上推”階段的調度損失。當最高優先級隊列出現“反轉”現象時，自適應算法將根據公式（12）來計算損失成本，再根據公式（13）依次減少除最高優先級隊列以外的隊列邊界。該階段降低了最高優先級以外的隊列邊界，減少較高優先級隊列中允許進入的數據包等級范圍，即減少等級較大的數據包進入高優先級隊列的情況，進而減少出現“反轉”現象，降低調度損失。

本文所設計的等級與優先隊列自適應映射算法的具體流程見算法2。

2 實驗驗證與性能分析

為測試多路徑時敏調度機制相關功能及性能，我們于Mininet 環境下搭建包含5 臺終端主機及5 臺BMv2 交換機的網絡拓撲。其中H1、H2、H3、H4 作為算力服務請求方與算力路由設備S1 相連；S1 分別與算力路由設備S2、S3、S4相連作為傳輸的3 條路徑；H5 作為算力節點與算力路由設備S5相連。各路徑設置的實驗參數如表1所示。

▼表1 路徑具體參數

2.1 多路徑轉發調度性能測試

本文實現了多路徑轉發調度中置信參數α為0.05的多路徑選擇算法，同時實現了傳統輪詢方式的路徑選擇算法、ε值為0.1的貪心策略的路徑選擇算法以及基于置信區間上界（UCB）算法的路徑算法以進行相關對比分析，并對每種選路算法進行了500輪次的選路決策。

為觀察各路徑選擇算法的時延性能，我們將每10 輪計為1個記數點來計算平均時延，結果如圖3所示。本文所設計的路徑選擇算法通過前期路徑探索后，時延在50 輪后有明顯的降低，150 輪后平均時延為20 ms 左右，基本收斂于最優路徑。我們將4種算法作定量分析：多路徑選擇算法的平均時延為21.57 ms，輪詢策略的平均時延為32.56 ms，ε-貪心算法的平均時延為25.12 ms，UCB 算法的平均時延為25.91 ms。本文所提的路徑選擇算法在進行500 輪次的決策條件后，和輪詢策略相比，時延均值降低33.75%；和ε-貪心算法相比，時延均值降低14.13%；和UCB 算法相比，時延均值降低16.75%。

▲圖3 各路徑選擇算法平均時延圖

為驗證不同置信參數α對多路徑選擇算法時延性能的影響，我們設置了3 組典型參數值，分別為：α= 0.05，α=0.15，α= 0.25，并進行了500輪次的路徑決策，每10輪為1個記數點來計算平均時延，具體結果如圖4 所示。α= 0.05時，本文所設計的多路徑選擇算法平均時延為21.57 ms；α= 0.15時，平均時延為23.30 ms；α= 0.25時，平均時延為24.02 ms。實驗結果表明，較小置信參數可較多地利用主從備份傳輸，以提升傳輸性能。

▲圖4 不同置信參數下的多路徑選擇算法平均時延圖

2.2 優先隊列調度性能測試

本節中，我們將測試優先隊列調度的各項性能指標，并與先進先出（FIFO）隊列方案、基于嚴格優先級隊列擬合推入先出（SP-PIFO）[12]隊列調度方案進行對比。在典型場景下，我們測試隊列調度算法的具體性能。假設路徑選擇算法已將S1 的轉發出端口路徑收斂于S1-S3 路徑，同時設定S1與S3鏈路帶寬為50 Mbit/s，時延為10 ms，不額外設置鏈路抖動。

在典型場景下，我們預設H1、H2、H3、H4 的數據流等級分別為0、1、2、3，分別代表高優先級、次高優先級、中優先級以及低優先級。H1、H2、H3、H4在同一時刻采用iperf工具來生成用戶數據報協議（UDP）流量，再發往終端H5（持續50 s）。其帶寬分別設置為10 Mbit/s、10 Mbit/s、15 Mbit/s及20 Mbit/s，總流量大于設置鏈路帶寬。這將造成一定程度的節點擁塞，從而驗證隊列調度的相關性能。

測試中，我們利用3個FIFO隊列實現了P4-APQ，同時利用3 個FIFO 隊列實現SP-PIFO。P4-APQ、SP-PIFO 以及FIFO 的隊列數據包容量大小均設置為64。P4-APQ、SPPIFO以及FIFO隊列的高優先級流單向時延隨時間的變化如圖5所示。

▲圖5 隊列調度算法高優先級流單向時延隨時間變化圖

對于高優先級流而言，本文所提的P4-APQ算法基于高優先級預留隊列的設計，時延性能略優于SP-PIFO，顯著優于FIFO。SP-PIFO 由于沒有相關預留隊列的設計，在最高優先級隊列中會出現“反轉”的現象，因此也會出現非最高優先級的數據流量，從而造成最高優先級流時延及抖動的增加。對于FIFO 隊列，由于對各類流量不作區分處理，高優先級流量時延較大。高優先級流在P4-APQ 算法的調度下，平均時延為16.30 ms，方差為0.39 ms2；在SP-PIFO 隊列調度下中，高優先級數據流的平均時延為17.53 ms，方差為0.65 ms2；在FIFO 隊列中，高優先級數據流平均時延為26.99 ms，方差為0.41 ms2。通過定量計算可知，本文設計的P4-APQ隊列調度算法針對高優先級數據流的平均時延較SP-PIFO 降低7.01%，較FIFO 降低39.6%；抖動較SP-PIFO降低40%，較FIFO降低4.9%。

P4-APQ、SP-PIFO 以及FIFO 隊列的最高優先級流吞吐量隨時間變化的情況如圖6 所示。本文所設計的P4-APQ 隊列調度算法高優先級流吞吐量均值為10.47 Mbit/s，SP-PIFO隊列調度算法高優先級流吞吐量均值為10.41 Mbit/s；FIFO隊列在高優先級流吞吐量均值為8.54 Mbit/s。由以上定量分析可以發現，本文所采用的P4-APQ通過給各流量的等級設定，并基于等級與隊列映射算法，可以保障高優先級業務流量的穩定吞吐量；高優先級流量吞吐量高于FIFO 隊列，與SP-PIFO吞吐量近似相等。

▲圖6 各隊列調度算法高優先級流吞吐量隨時間變化圖

根據上述分析，本文所設計的P4-APQ隊列調度算法針對較高優先級數據流，能夠有效降低排隊時延及其抖動，同時提供穩定的吞吐量。

3 結束語

算力網絡作為中國率先提出的新型網絡架構，是推動信息產業發展、支撐“十四五”發展規劃中“網絡強國”發展戰略的重要基礎。針對算力網絡的低時延傳輸需求，本文提出了多路徑時敏優先調度機制，設計了基于強化學習的多路徑低時延轉發調度算法，根據網絡實時狀態，動態選取低時延傳輸路徑，并在轉發出端口設計了等級與隊列自適應映射算法，減少低時延應用的排隊時延。經過相關實驗測試及分析，本文所設計的多路徑時敏優先調度機制能夠在算力網絡場景下提供低時延服務保障。