Project

General

Profile

Actions

Task #4305

closed

Feature #4279: Self-learning strategy

Self-learning forwarding strategy: issues and design choices

Added by Teng Liang over 6 years ago. Updated over 4 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
-
Target version:
-
Start date:
09/27/2017
Due date:
% Done:

0%

Estimated time:

Description

This issue intends to identify and summarize all the problems in implementing the self-learning forwarding strategy in NFD. Besides, it also compares different implementation designs.

Here is the paper about NDN self-learning. The high-level idea of self-learning that a node floods an Interest when no route is found; the Data packet sent back will carry a prefix announcement, and each node along the path will update its FIB and create a route towards the upstream node according to the prefix announcement.

This design is targeted at multi-access and point-to-point link types, ad hoc scenarios are not within the design scope.

Background: the current NFD design - NFD currently implements Ethernet unicast communication in the same way as a UDP tunnel: each NIC has one Ethernet-multicast face configured as either broadcast or ad hoc wireless, and zero or more Ethernet-unicast face for point-to-point communication with specific neighbors.

Issues:

  • #issue-1: how to identify if a multicast face and an unicast face are on the same NIC in a forwarding strategy, so that it doesn't broadcast a packet multiple times to the same shared medium?

  • #issue-2: how to create an unicast ethernet face in a forwarding strategy, since it doesn't have enough information?

  • #issue-3: how to update FIB in a forwarding strategy?

  • #issue-4: suppose a node A creates an unicast face towards the node B, and A sends an Interest through the unicast face to B; when will B create a corresponding unicast face to A? For example, will B receive the Interest and create the face automatically, or this function needs to be added (where to add the code)?

  • #issue-5: how to deal with multiple Interests when FIB states are not set up yet? This is an algorithm design issue.

Junxiao's implementation design

It solves #issue-1 and #issue-2 by refactoring Ethernet unicast/multicast communication and modifying FIB, and it solves #issue-3 by creating a temporary FIB. His design doesn't have the problem in #issue-4, but it doesn't cover #issue-5.

The problem of Junxiao's design is that it is complicated and involves a lot of efforts to solve small problems.

An alternative implementation design:
Keep the current design of ethernet multicast/unicast communication and FIB structure, and solve the issues with other methods.

  • For #issue-1, the localUri attribute in Face can help to identify if faces are on the same NIC and it is available for an forwarding strategy.

  • For #issue-2, NDNLP tags can be used to pass necessary information to an forwarding strategy to create a face.

  • For #issue-3, update FIB through RIB in an forwarding strategy (details are needed).
    Junxiao argued that updating FIB through RIB is asynchronous, which doesn't take effect immediately. Thus it may affect subsequent Interests. I don't think asynchronous operation will make a big difference.

  • For #issue-4, it is similar to UDP unicast scenario (details are needed).

  • For #issue-5, an application probably have some kind of discovery mechanism so it wouldn't send many Interests when the content is not discovered yet. Even an application send many Interests at the same time, as an NFD has no idea if a FIB update will happen soon to serve these Interests, it shouldn't queue these Interests. Thus, these Interests should be flooded when no routes are found.


Files

Actions #1

Updated by Teng Liang over 6 years ago

I think #issue-3 and #issue-4 can be implemented in the current NFD, but not sure which part of the code does the work. Does anyone have a clue?

Actions #2

Updated by Teng Liang over 6 years ago

  • Subject changed from Self-learning forwarding strategy for multi-access and point-to-point link type to Self-learning forwarding strategy - issues and designs
Actions #3

Updated by Yanbiao Li over 6 years ago

Teng Liang wrote:

I think #issue-3 and #issue-4 can be implemented in the current NFD, but not sure which part of the code does the work. Does anyone have a clue?

Ethernet channel will create an unicast face toward the sender when it receives an Ethernet frame, no matter it's broadcasted or not.

If we need to update FIB from strategy, I would also prefer to synchronous updates. Actually, the reason why we need to update the FIB in this scenario is to have later Interests go through the newly created unicast face. If the update is asynchronous we may have to wait for a while here (then, how long to wait?). If we do not wait, the next Interest may still go through the multicast face

Actions #4

Updated by Teng Liang over 6 years ago

Yanbiao Li wrote:

Ethernet channel will create an unicast face toward the sender when it receives an Ethernet frame, no matter it's broadcasted or not.

