產生大容量ＩＰｖ６轉發表的定位隨機預測方法

摘 要:受當前IPv6部署規模的限制，目前還不存在真實的大容量IPv6轉發表，因此對各種相關算法的性能分析必須采用預測產生的轉發表。通過對IPv6地址分配策略進行分析，提出了一種采用定點隨機估計的方法來預測生成大容量路由表的方法。該方法具有簡單、易捕獲、易實現等優點，已經在相關研究中得到應用。

關鍵詞:IPv6; 前綴分布; 定點隨機; 體系結構

中圖分類號:TP393.05文獻標志碼:A

文章編號:1001-3695(2009)09-3458-03

doi:10.3969/j.issn.1001-3695.2009.09.072

Kind of fixed-point random forecasting method generating highvolume forwarding information base of IPv6

YUAN Zong-yi， SUN Zhi-gang

(Computer School， National University of Defense Technology， Changsha 410073， China)

Abstract:In restraint with the scale of IPv6 deployment， there is not existing real and high volume IPv6 forwarding information base， which makes that analysis of relative algorithm must be based on the forcasting which can generate forwarding information base. This paper proposed a kind of fixed-point random forecasting method generating high volume forwarding information base of IPv6，which had simplicity，easy-capturement and easy-implementation， and this method had been applied to relative research work.

Key words:IPv6; prefix distribution; fixed-point random; architecture

IPv4地址的短缺，導致網絡發展的瓶頸。隨著下一代互聯網的快速發展，IPv6協議也越來越多地得到了廣泛的關注。未來IPv6路由表在路由器體系結構和網絡設計中起著舉足輕重的作用。IPv6的發展需要FIB(forwarding information base)表。許多的IP地址查找算法也都是基于對FIB表的準確預測。但由于目前IPv6網絡真實FIB表項數目較少，規模在1 000左右，真實FIB表數據不足以評估IPv6 FIB查找算法的性能，性能評估必須采用模擬生成的大容量FIB表。如果通過簡單的隨機輸入產生的FIB表，不但不具備代表性，而且與真實的表項相距甚遠。這些都是可以在IPv4的基礎上加以驗證的。因此很難準確地去預測未來IPv6 FIB表的結構。但是能夠生成具有與真實路由相吻合的FIB表，對于基于IPv6路由查找算法的IPv6路由器的發展及研究是十分必要的。因此非常需要一種結構模型對現在及未來的IPv6 FIB表進行準確模擬。

1 研究背景

IP地址作為互聯網中最基礎的地址資源，是互聯網發展的基石。由于網絡的高速發展，IP地址的緊缺問題日趨嚴峻。特別是由于各種歷史原因，IPv4有許多地址空間的使用是沒有效率的。這些部分地反映了地址樹的不平衡。但是可以在對于IPv6新的分配方案和地址管理策略中加以改進，使得能夠更加有效地利用地址空間。眾所周知，IPv6[1]是128 bit的，擁有3.4×1038個地址空間，它已經被廣泛地接受替代先前的IPv4地址。IPv6 地址的分類及基本結構IPv6 地址分為單播地址(unicast address)、組播地址(multicast address)和任播地址(anycast address)三大地址類型。但是，由于IPv6單播地址的分配管理占據了當前的大部分地址空間，如圖1所示， 是在RFC4291中規范的全局單播地址結構。其分配管理方法應是筆者重點關注的。

互聯網的IP 地址和AS 號碼分配是分級進行的。這種等級結構在全球范圍內進行分配方法分為兩種:一種是上層注冊機構IPv6的地址空間將地址劃分給下層注冊機構進行管理，稱為分配;另一種是注冊機構將地址劃分給用戶使用，稱為指派。總的來說，地址分配可以依據某種特定的邏輯來分割已經從RIR獲得的地址前綴。這些設計邏輯可以包含對以下因素的考察:地理邊界、組織機構邊界、業務類別等。這些方面與IPv4的地址規劃類似。然而也要務必同時考慮到以下IPv6特定的問題:前綴聚類、網絡的增長，特別是增長過程中是否還能保持聚類。一般情況下，在IPv6地址分配策略中，聚合的目標被認為是最重要的。

