NFD

I doubt FIB updates can be generated by "traversing the RIB tree".

A correct set of FIB updates can be calculated from one of the following:

• RIB snapshot before update + a RIB update
• RIB snapshot before update + RIB after update
• RIB after update + FIB snapshot before update

I suggest taking the first option.
Given the RIB before update and a RIB update, apply the update to the RIB and at the same time generate an optimal set of necessary FIB updates.

A RIB update shouldn't be limited to "one register/unregister command".
Routing protocol may want to update many RIB entries at the same time.

I wanted to emphasize that only a subtree needs to be traversed, and the algorithm needs to consider a RIB update at hand.

FIB updates cannot be calculated with just a RIB tree but without RIB update.

I've been looking over route inheritance flags and was wondering if anyone could help clarify the CAPTURE flag. The description doesn't illustrate the case where a prefix has a route with the CAPTURE flag set.

For example:

Going by the description, it sounds like prefix /A/B should have its CAPTURE flag set since route /A has its CAPTURE flag set. If that's the case, does that mean:

• Interest /P can go through face 1
• Interest /A/P can go through face 2 but not face 1
• Interest /A/B/P can go through face 3 but not 1 or 2 because its CAPTURE flag is set as well

Any help would be appreciated, thanks.

Not sure if I get your question correctly, but the example shows a snippet of prefix registration entries that can be set individually. Setting a flag on one entry doesn't change any flag in children or parent entries. About your last point:
"Interest /A/B/P can go through face 3 but not 1 or 2 because its CAPTURE flag is set as well"

Interest /A/B/P will go through face 3 indeed but not because it's CAPTURE flag is set. It would go to face 3 because /A doesn't have child_inherit flag so its face cannot be used, and /A's CAPTURE flag stops /A/B/P to use "/" entry as well. Hope that answers your question.

Thanks, that helps. The reason I thought that children entries would be changed is based on this description:

CAPTURE: indicates that no shorter prefix can be used; overrides CHILD_INHERIT. This flag applies on the prefix: if any route of a prefix has this flag, the prefix will have this flag.

Does that not mean if an entry has its CAPTURE flag set, then its children would also have their capture flag set?

Vince:

The statement "CAPTURE: indicates that no shorter prefix can be used; overrides CHILD_INHERIT. This flag applies on the prefix: if any route of a prefix has this flag, the prefix will have this flag." means just for that particular prefix, not longer prefixes. The prefix (e.g., /ndn/edu/memphis) can have multiple routes. If any of those routes has this flag, the prefix has this flag set.

For your question "Does that not mean if an entry has its CAPTURE flag set, then its children would also have their capture flag set?", I think the answer is no. What Obaid said is the following: If an entry A has its CAPTURE flag set, the children cannot use the nexthop of A's ancestors. This is different from setting a child's capture flag, which means that child cannot use its own ancestors' nexthops (including A's).

For everyone: I would like to get comments on two issues and reach an agreement:

1. do you think this is correct for the CAPTURE flag: "This flag applies on the prefix: if any route of a prefix has this flag, the prefix will have this flag."? In contrast, the INHERIT flag applies only to (prefix, nexthop). Do you think this is the correct behavior for INHERIT?

2. do you think the CAPTURE flag on prefix A should block all A's children from using A's ancestors' nexthops?

Lan

Route inheritance flags have the same semantics with their counterparts in CCNx Prefix Registration Protocol, including:

The flags CCN_FORW_ADVERTISE, CCN_FORW_CAPTURE and CCN_FORW_LOCAL affect the prefix as a whole, rather than the individual registrations.

CAPTURE flag on prefix A blocks all A's child and A itself from using A's ancestors' nexthops.
This is the semantics of CAPTURE flag.

CCN_FORW_CAPTURE says that no shorter prefix may be used, overriding child-inherit bits that would otherwise make the shorter entries usable.

The effective upstreams for a RIB entry can be determined with this pseudocode:

def getUpstreams(ribEntry):
    upstreams = set();
    for nexthop in ribEntry.nexthops:
        upstreams.add(nexthop.face)
    if ribEntry.CAPTURE:
        return upstreams
    ribEntry = ribEntry.parent
    while ribEntry is not None:
        for nexthop in ribEntry.nexthops:
            if nexthop.CHILD_INHERIT:
                upstreams.add(nexthop.face)
        if ribEntry.CAPTURE
            break
    return upstreams

Thanks, the link and the pseudocode make the process much more clear.

Comments on the pseudocode in note-13:

• Procedure Create ancestor_face_list is undefined
• There's no algorithm for: changing route inheritance flags on a RIB entry, but no change on FaceEntry
• There's no algorithm for: updating Cost in FaceEntry, but no change on route inheritance flags

Protocol questions:

• If a RIB entry has two routes for the same FaceId but different Origin, and they have different Cost. What Cost should the corresponding NextHop record take?
• Given these Routes: (/A, face=1, Cost=10, CHILD_INHERIT=yes), (/A/B, face=1, Cost=20, CHILD_INHERIT=no), (/A/B/C, face=2, Cost=10, CHILD_INHERIT=yes). What Cost should the NextHop record for face 1 at FIB entry /A/B/C take?

Comments on the pseudocode in note-19:

• Algorithm 1 line 7: child is undefined
• Algorithm 2 line 7: ancestor_face_list is uninitialized if condition on line 3 is false

I didn't review other algorithms due to unresolved protocol questions.

If a RIB entry has two routes for the same FaceId but different Origin, and they have different Cost. What Cost should the corresponding NextHop record take?

