Subject: Reconvergence micro-loops: problem and solutions overview

From: Alex Zinin <[email-masked]>
Date: Tue, 21 Sep 2004 23:41:22 -0700

Folks-

 This is another technical issue we need to tackle. Briefly, routers several
 hops away from the failure may form a temporary microloop while reconverging on
 the new topology. This is due to the fact that a router's new best path may be
 through a neighbor that used the first router as the best path before failure
 and haven't had a chance to recalculate and/or install new routes through its
 new downstream. The problem is briefly described in
 draft-ietf-rtgwg-ipfrr-framework-01.txt. There's also a description of it in
 draft-bryant-ipfrr-tunnels-00.txt.

 Strictly speaking, this is not part of a specific IP FRR mechanism. However,
 from the perspective of the characteristics of the network we are working on,
 this is certainly a problem that we need to solve, for Basic IP FRR too.

 Conceptually, there are two way to approach this problem:

  1. Loop prevention: make sure micro-loops do not form in the first place or
     that the probability of their formation is acceptably low.

  2. Loop detection and mitigation: detect packets coming from what you believe
     is a downstream neighbor and try to fix the loop in the forwarding plane.

 In the first group, we have a set of potential mechanisms, outlined by Mike and
 Stewart in draft-bryant-ipfrr-tunnels-00.txt. Excluding the tunnel-based
 methods from this discussion (since we need a solution for Basic IP FRR at this
 time), we have two mechanisms (with a brief description and pros-n-cons, by no
 means complete):

  a)Incremental Cost Advertisement: instead of removing failed link from the
    topology right away, go through a series of announcements, incrementing the
    cost each time and let the network converge for each version of the link
    cost, thus allowing routers more distant from the point of failure (and
    closer to the potential reroute path) calculate and install new paths before
    others. The network switches to the new primary next hops in a set of circles
    with a decreasing radius.

     Pros: -no changes to the protocol machinery (LSAs, SPF calculation)
           -no explicit router coordination needed
           -comparatively easy to implement
           -no interop issues (easy incremental deployment)
           -no changes to forwarding (beyond basic IP FRR)

     Cons: -slow network reconvergence
           -n times increase of protocol overhead and router load per
            single failure

  b)Ordered SPFs: based on the network topology and the distance of the
    calculating router from the point of failure, each router delays SPF
    calculation to ensure ordered switch-over to the new primaries.
    The total convergence time (proportional to the network diameter in
    the worst case) could be decreased by explicit signaling of SPF
    completion.

     Pros: -no increase in overhead or router load per failure (assuming no
            signaling)
           -better convergence times than in a) are achievable
           -no changes to forwarding (beyond basic IP FRR)

     Cons: -still slow network reconvergence
           -considerable complexity increase if signaling is employed
           -requires all routers to cooperate (I actually don't think this is
            an deciding factor, it is likely that most routers will
            need to be SW-upgraded anyways, and plus before that it's never
            worse than with no IP FRR)

 In the second group we have an idea from Alia. Based on what I understand:

  c)U-turn-like method: detect packets looped back from the primary and
    forward them using preinstalled loop-free alternate next-hops

     Pros: -real-time (fast)
           -no substantial changes to routing protocols
     
     Cons: -requires additional changes to forwarding (beyond basic IP FRR)

 My opinion as a WG chair is that we should avoid solutions involving more
 modifications to the forwarding plane than what's needed for IP FRR already.
 From this perspective I think we should work on loop prevention (i.e. the first
 group of solutions).

 At this point I'll let the authors comment on the descriptions above and/or
 correct me, and folks in the WG express their opinion on the pros and cons
 they see.
 
--
Alex
http://www.psg.com/~zinin

_______________________________________________
Rtgwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rtgwg

---

From: mike shand <[email-masked]>
Date: Wed, 22 Sep 2004 20:05:59 +0100