That's good to know. Do you know which part of code handles this?

If we need to update FIB from strategy, I would also prefer to synchronous updates. Actually, the reason why we need to update the FIB in this scenario is to have later Interests go through the newly created unicast face. If the update is asynchronous we may have to wait for a while here (then, how long to wait?). If we do not wait, the next Interest may still go through the multicast face

There are at least three ways to do synchronous update, 1) updating the FIB directly in a forwarding strategy (like when NFD initializes, it inserts "/localhost/nfd" to FIB), but it may cause problems since FIB is controlled by RIB. 2) creating another FIB for forwarding strategy to update (like a temporary FIB). The concern for the second approach is that it may cause a lot of changes to NFD. 3) updating FIB through RIB. Though it is asynchronous, can we make it synchronous? E.g., the forwarding strategy holds the Data until the FIB update is done.

Actions #5

Updated by Davide Pesavento over 6 years ago

Yanbiao Li wrote:

Ethernet channel will create an unicast face toward the sender when it receives an Ethernet frame, no matter it's broadcasted or not.

No, that's incorrect. EthernetChannel should process only unicast frames. If it does otherwise, it's an implementation bug.

Actions #6

Updated by Yanbiao Li over 6 years ago

Davide Pesavento wrote:

Yanbiao Li wrote:

Ethernet channel will create an unicast face toward the sender when it receives an Ethernet frame, no matter it's broadcasted or not.

No, that's incorrect. EthernetChannel should process only unicast frames. If it does otherwise, it's an implementation bug.

Yes, maybe I should have explained this to Teng in more detail. To my understanding, his question is "whether we have such an automatic creation function (where it is?) or we should make some changes (where to work?)"

My answers have two parts:

1/ We do have this feature, it's in EthernetChannel (more specifically, in EthernetChannel::processIncomingPacket, <-- handleRead <-- asyncRead <-- listen), and this can address his concerns in #issue-4.

2/ Toward this automatic creation feature itself (along the calling chain inside EthernetChannel), there is no dependence on whether the incoming frame is unicast or multicast. If you can directly use this feature, just go on. If you want to use it for another purpose that current implementation does not support (currently, only unicast ethernet channel will listen), you can also reuse this piece of code without big changes.

Why I highlighted this here was because I thought automatically creating an unicast face upon receiving the response of a multicast request could be more useful (and this is what I require in the IoT bootstrapping staff). According to the Ethernet protocol, it's definitely possible. At first, we do not know where exactly to send our request, so we send it to a multicast MAC address. Then, we get back a response where the SRC filed of the Ethernet frame is an unicast MAC address (but its DST filed is a multicast MAC address, so it will be took by the multicast channel in our side). Now, we could be able to create an unicast face if we really want.

Actions #7

Updated by Teng Liang over 6 years ago

  • Blocked by Feature #4280: Prefix announcement for self-learning added
Actions #8

Updated by Teng Liang over 6 years ago

This note is to record the discussion with Junxiao on Oct. 20, 2017.

#issue-3: how to update FIB in a forwarding strategy?
The concern about updating FIB though RIB: it requires a forwarding strategy send a packet to RIB manager first, and the RIB manager will send a FIB update to FIB manager. The whole procedure is executed after the Data packet is sent out, so it is possible that another (non-discovery) Interest comes before the FIB state is set up.

The proposed design: a forwarding strategy can directly update FIB through FIB manager. To maintain the consistence with RIB, the FIB manager sends a notification to RIB manager about the insertion. This can be implemented as a function in the base class of the forwarding strategy, so that any forwarding strategy can use it.

#issue-6: how to create and store prefix announcement?

The NFD should create the prefix announcement when a prefix is registered by an application, and the NFD signs it. Then NFD stores the prefix announcement in FIB as a tag. Additionally, the prefix announcement should be stored with Data packets in CS.

