許志偉,陳 波,張玉軍

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 計(jì)算技術(shù)研究所,北京 100190)

3(Department of Computer Science,University of Memphis,Memphis,TN 38152,USA)

現(xiàn)有的互聯(lián)網(wǎng)在可擴(kuò)展性、移動(dòng)性和安全性等方面面臨嚴(yán)峻的挑戰(zhàn)[1-3].互聯(lián)網(wǎng)的主流應(yīng)用形式已經(jīng)從基本的端到端通信轉(zhuǎn)變?yōu)榇笠?guī)模內(nèi)容傳輸,現(xiàn)有互聯(lián)網(wǎng)端到端的設(shè)計(jì)原則無法適應(yīng)這些新興的內(nèi)容密集型應(yīng)用形式,加劇了互聯(lián)網(wǎng)的內(nèi)容傳輸壓力.同時(shí),隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展,由移動(dòng)終端產(chǎn)生的流量占總體網(wǎng)絡(luò)流量的比重日益增加,而 TCP/IP體系結(jié)構(gòu)面向常連接設(shè)計(jì),IP地址被賦予身份和位置雙重功能,無法有效支撐移動(dòng)性應(yīng)用的要求.

為了從根本上解決互聯(lián)網(wǎng)面臨的這些問題,需要采用clean-slate方式設(shè)計(jì)并建設(shè)全新的未來互聯(lián)網(wǎng)[3-5].命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking,簡稱NDN)[6,7]根據(jù)信息名字請求和傳輸數(shù)據(jù),不再依賴固定的IP地址傳輸數(shù)據(jù),保證了互聯(lián)網(wǎng)的可擴(kuò)展性和移動(dòng)性;同時(shí),采用網(wǎng)內(nèi)數(shù)據(jù)泛在緩存和多路傳輸,有效地保障了這種基于內(nèi)容名字的傳輸機(jī)制的效率.鑒于 NDN網(wǎng)絡(luò)的這些優(yōu)點(diǎn),命名數(shù)據(jù)網(wǎng)絡(luò)的設(shè)計(jì)思想已經(jīng)得到了廣泛的重視和研究,將會應(yīng)用于包括5G在內(nèi)的新興網(wǎng)絡(luò)體系[8,9].

NDN網(wǎng)絡(luò)基于內(nèi)容名字進(jìn)行路由,內(nèi)容名字由不定數(shù)量的任意字符串組成.與 IP地址相比,內(nèi)容名字的結(jié)構(gòu)更為復(fù)雜,因此,現(xiàn)有的互聯(lián)網(wǎng)路由機(jī)制無法直接應(yīng)用于NDN網(wǎng)絡(luò).同時(shí),當(dāng)前互聯(lián)網(wǎng)擁有海量的在線內(nèi)容,相應(yīng)的內(nèi)容名字?jǐn)?shù)量也極其龐大.綜合考慮NDN網(wǎng)絡(luò)路由內(nèi)容名字的復(fù)雜性及其龐大的數(shù)量,基于名字的路由技術(shù)將是影響NDN網(wǎng)絡(luò)效率的最為關(guān)鍵的問題,將直接影響NDN網(wǎng)絡(luò)的效率和可用性[1].名字是內(nèi)容的標(biāo)識,目前常見的內(nèi)容名字可以分為兩類.

· 一類是以 NDN為代表的層次化名字,采用可讀的文本方式組織,一般由多個(gè)“/”隔開的名字段(字符串)組成,名字段的數(shù)量和長度都是任意的,類似于現(xiàn)行互聯(lián)網(wǎng)中的URL(uniform resource locator)[7].

· 另一類是以數(shù)字簽名為代表的扁平化名字.這類名字是經(jīng)過散列(hash)得到的散列值,具有很好的安全性[2].各類扁平化名字具有其專門的編碼方式,與IP地址類似,配備有完整的命名和路由規(guī)則.

當(dāng)前,關(guān)于層次化名字路由的研究還不成熟,尤其是如何優(yōu)化層次化名字路由,還沒有完善的解決方案.

目前,關(guān)于層次化名字路由傳輸?shù)难芯恐饕性谔嵘酚杀淼拿智熬Y(名字前綴由多個(gè)名字段構(gòu)成)查找速度方面[10-14],例如,通過前綴樹壓縮和GPU并行加速等方法來提高路由查表速度.現(xiàn)有的NDN路由機(jī)制為了獲取特定內(nèi)容,需要針對該內(nèi)容的名字添加相應(yīng)的路由表項(xiàng),利用內(nèi)容名字標(biāo)識路由,并關(guān)聯(lián)可以用于轉(zhuǎn)發(fā)的接口信息(不唯一),因此,NDN的路由表規(guī)模與現(xiàn)有 TCP/IP網(wǎng)絡(luò)的路由表規(guī)模相比將出現(xiàn)巨大的增長.另一方面,NDN網(wǎng)絡(luò)中內(nèi)容來源多樣,信息可以來自多信息源,或者移動(dòng)信息源,甚至以存儲在網(wǎng)內(nèi)緩存中的信息副本作為信息來源,導(dǎo)致網(wǎng)絡(luò)內(nèi)容版本變化更加頻繁,進(jìn)一步加劇了層次化名字路由器的負(fù)載.因此,僅靠提升單節(jié)點(diǎn)查表速度難以保證海量在線內(nèi)容的高效路由轉(zhuǎn)發(fā).針對這些問題,我們需要約減 NDN 網(wǎng)絡(luò)整體路由規(guī)模,實(shí)現(xiàn)層次化路由的聚合和聚合更新,保證高效、準(zhǔn)確地轉(zhuǎn)發(fā)內(nèi)容請求包及相應(yīng)的內(nèi)容包,提升NDN網(wǎng)絡(luò)整體效率.

路由聚合是降低路由表規(guī)模、提升查表效率和優(yōu)化路由轉(zhuǎn)發(fā)效率的主要措施.路由聚合用一條聚合路由代替大量原始路由,從而減小路由表規(guī)模[15].NDN網(wǎng)絡(luò)各節(jié)點(diǎn)路由聚合過程如圖1所示,聚合前,路由表中存在各個(gè)內(nèi)容對應(yīng)的表項(xiàng);聚合后,具有公共前綴和相同轉(zhuǎn)發(fā)接口的表項(xiàng)被聚合為一條聚合路由.不同于現(xiàn)有無類域間路由利用子網(wǎng)號(IP前綴)作為聚合路由標(biāo)識,NDN網(wǎng)絡(luò)聚合路由的標(biāo)識應(yīng)包括兩部分:首先是內(nèi)容名字前綴,其次還需要利用后綴聚合標(biāo)識區(qū)分這一前綴下發(fā)往不同接口內(nèi)容名字.這一聚合路由標(biāo)識上的差異實(shí)際上反映了IP路由和層次化名字路由的本質(zhì)差異.IP地址路由標(biāo)識了路由轉(zhuǎn)發(fā)的目的地址,特定子網(wǎng)內(nèi)IP地址有限,可以用子網(wǎng)號代表這些地址,作為聚合路由標(biāo)識.NDN網(wǎng)絡(luò)中,擁有同一名字前綴的路由的指向不確定,僅利用名字前綴無法代表所有被聚合的路由,形成的聚合路由也無法作為路由轉(zhuǎn)發(fā)的真正依據(jù),需要引入名字后綴的壓縮表示來共同標(biāo)識被聚合的路由.

Fig.1 An example for hierarchical name-based route aggregation圖1 層次化名字路由的聚合實(shí)例

為了實(shí)現(xiàn)全網(wǎng)路由聚合,最大程度地減少名字路由條目數(shù)量,在完成特定前綴的名字路由聚合后,需要將被聚合路由通告給其他網(wǎng)絡(luò)節(jié)點(diǎn),以便這些節(jié)點(diǎn)進(jìn)一步進(jìn)行路由聚合,與本地路由表壓縮的效果對比,路由聚合能夠在網(wǎng)絡(luò)層面真正大幅度縮減路由規(guī)模.

為了約減全網(wǎng)路由規(guī)模,提升層次化名字路由查表及轉(zhuǎn)發(fā)效率,本文對層次化名字路由聚合問題進(jìn)行了系統(tǒng)的分析,采用名字前綴和后綴壓縮表示共同標(biāo)識路由,提出了支持聚合的后綴壓縮表示機(jī)制,并以路由可用性為依據(jù)構(gòu)建了高可用的路由聚合機(jī)制,為NDN網(wǎng)絡(luò)投入實(shí)際部署提供了前提.主要包括如下工作.

(1)對層次化名字路由聚合問題進(jìn)行了研究,明確了將名字后綴納入聚合后的路由標(biāo)識的必要性.

(2)為了支持聚合路由在節(jié)點(diǎn)間的交換及進(jìn)一步的聚合,本文提出了一種支持更新及合并操作的后綴壓縮表示機(jī)制,堆疊計(jì)數(shù)布隆過濾器.

