Upon receiving an incoming packet, a router decides on which of its outgoing links to send the packet. Routers in the Internet generally make this decision on the basis of the shortest path from the router to the packet's destination. The router independently and locally computes this shortest path to the packet's destination. Although the router can account for various routing metrics, such as the latency of its outgoing links, the capacity of those links, and the present load on the links, the router chooses the outgoing path independently of the actual communications patterns among the end hosts in the Internet.
This independent and localized decision-making process in the routing protocol has been critical to the scalability of the Internet: New routers and new links are easily added without having to recompute routing decisions for the entire Internet. However, this routing process can also produce inefficiencies, such as unnecessary shared bottlenecks when multiple routers choose to use the same, shortest, path and leave other paths underutilized.
Localized routing decisions are also often demonstrably unfair, that is, they enhance the communications characteristics of one data flow at an incommensurate cost to other data flows. A broadly accepted measure of fairness in data networks is called “max-min fairness.” In a max-min fair allocation of resources, no consumer's allocation of resources can be increased without penalizing a consumer with a smaller allocation. Packet scheduling algorithms such as fair queuing and round-robin approximate max-min fairness for data flows across a single bottleneck link or router. However, such local, per-flow fairness is usually globally unfair because some communications nodes (hosts or routers) support several data flows.
Some networks allow multipath routing. Here, a router can send outgoing packets along paths other than the absolutely shortest one. Multipath routing allows significantly higher network throughput than single, shortest path routing. Multipath routing also yields a robustness to link failure that is unachievable with single, shortest path routing. Unfortunately, current per-flow or local bandwidth allocation implementations of multipath routing are sometimes even less fair than the more traditional single-path routing protocols.