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

    Research output: External Thesis Doctoral Thesis

    48 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    QualificationPh.D.
    Awarding Institution
    • Faculty of Computer Science
    Supervisors/Advisors
    • Colin, Jean-Noël, Supervisor
    • Schumacher, Laurent, Supervisor
    Award date15 Jun 2015
    Publication statusUnpublished - 2015

    Fingerprint

    Routing protocols
    Algebra
    Agglomeration
    Network protocols
    Internet
    Communication

    Keywords

    • networks
    • BGP
    • universal algebra
    • route aggregation
    • routing

    Cite this

    @phdthesis{8b8258f556e44cbeaae6a3bbaa315061,
    title = "The Algorithm-to-Algebra Method Applied to Route Aggregation: A Tale of Roadsigns",
    abstract = "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 willsupersede 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.",
    keywords = "networks, BGP, universal algebra, route aggregation, routing",
    author = "Seweryn Dynerowicz",
    year = "2015",
    language = "English",
    school = "Faculty of Computer Science",

    }

    The Algorithm-to-Algebra Method Applied to Route Aggregation : A Tale of Roadsigns. / Dynerowicz, Seweryn.

    2015. 99 p.

    Research output: External Thesis Doctoral Thesis

    TY - THES

    T1 - The Algorithm-to-Algebra Method Applied to Route Aggregation

    T2 - A Tale of Roadsigns

    AU - Dynerowicz, Seweryn

    PY - 2015

    Y1 - 2015

    N2 - 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 willsupersede 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.

    AB - 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 willsupersede 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.

    KW - networks

    KW - BGP

    KW - universal algebra

    KW - route aggregation

    KW - routing

    M3 - Doctoral Thesis

    ER -