陳文龍 趙一榮 肖 融 唐曉嵐 徐 恪

1(首都師范大學(xué)信息工程學(xué)院 北京 100048) 2(北京師范大學(xué)信息科學(xué)與技術(shù)學(xué)院 北京 100875) 3 (清華大學(xué)計算機科學(xué)與技術(shù)系 北京 100084) (chenwenlong@cnu.edu.cn)

2013年斯諾登披露的“棱鏡計劃”通過直接攻擊互聯(lián)網(wǎng)大型路由設(shè)備獲取網(wǎng)絡(luò)流量[1],使得路由器及轉(zhuǎn)發(fā)路徑的安全、可信備受關(guān)注.互聯(lián)網(wǎng)總是包羅不同廠商、基于不同平臺研制的路由器,安全可信度相差較大,而且同一設(shè)備部署于不同管理環(huán)境時其可信度也會有差異.另一方面,不同的互聯(lián)網(wǎng)流量的安全需求也各不相同.我們需要圍繞流量安全需求、路由節(jié)點可信度、流量傳輸路徑,進行區(qū)域范圍的一體化可信傳輸規(guī)劃.軟件定義網(wǎng)絡(luò)(software defined networking, SDN)[2]環(huán)境為上述需求提供了良好的網(wǎng)絡(luò)支撐環(huán)境.本文面向SDN網(wǎng)絡(luò)環(huán)境,為不同安全級別的流量提供相應(yīng)可信級別的傳輸路徑,確保網(wǎng)絡(luò)流量的可信傳輸.

本文設(shè)計了多級可信傳輸機制(credible trans-mission mechanism with multiple levels, CETML),實現(xiàn)流量的可信傳輸.該傳輸體系中,每一個路由節(jié)點和每一個IP前綴都被指定相應(yīng)的可信級別.而且,進入可信網(wǎng)絡(luò)的流量基于其源、目的IP地址,在IP頭部被設(shè)置明確的可信級別,用于標(biāo)識流量所期望的傳輸路徑(即路由節(jié)點)的最小可信級別.可信傳輸機制確保網(wǎng)絡(luò)中的報文必須通過不小于其可信級別的路由器進行轉(zhuǎn)發(fā).本文面向SDN網(wǎng)絡(luò)環(huán)境,基于可信級別構(gòu)建虛擬拓撲,設(shè)計了可依次迭代的多級路由計算方法.路由節(jié)點序號按可信級別反序排列,利用Floyd算法思想,實現(xiàn)高效的多關(guān)聯(lián)拓撲最短路由計算算法.

本文主要貢獻包括3方面:

1) 提出了多級可信傳輸體系,為網(wǎng)絡(luò)流量及路由節(jié)點指定可信級別,并確保網(wǎng)絡(luò)流量總是通過不小于其可信級別的路由器進行傳輸;

2) 基于可信級別構(gòu)建多級虛擬拓撲,設(shè)計路由節(jié)點的可擴展二維序號,使得一次迭代算法獲得所有虛擬拓撲的路由計算結(jié)果,顯著降低了路由計算的復(fù)雜度;

3) 設(shè)計了路由器中基于可信級別索引的多跳轉(zhuǎn)發(fā)表結(jié)構(gòu),優(yōu)化了存儲空間并提升了轉(zhuǎn)發(fā)效率.

1 相關(guān)研究

在網(wǎng)絡(luò)傳輸安全的研究中,可信網(wǎng)絡(luò)[3]一直是關(guān)注的熱點問題.文獻[4]提出了一種適用于開放分布式網(wǎng)絡(luò)環(huán)境下的基于信任領(lǐng)域和評價可信度量的信任模型,并給出了模型流程及相關(guān)定義.同時設(shè)計了基于節(jié)點評分行為相似性的共謀團體識別算法,以及評價節(jié)點反饋權(quán)重的方法.文獻[5-6]介紹了一種主觀邏輯信任模型,通過消除不信任路徑的方法簡化信任圖,將復(fù)雜的信任圖簡化為串并行圖,但這種簡化方式在理論上存在信息損失的可能性.改進的信任模型無需信任圖簡化,轉(zhuǎn)而使用邊緣切割的方式得到規(guī)范圖,并計算節(jié)點的信任度.文獻[7-8]設(shè)計了路由交換范式構(gòu)建可信網(wǎng)絡(luò),可對報文進行轉(zhuǎn)發(fā)過濾,對路由設(shè)備的行為進行管理控制,并設(shè)計相應(yīng)范式,實驗證明其可有效識別竊聽分組行為.文獻[9]提出一種自治域網(wǎng)絡(luò)中終端切換時的快速身份認證方法,以保證安全終端的域內(nèi)可信.

