基于網絡編碼的分層媒體多播中的層速率分配優化

林曉斌 許胤龍 詹 成 王青山

①(中國科學技術大學計算機科學與技術學院 合肥 230027)②(安徽省高性能計算重點實驗室 合肥 230027)③(合肥工業大學理學院 合肥 230009)

1 引言

隨著網絡技術的快速發展，視頻會議、遠程教學、交互視頻游戲等眾多流媒體應用受到廣泛的關注。由于網絡的異構性，同一個多播會晤中各接收節點可能具有不同的接收帶寬。單速率多播中，所有接收節點以相同速率接收服務，不適合異構網絡。而多速率多播在同一個多播會晤中以不同的速率為不同接收節點提供服務，更適合大規模異構網絡的多媒體應用。

分層多播(累積分層多播)[1]是一種廣泛應用的多速率多播技術。在分層多播中，源節點將多媒體數據編碼成一個基礎層和若干增強層。基礎層包含最基本數據，能夠獨立解碼；而增強層k只有在基礎層，增強層1，增強層2，…，增強層k?1都收到時才能解碼。接收節點收到的分層數量越多服務質量越好。各接收節點可以根據各自的帶寬接收相應層數的分層數據。

在傳統的網絡通信中，中間節點收到數據后對數據不進行任何處理，只實現存儲轉發。而利用網絡編碼(network coding)[2]，中間節點對收到的數據進行編碼處理后再轉發，接收節點收到足夠的編碼數據后，通過解碼操作即可得到所有參與編碼的原始數據。通過網絡編碼，中間節點可以增加每次傳輸的有效信息量，從而提高網絡吞吐量。Ahlswede等人[2]、Koetter等人[3]證明了利用網絡編碼多播組可以達到的最大多播速率等于源節點到各接收節點的最大流的最小值。Li等人[4]證明了利用線性網絡編碼多播組就可以達到最大多播速率。Sanders等人[5]則提出了構造線性編碼的多項式時間算法來保證多播組能達到最大多播速率。

近年來，基于網絡編碼的多速率媒體多播引起了一些專家學者的關注。文獻[6-9]研究了多速率多播的問題，但沒有考慮分層之間的優先級，不符合分層多播中高層數據依賴低層數據解碼的特性。在每層速率已知的前提下，Zhao等人[10]、Xu等人[11]、Wu等人[12]分別研究了基于網絡編碼的分層多播。由于這些工作都假定各層速率是預先固定的，不能根據網絡拓撲動態分配各層速率，從而不能充分利用網絡帶寬。在層速率可變的假定下，Zhang等人[13]研究了基于網絡編碼的層速率分配問題。由于該問題是一個非線性整數規劃的問題，他們提出了確定層速率的近似算法ApproxIVM。但該算法根據少數最大流較小的接收節點的最大流來確定層速率，會導致多數最大流較大的接收節點不能充分利用帶寬；且每一分層速率確定后，文中沒有給出算法用于分配每層數據所需的鏈路帶寬，從而不能充利用網絡帶寬。

針對每層速率可變的分層多播問題，本文研究了基于網絡編碼的層速率優化分配算法。該算法首先將網絡圖按接收節點的總數分解成子圖，然后將這些子圖按分層層數進行合并，在合并后的各子圖中接收節點的最大流的最小值即是優化分配的各層速率大小。相比低帶寬接收節點優先的層速率分配算法ApproxIVM[13]，本文的算法居于全局優化，能夠滿足不同接收節點的帶寬需求。模擬實驗表明本文算法能夠顯著提高網絡吞吐量，提高網絡帶寬的利用率。

2 問題模型

本節對基于網絡編碼的分層媒體多播中的層速率分配優化問題進行簡要的形式化描述。表1給出幾個重要的變量。

