Interdomain Multipath Routing

Igor Anatolyevich Ganichev

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2011-136
December 15, 2011

http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-136.pdf

While astonishingly successful, Internet is still less reliable than the phone system and supports very limited user choice and control. As many researchers observed, multipath routing is a promising paradigm to address these issues. In this thesis, we argue that multipath routing can indeed go a long way towards these goals as well as lead to a more scalable, extensible, and evolvable Internet.

We begin by describing Yet Another Multipath Routing (YAMR) protocol that provably constructs a set of paths resilient to any one interdomain link failure. YAMR uses an efficient scheme to construct the paths and a novel failure hiding technique to further reduce the control plane overhead.

Next, we describe Pathlet Routing, a protocol that departs from the path-vector paradigm. Pathlet routing allows ASes to advertise policy-compliant path segments called pathlets, and allows users to stitch them together, thus forming a complete path suitable for the user's particular needs. Pathlet routing greatly reduces the forwarding table size, can efficiently express a wide class of routing policies, and provide an exponential number of paths to the users. Finally, we investigate how pathlet routing can be a basis for an evolvable Internet architecture.

Advisor: Scott Shenker


BibTeX citation:

@phdthesis{Ganichev:EECS-2011-136,
    Author = {Ganichev, Igor Anatolyevich},
    Title = {Interdomain Multipath Routing},
    School = {EECS Department, University of California, Berkeley},
    Year = {2011},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-136.html},
    Number = {UCB/EECS-2011-136},
    Abstract = {While astonishingly successful, Internet is still less reliable than the phone system and supports very limited user choice and control. As many researchers observed, multipath routing is a promising paradigm to address these issues. In this thesis, we argue that multipath routing can indeed go a long way towards these goals as well as lead to a more scalable, extensible, and evolvable Internet.

We begin by describing Yet Another Multipath Routing (YAMR) protocol that provably constructs a set of paths resilient to any one interdomain link failure. YAMR uses an efficient scheme to construct the paths and a novel failure hiding technique to further reduce the control plane overhead.

Next, we describe Pathlet Routing, a protocol that departs from the path-vector paradigm. Pathlet routing allows ASes to advertise policy-compliant path segments called pathlets, and allows users to stitch them together, thus forming a complete path suitable for the user's particular needs. Pathlet routing greatly reduces the forwarding table size, can efficiently express a wide class of routing policies, and provide an exponential number of paths to the users. Finally, we investigate how pathlet routing can be a basis for an evolvable Internet architecture.}
}

EndNote citation:

%0 Thesis
%A Ganichev, Igor Anatolyevich
%T Interdomain Multipath Routing
%I EECS Department, University of California, Berkeley
%D 2011
%8 December 15
%@ UCB/EECS-2011-136
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-136.html
%F Ganichev:EECS-2011-136