
On 7/27/05, Russ White <[email protected]> wrote:
> BEGIN PGP SIGNED MESSAGE
> 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 loopfree
> > 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 nexthop's distance to D is less than S's
distance to D. Shortest
paths are a subset of these.
c) loopfree paths: the nexthop's shortest path(s) to D do not go
through S. Downstream
paths are a subset of these.
d) looping paths: the set of nexthops 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 loopfree path
> > with regard to S to reach the destination; if so, S can use N_i as a
> > loopfree 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+
> >> 
> >> SD
> >> 
> >>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:
> >>
> >>ABC
> >> 
> >>D+
> >>
> >>Now, what you say here:
> >>
> >>
> >>>This is the tighter condition of a downstream neighbor, which is a
> >>>subset of the loopfree 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 loopfree neighbor
> > is based on the costs.
>
> > A downstream neighbor N satisfies the equation: D_opt(N, D) < D_opt(S, D)
> > A loopfree 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 shortestpath to D, S's nexthop 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:
loopfree & 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 beDopt(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 loopfree 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 loopfree in regards to B & C.
>
> Okay, so let's go over this again. Using this network:
>
> ABC
>  
> 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 correctbecause 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 loopfree 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 classbut 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 draftietfrtgwgipfrrframework03.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:
>
> ABC
>  
> +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
equation!
> 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 loopfree neighbor is correct. For a downstream
neighbor, it is not.
A downstream neighbor has a shortest path to destination D that is
loopfree 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 yoursand 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
loopfree 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?!?!
Alia
_______________________________________________
Rtgwg mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/rtgwg

