在線論文： 1. 組播OVERLAY網(wǎng)絡(luò)分布式動態(tài)路由的研究1 2. 應(yīng)用層主動網(wǎng)絡(luò)中服務(wù)位置與路由算法的研究 3. Study on Exact Average Degree Model for Stochastic Network Simulation

余鎮(zhèn)危, 劉克儉　  中國礦業(yè)大學(xué)(北京)，北京，100083 zwyu@cumtb.edu.cn    摘要：本文給出了組播覆蓋網(wǎng)絡(luò)MON動態(tài)路由的定義，并在此基礎(chǔ)上提出了MON動態(tài)組播路由計算所應(yīng)考慮的問題，給出了基于分布式觸發(fā)重組的MON動態(tài)組播路由算法NPPR-N和NPPR-D，并在本文的最后對算法的復(fù)雜度進(jìn)行了推證，對算法的有效性進(jìn)行了以EAD模型為基礎(chǔ)平臺的網(wǎng)絡(luò)模擬。 關(guān)鍵詞：OVERLAY；組播；動態(tài)路由；分布式觸發(fā)重組 1　引言 現(xiàn)實的網(wǎng)絡(luò)環(huán)境，還不具備為實現(xiàn)某一種應(yīng)用而全部改造或重新定制現(xiàn)有路由器或交換機的可能，如何利用已改造的有限的功能節(jié)點來完成與其新型應(yīng)用需求線性逼近的網(wǎng)絡(luò)性能，這就是OVERLAY網(wǎng)絡(luò)目前所熱衷研究的問題。就組播問題來說，所有節(jié)點都具有組播功能的網(wǎng)絡(luò)稱為全組播網(wǎng)絡(luò)，這是為簡化問題的研究，而對網(wǎng)絡(luò)參數(shù)進(jìn)行的極度弱化，過去包括目前所提出的幾乎所有的組播路由算法，雖然解決問題所使用的技術(shù)會有所不同，比如啟發(fā)式，螞蟻或遺傳，但都是針對全組播網(wǎng)絡(luò)而言。顯然這些在全組播網(wǎng)絡(luò)基礎(chǔ)上所提出的算法，距真正的應(yīng)用于實際網(wǎng)絡(luò)，還有很大的距離。                                      2 MON組播樹問題的描述 目前在實際的網(wǎng)絡(luò)環(huán)境中，具有組播功能的結(jié)點的比率還不是很高，大約只有20%左右(2000年為17%)。而如何利用不足五分之一的組播功能節(jié)點來完成組播應(yīng)用的需求呢？這就是我們研究組播OVERLAY網(wǎng)絡(luò)的初衷。網(wǎng)絡(luò)中只有部分節(jié)點具有組播功能的網(wǎng)絡(luò)我們稱其為部分組播網(wǎng)絡(luò)。在部分組播網(wǎng)絡(luò)中，所有的具有組播功能的節(jié)點就構(gòu)成了對整個網(wǎng)絡(luò)的一個組播覆蓋（multicast overlay）,因此對部分組播網(wǎng)絡(luò)組播問題的研究就轉(zhuǎn)化為覆蓋網(wǎng)絡(luò)路由研究的一部分。組播覆蓋網(wǎng)絡(luò)組播樹與全組播網(wǎng)絡(luò)組播樹的不同之處在于，前者會包含很多重復(fù)的鏈路，而后者則沒有。因為組播覆蓋網(wǎng)絡(luò)中，如果從一個節(jié)點到幾個節(jié)點的路徑中有相同的鏈路，而相同鏈路中的節(jié)點如不具有組播功能，則這些相同的鏈路就無法共享。因此在組播覆蓋網(wǎng)絡(luò)中，組播樹的求解問題，就與一般定義的全組播網(wǎng)絡(luò)的組播樹的求解問題有所不同。 本文中有如下定義 定義1.1：在MON組播覆蓋網(wǎng)絡(luò)中，具有組播功能的結(jié)點為MV(multicastable Vertex)節(jié)點，反之，不具有組播功能的結(jié)點稱為NMV(Non-multicastable Vertex)節(jié)點。 定義1-2：組播覆蓋網(wǎng)絡(luò)組播樹：給定一個網(wǎng)絡(luò)有向圖G=(V,M,E,C),V由MV結(jié)點(組播功能結(jié)點)和NMV結(jié)點(非組播功能結(jié)點)組成，MV結(jié)點的集合為M，E為圖中所有邊的集合，C為邊所對應(yīng)的權(quán)值的集合，從V中選擇一組結(jié)點(terminal)D,一個源結(jié)點s D,從G中生成一個樹T=(VT，MT，ET，CT)，使得樹的費用最小，生成的樹就稱為組播樹，其中TG ，VT V，DVT，，MTVT，ETE，T中的源結(jié)點s到每一個D中的結(jié)點都有通路，且s的入度為0，其中非端結(jié)點的NMV結(jié)點入度與出度相等，而非端結(jié)點的MV結(jié)點的出度至少等于其入度。 1基金項目：高等學(xué)校博士學(xué)科點專項科研基金資助課題（20030290003） 定義1-3：最短路徑：結(jié)點u,vV之間的最短路徑是指從u到v的費用最小的路徑，用P(u,v)表示，若沿P(u,v)的結(jié)點有u,v0,v1…vk-1,vk,v,則P(u,v)={u,v0,v1…vk-1,vk,v}。結(jié)點到樹的最短路徑是指結(jié)點到該樹所有結(jié)點中路徑最短的那一條。 定義1-4：組播覆蓋網(wǎng)絡(luò)組播樹費用CT：設(shè)組播樹T中的鏈路有N條，而其中某一非組播鏈路如果出現(xiàn)的次數(shù)為ni次，如圖3-1中邊E(2，4)：則組播樹的總費用可表示成為： CT   3 MON動態(tài)組播樹問題的描述 動態(tài)路由優(yōu)化問題是多點通信所特有的。在點到點通信中，不會有第三方的介入。如果其中有一方想離開，整個通信進(jìn)程也就終止了，因此不存在動態(tài)路由問題。而在多點通信中，參與通信組的成員可以隨時地離開，新的結(jié)點也可以隨時地加入而不影響整個通信進(jìn)程。通信成員的動態(tài)性決定了多點路由的動態(tài)性。當(dāng)然，動態(tài)路由的概念還可以擴展。由于鏈路失敗、局部擁塞、網(wǎng)絡(luò)拓?fù)渥兓�等原因使某些成員脫離了通信組，那么這些成員重新加入到通信組的過程也就相當(dāng)于一個新成員的加入過程。靜態(tài)路由優(yōu)化是在通信開始之前，在一組己知的成員之間，利用某種優(yōu)化算法來尋找路由。而對于動態(tài)路由，由于無法事先預(yù)測哪些成員將會加入或離開通信組。原則上還要求路由調(diào)整時對其它成員不造成影響或影響的程度很小。因此，動態(tài)路由的優(yōu)化問題比靜態(tài)路由的更為復(fù)雜，但其研究成果卻對實際網(wǎng)絡(luò)更具現(xiàn)實意義。 多點動態(tài)路由優(yōu)化同樣可分為網(wǎng)絡(luò)費用優(yōu)化和目的地費用優(yōu)化。由于目的地費用優(yōu)化與目的結(jié)點加入或離開通信組的次序無關(guān)，只與該目的結(jié)點和源有關(guān)，因此動態(tài)路由中目的地費用優(yōu)化問題和靜態(tài)路由中目的地費用優(yōu)化問題是一樣的。本文主要研究動態(tài)路由中網(wǎng)絡(luò)費用優(yōu)化問題。如不作特別說明，動態(tài)路由優(yōu)化專指動態(tài)路由的網(wǎng)絡(luò)費用優(yōu)化。 動態(tài)路由網(wǎng)絡(luò)費用優(yōu)化問題可以描述為：給定連通的的平面圖G＝(V，E，c)。G有n個頂點，m條邊，即 ，，邊費用函數(shù)c：ER+。r是組成員更新請求，r=(r0,r1,r2…..rk)。其中ri＝(vi，pi)，(加入，離開)。除了撤消整個通信進(jìn)程的請求之外，每次請求只包括一個結(jié)點。 在ri請求后的組成員集合Si為： 因為Si集合不知道請求rj(j>I)的情況，所以動態(tài)路由優(yōu)化屬于在線問題。 動態(tài)路由優(yōu)化問題可以分為四大類： 1．不允許結(jié)構(gòu)重組的路由優(yōu)化方案：指在有成員離開或新結(jié)點加入到通信組時，優(yōu)化路由的原則，是對通信組內(nèi)的其他成員的通信路徑不作改動。 2．完全結(jié)構(gòu)重組的路由優(yōu)化方案：指在現(xiàn)有的成員之間建立一個網(wǎng)絡(luò)費用最優(yōu)路由樹。一旦有成員離開通信組或有新結(jié)點加入通信組，在更新后的成員之間再建立一個網(wǎng)絡(luò)費用最優(yōu)路由樹。這實際上是退化到靜態(tài)路由優(yōu)化問題。 3．部分結(jié)構(gòu)重組的路由優(yōu)化方案：指在成員更新后，只對路由樹的某些部分進(jìn)行調(diào)整，被調(diào)整的路由鏈路數(shù)不超過一定上限。避免了全局調(diào)整的復(fù)雜計算，同時也將對其它成員的影響降低到最小。 4．觸發(fā)結(jié)構(gòu)重組的路由優(yōu)化方案：指在成員更新后，開始按不允許結(jié)構(gòu)重組的優(yōu)化方案來更新路由，同時監(jiān)視更新后路由樹的費用。一旦路由樹費用與最優(yōu)費用之比超過某個門限值，就進(jìn)行一次結(jié)構(gòu)重組。這時的結(jié)構(gòu)重組可能是完全結(jié)構(gòu)重組，也可能是部分結(jié)構(gòu)重組。觸發(fā)結(jié)構(gòu)重組的優(yōu)化方案減少了路由重組的次數(shù)，節(jié)省了計算費用，并可將路由樹的費用和最優(yōu)費用之比維持在一定的水平。它的缺點也在于沒有從根本上克服路由結(jié)構(gòu)重組帶來的問題，并且需要不斷監(jiān)視路由樹的費用，會增加路由優(yōu)化的復(fù)雜性和額外開銷。 4 MON動態(tài)組播路由算法PRRN-N 全組播網(wǎng)絡(luò)的組播樹生成算法目前已提出了很多，在其時間復(fù)雜度可以忍受的前提下，目前所提出的算法大多是在尋求次優(yōu)解，許多用啟發(fā)式算法或者遺傳算法、螞蟻算法等求解組播路由問題的文章相繼發(fā)表。然而應(yīng)該認(rèn)識到，啟發(fā)式算法有其自身的缺陷，即只能找到局部最優(yōu)，遺傳算法和螞蟻算法雖然都是全局算法，但是其編解碼方法都比較復(fù)雜，個體編解碼復(fù)雜度為O(n2)~ O(n3)。另外，目前對組播路由問題的表述模型尚不統(tǒng)一。所以，在此本文利用簡潔的Prüfer編碼，通過構(gòu)造完全圖的方式，把MON組播樹“樹核”的求解問題改為全組播路由問題來求解，以得到更快的通用的全組播網(wǎng)絡(luò)組播樹的遺傳算法。 4．1　PRRN－N覆蓋層組播“樹核”生成算法 MON中具有組播功能的結(jié)點，其組播路由問題的概念模型可以表示為：設(shè)網(wǎng)絡(luò)G(V,E)，V是節(jié)點 (表示所有具有組播功能及非組播功能結(jié)點的總和)的集合, E是邊(表示節(jié)點之間的點到點連接)的集合，邊權(quán)表示節(jié)點之間的組播代價。 給定源的集合 ,具有組播功能的結(jié)點集合，對要求解一棵滿足網(wǎng)絡(luò)費用代價最小的組播樹，使得：T以s為根節(jié)點，且，這里VT表示T的節(jié)點集合。 先將V中的帶有組播功能的結(jié)點集合D中的所有結(jié)點，以Dijkstra算法由圖G中的最短路構(gòu)造其完全圖Kn，E是邊(任兩組播結(jié)點之間的連接)的集合，邊權(quán)表示結(jié)點之間的“組播代價”，在此為圖G中兩點間的最短路。 完全圖Kn的不同生成樹共有nn-2棵，正好可以用n-2位的n-進(jìn)制整數(shù)來表示，每位數(shù)字都在[1..n]之間，它對應(yīng)為Kn的節(jié)點編號，這就是Prüfer編碼，它為設(shè)計基于生成樹的優(yōu)化問題的遺傳算法提供了最簡潔的編碼方案之一。由Prüfer序列到生成樹T的解碼算法seqToTree如下：  算法1   seqToTree [算法開始] 輸入：Prüfer編碼序列P； 輸出：Kn的生成樹T； [算法開始] 確定節(jié)點數(shù)n:=P的長度+2； 統(tǒng)計每個節(jié)點在P中的出現(xiàn)次數(shù)A[1..n]； 生成具有n個孤立節(jié)點的圖T,節(jié)點依次標(biāo)記為1,2,…,n； 令Q為T的所有不在P中的節(jié)點編號集合,并非減有序； 當(dāng)P非空，循環(huán)做 從P中移出第一個元素v, 從Q中移出第一個元素u, A[v]:=A[v]-1； 在T中增加邊<v,u>； 如果A[v]=0, 則折半插入v到Q中； 從Q中移出最后兩個元素v和u, 在T中增加邊<v,u>； 輸出T. [算法結(jié)束] 由于Prüfer編碼代表的生成樹是無序樹（不指定根），而組播樹需要指定根，所以我們擴充Prüfer編碼為n-1位，最后一位代表根節(jié)點編號。另外，還需要對解碼得到的Kn的生成樹進(jìn)行剪枝，刪除不在組播終點集D中的葉子節(jié)點才能得到所求的組播樹，剪枝算法prune的設(shè)計見如下： 算法2   prune 輸入：Kn的生成樹T,組播終點集合D; 輸出：組播樹T； [算法開始] 對T做后根次序遍歷,一邊遍歷一邊做： a)如果當(dāng)前被遍歷節(jié)點v是葉子節(jié)點并且不在D中,則: 從T中刪除v； 輸出T. [算法結(jié)束] 遺傳算法設(shè)計： 遺傳算法基于達(dá)爾文進(jìn)化論的思想，將待求問題的解空間看成自然界，將解空間中的每個變量的目標(biāo)函數(shù)值看成個體對環(huán)境的適應(yīng)性，然后通過（自然）選擇、交叉、變異等遺傳操作不斷進(jìn)化，在一個可以接受的時間內(nèi)到達(dá)一代比較優(yōu)秀的種群，其中包含了我們要求的最優(yōu)或近似最優(yōu)個體。 一個特定的遺傳算法主要由染色體編碼、種群初始化、適應(yīng)值標(biāo)定和遺傳算子（選擇、交叉和變異）設(shè)計等方面組成�；�于前面的討論，我們設(shè)計了求解模型的遺傳算法：染色體用擴充的Prüfer編碼表示；給定具有n個節(jié)點的網(wǎng)絡(luò)G和種群規(guī)模P后，初始種群由隨機生成的P行n-1列的矩陣表示，其中的每個元素為[1..n]之間的整數(shù)，代表G中的節(jié)點編號；計算每個染色體（Prüfer序列）的適應(yīng)值時，依次用算法seqToTree和prune得到組播樹T，通過計算該個體的優(yōu)化目標(biāo)值g，再對g做標(biāo)定得到個體適應(yīng)值f=1/(1+g)；選擇算子采用改進(jìn)的一次旋轉(zhuǎn)賭輪方法；交叉算子采用隨機多點交叉；變異算子采用基因位變異和基因片變異（包括遷移和翻轉(zhuǎn)）；保優(yōu)策略，即每代最優(yōu)秀個體直接進(jìn)入下一代而不參與交叉和變異。  算法復(fù)雜性分析： 從算法中可以看出，對每一染色體解碼求生成樹的復(fù)雜度為O(nlogn)，對生成樹進(jìn)行剪枝得到組播分布樹的算法復(fù)雜度為O(n)；而對得到的組播樹進(jìn)行優(yōu)化目標(biāo)值計算和適應(yīng)值標(biāo)定所需要的復(fù)雜度可以從如下方面分析： 根據(jù)Dijkstra的算法，計算每對節(jié)點間最短路徑需要O(n3)的復(fù)雜度。但是，我們注意到是在給定的組播樹T中，若求解的是有源樹，給定組播源點s后，對任意的d，計算節(jié)點對(s,d)之間的距離時只需從s出發(fā)對T做一次遍歷即可，復(fù)雜度為O(n)；若計算的是共享樹，則對任意的組播源點s，組播信息都是先從s通過第一跳單播到共享根，再從共享根到達(dá)每個組播終點d，所以計算節(jié)點對(s,d)之間的距離時也只需從共享根出發(fā)對T做一次遍歷，復(fù)雜度也為O(n)；   交叉算子和變異算子的復(fù)雜度均不超過O(n)； 于是，給定群規(guī)模P和最大進(jìn)化代數(shù)maxG，該算法的計算復(fù)雜度為O(P×maxG×O(mlogm))式中m為組播功能結(jié)點數(shù)，相對于求解同類問題的其它算法而言，這個結(jié)果確實令人鼓舞。所有利用遺傳算法求解組播路由問題的算法都需要進(jìn)行優(yōu)化目標(biāo)值的計算和適應(yīng)值標(biāo)定，以上的設(shè)計實現(xiàn)了一種更快的求解全組播網(wǎng)絡(luò)組播路由問題的遺傳算法。然而，應(yīng)該注意的是，Prüfer數(shù)表示的是Kn的生成樹，而不是給定網(wǎng)絡(luò)G(V,E),|V|=n的生成樹；組播數(shù)T也不是G的生成樹，而是針對組播源點集S和組播功能結(jié)點集MV的steiner樹。在求得最優(yōu)解后，需要將得到的組播樹按圖G中的最短路展開，并對相同路作歸并操作。以此才能得到所求部分組播網(wǎng)絡(luò)組播生成樹的“樹核”。如圖1.   圖1　覆蓋層組播“樹核”生成 4.2　PRRH-N結(jié)點動態(tài)加入算法： [算法開始]    1)以部分組播網(wǎng)絡(luò)基于網(wǎng)絡(luò)費用最優(yōu)的靜態(tài)組播樹生成算法先生成動態(tài)組播樹的“樹核”T。 2)當(dāng)新的一個結(jié)點Di要加入組播組時，先計算其到“樹核”T中各組播結(jié)點MVi(其取值范圍是MVS集合的成員)的最短路。 3)比較此結(jié)點Di到源s的最短路近還是到離它最近的組播結(jié)點MVi的最短路近，如到源近直聯(lián)到源。在樹中加入結(jié)點Di及其到源的邊。 4)如到最近的MVi近，則檢查此MVi是否已是組播組內(nèi)成員(本身是端結(jié)點或有別的結(jié)點通過此組播功能結(jié)點接入組播組)，如是，以此MVi結(jié)點為“登陸結(jié)點”接入組播組(如有兩個結(jié)點滿足要求，選擇距s近的那一MV結(jié)點)。樹中加入結(jié)點Di及其到此MVi結(jié)點的邊 5)如最近的MVi結(jié)點還不是組內(nèi)結(jié)點，則向它注冊, 并告之此Di到它的最短路是多少及到源的最短路是多少，同時計算所有向此結(jié)點注冊的結(jié)點經(jīng)它連入組播樹的費用和是否小于直連源的費用和，如是所有注冊結(jié)點由其連入組播樹，反之計算此Di到“樹核”T上各組播功能結(jié)點MVi及MVi到源s的最短路徑的值,找到T中含有組播結(jié)點MVi的到源s的最短路Pmin，比較此結(jié)點Di到源s的最短路近還是到擁有Pmin的組播結(jié)點MVi的最短路近，如到源近直聯(lián)到源。在樹中加入結(jié)點Di及其到源的邊。 6)反之，選擇此擁有Pmin的組播結(jié)點MVi作為此結(jié)點的“登陸結(jié)點”連入組播組(如有多點滿足要求，選擇距s遠(yuǎn)的那一MV結(jié)點)。并在組播樹中加入Pmin邊。 [算法結(jié)束] 如圖2.       圖2. PRRH-N結(jié)點動態(tài)加入算法 4.3　PRRH-N結(jié)點動態(tài)退出算法： [算法開始] 1)如果此結(jié)點是直聯(lián)到源的，且路徑中沒有別的組內(nèi)成員，則將路中所有的結(jié)點從樹中刪除。并在距此點最近的MVi結(jié)點注消此結(jié)點 2)如果此結(jié)點是直聯(lián)到源的，但路徑中還有別的組內(nèi)成員，則將此結(jié)點刪除直到另一組內(nèi)成員成為葉子結(jié)點為止。在距此點最近的MVi結(jié)點注消此結(jié)點的同時，注消新的葉子結(jié)點，并對這一剛成為葉子結(jié)點的組內(nèi)成員用動態(tài)結(jié)點加入算法重新加入組播組。 3)如果此結(jié)點是聯(lián)到“樹核”T中的組播功能結(jié)點MVi上的，且MVi上還連著其它的組內(nèi)成員，在刪除此結(jié)點的同時，要計算所有經(jīng)此MVi結(jié)點連入組播組的結(jié)點至源s的費用總和是否大于其向源直聯(lián)的費用總和。如是注消這些結(jié)點，并用動態(tài)結(jié)點加入算法將這些結(jié)點重新加入組播組。 [算法結(jié)束]                           5 MON動態(tài)組播路由算法PRRN-D 目的地費用最優(yōu)路由算法是用來優(yōu)化路由的目的地費用。如果是點到點通信，那么目的地費用最優(yōu)也就是網(wǎng)絡(luò)費用最優(yōu)。但在多點通信中，兩者并不等價。在點到多點通信中，可以先計算源到每個目的結(jié)點的費用最優(yōu)路徑。然后將這些路徑合并(全組播網(wǎng)絡(luò))。路徑中相同的鏈路可以被共享。形成的路由樹稱為目的地費用最優(yōu)組播路由樹。雖然目的地費用最優(yōu)組播路由樹的網(wǎng)絡(luò)費用不一定是最優(yōu)的，但可以推測它的網(wǎng)絡(luò)費用至少不會太差。并且目的地費用最優(yōu)路由樹的網(wǎng)絡(luò)費用與目的結(jié)點加入或離開通信組的先后次序無關(guān)，這對于動態(tài)路由的優(yōu)化是有益的。因此目的地費用最優(yōu)路由算法也可以在多點動態(tài)路由中優(yōu)化網(wǎng)絡(luò)費用。 5.1 PRRH-D覆蓋層組播“樹核”生成算法  MON中具有組播功能的節(jié)點亦可依據(jù)目的地費用最優(yōu)的思想，以啟發(fā)的方法高速構(gòu)成PRRN－D覆蓋層組播“樹核”。其算法如下： [算法開始] 1)選擇組播功能結(jié)點集合MVS的成員，各組播功能結(jié)點先對組播源點s以Dijkstra算法最短路尋路，然后執(zhí)行“歸并操作”即合并相同邊，“歸并操作”后的組播樹即為我們所要求的部分組播網(wǎng)絡(luò)組播樹的“樹核”。 2)對“歸并操作”后的組播結(jié)點“樹核”，計算每一個組播結(jié)點到源s的路徑長度，并寫入各組播結(jié)點的路由表。 [算法結(jié)束] 5.2　PRRH-D結(jié)點動態(tài)加入算法： [算法開始] 1)以部分組播網(wǎng)絡(luò)基于目的地費用最優(yōu)的靜態(tài)組播樹生成算法先生成動態(tài)組播樹的“樹核”T。 2)當(dāng)新的一個結(jié)點Di要加入組播組時，先計算其到“樹核”T中各組播結(jié)點MVi(其取值范圍是MVS集合的成員)的最短路。 3)比較此結(jié)點Di到源s的最短路近還是到離它最近的組播結(jié)點MVi的最短路近，如到源近直聯(lián)到源。在樹中加入結(jié)點Di及其到源的邊。 4)如到最近的MVi近，則檢查此MVi是否已是組播組內(nèi)成員(本身是端結(jié)點或有別的結(jié)點通過此組播功能結(jié)點接入組播組)，如是，以此MVi結(jié)點為“登陸結(jié)點”接入組播組(如有兩點滿足要求，選擇距s近的那一MV結(jié)點)。樹中加入結(jié)點Di及其到此MVi結(jié)點的邊 5)如最近的MVi結(jié)點還不是組內(nèi)結(jié)點，則向它注冊, 并告之此Di到它的最短路是多少及到源的最短路是多少，同時計算所有向此結(jié)點注冊的結(jié)點經(jīng)它連入組播樹的費用和是否小于直連源的費用和，如是所有注冊結(jié)點由其連入組播樹，反之計算此Di到“樹核”T上各組播功能結(jié)點MVi及MVi到源s的最短路徑的值,找到T中含有組播結(jié)點MVi的到源s的最短路Pmin，比較此結(jié)點Di到源s的最短路近還是到擁有Pmin的組播結(jié)點MVi的最短路近，如到源近直聯(lián)到源。在樹中加入結(jié)點Di及其到源的邊。 6)反之，選擇此擁有Pmin的組播結(jié)點MVi作為此結(jié)點的“登陸結(jié)點”連入組播組(如有兩點滿足要求，選擇距s遠(yuǎn)的那一MV結(jié)點)。并在組播樹中加入Pmin邊。 [算法結(jié)束] 5.3　PRRH-D結(jié)點動態(tài)退出算法： [算法開始] 1)如果此結(jié)點是直聯(lián)到源的，且路徑中沒有別的組內(nèi)成員，則將路中所有的結(jié)點從樹中刪除。并在距此點最近的MVi結(jié)點注消此結(jié)點 2)如果此結(jié)點是直聯(lián)到源的，但路徑中還有別的組內(nèi)成員，則將此結(jié)點刪除直到另一組內(nèi)成員成為葉子結(jié)點為止。在距此點最近的MVi結(jié)點注消此結(jié)點的同時，注消新的葉子結(jié)點，并對這一剛成為葉子結(jié)點的組內(nèi)成員用動態(tài)結(jié)點加入算法重新加入組播組。 3)如果此結(jié)點是聯(lián)到“樹核”T中的組播功能結(jié)點MVi上的，且MVi上還連著其它的組內(nèi)成員，在刪除此結(jié)點的同時，要計算所有經(jīng)此MVi結(jié)點連入組播組的結(jié)點至源s的費用總和是否大于其向源直聯(lián)的費用總和。如是，則注消這些結(jié)點，并用動態(tài)結(jié)點加入算法將這些結(jié)點重新加入組播組。 [算法結(jié)束] 以上算法參見圖畫3. 圖3　覆蓋層組播“樹核”生成及節(jié)點動態(tài)加入、退出舉例 6 兩種算法復(fù)雜度及網(wǎng)絡(luò)模擬 PRRH-D算法：其組播結(jié)點樹核生成時，采用的是Dijkstra算法，然后對各組播結(jié)點向源結(jié)點s所尋到的最短路進(jìn)行歸并，設(shè)其MV結(jié)點數(shù)為m，網(wǎng)絡(luò)規(guī)模即網(wǎng)絡(luò)中總的結(jié)點數(shù)為n，則其樹核生成最壞情況下時間復(fù)雜度為 。而各終端結(jié)點加入組播組時每一結(jié)點最壞情況下要調(diào)用Dijkstra算法三次，分別對源結(jié)點s及樹核內(nèi)距終端結(jié)點Di最近的MV結(jié)點和具有P(Di,MVi,s)min的MV結(jié)點尋最短路，最壞情況下，每一終端結(jié)點最終加入組播組的時間復(fù)雜度為。PRRH-D算法的每一結(jié)點退出操作的最差情況的時間復(fù)雜度為，t為組播樹中所含的結(jié)點數(shù)，而因此而選擇重新選路的各終端結(jié)點需再次調(diào)用Dijkstra算法三次，如這部分結(jié)點數(shù)為r,則最壞情況下，這部分終端結(jié)點最終加入組播組的時間復(fù)雜度為。 PRRH-N算法屬于源路由算法(source-rooted routing)。源路由算法的結(jié)點經(jīng)某一路由協(xié)議(如鏈路狀態(tài)協(xié)議)獲得完整的網(wǎng)絡(luò)拓樸信息。網(wǎng)絡(luò)中每一結(jié)點的拓樸信息是一樣的，所以網(wǎng)絡(luò)中每一結(jié)點都可以接受用戶呼叫并進(jìn)行路由計算。假設(shè)網(wǎng)絡(luò)狀態(tài)信息在算法執(zhí)行之前已經(jīng)完成，且在算法計算路由時，網(wǎng)絡(luò)的拓樸狀態(tài)不變。則NCH及DCH算法的時間復(fù)雜度的計算就可以分為兩個獨立的兩個部分(組播結(jié)點樹核的生成及終端結(jié)點最終完成加入組播組)來計算，綜述如下： 其組播組結(jié)點樹核生成時，首先要以組播功能結(jié)點間的最短路生成其全連通網(wǎng)絡(luò)。采用Dijkstra算法，各組播結(jié)點及源結(jié)點s間彼此最短路尋徑，設(shè)其MV結(jié)點數(shù)為m，網(wǎng)絡(luò)規(guī)模即網(wǎng)絡(luò)中總的結(jié)點數(shù)為n，則組播功能結(jié)點全連通網(wǎng)絡(luò)生成在最壞情況下時間復(fù)雜度為。而樹核生成的遺傳算法和seqToTree算法的時間復(fù)雜度為O(P×maxG×O(mlogm))。同樣每一終端結(jié)點加入組播組時每一結(jié)點最壞情況下要調(diào)用Dijkstra算法三次，分別對源結(jié)點s及樹核內(nèi)距終端結(jié)點Di最近的MV結(jié)點和具有P(Di,MVi,s)min的MV結(jié)點尋最短路，最壞情況下，每一終端結(jié)點最終加入組播組的時間復(fù)雜度為。PRRH-N算法的每一結(jié)點退出操作的最差情況的時間復(fù)雜度為，t為組播樹中所含的結(jié)點數(shù)，而因此選擇重新選路的各終端結(jié)點需再次調(diào)用Dijkstra算法三次，如這部分結(jié)點數(shù)為r,則最壞情況下，這部分終端結(jié)點最終加入組播組的時間復(fù)雜度為。 由于兩種算法都采用了分布式觸發(fā)的思想，無需覆蓋層對整體的費用做出監(jiān)控及評價，故而從基礎(chǔ)解決了原觸發(fā)重組費用優(yōu)化方案的缺點，減輕了路由優(yōu)化的復(fù)雜性和額外開銷。 目前對于MON網(wǎng)絡(luò)動態(tài)組播樹的生成算法，還沒有研究人員進(jìn)行過系統(tǒng)的研究，因此也還沒有基準(zhǔn)算法來用于網(wǎng)絡(luò)模擬和比較。因此，本文的網(wǎng)絡(luò)模擬只能采用課題組MON靜態(tài)組播樹生成算法NCH來作為模擬基準(zhǔn)。 ·圖4  PRRH-N，PRRH-D算法EAD仿真網(wǎng)絡(luò)模擬數(shù)據(jù) 本文以課題組EAD仿真模型所生成的模擬網(wǎng)絡(luò)來做模擬平臺，在EAD算法生成的模擬網(wǎng)絡(luò)過程中，其MV結(jié)點比例是固定的(17%)，而長短邊之比隨著不同的需求，通過對 及F2的調(diào)節(jié)，也可以被定位于一很小的領(lǐng)域內(nèi)，所以在同一網(wǎng)絡(luò)規(guī)模前提下影響部分組播網(wǎng)絡(luò)動態(tài)組播樹生成算法的可變因素主要有：1.加入組播組的端結(jié)點的更新速度,2.在某一時刻，組播組成員數(shù)量在模擬網(wǎng)絡(luò)的全部結(jié)點中所占的比例，對于這兩點，都可以以一個無量綱的概念，對不同的網(wǎng)絡(luò)規(guī)模進(jìn)行一致的模擬，以利于后期實驗結(jié)果的比較。 本文采用以下假設(shè)：加入組播組的端結(jié)點以一種穩(wěn)定的速度進(jìn)行更新，即某一時刻有占網(wǎng)絡(luò)結(jié)點總數(shù)5%的組播組成員退出組播組，而另有占網(wǎng)絡(luò)結(jié)點總數(shù)5%的非組播組成員加入組播組，而初始狀態(tài)選擇組播組成員占總結(jié)點數(shù)的20%和40%來進(jìn)行模擬。這樣就有可能選擇相同的靜態(tài)部分組播網(wǎng)絡(luò)組播樹生成算法來作為待模擬算法的基準(zhǔn)算法，以便能從本質(zhì)上把握待模擬算法的一些基本特征，并給出其性能評價。 由模擬數(shù)據(jù)可知(見圖4)，PRRH-N和PRRH-D算法因為可以在結(jié)點加入組播組及結(jié)點退出組播組時都能觸發(fā)樹結(jié)構(gòu)的部分重組。所以其費用能夠被限定在基準(zhǔn)以上的一個很小的區(qū)域內(nèi)，因為考慮到現(xiàn)實網(wǎng)絡(luò)中的實現(xiàn)問題，兩種算法都沒有終端結(jié)點向上歸并的操作，所以，實驗中可見費用會出現(xiàn)“躍點”，特別是當(dāng)組播組成員比例相對較小時，這一點表現(xiàn)的尤為突出。在組播組成員比例進(jìn)一步增加時，兩種算法都表現(xiàn)出很好的收斂性，而且其費用的統(tǒng)計平均值也均被限定在不高于基準(zhǔn)的10%，這一結(jié)果還是非常令人鼓舞的。 7  結(jié)束語 PRRH-N算法在費用優(yōu)化方面是兩種算法中最優(yōu)的，基于結(jié)點費用最優(yōu)觸發(fā)重組操作，能最大限度的減小算法的散列躍度，算法收斂性能夠有一個很好保證，但時間復(fù)雜度整體來說過大，在實際應(yīng)用中，可操作性要明顯低于PRRH-D算法。但在組播組成員相對較少時，對費用優(yōu)化苛刻的前提下，該算法還是應(yīng)該成為首選的。 PRRH-D算法在時間復(fù)雜度方面較PRRH-N算法為優(yōu)，而其網(wǎng)絡(luò)費用優(yōu)化又明顯的線性逼近 PRRH-N算法，在組播組成員比例達(dá)到40%左右時，該算法的費用優(yōu)化性能已近似等于PRRH-N算法， 故在對算法計算時間及費用優(yōu)化都有較高要求時，還是選用PRRH-D算法為好。 因兩種算法都是基于“樹核”的，所以兩種算法都可以在一定路由協(xié)議的支持下進(jìn)行多面體分級路由模式的改良，也可以方便的向多點對多點組播路由算法改進(jìn)，這樣就能夠使算法在可擴展性方面有一個質(zhì)的提高，同時也可以使其向多點對多點路由計算提供良好的支持。其次，基于“樹核”的路由方式，也可以在鏈路負(fù)載平衡方面較原有的CBT算法(原針對全組播網(wǎng)絡(luò)的一種多對多組播路由算法)有一個質(zhì)的提高。以上方案都將是今后對于部分組播網(wǎng)絡(luò)路由算法研究的很好的方向。 參考文獻(xiàn) [1]   董慶陽,  計算機通信網(wǎng)絡(luò)組播路由算法和協(xié)議的研究, 上海交通大學(xué)博士學(xué)位論文, 2000年 [2]   王征應(yīng),  高速網(wǎng)絡(luò)QOS路由技術(shù)的研究及路由仿真平臺的研制, 華中科技大學(xué)博士學(xué)位論文, 2001年 [3]   李漢兵, 計算機網(wǎng)絡(luò)路由算法, 西安電子科技大學(xué)博士學(xué)位論文, 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  余鎮(zhèn)危, 劉克儉　  中國礦業(yè)大學(xué)(北京)，北京，100083 zwyu@cumtb.edu.cn  摘要：本文給出了組播覆蓋網(wǎng)絡(luò)MON動態(tài)路由的定義，并在此基礎(chǔ)上提出了MON動態(tài)組播路由計算所應(yīng)考慮的問題，給出了基于分布式觸發(fā)重組的MON動態(tài)組播路由算法NPPR-N和NPPR-D，并在本文的最后對算法的復(fù)雜度進(jìn)行了推證，對算法的有效性進(jìn)行了以EAD模型為基礎(chǔ)平臺的網(wǎng)絡(luò)模擬。 關(guān)鍵詞：OVERLAY；組播；動態(tài)路由；分布式觸發(fā)重組 1　引言 現(xiàn)實的網(wǎng)絡(luò)環(huán)境，還不具備為實現(xiàn)某一種應(yīng)用而全部改造或重新定制現(xiàn)有路由器或交換機的可能，如何利用已改造的有限的功能節(jié)點來完成與其新型應(yīng)用需求線性逼近的網(wǎng)絡(luò)性能，這就是OVERLAY網(wǎng)絡(luò)目前所熱衷研究的問題。就組播問題來說，所有節(jié)點都具有組播功能的網(wǎng)絡(luò)稱為全組播網(wǎng)絡(luò)，這是為簡化問題的研究，而對網(wǎng)絡(luò)參數(shù)進(jìn)行的極度弱化，過去包括目前所提出的幾乎所有的組播路由算法，雖然解決問題所使用的技術(shù)會有所不同，比如啟發(fā)式，螞蟻或遺傳，但都是針對全組播網(wǎng)絡(luò)而言。顯然這些在全組播網(wǎng)絡(luò)基礎(chǔ)上所提出的算法，距真正的應(yīng)用于實際網(wǎng)絡(luò)，還有很大的距離。                                      2 MON組播樹問題的描述 目前在實際的網(wǎng)絡(luò)環(huán)境中，具有組播功能的結(jié)點的比率還不是很高，大約只有20%左右(2000年為17%)。而如何利用不足五分之一的組播功能節(jié)點來完成組播應(yīng)用的需求呢？這就是我們研究組播OVERLAY網(wǎng)絡(luò)的初衷。網(wǎng)絡(luò)中只有部分節(jié)點具有組播功能的網(wǎng)絡(luò)我們稱其為部分組播網(wǎng)絡(luò)。在部分組播網(wǎng)絡(luò)中，所有的具有組播功能的節(jié)點就構(gòu)成了對整個網(wǎng)絡(luò)的一個組播覆蓋（multicast overlay）,因此對部分組播網(wǎng)絡(luò)組播問題的研究就轉(zhuǎn)化為覆蓋網(wǎng)絡(luò)路由研究的一部分。組播覆蓋網(wǎng)絡(luò)組播樹與全組播網(wǎng)絡(luò)組播樹的不同之處在于，前者會包含很多重復(fù)的鏈路，而后者則沒有。因為組播覆蓋網(wǎng)絡(luò)中，如果從一個節(jié)點到幾個節(jié)點的路徑中有相同的鏈路，而相同鏈路中的節(jié)點如不具有組播功能，則這些相同的鏈路就無法共享。因此在組播覆蓋網(wǎng)絡(luò)中，組播樹的求解問題，就與一般定義的全組播網(wǎng)絡(luò)的組播樹的求解問題有所不同。 本文中有如下定義 定義1.1：在MON組播覆蓋網(wǎng)絡(luò)中，具有組播功能的結(jié)點為MV(multicastable Vertex)節(jié)點，反之，不具有組播功能的結(jié)點稱為NMV(Non-multicastable Vertex)節(jié)點。 定義1-2：組播覆蓋網(wǎng)絡(luò)組播樹：給定一個網(wǎng)絡(luò)有向圖G=(V,M,E,C),V由MV結(jié)點(組播功能結(jié)點)和NMV結(jié)點(非組播功能結(jié)點)組成，MV結(jié)點的集合為M，E為圖中所有邊的集合，C為邊所對應(yīng)的權(quán)值的集合，從V中選擇一組結(jié)點(terminal)D,一個源結(jié)點s D,從G中生成一個樹T=(VT，MT，ET，CT)，使得樹的費用最小，生成的樹就稱為組播樹，其中TG ，VT V，DVT，，MTVT，ETE，T中的源結(jié)點s到每一個D中的結(jié)點都有通路，且s的入度為0，其中非端結(jié)點的NMV結(jié)點入度與出度相等，而非端結(jié)點的MV結(jié)點的出度至少等于其入度。 1基金項目：高等學(xué)校博士學(xué)科點專項科研基金資助課題（20030290003） 定義1-3：最短路徑：結(jié)點u,vV之間的最短路徑是指從u到v的費用最小的路徑，用P(u,v)表示，若沿P(u,v)的結(jié)點有u,v0,v1…vk-1,vk,v,則P(u,v)={u,v0,v1…vk-1,vk,v}。結(jié)點到樹的最短路徑是指結(jié)點到該樹所有結(jié)點中路徑最短的那一條。 定義1-4：組播覆蓋網(wǎng)絡(luò)組播樹費用CT：設(shè)組播樹T中的鏈路有N條，而其中某一非組播鏈路如果出現(xiàn)的次數(shù)為ni次，如圖3-1中邊E(2，4)：則組播樹的總費用可表示成為： CT   3 MON動態(tài)組播樹問題的描述 動態(tài)路由優(yōu)化問題是多點通信所特有的。在點到點通信中，不會有第三方的介入。如果其中有一方想離開，整個通信進(jìn)程也就終止了，因此不存在動態(tài)路由問題。而在多點通信中，參與通信組的成員可以隨時地離開，新的結(jié)點也可以隨時地加入而不影響整個通信進(jìn)程。通信成員的動態(tài)性決定了多點路由的動態(tài)性。當(dāng)然，動態(tài)路由的概念還可以擴展。由于鏈路失敗、局部擁塞、網(wǎng)絡(luò)拓?fù)渥兓�等原因使某些成員脫離了通信組，那么這些成員重新加入到通信組的過程也就相當(dāng)于一個新成員的加入過程。靜態(tài)路由優(yōu)化是在通信開始之前，在一組己知的成員之間，利用某種優(yōu)化算法來尋找路由。而對于動態(tài)路由，由于無法事先預(yù)測哪些成員將會加入或離開通信組。原則上還要求路由調(diào)整時對其它成員不造成影響或影響的程度很小。因此，動態(tài)路由的優(yōu)化問題比靜態(tài)路由的更為復(fù)雜，但其研究成果卻對實際網(wǎng)絡(luò)更具現(xiàn)實意義。 多點動態(tài)路由優(yōu)化同樣可分為網(wǎng)絡(luò)費用優(yōu)化和目的地費用優(yōu)化。由于目的地費用優(yōu)化與目的結(jié)點加入或離開通信組的次序無關(guān)，只與該目的結(jié)點和源有關(guān)，因此動態(tài)路由中目的地費用優(yōu)化問題和靜態(tài)路由中目的地費用優(yōu)化問題是一樣的。本文主要研究動態(tài)路由中網(wǎng)絡(luò)費用優(yōu)化問題。如不作特別說明，動態(tài)路由優(yōu)化專指動態(tài)路由的網(wǎng)絡(luò)費用優(yōu)化。 動態(tài)路由網(wǎng)絡(luò)費用優(yōu)化問題可以描述為：給定連通的的平面圖G＝(V，E，c)。G有n個頂點，m條邊，即 ，，邊費用函數(shù)c：ER+。r是組成員更新請求，r=(r0,r1,r2…..rk)。其中ri＝(vi，pi)，(加入，離開)。除了撤消整個通信進(jìn)程的請求之外，每次請求只包括一個結(jié)點。 在ri請求后的組成員集合Si為： 因為Si集合不知道請求rj(j>I)的情況，所以動態(tài)路由優(yōu)化屬于在線問題。 動態(tài)路由優(yōu)化問題可以分為四大類： 1．不允許結(jié)構(gòu)重組的路由優(yōu)化方案：指在有成員離開或新結(jié)點加入到通信組時，優(yōu)化路由的原則，是對通信組內(nèi)的其他成員的通信路徑不作改動。 2．完全結(jié)構(gòu)重組的路由優(yōu)化方案：指在現(xiàn)有的成員之間建立一個網(wǎng)絡(luò)費用最優(yōu)路由樹。一旦有成員離開通信組或有新結(jié)點加入通信組，在更新后的成員之間再建立一個網(wǎng)絡(luò)費用最優(yōu)路由樹。這實際上是退化到靜態(tài)路由優(yōu)化問題。 3．部分結(jié)構(gòu)重組的路由優(yōu)化方案：指在成員更新后，只對路由樹的某些部分進(jìn)行調(diào)整，被調(diào)整的路由鏈路數(shù)不超過一定上限。避免了全局調(diào)整的復(fù)雜計算，同時也將對其它成員的影響降低到最小。 4．觸發(fā)結(jié)構(gòu)重組的路由優(yōu)化方案：指在成員更新后，開始按不允許結(jié)構(gòu)重組的優(yōu)化方案來更新路由，同時監(jiān)視更新后路由樹的費用。一旦路由樹費用與最優(yōu)費用之比超過某個門限值，就進(jìn)行一次結(jié)構(gòu)重組。這時的結(jié)構(gòu)重組可能是完全結(jié)構(gòu)重組，也可能是部分結(jié)構(gòu)重組。觸發(fā)結(jié)構(gòu)重組的優(yōu)化方案減少了路由重組的次數(shù)，節(jié)省了計算費用，并可將路由樹的費用和最優(yōu)費用之比維持在一定的水平。它的缺點也在于沒有從根本上克服路由結(jié)構(gòu)重組帶來的問題，并且需要不斷監(jiān)視路由樹的費用，會增加路由優(yōu)化的復(fù)雜性和額外開銷。 4 MON動態(tài)組播路由算法PRRN-N 全組播網(wǎng)絡(luò)的組播樹生成算法目前已提出了很多，在其時間復(fù)雜度可以忍受的前提下，目前所提出的算法大多是在尋求次優(yōu)解，許多用啟發(fā)式算法或者遺傳算法、螞蟻算法等求解組播路由問題的文章相繼發(fā)表。然而應(yīng)該認(rèn)識到，啟發(fā)式算法有其自身的缺陷，即只能找到局部最優(yōu)，遺傳算法和螞蟻算法雖然都是全局算法，但是其編解碼方法都比較復(fù)雜，個體編解碼復(fù)雜度為O(n2)~ O(n3)。另外，目前對組播路由問題的表述模型尚不統(tǒng)一。所以，在此本文利用簡潔的Prüfer編碼，通過構(gòu)造完全圖的方式，把MON組播樹“樹核”的求解問題改為全組播路由問題來求解，以得到更快的通用的全組播網(wǎng)絡(luò)組播樹的遺傳算法。 4．1　PRRN－N覆蓋層組播“樹核”生成算法 MON中具有組播功能的結(jié)點，其組播路由問題的概念模型可以表示為：設(shè)網(wǎng)絡(luò)G(V,E)，V是節(jié)點 (表示所有具有組播功能及非組播功能結(jié)點的總和)的集合, E是邊(表示節(jié)點之間的點到點連接)的集合，邊權(quán)表示節(jié)點之間的組播代價。 給定源的集合 ,具有組播功能的結(jié)點集合，對要求解一棵滿足網(wǎng)絡(luò)費用代價最小的組播樹，使得：T以s為根節(jié)點，且，這里VT表示T的節(jié)點集合。 先將V中的帶有組播功能的結(jié)點集合D中的所有結(jié)點，以Dijkstra算法由圖G中的最短路構(gòu)造其完全圖Kn，E是邊(任兩組播結(jié)點之間的連接)的集合，邊權(quán)表示結(jié)點之間的“組播代價”，在此為圖G中兩點間的最短路。 完全圖Kn的不同生成樹共有nn-2棵，正好可以用n-2位的n-進(jìn)制整數(shù)來表示，每位數(shù)字都在[1..n]之間，它對應(yīng)為Kn的節(jié)點編號，這就是Prüfer編碼，它為設(shè)計基于生成樹的優(yōu)化問題的遺傳算法提供了最簡潔的編碼方案之一。由Prüfer序列到生成樹T的解碼算法seqToTree如下：  算法1   seqToTree [算法開始] 輸入：Prüfer編碼序列P； 輸出：Kn的生成樹T； [算法開始] 確定節(jié)點數(shù)n:=P的長度+2； 統(tǒng)計每個節(jié)點在P中的出現(xiàn)次數(shù)A[1..n]； 生成具有n個孤立節(jié)點的圖T,節(jié)點依次標(biāo)記為1,2,…,n； 令Q為T的所有不在P中的節(jié)點編號集合,并非減有序； 當(dāng)P非空，循環(huán)做 從P中移出第一個元素v, 從Q中移出第一個元素u, A[v]:=A[v]-1； 在T中增加邊<v,u>； 如果A[v]=0, 則折半插入v到Q中； 從Q中移出最后兩個元素v和u, 在T中增加邊<v,u>； 輸出T. [算法結(jié)束] 由于Prüfer編碼代表的生成樹是無序樹（不指定根），而組播樹需要指定根，所以我們擴充Prüfer編碼為n-1位，最后一位代表根節(jié)點編號。另外，還需要對解碼得到的Kn的生成樹進(jìn)行剪枝，刪除不在組播終點集D中的葉子節(jié)點才能得到所求的組播樹，剪枝算法prune的設(shè)計見如下： 算法2   prune 輸入：Kn的生成樹T,組播終點集合D; 輸出：組播樹T； [算法開始] 對T做后根次序遍歷,一邊遍歷一邊做： a)如果當(dāng)前被遍歷節(jié)點v是葉子節(jié)點并且不在D中,則: 從T中刪除v； 輸出T. [算法結(jié)束] 遺傳算法設(shè)計： 遺傳算法基于達(dá)爾文進(jìn)化論的思想，將待求問題的解空間看成自然界，將解空間中的每個變量的目標(biāo)函數(shù)值看成個體對環(huán)境的適應(yīng)性，然后通過（自然）選擇、交叉、變異等遺傳操作不斷進(jìn)化，在一個可以接受的時間內(nèi)到達(dá)一代比較優(yōu)秀的種群，其中包含了我們要求的最優(yōu)或近似最優(yōu)個體。 一個特定的遺傳算法主要由染色體編碼、種群初始化、適應(yīng)值標(biāo)定和遺傳算子（選擇、交叉和變異）設(shè)計等方面組成�；�于前面的討論，我們設(shè)計了求解模型的遺傳算法：染色體用擴充的Prüfer編碼表示；給定具有n個節(jié)點的網(wǎng)絡(luò)G和種群規(guī)模P后，初始種群由隨機生成的P行n-1列的矩陣表示，其中的每個元素為[1..n]之間的整數(shù)，代表G中的節(jié)點編號；計算每個染色體（Prüfer序列）的適應(yīng)值時，依次用算法seqToTree和prune得到組播樹T，通過計算該個體的優(yōu)化目標(biāo)值g，再對g做標(biāo)定得到個體適應(yīng)值f=1/(1+g)；選擇算子采用改進(jìn)的一次旋轉(zhuǎn)賭輪方法；交叉算子采用隨機多點交叉；變異算子采用基因位變異和基因片變異（包括遷移和翻轉(zhuǎn)）；保優(yōu)策略，即每代最優(yōu)秀個體直接進(jìn)入下一代而不參與交叉和變異。  算法復(fù)雜性分析： 從算法中可以看出，對每一染色體解碼求生成樹的復(fù)雜度為O(nlogn)，對生成樹進(jìn)行剪枝得到組播分布樹的算法復(fù)雜度為O(n)；而對得到的組播樹進(jìn)行優(yōu)化目標(biāo)值計算和適應(yīng)值標(biāo)定所需要的復(fù)雜度可以從如下方面分析： 根據(jù)Dijkstra的算法，計算每對節(jié)點間最短路徑需要O(n3)的復(fù)雜度。但是，我們注意到是在給定的組播樹T中，若求解的是有源樹，給定組播源點s后，對任意的d，計算節(jié)點對(s,d)之間的距離時只需從s出發(fā)對T做一次遍歷即可，復(fù)雜度為O(n)；若計算的是共享樹，則對任意的組播源點s，組播信息都是先從s通過第一跳單播到共享根，再從共享根到達(dá)每個組播終點d，所以計算節(jié)點對(s,d)之間的距離時也只需從共享根出發(fā)對T做一次遍歷，復(fù)雜度也為O(n)；   交叉算子和變異算子的復(fù)雜度均不超過O(n)； 于是，給定群規(guī)模P和最大進(jìn)化代數(shù)maxG，該算法的計算復(fù)雜度為O(P×maxG×O(mlogm))式中m為組播功能結(jié)點數(shù)，相對于求解同類問題的其它算法而言，這個結(jié)果確實令人鼓舞。所有利用遺傳算法求解組播路由問題的算法都需要進(jìn)行優(yōu)化目標(biāo)值的計算和適應(yīng)值標(biāo)定，以上的設(shè)計實現(xiàn)了一種更快的求解全組播網(wǎng)絡(luò)組播路由問題的遺傳算法。然而，應(yīng)該注意的是，Prüfer數(shù)表示的是Kn的生成樹，而不是給定網(wǎng)絡(luò)G(V,E),|V|=n的生成樹；組播數(shù)T也不是G的生成樹，而是針對組播源點集S和組播功能結(jié)點集MV的steiner樹。在求得最優(yōu)解后，需要將得到的組播樹按圖G中的最短路展開，并對相同路作歸并操作。以此才能得到所求部分組播網(wǎng)絡(luò)組播生成樹的“樹核”。如圖1.   圖1　覆蓋層組播“樹核”生成 4.2　PRRH-N結(jié)點動態(tài)加入算法： [算法開始]    1)以部分組播網(wǎng)絡(luò)基于網(wǎng)絡(luò)費用最優(yōu)的靜態(tài)組播樹生成算法先生成動態(tài)組播樹的“樹核”T。 2)當(dāng)新的一個結(jié)點Di要加入組播組時，先計算其到“樹核”T中各組播結(jié)點MVi(其取值范圍是MVS集合的成員)的最短路。 3)比較此結(jié)點Di到源s的最短路近還是到離它最近的組播結(jié)點MVi的最短路近，如到源近直聯(lián)到源。在樹中加入結(jié)點Di及其到源的邊。 4)如到最近的MVi近，則檢查此MVi是否已是組播組內(nèi)成員(本身是端結(jié)點或有別的結(jié)點通過此組播功能結(jié)點接入組播組)，如是，以此MVi結(jié)點為“登陸結(jié)點”接入組播組(如有兩個結(jié)點滿足要求，選擇距s近的那一MV結(jié)點)。樹中加入結(jié)點Di及其到此MVi結(jié)點的邊 5)如最近的MVi結(jié)點還不是組內(nèi)結(jié)點，則向它注冊, 并告之此Di到它的最短路是多少及到源的最短路是多少，同時計算所有向此結(jié)點注冊的結(jié)點經(jīng)它連入組播樹的費用和是否小于直連源的費用和，如是所有注冊結(jié)點由其連入組播樹，反之計算此Di到“樹核”T上各組播功能結(jié)點MVi及MVi到源s的最短路徑的值,找到T中含有組播結(jié)點MVi的到源s的最短路Pmin，比較此結(jié)點Di到源s的最短路近還是到擁有Pmin的組播結(jié)點MVi的最短路近，如到源近直聯(lián)到源。在樹中加入結(jié)點Di及其到源的邊。 6)反之，選擇此擁有Pmin的組播結(jié)點MVi作為此結(jié)點的“登陸結(jié)點”連入組播組(如有多點滿足要求，選擇距s遠(yuǎn)的那一MV結(jié)點)。并在組播樹中加入Pmin邊。 [算法結(jié)束] 如圖2.       圖2. PRRH-N結(jié)點動態(tài)加入算法 4.3　PRRH-N結(jié)點動態(tài)退出算法： [算法開始] 1)如果此結(jié)點是直聯(lián)到源的，且路徑中沒有別的組內(nèi)成員，則將路中所有的結(jié)點從樹中刪除。并在距此點最近的MVi結(jié)點注消此結(jié)點 2)如果此結(jié)點是直聯(lián)到源的，但路徑中還有別的組內(nèi)成員，則將此結(jié)點刪除直到另一組內(nèi)成員成為葉子結(jié)點為止。在距此點最近的MVi結(jié)點注消此結(jié)點的同時，注消新的葉子結(jié)點，并對這一剛成為葉子結(jié)點的組內(nèi)成員用動態(tài)結(jié)點加入算法重新加入組播組。 3)如果此結(jié)點是聯(lián)到“樹核”T中的組播功能結(jié)點MVi上的，且MVi上還連著其它的組內(nèi)成員，在刪除此結(jié)點的同時，要計算所有經(jīng)此MVi結(jié)點連入組播組的結(jié)點至源s的費用總和是否大于其向源直聯(lián)的費用總和。如是注消這些結(jié)點，并用動態(tài)結(jié)點加入算法將這些結(jié)點重新加入組播組。 [算法結(jié)束]                           5 MON動態(tài)組播路由算法PRRN-D 目的地費用最優(yōu)路由算法是用來優(yōu)化路由的目的地費用。如果是點到點通信，那么目的地費用最優(yōu)也就是網(wǎng)絡(luò)費用最優(yōu)。但在多點通信中，兩者并不等價。在點到多點通信中，可以先計算源到每個目的結(jié)點的費用最優(yōu)路徑。然后將這些路徑合并(全組播網(wǎng)絡(luò))。路徑中相同的鏈路可以被共享。形成的路由樹稱為目的地費用最優(yōu)組播路由樹。雖然目的地費用最優(yōu)組播路由樹的網(wǎng)絡(luò)費用不一定是最優(yōu)的，但可以推測它的網(wǎng)絡(luò)費用至少不會太差。并且目的地費用最優(yōu)路由樹的網(wǎng)絡(luò)費用與目的結(jié)點加入或離開通信組的先后次序無關(guān)，這對于動態(tài)路由的優(yōu)化是有益的。因此目的地費用最優(yōu)路由算法也可以在多點動態(tài)路由中優(yōu)化網(wǎng)絡(luò)費用。 5.1 PRRH-D覆蓋層組播“樹核”生成算法  MON中具有組播功能的節(jié)點亦可依據(jù)目的地費用最優(yōu)的思想，以啟發(fā)的方法高速構(gòu)成PRRN－D覆蓋層組播“樹核”。其算法如下： [算法開始] 1)選擇組播功能結(jié)點集合MVS的成員，各組播功能結(jié)點先對組播源點s以Dijkstra算法最短路尋路，然后執(zhí)行“歸并操作”即合并相同邊，“歸并操作”后的組播樹即為我們所要求的部分組播網(wǎng)絡(luò)組播樹的“樹核”。 2)對“歸并操作”后的組播結(jié)點“樹核”，計算每一個組播結(jié)點到源s的路徑長度，并寫入各組播結(jié)點的路由表。 [算法結(jié)束] 5.2　PRRH-D結(jié)點動態(tài)加入算法： [算法開始] 1)以部分組播網(wǎng)絡(luò)基于目的地費用最優(yōu)的靜態(tài)組播樹生成算法先生成動態(tài)組播樹的“樹核”T。 2)當(dāng)新的一個結(jié)點Di要加入組播組時，先計算其到“樹核”T中各組播結(jié)點MVi(其取值范圍是MVS集合的成員)的最短路。 3)比較此結(jié)點Di到源s的最短路近還是到離它最近的組播結(jié)點MVi的最短路近，如到源近直聯(lián)到源。在樹中加入結(jié)點Di及其到源的邊。 4)如到最近的MVi近，則檢查此MVi是否已是組播組內(nèi)成員(本身是端結(jié)點或有別的結(jié)點通過此組播功能結(jié)點接入組播組)，如是，以此MVi結(jié)點為“登陸結(jié)點”接入組播組(如有兩點滿足要求，選擇距s近的那一MV結(jié)點)。樹中加入結(jié)點Di及其到此MVi結(jié)點的邊 5)如最近的MVi結(jié)點還不是組內(nèi)結(jié)點，則向它注冊, 并告之此Di到它的最短路是多少及到源的最短路是多少，同時計算所有向此結(jié)點注冊的結(jié)點經(jīng)它連入組播樹的費用和是否小于直連源的費用和，如是所有注冊結(jié)點由其連入組播樹，反之計算此Di到“樹核”T上各組播功能結(jié)點MVi及MVi到源s的最短路徑的值,找到T中含有組播結(jié)點MVi的到源s的最短路Pmin，比較此結(jié)點Di到源s的最短路近還是到擁有Pmin的組播結(jié)點MVi的最短路近，如到源近直聯(lián)到源。在樹中加入結(jié)點Di及其到源的邊。 6)反之，選擇此擁有Pmin的組播結(jié)點MVi作為此結(jié)點的“登陸結(jié)點”連入組播組(如有兩點滿足要求，選擇距s遠(yuǎn)的那一MV結(jié)點)。并在組播樹中加入Pmin邊。 [算法結(jié)束] 5.3　PRRH-D結(jié)點動態(tài)退出算法： [算法開始] 1)如果此結(jié)點是直聯(lián)到源的，且路徑中沒有別的組內(nèi)成員，則將路中所有的結(jié)點從樹中刪除。并在距此點最近的MVi結(jié)點注消此結(jié)點 2)如果此結(jié)點是直聯(lián)到源的，但路徑中還有別的組內(nèi)成員，則將此結(jié)點刪除直到另一組內(nèi)成員成為葉子結(jié)點為止。在距此點最近的MVi結(jié)點注消此結(jié)點的同時，注消新的葉子結(jié)點，并對這一剛成為葉子結(jié)點的組內(nèi)成員用動態(tài)結(jié)點加入算法重新加入組播組。 3)如果此結(jié)點是聯(lián)到“樹核”T中的組播功能結(jié)點MVi上的，且MVi上還連著其它的組內(nèi)成員，在刪除此結(jié)點的同時，要計算所有經(jīng)此MVi結(jié)點連入組播組的結(jié)點至源s的費用總和是否大于其向源直聯(lián)的費用總和。如是，則注消這些結(jié)點，并用動態(tài)結(jié)點加入算法將這些結(jié)點重新加入組播組。 [算法結(jié)束] 以上算法參見圖畫3. 圖3　覆蓋層組播“樹核”生成及節(jié)點動態(tài)加入、退出舉例 6 兩種算法復(fù)雜度及網(wǎng)絡(luò)模擬 PRRH-D算法：其組播結(jié)點樹核生成時，采用的是Dijkstra算法，然后對各組播結(jié)點向源結(jié)點s所尋到的最短路進(jìn)行歸并，設(shè)其MV結(jié)點數(shù)為m，網(wǎng)絡(luò)規(guī)模即網(wǎng)絡(luò)中總的結(jié)點數(shù)為n，則其樹核生成最壞情況下時間復(fù)雜度為 。而各終端結(jié)點加入組播組時每一結(jié)點最壞情況下要調(diào)用Dijkstra算法三次，分別對源結(jié)點s及樹核內(nèi)距終端結(jié)點Di最近的MV結(jié)點和具有P(Di,MVi,s)min的MV結(jié)點尋最短路，最壞情況下，每一終端結(jié)點最終加入組播組的時間復(fù)雜度為。PRRH-D算法的每一結(jié)點退出操作的最差情況的時間復(fù)雜度為，t為組播樹中所含的結(jié)點數(shù)，而因此而選擇重新選路的各終端結(jié)點需再次調(diào)用Dijkstra算法三次，如這部分結(jié)點數(shù)為r,則最壞情況下，這部分終端結(jié)點最終加入組播組的時間復(fù)雜度為。 PRRH-N算法屬于源路由算法(source-rooted routing)。源路由算法的結(jié)點經(jīng)某一路由協(xié)議(如鏈路狀態(tài)協(xié)議)獲得完整的網(wǎng)絡(luò)拓樸信息。網(wǎng)絡(luò)中每一結(jié)點的拓樸信息是一樣的，所以網(wǎng)絡(luò)中每一結(jié)點都可以接受用戶呼叫并進(jìn)行路由計算。假設(shè)網(wǎng)絡(luò)狀態(tài)信息在算法執(zhí)行之前已經(jīng)完成，且在算法計算路由時，網(wǎng)絡(luò)的拓樸狀態(tài)不變。則NCH及DCH算法的時間復(fù)雜度的計算就可以分為兩個獨立的兩個部分(組播結(jié)點樹核的生成及終端結(jié)點最終完成加入組播組)來計算，綜述如下： 其組播組結(jié)點樹核生成時，首先要以組播功能結(jié)點間的最短路生成其全連通網(wǎng)絡(luò)。采用Dijkstra算法，各組播結(jié)點及源結(jié)點s間彼此最短路尋徑，設(shè)其MV結(jié)點數(shù)為m，網(wǎng)絡(luò)規(guī)模即網(wǎng)絡(luò)中總的結(jié)點數(shù)為n，則組播功能結(jié)點全連通網(wǎng)絡(luò)生成在最壞情況下時間復(fù)雜度為。而樹核生成的遺傳算法和seqToTree算法的時間復(fù)雜度為O(P×maxG×O(mlogm))。同樣每一終端結(jié)點加入組播組時每一結(jié)點最壞情況下要調(diào)用Dijkstra算法三次，分別對源結(jié)點s及樹核內(nèi)距終端結(jié)點Di最近的MV結(jié)點和具有P(Di,MVi,s)min的MV結(jié)點尋最短路，最壞情況下，每一終端結(jié)點最終加入組播組的時間復(fù)雜度為。PRRH-N算法的每一結(jié)點退出操作的最差情況的時間復(fù)雜度為，t為組播樹中所含的結(jié)點數(shù)，而因此選擇重新選路的各終端結(jié)點需再次調(diào)用Dijkstra算法三次，如這部分結(jié)點數(shù)為r,則最壞情況下，這部分終端結(jié)點最終加入組播組的時間復(fù)雜度為。 由于兩種算法都采用了分布式觸發(fā)的思想，無需覆蓋層對整體的費用做出監(jiān)控及評價，故而從基礎(chǔ)解決了原觸發(fā)重組費用優(yōu)化方案的缺點，減輕了路由優(yōu)化的復(fù)雜性和額外開銷。 目前對于MON網(wǎng)絡(luò)動態(tài)組播樹的生成算法，還沒有研究人員進(jìn)行過系統(tǒng)的研究，因此也還沒有基準(zhǔn)算法來用于網(wǎng)絡(luò)模擬和比較。因此，本文的網(wǎng)絡(luò)模擬只能采用課題組MON靜態(tài)組播樹生成算法NCH來作為模擬基準(zhǔn)。 · 圖4  PRRH-N，PRRH-D算法EAD仿真網(wǎng)絡(luò)模擬數(shù)據(jù) 本文以課題組EAD仿真模型所生成的模擬網(wǎng)絡(luò)來做模擬平臺，在EAD算法生成的模擬網(wǎng)絡(luò)過程中，其MV結(jié)點比例是固定的(17%)，而長短邊之比隨著不同的需求，通過對 及F2的調(diào)節(jié)，也可以被定位于一很小的領(lǐng)域內(nèi)，所以在同一網(wǎng)絡(luò)規(guī)模前提下影響部分組播網(wǎng)絡(luò)動態(tài)組播樹生成算法的可變因素主要有：1.加入組播組的端結(jié)點的更新速度,2.在某一時刻，組播組成員數(shù)量在模擬網(wǎng)絡(luò)的全部結(jié)點中所占的比例，對于這兩點，都可以以一個無量綱的概念，對不同的網(wǎng)絡(luò)規(guī)模進(jìn)行一致的模擬，以利于后期實驗結(jié)果的比較。 本文采用以下假設(shè)：加入組播組的端結(jié)點以一種穩(wěn)定的速度進(jìn)行更新，即某一時刻有占網(wǎng)絡(luò)結(jié)點總數(shù)5%的組播組成員退出組播組，而另有占網(wǎng)絡(luò)結(jié)點總數(shù)5%的非組播組成員加入組播組，而初始狀態(tài)選擇組播組成員占總結(jié)點數(shù)的20%和40%來進(jìn)行模擬。這樣就有可能選擇相同的靜態(tài)部分組播網(wǎng)絡(luò)組播樹生成算法來作為待模擬算法的基準(zhǔn)算法，以便能從本質(zhì)上把握待模擬算法的一些基本特征，并給出其性能評價。 由模擬數(shù)據(jù)可知(見圖4)，PRRH-N和PRRH-D算法因為可以在結(jié)點加入組播組及結(jié)點退出組播組時都能觸發(fā)樹結(jié)構(gòu)的部分重組。所以其費用能夠被限定在基準(zhǔn)以上的一個很小的區(qū)域內(nèi)，因為考慮到現(xiàn)實網(wǎng)絡(luò)中的實現(xiàn)問題，兩種算法都沒有終端結(jié)點向上歸并的操作，所以，實驗中可見費用會出現(xiàn)“躍點”，特別是當(dāng)組播組成員比例相對較小時，這一點表現(xiàn)的尤為突出。在組播組成員比例進(jìn)一步增加時，兩種算法都表現(xiàn)出很好的收斂性，而且其費用的統(tǒng)計平均值也均被限定在不高于基準(zhǔn)的10%，這一結(jié)果還是非常令人鼓舞的。 7  結(jié)束語 PRRH-N算法在費用優(yōu)化方面是兩種算法中最優(yōu)的，基于結(jié)點費用最優(yōu)觸發(fā)重組操作，能最大限度的減小算法的散列躍度，算法收斂性能夠有一個很好保證，但時間復(fù)雜度整體來說過大，在實際應(yīng)用中，可操作性要明顯低于PRRH-D算法。但在組播組成員相對較少時，對費用優(yōu)化苛刻的前提下，該算法還是應(yīng)該成為首選的。 PRRH-D算法在時間復(fù)雜度方面較PRRH-N算法為優(yōu)，而其網(wǎng)絡(luò)費用優(yōu)化又明顯的線性逼近 PRRH-N算法，在組播組成員比例達(dá)到40%左右時，該算法的費用優(yōu)化性能已近似等于PRRH-N算法， 故在對算法計算時間及費用優(yōu)化都有較高要求時，還是選用PRRH-D算法為好。 因兩種算法都是基于“樹核”的，所以兩種算法都可以在一定路由協(xié)議的支持下進(jìn)行多面體分級路由模式的改良，也可以方便的向多點對多點組播路由算法改進(jìn)，這樣就能夠使算法在可擴展性方面有一個質(zhì)的提高，同時也可以使其向多點對多點路由計算提供良好的支持。其次，基于“樹核”的路由方式，也可以在鏈路負(fù)載平衡方面較原有的CBT算法(原針對全組播網(wǎng)絡(luò)的一種多對多組播路由算法)有一個質(zhì)的提高。以上方案都將是今后對于部分組播網(wǎng)絡(luò)路由算法研究的很好的方向。 參考文獻(xiàn) [1]   董慶陽,  計算機通信網(wǎng)絡(luò)組播路由算法和協(xié)議的研究, 上海交通大學(xué)博士學(xué)位論文, 2000年 [2]   王征應(yīng),  高速網(wǎng)絡(luò)QOS路由技術(shù)的研究及路由仿真平臺的研制, 華中科技大學(xué)博士學(xué)位論文, 2001年 [3]   李漢兵, 計算機網(wǎng)絡(luò)路由算法, 西安電子科技大學(xué)博士學(xué)位論文, 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 劉克儉 余鎮(zhèn)危  竇巍 （中國礦業(yè)大學(xué)研究生院，北京，100083） 摘要：本文在分析研究主動應(yīng)用的基礎(chǔ)上，針對應(yīng)用層主動網(wǎng)絡(luò)節(jié)點對費用的影響，提出了一個新的費用模型，并基于此模型設(shè)計了一個靈活的主動路由算法。實驗證明此算法具有高效性和可擴展性，在大規(guī)模網(wǎng)絡(luò)環(huán)境下也表現(xiàn)出很高的可用性。 關(guān)鍵詞：應(yīng)用層主動網(wǎng)絡(luò)，移動代理，服務(wù)位置，主動路由算法 中圖分類號：TP393　　　文獻(xiàn)標(biāo)識碼：A 引言 當(dāng)前為了解決傳統(tǒng)計算機網(wǎng)絡(luò)體系結(jié)構(gòu)面臨的困難，研究界提出了應(yīng)用層主動網(wǎng)絡(luò)的思想[2][6]。應(yīng)用層主動網(wǎng)絡(luò)就是在現(xiàn)有的網(wǎng)絡(luò)基礎(chǔ)之上建立一個虛擬網(wǎng)絡(luò)用來支持原有網(wǎng)絡(luò)沒有提供的分組處理功能。它的主要優(yōu)點是不需要整個網(wǎng)絡(luò)范圍內(nèi)的網(wǎng)絡(luò)組件的支持，加快了所需網(wǎng)絡(luò)功能和服務(wù)的部署，并且由于支持不同的服務(wù)功能的多個應(yīng)用層主動網(wǎng)絡(luò)可以共存，也增加了其靈活性。由此，應(yīng)用層主動網(wǎng)絡(luò)的提出迅速成為主動網(wǎng)絡(luò)研究的分支。 為了在應(yīng)用層主動網(wǎng)絡(luò)上支持用戶的對多樣服務(wù)的需求，需要在應(yīng)用層主動網(wǎng)絡(luò)上選擇合理的位置注入特定的服務(wù)（如壓縮、處理、緩存、重新編碼等）來為用戶服務(wù)[1]，我們稱之為proxy[6]。如何優(yōu)化服務(wù)位置是本文考慮的主要問題。首先給出了適合應(yīng)用層主動網(wǎng)絡(luò)的費用模型；其次提出并抽象應(yīng)用層主動網(wǎng)絡(luò)中的服務(wù)位置問題；最后給出算法解決該問題并對算法的特性進(jìn)行了驗證。 2　應(yīng)用層主動網(wǎng)絡(luò)上的費用模型 2.1傳統(tǒng)網(wǎng)絡(luò)費用模型的不適應(yīng) 目前的Internet形成了基本的費用模型，包括接納控制、路由和資源預(yù)留等方面�？偟膩砜�，費用包括節(jié)點對負(fù)載進(jìn)行分類交換、排隊和調(diào)度的費用，以及傳輸?shù)较乱粋�節(jié)點的傳輸費用。當(dāng)前Internet的實際證明，這一模型是高效和魯棒的，并依賴這一模型設(shè)計了許多有效的協(xié)議，比如“最短路徑路由”就是基于此費用模型，尋找在源與目的之間的一條路由，使得每跳的費用之和最小。 但是，以上所有協(xié)議的設(shè)計都是只限于被動網(wǎng)絡(luò)。在帶服務(wù)的應(yīng)用層主動網(wǎng)絡(luò)中，則不僅僅需要一般的傳輸資源，而且必須滿足中間結(jié)點對流的處理。這種情況下，路由的費用包括了結(jié)點的處理費用（壓縮、處理、緩存、重新編碼等），而且因為傳輸過程中隨著流的屬性的變化（如重新編碼、混合），也在不斷影響后續(xù)傳輸?shù)馁M用，因此在應(yīng)用層主動網(wǎng)絡(luò)中路由成為了一個非常有挑戰(zhàn)性的問題。 2.2 應(yīng)用層主動網(wǎng)絡(luò)應(yīng)用的一個例子 圖 1 主動壓縮費用變化 為了避免擁塞控制，比如可以利用proxy進(jìn)行數(shù)據(jù)的壓縮，節(jié)省proxy到用戶的帶寬。proxy與server之間的流速率將大于proxy與client之間的數(shù)據(jù)流 ，用ri表示這個變化的比率。在該例子中，費用模型需要考慮壓縮代價和由于壓縮考慮流量的變化。 如下所示分別標(biāo)注了鏈路費用和節(jié)點費用。在節(jié)點注入主動壓縮proxy之后增加了節(jié)點處理費用，并對后續(xù)的費用（節(jié)點和邊）產(chǎn)生了影響。很明顯，傳統(tǒng)的最短路徑算法（如Dijkstra算法）應(yīng)用于以上模型是無效的，無法計算出的最優(yōu)費用的路徑，如下例子可以說明。假設(shè)主動節(jié)點c、d壓縮率0.5。 圖2  傳統(tǒng)的路由算法的不適應(yīng)性 結(jié)果，Dijkstra算法由于不計節(jié)點費用，求出路徑（a-b-d-g）費用為50（20+10+20）；在各節(jié)點分別注入proxy，考慮主動節(jié)點的壓縮率和費用，計算出最短路徑（a-c-d-g）費用為25.25（20*0.5+3+13*0.5+2+8.5*0.5），優(yōu)于Dijkstra算法。當(dāng)然，某些主動服務(wù)有可能使費用增加，而不是減少，比如主動加密，但由于中間節(jié)點產(chǎn)生費用導(dǎo)致總體費用的變化，所以仍然不能使用傳統(tǒng)的路由算法。 因此，得出結(jié)論，采用常規(guī)的最短路徑算法在某些主動應(yīng)用場合失效（不是所有場合），需要尋找最優(yōu)的路由算法。 2.3 應(yīng)用層主動網(wǎng)絡(luò)的費用模型 主動服務(wù)節(jié)點的處理代價 ，對經(jīng)歷該主動節(jié)點的流的影響比率為，流經(jīng)過的鏈路帶寬代價為。 主動網(wǎng)絡(luò)       （1） 被動網(wǎng)絡(luò)             （2） 設(shè)共有n節(jié)點，節(jié)點k為要研究的對象，引入主動計算，因此主動網(wǎng)絡(luò)總費用為： =   = =                （3） 引入proxy之后，主動流經(jīng)過k節(jié)點發(fā)生改變，因此k之后的費用也發(fā)生變化，因此對后續(xù)節(jié)點費用也產(chǎn)生影響，我們用 表示這種變化。 （4） 3　服務(wù)位置問題 首先把問題抽象，網(wǎng)絡(luò)模型可表示為帶權(quán)圖 ，是主動節(jié)點的集合，是邊（表示節(jié)點之間的連接）的集合，為提供裝載proxy服務(wù)的中間處理節(jié)點的集合（節(jié)點或者子網(wǎng)），每一條邊的費用為；主動節(jié)點的節(jié)點處理費用為 。有一個源節(jié)點s，一個目的節(jié)點d，中間至少包括一個主動節(jié)點r裝入proxy。我們的目標(biāo)是找到從s到d最小費用的邏輯路徑，以及裝載proxy的位置r。這條邏輯路徑的費用包括鏈路費用總和、路徑中proxy主動節(jié)點的費用。 目的是求上述條件下的路由算法，計算出在哪些位置注入proxy或注入多少個proxy組成的路徑的費用是最優(yōu)的。如果 表示節(jié)點i對流的影響，Ai表示流速率（單位帶寬），即有： f為最小的費用函數(shù)，Ci表示節(jié)點執(zhí)行主動計算的費用，在每一次使用主動計算與是否執(zhí)行主動計算相關(guān)，并且對后續(xù)流量是有影響的，根據(jù)流量變化不斷乘上變化因子 .。 4　算法描述 假設(shè)事先獲得了邏輯域內(nèi)網(wǎng)絡(luò)的拓?fù)洌�類似于OSPF鏈路狀態(tài)協(xié)議），首先我們說明了如何解決一個proxy的位置問題，其次擴展到多個proxy的情形。 4.1網(wǎng)絡(luò)中唯一proxy的路由 先看簡單的情形，假設(shè)在網(wǎng)絡(luò)中只有一個proxy，尋找注入這個proxy的位置，其余中間節(jié)點則仍是被動的。首先，復(fù)制一份原始拓?fù)鋱D，形成兩層，如圖3所示。對于每個節(jié)點 ，都有可能裝入proxy，因此，在兩層中增加了若干有向邊(r0,r1)，令這些邊的費用等于節(jié)點r的費用C(r)。構(gòu)成的新圖中的源點為s，目的點則不再是d，而是1層的d1點。 主動路徑的問題即可轉(zhuǎn)化為：求0層的s到的1層的d1的一條不計節(jié)點費用的最短路徑。所以可以使用一般的最短路徑算法，計算好的這條路徑跨越兩層，合并之后即是原圖的最小費用的路徑。     圖3 單個proxy的主動路由方法 容易證明這一方法的正確性。我們求得從s到d1的最小費用路徑 , 在原圖有一條路徑相對應(yīng)，且費用相同。假設(shè)原圖另有一條費用更低的路徑，那么在展開圖也有一條與之對應(yīng)的s到d1的路徑，這條路徑費用則比我們求得的費用要低，因此矛盾。得證。 上一節(jié)公式（4）說明，主動節(jié)點處理后的主動流會引起后續(xù)路由的費用的變化，因此需要考慮帶寬變化因子的影響。設(shè)0層到1層的帶寬變化率為，解決辦法是，把0層到1層的費用乘上，再利用最短路徑算法求得。 路徑確定之后，proxy的位置也就相應(yīng)確定下來，路徑中跨越0層到1層的那個節(jié)點就是注入proxy的最合理的位置。 4.2 多proxy的路由和位置 （1） 網(wǎng)絡(luò)中只有1個proxy的算法可以擴展到多個proxy節(jié)點。 有n個可選的主動節(jié)點，則最多需擴展到n+1層。因此，如果在網(wǎng)絡(luò)中裝入k個proxy（ ），則復(fù)制后需排列為k+1層，類似于4.1問題轉(zhuǎn)化常規(guī)最短路徑問題，即求s到dk+1的邊的費用最低的路徑。 而且，仍然要考慮帶寬變化的影響。對于第i層的邊，邊的費用要乘上；從第i層到i+1層的邊的費用乘上。 （2）全局最短路徑 求原圖的任意數(shù)量的proxy構(gòu)成的最短路徑，實際上就是從1個proxy到n個proxy的情況都考慮一遍。在4.1的基礎(chǔ)上，我們可以得出 Pathmin = Min(Min(s,d),Min(s,d1)), …  Min(s,dn＋1))最短路徑即在所有0至n個proxy情況下求得的最短路徑中取最小值。 圖4 多個proxy的主動路由方法 （3）算法復(fù)雜性分析 網(wǎng)絡(luò)具有k個proxy，則分層圖包含 個節(jié)點，和條邊，求最短路徑的時間復(fù)雜度為。顯然，這種方法空間復(fù)雜度是隨著proxy數(shù)量的增加而線性增長的。 5　實驗驗證與結(jié)論 本論文在Intel Celeron 1.4GHZ ，256MRAM的微機上利用Sun Java（J2SDK1.4）語言編寫了上述算法程序。為了驗證仿真結(jié)果，網(wǎng)絡(luò)的拓?fù)鋱D生成使用了BRITE工具[3]，使用隨機化的方法產(chǎn)生具有實際網(wǎng)絡(luò)特性的圖的模型，實驗網(wǎng)絡(luò)的拓?fù)渖�成基于Waxman[4]的拓?fù)渖�成模型�?/P> 在我們的實驗和算法實施中，網(wǎng)絡(luò)有如下屬性：①邊的費用在[10,200]范圍上均勻分布。②中間處理節(jié)點的費用在[1,10 ]上均勻分布。③如果不特殊說明，則平均每個節(jié)點連接邊數(shù)m=5，α=0.15，β=0.2。 5.1   算法正確性的實驗驗證 圖5 一個簡單的主動路由算法的例子 根據(jù)圖5所示簡單網(wǎng)絡(luò)（節(jié)點費用為a0=1，b0=2，c0=1，d0=2，e0=1；λ=0.5），通過模擬程序求Dijkstra算法與主動路由算法結(jié)果如表1所示： 表1 λ=0.5，初始節(jié)點a0，終點e0的最短路徑 Active算法 Proxy數(shù)量 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情況相當(dāng)于Dijkstra算法的結(jié)論。 上述兩種算法計算的最短路徑結(jié)論是不同的。首先說明了在節(jié)點增加了主動計算費用之后，傳統(tǒng)路由算法不適合主動網(wǎng)絡(luò)。其次說明本文的主動路由算法的可以得出正確的結(jié)論，并可求出Proxy所在路徑上的位置。此實驗只是在一個給定的較小網(wǎng)絡(luò)拓?fù)渲械膶嶒�，目的是說明算法的正確性。 5.2 大規(guī)模網(wǎng)絡(luò)下算法特性的模擬實驗 （1）隨機拓?fù)涔?jié)點總量變化的影響。實驗統(tǒng)計了不同節(jié)點大規(guī)模節(jié)點總數(shù)的拓?fù)淝闆r，從大量的實驗數(shù)據(jù)中發(fā)現(xiàn)主動路徑上的Proxy數(shù)量集中在一定范圍內(nèi)。以所有節(jié)點作為起始點計算Proxy個數(shù)對應(yīng)的最短主動路徑數(shù)量分布，并取均值（取整數(shù)），得出可信的分布結(jié)果。如圖6所示： 圖6 大規(guī)模網(wǎng)絡(luò)下主動路徑數(shù)量分布 從圖中看出：實際網(wǎng)絡(luò)拓?fù)渲�，在最短主動路徑上部署的Proxy數(shù)量的分布集中在一個范圍內(nèi)。當(dāng)流量變化率λ=0.5時，這個范圍基本上在1至5個Proxy（包含起始節(jié)點本身）。這為我們大規(guī)模應(yīng)用這個算法提供了依據(jù)。在主動壓縮或主動緩存的應(yīng)用中，依據(jù)主動應(yīng)用的特點實際也不可能部署太多的Proxy，實驗恰恰說明了網(wǎng)絡(luò)中絕大多數(shù)節(jié)點使用較少的Proxy就可以達(dá)到主動最短路徑的要求。 （2）流量變化率λ對主動路由算法的影響 上述是對固定的流量變化率λ=0.5進(jìn)行的實驗；還需要考慮在不同λ值的條件下（λ<1和λ>1）的變化。λ表示執(zhí)行主動計算之后流量的變化率，λ<1表示主動計算使得流量的后續(xù)路徑費用減少，帶來減少帶寬的好處；但是，某些主動應(yīng)用利用主動計算改變流特性，不一定會有減少帶寬的好處（如重新編碼），所以用λ>1表示主動計算使流量的后續(xù)路徑費用增大。當(dāng)λ逐漸變大時，意味著主動計算的執(zhí)行使流向著增加帶寬費用的方向變化，λ>1變化對算法的效率和主動路徑數(shù)量分布產(chǎn)生如圖7所示的影響（節(jié)點總量為500）。 圖7 不同λ條件下（λ<1）的主動路徑數(shù)量分布 分析實驗結(jié)果，當(dāng)主動計算對流的改變程度變小時，即隨著λ增加，不用Proxy的路徑越來越多，使用Proxy的主動路徑的數(shù)量呈下降趨勢。從而得出結(jié)論，在λ<1時，λ越小則利用主動計算的價值就越大，反之則多數(shù)情況不必利用主動計算。所以，通過實驗進(jìn)一步驗證了本文費用模型合理性。當(dāng)λ等于1.0時是極限狀態(tài)，幾乎沒有路徑使用Proxy，主動路徑數(shù)量的分布曲線成為一條逼近于0的直線�？傊�，當(dāng)λ<1，λ越小則越適合（快速和普遍）用主動算法求解最短主動路徑和Proxy的位置。 其次，當(dāng)λ>1時，主動路由算法仍然是正確的。實驗表明隨著λ>1不斷增加，主動路徑分布出現(xiàn)不均勻的現(xiàn)象，各說明最短路徑使用Proxy數(shù)量的差異比較大。并且，當(dāng)λ>2.0之后的最短路徑數(shù)量分布隨著λ的變化是微小的，而且越來越逼近一個極值狀態(tài)。 （3）算法的執(zhí)行效率 主動算法的執(zhí)行時間主要考慮兩個方面：第一是計算層數(shù)k（即算法所限定的Proxy個數(shù)）對算法時間的影響是線性的，算法時間主要消耗在數(shù)據(jù)結(jié)構(gòu)的建立和復(fù)制上；第二是不同變化率λ的算法時間比較，當(dāng)拓?fù)淇偭繛?00，計算層數(shù)k=15不變的條件下，λ對算法所耗時間的影響如圖8所示。 圖8 算法時間隨λ的變化 最后，本文還對Waxman模型中的連接邊數(shù)、以及α和β參數(shù)值的變化進(jìn)行了實驗。發(fā)現(xiàn)，連接邊數(shù)m對主動路徑數(shù)量分布有較大影響，而α和β值對主動路徑數(shù)量分布的影響不敏感。 6. 結(jié)束語 主動網(wǎng)絡(luò)的費用模型不同于傳統(tǒng)網(wǎng)絡(luò)，沿用傳統(tǒng)的費用模型和路由算法將導(dǎo)致不正確的結(jié) 論。本文提出一種新的主動網(wǎng)絡(luò)費用模型考慮了數(shù)據(jù)流在主動節(jié)點環(huán)境中的執(zhí)行費用，并在此基礎(chǔ)上研究一種合理的主動路由算法，通過大量的模擬驗證，說明算法各個方面的特性，得出一些非常有價值的結(jié)論。 最后，需要說明的是本文只針對單服務(wù)主動路由算法進(jìn)行了研究，而在組播條件下和多服務(wù)約束條件下需要研究新的算法，比如利用遺傳算法和啟發(fā)式算法等。   參考文獻(xiàn)： 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            竇巍,余鎮(zhèn)危,潘耘.基于移動agent的應(yīng)用層主動網(wǎng)絡(luò).第六屆全國計算機應(yīng)用聯(lián)合學(xué)術(shù)會議.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

其它PDF論文列表：

A Chaotic Neural Network Algorithm for Task Scheduling

A Genetic Algorithm for the Overlay Multicast Routing Problem

Hierarchical Semantic Perceptron Net based Neural Network

On the Model of OoS Multicast Routing Problems in Active Networks

Overlay網(wǎng)絡(luò)上的服務(wù)部署問題的研究（一）

Overlay網(wǎng)絡(luò)上的服務(wù)部署問題的研究（二）

基于Overlay Network的網(wǎng)格虛擬端到端帶寬分配問題研究

拓?fù)涓兄�的分層對等Overlay網(wǎng)格架構(gòu)及其聚類算法研究

網(wǎng)絡(luò)流量行為分析的小波加權(quán)混沌局域模型

網(wǎng)絡(luò)體系結(jié)構(gòu)建模和性能評價的形式化方法

應(yīng)用層組播樹分裂恢復(fù)算法研究

支持QoS的覆蓋組播分布式動態(tài)路由研究