考量服務品質之分散式廣播演算法

Abstract

應用層覆蓋網路是建立於傳統的網路系統之上，相較於底層網路架構，其具有更彈性與可調整性之特性。在覆蓋網路中最引人注目的議題之一即是訊息廣播，而許多網路應用也都會使用到訊息廣播技術。透過廣播技術，一個訊息或是網路狀態，可以從起始節點被傳遞給網路上所有的其他節點。而對於分散式系統來說，廣播更因為可以讓整個系統維持共識而在許多分散式應用中更顯重要。 不同應用會根據其網路環境與使用情境而對其網路有不同的目標。在本論文中，我們建立一個最佳化問題並考量一個更普遍性的目標，也就是讓廣播到整個網路所產生的傳輸成本最小化，而這個傳輸成本的定則因為網路所關注的面向不同而有所差異。另外，本論文也考量對服務品質的需求，我們將這些服務品質需求轉化為最佳化問題中的限制式，以將其納入最後決策考量。 本論文所要解決的問題是一個NP-完全的問題，我們提出一個透過建立廣播樹致力於有效率路由規劃的數學規劃模型，我們並使用拉格朗日鬆弛法來解決此一最佳化問題。另外，我們提出一個能夠考量服務品質之分散式廣播演算法來讓其能夠被實際應用在分散式網路的環境之中。最後，我們透過模擬實驗來評估所提出之演算法的效能，同時亦提出數種情境設定並觀察變化，並針對實驗結果予以分析與解釋。

Application-level overlay network is built on top of the traditional Internet system, and it is more flexible and adjustable than existing underlay network. One of the most attractive issue in overlay networks is broadcasting, which could be applied by a number of applications. With broadcasting, a message or network status could be transmitted to the whole network from the source node. In the case of distributed system, broadcasting can help keeping a consensus for the whole system. Different application would set their own objective for their transmission, depends on the network environment and scenario. In this thesis, we formulate an optimization problem and consider a more general objective, which is the minimization of transmission cost in the whole network. The transmission cost mentioned here varies depending on the concern of the network. Furthermore, some QoS (Quality of Service) requirements are also considered, they are transformed into constraints in the proposed optimization problem. The problem that this thesis is going to solve is actually a NP-complete problem. We propose a mathematical programming model which attempts to schedule an efficient routing strategy by constructing a broadcast tree. The Lagrangean relaxation method is then applied to solve the optimization problem. Besides, a distributed broadcast algorithm that considers QoS requirements is proposed to make it possible to implement this algorithm in a distributed environment. Finally, some computing experiments are done to evaluate the performance and variation of the proposed algorithm, and the analyses and interpretations are given.