Subject: Comparison of symmetric and asymmetric PLSN algorithms

From: mike shand <[email-masked]>
Date: Tue, 07 Jun 2005 20:13:32 +0100

I know this is just one datapoint, but here are some results for the 
comparison of the two PLSN algorithms for a real world network having a few 
asymmetric cost links (14 out of a total of 340).

The numbers give the number of source destination pairs which are subject 
to looping for each of the links which generate a non-zero number of loops.

There are 187 nodes in this network, and hence 34782 possible source 
destination pairs.

As you can see, the results for the symmetric algorithm are (as expected) 
much better than the asymmetric, even though there will be some loops extra 
loops caused by the use of the "wrong" algorithm. But note that in no case 
is the symmetric algorithm worse than the asymmetric.

Clearly a network with more asymmetric links (or perhaps links having more 
asymmetry, or both) would be more likely to give a result in favour of the 
asymmetric algorithm. But this network is fairly typical of the real world 
collection I have.

asymsym
49200
12140
11411141
10200
5160
4720
452352
4260
3900
3270
18385
1800
175174
157138
157138
157138
12417
1200
1100
9415
9415
8915
5620
5454
500
360
300
280
278
1414
70
60
00
00 

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

---

From: Alia Atlas <[email-masked]>
Date: Tue, 07 Jun 2005 16:56:01 -0400

Mike,

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.

Alia

At 03:13 PM 6/7/2005, mike shand wrote:
>comparison of the two PLSN algorithms for a real world network having a 
>few asymmetric cost links (14 out of a total of 340).
>
>much better than the asymmetric, even though there will be some loops 
>extra loops caused by the use of the "wrong" algorithm. But note that in 
>no case is the symmetric algorithm worse than the asymmetric.
>

---

From: mike shand <[email-masked]>
Date: Tue, 07 Jun 2005 22:29:53 +0100

>The numbers are very interesting.

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

         Mike

---

From: mike shand <[email-masked]>
Date: Wed, 08 Jun 2005 13:24:31 +0100

At 22:29 07/06/2005, mike shand 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...
>>
> 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 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.

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.

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.

The more I think about this the more my brain hurts.

         Mike

---

From: Alia Atlas <[email-masked]>
Date: Mon, 13 Jun 2005 11:01:51 -0400

At 08:24 AM 6/8/2005, mike shand wrote:
>>         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.
>
>Going back to the original asymmetric cost diagram that Pierre used, we 
>get the following results
>
>asym    sym
>0       0
>0       0
>0       0

So, in the asym case, all the loops are 2-hop?

>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?  What about cases where one direction of the link changes to be 
max-cost?   Do you think such a topology transformation is likely to cause 
the multi-hop loops.

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

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

Alia

---

From: mike shand <[email-masked]>
Date: Mon, 13 Jun 2005 16:36:31 +0100

At 16:01 13/06/2005, Alia Atlas wrote:
>>> there are (if any). Of course I could record both of those 
>>> statistics... I'll see what I can do tomorrow.
>>
>>asymmetric costs there are no multi-hop loops caused by them. So it is 
>>not surprising that we get the result we did!
>>

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.

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

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

Yes, that is what I was postulating above,

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

Yes.

>Alia

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

---

From: Alex Zinin <[email-masked]>
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
 not.

 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.

-- 
Alex
http://www.psg.com/~zinin

---

From: Alia Atlas <[email-masked]>
Date: Tue, 14 Jun 2005 11:10:10 -0400

At 11:36 AM 6/13/2005, mike shand wrote:
>>>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.
>>

What I was asking was whether you are seeing multi-hop micro-forwarding 
loops using the symmetric condition & PLSN during the transition on the 
real network topologies that you have.

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

I was asking about the max-costing because that is something that does 
occur in networks to cause asymmetric link costs.

If the networks with asymmetric link costs that you have seem to have fewer 
unresolved micro-loops across fewer links using the symmetric condition, 
then that's a good start to think that the symmetric condition is the way 
to go.   To be even more comfortable with that, it'd be very good to see if 
similar behavior holds with links costed out causing asymmetric costs.  I 
imagine that the primary case to consider might be when an entire router's 
links are all costed-out, as in RFC3137.  An operator taking a link out via 
costing would probably do it in both directions; similarly, the costing out 
of a link due to lack of an LDP session should occur in both directions - 
though it needn't.

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

Excellent!  I assume this was using the symmetric condition- because there 
are type As and a type B in it?  What does it look like using the 
asymmetric one?

