Project

General

Profile

Feature #3000

Design mobility with forwarding hint

Added by Junxiao Shi about 4 years ago. Updated over 1 year ago.

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

50%

Estimated time:
6.00 h

Description

Design forwarding and table to use forwarding hint for mobility.

Reference: SNAMP: Secure Namespace Mapping to Scale NDN Forwarding

forwarding-hint_20150520.pptx (75.1 KB) forwarding-hint_20150520.pptx Junxiao Shi, 06/30/2015 09:16 AM
forwarding-pipelines_20150702.pptx (86.4 KB) forwarding-pipelines_20150702.pptx Junxiao Shi, 07/02/2015 07:47 PM
forwarding-pipelines_20150709.pptx (87.3 KB) forwarding-pipelines_20150709.pptx Junxiao Shi, 07/09/2015 05:30 PM
forwarding-hint_20150814.pptx (76.6 KB) forwarding-hint_20150814.pptx Junxiao Shi, 08/14/2015 09:04 PM
forwarding-pipelines_20150814.pptx (88.4 KB) forwarding-pipelines_20150814.pptx Junxiao Shi, 08/14/2015 09:04 PM

Related issues

Related to ndn-cxx - Feature #2587: Link and forwarding hintClosed

Related to NFD - Feature #3034: ContentStore miss pipeline: process Link for mobilityClosed

Related to NFD - Feature #3161: CS: partition by forwarding hintNew

Related to NFD - Feature #3162: PIT: index with forwarding hintNew

Related to NFD - Feature #3159: NetworkRegionTable configuration optionClosed

Related to NFD - Feature #3163: Insert to CS with forwarding hintNew

Related to NFD - Feature #3333: Design Interest digestNew

Related to NFD - Feature #3664: Incoming Nack pipeline: consider Link during FIB lookupClosed

Related to NFD - Feature #3893: Strip Link object from Interest when it reaches producer regionClosed

Related to NFD - Feature #4055: Forwarding hint: represented as name onlyClosed

History

#1 Updated by Junxiao Shi about 4 years ago

forwarding-hint_20150520.pptx is the high level idea.

This Task shall produce updated forwarding pipelines flowcharts and table API.

We have identified these changes are necessary:

  1. "router Name" in configuration file
  2. ContentStore: store Data along with the Link object used to retrieve it
  3. ContentStore: lookup with Link object (exact match)
  4. PIT: use <Name,Selectors,Link> as index key
  5. either NFD or consumer API: perform NDNS lookup, and add Link object into outgoing Interest
  6. incoming Interest pipeline: lookup ContentStore with Link object
  7. ContentStore miss pipeline: determine whether the Interest has reached producer region
  8. ContentStore miss pipeline: if Interest has not reached producer region, lookup FIB with delegation Name(s), and insert SelectedDelegation field
  9. incoming Data pipeline: determine which Link object has been used to retrieve Data, and insert to ContentStore with that Link object

A minimal implementation would be {1, 5, 7, 8}.
This enables applications that rely on mobility to work, but does not address cache poisoning concern.

#2 Updated by Junxiao Shi about 4 years ago

#3 Updated by Junxiao Shi about 4 years ago

  • Target version changed from v0.5 to v0.4

20150701 conference call concludes that note-1 item 5 is unnecessary for mobility support, because the mobile can directly supply its Link object to the requester, and the requester does not have to perform NDNS lookup in order to obtain the Link object.

We agree that note-1 item {1,7,8} is sufficient as a minimal implementation for mobility support, and design can start now.

#4 Updated by Junxiao Shi about 4 years ago

  • Status changed from New to In Progress

#5 Updated by Junxiao Shi about 4 years ago

I've updated forwarding pipelines design with note-1 item {7,8}. Updated pages are page 11,13,14,15.

Due to limitations in Strategy API design:

  • At the first default-free router, which delegation to use is chosen by forwarding pipelines solely based on whether a FIB match is found. Ideally, this choice should be made by the strategy, taking into account the performance of nexthops.
  • Measurements are collected under the namespace of Interest Name, without considering which delegation is chosen. Ideally, on a router far from the producer region, performance is more relevant with the delegation Name.

I intend to solve these problems with #2000.

#6 Updated by Junxiao Shi about 4 years ago

An additional problem in note-5 design is: a node in consumer region can erroneously insert SelectedDelegation.

In "choose and set SelectedDelegation" procedure, if the consumer host has a FIB entry ndn:/, any delegationName can match this FIB entry and be selected as SelectedDelegation.

Even if we change the procedure to ignore ndn:/, a generic FIB entry such as ndn:/ndn (covering all sites on NDN testbed) would cause a similar effect.

20150703 conference call discussed these problems but didn't reach a conclusion.

Lixia prefers to start with a simple solution, but disagrees with the assumption of having only one delegation per Link.

#7 Updated by Junxiao Shi about 4 years ago

