基于對等網(wǎng)絡(luò)的視頻點播系統(tǒng)體系結(jié)構(gòu)研究

基于對等網(wǎng)絡(luò)的視頻點播系統(tǒng)體系結(jié)構(gòu)研究

1p2p文件共享系統(tǒng)20世紀90年代，萬維網(wǎng)成功之后，人們還希望可以自由地在互聯(lián)網(wǎng)上觀看我最喜歡的視頻節(jié)目，即視頻廣播。vod系統(tǒng)基于c.s結(jié)構(gòu)。為了增加系統(tǒng)支持的用戶，降低用戶的等待時間，他提出了一系列算法，如編碼、訪問等。然而，由于網(wǎng)絡(luò)的高服務(wù)插值和延遲的特點，它很快發(fā)現(xiàn)了一個問題，即使用基于c的這種情況。因此，一個當然是想把多個服務(wù)器分散到網(wǎng)絡(luò)。當用戶加載節(jié)目時，他們可以從距離最近服務(wù)器的服務(wù)器獲得數(shù)據(jù)。這是python（渲染網(wǎng)絡(luò)）的概念，它在一定程度上提高了整個系統(tǒng)的可擴展性，但引入了一個新問題：由于需要很多服務(wù)器，整個系統(tǒng)的加載和維護都非常貴。對于這個問題，人們立即提出了一個解決方案：他們發(fā)現(xiàn)用戶終端的性能不斷提高，甚至可以達到服務(wù)器標準。因此，基于平等網(wǎng)絡(luò)的視頻點播系統(tǒng)（以下簡稱vod）出現(xiàn)了。視頻點播不是p2p技術(shù)的第一應(yīng)用程序。事實上，在此之前，基于p2p的公共音樂系統(tǒng)非常流行。第一個現(xiàn)代意義上的公共音樂系統(tǒng)由只有18歲的美國人開發(fā)。napster和音樂書籍共享很快。napster很快普及，2001年達到150萬最大在線用戶。由于版權(quán)問題，napster最終停止了運作，但它導(dǎo)致了p2p使用的高潮。此后，許多類似系統(tǒng)，如gray、kana、edony和比特幣，它們也被廣泛使用。隨著內(nèi)容共享系統(tǒng)的開放，p2p的另一個重要應(yīng)用是視頻廣播。從2004年底到2005年，基于p2p的網(wǎng)絡(luò)視頻逐漸傳播，如歡樂視頻、格列表演、音樂表演、pp音樂等。這些系統(tǒng)通過電視臺、廣播、電視表演和其他娛樂內(nèi)容網(wǎng)站而聞名。2007年，p2p的廣告取得了巨大成功，幾乎沒有人懷疑這的廣闊前景。當時，許多公司包括ppstream、pp生存、uuse、vehst、jold等，另一個更加挑戰(zhàn)的服務(wù)是p2p兩點。文件共享、視頻直播、視頻點播有一個共同的特點:耗帶寬.為了提高系統(tǒng)的可擴展性并降低成本,P2P技術(shù)成為它們的首選.但是,采用P2P技術(shù)又有一些不利的因素.例如,P2P網(wǎng)絡(luò)是動態(tài)的、不穩(wěn)定的(churning),節(jié)點的上線、下線是任意的.如果正在提供服務(wù)的節(jié)點突然下線了,將會對接收服務(wù)的節(jié)點造成影響.而且,P2P網(wǎng)絡(luò)中節(jié)點的差異性很大,如上傳帶寬,有一些校園網(wǎng)用戶可以達到100Mbps,但某些ADSL用戶可能只有幾百Kbps,甚至達不到一個視頻的平均碼率.這些因素對文件共享系統(tǒng)來說,可能只是影響文件的下載時間;但對時延敏感的視頻直播、點播應(yīng)用,卻可能造成播放不流暢,甚至無法播放的嚴重后果.視頻的直播與點播,雖然相似,但又有很多不同之處.直播更像電視,用戶只能選擇看或不看,并沒有太多的交互性;點播則更像DVD,用戶可以選擇何時播放,并且在觀看過程中可以進行暫停、恢復(fù)、拖動播放等VCR操作.因此,同一頻道不同用戶的播放進度,在直播中是相近的,而在點播中卻可能相差很大.播放進度差異的直接影響是,用戶間數(shù)據(jù)共享的機會更少.因此在實現(xiàn)上,點播比直播更具挑戰(zhàn)性.表1給出了基于P2P的視頻直播與視頻點播的一個比較.面對高帶寬、高存儲、高實時要求的VoD應(yīng)用,P2P網(wǎng)絡(luò)中有限的資源可用性的問題顯得非常突出.這表現(xiàn)在兩個方面:(1)由于節(jié)點硬件條件(帶寬、存儲)的限制,能提供的資源是有限的;(2)由于缺乏一個有效的激勵機制,節(jié)點愿提供的資源是有限的.目前,雖然已有很多大型的VoD/P2P系統(tǒng),如PPLive、PPStream、迅雷等,但它們在很大程度上依賴于服務(wù)器或CDN,因而普遍存在“成本過高、盈利困難”的問題.本文致力于研究如何在VoD應(yīng)用中發(fā)揮P2P技術(shù)的優(yōu)勢,對VoD/P2P系統(tǒng)在3個方面作綜述,也就是:(1)數(shù)據(jù)傳輸.討論如何充分地利用節(jié)點的有限帶寬;(2)數(shù)據(jù)存儲.討論如何充分地利用節(jié)點的有限存儲;(3)激勵機制.討論如何刺激節(jié)點貢獻資源.本文第2節(jié)討論VoD/P2P的數(shù)據(jù)傳輸,包括傳輸過程中的拓撲結(jié)構(gòu)以及編碼技術(shù);第3節(jié)討論VoD/P2P的數(shù)據(jù)存儲,包括存儲過程中的資源查找結(jié)構(gòu)、編碼方案以及替換策略;第4節(jié)討論VoD/P2P的激勵機制,介紹3種常見的策略;最后,第5節(jié)總結(jié)全文.2、異構(gòu)的網(wǎng)絡(luò)的設(shè)計VoD/P2P的傳輸希望解決如下的問題:如何從一個或多個源節(jié)點向多個目標節(jié)點分發(fā)數(shù)據(jù),使之在動態(tài)的、異構(gòu)的網(wǎng)絡(luò)中:(1)保證視頻的傳輸率,即目標節(jié)點的有效輸入帶寬不能小于視頻的碼率;(2)減少用戶等待時間,即用戶從發(fā)出點播請求到視頻播放的時間間隔盡可能短;(3)降低帶寬浪費,即點播不能消耗很多不必要的帶寬而影響其它應(yīng)用.近年來,對傳輸問題的研究主要集中在拓撲結(jié)構(gòu)與編碼技術(shù)兩方面.2.1組織結(jié)構(gòu)peer在早期的基于C/S結(jié)構(gòu)的點播系統(tǒng)中,人們曾希望采用IP組播技術(shù)來降低系統(tǒng)的帶寬消耗.但遺憾的是,在實際環(huán)境中,IP組播并不能很好地被支持.不過借助于P2P,IP組播可以有一個替代策略,即應(yīng)用層組播(ApplicationLayerMulticast,ALM).它的基本思想是,在應(yīng)用層,P2P網(wǎng)絡(luò)的每個節(jié)點都充當路由器的角色,將收到的數(shù)據(jù)轉(zhuǎn)發(fā)給其它多個節(jié)點.這其實是在應(yīng)用層構(gòu)建了另一個“網(wǎng)絡(luò)層”,或稱為PeerOverlay.本文接下來所說的傳輸中的拓撲結(jié)構(gòu),也就是PeerOverlay的拓撲結(jié)構(gòu).在PeerOverlay中,若每個節(jié)點最多只有一個上游節(jié)點提供數(shù)據(jù),稱這樣的拓撲為單源結(jié)構(gòu).而與此對應(yīng)的,若每個節(jié)點可以有多個上游節(jié)點提供數(shù)據(jù),稱這個拓撲為多源結(jié)構(gòu).對單源、多源結(jié)構(gòu)的一個更嚴格的定義是:P2P網(wǎng)絡(luò)中,針對某一個頻道,將其中的節(jié)點抽象為有向圖的點,將一個節(jié)點向另一個節(jié)點提供數(shù)據(jù)的鏈路抽象為有向圖的邊,則形成一個有向圖G;如果G中每個點的入度不大于1,稱G是單源結(jié)構(gòu),反之,稱G為多源結(jié)構(gòu).圖1給出了不同拓撲的PeerOverlay的例子.在VoD/P2P的早期研究中,大多數(shù)的傳輸拓撲是單源結(jié)構(gòu)的,如樹狀、鏈狀、環(huán)狀.在P2Cast中,同一頻道中到達時間相近的peer組成一個session.在每個session中,server連同這些peer構(gòu)成一棵應(yīng)用層的組播樹.那些到達時間稍晚的peer,也可以加入到某一個session中,并從這個session的server或peer取得它所錯過的數(shù)據(jù)(即補丁流).在這個系統(tǒng)中,peer的主要作用是:(1)作為組播樹的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù);(2)為后繼的peer提供補丁流.在文獻中,為了避免上游節(jié)點由于帶寬有限而成為系統(tǒng)瓶頸,作者提出了一個父子交換協(xié)議(ParentChildExchange,PCX),通過某種規(guī)則動態(tài)地交換上、下游節(jié)點,以優(yōu)化拓撲結(jié)構(gòu).為了能快速修復(fù)上游節(jié)點的失效,P2VoD將到達時間相近的節(jié)點(播放進度也相近)組織在一起,稱為一個Generation.當某節(jié)點的上游節(jié)點失效后,該失效節(jié)點所在的Generation中任何一個其它節(jié)點都可以替代失效節(jié)點,成為新的上游節(jié)點.類似的思想也出現(xiàn)在文獻中.單源結(jié)構(gòu)有很多優(yōu)點.首先,它很直觀,從而很容易對系統(tǒng)進行調(diào)試和評估;其次,當系統(tǒng)穩(wěn)定時,上游節(jié)點一般知道下游節(jié)點需要什么數(shù)據(jù),從而可以通過推模式(push-based)向下游提供數(shù)據(jù),減小端到端延遲;最后,因為拓撲簡單,單源結(jié)構(gòu)可以理論上優(yōu)化,以達到最佳的系統(tǒng)性能.但是,單源結(jié)構(gòu)又有很多不足,表現(xiàn)在:(1)資源利用率低.只有源節(jié)點與中間節(jié)點提供數(shù)據(jù),而大量的葉子節(jié)點并不提供數(shù)據(jù),它們的資源(主要是上傳帶寬)并沒有得到有效利用.這導(dǎo)致的另一個后果是負載不均衡;(2)對服務(wù)節(jié)點要求太高.單源結(jié)構(gòu)中,一個節(jié)點要提供服務(wù),它的上傳帶寬必須大于視頻碼率.由于單源結(jié)構(gòu)的缺點,多源結(jié)構(gòu)逐漸流行起來.其思想是:將原始視頻轉(zhuǎn)換成很多數(shù)據(jù)塊,一個節(jié)點同時從若干個不同的上游節(jié)點取得不同的數(shù)據(jù)塊,當收集到足夠數(shù)量的塊時,就可以恢復(fù)出原始視頻.多源結(jié)構(gòu)可以有效地避免單源的不足:由于節(jié)點間相互交換數(shù)據(jù)塊,每個節(jié)點都可以貢獻資源,資源利用率更高;通過將視頻分成很小粒度的數(shù)據(jù)塊,也降低了節(jié)點能提供服務(wù)的門檻.從本質(zhì)上說,多源結(jié)構(gòu)由于節(jié)點間相互提供數(shù)據(jù),沒有明確的上游與下游,其拓撲必然是網(wǎng)狀的.但是從設(shè)計的角度,它可以分為多樹結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)[14,15,16,17,18,19,20,21,22]、混合結(jié)構(gòu)等.多樹結(jié)構(gòu)通常由多棵組播樹組成,每一棵子樹對應(yīng)一個視頻子流;而網(wǎng)狀結(jié)構(gòu)則沒有“樹”的任何特征,視頻數(shù)據(jù)甚至不表現(xiàn)為具體的流,而是以塊的形式傳輸.圖1(b)給出了多樹結(jié)構(gòu)的一個例子,其中的視頻被分成兩個子流.由于需要維護多棵組播樹,多樹結(jié)構(gòu)的實現(xiàn)較復(fù)雜,反而是網(wǎng)狀結(jié)構(gòu)由于實現(xiàn)簡單卻同樣有效,近年來更加流行.Coolstreaming是一個典型的網(wǎng)狀結(jié)構(gòu).在Coolstreaming中,視頻按照播放順序被分割成一系列數(shù)據(jù)塊.每個節(jié)點維護若干個與自己播放進度相近的節(jié)點,并周期性地與它們交換信息,當發(fā)現(xiàn)其它節(jié)點有自己沒有的數(shù)據(jù)塊時,就從這些節(jié)點請求數(shù)據(jù).在文獻中,作者提出了一個共同體(alliances)的概念.一個共同體由若干個節(jié)點組成,一個節(jié)點可以參加若干個共同體.在共同體內(nèi),按照互利的原則,數(shù)據(jù)是協(xié)同下載與共享的.這個由共同體組成的網(wǎng)狀結(jié)構(gòu),可以抽象為小世界網(wǎng)絡(luò),從而具有小世界網(wǎng)絡(luò)的某些優(yōu)點.作者認為這樣的一個系統(tǒng)有更好的可擴展性,比Coolstreaming有更好的QoS保證.多源結(jié)構(gòu)比單源結(jié)構(gòu)有更大的優(yōu)勢,但是在采用多源結(jié)構(gòu)以前,有一個問題需要考慮:由于存在多個上游節(jié)點,收到的數(shù)據(jù)很容易造成重復(fù),從而浪費帶寬.通過協(xié)商可以一定程度上減少數(shù)據(jù)重復(fù),但由于實際環(huán)境中協(xié)商并不總是及時的,數(shù)據(jù)重復(fù)的情況并不能避免;另一方面,協(xié)商本身引入了通信開銷與延遲,而且在協(xié)商過程中,帶寬并不能充分地利用.幸運的是,還有另一種處理數(shù)據(jù)重復(fù)的辦法——編碼.本文接下來討論傳輸中的編碼.2.2帶寬東南角的冗余編碼與網(wǎng)絡(luò)編碼在VoD/P2P的數(shù)據(jù)傳輸過程中,編碼的運用主要有如下目的:(1)增強網(wǎng)絡(luò)容錯性.當網(wǎng)絡(luò)丟包或上游節(jié)點失效時,不對當前節(jié)點產(chǎn)生影響,或影響很小;(2)提高數(shù)據(jù)差異性.即便在沒有協(xié)商的情況下,從不同上游節(jié)點接收的數(shù)據(jù)也沒有重復(fù),或者產(chǎn)生重復(fù)的概率很小;(3)適應(yīng)節(jié)點異構(gòu)性.將原始的視頻流編碼成若干子流,每個子流的帶寬要求較低,所以那些下載帶寬較小的節(jié)點若沒有能力接收整個視頻流,可以接收少量的子流,同樣可以播放視頻(清晰度降低).本文接下來介紹3種主要的編碼思想(圖2),即多描述編碼(MultipleDescriptionCoding,MDC)、冗余編碼、網(wǎng)絡(luò)編碼(NetworkCoding).多描述編碼是為了適應(yīng)網(wǎng)絡(luò)丟包,并適應(yīng)不同帶寬用戶而提出的一種編碼思想.它將原始的視頻流編碼成若干個子流,取得任意數(shù)量的子流都可解碼播放,并且取得的流越多,播放質(zhì)量越高.編碼的具體實現(xiàn)有多種,可以是基于視頻的時域分割,也可以是基于視頻分層編碼,或者是一些其它的設(shè)計.多描述編碼有很好的容錯性,因此它在很多系統(tǒng)中被采用.但它有一個很大的缺點,就是當編碼的子流數(shù)目少時,并不能表現(xiàn)它的優(yōu)勢;而當子流數(shù)目多時,引入的帶寬開銷很大.有研究表明,當編碼成2個子流,引入的帶寬開銷大致在10%～50%;而當編碼成8個流時,開銷在20%～200%.具體的開銷與編碼實現(xiàn)及視頻內(nèi)容有很大的關(guān)系.與多描述編碼相比,冗余編碼和網(wǎng)絡(luò)編碼引入的帶寬開銷則小得多,一般只是編碼中用到的一些元數(shù)據(jù)信息.事實上,冗余編碼和網(wǎng)絡(luò)編碼擁有相同的算法基礎(chǔ),即或者基于數(shù)論中的有限域,或者基于圖論中的稀疏二部圖.為了適應(yīng)點播的“邊下載邊播放”的特點,在編碼前,視頻文件首先按播放順序被分割成若干段(比如每1段有1秒的播放時間),稱之為原始數(shù)據(jù)段.基于有限域的編碼流程是:對每一個原始數(shù)據(jù)段,將其平分成N塊,然后將這N數(shù)據(jù)塊在GF(2k)域上作線性疊加以生成冗余塊.當GF域足夠大時,生成的冗余塊間線性相關(guān)的概率很小,所以任取N(或稍大于N)冗余塊即可解碼出原始數(shù)據(jù)段.例如,ReedSolomonCode是一個常用的基于有限域的編碼.基于稀疏二部圖的編碼流程是:對每一個原始數(shù)據(jù)段,將其平分成N塊,然后按照某種分布從中任選r塊(r≤N),并將這r數(shù)據(jù)塊作“異或”操作以生成冗余塊.為了使任取N(或稍大于N)冗余塊即可解碼,實際的編碼過程更復(fù)雜一些.相關(guān)的編碼實例包括TornadoCode、LTCode、RaptorCode等.如果一個編碼可以從原始塊中生成無窮多的冗余塊,則稱這個編碼為ratelesscode,反之則稱為ratedcode.冗余編碼與網(wǎng)絡(luò)編碼的主要區(qū)別在于,前者是離線編碼.具體地說,冗余編碼是在數(shù)據(jù)傳輸前(離線狀態(tài)下),將原始數(shù)據(jù)段分成N塊,并利用某種算法(如ReedSolomonCode)擴展出M塊冗余,從這N+M數(shù)據(jù)塊中任取不同的N塊就可解碼出原始數(shù)據(jù).冗余編碼其實更多地針對存儲而非傳輸,因為它的編碼過程發(fā)生在傳輸前,而且它的優(yōu)勢主要表現(xiàn)在存儲中(參見第3節(jié)).但在傳輸過程中,同樣可以因為它的“冗余”而得到好處.圖2(b)、(c)對冗余編碼與沒有編碼的方案作了比較.冗余編碼的一個缺點是,當冗余塊數(shù)M較小時,在沒有協(xié)商的情況下,任取N數(shù)據(jù)塊,因發(fā)生重復(fù)而不能解碼的概率仍較大(如圖3所示).例如N=6,M=4時,這個概率是85%;即使M=1000,這個概率仍有1.5%.而另一方面,當M值很大時,按照圖2(c)的結(jié)構(gòu),源節(jié)點需要預(yù)先緩存很多冗余塊,將消耗大量存儲空間.當然,后一個問題可以通過一邊編碼一邊發(fā)布的形式解決,其實這已經(jīng)具有了網(wǎng)絡(luò)編碼的某些特征.網(wǎng)絡(luò)編碼剛產(chǎn)生時,就被認為是一種很有前景的編碼.它的思想是:當一個源節(jié)點向多個目標節(jié)點組播數(shù)據(jù)時,中間節(jié)點在轉(zhuǎn)發(fā)收到的數(shù)據(jù)之前先進行編碼.網(wǎng)絡(luò)編碼可以讓網(wǎng)絡(luò)達到最大流的吞吐量.圖2(d)給出了網(wǎng)絡(luò)編碼的一個例子.在這個例子中,如果不采用網(wǎng)絡(luò)編碼,A、C兩節(jié)點至多只有一個節(jié)點能播放視頻.Avalanche是一個采用網(wǎng)絡(luò)編碼的大型內(nèi)容分發(fā)網(wǎng)絡(luò).實驗表明,該系統(tǒng)文件下載時間比沒有編碼的系統(tǒng)縮短了2～3倍,并且采用網(wǎng)絡(luò)編碼提高了系統(tǒng)的魯棒性.在rStream,由于采用基于ratelesscode的網(wǎng)絡(luò)編碼,每個節(jié)點理論上只要能支持與原始視頻碼率相當?shù)南螺d速率即可播放,而不用擔心收到的數(shù)據(jù)會重復(fù),因此系統(tǒng)主要將精力放到如何最小化端到端的延遲上.在Lava中,作者對直播/點播系統(tǒng)中網(wǎng)絡(luò)編碼的作用作了系統(tǒng)的研究,得出的結(jié)論為:(1)網(wǎng)絡(luò)編碼可以使流調(diào)度更加細粒度化,并減少數(shù)據(jù)重復(fù)和帶寬消耗;(2)網(wǎng)絡(luò)編碼可以更好地適應(yīng)網(wǎng)絡(luò)動態(tài)性;(3)對于物理帶寬剛剛能滿足視頻碼率的用戶,網(wǎng)絡(luò)編碼可能是最有效的手段.在文獻中,作者對基于ReedSolomonCode的網(wǎng)絡(luò)編碼可能的一些問題作了研究,主要的結(jié)論是:(1)當分塊數(shù)N很大時,矩陣的生成和轉(zhuǎn)置會有較大的計算開銷;(2)當冗余塊粒度較小時,每個塊包含的生成信息將占較大比重,導(dǎo)致較大的帶寬開銷;(3)網(wǎng)絡(luò)編碼過程中,中間節(jié)點需要等待一定數(shù)量的塊到達,然后進行再編碼.如果等待的塊較多,則很多中間節(jié)點的等待時間的累積將是很可觀的,導(dǎo)致大的端到端延時;如果等待的塊較少,則再編碼后生成的塊的線性相關(guān)的概率會增加.在文獻中,作者討論了編碼中一些參數(shù)的選取.表2列出了以上3種編碼的一個比較.2.3從上游節(jié)點請求數(shù)據(jù)VoD/P2P的傳輸問題關(guān)注于如何充分利用節(jié)點的帶寬.首先,為了保證網(wǎng)絡(luò)中的節(jié)點都可能提供資源,多源結(jié)構(gòu)成為一個首選;其次,為了適應(yīng)多源結(jié)構(gòu)的特點以及降低用戶帶寬要求,視頻進行了分割;最后,為了減少數(shù)據(jù)的重復(fù)以及協(xié)商開銷,并達到網(wǎng)絡(luò)最大流,網(wǎng)絡(luò)編碼可能是一個主流.與傳輸相關(guān)的另一個問題是數(shù)據(jù)驅(qū)動方式,基本的有兩種:(1)拉策略(pull-based),下游節(jié)點根據(jù)自己的需要從上游節(jié)點請求數(shù)據(jù).一般包括一個協(xié)商的過程,在協(xié)商過程中可能不能充分利用帶寬,并且有延時;(2)推策略(push-based),上游節(jié)點主動將數(shù)據(jù)發(fā)送給下游節(jié)點.這種策略可以避免拉策略的缺點,但可能造成數(shù)據(jù)重復(fù),特別是在多源結(jié)構(gòu)中.雖然在采用編碼后,數(shù)據(jù)重復(fù)的概率降低很多,但在網(wǎng)絡(luò)波動過程中,由于通信不及時而造成的數(shù)據(jù)重復(fù)是不能避免的.從目前看來,一種合適的做法是,每隔一段時間做pull-based,而在這段時間過程中采用push-based.VoD/P2P的傳輸問題,大約從2000年開始,一直成為該領(lǐng)域最熱的問題.但是,大部分的研究都假設(shè)直播環(huán)境,或者熱門節(jié)目的點播(類似于直播).對于一個大規(guī)模、大容量的VoD/P2P系統(tǒng),這些假設(shè)可能并不全面.如何處理冷門與熱門節(jié)目并存的系統(tǒng),并在系統(tǒng)資源不夠時作怎樣的調(diào)度和折中,可能是將來的一個研究點.另一方面,大多數(shù)研究者都針對某一個頻道的性能作優(yōu)化,并且明確或不明確地假設(shè)一個節(jié)點只參加一個頻道.但是在實際情況下,一個節(jié)點參加多個頻道的情況是普遍的,特別是系統(tǒng)中的那些“準server”節(jié)點.如何對這些節(jié)點進行調(diào)度,以讓它們對系統(tǒng)的貢獻達到最大,也是將來的潛在研究點.3任意視頻存儲的特點VoD/P2P的存儲希望解決如下的問題:如何將海量的視頻數(shù)據(jù)部署到系統(tǒng)中大量的節(jié)點中,使之在動態(tài)的、異構(gòu)的網(wǎng)絡(luò)中:(1)保證數(shù)據(jù)可用性.即任意節(jié)點在任意時刻任意網(wǎng)絡(luò)位置,都可以訪問已存在于系統(tǒng)中的任意視頻;(2)節(jié)點負載均衡.即存儲應(yīng)足夠分散,從而避免某些節(jié)點承載大量服務(wù)而某些節(jié)點閑置的情況;(3)高效的資源定位.即對任意視頻,可以迅速得到其所存儲的網(wǎng)絡(luò)位置;(4)視頻的細粒度隨機訪問和低延遲.其中最后一點,是VoD/P2P存儲與文件共享系統(tǒng)的最主要差別.本節(jié)接下來將介紹存儲問題的3個主要方面,即資源查找結(jié)構(gòu)、編碼方案、存儲調(diào)度.3.1p2p網(wǎng)絡(luò)的安全問題面對P2P網(wǎng)絡(luò)中大量的節(jié)點,設(shè)計一個高效的資源查找算法非常重要.但在實際中,資源查找算法與節(jié)點的組織方式密切相關(guān),因此資源查找算法的設(shè)計等價于資源查找結(jié)構(gòu)的設(shè)計,并通常考慮如下因素:快速的資源定位與訪問、系統(tǒng)的可擴展性以及小的開銷.目前,常見的資源查找結(jié)構(gòu)包括中心化的P2P網(wǎng)絡(luò)、非中心的P2P網(wǎng)絡(luò)以及層次化Cluster結(jié)構(gòu)(圖4).在中心化的P2P網(wǎng)絡(luò)中,一般存在一個索引服務(wù)器(IndexServer或Tracker),管理網(wǎng)絡(luò)中的節(jié)點與資源.雖然這種結(jié)構(gòu)有可擴展性差、單點失敗等缺點,但卻是實際系統(tǒng)中最常見的,原因如下:(1)系統(tǒng)實現(xiàn)簡單;(2)索引服務(wù)器掌握整個系統(tǒng)的信息,因此對資源的查找非常迅速,并且容易對系統(tǒng)作優(yōu)化;(3)P2P網(wǎng)絡(luò)的安全問題并沒有很好解決,采用中心化的服務(wù)器對系統(tǒng)有更好的可控性;(4)雖然可能單點失敗,但在大多數(shù)情況下,采用專門的服務(wù)器會比純粹的P2P網(wǎng)絡(luò)更穩(wěn)定;(5)可擴展性問題可以通過部署多個服務(wù)器的方式解決.與中心化P2P網(wǎng)絡(luò)相對應(yīng)的是非中心的P2P網(wǎng)絡(luò).在這種網(wǎng)絡(luò)中路由是一個有意思的問題,即如何將消息快速發(fā)送到某個給定ID的節(jié)點.通常這些系統(tǒng)都使用了基于超立方體的路由思想.如果將網(wǎng)絡(luò)中的節(jié)點映射成超立方體的頂點,那是Chord、Pastry、Tapestry的思想;而如果將超立方體的每條邊進一步劃分以形成更多的點(相當于笛卡兒坐標系中的點),則是CAN的思想.限于篇幅,本文對具體的路由過程不再展開.假設(shè)這樣的路由算法已經(jīng)實現(xiàn),則可以在它的基礎(chǔ)上構(gòu)建分布式哈希(DistributedHashTable,DHT),以實現(xiàn)資源定位.DHT的基本思想是:系統(tǒng)中,節(jié)點與文件有相同的ID格式,一個文件的元信息(例如存儲該文件的節(jié)點IP地址、文件熱度等,但不包括文件本身),由具有與該文件相同ID的節(jié)點維護;當需要定位某一文件時,只要向那個與文件有相同ID的節(jié)點發(fā)送請求即可.當然,實際的實現(xiàn)會復(fù)雜一些.當系統(tǒng)中節(jié)點數(shù)為n時,DHT一般可以在O(logn)或者O(dn1/d)(d是維度常數(shù))步內(nèi)定位資源.由于DHT將負載分散到網(wǎng)絡(luò)中,可以達到很好的可擴展性;由于系統(tǒng)沒有中心,也避免了單點失敗.但是DHT的查詢時間通常比基于中心服務(wù)器的結(jié)構(gòu)要長,當網(wǎng)絡(luò)不穩(wěn)定時維護開銷很大,并且存在安全問題,系統(tǒng)可控性差.另一方面,DHT是基于ID定位資源的,所以一般不考慮網(wǎng)絡(luò)位置(Pastry等除外),也不支持關(guān)鍵字的查詢.層次化Cluster的思想來源于無線傳感器網(wǎng)絡(luò):按一定的規(guī)則將若干個節(jié)點組成Cluster,每個Cluster選出首領(lǐng),這些首領(lǐng)組成新的Cluster,從而形成一個層次化的結(jié)構(gòu).在VoD/P2P網(wǎng)絡(luò)中,節(jié)點可以根據(jù)網(wǎng)絡(luò)位置,相近的節(jié)點組成一個Cluster;也可以將內(nèi)容相似的節(jié)點組成一個Cluster.當一個節(jié)點需要定位資源時,可以從自己所處的Cluster開始,逐層往上查詢.在這類系統(tǒng)中,為了提高系統(tǒng)的性能,一般將最上層的首領(lǐng)節(jié)點設(shè)置為server.由于P2P網(wǎng)絡(luò)的動態(tài)性,實現(xiàn)一個自適應(yīng)的層次化Cluster結(jié)構(gòu)比較復(fù)雜.3.2冗余編碼的特殊在VoD/P2P系統(tǒng)中,存儲編碼主要是為了提高數(shù)據(jù)的可用性,常用的方案是冗余編碼.事實上,編碼方案已經(jīng)不再是一個問題,因為它在很多容災(zāi)系統(tǒng)中就有了深入研究.但是VoD/P2P的存儲編碼有其特殊性,表現(xiàn)在:(1)為了減小計算開銷,存儲編碼需要與傳輸編碼保持一致.存儲狀態(tài)下的網(wǎng)絡(luò)編碼可以看成是一種特殊的冗余編碼.(2)細粒度的編碼.例如,當用戶請求23分鐘55秒的數(shù)據(jù)時,編碼粒度為1分鐘的方案需要將整個第24分鐘的數(shù)據(jù)解碼出來,而編碼粒度為1秒的方案可以只解碼出那1秒.圖3給出了不同的冗余編碼與數(shù)據(jù)可用性的關(guān)系.從中可以看出,擴展的冗余塊數(shù)越多,數(shù)據(jù)可用性越高,但是安全問題也是需要考慮的.因為當冗余塊較少時,可以對每一塊作數(shù)字簽名,以保證數(shù)據(jù)的完整性;但當冗余塊很多時,數(shù)字簽名變得不可行.對于網(wǎng)絡(luò)編碼,這個問題可能更突出.3.3vod/p2p系統(tǒng)預(yù)取VoD/P2P中的存儲調(diào)度用于應(yīng)對將來的數(shù)據(jù)請求,它關(guān)注于如何以較小的開銷(帶寬、存儲)來達到任意視頻(冷門與熱門節(jié)目)、任意時刻、任意網(wǎng)絡(luò)位置的數(shù)據(jù)可用性.這一小節(jié)主要介紹3部分內(nèi)容:前綴緩存、預(yù)取技術(shù)、替換策略.前綴緩存是指在系統(tǒng)中維持視頻的開始部分一個較高的冗余度.在很多情況下,VoD系統(tǒng)中的用戶并不會將整段視頻看完,而常常只播放視頻的開頭部分.相對于視頻的其它部分,視頻前綴有更高的訪問率,因此緩存前綴可以使存儲的利用更合理.但這只是前綴緩存提出的一個原因,而另一個更重要的因素是:由于大多數(shù)用戶是從頭開始播放視頻的(在實際情況中,視頻前綴可能是播放必須的,因為它包含了視頻元數(shù)據(jù)),如果視頻的前綴很容易找到并下載,將減少用戶的等待時間.在實現(xiàn)中,這個策略需要考慮前綴冗余度、前綴長度等參數(shù)的設(shè)置.COPACC是一個多代理多peer的系統(tǒng)(代理可看成是server),其中視頻的前綴由代理存儲.預(yù)取是指節(jié)點在帶寬剩余的情況下,預(yù)先下載暫時還不會被使用的數(shù)據(jù),這些數(shù)據(jù)將來可能會被本節(jié)點或其它節(jié)點使用.在VoD/P2P系統(tǒng)中,預(yù)取技術(shù)主要是為了提高系統(tǒng)整體性能.預(yù)取可以分為在線預(yù)取和離線預(yù)取.前者是指節(jié)點在視頻播放過程中,預(yù)先取得該視頻的其它數(shù)據(jù);后者則是指節(jié)點在沒有視頻播放的時候,預(yù)先部署某個視頻的數(shù)據(jù).離線預(yù)取更多地表現(xiàn)為替換策略,所以這里的預(yù)取只針對在線預(yù)取.常用的預(yù)取策略有:(1)順序預(yù)取,指按照播放順序預(yù)取數(shù)據(jù);(2)隨機預(yù)取,指隨機選擇要預(yù)取的數(shù)據(jù);(3)最少塊預(yù)取,指優(yōu)先預(yù)取局部或全局最稀少的塊(rarest-first策略).順序預(yù)取一般會導(dǎo)致節(jié)點間數(shù)據(jù)差異性變小而共享困難,但另一方面,由于視頻是順序播放的,完全的隨機預(yù)取或最少塊預(yù)取將導(dǎo)致很差的播放效果.在實際過程中,一般將一個視頻分成若干段,在段內(nèi)采用隨機或最少塊預(yù)取,而段間順序預(yù)取.最少塊預(yù)取比隨機預(yù)取效果更好,但由于需要知道更多信息,也會帶來更多開銷.在RedCarpet中,采用第1個段90%的概率隨機預(yù)取,第2個段10%的概率最少塊預(yù)取策略.在P2Proxy中,server通過自己掌握的全局信息來引導(dǎo)peer預(yù)取數(shù)據(jù).在文獻中,He等提出了一個有意思的預(yù)取策略.作者試圖挖掘視頻內(nèi)部的相關(guān)性,預(yù)測用戶的VCR操作可能跳到的位置,以提前預(yù)取相應(yīng)的數(shù)據(jù).節(jié)點的存儲空間是有限的,替換策略決定哪些數(shù)據(jù)需要被存儲,哪些數(shù)據(jù)需要被替換,以達到最佳的系統(tǒng)性能.常用的替換依據(jù)包括熱度、使用率等.熱度反映了一個節(jié)目被點播的次數(shù),通常熱門的節(jié)目需要更高的冗余度;使用率反映了一個數(shù)據(jù)塊被訪問的次數(shù),使用率低的塊一般優(yōu)先被替換出去.但是一個好的替換策略需要考慮更多因素:(1)如何計算熱度與使用率.使用全局的信息需要更多開銷,而使用局部信息可能不會很準確;(2)如何適應(yīng)節(jié)點的異構(gòu)性.在P2P網(wǎng)絡(luò)中,節(jié)點的在線時間、帶寬存儲性能、貢獻積極性會有很大差別.如果對這些節(jié)點使用相同的替換策略可能會有問題;(3)系統(tǒng)在保證熱門節(jié)目的同時,也需要考慮冷門節(jié)目的可用性.很多系統(tǒng)都研究了peer與server的協(xié)同緩存問題.在PROP中,提出了一個緩存策略,由proxy緩存熱門的節(jié)目,而由peer依據(jù)“利用度”緩存其它的節(jié)目.“利用度”是通過熱度變換而來,一般熱門或冷門的節(jié)目有一個小的“利用度”,而熱度適中的節(jié)目有一個大的“利用度”.3.4存儲與傳輸?shù)恼蟅oD/P2P的存儲問題關(guān)注于如何充分利用節(jié)點的存儲.在編碼方案上,冗余編碼可提高數(shù)據(jù)的可用性,可能是將來的主流.在資源查找結(jié)構(gòu)上,雖然DHT等非中心化結(jié)構(gòu)有極好的可擴展性,但由于其不穩(wěn)定、可控性差等,目前并非實際系統(tǒng)的首選;反而是層次化Cluster結(jié)構(gòu)可以充分考慮網(wǎng)絡(luò)位置,可能是將來的一個選擇.但由于簡單有效,目前實用的索引系統(tǒng)主要還是基于中心化結(jié)構(gòu)的.存儲與傳輸是密不可分的,兩者共用一套編碼方案.通過存儲調(diào)度,節(jié)點間有更多的數(shù)據(jù)共享機會,從而可以更好地利用帶寬.與P2P直播相比,點播在實際中遇到的一個很大的問題是“無源可用”,因此存儲可能是比傳輸更重要的問題.在過去的近十年中,由于視頻直播是一個主要的研究焦點,存儲問題并沒有引起足夠的重視.雖然VoD/P2P可以繼承文件共享系統(tǒng)以及基于C/S的VoD的相關(guān)成果,但這個問題的研究還遠遠不夠.如何將存儲與傳輸更好地結(jié)合,如何構(gòu)建一個自適應(yīng)的位置相關(guān)、內(nèi)容相關(guān)、興趣相關(guān)的小世界存儲網(wǎng)絡(luò),如何設(shè)計有效的替換策略等等,都是需要進一步研究的.4中小型用戶的建設(shè)過程中,主要的用戶的選取過程會導(dǎo)致用戶的提供服務(wù)而不提供服務(wù)有關(guān)激勵問題的研究最初出現(xiàn)在P2P的文件共享系統(tǒng).一份對Gnutella的研究指出,系統(tǒng)中70%的用戶不共享任何文件,近50%的請求是由1%的用戶處理的.用戶這種只享受服務(wù)而不提供服務(wù)的行為,通常被稱為free-riding.在VoD/P2P中,普遍的free-riding行為將導(dǎo)致頻繁的點播緩沖,這將迫使運營商不得不部署更多的服務(wù)器,導(dǎo)致系統(tǒng)成本上升.因此,設(shè)計一個有效的激勵機制,減少或避免用戶的free-riding行為,對VoD/P2P非常重要.目前,常見的激勵機制可分為3類:Tit-for-Tat(TFT)、不對稱TFT、虛擬貨幣機制.4.1vod下載機制TFT可以看成是博弈論的一個實例,其核心思想是:提供多少服務(wù),獲取多少服務(wù).統(tǒng)計服務(wù)的粒度可以是字節(jié)數(shù)、塊數(shù)、流數(shù)、上傳速率等,并且可能是一個模糊的統(tǒng)計.這種機制可應(yīng)用于一次會話中,以避免free-riding;也可以基于長期行為,如積分機制、信譽機制.在Orchard中,視頻采用MDC編碼分成多個流,一個節(jié)點下載一個流就需要上傳一個流,即與其它節(jié)點進行流交換.由于流越多視頻越清晰,所以有能力的節(jié)點就會傾向于上傳更多的流.雖然TFT可以很好地應(yīng)用于BT等文件共享系統(tǒng)以避免free-riding,但對VoD并不十分適用,這是因為:(1)TFT一般通過限制下載速率來懲罰那些提供服務(wù)較少的節(jié)點,這對文件下載的影響是更長的下載時間,但對VoD的影響是視頻不能播放,導(dǎo)致用戶流失;(2)TFT在文件下載中取得成功的一個重要原因是“rarest-first”的數(shù)據(jù)下載策略,但VoD通常要求順序地下載與播放,因此剛開始播放的節(jié)點由于缺乏其它節(jié)點感興趣的數(shù)據(jù)而不能提供服務(wù),成為TFT的受害者.TFT是一種公平的機制,但這也導(dǎo)致了它的缺點:那些服務(wù)能力差的節(jié)點將得不到及時的服務(wù),可能無法生存.4.2不對稱tf特性不對稱TFT是針對TFT的缺點提出的,它要求服務(wù)能力強的節(jié)點貢獻更多資源,以幫助服務(wù)能力差的節(jié)點.在taxation中,不同的節(jié)點有不同的上傳指標,這被抽象成稅收,服務(wù)能力強的節(jié)點的稅率更大一些.系統(tǒng)將這些收取的稅當成基本社會福利,平分給系統(tǒng)中的節(jié)點.也就是說,節(jié)點即使不提供任何服務(wù),也可以擁有“基本社會福利”的服務(wù).不對稱TFT的一個極端情況是:所有加入到系統(tǒng)中的節(jié)點都要求毫不保留地提供服務(wù).這實際上是目前很多商業(yè)系統(tǒng)的做法,它們通過客戶端程序強制用戶貢獻資源,而對資源貢獻的多少不加區(qū)分,節(jié)點不會因為貢獻資源多而得到更好服務(wù),也不會因為貢獻資源少而得到較差服務(wù).與TFT不同,不對稱TFT更多地追求平均化,因此從某種意義上說它不能算是激勵機制.但這種機制有如下的優(yōu)點:(1)通過照顧服務(wù)能力差的節(jié)點擴大了用戶面,這對以廣告作為重要收入的商業(yè)VoD/P2P系統(tǒng)非常重要;(2)強制性地利用系統(tǒng)中所有節(jié)點,特別是服務(wù)能力強的節(jié)點的資源,提高了系統(tǒng)的整體性能;(3)在不追求公平的條件下,這種機制實現(xiàn)比較簡單.不對稱TFT對服務(wù)能力強的節(jié)點是不公平的,容易造成用戶反感,這些節(jié)點在點播結(jié)束后傾向于立即退出系統(tǒng),從而影響系統(tǒng)性能.4.3虛擬貨幣機制虛擬貨幣機制的思想是:節(jié)點提供服務(wù)增加虛擬貨幣,獲取服務(wù)減少虛擬貨幣.與上文提到的兩類機制的差別是,虛擬貨幣機制是開放性的,它不局限于系統(tǒng)內(nèi)部,因為虛擬貨幣可以與現(xiàn)實貨幣相互轉(zhuǎn)換(出于安全的考慮,一般不允許用虛擬貨幣兌換現(xiàn)實貨幣).也就是說,提供服務(wù)并不是增加虛擬貨幣的唯一方式,節(jié)點可以通過其它途徑增加自己的虛擬貨幣