基于分段路由技術(shù)的量子密鑰分發(fā)網(wǎng)絡(luò)路由方案研究*

池亞平 程崢華 張亮亮

1. 北京電子科技學(xué)院，北京市 100070

2. 中國科學(xué)技術(shù)大學(xué)，合肥市 230027

3. 西安電子科技大學(xué)，西安市 710071

0 引言

量子保密通信技術(shù)是一種利用量子力學(xué)原理實現(xiàn)量子密鑰分發(fā)（Quantum Key Distribution，QKD）［1］的通信技術(shù)。 近年來，隨著QKD 技術(shù)的不斷發(fā)展，量子保密通信從理論研究逐步走向應(yīng)用，量子通信也已經(jīng)從點到點的小型專用通信系統(tǒng)發(fā)展到面向?qū)嶋H應(yīng)用的量子保密通信網(wǎng)絡(luò)［2］［3］。 在構(gòu)建更大規(guī)模QKD 網(wǎng)絡(luò)中，路由算法與路由策略控制成為量子保密通信網(wǎng)絡(luò)研究領(lǐng)域的研究熱點之一。

目前國內(nèi)外對QKD 網(wǎng)絡(luò)的路由方案研究較少，并且現(xiàn)有QKD 網(wǎng)絡(luò)路由方案普遍采用經(jīng)典網(wǎng)絡(luò)路由算法——開放式最短路徑優(yōu)先（Open Shortest Path First，OSPF）。 其網(wǎng)絡(luò)狀態(tài)參數(shù)基本包含剩余密鑰量、密鑰生成速率和跳數(shù)等，對于量子密鑰資源的負載均衡大多采用動態(tài)路由設(shè)計思想，如文獻［4］針對分布式可信中繼QKD網(wǎng)絡(luò)中的路由問題，提出一種動態(tài)路由方案，但分布式網(wǎng)絡(luò)環(huán)境下每個節(jié)點只能獲取鄰接節(jié)點的信息，實現(xiàn)的是局部最優(yōu)，可能導(dǎo)致所選的中繼路徑非全局相對最優(yōu)相對最短，并不能滿足QKD 網(wǎng)絡(luò)中有效利用量子密鑰資源的需求。

軟件定義網(wǎng)絡(luò)（Software Defined Networking，SDN）［5］是新一代網(wǎng)絡(luò)架構(gòu)，核心在于實現(xiàn)控制平面與數(shù)據(jù)平面分離，控制器平面可以中心化地管控網(wǎng)絡(luò)資源，包括綜合感知量子保密通信網(wǎng)絡(luò)密鑰資源狀態(tài)，統(tǒng)籌調(diào)度全網(wǎng)的量子密鑰資源，實現(xiàn)密鑰資源的平衡和有效利用。 如文獻［6］設(shè)計了一種基于SDN 的量子保密通信網(wǎng)絡(luò)架構(gòu)模型，提出了一種以跳數(shù)和鏈路密鑰為權(quán)重度量的、基于SDN 的動態(tài)路由算法，實現(xiàn)了密鑰資源的有效利用和負載均衡。

但是，在這種基于SDN 架構(gòu)的集中式QKD網(wǎng)絡(luò)中，SDN 控制器與中繼路徑上的每一節(jié)點交互。 隨著共享密鑰服務(wù)請求的增加，控制器負載逐步增大，同時節(jié)點交換機的流表開銷也會隨之加重，造成流表下發(fā)和流表更新不及時等問題，共享密鑰服務(wù)仍按照之前中繼路徑進行轉(zhuǎn)發(fā)，無法及時有效地調(diào)度，甚至可能導(dǎo)致某一鏈路密鑰資源的消耗殆盡，進而中繼傳輸中止，共享密鑰服務(wù)失敗，量子密鑰資源被嚴重浪費。

分段路由（Segment Routing，SR）［7］［8］［9］技術(shù)可有效解決上述問題。 這一技術(shù)基于源路由機制，可借助SDN 集中控制的特點，通過改進型路由算法實現(xiàn)流量負載均衡、降低流表資源開銷［10］。 文獻［11］采用分段路由轉(zhuǎn)發(fā)技術(shù)，結(jié)合SDN 結(jié)構(gòu)，提出了一種基于受限K 最短路徑（Constrained K-Shortest Pathes，CKSP）算法。 該算法采用分段路由技術(shù)進行負載均衡，在K 條最短路徑中計算一條同時滿足預(yù)期網(wǎng)路最大流和最小化鏈路利用率方差的最優(yōu)路徑，增大了網(wǎng)絡(luò)吞吐量，平滑了流量分布，并降低了網(wǎng)絡(luò)總丟包率。 文獻［12］針對當前SDN 網(wǎng)絡(luò)在應(yīng)對大量數(shù)據(jù)流時造成的流表利用率低，轉(zhuǎn)發(fā)響應(yīng)較慢以及當前網(wǎng)絡(luò)調(diào)度算法容易造成網(wǎng)絡(luò)局部擁塞和負載不均衡等問題，提出了一種基于分段路由的多路徑調(diào)度算法SRMF，該文獻通過實驗驗證了分段路由轉(zhuǎn)發(fā)技術(shù)在多種網(wǎng)絡(luò)拓撲下較一般轉(zhuǎn)發(fā)技術(shù)在流表項開銷方面有明顯優(yōu)勢。

