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

From: Russ White <[email-masked]>
Date: Fri, 22 Jul 2005 16:44:11 -0400

Comments on draft-ietf-rtgwg-microloop-analysis-00....

     This document provides an analysis of microloop formation.
     Specifically, we categorize different types of reconvergence
     scenarios, and explore their properties. We then show that in certain
     scenaiors microloops do not form, in others they can be eliminated
     using simple techniques described in this document, and define
     scenarios where more sophisticated loop avoidance mechanisms may be
     necessary.

Replace with:

This document provides an analysis of microloop formation. Specifically,
we categorize different types of convergence scenerios, and explore
their properties, to determine:

   o Which scenerios will not result in a microloop.
   o Which scenerios will result in a microloop, but the microloop can be
eliminated using simple techniques described in this document.
   o Which scenerios will result in a microloop requiring more
sophisticated loop avoidance mechanisms.

The parallelism wasn't right in there someplace. :-)

-

       Downstream neighbor
            Neighbor N of router S is considered S's downstream neighbor
            for destination D, if Dopt(N, D) < Dopt(S, D)

It might be worthwhile to state that you are considering "downstream" to
be "closer to the destination." There's often a lot of confusion in the
concept of downstream and upstream.

-

       Primary neighbor
            Neighbor N of router S is considered S's primary neighbor for
            destination D, if N provides the shortest path to D according
            to the SPF calculation.

There could be more than one of these. Don't know if it's worth
mentioning or not. (After reading a bit further, I see you mention this
in section 3.2, but only after the change. It's worth mentioning here
that there are cases where this is true before the change, and it's
always safe to simply drop the failing path, and rely on the remaining
path, in these cases).

-

       Loop-free neighbor
            Neighbor N of router S is considered S's loop-free neighbor
            for destination D, if Dopt(N, D) < Dopt(N, S) + Dopt(S, D).
            Note that a loop-free neighbor may be, for example, router's
            primary before or after failure.

I don't know if I agree with this.... You're saying a neighbor is only
loop free if the cost from the neighbor to the destination is less than
the cost from the local router to the destination plus the cost from the
neighbor to the local router? That's not true, since their cost could be
much less than yours, but your cost to them is greater than the
differential, which, according to this definition, marks the route as a
loop (actually, I think this formula is worse than that, and marks all
possible alternate routes as loops).

A neighbor always has a loop free route if their cost is less than your
cost--it's geometrically impossible to be otherwise (see Garcia's
original DUAL paper). Your cost to the neighbor in question has no part
to play in determining if they have a loop free alternate path to the
one you have. If Dopt(N,D) < Dopt(S,D), the path is loop free in all cases.

A neighbor MAY have a loop free path, even if their cost is greater than
or equal to yours, but there's no way for you to know that without
taking yourself out of the tree and calculating an SPF from their point
of view (and it's impossible to verify is the destination is only
reachable through an aggregate of information formed along a flooding
domain boundary, which is where I think you've run into problems with
L1/L2/ABRs).

-

            For networks with symmetric link costs, after a topology
            change, it is safe for router X to switch to neigbor Y as its
            next-hop for a specific destination if the path through Y sat-
            isfies both of the following criteria:

            1.   X considered Y as its loop-free neighbor based on the
                 topology before change AND

            2:   X considers Y as its downstream neighbor based on the
                 topology after change.

I would reverse the second requirement--it doesn't matter what X thinks
about where Y should be forwarding traffic, it matters what Y thinks
about where Y should be forwarding traffic. So, perhaps:

Y does not consider X as its downstream neighbor based on the topology
after change. X can infer this as long as it still considers Y a
downstream neighbor after the topology change.

Or something like that (?).

-

            Routers whose new primary next-hops after the topology change
            are safe and transition to them will not create a microloop.
            Two subtypes are recognized:

transition should be transitioning

-

     The following section formally defines the mechanism.

The following section formally defines a mechanism that can be used to
gaurentee this condition.

-

Section 3.2 is a bit confusing. If I have multiple paths of the same
cost after the topology change, they cannot be a mix of types, simply
because they are all equal cost (?). If I have one path that's type A,
and another path of the same cost, how can that second cost be of type
B, since the types are defined based on the costs of the paths?

