李振華指導(dǎo)教師陳貴海教授南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系市公開課一等獎(jiǎng)百校聯(lián)賽特等獎(jiǎng)?wù)n件

P2P流媒體系統(tǒng)若干關(guān)鍵屬性優(yōu)化方案

李振華指導(dǎo)教師：陳貴海教授南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系第1頁提要P2P流媒體系統(tǒng)若干關(guān)鍵屬性1、具有高播放連續(xù)度的P2P流媒體系統(tǒng)的設(shè)計(jì)2、流媒體發(fā)布源的快速切換3、底層覆蓋網(wǎng)的拓?fù)鋬?yōu)化總結(jié)與展望第2頁P(yáng)2P流媒體系統(tǒng)P2P研究主要子領(lǐng)域經(jīng)典系統(tǒng)

Skype UUCall

PPLive PPStream

新浪UUSee ……激烈競爭P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第3頁研究意義1月17日中國互聯(lián)網(wǎng)發(fā)展情況統(tǒng)計(jì)匯報(bào)中國內(nèi)地網(wǎng)民觀看網(wǎng)絡(luò)視頻幾個(gè)主要方式中，經(jīng)過P2P流媒體下載軟件比率到達(dá)29.91%，靠近三分之一！學(xué)術(shù)界SIGCOMM’07：微軟研究院（華人1、2作） SIGCOMM’08：PPLive企業(yè)+香港漢字大學(xué)（華人all） Rank1：INFOCOM、ICNP、ICDCS、…… Rank2：IPDPS、ICPP、NOSSDAV、……P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第4頁概念功效分類：

實(shí)時(shí)播放（LiveStreaming）

點(diǎn)播（VoD，VideoonDemand）工作方式分類：

樹狀多播

網(wǎng)狀多播（基于Gossip協(xié)議）P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第5頁比較網(wǎng)狀多播已成為P2P流媒體主流

P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望基于樹狀多播P2P流媒體系統(tǒng)基于Gossip協(xié)議P2P流媒體系統(tǒng)拓?fù)浣Y(jié)構(gòu)樹狀網(wǎng)狀，無固定形狀鄰居數(shù)目子結(jié)點(diǎn)數(shù)，或子結(jié)點(diǎn)數(shù)+1不確定，通常有一上限傳輸方式父節(jié)點(diǎn)傳輸給其子結(jié)點(diǎn)鄰居間按需傳輸容錯(cuò)性單點(diǎn)失效，容錯(cuò)性低靈活健壯，容錯(cuò)性高多出數(shù)據(jù)無有帶寬利用利用率低利用率高適用環(huán)境靜態(tài)或低動(dòng)態(tài)網(wǎng)絡(luò)高動(dòng)態(tài)網(wǎng)絡(luò)系統(tǒng)規(guī)模中、小規(guī)模大規(guī)模發(fā)展情況逐步被淘汰領(lǐng)域主流第6頁P(yáng)2P流媒體系統(tǒng)屬性P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望用戶體驗(yàn)的角度播放連續(xù)度播放數(shù)據(jù)率啟動(dòng)時(shí)延源切換時(shí)延帶寬利用率系統(tǒng)容錯(cuò)性網(wǎng)絡(luò)設(shè)計(jì)者的角度定位效率端到端時(shí)延數(shù)據(jù)吞吐量拓?fù)湟恢滦钥蓴U(kuò)展性……第7頁關(guān)鍵屬性選取依據(jù)

1、直接影響用戶體驗(yàn)，2、或?qū)ο到y(tǒng)性能至關(guān)主要， 3、可優(yōu)化空間大，4、優(yōu)化包括到人為原因少關(guān)鍵屬性

播放連續(xù)度、開啟時(shí)延、源切換時(shí)延、系統(tǒng)容錯(cuò)性、可擴(kuò)展性。P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第8頁本文工作關(guān)鍵屬性1：播放連續(xù)度優(yōu)化方案1：(IPDPS’08)ContinuStreaming系統(tǒng)關(guān)鍵屬性2：源切換時(shí)延優(yōu)化方案2：(ICPP’08)快速源切換算法關(guān)鍵屬性3：系統(tǒng)容錯(cuò)性優(yōu)化方案3：(GCC’07) 底層覆蓋網(wǎng)拓?fù)鋬?yōu)化P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第9頁優(yōu)化方案1：含有高播放連續(xù)度P2P流媒體系統(tǒng)設(shè)計(jì)P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第10頁背景與動(dòng)機(jī)Gossip多播固有缺點(diǎn)：隨機(jī)性、不確定性前人工作多從優(yōu)化數(shù)據(jù)調(diào)度算法著手光優(yōu)化數(shù)據(jù)調(diào)度算法是不夠！P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第11頁我們工作數(shù)據(jù)預(yù)取基于DHT彌補(bǔ)Gossip缺陷高播放連續(xù)度額外開銷低緊迫界限機(jī)制動(dòng)態(tài)預(yù)測(cè)遺漏分片有效避免不必要的預(yù)取操作性能評(píng)價(jià)理論分析模擬實(shí)驗(yàn)P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第12頁ContinuStreaming系統(tǒng)架構(gòu)P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第13頁數(shù)據(jù)預(yù)?。壕o迫界限機(jī)制動(dòng)態(tài)預(yù)測(cè)自適應(yīng)調(diào)整P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第14頁性能評(píng)價(jià)播放連續(xù)度從80%左右提升到95%左右（左圖），額外開銷低于4%（右圖）。P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第15頁優(yōu)化方案2：流媒體公布源快速切換P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第16頁背景多個(gè)媒體公布源，串行工作P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第17頁動(dòng)機(jī)一樣帶寬，不一樣源切換算法，源切換時(shí)間不一樣P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第18頁我們工作源切換過程建立模型歸結(jié)為優(yōu)化問題推導(dǎo)出理論最優(yōu)解快速源切換算法實(shí)用貪心趨近理論最優(yōu)解無額外通信開銷性能評(píng)價(jià)真實(shí)拓?fù)淠M實(shí)驗(yàn)P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第19頁過程建模P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望優(yōu)化目標(biāo)：最小化T2第20頁快速源切換算法P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望優(yōu)化目標(biāo)：最小化T2第21頁快速源切換算法相比傳統(tǒng)源切換算法，源切換時(shí)間降低20-30%，額外開銷沒有增加P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第22頁優(yōu)化方案3：底層覆蓋網(wǎng)拓?fù)鋬?yōu)化P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第23頁背景與動(dòng)機(jī)底層覆蓋網(wǎng)對(duì)P2P流媒體系統(tǒng)至關(guān)主要性：只要覆蓋網(wǎng)分割，流媒體系統(tǒng)就陷于中止底層覆蓋網(wǎng)拓?fù)潢P(guān)鍵點(diǎn)存在：割點(diǎn)

