The Algorithm-to-Algebra Method Applied to Route Aggregation: A Tale of Roadsigns

Over the last decades, the Internet evolved in a strongly organic but loosely-engineered way. The nexuses that formed at its top level are managed mostly by commercially-driven organizations and are thus governed by relationships where all information does not flow freely to the rest of the world for the establishment of the routes throughout the Internet. This evolution has given rise to a plethora of protocols which were designed and adapted on an as-needed basis, resulting in monolithic entities that require highly qualified administrators for their daily management. Certain specific configurations, colloquially known as configuration errors, can result in route oscillations or disruptions on a global scale with a potential to affect communications globally. Furthermore, an intimate knowledge of the inner workings of various protocols is not sufficient to solve the problems that can arise due to the concomitance of various conditions distributed across several domains managed by different organisations.

The complexity and problems that arise stir several questions, both for the understanding of the origin of the problems and for the design of the protocols that will
supersede them. An important guideline cherished by computing scientists is modularity of a solution to a complex problem. While the longing for such modularity has often been voiced by the networking community as an increasingly pressing necessity, it seems to be still missing from the vast literature of its research field. To make things worse, no comprehensive theory of routing and forwarding exists as of today to synthesize the compiled list of protocols and their associated problems.

Over the past decades, the problem of identifying the best paths in a graph has been an object of study from an algebraic perspective. This approach was always somehow limited to metrics and was never fully applied to real-world routing protocols to attempt capturing as many aspects as possible. This changed in the recent years, with attempts to reduce the distance between the algebraic theory of path finding and various mecanisms which can be found in protocols in use nowadays.
Metarouting has emerged as a promising approach embracing Dijkstra’s separation of concerns by looking at routing protocols from an algebraic perspective. Instead of adopting the radical viewpoint of throwing away the entire corpus of routing protocols and starting from scratch, Griffin and Sobrinho proposed to deconstruct existing routing protocols and study how their common building blocks fit together. A guiding principle behind this approach is the Algorithm-to-Algebra Method, whereby aspects that were thought to be algorithmic in nature are progressively transferred to an algebraic dimension of the central problem that routing protocols are solving.

In line with this seminal work, the goal of this thesis is to transfer two related mecanisms in use on the Internet, Route Aggregation and Longest Macth Prefix, into an algebraic form.