本文在研究SDN 和分段路由技術(shù)相關(guān)研究成果的基礎(chǔ)上，針對可信中繼QKD 網(wǎng)絡(luò)的路由優(yōu)化問題，綜合應(yīng)用SDN 的全局控制優(yōu)勢和分段路由源路由特點，提出一種可應(yīng)用于QKD 網(wǎng)絡(luò)的路由選擇方案，實現(xiàn)量子密鑰資源的均衡利用問題。

1 相關(guān)技術(shù)基礎(chǔ)

1.1 可信中繼原理

目前將點對點QKD 網(wǎng)絡(luò)擴展為多用戶QKD 網(wǎng)絡(luò)的組網(wǎng)方式有三種：光交換／分束器方案、量子中繼方案和可信中繼方案［13］。 光交換／分束器方案利用光路交換機或光分束器，實現(xiàn)多用戶QKD 鏈路切換，從而實現(xiàn)多用戶間的密鑰分發(fā)，但由于量子信號衰減帶來的傳輸距離限制，該方式無法進行遠距離傳輸，所以不適用于大規(guī)模的組網(wǎng)。 量子中繼方案利用量子糾纏原理實現(xiàn)量子態(tài)的存儲和轉(zhuǎn)發(fā)，理論上可以實現(xiàn)遠距離的密鑰分發(fā)，但目前該方案需要的量子存儲器或量子糾錯技術(shù)仍不成熟，暫未達到實用的程度。 可信中繼方案通過將多個點對點的QKD 鏈路連接起來以實現(xiàn)端到端的密鑰分發(fā)，從而實現(xiàn)遠距離的密鑰分發(fā)，是目前全球QKD 網(wǎng)絡(luò)中廣泛采用的使用解決方案。

本文面向可信中繼QKD 網(wǎng)絡(luò)研究路由方案，基于可信中繼的QKD 網(wǎng)絡(luò)基本思想是利用一次一密算法（One-Time Pad，OTP）［14］［15］實現(xiàn)非相鄰節(jié)點間密鑰的傳遞，并將得到的共享密鑰分發(fā)給用戶，這個過程稱為“逐跳”加密機制，圖1 顯示了使用這一機制在兩個用戶之間交換密鑰的基本原理。

圖1 密鑰中繼原理圖

如圖1 所示，假設(shè)兩個鄰近節(jié)點QKD 系統(tǒng)生成的共享密鑰為Ki，此時Alice 想將生成的量子密鑰傳遞給Bob，實現(xiàn)遠距離密鑰共享，其密鑰中繼路徑為Alice—＞node（1）—＞node（2）—＞…—＞node（i） —＞…—＞Bob，中繼步驟如下：

（1）Alice 與node（1）基于BB84 等量子密鑰分發(fā)協(xié)議生成共享量子密鑰KA；

（2）node（1）使用OTP 算法將K1作為KA的保護密鑰，加密傳遞給node（2）；

（3）node（2）用共享密鑰K1對收到的KA⊕K1進行異或解密，得到KA；

（4）然后重復(fù)步驟（2）（3），將KA加密并傳遞給下一個節(jié)點進行解密，直到Bob 得到KA后，整個過程結(jié)束。 至此Alice 和Bob 都獲得了量子密鑰KA。

基于可信中繼的QKD 網(wǎng)絡(luò)由量子密鑰生產(chǎn)層不斷為相鄰節(jié)點生成量子密鑰，再以密鑰中繼的方式，為任意網(wǎng)絡(luò)節(jié)點提供共享密鑰，因此在選擇密鑰中繼路徑時，應(yīng)選擇路徑長度短的中繼路徑避免無意義密鑰消耗。

1.2 分段路由技術(shù)原理

分段路由技術(shù)由源節(jié)點為網(wǎng)絡(luò)中的數(shù)據(jù)包指定路徑，并通過特定算法將業(yè)務(wù)路徑編碼成一個有序的段（Segment）列表封裝到數(shù)據(jù)包首部來顯式標識路徑，中間節(jié)點只負責快速的數(shù)據(jù)轉(zhuǎn)發(fā)。 分段路由與SDN 結(jié)合，使用MPLS 標簽棧來存儲分段路由中一條數(shù)據(jù)轉(zhuǎn)發(fā)路徑的段列表，其工作機制如下：

在源交換機將路徑Segment 列表以MPLS標簽棧壓入到數(shù)據(jù)包首部，根據(jù)各節(jié)點標簽轉(zhuǎn)發(fā)流表項匹配棧頂標簽和標簽出棧，最終將數(shù)據(jù)包送至目的交換機。 中間節(jié)點不必為所有可能經(jīng)過它們的流維持狀態(tài)信息，所有的狀態(tài)信息以標簽棧的形式存在于數(shù)據(jù)包中。

