Border Gateway Protocol (BGP) is the backbone of routing infrastructure in the Internet. In its current form, it is an insecure protocol with potential for propagation of bogus routing information. There have been several high-profiles Internet outages linked to BGP in recent times. Several BGP security proposals have been presented in the literature; however, none has been adopted so far and, as a result, securing BGP remains an unsolved problem to this day. Among existing BGP security proposals, Secure BGP (S-BGP) is considered most comprehensive. However, it presents significant challenges in terms of number of signature verifications and deployment considerations. For it to provide comprehensive security guarantees, it requires that all Autonomous Systems (ASes) in the Internet to adopt the scheme and participate in signature additions and verifications in BGP messages. Among others, these challenges have prevented S-BGP from being deployed today. In this thesis, we present two novel lightweight security protocols, called Credible BGP (C-BGP) and Hybrid Cryptosystem BGP (HC-BGP), which rely on security mechanisms in S-BGP but are designed to address signature verification overhead and deployment challenges associated with S-BGP. We develop original and detailed analytical and simulation models to study performance of our proposals and demonstrate that the proposed schemes promise significant savings in terms of computational overhead and security performance in presence of malicious ASes in the network. We also study the impact of IP prefix hijacking on control plane as well as data plane. Specifically, we analyze the impact of bogus routing information on Inter-Domain Packet Filters and propose novel and simple extensions to existing BGP route selection algorithm to combat bogus routing information.

Border Gateway Protocol (BGP) is the backbone of routing infrastructure in the Internet. In its current form, it is an insecure protocol with potential for propagation of bogus routing information. There have been several high-profiles Internet outages linked to BGP in recent times. Several BGP security proposals have been presented in the literature; however, none has been adopted so far and, as a result, securing BGP remains an unsolved problem to this day. Among existing BGP security proposals, Secure BGP (S-BGP) is considered most comprehensive. However, it presents significant challenges in terms of number of signature verifications and deployment considerations. For it to provide comprehensive security guarantees, it requires that all Autonomous Systems (ASes) in the Internet to adopt the scheme and participate in signature additions and verifications in BGP messages. Among others, these challenges have prevented S-BGP from being deployed today. In this thesis, we present two novel lightweight security protocols, called Credible BGP (C-BGP) and Hybrid Cryptosystem BGP (HC-BGP), which rely on security mechanisms in S-BGP but are designed to address signature verification overhead and deployment challenges associated with S-BGP. We develop original and detailed analytical and simulation models to study performance of our proposals and demonstrate that the proposed schemes promise significant savings in terms of computational overhead and security performance in presence of malicious ASes in the network. We also study the impact of IP prefix hijacking on control plane as well as data plane. Specifically, we analyze the impact of bogus routing information on Inter-Domain Packet Filters and propose novel and simple extensions to existing BGP route selection algorithm to combat bogus routing information.

Border Gateway Protocol (BGP) is the backbone of routing infrastructure in the Internet. In its current form, it is an insecure protocol with potential for propagation of bogus routing information. There have been several high-profiles Internet outages linked to BGP in recent times. Several BGP security proposals have been presented in the literature; however, none has been adopted so far and, as a result, securing BGP remains an unsolved problem to this day. Among existing BGP security proposals, Secure BGP (S-BGP) is considered most comprehensive. However, it presents significant challenges in terms of number of signature verifications and deployment considerations. For it to provide comprehensive security guarantees, it requires that all Autonomous Systems (ASes) in the Internet to adopt the scheme and participate in signature additions and verifications in BGP messages. Among others, these challenges have prevented S-BGP from being deployed today. In this thesis, we present two novel lightweight security protocols, called Credible BGP (C-BGP) and Hybrid Cryptosystem BGP (HC-BGP), which rely on security mechanisms in S-BGP but are designed to address signature verification overhead and deployment challenges associated with S-BGP. We develop original and detailed analytical and simulation models to study performance of our proposals and demonstrate that the proposed schemes promise significant savings in terms of computational overhead and security performance in presence of malicious ASes in the network. We also study the impact of IP prefix hijacking on control plane as well as data plane. Specifically, we analyze the impact of bogus routing information on Inter-Domain Packet Filters and propose novel and simple extensions to existing BGP route selection algorithm to combat bogus routing information.