將網絡用有向圖G(V, E, s, T)表示，其中V是節點集，E是邊集，s是源節點，T是所有n個接收節點的集合，即T={t1, t2,…,tn}?V 。邊(u, v)表示節點u和節點v之間的鏈路，c(u, v)表示鏈路(u, v)的容量。假定s上的視頻數據經編碼器分層編碼后形成m(m≤n)個具有順序關系的層：第1層(基礎層)，第2層(增強層1)，…，第m層(增強層m?1)。為保證各接收節點能夠正確地解碼接收的網絡編碼數據包，本文限定對分層編碼的視頻文件進行網絡編碼時只是在同一分層的數據包之間進行。因為如果允許不同分層的數據包之間進行網絡編碼，可能造成低帶寬的接收節點由于只能接收部分的網絡編碼包，從而不能正確解碼。

表1 模型的部分變量

由文獻[11,13]，基于網絡編碼的分層媒體多播中的層速率優化分配問題可模型化為以下數學規劃：

數學規劃的目標是最大化各接收節點的接收速率總和，即網絡吞吐量。約束條件(1)和條件(2)是分層媒體數據的解碼條件，即第k層在第1層到第k?1層都接收的前提下才能解碼。約束條件(3)是從源節點s到每一特定接收節點ti(?ti∈T)的第k(?k=1,2,…,m)層的數據流的平衡條件。約束條件(4)是基于網絡編碼的帶寬使用特性：同一層數據流之間不競爭鏈路帶寬。約束條件(5)保證每條鏈路的帶寬使用在其容量限制之內。

3 啟發式算法

在分層媒體多播中，網絡各鏈路為每層數據分配鏈路帶寬。根據各鏈路為m層數據分配的鏈路帶寬，網絡圖G (V, E, s, T)被分解成m個子圖Gk(Vk, Ek,s, Tk)(1≤k≤m)。Gk(Vk, Ek, s, Tk)是第k層數據在網絡G (V, E, s, T)中的傳輸圖，其中Ek={(u, v)|fk(u, v)＞0,(u, v)∈E}，V為與E中的邊關聯的節點集合, Tk是接收第k層的接收節點集合。在層速率固定(即在問題模型的數學規劃中，bk是已知常量，此時數學規劃為整數線性規劃)的情形下，文獻[13]證明了數學規劃的可行解對應于將網絡圖分解的各子圖中的各參數，文獻[10,11]設計了相應的算法根據給定的各層速率將網絡圖分解成子圖。而在層速率可變(即在問題模型的數學規劃中，bk是需優化的變量，此時數學規劃為非線性整數規劃)的情形下，本文通過證明定理1從而求解各層的優化速率并得到各層相應的傳輸子圖。

定理1 在圖G(V, E, s, T)按最大化吞吐量最優分解的m個子圖Gk(Vk, Ek, s, Tk)(1≤k≤m)中，從s到Tk的各接收節點最大流的最小值minmaxflow(Gk)是第k層的最優層速率。

證明 不妨設在傳輸子圖Gk(Vk, Ek, s, Tk)中從s到ti(ti∈Tk)的最大流maxflow(ti)=min-maxflow(Gk)。若min-maxflow(Gk)＜，則ti不能收到第k層，即ti?Tk，矛盾。若min-maxflow(Gk)＞，利用算法LIF[5]設定網絡編碼系數，對在子圖Gk(Vk,Ek, s, Tk)中傳輸的數據包進行網絡編碼，能夠保證Tk中的所有接收節點都以min-maxflow(Gk)接收數據，與題設是第k層的最優層速率矛盾。因此，min-maxflow(G)=。 證畢

