The rapid development of the Internet catalyzes emerging applications and diverse requirements. However, the single best-effort path selection paradigm of BGP impedes the inter-domain routing system for addressing such demands. Despite numerous protocols designed for optimization, they manifest limitations: 1) a single protocol often fails to cater to the broad spectrum of AS requirements, and 2) the adoption of multiple protocols occurs disjointedly, leading to partial-deployment issues. In addressing these challenges, we propose Vinculum-BGP ($\textsf {VBGP}$), enabling ASes to flexibly optimize routes and fostering the evolution of inter-domain routing. The core of$\textsf {VBGP}$is a low-cost vinculum (named as$\textsf {rra}$) scheme for bi-directional path negotiation. This scheme improves upon current multipath routing protocols by allowing ASes to discover unpropagated but beneficial paths, ensuring seamless integration with a majority of routers and adaptability to various requirements. We formally prove the stability of routing under$\textsf {rra}$, showing that$\textsf {VBGP}$facilitates the optimization between different protocols without compromising routing stability. We also introduce some simple-to-implement$\textsf {rra}$policies, so that$\textsf {VBGP}$ASes can achieve comparable results to existing complex protocols in terms of pathavailabilityandquality. Finally, we assess the efficacy of$\textsf {VBGP}$through Internet-scale simulations spanning various deployment scenarios, showcasing its substantial benefits to ASes during the initial deployment phase with minimal costs.

Path-aware networks have garnered significant attention as an emerging research area. It allows network senders to actively select or influence transmission paths to meet specific requirements, which necessitates the support of path validation mechanisms. Supported by the path-aware networking research group under the Internet Engineering Task Force (IETF), path validation plays a crucial role in enhancing end hosts' control over packet forwarding. However, existing methods face trade-offs among security, protocol header overhead, and computational cost, forming a ''trilemma.'' Drawing inspiration from persistent validation in zero-trust architecture, we propose the 1BIT protocol. This protocol reduces protocol header overhead by more than 57% while providing robust data flow security. The packet demand for path fault detection is reduced by more than 72%, and fault locations can be precisely identified. By employing hash algorithms and few binary operations, the 1BIT protocol achieves high throughput and supports routers capable of adapting to high-speed, multi-interface environments. On a 16-core CPU, the 1BIT protocol can handle throughput exceeding 100 Gbps. This lightweight and efficient solution introduces anomaly signal detection techniques into the field of path validation. Benefiting from in-depth research on anomaly signal detection, this technology offers a richer set of solutions for path validation and lays the foundation for future research and implementation in areas such as multi-path validation and path privacy protection.

The complexity of routing requirements leads to increasingly intricate routing metrics. Existing routing algebra theories have demonstrated that convergent and optimal routing algorithms can be designed only when path metrics satisfy certain properties such as monotonicity and isotonicity. Furthermore, some non-isotonic metrics can be converted into isotonic forms on partial orders through reduction. However, practical scenarios often involve non-commutative algebraic properties, which are overlooked by existing theories. For these problems, there lacks a unified framework to study their solvability, a systematic method for their reduction, and an efficient algorithm to compute optimal routes. In this work, we extend routing algebra to accommodate non-commutative routing problems, propose general reduction methods for them, and explore their solvability. In addition, we design a link state algorithm that converge fast on a reduced partial order. All these discussions are supported by concrete examples, theoretical proofs, and simulations on various network topologies.

Knowledge of the business relationships between Autonomous Systems (ASes) is the basis for studying many aspects of the Internet. Despite the significant progress achieved by the latest inference algorithms, their inference results still suffer from errors on many special or critical links, thus hindering many relationship-related applications. We take an in-depth analysis on the challenges inherent in inferring AS relationships, including complex routing policies, limited and biased vantage point (VP) coverage, as well as a lack of accurate validation data. To address these challenges, we introduce HELA, a framework for inferring AS relationships with a hybrid of empirical and machine learning algorithms. HELA incorporates an array of grouping, voting, and machine learning algorithms and allows flexible substitution of each. We systematically evaluate various combinations of them to determine the most effective one for HELA. Furthermore, we describe the collection of varied validation datasets, including BGP community and RPSL records from Internet Routing Registries (IRRs), as well as OneStep community. Our up-to-date dataset corrects errors in previous published validation sets, contains 95% more labelled links, and exhibits a closer alignment to actual link distribution. Using routing data and validation datasets composed for each month during$2021\sim 2023$, we access HELA’s superiority in both inference accuracy and stability compared to the state-of-the-art inference algorithms, i.e., AS-Rank, ProbLink, and HELA’s predecessor TopoScope. In particular, HELA achieves up to$2.9\times $reduction on error rates across overall datasets, up to$2.6\times $reduction with a$4.5\times $decrease on standard deviation on incomplete and biased datasets, and up to$1.7\times $reduction on various sources of validation datasets.

Knowledge of the Internet topology and the business relationships between Autonomous Systems (ASes) is the basis for studying many aspects of the Internet. Despite the significant progress achieved by latest inference algorithms, their inference results still suffer from errors on some critical links due to limited data, thus hindering many applications that rely on the inferred relationships. We take an in-depth analysis on the challenges inherent in the data, especially the limited coverage and biased concentration of the vantage points (VPs). Some aspects of them have been largely overlooked but will become more exacerbated when the Internet further grows. Then we develop TopoScope, a framework for accurately recovering AS relationships from such fragmentary observations. TopoScope uses ensemble learning and Bayesian Network to mitigate the observation bias originating not only from a single VP, but also from the uneven distribution of available VPs. It also discovers the intrinsic similarities between groups of adjacent links, and infers the relationships on hidden links that are not directly observable. Compared to state-of-the-art inference algorithms, TopoScope reduces the inference error by up to 2.7-4 times, discovers the relationships for around 30,000 upper layer hidden AS links, and is still more accurate and stable under more incomplete or biased observations.