摘 要：介紹P2P流媒體技術(shù)的發(fā)展由來，著重討論目前P2P流媒體系統(tǒng)的2種典型模型：基于樹狀拓?fù)鋮f(xié)議及擴(kuò)展的模型和基于Gossip協(xié)議的模型，以及他們的最新研究進(jìn)展。分析這兩種模型實(shí)現(xiàn)新節(jié)點(diǎn)加入、節(jié)點(diǎn)離開以及節(jié)點(diǎn)之間數(shù)據(jù)交換的方法，總結(jié)他們?cè)诰W(wǎng)絡(luò)帶寬效率、延時(shí)和可靠性之間的權(quán)衡，指出了各自的優(yōu)缺點(diǎn)。

關(guān)鍵詞：應(yīng)用層組播；P2P；流媒體；Gossip協(xié)議

中圖分類號(hào)：TN393 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1004-373X(2008)02-159-03

Research Progress Based on P2P Stream Medium System Model

YGAN Weiwen，WANG Jianxin

(School of Information Science and Engineering，Central South University，Changsha，410083，China)

Abstract：This paper introduces the development of P2P stream medium technology，discusses two kinds of typical P2P stream medium model in current: the model of tree-based protocol and extensions and the model of Gossip- based protocol，and their new research progress，analyses the methods of both models how to add new nodes，nodes leaving，and data exchange between nodes，aggregates the different models how to balance in the efficiency of the network bandwidth，delay，and reliability，describes their advantages and disadvantages of both models.

Keywords：application layer multicast;P2P;streaming medium;Gossip- based protocol

隨著Internet的迅速發(fā)展，能滿足“邊下載邊播放”的流媒體技術(shù)應(yīng)運(yùn)而生并且得到快速發(fā)展。然而人們對(duì)媒體的質(zhì)量和延時(shí)要求不斷提高，傳統(tǒng)的基于單播的傳輸方式很難滿足人們的要求，主要原因在于傳統(tǒng)的單播容易導(dǎo)致服務(wù)器端的性能瓶頸和網(wǎng)絡(luò)資源的浪費(fèi)，且不能有效地支持流媒體的大規(guī)模數(shù)據(jù)分發(fā)。

近年興起的CDN[1]（Content Delivery Network）服務(wù)通過在Internet上廣泛部署服務(wù)節(jié)點(diǎn)，把服務(wù)內(nèi)容“推”向網(wǎng)絡(luò)的“邊緣”，并把客戶請(qǐng)求路由到距客戶最近的服務(wù)節(jié)點(diǎn)，從而減輕了服務(wù)器的壓力和對(duì)骨干網(wǎng)絡(luò)的帶寬消耗，然而卻增加了系統(tǒng)總成本，并且?guī)砹巳缇彺嬉恢滦院拓?fù)載平衡等管理難題。因此，研究人員又提出了IP組播技術(shù)：在網(wǎng)絡(luò)層提供把數(shù)據(jù)包發(fā)送到共享相同IP地址的一個(gè)主機(jī)組的服務(wù)，但是IP組播技術(shù)由于協(xié)議本身的復(fù)雜性、網(wǎng)絡(luò)異構(gòu)性、以及缺少支持組播的可靠的擁塞控制機(jī)制等自身固有的限制而難以部署。

1 P2P流媒體技術(shù)的提出

為了提高Internet上流媒體應(yīng)用的QoS，研究人員提出了基于P2P網(wǎng)絡(luò)的媒體分發(fā)技術(shù)：把P2P技術(shù)應(yīng)用到流媒體，把組播的功能從網(wǎng)絡(luò)層移到應(yīng)用層[2]。在單播的流媒體系統(tǒng)中用戶之間是沒有任何聯(lián)系的，但采用P2P技術(shù)后，每個(gè)流媒體用戶就是P2P中的一個(gè)節(jié)點(diǎn)，用戶可以根據(jù)他們的網(wǎng)絡(luò)狀態(tài)和設(shè)備能力與一個(gè)或幾個(gè)用戶建立連接來分享數(shù)據(jù)，這種連接能減少服務(wù)器的負(fù)擔(dān)和提高每個(gè)用戶的視頻質(zhì)量。

