[Nfd-dev] namespace-based strategy choice weakness

Tue Jul 5 05:06:30 PDT 2016

How about the following naming scheme?

/ndn/edu/arizona/cs/app

so strategies can be configured per app if needed, e.g.,

/ndn/edu/arizona/cs => access v1
/ndn/edu/arizona/cs/ndncon => realtime
/ndn/edu/arizona/cs/nfs => highthroughput

FIB can contain only one record:

/ndn/edu/arizona/cs

Lan

On Jul 4, 2016, at 7:53 PM, Junxiao Shi <shijunxiao at email.arizona.edu<mailto:shijunxiao at email.arizona.edu>> wrote:

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
_______________________________________________
Nfd-dev mailing list
Nfd-dev at lists.cs.ucla.edu<mailto:Nfd-dev at lists.cs.ucla.edu>
http://www.lists.cs.ucla.edu/mailman/listinfo/nfd-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/nfd-dev/attachments/20160705/1b2a0876/attachment.html>