QoS of applications is essential for content providers, and it is required to improve the end-to-end communication quality from a content provider to users. Generally, a content provider's data center network is connected to multiple ASes and has multiple egress paths to reach the content user's network. However, on the Internet, the communication quality of network paths outside of the provider's administrative domain is a black box, so multiple egress paths cannot be quantitatively compared. In addition, it is impossible to determine a unique egress path within a network domain because the parameters that affect the QoS of the content are different for each network. We propose a “Performance Aware Egress Path Discovery” method to improve QoS for content providers. The proposed method uses two techniques: Egress Peer Engineering with Segment Routing over IPv6 and Passive End-to-End Measurement. The method is superior in that it allows various metrics depending on the type of content and can be used for measurements without affecting existing systems. To evaluate our method, we deployed the Performance Aware Egress Path Discovery System in an existing content provider network and conducted experiments to provide production services. Our findings from the experiment show that, in this network, 15.9% of users can expect a 30Mbps throughput improvement, and 13.7% of users can expect a 10ms RTT improvement.

The BGPsec protocol, which is an extension of the border gateway protocol (BGP) for Internet routing known as BGPsec, uses digital signatures to guarantee the validity of routing information. However, the use of digital signatures in routing information on BGPsec causes a lack of memory in BGP routers, creating a gaping security hole in today's Internet. This problem hinders the practical realization and implementation of BGPsec. In this paper, we present APVAS (AS path validation based on aggregate signatures), a new protocol that reduces the memory consumption of routers running BGPsec when validating paths in routing information. APVAS relies on a novel aggregate signature scheme that compresses individually generated signatures into a single signature. Furthermore, we implement a prototype of APVAS on BIRD Internet Routing Daemon and demonstrate its efficiency on actual BGP connections. Our results show that the routing tables of the routers running BGPsec with APVAS have 20% lower memory consumption than those running the conventional BGPsec. We also confirm the effectiveness of APVAS in the real world by using 800,000 routes, which are equivalent to the full route information on a global scale.

Linux container technology and clusters of the containers are expected to make web services consisting of multiple web servers and a load balancer portable, and thus realize easy migration of web services across the different cloud providers and on-premise datacenters. This prevents service to be locked-in a single cloud provider or a single location and enables users to meet their business needs, e.g., preparing for a natural disaster. However existing container management systems lack the generic implementation to route the traffic from the internet into the web service consisting of container clusters. For example, Kubernetes, which is one of the most popular container management systems, is heavily dependent on cloud load balancers. If users use unsupported cloud providers or on-premise datacenters, it is up to users to route the traffic into their cluster while keeping the redundancy and scalability. This means that users could easily be locked-in the major cloud providers including GCP, AWS, and Azure. In this paper, we propose an architecture for a group of containerized load balancers with ECMP redundancy. We containerize Linux ipvs and exabgp, and then implement an experimental system using standard Linux boxes and open source software. We also reveal that our proposed system properly route the traffics with redundancy. Our proposed load balancers are usable even if the infrastructure does not have supported load balancers by Kubernetes and thus free users from lock-ins.

By focusing on the recent swing to the centralized approach by the software defined network (SDN), this paper presents a novel network architecture for refactoring the current distributed Internet protocol (IP) by not only utilizing the SDN itself but also implementing its cooperation with the optical transport layer. The first IP refactoring is for flexible network topology reconfiguration: the global routing and explicit routing functions are transferred from the distributed routers to the centralized SDN. The second IP refactoring is for cost-efficient maintenance migration: we introduce a resource portable IP router that can behave as a shared backup router by cooperating with the optical transport path switching. Extensive evaluations show that our architecture makes the current IP network easier to configure and more scalable. We also validate the feasibility of our proposal.

This paper proposes route advertisement policies (RAP) and an inbound traffic engineering (ITE) technique for a multihomed autonomous system (AS) employing the Border Gateway Protocol (BGP) and provider aggregatable (PA) addressing. The proposed RAP avail the advantage of address aggregation benefit of PA addressing. If multiple address spaces are allocated to each of the ASes that are multihomed to multiple upstream ASes, reduction of the forwarding information base (FIB) and quick convergence are achieved. However, multihoming based on PA addressing raises two issues. First, more specific address information is hidden due to address aggregation. Second, multiple allocated address spaces per AS does not provide the capability of ITE. To cope with these two limitations, we propose i) RAP to ensure connectivity among ASes with fewer routes installed in the FIB of each top-tier AS, and ii) an ITE technique to control inbound routes into multihomed ASes. Our ITE technique does not increase the RIB and FIB sizes in the Internet core. We implement the proposed RAP in an emulation environment with BGP using the Quagga software suite and our developed Hierarchical Automatic Number Allocation (HANA) protocols. We use HANA as a tool to automatically allocate hierarchical PA addresses to ASes. We confirm that with our proposed policies the FIB and RIB (routing information base) sizes in tier-1 ASes do not change with the increase of tier-3 ASes, and the number of BGP update messages exchanged is reduced by up to 69.9% from that achieved with conventional BGP RAP. We also confirmed that our proposed ITE technique, based on selective prefix advertisement, can indeed control inbound traffic into a multihomed AS employing PA addressing.