In a few years, the Internet has quickly evolved from a research network connecting a handful of users to the largest distributed system ever built. The Internet connects more than 20,000 Autonomous Systems (ASs) which are administratively independent networks. While the initial Internet was designed to provide a best-effort connectivity among these ASs, there is nowadays a growing trend to deploy new services such as Voice/Video over IP or VPNs. To support these emergent services, ASs need to better engineer their Internet traffic. Traffic Engineering encompasses several goals such as better spreading the traffic load inside a network and obtaining better end-to-end performance (lower latency or higher bandwidth).<br><br> Engineering the traffic inside a single AS is feasible and pretty well understood. To the opposite, interdomain traffic engineering is still a difficult problem. The main issue comes from the current Internet routing architecture, articulated around the Border Gateway Protocol (BGP). BGP propagates a subset of the Internet topology for scalability and stability reasons and does not optimize a single global objective. This limits the control each AS has on its routing and has dramatic implications for interdomain traffic engineering.<br><br> In this thesis, we evaluate the primitive BGP-based routing control mechanisms. For this purpose, we designed and implemented a new approach for modeling BGP on large Internet-scale network topologies. Finally, to overcome the limitations of BGP in terms of routing control, we propose Virtual Peerings, a new mechanism based on a combination of BGP and IP tunneling. We apply Virtual Peerings to solve various interdomain traffic engineering problems such as balancing the load of Internet traffic received by an AS or decreasing the end-to-end latency of Internet paths.

Thesis (M.S. in Computer Science)--Naval Postgraduate School, March 2004. / Thesis advisor(s): Geoffrey Xie. Includes bibliographical references (p. 155-156). Also available online.

The Internet consists of over 50 thousand smaller networks, called Autonomous Systems (ASes) (e.g., AT&T, Sprint, Google), that use the Border Gateway Protocol (BGP) to figure out how to reach each other. One way or another, we all rely on BGP because it is what glues the Internet together, but despite its crucial role, BGP remains vulnerable to propagation of bogus routing information due to malicious attacks or unintentional misconfigurations. The United States Department of Homeland Security (DHS) views BGP security as part of its national strategy for securing the Internet, and there is a big push to standardize a secure variant of BGP (S*BGP) by the Internet Engineering Task Force (IETF). However, S*BGP properties and their impact on the Internet's routing infrastructure, especially in partial deployment, have not yet been fully understood. To address this issue, in this thesis we use methodologies from applied cryptography, algorithms, and large scale simulations to study the following three key properties with respect to their deployment: 1. provable security guarantees, 2. stability in full and partial deployment with or without attackers, 3. benefits and harm resulting from full and partial deployment. With our analysis we have discovered possible security weaknesses in previously proposed secure BGP variants and suggest possible fixes to address them. Our analysis also reveals that security benefits from partially deployed S*BGP are likely to be meager, unless a significant fraction of ASes deploy it. At the same time, complex interactions between S*BGP and the insecure, legacy BGP can introduce new vulnerabilities and instabilities into the Internet's routing infrastructure. We suggest possible strategies for mitigating such pitfalls and facilitating S*BGP deployment in practice.

