Subject: [OSPF] draft-kini-ospf-fast-notification-01

From: Curtis Villamizar <[email-masked]>
Date: Mon, 04 Apr 2011 16:33:13 -0400

Has anyone measured the per hop flooding delay that is incurred in
modern routers?

If this is small compared to geographic delay (speed of light delay)
then there is no need for this work.  Many routers forward packets
directly to a line card CPU and coordinate flooding among line card
CPU processors, a bit like flooding inside the chassis.  Worst case
for a high priority process is about two interrupt times.  Interrupt
times on a modern CPU is about 100 usec.  If there are a lot of LSA
being flooded, then many LSA can be picked up in one system call if
driver code is written to allow this.  Even where this goes to the
CPU, modern code is smart enough to have the SPF run in a different
thread or process, so as not to hold up any further flooding.  There
was a presentation in NANOG on this topic about 5 years ago or more
but I don't have a pointer to the URL at the moment.

The assertion in the abstract that "The delay due to the involvement
of the control-plane adversely affects OSPF convergence" is not
supported in the draft and certainly not in my experience.  The SPF
time is typically long compared to the sum of per hop flooding delays
due to hitting a CPU.

Curtis

---

From: Vishwas Manral <[email-masked]>
Date: Mon, 4 Apr 2011 13:36:11 -0700

On Mon, Apr 4, 2011 at 1:33 PM, Curtis Villamizar <[email-masked]> wrote:
Hi Curtis,

>From the few we have worked, it works from 10's of nanoseconds to microseconds.

You may see some work on
http://tools.ietf.org/html/draft-manral-ospf-te-delay-00. We need to
actually add per device delay to make the solution generic, which is
what we are trying to work on.

Thanks,
Vishwas

---

From: Sriganesh Kini <[email-masked]>
Date: Mon, 4 Apr 2011 14:35:21 -0700

Vishwas,

Your draft seems to be referring to the end-to-end delay of a packet
forwarded entirely by data-plane. So those results would be applicable
to the OSPF fast-notification. It would not be applicable to
end-to-end delay of OSPF LSA flooding since the LSAs are processed at
each hop by the control-plane.

Curtis,

The control-plane delays you haven't listed include sending LSUpdate
from data-plane to control-plane and its processing such as
authenticating, comparing against LSDB, sending LSAck (with potential
re-transmission), queueing for further flooding (including re-transmit
if timer expires), re-adding interface specific auth params etc. All
of these need to be done at each intermediate hop as the LSA gets
flooded and hence the delay is cumulative. These delays may not seem
like much but it does add to the overall delay in convergence. The SPF
by itself does not take that much time in modern CPUs but the download
of routes certainly increases with number of downloads. However,
modern forwarding architectures are such that in many failure
conditions many downloads are not needed. A single download can change
the nexthop of a large number of routes. In such conditions the
hop-by-hop control-plane flooding does not remain an insignificant
component of convergence. There will of course be networks where
geographic delay itself may be large enough to dwarf all other
numbers, but there are a lot of networks where that is not true.

We will be updating the draft to support the assertions.

Thanks

On Mon, Apr 4, 2011 at 1:36 PM, Vishwas Manral <[email-masked]> wrote:
> _______________________________________________
> OSPF mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ospf
>

-- 
- Sri

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Tue, 5 Apr 2011 05:29:16 +0530

> if timer expires), re-adding interface specific auth params etc. All

You will have more delays even before this. The LSAs need to be picked up from the HW to the CPU and based on your queue scheduling algorithm there could be some delays there. Typically if its strict scheduling then you would drain all the BFDs, EFMs, LACPs, OSPF HELLOs, etc before you get to the LSUpdates. Once you have drained all such packets from the HW they will only be processed once your OSPF task gets a CPU slice. It will then take some time in processing the LSUpdates as it may have Hellos queued up ahead (based on the architecture). Similarly, at the egress there could again be some delays. If there is a central task that's responsible for sending out the packets then it could also be maintaining priority queues and LSUpdates will certainly not get into the highest. While I understand that all these delays are very small, they do start adding up as the LSAs travel hop-by-hop. It also starts getting significant as your router starts becoming busy and the processes have to contend for the CPU cycles. If the router software is not entirely lockless then you would also see processes stalled because some other task has acquired a lock that they're waiting on. So, forwarding them in the HW seems like a good idea provided we can make it work without making the solution too convoluted and complex.

