Search

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 NP-hardness 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.

The Internet is constantly evolving and changing over time. Outages, attacks, upgrades, censorships, and policy changes modify the routing very frequently everywhere in the world. To give the possibility to the Internet Service Providers and to the network operators of monitoring such an evolving scenario, many organizations collect the routing changes and give free access to them. We propose, prototype, and evaluate a visual interface, called Upstream Visibility, to display such data. It is based on three views: (1) a global view that, based on stacked area charts, gives the high level trend of the visibility of an IP prefix; (2) a local view allows the user to check the effects over time of the visibility of an IP prefix on specific locations of the network; and (3) a traditional graph animation view. Also, we propose heuristics for producing such type of drawings, evaluating their effectiveness and performance against scenarios describing well-known Internet incidents.