一種有效的Ｐ２Ｐ流媒體點(diǎn)播的供應(yīng)者發(fā)現(xiàn)機(jī)制

摘 要：提出了一種新的供應(yīng)者發(fā)現(xiàn)機(jī)制，在源服務(wù)器上創(chuàng)建類似目錄的數(shù)據(jù)結(jié)構(gòu)維護(hù)系統(tǒng)中少量特定P2P節(jié)點(diǎn)的信息，用來鎖定與目標(biāo)供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)，再通過這些節(jié)點(diǎn)的緩存交迭表與其鄰近節(jié)點(diǎn)直接通信來找到合適的供應(yīng)者。仿真實(shí)驗(yàn)結(jié)果表明，該供應(yīng)者發(fā)現(xiàn)機(jī)制能夠加快P2P節(jié)點(diǎn)的加入和恢復(fù)操作，且整個系統(tǒng)的通信負(fù)擔(dān)明顯降低。

關(guān)鍵詞：對等網(wǎng)絡(luò)； 視頻點(diǎn)播； 流媒體；供應(yīng)者

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2008)09280405

Efficient mechanism for finding suppliers in P2P on demand streaming systems

QIN Shaohua， WU Mingsheng， WANG Qiang， SUN Guigang， XIAO Gaochao，XIAO Lili

(School of Computer Science Information Engineering， Guangxi Normal University， Guilin Guangxi 541004， China）

Abstract:This paper presented an original mechanism for finding suppliers， the server maintained a few specific peers’ information by a structure which was similar to directory. The requester was able to find peers whose playing progression was close to suppliers’ by using this information. Then by these peers’ overlapping buffer tables totheir adjacent peers， the requester could locate proper suppliers accurately. The simulation result shows that users in the mechanism require less time in join and recovery operation， and the mechanism keeps the systems message overhead small.

Key words:P2P;video on demand;media streaming;supplier

P2P流媒體點(diǎn)播系統(tǒng)是目前網(wǎng)絡(luò)應(yīng)用研究中的熱點(diǎn)。由于P2P系統(tǒng)中節(jié)點(diǎn)的動態(tài)性、點(diǎn)播系統(tǒng)中VCR操作的復(fù)雜性以及流媒體本身固有的特性，使得供應(yīng)者發(fā)現(xiàn)一直是P2P流媒體點(diǎn)播系統(tǒng)的難題?，F(xiàn)有的解決方法主要有兩種：a）基于目錄的方法，采用目錄來維護(hù)各P2P節(jié)點(diǎn)上緩存流媒體片段的信息。目錄可以集中存放^[1]，也可以分散到代理服務(wù)器或P2P節(jié)點(diǎn)上^[2]。b）基于P2P節(jié)點(diǎn)間通信的方法，讓節(jié)點(diǎn)維護(hù)用于追蹤供應(yīng)者的信息，通過節(jié)點(diǎn)間的直接通信來發(fā)現(xiàn)供應(yīng)者^[3]。文獻(xiàn)[4～6]也體現(xiàn)了節(jié)點(diǎn)直接通信的思想。

基于目錄的供應(yīng)者發(fā)現(xiàn)由單個服務(wù)器承擔(dān)整個系統(tǒng)的發(fā)現(xiàn)任務(wù)^[1]，服務(wù)器要維護(hù)每個P2P節(jié)點(diǎn)的信息，容易形成瓶頸。盡管將目錄分散到代理服務(wù)器或節(jié)點(diǎn)上^[2]，可以降低服務(wù)器的資源消耗，但是目錄的維護(hù)較為復(fù)雜。在基于P2P節(jié)點(diǎn)間直接通信的方法^[3]中，節(jié)點(diǎn)維護(hù)其鄰近節(jié)點(diǎn)的信息及部分非鄰近節(jié)點(diǎn)的信息，承擔(dān)整個系統(tǒng)的發(fā)現(xiàn)任務(wù)，節(jié)點(diǎn)的加入和恢復(fù)操作耗時較長。本文提出一種新的供應(yīng)者發(fā)現(xiàn)方法，將基于目錄的方法與基于P2P節(jié)點(diǎn)通信的方法有效結(jié)合起來，服務(wù)器用類似目錄的結(jié)構(gòu)維護(hù)系統(tǒng)中少量特定P2P節(jié)點(diǎn)的信息，各P2P節(jié)點(diǎn)上維護(hù)緩存內(nèi)容與自己交迭（overlapping buffer）的部分節(jié)點(diǎn)地址信息；通過服務(wù)器上維護(hù)的信息來鎖定與供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)，再通過這些節(jié)點(diǎn)上維護(hù)的信息與其鄰近節(jié)點(diǎn)直接通信以進(jìn)一步確定供應(yīng)者。該方法簡稱為DOB方法(directory and overlapping bufferbased approach)。在該方法中，源服務(wù)器上僅維護(hù)少量節(jié)點(diǎn)的信息，可以節(jié)省存儲空間及操作時間；P2P節(jié)點(diǎn)不維護(hù)非鄰近節(jié)點(diǎn)的信息，可以降低系統(tǒng)的通信負(fù)擔(dān)，加快節(jié)點(diǎn)的加入和恢復(fù)操作。