目前P2P流媒體模型主要可以分為2大類：基于樹狀拓?fù)鋮f(xié)議及擴(kuò)展的模型(Tree-based protocol and extensions)和基于Gossip協(xié)議的模型(Gossip- based protocol )。他們都采用層疊( overlay)結(jié)構(gòu)，所謂層疊結(jié)構(gòu)，就是架構(gòu)在物理網(wǎng)絡(luò)基礎(chǔ)上的邏輯結(jié)構(gòu)，該邏輯結(jié)構(gòu)表現(xiàn)為終端節(jié)點(diǎn)及其邏輯關(guān)聯(lián)的邊的集合，他能表現(xiàn)出物理網(wǎng)絡(luò)不具備的、適應(yīng)應(yīng)用需求的屬性。

2 基于樹狀拓?fù)鋮f(xié)議及擴(kuò)展的模型

在基于樹狀拓?fù)鋮f(xié)議模型中，子節(jié)點(diǎn)從父節(jié)點(diǎn)獲取數(shù)據(jù)，樹的根節(jié)點(diǎn)就是源節(jié)點(diǎn)S（提供媒體數(shù)據(jù)源），模型的層疊結(jié)構(gòu)如圖1所示。

2.1 新節(jié)點(diǎn)的加入

當(dāng)一個(gè)新節(jié)點(diǎn)N試圖加入網(wǎng)絡(luò)時(shí)，首先要向根節(jié)點(diǎn)S請(qǐng)求服務(wù)，如果服務(wù)器有足夠的帶寬，則根節(jié)點(diǎn)向新節(jié)點(diǎn)N提供服務(wù)，否則根節(jié)點(diǎn)把N的請(qǐng)求轉(zhuǎn)發(fā)給其某個(gè)直接的子節(jié)點(diǎn)。子節(jié)點(diǎn)根據(jù)自己的資源情況判斷是否給N提供服務(wù)，以此類推，直到N找到一個(gè)父節(jié)點(diǎn)。在這種模型中，每個(gè)節(jié)點(diǎn)僅維護(hù)自己的父節(jié)點(diǎn)和直接的子節(jié)點(diǎn)的信息。

2.2 節(jié)點(diǎn)的正常離開

當(dāng)節(jié)點(diǎn)D離開的時(shí)候，如果D是葉子節(jié)點(diǎn)，則D只需要向其父節(jié)點(diǎn)發(fā)一個(gè)退出的請(qǐng)求，通知D的父節(jié)點(diǎn)釋放所有為D提供服務(wù)的資源，組播樹的其他節(jié)點(diǎn)維持不變；如果節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則節(jié)點(diǎn)D的離開會(huì)導(dǎo)致D的所有后續(xù)子節(jié)點(diǎn)失去服務(wù)，所以在節(jié)點(diǎn)D離開之前，必須為D的所有子節(jié)點(diǎn)重新分配父節(jié)點(diǎn)。重新分配父節(jié)點(diǎn)有2種模式，一種是D的所有后續(xù)節(jié)點(diǎn)都被重新加入。另一種是維持節(jié)點(diǎn)D后面的子樹不動(dòng)，也就是說節(jié)點(diǎn)D只把他的每個(gè)直接子節(jié)點(diǎn)作為1個(gè)子樹重定向給新的服務(wù)節(jié)點(diǎn)T。這種模式由于不需要重新加入所有子節(jié)點(diǎn)，樹的修復(fù)會(huì)更快。

2.3 節(jié)點(diǎn)的異常離開

由于某種原因，節(jié)點(diǎn)可能在任意時(shí)刻在沒有發(fā)送任何消息的情況下突然中斷離開，系統(tǒng)為了檢測到這種狀況。每個(gè)節(jié)點(diǎn)需要周期性的向他們的父節(jié)點(diǎn)和子節(jié)點(diǎn)發(fā)送消息，說明自己工作正常。某個(gè)節(jié)點(diǎn)在幾個(gè)周期內(nèi)都沒有收到子節(jié)點(diǎn)正常的消息，則認(rèn)為子節(jié)點(diǎn)己經(jīng)非正常離開，該節(jié)點(diǎn)將回收服務(wù)該子節(jié)點(diǎn)的資源。同樣子節(jié)點(diǎn)在幾個(gè)周期內(nèi)都沒有收到父節(jié)點(diǎn)正常的消息，則認(rèn)為父節(jié)點(diǎn)己經(jīng)非正常離開，該節(jié)點(diǎn)以及所有后續(xù)節(jié)點(diǎn)都需要重新加入網(wǎng)絡(luò)。

2.4 常見的樹狀模型及其存在的不足

