 1/draftietfrtgwgmrtfrralgorithm02.txt 20150309 14:14:41.808909571 0700
+++ 2/draftietfrtgwgmrtfrralgorithm03.txt 20150309 14:14:41.936912652 0700
@@ 1,24 +1,24 @@
Routing Area Working Group G. Enyedi, Ed.
InternetDraft A. Csaszar
Intended status: Standards Track Ericsson
Expires: July 23, 2015 A. Atlas, Ed.
+Expires: September 10, 2015 A. Atlas, Ed.
C. Bowers
Juniper Networks
A. Gopalan
University of Arizona
 January 19, 2015
+ March 9, 2015
Algorithms for computing Maximally Redundant Trees for IP/LDP Fast
Reroute
 draftietfrtgwgmrtfrralgorithm02
+ draftietfrtgwgmrtfrralgorithm03
Abstract
A complete solution for IP and LDP FastReroute using Maximally
Redundant Trees is presented in [ID.ietfrtgwgmrtfrr
architecture]. This document defines the associated MRT Lowpoint
algorithm that is used in the default MRT profile to compute both the
necessary Maximally Redundant Trees with their associated nexthops
and the alternates to select for MRTFRR.
@@ 30,21 +30,21 @@
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as InternetDrafts. The list of current Internet
Drafts is at http://datatracker.ietf.org/drafts/current/.
InternetDrafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
 This InternetDraft will expire on July 23, 2015.
+ This InternetDraft will expire on September 10, 2015.
Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/licenseinfo) in effect on the date of
publication of this document. Please review these documents
@@ 59,52 +59,52 @@
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5
3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5
4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 7
4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7
4.2. Finding an Ear and the Correct Direction . . . . . . . . 9
4.3. LowPoint Values and Their Uses . . . . . . . . . . . . . 11
4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 15
4.5. Determining LocalRoot and Assigning BlockID . . . . . . 17
5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19
 5.1. MRT Island Identification . . . . . . . . . . . . . . . . 20
 5.2. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21
 5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21
 5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
 inheritance . . . . . . . . . . . . . . . . . . . . . . . 22
 5.5. Augmenting the GADAG by directing all links . . . . . . . 24
 5.6. Compute MRT nexthops . . . . . . . . . . . . . . . . . . 26
 5.6.1. MRT nexthops to all nodes partially ordered with
 respect to the computing node . . . . . . . . . . . . 27
 5.6.2. MRT nexthops to all nodes not partially ordered with
 respect to the computing node . . . . . . . . . . . . 28
 5.6.3. Computing Redundant Tree nexthops in a 2connected
 Graph . . . . . . . . . . . . . . . . . . . . . . . . 29
 5.6.4. Generalizing for a graph that isn't 2connected . . . 30
 5.6.5. Complete Algorithm to Compute MRT NextHops . . . . . 31
 5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33
 5.8. Finding FRR NextHops for ProxyNodes . . . . . . . . . . 37
 6. MRT Lowpoint Algorithm: Nexthop conformance . . . . . . . . 40
 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40
 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41
 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 51
 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51
 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51
 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51
 12. Security Considerations . . . . . . . . . . . . . . . . . . . 51
 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 51
 13.1. Normative References . . . . . . . . . . . . . . . . . . 51
 13.2. Informative References . . . . . . . . . . . . . . . . . 51

 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 53
 Appendix B. Option 3: Computing GADAG using a hybrid method . . 58
 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60
+ 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 19
+ 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22
+ 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23
+ 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23
+ 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
+ inheritance . . . . . . . . . . . . . . . . . . . . . . . 24
+ 5.6. Augmenting the GADAG by directing all links . . . . . . . 26
+ 5.7. Compute MRT nexthops . . . . . . . . . . . . . . . . . . 28
+ 5.7.1. MRT nexthops to all nodes partially ordered with
+ respect to the computing node . . . . . . . . . . . . 29
+ 5.7.2. MRT nexthops to all nodes not partially ordered with
+ respect to the computing node . . . . . . . . . . . . 30
+ 5.7.3. Computing Redundant Tree nexthops in a 2connected
+ Graph . . . . . . . . . . . . . . . . . . . . . . . . 31
+ 5.7.4. Generalizing for a graph that isn't 2connected . . . 32
+ 5.7.5. Complete Algorithm to Compute MRT NextHops . . . . . 33
+ 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 35
+ 5.9. Finding FRR NextHops for ProxyNodes . . . . . . . . . . 39
+ 6. MRT Lowpoint Algorithm: Nexthop conformance . . . . . . . . 42
+ 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 42
+ 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 43
+ 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 53
+ 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 53
+ 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 53
+ 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 53
+ 12. Security Considerations . . . . . . . . . . . . . . . . . . . 53
+ 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 53
+ 13.1. Normative References . . . . . . . . . . . . . . . . . . 53
+ 13.2. Informative References . . . . . . . . . . . . . . . . . 53
+ Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 56
+ Appendix B. Option 3: Computing GADAG using a hybrid method . . 61
+ Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 63
1. Introduction
MRT FastReroute requires that packets can be forwarded not only on
the shortestpath tree, but also on two Maximally Redundant Trees
(MRTs), referred to as the MRTBlue and the MRTRed. A router which
experiences a local failure must also have predetermined which
alternate to use. This document defines how to compute these three
things for use in MRTFRR and describes the algorithm design
decisions and rationale. The algorithm is based on those presented
@@ 376,21 +376,21 @@
disjoint from the decreasing paths. E.g. in the previous example
node B has multiple possibilities to forward packets along an
increasing path: it can either forward packets to C or F.
4.2. Finding an Ear and the Correct Direction
For simplicity, the basic idea of creating a GADAG by adding ears is
described assuming that the network graph is a single 2connected
cluster so that an ADAG is sufficient. Generalizing to multiple
blocks is done by considering the blockroots instead of the GADAG
 root  and the actual algorithm is given in Section 5.4.
+ root  and the actual algorithm is given in Section 5.5.
In order to understand the basic idea of finding an ADAG, first
suppose that we have already a partial ADAG, which doesn't contain
all the nodes in the block yet, and we want to extend it to cover all
the nodes. Suppose that we find a path from a node X to Y such that
X and Y are already contained by our partial ADAG, but all the
remaining nodes along the path are not added to the ADAG yet. We
refer to such a path as an ear.
Recall that our ADAG is closely related to a partial order. More
@@ 432,21 +432,21 @@
cycle; therefore the ear must go from X to Y.
In the case, when X and Y are not ordered with each other, we can
select either direction for the ear. We have no restriction since
neither of the directions can result in a cycle. In the corner case
when one of the endpoints of an ear, say X, is the root (recall that
the two endpoints must be different), we could use both directions
again for the ear because the root can be considered both as smaller
and as greater than Y. However, we strictly pick that direction in
which the root is lower than Y. The logic for this decision is
 explained in Section 5.6
+ explained in Section 5.7
A partial ADAG is started by finding a cycle from the root R back to
itself. This can be done by selecting a nonready neighbor N of R
and then finding a path from N to R that doesn't use any links
between R and N. The direction of the cycle can be assigned either
way since it is starting the ordering.
Once a partial ADAG is already present, it will always have a node
that is not the root R in it. As a brief proof that a partial ADAG
can always have ears added to it: just select a nonready neighbor N
@@ 480,21 +480,21 @@
Add the ear towards Y to the ADAG
Figure 6: Generic Algorithm to find ears and their direction in
2connected graph
Algorithm Figure 6 merely requires that a cycle or ear be selected
without specifying how. Regardless of the way of selecting the path,
we will get an ADAG. The method used for finding and selecting the
ears is important; shorter ears result in shorter paths along the
MRTs. The MRT Lowpoint algorithm's method using LowPoint
 Inheritance is defined in Section 5.4. Other methods are described
+ Inheritance is defined in Section 5.5. Other methods are described
in the Appendices (Appendix A and Appendix B).
As an example, consider Figure 5 again. First, we select the
shortest cycle containing R, which can be RABFDE (uniform link
costs were assumed), so we get to the situation depicted in Figure 5
(b). Finally, we find a node next to a ready node; that must be node
C and assume we reached it from ready node B. We search a path from
C to R without B in the original graph. The first ready node along
this is node D, so the open ear is BCD. Since B<C and C>D to the ADAG. Since all the nodes are ready, we stop at
@@ 549,21 +549,21 @@
Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to
a example graph.
global_variable: dfs_number
Lowpoint_Visit(node x, node parent, interface p_to_x)
D(x) = dfs_number
L(x) = D(x)
dfs_number += 1
x.dfs_parent = parent
 x.dfs_parent_intf = p_to_x