Do you think we can adequately describe the topology conditions that can 
lead to the multi-hop micro-loop problem with the symmetric condition?

Alia

---

From: mike shand <[email-masked]>
Date: Tue, 14 Jun 2005 16:47:17 +0100

>real network topologies that you have.

Ah. I understand now. Yes I do see the occasional multi-hop loop in real 
topologies using the symmetric condition.

>>Interesting. Of course if the connectivity fails in just one direction 
>>the reverse connectivity check (does OSPF have that to?) would cause BOTH 
>>different matter since I don't think implementations count that as 
>>failing the RCC.
>>
>If the networks with asymmetric link costs that you have seem to have 
>fewer unresolved micro-loops across fewer links using the symmetric 
>condition, then that's a good start to think that the symmetric condition 
>is the way to go.   To be even more comfortable with that, it'd be very 
>good to see if similar behavior holds with links costed out causing 
>asymmetric costs.  I imagine that the primary case to consider might be 
>when an entire router's links are all costed-out, as in RFC3137.  An 
>operator taking a link out via costing would probably do it in both 
>directions; similarly, the costing out of a link due to lack of an LDP 
>session should occur in both directions - though it needn't.

Understand. So I should try going through each node, setting all its link 
costs to be infinite in the direction from that node, and looking for 
loops? Is that what you mean?  I'll put it on the list of things to try.

>>links and managed to produce a 9 hop loop, which traversed 6 type C 
>>nodes, 2 type As and a type B!!!
>
>are type As and a type B in it?

Um... what am I missing here? It is still possible to get type A and B with 
the asymmetric condition isn't it?

>   What does it look like using the asymmetric one?

I get the loop with both sym and asym conditions.

>lead to the multi-hop micro-loop problem with the symmetric condition?

Perhaps, but I'm not going to attmept it right now:-)

         Mike

---

From: Alia Atlas <[email-masked]>
Date: Tue, 14 Jun 2005 12:23:59 -0400

>topologies using the symmetric condition.

OK.  But the frequency (number of micro-loops * number of links affected) 
is better with the symmetric condition than with the asymmetric?

>loops? Is that what you mean?  I'll put it on the list of things to try.

I'm sure you've got a long list :-)  That's basically what I mean/think 
makes the most sense.

>>Excellent!  I assume this was using the symmetric condition- because 
>>there are type As and a type B in it?
>
>Um... what am I missing here? It is still possible to get type A and B 
>with the asymmetric condition isn't it?
>

I'm a bit confused then.  A multi-hop loop with the asymmetric condition 
shouldn't  go through type A or type B nodes.  That's the point of changing 
the condition to be stricter.

Regardless of whether a node is using the old topology or the new topology, 
with the asymmetric condition, a type A or a type B router will use a 
next-hop between DELAY_SPF and DELAY_TYPEB will be closer to the 
destination.  This guarantees monotonically decreasing distance, so that 
loops cannot form.

Thus, a multi-hop micro-loop could go through a lot of type C's, but as 
soon as it hits a type B or type A, I'd think it would exit the loop.

Maybe I'm missing something.  I guess it might be possible for a type C to 
send back up , but I'm not seeing how.   Consider a type A node A and a 
type C node C - where C is the first type C node encountered on A's 
next-hop path to D (where this path is that used between DELAY_SPF and 
DELAY_TYPEB).

We know that:
          D_old(A, D) > D_old(C,D)
          D_new(A, D) > D_new(C, D)

Can you describe the topology you're using?  I'm not picturing how one 
could get the multi-hop micro-loop between type A, B and C when using the 
asymmetric condition.

>Perhaps, but I'm not going to attmept it right now:-)

Not a 5-minute response-time email?  I'm shocked :-)

Alia

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

---

From: mike shand <[email-masked]>
Date: Tue, 14 Jun 2005 18:33:30 +0100

>is better with the symmetric condition than with the asymmetric?

Yes. We loose the multi-hop loops (in general... see below), but gain a lot 
more single hop loops becuase the stricter condition results in more C-C pairs.

>>>condition, then that's a good start to think that the symmetric 
>>>condition is the way to go.   To be even more comfortable with that, 
>>>it'd be very good to see if similar behavior holds with links costed out 
>>>causing asymmetric costs.  I imagine that the primary case to consider 
>>>might be when an entire router's links are all costed-out, as in 
>>>RFC3137.  An operator taking a link out via costing would probably do it 
>>>in both directions; similarly, the costing out of a link due to lack of 
>>>an LDP session should occur in both directions - though it needn't.
>>

