Open issues in interdomain routing: a survey
---
paper_title: Analyzing the Internet's BGP Routing Table

paper_content:

The Internet continues along a path of seeming inexorable growth, at a rate which has, at a minimum, doubled in size each year. How big it needs to be to meet future demands remains an area of somewhat vague speculation. Of more direct interest in the question of whether the basic elements of the Internet can be extended to meet such levels of future demand, whatever they may be. To rephrase this question, are there inherent limitations in the technology of the Internet, or its architecture of deployment that may impact on the continued growth of the Internet to meet ever expanding levels of demand?
---
paper_title: IAB Concerns and Recommendations Regarding Internet Research and Evolution

paper_content:

This document discusses IAB concerns that ongoing research is needed ::: to further the evolution of the Internet infrastructure, and that ::: consistent, sufficient non-commercial funding is needed to enable such ::: research. This memo provides information for the Internet community.
---
paper_title: Internet Routing Architectures

paper_content:

From the Book: ::: To say that the Internet has changed in the past 10 years is a vast understatement. The Internet today is the single most influential phenomenon in computing. The way in which it continues to evolve is likely to affect every form of data communication on a global scale. Internet information-handling strategies, such as Web-based customer support and secure networked commerce, will permanently alter business and consumer behavior. ::: ::: As the Internet and networking have evolved, so too has Cisco Systems' role. Cisco has become the premier worldwide provider of networking for the Internet. In this role, Cisco helps network managers build reliable, scaleable, and cost-effective solutions for networks that span the requirements of small offices to globally-dispersed enterprises. Over the years, Cisco has assembled the largest and most experienced staff of networking experts who serve customers in planning, implementing, and troubleshooting large networks. Bassam Halabi is one of those experts. ::: ::: Although Cisco's expertise is primarily delivered directly to customers, it also can be shared through other means. A new and important medium for sharing Cisco's networking expertise is the Cisco Press. In creating this new forum, New Riders Publishing and Cisco Systems jointly plan to build a library of publications that provide practical information about the design and implementation of routers, switches, servers, and connectivity software. ::: ::: Bassam Halabi's Internet Routing Architectures is the first of these books. Bassam provides his keen insight into interdomain routing, Internet service provider requirements, and the changing Internet infrastructure. He toucheson issues that affect everyone connecting networks to or through the Internet. Bassam's many years of consulting experience with Cisco's largest IP-based networks contribute to this book's useful design recommendations. He brings a pragmatic perspective to the process of building links between domains and selecting network designs for specific situations. ::: ::: Internet Routing Architectures is a readable distillation of essential design and implementation guidelines. We trust you will find it a valuable addition to your networking library.
---
paper_title: Characterizing the Internet hierarchy from multiple vantage points

paper_content:

The delivery of IP traffic through the Internet depends on the complex interactions between thousands of autonomous systems (AS) that exchange routing information using the border gateway protocol (BGP). This paper investigates the topological structure of the Internet in terms of customer-provider and peer-peer relationships between autonomous systems, as manifested in BGP routing policies. We describe a technique for inferring AS relationships by exploiting partial views of the AS graph available from different vantage points. Next we apply the technique to a collection of ten BGP routing tables to infer the relationships between neighboring autonomous systems. Based on these results, we analyze the hierarchical structure of the Internet and propose a five-level classification of AS. Our characterization differs from previous studies by focusing on the commercial relationships between autonomous systems rather than simply the connectivity between the nodes.
---
paper_title: OPCA: robust interdomain policy routing and traffic control

paper_content:

An increasing number of ASes have been connecting to the Internet through the BGP inter-domain routing protocol. With increasing stress on the scale of this system and increasing reliance on Internet connectivity, more participants demand additional functionality from interdomain routing that BGP cannot handle. For example, we believe that the recent trend towards multihomed stub networks exhibits a likely intent to achieve fault tolerant and load balanced connectivity to the Internet. However, BGP today offers route fail-over times as long as 15 minutes, and very limited control over incoming traffic across multiple wide area paths. More research literature and news media are calling for stemming malicious or erroneous routing announcements. We propose a policy control architecture, OPCA, that runs as an overlay network on top of BGP. OPCA allows an AS to make route change requests at other, remote ASes to achieve faster route fail-over and provide capabilities to control traffic entering the local AS. The proposed architecture and protocol will co-exist and interact with the existing routing infrastructure and will allow for a scalable rollout of the protocol.
---
paper_title: Analyzing the Internet's BGP Routing Table

