Project

General

Profile

Actions

Feature #1697

closed

Calculate FIB cost as the lowest cost among all inherited Routes

Added by Alex Afanasyev almost 10 years ago. Updated almost 4 years ago.

Status:
Rejected
Priority:
Normal
Assignee:
-
Category:
RIB
Target version:
-
Start date:
Due date:
% Done:

0%

Estimated time:
3.00 h

Description

Currently, FIB calculation uses "longest prefix match" to set cost for the Face in the FIB entry. This is demonstrated in note 31 of issue #1325, where the current implementation is depicted in a second example.

The "correct" behavior should be to determine the lowest cost for the Face among possible parent records. This should result in FIB like

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

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)

Related issues 1 (0 open1 closed)

Blocked by NFD - Feature #1941: FibUpdaterClosedVince Lehman

Actions
Actions #1

Updated by Junxiao Shi almost 10 years ago

  • Description updated (diff)

RibMgmt revision 6 reflects this choice.

Actions #2

Updated by Junxiao Shi over 9 years ago

  • Subject changed from Implement "correct" cost assignment for FIB entries when CHILD_INHERIT is active to Calculate FIB cost as the lowest cost among all inherited Routes
  • Assignee set to Vince Lehman
  • Start date deleted (06/25/2014)
  • Estimated time set to 3.00 h
Actions #3

Updated by Junxiao Shi over 9 years ago

Actions #4

Updated by Junxiao Shi over 8 years ago

  • Target version changed from v0.3 to v0.5

Vince suggests putting this to v0.5 target at 20151110 conference call.

Actions #5

Updated by Vince Lehman almost 8 years ago

  • Assignee deleted (Vince Lehman)
Actions #6

Updated by Muktadir Chowdhury over 7 years ago

  • Assignee set to Muktadir Chowdhury
Actions #7

Updated by Junxiao Shi almost 7 years ago

  • Tracker changed from Task to Feature
  • Target version changed from v0.5 to v0.6
Actions #8

Updated by Muktadir Chowdhury almost 7 years ago

  • Assignee changed from Muktadir Chowdhury to Nicholas Gordon
Actions #9

Updated by Nicholas Gordon over 6 years ago

I want to clarify a point about this, about whether the cost for a prefix with CHILD_INHERIT set applies just to immediate children that don't have CAPTURE set, or all children that don't have CAPTURE set. That is, given the routes

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

should we get

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

Or should we get

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

It seems reasonable to me that we should get the former, because we can specify a route to have CAPTURE so that inherited routes, even from all the way at the top, don't get used instead. We want to use the most efficient route possible for all prefixes, so it seems that we should pick any route that is a valid sub-prefix of the given prefix.

Actions #10

Updated by Junxiao Shi over 6 years ago

Reply to note-9: the first table is correct.

Formally, if we represent the RIB on a name hierarchy,
For the root node or a node that has CAPTURE on any route, the FIB entry has the same face+cost combinations as the RIB entry.
For any other node, given the FIB entry for its parent node, to compute the FIB entry for the current (child) node:

  1. Clone the parent FIB entry.
  2. For each route in parent RIB entry, if the route is tagged CHILD_INHERIT=no, delete the FIB nexthop record.
  3. For each route in child RIB entry, if the FIB entry has a nexthop record with the same face, update this nexthop record so that the cost is the lesser between existing nexthop record and the RIB route; if the FIB entry does not have a nexthop record with the same face, add the nexthop record.
Actions #11

Updated by Davide Pesavento about 6 years ago

  • Target version changed from v0.6 to v0.7
Actions #12

Updated by Nicholas Gordon almost 6 years ago

  • Assignee deleted (Nicholas Gordon)
Actions #13

Updated by Davide Pesavento over 4 years ago

  • Target version deleted (v0.7)
Actions #14

Updated by Junxiao Shi about 4 years ago

2020-03-12 NFD call decides to reject this issue.
RibMgmt rev30 reflects this choice.

Actions #15

Updated by Junxiao Shi almost 4 years ago

  • Status changed from New to Rejected
Actions

Also available in: Atom PDF