Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Routing Along DAGs

Abstract

Since the invention of packet switching networks, routing is an important, if not the most fundamental, component of networking. Over decades, both academia and industry put huge efforts to improve routing in various scenarios. 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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View