崔宇，張兆心，張宏莉，田志宏

（哈爾濱工業(yè)大學(xué) 計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心，黑龍江 哈爾濱 150001）

1 引言

通過網(wǎng)絡(luò)模擬器對網(wǎng)絡(luò)協(xié)議和網(wǎng)絡(luò)行為進行模擬是目前研究網(wǎng)絡(luò)的重要方法之一。較著名的單機網(wǎng)絡(luò)模擬器有NS-2[1]、OPNET[2]等。受硬件資源的限制，單機模擬器已經(jīng)不能滿足研究者對模擬規(guī)模和模擬性能的要求。因此，并行模擬和流模擬技術(shù)作為解決這一問題的有效途徑被提出并廣泛使用。流模擬技術(shù)如JSim，其通過對鏈路和節(jié)點的抽象來計算網(wǎng)絡(luò)的實時狀態(tài)[3]。該方法具有速度快但對網(wǎng)絡(luò)情況描述粒度較粗的特點，適合對網(wǎng)絡(luò)流量的整體分析。并行模擬技術(shù)如PDNS[4,5]，其采用了數(shù)據(jù)分組級別的模擬，能有效刻畫網(wǎng)絡(luò)中任意時刻節(jié)點和鏈路的情況，可以對網(wǎng)絡(luò)進行細(xì)致的分析。

在并行網(wǎng)絡(luò)模擬中，路由表的存儲與查詢一直是影響模擬速度和規(guī)模的主要因素之一。文獻[6]通過對各階段模擬時間的測量，得出了調(diào)度和路由計算部分占用了整個模擬過程大部分開銷的結(jié)論。文獻[7]指出 PDNS原始的遠(yuǎn)程路由策略在拓?fù)湟?guī)模不大時即占用了很大的內(nèi)存空間，路由查找效率低下。

目前，主要的遠(yuǎn)程路由策略包括：全路徑路由策略、GHOST[8]路由策略、基于邊界路由器的路由策略[7]和層次路由策略[6]。全路徑路由策略是最早使用的遠(yuǎn)程策略，其存儲了本模擬器中每個節(jié)點到整個拓?fù)渲腥抗?jié)點的路由信息。假設(shè)本模擬器中節(jié)點數(shù)為K，整個拓?fù)涔?jié)點數(shù)為N，則對于本模擬器來說其遠(yuǎn)程路由表的記錄數(shù)目為KN。路由查詢時，該方法需遍歷本模擬器內(nèi)的所有記錄，時間復(fù)雜度為O(KN)。為了縮短路由表長度，全路徑路由策略采用了網(wǎng)絡(luò)掩碼的技術(shù)，通過只存儲某一區(qū)域內(nèi) IP地址的相同前綴來減少路由表長度。但該種方法只能處理IP地址比較規(guī)則且可以使用掩碼的情況，對于拓?fù)湫问奖容^復(fù)雜的情況則不適用。GHOST路由策略將整個拓?fù)涞男畔⒋鎯Φ矫恳粋€模擬器中，其中當(dāng)前模擬器包含的拓?fù)鋮^(qū)域以實模式表示，即建立節(jié)點、鏈路、應(yīng)用等，而其他區(qū)域則使用虛模式，即只存儲了節(jié)點與鏈路的鄰接信息。查找時，類似Nix-Vector[9]，使用BFS算法求出源到目的最短路徑P，查找的時間復(fù)雜度為O(N)，N為節(jié)點總數(shù)。P中實模式部分采用Nix-Vector進行路由，當(dāng)數(shù)據(jù)分組到達源節(jié)點所在子網(wǎng)的邊界路由器時，遠(yuǎn)程路由模塊根據(jù)P選擇相應(yīng)的遠(yuǎn)程鏈路轉(zhuǎn)發(fā)數(shù)據(jù)分組，從而完成數(shù)據(jù)分組在本模擬器內(nèi)的路由。在下一個模擬器中，數(shù)據(jù)分組的路由方式有 2種：其一是從前一個模擬器接收最短路徑P的剩余部分進行直接轉(zhuǎn)發(fā)，這種方式的特點是不用再次計算，速度快，但由于進行了路徑P的傳遞，因此會產(chǎn)生額外的同步和通信數(shù)據(jù)，也占用了大量的內(nèi)存；其二是在每個模擬器上重新計算新的路徑Pi，這種方式的特點是減少了內(nèi)存占用量和模擬器之間的通信量，但增加了計算時間，并且，由于GHOST方式需要對每個數(shù)據(jù)分組維護一個源到目的的路徑，因此該方法占用的內(nèi)存隨數(shù)據(jù)分組數(shù)量的增大而增大，不利于大規(guī)模模擬?；谶吔缏酚善鞯倪h(yuǎn)程路由策略在每個模擬器中只存儲了本模擬器內(nèi)的邊界路由器到其他所有節(jié)點的最短距離和下一跳邊界路由器。在計算節(jié)點A到節(jié)點Β的最短距離時，該策略取A到A所在子網(wǎng)某邊界路由器Ei與Ei到Β的距離之和中最短的作為源節(jié)點所在子網(wǎng)的出口邊界路由器，并通過其進行遠(yuǎn)程路由。與全路徑方式相比，該方法有效地降低了內(nèi)存占用量，并減少一定的模擬運行時間，文獻[7]指出其路由表的規(guī)模只為前者的10%，模擬時間節(jié)省25%。層次路由策略可以理解為分層的全拓?fù)銯lat路由策略，其按照每層中節(jié)點的數(shù)目分配編碼。比如核心層有K個節(jié)點，則核心層需要使用編碼地址高作編號。外圍層次的節(jié)點和與其相連的內(nèi)層節(jié)點有共同的前綴編碼，并在其后繼續(xù)編碼。路由時，該方法在每個節(jié)點處只計算前綴是否一致即可，速度最快，每個節(jié)點上查找的時間復(fù)雜度為O(1)。內(nèi)存占用量上，該方法受限于核心層的大小，假設(shè)核心層節(jié)點數(shù)為N，則核心層的空間復(fù)雜度為O(N2)。

