This paper proposes a new approach to support restoration of Label Switched Paths (LSP) set up in the MPLS network. The proposed scheme tries to establish all possible bypass tunnels according to the maximum bandwidth between two LSR around the protected Label Switched Router (LSR). The proposed scheme uses the idea of the maximum bandwidth between two LSRs and establishes the bypass tunnels passing through the critical links which will affect the maximum bandwidth between two LSRs. All of LSPs affected by a LSR failure or a link failure can choice a bypass tunnel fit its QoS constraints to reroute. This paper also compares the different between the proposed bypass tunnel and link disjoint bypass tunnel. The simulation result show that the proposed approach has better packet loss in rerouting and can allow more affected LSP to reroute compare to RSVP and efficient Pre-Qualify. The proposed bypass tunnels have better performance than link disjoint bypass tunnels.

As the Internet becomes the ubiquitous infrastructure for various applications, demands on the reliability, availability and security of routing protocols in the Internet are becoming more stringent. Unfortunately, failures are still common in the daily operation of a network. Service disruption for even a short time can seriously affect the quality of real-time applications, such as VoIP and video on demand applications. Moreover, critical business and government applications require routing protocols to be robust against malicious attacks, such as denial of Service attacks. This dissertation proposes three techniques to address some reliability and security concerns in intra-domain (distance vector) routing protocols and inter-domain (path vector) routing protocols. The first technique addresses the problem of service disruption that arises from sudden link failures in distance vector routing protocols. We consider two types of link failures: single link failures and shared risk link group failures. For single link failures, we propose an IP fast reroute mechanism to reroute packets around the failed links. This fast reroute mechanism is the first that does not require complete knowledge of the network topology and does not require changing of the original routing protocol. This mechanism proactively computes a set of relay nodes that can be used to tunnel the rerouted packets immediately after the detection of a link or node failure. The mechanism includes an algorithm for a node to automatically identify itself as a candidate relay node for a reroute link and notify the source node of the reroute link of its candidacy. The source node can then decide the validity of a candidate relay node. The mechanism also includes an algorithm to suppress redundant notification messages. We then extend our IP fast reroute mechanism for single link failures to accommodate shared risk link group failures. We achieve this goal by introducing one more bit information. Through simulations, I show that the proposed mechanisms succeed in rerouting around failed links about 100% of the time, with the length of the reroute path being comparable to the length of the re-converged shortest path. The second technique addresses the problem that arises from allowing any node to route data packets to any other node in the network (and consequently allow any adversary node to launch DoS attacks against other nodes in the network). To solve this problem, we propose a blocking option to allow a node u to block a specified set of nodes and prevent each of them from sending or forwarding packets to node u. The blocking option intends to discard violating packets near the adversary nodes that generated them rather than near their ultimate destinations. We then discuss unintentionally blocked nodes, called blind nodes and extend the routing protocols to allow each node to communicate with its blind nodes via some special nodes called joint nodes. Finally, I show, through extensive simulation, that the average number of blind nodes is close to zero when the average number of blocked nodes is small. The third technique addresses the problem that arises when a set of malicious ASes in the Internet collude to hijack an IP prefix from its legitimate owner in BGP. (Note that none of previous proposals for protecting BGP against IP prefix hijacking is effective when malicious ASes can collude.) To solve this problem, we propose an extension of BGP in which each listed AS in an advertised route supplies a certified full list of all its peers. Then I present an optimization where each AS in an advertised route supplies only a balanced peer list, that is much smaller than its full peer list. Using real Internet topology data, I demonstrate that the average, and largest, balanced peer list is 92% smaller than the corresponding full peer list. Furthermore, in order to handle the dynamics of the Internet topology, we propose algorithms on how to issue certificates to reflect the latest changes of the Internet topology graph. Although the results in this dissertation are presented in the context of distance vector and path vector routing protocols, many of these results can be extended to link state routing protocols as well. / text

Multiprotocol Label Switching (MPLS) fuses the intelligence of routing with the performance of switching and provides significant benefits to networks with a pure IP architecture as well as those with IP and ATM or a mix of ther Layer 2 technologies. MPLS technology is key to scalable virtual private networks (VPNs) and end-to-end quality of service (QoS), enabling efficient utilization of existing networks to meet future growth. The technology also helps to deliver highly scalable, differentiated end-to-end IP services with simpler configuration, management, and provisioning for both Internet providers and end-users. However, MPLS is a connection-oriented architecture. In case of failure MPLS first has to establish a new label switched path (LSP) and then forward the packets to the newly established LSP. For this reason MPLS has a slow restoration response to a link or node failure on the LSP.The thesis provides a description of MPLS-based architecture as a preferred technology for integrating ATM and IP technologies, followed by a discussion of the motivation for the fast and reliable restoration mechanism in an MPLS network. In this thesis first we address the fast rerouting mechanisms for MPLS networks and then we focus on the problem of packet loss, packet reordering and packet delay for protected LSP in MPLS-based network for a single node/link failure. In order to deliver true service assurance for guaranteed traffic on a protected LSP we use the fast rerouting mechanism with a preplanned alternative LSP. We propose enhancements to current proposals described in extant literature. Our fast rerouting mechanism avoids packet disorder and significantly reduces packet delay during the restoration period.An extension of the Fast Rerouting proposal, called Reliable and Fast Rerouting (RFR), provides some preventive actions for the protected LSP against packet loss during a failure. RFR maintains the same advantages of Fast Rerouting while eliminating packet losses, including those packet losses due to link or node failure (circulating on the failed links), which were considered to be "inevitable" up to now.For the purpose of validating and evaluating the behavior of these proposals a simulation tool was developed. It is based on the NS, a well-known network simulator that is being used extensively in research work. An extension featuring the basic functionality of MPLS (MNS) is also available for the NS, and this is the basis of the developed simulation tool.Simulation results allow the comparison of Fast Rerouting and RFR with previous rerouting proposals.In addition to this we propose a mechanism for multiple failure recovery in an LSP. This proposal combines the path protection, segment protection and local repair methods. In addition to the multiple link/node failure protection, the multiple fault tolerance proposal provides a significant reduction of delay that the rerouted traffic can experience after a link failure, because the repair action is taken close to the point of failure.Then we proceed to address an inherent problem of the preplanned alternative LSP. As alternative LSPs are established together with the protected LSP it may happen that the alternative is not the optimal LSP at the time the failure occurs. To overcome this undesired behavior, we propose the Optimal and Guaranteed Alternative Path (OGAP). The proposal uses a hybrid of fast-rerouting and a dynamic approach to establish the optimal alternative LSP while rerouting the affected traffic using the preplanned alternative LSP. This hybrid approach provides the best of the fast rerouting and the dynamic approaches.At the same time we observed that the protection path becomes in fact unprotected from additional failures after the traffic is rerouted onto it.To address this we propose a guarantee mechanism for protection of the new protected LSP carrying the affected traffic, by establishing an alternative LSP for the rerouted traffic after a failure, avoiding the vulnerability problem for the protected traffic.Finally, we present a further optimization mechanism, adaptive LSP, to enhance the existing traffic engineering for Quality of Services (QoS)provision and improve network resource utilization. The adaptive LSP proposal allows more flexibility in network resource allocation and utilization by adapting the LSP to variations in all network loads,resulting in an enhancement of existing MPLS traffic engineering.