對許多服務而言，未來有線及無線網路將走向共享網際網路通訊協定為基礎的 (IP-based) 核心網路，然而，目前的網路技術卻未臻完善，使得有些問題無可避免會阻礙理想的達成，例如，我們都知道網際網路通訊協定網路彼此以路由器互連，但是由於路由器必須使用外在閘道通訊協定 (Border Gateway Protocol, BGP) 聯繫，而且使用耗時且點跨點 (hop-by-hop) 的處理程序，導致實際的路由可能很難預測，所以多協定標籤交換技術 (Multi-Protocol Label Switching, MPLS) 或廣義多協定標籤交換技術 (Gen-eralized Multi-Protocol Label Switching, GMPLS) 為用來改善此問題的商業化標籤交換技術。此外，傳統網際網路通訊協定網路為人所詬病的交通流量管理 (traffic engineering) 能力，則可藉由廣義多協定標籤交換技術來改善，因為此技術引入限制基礎的 (constraint-based) 路由方式而具有強大的交通流量管理能力；另一方面，傳統網際網路通訊協定網路缺乏服務品質保證的機制，能藉由資源預約通訊協定 (Resource ReSerVation Protocol, RSVP) 和封包排程器的幫助，以提昇服務品質的保證。因此，發展多協定標籤交換技術或廣義多協定標籤交換技術之評估模型及效能評估方式是刻不容緩。
本論文探討的內容包括四個主題：第一個主題是提供標籤資源充裕下多協定標籤交換技術或廣義多協定標籤交換技術之效能評估模型，其交通流只能通過自己的標籤交換路徑 (Label Switched Path, LSP)。第二個主題的模型為第一個主題的擴充，此模型是用來建構多個交通流競爭有限標籤的情況。第三個主題模型的交通流在獲得標籤交換路徑前，可先通過預定路徑 (default path)。最後一個主題，我們將Generalized Processor Sharing (GPS)-based排程演算法加入多協定標籤交換技術或廣義多協定標籤交換技術中，使得它能提供服務品質的保證。
針對第一個主題，我們提出標籤資源充裕下多協定標籤交換技術或廣義多協定標籤交換技術之排隊模型，這個模型原始標籤設定策略 (la-bel-setup policy) 的啟動是依據累積在交換器暫存器的封包量達到觸發臨界值，但由於交通流在獲得標籤交換路徑前是先累積在交換器暫存器中，因而容易引發傳輸暫停 (timeout) 的問題，於是我們嘗試將標籤設定策略的啟動修改成累積在交換器暫存器的封包量達到觸發臨界值或標籤設定計時器 (label-setup timer) 截止時，此模型的標籤解除策略 (label-release policy) 便是由可調整的標籤解除計時器 (label-release timer) 所控制。依據此模型，我們可清楚觀察到標籤設定策略及標籤解除策略如何影響多協定標籤交換技術或廣義多協定標籤交換技術之效能。
第二個主題模型為第一個主題模型的延伸，適用於標籤資源有限時的環境，透過此模型，可明確觀察到標籤設定策略及標籤解除策略如何影響有限標籤下多協定標籤交換技術或廣義多協定標籤交換技術之效能。
在第三個主題的模型中，交通流取得標籤交換路徑前，我們並未中斷其在預定路經的通訊，此模型的標籤設定策略是依據累積在預定路徑的封包量達到觸發臨界值，而標籤解除策略與前兩個主題相同，雖然此模型可使用預定路徑及標籤交換路徑，卻引發封包失序 (out-of-sequence) 的問題，因此我們加上強制切換裝置 (flush mechanism)，以改善此現象。
除了上述三種可提高效能的模型，多協定標籤交換技術或廣義多協定標籤交換技術服務品質的保證，也是我們所欲達成的目標，因此，在本論文的最後一個主題中，我們發展具有GPS-based排程器的多協定標籤交換技術或廣義多協定標籤交換技術，標籤資源有限及充裕的情況都涵蓋在此模型中，藉由此模型，我們便能依據可容忍的延遲上限及可用的暫存器，選擇適當的標籤數。值得一提的是，此模型也可應用於以廣義多協定標籤交換技術為基礎的虛擬私有網路 (Virtual Private Network, VPN)。