Border Gateway Protocol (BGP), with its advantages in routing isolation support and mature application, is a promising candidate to integrate satellite systems into the terrestrial IP network. However, with more and more ground stations accessing satellites by BGP, a significant amount of routing overhead can be produced on limited satellite links, especially for geostationary satellite networks with thousands of accessing terminals in extremely large areas. To solve this challenge, multicast transport of BGP was proposed, which takes advantage of the inherent broadcast property of wireless channels. However, its performance can be seriously degraded when interfered with the environment. In this paper, NCSR (Network Coding for Satellite network BGP Routing transport) [1] is explored in depth. Unlike existing counterparts, NCSR pays more attention to the lossy space links and can achieve reliability with more bandwidth savings. A greedy based coding algorithm is proposed to realize the network coding operation. To demonstrate the efficiency of NCSR, we conduct theoretical analyses and extensive simulations in typical scenarios of satellite systems. Simulation results show that NCSR can greatly reduce the bandwidth usage while achieving comparable latency. Discussions on practical considerations when applying network coding method for reliability assurance are also presented in detail.

As interdomain routing protocol, BGP is fairly simple, and allows plenty of policies based on ISPs' preferences. However, recent studies show that BGP routes are often non-optimal in end-to-end performance, due to technological and economic reasons. To obtain improved end-to-end performance, overlay routing, which can change traffic routing in application layer, has gained attention. However, overlay routing often violates BGP routing policies and harms ISPs' interest. In order to take the advantage of overlay to improve the end-to-end performance, while overcoming the disadvantages, we propose a novel interdomain overlay structure, in which overlay nodes are operated by ISPs within an ISP alliance. The traffic between ISPs within the alliance could be routed by overlay routing, and the other traffic would still be routed by BGP. As economic structure plays very important role in interdomain routing, so we propose an effective and fair charging and pricing scheme within the ISP alliance in correspondence with the overlay routing structure. Finally, we give a simple pricing algorithm, with which ISPs can find the optimal prices in the practice. By mathematical analysis and numerical experiments, we show the correctness and convergence of the pricing algorithm.

Root cause analysis of BGP updates is the key to debug and troubleshoot BGP routing problems. However, it is a challenge to precisely diagnose the cause and the origin of routing instability. In this paper, we are the first to distinguish link failure events from policy change events based on BGP updates from single vantage points by analyzing the relationship of the closed loops formed through intersecting all the transient paths during instability and the length variation of the stable paths after instability. Once link failure events are recognized, their origins are precisely inferred with 100% accuracy. Through simulation, our method is effective to distinguish link failure events from link restoration events and policy related events, and reduce the size of candidate set of origins.

Multipath routing has been extended to Border Gateway Protocol (BGP), the current de facto inter-domain routing protocol, to address the reliability and performance issues of the current Internet. However, inter-domain multipath routing introduces a significant challenge for scalability due to the large scale of the inter-domain routing system. At the same time it also introduces new challenges in terms of security and security related overhead. In this paper, we propose a regional multipath approach, Regional Multipath Inter-domain Routing (RMI), where multiple paths are only allowed to be propagated within a well-defined range. With multipath routing in a region, we enable inter-domain routing with rich path diversity and improved security, and no longer have to sacrifice scalability. We show how to propagate multiple paths based on the region by theoretical analysis and by extensive simulations. Our simulations show that the number of messages generated using this approach and the convergence delay are much less than those of BGP and BGP with full multipath advertisement.

Various incidents expose the vulnerability and fragility of the Internet inter-domain routing, and highlight the need for further efforts in developing new approaches to evaluating the trustworthiness of routing information. Based on collections of BGP routing information, we disclose a variety of anomalies and malicious attacks and demonstrate their potential impacts on the Internet security. This paper proposes a systematic approach to detecting the anomalies in inter-domain routing, combining effectively spatial-temporal multiple-view method, knowledge-based method, and cooperative verification method, and illustrates how it helps in alleviating the routing threats by taking advantage of various measures. The main contribution of our approach lies on critical techniques including the construction of routing information sets, the design of detection engines, the anomaly verification and the encouragement mechanism for collaboration among ASs. Our approach has been well verified by our Internet Service Provider (ISP) partners and has been shown to be effective in detecting anomalies and attacks in inter-domain routing.

