基于Ｋａｄｅｍｌｉａ模型的流媒體點播系統的研究

摘要：Kademlia是一種構建結構化對等網絡的機制，基于DHT（Distributed Hash Table，分布式哈希表）和XOR（異或運算）實現了覆蓋網（Overlay Network）的構建和節點快速定位以及資源的精確搜索，我們結合當前ALM（ALM，Application Layer Multicast，應用層組播）技術，深入探討了P2P流媒體技術，提出一種流媒體點播模型KadVOD，并對其節點管理、分布式存儲和傳輸機制做了認真分析。

關鍵詞：對等網絡；Kademlia；ALM；VoD

中圖分類號：TP317文獻標識碼：A文章編號：1009-3044(2008)26-1809-03

Research on the Kademlia-based Steaming Video on Demond System

PING Xiao-yan， CHEN Hua， LV Yu

(Kangding Nationality Teacher's College， Kangding 626001， China)

Abstract:Kademlia based on DHT (Distributed Hash Table，distributional Hasche table) and XOR Operation is one kind of unstructured peer-to-peer network mechanism， realized the Overlay Network construction，the fast node-localization mechanism and the resources rapid search， we discussed the P2P media streaming technology thoroughly with ALM (ALM， Application Layer Multicast)， and proposed one kind of media streamings system named KadVOD in this article， and the node administration， the distributional location and the transmission machine of KadVod has made the earnest analysis.

Key words: peer-to-peer network; kademlia; ALM; vod

1 引言

在大規模網絡中的流媒體內容分發（直播與點播）技術一直是計算機技術研究的熱點。早期研究者提出了IP組播（Ip Multicast）技術，其核心思想是讓多個用戶終端共享一條數據流（Streaming），IP組播被認為是最理想的“單點-多點”流媒體分發技術，但由于傳輸模式（需要路由器支持）和管理模式（合理的計費模型）的復雜性而未得到廣泛應用[1]。研究者在IP組播技術的基礎上提出了應用層組播（ALM，Application Layer Multicast）技術，即在應用層上實現數據流（Streaming）的共享分發與多路復用，ALM的最大優點在于：無需改變現有物理網絡的情況下實現數據流的分發，易于部署和控制，有很好的擴展性。

在P2P（peer-to-peer，對等網絡）技術浪潮中，研究者又將P2P技術引入到ALM中，稱為P2P Streaming（p2p流媒體）技術，其核心思想在于將參與節點構造成一個覆蓋網（Overlay），節點既作為接收者又作為轉發者，充分利用節點的存儲和帶寬（下行和上行）能力，讓數據流按照一定的策略（如節點路由策略、數據傳輸和控制策略）在覆蓋網中快速分發并滿足流媒體的實時特性（直播）和異步特性（點播）要求。在P2P流媒體技術研究中，通常分為P2P流媒體直播和P2P流媒體點播。在基于P2P的流媒體直播中，按照覆蓋網即組播樹的構建方式主要分為：基于單樹拓撲的數據分發，如針對視頻會議的ESM[2]，Deshpande提出的SpreadIT[3]，Banerjee等提出的NICE和SRMS[4]，Guo等提出的基于Patching流的數據分發模式[5]，Tran等提出的ZIGZAG[6]，基于應用層網關的OverCAST[7]；基于多樹拓撲的數據分發，如基于MDC（Multiple Description Coding）[8]的CoopNET，Castro提出的Splitstream[9]；基于隨機拓撲（Gossip協議）的數據分發，如DONet/CoolStreaming[10]，GridMedia[11]，TAG[12]，GNutellaStreaming[13]；基于DHT技術的拓撲，如CAN[14]。這些研究側重于構造組播樹，并在數據傳輸中廣泛采用基于分層、分段的優化策略，以降低帶寬消耗、時延和提高Qos（服務質量）。當前在中國大陸投入商用的P2P流媒體直播系統有很多，比較流行的如pplive[15]，ppstream[16]，sopcast[17]，QQlive[18]等。基于P2P的流媒體點播的最大特性是其異步性，即數據流的流動是由用戶行為所決定，其核心思想是在節點中緩存部分數據流并轉發（根據其他節點請求）。根據數據流的緩存策略，主要分為初始緩存策略、最近緩存策略、全局指定緩存策略，研究者提出了很多方案，如基于初始緩存策略的P2CAST[19]，基于FIFO隊列（最近緩存策略）的P2VOD[20]和基于中心索引的DirectStream[21]，基于全局指定策略的P2PStream[22]。當前在中國大陸比較流行的P2P流媒體點播系統很多，如基于混合機構和BitTorrent的風行[23]和Qvod[24]，能同時直播和點播的pplive，ppstream等。[1]

在仔細研究Kademlia[25]模型和ALM的基礎上，我們提出了一種P2P流媒體點播模型KadVOD（vod based on Kademlia）。其特點有：(1)節點快速定位，(2)分布式的緩存管理和高效的搜索機制，(3)基于數據分段的多源傳輸策略。由于Kademlia是作為構建KadVOD的關鍵技術，我們將用一大節的篇幅來介紹Kademlia模型。

2 Kademlia模型

2.1 基本概念

Kademlia是一種基于DHT（Distributed Hash Table，分布式哈希表）和Xor（異或運算）的結構化對等網絡模型，由Petar Maymounkov和David Mazières在2002年提出[25]，隨后在Overnet[26]、eMule[27]、BitTorrent[28-29]等流行P2P軟件中得到實現和應用。其基本思想是將關鍵詞信息構造成一個哈希表，并將其按照一定策略分布式存儲在節點中。

在Kademlia模型中，距離（Distance）是一個核心概念，其由兩個ID（ID為一定長度的數值）通過Xor運算獲得。節點標識nodeid通常為160位，內容關鍵詞信息被存儲在距離內容發布節點距離較近的節點上，一個節點nodeA要查找關鍵詞為key的內容節點集合nodeSetC（保存有關鍵詞為key的內容節點集合），將通過node-lookup（下面將介紹）算法查找距離關鍵詞key最近的節點集合nodeSetB，在nodeSetB中的節點上保存有到節點nodeSetC的所有信息，如節點的nodeID、IP、端口、文件內容索引等。

2.2 k-bucket

節點保存有logN個稱為k-bucket的節點表（N為網絡節點總數，在Kademlia中k-bucket的個數為160），在第i個k-bucket中保存有距離為2i~2i+1的其它k（通常k為20）個節點信息，k-bucket由定時策略和查找過程刷新。其基本過程如下：1) 如果對方節點在對應距離的k-bucket中，將其位置移動到此k-bucket尾部；2) 如果對方節點不在對應距離的k-bucket中且該k-bucket未滿（節點數

