«Electrical and Computer Engineering Department This thesis is approved, and it is acceptable in quality and form for publication on microfilm: ...»
Electrical and Computer Engineering
This thesis is approved, and it is acceptable in quality and form for publication on
Approved by the Thesis Committee:
Dr Nasir Ghani Chairperson
Dr Jim Plusequallic
Dr Payman Zarkesh-Ha
Dean, Graduate School
MULTI-DOMAIN CRANKBACK OPERATION FOR
IP/MPLS & DWDM NETWORKSBY
BACHELOR OF INFORMATION TECHNOLOGY
THESISSubmitted in Partial Fulfillment of the Requirements for the Degree of Master of Science Electrical Engineering The University of New Mexico Albuquerque, New Mexico July, 2010 ©2010, Fareena Saqib iii
DEDICATIONThis thesis is dedicated to my family, for all the love, support, and the many sacrifices made.
ACKNOWLEDGMENTSFirst of all I wish to offer my gratitude to Almighty God for the Blessings bestowed upon me.
I would like to express my sincerest gratitude and indebtedness to my advisor and supervisor Dr. Nasir Ghani for his untiring assistance, timely guidance, encouragement and creativity at every stage of this study. Working with him has been a true privilege, and I have benefited tremendously from his knowledge of science, both in depth and broadness, and his enthusiasm in supporting me to carry out and complete the research work. He is a role model that I can always look up to.
My deepest appreciation and thanks are extended to Dr. Wennie Shu, Dr. Jim Plusquellic, and Dr. Payman Zarkesh-Ha for their continuous support, encouragement and valuable suggestions. I am also grateful to all the Optical Networks group members in the Electrical and Computer Engineering Department at the University of New Mexico as well as my post-graduate colleagues for their assistance, motivation and valuable comments to improve the dissertation. I am especially grateful to Mostafa Esmaeili for his dedicated assistance, guidance and professional contributions.
It would have not been possible for me to complete the research project without the motivation that my family members provided. Their constant reassurance and tireless optimism provided me the impetus to find ways out of seeming dead-ends.
It is almost impossible to make note of all those, whose inspirations have been vital in the completion of this dissertation. I am grateful to all of them.
Network carriers and operators have built and deployed a very wide range of networking technologies to meet their customers’ needs. These include ultra scalable fibre-optic backbone networks based upon dense wavelength division multiplexing (DWDM) solutions as well as advanced layer 2/3 IP multiprotocol label switching (MPLS) and Ethernet technologies as well. A range of networking control protocols has also been developed to implement service provisioning and management across these networks.
As these infrastructures have been deployed, a range of new challenges have started to emerge. In particular, a major issue is that of provisioning connection services between networks running across different domain boundaries, e.g., administrative geographic, commercial, etc. As a result, many carriers are keenly interested in the design of multi-domain provisioning solutions and algorithms. Nevertheless, to date most such efforts have only looked at pre-configured, i.e., static, inter-domain route computation or more complex solutions based upon hierarchical routing. As such there is significant
Moreover, it is here that crankback signaling offers much promise.
Crankback makes use of active messaging techniques to compute routes in an iterative manner and avoid problematic resource-deficient links. However very few multi-domain crankback schemes have been proposed, leaving much room for further investigation. Along these lines, this thesis proposes crankback signaling solution for multi-domain IP/MPLS and DWDM network operation. The scheme uses a joint intra/inter-domain signaling strategy and is fully-compatible with the standardized resource reservation (RSVP-TE) protocol. Furthermore, the proposed solution also implements and advanced next-hop domain selection strategy to drive the overall crankback process. Finally the whole framework assumes realistic settings in which individual domains have full internal visibility via link-state routing protocols, e.g., open shortest path first traffic engineering (OSPF-TE), but limited “next-hop” inter-domain visibility, e.g., as provided by inter-area or inter-autonomous system (AS) routing protocols.
The performance of the proposed crankback solution is studied using softwarebased discrete event simulation. First, a range of multi-domain topologies are built and tested. Next, detailed simulation runs are conducted for a range of scenarios. Overall, the findings show that the proposed crankback solution is very competitive with hierarchical routing, in many cases even outperforming full mesh abstraction. Moreover the scheme maintains acceptable signaling overheads (owing to it dual inter/intra domain crankback design) and also outperforms existing multi-domain crankback algorithms.
TABLE OF CONTENTS
LIST OF FIGURES
LIST OF TABLES
LIST OF ABBREVIATIONS AND ACRONYMS
1.3 Problem Statement
1.5 Research Approach
1.6 Thesis Outline
1.7 Thesis Timelines
2.1 Multi-Domain Optical Networking Standards
2.2 Research Survey
2.2.3 Crankback Signaling
ENHANCED CRANKBACK SOLUTION
3.1 Setup Signaling Overview
3.2 Multi-Domain Crankback Operation
3.3 Next-Hop Domain Computation
3.4 DWDM Extension (GMPLS Networks)
4.1 Network Topologies
4.2 Performance Metrics
5.1 Performance Evaluation for Ethernet and IP
5.2 Multi-Domain IP/MPLS Scenarios
5.3 Multi-Domain DWDM Scenarios
CONCLUSIONS AND FUTURE WORK
Figure1.1: Timeline of thesis work
Figure 3.1: PATH and RESV signaling sequence
Figure 3.2: Crankback operation
Figure 3.3: Crankback notification algorithm (at local or egress border node).
............... 27 Figure 3.4: Crankback re-computation algorithm (at domain ingress border node)......... 29 Figure 3.5: Enhanced intra/inter-domain crankback scheme (H1=2, H2=2)
Figure 3.6: Multi-entry distance vector table computation algorithm (at PCE).
............... 33 Figure 3.7: Multi-entry next-hop table
Figure 3.8: Enhanced crankback scheme for multi-domain lightpath RWA (H1=2, H2=2)
Figure 4.1: NSFNET topology
Figure 4.2: 10 domain topology
Figure 5.1: Inter-domain BBR performance for 10 domain
Figure 5.2: Inter-domain BBR performance for NSFNET
Figure 5.3: Average inter-domain lightpath for 10 domain network
Figure 5.4: Average inter-domain length for NSFNET
Figure 5.5: Average setup delay for 10 domain network
Figure 5.6: Average setup delay for NSFNET
Figure 5.7: Inter-domain lightpath blocking for 10 domain network
Figure 5.8: Inter-domain lightpath blocking for NSFNET
Figure 5.9: Average lightpath setup delay for 10 domain
Figure 5.10: Average lightpath setup delay for NSFNET
Table 2.1: Summary of multi-domain standards
Table 2.2: Summary of multi-domain research studies
ATM Asynchronous transfer mode BGP Border gateway protocol CSPF Constrained shortest path first DES Discrete event simulation DWDM Dense wavelength division multiplexing EGP Exterior gateway protocol GMPLS Generalized multi-protocol label switching IAT Inter-arrival time IGP Interior gateway protocol
ITU-T Telecommunication Standardization Sector of the ITU LAN Local area networks LPCS Lightpath circuit switching MAH Minimum average hop MAC Minimum average cost MPLS Multiprotocol label switching NSFNET National Science Foundation network
QoS Quality of service RWA Routing and wavelength assignment SP Shared protection TE Traffic engineering VCAT Virtual concatenation
The last two decades have seen tremendous progress in networking technologies.
Here, the traditional “best-effort” paradigms of Internet networking service have now been replaced by full-blown quality of service (QoS) provisions for multiple service types, e.g., data, voice, video, etc. For example at the IP (Layer 3) level, new multiprotocol label switching (MPLS) technologies  have been introduced to support direct circuit setup between router nodes. As a result, network carrier can now achieve advances traffic engineering (TE) capabilities over then service backbones, improving vastly upon earlier hop-based routing setups.
Meanwhile there have also been many advances at the lower fiber-optic level, i.e., Layer1. Most notably, new dense wavelength division multiplexing (DWDM) technologies  have been developed to carry multiple signals over a single fibre using separate wavelength frequencies. Current DWDM systems can easily support over 100 wavelengths per fiber, giving over 1 terabit/sec capacity. Moreover, advanced optical add-drop and switching technologies have also ushered in new lightpath current routing capabilities, i.e., allowing a wavelength channel to be routed across a network of optical switches with little/no backbone processing. Finally, the MPLS framework has also been extended to support these newer optical technologies, i.e., termed as the generalized MPLS (GMPLS) framework .
1.1 Background As the above techniques have been deployed, network provisioning issues have received much focus. Namely a wide range of constraint-based routing solutions have been proposed for IP/MPLS networks . Similarly, many studies have also been done for lightpath circuit routing and wavelength assignment (RWA)  in optical DWDM networks. However most of these efforts have only focused on single “domain” settings in which a provisioning entity has complete “network-wide” topology/resource views, e.g., single link-state routing domain . Clearly, as user demands grow there is now a strong desire to achieve TE provisioning across multiple domains, both at the IP/MPLS and optical DWDM layers. Owing to obvious scalability and confidentiality concerns here , it is clear that this must be achieved in a distributed, decentralized manner.
To address multi domain provisioning challenges, a diverse set of provisions have emerged to help improve multi-domain TE support, both at the IP/MPLS and underlying optical GMPLS layers. On the standards side, many ubiquitous routing protocols already provide varying levels of inter-domain visibility, e.g., next-hop/path-vector dissemination in exterior gateway protocol (EGP)  and hierarchical link-state dissemination in twolevel open-shortest-path-first (OSPF-TE) . Furthermore, the new IETF path computation element (PCE)  framework also defines a comprehensive framework for multi-domain path computation and TE.
Meanwhile on the research side, a host of multi-domain TE schemes have been studied, see survey in  and Chapter 2. A key focus here is to address the tradeoff between inter-domain visibility and control plane complexity (i.e., dissemination, computation). For example, some have developed hierarchical link-state routing solutions to increase inter-domain visibility. The major contributions here are graphtheoretic topology abstractions for compressing domain-level state in IP/MPLS and DWDM networks. However, even though hierarchical routing delivers good blocking performance, associated routing overheads are very high, i.e., low scalability across large networks. Hence these schemes will likely be problematic in real-world settings where carriers tend to prefer EGP distance/path-vector protocols, e.g., border gateway protocol (BGP) variants. Nevertheless, these latter protocols only provide next-hop domain and end-point reachability state and most operational versions do not support any QoS parameters, e.g., delay, bandwidth, etc. As a result, hierarchical routing solutions do not represent a complete framework for all multi-domain provisioning scenarios.
1.2 Motivation In light of the above, there is growing need to develop scheme to provision guaranteed bandwidth connections across multiple IP/MPLS and/or optical DWDM domains. Ideally, these schemes should yield effective provisioning and high scalability ,. Along these lines crankback signaling schemes  offer a very promising approach for developing new solutions for the multi-domain TE. Namely, it is envisioned that these resultant schemes will potentially yield very good performance gains (in terms of blocking) at the same time as reducing overheads. However even though some crankback schemes have been studied -, most of these strategies pursue more basic “exhaustive” search methodologies and hence entail significant signaling overheads. Moreover, none of these solutions have been gauged against alternate hierarchical routing schemes. Along these lines the focus of this thesis is to study the design of advanced crank back strategies for multi domain networks.
1.3 Problem Statement This thesis focuses on the design of multi-domain crankback operation (MCO) for IP and optical DWDM networks. These solutions are also gauged against competing “global” hierarchical routing schemes.