Subject: discussion on fast notification work

From: Alia Atlas <[email-masked]>
Date: Wed, 6 Jul 2011 16:57:12 -0400

The last 2 IETFs, we have had discussions about the idea of fast
notification, as described in
draft-lu-fast-notification-framework, draft-lu-fn-transport-00, and
draft-csaszar-ipfrr-fn-00.

Since then, I have not seen substantial discussion or interest on the
mailing list.  If you are
interested in this work, have questions about it, or would like to see
RTGWG continue to discuss it,
please send email to this mailing list.  I'd like to see this
conversation happening here before IETF.

Thanks,
Alia

---

From: John E Drake <[email-masked]>
Date: Wed, 6 Jul 2011 14:53:42 -0700

Alia,

Is it okay for me to say that I think that this is a really bad idea and that I was glad that interest in it had waned?

Thanks,

John

Sent from my iPhone

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
> Of Alia Atlas
> Sent: Wednesday, July 06, 2011 1:57 PM
> To: [email-masked]
> Subject: discussion on fast notification work
> 
> _______________________________________________
> rtgwg mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/rtgwg

---

From: Alia Atlas <[email-masked]>
Date: Wed, 6 Jul 2011 18:03:20 -0400

John,

Absolutely - I have not seen positive comments about this being a
problem that needs solving and have seen concerns about the security
implications.

I would prefer to have any discussion about it here so that we do not
spend valuable f2f time on this unless there is significant interest.

Alia

---

From: Jeff Tantsura <[email-masked]>
Date: Wed, 6 Jul 2011 19:04:51 -0400

Hi Alia/John,

Thanks for your comments.

We have been listening very carefully and have taken all the critic rather seriously.

We have changed the way we distribute FNs, added authentication and prototyped/measured convergence times in networks of different diameters.
We have also added some additional clients (protocols to use FN)

Updated draft will be published soon.

We would really like to present our work.

Thanks! 

Regards,
Jeff  

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of John E Drake
Sent: Wednesday, July 06, 2011 14:54
To: Alia Atlas; [email-masked]
Subject: RE: discussion on fast notification work

Alia,

Thanks,

John

Sent from my iPhone

---

From: András Császár <[email-masked]>
Date: Thu, 7 Jul 2011 12:52:19 +0200

Dear All,

As a recap, the basic idea was to explore how one could approximate
1. near instantaneous notification of failures to neighbour and remote nodes
2. near instantaneous update of the FIB 

1 is approximated by a completely dataplane-based fast notification (FN) framework.
2 is approximated by pre-calculating and pre-downloading backup routes for RELEVANT failures and doing the FIB update from within the linecard.

Since last IETF, based on the comments we received, we have been working on (and prototyping) a method where FNs are propagated on the shortest path and each hop performs SHA256 authentication in the dataplane before forwarding the packet.

Important highlights proving feasibility:

- In a 1000-node area with a diameter of 20 hops and 500k external routes, the backup FIB even in a very bad case is not bigger than 30MB with very diverse ECMP (10 ECMP alternatives for each destination). The download of this backup FIB size should be no problem.

- A naive serial FIB update procedure after a failure in the above network takes less than 15ms within a dataplane card (assuming 5MT/sec memory performance and 1 memory controller). But there may be more intelligent approaches, such as a lazy (on-demand) FIB update.

- In reality, our calculations show that typically only nodes between 1 and 3 hops away need to prepare for a failure, i.e. failures only 1-2-3 hops away are RELEVANT (the above calculation assumes that for each destination needs to prepare for all failures of the 20-hop diameter)

- Very important: the FN packet always proceeds AHEAD OF normal data packets, so re-routed data packets typically find nodes on their way which have finished or almost finished reconfiguring. (In this way long links do not cause problems as both FN and normal data packets are delayed the same.)

- Pre-calculation complexity is in the same order of magnitude as with Not-Via, and it's done "offline"

Conclusions of our naïve implementation are the following:

- The solution can be implemented on a current platform, and we don't seem to use any operation that would make it less useful on other platforms including e.g. EZChip NP-4

- A FN packet can be originated in less than 200us (micro-sec) after failure detection 

- An FN packet can be forwarded at each hop in ca. 180us (this already includes SHA256 verification and duplicate check!)

András

> From: [email-masked] [mailto:[email-masked]] 
> On Behalf Of Alia Atlas
> Sent: 2011. július 6. 22:57
> To: [email-masked]

---

From: András Császár <[email-masked]>
Date: Thu, 7 Jul 2011 12:53:12 +0200

Hi John,

Why exactly do you think it is "a really bad idea"?

Kind regards,
András 

> On Behalf Of John E Drake
> Sent: 2011. július 6. 23:54
> Is it okay for me to say that I think that this is a really 
> bad idea and that I was glad that interest in it had waned?
> 
> Thanks,
> 
> John
> 
> Sent from my iPhone
> 
> 
> > From: [email-masked] 
> [mailto:[email-masked]] On Behalf
> > Of Alia Atlas

---

From: András Császár <[email-masked]>
Date: Thu, 7 Jul 2011 13:01:36 +0200

Alia,

The problem is clear: how to do fast fail-over in IP and LDP with full failure coverage in arbitrary network topologies. Several other ongoing proposals are targeting the same problem (just to mention Not-Via or MRT). So, I think there is consensus that the problem needs solving.

Per-hop authentication should minimise the security implications considerably. We have been working on a prototype doing this with SHA256 and we are adding this to the draft now.

Cheers,
András

> Sent: 2011. július 7. 0:03
> To: John E Drake
> Cc: [email-masked]
> Subject: Re: discussion on fast notification work
> 
> John,
>

---

From: John E Drake <[email-masked]>
Date: Thu, 7 Jul 2011 04:22:45 -0700

Please see my previous emails to the list.

Sent from my iPhone

> From: András Császár [mailto:[email-masked]]
> Sent: Thursday, July 07, 2011 3:53 AM
> To: John E Drake; Alia Atlas; [email-masked]

---

From: Anton Smirnov <[email-masked]>
Date: Thu, 07 Jul 2011 13:54:26 +0200