-

     While this mechanism does not remove all possible micro-loops, it
     addresses the majority of them in topologies with a reasonable level
     of physical redundancy.  Topologically, micro-loop coverage provided
     by this algorithm is

Is?? Is???? I'm dying to know what the rest of this sentence says!!!! :-)

-

And there's one more, I sent Alex previously:

What are "incornsistencies"?? Corn that's sometimes white and sometimes 
yellow? Sorry, just couldn't resist!!! <hehe>

:-)

Russ

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

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

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

---

From: Alia Atlas <[email-masked]>
Date: Fri, 22 Jul 2005 16:03:05 -0700

Hi Russ,

> possible alternate routes as loops).

If N's shortest path to D goes via S, then Dopt(N,D) == Dopt(N,S) +
Dopt(S,D) because a shortest path is comprised of shortest paths.
This is considering the shortest path from N's  view.

If N is a loop-free neighbor for a particular destination, then S can
send that traffic to N & know that it won't come back.   S may choose
to do so for this purpose even if the cost from S to N is high.

> one you have. If Dopt(N,D) < Dopt(S,D), the path is loop free in all cases.

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.

> domain boundary, which is where I think you've run into problems with

S needs to know what its neighbor will do without knowledge of the
topology change.  It isn't necessary for S to remove itself from the
topology before computing the SPF from the neighbor's point of view.
This mechanism is assuming (much like the loop-free alternates) that S
can obtain the necessary information, which can be done by doing an
SPF from each neighbor's viewpoint on the same tree.

Could you expand more on the concerns you have about L1/L2/ABRs?  I
know that we ran into some issues with OSPF where traffic could leave
an area & then possibly re-enter that area, causing unknown loops.
The LFA draft addresses this for OSPF.  I didn't think that there are
similar issues for IS-IS.  What are you picturing?

Alia

---

From: Alia Atlas <[email-masked]>
Date: Wed, 27 Jul 2005 15:03:38 -0700

Hi Russ,

On 7/27/05, Russ White <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> 
> >>       Loop-free neighbor
> 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.

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

> 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:
> 
> 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)

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

> 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.
 
> 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.
 
> See "Loop-free routing using diffusing computations," 1993, JJ Garcia,
> Sections II and III, published in the ACM Transactions on Networking
> (thus available through the ACM, if you're a member). The mathematical
> analysis Garcia provides into "requirements for loop freeness," based
> soley on the metrics, is extensive.

Ok.  I'll take a look.

> In "standard" IS-IS, this isn't a problem, since you never take routes
> from L2 into L1, and therefore you can't have loops. I don't tend to
> think of these problems in terms of a specific implementation,
> though--if you're addressing the theoretical mechanisms of finding
> alternate loop free paths, then the problem is the same, in theory, in
> all possible link state protocols that divide the flooding domain by
> removing topology information at set boundaries within the network. AIMV
> (actual implementations may vary, a corollary of the underlying theory
> that YMMV, or perhaps RLMV).
> 
> :-)

K.  We did a bit of considering the problem  & decided to put an SEP
field around it by specifying applicability restrictions for OSPF,
which is the actual implementation that exhibited the problem.  My
concern was whether the actual implementation for IS-IS might have any
unobvious issues as well.

Alia

---

From: Russ White <[email-masked]>
Date: Wed, 27 Jul 2005 19:50:18 -0400

> 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 cost of a "looping" path that goes via S.

?? How do you know it's a loop?

