NFD

One addition: The forwarding strategy at each router on the path must be able to read and manipulate the congestion mark. Currently, it can't change any parts of the data packet, so we might need some re-design.

Data is end to end; attempting to change any field in a Data invalidates the signature.

That's a limitation of NFD which is not part of the NDN design, right? Lots of research (e.g. https://datatracker.ietf.org/doc/draft-moiseenko-icnrg-flowclass/?include_text=1) assumes that there can be data header fields outside the "security envelope".

Just mentioning that, because you could get long-term maintenance problems by putting everything into NDNLP.

For all that matters now, I agree to use NDNLPv2.

Today's NFD call confirmed to use NDNLPv2 for congestion signaling.

I'll create the other congestion control related soon, namely:

• Congestion Detection (when to set the congestion bits)
• Consumer Reaction
• Local Link Loss Detection (for use on top of UDP Tunnels)

NDNLPv2 has two ranges of TLV-TYPE codes reserved (see spec). You may pick any code within the range. I suggest a 3-octet code for this purpose.

Junxiao Shi wrote:

NDNLPv2 has two ranges of TLV-TYPE codes reserved (see spec). You may pick any code within the range. I suggest a 3-octet code for this purpose.

@Junxiao: I'm a bit confused about the NDNLP block assignment:

Two blocks of TLV-TYPE codes have been reserved by link protocols:

[80:100], 1-octet encoding
[800:1000], 3-octet encoding

TLV-TYPE codes for LpHeaderField SHOULD be assigned according to the following rules:

1. if the field can be safely ignored by a receiver that doesn't understand the field, pick an unused code in [800:959] range whose least significant 2-bits are 00.
2. if the field would occur frequently, pick an unused code in [81:99] range.
3. otherwise, pick an unused code in [800:959] range whose least sigificant 2-bits are 01. Note: code assignment for a TLV-TYPE nested within a LpHeaderField is not restricted by the above rules.

Does 3-octet mean, that we have 3 bytes of possible values for congestion signals (= values in the range of up to 2²⁴ )?

What means "can be safely ignored"? What does it mean for a field to "occur frequently"?

I don't believe that this field can be ignored, so can I have 830 assigned?

Also, as far as I know, there isn't a signature authentication check currently implemented in the link protocol. Therefore, I believe this task would just involve adding the field to the link protocol headers in ndn-cxx.

Eric Newberry wrote:

I don't believe that this field can be ignored

Why not?

Davide Pesavento wrote:

Eric Newberry wrote:

I don't believe that this field can be ignored

Why not?

Yes, what does "can be ignored" even mean? That it can be ignored by the routers? Or by the end hosts?

What if a router/end-host doesn't support the field? Then what's the alternative to ignoring it?

"can be ignored" means that if an implementation (so a host/router/whatever) doesn't support that field, it can just skip the TLV block and continue parsing and processing the packet as if the field wasn't present. The alternative is to stop decoding and drop the packet altogether.

In this case: Yes, the rest of the packet is still useful even if the host doesn't understand the congestion mark. Thus it "can be ignored".

Moreover, I suggest to add your explanation to the NDNLP wiki page.

Davide Pesavento wrote:

"can be ignored" means that if an implementation (so a host/router/whatever) doesn't support that field, it can just skip the TLV block and continue parsing and processing the packet as if the field wasn't present. The alternative is to stop decoding and drop the packet altogether.

Ah, I misread the meaning of "can be ignored". Now I would say that it's ok for the field to be ignored, as it does not interfere with the transmission of the packet hop-by-hop.

Therefore, could I have type 832 assigned for this? (the last two bits are 0, marking it as safely ignorable)

This is based off of the description in the TLV types section at the bottom of the NDNLPv2 wiki page. This section states that a field can be safely ignored if it is "in the range [800:959] whose two least significant bits are 00". However, there is conflicting wording in the LpHeaderField section at the top, which states that "if the unknown field is in range [800:959], and the least significant bit is 1, the receive SHOULD ignore the field".

Yes, 832 works fine.

That is, you can go ahead and implement it. If anyone objects to the type assignment, we can easily change it later.

a field can be safely ignored if it is "in the range [800:959] whose two least significant bits are 00"

