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

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

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

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