(3)為了限制后綴壓縮表示引起的冗余轉(zhuǎn)發(fā),我們依據(jù)聚合路由的可用性構(gòu)建了一套動(dòng)態(tài)名字路由聚合機(jī)制,在保證路由轉(zhuǎn)發(fā)正確性的前提下,最大程度地聚合名字路由,約減全面路由規(guī)模,提升了路由轉(zhuǎn)發(fā)效率,保證了海量在線內(nèi)容的高效路由轉(zhuǎn)發(fā).

本文首先在第1節(jié)對問題背景和相關(guān)研究進(jìn)行系統(tǒng)分析.第2節(jié)分析層次化名字路由問題.第3節(jié)提出一種可合并計(jì)數(shù)布隆過濾器,用于名字后綴的壓縮表示,和名字前綴一同標(biāo)識聚合路由,以便進(jìn)行本地路由聚合和全網(wǎng)聚合路由通告.在此基礎(chǔ)上,本文給出一套高可用的動(dòng)態(tài)路由聚合機(jī)制.最后,本文在真實(shí)網(wǎng)絡(luò)拓?fù)涞幕A(chǔ)上構(gòu)建仿真平臺,驗(yàn)證所提出的層次化名字路由聚合機(jī)制.

1 背景及研究現(xiàn)狀

1.1 NDN網(wǎng)絡(luò)

NDN根據(jù)層次化的名字而不是IP地址路由和轉(zhuǎn)發(fā)數(shù)據(jù)包.為了從NDN網(wǎng)絡(luò)中獲取需要的內(nèi)容,一個(gè)請求節(jié)點(diǎn) Consumer首先發(fā)送請求包(interest),其中包括被請求內(nèi)容的層次化名字.網(wǎng)絡(luò)中的路由節(jié)點(diǎn)收到該請求包后,分3步進(jìn)行處理.

(1)首先查找PIT表(pending interest table).PIT表記錄了之前轉(zhuǎn)發(fā)過的所有未被響應(yīng)的請求包信息,包括被請求內(nèi)容的名字、收到該請求的時(shí)間、接口及轉(zhuǎn)發(fā)接口.如果在 PIT表中找到了特定名字的請求信息,則意味著已經(jīng)轉(zhuǎn)發(fā)過該請求,將新的請求到達(dá)端口加入該表項(xiàng)的接口列表,收到內(nèi)容后一并處理;如果沒有找到,則建立新的PIT表項(xiàng).

(2)查找該節(jié)點(diǎn)的內(nèi)容緩存CS(content store),如果緩存了該內(nèi)容,則直接構(gòu)建相應(yīng)的內(nèi)容包(content),并從收到請求的接口返回內(nèi)容包.

(3)如果本地未緩存所請求內(nèi)容,則查找轉(zhuǎn)發(fā)表FIB(forwarding information base),從指定接口將該請求轉(zhuǎn)發(fā)給下一跳的各個(gè)鄰居.如果傳輸路徑上的節(jié)點(diǎn)都沒有緩存被請求內(nèi)容,則請求包最終將被轉(zhuǎn)發(fā)到內(nèi)容發(fā)布者 Producer,由內(nèi)容發(fā)布者構(gòu)建內(nèi)容包.內(nèi)容包中將包括內(nèi)容名字、內(nèi)容、內(nèi)容包簽名及簽名信息(發(fā)布者公鑰等).然后,同樣由內(nèi)容發(fā)布者從收到請求包的接口返回該內(nèi)容包.內(nèi)容包由轉(zhuǎn)發(fā)請求包的路由節(jié)點(diǎn)按照其對應(yīng) PIT表項(xiàng)中的記錄沿請求到達(dá)接口原路徑返回,最終達(dá)到內(nèi)容請求者Consumer.

各節(jié)點(diǎn) FIB中記錄全網(wǎng)所有在線內(nèi)容的轉(zhuǎn)發(fā)信息,路由條目數(shù)量巨大,為了保證正常的基于層次化名字的路由轉(zhuǎn)發(fā),必須有效地約減路由條目數(shù)量,提升路由查表及轉(zhuǎn)發(fā)效率.

1.2 相關(guān)研究分析

針對現(xiàn)有的TCP/IP網(wǎng)絡(luò)規(guī)模不斷增長的問題,大量工作試圖通過IP路由聚合和壓縮加以解決[15,16].其中,基于無類域間路由的TCP/IP網(wǎng)絡(luò)路由聚合機(jī)制利用子網(wǎng)號(IP前綴)代表被聚合的子網(wǎng)IP地址,有效地約簡了全網(wǎng)路由規(guī)模[15],保證了現(xiàn)有 TCP/IP網(wǎng)絡(luò)體系結(jié)構(gòu)的互聯(lián)網(wǎng)的可用性.其后,為了進(jìn)一步縮短路由查表時(shí)間,提升路由轉(zhuǎn)發(fā)效率,出現(xiàn)了大量本地路由表壓縮方面的研究.Degermark等人通過一種全新的 hash機(jī)制實(shí)現(xiàn)了路由IP前綴的壓縮[16].文獻(xiàn)[17]首次使用基本的Bloom過濾器實(shí)現(xiàn)了路由表查表過程的優(yōu)化.針對IPv4和IPv6路由查表過程,文獻(xiàn)[18]提出了一種編碼機(jī)制,在保證查找效率的同時(shí),降低了查找過程中的誤判率.然而,由于名字路由不再基于 IP實(shí)現(xiàn)路由,而是以內(nèi)容名字為路由標(biāo)識進(jìn)行路由,路由標(biāo)識的數(shù)量不可控,且結(jié)構(gòu)更為復(fù)雜,這些研究都無法直接應(yīng)用于層次化名字路由.

在 NDN路由轉(zhuǎn)發(fā)方面,張麗霞等人[7]進(jìn)行了大量基礎(chǔ)性研究.首先,在文獻(xiàn)[19]中提出了 NDN網(wǎng)絡(luò)的自適應(yīng)多路轉(zhuǎn)發(fā)機(jī)制,在轉(zhuǎn)發(fā)路徑選擇方面優(yōu)化了網(wǎng)絡(luò)傳輸效率;其次,文獻(xiàn)[20,21]分別提出了 NDN網(wǎng)絡(luò)中基于內(nèi)容名字的最短路徑優(yōu)先協(xié)議OSPFN和鏈路狀態(tài)協(xié)議NLSR,實(shí)現(xiàn)了基本的層次化名字路由.在所提出的這些關(guān)鍵問題的引導(dǎo)下,層次化名字路由機(jī)制得到了更為廣泛的研究[22-24],包括分層路由和路由可達(dá)性評估等機(jī)制被先后引入層次化名字路由過程.為了進(jìn)一步提升路由查表效率,文獻(xiàn)[10,13,14,25]通過哈希表、名字前綴的前綴樹索引和前綴樹壓縮等方式優(yōu)化了NDN路由節(jié)點(diǎn)路由查表(內(nèi)容名字查找)效率.文獻(xiàn)[11]通過GPU提升了前綴樹查找效率.為了實(shí)現(xiàn)板卡級別的包過濾,進(jìn)而優(yōu)化NDN網(wǎng)絡(luò)內(nèi)容獲取效率,文獻(xiàn)[12]利用布隆過濾器實(shí)現(xiàn)了網(wǎng)絡(luò)節(jié)點(diǎn)本地FIB表、PIT表和CS緩存的表項(xiàng)板卡級緩存,提升了轉(zhuǎn)發(fā)效率.然而,當(dāng)今互聯(lián)網(wǎng)已經(jīng)得到了全方位的應(yīng)用,在可以預(yù)期的互聯(lián)網(wǎng)擴(kuò)大應(yīng)用的大背景下,網(wǎng)絡(luò)信息數(shù)量將進(jìn)一步急劇增長[3],僅僅通過改進(jìn)本地路由查表過程、提升查表效率,并不能從根本上解決未來層次化名字路由在應(yīng)用中的路由規(guī)模問題,需要通過研究包括路由聚合在內(nèi)的全網(wǎng)路由規(guī)模約減機(jī)制來保證正常的路由查表及轉(zhuǎn)發(fā).

2 針對層次化名字路由的聚合過程分析

構(gòu)建在現(xiàn)有互聯(lián)網(wǎng)層次化網(wǎng)絡(luò)拓?fù)渲系腡CP/IP路由聚合機(jī)制,通過無類域間路由將子網(wǎng)IP地址聚合成對應(yīng)的子網(wǎng)網(wǎng)絡(luò)號以約減路由表規(guī)模,并將聚合后的路由通告給其他網(wǎng)絡(luò)節(jié)點(diǎn),以便進(jìn)行進(jìn)一步的聚合,最終形成高度聚合的聚合路由,在全網(wǎng)范圍內(nèi)約減路由規(guī)模.NDN的層次化名字路由根據(jù)路由名決定從哪幾個(gè)接口轉(zhuǎn)發(fā)內(nèi)容請求.下面通過一個(gè)例子分析名字路由聚合過程.注意,為了簡化分析,假設(shè)各節(jié)點(diǎn)路由的轉(zhuǎn)發(fā)接口均一致,不再特別說明.參照IP地址聚合機(jī)制,層次化名字聚合過程如圖2(a)所示.

