| dc.contributor.advisor | 連耀南 | zh_TW |
| dc.contributor.author (Authors) | 李宗勳 | zh_TW |
| dc.creator (作者) | 李宗勳 | zh_TW |
| dc.date (日期) | 2003 | en_US |
| dc.date.accessioned | 17-Sep-2009 13:53:42 (UTC+8) | - |
| dc.date.available | 17-Sep-2009 13:53:42 (UTC+8) | - |
| dc.date.issued (上傳時間) | 17-Sep-2009 13:53:42 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0090753026 | en_US |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/32631 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 資訊科學學系 | zh_TW |
| dc.description (描述) | 90753026 | zh_TW |
| dc.description (描述) | 92 | zh_TW |
| dc.description.abstract (摘要) | 面對通訊與資訊科技的大幅進步、網際網路的蓬勃發展、以及電信自由化帶來的激烈競爭，通訊網路正在進行一個巨大的變革，企圖將原有Circuit Switching 與 Packet Switching 網路整合成一個單一整合型網路－All-IP網路以支援所有的應用服務。All-IP網路受限於封包交換網路原有的特性，有服務品質問題(QoS)有待克服，因此有必要在All-IP網路上提供服務品質管理機制以實現整合型網路的目標。而要提供適當的QoS 管理，其成功之關鍵主要在於是否能提供一個簡單易行之架構。本論文先提出BBQ(Budget-Based QoS)採用以預算為基礎之服務品質管理，BBQ提供一個高適用性的管理架構和相關的管理工具，可適用於不同的下層網路架構和不同營運目標的網管政策。 而在本文中提出以路徑規劃(Path Planning)的方式作為此架構的路由方法。路徑規劃係以過去的歷史訊務資料為基礎，為未來可能進入網路中的訊務規劃出一組具有品質要求的路徑，而在系統運作時，只需根據訊務的需求，指定一條符合其品質要求的路徑即可。此方法不但可以給予進入網路的訊務絕對的服務品質保證，而且事前的運算可以免除在系統運作時大量的計算負擔。在本論文中，我們設計了一套路徑規劃的演算法，來驗證我們的方法之效能。而經過反覆的模擬測試，發現本路徑規劃方法的確較傳統OSPF演算法擁有較佳的網路效能，且可以提供進入網路的訊務較佳的服務品質保證。 | zh_TW |
| dc.description.abstract (摘要) | The advance in information technology and impact of telecommunications liberalization cause a revolution in commucation world. It attempt to merge circuit-switching and packet-switching network into one standlone perform. All-IP is one of those candidates. But All-IP also inherits the characteristics of packet-switching network, the problem of transmission quality. So, we need some management system of quality on All-IP network to achieve the ambition of converged network. In this thesis, we propose BBQ management system. BBQ offers a highly adaptive management architecture and some management tools for operators. Those tools can be used in different underly network layer and can be tuned by different network policy. We propose the path planning as routing approach in BBQ architecture. Path-planning is doing path calculation for the traffic may happen in future using the historic traffic statistic. In run-time, admission control component will assign a planned path that satisfy the requirements of admitted traffic. In this method, absolute transmission quality is guaranteed to admitted traffic. And pre-planning can reduce heavy calculation overhead in run-time. In this thesis, we design a path-planning algorithm, the GPPA algorithm, which takes pre-defined profit as its maximize objective under bandwidth and quality constraints. Through an performance evaluation using simulation method, we demonstrate that the path-planning might outperform the traditional OSPF algorithm. | en_US |
| dc.description.tableofcontents | 內容目錄摘要 2第一章、簡介 (Introduction) 10 1.1 電信產業的趨勢 11 1.1.1 整合性網路 (Network Convergence - All-IP Network) 12 1.1.2 封包網路上乘載具時效性應用問題 (Real-time Application on packet-switching networks) 13 1.2 網路服務品質定義 (Definition of QoS) 14 1.2.1 分歧的品質保證期望 (Diversified QoS Expectations) 15 1.3 全IP網路之服務品質保證 (QoS over All-IP Networks) 15 1.4 UMTS服務等級 (UMTS Services Class) 16 1.5 網路服務品質管理方法 (QoS Management) 19 1.5.1 Integrated Service 19 1.5.2 Differentiated Service 19 1.6 研究動機及目的 (Motivation and Research Objective) 20 1.7 解決方案 (Solution Approaches) 21 1.8 論文組織結構 22第二章、相關研究 (Related Work) 23 2.1 服務品質保證方案相關研究 23 2.1.1 端對端的服務品質保證 23 2.1.2 資源分配最佳化 23 2.2 服務品質網路架構 24 2.2.1 Integrated Service 25 2.2.2 Differentiated Service 25 2.2.3 Victor`s System 29 2.2.4 TEQUILA 30 2.3 繞徑問題相關研究 32 2.3.1 傳統繞徑方法 32 2.3.1.1 廣播式繞徑方法 (Flooding) 32 2.3.1.2 最短路徑演算法 (Shorest Path Routing) 33 2.3.1.3 訊務基礎路徑演算法 (Flow-based Routing) 33 2.3.1.4 距離向量繞徑演算法 (Distance Vector Routing) 33 2.3.1.5 鏈結狀態繞徑方法 (Link State Routing) 34 2.3.2 具服務品質保證之繞徑方法 (Multi-Constrained Path) 34 2.3.3 繞徑方法之評論 35 2.4 評論 (Summary) 35第三章、以預算為基礎之服務品質保證 (Budget-Based QoS) 37 3.1 BBQ架構 (Budget-Based QoS Framework) 37 3.1.1 簡化的All-IP網路架構 (A Simplified All-IP Network Architecture) 38 3.1.2 以預算為基礎之管理 (Budget-Based Management) 39 3.1.3 路徑定義 (Path Definitions) 40 3.1.4 承載服務架構 (Bearer Service Architecture) 41 3.1.5 服務品質熵數 (Quality Entropy) 42 3.1.6 即時資源分配與預先資源管理 43 3.1.7 集中式與分散式資源配置 (Centralized vs. Distributed Allocations) 44 3.1.8 需求預測 45 3.2 管理系統架構 (Management System Architecture for BBQ) 46 3.2.1 BBQ管理系統假設 (BBQ System Assumptions) 46 3.2.2 分散式分層管理系統 (Distributed Management System Hierarchy) 46 3.2.3 管理系統軟體架構 (Management System Software Architecture) 47 3.2.4 簡化的端對端服務品質建立流程 (A Simplified End-to-End Path Setup Procedure) 48 3.3 BBQ中的核心網路架構與QoS元件 (Core Network Architecture and QoS Components for BBQ) 49 3.3.1 核心網路資源規劃方法 50 3.3.2 核心網路內的資源規劃元件 51 3.3.3 分散式資源規劃運作流程 53 3.3.4 資源調配可能產生之問題討論 57 3.3.4.1 Inter-Ingress資源浪費 57 3.3.4.2 Intra-Ingress 資源浪費 58 3.3.5 資源調配問題之解決方案 60第四章、核心網路之路徑規劃 62 4.1 BBQ架構中各層級之路徑 (Path Definition) 63 4.2 在BBQ架構中的路徑規劃元件 (Path Planning Agent in BBQ Architecture) 64 4.3 路徑規劃的環境假設 66 4.4 端對端規劃路徑元件與核心網路內路徑規劃元件之互動 66 4.5 核心網路內路徑規劃運作流程 (Path Planning Procedure) 67 4.5.1 路徑資源需求與鏈結頻寬需求之轉換 68 4.6 路徑規劃最佳化 70 4.7 最佳化模型 (System Model) 71 4.8 Greedy Algorithm for Path Planning(G.P.P.A.) 75 4.8.1 演算法虛擬碼 (Pseudo Code) 78 4.8.2 演算法複雜度分析 79 4.9 小結(Summary) 80第五章、效能評估 (Performance Evaluation) 81 5.1 效能評估指標 (Performance Evaluation Metrics) 81 5.1.1 獲利指標 (Profit) 81 5.1.2 鏈結使用率之標準差 (Link Utilization S.D.) 82 5.1.3 獲利密度(Profit Density) 82 5.2 實驗設計 (Design of Experiment) 82 5.2.1 實驗工具 82 5.2.1.1 BBQ Computational Simulator 83 5.2.2 實驗測試組產生方式 83 5.2.2.1 網路拓樸之產生與設定 83 5.2.2.2 訊務之產生與設定 84 5.2.3 實驗流程 85 5.2.4 實驗組 86 5.3 模擬過程及結果分析 87 5.3.1 實驗一：演算法的行為測試 87 5.3.1.1 獲利趨勢 87 5.3.1.2 獲利密度趨勢 88 5.3.2 實驗二：節點多寡之影響 (Number of Nodes) 89 5.3.2.1 拓樸中節點多寡對於獲利指標的影響 89 5.3.2.2 拓樸中節點多寡對於鏈結使用率標準差的影響 91 5.3.2.3 拓樸中節點多寡對於獲利密度的影響 92 5.3.3 實驗三：連接率之影響 (Connectivity) 93 5.3.3.1 連接率對於獲利指標的影響 93 5.3.3.2 連接率對於鏈結使用率標準差的影響 95 5.3.3.3 連接率對於獲利密度的影響 96 5.3.4 實驗四：預測誤差之影響 (Forecast Error) 97 5.3.4.1 預測誤差之定義 97 5.3.4.2 預測誤差對於獲利指標的影響 97 5.3.4.3 預測誤差對於獲利密度的影響 99 5.4 結論 100第六章、總結 (Conclusion) 101致謝詞 (Acknowledgment) 103參考文獻 (References) 103圖目錄圖1. 1：各UMTS服務類別對三大品質指標之容忍度 18圖2. 1：每個使用者所得到的服務品質取決於網路的負載 25圖2. 2：DiffServ Domain說明 27圖2. 3：以DiffServ為基礎的分散式資源管理 31圖2. 4：TEQUILA架構 32圖3. 1：簡化的全IP網路架構 40圖3. 2：端對端承載服務 42圖3. 3：服務品質熵數之對應 43圖3. 4：BBQ管理系統軟體元件架構 49圖3. 5：簡化的端對端服務品質建立流程 50圖3. 6：BBQ架構之核心網路 51圖3. 7：核心網路軟體架構 54圖3. 8：核心網路中資源分配流程 56圖3. 9：資源規劃流程 57圖3. 10：不同Ingress之間資源無法彈性調配 59圖3. 11：不同路徑之間的資源無法彈性調配 60圖4. 1：路徑規劃元件之互動程序 67圖4. 2：路徑規劃轉換鏈結頻寬需求之說明 69圖4. 3：演算法流程 77圖5. 1：實驗流程圖 85圖5. 2：實驗步驟及資料流向 86圖5. 3：預測規劃的獲利趨勢 88圖5. 4：預測規劃與利潤密度趨勢 89圖5. 5：節點多寡對於獲利指標的影響 90圖5. 6：節點多寡對於鏈結使用率標準差的影響 92圖5. 7：節點多寡對於獲利密度的影響 93圖5. 8：連接率對於獲利指標的影響 94圖5. 9：鏈結率對於鏈結使用率標準差的影響 96圖5. 10：連接率對於獲利密度的影響 97圖5. 11：預測誤差對於獲利指標的影響 98圖5. 12：預測誤差對於獲利密度的影響 99表目錄表1. 1：各種新興的網路技術 11表1. 2：傳統電信網路，網路網路和整合型網路特性比較表 12表1. 3：circuit-switching 與 packet-switching 網路特性比較 14表1. 4：UMTS 品質分類及與各項特性 17表1. 5：UMTS Bearer Service Attributes的數值範圍 18表2. 1：各種PHB的服務範例 28表3. 1：BBQ中分層分工架構 47表4. 1：BBQ架構中各種路徑之定義 63表4. 2：BBQ架構中各種PPA的比較 64表4. 3：各階段路徑規劃所需之輸入與輸出參數 69表4. 4：資源分配路徑規劃符號表 71表5. 1：實驗組參數設定及其範圍 83表5. 2：效能評估實驗 86 | zh_TW |
| dc.format.extent | 74023 bytes | - |
| dc.format.extent | 114163 bytes | - |
| dc.format.extent | 117173 bytes | - |
| dc.format.extent | 333976 bytes | - |
| dc.format.extent | 293774 bytes | - |
| dc.format.extent | 3601380 bytes | - |
| dc.format.extent | 582912 bytes | - |
| dc.format.extent | 328292 bytes | - |
| dc.format.extent | 95859 bytes | - |
| dc.format.extent | 109576 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.language.iso | en_US | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0090753026 | en_US |
| dc.subject (關鍵詞) | QoS | en_US |
| dc.subject (關鍵詞) | BBQ | en_US |
| dc.subject (關鍵詞) | Path Planning | en_US |
| dc.title (題名) | 預算法全IP核心網路服務品質管理之路徑規劃 | zh_TW |
| dc.type (資料類型) | thesis | en |
| dc.relation.reference (參考文獻) | [1]3rd Generation Partnership Project, ""Technical Specification Group Services and Systems Aspects: Architecture for an All IP network``, 3GPP TR 23.922 version 1.0.0., October 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [2]Xiao, X., L. -M. Ni, ""Internet QoS: A Big Picture", IEEE Network, 13(2):8-18, March-April 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [3]Miras, D., ""Network QoS Needs of Advanced Internet Applications", Internet2 - QoS Working Group, November 2002. | zh_TW |
| dc.relation.reference (參考文獻) | [4]Pascal Lorenz, ""Quality of service and new architectures for future telecommunications networks", MILCOM 2000 - IEEE Military Communications Conference, no.1, October 2000 pp.695-698. | zh_TW |
| dc.relation.reference (參考文獻) | [5]D. Goderis, S. Van den Bosch, Y. T`Joens, P. Georgatsos, D. Griffin, G. Pavlou, P. Trimintzios, G. Memenios, E. Mykoniati, C. Jacquenet, ""A service-centric IP quality of service architecture for next generation networks", NOMS 2002 - IEEE/IFIP Network Operations and Management Symposium, no.1, April 2002 pp. 139-154. | zh_TW |
| dc.relation.reference (參考文獻) | [6]Mahbubul Alam, Ramjee Prasad, John R. Farserotu, ""Quality of service among IP-based heterogeneous networks", IEEE Personal Communications, no.6, December 2001 pp.18-24. | zh_TW |
| dc.relation.reference (參考文獻) | [7]Vijay K. Garg, Oliver T. W. Yu, "Integrated QoS support in 3G UMTS networks", WCNC 2000 - IEEE Wireless Communications and Networking Conference, no.1, September 2000 pp.1187-1192. | zh_TW |
| dc.relation.reference (參考文獻) | [8]E. Crawley, Editor, L. Berger, S. Berson, ""A Framework for Integrated Services and RSVP over ATM",RFC 2382, August 1998. | zh_TW |
| dc.relation.reference (參考文獻) | [9]D. Black, M. Carlson, E. Davies, Z. Wang, ""An Architecture for Differentiated Services", RFC 2475, December 1998. | zh_TW |
| dc.relation.reference (參考文獻) | [10]Christian Huitema, ""Routing in the Internet", Prentice Hall PTR, 2000, pp.356. | zh_TW |
| dc.relation.reference (參考文獻) | [11]Spiridon Bakiras and Victor O.K. Li, ""Efficient Resource Management for End-to-End QoS Guarantees in DiffServ Networks", IEEE International Conference on Communications, 2002. | zh_TW |
| dc.relation.reference (參考文獻) | [12]Jacobson, V., K. Nichols, K. Poduri, ""An Expedited Forwarding PHB", RFC 2598, June 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [13]Heinanen, J., F. Baker, W. Weiss, and J. Wroclawski, ""Assured Forwarding PHB Group", RFC 2597, June 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [14]Clark, D., W. Fang, ""Explicit Allocation of Best Effort packet Delivery Service", IEEE/ACM Transactions on Networking, 6(4):364-373, August 1998. | zh_TW |
| dc.relation.reference (參考文獻) | [15]P. Trimintzios et al., ""A Management and Control Architecture for Providing IP Differentiated Services in MPLS-based Networks," IEEE Commun. Mag., vol. 39, no. 5, May 2001, pp. 80-88. | zh_TW |
| dc.relation.reference (參考文獻) | [16]P. Trimintzios et al., ""A Policy-Based Quality of Service Management System for IP DiffServ Networks," IEEE Network., vol. 16, no. 2, Mar 2002, pp. 50-56. | zh_TW |
| dc.relation.reference (參考文獻) | [17]Eleni Mykoniati et al., ""Admission Control for Providing QoS in DiffServ IP Networks: The TEQUILA Approach, "" IEEE Commun. Mag. Jan 2003, pp. 38-44. | zh_TW |
| dc.relation.reference (參考文獻) | [18]G. Feng, K. Makki, N. Pissinou, C. Douligeris, "An efficient heuristic for delay-cost-constrained QoS routing, "" IEEE International Conference on Communications, 2001, ICC 2001, vol. 8, pp. 2603-2607. | zh_TW |
| dc.relation.reference (參考文獻) | [19]Q. Ma and P. Steenkiste, ""On path selection for traffic with bandwidth guarantees," In Proceedings of IEEE International Conference on Network Protocols, Atlanta, GA, October 1997. | zh_TW |
| dc.relation.reference (參考文獻) | [20]Turgay Korkmaz, and Marwan Krunz, ""Multi-Constrained Optimal Path Selection," IEEE INFOCOM 2001, pp. 834-843. | zh_TW |
| dc.relation.reference (參考文獻) | [21]S. Floyd, and V. Jacobson, ""Random Early Detection Gateways for Congestion Avoidance``, IEEE/ACM Transactions on Networking, vol. 1, no. 4, August 1993, pp. 397-413. | zh_TW |
| dc.relation.reference (參考文獻) | [22]Nicolas Christin and Jörg Liebeherr, ""A QoS Architecture for Quantitative Service Differentiation ``, IEEE Communications Magazine, June 2003. | zh_TW |
| dc.relation.reference (參考文獻) | [23]A. Demers, S. Keshav and S. Shenker, ""Design and Analysis of a Fair Queueing Algorithm``, Proc. SIGCOMM`89, ACM, September 1989, pp. 1-12. | zh_TW |
| dc.relation.reference (參考文獻) | [24]D. Awduche, J. Malcolm, J. Agogbua, M. O`Dell and J. McManus, ""Requirements for Traffic Engineering Over MPLS``, RFC 2702, September 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [25]D. Ooms, B. Sales, W. Livens, A. Acharya, F. Griffoul and F. Ansari, ""Overview of IP Multicast in a Multi-Protocol Label Switching (MPLS) Environment``, RFC 3553, August 2002. | zh_TW |
| dc.relation.reference (參考文獻) | [26]E. Rosen and Y. Rekhter, ""BGP/MPLS VPN``, RFC 2547, March 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [27]A. S. Tanenbaum, ""Computer Networks, Third Edition``, Prentice Hall, March 1996, pp. 345-366. | zh_TW |
| dc.relation.reference (參考文獻) | [28]Dijkstra, E.W., ""A Note on Two Problems in Connection with Graphs``, Numerische Math, vol. 1, March 1959, pp. 269-271. | zh_TW |
| dc.relation.reference (參考文獻) | [29]C. Hedrick, ""Routing Information Protocol``, RFC 1058, June 1988. | zh_TW |
| dc.relation.reference (參考文獻) | [30]J. Moy, ""OSPF version 2``, RFC 1583, March 1994. | zh_TW |
| dc.relation.reference (參考文獻) | [31]Christophe Beaujean, ""Delay-Based Routing Issues in IP Networks``, contact GRADIENT CR/98/148, May 2000. | zh_TW |
| dc.relation.reference (參考文獻) | [32]Douglas S.Reeves and Hussein F. Salama, ""A Distributed Algorithm for Delay-Constrained Unicast Routing``, IEEE Transaction on Network, April 2000. | zh_TW |
| dc.relation.reference (參考文獻) | [33]R. Braden, L. Zhang, S. Berson, S. Herzog and S. Jamin, ""Resource Reservation Protocol (RSVP) – Version 1 Functional Specification``, RFC 2205, September 1997. | zh_TW |
| dc.relation.reference (參考文獻) | [34]K. Chan, R. Sahita, S. Hahn and K. McCloghrie, ""Differentiated Services Quality of Service Policy Information Base ``, RFC 3317, March 2003. | zh_TW |
| dc.relation.reference (參考文獻) | [35]Bill Goodman, ""Internet Telephony and Modem Delay``, IEEE Network, May 1999, pp. 8-16. | zh_TW |
| dc.relation.reference (參考文獻) | [36]J. Garcia-Luna-Aceves and J. Behrens, ""Distributed scalable routing based on vectors of link states``, IEEE J. Select on Communication, October 1995. | zh_TW |
| dc.relation.reference (參考文獻) | [37]Jon Postel, ""Internet Protocol``, RFC 791, September 1981. | zh_TW |
| dc.relation.reference (參考文獻) | [38]Mark A. Sportack, ""IP Routing Fundamentals``, Cisco ISBN: I-57870-071-x, May 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [39]R. Wideyono, ""The Design and Evaluation of Routing Algorithms for Real-Time Channels``, International Computer Science Institute, Univ. of California at Berkeley, Tech Rep. ISCI TR-94-024, June 1994. | zh_TW |
| dc.relation.reference (參考文獻) | [40]S. Rampal and D. Reeves, ""An evaluation of routing and admission control algorithms for multimedia traffic``, Proc. of the 5th IFIP Conf. on High Performance Networks, October 1995. | zh_TW |
| dc.relation.reference (參考文獻) | [41]S. Lavenberg, ""Mean Value Analysis of Closed Multichain Queuing Networks``, Journal of the Association for Computing Machinery, vol. 27, no. 2, April 1980, pp. 313-322. | zh_TW |
| dc.relation.reference (參考文獻) | [42]Z. Wang and J. Crowcroft, ""Quality of Service Routing for Supporting Multimedia Applications``, IEEE Select on Communication, September 1996. | zh_TW |
