楊地委，孫淑霞，崔金國(guó)

（成都理工大學(xué)信息工程學(xué)院， 成都610059）

在FTP和HTTP協(xié)議中，每個(gè)下載者從FTP或HTTP服務(wù)器處下載自己所需要的文件，各個(gè)下載者之間沒(méi)有交互。當(dāng)非常多的用戶同時(shí)訪問(wèn)和下載服務(wù)器上的文件時(shí)，由于FTP服務(wù)器的處理能力和帶寬的限制，下載速度會(huì)急劇下降，有的用戶根本訪問(wèn)不了服務(wù)器。采用應(yīng)用層組播技術(shù)的單源數(shù)據(jù)傳輸系統(tǒng)是面向單源的實(shí)時(shí)應(yīng)用，加入了用戶下載數(shù)據(jù)之間的交流，提高了下載的速度和效率。

1 應(yīng)用層組播技術(shù)簡(jiǎn)介

應(yīng)用層組播技術(shù)的研究作為覆蓋網(wǎng)絡(luò)研究的一個(gè)方向，是國(guó)際上剛剛興起的研究熱點(diǎn)，很多大學(xué)和研究院都在進(jìn)行這方面的研究。目前在Peerto-Peer（P2P）網(wǎng)絡(luò)上實(shí)現(xiàn)的應(yīng)用層組播方案主要有3種：CAN Multicast、Scribe和Bayeux。它們都是在基于動(dòng)態(tài)哈希路由的P2P網(wǎng)絡(luò)上實(shí)現(xiàn)的，其中CAN Multicast是在CAN之上實(shí)現(xiàn)的，Scribe是在Pastry上實(shí)現(xiàn)的，Bayeux是在Tapestry上實(shí)現(xiàn)的。這幾種方案都充分利用了P2P網(wǎng)絡(luò)的路由機(jī)制。因此，只需增加少量的模塊就可以實(shí)現(xiàn)多播功能。與原先的P2P網(wǎng)絡(luò)相比，只增加少量的開(kāi)銷就實(shí)現(xiàn)了多播功能，同時(shí)繼承了P2P網(wǎng)絡(luò)的支持大規(guī)模和支持成員動(dòng)態(tài)變化的特性。可用于分布式仿真、多方實(shí)時(shí)游戲和大規(guī)模協(xié)作應(yīng)用等。但這3種方案對(duì)于應(yīng)用層多播的模型、性能分析和性能優(yōu)化都沒(méi)有進(jìn)行研究。

大規(guī)模單源應(yīng)用層組播樹(shù)方案中，最具有代表性的就是NICE和Zigzag應(yīng)用層組播樹(shù)構(gòu)建方案。兩者的思路都是“分層”、“分群”，成員只與少量固定數(shù)目的節(jié)點(diǎn)聯(lián)系。NICE的維護(hù)管理具有分布性和自治性，節(jié)點(diǎn)的維護(hù)負(fù)載較輕，且節(jié)點(diǎn)的退出只影響局部節(jié)點(diǎn)，不影響根節(jié)點(diǎn)。缺點(diǎn)是層次越高的節(jié)點(diǎn)負(fù)載越重，如最高層的節(jié)點(diǎn)的度數(shù)達(dá)到logN，當(dāng)系統(tǒng)規(guī)模很大時(shí)，這會(huì)成為系統(tǒng)的瓶頸。

2 SSTS構(gòu)造

采用應(yīng)用層組播技術(shù)的單源數(shù)據(jù)傳輸系統(tǒng)（SSTS，Single Source Transfer System）由一個(gè)數(shù)據(jù)源服務(wù)器和若干客戶端組成，是在應(yīng)用層建立組播，在客戶機(jī)間復(fù)制和轉(zhuǎn)發(fā)數(shù)據(jù)，數(shù)據(jù)源服務(wù)器負(fù)責(zé)提供組播數(shù)據(jù)的來(lái)源，每個(gè)客戶端經(jīng)過(guò)一定的算法加入組播樹(shù)后進(jìn)行文件的傳輸。該系統(tǒng)是一種改進(jìn)了的結(jié)構(gòu)化的P2P系統(tǒng)，具有結(jié)構(gòu)化P2P系統(tǒng)尋址方便，易于定位的特點(diǎn)，同時(shí)也具有BT等常見(jiàn)的P2P文件共享系統(tǒng)的多節(jié)點(diǎn)分片下載的特點(diǎn)，可以方便快捷地進(jìn)行文件傳輸，用戶可以在下載文件的同時(shí)與其他用戶交互，不僅解決了多用戶下載文件時(shí)對(duì)服務(wù)器帶來(lái)的壓力，也提高了數(shù)據(jù)傳輸?shù)乃俣群托?。該系統(tǒng)的主要算法和模型包括組播樹(shù)的構(gòu)造與維護(hù)，備份區(qū)和緩沖區(qū)的設(shè)計(jì)及分片傳輸算法的設(shè)計(jì)。

