摘要：針對當(dāng)前樹狀流媒體系統(tǒng)結(jié)構(gòu)由于結(jié)構(gòu)與算法復(fù)雜而造成的視頻塊傳輸延遲問題，邏輯網(wǎng)絡(luò)與物理網(wǎng)絡(luò)拓?fù)涫涞葐栴}，該文提出了一種流媒體樹狀結(jié)構(gòu)的構(gòu)建與維護(hù)算法doubletree，并且討論了該結(jié)構(gòu)改進(jìn)的DHT關(guān)鍵詞構(gòu)建方法，算法分析結(jié)果顯示doubletree可以獲得更高的傳輸效率與服務(wù)質(zhì)量。

關(guān)鍵詞：流媒體；樹狀；回放；DRPSS；DHT關(guān)鍵詞

中圖分類號(hào)：TP37 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）13-3152-03

隨著網(wǎng)絡(luò)和流媒體技術(shù)的高速發(fā)展，傳統(tǒng)的客戶端與服務(wù)器C/S（Client/Server）網(wǎng)絡(luò)結(jié)構(gòu)在客戶端增多的情況下，由于服務(wù)器與客戶端的單通道傳輸結(jié)構(gòu)，往往導(dǎo)致視頻傳輸質(zhì)量下降，服務(wù)器擁塞，甚至服務(wù)器癱瘓等問題。所以C/S網(wǎng)絡(luò)結(jié)構(gòu)已經(jīng)無法滿足流媒體系統(tǒng)中客戶端對視頻流的請求。為解決服務(wù)器瓶頸，網(wǎng)絡(luò)擴(kuò)展等問題，P2P技術(shù)應(yīng)運(yùn)而生。P2P技術(shù)是一種對等網(wǎng)絡(luò)技術(shù)，P2P網(wǎng)絡(luò)結(jié)構(gòu)中沒有中心節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)既是客戶端又是服務(wù)器。所以P2P技術(shù)可以很好的降低服務(wù)器帶寬資源和網(wǎng)絡(luò)擁塞問題，具有較高的擴(kuò)展性和性價(jià)比。

P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)大致可分為3種類型： 樹狀，網(wǎng)狀和DHT結(jié)構(gòu)。由于樹狀結(jié)構(gòu)相對于網(wǎng)狀和DHT結(jié)構(gòu)的擴(kuò)展性好，并且控制開銷較小，所以當(dāng)前很多P2P流媒體系統(tǒng)都是基于樹狀結(jié)構(gòu)建立的。代表流媒體系統(tǒng)有NICE[[1]]，Bullet[[2]]和oStream[[3]]。NICE通過分層和聚類的方式來組建大規(guī)模流媒體組播樹，提高了擴(kuò)展性，但是增加了中間節(jié)點(diǎn)的中轉(zhuǎn)壓力。Bullet和ostream分別通過節(jié)點(diǎn)間的正交協(xié)作算法和啟發(fā)式算法來構(gòu)建較小鏈路消耗的流媒體組播樹，減低了系統(tǒng)的傳輸消耗，但是算法的實(shí)現(xiàn)較為復(fù)雜，增加了系統(tǒng)傳輸?shù)臅r(shí)間延遲。

本文通過對流媒體樹狀結(jié)構(gòu)特點(diǎn)的分析，結(jié)合splitstream[[4]]流媒體系統(tǒng)的正交樹結(jié)構(gòu)思想，提出了中心化流媒體樹狀結(jié)構(gòu)。通過中心控制節(jié)點(diǎn)（根節(jié)點(diǎn)）和TT算法對流媒體樹狀結(jié)構(gòu)進(jìn)行建立和維護(hù)。

1 相關(guān)知識(shí)

1.1 流媒體樹狀結(jié)構(gòu)分析

對于樹結(jié)構(gòu)的建立和維護(hù)，應(yīng)該考慮一下幾個(gè)問題。

1）樹的規(guī)模：樹應(yīng)該盡可能的短，在根節(jié)點(diǎn)與葉子節(jié)點(diǎn)之間，中間節(jié)點(diǎn)應(yīng)盡可能少。短樹結(jié)構(gòu)將會(huì)減少由于節(jié)點(diǎn)離開和失效，父節(jié)點(diǎn)阻塞等原因造成的組播樹的崩潰。由于它的短小，每棵樹由于將會(huì)被平衡，需要可能的繁盛，例如，每個(gè)節(jié)點(diǎn)的出度將會(huì)達(dá)到它帶寬的上限，但是，由于出度的增大，也會(huì)因?yàn)槠渌鼞?yīng)用程序競爭帶寬而造成流媒體樹的崩潰。

