Re: [Detnet] Validity of Deadline based forwarding

peng.shaofu@zte.com.cn Fri, 17 November 2023 10:02 UTC

Return-Path: <peng.shaofu@zte.com.cn>
X-Original-To: detnet@ietfa.amsl.com
Delivered-To: detnet@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DE931C14CF09 for <detnet@ietfa.amsl.com>; Fri, 17 Nov 2023 02:02:30 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H5=0.001, RCVD_IN_MSPIKE_WL=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id MdIjj4MY2cou for <detnet@ietfa.amsl.com>; Fri, 17 Nov 2023 02:02:26 -0800 (PST)
Received: from mxhk.zte.com.cn (mxhk.zte.com.cn [63.216.63.40]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D3FF4C15108E for <detnet@ietf.org>; Fri, 17 Nov 2023 02:02:24 -0800 (PST)
Received: from mse-fl1.zte.com.cn (unknown [10.5.228.132]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mxhk.zte.com.cn (FangMail) with ESMTPS id 4SWsrt5KCnz8XrRG; Fri, 17 Nov 2023 18:02:22 +0800 (CST)
Received: from njy2app02.zte.com.cn ([10.40.13.116]) by mse-fl1.zte.com.cn with SMTP id 3AHA2BiS083385; Fri, 17 Nov 2023 18:02:11 +0800 (+08) (envelope-from peng.shaofu@zte.com.cn)
Received: from mapi (njb2app07[null]) by mapi (Zmail) with MAPI id mid201; Fri, 17 Nov 2023 18:02:14 +0800 (CST)
Date: Fri, 17 Nov 2023 18:02:14 +0800
X-Zmail-TransId: 2aff65573a267d2-0b326
X-Mailer: Zmail v1.0
Message-ID: <202311171802149033364@zte.com.cn>
In-Reply-To: <CA+8ZkcQ_Wk+M98PzTJrPiKKhBdQ=Yv+Z_0HmASjjTNq=xYgpag@mail.gmail.com>
References: CA+8ZkcRa4Frzh15vTOizEi9A8xSa0QxieLW_d5OGOwuVdde+iA@mail.gmail.com, 202311161203216247675@zte.com.cn, CA+8ZkcQ_Wk+M98PzTJrPiKKhBdQ=Yv+Z_0HmASjjTNq=xYgpag@mail.gmail.com
Mime-Version: 1.0
From: peng.shaofu@zte.com.cn
To: jjoung@smu.ac.kr
Cc: detnet@ietf.org
Content-Type: multipart/mixed; boundary="=====_001_next====="
X-MAIL: mse-fl1.zte.com.cn 3AHA2BiS083385
X-Fangmail-Gw-Spam-Type: 0
X-Fangmail-Anti-Spam-Filtered: true
X-Fangmail-MID-QID: 65573A2E.000/4SWsrt5KCnz8XrRG
Archived-At: <https://mailarchive.ietf.org/arch/msg/detnet/RPyKbnQNGUOQDpGM1s1Tbz-mkts>
Subject: Re: [Detnet] Validity of Deadline based forwarding
X-BeenThere: detnet@ietf.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: Discussions on Deterministic Networking BoF and Proposed WG <detnet.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/detnet>, <mailto:detnet-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/detnet/>
List-Post: <mailto:detnet@ietf.org>
List-Help: <mailto:detnet-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/detnet>, <mailto:detnet-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 17 Nov 2023 10:02:31 -0000

Hi Jinoo,

Please see further explanations inline #PSF3.

Regards,
PSF


Original


From: JinooJoung <jjoung@smu.ac.kr>
To: 彭少富10053815;
Cc: detnet@ietf.org <detnet@ietf.org>;
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 <peng.shaofu@zte.com.cn> wrote:



Hi Jinno,

Thanks for your insightful questions.
Please see more explanation inline #PSF2.

Regards,
PSF







Original

From: JinooJoung <jjoung@smu.ac.kr>
To: DetNet WG <detnet@ietf.org>;
Date: 2023年11月13日 19:21
Subject: [Detnet] Validity of Deadline based forwarding

_______________________________________________
detnet mailing list
detnet@ietf.org
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