Subject: [OSPF] SPF calculation

From: Joakim Tjernlund <[email-masked]>
Date: Thu, 6 Aug 2009 11:22:14 +0200

In  "16.1.1.  The next hop calculation" one have:
            In the second case, the parent vertex is a network that
            directly connects the calculating router to the destination
            router.  The list of next hops is then determined by
            examining the destination's router-LSA.  For each link in
            the router-LSA that points back to the parent network, the
            link's Link Data field provides the IP address of a next hop
            router.  The outgoing interface to use can then be derived
            from the next hop IP address (or it can be inherited from
            the parent network).

Suppose that one cannot find any links that points back, is it a good
idea to treat this case as a intervening router:

            If there is at least one intervening router in the current
            shortest path between the destination and the root, the
            destination simply inherits the set of next hops from the
            parent.
That is, just inherit the next hops from its parents?

    Jocke

---

From: Joakim Tjernlund <[email-masked]>
Date: Thu, 6 Aug 2009 16:02:22 +0200

"Joel M. Halpern" <[email-masked]> wrote on 06/08/2009 15:38:47:
>
> I am not sure what you are asking.  A link advertised in OSPF may only
> be used if it is advertised in both directions.

Exactly, so you may encounter the scenario below when links are going
down/up until all routers has recalculated everything.

> Therefore, it appears taht the case you are describing can not occur.

It can, so when it does you can either just give up or try
to do the best you can until you find a back link.

    Jocke
PS.
    Please keep the ospf list on the CC: line.

> Yours,
> Joel
> Joakim Tjernlund wrote:
> > _______________________________________________
> > OSPF mailing list
> > [email-masked]
> > https://www.ietf.org/mailman/listinfo/ospf
> >
>

---

From: Acee Lindem <[email-masked]>
Date: Thu, 6 Aug 2009 14:18:38 -0400

Hello Joakim,

> That is, just inherit the next hops from its parents?

No - if the Router-LSA doesn't have a link to the Network-LSA you  
don't use it in the SPF calculation. If fails the bi-directional check.

Hope this helps,
Acee

---

From: Dave Katz <[email-masked]>
Date: Thu, 6 Aug 2009 12:24:25 -0600

If there is no back link, there is no link, and SPF moves on.  If the  
network is partitioned, somebody should fix it.

Ignoring the bidirectional test rule can lead to loops and black  
holes, particularly if other implementations are following the rules.

--Dave

---

From: Joakim Tjernlund <[email-masked]>
Date: Thu, 6 Aug 2009 21:16:23 +0200

> Hello Joakim,

Hi Acee, I am back with my questions :)

> don't use it in the SPF calculation. If fails the bi-directional check.

The idea here is use some link until the remote end has updated its LSA
to include the "back link" so the intervening router case will just
act as a substitute until next LSA update.

What I wonder is if this can cause more trouble than it solves, i.e what
bad things can happen? Or won't it help at all?

  Jocke

---

From: Dave Katz <[email-masked]>
Date: Thu, 6 Aug 2009 13:22:47 -0600

> act as a substitute until next LSA update.

How do you know whether it's a transient condition?

> bad things can happen?

Routing loops and black holes.

> Or won't it help at all?

Probably not.

--Dave

---

From: Joakim Tjernlund <[email-masked]>
Date: Thu, 6 Aug 2009 21:28:07 +0200

Dave Katz <[email-masked]> wrote on 06/08/2009 20:24:25:

Hi Dave :)

> network is partitioned, somebody should fix it.

Yes, this problem exist for a short while, until the remote
route has updated it's LSA.

> holes, particularly if other implementations are following the rules.

hmm, can you be more specfic?

Consider this example:

R1 R2 R3
 |  |  |
 ------- N1

Destination is R3 and R2 is the calculation router. R2 cannot find a backlink
so it falls back to the intervening router case and uses the nexthops
from the "parent", hoping that one of them will redirect IP frames to
R3.

 Jocke

---