在基于樹狀拓?fù)鋮f(xié)議及擴(kuò)展的模型中，首先要解決的問題是組播樹的構(gòu)建，PeerCast[3]是最簡單的基于樹狀拓?fù)鋮f(xié)議模型。在組播樹中，如果節(jié)點(diǎn)離根節(jié)點(diǎn)越遠(yuǎn)，則數(shù)據(jù)的時(shí)延就越大，因此，樹的深度應(yīng)該盡可能小。但是每個(gè)節(jié)點(diǎn)的有限輸出帶寬限制了節(jié)點(diǎn)的寬度。理想的組播樹是在深度和寬度之間能夠有效地平衡。Zig-Zag[4]模型能夠有效地構(gòu)造組播樹，他定義了一整套完整的樹的構(gòu)建規(guī)則，保證樹的深度維持在O(log N)，N為系統(tǒng)中的節(jié)點(diǎn)數(shù)。盡管Zig-Zag模型能構(gòu)造一棵平衡的組播樹，但系統(tǒng)中也只有部分節(jié)點(diǎn)參與數(shù)據(jù)分發(fā)。例如在一棵平衡的樹中，如果每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)為f，樹的深度為h，那么葉子節(jié)點(diǎn)數(shù)量為fh，而參與數(shù)據(jù)分發(fā)的節(jié)點(diǎn)數(shù)量為fh－1f－1，系統(tǒng)中的葉子數(shù)量隨f的增加而增大。

基于樹狀拓?fù)鋮f(xié)議模型存在以下缺點(diǎn)：

（1）在基于樹的模型中，每個(gè)節(jié)點(diǎn)都只有一個(gè)父節(jié)點(diǎn)，子節(jié)點(diǎn)的服務(wù)質(zhì)量依賴于父節(jié)點(diǎn)，一旦父節(jié)點(diǎn)離開系統(tǒng)，則他的子節(jié)點(diǎn)就需要被重新插入到組播樹中。系統(tǒng)對(duì)樹的恢復(fù)速度將嚴(yán)重影響對(duì)受影響的子節(jié)點(diǎn)的服務(wù)質(zhì)量。

（2） 組播樹中的葉子節(jié)點(diǎn)只作為純客戶端，沒有參與到媒體的分發(fā)，而通常葉子節(jié)點(diǎn)在樹中所占的比例非常大，因此，基于樹的系統(tǒng)沒有充分利用所有節(jié)點(diǎn)的能力。

2.5 基于樹狀拓?fù)鋮f(xié)議模型的研究進(jìn)展

為了克服上述缺點(diǎn)，SplitStream[5]模型被提了出來，SplitStream模型的主要思想就是把媒體數(shù)據(jù)分成k個(gè)獨(dú)立的碼流，可以通過多重描述編碼（MDC）實(shí)現(xiàn)，然后為每個(gè)碼流構(gòu)造一個(gè)組播樹，形成一個(gè)“森林”，每個(gè)節(jié)點(diǎn)可以根據(jù)帶寬情況選擇接收其中的幾個(gè)碼流。樹的構(gòu)造的主要困難是要求每個(gè)節(jié)點(diǎn)只在某棵樹中為中間節(jié)點(diǎn)，而在其他的樹中都為葉子節(jié)點(diǎn)。如圖2所示，數(shù)據(jù)被分成2個(gè)單獨(dú)的流，每個(gè)流形成一棵組播樹，組播樹1的中間節(jié)點(diǎn)2，3，4，在組播樹2中則為葉子節(jié)點(diǎn)。

3 基于Gossip協(xié)議模型

基于gossip的分發(fā)協(xié)議是最近出現(xiàn)的非常新穎的一類協(xié)議，他們具有非常好的擴(kuò)展性和可靠性。在這些協(xié)議里，節(jié)點(diǎn)隨機(jī)的給系統(tǒng)中的部分節(jié)點(diǎn)發(fā)送消息，每個(gè)接收到消息的節(jié)點(diǎn)繼續(xù)向其他節(jié)點(diǎn)發(fā)送消息，重復(fù)這個(gè)過程，直到消息被發(fā)送給系統(tǒng)中的所有節(jié)點(diǎn)。在基于樹狀拓?fù)鋮f(xié)議及擴(kuò)展的模型中，都顯式的定義了節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系，子節(jié)點(diǎn)從父節(jié)點(diǎn)獲取數(shù)據(jù)，而在基于Gossip協(xié)議的系統(tǒng)模型中，節(jié)點(diǎn)之間不需要構(gòu)造復(fù)雜的拓?fù)潢P(guān)系，也沒有確定的父節(jié)點(diǎn)。在這種模型中，每個(gè)節(jié)點(diǎn)通過Gossip協(xié)議維護(hù)系統(tǒng)中其他部分節(jié)點(diǎn)的視圖，通過一定的調(diào)度算法在節(jié)點(diǎn)之間交換數(shù)據(jù)，每1個(gè)節(jié)點(diǎn)即是數(shù)據(jù)的接收者又是數(shù)據(jù)的提供者。在這種系統(tǒng)中，通常需要比較大的緩存，系統(tǒng)的啟動(dòng)延遲相對(duì)比較大。但是，因?yàn)槊總€(gè)節(jié)點(diǎn)的數(shù)據(jù)來源并不依賴于某個(gè)特定的父節(jié)點(diǎn)，所以系統(tǒng)有更強(qiáng)的健壯性。DONet (Data-driven Overlay Network)[6]是一個(gè)典型的基于Gossip協(xié)議的模型。