20150708 conference call discussed note-6 question.
The solution is:

  • Hosts in consumer region should install default route in ndn:/. Operator shouldn't use ndn:/ndn as default route.
  • Given an Interest with Link but without SelectedDelegation, forwarding should lookup FIB with the first delegation Name.
    • If lookup matches the FIB entry ndn:/ with at least one nexthop record, it's assumed that the Interest is still in consumer region. It's forwarded according to the matched FIB entry, but SelectedDelegation field is not inserted.
    • If lookup matches a FIB entry other than ndn:/, or the FIB entry ndn:/ with zero nexthop record, it's assumed that the Interest has reached the first default-free router. The choice for SelectedDelegation should be made at this router.

Design will be updated to reflect this solution.

#8 Updated by Junxiao Shi about 4 years ago

Design is updated to adopt note-7 solution. Page 11,13,14,15.

#9 Updated by Junxiao Shi about 4 years ago

  • Related to Feature #3026: RouterName configuration option added

#10 Updated by Junxiao Shi about 4 years ago

  • Related to Feature #3034: ContentStore miss pipeline: process Link for mobility added

#11 Updated by Junxiao Shi about 4 years ago

20150713 conference call approves the design in note-8.

This issue will remain open. It's not to be closed until the final design, including all items in note-1, is complete.

For this reason, implementation tasks are "related to" but not "blocked by" this issue.

#12 Updated by Alex Afanasyev almost 4 years ago

As shown in pptx, the detection of whether interest reached the producer region is based on "router's name".

Why router's name, not network(s) to which this router belongs. Besides the fact that router's name not necessary matches network it servers, the implication here is that we are allowing directing interests towards a specific router. This by itself is worrisome for me.

My thinking is that the logic should be based entirely on "network name" (with the same logic: delegation name should be a prefix of network name). In the long run, there could be multiple network names to which router belongs.

#13 Updated by Junxiao Shi almost 4 years ago

Reply to note-12:

It makes sense to allow a router to be configured with multiple "network name"s, or more precisely, region names.

However, I'm unsure whether this complication is necessary at this moment in the minimal feature set.

#14 Updated by Junxiao Shi almost 4 years ago

From http://gerrit.named-data.net/#/c/2279/4/daemon/fw/forwarder.cpp:

why "isInProducerRegion" is overloaded with two meanings: that the link is not present and that the link present and something is in producer region

This is a consequence of "determine whether in producer region" algorithm design (in note-8).

I agree with the comment that it's better to having a separate decision point to test whether a Link object exists.

I'll amend the design after note-12 is resolved.

#15 Updated by Alex Afanasyev almost 4 years ago

Junxiao Shi wrote:

Reply to note-12:

It makes sense to allow a router to be configured with multiple "network name"s, or more precisely, region names.

However, I'm unsure whether this complication is necessary at this moment in the minimal feature set.

I didn't suggest allowing multiple network names right now, only in the future (=long term). The only change that I would like to have right now is to check against the configured "network name", not the "router name".

#16 Updated by Junxiao Shi almost 4 years ago

Reply to note-12:

This won't work.

"network name", in NLSR sense, is equivalent to an AS number.

Every NDN router on the testbed is in the same network /ndn.
A router may be configured as: network=ndn, site=edu/memphis, router=cs/pollux.

Using NLSR's "network name" as mobility's "region name" implies mobility is never useful on the testbed.

#17 Updated by Alex Afanasyev almost 4 years ago

I see the point now. I guess I don't fully understand the meaning of "site". In my mind, "network" is something like "/ndn/edu/memphis", i.e., a combined NLSR "network" and "site".

I would like to question #3026 requirement: "contain enough information to be used by NLSR to initialize itself". Semantics of NLSR (e.g., concept of routing domain, site) doesn't necessarily apply to NFD...

#18 Updated by Lan Wang almost 4 years ago

Just want to mention the following:

  • NLSR is designed for intra-domain routing.

  • We consider the NDN testbed as one network, hence /ndn is the network name, not /ndn/edu/memphis.

  • If you want to test the LINK design for mobility, it's best to set up multiple networks, each running its own instance of NLSR and inject some routes to other networks at the border routers (e.g., the border router at /att injects a route to /verizon with itself as the originator into the NLSR for /att) also set up some static routes at those border routers to get to other networks.

#19 Updated by Alex Afanasyev almost 4 years ago

We want not just "test", we want to actually use it on the existing testbed. Our implementation shouldn't depend on how NLSR is configured...

Considering current "intra-domain" configuration. LINK should include prefix that is routed globally and within a specific network (and recursively within smaller networks, if necessary). As I see, this prefix is not NLSR's network, it looks like NLSR's network+site, but it is even not this prefix. I think what we really should use are prefixes for which NLSR announces reachability: set of advertising.prefix configuration setting from nlsr.conf.

#20 Updated by Junxiao Shi almost 4 years ago

20150810 conference call decides to change "in producer region" algorithm to use "region names" rather than "router name", so that the design can prevent an attacker from addressing a single router.

Design slides are updated.