由定理1，優化分配m層的層速率即是將網絡圖優化分解成m個傳輸子圖，每個傳輸子圖中從源到各接收節點的最大流的最小值即是優化的層速率。由于直接將網絡圖分解成m(m≤n)個子圖較困難，本文先設計算法NRAA(N-layer Rate Allocation Algorithm)將網絡圖按接收節點的個數n分解成n個傳輸子圖Hl(Vl, El, s, Tl)(1≤l≤n)，其中E={(u, v)|yl(u, v)＞0,(u, v)∈E}且yl(u, v)表示n層機制下鏈路(u, v)為第l層分配的帶寬，Vl是與El中的邊相關聯的節點集合，Tl是接收n層機制下第l層的接收節點集合；然后設計算法MRAA(M-layer Rate Allocation Algorithm)將n個子圖Hl(Vl, El, s, Tl)(1≤l≤n)合并成m個子圖Gk(Vk,Ek, s, Tk)(1≤k≤m)，在合并而成的各子圖中接收節點最大流的最小值即是優化分配的m層機制下的各層速率。

3.1 算法NRAA

將圖G (V, E, s, T)分解成n個子圖，則每個接收節點都能按照各自的接收帶寬接收分層數據。假定圖Rl(Vl, El, s, Tl)是網絡圖G (V, E, s, T)為n層機制下的第1層到第l?1(2≤l≤n)層分配鏈路帶寬后的殘余圖。由定理1，我們可根據圖Rl(Vl, El, s, Tl)中從s到Tl的各接收節點的最大流來確定n層機制下第l層速率，并設計如下算法NRAA：如果所有接收節點的最大流都大于0，則以最大流的最小值為第l層速率，各鏈路為第l層優化分配鏈路帶寬以構造傳輸子圖Hl(Vl, El, s, Tl)(1≤l≤n)。否則如果最大流等于0的接收節點個數δ≥1，則刪除當前最大流為0的全部接收節點并確定第l層到第l+δ?1層的速率為0，即本文允許空層的存在。重復上述操作，直至n層機制下各層速率和各層傳輸子圖都得以確定。在算法NRAA構造的各層傳輸子圖Hl(Vl,El, s, Tl)(1≤l≤n)中利用算法LIF[5]作為網絡編碼方案，能夠保證Tl中的所有接收節點都能以圖Hl(Vl, El, s, Tl)中從s到Tl的各接收節點的最大流的最小值作為接收速率接收n層機制下的第l層數據。

算法NRAA與算法ApproxIVM[13]有些相似，但不同的是：算法ApproxIVM是通過m(m≤n)次迭代地取殘余圖中的非零最大流的最小值來確定m層機制下的各層速率；且對于層速率優化的關鍵部分(即層速率確定后如何優化分配為滿足該層速率所需的鏈路帶寬)，算法ApproxIVM沒有給出相應的鏈路帶寬分配策略，從而直接影響下一層速率的大小，本文則在算法NRAA中提出如下啟發式算法NALBA(New Algorithm for Link Bandwidth Allocation)為第l(1≤l≤n)層數據優化分配鏈路帶寬，進而從殘余圖Rl(Vl, El, s, Tl)中優化分解出n層機制下第l層傳輸子圖Hl(Vl, El, s, Tl)。

因為本文以圖Rl(Vl, El, s, Tl)中從s到Tl的各接收節點的最大流的最小值為第l層速率，所以圖Rl(Vl, El, s, Tl)中最大流最小的接收節點的路徑帶寬全部分配給第l層數據。因此，在非最小最大流的接收節點的各路徑上為第l層數據分配帶寬時，應讓它們充分利用最大流最小的接收節點路徑上為第l層數據必需分配的帶寬。根據此思想，算法NALBA詳細過程如下：

在圖Rl(Vl, El, s, Tl)中，根據算法Edmonds-Karp[14]計算從s到ti(ti∈Tl)的最大流maxflow(ti)，并找出最大流經過的路徑集合Pi。假設maxflow(ti)經過路徑的流量是，經過鏈路(u, v)的流量是Fi(u, v)。令表示Tl中最大流最小的接收節點集合。確定Tl中接收節點的最大流的最小值min為第l層速率。要使中的所有接收節點都能接收第l層數據，則在鏈路(u, v)上需分配的帶寬f'(u, v)=max{Fi(u, v)|ti∈}。對最大流大于min的每個接收節點ti(ti∈Tl?)，都分別執行如下各步驟為第l層分配鏈路帶寬(表2)。

