Actually, I'm not really surprised about the 100% coverage. But that is true only for link failures and uniform link costs, right? Isn't that possible to extend this reasoning to non-uniform link costs to find out what rings are not useable in that case? Moreover, can't we extend the same reasoning for node failures? There is simmilar cycle for s and its next-next-hop, when the network is 2-connected...
Gabor -----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Gabor Retvari Sent: Friday, June 01, 2012 11:33 AM To: [email protected]; Alia Atlas Cc: Levente Csikor Subject: Re: opinions on adoption of draft-shand-remote-lfa as a WG draft 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 -- Gábor Rétvári, Ph.D. Research Fellow, BME-TMIT Phone: +36-1-463-1060 Fax: +36-1-463-1763 _______________________________________________ rtgwg mailing list [email protected] https://www.ietf.org/mailman/listinfo/rtgwg _______________________________________________ rtgwg mailing list [email protected] https://www.ietf.org/mailman/listinfo/rtgwg
