余鎮危, 劉克儉
中國礦業大學(北京)，北京，100083
zwyu@cumtb.edu.cn
摘要：本文給出了組播覆蓋網絡MON動態路由的定義，并在此基礎上提出了MON動態組播路由計算所應考慮的問題，給出了基于分布式觸發重組的MON動態組播路由算法NPPR-N和NPPR-D，并在本文的最后對算法的復雜度進行了推證，對算法的有效性進行了以EAD模型為基礎平臺的網絡模擬。
關鍵詞：OVERLAY；組播；動態路由；分布式觸發重組
1 引言
現實的網絡環境，還不具備為實現某一種應用而全部改造或重新定制現有路由器或交換機的可能，如何利用已改造的有限的功能節點來完成與其新型應用需求線性逼近的網絡性能，這就是OVERLAY網絡目前所熱衷研究的問題。就組播問題來說，所有節點都具有組播功能的網絡稱為全組播網絡，這是為簡化問題的研究，而對網絡參數進行的極度弱化，過去包括目前所提出的幾乎所有的組播路由算法，雖然解決問題所使用的技術會有所不同，比如啟發式，螞蟻或遺傳，但都是針對全組播網絡而言。顯然這些在全組播網絡基礎上所提出的算法，距真正的應用于實際網絡，還有很大的距離。
2 MON組播樹問題的描述
目前在實際的網絡環境中，具有組播功能的結點的比率還不是很高，大約只有20%左右(2000年為17%)。而如何利用不足五分之一的組播功能節點來完成組播應用的需求呢？這就是我們研究組播OVERLAY網絡的初衷。網絡中只有部分節點具有組播功能的網絡我們稱其為部分組播網絡。在部分組播網絡中，所有的具有組播功能的節點就構成了對整個網絡的一個組播覆蓋（multicast overlay）,因此對部分組播網絡組播問題的研究就轉化為覆蓋網絡路由研究的一部分。組播覆蓋網絡組播樹與全組播網絡組播樹的不同之處在于，前者會包含很多重復的鏈路，而后者則沒有。因為組播覆蓋網絡中，如果從一個節點到幾個節點的路徑中有相同的鏈路，而相同鏈路中的節點如不具有組播功能，則這些相同的鏈路就無法共享。因此在組播覆蓋網絡中，組播樹的求解問題，就與一般定義的全組播網絡的組播樹的求解問題有所不同。
本文中有如下定義
定義1.1：在MON組播覆蓋網絡中，具有組播功能的結點為MV(multicastable Vertex)節點，反之，不具有組播功能的結點稱為NMV(Non-multicastable Vertex)節點。
定義1-2：組播覆蓋網絡組播樹：給定一個網絡有向圖G=(V,M,E,C),V由MV結點(組播功能結點)和NMV結點(非組播功能結點)組成，MV結點的集合為M，E為圖中所有邊的集合，C為邊所對應的權值的集合，從V中選擇一組結點(terminal)D,一個源結點s 
D,從G中生成一個樹T=(VT，MT，ET，CT)，使得樹的費用最小，生成的樹就稱為組播樹，其中T
G ，VT 
V，D
VT，，MT
VT，ET
E，T中的源結點s到每一個D中的結點都有通路，且s的入度為0，其中非端結點的NMV結點入度與出度相等，而非端結點的MV結點的出度至少等于其入度。
1基金項目：高等學校博士學科點專項科研基金資助課題（20030290003）
定義1-3：最短路徑：結點u,v
V之間的最短路徑是指從u到v的費用最小的路徑，用P(u,v)表示，若沿P(u,v)的結點有u,v0,v1…vk-1,vk,v,則P(u,v)={u,v0,v1…vk-1,vk,v}。結點到樹的最短路徑是指結點到該樹所有結點中路徑最短的那一條。
定義1-4：組播覆蓋網絡組播樹費用CT：設組播樹T中的鏈路有N條，而其中某一非組播鏈路如果出現的次數為ni次，如圖3-1中邊E(2，4)：則組播樹的總費用可表示成為：
CT
3 MON動態組播樹問題的描述
動態路由優化問題是多點通信所特有的。在點到點通信中，不會有第三方的介入。如果其中有一方想離開，整個通信進程也就終止了，因此不存在動態路由問題。而在多點通信中，參與通信組的成員可以隨時地離開，新的結點也可以隨時地加入而不影響整個通信進程。通信成員的動態性決定了多點路由的動態性。當然，動態路由的概念還可以擴展。由于鏈路失敗、局部擁塞、網絡拓撲變化等原因使某些成員脫離了通信組，那么這些成員重新加入到通信組的過程也就相當于一個新成員的加入過程。靜態路由優化是在通信開始之前，在一組己知的成員之間，利用某種優化算法來尋找路由。而對于動態路由，由于無法事先預測哪些成員將會加入或離開通信組。原則上還要求路由調整時對其它成員不造成影響或影響的程度很小。因此，動態路由的優化問題比靜態路由的更為復雜，但其研究成果卻對實際網絡更具現實意義。
多點動態路由優化同樣可分為網絡費用優化和目的地費用優化。由于目的地費用優化與目的結點加入或離開通信組的次序無關，只與該目的結點和源有關，因此動態路由中目的地費用優化問題和靜態路由中目的地費用優化問題是一樣的。本文主要研究動態路由中網絡費用優化問題。如不作特別說明，動態路由優化專指動態路由的網絡費用優化。
動態路由網絡費用優化問題可以描述為：給定連通的的平面圖G＝(V，E，c)。G有n個頂點，m條邊，即 
，
，邊費用函數c：E
R+。r是組成員更新請求，r=(r0,r1,r2…..rk)。其中ri＝(vi，pi)，
(加入，離開)。除了撤消整個通信進程的請求之外，每次請求只包括一個結點。
在ri請求后的組成員集合Si為： 
因為Si集合不知道請求rj(j>I)的情況，所以動態路由優化屬于在線問題。
動態路由優化問題可以分為四大類：
1．不允許結構重組的路由優化方案：指在有成員離開或新結點加入到通信組時，優化路由的原則，是對通信組內的其他成員的通信路徑不作改動。
2．完全結構重組的路由優化方案：指在現有的成員之間建立一個網絡費用最優路由樹。一旦有成員離開通信組或有新結點加入通信組，在更新后的成員之間再建立一個網絡費用最優路由樹。這實際上是退化到靜態路由優化問題。
3．部分結構重組的路由優化方案：指在成員更新后，只對路由樹的某些部分進行調整，被調整的路由鏈路數不超過一定上限。避免了全局調整的復雜計算，同時也將對其它成員的影響降低到最小。
4．觸發結構重組的路由優化方案：指在成員更新后，開始按不允許結構重組的優化方案來更新路由，同時監視更新后路由樹的費用。一旦路由樹費用與最優費用之比超過某個門限值，就進行一次結構重組。這時的結構重組可能是完全結構重組，也可能是部分結構重組。觸發結構重組的優化方案減少了路由重組的次數，節省了計算費用，并可將路由樹的費用和最優費用之比維持在一定的水平。它的缺點也在于沒有從根本上克服路由結構重組帶來的問題，并且需要不斷監視路由樹的費用，會增加路由優化的復雜性和額外開銷。
4 MON動態組播路由算法PRRN-N
全組播網絡的組播樹生成算法目前已提出了很多，在其時間復雜度可以忍受的前提下，目前所提出的算法大多是在尋求次優解，許多用啟發式算法或者遺傳算法、螞蟻算法等求解組播路由問題的文章相繼發表。然而應該認識到，啟發式算法有其自身的缺陷，即只能找到局部最優，遺傳算法和螞蟻算法雖然都是全局算法，但是其編解碼方法都比較復雜，個體編解碼復雜度為O(n2)~ O(n3)。另外，目前對組播路由問題的表述模型尚不統一。所以，在此本文利用簡潔的Prüfer編碼，通過構造完全圖的方式，把MON組播樹“樹核”的求解問題改為全組播路由問題來求解，以得到更快的通用的全組播網絡組播樹的遺傳算法。
4．1 PRRN－N覆蓋層組播“樹核”生成算法
MON中具有組播功能的結點，其組播路由問題的概念模型可以表示為：設網絡G(V,E)，V是節點 (表示所有具有組播功能及非組播功能結點的總和)的集合, E是邊(表示節點之間的點到點連接)的集合，邊權表示節點之間的組播代價。 給定源的集合 
,具有組播功能的結點集合
，對
要求解一棵滿足網絡費用代價最小的組播樹
，使得：T以s為根節點，且
，這里VT表示T的節點集合。
先將V中的帶有組播功能的結點集合D中的所有結點，以Dijkstra算法由圖G中的最短路構造其完全圖Kn，E是邊(任兩組播結點之間的連接)的集合，邊權表示結點之間的“組播代價”，在此為圖G中兩點間的最短路。
完全圖Kn的不同生成樹共有nn-2棵，正好可以用n-2位的n-進制整數來表示，每位數字都在[1..n]之間，它對應為Kn的節點編號，這就是Prüfer編碼，它為設計基于生成樹的優化問題的遺傳算法提供了最簡潔的編碼方案之一。由Prüfer序列到生成樹T的解碼算法seqToTree如下：
算法1 seqToTree
[算法開始]
輸入：Prüfer編碼序列P；
輸出：Kn的生成樹T；
[算法開始]
確定節點數n:=P的長度+2；
統計每個節點在P中的出現次數A[1..n]；
生成具有n個孤立節點的圖T,節點依次標記為1,2,…,n；
令Q為T的所有不在P中的節點編號集合,并非減有序；
當P非空，循環做
從P中移出第一個元素v, 從Q中移出第一個元素u, A[v]:=A[v]-1；
在T中增加邊<v,u>；
如果A[v]=0, 則折半插入v到Q中；
從Q中移出最后兩個元素v和u, 在T中增加邊<v,u>；
輸出T.
[算法結束]
由于Prüfer編碼代表的生成樹是無序樹（不指定根），而組播樹需要指定根，所以我們擴充Prüfer編碼為n-1位，最后一位代表根節點編號。另外，還需要對解碼得到的Kn的生成樹進行剪枝，刪除不在組播終點集D中的葉子節點才能得到所求的組播樹，剪枝算法prune的設計見如下：
算法2 prune
輸入：Kn的生成樹T,組播終點集合D;
輸出：組播樹T；
[算法開始]
對T做后根次序遍歷,一邊遍歷一邊做：
a)如果當前被遍歷節點v是葉子節點并且不在D中,則: 從T中刪除v；
輸出T.
[算法結束]
遺傳算法設計：
遺傳算法基于達爾文進化論的思想，將待求問題的解空間看成自然界，將解空間中的每個變量的目標函數值看成個體對環境的適應性，然后通過（自然）選擇、交叉、變異等遺傳操作不斷進化，在一個可以接受的時間內到達一代比較優秀的種群，其中包含了我們要求的最優或近似最優個體。
一個特定的遺傳算法主要由染色體編碼、種群初始化、適應值標定和遺傳算子（選擇、交叉和變異）設計等方面組成。基于前面的討論，我們設計了求解模型的遺傳算法：染色體用擴充的Prüfer編碼表示；給定具有n個節點的網絡G和種群規模P后，初始種群由隨機生成的P行n-1列的矩陣表示，其中的每個元素為[1..n]之間的整數，代表G中的節點編號；計算每個染色體（Prüfer序列）的適應值時，依次用算法seqToTree和prune得到組播樹T，通過計算該個體的優化目標值g，再對g做標定得到個體適應值f=1/(1+g)；選擇算子采用改進的一次旋轉賭輪方法；交叉算子采用隨機多點交叉；變異算子采用基因位變異和基因片變異（包括遷移和翻轉）；保優策略，即每代最優秀個體直接進入下一代而不參與交叉和變異。
算法復雜性分析：
從算法中可以看出，對每一染色體解碼求生成樹的復雜度為O(nlogn)，對生成樹進行剪枝得到組播分布樹的算法復雜度為O(n)；而對得到的組播樹進行優化目標值計算和適應值標定所需要的復雜度可以從如下方面分析：
根據Dijkstra的算法，計算每對節點間最短路徑需要O(n3)的復雜度。但是，我們注意到是在給定的組播樹T中，若求解的是有源樹，給定組播源點s后，對任意的d，計算節點對(s,d)之間的距離時只需從s出發對T做一次遍歷即可，復雜度為O(n)；若計算的是共享樹，則對任意的組播源點s，組播信息都是先從s通過第一跳單播到共享根，再從共享根到達每個組播終點d，所以計算節點對(s,d)之間的距離時也只需從共享根出發對T做一次遍歷，復雜度也為O(n)； 交叉算子和變異算子的復雜度均不超過O(n)；
于是，給定群規模P和最大進化代數maxG，該算法的計算復雜度為O(P×maxG×O(mlogm))式中m為組播功能結點數，相對于求解同類問題的其它算法而言，這個結果確實令人鼓舞。所有利用遺傳算法求解組播路由問題的算法都需要進行優化目標值的計算和適應值標定，以上的設計實現了一種更快的求解全組播網絡組播路由問題的遺傳算法。然而，應該注意的是，Prüfer數表示的是Kn的生成樹，而不是給定網絡G(V,E),|V|=n的生成樹；組播數T也不是G的生成樹，而是針對組播源點集S和組播功能結點集MV的steiner樹。在求得最優解后，需要將得到的組播樹按圖G中的最短路展開，并對相同路作歸并操作。以此才能得到所求部分組播網絡組播生成樹的“樹核”。如圖1.
圖1 覆蓋層組播“樹核”生成
4.2 PRRH-N結點動態加入算法：
[算法開始]
1)以部分組播網絡基于網絡費用最優的靜態組播樹生成算法先生成動態組播樹的“樹核”T。
2)當新的一個結點Di要加入組播組時，先計算其到“樹核”T中各組播結點MVi(其取值范圍是MVS集合的成員)的最短路。
3)比較此結點Di到源s的最短路近還是到離它最近的組播結點MVi的最短路近，如到源近直聯到源。在樹中加入結點Di及其到源的邊。
4)如到最近的MVi近，則檢查此MVi是否已是組播組內成員(本身是端結點或有別的結點通過此組播功能結點接入組播組)，如是，以此MVi結點為“登陸結點”接入組播組(如有兩個結點滿足要求，選擇距s近的那一MV結點)。樹中加入結點Di及其到此MVi結點的邊
5)如最近的MVi結點還不是組內結點，則向它注冊, 并告之此Di到它的最短路是多少及到源的最短路是多少，同時計算所有向此結點注冊的結點經它連入組播樹的費用和是否小于直連源的費用和，如是所有注冊結點由其連入組播樹，反之計算此Di到“樹核”T上各組播功能結點MVi及MVi到源s的最短路徑的值,找到T中含有組播結點MVi的到源s的最短路Pmin，比較此結點Di到源s的最短路近還是到擁有Pmin的組播結點MVi的最短路近，如到源近直聯到源。在樹中加入結點Di及其到源的邊。
6)反之，選擇此擁有Pmin的組播結點MVi作為此結點的“登陸結點”連入組播組(如有多點滿足要求，選擇距s遠的那一MV結點)。并在組播樹中加入Pmin邊。
[算法結束]
如圖2.
圖2. PRRH-N結點動態加入算法
4.3 PRRH-N結點動態退出算法：
[算法開始]
1)如果此結點是直聯到源的，且路徑中沒有別的組內成員，則將路中所有的結點從樹中刪除。并在距此點最近的MVi結點注消此結點
2)如果此結點是直聯到源的，但路徑中還有別的組內成員，則將此結點刪除直到另一組內成員成為葉子結點為止。在距此點最近的MVi結點注消此結點的同時，注消新的葉子結點，并對這一剛成為葉子結點的組內成員用動態結點加入算法重新加入組播組。
3)如果此結點是聯到“樹核”T中的組播功能結點MVi上的，且MVi上還連著其它的組內成員，在刪除此結點的同時，要計算所有經此MVi結點連入組播組的結點至源s的費用總和是否大于其向源直聯的費用總和。如是注消這些結點，并用動態結點加入算法將這些結點重新加入組播組。
[算法結束]
5 MON動態組播路由算法PRRN-D
目的地費用最優路由算法是用來優化路由的目的地費用。如果是點到點通信，那么目的地費用最優也就是網絡費用最優。但在多點通信中，兩者并不等價。在點到多點通信中，可以先計算源到每個目的結點的費用最優路徑。然后將這些路徑合并(全組播網絡)。路徑中相同的鏈路可以被共享。形成的路由樹稱為目的地費用最優組播路由樹。雖然目的地費用最優組播路由樹的網絡費用不一定是最優的，但可以推測它的網絡費用至少不會太差。并且目的地費用最優路由樹的網絡費用與目的結點加入或離開通信組的先后次序無關，這對于動態路由的優化是有益的。因此目的地費用最優路由算法也可以在多點動態路由中優化網絡費用。
5.1 PRRH-D覆蓋層組播“樹核”生成算法
MON中具有組播功能的節點亦可依據目的地費用最優的思想，以啟發的方法高速構成PRRN－D覆蓋層組播“樹核”。其算法如下：
[算法開始]
1)選擇組播功能結點集合MVS的成員，各組播功能結點先對組播源點s以Dijkstra算法最短路尋路，然后執行“歸并操作”即合并相同邊，“歸并操作”后的組播樹即為我們所要求的部分組播網絡組播樹的“樹核”。
2)對“歸并操作”后的組播結點“樹核”，計算每一個組播結點到源s的路徑長度，并寫入各組播結點的路由表。
[算法結束]
5.2 PRRH-D結點動態加入算法：
[算法開始]
1)以部分組播網絡基于目的地費用最優的靜態組播樹生成算法先生成動態組播樹的“樹核”T。
2)當新的一個結點Di要加入組播組時，先計算其到“樹核”T中各組播結點MVi(其取值范圍是MVS集合的成員)的最短路。
3)比較此結點Di到源s的最短路近還是到離它最近的組播結點MVi的最短路近，如到源近直聯到源。在樹中加入結點Di及其到源的邊。
4)如到最近的MVi近，則檢查此MVi是否已是組播組內成員(本身是端結點或有別的結點通過此組播功能結點接入組播組)，如是，以此MVi結點為“登陸結點”接入組播組(如有兩點滿足要求，選擇距s近的那一MV結點)。樹中加入結點Di及其到此MVi結點的邊
5)如最近的MVi結點還不是組內結點，則向它注冊, 并告之此Di到它的最短路是多少及到源的最短路是多少，同時計算所有向此結點注冊的結點經它連入組播樹的費用和是否小于直連源的費用和，如是所有注冊結點由其連入組播樹，反之計算此Di到“樹核”T上各組播功能結點MVi及MVi到源s的最短路徑的值,找到T中含有組播結點MVi的到源s的最短路Pmin，比較此結點Di到源s的最短路近還是到擁有Pmin的組播結點MVi的最短路近，如到源近直聯到源。在樹中加入結點Di及其到源的邊。
6)反之，選擇此擁有Pmin的組播結點MVi作為此結點的“登陸結點”連入組播組(如有兩點滿足要求，選擇距s遠的那一MV結點)。并在組播樹中加入Pmin邊。
[算法結束]
5.3 PRRH-D結點動態退出算法：
[算法開始]
1)如果此結點是直聯到源的，且路徑中沒有別的組內成員，則將路中所有的結點從樹中刪除。并在距此點最近的MVi結點注消此結點
2)如果此結點是直聯到源的，但路徑中還有別的組內成員，則將此結點刪除直到另一組內成員成為葉子結點為止。在距此點最近的MVi結點注消此結點的同時，注消新的葉子結點，并對這一剛成為葉子結點的組內成員用動態結點加入算法重新加入組播組。
3)如果此結點是聯到“樹核”T中的組播功能結點MVi上的，且MVi上還連著其它的組內成員，在刪除此結點的同時，要計算所有經此MVi結點連入組播組的結點至源s的費用總和是否大于其向源直聯的費用總和。如是，則注消這些結點，并用動態結點加入算法將這些結點重新加入組播組。
[算法結束]
以上算法參見圖畫3.
圖3 覆蓋層組播“樹核”生成及節點動態加入、退出舉例
6 兩種算法復雜度及網絡模擬
PRRH-D算法：其組播結點樹核生成時，采用的是Dijkstra算法，然后對各組播結點向源結點s所尋到的最短路進行歸并，設其MV結點數為m，網絡規模即網絡中總的結點數為n，則其樹核生成最壞情況下時間復雜度為 
。而各終端結點加入組播組時每一結點最壞情況下要調用Dijkstra算法三次，分別對源結點s及樹核內距終端結點Di最近的MV結點和具有P(Di,MVi,s)min的MV結點尋最短路，最壞情況下，每一終端結點最終加入組播組的時間復雜度為
。PRRH-D算法的每一結點退出操作的最差情況的時間復雜度為
，t為組播樹中所含的結點數，而因此而選擇重新選路的各終端結點需再次調用Dijkstra算法三次，如這部分結點數為r,則最壞情況下，這部分終端結點最終加入組播組的時間復雜度為
。
PRRH-N算法屬于源路由算法(source-rooted routing)。源路由算法的結點經某一路由協議(如鏈路狀態協議)獲得完整的網絡拓樸信息。網絡中每一結點的拓樸信息是一樣的，所以網絡中每一結點都可以接受用戶呼叫并進行路由計算。假設網絡狀態信息在算法執行之前已經完成，且在算法計算路由時，網絡的拓樸狀態不變。則NCH及DCH算法的時間復雜度的計算就可以分為兩個獨立的兩個部分(組播結點樹核的生成及終端結點最終完成加入組播組)來計算，綜述如下：
其組播組結點樹核生成時，首先要以組播功能結點間的最短路生成其全連通網絡。采用Dijkstra算法，各組播結點及源結點s間彼此最短路尋徑，設其MV結點數為m，網絡規模即網絡中總的結點數為n，則組播功能結點全連通網絡生成在最壞情況下時間復雜度為
。而樹核生成的遺傳算法和seqToTree算法的時間復雜度為O(P×maxG×O(mlogm))。同樣每一終端結點加入組播組時每一結點最壞情況下要調用Dijkstra算法三次，分別對源結點s及樹核內距終端結點Di最近的MV結點和具有P(Di,MVi,s)min的MV結點尋最短路，最壞情況下，每一終端結點最終加入組播組的時間復雜度為
。PRRH-N算法的每一結點退出操作的最差情況的時間復雜度為
，t為組播樹中所含的結點數，而因此選擇重新選路的各終端結點需再次調用Dijkstra算法三次，如這部分結點數為r,則最壞情況下，這部分終端結點最終加入組播組的時間復雜度為
。
由于兩種算法都采用了分布式觸發的思想，無需覆蓋層對整體的費用做出監控及評價，故而從基礎解決了原觸發重組費用優化方案的缺點，減輕了路由優化的復雜性和額外開銷。
目前對于MON網絡動態組播樹的生成算法，還沒有研究人員進行過系統的研究，因此也還沒有基準算法來用于網絡模擬和比較。因此，本文的網絡模擬只能采用課題組MON靜態組播樹生成算法NCH來作為模擬基準。
·圖4 PRRH-N，PRRH-D算法EAD仿真網絡模擬數據
本文以課題組EAD仿真模型所生成的模擬網絡來做模擬平臺，在EAD算法生成的模擬網絡過程中，其MV結點比例是固定的(17%)，而長短邊之比隨著不同的需求，通過對 
及F2的調節，也可以被定位于一很小的領域內，所以在同一網絡規模前提下影響部分組播網絡動態組播樹生成算法的可變因素主要有：1.加入組播組的端結點的更新速度,2.在某一時刻，組播組成員數量在模擬網絡的全部結點中所占的比例，對于這兩點，都可以以一個無量綱的概念，對不同的網絡規模進行一致的模擬，以利于后期實驗結果的比較。
本文采用以下假設：加入組播組的端結點以一種穩定的速度進行更新，即某一時刻有占網絡結點總數5%的組播組成員退出組播組，而另有占網絡結點總數5%的非組播組成員加入組播組，而初始狀態選擇組播組成員占總結點數的20%和40%來進行模擬。這樣就有可能選擇相同的靜態部分組播網絡組播樹生成算法來作為待模擬算法的基準算法，以便能從本質上把握待模擬算法的一些基本特征，并給出其性能評價。
由模擬數據可知(見圖4)，PRRH-N和PRRH-D算法因為可以在結點加入組播組及結點退出組播組時都能觸發樹結構的部分重組。所以其費用能夠被限定在基準以上的一個很小的區域內，因為考慮到現實網絡中的實現問題，兩種算法都沒有終端結點向上歸并的操作，所以，實驗中可見費用會出現“躍點”，特別是當組播組成員比例相對較小時，這一點表現的尤為突出。在組播組成員比例進一步增加時，兩種算法都表現出很好的收斂性，而且其費用的統計平均值也均被限定在不高于基準的10%，這一結果還是非常令人鼓舞的。
7 結束語
PRRH-N算法在費用優化方面是兩種算法中最優的，基于結點費用最優觸發重組操作，能最大限度的減小算法的散列躍度，算法收斂性能夠有一個很好保證，但時間復雜度整體來說過大，在實際應用中，可操作性要明顯低于PRRH-D算法。但在組播組成員相對較少時，對費用優化苛刻的前提下，該算法還是應該成為首選的。
PRRH-D算法在時間復雜度方面較PRRH-N算法為優，而其網絡費用優化又明顯的線性逼近
PRRH-N算法，在組播組成員比例達到40%左右時，該算法的費用優化性能已近似等于PRRH-N算法，
故在對算法計算時間及費用優化都有較高要求時，還是選用PRRH-D算法為好。
因兩種算法都是基于“樹核”的，所以兩種算法都可以在一定路由協議的支持下進行多面體分級路由模式的改良，也可以方便的向多點對多點組播路由算法改進，這樣就能夠使算法在可擴展性方面有一個質的提高，同時也可以使其向多點對多點路由計算提供良好的支持。其次，基于“樹核”的路由方式，也可以在鏈路負載平衡方面較原有的CBT算法(原針對全組播網絡的一種多對多組播路由算法)有一個質的提高。以上方案都將是今后對于部分組播網絡路由算法研究的很好的方向。
參考文獻
[1] 董慶陽, 計算機通信網絡組播路由算法和協議的研究, 上海交通大學博士學位論文, 2000年
[2] 王征應, 高速網絡QOS路由技術的研究及路由仿真平臺的研制, 華中科技大學博士學位論文, 2001年
[3] 李漢兵, 計算機網絡路由算法, 西安電子科技大學博士學位論文, 2000年
[4] Yunxi Sherlia Shi . Design of Overlay Networks for Internet Multicast.(PhD thesis ).[D]. Washington University. August, 2002
[5] G.N.Rouskas and I.Baldine. Multicast Rjouting with End-to-End Delay and Delay Variation Constraints. IEEE Journal on selected Areas in Communications, 1997, Vol.15:346-356
[6] Ghosh, M. Fry, and J. Crowcroft. An architecture for application layer routing.[C]. In 2nd Int. Working Conf. on Active
Distributed Dynamic Routing on the Multicast Overlay Network
YU Zhenwei, LIU Kejian
China University of Mining and Technology-Beijing, Beijing, 100083
zwyu@cumtb.edu.cn
Abstract ： This text gives a definition for the dynamic routing in MON the Multicast Overlay Network, and put forward the problems of the dynamic route computing should be considerated for the first time, and a Arithmetic PRRH-N & PRRH-D according to the distributing triggers the reorganization , in the end ,the report calculate the complexity of the Arithmetic , simulate the PRRH-N on the model of EAD .
Key words: overlay ; multicast ; dynamic routing ; distributed triggers the reorganization
余鎮危, 劉克儉
中國礦業大學(北京)，北京，100083
zwyu@cumtb.edu.cn
摘要：本文給出了組播覆蓋網絡MON動態路由的定義，并在此基礎上提出了MON動態組播路由計算所應考慮的問題，給出了基于分布式觸發重組的MON動態組播路由算法NPPR-N和NPPR-D，并在本文的最后對算法的復雜度進行了推證，對算法的有效性進行了以EAD模型為基礎平臺的網絡模擬。
關鍵詞：OVERLAY；組播；動態路由；分布式觸發重組
1 引言
現實的網絡環境，還不具備為實現某一種應用而全部改造或重新定制現有路由器或交換機的可能，如何利用已改造的有限的功能節點來完成與其新型應用需求線性逼近的網絡性能，這就是OVERLAY網絡目前所熱衷研究的問題。就組播問題來說，所有節點都具有組播功能的網絡稱為全組播網絡，這是為簡化問題的研究，而對網絡參數進行的極度弱化，過去包括目前所提出的幾乎所有的組播路由算法，雖然解決問題所使用的技術會有所不同，比如啟發式，螞蟻或遺傳，但都是針對全組播網絡而言。顯然這些在全組播網絡基礎上所提出的算法，距真正的應用于實際網絡，還有很大的距離。
2 MON組播樹問題的描述
目前在實際的網絡環境中，具有組播功能的結點的比率還不是很高，大約只有20%左右(2000年為17%)。而如何利用不足五分之一的組播功能節點來完成組播應用的需求呢？這就是我們研究組播OVERLAY網絡的初衷。網絡中只有部分節點具有組播功能的網絡我們稱其為部分組播網絡。在部分組播網絡中，所有的具有組播功能的節點就構成了對整個網絡的一個組播覆蓋（multicast overlay）,因此對部分組播網絡組播問題的研究就轉化為覆蓋網絡路由研究的一部分。組播覆蓋網絡組播樹與全組播網絡組播樹的不同之處在于，前者會包含很多重復的鏈路，而后者則沒有。因為組播覆蓋網絡中，如果從一個節點到幾個節點的路徑中有相同的鏈路，而相同鏈路中的節點如不具有組播功能，則這些相同的鏈路就無法共享。因此在組播覆蓋網絡中，組播樹的求解問題，就與一般定義的全組播網絡的組播樹的求解問題有所不同。
本文中有如下定義
定義1.1：在MON組播覆蓋網絡中，具有組播功能的結點為MV(multicastable Vertex)節點，反之，不具有組播功能的結點稱為NMV(Non-multicastable Vertex)節點。
定義1-2：組播覆蓋網絡組播樹：給定一個網絡有向圖G=(V,M,E,C),V由MV結點(組播功能結點)和NMV結點(非組播功能結點)組成，MV結點的集合為M，E為圖中所有邊的集合，C為邊所對應的權值的集合，從V中選擇一組結點(terminal)D,一個源結點s D,從G中生成一個樹T=(VT，MT，ET，CT)，使得樹的費用最小，生成的樹就稱為組播樹，其中TG ，VT V，DVT，，MTVT，ETE，T中的源結點s到每一個D中的結點都有通路，且s的入度為0，其中非端結點的NMV結點入度與出度相等，而非端結點的MV結點的出度至少等于其入度。
1基金項目：高等學校博士學科點專項科研基金資助課題（20030290003）
定義1-3：最短路徑：結點u,vV之間的最短路徑是指從u到v的費用最小的路徑，用P(u,v)表示，若沿P(u,v)的結點有u,v0,v1…vk-1,vk,v,則P(u,v)={u,v0,v1…vk-1,vk,v}。結點到樹的最短路徑是指結點到該樹所有結點中路徑最短的那一條。
定義1-4：組播覆蓋網絡組播樹費用CT：設組播樹T中的鏈路有N條，而其中某一非組播鏈路如果出現的次數為ni次，如圖3-1中邊E(2，4)：則組播樹的總費用可表示成為：
CT
3 MON動態組播樹問題的描述
動態路由優化問題是多點通信所特有的。在點到點通信中，不會有第三方的介入。如果其中有一方想離開，整個通信進程也就終止了，因此不存在動態路由問題。而在多點通信中，參與通信組的成員可以隨時地離開，新的結點也可以隨時地加入而不影響整個通信進程。通信成員的動態性決定了多點路由的動態性。當然，動態路由的概念還可以擴展。由于鏈路失敗、局部擁塞、網絡拓撲變化等原因使某些成員脫離了通信組，那么這些成員重新加入到通信組的過程也就相當于一個新成員的加入過程。靜態路由優化是在通信開始之前，在一組己知的成員之間，利用某種優化算法來尋找路由。而對于動態路由，由于無法事先預測哪些成員將會加入或離開通信組。原則上還要求路由調整時對其它成員不造成影響或影響的程度很小。因此，動態路由的優化問題比靜態路由的更為復雜，但其研究成果卻對實際網絡更具現實意義。
多點動態路由優化同樣可分為網絡費用優化和目的地費用優化。由于目的地費用優化與目的結點加入或離開通信組的次序無關，只與該目的結點和源有關，因此動態路由中目的地費用優化問題和靜態路由中目的地費用優化問題是一樣的。本文主要研究動態路由中網絡費用優化問題。如不作特別說明，動態路由優化專指動態路由的網絡費用優化。
動態路由網絡費用優化問題可以描述為：給定連通的的平面圖G＝(V，E，c)。G有n個頂點，m條邊，即 ，，邊費用函數c：ER+。r是組成員更新請求，r=(r0,r1,r2…..rk)。其中ri＝(vi，pi)，(加入，離開)。除了撤消整個通信進程的請求之外，每次請求只包括一個結點。
在ri請求后的組成員集合Si為： 因為Si集合不知道請求rj(j>I)的情況，所以動態路由優化屬于在線問題。
動態路由優化問題可以分為四大類：
1．不允許結構重組的路由優化方案：指在有成員離開或新結點加入到通信組時，優化路由的原則，是對通信組內的其他成員的通信路徑不作改動。
2．完全結構重組的路由優化方案：指在現有的成員之間建立一個網絡費用最優路由樹。一旦有成員離開通信組或有新結點加入通信組，在更新后的成員之間再建立一個網絡費用最優路由樹。這實際上是退化到靜態路由優化問題。
3．部分結構重組的路由優化方案：指在成員更新后，只對路由樹的某些部分進行調整，被調整的路由鏈路數不超過一定上限。避免了全局調整的復雜計算，同時也將對其它成員的影響降低到最小。
4．觸發結構重組的路由優化方案：指在成員更新后，開始按不允許結構重組的優化方案來更新路由，同時監視更新后路由樹的費用。一旦路由樹費用與最優費用之比超過某個門限值，就進行一次結構重組。這時的結構重組可能是完全結構重組，也可能是部分結構重組。觸發結構重組的優化方案減少了路由重組的次數，節省了計算費用，并可將路由樹的費用和最優費用之比維持在一定的水平。它的缺點也在于沒有從根本上克服路由結構重組帶來的問題，并且需要不斷監視路由樹的費用，會增加路由優化的復雜性和額外開銷。
4 MON動態組播路由算法PRRN-N
全組播網絡的組播樹生成算法目前已提出了很多，在其時間復雜度可以忍受的前提下，目前所提出的算法大多是在尋求次優解，許多用啟發式算法或者遺傳算法、螞蟻算法等求解組播路由問題的文章相繼發表。然而應該認識到，啟發式算法有其自身的缺陷，即只能找到局部最優，遺傳算法和螞蟻算法雖然都是全局算法，但是其編解碼方法都比較復雜，個體編解碼復雜度為O(n2)~ O(n3)。另外，目前對組播路由問題的表述模型尚不統一。所以，在此本文利用簡潔的Prüfer編碼，通過構造完全圖的方式，把MON組播樹“樹核”的求解問題改為全組播路由問題來求解，以得到更快的通用的全組播網絡組播樹的遺傳算法。
4．1 PRRN－N覆蓋層組播“樹核”生成算法
MON中具有組播功能的結點，其組播路由問題的概念模型可以表示為：設網絡G(V,E)，V是節點 (表示所有具有組播功能及非組播功能結點的總和)的集合, E是邊(表示節點之間的點到點連接)的集合，邊權表示節點之間的組播代價。 給定源的集合 ,具有組播功能的結點集合，對要求解一棵滿足網絡費用代價最小的組播樹，使得：T以s為根節點，且，這里VT表示T的節點集合。
先將V中的帶有組播功能的結點集合D中的所有結點，以Dijkstra算法由圖G中的最短路構造其完全圖Kn，E是邊(任兩組播結點之間的連接)的集合，邊權表示結點之間的“組播代價”，在此為圖G中兩點間的最短路。
完全圖Kn的不同生成樹共有nn-2棵，正好可以用n-2位的n-進制整數來表示，每位數字都在[1..n]之間，它對應為Kn的節點編號，這就是Prüfer編碼，它為設計基于生成樹的優化問題的遺傳算法提供了最簡潔的編碼方案之一。由Prüfer序列到生成樹T的解碼算法seqToTree如下：
算法1 seqToTree
[算法開始]
輸入：Prüfer編碼序列P；
輸出：Kn的生成樹T；
[算法開始]
確定節點數n:=P的長度+2；
統計每個節點在P中的出現次數A[1..n]；
生成具有n個孤立節點的圖T,節點依次標記為1,2,…,n；
令Q為T的所有不在P中的節點編號集合,并非減有序；
當P非空，循環做
從P中移出第一個元素v, 從Q中移出第一個元素u, A[v]:=A[v]-1；
在T中增加邊<v,u>；
如果A[v]=0, 則折半插入v到Q中；
從Q中移出最后兩個元素v和u, 在T中增加邊<v,u>；
輸出T.
[算法結束]
由于Prüfer編碼代表的生成樹是無序樹（不指定根），而組播樹需要指定根，所以我們擴充Prüfer編碼為n-1位，最后一位代表根節點編號。另外，還需要對解碼得到的Kn的生成樹進行剪枝，刪除不在組播終點集D中的葉子節點才能得到所求的組播樹，剪枝算法prune的設計見如下：
算法2 prune
輸入：Kn的生成樹T,組播終點集合D;
輸出：組播樹T；
[算法開始]
對T做后根次序遍歷,一邊遍歷一邊做：
a)如果當前被遍歷節點v是葉子節點并且不在D中,則: 從T中刪除v；
輸出T.
[算法結束]
遺傳算法設計：
遺傳算法基于達爾文進化論的思想，將待求問題的解空間看成自然界，將解空間中的每個變量的目標函數值看成個體對環境的適應性，然后通過（自然）選擇、交叉、變異等遺傳操作不斷進化，在一個可以接受的時間內到達一代比較優秀的種群，其中包含了我們要求的最優或近似最優個體。
一個特定的遺傳算法主要由染色體編碼、種群初始化、適應值標定和遺傳算子（選擇、交叉和變異）設計等方面組成。基于前面的討論，我們設計了求解模型的遺傳算法：染色體用擴充的Prüfer編碼表示；給定具有n個節點的網絡G和種群規模P后，初始種群由隨機生成的P行n-1列的矩陣表示，其中的每個元素為[1..n]之間的整數，代表G中的節點編號；計算每個染色體（Prüfer序列）的適應值時，依次用算法seqToTree和prune得到組播樹T，通過計算該個體的優化目標值g，再對g做標定得到個體適應值f=1/(1+g)；選擇算子采用改進的一次旋轉賭輪方法；交叉算子采用隨機多點交叉；變異算子采用基因位變異和基因片變異（包括遷移和翻轉）；保優策略，即每代最優秀個體直接進入下一代而不參與交叉和變異。
算法復雜性分析：
從算法中可以看出，對每一染色體解碼求生成樹的復雜度為O(nlogn)，對生成樹進行剪枝得到組播分布樹的算法復雜度為O(n)；而對得到的組播樹進行優化目標值計算和適應值標定所需要的復雜度可以從如下方面分析：
根據Dijkstra的算法，計算每對節點間最短路徑需要O(n3)的復雜度。但是，我們注意到是在給定的組播樹T中，若求解的是有源樹，給定組播源點s后，對任意的d，計算節點對(s,d)之間的距離時只需從s出發對T做一次遍歷即可，復雜度為O(n)；若計算的是共享樹，則對任意的組播源點s，組播信息都是先從s通過第一跳單播到共享根，再從共享根到達每個組播終點d，所以計算節點對(s,d)之間的距離時也只需從共享根出發對T做一次遍歷，復雜度也為O(n)； 交叉算子和變異算子的復雜度均不超過O(n)；
于是，給定群規模P和最大進化代數maxG，該算法的計算復雜度為O(P×maxG×O(mlogm))式中m為組播功能結點數，相對于求解同類問題的其它算法而言，這個結果確實令人鼓舞。所有利用遺傳算法求解組播路由問題的算法都需要進行優化目標值的計算和適應值標定，以上的設計實現了一種更快的求解全組播網絡組播路由問題的遺傳算法。然而，應該注意的是，Prüfer數表示的是Kn的生成樹，而不是給定網絡G(V,E),|V|=n的生成樹；組播數T也不是G的生成樹，而是針對組播源點集S和組播功能結點集MV的steiner樹。在求得最優解后，需要將得到的組播樹按圖G中的最短路展開，并對相同路作歸并操作。以此才能得到所求部分組播網絡組播生成樹的“樹核”。如圖1.
圖1 覆蓋層組播“樹核”生成
4.2 PRRH-N結點動態加入算法：
[算法開始]
1)以部分組播網絡基于網絡費用最優的靜態組播樹生成算法先生成動態組播樹的“樹核”T。
2)當新的一個結點Di要加入組播組時，先計算其到“樹核”T中各組播結點MVi(其取值范圍是MVS集合的成員)的最短路。
3)比較此結點Di到源s的最短路近還是到離它最近的組播結點MVi的最短路近，如到源近直聯到源。在樹中加入結點Di及其到源的邊。
4)如到最近的MVi近，則檢查此MVi是否已是組播組內成員(本身是端結點或有別的結點通過此組播功能結點接入組播組)，如是，以此MVi結點為“登陸結點”接入組播組(如有兩個結點滿足要求，選擇距s近的那一MV結點)。樹中加入結點Di及其到此MVi結點的邊
5)如最近的MVi結點還不是組內結點，則向它注冊, 并告之此Di到它的最短路是多少及到源的最短路是多少，同時計算所有向此結點注冊的結點經它連入組播樹的費用和是否小于直連源的費用和，如是所有注冊結點由其連入組播樹，反之計算此Di到“樹核”T上各組播功能結點MVi及MVi到源s的最短路徑的值,找到T中含有組播結點MVi的到源s的最短路Pmin，比較此結點Di到源s的最短路近還是到擁有Pmin的組播結點MVi的最短路近，如到源近直聯到源。在樹中加入結點Di及其到源的邊。
6)反之，選擇此擁有Pmin的組播結點MVi作為此結點的“登陸結點”連入組播組(如有多點滿足要求，選擇距s遠的那一MV結點)。并在組播樹中加入Pmin邊。
[算法結束]
如圖2.
圖2. PRRH-N結點動態加入算法
4.3 PRRH-N結點動態退出算法：
[算法開始]
1)如果此結點是直聯到源的，且路徑中沒有別的組內成員，則將路中所有的結點從樹中刪除。并在距此點最近的MVi結點注消此結點
2)如果此結點是直聯到源的，但路徑中還有別的組內成員，則將此結點刪除直到另一組內成員成為葉子結點為止。在距此點最近的MVi結點注消此結點的同時，注消新的葉子結點，并對這一剛成為葉子結點的組內成員用動態結點加入算法重新加入組播組。
3)如果此結點是聯到“樹核”T中的組播功能結點MVi上的，且MVi上還連著其它的組內成員，在刪除此結點的同時，要計算所有經此MVi結點連入組播組的結點至源s的費用總和是否大于其向源直聯的費用總和。如是注消這些結點，并用動態結點加入算法將這些結點重新加入組播組。
[算法結束]
5 MON動態組播路由算法PRRN-D
目的地費用最優路由算法是用來優化路由的目的地費用。如果是點到點通信，那么目的地費用最優也就是網絡費用最優。但在多點通信中，兩者并不等價。在點到多點通信中，可以先計算源到每個目的結點的費用最優路徑。然后將這些路徑合并(全組播網絡)。路徑中相同的鏈路可以被共享。形成的路由樹稱為目的地費用最優組播路由樹。雖然目的地費用最優組播路由樹的網絡費用不一定是最優的，但可以推測它的網絡費用至少不會太差。并且目的地費用最優路由樹的網絡費用與目的結點加入或離開通信組的先后次序無關，這對于動態路由的優化是有益的。因此目的地費用最優路由算法也可以在多點動態路由中優化網絡費用。
5.1 PRRH-D覆蓋層組播“樹核”生成算法
MON中具有組播功能的節點亦可依據目的地費用最優的思想，以啟發的方法高速構成PRRN－D覆蓋層組播“樹核”。其算法如下：
[算法開始]
1)選擇組播功能結點集合MVS的成員，各組播功能結點先對組播源點s以Dijkstra算法最短路尋路，然后執行“歸并操作”即合并相同邊，“歸并操作”后的組播樹即為我們所要求的部分組播網絡組播樹的“樹核”。
2)對“歸并操作”后的組播結點“樹核”，計算每一個組播結點到源s的路徑長度，并寫入各組播結點的路由表。
[算法結束]
5.2 PRRH-D結點動態加入算法：
[算法開始]
1)以部分組播網絡基于目的地費用最優的靜態組播樹生成算法先生成動態組播樹的“樹核”T。
2)當新的一個結點Di要加入組播組時，先計算其到“樹核”T中各組播結點MVi(其取值范圍是MVS集合的成員)的最短路。
3)比較此結點Di到源s的最短路近還是到離它最近的組播結點MVi的最短路近，如到源近直聯到源。在樹中加入結點Di及其到源的邊。
4)如到最近的MVi近，則檢查此MVi是否已是組播組內成員(本身是端結點或有別的結點通過此組播功能結點接入組播組)，如是，以此MVi結點為“登陸結點”接入組播組(如有兩點滿足要求，選擇距s近的那一MV結點)。樹中加入結點Di及其到此MVi結點的邊
5)如最近的MVi結點還不是組內結點，則向它注冊, 并告之此Di到它的最短路是多少及到源的最短路是多少，同時計算所有向此結點注冊的結點經它連入組播樹的費用和是否小于直連源的費用和，如是所有注冊結點由其連入組播樹，反之計算此Di到“樹核”T上各組播功能結點MVi及MVi到源s的最短路徑的值,找到T中含有組播結點MVi的到源s的最短路Pmin，比較此結點Di到源s的最短路近還是到擁有Pmin的組播結點MVi的最短路近，如到源近直聯到源。在樹中加入結點Di及其到源的邊。
6)反之，選擇此擁有Pmin的組播結點MVi作為此結點的“登陸結點”連入組播組(如有兩點滿足要求，選擇距s遠的那一MV結點)。并在組播樹中加入Pmin邊。
[算法結束]
5.3 PRRH-D結點動態退出算法：
[算法開始]
1)如果此結點是直聯到源的，且路徑中沒有別的組內成員，則將路中所有的結點從樹中刪除。并在距此點最近的MVi結點注消此結點
2)如果此結點是直聯到源的，但路徑中還有別的組內成員，則將此結點刪除直到另一組內成員成為葉子結點為止。在距此點最近的MVi結點注消此結點的同時，注消新的葉子結點，并對這一剛成為葉子結點的組內成員用動態結點加入算法重新加入組播組。
3)如果此結點是聯到“樹核”T中的組播功能結點MVi上的，且MVi上還連著其它的組內成員，在刪除此結點的同時，要計算所有經此MVi結點連入組播組的結點至源s的費用總和是否大于其向源直聯的費用總和。如是，則注消這些結點，并用動態結點加入算法將這些結點重新加入組播組。
[算法結束]
以上算法參見圖畫3.
圖3 覆蓋層組播“樹核”生成及節點動態加入、退出舉例
6 兩種算法復雜度及網絡模擬
PRRH-D算法：其組播結點樹核生成時，采用的是Dijkstra算法，然后對各組播結點向源結點s所尋到的最短路進行歸并，設其MV結點數為m，網絡規模即網絡中總的結點數為n，則其樹核生成最壞情況下時間復雜度為 。而各終端結點加入組播組時每一結點最壞情況下要調用Dijkstra算法三次，分別對源結點s及樹核內距終端結點Di最近的MV結點和具有P(Di,MVi,s)min的MV結點尋最短路，最壞情況下，每一終端結點最終加入組播組的時間復雜度為。PRRH-D算法的每一結點退出操作的最差情況的時間復雜度為，t為組播樹中所含的結點數，而因此而選擇重新選路的各終端結點需再次調用Dijkstra算法三次，如這部分結點數為r,則最壞情況下，這部分終端結點最終加入組播組的時間復雜度為。
PRRH-N算法屬于源路由算法(source-rooted routing)。源路由算法的結點經某一路由協議(如鏈路狀態協議)獲得完整的網絡拓樸信息。網絡中每一結點的拓樸信息是一樣的，所以網絡中每一結點都可以接受用戶呼叫并進行路由計算。假設網絡狀態信息在算法執行之前已經完成，且在算法計算路由時，網絡的拓樸狀態不變。則NCH及DCH算法的時間復雜度的計算就可以分為兩個獨立的兩個部分(組播結點樹核的生成及終端結點最終完成加入組播組)來計算，綜述如下：
其組播組結點樹核生成時，首先要以組播功能結點間的最短路生成其全連通網絡。采用Dijkstra算法，各組播結點及源結點s間彼此最短路尋徑，設其MV結點數為m，網絡規模即網絡中總的結點數為n，則組播功能結點全連通網絡生成在最壞情況下時間復雜度為。而樹核生成的遺傳算法和seqToTree算法的時間復雜度為O(P×maxG×O(mlogm))。同樣每一終端結點加入組播組時每一結點最壞情況下要調用Dijkstra算法三次，分別對源結點s及樹核內距終端結點Di最近的MV結點和具有P(Di,MVi,s)min的MV結點尋最短路，最壞情況下，每一終端結點最終加入組播組的時間復雜度為。PRRH-N算法的每一結點退出操作的最差情況的時間復雜度為，t為組播樹中所含的結點數，而因此選擇重新選路的各終端結點需再次調用Dijkstra算法三次，如這部分結點數為r,則最壞情況下，這部分終端結點最終加入組播組的時間復雜度為。
由于兩種算法都采用了分布式觸發的思想，無需覆蓋層對整體的費用做出監控及評價，故而從基礎解決了原觸發重組費用優化方案的缺點，減輕了路由優化的復雜性和額外開銷。
目前對于MON網絡動態組播樹的生成算法，還沒有研究人員進行過系統的研究，因此也還沒有基準算法來用于網絡模擬和比較。因此，本文的網絡模擬只能采用課題組MON靜態組播樹生成算法NCH來作為模擬基準。
· 圖4 PRRH-N，PRRH-D算法EAD仿真網絡模擬數據
本文以課題組EAD仿真模型所生成的模擬網絡來做模擬平臺，在EAD算法生成的模擬網絡過程中，其MV結點比例是固定的(17%)，而長短邊之比隨著不同的需求，通過對 及F2的調節，也可以被定位于一很小的領域內，所以在同一網絡規模前提下影響部分組播網絡動態組播樹生成算法的可變因素主要有：1.加入組播組的端結點的更新速度,2.在某一時刻，組播組成員數量在模擬網絡的全部結點中所占的比例，對于這兩點，都可以以一個無量綱的概念，對不同的網絡規模進行一致的模擬，以利于后期實驗結果的比較。
本文采用以下假設：加入組播組的端結點以一種穩定的速度進行更新，即某一時刻有占網絡結點總數5%的組播組成員退出組播組，而另有占網絡結點總數5%的非組播組成員加入組播組，而初始狀態選擇組播組成員占總結點數的20%和40%來進行模擬。這樣就有可能選擇相同的靜態部分組播網絡組播樹生成算法來作為待模擬算法的基準算法，以便能從本質上把握待模擬算法的一些基本特征，并給出其性能評價。
由模擬數據可知(見圖4)，PRRH-N和PRRH-D算法因為可以在結點加入組播組及結點退出組播組時都能觸發樹結構的部分重組。所以其費用能夠被限定在基準以上的一個很小的區域內，因為考慮到現實網絡中的實現問題，兩種算法都沒有終端結點向上歸并的操作，所以，實驗中可見費用會出現“躍點”，特別是當組播組成員比例相對較小時，這一點表現的尤為突出。在組播組成員比例進一步增加時，兩種算法都表現出很好的收斂性，而且其費用的統計平均值也均被限定在不高于基準的10%，這一結果還是非常令人鼓舞的。
7 結束語
PRRH-N算法在費用優化方面是兩種算法中最優的，基于結點費用最優觸發重組操作，能最大限度的減小算法的散列躍度，算法收斂性能夠有一個很好保證，但時間復雜度整體來說過大，在實際應用中，可操作性要明顯低于PRRH-D算法。但在組播組成員相對較少時，對費用優化苛刻的前提下，該算法還是應該成為首選的。
PRRH-D算法在時間復雜度方面較PRRH-N算法為優，而其網絡費用優化又明顯的線性逼近
PRRH-N算法，在組播組成員比例達到40%左右時，該算法的費用優化性能已近似等于PRRH-N算法，
故在對算法計算時間及費用優化都有較高要求時，還是選用PRRH-D算法為好。
因兩種算法都是基于“樹核”的，所以兩種算法都可以在一定路由協議的支持下進行多面體分級路由模式的改良，也可以方便的向多點對多點組播路由算法改進，這樣就能夠使算法在可擴展性方面有一個質的提高，同時也可以使其向多點對多點路由計算提供良好的支持。其次，基于“樹核”的路由方式，也可以在鏈路負載平衡方面較原有的CBT算法(原針對全組播網絡的一種多對多組播路由算法)有一個質的提高。以上方案都將是今后對于部分組播網絡路由算法研究的很好的方向。
參考文獻
[1] 董慶陽, 計算機通信網絡組播路由算法和協議的研究, 上海交通大學博士學位論文, 2000年
[2] 王征應, 高速網絡QOS路由技術的研究及路由仿真平臺的研制, 華中科技大學博士學位論文, 2001年
[3] 李漢兵, 計算機網絡路由算法, 西安電子科技大學博士學位論文, 2000年
[4] Yunxi Sherlia Shi . Design of Overlay Networks for Internet Multicast.(PhD thesis ).[D]. Washington University. August, 2002
[5] G.N.Rouskas and I.Baldine. Multicast Rjouting with End-to-End Delay and Delay Variation Constraints. IEEE Journal on selected Areas in Communications, 1997, Vol.15:346-356
[6] Ghosh, M. Fry, and J. Crowcroft. An architecture for application layer routing.[C]. In 2nd Int. Working Conf. on Active
Distributed Dynamic Routing on the Multicast Overlay Network
YU Zhenwei, LIU Kejian
China University of Mining and Technology-Beijing, Beijing, 100083
zwyu@cumtb.edu.cn
Abstract ： This text gives a definition for the dynamic routing in MON the Multicast Overlay Network, and put forward the problems of the dynamic route computing should be considerated for the first time, and a Arithmetic PRRH-N & PRRH-D according to the distributing triggers the reorganization , in the end ,the report calculate the complexity of the Arithmetic , simulate the PRRH-N on the model of EAD .
Key words: overlay ; multicast ; dynamic routing ; distributed triggers the reorganization
劉克儉 余鎮危 竇巍
（中國礦業大學研究生院，北京，100083）
摘要：本文在分析研究主動應用的基礎上，針對應用層主動網絡節點對費用的影響，提出了一個新的費用模型，并基于此模型設計了一個靈活的主動路由算法。實驗證明此算法具有高效性和可擴展性，在大規模網絡環境下也表現出很高的可用性。
關鍵詞：應用層主動網絡，移動代理，服務位置，主動路由算法
中圖分類號：TP393 文獻標識碼：A
引言
當前為了解決傳統計算機網絡體系結構面臨的困難，研究界提出了應用層主動網絡的思想[2][6]。應用層主動網絡就是在現有的網絡基礎之上建立一個虛擬網絡用來支持原有網絡沒有提供的分組處理功能。它的主要優點是不需要整個網絡范圍內的網絡組件的支持，加快了所需網絡功能和服務的部署，并且由于支持不同的服務功能的多個應用層主動網絡可以共存，也增加了其靈活性。由此，應用層主動網絡的提出迅速成為主動網絡研究的分支。
為了在應用層主動網絡上支持用戶的對多樣服務的需求，需要在應用層主動網絡上選擇合理的位置注入特定的服務（如壓縮、處理、緩存、重新編碼等）來為用戶服務[1]，我們稱之為proxy[6]。如何優化服務位置是本文考慮的主要問題。首先給出了適合應用層主動網絡的費用模型；其次提出并抽象應用層主動網絡中的服務位置問題；最后給出算法解決該問題并對算法的特性進行了驗證。
2 應用層主動網絡上的費用模型
2.1傳統網絡費用模型的不適應
目前的Internet形成了基本的費用模型，包括接納控制、路由和資源預留等方面。總的來看，費用包括節點對負載進行分類交換、排隊和調度的費用，以及傳輸到下一個節點的傳輸費用。當前Internet的實際證明，這一模型是高效和魯棒的，并依賴這一模型設計了許多有效的協議，比如“最短路徑路由”就是基于此費用模型，尋找在源與目的之間的一條路由，使得每跳的費用之和最小。
但是，以上所有協議的設計都是只限于被動網絡。在帶服務的應用層主動網絡中，則不僅僅需要一般的傳輸資源，而且必須滿足中間結點對流的處理。這種情況下，路由的費用包括了結點的處理費用（壓縮、處理、緩存、重新編碼等），而且因為傳輸過程中隨著流的屬性的變化（如重新編碼、混合），也在不斷影響后續傳輸的費用，因此在應用層主動網絡中路由成為了一個非常有挑戰性的問題。
2.2 應用層主動網絡應用的一個例子
圖 1 主動壓縮費用變化
為了避免擁塞控制，比如可以利用proxy進行數據的壓縮，節省proxy到用戶的帶寬。proxy與server之間的流速率將大于proxy與client之間的數據流 ，用ri表示這個變化的比率。在該例子中，費用模型需要考慮壓縮代價和由于壓縮考慮流量的變化。
如下所示分別標注了鏈路費用和節點費用。在節點注入主動壓縮proxy之后增加了節點處理費用，并對后續的費用（節點和邊）產生了影響。很明顯，傳統的最短路徑算法（如Dijkstra算法）應用于以上模型是無效的，無法計算出的最優費用的路徑，如下例子可以說明。假設主動節點c、d壓縮率0.5。
圖2 傳統的路由算法的不適應性
結果，Dijkstra算法由于不計節點費用，求出路徑（a-b-d-g）費用為50（20+10+20）；在各節點分別注入proxy，考慮主動節點的壓縮率和費用，計算出最短路徑（a-c-d-g）費用為25.25（20*0.5+3+13*0.5+2+8.5*0.5），優于Dijkstra算法。當然，某些主動服務有可能使費用增加，而不是減少，比如主動加密，但由于中間節點產生費用導致總體費用的變化，所以仍然不能使用傳統的路由算法。
因此，得出結論，采用常規的最短路徑算法在某些主動應用場合失效（不是所有場合），需要尋找最優的路由算法。
2.3 應用層主動網絡的費用模型
主動服務節點的處理代價 
，對經歷該主動節點的流的影響比率為
，流經過的鏈路帶寬代價為
。
主動網絡 
（1）
被動網絡 
（2）
設共有n節點，節點k為要研究的對象，引入主動計算，因此主動網絡總費用為：
=
= 
=
（3）
引入proxy之后，主動流經過k節點發生改變，因此k之后的費用也發生變化，因此對后續節點費用也產生影響，我們用 
表示這種變化。
（4）
3 服務位置問題
首先把問題抽象，網絡模型可表示為帶權圖 
，
是主動節點的集合，
是邊（表示節點之間的連接）的集合，
為提供裝載proxy服務的中間處理節點的集合（節點或者子網），每一條邊
的費用為
；主動節點
的節點處理費用為 
。有一個源節點s，一個目的節點d，中間至少包括一個主動節點r裝入proxy。我們的目標是找到從s到d最小費用的邏輯路徑，以及裝載proxy的位置r。這條邏輯路徑的費用包括鏈路費用總和、路徑中proxy主動節點的費用。
目的是求上述條件下的路由算法，計算出在哪些位置注入proxy或注入多少個proxy組成的路徑的費用是最優的。如果 
表示節點i對流的影響，Ai表示流速率（單位帶寬），即有：
f為最小的費用函數，Ci表示節點執行主動計算的費用，在每一次使用主動計算與是否執行主動計算相關，并且對后續流量是有影響的，根據流量變化不斷乘上變化因子 
.。
4 算法描述
假設事先獲得了邏輯域內網絡的拓撲（類似于OSPF鏈路狀態協議），首先我們說明了如何解決一個proxy的位置問題，其次擴展到多個proxy的情形。
4.1網絡中唯一proxy的路由
先看簡單的情形，假設在網絡中只有一個proxy，尋找注入這個proxy的位置，其余中間節點則仍是被動的。首先，復制一份原始拓撲圖，形成兩層，如圖3所示。對于每個節點 
，都有可能裝入proxy，因此，在兩層中增加了若干有向邊(r0,r1)，令這些邊的費用等于節點r的費用C(r)。構成的新圖中的源點為s，目的點則不再是d，而是1層的d1點。
主動路徑的問題即可轉化為：求0層的s到的1層的d1的一條不計節點費用的最短路徑。所以可以使用一般的最短路徑算法，計算好的這條路徑跨越兩層，合并之后即是原圖的最小費用的路徑。
圖3 單個proxy的主動路由方法
容易證明這一方法的正確性。我們求得從s到d1的最小費用路徑 
, 在原圖有一條路徑相對應，且費用相同。假設原圖另有一條費用更低的路徑，那么在展開圖也有一條與之對應的s到d1的路徑
，這條路徑費用則比我們求得的費用要低，因此矛盾。得證。
上一節公式（4）說明，主動節點處理后的主動流會引起后續路由的費用的變化，因此需要考慮帶寬變化因子
的影響。設0層到1層的帶寬變化率為
，解決辦法是，把0層到1層的費用乘上
，再利用最短路徑算法求得。
路徑確定之后，proxy的位置也就相應確定下來，路徑中跨越0層到1層的那個節點就是注入proxy的最合理的位置。
4.2 多proxy的路由和位置
（1） 網絡中只有1個proxy的算法可以擴展到多個proxy節點。 有n個可選的主動節點，則最多需擴展到n+1層。因此，如果在網絡中裝入k個proxy（ 
），則復制后需排列為k+1層，類似于4.1問題轉化常規最短路徑問題，即求s到dk+1的邊的費用最低的路徑。
而且，仍然要考慮帶寬變化的影響。對于第i層的邊，邊的費用要乘上
；從第i層到i+1層的邊的費用乘上
。
（2）全局最短路徑
求原圖的任意數量的proxy構成的最短路徑，實際上就是從1個proxy到n個proxy的情況都考慮一遍。在4.1的基礎上，我們可以得出
Pathmin = Min(Min(s,d),Min(s,d1)), … Min(s,dn＋1))最短路徑即在所有0至n個proxy情況下求得的最短路徑中取最小值。
圖4 多個proxy的主動路由方法
（3）算法復雜性分析
網絡具有k個proxy，則分層圖包含 
個節點，和
條邊，求最短路徑的時間復雜度為
。顯然，這種方法空間復雜度是隨著proxy數量的增加而線性增長的。
5 實驗驗證與結論
本論文在Intel Celeron 1.4GHZ ，256MRAM的微機上利用Sun Java（J2SDK1.4）語言編寫了上述算法程序。為了驗證仿真結果，網絡的拓撲圖生成使用了BRITE工具[3]，使用隨機化的方法產生具有實際網絡特性的圖的模型，實驗網絡的拓撲生成基于Waxman[4]的拓撲生成模型：
在我們的實驗和算法實施中，網絡有如下屬性：①邊的費用在[10,200]范圍上均勻分布。②中間處理節點的費用在[1,10 ]上均勻分布。③如果不特殊說明，則平均每個節點連接邊數m=5，α=0.15，β=0.2。
5.1 算法正確性的實驗驗證
圖5 一個簡單的主動路由算法的例子
根據圖5所示簡單網絡（節點費用為a0=1，b0=2，c0=1，d0=2，e0=1；λ=0.5），通過模擬程序求Dijkstra算法與主動路由算法結果如表1所示：
表1 λ=0.5，初始節點a0，終點e0的最短路徑
|
Active算法 |
Proxy數量 |
0 |
1 |
2 |
3 |
|
費用 |
20.0 |
11.0 |
9.5 |
10.5 |
|
Dijkstra算法費用 |
20.0 |
DijkStra算法求得最短路徑為（a－d－e），費用為20.0。而主動算法求得最小費用9.5，2個Proxy，這個2個Proxy位置分別為a和b，即最短主動路徑為（a－b－e），其中主動算法0個Proxy情況相當于Dijkstra算法的結論。
上述兩種算法計算的最短路徑結論是不同的。首先說明了在節點增加了主動計算費用之后，傳統路由算法不適合主動網絡。其次說明本文的主動路由算法的可以得出正確的結論，并可求出Proxy所在路徑上的位置。此實驗只是在一個給定的較小網絡拓撲中的實驗，目的是說明算法的正確性。
5.2 大規模網絡下算法特性的模擬實驗
（1）隨機拓撲節點總量變化的影響。實驗統計了不同節點大規模節點總數的拓撲情況，從大量的實驗數據中發現主動路徑上的Proxy數量集中在一定范圍內。以所有節點作為起始點計算Proxy個數對應的最短主動路徑數量分布，并取均值（取整數），得出可信的分布結果。如圖6所示：
圖6 大規模網絡下主動路徑數量分布
從圖中看出：實際網絡拓撲中，在最短主動路徑上部署的Proxy數量的分布集中在一個范圍內。當流量變化率λ=0.5時，這個范圍基本上在1至5個Proxy（包含起始節點本身）。這為我們大規模應用這個算法提供了依據。在主動壓縮或主動緩存的應用中，依據主動應用的特點實際也不可能部署太多的Proxy，實驗恰恰說明了網絡中絕大多數節點使用較少的Proxy就可以達到主動最短路徑的要求。
（2）流量變化率λ對主動路由算法的影響
上述是對固定的流量變化率λ=0.5進行的實驗；還需要考慮在不同λ值的條件下（λ<1和λ>1）的變化。λ表示執行主動計算之后流量的變化率，λ<1表示主動計算使得流量的后續路徑費用減少，帶來減少帶寬的好處；但是，某些主動應用利用主動計算改變流特性，不一定會有減少帶寬的好處（如重新編碼），所以用λ>1表示主動計算使流量的后續路徑費用增大。當λ逐漸變大時，意味著主動計算的執行使流向著增加帶寬費用的方向變化，λ>1變化對算法的效率和主動路徑數量分布產生如圖7所示的影響（節點總量為500）。
圖7 不同λ條件下（λ<1）的主動路徑數量分布
分析實驗結果，當主動計算對流的改變程度變小時，即隨著λ增加，不用Proxy的路徑越來越多，使用Proxy的主動路徑的數量呈下降趨勢。從而得出結論，在λ<1時，λ越小則利用主動計算的價值就越大，反之則多數情況不必利用主動計算。所以，通過實驗進一步驗證了本文費用模型合理性。當λ等于1.0時是極限狀態，幾乎沒有路徑使用Proxy，主動路徑數量的分布曲線成為一條逼近于0的直線。總之，當λ<1，λ越小則越適合（快速和普遍）用主動算法求解最短主動路徑和Proxy的位置。
其次，當λ>1時，主動路由算法仍然是正確的。實驗表明隨著λ>1不斷增加，主動路徑分布出現不均勻的現象，各說明最短路徑使用Proxy數量的差異比較大。并且，當λ>2.0之后的最短路徑數量分布隨著λ的變化是微小的，而且越來越逼近一個極值狀態。
（3）算法的執行效率
主動算法的執行時間主要考慮兩個方面：第一是計算層數k（即算法所限定的Proxy個數）對算法時間的影響是線性的，算法時間主要消耗在數據結構的建立和復制上；第二是不同變化率λ的算法時間比較，當拓撲總量為500，計算層數k=15不變的條件下，λ對算法所耗時間的影響如圖8所示。
圖8 算法時間隨λ的變化
最后，本文還對Waxman模型中的連接邊數、以及α和β參數值的變化進行了實驗。發現，連接邊數m對主動路徑數量分布有較大影響，而α和β值對主動路徑數量分布的影響不敏感。
6. 結束語
主動網絡的費用模型不同于傳統網絡，沿用傳統的費用模型和路由算法將導致不正確的結
論。本文提出一種新的主動網絡費用模型考慮了數據流在主動節點環境中的執行費用，并在此基礎上研究一種合理的主動路由算法，通過大量的模擬驗證，說明算法各個方面的特性，得出一些非常有價值的結論。
最后，需要說明的是本文只針對單服務主動路由算法進行了研究，而在組播條件下和多服務約束條件下需要研究新的算法，比如利用遺傳算法和啟發式算法等。
參考文獻：
1 Elan Amir. Steven McCanne, and Randy Katz, An Active Service Framework and it’s Application to Real-time Multimedia Transcoding.[C]. Proceedings of ACM SIGCOMM’98，Vancouver， BC,Canada，Sep 1998.
2 A. Ghosh, M. Fry, and J. Crowcroft. An architecture for application layer routing.[C]. In 2nd Int. Working Conf. on Active Networks (IWAN2000), October 2000.
3 Alberto Medina, Anukool Lakhina, Ibrahim Matta, John Byers. BRITE: An Approach to Universal Topology Generation. in Proceedings of MASCOTS 01, August 2001.
4 B.Waxman.”Routing of Multipoint Connections”.IEEE J.on Selected Areas in Comm.,6:1617-1622,December 1988.
5 Sumi Y. Choi, Jonathan Turner, and Tilman Wolf, Configuring session in programmable networks. Proceedings of IEEE Infocom 2001,Apr. 2001.
6 竇巍,余鎮危,潘耘.基于移動agent的應用層主動網絡.第六屆全國計算機應用聯合學術會議.2002.10
Service Placing Problem on Application Layer Active Network
LIU Ke-Jian YU Zhen-Wei
(Graduate Student College of China University of Mining and Technology,Beijing,100083,China)
Abstract By the studying of classical Active Applications (AA), we proposed a novel open Mobile Agent-based Application Layer Active Network。 Proxy server allow to deliver service tasks to any place in the network. We presented a new cost modal and it’s routing algorithm to solve the problem of proxy placement.
Key words ：ALAN，active network，mobile agent，proxy placing，active routing algorithm
LIU Ke-jian YU Zhen-wei
(Graduate College of China University of Mining and Technology, Beijing, 100083, China)
Abstract: The model for stochastic network simulation of exact average degree (EAD) is proposed in this paper, including the following contents: regional distribution of stochastic nodes, selection of core nodes and overlay functional nodes, deduction of new probability connectivity formula, classifying and restricting strategy of increasing degree, fast connectivity strategy of stochastic network, etc. In addition, this paper also makes further explanation, deduction and simulation for the unplugging performance of random network model.
Key words: model for stochastic network simulation, exact average degree, overlay nodes
0 Introduction
The research on routing issue cannot do without simulation and testing. It is impossible to carry out routing test in the real network for most researchers at present, while a routing test carried out in a specific network will restrict the test result to the specific experimental network unavoidably. A routing protocol or algorithm performing well in a specific network cannot always demonstrate equally good performance once there is a great change in the network topology or when it is transplanted to another different network. Therefore, tests of performance of routing protocols or algorithms have to be based on stochastic network. First of all, the model for stochastic network simulation must give prominence to randomicity, that is, stochastic network generated by the same algorithm should not be the same every time from node distribution to connection so as to guarantee the randomicity of routing tests and the corresponding results carried out in stochastic network, as well as the reliability of simulation results. Second, the main features of the model for stochastic network simulation should be consistent with those of real network in order to guarantee the reliability of routing tests. If the main features of the generated model for stochastic network simulation differ much from those of real network, the performance of the algorithm in real network would be on suspicion. As a result, a superior model for stochastic network simulation is not only the presupposition and foundation of a simulation test of routing algorithm, but also the primary assurance of verification of successful design accurately.
1 Meaning of Research on EAD Simulation Model
In previous documents, Waxman proposed two kinds of models generated by stochastic networks: RGl and RG2. The network nodes generated by RGl randomly distributed in rectangular grids, the coordinates of nodes are stochastic integers in consistent distribution, and the distance between every two nodes is a Euclid length. As is different from model RGl, for the network nodes generated by RG2, the distance between every two nodes is a random value between (0, L) in consistent distribution. In both models, there is a certain probability determining whether to connect the two nodes. The probability is determined by distance between the two nodes. The probability of connecting nodes u and v is determined by formula (2-1):
(2-1)
A random value Rd in uniform distribution is generated between 0 and RMAX, and if:
(2-2)
Then the connection exists between nodes u and v, otherwise the connection does not exist.
In formula (2-1), d (u, v) is the distance between nodes u and v, L is the longest distance between nodes, and parameters 
and 
control the features of network graph generated, the values of which are in (0，1). The bigger 
is, the bigger the average degree; and the bigger 
is, the bigger the ratio of long side to short side. After simulation of its performance, we can find out many defects, such as: as for networks with the same scale, 
and 
, the average degrees would always differ much. And if the network scale changes, the average degree would not have a bit consistency. Consequently, some distinct improved modes were brought out on basis of RG1 model in order to improve such defects, such as:
Exponential Model: relate the distance between nodes to probability p (u, v), and then the probability of total sides generated would present a downward trend of exponential as the distance between nodes increases. The probability formula is as following:
(2-3)
Doar-leslie Model: factor 
(where 
is estimated average degree, n is number of nodes in the network, and k is a constant) is used to adjust probability p (u, v) to control the number of sides generated in the network. The probability formula is as following:
(2-4)
Further research discovered that the convergence of average degree in these models above were still not satisfying. There still are differences between the situation of real network and the ratio of long side to short side as well as the probability of connection of over-lengthy sides. The high connection rate of core nodes and the defect of impact on network routing of special node clusters (such as overlay functional nodes) in the network are neglected. So it becomes a hot issue how to generate a model of network simulation more consistent to the real network in order to support more complicated routing strategies (such as active overlay network routing or partial multicast network).
2 EAD Model for Stochastic Network Simulation
The computer network can be abstracted as the graph in graph theory. As for graph G=(V, E, C), V represents the set of nodes in G, E represents the set of oriented sides in G, and C represents the set of weights corresponding to oriented sides. The weight of side is also called the cost of side. Every side corresponds to two nodes u, v 
V. Every two nodes correspond to two sides (u, v) and (v, u). If the costs of these two sides are equal, the graph G is called symmetric graph, and if the costs of these two sides are not equal, the graph G is called asymmetric graph, i.e. oriented graph. In this thesis, V represents the set of routers in the network, E represents the set of all links, and C represents the set of bandwidth, delay, data loss rate or their assemblies. The research of algorithm to generate model for network simulation is based on unoriented graphs to map to real network, namely full symmetric network. The research of this thesis is also based on such prerequisite.
2.1 Generation of EAD Stochastic Nodes
The nodes in stochastic network mentioned above are all scattered in a fixed plane according to probability of uniform distribution. What is worth of attention is that, the nodes in real network is not distributed uniformly, but often incline to partial center-focused distribution. For example, in domestic network, the distribution density of network nodes in the east inshore area with dense population and more developed economy is generally heavier than that of west area with sparse population and less developed economy. In overseas network, this trend is more obvious. The distribution density of network nodes in developed countries is heavier than that of developing countries. In addition, there is hardly a network node in oceans covering more than 75% of the surface of the Earth. In order to eliminate this difference, EAD makes improvement to distribution of network nodes as following:
Divide network plane into several sub-areas, and mark these sub-areas as dense areas (D areas), sparse areas (S areas) and 0 distributing areas (Z areas) separately according to actual requests (or at random). When generating network, nodes can be generated separately with different density for each area.
In real network, connectivity of most nodes is from 3 to 4, and only the connectivity of a few nodes at network center (3% up to 2000) could exceed 20. These core nodes (expressed with set O) include ISP suppliers, large-scale research institutions, industrial network centers, telecommunication providers and so on. Previous simulation models did not consider connectivity of core nodes. Therefore the guard conditions of all nodes are the same without distinguishing between the primary and the secondary. There is very great disparity with real network, so it will unavoidably bring uncertain factors to the network simulation of some algorithms.
Furthermore, previous models for stochastic network simulation did not involve the concept of special node cluster in network (such as overlay functional nodes, multicast functional nodes, etc.), neither. But these nodes may be supporting a certain service of the whole network. For example, there are nearly 20% of the nodes in real network bearing multicast function (17% in 2000). These nodes are able to execute multicast throughout the network. How to generate partial nodes as simulation network of multicast nodes, and how to offer the possibility of simulation verification for partial multicast routing algorithm, become a very realistic problem.
In EAD, randomly select from the nodes generated in dense area (D area) of simulation network generated according to areas, 
nodes (
is the scale of simulation network, i.e. total of network nodes, taking partial multicast network as an example) as core nodes and multicast nodes, and select from the rest nodes 14% as multicast nodes.
2.2 Generation of EAD Stochastic Linkage
According to the above explanation, if 
and
do not change, the average degree will increase with network scale n increases. In order to decrease such impacts, formula (2-1) has to be modified. As we have already known, as for 0
that is when p is in direct proportion to ( 
)
, the limits of maximum degree and minimum degree of stochastic network are determined. Therefore the average degree of network will not increase unlimitedly. According to this definition, we get the following formula through comparison of repeated convergence and experimental verification:
(2-5)
We can see from formula (2-5) that connection probability P (u, v) approaches to 0 as network scale n increases. In this way, the average degree of network adopting formula (2-5) as connection probability formula will not increase with the increase of network scale n. Our experiments also discover that when F1=16, F2=2.8, the average degree will have a very good convergence. If F1 increases, network connectivity will increase; if F2 decreases, the scale of long side will decrease further. EAD applies this connection probability formula to connection of non-core nodes. That is, when u, v 
; u, v
, the available connection formula of two nodes is (2-5). Certainly, this also brings some problems. Since formula (2-5) will increase with the increase of network scale n, the scale of long side will tend to decrease. In fact, the result will come out that all nodes tend to connect to adjacent nodes, while in a real network, the long distance connection between core nodes and some special nodes among regions and countries cannot be embodied. In such cases, if there is core node between two nodes, then EAD adopts the following formula:
(2-6)
to make a supplementary restriction for network connection probability formula.
In order to make average degree of network more exact, EAD makes further restraint to the generation of stochastic network: when there isn’t core nodes between two connected nodes, adopt connection probability formula (2-5), at the same time make restraint to connection node degree: that is, if node degree of any one nodes of the two exceed 
+1, then the other nodes do not connect to it, where 
is expected average degree. However, if one of the two nodes is the core node, then adopt connection probability formula (2-6), where the upper limit of core node is 12;25 (when n>64), that is when node degree of the core node is bigger than 12;25 (when n>64), then EAD will not permit other nodes to connect to it.
In course of connection, in order to maintain the probability of participating in connection for every node in consistence, we adopt the algorithm of connecting out-nodes in order, while selecting randomly in-nodes that are not marked (nodes with such marks will not participate in computation). Select in-nodes for current computation of connection probability, and reject the second connection when the same two nodes generate the second connection. In course of computation of connection probability, when node degree of an out-node equals to 
+1 (non-core node) or 12;25 (core node and n>64), drop the connection computation of this node, mark it (as not to participate in computation), and select the next node orderly as the out-node to continue connection computation. If the in-node has already satisfied the condition of dropping connection, reject computation of connection probability of this node to out-node, mark it (as not to participate in computation), and select the next node orderly to continue computation of connection probability.
Experiments show that EAD model for stochastic network generation accord with existing real network both in average degree and in the ratio of long side to short side better than previous model for stochastic network.
2.3 Fast Connection Strategy of EAD
In course of generating connection, since the existence of every connection is independent to one another, therefore the resulting stochastic network may not in connectivity after the generation of connections. The practice of previous simulation models is: to make connectivity test for the resulting network after generation of stochastic connections of nodes. If it is not a connected network, then reject it and re-generate stochastic connections. Make repeatable tests until we get a connected stochastic network.
Experiments show that we have to attempt many times to generate a connected stochastic network when there are many network nodes. There is nearly an exponential grade relationship between the average attempt times and connection rate (the rate of total connected nodes to total nodes). For example, if 200 nodes are connected completely and stochastically, the requisite average attempt times would be more than 5000, but if only 95% of nodes need to be connected, the requisite average attempt times would be no more than 20. This is of much importance for connected stochastic network with more nodes generated. When there are more nodes, EAD will first apply the generation method of simulation model above to get a quasi-connection network with more than 95% nodes connected, then link the unconnected nodes or subnets to the connected network through the fastest path. So EAD can get a completely connected stochastic network in a shorter period.
3 Compare Performance of EAD with Previous Models
When compare our model with previous models, we set out from this principle: under the limit of equal average degree, priorly select parameter values more close to actual network characteristics, that is to regard characteristics most close to the real network as precondition to adjust according to the different adjusting function to connection probability formula of 
and 
. Refer to Graph 3-1 and 3-2 for the comparison of average degrees of RG1 and EAD:
Graph 3-1: Comparison of RG1 and EAD Average Degree
Where: F1=16, F2=2.8, L=100 
raph 3-2: Comparison of Various Models
According to the comparison of characteristics of node degrees of models above, we can find out that EAD is obviously better than RG1 in the aspect of average degree. When network scale rises to 1024, RG1 average degree has already arrived at 89.17. In fact, since such stochastic network generated shows much difference to real network, so there is no realistic meaning of it. However, when we control 
=0.01 or so, for the stochastic network R generated by G1, although the average degree can still bear preferable convergence if network scale is larger than 512, it does not accord with real network seriously due to over-high loss rate of long side. In fact, this network does not bear much realistic meaning. As for the characteristics of average degree, RG1 and exponential model are fundamentally the same: when network scale increases continuously, the algorithms present strong ascending tendency of average degree with very bad convergence. Although exponential model is better, it cannot adjust 
, while 
is responsible for control the ratio of long side to short side, so there is great gap between the resulting simulation network and real network.
As can be seen from those graphs, after EAD algorithm applies restraint in node degree, its convergence becomes excellent, and the average degree is always limited within a very small range, at the same time network scale expends with multiples. Because when the distance between two nodes increases, EDA algorithm will apply formula
to calculate the connection probability. Actually connection probability will decrease with exponent as network scale increases, however, many long sides connected to core nodes in real network will be lost while EDA algorithm guarantee the average degree. As a result, EAD algorithm also takes into account long-distance connection of core nodes to other nodes while it adjusts the ratio of long side to short side through 
and 
. By adopting formula
, calculate connection probability between a core node and another node, EAD algorithm prompts to compensate the lost long side while guarantee connection of high node degree in core nodes 12;25 (n>64), so that the generated simulation network is more close to real network than before.
EAD algorithm greatly improves previous algorithm. No matter in the aspect of core node and its behaviors of high connection node degree, or in the aspect of embodiment of multicast node in the network, or in the aspect of convergence of average degree that we have been caring in the past, EAD algorithm is more close to our real network. EAD algorithm provides a good experimental platform for network simulation of partial multicast network routing algorithm in the latter part of the text.
4 Conclusion
This thesis researches the impacts on simulation network of core nodes, node clusters of special functions, convergence of average degree and ratio of long side to short side, and brings forward a method to generate simulation network from a new aspect. The simulation network generated by EAD algorithm is more close to real network, and provide an excellent experimental platform for network simulation of algorithm, especially simulation of special network (such as active overlay network or partial multicast network). As for further research, if we randomly assign a value from 0 to MAX while EAD generates real connection between two nodes, then we can simulate to generate an asymmetric network. And if we execute multi-target restraints to special functional nodes in the algorithm, we can provide support to a good many hotspot simulation of overlay network.
There still are a lot of work to done about the algorithm research of stochastic network model. Aiming at different demands (such as new-type polyhedron layered routing strategy), we can make necessary alteration to EAD, however, as for exact average degree, it has already laid a good foundation for further research in the future.
References:
1. Dong Qingyang, Research on Computer Communication Network Multicast Routing Algorithm and Protocol, Doctoral academic dissertation, Shanghai Jiaotong University, 2000
2. Wang Zhengying, Research on High-speed Network QOS Routing Technology and Development of Routing Simulation Platform, Doctoral academic dissertation, Huazhong University of Science and Technology, 2001
3. Li Hanbing, Computer Network Routing Algorithm, Doctoral academic dissertation, Xidian University, 2000
4. Wang Xingren, Development of System Simulation Technology in the 21st Century, Journal of System Simulation, Issue 2, Vol. 11, 1999
5. Jochen Behrens, “Distributed Routing for Very Large Networks Based on Link Vectors”, June 1997,Ph.D thesis, Computer Science College, University of California, Santa Cruz
6. M. B. Doar. A Better Model for Generating Test Networks. In Proceedings of Globecom ’96. Global Internet ’96, 1996.
7. Sandeep Bajaj, Lee Breslau, Deborah Estrin, Kevin Fall, etc. Improving Simulation for Network Research, Technical Report 99-702, University of Southern California, March, 1999
8. Miguel Angel Olabe, Juan Carlos Olabe, Telecommunication Network Design Using Modeling and Simulation, IEEE Transaction on education, vol. 41, No. 1, February 1998.
Project supported by foundation: this work was supported by a national grant from Ph.D. Programs Foundation of China (20030290003) and Project for the Open Research Foundation of the State Key Laboratory of Novel Software Technology at Nanjing University (2002-2003)
Authors brief introduction: Mr. Liu Ke-Jian (1969－), Ph.D. student, Graduate College of China University of Mining and Technology, Beijing, mainly engaged in active overlay network key technology, new network architecture, and partial multicast network routing technology. E＿mail: lkj_s116@263.net
余鎮危,教授,博士生導師,中國礦業大學(北京)。1942年1月生于上海, 1966畢業于中國科學技術大學。畢業后在沈陽計算機技術研究設計院工作，曾任研究室主任，副總工程師,研究所所長等職。1993年1月至1996年3月應邀到美國Auburn大學計算機科學與工程系進行高速計算機網絡合作研究，1996年4月應聘到中國礦業大學（北京）從事教學和科研工作，曾任機電與信息工程學院副院長，兼任國家教育部自學考試中心計算機網絡專業專家組成員，國家煤炭工業信息與自動化專業委員會專家，高新技術信息與通信領域技術預測咨詢專家，北京信息領域咨詢專家。曾擔任國際計算機及應用學會（ISCA）計算機網絡學術會議主席。長年從事計算機網絡，計算機體系結構和計算機應用研究工作, 先后承擔國家，省部級及橫向科研項目40多項，包括主動Overlay網絡體系結構及關鍵技術的研究，應用層與網絡層協同路由的研究，計算機網絡體系結構形式化理論的研究，基于移動Agent應用層主動網絡服務部署的研究，基于復雜性理論計算機網絡行為的研究，以及FDDI實時信令系統，基于相聯存儲器的ATM交換機，大氣環境自動監測系統，環境噪聲自動監測系統，海軍基地專用信息處理系統等，其中獲部省級科學技術進步獎6項，國家優秀新產品獎4項。在國內外發表專著2本，論文80多篇。曾赴美國，日本，瑞典，前蘇聯，新加坡,加拿大參加國際學術會議。多年來榮獲“全國勞動模范”，全國“五一勞動獎章”，遼寧“五一勞動獎章”，遼寧省勞動模范，沈陽市特等勞動模范稱號，被電子部授予部級“有突出貢獻專家”，遼寧省授予省級“有突出貢獻專家”，沈陽市授予市級“有突出貢獻專家”，于1990 年被收入“中國人物年鑒”，享受“政府特殊津貼”。在校講授“計算機網絡體系結構”，“計算機網絡研究前沿”，“高速計算機網絡”，“計算機體系結構”，“計算機組成”，“計算機網絡”，“計算機原理”等課程。目前的研究領域包括下一代計算機網絡體系結構和協議，高速計算機網絡，復雜性理論在計算機網絡領域的應用，計算機網絡應用和計算機應用技術等。在人才培養方面注重能力，方法和素質的培養，努力在科技前沿進行探索，指導博士后，博士生和碩士生90多名，畢業50多名。