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.

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.