More explanations: the self-learning has two types of Interests: discovery and non-discovery (can be implemented with a discovery tag in NDNLP). A discovery Interest brings a Data packet with the prefix announcement, while a non-discovery Interest does not. Here are four cases:

  1. The discovery Interest is broadcast to the network; after the Data is found, it is sent back with the prefix announcement. Nodes along the path will update their FIB and store the prefix announcement (for case 4).
  2. The non-discovery Interest will be sent along the path to the producer.
  3. When a non-discovery Interest finds no FIB entry on a node, a NACK is sent back that clears the FIB state along the path. (The first NFD will send a discovery Interest without informing the consumer?)
  4. When a discovery Interest is sent to a node that knows a path (has a FIB entry), the node changes the discovery Interest to a non-discovery Interest. As a non-discovery Interest brings a Data packet without a prefix announcement, the node should attach the prefix announcement to it and send it back.
Actions #9

Updated by Nicholas Gordon over 6 years ago

For what it's worth, I don't think that direct FIB manipulation is a good idea. My objections stem from the fact that if you change the FIB, you have to propagate those changes back into the RIB. Then, the RIB has to take these corner cases into account, and then you're essentially duplicating the core functions of the RIB: to aggretate routing information and create a forwarding set.

It seems to me that the main problem with submitting these updates to the RIB in the orthodox way is that the nodes down the path may not have the FIB entry set up soon enough. A few of my thoughts then are:

  1. Use some kind of acknowledgment system so that nodes can establish that the discovery packet has been received and integrated into the FIB.
  2. Create some kind of accelerated pipleine through the RIB, so that everything can be funneled there. If I'm not mistaken, local faces are already implemented as a UNIX socket, so this should be a pretty fast process, anyway.
  3. Build some kind of wait time into the strategy to allow time post-discovery for the next node to process the discovery.
  4. Accept the fact that some packets may require retransmission. If network performance is so critical, then I think it would be better to improve the source -> RIB -> FIB pipeline, rather than disregarding the architecture and hacking something in.
Actions #10

Updated by Davide Pesavento over 6 years ago

Nicholas Gordon wrote:

For what it's worth, I don't think that direct FIB manipulation is a good idea.

I agree.

It seems to me that the main problem with submitting these updates to the RIB in the orthodox way is that the nodes down the path may not have the FIB entry set up soon enough.

Correct. But (question to Teng/Junxiao) what is the impact of that? Is it such a big deal if a second interest comes before the new FIB state is set up? We're talking about a few milliseconds here...

I'm also not sure why the strategies are not allowed to have "private" FIBs, that can only be accessed by the owning strategy. The FibManager (and therefore nfdc) would be unable to dump those tables, but I think that's a minor issue.

Actions #11

Updated by Teng Liang over 6 years ago

I agree with Nicholas (note-9) that regarding an architecture issue, we should not hack the system (make a shortcut) to achieve a better performance, but instead should improve the architecture.

Correct. But (question to Teng/Junxiao) what is the impact of that? Is it such a big deal if a second interest comes before the new FIB state is set up? We're talking about a few milliseconds here...

The fact is that we don't really know how long it takes to set up a FIB state, so the original idea is to achieve a "perfect" or "clean" update. The worst case is that a few more Interests will be flooded, which should not be. Though this is not much overhead.

I'm also not sure why the strategies are not allowed to have "private" FIBs, that can only be accessed by the owning strategy. The FibManager (and therefore nfdc) would be unable to dump those tables, but I think that's a minor issue.

I have no objection to that. One limit of "private" FIBs is that they are not shared to other forwarding strategies, so other strategies can not utilize them.

Actions #12

Updated by Nicholas Gordon over 6 years ago

I was discussing this with Alex and Lan, and their combined suggestions I think present a good solution. We can choose either to:

  1. Buffer the interests we receive instead of no-route NACKing them immediately, and re-evaluate them after some time. This ought to give enough time for the FIB entry to be set up, or
  2. Record all interests in the PIT, even if they don't have a FIB entry. Then, whenever a FIB entry is created, check the PIT to see if any interests should be forwarded now.

Naturally, in these cases you would delete the interest/not forward the interest if the lifetime expires, even in the probably-short buffering case.

My thoughts are that idea 2 is a generalization of idea 1. Idea 1 is simpler, and introduces the least amount of overhead, since you are checking each interest at most twice. Idea 2 is more optimistic, but introduces a very expensive habit of searching the whole PIT any time a FIB entry is added, which could potentially be very often in ad-hoc networks.

Idea 2 also presents a much more aggressive approach to getting data, but may end up in interest flooding, e.g. if an application sends a lot of interests, maybe like Flume does with forward-looking interests. Then, when a FIB entry is created, that NFD would be inadvertently flooding the link with all of these retained interests. This could also happen a lot in ad hoc networks, which is where interest flooding may be the most unacceptable.

