一種基于節(jié)點(diǎn)能力區(qū)分的Pareto最優(yōu)網(wǎng)絡(luò)編碼組播方法
2016-05-14 10:33:51鄭力明符永銓李曉冬
軟件工程 2016年7期
鄭力明 符永銓 李曉冬
摘 要：快速數(shù)據(jù)分發(fā)在突發(fā)事件響應(yīng)，軍事領(lǐng)域等具有重要的應(yīng)用。針對(duì)異構(gòu)用戶節(jié)點(diǎn)群體下快速數(shù)據(jù)分發(fā)問題，提出基于能力區(qū)分的拓?fù)錁?gòu)建和速率控制的網(wǎng)絡(luò)編碼組播協(xié)議CORE。CORE利用能力區(qū)分的自適應(yīng)層次化拓?fù)錁?gòu)建鼓勵(lì)節(jié)點(diǎn)提供高的上傳帶寬并優(yōu)化系統(tǒng)范圍吞吐率；利用直方圖的方式對(duì)基于網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸進(jìn)行流量控制，降低冗余數(shù)據(jù)的傳輸；基于分布式的速率控制實(shí)現(xiàn)Pareto最優(yōu)的下載速率分配。實(shí)驗(yàn)結(jié)果表明CORE具有良好的可擴(kuò)展性，能夠充分利用異構(gòu)節(jié)點(diǎn)的上傳能力，提供區(qū)分的下載帶寬分配，較高的數(shù)據(jù)傳輸吞吐率、低端到端網(wǎng)絡(luò)延遲，能夠提供異構(gòu)網(wǎng)絡(luò)環(huán)境下分發(fā)時(shí)間緊迫的數(shù)據(jù)分發(fā)服務(wù)。
關(guān)鍵詞：數(shù)據(jù)分發(fā)；網(wǎng)絡(luò)編碼；能力區(qū)分；速率分配
中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A
1 引言（Introduction）
覆蓋網(wǎng)通過將數(shù)據(jù)傳輸負(fù)載分布到用戶節(jié)點(diǎn)極大提高了數(shù)據(jù)分發(fā)[1]過程的擴(kuò)展性，然而基于覆蓋網(wǎng)的數(shù)據(jù)分發(fā)存在“搭便車”（free loader）的問題[2]：一些節(jié)點(diǎn)消耗覆蓋網(wǎng)的數(shù)據(jù)傳輸能力卻不能提供足夠的上傳能力。已有的基于激勵(lì)機(jī)制的覆蓋網(wǎng)數(shù)據(jù)分發(fā)協(xié)議關(guān)注在傳統(tǒng)存儲(chǔ)轉(zhuǎn)發(fā)環(huán)境下用戶間的協(xié)作[3-5]，然而在利用網(wǎng)絡(luò)編碼技術(shù)的快速數(shù)據(jù)分發(fā)環(huán)境下面臨如何在適合網(wǎng)絡(luò)編碼組播的拓?fù)浣Y(jié)構(gòu)中實(shí)現(xiàn)能力區(qū)分；如何調(diào)度網(wǎng)絡(luò)編碼傳輸速率實(shí)現(xiàn)優(yōu)化的下載帶寬分配等問題。同時(shí)網(wǎng)絡(luò)編碼環(huán)境下已有的基于速率控制的優(yōu)化方式假設(shè)存在獨(dú)立的服務(wù)節(jié)點(diǎn)[6-8]，需要額外的部署開銷。
針對(duì)異構(gòu)節(jié)點(diǎn)群體實(shí)現(xiàn)快速數(shù)據(jù)分發(fā)的問題，提出了基于能力區(qū)分的方式進(jìn)行拓?fù)錁?gòu)建和速率控制的網(wǎng)絡(luò)編碼組播協(xié)議CORE（Capacity-differentiation Optimal REsilient multicast based on network coding）。模擬測(cè)試顯示CORE協(xié)議具有高度的擴(kuò)展性，較高的吞吐率和低端到端延遲等優(yōu)點(diǎn)。
2 相關(guān)工作（Related work）
由于覆蓋網(wǎng)環(huán)境下用戶節(jié)點(diǎn)提供上傳能力需要消耗本節(jié)點(diǎn)的網(wǎng)絡(luò)傳輸能力，研究發(fā)現(xiàn)覆蓋網(wǎng)中存在大量的不提供上傳帶寬而僅獲取數(shù)據(jù)的用戶節(jié)點(diǎn)，導(dǎo)致請(qǐng)求信息被轉(zhuǎn)發(fā)到系統(tǒng)中提供數(shù)據(jù)下載服務(wù)的少量節(jié)點(diǎn)（稱為“tragedy of the commons”）[2]。針對(duì)覆蓋網(wǎng)環(huán)境下用戶節(jié)點(diǎn)服務(wù)區(qū)分和激勵(lì)問題，已有的研究包括：文件共享環(huán)境下單個(gè)節(jié)點(diǎn)上傳帶寬分配機(jī)制[3]，多個(gè)覆蓋網(wǎng)數(shù)據(jù)傳輸會(huì)話優(yōu)先調(diào)度和帶寬分配[4]，集中式的基于微分方程建模提供靜態(tài)組播環(huán)境下不同服務(wù)質(zhì)量[5]等。另一方面，為了利用不同能力的節(jié)點(diǎn)，F(xiàn)lorida大學(xué)的Zhang等在結(jié)構(gòu)化覆蓋網(wǎng)環(huán)上利用異構(gòu)節(jié)點(diǎn)上傳能力進(jìn)行任意源組播（any source multicast）[9]，沒有考慮服務(wù)區(qū)分等問題。然而在基于網(wǎng)絡(luò)編碼快速數(shù)據(jù)分發(fā)環(huán)境下，面臨新的問題包括：如何構(gòu)建節(jié)點(diǎn)能力感知的高效拓?fù)浣Y(jié)構(gòu)以提高數(shù)據(jù)分發(fā)的吞吐率，如何在適合網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)的拓?fù)浣Y(jié)構(gòu)中實(shí)現(xiàn)能力區(qū)分；如何調(diào)度數(shù)據(jù)傳輸速率實(shí)現(xiàn)優(yōu)化的下載帶寬分配。
在網(wǎng)絡(luò)編碼組播環(huán)境下資源優(yōu)化的研究基于網(wǎng)絡(luò)流模型，典型工作如Toronto大學(xué)的Li等[6]假定鏈路的速率和容量為固定，利用Langrangian對(duì)偶方式最大化系統(tǒng)范圍吞吐率；MIT的Wu等[8]為每個(gè)組播鏈路流設(shè)定開銷函數(shù)，通過尋找最優(yōu)的編碼子圖（每個(gè)會(huì)話在每個(gè)鏈路的傳輸數(shù)據(jù)量）來最小化網(wǎng)絡(luò)編碼組播環(huán)境下的傳輸開銷；加州理工的Chen[7]等利用速率控制優(yōu)化系統(tǒng)范圍的特定性能目標(biāo)，通過源節(jié)點(diǎn)調(diào)整傳輸速率，以及轉(zhuǎn)發(fā)節(jié)點(diǎn)在多個(gè)組播會(huì)話間調(diào)度的調(diào)度實(shí)現(xiàn)最大化系統(tǒng)效用。
3 系統(tǒng)模型（System model）
將用戶節(jié)點(diǎn)組成的網(wǎng)絡(luò)建模為有向圖G（V，E），V為節(jié)點(diǎn)集合，E為邊集。節(jié)點(diǎn)集V包含兩類節(jié)點(diǎn)：源節(jié)點(diǎn)S和接收節(jié)點(diǎn)T（接收節(jié)點(diǎn)作為中間轉(zhuǎn)發(fā)節(jié)點(diǎn)）。。邊集，每個(gè)邊具有最大帶寬容量。假定每個(gè)節(jié)點(diǎn)i具有一個(gè)網(wǎng)絡(luò)坐標(biāo)xi，同時(shí)緩存源節(jié)點(diǎn)的網(wǎng)絡(luò)坐標(biāo)xs（假定網(wǎng)絡(luò)坐標(biāo)為真實(shí)的且相對(duì)穩(wěn)定，虛假坐標(biāo)處理可通過發(fā)送額外的探測(cè)數(shù)據(jù)包實(shí)現(xiàn)）。每個(gè)節(jié)點(diǎn)i具有一個(gè)標(biāo)識(shí)符i.id，以及一個(gè)層次level，標(biāo)識(shí)符在節(jié)點(diǎn)參與系統(tǒng)的生命期內(nèi)唯一，然而節(jié)點(diǎn)i的level值可能因網(wǎng)絡(luò)的演化而變動(dòng)。節(jié)點(diǎn)i在加入時(shí)聲明自己的上傳帶寬bui和下載帶寬bdi。
為了顯示能力區(qū)分的有效性，給出下列示例（如圖1（a）—圖（d）所示，假定所有節(jié)點(diǎn)在線），其中每個(gè)節(jié)點(diǎn)的參數(shù)配置利用三元組表示，分別代表接收節(jié)點(diǎn)的優(yōu)先度，上傳帶寬和下載帶寬（單位為Mbps），接收節(jié)點(diǎn)參數(shù)配置為：
設(shè)定源節(jié)點(diǎn)S最大子女?dāng)?shù)為2，上傳帶寬為1Mbps。圖1中有向邊代表數(shù)據(jù)傳輸方向，邊上的值為該邏輯連接的傳輸帶寬?？疾煜螺d帶寬公平分配和按照優(yōu)先度分配，前者下載節(jié)點(diǎn)平均獲取父節(jié)點(diǎn)帶寬，后者設(shè)定節(jié)點(diǎn)優(yōu)先度越大，獲取下載帶寬越高。圖1（a）為無能力區(qū)分拓?fù)錁?gòu)建，下載帶寬公平分配；圖1（b）為無能力區(qū)分拓?fù)錁?gòu)建，帶寬根據(jù)節(jié)點(diǎn)優(yōu)先度分配；圖1（c）為能力區(qū)分拓?fù)錁?gòu)建，下載帶寬公平分配；圖1（d）為無能力區(qū)分拓?fù)錁?gòu)建，帶寬根據(jù)優(yōu)先度分配。
結(jié)果顯示圖1（a）平均吞吐率為0.34Mbps，圖1（b）平均吞吐量為0.34Mbps，圖1（c）平均吞吐率為0.41Mbps，圖1（d）平均吞吐率為0.43Mbps。圖1（c）和圖1（d）吞吐率的提高顯示能力區(qū)分的拓?fù)錁?gòu)建可以有效地利用當(dāng)前節(jié)點(diǎn)的上傳帶寬，從而提高系統(tǒng)范圍節(jié)點(diǎn)的吞吐率；同時(shí)圖1（d）通過基于能力區(qū)分的速率控制提升了高優(yōu)先度節(jié)點(diǎn)的下載帶寬，從而提高其上傳能力，因而在圖1（c）的基礎(chǔ)上進(jìn)一步增加了系統(tǒng)范圍的吞吐率。
CORE的目標(biāo)是鼓勵(lì)節(jié)點(diǎn)提高上傳帶寬，提高數(shù)據(jù)傳輸?shù)耐掏侣?，降低?shù)據(jù)完成時(shí)間；緩解單源節(jié)點(diǎn)數(shù)據(jù)分發(fā)的瓶頸，提高下游節(jié)點(diǎn)的傳輸帶寬；充分利用網(wǎng)絡(luò)編碼消除請(qǐng)求特定數(shù)據(jù)塊的優(yōu)勢(shì)，降低因完成數(shù)據(jù)傳輸?shù)慕邮展?jié)點(diǎn)突然退出導(dǎo)致的性能下降問題。
CORE以能力區(qū)分的方式將節(jié)點(diǎn)分為多個(gè)不相交的層次，每個(gè)節(jié)點(diǎn)根據(jù)優(yōu)先度大小確定加入的層次，高貢獻(xiàn)的節(jié)點(diǎn)位于較高的層次以降低距源節(jié)點(diǎn)的端到端延遲，源節(jié)點(diǎn)分發(fā)數(shù)據(jù)時(shí)按照層次由高到低的方向傳輸數(shù)據(jù)。
4 能力感知的近似Butterfly網(wǎng)絡(luò)構(gòu)造（The ability
to perceive the approximate butterfly network
structure）
為了提高基于網(wǎng)絡(luò)編碼方式下系統(tǒng)范圍節(jié)點(diǎn)吞吐率，降低數(shù)據(jù)傳輸?shù)亩说蕉搜舆t，同時(shí)基于節(jié)點(diǎn)貢獻(xiàn)能力實(shí)現(xiàn)區(qū)分的服務(wù)，構(gòu)建一個(gè)類似Butterfly網(wǎng)絡(luò)的有向無環(huán)的拓?fù)浣Y(jié)構(gòu)（Approximate Butterfly Network，ABN）。
任意層次L的一個(gè)節(jié)點(diǎn)i具有三類連接：
（1）數(shù)據(jù)連接（General Link）：與層L-1（L+1）的父節(jié)點(diǎn)和層L+1（L不為最底層）的子女節(jié)點(diǎn)建立的傳輸編碼數(shù)據(jù)的連接。
（2）同層連接（Level Link）：同一層次節(jié)點(diǎn)間建立的邏輯連接以維護(hù)不同層間容量范圍的嚴(yán)格不相交。
（3）Butterfly連接（Butterfly Link）：與層L-1和層L+1的各一個(gè)隨機(jī)節(jié)點(diǎn)建立的邏輯連接，分別稱為上、下Butterfly連接，負(fù)責(zé)引導(dǎo)新節(jié)點(diǎn)加入和無偏抽樣對(duì)應(yīng)層的節(jié)點(diǎn)。
圖2給出了一個(gè)四層的ABN拓?fù)?，虛線代表同層連接，實(shí)線為數(shù)據(jù)連接（部分?jǐn)?shù)據(jù)連接作為Butterfly連接）。
4.1 自適應(yīng)分層
在層次數(shù)為1時(shí)，拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)化為所有節(jié)點(diǎn)隨機(jī)連接的mesh網(wǎng)絡(luò)，而在層次數(shù)為N時(shí)，拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)化為線性連接。理想的層次數(shù)需要保證任意節(jié)點(diǎn)距源節(jié)點(diǎn)所有路徑的最大延遲最低，即：
啟發(fā)式算法包括分割當(dāng)前最底層和合并當(dāng)前層兩部分：
（1）分割。若當(dāng)前最低層到達(dá)最大容量后，在新的節(jié)點(diǎn)到來時(shí)，建立一個(gè)新的節(jié)點(diǎn)層。
（2）合并。若第L+1層的實(shí)際節(jié)點(diǎn)數(shù)目<，且在第L+1層所有節(jié)點(diǎn)加入第L層后，第L層節(jié)點(diǎn)數(shù)目<，則將層L+1與層L合并。
4.2 基于滑動(dòng)窗口路由機(jī)制判定層次容量范圍
為了輕量級(jí)的估計(jì)每層的容量范圍，實(shí)現(xiàn)基于能力區(qū)分的自適應(yīng)分層，提出基于滑動(dòng)窗口方式動(dòng)態(tài)的維護(hù)每層容量范圍。任意節(jié)點(diǎn)i在時(shí)刻t維護(hù)一個(gè)當(dāng)前層容量范圍的滑動(dòng)窗，緩存已知的當(dāng)前層最小和最大的優(yōu)先度及對(duì)應(yīng)的節(jié)點(diǎn)地址。為了動(dòng)態(tài)的維護(hù)當(dāng)前層容量范圍，節(jié)點(diǎn)i利用gossip方式[10]與同層的其他節(jié)點(diǎn)j交換值，然后更新滑動(dòng)窗口：
節(jié)點(diǎn)i在接收到查找當(dāng)前層容量范圍時(shí)，將查找請(qǐng)求轉(zhuǎn)發(fā)到對(duì)應(yīng)的地址，然后上述轉(zhuǎn)發(fā)過程遞歸執(zhí)行，最終返回當(dāng)前節(jié)點(diǎn)已知的最小和最大優(yōu)先度的節(jié)點(diǎn)。
5 基于直方圖的連續(xù)網(wǎng)絡(luò)編碼傳輸機(jī)制（Based
on the histogram of a continuous network coding
transmission mechanism）
直方圖構(gòu)建：每個(gè)父節(jié)點(diǎn)i維護(hù)一個(gè)緩存BlockCachei，保存已接收的編碼數(shù)據(jù)塊集合Bi（t）及對(duì)應(yīng)的編碼系數(shù)向量矩陣Mi（t），記為二元組
其中，為節(jié)點(diǎn)i在t時(shí)刻已發(fā)送到節(jié)點(diǎn)j的編碼塊數(shù)目，隨著父節(jié)點(diǎn)傳輸編碼塊數(shù)目而遞增。這樣父節(jié)點(diǎn)維護(hù)一個(gè)允許傳輸?shù)矫總€(gè)子女節(jié)點(diǎn)數(shù)據(jù)塊數(shù)目的直方圖，如圖3所示。父節(jié)點(diǎn)在接收到新的編碼數(shù)據(jù)時(shí)，更新每個(gè)子女節(jié)點(diǎn)對(duì)應(yīng)，然后以push方式連續(xù)傳輸至多個(gè)編碼數(shù)據(jù)塊至對(duì)應(yīng)子女節(jié)點(diǎn)j。
6.1 問題建模
假設(shè)節(jié)點(diǎn)j上傳和下載能力分別為Pj、Qj，設(shè)節(jié)點(diǎn)j從父節(jié)點(diǎn)i處獲取數(shù)據(jù)得到效用值為，為的非減函數(shù)，為父節(jié)點(diǎn)沿鏈路的傳輸帶寬，假定為嚴(yán)格的凹函數(shù)且二階可微[11]。設(shè)節(jié)點(diǎn)集合V中節(jié)點(diǎn)按序編號(hào)為，邊集為E。
為保證高優(yōu)先度的節(jié)點(diǎn)獲得高的分配帶寬，設(shè)定效用函數(shù)隨任意節(jié)點(diǎn)j優(yōu)先度增加而增加；為反映不同節(jié)點(diǎn)獲得帶寬的滿足程度，設(shè)定效用函數(shù)隨節(jié)點(diǎn)j下載能力增大而降低；為了降低端到端延遲，鏈路延遲越低，越大，設(shè)定分別為節(jié)點(diǎn)j優(yōu)先度和鏈路延遲，得到一個(gè)效用函數(shù)表達(dá)式：
除源節(jié)點(diǎn)以外所有節(jié)點(diǎn)均為接收節(jié)點(diǎn)，接收節(jié)點(diǎn)構(gòu)建自適應(yīng)的層次傳輸網(wǎng)絡(luò)編碼數(shù)據(jù)。構(gòu)造如下最大化所有節(jié)點(diǎn)效用的線性規(guī)劃問題：
P：任何凸規(guī)劃P的最優(yōu)解給出了一個(gè)組播會(huì)話中最優(yōu)的帶寬分配策略。通過最大化上述效用函數(shù)，凸優(yōu)化P保證高優(yōu)先度的節(jié)點(diǎn)獲得較高的帶寬，同時(shí)，通過對(duì)數(shù)函數(shù)（嚴(yán)格的凹函數(shù)）保證了不同節(jié)點(diǎn)帶寬分配的公平性[12]。
6.2 梯度下降方法
首先將原問題P的（2）式變?yōu)榈葍r(jià)的最小化問題：，然后將Lagrangian因子與原問題P約束（3）關(guān)聯(lián)，得到目標(biāo)函數(shù)式（4）：
現(xiàn)在得到原問題P的Lagrangian對(duì)偶問題：
C約束條件如下：
上述公式（6）中的Lagrangian子問題可以被分解為多個(gè)凸規(guī)劃的子問題，每個(gè)子問題可以被節(jié)點(diǎn)獨(dú)立的解決，即：
基于上述子問題的分解，可以分布式的解決原問題P的Lagrangian對(duì)偶問題。
梯度下降過程：首先設(shè)置初始化的非負(fù)Lagrangian因子，然后在梯度下降過程的第k（k=1，2，…）次迭代時(shí)，給定當(dāng)前的Lagrangian因子，基于water filling方法解決上述公式（7）的N個(gè)子問題以獲得當(dāng)前的，然后更新Lagrangian因子為
（9）
其中，“+”代表將映射到非負(fù)的實(shí)數(shù)，為單步增加長(zhǎng)度的序列。
7 實(shí)驗(yàn)測(cè)試與分析（The experiment and analysis）
設(shè)定每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子女節(jié)點(diǎn)數(shù)目分別均勻隨機(jī)的從6—12選擇，每個(gè)節(jié)點(diǎn)利用Butterfly連接無偏抽樣新的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)定期（設(shè)定10s）無偏抽樣同層一個(gè)節(jié)點(diǎn)交換滑動(dòng)窗口，每個(gè)節(jié)點(diǎn)下載和上傳能力分別均勻隨機(jī)的在0.5—4.5Mbps和0.5—1.5Mbps確定，覆蓋網(wǎng)鏈路延遲為1—100ms均勻隨機(jī)數(shù)。設(shè)定每層最大容量比例MAX為0.5以保證每個(gè)節(jié)點(diǎn)具有至少兩個(gè)父節(jié)點(diǎn)，下列結(jié)果均為10次平均值。
7.1 拓?fù)浣Y(jié)構(gòu)構(gòu)造和維護(hù)
在不同平均在線節(jié)點(diǎn)數(shù)目（1000—9000）下，測(cè)試CORE加入過程的分層能力，考察不同層次的節(jié)點(diǎn)分布以及拓?fù)浣Y(jié)構(gòu)維護(hù)開銷等性能指標(biāo)，結(jié)果如圖4（a）和圖4（b）所示。圖4（a）顯示各個(gè)層次的平均節(jié)點(diǎn)數(shù)目隨層次數(shù)目的提高近似以指數(shù)形式增加，有效地降低了系統(tǒng)中層次數(shù)目；圖4（b）顯示在不同平均在線節(jié)點(diǎn)數(shù)目下拓?fù)浣Y(jié)構(gòu)維護(hù)消息帶寬開銷較小，平
均<10kbps，而且隨著節(jié)點(diǎn)數(shù)目增大維護(hù)消息開銷保持相對(duì)穩(wěn)定。從圖4（a）和圖4（b）可知CORE能夠有效分層，且拓?fù)浣Y(jié)構(gòu)維護(hù)開銷較低。
7.2 滑動(dòng)窗口路由性能
在不同平均在線節(jié)點(diǎn)數(shù)目下，測(cè)試滑動(dòng)窗口路由機(jī)制的性能。統(tǒng)計(jì)600秒時(shí)間間隔系統(tǒng)范圍滑動(dòng)窗口的性能?？疾觳檎衣酚陕窂介L(zhǎng)度和準(zhǔn)確獲得當(dāng)前層容量范圍的查找比例（稱為命中率）等兩個(gè)指標(biāo)。將所有層次性能指標(biāo)平均，結(jié)果如圖5（a）和圖5（b）所示。圖5（a）顯示滑動(dòng)窗口路由機(jī)制能夠迅速收斂到全局的容量范圍，這是由于滑動(dòng)窗口基于gossip方式擴(kuò)散當(dāng)前層次容量范圍；圖5（b）顯示當(dāng)前滑動(dòng)窗口確定的對(duì)應(yīng)節(jié)點(diǎn)以極高概率（>99.9%）為當(dāng)前層容量范圍上、下限對(duì)應(yīng)節(jié)點(diǎn)，說明滑動(dòng)窗口路由機(jī)制能夠在網(wǎng)絡(luò)波動(dòng)下精確的獲取本層的容量范圍。從圖5（a）和圖5（b）可知滑動(dòng)窗口路由機(jī)制能夠高效的確定當(dāng)前層范圍。
7.3 速率控制收斂性
檢驗(yàn)動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下速率控制方法的收斂速度。設(shè)定收斂閾值=0.001。結(jié)果如圖6（a）和圖6（b）所示。圖6（a）顯示速率控制方法在不同平均節(jié)點(diǎn)數(shù)目下速率控制方法能夠以較低迭代次數(shù)收斂，平均的迭代次數(shù)<40；且平均迭代次數(shù)隨節(jié)點(diǎn)數(shù)目增加變化較小，這是由于速率控制方法為基于局部?jī)?yōu)化達(dá)到全局的收斂，每個(gè)父節(jié)點(diǎn)均僅與子女節(jié)點(diǎn)交換更新消息。圖6（b）顯示系統(tǒng)所有父節(jié)點(diǎn)平均的額外迭代開銷較小，平均迭代輪數(shù)<20，而且在不同時(shí)間額外迭代次數(shù)變化幅度較低，這是由于父節(jié)點(diǎn)執(zhí)行額外的速率控制迭代過程時(shí)均基于當(dāng)前子女節(jié)點(diǎn)的價(jià)格幅度，降低了價(jià)格幅度因初始化過程帶來的額外迭代過程。
統(tǒng)計(jì)平均在線節(jié)點(diǎn)數(shù)目5000時(shí)，不同層次的吞吐率以及端到端延遲，此時(shí)節(jié)點(diǎn)分為九層，從第二層開始統(tǒng)計(jì)（第一層為源節(jié)點(diǎn)）。在基于直方圖的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方式和基于能力分層下，采用速率控制和沒有速率控制的方法下的性能，結(jié)果如圖7（a）和圖7（b）所示。
圖7（a）顯示基于能力分層下平均吞吐率隨層次數(shù)增加首先近似指數(shù)降低，然后接近平穩(wěn)狀態(tài)。這是由于采用能力感知的分層方式，高上傳帶寬的節(jié)點(diǎn)位于上層，因此下層節(jié)點(diǎn)可以獲得更多的下載帶寬。圖7（b）顯示端到端延遲隨著層次數(shù)目增大而上升，然而基于能力分層和速率控制下端到端延遲隨著層次數(shù)增大上升幅度遠(yuǎn)小于其余方式，且在層次數(shù)>5后的端到端延遲接近平穩(wěn)狀態(tài)，這是由于速率控制機(jī)制同時(shí)考慮節(jié)點(diǎn)間的延遲，增加低延遲節(jié)點(diǎn)的下載帶寬，在全局范圍提升高優(yōu)先度節(jié)點(diǎn)獲取數(shù)據(jù)的平均速率。從圖7（a）和圖7（b）可知CORE通過速率控制機(jī)制實(shí)現(xiàn)了按照能力區(qū)分方式提供帶寬，同時(shí)有效提高了系統(tǒng)范圍的吞吐率。
8 結(jié)論（Conclusion）
針對(duì)異構(gòu)節(jié)點(diǎn)環(huán)境下實(shí)現(xiàn)基于覆蓋網(wǎng)的快速數(shù)據(jù)分發(fā)問題，提出了基于能力區(qū)分的拓?fù)錁?gòu)建和速率控制的網(wǎng)絡(luò)編碼組播協(xié)議CORE。CORE協(xié)議通過充分利用異構(gòu)節(jié)點(diǎn)能力并提供區(qū)分的服務(wù)質(zhì)量鼓勵(lì)節(jié)點(diǎn)提供高的上傳能力，同時(shí)提高全局范圍的吞吐率，降低節(jié)點(diǎn)獲取數(shù)據(jù)的延遲。模擬測(cè)試顯示CORE協(xié)議具有高度的擴(kuò)展性，較高的吞吐率和低端到端延遲，以及較低計(jì)算開銷等優(yōu)點(diǎn)。
參考文獻(xiàn)（References）
[1] Zheng Z，Wang Y，Ma X.PeerChatter：A Peer-to-Peer Architecture for Data Distribution over Social Networks[J].Information-An International Interdisciplinary Journal，2011，15（1）：259-266.
[2] E.Adar，B.Huberman.Free riding on Gnutella[J].FirstMonday，2010，5（10）：33-38.
[3] Richard T.B.Ma，Sam C.M.Lee，John C.S.Lui.Incentive and Service Differentiation in P2P Networks：A Game Theoretic Approach[J].IEEE/ACM Transactions on Networking，2012，14（5）：978-991.
[4] Chuan Wu，Baochun Li.Diverse：Application-Layer Service Differentiation in Peer-to-Peer Communications[J].IEEE Journal on Selected Areas in Communications，
2011，25（1）：222-234.
[5] F.Clevenot，P.Nain，K.W.Ross.Multiclass P2P Networks：Static Resource Allocation for Bandwidth for Service Differentiation and Bandwidth Diversity[C].In Proceedings of the Performance，2009.
[6] Zongpeng Li，Baochun Li，Lap Chi Lau.On Achieving Maximum
Multicast Throughput in Undirected Networks[J].IEEE Transactions on Information Theory，2013，52（6）：2467-2485.
[7] Lijun Chen，Tracey Ho，Steven H.Low.Optimization Based Rate Control for Multicast with Network Coding[C].In INFOCOM，2011.
[8] Chuan Wu，Baochun Li.rStream：Resilient and Optimal Peer-to-Peer Streaming with Rateless Codes[C].In INFOCOM，2011.
[9] Zhan Zhang，Shigang Chen，Yibei Ling.Capacity-Aware Multicast Algorithms on Heterogeneous Overlay Networks[J].IEEE Transactions on Parallel and Distributed Systems，2009，17（2）：135-147.
[10] Rahimian F，et al.Vitis：A Gossip-based Hybrid Overlay for Internet-scale Publish/Subscribe Enabling Rendezvous Routing in Unstructured Overlay Networks[C].In IEEE International Parallel & Distributed Processing Symposium （IPDPS），2011：746-757.
[11] S.Shenker.Fundamental design issues for the future Internet[J].IEEE J.Sel. Areas Commun，1995，13（7）：1141-1149.
[12] K.Sripanidkulchai，A.Ganjam.The Feasibility of Supporting Large-Scale Live Streaming Applications with Dynamic Application End-Points[C].In Proceedings of the SIGCOMM，2009.
