中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 摘要 隨著i n t e m e t 的飛速發(fā)展和多媒體技術(shù)的不斷成熟，流媒體應(yīng)用已經(jīng)成為互 聯(lián)網(wǎng)上最為重要、最具活力的應(yīng)用之一。流媒體傳輸需要網(wǎng)絡(luò)高帶寬的支持，傳 統(tǒng)客戶服務(wù)器架構(gòu)可擴(kuò)展性差，無(wú)法滿足大規(guī)模流媒體應(yīng)用要求。近年來(lái)p 2 p 技術(shù)得到迅速發(fā)展，與客戶服務(wù)器模式不同，p 2 p 網(wǎng)絡(luò)中單個(gè)用戶既是客戶節(jié) 點(diǎn)，也是服務(wù)器節(jié)點(diǎn)。p 2 p 技術(shù)利用了閑置在網(wǎng)絡(luò)邊緣的用戶資源，提高了系統(tǒng) 的可擴(kuò)展性，使得網(wǎng)絡(luò)技術(shù)向更大規(guī)模發(fā)展。p 2 p 技術(shù)的興起給大規(guī)模的流媒體 應(yīng)用帶來(lái)了新的解決方案叫2 p 流媒體。 本文首先介紹了p 2 p 流媒體出現(xiàn)的背景，特點(diǎn)和相關(guān)技術(shù)。p 2 p 分布式特點(diǎn) 極大地提高了系統(tǒng)的可擴(kuò)展性，但也帶來(lái)許多挑戰(zhàn)性問(wèn)題，如節(jié)點(diǎn)動(dòng)態(tài)性管理， 數(shù)據(jù)調(diào)度機(jī)制，公平性和安全問(wèn)題等。第二章介紹了p 2 p 相關(guān)技術(shù)，包括數(shù)據(jù) 編碼機(jī)制、激勵(lì)機(jī)制和網(wǎng)絡(luò)測(cè)量技術(shù)。第三章引出我們需要解決的問(wèn)題：如何設(shè) 計(jì)高效的數(shù)據(jù)調(diào)度算法滿足流媒體傳輸需求。我們介紹了已有的研究，結(jié)合實(shí)際 的流媒體系統(tǒng)深入分析了各種數(shù)據(jù)調(diào)度算法的優(yōu)缺點(diǎn)。 論文第四章提出了基于優(yōu)先級(jí)的數(shù)據(jù)調(diào)度方案d p c 。d p c 是一種分布式的 “拉”數(shù)據(jù)調(diào)度算法，由發(fā)送端和接收端調(diào)度兩部分組成，在對(duì)節(jié)點(diǎn)和數(shù)據(jù)塊劃 分優(yōu)先級(jí)后，發(fā)送節(jié)點(diǎn)優(yōu)先響應(yīng)優(yōu)先級(jí)高的鄰居節(jié)點(diǎn)請(qǐng)求，接收節(jié)點(diǎn)優(yōu)先請(qǐng)求優(yōu) 先級(jí)高的數(shù)據(jù)塊。這種嚴(yán)格按照優(yōu)先級(jí)的數(shù)據(jù)傳輸策略保證了數(shù)據(jù)分發(fā)的幾何級(jí) 數(shù)增長(zhǎng)，從而最小化數(shù)據(jù)傳輸延時(shí)。但是嚴(yán)格的優(yōu)先級(jí)傳輸策略需要節(jié)點(diǎn)之間交 互大量控制消息，在深入分析d p c 算法消息延時(shí)開(kāi)銷基礎(chǔ)上，進(jìn)一步提出了同 構(gòu)環(huán)境下基于“推”的d p c 算法改進(jìn)方案。改進(jìn)方案是基于發(fā)送端“推”數(shù)據(jù) 分發(fā)方式，數(shù)據(jù)發(fā)送完全由發(fā)送端控制，大大減少了消息延時(shí)開(kāi)銷。 與實(shí)時(shí)流媒體不同，p 2 p 點(diǎn)播系統(tǒng)中v c r 操作和播放異步降低了節(jié)點(diǎn)之間 的合作，增加了服務(wù)器負(fù)載，影響了系統(tǒng)的可擴(kuò)展性。第五章首先討論了p 2 p 點(diǎn)播系統(tǒng)中服務(wù)器負(fù)載因素，在此基礎(chǔ)上提出了基于預(yù)測(cè)的帶寬分配方案p b a ， p b a 算法基本思想是將數(shù)據(jù)分發(fā)轉(zhuǎn)化為帶寬分配問(wèn)題，利用額外帶寬幫助落后 節(jié)點(diǎn)預(yù)取數(shù)據(jù)塊，額外帶寬的分配是根據(jù)節(jié)點(diǎn)的穩(wěn)定性和播放位置。利用額外帶 寬預(yù)取數(shù)據(jù)降低了節(jié)點(diǎn)之間擁有數(shù)據(jù)塊的差異，從而減少離開(kāi)丟失引起的稀有數(shù) 據(jù)丟失，減少了服務(wù)器負(fù)載。 關(guān)鍵字：p 2 p ，流媒體，數(shù)據(jù)調(diào)度機(jī)制 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 a b s t r a c t w i t ht h ew i d e s p r e a dd e p l o y m e n to fb r o a d b a n da c c e s s ，m u l t i m e d i as e r v i c e sa r e g e t t i n gm o r ea n dm o r ep o p u l a r , a n dh a v eb e c a m eas i g n i f i c a n ta p p l i c a t i o ni nt o d a y s i n t e m e t m u l t i m e d i at r a n s m i s s i o nn e e d st h es u p p o r to fb r o a d b a n da c c e s s ，d u et op o o r s c a l a b i l i t y , t r a d i t i o n a lc l i e n t s e r v e rm o d e li sn o ta p p r o p r i a t ew h e nf a c i n gg r o w i n g u s e r so fm u l t i m e d i as e r v i c e s c o m p a r i n gw i t hc l i e n t s e r v e rm o d e l ，i np 2 pe a c hp e e r a c t sb o t ha ss e r v e ra n dc l i e n t t h ew h o l es y s t e mc o u l db e t t e ru t i l i z er e s o u r c e sf r o ma l l o v e rt h en e t w o r k ，t h u sg r e a t l yi m p r o v ei t ss c a l a b i l i t y p 2 pt e c h n o l o g yp r o v i d e san e w s o l u t i o nf o rl a r g e s c a l em u l t i m e d i as e r v i c e s i nt h i st h e s i sw ef i r s ti n t r o d u c et h eb a c k g r o u n do fp 2 pt e c h n o l o g y , f e a t u r e sa n d r e l a t e dr e s e a r c hi s s u e s a l t h o u g ht h ed e c e n t r a l i z e df e a t u r eo fp 2 pg r e a t l yi m p r o v e s y s t e ms c a l a b i l i t y , i ta l s ob r i n g sa b o u ts o m ec h a l l e n g i n gp r o b l e m s ，s u c ha sp e e r d y n a m i c s ，d a t as c h e d u l i n gm e c h a n i s m ，f a i r n e s sa n ds e c u r i t yi s s u e s t h es e c o n d c h a p t e r d i s c u s s e sr e l a t e dw o r ki np 2 pa r e a , i n c l u d i n gd a t ac o d i n g , n e t w o r k m e a s u r e m e n ta n di n c e n t i v em e c h a n i s m s t h et h i r dc h a p t e ri n t r o d u c e so n er e s e a r c h d i r e c t i o n ：h o wt od e s i g na l le f f i c i e n td a t as c h e d u l i n ga l g o r i t h mt om e e tt h en e e d so f m u l t i m e d i at r a n s m i s s i o n t h e nw ep u td a t as c h e d u l i n ga l g o r i t h m si n t os p e c i f i cp 2 p s t r e a m i n gs y s t e m st oa n a l y z et h e i rc o n sa n dp r o s i n c h a p t e rf o u rw ep r o p o s e dad i s t r i b u t e dp r i o r i t y b a s e d d a t as c h e d u l i n g a l g o r i t h mc a l l e dd p c d p ci se s s e n t i a l l yap u l l b a s e dm e c h a n i s m i tc o n t a i n st w o p a r t s ：s u p p l i e rs i d es c h e d u l e ra n dr e c e i v e rs i d es c h e d u l e r e a c hp e e ra n dd a t ac h u n ki s l a b e l e dw i t hp r i o r i t y e a c hs u p p l i e rw o u l dc h o o s ep e e r st os e r v eb a s e do nt h e i r 皿o r i t y , a n de a c hr e c e i v e rw o u l dr e q u e s td a t ac h u n k si nt h es a m ew a y t h e s es t r i c t r u l e sg u a r a n t e et h eg e o m e t r i cd i s t r i b u t i o no fd a t ac h u n k s ，a n dt h u sm i n i m i z et h ed e l a y f o rd a t ad i s t r i b u t i o n h o w e v e lt h es t r i c tp r i o r i t ya l s oi n t r o d u c e sm u c hm e s s a g e o v e r h e a d a f t e ra n a l y z i n gt h em e s s a g et r a n s m i s s i o nd e l a y , w ef u r t h e rp r o p o s ea p u s h b a s e dd p ca l g o r i t h m t h er e v i s e da l g o r i t h m i s p u l l b a s e ds c h e m e t h e s u p p l i e r st a k ef u l lr e s p o n s i b i l i t yf o rd a t ac h u n kd i s t r i b u t i o n ，a n dt h u st h e r ei sm u c h l e s sm e s s a g ee x c h a n g eb e t w e e np e e r s u n l i k el i v es t r e a m i n g ，v c ro p e r a t i o na n dp l a y b a c ka s y n c h r o n yi np 2 pv o d s y s t e m sg r e a t l yd i l u t ep e e r s a b i l i t yt oh e l pe a c ho t h e ra n do f f l o a dt h es e r v e r i n c h a p t e rf i v ew ef i r s td i s c u s st h em a j o rc a u s e so f s e r v e rl o a di np 2 pv o d s y s t e m ，a n d t h e np r o p o s ea p r e d i c t e d b a s e db a n d w i d t h a l l o c a t i o na l g o r i t h mc a l l e dp b a t h eb a s i c i i 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 i d e ao fp b ai st h a td a t as c h e d u l i n gc a nb ee q u a l l yt r e a t e da sb a n d w i d t ha l l o c a t i o n e a c hp e e ra l l o c a t e se x t r ab a n d w i d t ht oh e l pd e s c e n tp e e r sp r e f e t c hd a t ac h u n k s a s t a b l ep e e rw i t hh i g h e rp l a y b a c kp o s i t i o ni sa b l et oo b t a i na l a r g e rs h a r eo fe x t r a b a n d w i d t h i nt h i sw a y , t h ed i f f e r e n c e si nt h ea m o u n to fd a t ac h u n k sd o w n l o a d e db y d i f f e r e n tp e e r sw o u l dd e c r e a s e ，a n dt h u sr e d u c et h es e r v e rl o a dc a u s e db yd e p a r t u r e m i s s e s k e y w o r d s ：p e e r 。t o 。p e e r , m e d i as t r e a m i n g ，d a t as c h e d u l i n ga l g o r i t h m i i i 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文原創(chuàng)性和授權(quán)使用聲明 本人聲明所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究工作 所取得的成果。除己特別加以標(biāo)注和致謝的地方外，論文中不包含任 何他人已經(jīng)發(fā)表或撰寫過(guò)的研究成果。與我一同工作的同志對(duì)本研究 所做的貢獻(xiàn)均已在論文中作了明確的說(shuō)明。 本人授權(quán)中國(guó)科學(xué)技術(shù)大學(xué)擁有學(xué)位論文的部分使用權(quán)，即：學(xué) 校有權(quán)按有關(guān)規(guī)定向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子 版，允許論文被查閱和借閱，可以將學(xué)位論文編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢 索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。 保密的學(xué)位論文在解密后也遵守此規(guī)定。 作者簽名：二衄 研年f 月f 日 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 第一章 1 1 引言 第一章緒論 隨著i n t e m e t 網(wǎng)絡(luò)的飛速發(fā)展和多媒體技術(shù)的不斷成熟，互聯(lián)網(wǎng)上傳輸?shù)膬?nèi) 容已逐漸由簡(jiǎn)單的文本、圖像轉(zhuǎn)變?yōu)榘谋尽⒁纛l、視頻的多媒體數(shù)據(jù)。相比 傳統(tǒng)的文本和圖像數(shù)據(jù)，即使采用了編碼壓縮技術(shù)，音視頻文件數(shù)據(jù)量仍然相當(dāng) 大，同時(shí)音視頻數(shù)據(jù)傳輸對(duì)傳輸延遲敏感，因此流媒體服務(wù)需要消耗更多的帶寬。 隨著因特網(wǎng)的快速發(fā)展，用戶接入帶寬的不斷增大，以及音視頻壓縮技術(shù)的逐漸 成熟，這些都為流媒體的實(shí)際應(yīng)用提供了強(qiáng)大的動(dòng)力。 在線音樂(lè)、視頻直播和點(diǎn)播等因特網(wǎng)流媒體業(yè)務(wù)進(jìn)入實(shí)用階段。根據(jù)中國(guó)互 聯(lián)網(wǎng)信息中心第二十二次中國(guó)互聯(lián)網(wǎng)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告，網(wǎng)絡(luò)音樂(lè)是中國(guó)網(wǎng)民第 一大網(wǎng)絡(luò)應(yīng)用，使用率達(dá)到8 4 5 ，用戶量高達(dá)2 1 4 億人。網(wǎng)絡(luò)視頻也是中國(guó)網(wǎng) 民的重要互聯(lián)網(wǎng)娛樂(lè)方式。中國(guó)流媒體直播技術(shù)的發(fā)展非常迅速，目前國(guó)內(nèi)已有 超過(guò)1 0 家網(wǎng)站采用自行研發(fā)的軟件提供p 2 p 流媒體業(yè)務(wù)，包括p e l i v e 1 、 p p s t r e 鋤f 2 】、q q l i v e 3 、u u s e e 4 等。但是現(xiàn)有i n t e m e t 上構(gòu)建的大規(guī)模流媒體 系統(tǒng)始終面臨著一些挑戰(zhàn)：網(wǎng)絡(luò)服務(wù)質(zhì)量( q o s ) i 口l 題，節(jié)點(diǎn)異構(gòu)性和系統(tǒng)擴(kuò)展性 問(wèn)題。由于流媒體應(yīng)用對(duì)網(wǎng)絡(luò)帶寬、丟包、延遲抖動(dòng)等服務(wù)質(zhì)量都有嚴(yán)格要求， 目前的i n t e m e t 難以提供q o s 保證，這使得流媒體的大規(guī)模商業(yè)應(yīng)用難以滿足用 戶對(duì)服務(wù)質(zhì)量的需求。另外網(wǎng)絡(luò)和客戶端通常具有較大的異構(gòu)性，滿足具有不周 接入速度用戶的不同服務(wù)質(zhì)量需求，也是需要解決的問(wèn)題?？蓴U(kuò)展性問(wèn)題主要表 現(xiàn)在很多流媒體系統(tǒng)在用戶人數(shù)不多的情況下能夠提供滿意的服務(wù)，但是當(dāng)用戶 數(shù)達(dá)到一定數(shù)量，其服務(wù)質(zhì)量就嚴(yán)重下降。如何解決大規(guī)模流媒體應(yīng)用中的可擴(kuò) 展性問(wèn)題，一直是工業(yè)界和學(xué)術(shù)界關(guān)注的重點(diǎn)。 為了有效地解決上述挑戰(zhàn)，大量新技術(shù)、新架構(gòu)被提出，其中網(wǎng)絡(luò)傳輸技術(shù) 是構(gòu)建大規(guī)模流媒體系統(tǒng)的關(guān)鍵技術(shù)。目前已有的流媒體傳輸技術(shù)可以分為客戶 服務(wù)器模式、i p 組播、c d n 內(nèi)容分發(fā)技術(shù)和p 2 p 技術(shù)支持的流媒體方案。 1 2 流媒體傳輸技術(shù)的發(fā)展 1 2 1 客戶服務(wù)器模式 客戶服務(wù)器( c l i e r 彬s e r v e r ) 模式中每個(gè)客戶端使用單播方式與服務(wù)器建立連 固科學(xué)掛術(shù)大學(xué)碩學(xué)位論文第一章 接，直接從服務(wù)器獲取數(shù)據(jù)，如圖1 1 所示。這種模式優(yōu)點(diǎn)是技術(shù)成熟，實(shí)現(xiàn)簡(jiǎn) 單，適合于視頻點(diǎn)播等需要“單點(diǎn)到單點(diǎn)”數(shù)據(jù)傳輸?shù)牧髅襟w應(yīng)用，但是并不適 合于存在大規(guī)模并發(fā)用戶的網(wǎng)絡(luò)直播應(yīng)用。這是因?yàn)榇罅坎l(fā)用戶不僅可能導(dǎo)致 服務(wù)器負(fù)荷過(guò)重，形成資源瓶頸，而且會(huì)造成大量相同音視頻數(shù)據(jù)在骨干鏈路 重復(fù)傳輸?shù)那闆r，從而導(dǎo)致網(wǎng)絡(luò)資源的極大浪費(fèi)。為此，sd e e r i n g s 等人提出 了基于i p 組播的傳輸模式。 1 2 2 i p 組播 圖i 客戶n 務(wù)器模式示意圈 在i p 組播中，接收相同內(nèi)容的用戶構(gòu)成一個(gè)組播組，由路由器負(fù)責(zé)維護(hù)組 播組的狀態(tài)和組成員的變化，并在組成員之間構(gòu)造一棵數(shù)據(jù)分拄樹(shù)。流媒體服務(wù) 器只需要向組內(nèi)發(fā)送一份組播數(shù)據(jù)，由路由器在恰當(dāng)?shù)姆种c(diǎn)復(fù)制、轉(zhuǎn)發(fā)數(shù)據(jù)， 就可讓所有組成員收到數(shù)據(jù)，而任何一份數(shù)據(jù)包的拷貝只會(huì)在組播樹(shù)的每條鏈路 上出現(xiàn)一次。由于i p 組播能夠有效利用網(wǎng)絡(luò)資源并降低服務(wù)器的負(fù)荷，因此它 被認(rèn)為是解決“單點(diǎn)到多點(diǎn)( o n e t o - m a n y ) ”數(shù)據(jù)傳輸最理想的方式。然而i p 組播并沒(méi)有得到廣泛應(yīng)用，這是因?yàn)閕 p 組播需要路由器的支持，組播路由器需 要維護(hù)每個(gè)組播組狀態(tài)，增加了組播路由器的負(fù)載。 幽】2 i p 組播模式示意閏 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第一章 1 2 3 c d n 方式 內(nèi)容分發(fā)網(wǎng)絡(luò)( c o n t e n td e l i v e r yn e t w o r k s ) j 6 是一種基于分布式c s 結(jié)構(gòu)的 流媒體服務(wù)平臺(tái)，c d n 主要機(jī)制是通過(guò)在多個(gè)i s p 接入處布置多個(gè)層次的緩存 服務(wù)器節(jié)點(diǎn)，通過(guò)智能化策略，一方面通過(guò)全局內(nèi)容復(fù)制策略把內(nèi)容推送到各個(gè) 邊緣服務(wù)器，將中心服務(wù)器流媒體內(nèi)容分發(fā)到這些距離最近，服務(wù)質(zhì)量最好的節(jié) 點(diǎn)，同時(shí)通過(guò)全局負(fù)載均衡技術(shù)把用戶引導(dǎo)到最近的邊緣服務(wù)器，用戶可以就近 取得所需流媒體內(nèi)容，從而實(shí)現(xiàn)負(fù)載分散，減少了主干網(wǎng)絡(luò)流量，提高用戶訪問(wèn) 流媒體服務(wù)的響應(yīng)速度。但是c d n 網(wǎng)絡(luò)構(gòu)造成本高，可擴(kuò)展性差，不能適應(yīng)快 速增長(zhǎng)的用戶需求。 1 2 4p 2 p 流媒體技術(shù) 不同于傳統(tǒng)的c i s 網(wǎng)絡(luò)架構(gòu)p 2 p ( p e e b t o - p e e 0 架構(gòu)中網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都是 邏輯對(duì)等的，網(wǎng)絡(luò)中節(jié)點(diǎn)既是服務(wù)器又是客戶端。由于充分利用了參與節(jié)點(diǎn)的閑 散資源，解決了單一服務(wù)器資源瓶頸問(wèn)題。p 2 p 流媒體系統(tǒng)就是通過(guò)p 2 p 架構(gòu)在 節(jié)點(diǎn)間傳輸流媒體服務(wù)的系統(tǒng)。在p 2 p 流媒體系統(tǒng)中對(duì)相同視頻流感興趣的 節(jié)點(diǎn)協(xié)同合作傳輸數(shù)據(jù)數(shù)據(jù)轉(zhuǎn)發(fā)功能從i p 層轉(zhuǎn)移到應(yīng)用層。與i p 組播方案相 比，不需要中間路由器的支持，易于部署；與c d n 方案相比，由于用戶參與數(shù) 據(jù)分發(fā)，p 2 p 架構(gòu)極大地提供了系統(tǒng)可擴(kuò)展性。圖1 - 3 是p 2 p 流媒體數(shù)據(jù)分發(fā)示 意圖。 圖1 - 3p 2 p 流媒體技術(shù)示意圖 p 2 p 具有的良好特性使基于p 2 p 技術(shù)的流媒體成為近年來(lái)研究熱點(diǎn)，國(guó)際上 眾多知名大學(xué)和研究所紛紛投入了該領(lǐng)域的研究井取得了一系列的研究進(jìn)展， 如文件共享系統(tǒng)b i t t o n e m 7 廣泛應(yīng)用的實(shí)時(shí)流媒體系統(tǒng)c o o l s t r e a m i n g s 和 p p l i v e ，新興的視頻點(diǎn)播系統(tǒng)g r i d c a s t 9 等。 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第一章 1 3p 2 p 流媒體技術(shù)研究的關(guān)鍵問(wèn)題 p 2 p 流媒體系統(tǒng)中節(jié)點(diǎn)具有相同的地位，這種非中心化特點(diǎn)帶來(lái)了其在可擴(kuò) 展性、健壯性方面的優(yōu)勢(shì)，同時(shí)也引入了許多新的挑戰(zhàn)。經(jīng)過(guò)近幾年的研究和發(fā) 展，p 2 p 流媒體技術(shù)得到了長(zhǎng)足的發(fā)展，但是仍然有許多待解決的挑戰(zhàn)性難題。 我們歸納研究的關(guān)鍵問(wèn)題主要有以下幾點(diǎn)： ( 1 ) 節(jié)點(diǎn)動(dòng)態(tài)性管理 p 2 p 系統(tǒng)中節(jié)點(diǎn)的行為是不可預(yù)測(cè)的，每個(gè)節(jié)點(diǎn)可以隨時(shí)加入系統(tǒng)請(qǐng)求服 務(wù)，也會(huì)隨時(shí)終止服務(wù)，甚至在沒(méi)有預(yù)先通知下退出系統(tǒng)。極端情況下，大量節(jié) 點(diǎn)在短時(shí)間內(nèi)加入或者退出網(wǎng)絡(luò)。節(jié)點(diǎn)的高度動(dòng)態(tài)性對(duì)整個(gè)系統(tǒng)的服務(wù)質(zhì)量帶來(lái) 了挑戰(zhàn)。 ( 2 ) 節(jié)點(diǎn)異構(gòu)性 網(wǎng)絡(luò)中節(jié)點(diǎn)的能力是異構(gòu)的，它們的上下行帶寬，可提供的存儲(chǔ)空間和計(jì)算 能力是不同的。高質(zhì)量視頻流媒體需要足夠的帶寬支持，由于節(jié)點(diǎn)帶寬的異構(gòu)性， 一些節(jié)點(diǎn)可用帶寬低于視頻速率的要求。進(jìn)一步提高流媒體視頻速率，滿足高帶 寬節(jié)點(diǎn)對(duì)視頻質(zhì)量需求，幫助低帶寬節(jié)點(diǎn)獲取滿意的服務(wù)質(zhì)量是流媒體系統(tǒng)需要 研究的一個(gè)關(guān)鍵問(wèn)題。 ( 3 ) 數(shù)據(jù)調(diào)度算法 p 2 p 流媒體中每個(gè)節(jié)點(diǎn)既是服務(wù)提供者又是接收者，節(jié)點(diǎn)之間相互合作獲取 共同感興趣的視頻數(shù)據(jù)。滿足流媒體視頻數(shù)據(jù)播放的連續(xù)性是數(shù)據(jù)調(diào)度算法的基 本要求。除了連續(xù)性要求外，流媒體傳輸還需要考慮視頻播放的啟動(dòng)延時(shí)和播放 延時(shí)。啟動(dòng)延時(shí)是指節(jié)點(diǎn)從選定視頻到實(shí)際播放需要等待的時(shí)間，播放延時(shí)是指 收看相同視頻節(jié)點(diǎn)之間的播放位置差。如何高效地分發(fā)數(shù)據(jù)，充分利用系統(tǒng)節(jié)點(diǎn) 帶寬是流媒體數(shù)據(jù)調(diào)度算法設(shè)計(jì)的關(guān)鍵。 ( 4 ) 節(jié)點(diǎn)組成員管理 節(jié)點(diǎn)組成員管理是將參與系統(tǒng)中的節(jié)點(diǎn)有效組織起來(lái)形成邏輯上的覆蓋網(wǎng) 絡(luò)，除了需要考慮節(jié)點(diǎn)的高度動(dòng)態(tài)性，將覆蓋網(wǎng)絡(luò)時(shí)與實(shí)際的底層拓?fù)湎嘟Y(jié)合是 p 2 p 流媒體系統(tǒng)的一個(gè)關(guān)鍵，考慮了底層拓?fù)涞牧髅襟w系統(tǒng)可以對(duì)節(jié)點(diǎn)進(jìn)行聚 類，這樣做的好處是縮短數(shù)據(jù)傳輸路徑，降低了數(shù)據(jù)傳輸延時(shí)，減少跨i s p 流量。 ( 5 ) 公平性和安全問(wèn)題 由于p 2 p 網(wǎng)絡(luò)的去中心化特征，單個(gè)節(jié)點(diǎn)未必會(huì)積極的參與數(shù)據(jù)傳輸服務(wù)， 即所謂的“搭便車 現(xiàn)象，這使得分散在客戶端的資源無(wú)法得到充分利用。激勵(lì) 機(jī)制目的是鼓勵(lì)節(jié)點(diǎn)貢獻(xiàn)帶寬參與數(shù)據(jù)傳輸。設(shè)計(jì)有效的激勵(lì)機(jī)制是p 2 p 流媒 4 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 第一章 體系統(tǒng)需要解決的關(guān)鍵問(wèn)題。除了“搭便車”節(jié)點(diǎn)以外，p 2 p 系統(tǒng)中還可能存在 惡意節(jié)點(diǎn)。去中心化特點(diǎn)使得惡意節(jié)點(diǎn)發(fā)布的虛假信息或者惡意代碼可以迅速充 斥網(wǎng)絡(luò)，在p 2 p 系統(tǒng)中加入安全機(jī)制是一個(gè)關(guān)鍵研究問(wèn)題。 1 4 本章小結(jié) 本章概括性介紹了p 2 p 流媒體系統(tǒng)出現(xiàn)的背景、特點(diǎn)和需要解決的關(guān)鍵問(wèn) 題。流媒體傳輸需要網(wǎng)絡(luò)高帶寬的支持，傳統(tǒng)客戶服務(wù)器架構(gòu)可擴(kuò)展性差，存 在單一服務(wù)器資源瓶頸問(wèn)題。p 2 p 網(wǎng)絡(luò)架構(gòu)充分利用了網(wǎng)絡(luò)邊緣分布的大量計(jì)算 和存儲(chǔ)資源，節(jié)點(diǎn)在網(wǎng)絡(luò)中既是服務(wù)提供者又是接收者。p 2 p 架構(gòu)去中心化特征 極大地提高了系統(tǒng)的可擴(kuò)展性，同時(shí)也帶來(lái)了許多挑戰(zhàn)性問(wèn)題，如節(jié)點(diǎn)的有效管 理，數(shù)據(jù)的高效分發(fā)，公平性和安全問(wèn)題等。 1 5 論文結(jié)構(gòu) 第一章介紹了p 2 p 流媒體系統(tǒng)出現(xiàn)的背景、特點(diǎn)和需要解決的關(guān)鍵問(wèn)題。 第二章詳細(xì)闡述了p 2 p 流媒體的相關(guān)技術(shù)，包括視頻編碼技術(shù)、激勵(lì)機(jī)制、 網(wǎng)絡(luò)測(cè)量和p 2 p 分布式協(xié)同攻擊。 第三章分析p 2 p 流媒體系統(tǒng)節(jié)點(diǎn)組成員管理和數(shù)據(jù)調(diào)度機(jī)制。在此基礎(chǔ)之 上詳細(xì)分析了典型的p 2 p 實(shí)時(shí)流媒體和點(diǎn)播系統(tǒng)。 第四章提出了基于優(yōu)先級(jí)的數(shù)據(jù)調(diào)度算法d p c ，d p c 算法由發(fā)送端和接收 端調(diào)度兩部分組成，在對(duì)節(jié)點(diǎn)和數(shù)據(jù)塊劃分優(yōu)先級(jí)后，發(fā)送節(jié)點(diǎn)優(yōu)先響應(yīng)優(yōu)先級(jí) 高的鄰居節(jié)點(diǎn)請(qǐng)求，接收節(jié)點(diǎn)優(yōu)先請(qǐng)求優(yōu)先級(jí)高的數(shù)據(jù)塊。這種嚴(yán)格按照優(yōu)先級(jí) 的數(shù)據(jù)傳輸策略保證了數(shù)據(jù)分發(fā)的幾何級(jí)數(shù)增長(zhǎng)，從而最小化數(shù)據(jù)傳輸延時(shí)。但 是嚴(yán)格的優(yōu)先級(jí)傳輸策略需要節(jié)點(diǎn)之間交互大量控制消息，在深入分析了d p c 算法消息延時(shí)開(kāi)銷，進(jìn)一步提出了同構(gòu)環(huán)境下基于推”的d p c 算法改進(jìn)方案。 改進(jìn)方案中數(shù)據(jù)發(fā)送完全由發(fā)送端控制，大大減少了消息延時(shí)開(kāi)銷。 第五章深入分析了p 2 p 點(diǎn)播系統(tǒng)中服務(wù)器負(fù)載因素，在此基礎(chǔ)上提出了基 于預(yù)測(cè)的帶寬分配方案p b a ，p b a 算法將數(shù)據(jù)分發(fā)等價(jià)為帶寬分配問(wèn)題，利用 額外帶寬幫助落后節(jié)點(diǎn)預(yù)取數(shù)據(jù)塊。利用額外帶寬預(yù)取數(shù)據(jù)降低了節(jié)點(diǎn)之間的數(shù) 據(jù)差異，降低了離開(kāi)丟失引起的服務(wù)器負(fù)載。 第六章總結(jié)全文，并指出下一步的研究方向。 5 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第二章 第二章p 2 p 流媒體相關(guān)技術(shù) 2 1 數(shù)據(jù)編碼技術(shù) 傳統(tǒng)的視頻編碼方案是面向存儲(chǔ)的，其目標(biāo)是將視頻壓縮成一個(gè)或幾個(gè)固定 速率的碼流，然而網(wǎng)絡(luò)的異構(gòu)性和缺乏q o s 保證，因此傳統(tǒng)的固定速率的編碼 方案并不適合網(wǎng)絡(luò)傳輸。在采用i p 組播時(shí)，解決這個(gè)問(wèn)題最簡(jiǎn)單的方法是最小 速率傳輸，即組播系統(tǒng)的數(shù)據(jù)碼率是由接入帶寬最小的用戶決定，這類似于“木 桶效應(yīng) ，具有高帶寬接入的用戶無(wú)法享受到與其帶寬相匹配的視頻質(zhì)量。 2 1 1 精細(xì)粒度可擴(kuò)展編碼 理想的視頻編碼方案具有可以在任何位置截?cái)嗟奶匦裕獯a質(zhì)量隨之接收碼 率的增加而提高。為此研究人員提出了精細(xì)粒度可擴(kuò)展編碼方案( f i n eg r a n u l a r s c a l a b l e ，f o s ) i o i l 】。f g s 編碼的基本思想是將原始視頻編碼為一個(gè)基礎(chǔ)層 ( b a s el a y e r ) 碼流和若干增強(qiáng)層( e n h a n c e m e n tl a y e r s ) 碼流，其中基礎(chǔ)層包含 視頻流中最重要的信息，而增強(qiáng)層則“逐層遞近 地包含更細(xì)粒度的冗余信息， 用戶只需接收基礎(chǔ)層的碼流就可獲得基本的播放質(zhì)量。在接收基礎(chǔ)層碼流的基礎(chǔ) 上，接收的增強(qiáng)層碼流越多，解碼器重構(gòu)的圖像質(zhì)量也就越好。如圖2 1 所示， 精細(xì)粒度可擴(kuò)展編碼的視頻質(zhì)量隨著接收帶寬的增大而逐漸增大，因此它能夠更 好地適應(yīng)帶寬的異構(gòu)性和網(wǎng)絡(luò)帶寬的波動(dòng)。 潛 惑 沸 呻 圖2 1 視頻質(zhì)量隨著接收帶寬增加而增加 將精細(xì)粒度可擴(kuò)展編碼與組播相結(jié)合是解決帶寬異構(gòu)性的辦法，稱為分層組 播( 1 a y e rm u l t i c a s o 。在分層組播中，節(jié)點(diǎn)從多個(gè)鄰居節(jié)點(diǎn)處獲取數(shù)據(jù)，優(yōu)先請(qǐng)求 基礎(chǔ)層數(shù)據(jù)，保證基本的視頻播放，然后根據(jù)鄰居節(jié)點(diǎn)的緩存狀況和帶寬，請(qǐng)求 6 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第二章 增強(qiáng)層數(shù)據(jù)。由于分層編碼中的各個(gè)層的地位不是平等的，下層的優(yōu)先級(jí)高于上 層的優(yōu)先級(jí)，只有下層的數(shù)據(jù)接收到了，上層的數(shù)據(jù)才可以被解碼，如何有效地 分配帶寬獲取多層數(shù)據(jù)是一個(gè)值得研究的問(wèn)題【1 2 】。圖2 2 是節(jié)點(diǎn)請(qǐng)求多層視頻 數(shù)據(jù)示意圖。( a ) 是最保守的請(qǐng)求方式，節(jié)點(diǎn)從基礎(chǔ)層開(kāi)始逐層請(qǐng)求，數(shù)據(jù)層次 優(yōu)先，這種方案的是犧牲了視頻質(zhì)量來(lái)保證基本視頻播放連續(xù)性；( b ) 是一種激 進(jìn)的請(qǐng)求方式，節(jié)點(diǎn)請(qǐng)求相應(yīng)數(shù)據(jù)所有層數(shù)據(jù)，相比較( a ) ，( b ) 方案能夠提高短 期的視頻接收質(zhì)量，但犧牲了播放的連續(xù)性；( c ) 是一種折中方案，節(jié)點(diǎn)先請(qǐng)求 一部分基礎(chǔ)層數(shù)據(jù)，然后獲取一部分增強(qiáng)層數(shù)據(jù)，這樣就可以保證播放的連續(xù)性， 又能夠在定程度上提高視頻接收質(zhì)量。 2 1 2 多描述編碼 圖2 2 節(jié)點(diǎn)請(qǐng)求多層視頻數(shù)據(jù)示意圖 多描述編碼m d c ( m u l t i p l ed e s c r i p t i o nc o d i n g ) j 1 3 1 4 把視頻數(shù)據(jù)編碼成m 個(gè)獨(dú)立的流，稱為描述。其中的任何一個(gè)描述都可以在一定的失真率下單獨(dú)解碼， 不同描述流的疊加可以使得率失真降低。所以用戶接收到的描述流的個(gè)數(shù)越多， 重構(gòu)出來(lái)的視頻質(zhì)量就越高。m d c 與分層編碼的不同之處在于m d c 中的m 個(gè) 描述流的地位是平等的，它們中的任意子集都可以解碼。而分層編碼中的各個(gè)層 的地位不是平等的，下層的優(yōu)先級(jí)高于上層的優(yōu)先級(jí)，只有下層的數(shù)據(jù)接收到了， 上層的數(shù)據(jù)才可以被解碼。 沒(méi)有分層編碼層之間優(yōu)先級(jí)關(guān)系的限制，m d c 編碼中各個(gè)獨(dú)立的描述流相 比分層編碼更適合組播應(yīng)用。s p l i t s t r e a m 1 5 系統(tǒng)采用了多棵樹(shù)的覆蓋網(wǎng)絡(luò)結(jié)構(gòu)， 每棵數(shù)據(jù)轉(zhuǎn)發(fā)樹(shù)上分發(fā)一個(gè)m d c 描述流，用戶可以加入到多棵組播樹(shù)獲取數(shù)據(jù)， 每個(gè)節(jié)點(diǎn)允許加入的組播樹(shù)數(shù)量是由其貢獻(xiàn)帶寬決定的，節(jié)點(diǎn)在系統(tǒng)中貢獻(xiàn)越 大，就可以加入到越多的組播樹(shù)中，因而獲取更高的視頻接收質(zhì)量。如果多棵樹(shù) 結(jié)構(gòu)采用分層編碼，每棵組播樹(shù)對(duì)應(yīng)著一層視頻流。由于p 2 p 網(wǎng)絡(luò)中節(jié)點(diǎn)的動(dòng) 態(tài)性，當(dāng)組播樹(shù)中的內(nèi)部節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)，其下游節(jié)點(diǎn)將會(huì)有數(shù)據(jù)丟失，如果退 出的節(jié)點(diǎn)正在分發(fā)基礎(chǔ)層數(shù)據(jù)，那么下游節(jié)點(diǎn)將不能解碼獲取的高層數(shù)據(jù)，從而 造成了視頻播放的不連續(xù)性和帶寬的浪費(fèi)。相比之下，m d c 編碼視頻流之間是 7 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第二章 平等的，盡管內(nèi)部節(jié)點(diǎn)的退出造成了數(shù)據(jù)的丟失，其下游節(jié)點(diǎn)從其他樹(shù)中獲取的 數(shù)據(jù)依然可以解碼，內(nèi)部節(jié)點(diǎn)的退出對(duì)其下游節(jié)點(diǎn)的影響只是降低了視頻質(zhì)量。 圖2 - 3 是s p l i t s t r e a m 系統(tǒng)中多棵樹(shù)覆蓋網(wǎng)絡(luò)示意圖。節(jié)點(diǎn)1 ，2 和3 承擔(dān)m d c1 流的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，在其余兩棵樹(shù)中是葉子節(jié)點(diǎn)，獲取m d c2 和m d c3 視頻流。 圖2 - 3 多棵樹(shù)覆蓋網(wǎng)絡(luò)分發(fā)m d c 描述流 相比傳統(tǒng)的單一視頻流，分層和多描述編碼允許任意的切割視頻流，能夠很 好地支持網(wǎng)絡(luò)的異構(gòu)性。但是為了協(xié)調(diào)不同視頻子流，這些高級(jí)的編碼方式在原 始視頻數(shù)據(jù)中增加了足夠的冗余信息，相比單一視頻流，一定程度上帶來(lái)了帶寬 的浪費(fèi)，另外它們的解碼計(jì)算開(kāi)銷大，這些缺點(diǎn)都限制了它們的實(shí)際應(yīng)用。 2 1 3 網(wǎng)絡(luò)編碼 網(wǎng)絡(luò)編碼( n e t w o r kc o d i n g ) 1 6 是一種融合編碼和路由的信息交換技術(shù)，在傳 統(tǒng)存儲(chǔ)轉(zhuǎn)發(fā)的路由方法基礎(chǔ)上，通過(guò)允許中間節(jié)點(diǎn)對(duì)接收到的多個(gè)數(shù)據(jù)包進(jìn)行編 碼信息融合，增加單次傳輸?shù)男畔⒘?，從而提高整個(gè)網(wǎng)絡(luò)的性能。以著名的“蝴 蝶網(wǎng)絡(luò)模型為例，闡述了網(wǎng)絡(luò)編碼的基本原理。圖2 - 4 所示的“單信源二信宿 蝴蝶網(wǎng)絡(luò)，設(shè)各鏈路容量為l ，s 是信源節(jié)點(diǎn)，y 和z 是信宿節(jié)點(diǎn)，其余為中間 節(jié)點(diǎn)。根據(jù)“最大流最小割”定理，該多播的理論傳輸容量為2 ，即理論上信宿 y 和z 能夠同時(shí)收到信源s 發(fā)出的2 個(gè)單位信息，也就是說(shuō)能夠同時(shí)收到a 和b 。 圖( a ) 表示的是傳統(tǒng)的路由方式，節(jié)點(diǎn)w 單純地執(zhí)行存儲(chǔ)和轉(zhuǎn)發(fā)操作。假定w 轉(zhuǎn) 發(fā)信息b ，則鏈路w x 、x y 和x z 上傳輸?shù)男畔⒕鶠閎 ，信宿y 能夠同時(shí)收到a 和b ，但信宿z 只能收到b ，同時(shí)收到一個(gè)多余的b ，因此，信宿y 和z 無(wú)法同 時(shí)收到a 和b ，該多播不能實(shí)現(xiàn)最大傳輸容量。 8 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第二章 圖2 4 路由方法與網(wǎng)絡(luò)編碼比較：( a ) 傳統(tǒng)路由方法，( b ) 網(wǎng)絡(luò)編碼 圖( b ) 表示的是網(wǎng)絡(luò)編碼方案，節(jié)點(diǎn)w 對(duì)輸入的信息進(jìn)行編碼操作，如異或 操作，然后將編碼結(jié)果aob 發(fā)送到輸出鏈路w x ，然后又通過(guò)鏈路x y 和x z 最終到達(dá)信宿y 和z 。y 將收到的a 和a o b 進(jìn)行譯碼操作，就能解出b ，同理， 信宿z 也能解出a ，因此y 和z 能夠同時(shí)收到2 個(gè)信息，從而實(shí)現(xiàn)了多播理論 上的最大傳輸容量。由此可見(jiàn)，網(wǎng)絡(luò)編碼的核心思想是：具備編碼條件的網(wǎng)絡(luò)節(jié) 點(diǎn)對(duì)接收到的信息進(jìn)行一定方式的處理，然后傳輸給下級(jí)的節(jié)點(diǎn)，收到消息的 下一級(jí)節(jié)點(diǎn)如果具備編碼條件，又可以對(duì)接收到的信息進(jìn)行再編碼，如此反復(fù)， 直到所有經(jīng)過(guò)處理后的信息都匯聚到信宿節(jié)點(diǎn)為止。最后，在信宿節(jié)點(diǎn)，通過(guò)譯 碼就可以譯出信源發(fā)送的原始信息。從圖論的角度，入度至少為2 的節(jié)點(diǎn)具備編 碼條件。 網(wǎng)絡(luò)編碼雖然起源于多播傳輸，主要是為解決多播傳輸中的最大流問(wèn)題，但 是隨之研究的深入，網(wǎng)絡(luò)編碼與其他技術(shù)的結(jié)合越來(lái)越受到人們的關(guān)注，與p 2 p 技術(shù)結(jié)合是當(dāng)前的一個(gè)研究熱點(diǎn)。m i c r o s o f t 開(kāi)發(fā)的a v a l a n c h e 1 7 第次將網(wǎng)絡(luò) 編碼應(yīng)用到p 2 p 文件共享系統(tǒng)中，實(shí)驗(yàn)表明如果所有的節(jié)點(diǎn)都運(yùn)用網(wǎng)絡(luò)編碼， 則p 2 p 系統(tǒng)的平均下載速率比僅僅服務(wù)器端進(jìn)行編碼提高了2 0 3 0 ，比不用 網(wǎng)絡(luò)編碼提高了2 3 倍。另外，網(wǎng)絡(luò)編碼實(shí)際上提高了系統(tǒng)中數(shù)據(jù)冗余，因此它 能夠很好的解決p 2 p 文件共享中由于節(jié)點(diǎn)離開(kāi)導(dǎo)致的“稀有塊”問(wèn)題，更能適 應(yīng)p 2 p 網(wǎng)絡(luò)節(jié)點(diǎn)高度動(dòng)態(tài)性。圖2 5 是a v a l a n c h e 的工作原理，假設(shè)服務(wù)器需要 傳輸信息給節(jié)點(diǎn)a ，則首先將服務(wù)器上的信息分解成n 個(gè)數(shù)據(jù)塊，b l ，b 2 ，b 3 ，b n ， 然后隨機(jī)選擇編碼系數(shù)c l ，c 2 ，c n ，將線性網(wǎng)絡(luò)編碼后的信息e 1 = c l b l + c 2 b 2 + + c nb 。傳輸給節(jié)點(diǎn)a 。同時(shí)節(jié)點(diǎn)a 從其他處獲取另外的信息e 2 = c i b i + c 2 b 2 + + c nb n ，節(jié)點(diǎn)a 隨機(jī)選擇系數(shù)對(duì)獲取的信息進(jìn)行再編碼操作，將編碼后結(jié) 果e 3 = d l e l + d 2 e 2 發(fā)送給節(jié)點(diǎn)b ，依次類推，只要每個(gè)節(jié)點(diǎn)收集到足夠的信息，就 可以通過(guò)解線性方程譯出原始信息。 9 十同科學(xué)技術(shù)大學(xué)碗士學(xué)位論文第= 蘋 強(qiáng)務(wù)器 圖2 - 5 a v a l a n c h e 工作原理 網(wǎng)絡(luò)編碼可以提高系統(tǒng)中數(shù)據(jù)冗余，能夠很好地解決p 2 p 文件共享系統(tǒng)中 的“稀有塊”問(wèn)題。對(duì)流媒體系統(tǒng)來(lái)說(shuō)，引入網(wǎng)絡(luò)編碼提高數(shù)據(jù)冗余可以有效地 解決“內(nèi)容瓶頸”現(xiàn)象，提高節(jié)點(diǎn)的帶寬利用率。但流媒體應(yīng)用中數(shù)據(jù)實(shí)時(shí)性要 求高，傳統(tǒng)的視頻編碼，節(jié)點(diǎn)收到單個(gè)數(shù)據(jù)塊即可解碼，實(shí)時(shí)性高，網(wǎng)絡(luò)編碼必 須收集到足夠的信息才能夠解碼，降低了解碼實(shí)時(shí)性。由于實(shí)際網(wǎng)絡(luò)中不同路徑 上傳輸?shù)姆纸M通常會(huì)經(jīng)歷各異的傳播和排隊(duì)延遲，分組的異步傳輸將極大地增大 節(jié)點(diǎn)的存儲(chǔ)開(kāi)銷，并影響解碼速度。劇此，網(wǎng)絡(luò)編碼并不能簡(jiǎn)單的擴(kuò)展應(yīng)用到流 媒體系統(tǒng)。已有的將網(wǎng)絡(luò)編碼應(yīng)用到實(shí)時(shí)流媒體方案中，一般都采用了一種基于 “代”( g e n e r a t i o n ) 的緩存模型 】8 】，源節(jié)點(diǎn)將同一組原始數(shù)據(jù)塊歸為一“代”，中 繼節(jié)點(diǎn)以“代”為索引存儲(chǔ)接收編碼分組并對(duì)屬于同一代的分組進(jìn)行編碼操作， 該方案可以有效地減低網(wǎng)絡(luò)異步傳輸影響，提高了數(shù)據(jù)實(shí)時(shí)性。最后，采用了網(wǎng) 絡(luò)編碼的系統(tǒng)中，源節(jié)點(diǎn)和中繼節(jié)點(diǎn)需要進(jìn)行編碼操作，隨著數(shù)據(jù)在網(wǎng)絡(luò)中的傳 輸，編碼開(kāi)銷逐漸增加，同時(shí)解碼丌銷也逐漸增加，因此優(yōu)化編解碼速率也是網(wǎng) 絡(luò)編碼能夠應(yīng)用到流媒體系統(tǒng)的急需解決的問(wèn)題。 2 2p 2 p 網(wǎng)絡(luò)激勵(lì)機(jī)制 與傳統(tǒng)的集中式的客戶j 1 7 務(wù)器模式不同，基于p 2 p 的系統(tǒng)是去中心化的， 服務(wù)器的分發(fā)功能被轉(zhuǎn)移到普通參與節(jié)點(diǎn)，節(jié)點(diǎn)不僅是數(shù)據(jù)的接收者，又是數(shù)據(jù) 提供者，向系統(tǒng)中鄰居節(jié)點(diǎn)提供服務(wù)。因此節(jié)點(diǎn)是否積極參與數(shù)據(jù)分發(fā)直接影 響了p 2 p 流媒體系統(tǒng)性能。 在p 2 p 網(wǎng)絡(luò)發(fā)展早期，激勵(lì)機(jī)制并來(lái)引起足夠的重視，絕太多數(shù)系統(tǒng)并沒(méi) 有將其包含在系統(tǒng)設(shè)計(jì)中，隨著p 2 p 網(wǎng)絡(luò)系統(tǒng)的應(yīng)用越來(lái)越廣泛，系統(tǒng)規(guī)模越 來(lái)越丈，缺乏激勵(lì)機(jī)制所導(dǎo)致的問(wèn)題也越來(lái)越嚴(yán)重。e a d a r i 9 等人最早在研究 中指出p 2 p 網(wǎng)絡(luò)中存在大量的“搭便車”( f r e e r i d e 時(shí)節(jié)點(diǎn)，g n u t e l l a 系統(tǒng)中7 0 的用戶都只是從系統(tǒng)獲取自己需要的文件而不向系統(tǒng)提供共享文件，而系統(tǒng)中 詈f孳 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第二章 5 0 的共享文件來(lái)自1 的節(jié)點(diǎn)。在實(shí)時(shí)性和帶寬需求更高的流媒體應(yīng)用中，節(jié) 點(diǎn)的不合作將嚴(yán)重影響系統(tǒng)的性能。因此，為p 2 p 流媒體應(yīng)用設(shè)計(jì)激勵(lì)機(jī)制成 為當(dāng)前的研究熱點(diǎn)，目前已有的激勵(lì)方式主要有兩類：虛擬支付和自然激勵(lì)。 2 2 1 虛擬支付 為了量化節(jié)點(diǎn)的貢獻(xiàn)帶寬，直觀的做法是引入虛擬計(jì)量單位，如虛擬貨幣， 積分或者信譽(yù)。節(jié)點(diǎn)貢獻(xiàn)一定量的帶寬換取相應(yīng)的貨幣或者積分，節(jié)點(diǎn)利用獲得 的貨幣或者積分“購(gòu)買”需要的數(shù)據(jù)或者服務(wù)質(zhì)量。h a b i b 2 0 等設(shè)計(jì)了一個(gè)基 于積分的鼓勵(lì)用戶貢獻(xiàn)轉(zhuǎn)發(fā)資源的激勵(lì)機(jī)制。其主要思想是：記錄每個(gè)節(jié)點(diǎn)給其 他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的貢獻(xiàn)并將其對(duì)應(yīng)于一定的積分值，又把積分值換算成優(yōu)先級(jí)， 優(yōu)先級(jí)被應(yīng)用在每個(gè)節(jié)點(diǎn)選擇鄰居節(jié)點(diǎn)的過(guò)程中。規(guī)定每個(gè)節(jié)點(diǎn)都可以選擇優(yōu)先 級(jí)與自己相當(dāng)或比自己低的節(jié)點(diǎn)為自己提供數(shù)據(jù)。因此，貢獻(xiàn)分值越高的節(jié)點(diǎn)， 可選擇的鄰居節(jié)點(diǎn)范圍越廣，能夠選擇到更好鄰居節(jié)點(diǎn)的機(jī)會(huì)也就越大。這樣， 做轉(zhuǎn)發(fā)貢獻(xiàn)較多的節(jié)點(diǎn)就可以獲得較好的服務(wù)質(zhì)量。圖2 - 6 表示了帶寬換積分的 示意圖。 圖2 - 6 帶寬轉(zhuǎn)換積分的示意圖 t a n 2 1 等人提出了一種基于拍賣的鼓勵(lì)用戶貢獻(xiàn)帶寬的激勵(lì)方式，其主要 思想是：每個(gè)節(jié)點(diǎn)通過(guò)向其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)賺取積分，貢獻(xiàn)的越多，獲得積分越 多。流媒體數(shù)據(jù)發(fā)送分為若干個(gè)周期，每個(gè)周期內(nèi)節(jié)點(diǎn)請(qǐng)求一個(gè)數(shù)據(jù)段并且接收 其他節(jié)點(diǎn)數(shù)據(jù)段請(qǐng)求。數(shù)據(jù)段的請(qǐng)求和發(fā)送采用“市場(chǎng) 機(jī)制，即在每個(gè)數(shù)據(jù)調(diào) 度周期初始，每個(gè)請(qǐng)求節(jié)點(diǎn)分別向數(shù)據(jù)提供節(jié)點(diǎn)出價(jià)，而在數(shù)據(jù)提供節(jié)點(diǎn)的帶寬 允許范圍內(nèi)，那些出價(jià)較高的請(qǐng)求節(jié)點(diǎn)將贏得此次數(shù)據(jù)段的發(fā)送，即“最高競(jìng)價(jià) 策略。因此，貢獻(xiàn)分值越高的節(jié)點(diǎn)，越有可能在競(jìng)爭(zhēng)中獲勝，選擇延時(shí)小數(shù)據(jù)提 供節(jié)點(diǎn)，從而獲得較好的服務(wù)質(zhì)量?？梢哉f(shuō)每次數(shù)據(jù)調(diào)度重新構(gòu)造了覆蓋網(wǎng)絡(luò)結(jié) 構(gòu)，圖2 7 表示了基于拍賣的覆蓋網(wǎng)絡(luò)的構(gòu)建過(guò)程。圖( a ) 表示1 - 6 共六個(gè)節(jié)點(diǎn)向 節(jié)點(diǎn)0 競(jìng)價(jià)，節(jié)點(diǎn)0 的外出帶寬為2 ，只能接收2 個(gè)出價(jià)最高的節(jié)點(diǎn)：圖( b ) 表示 節(jié)點(diǎn)5 和3 成為節(jié)點(diǎn)0 的直接子節(jié)點(diǎn)，同時(shí)節(jié)點(diǎn)0 把競(jìng)價(jià)結(jié)果通知其他落選節(jié)點(diǎn)： e f l c c ) 表示新一輪的競(jìng)價(jià)，落選節(jié)點(diǎn)向節(jié)點(diǎn)o 的直接子節(jié)點(diǎn)5 和3 出價(jià)。 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 第二章 帶寬數(shù)據(jù)傳輸 出價(jià)控制消思 口- + 圖2 7 基于拍賣的覆蓋網(wǎng)絡(luò)構(gòu)建 基于計(jì)費(fèi)機(jī)制的虛擬支付是一種有效的激勵(lì)方案，但其缺點(diǎn)也很明顯。為了 有效地量化節(jié)點(diǎn)的貢獻(xiàn)，計(jì)算節(jié)點(diǎn)的虛擬貨幣和積分，需要集中式的中心服務(wù)器。 因此，這種激勵(lì)方式普遍存在可擴(kuò)展性問(wèn)題。另外除了“搭便車 節(jié)點(diǎn)，p 2 p 網(wǎng) 絡(luò)中還存在惡意節(jié)點(diǎn)，惡意節(jié)點(diǎn)相互勾結(jié)向服務(wù)器謊報(bào)自己的貢獻(xiàn)賺取虛擬貨幣 或者積分。如何有效及時(shí)地識(shí)別惡意節(jié)點(diǎn)并將其隔離出p 2 p 網(wǎng)絡(luò)，也是一個(gè)重 要的研究問(wèn)題。 2 2 2 自然激勵(lì) 自然激勵(lì)方式是指節(jié)點(diǎn)的貢獻(xiàn)與自己實(shí)際的接收狀況相匹配，由自己的接收 狀態(tài)決定貢獻(xiàn)。最成功的自然激勵(lì)是文件共享b i t t o r r e n t 系統(tǒng)采用的“t i t f o r - t a t 策略，其主要思想是：節(jié)點(diǎn)將自己擁有的數(shù)據(jù)傳輸給固定數(shù)量的請(qǐng)求下載節(jié)點(diǎn)， 這些被允許下載的節(jié)點(diǎn)是過(guò)去一段時(shí)間內(nèi)提供給它最大下載速率的節(jié)點(diǎn)。從博弈 論的角度，“t i t f o r - t a t ”是囚徒困境博弈中的一個(gè)重要策略，即依據(jù)對(duì)手的策略選 擇自己的優(yōu)勢(shì)策略，因此，“t i t f o r - t a t ”可以有效地解決惡意節(jié)點(diǎn)勾結(jié)欺騙問(wèn)題。 “t i t f o r - t a t ”要求節(jié)點(diǎn)之間存在雙向數(shù)據(jù)流，也就是節(jié)點(diǎn)之間各自擁有對(duì)方感興趣 的數(shù)據(jù)，但是在基于“推”數(shù)據(jù)分發(fā)流媒體系統(tǒng)中，數(shù)據(jù)流從源節(jié)點(diǎn)自項(xiàng)向下分 發(fā)，節(jié)點(diǎn)之間沒(méi)有雙向數(shù)據(jù)流，在基于“拉”數(shù)據(jù)分發(fā)流媒體系統(tǒng)，由于實(shí)時(shí)流 媒體系統(tǒng)中節(jié)點(diǎn)播放是半同步的，p 2 p 流媒體系統(tǒng)普遍存在“內(nèi)容瓶頸”現(xiàn)象， 即盡管鄰居節(jié)點(diǎn)存在剩余帶寬，鄰居節(jié)點(diǎn)沒(méi)有節(jié)點(diǎn)需要的數(shù)據(jù)。因而流媒體系統(tǒng) 中節(jié)點(diǎn)之間的雙向數(shù)據(jù)流并不明顯?！皌 i t f o r - t a t ”策略并不能簡(jiǎn)單地?cái)U(kuò)展到流媒體 系統(tǒng)。 為了提高節(jié)點(diǎn)之間雙向數(shù)據(jù)流量，l i u 2 2 等人提出了基于分層編碼的實(shí)時(shí)流 媒體激勵(lì)方案，其主要思想是：由于分層編碼的引入，節(jié)點(diǎn)之間分布不同層的數(shù) 據(jù)，極大地降低了“內(nèi)容瓶頸”的可能性，提高了節(jié)點(diǎn)之間雙向數(shù)據(jù)流量，在此 基礎(chǔ)上，“t i t f o r - t a t ”用來(lái)對(duì)節(jié)點(diǎn)進(jìn)行區(qū)分服務(wù)，上傳帶寬大并且愿意承擔(dān)轉(zhuǎn)發(fā)任 1 2 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 第二章 務(wù)的節(jié)點(diǎn)，可以從鄰居節(jié)點(diǎn)處獲取更多層的視頻數(shù)據(jù)，改善自己的視頻質(zhì)量。 m 0 1 1 2 3 】等人為p 2 p 視頻點(diǎn)播系統(tǒng)設(shè)計(jì)了激勵(lì)方案一一“g i v e t o g e t ”，與 t i t f o r - t a t 不同，“g i v e t o g e t 不依賴節(jié)點(diǎn)之間的雙向數(shù)據(jù)流，每個(gè)調(diào)度周期節(jié) 點(diǎn)根據(jù)孫子節(jié)點(diǎn)的反饋評(píng)估直接子節(jié)點(diǎn)的轉(zhuǎn)發(fā)性能，允許轉(zhuǎn)發(fā)性能最好的固定數(shù) 量的直接子節(jié)點(diǎn)在下一個(gè)調(diào)度周期繼續(xù)向本節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)。圖2 8 說(shuō)明了 “g i v e t o g e t ”算法中的反饋和評(píng)估過(guò)程。c 是節(jié)點(diǎn)p 的直接子節(jié)點(diǎn)，節(jié)點(diǎn)g 既是 c 的直接子節(jié)點(diǎn)，又是節(jié)點(diǎn)p 的孫子節(jié)點(diǎn)。節(jié)點(diǎn)p 根據(jù)孫子節(jié)點(diǎn)g 的反饋信息 依據(jù)以下標(biāo)準(zhǔn)對(duì)直接子節(jié)點(diǎn)c 進(jìn)行評(píng)估：1 ) 節(jié)點(diǎn)c 向其子節(jié)點(diǎn)g 傳輸?shù)臄?shù)據(jù)總 量；2 ) 節(jié)點(diǎn)c 向子節(jié)點(diǎn)g 傳輸來(lái)自節(jié)點(diǎn)p 數(shù)據(jù)的數(shù)據(jù)量。 數(shù)據(jù)流 - + 反t 亮信息 圖2 - 8 “g i v e - t o g e t 算法反饋過(guò)程 由于流媒體中節(jié)點(diǎn)播放的半同步性，節(jié)點(diǎn)之間雙向數(shù)據(jù)流量小，因此 “t i t f o r - t a t 策略并不能直接應(yīng)用到流媒體系統(tǒng)。研究人員引入了分層編碼等高級(jí) 視頻編碼格式增加節(jié)點(diǎn)的數(shù)據(jù)分布多樣性，從而提高雙向數(shù)據(jù)流量；但是高級(jí)視 頻編碼技術(shù)目前還不夠成熟，還不能應(yīng)用到p 2 p 流媒體系統(tǒng)中。“g i v e t o g e t ， 算法雖然繞開(kāi)了雙向數(shù)據(jù)流量的問(wèn)題，但是依賴于節(jié)點(diǎn)反饋信息，增加了控制消 息開(kāi)銷，同時(shí)它也無(wú)法解決可能存在的惡意節(jié)點(diǎn)相互勾結(jié)。 2