Scalable timers for soft state protocols

One-line summary: Like the "experiments" mechanism in SRM: sender algs to dynamically control aggregate rate of soft-state refresh messages, and corresponding receiver algs to control when the state is timed out. Receiver can estimate interval either from examining start-of-round markers or from EWMA of interval and interval-deviation; neither is a "clear winner" and both require parameter tweaking.

Overview/Main Points

• Assumption: the control traffic bandwidth, rather than the refresh interval, is fixed as more senders are added.
• Argument: receivers should implicitly deduce changes in refresh interval, rather than being explicitly notified of changes. (Ed.: another "implicit approach" argument)
• Assumption: multiple "classes" of soft state traffic; authors distinguish "trigger" from "refresh" messages. (Presumably the former are "urgent" or require rapid response.)
• Simple prio scheme at senders might starve refresh traffic, so instead propose 2 alternatives:
  • Counting rounds: send some fraction of refresh state on each message; after all refresh state has been sent, that's one "round". (Receiver assumes that sender is using round-robin.) State that has not been refrshed for 3 rounds is timed out.
  • EWMA of refresh interval and its deviation. Receiver times out state based on current estimates, and updates estimates when refreshes are received. Exception: during a long burst of trigger (high-prio) traffic, don't time out any refreshable state, because it might be the case that the trigger traffic is soaking up all the control bandwidth.
• Simulated for PIM routing; various parameter tweaks, plus the constant tension between premature state timeout and using state that's too stale. Conclusion: "Both approaches ... allow the receivers to adapt to changes at the sender, so ...there is no clear winner."

Relevance

Flaws

• The distinction between trigger and refresh is not particularly well described or motivated, except with respect to the one example (PIM).
• How do senders deduce the amount of control bandwidth available? Presumably because they can see other sender's state messages, but this isn't made explicit.
• The usual tweaking needed for EWMA constant, except worse, because constants are needed for both the interval and interval-deviation estimators.