>  this is certainly a problem that we need to solve, for Basic IP FRR too.

I agree. Without addressing this problem, the usefulness of any Fast 
reroute mechanism is reduced. i.e. there will be destinations for which 
traffic will be dropped for periods of several hundred milliseconds even 
though a viable repair path is put in place in a few tens of milliseconds.

With the basic repair mechanism it is possible to identify a subset of the 
links in the network which can be completely protected by the repair 
mechanism and hence make some service guarantees (albeit rather restricted 
ones compared to a more complete IPFRR solution). However, when microloops 
are considered the set of links for which a minimum outage time in the tens 
of milliseconds can be guaranteed is reduced.

I don't have a proof of this, but I think that links which are protected by 
downstream routes by virtue of them being part of a Euclidean triangle will 
not suffer loops. However, those links which have downstream routes for 
other reasons will almost certainly generate loops for some destinations 
when they fail.

The effect of this would be that guarantees could only be made about the 
failure of links which were members of Euclidean triangles.

Note that this means that any attempt to configure the network to increase 
the number of "basic scheme" repairs by adjusting costs (as opposed to 
introducing triangles) is probably futile without microloop prevention.

>  time), we have two mechanisms (with a brief description and pros-n-cons, 

I'm not sure why you automatically rule out tunnel based approaches. The 
simple scheme of encapsulating data to the near side of the failure for the 
duration of the convergence does not rely on more complex IPFRR schemes for 
its operation. However it DOES need tunnelling.

>            -n times increase of protocol overhead and router load per

Yes. While I like the simplicity of this scheme, I don't think it is 
feasible in real world networks (at least those using wide metrics) because 
of the potentially large number of increments which may be required.

>  From this perspective I think we should work on loop prevention (i.e. 

I agree.

---

From: Alex Zinin <[email-masked]>
Date: Wed, 22 Sep 2004 15:30:39 -0700

Mike,

> though a viable repair path is put in place in a few tens of milliseconds.

This might even be in the order of seconds if neighboring routers happen
to time their SPF calculations and route installation differently enough.
Of course, the are also corner cases of dropped (and later restransmitted)
updates, but we don't optimize for those.

> its operation. However it DOES need tunnelling.

Sorry I didn't spell this out. I am hoping we can come up with a simple enough
scheme that reduces micro-loop probability sufficiently and does not require any
other mechanisms in the forwarding plane that those already required for the
basic IP FRR functionality. I tend to consider tunneling as an additional
mechanism in this context.

Point taken, however. If we end up not finding such a simple technique, we may
as well look at the tunnel based approaches, provided that they don't involve
complexity of the advanced IP FRR schemes.

>>   a)Incremental Cost Advertisement: instead of removing failed link from the
...
> of the potentially large number of increments which may be required.

Will take this to a separate thread.

Regards,
Alex

---

From: Alex Zinin <[email-masked]>
Date: Wed, 22 Sep 2004 15:35:43 -0700

Mike,

...

> of the potentially large number of increments which may be required.

To make sure we have a complete picture here, have guys done any analysis (based
on the network topologies you have) of the mix, max, and average number of
increments required for link failures. I.e., it is clear that counting up
through all possible link cost values is not necessary, and we only need an
increasing sequence of values so that routers that may indeed form a loop
converge in an orderly fashion. It should be possible to calculate such sequence
for each possible link failure in a given topology. It would be interesting to
know these numbers.

Alex

---

From: mike shand <[email-masked]>
Date: Thu, 23 Sep 2004 00:24:12 +0100

>for each possible link failure in a given topology. It would be interesting to

Yes, I've done the simulations for a bunch of networks. I'll try to gather 
the data into something meaningful. May have to wait till I get back home 
next week. But the bottom line is it isn't good news.

         Mike

---

From: Alex Zinin <[email-masked]>
Date: Wed, 22 Sep 2004 16:39:41 -0700

> next week. But the bottom line is it isn't good news.

Right. From my analysis, turning around zones of the network that use the failed
link in their SPT is potentially expensive, but I only did it on paper and it's
always useful to check against real-life networks.

Thanks, Mike!

Alex

---

From: Alia Atlas <[email-masked]>
Date: Thu, 23 Sep 2004 12:20:12 -0400

At 03:05 PM 9/22/2004, mike shand wrote:
>simple scheme of encapsulating data to the near side of the failure for 
>the duration of the convergence does not rely on more complex IPFRR 
>schemes for its operation. However it DOES need tunnelling.

Tunneling is an additional mechanism which may or may not be supported in 
the fast path and which has associated operational overhead.

The advantage of the other two mechanisms is they actually work when a link 
is added or the cost of a link is changed.  If you are arguing that 
micro-loop prevention is vital to support SLAs and avoid traffic loss, 
those same arguments seem to me to apply for when a link is added.

Both the incremental cost advertisement and the ordered SPF approaches 
solve the problem for the new link case as well as the failed link case.

Any approach based on using a tunneled alternate does not.

Alia

---

From: mike shand <[email-masked]>
Date: Thu, 23 Sep 2004 18:17:03 +0100

At 12:20 23/09/2004 -0400, Alia Atlas wrote:
>The advantage of the other two mechanisms is they actually work when a 
>link is added or the cost of a link is changed.  If you are arguing that 

And so do tunnels!

         Mike

---

From: Pekka Savola <[email-masked]>
Date: Thu, 23 Sep 2004 20:47:13 +0300 (EEST)

> the fast path and which has associated operational overhead.

For what it's worth, I feel that tunneling would be a non-trivial
solution, and I'd be wary about taking that approach if there are
reasonable alternatives.

At least:

- you'll need to figure out how to deal with fragmentation issues
caused by the overhead when the data packet size was already maxed
out, as noted in draft-savola-mtufrag-network-tunneling-01.txt
[comments are welcome, btw!]

- you'll either need to set up tunnels *securely*, either a priori or 
dynamically.

- if done dynamically, this raises a significant number of issues
about the tunnels providing an easier means for external packet
injection, because it will be difficult to secure the tunneling.

- tunneling needs to be supported in hardware for hardware forwarding 
platforms, and this may be a deployment barrier.

-- 
Pekka Savola                 "You each name yourselves king, yet the
Netcore Oy                    kingdom bleeds."
Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings

---

From: Alia Atlas <[email-masked]>
Date: Thu, 23 Sep 2004 14:39:32 -0400

>>solve the problem for the new link case as well as the failed link case.

How so?  I can infer what one might do, but it is not described at all in 
your draft, and I'm not certain what this would do to the traffic load on 
the links.

How and when does the use of the tunnels get terminated?  What happens if 
there is a second change?  How is a new node handled, where multiple new 
links may be learned of simultaneously, or similarly a failed node?

Alia

---

From: mike shand <[email-masked]>
Date: Thu, 23 Sep 2004 20:05:24 +0100

>your draft, and I'm not certain what this would do to the traffic load on 

In draft-bryant 6.2 (for example), globally replace "failure" by "new 
adjacency" and that is pretty much it.

>How and when does the use of the tunnels get terminated?

When everyone has converged (as for link down). e.g. on a timer

>What happens if there is a second change?  How is a new node handled, 
>where multiple new links may be learned of simultaneously, or similarly a 
>failed node?

Unrelated second changes are generally a problem (even with ordered SPFs), 
but the related set of changes caused by node down/up turn out to be OK.

         Mike

---

From: Albert Tian <[email-masked]>
Date: Thu, 23 Sep 2004 17:51:13 -0700

Hi, Alex,

>      Cons: -requires additional changes to forwarding (beyond basic IP FRR)

Also micro-loops may involve multiple nodes when metrics are asymmetric, making
detection difficult.

Thanks,

Albert