上述4種遠(yuǎn)程路由策略中，層次路由策略速度最快但內(nèi)存占用量偏高，GHOST路由策略速度偏慢且內(nèi)存占用量隨數(shù)據(jù)分組量動態(tài)變化，基于邊界路由器的路由策略取中，在內(nèi)存占用和查找速度上取得了一定的平衡。這4種方式均處理不了目的IP地址不存在的情況，其中層次方式可以對編碼地址進行最長前綴匹配，但原始IP仍然無法與編碼IP對應(yīng)。

本文以基于邊界路由器的遠(yuǎn)程路由策略為基礎(chǔ)，提出了基于優(yōu)化邊界的遠(yuǎn)程路由策略，解決了前者出現(xiàn)的無法進行最長前綴路由、冗余查詢等問題，在降低內(nèi)存占用量的同時提高了模擬的運行速度。

2 基于優(yōu)化邊界的遠(yuǎn)程路由策略

并行網(wǎng)絡(luò)模擬需要將整個拓?fù)鋭澐譃槿舾蓚€模擬區(qū)域，部署在不同的模擬器上，通過遠(yuǎn)程鏈路進行連接。每個模擬區(qū)域包含至少一個連通區(qū)域，每個連通區(qū)域稱為一個子網(wǎng)。在數(shù)據(jù)分組的轉(zhuǎn)發(fā)過程中，遠(yuǎn)程路由只關(guān)心源到目的節(jié)點最短路徑上所經(jīng)過的子網(wǎng)以及路徑上重要的節(jié)點如邊界路由器，而不關(guān)心某子網(wǎng)中2個節(jié)點如何進行本地數(shù)據(jù)分組的轉(zhuǎn)發(fā)。因此，遠(yuǎn)程路由只需計算出最短路徑上能正確引導(dǎo)數(shù)據(jù)分組跨越不同子網(wǎng)的重要節(jié)點信息即可。

基于優(yōu)化邊界的遠(yuǎn)程路由策略的核心思想是將以目的 IP地址進行路由計算與轉(zhuǎn)發(fā)的方式轉(zhuǎn)換成以邊界路由器編號進行轉(zhuǎn)發(fā)的方式。以圖1所示拓?fù)錇槔?，實心?jié)點為邊界路由器，空心節(jié)點為終端節(jié)點，R1、R2、R3、R4在L0到L1最短路徑上。當(dāng)子網(wǎng)0中L0節(jié)點向子網(wǎng)2中的L1節(jié)點發(fā)送數(shù)據(jù)分組時，路由模塊將以L1為基礎(chǔ)的路由方式轉(zhuǎn)化為以二元組(R1,R4)為基礎(chǔ)的路由計算方式，并以該二元組為基礎(chǔ)進行中間子網(wǎng)如子網(wǎng)1上的路由轉(zhuǎn)發(fā)。

圖1 拓?fù)渑e例

為了便于描述，首先給出一些定義。

定義1源子網(wǎng)：源節(jié)點所在子網(wǎng)。

定義2目的子網(wǎng)：目的節(jié)點所在子網(wǎng)。

定義 3源子網(wǎng)出口邊界路由器：在源節(jié)點到目的節(jié)點的最短路徑上，第一個連接遠(yuǎn)程鏈路的節(jié)點，如圖1中的R1節(jié)點。