Hi András,

 > 2. near instantaneous update of the FIB

    I am no specialist in FIB implementations but it would appear to me 
that implementations and their requirements vary so much that intention 
itself of improving them all is incorrect and bound to fail.

 > 1. near instantaneous notification of failures to neighbour and 
remote nodes

    Here is my vision of the problem:
    My logic says that good inter-router notification cannot be made as 
fast as good intra-router API notification. So all good local repair 
techniques are intrinsically superior to [even good] inter-router 
notification approach. Superior first of all in speed of restoration but 
obviously things like deployment ease add attractiveness.
    That is, remote notification technique's niche is squeezed; it can 
be applied as an aid to local repair techniques in those cases where 
network topology provides redundancy but local repair techniques can't 
use it. Since more elaborate local repair techniques are being developed 
which expand their coverage, niche for remote notification technique is 
contracting to the point when people don't want to bother with it (not 
even care to criticize it :-) )

    I am guessing that authors of the proposal don't agree with this 
part: "My logic says that good inter-router notification cannot be made 
as fast as good intra-router API."
    May I suggest to authors to work on this perception? Otherwise I am 
afraid there again will be total misunderstanding and disinterest.

Anton

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Thu, 7 Jul 2011 14:06:31 +0200

I may missed something, since I found only 1 mail you wrote to this list before in this year. Based on that mail, I think you are mixing things; there you were writing about draft-kini-ospf-fast-notification-01, while Andras is speaking about draft-csaszar-ipfrr-fn-00. While the first one is just wanting to increase the speed of LSA advertisement, the second one is doing real FRR using only data plane. Am I right, were you speaking about the former draft?
BR,

Gabor Enyedi

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of John E Drake
Sent: Thursday, July 07, 2011 1:23 PM
To: András Császár; Alia Atlas; [email-masked]
Subject: RE: discussion on fast notification work

Sent from my iPhone

> > Is it okay for me to say that I think that this is a really bad idea 
> > and that I was glad that interest in it had waned?
> >
> > Thanks,
> >
> > John
> >
> > Sent from my iPhone
> >
> >
> > > draft-lu-fast-notification-framework, draft-lu-fn-transport-00, 
> > > and draft-csaszar-ipfrr-fn-00.
> > >

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Thu, 7 Jul 2011 14:19:58 +0200

Hi Anton,

"That is, remote notification technique's niche is squeezed; it can be applied as an aid to local repair techniques in those cases where network topology provides redundancy but local repair techniques can't use it. Since more elaborate local repair techniques are being developed which expand their coverage niche for remote notification technique is contracting to the point when people don't want to bother with it (not even care to criticize it :-) )"

When you are saying "local repair", are you speaking about just the LFA, or do you include techniques like Not-via?
BR,

Gabor

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Anton Smirnov
Sent: Thursday, July 07, 2011 1:54 PM
To: András Császár
Cc: [email-masked]
Subject: Re: discussion on fast notification work

    Hi András,

 > 2. near instantaneous update of the FIB  >

    I am no specialist in FIB implementations but it would appear to me that implementations and their requirements vary so much that intention itself of improving them all is incorrect and bound to fail.

    Here is my vision of the problem:
    My logic says that good inter-router notification cannot be made as fast as good intra-router API notification. So all good local repair techniques are intrinsically superior to [even good] inter-router notification approach. Superior first of all in speed of restoration but obviously things like deployment ease add attractiveness.
    That is, remote notification technique's niche is squeezed; it can be applied as an aid to local repair techniques in those cases where network topology provides redundancy but local repair techniques can't use it. Since more elaborate local repair techniques are being developed which expand their coverage, niche for remote notification technique is contracting to the point when people don't want to bother with it (not even care to criticize it :-) )

    I am guessing that authors of the proposal don't agree with this
part: "My logic says that good inter-router notification cannot be made as fast as good intra-router API."
    May I suggest to authors to work on this perception? Otherwise I am afraid there again will be total misunderstanding and disinterest.

Anton

On 07/07/2011 12:52 PM, András Császár wrote:
> Dear All,
>
> As a recap, the basic idea was to explore how one could approximate 1. 
> near instantaneous notification of failures to neighbour and remote 
> nodes 2. near instantaneous update of the FIB
>
> - In reality, our calculations show that typically only nodes between 
> 1 and 3 hops away need to prepare for a failure, i.e. failures only 
> 1-2-3 hops away are RELEVANT (the above calculation assumes that for 
> each destination needs to prepare for all failures of the 20-hop 
> diameter)
>
> - Very important: the FN packet always proceeds AHEAD OF normal data 
> packets, so re-routed data packets typically find nodes on their way 
> which have finished or almost finished reconfiguring. (In this way 
> long links do not cause problems as both FN and normal data packets 
> are delayed the same.)
>
> - The solution can be implemented on a current platform, and we don't 
> seem to use any operation that would make it less useful on other 
> platforms including e.g. EZChip NP-4
>
> - An FN packet can be forwarded at each hop in ca. 180us (this already 
> includes SHA256 verification and duplicate check!)
>
>
> András
>
>
>> From: [email-masked] [mailto:[email-masked]] On 
>> Behalf Of Alia Atlas
>> notification, as described in draft-lu-fast-notification-framework, 
>> draft-lu-fn-transport-00, and draft-csaszar-ipfrr-fn-00.
>>
>> mailing list.  If you are interested in this work, have questions 
>> about it, or would like to see RTGWG continue to discuss it, please 
>> send email to this mailing list.  I'd like to see this conversation 
>> happening here before IETF.
>>
>> Thanks,
>> Alia

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Thu, 7 Jul 2011 15:13:05 +0200

Hi Anton,

OK, I see what you meant. You are completely right, intra router notification must be much faster, we are just saying that we can be fast enough even in this way. Naturally, being a bit slower is a disadvantage. But we have advantages as well. E.g. LFA cannot do 100% single failure coverage - FN can; NotVia, LW-NotVia and MRC needs several extra IP addresses - FN doesn't need such addresses; FIFR needs per interface FIB - we do not need such things. And so on... Unfortunately, all the current solutions have drawbacks, ours is being a bit slower. We believe we can still meet the 50ms limit, so this drawback may not be really important compared to the advantages.
BR,

