Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Quagga: Dev

[PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation

 

 

First page Previous page 1 2 Next page Last page  View All Quagga dev RSS feed   Index | Next | Previous | View Threaded


joakim.tjernlund at transmode

Aug 2, 2012, 1:45 PM

Post #26 of 45 (937 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Scott Feldman <sfeldma [at] cumulusnetworks> wrote on 2012/08/02 22:38:14:
>
> On Aug 2, 2012, at 1:13 PM, Joakim Tjernlund wrote:
>
> > Good, question is now what that will do to normal ppp links(with a /32 mask)
>
> You mean ptp-over-lan with /32 (unnumbered)? That's what I'm looking at. We're close with your last iteration. Would you send out your latest patch? That way at least ptp-over-lan (non /32) works as before. The /32 support can be reviewed next (once I get it working :)

both normal ppp links(created with pppd) and ptp-lan/32. I don't think this will work with the current way.
Only way to make it work is if you configure the remote IP first. Then , maybe, it will work with the
code you just tested.
Path will be sent soon, need to be social at home first(still on vacation)

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 6, 2012, 4:10 AM

Post #27 of 45 (930 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Hi Joakim,

Can I ask why you went for this approach? We already have a unique handle
for an interface, the ifindex - why not use that?

On Sat, 7 Jul 2012, Joakim Tjernlund wrote:

> Maintain router LSA positions in OSPF interface.
> Find the OSPF interface in nexthop_calculation using
> the position in the router LSA. This is possible because
> the only time nexthop_calculation needs to look up interfaces
> is when dealing with its own Router LSA.
>
> This has the following advantages:
> - Multiple PtP interfaces with the same IP address between two routers.
> - Use Unnumbered PtP on just one end of the link.
> - Faster OI lookup for the OSPF interface and only
> done once for PtoP links.
>
> *ospf_interface.h: (struct ospf_interface) Add storage for
> storing router LSA position.
>
> *ospf_interface.c: (ospf_if_lookup_by_lsa_pos)
> lookup OSPF I/F in an area using LSA position.
>
> *ospf_lsa.c: (router_lsa_link_set) record Router LSA position.
>
> *ospf_spf.c: (ospf_spf_next) Count and pass along lsa position.
> (ospf_nexthop_calculation) Add lsa position argument.
> call ospf_if_lookup_by_lsa_pos() for OSFP interface handle.
> Clean up and remove all calls ospf_if_is_configured() the
> rest. Adjust a few debug logs.
>


> diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c
> index d5959eb..493209a 100644
> --- a/ospfd/ospf_lsa.c
> +++ b/ospfd/ospf_lsa.c
> @@ -670,6 +670,7 @@ router_lsa_link_set (struct stream *s, struct ospf_area *area)
> {
> if (oi->state != ISM_Down)
> {
> + oi->lsa_pos_beg = links;
> /* Describe each link. */
> switch (oi->type)
> {
> @@ -691,6 +692,7 @@ router_lsa_link_set (struct stream *s, struct ospf_area *area)
> case OSPF_IFTYPE_LOOPBACK:
> links += lsa_link_loopback_set (s, oi);
> }
> + oi->lsa_pos_end = links;
> }
> }
> }

> diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
> index d7f9ba2..e866d0c 100644
> --- a/ospfd/ospf_spf.c
> +++ b/ospfd/ospf_spf.c
> @@ -477,13 +477,15 @@ ospf_spf_add_parent (struct vertex *v, struct vertex *w,
> static unsigned int
> ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
> struct vertex *w, struct router_lsa_link *l,
> - unsigned int distance)
> + unsigned int distance, int lsa_pos)
> {
> struct listnode *node, *nnode;
> struct vertex_nexthop *nh;
> struct vertex_parent *vp;
> struct ospf_interface *oi = NULL;
> unsigned int added = 0;
> + char buf1[BUFSIZ];
> + char buf2[BUFSIZ];
>
> if (IS_DEBUG_OSPF_EVENT)
> {
> @@ -502,30 +504,38 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
> the OSPF interface connecting to the destination network/router.
> */
>
> + /* we *must* be supplied with the link data */
> + assert (l != NULL);
> + oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos);
> + if (!oi)
> + {
> + zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
> + __func__, lsa_pos,
> + inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
> + inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
> + return 0;
> + }

I don't quite understand how this. How can the position of the link in the
router-LSA in some far-off, off-link router have any correspondence with
the ospf_interfaces of the local router?

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
Just give Alice some pencils and she will stay busy for hours.
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 6, 2012, 4:44 AM

Post #28 of 45 (927 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Also, in what way is it optimising SPF? It seems to replace 1 scan of the
oiflist with a scan of the per-area ospf_interface list, but if that's the
optimisation - an area-restricted version of ospf_if_configured could have
been added, with less disruption to the code. ??

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
Beware of all enterprises that require new clothes, and not rather
a new wearer of clothes.
-- Henry David Thoreau
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


joakim.tjernlund at transmode

Aug 6, 2012, 5:15 AM

Post #29 of 45 (929 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Paul Jakma <paul [at] jakma> wrote on 2012/08/06 13:10:31:
>
> Hi Joakim,
>
> Can I ask why you went for this approach? We already have a unique handle
> for an interface, the ifindex - why not use that?

Ifindex from where? The router LSA were one would put ifindex instead of IP address?
That does not work for the 2 cases I listed in the commit msg:

> > - Multiple PtP interfaces with the same IP address between two routers.

You don't have to set the unnumbered flag, for example current quagga does not.

> > - Use Unnumbered PtP on just one end of the link.

Unumbered on just one side shoukd also work, at least according to
Acee L. on the ietf list( if not memory fails ).

>
> On Sat, 7 Jul 2012, Joakim Tjernlund wrote:
>
> > Maintain router LSA positions in OSPF interface.
> > Find the OSPF interface in nexthop_calculation using
> > the position in the router LSA. This is possible because
> > the only time nexthop_calculation needs to look up interfaces
> > is when dealing with its own Router LSA.
> >
> > This has the following advantages:
> > - Multiple PtP interfaces with the same IP address between two routers.
> > - Use Unnumbered PtP on just one end of the link.
> > - Faster OI lookup for the OSPF interface and only
> > done once for PtoP links.
> >
> > *ospf_interface.h: (struct ospf_interface) Add storage for
> > storing router LSA position.
> >
> > *ospf_interface.c: (ospf_if_lookup_by_lsa_pos)
> > lookup OSPF I/F in an area using LSA position.
> >
> > *ospf_lsa.c: (router_lsa_link_set) record Router LSA position.
> >
> > *ospf_spf.c: (ospf_spf_next) Count and pass along lsa position.
> > (ospf_nexthop_calculation) Add lsa position argument.
> > call ospf_if_lookup_by_lsa_pos() for OSFP interface handle.
> > Clean up and remove all calls ospf_if_is_configured() the
> > rest. Adjust a few debug logs.
> >
>
>
> > diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c
> > index d5959eb..493209a 100644
> > --- a/ospfd/ospf_lsa.c
> > +++ b/ospfd/ospf_lsa.c
> > @@ -670,6 +670,7 @@ router_lsa_link_set (struct stream *s, struct ospf_area *area)
> > {
> > if (oi->state != ISM_Down)
> > {
> > + oi->lsa_pos_beg = links;
> > /* Describe each link. */
> > switch (oi->type)
> > {
> > @@ -691,6 +692,7 @@ router_lsa_link_set (struct stream *s, struct ospf_area *area)
> > case OSPF_IFTYPE_LOOPBACK:
> > links += lsa_link_loopback_set (s, oi);
> > }
> > + oi->lsa_pos_end = links;
> > }
> > }
> > }
>
> > diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
> > index d7f9ba2..e866d0c 100644
> > --- a/ospfd/ospf_spf.c
> > +++ b/ospfd/ospf_spf.c
> > @@ -477,13 +477,15 @@ ospf_spf_add_parent (struct vertex *v, struct vertex *w,
> > static unsigned int
> > ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
> > struct vertex *w, struct router_lsa_link *l,
> > - unsigned int distance)
> > + unsigned int distance, int lsa_pos)
> > {
> > struct listnode *node, *nnode;
> > struct vertex_nexthop *nh;
> > struct vertex_parent *vp;
> > struct ospf_interface *oi = NULL;
> > unsigned int added = 0;
> > + char buf1[BUFSIZ];
> > + char buf2[BUFSIZ];
> >
> > if (IS_DEBUG_OSPF_EVENT)
> > {
> > @@ -502,30 +504,38 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
> > the OSPF interface connecting to the destination network/router.
> > */
> >
> > + /* we *must* be supplied with the link data */
> > + assert (l != NULL);
> > + oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos);
> > + if (!oi)
> > + {
> > + zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
> > + __func__, lsa_pos,
> > + inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
> > + inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
> > + return 0;
> > + }
>
> I don't quite understand how this. How can the position of the link in the
> router-LSA in some far-off, off-link router have any correspondence with
> the ospf_interfaces of the local router?

It does not, but the trick here is that you only do the oi lookup for
you own router LSA:
if (v == area->spf)
{
/* 16.1.1 para 4. In the first case, the parent vertex (V) is the
root (the calculating router itself). This means that the
destination is either a directly connected network or directly
connected router. The outgoing interface in this case is simply
the OSPF interface connecting to the destination network/router.
*/

/* we *must* be supplied with the link data */
assert (l != NULL);
oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos);

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


joakim.tjernlund at transmode

Aug 6, 2012, 5:40 AM

Post #30 of 45 (933 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Paul Jakma <paul [at] jakma> wrote on 2012/08/06 13:44:07:
>
> Also, in what way is it optimising SPF? It seems to replace 1 scan of the
> oiflist with a scan of the per-area ospf_interface list, but if that's the
> optimisation - an area-restricted version of ospf_if_configured could have
> been added, with less disruption to the code. ??

Because ospf_if_is_configured() is called inside the while loop.
ospf_if_is_configured() is also more expensive per call.
An area optimized version would not overcome the limitations I listed
in previous mail either.

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 6, 2012, 6:43 AM

Post #31 of 45 (930 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

On Mon, 6 Aug 2012, Joakim Tjernlund wrote:

> Ifindex from where? The router LSA were one would put ifindex instead of
> IP address?

You put it in the link-data field, see 12.4.1 page 127 and 12.4.1.1.

> That does not work for the 2 cases I listed in the commit msg:

>>> - Multiple PtP interfaces with the same IP address between two routers.

> You don't have to set the unnumbered flag, for example current quagga
> does not.

Well, then that has to be set. That's part of the work that would have to
be done for unnumbered support.

>>> - Use Unnumbered PtP on just one end of the link.

> Unumbered on just one side shoukd also work, at least according to
> Acee L. on the ietf list( if not memory fails ).

Why wouldn't this work with ifindex?

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
Power Company having EMP problems with their reactor
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 6, 2012, 7:17 AM

Post #32 of 45 (929 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

On Mon, 6 Aug 2012, Joakim Tjernlund wrote:


> It does not, but the trick here is that you only do the oi lookup for
> you own router LSA:
> if (v == area->spf)

Ah, the hazards of reading diffs. Thanks.

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
A hundred thousand lemmings can't be wrong!
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


joakim.tjernlund at transmode

Aug 6, 2012, 8:55 AM

Post #33 of 45 (933 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Paul Jakma <paul [at] jakma> wrote on 2012/08/06 15:43:46:
>
> On Mon, 6 Aug 2012, Joakim Tjernlund wrote:
>
> > Ifindex from where? The router LSA were one would put ifindex instead of
> > IP address?
>
> You put it in the link-data field, see 12.4.1 page 127 and 12.4.1.1.

Right, what I figured then.

>
> > That does not work for the 2 cases I listed in the commit msg:
>
> >>> - Multiple PtP interfaces with the same IP address between two routers.
>
> > You don't have to set the unnumbered flag, for example current quagga
> > does not.
>
> Well, then that has to be set. That's part of the work that would have to
> be done for unnumbered support.

1) unnumbered is manually configured so how would you do that exactly?
2) You break current released Quagga if use unnumbered
3) I am not convinced that you must use unnumbered, current Q can
use the same IP on ppp links, just not more than on ppp link/router.
Why is this suddenly wrong?