（1） 網(wǎng)絡(luò)初始化階段，SDN 控制器通過LLDP（Link Layer Discovery Protocol，鏈路發(fā)現(xiàn)協(xié)議）協(xié)議進行鏈路發(fā)現(xiàn)，根據(jù)這一協(xié)議搜集的信息確定和管理網(wǎng)絡(luò)拓撲結(jié)構(gòu)，為各節(jié)點分配全局分段路由標簽Node SID。 將這一網(wǎng)絡(luò)拓撲結(jié)構(gòu)抽象為有向圖鄰接關(guān)系，確定各網(wǎng)絡(luò)節(jié)點的標簽轉(zhuǎn)發(fā)表。

（2）當一數(shù)據(jù)流到達時，由于沒有流表匹配，觸發(fā)PACKET＿IN 進入控制器，控制器為數(shù)據(jù)流計算出一條路徑，進而將這條路徑轉(zhuǎn)換成由全局路由標簽SID 組成的標簽棧，下發(fā)至源交換機，數(shù)據(jù)流匹配該流表項并被打上對應(yīng)標簽，后續(xù)傳輸通過匹配標簽轉(zhuǎn)發(fā)表轉(zhuǎn)發(fā)，直到恢復(fù)為IP 數(shù)據(jù)包到達目的交換機。

如圖2 所示，網(wǎng)絡(luò)初始化時，SDN 控制器會給每一個交換節(jié)點分配全局路由標簽SID。 h1到h2 的數(shù)據(jù)包PKT 由SDN 控制器計算得到轉(zhuǎn)發(fā)路徑為P（S1—＞S2—＞S3—＞S5—＞S6），然后源節(jié)點S1 將P 這條路徑通過段列表的形式封裝到數(shù)據(jù)包PKT 頭部，即標簽106、105、103、102入棧。 在節(jié)點S1 處，開始依次匹配交換機節(jié)點的標簽轉(zhuǎn)發(fā)表進行轉(zhuǎn)發(fā)，如PKT 在S1 處根據(jù)棧頂標簽102 查詢到其對應(yīng)標簽轉(zhuǎn)發(fā)表為（102 pop， out 2），將其PKT 的102 標簽彈出轉(zhuǎn)發(fā)至S2，數(shù)據(jù)包PKT 到達S2，再根據(jù)棧頂標簽103 查詢其對應(yīng)標簽轉(zhuǎn)發(fā)表項為（103 pop， out 2），同樣將其PKT 的103 標簽彈出再進行轉(zhuǎn)發(fā)至S3，后續(xù)交換節(jié)點的匹配轉(zhuǎn)發(fā)操作同樣按此過程進行，直至PKT 到達目的節(jié)點S6，數(shù)據(jù)包的轉(zhuǎn)發(fā)過程結(jié)束。

圖2 分段路由轉(zhuǎn)發(fā)過程

2 基于分段路由的密鑰分發(fā)網(wǎng)絡(luò)架構(gòu)模型

本文所提出的網(wǎng)絡(luò)架構(gòu)運用于量子密鑰分發(fā)網(wǎng)絡(luò)，該網(wǎng)絡(luò)的SDN 架構(gòu)由數(shù)據(jù)層、控制層及應(yīng)用層構(gòu)成，將SDN 這種技術(shù)應(yīng)用于量子密鑰分發(fā)網(wǎng)絡(luò)，其中的量子密鑰中繼層和量子密鑰交換層對應(yīng)于SDN 架構(gòu)的數(shù)據(jù)層，實現(xiàn)任意節(jié)點間的密鑰中繼以提供端到端的共享密鑰，在這里基于可信中繼的QKD 網(wǎng)絡(luò)的量子密鑰交換層不再具有路由選路功能，而是將制定路由策略的功能上交到SDN 架構(gòu)的控制層。

本文提出的軟件定義的QKD 網(wǎng)絡(luò)架構(gòu)如圖3 所示。 該網(wǎng)絡(luò)架構(gòu)包括產(chǎn)生量子密鑰的量子密鑰生成節(jié)點和具有密鑰中繼功能的量子密鑰中繼節(jié)點以及SDN＋SR 控制器三部分。 其中，控制器屬于控制層，量子密鑰中繼節(jié)點屬于數(shù)據(jù)層，量子密鑰生成節(jié)點屬于量子層。

圖3 SDN-SR 的QKD 網(wǎng)絡(luò)架構(gòu)圖

控制層是該架構(gòu)的核心部分，主要功能是通過OpenFlow 協(xié)議（一種網(wǎng)絡(luò)通信協(xié)議），主動收集數(shù)據(jù)層中各密鑰節(jié)點中儲存的密鑰池資源信息，為數(shù)據(jù)層任意網(wǎng)絡(luò)節(jié)點間密鑰的安全共享提供密鑰資源充足的密鑰中繼路徑。 本文的控制平面包括以下幾個模塊：

（1）標簽轉(zhuǎn)發(fā)表構(gòu)建模塊：根據(jù)SDN 控制器初始化階段確定的網(wǎng)絡(luò)拓撲信息，通過一級流表構(gòu)建分段路由的標簽轉(zhuǎn)發(fā)表流表項，供密鑰中繼使用。

（2）密鑰信息采集模塊：根據(jù)OFP＿PORT＿STATS＿REQUEST 和OFP＿PORT＿STATS＿REPLY消息獲取QKD 數(shù)據(jù)層存儲的量子層密鑰資源信息，將其獲取到的全網(wǎng)量子密鑰剩余量加權(quán)作為鏈路權(quán)重供路徑計算模塊使用。

