冗餘複播圖上之分散式網路編碼

Abstract

對於多重傳播來說，其傳輸速率上限往往被max-flow bound給限制住。為了改善傳統單一訊源多重傳播的傳輸速率，在每個網路節點增加一個網路編碼的新功能。藉由網路編碼的功能，這個傳輸速率的上限就可以達得到。更進一步地，使用線性網路編碼就足以讓單一訊源多重傳播速率能夠達到其上限速率，並且，網路碼往往可以在一個有限的場找到。 在覆蓋式網路上，虛擬網路拓撲可以經由不同的使用目的建構出來，而且每個虛擬網路節點可以具備更高階的處理能力。借重網路編碼和覆蓋式網路的優點，可以建造出2階冗餘複播圖以提供單一訊源多重傳輸。在2階冗餘複播圖上，網路碼的建構可以不需要網路拓撲的資訊。基於這個特別的多重傳播圖形，我們推導出在一個2的延伸場上最大能用量的編碼向量數目，並且提出產生編碼向量的演算法。相較於Zhu她們所提的方法，此演算法更加的容易，並且，用於多重傳輸的網路碼會需一更少的處理時間。由於在現實世界中，資訊的儲存與傳送都是二位元形式，如果網路碼是從質數場上建構出的，則將會損失一些資訊。我們所提出的方法，是建構在GF(2^m)的場上，所以不會有資訊流失。在2階冗餘複播圖上，從GF(2^m)建構出的網路碼終將增加端點到端點間的流量，是個合理的推測。

Multicast transmission over a network is upper bounded by the network capacity (rate) called the \emph{max-flow bound}. In order to improve the capacity of a conventional single source multicast, a new function called network coding is introduced to network nodes. It has been shown that, by means of network coding, the capacity is always achievable. Moreover, linear network codes are sufficient to attain the capacity for all single source multicast transmissions and they cam always can be found over finite fields.

In an overlay network, virtual network topology over an existing physical network is constructed to meet some special networking requirements. For the purpose of implementing network coding, all virtual network nodes must be capable of handling higher level operations. Taking the advantages of network coding and overlay networks, a two-redundant multicast graph is constructed so that network codes over the resulting overlay network can be designed without the knowledge of the network topology. Based on this special multicast graph, we derive the maximum available encoding vectors over an extension filed of GF(2) and propose an encoding vector generation algorithm. The algorithm is simpler and the resulting multicast network codec renders lower complexity. It is believed that network codes over GF(2^m) for redundant multicast graph can also enhance the end-to-end throughput.