Computing with BGP: from Routing Configurations to Turing Machines
Marco Chiesa, Luca Cittadini, Giuseppe Di Battista, Laurent Vanbever, Stefano Vissicchio · 2012
Abstract—Because of its practical relevance, the Border Gateway Protocol (BGP) has been the target of a huge research and industrial effort since more than a decade and a BGP routing theory has been developed out of that effort. In this paper, we show that there exists a mapping between BGP and a logic circuit. We show simple networks with routers with elementary BGP configurations that simulate logic gates, clocks and flip-flops, and we show how to interconnect them to simulate arbitrary logic circuits. We then investigate the implications of such a mapping on the computational complexity of BGP problems. We show that, under reasonable assumptions on message timings, BGP has the same computing power as a Turing Machine. As a consequence, we devise a new method for studying the complexity of analyzing BGP configurations and exploit such a method to give several new complexity bounds. Also, if message timings are unrestricted, BGP can simulate a combinational logic circuit, which allows us to prove the NPhardness of a new variant of a well-known BGP problem. Finally, we investigate whether the mapping is still feasible when BGP policies are restricted, e.g., in iBGP or when Local Transit Policies or Gao-Rexford conditions are enforced. I.