Project

General

Profile

Task #1325

Generate FIB updates

Added by Syed Amin over 5 years ago. Updated about 5 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
RIB
Target version:
Start date:
03/07/2014
Due date:
% Done:

100%

Estimated time:

Description

Traverse the RIB Tree and generate fib updates according to the flags.

fib_update.pdf (93.5 KB) fib_update.pdf Vince Lehman, 06/11/2014 11:36 AM
fib-updates.pdf (103 KB) fib-updates.pdf Vince Lehman, 06/20/2014 11:26 AM
fib-updates.pdf (103 KB) fib-updates.pdf Vince Lehman, 06/23/2014 12:23 PM
fib-updates.pdf (104 KB) fib-updates.pdf Vince Lehman, 06/25/2014 09:19 AM

Related issues

Related to NFD - Feature #1687: Route inheritance test scenarioClosed

History

#1 Updated by Alex Afanasyev over 5 years ago

  • Category set to RIB
  • Target version set to v0.2

#2 Updated by Junxiao Shi over 5 years ago

  • Subject changed from Generation of FIB updates to Generate FIB updates
  • Parent task deleted (#1271)

#3 Updated by Junxiao Shi over 5 years ago

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.

#4 Updated by Lan Wang over 5 years ago

  • Assignee changed from Syed Amin to Vince Lehman

I'm not sure if traversing the trie is in conflict with what you suggested. If a new RIB update changes the next hop or flag of an RIB entry, in most cases (e.g., the children inherits this nexthop) it is necessary to traverse the subtree rooted at that node to update the nexthops of the children prefixes. By the way, I am reassigning this task to Vince Lehman, another student in my group.

#5 Updated by Junxiao Shi over 5 years ago

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.

#6 Updated by Vince Lehman over 5 years ago

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:

Name Prefix nexthop FaceId CHILD_INHERIT CAPTURE
/ 1 yes no
/A 2 no yes
/A/B 3 no no

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.

#7 Updated by Syed Amin over 5 years ago

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.

#8 Updated by Vince Lehman over 5 years ago

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?

#9 Updated by Lan Wang over 5 years ago

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

#10 Updated by Junxiao Shi over 5 years ago

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

#11 Updated by Vince Lehman over 5 years ago

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

#12 Updated by Vince Lehman over 5 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 30

#13 Updated by Vince Lehman over 5 years ago

Here is the current pseudocode for applying FIB updates. I appreciate any feedback or comments.

#14 Updated by Vince Lehman over 5 years ago

  • % Done changed from 30 to 40

#15 Updated by Vince Lehman over 5 years ago

  • % Done changed from 40 to 50

#16 Updated by Vince Lehman over 5 years ago

  • % Done changed from 50 to 70

#17 Updated by Junxiao Shi over 5 years ago

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

#18 Updated by Vince Lehman over 5 years ago

  • % Done changed from 70 to 90

#19 Updated by Vince Lehman over 5 years ago

  • Procedure Create ancestor_face_list is undefined

I have added the procedure to the end of the document

  • 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

While I was writing the code, I updated the pseudocode algorithms to match these cases I had not considered.

Here is the updated pseudocode:

#20 Updated by Junxiao Shi over 5 years ago

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.

#21 Updated by Lan Wang over 5 years ago

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?

#22 Updated by Junxiao Shi over 5 years ago

  • Status changed from In Progress to Feedback

The pseudocode shall be updated to reflect the answers in note-21.

#23 Updated by Vince Lehman over 5 years ago

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)?

#25 Updated by Junxiao Shi about 5 years ago

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.

#26 Updated by Junxiao Shi about 5 years ago

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

#27 Updated by Junxiao Shi about 5 years ago

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.

#28 Updated by Beichuan Zhang about 5 years ago

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.

#29 Updated by Vince Lehman about 5 years ago

  • 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?

If a face is in a face_list, it means there is a face in the face_list that has the same FaceId and Origin.

  • Algorithm 3 line 6: violates first answer in note-21

Fixed

  • Algorithm 5 line 16: ancestor_face_list is undefined if condition on line 4 is false

Fixed

#30 Updated by Vince Lehman about 5 years ago

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:

Name (Face, Cost)
/ (1, 10)
/a (1, 20)
/a/b (2, 5), (1, 10)

Or

Name (Face, Cost)
/ (1, 10)
/a (1, 20)
/a/b (2, 5), (1, 20)

#31 Updated by Vince Lehman about 5 years ago

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)}

#32 Updated by Lan Wang about 5 years ago

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?

#33 Updated by Alex Afanasyev about 5 years ago

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.

#34 Updated by Junxiao Shi about 5 years ago

Answer to note-30: first FIB is correct.

Answer to note-32: second choice is correct.

#35 Updated by Alex Afanasyev about 5 years ago

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

#36 Updated by Junxiao Shi about 5 years ago

The algorithms in note-29 seems correct.

#37 Updated by Alex Afanasyev about 5 years ago

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.

#38 Updated by Vince Lehman about 5 years ago

  • % Done changed from 90 to 100

#39 Updated by Junxiao Shi about 5 years ago

  • Related to Feature #1687: Route inheritance test scenario added

#40 Updated by Alex Afanasyev about 5 years ago

  • Status changed from Feedback to Closed

Also available in: Atom PDF