>
> >>> - Use Unnumbered PtP on just one end of the link.
>
> > Unumbered on just one side shoukd also work, at least according to
> > Acee L. on the ietf list( if not memory fails ).
>
> Why wouldn't this work with ifindex?

My turn to be a bit grumpy, we have been over this before. I tried to explain it to you,
here is a mail that I found after much digging:

-----------------------------------------------------------------------------

Since this has become a long thread and I don't seem to get through to you, I
figured I should summarize:

Current nexthop_calculation:
- Cannot do unnumbered
- Cannot do multiple numbered PtoP with the same local IP
address to the same router.
- Can do multiple numbered PtoP with the same local IP
address to the different routers. Has been so for
many years.

Adding ifindex aka. b) version:
- Same as above plus:
- Can do unnumbered iff both ends of the link is unnumbered.

The reason for these limitations is in ospf_if_is_configured(). This
function tries to match the remote IP address of the PtoP I/F.
The nexthop_calculation() tries find a matching interface by looking
in the remote router LSA:
/* l is a regular point-to-point link.
Look for a link from W to V.
*/
while ((l2 = ospf_get_next_link (w, v, l2)))
{
oi = ospf_if_is_configured (area->ospf,
&(l2->link_data));

if (oi == NULL)
continue;

if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
&l->link_data))
continue;