多徑路由傳輸?shù)燃夹g(shù)作為傳統(tǒng)路由的擴展,既可提高網(wǎng)絡(luò)傳輸能力,又能為安全傳輸提供技術(shù)支撐.基于2維路由的多徑傳輸可為具有相同目的IP、不同源IP的流量提供不同安全性能的傳輸路徑[10].文獻[11]為多徑傳輸?shù)牧鲃澐謫栴}設(shè)計了最大最小值的路徑延時算法,并可計算出最佳的流量分割方法.文獻[12-13]設(shè)計了依據(jù)傳輸時延預(yù)測的多徑傳輸算法,減少不同路徑傳輸時延差異對多徑傳輸帶來的影響.文獻[14]基于鏈路狀態(tài)路由設(shè)計了多路徑傳輸體系,并把路徑長度和路徑可靠性作為路由選擇的主要參數(shù).

SDN是一種集中式路由控制環(huán)境,非常適合部署靈活的路由策略,可通過多路徑傳輸提升網(wǎng)絡(luò)安全性或帶寬利用率[15].文獻[16]介紹了軟件定義網(wǎng)絡(luò)的研究進展,包括軟件定義網(wǎng)絡(luò)的體系結(jié)構(gòu)和協(xié)議設(shè)計,以及各層次設(shè)備設(shè)計與轉(zhuǎn)發(fā)規(guī)則,并對其一致性、可用性、容錯性等關(guān)鍵控制屬性進行了評估.SDN環(huán)境中,控制服務(wù)器需要計算拓撲中每2個節(jié)點之間的最優(yōu)路徑,現(xiàn)有的Dijkstra算法是一種選擇,但仍需優(yōu)化.文獻[17]介紹的Dijkstra優(yōu)化算法,利用兩點間直線距離最短的思想,重新規(guī)劃節(jié)點計算順序使得節(jié)點計算數(shù)量減少,從而提升算法效率.文獻[18]面對Dijkstra算法,引入了加權(quán)約束函數(shù)來解決數(shù)據(jù)結(jié)構(gòu)存儲的空間和時間冗余等缺陷,并且靈活地改變權(quán)值以適應(yīng)不同的網(wǎng)絡(luò)復(fù)雜度.Floyd-Warshall算法[19]通過路由矩陣的迭代計算,完成網(wǎng)絡(luò)中所有節(jié)點間的最優(yōu)傳輸路徑的計算,研究者通過排除無關(guān)節(jié)點等方法進行算法優(yōu)化[20].社交網(wǎng)絡(luò)的分類別連接路徑[21]與本文工作有類似思想,其拓撲中每條邊都具有不同的標(biāo)簽屬性,用于標(biāo)識不同類別的連接關(guān)系.研究者設(shè)計了EDP(edge-disjoint partitioning)方法,計算同類別或跨類別節(jié)點的最短路徑.EDP由一個逐步增量建立的動態(tài)索引機制和一個高效的索引遍歷算法構(gòu)成,增量機制使得建立索引的開銷被分攤,提高了計算效率.

2 多級可信傳輸體系

多級可信傳輸?shù)暮诵乃枷胧?網(wǎng)絡(luò)中的報文必須通過不小于其可信級別的路由器進行轉(zhuǎn)發(fā),具體內(nèi)容描述如下:

1) 自治域網(wǎng)絡(luò)的管理機構(gòu)指定并配置所轄路由器的可信級別.考慮因素包括:生產(chǎn)廠商、系統(tǒng)研制平臺架構(gòu)、運營機構(gòu)、管理環(huán)境等.不同的網(wǎng)絡(luò)運營訴求會導(dǎo)致不同的配置依據(jù),本文不做分析.

2) 管理機構(gòu)對相關(guān)IP前綴指定可信級別,其他IP前綴為默認的最低可信級別.IP前綴的可信級別存儲在接入路由器中.

3) 路由器在可信級別約束范圍內(nèi)計算最優(yōu)路由.本文面向SDN環(huán)境設(shè)計,由控制器進行集中式路由計算,并向各路由器下發(fā)相應(yīng)的轉(zhuǎn)發(fā)表項.

4) 接入路由器依據(jù)統(tǒng)一策略，對進入自治域網(wǎng)絡(luò)的報文標(biāo)記可信級別,詳見2.1節(jié).

5) 路由器根據(jù)接收到報文的可信級別,選擇相應(yīng)級別的轉(zhuǎn)發(fā)路徑完成報文轉(zhuǎn)發(fā).