Gabor 

-----Original Message-----
From: Anton Smirnov [mailto:[email-masked]] 
Sent: Thursday, July 07, 2011 2:44 PM
To: Gábor Sándor Enyedi
Cc: John E Drake; András Császár; Alia Atlas; [email-masked]
Subject: Re: discussion on fast notification work

    Hi Gabor,
    I am not speaking of any particular draft, I am speaking of families of solutions - rerouting decision made entirely within router adjacent to failure vs. router close to failure point communicating with other routers to reroute traffic remotely.
    All FN drafts fall into category of remote notification; LFA, not-via and other works FN being compared with fall into category of local repair.

Anton

On 07/07/2011 02:06 PM, Gábor Sándor Enyedi wrote:
> Of John E Drake
>>> Behalf Of John E Drake

---

From: Anton Smirnov <[email-masked]>
Date: Thu, 07 Jul 2011 14:44:18 +0200

Hi Gabor,
    I am not speaking of any particular draft, I am speaking of families 
of solutions - rerouting decision made entirely within router adjacent 
to failure vs. router close to failure point communicating with other 
routers to reroute traffic remotely.
    All FN drafts fall into category of remote notification; LFA, 
not-via and other works FN being compared with fall into category of 
local repair.

Anton

---

From: Alia Atlas <[email-masked]>
Date: Thu, 7 Jul 2011 10:00:59 -0400

Hi Andras,

Thanks for the email better describing the idea and scaling.

2011/7/7 András Császár <[email-masked]>:
> Alia,
>
> The problem is clear: how to do fast fail-over in IP and LDP with full failure coverage in
> arbitrary network topologies. Several other ongoing proposals are targeting the same
> problem (just to mention Not-Via or MRT). So, I think there is consensus that the problem
> needs solving.

Not-Via, MRT, and LFA are all mechanism for a router to do local
repair in response to a local failure.

This proposal is an effort to take the idea to the next step and
attempt to have all the routers converge to the new topology very very
quickly.

Converging very very quickly has the advantage of not having
micro-forwarding loops for long.  It also means there's no need for
fast-reroute, since everyone learns about and reacts to the failure
rapidly enough.

The scaling, computation, and speed are real concerns with this
approach.  I was quite interested to see your numbers.  Thanks for
doing that work.  One issue, of course, is that there is a large
installed base of routers that are not NP-based; I'm not sure of the
practicality there.

> Per-hop authentication should minimise the security implications considerably. We have been working on a prototype doing this with SHA256 and we are adding this to the draft now.

I look forward to it.

Alia

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 07 Jul 2011 19:19:09 -0400

I agree with John that there doesn't seem to be a problem to solve.

To add to that.

In this case there seem to be consensus that this was a bad idea.  If
the authors want to change that consensus, a draft should come well
ahead of the meeting with discussion on the list, and only then if
there is interest, should be spend meeting time on this.

For example, on the list we can discuss what vendor equipment was used
in the networks that were prototyped/measured.  We don't want a
protocol fix that addresses a bad implementation of a perfectly good
protocol.  I prefer draft first, well in advance of the meeting, then
consider a time slot allocation after discussion on list.

[ begin aside

The issue is whether it is possible to keep the flooding latency low
relative to geographic delay and detection time.  A somewhat worst
case flooding delay in a good implementation consists of 1) receive
packet on line card, check if it is a known change, 2) send it to
another processor to verify if it is known, 3) receive it agains and
recheck, 4) send it again to line cards, 5) receive it and send it on
the line interface.  Some implementations multicast from the receiving
node, yielding only one internal hop, for two context switches total.

Even absent of geographic delay, detection time is order 10 msec.  If
we assume a context switch time of 1 msec even receiving a packet
three times within the same node adds on the order of 3 msec per hop.

In a good implementiation, this processing is done on the line cards
which have little else to do other than react to low effort near real
time requirements such as protection and flooding and installing new
state at a slightly lower priority (and with good CPU starvation
prevention in the scheduling).  If the line card processor is doing
real time work and there is a desire to reduce latency, most cards
today can support a change to the clock interrupt from a 1000 Hz clock
to something a bit faster.  The down side is increasing the amount of
time spent in the RTC interrupt code.

In a bad implementation there is a chance that a CPU delays flooding
while waiting for an SPF or for some high CPU user link BGP to finish
up some increment of work.  Then the delays can be quite long.

One advantage of flooding is that after a fault the flooding does not
rely on assumptions about the remaining topology.  Multiple simultaous
faults due to failure of a shared resource can and often do occur.
Any mechanism that relys on forwarding or relies on source routing
through a best guess at what links remain will fail to deliver
notifications in such a case.  In that case we are back to the
flooding delay anyway, so might as well work on keeping that short.

Maybe on the list the authors can describe the motivation, the target
flooding or notification delay, and how the shortcomings discussed
previously are addressed.

end aside ]

Curtis

In message <[email-masked]>
Jeff Tantsura writes:
> We have changed the way we distribute FNs, added authentication and
> prototyped/measured convergence times in networks of different
> diameters.  We have also added some additional clients (protocols to
> use FN)
>

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 07 Jul 2011 19:43:38 -0400

Anton,

A key point made below is.

  Protection at the PLR is always faster than inter-node protection.

That said, if someone wants fast protection with full coverage, run
MPLS with RSVP-TE and enable FRR and join the rest of the world that
has already figured that out.  Then there is complete (single failure)
protection at every PLR.  If multiple failures occur, then precomputed
protection is impractical, notification schemes don't work, and
flooding needs to work well and SPF and/or CSPF and installation of
new FIB needs to be fast.

Of course, those that think the idea of running MPLS is way too scary
or think that reinventing the wheel is great fun can continue this
conversation as long as they like.  After all if people didn't think
MPLS was scary we wouldn't even have IPFRR in the first place.

