RE: comments on ARO

["Vishal Sharma" <v.sharma@ieee.org>]

JP,

Thanks for the comments.

A comment and question in-line.

-Vishal

> -----Original Message-----
> From: Jean Philippe Vasseur [mailto:jvasseur@cisco.com]
> Sent: Thursday, April 29, 2004 10:27 AM
> To: v.sharma@ieee.org
> Cc: stefaan.de_cnodder@alcatel.be; ccamp@ops.ietf.org; Fabio Ricciato;
> Ugo Monaco; Alessio D'Achille; Marco Listanti
> Subject: RE: comments on ARO
>
<<snip>>

> > > > 1) Recording only border nodes:
> > > >
> > > > Actually, if one only recorded border nodes, then upon signaling
> > > > the secondary, the ingress border node for the secondary has no
> > > > idea about the intra-area (or intra-AS)  path of the primary (in its
> > > > own area or AS), and therefore cannot ensure that the primary and
> > > > secondary segments are in fact disjoint.
> > > >
> > > > This was a point I discussed with several other people
> > > > (who initially proposed the same thing), including
> > > > Arthi and Adrian, but we concluded, for the reason above,
> that merely
> > > > recording the border nodes does not work for diversity. As a
> > > > result, the ARO does, in fact, serve a very useful purpose.
> > > >
> > > > We can of course think more about what the trade-offs are, and
> > > see if there
> > > > is some way to retain the main advantage of the proposal (diversity,
> > > > joint optimization of both paths) while also recording less
> information.
> > > >
> > >
> > > The problem I want to solve here is NOT to reduce the amount of
> > > information in the ARO, i.e. my purpose is not to reduce its length.
> > > Rather, by only recording the border nodes you give more freedom
> > > when signaling the secondary (using the XRO!) meaning that when
> > > crankback or re-optimization of the secondary is possible, the
> > > primary does not have to be resignaled to get a new ARO.
> >
> >Sure, I understood that the goal wasn't to reduce the length of
> >the ARO per se, but rather the level of detail that would need to
> >be recorded in it (regardless of the actual amount of data the ARO
> >would carry).
> >
> >If you recollect the classification of path computation models
> >I gave in my email to JP
> >http://ops.ietf.org/lists/ccamp/ccamp.2004/msg00467.html
> >
> >we have under distributed computing: i) a parallel path computation
> >model and  ii) a sequential one.
> >ARO achieves the former, while XRO achieves the latter.
> >
> >So, if one did not compute and record the path of the secondary
> >jointly with the primary (and only recorded the border nodes instead)
> >the scheme would reduce to a _sequential path computation_, with its
> >attendant drawbacks (sub-optimality, trap topology, etc.).
> >
> >The beauty of the ARO scheme is that it can compute end-to-end
> >diverse paths using a parallel path computation model (albeit distributed
> >at each area/AS), with the simplicity of the  per-domain approach, and
> >without any changes to the signaling protocols.
>
> Here is one of main concerns that I have about this scheme: by contrast
> with a distributed PCE-approach, a severe drawback with such a model lies
> in the potential number of retrials (since it has to be combined with
> crankback) and consequently the potential set up time. Indeed,
> you may have
> diverse paths within a domain, and then a set up failure in the next hop
> domain requiring to crankback in the previous domain; the number of
> potential trials may be really non negligible.
>
> Moreover, you can still cannot guarantee and an end to end shortest path.

<snipped to end>

We have to think a bit more about the idea of combining ARO with
crankback and need to get back after giving it some thought.

