基于關(guān)鍵節(jié)點的分段路由標(biāo)簽棧壓縮算法

石鴻偉 黃鳳芝

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

（2.南京鐵道職業(yè)技術(shù)學(xué)院機車車輛學(xué)院 江蘇省南京市 210031)

1 引言

隨著網(wǎng)絡(luò)技術(shù)的不斷演進，新興的網(wǎng)絡(luò)業(yè)務(wù)種類越來越多，不同業(yè)務(wù)對網(wǎng)絡(luò)的要求不盡相同，尤其是對傳統(tǒng)的互聯(lián)網(wǎng)提出了新的挑戰(zhàn)。

智能化流量調(diào)度是下一代互聯(lián)網(wǎng)絡(luò)的關(guān)鍵能力，對業(yè)務(wù)應(yīng)用質(zhì)量的保障、網(wǎng)絡(luò)帶寬資源的優(yōu)化起到非常重要的作用。現(xiàn)有的多協(xié)議標(biāo)簽交換（MPLS, Multi-Protocol Label Switching）[1]及基于流量工程擴展的資源預(yù)留協(xié)議（RSVP-TE, Resource ReSerVation Protocol-Traffic Engineering）[2]等技術(shù)可以滿足應(yīng)用對帶寬的差異化保障需求，但存在協(xié)議種類多、部署復(fù)雜、管理困難、可擴展性差等問題，無法滿足下一代互聯(lián)網(wǎng)絡(luò)業(yè)務(wù)動態(tài)部署、彈性擴展、靈活調(diào)度等方面的要求。

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

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

表1：SR 標(biāo)簽分類

圖1：鄰接標(biāo)簽

圖2：SR 引流方案

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

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

2 相關(guān)工作

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

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

3 Segment Routing技術(shù)分析

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

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

因此，被業(yè)內(nèi)稱為下一代MPLS技術(shù)的Segment Routing出現(xiàn)了。SR 技術(shù)源于MPLS，但是又對MPLS 進行了革命式的創(chuàng)新，它是一種全新的網(wǎng)絡(luò)思維，即業(yè)務(wù)驅(qū)動網(wǎng)絡(luò)。通過源路由機制，將業(yè)務(wù)邏輯進行按需編排，封裝到數(shù)據(jù)報文頭部，在MPLS 網(wǎng)絡(luò)中，根據(jù)編排后的SR 標(biāo)簽堆棧指導(dǎo)數(shù)據(jù)報文進行轉(zhuǎn)發(fā)。因SR 與SDN 技術(shù)天然結(jié)合的特性，也逐漸成為SDN 網(wǎng)絡(luò)架構(gòu)的一個重要技術(shù)應(yīng)用。

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

圖3：標(biāo)簽棧深大小

圖4：接口調(diào)用響應(yīng)時間

SR 標(biāo)簽主要分三類，具體參見表1。

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

Node SID：節(jié)點標(biāo)簽，可以理解為一種特殊的Prefix-SID。例如，將設(shè)備Loopback 接口下配置的IP 地址作為前綴，其對應(yīng)的 Prefix SID 實際就是Node SID。

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

根據(jù)以上的標(biāo)簽分類原則，SR-TE 轉(zhuǎn)發(fā)路徑也可以分兩類。

松散路徑（Loose Explicit）：利用Prefix/Node SID 的組合，結(jié)合使用IGP 算路，可以在網(wǎng)絡(luò)中形成多條轉(zhuǎn)發(fā)路徑。

嚴(yán)格路徑（Strict Explicit）：當(dāng)需要對流量進行精細化調(diào)度時，使用Adjacency SID，可以唯一指定一條顯式路徑。

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

（1）SDN 控制器通過BGPLS 協(xié)議收集全網(wǎng)的拓撲信息、鏈路狀態(tài)信息，并分配SR 標(biāo)簽利用Netconf 協(xié)議下發(fā)到設(shè)備上。

（2）當(dāng)存在10.0.1.0/24 和10.0.2.0/24 互訪需求時，網(wǎng)絡(luò)中會有非常多的轉(zhuǎn)發(fā)路徑，比如ABCF，ADEF，ABCEF 等。如果不需要對流量做調(diào)度，按照默認的多路徑轉(zhuǎn)發(fā)即可。

（3）如果應(yīng)用對網(wǎng)絡(luò)提出了SLA 要求，比如需要一條帶寬大于10M，延時少于30ms 的轉(zhuǎn)發(fā)路徑。

（4）SDN 控制器根據(jù)已經(jīng)掌握的全網(wǎng)拓撲信息、狀態(tài)信息、標(biāo)簽信息，計算出符合條件的顯式路徑，通過Netconf 下發(fā)到源節(jié)點A 上，轉(zhuǎn)發(fā)路徑為ABCF。

（5）當(dāng)鏈路CF 出現(xiàn)流量擁塞，SDN 控制器感知到后，重新計算滿足業(yè)務(wù)需求的路徑，將轉(zhuǎn)發(fā)路徑下發(fā)到源節(jié)點A 上，轉(zhuǎn)發(fā)路徑為ABCEF。

