Subject: [homenet] Dynamically computed metrics in IS-IS are difficult

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 24 Mar 2015 20:32:11 +0100

Dear all,

At todays meeting, the claim was made (at least twice) that adding
dynamically computed metrics to IS-IS is "just a feature".  I strongly
disagree with this assessment -- it's an open research problem, and
a difficult one at that.

Any interesting metric (packet loss, delay, etc.) will cause a negative
feedback loop, which will lead to oscillations.  In Babel, there are three
mechanisms that cope with the oscillations caused by feedback loops:

1. the protocol is loop-avoiding, which means that even when oscillations
   happen they don't normally cause packets to be lost;
2. the protocol uses delayed updates, which means that even when a metric
   is varying the amount of network traffic remains controlled;
3. the protocol uses a hysteresis mechanism which limits the frequency of
   oscillations.

IS-IS is fundamentally based on the notion that a topology change is
propagated throughout the network in a timely manner and SPF is recomputed
by all nodes -- it has no loop-avoidance mechanism other then timely
reconvergence.  If implemented naively, a dynamically computed metric will
cause repeated flooding, repeated SPF computation, and repeated transient
loops.

I'm sure these issues can be solved, and I'm pretty confident that Henning
can tell you how; at any rate, it would be a very interesting research
project.  However, it is a difficult one, and the three techniques used in
Babel do not apply directly to a link-state protocol.

-- Juliusz

---

From: Margaret Wasserman <[email-masked]>
Date: Tue, 24 Mar 2015 16:15:03 -0500

Juliusz,

I understand that this is a complex feature that would require quite a bit of work to get right.  There would also be work involved in standardizing the IS-IS autoconf and IS-IS source-specific routing extensions.  In addition, we might want/need to standardize a mechanism for running IS-IS over IP.  That would be considerable amount of work.

I don't think it is likely to be a lot of work, though, compared to the effort to standardize Babel which would include:

- Starting an IETF WG to do the work, and understanding that the WG would have change control over Babel.
- Substantial work to bring the spec up to the level of detail/clarity required for and IETF protocol.
- Consideration of many IETF requirements, perhaps most notably security requirements.
- Finding a second set of people who are willing to do a complete, independent, fully-interoperable implementation.

Personally, I think that Babel is an interesting Routing Protocol with substantially different applicability than IS-IS, OSPF or BGP, and it might be good to standardize it, whether Homenet adopts it or not.  However, I think that the time to do that would be a serious problem for Homenet because of the time pressure to finalize a standard for Homenet.

Margaret

On Mar 24, 2015, at 2:32 PM, Juliusz Chroboczek <[email-masked]> wrote:

> _______________________________________________
> homenet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/homenet

---

From: Markus Stenberg <[email-masked]>
Date: Tue, 24 Mar 2015 16:30:15 -0500

> On 24.3.2015, at 16.15, Margaret Wasserman <[email-masked]> wrote:

Why does it need WG? 

> - Substantial work to bring the spec up to the level of detail/clarity required for and IETF protocol.

More substantial than researching+standardizing some new IS-IS stuff? Editing documents is hard, but I thought not that hard.

> - Consideration of many IETF requirements, perhaps most notably security requirements.

IS-IS is harder to secure than Babel. Both have HMAC-MD5 crap stuff, and Babel you can run with e.g. manual keyed IPsec, IS-IS you cannot. Hmm.

> - Finding a second set of people who are willing to do a complete, independent, fully-interoperable implementation.

Well, I could find some weekend time if it is enough to kill this discussion. 40 page RFC cannot be _that_ hard to implement if the ‘big’ reference implementation is 10k LoC.

> Personally, I think that Babel is an interesting Routing Protocol with substantially different applicability than IS-IS, OSPF or BGP, and it might be good to standardize it, whether Homenet adopts…

I wonder when do you think all of this IS-IS _research_, _standardization_ and _implementation_ would be done?

Babel I can use _now_.

Cheers,

-Markus

---

From: Evan Hunt <[email-masked]>
Date: Tue, 24 Mar 2015 21:43:38 +0000

On Tue, Mar 24, 2015 at 04:15:03PM -0500, Margaret Wasserman wrote:
> I don't think it is likely to be a lot of work, though, compared to the
> effort to standardize Babel which would include:

[mostly things that involve an exhausting amount of talking, but
do not require the invention of new technology]

> Personally, I think that Babel is an interesting Routing Protocol with
> substantially different applicability than IS-IS, OSPF or BGP, and it
> might be good to standardize it, whether Homenet adopts it or not.
> However, I think that the time to do that would be a serious problem for
> Homenet because of the time pressure to finalize a standard for Homenet.

If there were running code that could make IS-IS function as well as
babel does with respect to dynamically computed metrics, and on wireless
networks of varying quality and shifting topology, then IS-IS would
win on the basis of expediency.

If there were a solid specification and second implementation of babel,
babel would win on the basis of functionality.