多級可信傳輸主要工作包括:1)可信級別的設(shè)定及標(biāo)識,以及可信傳輸策略的制定;2)多級可信傳輸體系下,最優(yōu)路徑的高效計算方法.多級可信傳輸是一種區(qū)域網(wǎng)絡(luò)整體規(guī)劃的部署方案,本文以SDN環(huán)境為背景進行集中式路由計算方法的設(shè)計.

圖1左上角的拓撲結(jié)構(gòu)是多級可信網(wǎng)絡(luò)的物理拓撲,包括:第3級正方形節(jié)點(最高可信級別),A,B,C,D;第2級六邊形節(jié)點,E,F;第1級圓形節(jié)點(最低可信級別),G,H.由于高級別的路由節(jié)點可以轉(zhuǎn)發(fā)低級別的流量，所以該物理拓撲可衍生出3個不同可信級別的虛擬拓撲,即另外3個分級別拓撲結(jié)構(gòu).顯然,可信級別由低到高形成的虛擬拓撲,具有依次包含關(guān)系.令拓撲中所有鏈路的雙向權(quán)值均為1,以A,D兩點的流量傳輸為例,針對不同可信級別的流量,它們在第1～3級虛擬拓撲中的最優(yōu)路徑分別為:A-G-D,A-B-C-D,A-B-C-D.

Fig. 1 Topology with multiple levels credibility圖1 多級可信拓撲

本文假設(shè)網(wǎng)絡(luò)管理機構(gòu)在構(gòu)建拓撲時確保不同可信級別的路由器是連通的.后續(xù)研究中,將針對某級別不連通的拓撲設(shè)計隧道連通方案.

2.1 可信級別的標(biāo)識

可信傳輸體系中,每一個IP前綴PF(代表某一局域網(wǎng))都具有對應(yīng)的可信級別,表示為:CR(PF).任一路由節(jié)點r都有唯一的可信級別:CR(r).在此說明,路由器和IP前綴的可信等級是由網(wǎng)絡(luò)管理者預(yù)先指定的.

令數(shù)據(jù)流Γ的源、目的IP前綴為〈PFs,PFd〉,則數(shù)據(jù)流Γ的可信級別由其源、目的前綴決定,表示為式(1)：

CR(Γ)=Ftraffic(CR(PFs),CR(PFd)).

(1)

基于不同的可信管理需求,設(shè)置不同的Ftraffic計算策略,本文建議直接取源、目的IP可信級別的較小值為流量的可信級別,即：

CR(Γ)=min(CR(PFs),CR(PFd)).

(2)

當(dāng)然,我們需要存儲IP前綴與可信級別的對應(yīng)關(guān)系:〈PF,CR(PF)〉,IP地址可信級別的對應(yīng)關(guān)系查找過程也符合最長前綴匹配規(guī)則.例如,若可信傳輸網(wǎng)絡(luò)有2個可信級別關(guān)系〈10.0.0.08,CR1〉,〈10.10.0.016,CR2〉,則IP地址10.10.0.1對應(yīng)的可信級別為CR2.

通常,我們只對部分需關(guān)注的IP前綴存儲其可信級別,其他IP前綴為默認的最低可信級別(1級).而且,IP前綴可信級別信息只需存儲在自治域邊緣路由器中,它們對進入自治域網(wǎng)絡(luò)的流量進行可信級別的標(biāo)識,所以前綴可信級別信息存儲代價不大.令非默認級別的IP前綴數(shù)量為N_PFCR,則多級可信網(wǎng)絡(luò)中每個邊緣路由器需存儲N_PFCR個前綴可信級別信息:〈PF,CR(PF)〉.

邊緣路由器根據(jù)報文源、目的IP地址和已存儲的所轄IP前綴可信級別,在IP頭部標(biāo)記流量的可信級別(IPv4為“traffic class”字段,IPv6為“type of service”字段).

2.2 多級可信轉(zhuǎn)發(fā)

多級可信傳輸體系中,去往同一IP網(wǎng)段的報文會基于報文的可信級別選擇不同的轉(zhuǎn)發(fā)路徑.所以,一條轉(zhuǎn)發(fā)項可能包含多個下一跳,它由第3節(jié)的多級路由計算所得.考慮到不同級別的轉(zhuǎn)發(fā)很可能共用相同的下一跳,為了提高存儲效率,采用下一跳索引的轉(zhuǎn)發(fā)項存儲結(jié)構(gòu),如圖2所示.每個路由器會單獨構(gòu)建一個下一跳索引表,包括路由節(jié)點所有的出接口和下一跳IP.轉(zhuǎn)發(fā)項有最多SM個下一跳索引,當(dāng)報文的可信級別為i時(取值范圍為[1,SM]),取其第i個下一跳索引,其值為index #i.若值為0,表示不存在對應(yīng)級別的下一跳,否則取“下一跳索引表”中的第“index #i”項內(nèi)容為該報文的下一跳轉(zhuǎn)發(fā)信息.由于路由器無法轉(zhuǎn)發(fā)可信級別高于自身的報文,若路由器可信級別為k,則它所有轉(zhuǎn)發(fā)項都最多有k個下一跳.