> A loop-free neighbor N satisfies the equation:  D_opt(N,D) < D_opt(N,

These equations are wrong. The second one doesn't gaurantee loop 
freeness. The first one gaurantees loop freeness and that the neighbor 
is "downstream."

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

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

> 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

- --

---

From: Alia Atlas <[email-masked]>
Date: Wed, 27 Jul 2005 17:25:43 -0700

On 7/27/05, Russ White <[email-masked]> wrote:
> Hash: SHA1

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.

> ?? 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.
 
> freeness. The first one gaurantees loop freeness and that the neighbor

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.

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

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

> Dopt(N,D) you're not actually saying which path you're comparing to

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.

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

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

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

Alia

---

From: Russ White <[email-masked]>
Date: Wed, 27 Jul 2005 20:30:19 -0400

>>tell the difference based on your cost and your neighbor's cost alone.

BTW, I'll make the challenge more specific. Suppose you have these two 
networks:

A-(25)-B-(25)-C
|      |
|     (50)
|      |
+-(25)-D

A-(25)-B-(25)-C
        |      |
       (50)    |
        |      |
        D-(75)-+

How can B tell which is which, based only on metrics (no SPF or split 
horizon tricks allowed, just metrics!). The metrics are identical in 
both cases:

- -- B->C (best) == 25
- -- B->D == 50
- -- D->C (via C) == 75
- -- D->C (via B) == 75

Yet one is a loop, and the other is not. Further, D->C !< B->C, so B 
thinks this is a loop, in both cases--they both fall into the same 
category of the neighbor's cost being more than the local cost, which is 
the category you're saying you can split by looking at the metrics. To 
make matters worse, D is actually ECMP load sharing to C in both cases 
(!), without realizing the traffic is actually passing through the B->C 
link in the first case across both available paths.

Even if you make the B->D link 25 in both cases, B cannot tell the 
difference between these two cases, and making it ECMP just tears the 
entire concept of "downstream neighbor" and "loop free neighbor" 
completely asunder.... :-)

> unobvious issues as well.

In theory, you'd never send traffic through an L1 domain to get between 
two sections of the L2 domain, nor would you ever go through L2 to reach 
some other destination in the same L1 domain, so the problem can't 
exist, really. Now, if you get into a situation where the link failure 
that specifically causes you to fall back to your backup path also 
happens to split the domain, I don't know what the result would be. I 
don't think you'd run into a problem there, either, but it's an 
interesting case to consider, perhaps (?).

:-)

Russ

- --

---

From: Russ White <[email-masked]>
Date: Wed, 27 Jul 2005 21:03:00 -0400

> distance to D.  Shortest paths are a subset of these.
> through S.  Downstream paths are a subset of these.

Agreed. All of C and all of D fall into Dopt(S,D) > Dopt(N,D), based on 
your definition of B. You can't tell which is which by relying on the 
metrics. See my example in my other email....

> shortest possible "looping" path that would go via S.

Hmmm.... I think what you're saying here is that as long as a neighbor's 
cost is less than my cost, it must be loop free, since any additional 
cost, even 1 more, could be a loop. In fact, if a neighbor has an equal 
cost, it could be a loop, in theory, in the case of equal cost multipaths.

> D).   If D_opt(N, D) is less than this, then the path from N to D

Okay, so what you're trying to actually figure out is whether the path 
from N goes through me, S. So, what you're actually trying to split is 
the second case, not the third, from what it looks like. Going back to 
my three cases:

1. This is the lowest cost path. This is loop free.
2. My neighbor's cost is less than my cost. This is loop free.
3. My neighbor's cost is more than my cost. This may, or may not, be 
loop free, but I can't tell from the metrics.

What you're actually trying to determine seems to be whether or not N 
will, or is, using you as its next hop, in case 2. To do this, you have 
to add your cost to N, and see if that's lower or higher than your cost 
to D. If it is, then N must be using the alternate path to D. If it's 
not, then N must be using you as it's alternate path.

Is that right? If so, you're not messing with the third case, you're 
breaking the second case down into it's two options.

> loop-free & looping.  Why do you believe that this can't be told from

See my other example. You can't know the difference between the two.

> own perspective?  Why do you think this is unknowable?!?!

Because of my other example, and my long experience with EIGRP, a 
protocol that uses this specific property of paths to determine a loop 
free feasible successor. :-) I could probably draw you a large number of 
easy to complicated networks where a specific router, under the 
conditions where Dopt(S,D) > Dopt(N,D), may or may not be a loop, and 
the metrics look the same in all cases. Now, breaking the second case 
down into it's two possibilities is useful in the link state case (it's 
not in EIGRP's case, by the way, for various reasons), because you can't 
tell the difference between the two without the second step of 
determining if N must be using S as it's next hop or not.

