On the Feasibility of Inter-domain Routing via a Small Broker Set
Dong Lin, David Hui, Weijie Wu, Tingwei Liu, Yating Yang, Yi Wang, John Chi-Shing Lui, Gong Zhang and Yingtao Li
Huawei Technologies Ltd Co., Huawei Technologies Ltd Co., Huawei Technologies Ltd Co., The Chinese University of Hong Kong, Beijing Institute of Technology, Tsinghua University, Chinese University of Hong Kong, Huawei Technologies Ltd Co., Huawei Technologies Ltd Co.

The current inter-domain routing protocol, namely, the Border Gateway Protocol (BGP), cannot provide end-to-end (E2E) quality-of-service (QoS) guarantees. The main reason is that an autonomous system (AS) can only receive guarantees from its first hop ASes via service level agreements (SLAs). But beyond the first hop, QoS along the path from source to destination AS is not within the source AS’s control regime. In this paper, we investigate the feasibility of providing high QoS-guaranteed E2E transit services by utilizing a (small) set of ASes/IXPs to serve as “brokers” to provide supervision, control and resource negotiation. Finding an optimal set of ASes as brokers can be formulated as a Maximum Coverage with B-dominating path Guarantee (MCBG) problem, which we prove to be NP-hard. To address this problem, we design a ( 1-e-1 / 4 )-approximation algorithm and also an efficient heuristic algorithm when considering additional constraints (e.g., path length). Based on the current Internet topology, we discover a “3540-alliance” subset (accounting only 6.8%) of 52,079 ASes/IXPs, which can provide high QoS guarantees for 99.29% E2E connections.