表2 第l層分配鏈路帶寬

表2中第(3)步對均勻分攤網絡帶寬到各路徑的處理方法，可參見文獻[10]的Heuristic Approach。在算法NALBA中，路徑為從s到ti(ti∈)的第l層數據分配的帶寬=，路徑為從s到ti(ti∈Tl?)的第l層數據分配的帶寬=preFlo+evenFlo。n層機制下鏈路(u, v)上為通往ti(ti∈Tl) 的第l層數據分配的帶寬：

因此，n層機制下鏈路(u, v)為第l(1≤l≤n)層數據分配的總帶寬為

證明 算法NALBA對所有接收節點執行相同操作，所以我們以單個接收節點ti(ti∈Tl)為例進行分析。不妨設ti為非最小最大流的接收節點。首先執行算法Edmonds-Karp[14]計算maxflow(ti)并找出ti的路徑集Pi，時間復雜度為O(| Vl||El|2)。其次，算法NALBA為第l層分配鏈路帶寬各步驟的時間復雜度為O(|El|)。綜上，對單個接收節點ti所需執行操作的時間復雜度為O(| Vl||El|2)+O(|El|)=O(| Vl||El|2)。共有|Tl|個接收節點，因此算法NALBA的時間復雜度為O(| Tl||Vl||El|2)。 證畢

基于算法NALBA分配n層機制下各層傳輸子圖的鏈路帶寬，本文設計算法NRAA如表3所示：

表3 本文設計算法NRAA

在算法NRAA構造的圖Hl(Vl, El, s, Tl)(1≤l≤n)中利用算法LIF[5]作為網絡編碼方案，能夠保證Tl中的所有接收節點都接收到n層機制下的第l層數據。

由算法NRAA優化分配n層機制下的層速率列表A=＜a1, a2,…,an＞，并得到n層機制下各接收節點的接收速率列表C=＜c1, c2,…,cn＞，則根據算法NRAA的設計思想顯然易證以下性質。

性質1 若由算法NRAA得到的各接收節點的接收速率c1, c2,…,cn滿足c1≤c2≤…≤cn，則ci(1≤i≤n)與n層機制下各層速率a1, a2,…,an之間的關系滿足ci=a1+a2+…+ai。

定理3 在網絡G (V, E, s, T)中，n(|T|=n)層機制下的層速率優化分配算法NRAA的時間復雜度為O(| V||T|2|E|2)。

證明 算法NRAA的時間復雜度是由n次調用算法NALBA決定的。而由定理2，在網絡G (V, E,s, T)的殘余子圖Rl(Vl, El, s, Tl)中，算法NALBA的時間復雜度為O(| Tl||Vl||El|2)，其中Vl?V, El?E, Tl?T。所以算法NRAA的時間復雜度為n*O(| T||V||E|2)=O(| V||T|2|E |2)。 證畢

3.2 算法MRAA

為優化分配m(m≤n)層的層速率，本文將由算法NRAA預先分成的n層視頻數據合并成m層。假定由算法NRAA優化分配的n層機制下層速率列表A=＜a1, a2,…,an＞，接收節點接收速率的有序列表C=＜c1, c2,…,cn＞(其中c1≤c2≤…≤cn)。在最大化網絡吞吐量的目標下，將n層合并成m層的過程等價于在最大化的目標下，將有序列表C劃分成m個子列表C1, C2,…,Cm。其中|Ck|表示子列表Ck的元素個數，min(Ck)表示子列表Ck中的最小值。上述劃分即是將n個接收節點劃分成m個接收組Q1, Q2,…,Qm，在接收組Qk中有|Ck|個接收節點且組中的所有接收節點都能以速率min(Ck)接收在m層機制下從第1層到第k層的共計k層的分層數據。因此可優化分配m層機制下各層速率為