break;
}
This will only work iff there is only ONE matching IP address. There will
be no IP address if the remote side is unnumbered. If there is more
that one matching IP address, it wont find the correct interface in many cases.
You should also note how inefficient this is:
Assume you have 8 PtP I/Fs and the the remote router lsa has
50 entries in it. ospf_get_next_link() will then search in average 25 entries
before finding a matching one, ospf_if_is_configured() will then have to
search all ospf interfaces in average 4 times before finding the
interface.
That is a lot of work for finding one PtP interface. Don't even want
to think about worst case.

Now look at the next case:
assert(w->type == OSPF_VERTEX_NETWORK);
oi = ospf_if_is_configured (area->ospf, &(l->link_data));
if (oi)
{
nh = vertex_nexthop_new ();
nh->oi = oi;
nh->router.s_addr = 0;
ospf_spf_add_parent (v, w, nh, distance);
return 1;
}
}
Suppose you have a loopback IF with the same IP address as
one of your other addresses, then there is a risk that
the wrong IF is found.

the a) version gets rid of all these problems at virtually
no cost and will ALWAYS identify the correct interface.

Jocke



_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 6, 2012, 11:28 AM

Post #34 of 45 (930 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

On Mon, 6 Aug 2012, Joakim Tjernlund wrote:

> Paul Jakma <paul [at] jakma> wrote on 2012/08/06 15:43:46:

>> Well, then that has to be set. That's part of the work that would have to
>> be done for unnumbered support.
>
> 1) unnumbered is manually configured so how would you do that exactly?

Well, at least some unnumbered setups can be recognised automatically (and
they should be really). Why does it matter to LSAs and SPF whether an
interface's unnumbered status was set manually or automatically?

We've had discussions before about teaching zebra to detect these, I'm
sure you had patches (we've discussed the details of indexing them
before).

Sorry to be vague, but this was quite a few years ago, and I don't have an
archive handy and my memory at the moment is hazy too.

> I tried to explain it to you, here is a mail that I found after much
> digging:

> -----------------------------------------------------------------------------
>
> Since this has become a long thread and I don't seem to get through to you, I
> figured I should summarize:
>
> Current nexthop_calculation:
> - Cannot do unnumbered

Indeed.

> - Cannot do multiple numbered PtoP with the same local IP
> address to the same router.

Yes, that's multiple unnumbered links to the same remote router.

> - Can do multiple numbered PtoP with the same local IP
> address to the different routers. Has been so for
> many years.

Other implementations often treat this case as unnumbered I think.

> Adding ifindex aka. b) version:
> - Same as above plus:
> - Can do unnumbered iff both ends of the link is unnumbered.
>
> The reason for these limitations is in ospf_if_is_configured(). This
> function tries to match the remote IP address of the PtoP I/F.
> The nexthop_calculation() tries find a matching interface by looking
> in the remote router LSA:
> /* l is a regular point-to-point link.
> Look for a link from W to V.
> */
> while ((l2 = ospf_get_next_link (w, v, l2)))
> {
> oi = ospf_if_is_configured (area->ospf,
> &(l2->link_data));
>
> if (oi == NULL)
> continue;
>
> if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
> &l->link_data))
> continue;
>
> break;
> }

> This will only work iff there is only ONE matching IP address. There
> will be no IP address if the remote side is unnumbered. If there is more
> that one matching IP address, it wont find the correct interface in many
> cases.

Well, because that code doesn't support unnumbered. So it doesn't work. So
it needs to be changed. Sure. :)

For unnumbered, for LSAs for remote, attached routers, the link-data is
going to be some cookie that is meaningless to the local router (whether
that's an ifindex or lsa-pos or whatever doesn't matter). Some other
method of finding the right oi has to be used. E.g. you can use the
link-data of V (the local router's LSA in that area), which can be an
ifindex.

So yes, completely agree the above code needs to be quite different for
unnumbered.

> You should also note how inefficient this is: Assume you have 8 PtP I/Fs
> and the the remote router lsa has 50 entries in it. ospf_get_next_link()
> will then search in average 25 entries before finding a matching one,
> ospf_if_is_configured() will then have to search all ospf interfaces in
> average 4 times before finding the interface. That is a lot of work for
> finding one PtP interface. Don't even want to think about worst case.

Well, O(n) searches can be turned into O(1) ones, at the cost of some
memory - if the lookup can't be avoided.

In this case, you're not going to do this search, because it doesn't apply
for unnumbered. You'll use V's link-data to find the ospf_interface - and
you can just have that hold the local ifindex - as the RFC says must be
done. Then there's no need to also store the local lsa_pos.

I.e. the ifindex is as good, if not better, an identifier as the lsa_pos,
plus it has to be put in the local LSA link-data anyway to be
RFC-letter-compliant.

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
The revolution will not be televised.
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


joakim.tjernlund at transmode

Aug 6, 2012, 1:02 PM

Post #35 of 45 (929 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Paul Jakma <paul [at] jakma> wrote on 2012/08/06 20:28:22:
>
> On Mon, 6 Aug 2012, Joakim Tjernlund wrote:
>
> > Paul Jakma <paul [at] jakma> wrote on 2012/08/06 15:43:46:
>
> >> Well, then that has to be set. That's part of the work that would have to
> >> be done for unnumbered support.
> >
> > 1) unnumbered is manually configured so how would you do that exactly?
>
> Well, at least some unnumbered setups can be recognised automatically (and
> they should be really). Why does it matter to LSAs and SPF whether an
> interface's unnumbered status was set manually or automatically?
>
> We've had discussions before about teaching zebra to detect these, I'm
> sure you had patches (we've discussed the details of indexing them
> before).
>
> Sorry to be vague, but this was quite a few years ago, and I don't have an
> archive handy and my memory at the moment is hazy too.

