Project

General

Profile

Actions

Feature #3868

closed

Strategy parameters

Added by Junxiao Shi over 7 years ago. Updated about 7 years ago.

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

100%

Estimated time:
12.00 h

Description

In StrategyChoice and Strategy API, design a method to pass parameters to the strategy instance.

Many strategies contain parameters, such as retransmission suppression interval, range of RTT prediction, how often to probe alternate paths.
It's desirable to be able to adjust these parameters without re-compiling NFD. In an experiment environment, adjusting parameters without re-compiling allows easier experiment scheduling: the scheduling script does not need to re-compile and re-deploy NFD, but only need to run a management command or change a configuration file and then restart NFD. In a deployed environment and in particular the NDN testbed, adjusting parameters without re-compiling allows easier strategy testing: to test a different parameter on the testbed, the experimenter can request testbed operations to change the configuration, without going through the process of making a new binary package.

The parameters should be specified via StrategyChoice protocol and in NFD configuration file.
When the same strategy is used on multiple namespaces, each namespace should have its own strategy parameters.


Files

20161211164017.tgz (574 KB) 20161211164017.tgz integ 3435,1 Junxiao Shi, 12/11/2016 10:17 AM
Actions #1

Updated by Junxiao Shi over 7 years ago

I suggest keeping the parameters in the strategy name instead of creating a new field, because name should be expressive.
For example, a complete strategy name could be: /localhost/nfd/strategy/my-strategy/%FD%01/retx-suppression=fixed(10ms);retry-interval=200ms.
All parameters of a strategy are encoded into one name component. The strategy itself defines the format of this component: it can be human-readable or binary. If a binary format is used, the strategy designer should provide a command-line utility to generate the parameters component from command line options.

StrategyChoice should create one instance of the strategy class for each distinct strategy name, and associate the instance onto the namespace.
With some parameters encoding formats such as JSON, there could be multiple ways to encode the same parameters. However, it's unnecessary for StrategyChoice to normalize the parameters and merge the instances, since Strategy instances are designed to be stateless, and having multiple instances is harmless except for very little memory consumption.
It's also acceptable to have one strategy instance per strategy choice entry, regardless of whether the parameters are the same.

So far the strategy version is incremented every time there's a behavior change, and the recommendation for operators is to specify the unversioned strategy name. Once parameters are introduced, operators would have to specify versioned strategy name when parameters are used. This obviously leads to the concern of backwards compatibility whenever strategy version is incremented.
The solution to this problem is to allow the strategy itself offer backwards compatibility. A strategy class registers itself using the maximum version number. StrategyChoice instantiates the strategy class with lowest version no less than the chosen version. For example, if my-strategy v4 and v7 are installed, choosing v0-v4 instantiates v4, choosing v5-v7 instantiates v7, and choosing any higher version results in an error.

Actions #2

Updated by Anonymous over 7 years ago

Here is some related discussion on the mailing list from about a year ago:

Another way of specializing strategies is to define a parameters as part of strategy name. For example,

ndn:/localhost/nfd/strategy/broadcast/%FD%01/?param=false


Alex

On Apr 13, 2015, at 12:23 PM, Lan Wang (lanwang) lanwang@memphis.edu wrote:

Sounds like a useful feature to me in general. They can also be implemented as different strategies (see Junxiao's various best-route strategies).

Lan

On Apr 13, 2015, at 7:12 AM, Klaus Schneider klaus.schneider@uni-bamberg.de
wrote:

One immediate application example is to give the Broadcast Strategy a parameter that states if it should send out Interests with a new nonce.

A new nonce allows the broadcasted Interests to travel different paths with overlapping nodes (or reaching the same content source) without being dropped by the duplicate nonce detection. This small alteration can be very useful when the duplicate Interests are used to compensate for link problems (delay, loss) on one of the paths.

Best regards.

Hi everyone,

I think it would be a good idea to have (optional) parameters for a
forwarding strategy in order to make the design more flexible.

The CCNx prototype supports this:

> ccndc setstrategy <prefix> <strategy> [<parameters> [<lifetime>]]

Unfortunately, there is currently no such option in NFD:

> nfdc set-strategy <namespace> <strategy-name>

If you think this is reasonable, I can help with the implementation. I
am also not sure if this is the right place for such feature requests or
if I should put them up as a redmine ticket?

Thanks,
Klaus

Actions #3

Updated by Anonymous over 7 years ago

Here's some code where I added the strategy parameters in ndnSIM 2.0 (don't know the exact NFD version): https://github.com/schneiderklaus/ndnSIM/commit/f26d1ae36e5cb2f7da982f1ba70e1d297a412d54

It's probably not the cleanest code, but maybe it's a useful starting point.

Actions #4

Updated by Junxiao Shi over 7 years ago

  • Status changed from New to In Progress
  • Assignee set to Junxiao Shi
  • Target version set to v0.6
Actions #5

Updated by Junxiao Shi over 7 years ago

  • % Done changed from 0 to 10

https://gerrit.named-data.net/3431 refactors Strategy registry.

