Re: [Detnet] Validity of Deadline based forwarding

Jinoo Joung <> Tue, 14 November 2023 08:57 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6AC92C151076 for <>; Tue, 14 Nov 2023 00:57:12 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -5.903
X-Spam-Status: No, score=-5.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_DNSWL_HI=-5, 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=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 4WMUPYjSmPf8 for <>; Tue, 14 Nov 2023 00:57:08 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4864:20::1033]) (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 (Postfix) with ESMTPS id 41DEFC151067 for <>; Tue, 14 Nov 2023 00:57:07 -0800 (PST)
Received: by with SMTP id 98e67ed59e1d1-27ddc1b1652so4847165a91.2 for <>; Tue, 14 Nov 2023 00:57:07 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20230601; t=1699952227; x=1700557027;; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=fLbXO8N4x9uExunf0p0P/Haykob+eAEyjGzhRcXK5g8=; b=0mQtz4bKlfkX9VQtUIiPT0e1ej7sQnaxlHQAYgc80dfmukPnX71GYQ+O1GuTBR6Z1s mR2TA+1gJarJ3TBZMZ91soSGp68ALPZMtTL7JOygMmH7Q6ifCta4ExVRDHnldTC4G2YK Bs9iQwd3ljX018H+1eTm5shVgjq7UqQ5kb32Uay2qAqCGGMp6ypdmabBAqJEBk8uBrNJ g4ZLWaGs5tUctHxV7WgdUjWO5XkcAAo4pRZJ0+aRlWRomECv5UrZ2QMiPeAInrAfcZw9 w/lGYBhGF4f1+O+O4W7bN3NLLcSP9JZ6hvARtRLSRvCuFLrYKv2wrJqwFf6QE6WZ6Wx+ AjUw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20230601; t=1699952227; x=1700557027; 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=fLbXO8N4x9uExunf0p0P/Haykob+eAEyjGzhRcXK5g8=; b=muVUPgJuMsJ2rCKkO15I78NleyPRZBuScewX6bOcNN9yxa9HPUURHpX3HUKGUGhjZK D7umzIhL262c2HaiaG/I6cHgMcIzxA0biS8OXcDaiFTEuXQdSIti/Ol5C2ZStNyog9kO wUpuT2HCsTM3w+Xel8ALf0+8G0aWFmAul1zrShYpyftlIxDegGZUmkSIpccVXn3SytId E4RESRI4p6JZbhgTUCt5eLUbA7Rq2bAijyirdGYTIin6tFOxUmRalV/+ZFRNR5TOHbZF yMp0BcdpbRDUeTqRiYfShExzBA+tb1tnksuiN6sHyhbbgV737onAEx5ADgKQNfkT7Au0 75TA==
X-Gm-Message-State: AOJu0YyZoHaFasZSqQ3Cgy7S5u0aCguP1ZEleE2oIKch4KfEZUcjdeoi 8R0yKajnbmmSi30vov8DgAJ4QHbXE7YEIts9TIATaqpPiW29jku5TYs=
X-Google-Smtp-Source: AGHT+IGwStkT3P9fLXiJlHwzWhuH5+AIrzWPK7trjS94cfknAcyFyLQc3J5ZPlaYS0t8cl9iSmP9Qj8s96V/jSItkKI=
X-Received: by 2002:a17:90b:1bc3:b0:281:e1:af1d with SMTP id oa3-20020a17090b1bc300b0028100e1af1dmr3060423pjb.18.1699952226617; Tue, 14 Nov 2023 00:57:06 -0800 (PST)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Jinoo Joung <>
Date: Tue, 14 Nov 2023 17:56:56 +0900
Message-ID: <>
Content-Type: multipart/alternative; boundary="0000000000009a5f9a060a18f8d4"
Archived-At: <>
Subject: Re: [Detnet] Validity of Deadline based forwarding
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: Discussions on Deterministic Networking BoF and Proposed WG <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 14 Nov 2023 08:57:12 -0000

Hello Shaofu,
Thanks for the kind reply.
I now understand better how you are trying to establish the solution.
However, my doubt does not get resolved. In fact,it grows.
Please see in-line for more questions, with JJ.

Thanks in advance.

On Tue, Nov 14, 2023 at 12:25 PM <> wrote:

> Hi Jinoo,
> Thanks for your reviews and questions.
> Please see inline #PSF.
> Regards,
> Original
> *From: *JinooJoung <>
> *To: *DetNet WG <>;
> *Date: *2023年11月13日 19:21
> *Subject: **[Detnet] Validity of Deadline based forwarding*
> _______________________________________________
> detnet mailing list
> 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.

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

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

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

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

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

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

Please note that the paper also assumes that minimum packet interarrival
time is large enough.
I.e. no burst is assumed.

> Best regards,
> Jinoo