I don't recall I had patches, if I did they were probably very sketchy and I recall
there were objections to that too. Probably because of 2) which cut away, please don't
remove stuff you don't want to answer.

>
> > I tried to explain it to you, here is a mail that I found after much
> > digging:
>
> > -----------------------------------------------------------------------------
> >
> > Since this has become a long thread and I don't seem to get through to you, I
> > figured I should summarize:
> >
> > Current nexthop_calculation:
> > - Cannot do unnumbered
>
> Indeed.
>
> > - Cannot do multiple numbered PtoP with the same local IP
> > address to the same router.
>
> Yes, that's multiple unnumbered links to the same remote router.

as 3) (also removed), that is debatable.

>
> > - Can do multiple numbered PtoP with the same local IP
> > address to the different routers. Has been so for
> > many years.
>
> Other implementations often treat this case as unnumbered I think.

But released quagga don't. Do you want to break all quagga installations
that uses this feature?

>
> > Adding ifindex aka. b) version:
> > - Same as above plus:
> > - Can do unnumbered iff both ends of the link is unnumbered.
> >
> > The reason for these limitations is in ospf_if_is_configured(). This
> > function tries to match the remote IP address of the PtoP I/F.
> > The nexthop_calculation() tries find a matching interface by looking
> > in the remote router LSA:
> > /* l is a regular point-to-point link.
> > Look for a link from W to V.
> > */
> > while ((l2 = ospf_get_next_link (w, v, l2)))
> > {
> > oi = ospf_if_is_configured (area->ospf,
> > &(l2->link_data));
> >
> > if (oi == NULL)
> > continue;
> >
> > if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
> > &l->link_data))
> > continue;
> >
> > break;
> > }
>
> > This will only work iff there is only ONE matching IP address. There
> > will be no IP address if the remote side is unnumbered. If there is more
> > that one matching IP address, it wont find the correct interface in many
> > cases.
>
> Well, because that code doesn't support unnumbered. So it doesn't work. So
> it needs to be changed. Sure. :)
>
> For unnumbered, for LSAs for remote, attached routers, the link-data is
> going to be some cookie that is meaningless to the local router (whether
> that's an ifindex or lsa-pos or whatever doesn't matter). Some other
> method of finding the right oi has to be used. E.g. you can use the
> link-data of V (the local router's LSA in that area), which can be an
> ifindex.
>
> So yes, completely agree the above code needs to be quite different for
> unnumbered.
>
> > You should also note how inefficient this is: Assume you have 8 PtP I/Fs
> > and the the remote router lsa has 50 entries in it. ospf_get_next_link()
> > will then search in average 25 entries before finding a matching one,
> > ospf_if_is_configured() will then have to search all ospf interfaces in
> > average 4 times before finding the interface. That is a lot of work for
> > finding one PtP interface. Don't even want to think about worst case.
>
> Well, O(n) searches can be turned into O(1) ones, at the cost of some
> memory - if the lookup can't be avoided.

Right, my first impl. had the O(1) property but you rejected that one, I don't
mind bringing it back but I am not going to do that work again.

>
> In this case, you're not going to do this search, because it doesn't apply
> for unnumbered. You'll use V's link-data to find the ospf_interface - and
> you can just have that hold the local ifindex - as the RFC says must be
> done. Then there's no need to also store the local lsa_pos.

And how are you going to map ifindex to ospf_interface? What about other
numbered ptp I/Fs ?

>
> I.e. the ifindex is as good, if not better, an identifier as the lsa_pos,
> plus it has to be put in the local LSA link-data anyway to be
> RFC-letter-compliant.

Please feel free to show us how it is done. I don't really see any barring
shortcomings in your reply, just you claiming it can be done even better.

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 6, 2012, 3:04 PM

Post #36 of 45 (928 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

On Mon, 6 Aug 2012, Joakim Tjernlund wrote:

> But released quagga don't. Do you want to break all quagga installations
> that uses this feature?

Aha, ok, so this is the motivation for going with the LSA position? To
keep the sent LSA same, to avoid upsetting remote Quaggas that havn't been
updated to unnumbered code?

> And how are you going to map ifindex to ospf_interface?

Exactly as the added ospf_if_lookup_by_lsa_pos does, excepting searching
for ifindex (oi->ifp->ifindex).

> What about other numbered ptp I/Fs ?

Those would stay by address, as now.

> Please feel free to show us how it is done. I don't really see any
> barring shortcomings in your reply, just you claiming it can be done
> even better.

I hope I didn't say better - I was simply asking "why not ifindex?". The
ifindex is the typical identifier to use, and the identifier the RFC
explicitly has in mind. So not taking that approach is unusual.

When a change does something unusual, it's worth trying to understand why
that is. Either because it should really be doing the usual instead and
the change perhaps needs updating, or because it's worth explaining to
everyone else why the usual doesn't work.

It's not meant to be a personal slight, or challenge.

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
How sharper than a serpent's tooth is a sister's "See?"
-- Linus Van Pelt
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


joakim.tjernlund at transmode

Aug 6, 2012, 4:09 PM

Post #37 of 45 (926 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Paul Jakma <paul [at] jakma> wrote on 2012/08/07 00:04:29:
>
> On Mon, 6 Aug 2012, Joakim Tjernlund wrote:
>
> > But released quagga don't. Do you want to break all quagga installations
> > that uses this feature?
>
> Aha, ok, so this is the motivation for going with the LSA position? To
> keep the sent LSA same, to avoid upsetting remote Quaggas that havn't been
> updated to unnumbered code?

That is one reason. That alone should should be enough.
As you feel differently, do ask the list what they feel about that,
it doesn't matter to me anymore as all our systems in the field
can deal with this.

>
> > And how are you going to map ifindex to ospf_interface?
>
> Exactly as the added ospf_if_lookup_by_lsa_pos does, excepting searching
> for ifindex (oi->ifp->ifindex).

And that is better how?

>
> > What about other numbered ptp I/Fs ?
>
> Those would stay by address, as now.

Right, that is both more expensive and does not deal with numbered
in one end and unnumbered in the other. What an improvement.

>
> > Please feel free to show us how it is done. I don't really see any
> > barring shortcomings in your reply, just you claiming it can be done
> > even better.
>
> I hope I didn't say better - I was simply asking "why not ifindex?". The
> ifindex is the typical identifier to use, and the identifier the RFC
> explicitly has in mind. So not taking that approach is unusual.

You pretty much did and asking questions that I recently answered shows
that you haven't paid much attention.

>
> When a change does something unusual, it's worth trying to understand why
> that is. Either because it should really be doing the usual instead and
> the change perhaps needs updating, or because it's worth explaining to
> everyone else why the usual doesn't work.
>
> It's not meant to be a personal slight, or challenge.

But it is. You cannot be bothered to actually read the code and think
for a moment about this change. Especially since this is at least
the second, possibly third, time we have this discussion.

If you had done so you would have seen that this is a very clever
way to overcome current limitations, is faster and only costs 32 bits
in each ospf_interface. It a way way better than we currently have and
if you can do better, please do.

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 7, 2012, 3:03 AM

Post #38 of 45 (931 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

On Tue, 7 Aug 2012, Joakim Tjernlund wrote:

> That is one reason. That alone should should be enough.

Well, it still doesn't require lsa_pos. If the remote side is old/current
Quagga you can use the IP method, and list your own IP in the LSA - you
can't have multiple links to them anyway. So you can use that, and you
don't need to change the LSA.

For unnumbered both sides, old/current Quagga can't be involved, so you
definitely can use the method the RFC says - listing the ifindex in the
LSA.

> If you had done so you would have seen that this is a very clever way to
> overcome current limitations, is faster and only costs 32 bits in each
> ospf_interface. It a way way better than we currently have and if you
> can do better, please do.

Yes, it's clever. However, it was pretty unusual. If you think people are
not entitled to ask you to explain your patches, particularly clever
and/or unusual stuff, then please just stop submitting patches, so none of
us wastes our time.

However clever you are, you are still human, and so the odd change of
yours will inevitably be a turd (e.g. reverting the #303 bug fix; the SPF
change breaking PtP on LAN). How is anyone supposed to figure out whether
your patch is brilliant or crap, when you can be so dismissive of any
questions, even angered by them? (you are always _certain_ of the
correctness of all your patches).

It took an incredible amount of arguing to show you the SPF nexthop revert
was wrong. Indeed, I had to actually summarise the code in psuedo-code
form for you (who wont read code?). Scott pointed out a clear regression
in another SPF change you proposed, and you argued that!

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
Paul's Law:
In America, it's not how much an item costs, it's how much you save.
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


joakim.tjernlund at transmode

Aug 7, 2012, 7:47 AM

Post #39 of 45 (929 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Paul Jakma <paul [at] jakma> wrote on 2012/08/07 12:03:22:
>
> On Tue, 7 Aug 2012, Joakim Tjernlund wrote:
>
> > That is one reason. That alone should should be enough.
>
> Well, it still doesn't require lsa_pos. If the remote side is old/current
> Quagga you can use the IP method, and list your own IP in the LSA - you
> can't have multiple links to them anyway. So you can use that, and you
> don't need to change the LSA.
>
> For unnumbered both sides, old/current Quagga can't be involved, so you
> definitely can use the method the RFC says - listing the ifindex in the
> LSA.

True, but what about the case you removed from this mail? Not important?

>
> > If you had done so you would have seen that this is a very clever way to
> > overcome current limitations, is faster and only costs 32 bits in each
> > ospf_interface. It a way way better than we currently have and if you
> > can do better, please do.
>
> Yes, it's clever. However, it was pretty unusual. If you think people are
> not entitled to ask you to explain your patches, particularly clever
> and/or unusual stuff, then please just stop submitting patches, so none of
> us wastes our time.

But I have explained it, you understand it even though you
just read the patch.

Your recent questions isn't about what did and how, you are asking me to
if I cannot solve all the issues in a different way( by doing some minor
touch ups on existing code). This I have explained I cannot both before
and in this thread.

You think it can be done obviously so why not outline how you want it
solved and the pros and cons?

So far I haven't heard any concerns about the patch being wrong or that
it doesn't do what it claims to do, I guess that is a plus.

>
> However clever you are, you are still human, and so the odd change of
> yours will inevitably be a turd (e.g. reverting the #303 bug fix; the SPF
> change breaking PtP on LAN).

I did a blind forward port of my patches to jump start/aid getting them into
to tree. I said as much up front, I had no idea that Q had gained
support for PtP LANs already and when that was clear to me I fixed
it. No surprise really.

> How is anyone supposed to figure out whether
> your patch is brilliant or crap, when you can be so dismissive of any
> questions, even angered by them?

We have moved beyond that, now the questions are: Can you redo it
all using the existing functions with some touch ups? Again, no I cannot
without loosing some important feature.

> (you are always _certain_ of the
> correctness of all your patches).

Your words, I am not actually. Often yes, sometimes unsure and then I say so and
in the odd case I am simply wrong.

>
> It took an incredible amount of arguing to show you the SPF nexthop revert
> was wrong. Indeed, I had to actually summarise the code in psuedo-code
> form for you (who wont read code?).

Took a while to catch on yes. Mostly for the initial "explanations" was very
vague and pointers to a big bug and a web site.
Now I got it, I cannot say I am sure that no loops can happen but you are
and I will take your word for it.

So to sum it up:
No, I cannot do it differently. You think you can.
There aren't any known problems, real or perceived, with the way I do it.

Agreed? If so, we can stop now.

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 7, 2012, 10:04 AM

Post #40 of 45 (923 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

On Tue, 7 Aug 2012, Joakim Tjernlund wrote:

> So to sum it up:

> No, I cannot do it differently. You think you can.

Well, it wasn't about some battle of ways. It was about just trying to
understand the lsa_pos approach you took, and what merits it had. Getting
you to compare it to the ifindex approach (which is not something I just
/think/ could be done, but is the approach the RFC describes) should have
been a reasonable way to achieve that. :)