It has been expected that both wireline and wireless networks will share the same Internet Protocol (IP)-based core networks for many services. However, some impediments defer the realization of this vision. For instance, IP networks interconnect with each other via routers running Border Gateway Protocol (BGP) routing protocols. As a result, the routing decision of most backbone routers at present is based on time-consuming hop-by-hop process and the actual route may be hard to predict. Multi-Protocol Label Switching (MPLS) or its extension Generalized Multi-Protocol Label Switching (GMPLS) is a commercial label-switching technology that designs to overcome this predicament. Furthermore, weak traffic engineering capability and lack of Quality-of-Service (QoS)
guaranteed mechanisms in traditional IP networks can be improved
with the use of MPLS/GMPLS since MPLS introduces constraint-based routing to provide powerful traffic engineering. In addition, with the help of mechanisms in differentiated services, such as Resource ReSerVation Protocol (RSVP) and packet schedulers, it is possible for MPLS to provide QoS in IP networks. Consequently, performance models and performance prediction methods in MPLS/GMPLS networks have become increasingly important.
The topics studied in this dissertation include four parts. The first part is to provide a performance evaluation model for an MPLS/GMPLS switch with sufficient label resources, where data
packets can only traverse over its Label Switched Path (LSP). The second part is similar to the first part, except that competing streams must struggle for labels. The model in the third part permits data packets to pass through the default path, which is determined by traditional IP routing protocol, before ascertaining an LSP which is a fast route. Finally, we incorporate a Generalized Processor Sharing (GPS)-based scheduler to an MPLS/GMPLS switch so that it can accommodate guaranteed QoS, such as maximum delay.
For the first topic, we propose a queueing model of the MPLS/GMPLS switch under different label-setup and release policies, supporting sufficient number of labels. The original label-setup policy is invoked when the number of accumulated packets in the switch buffer exceeds a triggering threshold. However, this policy may cause a timeout problem because traffic deposits in the switch buffer before an appropriate LSP has been found. The label-setup policy is modified such that either if the accumulated packets in the switch buffer have exceeded the triggering threshold or if the label-setup timer has expired, and then the GMPLS controller shall set up a label. The label-release policy depends on an adjustable
timer. We can clearly comprehend how both the label-setup policy
and label-release policy affect the performance of an MPLS/GMPLS
switch according to this model.
The second topic extends from the first model and portrays for the situation with limited number of labels. From this proposed model, one can easily observe the competition of multiple IP flows for limited number of labels and how the label-setup policy and the label-release policy affect the system performance.
In the third topic, relatively, we do not suspend the
communication of data packets in the default path. The label-setup policy under this model is detonated when the accumulated packets in the default path buffer reach a triggering threshold. The label-release policy is the same as the above two models. Although this model can utilize both the default path and the LSP, the price is an out-of-sequence problem. To resolve this problem, we incorporate a flush mechanism into the proposed model.
To cope with the issues of accommodating QoS sensitive services in MPLS/GMPLS networks, in the final topic of this dissertation we develop an MPLS/GMPLS switch equipped with a GPS-based scheduler. Both the operations with sufficient and limited number of labels are covered. Via this model, one can make an appropriate choice for the number of labels depending on the allowable delay and the available buffer size. The application of the proposed model includes MPLS-VPN (Virtual Private Network) services.

Cover
Abstract
Contents
List of Tables
List of Figures
1 Introduction
1.1 Evolution of IP Core Network Architecture
1.2 Reviews of Packet Scheduling Algorithms and Label Switching Technologies

