Re: [Detnet] Validity of Deadline based forwarding

["Gengxuesong (Geng Xuesong)" <[e-mail]>]

Hi

Thanks for starting this thread for deep discussion of  Deadline based forwarding for clarification. (I have also raised similar concern in IETF 117)
I think the conclusion is quite clear. Here are some further comments for WG’s reference based on the agreement:

1.       Maybe we should consider to adding a criteria in queuing mechanism comparing to differentiate whether the mechanism could provide latency uncertainty or not. (for example in-time mode of deadline based forwarding)

2.       I’m still  confused with the on-time mode with certainty. If the latency is guaranteed by eligible arrival pattern and proper resource reservation (just as C-Score), so how deadline could play a role in this mechanism?

Best
Xuesong

From: detnet [mailto:[e-mail]] On Behalf Of Jinoo Joung
Sent: Tuesday, November 21, 2023 3:08 PM
To: [e-mail]
Cc: [e-mail]
Subject: Re: [Detnet] Validity of Deadline based forwarding


Dear Shaofu,
Thanks for the response.

I think we have made an agreement to a great degree.
If I may summarize what you have concluded:

1. The in-time mode, with latency compensation, can suffer from the uncertainty caused by burst accumulation.
2. Therefore it should be deployed with care, and is recommended only in small networks, where the burst accumulation issue is not serious.
3. The on-time mode should be used in large networks.

Great. I agree.
However, I would like this to be stated clearly in 15. Deployment Considerations, or elsewhere this would fit into.

Best regards,
Jinoo



On Tue, Nov 21, 2023 at 12:41 PM <[e-mail]<mailto:[e-mail]>> wrote:



Hi Jinoo,



Please see inline #PSF6.



Regards,

PSF




Original
From: JinooJoung <[e-mail]<mailto:[e-mail]>>
To: 彭少富10053815;
Cc: [e-mail]<mailto:[e-mail]> <[e-mail]<mailto:[e-mail]>>;
Date: 2023年11月20日 17:34
Subject: Re: [Detnet] Validity of Deadline based forwarding

Hello Shaofu,
Thanks again for the quick response, and your hard work.
It is much easier for me without examples. :)

So in essence, the latency compensation sorts a packet according to its "ideal arrival time (AT)",
which is defined by AT_i_h(p) = AT_i_0(p) + sum(d_i_k over k=0 to h),

where AT_i_h(p) is the ideal arrival time at node h of packet p in flow i.

#PSF6: Yes, but a minor correction is that the packets are sroted in the scheduler queue according to their "ideal departure time", because the item "sum(...)" contains d_i_h itself. As we discussed before, "ideal arrival time" is used to represent egligible arrivals and compare with regulation result, and eligible arrival time at node h plus d_i_h equals to the ideal departure time from node h.

And the packets are served according to the service order decided by the AT values.

(BTW, this is similar to C-SCORE which sorts packets according to their ideal finish time (FT) values.)

#PSF6: Yes, they have the similar idea, except with different algorithms to calculate the rank value due to the basic difference between these two proposals, i.e., one is delay based, and the other is rate based.

Now let's revisit my question:
How do you guarantee a'_i(t) to be the same as a_i_0(t) with the latency compensation?

Now a more appropriate wording for the question would be:
How do you guarantee the regulated arrival process, with the AT-based sorted queue?
(BTW, I think the latency compensation is not a proper name for the scheme.)

Note that even C-SCORE, which uses the sorted queue with FT, cannot guarantee the reproduction of the regulated arrival process.

#PSF6: We may think the packets sorted in the queue with ideal departure time as a virtual regulation, because the rank distance between the adjacent packets of the flow i is exactly maintained consistently with the corresponding interval between these two adjacent packets on the flow entrance node. There is no need to require that this virtual regulation and a real regulation component must have exactly the same result, as long as they are both less than A_i(t).

Not sure if I understand your revised quesiton.