3 組播樹(shù)構(gòu)造

整個(gè)SSTS中的節(jié)點(diǎn)具有高動(dòng)態(tài)性，隨時(shí)都可能有節(jié)點(diǎn)失效或退出，由于應(yīng)用層的組播系統(tǒng)需要系統(tǒng)節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)，所以節(jié)點(diǎn)的突然失效會(huì)使組播服務(wù)中斷，其次應(yīng)用層組播系統(tǒng)通過(guò)節(jié)點(diǎn)間的相互傳遞發(fā)送數(shù)據(jù)，組播樹(shù)構(gòu)建另一個(gè)要點(diǎn)就是盡量減少數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸路徑，以減少數(shù)據(jù)到達(dá)接收者的延遲和網(wǎng)絡(luò)負(fù)荷。本文設(shè)計(jì)的組播樹(shù)構(gòu)造采用4叉樹(shù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)至多只有4棵子樹(shù)，4叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒。

3.1 節(jié)點(diǎn)加入組播樹(shù)

當(dāng)節(jié)點(diǎn)P運(yùn)行SSTS以后，服務(wù)器根據(jù)節(jié)點(diǎn)資源列表中讀出該節(jié)點(diǎn)的IP地址和端口號(hào)，判斷其網(wǎng)絡(luò)位置，然后從節(jié)點(diǎn)資源列表中找出該節(jié)點(diǎn)網(wǎng)絡(luò)位置最近的節(jié)點(diǎn)，判斷該節(jié)點(diǎn)的直接子節(jié)點(diǎn)個(gè)數(shù)是否已經(jīng)達(dá)到上限，如果沒(méi)有達(dá)到上限，則把該節(jié)點(diǎn)做為P節(jié)點(diǎn)的父節(jié)點(diǎn)；如果直接子節(jié)點(diǎn)已經(jīng)達(dá)到上限，則從節(jié)點(diǎn)資源列表中的其它節(jié)點(diǎn)中尋找離該節(jié)點(diǎn)最近的節(jié)點(diǎn)，并重復(fù)以上判斷過(guò)程，直到P找到合適的父節(jié)點(diǎn)。新加入的節(jié)點(diǎn)首先向候選父節(jié)點(diǎn)發(fā)送請(qǐng)求加入的報(bào)文，在得到同意后加入并更新節(jié)點(diǎn)資源列表。如果此節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)就向父節(jié)點(diǎn)發(fā)送請(qǐng)求報(bào)文，獲取父節(jié)點(diǎn)的備份區(qū)數(shù)據(jù)。用于將來(lái)父節(jié)點(diǎn)離開(kāi)時(shí)，其左子節(jié)點(diǎn)直接切換到父節(jié)點(diǎn)上。

3.2 節(jié)點(diǎn)的離開(kāi)與切換

在組播樹(shù)形成以后，必然會(huì)有節(jié)點(diǎn)由于某種原因要求退出組播，但是節(jié)點(diǎn)的離開(kāi)不能影響組播樹(shù)的正常運(yùn)作。如果節(jié)點(diǎn)沒(méi)有任何子節(jié)點(diǎn)，那么只需要通知父節(jié)點(diǎn)刪除該節(jié)點(diǎn)。如果節(jié)點(diǎn)有一個(gè)或多個(gè)子節(jié)點(diǎn)，那么節(jié)點(diǎn)離開(kāi)后其左子節(jié)點(diǎn)代替該節(jié)點(diǎn)。用以下算法來(lái)處理：