Curtis

In message <[email-masked]>
Anton Smirnov writes:

    Hi András,

Anton

---

From: András Császár <[email-masked]>
Date: Fri, 8 Jul 2011 10:33:45 +0200

Hi Anton, 

> itself of improving them all is incorrect and bound to fail.

Just like any other IPFRR solution, IPFRR-FN assumes that backup alternative routes are pre-calculated and pre-downloaded to the linecards. The specification should and does NOT mandate any specific implementation - this is completely platform dependent.

> notification approach. 

The above opinion and also that of John, all challenge that IPFRF-FN is not relying on local repair.

Local repair is a principle that would be good to have, I agree. But, this is the root cause why LFA cannot cannot give 100% coverage. *SOME* information must be given to even remote nodes to do forwarding differently. Not-Via, MRT and MRC are trying to overcome this problem by squeezing some information into EVERY data packet on detour. And neither of these solutions have, as of yet, consensus, since HACKING this info onto the packet brings additional complexities.

Now, if there is *no solution* that provides 100% coverage AND has WG consensus, then we should look at the cause for the problem - local repair.

But IPFRR-FN still sticks to other principles of classic IPFRR: pre-computation and pre-installation.

And still you are right: if it was impossible or infeasible to notify remote nodes of failures quickly enough, or if it was impossible/infeasible to prepare for remote failures, then remote repair cannot fly.

We are suggesting that both notification and preparation are actually possible and even feasible.

And yes, it may be not exactly as fast as local repair but:
- It is still fast enough and can deliver sub-50ms repair
- There is actually no local repair based IPFRR solution with 100% coverage and consensus

Regards,
András

---

From: András Császár <[email-masked]>
Date: Fri, 8 Jul 2011 10:48:03 +0200

Hi Alia,

> attempt to have all the routers converge to the new topology very very