根據(jù)以上的分析和舉例，可以看到，在網(wǎng)絡(luò)節(jié)點不多，鏈路不復(fù)雜的情況下，SR 標(biāo)簽堆棧已經(jīng)被用掉5 個了。如果在廣域大規(guī)模組網(wǎng)的情況下，由于MSD 的限制，是很難做到大網(wǎng)級滿足業(yè)務(wù)要求的精細化流量調(diào)度。

4 LSC-K算法設(shè)計

4.1 設(shè)計思路

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

因此，在大規(guī)模網(wǎng)絡(luò)組網(wǎng)中，合理選擇關(guān)鍵節(jié)點，在關(guān)鍵節(jié)點之間確定唯一的轉(zhuǎn)發(fā)路徑，可極大壓縮互連節(jié)點上的Node SID，最終實現(xiàn)減少轉(zhuǎn)發(fā)路徑節(jié)點數(shù)量，達到標(biāo)簽堆棧壓縮的目標(biāo)。

本文的求解MSD 問題可以歸納為，如何根據(jù)網(wǎng)絡(luò)組網(wǎng)情況，結(jié)合源目的節(jié)點互聯(lián)需求，合理確定網(wǎng)絡(luò)拓撲中的關(guān)鍵節(jié)點，有效壓縮轉(zhuǎn)發(fā)路徑上互連節(jié)點的問題。

4.2 算法描述

首先，給出算法中的相關(guān)定義。

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

互連節(jié)點：兩個網(wǎng)絡(luò)節(jié)點直接互連，路徑跳數(shù)nij為1，這兩個網(wǎng)絡(luò)節(jié)點互為互聯(lián)節(jié)點。

關(guān)鍵節(jié)點：節(jié)點i 的互連節(jié)點個數(shù)大于2 時，該節(jié)點為關(guān)鍵節(jié)點。

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

路徑矩陣：由 m × m 個轉(zhuǎn)發(fā)路徑aij排成的m 行m 列的數(shù)表。其中，m 表示網(wǎng)絡(luò)拓撲節(jié)點個數(shù)。由于轉(zhuǎn)發(fā)路徑的無向性，因此，路徑矩陣也是對稱矩陣。

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

4.2.1 步驟一：確定關(guān)鍵節(jié)點

根據(jù)網(wǎng)絡(luò)拓撲初始化路徑矩陣，其中到自己的路徑跳數(shù)nii設(shè)置為0，節(jié)點i 到互連節(jié)點j 的路徑跳數(shù)nij設(shè)置為1，節(jié)點i 到非互連節(jié)點j 的路徑跳數(shù)nij設(shè)置為*。

分別計算節(jié)點i 的互連節(jié)點個數(shù)Mi。

當(dāng)Mi大于2 時，確定為節(jié)點i 為關(guān)鍵節(jié)點，并插入到關(guān)鍵節(jié)點列表KeynodeList 中。如果Mi都不大于2，則跳轉(zhuǎn)到步驟四，處理沒有關(guān)鍵節(jié)點的情況。

4.2.2 步驟二：更新關(guān)鍵節(jié)點之間的轉(zhuǎn)發(fā)路徑

（1）遍歷KeynodeList，根據(jù)Dijkstra 算法，分別計算關(guān)鍵節(jié)點之間的轉(zhuǎn)發(fā)路徑aij{nij，PathListij}。

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

（3）如果PathListij有多條路徑鏈表，選取路徑跳數(shù)nij最小那條轉(zhuǎn)發(fā)路徑，如果跳數(shù)相同，隨機選一條路徑。并設(shè)置該路徑上首節(jié)點為分支節(jié)點。

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

（5）根據(jù)剪枝結(jié)果，更新轉(zhuǎn)發(fā)路徑aij{nij, PathListij}。

4.2.3 步驟三：更新其他節(jié)點之間的轉(zhuǎn)發(fā)路徑

（1）查找源節(jié)點i 直連的關(guān)鍵節(jié)點KeynodeListi

1.如果源節(jié)點是關(guān)鍵節(jié)點，繼續(xù)后續(xù)處理流程。

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

（2）查找目的節(jié)點j 直連的關(guān)鍵節(jié)點KeynodeListj

1.如果目的節(jié)點是關(guān)鍵節(jié)點，繼續(xù)后續(xù)處理流程。

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

（3）確定KeynodeListi與KeynodeListj之間轉(zhuǎn)發(fā)路徑

1.判斷KeynodeListi和KeynodeListj中，是否有相同的關(guān)鍵節(jié)點。

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

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

4.2.4 步驟四：處理沒有關(guān)鍵節(jié)點的場景

當(dāng)拓撲中沒有關(guān)鍵節(jié)點，該拓撲只有兩種情況：線狀拓撲或者環(huán)狀拓撲。

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

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

5 實驗驗證及分析

一個高效的路徑壓縮算法可以從有效性和服務(wù)質(zhì)量兩個方面進行評價。有效性指的是衡量該算法對標(biāo)簽轉(zhuǎn)發(fā)路徑進行壓縮的效果。服務(wù)質(zhì)量指的是業(yè)務(wù)調(diào)用該算法進行路徑計算請求的時間。

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

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

5.1 不同源目節(jié)點的路徑棧深

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

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

5.2 算路查詢效率

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

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

6 結(jié)束語

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