BGP dictates routing between autonomous systems with rich policy mechanisms in today's Internet. Operators translate high-level policy principles into low-level configurations of multiple routers without a comprehensive understanding of the actual effect on the network behaviors, making the routing management and operation an error-prone and time-consuming procedure. A fundamental question to answer is: how to verify the intended routing principles against the actual routing effects of an ISP? In this paper, we develop a methodology RPIM (Routing Policy Inference Model) towards this end. RPIM extracts from the routing tables various policy patterns, which represent certain high-level policy intentions of network operators, and then maps the patterns into specific design primitives that the ISP employs. To the best of our knowledge, we are the first to infer routing policies in ISP networks comprehensively from the aspects of business relationship, traffic engineering, scalability and security. We apply RPIM to 11 ASes selected from RIPE NCC RIS project, and query IRR database to validate our approach. Vast majority of inferred policies are confirmed by the policy registries, and RPIM achieves 96.23% accuracy excluding validation difficulties caused by incompleteness of the IRR database.

An anomalous change in traffic distributions caused by an external inter-domain routing change leads to congestion of some network links, which then affects the network quality or disrupts traffic. Thus, network operators need to promptly deal with these problems by changing the routing policy or by soliciting the help of an involved or neighboring network operator through operator channels. In addition, they need to diagnose situations in which customers are affected by the incident or in which destinations become unreachable. Although this task is indispensable, understanding the situation is difficult since the cause lies outside the operators' network domains. To alleviate the load on operators, we developed a system for monitoring traffic shifts and the disruptions caused by BGP routing changes. It is challenging to extract information that is more valid from a large amount of BGP update messages and traffic flow records. By correlating these data, the system provides meaningful reports and visualized traffic statistics, and it enables operators to easily detect the cause of traffic changes and to investigate the extent of damage. We demonstrate the effectiveness of the system and evaluate its feasibility by applying it to an ISP backbone network. In addition, we present a case study of traffic changes that the system detected.

The Internet has grown extremely fast in the last two decades. The number of routes to be supported by the routers has become very large. Moreover, the number of messages exchanged to distribute the routes has increased even faster. In this paper, we propose SpliTable, a scalable way to support the Internet routes in a Service Provider network. In our proposal, BGP route selection is done by distributed servers on behalf of the routers. They are called route selection servers. The selected routes are then stored in distributed routing tables. Each router maintains only its share of Internet routes, not the routes for each Internet prefix as it is the case today. We adapted the concept of Distributed Hash Tables (DHT) for that purpose. We show analytically that our proposal is more scalable in the number of routes supported in each router than current iBGP route distribution solutions. Moreover, the number of control messages exchanged with our proposal is bounded contrary to current sparse iBGP route distribution solutions which may never converge. We confirm these findings in an evaluation of a prototype implementation.

The current interdomain routing protocol, BGP, is not resilient to a path failure due to its single-path and slowly-converging route calculation. This paper proposes a novel approach to improve the resilience of the interdomain communication by enabling a set of ASes to form an alliance for themselves. The alliance members cooperatively discover a set of disjoint paths using not only the best routes advertised via BGP but also the ones unadvertised. Since such a set of disjoint paths are unlikely to share a link failure, a member AS can provide a pair of the other members with a transit to circumvent the failure. We evaluate how many disjoint paths we could discover from both advertised and hidden (unadvertised) routes by analyzing publicly available BGP route data. Our feasibility study indicates that an alliance of ASes can establish a set of disjoint paths between arbitrary pair of its alliance members with high probability to improve the resilience of interdomain routing among the members.

We explain how network failures were caused by a natural disaster, describe the restoration steps that were taken, and present lessons learned from the recovery. At 21:26 on December 26th (UTC+9), 2006, there was a serious undersea earthquake off the coast of Taiwan, which measured 7.1 on the Richter scale. This earthquake caused significant damage to submarine cable systems. The resulting fiber cable failures shut down communications in several countries in the Asia Pacific networks. In the first post-earthquake recovery step, BGP routers detoured traffic along redundant backup paths, which provided poor quality connection. Subsequently, operators engineered traffic to improve the quality of recovered communication. To avoid filling narrow-bandwidth links with detoured traffic, the operators had to change the BGP routing policy. Despite the routing-level first aid, a few institutions could not be directly connected to the R&E network community because they had only a single link to the network. For these single-link networks, the commodity link was temporarily used for connectivity. Then, cable connection configurations at the switches were changed to provide high bandwidth and next-generation Internet service. From the whole restoration procedure, we learned that redundant BGP routing information is useful for recovering connectivity but not for providing available bandwidth for the re-routed traffic load and that collaboration between operators is valuable in solving traffic engineering issues such as poor-quality re-routing and lost connections of single-link networks.