[Please note that the goal with ARO is not necessarily to guarantee
an end-to-end shortest path. Rather, it is to ensure that diverse
paths can be efficiently computed, while meeting certain constraints
per some metrics (as further explained in Fabio's email
http://ops.ietf.org/lists/ccamp/ccamp.2004/msg00562.html
and my recent reply to Stefaan
http://ops.ietf.org/lists/ccamp/ccamp.2004/msg00561.html)]


Reading draft-vasseur-ccamp-inter-area-as, especially Sec. 6.6
I was a bit unclear on how the computation proceeds.
(BTW, the draft will read much better if the generic steps are
explained first, and then the worked example. As it stands, the
two are intermixed, and it becomes much more difficult to understand
what the algo. is.)

The draft states that
"the PCE provides the list of shortest paths (with their corresponding
ERO (potentially partial ERO) + Path-cost) from _every_ ASBR to the
inter-AS TE LSP destination."

Suppose the destination is in ASn. PCEn computes a set of shortest paths
from _every_ ASBR in ASn to the destination, and passes them back to PCn-1.

What does PCn-1 do?

My understanding from the draft is that it computes a set of
shortest paths between all ASBRs that
connect ASn-1 to ASn-2 and those that connect ASn-1 to ASn, and
includes the inter-AS links between ASn-1 and ASn in those
shortest path computations.

My question is: what does PCn-1 send back to PCn-2?

Does it, in turn, send PCn-2 the set of all possible paths traversing
ASn-1 and ASn or does it concatenate all paths, choose the shortest
one, and send back one (the shortest path traversing ASn-1 and ASn)?

If the former, then we have a major scalability issue, as the
number of paths passed back to successive PCi's will grow,
literally exponentially, from AS to AS.

If the latter, the scheme may fail to select the shortest path,
as I explain below (which is not unexpected).

Take the following fig. from the draft (where I have added a link
between ASBR3 and ASBR5):


     <-- AS 1 ---> <------- AS 2 -----><--- AS 3 ---->

               <---BGP--->            <---BGP-->
CE1---R0---X1-ASBR1-----ASBR4--R3---ASBR7----ASBR9----R6
      |\     \ |       / |   / |   / |          |      |
      | \     ASBR2---/ ASBR5  | --  |          |      |
      |  \     |  /----/ |     |/    |          |      |
      R1-R2---ASBR3-----ASBR6--R4---ASBR8----ASBR10----R7---CE2


We will use the mechanisms specified in Sec. 6 of draft-vasseur, and
assume for this part of the discussion that the objective is to the
shortest path between R0 and R7.

As before, ASBR1, ASBR4, and ASBR9 are the PCEs for AS's 1, 2, and
3, respectively.

The request propagates from R0 to the PCE's, to ASBR1 on to ASBR4 on
to ASBR9, as before.

1. ASBR9 computes two paths:

ASBR9-R6-R7 Cost = 10, say
ASBR10-R7   Cost = 20, say (per some metric)

2. It passes these back to ASBR4, which in turn calculates that the
possibilities
to traverse AS2 are:

ASBR4-R3-ASBR7-ASBR9, Cost = 30
ASBR5-R3-ASBR7-ASBR9, Cost = 40
ASBR6-R4-ASBR8-ASBR10, Cost = 30
(Assume all other permutations have higher cost.)

3. Using the concatenation approach mentioned in the draft, it computes
that the shortest paths traversing ASs 2 and 3 is, therefore,

ASBR4-R3-ASBR7 -- ASBR9-R6-R7, total cost = 40

4. It passes this back to ASBR1, which in turn calculates that the
possibilities
to traverse AS1 to reach ASBR4 are:

R0-X1-ASBR1-ASBR4, Cost = 50
R0-X1-ASBR2-ASBR4, Cost = 60
(There are other permutations, but assume their cost is higher.)

Also, assume that the path from R01 to ASBR5,
R0-R2-ASBR3-ASBR5 has cost = 30.

5. Again, using concatenation, ASBR1 calculates that the "shortest
path" is

R0-X1-ASBR1 -- ASBR4-R3-ASBR7 -- ASBR9-R6-R7, total cost = 90
<--------------->   <------------->  <----->
       50                 30            10

However, there was a shorter path
R0-R2-ASBR3 -- ASBR5-R3-ASBR7 -- ASBR9-R6-R7, total cost = 80
<-------------->  <-------------->   <----->
       30                40             10

which could not get picked in this case.

For this, it would have to be that all possible paths are propagated
back to PC1, which then selects the shortest one among them, but
this, it seems to me, would be an operational and computational nightmare.