I do think the draft's wording is a little confusing--I've read it three 
or four times, and couldn't make out what it was trying to say in this area.

:-)

Russ

- --

---

From: mike shand <[email-masked]>
Date: Thu, 28 Jul 2005 09:11:31 +0100

Russ,
         I'm completely confused about what you are saying here. We are 
talking about B wanting to send traffic to C, right? In BOTH cases there is 
a loop. Clearly so in the first case, since there is no other path than 
through B. But in the second case there is also a loop because of ECMP. If 
ANY ECMP path may loop then you have to consider it a loop.

Then you suggest changing the B-D cost to 25. Again in BOTH cases there is 
loop. I don't know what you are trying to show here.

However if you changed the cost of B-D  to 51 THEN it becomes interesting. 
Case 1 is clearly a loop, but case 2 is not.

In neither case is D a downstream neighbor (since the cost from D to C is > 
cost from B to C).

But consider LFAs

we have an LFA if D_opt(N, D) < D_opt(N, S) + D_opt(S, D)

or in this case if  D_opt(D, C) < D_opt(D, B) + D_opt(B, C)

But in case 1 D is NOT an LFA

D_opt(D, C) = 75 (DABC)
D_opt(D, B) = 50 (DAB)
D_opt(B, C) = 25 (BC)

hence 75 !< 50 + 25

whereas in case 2 D IS an LFA

D_opt(D, C) = 75 (DC)
D_opt(D, B) = 51 (DB)
D_opt(B, C) = 25 (BC)

hence 75 < 51 + 25

         Mike

At 01:30 28/07/2005, Russ White wrote:
>-----BEGIN PGP SIGNATURE-----
>Version: PGP Desktop 9.0.1 (Build 2185)
>
>iQA/AwUBQugnJREdu7FIVPTkEQLp1ACg1AeIaNMVkjA9oKNpmIPWzlw4nScAmgJP
>MQ+fkvO2i3jfdiJJXYSCXxth
>=pLCY
>-----END PGP SIGNATURE-----
>

---

From: Russ White <[email-masked]>
Date: Thu, 28 Jul 2005 08:29:13 -0400

> talking about B wanting to send traffic to C, right? In BOTH cases there 
> is a loop. Clearly so in the first case, since there is no other path 
> than through B. But in the second case there is also a loop because of 
> ECMP. If ANY ECMP path may loop then you have to consider it a loop.
> 
> Then you suggest changing the B-D cost to 25. Again in BOTH cases there 
> is loop. I don't know what you are trying to show here.

So, this is part of the problem--what do you mean by "loop?" Do you mean 
D has an alternate path that does not go through B, or do you mean D 
would not send traffic via B to get to C given the current metrics? 
Those are two different definitions, and I've not figured out which one 
the draft is using. I _think_ the draft "wants to mean" that the first 
is a loop free path, and the second is a "downstream neighbor," but the 
formula's don't seem to work this way.

> However if you changed the cost of B-D  to 51 THEN it becomes 
> interesting. Case 1 is clearly a loop, but case 2 is not.

> In neither case is D a downstream neighbor (since the cost from D to C 
> is > cost from B to C).
> 
> But consider LFAs
> 

I see, you're counting on the looped path showing up as an alternate 
lower cost path to the neighbor itself. In other words, this could be 
simlified to if there is a path with lower cost to the neighbor through 
some other path, then the path through the neighbor must be a loop.

Then why not just say so? :-)

The draft is very confusing, and doesn't really explain the principle 
being used here very well at all....

:-)

Russ

---

From: mike shand <[email-masked]>
Date: Thu, 28 Jul 2005 13:51:26 +0100

At 13:29 28/07/2005, Russ White wrote:

>So, this is part of the problem--what do you mean by "loop?" Do you mean D 
>has an alternate path that does not go through B, or do you mean D would 
>not send traffic via B to get to C given the current metrics? Those are 
>two different definitions, and I've not figured out which one the draft is 
>using. I _think_ the draft "wants to mean" that the first is a loop free 
>path, and the second is a "downstream neighbor," but the formula's don't 
>seem to work this way.