如圖2所示，每個組織由其上一級分配一個前綴，然后順次將前綴分配給其下一級。因此，每個組織(IANA、RIR、NIR、LIR和ISP)代表了一個匯聚邊界。

伴隨著IPv6協議的發展，未來IPv6路由表在路由器體系結構和網絡設計中扮演著重要的角色!IPv6產品在發展初期，除了Hitachi、NEC、富士通等日本廠商外，其他產品對IPv6的支持都是通過軟件實現的。但隨著IPv6產業化趨勢漸趨明朗，加之硬件支持可以提高對IPv6分組的處理能力，越來越多的廠商開始提供支持IPv6的產品。總之，對IPv6的硬件支持是必然的趨勢。這就勢必需要對未來IPv6路由表的結構與分布進行準確的預測，以此來開發設計適應未來網絡發展需求的IP地址查找算法，并進一步解決多宿主、負載均衡、路由表項過大等原因對路由器及其查找算法的影響。

由于目前現存的IPv6路由器上的路由表很小又很不全面[2]，IPv6路由表無論是從大小和結構上來說都不能反映對未來IPv6網絡發展的預測。對于IPv6的路由表分析大多都是用隨機的形式產生的路由表，但通過筆者對現存的IPv4路由表分析來看，隨機產生的路由表與真實表的情況相差甚遠，由此產生的分析數據對于針對IPv6而開發的網絡硬件的生產廠商就不能提供有效的參考，這將會制約網絡的發展。

2 相關研究

2.1 Cisco預測方法[3]

由于事物發展的連續性，IPv6與IPv4有著許多相似的特征，理解分析這些有助于指導地址分配策略，能夠更好地利用地址空間，同時更好地查找算法也會從這些相應的特征中產生。Cisco考慮到這些相似性，使得IPv6表產生策略是繼承當前IPv4表的適當特征并依附IPv6的分配策略來綜合產生IPv6表。

一種方案是將bit值插入到IPv4地址前綴。如圖3所示，在這種方案中，Cisco采用了各種不同的方法去擴展IPv4前綴來作實驗，同時保持從現存的表中觀察內在的幾個本質特征。在插入的方法中有在IPv4的前綴之中插入額外的隨機字節;有在每個IPv4bit后插入0和1，也有在字節與字節或是bit與bit間重復著IPv4前綴的，還有在每個IPv4bit前添加0或1。在這些插入方法中最具有高預測模型的應該為后兩種方法，因為這樣的性能和開銷最接近IPv4。依托這種前綴的位置和bit是如何插入的，以此來獲得不同的層級。可是遺憾的是，新產生的表與原始的IPv4表還是有不少的差異，產生結果也許并不是未來IPv6路由表最真實的表述。

另一種方案就是將IPv4前綴結合全球惟一的AS號(即自治系統號碼)來產生IPv6路由表。Cisco通過這種方案產生的路由表的組成是由幾個從IPv4中觀察到的關鍵特征來反映到IPv6的分配方案上。由于AS號是AS(IP網絡組)的惟一標志符，它們體現出了一個好的IP前綴的聚合，如圖4所示，AS號有16 bit的長度，加載32 bit的IP地址前面。然后，用隨機數去填充剩余的bit組成64 bit的IPv6地址。因此，一個合成的IPv6前綴是由AS號+IPv4前綴+隨機數(如果前綴長度超過48)。

通過這種插入AS號的方案產生的路由表，由于在路由表中保留父子關系，從分析模擬的數據來看，產生的路由表保留著IPv4非隨機的屬性，能在一定程度上模擬未來的IPv6路由表。

2.2 ARAM模型對未來IPv6路由表的結構進行了預測和推理