Upcoming changes:
Every strategy choice entry should have its own Strategy instance; eliminate the shared instances maintained in StrategyChoice table.
Change instantiation logic in Strategy::create according to note-1.
Add strategy parameters.

Actions #6

Updated by Junxiao Shi over 7 years ago

  • % Done changed from 10 to 20

https://gerrit.named-data.net/3435 allows StrategyChoice::insert to create a new Strategy instance for each StrategyChoice entry, for Strategy types that are registered in the registry.
Shared instances from StrategyChoice::install are still used in unit testing; they will be eliminated in another commit.

Actions #7

Updated by Davide Pesavento over 7 years ago

Junxiao Shi wrote:

https://gerrit.named-data.net/3435 allows StrategyChoice::insert to create a new Strategy instance for each StrategyChoice entry, for Strategy types that are registered in the registry.

Isn't this a major behavior change? Also, what's the increase in memory consumption after this change?

Actions #8

Updated by Junxiao Shi over 7 years ago

Both questions in note-7 are already answered in note-1.

Isn't this a major behavior change?

No, because Strategy instance is meant to be stateless, and all states should be stored in Measurements and other tables.

what's the increase in memory consumption after this change?

Neglectible, because there's no state in Strategy instance.

Actions #9

Updated by Davide Pesavento over 7 years ago

Yeah I know they're supposed to be stateless, but are they in practice? At least AccessStrategy seems to contain quite a bit of state, including an unordered_map with an instance of RttEstimator for each face...

Actions #10

Updated by Junxiao Shi over 7 years ago

Reply to note-9:

Any strategy that violates the stateless requirement is a problem of that strategy, not a problem of StrategyChoice. StrategyChoice has no obligation to accomodate an incorrect strategy design.
I actually know about that specific in AccessStrategy, but as the designer of AccessStrategy I can assure that the impact of having separate instances is negligible, because in practice AccessStrategy is used only in one StrategyChoice entry at the local testbed site prefix. Thus, this one can be changed later. AccessStrategy will soon be replaced with a self-learning strategy (in several months), so I won't update it now.

Actions #11

Updated by Anonymous over 7 years ago

Just for clarification: Is the state of the strategy supposed to be saved somewhere else than the strategy instance?

Or does the current specification simply not allow a strategy to use for example an RTT estimator?

Actions #12

Updated by Davide Pesavento over 7 years ago

Klaus Schneider wrote:

Just for clarification: Is the state of the strategy supposed to be saved somewhere else than the strategy instance?

Yes, see NFD developer's guide section 5.1.3 [Forwarding Strategy/Strategy API/Storage].

Actions #13

Updated by Anonymous over 7 years ago

Thanks! In this case, I agree with Junxiao's note-10, that this is the problem of the designer of the strategy who's going against the specification.

Actions #14

Updated by Junxiao Shi over 7 years ago

I'm trying to convert StrategyTester to support registration. The first problem I ran into is static initialization order fiasco.
I need something like NFD_REGISTER_NAMED_STRATEGY(NccStrategyTester, Name(NccStrategy::STRATEGY_NAME).append("tester")), but the registered strategy name is /tester rather than /localhost/nfd/strategy/ncc/%FD%01/tester.
Thus, https://gerrit.named-data.net/3441 changes S::STRATEGY_NAME static variable to S::getStrategyName() static function to avoid this problem.

Actions #15

Updated by Junxiao Shi over 7 years ago

  • % Done changed from 20 to 30

https://gerrit.named-data.net/3447 allows StrategyTester to be added into the strategy registry. To test its effectiveness, in unit-tests.conf set StrategyChoice WARN loglevel, and check there's no "using shared strategy instance" warning.

A note on "The tester is unused in this file, but it's used in various templated test suites." comment:
Every StrategyTester<S> must be registered exactly once.
Some strategy test suites are entirely implemented with TopologyTester and do not use StrategyTester. However, there is a "templated test suite" strategy-scope-control.t.cpp which uses StrategyTester<S> for those strategies.
Although I could add those registrations into strategy-scope-control.t.cpp, it would cause confusion once a second templated test suite is added, such as those suggested in https://gerrit.named-data.net/3013 20161206 review comment. Therefore, I decide to place each registration into the test suite file for S, even if it's not directly used in that file.

Actions #16

Updated by Junxiao Shi over 7 years ago

  • % Done changed from 30 to 40

https://gerrit.named-data.net/3453 passes the whole strategy name as specified in StrategyChoice::insert to strategy subclass constructor, so that they could parse and process any parameters it may contain.
Existing strategy constructors are modified to reject any parameters, so that the overall behavior remains the same.

Actions #17

Updated by Junxiao Shi over 7 years ago

  • % Done changed from 40 to 50

https://gerrit.named-data.net/3471 updates test cases using DummyStrategy to register their strategies instead of relying on StrategyChoice::install.
Some test cases that rely on the old strategy versioning scheme are temporarily disabled, and will be re-enabled in a later Change after new versioning scheme is implemented.