> There aren't any known problems, real or perceived, with the way I do it.

Now that you've explained it, no, it appears not.

Taking indices into one object and stashing them in another does tend to
make people go "uh?". E.g. the backlink for VLinks got your notice and
made you question too, no?

Anyway…

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
No question is so difficult as one to which the answer is obvious.


joakim.tjernlund at transmode

Aug 7, 2012, 10:37 AM

Post #41 of 45 (920 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Paul Jakma <paul [at] jakma> wrote on 2012/08/07 19:04:32:
>
> On Tue, 7 Aug 2012, Joakim Tjernlund wrote:
>
> > So to sum it up:
>
> > No, I cannot do it differently. You think you can.
>
> Well, it wasn't about some battle of ways. It was about just trying to
> understand the lsa_pos approach you took, and what merits it had. Getting
> you to compare it to the ifindex approach (which is not something I just

Been there already, that was one of the first methods I tried. There is
even patches on the list suggesting this method, but was later superseded
by the lsa_pos method because of its limitations.

> /think/ could be done, but is the approach the RFC describes) should have
> been a reasonable way to achieve that. :)

I don't think the RFC prescribes any method for finding the interface,
not in 16.1.1 anyway. The RFC simply says:
The outgoing interface in this case is simply the OSPF
interface connecting to the destination network/router

