多重群播網路基於線性網路編碼之編碼複雜度研究

The Encoding Complexity of Linear Network Coding for Multicast

巫佳雯(Chia-Wen Wu)

指導教授 ： 石維寬

國立清華大學/電機資訊學院/資訊工程學系/碩士(2008年)

摘要

網路編碼（Network Coding）在通訊網路的領域中，成為一種嶄新的資訊散佈方式，這種資訊傳播方式可以明顯地增強通訊網路的效率與可靠度。關於網路編碼（Network Coding）在運作時所產生的複雜度，它表示為使用網路編碼時的計算總量，以及每一筆資訊流被成功傳送時所需要的網路資源。
在計算網路的編碼時的有限體元素個數，我們稱之為編碼（code）時所需求的符號個數（alphabet size）。而在有限體中做運算的成本和其元素個數成正比，這表示網路編碼的計算複雜度與符號個數（alphabet size）成正比。另外，在需要進行資訊流合併的編碼點（coding points）中，其所需的成本自然會高過於只有複製和轉送封包的節點，且可能會造成延遲的情形發生。
在本論文當中，主要探討在線性網路編碼（Linear Network Coding）的運作情況時，對於所需求的符號個數（alphabet size）以及編碼點（coding points）個數的上限值，以及如何最小化這兩者的個數，使得網路編碼在實際上運作時可以得到最佳的效能。除此之外，也針對符號個數（alphabet size），分別與最小切割（min-cut）、工作量（throughput）和設計複雜度做一個權衡性的比較。

關鍵字

線性網路編碼 ； 符號個數 ； 編碼點 ； 最小切割

並列摘要

無資料

並列關鍵字

Linear network coding ； alphabet size ； coding points ； min-cut

參考文獻

5. A. R. Lehman and E. Lehman, “Complexity classification of network

9. M. Kim, C. W. Ahn, M. M?dard, and M. Effros, “On minimizing network coding resources: An evolutionary approach,” Network Coding Workshop, 2006.

2. R. K?tter and M. M?dard, “Beyond routing: An algebraic approach to network coding,” IEEE/ACM Transaction on Networking, vol. 11, pp.782 – 796, October

4. C. Fragouli and E. Soljanin, “Information flow decomposition for network coding,” IEEE Transactions on Information Theory, vol. 52, pp. 829 – 848,

March 2006.