Subject: Comments on Algorithm description in draft-ietf-rtgwg-ipfrr-spec-base-09

From: Stewart Bryant <[email-masked]>
Date: Wed, 03 Oct 2007 15:12:46 +0100

Alia

We have taken a look at the algorithm in section 3.6 of
 draft-ietf-rtgwg-ipfrr-spec-base-09, and there are a
number of cases where some clarification is needed to aid
understanding.

The root problem is that you have an object oriented
description of the algorithm but have not always defined
the objects.

Please see below.

We will also provide comments on the draft itself in another email.

Mike & Stewart

======begin=====

   S is the computing router and has candidate next-hops H_1 through
   H_k. 

SB> You need to define a candidate next hop before you can say a router
SB> has them (i.e. move the definition earlier)
 
   N_i and N_j are used to refer to neighbors of S. For a next-hop
   to be a candidate, the next-hop must be associated with a bi-
   directional link, as is determined by the IGP. 

SB> I think you want to say:
SB> S is the computing router
SB> S has neighbours N_1 to N_j
SB> The candidate next hops H_1 to H_k are the subset of N that are
SB> bidirectionally connected to S.

SB> Why does H_i have to be bidirectionally connected?

   For a particular
   destination router D, let S have already computed D_opt(S, D), and
   for each neighbor N_i, D_opt(N_i, D), D_opt(N_i, S), and D_opt(N_i,

SB> Why is this N_i and not H_i?

   N_j), the distance from N_i to each other neighbor N_j, and the set
   of SRLGs traversed by the path D_opt(N_i, D).  S should follow the
   below procedure for every primary next-hop selected to reach D. This
   set of primary next-hops is represented P_1 to P_p.  This procedure
   finds the alternate next-hop(s) for P_i.

SB> In the text so far X_i refers  to the node  itself, i.e. what you later
SB> appear to call X_i.neighbor. This is confusing

   First, initialize the alternate information for P_i as follows:

      P_i.alt_next_hops = {}
      P_i.alt_type = NONE
      P_i.alt_link-protect = FALSE
      P_i.alt_node-protect = FALSE
      P_i.alt_srlg-protect = {}

   For each candidate next-hop H_h,

   1.   Initialize variables as follows:

           cand_type = NONE
           cand_link-protect = FALSE
           cand_node-protect = FALSE
           cand_srlg-protect = {}

   2.   If H_h is P_i, skip it and continue to the next candidate next-
        hop.

   3.   If H_h.link is administratively allowed to be used as an
        alternate,

SB> You need to define H_h.link. Do you mean the link
SB> between S and H_h, and can their be multiple links
SB> between S and H?

           and the cost of H_h.link is less than the maximum,
           and the reverse cost of H_h is less than the maximum,
           and H_h.neighbor is not overloaded (for ISIS),
           and H_h.link is bi-directional,

SB> H_h is already defined to be bidirectional - why is this is test
SB> condition?

        then H_h can be considered as an alternate.  Otherwise, skip it
        and continue to the next candidate next-hop.

   4.   If D_opt( H_h.neighbor, D) >= D_opt( H_h.neighbor, S) + D_opt(S,
        D), then H_h is not loop-free.  Skip it and continue to the next
        candidate next-hop.

SB> You need to define H_h.neighbour. Does it just mean the node
SB> H_h? In which case, why is it different from H_h?

   5.   cand_type = LOOP-FREE.

   6.   If H_h is a primary next-hop, set cand_type to PRIMARY.

   7.   If H_h.link is not P_i.link, set cand_link-protect to TRUE.

   8.   If D_opt(H_h.neighbor, D) < D_opt(H_h.neighbor, P_i.neighbor) +
        D_opt(P_i.neighbor, D), set cand_node-protect to TRUE.

SB> You need to define P_i.neighbour

   9.   If the router considers SRLGs, then set the cand_srlg-protect to
        the set of SRLGs traversed on the path from S via P_i to

SB> Does this mean S via Pi.link to P_i.neighbour?

        P_i.neighbor.  Remove the set of SRLGs to which H_h belongs from
        cand_srlg-protect.  Remove from cand_srlg-protect the set of
        SRLGs traversed on the path from H_h.neighbor to D. Now
        cand_srlg-protect holds the set of SRLGs to which P_i belongs
        and that are not traversed on the path from S via H_h to D.

   10.  If cand_type is PRIMARY, the router prefers other primary next-
        hops for use as the alternate, and the P_i.alt_type is not
        PRIMARY, goto Step 19.

   11.  If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE,
        goto Paragraph 19.

   12.  If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE,
        goto Step 19.

   13.  If cand_srlg-protect has a better set of SRLGs than
        P_i.alt_srlg-protect, goto Step 19.

   14.  If cand_srlg-protect is different from P_i.alt_srlg-protect,
        then select between H_h and P_i.alt_next_hops based upon
        distance, IP addresses, or any router-local tie-breaker.  If H_h
        is preferred, then goto Step 19.  Otherwise, skip H_h and
        continue to the next candidate next-hop.