Fig.2 Potential problems in hierarchical name-based route aggregation圖2 針對層次化名字的路由聚合過程的潛在問題

(1)在路由建立過程中,路由器R1和R2分別向路由器R3發(fā)送了針對名字A1/B1/C1和A1/B1/C2的路由通告.

(2)路由器R3收到這兩條路由通告后,聚合成路由表項(xiàng)A1/B1并添入其FIB(fowarding information base)表.

(3)路由器R3繼續(xù)向周邊路由器通告聚合后的路由表項(xiàng),最終路由器R4將收到的路由通告A1/B1與其本地路由A1/B2進(jìn)一步聚合,得到路由A1并通告給R5.

(4)在數(shù)據(jù)請求階段,路由器R5向R4發(fā)送請求包,請求名字為A1/B1/C1的內(nèi)容.

(5)路由器R4會根據(jù)路由表項(xiàng)A1/B1將請求包轉(zhuǎn)發(fā)給路由器R3.

(6)最終由路由器R3轉(zhuǎn)發(fā)給路由器R1,路由器R1返回相應(yīng)的數(shù)據(jù)內(nèi)容給請求者.

從上述過程可知,采用層次化名字聚合能夠縮小全網(wǎng)路由表規(guī)模,進(jìn)而提升路由查找效率.然而,如果僅僅采取與IP地址類似的聚合方式,那么當(dāng)請求沒有聚合過的內(nèi)容時(shí),這種聚合方式將會出現(xiàn)問題.還是在上述例子中,如果在步驟(4′)中,R5請求名字為A1/B1/C3的數(shù)據(jù),那么在步驟(5′)中,R4同樣會基于聚合后的路由表項(xiàng)將請求包轉(zhuǎn)發(fā)給路由器R3,但因?yàn)槁酚善鱎3中并沒有聚合名字為A1/B1/C3的路由信息,將導(dǎo)致數(shù)據(jù)請求失敗.

從上述實(shí)例可以看出,名字聚合不能完全采用IP路由聚合的方式.原因在于,IP路由地址是一種具有固定長度的由0和1組成的比特串,當(dāng)聚合后的IP地址前綴長度為k時(shí),其可能包含的被聚合后綴的取值最多只有232-k種,IP地址聚合時(shí)考慮到了所有可能的后綴取值,聚合后通過IP前綴信息標(biāo)識路由;與IP地址不同,內(nèi)容名字的取值可以是任意字符串.層次化名字的一個(gè)名字段在理論上有無窮多種取值,如圖2(a)中,名字前綴“A1/B1/”后面可以添加各種字符串(名字后綴),因此,以名字前綴為標(biāo)識的聚合結(jié)果無法囊括所有可能的名字后綴,即使請求名字同路由名字的前綴吻合,也無法保證可以根據(jù)該路由轉(zhuǎn)發(fā)請求并獲得對應(yīng)的內(nèi)容.因此,在名字路由聚合過程中,不僅需要抽離出待聚合路由的公共前綴來作為新的聚合路由前綴,同時(shí)為了準(zhǔn)確地將多條路由聚合為一條聚合路由,也需要生成這些待聚合路由名字后綴的壓縮表示,和聚合路由前綴一起標(biāo)識聚合路由,如圖2(b)所示.為了便于節(jié)點(diǎn)間交換聚合路由并進(jìn)一步聚合這些路由,實(shí)現(xiàn)全網(wǎng)路由聚合,后綴壓縮表示不僅需要能夠準(zhǔn)確地壓縮表示被聚合路由的名字后綴,還需要支持多個(gè)后綴壓縮表示的合并,以便構(gòu)建新的聚合路由.如圖2(b)中,R3完成對路由A1/B1/C1和A1/B1/C2的聚合后,會將聚合路由A1/B1:C(x)通告周邊節(jié)點(diǎn)R4,其中,C(x)為名字后綴C1和C2的壓縮表示,R4可以將收到的聚合路由A1/B1:C(x)和本地路由A1/B2:C(y)進(jìn)一步聚合,壓縮表示B1,B2的同時(shí),合并C(x),C(y),形成新的聚合路由A1:B(k)/C(x,y),聚合路由標(biāo)識由名字前綴A1和名字后綴壓縮表示B(k)/C(x,y)共同構(gòu)成.

考慮到全網(wǎng)海量內(nèi)容名字聚合后的巨大熵空間,過度的聚合必將帶來路由查表過程中的誤判,因此在名字聚合過程中,需要保證聚合后路由的可用性.在此基礎(chǔ)上,最大程度地聚合路由,縮減全網(wǎng)路由的規(guī)模.如何構(gòu)建準(zhǔn)確的后綴壓縮表示機(jī)制,并以聚合路由可用性為依據(jù)完善層次化名字路由的聚合機(jī)制,以更少的路由條目表征正確的路由轉(zhuǎn)發(fā)路徑,這將是一個(gè)極具挑戰(zhàn)性的問題,也是層次化名字路由聚合過程中必須解決的一個(gè)關(guān)鍵問題.

3 針對層次化名字路由的聚合機(jī)制

根據(jù)上一節(jié)的分析,為了構(gòu)建針對層次化名字路由的聚合機(jī)制,主要需要解決兩個(gè)問題.

(1)聚合路由標(biāo)識問題,具體來說就是名字后綴的壓縮表示問題;

(2)以路由可用性為基準(zhǔn)的路由聚合問題.

為了解決這些問題,本節(jié)首先對聚合過程中的核心問題——名字后綴壓縮表示問題進(jìn)行分析,并按照分析結(jié)論設(shè)計(jì)支持路由名字后綴壓縮表示的計(jì)數(shù)布隆過濾器——堆疊計(jì)數(shù)布隆過濾器,和名字前綴一起構(gòu)成聚合路由標(biāo)識;最后,在對NDN路由可達(dá)性分析的基礎(chǔ)上構(gòu)建一套高可用動(dòng)態(tài)路由聚合機(jī)制.

3.1 后綴壓縮表示問題分析

網(wǎng)絡(luò)內(nèi)容不斷發(fā)生變化,存在內(nèi)容源失效、內(nèi)容過期和內(nèi)容版本更新等情況,為了能夠動(dòng)態(tài)地添加并更新指向相關(guān)內(nèi)容的聚合路由,后綴壓縮表示機(jī)制不僅要表示特定內(nèi)容后綴的存在性,同時(shí)還要支持特定內(nèi)容后綴的刪除和更新.經(jīng)過多年的發(fā)展,布隆過濾器(Bloom filter,簡稱BF)已經(jīng)成為應(yīng)用最為廣泛的壓縮表示機(jī)制,衍生出了多種不同類型的布隆過濾器,其中,計(jì)數(shù)布隆過濾器(counting Bloom filter,簡稱 CBF)被設(shè)計(jì)用來同時(shí)支持添加操作和刪除操作[26].CBF通過將 BF的單比特位單元擴(kuò)展為用于計(jì)數(shù)的固定長度的多比特位單元,記錄各單元被重復(fù)設(shè)置為1的次數(shù)(所添加名字段的哈希值命中這一單元的次數(shù)),以便哈希到這些單元上的已添加元素需要被刪除時(shí),通過減小這些單元上的計(jì)數(shù)器值來實(shí)現(xiàn)元素刪除.除了用l比特的計(jì)數(shù)器替代基本布隆過濾器的單比特單元外,CBF完全等同于 BF,可以按照基本布隆過濾器的配置方法配置,包括配置過濾器單元(計(jì)數(shù)器)數(shù)、哈希函數(shù)數(shù)量等.CBF的哈希函數(shù)命中特定單元的最大次數(shù)c大于特定整數(shù)i的概率具有上界[27],可以根據(jù)這一上界配置CBF各單元計(jì)數(shù)器大小(比特位串長度l).通常情況下,4比特長的計(jì)數(shù)器即可滿足構(gòu)建CBF的需要,以極大的概率保證任一單元的計(jì)數(shù)器都不會超出其最大計(jì)數(shù)范圍.CBF可以滿足路由聚合過程中路由更新引起的動(dòng)態(tài)添加、刪除名字后綴的需要.為了優(yōu)化CBF的性能,在支持添加操作和刪除操作的同時(shí),降低存儲開銷和假陽性率,多種新型計(jì)數(shù)布隆過濾器先后被提出來.其中,Cohen等人提出了 Spectral Bloom Filter(SBF)[28],可以確保其任一單元的計(jì)數(shù)器都不會超出其最大計(jì)數(shù)值,但是與 CBF相比增加了的存儲開銷.文獻(xiàn)[29]基于d-left哈希提出dlCBF,與CBF相比,在同樣的假陽性率下優(yōu)化了存儲開銷.MPCBF[30]利用多級比特?cái)?shù)組在保證查詢效率的基礎(chǔ)上實(shí)現(xiàn)了CBF的功能,其存儲開銷和假陽性率與CBF相比都有所改善.

