應用在資料串流環境之湧泉碼設計及其效能分析

Abstract

本論文的目的在於能有效率地使用網路頻寬來產生最大的吞吐量，並能夠減少封包遺失所造成網路服務的中斷時間。網路的環境中，由於頻寬和計算資源相當稀有，當網路壅塞發生時，傳統的TCP協定為了避免單一終端設備過度搶佔網路資源，因此會大幅降低終端設備發送封包的速率，以避免過度壅塞導致更多的封包遺失。但是在網路中壅塞並非是造成封包遺失的唯一原因(例如：Noisy Link)，因此TCP壅塞控制無法有效率地立即恢復最大的吞吐量。此外，當封包遺失率很高時，TCP的機制會等待很長的時間來感知封包遺失的事件並且再次重送遺失的封包，因此這個機制會出現大量的網路延遲。我們在目前串流(streaming)資料傳輸中較常使用的使用者資料段協定(User Datagram Protocol, UDP)加上了湧泉碼的設計。此設計，使得原本無可靠度的UDP協定也可以提供可靠且高速率網路傳輸。我們使用IETF (Internet Engineering Task Force )RFC 6330的規格書[1]上所提供的隨機矩陣產生器，此產生器能隨機產生蓋洛瓦體(Galois Field，GF ) GF(2^8)的元素。我們可藉由這些隨機產生的元素構成一個K×N的隨機產生矩陣並用此矩陣對原先封包的行矩陣進行IETF RFC 6330所定義的矩陣運算，因此可將K個封包擴展為N個封包(N>K)。假如這些封包有任何的遺失，接收端仍可以藉由收到封包的標頭中的種子數目來解出對應的隨機GF(2^8)元素，當收到K個封包就能建構出K×K的矩陣，再藉由高斯消去法來求出是否滿秩。透過這個機制，在一定的遺失率下，當封包遺失發生時接收端還是可以順利還原出原始K個封包而不用啟動重送機制。我們提出的湧泉碼，由於使用了GF(2^8)的元素，能使解碼失敗的機率較一般編碼使用GF(2)的元素較低。實驗的結果明確地顯示，我們提出的湧泉碼在UDP的資料串流中能有效地在高封包遺失率情況下產生較高的吞吐量。在NS2上目前沒有現成的湧泉碼模組，但在本論文中我們設計實作此協定並且與常用的通訊協定進行效能評估。這些設計及實現的結果，可作為未來欲實現湧泉碼於NS2的相關研究基石。

The goals of this thesis are to utilize the network resources optimally and allowed to send real-time data as fast as possible. Excessive network traffic causes network congestion and it leads to packets loss. Transmission Control Protocol (TCP) congestion control avoid this kind of packets loss. However, packets losses could be caused by either network congestion or channel transmission errors. If packet losses are caused by transmission errors, TCP will slow down its sending rate that unnecessarily leads to low throughput. On the other hand, the receiver needs to wait the retransmitted packet when the sent packet is lost. If many packets are lost, it will lead to obvious latency and cause a lot of retransmitted packets, which cannot sustain high throughput. To solve the existing protocol inefficiency problem, we design fountain codes suitable in UDP streaming environments. In our research methods, the blocks of packets can transform them into the algebraic equations. Even if the packets within the block are lost, the receiver can synchronize by the seed number to reconstruct the random number generator matrix, and according to the gauss elimination to decode. The proposed LT encoding uses a characteristic 2 finite field with 256 elements, which can also be called the Galois field GF(2^8). These elements are derived from IETF (Internet Engineering Task Force) RFC 6330. We can use these elements to construct K×N random number matrix. Thus, we can extend K source packets to the N (N>K) encoding packets. If the receiver received the K packets, we could try to recover the K source packets. In the experimental results which indicate that the proposed fountain code in UDP streaming is very helpful in reducing inefficiency in the case of high packet loss rate. The demonstration is designed and implemented by the Network Simulator – NS2. Our results may serve as a basis to facilitate the related future fountain code research.