成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	邱基峰 Chiu, Ji-Feng
論文名稱：	具避免侵占及預測流量之差異性服務流量工程演算法 Preemption Avoidance and Traffic Prediction Algorithms for DiffServ-aware Traffic Engineering
指導教授：	黃文祥 Hwang, Wen-Shyang 謝錫堃 Shieh, Ce-Kunen
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2003
畢業學年度：	91
語文別：	英文
論文頁數：	89
中文關鍵詞：	多重協定標籤交換、流量工程、差異性服務、動態頻寬分配、侵占、流量預測、服務品質
外文關鍵詞：	DiffServ, Dynamic Bandwidth Allocation, Preemption, Traffic Prediction, QoS, MPLS, Traffic Engineering
相關次數：	點閱：180 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

差異性服務流量工程主要包括兩個項目：差異性服務及流量工程。差異性服務將流量分類來改善擴充性。流量工程原主要目的為利用強制性路由來改善傳統路由方法，此種路由方法之路由表不僅儲存網路拓撲還包括資源使用情形及服務品質的需求。因此，流量工程需要一有效資源管理機制，其利用資源相關資訊於邊界路由器上可容易的保留資源以滿足所需服務品質。本論文將設計於差異性服務流量工程架構上設計一資源管理機制。
事實上，保障端點對端點之服務品質及資源使用最佳化即是資源管理的關鍵。這把我們帶向如何有效地管理資源來滿足服務品質，此問題於差異性服務流量工程當中必須解決底下兩個問題：標籤交換路徑之侵占與資源分配。本論文將先提出一個具自動設定服務品質之參數以提供標籤交換路徑的資源分配之方法，同時提出一具侵占避免以滿足服務品質及可分散流量達到負載平衡之演算法。

The DiffServ-aware traffic engineering incorporates two ideas: DiffServ and traffic engineering. The DiffServ improves the network scalability through aggregating a large number of traffic flows into a set of traffic classes. The traffic engineering primarily deals with constraint-based routing that routing tables are now built not only on the topology basis but also on the basis of resource availability and QoS requirements. Obviously, the traffic engineering requires a resource management mechanism at each network node to reserve resources for satisfying flow QoS requirements, and to flood network information with resource availability. Designing a resource management scheme for supporting the DiffServ-aware traffic engineering framework is what we focus on in this thesis.
Resource management is, in fact, the key to achieve the end-to-end quantitative QoS guarantees and the optimization utilization of transmission resources. These drive us to the topic about how to manage resource to meet QoS requirements efficiently. The question resolves itself into the following two points for the DiffServ-aware traffic engineering in a MPLS network. It comprises of LSPs (Label Switching Paths) preemption and capacity allocation. We first point out the automatical setting of QoS parameters to allocate LSP capacity and how to avoid the preemption to achieve QoS guarantees and then discuss the distributing of traffic to achieve load balancing in this thesis.