Actions #18

Updated by Junxiao Shi over 7 years ago

https://gerrit.named-data.net/3477 switches TablesConfigSection::processStrategyChoiceSection to use Strategy::canCreate instead of StrategyChoice::hasStrategy.
One problem is discovered during this transition: if specified strategy parameters are rejected by the strategy constructor, dry-run would not be able to catch this error. However, since dry-run has limited usage, I wouldn't worry about this.

Actions #19

Updated by Junxiao Shi over 7 years ago

  • % Done changed from 50 to 60

https://gerrit.named-data.net/3482 switches StrategyChoiceManager to use Strategy::canCreate instead of StrategyChoice::hasStrategy. Test cases are still disabled and will be re-added after versioning scheme is changed.
In strategy-choice/set command handler, when Strategy::insert fails it previously returns code 405 that is not defined in StrategyChoice protocol. This condition cannot occur previously, but would occur now when the parameter is unacceptable by strategy subclass construtor. I decide to keep the 405 "unacceptable" code which is appropriate for this semantics, and will update protocol later.

https://gerrit.named-data.net/3483 deletes Strategy::getName which has been renamed to Strategy::getInstanceName.

Actions #20

Updated by Junxiao Shi over 7 years ago

It's pointed out that 405 is actually "method not allowed" while 504 is "gateway timeout". Both are inappropriate. I've combined them to 404 "not found" in https://gerrit.named-data.net/3482 patchset5.
It's unnecessary to programmatically distinguish whether the strategy program does not exist or the parameters are bad, so they have the same code. However, a more specified error message would be helpful. After StrategyChoice drops "installed instances" feature, I plan to change StrategyChoice::insert return type to include an error message (which could indicate "strategy not found" or the exception text from Strategy subclass constructor), and pass it along as the status text.

Actions #21

Updated by Junxiao Shi over 7 years ago

  • % Done changed from 60 to 70

https://gerrit.named-data.net/3505 drops installed instances feature in StrategyChoice table.

Actions #22

Updated by Junxiao Shi over 7 years ago

https://gerrit.named-data.net/3508 implements note-1 versioning scheme.

Actions #23

Updated by Junxiao Shi about 7 years ago

https://gerrit.named-data.net/3529 includes an error description in StrategyChoice::insert return value.
I intentionally designed the return type to be InsertResult struct, rather than std::tuple<bool, std::string>. This avoids constructing the "error message" string when it's not needed, and minimizes changes to other code that does not use the error description.

Effect:

vagrant@m0212:~/NFD$ nfdc set-strategy /A /localhost/nfd/strategy/no-such-strategy
Failed to set strategy choice: Strategy not registered (code: 404)
vagrant@m0212:~/NFD$ nfdc set-strategy /B /localhost/nfd/strategy/best-route/%FD%04/param
Failed to set strategy choice: Error instantiating strategy: BestRouteStrategy2 does not accept parameters (code: 404)
vagrant@m0212:~/NFD$ nfdc set-strategy /C /localhost/nfd/strategy/best-route/%FD%03
Failed to set strategy choice: Error instantiating strategy: BestRouteStrategy2 does not support version 3 (code: 404)
Actions #24

Updated by Junxiao Shi about 7 years ago

  • % Done changed from 70 to 90

https://gerrit.named-data.net/3610 rewrites StrategyChoiceManager test suite. It no longer deals with strategy versioning or parameters since they are provided by StrategyChoice.

The implemented behavior has two differences from StrategyChoice rev7:

  • set non-existing strategy returns 404 rather than 504
  • unset ndn:/ returns 400 rather than 403

I'll update the protocol to match implementation.

Actions #25

Updated by Junxiao Shi about 7 years ago

  • Status changed from In Progress to Code review
  • % Done changed from 90 to 100

StrategyChoice is updated to rev8 to match the implementation.

https://gerrit.named-data.net/3613 corrects StrategyChoice::changeStrategy behavior so that changing only the parameters would not unnecessary clear out StrategyInfo. This is judged by whether old strategy and new strategy are coming from the same record in the strategy registry.

Actions #26

Updated by Davide Pesavento about 7 years ago

Don't forget to update the dev guide.

Actions #27

Updated by Junxiao Shi about 7 years ago

  • Status changed from Code review to In Progress

Coding portion of this issue is completed. I'll update devguide next.

Actions #28

Updated by Junxiao Shi about 7 years ago

  • Status changed from In Progress to Resolved

NFD devguide is updated in nfd-docs:commit:80d61b7317dc2420da363c39ba7d1e4c9f20f87a.

Actions #29

Updated by Davide Pesavento about 7 years ago

Junxiao Shi wrote:

NFD devguide is updated in nfd-docs:commit:80d61b7317dc2420da363c39ba7d1e4c9f20f87a.

Looks good to me.

Actions #30

Updated by Junxiao Shi about 7 years ago

  • Status changed from Resolved to Closed

One of the rare times documentation is actually reviewed, instead of "closing after 5 days with no objection".

Actions

Also available in: Atom PDF