（3）中繼路徑計算模塊：主要計算從源節(jié)點到目的節(jié)點的中繼路徑，并將計算得到的中繼路徑轉(zhuǎn)化為Node SID 構(gòu)成的分段路由段列表，然后將段列表以標簽壓棧流表項下發(fā)至源中繼節(jié)點或中間中繼節(jié)點。

數(shù)據(jù)層由實際的數(shù)據(jù)通信節(jié)點與經(jīng)典數(shù)據(jù)信道組成，當有密鑰交換業(yè)務(wù)時，數(shù)據(jù)層將使用量子層的點到點量子密鑰來完成共享密鑰的安全端到端中繼傳輸。

量子層主要是由量子系統(tǒng)的設(shè)備，量子鏈路與量子密鑰池構(gòu)成，相鄰節(jié)點間基于BB84、B92等量子密鑰分發(fā)協(xié)議，產(chǎn)生QKD 網(wǎng)絡(luò)密鑰資源，并將其存儲在量子密鑰池，用于實現(xiàn)數(shù)據(jù)層多用戶間密鑰的安全傳遞與共享。

SDN 控制層通過南向接口協(xié)議獲取數(shù)據(jù)層網(wǎng)絡(luò)信息，根據(jù)收集到的量子網(wǎng)絡(luò)的密鑰資源信息計算出最佳密鑰中繼路徑，再將密鑰數(shù)據(jù)包信息和轉(zhuǎn)發(fā)規(guī)則流表下發(fā)至該條密鑰中繼路徑的源節(jié)點。 在量子密鑰分發(fā)網(wǎng)絡(luò)的運用分段路由技術(shù)，控制器無需與路徑中每一節(jié)點進行交互，而只需與該路徑的源節(jié)點進行交互，對路徑進行編碼后向源節(jié)點一次下發(fā)包含所有分段標簽信息的標簽棧流表，再利用標簽操作進行這條路徑上的數(shù)據(jù)轉(zhuǎn)發(fā)工作，這樣不僅減輕了控制器的負擔，降低流表項開銷，同時分段路由可根據(jù)網(wǎng)絡(luò)每條鏈路的量子密鑰信息的約束條件進行流量調(diào)度優(yōu)化計算，若某一節(jié)點失效，可利用分段路由技術(shù)對流進行重路由，保證共享密鑰服務(wù)的成功交換，從而減少量子密鑰的多余消耗。

3 路由算法改進設(shè)計

對于目前的QKD 技術(shù)來說，量子鏈路的密鑰生成速率仍然有限且相對較低，因此量子密鑰資源非常珍貴。 然而，根據(jù)第一節(jié)中密鑰中繼的工作原理可知，當用戶間交換一定數(shù)量的共享密鑰時，中繼路徑上對應(yīng)的每條量子鏈路必須消耗等量的量子密鑰。 因此本文的工作是尋找一種實現(xiàn)任意用戶間密鑰交換的路由方案，包括尋找從請求節(jié)點到目的節(jié)點的最佳密鑰中繼路徑，再將該路徑下發(fā)至分段標簽壓棧流表項至路徑源節(jié)點。

3.1 QKD 網(wǎng)絡(luò)節(jié)點與鏈路相關(guān)定義

圖論作為一種描述事物之間特定關(guān)系的數(shù)學(xué)方法，被廣泛應(yīng)用于網(wǎng)絡(luò)化對象的研究過程中［16］。 QKD 網(wǎng)絡(luò)主要由節(jié)點之間的密鑰共享關(guān)系構(gòu)成，共享密鑰的產(chǎn)生有兩種方式：一是由量子信道直接生成共享密鑰，二是由密鑰中繼方式間接生成共享密鑰。 在本文中我們重點討論第二種方式生成的共享密鑰。

本文將QKD 網(wǎng)絡(luò)用一個二元組G ＝{V，E} 來表示，其中V ＝｛v1，v2，…，vn｝ 表示密鑰節(jié)點集，相應(yīng)的vi表示任意密鑰節(jié)點，E ＝｛eij｝ 表示密鑰鏈路集，eij表示從密鑰節(jié)點vi到密鑰節(jié)點vj之間的一條密鑰鏈路。

定義1 根據(jù)2.3 節(jié)中設(shè)計的QKD 網(wǎng)絡(luò)架構(gòu)，我們將密鑰節(jié)點從量子層和數(shù)據(jù)層分為兩類：量子密鑰生成節(jié)點qnode、密鑰中繼節(jié)點tnode，可以表示為：

3.2 路由選擇算法優(yōu)化設(shè)計

本文以Yen 算法為基礎(chǔ)，根據(jù)量子網(wǎng)絡(luò)的鏈路費用度量為多用戶間密鑰交換選擇一條密鑰量充足并保證網(wǎng)絡(luò)密鑰量均衡的密鑰中繼路徑。 Yen 算法是Jin Y.Yen 在1971 年發(fā)表的以其名字命名的算法，算法采用的是偏離路徑的思想，其利用經(jīng)典的最短路徑算法求出源－目的節(jié)點之間的最短路徑，然后依次偏離出各條最短路徑，直到第K 條為止。 這里采用經(jīng)典且廣泛應(yīng)用的最短路徑——Dijkstra 算法作為Yen 算法的基礎(chǔ)，來搜索出最短路徑。

