下一代互聯(lián)網(wǎng)的報(bào)文標(biāo)識(shí)與查找技術(shù)的研究.pdf

1、隨著互聯(lián)網(wǎng)的不斷發(fā)展，下一代互聯(lián)網(wǎng)NGI（Next Generation Internet）的研究已受到了廣泛的關(guān)注，為實(shí)現(xiàn)對(duì)更廣泛接入終端、異構(gòu)傳輸網(wǎng)絡(luò)的統(tǒng)一高效處理，可將數(shù)據(jù)的標(biāo)識(shí)和查找的過(guò)程抽象為四個(gè)層面：連接層面、流層面、承載層面和應(yīng)用層面。本文重點(diǎn)研究基于連接層面和流層面的報(bào)文標(biāo)識(shí)和查找技術(shù)。對(duì)于連接層面而言，報(bào)文標(biāo)識(shí)與查找的過(guò)程主要是用于確立報(bào)文傳輸路徑、實(shí)現(xiàn)報(bào)文快速轉(zhuǎn)發(fā)，通常稱之為路由查找；而對(duì)于流層面而言，報(bào)文標(biāo)識(shí)與查找

2、的過(guò)程則主要是用于實(shí)現(xiàn)對(duì)不同數(shù)據(jù)流的差異化控制，可在多種應(yīng)用場(chǎng)景中實(shí)現(xiàn)數(shù)據(jù)流的不同處理，通常也將該過(guò)程稱之為包分類。
　　 隨著IPv4地址的日益緊缺，引入下一代互聯(lián)網(wǎng)NGI的核心協(xié)議--IPv6已成為業(yè)界的共識(shí)，引起了產(chǎn)業(yè)界的廣泛關(guān)注和認(rèn)可。與IPv4相比，IPv6具有很多優(yōu)點(diǎn)，但是，IPv6并沒(méi)有改變網(wǎng)絡(luò)設(shè)備（如路由器）在數(shù)據(jù)平面的功能。事實(shí)上，128位的IPv6地址給路由器的設(shè)計(jì)和制造提出了更大挑戰(zhàn)，特別是對(duì)路由器的核心報(bào)

3、文查找技術(shù)--路由查找和包分類算法提出了更高的要求。因此，研究能夠適用于IPv6的報(bào)文查找算法是非常關(guān)鍵的，它是實(shí)現(xiàn)下一代互聯(lián)網(wǎng)高效數(shù)據(jù)傳輸?shù)囊豁?xiàng)基礎(chǔ)技術(shù)。與此同時(shí)，IPv6報(bào)頭中新增的流標(biāo)簽字段也為下一代互聯(lián)網(wǎng)數(shù)據(jù)流的標(biāo)識(shí)與查找?guī)?lái)了新的契機(jī)。區(qū)別與傳統(tǒng)數(shù)據(jù)流的標(biāo)識(shí)方法，基于流標(biāo)簽的數(shù)據(jù)流標(biāo)識(shí)可以有效地降低報(bào)文中某些字段（如端口、協(xié)議等）查找的難度，擺脫數(shù)據(jù)加密對(duì)數(shù)據(jù)流識(shí)別帶來(lái)的影響。因此，研究基于流標(biāo)簽的數(shù)據(jù)流標(biāo)識(shí)技術(shù)也是非常有意義

4、的。
　　 本文一方面深入研究基于通用標(biāo)識(shí)的報(bào)文查找技術(shù)（包括連接層面的路由查找技術(shù)和流層面的包分類技術(shù)），提出適合IPv6的報(bào)文查找新算法；另一方面研究基于流標(biāo)簽的數(shù)據(jù)流標(biāo)識(shí)技術(shù)，提出面向異構(gòu)網(wǎng)絡(luò)的數(shù)據(jù)流標(biāo)識(shí)方法；最后，本文提出了下一代互聯(lián)網(wǎng)中面向數(shù)據(jù)流的體系結(jié)構(gòu)。本文主要貢獻(xiàn)和創(chuàng)新點(diǎn)包括如下幾個(gè)方面：
　　 （1）本文研究了用于報(bào)文標(biāo)識(shí)和查找的數(shù)據(jù)查找模型，挖掘IPv6尋址結(jié)構(gòu)的特點(diǎn)、IPv6地址分配的特點(diǎn)，并對(duì)規(guī)則