但是,如果利用現(xiàn)有各類計(jì)數(shù)布隆過濾器壓縮表示路由名字后綴,在全網(wǎng)路由聚合過程中,來自不同節(jié)點(diǎn)的相關(guān)路由后綴的壓縮表示將被進(jìn)一步聚合,這就需要將后綴壓縮表示(計(jì)數(shù)布隆過濾器)合并,而現(xiàn)有的各類計(jì)數(shù)布隆過濾器[27-30]都不支持多個(gè)計(jì)數(shù)布隆過濾器的合并操作.現(xiàn)有計(jì)數(shù)布隆過濾器都通過類似計(jì)數(shù)器的機(jī)制來記錄哈希函數(shù)重復(fù)命中各個(gè)單元的情況,多個(gè)計(jì)數(shù)布隆過濾器合并時(shí)可以選擇的合并算子包括加運(yùn)算、或運(yùn)算和異或運(yùn)算.首先,逐個(gè)單元進(jìn)行計(jì)數(shù)器值的按位或運(yùn)算和異或的運(yùn)算結(jié)果不能代表不同元素命中各單元的計(jì)數(shù)總和,因此無法用來支持計(jì)數(shù)布隆過濾器的合并.而對應(yīng)單元的計(jì)數(shù)器相加同樣也存在問題.例如,

(1)將計(jì)數(shù)布隆過濾器的計(jì)數(shù)器長度設(shè)為4比特,最大計(jì)數(shù)值為15.

(2)當(dāng)一個(gè)節(jié)點(diǎn)R周邊的16個(gè)節(jié)點(diǎn)中的一個(gè)Rj壓縮表示一個(gè)后綴名字段nsgx后,nsgx的k個(gè)哈希結(jié)果指向的計(jì)數(shù)布隆過濾器CBFj的計(jì)數(shù)器的值c1j,…,ckj均加 1,得到?cij≥1,i∈{1,2,…,k},j∈{1,2,…,16}.

(3)假設(shè)R周邊的16個(gè)節(jié)點(diǎn)都壓縮表示了nsgx,當(dāng)R需要進(jìn)一步聚合這條路由時(shí),需要合并來自16個(gè)鄰居的計(jì)數(shù)布隆過濾器CBF1,…,CBF16.如果采用相加的方式合并這些CBF,則需要將這些計(jì)數(shù)布隆過濾器各單元計(jì)數(shù)器的值相加,即ci=ci1+…+ci16.由于?cij≥1,故ci≥16,超出了計(jì)數(shù)器的最大計(jì)數(shù)范圍.

注意,這與上述計(jì)數(shù)器最大值的概率上界并不沖突.文獻(xiàn)[27]中上界的證明條件是計(jì)數(shù)布隆過濾器用于壓縮表示不重復(fù)元素,如果不同路由存在相同的名字后綴,計(jì)數(shù)布隆過濾器的計(jì)數(shù)器很快就會溢出.究其原因,現(xiàn)有計(jì)數(shù)布隆過濾器在壓縮表示被添加的元素的過程中,沒有保留足夠的信息,無法發(fā)現(xiàn)兩個(gè)壓縮表示結(jié)果中相同的元素,合并后壓縮表示結(jié)果中會出現(xiàn)重復(fù)元素.綜上所述,由于現(xiàn)有計(jì)數(shù)布隆過濾器不能有效地排除不同路由節(jié)點(diǎn)上記錄的相同名字后綴的影響,因此不能支持來自不同路由節(jié)點(diǎn)的名字路由的聚合操作.為了實(shí)現(xiàn)支持路由聚合的名字后綴壓縮表示機(jī)制,并和路由名字前綴一同標(biāo)識聚合路由,需要構(gòu)建一種全新的壓縮表示機(jī)制,該機(jī)制需要同時(shí)支持:(1)后綴名字段的動(dòng)態(tài)添加和刪除;(2)多個(gè)壓縮表示結(jié)果的合并.針對這兩個(gè)需求,我們在第3.2節(jié)中設(shè)計(jì)了一種全新的計(jì)數(shù)布隆過濾器——堆疊計(jì)數(shù)布隆過濾器(compounded counting Bloom filter,簡稱CCBF),用于被聚合路由名字后綴的壓縮表示.

3.2 堆疊計(jì)數(shù)布隆過濾器

為了支持名字后綴的動(dòng)態(tài)添加和刪除,同時(shí)支持多個(gè)壓縮表示的合并,我們在現(xiàn)有計(jì)數(shù)布隆過濾器思想的基礎(chǔ)上構(gòu)建的新的后綴壓縮表示機(jī)制需要:

(1)歸并重復(fù)后綴名字段的添加,支持多個(gè)壓縮表示的合并;

(2)記錄后綴名字段哈希結(jié)果命中過濾器各個(gè)單元的次數(shù),支持后綴名字段的動(dòng)態(tài)添加和刪除.

通過加運(yùn)算合并現(xiàn)有計(jì)數(shù)布隆過濾器時(shí),由于無法排除記錄在多個(gè)計(jì)數(shù)布隆過濾器中的重復(fù)后綴名字段,造成合并結(jié)果中會出現(xiàn)計(jì)數(shù)器計(jì)數(shù)溢出的情況.我們注意到,基本布隆過濾器可以通過按位或歸并重復(fù)名字段.這是由于在基本布隆過濾器中重復(fù)添加和合并重復(fù)名字段時(shí),重復(fù)的名字段的所有哈希結(jié)果都將命中過濾器中同一個(gè)單元,即使重復(fù)置1,也不會改變BF比特?cái)?shù)組的取值,從而屏蔽了重復(fù)名字段的影響.例如,將一個(gè)布隆過濾器BF1同另外一個(gè)布隆過濾器BF2合并的過程中,如果BF1和BF2中都添加了后綴名字段nsgx,nsgx的k個(gè)哈希結(jié)果分別指向的這兩個(gè)布隆過濾器的k個(gè)單元(位),b11,…,bk1和b12,…,bk2,全部被置 1.注意到,合并BF1和BF2后,仍有:

合并結(jié)果中同樣是這k個(gè)單元被置1,可以有效地歸并記錄在不同布隆過濾器中的重復(fù)名字段.根據(jù)這一觀察,我們利用基本布隆過濾器可以歸并重復(fù)元素的特點(diǎn),通過堆疊多個(gè)相同的基本布隆過濾器來構(gòu)建支持合并的計(jì)數(shù)布隆過濾器.多個(gè)基本布隆過濾器的特定位置的單元可以共同記錄該位置被所添加的后綴名字段的哈希結(jié)果命中的次數(shù)(每次將其中一個(gè)基本布隆過濾器的相應(yīng)單元置 1),從而構(gòu)建了一種全新的支持合并的計(jì)數(shù)布隆過濾器——堆疊計(jì)數(shù)布隆過濾器.CCBF通過偽隨機(jī)發(fā)生器使用多個(gè)基本布隆過濾器,在有效使用所包含的過濾器的同時(shí),保留了各單元被重復(fù)置1時(shí)過濾器的使用順序.

CCBF的數(shù)據(jù)結(jié)構(gòu)如圖3所示.

Fig.3 Framework of compounded counting Bloom flitter圖3 堆疊計(jì)數(shù)布隆過濾器的結(jié)構(gòu)

CCBF由g個(gè)比特?cái)?shù)組(長度為m)和它們按位或的結(jié)果數(shù)組orBarr構(gòu)成.其中,g的大小以能夠滿足計(jì)數(shù)需要為基準(zhǔn),本節(jié)后續(xù)將具體說明.orBarr是 CCBF的g個(gè)比特?cái)?shù)組按位或的結(jié)果,用于提升 CCBF的查詢效率.CCBF除了支持名字段的添加、刪除和查詢外,還支持多個(gè)CCBF的合并.下面對這些操作逐一加以說明.

(1)添加、刪除和查詢后綴名字段

CCBF在添加一個(gè)名字段nsg的過程中,針對k次哈希操作中的第j次哈希操作,利用偽隨機(jī)數(shù)生成器,根據(jù)哈希結(jié)果對應(yīng)位置單元(下標(biāo)為hashj(nsg)的單元)已經(jīng)被置1的比特?cái)?shù)組的數(shù)量,隨機(jī)選中g(shù)個(gè)比特?cái)?shù)組中的一個(gè)比特?cái)?shù)組barri(CCBF的第i個(gè)比特?cái)?shù)組),將其下標(biāo)為hashj(nsg)的單元置1.同時(shí),如果為名字段nsg的k個(gè)哈希結(jié)果選擇的比特?cái)?shù)組滿足:

則說明該名字段已經(jīng)添加過,放棄本次添加.注意,本文采用的偽隨機(jī)數(shù)發(fā)生器根據(jù)第hashj(nsg)個(gè)單元已經(jīng)被置 1的比特?cái)?shù)組的數(shù)量來選擇下一個(gè)要使用的比特?cái)?shù)組,具體操作就是針對各個(gè)單元隨機(jī)生成一個(gè)數(shù)組標(biāo)號的排列,并以這些排列為列構(gòu)建矩陣,在產(chǎn)生偽隨機(jī)數(shù)的過程中,以特定單元已經(jīng)被置1的數(shù)組的數(shù)量加1為行號,查找特定單元對應(yīng)的列上相應(yīng)行中記錄的數(shù)組標(biāo)號,返回該標(biāo)號代表的數(shù)組.因此,選中的比特?cái)?shù)組對應(yīng)的單元必然還沒有被置 1.這樣既避免了名字段的重復(fù)添加,又高效地實(shí)現(xiàn)了特定單元被置 1次數(shù)的計(jì)數(shù),為刪除名字段提供了前提.具體添加操作的計(jì)算過程如算法1所示.算法1中,利用偽隨機(jī)數(shù)發(fā)生器隨機(jī)選擇比特?cái)?shù)組,針對一個(gè)特定的哈希結(jié)果指向的單元,總能在g個(gè)比特?cái)?shù)組中找到一個(gè)數(shù)組,其對應(yīng)單元為0(證明見定理1),可以持續(xù)支持新數(shù)據(jù)的插入.