perhaps the lower cost. Existing routing protocols need to address the same issue, for example: http://www.cisco.com/c/en/us/td/docs/security/asa/asa82/configuration/guide/config/route_static.html: "The distance is the administrative distance for the route. The default is 1 if you do not specify a value. Administrative distance is a parameter used to compare routes among different routing protocols. The default administrative distance for static routes is 1, giving it precedence over routes discovered by dynamic routing protocols but not directly connect routes. The default administrative distance for routes discovered by OSPF is 110. If a static route has the same administrative distance as a dynamic route, the static routes take precedence. Connected routes always take precedence over static or dynamically discovered routes." The distance here is the cost. I'm not sure what connected routes here mean. Maybe prefixes directly connected to the node.

Given these Routes: (/A, face=1, Cost=10, CHILD_INHERIT=yes), (/A/B, face=1, Cost=20, CHILD_INHERIT=no), (/A/B/C, face=2, Cost=10, CHILD_INHERIT=yes). What Cost should the NextHop record for face 1 at FIB entry /A/B/C take?

is it not 10 from /A?

perhaps the lower cost. Existing routing protocols need to address the same issue, for example: http://www.cisco.com/c/en/us/td/docs/security/asa/asa82/configuration/guide/config/route_static.html: "The distance is the administrative distance for the route. The default is 1 if you do not specify a value. Administrative distance is a parameter used to compare routes among different routing protocols. The default administrative distance for static routes is 1, giving it precedence over routes discovered by dynamic routing protocols but not directly connect routes. The default administrative distance for routes discovered by OSPF is 110. If a static route has the same administrative distance as a dynamic route, the static routes take precedence. Connected routes always take precedence over static or dynamically discovered routes." The distance here is the cost. I'm not sure what connected routes here mean. Maybe prefixes directly connected to the node.

Does this mean in the case where a route with the same face ID is registered to a namespace with a higher cost, the FIB should not be updated for that namespace?

For example:

(/a, Face=5, Cost=5, Origin=255, CHILD_INHERIT=no) is registered first, an update is generated, and the FIB now has an entry for (/a, Face=5, Cost=5).

Later, (/a, Face=5, Cost=10, Origin=0, CHILD_INHERIT=no) is registered. Should a FIB update be generated for /a, making the FIB contain (/a, Face=5, Cost=10), or should an update not be generated and the FIB remain unchanged with the entry (/a, Face=5, Cost=5)?

A proposal about which component should generate FIB updates is sent to nfd-dev list.

http://www.lists.cs.ucla.edu/mailman/private/nfd-dev/2014-June/000217.html

I invite watchers of this Task to have a look.

Comments on the algorithms in note-24:

• What does "if face is in face_list" mean? Does it require same FaceId only, same FaceId and Origin, or all fields to be equal?
• Algorithm 3 line 6: violates first answer in note-21
• Algorithm 5 line 16: ancestor_face_list is undefined if condition on line 4 is false

Vince Lehman wrote:

Does this mean in the case where a route with the same face ID is registered to a namespace with a higher cost, the FIB should not be updated for that namespace?

According to 20140624 conference call, the answer to this question is YES.

Please update algorithms to reflect this answer.

we talked about Vince's question today, and I didn't see any problem with ignoring the later registration whose cost is higher, that's why we think we should follow Lan's suggestion, unless you can think of a counter example.

I was discussing the following issue with Obaid and would like some feedback from others.

Given the routes:

• (/, face=1, Cost=10, CHILD_INHERIT=yes),
• (/a, face=1, Cost=20, CHILD_INHERIT=yes), and
• (/a/b, face=2, Cost=5, CHILD_INHERIT=no)

should the FIB look like:

Or

The above should be:

Given the routes: (/, face=1, Cost=10, CHILD_INHERIT=yes), (/a, face=1, Cost=20, CHILD_INHERIT=yes), and (/a/b, face=2, Cost=5, CHILD_INHERIT=no), should the FIB look like:

{ Name= / (Face=1, Cost=10) }

{ Name= /a (Face=1, Cost=20) }

{ Name= /a/b (Face=2, Cost=5), (Face=1, Cost=10)}

Or

{ Name= / (Face=1, Cost=10) }

{ Name= /a (Face=1, Cost=20) }

{ Name= /a/b (Face=2, Cost=5), (Face=1, Cost=20)}

an additional question is what should be the fib entry for /a:

is it

{ Name= /a (Face=1, Cost=10) } // inherit from its parent /

or

{ Name= /a (Face=1, Cost=20) } // using its own rib entry?

I don't really have an answer, since in either case there could be implications. The straightforward answer (and probably simpler to implement) is to inherit the cost from the parent entry. But this would prevent somebody to "demote" specific entry, if necessary (e.g., i know that everything to /x should be forwarded to default route, but for /x/y/z should primarily use the other route and fallback to the default when necessary. Though, the same behavior can be implemented by correctly setting the cost on the /x/y/z entry.

I think we should just select one behavior, implement, and document it. I would say there is no correct answer for this question. Select whatever is simpler.

Answer to note-30: first FIB is correct.

Answer to note-32: second choice is correct.

Why? For me this is contradictory. If first FIB is correct, then the answer to note 32 should be first one as well.

The algorithms in note-29 seems correct.

Forgot to mention that during the conference call on June 25, 2014 we have decided that version 0.2 can use any consistent logic to calculate FIB. In particular, the current code under review calculates FIB as described in the first option in note 30/31 (i.e., the cost is assigned from the first parent) and it should not be changed for the release.

The next release should update the logic to use the lowest cost for the Face, among all RIB entries allowed by the flags.

Both of these points must be documented in the developer document.