5、集的特征進(jìn)行了深入的研究，在此基礎(chǔ)上提出并實(shí)現(xiàn)了業(yè)界首個(gè)應(yīng)用于IPv6包分類的規(guī)則生成器ClassBenchv6，為IPv6包分類算法的設(shè)計(jì)與評(píng)估奠定了基礎(chǔ)，并得到了業(yè)界的認(rèn)可。
　　 （2）本文研究了連接層面的報(bào)文標(biāo)識(shí)和查找技術(shù)，提出了三個(gè)高效的IPv6路由查找算法：LPFS-OHT、BTLPT和DBH算法。
　　 LPFS-OHT算法采用最長(zhǎng)前綴優(yōu)先匹配的思想，將較長(zhǎng)前綴所對(duì)應(yīng)的Hash表折疊在較短前綴比特樹(shù)上，從而

6、實(shí)現(xiàn)較長(zhǎng)前綴的快速定位，并實(shí)現(xiàn)“一次匹配即可停止”，算法相比現(xiàn)有最長(zhǎng)前綴優(yōu)先查找樹(shù)性能提升了40％。
　　 BTLPT算法和DBH算法是基于葉子節(jié)點(diǎn)集劃分框架的算法。本文首次提出了葉子節(jié)點(diǎn)集劃分框架，將最長(zhǎng)前綴匹配問(wèn)題轉(zhuǎn)換為精確匹配問(wèn)題，并具有劃分集數(shù)量最小化、適合動(dòng)態(tài)更新等優(yōu)點(diǎn)?；谠撊~子節(jié)點(diǎn)集劃分框架，本文提出了BTLPT路由查找算法。該算法的查找訪存次數(shù)僅為目前路徑壓縮前綴樹(shù)和基于前綴范圍算法的50％以內(nèi)，并且占用很少的內(nèi)

7、存，該算法的性能與地址長(zhǎng)度無(wú)關(guān)，適合在IPv6中使用。此外，DBH路由查找算法突破了基于長(zhǎng)度二分查找算法無(wú)法實(shí)現(xiàn)動(dòng)態(tài)更新的局限，是迄今為止首個(gè)能夠?qū)崿F(xiàn)O（logW）的查找性能的動(dòng)態(tài)算法，在IPv6中可實(shí)現(xiàn)最壞情況下僅為7次哈希訪存。
　　 （3）本文研究了流層面的報(bào)文標(biāo)識(shí)和查找技術(shù)，提出了兩個(gè)面向IPv6的包分類算法：ODS-BT和H-LCFST。此外，還提出了基于流標(biāo)簽的報(bào)文標(biāo)識(shí)技術(shù)。
　　 ODS-BT算法采用了新穎

8、的規(guī)則集空間劃分方法，從而實(shí)現(xiàn)了高效查找、內(nèi)存占用少和適合更新的目標(biāo)，該算法的查找性能與地址長(zhǎng)度無(wú)關(guān)，在IPv6中具有很好的可擴(kuò)展性。H-L，CFST算法通過(guò)對(duì)規(guī)則集特征進(jìn)行深入分析，充分利用IPv6規(guī)則集的特征來(lái)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，并提出了多個(gè)啟發(fā)式規(guī)則可針對(duì)不同的規(guī)則集特征構(gòu)建最優(yōu)的數(shù)據(jù)結(jié)構(gòu)，實(shí)驗(yàn)結(jié)果表明該算法能夠廣泛適應(yīng)于不同類型的IPv6規(guī)則集。
　　 此外，為了進(jìn)一步利用IPv6流標(biāo)簽在標(biāo)識(shí)數(shù)據(jù)流方面的優(yōu)勢(shì)，本文提出了面向異

9、構(gòu)網(wǎng)絡(luò)的流標(biāo)簽數(shù)據(jù)流標(biāo)識(shí)方法，對(duì)流標(biāo)簽做了詳細(xì)的定義，提供靈活的單流、聚合流的識(shí)別能力，并將其應(yīng)用于端對(duì)端QoS等級(jí)映射領(lǐng)域，為異構(gòu)網(wǎng)絡(luò)提供統(tǒng)一的QoS標(biāo)識(shí)平面。本文對(duì)流標(biāo)簽做了系統(tǒng)實(shí)現(xiàn)及仿真驗(yàn)證，為流標(biāo)簽的進(jìn)一步應(yīng)用打下較好的基礎(chǔ)。
　　 （4）基于上述報(bào)文標(biāo)識(shí)與查找技術(shù)的研究基礎(chǔ)，本文在最后提出了下一代互聯(lián)網(wǎng)中面向數(shù)據(jù)流的體系結(jié)構(gòu)FIA，定義了一個(gè)新的商業(yè)模型，在可信任可運(yùn)營(yíng)網(wǎng)絡(luò)聯(lián)盟的框架下，提出了基于數(shù)據(jù)流的控制平面和數(shù)據(jù)