1 系統(tǒng)模型

在進(jìn)行本文討論之前，首先說明幾個假設(shè)：a）系統(tǒng)中僅有一個源服務(wù)器，并且是已知的；b）各P2P節(jié)點(diǎn)請求訪問同一個視頻對象；c）一個需求者只從一個供應(yīng)者獲得流服務(wù)。注意，以上不是DOB方法的限定條件，將它們擴(kuò)展到多個的情況是容易的。另外，假設(shè)各個P2P節(jié)點(diǎn)上的緩沖器大小都為B。

1.1 相關(guān)基礎(chǔ)理論知識

在文獻(xiàn)[1，7]中，需求者直接從P2P節(jié)點(diǎn)的緩沖器中獲得流媒體片段。這需要滿足兩個基本條件：a）需求者的緩存內(nèi)容與供應(yīng)者的緩存內(nèi)容必須交迭；b）需求者要維護(hù)供應(yīng)者的地址信息。

如果兩個節(jié)點(diǎn)播放進(jìn)度的間距小于B，就稱兩個緩存器交迭，那么先播放的節(jié)點(diǎn)就可以提供其緩存的流媒體片段給后播放的節(jié)點(diǎn)。在圖1中使用滑動窗口描述緩存內(nèi)容交迭的關(guān)系，將視頻播放看成時間軸，每個節(jié)點(diǎn)抽象成時間軸上的一個點(diǎn)。此點(diǎn)所在時間軸的位置指示該節(jié)點(diǎn)的當(dāng)前播放進(jìn)度，將這種點(diǎn)稱為視頻點(diǎn)。每個節(jié)點(diǎn)將它下載的流數(shù)據(jù)在其緩沖器中保存一段時間（長度為B）后再播放，且播放后就刪除。例如圖1中的節(jié)點(diǎn)i，它正在視頻點(diǎn)tnow播放流，保存了從視頻點(diǎn)tnow到tnow

1.2 基本數(shù)據(jù)結(jié)構(gòu)

設(shè)計(jì)發(fā)現(xiàn)機(jī)制的關(guān)鍵是確定源服務(wù)器和P2P節(jié)點(diǎn)應(yīng)該分別維護(hù)哪些信息及其數(shù)據(jù)結(jié)構(gòu)，以便高效地發(fā)現(xiàn)供應(yīng)者。在DOB方法中，各P2P節(jié)點(diǎn)上要維護(hù)兩類信息：第一類描述節(jié)點(diǎn)間流媒體片段的供需關(guān)系；第二類描述各P2P節(jié)點(diǎn)緩存內(nèi)容的交迭關(guān)系。這些關(guān)系可以通過建立流供需表和OB（overlapping buffer）表來實(shí)現(xiàn)，如圖2所示。

流供需表維護(hù)本地節(jié)點(diǎn)供應(yīng)者的信息和那些從該節(jié)點(diǎn)獲取服務(wù)的需求者信息。流供需表中的供需關(guān)系將節(jié)點(diǎn)連接成以源服務(wù)器為根的樹，如圖3所示。在一個子樹中，父子間的緩沖器是交迭的。兩個相脫節(jié)的子樹表示沒有節(jié)點(diǎn)緩存中間的流數(shù)據(jù)。結(jié)果，左邊子樹不能下載來自右邊子樹的流數(shù)據(jù)，必須直接從源服務(wù)器獲得流數(shù)據(jù)。將每個子樹中的所有節(jié)點(diǎn)稱為一個群，群中最先播放視頻的P2P節(jié)點(diǎn)稱為頭節(jié)點(diǎn)；最后播放視頻的P2P節(jié)點(diǎn)稱為尾節(jié)點(diǎn)。在圖3中，A1是頭節(jié)點(diǎn)，A2是尾節(jié)點(diǎn)。

OB表用來跟蹤緩存內(nèi)容相互交迭的P2P節(jié)點(diǎn)信息。這些節(jié)點(diǎn)分為向前節(jié)點(diǎn)與向后節(jié)點(diǎn)。時間軸上位于本地節(jié)點(diǎn)左邊的節(jié)點(diǎn)稱為向前節(jié)點(diǎn)；位于本地節(jié)點(diǎn)右邊的節(jié)點(diǎn)稱為向后節(jié)點(diǎn)。各P2P節(jié)點(diǎn)的OB表中的鄰居關(guān)系將一個群中的節(jié)點(diǎn)連接成一個網(wǎng)，如圖1所示。在單個網(wǎng)里，能夠通過OB表中的信息在節(jié)點(diǎn)間移動，以便查找供應(yīng)者。只要兩個節(jié)點(diǎn)位于同一個網(wǎng)中，一個節(jié)點(diǎn)就可以通過OB表中的信息發(fā)現(xiàn)另一個節(jié)點(diǎn)。

因?yàn)樵谕ǔ２シ拍Ｊ较孪炔シ殴?jié)點(diǎn)與后播放節(jié)點(diǎn)是在同速下播放媒體流的，兩節(jié)點(diǎn)的播放進(jìn)度間隔為恒值，所以在兩者間建立的供需關(guān)系和交迭關(guān)系是相對穩(wěn)定的，維護(hù)負(fù)擔(dān)較輕。