paper_content:

The Internet continues along a path of seeming inexorable growth, at a rate which has, at a minimum, doubled in size each year. How big it needs to be to meet future demands remains an area of somewhat vague speculation. Of more direct interest in the question of whether the basic elements of the Internet can be extended to meet such levels of future demand, whatever they may be. To rephrase this question, are there inherent limitations in the technology of the Internet, or its architecture of deployment that may impact on the continued growth of the Internet to meet ever expanding levels of demand?
---
paper_title: Route flap damping exacerbates internet routing convergence

paper_content:

Route flap damping is considered to be a widely deployed mechanism in core routers that limits the widespread propagation of unstable BGP routing information. Originally designed to suppress route changes caused by link flaps, flap damping attempts to distinguish persistently unstable routes from routes that occasionally fail. It is considered to be a major contributor to the stability of the Internet routing system.We show in this paper that, surprisingly, route flap damping can significantly exacerbate the convergence times of relatively stable routes. For example, a route to a prefix that is withdrawn exactly once and re-announced can be suppressed for up to an hour (using the current RIPE recommended damping parameters). We show that such abnormal behavior fundamentally arises from the interaction of flap damping with BGP path exploration during route withdrawal. We study this interaction using a simple analytical model and understand the impact of various BGP parameters on its occurrence using simulations. Finally, we outline a preliminary proposal to modify route flap damping scheme that removes the undesired interaction in all the topologies we studied. .
---
paper_title: Delayed Internet routing convergence

paper_content:

This paper examines the latency in Internet path failure, failover, and repair due to the convergence properties of interdomain routing. Unlike circuit-switched paths which exhibit failover on the order of milliseconds, our experimental measurements show that interdomain routers in the packet-switched Internet may take tens of minutes to reach a consistent view of the network topology after a fault. These delays stem from temporary routing table fluctuations formed during the operation of the border gateway protocol (BGP) path selection process on the Internet backbone routers. During these periods of delayed convergence, we show that end-to-end Internet paths will experience intermittent loss of connectivity, as well as increased packet loss and latency. We present a two-year study of Internet routing convergence through the experimental instrumentation of key portions of the Internet infrastructure, including both passive data collection and fault-injection machines at major Internet exchange points. Based on data from the injection and measurement of several hundred thousand interdomain routing faults, we describe several unexpected properties of convergence and show that the measured upper bound on Internet interdomain routing convergence delay is an order of magnitude slower than previously thought. Our analysis also shows that the upper theoretic computational bound on the number of router states and control messages exchanged during the process of BGP convergence is factorial with respect to the number of autonomous systems in the Internet. Finally, we demonstrate that much of the observed convergence delay stems from specific router vendor implementation decisions and ambiguity in the BGP specification.
---
paper_title: BGP Route Flap Damping

paper_content:

A usage of the BGP routing protocol is described which is capable of reducing the routing traffic passed on to routing peers and therefore the load on these peers without adversely affecting route convergence time for relatively stable routes. This technique has been implemented in commercial products supporting BGP. The technique is also applicable to IDRP.
---
paper_title: Improved BGP convergence via ghost flushing

paper_content:

Labovitz et al. (2001) and Labovitz et al. (2000) noticed that sometimes it takes border gateway protocol (BGP) a substantial amount of time and messages to converge and stabilize following the failure of some node in the Internet. In this paper, we suggest a minor modification to BGP that eliminates the problem pointed out and substantially reduces the convergence time and communication complexity of BGP. Roughly speaking, our modification ensures that bad news (the failure of a node/edge) propagate fast, while good news (the establishment of a new path to a destination) propagate somewhat slower. This is achieved in BGP by allowing withdrawal messages to propagate with no delay as fast as the network forward them, while announcements propagate as they do in BGP with a delay at each node of one minRouteAdver (except for the first wave of announcements). As a by product of this work, a new stateless mechanism to overcome the counting to infinity problem is provided, which compares favorably with other known stateless mechanisms (in RIP and IGRP).
---
paper_title: Limiting path exploration in BGP