I guess you may otherwise still worry about burst accumulation in the case of in-time mode ? Please refer to section "15.  Deployment Considerations",  even in the case of in-time mode, if the network include few hops (that means burst accumulation issues is not serious), operators may still choose in-time mode to get a ASAP-low E2E latency. Otherwise, with a large hops, on-time mode can be configured.


Before answering my question, you may consider the fact that these schemes can be performed with the on-time mode.
I feel this scheme fits well with the on-time mode.
Then the burst accumulation can be avoided, and the admission condition can be checked as well.

#PSF6:  Yes, the sorted queue can be configured to work in the on-time mode, or combined with a pre calendar queue with on-time mode to absorb E (please refer to the 118-presentation slides).




Best,
Jinoo


On Mon, Nov 20, 2023 at 4:46 PM <[e-mail]<mailto:[e-mail]>> wrote:



Hi Jinoo,



Please see inline #PSF5.



Regards,

PSF




Original
From: JinooJoung <[e-mail]<mailto:[e-mail]>>
To: 彭少富10053815;
Cc: [e-mail]<mailto:[e-mail]> <[e-mail]<mailto:[e-mail]>>;
Date: 2023年11月20日 12:40
Subject: Re: [Detnet] Validity of Deadline based forwarding
_______________________________________________
detnet mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/detnet

Hello Shaofu,
Great. We are getting consensus.

I told you, in the first mail, that if flows are regulated then everything is OK.
Let me summarize again what we have agreed upon.

1. Burst accumulation means an accumulation of bursts of packets within a flow.
2. Burst accumulates in the in-time mode.
3. Admission condition check is necessary at every node.
4. That admission condition is Equation 1 (sum{A_i(t-d_i) for all i} <= C*t).
5. A_i(t) is defined to be the arrival constraint function of flow i.
6. a_i(t) is defined to be the arrival process of flow i.
7. a'_i(t) is defined to be the REGULATED arrival process of flow i.
8. A_i(t) should be larger than a'_i(t), i.e. a'_i(t, t+tau) < A_i(0,tau), for any t>0 and tau >0.

#PSF5: Thank you again for this summarization, and this also reminds me of the need to document these summaries so that people can better understand this proposal.


Then a'_i(t) should remain the same across all the nodes, i.e. a'_i_h(t) = a_i_0(t).
And so does A_i(t).
Therefore condition 4 can be tested.

My question is then: How do you guarantee a'_i(t) to be the same as a_i_0(t) with the latency compensation?

Remember, that the latency compensation is work-conserving, while a regulation is not.

#PSF5: First, my repeated statement is that it is in-time mode, but not latency compensation (in fact it can be combined with on-time mode), to get work-conserving behavior. Anyway, this may just be a minor improper wording, and I know your key concern is how to guarantee a'_i(t) by latency compensation.

Let us denote the arrival pattern (after regulation) face by the shceduler on the flow entrance node as arrival_pattern_0, which contains a sequence of packets with varaint of intervals between adjacent packets. We say that arrival_pattern_0 is eligible arrivals because its arrival curve is less than A_i(t).

Then we can easily get a conclusion that arrival_pattern_1 = arrival_pattern_0 + d_i_0 is also eligible arrivals because its arrival curve is also less than A_i(t). Here, arrival_pattern_0 + d_i_0 means that the arrival time (at the schedulier of flow entrance node) of each packet in arrival_pattern_0 is added with d_i_0 that is the delay bounds on the flow entrance node. In fact, arrival_pattern_1 is the eligible arrivals on the second node (assuming no link delay and intra node forwarding delay for simplicity). So, how did latency compensation get arrival_pattern_1 ?

·         For any packet p of flow i, denote its arrival time at the scheduler of the flow entrance node as time_p_0, and it may be served by the scheduler with queuing delay in the range from 0 to a delay bounds d_i_0. Suppose the queuing delay is q, then packet p will actually arrive at the second node at time time_p_0 + q (i.e., the actual arrival time at the second node) . And importantly, a latency deviation E = d_i_0 - q is also carried in the sending packet.