Fig. 2 Forwarding entries including multiple next hops圖2 包含多級下一跳的轉(zhuǎn)發(fā)項結(jié)構(gòu)

多級轉(zhuǎn)發(fā)機制在商用路由器中的實現(xiàn)并不復(fù)雜.高性能路由系統(tǒng)中典型的TCAM+SRAM處理體系中，由于TCAM實現(xiàn)IP前綴的最長匹配,無需修改.只需修改SRAM中的下一跳匹配結(jié)果,并在SRAM中構(gòu)建一個較小容量的下一跳索引表.

3 多級路由計算

表1為主要符號的描述說明.令可信級別為1～SM,SM為最高級別的安全可信等級,圖1左上角的拓撲結(jié)構(gòu)中SM=3.令物理拓撲G的全體路由節(jié)點集合為Rtotal,任一路由節(jié)點r都有唯一的可信級別CR(r),其取值范圍為[1,SM].令LRi表示可信級別為i的路由節(jié)點集合,該集合的路由節(jié)點數(shù)量為N_LRi,有：

LRi={r|CR(r)=i}，N_LRi=|LRi|. (3)

本文中,任一節(jié)點不允許同時屬于多個可信級別,滿足節(jié)點可信級別的唯一性原則,有：

LRi∩LRj=?，

(4)

其中，i≠j,1≤i,j≤SM.

根據(jù)可信傳輸?shù)霓D(zhuǎn)發(fā)策略,拓撲G可根據(jù)可信等級規(guī)劃出SM個不同級別的虛擬拓撲VG1～SM,其對應(yīng)的路由器集合為VR1～SM.物理拓撲G中,對于可信級別為i的流量,其傳輸路徑的選擇范圍為VGi.說明,本文只考慮點到點鏈路,只有鏈路兩端的節(jié)點都屬于VGi,它們對應(yīng)的鏈路才屬于VGi.

可信級別為i的虛擬網(wǎng)絡(luò)拓撲VGi中,所有路由節(jié)點的可信級別都不小于i,即VGi的路由器集合VRi滿足:

VRi={r|CR(r)≥i}.

(5)

同時,虛擬拓撲VGi的路由器集合VRi也可表示為

(6)

對于物理拓撲G,虛擬拓撲VG1與G等同,路由節(jié)點數(shù)量也相同,即VR1=Rtotal.而且,SM個不同可信級別的拓撲VG1～SM,其路由器集合滿足：

VR1?VR2?…?VRSM.

(7)

顯然,相應(yīng)的虛擬拓撲之間的包含關(guān)系為：

VG1?VG2?…?VGSM.

(8)

令VRi的節(jié)點數(shù)量為N_VRi,有：

(9)

多級可信路由計算的關(guān)鍵問題是:面向多個關(guān)聯(lián)的虛擬拓撲,如何高效計算所有拓撲中任意兩節(jié)點間的最短路徑.考慮多級可信體系須要對路由器及IP前綴進行可信級別的指定及配置,同時SDN研究也促進了業(yè)界對集中式網(wǎng)絡(luò)體系架構(gòu)的認可,本文主要研究多級路由的集中式計算.

典型的Floyd-Warshall算法可在O(n3)內(nèi)求解出拓撲中所有節(jié)點對之間的最短路徑.如果直接應(yīng)用該算法,那么對于SM個虛擬拓撲需要進行SM次Floyd算法,效率不高.本文考慮了多級可信拓撲的特點與聯(lián)系,將節(jié)點序號按可信級別反序排列,設(shè)計了可依次迭代的多級可信網(wǎng)絡(luò)最短路徑算法.

本文算法中,拓撲中路由節(jié)點用二維索引來標(biāo)識,表示為NodeIndex(i,j).第1維度i表示節(jié)點的可信級別,i取值越大則可信等級越高;第2維度j表示節(jié)點在相同可信級別節(jié)點集合中的序號,考慮路由計算的效率,j根據(jù)節(jié)點的鄰接度數(shù)反序排列.