量子網(wǎng)絡(luò)的鏈路費用度量考慮鏈路密鑰池剩余密鑰量和路由跳數(shù)，具體說明如下：

（1）鏈路密鑰池剩余密鑰量。 QKD 網(wǎng)絡(luò)中由于密鑰生成速率有限且普遍較低，鏈路密鑰資源的分布也不一致，現(xiàn)有的QKD 網(wǎng)絡(luò)研究如SECOQC 網(wǎng)絡(luò)將經(jīng)典網(wǎng)絡(luò)中的一些成熟技術(shù)直接移植到QKD 網(wǎng)絡(luò)中，網(wǎng)絡(luò)層選擇路由時沒有考慮引入本地密鑰量作為鏈路代價，導(dǎo)致一旦中繼路徑中某條鏈路密鑰量不足或者出現(xiàn)故障，從而造成路徑上其他鏈路密鑰逐漸消耗殆盡進而出現(xiàn)密鑰“塌陷式”級聯(lián)不足［16］。 所以本文考慮鏈路密鑰池剩余密鑰量作為路由選擇的重要指標，同時為了更好地平衡網(wǎng)絡(luò)中的鏈路密鑰資源，考慮為每個鏈路池設(shè)置一個閾值。 在選路時只能選擇密鑰池密鑰資源充足的鏈路，忽視鏈路密鑰池剩余密鑰量低于閾值的鏈路，以滿足中繼傳輸?shù)男枨?，提高用戶密鑰交換服務(wù)成功率。

（2）路由跳數(shù)。 由QKD 網(wǎng)絡(luò)的密鑰中繼方式可以看出，網(wǎng)絡(luò)中任意密鑰節(jié)點間需要交換密鑰時，每經(jīng)過一個密鑰中繼節(jié)點都要消耗一定的密鑰資源，當選擇的一條路徑的長度越長，即路由跳數(shù)越多，它就會消耗更加多余的密鑰資源，使得資源的利用率進一步降低。 因此，在保證所選鏈路的密鑰資源充足等前提下，應(yīng)盡量選擇鏈路數(shù)量較少的路徑作為用戶密鑰傳輸?shù)闹欣^路徑，這樣可以減少密鑰資源的無意義消耗，進而節(jié)省QKD 網(wǎng)絡(luò)的密鑰資源。

本文中的路由選擇算法為先選出K 條最優(yōu)路徑，可以表示為：

最后，中繼路徑Pbest，可以表示為：

綜上所述，路由選擇問題的數(shù)學(xué)模型可以表示為上文中的（5）（6）（7）（8）（9）（10），式（5）（6）保證了中繼鏈路密鑰量充足并均衡分布，式（7）（8）（9）保證了選取的K 條路徑的每一條路徑的鏈路剩余密鑰總量最多且鏈路密鑰量也最多，式（10）則為目標函數(shù)，即中繼路徑的權(quán)重最優(yōu)長度最短。

本文中利用動態(tài)的路由選擇實現(xiàn)量子保密通信網(wǎng)絡(luò)中密鑰資源的負載均衡，其過程如下：

第一步：控制器周期性收集量子層每條鏈路密鑰池中的密鑰剩余量，剔除QKD 鏈路中剩余密鑰量低于閾值的鏈路；

第二步：根據(jù)權(quán)重表達式（2）設(shè)置鏈路權(quán)重，以Yen 算法為基礎(chǔ)選出K 條最優(yōu)路徑；

第三步：比較這K 條路徑的路徑長度大小，選擇路由跳數(shù)最小的路徑作為最終的密鑰中繼路徑。

本文的路由選擇算法是在量子密鑰分發(fā)網(wǎng)絡(luò)下，用戶密鑰交換服務(wù)請求觸發(fā)PACKET＿IN時，計算出一條密鑰中繼路徑完成用戶密鑰交換算法。 對于密鑰中繼路徑的選擇，僅考慮路由跳數(shù)最短無法滿足多目標優(yōu)化需求，因此本文以鏈路密鑰池剩余密鑰量為度量設(shè)置鏈路權(quán)重，保證選擇的鏈路的密鑰池剩余量最多，以Yen 算法為基礎(chǔ)計算K 條密鑰中繼路徑，保證當其中一條密鑰中繼失敗時，有備選路徑可供選擇，提高用戶密鑰交換服務(wù)成功率，接著從這K 條路徑中選擇路由跳數(shù)最少的作為密鑰中繼路徑，避免鏈路密鑰的無意義消耗。 同時，本文動態(tài)進行路由選擇，與靜態(tài)路由選擇相比，保證鏈路密鑰不被消耗殆盡，同時均衡網(wǎng)絡(luò)的鏈路密鑰池密鑰資源。

3.3 路徑編碼算法設(shè)計