+ x.dfs_parent_intf = p_to_x.remote_intf
x.lowpoint_parent = NONE
for each interface intf of x
if D(intf.remote_node) is not set
Lowpoint_Visit(intf.remote_node, x, intf)
if L(intf.remote_node) < L(x)
L(x) = L(intf.remote_node)
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
else if intf.remote_node is not parent
if D(intf.remote_node) < L(x)
@@ 598,40 +598,40 @@
[A][B] [G] [L][M]
(1, ) (2, ) (7, ) (12, ) (13, )
(b) with DFS values assigned (D(x), L(x))
[E] [J][I] [P][O]
(5,0)  (10,3) (9,3) (16,11) (15,11)
     
     
[R] [D][C][F] [H][K] [N]
 (0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11)
+ (0,0) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11)
     
     
[A][B] [G] [L][M]
(1,0) (2,0) (7,3) (12,11) (13,11)
(c) with lowpoint values assigned (D(x), L(x))
Figure 9: Example lowpoint value computation
From the lowpoint value and lowpoint parent, there are three very
useful things which motivate our computation.
First, if there is a child c of x such that L(c) >= D(x), then there
are no paths in the network graph that go from c or its descendants
to an ancestor of x  and therefore x is a cutvertex. In Figure 9,
this can be seen by looking at the DFS children of C. C has two
children  D and F and L(F) = 3 = D(C) so it is clear that C is a
cutvertex and F is in a block where C is the block's root. L(D) = 0
 > 3 = D(C) so D has a path to the ancestors of C; in this case, D can
+ < 3 = D(C) so D has a path to the ancestors of C; in this case, D can
go via E to reach R. Comparing the lowpoint values of all a node's
DFSchildren with the node's DFSvalue is very useful because it
allows identification of the cutvertices and thus the blocks.
Second, by repeatedly following the path given by lowpoint_parent,
there is a path from x back to an ancestor of x that does not use the
link [x, x.dfs_parent] in either direction. The full path need not
be taken, but this gives a way of finding an initial cycle and then
ears.
@@ 652,54 +652,55 @@
[E] [J][I] [P][O]
     
     
[R] [D][C][F] [H][K] [N]
     
     
[A][B] [G] [L][M]
(a) A graph with four blocks that are:
 3 2connected clusters and a cutlink
+ three 2connected clusters
+ and one cutlink
[E]< [J]<[I] [P]<[O]
   ^  ^
V  V  V 
[R] [D]<[C] [F] [H]<[K] [N]
^  ^ ^
 V  
[A]>[B] [G] [L]>[M]
 (b) MRTBlue
+ (b) MRTBlue for destination R
[E] [J]>[I] [P]>[O]
  
V V V
[R] [D]>[C]<[F] [H]<[K] [N]
^  ^  ^ 
 V    V
[A]<[B] [G]< [L]<[M]
 (c) MRTRed
+ (c) MRTRed for destionation R
Figure 10
Consider the example depicted in Figure 10 (a). In this figure, a
special graph is presented, showing us all the ways 2connected
clusters can be connected. It has four blocks: block 1 contains R,
A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K,
L, M, N, O, P, and block 4 is a cutlink containing H and K. As can
be observed, the first two blocks have one common node (node C) and
blocks 2 and 3 do not have any common node, but they are connected
through a cutlink that is block 4. No two blocks can have more than
 one common node, since two blocks with at least 2 common nodes would
 qualify as a single 2connected cluster.
+ one common node, since two blocks with at least two common nodes
+ would qualify as a single 2connected cluster.
Moreover, observe that if we want to get from one block to another,
we must use a cutvertex (the cutvertices in this graph are C, H,
K), regardless of the path selected, so we can say that all the paths
from block 3 along the MRTs rooted at R will cross K first. This
observation means that if we want to find a pair of MRTs rooted at R,
then we need to build up a pair of RTs in block 3 with K as a root.
Similarly, we need to find another pair of RTs in block 2 with C as a
root, and finally, we need the last pair of RTs in block 1 with R as
a root. When all the trees are selected, we can simply combine them;
@@ 715,38 +716,39 @@
4.5. Determining LocalRoot and Assigning BlockID
Each node in a network graph has a localroot, which is the cut
vertex (or root) in the same block that is closest to the root. The
localroot is used to determine whether two nodes share a common
block.
Compute_Localroot(node x, node localroot)
x.localroot = localroot
 for each DFS child c
+ for each DFS child node c of x
if L(c) < D(x) //x is not a cutvertex
Compute_Localroot(c, x.localroot)
else
mark x as cutvertex
Compute_Localroot(c, x)
Compute_Localroot(root, root)
Figure 11: A method for computing localroots
There are two different ways of computing the localroot for each
node. The standalone method is given in Figure 11 and better
illustrates the concept; it is used by the MRT algorithms given in
the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm
computes the localroot for a block as part of computing the GADAG
using lowpoint inheritance; the essence of this computation is given
 in Figure 12.
+ in Figure 12. Both methods for computing the localroot produce the
+ same results.
Get the current node, s.
Compute an ear(either through lowpoint inheritance
or by following dfs parents) from s to a ready node e.
(Thus, s is not e, if there is such ear.)
if s is e
for each node x in the ear that is not s
x.localroot = s
else
for each node x in the ear that is not s or e
@@ 790,72 +792,156 @@
5. Algorithm Sections
This algorithm computes one GADAG that is then used by a router to
determine its MRTBlue and MRTRed nexthops to all destinations.
Finally, based upon that information, alternates are selected for
each nexthop to each destination. The different parts of this
algorithm are described below. These work on a network graph after
its interfaces have been ordered as per Figure 14.
1. Compute the local MRT Island for the particular MRT Profile.
 [See Section 5.1.]
+ [See Section 5.2.]
 2. Select the root to use for the GADAG. [See Section 5.2.]
+ 2. Select the root to use for the GADAG. [See Section 5.3.]
 3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.]
+ 3. Initialize all interfaces to UNDIRECTED. [See Section 5.4.]
4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See
Figure 8.]
 5. Construct the GADAG. [See Section 5.4]
+ 5. Construct the GADAG. [See Section 5.5]
6. Assign directions to all interfaces that are still UNDIRECTED.
 [See Section 5.5.]
+ [See Section 5.6.]
7. From the computing router x, compute the nexthops for the MRT
 Blue and MRTRed. [See Section 5.6.]
+ Blue and MRTRed. [See Section 5.7.]
8. Identify alternates for each nexthop to each destination by
determining which one of the blue MRT and the red MRT the
 computing router x should select. [See Section 5.7.]
+ computing router x should select. [See Section 5.8.]
+
+5.1. Interface Ordering
To ensure consistency in computation, all routers MUST order
interfaces identically down to the set of links with the same metric
to the same neighboring node. This is necessary for the DFS, where
the selection order of the interfaces to explore results in different
trees, and for computing the GADAG, where the selection order of the
interfaces to use to form ears can result in different GADAGs. The
required ordering between two interfaces from the same router x is
given in Figure 14.
Interface_Compare(interface a, interface b)
if a.metric < b.metric
return A_LESS_THAN_B
if b.metric < a.metric
return B_LESS_THAN_A
 if a.neighbor.loopback_addr < b.neighbor.loopback_addr
+ if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id
return A_LESS_THAN_B
 if b.neighbor.loopback_addr < a.neighbor.loopback_addr
+ if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id
return B_LESS_THAN_A
 // Same metric to same node, so the order doesn't matter anymore for
+ // Same metric to same node, so the order doesn't matter for
// interoperability.
 // To have a unique, consistent total order,
 // tiebreak in OSPF based on the link's linkData as
 // distributed in an OSPF RouterLSA
 if a.link_data < b.link_data
 return A_LESS_THAN_B
 return B_LESS_THAN_A