Actions #13

Updated by Teng Liang over 6 years ago

Nicholas Gordon wrote:

I was discussing this with Alex and Lan, and their combined suggestions I think present a good solution. We can choose either to:

  1. Buffer the interests we receive instead of no-route NACKing them immediately, and re-evaluate them after some time. This ought to give enough time for the FIB entry to be set up, or
  2. Record all interests in the PIT, even if they don't have a FIB entry. Then, whenever a FIB entry is created, check the PIT to see if any interests should be forwarded now.

These are good suggestions in general. Just regarding the self-learning forwarding strategy, if the FIB entry is not set up, a "broadcast" Interest will be flooded. Thus the solution 1 is not the case of the self-learning. The solution 2 may reduce redundant Interest flooding (if updating FIB through RIB takes a relative long time), but it delays the discovery procedure for the first Interest as it always buffers Interests first. Thus, we could try the simple one (i.g., flood Interest if no FIB entries) and test it. If it is a big problem, we can consider these solutions. Does it make sense?

Actions #14

Updated by Davide Pesavento over 6 years ago

  • Subject changed from Self-learning forwarding strategy - issues and designs to Self-learning forwarding strategy: issues and design choices
  • Assignee set to Teng Liang
Actions #15

Updated by Davide Pesavento over 6 years ago

  • Blocked by deleted (Feature #4280: Prefix announcement for self-learning)
Actions #16

Updated by Davide Pesavento over 6 years ago

Actions #17

Updated by Teng Liang over 6 years ago

As discussed in the NFD call on Nov. 20, 2017, the challenges of the self-learning forwarding strategy implementation stem from its (frequent) manipulation of FIB, including FIB entry creation, FIB entry refreshment, and the extension of FIB entry for the prefix announcement attachment. Here are three possible solutions and pros and cons.

  • Direct FIB manipulation
    • Pros: FIB update is synchronous and the operation cost is low
    • Cons: May require a lot of work to resolve the conflicts with RIB and the consequences of changing the logic of FIB manipulation; requires the change of FIB
  • Update FIB through RIB
    • Pros: Keep the consistency of FIB manipulation
    • Cons: The operation cost is high; requires the changes of FIB and RIB; may require extra mechanisms for corner cases when FIB entries are not set up (e.g., buffering Interests)
  • Create a “private” FIB for a forwarding strategy
    • Pros: the same as direct FIB manipulation; have no conflicts with RIB and the master FIB
    • Cons: requires table management (e.g., insertion, removal, lookup)

Davide, Junxiao and I accept the third solution. I am looking into the best place for the "private" FIB (probably the measurement table).

Actions #18

Updated by Davide Pesavento over 6 years ago

Teng Liang wrote:

  • Create a “private” FIB for a forwarding strategy
    • Pros: the same as direct FIB manipulation; have no conflicts with RIB and the master FIB
    • Cons: requires table management (e.g., insertion, removal, lookup)

Add "state is lost if strategy choice is changed at runtime" to the cons. In practice this is a non-issue, since strategy changes are extremely infrequent operations.

I am looking into the best place for the "private" FIB (probably the measurement table).

Well, you don't really have any other choices... Strategies must be stateless, so the only possible place is the Measurements table.

Actions #19

Updated by Teng Liang over 6 years ago

Davide Pesavento wrote:

Well, you don't really have any other choices... Strategies must be stateless, so the only possible place is the Measurements table.

Can I interpret it in this way: self-learning uses the Measurements table as its "private" FIB; when a Data packet carries a prefix announcement is received, a Measurement entry for the prefix is added including the prefix announcement; when an Interest packet is received, the Measurement table finds a longest prefix match for the Interest name and returns a FaceId. Then the Measurement table should be extended as a FIB.

An alternative is to explicitly create a "private" FIB for forwarding strategies.

Actions #20

Updated by Davide Pesavento over 6 years ago

Teng Liang wrote:

Davide Pesavento wrote:

Well, you don't really have any other choices... Strategies must be stateless, so the only possible place is the Measurements table.

Can I interpret it in this way: self-learning uses the Measurements table as its "private" FIB; when a Data packet carries a prefix announcement is received, a Measurement entry for the prefix is added including the prefix announcement; when an Interest packet is received, the Measurement table finds a longest prefix match for the Interest name and returns a FaceId.

Yes.

Then the Measurement table should be extended as a FIB.

You lost me here. A measurements entry can already store arbitrary per-strategy information. What do you need to extend?

An alternative is to explicitly create a "private" FIB for forwarding strategies.

Do you mean as a separate table? Why? What would be the advantage compared to using Measurements?

Actions #21

Updated by Teng Liang over 6 years ago

Davide Pesavento wrote:

Then the Measurement table should be extended as a FIB.

You lost me here. A measurements entry can already store arbitrary per-strategy information. What do you need to extend?

An alternative is to explicitly create a "private" FIB for forwarding strategies.

Do you mean as a separate table? Why? What would be the advantage compared to using Measurements?

I didn't realize how the measurement table works. The measurement table should work well as the "private" FIB for forwarding strategies. I am looking into it for a concrete design.

Actions #22

Updated by Davide Pesavento over 6 years ago

  • Parent task set to #4279
Actions #23

Updated by Teng Liang over 6 years ago

Self-learning is designed to work for wired local area networks, infrastructure mode Wi-Fi and ad hoc networks. As a forwarding strategy may have customized mechanisms in ad hoc networks, such as Interest suppression, self-learning is better to be implemented as two different versions, one for the first two scenarios and one for the last scenario. The plan is to implement self-learning for local area networks and infrastructure mode Wi-Fi first as Task #4279.

From the implementation perspective, NFD uses Ethernet face with point-to-point or multicast links in the target scenarios. Besides existing subtasks for #4279, I am thinking to create three more subtasks:

  • Add necessary information in NDNLP field and tag, so a forwarding strategy can create an Ethernet unicast face when it does not exist.
  • Design and implement measurement table for self-learning.
  • A test suite for self-learning

These are relative smaller and independent tasks that different people can work on. I am looking for comments before actually creating these.

Actions #24

Updated by Davide Pesavento over 6 years ago

Teng Liang wrote:

  • Add necessary information in NDNLP field and tag, so a forwarding strategy can create an Ethernet unicast face when it does not exist.

I have no idea what this means. You need to explain what the problem is and how you intend to solve it in some more detail, if you're looking for feedback.

  • Design and implement measurement table for self-learning.

Not the table itself, but the strategy-private structure that will be stored in the measurements table. I don't think this is a separate task from the implementation of the strategy itself.

  • A test suite for self-learning

Are you talking about unit tests or integration tests? If it's the former, then it's not a separate task, each code change must be committed together with its own unit tests.

Actions #25

Updated by Teng Liang over 6 years ago

Davide Pesavento wrote:

Teng Liang wrote:

  • Add necessary information in NDNLP field and tag, so a forwarding strategy can create an Ethernet unicast face when it does not exist.

I have no idea what this means. You need to explain what the problem is and how you intend to solve it in some more detail, if you're looking for feedback.

The problem is how to create a unicast face in a forwarding strategy when it doesn't have enough information (e.g., remote url). For example, node A multicasts a discovery Interest to its neighbors, then it receives a Data with prefix announcement from node B. On receiving the Data, node A creates a FIB entry . If node A does not have a unicast face to B, it needs to create one. I am thinking to attach the necessary information to Interest or Data using NDNLP tag.

  • Design and implement measurement table for self-learning.

Not the table itself, but the strategy-private structure that will be stored in the measurements table. I don't think this is a separate task from the implementation of the strategy itself.

Agree. This one and the unit tests are part of the forwarding strategy. However, I break them into more pieces for the purpose of hackathon project, so my teammates can have smaller tasks. This one is similar to design and implement daemon/fw/asf-measurements.hpp(cpp) with unit tests.

  • A test suite for self-learning

Are you talking about unit tests or integration tests? If it's the former, then it's not a separate task, each code change must be committed together with its own unit tests.

I was thinking about self-learning.t.cpp and assume it belongs to unit tests, but it still requires some work, like designing test scenarios. I agree to put this one and previous one in the same code change with the self-learning forwarding strategy. My purpose is to break the forwarding strategy task into smaller ones so that multiple people can work together on this in the hackathon. To summarize, I don't need to create separate tasks for these two, since they are part of forwarding strategy, but people can work on them separately and integrate them into the same code change.

Actions #26

Updated by Teng Liang over 6 years ago

Automatically creating an unicast Ethernet/UDP face on receiving a multicast Ethernet/UDP packet seems difficult to be implemented. One ugly approach is to attach FaceUri to an Interest/Data packet, and let a forwarding strategy to create the unicast face. Is there a more elegant approach?

Actions #27

Updated by Teng Liang about 6 years ago

We decided to bypass RIB and build a private FIB for self-learning forwarding strategy, because 1) we wanted to avoid break changes to existing code base, 2) Junxiao had concerns of asynchrounous FIB update through RIB. However, since self-learning also does routing work, bypassing RIB ends up with building another RIB (with announcement verification and FIB update). Thus we should utilize (or extend) RIB to satisfy self-learning.