Please note that in IPFRR-FN (http://tools.ietf.org/html/draft-csaszar-ipfrr-fn) 
we are NOT suggesting ANY modification to IGPs.
So, in fact we are not changing the convergence properties of ISIS or OSPF at all. (This has been suggested in http://tools.ietf.org/html/draft-kini-ospf-fast-notification but this thread should NOT be about that. It's an OSPF WG matter.)

Looking at IPFRR-FN, while it does not affect IGP convergence, it can be said that IPFRR-FN lets the routers converge onto a consistent backup forwarding state, which is actually mostly identical to what the IGP will calculate once it converges. (Since the pre-calculation was also done on the IGP topo database.)

> installed base of routers that are not NP-based; I'm not sure of the

Please note that our prototype/measurements are not based on NP-based linecard either. By mentioning NP, which is a completely different platform from ours, I was just highlighting that after discussing with a guy more familiar with programming NP we believe that there is no hinderniss for IPFRR-FN to be implemented on NP, either.

András

---

From: András Császár <[email-masked]>
Date: Fri, 8 Jul 2011 11:09:32 +0200

Hello Curtis, 

> We don't want a
> protocol.

Please note we are not trying to develop a protocol fix.
Currently there exist not standard protocol for
- IPFRR
- with 100% failure coverage

There are proposals only. So there is nothing to fix.

Note that IPFRR-FN has no intention to fix/improve OSPF/ISIS routing convergence. Instead, we acknowledge that there are practical reasons why IGPs typically do not provide fail-over times below a few hundred milliseconds. But if sub-50ms fail-over is really needed (which could actually be another thread for debate IMHO), then something else is needed.

We are almost finishing the new drafts, but it is unlikely we can submit them much earlier before Monday's cut-off.

András

> On Behalf Of Curtis Villamizar
> Sent: 2011. július 8. 1:19
> To: Jeff Tantsura
> Cc: [email-masked]
> In message 
> <[email-masked]
> .ericsson.se>
> Jeff Tantsura writes:
> >  
> > Hi Alia/John,
> >  
> [mailto:[email-masked]] On Behalf Of John E Drake

---

From: András Császár <[email-masked]>
Date: Fri, 8 Jul 2011 11:16:11 +0200

> has already figured that out.  

Yes, that is right, with RSVP-TE you can solve it. We haven't challanged the fact that there are operators who do not want to bother with at least RSVP-TE (but rather use LDP) or do not want to bother with MPLS at all.

> Then there is complete (single failure)

Agreed, speeding up FIB installation is an important task on most platforms, although that seems to me more of an implementation question.

András

---

From: Anton Smirnov <[email-masked]>
Date: Fri, 08 Jul 2011 11:36:32 +0200

Curtis,
    yes, that was my message though without giving too much credit to 
LFA versus other local repair methods and without being too MPLS-centric.

Anton

On 07/08/2011 01:43 AM, Curtis Villamizar wrote:
> In message<[email-masked]>
> Anton Smirnov writes:
>
>      Hi András,
>

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Fri, 8 Jul 2011 12:35:03 +0200

Hi Curtis,

At this point I feel, that there was a terrible mistake, and drafts were mixed. I try to make clear what the situation is.

Draft 1. - draft-kini-ospf-fast-notification-01:
This draft is trying to increase the speed of LSA/LSP propagation. This problem can be easily challenged, since currently the bottleneck of convergence time is not the propagation. Later this may change, but currently you are right, this draft may have no attention.

Draft 2. - draft-csaszar-ipfrr-fn-00
This is a full-fledged protection technique for IP (and LDP) networks, exactly like e.g. LFA, and trying to address the same problems. I know, that several people think that protection MUST be local, but it is not true. The difference between protection and restoration is that while restoration does all the work AFTER the failure, protection is proactive, and only some minor reaction is needed when the failure occurs (e.g. switching to the precomputed detours). Therefore we were thinking that: "OK, everybody wants to do local protection for IP, but why? They want to avoid the latency of propagating an information packet, but that is not an issue for 99% of the areas! We have 50ms, in the very worst case 10-15ms is enough to get through most of the areas... So some not local but still protection technique may fit to the requirements." So we thought that we can try to do some non-local PROTECTION for IP, and see what we get for the price of being say 10ms slower than the LFA, NotVia, or any other regular IPFRR. We got that we can protect 100% of single link, node and single SRLG failures, we get to the shortest paths after the failure immediately (so no second convergence is needed after the new topology was explored), we do not need any extra protection address or even tunneling.
Recall, that we are speaking about a protection mechanism, not some OSPF/IS-IS hack. So this draft describes a mechanism, where alternatives are predownloaded, and failure reaction is done without involving the control plane. This means that we need time for:

1. detecting the failure - T1
2. propagating the notification - T2
3. doing the failover - T3

The third one is now needed at all the routers, but it is done parallel, so the network is fully recovered when the last node is reconfigured, T1+T2+T3 time after the failure. And with a "local" protection? We would need T1+T3 time. We are saying that we can afford spending that extra T2 time in most of the networks to get the previous advantages.

Please do not mix the two drafts!
BR,

Gabor

P.S.: We are currently modifying draft-csaszar-ipfrr-fn-00, and address its most important problems (e.g. authentication). If you can wait till Monday, it may worth to read the new version.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Curtis Villamizar
Sent: Friday, July 08, 2011 1:44 AM
To: Anton Smirnov
Cc: [email-masked]
Subject: Re: discussion on fast notification work 

Anton,

That said, if someone wants fast protection with full coverage, run MPLS with RSVP-TE and enable FRR and join the rest of the world that has already figured that out.  Then there is complete (single failure) protection at every PLR.  If multiple failures occur, then precomputed protection is impractical, notification schemes don't work, and flooding needs to work well and SPF and/or CSPF and installation of new FIB needs to be fast.

Of course, those that think the idea of running MPLS is way too scary or think that reinventing the wheel is great fun can continue this conversation as long as they like.  After all if people didn't think MPLS was scary we wouldn't even have IPFRR in the first place.

Curtis

    Hi András,

Anton

---

From: Alia Atlas <[email-masked]>
Date: Fri, 8 Jul 2011 09:42:00 -0400

Andras,

> - It is still fast enough and can deliver sub-50ms repair

The basic concern about non-local repair is the speed of light delay.
If one is looking at an intercontinental network, these delays add up
so that sub-50ms is not physically possible.

I think your argument is that the notification arrives with/before the traffic,
but that reasoning isn't very convincing to me...  Perhaps you can explain
it better here?

Alia

---

From: Alia Atlas <[email-masked]>
Date: Fri, 8 Jul 2011 09:53:01 -0400

Hi Gabor,

2011/7/8 Gábor Sándor Enyedi <[email-masked]>:
>Therefore we were thinking that: "OK, everybody wants to do local protection for IP, but why? They want to avoid the latency of propagating an information packet, but that is not an issue for 99% of the areas! We have 50ms, in the very worst case 10-15ms is enough to get through most of the areas... So some not local but still protection technique may fit to the requirements."

[Alia] I think that the idea of this 10-15ms is problematic for
intercontinental networks.
If, according to wikipedia, the delay through optical fiber is about
1000km/5ms - then that means to go from Boston to San Francisco, takes
approximately 21.6ms.

Now, you may be saying that there are a large number of networks with
significantly more constrained distances where this could apply...

> The third one is now needed at all the routers, but it is done parallel, so the network is fully recovered when the last node is reconfigured, T1+T2+T3 time after the failure. And with a "local" pr…

[Alia] I do think an advantage of this approach is the lack of concern
about micro-forwarding loops during convergence.  Of course, those can
still be an issue with just cost changes, so I don't think it changes
the need for such technology.

Alia

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Fri, 8 Jul 2011 17:08:29 +0200

Hi Alia,

Andras already went home, so I try to answer your question. Actually, this is the first good reason against FN today...

So, when I was saying in my previous mail that we think we can live with that "T2" time, I was not completely precise. I still believe, that in most cases T2 must not be more than 10-15ms, but your right, there are huge links with serious delay. Let's see such an example, and check whether local protection is better or not. 

|
A--H
|  |     
B  G
|  |   
C  F
|  |
D--E
|

If there is problem with the figure, I just wanted to draw a cycle with 6 nodes, where packets enter to the network at node D and leave it at node A. Suppose that the two parts of the network are at the other side of the Atlantic ocean, say A, B, G, H are in America and C, D, E, F are in Europe. In this way both link B-C and F-G have huge delay (say 40ms). Suppose that all the link costs are uniform (so the shortest path is D-C-B-A) and link B-C goes down, so we need to do something. Since there is no other possibility, the failed link cannot be bypassed in America, we need to "ask" for help from nodes in Europe in order to use the "other" transatlantic link. Observe how unrealistic this case is; after the failure, the shortest path from B to A crosses the ocean TWICE!

What will happen, if we apply FN here? Suppose that we are right, and we can forward FN packets extremely rapidly (as it is the case), so the speed of an FN packet is (almost) equal to a normal packet's speed. In order to make the example simple, now suppose that processing FN packets takes no time (it is not 0, but it will not make any difference, if you want, I can later explain why). So when B detects the failure, it will send out the notification (A will send it out as well, but there is a bigger latency along that path, so it is not important). You are right, the packet will not make it in time, and more than 50ms is needed to get to node D after the failure (there is the detection time). But none of the packets will be lost, packets received by B will be sent back to C. Since those packets will get exactly the same delay thanks to link B-C, when they arrive to C, C is already reconfigured (since the FN packet was there before), and they will be sent to D. The situation is the same with D. So when will node A get the first packet after the failure? We can say that this time is the sum of the delays of link B-C, C-D, D-E, E-F, F-G, G-H, H-A. And yes, there can be some reordering, but currently the hosts can deal with it (see e.g. RTP hosts).

What is the situation if we have some local repair? If we have some local repair at node B, it will send the packets back to C as well. So after the failure the packets will follow path D-C-B-C-D-E-F-G-H-A. When will node A get the first packet after the failure? We get it again, we need to sum the delays of link B-C, C-D, D-E, E-F, F-G, G-H, H-A. OK, now we do not have reordering...

Actually, you may say that if we need to forward the FN packets too far (I mean too many hops away, here physical distance is not an issue), we may cause congestion. You are right, but first, we found that usually we need to reroute quite locally, i.e. we do not need to get farther then 2-3 hops. Second, you cannot avoid this problem if you use some local rerouting; sooner or later the IGP will converge, and you will need to change the routing of C, and at that point, C needs to send both packets in link B-C and C-D back to D, which may cause a congestion.

OK, this example may not cover all the possible situations, but I think based on this you may found out all the remaining ones. No doubt, this solution is not perfect, I am just saying that this is the best I know for IP networks. For plain IP it is better even than using maximally redundant trees, since it can deal with SRLG-s, and MRT-s cannot. Moreover, it is as simple as it is possible, which is not the case with redundant trees, as you saw yesterday. :)
BR,

Gabor

P.S.: We are just modifying the draft to use flooding instead of redundant trees and SHA-256 authentication. Even with this, in our prototype the forwarding time of an FN packet was almost equal to the forwarding time of a big (1500 byte) data packet.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Alia Atlas
Sent: Friday, July 08, 2011 3:42 PM
To: András Császár
Cc: [email-masked]
Subject: Re: discussion on fast notification work

Andras,

The basic concern about non-local repair is the speed of light delay.
If one is looking at an intercontinental network, these delays add up so that sub-50ms is not physically possible.

I think your argument is that the notification arrives with/before the traffic, but that reasoning isn't very convincing to me...  Perhaps you can explain it better here?

Alia

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 08 Jul 2011 22:21:57 -0400

Regardless as to whether the discussion mixed aspects of the various

>> happening here before IETF.

I have to agree that there has not been interest in this work.

Curtis

In message <[email-masked]>
Gábor Sándor Enyedi writes:
>  
> Hi Curtis,
>  
> At this point I feel, that there was a terrible mistake, and drafts
> were mixed. I try to make clear what the situation is.
>  
> Draft 1. - draft-kini-ospf-fast-notification-01: This draft is trying
> to increase the speed of LSA/LSP propagation. This problem can be
> easily challenged, since currently the bottleneck of convergence time
> is not the propagation. Later this may change, but currently you are
> right, this draft may have no attention.
>  
> Draft 2. - draft-csaszar-ipfrr-fn-00 This is a full-fledged protection
> technique for IP (and LDP) networks, exactly like e.g. LFA, and trying
> to address the same problems. I know, that several people think that
> protection MUST be local, but it is not true. The difference between
> protection and restoration is that while restoration does all the work
> AFTER the failure, protection is proactive, and only some minor
> reaction is needed when the failure occurs (e.g. switching to the
> precomputed detours). Therefore we were thinking that: "OK, everybody
> wants to do local protection for IP, but why? They want to avoid the
> latency of propagating an information packet, but that is not an issue
> for 99% of the areas! We have 50ms, in the very worst case 10-15ms is
> enough to get through most of the areas... So some not local but still
> protection technique may fit to the requirements." So we thought that
> we can try to do some non-local PROTECTION for IP, and see what we get
> for the price of being say 10ms slower than the LFA, NotVia, or any
> other regular IPFRR. We got that we can protect 100% of single link,
> node and single SRLG failures, we get to the shortest paths after the
> failure immediately (so no second convergence is needed after the new
> topology was explored), we do not need any extra protection address or
> even tunneling.  Recall, that we are speaking about a protection
> mechanism, not some OSPF/IS-IS hack. So this draft describes a
> mechanism, where alternatives are predownloaded, and failure reaction
> is done without involving the control plane. This means that we need
> time for:
>  
> The third one is now needed at all the routers, but it is done
> parallel, so the network is fully recovered when the last node is
> reconfigured, T1+T2+T3 time after the failure. And with a "local"
> protection? We would need T1+T3 time. We are saying that we can afford
> spending that extra T2 time in most of the networks to get the
> previous advantages.
>  
> P.S.: We are currently modifying draft-csaszar-ipfrr-fn-00, and
> address its most important problems (e.g. authentication). If you can
> wait till Monday, it may worth to read the new version.
>  
>  
>

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 08 Jul 2011 22:35:16 -0400

> 1000km/5ms - then that means to go from Boston to San Francisco, takes

Closer to 34 msec measured.  This is due to the fiber not being laid
in a straight line.

Not that it alters your point any.

This is also why detection time is usually taken to be a nominally
order 10 msec.  If a break in a 20 msec fiber occurs in the middle,
then it will be 10 msec before either end sees any signal degregation
(lights out in this case) and knows about the fault.  There is usually
a small hold up time before declaring the link down (a few msec).  At
that point The fastest possible protection is when both sides
independently make a local repair.

Lets also not go down the "who cares" rathole wrt the 50 msec number.

> the need for such technology.

Microforwarding loops are always a concern in hop by hop forwarding.

Like it or not, RSVP-TE has the advantage that the path either works
or it doesn't.  Either the traffic arrives somehow, maybe not
optimally during a protection transient, or it gets blackholed.

Again, lets not go too far down the "who cares" rathole.

Curtis

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 08 Jul 2011 23:12:52 -0400

In message <[email-masked]>
Alia Atlas writes:
> I think your argument is that the notification arrives with/before the
> traffic, but that reasoning isn't very convincing to me...  Perhaps
> you can explain it better here?
>  
> Alia

Its that faster-light again.  Fixes just about anything!  :-)

