RE: comments on ARO

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

JP,

Thanks for clarifying. Questions in-line.

-Vishal

> -----Original Message-----
> From: owner-ccamp@ops.ietf.org [mailto:owner-ccamp@ops.ietf.org]On
> Behalf Of Jean Philippe Vasseur
> Sent: Friday, April 30, 2004 5:36 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
>
>
<<big snip>>

> > >
> > > 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.
>
> Yes I noticed that ;-) hence my comment that it cannot guarantee the
> 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)]
>
> But my main concern remains: the number of required crankback required in
> some cases and the related impact on set up failure.
>
> >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.
>
> What you described is not how the algorithm works ... All the shortest
> paths from the destination to every entry ASBR are computed in a backward
> and recursive manner (hence you progressively compute the SPT
> rooted at the
> LSP destination). Note that there are several variations and
> optimizations,
> I just described the general case that applies to the generic case of N
> ASes. I'll try to clarify in the next revision of the draft.


In that case, I feel a much clearer exposition is needed in Sec. 6.6.
I had read it several times, but it wasn't clear that the algo.
works as described above.
(BTW, I will now think about things in the light of what you clarified,
and get back with any questions.)

In the meantime, I have few quick questions ...

-- Who decides on the initial AS path (and consequently
the sequence of distributed PCEs) that the request should traverse?
(Since there could be multiple paths to get from the source (and its
AS) to the destination (and its AS).)

There is a phrase at the start of Sec. 6.6, which says
"In the case of inter-AS TE, the PCE must
be able to serve the source AS and can compute inter-AS TE LSP path
terminating in the destination ASn."

So, is the first PCE assumed to make that selection of AS's?

-- On what criteria is this decision based?

-- Also, if the SPT rooted at the destination is the one being computed,
why does the text show "trees" rooted at ASBR4 and ASBR1, respectively?
Instead (or in addition), it should show an example of what the final
SPT, rooted at R7, looks like.

-- And, why do the two "SPT's" illustrated have loops?

-- Also, at one point (after the fig. for the "SPT" rooted at ASBR4) the
text says
"The cost of the ASBR-ASBR link between ASBR of different ASes is also
known by the PCEi (see section 6.2)."

I assume this means the cost of ASBR-ASBR links that connect the current
AS to its neighboring AS's?

-- And is 6.2 the intended section being referred to? Since 6.2 merely
has a paragraph explaining what a PCE is.