考量成本效益之適性化異質網路路由演算法

在現今多元架構的網路環境中，存在著眾多的網路服務提供者(ASP)及經營者(network operators)，如果在這樣的網路環境中進行服務存取的動作，產生的網路連線勢必會經過不同的網路經營者之網路，或是經過不同形式的網路媒介，所以在服務品質及效益上的考量，網路服務提供者的選擇將會有許多的自主性。本研究將基於成本效益的模式，依據賽局理論(game theory)的觀念建立我們的研究目標，在這多元化的異質網路結構中，選出最符合網路服務提供者需求的路由策略。由於本研究所探討的問題是歸屬在資源條件限制下之路由最佳化，也就是服務品質為考量的路由問題。此項問題在本質上是屬於NP-Complete的問題，因此我們採用拉格蘭日鬆弛法（Lagrangean Relaxation）作為主要的解題程序；針對問題中不同條件式之鬆弛後，對應到相關的經驗法則，以減少求解的複雜度；在問題規劃完成之後，再將此數學規劃問題導入合理化的數據，以測試並驗證這些解題程序之效果及效率，以求達到數學最佳化 (Mathematical Optimization)。對於網路的路由策略選擇，本研究的貢獻在於提供一個路由的參考方針，使得網路參與者在面對基於異質網路（Heterogeneous Network）架構的路由問題時，可以有一準則可依循，而且結果將符合網路服務提供者本身的需求理念與考量。

關鍵字

賽局理論；異質網路；數學最佳化；拉格蘭日鬆弛法；路由；服務品質

並列摘要

Nowadays, the network environment is diversified and there are so many network service providers and network operators. If we proceed to access network services in such an environment, the connections between terminals would pass through different network operators’ networks or diverse network media. Therefore, in the consideration of quality of service and beneficial results, network service providers would be their own master in choosing their network operators. The goal of our research will be based on cost and utility according to the game theory. We will try to make the proper routing decisions that will tally with network service providers’ need in the heterogeneous network. Because the thesis that we probe into is in the classification of path-constrained and path-optimization QoS routing problems, it is the NP-complete Problem. Therefore, we will apply the Lagrangean relaxation method and the subgradient method to solve the problems. After the planning of mathematical model is done, we will try to find the proper statistics to fit into the model. We will also make some experiments to test the effect and efficiency of the model in order to achieve the Mathematical Optimization. About the heterogeneous network routing, our main contribution is that we provide the guidance for the routing decision makers so that they can handle the routing problems in the heterogeneous network, and the routing decisions that we provided will satisfy the network service providers’ needs and considerations.

並列關鍵字

Lagrangean Relaxation ； Heterogeneous Network ； Game Theory ； Mathematical Optimization ； Routing ； QoS

參考文獻

[1] Marija Vrdoljak and Sasa Ivan Vrdoljak, “Fixed-Mobile Convergence Strategy: Technologies and Market Opportunities,” IEEE Communications Magazine, February 2000.

[7] R.H Stratman, “Development of an integrated network manager for heterogeneous networks using OSI standards and object-oriented techniques,” IEEE Journal on Selected Areas in Communications, vol. 12, no. 6, August 1994.

[11] J.S. Baras, M.S. Corson, K. Jang, M. Li, A. Misra and H. Xie, “Hierarchical, layered modeling and performance evaluation of hybrid communication networks,” Proc. MILCOM 97, vol. 3, pp. 1313-1317, November 1997.

[14] Shigang Chen and Klara Nahrstedt “An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions,” IEEE Network, NOV/DEC 1998.

[16] Lee, W. C. et al, “Routing subject to Quality of Service constraints integrated communication networks,” IEEE Network, July/August 1995.

國際替代計量

考量成本效益之適性化異質網路路由演算法

未授權

主題瀏覽