Finding the nexthop IP address is what you are thinking of.

>
> > There aren't any known problems, real or perceived, with the way I do it.
>
> Now that you've explained it, no, it appears not.

Good.

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


nick at inex

Aug 7, 2012, 11:19 AM

Post #42 of 45 (918 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

On 07/08/2012 18:04, Paul Jakma wrote:
> Taking indices into one object and stashing them in another does tend to
> make people go "uh?". E.g. the backlink for VLinks got your notice and made
> you question too, no?

maybe document carefully in the code why this approach was taken? It may
lower the wtf rate for future generations of developers.

Nick
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


paul at jakma

Aug 7, 2012, 12:03 PM

Post #43 of 45 (920 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

On Tue, 7 Aug 2012, Joakim Tjernlund wrote:

> I don't think the RFC prescribes any method for finding the interface,
> not in 16.1.1 anyway. The RFC simply says:

> The outgoing interface in this case is simply the OSPF
> interface connecting to the destination network/router

And having a cookie attached to the link in your LSA is what lets you
relate that link back to your OSPF interface - for unnumbered. The RFC
anticipates that the interface ifindex will be that cookie, stashed in the
link-data. You decided to go the other way and stash the LSA index into
the ospf_interface.

At this point, they seem to be mostly equivalent approaches (other than
that one approach will be more familiar to people, by virtue of the RFC
suggesting it).