通過運用消息和定時的k-bucket刷新策略，每個節點保存著不同距離的在線聯系人信息，顯然，離節點距離（Distance）越近的節點越容易保存在k-bucket中。

2.3 節點的查找

Kademlia中，節點查找的基本過程為：節點R要查找某個結點a時，如果a不在其k-bucket中，就從k-bucket找到與a距離最近的結點b，然后向b查詢a，如果b的k-bucket有a，就把a的信息返回R，如果b的k-bucket沒有a， b就從自己的k-bucket找到與a距離更近的c返回給R，然后R向c查詢a。這是個遞歸過程。

為例實現上述過程，Kademlia定義了4個原語操作RPC：Ping探測節點是否在線，Store（Key，Value）存儲（Key，Value）對到其他節點，find_node（ID）查找與ID距離相近的k個節點，find_value（key）查找關鍵字key，并返回Value。查找算法node-lookup的過程如下：(1)初始節點從其距離最近的k-bucket中取出a個（通常a為3）聯系人，作為候選名單（shortlist），并向其做并行、異步FIND_*操作，如果候選聯系人在線或在規定時間內響應，將返回k或少于k個聯系人，將這些聯系人加入到shortlist中，否則，從shortlist中刪除此聯系人；(2)再從shortlist中選取a個此前未聯系過的候選聯系人，進行(1)的步驟；(3)如果一輪下來未找到距離更近的候選人，則向k個距離較近的且未聯系過的聯系人發送FIND_*操作；(4)查詢結束的條件是：返回的聯系人不比shortlist和對應k-bucket中聯系人的距離更近或者已經返回了k個在線的候選聯系人。