+ return A_EQUAL_TO_B
Figure 14: Rules for ranking multiple interfaces. Order is from low
to high.
5.1. MRT Island Identification
+ In Figure 14, if two interfaces on a router connect to the same
+ remote router with the same metric, the Interface_Compare function
+ returns A_EQUAL_TO_B. This is because the order in which those
+ interfaces are initially explored does not affect the final GADAG
+ produced by the algorithm described here. While only one of the
+ links will be added to the GADAG in the initial traversal, the other
+ parallel links will be added to the GADAG with the same direction
+ assigned during the procedure for assigning direction to UNDIRECTED
+ links described in Section 5.6. An implementation is free to apply
+ some additional criteria to break ties in interface ordering in this
+ situation, but that criteria is not specified here since it will not
+ affect the final GADAG produced by the algorithm.
+
+ The Interface_Compare function in Figure 14 relies on the
+ interface.metric and the interface.neighbor.mrt_node_id values to
+ order interfaces. The exact source of these values for different
+ IGPs (or flooding protocol in the case of ISISPCR
+ [ID.farkasisispcr]) and applications is specified in Figure 15.
+ The metric and mrt_node_id values for OSPFv2, OSPFv3, and ISIS
+ provided here is normative. The metric and mrt_node_id values for
+ ISISPCR should be considered informational.
+
+ ++++
+  IGP/flooding  mrt_node_id  metric of 
+  protocol  of neighbor  interface 
+  and  on interface  
+  application   
+ ++++
+  OSPFv2 for  4 octet Neighbor  2 octet Metric field 
+  IP/LDP FRR  Router ID in  for corresponding 
+   Link ID field for  pointtopoint link 
+   corresponding  in RouterLSA 
+   pointtopoint link  
+   in RouterLSA  
+ ++++
+  OSPFv3 for  4 octet Neighbor  2 octet Metric field 
+  IP/LDP FRR  Router ID field  for corresponding 
+   for corresponding  pointtopoint link 
+   pointtopoint link  in RouterLSA 
+   in RouterLSA  
+ ++++
+  ISIS for  7 octet neighbor  3 octet metric field 
+  IP/LDP FRR  system ID and  in Extended IS 
+   pseudonode number  Reachability TLV #22 
+   in Extended IS  or MultiTopology 
+   Reachability TLV #22  IS Neighbor TLV #222 
+   or MultiTopology  
+   IS Neighbor TLV #222  
+ ++++
+  ISISPCR for  8 octet Bridge ID  3 octet SPBLINKMETRIC in 
+  protection  created from 2 octet  SPBMetric subTLV (type 29)
+  of traffic  Bridge Priority in  in Extended IS Reachability 
+  in bridged  SPB Instance subTLV  TLV #22 or MultiTopology 
+  networks  (type 1) carried in  Intermediate Systems 
+   MTCapability TLV  TLV #222. In the case 
+   #144 and 6 octet  of asymmetric link metrics, 
+   neighbor system ID in  the larger link metric 
+   Extended IS  is used for both link 
+   Reachability TLV #22  directions. 
+   or MultiTopology  (informational) 
+   Intermediate Systems  
+   TLV #222  
+   (informational)  
+ ++++
+
+ Figure 15: value of interface.neighbor.mrt_node_id and
+ interface.metric to be used for ranking interfaces, for different
+ flooding protocols and applications
+
+ The metrics are unsigned integers and MUST be compared as unsigned
+ integers. The results of mrt_node_id comparisons MUST be the same as
+ would be obtained by converting the mrt_node_ids to unsigned integers
+ using network byte order and performing the comparison as unsigned
+ integers. Also note that these values are only specified in the case
+ of pointtopoint links. Therefore, in the case of ISIS for IP/LDP
+ FRR, the pseudonode number (the 7th octet) will always be zero.
+
+ In the case of ISIS for IP/LDP FRR, this specification allows for
+ the use of MultiTopology routing. [RFC5120] requires that
+ information related to the standard/default topology (MTID = 0) be
+ carried in the Extended IS Reachability TLV #22, while it requires
+ that the MultiTopology IS Neighbor TLV #222 only be used to carry
+ topology information related to nondefault topologies (with nonzero
+ MTIDs). [RFC5120] enforces this by requiring an implementation to
+ ignore TLV#222 with MTID = 0. The current document also requires
+ that TLV#222 with MTID = 0 MUST be ignored.
+
+5.2. MRT Island Identification
The local MRT Island for a particular MRT profile can be determined
by starting from the computing router in the network graph and doing
a breadthfirstsearch (BFS). The BFS explores only links that are
in the same area/level, are not IGPexcluded, and are not MRT
ineligible. The BFS explores only nodes that are are not IGP
excluded, and that support the particular MRT profile. See section 7
of [ID.ietfrtgwgmrtfrrarchitecture] for more precise definitions
of these criteria.
@@ 867,70 +953,70 @@
while (explore_list is not empty)
next_rtr = remove_head(explore_list)
for each interface in next_rtr
if interface is (not MRTineligible and not IGPexcluded
and in area)
if ((interface.remote_node supports profile_id) and
(interface.remote_node.IN_MRT_ISLAND is FALSE))
interface.remote_node.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, interface.remote_node)
 Figure 15: MRT Island Identification
+ Figure 16: MRT Island Identification
5.2. GADAG Root Selection
+5.3. GADAG Root Selection
In Section 8.3 of [ID.ietfrtgwgmrtfrrarchitecture], the GADAG
Root Selection Policy is described for the MRT default profile. In
 [ID.atlasospfmrt] and [ID.liisismrt], a mechanism is given for
+ [ID.ietfospfmrt] and [ID.ietfisismrt], a mechanism is given for
routers to advertise the GADAG Root Selection Priority and
consistently select a GADAG Root inside the local MRT Island. The
MRT Lowpoint algorithm simply requires that all routers in the MRT
Island MUST select the same GADAG Root; the mechanism can vary based
upon the MRT profile description. Before beginning computation, the
network graph is reduced to contain only the set of routers that
support the specific MRT profile whose MRTs are being computed.
Analysis has shown that the centrality of a router can have a
significant impact on the lengths of the alternate paths computed.
Therefore, it is RECOMMENDED that offline analysis that considers
the centrality of a router be used to help determine how good a
choice a particular router is for the role of GADAG root.
5.3. Initialization
+5.4. Initialization
Before running the algorithm, there is the standard type of
initialization to be done, such as clearing any computed DFSvalues,
lowpointvalues, DFSparents, lowpointparents, any MRTcomputed
nexthops, and flags associated with algorithm.
It is assumed that a regular SPF computation has been run so that the
primary nexthops from the computing router to each destination are
known. This is required for determining alternates at the last step.
Initially, all interfaces MUST be initialized to UNDIRECTED. Whether
they are OUTGOING, INCOMING or both is determined when the GADAG is
constructed and augmented.
It is possible that some links and nodes will be marked as unusable
using standard IGP mechanisms (see section 7 of
[ID.ietfrtgwgmrtfrrarchitecture]). Due to FRR manageability
considerations [ID.ietfrtgwglfamanageability], it may also be
desirable to administratively configure some interfaces as ineligible
to carry MRT FRR traffic. This constraint MUST be consistently
 flooded via the IGP [ID.atlasospfmrt] [ID.liisismrt] by the
+ flooded via the IGP [ID.ietfospfmrt] [ID.ietfisismrt] by the
owner of the interface, so that links are clearly known to be MRT
ineligible and not explored or used in the MRT algorithm. In the
algorithm description, it is assumed that such links and nodes will
not be explored or used, and no more discussion is given of this
restriction.
5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance
+5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance
As discussed in Section 4.2, it is necessary to find ears from a node
x that is already in the GADAG (known as IN_GADAG). Two different
methods are used to find ears in the algorithm. The first is by
going to a not IN_GADAG DFSchild and then following the chain of
lowpoint parents until an IN_GADAG node is found. The second is by
going to a not IN_GADAG neighbor and then following the chain of DFS
parents until an IN_GADAG node is found. As an ear is found, the
associated interfaces are marked based on the direction taken. The
nodes in the ear are marked as IN_GADAG. In the algorithm, first the
@@ 969,79 +1055,79 @@
the ear unless the end of the ear is x itself, in which case the
localroot for all the nodes in the ear would be x. This is because
whenever the first cycle is found in a block, or an ear involving a
bridge is computed, the cutvertex closest to the root would be x
itself. In all other scenarios, the properties of lowpoint/dfs
parents ensure that the end of the ear will be in the same block, and
thus inheriting its localroot would be the correct localroot for
all newly added nodes.
The pseudocode for the GADAG algorithm (assuming that the adjustment
 of lowpoint for cutvertices has been made) is shown in Figure 16.
+ of lowpoint for cutvertices has been made) is shown in Figure 17.
 Construct_Ear(x, Stack, intf, type)
+ Construct_Ear(x, Stack, intf, ear_type)
ear_list = empty
cur_node = intf.remote_node
cur_intf = intf
not_done = true
while not_done
cur_intf.UNDIRECTED = false
cur_intf.OUTGOING = true
cur_intf.remote_intf.UNDIRECTED = false
cur_intf.remote_intf.INCOMING = true
if cur_node.IN_GADAG is false
cur_node.IN_GADAG = true
add_to_list_end(ear_list, cur_node)
 if type is CHILD
+ if ear_type is CHILD
cur_intf = cur_node.lowpoint_parent_intf
cur_node = cur_node.lowpoint_parent
 else type must be NEIGHBOR
+ else // ear_type must be NEIGHBOR
cur_intf = cur_node.dfs_parent_intf
cur_node = cur_node.dfs_parent
else
not_done = false
 if (type is CHILD) and (cur_node is x)