2維索引分配機制為多級拓撲路由計算提供了方便,根據(jù)1維序號可直接確定節(jié)點與某可信拓撲的從屬關(guān)系.而且,2維序號還可有效提升多級可信網(wǎng)絡(luò)拓撲的可擴展性,因為第i級路由節(jié)點的增、刪對路由計算過程影響較小.特別是對可信級別大于i的路由結(jié)果沒有任何改變.

多級別可信網(wǎng)絡(luò)路由計算中,路由節(jié)點的迭代順序有2項規(guī)則：

2) 級內(nèi)規(guī)則.對于相同可信級別的節(jié)點(即第2維度),序號由小到大依次進行路由矩陣的迭代計算.

定義2.i階子矩陣.給定n階矩陣R,取其前i行、前i列可形成i階子矩陣T,1≤i≤n;稱矩陣T為矩陣R的i階子矩陣,表示為T=SUBi(R).

推論1.

由于矩陣的每一次迭代計算都可能改變矩陣中任一元素的值,所以有:

住宅工程質(zhì)量通病的防治是一項系統(tǒng)化、長期性的工作，雖然受到技術(shù)和工藝的限制，我們很難做到完全消除所有的通病，但通過集全社會的努力研發(fā)出更“新、高、精、尖”的技術(shù)、更完善的方案，提前做好預(yù)防和控制措施，能夠?qū)①|(zhì)量通病的影響降到最低，改善人居環(huán)境，提升人民群眾的生活品質(zhì)。

(10)

其中，i

所以,虛擬拓撲VGi的路由計算結(jié)果,必須在G的N_VRi次迭代時通過子矩陣獲取.

基于推論1,可設(shè)計在一次Floyd算法運算中,獲得所有可信虛擬拓撲的路由結(jié)果.給定全網(wǎng)物理拓撲G(即虛擬拓撲VG1),并根據(jù)可信等級確定的2維節(jié)點編號,實施n階矩陣的迭代路由計算,有:

(11)

對應(yīng)上述分析的具體算法如算法1所示：

算法1. 多級路由計算.

② fork←getNode(V,NodeIndex(i,j)) do

③ for each nodeu∈Vdo

④ for each nodev∈Vdo

⑤ ifA(u,v)>A(u,k)+A(k,v) then

⑥A(u,v)=A(u,k)+A(k,v)；

⑦P(u,v)=P(u,k)；

⑧count=count+1；

⑨ end if

⑩ end for

算法1主要包括3部分：

Fig. 3 Topology for calculation of multi-level routing圖3 多級路由計算拓撲

上述處理方法可使得算法迭代過程中的中間運算結(jié)果具有實際意義,從整體上達到降低計算復(fù)雜度、減少計算量的效果.節(jié)點迭代順序的規(guī)劃、中間運算結(jié)果的運用,這2點是本文CETML路由計算的核心內(nèi)容.

(12)

(13)

(14)

4 實驗及性能分析

1) 轉(zhuǎn)發(fā)項存儲分析.下一跳索引表中,每一項占用8 B；通常路由器不會超過100個鄰居節(jié)點,則至多占用100×8=800 B內(nèi)存空間.現(xiàn)有的非多級傳輸體系(non-multiple levels transmission, NMLT)中路由器的轉(zhuǎn)發(fā)引擎為了節(jié)省存儲,也使用下一跳索引結(jié)構(gòu),則本文工作與現(xiàn)有技術(shù)消耗同樣的下一跳索引表存儲空間.對于IPv4轉(zhuǎn)發(fā)項,“DestIP Network”為4 B;“Mask Length”為1 B;“index #i”根據(jù)路由器對外接口數(shù)確定,1 B可支持256個接口,足夠使用.NMLT機制中轉(zhuǎn)發(fā)項只需一個下一跳索引“index #i”,則一條轉(zhuǎn)發(fā)項占6 B.多級可信傳輸體系中,轉(zhuǎn)發(fā)項需存儲多個下一跳索引,其數(shù)量與路由器r的可信級別CR(r)等同,共占(5+CR(r)) B.

如第3節(jié)的符號定義,可信級別為i的路由節(jié)點數(shù)量為N_LRi,它們的轉(zhuǎn)發(fā)項需存儲i個下一跳索引.令可信傳輸網(wǎng)絡(luò)中所有路由器的轉(zhuǎn)發(fā)項數(shù)量相同，都為N_RT,則平均單個路由器的轉(zhuǎn)發(fā)表消耗內(nèi)存為

(15)

Fig. 5 Calculation time of the different algorithms for the typical topologies圖5 典型拓撲不同路由算法計算時間