ABSTRACT......................................................................i
ACKNOWLEDGMENTS..............................................................iv
CONTENTS.....................................................................vi
LIST OF TABLES...............................................................ix
LIST OF FIGURES...............................................................x
CHAPTER 1 INTRODUCTION......................................................1-1
1 DiffServ-aware Traffic Engineering (DS-TE)..............................1-1
2 Thesis Motivation.......................................................1-3
3 Contributions...........................................................1-5
4 Organization of this Thesis.............................................1-6
CHAPTER 2 BACKGROUND AND RELATED WORK.......................................2-1
1 Network Quality of Service..............................................2-1
1.1 The Integrated Services (IntServ) Model...............................2-1
1.2 The Differentiated Services (DiffServ) Model..........................2-3
2 MPLS....................................................................2-4
2.1 MPLS Fundamentals.....................................................2-4
2.2 MPLS Signal Protocols.................................................2-6
2.2.1 Label Distribution Protocol (LDP)...................................2-7
2.2.2 Constraint-bsaed Routed LDP (CR-LDP)................................2-8
2.2.3 RSVP-TE.............................................................2-9
2.3 MPLS and DiffServ.....................................................2-11
2.4 Traffic Engineering...................................................2-12
3 Traffic Engineering Algorithms..........................................2-13
3.1 Shortest Path (SP) and Minimum Hops (MH)..............................2-14
3.2 Widest-Shortest Path (WSP)............................................2-14
3.3 Shortest-Widest Path (SWP)............................................2-14
4 LSPs Capacity Allocation................................................2-15
5 Summary.................................................................2-16
CHAPTER 3 ENHANCING THE DIFFSERV-AWARE TRAFFIC ENGINEERING FRAMEWORK......3-1
1 System Model and Problem Definition.....................................3-1
2 Improving the DiffServ-aware Traffic Engineering Model..................3-3
2.1 QoS Mapping Controller (QMC)..........................................3-5
2.2 Policy-Based Traffic Engineering (PBTE)...............................3-7
3 Evaluation of the DiffServ-aware Traffic Engineering Model..............3-9
3.1 Cost Efficiency.......................................................3-19
3.2 Robustness............................................................3-10
4 Summary.................................................................3-11
CHAPTER 4 LSPs CAPACITY AUTO-ALLOCATOR FOR QMC.............................4-1
1 LSPs Capacity Allocation................................................4-1
2 LSPs Capacity Auto-Allocator............................................4-2
2.1 Differential-based Prediction Method..................................4-3
2.1.1 Function Approximation..............................................4-4
2.1.2 Fourth-order Adams Predictor-Corrector Method.......................4-5
2.2 Evaluation............................................................4-6
3 Performance Studies.....................................................4-7
3.1 Bandwidth Distribution................................................4-8
3.2 Error Distribution....................................................4-11
3.3 Link Utilization......................................................4-12
3.4 Packet Loss Rate......................................................4-14
4 Discussions.............................................................4-15
5 Summary.................................................................4-16
CHAPTER 5 PREEMPTION-AWARE TRAFFIC ENGINEERING ALGORITHM....................5-1
1 LSPs Preemption.........................................................5-1
2 Preempted Probability Algorithm.........................................5-2
3 Simulation Results......................................................5-5
3.1 Simulation Configuration..............................................5-5
3.2 Preemption Avoidance..................................................5-7
3.2.1 Numbers of Preemption...............................................5-8
3.2.2 Blocking Probability................................................5-8
3.3 Load Balancing........................................................5-9
4 Discussions.............................................................5-12
5 Summary.................................................................5-11
CHAPTER 6 CONCLUSIONS AND FUTURE WORK......................................6-1
1 Conclusions.............................................................6-1
2 Future Work.............................................................6-2
REFERENCES..................................................................R-1
                                    

