Re: [Detnet] Validity of Deadline based forwarding

Jinoo Joung <jjoung@smu.ac.kr> Thu, 16 November 2023 14:20 UTC

Return-Path: <jjoung@smu.ac.kr>
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 0336FC14F747 for <detnet@ietfa.amsl.com>; Thu, 16 Nov 2023 06:20:17 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.903
X-Spam-Level:
X-Spam-Status: No, score=-0.903 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001, URI_DOTEDU=1] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=smu-ac-kr.20230601.gappssmtp.com
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 iQDd0U8d2O6V for <detnet@ietfa.amsl.com>; Thu, 16 Nov 2023 06:20:13 -0800 (PST)
Received: from mail-pf1-x433.google.com (mail-pf1-x433.google.com [IPv6:2607:f8b0:4864:20::433]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id AF6FCC14CF05 for <detnet@ietf.org>; Thu, 16 Nov 2023 06:19:28 -0800 (PST)
Received: by mail-pf1-x433.google.com with SMTP id d2e1a72fcca58-6bee11456baso769719b3a.1 for <detnet@ietf.org>; Thu, 16 Nov 2023 06:19:28 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=smu-ac-kr.20230601.gappssmtp.com; s=20230601; t=1700144367; x=1700749167; darn=ietf.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=2vWpL7czVQSYCGN64/jn+m6+HBmAUE8D/OJxqKjHQM8=; b=0n3BNSciW2sPfM9/NJ55uXEEAfTKe3eunV0pRIfRriwtZbuUblXn83oDoTYmz4AIgJ LWkeCZZczXYM08/nhgoEIBKULei/H6voU1o4qM01x+ls/80zMXEsS0mQfkN3ZkaSmM3X G0lGnkRffuVM3LtYicg92cnh/oqr/u9/T3KQZBqxlIr/xO3mmqKoZpTa73+Q3GAkb5fg lTjJ7rHAPxHNAFHXERh35YBKPe7ts4zAusdb24iJVo8Z+W6igBappjGbMK/fR+WMRMm/ ofg/Mdm3nze/z5G1MUvArEWVZYCh8jTv9FLHSOyskSoOcC9pyuBau+75Rt3awcxSf+BM 5fQQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700144367; x=1700749167; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=2vWpL7czVQSYCGN64/jn+m6+HBmAUE8D/OJxqKjHQM8=; b=Kv2kpqWSA86l3f3wSP1A8e1SLfmwga5BLxNzQZ3eFMUCKsl/G1LDOtMjH4JjwbCBas nzXDXAI58NpmFeMSGs8Ot7DbmZIgsd/ceCuatrrBR/9lsXDUXz55mJDm+NuEca7tuSba n4HE9dG/EECCyIaOXKMmpd4l049uKADQgoXrUFwghC6DjvNs4gfoXtJZKLq09kdccloT XLxER5SeIgdz1UC9zAPsUVEgc8fTo7bPf0CwldKSwvpHFR4sBaP1QMcta6EnYU0a6Njy Z2wYlp+yRVbdMlUDtIfV4jNNLFDIdNnpSMZwVuTYjkRzpqwHxxjhnT0dZ2Mu6kUOMxga b5TA==
X-Gm-Message-State: AOJu0YwcInTDIFBd+9QTX5spM+Zy2pWHaNLy59WiNWwI5Gn+78I8gj6I sDVtp+GmZW+fQzOhQWdMiOqKM8seYQ2n05rXYm9mQWqLct2nr+pgiGQ=
X-Google-Smtp-Source: AGHT+IF1Ot65MPqPNd2mcqxzpr7Z8DFyejYKB4wRNldR54V7Q0aKwnjYXgyZPKFHyLAN25+M7zKTnQv1IEH/WCAvbVY=
X-Received: by 2002:a17:90b:4a01:b0:280:cd7b:1fa5 with SMTP id kk1-20020a17090b4a0100b00280cd7b1fa5mr13950408pjb.4.1700144367191; Thu, 16 Nov 2023 06:19:27 -0800 (PST)
MIME-Version: 1.0
References: <CA+8ZkcRa4Frzh15vTOizEi9A8xSa0QxieLW_d5OGOwuVdde+iA@mail.gmail.com> <202311161203216247675@zte.com.cn>
In-Reply-To: <202311161203216247675@zte.com.cn>
From: Jinoo Joung <jjoung@smu.ac.kr>
Date: Thu, 16 Nov 2023 23:19:19 +0900
Message-ID: <CA+8ZkcQ_Wk+M98PzTJrPiKKhBdQ=Yv+Z_0HmASjjTNq=xYgpag@mail.gmail.com>
To: peng.shaofu@zte.com.cn
Cc: detnet@ietf.org
Content-Type: multipart/alternative; boundary="00000000000012e34e060a45b509"
Archived-At: <https://mailarchive.ietf.org/arch/msg/detnet/RP-B3lEXU7JjMwBEMwt9GIDQnSQ>
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: Thu, 16 Nov 2023 14:20:17 -0000

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.

> 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.

>
>    -
>
>    *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.

>
>    -
>
>    *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.

>
>    -
>
>    *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.

>
>    -
>
>    *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.

>
> 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.

>
>
> *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*
>> <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.

>
> 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
>>
>>
>>
>