This statement is correct. Nack has a code ending with 00. I recalled that Beichuan argued for Nack to be non-critical because a router that does not understand Nack can treat it as a looping Interest and process accordingly.

However, there is conflicting wording in the LpHeaderField section at the top, which states that "if the unknown field is in range [800:959], and the least significant bit is 1, the receive SHOULD ignore the field".

This is a mistake and should be corrected as part of this issue.

As part of this issue, the semantics and internal structure of congestion mark should be defined on NDNLPv2 page. Merely assigning a TLV-TYPE code is insufficient.

A description of the CongestionMark field has been added to the NDNLPv2 wiki page.

Eric Newberry wrote:

A description of the CongestionMark field has been added to the NDNLPv2 wiki page.

Looks good. I just added some clarification.

@Junxiao: Is the semantic description specific enough?

A value of 0 indicates no congestion; a value greater than 0 indicates some level of congestion.

So, is the CongestionMark field supposed to be added to every packet by hosts that support it? In that case, I think we are in the "if the field would occur frequently" case, and we should use a denser encoding.

The exact meaning of the bits in this field is left up to the congestion control strategy in use.

But there's no guarantee that the other host is using the same congestion control...

Reply to note-27:

the CongestionMark field supposed to be added to every packet by hosts that support it

I suggest an additional definition: a packet without CongestionMark indicates there's no known congestion.
Thus, router does not need to carry CongestionMark=0 in every packet.

use a denser encoding

CongestionMark is a non-critical field, which only has 3-octet TLV-TYPE codes.

there's no guarantee that the other host is using the same congestion control

One solution is to make CongestionMark more specialized: define the semantics of each bit as part of the protocol.
If another congestion control strategy wants a different structure incompatible with the existing definition, it can define another LpHeader field.

So, is the CongestionMark field supposed to be added to every packet by hosts that support it? \

I would say, yes the congestion mark should be added to every packet by hosts that support it.

Junxiao Shi wrote:

Reply to note-27:

the CongestionMark field supposed to be added to every packet by hosts that support it

I suggest an additional definition: a packet without CongestionMark indicates there's no known congestion.
Thus, router does not need to carry CongestionMark=0 in every packet.