對于有序列表劃分成子列表的問題，Gau等人[15]證明了有序列表的最優劃分一定是有序劃分，并提出了把元素個數為n的有序列表劃分成m個有序子列表的多項式時間算法FALP(Fast Algorithm for List Partition)。

不妨設有序列表C=＜c1, c2,…,cn＞(其中c1≤c2≤…≤cn)，經算法FALP劃分成有序子列表(每個子列表的元素從小到大排序)為：C1=＜c1, c2,…,ci1?1＞(注：i0=1),C2=＜ci1,ci1+1,…,ci2?1＞,…,Cm=＜cim?1,cim?1+1,…cn＞，則接收節點集合T={t1, t2,…,tn}被分成的m個接收分組：

因此，m層機制下，Tk=Qi。在組Qk(1≤k≤m)中的接收節點的接收速率都為cik?1，又根據式(3)，優化分配m層機制下各層速率為

而由算法NRAA的性質1：ci=a1+a2+…+ai(1≤i≤n)，因此優化分配m層機制下第k(1≤k≤m)層速率為

即m層機制下的第k(1≤k≤m)層數據是由n層機制下的第ik?2+1層到第ik?1層共ik?1?ik?2層數據合并而成的。因此m層機制下第k(1≤k≤m)層的傳輸子圖Gk(Vk, Ek, s, Tk)的鏈路帶寬fk(u, v)與n層機制下的各傳輸子圖Hl(Vl, El, s, Tl)(1≤l≤n)的鏈路帶寬yl(u, v)滿足以下等式：

綜上，本文設計算法MRAA將算法NRAA構造的n層機制下的n個傳輸子圖合并成m個傳輸子圖，優化分配m層機制下的各層速率。算法MRAA如表4所示。

表4 本文設計算法MRAA

在算法MRAA構造的第k(1≤k≤m)層傳輸子圖Gk(Vk, Ek, s, Tk)中，利用算法LIF[5]作為網絡編碼方案，能夠保證Tk中的所有接收節點都能以式(6)所示的速率接收m層機制下的第k層數據。

定理4 在網絡G (V, E, s, T)中，m(m≤n=|T|)層機制下的層速率分配算法MRAA的時間復雜度為O(| V||T|2|E|2)。

證明 算法MRAA由3步組成。第1步，調用算法NRAA，時間復雜度為O(| V||T|2|E|2)；第2步，按接收速率排序結果對接收節點重新編號，時間復雜度為O(n2)=O(| T|2)；第3步，調用算法FALP，時間復雜度為O(mn2)=O(m| T |2)。所以總時間復雜度為O(| V||T|2|E|2)+O(| T|2)+O(m| T|2)=O(| V||T|2|E |2)。 證畢

4 模擬實驗

本文通過C++模擬實驗進行算法性能評價。首先比較為各層視頻數據分配鏈路帶寬的新算法NALBA、隨機分配策略RANDOM、算法Heuristic Approach[10]的均勻分配策略；然后比較層速率全局優化分配算法MRAA、低帶寬接收節點優先的層速率分配算法ApproxIVM[13]、層速率固定的算法Heuristic Approach[10]。

文獻[16]表明為滿足網絡的異構性并保持合理的額外開銷，在分層多播中分層層數為4層是較為合理的值。因此本文在實驗中取分層層數m=4。

在應用網絡編碼的前提下，從源節點到某特定接收節點的最大流的值反映該接收節點的可接收帶寬的大小。在實驗中本文先采用平均標準化接收速率ANR(Average Normalized Rate)[6]如式(8)所示(其中ri表示ti接收到的各分層數據的總速率，maxflow(ti)表示從s到ti的最大流，T是所有接收節點的集合。)對各算法進行比較。參數ANR反映網絡中各接收節點對各自可接收帶寬的平均利用率。參數ANR越大，表明各接收節點的實際接收帶寬越趨近各自的可接收帶寬。但是本文的優化目標是吞吐量，因此本節定義標準化的總接收速率NTR(Normalized Total Rate)如式(9)所示(式(9)中各變量與式(8)含義一致。)來表示整個網絡的實際接收帶寬總和占可接收帶寬總和的比例，反映整個網絡的帶寬使用總量，即網絡吞吐量。