定義 4目的子網(wǎng)入口邊界路由器：在源節(jié)點到目的節(jié)點的最短路徑上，最后一個連接遠(yuǎn)程鏈路的節(jié)點，如圖1中的R4節(jié)點。

定義 5中間子網(wǎng)：指在源節(jié)點到目的節(jié)點的最短路徑上的非源子網(wǎng)和目的子網(wǎng)的子網(wǎng)。

由此，基于優(yōu)化邊界的遠(yuǎn)程路由策略的核心思想可以總結(jié)成：將以目的 IP地址為路由計算和轉(zhuǎn)發(fā)的方式轉(zhuǎn)換為以源子網(wǎng)出口邊界路由器和目的子網(wǎng)入口邊界路由器組成的二元組進行計算和轉(zhuǎn)發(fā)的方式。為了實現(xiàn)這種路由方式，需要完成2個部分的工作：第一是將目的 IP地址轉(zhuǎn)換為二元組的形式；第二是通過該二元組進行路由選擇。

2.1 將目的IP地址轉(zhuǎn)換為二元組

為了將目的IP轉(zhuǎn)換為二元組，本策略為每個子網(wǎng)設(shè)計了一個存儲查詢框架。如圖2所示。

圖2 遠(yuǎn)程路由存儲與查詢的框架

如圖2所示，Level Compression Trie表示一顆層壓縮樹[10]，存儲了拓?fù)渲兴泄?jié)點，可對目的IP進行最長前綴匹配，從而解決不存在節(jié)點無法路由的問題。假設(shè)拓?fù)涔?jié)點總數(shù)為N，則該樹最多包含2N個節(jié)點，最多查找 32次。樹中每個葉子指向Record中的一條記錄，表示該IP可以使用此記錄中提供的路徑到達。Record記錄的格式為“(Sed1.Ded1.Len1); (Sed2.Ded2.Len2); …; (Sedk.Dedk.Lenk);”。其中，“(Sedk.Dedk.Lenk);”稱作一個片段，表示從源子網(wǎng)邊界路由器 Sedk到目的節(jié)點的長度為 Lenk，目的子網(wǎng)入口邊界路由器為 Dedk。每條記錄中片段的個數(shù)與源子網(wǎng)中邊界路由器個數(shù)一致，表示源子網(wǎng)中所有邊界路由器到目的節(jié)點的最短路徑長度和路由方式。

下面以圖3所示拓?fù)錇槔f明Record中存儲的內(nèi)容。圖中所示拓?fù)涔?個子網(wǎng)，子網(wǎng)N2中全部節(jié)點(除邊界路由器)在子網(wǎng)N1中存儲的記錄如表1所示?？梢钥吹?，N1子網(wǎng)包含2個邊界路由器，因此每條記錄均包含2個片段。計算路由時，需要進行比較，選擇距離最短的。假設(shè)A節(jié)點向Β節(jié)點發(fā)數(shù)據(jù)，A節(jié)點通過層壓縮樹查找到Β節(jié)點的Record記錄，其內(nèi)容為“(R11.R12.L1); (R21.R22.L2); …;(Ri1.Ri2.Li);”。此時有多個片段，需比較出A到Β最短路徑經(jīng)過的片段，采用的方法是循環(huán)計算LA,Rk1+Lk的距離之和L(1≤k≤i)，其中，LA,Rk1表示A節(jié)點到Rk1邊界路由器的本地最短距離，取L最短者為A到Β使用的邊界路由器二元組。在處理同一子網(wǎng)內(nèi)2個節(jié)點的通信時，大部分情況下不用通過遠(yuǎn)程鏈路，此時首先計算兩節(jié)點間的本地最短距離，如果存在Record對應(yīng)的記錄則進行比較，選擇距離較小的。

圖3 舉例用拓?fù)?/p>

表1 N1子網(wǎng)中存儲的N2子網(wǎng)Record

2.2 Record的優(yōu)化

每條 Record記錄存儲了源子網(wǎng)中所有邊界路由器到目的節(jié)點的片段，假設(shè)子網(wǎng)S中有1K個邊界路由器，整個拓?fù)?M個節(jié)點，片段長6byte，那么S對應(yīng)的 Record總量為 1K×1M×6byte=6Gbyte，這占用了大量的內(nèi)存空間。因此，需要采用逐個子網(wǎng)計算的方式，每次只計算一對子網(wǎng)的Record，減少內(nèi)存占用量。為此，本文引入了采用基于CQ(calendar queue)[11]方式的BFS算法對每個目的子網(wǎng)進行計算。該算法以距離為縱線，以與源邊界路由器最短距離相同的節(jié)點組成橫線。舉例來說，當(dāng)計算R2對子網(wǎng)N2中所有點的片段時，形成的CQ初始情況如圖4所示。

