Project

General

Profile

Actions

Feature #1913

closed

RetransmissionSuppression: exponential back-off

Added by Alex Afanasyev about 10 years ago. Updated almost 9 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Forwarding
Target version:
Start date:
Due date:
% Done:

100%

Estimated time:
6.00 h

Description

Currently, BestRoute v2 strategy uses a fixed time interval to suppress any potential retransmissions from client side.
This is used to prevent accidental/malicious clients from sending Interest end-to-end.

However, fixing the interval removes ability for low-RTT communication to retrieve data when losses happen.

Enabling RTT estimation could be a potential option, but given that this estimation would never be reliable (even if granularity of the estimation was Data packet), multi-path nature of Interest forwarding and caches would make such estimation close to useless).
Another point against using RTT is that the clients themselves be using RTT estimation to detect losses, which results in double-control loop and potentially unstable behavior.

Alternative and simpler approach is to use exponential back-off approach with some short (fixed or "estimated") value.
This way, we still give the end-clients control over the retransmission, but effectively prevent abuse of the mechanism.

Detailed steps for the proposal:

  • Set INITIAL_SUPPRESSION_INTERVAL = 1ms (or even lower)

  • Define SuppressionInfo class derived from StrategyInfo to hold time::Duration and time::steady_clock::TimePoint values:

    class SuppressionInfo
    {
    ...
    public:
        time::Duration suppessionInterval;
        time::steady_clock::TimePoint suppressUntil;
    };
    
  • On incoming interest:

    • if new PIT entry

      • install SuppressionInfo on PIT entry, initializing

        suppessionInterval = INITIAL_SUPPRESSION_INTERVAL

        suppressUntil = time::steady_clock::now() + suppessionInterval

      • proceed with normal Interest processing

    • if retransmission detected

      • retrieve StrategyInfo from PIT entry
      • if suppressUntil larger or equal to time::steady_clock::now() abort processing
      • otherwise update SuppressionInfo values:

        suppessionInterval = 2 * suppessionInterval

        suppressUntil = time::steady_clock::now() + suppessionInterval

      • proceed with normal Interest processing


Related issues 2 (0 open2 closed)

Related to NFD - Bug #2621: Interest aggregation scenario: broken due to retransmission suppression changeClosedEric Newberry

Actions
Blocked by NFD - Task #2377: Abstract retransmission suppression logicClosedJunxiao Shi

Actions
Actions #1

Updated by Junxiao Shi about 10 years ago

  • Description updated (diff)
  • Assignee set to Junxiao Shi
  • Estimated time set to 6.00 h

I agree that exponential back-off is better than RTT estimation, because prefix granularity is always a problem in RTT estimation.

The definition of retransmission is doubtful: why should we care which downstream is sending a similar Interest?

The strategy can decide to suppress or to forward a similar Interest, without looking at where it comes from, because there's no fundamental difference between retransmission by same downstream or receiving a similar Interest from another downstream (which might be same consumer via different path, or different consumer requesting same content).

Actions #2

Updated by Junxiao Shi almost 10 years ago

  • Blocked by Task #2377: Abstract retransmission suppression logic added
Actions #3

Updated by Alex Afanasyev almost 10 years ago

I don't have much objections completely ignoring origin of the packet for "retransmission suppression". We can implement this way and if it will be causing problems add extra logic.

Actions #4

Updated by Junxiao Shi almost 10 years ago

  • Tracker changed from Task to Feature
  • Subject changed from Exponential back-off for retransmission action suppression interval (BestRoute v.2 strategy) to RetransmissionSuppression: exponential back-off
  • Description updated (diff)
  • Status changed from New to In Progress

The first commit under this Feature would be a RetransmissionSuppression class that supports exponential back-off.

Further commits are needed to enable the new algorithm for each strategy.

Actions #5

Updated by Junxiao Shi almost 10 years ago

  • % Done changed from 0 to 10

http://gerrit.named-data.net/1686

I'd first rename original algorithm RetransmissionSuppression to RetxSuppressionFixed, and declare API in a base class RetxSuppression.

The new algorithm will be implemented as a new subclass of RetxSuppression in the next commit.

Actions #6

Updated by Junxiao Shi almost 10 years ago

  • % Done changed from 10 to 30
Actions #7

Updated by Junxiao Shi almost 10 years ago

  • % Done changed from 30 to 60

RetransmissionSuppressionExponential is implemented.

API is now: Result decide(const Face& inFace, const Interest& interest, pit::Entry& pitEntry) const.

It accepts mutable pit::Entry reference instead of const reference, so that StrategyInfo can be attached.

Actions #8

Updated by Junxiao Shi over 9 years ago

best-route uses RetxSuppressionExponential http://gerrit.named-data.net/1805

Note: best-route becomes v3 after this semantical change. I decide to keep type name BestRouteStrategy2 instead of changing it to BestRouteStrategy3 because this '2' is just to distinguish the type from v1 which would be kept permanently for comparison purposes, and the '2' does not indicate version number.

Actions #9

Updated by Junxiao Shi over 9 years ago

  • Status changed from In Progress to Closed
  • % Done changed from 60 to 100

I'm closing this issue now.

AccessStrategy still has fixed-interval duplicate suppression. Whether to change that requires an independent decision.

Actions #10

Updated by Junxiao Shi over 9 years ago

  • Related to Bug #2621: Interest aggregation scenario: broken due to retransmission suppression change added
Actions #11

Updated by Junxiao Shi almost 9 years ago

devguide is updated about exponential back-off usage in best-route in nfd-docs:commit:6c602414e63d1e14398d132e273b9b80f6feea0e.

Actions

Also available in: Atom PDF