多級可信傳輸網(wǎng)絡(luò)(CETML)中,令各級路由器數(shù)量相等,則內(nèi)存消耗如圖4所示.多級傳輸路由器的內(nèi)存消耗相對現(xiàn)有轉(zhuǎn)發(fā)引擎略多,并且隨級別數(shù)量增加而有所增加,但總體增加并不明顯.例如,當(dāng)網(wǎng)絡(luò)中包含1萬條路由項時,路由器也只是增加10 ～20 KB的內(nèi)存消耗.

Fig. 4 Memory consumption of forwarding entries圖4 轉(zhuǎn)發(fā)項存儲內(nèi)存占用

2) 路由計算性能分析.針對真實網(wǎng)絡(luò)拓撲的路由計算實驗分析了不同方法的計算性能.實驗的網(wǎng)絡(luò)拓撲選擇4個國內(nèi)外典型知名拓撲:①Cernet[22].中國教育和科研計算機網(wǎng),實驗拓撲包括36個節(jié)點、49條鏈路.②Cernet2[23].中國下一代互聯(lián)網(wǎng)示范網(wǎng)絡(luò)核心網(wǎng),實驗拓撲包括20個節(jié)點、22條鏈路.③Abilene[24].由研究機構(gòu)和教育團體創(chuàng)建的一個美國骨干網(wǎng)絡(luò),實驗拓撲包括12個節(jié)點、18條鏈路.④Geant[25].歐洲研究單位和教育機構(gòu)合作建立的網(wǎng)絡(luò),實驗拓撲包括44個節(jié)點、71條鏈路.

每個路由節(jié)點的可信等級采用均勻分布的隨機方式生成,并且需保證SM個可信級別中任意級別的路由節(jié)點數(shù)不為零.在每一種拓撲中分別進行可信級別數(shù)量為1～5的5次實驗,5次實驗中虛擬拓撲數(shù)量分別為1～5.每次實驗中,分別運用Dijkstra算法、Floyd算法、CETML算法,計算n個節(jié)點任意兩節(jié)點之間的最短路徑,統(tǒng)計各個算法的平均計算時間.

本次實驗在PC端的Windows10(64bit)專業(yè)版系統(tǒng)下完成.設(shè)備硬件配置為Intel Core i5-4200M、2.50 GHz雙核CPU、8 GB DDR3L內(nèi)存.軟件配置為Visual Studio Community 2017版本15.3.0,SDK版本為10.0.14393.0,Release方案配置,x64方案平臺,禁用優(yōu)化Od,實驗程序使用CC++語言實現(xiàn).

不同路由算法的計算性能實驗結(jié)果如圖5所示.首先,當(dāng)網(wǎng)絡(luò)中僅存在唯一可信級別時(等同于無可信級別的傳統(tǒng)網(wǎng)絡(luò)),CETML與Dijkstra算法、Floyd算法三者的計算時間相差極小;然而,隨著可信級別數(shù)量增加,Dijkstra算法、Floyd算法的計算時間顯著上升,而CETML的計算時間較為平穩(wěn).

從理論上分析,對于直接運用Dijkstra、Floyd算法,計算一個虛擬拓撲所有節(jié)點對之間的路徑信息的時間復(fù)雜度為O(n3);當(dāng)存在m個可信級別時,計算m個虛擬拓撲路徑信息的時間復(fù)雜度為O(mn3).對于CETML算法,計算m個虛擬拓撲的路由信息,只需對VG1進行1次時間復(fù)雜度為O(n3)的計算,并分別在N_VRi次迭代時獲取子矩陣.因此,CETML的時間復(fù)雜度低于Dijkstra算法和Floyd算法.實驗數(shù)據(jù)基本符合理論分析結(jié)果.

5 總 結(jié)

“棱鏡計劃”揭示了互聯(lián)網(wǎng)路由設(shè)備安全以及可信傳輸?shù)闹匾?本文針對網(wǎng)絡(luò)流量的安全需求及網(wǎng)絡(luò)設(shè)備的可信級別,設(shè)計了基于虛擬拓撲的多級可信傳輸機制——CETML,可信網(wǎng)絡(luò)中的流量總是由不小于其可信級別的路由器進行轉(zhuǎn)發(fā).