圖4 R2節(jié)點對N2子網(wǎng)的CQ初始情況

圖中R5與R2最短距離為2，因此插入第二行，前后2個值分別表示當(dāng)前擴展到的節(jié)點和到達本節(jié)點的入口邊界路由器。同理R6插入到第三行。計算時從距離為1開始，逐次取出每行中的節(jié)點，將沒有被插入過的鄰居節(jié)點插入到下一行，表示距離加 1，第二個分量不變。通過從邊界路由器向子網(wǎng)內(nèi)部的擴散，N2子網(wǎng)中所有的點均可計算出對應(yīng)于R2的片段。當(dāng)N1中所有邊界路由器對N2子網(wǎng)均進行一次擴散后，N1即存儲了N2子網(wǎng)中所有節(jié)點的記錄，且每條記錄中片段的數(shù)目與源子網(wǎng)中邊界路由器的數(shù)目一致。

雖然可以通過逐個子網(wǎng)計算的方式來減少計算時內(nèi)存的使用量，但記錄的總量并沒有改變。為此，本文使用了3種方法來縮減Record記錄數(shù)目和每條記錄的片段數(shù)目。

1) 樹區(qū)域收縮(tree contraction)

所謂樹區(qū)域收縮就是將拓?fù)鋱D中樹區(qū)域包含的節(jié)點用根節(jié)點表示，省去非根節(jié)點的記錄，以減少記錄數(shù)目。樹區(qū)域收縮不影響路由選擇結(jié)果，下面給出證明。

結(jié)論經(jīng)樹區(qū)域收縮的路由表在路由選擇上與原始情況一致。

證明假設(shè)Ri、Rj為源子網(wǎng)邊界路由器，Tr為目的子網(wǎng)中一樹根節(jié)點，Ri、Rj與Tr形成的記錄為“(Ri.Rr1.Pr1);(Rj.Rr2.Pr2)”。Tx為樹中任一節(jié)點，Ri、Rj與Tx形成的記錄為“(Ri.Rx1.Px1); (Rj.Rx2.Px2)”。首先，由貪心算法可知，Tr一定在Tx到Ri的最短路徑上，因此2段路徑重合并且由目的子網(wǎng)入口邊界路由器的定義可知，Rr1 =Rx1，同理Rr2 =Rx2?？梢?，樹中節(jié)點與樹根節(jié)點記錄中對應(yīng)片段的邊界路由器一致，只是距離不同。在計算源子網(wǎng)中某一節(jié)點A到Tx的最短路徑時，要比較LA,Ri+Px1和LA,Rj+Px2的大小，兩端同時減掉LTr,Tx的大小，比較結(jié)果不變，形式變?yōu)長A,Ri+Pr1和LA,Rj+Pr2。而這與比較A到Tr的方式一樣，因此樹區(qū)域中的節(jié)點可由樹根節(jié)點代替，收縮后路由情況不變。證畢。

經(jīng)樹區(qū)域收縮后，由于樹區(qū)域中的節(jié)點均被樹根節(jié)點代替，因此Record記錄的條數(shù)得到了減少。對圖3所示拓?fù)涠?，?jīng)樹區(qū)域收縮后，其拓?fù)淙鐖D5所示。

圖5 樹結(jié)構(gòu)收縮后的拓?fù)?/p>

圖5中，網(wǎng)格線標(biāo)識的節(jié)點為樹區(qū)域的根節(jié)點，可以看到，N2包含了2個樹形區(qū)域，共計6個節(jié)點。經(jīng)樹區(qū)域收縮后，對于源子網(wǎng)N1而言，目的子網(wǎng)N2對應(yīng)的Record如表2所示。可以看到，樹區(qū)域中的節(jié)點均指向了樹根的記錄。

表2 樹區(qū)域收縮后N1中存儲的N2 Record

2) 后連節(jié)點去重(assnode reduction)

后連節(jié)點去重是減少 Record記錄數(shù)目的另一種方法，用于樹區(qū)域收縮之后，對收縮后的拓?fù)溥M行進一步處理。下面首先給出后連節(jié)點的定義。

定義 6后連節(jié)點(assnode): 設(shè)某子網(wǎng)S，SET(S)表示S上所有邊界路由器的集合，P、Q為另一個子網(wǎng)中鄰接的2個點。若SET(S)中的邊界路由器到Q點的最短路徑均經(jīng)過P，則稱Q為P的后連節(jié)點，P為Q的前導(dǎo)節(jié)點。

