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