This paper addresses the problem of inter-domain QoS routing with Service Level Agreements (SLA) for data transport between peering domains, using virtual-trunk type aggregates. The problem is formally stated and formulated in Integer Linear Programming. As a practical solution, we define the QoS_INFO extension to the BGP routing protocol, conveying three different QoS metrics (light load delay, assigned bandwidth and a congestion alarm), and a path selection algorithm using a combination of these metrics. We present simulation results of QoS_INFO, standard BGP, and BGP with the QoS_NLRI extension, and compare them with the optimal route set provided by the ILP formulation. The results show that our proposal yields better QoS than standard BGP or BGP with the QoS_NLRI extension, since it is able to efficiently avoid congested paths, and that the impact of QoS_INFO in route stability is relatively low.

Contents delivery services are deployed over the Internet and its technology. Contents delivery services demand high quality. Consequently, a large network capacity is required. In order to efficiently deliver such contents and to meet high quality demands, network operators are required to explicitly indicate the branch node and/or the link so that packets are efficiently sent. Fast restoration at the time of trouble has become an important issue. MPLS technology has been utilized to realize Traffic Engineering and Fast Reroute to cope with this issue. However, only a point-to-point path is allowed in the current MPLS technology. To allow an efficient high-quality contents delivery, a point-to-multipoint path called as P2MP-LSP is under discussion. However, proposed methods lack of getting information about P2MP-LSP node due to the current MPLS signaling method to establish P2MP-LSP. This paper introduces a discovery technique of the P2MP-LSP node and an establishment technique of the P2MP-LSP using BGP. In addition, a basic function of this proposal is experimented, and its practicality is evaluated.

BGP might experience a lengthy path exploration process to reach the convergence after the routing changes. found that the BGP rate-limiting timer--MinRouteAdvertisementInterval (MRAI) has an optimal value Mo that achieves the best trade-off between the stability and the convergence speed. In this paper, with the aid of a timed BGP model, we investigate the effects of MRAI and its optimal value Mo for the BGP convergence process. We find that an adequately long MRAI timer can batch-remove candidate paths and ensure the routing stability in the convergence process. There exists a minimal MRAI Ms that achieves the effect, which is also the upper bound of Mo and provides an approximation of Mo. We calculate the approximations of Ms for different settings and estimate the optimal MRAI for the Internet. According to the results, the optimal MRAI for the Internet might be 5-10 times less than the current default value used in the Internet. The simulations taken with SSFNet and the experiments conducted over the Planet-Lab demonstrate the correctness of our analysis.

In the Internet, the routing system consists of the Interior-domain and the Inter-domain. Within the Inter-domain routing, Autonomous System (AS) represents the administrative network domain, which is managed by a single institution with its operational policy. ASs exchange the ASs' reachability information to each other. Without the Inter-domain routing scheme, the nodes in the Internet can't communicate across the multiple ASs. The Inter-domain routing is an essential functional element in the global Internet operation. However, due to several reasons such as miss-configuration at the routers, the Inter-domain routing becomes unstable. This occurs that one AS (say AS1) propagates the prefix that has been already assigned to another AS (say AS2) and other peers receive its routing update and inject the misconfigured AS information to their peering routers. Since the routing information associated with AS1 is over written by AS2, AS1 loses the network connectivity. This problem is known as the Conflict Origin AS prefix or the Multiple Origin AS. We recognize that this is a serious problem which degrades the quality of Internet backbone infrastructure. We focus on this problem and propose the mechanism that can detect the Conflict Origin AS prefix automatically using the policy database. Based on the evaluation using the prototype system, we demonstrate that the proposed mechanism can work well with the existing Internet's Inter-domain routing system.

In this article, we survey current and next generation IX (Internet eXchange) technologies. An IX is a mechanism to interconnect many networks to each other. In other words, an ISP can establish 'peerings' with other ISPs by connecting their routers into IXes. First, we describe the basic IX model, including a policy model, called the 'bilateral' model, which allows participating ISPs to control routing policy and traffic on a 'peer' basis. Next, we classify current IX architectures from a technical point of view and discuss issues of current IXes. In the latter potion of this article, we describe next generation IX technologies, which achieve new features for IXes, such as: enabling larger volume traffic exchange with optical technology, providing virtual private peerings, migrating data-link media to participate into an IX, and exchanging traffic over widely distributed areas. We survey cutting-edge technologies for next generation IXes, and discuss the future of IX technology.