算法1.CCBF.add(nsg).

輸入:nsg.//待壓縮表示的后綴名字段

定理1.CCBF過濾器中包含g個(gè)比特?cái)?shù)組,令這些比特?cái)?shù)組第pj個(gè)單元被置為1的個(gè)數(shù)為cj,則cj大于等于g的概率可控,具有概率上界.

證明:令 CCBF能夠插入的名字段的最大值為n,其相應(yīng)的比特?cái)?shù)組長度為m,哈希函數(shù)個(gè)數(shù)為k,比特?cái)?shù)組數(shù)量為g,則g個(gè)比特?cái)?shù)組的第pj個(gè)單元被置為1的數(shù)量cj大于等于g的概率為

根據(jù)斯特林公式化簡可得:

由文獻(xiàn)[26]中的公式:

可知,在布隆過濾器的最優(yōu)配置中,n×k與m成線性關(guān)系,因此,n×k遠(yuǎn)大于g,公式(4)中根號內(nèi)的值小于 1.同時(shí),對第2項(xiàng)放大,得到公式(3)的一個(gè)松弛上界:

將公式(5)代入可得:

為g個(gè)比特?cái)?shù)組特定位pj被置為1的次數(shù)cj,得到g的概率上界. □

根據(jù)公式(7),當(dāng)g為16時(shí),CCBF任意一位全部被置1的概率為1.37×10-15×m,在通常網(wǎng)絡(luò)應(yīng)用中,這種情況不會出現(xiàn),即當(dāng)向包括16個(gè)比特?cái)?shù)組的CCBF添加名字段時(shí),總可以為k個(gè)哈希結(jié)果找到對應(yīng)單元為0的比特?cái)?shù)組,完成添加操作.

下面對添加操作的計(jì)算復(fù)雜度進(jìn)行分析和比較.算法1共進(jìn)行了k次哈希、k次隨機(jī)數(shù)組選擇及k次數(shù)組讀寫操作,最后將g個(gè)比特?cái)?shù)組按位或得到更新后的orBarr,計(jì)算復(fù)雜度為O(k×H1+k×H2+k+m×g),其中,H1為布隆過濾器哈希過程的時(shí)間開銷,H2為偽隨機(jī)數(shù)生成器選擇數(shù)組的時(shí)間開銷,偽隨機(jī)數(shù)生成器實(shí)際上就是在針對各單元的隨機(jī)數(shù)組標(biāo)號排列中查找一個(gè)元素,其計(jì)算復(fù)雜度遠(yuǎn)低于布隆過濾器的哈希函數(shù),而比特?cái)?shù)組按位或操作的復(fù)雜度m×g同樣小于布隆過濾器的哈希函數(shù)的復(fù)雜度,因此,本算法的計(jì)算復(fù)雜度規(guī)約為O(k×H1).現(xiàn)有的計(jì)算布隆過濾器,包括CBF、SBF、dlCBF和MPCBF,添加新元素時(shí)直接查找并更新對應(yīng)的計(jì)數(shù)單元,而本算法還要通過額外的偽隨機(jī)生成器選擇計(jì)數(shù)單元對應(yīng)的比特?cái)?shù)組,雖然計(jì)算復(fù)雜度均為O(k×H1),但算法1的計(jì)算開銷將近似 2倍于上述 4類計(jì)數(shù)布隆過濾器的添加操作的計(jì)算開銷.當(dāng)然,鑒于現(xiàn)有布隆過濾器哈希函數(shù)的高效性[26],CCBF添加操作的總體計(jì)算開銷仍較小,不會影響CCBF的應(yīng)用.

布隆過濾器作為一種壓縮表示機(jī)制,除了可以節(jié)省存儲空間外,最關(guān)鍵的是可以提升后綴名字段存在性查詢的效率.與添加和刪除操作相比,后綴名字段(路由)查詢是路由聚合機(jī)制中最常見的操作,為了優(yōu)化聚合路由(CCBF的名字段)查詢效率,我們在 CCBF中添加了一個(gè)記錄 CCBF中g(shù)個(gè)比特?cái)?shù)組按位或的結(jié)果的數(shù)組orBarr,在進(jìn)行查詢的過程中,無需逐一查看g個(gè)比特?cái)?shù)組,判斷哈希結(jié)果對應(yīng)單元是否為 1,而是直接查看orBarr的對應(yīng)單元是否為 1即可,具體查詢操作如算法 2所示,查詢操作的復(fù)雜度完全等價(jià)于基本布隆過濾器查詢操作的復(fù)雜度,與CBF和MPCBF的查詢過程類似,可以直接定位各個(gè)哈希函數(shù)對應(yīng)的單元并進(jìn)行查詢,具有相同的計(jì)算復(fù)雜度.由于 SBF在查詢過程中在通過哈希函數(shù)定位計(jì)數(shù)單元后仍需要通過索引最終找到這些計(jì)數(shù)單元,以完成查找,dlCBF需要在d個(gè)分區(qū)中逐一定位并查找各個(gè)哈希對應(yīng)的單元,存在重復(fù)操作.因此,SBF、dlCBF查詢效率低于CBF、MPCBF以及算法2.

算法2.CCBF.query(nsg).

輸入:nsg.//待查詢的后綴名字段

CCBF刪除操作的計(jì)算過程類似于添加操作的計(jì)算過程,這里不再贅述,僅就其中的關(guān)鍵操作步驟進(jìn)行說明.首先確認(rèn)該名字段可以刪除(類似算法 2的查找過程);然后,通過偽隨機(jī)數(shù)生成器定位上一次添加操作中各個(gè)哈希函數(shù)操作的單元所在的比特?cái)?shù)組,將這些比特?cái)?shù)組對應(yīng)單元清零,并更新orBarr,完成名字段刪除操作.因此,CCBF刪除操作的計(jì)算復(fù)雜度與添加操作類似,為O(k×H1).與其他計(jì)數(shù)布隆過濾器相比,CCBF的刪除過程需要通過偽隨機(jī)數(shù)發(fā)生器找到需要進(jìn)行單元清零操作的比特?cái)?shù)組,因此,刪除操作的計(jì)算開銷近似 2倍于其他計(jì)數(shù)布隆過濾器的刪除操作的開銷.

(2)合并操作

不同于其他現(xiàn)有計(jì)數(shù)布隆過濾器,CCBF支持合并操作,即將多個(gè)配置完全相同的CCBF合并為1個(gè),以便應(yīng)用于類似路由聚合這樣需要?dú)w并已有名字段的場景.多個(gè)CCBF的合并操作相當(dāng)于將這些CCBF壓縮表示的名字段(添加的元素)合并,即等同于在一個(gè)CCBF中添加其他CCBF中壓縮表示過的名字段.CCBF中的偽隨機(jī)數(shù)發(fā)生器可以確保哈希結(jié)果對應(yīng)單元置 1時(shí)選擇的比特?cái)?shù)組有固定的順序,CCBF中添加后綴名字段(元素)的順序不會影響各個(gè)比特?cái)?shù)組的取值,詳見定理2.因此,按照不同CCBF比特?cái)?shù)組的標(biāo)號,可以按順序合并各個(gè)比特?cái)?shù)組(按位或,與BF的合并操作相同),實(shí)現(xiàn)多個(gè)CCBF的合并.

當(dāng)然,多個(gè)CCBF合并后壓縮表示的名字段數(shù)量仍然受到其比特?cái)?shù)組數(shù)量g和長度m的限制.以兩個(gè)CCBF的合并過程為例,合并過程主要是將兩個(gè)CCBF中的g個(gè)比特?cái)?shù)組兩兩按位進(jìn)行或操作,同時(shí)將兩者的orBarr也按位或.具體如算法3所示.

算法3.CCBF.combine(other).

輸入:other.//待合并的另外一個(gè)CCBF過濾器,兩個(gè)CCBF的配置完全相同,且合并后的后綴數(shù)沒用超過CCBF的容量n

其中,為了保證合并后不會超過CCBF的配置容量n,CCBF利用estSize函數(shù)估計(jì)當(dāng)前已添加的名字段的數(shù)量(已添加名字段數(shù)量).CCBF每次添加1個(gè)名字段時(shí)會有k位被置1,因此可以利用g個(gè)比特?cái)?shù)組中1的總數(shù)除以k,得到已經(jīng)添加的名字段的數(shù)量,estSize函數(shù)的計(jì)算過程如公式(8)所示。

