基于優(yōu)先度的應(yīng)用層組播協(xié)議

1、基于優(yōu)先度的應(yīng)用層組播協(xié)議基于優(yōu)先度的應(yīng)用層組播協(xié)議俞俊俞?。?980-），男，2003年獲浙江大學計算機學士學位, 現(xiàn)在浙江大學計算機系攻讀碩士學位。研究方向為分布式系統(tǒng)和應(yīng)用層組播。E-mail: yujun116.，陳嶺陳嶺（1977-），男，1999年獲浙江大學計算機學士學位，2004年獲浙江大學計算機博士學位?，F(xiàn)為浙江大學計算機系講師，研究方向為計算機支持協(xié)同工作和協(xié)同虛擬環(huán)境。，陳根才陳根才（1950-），男， 1973年獲杭州大學物理學士學位，現(xiàn)為浙江大學計算機系教授。研究方向為計算機網(wǎng)絡(luò)、數(shù)據(jù)庫和計算機支持協(xié)同工作。（1,2,3 浙江大學計算機科學與技術(shù)學院，杭州310027）

2、摘 要：本文提出了一種用于分布式虛擬環(huán)境的應(yīng)用層組播協(xié)議基于優(yōu)先度的應(yīng)用層組播。與之前提出的其他應(yīng)用層組播協(xié)議相比，它的優(yōu)勢在于將實體在虛擬環(huán)境中的優(yōu)先度作為構(gòu)建組播樹的參數(shù)之一，而別的應(yīng)用層組播協(xié)議僅僅考慮了網(wǎng)絡(luò)層因數(shù)。因此它更加適用于那些實體優(yōu)先度不同的應(yīng)用，例如：分布式虛擬環(huán)境（DVE）。通過仿真實驗得出：基于這種應(yīng)用層組播協(xié)議建出的組播樹在節(jié)點扇出和總帶寬利用率上都比單播方式高效。同時優(yōu)先度對建樹起到了指導作用，即優(yōu)先度大的實體，它到根節(jié)點的延時就小。由這幾點可以證明，基于優(yōu)先度的應(yīng)用層組播很好的滿足了DVE系統(tǒng)的特點。關(guān)鍵詞：優(yōu)先度；分布式虛擬環(huán)境；應(yīng)用層組播協(xié)議571. 引言近幾年

3、以來分布式虛擬環(huán)境得到了廣泛的應(yīng)用（DVE）。隨著用戶的不斷增多，研究者們將注意力集中到如何減少用戶獲得的無關(guān)數(shù)據(jù)。高層體系結(jié)構(gòu)1（HLA）是一種用來過濾無關(guān)數(shù)據(jù)的機制，它為每個發(fā)送實體建立發(fā)送區(qū)域，并由此建立發(fā)送組，以及對組中成員采用組播的方式發(fā)送信息。目前的HLA是采用了IP組播的方式來實現(xiàn)組播功能，這是一種目前廣泛采用的組播機制2（ALM）。但它同時存在不足，隨著用戶的增多，組播組必然增多，而IP組播一個很大的不足就是IP組播地址的缺乏。目前被提出用來取代IP組播的機制就是應(yīng)用層組播2。應(yīng)用層組播的目的是將組播功能在應(yīng)用層上實現(xiàn)，這樣就不需要在網(wǎng)絡(luò)層有特殊的硬件的支持。目前，已提出的AL

4、M體系有：ESM(End System Multicast)、ALMI(Application Level Multicast Infrastructure)、YOID(Your Own Internet Distribution)三種體系。ESM體系由CMU大學網(wǎng)絡(luò)實驗室提出，采用NARADA2協(xié)議。它針對的應(yīng)用是網(wǎng)絡(luò)視頻點播系統(tǒng)。它采用了兩步建樹過程：首先所有節(jié)點（已加入到系統(tǒng)中的節(jié)點）被連接成一個連通子圖，之后再由連通子圖生成最短路徑樹作為組播樹3。ALMI4由華盛頓大學提出，其設(shè)計的目的是通過應(yīng)用層組播實現(xiàn)分布式數(shù)據(jù)庫。它與NARADA不同之處在于它的多點發(fā)送。雖然也是采用了兩步建樹方

