Abstract.

What would the Internet be like, if the software running on your computer could choose over which route to send its data? In this talk I will survey four different mathematical models for understanding the consequences of routing flexibility. There are many open questions about how these four types of model should fit together.

• The idea of generalized cut constraints expresses the fundamental constraints which even the most flexibly routed network can't avoid. It comes from basic linear programming.
• The idea of resource pooling expresses what it means for the software to make intelligent routing choices—namely that certain resources in the network should not be allowed to go underutilized. It stems from heavy traffic queueing theory.
• The slogan the power of two choices says that most of the benefits of flexible routing can be achieved even when each user has only a small amount of choice. This theory comes from classic Markov chain analysis.
• The concept of the Wardrop equilibrium, including Braess's paradox, exposes some of the perverse outcomes that can arise when users make selfish choices.

In fact, the Internet does have mechanisms for route choice, but they have never worked properly and today most network operators disable the mechanisms. We may hope that the theory can be properly understood and applied to produce workable mechanisms.