其中,g和k為CCBF配置的比特?cái)?shù)組數(shù)量和哈希函數(shù)數(shù)量,比特?cái)?shù)組的sum4ones函數(shù)可以計(jì)算它其中被置1的單元的數(shù)量.算法3的計(jì)算過程包括估計(jì)已添加名字段總數(shù)和合并比特?cái)?shù)組兩部分,其中,

· 估計(jì)已添加名字段的復(fù)雜度為Ο(m×g),其中,m為比特?cái)?shù)組長度,g為比特?cái)?shù)組數(shù)量(最大計(jì)數(shù)范圍);

· 合并比特?cái)?shù)組的復(fù)雜度也是Ο(m×g).

因此,算法3總的計(jì)算復(fù)雜度為Ο(m×g).注意,現(xiàn)有其他計(jì)數(shù)布隆過濾器均無法支持合并操作.

定理2.CCBF中添加元素的順序不會影響CCBF中各個(gè)比特?cái)?shù)組的取值.

證明:對于一組元素nsg1,…nsgi,…,nsgn,將其按順序添加到一個(gè) CCBF中.不失一般性,假設(shè)有兩個(gè)名字段——nsgx和nsgy,其哈希結(jié)果命中了 CCBF的第j個(gè)單元,CCBF中的偽隨機(jī)數(shù)發(fā)生器以確定順序在barr1,…,barrg中選中兩個(gè)比特?cái)?shù)組,將其第j個(gè)單元置1.這一過程中,隨機(jī)數(shù)發(fā)生器選中的下一個(gè)比特?cái)?shù)組的依據(jù)是當(dāng)前第j個(gè)單元被置1的比特?cái)?shù)組的個(gè)數(shù).因此,如果首先添加nsgx,第j個(gè)單元被置1的比特?cái)?shù)組的個(gè)數(shù)為0,隨機(jī)數(shù)發(fā)生器選中barr(1),將barr(1)[j]置 1.當(dāng)添加nsgy時(shí),選中barr(2),將barr(2)[j]置 1.同樣,如果先添加nsgy,將對barr(1)[j]置1,然后添加nsgx時(shí),將對barr(2)[j]置1.無論nsgx和nsgy的添加順序如何,添加結(jié)果都是barr(1)[j]和barr(2)[j]被置1.對特定單元的多次加1操作的順序不影響該單元使用,因此,CCBF中添加名字段的順序不會影響CCBF中各個(gè)比特?cái)?shù)組的取值. □

綜上所述,堆疊計(jì)數(shù)布隆過濾器可以高效地完成名字段的添加、刪除和查詢,其計(jì)算復(fù)雜度基本與現(xiàn)有計(jì)數(shù)布隆過濾器等同,其中,路由過程中最為頻繁的查詢操作的效率優(yōu)于或等同于其他計(jì)數(shù)布隆過濾器.同時(shí),堆疊計(jì)數(shù)布隆過濾器 CCBF支持高效的多過濾器合并,為聚合路由后綴合并(及其他需要合并多個(gè)壓縮表示的場景)奠定了基礎(chǔ).CCBF空間復(fù)雜度為Ο(m×g),與CBF的空間復(fù)雜度Ο(m×log2g)相比,使用的存儲空間更多.同樣地,與 dlCBF和 MPCBF相比也需要更多的存儲空間(除 SBF使用的存儲空間隨添加元素增長外,dlCBF和MPCBF都在CBF的基礎(chǔ)上優(yōu)化了存儲空間開銷[29,30]),但是根據(jù)定理1,g的取值在實(shí)際應(yīng)用中具有上界(通常情況下為 16),因此,CCBF空間復(fù)雜度可控,在當(dāng)前網(wǎng)絡(luò)設(shè)備存儲空間不斷擴(kuò)大的背景下,完全可以應(yīng)用于各類互聯(lián)網(wǎng)應(yīng)用場景.在假陽性率方面,CCBF中哈希函數(shù)定位數(shù)組單元的方式與BF和CBF相同,函數(shù)個(gè)數(shù)k和數(shù)組長度m的配置也與BF和CBF相同[26],因此,CCBF中添加一個(gè)元素時(shí),k個(gè)哈希結(jié)果均發(fā)生碰撞的概率(假陽性率)與BF和CBF完全相同.雖然CCBF的假陽性率高于優(yōu)化了假陽性率的SBF、dlCBF和MPCBF,但是路由聚合過程中,假陽性的出現(xiàn)只會增加冗余轉(zhuǎn)發(fā)數(shù)量,不會引起轉(zhuǎn)發(fā)錯(cuò)誤,并非路由聚合過程中的首要因素,不會影響CCBF在聚合路由后綴壓縮表示中的應(yīng)用.

綜上所述,CCBF的主要設(shè)計(jì)目標(biāo)是實(shí)現(xiàn)多個(gè)CCBF的合并,以便支持路由聚合操作.在此基礎(chǔ)上,CCBF優(yōu)化了其查詢效率,為構(gòu)建高效的路由聚合機(jī)制提供了前提.在基于CCBF的后綴壓縮表示的基礎(chǔ)上,可以將指向同一接口的多條具有公共名字前綴的路由聚合為 1條聚合路由,用公共名字前綴和后綴壓縮表示共同標(biāo)識聚合路由(如圖1所示),有效地避免了第2節(jié)中指出的僅采用路由名字前綴來標(biāo)識路由時(shí)出現(xiàn)的路由錯(cuò)誤,構(gòu)建了準(zhǔn)確、高效的路由標(biāo)識.

3.3 基于路由可達(dá)性的動(dòng)態(tài)名字路由聚合機(jī)制

在上述層次化名字聚合路由標(biāo)識的基礎(chǔ)上,本文利用路由可達(dá)性度量聚合路由可用性,并作為路由聚合條件,將多條穩(wěn)定可達(dá)的具有公共名字前綴的路由(包括其他節(jié)點(diǎn)通告的路由)聚合為一條聚合路由;當(dāng)可達(dá)性下降后,進(jìn)行解聚合,還原被聚合路由,降低聚合程度,提升路由可達(dá)性;聚合和解聚合都需要通告周邊鄰居節(jié)點(diǎn).按照這一動(dòng)態(tài)聚合方式,本文構(gòu)建了一套基于路由可達(dá)性的動(dòng)態(tài)名字路由聚合機(jī)制.

本文之所以將路由可達(dá)性作為路由聚合的條件,其原因是聚合路由壓縮表示了被聚合路由的名字后綴(或后綴壓縮表示),將不可避免地在路由查找過程中引入假陽性,將沒有聚合過的路由納入聚合路由查找結(jié)果,進(jìn)而在NDN網(wǎng)絡(luò)中帶來冗余的轉(zhuǎn)發(fā).由于NDN網(wǎng)絡(luò)采用多路轉(zhuǎn)發(fā)機(jī)制,因此假陽性引起的冗余轉(zhuǎn)發(fā)不會影響正常的內(nèi)容獲取,僅僅會加大網(wǎng)絡(luò)負(fù)載.當(dāng)然,過大的網(wǎng)絡(luò)負(fù)載同樣會影響網(wǎng)絡(luò)效率,甚至?xí)窒酚删酆虾舐酚梢?guī)?？s減帶來的效率提升.如果假陽性問題引起的網(wǎng)絡(luò)負(fù)載過大,將會進(jìn)一步引起網(wǎng)絡(luò)擁塞等問題,因此,我們需要最大程度地保證轉(zhuǎn)發(fā)的正確性,同時(shí),通過路由聚合減小路由規(guī)模,提升網(wǎng)絡(luò)效率.其中,為了回滾聚合路由,需要在低速存儲中備份被聚合路由,在減小路由節(jié)點(diǎn)高速內(nèi)存空間的同時(shí),實(shí)現(xiàn)了基于路由可達(dá)性的動(dòng)態(tài)聚合過程.本文名字路由聚合記錄如圖4所示.

Fig.4 An example for dynamic route aggregation圖4 動(dòng)態(tài)路由聚合過程實(shí)例

NDN網(wǎng)絡(luò)節(jié)點(diǎn)的不同接口可以獲取不同內(nèi)容,因此,本文的聚合機(jī)制在聚合相關(guān)路由的同時(shí),保留了各個(gè)接口的獨(dú)立記錄.為每條聚合路由針對不同接口設(shè)置獨(dú)立的后綴壓縮表示單元和相應(yīng)的可達(dá)性統(tǒng)計(jì)單元,形成聚合路由的標(biāo)識二元組結(jié)構(gòu):〈路由前綴;轉(zhuǎn)發(fā)接口信息〉,其中,轉(zhuǎn)發(fā)接口信息中記錄了接口ID、路由后綴壓縮表示、轉(zhuǎn)發(fā)延遲統(tǒng)計(jì)和可達(dá)性統(tǒng)計(jì)等狀態(tài)信息(如圖4所示).可達(dá)性統(tǒng)計(jì)為RP(faceID),其中,faceID為相應(yīng)的接口ID.可達(dá)性統(tǒng)計(jì)值為最近轉(zhuǎn)發(fā)出去的請求的響應(yīng)比,代表路由可用性的統(tǒng)計(jì)結(jié)果,如公式(9)所示.