路徑編碼算法是區(qū)別分段路由技術(shù)與其他路由技術(shù)的關(guān)鍵，體現(xiàn)了分段路由技術(shù)的源路由轉(zhuǎn)發(fā)的特點。 目前分段路由支持MPLS 和IPv6兩種數(shù)據(jù)平面，基于MPLS 數(shù)據(jù)平面的分段路由被稱為SR-MPLS，其Segment 為MPLS 標簽；基于IPv6 轉(zhuǎn)發(fā)平面的分段路由被稱為SRv6，其Segment 為IPv6 地址。 本文所提分段路由技術(shù)則使用SR-MPLS，在采用上一節(jié)中的路由選擇算法選出最優(yōu)中繼路徑Pbest后，設(shè)計一種部署在MPLS 設(shè)備以MPLS 標簽為基礎(chǔ)（MPLS 設(shè)備通常只支持有限數(shù)量的棧標簽，稱為段列表深度）的路徑編碼算法對該條路徑進行編碼，得到該路徑最終所需的分段路由段列表。 使用的路徑編碼算法的偽代碼如下所示：

算法1 路徑編碼算法

輸入：中繼路徑節(jié)點集合Nodes， 源節(jié)點src，目的節(jié)點dst，最大棧深度MSD

輸出：段列表SL

算法首先從中繼路徑Pbest中獲得從源節(jié)點到目的節(jié)點的所有節(jié)點集，以及最大受標簽棧深度限制的MSD（Maximum Stack Depth，最大棧深度）。

步驟1 到4：從中繼節(jié)點集Nodes的第二個節(jié)點遍歷到最后一個節(jié)點，將代表每一中繼節(jié)點的標簽加入到segmentList集合；

步驟5 到10：當?shù)玫降膕egmentList集合大小最大棧深度MSD 時，將以MSD 為單位對segmentList進行多段劃分，以實現(xiàn)中繼路徑的中間節(jié)點標簽壓棧操作；

步驟11 到12：否則，不對segmentList進行多段劃分；

步驟13：得到最終的段列表SL。

經(jīng)過上述的路徑編碼算法，可得到最終的段列表。 如圖4 所示，路徑P（S1—＞S2—＞S3—＞S5—＞S6）得到的段列表SL 為｛102，103，105，106｝，受數(shù)據(jù)平面中繼節(jié)點標簽棧深度的限制（這里假設(shè)最大棧深度為2），還需要將得到的SL 進行分割得到最終SL 為｛｛102，103｝，｛105，106｝｝，接著將｛102，103｝段列表以標簽壓棧流表項形式下發(fā)給源交換機S1，｛105，106｝段列表以標簽壓棧流表項形式下發(fā)給中繼節(jié)點S3，經(jīng)過這條路徑的數(shù)據(jù)包在經(jīng)過S1 時匹配流表項被打上103，102 標簽，經(jīng)過S3 的操作也是如此。

圖4 分段路由標簽壓棧流表下發(fā)示例

完成路由選擇和路徑編碼之后，就需要使用OpenFlow 協(xié)議與交換機交互，將密鑰中繼轉(zhuǎn)發(fā)路徑的分段路由段列表，即一級標簽壓棧流表項，即匹配域為（入端口，源IP 地址，目的IP 地址，協(xié)議類型），指令集為壓入指定標簽棧，下發(fā)至數(shù)據(jù)層源節(jié)點和中間節(jié)點，源節(jié)點和中間節(jié)點將其保存在交換機流表中，如圖4 所示。 當有用戶密鑰交換服務(wù)請求時，將該服務(wù)需要的密鑰資源在源節(jié)點進行標簽壓棧，再根據(jù)各個節(jié)點初始化時構(gòu)建的標簽轉(zhuǎn)發(fā)表流表項進行標簽匹配轉(zhuǎn)發(fā)，實現(xiàn)SDN 控制、分段路由技術(shù)轉(zhuǎn)發(fā)的量子密鑰分發(fā)網(wǎng)絡(luò)。

4 實驗仿真與分析

4.1 仿真方案設(shè)計

本文實驗的SDN 控制器選擇基于Java 的開源Floodlight 控制器，實驗平臺是Ubuntu 16.04操作系統(tǒng)，Open vSwitch 2.5.7 虛擬交換機，OpenFlow 1.3 南向接口協(xié)議。

借鑒美國國家科學(xué)基金網(wǎng)（National Science Foundation Network，NSFNET）網(wǎng)絡(luò)，在輕量級仿真平臺mininet 對上述所提方案進行實驗仿真環(huán)境搭建，該網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖5 所示。 由于本文不深入研究量子密鑰分發(fā)網(wǎng)絡(luò)中通過量子信道生成密鑰資源的過程，因此通過修改OVS 交換機源碼為密鑰中繼節(jié)點的每條鄰接鏈路設(shè)置一個整型變量來模擬鏈路密鑰池中的剩余密鑰量，并通過變量值的增減來模擬密鑰資源的生成及消耗過程。

圖5 NSFNET 網(wǎng)絡(luò)拓撲圖