OK

>shouldn't  go through type A or type B nodes.  That's the point of 
>changing the condition to be stricter.

Yes, but it can still be fed back into it by a chain of C's

So in the example I gave, for a destination of node 7 (which is at the 
other end of a link connected to node 22) we have nodes 3 & 19 which are 
type A even with the asym condition.

After the failure 3's route to 7 is via 19 (and hence 19 is downstream), 
but before the failure 19 is also downstream, since 19's route to 7 is via 
nodes 2 and 26. hence 19 is a safe neighbor.

Similarly, after the failure 19's route to 7 is via 8 (hence 8 is 
downstream). Before the failure 19's route is via 2 (as before), but 8 has 
a path via 26. hence it is downstream of 19 both before and after the failure.

After the failure, 22's route to 7 is via 29,18,28,3,19,8,1,9,7.

BTW if I didn't mention it before the failing link is between 22 and 7.

If it helps, the following describes the topology

Much of it is irrelevant, but it is just what got randomly created.

link  2 to 12 cost 257 rev 4530
link  18 to 30 cost 265 rev 3480
link  19 to 2 cost 146 rev 30
link  22 to 7 cost 261 rev 2620
link  23 to 17 cost 368 rev 3830
link  24 to 17 cost 193 rev 2710
link  25 to 13 cost 142 rev 1720
link  26 to 11 cost 312 rev 1800
link  27 to 4 cost 356 rev 3450
link  28 to 10 cost 219 rev 4420
link  29 to 5 cost 246 rev 2450
link  1 to 9 cost 500 rev 2950
link  3 to 19 cost 408 rev 1200
link  6 to 14 cost 264 rev 320
link  8 to 26 cost 135 rev 4580
link  12 to 24 cost 126 rev 4100
link  15 to 6 cost 205 rev 3330
link  18 to 28 cost 402 rev 130
link  22 to 20 cost 189 rev 3920
link  23 to 24 cost 496 rev 2770
link  25 to 28 cost 116 rev 4890
link  27 to 21 cost 488 rev 3390
link  29 to 22 cost 430 rev 1100
link  1 to 8 cost 100 rev 630
link  2 to 26 cost 148 rev 3630
link  3 to 25 cost 227 rev 4550
link  4 to 16 cost 15 rev 4460
link  11 to 16 cost 319 rev 2650
link  12 to 26 cost 11 rev 2720
link  14 to 15 cost 139 rev 400
link  18 to 23 cost 64 rev 860
link  19 to 17 cost 357 rev 2030
link  27 to 30 cost 383 rev 4880
link  29 to 21 cost 156 rev 2400
link  1 to 15 cost 68 rev 4630
link  2 to 23 cost 157 rev 2610
link  3 to 28 cost 384 rev 790
link  4 to 24 cost 301 rev 770
link  5 to 20 cost 16 rev 4600
link  6 to 12 cost 413 rev 3990
link  7 to 9 cost 236 rev 2690
link  8 to 19 cost 301 rev 1200
link  10 to 30 cost 479 rev 950
link  11 to 22 cost 178 rev 2870
link  13 to 27 cost 440 rev 3360
link  14 to 25 cost 359 rev 3140
link  18 to 29 cost 241 rev 2310

Sorry its overly complex. I'm sure it would be possible to extract a subset 
which had the required properties.

         Mike

>Regardless of whether a node is using the old topology or the new 
>topology, with the asymmetric condition, a type A or a type B router will 
>use a next-hop between DELAY_SPF and DELAY_TYPEB will be closer to the

---

From: Alia Atlas <[email-masked]>
Date: Tue, 14 Jun 2005 16:06:22 -0400

Mike,

>Yes, but it can still be fed back into it by a chain of C's

Thanks for the copious examples :-)  I see exactly what you're talking 
about now.  Essentially, the shortest path in one direction between 2 type 
Cs might be via multiple hops that are type C.   I hadn't fully appreciated 
that.

Alia

>Sorry its overly complex. I'm sure it would be possible to extract a 
>subset which had the required properties.
>
>         Mike
>
>
>
>
>
>>Maybe I'm missing something.  I guess it might be possible for a type C 
>>to send back up , but I'm not seeing how.   Consider a type A node A and 
>>a type C node C - where C is the first type C node encountered on A's 
>>>>Do you think we can adequately describe the topology conditions that 
>>>>can lead to the multi-hop micro-loop problem with the symmetric condition?
>>>
>>>>>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)
>>>>>