regards,
--
Paul Jakma paul [at] jakma @pjakma Key ID: 64A2FF6A
Fortune:
I generally avoid temptation unless I can't resist it.
-- Mae West
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


joakim.tjernlund at transmode

Aug 7, 2012, 2:09 PM

Post #44 of 45 (915 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Paul Jakma <paul [at] jakma> wrote on 2012/08/07 21:03:28:
>
> On Tue, 7 Aug 2012, Joakim Tjernlund wrote:
>
> > I don't think the RFC prescribes any method for finding the interface,
> > not in 16.1.1 anyway. The RFC simply says:
>
> > The outgoing interface in this case is simply the OSPF
> > interface connecting to the destination network/router
>
> And having a cookie attached to the link in your LSA is what lets you
> relate that link back to your OSPF interface - for unnumbered. The RFC
> anticipates that the interface ifindex will be that cookie, stashed in the
> link-data. You decided to go the other way and stash the LSA index into
> the ospf_interface.

For calculation of nexthop IP addresses:
the interface's MIB-II [Ref8] ifIndex value. For the other link
types it specifies the router interface's IP address. This
latter piece of information is needed during the routing table
build process, when calculating the IP address of the next hop.
See Section 16.1.1 for more details.

Seems to me most impl. overload that to also to also mean interface, I guess
that is the first thing you come to think of ...

My way took a lot of effort to invent. I had to come up
with something that would work with our old zebra based impl. it was
hacked to death by people before me. Fortunately all such systems has
been upgraded to Quagga so I don't have to worry any more. I used
to have a local hack on top which automatically detected if Q was talking
to an old zebra and toggled unnumbered off for that link. That hack
has been removed as of a few releases back.

>
> At this point, they seem to be mostly equivalent approaches (other than

Oh come on, it is way better and you know it :)

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev


joakim.tjernlund at transmode

Aug 7, 2012, 2:20 PM

Post #45 of 45 (916 views)
Permalink
Re: [PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation [In reply to]

Nick Hilliard <nick [at] inex> wrote on 2012/08/07 20:19:51:
>
> On 07/08/2012 18:04, Paul Jakma wrote:
> > Taking indices into one object and stashing them in another does tend to
> > make people go "uh?". E.g. the backlink for VLinks got your notice and made
> > you question too, no?
>
> maybe document carefully in the code why this approach was taken? It may
> lower the wtf rate for future generations of developers.

Never got the backlink reference. It is in every vertex and is mostly useless
except for VLINKS which I noted after a simple grep. I would like
to remove backlinks for vertexes but in order to do that one must decouple
VLINK from backlinks, surely it must be possible to do a route
lookup of sorts instead? I must admit that I haven't looked at it more
than briefly and it looks non trivial to me. Then again I haven't looked at VLINKS
before so maybe it is not so hard?

Second best would be to pass backlink to nexthop_calculation() so
you don't have to figure it out over and over again.

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

First page Previous page 1 2 Next page Last page  View All Quagga dev RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.