下面討論服務(wù)器上要維護(hù)的數(shù)據(jù)結(jié)構(gòu)。從上面的敘述容易發(fā)現(xiàn)，OB表不能完全解決供應(yīng)者發(fā)現(xiàn)的問題，一個請求不能穿越相互脫節(jié)的網(wǎng)來發(fā)現(xiàn)供應(yīng)者。而且，即使將相互脫節(jié)的網(wǎng)連接起來，發(fā)現(xiàn)操作仍面臨性能問題，即通過OB表中的信息在節(jié)點(diǎn)間移動的速度太慢了。所以，系統(tǒng)需要維護(hù)其他信息，以便迅速跳到不同視頻點(diǎn)。解決這個問題的方法是在服務(wù)器上維護(hù)一個類似目錄的結(jié)構(gòu)。在每個群中選出少量P2P節(jié)點(diǎn)來幫助供應(yīng)者的發(fā)現(xiàn)，這些節(jié)點(diǎn)稱為幫助節(jié)點(diǎn)。源服務(wù)器要創(chuàng)建一個線性表，此線性表采用順序表示，每個數(shù)據(jù)元素只有一個數(shù)據(jù)項(xiàng)，此數(shù)據(jù)項(xiàng)的類型是一個指向幫助節(jié)點(diǎn)的指針。該線性表含有一個位于第0行的頭數(shù)據(jù)元素，位于第1行的第一個數(shù)據(jù)元素指向從時間0到t的幫助節(jié)點(diǎn)，位于第2行的第二個數(shù)據(jù)元素指向從時間t到2t的幫助節(jié)點(diǎn)，依此類推。其中，t是線性表每行負(fù)責(zé)的視頻長度。

幫助節(jié)點(diǎn)的選擇方法如圖4所示。在一個群中，頭節(jié)點(diǎn)作為頭幫助節(jié)點(diǎn)，尾節(jié)點(diǎn)作為尾幫助節(jié)點(diǎn)，與頭節(jié)點(diǎn)距離最接近d(2B≤d，d+B≤T)的整數(shù)倍的節(jié)點(diǎn)作為中間幫助節(jié)點(diǎn)。其中，d是幫助節(jié)點(diǎn)間的設(shè)定距離，每個幫助節(jié)點(diǎn)負(fù)責(zé)的視頻長度不大于d+B。服務(wù)器中線性表每行所管理的幫助節(jié)點(diǎn)按播放進(jìn)度從小到大的順序進(jìn)行鏈?zhǔn)酱鎯Α椭?jié)點(diǎn)的節(jié)點(diǎn)結(jié)構(gòu)如圖5所示，主要信息包括幫助節(jié)點(diǎn)的類型﹑此節(jié)點(diǎn)被選為幫助節(jié)點(diǎn)時的系統(tǒng)時間TBP﹑此節(jié)點(diǎn)被選為幫助節(jié)點(diǎn)時的播放進(jìn)度PBP和此節(jié)點(diǎn)的IP地址。圖5顯示了用類似目錄的結(jié)構(gòu)如何維護(hù)圖4中幫助節(jié)點(diǎn)的信息。線性表的長度Nl由視頻總長度T和t共同決定：Nl=T/ t。

2 主要操作過程

本文介紹了DOB方法的體系結(jié)構(gòu)后，本章討論有關(guān)它的主要操作過程。DOB方法需要定期將線性表每個數(shù)據(jù)元素中的數(shù)據(jù)后移一行，以便從線性表中移除期滿的最后一行中的幫助節(jié)點(diǎn)信息。本文用TPR表示線性表所有數(shù)據(jù)元素向后平移一行的周期，則TPR＝ t。假設(shè)上次線性表數(shù)據(jù)元素后移一行的時間為TLT，現(xiàn)在時間是TC，

2.1 查找過程

假設(shè)要在視頻點(diǎn)tB播放的P2P節(jié)點(diǎn)查找一個供應(yīng)者。系統(tǒng)中可以充當(dāng)服務(wù)器的P2P節(jié)點(diǎn)的播放進(jìn)度在(tB，tB+B)內(nèi)，覆蓋（tB，tB+B)的幫助節(jié)點(diǎn)在(tB-(d+B) / 2 ， tB+(d+3B) / 2)內(nèi)。下面鎖定該范圍內(nèi)的所有幫助節(jié)點(diǎn)，步驟如下：a）設(shè)n1、n2已為兩個整數(shù)，令n1=「[tB-(d+B)/2-TC+TLT]/t；n2=「[tB+(d+3B)/2-TC+TLT]/ t，則n1和n2分別為負(fù)責(zé)范圍(tB-(d+B)/2，tB+(d+3B)/2)的最小行數(shù)和最大行數(shù)；b）對于從第n1行到第n2行的每個幫助節(jié)點(diǎn)，根據(jù)其TBP和PBP得出現(xiàn)在播放進(jìn)度，從而可以判斷其是否為(tB-(d+B)/2，tB+(d+3B)/2)內(nèi)的幫助節(jié)點(diǎn)。鎖定了幫助節(jié)點(diǎn)，也就是鎖定了與目標(biāo)供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)。如果不存在符合要求的幫助節(jié)點(diǎn)，就要直接從源服務(wù)器獲得流服務(wù)。