According to RibMgmt, a local host or a next hop can register prefix either using "/localhost/nfd/rib" or "/localhop/nfd/rib". We could apply a trust model that can directly using rib control command, meaning that NFD uses control command to register prefix with a neighbor NFD.

Here is an example: an application registers a prefix with an NFD. The NFD has an FIB entry towards the app. Using self-learning, to satisfy a pending "discovery" Interest, the NFD sends a rib control command to register a route on its neighbor NFD (use a unicast face) in the onSatisfyingInterest phase. (How to handle the response?)

 /localhop/nfd/rib/rigister/<control-parameters>

This design doesn't not need prefix announcement attachment. It also avoids Data packet manipulation in forwarding strategy.

One feature is still needed: automatic unicast face creataion on receiving multicast packet.

This implementation design is based on a major change in the protocol design: the curretn protocol sends a NACK back when receiving a "non-discovery" Interest, indicating that a new round of dicovery should be initiated at the consumer. For some reasons, the nodes in the middle of the path have not updated its FIB yet when receiving a "non-discvoery" Interest (they are supposed to finish the update). In this case, the self-learning with change "non-discovery" Interest to "discovery" Interest immediately and flood it, instead of send NACK back.

Actions #28

Updated by Davide Pesavento about 6 years ago

Teng Liang wrote:

Using self-learning, to satisfy a pending "discovery" Interest, the NFD sends a rib control command to register a route on its neighbor NFD (use a unicast face) in the onSatisfyingInterest phase.

I'm not sure I understand this. Can you give more details? A sequence diagram would help.

Actions #29

Updated by Teng Liang about 6 years ago

  • File self-learning_20180116 added

Davide Pesavento wrote:

Teng Liang wrote:

Using self-learning, to satisfy a pending "discovery" Interest, the NFD sends a rib control command to register a route on its neighbor NFD (use a unicast face) in the onSatisfyingInterest phase.

I'm not sure I understand this. Can you give more details? A sequence diagram would help.

Please see the sequence diagram file "self-learning_20180116.png"

I realized that directly sending RIB command to a neighbor NFD only works within a single hop, so prefix announcement is still used. Then RIB should be extended to accept prefix announcement, verify it and update FIB accordingly.

Actions #30

Updated by Teng Liang about 6 years ago

  • File deleted (self-learning_20180116)
Actions #31

Updated by Teng Liang about 6 years ago

  • File An Example of Self-learning - 20180117.png added
Actions #32

Updated by Teng Liang about 6 years ago

  • File deleted (An Example of Self-learning - 20180117.png)
Actions #34

Updated by Teng Liang about 6 years ago

The core idea of the new implementation design is that: the prefix announcement can be directly sent to RIB to update FIB.

Actions #35

Updated by Junxiao Shi about 6 years ago

This implementation design is based on a major change in the protocol design: the curretn protocol sends a NACK back when receiving a "non-discovery" Interest, indicating that a new round of dicovery should be initiated at the consumer. For some reasons, the nodes in the middle of the path have not updated its FIB yet when receiving a "non-discvoery" Interest (they are supposed to finish the update). In this case, the self-learning with change "non-discovery" Interest to "discovery" Interest immediately and flood it, instead of send NACK back.

When a node receives a non-discovery Interest but lacks a valid route, how does it distinguish whether this is caused by "awaiting FIB update" so it should re-flood, or this is caused by "link failure" so it should Nack and let consumer re-flood?
An intermediate node cannot re-flood upon link failure because that would discover suboptimal path. See self-learning dissertation for details.

