Subject: Diverse path failure and optimality in draft-dachille-inter-area-path-protection

From: ugo monaco <[email-masked]>
Date: Mon, 26 Apr 2004 02:26:27 +0200

Dear ccamper, Zafar, Dimitri,

as anticipated in the recent email by Vishal we are addressing 
several important comments collected at Seoul regarding the joint-selection 
of diverse paths with ARO, i.e. the approach proposed in 
<http://www.ietf.org/internet-drafts/draft-dachille-inter-area-path-protection-00.txt>.

As Vishal did I summarized your comments to ensure that we rightly
understood inputs, and to help people on the ML follow
and contribute to the discussion.
Comments from others who have feedback are welcome, and
much appreciated.

Please let me know if you had any additional comments
as well. We will take these into account in providing our
responses, and, later, in updating the document.

Thanks again for your feedback on our draft during the Seoul meeting.
Best Regards.

Ugo Monaco

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Zafar's questions:

i) What happens when the setup of the diverse path fails, or there is a
 failure on it after it has been set up?

ii) Relationship of this scheme to PCS/PCE approach of JP?

Dimitri Papadimitriou

i) Your question was about why we are trying for optimality with a joint 
path selection scheme, when it is not possible, especially as the number 
of AS's or areas along a path increase, to achieve the *global* optimum.
Your other comment was that we should mention this somewhere in the document.

Please note that in response to this last question Fabio Ricciato listed many
advantages of a joint computation (with ARO) of inter-area/AS paths in a 
prevoius email posted on the ML "About optimality of inter-AS parallel 
computation in draft-dachille-inter-area-path-protection".
We hope that Fabio rightly addressed your input and we will appreciate further 
comments and notes.

---

From: [email-masked]
Date: Mon, 26 Apr 2004 15:47:15 +0200

hi, by discussing the proposed method there seems to be three issues 
that make the method questionable in terms of guarantee to deliver what 
it intends to deliver, its usability (the time validity of the path is 
not guaranteed) and its applicability in terms of objective initially 
targeted wrt to the network topology

1) imagine three areas decoupled computation as explained at their
respective ingress, with ARO method; how the third computation element
(tail-end) is aware of srlg's that may affect a link selected in the
head-end area

example: link 1 is selected in area 1 (head-end) with srlg 1, link 2 is
selected in in area 2 with srlg 2, and link 3 in area 3 (tail-end) with
srlg 3 and 1 (since the tail end doesn't know that srlg 1 is associated
to link 1 in addition to its association to link 3 even if it knows that
the link 1 has been selected for the ARO) the problem is that you can
not retrieve such kind of error (except but how practical is it if one
start cumulating all this information between computation points)

2) resource contention, the secondary path may never be established
since the computation point as *no* capability to make any reservation
on it (except from the first segment) since by definition "disjoint" -
it simply becomes a kind of "best effort" secondary path (in the sense
use it if no other reservation are making use of these links)

3) the method seems to raise additional issues when the number of 
potential entry point for the secondary disjoint path increases, at each 
step of the computation (otherwise the method wouldn't provide what it 
intends to deliver)

thanks,
- dimitri.

ugo monaco wrote:

> as anticipated in the recent email by Vishal we are addressing several 
> important comments collected at Seoul regarding the joint-selection of 
> diverse paths with ARO, i.e. the approach proposed in 
> We hope that Fabio rightly addressed your input and we will appreciate 
> further comments and notes.
> 
> 
> 
> 

-- 
Papadimitriou Dimitri
E-mail : [email-masked]
E-mail : [email-masked]
Webpage: http://psg.com/~dpapadimitriou/
Address: Fr. Wellesplein 1, B-2018 Antwerpen, Belgium
Phone  : +32 3 240-8491

---

From: ricciato <[email-masked]>
Date: Tue, 27 Apr 2004 12:43:17 +0200

Hi Dimitri,

thanks for your comments, see inline.

ciao
Fabio

[email-masked] wrote:

> that make the method questionable in terms of guarantee to deliver 
> what it intends to deliver, its usability (the time validity of the 
> path is not guaranteed) and its applicability in terms of objective 
> initially targeted wrt to the network topology
>

You´re rising this problem with SRLGs spanning non-adjacent areas.

First, I do not know if this is a common case in practical scenarios. 
Can other ccampers comment on that ?