CETML機制中,網(wǎng)絡(luò)管理者為每個路由器及關(guān)注的IP前綴指定可信級別,繼而基于源、目的IP前綴得到每個網(wǎng)絡(luò)流量的可信級別.在可信網(wǎng)絡(luò)的邊緣,接入路由器利用IP頭部的空閑空間為每個數(shù)據(jù)包標(biāo)識可信級別.CETML根據(jù)網(wǎng)絡(luò)中路由器的不同級別構(gòu)建多個虛擬拓撲,由于可信傳輸?shù)奶卣?可分析出可信級別由低到高的虛擬拓撲間的依次包含關(guān)系.考慮多級可信傳輸體系中集中式管理的元素較多,本文主要研究集中式路由算法.以Floyd算法為基礎(chǔ),面向SDN環(huán)境設(shè)計了高效的多級別路由計算方法,多個虛擬拓撲的最優(yōu)路由信息在一次Floyd計算過程中依次獲取.其中,路由節(jié)點基于可信級別的2維序號,為多拓撲路由迭代計算提供了可行基礎(chǔ),也為路由節(jié)點的增刪提供了便利,提升了可信網(wǎng)絡(luò)結(jié)構(gòu)的可擴展性.CETML還設(shè)計了多級可信轉(zhuǎn)發(fā)引擎的轉(zhuǎn)發(fā)表結(jié)構(gòu),優(yōu)化了存儲性能,簡化了處理過程.

實驗驗證了CETML路由計算的高效性,針對國內(nèi)外4個實際網(wǎng)絡(luò)拓撲進行多級路由計算,展示了CETML明顯優(yōu)于Dijkstra算法和原本的Floyd算法.對于CETML帶來的存儲開銷也做了分析,邊緣路由器需要存儲少量前綴可信級別信息(與非默認可信級別的IP前綴相關(guān)).此外,基于可信級別索引的多跳轉(zhuǎn)發(fā)表結(jié)構(gòu)也會增加少量的存儲(1萬條路由對應(yīng)10～20 KB的內(nèi)存).需要說明,多級可信傳輸機制部署還會帶來一個顯然的額外收益,因為多徑傳輸會使整個網(wǎng)絡(luò)的帶寬利用率提高.

[1]National Security Agency. PRISMUS-984XN Overview. 2013 [2017-11-22]. https:edwardsnowden.comzh20130607prism-overview-slides

[2]Nunes B A A, Mendonca M, Nguyen X N, et al. A survey of software-defined networking: Past, present, and future of programmable networks. IEEE Communications Surveys and Tutorials, 2014,16(3): 1617-1634

[3]Lin Chuang, Peng Xuehai. Research on trustworthy networks[J]. Chinese Journal of Computers, 2005, 28(5): 751-758 (in Chinese)(林闖, 彭雪海. 可信網(wǎng)絡(luò)研究[J]. 計算機學(xué)報, 2005, 28(5): 751-758)

[4]Cai Hongyun, Tian Junfeng, Li Zhen, et al. Trust model based on trust area and evaluation credibility[J]. Journal of Computer Research and Development, 2011, 48(11): 2131-2138 (in Chinese)(蔡紅云, 田俊峰, 李珍, 等. 基于信任領(lǐng)域和評價可信度量的信任模型研究[J]. 計算機研究與發(fā)展, 2011, 48(11): 2131-2138)

[5]J?sang A, Hayward R, Pope S. Trust network analysis with subjective logic[C]Proc of the 29th Australasian Computer Science Conf(ACSC2006). Piscataway, NJ: IEEE, 2006: 179-184

[6]J?sang A, Bhuiyan T. Optimal trust network analysis with subjective logic[C]Proc of the 2nd Int Conf on Emerging Security Information, Systems and Technologies. Los Alamitos, CA: IEEE Computer Society, 2008: 179-184

[7]Xu Ke, Zhao Yudong, Chen Wenlong, et al. Paradigm-based routing & switching system for data interception attacks[J]. Chinese Journal of Computers, 2017, 40(7): 1649-1663 (in Chinese)(徐恪, 趙玉東, 陳文龍, 等. 防御數(shù)據(jù)竊聽攻擊的路由交換范式體系[J]. 計算機學(xué)報, 2017, 40(7): 1649-1663)

[8]Xu Lei, Xu Ke, Shen Meng, et al. MINOS: Regulating router data plane actions in dynamic runtime environments[C]Proc of ACM Turing 50th Celebration Conf. New York: ACM, 2017: No.40

[9]Zheng Lijuan, Han Zhen. Trusted intra-domain fast authentication protocol based on split mechanism network[J]. Journal of Computer Research and Development, 2012, 49(5): 939-948 (in Chinese)(鄭麗娟, 韓臻. 基于分離機制網(wǎng)絡(luò)的可信域內(nèi)快速認證協(xié)議[J]. 計算機研究與發(fā)展, 2012, 49(5): 939-948)