其中,n(t-1)為t-1時(shí)刻總共發(fā)出的內(nèi)容請求包數(shù)量,ns(t)為t時(shí)刻收到的內(nèi)容響應(yīng)包數(shù)量.其中,通過卷積運(yùn)算淘汰舊的統(tǒng)計(jì)信息,提升當(dāng)前請求響應(yīng)情況在統(tǒng)計(jì)結(jié)果中的比重.針對接口faceID,RP(faceID)準(zhǔn)確地反映了依據(jù)聚合路由從該接口轉(zhuǎn)發(fā)請求、獲取內(nèi)容的可能性,可以作為評估聚合路由可用性的標(biāo)準(zhǔn).根據(jù)文獻(xiàn)[31]中的相關(guān)定理,當(dāng)節(jié)點(diǎn)間連通概率大于等于lg(N)/N時(shí)(N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)),網(wǎng)絡(luò)為強(qiáng)連通網(wǎng)絡(luò).因此,我們可以將這一條件作為判斷路由可達(dá)性的閾值,如果所有RP(faceID)都大于lg(N)/N,則可以獲取分布在任意網(wǎng)絡(luò)節(jié)點(diǎn)上的內(nèi)容.

當(dāng)一組具有公共前綴的聚合路由在所有接口上的可達(dá)性都達(dá)到了閾值,且持續(xù)了從某個(gè)時(shí)刻t起的兩個(gè)時(shí)刻時(shí),則這些路由被認(rèn)為是穩(wěn)定的路由,可以和其他具有公共前綴的穩(wěn)定路由一同進(jìn)一步聚合新的聚合路由.這種延遲決策機(jī)制可以避免聚合過程中的抖動(dòng)現(xiàn)象(頻繁重復(fù)聚合和解聚合的循環(huán)).同樣地,聚合路由兩個(gè)時(shí)刻內(nèi)持續(xù)不可用,則需要將其分解為之前被聚合的路由,以提升路由準(zhǔn)確性,改善路由可達(dá)情況.為了支撐聚合路由回滾,需要在各個(gè)節(jié)點(diǎn)保留如圖4所示的線索樹結(jié)構(gòu),在聚合路由的同時(shí)保留被聚合路由信息,以便更新和回滾聚合路由.其中,當(dāng)前路由線索是當(dāng)前使用的聚合路由的線索,當(dāng)需要更新和回滾路由時(shí),可以快速找到相應(yīng)的聚合路由,并回滾或更新相關(guān)被聚合路由.本文的動(dòng)態(tài)聚合機(jī)制可以在保證路由可用性的前提下最大程度地聚合路由,縮小全網(wǎng)路由規(guī)模,提升層次化名字路由效率.

4 實(shí)驗(yàn)評估

4.1 方案部署與實(shí)現(xiàn)

我們在NDN網(wǎng)絡(luò)的仿真平臺ndnSIM[32]的基礎(chǔ)上實(shí)現(xiàn)了本文針對層次化名字路由的聚合機(jī)制.

· 首先,我們對ndnSIM的FIB模塊進(jìn)行了修改.現(xiàn)有的ndnSIM中,每條路由包含路由名字前綴和轉(zhuǎn)發(fā)接口信息.基于本文動(dòng)態(tài)路由聚合機(jī)制,我們在轉(zhuǎn)發(fā)接口信息中添加了后綴壓縮表示 C和可達(dá)性統(tǒng)計(jì)RP(見公式(9)).RP中的統(tǒng)計(jì)值n(t-1)是在查表轉(zhuǎn)發(fā)請求時(shí)計(jì)數(shù),而nr(t)是下一個(gè)時(shí)刻收到的內(nèi)容包的數(shù)量.根據(jù)不同的預(yù)定容量n,用于壓縮表示后綴名字段的CCBF按布隆過濾器最優(yōu)配置設(shè)置比特?cái)?shù)組長度m及哈希函數(shù)個(gè)數(shù)k[26],同時(shí),根據(jù)本文第3.2節(jié)的分析,比特?cái)?shù)組數(shù)量被設(shè)置為16.在此基礎(chǔ)上,FIB模塊周期性更新 RP,根據(jù)更新過的 RP分析現(xiàn)有路由的可用性,將持續(xù)可用的路由進(jìn)行進(jìn)一步聚合,得到新的聚合路由,并周期性地通告周邊節(jié)點(diǎn).同時(shí)更新在低速外部存儲中的記錄路由聚合過程的數(shù)據(jù)結(jié)構(gòu)(如圖4所示),以備聚合路由回滾時(shí)還原其中備份的路由信息.

· 其次,我們修改了轉(zhuǎn)發(fā)模塊ndn-forwarding-strategy.實(shí)現(xiàn)了基于名字前綴和后綴壓縮表示的轉(zhuǎn)發(fā)機(jī)制.

仿真平臺在本地計(jì)算機(jī)上部署,其配置如下:Ubuntu 13.04,內(nèi)核版本 3.8.8,Intel Core i7 3.4G CPU,DDR3 1866 16G內(nèi)存,1TB硬盤.為了保證仿真結(jié)果真實(shí)、可靠,我們采用了一個(gè)真實(shí)的網(wǎng)絡(luò)拓?fù)洹獨(dú)W洲EBONE網(wǎng)絡(luò)拓?fù)鋄33],包括279個(gè)節(jié)點(diǎn)、731條邊,其中包括65個(gè)邊界網(wǎng)關(guān)節(jié)點(diǎn)、45個(gè)網(wǎng)關(guān)節(jié)點(diǎn)和169個(gè)邊緣路由節(jié)點(diǎn).在邊緣節(jié)點(diǎn)中,我們隨機(jī)選擇了10個(gè)節(jié)點(diǎn)作為內(nèi)容發(fā)布節(jié)點(diǎn)producer,實(shí)驗(yàn)中請求的各類內(nèi)容全部由這10個(gè)節(jié)點(diǎn)發(fā)布.另外,選擇了 30個(gè)節(jié)點(diǎn)作為內(nèi)容請求方 consumer,內(nèi)容請求服從參數(shù)α為 0.6的 Zipf-Mandelbrot分布,即被請求的多數(shù)內(nèi)容為熱門內(nèi)容,其他內(nèi)容很少被請求.為了全面驗(yàn)證本文路由聚合機(jī)制的有效性,實(shí)驗(yàn)中使用了多個(gè)不同規(guī)模的數(shù)量集,這些數(shù)據(jù)集的具體信息見表1.

Table 1 Datasets表1 數(shù)據(jù)集

在此基礎(chǔ)上,通過對這些數(shù)據(jù)進(jìn)行組合,我們可以得到各種規(guī)模的名字?jǐn)?shù)據(jù)集.在其基礎(chǔ)上,我們對本文路由聚合機(jī)制的有效性進(jìn)行了全面的評估.首先比較了路由聚合前后的路由表規(guī)模;其次,通過與 NDN原生路由查表機(jī)制以及利用CBF壓縮路由表的對比方案比較,給出了路由聚合前后的路由查表效率的比較;最后,通過對比分析了本文路由聚合機(jī)制帶來的假陽性問題.

4.2 聚合前后路由表規(guī)模對比分析

路由聚合的目標(biāo)是減少路由條目數(shù)量,從而提升路由查表效率,進(jìn)而優(yōu)化網(wǎng)絡(luò)傳輸效率.同時(shí),路由條目的減少還會減少路由設(shè)備內(nèi)存的使用,降低 NDN網(wǎng)絡(luò)部署成本.為了驗(yàn)證本文路由聚合機(jī)制的聚合效果,我們在數(shù)據(jù)集Alexa top 1M上比較了各個(gè)路由節(jié)點(diǎn)在同一時(shí)刻采用聚合后的路由條目數(shù)量和不采用聚合的情況下路由條目數(shù)量的比值R,在2 000s內(nèi)對279個(gè)路由器每隔6s記錄一次R值,仿真結(jié)果如圖5所示.

Fig.5 Effection on FIB size reduction of route aggregation圖5 路由聚合對路由表規(guī)模的影響

仿真過程中,隨著時(shí)間Time的推移,路由聚合程度不斷提升,路由規(guī)模不斷縮小,在1 400s附近,全網(wǎng)路由聚合達(dá)到穩(wěn)定狀態(tài).全部 279個(gè)節(jié)點(diǎn)中,在全網(wǎng)路由聚合完成后,路由條目數(shù)量至少壓縮了 60%,平均壓縮了75.47%,路由聚合對路由規(guī)模的縮減效果明顯.注意,由于現(xiàn)有數(shù)據(jù)集中多數(shù)名字(URL)只有 2級,如果應(yīng)用于實(shí)際部署的NDN網(wǎng)絡(luò)中,路由名字層次變化更多,路由聚合效果也會更為顯著.

4.3 聚合路由效率分析