Kademlia基于查找算法node-lookup實現了(1)節點的加入，退出：節點加入到網絡時，首先獲得一個其他聯系人信息，并將其加入到相應的k-bucket中，執行node_lookup（自己的ID）以刷新所有k-bucket。節點退出網絡時，如果斷線，則其他節點在刷新k-bucket時會拋棄此節點；否則向其他節點發送退出消息，其他節點刷新k-bucket。(2)（key，Value）對的分布存儲、發布、查找，其關鍵詞信息隨著查找過程自動分布到節點中，以供其他節點查找：通過node_lookup（key）找到k個距離key最近的節點（聯系人），向其發送STORE操作，搜索（key，value）對的過程同node_lookup一樣，如果成功則返回value，并向距離key最近的未返回value的節點發送STORE操作，否則返回k個距離近的節點。

Kademlia的主要特點是簡單，高魯棒性，節點的快速定位，關鍵詞精確搜索，查找的平均步長為O（logN），所以通常用Kademlia構造能快速定位的對等覆蓋網（Overlay），如在BitTorrent中的Kademila實現，定義了KRPC協議和DHT queries（包含PING、FIND_NODE、GET_peers、ANNOUNCE_PEERS）實現定位和查找，而BitTorrent中的下載仍然采用Tit-for-Tat（針鋒相對）策略和片段優先算法[29]。使用Kademila機制的BitTorrent實現了Trackerless，即不需要Tracker服務器也能進行文件的快速分發和下載。

3 KadVOD系統模型描述

3.1 系統架構

我們將改造Kademlia以適應流媒體的轉發，其系統架構如圖1所示：

KadVOD是一個混合結構系統，包含目錄服務器DS，DS提供頻道（即數據源）列表，所有正在點播相同節目的節點集合nodeset組成一個頻道，頻道以關鍵詞標識（這和BitTorrent的torrent網絡機制相同）。Nodeset中的節點通過全局指定緩存機制互相交換數據信息，形成一個自治覆蓋網（Overlay），數據在覆蓋網中流動。DS的功能是發布頻道和讓節點注冊以獲得第一批網絡中的節點，此外還將進行頻道狀態維護。

用戶點播的過程如下：節點R向DS注冊，請求某一頻道，DS返回部分正在點播此頻道的節點S，R將根據播放進度向多個S請求數據流片段，同時，R根據查找算法在覆蓋網中O搜索片段，如果所有S和O都沒有請求片段，R將向DS發起數據片段請求（在DS未達到帶寬上限時）；R在請求到數據片段后將緩存本地以供其他節點請求。

3.2 節點管理

頻道（文件描述值）fileID：首先將一個媒體文件分段，并進行SHA1[30]摘要seg_key，形成媒體文件描述值fileID，其長度都為160位，分段由全局指定（默認：按長度分段默認為256KB大小，按時間分段則為60s）。節點用160位nodeID標識。K-bucket中的節點包含nodeID、ip、port字段。而保存頻道信息的節點中用（fileID，nodeID、ip、port、{seg_key}）標識正在收看fileID頻道的節點。

DS服務器：提供數據源、頻道列表的服務器，有固定的ip地址。其主要功能：發布頻道，這是原始數據流，并指定分段策略；接納新節點的注冊，返回頻道信息；統計頻道點播信息；當節點在覆蓋網中搜索不到頻道節目或者其他節點時，為其提供搜索服務；當頻道未在覆蓋網中完全分布時，為節點提供有限的數據下載，比如新發布頻道，第一個節點加入時。