Cheers, Manav

---

From: Curtis Villamizar <[email-masked]>
Date: Mon, 04 Apr 2011 22:02:20 -0400

In message <BANLkTinCQ=[email-masked]>
> what we are trying to work on.

I'm not talking about forwarding latency, but IGP flooding latency.
In flooding you are not supposed to reflood something back to an LSR
that already knows about it so a CPU is involved unless someone has
put the flooding into an FPGA (these days who knows).

Curtis

---

From: Curtis Villamizar <[email-masked]>
Date: Mon, 04 Apr 2011 22:14:53 -0400

Sri,

I spoke to a few people at IETF who have implemented OSPF and I have
deployed OSPF.  Flooding was not considered an issue.

A notfification would normally go out when a LSA is modified to
withdraw an adjacency.  Even a software SHA-256 is not that long a
time in software.

The question was whether anyone running a real network had measuered
flooding delay and found it to be a problem.

Also keep in mind that *modern* IGP implementations reflood first and
then SPF and download routes later.  You might want to look through
the archives of presentations at NANOG related to convergence.  Packet
designs and Qwest did some work on this about 5 years ago or more.
You may be tackling a non-problem.

Curtis

In message <[email-masked]>

---

From: Curtis Villamizar <[email-masked]>
Date: Mon, 04 Apr 2011 22:25:36 -0400

In message <[email-masked]>
"Bhatia, Manav (Manav)" writes:
> You will have more delays even before this. The LSAs need to be picked
> up from the HW to the CPU and based on your queue scheduling algorithm
> there could be some delays there. Typically if its strict scheduling
> then you would drain all the BFDs, EFMs, LACPs, OSPF HELLOs, etc
> before you get to the LSUpdates. Once you have drained all such
> packets from the HW they will only be processed once your OSPF task
> gets a CPU slice. It will then take some time in processing the
> LSUpdates as it may have Hellos queued up ahead (based on the
> architecture). Similarly, at the egress there could again be some
> delays. If there is a central task that's responsible for sending out
> the packets then it could also be maintaining priority queues and
> LSUpdates will certainly not get into the highest. While I understand
> that all these delays are very small, they do start adding up as the
> LSAs travel hop-by-hop. It also starts getting significant as your
> router starts becoming busy and the processes have to contend for the
> CPU cycles. If the router software is not entirely lockless then you
> would also see processes stalled because some other task has acquired
> a lock that they're waiting on. So, forwarding them in the HW seems
> like a good idea provided we can make it work without making the
> solution too convoluted and complex.
>  
> Cheers, Manav

Manav,

There is no question that you *can* design and/or code things badly.
There was work done by Packet Designs and Qwest a while back and
reported in NANOG.  After this work, a major router vendor's
implementation was optimized and a lot of delays were removed.  A big
mistake they were making is SPF and route install first and then
reflood.  It is better to get the word out that there is a problem.
After this the two leading core router vendors both had fast reflood
times.

At Avici, the minor core router vendor in its time, the CPU on the
line card (which had no long treads and low interrupt latency) handled
OSPF Hello and LSUpdate processing and only passed changes to the
router processor.

I just want to be sure that we aren't adding (more) baggage to fix a
non-problem or to fix someone's bad software implementation.

Curtis

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Tue, 5 Apr 2011 09:57:18 +0530

> reflood.  It is better to get the word out that there is a problem.

I believe RFC 2328 is quite clear that LSAs should be flooded before "recalculating the routing table structure", so I am quite surprised that there were implementations that were doing otherwise. Thus I don't think anybody on this list seriously believes that this is an issue that folks are trying to solve. I believe the idea is quite simple - Flooding a changed LSA in HW (data plane) is faster than doing it in SW (not matter how optimized the latter is) or your control plane.

Lets at least look at the proposed solution and see if its worth considering. Who knows the discussion might lead us to something better that we may want to use. 

Also note that I am not the author or in any way related to the draft! :) 

Cheers, Manav

---

From: András Császár <[email-masked]>
Date: Tue, 5 Apr 2011 15:08:53 +0200

