Why is OSPF (or IS-IS) afraid of unequal-cost load balancing

You might have wondered why no link-state routing protocols support unequal-cost load balancing (UCLB). Petr Lapukhov provides part of the answer in his Understanding Unequal-Cost Load-Balancing article: EIGRP is one of those few protocols that can ensure a neighbor is not using the current router as its next-hop.

However, one has to wonder: with OSPF and IS-IS having the full network topology (or at least the intra-area part of it) in the SPF tree, how hard would it be to detect that sending a packet to someone that is not on the shortest path would not generate a forwarding loop? Is the lack of OSPF or IS-IS UCLB in Cisco IOS the result of lip service to the standards (at least the OSPF one is way too prescriptive) or a shoddy implementation? What are your thoughts?

8 comments:

  1. "You might have wondered why no link-state routing protocols support unequal-cost load balancing"... Isnt that precisely what TE metrics let you do with an MPLS backbone?

    ReplyDelete
  2. You're absolutely correct (see my Perfect load balancing article for details) ... but why is the UCLB functionality not available in pure OSPF/IS-IS?

    ReplyDelete
  3. In my opinion -

    I believe UCLB is possible, but it will require major changes to the SPF algorithm, mainly becuase SPF doesn't know what lies ahead - it grows from the the root to the leaves. so calculating an alternative path, for EVERY node and checking the FC for it (the implication would be not to remove the root neighbor node's triplet from the TENT list until it is checked agianst every node that enters the PATH list, for the FC), when just in the building process seems quite intense.

    Link state protocols get raw data and calculate the SPF tree. Distance vector protocols get processed data - they don't have to run any calculations, just pick the lowest.

    So i am guessing implementing UCLB in distance vector protocols (or OSPF inter-area), by adding communication of advertised distances between neighbors, will be less difficult to implement than in OSPF/IS-IS intra-area.

    ReplyDelete
  4. There has been some work on link-state protocols with splitting over non-shortest paths, by putting exponentially diminishing fractions of the traffic on longest paths. This actually works quite well and can, in fact, enable "optimal" traffic engineering simply by tuning the links weights. See, for instance, the work in:


    http://www.research.att.com/~dahaixu/pub/nem/pefti.pdf
    http://www.research.att.com/~dahaixu/pub/deft/deft.pdf

    for details.

    ReplyDelete
  5. Wow, there are prestigious readers on this blog ;-)

    ReplyDelete
  6. To Ivan: well, as I mentioned previously, RFC5286 defines to appication of LFA concent (Loop-Free Alternative) in the context of link-state routing protocols such as OSPF and ISIS. This leads us to the brave new world of IP FRR :)

    To Jen: thanks for providing some really interesting reading! I feel like i'm going to get stuck in those for the few next days :)

    ReplyDelete
  7. That will prone to cause routing loops in my opinion. Especially when a path / router goes down and SPF needs to recalculate again on an UCLB Network...

    ReplyDelete
  8. Actually, the UCLB question could be answered in terms of histroy and features. The designers of OSPF and IS-IS at their time of origination never envisioned the type of networks we would have today and even during their protocol evolution over time to factor that "feature" in. The other consideration is that the mold was made for these protocols and integration of UCLB would be too difficult and costly for the many distros of the protocols.
    Now UCLB can be "added" on top of the routing protocol just like another policy routing type feature or feature in general. Look at BFD and Ethernet CFM that could have been designed in the beginning but it was not and thus now it is available as an option to enhance the underlying protocols operation.

    So, maybe in IOS 16 we will get a UCLB knob for OSPF and IS-IS.

    ReplyDelete

You don't have to log in to post a comment, but please do provide your real name/URL. Anonymous comments might get deleted.

Ivan Pepelnjak, CCIE#1354, is the chief technology advisor for NIL Data Communications. He has been designing and implementing large-scale data communications networks as well as teaching and writing books about advanced technologies since 1990. See his full profile, contact him or follow @ioshints on Twitter.