Task #1871
closed
Best Route Strategy version 2: recognize consumer retransmission
100%
Description
Develop a forwarding strategy that recognizes and reacts to consumer retransmission.
One common weakness of best-route, broadcast, and ncc strategies is:
After Interest is forwarded to one or more upstreams, no more retries will be made until the InterestLifetime expires.
Although the consumer app may retransmit the Interest, those retransmissions are ignored.
This design is believed to make those strategies (and also ccnd) vulnerable to packet loss, and thus unsuitable for usage over UDP tunnels across Interest.
This Task is to design and implement a simple forwarding strategy that recognizes downstream retransmissions.
If a consumer suspects there's an Interest or Data loss, it can retransmit the Interest, and such a retransmission should trigger the strategy to try an alternate path or a previously used path.
However, to avoid sending too many Interests, a retransmission will trigger another forwarding only if it's at least one RTT apart from the previous forwarding.
An opposite view is that, the strategy should retry alternate or same path all the time until InterestLifetime expires.
However, this design is unsuitable for nodes except end hosts, because the downstream node may already have received the Data via another path, and retries are unnecessary.
An explicit retransmission or retry from the downstream signals that the downstream still needs the Data.
Updated by Junxiao Shi over 10 years ago
I'll mock up a simple implementation for evaluation. After that, we can decide whether it should go with v0.2 or v0.3.
Updated by Junxiao Shi over 10 years ago
The specific design for this strategy is:
afterReceiveInterest
(not violating scope) /------\
(not duplicate Nonce) / is new \
------------------------> PIT |---Y---> forward to nexthop with lowest routing cost
\ entry? / (except downstream)
\------/
|
N
|
v
/--------\
/ is last \---Y---> suppress
/ outgoing \
| Interest |
\ within /
\ 100ms ? /---N---> forward to unused nexthop with
\--------/ lowest routing cost, or start over
if every nexthop is used
(except current downstream)
Since the strategy uses nexthops one by one, I suggest the name one-by-one.
Updated by Junxiao Shi over 10 years ago
- Status changed from New to In Progress
I'm coding on release-0.2.0 branch because it contains more bugfixes, but the target version of this strategy should be decided based on test results.
Updated by Junxiao Shi over 10 years ago
- % Done changed from 0 to 40
According to Beichuan's suggestion, this strategy will be named Best Route version 2, and the NDN Name would be ndn:/ndn:/localhost/nfd/strategy/best-route/%FD%02.
#1893 will allow this strategy to be chosen by ndn:/ndn:/localhost/nfd/strategy/best-route, but the full strategy Name is required for now.
Updated by Junxiao Shi over 10 years ago
- Status changed from In Progress to Resolved
- % Done changed from 40 to 100
Evaluation version is completed.
Updated by Junxiao Shi over 10 years ago
- Subject changed from Strategy that recognizes consumer retransmission to Best Route Strategy version 2: recognize consumer retransmission
- Target version set to v0.2
20140820 conference call decides to include the strategy in v0.2, given that it doesn't change the behavior of best-route except when consumer retransmits.
Since #1893 won't be included in v0.2, we will rename version 2 as ndn:/ndn:/localhost/nfd/strategy/best-route, and rename version 1 as ndn:/ndn:/localhost/nfd/strategy/best-route/%FD%01, so that an unversioned strategy Name selects the new strategy.
We need to run integration tests on the new strategy (currently blocked by #1895). If there's major issue, we may retarget this Task to v0.3.
Updated by Alex Afanasyev over 10 years ago
I have a small concern about this plan. BestRoute is default strategy, but it is default only on user machines. As of right now, on the testbed we are not using BestRoute for any prefixes: we use broadcast for /ndn/broadcast and ncc for everything else.
Unless we provide the same mechanism for ncc, this will not provide a complete solution for communication that involve testbed.
Not directly related question. Can this be implemented as a mechanism that can be "plugged-in" into any strategy instead of requiring to make a new strategy? Wild idea, strategy selection can allow to pass "options" for fine tuning the strategy.
Updated by Junxiao Shi over 10 years ago
- Private changed from No to Yes
I have no plan for NCC new version. NCC is a precise reproduction of CCNx 7002.
Testbed needs NCC because it's the only strategy that can retry on multiple faces.
In v0.3 one or more new strategy will be designed for testbed routers (Task #1901).
Pluggable, combinable strategy behavior is a research question that hasn't been explored. I discussed this Beichuan in Spring 2013 but there's no outcome.
Parameterized strategy choice is possible but not necessary in current strategies.
Best Route version 2 has a MIN_RETRANSMISSION_DURATION parameter, but it should be made adaptive in a future version.
Updated by Beichuan Zhang over 10 years ago
As I mentioned during yesterday's call, while this feature has improved UDP performance, there're a few issues going forward.
The default strategy on testbed hubs is ncc, which doesn't have this feature. But it supports forwarding interests to multiple nexthops, which helps deal with packet loss. The BestRoute strategy supports retx but only a single path at a time.
Similar situation to broadcast, supporting multipath but no retx.
To take advantage of this feature, the consumer app or library needs to initiate retx.
Ideally we should have a default strategy that supports both multipath and retx. How much time is needed to get a simple one going?
Updated by Junxiao Shi over 10 years ago
- Status changed from Resolved to Closed
Developer Guide is updated to reflect version 2 behavior.
According to Beichuan suggestion, version 1 can be kept in code, but it shouldn't be described in any documentation.
Updated by Alex Afanasyev over 10 years ago
I have updated PDF document on named-data.net website (it has the same name/link and includes new revision information).