DetNet Working Group Y. Ryoo Internet-Draft ETRI Intended status: Standards Track J. Joung Expires: 1 September 2025 Sangmyung University 28 February 2025 Non-work Conserving Stateless Core Fair Queuing draft-ryoo-detnet-nscore-00 Abstract This document specifies the framework and operational procedure for deterministic networking that guarantees maximum and minimum end-to- end latency bounds to flows. The solution has non-periodic, asynchronous, flow-level, non-work conserving, on-time, and rate- based functional characteristics, according to the taxonomy suggested by [draft-ietf-detnet-dataplane-taxonomy-02]. The packets are stored in the queue in ascending order of the ideal service start time, called Eligible Time (ET), and the ideal service completion time, called Finish Time (FT). The queued packets were forwarded between ET and FT in a non-work conserving manner. The ET and FT are calculated at the entrance node according to the packet size and rate of the flow. All subsequent core nodes are stateless and asynchronously compute ET and FT based on metadata received via packet headers. This mechanism is called non-work-preserving stateless fair queuing, which guarantees both E2E latency upper and lower bounds. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 1 September 2025. Ryoo & Joung Expires 1 September 2025 [Page 1] Internet-Draft N-SCORE February 2025 Copyright Notice Copyright (c) 2025 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1. Symbols Used in This Document . . . . . . . . . . . . . . 3 2.2. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 3 3. Requirements Language . . . . . . . . . . . . . . . . . . . . 3 4. N-SCORE Packet Scheduler Framework . . . . . . . . . . . . . 4 5. E2E latency and jitter bound . . . . . . . . . . . . . . . . 5 6. Operational Procedure . . . . . . . . . . . . . . . . . . . . 6 6.1. Operational Procedure in Entrance Node . . . . . . . . . 6 6.2. Operational Procedure in Core Node . . . . . . . . . . . 7 7. Capability Analysis . . . . . . . . . . . . . . . . . . . . . 8 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 9. Security Considerations . . . . . . . . . . . . . . . . . . . 9 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 10.1. Normative References . . . . . . . . . . . . . . . . . . 9 10.2. Informative References . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 1. Introduction A class of schedulers called Fair Queuing (FQ) limits interference between flows to the degree of the maximum packet size. In FQ, the ideal service completion time, called Finish Time (FT), of a packet is obtained from an imaginary system that can provide the ideal flow isolation. Applying this technique, the end-to-end (E2E) latency bound of a flow is similar to that of an ideally isolated system. Since calculating the FT of the current packet requires the FT of previous packets within the flow, this means that nodes must manage the state of the flow. The complexity of managing the state of a large number of flows can be a burden, so the proposed framework for large-scale deterministic networking is called work conserving Ryoo & Joung Expires 1 September 2025 [Page 2] Internet-Draft N-SCORE February 2025 stateless core fair queuing (C-SCORE), which generates FT for packets at the entrance node and marks FT in the packet to operate with stateless in core nodes. However, C-SCORE is a scheduler of work conserving approach, so it has an in-time characteristic. Therefore, this draft proposes a non- work conserving scheduler method by extending C-SCORE to have an on- time characteristic, called N-SCORE. The entrance node additionally obtains an ideal service start time, called an eligible time (ET), of the current packet based on the FT of the previous packet or the arrival time of the current packet. All of the nodes queued packets in ascending order of the ET and FT and forward the packet between ET and FT in a non-work conserving approach. N-SCORE is a method that guarantees not only the upper bound but also the lower bound of E2E latency by adding ET while using the information managed by the entrance node of the existing C-SCORE. 2. Terminology 2.1. Symbols Used in This Document FQ fair queuing FT finish time ET eligible time Fh(p) FT of the packet p at the node h Eh(p) ET of the packet p at the node h Ah(p) arrinal time of the packet p at the node h dh(p) maximum delay of the packet p at the node h ch(p) service complition time of packet p at the node h r(p) service rate of the packet p L(p) length of the packet p Rh link capacity of the node h Lhmax maximum packet length of the node h PDh propagation delay of the link h 2.2. Abbreviations 3. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. Ryoo & Joung Expires 1 September 2025 [Page 3] Internet-Draft N-SCORE February 2025 4. N-SCORE Packet Scheduler Framework Utilizing the concept of virtual clock (VC) scheduler, C-SCORE defines FT for packet p as F(p) = max{F(p-1), A(p)} + L(p)/r(p). (1) Where (p-1) and p are consecutive packets of the flow being observed, F(p-1) is the finish time of p-1, A(p) is the arrival time of p, L(p) is the length of p, and r(p) is the flow service rate. Flow exponents are omitted. In C-SCORE, the entrance node manages F(p-1) and obtains F(p) by comparing it with A(p). Then, it calculates F(p) of the next node and marks it in the packet header. The service period of packet p in each node is defined as (A(p), F(p)]. Assuming the link propagation delay is zero, an example of the packet service period at the entrance node and core node with the C-SCORE scheduler is illustrated as follows: A1(1) A1(2)A1(3)A1(4) | | | | V V V V <----1----> <----2---->F1(2) node 1 | F1(1) | <-------3------->F1(3) | | | <----------4---------->F1(4) | | | | A2(1) A2(2)A2(3)A2(4) | | | | V V V V <----------1--------->F2(1) node 2 <---------2---------->F2(2) <-------------3------------>F2(3) <-----------------4-------------->F2(4) Figure 1: C-SCORE packet scheduler service period The proposed N-SCORE framework introduces an additional parameter, ET (Eligible Time), which is used as the earliest possible packet service start time. Without requiring additional state management for ET, N-SCORE utilizes the information already managed by the entrance node in the existing C-SCORE to obtain ET and FT as follows: E(p) = max{F(p-1), A(p)} (2) F(p) = E(p) + L(p)/r (3) Ryoo & Joung Expires 1 September 2025 [Page 4] Internet-Draft N-SCORE February 2025 A packet can join the output link scheduler immediately after its ET. If no other packet is present in the scheduler, the packet is served right away. Otherwise, the packet joins the queue. Packets in the queue are served in ascending order of their ET and FT. Since the FT of N-SCORE is identical to that of C-SCORE, packets in N-SCORE follow the same service order as in C-SCORE. The only difference between the two systems is the existence of ET. However, in N-SCORE, due to the presence of the ET, the service period of packet p, while maintaining the same service order, is defined as (E(p), F(p)]. Here, E(p) and F(p) are ET and FT of packet p, respectively. Consequently, N-SCORE forwards packets in a non-work-preserving manner, maintaining a constant interval between E(p) and F(p) in all nodes. The service periods of packets within the same flow do not overlap at each node. Assuming zero link propagation delay, the packet service period at the entrance and core nodes with the N-SCORE scheduler is illustrated as follows: A1(1) A1(2)A1(3)A1(4) | | | | V V V V <----1----> <----2----><----3----><----4----> node 1 E1(1) F1(1) E1(2) F1(2)=E1(3) F1(3)=E1(4) F1(4) | | | | A2(1) A2(2) A2(3) A2(4) | | | | V V V V ...........<----1---->.....<----2----><----3----><----4----> node 2 E2(1) F2(1) E2(2) F2(3)=E2(3) F2(3)=E2(4) F2(4) Figure 2: N-SCORE packet scheduler service period 5. E2E latency and jitter bound The end-to-end (E2E) latency of N-SCORE is upper-bounded by: (B-L)/r+∑[h=0,H]{L/r + Lhmax/Rh} (4) which is the same as that of C-SCORE, which operates based on FT. Here, B, L, and r represent the maximum burst size, maximum packet length, and service rate of the observed flow, respectively. The link propagation delay is omitted. Unlike C-SCORE, which has no lower bound for E2E latency, the E2E latency of N-SCORE, which operates based on both ET and FT, is lower- bounded by: Ryoo & Joung Expires 1 September 2025 [Page 5] Internet-Draft N-SCORE February 2025 ∑[h=0, H-1]{L/r+(Lhmax)/Rh} +Lmin/RH (5) where L, Lmin, and r denote the maximum packet length, minimum packet length, and service rate of the observed flow, respectively. The link propagation delay is omitted. Therefore, unlike C-SCORE, which exhibits high jitter ranging from 0 to the E2E maximum delay, the E2E jitter of N-SCORE is bounded by: B/r+(LHmax)/RH - Lmin/RH (6) 6. Operational Procedure The N-SCORE scheduler in all nodes has a deterministic service period of ( E(p), F(p)] for packet p. Packets are queued in a priority queue in ascending order of ET and FT and can be dequeued after ET in a non-work-conserving manner. It operates at a constant interval that depends on the packet size and the service rate. N-SCORE manages per-flow state to calculate ET and FT at the entrance node. However, core nodes do not maintain state to accommodate large-scale networks. As a result, N-SCORE calculates and applies ET and FT differently at the entrance node and subsequent core nodes. Whenever a packet arrives, the entrance node calculates its ET and FT based on the managed per-flow state, updates the state using the calculated FT, and appends ET and FT as metadata to the packet header. Subsequent core nodes retrieve ET and FT from the metadata without maintaining state separately. At the same time, they calculate new ET and FT for the next node and update the metadata accordingly. 6.1. Operational Procedure in Entrance Node The entrance node manages the per-flow state, including the FT of the previous packet, F(p−1), and the service rate assigned to the flow, r(p). When a packet arrives at the entrance node, its ET, E(p), is determined as max{F(p−1), A(p)}. The entrance node compares each packet's arrival time, A(p), with the managed F(p−1) and sets the later time as E(p). The FT of the arriving packet, F(p), is calculated as E(p)+L(p)/r(p), and the FT of the previous packet is updated with the newly obtained F(p). Packets are stored in a priority queue in ascending order of E(p) and F(p) and can be dequeued after E(p) in a non-work-conserving manner. When the packet arrival interval is greater than the service rate, as seen with the first and second packets in Figure 2, the arrival times of these packets at node 1, A1(1) and A1(2), are later than the FT of Ryoo & Joung Expires 1 September 2025 [Page 6] Internet-Draft N-SCORE February 2025 the previous packet managed by the entrance node, F1(0) and F1 (1), respectively. Therefore, the ET of the first and second packets at node 1, E1(1) and E1(2), are set as A1(1) and A1(2), respectively. In this case, the service period is (A(p), A(p)+L(p)/r(p)], which matches the service period of C-SCORE. However, when the packet arrival interval is smaller than the service rate, as seen with the third and fourth packets in Figure 2, the arrival times of these packets at node 1, A1(3) and A1(4), are earlier than the FT of the previous packet managed by the entrance node, F1(2) and F1(3), respectively. Consequently, the ET of the third and fourth packets at node 1, E1(3) and E1(4), are set as F1(2) and F1(3), respectively. In this case, unlike C-SCORE’s service period of (A(p), F(p−1) + L(p)/r(p)], the N-SCORE service period is (F(p−1), F(p−1) + L(p)/r(p)]. N-SCORE regulates packet transmission based on the service rate, ensuring a deterministic and non- overlapping service period for all packets. A packet is dequeued after E(p), and before leaving, the entrance node marks metadata in the packet header, including L(p)/r(p), as well as the ET and FT for the next node. The subsequent core nodes then use this metadata to determine their ET and FT. 6.2. Operational Procedure in Core Node When the ET and FT of a packet are determined at the entrance node, the ET and FT of all subsequent nodes are determined based on the previous node's ET and FT as follows: Eligible Time for the next node: Eh+1(p) = Eh(p) + dh(p) (7) Finish Time for the next node: Fh+1(p) = Fh(p) + dh(p) (8) Here, dh(p) represents the maximum delay within node h, which is calculated as: dh(p) = L(p)/r(p) + Lhmax/Rh (9) The term Lhmax/Rh accounts for delay factors at node h, where Lhmax is the max packet length at node h across all flows transmitted through the observed output port, and Rh is the link capacity of node h. Ryoo & Joung Expires 1 September 2025 [Page 7] Internet-Draft N-SCORE February 2025 The entrance node delivers the metadata, including L(p)/r(p), ET, and FT, through the packet header. Subsequent core nodes obtain their ET and FT from the metadata without per-flow state management. Based on its delay factors and L(p)/r(p) value in the metadata, each core node computes dh(p), determines the ET and FT for the next node, and updates the metadata accordingly. Packets are stored in a priority queue in ascending order of E(p) and F(p), as derived from the metadata, and can be dequeued after E(p) in a non-work conserving manner. 7. Capability Analysis Based on the draft of the taxonomy, latency-bound solutions are classified according to functional characteristics such as * periodicity (periodic, non-periodic) * network synchronization (phase and frequency synchronous, asynchronous) * traffic granularity (flow level, flow aggregate level, class level) * work conserving (work conserving, non-work conserving) * target transmission time (in-time, on-time) * service order (rate-based, time-based, arrival-based, priority- based) The solutions proposed in DetNet and TSN can be broadly classified into seven types according to their functional characteristics: 1. Non-periodic/asynchronous/flow level/work conserving/in-time/ rate-based solution (C-SCORE) 2. Non-periodic/asynchronous/flow level/non-work conserving/in-time/ rate-based solution (ATS) 3. Non-periodic/asynchronous/class level/work conserving/in-time/ time-based solution (In-time EDF) 4. Non-periodic/asynchronous/class level/non-work conserving/on- time/time-based solution (On-time EDF) 5. Non-periodic/asynchrounous/flow aggregate level/non-work conserving/on-time/time-based solution (PIFO based on-time) Ryoo & Joung Expires 1 September 2025 [Page 8] Internet-Draft N-SCORE February 2025 6. Periodic/phase synchronous/class level/non-work conserving/on- time/time-based solution (TAS, CQF) 7. Periodic/frequency synchronous/class level/non-work conserving/ on-time/time-based solution (TQF, CSQF, TCQF, ECQF) The current solutions that provide on-time characteristics are all solutions with class-level or flow aggregate level traffic granularity characteristics and time-based service order characteristics. This draft suggests a new type of solution that has not been proposed before: 8. Non-periodic/asynchronous/flow level/non-work conserving/on-time/ rate-based solution (N-SCORE) The proposed solution is an on-time solution with rate-based service order characteristic that can handle a large number of dynamic flows with simple admission control. Additionally, it has flow-level traffic granularity characteristics that can minimize the effects of other flows' bursts. 8. IANA Considerations This document makes no request of IANA. Note to RFC Editor: this section may be removed on publication as an RFC. 9. Security Considerations TBD 10. References 10.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 10.2. Informative References Ryoo & Joung Expires 1 September 2025 [Page 9] Internet-Draft N-SCORE February 2025 Authors' Addresses Yeoncheol Ryoo ETRI Email: dbduscjf@etri.re.kr Jinoo Joung Sangmyung University Email: jjoung@smu.ac.kr Ryoo & Joung Expires 1 September 2025 [Page 10]