> I believe the idea is quite simple - 
> Flooding a changed LSA in HW (data plane) is faster than 
> doing it in SW (not matter how optimized the latter is) or 
> your control plane.

That's the main purpose, yes.

You could combine this with something else: OSPF could pre-calc/pre-download potential new LSAs to the dataplane anticipating local failures. 

Whenever a local failure really happens, dataplane notices it by LoS or BFD, then can immediately disseminate the changed LSA using FN. So, in addition to the per-hop CP processing of LSAs, you could also spare some time with originating an LSA:
- failure trigger reaching/processed by CP
- OSPF originating a new LSA
- OSPF sending the LSU packet down to DP

Cheers,
András

---

From: John E Drake <[email-masked]>
Date: Tue, 5 Apr 2011 07:04:02 -0700

We actually implemented this in IBM's Nways products in the early/mid nineties and found it wasn't worth the trouble.  It had no measurable effect on network performance and the protocols necessary to terminate the broadcast were messy and error prone.

Sent from my iPhone

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> András Császár
> Sent: Tuesday, April 05, 2011 6:09 AM
> To: Bhatia, Manav (Manav); [email-masked]
> Cc: [email-masked]
> Subject: Re: [OSPF] draft-kini-ospf-fast-notification-01
> 
> You could combine this with something else: OSPF could pre-calc/pre-
> download potential new LSAs to the dataplane anticipating local
> failures.
> 
> Whenever a local failure really happens, dataplane notices it by LoS or
> BFD, then can immediately disseminate the changed LSA using FN. So, in
> addition to the per-hop CP processing of LSAs, you could also spare
> some time with originating an LSA:

---

From: John E Drake <[email-masked]>
Date: Tue, 5 Apr 2011 07:49:02 -0700

I am aware of at least one implementation from the 2002/2004 time frame with a per node OSPF flooding transit time of O(10 uSecs);  this implementation was a port of a commercially available OSPF stack rather than a custom implementation. 

Sent from my iPhone

> Curtis Villamizar
> Sent: Monday, April 04, 2011 7:15 PM
> To: Sriganesh Kini
> Cc: [email-masked]
> In message
> <[email-masked]>
> Sriganesh Kini writes:
> >
> > Vishwas,
> >

---

From: John E Drake <[email-masked]>
Date: Tue, 5 Apr 2011 09:14:18 -0700

Also, what you describe in your second and third paragraphs is an implementation choice - no protocol changes are required.

Sent from my iPhone

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 05 Apr 2011 16:15:09 -0400

In message <[email-masked]>
"Bhatia, Manav (Manav)" writes:
> I believe RFC 2328 is quite clear that LSAs should be flooded before
> "recalculating the routing table structure", so I am quite surprised
> that there were implementations that were doing otherwise. Thus I
> don't think anybody on this list seriously believes that this is an
> issue that folks are trying to solve. I believe the idea is quite
> simple - Flooding a changed LSA in HW (data plane) is faster than
> doing it in SW (not matter how optimized the latter is) or your
> control plane.
>  
> Lets at least look at the proposed solution and see if its worth
> considering. Who knows the discussion might lead us to something
> better that we may want to use.
>  

We have plenty of junk internet-drafts in IETF.  One or two less would
be better.  If it is not solving a real world problem then we should
get rid of it.  First we have to agree that there is a requirement.

draft-kini-ospf-fast-notification-01.txt calls for multicast, and
cites draft-lu-fast-notification-framework-00.txt for "transporting
the message encoding", but the latter makes no mention of multicast.

If multicast is used, a multicast routing protocol is needed.  A
multicast tree can have transient loops.  The last thing we need to
add to OSPF is a new control plane transient loop creation capability.
At least flooding is guarenteed to never loop.

When a fault occurs in a multicast tree, the tree must converge before
any other fault is reliably reported using multicast.  Multiple faults
are common.  Most are covered in protocols such as RSVP-TE that
support SRLG (but many are not even covered by SRLG).

This work is half thought out and it doesn't address a real problem so
I support telling the authors that it has no place in the OSPF WG.

Curtis

---

From: Sriganesh Kini <[email-masked]>
Date: Sun, 10 Apr 2011 10:02:47 -0700

Thanks for all the feedback.

We will take them into consideration in deciding how to proceed.

- Sri