使用Lagrangean 近似方法建立具有服務品質之點對點虛擬路徑

Abstract

在現今的網路設計當中中,越來越重視 QoS (Quality of Service)的重要性,在我們的設計中,我們針對不同服務所需滿足之服務要求(在文章中我們關心的目標是以每一個連線的點對點的延遲為訴求), 我們的問題是專注在滿足各個連線的服務品質要求下, 尋找一種路由的方式, 建立虛擬路徑, 使得使用率最高的連結上的負載為最輕(Load Balance Model), 此種構想是希望滿足現有的連線的需求之下, 尋找一種資源分配的方式, 去保留最富彈性的資源選擇給後續再進入網路中要求建立虛擬路徑的連線, 使得其有最大的選擇空間。 我們將此問題規劃成為mixed non-linear programming的形式, 我們利用Lagrangean Relaxation的方式去將此問題的複雜度降低(將某些限制放寬), 再利用此放寬限制後的問題的結果作為一個指引, 搭配我們所提出的一種近似最佳化演算法, 尋得一組合法的解答, 再利用subgradient 的方式,去一直改進答案的優良性,我們的目標是雖然我們無法得到真正的最佳解, 但我們能藉由此種方法的下限值與上限值的差距, 經由實驗的數據, 可以得知我們的方法已經非常優秀, 幾乎求得最佳值。

In this thesis, we have improved a QoS routing problem. We give an approach to minimize the congested link utilization while to satisfy individual connection’s packet delay. We use a Lagrangean Relaxation based approach augmented with an efficient primal heuristic algorithm, called Lagrangean Relaxation Heuristic (LRH). With the aid of generated Lagrangean multipliers and lower bound indexes, the primal heuristic algorithm of LRH achieves a near-optimal upper-bound solution. A performance study delineated that the performance trade-off between accuracy and convergence speed can be manipulated via adjusting the Unimproved Count (UC) parameter in the algorithm. We have drawn comparisons of accuracy and computation time between LRH and the Linear Programming Relaxation (LPR)-based method, under three networks named NSFNET, PACBELL, and GTE and three random networks. Experimental results demonstrated that the LRH is superior to the other approach, namely the LPR method, in both accuracy and computational time complexity, particularly for larger size networks.