ARAM是一種通過模擬形成路由表的因素、前綴間的關系來生成路由表的模型。這個模型定義了各種給定大小的路由表的結構。ARAM近似模擬路由表增長的原因(分配注冊、ISP的指派、多宿主和負載均衡)。ARAM內部結構的輸入和輸出是很特別的[4]。ARAM的輸出是一個渴望得到大小的路由表。更精確地說，輸出是可能顯現在路由表中地址前綴的聚合，并且不包括其他可能聯系到這些前綴的路由屬性，如AS路徑、下一跳或BGP組。所需路由表大小對ARAM來說不是一個很明確的輸入。在一定程度上，通過五個參數來定義:RIRs分配allocation給LIRs的數量N、對分配allocation進行分割的概率Fsplit、分割出的地址所占地址空間的百分比Csplit、一個已分割的或完整的前綴進行再分割的概率Fspawn、再分割生成的前綴占被分割的或完整的前綴地址空間的百分比Cspawn。通過以上五個參數，再結合注冊機構對ISP進行前綴的分配(allocation practice)，ISP和它們的客戶對BGP表中這些前綴的再分配 (routing practice)就能近似地模擬出較大數量的路由表。

3 定點隨機預測算法及應用

定點隨機預測算法的基本思想是對現有IPv6的前綴分布及分配策略進行細致分析，并根據目前骨干路由器中真實存在的IPv6前綴情況，確定現存的關鍵前綴點并估算其相關比例，同時圍繞這些關鍵點依照其預測比例進行大規模無重復隨機擴展，這樣就能夠得到一張相對近似的擁有較大表項數據的IPv6路由表。伴隨著IPv6的不斷推廣和完善，定點隨機估算方法也在不斷完善關鍵點的比例分配，這必將能為網絡硬件廠商提供更加貼近真實情況的路由表數據。定點隨機算法的局部描述如下:

/*回調函數，將節點內的item結構數據輸出到文件，用于創建不重復的隨機數據*/

算法輸入:根據Cernet2真實的比例確定定點分配輸入所需數據量的各定點比例

算法輸出:圍繞定點比例產生相應比例的大規模數據用來生成分層級的地址樹

bool writeNodeData(Node node)