Second, IMHO this case is hard to handle for _any_ distributed scheme, 
in lack of any exchange of info between computation points about srlg 
spanning multiple area.
For instance, I´m wondering if the sequential computation with RRO+XRO 
(as alternatve to parallel computation with ARO) can handle this 
scenario, or not.
Could you comment on that ?

> use it if no other reservation are making use of these links)

In the parallel approach with ARO, during the first phase the primary 
LSP is establisehed (including bw reservation), while for the  secondary 
only the path is computed.
This computation is base on the topology / load information available at 
the computation point, so that link without enough bw are pinned out and 
can not be included in the primary nor the secondary LSP.
In a successive phase,  the secondary LSP is reserved along the 
secondary path.

What can happen is a race condition, where the bw along the secondary is 
available during the 1st phase, but not during the 2nd phase, since some 
other reservation occurred  in between the two along some secondary link.
If this occurr, the secondary path can not be established, and maybe all 
the signaling procedure has to be repeated, for primary for secondary. 
(btw, let me expand in a separate mail the discussion about the case of 
unsuccesful computation, which was also raised by others )

First, I remark that this time window in which the race can occurr is 
really short, in the order of one PATH/RESV round trip time, and since 
hopefully you´re not going to operate your network at it´s capacity 
limit, the probability of failing signaling due to a race should be 
really small.

Second, I think that races are a well-known  problem common to   _all_  
distributed computation/reservation schemes, i.e. not specific to 
parallel computation with ARO
 (incidentally, I note that RSVP itself is prone to race since the path 
computation occurss in the downstream PATH messages, while the bw 
reservation is applied during the upstream RESV messages).

> potential entry point for the secondary disjoint path increases, at 
> each step of the computation (otherwise the method wouldn't provide 
> what it intends to deliver)

It is not clear to me what are exactly these additional issues, maybe 
you´d like to provide some more concrete example.
In general,  my feeling is, again, that such issue might be non-specific 
to the parallel computation scheme, but rather common to any dstributed 
scheme.

However, there was a point raised by Adrian that might have some 
relationship to the choice of the entry-point for the secondary path.
If this is the case, you might find some  interesting hints in my 
previous mail (posted Mon, 19 Apr 2004, 
http://ops.ietf.org/lists/ccamp/ccamp.2004/msg00474.html ... sorry it´s 
so long :-)

As a last but important remark, let me suggest to distnguish the 
problems that are intrinsic to _all_ distributed diverse path 
computation schemes, from those that are specific to one scheme (e.g. 
parallel comp. with ARO).  Both are important of course, but it would be 
beneficial to the discussion to clearly separate them in different 
tracks in the ml.
I´d solicit other ccamp-ers also to comment on that.

---

From: "Vishal Sharma" <[email-masked]>
Date: Thu, 29 Apr 2004 01:01:02 -0700

Hi Dimitri,

Thanks for your thoughts.

However, as Fabio rightly observed, it is very critical that we
distinguish between characteristics that are intrinsic (and common)
to _all_ distributed path computation approaches from those that are
specific to the ARO approach.

The points you have mentioned below are inherent in _any_
distributed path computation paradigm (and indeed in any
distributed signaling/resource reservation paradigm), as I explain below,
and are therefore not drawbacks that arise due to particular
mechanisms/methods proposed in the ARO approach.

Comments in-line.

-Vishal

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On
> Behalf Of [email-masked]
> Sent: Monday, April 26, 2004 6:47 AM
> To: ugo monaco
> Cc: ccamp; Zafar Ali
> Subject: Re: Diverse path failure and optimality in
> draft-dachille-inter-area-path-protection
>
>
>

- First, if we are talking about IGP areas, the problem is a non-issue.

(They would be under the control
of a single provider, and the provider can reasonably be expected to
assign distinct, globally unique SRLGs to the links in different areas.)

- If we are talking about AS's, the problem is _universal_, and all
schemes related to restoration have to deal with it. In particular,
_any_ scheme that does distributed path computation has to deal with it.

So the question is unrelated to the ARO scheme, but a broader one
about how different providers assign SRLG's to resources.

This is actually a very important issue, but outside the scope of the
ARO document, and not one that I have seen any comprehensive approach to,
yet.

Perhaps others on the list (carriers?) can comment on it.

> use it if no other reservation are making use of these links)

As Fabio has very nicely explained in
his email,
http://ops.ietf.org/lists/ccamp/ccamp.2004/msg00553.html

