Subject: Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some comments and questions

From: Levente Csikor <[email-masked]>
Date: Thu, 01 Aug 2013 16:10:50 +0200

Dear All,
since our previous works in remote LFA analysis (papers already sent to 
these mailing lists) assumed unit cost networks, therefore as I 
promised, I calculated the corresponding LFA and rLFA coverages in those 
networks with their original link costs.
These networks were inferred from Rocketfuel dataset (/Mahajan, R., 
Spring, N., Wetherall, D., Anderson, T.://
//Inferring link weights using end-to-end measurements. In: ACM IMC, pp. 
231–236 (2002)/), SNDLib (http://sndlib.zib.de), and 
TopologyZoo(http://www.topology-zoo.org). The found coverages and some 
details are found in the table below, where /n/ and /m/ denote the 
number of nodes and the number of links, respectively. The other columns 
mark the different coverages obrtained by simple LFA and remote LFA, 
where LP indicates the link-protecting case, while NP notes the case of 
node protection.
Topologies marked with an asterisk(*) did not have inferred real link 
costs from the datasets, so their costs were initially set to 1 (unit 
costs).

I believe that these results computed on real-world networks could 
significantly improve the rlfa draft, especially Sec. 9.3., and the 
advantages of remote LFA over simple LFA would be more emphasized.

+==============+====+====+==========+===========+============+============+
| Topology     | n  | m  | LFA_LP   | LFA_NP    |  rLFA_LP   | rLFA_NP   |
+==============+====+====+==========+===========+============+============+
| AS1221       | 7  | 9  | 0.809    | 0.25    |   0.809    |    0.25    |
+--------------+----+----+----------+-----------+------------+------------+
| AS1239       | 30 | 69 | 0.8735   | 0.7554 |     1      |   0.9795   |
+--------------+----+----+----------+-----------+------------+------------+
| AS1755       | 18 | 33 | 0.8725   |  0.7741   |   0.9967   |   0.9959   |
+--------------+----+----+----------+-----------+------------+------------+
| AS3257       | 27 | 64 | 0.923    |  0.7186   |   0.99     |   0.8472   |
+--------------+----+----+----------+-----------+------------+------------+
| AS3967       | 21 | 36 | 0.7857   |  0.6460   |     1      |   0.9325   |
+--------------+----+----+----------+-----------+------------+------------+
| AS6461       | 17 | 37 | 0.9338   |  0.6933   |   0.9963   |   0.7075   |
+--------------+----+----+----------+-----------+------------+------------+
| Abilene*     | 12 | 15 | 0.5606   |  0.6078   |   0.9090   |   0.8725   |
+--------------+----+----+----------+-----------+------------+------------+
| Arnes*       | 41 | 57 | 0.6225   |  0.3518   |   0.7487   |   0.4562   |
+--------------+----+----+----------+-----------+------------+------------+
| AT&T         | 22 | 38 | 0.8225   |  0.5647   |     1      |   0.8497   |
+--------------+----+----+----------+-----------+------------+------------+
| Deltacom     | 113| 161| 0.5771   |  0.4910   |   0.8539   |   0.8148   |
+--------------+----+----+----------+-----------+------------+------------+
| Gambia       | 28 | 28 | 0.037    |   0.04    |   0.1851   |     0.12   |
+--------------+----+----+----------+-----------+------------+------------+
| Geant        | 37 | 55 | 0.6906   |  0.3977   |   0.8303   |   0.6582   |
+--------------+----+----+----------+-----------+------------+------------+
| Germ_50      | 50 | 88 | 0.9004   |  0.8381   |     1      |   0.9995   |
+--------------+----+----+----------+-----------+------------+------------+
| Germany*     | 27 | 32 | 0.6948   |  0.599    |     1      |   0.9549   |
+--------------+----+----+----------+-----------+------------+------------+
| InternetMCI  | 19 | 33 | 0.9035   |  0.6798   |   0.9415   |   0.9136   |
+--------------+----+----+----------+-----------+------------+------------+
| Italy*       | 33 | 56 | 0.784    |  0.5741   |     1      |   0.9269   |
+--------------+----+----+----------+-----------+------------+------------+
| NSF*         | 26 | 43 | 0.86     |  0.6347   |     1      |     1      |
+--------------+----+----+----------+-----------+------------+------------+

Furthermore, after reading the draft again-and-again, I have found that 
it should be more emphasized in the draft that calculating or seeking 
for a remote LFA staging point should be done IF AND ONLY IF no simple 
LFA were found. This is important, since normally people obviously think 
and observe that the failure coverage of remote LFA should be greater 
than or equal to the coverage obtained by simple LFA. Moreover, people 
also think that LFAs produce a subset of remote LFAs. However, if after 
a failure only P-spaces and Q-spaces are taken into account in order to 
seek a (remote) loop-free alternate, then it is possible that a simple 
LFA would not be found resulting unprotected node-pairs. But, this case 
could only happen when link costs are not unit costs. For an easier 
understanding, consider the network depicted below:
          1             1
F--------S-----------X--------E
\ /         \
      10 \    / 4         \  1
      \  /       1             \
N ---------------------------C
|    |
        1  | |  1
           | |
           | 1            1 |
A--------------B-------------D

Assume that S wishes to send a packet to D, and the shortest path goes 
through E, therefore it is S-E-C-D. Suppose that the link (s,e)
fails, or even the node e itself fails. In this case, since LFA (and its 
calculation) only consider all other neighbors of s, then node N would 
be an easy LFA for this failure, since dist(N,D) < dist(N,S)+dist(S,D).
However, if we only seek possible remote LFAs, than according to the 
(r)SPF calculations, or taking into account our distance-function 
conditions will result that D's Q-space will contain node N (besides 
some other nodes), but S's P-space won't (it will only contain node F 
and what is more, if node F does not exist, then S's P-space would be 
empty), therefore no intersection of the two spaces will exist, leaving 
this network vulnerable to the failure of link (s,e).

This results that a neighbor should be always reached by the neighboring 
link, even if there exists a shorter, but definitely bigger in hop-count 
path to it.
According to this case (when seeking simple LFA is missed), the 
condition of extended P-space described by our distance functions, 
should be modified a bit:
For source /s/, destination /d/, and next-hop /e/, some node /n != s,d/ 
is an extended link-protecting remote LFA for the /s-d/ pair if and only if
/∃v ∈ neigh(s) : dist(v, n) < dist(v, s) + dist(s, e) + dist(e, n)//*&& 
dist(s,v) < dist(s,e) + dist(e**,v)*/**
/dist(n, d) < dist(n, s) + dist(s, d) . /

One can easily observe that emphasizing more that remote LFA seeking 
process is only "executed" after no simple LFA is found could much more 
ease the understanding and won't result a headache to the reader who 
accidentally wants to calculate rLFA coverage in such network.

Please let me know, if my interpretation is not correct.
Thanks.

Best,
Levente

On 07/02/2013 07:07 PM, Stewart Bryant wrote:
> On 26/06/2013 14:13, Levente Csikor wrote:
>
> Levente
>
> In each case below the conditions are surely fulfilled if n=e
> thus I think that in each case the condition needs to be
> changed to :
>
> some node n!={s or e}
>> In order to not to read our full papers and searching the answers, I 
>> copied here the relevant parts:
>> *Link-protecting rLFA condition:*
>> For source /s/, destination /d/, and next-hop /e/, some node /n/ /!= 
>> s,d/ is a link-protecting remote LFA for the /s-d/ pair  if and only if
>> /dist(s, n) < dist(s, e) + dist(e, n)/  (1)
>> /dist(n, d) < dist(n, s) + dist(s, d)/  (2)
>> In these equations, one can easily see, that (1) defines the P-space, 
>> while (2) is the condition of Q-space. Furthermore, with these 
>> formalized conditions, one can easily observe, that (2) is actually 
>> the basic loop-free criterion of pure LFA.
>>
>> *Link-protecting rLFA condition with extended P-space:*
>> For source /s/, destination /d/, and next-hop /e/, some node /n != 
>> s,d/ is an extended link-protecting remote LFA for the /s-d/ pair if 
>> and only if
>> /∃v ∈ neigh(s) : dist(v, n) < dist(v, s) + dist(s, e) + dist(e, n)///
>> /dist(n, d) < dist(n, s) + dist(s, d) . /
>>
>> *Node-protecting rLFA condition:*
>> For source /s/, destination /d/, and next-hop /e/, some /n != s,d/ is 
>> a node-protecting remote LFA for the /s-d/ pair if and only if
>> /dist(s,n) < dist(s,e) + dist(e,n)///     (3)
>> /dist(n,d) < dist(n,e) + dist(e,d) /    (4)
>> As it was in the case of link protection, here, (3) defines the 
>> P-space, while (4) characterize the Q-space.
>> Here, two important observations can be made, which are the followings:
>>  - P-space does not depend on the protection scheme (i.e., link or 
>> node protection)
> SB> That falls directly out of the definition of P-space
> SB> since in link you cannot traverse the link to e and in
> SB> node only get to e if you traverse the link to e
> SB> thus the exclusion of the link to e applies in both cases
>>  - (4) again is the basic node-protecting loop-free criterion of pure 
>> LFA.
>>
>> *Node-protecting rLFA condition with extended P-space:*
>> For source /s/, destination /d/, and next-hop /e/, some node /n != 
>> s,d/ is an extended node-protecting remote LFA for the /s-d/ pair if 
>> and only if
>> /∃v ∈ neigh(s) : dist(v, n) < dist(v, e) + dist(e, n)/
>> /dist(n, d) < dist(n, e) + dist(e, d) ./
>>
>> Despite the fact that we only considered unit cost networks, the 
>> formal definitions above are *true for any arbitrary weighted network.*
> SB> I do not see where the unit costs come into the text above. It looks
> SB> like it is already expressed in terms of arbitrary cost.
>
> SB> Additionally in order to limit the number of SPFs to a practical
> SB> level, we normally suggest that the repair target in not d, but
> SB> instead is e (in the link case) or next hop of e (node case).
>
> SB> Anyway I will work on some text.
>
> - Stewart

---

From: Levente Csikor <[email-masked]>
Date: Fri, 02 Aug 2013 08:24:59 +0200

Dear All,
I'm sending my previous mail again since the font for the ASCII art 
network was not fixed and may not appear in a right format at everyone.

If it still messy, let me know.

Sorry,
Levente

Dear All,
231--236 (2002)/), SNDLib (http://sndlib.zib.de), and 

/?v ? neigh(s) : dist(v, n) < dist(v, s) + dist(s, e) + dist(e, n)//*&& 
dist(s,v) < dist(s,e) + dist(e**,v)*/

Best,
Levente

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Fri, 2 Aug 2013 07:59:03 +0000

Are these the single or the bidirectional coverage results?

Gabor

From: [email-masked] [mailto:[email-masked]] On Behalf Of Levente Csikor
Sent: Friday, August 02, 2013 8:25 AM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some comments and questions

Dear All,
I'm sending my previous mail again since the font for the ASCII art network was not fixed and may not appear in a right format at everyone.

Sorry,
Levente

Dear All,
since our previous works in remote LFA analysis (papers already sent to these mailing lists) assumed unit cost networks, therefore as I promised, I calculated the corresponding LFA and rLFA coverages in those networks with their original link costs.
These networks were inferred from Rocketfuel dataset (Mahajan, R., Spring, N., Wetherall, D., Anderson, T.:
Inferring link weights using end-to-end measurements. In: ACM IMC, pp. 231–236 (2002)), SNDLib (http://sndlib.zib.de), and TopologyZoo(http://www.topology-zoo.org). The found coverages and some details are found in the table below, where n and m denote the number of nodes and the number of links, respectively. The other columns mark the different coverages obrtained by simple LFA and remote LFA, where LP indicates the link-protecting case, while NP notes the case of node protection.
Topologies marked with an asterisk(*) did not have inferred real link costs from the datasets, so their costs were initially set to 1 (unit costs).

I believe that these results computed on real-world networks could significantly improve the rlfa draft, especially Sec. 9.3., and the advantages of remote LFA over simple LFA would be more emphasized.

Furthermore, after reading the draft again-and-again, I have found that it should be more emphasized in the draft that calculating or seeking for a remote LFA staging point should be done IF AND ONLY IF no simple LFA were found. This is important, since normally people obviously think and observe that the failure coverage of remote LFA should be greater than or equal to the coverage obtained by simple LFA. Moreover, people also think that LFAs produce a subset of remote LFAs. However, if after a failure only P-spaces and Q-spaces are taken into account in order to seek a (remote) loop-free alternate, then it is possible that a simple LFA would not be found resulting unprotected node-pairs. But, this case could only happen when link costs are not unit costs. For an easier understanding, consider the network depicted below:
            1              1
          F--------S-----------X--------E
           \      /                      \
         10 \    / 4                      \  1
             \  /        1                 \
              N ---------------------------C
              |                            |
           1  |                            |  1
              |                            |
              |      1             1       |
              A--------------B-------------D

Assume that S wishes to send a packet to D, and the shortest path goes through E, therefore it is S-E-C-D. Suppose that the link (s,e)
fails, or even the node e itself fails. In this case, since LFA (and its calculation) only consider all other neighbors of s, then node N would be an easy LFA for this failure, since dist(N,D) < dist(N,S)+dist(S,D).
However, if we only seek possible remote LFAs, than according to the (r)SPF calculations, or taking into account our distance-function conditions will result that D's Q-space will contain node N (besides some other nodes), but S's P-space won't (it will only contain node F and what is more, if node F does not exist, then S's P-space would be empty), therefore no intersection of the two spaces will exist, leaving this network vulnerable to the failure of link (s,e).

This results that a neighbor should be always reached by the neighboring link, even if there exists a shorter, but definitely bigger in hop-count path to it.
According to this case (when seeking simple LFA is missed), the condition of extended P-space described by our distance functions, should be modified a bit:
For source s, destination d, and next-hop e, some node n != s,d is an extended link-protecting remote LFA for the s-d pair if and only if
∃v ∈ neigh(s) : dist(v, n) < dist(v, s) + dist(s, e) + dist(e, n)  && dist(s,v) < dist(s,e) + dist(e,v)
dist(n, d) < dist(n, s) + dist(s, d) .

One can easily observe that emphasizing more that remote LFA seeking process is only "executed" after no simple LFA is found could much more ease the understanding and won't result a headache to the reader who accidentally wants to calculate rLFA coverage in such network.

Best,
Levente

---

From: Levente Csikor <[email-masked]>
Date: Fri, 02 Aug 2013 10:01:02 +0200

These are bidirectionalresults.

Levente

On 08/02/2013 09:59 AM, Gábor Sándor Enyedi wrote:
> *From:[email-masked] [mailto:[email-masked]] *On 
> Behalf Of *Levente Csikor
> *Sent:* Friday, August 02, 2013 8:25 AM
> *To:* [email-masked]
> *Cc:* [email-masked]; 
> [email-masked]; [email-masked]
> *Subject:* Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some 
> comments and questions
>
> Dear All,
> since our previous works in remote LFA analysis (papers already sent 
> to these mailing lists) assumed unit cost networks, therefore as I 
> promised, I calculated the corresponding LFA and rLFA coverages in 
> those networks with their original link costs.
> Spring, N., Wetherall, D., Anderson, T.:
> Inferring link weights using end-to-end measurements. In: ACM IMC, pp. 
> number of nodes and the number of links, respectively. The other 
> columns mark the different coverages obrtained by simple LFA and 
> remote LFA, where LP indicates the link-protecting case, while NP 
> notes the case of node protection.
> Furthermore, after reading the draft again-and-again, I have found 
> that it should be more emphasized in the draft that calculating or 
> seeking for a remote LFA staging point should be done IF AND ONLY IF 
> no simple LFA were found. This is important, since normally people 
> obviously think and observe that the failure coverage of remote LFA 
> should be greater than or equal to the coverage obtained by simple 
> LFA. Moreover, people also think that LFAs produce a subset of remote 
> LFAs. However, if after a failure only P-spaces and Q-spaces are taken 
> into account in order to seek a (remote) loop-free alternate, then it 
> is possible that a simple LFA would not be found resulting unprotected 
> node-pairs. But, this case could only happen when link costs are not 
> unit costs. For an easier understanding, consider the network depicted 
> below:
>             1 1
> fails, or even the node e itself fails. In this case, since LFA (and 
> its calculation) only consider all other neighbors of s, then node N 
> would be an easy LFA for this failure, since dist(N,D) < 
> dist(N,S)+dist(S,D).
> empty), therefore no intersection of the two spaces will exist, 
> leaving this network vulnerable to the failure of link (s,e).
>
> This results that a neighbor should be always reached by the 
> neighboring link, even if there exists a shorter, but definitely 
> bigger in hop-count path to it.
> /∃//v //∈//neigh(s) : dist(v, n) < dist(v, s) + dist(s, e) + dist(e, 
> n) *&& dist(s,v) < dist(s,e) + dist(e,v)*/
> process is only "executed" after no simple LFA is found could much 
> more ease the understanding and won't result a headache to the reader 
> who accidentally wants to calculate rLFA coverage in such network.
>

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Fri, 2 Aug 2013 08:10:29 +0000