{ //將節點數據追加寫入udata.txt文件，根節點的數據不寫入

if(node->isNull)

return 1;

FILE out = NULL;

if((out = fopen(\"data.txt\"，\"ab\")) == NULL)

{

cout << \"不能打開輸出文件，創建不重復數據文件失敗!\";

exit(1);

}

fwrite((node->data)，sizeof(Item)，1，out);

fclose(out);

FILE rout = NULL;

if((rout = fopen(\"readabledata.txt\"，\"ab\")) == NULL)

{

cout << \"不能打開輸出文件，創建可讀數據文件失敗!\";

exit(1);

}

fprintf(rout，\"%d \"，node->data.length);

for(int i=0;idata.length;i++)

{

if(node->data.prefix.test(i))

fprintf(rout，\"1\");

else

fprintf(rout，\"0\");

}

fprintf(rout，\" %d\\"，node->data.port);

fclose(rout);

return true;

}

同時利用當前Cernet2[5]和Cisco預測的前綴分布進行比較，如圖5所示，對未來IPv6路由表進行預測。

由于樹結構是目前FIB查表采用的主要數據結構，當前主要的FIB查表算法，如Tree Bitmap[6]，每次訪存處理一個查找一個子樹，子樹的個數和分布是影響算法性能的重要因素。于是，考慮基于模擬實驗產生的大量數據，并根據兩種前綴分布生成的各層級(每四位前綴劃分一個層級，64 bit前綴共劃分16個層級)子樹數目生成了如表1所示的子樹統計表，這為下一步網絡硬件的發展提供了很好的參考數據。

表1 模擬100W數據中兩種預測方法產生子樹的統計

層Cisco預測估算定點隨機估算層Cisco預測估算定點隨機估算

122972 71538 840

2323210115 0906 473

351251211114 838217

48 1928 19212580 517286 617

5127 853123 6991315 5261 618

6133 211125 9611425 3880

716 01751 5291520 5000

892 503556 87616054 209

在與其他算法進行比較過程中，定點隨機體現出了較好的優勢。如表2所示，定點隨機估算法簡單實用，并未簡單地停留在理論抽象階段，該算法能夠靈敏地捕獲目前核心路由器上的前綴分布特征及趨勢，并根據這些變化的特征及趨勢不斷改變和完善算法輸入的數據比例，可操作性強。

表2 路由表預測算法的幾種比較

比較項

Cisco

IPv4前綴中插入或重復bitIPv4前綴中插入AS number

ARAM模型定點隨機法

抽象性具體具體抽象具體

簡易性簡便簡便復雜簡便

捕獲性不易捕獲不易捕獲易捕獲易捕獲

遠瞻性不可完善不可完善可完善可完善

實現性易實現易實現復雜易實現

目前，該定點隨機方法已經在高性能路由器研究中得到應用。文獻[7]對存儲和查表開銷進行了評估，取得很好效果，得到研究人員的認可。

4 結束語

由于對于路由器而言，減少路由表的大小是很有意義的，路由器中的各項條目如果很少，意味著路由器保存這些條目對應的路由信息的內存空間可以減少。但由于多宿主(multi-home)的應用對于網絡的地址和路由有著很苛刻的要求，這對有大量地址前綴和嚴格層次化的地址結構的IPv6 來說，意味著極大的挑戰。對于今天的Cernet和Ncernet2而言，部署IPv6的環境已經是典型的多接入(multihoming)的環境，同時還有大量的新技術在研究和開發的過程中，如真實IPv6地址的體系結構、IPv4～IPv6無狀態地址映射技術等，都或多或少涉及到對地址體系結構的調整和變更。從這方面來說，發展這些新技術的同時，設計好多接入環境的地址規劃方案，是一項頗具挑戰性的工作，而目前并沒有一個公認的簡單、有效的辦法來解決這個問題。

雖然Cisco提出的對路由表的模擬和ARAM模型對路由表的模擬從一定程度上規劃了模擬的要素，并期待能夠有預見性地模擬路由表項的增長，但是這些方案措施離簡單、易用、精確、可持續性的標準都還有很大的距離。本文所提出的定點隨機的方案也都還是基于現今及最近一個時期內路由表的實際增長情況的預測，本身也是一個試探性的綜合預測方法，但這為接下來的網絡硬件的發展提供了重要的數據參考，因此不期望這種定點隨機的方法產生大量的IPv6路由表項是最精確最完美最符合未來發展趨勢的方案。隨著IPv6的發展與成熟，更多精確的數據變得可用，勢必能更好地推斷路由實踐并更好地追蹤IPv6分配的發展和路由實踐，以此來設計出比定點隨機更加精準可靠的模擬方法。

參考文獻:

[1]DEERING S， HINDEN R. RFC2460， Internet protocol， version 6 (lPv6) specification [S].

[2]Active IPv6 BGP entries [EB/OL]. http:// bgp.potaroo.net/v6/as1221/index.html.

[3]WANG Mei， DEERING S， HAIN T， et al. Non-random generator for IPv6 tables [C]//Proc of the 12th Annual IEEE Symposium on High Performance Interconnects. 2004: 35-40.

[4]NARAYAN H， GOVINDAN R， VARGHESE G. The impact of address allocation and routing on the structure and implementation of routing tables[C]//Proc of SIGCOMM. 2003.

[5]中國Cernet中心全球IPv6路由表[EB/OL]. (2008-04). http:// bgpview.6test .edu.cn/ datav6/.

[6]EATHERTON W， VARGHESE G， DITTIA Z. Tree bitmap: hardware/software IP lookups with incremental updates[J].ACM SIGCOMM Computer Communications Review， 2004，34(2):97-122.

[7]孫志剛， 戴藝， 龔正虎. 面向下一代互聯網的可擴展路由器體系結構——MPFS [J].中國科學 E輯: 信息科學， 2008， 38(10):1652-1662.