5、式，但卻是采用了最小生成樹作為所有節(jié)點的共享樹。ACIRI（AT&T Center for Internet Research at ICSI）研究中心提出的YOID5與前兩種不同，它采用了單步建樹的方式，同時還加入了避免循環(huán)產(chǎn)生機制。以上列出的應(yīng)用層組播協(xié)議只將網(wǎng)絡(luò)層因素（如帶寬，延時）作為建樹依據(jù)，它們僅適用于那些不存在節(jié)點優(yōu)先關(guān)系的應(yīng)用，例如視頻點播。在這些應(yīng)用中，所有節(jié)點都具有相同的優(yōu)先度。而分布式虛擬環(huán)境中的實體卻由于位置的不同而具有不同的優(yōu)先度。與狀態(tài)更新實體接近的節(jié)點需要更短的更新時間，這就需要在建樹過程中將實體的優(yōu)先度考慮進來。通過仿真實驗發(fā)現(xiàn)，本文提出的基于優(yōu)先度的應(yīng)

6、用層組播協(xié)議可以滿足DVE的建樹要求。2. 研究背景隨著網(wǎng)絡(luò)的發(fā)展，許多基于網(wǎng)絡(luò)的應(yīng)用被開發(fā)出來。這其中很多應(yīng)用需要用到組播，例如，網(wǎng)絡(luò)視頻會議，網(wǎng)絡(luò)聊天室，大規(guī)模網(wǎng)絡(luò)游戲等。而它們對組播的運用與當初設(shè)計IP組播的初衷有很大不同，這表現(xiàn)在：1. 這些應(yīng)用的組播規(guī)模較小，而IP組播是被設(shè)計進行大規(guī)模組播應(yīng)用的。2. 由于組播數(shù)目的增大，路由器需要保存和更新的路由表的數(shù)量增多了，這增大了路由器的負擔。所以針對這些應(yīng)用，研究者試圖設(shè)計出一種可以用來代替IP組播的機制。它可以更加靈活的實現(xiàn)組播功能。應(yīng)用層組播被設(shè)計出來代替IP組播進行小規(guī)模的組播。它有以下幾個特點：1. 它不需要特殊的硬件支持，一切都

7、是通過上層的軟件來實現(xiàn)。2. 它設(shè)計的應(yīng)用是小規(guī)模的組播應(yīng)用。其中ESM，ALMI和YOID(是三種具有代表性的體系。I、ESMESM具有以下幾大優(yōu)點： 從技術(shù)上來說，視頻點播系統(tǒng)需要發(fā)送節(jié)點有足夠的發(fā)送帶寬支持。連接的用戶越多則消耗的帶寬越大。當服務(wù)器的可用帶寬用盡時，則新用戶難以再加入到系統(tǒng)中。ESM系統(tǒng)允許通過轉(zhuǎn)發(fā)的方法來實現(xiàn)視頻點播，即用戶不直接從服務(wù)器獲取視頻數(shù)據(jù)，而是從別的用戶那里獲得。這種實現(xiàn)方式就是一種應(yīng)用層組播的方式。它可以降低服務(wù)器的帶寬利用。 在ESM系統(tǒng)中，不必考慮底層網(wǎng)絡(luò)的實現(xiàn)，而僅需要考慮如何更好的提高組播效率。ESM采用NARADA作為組網(wǎng)協(xié)議，它采用兩步建樹方式

8、： 第一步是建立連通子圖，它是建立在完全連通圖的基礎(chǔ)之上（complete virtual graph）。 第二步是采用最短路徑樹算法在連通子圖上建組播樹。NARADA建樹過程中采用了距離矢量路由算法6（Distance Vector Routing）。每一組成員都記錄了本節(jié)點到別的節(jié)點的最短路徑。II、ALMIALMI為所有的系統(tǒng)提供了控制節(jié)點，該節(jié)點負責組播樹的一致性和有效性。建樹和維護樹都由它完成。ALMI分為兩部分：控制節(jié)點和組成員?？刂乒?jié)點：它的任務(wù)是用來建樹和維護樹。它有以下功能： 若有成員離開或是加入時，它被用來維護組播樹的連通性。 它不斷接收鄰節(jié)點的更新信息，并且不斷的計算最小

9、生成樹以保證組播樹的連通性。組成員：它有以下功能： 它負責數(shù)據(jù)的接收和轉(zhuǎn)發(fā)。就好象IP組播中的路由器的作用。 它監(jiān)控周圍若干節(jié)點的狀態(tài)更新情況，并不斷的把更新信息傳給控制節(jié)點。它采用周期性探測的方式，即每隔一段時間發(fā)送一個探測包到鄰節(jié)點。ALMI 與NARADA 一樣采用兩步建樹的方式。不同處在于ALMI是利用了MST(Minimum Spanning Tree)的建樹策略。III、YOIDNARADA和ALMI的兩步建樹方式提供了建樹的穩(wěn)定性和最優(yōu)性。當有組播成員加入或離開時，它影響的僅僅是連通子圖，而組播樹不受影響。但兩步建樹也有缺點，那就是建樹的收斂時間慢，往往需要較長時間。這對于一些組

