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

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

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

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

4、正確性，分析了其復雜性，說明了分級尋址模型與IPv4的互操作性，用仿真實驗評價了分級尋址模型的性能。在文獻中，這是IP地址擴展模型第一次與層次路由方法相結合。 其次，本文分析了分級尋址性能與分級尋址模型中分簇結構之間的關系，證明最優(yōu)分簇結構中，各簇大小相等，IPEA的路由表長度等于本地簇的大小，與分簇結構無關。按照各簇間負載平衡的標準，確定了最優(yōu)分簇結構，和相應的最優(yōu)分簇結構高度，證明了最優(yōu)分簇結構是平衡樹。同層簇的流量密度相等

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

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