Curtis

btw - Typical optical reach with latest transmission equipment and
good clean fiber is on the order of 2,000 km today (a bit more).
Therefore links are rarely over 10 msec, except across oceans which
can be much longer.  Network diameters can be a few 100 msec.  Unless
they use satellites in which case the delays can be absurdly long
(1/4-1/2 sec RTT for one hop to a LEO satellite).

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 08 Jul 2011 23:31:01 -0400

If there is a failure of the link B-C, then traffic can't go B-C-B.

Assume that the failure is in roughly the middle of the ocean and the
fiber is broken in both directions.  At each end, a local repair is
done.  With MPLS FRR (or IPFRR), the path is D-C-D-E-F-G-H-A (the
merge point can be closer to the egress than the other end of the
failed link.

The case that would be more interesting is if A-B failed.  MPLS FRR
works fine for this case, but IPFRR is a bit more problematic with the
two hops to get to the alternate route (ie: D-C-B-C-D-E...).

For such a case, where two links cross an ocean, you would think that
the provider might be smart enough to put a link between B-G and C-F
if B-C and F-G are the cross Atlantic links.  That way neither working
or protection traffic never crosses the ocean more than once.  Given
that cross Atlantic links are really expensive that would seem like a
reasonable thing to do.

Curtis

In message <[email-masked]>
Gábor Sándor Enyedi writes:
> What will happen, if we apply FN here? Suppose that we are right, and we can forward FN packets extremely rapidly (as it is the case), so the speed of an FN packet is (almost) equal to a normal packet's speed. In order to make the example simple, now suppose that processing FN packets takes no time (it is not 0, but it will not make any difference, if you want, I can later explain why). So when B detects the failure, it will send out the notification (A will send it out as well, but there is a bigger latency along that path, so it is not important). You are right, the packet will not make it in time, and more than 50ms is needed to get to node D after the failure (there is the detection time). But none of the packets will be lost, packets received by B will be sent back to C. Since those packets will get exactly the same delay thanks to link B-C, when they arrive to C, C is already reconfigured (since the FN packet was there before), and they will be sent to D. The situati!
 on is the same with D. So when will node A get the first packet after the failure? We can say that this time is the sum of the delays of link B-C, C-D, D-E, E-F, F-G, G-H, H-A. And yes, there can be some reordering, but currently the hosts can deal with it (see e.g. RTP hosts).

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Sat, 9 Jul 2011 09:24:11 +0200

Curtis,

Forgive me, I made a mistake. Initially, there were only 6 nodes in the cycle, then I modified it, but not consequently. Naturally, this is an example for the failure of link A-B. Please consider the example as I would wrote there " link A-B goes down". Sorry for confusing you or anyone else.

After reconsidering the example, do you still think that this idea does not worth even to speak about it?

Gabor

________________________________________
Feladó: [email-masked] [[email-masked]]
Küldve: 2011. július 9. 5:31
Címzett: Gábor Sándor Enyedi
Másolatot kap: Alia Atlas; András Császár; [email-masked]
Tárgy: Re: discussion on fast notification work

Curtis

---

From: Kireeti Kompella <[email-masked]>
Date: Sat, 9 Jul 2011 13:39:19 -0700

On Jul 9, 2011, at 0:24, "Gábor Sándor Enyedi" <[email-masked]<mailto:[email-masked]>> wrote:

"You can speak your mind
But not on my time" -- B. Joel

Kireeti

---

From: Curtis Villamizar <[email-masked]>
Date: Sat, 09 Jul 2011 21:51:33 -0400

Gabor,

Work that are worth continuing is work that service providers would
like to deploy or that has some compelling value.  I haven't seen any
provider interest or a compelling value.

By the example you are implying that the value is pushing the
protection back to a prior node.  That was rejected in MPLS FRR
becuase 1) FRR is fastest at the PLR, 2) protection is deployed for
the benefit of a minority of traffic with strict requirements (who are
paying a lot more for service) and diffserv takes case of any interim
congestion for that high priority traffic and 3) protection is
temporary and the ultimate solution is to reroute the working path and
get it protected again.