鎖定幫助節(jié)點(diǎn)后，通過幫助節(jié)點(diǎn)及其鄰居的OB表就可以發(fā)現(xiàn)(tB，tB+B)內(nèi)的所有節(jié)點(diǎn)。根據(jù)從候選節(jié)點(diǎn)到需求者的時間延遲、候選節(jié)點(diǎn)與需求者間的帶寬、候選節(jié)點(diǎn)的計(jì)算能力、候選節(jié)點(diǎn)的壽命和可信度，從候選節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)作為供應(yīng)者。如果不存在滿足要求的節(jié)點(diǎn)，就要直接從源服務(wù)器獲得流服務(wù)。因?yàn)閺牡讵玭1行到第n2行幫助節(jié)點(diǎn)個數(shù)的上界為2×(n2-n1+1)×t/B，而n2-n1的最大值為2，所以鎖定幫助節(jié)點(diǎn)的最壞時間復(fù)雜度為O(t/B)。此操作所得幫助節(jié)點(diǎn)個數(shù)的上界為2×(d+2B)/B，但排除這種單節(jié)點(diǎn)群的特殊情況后，所得幫助節(jié)點(diǎn)的個數(shù)一般不大于3。

2.2 加入過程

一個新節(jié)點(diǎn)加入系統(tǒng)的過程可以分成三個步驟：a）發(fā)現(xiàn)供應(yīng)者；b）建立流供需表和OB表信息；c）必要時建立或調(diào)整幫助節(jié)點(diǎn)信息。

假設(shè)一個新節(jié)點(diǎn)N想播放視頻點(diǎn)tB的流媒體片段。首先執(zhí)行查找操作，得到新節(jié)點(diǎn)的供應(yīng)者，查找過程如2.1節(jié)所述；然后根據(jù)查找結(jié)果可以分為三種情況來進(jìn)行處理：

a)需要建立一個新的單點(diǎn)群，N的供應(yīng)者為源服務(wù)器，需求者表格和OB表均為空。N既充當(dāng)頭幫助節(jié)點(diǎn)又充當(dāng)尾幫助節(jié)點(diǎn)；TBP為執(zhí)行加入操作時的系統(tǒng)時間；

b)N成為一個群的頭節(jié)點(diǎn)，供應(yīng)者為源服務(wù)器，需求者為該群原來的頭節(jié)點(diǎn)。OB表的向后節(jié)點(diǎn)項(xiàng)為空，向前節(jié)點(diǎn)信息要通過與此群原來的頭節(jié)點(diǎn)交換信息來建立。因?yàn)轭^幫助節(jié)點(diǎn)的更換，此群的中間幫助節(jié)點(diǎn)也要重新選擇。此群的尾幫助節(jié)點(diǎn)信息保持不變。

c)查找得到一個節(jié)點(diǎn)P可充當(dāng)N的供應(yīng)者，P也把N加為它的需求者。N的其他信息的確定分類處理：(a)通過P的OB表判斷發(fā)現(xiàn)N并非此群的尾節(jié)點(diǎn)，這時N的需求者表格為空，N的OB表信息要通過P及其鄰居的OB表來建立。如果視頻點(diǎn)tB與頭幫助節(jié)點(diǎn)的距離比負(fù)責(zé)tB的幫助節(jié)點(diǎn)與頭幫助節(jié)點(diǎn)的距離更加接近d的整數(shù)倍，那么N就成為幫助節(jié)點(diǎn)來代替負(fù)責(zé)tB的幫助節(jié)點(diǎn)。(b)N為群的尾節(jié)點(diǎn)，且通過查找發(fā)現(xiàn)在(tB-B，tB)內(nèi)不存在另一個群，這時N的需求者表格為空，OB表的向前節(jié)點(diǎn)項(xiàng)為空，向后節(jié)點(diǎn)信息要通過P及其鄰居的OB表來建立，還要把此群的尾幫助節(jié)點(diǎn)改為N；然后判斷是否需要增加一個新的中間幫助節(jié)點(diǎn)。方法如下：如果原群的尾節(jié)點(diǎn)Otail與頭節(jié)點(diǎn)的距離比N與頭節(jié)點(diǎn)的距離更接近d的整數(shù)倍，且Otail與上一個幫助節(jié)點(diǎn)的距離與d之差的絕對值小于等于B，則需要增加一個新的中間幫助節(jié)點(diǎn)Otail；否則，就不需要增加新的中間幫助節(jié)點(diǎn)。(c)N為群的尾節(jié)點(diǎn)，并且通過查找發(fā)現(xiàn)在（tB-B，tB)內(nèi)有另一個群，這時就相當(dāng)于N把兩個群連接成一個群。N的需求者為左邊群的頭節(jié)點(diǎn)，N的OB表要通過與供應(yīng)者和需求者交換信息來建立，還要更新從N的上一個幫助節(jié)點(diǎn)到新群尾節(jié)點(diǎn)之間的所有中間幫助節(jié)點(diǎn)信息。

