[Nfd-dev] namespace-based strategy choice weakness

[Junxiao Shi]

Dear folks

NFD adopts a namespace-based strategy choice: for an incoming Interest that
needs to be forwarded, the forwarding strategy responsible for making
forwarding decisions of this Interest is identified by a longest prefix
match on the strategy choice table.
For example, Arizona router has its strategy choice table configured as
follows:

   - / => best-route v4
   - /ndn/multicast => multicast v1
   - /ndn/edu/arizona => access v1
   - (other entries omitted)

Interest /ndn/edu/ucla/ping/1 matches / entry and will be handled by
best-route strategy. Interest /ndn/edu/arizona/cs/shijunxiao/ping/2 matches
/ndn/edu/arizona entry and will be handled by access strategy.

This namespace-based strategy choice allows a network operator to configure
different strategies for different kinds of links. In the above Arizona
router example, /ndn/edu/arizona is the local site prefix that covers all
end hosts connected to Arizona router (typically via UDP tunnels), and
access strategy is designed for this kind of last hop UDP tunnels. The
default strategy, configured on / entry, is set to best-route v4, which is
designed for forwarding Interests over multiple hops on the global backbone
network.

However, *namespace-based strategy choice offers very limited support for
tailoring the strategy choice based on application needs*.
Currently, NFD only has a handful of strategies. The "smart" ones
(best-route, access, ncc) all optimize for the same goal: minimize
round-trip delay.
In the future, especially with the development in congestion control, NFD
is likely to have more strategies with different optimization goals: some
strategies can minimize round-trip delay, and some other strategies can
maximize throughput.
Different application scenarios can benefit from different strategy
choices: a real-time video conferencing application wants lower delay but
can tolerate smaller throughput as long as it's enough for receiving the
lowest video quality, and wants to toss any Data that cannot arrive before
the playout deadline; a file downloading application prefers higher
throughput; a backup application can give more emphasize on minimizing
monetary cost as long as the backup can complete overnight.


In the current namespace-based strategy choice, *it's hard to configure
different strategies to different applications*.
Since we mandate every user to have a testbed certificate and use automatic
prefix propagation to register prefixes toward end hosts, the only name
structure applications can use is to have the user identity before
application name, such as /ndn/edu/arizona/cs/shijunxiao/ndncon.
Suppose ndncon wants to set a different strategy than the access strategy
in /ndn/edu/arizona entry, it would *have to create a separate strategy
choice entry for each user*'s ndncon sub-namespace. In other words, the
Arizona router would end up with a strategy choice table that looks like
this:

   - /ndn/edu/arizona/cs/shijunxiao/ndncon => realtime
   - /ndn/edu/arizona/cs/bzhang/ndncon => realtime
   - /ndn/edu/arizona/cs/zhuoli/ndncon => realtime
   - (repeat for every other user)

This is certainly not scalable. Also, if we want to realtime strategy to be
applied on other routers, every router in the backbone network needs to
have these strategy choice entries. #2054-6
<https://redmine.named-data.net/issues/2054#note-6> was a hassle similar to
this.

If we change the name structure to have the application name before the
user identity (let's forget about automatic prefix propagation for now), we
could have a name like /ndncon/ndn/edu/arizona/cs/shijunxiao. In this case,
we only need one strategy choice entry for each application:

   - /ndncon => realtime
   - /ndnfs => high-throughput

But it's a disaster for FIB. Our FIB would look like this:

   - /ndncon/ndn/edu/arizona/cs/shijunxiao => Junxiao's end host
   - /ndncon/ndn/edu/arizona/cs/bzhang => Beichuan's end host
   - /ndncon/ndn/edu/arizona/cs/zhuoli => Zhuo's end host
   - /ndnfs/ndn/edu/arizona/cs/shijunxiao => Junxiao's end host
   - /ndnfs/ndn/edu/arizona/cs/bzhang => Beichuan's end host
   - /ndnfs/ndn/edu/arizona/cs/zhuoli => Zhuo's end host
   - (repeat for every other application)

And this also affects the global routing system. It would need multiple
entries toward each site, like:

   - /ndncon/ndn/edu/arizona => nexthop toward Arizona
   - /ndnfs/ndn/edu/arizona => nexthop toward Arizona
   - (repeat for every other application)

Therefore, *changing the name structure as application name before user
identity causes scalability issue* in FIB and routing, and thus is not a
viable solution.


We have identified several alternate design ideas for strategy choice.

NFD can *choose effective strategy from a marked component*.
Instead of doing longest prefix match in the strategy choice table, a
strategy choice entry can indicate:

   - contains "app=ndncon" => realtime
   - contains "app=ndnfs" => high-throughput

The first entry can match any incoming Interest that contains "app=ndncon"
as one of the name components, and choose realtime strategy for such
traffic.
It's necessary to use a marked component (see #2012
<https://redmine.named-data.net/issues/2012>) rather than a generic name
component "ndncon", because only a marked component can identify the
Interest is indeed ndncon traffic. Using a generic name component would
match an Interest like /github/remap/ndncon/v0.7.7/ndncon.app which is the
binary package of ndncon but not actual ndncon traffic.
This should be used in conjunction with namespace-based strategy choice,
because choosing a strategy based on link properties is also a useful
feature.

A weakness of the first idea is that the strategy choice is still based on
the name. However, sometimes a different strategy may be preferred based on
what the consumer is doing.
ndncon is normally a realtime video conferencing application. It requires
very low delay, and any Data that cannot be delivered before playout
deadline can be tossed because they won't be played if they arrive late.
However, suppose there's a video recording consumer that wants to record a
high quality video stream from ndncon. Assuming a local repo-ng is deployed
alongside ndncon producer, there would be no rush for the video recording
consumer to receive the Data packet. In this case, this consumer would
prefer a strategy that offers high throughput, and does not want any late
arriving Data to be tossed.

To support this use case, *an Interest can carry a strategy choice field*.
NFD can choose a strategy according to this field.
We could either put a strategy name into this field and let NFD retrieve
the strategy program, or put some generic preferences in this field and let
NFD pick a strategy that best matches those preferences.
The bandwidth overhead of this field is less of a concern, because it would
be much smaller than a Link object.
A major challenge in this second idea is that it's unclear which strategy
would be used if Interests sharing the same PIT entry from different
consumers are asking for different strategies. It's certainly undesirable
to split into multiple PIT entries based of different strategy choice and
send packets multiple times.


The above do not conflict with composable strategy building blocks (#2000
<https://redmine.named-data.net/issues/2000>) or composable forwarding
plane. That just allows a different way to express strategy choice: instead
of using a table, composable forwarding uses a script or flowchart to
select a strategy behavior.
The above do not conflict with expressing strategy choice through routing
protocols. That just allows a different way to install entries into
strategy choice table. One relation is that the strategy choice field in
Interest can have the same format as how strategy choice is represented in
routing announcements.


The above content is extended a recap from my discussion with Zhuo Li, a
new developer at Arizona that will work on forwarding.
Yours, Junxiao
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/nfd-dev/attachments/20160704/47c06609/attachment.html>