3.1 節(jié)點(diǎn)的管理

DONet中每個(gè)節(jié)點(diǎn)有1個(gè)在整個(gè)系統(tǒng)種系統(tǒng)惟一的標(biāo)識(shí)，比如IP地址，并且維護(hù)一個(gè)系統(tǒng)中其他節(jié)點(diǎn)的標(biāo)識(shí)的緩存mCache。當(dāng)新節(jié)點(diǎn)加入時(shí)，首先請(qǐng)求源節(jié)點(diǎn)，源節(jié)點(diǎn)從他的mCache中隨機(jī)的選擇一個(gè)節(jié)點(diǎn)作為新節(jié)點(diǎn)的代理。新節(jié)點(diǎn)從代理節(jié)點(diǎn)獲得初始伙伴節(jié)點(diǎn)的列表。在一個(gè)動(dòng)態(tài)的系統(tǒng)中，為了創(chuàng)建和維護(hù)mCache，每個(gè)節(jié)點(diǎn)周期性地發(fā)送宣告自己存在的消息，消息的接收節(jié)點(diǎn)首先判斷是否為新消息，如果是添加該節(jié)點(diǎn)信息，如果不是更新該節(jié)點(diǎn)的更新時(shí)間，如果某節(jié)點(diǎn)的更新時(shí)間小于零，該節(jié)點(diǎn)將被刪除。

3.2 數(shù)據(jù)的表示與交換

在DONet中，節(jié)點(diǎn)的伙伴及伙伴之間數(shù)據(jù)的傳輸方向并不固定，伙伴之間根據(jù)各自的緩存的數(shù)據(jù)情況進(jìn)行數(shù)據(jù)交換，所以節(jié)點(diǎn)和伙伴需要相互知道所緩存的數(shù)據(jù)的內(nèi)容。在DONet中，視頻數(shù)據(jù)被分割成相同大小的塊，用1個(gè)緩存映射BM (buffer map)來表示節(jié)點(diǎn)中是否擁有某個(gè)數(shù)據(jù)塊。節(jié)點(diǎn)和伙伴通過不斷交換BM來了解相互間的緩存情況。在DONet實(shí)現(xiàn)中，每個(gè)數(shù)據(jù)塊代表1 s的數(shù)據(jù)，用1個(gè)滑動(dòng)窗口(Sliding window)代表BM，大小為120個(gè)片斷，BM中120個(gè)比特來記錄每個(gè)比特位代表1個(gè)數(shù)據(jù)片斷，比特的值為1表示有這個(gè)片斷，0表示沒有。由于不同節(jié)點(diǎn)的滑動(dòng)窗口代表的并不是完全一樣的數(shù)據(jù)，DONet用2個(gè)字節(jié)表示滑動(dòng)窗口中第一個(gè)片斷的序列號(hào)。

3.3 數(shù)據(jù)調(diào)度算法

調(diào)度的目的就是如何從伙伴節(jié)點(diǎn)獲取數(shù)據(jù)塊。在一個(gè)靜態(tài)的、同構(gòu)的環(huán)境中，由于各節(jié)點(diǎn)的帶寬基本相同，可以隨機(jī)地從各伙伴節(jié)點(diǎn)獲取數(shù)據(jù)塊；然而在一個(gè)動(dòng)態(tài)的、異構(gòu)的網(wǎng)絡(luò)中，需要更智能的調(diào)度算法。調(diào)度的約束有兩個(gè)：

（1） 每個(gè)片斷數(shù)據(jù)需要在播放的Deadline之前獲取，錯(cuò)過Deadline的片斷要盡可能的少；

（2） 如果某個(gè)片斷的提供者越少，就越難滿足Deadline的要求，因此在DONet中，采用最少塊優(yōu)先的算法。

3.4 基于Gossip協(xié)議模型的研究進(jìn)展