實驗參數(shù)設(shè)置如下：每條鏈路的密鑰生成速率為15KBps 到30KBps 之間的隨機整數(shù)值，每條鏈路的密鑰池總?cè)萘繛?0000KB，每條鏈路的密鑰池閾值為2000KB，每條鏈路的密鑰池初始量為5000KB，控制器以10s 為周期收集每條鏈路的密鑰池剩余密鑰量。 由于實際網(wǎng)絡(luò)中，每個源節(jié)點的密鑰交換需求服從泊松分布，因此需要修改mininet 源碼模擬真實網(wǎng)絡(luò)環(huán)境下的用戶密鑰交換服務(wù)需求。 假設(shè)密鑰交換長度為固定的20KB，密鑰交換請求業(yè)務(wù)發(fā)送速率為50KB／s，密鑰交換需求持續(xù)時間為10s，每個終端用戶節(jié)點可以將用戶密鑰需求隨機發(fā)送給其他任何一個終端用戶。

本文在搭建好仿真環(huán)境后，我們的實驗將從以下四個性能指標進行相應(yīng)的仿真環(huán)境設(shè)置：

（1）路由可行性驗證：首先對本文設(shè)計的路由選擇算法結(jié)合分段路由轉(zhuǎn)發(fā)技術(shù)的可行性進行驗證。 終端用戶h1 向h2 發(fā)送用戶密鑰業(yè)務(wù)請求時，SDN 控制器會從K 條最優(yōu)密鑰中繼路徑中選擇跳數(shù)最少的路徑作為最終密鑰中繼路徑。 最終密鑰中繼路徑確定后，利用分段路由技術(shù)將該路徑進行編碼，并將其編碼結(jié)果下發(fā)至源節(jié)點（以及中間節(jié)點）。 經(jīng)過這兩步后，用戶密鑰UK 由中繼路徑轉(zhuǎn)發(fā)，并消耗鏈路密鑰LK。

（2）鏈路密鑰池密鑰資源：全網(wǎng)各鏈路密鑰池的密鑰剩余量情況反映密鑰資源分布的均衡情況。 在對鏈路密鑰池密鑰資源性能對比仿真實驗中，我們將與OSPF 算法（總選擇路由跳數(shù)最少的一條路徑）進行對比，各終端節(jié)點h1、h2、h3、h4、h5 間隨機選擇一個終端節(jié)點發(fā)送用戶密鑰請求服務(wù)，所有鏈路生成密鑰，只有密鑰中繼路徑上的鏈路才需要消耗密鑰，每隔10s 輸出網(wǎng)絡(luò)中各條鏈路密鑰池中剩余密鑰量的日志情況。

（3）用戶密鑰交換服務(wù)成功率：用戶密鑰交換失敗的主要原因是密鑰中繼路徑中的一些QKD 鏈路缺少鏈路密鑰LK，因此該值越高說明其路由方案越好。 在本文實驗中，同樣與OSPF算法進行用戶密鑰交換服務(wù)成功率的性能情況對比，設(shè)置每條鏈路密鑰池的初始密鑰量為5000KB，保證密鑰池中足夠的密鑰量可供消耗，接著讓h1 向h2 發(fā)送用戶密鑰交換服務(wù)請求，并從300 的服務(wù)請求數(shù)量逐漸增加到1200。

（4）流表項開銷：用戶密鑰交換服務(wù)的中繼轉(zhuǎn)發(fā)決定于密鑰中繼節(jié)點的流表，其節(jié)點的流表開銷越大，說明所消耗流表資源越大。 在流表項開銷的性能對比實驗中，我們將采用分段路由轉(zhuǎn)發(fā)技術(shù)與SDN 默認轉(zhuǎn)發(fā)技術(shù)分別進行實驗，通過不斷增加通信終端對的數(shù)量，以增加用戶密鑰交換服務(wù)請求，如首先讓h1 向h2 發(fā)送密鑰交換請求服務(wù)，模擬一對終端的密鑰交換業(yè)務(wù)，再讓h1 向h2、h1 向h3 發(fā)送密鑰交換請求服務(wù)，模擬兩對終端的密鑰請求業(yè)務(wù)，依次類推，得到采用分段路由轉(zhuǎn)發(fā)技術(shù)和SDN 默認轉(zhuǎn)發(fā)技術(shù)下全網(wǎng)所有密鑰中繼節(jié)點的流表項開銷情況。

4.2 仿真結(jié)果與分析

4.2.1 路由可行性驗證

圖6 展示的是終端節(jié)點h1 和h2 用戶密鑰請求的路由選擇情況，可以看到，選出的3 條最優(yōu)密鑰中繼路徑為：h1 →S2 →S3 →S6 →S13 →S14 →h2，h1 →S2 →S4 →S11 →S14 →h2，h1 →S2 →S3 →S1 →S8 →S9 →S14 →h2，最終的密鑰中繼路徑為h1 →S2 →S4 →S11 →S14 →h2。

圖6 中繼路徑的選擇

圖7 中的（a）為h1 向h2 發(fā)起用戶密鑰請求時，控制器下發(fā)至h1 直連交換機S2 的標簽壓棧流表項，h1 發(fā)送的用戶密鑰UK 經(jīng)過S2 會依次被打上14、11 的標簽，如（c）所示，并從端口4 轉(zhuǎn)發(fā)出去，（b）與（c）情況類似。

圖7 分段路由技術(shù)源節(jié)點流表及MPLS 標簽棧