2）樹的多樣性與有效性：組播樹應(yīng)該具有多樣性。例如，一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的集合在一棵樹中應(yīng)盡可能不相連。但是，追求多樣性將會(huì)影響擁有一棵有效的生成樹。例如，一棵樹的結(jié)構(gòu)很符合覆蓋網(wǎng)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)中的三個(gè)節(jié)點(diǎn)，一個(gè)在北京，一個(gè)在廣州，一個(gè)在香港，如果父節(jié)點(diǎn)可以相連，則樹結(jié)構(gòu)北京——廣州——香港，將會(huì)比廣州——北京——香港這個(gè)具有父子關(guān)系的樹結(jié)構(gòu)更有效。

3）節(jié)點(diǎn)的加入與離開：節(jié)點(diǎn)的加入和離開過程應(yīng)該盡可能的快，這樣才能使有興趣的節(jié)點(diǎn)盡快的加入樹結(jié)構(gòu)獲取視頻流，并且擁有最小的干擾，只需一個(gè)網(wǎng)絡(luò)來回的加入和離開過程將會(huì)是干擾最小的策略。

4）可擴(kuò)展性：樹的管理算法應(yīng)該適應(yīng)大規(guī)模節(jié)點(diǎn)數(shù)量和高速率的節(jié)點(diǎn)加入與離開。

以上問題的一些目標(biāo)是互相矛盾的，因?yàn)槲覀兛紤]流媒體應(yīng)用程序是不相關(guān)的，所以適當(dāng)?shù)难舆t是可以接受的，又因?yàn)榛謴?fù)力是流媒體結(jié)構(gòu)節(jié)點(diǎn)加入和維護(hù)的主要目標(biāo)，所以本文選擇創(chuàng)建一棵伴隨著快速的加入和離開的多樣性的短樹。

1.2 建立內(nèi)部節(jié)點(diǎn)不相交樹

2 中心控制的樹結(jié)構(gòu)和doubletree算法

為了使節(jié)點(diǎn)快速的加入和離開，該文使用了中心控制的樹管理策略，由一個(gè)中心節(jié)點(diǎn)管理樹的建立和維護(hù)，通常設(shè)置為樹的根節(jié)點(diǎn)，根節(jié)點(diǎn)一般比普通節(jié)點(diǎn)更有資源和更加有用，節(jié)點(diǎn)加入和離開操作只需要一或兩個(gè)網(wǎng)絡(luò)往返——一次去根節(jié)點(diǎn)，一次去新的父節(jié)點(diǎn)。

依賴根節(jié)點(diǎn)意味著系統(tǒng)不再是自組織的，但這只是對控制傳輸?shù)?，對于?shù)據(jù)傳輸其仍然是自擴(kuò)展的。為了避免根節(jié)點(diǎn)造成的系統(tǒng)瓶頸問題，本設(shè)計(jì)將其擴(kuò)展為一個(gè)根節(jié)點(diǎn)簇，然后隨機(jī)指定客戶端去連接其中一個(gè)根節(jié)點(diǎn)。由于整個(gè)根節(jié)點(diǎn)簇帶寬的增大，它將導(dǎo)致更短，更有效的分布樹。

2.1 樹的中心管理

根節(jié)點(diǎn)具有樹的所有管理機(jī)能，當(dāng)一個(gè)節(jié)點(diǎn)要加入時(shí)，節(jié)點(diǎn)將聯(lián)系根節(jié)點(diǎn)，根節(jié)點(diǎn)將會(huì)發(fā)送給新加入節(jié)點(diǎn)一個(gè)指定的父節(jié)點(diǎn)的信息。然后，新節(jié)點(diǎn)聯(lián)系其指定節(jié)點(diǎn)作為父節(jié)點(diǎn)接收數(shù)據(jù)流。當(dāng)一個(gè)節(jié)點(diǎn)正常離開時(shí)，它將通知根節(jié)點(diǎn)，然后根節(jié)點(diǎn)將會(huì)為離開節(jié)點(diǎn)的子節(jié)點(diǎn)找到一個(gè)新的父節(jié)點(diǎn)，并且通知雙方互相的存在。

如果是節(jié)點(diǎn)異常離開，節(jié)點(diǎn)監(jiān)視器將監(jiān)視節(jié)點(diǎn)的丟包率，如果丟包數(shù)量達(dá)到一定的上線，節(jié)點(diǎn)將會(huì)檢查其父節(jié)點(diǎn)是否也處于這種情況，如果父節(jié)點(diǎn)也處于此情況，則等待父節(jié)點(diǎn)處理此問題，如果父節(jié)點(diǎn)沒有此問題，或父節(jié)點(diǎn)失效，則節(jié)點(diǎn)將連接根節(jié)點(diǎn)獲取另一個(gè)父節(jié)點(diǎn)。

