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

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

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

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