RAD

From RAD Lab

Contents 1 Routing Along DAGs 1.1 People 1.2 Summary 1.3 Roadmap 1.4 Progress 1.5 Todo 1.6 Publication

Routing Along DAGs

People

• Faculty: Scott Shenker
• Students: Junda Liu
• Post-doc: Michael Schapira

Summary

Borrowing ideas from the wireless networking literature, we argue that the fundamental output of routing algo- rithms should be a directed acyclic graph (DAG) between each source and destination, rather than a path (or small set of paths). We show how this “routing along DAGs” approach provides fast failover and adaptive real-time load-balancing, and can be applied to many different network settings (e.g., L2, L3, interdomain).

Roadmap

Mid-November

Progress

1. DAG construction and maintenaince algorithms and proofs
2. Local load-balancing algorithm and proof

Todo

1. Fast detection of disconnection (partitioned network)
2. More theory questions
3. Implementation

Publication