（1）每個(gè)節(jié)點(diǎn)的離開(kāi)都會(huì)向其父節(jié)點(diǎn)發(fā)送OUT標(biāo)識(shí)，其子節(jié)點(diǎn)立即向其祖父節(jié)點(diǎn)發(fā)送加入請(qǐng)求報(bào)文，在得到同意后加入；（2）每個(gè)節(jié)點(diǎn)在同一時(shí)間內(nèi)只允許一個(gè)子節(jié)點(diǎn)的加入，如果同時(shí)有多個(gè)節(jié)點(diǎn)的加入，由于帶寬資源的限制，將其一個(gè)或多個(gè)節(jié)點(diǎn)交給子節(jié)點(diǎn)來(lái)處理；（3）在切換過(guò)程中，節(jié)點(diǎn)不接受其他節(jié)點(diǎn)的加入請(qǐng)求；（4）在切換過(guò)程中，如果發(fā)送失敗，向上層報(bào)錯(cuò)，節(jié)點(diǎn)可重新執(zhí)行加入組播樹(shù)。

算法的具體過(guò)程如圖1，節(jié)點(diǎn)B離開(kāi)組播樹(shù)后，它的子節(jié)點(diǎn)F、G、H、I立即向其祖父節(jié)點(diǎn)A發(fā)送加入請(qǐng)求，而節(jié)點(diǎn)A的帶寬只能接收一個(gè)節(jié)點(diǎn)，此時(shí)有左子節(jié)點(diǎn)加入，其他節(jié)點(diǎn)加入由F節(jié)點(diǎn)接收。

圖1 節(jié)點(diǎn)B離開(kāi)導(dǎo)致的切換

該算法保證子節(jié)點(diǎn)在父節(jié)點(diǎn)離開(kāi)后能迅速建立到祖父節(jié)點(diǎn)中，而且左子節(jié)點(diǎn)保存了父節(jié)點(diǎn)的備份區(qū)數(shù)據(jù)，避免了再次傳數(shù)據(jù)造成的帶寬限制，也保證組播樹(shù)的穩(wěn)定，從而提高下載數(shù)據(jù)的效率。

4 備份區(qū)及緩沖區(qū)的設(shè)計(jì)

備份區(qū)和緩沖區(qū)的設(shè)計(jì)影響到系統(tǒng)的整體性能，為了獲得更高的數(shù)據(jù)傳輸和實(shí)時(shí)性能，備份區(qū)和緩沖區(qū)總計(jì)大小設(shè)計(jì)為16 M，備份區(qū)為4 M，緩沖區(qū)12 M。需下載文件邏輯上分成相同的4塊區(qū)域，每個(gè)子家族的備份區(qū)保存各自不同的數(shù)據(jù)區(qū)域。例如一個(gè)需下載文件為800 M，第1子家族保存0 M～200 M，第2子家族201 M～400 M，依此類推。

每個(gè)節(jié)點(diǎn)的備份區(qū)保存數(shù)據(jù)4個(gè)piece，每個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)保存父節(jié)點(diǎn)的備份區(qū)數(shù)據(jù)。每個(gè)節(jié)點(diǎn)將下載到的數(shù)據(jù)先保存在緩沖區(qū)中，在達(dá)到一定的數(shù)值時(shí)再將數(shù)據(jù)寫(xiě)入硬盤的文件中。每個(gè)節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)時(shí)，先在緩沖區(qū)中尋找，若緩沖區(qū)中不存在所請(qǐng)求的數(shù)據(jù)，則根據(jù)分片傳輸算法把請(qǐng)求到的數(shù)據(jù)先寫(xiě)入緩沖區(qū)中。

5 分片傳輸算法的設(shè)計(jì)

需下載文件在邏輯上被劃分為大小相同的塊，稱為piece，每個(gè)piece的大小為1 M。每個(gè)piece分成相同的slice（256 k），節(jié)點(diǎn)與節(jié)點(diǎn)以slice為單位進(jìn)行傳輸。

當(dāng)一個(gè)文件要加入SSTS時(shí)，先進(jìn)行文件分片操作，并產(chǎn)生順序的驗(yàn)證文件，把文件分成4個(gè)相同的區(qū)域，根節(jié)點(diǎn)的4個(gè)子節(jié)點(diǎn)分別存儲(chǔ)各自的數(shù)據(jù)區(qū)域，以下各子節(jié)點(diǎn)的備份區(qū)存儲(chǔ)數(shù)據(jù)遞推。