23 離開過程

當(dāng)一個節(jié)點(diǎn)C要離開時，在真正切斷它之前，要通知與其聯(lián)系的節(jié)點(diǎn)（包括C的供應(yīng)者﹑需求者和OB表中的節(jié)點(diǎn)），以便這些節(jié)點(diǎn)可對C的離開作出反應(yīng)，將C從其相應(yīng)表格中刪除。但是有些節(jié)點(diǎn)的離開要作特殊處理：

a）當(dāng)C為頭節(jié)點(diǎn)時，需要在OB表的向前節(jié)點(diǎn)中尋找一個新的頭節(jié)點(diǎn)，讓它直接從源服務(wù)器獲得流服務(wù)，還要以新頭節(jié)點(diǎn)為準(zhǔn)來調(diào)整此群的幫助節(jié)點(diǎn)信息。

b）當(dāng)C為中間幫助節(jié)點(diǎn)時，要通過C的OB表尋找一個新的中間幫助節(jié)點(diǎn)來代替C。

c）當(dāng)C為尾節(jié)點(diǎn)時，要在OB表的向后節(jié)點(diǎn)中尋找一個新的尾節(jié)點(diǎn)Ntail，并考慮是否減少一個中間幫助節(jié)點(diǎn)。方法如下：如果Ntail是原群中的中間幫助節(jié)點(diǎn)，則需要減少一個中間幫助節(jié)點(diǎn)Ntail；否則，就無須減少中間幫助節(jié)點(diǎn)。

d）如果C的OB表中向前節(jié)點(diǎn)和向后節(jié)點(diǎn)的緩沖器所緩存的內(nèi)容不交迭，那么刪除C時原來群就被分為兩個新的群，如圖4中的B2。這種情況下對時間軸上C左邊的群執(zhí)行a）的操作，右邊的群執(zhí)行c）的操作。

e）當(dāng)C所在群僅有C一個節(jié)點(diǎn)時，要將此群的頭幫助節(jié)點(diǎn)信息和尾幫助節(jié)點(diǎn)信息從服務(wù)器中刪除。

24 VCR拖動過程

節(jié)點(diǎn)執(zhí)行拖動操作時，線性表處理目標(biāo)視頻點(diǎn)很遠(yuǎn)的情況，可以快速鎖定與供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)；OB表處理目標(biāo)視頻點(diǎn)鄰近的情況，可以確定充當(dāng)供應(yīng)者的節(jié)點(diǎn)。設(shè)定一個常量D（D≥(d+B)/2），根據(jù)目標(biāo)視頻點(diǎn)與本地視頻點(diǎn)之間的距離與D比較的結(jié)果，確定是只通過OB表查找供應(yīng)者，還是直接請求源服務(wù)器。

假設(shè)在視頻點(diǎn)t1播放的節(jié)點(diǎn)C想跳到另一視頻點(diǎn)t2。當(dāng)｜t1-t2｜＞D時，C要直接詢問源服務(wù)器，執(zhí)行查找操作來發(fā)現(xiàn)供應(yīng)者。當(dāng)｜t2-t1｜≤D時，C可以通過OB表逐漸向供應(yīng)者靠近。如果C與目標(biāo)供應(yīng)者在同一個群中，C只通過OB表就可以找到它；如果不在同一個群中，C就直接詢問源服務(wù)器，執(zhí)行查找操作來發(fā)現(xiàn)目標(biāo)供應(yīng)者。一旦發(fā)現(xiàn)目標(biāo)供應(yīng)者，接著要執(zhí)行加入操作的步驟b）c）來完成移動過程。

25 恢復(fù)及維護(hù)過程

當(dāng)一個節(jié)點(diǎn)收到其供應(yīng)者的離開消息或它發(fā)現(xiàn)其供應(yīng)者失效時，需要恢復(fù)來發(fā)現(xiàn)新的供應(yīng)者。因?yàn)榇斯?jié)點(diǎn)已經(jīng)在系統(tǒng)中，其鄰居都緩存了接近它播放進(jìn)度的媒體內(nèi)容，即此節(jié)點(diǎn)潛在的供應(yīng)者恰在其鄰居中，此節(jié)點(diǎn)只需向其OB表中的向后節(jié)點(diǎn)發(fā)出請求，并在其中選擇一個新的供應(yīng)者。如果通過OB表沒有發(fā)現(xiàn)供應(yīng)者，恢復(fù)節(jié)點(diǎn)就要執(zhí)行查找操作。

執(zhí)行維護(hù)操作時，服務(wù)器需要檢查幫助節(jié)點(diǎn)的活性并更換失效的幫助節(jié)點(diǎn)；各P2P節(jié)點(diǎn)要檢查其流供需表和OB表中節(jié)點(diǎn)的活性，并刪除或更換無效的信息。

3 實(shí)驗(yàn)結(jié)果與性能比較