The Internet is literally an “Inter-Network”, that is, a network of networks. Networks can be entities including Internet Service Providers (ISPs), universities and commercial enterprises. Every network or Autonomous System (AS) has individual requirements, restrictions and capabilities to transit data traffic. No central controlling body determines how ASes connect—instead contractual agreements are established between AS pairs to govern their relationship. It is not feasible for all ASes to be physically connected to all others. Consequently, some ASes provide transit between other ASes. Such a service usually results in remuneration from one or both ASes. Unlike centrally administered networks where all nodes in the network make generic, predictable decisions, each AS has the ability to select its best route based on its own proprietary commercial agreements. Such agreements are converted to a technical policy implemented in the Border Gateway Protocol (BGP). The ability to implement policies ensures the commercial viability of the Internet, but also makes the prediction of routes difficult and even more worrisome, conflicting policies can cause undesirable BGP states where no single AS has sufficient knowledge to understand what is happening [43]. Designing new clean-slate routing protocols is one approach to improving the predictability and reliability of the Internet. However, due to the Internet’s distributed political and administrative control, significant collaboration is required to implement a new routing protocol — especially when no new protocol currently proposed has sufficiently superior flexibility, scalability or robustness. The difficulty in implementing new and improved protocols is evident in the deployment of IPv6 [23]. Although the IPv6 standard has been defined for over a decade and offers a larger address space, better security and embedded quality of service in comparison to traditional IPv4, its deployment is limited to 1200 of over 30000 ASes in the Internet [66]. Hence, it is crucial practical solutions to current problems are evolved in addition to developing clean-slate techniques. Consequently, our approach is pragmatic — designing tangible solutions to practical problems that can be implemented immediately. In this thesis we examine and combine eBGP, iBGP, OSPF, Netflow and router configuration data to discover important aspects of routing. It is this investigation that instigated the development of a model of iBGP. iBGP is the version of BGP implemented within ASes to propagate routes between internal routers. It exists on a logical topology, however it interacts with the physical topology. It is this interaction which can cause persistent oscillation [49] — a system state where routers alter their decision ad infinitum. Detecting configurations which can cause this oscillation is NP-hard [49]. However, our model of iBGP introduced in this thesis benefits from the ‘designed’ structure of the iBGP topology to restrict the search space dramatically to one that is computationally feasible. iBGP data — which is collected to analyze router decisions — is often only collected on a subset of routers due to its massive storage requirements. In addition there is a substantial amount of correlation between router decisions. Our model of iBGP discovers the dependencies between router decisions and can consequently predict the decisions of those routers for which no measurements are available. It does not rely on any assumption of operator configuration, and subsequently is able to be applied in any network scenario — not just the one originally configured. It is this feature, together with the model’s ability to use any available measurement data that makes our technique ideal for network measurement and management applications. We found our model is efficient and accurate on the network of a large Tier-2 AS, where all but seven of over 12:7 million decisions were consistent with observed data. Further we were able to predict the decision of 85% of routers where observed data was unavailable. During our analysis, we also identified several minor configuration errors on operational routers when we predicted the “correct” outcome. The internal state of a network can be influenced by neighboring ASes. Peering agreements are closely guarded due to their commercially sensitivity. They are implemented in BGP in the form of policies and are difficult to infer with publicly available data sources. We examined the peering policies of over 100 ASes from the perspective of a large Tier-2 AS, finding 22% differ from the canonical peering policy outlined in many peering agreements. When a policy differes from the canonical peering policy, it may result in sub-optimal routing within the Tier-2 AS. We used our model of iBGP to firstly predict the decisions of all routers under the current peering policy, before determining the changes that would have occurred under a canonical peering policy. This analysis not only provided a metric for the routing impact of a peers’ non-canonical policy, but subsequently used in combination with traffic data allowed us to determine the influence of the peer on traffic flows. Our techniques described allow an AS to fully quantify the impact of a non-canonical peering policy and adapt business arrangements appropriately. Throughout our analysis of BGP data, we noticed several inconsistencies in the data. Although the results in the above work were insensitive to such inconsistencies, other applications requiring accurate, fine time-scale analysis of the routing state are much more sensitive. Consequently, we undertake a self-consistency check on the BGP data and examine the possible causes of such inconsistencies. We also present a mechanism to ‘clean’ the data to minimize the effects of any inconsistency. / http://proxy.library.adelaide.edu.au/login?url= http://library.adelaide.edu.au/cgi-bin/Pwebrecon.cgi?BBID=1459175 / Thesis (Ph.D.) -- University of Adelaide, School of Mathematical Science, 2009