the prefix announcement can be directly sent to RIB to update FIB.

This requires RibMgmt to accept prefix announcements. I think it's needed anyway after #4443. The prefix registration command could accept prefix announcements in the InterestPayload.

In note-33 diagram, "NFD-B OnSatisfyingInterest" block has step "store PA in the measurement table if the update succeeds". This is unimplementable because NFD-RIB does not tell you whether the update succeeds. See RibMgmt "Semantics of successful responses" section.

Actions #36

Updated by Teng Liang about 6 years ago

Junxiao Shi wrote:

When a node receives a non-discovery Interest but lacks a valid route, how does it distinguish whether this is caused by "awaiting FIB update" so it should re-flood, or this is caused by "link failure" so it should Nack and let consumer re-flood?
An intermediate node cannot re-flood upon link failure because that would discover suboptimal path. See self-learning dissertation for details.

I see your points. First, do you agree that we should use RIB to update FIB in self-learning? Second, "awaiting FIB update" seems to be a corner case, since it involves local operations that should be fast. You may disagree with it, so I would follow the current protocol design (i.e., always treat it as "link failure") and test it afterwards. If this is an issue, we can add mechanisms to fix it later.

the prefix announcement can be directly sent to RIB to update FIB.

This requires RibMgmt to accept prefix announcements. I think it's needed anyway after #4443. The prefix registration command could accept prefix announcements in the InterestPayload.

Why this has something to do with InterestPayload. I am thinking to define prefix announcement as a command Interest that RIB can recognize. If you agree with going this way, I will create a new feature accordingly.

In note-33 diagram, "NFD-B OnSatisfyingInterest" block has step "store PA in the measurement table if the update succeeds". This is unimplementable because NFD-RIB does not tell you whether the update succeeds. See RibMgmt "Semantics of successful responses" section.

"Successful responses from these commands indicate that NFD RIB Management has received and authorized the command, and will perform the requested updates shortly." The point is that the forwarding strategy only stores a PA that is verified, and the response tells a forwarding strategy about it. Whether the update succeeds does not matter.

Actions #37

Updated by Nicholas Gordon about 6 years ago

I am thinking to define prefix announcement as a command Interest that RIB can recognize. If you agree with going this way, I will create a new feature accordingly.

I agree. I don't understand how the pipelines in NFD work, but from an outsider's perspective it shouldn't matter whether it's a Command Interest or an ordinary Interest with a payload -- they should be in the same pipelines. Then, we should keep with orthodoxy and just use Command Interests.

I realized that directly sending RIB command to a neighbor NFD only works within a single hop, so prefix announcement is still used. Then RIB should be extended to accept prefix announcement, verify it and update FIB accordingly.

So I'm sure you've thought of this, but this is starting to look a lot like a routing program in some aspects. Let me point out a few things:

  1. You have to propagate forwarding/routing information between disconnected nodes in order to get good results, just like NLSR.
  2. NLSR does this by disseminating LSAs, you are suggesting to do it on-demand, push-style by modifying NFD to permit other NFDs to directly add RIB routes. NLSR could have done it this way, but then NFD stops being just a forwarding program and starts creeping out in all directions.
  3. There's no really good reason that what you're designing here shouldn't live in its own program. You could have a smaller plugin that lives in NFD as a forwarding strategy and then hooks into a separate daemon. Then you eliminate the need for heavily modifying NFD. But then you have NLSR's problem, where you need a trust model between nodes, a namespace structure, ... :-).
Actions #38

Updated by Teng Liang about 6 years ago

Nicholas Gordon wrote:

  1. You have to propagate forwarding/routing information between disconnected nodes in order to get good results, just like NLSR.
  2. NLSR does this by disseminating LSAs, you are suggesting to do it on-demand, push-style by modifying NFD to permit other NFDs to directly add RIB routes. NLSR could have done it this way, but then NFD stops being just a forwarding program and starts creeping out in all directions.
  3. There's no really good reason that what you're designing here shouldn't live in its own program. You could have a smaller plugin that lives in NFD as a forwarding strategy and then hooks into a separate daemon. Then you eliminate the need for heavily modifying NFD. But then you have NLSR's problem, where you need a trust model between nodes, a namespace structure, ... :-).
  1. What does "disconnected nodes" mean? Do you mean when some nodes go offline?

  2. You are suggesting we can implement the routing part of self-learning in a separate program, like NLSR, right? I agree that a routing program should be implemented separately, and self-learning does routing work. However, there is a difference between self-learning and NLSR: before sending commands to RIB, NLSR needs to do calculation, but self-learning only needs to verify the prefix announcement. Thus, since RIB already has a validator, can self-learning utilize it instead of building a new one? To utilize the validator in RIB, self-learning needs to extend RIB to recognize the prefix announcement (e.g., with the prefix /self-learning/nfd/rib/). The upsides are: 1) avoid building a new routing program (extending RIB in this case has much less work?), 2) it is easier for a network operator to configure self-learning, since self-learning is built into NFD. However, I am not sure if extending RIB like this violates any rule, that may cause potential problems.