paper_content:

Slow convergence in the Internet can be directly attributed to the "path exploration" phenomenon, inherent in all path vector protocols. The root cause for path exploration is the dependency among paths propagated through the network. Addressing this problem in BGP is particularly difficult as the AS paths exchanged between BGP routers are highly summarized. In this paper, we describe why path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism - forward edge sequence numbers - to annotate the AS paths with additional "path dependency" information. We then develop an enhanced path vector algorithm, EPIC, shown to limit path exploration and lead to faster convergence. In contrast to other solutions, ours is shown to be correct on a very general model of Internet topology and BGP operation. Using theoretical analysis and simulations, we demonstrate that EPIC can achieve a dramatic improvement in routing convergence, compared to BGP and other existing solutions.
---
paper_title: Locating internet routing instabilities

paper_content:

This paper presents a methodology for identifying the autonomous system (or systems) responsible when a routing change is observed and propagated by BGP. The origin of such a routing instability is deduced by examining and correlating BGP updates for many prefixes gathered at many observation points. Although interpreting BGP updates can be perplexing, we find that we can pinpoint the origin to either a single AS or a session between two ASes in most cases. We verify our methodology in two phases. First, we perform simulations on an AS topology derived from actual BGP updates using routing policies that are compatible with inferred peering/customer/provider relationships. In these simulations, in which network and router behavior are "ideal", we inject inter-AS link failures and demonstrate that our methodology can effectively identify most origins of instability. We then develop several heuristics to cope with the limitations of the actual BGP update propagation process and monitoring infrastructure, and apply our methodology and evaluation techniques to actual BGP updates gathered at hundreds of observation points. This approach of relying on data from BGP simulations as well as from measurements enables us to evaluate the inference quality achieved by our approach under ideal situations and how it is correlated with the actual quality and the number of observation points.
---
paper_title: On routing table growth

paper_content:

The Internet has experienced explosive growth since its commercialization. The sizes of the routing tables have increased by an order of magnitude over the past six years. This dramatic growth of the routing table can decrease the packet forwarding speed and demand more router memory space. In this paper, we explore the extent that various factors contribute to the routing table growth and predict the future rate of growth of the routing table. We first perform measurement study to determine the extent that factors such as multi-homing, failure to aggregate, load balancing, and address fragmentation contribute to routing table size, and find that only of prefixes are due to multi-homing, of prefixes are due to failure to aggregate, of prefixes are due to load balancing, and more than of prefixes are due to address fragmentation. This leads us to group all prefixes that are not aggregated due to either failure to aggregate or address fragmentation. We find that the number of prefix clusters is no more than of the number of prefixes. We explore the extent that load balancing contributes to the number of prefix clusters. Furthermore, we predict the growth pattern of prefixes and prefix clusters by observing power-laws on prefixes and prefix clusters. The number of prefixes grows much faster than the number of prefix clusters does. To the best of our knowledge, this is the first study on the explosive growth of routing tables by systematically comparing factors that contribute to the growth and by observing routing table growth patterns.
---
paper_title: Characterizing the Internet hierarchy from multiple vantage points

paper_content:

The delivery of IP traffic through the Internet depends on the complex interactions between thousands of autonomous systems (AS) that exchange routing information using the border gateway protocol (BGP). This paper investigates the topological structure of the Internet in terms of customer-provider and peer-peer relationships between autonomous systems, as manifested in BGP routing policies. We describe a technique for inferring AS relationships by exploiting partial views of the AS graph available from different vantage points. Next we apply the technique to a collection of ten BGP routing tables to infer the relationships between neighboring autonomous systems. Based on these results, we analyze the hierarchical structure of the Internet and propose a five-level classification of AS. Our characterization differs from previous studies by focusing on the commercial relationships between autonomous systems rather than simply the connectivity between the nodes.
---
paper_title: An analysis of BGP convergence properties

paper_content:

The Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol used to exchange reachability information between Autonomous Systems in the global Internet. BGP is a path-vector protocol that allows each Autonomous System to override distance-based metrics with policy-based metrics when choosing best routes. Varadhan et al. [18] have shown that it is possible for a group of Autonomous Systems to independently define BGP policies that together lead to BGP protocol oscillations that never converge on a stable routing. One approach to addressing this problem is based on static analysis of routing policies to determine if they are safe. We explore the worst-case complexity for convergence-oriented static analysis of BGP routing policies. We present an abstract model of BGP and use it to define several global sanity conditions on routing policies that are related to BGP convergence/divergence. For each condition we show that the complexity of statically checking it is either NP-complete or NP-hard.
---
paper_title: The stable paths problem and interdomain routing

paper_content:

Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems to independently define their routing policies with little or no global coordination. It is then natural to ask if BGP can be viewed as a distributed algorithm for solving some fundamental problem. We introduce the stable paths problem and show that BGP can be viewed as a distributed algorithm for solving this problem. Unlike a shortest path tree, such a solution does not represent a global optimum, but rather an equilibrium point in which each node is assigned its local optimum. We study the stable paths problem using a derived structure called a dispute wheel, representing conflicting routing policies at various nodes. We show that if no dispute wheel can be constructed, then there exists a unique solution for the stable paths problem. We define the simple path vector protocol (SPVP), a distributed algorithm for solving the stable paths problem. SPVP is intended to capture the dynamic behavior of BGP at an abstract level. If SPVP converges, then the resulting state corresponds to a stable paths solution. If there is no solution, then SPVP always diverges. In fact, SPVP can even diverge when a solution exists. We show that SPVP will converge to the unique solution of an instance of the stable paths problem if no dispute wheel exists.
---
paper_title: Routing stability in congested networks: experimentation and analysis

paper_content:

Loss of the routing protocol messages due to network congestion can cause peering session failures in routers, leading to route flaps and routing instabilities. We study the effects of traffic overload on routing protocols by quantifying the stability and robustness properties of two common Internet routing protocols, OSPF and BGP, when the routing control traffic is not isolated from data traffic. We develop analytical models to quantify the effect of congestion on the robustness of OSPF and BGP as a function of the traffic overload factor, queueing delays, and packet sizes. We perform extensive measurements in an experimental network of routers to validate the analytical results. Subsequently we use the analytical framework to investigate the effect of factors that are difficult to incorporate into an experimental setup, such as a wide range of link propagation delays and packet dropping policies. Our results show that increased queueing and propagation delays adversely affect BGP's resilience to congestion, in spite of its use of a reliable transport protocol. Our findings demonstrate the importance of selective treatment of routing protocol messages from other traffic, by using scheduling and utilizing buffer management policies in the routers, to achieve stable and robust network operation.
---
paper_title: Reliability models and evaluation of internal BGP networks

paper_content:

The performance of global Internet communication is significantly influenced by the reliability and the stability of Internet routing systems, especially the border gateway protocol (BGP), the de facto standard for inter-domain routing. In this paper, we investigate the reliability of BGP sessions and the internal BGP (IBGP) networks in the environment of unreliable physical and routing layers. The reliability analysis of IBGP networks is difficult, because IBGP sessions may be correlated to each other by the shared underlying physical links and TCP enables IBGP sessions to tolerate certain level of network failures. In this paper, we first investigate the failure probability of IBGP sessions and its relation to BGP timers and TCP retransmission behaviors. The result of this investigation is a simple modification of TCP that increases the robustness of IBGP sessions significantly. Second, we present a novel reliability model to measure the resilience of the whole IBGP networks. This model is of great importance for studying the function loss of IBGP operations and it also provides the theory basis for IBGP network optimization in terms of reliability
---
paper_title: SECURE BORDER GATEWAY PROTOCOL (S-BGP)

paper_content:

The Border Gateway Protocol is used for routing information among autonomous systems .It is highly affected by malicious attacks, due to the lack of a security in BGP control traffic. In this paper explain a secure, scalable, deployable architecture (S-BGP) for an authorization and authentication of the system. The papers explain the vulnerability and security requirement for BGP. This paper provides a comparison among this architecture to other approaches that have been proposed and analyzes the performance. Internet routing protocol is based on distributed component of many router and they exchange routing information among different domain by Border Gateway Protocol.
---
paper_title: Understanding BGP misconfiguration

paper_content:

It is well-known that simple, accidental BGP configuration errors can disrupt Internet connectivity. Yet little is known about the frequency of misconfiguration or its causes, except for the few spectacular incidents of widespread outages. In this paper, we present the first quantitative study of BGP misconfiguration. Over a three week period, we analyzed routing table advertisements from 23 vantage points across the Internet backbone to detect incidents of misconfiguration. For each incident we polled the ISP operators involved to verify whether it was a misconfiguration, and to learn the cause of the incident. We also actively probed the Internet to determine the impact of misconfiguration on connectivity.Surprisingly, we find that configuration errors are pervasive, with 200-1200 prefixes (0.2-1.0% of the BGP table size) suffering from misconfiguration each day. Close to 3 in 4 of all new prefix advertisements were results of misconfiguration. Fortunately, the connectivity seen by end users is surprisingly robust to misconfigurations. While misconfigurations can substantially increase the update load on routers, only one in twenty five affects connectivity. While the causes of misconfiguration are diverse, we argue that most could be prevented through better router design.
---
paper_title: The performance impact of BGP security

paper_content:

The border gateway protocol possesses security vulnerabilities, because speakers can lie. Proposed security protocols can address the vulnerabilities, but can significantly increase the performance overheads, which prevent their real-world deployment. Public key cryptography can address these vulnerabilities. We report our research into analyzing recently proposed security protocols and building simulation frameworks to evaluate their costs, and designing and validating techniques to reduce them.
---
paper_title: SPV: secure path vector routing for securing BGP

paper_content:

As our economy and critical infrastructure increasingly relies on the Internet, the insecurity of the underlying border gateway routing protocol (BGP) stands out as the Achilles heel. Recent misconfigurations and attacks have demonstrated the brittleness of BGP. Securing BGP has become a priority.In this paper, we focus on a viable deployment path to secure BGP. We analyze security requirements, and consider tradeoffs of mechanisms that achieve the requirements. In particular, we study how to secure BGP update messages against attacks. We design an efficient cryptographic mechanism that relies only on symmetric cryptographic primitives to guard an ASPATH from alteration, and propose the Secure Path Vector (SPV) protocol. In contrast to the previously proposed S-BGP protocol, SPV is around 22 times faster. With the current effort to secure BGP, we anticipate that SPV will contribute several alternative mechanisms to secure BGP, especially for the case of incremental deployments.
---
paper_title: Beware of BGP attacks

paper_content:

This note attempts to raise awareness within the network research community about the security of the interdomain routing infrastructure. We identify several attack objectives and mechanisms, assuming that one or more BGP routers have been compromised. Then, we review the existing and proposed countermeasures, showing that they are either generally ineffective (route filtering), or probably too heavyweight to deploy (S-BGP). We also review several recent proposals, and conclude by arguing that a significant research effort is urgently needed in the area of routing security.
---
paper_title: Origin authentication in interdomain routing

paper_content:

Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence of origin authentication; there is no way to validate claims of address ownership or location. The lack of such services not only enables attacks by malicious entities, but also indirectly allows seemingly inconsequential misconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize original, broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80% of the delegation on the Internet. We conclude by evaluating the proposed services via trace-based simulation, which demonstrates that the enhanced proof systems can significantly reduce resource costs associated with origin authentication.
---
paper_title: Internet Routing Architectures

paper_content:

From the Book: ::: To say that the Internet has changed in the past 10 years is a vast understatement. The Internet today is the single most influential phenomenon in computing. The way in which it continues to evolve is likely to affect every form of data communication on a global scale. Internet information-handling strategies, such as Web-based customer support and secure networked commerce, will permanently alter business and consumer behavior. ::: ::: As the Internet and networking have evolved, so too has Cisco Systems' role. Cisco has become the premier worldwide provider of networking for the Internet. In this role, Cisco helps network managers build reliable, scaleable, and cost-effective solutions for networks that span the requirements of small offices to globally-dispersed enterprises. Over the years, Cisco has assembled the largest and most experienced staff of networking experts who serve customers in planning, implementing, and troubleshooting large networks. Bassam Halabi is one of those experts. ::: ::: Although Cisco's expertise is primarily delivered directly to customers, it also can be shared through other means. A new and important medium for sharing Cisco's networking expertise is the Cisco Press. In creating this new forum, New Riders Publishing and Cisco Systems jointly plan to build a library of publications that provide practical information about the design and implementation of routers, switches, servers, and connectivity software. ::: ::: Bassam Halabi's Internet Routing Architectures is the first of these books. Bassam provides his keen insight into interdomain routing, Internet service provider requirements, and the changing Internet infrastructure. He toucheson issues that affect everyone connecting networks to or through the Internet. Bassam's many years of consulting experience with Cisco's largest IP-based networks contribute to this book's useful design recommendations. He brings a pragmatic perspective to the process of building links between domains and selecting network designs for specific situations. ::: ::: Internet Routing Architectures is a readable distillation of essential design and implementation guidelines. We trust you will find it a valuable addition to your networking library.
---
paper_title: Advertisement of Multiple Paths in BGP