若Q為P的后連節(jié)點，則Q可用P的記錄代替以進一步減少記錄數(shù)目，其證明思想與樹區(qū)域收縮的證明類似。后連節(jié)點去重依然采用源子網(wǎng)S對目的子網(wǎng)D進行BFS擴散。D中每個節(jié)點存儲了其鄰接節(jié)點的鏈表，當(dāng)從S中Ri邊界路由器對D進行擴散時，如果D中的節(jié)點Β是從A節(jié)點擴散到的，則將A的鄰居節(jié)點鏈表中Β對應(yīng)元素的引用計數(shù)加1。若Β節(jié)點對應(yīng)元素的引用計數(shù)和S中邊界路由器個數(shù)相等，則說明Β為A的后連節(jié)點。后連節(jié)點具有遞歸性，如果Β是A的后連節(jié)點，C是Β的后連節(jié)點，則Β、C節(jié)點均可以用A代替。下面給出后連節(jié)點的標(biāo)識算法。

算法1后連節(jié)點標(biāo)識算法

后連節(jié)點去重后，目的子網(wǎng)對應(yīng)的記錄數(shù)目進一步減少。以圖5所示拓?fù)錇槔?jīng)后連節(jié)點去重，N1中Record如表3所示。

表3 后連節(jié)點去重后N1中存儲的N2 Record

3) 邊界路由器去重(edge router reduction)

經(jīng)樹區(qū)域收縮和后連節(jié)點去重后，子網(wǎng)中存儲的 RECORD數(shù)目得以有效的減少，形成了多個節(jié)點對應(yīng)一條記錄的形式。邊界路由器去重對每條記錄進行分析，刪除其中的冗余片段，從而進一步減少內(nèi)存占用。下面給出冗余片段的定義。

定義7冗余片段：設(shè)源子網(wǎng)S1，目的子網(wǎng)S2，Ri、Rj為S1中的2個邊界路由器，P為S2中的一個節(jié)點，P的記錄為“(Ri.Rx.Pi);(Rj.Ry.Pj)”。若Pi+LRi,Rj≤Pj，其中，LRi,Rj表示兩者之間的距離，則稱Rj的片段對于Ri而言是冗余的。

冗余片段是可以去掉的，如圖6所示，假設(shè)A節(jié)點向P節(jié)點發(fā)送數(shù)據(jù)分組，如果存在關(guān)系Pi+LRi,Rj≤Pj，則A一定不會選擇A-Rj-P的路線，因為A-Rj-Ri-P的距離可能更短，所以Rj對應(yīng)片段是冗余的，可以去掉。

圖6 冗余片段示意

經(jīng)過邊界路由器去重，圖 5所示的拓?fù)渲蠳1子網(wǎng)存儲的N2子網(wǎng)的記錄如表4所示。

表4 邊界路由器去重后N1中存儲的N2 Record

樹區(qū)域收縮，后連節(jié)點去重和邊界路由器去重后，Record的條數(shù)和每條記錄的片段數(shù)得以有效的減少，總的內(nèi)存占用量也隨之減少。經(jīng)過遠(yuǎn)程路由的查詢和比較后，源子網(wǎng)出口邊界路由器和目的子網(wǎng)入口邊界路由器組成的二元組得以確定，進而開始數(shù)據(jù)分組的路由。如果源到目的最短路徑本地可達，則不需經(jīng)過邊界路由器。

2.3 邊界路由器二元組的路由

路由轉(zhuǎn)發(fā)時，源節(jié)點通過本地路由將數(shù)據(jù)分組轉(zhuǎn)發(fā)給源子網(wǎng)出口邊界路由器，之后，數(shù)據(jù)分組在中間子網(wǎng)的轉(zhuǎn)發(fā)由邊界路由器完成，到達目的子網(wǎng)后，目的子網(wǎng)的入口邊界路由器通過本地路由將數(shù)據(jù)分組送達目的節(jié)點。

為了對邊界路由器二元組進行路由，首先將拓?fù)渲兴械倪吔缏酚善骶幪?，同一個子網(wǎng)中的編號連續(xù)。如圖5中，R1編號為1，R2編號為2，以此類推。其次，每個邊界路由器保存了2個結(jié)構(gòu)：NHP、RLP，其中NHP稱為下一跳存儲表，采用數(shù)組存儲了本邊界路由器到所有邊界路由器的下一跳序列，存儲空間復(fù)雜度為O(N)，N為整個拓?fù)溥吔缏酚善骺倲?shù)，查找的時間復(fù)雜度為O(1)。RLP稱為遠(yuǎn)程鏈路存儲表，存儲了與該邊界路由器連接的所有遠(yuǎn)程鏈路和另一端的邊界路由器編號，空間復(fù)雜度為O(k)，查找的時間復(fù)雜度為O(k)，k為連接的遠(yuǎn)程鏈路個數(shù)。圖7顯示了R1節(jié)點上存儲的NHP和RLP的內(nèi)容。