·         On the second node, packet p will NOT be served based on its actual arrival time (otherwise it is FIFO based scheduling). Instead, it recovery its eligible arrival time based on latency compensation, that is, eligible arrival time = actual arrival time + E =  time_p_0 + q + d_i_0 - q = time_p_0 + d_i_0. Therefore we have arrival_pattern_1 = arrival_pattern_0 + d_i_0.

Similarly, we have:

arrival_pattern_2 = arrival_pattern_0 + d_i_0 + d_i_1 for the third node,

arrival_pattern_3 = arrival_pattern_0 + d_i_0 + d_i_1  + d_i_2 for the fourth node,

and so on.

On any node h, packet p will be sorted in the queue based on its eligible arrival time plus d_i_h, i.e., time_p_0 + d_i_0 + ... + d_i_h and scheduled.


Best,
Jinoo


On Mon, Nov 20, 2023 at 12:58 PM <[e-mail]<mailto:[e-mail]>> wrote:



Hi Jinoo,



Thank you for summarizing some of the discussion results, that is great.

Please see inline #PSF4.



Regards,

PSF




Original
From: JinooJoung <[e-mail]<mailto:[e-mail]>>
To: 彭少富10053815;
Cc: [e-mail]<mailto:[e-mail]> <[e-mail]<mailto:[e-mail]>>;
Date: 2023年11月17日 19:50
Subject: Re: [Detnet] Validity of Deadline based forwarding
Hello Shaofu,
It seems that we have little common understanding.
For example, you claim that in the last example scenario the fixed packet inter-arrival time produced by a regulator is just a special case.
But, it is a WRONG example to me, because a regulator cannot produce such a fixed inter-arrival time.

So, let's not bother with such a lengthy example.
Let's start with what we have agreed upon.

The facts we agree so far are:
1. Burst accumulation means an accumulation of bursts of packets within a flow.
2. Burst accumulates in the in-time mode.
3. Admission condition check is necessary at every node.
4. That admission condition is Equation 1 (sum{A_i(t-d_i) for all i} <= C*t).
5. A_i(t) is defined to be the arrival constraint function of flow i.


If you do not agree, please let me know, so that we can start all over again. :)

#PSF4: Agree.




I would like to add two more facts.

6. a_i(t) is defined to be the actual arrival process of flow i.
7. A_i(t) should be larger than a_i(t), i.e. a_i(t, t+tau) < A_i(0,tau), for any t>0 and tau >0.


These Facts 6 and 7 (and Fact 4) are described in Eq (1), Section 2 Traffic Model, in the paper [RPQ] you refer to in your draft.

[RPQ] "Exact Admission Control for Networks with a Bounded Delay
Service", 1996, <https://ieeexplore.ieee.org/document/556345/>.

#PSF4:  There is a slight difference between facts 6/7 you provided and that of the [RPQ] paper, however, this slight difference caused your following question. Please note in [RPQ] paper, a_i(t), faced by scheduler, is the actual arrivals that has be REGULATED and never contains burst accumulation, and A_i(t) is the upper limit of this regulated actual arrivals of flow i.

If I understand your point correctly, you may say that a_i(t) is the actual arrivals and may contain burst accumulation, and even in the case of burst accumulation it should still meet a_i(t, t+tau) < A_i(tau). No, this is not the case.

So, I try to update your facts 6/7 as below:

·         6. a_i(t) is defined to be the actual arrival process of flow i that faced by scheduler and has not been regulated in the local node.

·         7. A_i(t) is defined to be the constraint funciton of flow i, and it should be larger than the regulated a'_i(t), i.e. a'_i(t, t+tau) < A_i(0,tau), for any t>0 and tau >0.




Let's define a_i_h(t) as the actual arrival process of flow i at node h.

Similarly let d_i_h be the delay bound of flow i at node h.

#PSF4: For simplicity of encoding, we would like to use the a single delay bound d_i for flow i on each node h (h=1, 2,..., H). However, if we don't care the encoding efficiency, it is also possible to support different d_i_h on different node.