10、成員變化不大的應(yīng)用當然沒問題，一旦組變化頻率增大，就有可能造成抖動。YOID采用單步建樹方式來縮短建樹時間，同時，如何防止循環(huán)是其需解決的另一個關(guān)鍵問題。在YOID中有一個節(jié)點作為起始節(jié)點，任何新加入的組成員都到起始節(jié)點獲取鄰節(jié)點信息，然后再在這些鄰節(jié)點中選取一個作為父節(jié)點。YOID采用了單步建樹方式并且加入了防止循環(huán)產(chǎn)生的機制。3. 基于優(yōu)先度的應(yīng)用層組播 之前提出的三種應(yīng)用層組播協(xié)議僅僅是利用網(wǎng)絡(luò)層參數(shù)作為建樹依據(jù)。在這些協(xié)議中，每個節(jié)點的優(yōu)先度是相同的。在一些應(yīng)用中的確存在這樣的情況，例如：視頻點播，視頻會議等。但在其他一些應(yīng)用卻有不同的情況。如：大規(guī)模網(wǎng)絡(luò)游戲，大規(guī)模分布式仿真系統(tǒng)等。

11、節(jié)點在這些系統(tǒng)中由于所處位置不同而具有不同的優(yōu)先度。優(yōu)先度越大的實體則它收到的更新時間越短，也就意味著兩個節(jié)點之間的路徑越短。而當節(jié)點的優(yōu)先度小時，兩個節(jié)點之間的路徑不是最優(yōu)，協(xié)議會根據(jù)優(yōu)先度選擇合適的路徑給這兩個節(jié)點。3.1 基于優(yōu)先度的應(yīng)用層組播協(xié)議它在結(jié)構(gòu)上被分為兩部分：起始節(jié)點：在系統(tǒng)啟動的初級階段，選定一個節(jié)點作為起始節(jié)點，它的IP地址通過廣播的方式通知所有別的系統(tǒng)成員。這個節(jié)點一方面記錄分布式虛擬環(huán)境中所有實體的位置，并不斷更新它們的位置，另一方面根據(jù)這些實體的位置采用HLA機制，為每個有狀態(tài)更新的實體確定組播組。并把組播成員信息發(fā)送給這個狀態(tài)更新實體所在的節(jié)點。它本身不參與數(shù)據(jù)發(fā)

12、送，同時也不參與建樹過程。這樣做最大限度的保證了系統(tǒng)的穩(wěn)定性，一旦起始節(jié)點出現(xiàn)異常，也不會影響到整個系統(tǒng)的工作。僅僅是新的節(jié)點無法加入到系統(tǒng)中。發(fā)送節(jié)點：發(fā)送節(jié)點就是那些有狀態(tài)更新的實體所在的節(jié)點。這些節(jié)點負責組播樹的構(gòu)建，它們自身是樹的根節(jié)點。在建樹過程中，根據(jù)從起始節(jié)點收到的成員的優(yōu)先度來構(gòu)建組播樹。3.2 建樹的過程1. 首先由起始節(jié)點計算出組播組中成員的優(yōu)先度。在分布式虛擬環(huán)境中每個實體都具有兩個區(qū)域：碰撞區(qū)域和發(fā)現(xiàn)區(qū)域。當發(fā)送實體和接收實體之間距離小于發(fā)現(xiàn)區(qū)域的值時，則它進入到組播組中。實體優(yōu)先度的計算如下： 2. 當每個發(fā)送實體所在節(jié)點接收到組播成員信息和優(yōu)先度信息時，若實體的優(yōu)先

13、度等于1，則它進入到隊列1中；若是小于1，則進入到隊列2。采用兩個隊列的目的是為了方便的構(gòu)建出基于優(yōu)先度的組播樹。3. 若隊列1不為空，則所有隊列1中的實體所在節(jié)點直接連到發(fā)送節(jié)點上，而隊列2中的節(jié)點會選擇隊列1中的節(jié)點作為其父節(jié)點，這一選擇是周期性的。在此不考慮節(jié)點的帶寬承受能力。若隊列1為空，則隊列2中的節(jié)點會直接連接到發(fā)送節(jié)點上。這樣即充分考慮到了實體優(yōu)先度的作用，同時也充分利用了帶寬。隨著節(jié)點狀態(tài)的更新，以上算法會重復(fù)執(zhí)行，以保持組播樹的有效性。這種建樹方式的優(yōu)點是：1. 那些具有較高優(yōu)先度的節(jié)點會進入到隊列1中，因此在建樹中會直接連到發(fā)送節(jié)點上去。直連表示的路徑是最短的，也就是符合了

