摘要：本文在研究分析現(xiàn)有P2P 視頻直播系統(tǒng)的基礎(chǔ)上，提出了SLOP 系統(tǒng)中最少優(yōu)先的動態(tài)數(shù)據(jù)量請求調(diào)度算法，并進(jìn)行了仿真分析，得到相應(yīng)結(jié)論。

1 前言

SLOP 是Streaming Live media Over Peer-to-peer 的簡稱，它是一個基于P2P 技術(shù)的視頻直播傳輸系統(tǒng)，其在視頻直播系統(tǒng)中的位置見圖1。它將觀看同一節(jié)目的所有用戶組成一個覆蓋網(wǎng)，覆蓋網(wǎng)內(nèi)結(jié)點(diǎn)通過相互協(xié)作完成數(shù)據(jù)的傳輸?，F(xiàn)有的P2P 視頻直播系統(tǒng)在覆蓋網(wǎng)技術(shù)和數(shù)據(jù)交換技術(shù)兩方面都存在著值得改進(jìn)的地方，本文重點(diǎn)研究視頻直播傳輸系統(tǒng)中的數(shù)據(jù)交換問題。

P2P 視頻直播系統(tǒng)中面對的是實(shí)時流動的數(shù)據(jù)，結(jié)點(diǎn)的緩沖區(qū)大小有限，只有保證結(jié)點(diǎn)之間的數(shù)據(jù)窗口有相互重疊的數(shù)據(jù)它們才能進(jìn)行相互交換數(shù)據(jù)。P2P 視頻直播系統(tǒng)中采用滑動窗口的機(jī)制，結(jié)點(diǎn)只能緩存當(dāng)前播放點(diǎn)前后的一小段數(shù)據(jù)，需要提供一種機(jī)制保證所有結(jié)點(diǎn)窗口內(nèi)的數(shù)據(jù)有重疊部分才能夠相互協(xié)作交換數(shù)據(jù)。另外P2P 視頻直播系統(tǒng)中不建立數(shù)據(jù)傳輸?shù)臉浣Y(jié)構(gòu)，因而需要實(shí)時交換窗口內(nèi)的數(shù)據(jù)狀態(tài)信息，這種數(shù)據(jù)狀態(tài)信息是一個種額外的開銷，應(yīng)該越小越好，所以，提供更好更及時的數(shù)據(jù)狀態(tài)交換算法也是研究的要點(diǎn)。

P2P 視頻直播系統(tǒng)中的數(shù)據(jù)要求實(shí)時性，而結(jié)點(diǎn)又采用亂序的方式獲取數(shù)據(jù)，因而結(jié)點(diǎn)之間數(shù)據(jù)的差異性，和選擇什么數(shù)據(jù)塊由什么結(jié)點(diǎn)來傳輸是一個關(guān)鍵性問題。選擇恰當(dāng)?shù)慕Y(jié)點(diǎn)傳輸恰當(dāng)?shù)臄?shù)據(jù)塊是發(fā)揮系統(tǒng)中所有結(jié)點(diǎn)能力的關(guān)鍵，也是提升系統(tǒng)擴(kuò)展能力的關(guān)鍵。如果都選擇最新的數(shù)據(jù)塊傳輸，就不能發(fā)揮結(jié)點(diǎn)之間協(xié)同的能力而降低系統(tǒng)的擴(kuò)展性。因而現(xiàn)在一般都采用數(shù)據(jù)塊的提供者最少的先下載，選擇什么結(jié)點(diǎn)什么時間傳輸該塊決定了緩沖窗口內(nèi)的數(shù)據(jù)能否使得結(jié)點(diǎn)正常進(jìn)行播放，也影響著其它的結(jié)點(diǎn)獲取數(shù)據(jù)。因而提供一種讓結(jié)點(diǎn)之間負(fù)載均衡又能滿足播放要求的數(shù)據(jù)塊請求算法是非常必要的。

2 基本思想

