并行網絡模擬中遠程路由策略的研究

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

（哈爾濱工業(yè)大學 計算機網絡與信息安全技術研究中心，黑龍江 哈爾濱 150001）

1 引言

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

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

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

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

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

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

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

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

圖1 拓撲舉例

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

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

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

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

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

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

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

2.1 將目的IP地址轉換為二元組

為了將目的IP轉換為二元組，本策略為每個子網設計了一個存儲查詢框架。如圖2所示。

圖2 遠程路由存儲與查詢的框架

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

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

圖3 舉例用拓撲

表1 N1子網中存儲的N2子網Record

2.2 Record的優(yōu)化

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

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

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

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

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

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

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

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

經樹區(qū)域收縮后，由于樹區(qū)域中的節(jié)點均被樹根節(jié)點代替，因此Record記錄的條數(shù)得到了減少。對圖3所示拓撲而言，經樹區(qū)域收縮后，其拓撲如圖5所示。

圖5 樹結構收縮后的拓撲

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

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

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

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

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

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

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

后連節(jié)點去重后，目的子網對應的記錄數(shù)目進一步減少。以圖5所示拓撲為例，經后連節(jié)點去重，N1中Record如表3所示。

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

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

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

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

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

圖6 冗余片段示意

經過邊界路由器去重，圖 5所示的拓撲中N1子網存儲的N2子網的記錄如表4所示。

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

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

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

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

為了對邊界路由器二元組進行路由，首先將拓撲中所有的邊界路由器編號，同一個子網中的編號連續(xù)。如圖5中，R1編號為1，R2編號為2，以此類推。其次，每個邊界路由器保存了2個結構：NHP、RLP，其中NHP稱為下一跳存儲表，采用數(shù)組存儲了本邊界路由器到所有邊界路由器的下一跳序列，存儲空間復雜度為O(N)，N為整個拓撲邊界路由器總數(shù)，查找的時間復雜度為O(1)。RLP稱為遠程鏈路存儲表，存儲了與該邊界路由器連接的所有遠程鏈路和另一端的邊界路由器編號，空間復雜度為O(k)，查找的時間復雜度為O(k)，k為連接的遠程鏈路個數(shù)。圖7顯示了R1節(jié)點上存儲的NHP和RLP的內容。

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

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

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

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

算法2遠程鏈路接收處理算法

3 實驗結果與分析

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

表5 測試用拓撲環(huán)境

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

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

圖8 各方法縮減比例

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

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

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

圖10 實驗中各部分內存占用量

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

圖11 2種路由策略的內存占用

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

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

圖 12顯示了基于優(yōu)化邊界和基于邊界路由器的遠程路由策略在實驗中的運行時間?？梢钥闯?，前者消耗的模擬時間明顯短于后者，時間比平均在25%以下。同時隨著拓撲的增大，前者的增長速度也慢于后者，基本以線性的速度增長。

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

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

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

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

4 結束語

路由的存儲和查找是影響網絡模擬性能的重要因素，相關的研究也提出了諸多降低內存和提高模擬速度的解決辦法。本文針對大規(guī)模的網絡模擬環(huán)境，以降低內存占用為主，提出了基于優(yōu)化邊界的遠程路由策略，使用樹區(qū)域收縮、后連節(jié)點去重和邊界路由器去重3種方法，大幅地降低了內存占用量，同時用邊界路由器ID取代目的IP作為路由轉發(fā)方式，有效地降低了路由查找時間。實驗中出現(xiàn)的問題，如層壓縮樹與子網個數(shù)相關和后連節(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è)大學, 2009.LI B.The Research and Implementation of Strategy for Improving the Performance of PDNS[D].Harbin: Harbin Institute of Technology,2009.

[7] 郝志宇.并行網絡模擬中的遠程路由計算和查找方法[J].通信學報, 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路由查找和分組分類技術的研究[D].北京:清華大學, 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.