Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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