From: Joakim Tjernlund <[email-masked]>
Date: Thu, 6 Aug 2009 21:32:18 +0200

> How do you know whether it's a transient condition?

hmm, good question. Have to dwell on that. Assume for now that it will
be transient.

> Routing loops and black holes.

Can these affect other routes too?

> Probably not.

But it might? Please see the other mail I just sent before this one.

---

From: Acee Lindem <[email-masked]>
Date: Thu, 6 Aug 2009 15:33:53 -0400

> bad things can happen? Or won't it help at all?

I don't see that this achieves anything. If the router is reachable  
through an intra-area path, the SPF will find it. You don't want to  
do any second guessing - this will only create blackholes and routing  
loops.

Thanks,
Acee

---

From: Dave Katz <[email-masked]>
Date: Thu, 6 Aug 2009 16:04:59 -0600

> from the "parent", hoping that one of them will redirect IP frames to

This is an uninteresting case, as there are no alternative paths.   
Further, there will be no "intervening router" in this case, since  
each of R1, 2, and 3 will be adjacent to only N1.  There will be no  
next hops to inherit.  The "intervening router" rule basically just  
points out that if the best path from A to C is through B, the next  
hop to C is simply the next hop to B.  More or less.

Where it can get much uglier is if there is a back path between R2 and  
R3;  other routers playing properly will try to send the traffic  
through R3, but R3 will try to forward it locally.  In this case it  
will probably result in the traffic just disappearing down a hole  
instead of being properly delivered on the alternative path.  But if  
you start playing these games more generally, you can end up with  
traffic flying in circles.

While routing is transiently nondeterministic, "hoping" is a bit less  
rigorous than required.  ;-)  And by "redirect" I assume you mean  
"forward", as "redirect" means something specific (and only applies to  
hosts.)

In the general case, routing only converges on stability because  
everyone plays the game the same way, and the rules are designed to  
make it happen.  If you change the rules or somebody plays them  
differently, it is very easy to break the algorithm.

It's not at all clear to me why this would be interesting, even if it  
worked.  In a modern, competent OSPF implementation (namely, one which  
ignores the rules about repeated LSA generation and is otherwise  
carefully tuned) you will see the other guy's LSA with the back link  
within a few milliseconds anyhow.  In a well-engineered network there  
will be an alternative path anyhow, and traffic can be delivered on  
that path until the new one comes up fully.

---

From: Joakim Tjernlund <[email-masked]>
Date: Fri, 7 Aug 2009 01:06:15 +0200

> This is an uninteresting case, as there are no alternative paths.

Yes, it is very simple to make it clear what I am after.

> each of R1, 2, and 3 will be adjacent to only N1.

Yes, I am just saying that in this particular case I want apply the
same SPF rules as the intervening router uses.

> There will be no
> through R3, but R3 will try to forward it locally.

hmm, don't you mean "through R2, but R2" ?

> In this case it

I am starting to think that my idea was a bad idea now :)

> "forward", as "redirect" means something specific (and only applies to

Yes, I meant forwarding(sloppy me :)

---

From: Dave Katz <[email-masked]>
Date: Thu, 6 Aug 2009 17:23:07 -0600

> same SPF rules as the intervening router uses.

But there is no intervening router to inherit the next hops from, so  
the particular point is moot.  But in the broader context, yes, it  
would be possible to simply declare R3 to be the next hop, assuming  
that R2 has heard Hello packets from it on the wire, but as you gather  
this isn't such a good idea.

> hmm, don't you mean "through R2, but R2" ?

Yes, my mistake.

> I am starting to think that my idea was a bad idea now :)

Stick with that thought.  ;-)

--Dave

---

From: Joakim Tjernlund <[email-masked]>
Date: Fri, 7 Aug 2009 01:34:41 +0200

Dave Katz <[email-masked]> wrote on 07/08/2009 01:23:07:
....
> Stick with that thought.  ;-)

:) This really wasn't "my idea" to begin with but I figured I should try it out.