NFD

Hi Vince,

sorry that I missed the NFD call today, I got confused by some change in the timezone difference (Tucson apparently doesn't have daylight saving time).

Some comments:

1. It looks like delay probing is incredibly cheap (one packet every 60s/10s). Wouldn't it thus be easier to just probe all faces (which are not the current primary face) every x seconds? This might save some coding and debugging effort.

2. As I understood, you are recording the RTT measurements of the regular data for the primary path and the RTT measurements of probes for the probed paths. Therefore, the primary path receives many more RTT measurements, and thus quicker updates, than the probed paths. This might lead to problems, such as the following:

Let's say you have the following topology. Router A has two faces to R1,R2, but they both join to the same link (C,P).

----- R1 -----|
|             |
A             C ------ P
|             |
------R2------|

Let's say (A,R1) is the primary path. Now, when the delay at (C,P) increases, A will switch to R2 as primary path. After some time, A will notice that the delay on R2 is actually higher, and switch back to R1.

A solution would for all paths (also the primary path) to only consider RTT measurements during probing time (probing all faces the same time improves the reliability here). However, it also slows down the time to detect delay changes at the primary path.

The scenario can become worse when the primary traffic of A actually causes the delay by increasing the queuing delay at the intermediate routers. In this case, A may indefinitely oscillate between R1, and R2.

In this case, you might want to consider some sort of hysteresis, that is, an additional threshold that encourages staying on the current face if the other faces are just slightly better.

I described the idea in my last paper ( http://conferences2.sigcomm.org/acm-icn/2015/proceedings/p137-schneider.pdf ) and have a prototype implementation here: https://github.com/schneiderklaus/ndnSIM/blob/master/NFD/daemon/fw/lowest-cost-strategy.cpp (although with a different scenario in mind).

1. Here is another problem when the secondary path overlaps with the primary path (as described above). You use a new nonce for the probes, which avoids the problem that the second interest will be dropped at router C. However, Router C will still put the second interest in the PIT-Entry and not send out a second data packet. Since the data packet is already on its way, the probing result of the slower path will be faster than its actual RTT.

Maybe this doesn't matter, because the interest should still be slower than the fastest path (the returning data still has a longer one-way delay). Another option would be to probe a name different than the current interest. Maybe with the a correct prefix, but unavailable (randomly generated) data name (getting a NACK back).

Hi Klaus,

Thanks for the comments and questions.

Klaus Schneider wrote:

1. It looks like delay probing is incredibly cheap (one packet every 60s/10s). Wouldn't it thus be easier to just probe all faces (which are not the current primary face) every x seconds? This might save some coding and debugging effort.

I do want to clarify that although there is probing every 60s, this probing is per namespace. If there are many FIB entries with many next hops, trying every face for each probing period may not be very cheap (especially on highly connected nodes).

There are two main reasons we chose to probe only a single face at each probing period:

1. We want to take advantage of the routing metrics provided by hyperbolic routing to influence our interface selection for probing. It is possible that many of the interfaces are not useful for a particular name prefix; instead of probing these faces that will not lead to data, we try to limit our probes to interfaces we expect to be useful based on hyperbolic distance.

2. We want to keep the overhead constant regardless of the connectivity of the node; we want to constrain the overhead as topologies grow in size. By only probing one interface per namespace, the overhead is limited by the number of namespaces and the probing interval (i.e. 60 seconds).

Klaus Schneider wrote:

1. As I understood, you are recording the RTT measurements of the regular data for the primary path and the RTT measurements of probes for the probed paths. Therefore, the primary path receives many more RTT measurements, and thus quicker updates, than the probed paths. This might lead to problems, such as the following:

Let's say you have the following topology. Router A has two faces to R1,R2, but they both join to the same link (C,P).

----- R1 -----|
|             |
A             C ------ P
|             |
------R2------|

Let's say (A,R1) is the primary path. Now, when the delay at (C,P) increases, A will switch to R2 as primary path. After some time, A will notice that the delay on R2 is actually higher, and switch back to R1.

A solution would for all paths (also the primary path) to only consider RTT measurements during probing time (probing all faces the same time improves the reliability here). However, it also slows down the time to detect delay changes at the primary path.

The scenario can become worse when the primary traffic of A actually causes the delay by increasing the queuing delay at the intermediate routers. In this case, A may indefinitely oscillate between R1, and R2.

In this case, you might want to consider some sort of hysteresis, that is, an additional threshold that encourages staying on the current face if the other faces are just slightly better.

I described the idea in my last paper ( http://conferences2.sigcomm.org/acm-icn/2015/proceedings/p137-schneider.pdf ) and have a prototype implementation here: https://github.com/schneiderklaus/ndnSIM/blob/master/NFD/daemon/fw/lowest-cost-strategy.cpp (although with a different scenario in mind).

Thanks for the suggestion, I will read over "Beyond Network Selection" again and look into this as it seems like it could be useful.

Klaus Schneider wrote:

1. Here is another problem when the secondary path overlaps with the primary path (as described above). You use a new nonce for the probes, which avoids the problem that the second interest will be dropped at router C. However, Router C will still put the second interest in the PIT-Entry and not send out a second data packet. Since the data packet is already on its way, the probing result of the slower path will be faster than its actual RTT.

Maybe this doesn't matter, because the interest should still be slower than the fastest path (the returning data still has a longer one-way delay). Another option would be to probe a name different than the current interest. Maybe with the a correct prefix, but unavailable (randomly generated) data name (getting a NACK back).

Yes, we think that since the Interest would be slower than the faster path and since we are using SRTT to smooth out these variations that this should not be a serious issue. If the strategy starts using the slower path due to caching on the path or cases like the above, eventually the SRTT of the slower path should become worse than the faster path and switch back.

Vince Lehman wrote:

Hi Klaus,

Thanks for the comments and questions.

Klaus Schneider wrote:

1. It looks like delay probing is incredibly cheap (one packet every 60s/10s). Wouldn't it thus be easier to just probe all faces (which are not the current primary face) every x seconds? This might save some coding and debugging effort.

I do want to clarify that although there is probing every 60s, this probing is per namespace. If there are many FIB entries with many next hops, trying every face for each probing period may not be very cheap (especially on highly connected nodes).

Okay, that makes sense. Are there any estimates of how many name prefix entries the average core router holds?

20160329 conference call approves the idea of this strategy.

It's pointed out that the development of adaptive forwarding strategy is independent from the adoption of hyperbolic routing.
Hyperbolic routing may rely on adaptive forwarding strategy as a prerequisite, but developing adaptive forwarding strategy does not depend on the approval of hyperbolic routing deployment.

Before going into implementation, the design needs to be amended to clarify the following:

• How does the strategy handle consumer retransmissions?
• How does the strategy process incoming Nacks?
• Does the strategy generate outgoing Nacks?

I understand that the strategy was designed before these issues were raised, so now it's a good time to think above them.
Although I recommend supporting all three features listed above, a design without these features will be acceptable to me, as long as the designer has thought about them.

The design may choose the adopt the same processing steps for consumer retransmissions and Nacks as another existing strategy, such as best-route v4.
In that case, the design can simply reference the referenced strategy, but the implementation will need to copy over the relevant code (this is unfortunate, but will be improved after #2000).

As discussed in today's call:

The reaction to congestion NACKs probably requires agreement between the receiver and the sender of the NACK. Before implementing it here, we should specific when exactly the upstream sends a congestion NACK. Moreover, the reaction will likely be similar in many strategies and is a good candidate for task #2000.

Also, "Duplicate NACK" sounds like "Duplicate ACK" from TCP. Does it mean that you receive two NACKs for the same sequence number in a row? If not, I would suggest to find another name to avoid confusion.

After Receive Interest Trigger, should we send back a NACK if there is no faceToUse for forwarding or only reject the pending Interest?

Minsheng Zhang wrote:

After Receive Interest Trigger, should we send back a NACK if there is no faceToUse for forwarding or only reject the pending Interest?

Yes, I think a NACK should probably be sent in that scenario.

Hey Vince,

I just read the new specification and have a couple questions:

To facilitate optimal forwarding in hyperbolic routing (HR) and address drawbacks (embedding issues, network
dynamics, etc.), a strategy must be able to make forwarding decisions based on Data retrieval delay

It is unclear to me why the strategy must be based on "data retrieval delay" rather than packet loss information or explicit signals? Maybe you can put in a longer rationale or a reference.

Group 3: Next hops that timed-out on the previous Interest

What do you consider as reasons for why the Interest timed out? What do you mean with "the previous Interest"? "Previous" according to the naming convention (/foo/N, /foo/N+1) or any interests sent out previously?

Let's say we are sending interests /foo/1, /foo/2, /foo/3, and so on. Let's also say Interest /foo/2 timed out and you detect the timeout just before you send out /foo/17. Do you then put the router into Group 3?

What if at this point /foo/3, /foo/4, and /foo/5 have been received successfully?

• What is the rationale for your two formulas of the probing probability?

Lastly, a more general question:

• Is saving measurement information (here: SRTT) per FIB entry fine-granular enough?

What if the your local FIB entry /foo splits up at later routers to /foo/A, /foo/B, /foo/C. Then you would be mixing RTT measurements for different prefixes and likely send some traffic on suboptimal paths.

This isn't specific to hyperbolic routing, so feel free to ignore. But it would still be interesting if there's a good solution already.

I've pushed changes to the Developer's guide to add a description and citation for the ASF strategy.