作為影響網(wǎng)絡(luò)傳輸效果的關(guān)鍵因素,路由查表效率直接影響網(wǎng)絡(luò)數(shù)據(jù)包轉(zhuǎn)發(fā)延時(shí).路由聚合主要通過減少路由條目數(shù)量(路由表規(guī)模)來提升路由查表效率,進(jìn)而縮小網(wǎng)絡(luò)數(shù)據(jù)包轉(zhuǎn)發(fā)延時(shí).利用本文路由聚合機(jī)制,可以將多條具有公共前綴的層次化名字路由聚合為單條聚合路由,并利用這些路由的公共名字前綴和后綴壓縮表示來共同標(biāo)識該聚合路由.因此,與未進(jìn)行聚合的層次化名字路由相比,本文的路由聚合機(jī)制在縮短名字前綴查找時(shí)間的同時(shí),也引入了路由后綴的查找過程.為了驗(yàn)證本文聚合過程對路由查表時(shí)間的影響,我們首先針對不同規(guī)模Ns的名字路由(1萬、10萬和100萬)進(jìn)行路由聚合,并比較聚合前后各路由的查表時(shí)間總和LTime.實(shí)驗(yàn)結(jié)果如圖6(a)所示,圓形點(diǎn)線代表未聚合路由查表時(shí)間總和,方形點(diǎn)線為本文聚合路由查表時(shí)間總和.可以看出,未被聚合的路由的查表時(shí)間與路由規(guī)模成正比例關(guān)系,隨著路由規(guī)模Ns的增長線性增加;而聚合后路由查找基本不受路由規(guī)模增長的影響,僅表現(xiàn)出1s的差異,如圖6(a)所示.究其原因,主要是由于聚合后減小了前綴數(shù)量及前綴查找時(shí)間;同時(shí),本文在后綴壓縮表示查詢方面的優(yōu)化(為CCBF添加16個(gè)比特?cái)?shù)組按位或得到的歸并結(jié)果orBarr)也避免了大量后綴查詢時(shí)延的引入.

Fig.6 Comparison of route lookup time圖6 路由查找效率對比

為了進(jìn)一步驗(yàn)證本文路由聚合機(jī)制的查表效率,我們在 CBF的基礎(chǔ)上構(gòu)建了一套路由壓縮機(jī)制作為對比方案,采用與本文的聚合路由相同的前綴和CBF壓縮表示的路由后綴共同標(biāo)識壓縮后的路由.壓縮后的路由規(guī)模與本文路由聚合后的路由規(guī)模相同,通過這一方式對比驗(yàn)證本文聚合路由查表效率.如圖6(b)所示,方形點(diǎn)線為CBF的查詢時(shí)間LTime-CBF,圓形點(diǎn)線為本文CCBF的查詢時(shí)間LTime-CCBF.在不同規(guī)模的路由表上,本文方案的查表時(shí)間始終只有對比方案的一半,本文建立在orBarr上的查詢過程的效率要優(yōu)于CBF的查詢效率.

同時(shí),我們對比了聚合前后路由更新效率(如圖7所示),路由更新時(shí)間等于所有路由的查找、刪除和添加操作的總和,用UpTime代表.圖7(a)中,圓形點(diǎn)線為未聚合路由總更新時(shí)間,方形點(diǎn)線為本文方案路由總更新時(shí)間.未聚合路由的整體更新時(shí)間都隨路由規(guī)模Ns的增長呈線性增長,本文路由聚合機(jī)制的更新時(shí)間增加較慢,路由規(guī)模對路由更新效率的影響同樣存在.為了進(jìn)一步評估本文機(jī)制的路由更新效率,圖7(b)中,我們對比了本文機(jī)制的路由更新時(shí)間和基于CBF的對比方案的路由更新時(shí)間.圓形點(diǎn)線為本文機(jī)制的總路由更新時(shí)間,方形點(diǎn)線為對比方案的總路由更新時(shí)間.兩個(gè)方案的總路由更新時(shí)間都隨路由規(guī)模Ns的增長呈線性增長,本文路由更新時(shí)間略小于對比方案路由更新時(shí)間的 2倍,雖然與路由查表時(shí)間相比,本文的路由聚合機(jī)制的路由更新時(shí)間較長,但路由更新不是網(wǎng)絡(luò)路由轉(zhuǎn)發(fā)過程中最關(guān)鍵的操作,操作頻率較低,且獨(dú)立處理,基本不影響路由查表過程.

Fig.7 Comparison of route updating time圖7 路由更新時(shí)間對比

4.4 假陽性分析

本文的聚合標(biāo)識在使用路由名字前綴的同時(shí),還引入了基于CCBF的后綴壓縮表示.CCBF本身可能會在查詢過程中引入假陽性,即查詢到未被壓縮表示過的名字段.假陽性在路由聚合問題的背景下,將會引發(fā)路由查詢的假陽性誤判,將數(shù)據(jù)包發(fā)往沒有通告過相關(guān)路由的接口.注意,假陽性不會影響數(shù)據(jù)包從通告過該路由的接口正常轉(zhuǎn)發(fā),僅僅是增加了冗余的路由轉(zhuǎn)發(fā).本節(jié)實(shí)驗(yàn)驗(yàn)證了本文后綴壓縮表示所采用的 CCBF布隆過濾器的假陽性情況,并與基于CBF的對比方案的假陽性進(jìn)行了對比.在布隆過濾器的配置過程中,本文為各個(gè)過濾器設(shè)定的最大假陽性率均為0.01.圖8中,菱形點(diǎn)線為CCBF在不同規(guī)模數(shù)據(jù)集下的查詢假陽性數(shù)Fp-CCBF,方形點(diǎn)線為對比方案在不同規(guī)模數(shù)據(jù)集下的查詢假陽性數(shù) FP-CBF.兩種布隆過濾器在不同規(guī)模的數(shù)據(jù)集上的假陽性值相同.

為了進(jìn)一步分析假陽性的出現(xiàn)情況,分析兩種方案在不同的添加比例Rfill下的假陽性變化情況,本文針對3種不同規(guī)模的數(shù)據(jù)集(1萬、10萬和100萬)進(jìn)行了實(shí)驗(yàn).其中,Rfill=nc/n,n為布隆過濾器容量(分別取1萬、10萬和100萬),nc為添加到布隆過濾器的名字段數(shù)量.如圖9所示,在不同規(guī)模的數(shù)據(jù)集下,兩種方案的假陽性查詢數(shù)量在Rfill達(dá)到0.85后出現(xiàn)了假陽性查詢,并在Rfill到達(dá)1時(shí)達(dá)到最大值,兩種方案的假陽性查詢數(shù)量始終保持相同.本文方案在查詢假陽性方面等同于基于計(jì)數(shù)布隆過濾器CBF的對比方案,沒有帶來額外的假陽性查詢.

Fig.8 False positive under datasets with different size圖8 不同規(guī)模數(shù)據(jù)集下的假陽性

Fig.9 False positive with differentRfill圖9 不同Rfill下的假陽性

5 結(jié) 論

為了實(shí)現(xiàn)針對層次化名字路由的聚合機(jī)制,進(jìn)而優(yōu)化NDN等信息中心網(wǎng)絡(luò)的傳輸效率,本文首先分析了層次化名字路由的聚合問題,明確了路由聚合過程中需要同時(shí)利用路由名字前綴和后綴壓縮表示來共同標(biāo)識聚合后的路由.為了實(shí)現(xiàn)對名字后綴的壓縮標(biāo)識,同時(shí)在路由聚合過程中通告和進(jìn)一步聚合(合并)這些后綴壓縮標(biāo)識,本文提出了一種全新的計(jì)數(shù)布隆過濾器 CCBF.CCBF在支持多過濾器合并的同時(shí),還優(yōu)化了查詢效率.在此基礎(chǔ)上,本文進(jìn)一步提出了面向路由可達(dá)性的動(dòng)態(tài)路由聚合機(jī)制,在保證路由可達(dá)性的前提下最大化聚合路由.我們在真實(shí)網(wǎng)絡(luò)拓?fù)浼皵?shù)據(jù)集上構(gòu)建了實(shí)驗(yàn)環(huán)境,驗(yàn)證了本文路由聚合機(jī)制的有效性,本文路由聚合機(jī)制通過有效聚合路由,以較小的冗余路由轉(zhuǎn)發(fā)(假陽性路由查詢)為代價(jià),減小了路由規(guī)模,優(yōu)化了網(wǎng)絡(luò)傳輸效率,為NDN等信息中心網(wǎng)絡(luò)投入實(shí)際應(yīng)用提供了前提.

本文的路由聚合程度由路由可達(dá)性動(dòng)態(tài)決定.作為影響可達(dá)性的關(guān)鍵因素,如果能夠有效地降低 CCBF的假陽性查詢結(jié)果,則不但可以避免過多的冗余轉(zhuǎn)發(fā),而且可以提升路由可達(dá)性,進(jìn)一步提升路由聚合程度,減少路由條目數(shù)量.為此,在下一步的研究工作中,應(yīng)該將綜合分析現(xiàn)有計(jì)數(shù)布隆過濾器的優(yōu)化思路,降低堆疊計(jì)數(shù)布隆過濾器的查詢假陽性,進(jìn)一步改進(jìn)路由后綴壓縮表示機(jī)制及相應(yīng)的路由聚合過程.