Computing With BGP: From Routing Configurations to Turing Machines

Provided by: ROMA
Topic: Mobility
Format: PDF
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, the authors show that there exists a mapping between BGP and a logic circuit. They show simple networks with routers with elementary BGP configurations that simulate logic gates, clocks and flip-flops, and they show how to interconnect them to simulate arbitrary logic circuits. They then investigate the implications of such a mapping on the computational complexity of BGP problems. They show that, under reasonable assumptions on message timings, BGP has the same computing power as a Turing Machine.

Find By Topic