14、依靠優(yōu)先度建樹的思想。2. 組播樹的不會超過3層，同時又是單步建樹，所以建樹的時間要短于最小生成樹。3. 同YOID一樣，這里采用的是單步建樹。但有一點與YOID不同，它不需要循環(huán)檢測機制，這是由于每個節(jié)點都有優(yōu)先值的原因。同時優(yōu)先值大的不會成為優(yōu)先值小的子節(jié)點，所以不可能產(chǎn)生循環(huán)的情況。圖1給出了虛擬環(huán)境中實體的位置情況。其中A是狀態(tài)更新實體，而B、C、D在實體A的碰撞區(qū)域中，而E、F、G中實體A的發(fā)現(xiàn)區(qū)域中，所以B、C、D進入隊列1中，而E、F、G進入隊列2中。根據(jù)圖1 而構(gòu)建的組播樹見圖2。HEFGDABCColisionRegionObservationN Region圖1 實體在分布

15、式虛擬環(huán)境中的位置圖2 實體A的組播樹4. 仿真實驗設(shè)計4.1 拓撲圖設(shè)計采用Geog-Tech7的拓撲圖生成器產(chǎn)生出30個節(jié)點的拓撲圖。它被用來作為仿真實驗的主干網(wǎng)絡(luò)。同時30個工作站被假設(shè)連接到了這30個節(jié)點上，但不考慮連接帶來的延遲。所有網(wǎng)絡(luò)上的參數(shù)都是靜態(tài)的。通過拓撲圖生成器預(yù)先設(shè)定好，然后基于靜態(tài)的拓撲圖構(gòu)造出應(yīng)用層上的完全連同圖。采用的算法是最短路徑算法。4.2 分布式虛擬環(huán)境設(shè)計在虛擬環(huán)境中有30個實體，它們都有自身的運動速度和運動方向。這30個實體都有狀態(tài)更新，同時它們的碰撞區(qū)域和發(fā)現(xiàn)區(qū)域被設(shè)為相同的。當實體運動到了虛擬環(huán)境的邊界上的時候，它會反向以不變速度繼續(xù)運動。4.3 仿

16、真實驗中評價參數(shù)的設(shè)計兩種協(xié)議用在本仿真實驗中，分別為應(yīng)用層組播協(xié)議和單播協(xié)議。評價參數(shù)如下：1） 帶寬占用量帶寬占用量被分為兩部分統(tǒng)計。一部分統(tǒng)計根節(jié)點的扇出度，另一部分統(tǒng)計節(jié)點所有帶寬的占用，包括節(jié)點的扇出和扇入。它被用來測量帶寬的利用率。2） 組播樹的延時代表了組播組中實體的個數(shù)。是代表了根節(jié)點到任意節(jié)點的延時。3） 組播樹的優(yōu)先度是代表了樹中每個節(jié)點的優(yōu)先度。通過組播樹延時和組播樹優(yōu)先度可以反映出是否依據(jù)了優(yōu)先度建樹的方針。5. 仿真結(jié)果和分析圖3 和圖4 統(tǒng)計了兩部分帶寬。在圖3中X軸代表了所有在仿真過程中構(gòu)建出的組播樹。Y軸代表了根節(jié)點的扇出。這里扇出是指在一次仿真中所有組播樹根節(jié)

17、點的扇出的總和。由圖3 可以看出unicast中根節(jié)點的扇出要遠大于基于優(yōu)先度的應(yīng)用層組播的扇出。這表明基于優(yōu)先度的應(yīng)用層組播可以有效提高帶寬利用率。圖3 中有若干點上，根節(jié)點的扇出相同，這些點的出現(xiàn)是由于當隊列1為空時，則隊列2中的節(jié)點會直接連到根節(jié)點上，這會增大節(jié)點的扇出。但這種情況出現(xiàn)的很少。圖4 是從整體的角度來記錄帶寬利用率。節(jié)點的扇出和扇入都被記錄下來。目的是全面評價算法在帶寬利用上的表現(xiàn)。從圖4 中我們可以得出與圖3 幾乎相同的結(jié)論，這表明仿真實驗的數(shù)據(jù)是客觀真實的。也確實說明基于優(yōu)先度的應(yīng)用層組播協(xié)議可以有效降低帶寬。同時結(jié)合圖3 和圖4 來看，在圖的后半部分，曲線呈現(xiàn)出平穩(wěn)趨

