基于關鍵節點的分段路由標簽棧壓縮算法

石鴻偉 黃鳳芝

（1.網絡通信與安全紫金山試驗室未來網絡研究中心 江蘇省南京市 211111）

（2.南京鐵道職業技術學院機車車輛學院 江蘇省南京市 210031)

1 引言

隨著網絡技術的不斷演進，新興的網絡業務種類越來越多，不同業務對網絡的要求不盡相同，尤其是對傳統的互聯網提出了新的挑戰。

智能化流量調度是下一代互聯網絡的關鍵能力，對業務應用質量的保障、網絡帶寬資源的優化起到非常重要的作用。現有的多協議標簽交換（MPLS, Multi-Protocol Label Switching）[1]及基于流量工程擴展的資源預留協議（RSVP-TE, Resource ReSerVation Protocol-Traffic Engineering）[2]等技術可以滿足應用對帶寬的差異化保障需求，但存在協議種類多、部署復雜、管理困難、可擴展性差等問題，無法滿足下一代互聯網絡業務動態部署、彈性擴展、靈活調度等方面的要求。

因此，國際互聯網工程任務組（IETF, The Internet Engineering Task Force）提出了的一種新型的標準化體系架構-分段路由（SR, Segment Routing）[3]。這種新型的SR 協議既能夠兼容MPLS 網絡[4]也可以兼容IPv6 網絡[5-7]，既很好的繼承了MPLS 技術的優勢，又能夠適應未來IPv6、SDN 等技術的發展[8]，為互聯網絡提供了一種高效靈活的管控手段，具有部署簡單、靈活擴展的特點，可以更好的實現流量調度和路徑優化，均衡流量分布，提高專線利用率，保障關鍵業務質量，降低線路成本。

SR 協議是基于源路由的機制。路徑描述采用在數據報文頭中插入帶順序的段列表（Segment List）以指示收到這些數據包的節點（路由器、主機或設備）如何去轉發和處理這些數據包。在基于SR 的互聯網絡中，不再需要LDP 和RSVP-TE 等信令協議，僅依賴于已經部署的路由協議（如OSPF[9]和ISIS[10]）進行擴展。互聯網服務提供商（ISP, Internet Service Provider）可以在無需額外投資的情況下，在當前生產網絡中的節點上啟用部署SR，極大降低了網絡的資本性支出（CAPEX, Capital Expenditures）和運營成本（OPEX, Operating Expense）[11]。

表1：SR 標簽分類

圖1：鄰接標簽

圖2：SR 引流方案

SR 路徑是由一系列有序的段標識符（SID, Segment Identifiers）組成。每個SID 與數據平面轉發指令相關聯，例如，沿著IGP 最短路徑進行轉發或者轉發到指定的出接口上。在SR MPLS 中，這些SID 被編碼為標簽堆棧。在流量工程中，由于需要提供差異化的服務能力，多約束條件（最短時延，最大帶寬等）被用于路徑計算。承載業務流量的轉發路徑并不一定遵循最短路徑。因此，標簽堆棧的大小與轉發路徑的長度成正比關系。

然而，當前在轉發平面數通設備上，為了達到數據報文線速轉發，廠商都是通過供專門應用的集成電路（ASIC, Application Specific Integrated Circuit）上實現的MPLS 報文轉發[12]。由于這些專用集成電路被設計成高效執行某些特定任務，因此，可執行的操作的大小和類型受到了限制，即硬件設備的最大堆棧深度（MSD, Maximum Stack Depth）。這種限制會影響到數據報文頭插入標簽堆棧的大小。一些典型的商用網絡設備當前最多只能支持3 到5 層標簽[13]。如何有效的對轉發路徑進行標簽編碼，減少標簽堆棧的大小，擴大受控網絡的規模具有至關重要的意義。

2 相關工作

目前，為了解決或降低最大堆棧深度MSD 對SR 標簽棧的限制，研究領域內有兩種主流的研究方向：標簽壓縮[14-15]和粘連標簽[16-17]。標簽壓縮是指在不影響轉發路徑表達的前提下降低標簽堆棧的深度。粘連標簽是指在標簽堆棧中加入一種可擴展的特殊標簽，該標簽到達轉發設備后，根據映射規則，被重新替換為多個有序SR標簽，重新壓入數據包的報文頭中，繼續轉發。不過，即便使用粘連標簽技術，在粘連之前先通過標簽壓縮技術降低標簽棧的總深度也是很有必要的。因此，本文重點在標簽壓縮方向進行深入研究。

