[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: Russ White
Date: Wed, 27 Jul 2005 19:50:18 -0400
-----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 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?

> 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?

>>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."

> 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.

>>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?

>>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.

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?

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.

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.

:-)

Russ

- -- 
[email protected] CCIE <>< Grace Alone


-----BEGIN PGP SIGNATURE-----
Version: PGP Desktop 9.0.1 (Build 2185)

iQA/AwUBQugdwxEdu7FIVPTkEQIg8ACcCGQPPKb59lpdiCJm8XAlE05ONMcAoMmj
ng1NNenhTQG1+WtJyyM/vJk5
=mdsv
-----END PGP SIGNATURE-----

_______________________________________________
Rtgwg mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/rtgwg

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