單源數據傳輸系統的設計

楊地委，孫淑霞，崔金國

（成都理工大學信息工程學院， 成都610059）

在FTP和HTTP協議中，每個下載者從FTP或HTTP服務器處下載自己所需要的文件，各個下載者之間沒有交互。當非常多的用戶同時訪問和下載服務器上的文件時，由于FTP服務器的處理能力和帶寬的限制，下載速度會急劇下降，有的用戶根本訪問不了服務器。采用應用層組播技術的單源數據傳輸系統是面向單源的實時應用，加入了用戶下載數據之間的交流，提高了下載的速度和效率。

1 應用層組播技術簡介

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

大規模單源應用層組播樹方案中，最具有代表性的就是NICE和Zigzag應用層組播樹構建方案。兩者的思路都是“分層”、“分群”，成員只與少量固定數目的節點聯系。NICE的維護管理具有分布性和自治性，節點的維護負載較輕，且節點的退出只影響局部節點，不影響根節點。缺點是層次越高的節點負載越重，如最高層的節點的度數達到logN，當系統規模很大時，這會成為系統的瓶頸。

2 SSTS構造

采用應用層組播技術的單源數據傳輸系統（SSTS，Single Source Transfer System）由一個數據源服務器和若干客戶端組成，是在應用層建立組播，在客戶機間復制和轉發數據，數據源服務器負責提供組播數據的來源，每個客戶端經過一定的算法加入組播樹后進行文件的傳輸。該系統是一種改進了的結構化的P2P系統，具有結構化P2P系統尋址方便，易于定位的特點，同時也具有BT等常見的P2P文件共享系統的多節點分片下載的特點，可以方便快捷地進行文件傳輸，用戶可以在下載文件的同時與其他用戶交互，不僅解決了多用戶下載文件時對服務器帶來的壓力，也提高了數據傳輸的速度和效率。該系統的主要算法和模型包括組播樹的構造與維護，備份區和緩沖區的設計及分片傳輸算法的設計。

3 組播樹構造

整個SSTS中的節點具有高動態性，隨時都可能有節點失效或退出，由于應用層的組播系統需要系統節點來轉發數據，所以節點的突然失效會使組播服務中斷，其次應用層組播系統通過節點間的相互傳遞發送數據，組播樹構建另一個要點就是盡量減少數據在網絡中的傳輸路徑，以減少數據到達接收者的延遲和網絡負荷。本文設計的組播樹構造采用4叉樹結構，每個節點至多只有4棵子樹，4叉樹的子樹有左右之分，次序不能顛倒。

3.1 節點加入組播樹

當節點P運行SSTS以后，服務器根據節點資源列表中讀出該節點的IP地址和端口號，判斷其網絡位置，然后從節點資源列表中找出該節點網絡位置最近的節點，判斷該節點的直接子節點個數是否已經達到上限，如果沒有達到上限，則把該節點做為P節點的父節點；如果直接子節點已經達到上限，則從節點資源列表中的其它節點中尋找離該節點最近的節點，并重復以上判斷過程，直到P找到合適的父節點。新加入的節點首先向候選父節點發送請求加入的報文，在得到同意后加入并更新節點資源列表。如果此節點為父節點的左子節點就向父節點發送請求報文，獲取父節點的備份區數據。用于將來父節點離開時，其左子節點直接切換到父節點上。

3.2 節點的離開與切換

在組播樹形成以后，必然會有節點由于某種原因要求退出組播，但是節點的離開不能影響組播樹的正常運作。如果節點沒有任何子節點，那么只需要通知父節點刪除該節點。如果節點有一個或多個子節點，那么節點離開后其左子節點代替該節點。用以下算法來處理：

（1）每個節點的離開都會向其父節點發送OUT標識，其子節點立即向其祖父節點發送加入請求報文，在得到同意后加入；（2）每個節點在同一時間內只允許一個子節點的加入，如果同時有多個節點的加入，由于帶寬資源的限制，將其一個或多個節點交給子節點來處理；（3）在切換過程中，節點不接受其他節點的加入請求；（4）在切換過程中，如果發送失敗，向上層報錯，節點可重新執行加入組播樹。

算法的具體過程如圖1，節點B離開組播樹后，它的子節點F、G、H、I立即向其祖父節點A發送加入請求，而節點A的帶寬只能接收一個節點，此時有左子節點加入，其他節點加入由F節點接收。

圖1 節點B離開導致的切換

該算法保證子節點在父節點離開后能迅速建立到祖父節點中，而且左子節點保存了父節點的備份區數據，避免了再次傳數據造成的帶寬限制，也保證組播樹的穩定，從而提高下載數據的效率。

4 備份區及緩沖區的設計

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

每個節點的備份區保存數據4個piece，每個節點的左子節點保存父節點的備份區數據。每個節點將下載到的數據先保存在緩沖區中，在達到一定的數值時再將數據寫入硬盤的文件中。每個節點請求數據時，先在緩沖區中尋找，若緩沖區中不存在所請求的數據，則根據分片傳輸算法把請求到的數據先寫入緩沖區中。

5 分片傳輸算法的設計

需下載文件在邏輯上被劃分為大小相同的塊，稱為piece，每個piece的大小為1 M。每個piece分成相同的slice（256 k），節點與節點以slice為單位進行傳輸。

當一個文件要加入SSTS時，先進行文件分片操作，并產生順序的驗證文件，把文件分成4個相同的區域，根節點的4個子節點分別存儲各自的數據區域，以下各子節點的備份區存儲數據遞推。

在SSTS中，每個節點都存儲節點資源列表，在節點資源列表中保存著組播樹的結構和每個節點所保存的數據及驗證文件。數據data存放在data的父節點和其左子節點上。

節點P查找數據d時，根據驗證文件查找數據d所在區域，然后遍歷一下組播樹，但是每前進一步時，都在葉子節點查找需要的文件。如果沒有，繼續查找，如果找到需要的文件，就可以開始文件的傳輸，同時繼續查找d的后繼節點和其它備份節點。如果找不到就到服務器直接下載。

6 SSTS分析與實現

（1）服務處理能力。每個節點保存4個piece，對于服務器的處理能力，當前的計算機一般都有足夠的內存和處理能力。（2）組播樹的構造。各個節點都具有TCP/IP網絡通信的能力，因此只要節點能與互聯網進行連接，就可以方便地加入該系統。（3）網絡延遲。文件下載時，在SSTS中是從多個緩存節點同時向請求節點分片傳送文件，是多對一傳輸，避免了網絡上的延遲，從而提高了數據傳輸的速度。（4）擴展能力。該系統是典型的拓撲結構，并且引入了P2P技術，是一種結構化的P2P系統，其中，因為每個節點都保存其父節點的備份區數據，即使某個節點突然離開系統，也不會造成常見的文件丟失現象。因此，本系統具有很高的擴展能力。

7 結束語

從以上分析可以看出，SSTS的健壯性好，避免節點突然離開造成文件丟失的可能；同時文件下載的傳輸速度得到很大的提高，使得系統響應時間變小，更方便用戶的使用。節點的加入和離開與查找文件的速度有了明顯的提高。由此可見，SSTS兼備FTP和P2P系統的優點，尋址方便，穩定性高，傳輸速度快，是一種較好的結構化的單源數據傳輸系統。

[1] 陳旭孟. 一個面向實時傳輸的應用層組播協議的設計[J] .計算機應用與軟件，2008，25（9）.

[2] 申新鵬. 結構化多點協作P2P系統研究[J] . 計算機應用研究，2008，25（10）.