[10]Xu Mingwei, Yang Shu, Wang Dan, et al. Two dimensional-IP routing[C]Proc of Int Conf on Computing, NETWORKING and Communications. Los Alamitos, CA: IEEE Computer Society, 2013: 835-839

[11]Shailendra S, Bhattacharjee R, Bose S K. Optimized flow division modeling for multi-path transport[C]Proc of India Conf (INDICON). Piscataway, NJ: IEEE, 2011: 1-4

[12]Du Wenfeng, Lai Liqian, Wu Zhen. Transmission delay prediction based data allocation scheme for concurrent mutipath transfer[J]. Journal of Software, 2015, 26(8): 2041-2055 (in Chinese)(杜文峰, 賴力潛, 吳真. 基于傳輸時延預(yù)測的多路徑并發(fā)傳輸數(shù)據(jù)分配算法[J]. 軟件學(xué)報, 2015, 26(8): 2041-2055)

[13]Du Wenfeng, Wu Zhen, Lai Liqian. Delay-sensitive data allocation scheme for CMT over diversity paths[J]. Journal on Communications, 2013, 34(4): 149-157 (in Chinese)(杜文峰, 吳真, 賴力潛. 傳輸延遲感知的多路徑并發(fā)差異化路徑數(shù)據(jù)分配方[J]. 通信學(xué)報, 2013, 34(4): 149-157)

[14]Tao Jing, Gao Xianming, Wang Baosheng, et al. Multi-path based link-state routing mechanism[C]Proc of the 18th Int Conf on Advanced Communication Technology (ICACT). Piscataway, NJ: IEEE, 2016: 342-351

[15]Casoni M, Grazia C A, Klapez M. SDN-based resource pooling to provide transparent multi-path communications[J]. IEEE Communications Magazine, 2017, 55(12): 1-7

[16]Zhang Chaokun, Cui Yong, Tang Heyi, et al. State-of-the-art survey on software-defined networking (SDN)[J]. Journal of Software, 2015, 26(1): 62-81 (in Chinese)(張朝昆, 崔勇, 唐翯祎, 等. 軟件定義網(wǎng)絡(luò)(SDN)研究進展[J]. 軟件學(xué)報, 2015, 26(1): 62-81)

[17]Bao Peiming. An optimization algorithm based on Dijkstra algorithm in search of shortcut[J]. Journal of Computer Research and Development, 2001, 38(3): 307-311 (in Chinese)(鮑培明. 距離尋優(yōu)中Dijkstra算法的優(yōu)化[J]. 計算機研究與發(fā)展, 2001, 38(3): 307-311)

[18]Huang Y, Yi Q, Shi M. An improved Dijkstra shortest path algorithm[C]Proc of the 2nd Int Conf on Computer Science and Electronics Engineering(ICCSEE-13). Paris, France: Atlantis Press, 2013: 226-229

[19]Aini A, Salehipour A. Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem[J]. Applied Mathematics Letters, 2012, 25(1): 1-5

[20]Wei Dachuan. Implementation of route selection function based on improved Floyd algorithm[C]Proc of Wase Int Conf on Information Engineering. Piscataway, NJ: IEEE, 2010: 223-227

[21]Hassan M S, Aref W G, Aly A M. Graph indexing for shortest-path finding over dynamic sub-graphs[C]Proc of the 2016 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2016: 1183-1197

[22]Cernet Network. Cernet topology[OL]. [2017-11-22]. http:www.cernet.comaboutusgyce_tpt.htm

[23]Cernet Network. Cernet2 topology[OL]. [2017-11-22]. http:www.cernet.comaboutusinternet2_tp.htm

[24]Internet2 Offices. Abilene topology[OL]. [2017-11-22]. https:www.internet2.edumediamedialibrary20170517I2-Network-Infrastructure-Topology-Layer_3logos-201705_TnrVotx.pdf

[25]Geant. Geant topology[OL]. [2017-11-22]. https:www.geant.orgResourcesDocumentsGEANT_top ology_map_august2017.pdf

ChenWenlong, born in 1976. PhD, associate professor. His main research interests include Internet architecture and network protocol.

ZhaoYirong, born in 1993. Master candidate. His main research interests include Internet architecture and Internet security.

XiaoRong, born in 1974. PhD, lecturer. Her main research interests include Internet architecture and Internet of things.

TangXiaolan, born in 1987. PhD, associate professor. Her main research interests include Internet architecture and wireless networks.

XuKe, born in 1974. Professor, PhD supervisor. His main research interests include Internet architecture, high perfor-mance router, P2P network, Internet of things and network economics.