#21 Updated by Junxiao Shi almost 4 years ago

  • Related to deleted (Feature #3026: RouterName configuration option)

#22 Updated by Junxiao Shi almost 4 years ago

  • Related to Feature #3161: CS: partition by forwarding hint added

#23 Updated by Junxiao Shi almost 4 years ago

  • Related to Feature #3162: PIT: index with forwarding hint added

#24 Updated by Junxiao Shi almost 4 years ago

  • % Done changed from 20 to 50

note-1 item-7,8 has been implemented in #3034.

note-1 item-1 is changed to "region names" according to note-20, and is to be implemented in #3159.

note-1 item-2,3,6 is to be implemented in #3161.

note-1 item-4 is to be implemented in #3162.

note-1 item-9 is to be implemented in #3163.

#25 Updated by Junxiao Shi almost 4 years ago

  • Related to Feature #3159: NetworkRegionTable configuration option added

#26 Updated by Junxiao Shi almost 4 years ago

  • Related to Feature #3163: Insert to CS with forwarding hint added

#27 Updated by Junxiao Shi almost 4 years ago

During NDNcomm2015 "Revisiting name-content binding: In-network name space operations" session, Nacho Solis (PARC) raises an attack scenario after I introduce forwarding logic for Link:

P--\     /--C
    S---R
E--/     \--A
  • /producer is an unroutable prefix, and its legit Link object is /P at node P.
  • C is a legit user who wants to retrieve /producer from P.
  • A is an attacker who wants to poison cache for contents under /producer.
  • E is controlled by producer, and its routable prefix is /E.

Steps:

  1. C expresses an Interest with Link /P, which is forwarded along C-R-S-P.
  2. A expresses an Interest of same Name with Link /E, which is forwarded along A-R-S-E.
    Note that it's unfeasible to "keep Names secret". For realtime streaming traffic, it's easy for A to keep track of the current Interest Names (by running a legit consumer elsewhere), and to predict next Interest Names.
  3. E returns Data faster than P.
  4. At S, the Data satisfies A's Interest only, because PIT entry of C's Interest does not have an out-record toward E.
  5. At R, the Data satisfies both A's Interest and C's Interest, because PIT entries of both Interests have out-records toward S.
  6. R caches E's Data with both Link object /E and Link object /A.
    This is cache poisoning.
  7. R returns E's Data to both A and C.
    This prevents C from receiving legit Data.

The root cause of this attack scenario is: after R forwards an Interest with multiple distinct Link objects toward the same upstream, when Data comes back from S, R cannot determine which Link object was used to retrieve this Data.

One solution is: the Link object used to retrieve a Data should be returned along with the Data itself, e.g. in NDNLP header.

#28 Updated by Junxiao Shi over 3 years ago

#29 Updated by Junxiao Shi over 3 years ago

note-27 attack scenario is to be discussed in #3333.

note-1 item-4 and item-9 cannot start until a solution for this attack is ready.

#30 Updated by Junxiao Shi over 3 years ago

  • Target version changed from v0.4 to v0.5

This issue will remain open. It's not to be closed until the final design, including all items in note-1, is complete.

#31 Updated by Lixia Zhang over 3 years ago

3/15/16: JeffB pointed out that the 2015/08/14 slide deck did not clearly describe LINK processing (slide 11 box, slide 13 explanation). Deserve a revision.

#32 Updated by Junxiao Shi about 3 years ago

  • Related to Feature #3664: Incoming Nack pipeline: consider Link during FIB lookup added

#33 Updated by Junxiao Shi over 2 years ago

  • Target version changed from v0.5 to v0.6

20161206 call points out that there's an operational difficulty in using producer region table: if the producer region table on an end host is not configured, the end host would attempt to forward any received Interest with Link back to the network instead of to a local producer.
A possible solution is: as soon as an Interest with Link reaches a router within the producer region, the router should delete the Link object and forward the Interest without Link. The end host will not see the Link object, and can forward the Interest to a local producer properly, without requiring producer region table configuration.

#34 Updated by Alex Afanasyev over 2 years ago

  • Related to Feature #3893: Strip Link object from Interest when it reaches producer region added

#35 Updated by Alex Afanasyev over 2 years ago

Junxiao, will you be able to implement stripping of the Link object when an Interest arrives at the network region (I created a separate issue #3893 for that)?

#36 Updated by Junxiao Shi about 2 years ago

  • Related to Feature #4055: Forwarding hint: represented as name only added

#37 Updated by Junxiao Shi almost 2 years ago

  • Subject changed from Design mobility with Link to Design mobility with forwarding hint
  • Description updated (diff)
  • Assignee deleted (Junxiao Shi)

This issue has been blocked for years due to #3333. Given I'm graduating soon, I will no longer work on this issue.

#38 Updated by Davide Pesavento over 1 year ago

  • Tracker changed from Task to Feature
  • Status changed from In Progress to Feedback
  • Target version deleted (v0.6)

Also available in: Atom PDF