Subject: FW: Review request for draft-lu-fast-notification-framework-00.txt

From: Albert Tian <[email-masked]>
Date: Tue, 9 Nov 2010 01:03:07 -0500

Hi Stephane/Oliver,

thanks very much for all your valuable comments.

What we are saying essentially are:

A) fast convergence is important in its own right. LFA and other LR mechanisms provide benefits but they can not replace fast convergence, for coverage issues, for additional complexity etc.

B) there are several aspects in fast convergence: detection time, propergation time, SPF time, RIB/FIB time etc. We need to attack and reduce all of them. The flooding time is one part of the propergation delay, and that is what we are trying to reduce in this draft. 

C) We do not want to be tied down to a specific fast notification solution at this stage, and want to be able to change the engine down the road. Alia has pointed out some race conditions yesterday among many other things and we really appreciate that.

D) we started with fast convergence as an application, but we think in the future other application may also benefit from a fast notification framework.

BTW are you at the IETF Beijing? If so we could meet at the back of routing-area open meeting (Tue@1700 or end of meeting, which ever is earlier) if you are around. Others are also welcome to join us.

Thanks,
Albert

On Mon, Nov 8, 2010 at 1:00 PM,  <[email-masked]> wrote:
>
>>>>Moreover I think that network wide convergence will never permit to
> achieve the same level of service (in term of
>>>>packet loss) than local protection mechanism like LFA, or FRR using
> MPLS TE. So if you to achieve tens of msec packet
>>>>loss, LR is needed absolutely.
> [luw] What is the base of this conclusion? Even RFC[5714] itself 
> admits that it cannot guarantee 100% coverage.
>
> [sli] clearly with LFA you can't have 100% coverage inside a network 
> (except if you build it based on LFA limitations :) ) but there is 
> some solutions that can permit to approach the 100% coverage. But to 
> be more clear about what I said : protection/local repair mechanism 
> have not the same purpose than network wide convergence. And you will 
> never be able to achieve a network wide convergence with the same 
> level of packet loss than the one proposed by protection mechanism like TE or LFA :
> basically, in protection mechanism, there is no computation involved 
> when the failure occurs (pre computation is done), the FIB/LFIBs are 
> just switching states. So both are complementary, LFA/TE are not there 
> to replace network wide convergence, it's just a temporary mechanism 
> until convergence occurs.
>
>>>Other point, when you talk about current mechanism of LSP ack
> mechanism in current IGPs (paragraph 3) that involves
>>>control plane and so slow down the network wide convergence, you are
> right (purely theorically) but this is clearly
>>>necessary I think. It would be bad if you start flooding corrupted
> information network wide ...
>
> [luw] Were you talking about paragraph 3 under "Introduction"? That 
> paragraph simply says "if only others know our situations...".
>
> [sli] Here was the statement I was referencing : "Regular routing 
> protocol performs the flooding in store-and-forward
>   manner.  While this is reliable (retransmission) and secure
>   (adjacency check), it involves control plane operation and the
>   control plane to data plane communication.  It inevitably drags the 
> network wide convergence"
>
>>>Other point, how are you planning to manage churn of events with your
> framework ? There is still a need like in mostIGP
>>>to slowdown event propagation in case of churn. Fastconvergence is
> good for a single event, but you still need to adapt
>>>to churn and slowing down convergence to prevent life of you nodes :)
>
> [luw] Quite opposite. The curent IPFRR solutions will incur lot of 
> work on the affected routers. It takes lots of churns for the network 
> to recover from the events and become ready for the next hit.
>
> [sli] can you explain a bit what you mean by "It takes lots of churns 
> for the network to recover from the events and become ready for the 
> next hit." to be sure I'm undertanding correctly. If you mean than 
> protection mechanism are not well designed for churns, you are totally 
> right (I share this opinion) but some other mechanism need to be 
> implemented (IGP backoff, dampening ...) to limit churns.
>
>>>Last point, is that here you deal only with IGP convergence, but on a
> node which is running multiple routing protocols, >>an IGP event as 
> directly an effect on other routing protocols (PIM, BGP ...). And we 
> already saw on our network, that >>concurrence of protocols inside a 
> node is a major issue for fast IGP convergence (BGP slowing down IGP 
> convergence for >>example due to bad process prioritization) and here 
> we are dependent of vendor implementations. On some router OS, >>there 
> is a huge work on this with vendors.
> [luw] This is a good problem to have, right? There are two choices:
>      a. Forbid IGP's improvement and make PIM, BGP happy;
>      b. Improve PIM, BGP ... accordingly.
>        The choice is obvious.
> [sli] Yes clearly !!
>
>
> Regards,
>
> Stephane
>
> *********************************
> This message and any attachments (the "message") are confidential and intended solely for the addressees.
> Any unauthorised use or dissemination is prohibited.
> Messages are susceptible to alteration.
> France Telecom Group shall not be liable for the message if altered, changed or falsified.
> If you are not the intended addressee of this message, please cancel it immediately and inform the sender.
> ********************************
>
> _______________________________________________
> rtgwg mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/rtgwg
>