SLOP 系統(tǒng)中結(jié)點(diǎn)之間相互協(xié)作并利用彼此的上傳帶寬來及時的獲得數(shù)據(jù)。那么數(shù)據(jù)塊的請求調(diào)度需要考慮兩個方面，數(shù)據(jù)塊的分布和結(jié)點(diǎn)的上傳帶寬。數(shù)據(jù)塊的分布必須均勻，分布均勻是指鄰居結(jié)點(diǎn)之間享有不同的數(shù)據(jù)塊。首先分布均勻使得結(jié)點(diǎn)之間有不同的數(shù)據(jù)。這是它們能相互交換數(shù)據(jù)的前提條件。其次分布均勻不會使得某個結(jié)點(diǎn)成為新的中心結(jié)點(diǎn)而出現(xiàn)瓶頸。結(jié)點(diǎn)的上傳帶寬是高度動態(tài)變化的，系統(tǒng)必須適應(yīng)這種帶寬動態(tài)變化的網(wǎng)絡(luò)環(huán)境。首先，寬帶網(wǎng)的飛速發(fā)展雖然提高了結(jié)點(diǎn)與服務(wù)器之間的帶寬，但是結(jié)點(diǎn)與結(jié)點(diǎn)之間的帶寬因跨越跳數(shù)較多仍然較低。其次，結(jié)點(diǎn)是異構(gòu)的，它們接入網(wǎng)絡(luò)的方式不同導(dǎo)致其上傳帶寬也不一樣。最后，結(jié)點(diǎn)處在一個高度動態(tài)變化的環(huán)境之中，它的上傳帶寬受網(wǎng)絡(luò)流量的影響而不停變化。塊請求調(diào)度算法在為每個鄰居分配上傳任務(wù)時必須考慮這種情況。因此，數(shù)據(jù)塊分布不均勻?qū)?dǎo)致無法有效利用結(jié)點(diǎn)的上傳帶寬，不考慮結(jié)點(diǎn)的上傳帶寬的動態(tài)性而分配數(shù)據(jù)塊請求量會導(dǎo)致不能及時獲得數(shù)據(jù)。

本文提出在 SLOP 中采用最少優(yōu)先的動態(tài)數(shù)據(jù)量請求調(diào)度算法來應(yīng)對上述兩個因素。所謂最少優(yōu)先即結(jié)點(diǎn)首先請求鄰居數(shù)最少的塊，同時也隱含著對鄰居數(shù)相同的塊隨機(jī)請求。最少優(yōu)先使得數(shù)據(jù)能夠快速的蔓延到結(jié)點(diǎn)之中，并且使之分布均勻。這樣結(jié)點(diǎn)之間就擁有彼此不同的數(shù)據(jù)而能相互請求。所謂動態(tài)數(shù)據(jù)量即每次鄰居連接管理器依據(jù)鄰居連接上次數(shù)據(jù)的獲取情況重新計(jì)算下次應(yīng)該分配的請求數(shù)據(jù)量。動態(tài)數(shù)據(jù)量請求實(shí)時的適應(yīng)了網(wǎng)絡(luò)帶寬的動態(tài)變化，能讓強(qiáng)能力的鄰居提供更多的數(shù)據(jù)，而弱能力的鄰居也能提供數(shù)據(jù)。

3 最少優(yōu)先的動態(tài)數(shù)據(jù)量請求調(diào)度算法

該算法包含四個內(nèi)容點(diǎn)，劃分塊、交換數(shù)據(jù)塊狀態(tài)信息、分配數(shù)據(jù)量和選擇數(shù)據(jù)塊。劃分塊是交換數(shù)據(jù)狀態(tài)信息的基礎(chǔ)，數(shù)據(jù)塊狀態(tài)信息以塊為單位進(jìn)行描述。數(shù)據(jù)狀態(tài)信息又是選擇數(shù)據(jù)塊的基礎(chǔ)，結(jié)點(diǎn)只能向有該數(shù)據(jù)塊的鄰居發(fā)起對該塊的請求。分配數(shù)據(jù)量依據(jù)鄰居結(jié)點(diǎn)上次提供的數(shù)據(jù)量進(jìn)行動態(tài)調(diào)整。這四個內(nèi)容點(diǎn)彼此相連構(gòu)成該算法。

3.1 劃分塊

我們用 K 代表塊的大小。塊越小描述塊的信息就越多，導(dǎo)致結(jié)點(diǎn)間鏈路開銷增大。數(shù)據(jù)量以塊為單位分配，塊越大就無法分配較小的數(shù)據(jù)量。我們用W 表示結(jié)點(diǎn)緩沖窗口能存放塊的數(shù)目。W 太小使得結(jié)點(diǎn)之間沒有彼此需要的數(shù)據(jù)而不能達(dá)到利用結(jié)點(diǎn)的上傳帶寬的目的。緩沖的塊數(shù)目越多，后續(xù)結(jié)點(diǎn)與源節(jié)目播放的時間差就越長。當(dāng)前，SLOP 中默認(rèn)設(shè)定K=4KB，W＝4000。