4.1 參數ANR比較實驗

圖1采用50個節點和10個接收節點的隨機網絡拓撲。在算法MRAA的步驟1，即執行算法NRAA時，分別執行隨機分配路徑帶寬的RANDOM策略，算法Heuristic Approach的均勻分配策略和算法NALBA 3種不同的方案為每層數據分配鏈路帶寬，得到算法MRAA的3個不同結果。圖1中RANDOM策略最差。因為RANDOM策略在各路徑上為每層數據隨機分配帶寬，沒有考慮帶寬的有效分配。在圖1中，當網絡的節點平均度從5增加到8時，算法NALBA相比算法Heuristic Approach的均勻分配策略對ANR參數的改進在圖1(a)中由3%增加到7%，在圖1(b)中由5%增加到10%。這是因為節點度越大，從源節點到不同接收節點的路徑之間有公共鏈路的可能性越大，所以算法NALBA在非最小最大流的接收節點的路徑上為各層分配帶寬時，讓那些與最大流最小的接收節點的路徑有公共鏈路的路徑共享最小最大流接收節點的路徑上為該層視頻數據必需分配的帶寬能夠節省更多的帶寬。

圖2采用100個節點，接收節點個數在[4,40]以步長為4變化，鏈路容量均勻分布在[1,20]的隨機網絡拓撲。圖2是算法MRAA，算法ApproxIVM，算法Heuristic Approach的比較結果。其中在層速率固定的算法Heuristic Approach中，本文假定從源節點到各接收節點的最大流的范圍已知為[Min,Max]，源節點根據此范圍固定第1層的速率為Min，其他層的速率相等且為(Max?Min)/(m?1)，m為分層層數。從圖2中可以看出，MRAA相比ApproxIVM和Heuristic Approach對ANR參數的改進在圖2(a)中平均分別為6%和20%，在圖2(b)中平均分別為10%和19%。因為MRAA根據網絡拓撲從全局的角度優化分配各層速率，并且采用算法NALBA為各層有效分配鏈路帶寬；ApproxIVM只根據網絡中最大流最小的4個接收節點的最大流來確定4層視頻數據的速率而且在各鏈路為每一層數據分配帶寬時采用隨機分配的方式，這些都使得網絡ANR參數受影響；而Heuristic Approach中各層速率固定，沒有根據網絡拓撲分配各層速率，因此其ANR參數最差。

4.2 參數NTR比較實驗

圖1 NALBA, RANDOM, Heuristic Approach算法的參數ANR比較

圖2 MRAA, ApproxIVM, Heuristic Approach算法的參數ANR比較

圖3 NALBA, RANDOM, Heuristic Approach的參數NTR比較

圖4 MRAA, ApproxIVM, Heuristic Approach的參數NTR比較

當以NTR為比較參數時，重復上述實驗得到實驗結果如圖3和圖4。圖3與圖1相似，而圖4與圖2相比有些變化。在圖4中，MRAA相比Heuristic Approach和ApproxIVM對網絡吞吐量的提高在圖4(a)中平均分別為16%和15%，在圖4(b)中平均分別為14%和18%。因為MRAA考慮全局最優，使得所有接收節點都能充分利用帶寬，所以各接收節點的平均帶寬利用率和網絡吞吐量都是三者中最優的。在圖4(a)和圖4(b)中，隨著接收節點個數的增加，層速率固定的算法Heuristic Approach的吞吐量反而大于層速率經部分優化分配的算法ApproxIVM。因為本文設定Heuristic Approach根據接收節點最大流的范圍固定各層速率；而ApproxIVM根據少數低帶寬接收節點的最大流分配各層速率，從而導致多數最大流較大的高帶寬接收節點只能以低速率接收分層數據，不能充分利用帶寬，從而影響網絡吞吐量，尤其是當接收節點較多時。

