Re: [Detnet] Validity of Deadline based forwarding

Jinoo Joung <jjoung@smu.ac.kr> Mon, 20 November 2023 04:40 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 E2403C14CE47 for <detnet@ietfa.amsl.com>; Sun, 19 Nov 2023 20:40:05 -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_DNSWL_NONE=-0.0001, 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 NcTsoNGpobGI for <detnet@ietfa.amsl.com>; Sun, 19 Nov 2023 20:40:01 -0800 (PST)
Received: from mail-pf1-x42a.google.com (mail-pf1-x42a.google.com [IPv6:2607:f8b0:4864:20::42a]) (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 8E897C14CE36 for <detnet@ietf.org>; Sun, 19 Nov 2023 20:40:00 -0800 (PST)
Received: by mail-pf1-x42a.google.com with SMTP id d2e1a72fcca58-6c33ab26dddso3370185b3a.0 for <detnet@ietf.org>; Sun, 19 Nov 2023 20:40:00 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=smu-ac-kr.20230601.gappssmtp.com; s=20230601; t=1700455200; x=1701060000; 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=OIA6oQGDEZgDRcAIF9QJCw05doN8ud4HquMozdD4z8Q=; b=FKIYkyweKnKDLfLIwYeo+TLuc21yYBkqAnHyyrlKi2YnFM7hWYi2n8v5MV70MQOgFE N5a17zVafXlYU2sTA/i5TDhfEWPeXm+VleXKkIw1U8YIPzkLsZ/VTxTl87dhN7UM4eKD 03XNxL16foKmxbJokfov6ICmVwuWcezA5KqeuTVLyoOEtB29vyYsyXRzIw5qNwLbquRh LuBGQuZQbrmoj8LLkokKlpq64z2zC4Ep6C+NUU43I/qnnAoF6ElN2y+r9E46X4o6S7S1 PaxUW583bCEmhhzsC7i7Xh5V1sbNgV0dEFGWWaV63LyAAugxKnzUHvhflcgNbKGFqK52 rXGg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700455200; x=1701060000; 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=OIA6oQGDEZgDRcAIF9QJCw05doN8ud4HquMozdD4z8Q=; b=D7zap+t+MNPpbwnSFNb13jLgp3CU9Uhf52H9fpC/d/V1RBdDgB2LOon2NAsjoN06qn dPFB4r8nK1yRHTNCFvXXpxtRrj/Lar/vOwsFt+QBM6tdy1mOfpK8LEbMSa60EogXc/QV jzyfqWdZJijiSCSpWN8s07NNLMyImnJh5tDpQcAsOxJs7rSYdW4MP8YAvWq8qLzF2RXK waDOCgkqmv03GVT5FfeS+6uR02C9vb/cICXCVsQZL6upW5DCOh6v/wgmHiNcQLoEBxLD 7yL5aScEylZykIj4c6MgyRGADtgAsCz0fueiezbPfyKjwaAwE/MXsPRR8VRdVPkp1P7f hXFw==
X-Gm-Message-State: AOJu0YzOqiQg4aKrsSN0Rl2UcXhd9Rnypc+Wy0yGec2tf5YKmBm76uWm cDFyE7cZbxp8mKe/wtuXAVXhNvV3/PODxIX+ki6Yh8jPU3zxUh3fwgA=
X-Google-Smtp-Source: AGHT+IHMViTixP/jtR5EoSsxBTViID2iL1BtOU6HkwASIqyWNe1NHa9F2j/n+7okebV0mWa1SSTan+dJR9DpSx5WkxY=
X-Received: by 2002:a05:6a20:8e1a:b0:187:56f2:201f with SMTP id y26-20020a056a208e1a00b0018756f2201fmr5066151pzj.22.1700455199522; Sun, 19 Nov 2023 20:39:59 -0800 (PST)
MIME-Version: 1.0
References: <CA+8ZkcTZc0NU6kb57UJStwSLpW4Rw8U2GRSTvq2s2DvC1vjwvw@mail.gmail.com> <202311201158108513264@zte.com.cn>
In-Reply-To: <202311201158108513264@zte.com.cn>
From: Jinoo Joung <jjoung@smu.ac.kr>
Date: Mon, 20 Nov 2023 13:39:50 +0900
Message-ID: <CA+8ZkcSMdM4sQb5xVPuGyiuVufUEF-S4O6O2b+62uXvsPibwqQ@mail.gmail.com>
To: peng.shaofu@zte.com.cn
Cc: detnet@ietf.org
Content-Type: multipart/alternative; boundary="0000000000001fd5fd060a8e1405"
Archived-At: <https://mailarchive.ietf.org/arch/msg/detnet/VLMaFr7o2XEZECi0vpGDj-oWRoc>
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: Mon, 20 Nov 2023 04:40:06 -0000

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.

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.

Best,
Jinoo



On Mon, Nov 20, 2023 at 12:58 PM <peng.shaofu@zte.com.cn> wrote:

>
> Hi Jinoo,
>
>
> Thank you for summarizing some of the discussion results, that is great.
>
> Please see inline #PSF4.
>
>
> Regards,
>
> PSF
>
>
>
> Original
> *From: *JinooJoung <jjoung@smu.ac.kr>
> *To: *彭少富10053815;
> *Cc: *detnet@ietf.org <detnet@ietf.org>;
> *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 <peng.shaofu@zte.com.cn> wrote:
>
>>
>> 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*
>>>> <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
>>>>
>>>>
>>>>
>>>
>>
>