Moving the repair to a prior node increases the period during which
loss occurs but reduces the delay once protection occurs.  This is a
tradeoff that was discussed a decade ago when MPLS FRR was discussed
and the decision was made to favor the faster repair.

I don't see why that hasn't served the industry well and don't see why
it needs to be different for IPFRR.

So I see that technical advantage but don't see the demand for this.

Curtis

In message <[email-masked]>
Gábor Sándor Enyedi writes:

Curtis,

Gabor

Curtis

---

From: Curtis Villamizar <[email-masked]>
Date: Sat, 09 Jul 2011 21:56:05 -0400

In message <[email-masked]>
Kireeti Kompella writes:

> But not on my time" -- B. Joel

That seemed a bit harsh.

I prefer the "I see the technical advantage but ..." summary.

Maybe I need to lighten up.  :-)

Curtis

---

From: András Császár <[email-masked]>
Date: Mon, 11 Jul 2011 11:00:43 +0200

Hi Alia,

<BACKGROUND>
A node, in FN-flooding mode, multicasts the received FN message to ALL OSPF neighbours in the same area. To facilitate this, the IGP in each node pre-installs a multicast route entry for the multicast group address of the FN service and adds a link to each of its neighbour to the if list of the multicast route. The multicast route is flagged as a bidirectional multicast, i.e. the incoming packet is replicated to each i/f in the list except the incoming i/f.

Since this is kind of dataplane based flooding, the linecards need to check for duplicate FN (i.e. flooding may cause the FN message to loop back) before forwarding. (On our not too recent HW platform, an FN packet spends 180 micro-sec in the linecard including this duplicate check AND SHA256 authentication before a replica appears on the oifs.)
</BACKGROUND>

A key point: in order to facilitate sub-50ms fail-over, a node remote to the failure does NOT need to have changed its FIB within 50ms, but it needs to have changed its FIB by the time re-routed packets reach it. Non-re-routed packets just keep going on the old path until meeting up a node which is already re-configured.

During fail-over, a node may be in two states when considering a given destination:
- Old next-hop
- New NH (activated backup)

In case of the PLR, the old NH is dead, leading to packet loss. Any other node with old NHs keep forwarding traffic towards the PLR.

A PLR after detecting the failure:
- originates and sends an FN packet (200 micro-sec)
- starts FIB update within the linecard (just like in any other IPFRR, e.g. LFA)

So, connectivity is interrupted as long as the PLR performed the FIB update (T3). Then packets go to a new NH, i.e. reaching it after T3+T2 time, i.e. T2 is the propagation time to re-use Gabor's notation.

The FN packet reaches 1-hop radius nodes in T2+200us, then the one-hop radius nodes perform FIB update, and they are ready by T2+200us+T3. 