+ if (ear_type is CHILD) and (cur_node is x)
//x is a cutvertex and the local root for
//the block in which the ear is computed
localroot = x
else
// Inherit localroot from the end of the ear
localroot = cur_node.localroot
while ear_list is not empty
y = remove_end_item_from_list(ear_list)
y.localroot = localroot
push(Stack, y)
Construct_GADAG_via_Lowpoint(topology, root)
root.IN_GADAG = true
 root.localroot = root
+ root.localroot = None
Initialize Stack to empty
push root onto Stack
while (Stack is not empty)
x = pop(Stack)
foreach interface intf of x
if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is x))
Construct_Ear(x, Stack, intf, CHILD)
foreach interface intf of x
if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is not x))
Construct_Ear(x, Stack, intf, NEIGHBOR)
Construct_GADAG_via_Lowpoint(topology, root)
 Figure 16: Lowpoint Inheritance GADAG algorithm
+ Figure 17: Lowpoint Inheritance GADAG algorithm
5.5. Augmenting the GADAG by directing all links
+5.6. Augmenting the GADAG by directing all links
The GADAG, regardless of the algorithm used to construct it, at this
point could be used to find MRTs but the topology does not include
all links in the network graph. That has two impacts. First, there
might be shorter paths that respect the GADAG partial ordering and so
the alternate paths would not be as short as possible. Second, there
may be additional paths between a router x and the root that are not
included in the GADAG. Including those provides potentially more
bandwidth to traffic flowing on the alternates and may reduce
congestion compared to just using the GADAG as currently constructed.
@@ 1058,21 +1144,21 @@
the topological sort is that it works on DAGs and not ADAGs or
GADAGs.
To convert a GADAG to a DAG, it is necessary to remove all links that
point to a root of block from within that block. That provides the
necessary conversion to a DAG and then a topological sort can be
done. Finally, all UNDIRECTED links are assigned a direction based
upon the total ordering. Any UNDIRECTED links that connect to a root
of a block from within that block are assigned a direction INCOMING
to that root. The exact details of this whole process are captured
 in Figure 17
+ in Figure 18
Set_Block_Root_Incoming_Links(topo, root, mark_or_clear)
foreach node x in topo
if node x is a cutvertex or root
foreach interface i of x
if (i.remote_node.localroot is x)
if i.UNDIRECTED
i.OUTGOING = true
i.remote_intf.INCOMING = true
i.UNDIRECTED = false
i.remote_intf.UNDIRECTED = false
@@ 1128,149 +1214,157 @@
i.remote_intf.INCOMING = true
i.remote_intf.UNDIRECTED = false
else
i.INCOMING = true
i.UNDIRECTED = false
i.remote_intf.OUTGOING = true
i.remote_intf.UNDIRECTED = false
Add_Undirected_Links(topo, root)
 Figure 17: Assigning direction to UNDIRECTED links
+ Figure 18: Assigning direction to UNDIRECTED links
Proxynodes do not need to be added to the network graph. They
cannot be transited and do not affect the MRTs that are computed.
The details of how the MRTBlue and MRTRed nexthops are computed
for proxynodes and how the appropriate alternate nexthops are
 selected is given in Section 5.8.
+ selected is given in Section 5.9.
5.6. Compute MRT nexthops
+5.7. Compute MRT nexthops
As was discussed in Section 4.1, once a ADAG is found, it is
straightforward to find the nexthops from any node X to the ADAG
root. However, in this algorithm, we will reuse the common GADAG and
find not only the one pair of MRTs rooted at the GADAG root with it,
but find a pair rooted at each node. This is useful since it is
significantly faster to compute.
The method for computing differently rooted MRTs from the common
GADAG is based on two ideas. First, if two nodes X and Y are ordered
with respect to each other in the partial order, then an SPF along
OUTGOING links (an increasingSPF) and an SPF along INCOMING links (a
decreasingSPF) can be used to find the increasing and decreasing
paths. Second, if two nodes X and Y aren't ordered with respect to
each other in the partial order, then intermediary nodes can be used
to create the paths by increasing/decreasing to the intermediary and
then decreasing/increasing to reach Y.
As usual, the two basic ideas will be discussed assuming the network
is twoconnected. The generalization to multiple blocks is discussed
 in Section 5.6.4. The full algorithm is given in Section 5.6.5.
+ in Section 5.7.4. The full algorithm is given in Section 5.7.5.
5.6.1. MRT nexthops to all nodes partially ordered with respect to the
+5.7.1. MRT nexthops to all nodes partially ordered with respect to the
computing node
To find two nodedisjoint paths from the computing router X to any
node Y, depends upon whether Y >> X or Y << X. As shown in
 Figure 18, if Y >> X, then there is an increasing path that goes from
+ Figure 19, if Y >> X, then there is an increasing path that goes from
X to Y without crossing R; this contains nodes in the interval [X,Y].
There is also a decreasing path that decreases towards R and then
decreases from R to Y; this contains nodes in the interval
[X,Rsmall] or [Rgreat,Y]. The two paths cannot have common nodes
other than X and Y.
[Y]<(Cloud 2)< [X]
 ^
 
V 
(Cloud 3)>[R]>(Cloud 1)
MRTBlue path: X>Cloud 2>Y
MRTRed path: X>Cloud 1>R>Cloud 3>Y
 Figure 18: Y >> X
+ Figure 19: Y >> X
 Similar logic applies if Y << X, as shown in Figure 19. In this
+ Similar logic applies if Y << X, as shown in Figure 20. In this
case, the increasing path from X increases to R and then increases
from R to Y to use nodes in the intervals [X,Rgreat] and [Rsmall,
Y]. The decreasing path from X reaches Y without crossing R and uses
nodes in the interval [Y,X].
[X]<(Cloud 2)< [Y]
 ^
 
V 
(Cloud 3)>[R]>(Cloud 1)
MRTBlue path: X>Cloud 3>R>Cloud 1>Y
MRTRed path: X>Cloud 2>Y
 Figure 19: Y << X
+ Figure 20: Y << X
5.6.2. MRT nexthops to all nodes not partially ordered with respect to
+5.7.2. MRT nexthops to all nodes not partially ordered with respect to
the computing node
When X and Y are not ordered, the first path should increase until we
get to a node G, where G >> Y. At G, we need to decrease to Y. The
other path should be just the opposite: we must decrease until we get
to a node H, where H << Y, and then increase. Since R is smaller and
greater than Y, such G and H must exist. It is also easy to see that
these two paths must be node disjoint: the first path contains nodes
in interval [X,G] and [Y,G], while the second path contains nodes in
 interval [H,X] and [H,Y]. This is illustrated in Figure 20. It is
+ interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is
necessary to decrease and then increase for the MRTBlue and increase
and then decrease for the MRTRed; if one simply increased for one
and decreased for the other, then both paths would go through the
root R.
(Cloud 6)<[Y]<(Cloud 5)<
 
 
V 
[G]>(Cloud 4)>[R]>(Cloud 1)>[H]
^ 
 
 
(Cloud 3)<[X]<(Cloud 2)<
MRTBlue path: decrease to H and increase to Y
X>Cloud 2>H>Cloud 5>Y
MRTRed path: increase to G and decrease to Y
X>Cloud 3>G>Cloud 6>Y
 Figure 20: X and Y unordered
+ Figure 21: X and Y unordered
This gives disjoint paths as long as G and H are not the same node.
Since G >> Y and H << Y, if G and H could be the same node, that
would have to be the root R. This is not possible because there is
only one incoming interface to the root R which is created when the
initial cycle is found. Recall from Figure 6 that whenever an ear
was found to have an end that was the root R, the ear was directed
from R so that the associated interface on R is outgoing and not
incoming. Therefore, there must be exactly one node M which is the
largest one before R, so the MRTRed path will never reach R; it will
turn at M and decrease to Y.
5.6.3. Computing Redundant Tree nexthops in a 2connected Graph
+5.7.3. Computing Redundant Tree nexthops in a 2connected Graph
The basic ideas for computing RT nexthops in a 2connected graph
 were given in Section 5.6.1 and Section 5.6.2. Given these two
+ were given in Section 5.7.1 and Section 5.7.2. Given these two
ideas, how can we find the trees?
If some node X only wants to find the nexthops (which is usually the
case for IP networks), it is enough to find which nodes are greater
and less than X, and which are not ordered; this can be done by
running an increasingSPF and a decreasingSPF rooted at X and not
 exploring any links from the ADAG root. ( Traversal algorithms other
 than SPF could safely be used instead where one traversal takes the
 links in their given directions and the other reverses the links'
 directions.)
