[email protected]
[Top] [All Lists]

Re: Comparison of symmetric and asymmetric PLSN algorithms

Subject: Re: Comparison of symmetric and asymmetric PLSN algorithms
From: mike shand
Date: Mon, 13 Jun 2005 16:36:31 +0100
At 16:01 13/06/2005, Alia Atlas wrote:
At 08:24 AM 6/8/2005, mike shand wrote:
At 22:29 07/06/2005, mike shand wrote:
At 21:56 07/06/2005, Alia Atlas wrote:

Do you have any info on the length of the multi-hop loops? I.e., one loop that is 5 links long might want to count more...
The numbers are very interesting.

No. At the moment I don't even know how many multihop loops there are (if any). Of course I could record both of those statistics... I'll see what I can do tomorrow.
Well, it turns out that it is rather more difficult than I thought to get
this information owing to the recursive way I explore for loops. However,
it seems this was a bad choice of network, since despite the presence of
asymmetric costs there are no multi-hop loops caused by them. So it is
not surprising that we get the result we did!
Going back to the original asymmetric cost diagram that Pierre used, we
get the following results
asym    sym
0       0
0       0
0       0
4       5       3 of which are 3 hop loops
0       0
0       0
0       0
8       6       all 6 of which are 3 hop loops
So, in the asym case, all the loops are 2-hop?
Yes, because although it prevents the 3 hop loops it results in more type
C-C pairs which give 2 hop loops (as normal).
Whether it is POSSIBLE to get multi-hop loops (say between multiple type C
nodes) when using the asym algorithm, I'm not sure. I don't think I have
seen any, but that doesn't mean they can never exist.

So this is more of a swings and roundabouts case.

I'm beginning to think that we can ignore the asymmetric cost case unless we have evidence that doing so would make things dramatically worse.
You aren't catching real multi-hop loops in the topologies that you have?
Not sure what you mean. There can't be any loops in the converged topologies.

  What about cases where one direction of the link changes to be max-cost?
Interesting. Of course if the connectivity fails in just one direction the
reverse connectivity check (does OSPF have that to?) would cause BOTH
directions to be treated as failed simultaneously. Going to max-cost is a
different matter since I don't think implementations count that as failing
the RCC.
My first take on this is that it shouldn't make any difference since in the
SPT a link can only ever exist in one direction (or none) at once.
Do you think such a topology transformation is likely to cause the multi-hop loops.
On the above quick analysis, no, but I reserve the right to be wrong:-)

My only caveat would be that if we want to combine PLSN with some other loop prevention technique to get 100% coverage (e.g. using tunnels only for the cases not dealt with by PLSN), then we should probably use the asymmetric cost algorithm even though it might result in using more tunnels than necessary. The reason is that the multi-hop loops which occur while using the symmetric cost algorithm are (currently) unpredictable, and hence it is difficult to know when to use a tunnel to avoid them. Whereas the extra single link loops which occur by using the asymmetric algorithm are at least predictable (they can only occur over type C pairs). Of course if we could figure out how to predict the multi-hop loops, then this wouldn't matter.
There might be a way to predict the multi-hop loops over type A and type
B, but the complication of different routers on the path using either the
old or new topology would certainly make it more complex.

Hmmm. Is it true that using the asymmetric algorithm prevents ALL multi-hop links, or can we still get multi-hop loops around cycles which are all type C.
We can still get multi-hop loops around cycles that are all type C, I
believe. Certainly, we can get 2-hop loops around cycles that are all type C.
Yes, that is what I was postulating above,

The asymmetric algorithm is to avoid the type A or type B actually loopin.g


I just tried a randomly generated topology with all (very) asymmetric links and managed to produce a 9 hop loop, which traversed 6 type C nodes, 2 type As and a type B!!!
Testing path from node 8 (8) to node 7 (7) at time 1

Node 8 (8): Packet discarded because looped
Node 19 (19) New: Forwarded via adj 1 over link 42 to node 8
Node 3 (3) New: Forwarded via adj 1 over link 13 to node 19
Node 28 (28) New: Forwarded via adj 1 over link 37 to node 3
Node 18 (18) New: Forwarded via adj 1 over link 18 to node 28
Node 29 (29) New: Forwarded via adj 1 over link 47 to node 18
Node 22 (22) New: Forwarded via adj 1 over link 23 to node 29
Node 11 (11) Temp: Forwarded via adj 1 over link 44 to node 22
Node 26 (26) Old: Forwarded via adj 1 over link 8 to node 11
Node 8 (8) Old: Forwarded via adj 1 over link 15 to node 26

(read the trace going up)

Node 11 is type B and nodes 3 and 11 are type A for the destination node 7

So at time 1 (when the type C's change), type A MUST forward according to new topology, type B according to the temporary type B next hop, and the type C either according to old or new topology (since they are in the process of changing)
So, yes, we can get multi-hop loops with the asymmetric algorithm!


Rtgwg mailing list
[email protected]

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