分點(diǎn)C765C1234D>TTL>TTLCC1234567P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第24頁我們工作分點(diǎn)的概念拓?fù)潢P(guān)鍵但的存在割點(diǎn)

分點(diǎn)定義分點(diǎn)分點(diǎn)的檢測(cè)與消除分點(diǎn)檢測(cè)算法分點(diǎn)消除算法性能評(píng)價(jià)模擬實(shí)驗(yàn)P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第25頁分點(diǎn)定義P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望定位

可達(dá)

分點(diǎn)≤TTL3214≤TTL≤TTL＞TTL3214C765C2341第26頁分點(diǎn)檢測(cè)P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望67CC15234Msg_ResponseMsg_Init67CC15234Msg_Probe753167CC1523417531Msg_Probe67CC15234Msg_Arrival5,71,367CC15234Yes!7CC153

（0）網(wǎng)絡(luò)初始狀態(tài) （1）開啟檢測(cè) （2a）探測(cè)可達(dá)性I（2b）探測(cè)可達(dá)性II （3）搜集可達(dá)關(guān)系

（4）劃分子集、判定分點(diǎn)第27頁性能評(píng)價(jià)P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第28頁總結(jié)(1)Book:

GuihaiChen

andZhenhuaLi.Peer-to-PeerNetwork:Structure,ApplicationandDesign(《對(duì)等網(wǎng)絡(luò)：結(jié)構(gòu)、應(yīng)用與設(shè)計(jì)》).TsinghuaUniversityPress,Sep..About400KcharactersinChinese.JournalPaper:HuanChen,GuihaiChen,ZhenhuaLiandXiaomeiCao.AMarketModelbasedReputationmanagementMechanismforPeer-to-PeerNetworks.AcceptedbyJournalofChineseComputerSystems(《小型微型計(jì)算機(jī)系統(tǒng)》),inChinesewithEnglishabstract.RuifengYuan,ZhenhuaLiandGuihaiChen.EnhancingOverlay'sPerformancewithVirtualNodeSwitchMechanism.Acceptedby

ComputerScience(《計(jì)算機(jī)科學(xué)》),inChinesewithEnglishabstract.ZhenhuaLi,GuihaiChenandTongqingQiu.PartitionNode:theTopologicallyCriticalNodesofUnstructuredP2PNetwork.AcceptedbyChineseJournalofSoftware(《軟件學(xué)報(bào)》),inChinesewithEnglishabstract.P2P流媒體系統(tǒng)關(guān)鍵屬性播放連續(xù)度快速源切換覆蓋網(wǎng)拓?fù)鋬?yōu)化總結(jié)與展望第29頁總結(jié)(2)ConferencePaper:

ZhenhuaLi,JiannongCao,GuihaiChenandYanLiu.FastSourceSwitchingforGossip-basedPeer-to-PeerStreaming.The37thInternationalConferenceonParallelProcessing(ICPP),September8-12,inPortlandOregon,USA.ZhenhuaLi,JiannongCaoandGuihaiChen.ContinuStreaming:AchievingHighPlaybackContinuityofGossip-basedPeer-to-PeerStreaming.The22ndIEEEInternationalParallelandDistributedProcessingSymposium(IPDPS),April14-18,inMiamiFlorida,USA.ZhenhuaLiandGuihaiChen.DetectingandReducingPartitionNodesinLimited-routing-hopOverlayNetworks.The6thInternationalConferenceonGridandCooperativeComputing(GCC),pages19-25,August16-18,inUrumchi,Xinjiang,China.JunfengXie,ZhenhuaLiandGuihaiChen.ASemanticOverlayNetworkforUnstructuredPeer-to-PeerProtocols.The13thInternationalConferenceonParallelandDistributedSystems(ICPADS),pages1-8,December5-7,inHsinchu,Taiwan.ZhiyuLiu,RuifengYuan,ZhenhuaLi,HongxingLiandGuihaiChen.SurviveunderHighChurninStructuredP2PSystems:EvaluationandStrategy.LectureNotesinComputerScience(ProceedingsofICCS),Volume3994,pages404-411,