+ exploring any links from the ADAG root.
+
+ In principle, an traversal method other than SPF could be used to
+ traverse the GADAG in the process of determining blue and red next
+ hops that result in maximally redundant trees. This will be the case
+ as long as one traversal uses the links in the direction specified by
+ the GADAG and the other traversal uses the links in the direction
+ opposite of that specified by the GADAG. However, a different
+ traversal algorithm will generally result in different blue and red
+ nexthops. Therefore, the algorithm specified here requires the use
+ of SPF to traverse the GADAG to generate MRT blue and red nexthops,
+ as described below.
An increasingSPF rooted at X and not exploring links from the root
will find the increasing nexthops to all Y >> X. Those increasing
nexthops are X's nexthops on the MRTBlue to reach Y. A
decreasingSPF rooted at X and not exploring links from the root will
find the decreasing nexthops to all Z << X. Those decreasing next
hops are X's nexthops on the MRTRed to reach Z. Since the root R
is both greater than and less than X, after this increasingSPF and
decreasingSPF, X's nexthops on the MRTBlue and on the MRTRed to
reach R are known. For every node Y >> X, X's nexthops on the MRT
@@ 1302,47 +1396,47 @@
    ^ 
   V  
R F C R F C
    ^ ^
   V  
AB A>B
(a) (b)
A 2connected graph A spanning ADAG rooted at R
 Figure 21
+ Figure 22
 As an example consider the situation depicted in Figure 21. Node C
+ As an example consider the situation depicted in Figure 22. Node C
runs an increasingSPF and a decreasingSPF on the ADAG. The
increasingSPF reaches D, E and R and the decreasingSPF reaches B, A
and R. E>>C. So towards E the MRTBlue nexthop is D, since E was
reached on the increasing path through D. And the MRTRed nexthop
towards E is B, since R was reached on the decreasing path through B.
Since E>>D, D will similarly compute its MRTBlue nexthop to be E,
ensuring that a packet on MRTBlue will use path CDE. B, A and R
will similarly compute the MRTRed nexthops towards E (which is
ordered less than B, A and R), ensuring that a packet on MRTRed will
use path CBARE.
C can determine the nexthops towards F as well. Since F is not
ordered with respect to C, the MRTBlue nexthop is the decreasing
one towards R (which is B) and the MRTRed nexthop is the increasing
one towards R (which is D). Since F>>B, for its MRTBlue nexthop
towards F, B will use the real increasing nexthop towards F. So a
packet forwarded to B on MRTBlue will get to F on path CBF.
Similarly, D will use the real decreasing nexthop towards F as its
 MRTRed nexthop, an packet on MRTRed will use path CDF.
+ MRTRed nexthop, a packet on MRTRed will use path CDF.
5.6.4. Generalizing for a graph that isn't 2connected
+5.7.4. Generalizing for a graph that isn't 2connected
If a graph isn't 2connected, then the basic approach given in
 Section 5.6.3 needs some extensions to determine the appropriate MRT
+ Section 5.7.3 needs some extensions to determine the appropriate MRT
nexthops to use for destinations outside the computing router X's
blocks. In order to find a pair of maximally redundant trees in that
graph we need to find a pair of RTs in each of the blocks (the root
of these trees will be discussed later), and combine them.
When computing the MRT nexthops from a router X, there are three
basic differences:
1. Only nodes in a common block with X should be explored in the
increasingSPF and decreasingSPF.
@@ 1362,104 +1456,99 @@
increasingSPF or decreasingSPF, then W is unordered with
respect to X. X's MRTBlue nexthops to W are X's decreasing
(aka MRTRed) nexthops to X's localroot. X's MRTRed next
hops to W are X's increasing (aka MRTBlue) nexthops to X's
localroot.
3. For nodes in different blocks, the nexthops must be inherited
via the relevant cutvertex.
These are all captured in the detailed algorithm given in
 Section 5.6.5.
+ Section 5.7.5.
5.6.5. Complete Algorithm to Compute MRT NextHops
+5.7.5. Complete Algorithm to Compute MRT NextHops
The complete algorithm to compute MRT NextHops for a particular
 router X is given in Figure 22. In addition to computing the MRT
+ router X is given in Figure 23. In addition to computing the MRT
Blue nexthops and MRTRed nexthops used by X to reach each node Y,
the algorithm also stores an "order_proxy", which is the proper cut
vertex to reach Y if it is outside the block, and which is used later
in deciding whether the MRTBlue or the MRTRed can provide an
acceptable alternate for a particular primary nexthop.
In_Common_Block(x, y)
 if (((x.localroot is y.localroot) and (x.block_id is y.block_id))
+ if ( (x.block_id is y.block_id))
or (x is y.localroot) or (y is x.localroot))
return true
return false
 Store_Results(y, direction, spf_root, store_nhs)
+Store_Results(y, direction)
if direction is FORWARD
y.higher = true
 if store_nhs
y.blue_next_hops = y.next_hops
if direction is REVERSE
y.lower = true
 if store_nhs
y.red_next_hops = y.next_hops
 SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs)
+SPF_No_Traverse_Root(spf_root, block_root, direction)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity and next_hops to empty
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
while (spf_heap is not empty)
min_node = remove_lowest(spf_heap)
 Store_Results(min_node, direction, spf_root, store_nhs)
+ Store_Results(min_node, direction)
if ((min_node is spf_root) or (min_node is not block_root))
foreach interface intf of min_node
 if (((direction is FORWARD) and intf.OUTGOING) or
 ((direction is REVERSE) and intf.INCOMING) and
 In_Common_Block(spf_root, intf.remote_node))
+ if ( ( ((direction is FORWARD) and intf.OUTGOING) or
+ ((direction is REVERSE) and intf.INCOMING) )
+ and In_Common_Block(spf_root, intf.remote_node) )
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric
if min_node is spf_root
intf.remote_node.next_hops = make_list(intf)
else
intf.remote_node.next_hops = min_node.next_hops
insert_or_update(spf_heap, intf.remote_node)
else if path_metric is intf.remote_node.spf_metric
if min_node is spf_root
add_to_list(intf.remote_node.next_hops, intf)
else
add_list_to_list(intf.remote_node.next_hops,
min_node.next_hops)
SetEdge(y)
if y.blue_next_hops is empty and y.red_next_hops is empty
 if (y.local_root != y) {
+ if (y.localroot != y)
SetEdge(y.localroot)
 }
y.blue_next_hops = y.localroot.blue_next_hops
y.red_next_hops = y.localroot.red_next_hops
y.order_proxy = y.localroot.order_proxy
Compute_MRT_NextHops(x, root)
foreach node y
y.higher = y.lower = false
clear y.red_next_hops and y.blue_next_hops
y.order_proxy = y
 SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE)
 SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE)
+ SPF_No_Traverse_Root(x, x.localroot, FORWARD)
+ SPF_No_Traverse_Root(x, x.localroot, REVERSE)
// red and blue nexthops are stored to x.localroot as different
// paths are found via the SPF and reverseSPF.
// Similarly any nodes whose localroot is x will have their
// red_next_hops and blue_next_hops already set.
// Handle nodes in the same block that aren't the localroot
foreach node y
if (y.IN_MRT_ISLAND and (y is not x) and
 (y.localroot is x.localroot) and
 ((y is x.localroot) or (x is y.localroot) or
 (y.block_id is x.block_id)))
+ (y.block_id is x.block_id) )
if y.higher
y.red_next_hops = x.localroot.red_next_hops
else if y.lower
y.blue_next_hops = x.localroot.blue_next_hops
else
y.blue_next_hops = x.localroot.red_next_hops
y.red_next_hops = x.localroot.blue_next_hops
// Inherit nexthops and order_proxies to other components
if x is not root
@@ 1467,41 +1556,41 @@
root.red_next_hops = x.localroot.red_next_hops
root.order_proxy = x.localroot
foreach node y
if (y is not root) and (y is not x) and y.IN_MRT_ISLAND
SetEdge(y)
max_block_id = 0
Assign_Block_ID(root, max_block_id)
Compute_MRT_NextHops(x, root)
 Figure 22
+ Figure 23
5.7. Identify MRT alternates
+5.8. Identify MRT alternates
At this point, a computing router S knows its MRTBlue nexthops and
MRTRed nexthops for each destination in the MRT Island. The
primary nexthops along the SPT are also known. It remains to
determine for each primary nexthop to a destination D, which of the
MRTs avoids the primary nexthop node F. This computation depends
upon data set in Compute_MRT_NextHops such as each node y's
y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower
and topo_orders. Recall that any router knows only which are the
nodes greater and lesser than itself, but it cannot decide the
relation between any two given nodes easily; that is why we need
topological ordering.
For each primary nexthop node F to each destination D, S can call
Select_Alternates(S, D, F, primary_intf) to determine whether to use
the MRTBlue nexthops as the alternate nexthop(s) for that primary
next hop or to use the MRTRed nexthops. The algorithm is given in
 Figure 23 and discussed afterwards.