Nice. However, I’m a bit confused, because topologies with uniform link costs should have 100% link failure coverage (if they are 2-connected), shouldn’t they? Isn’t Abilene and Arnes 2-connected?

Other: did you noticed that with some minimal extra computation, it is possible to reach 100% node protection with rLFA, if we suppose that all the nodes do rLFA in the network. Maybe we could assign a single extra label/IP address to say that “use uniform link costs for this packet”, and get something quite similar to MRT? :)

Gabor

From: Levente Csikor [mailto:[email-masked]]
Sent: Friday, August 02, 2013 10:01 AM
To: Gábor Sándor Enyedi
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some comments and questions

These are bidirectional results.

Levente

Gabor

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]] On Behalf Of Levente Csikor
Sent: Friday, August 02, 2013 8:25 AM
To: [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some comments and questions

Dear All,

Sorry,
Levente

Dear All,

Best,
Levente

---

From: <[email-masked]>
Date: Fri, 2 Aug 2013 10:13:38 +0200

Hi,

Correct me if I don't understand correctly what you meant.

 "I have found that it should be more emphasized in the draft that calculating or seeking for a remote LFA staging point should be done IF AND ONLY IF no simple LFA were found."

This is how the draft is written today :

§3.1 :
"If there
   is no such LFA neighbor, then S may be able to create a virtual LFA
   by using a tunnel to carry the packet to a point in the network which
   is not a direct neighbor of S from which the packet will be delivered
   to the destination without looping back to S."

§4.1 :
"Not all links will require protection using a tunneled repair path.
   Referring to Figure 1, if E can already be protected via an LFA, S-E
   does not need to be protected using a repair tunnel, since all
   destinations normally reachable through E must therefore also be
   protectable by an LFA. "

The draft also precise that extended P-Space must be used :
"9.1<http://tools.ietf.org/html/draft-ietf-rtgwg-remote-lfa-02#section-9.1>.  Simplicity

   The remote LFA algorithm is simple to compute.

   o  The extended P space does not require any new computation (it is
      known once per-prefix LFA computation is completed).
"

In your example, N is part of extended P-Space. So N would be a PQ (it's a normal LFA also as you stated).

My comment :
- Yes, extended P-Space usage is mandatory in order to maximize coverage (for me it's clearly explained in the draft)

- draft currently states that remote LFA would be computed only when normal LFA is not available BUT this is not a good idea. Based on the use case we are presenting if draft-ietf-rtgwg-lfa-manageability, there is a strong interrest in always computing rLFA protection then be able to compare attributes of PQs and normal LFAs to determine which one is the more efficient based on service provider requirements. This does not mean that we don't use extended P Space, extended P-Space need always to be used.

- You are providing NP coverage for rLFA , thanks for the info, but I just want to highlight that this is just "informational" as a router is not able to determine that the PQ is providing NP or not for the specific destination. Determining such PQ attribute would require extra SPF, as stated in draft-psarkar-rtgwg-rlfa-node-protection-00<http://www.google.fr/url?q=https://datatracker.ietf.org/doc/draft-psarkar-rtgwg-rlfa-node-protection/&sa=U&ei=zWn7UcyGGMTcOo3agcgM&ved=0CB4QFjAA&usg=AFQjCNE10vQJ-5GomSFsDkPVW6mXz0wzRQ>.

Best Regards,

Stephane

________________________________
De : [email-masked] [mailto:[email-masked]] De la part de Levente Csikor
Envoyé : jeudi 1 août 2013 16:11
À : [email-masked]
Cc : [email-masked]; [email-masked]; [email-masked]
Objet : Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some comments and questions

Dear All,

Best,
Levente

Levente

some node n!={s or e}
In order to not to read our full papers and searching the answers, I copied here the relevant parts:
Link-protecting rLFA condition:
For source s, destination d, and next-hop e, some node n != s,d is a link-protecting remote LFA for the s-d pair  if and only if
  dist(s, n) < dist(s, e) + dist(e, n)  (1)
  dist(n, d) < dist(n, s) + dist(s, d)  (2)
In these equations, one can easily see, that (1) defines the P-space, while (2) is the condition of Q-space. Furthermore, with these formalized conditions, one can easily observe, that (2) is actually the basic loop-free criterion of pure LFA.

Link-protecting rLFA condition with extended P-space:
For source s, destination d, and next-hop e, some node n != s,d is an extended link-protecting remote LFA for the s-d pair if and only if
∃v ∈ neigh(s) : dist(v, n) < dist(v, s) + dist(s, e) + dist(e, n)
dist(n, d) < dist(n, s) + dist(s, d) .

Node-protecting rLFA condition:
For source s, destination d, and next-hop e, some n != s,d is a node-protecting remote LFA for the s-d pair if and only if
dist(s,n) < dist(s,e) + dist(e,n)      (3)
dist(n,d) < dist(n,e) + dist(e,d)     (4)
As it was in the case of link protection, here, (3) defines the P-space, while (4) characterize the Q-space.
Here, two important observations can be made, which are the followings:
 - P-space does not depend on the protection scheme (i.e., link or node protection)
SB> That falls directly out of the definition of P-space
SB> since in link you cannot traverse the link to e and in
SB> node only get to e if you traverse the link to e
SB> thus the exclusion of the link to e applies in both cases
 - (4) again is the basic node-protecting loop-free criterion of pure LFA.

Node-protecting rLFA condition with extended P-space:
For source s, destination d, and next-hop e, some node n != s,d is an extended node-protecting remote LFA for the s-d pair if and only if
∃v ∈ neigh(s) : dist(v, n) < dist(v, e) + dist(e, n)
dist(n, d) < dist(n, e) + dist(e, d) .

Despite the fact that we only considered unit cost networks, the formal definitions above are true for any arbitrary weighted network.
SB> I do not see where the unit costs come into the text above. It looks
SB> like it is already expressed in terms of arbitrary cost.

- Stewart

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.

---

From: Levente Csikor <[email-masked]>
Date: Fri, 02 Aug 2013 10:26:43 +0200

See comments inline.

On 08/02/2013 10:10 AM, Gábor Sándor Enyedi wrote:
>
> Nice. However, I’m a bit confused, because topologies with uniform 
> link costs should have 100% link failure coverage (if they are 
> 2-connected), shouldn’t they? Isn’t Abilene and Arnes 2-connected?
>
Yepp, they are not 2-connected
Abilene: 
http://www.ots.utsystem.edu/pubs/internet2/graphics/abilenebackbone.gif
Arnes: http://www.xipi.eu/InfinityImages/images/2263/arnes.png

> Other: did you noticed that with some minimal extra computation,
>
> it is possible to reach 100% node protection with rLFA, if we suppose 
> that all the nodes do rLFA in the network.
>
I'm a  bit confused:  why do we suppose that not all nodes do rLFA?

> Maybe we could assign a single extra label/IP address to say that “use 
> uniform link costs for this packet”, and get something quite similar 
> to MRT? :)
>
> Gabor
>
> *From:*Levente Csikor [mailto:[email-masked]]
> *Sent:* Friday, August 02, 2013 10:01 AM
> *To:* Gábor Sándor Enyedi
> *Cc:* [email-masked]; [email-masked]; 
>     *From:[email-masked] <mailto:[email-masked]>
>     [mailto:[email-masked]] *On Behalf Of *Levente Csikor
>     *To:* [email-masked] <mailto:[email-masked]>
>     *Cc:* [email-masked]
>     <mailto:[email-masked]>;
>     [email-masked] <mailto:[email-masked]>;
>     [email-masked] <mailto:[email-masked]>
>     *Subject:* Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? -
>     some comments and questions
>
>     Dear All,
>     I'm sending my previous mail again since the font for the ASCII
>     art network was not fixed and may not appear in a right format at
>     everyone.
>
>     since our previous works in remote LFA analysis (papers already
>     sent to these mailing lists) assumed unit cost networks, therefore
>     as I promised, I calculated the corresponding LFA and rLFA
>     coverages in those networks with their original link costs.
>     These networks were inferred from Rocketfuel dataset (/Mahajan,
>     R., Spring, N., Wetherall, D., Anderson, T.:
>     Inferring link weights using end-to-end measurements. In: ACM IMC,
>     pp. 231–236 (2002)/), SNDLib (http://sndlib.zib.de), and
>     TopologyZoo(http://www.topology-zoo.org). The found coverages and
>     some details are found in the table below, where /n/ and /m/
>     denote the number of nodes and the number of links, respectively.
>     The other columns mark the different coverages obrtained by simple
>     LFA and remote LFA, where LP indicates the link-protecting case,
>     while NP notes the case of node protection.
>     Topologies marked with an asterisk(*) did not have inferred real
>     link costs from the datasets, so their costs were initially set to
>     1 (unit costs).
>
>     significantly improve the rlfa draft, especially Sec. 9.3., and
>     the advantages of remote LFA over simple LFA would be more emphasized.
>
>
>     seeking for a remote LFA staging point should be done IF AND ONLY
>     IF no simple LFA were found. This is important, since normally
>     people obviously think and observe that the failure coverage of
>     remote LFA should be greater than or equal to the coverage
>     obtained by simple LFA. Moreover, people also think that LFAs
>     produce a subset of remote LFAs. However, if after a failure only
>     P-spaces and Q-spaces are taken into account in order to seek a
>     (remote) loop-free alternate, then it is possible that a simple
>     LFA would not be found resulting unprotected node-pairs. But, this
>     case could only happen when link costs are not unit costs. For an
>     easier understanding, consider the network depicted below:
>                 1     1
>     Assume that S wishes to send a packet to D, and the shortest path
>     goes through E, therefore it is S-E-C-D. Suppose that the link (s,e)
>     fails, or even the node e itself fails. In this case, since LFA
>     (and its calculation) only consider all other neighbors of s, then
>     node N would be an easy LFA for this failure, since dist(N,D) <
>     dist(N,S)+dist(S,D).
>     However, if we only seek possible remote LFAs, than according to
>     the (r)SPF calculations, or taking into account our
>     distance-function conditions will result that D's Q-space will
>     contain node N (besides some other nodes), but S's P-space won't
>     (it will only contain node F and what is more, if node F does not
>     exist, then S's P-space would be empty), therefore no intersection
>     of the two spaces will exist, leaving this network vulnerable to
>     the failure of link (s,e).
>
>     s,d/ is an extended link-protecting remote LFA for the /s-d/ pair
>     if and only if
>     /∃v //∈ neigh(s) : dist(v, n) < dist(v, s) + dist(s, e) + dist(e,
>     One can easily observe that emphasizing more that remote LFA
>     seeking process is only "executed" after no simple LFA is found
>     could much more ease the understanding and won't result a headache
>     to the reader who accidentally wants to calculate rLFA coverage in
>     such network.
>

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Fri, 2 Aug 2013 08:36:33 +0000

“Yepp, they are not 2-connected”

If they are not 2-connected, isn’t it unfair to write only the coverage there? I mean it would be nice to put there the maximum possible coverage too, that what e.g. MRT can reach.

“I'm a  bit confused:  why do we suppose that not all nodes do rLFA?”

You may have some legacy nodes in real networks.

Gabor

From: Levente Csikor [mailto:[email-masked]]
Sent: Friday, August 02, 2013 10:27 AM
To: Gábor Sándor Enyedi
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some comments and questions

See comments inline.
Abilene: http://www.ots.utsystem.edu/pubs/internet2/graphics/abilenebackbone.gif

Other: did you noticed that with some minimal extra computation,
it is possible to reach 100% node protection with rLFA, if we suppose that all the nodes do rLFA in the network.
I'm a  bit confused:  why do we suppose that not all nodes do rLFA?

Maybe we could assign a single extra label/IP address to say that “use uniform link costs for this packet”, and get something quite similar to MRT? :)

Gabor

From: Levente Csikor [mailto:[email-masked]]
Sent: Friday, August 02, 2013 10:01 AM
To: Gábor Sándor Enyedi
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some comments and questions

Levente

Gabor

Dear All,

Sorry,
Levente

Dear All,

Best,
Levente

---

From: Levente Csikor <[email-masked]>
Date: Fri, 02 Aug 2013 14:05:57 +0200

Dear Stephane,
see comments inline.

On 08/02/2013 10:13 AM, [email-masked] wrote:
>  "I have found that it should be more emphasized in the draft that 
> calculating or seeking for a remote LFA staging point should be done 
> IF AND ONLY IF no simple LFA were found."
> "*9.1* 
> <http://tools.ietf.org/html/draft-ietf-rtgwg-remote-lfa-02#section-9.1>*. 
> Simplicity*
>
Yes, you have right that in most of the cases it is emphasized, probably 
somehow I did read a previous version of the draft.

However, I'm getting a bit confused about you stated below, which is true :)
> (it's a normal LFA also as you stated).
in the draft:
4.2.2 
<http://tools.ietf.org/html/draft-ietf-rtgwg-remote-lfa-02#section-4.2.2>. 
Extended P-space

... "This may be calculated by computing the an SPT at each of S's 
neighbors (N) (excluding E) and excising the subtree reached via the 
path N->S->E..."

In this case, all the neighbors are always examined regardless to the 
costs of the neighboring link, therefore the extended P-space will 
always contain all the neighbors except the failed one. Thus it will 
always contain the simple LFA if it exists.

Am I right?

> My comment :
> - Yes, extended P-Space usage is mandatory in order to maximize 
> coverage (for me it's clearly explained in the draft)
> - draft currently states that remote LFA would be computed only when 
> normal LFA is not available BUT this is not a good idea. Based on the 
> use case we are presenting if draft-ietf-rtgwg-lfa-manageability, 
> there is a strong interrest in always computing rLFA protection then 
> be able to compare attributes of PQs and normal LFAs to determine 
> which one is the more efficient based on service provider 
> requirements. This does not mean that we don't use extended P Space, 
> extended P-Space need always to be used.
> - You are providing NP coverage for rLFA , thanks for the info, but I 
> just want to highlight that this is just "informational" as a router 
> is not able to determine that the PQ is providing NP or not for the 
> specific destination. Determining such PQ attribute would require 
> extra SPF, as stated in 
> *draft*-psarkar-rtgwg-*rlfa*-*node*-*protection*-00 
> <http://www.google.fr/url?q=https://datatracker.ietf.org/doc/draft-psarkar-rtgwg-rlfa-node-protection/&sa=U&ei=zWn7UcyGGMTcOo3agcgM&ved=0CB4QFjAA&usg=AFQjCNE10vQJ-5GomSFsDkPVW6mXz0wzRQ>.
Calculating these coverages these coverages required all-pair shortest 
path computation and then NP and LP rLFAs can be easily determine by 
distance functions

> Stephane

Thanks for your comments,

Levente
>
>     ------------------------------------------------------------------------
>     *De :* [email-masked] [mailto:[email-masked]] *De
>     la part de* Levente Csikor
>     *Envoyé :* jeudi 1 août 2013 16:11
>     *À :* [email-masked]
>     *Cc :* [email-masked];
>     *Objet :* Re: draft-ietf-rtgwg-remote-lfa - ready for WGLC? - some
>     comments and questions
>
>     Dear All,
>     R., Spring, N., Wetherall, D., Anderson, T.://
>     //Inferring link weights using end-to-end measurements. In: ACM
>     IMC, pp. 231–236 (2002)/), SNDLib (http://sndlib.zib.de), and
>     /∃v ∈ neigh(s) : dist(v, n) < dist(v, s) + dist(s, e) + dist(e,
>     n)//*&& dist(s,v) < dist(s,e) + dist(e**,v)*/
>>>     In order to not to read our full papers and searching the
>>>     answers, I copied here the relevant parts:
>>>     For source /s/, destination /d/, and next-hop /e/, some node /n/
>>>     /!= s,d/ is a link-protecting remote LFA for the /s-d/ pair  if
>>>     and only if
>>>     In these equations, one can easily see, that (1) defines the
>>>     P-space, while (2) is the condition of Q-space. Furthermore,
>>>     with these formalized conditions, one can easily observe, that
>>>     (2) is actually the basic loop-free criterion of pure LFA.
>>>
>>>     For source /s/, destination /d/, and next-hop /e/, some node /n
>>>     != s,d/ is an extended link-protecting remote LFA for the /s-d/
>>>     pair if and only if
>>>     For source /s/, destination /d/, and next-hop /e/, some /n !=
>>>     s,d/ is a node-protecting remote LFA for the /s-d/ pair if and
>>>     only if
>>>     For source /s/, destination /d/, and next-hop /e/, some node /n
>>>     != s,d/ is an extended node-protecting remote LFA for the /s-d/
>>>     pair if and only if

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 02 Aug 2013 12:46:34 -0400

Some of the topology data is very old.  TopologyZoo lists a "last
updated" date which does not correspond to when the network looked the
way it did in the update.  For example, networks that look to be from
the late 1980s or 1990s have dates in 2011 or 2012.

NSF looks to be NSFNET circa late 1980s (the AS number would have
helped as the DSO, T1, and T3 NSFNET and vBNS all had differenct AS).
InternetMCI went out of existance in the mid-1990s.  Sprintlink
(AS1239) looks to be same era.

These show the network cores for provider networks.  Some have about
1,000 nodes in their edge network but a small core.  Back in the late
1990s a lot of US networks had a flat ISIS IGP with 600 to 1,200
nodes, according to claims made in NANOG presentations at the time or
claims made outside of meetings at NANOG or IETF.

The data therefore may be real world but a lot of it is about 20 years
old and may not reflect the present.

Curtis

In message <[email-masked]>

---

From: Levente Csikor <[email-masked]>
Date: Fri, 02 Aug 2013 18:57:13 +0200

Sending up-to-date topologies are welcome and suggested:)
I can calculate the coverage of them.

LEMON format is preferred, but GMLor Graph ML, or any humanreadable 
format could be converted.

---

From: <[email-masked]>
Date: Wed, 7 Aug 2013 10:50:37 +0200

Hi Authors and Chairs,

Regarding remote LFA draft, I would hope to see some points addressed in the draft before going to WGLC.
- It would be good to add some simulation results about how much TLDP session are required (TX and TX+RX), this in order to make people aware on how much rLFA may impact their TLDP session scaling

- We already raised the point some months ago about possibly "interop" issues in the following cases :
    * PLR choose a PQ which is not able to accept TLDP session : we verified it in a lab, and we can clearly fall into such situation in a live network, leading to protection not available.

    * PQ having multiple IP addresses /32 attached, so which one would be used to establish TLDP session ? Current implementations are using some heuristics and it would be good to document this

- Current text states that rLFA is computed only when LFA are not available and our analysis pointed that this is really not a good idea as in term of manageability rLFA alternate may be better than LFA alternate. It would be good that rLFA draft points to potential manageability issues and refers to the appropriate draft.

Thanks,

Best Regards,

Stephane