Gabor,
Your analysis is right. It is a strong assumption to consider that all
links have the same metric, though.
You can get rid of that assumption if you consider PQ with directed
forwarding.
I had proved that in my thesis when I was young ;-)
biblio.info.ucl.ac.be/2007/457147.pdf (page 59)
Pierre.
On 6/1/12 11:32 AM, Gabor Retvari wrote:
On Friday, June 01, 2012 10:34:38 Gábor Sándor Enyedi wrote:
I conditionally support it. I think we need several further studies; e.g.
what are the RLFA friendly topologies, how can I improve my network to
keep up full coverage (and what extra cost that has), what is the
bidirectional coverage of RLFA (if path cannot be protected in either
directions, the route is not protected)
Just coincidentally, we have been doing some research on precisely these
questions for some time now. So far, we only have had preliminary results,
valid only for graphs with unit-costs.
Interestingly, we found that if the graph of the network (disregarding LANs,
SRLGs, etc. for now) is symmetric, 2-edge-connected, and each link is
set to the same administrative cost, then RLFA provides full coverage against
single link failures.
The argument goes on as follows:
- if some router 's' has an RLFA to the next-hop 'n' towards some destination
prefix 'd', then 's' has an RLFA to 'd' (with respect to the failure of
link '(s,n)');
- if a graph is 2-edge-connected, every edge is contained in at least one
ring, so '(s,n)' is also contained in a ring;
- consider the shortest ring amongst the rings that contain '(s,n)' and
suppose that the ring consists of even number of nodes: then, the same
reasoning as in the RLFA draft (draft-shand-remote-lfa-00, see Fig. 1) will
show that the intersection of the extended P-space of 's' and the Q-space
of 'n' is not empty;
- so 's' has an RLFA to the next-hop 'n', and so, by the first point, it has
an RLFA to any 'd' reachable through 'n';
- the same applies to the case when the shortest ring that contains '(s,n)'
is an odd-ring;
- since the above holds for any 's-d' pair, we conclude that we have full
RLFA coverage.
Our initial numerical studies seem to support the above claims, but please,
don't hesitate to correct me if I'm wrong.
The rest of our investigations are concerned with "unextended RLFA" (i.e.,
the one without the extended P-space option) to see whether we really need
this complexity in RLFA. We found that in 2-node-connected networks
"unextended RLFA" coverage can go down to 50%, and in the 2-edge-connected
case this can be as low as 33%, so the "extended" option is indeed important.
We have a rudimentary draft paper ready. If the need arises, we're happily
disclose it.
Gabor
_______________________________________________
rtgwg mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rtgwg