為了解決標簽壓縮方法計算量大、壓縮效率不高等問題，本文提出了一種基于關鍵節點的標簽棧壓縮算法（LSC-K, Label Stack Compression based on Key-node），根據網絡節點間的互連意圖，通過分析網絡組網拓撲關系，識別關鍵網絡節點，結合分段路由松散路徑原理，消減轉發路徑上無效的節點數量，實現標簽堆棧的壓縮。

3 Segment Routing技術分析

在廣域網場景中，MPLS 技術已經得到了大規模的部署。隨著社會的發展，ISP 服務提供商、OTT（Over The Top）業務商、大型企業等迫切需要廣域網能夠提供租戶隔離、差異化的流量調度等網絡服務能力。因此，LDP、RSVP-TE 等協議也得到了廣泛應用部署。但這種解決方案的問題也逐漸暴露出來。

MPLS 網絡的控制面技術主要依賴LDP 和RSVP-TE。首先LDP 沒有流量工程機制，無法按需指定轉發路徑，也無法基于業務（時延、帶寬、丟包等）進行流量調度。因此需要通過疊加RSVPTE 實現流量工程。但是RSVP 信令非常復雜，每個節點都需要維護一個龐大的鏈路信息數據庫。由于RSVP-TE 要求節點之間構建Full-mesh 隧道，在大規模部署時，擴展性受到了限制。另外RSVP-TE 隧道不支持等價多路徑（Equal-Cost Multipath Routing，ECMP），無法滿足現代IP 網絡的需求。

因此，被業內稱為下一代MPLS技術的Segment Routing出現了。SR 技術源于MPLS，但是又對MPLS 進行了革命式的創新，它是一種全新的網絡思維，即業務驅動網絡。通過源路由機制，將業務邏輯進行按需編排，封裝到數據報文頭部，在MPLS 網絡中，根據編排后的SR 標簽堆棧指導數據報文進行轉發。因SR 與SDN 技術天然結合的特性，也逐漸成為SDN 網絡架構的一個重要技術應用。

SR 技術從被設計之初就堅持了對網絡協議做減法的原則。首先，裁剪掉了RSVP 復雜的信令機制。通過SDN 集中式控制思想和源路由機制，很好的解決了信令交互帶來的復雜性。其次，裁剪掉了LDP 標簽分發機制，直接通過網絡中已部署的IGP 協議進行分發和同步標簽信息。例如IS-IS 協議是通過TLV 實現，OSPF 協議通過不透明LSA 實現。如果網絡中引入SDN 控制器，分發和同步標簽信息的工作也可以由控制器完成。

圖3：標簽棧深大小

圖4：接口調用響應時間

SR 標簽主要分三類，具體參見表1。

Prefix SID：前綴標簽，是為目的地址前綴分配的標簽，標簽在整個SR 域內全局唯一，標識的方式為SRGB+Index，其中SRGB（Segment Routing Global Block）為分段路由全局塊。例如，如果SRGB 從16000 起始，10.0.0.0/24 網段被分配的Index 為1，那么10.0.0.0/24 的Prefix-SID 為16001。

Node SID：節點標簽，可以理解為一種特殊的Prefix-SID。例如，將設備Loopback 接口下配置的IP 地址作為前綴，其對應的 Prefix SID 實際就是Node SID。

Adjacency SID：鄰接標簽，表示轉發設備上某條鏈路的單跳路徑，僅在設備本地有效。如圖1 所示，9001、9002、9003 分別表示的是為每條鏈路分配的鄰接標簽。

根據以上的標簽分類原則，SR-TE 轉發路徑也可以分兩類。

松散路徑（Loose Explicit）：利用Prefix/Node SID 的組合，結合使用IGP 算路，可以在網絡中形成多條轉發路徑。

嚴格路徑（Strict Explicit）：當需要對流量進行精細化調度時，使用Adjacency SID，可以唯一指定一條顯式路徑。

具體的SR 引流方案如圖2 所示。

（1）SDN 控制器通過BGPLS 協議收集全網的拓撲信息、鏈路狀態信息，并分配SR 標簽利用Netconf 協議下發到設備上。

（2）當存在10.0.1.0/24 和10.0.2.0/24 互訪需求時，網絡中會有非常多的轉發路徑，比如ABCF，ADEF，ABCEF 等。如果不需要對流量做調度，按照默認的多路徑轉發即可。

（3）如果應用對網絡提出了SLA 要求，比如需要一條帶寬大于10M，延時少于30ms 的轉發路徑。

（4）SDN 控制器根據已經掌握的全網拓撲信息、狀態信息、標簽信息，計算出符合條件的顯式路徑，通過Netconf 下發到源節點A 上，轉發路徑為ABCF。