So, if the nodes perform FIB update roughly in the same time, then the 1-hop node has an old route for 200usec after receiving the first re-routed packet. 

So, in the end, traffic finds not-yet-ready nodes altogether for T3 + k x 200us time in the worst case, i.e. T3 FIB update in the PLR then in each hop 200 micro-sec.

In an extreme case, it may happen that the PLR needs to change the route and then only a remote node k hops away makes another repairing route change.

In this case: 
FN reaches the remote node in: 200us + k x (T2 + 200us).
Remote node is ready with FIB by 200us + k x (T2 + 200us) + T3

First re-routed packet reaches remote node by T3 (PLR FIB update) + k x T2.
I.e. remote node keeps forwarding packets on old route for maximally (k+1) x 200us. With any reasonable network diameter, this is lower than 4-5ms.

András

> From: Alia Atlas [mailto:[email-masked]] 
> Sent: 2011. július 8. 15:42
> To: András Császár
> Cc: Anton Smirnov; [email-masked]

---

From: Kireeti Kompella <[email-masked]>
Date: Mon, 11 Jul 2011 14:02:09 -0700

>> But not on my time" -- B. Joel

Wasn't intended that way.

The harsh reality is the limited time and limited processing capacity I have [where is Eldon Tyrell when you need him???]

Another way of looking at the quote is, don't throttle the sender -- but do allow receivers to filter.  That's not harsh, is it?

I spent considerable time working out the transatlantic example -- what data path is being considered, what link is assumed to fail.  I got there eventually, but a simple "Consider the path D->A, and suppose link BA [not CB] fails" would have saved me time.

Beyond that, I fail to see the benefit of this approach, and several things about it make me uneasy, if not queasy.  I'm not sure the "technical advantage" of this outweighs the concerns ... and am not willing to put in the time to work it out.

Kireeti.

---

From: András Császár <[email-masked]>
Date: Tue, 12 Jul 2011 08:37:49 +0200

Hi Kireeti,

> Beyond that, I fail to see the benefit of this approach, and 
> several things about it make me uneasy, if not queasy.  I'm 
> not sure the "technical advantage" of this outweighs the 
> concerns ... and am not willing to put in the time to work it out.

I understand you don't have time to work out any details of some else's proposal but given a little time could you share your concerns at least: we'd try to answer those if possible.

Thanks,
András

---

From: mike shand <[email-masked]>
Date: Tue, 12 Jul 2011 13:52:32 +0100

There seem to be two issues here, of which the first is perhaps the most 
pertinent :-

1) Is there any interest in adding significant complexity in order to 
provide 100% protection coverage? The evidence seems to be that there is 
not. There have been a number of such solutions (mine included) proposed 
both here and in the academic literature, and so far none of them have 
received overwhelming support. Those wanting 100% protection seem quite 
happy to invoke MPLS FRR.

2) Is non-local repair a viable option? The arguments against this seem 
to be:-

    a) However fast the propagation is made, it is still limited by
    "speed of light". It has been argued that the data packets are also
    so limited, so it doesn't matter, but I still have to be convinced
    that this is always true.
    b) The pre-computation of remote repairs significantly increases
    both the computational complexity and the size of FIB information
    required. It is not clear how this scales in large real world SP
    topologies.
    c) It is asserted that "re-route points" are typically only 2 or 3
    hops away. This is true, but there are significant counter examples.
    This seems to lead to a choice between less than 100% repair
    coverage or even more complex remote repair scenarios.

My feeling is that to change from a local repair to a remote repair 
paradigm requires the demonstration of very significant benefits, and I 
haven't seen that. Indeed, quite the opposite.

     Mike

---

From: Tony Li <[email-masked]>
Date: Tue, 12 Jul 2011 08:27:52 -0700

On Jul 12, 2011, at 5:52 AM, mike shand wrote:

> Is there any interest in adding significant complexity in order to provide 100% protection coverage?

I believe that there is interest and benefit from providing 100% protection coverage without resorting to MPLS.

However, adding significant complexity is NOT the intent.  ;-)

From a strategic point of view, it would be very beneficial for a pure packet switching network to provide similar functionality to the connection oriented overlay hybrid approach that MPLS represents.  This would allow networks to have the benefits of faster protection without the maintenance overhead of MPLS.

The alternative is to admit that IP is inferior to MPLS.

Regards,
Tony

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 12 Jul 2011 12:20:40 -0400

In message <[email-masked]>
Tony Li writes:
> I believe that there is interest and benefit from providing 100%
> protection coverage without resorting to MPLS.
>  
> > From a strategic point of view, it would be very beneficial for a pure
> > packet switching network to provide similar functionality to the
> > connection oriented overlay hybrid approach that MPLS represents.
> > This would allow networks to have the benefits of faster protection
> > without the maintenance overhead of MPLS.
>  

We can always count on you for a content free slogan.

> Tony

Tony,

IP and MPLS (RSVP-TE) do different things.  IP is massively scalable.
MPLS is not as scalable and by itself does nothing (which some
transport guys are a long way from figuring out).  MPLS has TE
capability and has better support for protection.  IP over MPLS is a
powerful combination.  IP alone within a provider domain is a little
more simple, but not by much.

IPFRR is inferior to MPLS FRR.  The latter can never form transient
microloops in the post protection transition and has other drawbacks.
Get used to it.

The whole point of IPFRR (if there is a point to IPFRR at all) is to
provide a simple solution to improve on IP convergence.  If a more
complex solution is needed, trying to retrofit full coverage
protection onto IP is a losing proposition.  MPLS is not all that
complicated and with MPLS mesh groups and zero bandwidth reservation
can be trivial to configure for FRR benefits only.

Curtis

---

From: "Manfredi, Albert E" <[email-masked]>
Date: Tue, 12 Jul 2011 15:49:07 -0500

> The alternative is to admit that IP is inferior to MPLS.

Heh! Since MPLS sort of spun off from IP over ATM, I guess we'd be back to those debates of the 1990s!

Bert