Actions #39

Updated by Davide Pesavento about 6 years ago

Two comments on the diagram in note-33:

  1. in the OnSatisfyingInterest box of NFD-A, it sounds like both the producer and NFD-A can create the PA. Is that the case? If so, it means that they need to share the private key for the PA signature, or that other nodes need to trust both keys. If not, how can NFD-A create the PA? Moreover, I'm not sure why NFD-A needs to concern itself with this problem (lack of PA on the Data).

  2. at some point NFD-A sends the Data back to NFD-B via a unicast face, should I assume that the previous Interest was sent on a multicast face instead?

Actions #40

Updated by Teng Liang about 6 years ago

Davide Pesavento wrote:

Two comments on the diagram in note-33:

  1. in the OnSatisfyingInterest box of NFD-A, it sounds like both the producer and NFD-A can create the PA. Is that the case? If so, it means that they need to share the private key for the PA signature, or that other nodes need to trust both keys. If not, how can NFD-A create the PA? Moreover, I'm not sure why NFD-A needs to concern itself with this problem (lack of PA on the Data).

  2. at some point NFD-A sends the Data back to NFD-B via a unicast face, should I assume that the previous Interest was sent on a multicast face instead?

  1. At first I thought a producer doesn't care about PA, since the business is only among NFDs (to build routes in network). Then, according to the trust model in self-learning (NFDs in an network trust each other), a producer should not generate a PA, since producer is not a role in the trust model. Thus, there are two separate steps: 1) only trusted apps can register prefix with an NFD, 2) the first NFD should generate PA according to FIB. The first step is not part of self-learning (I assume NFD can control who can register prefix, right?). As NFD-A is the first NFD (by checking FIB), it has to create a PA.

  2. Yes, but I am not sure how many changes are need to implement it (e.g., how does NFD behave when the returned Data comes from a different face). Any comments on this one?

Actions #41

Updated by Teng Liang about 6 years ago

Regarding the call on Jan 22, I see a key design question that we have to answer first: what is the trust model in self-learning?

1) In an NDN network, a trusted producer is trusted by all NFDs in the network. In other words, a producer should generate PA and other NFDs can verify and accept it.

2) In an NDN network, a trusted NFD is trusted by all NFDs in the network. In other words, an NFD should generate PA on behalf of all its trusted producers, and other NFDs can verify and accept it.

For option 1), when a producer register a prefix with an NFD, it generates a PA as well (e.g., with the prefix /self-learning/nfd/rib) and stores it somewhere that a forwarding strategy can access (where?). For option 2), the self-learning forwarding strategy in an NFD can check FIB and generate PA accordingly, and store it in the measurement table.

In both options, a self-learning validator should be implemented in the NFD (in RIB manager?).

I have two concerns about option 1): (i) self-learning is not used for all prefixes, so PA is not always needed (2) I don't know where and how to store the PA (can it be stored in the measurement table of self-learning?).

My concern for option 2): generating PA in forwarding strategy slows down forwarding processing, but for each prefix registered by local apps, PA is generated once.

Actions #42

Updated by Davide Pesavento about 6 years ago

  • Status changed from New to In Progress
Actions #43

Updated by Junxiao Shi over 5 years ago

  • Tags set to SelfLearning
Actions #44

Updated by Junxiao Shi about 5 years ago

  • Status changed from In Progress to Rejected

Discussion should belong to nfd-dev mailing list. It does not need an issue.

Actions #45

Updated by Davide Pesavento over 4 years ago

  • Status changed from Rejected to Closed
Actions

Also available in: Atom PDF