[email protected]
[Top] [All Lists]

Re: Comparison of symmetric and asymmetric PLSN algorithms

Subject: Re: Comparison of symmetric and asymmetric PLSN algorithms
From: Alex Zinin
Date: Mon, 13 Jun 2005 18:56:37 -0700
Mike, Alia-

 Interesting results. Makes me wonder if we really want the asym condition.
 Given that the trade-off seems to be one type of loops vs another, I guess

 One other interesting observation is that the affect of a few asym links
 in a normally sym network appears to be reasonably small, and hence
 changing link costs in a sym network should not have a drastic affect.


Monday, June 13, 2005, 8:36:31 AM, mike shand wrote:
> 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

> Yes.


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

>          Mike

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

Rtgwg mailing list
[email protected]

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