Nous considérons, dans cette thèse, un nouveau service par lequel les opérateurs de télécommunications offrent des routes supplémentaires à leurs clients (en plus de la route par défaut) comme un service gratuit ou à valeur ajoutée. Ces routes supplémentaires peuvent être utilisées par des clients afin d’optimiser leurs communications, en outrepassant des points de congestion d’Internet, ou les aider à atteindre leurs objectifs d’ingénierie de trafic (meilleurs délais etc.) ou dans un but de robustesse. Nous proposons d’abord une architecture simple permettant à un opérateur de télécommunication de bénéficier de la diversité de chemin qu’il reçoit déjà. Nous étendons ensuite cette architecture afin de rendre possible la propagation de cette diversité de chemin, non seulement aux voisins directs mais aussi, de proche en proche, aux autres domaines. Nous profitons de cette occasion pour relaxer la sélection des routes des différents domaines afin de leur permettre de mettre en place de nouveaux paradigmes de routage. Néanmoins, annoncer des chemins additionnels peut entrainer des problèmes de passage à l’échelle car chaque opérateur peut potentiellement recevoir plus de chemins que ce qu’il peut gérer. Nous quantifions ce problème et mettons en avant des modifications et filtrages simples permettant de réduire ce nombre à un niveau acceptable. En dernier, nous proposons un processus, inspiré des ventes aux enchères, permettant aux opérateurs de propager aux domaines voisins seulement les chemins qui intéressent les dits voisins. De plus, ce processus permet de mettre en avant un nouveau paradigme de propagation de routes, basé sur des négociations et accords commerciaux / In this thesis we consider a new service where carriers offer additional routes to their customers (w.r.t. to the BGP default route) as a free or value-added service. These alternate routes can be used by customers to optimize their communications, by bypassing some congested points in the Internet (e.g. a “tussled” peeringpoints), to help them to meet their traffic engineering objectives (better delays etc.) or just for robustness purposes (e.g, shift to a disjoint alternate route if needed). First we propose a simple architecture that allows a network service provider to benefit from the diversity it currently receives. Then we extend this architecture in order to make the propagation of the Internet path diversity possible, not only to direct neighbors but also to their neighbors and so on. We take advantage of this advance to relax the route selection processes of autonomous systems in order to make them be able to set up new routing paradigms. Nevertheless announcing additional paths can lead to scalability issues, so each carrier could receive more paths than what it could manage. We quantify this issue and we underline easy adaptations and small path filterings which make the number of paths drop to a manageable amount. Last but not least we set up an auction-type route allocation framework, which gives to network service providers the opportunities first to propagate to their neighbors only the paths the said neighbors are interested in and second to leverage a new routing selection paradigm based on commercial agreements and negotiations

This thesis discusses the implications of the traffic characteristics on interdomain traffic engineering with BGP. We first provide an overview of the interdomain traffic control problem. Then, we present results concerning the characteristics of the interdomain traffic, based on the analysis of real traffic traces gathered from non-transit ASes. We discuss the implications of the topological properties of the traffic on interdomain traffic engineering. Based on this knowledge of the traffic characteristics, we go on to study the complexity of designing interdomain traffic engineering techniques by defining the problem as an optimization problem. We show that designing traffic engineering techniques is possible but that several issues inherent to the current interdomain architecture make the task complex. Finally, we evaluate the current state-of-the-art of interdomain traffic engineering and discuss how we envision its future.

From its beginnings as a single link between two research institutions in 1969, the Internet has grown in size and scope, to become a global internetwork connecting over 700 million computers, and 1.7 billion users. No longer a niche facility for scientific collaboration, the Internet now touches the lives of the world’s population, irrespective of their occupation or geography. It is used by people the world over, to pay bills, read the news, listen to music, watch videos, telephone or video-conference friends and family, and much more. The Internet is the premier communications network of our age. Unfortunately, however, there are some respects in which the Internet lags the networks it replaces. In particular, with respect to reliability, the Internet falls far short of the Public Switched Telephone Network which proceeded it. Whereas the PSTN sought, and often delivered the vaunted “five nines” of reliability, the Internet struggles to compete. As for the cause of this reliability shortfall, available evidence indicates that much of the shortfall is due to the unreliability of IP routers themselves. Given the importance of a reliable Internet to contemporary society, vendors and researchers have proposed a number of solutions to either improve the reliability of individual IP routers, or to make networks more resilient to the unavailability of a single router. While having some promise, these existing solutions face significant obstacles to widespread deployment. Thus, in this dissertation, we endeavor to find or construct a practical, readily deployable, method for mitigating the outages caused by IP routers. To achieve our goal, we take inspiration from previous proposals, which advocated the use of link migration. These proposals improve network resilience, by moving links away from a failed (or failing) router, to an in-service router. To understand the constraints of a practical solution, and resolve the limitations of previous proposals, we conduct extensive experimentation, and study source code and protocol specifications. Using the insights produced by these studies, we construct a practical, readily deployable migration solution with sub-second outage times.