Gossip算法是一種可靠的分布式信息擴(kuò)散機(jī)制，他使得網(wǎng)格內(nèi)各個(gè)結(jié)點(diǎn)之間可以交換彼此了解的信息，并及時(shí)進(jìn)行更新。但是傳統(tǒng)的Gossip算法存在一些問題：發(fā)送消息的數(shù)目較多，使得消息擴(kuò)散的負(fù)載較大；網(wǎng)格規(guī)模很大時(shí)，消息發(fā)送的失敗率會(huì)明顯增加。

以傳統(tǒng)Gossip協(xié)議為基礎(chǔ)，提出了一種域間和域內(nèi)兩層消息擴(kuò)散機(jī)制：第一層是在同一個(gè)域內(nèi)進(jìn)行消息擴(kuò)散，第二層是在域間進(jìn)行消息擴(kuò)散。改進(jìn)后的分層Gossip機(jī)制，消息擴(kuò)散的負(fù)荷減小，擴(kuò)散范圍增大，而且由于將大規(guī)模結(jié)點(diǎn)在邏輯上劃分為了多個(gè)小區(qū)域，降低了消息擴(kuò)散的失敗率，從而可以及時(shí)有效地更新在各分布式信息服務(wù)器中存儲(chǔ)的異地資源信息，提高資源查詢的效率和性能。

4 結(jié) 語

在基于組播樹的應(yīng)用層組播系統(tǒng)中，如 PeerCast、Zig-Zag，其雖然取得網(wǎng)絡(luò)帶寬的有效性，然而不管樹如何構(gòu)建的，系統(tǒng)中也只有部分節(jié)點(diǎn)參與數(shù)據(jù)分發(fā)，組播樹中低層節(jié)點(diǎn)的離開都不可避免地會(huì)影響到后續(xù)的子節(jié)點(diǎn)，其犧牲了可靠性。SplitStream部署了 MDC，部分的解決了可靠性的問題，但卻引入冗余的編碼，事實(shí)上是用網(wǎng)絡(luò)效率換取可靠性。

基于 gossip協(xié)議的 DONet，通過 gossip 協(xié)議獲取系統(tǒng)中其他節(jié)點(diǎn)建立通訊，并互相交換數(shù)據(jù)。因?yàn)椴灰蕾囉谀硞€(gè)節(jié)點(diǎn)，DONet 在保證系統(tǒng)的可靠性的同時(shí)取得了網(wǎng)絡(luò)效率，但卻犧牲了延時(shí)。DONet中的主要問題是系統(tǒng)的啟動(dòng)延時(shí)和網(wǎng)絡(luò)異構(gòu)帶寬的適應(yīng)性?？梢园l(fā)現(xiàn)，不同的模型都是試圖在網(wǎng)絡(luò)帶寬效率、延時(shí)和可靠性之間做出某種權(quán)衡。

參 考 文 獻(xiàn)

［1］Mohamed M Hefeeda，Bharat K Bhargava.On-demand Media Streaming Over the Internet.The Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS′03)，Puerto Rico，2003.

［2］馬凌霄.基于P2P網(wǎng)絡(luò)的流媒體技術(shù)研究[D].杭州：浙江大學(xué)，2005.

［3］Deshpande H，Bawa M，Garcia-Molina H.Streaming Live Media over a Peer-to-Peer Network[R].Technical Report，Stanford University，2001.

［4］Duc A T，Kien A H.An Efficient Peer-to-peer Scheme for Media Streaming.In Proc.of IEEE INFOCOM′03， San Francisco，2003.

［5］Castro M，Druschel P，Kemarrec A-M，et al.High-bandwidth Content Distribution in Cooperative Environments[M].Berkeley，2003.

［6］Zhang X，Liu J，Li B，et al.A Data-driven Overlay Network for Live Media Streaming[R].Technical Report，2004.

［7］洪臻，李七金，凌晨.基于DHT的對(duì)等網(wǎng)絡(luò)路由定位模型研究[J].現(xiàn)代電子技術(shù)，2007，30(2):118-120.[ZK)]

作者簡介 陽衛(wèi)文 男，1974年出生，湖南衡陽人，碩士生。主要從事流媒體技術(shù)方向的研究。

王建新 男，1969年出生，湖南邵東人，教授。研方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)優(yōu)化算法、虛擬實(shí)驗(yàn)環(huán)境。

科學(xué)計(jì)算及信息處理李 季等：基于加權(quán)模糊解耦策略的注塑機(jī)料筒溫度控制

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。