[email protected]
[Top] [All Lists]

Re: [Fwd: [Fwd: I-D ACTION:draft-ietf-rtgwg-microloop-analysis-00.txt]]

Subject: Re: [Fwd: [Fwd: I-D ACTION:draft-ietf-rtgwg-microloop-analysis-00.txt]]
From: Alia Atlas
Date: Wed, 27 Jul 2005 17:25:43 -0700
On 7/27/05, Russ White <[email protected]> wrote:
> Hash: SHA1
> >>Yes, but you've used the definition of N's shortest path as the
> >>definition of N's loop free path (?). I thought the point of this was to
> >>discover loop free paths other than your shortest path (?). Look at it
> >>this way:
> >
> > I think that the point of confusion is about discovering loop-free
> > paths other than your shortest path.  I think that you are assuming
> > something more complicated.
> I'm not trying to.... :-) There are three classes of paths:
> - -- Your best path, which is known to be loop free.
> - -- Alternate known loop free paths.
> - -- Alternate paths not known to be looped or loop free.
> Which of these three do "downstream neighbors" fit in to?

Downstream neighbors fit into both the first and the second.

>From the perspective of the computing router S, there are 4 classes of
paths in regard to a particular destination D:
 a) shortest paths
 b) downstream paths: the next-hop's distance to D is less than S's
distance to D.  Shortest
                                 paths are a subset of these.
 c) loop-free paths: the next-hop's shortest path(s) to D do not go
through S.  Downstream
                            paths are a subset of these.
 d) looping paths: the set of next-hops with at least one shortest
path that does go through S.

> > The idea with LFA is that S assumes that its neighbors are following
> > their shortest paths, because the neighbors will not have learned
> > about nor responded to the failure local to S at the time that S
> > repairs.  Thus S considers whether a neighbor N_i has a loop-free path
> > with regard to S to reach the destination; if so, S can use N_i as a
> > loop-free alternate.  Of course, the protection provided by that path
> > needs to be determined as well.
> > With PLSN, a similar assumption applies.  The assumption for a router
> > S is that its neighbors are forwarding traffic based on either the old
> > topology, to a "safe neighbor", or on the new topology.  The idea is
> > to work with the uncertainty of a neighbor's state in a way to provide
> > safe transitions.  The neighbor is assumed to be either following a
> > shortest path or, possibly, a downstream path.
> >
> >
> >>N-----+
> >>|     |
> >>|     S--D
> >>|     |
> >>L-----+
> >>
> >>If's N's beat path to D is through S, the the best loop free path to D
> >>has the cost Dopt(S,D) + Dopt(N,S), which is just the same as Dopt(N,D).
> >>When will the path through L be gaurenteed to be loop free? When
> >>Dopt(L,D) is less that Dopt(N,D). It might be loop free even when
> >>Dopt(L,D) > Dipt(N,D), but there's no mathematical way I know of to
> >>prove this.
> >>
> >>The formula in the draft states a path is loop free if:
> >>
> >>
> >>>>           for destination D, if Dopt(N, D) < Dopt(N, S) + Dopt(S, D).
> >>
> >>I'm confused. Is the path under consideration for "loop freeness," on
> >>the left or the right side of this inequality?
> >
> > The path under consideration is on the left side; the right side is
> > the cost of a "looping" path that goes via S.
> ?? How do you know it's a loop?

Perhaps I should have said that the right side is the cost of the
shortest possible "looping" path that would go via S.

The question is whether the shortest path from N to D goes via S.  
The shortest distance that such a path can be is D_opt(N,S) + D_opt(S,
D).   If D_opt(N, D) is less than this, then the path from N to D
cannot go through S.
> >>If it's the one the left, and I've run this comparison for every
> >>possible route, then the route on the left is the best path to the
> >>destination, and therefore by definition loop free. In fact, this is the
> >>path I'm currently using to reach D, so I've done nothing different than
> >>what I have today. If this is a comparison between any two routes in
> >>your local table, then the comparison says nothing about anything,
> >>because you could be comparing your two worst routes, both of which are
> >>loops.
> >
> > N isn't doing anything different than it is today.
> >
> >>If it's the one on the right, "Dopt(N,S) + Dopt(S,D)" in reference to
> >>the "shortest path" of "Dopt(N,D)," then you're saying any path with a
> >>metric higher than the shortest path is either always downstream, or
> >>always loop free, neither of which are true. Consider this:
> >>
> >>A----B----C
> >>|    |
> >>D----+
> >>
> >>Now, what you say here:
> >>
> >>
> >>>This is the tighter condition of a downstream neighbor, which is a
> >>>subset of the loop-free neighbors.  It is more restrictive & provides
> >>>worse coverage.
> >>
> >>Says that both B and D are "loop free" in repesect to A->C, but B might
> >>be the only "downstream" neighbor (for some reason I still don't
> >>understand). Does it depend on the cost? In other words, are you trying
> >>to say that while you know D is loop free, B is actually downstream? In
> >>what case would you know that B is downstream and not also the best
> >>path, based on the formulas given in the draft?
> >
> > The difference between a downstream neighbor and a loop-free neighbor
> > is based on the costs.
> > A downstream neighbor N satisfies the equation:  D_opt(N, D) < D_opt(S, D)
> > A loop-free neighbor N satisfies the equation:  D_opt(N,D) < D_opt(N,
> > S) + D_opt(S, D)
> These equations are wrong. The second one doesn't gaurantee loop
> freeness. The first one gaurantees loop freeness and that the neighbor
> is "downstream."