Ok, we can just disccuss based on different d_i_h for your convinience.



Now, a_i_h(t) is different from a_i_0(t) with Fact 2, where 0 is the entrance node of flow i.

#PSF4: Yes.



Thus A_i_h(t) has to be different from A_i_0(t), because of Fact 7.

#PSF4: No. According to factor 5 mentioned above, A_i_h(t) is the constraint function of flow i, it is used to give upper limit of eligible arrival pattern, that is, it is preset and determined, and independent of actual arrivals a_i_h(t).

If this point is not easy to get, please consider the traditional bandwidth reservation case, where, a reserved bandwidth R (which is preset and determined) is provided to flow i, but on the intermediate node, the actual arrivals of flow i, due to burst accumulation, may have an actual arrival rate r exceeding R. Do you think in this case R should be dynamically changed to a large value to still meet r < R ? My answer is: no, what we should do is just to get a rate-controlled r' to meet r' < R if we want to get some performance of scheduling.

In brief, A_i_h(t) is a reserved constraint function, it is the upper limit of the eligible arrivals a'_i_h(t), and the actual arrivals a_i_h(t) should firstly convert to eligible arrivals a'_i_h(t) by some methods (such as regulation, latency compensation).



Therefore at node h, the condition in Fact 5 becomes sum{A_i_h(t-d_i_h) for all i} <= C_h*t.
My question: How do you obtain A_i_h(t - d_i_h)?

#PSF4: See the above explanations, A_i_h(t - d_i_h) is a preset and determined constraint function of flow i.


Please show me NO example. :)
Also please avoid using the terms that are not directly related,
such as delay level, delay resource pool, latency deviation, etc.

#PSF4: If you have some more suitable terms, please share them to us and we can update the document. For example, we think a mechanism provide multiple classes(or levels) with different delay bounds is a very practical requirement, that is why the term "delay level" introduced.




Best regards,
Jinoo


On Fri, Nov 17, 2023 at 7:02 PM <[e-mail]<mailto:[e-mail]>> wrote:



Hi Jinoo,



Please see further explanations inline #PSF3.



Regards,

PSF


Original
From: JinooJoung <[e-mail]<mailto:[e-mail]>>
To: 彭少富10053815;
Cc: [e-mail]<mailto:[e-mail]> <[e-mail]<mailto:[e-mail]>>;
Date: 2023年11月16日 22:19
Subject: Re: [Detnet] Validity of Deadline based forwarding
Hello Shaofu,
I appreciate the detailed explanation.
I also appreciate that you admit your misunderstandings.

But I still think you are missing some important points.

Even if the packets are sorted according to the "ideal" arrival time,
the actual service is work-conserving, then the burst accumulates, and the A_i(t) in Equation 1 changes.
Your "Ideal" arrival time is just the service order.
Thus the max burst changes over hops. How do you find the altered max burst? That's the point.

Please see more inline with JJ2.

Best,
Jinoo

On Thu, Nov 16, 2023 at 1:03 PM <[e-mail]<mailto:[e-mail]>> wrote:



Hi Jinno,



Thanks for your insightful questions.

Please see more explanation inline #PSF2.



Regards,

PSF




Original
From: JinooJoung <[e-mail]<mailto:[e-mail]>>
To: DetNet WG <[e-mail]<mailto:[e-mail]>>;
Date: 2023年11月13日 19:21
Subject: [Detnet] Validity of Deadline based forwarding
_______________________________________________
detnet mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/detnet

Hello Shaofu,

I have a question for clarification on the admission criteria (or the schedulability condition) of the Deadline based forwarding.
Let's consider only the In-time mode operation with PIFO implementation, for simplicity.

#PSF: In the case of in-time mode, packets may be sent before its deadline, but never exceed its deadline. I know you suspect that this conclusion may not hold true on the intermediate nodes, that's okay. Let's consider this conclusion on the flow entrance node first. I will further explain the behavior on the intermediate nodes later.