SB> The nesting of the IF then ELSE statements in step 14 is not clear.

   15.  If D_opt(H_h.neighbor, D) < D_opt(P_i.neighbor, D) and
        D_opt(P_i.alt_next_hops, D) >= D_opt(P_i.neighbor, D), then H_h
        is a downstream alternate and P_i.alt_next_hops is simply an
        LFA.  Prefer H_h and goto Step 19.

   16.  Based upon the alternate types, the alternate distances, IP
        addresses, or other tie-breakers, decide if H_h is preferred to
        P_i.alt_next_hops.  If so, goto Step 19.

   17.  Decide if P_i.alt_next_hops is preferred to H_h.  If so, then
        skip H_h and continue to the next candidate next-hop.

   18.  Add H_h into P_i.alt_next_hops.  Set P_i.alt_type to the better
        type of H_h.alt_type and P_i.alt_type.  Continue to the next
        candidate next-hop.

   19.  Replace the P_i alternate next-hop set with H_h as follows:

           P_i.alt_next_hops = {H_h}
           P_i.alt_type = cand_type
           P_i.alt_link-protect = cand_link-protect
           P_i.alt_node-protect = cand_node-protect
           P_i.alt_srlg-protect = cand_srlg-protect

        Continue to the next candidate next-hop.

========end======

_______________________________________________
rtgwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rtgwg

---

From: "Alia Atlas" <[email-masked]>
Date: Thu, 25 Oct 2007 11:25:32 -0400

Stewart,

Thanks for the careful read and good comments; sorry for taking so long to
respond - I've been traveling & sick.

> SB> bidirectionally connected to S.

This is almost correct - a next-hop includes not just the neighbor but also
the outgoing interface.  There can be multiple candidate next-hops that
refer to
the same neighbor N_i.

Just because bidirectional connectivity is required in OSPF/ISIS for a link
to be usable.   I think that is more a sanity-check that both ends of the
link
have the same database - and I see no reason to vary from it here.
Do you disagree?

   For a particular
> SB> Why is this N_i and not H_i?

A next-hop is the (outgoing interface,  N_i) pair.  The distance computed is
to
the neighbor N_i and need not go through the outgoing interface associated
with
H_i.

> SB> appear to call X_i.neighbor. This is confusing

I'm not sure exactly what you mean here (since there aren't any X_i in the
text).
Is this the confusion between a neighbor N_i and a next-hop H_i that
contains
(outgoing interface, neighbor)?

Does replacing the following paragraph

"S is the computing router and has candidate next-hops H_1 through
   H_k.  N_i and N_j are used to refer to neighbors of S. For a next-hop
   to be a candidate, the next-hop must be associated with a bi-
   directional link, as is determined by the IGP."

with

"S is the computing router.  S has neighbors N_1 to N_j.  A
candidate next-hop is indicated by (outgoing link, neighbor) and
the outgoing link must be bidirectionally connected, as is
determined by the IGP.  The candidate next-hops of S are enumerated as
H_1 through H_k."

help?

> SB> between S and H_h, and can their be multiple links

Does explaining that a next-hop is a (outgoing link, neighbor) pair earlier
in the modified paragraph help?

> SB> H_h is already defined to be bidirectional - why is this is test

I want the algorithm to capture all the conditions; the other was just the
text
defining what are valid candidate next-hops.  I think it is clearer to have
all the conditions
in one place rather than scattered; I could remove this condition from the
earlier text if that
would be preferable.

> SB> H_h? In which case, why is it different from H_h?

Again, H_h is a next-hop so (outgoing link, neighbor)

> SB> You need to define P_i.neighbour

P_i is a primary next-hop and next-hops are (outgoing link, neighbor).

> SB> Does this mean S via Pi.link to P_i.neighbour?

yes - fixed

> SB> The nesting of the IF then ELSE statements in step 14 is not clear.

I changed the "Otherwise," to "If P_i.alt_next_hops is preferred,"

Alia