---

From: mike shand <[email-masked]>
Date: Tue, 09 Nov 2010 08:53:31 +0000

Albert

> A) fast convergence is important in its own right. LFA and other LR mechanisms provide benefits but they can not replace fast convergence, for coverage issues, for additional complexity etc.
I completely agree. Fast convergence is certainly important in its own 
right. Indeed, fast convergence and FRR are complementary and synergistic.
> B) there are several aspects in fast convergence: detection time, propergation time, SPF time, RIB/FIB time etc. We need to attack and reduce all of them. The flooding time is one part of the prope…
Yes, but as others have shown, it is not the most significant. And the 
most significant part of the propagation delay is probably the time of 
flight of the messages anyway.
> C) We do not want to be tied down to a specific fast notification solution at this stage, and want to be able to change the engine down the road. Alia has pointed out some race conditions yesterday…
Indeed. Fast convergence mechanism have to preserve the correctness 
properties of the existing convergence mechanisms themselves. It has 
been mentioned that FRR mechanisms are complex, but the crucial 
difference is that the complexity does not interfere with the normal 
convergence process. i.e. the "complex" FRR computations only take place 
after normal (fast) convergence has taken place, in preparation for 
protecting the next failure. In the even of topology churn, the normal 
convergence always takes preference, even to the extent that no FRR 
computations take place until the topology has stabilised. And they have 
no effect on the correctness of the normal convergence, which is unchanged.

i.e. following a failure event, packets will first be re-routed using 
the repair paths computed BEFORE the failure, then as convergence takes 
place they will be routed using the correct new topology information and 
THEN  the FRR computations will prepare for the NEXT failure.
> BTW are you at the IETF Beijing? If so we could meet at the back of routing-area open meeting (Tue@1700 or end of meeting, which ever is earlier) if you are around. Others are also welcome to join…

Sorry. I'm not in Beijing.

     Mike

> Thanks,
> Albert
>
>
> On Mon, Nov 8, 2010 at 1:00 PM,<[email-masked]>  wrote:
>> node which is running multiple routing protocols,>>an IGP event as
>> already saw on our network, that>>concurrence of protocols inside a
>> convergence for>>example due to bad process prioritization) and here
>> we are dependent of vendor implementations. On some router OS,>>there

-- 
For corporate legal information go to:
www.cisco.com/web/about/doing_business/legal/cri

---

From: Albert Tian <[email-masked]>
Date: Wed, 10 Nov 2010 01:46:56 +0800

Hi Mike,

Thanks very much for your feedback. Some comments inlined below, see [tian].

<snip>

>> B) there are several aspects in fast convergence: detection time,
>> propergation time, SPF time, RIB/FIB time etc. We need to attack and reduce
>> all of them. The flooding time is one part of the propergation delay, and
>> that is what we are trying to reduce in this draft.
>
> Yes, but as others have shown, it is not the most significant. And the most
> significant part of the propagation delay is probably the time of flight of
> the messages anyway.

[tian] Yes you are right in that some other part, in particular
RIB/FIB time, was the most significant. Thanks to the earlier
researches that have exposed the problem, people have been focusing on
reducing that: reduce the IGP table size, prioritized prefix, proper
use of recursive routes, etc. These have all shown to be effective
techniques. We have not forgotten these, and will continue to improve
along those lines. Also those are mostly implementation issues and can
be done outside of IETF.

[tian] the propagation delay on the wire is indeed a very interesting
topic. Unfortunately we have to report that we were not able to reduce
the propagation delay on the wire ;-) However, our conjecture is that
the propagation delay on the wire will NOT contribute to packet loss,
only to packet re-ordering. In other words, if in a perfect world
where each router converges instantaneously upon the reception of the
failure notification, and the failure notifications can be propagated
without any additional delay, then there would be no packet loss
during convergence, regardless how long the wires are (assuming
packets can be queued up). We can proof some simple cases. The key
fact here is that the wire is also a FIFO buffer. This may also be the
reason why the whole micro-loop problem is not as bad as everyone is
expecting (otherwise the whole FRR would be completely useless).