Why do you believe that the second one doesn't guarantee loop freeness???
S is the computing router.  D is the destination.  N is a neighbor of
S.  The question is whether N's shortest path to D goes via S.

> > On S's shortest-path to D, S's next-hop E is a downstream neighbor
> > (unless the link from S to E is cost 0).
> Huh? Again, there are three options for a path, based on the metric:
> - -- The path is your best path. This is known to be loop free.
> - -- Your neighbor's cost is less than your total cost. This is known to
> be loop free, but not the "best."
> - -- Your neighbor's cost is more than your total cost. You don't know if
> this path is loop free or not, and there's no way to tell from the metrics.

And, again, the third one case CAN and IS broken into 2 groups:
loop-free & looping.  Why do you believe that this can't be told from
the metrics???

> >>The concept of "downstream" becomes much more complex in the case of
> >>B->C. Is D a "loop free" neighbor? Based on the defintion given in the
> >>draft, it appears to be--Dopt(B,C) < Dopt(D,C) + Dopt(B,D). But, D's
> >>"alternate path" to C actually runs _though_ C, and therefore D is not
> >>truly downstream of B with regards to C. How can B know the difference??
> > I am confused by how you got this equation.  If the question is
> > whether D is loop-free with regards to B and C, then the equation to
> > check would be:
> >           D_opt(D,C) ?<? D_opt(D,B) + D_opt(B,C)
> > This is false.  Thus D is not loop-free in regards to B & C.
> Okay, so let's go over this again. Using this network:
> A---B---C
> |   |
> D---+
> Alternatives:
> - -- You're saying that if the optimum path to C through D is less than
> the cost of A->B + B->C, then the path through D is not a loop. Yes,
> you're correct--because the path through D is your best path. Now, we
> don't know if the path through B is a loop or not!
> - -- You're saying the path through D is loop free if the cost of A->C <
> A->D + D->C. This would declare all paths as loops other than your best
> path, so that one doesn't make any sense, either.
> - -- You're saying the path through D is loop free if the cost of D->C <
> A->B + B->C. This is true, but this is no different than saying it's
> loop free because A->C < D->C, which is what I said in the first place.
> You don't need to break out the two sections of the path to say this.
> Which of the these three is it?

The equation I gave was from the perspective of B, because you were
asking if D was loop-free with regards to B for a path to the
destination C.

> >>There are three sets of routes in any database:
> >>
> >>- -- One or more shortest paths, known to be loop free.
> >
> > These are the best downstream neighbors
> >
> >>- -- Paths where the neighbor's cost is lower than your cost, which are
> >>gaurenteed to be loop free.
> >
> > These are the remaining downstream neighbors
> >
> >>- -- Paths where the neighbor's cost is higher than your cost, which you
> >>can't know are loop free or not.
> >>
> >>You could divide the last one into two groups, if you can find a way to
> >>tell between loop free and looped paths in this class--but you can't
> >>tell the difference based on your cost and your neighbor's cost alone.
> >
> > You can't tell the difference based upon D_opt(S,D) and D_opt(N,D)
> > alone. You also need to know D_opt(N,S).  With this extra bit of
> > information, one can divide the last group into two.  That's what the
> > LFA draft and the PLSN draft do.
> Where are S, N, and D? Is S the peer you're learning your best path
> from, or the peer you're learning the path you're trying to decide is
> loop free or not? That's part of the confusion here, when you say
> Dopt(N,D) you're not actually saying which path you're comparing to
> what, and why.

I would suggest that you read draft-ietf-rtgwg-ipfrr-framework-03.txt.
 This is where the terminology is defined.
S is the computing router.
N is a neighbor of S. 
D is the destination.
E is the primary neighbor of S on S's shortest path to reach D.

> Going back to the network I've shown:
> A---B---C
> |   |
> +---D
> Based on the metrics alone, how can B tell if D is a loop to C or not?

In reference to what?  Is B trying to determine whether D will send
traffic via B in order to reach C?  If so, I already gave you the

> I don't understand this concept of a "downstream" neighbor. I think what
> you're saying is:
> - -- A loop free neighbor has a path to destination X that does not go
> through me.
> - -- A downstream neighbor has a loop free path to destination X, and is
> not using me as it's next hop, either, so that if I sent traffic to a
> downstream neighbor, I know it will not foward the traffic back to me.

The first for a loop-free neighbor is correct.  For a downstream
neighbor, it is not.

A downstream neighbor has a shortest path to destination D that is
loop-free with regards to S and the shortest distance from the
downstream neighbor to D is less than the shortest distance from S to
D.  (D_opt(N, D) < D_opt(S, D))

> I understand the difference if these are your actual definitions (though
> they need to be clarified in the doc), but I don't see how you can tell
> the difference between the two. Either a neighbor's path is loop free,
> which means their metric is lower than yours--and in that case, they
> won't be using you as their next hop. Or, you don't know if it's loop
> free or not, because your neigbor is using you as their next hop.
> :-)

Why do you think a router S can't tell if a neighbor N's path is
loop-free to a particular destination?

Are you making an assumption that S has only run a single SPF from its
own perspective?  Why do you think this is unknowable?!?!


Rtgwg mailing list
[email protected]

<Prev in Thread] Current Thread [Next in Thread>