Until one of those things exists, we're doomed to continue having an
argument about which values we prefer to compromise.

For myself, I *like* expediency, but I think functionality has to take
priority: radio spectrum isn't going to get less crowded, and topology
isn't going to get simpler.  So I suggest getting started on *both*
endeavors, and let homenet settle on whichever one makes progress first.
If you're correct that IS-IS's problems are straightforward to solve,
that's great.  If not, it's better if we have a plan B already in
progress.  Can we take the first steps toward standardization even if
homenet *hasn't* declared a preference yet?

-- 
Evan Hunt -- [email-masked]
Internet Systems Consortium, Inc.

---

From: David Lamparter <[email-masked]>
Date: Tue, 24 Mar 2015 23:05:35 +0100

> mechanisms that cope with the oscillations caused by feedback loops:

The oscillations are caused by usage of the route interfering with
usability of the route.  It's a problem created by deriving the metric
from live "use and see" measurements.  Taking measurements more
intelligently - like looking at the wifi neighbor state - is another way
of reducing oscillation.  It might be true that we can't avoid live
metrics, but it still is misrepresenting the problem to plainly say
"interesting metrics lead to scillations".

>    is varying the amount of network traffic remains controlled;

IS-IS wouldn't change the metric inside the routing protocol process, it
would be steered by a separate component that derives a metric for a
given neighbor.

Thus, you get the same result by applying this delay on that separate
component.

> 3. the protocol uses a hysteresis mechanism which limits the frequency of

Same for the hysteresis.

> cause repeated flooding, repeated SPF computation, and repeated transient

Indeed transient loops can occur during recomputation.  I don't see the
flooding being much different than babel, it's the same
distribution-of-information problem.

> Babel do not apply directly to a link-state protocol.

2 of the 3 do.

Babel really does two things, a routing protocol and fancy metric
management.  The latter is indeed a very interesting research project,
in fact one that all the Mesh networks struggle or have struggled with.
Knowing you, I assume you did a great job on the metric part.  That
means I will very likely try and see how much of it I can steal ;)

It also means that I'll be happy about someone coming up with an even
better metric in 2 years.  The consensus needed to make this work isn't
on the algorithm, it's on the values - as in: what number is a good wifi
link, what number is GigE, what number is a horrible 4 MBit/s powerline
link.

-David

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 24 Mar 2015 23:18:28 +0100

> I don't think it is likely to be a lot of work, though,

As far as I know, nobody has done something like that since the 1980s:

    Atul Khanna and John Zinky. The Revised ARPANET Routing Metric.
    SIGCOMM'89 Symposium proceedings on Communications architectures
    and protocols, pp. 45-56. ACM New York, NY, USA, 1989.

I'm pretty optimistic that the stabilisation and mitigation techniques
described in that paper can be made to work in IS-IS.  Even if it doesn't
work, it'd certainly be a fun research project.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 25 Mar 2015 01:19:05 +0100

Evan,

> If there were a solid specification

I'm a little confused about that.  I have put a lot of care into RFC 6126,
and I've tried to make it as clear as possible.  Looking at it with four
years' hindsight, there's little in it that I would write differently today.

It would be extremely helpful if you could take the time to explain to me
what it is exactly that you found confusing in RFC 6126.

-- Juliusz

---

From: Evan Hunt <[email-masked]>
Date: Wed, 25 Mar 2015 01:18:54 +0000

> what it is exactly that you found confusing in RFC 6126.

My apologies for lack of clarity: I was not speaking for myself, but
reflecting the statements made at the working group meeting today by
Margaret Wasserman among others, saying that babel is underspecified and
not of sufficient quality for IETF standardization as currently written,
and by Alia Atlas saying the routing area couldn't accept a homenet
specification relying on an experimental RFC.

I don't know what, if any, deficits there may be in 6126, just that
apparently some people regard this as enough of a problem that they prefer
a research project to make IS-IS work better rather than slogging through
the IETF standardization process.  While I can sympathize with the emotion,
but I hate to see running code lose a fight to political inertia.

---

From: "Christian Hopps" <[email-masked]>
Date: Wed, 25 Mar 2015 07:42:32 -0500

> disagree with this assessment -- it's an open research problem, and

I think Margaret tried to convey that it would not be as simple as 
copying the work from babel, but that we should be able to leverage the 
work already done there.

> 3. the protocol uses a hysteresis mechanism which limits the frequency 

Points 2 and 3 are, I believe, the work we should be able to fairly 
easily leverage.

> cause repeated flooding, repeated SPF computation, and repeated 

In fact much work has been done on this in the routing area. For example 
please see:

https://tools.ietf.org/html/rfc6976

Thanks,
Chris.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 25 Mar 2015 16:38:38 +0100

> I was not speaking for myself, but reflecting the statements made at the
> working group meeting

I see, thanks for your answer.

-- Juliusz