According to your draft, the admission is decided based on Equation 1, which is
sum{A_i(t-d_i) for all i} <= C*t,
where A_i(t) is the arrival constraint function of the flow i.
In the flow entrance node, this A_i(t) can be obtained from the flow specification (with max burst and arrival rate).

#PSF: Yes.


However, A_i(t) changes as the flow traverses hops, because of the burst accumulation.
How it will change is difficult to know, since it is a function of other flows' parameters as well.
Thus, in Options 1 and 2, you suggested the shaping (or regulation) function to be used in core nodes,
to enforce A_i(t) to become the initial arrival process,
so that we can test the admission condition (Equation 1) even in core nodes.

#PSF: Yes. But one thing to note is that the purpose of the re-shaping for a specific flow is to avoid accumulation between multiple bursts of that flow itself, rather than avoiding aggregation from other flows. Burst aggregation (i.e., flow aggregation) is natural, and we need to consider the demand for burst aggregation in the resource reservation process.


JJ: Sure. The burst accumulation always means the accumulation of bursts of packets within a flow.


Unfortunately, this approach needs per-flow state maintenance, therefore not scalable.
So, in Options 3 and 4 you suggested the "Latency compensation", as an alternative solution to the shaping.

How can this latency compensation apply to Equation 1, or
how do you check the admission condition in Option 3 or 4?

#PSF: In the case of latency compenstation (option 3/4), there is no maintenance of admission conditions for each flow, and also no admission condition check, on the intermediate node. Packets are automatically sorted according to "rank = arrival time + planned residence time (D) + latency deviation (E)" when PIFO used.
JJ: No admission control? That is what I've never heard of.
You cannot guarantee an arbitrarily small latency bound.
The paper you refer to (at the bottom of the email) is the seminal work that started EDF,
and it clearly states that several tests are necessary in order for EDF to work effectively.
Equation 1 (sum{A_i(t-d_i) for all i} <= C*t) is a more advanced test, which should be met at EVERY node.

#PSF2: Sorry, I misundertand "admission condition on the control plane" you mentioned as "admission control on the dataplane", since I attempt to point out the difference between option-1/2 and option-3/3 on the dataplane in the context of the previous question discussion. You are right that Equation-1 must be met at every node, during the processing of path computation & resource reservation on the control plane.



JJ2: Thank you for admitting the misunderstanding.

#PSF3: This is what I should do, to ensure that we are talking about the same thing. : )


I suspect that the latency compensation does not make Equation 1 to be usable in core nodes.
By utilizing the delay budget obtained from the previous nodes,
the latency compensation can only make more packets "eligible".
It is also unclear how to distinguish eligible and ineligible packets, but it is not important to me.

#PSF: As mentioned above, in the case of in-time mode, most arrivals may be ineligible (due to sending before their deadline), so they may have a positive E, and latency compensation will punish the packet to maintain a virtual time interval with the previous packet belonging to the same flow (as the evenly distributed result on the flow entrance node). For example, packet-1 and packet-2 belongs to the same flow, on the flow entrance node, packet-1 sent first, and 100us later packet-2 sent. So the virtual time interval between packet-1 and packet-2 is 100 us. Ideally, packet-1 arrived at a core node, and 100us later packet-2 arrived that core node. However, due to in-time scheduling behavior, packet-2 may imediately arrive when packet-1 arrived (e.g, on all upstream nodes, packet-1 always sent just at its deadline, while packet-2 is lucky to send without queueing delay), in this case, E of packet-2 = E of packet-1 + 100us. Packet-2 will be automatically sorted after packet-1, with a virtual distance of 100us.


