Feature #1697
closed
Calculate FIB cost as the lowest cost among all inherited Routes
0%
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)
Updated by Junxiao Shi over 10 years ago
- Description updated (diff)
RibMgmt revision 6 reflects this choice.
Updated by Junxiao Shi about 10 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
Updated by Junxiao Shi about 10 years ago
- Blocked by Feature #1941: FibUpdater added
Updated by Junxiao Shi about 9 years ago
- Target version changed from v0.3 to v0.5
Vince suggests putting this to v0.5 target at 20151110 conference call.
Updated by
Updated by Muktadir Chowdhury over 8 years ago
- Assignee set to Muktadir Chowdhury
Updated by Junxiao Shi over 7 years ago
- Tracker changed from Task to Feature
- Target version changed from v0.5 to v0.6
Updated by Muktadir Chowdhury over 7 years ago
- Assignee changed from Muktadir Chowdhury to Nicholas Gordon
Updated by Nicholas Gordon over 7 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.
Updated by Junxiao Shi over 7 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:
- Clone the parent FIB entry.
- For each route in parent RIB entry, if the route is tagged CHILD_INHERIT=no, delete the FIB nexthop record.
- 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.
Updated by Davide Pesavento almost 7 years ago
- Target version changed from v0.6 to v0.7
Updated by Junxiao Shi over 4 years ago
2020-03-12 NFD call decides to reject this issue.
RibMgmt rev30 reflects this choice.