圖7 R1節(jié)點上的NHP與RLP

圖7中，R1邊界路由器中保存的NHP序列為：0.0.2.2.5.5。第一個0表示到編號1即自身的下一跳；第二個0表示到編號2邊界路由器的下一跳，由于不用跨子網(wǎng)，因此也為 0。R3時，需經(jīng)過R2，因此記錄為2。

邊界路由器可以從2種鏈路接收數(shù)據(jù)分組：本地鏈路、遠(yuǎn)程鏈路。從本地鏈路接收到數(shù)據(jù)分組時，如果該數(shù)據(jù)分組目的地址不是自身，則該數(shù)據(jù)分組一定要通過該邊界路由器出本子網(wǎng)。因為當(dāng)該邊界路由器作為本地路徑中的一個普通節(jié)點時，數(shù)據(jù)分組并不會進入邊界路由器的遠(yuǎn)程計算模塊，而是通過節(jié)點的本地路由模塊轉(zhuǎn)發(fā)了。所以，這種情況下只需通過數(shù)據(jù)分組中目的子網(wǎng)入口邊界路由器編號在 NHP中查找下一跳的邊界路由器編號，然后進入RLP查找對應(yīng)的遠(yuǎn)程鏈路進行轉(zhuǎn)發(fā)，此時RLP中一定存在相應(yīng)記錄。

當(dāng)邊界路由器從遠(yuǎn)程鏈路接收到數(shù)據(jù)分組時，除目的為自身外有3種情況：第一，目的節(jié)點為本子網(wǎng)中的某個節(jié)點，此時直接調(diào)用本地路由發(fā)送到目的節(jié)點即可；第二，數(shù)據(jù)分組從本子網(wǎng)的另一個邊界路由器出本子網(wǎng)，此時需要將數(shù)據(jù)分組通過本地路由轉(zhuǎn)發(fā)到該邊界路由器；第三，通過本邊界路由器的其他遠(yuǎn)程鏈路發(fā)送出去。下面給出查詢算法。

算法2遠(yuǎn)程鏈路接收處理算法

3 實驗結(jié)果與分析

本節(jié)對基于優(yōu)化邊界遠(yuǎn)程路由策略的性能進行了測試，主要指標(biāo)是內(nèi)存占用量和模擬時間開銷。實驗從啟明星辰提供的全國拓?fù)鋽?shù)據(jù)庫中選取了 8個拓?fù)?，每個被劃分為4個區(qū)域，每個區(qū)域用一臺服務(wù)器進行模擬（3.0GHz的CPU、4GB內(nèi)存）。表5顯示了測試拓?fù)涞脑敿?xì)信息。其中，Router為路由器總數(shù)，TR為節(jié)點度為 1的路由器數(shù)目，Ave_De表示路由器的平均節(jié)點度，Node表示每個TR上綁定10個主機后拓?fù)涔?jié)點總數(shù)，ED表示每個劃分區(qū)域的邊界路由器個數(shù)，Sub表示每個劃分區(qū)域的子網(wǎng)數(shù)。

表5 測試用拓?fù)洵h(huán)境

基于優(yōu)化邊界的路由策略主要有 3個存儲結(jié)構(gòu)：層壓縮樹（CT）、RECORD（RE）和邊界路由器信息（ED）。實驗首先測試了2.2節(jié)中3種優(yōu)化方法在降低RE數(shù)量上的性能，之后得出了優(yōu)化后RE片段總量縮減的比例，然后給出了 CT、RE、ED各自使用的內(nèi)存量，最后通過與基于邊界路由器的遠(yuǎn)程路由策略進行內(nèi)存總量對比得出內(nèi)存優(yōu)化的整體性能。

優(yōu)化前，RE部分占用的內(nèi)存最大。因此，實驗使用了樹區(qū)域收縮(TC)、后連節(jié)點去重(AS)和邊界路由器去重(EC)3種方法對 RE進行了優(yōu)化，各方法的優(yōu)化結(jié)果如圖8所示。

圖8 各方法縮減比例