JJ: You can always come up with a simple example that works. But it should be generalized.
Moreover, the virtual time interval between packets may not be kept, because of the work-conserving behavior,
and that is the cause of the burst accumulation. The arrival constraint function in Equation 1 will be changed as hops by.

 #PSF2: The draft provides some generalized description (see 6.5.  Scheduled by Allowable Queueing Delay), but I am not sure if it meets your expectations. I always think that some simple examples can help people quickly understand this proposal. Note that Equation-1 is based on the ideal arrivals, but not the actual arrivals. Yes, in the case of in-time mode, the actual arrivals may cause burst accumulation, but we can pick out eligible packets to serve, that is, the actual arrivals are sorted in the queue based on their ideal arrive time rather than their actual arrive time. Below, I will provide a more general example. If it seems too long, I apologize...

JJ2: There is no "ideal" arrival time in the in-time mode. A packet may conform to the flow's arrival curve or not. That's it.

#PSF3: There is. In fact, the ideal arrival time is independent with in-time or on-time mode. The ideal arrive time is a bit similar with virtual FT in your C-SCORE solution, i.e., the virtual FT of the upstream node is the ideal arrive time of the local node (assuming no link delay).





·         Starting from Option 1/2, which we have reached a consensus on.

Suppose there are M flows, for flow-i, i=1,...,M, with the help of regulation on the flow entrance node, the arrival pattern to the scheduler on the entrance node looks like that time interval between the adjacent packets is x. That is to say, the ideal arrival pattern of flow-i on the first node is:

The ideal arrived time of packet-1@flow-i is T_i1;

The ideal arrived time of packet-2@flow-i is T_i1+x;

The ideal arrived time of packet-3@flow-i is T_i1+2x;

and so on;

JJ2: Again, we cannot define such a concept of "ideal" arrival time, in regulated flows. But anyway let's assume the packets arrived with a fixed inter-arrival time.

#PSF3: It would not be difficult to accept ideal arrival time if you can accept virtual FT (ideal departure time) in your C-SCORE. Yes, this is still an example that arrived with fixed intervals, one can certainly create another example with non-fixed intervals, that is, the service flow will not always generate packets to consume its total reserved bandwidth.





·         Based on this ideal arrival pattern, each packet of flow-i will be serivced before its deadline on the first node, right ?

And, even due to in-time scheduling mode on the first node, again with the help of regulation on the second node, the arrival pattern of flow-i to the scheduler on the second will be still maintained as:

The ideal arrived time of packet-1@flow-i is T_i1';

The ideal arrived time of packet-2@flow-i is T_i1'+x;

The ideal arrived time of packet-3@flow-i is T_i1'+2x;

and so on;
JJ2: You don't seem to understand what a regulation is. It does not make a packet inter-arrival time a fixed value.
The inter-arrival times of packets may change a lot, but they can still conform to the arrival curve.

If the packets show such a fixed pattern, then it is a damper, or we should call it the on-time mode.

#PSF3: Please note that this is still an example that the flow arrived with fixed intervals with max packet size to consume its total reserved bandwidth. As you know when we analysis latency it is better to based on the worst case. In this case, regulation (with parameter CBS = max packet size, CBR = service rate of flow) will cause the interval between adjacent packets to meet interval = max packet size / service rate. You can certainly image another non-worst case example, e.g,, the arrival patter on the flow entrance node look like a max-size packet following by a minimul-size packet, to get non-fixed interval.  The example based on fixed intervals looks more intuitive and clear (see above +x, +2x, +3x, ...).



·         Based on this ideal arrival pattern, each packet of flow-i will be serivced before its deadline on the second node, right ?

Then, after admission condition check, each flow, and on each node, will be serviced before its deadline, right ?
JJ2: What you are claiming is that "If the arrival pattern is the same as the first node, the deadline can be met at the second node."

Regulation does not make the same arrival pattern. You are using something very different. Something like a damper.

#PSF3: See the above explanation. In this example, we actually have same pattern between the second node and the first node, and this is a special regulation result that happens to look like damper result. Again, you can image another example, the analysis is similar.  The main point is rate-controlled on the second node whether for fixed interval example or non fixed interval example, and Equation-1 still meet on the second node.





·         Now we come back to Option 3/4.

