About optimality of inter-AS parallel computation in draft-dachille-inter-area-path-protection

[ricciato <ricciato@coritel.it>]

Dear ccampers, Dimitri,

we were reported by Vishal several comments collected at Seoul regarding 
draft-dachille, proposing the parallel computation (or 
joint-computation)  approach with ARO for diverse path-pair computation.

After several internal discussions and thoughts, we are now going to 
react to these, as anticipated in the recent mail by  Vishal.

Among other comments there was one issued by Dimitri.
If I correctly understood, his point was the following: the joint 
computation (with ARO) is guaranteed to *achieve* the global optimum 
only in the trivial case of a single AS, but not along a path with 
multiple AS. This is indeed due to the distributed nature of the route 
selection process, that can optimize local route segments, but can not 
generally achieve the *global* optimum (in fact, distributed 
optimization would need an iterative process to converge to global 
optimum, which is not the case here). Now, the Dimitri point was: why 
prefer the joint computation (with ARO)  to sequential computation (with 
XRO), since neither of the two in general achieve the global optimum ?


This is a good question and gives me the opportunity to make some more 
general considerations about the ARO approach scketched in the draft.

1. If you consider the classical problem (i.e., find two disjoint paths 
with the objective of minimizing some link metric) despite 
joint-computation does not reach the global optimum, it definitely 
improves the quality of the solution w.r.t. sequential-computation. The 
exact gain depends on the particular topology, and there are of course 
cases in which it can be zero (see note 1).

2. An additional benefit of joint- (or "parallel-") vs. 
sequential-computation is robusteness against trap-topologies (ref. to 
draft-dachille)

3. The joint-computation with ARO can be applied to a vast class of 
problems dealing with path-pair computation. I'm giving below some few 
examples.
(I think this also adrresses some comment by Jean-Louis). In general, in 
each problem of path-pair computation one can distinguish the 
constraint(s) from the optimization objective:

Case-I: find a pair of disjoint paths (i.e., disjointedness is a 
constraint)  wich minimize some link metric (hop-length, link-load, etc.)
Case-II: find a pair of maximally disjoint paths (disjointedness becomes 
an objective)
Case-III: find a pair of disjoint paths P1 and P2 that minimizes the 
difference |d(P1)-d(P2)|, where d() is some metric associated to the 
path (e.g., delay....might make sense in optical networks ??).
Case-IV: Assuming that for each link pair (i,j) it is possible to assign 
a "correlation" factor r(i,j) accounting for the probability of 
contemporary failures, find a pair of paths that minimizes the 
max{r(i,j)} over all pairs such that i is in P1 and j is in P2 [see note 2].

Maybe not all the above items are of practical interest in real 
applications, but the fact that our approach encompasses all of  them 
proves the flexibility and usefulness of joint-computation with ARO. 
Several other problems can be found.
In general, joint-selection with ARO can address to all problems 
presenting some *joint constraints* and/or *joint optimization 
objective* on the pair of paths.

Needless to say, each such case requires ad-hoc route-selection 
_algorithms_ to be implemented in the ingress border nodes (or in a 
centralized server within each AS), but all can be accommodated with the 
signaling procedure based on ARO.

Admittedly, the current draft version exclusively focused on case-I, and 
fails to make it clear that the set of possible applications is far 
broader. We will improve this point in the future version. Incidentally, 
I notice here that this is indeed the reason why we proposed the (quite 
neutral) term "Associated Route Object" instead of the more specific 
"Disjoint R.O." or "Backup R.O." etc.: we wanted to leave it open to a 
broad set of possible applications.

Maybe it would make sense to add some additional semantic in the PATH 
messages that specify the contraint(s) and/or the objectives to which 
the primary (in the ERO) and secondary (in the ARO) paths should 
(jointly!) comform.
This might be an associated sub-object of the ARO, perhaps ?
Might be named "Route Pair Requirements" (RPR) ?
In other words, the overall semantic in the PATH messages should sound like:
"compute a primary route segment (in the ERO), and an associated 
secondary route segment (in the ARO), such that they are subject to the 
contraint(s) X and optimize objective Y (X,Y are contained somehow in 
the RPR)".

The ERO+ARO+RPR scheme, in the framework of distributed *joint* route 
selection, would be really a quite flexible and general scheme.

What do you think about that ?


Looking forwards to get more comments,
best regards

Fabio Ricciato



Note 1: Having available some guidelines about realistic inter- and 
intra-AS topologies, we would be available to run extensive simulations 
to assess this gain in realistic case. Is there anyone interested in 
this activity ?

Note 2: In general 0<=r(i,j)<=1. This is a "fuzzy" extension of the SRLG 
concept. In fact, a SLRG can be defined as a set of links S having 
r(i,j)=1 for each i,j in S.