分散式計算系統資料傳送之最佳化

Abstract

在分散式計算環境中，程式的執行經常需要對遠端的資料進行存取。對於分散式環境下的即時性應用程式而言，高效率的網路資料傳輸機制是非常重要的。為了確保網路通訊品質，我們提出了一個連接導向式的多路徑資料傳送模型，也就是在來源節點與目的節點間可建立多條虛擬線路以增加傳輸頻寬。由於分散式環境下程式執行時所需的資料可能分布在不同的節點內，在不考慮線路傳輸相關延遲的假設之下,多路徑資料傳送的最佳化問題(也就是傳輸時間的最小化)可以描述成多對一的多重流量模型，因此使用線性規劃的技術可以求解此一問題。然而，在此篇論文中我們提出另一種基於切面與流量理論的新方法──關鍵切面法，來解決上述的流量模型。關鍵切面法在求解上述流量問題相關的組合性問題上(例如，當系統中的資料檔有多份拷貝時的最佳傳送問題，或是檔案存放位置的決策問題)具有較高的執行效率。這是因為我們架構在關鍵切面法上所提出的最佳解演算法能夠事先排除大部分的組合情況。此外，我們也對以上所提到的組合性問題提出相關的啟發式演算法。模擬的實驗結果驗證了我們提出的最佳解演算法有非常好的執行效率，而啟發式演算法所得的結果也非常接近最佳解。

In distributed computing environments, executing a program often requires the access of several remote data files. An efficient data routing scheme is thus important for time-critical applications. To ensure a prior desired communication quality, we present a connection-oriented routing scheme, the multipath routing, which allows multiple routes to be established between the source and the destination. By assuming that link delays are negligible, this routing problem can be modeled as a many-to-one multi-commodity flow problem. Linear programming techniques are existed feasible ways to obtain the optimal solution. In this dissertation, we propose an alternative approach, the critical-cut method, to solve this routing problem. The advantage of the proposed method is verified by applying it on the following combinatorial problems, the optimal routing problem for replicated data sources and the file allocation problem. The algorithms based on critical-cut concept have averted exhausting every combinations to obtain the optimal solutions. We also present heuristic approaches with polynomial time complexity to get sub-optimal solutions. Simulation results show that the proposed algorithms notably outperform the ones using linear programming in all cases. The results also show that the heuristic ones are good approximation for these problems.