However, then the hosts (routers and consumers) can no longer distinguish between "no congestion" and "congestion marks not supported by at least one router on the way". This is useful information. In fact, it might be useful to make the field a regular Integer (including negative values) to be able to include various error codes (that don't signal congestion, but contain other information).

use a denser encoding

CongestionMark is a non-critical field, which only has 3-octet TLV-TYPE codes.

there's no guarantee that the other host is using the same congestion control

True, there is no guarantee that every router is using the same marking algorithm.

One solution is to make CongestionMark more specialized: define the semantics of each bit as part of the protocol.
If another congestion control strategy wants a different structure incompatible with the existing definition, it can define another LpHeader field.

I think we can pre-specify a generalized marking behavior. I can see two options:

1. While in congested state: mark every packet

2. While in congested state: Spread out packet marks depending on the level of congestion. Our reference would be the CoDel drop logic: Mark first packet and wait 100ms. Mark next packet and wait a time indirectly proportional to the number of packets already marked. See https://datatracker.ietf.org/doc/draft-ietf-aqm-codel/

I suggest to choose the second option.

I don't think it's necessary to specify exactly what "congested state" means here. The router can choose between exceeding a threshold of packets in the queue, exceeding a threshold of queuing delay, being some time above a target value for queuing delay (like Codel), or others.

Similarly, the marking algorithm can vary as long as it's roughly equivalent to the CoDel logic.

The important point here is that each router indicates a rise in queue occupancy and the consumer reacts to it. Thus, the system should converge to a low queuing delay, even if the detection and signaling schemes are slightly different.

I agree with Junxiao. We should have a solid documentation for developers to use the congestion mark field inside the strategy. It should tell the developer how to manipulate the congestion header, independent of the algorithm they want to use.

We can leave the semantics of the marking algorithm (when the developer should set the mark) for later.

Junxiao Shi wrote:

• Strategy API needs to allow a strategy to add a CongestionMark onto an outgoing Data. Current code may or may not already permit this usage (if it allows, it's an undocumented feature), but nevertheless this needs to become a documented feature and be tested.

Can't this already be done in Strategy::beforeSatisfyInterest?

Eric Newberry wrote:

Junxiao Shi wrote:

• Strategy API needs to allow a strategy to add a CongestionMark onto an outgoing Data. Current code may or may not already permit this usage (if it allows, it's an undocumented feature), but nevertheless this needs to become a documented feature and be tested.

Can't this already be done in Strategy::beforeSatisfyInterest?

Can you post the exact code to add the congestion marks?

As Junxiao said, if it can be done it should be documented.

Nevermind, I was mistaken about the functionality of beforeSatisfyInterest.

Thanks!

For completeness, here's the link to the Gerrit change: https://gerrit.named-data.net/#/c/3342/

https://gerrit.named-data.net/3342 patchset1 introduces a beforeSendDataFromContentStore trigger to strategy API. This trigger is invoked in ContentStore hit pipeline, on the effective strategy of an incoming Interest to be satisfied by cached Data.

The moment of trigger invocation is questionable. When a Data is coming from the CS, no congestion has occurred between the path from current router to the data source since this path has zero length. Thus, the congestion mark indicates a congestion between the current router and the downstream.
To measure whether there's a congestion between the current router and the downstream, #1624 proposes to use sojourn time in the output queue. Output queuing is in the face system, which occurs after forwarding has sent the packet. Thus, the trigger is invoked too early in the processing procedure.

Also, even the strategy is able to detect a congestion between the current router and the downstream (e.g. because previous outgoing packets has long sojourn time), in case there are multiple downstreams on the same PIT entry but only some of those downstreams have a congestion, the strategy would not be able to tag the Data packet correctly, but could only either add a congestion mark for all downstream or for none.

A smaller issue is: The trigger allows modification on the Data packet still stored in the CS (rather than a copy of it), which may lead to undesired conflicts between strategies.
Suppose the path between current router and the downstream is in congestion, and strategy A adds a congestion mark to a Data packet. This congestion mark is retained in the CS entry. Later, the path is no longer in congestion, but strategy B which does not support congestion marks does nothing in the trigger and thus the Data goes out with the congestion mark still attached. This would confuse the downstream.

I think a bigger forwarding design change is needed to support this use case. I'll post a design in 10 days.

@Junxiao: Does the latest merge satisfy your comments in note-30?

Also: "Just wondering: where do we put the documentation of how to set congestion marks?"

Klaus Schneider wrote:

Also: "Just wondering: where do we put the documentation of how to set congestion marks?"

Do you mean documentation for how to set the field to a value or what each of the bits/the whole field means? For the former, it can be set just like any other field in an LpPacket (template getters and setters), so I don't believe any specific documentation on that is necessary.

I was talking about the former one.

Here's another question: Is the value of the congestion mark preserved over a series of NDNLP hops? For example if a data packet is marked by one router, is the mark automatically copied by each downstream router, or does each downstream router need to use a strategy that specifically copies the mark?

If not, we might consider making this preservation of congestion marks (over the whole path) the default behavior.

Klaus Schneider wrote:

Here's another question: Is the value of the congestion mark preserved over a series of NDNLP hops? For example if a data packet is marked by one router, is the mark automatically copied by each downstream router, or does each downstream router need to use a strategy that specifically copies the mark?

If not, we might consider making this preservation of congestion marks (over the whole path) the default behavior.

I believe this to be the case, as NFD extracts the CongestionMark field and adds it as a tag onto the network packet. When it goes to transmit this packet, it will take the value of the tag and add it as a CongestionMark field in the new LpPacket.

Eric Newberry wrote:

Klaus Schneider wrote:

Here's another question: Is the value of the congestion mark preserved over a series of NDNLP hops? For example if a data packet is marked by one router, is the mark automatically copied by each downstream router, or does each downstream router need to use a strategy that specifically copies the mark?

If not, we might consider making this preservation of congestion marks (over the whole path) the default behavior.

I believe this to be the case, as NFD extracts the CongestionMark field and adds it as a tag onto the network packet. When it goes to transmit this packet, it will take the value of the tag and add it as a CongestionMark field in the new LpPacket.

That's interesting. My intuition was the opposite (that NDNLP doesn't copy the value). Can someone confirm this?

@Junxiao has there been any progress on your design from note 37?

I think a bigger forwarding design change is needed to support this use case. I'll post a design in 10 days.

Unfortunately I didn't have time to finish this design, but I made some progress. It will be posted here after internal review.

@Junxiao: Does the latest merge satisfy your comments in note-30?

Yes, the separation into Change 3321, Change 3342, and another Change about Strategy API fulfills note-30.

Also: "Just wondering: where do we put the documentation of how to set congestion marks?"

NFD developer guide, Strategy section.

Is the value of the congestion mark preserved over a series of NDNLP hops? For example if a data packet is marked by one router, is the mark automatically copied by each downstream router, or does each downstream router need to use a strategy that specifically copies the mark?

This is an undefined behavior, because LpPacket is hop-by-hop, and forwarding is not required to preserve or remove ndn::Tags.

Is the value of the congestion mark preserved over a series of NDNLP hops? For example if a data packet is marked by one router, is the mark automatically copied by each downstream router, or does each downstream router need to use a strategy that specifically copies the mark?

This is an undefined behavior, because LpPacket is hop-by-hop, and forwarding is not required to preserve or remove ndn::Tags.

I think we should set the default to copying the tag, but also give the strategy the option to remove it, if necessary.

@Eric @Junxiao: As far as I understand the only thing remaining is to implement the strategy API for manipulating the congestion marks.

• Do we need a design for that?
• Are there any other tasks that block this issue?

The make access from the strategy easier, I would suggest the following simple API functions for every Interest, Data, and NACK packet:

bool isCongestionMarked();        // Returns true if the packet is currently contains a congestion mark.
void setCongestionMark(bool mark) // Adds or removes the congestion mark.

We should also put a documentation of this in the NFD developer guide.

Junxiao Shi wrote:

the only thing remaining is to implement the strategy API for manipulating the congestion marks.
Do we need a design for that?

Everything needs a design.

Lets start with the simple design I posted in note-49.

That should be sufficient to complete this issue, right?

Eric Newberry wrote:

Resuming work on this.

After finishing the API functions, it would also be good to have a simple integration test.

Something like this:

C -- R1 -- R2 -- R3 -- P

1. Consumer C sends an Interest
2. R1 adds the congestion mark
3. All other routers are configured to copy the congestion marks if it exists.
4. At the producer you check if the congestion mark arrived.

You can do the same with the Data packet in the reverse direction, but with the current strategy pipelines this test should fail (see #4290).

In general, the congestion marks should behave as if they are parts of the Interest/Data header. The user (someone implementing a new strategy) should not notice that the underlying implementation is NDNLP.

After finishing the API functions, it would also be good to have a simple integration test.

This needs a separate Redmine issue.

The make access from the strategy easier, I would suggest the following simple API functions for every Interest, Data, and NACK packet:

bool isCongestionMarked();        // Returns true if the packet is currently contains a congestion mark.
void setCongestionMark(bool mark) // Adds or removes the congestion mark.

I disagree. Such API is completely useless for applications. Functions only useful for strategies shall be placed in NFD's fw/algorithm.hpp.

Actually it is useful for consumer applications, since they need to retrieve the congestion marks from Data packets and NACKs.

It may even be useful for a producer application to insert congestion marks, in order to slow down consumers.

Reply to note-59:

I agree that applications can also use congestion mark.
However, I don't see a need to add more APIs. They are infrequently used. The existing Tag-based API should be sufficient.

They are infrequently used.

I don't think that's true either. There is many uses for these getters/setters inside new forwarding strategies or applications.

They will probably be used more than some of the existing functions:

• getMinSuffixComponents()
• getMaxSuffixComponents()
• getSelectors()

The existing Tag-based API should be sufficient.

The existing API requires knowledge of the underlying NDNLP. + It requires the user to deal with the distinction of "no tag" vs. "tag with congestion mark set to 0", which can be abstracted away.

Let's not forget that the implementation inside NDNLP is a workaround because we couldn't put a new (and manipulable) header field into Interest/Data packets. So we should at least try to make it as easily usable as if the congestion mark was a real header field.

Klaus Schneider wrote:

The make access from the strategy easier, I would suggest the following simple API functions for every Interest, Data, and NACK packet:

bool isCongestionMarked();        // Returns true if the packet is currently contains a congestion mark.
void setCongestionMark(bool mark) // Adds or removes the congestion mark.

Why is the proposed API boolean if CongestionMark is a nonNegativeInteger?

Klaus Schneider wrote:

bool isCongestionMarked();        // Returns true if the packet is currently contains a congestion mark.

Also, CongestionMark == 0 is defined as "no congestion", so I'm really confused about the desired semantics and intended usage.

Davide Pesavento wrote:

Why is the proposed API boolean if CongestionMark is a nonNegativeInteger?

The current design only uses binary (boolean) congestion marks. The unsigned int data type is for future compatibility.

To keep this compatibility, we can also turn the getter into:

unsigned getCongestionMark();

I don't know how the question in note-63 is different from the one in note-62.

Klaus Schneider wrote:

To keep this compatibility, we can also turn the getter into:

unsigned getCongestionMark();

ok, except unsigned -> uint64_t.

I don't know how the question in note-63 is different from the one in note-62.

The comment next to the function says "Returns true if the packet is currently contains a congestion mark", so if I get true I know the packet has a CongestionMark, but how do I distinguish between mark == 0 and mark > 0?

Now, with the function returning an unsigned integer, that problem's solved. But a new one arises: what does that function return for a packet that does not have a CongestionMark? Changing the return type to optional<uint64_t> is a potential solution.

Davide Pesavento wrote:

ok, except unsigned -> uint64_t.

Makes sense

Now, with the function returning an unsigned integer, that problem's solved. But a new one arises: what does that function return for a packet that does not have a CongestionMark? Changing the return type to optional<uint64_t> is a potential solution.

Not having a congestion mark and having a mark == 0 is semantically equivalent (it means no congestion). Thus, this wrapper function can abstract this difference away, by returning 0 in both cases.

Klaus Schneider wrote:

Not having a congestion mark and having a mark == 0 is semantically equivalent (it means no congestion). Thus, this wrapper function can abstract this difference away, by returning 0 in both cases.

So you don't interpret "no mark" == "no information on congestion" as different from "mark present and == 0" meaning "I positively know there is no congestion". In that case, I have no objections.

Yes. For debugging purposes it may be useful to distinguish these two cases, but for the normal case the tag should always be there. I think for debugging, the lower-level NDNLP API is sufficient.

But the more general question was: Do you agree that it's useful to have this higher-level API/wrapper or do you share Junxiao's objection in note-60?

(this question also addresses Eric and anyone else who wants to comment)

Klaus Schneider wrote:

But the more general question was: Do you agree that it's useful to have this higher-level API/wrapper or do you share Junxiao's objection in note-60?

I have no strong opinion either way.

What's missing here?

Eric listed some remaining problems as part of the integration test issue:

This test case could be extended to check for Data packet congestion mark propagation in the reverse direction, but this is not currently supported (see #4290). Additionally, NFD will currently not add a congestion mark to packets at any time in the current implementation (unless it is propagating an existing mark) - this must be implemented somehow for the Interest component of this test case to work.

Klaus Schneider wrote:

Eric listed some remaining problems as part of the integration test issue:

This test case could be extended to check for Data packet congestion mark propagation in the reverse direction, but this is not currently supported (see #4290). Additionally, NFD will currently not add a congestion mark to packets at any time in the current implementation (unless it is propagating an existing mark) - this must be implemented somehow for the Interest component of this test case to work.

Ok thanks. It's a bit hard to understand the status when things are spread across multiple redmine issues.

For the first problem (marking Data packets), there is a dedicated issue already (#4290), so it will be handled there.
The second problem (when to actually mark packets) doesn't belong to this issue, as its description says "This task is not about the logic when to set or reset congestion marks, but about giving routers the general ability to do so", so that task should also go in a separate redmine ticket (to be created).

Is there anything else to do for this issue or can we close it?

Let's wait until the Integration Tests are working.

That's a separate issue so we should be able to close this one even if that one isn't finished. It looks like everything in this issue's description has been completed.

Eric Newberry wrote:

That's a separate issue so we should be able to close this one even if that one isn't finished. It looks like everything in this issue's description has been completed.

+1