在SSTS中，每個(gè)節(jié)點(diǎn)都存儲(chǔ)節(jié)點(diǎn)資源列表，在節(jié)點(diǎn)資源列表中保存著組播樹(shù)的結(jié)構(gòu)和每個(gè)節(jié)點(diǎn)所保存的數(shù)據(jù)及驗(yàn)證文件。數(shù)據(jù)data存放在data的父節(jié)點(diǎn)和其左子節(jié)點(diǎn)上。

節(jié)點(diǎn)P查找數(shù)據(jù)d時(shí)，根據(jù)驗(yàn)證文件查找數(shù)據(jù)d所在區(qū)域，然后遍歷一下組播樹(shù)，但是每前進(jìn)一步時(shí)，都在葉子節(jié)點(diǎn)查找需要的文件。如果沒(méi)有，繼續(xù)查找，如果找到需要的文件，就可以開(kāi)始文件的傳輸，同時(shí)繼續(xù)查找d的后繼節(jié)點(diǎn)和其它備份節(jié)點(diǎn)。如果找不到就到服務(wù)器直接下載。

6 SSTS分析與實(shí)現(xiàn)

（1）服務(wù)處理能力。每個(gè)節(jié)點(diǎn)保存4個(gè)piece，對(duì)于服務(wù)器的處理能力，當(dāng)前的計(jì)算機(jī)一般都有足夠的內(nèi)存和處理能力。（2）組播樹(shù)的構(gòu)造。各個(gè)節(jié)點(diǎn)都具有TCP/IP網(wǎng)絡(luò)通信的能力，因此只要節(jié)點(diǎn)能與互聯(lián)網(wǎng)進(jìn)行連接，就可以方便地加入該系統(tǒng)。（3）網(wǎng)絡(luò)延遲。文件下載時(shí)，在SSTS中是從多個(gè)緩存節(jié)點(diǎn)同時(shí)向請(qǐng)求節(jié)點(diǎn)分片傳送文件，是多對(duì)一傳輸，避免了網(wǎng)絡(luò)上的延遲，從而提高了數(shù)據(jù)傳輸?shù)乃俣?。?）擴(kuò)展能力。該系統(tǒng)是典型的拓?fù)浣Y(jié)構(gòu)，并且引入了P2P技術(shù)，是一種結(jié)構(gòu)化的P2P系統(tǒng)，其中，因?yàn)槊總€(gè)節(jié)點(diǎn)都保存其父節(jié)點(diǎn)的備份區(qū)數(shù)據(jù)，即使某個(gè)節(jié)點(diǎn)突然離開(kāi)系統(tǒng)，也不會(huì)造成常見(jiàn)的文件丟失現(xiàn)象。因此，本系統(tǒng)具有很高的擴(kuò)展能力。

7 結(jié)束語(yǔ)

從以上分析可以看出，SSTS的健壯性好，避免節(jié)點(diǎn)突然離開(kāi)造成文件丟失的可能；同時(shí)文件下載的傳輸速度得到很大的提高，使得系統(tǒng)響應(yīng)時(shí)間變小，更方便用戶的使用。節(jié)點(diǎn)的加入和離開(kāi)與查找文件的速度有了明顯的提高。由此可見(jiàn)，SSTS兼?zhèn)銯TP和P2P系統(tǒng)的優(yōu)點(diǎn)，尋址方便，穩(wěn)定性高，傳輸速度快，是一種較好的結(jié)構(gòu)化的單源數(shù)據(jù)傳輸系統(tǒng)。

[1] 陳旭孟. 一個(gè)面向?qū)崟r(shí)傳輸?shù)膽?yīng)用層組播協(xié)議的設(shè)計(jì)[J] .計(jì)算機(jī)應(yīng)用與軟件，2008，25（9）.

[2] 申新鵬. 結(jié)構(gòu)化多點(diǎn)協(xié)作P2P系統(tǒng)研究[J] . 計(jì)算機(jī)應(yīng)用研究，2008，25（10）.