------------------------------------------------------------------------
*De :* [email protected] [mailto:[email protected]] *De
la part de* Levente Csikor
*Envoyé :* jeudi 1 août 2013 16:11
*À :* [email protected]
*Cc :* [email protected];
[email protected]; [email protected]
*Objet :* 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.
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
_________________________________________________________________________________________________________________________
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.
