Junda Liu

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2011-155

December 18, 2011

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-155.pdf

Routing is arguably the most fundamental aspect of networking, since it answers the basic question: how do you place the appropriate state in routers or switches so that packets will travel from source to destination? There is a huge academic literature on routing, and the commercial world has been honing their routing implementations for many years. However, with the explosive growth of Internet, wide adoption for critical business and services, and new environments like data center networks, routing has more difficulties to meet the increasingly stringent requirements.

We examine current routing schemes and discover that the problem is more fundamental, because they rely on many assumptions and trade-offs that are no longer applicable for today’s networks. Believing that more radical changes are necessary to effectively address the challenge, we start the design process from scratch, with assumptions, trade-offs and design philosophies which better reflect the networks of today and tomorrow. The outcome of the design process is a unified routing framework which utilizes directed acyclic graph (DAG) as routing topology. And we name it Routing Along DAGs (RAD).

RAD separates route optimization and connectivity maintenance, handles both failures and congestions, and recovers fast and locally. We explain the details of RAD design and test its performance on various real world topologies. Then we improve RAD to achieve even better performance and cover more use cases. With these extensions, RAD becomes both complete and practical.

Advisors: Scott Shenker

---

BibTeX citation:

@phdthesis{Liu:EECS-2011-155,
    Author= {Liu, Junda},
    Title= {Routing Along DAGs},
    School= {EECS Department, University of California, Berkeley},
    Year= {2011},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-155.html},
    Number= {UCB/EECS-2011-155},
    Abstract= {Routing is arguably the most fundamental aspect of networking, since
it answers the basic question: how do you place the appropriate state
in routers or switches so that packets will travel from source to
destination? There is a huge academic literature on routing, and the
commercial world has been honing their routing implementations for
many years. However, with the explosive growth of Internet, wide
adoption for critical business and services, and new environments like
data center networks, routing has more difficulties to meet the
increasingly stringent requirements.

We examine current routing schemes and discover that the problem is
more fundamental, because they rely on many assumptions and trade-offs
that are no longer applicable for today’s networks. Believing that
more radical changes are necessary to effectively address the
challenge, we start the design process from scratch, with assumptions,
trade-offs and design philosophies which better reflect the networks
of today and tomorrow. The outcome of the design process is a unified
routing framework which utilizes directed acyclic graph (DAG) as
routing topology. And we name it Routing Along DAGs (RAD).

RAD separates route optimization and connectivity maintenance, handles
both failures and congestions, and recovers fast and locally. We
explain the details of RAD design and test its performance on various
real world topologies. Then we improve RAD to achieve even better
performance and cover more use cases. With these extensions, RAD
becomes both complete and practical.},
}

EndNote citation:

%0 Thesis
%A Liu, Junda 
%T Routing Along DAGs
%I EECS Department, University of California, Berkeley
%D 2011
%8 December 18
%@ UCB/EECS-2011-155
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-155.html
%F Liu:EECS-2011-155