圖8中，樹區(qū)域收縮對減少RE條數(shù)的貢獻度最大，縮減了90%左右的記錄條數(shù)。這與每個度為1的路由器上綁定10個主機相關(guān)，可以預(yù)計，隨著主機數(shù)目的增加，樹區(qū)域收縮貢獻度也會越大。后連節(jié)點去重總體上徘徊在50%左右，性能次于樹區(qū)域收縮。其在第5個用例時出現(xiàn)了嚴(yán)重的波動，是受到了拓?fù)湫问阶兓挠绊?，存在一定的不穩(wěn)定性。邊界路由器去重的效用較低，在20%左右，也隨著拓?fù)涞淖兓霈F(xiàn)了一定的波動。經(jīng)過優(yōu)化，RE片段的總數(shù)目得到了有效縮減，縮減比例如圖9所示，其中，MAX、AVE和MIN分別表示4個區(qū)域中比例最高、平均和最低的值。從中可以看出，經(jīng)過簡化，各模擬器在不同拓?fù)錀l件下的Record片段數(shù)目有了很大減少，平均減少97%，最少減少94%。

圖9 各模擬器RECORD縮減前后比例

優(yōu)化后，CT、RE、ED各自內(nèi)存的占用量如圖10所示?？梢钥吹?，RE部分占用的內(nèi)存量得以有效減少，最大值不超過1Mbyte。ED占用內(nèi)存極少，基本可以忽略不計。CT占用量最大，主要有2個原因。其一是CT的個數(shù)與一個劃分區(qū)域內(nèi)的子網(wǎng)個數(shù)一致，如CT曲線的最高點和次高點，雖然次高點的拓?fù)湟?guī)模較大，但由于最高點子網(wǎng)數(shù)為3而次高點為 2，因此導(dǎo)致了拓?fù)漭^大但不是最高點的情況，可見本策略受劃分區(qū)域子網(wǎng)個數(shù)影響較大。其二是每棵CT中，樹節(jié)點數(shù)目最大為拓?fù)涔?jié)點總數(shù)2倍，因此隨著拓?fù)湟?guī)模的增大，該結(jié)構(gòu)占用的內(nèi)存量將會線性增長。

圖10 實驗中各部分內(nèi)存占用量

圖 11則顯示了每個實例中，內(nèi)存占用量最大的區(qū)域上，2種策略占用的內(nèi)存總量。

圖11 2種路由策略的內(nèi)存占用

可以看出，基于優(yōu)化邊界的遠(yuǎn)程路由策略內(nèi)存占用量最大不過10Mbyte，而基于邊界路由器的遠(yuǎn)程路由策略最大超過60Mbyte。兩者相比，前者占用內(nèi)存量最大為后者的45%，平均為14%?？梢娗罢咂骄鶞p少了超過85%的內(nèi)存占用量，因此在內(nèi)存使用上優(yōu)于后者。值得注意的是，后者的結(jié)果曲線在圖11中橫坐標(biāo)為6時出現(xiàn)了較大波動，這主要是受邊界路由器個數(shù)的影響，圖 11中橫坐標(biāo)為 4時邊界路由器為124，而圖11中橫坐標(biāo)為6時數(shù)目僅為17，可見基于邊界路由器的路由策略受邊界路由器數(shù)目影響較大。

遠(yuǎn)程路由的計算量主要體現(xiàn)在以下 2種節(jié)點上。其一是源節(jié)點，源節(jié)點向外發(fā)送的每個數(shù)據(jù)分組均需進行遠(yuǎn)程查詢以確定數(shù)據(jù)分組發(fā)送的方向：直接通過本地路由發(fā)往目的節(jié)點、或者發(fā)到邊界路由器上出本子網(wǎng)。其二是邊界路由器，當(dāng)需要往外子網(wǎng)發(fā)送的數(shù)據(jù)分組到達邊界路由器，或者從外子網(wǎng)到本子網(wǎng)時，均會在此進行遠(yuǎn)程路由查找。為了平衡2種節(jié)點處的計算量，本實驗設(shè)計了一個應(yīng)用程序并將其綁定在100個分散的主機上，該應(yīng)用循環(huán)對拓?fù)渲兴兄鳈CIP發(fā)送數(shù)據(jù)分組，發(fā)分組間隔0.001s，每秒數(shù)據(jù)分組總量為100k，模擬過程中數(shù)據(jù)分組總量為100n，n為葉子節(jié)點總數(shù)。這樣做的目的是，盡可能地讓數(shù)據(jù)分組通過拓?fù)渲兴械穆窂?，避免出現(xiàn)數(shù)據(jù)分組過度集中在某幾條鏈路上和過多或過少經(jīng)過邊界路由器的情況，從而更好地體現(xiàn)遠(yuǎn)程路由策略的整體性能。

圖 12顯示了基于優(yōu)化邊界和基于邊界路由器的遠(yuǎn)程路由策略在實驗中的運行時間?？梢钥闯觯罢呦牡哪M時間明顯短于后者，時間比平均在25%以下。同時隨著拓?fù)涞脑龃?，前者的增長速度也慢于后者，基本以線性的速度增長。

圖12 2種模擬策略的模擬時間