+ Figure 24 and discussed afterwards.
Select_Alternates_Internal(S, D, F, primary_intf,
D_lower, D_higher, D_topo_order)
//When D==F, we can do only link protection
if ((D is F) or (D.order_proxy is F))
if an MRT doesn't use primary_intf
indicate alternate is not nodeprotecting
return that MRT color
else // parallel links are cutlinks
@@ 1520,23 +1609,23 @@
return USE_BLUE
if (F.lower and F.higher)
if D_lower
return USE_RED
else if D_higher
return USE_BLUE
else
if primary_intf.OUTGOING and primary_intf.INCOMING
return AVOID_LINK_ON_BLUE
 if primary_intf.OUTGOING is true
+ if primary_intf.OUTGOING
return USE_BLUE
 if primary_intf.INCOMING is true
+ if primary_intf.INCOMING
return USE_RED
if D_higher
if F.higher
if F.topo_order < D_topo_order
return USE_RED
else
return USE_BLUE
else if F.lower
return USE_BLUE
@@ 1565,21 +1654,21 @@
D_lower = D.order_proxy.lower
D_higher = D.order_proxy.higher
D_topo_order = D.order_proxy.topo_order
else
D_lower = D.lower
D_higher = D.higher
D_topo_order = D.topo_order
return Select_Alternates_Internal(S, D, F, primary_intf,
D_lower, D_higher, D_topo_order)
 Figure 23
+ Figure 24
If either D>>S>>F or D<>D (ii) F<>G, we need to compare H.topo_order and
D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller
than H, so we should select the decreasing path towards the root.

If, however, the destination were instead J, we must find that
H.topo_order>J.topo_order, so we must choose the increasing Blue
nexthop to J, which is I. In the case, when instead the destination
is C, we find that we need to first decrease to avoid using H, so the
Blue, first decreasing then increasing, path is selected.
[E]<[D]<[H]<[J]
 ^ ^ ^
V   
[R] [C] [G]>[I]
@@ 1640,26 +1728,26 @@
Blue, first decreasing then increasing, path is selected.
[E]<[D]<[H]<[J]
 ^ ^ ^
V   
[R] [C] [G]>[I]
 ^ ^ ^
V   
[A]>[B]>[F]
 (a)
+ (a)ADAG rooted at R for
a 2connected graph
 Figure 24
+ Figure 25
5.8. Finding FRR NextHops for ProxyNodes
+5.9. Finding FRR NextHops for ProxyNodes
As discussed in Section 10.2 of
[ID.ietfrtgwgmrtfrrarchitecture], it is necessary to find MRT
Blue and MRTRed nexthops and MRTFRR alternates for a named proxy
nodes. An example case is for a router that is not part of that
local MRT Island, when there is only partial MRT support in the
domain.
A first incorrect and naive approach to handling proxynodes, which
cannot be transited, is to simply add these proxynodes to the graph
@@ 1760,29 +1848,29 @@
return Select_Alternates_Internal(S, P, F, primary_intf,
P.neighbor_B.lower,
P.neighbor_A.higher,
P.neighbor_A.topo_order)
else
return Select_Alternates_Internal(S, P, F, primary_intf,
P.neighbor_B.lower,
P.neighbor_A.higher,
P.neighbor_B.topo_order)
 Figure 25
+ Figure 26
6. MRT Lowpoint Algorithm: Nexthop conformance
This specification defines the MRT Lowpoint Algorithm, which include
the construction of a common GADAG and the computation of MRTRed and
MRTBlue nexthops to each node in the graph. An implementation MAY
select any subset of nexthops for MRTRed and MRTBlue that respect
 the available nodes that are described in Section 5.6 for each of the
+ the available nodes that are described in Section 5.7 for each of the
MRTRed and MRTBlue and the selected nexthops are further along in
the interval of allowed nodes towards the destination.
For example, the MRTBlue nexthops used when the destination Y >> X,
the computing router, MUST be one or more nodes, T, whose topo_order
is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y
is T. Similarly, the MRTRed nexthops MUST be have a topo_order in
the interval [Rsmall.topo_order, X.topo_order] or [Y.topo_order,
Rbig.topo_order].
@@ 1811,21 +1899,21 @@
they did not provide significant differences in the path lenghts for
the alternatives. This section does not focus on that analysis or
the decision to use the MRT Lowpoint algorithm as the default MRT
algorithm; it has the lowest computational and storage requirements
and gave comparable results.
Since this document defines the MRT Lowpoint algorithm for use in
fastreroute applications, it is useful to compare MRT and Remote LFA
[ID.ietfrtgwgremotelfa]. This section compares MRT and remote
LFA for IP Fast Reroute in 19 service provider network topologies,
 focusing on coverage and alternate path length. Figure 26 shows the
+ focusing on coverage and alternate path length. Figure 27 shows the
nodeprotecting coverage provided by local LFA (LLFA), remote LFA
(RLFA), and MRT against different failure scenarios in these
topologies. The coverage values are calculated as the percentage of
sourcedestination pairs protected by the given IPFRR method relative
to those protectable by optimal routing, against the same failure
modes. More details on alternate selection policies used for this
analysis are described later in this section.
+++
 Topology  percentage of failure 
@@ 1848,38 +1936,38 @@
 T212  59  63  100 
 T213  84  84  100 
 T214  68  78  100 
 T215  84  88  100 
 T216  43  59  100 
 T217  78  88  100 
 T218  72  75  100 
 T219  78  84  100 
+++++
 Figure 26
+ Figure 27
For the topologies analyzed here, LLFA is able to provide node
protecting coverage ranging from 37% to 95% of the sourcedestination
pairs, as seen in the column labeled NP_LLFA. The use of RLFA in
addition to LLFA is generally able to increase the nodeprotecting
coverage. The percentage of nodeprotecting coverage with RLFA is
provided in the column labeled NP_RLFA, ranges from 59% to 98% for
these topologies. The nodeprotecting coverage provided by MRT is
100% since MRT is able to provide protection for any source
destination pair for which a path still exists after the failure.
We would also like to measure the quality of the alternate paths
produced by these different IPFRR methods. An obvious approach is to
take an average of the alternate path costs over all source
destination pairs and failure modes. However, this presents a
problem, which we will illustrate by presenting an example of results
 for one topology using this approach ( Figure 27). In this table,
+ for one topology using this approach ( Figure 28). In this table,
the average relative path length is the alternate path length for the
IPFRR method divided by the optimal alternate path length, averaged
over all sourcedestination pairs and failure modes. The first three
columns of data in the table give the path length calculated from the
sum of IGP metrics of the links in the path. The results for
topology T208 show that the metricbased path lengths for NP_LLFA and
NP_RLFA alternates are on average 78 and 66 times longer than the
path lengths for optimal alternates. The metricbased path lengths
for MRT alternates are on average 14 times longer than for optimal
alternates.
@@ 1887,45 +1975,45 @@
+++
  average relative alternate path length 
 ++
Topology IGP metric  hopcount 
 ++
 NP_LLFA NP_RLFA  MRT NP_LLFA NP_RLFA  MRT 
++++++++
 T208  78.2  66.0  13.6 0.99  1.01  1.32 
++++++++
 Figure 27
+ Figure 28
The network topology represented by T208 uses values of 10, 100, and
1000 as IGP costs, so small deviations from the optimal alternate
path can result in large differences in relative path length. LLFA,
RLFA, and MRT all allow for at least one hop in the alterate path to
be chosen independent of the cost of the link. This can easily
result in an alternate using a link with cost 1000, which introduces
noise into the path length measurement. In the case of T208, the
adverse effects of using metricbased path lengths is obvious.
However, we have observed that the metricbased path length
introduces noise into alternate path length measurements in several
other topologies as well. For this reason, we have opted to measure
the alternate path length using hopcount. While IGP metrics may be
adjusted by the network operator for a number of reasons (e.g.
traffic engineering), the hopcount is a fairly stable measurement of
 path length. As shown in the last three columns of Figure 27, the
+ path length. As shown in the last three columns of Figure 28, the
hopcountbased alternate path lengths for topology T208 are fairly
wellbehaved.
 Figure 28, Figure 29, Figure 30, and Figure 31 present the hopcount
+ Figure 29, Figure 30, Figure 31, and Figure 32 present the hopcount
based path length results for the 19 topologies examined. The
topologies in the four tables are grouped based on the size of the
 topologies, as measured by the number of nodes, with Figure 28 having
 the smallest topologies and Figure 31 having the largest topologies.
