孫雅麗臺灣大學：資訊管理學研究所劉育良Liu, Yu-LiangYu-LiangLiu2007-11-262018-06-292007-11-262018-06-292006http://ntur.lib.ntu.edu.tw//handle/246246/54325虛擬私人網路提供客戶安全及易於管理的通訊環境。為虛擬私人網路配置足量的頻寬使其能滿足客戶所指定的頻寬需求已成為流量工程領域的一個重要的研究議題。目前一種新的虛擬私人網路資源管理模式稱為 “軟管模式” 已經在文獻中被廣為探討。軟管模式最大的好處之一就是能提供給客戶具彈性且便利的頻寬需求方式。 目前在文獻中已有許多的軟管模式虛擬私人網路建置演算法被發展出來。然而這些建置演算法的主要目的是提升 “建置單一軟管模式虛擬私人網路的頻寬配置效率”。然而這些建置演算法在以下的情況下卻無法達到令人滿意的 “拒絕率”及”需求拒絕率”： (1)網路骨幹上連結的剩餘頻寬量為有限， (2)多個虛擬私人網路的建置要求以 “線上的” 方式被處理。在本論文的第一個部份，我提出了一個新的軟管模式虛擬私人網路建置演算法稱為 “修正式的樹狀繞送演算法”，來解決先前所發展出來的建置演算法之高拒絕率問題。根據實驗的結果，“修正式的樹狀繞送演算法”的確可大幅降低“拒絕率”及”需求拒絕率”。 另外，為了確保虛擬私人網路服務之可靠性，於是 “確保虛擬私人網路中每一對端點之傳輸路徑的可靠性，便成為了一個最重要的議題”。在本論文的第二部份，我在單一連結損壞模式的假設下，對建置多個 “具頻寬保証” 且 “可復原” 的軟管模式虛擬私人網路之諸多議題加以探討。我們在這個部份的研究成果主要是提出一個新的 “備原路徑集合選擇演算法” 及三個 “可復原的軟管模式虛擬私人網路建置演算法”。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.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 簡歷…………………………………………………………….…………… .1081298129 bytesapplication/pdfen-US虛擬私人網路軟管模式虛擬私人網路建置演算法損壞復原流量工程Virtual Private NetworkHose-ModelVPN Provisioning AlgorithmsFailure RestorationTraffic Engineeringotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54325/1/ntu-95-D88725001-1.pdf