IP網(wǎng)分級(jí)尋址的研究.pdf

1、Internet己走過(guò)了三十余年的歷史，隨著Internet越來(lái)越廣泛的應(yīng)用，作為Internet基礎(chǔ)的TCP/IP協(xié)議族，也面臨著各種各樣的問(wèn)題。其中一個(gè)突出問(wèn)題是IPv4地址空間耗盡問(wèn)題。解決IPv4地址空間耗盡問(wèn)題的方法主要有兩種：設(shè)計(jì)全新的IP協(xié)議，在IPv4的基礎(chǔ)上打補(bǔ)丁。 為解決IPv4地址空間耗盡，路由表爆炸，網(wǎng)絡(luò)管理，新的應(yīng)用對(duì)IP網(wǎng)提出新的服務(wù)要求等問(wèn)題，1995年IETF發(fā)布了下一代IP協(xié)議規(guī)范——IPv6，

2、屬于第一類方法。為同樣目的，1996年發(fā)布的私有IP地址，1993年發(fā)布的臨時(shí)分配IP地址的DHCP，1993年發(fā)布的更有效率地使用IP地址的CIDR規(guī)范，1994年發(fā)布的復(fù)用IP地址的網(wǎng)絡(luò)地址轉(zhuǎn)換(NAT)等新的IP地址使用方式屬于第二類方法。 由于與IPv4的互操作性，IPv6還沒(méi)有像過(guò)去預(yù)期的那樣得到普遍使用，而前面提到的基于IPv4打補(bǔ)丁的方法也難以徹底解決問(wèn)題，并且NAT給某些端到端的應(yīng)用造成困難。 首先，針對(duì)

3、IPv4地址空間耗盡和路由表爆炸問(wèn)題，本文提出了一種IP網(wǎng)分級(jí)尋址模型。該模型的地址空間可以達(dá)到與IPv6地址空間同樣大。該模型將IP地址空間劃分成樹形結(jié)構(gòu)，不同層的結(jié)點(diǎn)賦予不同類的IP地址。這種層次的區(qū)分，使數(shù)據(jù)包的轉(zhuǎn)發(fā)過(guò)程不必修改包頭的地址信息。結(jié)點(diǎn)只需維護(hù)本簇內(nèi)結(jié)點(diǎn)的路由信息，這使路由表的長(zhǎng)度大大縮短，有利于解決路由表爆炸問(wèn)題。這種尋址方式基本上解決了IPv4地址空間耗盡和路由表爆炸兩個(gè)問(wèn)題。本文證明了分級(jí)尋址模型的層次路由協(xié)議的

4、正確性，分析了其復(fù)雜性，說(shuō)明了分級(jí)尋址模型與IPv4的互操作性，用仿真實(shí)驗(yàn)評(píng)價(jià)了分級(jí)尋址模型的性能。在文獻(xiàn)中，這是IP地址擴(kuò)展模型第一次與層次路由方法相結(jié)合。 其次，本文分析了分級(jí)尋址性能與分級(jí)尋址模型中分簇結(jié)構(gòu)之間的關(guān)系，證明最優(yōu)分簇結(jié)構(gòu)中，各簇大小相等，IPEA的路由表長(zhǎng)度等于本地簇的大小，與分簇結(jié)構(gòu)無(wú)關(guān)。按照各簇間負(fù)載平衡的標(biāo)準(zhǔn)，確定了最優(yōu)分簇結(jié)構(gòu)，和相應(yīng)的最優(yōu)分簇結(jié)構(gòu)高度，證明了最優(yōu)分簇結(jié)構(gòu)是平衡樹。同層簇的流量密度相等

5、。最后給出一個(gè)路由表長(zhǎng)度伸展指數(shù)與路由路徑長(zhǎng)度伸展指數(shù)關(guān)系的關(guān)聯(lián)式，很好地解釋了路由表長(zhǎng)度伸展指數(shù)與路由路徑長(zhǎng)度伸展指數(shù)逆相關(guān)的現(xiàn)象。這一現(xiàn)象從1977年Kleinrock等人公開發(fā)表以來(lái)，尚沒(méi)有解析式的解釋。仿真實(shí)驗(yàn)結(jié)果表明計(jì)算值與實(shí)驗(yàn)值擬合很好，證明了本章的分析結(jié)果。 第三，本文證明了分級(jí)尋址模型的最優(yōu)分簇結(jié)構(gòu)的簇大小是該網(wǎng)絡(luò)的基礎(chǔ)圖的團(tuán)數(shù)。將最優(yōu)分簇結(jié)構(gòu)的簇大小與圖論中的treedecomposition理論相關(guān)聯(lián)，應(yīng)用t

6、ree-width近似算法確定輸入圖的tree-width下界，并以之作為最優(yōu)分簇結(jié)構(gòu)的簇大小。提出了一個(gè)樹分割的初始分割生成算法。實(shí)驗(yàn)證明本文提出的算法性能優(yōu)于基于順序和隨機(jī)初始分割的Kernighan-Lin算法，與多層Kernighan-Lin算法性能相當(dāng)，但分割結(jié)果更符合樹形結(jié)構(gòu)。 最后，本文利用Petrinets理論對(duì)分級(jí)尋址模型中的路由算法加以分析。建立了分級(jí)轉(zhuǎn)發(fā)算法的有色Petrinet模型，證明了分級(jí)轉(zhuǎn)發(fā)算法的有