跳到主要內容

臺灣博碩士論文加值系統

(44.201.97.0) 您好!臺灣時間:2024/04/16 09:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:劉名恕
研究生(外文):Ming-Su Liu
論文名稱:使用Lagrangean近似方法建立具有服務品質之點對點虛擬路徑
論文名稱(外文):Construct QoS end-to-end virtual path using Lagrangean relaxation method
指導教授:陳昌居
指導教授(外文):Chang-Jiu Chen
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:61
中文關鍵詞:服務品質路徑選擇近似方法
外文關鍵詞:QoSroutingLagrangean relaxationsubgradient method
相關次數:
  • 被引用被引用:0
  • 點閱點閱:185
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在現今的網路設計當中中,越來越重視 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.
摘要 III
Abstract IV
誌 謝 V
Contents VI
List of Figures VI
List of Tables VII
1. Introduction 10
2. Previous Work 13
2.1. Source Routing Algorithms 13
2.2. Distributed Routing Algorithms 16
2.3. Hierarchical Routing Algorithms 19
2.4. Previous Work Summary 21
3. Problem Model and Formulation 22
3.1. Problem Description 22
3.2. Network Model and Definition 23
3.3. Problem Formulation 24
4. Lagrangean Relaxation and Problem Decomposition 30
4.1. Solving Subproblem 1 32
4.2. Solving Subproblem 2 33
4.3. Solving Subproblem 3 34
4.4. Subgradient Optimization Procedure 37
4.5. Summary of Lagrangean Relaxation Method 39
5. Lagrangean-based Heuristic Algorithm 40
5.1. Proposed Lagrangean-based Heuristic A lgorithm 41
5.2. Evaluation of the Feasible Schedule 42
6. Experimental Results 43
6.1. Performance Study 44
6.2. Performance Comparisons 46
7. Conclusions and Future Works 55
Reference 58
[1] A. Shaikh, J. Rexford, and K. Shin, “Dynamics of quality-of-service routing with inaccurate link-state information”. U. of MI Tech. rep. CSE-TR-350-97, Nov. 1997.
[2] ATM Forum, Private Network Network Interface (PNNI) v1.0 Specifications, May 1996.
[3] B. Gavish and S.L. Hantler, “An Algorithm for Optimal Route Selection in SNA Networks”. IEEE Trans. on Communications COM-31, pp. 1154-1160, Oct. 1983.
[4] B. Awerbuch et al., “Throughput- Competitive On-line Routing”. 34th Annual Symp. Foundations of Comp. Sci., Pala Alto, CA, Nov. 1993.
[5] B. Awerbuch et al., “Competitive Routing of Virtual Circuits with Unknown Duration”. 5th ACM-SIAM Symp. Discrete Algorithms, Jan. 1994.
[6] D. H. Lorenz and A. Orda, “QoS Routing in Networks with Uncertain Parameters”. IEEE INFOCOM ’98, Mar. 1998.
[7] D. Bienstock and O. Gunluk, “A degree sequence problem related to network design”. Networks, vol. 24, no. 4, pp. 195–205, July 1994.
[8] F. Y. S. Lin and J. R. Yee, “A New Multiplier Adjustment Procedure for the Distributed Computation of Routing Assignments in Virtual Circuit Data Networks”. ORSA Journal on Computing, Vol. 4, No. 3, Summer 1992.
[9] G. N. Rouskas and M. H. Ammar, “Dynamic reconfiguration in multihop WDM networks”. J. High Speed Networks, vol. 4, no. 3, pp. 221–238, 1995.
[10] H. F. Salama, D. S. Reeves, and Y. Viniotis, “A Distributed Algorithm for Delay-Constrained Unicast Routing”. IEEE INFOCOM ’97, Japan, Apr. 1997.
[11] I. Cidon, R. Rom and Y. Shavitt, “Multi-Path Routing Combined with Resource Reservation”. IEEE INFOCM ’97, pp. 92-100, Japan, Apr. 1997.
[12] J. F. P. Labourdette, G.W. Hart, and A. S. Acampora, “Branch-exchange sequences for reconfiguration of lightwave networks”. IEEE Trans. Commun., vol. 42, pp. 2822–2832, Oct. 1994.
[13] K. T. Cheng and F. Y. S. Lin, “Minmax End-to-End Delay Routing and Capacity Assignment for Virtual Circuit Networks”. Proc. IEEE Globecom, pp. 2134-2138, 1995.
[14] K. G. Shin and C. C. Chou, “A Distributed Route-Selection Scheme for Establishing Real-Time Channel”. 6th IFIP Int’l, Conf. High Pref. Networking, pp. 319-329, Sept. 1995.
[15] L. Fratta and M. Cerla and L. Kleinrock, “The flow deviation method: An approach to tore-and-forward communication network design”. Networks 3, pp. 97-133 1973.
[16] L. Kleinrock, “Queueing Systems”. Wiley-Interscience, New York, Vol.1 and Vol.2 1975-1976.
[17] P. J. Courtois and P. Semal, “An Algorithm for the Optimization of Nonbifurcated Flows in Computer Communication Networks”. Performance Evaluation, pp. 139-152, 1981.
[18] Q. Sun and H. Langendirfer, “A New Distributed Routing Algorithm with End-to-End Delay Guaantee”. Unpublished thesis, 1997.
[19] R. Guerin and A. Orda, “QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms”. IEEE INFOCOM ’97, Japan, Apr. 1997.
[20] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, “Network Flows: Theory, Algorithms, and Applications”. Prentice-Hall, 1993.
[21] R. Ramaswami and A. Segall, “Distributed network control for wavelength routed optical networks”. IEEE/ACM Trans. Networking, vol. 5, pp. 936–943, Dec. 1997.
[22] S. Plotkin, “Competitive Routing of Virtual Circuits in ATM Networks”. IEEE JSAC, Vol. 13, pp. 1128-1136, Aug. 1995.
[23] S. Chen and K. Nahrstedt, “Distributed Quality-of-Service Routing in High-Speed Networks Based on Selective Probing”. Tech. rep., Univ. of IL at Urbana-Champaign, Dept. Comp. Sci., 1998 the extended abstract was accepted by LCN ‘98.
[24] S. Chen and K. Nahrstedt, “Distributed QoS Routing with Imprecise State Information”. ICCCN ’98, Oct. 1998.
[25] Z. Wang and J. Crowcroft, “QoS Routing for Supporting Resource Reservation”. IEEE JSAC, Sept. 1996.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