（5）當鏈路CF 出現流量擁塞，SDN 控制器感知到后，重新計算滿足業務需求的路徑，將轉發路徑下發到源節點A 上，轉發路徑為ABCEF。

根據以上的分析和舉例，可以看到，在網絡節點不多，鏈路不復雜的情況下，SR 標簽堆棧已經被用掉5 個了。如果在廣域大規模組網的情況下，由于MSD 的限制，是很難做到大網級滿足業務要求的精細化流量調度。

4 LSC-K算法設計

4.1 設計思路

詳細分析圖2 中的網絡拓撲，從源節點A 到目的節點F 的轉發路徑中，對于B 節點，無論如何計算路徑，經過B 節點的轉發路徑是唯一確定的，因此該節點是可以被壓縮的，本文把這種節點叫做互連節點。對于C 節點，由于業務意圖的不同，網絡拓撲的變化，經過C 節點的Adjacency SID 存在不同選擇，本文把這種節點叫做關鍵節點。

因此，在大規模網絡組網中，合理選擇關鍵節點，在關鍵節點之間確定唯一的轉發路徑，可極大壓縮互連節點上的Node SID，最終實現減少轉發路徑節點數量，達到標簽堆棧壓縮的目標。

本文的求解MSD 問題可以歸納為，如何根據網絡組網情況，結合源目的節點互聯需求，合理確定網絡拓撲中的關鍵節點，有效壓縮轉發路徑上互連節點的問題。

4.2 算法描述

首先，給出算法中的相關定義。

轉發路徑：aij表示從節點i 到節點j 的路徑描述。路徑描述內容包括轉發路徑的跳數nij，以及轉發路徑節點列表PathListij，由于兩點之間可能存在多條轉發路徑，因此，它是一個二維列表。

互連節點：兩個網絡節點直接互連，路徑跳數nij為1，這兩個網絡節點互為互聯節點。

關鍵節點：節點i 的互連節點個數大于2 時，該節點為關鍵節點。

分支節點：當兩點之間存在多條等價多路徑的時候，選擇其中一條路徑上的首個節點作為分支節點。

路徑矩陣：由 m × m 個轉發路徑aij排成的m 行m 列的數表。其中，m 表示網絡拓撲節點個數。由于轉發路徑的無向性，因此，路徑矩陣也是對稱矩陣。

Dijkstra 算法：Dijkstra 算法使用了廣度優先搜索解決賦權有向圖或者無向圖的單源最短路徑問題，算法最終得到一個最短路徑樹。

4.2.1 步驟一：確定關鍵節點

根據網絡拓撲初始化路徑矩陣，其中到自己的路徑跳數nii設置為0，節點i 到互連節點j 的路徑跳數nij設置為1，節點i 到非互連節點j 的路徑跳數nij設置為*。

分別計算節點i 的互連節點個數Mi。

當Mi大于2 時，確定為節點i 為關鍵節點，并插入到關鍵節點列表KeynodeList 中。如果Mi都不大于2，則跳轉到步驟四，處理沒有關鍵節點的情況。

4.2.2 步驟二：更新關鍵節點之間的轉發路徑

（1）遍歷KeynodeList，根據Dijkstra 算法，分別計算關鍵節點之間的轉發路徑aij{nij，PathListij}。

（2）如果PathListij只有一條路徑鏈表，繼續后續處理流程。

（3）如果PathListij有多條路徑鏈表，選取路徑跳數nij最小那條轉發路徑，如果跳數相同，隨機選一條路徑。并設置該路徑上首節點為分支節點。

（4）確定好轉發路徑后，進行剪枝操作，遍歷該路徑上的所有節點（除了源、目的節點），如果該節點為關鍵節點或分支節點，則保留，否則剪枝。

（5）根據剪枝結果，更新轉發路徑aij{nij, PathListij}。

4.2.3 步驟三：更新其他節點之間的轉發路徑

（1）查找源節點i 直連的關鍵節點KeynodeListi

1.如果源節點是關鍵節點，繼續后續處理流程。

2.如果源節點非關鍵節點，通過路徑矩陣中，遍歷查找所有節點i 的互連節點是否為關鍵節點，如果是，插入KeynodeListi中，如果沒有找到，遍歷所有互連節點，迭代查找關鍵節點，直到找到所有距離節點i 最近的關鍵節點。

（2）查找目的節點j 直連的關鍵節點KeynodeListj

1.如果目的節點是關鍵節點，繼續后續處理流程。

