Repost: Tony Przygienda on Valley-Free (or Non-ZigZag) Routing
Most blog posts generate the usual noise from the anonymous peanut gallery (if only they’d have at least a sliver of Statler and Waldorf in them), but every now and then there’s a comment that’s pure gold. The one made by Tony Przygienda (of RIFT fame) on Valley-Free Routing post is so good and relevant that I decided to republish it as a separate blog post. Enjoy!
Valley free routing (which I call more generically no-zigzag routing, you can easily figure out what I mean, you go north until you change direction and go south which you do with the 0 and +/-, unsurprisingly major principle in RIFT again ;-) is a very desirable, very hard to achieve property unless you have a sense of N-S on the substrate (fabric, AS-mesh, whatever) which preconditions sense of direction (to be bit bloated, you need a partial mesh with a max-upper and lower bound). And hence, if done extremely well you are not even bound by ECMP anymore ;-)
I do obviously think for locally provisioned bandwith (such as IP fabrics) this is a natural way to progress and will become stronger with the demise of “artisanal local network configuration skills”. Whether it will be Clos or some variant thereof is not very interesting, routing will adjust, the more “interconnected” your fabric in terms of shortcut the more routing information you’ll have to slosh around @ convergence cost @ failure and so on. For things like WAN & AS meshes this is much, much harder thing to achieve, see also the “peer complex role” route leaking discussions in GROW. Hence I don’t think lots of progress will be made unless some kind of economic cost will be imposed on hot potato routing ;-)
At the danger of repeating myself, IMO a very simple approach to achieve VFR is to force direction on the graph so you know when you go up or down, everything else leads normally to a "strange attractor" architecture where "beacons" try to pull traffic towards them and it's easy to end in chaos (some people will get my "strange attractors" pun and that's where all the "complex role" and "multihomed prefix leaking" will end up with, they are creating the three-body problem again ;-) And once you have an up/down you realize that you are dealing with "partial orders" and resulting maximum and minimum bounds which allows you to do a lot of clean thinking what/how things are possible on such structures. Horizontal links are detrimental in terms of routing complexity in such architectures (except for protection purposes) BTW for reasons I don't dwelve further in but if you are familiar with the problem of having to install discards for your summaries ;-) to prevent loops horizontal links lead to same flavor of problems.
Another very extreme approach that can work is to have "all directions" being equal and try to operate a folded mesh, hypercube or dragonfly but that forces on you all links being equally long and equal bandwidth (and normally longer #hops paths with lower minimal cut properties). The advantage is that if you really build a full hypercube you don't need routing anymore, addresses are routes (problem of link breakage on such structure would lead us a deeper discussion about crank-backs and so on so I drop it). NUMA has exploited that kind of structures and it was/is viable for them but it looks hard to me in networks where we tend to "aggregate bandwidth up" and connectivity is far more expensive and less even due to physical spaces we span. And every forwarding hop is quite expensive on top delay-wise.
If that all reads like Greek to non-Greeks ;-) I observe that all those terms are easily accessible on Wikipedia and well-understood in graph theory and slightly advanced (linear) algebra. And for people I din't meet as side-note: I'm not a mathematician ;-) I write lots of code and I talk to people fighting the daily battle in the mud a lot for quite some time now and based on scar tissue and interest I got myself enough mathematical background to possibly see larger patterns that repeat ;-) And if the complexity of this bit is already overwhelming, let's mention that details of implementation of those things @ scale are unfortunately so voluminous and hideously complicated that they would be impossible to talk about in simple blog posts ;-)
The Cheshire Cat: That depends a good deal on where you want to get to.
Alice: I don't much care where.
The Cheshire Cat: Then it doesn't much matter which way you go.
Alice: ...So long as I get somewhere.
The Cheshire Cat: Oh, you're sure to do that, if only you walk long enough.” - Lewis Carroll, Alice in Wonderland.
This just came to my mind after reading Tony's comment above :)