2.2 DoubleTree算法

當(dāng)一個(gè)新節(jié)點(diǎn)加入時(shí)，我們首先決定這個(gè)節(jié)點(diǎn)是作為中間節(jié)點(diǎn)或是葉子節(jié)點(diǎn)加入一棵樹中，TT算法采用與SplitStream相同的機(jī)制，即一個(gè)節(jié)點(diǎn)只在一棵樹中為內(nèi)部節(jié)點(diǎn)，而在其他樹中均為葉子節(jié)點(diǎn)。TT算法首先找出在一棵樹中中間節(jié)點(diǎn)最少的樹，然后將新節(jié)點(diǎn)作為其中間節(jié)點(diǎn)加入此樹，這樣做的目的是使中間節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)在每課樹中是平衡的。

一個(gè)新節(jié)點(diǎn)作為中間節(jié)點(diǎn)加入樹中時(shí)，首先找到根節(jié)點(diǎn)，根節(jié)點(diǎn)通過搜索其信息結(jié)合分配給新節(jié)點(diǎn)一個(gè)擁有多余帶寬的一個(gè)中間節(jié)點(diǎn)，或者有一個(gè)孩子節(jié)點(diǎn)為中間節(jié)點(diǎn)的節(jié)點(diǎn)。如果一個(gè)有多余帶寬的節(jié)點(diǎn)找到了，我們就將其作為新節(jié)點(diǎn)的父節(jié)點(diǎn)。否則，我們將指定一個(gè)一個(gè)孩子節(jié)點(diǎn)為中間節(jié)點(diǎn)的節(jié)點(diǎn)作為新節(jié)點(diǎn)的父節(jié)點(diǎn)，然后為這個(gè)孩子節(jié)點(diǎn)重新找一個(gè)父節(jié)點(diǎn)。這樣做的目的是使樹的上層擁有足夠的中間節(jié)點(diǎn)，這些節(jié)點(diǎn)可以支持子節(jié)點(diǎn)。

2.3有效性

3 算法分析

本文的doubletree算法利用根節(jié)點(diǎn)作為控制節(jié)點(diǎn)建立組播樹并對其進(jìn)行維護(hù)，中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)的加入和離開在算法中的時(shí)間復(fù)雜度只有O（1）. 而根節(jié)點(diǎn)對信息集合的搜索的時(shí)間復(fù)雜度也只有O（N）. 大大減少了網(wǎng)絡(luò)延遲度。隨著節(jié)點(diǎn)數(shù)目的增加，使得數(shù)據(jù)塊穩(wěn)定數(shù)目大幅增加，又因?yàn)橥ㄟ^改進(jìn)的pastry關(guān)鍵詞進(jìn)行搜索，獲得物理距離最近的視頻塊提供者，所以數(shù)據(jù)塊的丟失率大幅減小。

4 總結(jié)

本文提出了一種基于P2P的中心控制的組播樹建構(gòu)算法，并通過對pastry關(guān)鍵詞的設(shè)計(jì)使網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)更符合物理拓?fù)浣Y(jié)構(gòu)。最后，對doubletree算法進(jìn)行了算法分析。分析結(jié)果表明該結(jié)構(gòu)降低了搜索延遲，提高了路由效率，并且流媒體的服務(wù)質(zhì)量也得到了大幅提高。

參考文獻(xiàn)：

[1] Baner Jee S， Bhattachar Jee B， Kommareddy C. Scalable application layer multicast [J ]. ACM SIGCOMM Computer Communication Review， 2002， 32 （4）： 205-217.

[2] Dejan Kostic， Adolfo Rodriguez， Jeannie R Albrecht， et al. High bandwidth data dissemination using an overlay mesh[C]. In： Proc 19th ACM Symposium on Operating System Principles， October 2003. 282-297.

[3] Y.Cui， B.Li， K.Nahrstedt.oStream：asynchronous treaming multicast in application-layer overlay networks[J]. Selected Areas in Communications. IEEE Journal， 2004， vol.22， no.1.

[4]Miguel Castro， Peter Druschel. SplitStream：High-bandwidth content distribution in cooperative enviroments[C].In：Proc 19th ACM Symp on Operating System Principles， October 2003.

[5] Antony Rowstron， Peter Druschel. Pastry： Scalable， decentralized object location and routing for large-scale peer-to-peer systems[C]. Appears in Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Platforms （Middleware 2001）. Heidelberg， Germany， November 2001.