If we are considering whether or not B's neighbor D is an LFA (for 
destination C), then what we mean is that if B were to send a packet 
addressed to C to D, then if we can guarantee that the packet will not come 
back to B we can say that D is an LFA. If the packet MAY come back to B, 
the D is not an LFA.

The conditions for this to be true are described by the relationship 
D_opt(D, C) < D_opt(D, B) + D_opt(B, C)

{aside...
Now I confess that I personally don't find the mathematical expression of 
these things particularly easy to manipulate in my mind. I much prefer a 
pictorial way of thinking about it. But nevertheless, the mathematical 
version is I think correct.
}

A downstream route is a much stronger requirement than an LFA. i.e. a 
downstream route is always an LFA, but the converse is not true.

In the draft we are considering, the safety condition is that we have an 
LFA in the old topology and a downstream route in the new topology.

As explained we cannot just choose LFA in both old and new topologies, 
since that could result in a loop. Using the stronger downstream 
requirement prevents this.

It would also be guaranteed loop free if we used downstream in both old and 
new (the so called assymetric cost condition), but this would dramatically 
reduce the number of type A pairs found.

One source of confusion here may be that we are talking about two sorts of 
"loops". There are the loops we are considering when we decide whether a 
neighbor is an LFA or not, and there are the loops which may form during a 
topology change. The two are related, but not the same thing.

         Mike

>I see, you're counting on the looped path showing up as an alternate lower 
>cost path to the neighbor itself. In other words, this could be simlified 
>to if there is a path with lower cost to the neighbor through some other 
>path, then the path through the neighbor must be a loop.
>

---

From: Alia Atlas <[email-masked]>
Date: Thu, 28 Jul 2005 10:57:56 -0700

Russ,

I think, from this email & the next one, I've got a slightly better
idea of what you're saying.  I was misinterpreting the "unknowable
from metrics".

The context for LFAs and PLSN, I think, has been link-state protocols
and not distance vector.  Because it is a link-state protocol, all the
topology is known at S and S can run multiple different SPFs to find
out the necessary information.  Certainly for a distance-vector
protocol, the SPF computation is what is distributed; I'm not sure
whether one could take the partial information & use that.  I've not
read that paper yet, so it feels like it could be possible :-) but I
haven't thought about it.

Want to? ;-)

> horizon tricks allowed, just metrics!). The metrics are identical in

Ah, in both cases:
   D->C == D->B + B->C

thus, it fails the loop-free test.  Both are loops, if one assumes
that D is doing ECMP & B has no information to assume otherwise.

> completely asunder.... :-)

ECMP is considered in these cases.  That's why both are considered loops!

> interesting case to consider, perhaps (?).

Yes, probably.  Maybe Mike's thought about that one?

Alia

---

From: Alia Atlas <[email-masked]>
Date: Thu, 28 Jul 2005 11:06:55 -0700

> the second case, not the third, from what it looks like. Going back to

No, I'm trying to split the third case.  
The case of downstream neighbors where D_opt(N,D) < D_opt(S,D) isn't
the issue here.  Those are loop-free by virtue of a each hop along a
shortest path being monotonically decreasing.

> not, then N must be using you as it's alternate path.

I'm trying to determine this for case 3.  The question is how will N
decide to forward a packet to D.  Is it via S or not?  N will use the
shortest path - so if N->S + S->D is shorter than any other known path
from N->D, N will use that.

> determining if N must be using S as it's next hop or not.

I have not thought about this in the context of EIGRP (for obvious
reasons :-) but I am confused by why you are unwilling to consider the
knowable information for N->S.

Again, I am not concerned with the downstream neighbors case, which
is, as I understand it, what EIGRP uses.

Also, the question is not whether N is using S as its next-hop, but
whether S is in the path from N to D.

> or four times, and couldn't make out what it was trying to say in this area.

Did you have a chance to loop at the framework & LFA drafts?  Clearly,
from this conversation, the PLSN draft needs some clarifications &
rewording. :-)

Alia