[1] R. Berezdivn, R. Breinig, R. Topp, and Raytheon,“Next-Generation Wireless Communications Concepts and Technologies,”IEEE Commun. Mag., pp. 108--116, March 2002.
[2] J. D. Vriendt, P. Laine, C. Lerouge, and X. Xu,“Mobile Network Evolution: A Revolution on the Move,”IEEE Commun. Mag., pp. 104--111, April 2002.
[3] R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective, Morgan Kaufmann, 1998.
[4] C. A. Brackett,“Dense Wavelendth Division Multiplexing Networks: PRinciples and Applications,”IEEE J. Select. Areas Commun., vol. 8, no. 6, pp. 948--964, Aug. 1990.
[5] Y. Rekhter, et. al.,“Cisco Systems' Tag Switching Architecture Overview,” RFC 2105, Cisco System, Inc., Feb. 1997.
[6] Y. Katsube, K. Nagami., and H. Esaki,“Toshiba's Router Architecture Extensions for ATM: Overview,”RFC 2098, Toshiba R&D Center, Feb. 1997.
[7] P. Newman, T. Lyon, and G. Minshall,“Flow labeled IP: Connectionless ATM under IP,”INFOCOM'96, pp. 1251--1266, San Francisco, CA.
[8] P. Newman, et. al.,“IP Switching and Gigabit Routers,”IEEE Commun., Mag., pp. 64--69, Jan., 1997.
[9] P. Newman, G. Minshall, and T. L. Lyon,“IP Switching: ATM under IP,” IEEE/ACM Trans. Networking, vol. 6, no. 2, pp. 117--129, Aug. 1998.
[10] A. Viswanathan, et al.,“ARIS: Aggregate Route-Based IP Switching,”IETF Internet draft-viswanathan-aris-overview-00.txt, March 1997.
[11] E. Rosen, A. Viswanathan, and R. Callon,“Multiprotocol Label Switching Ar-chitecture,”RFC 3031, Jan. 2001.
[12] E. Rosen, et. al.,“MPLS Label Stack Encoding,”RFC 3032, Jan. 2001.
[13] A. Conta, P. Doolan, Ennovate, and A. Malis,“Use of Label Switching on Frame Relay Networks Specification,”RFC 3034, Jan. 2001.
[14] B. Davie, et. al.,“MPLS using LDP and ATM VC Switching,”RFC 3035, Jan. 2001.
[15] Y. Ohba, Y. Katsube, E. Rosen, and P. Doolan,“MPLS Loop Prevention Mecha-nism,”RFC 3063, Feb. 2001.
[16] E. Rosen and Y. Rekhter,“BGP/MPLS VPNs,”RFC 2547, March 1999.
[17] K. Muthukrishnan and A. Malis,“A Core MPLS IP VPN Architecture,”RFC 2917, Sept. 2000.
[18] D. Awduche, et al.,“Requirements for Traffic Engineering over MPLS,”RFC 2702, Sept. 1999.
[19] Available at Cisco's Web Page, http://www.cisco.com.
[20] Available at Ericsson's Web Page, http://www.ericsson.com.
[21] Available at Juniper's Web Page, http://www.juniper.net.
[22] Available at Lucent's Web Page, http://www.lucent.com.
[23] Available at Nortelnetwork's Web Page, http://www.nortelnetworks.com.
[24] C. Qiao and S. Buffalo,“Labeled Optical Burst Switching for IP-over-WDM Integration,”IEEE Commun. Mag., pp. 104--114, Sept. 2000.
[25] H. Zhong,“Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks, Proceedings of IEEE, vol. 83, no. 10, pp. 1374--1396, Oct. 1995.
[26] A. K. Parekh and R. G. Gallager,“A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,” IEEE/ACM Trans. on Networking, vol. 1, no. 3, pp. 344--357, June 1993.
[27] A. Demers, S. Keshav, and S. Shenker,“Analysis and Simulation of a Fair Queueing Algorithm,”Proc. ACM SIGCOMM '89, pp. 1--12, 1989.
[28] J. C. R. Bennett and H. Zhang,“WF$^2$Q: Worst-Case Fair weighted Fair Queueing,”Proc. IEEE INFOCOM '96, San Francisco, USA, pp. 120--128, Apr. 1996.
[29] S. J. Golestani,“A Self-Clocked Fair Queueing Scheme for Broadband Applica-tions,”Proc. IEEE INFOCOM '94, Toronto, Canada, pp. 636--646, June 1994.
[30] L. Andersson, P. Doolan, N. Feldman, A. Fredette, and B. Thomas,“LDP Speci-fication,”RFC 3036, Jan. 2001.
[31] Y. Rekhter and T. Li,“A Border Gateway Protocol 4 (BGP-4),”RFC 1771, March 1995.
[32] R. Braden, L. Zhang, S. Berson, S. Herzog, S. Jamin, and T. Li,“Resource ReS-erVation Protocol (RSVP)--Version 1 Functional Specification,”RFC 2205, Sept. 1997.
[33] D. Awduche and Y. Rekhter,“Multiprotocol Lambda Switching: Combining MPLS Traffic Engineering Control with Optical Crossconnects,”IEEE Commun. Mag., pp. 111--116, March 2001.
[34] P. Ashwood-Smith, et al.,“Generalized Multi-Protocol Label Switching (GMPLS) Architecture,”IETF Internet draft-ietf-ccamp-gmpls-architecture-00.txt, June 2001, work in progress.
[35] A. Banerjee, J. Drake, J. P. Lang, B. Turner, K. Kompella, and Y. Rekhter, “Generalized Multiprotocol Label Switching: An Overview of Routing and Man-agement Enhancements,”IEEE Commun. Mag., pp. 2--8, Jan. 2001.
[36] A. Banerjee, et al.,“Generalized Multiprotocol Label Switching: An Overview of Signaling Enhancements and Recovery Technologies,”IEEE Commun. Mag., pp. 144--151, July 2001.
[37] Z. Niu, Y. Takahashi, and N. Endo,“Performance Evaluation of SVC-Based IP-Over-ATM Networks,”IEICE Trans. Commun., vol. E81-B, no. 5, pp. 948--957, May 1998.
[38] Z. Niu and Y. Takahashi,“An Extented Queueing Model for SVC-Based IP-Over-ATM Networks and its Analysis,”IEEE GLOBECOM'98, pp. 1950--1955, Sydney, Australia.
[39] Z. Niu and Y. Takahashi,“A Finite-Capacity Queue with Exhaustive Vaca-tion/Close-Down/Setup Times and Markovian Arrival Processes,”Queueing Systems 31, pp. 1--23, 1999.
[40] N. Endo, A. Sawada, and Z. Niu,“The Effect of Burst Duration of Input Traffic in SVC-based IP-over-ATM Networks,”11th ITC Specialist Seminar, pp. 76--81, Yokohama, Japan, 1999.
[41] J. Zheng and V. O. K. Li,“Performance Model for IP Switch,”IEE Electronics Letters, vol. 34, no. 21, pp. 2010--2012, Oct. 1998.
[42] S. Nakazawa, K. Kawahara, S. Yamaguchi, and Y. OIE,“Performance Com-parasion with Layer 3 Switches in Case of Flow-And Topology-Driven Connection Setup,”IEEE GLOBECOM'99, pp. 79--86, Rio de Janeiro, Brazil.
[43] S. Nakazawa, H. Tamura, K. Kawahara, and Y. OIE,“Performance Analysis of IP Datagram Transmission Delay in MPLS: Impact of Both the Number and the Bandwidth of LSPs of Layer 2,”IEEE ICC 2001, pp. 1006--1010, Helsinki, Finland.
[44] V. Fineberg,“A Practical Architecture for Implementing End-to-End QoS in an IP Newotk,”IEEE Commun. Mag., pp. 122--130, Jan. 2002.
[45] J. Lawrence,“Designing Multiprotocol Label Switching Networks,”IEEE Commun. Mag., pp. 134--142, July. 2001.
[46] R. Cole, D. Shur, and C. Villamizar,“IP over ATM: A Framework Document,” RFC 1932, April 1996.
[47] N. Endo, Z. Niu, and A. Sawada,“Performance Study of SVC-based IP-over-ATM Networks,”IEEE ATM Workshop, pp. 529--534, Kochi, Japan, 1999.
[48] S. Shakkottai,“TCP over End-to-End ABR: A Study of TCP Performance with End-to-End Rate Control and Stochastic Available Capacity,”Master of Engg. Thesis, Indian Institute of Science, Bangalore, India, Jan. 1998.
[49] P. G. Harrison and N. M. Patel, Performance Modeling of Communication Net-works and Computer Architectures, pp. 288--295, Addison Wesley, 1993.
[50] K. M. Chandy, U. Herzog, and L. S. Woo,“Parameter Analysis of Queueing Networks,”IBM Journal of Research and Development, vol. 19, no. 1, pp. 36--42, Jan. 1975.
[51] F. Baskett, K. M. Chandy, R. R. Muntz, and F. G. Palacios,“Open, Closed and Mixed Networks of Queues with Different Classes of Customers,”Journal of ACM, vol. 22, no. 2, pp. 248--260, April 1975.
[52] J. Mckenna, D. Mitra, and K. G. Ramakrishnan,“A Class of Closed Markovian Queueing Networks: Integral Representations, Asymptotic Expansions, and Genera-tions,”The Bell System Technical Journal, vol. 60, pp. 599--641, May-June 1981.
[53] X. Xiao, A. Hannan, and B. Bailey,“Traffic Engineering with MPLS in the Internet,”IEEE Network, vol. 14, no. 2, pp. 28--33, March/April 2000.
[54] K. Nagami and H. Esaki,“Fow Aggregated, Traffic Driven Label Mapping in Label-Switching Networks,”IEEE J. Select. Areas Commun., vol. 17, no. 6, pp. 1170--1189, June 1999.
[55] S. Lin and N. Mckeown,“A simulation study of IP switching,”ACM SIGCOMM'97, pp. 15--24, Palais des Festivals, Cannes, France.
[56] N. Ghani,“Lambda-Labeling: A Framework for IP-Over-WDM Using MPLS,”Workshop on Optical Networks, Dallas, TX, Jan. 2000.
[57] C. Y. Metz, IP Switching: Protocols and Architectures, MacGraw-Hill, 1999.
[58] O. Aboul-Magd, et al.,“Constraint-Based LSP Setup Using LDP,”IETF Inter-net draft-ietf-mpls-cr-ldp-05.txt, Feb. 2001, work in progress.
[59] D. Awduche, L. Berger, D.-H. Gan, T. Li, V. Srinivasan, and G. Swallow,“RSVP-TE: Extensions to RSVP for LSP Tunnels,”IETF Internet draft-ietf-mpls-rsvp-lsp-tunnel-09.txt, Aug. 2001, work in progress.
[60] J. Sadler and B. Mack-Crane,“Generalized Switch Management Protocol (gsmp),”IETF Internet draft-sadler-gsmp-tdm-labels-00.txt, Feb. 2001, work in pro-gress.
[61] P. Ashwood-Smith, et al.,“Generalized MPLS--Signaling Functional Descrip-tion,”IETF Internet draft-ietf-mpls-generalized-signaling-05.txt, July 2001, work in
progress.
[62] P. Ashwood-Smith, et al.,“Generalized MPLS Signaling--CR-LDP Exten-sions,”IETF Internet draft-ietf-mpls-generalized-cr-ldp-04.txt, July 2001, work in progress.
[63] P. Ashwood-Smith, et al.,“Generalized MPLS Signaling--RSVP-TE Exten-sions,”IETF Internet draft-ietf-mpls-generalized-rsvp-te-04.txt, July 2001, work in progress.
[64] K. Kompella, et al.,“OSPF Extensions in Support of Generalized MPLS,”IETF Internet draft-ietf-ccamp-ospf-gmpls-extensions-00.txt, Sept. 2001, work in pro-gress.
[65] K. Kompella, et al.,“IS-IS Extensions in Support of Generalized MPLS,” IETF Internet draft-ietf-isis-gmpls-extensions-04.txt, Sept. 2001, work in progress.
[66] The ATM Forum, LAN Emulation Over ATM Version 1.0, Jan., 1995.
[67] R. Szabo, P. Barta, F. Nemeth, J. Biro, and C-G Perntz,“Call Admission Control in Generalized Processor Sharing (GPS) Schedulers Using Non-Rate Proportional Weighting of Sessions,”IEEE INFOCOM 2000, vol. 3, pp. 1243--1252, Tel-Aviv, Israel.