從圖8 可以看到，h1 到h2 的業(yè)務(wù)請求首先選擇的是h1 →S2 →S3 →S6 →S13 →S14 →h2，但隨著時間的推移，鏈路密鑰不斷被消耗，第二次日志輸出時，密鑰中繼路徑切換為h1 →S2 →S4 →S11 →S14 →h2。

圖8 動態(tài)路由選擇情況

從上述對中繼路徑的選擇、分段路由技術(shù)的源節(jié)點流表和數(shù)據(jù)包的MPLS 棧，以及本文路由算法的動態(tài)選擇等情況的結(jié)果分析，可以看到本文所提結(jié)合分段路由技術(shù)路由算法的可行性，為量子密鑰分發(fā)網(wǎng)絡(luò)的路由方案提供一種新的思路。

4.2.2 鏈路密鑰池密鑰資源

圖9 表示使用本文所提方案與使用OSPF算法情況下各條鏈路密鑰池中剩余密鑰量的三次日志輸出情況。 從圖9 的（a）可以看出，本文所提方案和OSPF 鏈路密鑰資源變化趨勢幾乎完全相同，但到（b）（c）圖可以看到，兩種算法的密鑰資源情況開始出現(xiàn)一些偏差，說明本文所提方案的動態(tài)調(diào)整路徑起到了作用。 總的來說，采用本文所提方案和OSPF 算法各鏈路密鑰池的資源分布情況相差較大，本文所提方案下的鏈路密鑰池密鑰量相比OSPF 算法更加均勻，資源的利用也更加均衡。 從圖中也可以看到，有幾條鏈路的密鑰資源使用得較多，應(yīng)該考慮對這些關(guān)鍵鏈路密鑰資源的合理利用。

4.2.3 用戶密鑰交換服務(wù)成功率

如圖10 所示為實驗得到兩種方案的用戶密鑰交換服務(wù)成功率。 從圖中可以看出，本文所提方案和OSPF 路由算法的服務(wù)成功率都隨著用戶密鑰交換服務(wù)數(shù)量的增加而降低，但由于本文所提方案可以根據(jù)鏈路密鑰池密鑰資源的情況動態(tài)選擇剩余密鑰量較多的鏈路作為中繼鏈路轉(zhuǎn)發(fā)，而OSPF 路由方案始終選擇路由跳數(shù)最少的路徑中繼轉(zhuǎn)發(fā)，導(dǎo)致最短中繼路徑上的鏈路密鑰不斷被消耗，所以用戶密鑰交換服務(wù)的成功率要高于OSPF 路由算法。

圖10 h1 請求h2 的用戶密鑰交換服務(wù)成功率

4.2.4 流表項開銷

圖11 為采用分段路由轉(zhuǎn)發(fā)技術(shù)和默認轉(zhuǎn)發(fā)技術(shù)下，不同數(shù)量終端對的密鑰交換服務(wù)所需要下發(fā)的流表項開銷。

圖11 最大流表項開銷

由于分段路由技術(shù)需要在初始化時安裝默認表項，所以在請求密鑰交換服務(wù)的終端對較少的情況下，流表項開銷要大于默認轉(zhuǎn)發(fā)技術(shù)。 但從圖中可以看出，隨著終端對數(shù)量的增大，分段路由轉(zhuǎn)發(fā)技術(shù)的優(yōu)勢越來越大，這是因為分段路由技術(shù)只需要新增源節(jié)點流表和中間節(jié)點流表，不需要向其他節(jié)點下發(fā)流表。 而在現(xiàn)實網(wǎng)絡(luò)中，發(fā)送密鑰交換請求服務(wù)的終端用戶對將比本文實驗要更多且情況更復(fù)雜，所以采用分段路由轉(zhuǎn)發(fā)技術(shù)在減少流表項開銷上具有很大優(yōu)勢。

5 總結(jié)

本文面向量子密鑰分發(fā)網(wǎng)絡(luò)環(huán)境下的路由選擇問題，為減少控制器與中繼節(jié)點的通信以及數(shù)據(jù)層中繼節(jié)點的流表項開銷，結(jié)合分段路由技術(shù)設(shè)計了一種路由選擇算法。 針對QKD 網(wǎng)絡(luò)密鑰生成率低密鑰消耗不均勻等問題，利用K 最短路徑算法選出密鑰量充足且避免密鑰資源無意義消耗的密鑰中繼路徑，并根據(jù)網(wǎng)絡(luò)中鏈路密鑰量情況動態(tài)調(diào)整中繼路徑。 通過模擬量子保密通信網(wǎng)絡(luò)環(huán)境，實驗驗證了該路由選擇算法結(jié)合分段路由技術(shù)的可行性，并與目前QKD 網(wǎng)絡(luò)普遍使用的OSPF 路由算法進行對比，驗證該方案對于量子密鑰網(wǎng)絡(luò)中各鏈路密鑰池密鑰資源負載均衡以及用戶密鑰交換服務(wù)成功率的優(yōu)勢。 同時，實驗得出分段路由轉(zhuǎn)發(fā)技術(shù)相比于默認轉(zhuǎn)發(fā)技術(shù)運用到真實的基于SDN 的量子保密通信網(wǎng)絡(luò)中可減少流表項開銷，對于量子保密通信網(wǎng)絡(luò)的密鑰中繼節(jié)點的流表項開銷具有一定的參考價值。