With the help of regulation on the flow entrance node, the ideal arrival pattern of flow-i on the first node is:

The ideal arrived time of packet-1@flow-i is T_i1;

The ideal arrived time of packet-2@flow-i is T_i1+x;

The ideal arrived time of packet-3@flow-i is T_i1+2x;

and so on;

Based on this ideal arrival pattern, each packet of flow-i will be serivced before its deadline on the first node, right ?

And, due to in-time scheduling mode on the first node, the actual arrival pattern of flow-i to the scheduler of the second node may be different with the ideal one. But with the help of latency deviation (E), the ideal arrival pattern of flow-i can be recovered as (for simplicity, assuming both intra-node forwarding delay and link delay are 0):

·         The ideal arrived time of packet-1@flow-i is T_i1 + D; where D is the planned residence time.

The ideal arrived time of packet-2@flow-i is T_i1 + x + D;

The ideal arrived time of packet-3@flow-i is T_i1 + 2x + D;

and so on;

·         The packets are sorted in the scheduler queue based on this ideal arrival time, each packet of flow-i will be serivced before its deadline on the second node, right ?

Then, after admission condition check, each flow, and on each node, will be serviced before its deadline, right ?
JJ2: Even if the packets are sorted according to the "ideal" arrival time, the actual service is work-conserving, then the burst accumulates, and the A_i(t) in Equation 1 changes.
Ideal arrival time is just the service order.
The same can be said to the C-SCORE using Finish Time as the service order.
The burst also accumulates in C-SCORE.
The only difference is that in C-SCORE, the admission condition depends only on the service rate,
while in EDF the admission condition A_i(t) also depends on the max burst, which accumulates over hops.


I do hope you understand my points.

#PSF3: We have already gotten consensus on burst accumulation in the case of in-time mode. Please note that the max burst of A_i(t) is the upper limit of eligible max burst of delay level di, you can not treat the total amount of burst accumulation of actual arrivals (including ineligible arrivals) as eligible. The packets are sorted based on rank = ideal arrival time + D, where, rank does not only indicate the service order, but also the deadline. So, if we look at packets in the burst-accumulation (although they are back-to-back), some ineligible packets will have a large rank value (its deadline is more later), and will not crush the scheduling power of the scheduler.

#PSF3: Yes, the virtual FT of C-SCORE has the similar idea of the above rank value. And as you know the basic difference between them is that one is rate based scheduling and the other is delay based scheduling, and may cause significant difference in E2E latency.




As you have specified in the presentation slides,
if some of the packets become ineligible with Option 3 or 4,
then these packets will be served later than the eligible packets,
and are not guaranteed latency bounds.
But it is not the packets' faults to become ineligible.

#PSF: An ineligible packet (see the packet-2 in the above example) will certainly be served later than the eligible packet (see the packet-1 in the above example) that belongs to the same flow. However, it is not true between flows, e.g, packet-2 may still be served before the eligible packet-x from other flows because packet-x may have a large planned residence time (D).
JJ: Packet service order within a flow should not be altered. So whether they are eligible or not, the service order is not changed.
For packets from different flows, an ineligible packet can be served before an eligible one?
Then your argument "Eligible packets served earlier than ineligible packets" seems contradictory.
Please clarify.

 #PSF2: As we know, burst accumulation may cause an eligible packet to be serverd after an ineligible packet, and make latency estimation be difficult. This argument (in the slides) attempts to point out the fact that the scheduling of eligible packets is not affected by ineligible packets in the case of latency compensation. The word "earlier" is indeed not suitable, and leads to misunderstandings. Thanks.





Note that the relationship between multiple flows is the relationship of burst aggregation, that is to say, we assume that all flows arrived asynchronously, and based on the resource reservation, <packet-1, packet-2, ...> of a specific flow belongs to a specific delay level may reserve its dedicated resources.
JJ: "Packets of a specific flow may reserve dedicated resources."
Could you elaborate more? I am not sure what resources are here.
It would not mean a service rate, since it is a deadline based scheduler.