resource contention is a fact of life (read unavoidable) in any distributed
scheme (unless you assume _instantaneous communication_ between the
distributed entities), and is prevalent in every distributed
protocol/mechanism from RSVP-TE to mechanisms for diverse path
computation and setup, such as PCE-based, XRO-based, and, of course,
ARO-based
schemes.

Not sure why you thought this is specific to the ARO proposal.

> step of the computation (otherwise the method wouldn't provide what it

First, not sure what "additional issues" you are referring to. Can you
provide specifics?

In any case, every path computation scheme (distributed or otherwise) has to
handle
the case where there are multiple entry points for the secondary (and
primary) paths at a given area/AS. Again, nothing surprising here or
specific
to the ARO scheme in particular.

When there are many entry points, any scheme has to have a way to select
only one (or some number of them), and any one of several criteria may be
used to make that selection.

Of course, one can consider then the relative merits of the different
ways of making that selection.

> > Please note that in response to this last question Fabio
> Ricciato listed
> > many

---

From: [email-masked]
Date: Thu, 29 Apr 2004 20:04:06 +0200

hi - see in-line

> You´re rising this problem with SRLGs spanning non-adjacent areas.

yes, because it's another flavour of the trap problem (the proposal 
solves the single area trap issue and not the multi-area one and it is 
not a criticism but a way to determine the exact coverage of the method)

> in lack of any exchange of info between computation points about srlg 

any signaling that carries srlg explicit information is rather 
impractical and i don't think there is currently another way to solve 
this issue (in a distributed way) other than performing lookups from the 
link_id's on locally available information bases

> Could you comment on that ?

see above - in brief is to know what the proposal can cover and does not 
cover and in the latter case whether it is capable to detect it

> In a successive phase,  the secondary LSP is reserved along the 

yes, it is a parallel multi-hop computation with a sequential signaling 
(i don't have any doubt about this)

> unsuccesful computation, which was also raised by others )

ok -

> limit, the probability of failing signaling due to a race should be 

at least this raises the issue of applicability (this will be greatly 
depending on the arrival time, the amount of unreserved bandwidth and 
the (diverse) connectivity degree of each abr)

> reservation is applied during the upstream RESV messages).

but it becomes more problematic since the computation has no control at
all over the "diverse segment" it has computed (at the end the issue is
to make the scheme working it imposes operational procedures) this does 
not mean that other mechanisms (existing and to come have full control)

> you´d like to provide some more concrete example.

if at each computation point the number of alternatives increases, i
have some difficulties to understand how this mechanism works, either
pruning of these alternatives is performed (so global optimality can
never be achieved) or you're going to maintain and extend them until
reaching the end-point (is that really feasible ?)

> to the parallel computation scheme, but rather common to any dstributed 

would it be possible to tell us instead which are the conditions in
which the scheme works rather than raising the flag of "non-specific to
the parallel computation scheme but common to any distributed scheme"
since afaik this scheme is also distributed

> beneficial to the discussion to clearly separate them in different 

there are issues intrisic to the method and issues that applies to 
distributed method that applies also to this method and i agree that 
the proposed method won't solve them all - but it is imho part of the 
discussion to exactly know what the method covers, can potentially cover 
and not cover (applicability) i.e. the worst situation is when you're 
not detecting false event -

thanks,
- dimitri.

---

From: [email-masked]
Date: Thu, 29 Apr 2004 20:37:29 +0200

hi,

> specific to the ARO approach.

i don't think i'm saying that the ARO approach should solve all the 
problems i'm just trying to see the problems that the ARO approach 
solves and to which extend/conditions

> mechanisms/methods proposed in the ARO approach.

once again, this is not the way these points were raised (they are not 
saying there are no problems with existing methods) but to which extend 
the proposed ARO approach enforce them (or avoid them)

as last philosophical word i'd like to point the following:
<ftp://ftp.rfc-editor.org/in-notes/rfc3439.txt>

it details several principles (but sure we've already cross some of the 
boundaries this document mentions) that can be useful in re-positioning 
the whole "optimization" debate

thanks,
- dimitri.
>>>i) Your question was about why we are trying for optimality
>>
>>with a joint
>>
>>>path selection scheme, when it is not possible, especially as
>>
>>the number
>>
>>>advantages of a joint computation (with ARO) of inter-area/AS
>>
>>paths in a
>>