節點的注冊和退出：R以A(fileID)向DS發起申請，DS向R返回收看A的部分R集合，并使用node-lookup（nodeID）刷新k-bucket，此時R已加入到該頻道。DS更新頻道收看節點列表（包含nodeID，ip，port，time-to-live），R按照全局策略（默認間隔為1800s）向DS報告自己的信息。R退出時向DS發送退出消息，并向其k-bucket中的R發送退出消息。

節點搜索：節點注冊并刷新k-bucket后，節點有可能通過三種途徑獲得數據流，直接通過DS（如第一個注冊節點），通過DS返回的節點集合（后續注冊節點），通過node-lookup（fileID）獲得收看A的節點集合（后續節點），并開始從其它節點交換數據片段。

由于Kademlia的關鍵詞自動隨著node-lookup傳播并存儲到節點中（見2.3），在一段時間后，收看此頻道的節點信息（fileID，nodeID、ip、port、{seg_key}）將被分布到距離fileID相近的節點中，新注冊節點獲得的信息將會增多。由于采用了混合式結構，節點在注冊DS成功后，將不再需要從DS獲取節點信息，這使得系統有更好的容錯機制，解決了單點故障問題。

3.3 分布式數據緩存和傳輸管理

由于流媒體數據具有時間順序特性，我們在KadVOD采用分段策略，用SHA1值seg_key來標識數據流分段，其長度為160位。根據Kademlia的存儲策略，網絡中的節點R負責存儲與其nodeID距離最近的seg_key信息，即：在任意時刻t，R中保存所有擁有此seg_key的節點索引信息。

當R需要下載數據時，將獲取擁有此seg_key的節點W集合，W返回一個索引列表，其包含擁有此分段數據的節點Z集合，R將向Z節點發送數據請求，開始下載此片段，為了保證片段索引的有效性，節點將每隔3600s重新發布一次自己的索引信息，讓其它節點刷新k-bucket。這個過程通過node-lookup（seg_key）完成，從2.3節的node-lookup算法得知，查找的過程也是seg_key分布存儲的過程。

當節點查找到需要的數據分段后，將進行實際流媒體數據的傳輸。為了加快數據傳輸，將數據分段分為16個小片段或10s片段，節點從多個源節點下載這些小片段，并驗證其seg_key。為了保證連續播放，采用嚴格優先策略，即每一分段必須下載完成才能下載其他分段。為了簡化存儲管理和提高系統服務量，實際的數據緩存在節點存儲中，預先分配播放文件所需要的空間。

3.4 進一步的研究和討論

我們在提出的KadVOD模型中，將研究重點放在架構的設計、節點查找、數據分段和傳輸策略上，而應用播放層的同步、編解碼以及VCR（播放、停止、快進、快退）也是重要的研究對象，其次，并未考慮多DS（目錄服務器）及其協作問題；在數據緩存算法方面，如何優化分段和片段傳輸機制，提高磁盤利用率和降低緩存開銷也需要進一步認真研究。

4 結束語

結合P2P技術的ALM已稱為流媒體技術研究領域的熱點，我們在認真研究ALM和Kademlia的基礎上提出一種流媒體點播KadVOD模型，其具有Kademlia的諸多優點，又有ALM易于實現和部署的特性。隨著P2P流媒體技術的進一步發展，我們相信，將會出現許多實用并大規模部署的基于P2P的流媒體系統。

參考文獻：

[1] 劉亞杰.P2P流媒體內容分發關鍵技術研究[D].國防科技大學，2005.

[2] Chu S， Rao G， Seshan S. A case for end system multicast[J].IEEE Journal on Selected Areas in Communications，2002，20(8):1456.

[3] Deshpande H， Bawa M， Garcia-Molina H. Streaming Live Media overa Peer-to-peer[C].Technical report，Stanford University，2001.

