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

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

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

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

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

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

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

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

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