Network design is, as all things, a matter of choosing tradeoffs –there is no such thing as a free lunch! One of the tradeoffs we deal with all the time is state verses stretch. But while running through the CCDE slides at Cisco Live today, I had a lot of questions about what state and stretch really mean.
Stretch, quite simply, is the difference between the optimum path through the network (for any pair of hosts), and the actual path through the network. For instance, if the shortest actual path available is 2 hops, but traffic is actually flowing along a 3 hop path, the stretch is 1. Why should we ever have stretch in a network? It seems like you’d just never, ever, want stretch, because stretch always represents suboptimal use of available resources.
Because one of other fundamental concepts of network design is the use of information hiding to break up failure domains. Hierarchical network design, in fact, is the intentional use of aggregation to reduce the state –the routing table size, in most cases– in the control plane, so that changes in one area of the network don’t cause changes in the routing table halfway around the world. How does this relate to stretch?
Any time you hide state you increase stretch.
This might not be obvious in all networks –specifically, any time 100% of your traffic flows north/south, decreasing state will not impact stretch. But if you have a combination of north/south and east/west traffic, aggregation –reducing state– will always cause traffic to take a suboptimal path through the network –increased stretch.
Spanning tree is a perfect example of running to one extreme of the state/stretch tradeoff. Spanning tree reduces the state by forcing all traffic along a single tree in the network, and blocking links that don’t belong to that tree. Control plane state is absolutely minimized at the cost of increasing the stretch through the network to the maximum possible –to the point that we often design network topologies around the elimination of links not used on the single tree. TRILL and other fabric solutions break the single tree by injecting more state into the network. Another example is virtualization –splitting traffic off into a separate virtual topology removes the state of large numbers of destinations reachable through the physical network topology, at the cost of setting the stretch for those destinations to infinite (they become unreachable).
The state/stretch tradeoff is a useful tool, a useful paradigm to understand and describe the tradeoff between hiding information and optimal traffic flow through the network.