paper_content:

This document defines a BGP extension that allows the advertisement of ::: multiple paths for the same address prefix without the new paths ::: implicitly replacing any previous ones. The essence of the extension ::: is that each path is identified by a Path Identifier in addition to ::: the address prefix.
---
paper_title: On the correlation between route dynamics and routing loops

paper_content:

Routing loops are caused by inconsistencies in the routing state of the network. Although undesirable from this aspect, they can provide insight into the routing dynamics that caused them. In this work we present a methodology that utilizes a priori knowledge of loops to study the correlation between routing loops and routing events that could have caused them. We apply our technique to associate route changes with packet loops detected in actual traffic traces collected from the Sprint Backbone. Our study shows that a strong correlation exists between loops and changes in the BGP routing state while the link state protocols ISIS is seldom responsible for such events. Our analysis also identifies factors that influence the distribution of loop path lengths as well as the effectiveness of our detection techniques.
---
paper_title: Internet Routing Architectures

paper_content:

From the Book: ::: To say that the Internet has changed in the past 10 years is a vast understatement. The Internet today is the single most influential phenomenon in computing. The way in which it continues to evolve is likely to affect every form of data communication on a global scale. Internet information-handling strategies, such as Web-based customer support and secure networked commerce, will permanently alter business and consumer behavior. ::: ::: As the Internet and networking have evolved, so too has Cisco Systems' role. Cisco has become the premier worldwide provider of networking for the Internet. In this role, Cisco helps network managers build reliable, scaleable, and cost-effective solutions for networks that span the requirements of small offices to globally-dispersed enterprises. Over the years, Cisco has assembled the largest and most experienced staff of networking experts who serve customers in planning, implementing, and troubleshooting large networks. Bassam Halabi is one of those experts. ::: ::: Although Cisco's expertise is primarily delivered directly to customers, it also can be shared through other means. A new and important medium for sharing Cisco's networking expertise is the Cisco Press. In creating this new forum, New Riders Publishing and Cisco Systems jointly plan to build a library of publications that provide practical information about the design and implementation of routers, switches, servers, and connectivity software. ::: ::: Bassam Halabi's Internet Routing Architectures is the first of these books. Bassam provides his keen insight into interdomain routing, Internet service provider requirements, and the changing Internet infrastructure. He toucheson issues that affect everyone connecting networks to or through the Internet. Bassam's many years of consulting experience with Cisco's largest IP-based networks contribute to this book's useful design recommendations. He brings a pragmatic perspective to the process of building links between domains and selecting network designs for specific situations. ::: ::: Internet Routing Architectures is a readable distillation of essential design and implementation guidelines. We trust you will find it a valuable addition to your networking library.
---
paper_title: On the correctness of IBGP configuration

paper_content:

The Border Gateway Protocol (BGP) has two distinct modes of operation. External BGP (EBGP) exchanges reachability information between autonomous systems, while Internal BGP (IBGP) exchanges external reachability information within an autonomous system. We study several routing anomalies that are unique to IBGP because, unlike EBGP, forwarding paths and signaling paths are not always symmetric. In particular, we focus on anomalies that can cause the protocol to diverge, and those that can cause a router's chosen forwarding path to an egress point to be deflected by another router on that path. Deflections can greatly complicate the debugging of routing problems, and in the worst case multiple deflections can combine to form persistent forwarding loops. We define a correct IBGP configuration to be one that is anomaly free for every possible set of routes sent by neighboring autonomous systems. We show that determination of IBGP configuration correctness is NP-hard. However, we give simple sufficient conditions on network configurations that guarantee correctness.
---
paper_title: A cooperative approach to interdomain traffic engineering

