Cranckback and ARO. Really a problem ?

[ricciato <ricciato@coritel.it>]

Hi JP, Cheng-Yin, ccamper,

this message relates to  crankback within the ARO scheme, and I think 
also address the comments issued by Cheng-Yin.


I see the following main cases in which the signaling procedure with ARO 
fails, which then trigger cranckback:
1. lack of bwandwidth
2. some trap-like case (see below)


Regarding 1,  my feeling is that bw exahustion should be considered 
pretty like as a "exceptional" event in an operational network (it 
indicates that the carrier shoul have increased the link bw some time ago).
In this case the ARO sheme will have maybe to cranckback, but I think 
that any scheme that is efficient in the most common cases, while  
leading to some additional burrden (i.e., cranckback signaling) in some 
rare cases is definitely better than any alternative scheme that adds a 
lot of signaling overhead in all cases (*).
At least, this is my humble opinion, but maybe I´m wrong.
Accordingly, I do not think this is a really critical point, but I´m 
open to further discuss it.

Regarding 2, I´ll try to explain in the following that there might be 
some "particular" intra-AS topologies that, coupled with some "special" 
inter-AS conectivity scheme, lead the ARO scheme to crankback.
However, let me denote by P the probability that such case occurr for 
one area
(i.e. the probability of the joint event: "particular" topology in the 
AS(k)  _AND_  "special" connectivity scheme between AS(k) and AS(k+1)).
Therefore, the probability that the ARO signaling will have to 
cranckback of N backwards hops (=AS) is P ^ N (P to the power of N), 
which should be negligible for more than 1 hop since P<<1.

Therefore, in the worst case for _parallel computation_ (that occurr 
with probability P^N) you have to cranckback completely. But most 
cranckback events, if any at all, should be confined in a single hop 
(see below).

Let me also add that the "worst-case" for the alternative _sequential 
computation_ (i.e. presence of at least one trap topology along the 
path) occurrs with a higher probability than the worst-case for ARO, and 
always lead to complete cranckback. (Again, I´m open to expand on this 
point if there´s interest on the ml)

Now, let me try to expose what a "particular" intra area topology is, 
and what a "special" interconnectvity scheme.

I´ll use the same notation of my previous mail 
(http://ops.ietf.org/lists/ccamp/ccamp.2004/msg00474.html):

> Consider a linear topology of ASs from AS(1) (the source AS) to AS(N) 
> (the destination AS).
> Denote by I(k) and E(k), respectively, the ingress and egress nodes to 
> AS(k). Where needed, I'll distinguish between the ingress of the 
> primary and secondary path, respectively, by I1(k) and I2(k). Same for 
> th egress nodes (i.e., E1(k), E2(k)).


Let assume that at some point along the path, say at AS(J), you have 
only 2 egress points to AS(J+1) (we assumed that are not less than 2 in 
the draft), and 3 ingress point to AS(J+1), and that the first signaling 
phase for ARO has hitted I1(J+1) while only I2(J+1) and I3(J+1) have 
disjoint pairs towards the next AS(J+2). In this case it is not 
difficult to show that only 1-link cranckback  (i.e., from I(J+1) to  
E(J) suffices to overcome the block.

Let´s assume a more nasty case, in which there are 3 egress points from 
AS(J) and 3 ingress on AS(J+1), with just 1:1 links between the E(J) and 
I(J+1) sets.
Similarly to above, let´s assume that the topology inside AS(J+1) is 
such that  only I2(J+1) and I3(J+1) have disjoint pairs towards the next 
AS(J+2), while the signaling procedure ha hitted I1(J+1).
In this case, since we assumed 1:1 links between E(J) and I(J+1), you 
have to cranckaback of 1-hop, until I(J) !
But then, from I(J) in general you can find a disjoint pair passing from 
the other two egress in AS(J), in our case E2(J) and E3(J), thus 
avoiding E1(J) (*)

If this is not the case, you have hitted what I called a "particular" 
topology: the selected I(J) (say I1(J) and I2(J) ) have a disjoint pair 
to E1(J)+E2(J) or to E1(J)+E3(J) , but _not_ to E2(J)+E3(J) , AND there 
are other candidate ingress points to AS(J) other than I(J).

...you see how many AND events have to apply in order to have a 1-hop 
cranckback ? so I guess in real scenario the probability P being small.
and to have a  cranckback of N hops, you should have this P to the power 
of N !
and, even in this worst case, when the ARO approach involve a complete 
cranckback, I´m wondering if other scheme can find a solution at all.

In summary, it might be the case that the ARO scheme suffer some severe 
limitations that will be recognized in the rest of the discussion in the 
mailin list,
but in  my  feeling at the moment  the problem of cranckback is not one 
of that.

Any further comment is very wellcome !

ciao
Fabio



Notes:

(*) BTW this might point to the RFC 3439 that was brought to our 
attention by Dimitri in his mail on 04/29/2004, which I found really 
intersting reading !

(**)It comes to my mind that we could use the XRO in this case, to tell 
I(J) that they should avoid E3(J) .. .uau ! a joint ARO + XRO scenario!  
with XRO acting in the cranckback.
somebody thinks this deserves further interest ?





>     As a working hypothesis, we will assume that every inter-area 
>                  connection  is  duplicated.  In  other  words,  it  is  realized  by 
>                  interconnecting at least two different border nodes on each side. 
>                  This assumption is required to enforce  node-disjointedness,  and 
>                                                    
>               DÆAchille et al.   Internet draftûexpires July 2004       Page 3 of 25 
>                
>
>               draft-dachille-inter-area-path-protection-01.txt          January 2004
>                                                   
>                  corresponds to the usual way in which inter-AS connections are 
>                  arranged in pratice.