寬頻網路多媒體訊務最佳傳遞路徑選擇技術研究

Abstract

現今網路為了提供即時性的多媒體傳遞服務必須在短時間內有效地選擇封包的傳送路徑。除此，路徑的選擇需達到高效率的系統使用率，並同時提供保證的服務品質給使用者。在此論文中，我們提出一個快速且提供服務品質保證的路徑選擇方法，並建立具備線性規劃特點的數學模型。此模型中，目標函數有別於以往根據M/M/1排隊模型理論的非線性方法計算封包平均延遲，改以降低每個節點的輸入和輸出鏈結最大使用率總和做為目標函數，藉此分散網路流量，提高throughput。此方法將計算端對端延遲時間複雜的非線性問題轉換為較易解決的線性最佳化問題，進而提供一個快速、簡單求解最佳路徑選擇的方法，並能同時提供高服務品質給使用者。為了展現所提方法之效能，我們根據不同的網路拓璞、link capacity、使用者數量、使用者位置分布等各種情況，將所提的模型與M/M/1模型給定相同的參數，運用LINGO、CPLEX求得使用者選擇的路徑，並運用NS2網路模擬工具建置網路拓璞，藉此統計出各項實驗數據。透過實驗結果比較發現，在網路traffic並非符合M/M/1假設時，所提出的模型延遲在大部分情況下與M/M/1相當，而最差的情況也只比M/M/1稍大，但求解時間相對M/M/1模型減少好幾倍。

Nowadays, to deliver real-time multimedia services in network, the system must effectively choose delivery path for packets in a short time. The decision of choosing path must optimize the system utilization, and also guarantee the Quality-of-Service (QoS) for users in the meantime. In this paper, we propose a method which can quickly choose path and guarantee QoS for users, and formulate a linear programming mathematical model. In this model, the objective function is minimizing the sum of maximum input link utilization and maximum output link utilization of each node instead of calculating the average packet delay by non-linear M/M/1 queuing model. This method changes a difficult non-linear problem into an easy linear optimization problem and provides a quick and simple way to choose path. In order to compare the effectiveness of the proposed method with M/M/1 model in different topologies, link capacity, the number of users, and the distribution of users, we obtain the users’ selected path by using LINGO and CPLEX, and simulate it in NS2, network simulation tools. According to the experimental results, mostly the delay of the proposed model is nearly the same as the delay of M/M/1 model and even in the worst case is slightly bigger than M/M/1. However, M/M/1 model need much more the time of solving problem than the proposed model.