3.2 交換數(shù)據(jù)塊狀態(tài)信息

我們利用三字節(jié)來描述一段序號連續(xù)的數(shù)目不大于 255 的塊組，這樣描述4000 個連續(xù)的塊只需要48 字節(jié)。鄰居連接對象記錄對應(yīng)鄰居發(fā)送來的數(shù)據(jù)塊狀態(tài)信息和發(fā)送給對方的數(shù)據(jù)塊狀態(tài)信息。結(jié)點(diǎn)周期性的將緩沖窗口內(nèi)數(shù)據(jù)塊狀態(tài)信息與已發(fā)送的和鄰居發(fā)送的數(shù)據(jù)狀態(tài)信息之間的差值發(fā)送給鄰居結(jié)點(diǎn)，結(jié)點(diǎn)之間數(shù)據(jù)塊狀態(tài)信息的交換是必須的，因此我們采用這種增量的方法來減少這種開銷。我們設(shè)Rkbps 為當(dāng)前的頻道的碼率，G<V,E>為結(jié)點(diǎn)構(gòu)成的覆蓋網(wǎng)絡(luò)，當(dāng)所有結(jié)點(diǎn)都下載W 個數(shù)據(jù)塊時，最壞情況即用3 字節(jié)表示一個塊時產(chǎn)生的開銷為|E|×W×3×8bit，下載的數(shù)據(jù)總量為W×|V|×K×1024×8bit，開銷與數(shù)據(jù)的比值為(3×|E|)/(|V|×K×1024)，在每個結(jié)點(diǎn)平均連接30 個鄰居且K=4KB 的負(fù)載1.1％。我們的實(shí)際運(yùn)行中塊大部分都是以大于15 個連續(xù)的塊出現(xiàn)，因而實(shí)際中的負(fù)責(zé)肯定小于0.1％左右。

當(dāng)結(jié)點(diǎn)收到鄰居發(fā)送來的數(shù)據(jù)狀態(tài)信息時，它首先將該信息加入到鄰居連接對象的已接收數(shù)據(jù)塊狀態(tài)信息中，同時通知成員管理器增加緩沖窗口內(nèi)數(shù)據(jù)狀態(tài)信息中對應(yīng)塊鄰居數(shù)目。

當(dāng)與鄰居結(jié)點(diǎn)的連接斷開時，必須通知鄰居管理器減少緩沖窗口內(nèi)數(shù)據(jù)狀態(tài)信息中對應(yīng)塊鄰居數(shù)目，這樣才使得鄰居管理器記錄的緩沖窗口內(nèi)數(shù)據(jù)狀態(tài)信息正確，以保證塊選擇算法的正確性。

3.3 分配數(shù)據(jù)塊數(shù)目

數(shù)據(jù)量的分配依據(jù)鄰居結(jié)點(diǎn)上次完成的情況周期性動態(tài)計(jì)算。設(shè)定 T 為每秒請求數(shù)據(jù)塊的上限，設(shè)定為2×R/（K×8）＝R/4K。設(shè)定I 為每秒請求數(shù)據(jù)塊的下限，設(shè)定為4。設(shè)定G 為上秒請求的塊數(shù)目，F(xiàn) 為上秒完成塊的數(shù)目，C 為本秒將請求的數(shù)據(jù)塊數(shù)目。如果F 等于G，那么C 等于MIN（2×G，T）。如果F 小于G/2，那么C 等于0。如果F 大于等于G/2 小于L，那么C 等于MAX（I，F(xiàn)－（G－F））。

3.4 選擇數(shù)據(jù)塊