+ topologies, as measured by the number of nodes, with Figure 29 having
+ the smallest topologies and Figure 32 having the largest topologies.
Instead of trying to represent the path lengths of a large set of
alternates with a single number, we have chosen to present a
histogram of the path lengths for each IPFRR method and alternate
selection policy studied. The first eight colums of data represent
the percentage of failure scenarios protected by an alternate N hops
longer than the primary path, with the first column representing an
alternate 0 or 1 hops longer than the primary path, all the way up
through the eighth column respresenting an alternate 14 or 15 hops
longer than the primary path. The last column in the table gives the
percentage of failure scenarios for which there is no alternate less
@@ 2000,21 +2088,21 @@
 MRT_LOWPOINT_ONLY  58 27 11 3 1    
+++++++++++
 T205(avg primary hops=3.4)          
 OPTIMAL  92 8       
 NP_LLFA  89 3       8
 NP_LLFA_THEN_NP_RLFA  90 4       7
 NP_LLFA_THEN_MRT_LOWPOINT  91 9       
 MRT_LOWPOINT_ONLY  62 33 5 1     
+++++++++++
 Figure 28
+ Figure 29
++
  percentage of failure scenarios 
 Topology name  protected by an alternate N hops 
 and  longer than the primary path 
 alternate selection ++
 policy evaluated          no 
      10 12 14  alt
 0123456789111315 <16
+++++++++++
@@ 2047,21 +2135,21 @@
 MRT_LOWPOINT_ONLY  63 29 8      
+++++++++++
 T210(avg primary hops=2.5)          
 OPTIMAL  95 4 1      
 NP_LLFA  94 1       5
 NP_LLFA_THEN_NP_RLFA  94 3 1      2
 NP_LLFA_THEN_MRT_LOWPOINT  95 4 1      
 MRT_LOWPOINT_ONLY  91 6 2      
+++++++++++
 Figure 29
+ Figure 30
++
  percentage of failure scenarios 
 Topology name  protected by an alternate N hops 
 and  longer than the primary path 
 alternate selection ++
 policy evaluated          no 
      10 12 14  alt
 0123456789111315 <16
+++++++++++
@@ 2094,21 +2182,21 @@
 MRT_LOWPOINT_ONLY  30 20 18 12 8 4 3 2 3
+++++++++++
 T215(avg primary hops=4.8)          
 OPTIMAL  73 27       
 NP_LLFA  73 11       16
 NP_LLFA_THEN_NP_RLFA  73 13 2      12
 NP_LLFA_THEN_MRT_LOWPOINT  74 19 3 2 1 1 1  
 MRT_LOWPOINT_ONLY  32 31 16 12 4 3 1  
+++++++++++
 Figure 30
+ Figure 31
++
  percentage of failure scenarios 
 Topology name  protected by an alternate N hops 
 and  longer than the primary path 
 alternate selection ++
 policy evaluated          no 
      10 12 14  alt
 0123456789111315 <16
+++++++++++
@@ 2134,21 +2222,21 @@
 MRT_LOWPOINT_ONLY  37 29 21 10 3 1   
+++++++++++
 T219(avg primary hops=7.7)          
 OPTIMAL  77 15 5 1 1    
 NP_LLFA  72 5       22
 NP_LLFA_THEN_NP_RLFA  73 8 2      16
 NP_LLFA_THEN_MRT_LOWPOINT  74 8 3 3 2 2 2 2 4
 MRT_LOWPOINT_ONLY  19 14 15 12 10 8 7 6 10
+++++++++++
 Figure 31
+ Figure 32
In the preceding analysis, the following procedure for selecting an
RLFA was used. Nodes were ordered with respect to distance from the
source and checked for membership in Q and Pspace. The first node
to satisfy this condition was selected as the RLFA. More
sophisticated methods to select nodeprotecting RLFAs is an area of
active research.
The analysis presented above uses the MRT Lowpoint Algorithm defined
in this specification with a common GADAG root. The particular
@@ 2162,21 +2250,21 @@
chosen based on the GADAG Root Selection Priority advertised by each
router, the values of which would be determined offline.
In order to measure how sensitive the MRT alternate path lengths are
to the choice of common GADAG root, we performed the same analysis
using different choices of GADAG root. All of the nodes in the
network were ordered with respect to the node centrality as computed
above. Nodes were chosen at the 0th, 25th, and 50th percentile with
respect to the centrality ordering, with 0th percentile being the
most central node. The distribution of alternate path lengths for
 those three choices of GADAG root are shown in Figure 32 for a subset
+ those three choices of GADAG root are shown in Figure 33 for a subset
of the 19 topologies (chosen arbitrarily). The third row for each
topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the
results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth
rows show the alternate path length distibution for the 25th and 50th
percentile choice for GADAG root. One can see some impact on the
path length distribution with the less central choice of GADAG root
resulting in longer path lenghths.
We also looked at the impact of MRT algorithm variant on the
alternate path lengths. The first two rows for each topology present
@@ 2232,21 +2320,21 @@
 MRT_LOWPOINT (50 percentile)  19 14 13 10 8 6 5 5 10
+++++++++++
 T219(avg primary hops=7.7)          
 MRT_HYBRID ( 0 percentile)  20 16 13 10 7 5 5 5 3
 MRT_SPF ( 0 percentile)  31 23 19 12 7 4 2 1 
 MRT_LOWPOINT ( 0 percentile)  19 14 15 12 10 8 7 6 10
 MRT_LOWPOINT (25 percentile)  19 14 15 13 12 10 6 5 7
 MRT_LOWPOINT (50 percentile)  19 14 14 12 11 8 6 6 10
+++++++++++
 Figure 32
+ Figure 33
8. Implementation Status
[RFC Editor: please remove this section prior to publication.]
Please see [ID.ietfrtgwgmrtfrrarchitecture] for details on
implementation status.
9. Algorithm Work to Be Done
@@ 2268,72 +2356,79 @@
12. Security Considerations
This architecture is not currently believed to introduce new security
concerns.
13. References
13.1. Normative References
[ID.ietfrtgwgmrtfrrarchitecture]
 Atlas, A., Kebler, R., Bowers, C., Enyedi, G., Csaszar,
 A., Tantsura, J., Konstantynowicz, M., and R. White, "An
 Architecture for IP/LDP FastReroute Using Maximally
 Redundant Trees", draftrtgwgmrtfrrarchitecture04
 (work in progress), July 2014.
+ Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
+ A., Tantsura, J., and R. White, "An Architecture for IP/
+ LDP FastReroute Using Maximally Redundant Trees", draft
+ ietfrtgwgmrtfrrarchitecture05 (work in progress),
+ January 2015.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
13.2. Informative References
[EnyediThesis]
Enyedi, G., "Novel Algorithms for IP Fast Reroute",
Department of Telecommunications and Media Informatics,
Budapest University of Technology and Economics Ph.D.
Thesis, February 2011, .
 [ID.atlasmplsldpmrt]
 Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ.
 Wijnands, "LDP Extensions to Support Maximally Redundant
 Trees", draftatlasmplsldpmrt01 (work in progress),
 July 2014.
+ [ID.farkasisispcr]
+ Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., and P.
+ AshwoodSmith, "ISIS Path Computation and Reservation",
+ draftfarkasisispcr01 (work in progress), December
+ 2014.
 [ID.atlasospfmrt]
 Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF
 Extensions to Support Maximally Redundant Trees", draft
 atlasospfmrt02 (work in progress), July 2014.
+ [ID.ietfisismrt]
+ Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J.
+ Tantsura, "Intermediate System to Intermediate System (IS
+ IS) Extensions for Maximally Redundant Trees (MRT)",
+ draftietfisismrt00 (work in progress), February 2015.
+
+ [ID.ietfmplsldpmrt]
+ Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and
+ I. Wijnands, "LDP Extensions to Support Maximally
+ Redundant Trees", draftietfmplsldpmrt00 (work in
+ progress), January 2015.
+
+ [ID.ietfospfmrt]
+ Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li,
+ "OSPF Extensions to Support Maximally Redundant Trees",
+ draftietfospfmrt00 (work in progress), January 2015.
[ID.ietfrtgwgipfrrnotviaaddresses]
Bryant, S., Previdi, S., and M. Shand, "A Framework for IP
and MPLS Fast Reroute Using Notvia Addresses", draft
ietfrtgwgipfrrnotviaaddresses11 (work in progress),
May 2013.
[ID.ietfrtgwglfamanageability]
Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and P. Sarkar, "Operational management of
Loop Free Alternates", draftietfrtgwglfa
 manageability07 (work in progress), January 2015.