圖13所示為模擬中使用2種遠(yuǎn)程路由策略時模擬器平均每分鐘處理新生數(shù)據(jù)分組的能力?？梢钥闯?，基于優(yōu)化邊界的遠(yuǎn)程路由策略每分鐘可處理10 000以上的新生數(shù)據(jù)分組，而后者處理能力最高不到5 000，可見前者對模擬的整體性能提高很大。

圖13 2種策略下模擬器的處理能力

綜上實驗表明：在內(nèi)存占用上，樹區(qū)域收縮、后連節(jié)點去重和邊界路由器去重共減少了 95%左右的路由表，有效地解決了拓?fù)湟?guī)模較大時路由表過長的問題。相對于基于邊界路由器的遠(yuǎn)程路由策略，該方法降低了85%的整體內(nèi)存使用量，達到了良好的效果。在模擬速度上，圖12和圖13說明該策略有效地提高了模擬的性能，減少了75%以上的整體模擬時間。實驗也表明，該策略的內(nèi)存占用量與整個拓?fù)涞淖泳W(wǎng)數(shù)目關(guān)系很大。當(dāng)子網(wǎng)數(shù)目增加時，層壓縮樹數(shù)目也會增加，從而增加內(nèi)存的占用量。另外，后連節(jié)點和邊界路由器去重算法有一定的局限性和不穩(wěn)定性，對一些特定的拓?fù)湫问綗o法進行去重。

4 結(jié)束語

路由的存儲和查找是影響網(wǎng)絡(luò)模擬性能的重要因素，相關(guān)的研究也提出了諸多降低內(nèi)存和提高模擬速度的解決辦法。本文針對大規(guī)模的網(wǎng)絡(luò)模擬環(huán)境，以降低內(nèi)存占用為主，提出了基于優(yōu)化邊界的遠(yuǎn)程路由策略，使用樹區(qū)域收縮、后連節(jié)點去重和邊界路由器去重3種方法，大幅地降低了內(nèi)存占用量，同時用邊界路由器ID取代目的IP作為路由轉(zhuǎn)發(fā)方式，有效地降低了路由查找時間。實驗中出現(xiàn)的問題，如層壓縮樹與子網(wǎng)個數(shù)相關(guān)和后連節(jié)點、邊界路由器去重不穩(wěn)定等可作為進一步研究的方向。

[1] Network simulator-ns-2[EB/OL].http://www.isi.edu/nsnam/ns, 2004.

[2] DORLEU S, HOLWECK J, REN R.Modeling and simulation of fading and pathloss in OPNET for range communications[A].Radio and Wireless Symposium IEEE[C].2007.407-410.

[3] LIU Y, PRESTI F L, MISRA V.Scalable fluid models and simulations for large-scale IP networks[J].ACM Transactions on Modeling and Computer Simulation(TOMACS), 2004,14(3):305-324.

[4] RILEY G, FUJIMOTO R, AMMAR M.A generic framework for parallelization of network simulations[A].Proceedings of Seventh International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication System[C].College Park, 1999.128-135.

[5] SZYMANSKI B K, SAIFEE A, SASTRY A.Genesis: a system for large-scale parallel network simulation[A].The 17th Workshop on Parallel and Distributed Simulation(PADS’03), IEEE[C].San Diego California, 2003.61-68.

[6] 李博.PDNS性能提高策略研究與實現(xiàn)[D].哈爾濱:哈爾濱工業(yè)大學(xué), 2009.LI B.The Research and Implementation of Strategy for Improving the Performance of PDNS[D].Harbin: Harbin Institute of Technology,2009.

[7] 郝志宇.并行網(wǎng)絡(luò)模擬中的遠(yuǎn)程路由計算和查找方法[J].通信學(xué)報, 2007,28(6): 66-73.HAO Z Y.Approach to remote routing computation and lookup in parallel network simulation[J].Journal on Communications, 2007,28(6): 66-73.

[8] RILEY G, JAAFAR T, FUJIMOTO R.Using ghosts for global topology knowledge in space-parallel distributed network simulations[J].Simulation, 2005,81(4): 267-277.

[9] RILEY G, AMMAR M, FUJIMOTO R.Stateless routing in network simulations[A].Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems[C].San Francisco, 2000.524-531.

[10] 鄭凱.高性能IP路由查找和分組分類技術(shù)的研究[D].北京:清華大學(xué), 2006.30-31.ZHENG K.Research on High Performance IP Route Lookup and Packet Classification[D].Beijing: Tsinghua University, 2006.30-31.

[11] AHN J S, OH S H.Dynamic calendar queue[A].Proceedings of the Thirty-Second Annual Simulation Symposium[C].San Diego, CA,1999.20-25.