在P2P流媒體點(diǎn)播系統(tǒng)中，可以采用以下指標(biāo)來評估系統(tǒng)的性能：

a）源服務(wù)器負(fù)載。直接從源服務(wù)器獲得流服務(wù)的P2P節(jié)點(diǎn)個數(shù)。為了提高系統(tǒng)的伸縮性，應(yīng)該盡量降低源服務(wù)器的瓶頸影響。因?yàn)橄⑺加玫膸掃h(yuǎn)小于流媒體數(shù)據(jù)所占用的帶寬，所以要想降低源服務(wù)器的瓶頸影響，必須盡量減少直接從源服務(wù)器獲得流服務(wù)節(jié)點(diǎn)的個數(shù)。在本實(shí)驗(yàn)中，記下實(shí)驗(yàn)期間源服務(wù)器負(fù)載的最大值進(jìn)行比較。

b)供需延遲。供應(yīng)者與需求者間的時間延遲。時間延遲越小，發(fā)現(xiàn)機(jī)制性能越好。在本實(shí)驗(yàn)中，比較供應(yīng)者與需求者間時間延遲的平均值，這個量反映發(fā)現(xiàn)機(jī)制所生成流供需樹的質(zhì)量。c）查找時間。從一個P2P節(jié)點(diǎn)開始加入系統(tǒng)到它的供應(yīng)者被確定所用的時間。

d）恢復(fù)時間。從一個P2P節(jié)點(diǎn)的供應(yīng)者離開系統(tǒng)或失效到它發(fā)現(xiàn)一個新的供應(yīng)者所用的時間。

e）加入消息數(shù)。用來統(tǒng)計(jì)節(jié)點(diǎn)加入時查找操作所引起消息的個數(shù)。

f）恢復(fù)消息數(shù)。用來統(tǒng)計(jì)恢復(fù)操作所引起消息的個數(shù)。

g）維護(hù)消息數(shù)。用來統(tǒng)計(jì)維護(hù)操作所引起消息的個數(shù)。

3.1 仿真設(shè)置

在DOB方法的仿真中，設(shè)定播放整個視頻所需的時間為7 200 s，每個實(shí)驗(yàn)的仿真時間也為7 200 s。測定恢復(fù)時間和恢復(fù)消息數(shù)時，P2P節(jié)點(diǎn)的離開率設(shè)為20%；測定其他量時節(jié)點(diǎn)既不離開系統(tǒng)，也不失效。在實(shí)驗(yàn)中，分別改變緩沖器的大小和節(jié)點(diǎn)的個數(shù)，每種設(shè)置組合使用三個不同的由GTITM ^[8]產(chǎn)生的網(wǎng)絡(luò)拓?fù)淠M三次。同時，也對文獻(xiàn)[3]中的發(fā)現(xiàn)機(jī)制OBN進(jìn)行相應(yīng)模擬，以便將DOB方法與OBN進(jìn)行比較。表1列出在仿真DOB方法和OBN時設(shè)置的一些主要參數(shù)。

表1 仿真設(shè)置

參數(shù)值參數(shù)值

仿真時間7 200 sOB表大小8 peers(前后各4 peers)

視頻長度7 200 s緩沖器大小15，30，45，60 s

網(wǎng)絡(luò)大小1 000，4 000nodes維護(hù)周期60 s

另外，設(shè)OBN的指針表(finger table)至多容納14 peers的信息；DOB方法中B、d、t之間的關(guān)系設(shè)定為2B=d，d+B=t (注意：不是必須滿足這些關(guān)系)。

3.2 比較結(jié)果

32.1 源服務(wù)器負(fù)載

從圖6可以看出DOB方法源服務(wù)器負(fù)載的幾個特點(diǎn)：

a）隨著緩沖器的增大，源服務(wù)器負(fù)載降低。這是因?yàn)楫?dāng)緩沖器增大時，緩沖器所能緩存的流數(shù)據(jù)增多，節(jié)點(diǎn)成為供應(yīng)者的可能性增大，直接從源服務(wù)器獲得服務(wù)的節(jié)點(diǎn)數(shù)就減小。

b）隨著節(jié)點(diǎn)數(shù)的增加，源服務(wù)器負(fù)載降低。原因是系統(tǒng)中節(jié)點(diǎn)的數(shù)越大，可以為一個需求者提供流服務(wù)的節(jié)點(diǎn)就越多。所以，DOB方法有較好的擴(kuò)充性。

圖6還可以看出，DOB方法和OBN的源服務(wù)器負(fù)載接近，原因是這兩種發(fā)現(xiàn)機(jī)制在查找供應(yīng)者時都未對請求的最大跳數(shù)進(jìn)行限制，都將源服務(wù)器負(fù)載最小作為自己的首要目的。另外，DOB方法的源服務(wù)器負(fù)載略微小于OBN，原因是在OBN中指針表不能保證聯(lián)絡(luò)所有群，而在DOB方法中利用了線性表每行所指向的鏈結(jié)構(gòu)來輕松處理群之間通信的問題。

32.2 供需延遲