[1] Braden, R., Clark, D. and Shenker, S., “Integrated Services in the Internet Architecture: an Overview”, Internet RFC 1633, June 1994
[2] J. Wroclawski, “Specification of the Controlled-Load Network Element Service”, RFC 2211, Sept. 1997
[3] S. Shenker, C. Partridge and R. Guerin, “Specification of Guaranteed Quality of Service”, RFC 2212, Sept. 1997
[4] R.Barden, Ed, “Resource ReSerVation Protocol（RSVP）-Version 1 Functional Specification,“ Internet RFC 2205, September 1997.
[5] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang and W. Weiss, “An Architecture for Differentiated Services,” RFC 2475, December 1998.
[6] K. Nichols, S. Blake, F. Baker and D. Black, “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers,” RFC 2474, December 1998.
[7] Heinanen, J., Baker, F., Weiss, W. and J. Wroclawski, “Assured Forwarding PHB Group”, RFC 2597, June 1999.
[8] Jacobson, V., Nichols, K. and K. Poduri, “An Expedited Forwarding PHB”, RFC 2598, June 1999.
[9] F. L. Faucheur, T. D. Nadeau, A. Chiu, W. Townsend, et al, “Requirements for support of DiffServ-aware MPLS traffic engineering”, IETF Internet drafts, November 2000.
[10] F. L. Faucheur, T. D. Nadeau, A. Chiu, W. Townsend, et al, “Extensions to RSVP-TE and CR-LDP for support of DiffServ-aware MPLS traffic engineering”, IETF Internet drafts, November 2000.
[11] E.Rosen, A.Viswanathan, and R. Callon, “Multiprotocol Label Switching Architecture”, RFC 3031, January 2001
[12] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell and J. McManus, “Requirements for Traffic Engineering Over MPLS”, RFC 2702, September 1999
[13] B. Braden et al., “Recommendation on Queue Management and Congestion Avoidance in the Internet”, RFC 2309, Apr. 1998
[14] Li T., Rekhter Y., “A Provider Architecture for Differentiated Services and Traffic Engineering (PASTE)”, RFC 2430, October 1998
[15] P. Ashwood-Smith, B.Jamoussi, D.Fedyk, and D.Skalecki, “Improving Topology Data Base Accuracy with LSP Feedback in CR-LDP”, draft-ietf-mpls-te-feed-05.txt, Nov 2002
[16] Y. Ohba, Y. Katsube, E. Rosen, P. Doolan, “MPLS Loop Prevention Mechanism”, RFC 3063, Feb. 2001.
[17] F. Le Faucheur, L. Wu, B. Davie, S. Davari, P. Vaananen, R. Krishnan, P. Cheval, J. Heinanen, “MPLS Support of Differentiated Services”, RFC 3270, May. 2002.
[18] E. Rosen, D. Tappan, G. Fedorkow, Y. Rekhter, D. Farinacci, T. Li, A. Conta, “MPLS Label Stack Encoding”, RFC 3032, Jan. 2001.
[19] L. Andersson, P. Doolan, N. Feldman, A. Fredette, B. Thomas, “LDP Specification”, RFC 3036, Jan. 2001.
[20] D. Awduche, L. Berger, D. Gan, T. Li, V. Srinivasan, G. Swallow, “RSVP-TE：Extensions to RSVP for LSP Tunnels”, RFC 3209, Dec. 2001.
[21] B. Jamoussi, L. Andersson, R. Callon, R. Dantu, L. Wu, P. Doolan, T. Worster, N. Feldman, A. Fredette, M. Girish, E. Gray, J. Heinanen, T. Kilty, A. Malis, “Constraint-Based LSP Setup using LDP”, RFC 3212, Jan. 2002.
[22] J. Ash, M. Girish, E. Gray, B. Jamoussi, G. Wright, “Applicability Statement for CR-LDP”, RFC 3213, Jan. 2002.
[23] J. Ash, Y. Lee, P. Ashwood-Smith, B. Jamoussi, D. Fedyk, D. Skalecki, L. Li, “LSP Modification Using CR-LDP”, Internet-Draft RFC 3214, Jan. 2002.
[24] C. Villamizar, “OSPF Optimized Multipath (OSPF-OMP)”, Internet draft, <draftietf- ospf-omp-02.txt>, Feb. 2000.
[25] H. Smit and T. Li, “IS-IS extensions for Traffic Engineering”, Internet draft, <draft-ietf-isis-traffic-01.txt>, May 1999.
[26] N. Shen and H. Smit, “Calculating IGP routes over Traffic Engineering LSPs”, Internet draft <draft-hsmit-mpls-igp-spf-00.txt>, June 1999.
[27] F. L. Faucheur, T. D. Nadeau, A. Chiu, W. Townsend, et al, “Requirements for support of DiffServ-aware MPLS traffic engineering”, IETF Internet drafts, November 2000.
[28] F. L. Faucheur, T. D. Nadeau, A. Chiu, W. Townsend, et al, “Extensions to RSVP-TE and CR-LDP for support of DiffServ-aware MPLS traffic engineering”, IETF Internet drafts, November 2000.
[29] Y. Ohba, “Issues on Loop Prevention in MPLS Networks”, IEEE Communications Magazine, Vol. 37, No. 12, Dec. 1999, pp. 64 – 68.
[30] G. Swallow, “MPLS Advantages for Traffic Engineering”, IEEE Communications Magazine, Vol. 37, No. 12, Dec. 1999, pp. 54 – 57.
[31] G. Armitage, “MPLS：the magic behind the myths”, IEEE Communications Magazine, Vol. 38, No. 1, Jan. 2000, pp. 124 – 131.
[32] T.Li, “MPLS and the evolving Internet architecture”, IEEE Communications Magazine, Volume: 37 Issue: 12, pp.38-41, Dec. 1999.
[33] X.Xiao, A.Hannan, B.Bailey, and L.M.Ni, “Traffic Engineering with MPLS in the Internet”, IEEE Network, Volume: 14 Issue: 2 pp.28-33, March-April 2000
[34] D.O.Awduche, “MPLS and traffic engineering in IP networks”, IEEE Communications Magazine, Volume: 37 Issue: 12 pp.42-47, Dec. 1999
[35] S. Chen and K. Nahrstedt, “An Overview of Quality-of-Service Routing for the Next Generation High-Speed Networks: Problems and Solutions”, IEEE Network Magazine, Special Issue on Transmission and Distribution of Digital Video, 1998.
[36] E. Dinan, D. O. Awduche, B. Jabbari, “Analytical framework for dynamic traffic partitioning in MPLS networks”, IEEE International Conference on Communications,( ICC 2000), Vol. 3, pp. 1604 – 1608.
[37] S. Suri, M. Waldvogel, and P. Warkhede. “Profile-based routing: A new framework for MPLS traffic engineering”, Washington University Computer Science Technical Report WUCS-00-21, July 20001.
[38] Shyam Subramanian and Venkatesan Muthukumar, “Alternative Path Routing Algorithm for Traffic Engineering” http://www.ee.unlv.edu/~venkim/opnet/icseng02iPaper.pdf
[39] P.Aukia, M.Kodialam, P.V.N.Koppol, T.V.Lakshman, H.Sarin, B.Suter,, “RATES: a server for MPLS traffic engineering”, IEEE Network , Volume: 14 Issue: 2 , Mar/Apr 2000 Page(s): 34 -41
[40] M. Kodialam, T.V. Lakshman, “Minimum Interference Routing with Applications to MPLS Traffic Engineering”, INFOCOM 2000. Proceedings. IEEE, Vol. 2, pp. 884 – 893.
[41] A. Elwalid,Jin Cheng, S. Low, I. Widjaja, “MATE：MPLS adaptive traffic engineering”, INFOCOM 2001. Proceedings. IEEE, Vol. 3, pp. 1300 – 1309.
[42] M.K. Girish, Bei Zhou, Jian-Qiang Hu, “Formulation of the Traffic Engineering Problems in MPLS Based IP Networks”, Fifth IEEE Symposium on Computers and Communications, ISCC2000, Proceedings. IEEE, pp. 214 – 219.
[43] N. Rouhana, E. Horlait, “Differentiated services and integrated services use of MPLS”, IEEE Symposium on Computers and Communications ( ISCC 2000), Proceedings. IEEE, pp. 194 – 199.
[44] Ji-young Lim, Ki-Joon Chae, “Differentiated Link Based QoS Routing Algorithms for Multimedia Traffic in MPLS Networks”, 15th International Conference on Information Networking, (ICOIN 2001), Proceedings, pp. 587 – 592.
[45] Q.Ma and P.Steenkiste, “On path selection for traffic with bandwidth guarantees”, IEEE ICNP, pp.191–202, 1997.
[46] T.Saad, T.Yang, D.Makrakis and V.Groza, “DiffServ-enabled adaptive traffic engineering over MPLS”, ICII 2001, Volume: 2pp.128–133, 2001
[47] Z.Wang and J.Crowcroft, “Quality-of-service routing for supporting multimedia applications”, IEEE JSAC, Volume: 14 Issue: 7 pp.1228–1234, Sept. 1996
[48] B.Kim, W.Chun and J.Yoo, “Constraint-based LSP setup by message reversing of CR-LDP”, ICOIN 2001, pp.875–880, 2001, 2001
[49] G.Banerjee and D.Sidhu,” Label Switched Path Restoration under Two Random failures”, GLOBECOM 2001, Volume: 1pp.30-34, 2001
[50] J.C.de Oliveira, C.Scoglio, I.F.Akyildiz and G.Uhl, “A New Preemption Policy for DiffServ-Aware Traffic Engineering to Minimize Rerouting”, INFOCOM 2002, June 2002.
[51] T.Anjali, C.Scoglio, J.C. de Oliveira, I.F.Akyildiz, and G.Uhl, “Optimal Policy for Label Switched Path Set-up in MPLS Networks”, Computer Networks, Volume: 39 Issue: 2 pp.165-183, June 2002
[52] M.Moh, B.Wei and J.H Zhu, “Supporting differentiated services with per-class traffic engineering in MPLS”, International Conference on Computer Communications and Networks 2001, pp.354-360, 2001
[53] A. Adas, Supporting real-time VBR video using dynamic reservation based on linear prediction, in: Proceedings of IEEE INFOCOM_96, San Francisco, USA, March 1996, pp. 1476–1483.
[54] H. Zhang, E.W. Knightly, RED-VBR: A renegotiation based approach to support delay sensitive VBR video, Multimedia Systems 5 (1997) 164–176.
[55] C.N. Chuah, L. Subramanian, R.H. Katz, A.D. Joseph, QoS provisioning using a clearing house architecture, in: Proceedings of 8th International Workshop on Quality of Service, Pittsburgh, USA, June 2000.
[56] A. Terzis, L. Wang, J. Ogawa, L. Zhang, A two-tier resource management model for the Internet, in: Proceedings of IEEE GLOBECOM_99, Rio de Janeiro, Brazil, December 1999, pp. 1779–1791.
[57] White Paper, Cisco MPLS AutoBandwidth Allocator, http://www.cisco.com/warp/public/cc/pd/iosw/prodlit/ mpatb_wp.htm, June 2001.
[58] E. W. Knightly and H. Zhang, “D-BIND: An accurate traffic model for providing QoS guarantees to VBR traffic”, IEEE/ACM Trans. on Networking, vol. 5, no. 2, pp. 219-231, 1997.
[59] P. Bocheck and S. F. Chang, “Content-based VBR traffic modeling and its application to dynamic network resource allocation”, Tech. Rep. 48c-98-20, Columbia University, 1998.
[60] M. Wu, R. Joyce, and S. Y. Kung, “Dynamic resource allocation via video content and short-term traffic statistics”, to be presented in IEEE Int. Conf. on Image Processing, 2000.
[61] S. Chong, S. Li, and J. Ghosh, “Predictive dynamic bandwidth allocation for efficient transport of real-time VBR video over ATM,” IEEE. JSAC., vol. 13, no. 1, pp. 12–23, 1995.
[62] Anjali, T., Scoglio, C., and Uhl, G., “A New Scheme for Traffic Estimation and Resource Allocation for Bandwidth Brokers”, Computer Networks, 2003.
[63] Akyildiz, I.F., Anjali, T., Chen, L., de Oliveira, J.C., Scoglio, C., Sciuto, A., Smith, J.A., and Uhl, G., “A New Traffic Engineering Manager for DiffServ/MPLS Networks: Design and Implementation on an IP QoS Testbed”, Computer Communications, 2003.
[64] de Oliveira, J.C., Scoglio, C., Akyildiz, I.F., Uhl, G., and Smith, J.A., “A New Topology-Aware LSP Preemption Policy for DiffServ-MPLS Networks”, IEEE NETWORKS 2002, August 2002.
[65] Anjali, T., Scoglio, C., de Oliveira, J.C., Chen, L., Akyildiz, I.F., and Smith, J.A., “A New Path Selection Algorithm for MPLS Networks Based on Available Bandwidth Estimation”, QofIS 2002, October 2002.
[66] LBL, Xerox PARC, UCB, and USC/ISI, “Network Simulator – ns(version 2)”, http://www.isi.edu/nsnam/ns/
[67] Gaeil Ahn, Woojik Chun, “Design and Implementation of MPLS network Simulator Supporting LDP and CR-LDP”, IEEE International Conference on Networks,( ICOIN 2000), Proceedings, pp. 441 – 446.
[68] Gaeil Ahn, Woojik Chun, “Design and implementation of MPLS network simulator (MNS) supporting QoS”, 15th International Conference on Information Networking,(ICOIN 2001), Proceedings, pp. 694 – 699.
[69] LBL, Xerox PARC, UCB, and USC/ISI, “Network Simulator：Contributed Code”, http://www.isi.edu/nsnam/ns/ns-contributed.html
[70] LBL, Xerox PARC, UCB, and USC/ISI, “Research using NS”, http://www.isi.edu/nsnam/ns/ns-research.html
[71] J.F Chiu, Y.B Miao, C.W Lo, Z.P Huang, W.S Hwang and C.K Shieh, “A New Preemption Avoidance and Load balancing Policy for Traffic Engineering in MPLS Networks”, IASTED International Conference on Communications and Computer Networks (CCN2002), December 2002, pp. 234-239.
[72] J.F Chiu, Z.P Huang, C.W Lo, W.S Hwang and C.K Shieh, “Supporting End-to End QoS in DiffServ/MPLS Networks”, 10th International Conference on Telecommunications (ICT2003), February 2003, pp. 261-266.
[73] U. Black, “MPLS and Label Switching Networks”, Prentice Hall PTR, 2001
[74] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, “Network flows”, Prentice Hall, 1993.
[75] Advanced Internet Laboratory, http://www.ail.gmu.edu/
[76] http://www.cisco.com/warp/public/732/Tech/mpls/
[77] http://www.upperside.fr/
[78] http://www.dataconnection.com/mpls/default.htm
[79] http://www.mplsforum.org/
[80] http://www-tkn.ee.tu-berlin.de/~fitzek/TRACE/trace.html

校內：立即公開
校外：2003-07-04公開

簡易檢索 / 詳目顯示

相關論文