P2P視頻點(diǎn)播系統(tǒng)中的鄰居發(fā)現(xiàn)算法.pdf

1、P2P視頻點(diǎn)播是繼P2P文件共享、P2P直播之后，又一方興未艾的P2P研究領(lǐng)域。P2P視頻點(diǎn)播系統(tǒng)中的關(guān)鍵問(wèn)題之一是如何在節(jié)點(diǎn)加入或播放點(diǎn)跳躍時(shí)迅速定位新的供應(yīng)視頻數(shù)據(jù)的鄰居(即“鄰居發(fā)現(xiàn)”)。迅速地發(fā)現(xiàn)鄰居可以讓節(jié)點(diǎn)盡快得到視頻數(shù)據(jù)，讓用戶無(wú)需長(zhǎng)時(shí)間等待視頻開(kāi)始播放，享受平滑的觀看體驗(yàn)。當(dāng)前很多商用的系統(tǒng)都使用集中式的定位服務(wù)器來(lái)實(shí)現(xiàn)節(jié)點(diǎn)的鄰居發(fā)現(xiàn)，存在可擴(kuò)展性問(wèn)題。某些學(xué)者提出分布式鄰居發(fā)現(xiàn)算法，嘗試解決可擴(kuò)展性問(wèn)題，但是目前最好的

2、算法仍需要O(log(N))或O(log(m))的時(shí)間復(fù)雜度(N是覆蓋網(wǎng)的規(guī)模，m是視頻的長(zhǎng)度)。 在本論文中，我們?yōu)镻2P視頻點(diǎn)播系統(tǒng)提出一種O(l)時(shí)間復(fù)雜度的分布式鄰居發(fā)現(xiàn)算法，命名為InstantLeap。InstantLeap算法令節(jié)點(diǎn)自組織形成覆蓋網(wǎng)，作為輕量的索引結(jié)構(gòu)，使得節(jié)點(diǎn)在加入或任何播放點(diǎn)跳躍的操作時(shí)進(jìn)行鄰居發(fā)現(xiàn)都只需O(l)的平均時(shí)間復(fù)雜度，不受覆蓋網(wǎng)規(guī)模大小和視頻流長(zhǎng)度的影響，達(dá)到了理論上的最優(yōu)。據(jù)我們所

3、知，這是首次提出的P2P視頻點(diǎn)播系統(tǒng)中的O(l)時(shí)間復(fù)雜度的分布式鄰居發(fā)現(xiàn)算法。除了實(shí)現(xiàn)O(l)時(shí)間復(fù)雜度的理論最優(yōu)性能，InstantLeap還有以下優(yōu)點(diǎn)：實(shí)用性強(qiáng)，可以與現(xiàn)有十分流行的基于網(wǎng)格的流媒體協(xié)議結(jié)合；實(shí)現(xiàn)簡(jiǎn)單，使用統(tǒng)一的覆蓋網(wǎng)，同時(shí)支持有效的流分發(fā)和鄰居發(fā)現(xiàn)；開(kāi)銷小，與視頻流速率相比，占用帶寬僅僅不到2％。 在本論文中，我們分析比較了現(xiàn)有相關(guān)算法，提出層次化設(shè)計(jì)原理，給出詳盡的協(xié)議設(shè)計(jì)，然后建立數(shù)學(xué)模型證明Inst