Greedy Forwarding in the Internet using its Metric Structure
Fragkiskos Papadopoulos
Department of Electrical Engineering and Information Technology
Cyprus University of Technology
Lemesos, Cyprus
Abstract: Forwarding information through a network requires that nodes have a view of the current global topology of the system. This is accomplished by existing routing protocols, where nodes exchange information about the status of their connections to other nodes. This communication overhead as well as the maintenance of a large amount of forwarding state at each node are some of the most serious scaling limitations of the existing Internet routing architecture.
The known mechanism to efficiently forward packets inside a network without requiring a traditional routing protocol, i.e., without nodes having a global view of the topology of the system, is to embed the network in a metric space and then forward packets greedily based on distances in this space. The performance of such a mechanism however depends strongly on the relation, if any, between the observable network topology and the geometry of the underlying space.
In this talk, we will show that there is a metric space lying underneath the observable topology of the Internet, which is negatively curved, i.e., hyperbolic. We will do this by first presenting a connection between hyperbolic geometry and scale-free topology of complex networks like the Internet. We will explain why this geometry can naturally lead to the emergence of Internet-like topologies, and how it can be used to facilitate maximally efficient greedy forwarding. We will then proceed by mapping the real Internet (at the Autonomous System level) to a hyperbolic space. Guided by a constructed map, we will demonstrate that Internet routing exhibits scaling properties that are theoretically close to the best possible, even after changes in the network topology. We will conclude the talk by discussing open research questions regarding the implementation of this approach in practice.