18、勢，表明最后趨向于穩(wěn)定。圖3 根節(jié)點的扇出圖4 節(jié)點占用帶寬總和基于優(yōu)先度建立應(yīng)用層組播的主要目的是為了將優(yōu)先度結(jié)合進組播樹的構(gòu)建過程。通過圖5 看到，當優(yōu)先度變大時，通過應(yīng)用層組播可以有效降低組播樹的延時。反之當優(yōu)先度變小時，則組播樹的延時變大。這證明算法達到了預(yù)期的目的。同時圖6并沒有表現(xiàn)出這個趨勢。所以應(yīng)用層組播比單播更加適用于分布式虛擬環(huán)境。它滿足了分布式虛擬環(huán)境的要求。圖5 組播樹延時與其優(yōu)先度的比較圖6 單播樹的延時與其優(yōu)先度的比較6. 結(jié)束語本文提出了一種用于分布式虛擬環(huán)境的應(yīng)用層組播協(xié)議基于優(yōu)先度的應(yīng)用層組播，與之前提出的其他應(yīng)用層組播協(xié)議相比，它的優(yōu)勢在于將實體在虛擬環(huán)境中的

19、優(yōu)先度作為構(gòu)建組播樹的參數(shù)之一，通過仿真實驗得出：基于這種應(yīng)用層組播協(xié)議建立的組播樹在節(jié)點扇出和總帶寬利用率上都比單播方式高效。同時優(yōu)先度對建樹起到了指導作用，即優(yōu)先度大的實體，它到根節(jié)點的延時就小。由這幾點可以證明，基于優(yōu)先度的應(yīng)用層組播很好的滿足了DVE系統(tǒng)的特點。今后的工作中重點是為節(jié)點加上帶寬限制，并在有帶寬限制的條件下構(gòu)建組播樹。參考文獻：1 K. L. Morse, M. Zyda. Multicast grouping for data distribution management. In Proc of Computer Simulation Methods and Appl

20、ications Conference, 2000.2 Y. H. Chu, S.G. Rao, S. Seshan, H. Zhang. A case for end system multicast. IEEE Journal on Selected Areas in Communications, Vol. 20, No. 8, 2002: pp.1456-1471.3 L. Wei, D. Estrin. The trade-offs of multicast trees and algorithms. In Proc of International Conference on Co

21、mputer Communications Networks. 1994.4 D. Pendarakis, S. Shi, D. Verma, M. Waldvogel. ALMI: An application level multicast infrastructure. In Proc of USNIX Symposium on Internet Technologies and Systems, 2001:pp.49-60.5 P. Francis, Y. Pryadkin, P. Radoslavov, R. Govindan, B. Lindell. YOID: your own

22、internet distribution. In Proc of Peer to Peer workshop, 2002.6 D. Waitzman, C. Partridge, S. Deering. Distance Vector Routing. RFC 1075, 1988.7 K. L. Calvert, M. B. Doar, E. W. Zegura. Modelling internet topology. IEEE Communications Magazine, Vol. 35, No. 6, 1997: pp. 160-163.Priority based Applic

23、ation Level Multicast protocolYU Jun, CHEN Ling, CHEN Gencai(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China)Abstract: This paper proposes an application level multicast protocol based on priority used for Distributed Virtual Environment. Compared with other a

24、pplication level multicast protocols, the advantages of this protocol lie on using both the entities priority in DVE and the nodes network layer metric to construct the multicast tree. The simulation results show that the tree construction method based on priority has a better performance on bandwid

25、th usage than the unicast; meanwhile the priority is a very constructed parameter when build the multicast tree. From the above, the protocol is more suitable for DVE in which the nodes priorities are different.Key words: Priority; Distributed Virtual Environment; Application Level Multicast （責任編輯：曾

26、 丹）（上接第13頁）（5）由于粗糙集理論的容錯能力較強，因此該粗糙神經(jīng)網(wǎng)絡(luò)的容錯能力也較強；（6）該網(wǎng)絡(luò)可以處理動態(tài)非線性復(fù)雜系統(tǒng)。參考文獻：1 曾黃麟.粗集理論及其應(yīng)用. 重慶：重慶大學出版社, 1998. 2 Pawlak Z.Rough Sets. Theoretical Aspects of Reasoning About Data, Kluwer Academic Publishers, 1991.3 Keming Xie,Zehua Chen.Application of Rough Sets in Intelligent Control , Proc of 4th ISTM., Shanghai China, 2001:pp.291-294.5 Lingras P. Comparison of Neofuzzy and Rough Neural Network .Information Science