從圖7可以看出，使用DOB方法時隨著緩沖器的增大，節(jié)點(diǎn)數(shù)的增加，平均供需延遲降低。這是因?yàn)楫?dāng)緩沖器增大或節(jié)點(diǎn)增多時，一個需求者可以發(fā)現(xiàn)較多候選供應(yīng)者，從而能夠發(fā)現(xiàn)帶有較低供需延遲的供應(yīng)者。

從圖7還可以看出DOB方法的平均供需延遲略微小于OBN，原因是OBN在處理群之間的通信時不夠理想。

323 查找時間

從圖8可以看出，使用DOB方法時隨著緩沖器的增大，節(jié)點(diǎn)數(shù)的增加，查找時間略微升高，不過幅度很小。原因是影響查找時間的主要因素是請求消息需要的跳數(shù)，當(dāng)緩沖器增大或節(jié)點(diǎn)增多時，節(jié)點(diǎn)加入系統(tǒng)時要經(jīng)過較多跳數(shù)才能到達(dá)合適的供應(yīng)者，這樣就要經(jīng)過較多時間來完成查找過程。

從圖8還可以看出DOB方法的查找時間遠(yuǎn)小于OBN的查找時間。這是因?yàn)榘l(fā)現(xiàn)機(jī)制OBN在鎖定與目標(biāo)供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)時要在整個網(wǎng)絡(luò)中進(jìn)行一個復(fù)雜度為O(lg T)的跳躍過程，并且在所經(jīng)過的每個節(jié)點(diǎn)上進(jìn)行一個復(fù)雜度為O(lg T)的查詢過程。其中：T為播放整個視頻所用的時間。DOB方法在鎖定與目標(biāo)供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)時僅僅在服務(wù)器上進(jìn)行一個復(fù)雜度為O(t/B)的查詢過程。如果B、t選擇得當(dāng)，O(t/B)會遠(yuǎn)小于O(lg T)。在進(jìn)一步確定充當(dāng)供應(yīng)者的節(jié)點(diǎn)時，兩種方法所用的時間基本相等。

324 恢復(fù)時間

在本實(shí)驗(yàn)中，設(shè)定超時周期為400 ms。從圖9可以看出恢復(fù)時間遠(yuǎn)大于查找時間，主要原因在于兩個方面：a）當(dāng)一個節(jié)點(diǎn)失效時，它的需求者需要花費(fèi)400 ms的時間發(fā)現(xiàn)此失效；b）當(dāng)恢復(fù)節(jié)點(diǎn)發(fā)出一個恢復(fù)請求時，此請求可能傳給一個失效節(jié)點(diǎn)，這就需要另外400 ms的時間來發(fā)現(xiàn)被請求節(jié)點(diǎn)的失效。

從圖9還可以看出，使用DOB方法時隨著節(jié)點(diǎn)數(shù)的增加，緩沖器的增大，恢復(fù)時間略微減少。這是因?yàn)殡S著節(jié)點(diǎn)數(shù)目的增加，緩沖器的增大，候選供應(yīng)者的數(shù)目就會增加，請求者發(fā)現(xiàn)供應(yīng)者的機(jī)會變大，于是降低了恢復(fù)時間。

比較兩個系統(tǒng)的恢復(fù)時間可以發(fā)現(xiàn)，DOB方法所用的恢復(fù)時間小于OBN。一個主要原因是當(dāng)通過OB表沒有發(fā)現(xiàn)供應(yīng)者時，恢復(fù)節(jié)點(diǎn)就要執(zhí)行查找操作，而DOB方法的查找時間遠(yuǎn)小于OBN的查找時間。

325 加入消息數(shù)

從圖10可以看出，使用DOB方法時隨著緩沖器的增大，節(jié)點(diǎn)數(shù)的增加，加入消息數(shù)增加。這是因?yàn)楫?dāng)緩沖器增大或節(jié)點(diǎn)增多時，加入節(jié)點(diǎn)就需要與較多的節(jié)點(diǎn)進(jìn)行通信，這就產(chǎn)生了較多的通信消息。

比較兩個系統(tǒng)的加入消息數(shù)可以發(fā)現(xiàn)，DOB方法的加入消息數(shù)比OBN的要小得多。原因是發(fā)現(xiàn)機(jī)制OBN在鎖定與目標(biāo)供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)時要在整個網(wǎng)絡(luò)中進(jìn)行一個復(fù)雜度為O(lg T)的跳躍過程，也就是最多要與lg T個節(jié)點(diǎn)進(jìn)行通信；而DOB方法在鎖定與目標(biāo)供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)時無須與節(jié)點(diǎn)進(jìn)行通信，并且在進(jìn)一步確定充當(dāng)供應(yīng)者的節(jié)點(diǎn)時，兩種發(fā)現(xiàn)機(jī)制的通信消息數(shù)接近相等。

326 恢復(fù)消息數(shù)

從圖11可以看出，使用DOB方法時隨著緩沖器的增大，節(jié)點(diǎn)的增多，恢復(fù)消息數(shù)增加。這是因?yàn)楫?dāng)緩沖器增大或節(jié)點(diǎn)增多時，候選供應(yīng)者的數(shù)目增加，恢復(fù)節(jié)點(diǎn)就需要與較多的候選供應(yīng)者進(jìn)行通信，這就產(chǎn)生了較多的通信消息。

