請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/24004
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 孫雅麗(Yeali S. Sun) | |
dc.contributor.author | Yu-Liang Liu | en |
dc.contributor.author | 劉育良 | zh_TW |
dc.date.accessioned | 2021-06-08T05:13:53Z | - |
dc.date.copyright | 2006-07-13 | |
dc.date.issued | 2006 | |
dc.date.submitted | 2006-07-11 | |
dc.identifier.citation | [1] R. K. Ahuja and T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-hall, Englewood Cliffs, NJ, 1993.
[2] G. Apostolopoulos, R. Guérin, S. Kamat, S. K. Tripathi, Server-Based QoS Routing, in: Proc. of IEEE GLOBECOM, 1999. [3] D. O. Awduche, L. Berger, D. Gan, V. Srinivasan and T. Li, G. Swallow, RSVP-TE: Extension to RSVP for LSP tunnels, IETF RFC 3209, December 2001. [4] D. O. Awduche, J. Malcom, J. Agobua, M. O’Dell and J. Mcmanus, Requirement for Traffic Engineering over MPLS, IETF RFC 2702, September 1999. [5] A. Balasubramanlan and G. Sasaki, Bandwidth Requirement for Protected VPNs in the Hose Model, in: Proc. of IEEE International Symposium on Information Theory, 2003. [6] A. Banerjee, L. Drake, L. Lang, B. Turner, D. Awduche, L. Berger, K. Kompella, Y. Rekhter, Generalized Multi-protocol Label Switching: An Overview of Signaling Enhancements and Recovery Techniques, IEEE Communications Magazine 39 (7) (2001) 144-151. [7] M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, Linear Programming and network Flows, John Wiley & Sons, 1990. [8] L. Berger, Generalized Multi-Protocol Label Switching (GMPLS) signaling Functional Description, IETF RFC 3471, 2003. [9] D. Bertsekas, R. Gallager, Data Networks, Prentice-Hall, 1987. [10] R. Callon, N. Feldman, A. Fredette, G. Swallow, and A. Viswanathan, A Framework for Multiprotocol Label Switching”, Internet Deraft draft-ietf-mpls-framework-03.txt, 1999. [11] A. Capone, L. Fratta, F. Martignon, Dynamic Routing of Bandwidth Guaranteed Connections in MPLS Networks, International Journal on Wireless and Optical Communications 1 (1) (2003) 75-86. [12] A. Capone, L. Fratta, F. Martignon, Dynamic Online QoS Routing Schemes: Performance and Bounds, Computer Networks 50 (2006) 966-981. [13] C. T. Chou, Traffic Engineering for MPLS-based Virtual Private Networks, Computer Networks 44(3) (2004) 319–333. [14] T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, Twentieth printing, MIT Press, 1998. [15] B.S. Davie, Y. Rekhter, MPLS Technology and Applications, Morgan Kaufmann, San Francisco, CA, 2000. [16] N. G. Duffield, P. Goyal and A. Greenberg, A Flexible Model for Resource Management in Virtual Private Networks, in: Proc. of ACM SIGCOMM, 1999. [17] N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan and J. E. V. D. Merwe, Resource Management with Hoses: Point-to-Cloud Services for Virtual Private Networks, IEEE/ACM Transactions on Networking 10(5) (2002) 679-692. [18] T. Erlebach and M. Rürich, “Optimal Bandwidth Reservation in Hose-Model VPNs with Multi-Path Routing, in: Proc. of IEEE INFOCOM, 2004. [19] B. Fortz, M. Thorup, Optimizing OSPF/IS-IS weights in a changing world, IEEE J. Selected Areas in Communications 20 (4) (2002) 756–767. [20] L. Fratta, M. Gerla, L. Kleinrock, The Flow Deviation Method: An Approach to Store-and-Forward Network Design, Network 3 (1973) 97-133. [21] G. N. Frederickson and. J. J. Joseph, “Approximation Algorithms for Several Graph Augmentation Problems”, SIAM Journal of Computing, vol. 10-2, pp. 270-283, 1981. [22] K. Gopalan, T. C. Chiueh and Y. –J. Lin, Load Balancing Routing with Bandwidth-Delay Guarantees, IEEE Communications Magazine, vol. 42, pp. 108-113, 2004. [23] R. Guerin, A. Orda, and D. Williams QoS Routing Mechanisms and OSPF Extensions, IETF RFC 2676, 1999. [24] R. Guerin, D. Williams, and A. Orda, QoS Routing Mechanisms and OSPF Extensions, in Proc. of IEEE Globecom, 1997. [25] A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi and B. Yener, Provisioning a Virtual Private Network: A Network Design Problem for Multicommodity Flow, in: Proc. of the 33rd Annual ACM Symposium on Theory of Computing (STOC), 2001. [26] A. Gupta, A. Kumar and R. Rastogi, Exploring the Trade-off between Label Size and Stack Depth in MPLS Routing, in: Proc. of IEEE INFOCOM, 2003. [27] D. S. Hochbaum, Approximation Algorithms for NP-Hard Problems. Boston, MA: PWS, 1997. [28] E. Horowitz, S. Sahni and S. Anderson-Freed, Fundamentals of Data Structure in C, Computer Science Press, 1993. [29] G. Italiano, R. Rastogi and B. Yener, Restoration Algorithms for Virtual Private Networks in the Hose Model, in: Proc. of IEEE INFOCOM, 2002. [30] A. Jűttner, I. Szabơ and Á Szentesi, On Bandwidth Efficiency of the Hose Resource Management Model in Virtual Private Networks, in: Proc. of IEEE INFOCOM, 2003. [31] K. Kar, M. Kodialam and T. V. Lakshman, Minimum Interference Routing of Bandwidth Guaranteed Tunnels with MPLS Traffic Engineering Applications, IEEE J. Selected Areas in Communications 18(12) (2000) 2566-2579. [32] S. Khulleer and R. Thurimella, Approximation Algorithms for Graph Augmentation, Journal of Algorithms, Vol. 14-2, pp. 214-225, 1993. [33] M. Kodialam and T. V. Lakshman, Minimum Interference Routing with Applications to MPLS Traffic Engineering, in: Proc. of IEEE INFOCOM ,2000. [34] M. Kodialam and T. T. Lakshman, Dynamic Routing of Bandwidth Guaranteed Tunnels with Restoration, in: Proc. of IEEE INFOCOM, 2000. [35] M. Kodialam and T. T. Lakshman, Dynamic Routing of Locally Restorable Bandwidth Guaranteed Tunnels using Aggregated Link Usage Information, in: Proc. of IEEE INFOCOM, 2001. [36] L. Kou, G. Markowsky, L. Berman, A Fast Algorithm for Steiner Trees. Acta Informatica, Springer-Verlag, 1981: vol. 15, pp.141-145. [37] A. Kumar, R. Rastogi, A. Silberschatz and B. Yener, Algorithms for Provisioning Virtual Private Networks in the Hose Model, Bell Labs Technical Memo., 2000. [38] A. Kumar, R. Rastogi, A. Silberschatz and B. Yener, Algorithms for Provisioning Virtual Private Networks in the Hose Model, , in: Proc. of ACM SIGCOMM, 2001. [39] A. Kumar, R. Rastogi, A. Silberschatz and B. Yener, Algorithms for Provisioning Virtual Private Networks in the Hose Model, IEEE/ACM Transactions on Networking 10(4) (2002) 565-578. [40] L. E. Li, M. M. Buddhikot, C. Chekuri and K. Guo, Routing Bandwidth Guaranteed Paths with Local Restoration in Label Switched Networks in: Proc. of IEEE International Conference on Network Protocols, 2002. [41] H. –L. Liu, I. Faynberg, An Architectural Framework for Support of Quality of Service in Packet Networks, IEEE Communications Magazine, 41 (6) (2003) 98-105. [42] Y. -L. Liu, Y. S. Sun, M. C. Chen, MTRA: An On-Line Hose-Model VPN Provisioning Algorithm, Telecommunication Systems, 31(4) (2006) 379-398. [43] Y. -L. Liu, Y. S. Sun, M. C. Chen, Traffic Engineering for Hose-Model VPN Provisioning, in: Proc. of IEEE GLOBECOM, 2005. [44] J. L. Marzo, E. Calle, C. Scoglio, T. Anjali, QoS online routing and MPLS multi-level protection: A Survey, IEEE Communications Magazine 41 (10) (2003) 126-132. [45] A. Medina, A. Lakhina, I. Matta and J. Byers, BRITE: Universal Topology Generation from a User’s Perspective, http://www.cs.bu.edu/brite/publications/usermanual.pdf, 2001. [46] A. Medina, A. Lakhina, I. Matta and J. Byers, BRITE: An Approach to Universal Topology Generation, in: Proc. of the International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunications Systems (MASCOTS), 2001. [47] S. Norden, M.M. Buddhikot, M. Waldvogel and S. Suri, Routing Bandwidth Guaranteed Paths with Restoration in Label Switched Networks, in Proc. of IEEE International Conference on Network Protocols (ICNP 2001). [48] S. Norden, M.M. Buddhikot, M. Waldvogel and S. Suri, Routing Bandwidth-Guaranteed Paths with Restoration in Label-Switched Networks, Computer Network 46 (2004) 197-218. [49] J. Plesnik, A Bound for the Steiner Tree Problem in Graphs, Mathematica Slovaca, vol 31, no.2, 1981, pp.155-163. [50] S. Plotkin, Competitive Routing of Virtual Circuits in ATM Networks, IEEE J. Selected Areas in Communications 13(6) (1995) 1128-1136. [51] S. Raza, F. Aslam and Z. A. Uzmi, Online Routing of Bandwidth Guaranteed Paths with Local Restoration using Optimized Aggregate Usage Information in: Proc. of IEEE International Conference on Communications, 2005. [52] G. Rétvári, J. J. Bĺró, T. Cinkler, T. Henk, A Precomputation Scheme for Minimum Interference Routing: the Least-Critical-Path-First Algorithm, in: Proc. of IEEE INFOCOM, 2005. [53] F. Ricciato and U. Monaco, Routing Demands with Time-Varying Bandwidth Profiles on a MPLS Network, Computer Networks 47(1) (2005) 47–61. [54] F. Ricciato, S. Salsano, A. Belmonte, M. Listanti, Off-line configuration of a MPLS over WDM network under timevarying offered traffic, in: in: Proc. of IEEE INFOCOM, 2002. [55] E. Rosen, A. A. Viswanathan and R. Callon, Multiprotocol Label Switching Architecture, RFC 3031, 2001. [56] S. Suri, M. Waldvogel and P. R. Warkhede, Profile-Based Routing: A New Framework for MPLS Traffic Engineering, Washington University Computer Science Technical Report, July 2001 [57] S. Suri, M. Waldvogel and P. R. Warkhede, Profile-Based Routing and Traffic Engineering, Computer Communications 26(4) (2003) 351-365. [58] C. Swamy and A. Kumar, Primal-Dual Algorithms for Connected Facility Location Problems, in: Proc. of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, 2002. [59] S. –W. Tan, S. –W. Lee and B. Vaillaint, Non-Greeedy Minimum Interference Routing Algorithm for Bandwidth-Guaranteed Flows, Computer Communications 25(17) (2002) 1640-1652. [60] V. Vazirani, G. Tech, The Steiner Tree Problem and Its Generalizations, International Proceedings of Workshop on APPROX'98, Springer-Verlag, pp.33-38, 1998. [61] B. Wang, X. Su, and C. L. P. Chen, A New Bandwidth Guaranteed Routing Algorithm for MPLS Traffic Engineering”, in: Proc. of IEEE International Conference on Communications, 2002. [62] Z. Wang and J. Crowcroft, Quality of Service Routing for Supporting Multimedia Applications, IEEE J. Selected Areas in Communications 14(7) (1996) 1228-1236. [63] T.H. Wu, Fiber Network Service Survivability, Artech House, Norwood, MA, 1992. [64] Y. Yang, L. Zhang, J. K. Muppala and S. T. Chanson, Bandwidth-Delay Constrained Routing Algorithms, Computer Networks 42(4) (2003) 503-520. [65] D. Zhou, S. Subramaniam, Survivability in optical networks, IEEE Network 14 (6) (2000) 16–23. [66] AMPL: A Modeling Language for Mathematical Programming. Available at: http//www.ampl.com. [67] ILOG CPLEX. Available at: http://www.ilog.com/products/cplex/. [68] 鐘泓田,“多波長分工網路上虛擬私有網路之建置”,國立台灣大學資訊管理研究所碩士論文,中華民國九十一年。 [69] 陳佳宏,“架構於高適存分波多工網路之光繞路與波長指定演算法”,國立台灣大學資訊管理研究所碩士論文,中華民國九十二年。 | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/24004 | - |
dc.description.abstract | 虛擬私人網路提供客戶安全及易於管理的通訊環境。為虛擬私人網路配置足量的頻寬使其能滿足客戶所指定的頻寬需求已成為流量工程領域的一個重要的研究議題。目前一種新的虛擬私人網路資源管理模式稱為 “軟管模式” 已經在文獻中被廣為探討。軟管模式最大的好處之一就是能提供給客戶具彈性且便利的頻寬需求方式。
目前在文獻中已有許多的軟管模式虛擬私人網路建置演算法被發展出來。然而這些建置演算法的主要目的是提升 “建置單一軟管模式虛擬私人網路的頻寬配置效率”。然而這些建置演算法在以下的情況下卻無法達到令人滿意的 “拒絕率”及”需求拒絕率”: (1)網路骨幹上連結的剩餘頻寬量為有限, (2)多個虛擬私人網路的建置要求以 “線上的” 方式被處理。在本論文的第一個部份,我提出了一個新的軟管模式虛擬私人網路建置演算法稱為 “修正式的樹狀繞送演算法”,來解決先前所發展出來的建置演算法之高拒絕率問題。根據實驗的結果,“修正式的樹狀繞送演算法”的確可大幅降低“拒絕率”及”需求拒絕率”。 另外,為了確保虛擬私人網路服務之可靠性,於是 “確保虛擬私人網路中每一對端點之傳輸路徑的可靠性,便成為了一個最重要的議題”。在本論文的第二部份,我在單一連結損壞模式的假設下,對建置多個 “具頻寬保証” 且 “可復原” 的軟管模式虛擬私人網路之諸多議題加以探討。我們在這個部份的研究成果主要是提出一個新的 “備原路徑集合選擇演算法” 及三個 “可復原的軟管模式虛擬私人網路建置演算法”。 | zh_TW |
dc.description.abstract | Virtual private networks (VPNs) provide customers with a secure and manageable communication environment. The allocation of bandwidth for VPNs to meet the requirements specified by customers is now one of the most important research issues in the field of traffic engineering. A VPN resource-provisioning model called hose-model was developed to provide customers with a flexible and convenient way to specify the bandwidth requirements of a VPN.
Several hose-model VPN provisioning algorithms have already been proposed. They focus on the bandwidth efficiency issue in the case of establishing a single hose-mode VPN. However, these algorithms cannot achieve a satisfactory rejection ratio and demand rejection ratio when: (1) the residual bandwidths on links of the network backbone are finite and (2) multiple VPN setup requests are handled on-line. In the first part of this dissertation, we propose a new hose-model VPN provisioning algorithm called MTRA to address the issue. According to the simulation results, MTRA can indeed reduce rejection ratio and demand rejection ratio effectively. In addition, reliability of a VPN depends on the reliability of data transmission paths between all endpoints pair. In the second part of this dissertation, the issues regarding online establishment of restorable bandwidth-guaranteed hose-model VPNs under the single-link failure model is discussed. We mainly propose a new backup path set selection algorithm and three restorable VPN provisioning algorithms. | en |
dc.description.provenance | Made available in DSpace on 2021-06-08T05:13:53Z (GMT). No. of bitstreams: 1 ntu-95-D88725001-1.pdf: 1298129 bytes, checksum: 5180446eec0fd4f32ffdc62b7058fa5b (MD5) Previous issue date: 2006 | en |
dc.description.tableofcontents | Chapter 1 Introduction…………………………………………………………….1
1.1 Virtual Private Networks (VPNs)…...……..……………………..……………1 1.2 Motivation/Problem/Research Scope .…………………………………..…….5 1.3 Contributions…………………………………………………………………..8 Chapter 2 Background and Literature Survey …………………………………..10 2.1 The Hose Model ……………………………………… ………………….....10 2.2 Hose-Model VPN Provisioning……………………………………………...12 2.2.1 Provider-pipes algorithm………………………………………………...…13 2.2.2 Hose-specific state algorithm………………………………………………14 2.2.3 VPN-specific state algorithm……………………………………………… 15 2.2.4 Tree routing algorithm ………………………………………………….…16 2.3 Online QoS Routingv…...……………………………………………………26 2.3.1 Min-hop algorithm…………………………………………………….... …29 2.3.2 Widest shortest path algorithm………………………………………….. …29 2.3.3 Shortest widest path algorithm……………………………………………..29 2.3.4 Minimum interference routing algorithm…………………………………..30 2.3.5 Least critical path first algorithm……………………….. …………………32 2.3.6 Profile-base routing algorithm……………………………………………...32 2.3.7 Virtual flow deviation algorithm……………………………………………33 2.3.8 Routing connections with time-variable bandwidth profile ………………34 2.3.9 Routing connections with restoration …………………………………… 35 2.4 The Multi-Protocol Label Switching (MPLS) Technology…... ……………..35 2.4.1 MPLS label assignment scheme for a VPN tree…………………………...37 Chapter 3 On-line Hose Model VPNs Establishment ……………………….….39 3.1 Network Backbone Modeling………………………………………….…….39 3.2 VPN Setup Request Modeling………………………………….……………41 3.3 Problem……………………………………………………………….……...41 3.3.1 The Drawbacks of Previous Algorithms…………………………………....43 3.3.2 The Factors Influencing Rejection Ratio………………………………....46 3.4 Modified Tree Routing Algorithm……………………………………….….46 3.5 Theoretical Upper Bounds of the Rejection Ratios………………………….50 3.6 Performance Evaluation…………………………………………….……….54 3.6.1 Simulation Environment……………………………………….………....55 3.6.2 Simulation Results…………………………………………………….….56 Chapter 4 On-line ResTorable VPNs Establishment…………………………...69 4.1 Problem ……………………………………………………………….… ...69 4.1.1 Background……...…………………………………….…....................69 4.1.2 The Restorable VPN ..…...……………………………….…… …….71 4.1.3 Problem Definition...………………………………………………...72 4.2 Banwidth-Guaranteed Backup Paths Set Algorithm (BANGUAD)……….74 4.3 Bandwidth-Sharing Algorithm among Restorable VPNs ………………..81 4.4 The Three Proposed Restorable VPN Provisioning Algorithms ……….…..87 4.5 Performance Evaluation ………………………………………….……….89 Chapter 5 Conclusion and Future Works …………………………….……….97 Reference……………………………………………………………….……...101 簡歷…………………………………………………………….…………… .108 | |
dc.language.iso | en | |
dc.title | 建置軟管模式虛擬私人網路之流量工程研究 | zh_TW |
dc.title | Traffic Engineering for Hose-Model VPN Provisioning | en |
dc.type | Thesis | |
dc.date.schoolyear | 94-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 陳孟彰(Meng Chang Chen),高明達(Ming-Tat Ko),林永松(Yeong-Sung Lin),陳靜枝(Ching-Chin Chern) | |
dc.subject.keyword | 虛擬私人網路,軟管模式,虛擬私人網路建置演算法,損壞復原,流量工程, | zh_TW |
dc.subject.keyword | Virtual Private Network,Hose-Model,VPN Provisioning Algorithms,Failure Restoration,Traffic Engineering, | en |
dc.relation.page | 108 | |
dc.rights.note | 未授權 | |
dc.date.accepted | 2006-07-11 | |
dc.contributor.author-college | 管理學院 | zh_TW |
dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 1.27 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。