+ manageability08 (work in progress), March 2015.
[ID.ietfrtgwgremotelfa]
Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
 So, "Remote LoopFree Alternate Fast ReRoute", draft
 ietfrtgwgremotelfa10 (work in progress), January 2015.

 [ID.liisismrt]
 Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J.
 Tantsura, "Intermediate System to Intermediate System (IS
 IS) Extensions for Maximally Redundant Trees(MRT)", draft
 liisismrt01 (work in progress), July 2014.
+ So, "Remote LoopFree Alternate (LFA) Fast ReRoute
+ (FRR)", draftietfrtgwgremotelfa11 (work in progress),
+ January 2015.
[Kahn_1962_topo_sort]
Kahn, A., "Topological sorting of large networks",
Communications of the ACM, Volume 5, Issue 11 , Nov 1962,
.
[LFARevisited]
Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP
Fast ReRoute: Loop Free Alternates Revisited", Proceedings
of IEEE INFOCOM , 2011,
@@ 2350,20 +2445,24 @@
Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
Maximally Redundant Trees in Strictly Linear Time", IEEE
Symposium on Computers and Comunications (ISCC) , 2009,
.
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D.
McPherson, "OSPF Stub Router Advertisement", RFC 3137,
June 2001.
+ [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "MISIS: Multi
+ Topology (MT) Routing in Intermediate System to
+ Intermediate Systems (ISISs)", RFC 5120, February 2008.
+
[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast
Reroute: LoopFree Alternates", RFC 5286, September 2008.
[RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC
5714, January 2010.
[RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B.,
Uttaro, J., Leymann, N., and M. Horneffer, "LoopFree
Alternate (LFA) Applicability in Service Provider (SP)
Networks", RFC 6571, June 2012.
@@ 2404,21 +2503,21 @@
UNDIRECTED) already specified for each interface.
Mod_SPF(spf_root, block_root)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
found_in_gadag = false
while (spf_heap is not empty) and (found_in_gadag is false)
min_node = remove_lowest(spf_heap)
 if min_node.IN_GADAG is true
+ if min_node.IN_GADAG
found_in_gadag = true
else
foreach interface intf of min_node
if ((intf.OUTGOING or intf.UNDIRECTED) and
((intf.remote_node.localroot is block_root) or
(intf.remote_node is block_root)) and
(intf.remote_node is not TEMP_UNUSABLE) and
(intf is not TEMP_UNUSABLE))
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
@@ 2441,27 +2540,27 @@
y.local_node.IN_GADAG = true
y = y.local_node.spf_prev_intf
if(method is not hybrid)
Set_Ear_Direction(ear_list, cand_intf.local_node,
end_ear,block_root)
Clear TEMP_UNUSABLE from all interfaces between
cand_intf.remote_node and cand_intf.local_node
Clear TEMP_UNUSABLE from cand_intf.local_node
return end_ear
 Figure 33: Modified SPF for GADAG computation
+ Figure 34: Modified SPF for GADAG computation
Assume that an ear is found by going from y to x and then running an
SPF that terminates by minimizing z (e.g. y<>x...q<>z). Now it is
necessary to determine the direction of the ear; if y << z, then the
path should be y>x...q>z but if y >> z, then the path should be y<
 x...q<z. In Section 5.4, the same problem was handled by finding
+ x...q<z. In Section 5.5, the same problem was handled by finding
all ears that started at a node before looking at ears starting at
nodes higher in the partial order. In this algorithm, using that
approach could mean that new ears aren't added in order of their
total cost since all ears connected to a node would need to be found
before additional nodes could be found.
The alternative is to track the order relationship of each node with
respect to every other node. This can be accomplished by maintaining
two sets of nodes at each node. The first set, Higher_Nodes,
contains all nodes that are known to be ordered above the node. The
@@ 2504,58 +2603,58 @@
add i.local_node to x.Higher_Nodes
else
foreach node x where x.localroot is block_root
if end_b is in x.Lower_Nodes
foreach interface i in ear_list
add i.local_node to x.Lower_Nodes
if end_a is in x.Higher_Nodes
foreach interface i in ear_list
add i.remote_node to x.Higher_Nodes
 Figure 34: Algorithm to assign links of an ear direction
+ Figure 35: Algorithm to assign links of an ear direction
A goal of the algorithm is to find the shortest cycles and ears. An
ear is started by going to a neighbor x of an IN_GADAG node y. The
path from x to an IN_GADAG node is minimal, since it is computed via
SPF. Since a shortest path is made of shortest paths, to find the
shortest ears requires reaching from the set of IN_GADAG nodes to the
closest node that isn't IN_GADAG. Therefore, an ordered tree is
maintained of interfaces that could be explored from the IN_GADAG
nodes. The interfaces are ordered by their characteristics of
metric, local loopback address, remote loopback address, and ifindex,
as in the algorithm previously described in Figure 14.
The algorithm ignores interfaces picked from the ordered tree that
belong to the block root if the block in which the interface is
present already has an ear that has been computed. This is necessary
since we allow at most one incoming interface to a block root in each
block. This requirement stems from the way nexthops are computed as
 was seen in Section 5.6. After any ear gets computed, we traverse
+ was seen in Section 5.7. After any ear gets computed, we traverse
the newly added nodes to the GADAG and insert interfaces whose far
end is not yet on the GADAG to the ordered tree for later processing.
Finally, cutlinks are a special case because there is no point in
doing an SPF on a block of 2 nodes. The algorithm identifies cut
links simply as links where both ends of the link are cutvertices.
Cutlinks can simply be added to the GADAG with both OUTGOING and
INCOMING specified on their interfaces.
add_eligible_interfaces_of_node(ordered_intfs_tree,node)
for each interface of node
if intf.remote_node.IN_GADAG is false
insert(intf,ordered_intfs_tree)
check_if_block_has_ear(x,block_id)
block_has_ear = false
for all interfaces of x
 if (intf.remote_node.block_id == block_id) &&
 (intf.remote_node.IN_GADAG is true)
+ if ( (intf.remote_node.block_id == block_id) &&
+ intf.remote_node.IN_GADAG )
block_has_ear = true
return block_has_ear
Construct_GADAG_via_SPF(topology, root)
Compute_Localroot (root,root)
Assign_Block_ID(root,0)
root.IN_GADAG = true
add_eligible_interfaces_of_node(ordered_intfs_tree,root)
while ordered_intfs_tree is not empty
cand_intf = remove_lowest(ordered_intfs_tree)
@@ 2585,21 +2684,21 @@
cand_intf.remote_node,
cand_intf.remote_node.localroot,
SPF method)
y = ear_end.spf_prev_hop
while y.local_node is not cand_intf.local_node
add_eligible_interfaces_of_node(
ordered_intfs_tree,
y.local_node)
y = y.local_node.spf_prev_intf
 Figure 35: SPFbased GADAG algorithm
+ Figure 36: SPFbased GADAG algorithm
Appendix B. Option 3: Computing GADAG using a hybrid method
In this option, the idea is to combine the salient features of the
lowpoint inheritance and SPF methods. To this end, we process nodes
as they get added to the GADAG just like in the lowpoint inheritance
by maintaining a stack of nodes. This ensures that we do not need to
maintain lower and higher sets at each node to ascertain ear
directions since the ears will always be directed from the node being
processed towards the end of the ear. To compute the ear however, we
@@ 2614,21 +2713,21 @@
of an ear is predetermined. Thus, whenever the block already has an
ear computed, and we are processing an interface of the block root,
we mark the block root as unusable before the SPF run that computes
the ear. This ensures that the SPF terminates at some node other
than the blockroot. This in turn guarantees that the blockroot has
only one incoming interface in each block, which is necessary for
correctly computing the nexthops on the GADAG.
As in the SPF gadag, bridge ears are handled as a special case.
 The entire algorithm is shown below in Figure 36
+ The entire algorithm is shown below in Figure 37
find_spf_stack_ear(stack, x, y, xy_intf, block_root)
if L(y) == D(y)
// Special case for cutlinks
xy_intf.UNDIRECTED = false
xy_intf.remote_intf.UNDIRECTED = false
xy_intf.OUTGOING = true
xy_intf.INCOMING = true
xy_intf.remote_intf.OUTGOING = true
xy_intf.remote_intf.INCOMING = true
@@ 2664,21 +2763,21 @@
root.IN_GADAG = true
Initialize Stack to empty
push root onto Stack
while (Stack is not empty)
x = pop(Stack)
for each interface intf of x
y = intf.remote_node
if y.IN_GADAG is false
find_spf_stack_ear(stack, x, y, intf, y.block_root)
 Figure 36: Hybrid GADAG algorithm
+ Figure 37: Hybrid GADAG algorithm
Authors' Addresses
Gabor Sandor Enyedi (editor)
Ericsson
Konyves Kalman krt 11
Budapest 1097
Hungary
Email: Gabor.Sandor.Enyedi@ericsson.com