從圖11還可以看出，DOB方法的恢復(fù)消息數(shù)小于OBN。一個原因是當(dāng)通過OB表沒有發(fā)現(xiàn)供應(yīng)者時，恢復(fù)節(jié)點(diǎn)就要執(zhí)行查找操作，而DOB方法的加入消息數(shù)遠(yuǎn)小于OBN的加入消息數(shù)。

327 維護(hù)消息數(shù)

從圖12可以看出，DOB方法維護(hù)消息數(shù)的幾個特點(diǎn)：

a）隨著緩沖器的增大，維護(hù)消息數(shù)幾乎沒有改變。原因是維護(hù)操作主要是對各個表格所保存信息活性的確認(rèn)，并且實(shí)驗(yàn)中對每個節(jié)點(diǎn)的OB表中可以容納的peer個數(shù)進(jìn)行了限定。節(jié)點(diǎn)數(shù)的增加，維護(hù)消息數(shù)增加。這是因?yàn)楫?dāng)節(jié)點(diǎn)數(shù)增加時，整個系統(tǒng)中表格所保存的信息總量增加，這樣對整個系統(tǒng)進(jìn)行維護(hù)就需要確認(rèn)較多信息的活性。

從圖12還可以看出DOB方法的維護(hù)消息數(shù)接近OBN維護(hù)消息數(shù)的一半。這是因?yàn)樵贒OB方法中節(jié)點(diǎn)無須維護(hù)非鄰居節(jié)點(diǎn)的信息。

4 結(jié)束語

為了解決P2P流媒體點(diǎn)播系統(tǒng)中供應(yīng)者發(fā)現(xiàn)的問題，提高流媒體服務(wù)的質(zhì)量，本文采用基于目錄及P2P節(jié)點(diǎn)間通信相結(jié)合的方法，在源服務(wù)器上維護(hù)少量的P2P節(jié)點(diǎn)信息來鎖定與目標(biāo)供應(yīng)者播放進(jìn)度接近的節(jié)點(diǎn)；在各P2P節(jié)點(diǎn)上維護(hù)鄰居節(jié)點(diǎn)的信息，通過鄰居節(jié)點(diǎn)間的消息交換進(jìn)一步確定充當(dāng)供應(yīng)者的節(jié)點(diǎn)。

仿真實(shí)驗(yàn)的結(jié)果顯示出DOB方法的主要優(yōu)點(diǎn)在于兩個方面：a）節(jié)點(diǎn)在執(zhí)行加入和恢復(fù)操作時，耗時明顯少于發(fā)現(xiàn)機(jī)制OBN；b）整個系統(tǒng)的通信負(fù)擔(dān)約為OBN的一半。雖然DOB方法中類似目錄結(jié)構(gòu)的維護(hù)負(fù)擔(dān)稍微大于OBN中入口節(jié)點(diǎn)表(entrance peer list)的維護(hù)負(fù)擔(dān)，且對目錄的操作比對入口節(jié)點(diǎn)表的操作復(fù)雜，但是這對于典型的流媒體服務(wù)器是可以接受的。所以，實(shí)驗(yàn)結(jié)果肯定了DOB方法的有效性。

下一步要考慮的問題包括：在已知B時如何設(shè)定d和t的值才能使系統(tǒng)的性能最佳；如何使用DOB方法確保供應(yīng)者的質(zhì)量最好。

參考文獻(xiàn)：

[1]JIN S，BESTAVROS A.Cacheandrelay streaming media delivery for asynchronous clients[C]//Proc of International Workshop on Networked Group Communication. 2002.

[2]GUO Lei，CHEN Songqing，REN Shansi，et al. PROP: a scalable and reliable P2P assisted proxy streaming system[C]//Proc of the 24th International Conference on Distributed Computing Systems. 2004:778786.

[3]LIAO Chishiang，SUN Wenhung，KING Chungta， et al. OBN:peering for finding suppliers in P2P ondemand streaming systems[C]//Proc of IEEE Int’l Conf on Parallel and Distributed Systems. 2006:235242.

[4]GUO Yang，SUH K， KUROSE J， et al.P2Cast:peertopeer patching scheme for VoD service[C]// Proc ofInternational WWW Conference.New York: ACM Press，2003:301309.

[5]TRAN D A，HUA K A，DO T T. ZIGZAG: an efficient peertopeer scheme for media streaming[C]// Proc of IEEE INFOCOM. 2003:12831292. 

[6]ZHANG Xinyan，LIU Jiangchuan， LI B，et al. Cool streaming/DONet: a datadriven overlay network for efficient live media streaming[C]// Proc of IEEE INFOCOM.2005.

[7]SHEU S，HUA K A，TAVANAPONG W. Chaining: a generalized batching technique for videoondemand system[C]// Proc of IEEE International Conference on Multimedia Computing and Systems.1997:110117.

[8]ZEGURA E W，CALVERT K L，BHATTACHARJEE S. How to model an internetwork[C]// Procof IEEE INFOCOM.1996:594602.