Abstract
對現今的網路應用程式，群播是一個相當重要的功能。其中某些應用程式會特別強調群播資料的正確性，為確保資料能夠完整地由發送端傳到接收端，通常接收端會傳送回饋給發送端，來告知資料是否已經正確地到達接收端。但若有許多回饋同時從接收端流向發送端，網路會因而產生壅塞的情況。在這篇論文中，我們提出一個精簡回饋的方法，這個方法可以很有效地減少網路上回饋的數目，以避免網路壅塞的發生。 基本上，精簡回饋的方法可以分成兩類︰結構型與時間型。在結構型精簡回饋的方法中，所有的接收端都有一個指定的代傳接收端。當這個代傳接收端收到來自某些接收端的回饋時，會代替他們傳回饋給發送端，待收到重傳封包時，在一一傳給那些曾送回饋的接收端。而在時間型精簡回饋的方法中，所有接收端都是以群播的方式來傳送回饋，並且在傳送回饋之前，先延遲一段時間，若在這期間某接收端收到其他接收端傳來的回饋時，自己就不送回饋。如此，發送端收到的回饋就會減少。比較這兩種方法的優劣，我們發現時間型精簡回饋的方法比較容易實作，而結構型精簡回饋的方法則有較好的回饋精簡效率。因此為求較佳的效率，我們採用結構型精簡回饋的方法。 網際網路上的群播有以下的特性。由於群播群組的成員可以隨時加入或離開群組，因此發送端是在不知道群組成員的情形下進行群播。為使我們可以在網際網路上進行群播，我們必須採用一個動態的精簡回饋方法。 在群播進行之初，發送端不知道群組成員為何。而未收到正確資料的接收端，會將其回饋直接送給發送端，發送端則由收到的回饋當中得知各個接收端的位址，依據這些資訊，發送端可以逐漸地建造出一個完整的精簡回饋樹，各個接收端依據精簡回饋樹的結構，會將未來的回饋傳給一個指定的代傳接收端。隨著接收端的加入或離開群組，發送端可以動態地調整精簡回饋樹，以配合最新的網路狀況。 結構型精簡回饋方法的效能，主要是依賴精簡回饋樹的形狀，另一方面，為使發送端不必耗費太多的時間在精簡回饋樹的建造上，我們提出了一個簡單的建樹方式。我們將建樹的過程分成兩個時期：一個是建造期，另一個是維護期。在建造期，每當發送端得知一個新的接收端位址時，就會重新建一個完整的精簡回饋樹。而在維護期，每當發送端得知一個新的接收端位址時，只會將此接收端用一個最短路徑與原來的精簡回饋樹相連。這樣的方式考慮到了精簡回饋樹的效能與計算複雜度之間的取捨，避免發送端耗費太多的時間在精簡回饋樹的建造上。 針對先前提出精簡回饋的方法，提出一些可供擴充的功能，以適應更為複雜的網路環境。 首先，為使我們提出的方法，也能運用在可移動的接收端上，我們依據現行網際網路的標準，驗證所提精簡回饋方法的適用性。另一方面，針對一些效率不佳的情況提出改進的方案。例如，由於行動中的接收端傳給發送端的位址，通常不是其真正所在的位址，這樣的情形使得發送端建造的精簡回饋樹不能為移動的接收端設定一個較佳的代傳接收端。為此，我們提出一個方法，只要略加修改接收端的部份，便可使發送端得到接收端真正的位址，以利精簡回饋樹的建造。 其次，在接收端極多、分布極廣的環境下，只利用發送端來建造完整的精簡回饋樹比較不切實際。因此，我們建議分散一部份建樹的工作給一些較可靠的代傳接收端，由這些代傳接收端來負責其精簡回饋子樹的建造。組合所有的精簡回饋子樹和發送端本身建造的精簡回饋樹，即可形成完整的精簡回饋樹。 最後，為滿足某些應用程式對傳輸延遲的要求，我們修改了建造精簡回饋樹的演算法。每當要選擇某一接收端為代傳接收端時，若被代傳的接收端從送出回饋到收到重傳封包的延遲可以滿足所要求的重傳延遲，則可確定此代傳接收端為一可用的代傳接收端。經由這樣的修改，使得所建出的精簡回饋樹確保重傳資料造成的延遲可以符合應用程式的要求。 我們針對所提出的方法和時間型精簡回饋的方法作效能上的評比。我們模擬在20個節點、200個節點和550個節點的網路上，封包遺失率由0.001到0.02的情形下，計算發送端會收到的回饋數量，和網路上各個路由器處理回饋與重傳封包的數量。我們發現了以下的結果。 首先，在發送端收到回饋的數量上，不論網路的大小或封包遺失率的高低，兩種方法都有大致相當的精簡效率。雖然我們提出的方法在群播開始進行時，會有一段不穩定的時期，這段不穩定是因發送端才開始得知各接收端的位址，這段時期持續的時間很短，一旦進入穩定期，發送端所收到的回饋數量就限制在在一定的範圍之內。 其次，對於網路上各個路由器收到回饋和重傳封包的數量上，我們所提的方法相較於時間型精簡回饋的方法，有著極大的效能優勢。以200個節點的網路為例，不論封包遺失率是0.005或0.02，幾乎所有的路由器都少處理了高達100倍至1000倍的回饋和重傳封包。 雖然結構型精簡回饋的方法會耗費較多的計算時間，但是由於時下計算機的計算能力有長足的進步，且結構型精簡回饋的方法在精簡回饋的效能上有極大的吸引力。結構型的方法的確是一個值得用作精簡回饋的方法。 此外，我們所提出精簡回饋的方法能夠動態地依據群播群組中現有的接收端，來調整精簡回饋樹。並且針對不同地網路環境，如：有可移動主機的環境，群播群組散佈極廣的環境，和有傳輸延遲要求的應用程式，均有提出一些具體的擴充方式與建議。