在計(jì)算出該秒該鄰居應(yīng)該提供多少數(shù)據(jù)塊之后，鄰居管理器利用鄰居對象的數(shù)據(jù)塊狀態(tài)信息選取塊。為了保證數(shù)據(jù)的及時性，我們把緩沖窗口分為兩個部分，前1000 個塊必須是立即獲取的，而后3000 個塊依據(jù)最少優(yōu)先的選取策略，最少優(yōu)先的選取策略為首先選擇鄰居數(shù)目最少的塊，如果遇到多個塊有相同的鄰居數(shù)據(jù)就隨機(jī)選擇，同時把C 設(shè)定為實(shí)際選出的塊數(shù)目，修改鄰居管理器中數(shù)據(jù)塊的狀態(tài)為請求中，再向鄰居發(fā)起請求。

結(jié)點(diǎn)與鄰居斷開時，若還有請求沒有完成時結(jié)點(diǎn)通知鄰居管理器恢復(fù)請求中的這些塊為未請求狀態(tài)，以便給其它的鄰居提供。

結(jié)點(diǎn)收到鄰居發(fā)來的數(shù)據(jù)后，將數(shù)據(jù)寫入鄰居管理器中的緩沖窗口中，同時更新該塊數(shù)據(jù)的狀態(tài)為已獲得。這種信息將在交換數(shù)據(jù)塊狀態(tài)信息的處理中發(fā)送給其它的鄰居結(jié)點(diǎn)。

圖2 實(shí)驗(yàn)結(jié)構(gòu)圖

4 性能*價(jià)

我們從頻道質(zhì)量、交換狀態(tài)信息開銷量和源負(fù)載量三個方面來*價(jià)該算法。我們定義頻道質(zhì)量為結(jié)點(diǎn)播放頻道時一段時間內(nèi)丟失的數(shù)據(jù)量和全部數(shù)據(jù)量的比值，用Q 表示。交換狀態(tài)信息開銷量用狀態(tài)信息交換的數(shù)據(jù)量和實(shí)際傳輸數(shù)據(jù)的量之間的比值來描述，用O 表示。源的負(fù)載量定義為源當(dāng)前輸出的帶寬對頻道碼率的倍數(shù)，用L 表示。質(zhì)量越好，用戶的感觀效果越好就更能滿足應(yīng)用的要求，當(dāng)Q 為1 時表示沒有任何數(shù)據(jù)的丟失或延遲到達(dá)。交換狀態(tài)信息的數(shù)據(jù)量越小，O 也就越小。對于客戶端/服務(wù)器模式系統(tǒng)該值隨著用戶數(shù)增加同比率增加，而對于SLOP 系統(tǒng)來說該值增長緩慢而且到達(dá)一定值后不再增大。

在模擬實(shí)驗(yàn)中難以模擬結(jié)點(diǎn)之間的帶寬變化情況，所以該算法的性能我們通過采集系統(tǒng)實(shí)際運(yùn)行的數(shù)據(jù)所得。因?qū)嶋H運(yùn)行中條件和環(huán)境的限制，目前系統(tǒng)的用戶數(shù)最高僅在30 人左右。但是這些數(shù)據(jù)也可以真實(shí)的反映算法的性能。下面所得的數(shù)據(jù)在局域網(wǎng)內(nèi)部完成即每個機(jī)器都能夠被訪問到且具有類似的帶寬。如圖2 所示，直播源放在一臺單獨(dú)的服務(wù)器上并使用NetMeter 軟件測量從某時刻開始一段時間內(nèi)的帶寬值。SLOP 系統(tǒng)中使用突發(fā)的方式進(jìn)行數(shù)據(jù)傳輸，因而我們測量10 分鐘內(nèi)的平均帶寬值代表系統(tǒng)在這段穩(wěn)定時間內(nèi)服務(wù)器輸出的帶寬。Tracker 部署在另一臺服務(wù)器上。每臺PC 機(jī)上運(yùn)行0-5 個客戶端。當(dāng)K=20KB 時，每個客戶端需要80MB 左右的內(nèi)存。我們的PC 機(jī)內(nèi)存為512，為保證系統(tǒng)的正常運(yùn)行因此每個PC 機(jī)最多運(yùn)行5 個客戶端。每個客戶端負(fù)責(zé)記錄一段時間內(nèi)丟失的數(shù)據(jù)塊和收到的數(shù)據(jù)塊數(shù)，以及該客戶端與所有鄰居交換的數(shù)據(jù)量以及數(shù)據(jù)塊狀態(tài)信息量。在系統(tǒng)測試中，我們選擇能達(dá)到VHS 半屏質(zhì)量的320kbps 碼率，塊的大小分為4KB 和20KB 兩種情況。

