Bug #4262
closed
Interest processing takes long time if name has many components
100%
Description
Steps to reproduce:
- Use a standalone NFD instance that is not connected to other nodes.
ndnping -c 1 $(python -c "print '/X'*2000")
Expected: ndnping client receives a Nack.
Actual: NFD spends more than 15 seconds to process this packet, and ndnping times out when InterestLifetime expires at 4000ms.
If adding -o 60000 to set a higher InterestLifetime: ndnping receives a Nack as expected.
Since NFD forwarding is single threaded, spending too much time on one packet denies other packets from accessing the forwarding engine, and causes network congestion. NFD should limit the duration of processing each packet, and drop the packet or respond with a Nack if the time limit would be exceeded.
Updated by Junxiao Shi over 7 years ago
As shown in http://www.lists.cs.ucla.edu/pipermail/nfd-dev/2017-August/002693.html, if NFD-RIB thread is trying to execute a FIB command but the forwarding thread is kept busy servicing an Interest with many name components, the FIB command would timeout, causing a (rightful) crash on NFD-RIB side.
Updated by Davide Pesavento over 7 years ago
NFD should limit the duration of processing each packet, and drop the packet or respond with a Nack if the time limit would be exceeded.
An approach based on a timer is, by definition, unfeasible. Given that NFD is single-threaded, the callback associated with the expiring timer wouldn't be executed until the current packet is fully processed, rendering the timeout useless.
Interest packets with an abnormally large number of name components should be dropped before they enter the forwarding pipeline.
Updated by Alex Afanasyev over 7 years ago
I would propose much simpler approach - limit the number of name components that NFD processes by, say, 50 or less.
Updated by Junxiao Shi over 7 years ago
- Category changed from Forwarding to Tables
- Status changed from New to In Progress
- Assignee set to Junxiao Shi
- Start date deleted (
08/27/2017) - Estimated time changed from 3.00 h to 9.00 h
20170828 NFD call decides to limit the depth of NameTree to D. Consequently:
An Interest whose name has more than D components can still be accepted.
The resulting PIT entry will be attached to the NameTree node of a name prefix of the first D component.
FIB/StrategyChoice/Measurements entries with more than D name components cannot be created.
Attempts to create FIB/StrategyChoice entries shall be rejected by management.
Measurements::get(const Name&) will return the deepest allowable Meausurements entry.
Updated by Junxiao Shi over 7 years ago
- % Done changed from 0 to 10
https://gerrit.named-data.net/4165 adds NameTree::getMaxDepth() as an advisory limit of NameTree depth.
I'll then change PIT, StrategyChoice, and FIB to conform to this depth limit, and also update RibManager to also enforce this depth limit so that it would not attempt to create a FIB entry exceeding limit.
Finally, NameTree::getMaxDepth() will become mandatory to simplify NameTree implementation.
Updated by Davide Pesavento over 7 years ago
Have you determined what the bottleneck is?
Updated by Junxiao Shi over 7 years ago
- % Done changed from 10 to 30
https://gerrit.named-data.net/4174 PIT
With this change, ndnping -c 1 $(python -c "print '/X'*2000") no longer causes long processing time in NFD.
In Pit::lookup, I recognize the opportunity to eliminate nteName variable and replace it with an argument to NameTree::lookup that replaces enforceMaxDepth. This optimization is to be performed when max depth is enforced universally.
Updated by Junxiao Shi about 7 years ago
- % Done changed from 30 to 40
https://gerrit.named-data.net/4232 StrategyChoice
Updated by Davide Pesavento about 7 years ago
- Target version changed from v0.6 to v0.7
Updated by Junxiao Shi about 7 years ago
- % Done changed from 40 to 50
https://gerrit.named-data.net/4359 Measurements
Note that the current implementation of Measurements::get with FIB/PIT entry delegates to Measurements::get(const Name&) that is inefficient. This will be refactored after max depth is enforced universally.
I also notice that NameTree::lookup(const pit::Entry&) contains an incorrect assertion. This will be fixed later in this issue.
Updated by Junxiao Shi almost 7 years ago
FIB/StrategyChoice/Measurements entries with more than D name components cannot be created.
Attempts to create FIB/StrategyChoice entries shall be rejected by management.
FibMgmt rev34 and RibMgmt rev23 and StrategyChoice rev10 define that management shall return code 414 if name prefix is too long.
Updated by Junxiao Shi almost 7 years ago
https://gerrit.named-data.net/4464 implements code 414 for rib/register command.
Updated by Junxiao Shi almost 7 years ago
- % Done changed from 50 to 60
https://gerrit.named-data.net/4500 StrategyChoiceManager
Updated by Junxiao Shi almost 7 years ago
- % Done changed from 60 to 70
https://gerrit.named-data.net/4506 FibManager 414
Updated by Junxiao Shi almost 7 years ago
- Status changed from In Progress to Code review
- % Done changed from 70 to 100
https://gerrit.named-data.net/4603 enforces MaxDepth universally and completes this issue.
Updated by Junxiao Shi almost 7 years ago
- Status changed from Code review to Closed