It would not mean a buffer space, since it has nothing to do with the latency.

#PSF2: Please refer to section "2.2.  Delay Levels Provided by the Network" for the resource definition, that is also related with your concerns of "admission condition check". In brief, we introduce delay resource pool (including burst & bandwidth) for each delay level. As you know, although deadline mechanism is delay based scheduling, the defined delay levels must have their arrival constraint funciton (e.g, leaky bucket funtion) to meet the schedulability condition. The leack buckt function (b+r*t) of each dealy level will give the uper limit of b & r.

JJ2: The b changes over hops. How do you find the changed b? That's the point.

#PSF3: I am not sure what meaning of "changes" you mentioned. If the meaning is b changes due to burst accumulation, my answer is: No, b is a preset burst resource pool for specific delay lavel on each link. If the meaning is different b on different hop, my answer is: Yes, each link may have different burst resource pool for specific delay level just because of differenct link capacity (bandwidth).





Packet-1 may be conflict with other eligible packets from the same delay level, but all of them will be sent before the deadline related with that delay level; Packet-2 (even if it arrived back-to-back with packet-1 to cause burst accumulation) will not affect the scheduling of packet-1 and other eligible packets from other flows belongs to the same delay level. After 100us, packet-2 became the eligible protagonist of the party, however, it may send before that time (due to in-time scheduling behavior).

JJ: I am not sure what the "delay level" is. They have delay bounds. Should these bounds have some kind of discrete levels?

#PSF2: See the above explanation. Yes, these delay levels are discrete. The interval between adjacent delay levels can be flexibly configured.





Now, back to your statement "are not guaranteed latency bounds. But it is not the packets' faults to become ineligible. ", do you think that the punish time of 100us that may be expienced by packet-2 will cause packet-2 exceed its deadline ? My answer is NO. The reason is similar to "the re-shaping delay will not cause a packet to violate its latency bounds".
JJ: Of course not in this simple example. But can it be generalized?
Re-shaping is non-work conserving, and can suppress the burst accumulation.

But latency compensation is work conserving and cannot suppress it.

#PSF2: Please see the above generalized example. Note that it is in-time mode (work conserving) to cause burst accumulation, while latency compensation provides method to recovery ideal arrival pattern even in the case of burst accumulation. You may have found that latency compensation may also combine with on-time mode in the document.


Can you still say Option 3 or 4 is a suitable solution?

#PSF: There are many respected predecessors in the academic community who have conducted extensive research in this direction. : )

Please see similar idea of latency compensation in this paper: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=a2018cc8993c3705e851480a1b75addc7ce6bc9b


You have to verify the "delay bound test" mentioned in the above paper for each node. (It is Theorem 1, Equation 10.)
This paper assumes that each node n can guarantee nodal delay d_n, and only then E2E latency bound D (sum of d_n) can be met.
How a node can guarantee d_n is what you have to provide.
I can assure you that guaranteeing a nodal delay is the difficult part.

#PSF2: Yes, the test proceduire in this paper is exactly corresponding to the path computation & resource reservation on the control plane that we want to do. According to Equation 1 that we get consensus, if any flows of any delay levels meet their arrival constraint function, any packet's deadline can be met. This is a mature conclusion of EDF.


JJ2: The whole point is that the term A_i(t), in Equation 1, cannot be easily obtained.

How do you obtain A_i(t)? Please explain.

#PSF3: Please refer to section "3.2.1.  Conditions for Leaky Bucket Constraint Function", for example, we may firstly preset some delay levels, then set b_1 as C*d1 (for simplicity, not consider M), and r_1 as some value less than C for delay level d1, and recursively set resource pools for other delay levels.






Please note that the paper also assumes that minimum packet interarrival time is large enough.

I.e. no burst is assumed.

#PSF2: This is not the limitation for this paper. Also, we have not this limitation, please refer to section "2.4.  Relationship Between Service Burst Interval and Delay Level".




Best regards,
Jinoo