Interdomain Multipath Routing
Igor Anatolyevich Ganichev
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2011-136
December 15, 2011
This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/Archive/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.
Advisors: 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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-136.html %F Ganichev:EECS-2011-136