Bug #4262
closed
Interest processing takes long time if name has many components
Added by Junxiao Shi about 7 years ago.
Updated over 6 years ago.
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.
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.
I would propose much simpler approach - limit the number of name components that NFD processes by, say, 50 or less.
- 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.
- % 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.
Have you determined what the bottleneck is?
- % 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.
- % Done changed from 30 to 40
- Target version changed from v0.6 to v0.7
- % 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.
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.
- % Done changed from 50 to 60
- % Done changed from 60 to 70
- Status changed from In Progress to Code review
- % Done changed from 70 to 100
- Status changed from Code review to Closed
Also available in: Atom
PDF
Updated by 
Updated by 
Updated by