[4] Banerjee S. Resilient multicast using overlays[M].USA:Proeeedings of ACM Sigmetries.SanDiego，2003.

[5] Guo Y. P2Cast:P2P Patehing Scheme for VoD Serviee[C].Proeeedings of the 12th International World Wide Web Conference.BudaPest，2003.

[6] Tran D， Hua K， Do T. ZIGZAG:An Efficient Peer-to-Peer Scheme for Media Streaming[M].USA:Proeeedings of IEEEINFOCOM.SanFranciseo，CA，2003.

[7] Jannotti J， Gifford D K， Johnson K L. Overeast:reliable multicasting with a overlay network[J]. the USENIX SymPosium on Operating System Design and ImPlementation，2000:197-212.

[8] Goyal V K. MultiPle Deseription Coding:Compression Meets the Network[J].IEEE Signal Processing Magazine，2001，18(5):74-93.

[9] Castro M. Splitstream:High-bandwidth multicast in a cooperative environment[C].New York: Proceedings of 19th ACM Symposium on Operating Systems Principle(SOSP).Lake Bolton，2003.

[10] Zhnag X， Liu J， LiandT B. Coolstreaming/DONet:A Data-driven Overlay Netwok for Live Media Streaming[M].USA:In Proeeedings of IEEENIFOCOM.Mimai，FL，2005:13-17.

[11] Zhang M.Large0Scale Live Media Streaming over Peer-to-Peer Networks through Global Intenet[M].Proceedings of PZPMMS，2005.

[12] Zhou M ， Liu J.Tree-assisted gossiping for overlay video disrtibution[M].Kluwer Multimedia Tools and Applications，2005.

[13] GNUtella.[EB\\OL].www.gnugtella.rog.

[14] Stoiea， Morris R，Kagre D，et，al.Chord:A Scalable Peer-to-Peer lookup service for intenet applications[R].Technical Report.TR-819，MITLCS，200l.

[15] Pplive website.[EB\\OL].www.pplive.com.

[16] Ppstream website.[EB\\OL].www.ppstream.com.

[17] Sopcast website.[EB\\OL].www.sopcast.org.

[18] Qqlive website.[EB\\OL].www.qq.com.

[19] Guo Y， Suh K， Kurose J. P2Cast: peer-to-peer patching scheme for VoD service[C]. Proceedings of the 12th international conference on World Wide Web Budapest，2003.

[20] Do，T.T.Hua，K.A.Tantaoui，M.A.P2VoD: providing fault tolerant video-on-demand streaming in peer-to-peer environment. Communications，2004 IEEE International Conference on Publication Date: 20-24 June 2004.

[21] Guoa Y， Suhc K， Kuroseb J，et al. DirectStream: A directory-based peer-to-peer video streaming service[J].Computer Communications， 2008，31(3):520-536.

[22] Heefeda M， Bhargvaa B.On-demand Media Srtemaing Over the Internet[C]In Proceedings of 9th IEEE workshop on Future Trends of Distributed Computing Systems(FTDCS03).SanJuna，PuertoRieo，2003.

[23] 風行website.[EB\\OL].www.funshion.com

[24] Qvod website.[EB\\OL].www.qvod.com

[25] Maymounkov M， Mazières D. Kademlia: A Peer-to-peer Information System Based on the XOR Metric[C]. IPTPS 2002，LNCS 2429，2002:53-65.

[26] Overnet.[EB\\OL].http://en.wikipedia.org/wiki/Overnet.

[27] eMule.[EB\\OL]. http://en.wikipedia.org/wiki/Emule.

[28] BitTorrent.[EB\\OL]. http://en.wikipedia.org/wiki/Bittorrent.

[29] Bram Cohen.Incentives Build Robustness in BitTorrent.2003.

[30] SHA algorithm.[EB\\OL].http://en.wikipedia.org/wiki/SHA-1.