5 結束語

本文研究了基于網絡編碼的分層媒體多播中的層速率分配優化問題。證明了將網絡圖按分層層數最優分解成的各網絡子圖中的接收節點的最大流的最小值即是各層的最優層速率，并根據此思想提出了時間復雜度為O(| V||T|2|E|2)的啟發式算法MRAA優化分配各層速率。模擬實驗表明本文的算法能夠顯著改善網絡吞吐量，提高各接收節點的平均帶寬利用率。本文的研究工作基于單會晤多播的情形，而在多會晤情形下基于網絡編碼的分層媒體多播中的層速率分配優化問題要復雜得多，我們將以此作為將來進一步的研究工作。

[1] McCanne S, Jacobson V, and Vetterli M. Receiver-driven layered multicast. Proc. of ACM SIGCOMM 1996, Stanford,CA, USA, Aug. 1996: 117-130.

[2] Ahlswede R, Cai N, and Li S R, et al.. Network information flow. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216.

[3] Koetter R and Medard M. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2000, 11(5):782-795.

[4] Li S R, Yueng R W, and Cai N. Linear network coding. IEEE Transactions on Information Theory, 2003, 49(2): 371-381.

[5] Sanders P, Egner S, and Tolhuizen L. Polynomial time algorithms for network information flow. Proc. of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), San Diego, CA, USA, June 2003:286-294.

[6] Sundaram N, Ramanathan P, and Banerjee S. Multirate media stream using network coding. Proc. of the 43rd Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, Sep. 2005.

[7] Wu X, Ma B, and Sarshar N. Rainbow network problems and multiple description coding. IEEE Transactions on Information Theory, 2008, 54(10): 4565-4574.

[8] Shao M, Wu X, and Sarshar N. Rainbow network flow with network coding. Proc. of NetCod 2008, Hong Kong, China,Jan. 2008: 1-6.

[9] Shao M, Dumitrescu S, and Wu X. Toward the optimal multirate multicast for lossy packet network. Proc. of ACM Multimedia 08, Vancouver, BC, Canada, Oct. 2008: 765-768.[10] Zhao J, Yang F, and Zhang Q, et al.. LION: Layered overlay multicast with network coding. IEEE Transactions on Multimedia, 2006, 8(5): 1021-1032.

[11] Xu C, Xu Y, and Zhan C, et al.. On network coding based multirate video streaming in directed network. Proc. of the 26th IPCCC, New Orleans, Louisiana, USA, Apr. 2007:332-339.

[12] Wu Y. Distributing layered content using network coding. 5th IEEE Annual Communications Society Conference on Sensor,Mesh and Ad hoc Communications and Networks Workshops,San Francisco, CA, USA, June 2008: 1-4.

[13] 張牧, 張順頤, 劉偉彥. 多速率多播最大吞吐量問題研究. 電子與信息學報, 2008, 30(1): 16-20.Zhang M, Zhang S, and Liu W. On the optimal multi-rate throughput for multicast. Journal of Electronics &Information Technology, 2008, 30(1): 16-20.

[14] Cormen T H, Leiserson C E, and Rivest R L, et al..Introduction To Algorithms (Second Edition). Massachusetts:MIT Press, 2001: 643-698.

[15] Gau R, Haas Z J, and Krishnamachari B. On multicast flow control for heterogeneous receivers. IEEE/ACM Transactions on Networking, 2002, 10(1): 86-101.

[16] Yang Y R, Kim M S, and Lam S S. Optimal partitioning of multicast receivers. Proc. of ICNP 2000, Osaka, Japan, Nov.2000: 129-140.