>>
>> C) We do not want to be tied down to a specific fast notification solution
>> at this stage, and want to be able to change the engine down the road. Alia
>> has pointed out some race conditions yesterday among many other things and
>> we really appreciate that.
>
> properties of the existing convergence mechanisms themselves. It has been
> mentioned that FRR mechanisms are complex, but the crucial difference is
> that the complexity does not interfere with the normal convergence process.
> i.e. the "complex" FRR computations only take place after normal (fast)
> convergence has taken place, in preparation for protecting the next failure.
> In the even of topology churn, the normal convergence always takes
> preference, even to the extent that no FRR computations take place until the
> topology has stabilised. And they have no effect on the correctness of the
> normal convergence, which is unchanged.
>
> i.e. following a failure event, packets will first be re-routed using the
> repair paths computed BEFORE the failure, then as convergence takes place
> they will be routed using the correct new topology information and THEN  the
> FRR computations will prepare for the NEXT failure.

[tian] yes you are absolutely right that the correctness must be
guaranteed. We are trying to make the fast notification a pure
optimization on top of the existing flooding mechanisms such that the
correctness is not impacted. The current thinking is that the fast
notification will occupy a sequence number on the originator. Then we
can use the existing mechanism to deal with all re-ordering issues and
race conditions, which are more likely to happen here. The
notification can take the form of a normal IGP database update (though
does not have to), and can be flooded further following the normal
flooding procedure, as if it were received on a regular interface. In
other words, the slow flooding will fix everything and guarantee the
correctness.

>>
>> D) we started with fast convergence as an application, but we think in the
>> future other application may also benefit from a fast notification
>> framework.
>>
>> BTW are you at the IETF Beijing? If so we could meet at the back of
>> routing-area open meeting (Tue@1700 or end of meeting, which ever is
>> earlier) if you are around. Others are also welcome to join us.
>

[tian] too bad, you missed the Peking Ducks :-)

Thanks,
Albert

---

From: mike shand <[email-masked]>
Date: Tue, 16 Nov 2010 12:51:49 +0000

Albert,

     I listened to the audio of your presentation in Beijing, and that 
has prompted some questions.

     I understand that you propose that the FN service is used as in the 
802.1aq proposal as an "accelerator" to the normal flooding process. 
i.e. the result of the FN process is to temporarily replace older link 
state information until such time as it is replaced (or otherwise) by 
the normal operation of the flooding process. The reliability is 
provided by the normal flooding process.

     As in the .aq proposal, this seems to meet the requirements of 
maintaining correctness in the steady state. However, one thing which 
concerns me is the possibility of some routers receiving the fast 
notification and some not (which is possible, since it is not a reliable 
service). The effect of this would be that random routers in the network 
would receive the change information much earlier than others, and this 
could lead to the generation of relatively long duration micro-loops.

     802.1aq does not suffer from this problem directly, since it 
employs a (rather complex, as you hinted:-) loop prevention mechanism, 
whereby synchronization of neighbours databases must be achieved (using 
digest information) before changes can be made to the FIB. (there are 
exceptions, in that a certain amount of "wiggle room" is permitted while 
still retaining the guarantee of no loops.). It must be noted that this 
freedom from micro-loops is achieved at the expense of dropping packets 
which might otherwise loop, so throughput is not maintained.

     But the point I am making, is that in a normal IGP, the possible 
wide diversity in update arrival times seems to introduce the 
possibility of exacerbating micro-looping caused by desynchronised 
databases.

     I haven't thought too deeply about this, but was wondering if you 
had done any analysis concerning this property.

     One further question. From reading the OSPF FN draft, it seems that 
the arrival of FN information does NOT cause this information to be 
flooded to neighbors. (in IS-IS terms, SRM is not set). Is that correct?

     Oh yes, and another. It is suggested that the FN information is 
flooded down a spanning tree, but this spanning tree was presumably 
computed prior to the failure, and therefore may require the traversal 
of the link which has just failed. I don't understand how you guarantee 
delivery to all routers in this case.

In particular the phrase

"  Each router on the tree can send packets to
    all other routers on that tree. Even when the topology changes such
    that the tree breaks, the link-down notification is delivered to all
    routers."

needs some further explanation for me to be able understand it.

     Mike

---

From: Sriganesh Kini <[email-masked]>
Date: Tue, 16 Nov 2010 09:07:23 -0800

Mike,

Spanning tree cannot guarantee that the notification reaches all
routers under all failure notifications. I had stated as such in the
OSPF WG presentation. There are other techniques to compute redundant
trees for reliability. Pls refer to the slides.

I did notice that the wording in the draft is inaccurate. We will
update it in the next version. Thanks for pointing it out.

Also correct about FN not being 'flooded further'. When used without
any additional mechanism it can cause loops. It is not needed if the
multicast flooding topology is computed accurately.

Thanks

On Nov 16, 2010, at 4:51 AM, mike shand <[email-masked]> wrote:

> Albert,
>
>    I listened to the audio of your presentation in Beijing, and that has prompted some questions.
>
>    I understand that you propose that the FN service is used as in the 802.1aq proposal as an "accelerator" to the normal flooding process. i.e. the result of the FN process is to temporarily replace older link state information until such time as it is replaced (or otherwise) by the normal operation of the flooding process. The reliability is provided by the normal flooding process.
>
>    As in the .aq proposal, this seems to meet the requirements of maintaining correctness in the steady state. However, one thing which concerns me is the possibility of some routers receiving the fast notification and some not (which is possible, since it is not a reliable service). The effect of this would be that random routers in the network would receive the change information much earlier than others, and this could lead to the generation of relatively long duration micro-loops.
>
>    802.1aq does not suffer from this problem directly, since it employs a (rather complex, as you hinted:-) loop prevention mechanism, whereby synchronization of neighbours databases must be achieved (using digest information) before changes can be made to the FIB. (there are exceptions, in that a certain amount of "wiggle room" is permitted while still retaining the guarantee of no loops.). It must be noted that this freedom from micro-loops is achieved at the expense of dropping packets which might otherwise loop, so throughput is not maintained.
>
>    But the point I am making, is that in a normal IGP, the possible wide diversity in update arrival times seems to introduce the possibility of exacerbating micro-looping caused by desynchronised databases.
>
>    I haven't thought too deeply about this, but was wondering if you had done any analysis concerning this property.
>
>    One further question. From reading the OSPF FN draft, it seems that the arrival of FN information does NOT cause this information to be flooded to neighbors. (in IS-IS terms, SRM is not set). Is that correct?
>
>    Oh yes, and another. It is suggested that the FN information is flooded down a spanning tree, but this spanning tree was presumably computed prior to the failure, and therefore may require the traversal of the link which has just failed. I don't understand how you guarantee delivery to all routers in this case.
>
> In particular the phrase
>

---

From: Albert Tian <[email-masked]>
Date: Wed, 17 Nov 2010 21:18:59 -0800

Hi Mike,

Thanks very much for listening in and sorry for the late reply - stuck
in some all day meetings with little net access. Some answers inlined.

On Tue, Nov 16, 2010 at 4:51 AM, mike shand <[email-masked]> wrote:
> 802.1aq proposal as an "accelerator" to the normal flooding process. i.e.
> the result of the FN process is to temporarily replace older link state
> information until such time as it is replaced (or otherwise) by the normal
> operation of the flooding process. The reliability is provided by the normal
> flooding process

[tian] yes FN can be either a normal LSP/LSA, or could be in a new
format that allows some simplifications. In the former case the FN
doesn't have to temporary.

> could lead to the generation of relatively long duration micro-loops.

[tian] yes some nodes may receive fast notification while others not.
However, if we let the FN to in turn trigger slow flooding, I believe
we are not any worse than before. Think about these random routers are
seeds for the slow flooding. Before we have few seeds immediately
adjacent to the failure, now we can have many more. The problem can
also be addressed if we use other mechanisms to improve FN
reliability.

>
>    802.1aq does not suffer from this problem directly, since it employs a
> (rather complex, as you hinted:-) loop prevention mechanism, whereby
> synchronization of neighbours databases must be achieved (using digest
> information) before changes can be made to the FIB. (there are exceptions,
> in that a certain amount of "wiggle room" is permitted while still retaining
> the guarantee of no loops.). It must be noted that this freedom from
> micro-loops is achieved at the expense of dropping packets which might
> otherwise loop, so throughput is not maintained.
>
>    But the point I am making, is that in a normal IGP, the possible wide
> diversity in update arrival times seems to introduce the possibility of
> exacerbating micro-looping caused by desynchronised databases.
>

[tian] as I mentioned above, if FN further triggers slow flooding, we
do not increase the diversity in arrival time.

>    I haven't thought too deeply about this, but was wondering if you had
> done any analysis concerning this property.
>
>    One further question. From reading the OSPF FN draft, it seems that the
> arrival of FN information does NOT cause this information to be flooded to
> neighbors. (in IS-IS terms, SRM is not set). Is that correct?

[tian] we are considering both options. Now thinking about the
diversity issue your pointed out, I'm leaning towards setting the SRM
bits, especially if the underlying implementation is less reliable.
With the proper use of SRM, we will not cause any loops (As Sri
pointed out, if we don't have additional mechanisms such as SRM, loop
may happen if we "flood further" the FN).

>
>    Oh yes, and another. It is suggested that the FN information is flooded
> down a spanning tree, but this spanning tree was presumably computed prior
> to the failure, and therefore may require the traversal of the link which
> has just failed. I don't understand how you guarantee delivery to all
> routers in this case.
>
> In particular the phrase
>

[tian] There can be many mechanisms to over come link failures, for
example using multiple (disjoint) trees. Its a trade off between cost
and reliability.

Hope this helps!

Thanks,
Albert