（1） 頻道質(zhì)量

在 SLOP 系統(tǒng)的測試中，無論K 為4KB 還是20KB，頻道的質(zhì)量都在100％。在Internet 環(huán)境中，頻道會因?yàn)椴糠纸Y(jié)點(diǎn)接入帶寬低而導(dǎo)致質(zhì)量下降，但目前都大于90％。

（2） 源負(fù)載量

對于客戶端/服務(wù)器模式的視頻直播系統(tǒng)而言，源負(fù)載量為系統(tǒng)當(dāng)前的用戶數(shù)，如圖3 中三角形標(biāo)記的直線。而對于P2P 系統(tǒng)來說，源負(fù)載量將遠(yuǎn)遠(yuǎn)小于系統(tǒng)中的用戶數(shù)。從圖3 中可以看到用戶數(shù)為30 時，K 為4KB 的源負(fù)載僅為7.6，K 為20KB 的源負(fù)載僅為9.6。同時曲線隨著用戶數(shù)的增加其增長幅度越來越緩慢。我們也可以看出K 為20KB 和4KB 時它們在用戶數(shù)大于15時出現(xiàn)差異，K=20KB 的曲線增長更快。這是因?yàn)镵=20KB 時，塊比較大導(dǎo)致結(jié)點(diǎn)隨機(jī)交換數(shù)據(jù)時分布不均勻從而被迫從源獲取更多的數(shù)據(jù)。在我們的實(shí)際中也發(fā)現(xiàn)，K=4KB 時更加適合Internet中的用戶。從源負(fù)載的降低上，我們可以看出數(shù)據(jù)塊在結(jié)點(diǎn)之間的分布是均勻的，結(jié)點(diǎn)相互利用了彼此的上傳帶寬。

（3） 交換狀態(tài)信息開銷

圖 4 給出結(jié)點(diǎn)鄰居數(shù)不同時交換狀態(tài)信息的開銷。結(jié)點(diǎn)與每個鄰居都要進(jìn)行狀態(tài)信息的交換，因而鄰居數(shù)的增加這種狀態(tài)信息必然增多。上文中我們分析指出塊越大交換狀態(tài)信息開銷就越少，從圖4 中我們也可以看出。系統(tǒng)的測試中，結(jié)點(diǎn)的最大鄰居數(shù)為23 時，K 為4KB 時開銷為0.440‰，K 為20KB 時開銷為0.394‰。SLOP 的實(shí)際運(yùn)行中，結(jié)點(diǎn)的鄰居數(shù)一般設(shè)定在30 左右，因此交換狀態(tài)信息的開銷不超過0.500‰。從圖4 的曲線中我們可以看出曲線的增長隨著鄰居數(shù)的增加而變緩慢。一方面是因?yàn)榻Y(jié)點(diǎn)鄰居數(shù)增多它就能更快的獲得數(shù)據(jù)塊，使得數(shù)據(jù)塊連續(xù)而降低其描述信息。另一方面是差值法的狀態(tài)信息交換方法，使得結(jié)點(diǎn)與鄰居之間同時發(fā)送相同信息的概率降低。

圖4 鄰居數(shù)與數(shù)據(jù)塊信息開銷

5 結(jié)束語

從上面的分析和實(shí)驗(yàn)結(jié)果來看，首先SLOP 視頻直播傳輸系統(tǒng)能夠正確完成傳輸視頻流數(shù)據(jù)。其次，SLOP 系統(tǒng)極大的減輕了直播源的負(fù)載，而且有效的利用了鄰居結(jié)點(diǎn)的上傳帶寬。最后，數(shù)據(jù)塊狀態(tài)信息的交換量不超過0.500‰，這個值遠(yuǎn)小于現(xiàn)有的任何系統(tǒng)。

本文作者創(chuàng)新點(diǎn)：作者在研究分析了現(xiàn)有基于P2P 視頻直播系統(tǒng)的基礎(chǔ)上，在SLOP 系統(tǒng)中提出了最少優(yōu)先的動態(tài)數(shù)據(jù)量請求調(diào)度算法，不僅有效的降低了直播源的負(fù)載，提供了系統(tǒng)的擴(kuò)展性，同時該算法產(chǎn)生的額外信息開銷被降低到0.500‰。