paper_content:

For performance or cost reasons, autonomous systems (AS) often need to control the flow of their incoming interdomain traffic. Controlling its incoming traffic is a difficult task since it often implies influencing ASes on the path. The current BGP-based techniques that an AS can use for this purpose are primitive. Moreover, their effect is often difficult to predict. In this paper, we propose to solve this problem by using Virtual Peerings. A Virtual Peering is an IP tunnel between a border router of a source AS and a border router of a destination AS. This tunnel is established upon request from the destination AS. These tunnels can be negotiated by using backward compatible modifications to the border gateway protocol (BGP). By using Virtual Peerings, the source and destination ASes can achieve various traffic engineering objectives such as traffic-balancing or reducing the latency. A key advantage of our solution is that it does not require cooperation of the intermediate ASes and that it can be incrementally deployed in today's Internet. We then show by simulations that in a load-balancing scenario, a multi-homed AS only needs to request a few dozens of Virtual Peerings to balance its incoming traffic.
---
paper_title: BGP routing stability of popular destinations

paper_content:

The Border Gateway Protocol (BGP) plays a crucial role in the delivery of traffic in the Internet. Fluctuations in BGP routes cause degradation in user performance, increased processing load on routers, and changes in the distribution of traffic load over the network. Although earlier studies have raised concern that BGP routes change quite often, previous work has not considered whether these routing fluctuations affect a significant portion of the traffic. This paper shows that the small number of popular destinations responsible for the bulk of Internet traffic have remarkably stable BGP routes. The vast majority of BGP instability stems from a small number of unpopular destinations. We draw these conclusions from a joint analysis of BGP update messages and flow-level traffic measurements from AT&T's IP backbone. In addition, we analyze the routing stability of destination prefixes corresponding to the NetRating's list of popular Web sites using the update messages collected by the RouteViews and RIPE-NCC servers. Our results suggest that operators can engineer their networks under the assumption that the BGP advertisements associated with most of the traffic are reasonably stable.
---
paper_title: Controlling Hot Potatoes in Intradomain Traffic Engineering

paper_content:

The growth in Internet connectivity at the Autonomous System (AS) level and the practice of ”hot potato” routing has increased the possibility of interaction between intradomain and interdomain traffic engineering (TE). Hot potato routing occurs when a router inside an AS knows of multiple exit points out of the AS towards a destination, and selects the one that is ”closest” to it. The closeness of exit points is determined by the intradomain routing policy of the AS. In this paper, we use routing, traffic and topology data from the Sprint network to study the interaction between hot potato routing and intradomain TE based on selecting link metrics for the IS-IS (or OSPF) protocol. We find that 60% of network prefixes and 70% of traffic can be potentially affected by hot potato routing. We show that when we do not account for this problem, the results from intradomain TE can be off by 10% of link utilization. We show that considering hot potato routing explicitly when selecting link metrics improves performance by as much as 20% in terms of the maximum link load. Detailed examples are used to provide insights into this performance gain. However, this improvement comes at the cost of an increased sensitivity to changes in link metric values or link failures.
---
paper_title: Experiences in building a multihoming load balancing system

paper_content:

The growing popularity of consumer broadband connection technology, in particular cable TV and ADSL, has started a quiet revolution that will reshape the Internet connectivity solutions for commercial enterprises. One emerging theme is the replacement of dedicated lines based on frame relay or ISDN technologies with multiple inexpensive ADSL/cable TV links each of which potentially is subscribed from a different ISP. The key enabling technology for this revolution is multihoming load balancing, which spreads an enterprise's Internet traffic among multiple access links to increase the aggregate throughput, and diverts traffic away from non-functional links when they fail. Although there exist several commercial multihoming load balancing products in the marketplace, very little is published about the design tradeoffs and their performance implications. We describe the design space of multihoming load balancing systems, discuss the tradeoffs involved in load balancing and fail-over implementation strategies, and present quantitative performance measurements collected on a commercial multihoming load balancing system.
---
paper_title: Multi-homing Performance Benefits:An Experimental Evaluation of Practical Enterprise Strategies

paper_content:

Multihoming is increasingly being employed by large enterprises and data centers as a mechanism to extract good performance from their provider connections. Today, multihomed end-networks can employ a variety of commercial route control products to optimize performance over multiple ISP links. However, little is known about the mechanisms employed by such products and their relative trade-offs. ::: ::: In this paper, we propose and evaluate a wide range practical schemes that could go into the design of a route control device and analyze their trade-offs. We implement the proposed schemes on a Linux-based Web proxy and perform a trace-based emulation of their relative performance benefits. We show that both passive and active monitoring based techniques are equally effective and could improve Web performance by about 25% when compared to using a single provider. Another key observation is that the conventional practice of employing historical measurement samples to monitor and predict ISP performance could, in fact, result in sub-optimal performance.
---
paper_title: Inbound traffic engineering for multihomed ASs using AS path prepending

paper_content:

This article considers the AS path prepending approach to engineer inbound traffic for multihomed ASs. The AS path prepending approach artificially inflates the length of the AS path attribute on one of the links in hopes of diverting some of the traffic to other links. Unlike the current practice that determines the prepending length in a trial-and-error way, we propose AutoPrepend, a systematic and automated procedure for conducting prepending. The entire process consists of four components: passive measurement, active measurement, traffic change prediction, and AS path update. The main idea is to predict the traffic change due to a new prepending value before effecting the change. We have also employed a number of mechanisms to minimize intrusion into the normal operation of the Internet. We have deployed AutoPrepend on a noncommercial site and evaluated its effectiveness based on the measurements collected over six months.
---
paper_title: Interdomain traffic engineering with redistribution communities

paper_content:

Various traffic engineering techniques are used to control the flow of IP packets inside large ISP networks. However, few techniques have been proposed to control the flow of packets between domains. In this paper, we focus on the needs of stub ISPs that compose 80% of the global Internet. We first describe the typical traffic pattern of such a stub ISP. Then we briefly describe the methods that those ISPs currently use to engineer their interdomain traffic. We focus on the control of the incoming traffic and show the increasing utilization of the BGP Community attribute and discuss the limitations of this approach. We then propose the redistribution communities as a deployable method to control the flow of the incoming interdomain traffic. We implement those redistribution communities in zebra and evaluate its performance.
---

Title: Open Issues in Interdomain Routing: A Survey

Section 1: Introduction
Description 1: Introduction to interdomain routing and the importance of addressing the challenges it faces.

Section 2: The Basics of Interdomain Routing
Description 2: Overview of the structure and functioning of interdomain routing, including a description of Autonomous Systems (AS), routing protocols, and current practices.

Section 3: Research Challenges in Interdomain Routing
Description 3: Examination of the main research challenges, including scalability, convergence, security, and traffic engineering issues.

Section 4: Slow Convergence and Chattiness of BGP
Description 4: Detailed analysis of the slow convergence issues of BGP and the large amount of BGP advertisements exchanged during routing updates.

Section 5: Scalability Problems Due to Multihoming
Description 5: Discussion on the impact of multihoming on the scalability of BGP routing tables and the effectiveness of current solutions.

Section 6: Expressiveness and Safety of Policies
Description 6: Examination of the interaction of independent routing policies and the resulting global routing anomalies.

Section 7: Robustness of BGP Sessions
Description 7: Discussion on the reliability and vulnerability of BGP sessions, including the impact of congestion and the need for robust connections.

Section 8: Security Issues
Description 8: Analysis of the security vulnerabilities of the BGP protocol, including attacks on BGP message transmission and the lack of authentication in BGP.

Section 9: Lack of Multipath Routing
Description 9: Discussion on the limitations of BGP in supporting multiple paths for the same destination and the impact on load balancing and traffic engineering.

Section 10: Transit through an AS: iBGP Issues
Description 10: Description of the challenges faced by BGP when transmitting routes and packets within an AS, including issues with iBGP and route reflectors.

Section 11: Limited Traffic Engineering Capabilities
Description 11: Analysis of the limitations of current interdomain routing in terms of traffic engineering and the existing operational palliatives.

Section 12: Lack of QoS Support
Description 12: Examination of the lack of Quality of Service (QoS) support in BGP and the implications for applications requiring differentiated services.

Section 13: Conclusions and Lessons Learned
Description 13: Summary of the main lessons learned from the survey of interdomain routing issues and suggestions for future research directions.