2.如果目的節點非關鍵節點，通過路徑矩陣中，遍歷查找所有節點j 的互連節點是否為關鍵節點，如果是，插入KeynodeListj中，如果沒有找到，遍歷所有互連節點，迭代查找關鍵節點，直到找到所有距離節點j 最近的關鍵節點。

（3）確定KeynodeListi與KeynodeListj之間轉發路徑

1.判斷KeynodeListi和KeynodeListj中，是否有相同的關鍵節點。

2.如果存在，節點之間的路徑鏈表PathListij為{節點i，Keynode，節點j}。

3.如果不存在，從源節點列表KeynodeListi中，選擇一個節點o，在目的節點列表KeynodeListj中，選擇一個節點p，根據步驟二關鍵節點之間的轉發路徑結果，找到節點o 和節點p 之間的路徑鏈表PathListop，得到PathListij為{節點i，PathListop，節點j}。以此類推，迭代遍歷KeynodeListi和KeynodeListj中所有的節點。選取路徑跳數nij最小那條路徑鏈表。

4.2.4 步驟四：處理沒有關鍵節點的場景

當拓撲中沒有關鍵節點，該拓撲只有兩種情況：線狀拓撲或者環狀拓撲。

如果是線狀拓撲，任意兩點之間路徑鏈表PathListij為{節點i，節點j}。

如果是環狀拓撲，采用Dijkstra 算法計算出任意兩點之間路徑鏈表PathListij為{節點i，節點k，……，節點m，節點j}，設置節點k 為分支節點，最終節點i 和節點j 之間的路徑鏈表PathListij為{節點i，節點k，節點j}。

5 實驗驗證及分析

一個高效的路徑壓縮算法可以從有效性和服務質量兩個方面進行評價。有效性指的是衡量該算法對標簽轉發路徑進行壓縮的效果。服務質量指的是業務調用該算法進行路徑計算請求的時間。

本文使用JAVA 語言編寫網絡仿真軟件進行測試驗證，分別從不同源目節點的路徑棧深以及算路查詢效率兩個方面，將Dijkstra算法和LSC-K 算法進行對比，得出結論。

實驗平臺的硬件環境為Intel? Core TM，且有四個3.6GHz 的內核CPU，支持八線程并行，內存為16GB 的X86 服務器，運行Windows 10 專業版（x64）的操作系統。

5.1 不同源目節點的路徑棧深

實驗拓撲采用未來網絡試驗設施CENI 項目進行建模，該項目覆蓋全國40 個核心節點，133 個邊緣節點，隨機選擇不同源目節點進行30 次采樣，對比不同算法的路徑棧深情況，判斷路徑壓縮算法的有效性，如圖3 所示。

從圖中可以看出，當隨機選擇源目節點進行路徑計算時，由于Dijkstra 算法是基于最短路徑算路，受所選擇源目節點的物理位置影響，路徑棧深在4 ～7 跳不規則波動，而采用LSC-K 算法，通過拓撲分析，智能選擇關鍵節點，進行轉發節點壓縮，路徑棧深被有效的壓縮到3 ～4 跳，而且受節點物理位置影響小，可以達到很好的壓縮效果。

5.2 算路查詢效率

隨著萬物互聯的時代到來，越來越多的業務用戶對網絡服務質量提出更高的要求。路徑計算是最基本的需求。除了算路結果的有效性外，快速響應算路查詢請求，能夠極大提升用戶的使用體驗。因此，根據30 次算路的API 接口響應時間進行對比，判斷算路算法的查詢效率，如圖4 所示。

通過對比，發現使用Dijkstra 算法時，每次算法查詢請求都需要重新計算，由于受到服務器性能、轉發路徑差異等因素影響，接口調用響應時間上下波動較大。而采用LSC-K 算法時，由于該算法會提前構建路徑矩陣，因此在響應算路請求時，只需從內存中，將算好的路徑結果直接進行查找反饋，不受外部環境影響，非常平穩，且基本都在1ms 左右。

6 結束語

本文針對分段路由（Segment Routing）網絡中，在進行路徑計算時，針對所存在最大棧深（MSD）的問題進行了分析和改進，提出了基于關鍵節點的標簽棧壓縮算法（LSC-K 算法）。該算法通過分析網絡拓撲關系，識別關鍵網絡節點，結合分段路由松散路徑原理，消減轉發路徑上無效的轉發節點數量，實現標簽堆棧的壓縮。同時，利用快速構建路徑矩陣的方式，極大縮小算路查詢請求的時間。實驗結果表明，LSC-K 算法可以有效的壓縮標簽堆棧大小，提高網絡服務的質量，擴大受控網絡的規模，提高網絡資源的利用率，滿足未來網絡業務的需求。