Subject: [babel] ECMP routing

From: "STARK, BARBARA H" <[email-masked]>
Date: Fri, 12 Oct 2018 00:02:46 +0000

In Acee's review of the info model, he asked about ECMP routing. Wikipedia defines ECMP as "Equal-cost multi-path routing (ECMP) is a routing strategy where next-hop packet forwarding to a single destination can occur over multiple "best paths" which tie for top place in routing metric calculations."

I felt the info model could handle expressing ECMP simply by having multiple selected routes for the same destination prefix.

But I wondered if this was a question that should be asked more broadly than just in the context of the info model.

Juliusz once said on a babel thread "Of the multiple routes to a given destination, at most one is selected." Is this a necessary condition (due to the nature of Babel?) or is it simply that none of the implementations do ECMP?
Barbara

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 13 Oct 2018 13:44:40 +0200

(Added Acee to CC, in case he has some useful thoughts on the subject.)

> Juliusz once said on a babel thread "Of the multiple routes to a given
> destination, at most one is selected." Is this a necessary condition
> (due to the nature of Babel?) or is it simply that none of the
> implementations do ECMP?

RFC 6126bis does not allow ECMP.

While Babel should in principle be able to be extended to do ECMP, doing
that is not entirely obvious, for the following reasons:

  - it is not clear how to make the loop-avoidance algorithm interact with
    ECMP -- in concrete terms, what router-id and seqno to pick for an ECMP
    route;
  - since Babel uses dynamically computed metrics and hysteresis, the
    likelihood of multiple having exactly the same metric is fairly low;
    in practice, you'd need to balance over unequal-cost routes;
  - ECMP does not improve performance in all topologies; in fact, in many
    topologies, it decreases performance; hence, successful deployment of
    ECMP requires competent network administration, and it is not clear to
    me that Babel is being actively deployed in the kind of topologies
    where ECMP is worthwile.

In short, ECMP in Babel is an open research problem -- I think it would
make a good subject for a Master's degree, were it not for the last point
above.  Since the research has not been done yet, I think that it would be
premature to consider ECMP in the information model.

-- Juliusz

---

From: <[email-masked]>
Date: Sun, 14 Oct 2018 17:19:47 -0400

>     me that Babel is being actively deployed in the kind of topologies

Can you explain why this is? If you are doing ECMP on a per-flow basis, rather than a per-packet basis, and given there is more than one flow, it should always improve performance. It might be there are congested links downstream you are avoiding by not doing ECMP, but even without ECMP you're just as likely be on the congested link as not...

😊 /r

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 15 Oct 2018 00:05:57 +0200

>> topologies, it decreases performance;

> Can you explain why this is? If you are doing ECMP on a per-flow basis,
> rather than a per-packet basis, and given there is more than one flow,
> it should always improve performance.

ECMP only improves throughput, and in many networks you're not limited by
throughput -- you want to minimise latency, jitter, or packet loss.  And
I'm not sufficiently familiar with the literature to know whether the
effects of per-flow ECMP on metrics other than throughput have been
studied in detail.

I'm not saying ECMP cannot be done right, what I'm saying is that doing
ECMP right in the wide variety of networks that Babel has been designed to
handle with no human intervention is an open research problem, and
therefore one that it would be premature to standardise.

-- Juliusz

---

From: <[email-masked]>
Date: Sun, 14 Oct 2018 22:24:42 -0400

> throughput -- you want to minimise latency, jitter, or packet loss.  And I'm not
> sufficiently familiar with the literature to know whether the effects of per-flow
> ECMP on metrics other than throughput have been studied in detail.

This is a discussion we need to undertake over something to drink. 😊 I'll just say that ECMP can, in fact, be used to reduce jitter and latency, as well as throughput -- in fact, the three are sometimes intimately related. If the "cost" in ECMP included delay and/or jitter, ECMP would explicitly adjust for links equal in this regard -- or at least attempt to. Reality may be different than theory in this neighborhood. 

> I'm not saying ECMP cannot be done right, what I'm saying is that doing ECMP
> right in the wide variety of networks that Babel has been designed to handle
> with no human intervention is an open research problem, and therefore one
> that it would be premature to standardise.

My larger concern would be positive feedback loops, rather than specific issues with optimizing for a single metric. 

I'm okay with leaving this as a research project, though, for the moment, in BABEL.

😊 /r

---

From: "Acee Lindem (acee)" <[email-masked]>
Date: Mon, 15 Oct 2018 18:14:22 +0000

Hi Russ, Juliusz, 

I agree totally with Russ - I really don't see how ECMP could be more of an issue in Babel. In fact, it could lessen the impact of dynamic metric oscillations if you were to support CECMP (Close Enough Cost Multi-Path) with some % of variance allow between multipath routes. 
Thanks,
Acee

    

    
    
    😊 /r

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 15 Oct 2018 21:44:00 +0200

> I agree totally with Russ - I really don't see how ECMP could be more of
> an issue in Babel.

You guys are probably right, frankly, I don't know.  The question is:

  - given that nobody has been working on (C)ECMP for Babel, should the
    information model be written so as to allow (C)ECMP?
  - given that nobody is quite sure what (C)ECMP for Babel would look
    like, how do we integrate it into the information model?

I'd be thrilled to hear that somebody has done (C)ECMP in Babel, but as
far as I know, nobody is working on it (Toke, David, is that correct?).
Hence, I'd be of the opinion that information model should not consider
(C)ECMP at the current time, but be written so that it can be extended
when somebody gets around to implementing (C)ECMP in Babel.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Mon, 15 Oct 2018 13:01:42 -0700

I agree with Juliusz. I have not been working on this. I’d recommend
leaving it out for now but having a way to add it later.

David

> On Oct 15, 2018, at 12:44 PM, Juliusz Chroboczek <[email-masked]> wrote:
> 
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: "STARK, BARBARA H" <[email-masked]>
Date: Mon, 15 Oct 2018 19:59:01 +0000

> > I agree totally with Russ - I really don't see how ECMP could be more
> > of an issue in Babel.
> 

I see nothing in the info model that precludes ECMP. 
I did a quick search for other routing protocol YANG DMs, to see if they did anything specific. The only thing I could find was OSPF had a "maximum number of ECMP paths" parameter to limit the number of paths that could exist for a destination prefix. I could easily put this in as an optional parameter.

> I'd be thrilled to hear that somebody has done (C)ECMP in Babel, but as far as
> I know, nobody is working on it (Toke, David, is that correct?).
> (C)ECMP at the current time, but be written so that it can be extended when
> somebody gets around to implementing (C)ECMP in Babel.
> 
> -- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Tue, 16 Oct 2018 11:30:35 +0200

> leaving it out for now but having a way to add it later.

+1

-Toke