idnits 2.17.1 draft-finn-detnet-bounded-latency-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 535 has weird spacing: '...N queue non...' -- The document date (October 22, 2018) is 2012 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '2' on line 243 -- Looks like a reference, but probably isn't: '4' on line 243 == Outdated reference: A later version (-13) exists of draft-ietf-detnet-architecture-08 == Outdated reference: A later version (-02) exists of draft-ietf-detnet-dp-sol-ip-00 == Outdated reference: A later version (-02) exists of draft-ietf-detnet-dp-sol-mpls-00 == Outdated reference: A later version (-20) exists of draft-ietf-detnet-use-cases-19 ** Downref: Normative reference to an Informational draft: draft-ietf-detnet-use-cases (ref. 'I-D.ietf-detnet-use-cases') ** Downref: Normative reference to an Informational RFC: RFC 7806 Summary: 4 errors (**), 0 flaws (~~), 6 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 DetNet N. Finn 3 Internet-Draft Huawei Technologies Co. Ltd 4 Intended status: Standards Track J-Y. Le Boudec 5 Expires: April 25, 2019 E. Mohammadpour 6 EPFL 7 J. Zhang 8 Huawei Technologies Co. Ltd 9 B. Varga 10 J. Farkas 11 Ericsson 12 October 22, 2018 14 DetNet Bounded Latency 15 draft-finn-detnet-bounded-latency-02 17 Abstract 19 This document presents a parameterized timing model for Deterministic 20 Networking (DetNet), so that existing and future standards can 21 achieve the DetNet quality of service features of bounded latency and 22 zero congestion loss. It defines requirements for resource 23 reservation protocols or servers. It calls out queuing mechanisms, 24 defined in other documents, that can provide the DetNet quality of 25 service. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on April 25, 2019. 44 Copyright Notice 46 Copyright (c) 2018 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (https://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 62 2. Conventions Used in This Document . . . . . . . . . . . . . . 4 63 3. Terminology and Definitions . . . . . . . . . . . . . . . . . 4 64 4. DetNet bounded latency model . . . . . . . . . . . . . . . . 4 65 4.1. Flow creation . . . . . . . . . . . . . . . . . . . . . . 4 66 4.2. Relay system model . . . . . . . . . . . . . . . . . . . 5 67 5. Computing End-to-end Latency Bounds . . . . . . . . . . . . . 7 68 5.1. Non-queuing delay bound . . . . . . . . . . . . . . . . . 7 69 5.2. Queuing delay bound . . . . . . . . . . . . . . . . . . . 8 70 5.2.1. Per-flow queuing mechanisms . . . . . . . . . . . . . 8 71 5.2.2. Per-class queuing mechanisms . . . . . . . . . . . . 8 72 6. Achieving zero congestion loss . . . . . . . . . . . . . . . 10 73 6.1. A General Formula . . . . . . . . . . . . . . . . . . . . 10 74 7. Queuing model . . . . . . . . . . . . . . . . . . . . . . . . 11 75 7.1. Queuing data model . . . . . . . . . . . . . . . . . . . 11 76 7.2. Preemption . . . . . . . . . . . . . . . . . . . . . . . 13 77 7.3. Time-scheduled queuing . . . . . . . . . . . . . . . . . 13 78 7.4. Time-Sensitive Networking with Asynchronous Traffic 79 Shaping . . . . . . . . . . . . . . . . . . . . . . . . . 13 80 7.5. IntServ . . . . . . . . . . . . . . . . . . . . . . . . . 15 81 8. Time-based DetNet QoS . . . . . . . . . . . . . . . . . . . . 19 82 8.1. Cyclic Queuing and Forwarding . . . . . . . . . . . . . . 19 83 8.2. Time Scheduled Queuing . . . . . . . . . . . . . . . . . 19 84 9. Parameters for the bounded latency model . . . . . . . . . . 20 85 9.1. Sender parameters . . . . . . . . . . . . . . . . . . . . 20 86 9.2. Relay system parameters . . . . . . . . . . . . . . . . . 21 87 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 21 88 10.1. Normative References . . . . . . . . . . . . . . . . . . 21 89 10.2. Informative References . . . . . . . . . . . . . . . . . 22 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 92 1. Introduction 94 The ability for IETF Deterministic Networking (DetNet) or IEEE 802.1 95 Time-Sensitive Networking (TSN, [IEEE8021TSN]) to provide the DetNet 96 services of bounded latency and zero congestion loss depends upon A) 97 configuring and allocating network resources for the exclusive use of 98 DetNet/TSN flows; B) identifying, in the data plane, the resources to 99 be utilized by any given packet, and C) the detailed behavior of 100 those resources, especially transmission queue selection, so that 101 latency bounds can be reliably assured. Thus, DetNet is an example 102 of an INTSERV Guaranteed Quality of Service [RFC2212] 104 As explained in [I-D.ietf-detnet-architecture], DetNet flows are 105 characterized by 1) a maximum bandwidth, guaranteed either by the 106 transmitter or by strict input metering; and 2) a requirement for a 107 guaranteed worst-case end-to-end latency. That latency guarantee, in 108 turn, provides the opportunity for the network to supply enough 109 buffer space to guarantee zero congestion loss. To be of use to the 110 applications identified in [I-D.ietf-detnet-use-cases], it must be 111 possible to calculate, before the transmission of a DetNet flow 112 commences, both the worst-case end-to-end network latency, and the 113 amount of buffer space required at each hop to ensure against 114 congestion loss. 116 This document references specific queuing mechanisms, defined in 117 other documents, that can be used to control packet transmission at 118 each output port and achieve the DetNet qualities of service. This 119 document presents a timing model for sources, destinations, and the 120 network nodes that relay packets that is applicable to all of those 121 referenced queuing mechanisms. The parameters specified in this 122 model: 124 o Characterize a DetNet flow in a way that provides externally 125 measurable verification that the sender is conforming to its 126 promised maximum, can be implemented reasonably easily by a 127 sending device, and does not require excessive over-allocation of 128 resources by the network. 130 o Enable reasonably accurate computation of worst-case end-to-end 131 latency, in a way that requires as little detailed knowledge as 132 possible of the behavior of the Quality of Service (QoS) 133 algorithms implemented in each device, including queuing, shaping, 134 metering, policing, and transmission selection techniques. 136 Using the model presented in this document, it should be possible for 137 an implementor, user, or standards development organization to select 138 a particular set of queuing mechanisms for each device in a DetNet 139 network, and to select a resource reservation algorithm for that 140 network, so that those elements can work together to provide the 141 DetNet service. 143 This document does not specify any resource reservation protocol or 144 server. It does not describe all of the requirements for that 145 protocol or server. It does describe requirements for such resource 146 reservation methods, and for queuing mechanisms that, if met, will 147 enable them to work together. 149 NOTE: This draft is not yet complete, but it is sufficiently so to 150 share with the Working Group and to obtain opinions and direction. 151 The present intent of is for this draft to become a normative RFC, 152 defining how one SHALL/SHOULD provide the DetNet quality of service. 153 There are still a few authors' notes to each other present in this 154 draft. 156 2. Conventions Used in This Document 158 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 159 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 160 document are to be interpreted as described in [RFC2119]. 162 The lowercase forms with an initial capital "Must", "Must Not", 163 "Shall", "Shall Not", "Should", "Should Not", "May", and "Optional" 164 in this document are to be interpreted in the sense defined in 165 [RFC2119], but are used where the normative behavior is defined in 166 documents published by SDOs other than the IETF. 168 3. Terminology and Definitions 170 This document uses the terms defined in 171 [I-D.ietf-detnet-architecture]. 173 4. DetNet bounded latency model 175 4.1. Flow creation 177 The bounded latency model assumes the use of the following paradigm 178 for provisioning a particular DetNet flow: 180 1. Perform any configuration required by the relay systems in the 181 network for the classes of service to be offered, including one 182 or more classes of DetNet service. This configuration is not 183 tied to any particular flow. 185 2. Characterize the DetNet flow in terms of limitations on the 186 sender [Section 9.1] and flow requirements [Section 9.2]. 188 3. Establish the path that the DetNet flow will take through the 189 network from the source to the destination(s). This can be a 190 point-to-point or a point-to-multipoint path. 192 4. Select one of the DetNet classes of service for the DetNet flow. 194 5. Compute the worst-case end-to-end latency for the DetNet flow. 195 In the process, determine whether sufficient resources are 196 available for that flow to guarantee the required latency and to 197 provide zero congestion loss. 199 6. Assuming that the resources are available, commit those resources 200 to the flow. This may or may not require adjusting the 201 parameters that control the queuing mechanisms at each hop along 202 the flow's path. 204 This paradigm can be static and/or dynamic, and can be implemented 205 using peer-to-peer protocols or using a central server model. In 206 some situations, backtracking and recursing through this list may be 207 necessary. 209 Issues such as un-provisioning a DetNet flow in favor of another when 210 resources are scarce are not considered. How the path to be taken by 211 a DetNet flow is chosen is not considered in this document. 213 4.2. Relay system model 215 In Figure 1 we see a breakdown of the per-hop latency experienced by 216 a packet passing through a relay system, in terms that are suitable 217 for computing both hop-by-hop latency and per-hop buffer 218 requirements. 220 DetNet relay node A DetNet relay node B 221 +-------------------------+ +------------------------+ 222 | Queuing | | Queuing | 223 | Regulator subsystem | | Regulator subsystem | 224 | +-+-+-+-+ +-+-+-+-+ | | +-+-+-+-+ +-+-+-+-+ | 225 -->+ | | | | | | | | | + +------>+ | | | | | | | | | + +---> 226 | +-+-+-+-+ +-+-+-+-+ | | +-+-+-+-+ +-+-+-+-+ | 227 | | | | 228 +-------------------------+ +------------------------+ 229 |<->|<------>|<------->|<->|<---->|<->|<------>|<------>|<->|<-- 230 2,3 4 5 6 1 2,3 4 5 6 1 2,3 231 1: Output delay 4: Processing delay 232 2: Link delay 5: Regulation delay 233 3: Preemption delay 6: Queuing delay. 235 Figure 1: Timing model for DetNet or TSN 237 In Figure 1, we see two DetNet relay nodes (typically, bridges or 238 routers), with a wired link between them. In this model, the only 239 queues we deal with explicitly are attached to the output port; other 240 queues are modeled as variations in the other delay times. (E.g., an 241 input queue could be modeled as either a variation in the link delay 243 [2] or the processing delay [4].) There are six delays that a packet 244 can experience from hop to hop. 246 1. Output delay 247 The time taken from the selection of a packet for output from a 248 queue to the transmission of the first bit of the packet on the 249 physical link. If the queue is directly attached to the physical 250 port, output delay can be a constant. But, in many 251 implementations, the queuing mechanism in a forwarding ASIC is 252 separated from a multi-port MAC/PHY, in a second ASIC, by a 253 multiplexed connection. This causes variations in the output 254 delay that are hard for the forwarding node to predict or control. 256 2. Link delay 257 The time taken from the transmission of the first bit of the 258 packet to the reception of the last bit, assuming that the 259 transmission is not suspended by a preemption event. This delay 260 has two components, the first-bit-out to first-bit-in delay and 261 the first-bit-in to last-bit-in delay that varies with packet 262 size. The former is typically measured by the Precision Time 263 Protocol and is constant (see [I-D.ietf-detnet-architecture]). 264 However, a virtual "link" could exhibit a variable link delay. 266 3. Preemption delay 267 If the packet is interrupted (e.g. [IEEE8023br] and [IEEE8021Qbu] 268 preemption) in order to transmit another packet or packets, an 269 arbitrary delay can result. 271 4. Processing delay 272 This delay covers the time from the reception of the last bit of 273 the packet to the time the packet is enqueued in the regulator 274 (Queuing subsystem, if there is no regulation). This delay can be 275 variable, and depends on the details of the operation of the 276 forwarding node. 278 5. Regulator delay 279 This is the time spent from the insertion of the last bit of a 280 packet into a regulation queue until the time the packet is 281 declared eligible according to its regulation constraints. We 282 assume that this time can be calculated based on the details of 283 regulation policy. If there is no regulation, this time is zero. 285 6. Queuing subsystem delay 286 This is the time spent for a packet from being declared eligible 287 until being selected for output on the next link. We assume that 288 this time is calculable based on the details of the queuing 289 mechanism. If there is no regulation, this time is from the 290 insertion of the packet into a queue until it is selected for 291 output on the next link. 293 Not shown in Figure 1 are the other output queues that we presume are 294 also attached to that same output port as the queue shown, and 295 against which this shown queue competes for transmission 296 opportunities. 298 The initial and final measurement point in this analysis (that is, 299 the definition of a "hop") is the point at which a packet is selected 300 for output. In general, any queue selection method that is suitable 301 for use in a DetNet network includes a detailed specification as to 302 exactly when packets are selected for transmission. Any variations 303 in any of the delay times 1-4 result in a need for additional buffers 304 in the queue. If all delays 1-4 are constant, then any variation in 305 the time at which packets are inserted into a queue depends entirely 306 on the timing of packet selection in the previous node. If the 307 delays 1-4 are not constant, then additional buffers are required in 308 the queue to absorb these variations. Thus: 310 o Variations in output delay (1) require buffers to absorb that 311 variation in the next hop, so the output delay variations of the 312 previous hop (on each input port) must be known in order to 313 calculate the buffer space required on this hop. 315 o Variations in processing delay (4) require additional output 316 buffers in the queues of that same Detnet relay node. Depending 317 on the details of the queueing subsystem delay (6) calculations, 318 these variations need not be visible outside the DetNet relay 319 node. 321 5. Computing End-to-end Latency Bounds 323 5.1. Non-queuing delay bound 325 End-to-end latency bounds can be computed using the delay model in 326 Section 4.2. Here it is important to be aware that for several 327 queuing mechanisms, the worst-case end-to-end delay is less than the 328 sum of the per-hop worst-case delays. An end-to-end latency bound 329 for one DetNet flow can be computed as 331 end_to_end_latency_bound = non_queuing_latency + queuing_latency 333 The two terms in the above formula are computed as follows. First, 334 at the h-th hop along the path of this DetNet flow, obtain an upper 335 bound per-hop_non_queuing_latency[h] on the sum of delays 1,2,3,4 of 336 Figure 1. These upper-bounds are expected to depend on the specific 337 technology of the node at the h-th hop but not on the T-SPEC of this 338 DetNet flow. Then set non_queuing_latency = the sum of per- 339 hop_non_queuing_latency[h] over all hops h. 341 5.2. Queuing delay bound 343 Second, compute queuing_latency as an upper bound to the sum of the 344 queuing delays along the path. The value of queuing_latency depends 345 on the T-SPEC of this flow and possibly of other flows in the 346 network, as well as the specifics of the queuing mechanisms deployed 347 along the path of this flow. 349 For several queuing mechanisms, queuing_latency is less than the sum 350 of upper bounds on the queuing delays (5,6) at every hop. This 351 occurs with (1) per-flow queuing, and (2) per-class queuing with 352 regulators, as explained in Section 5.2.1, Section 5.2.2, and 353 Section 7. 355 For other queuing mechanisms the only available value of 356 queuing_latency is the sum of the per-hop queuing delay bounds. In 357 such cases, the computation of per-hop queuing delay bounds must 358 account for the fact that the T-SPEC of a DetNet flow is no longer 359 satisfied at the ingress of a hop, since burstiness increases as one 360 flow traverses one DetNet node. 362 5.2.1. Per-flow queuing mechanisms 364 With such mechanisms, each flow uses a separate queue inside every 365 node. The service for each queue is abstracted with a guaranteed 366 rate and a delay. For every flow the per-node delay bound as well as 367 end-to-end delay bound can be computed from the traffic specification 368 of this flow at its source and from the values of rates and latencies 369 at all nodes along its path. Details of calculation for IntServ are 370 described in Section 7.5. 372 5.2.2. Per-class queuing mechanisms 374 With such mechanisms, the flows that have the same class share the 375 same queue. A practical example is the queuing mechanism in Time 376 Sensitive Networking. One key issue in this context is how to deal 377 with the burstiness cascade: individual flows that share a resource 378 dedicated to a class may see their burstiness increase, which may in 379 turn cause increased burstiness to other flows downstream of this 380 resource. Computing latency upper bounds for such cases is 381 difficult, and in some conditions impossible 382 [charny2000delay][bennett2002delay]. Also, when bounds are obtained, 383 they depend on the complete configuration, and must be recomputed 384 when one flow is added. 386 A solution to deal with this issue is to reshape the flows at every 387 hop. This can be done with per-flow regulators (e.g. leaky bucket 388 shapers), but this requires per-flow queuing and defeats the purpose 389 of per-class queuing. An alternative is the interleaved regulator, 390 which reshapes individual flows without per-flow queuing 391 ([Specht2016UBS], [IEEE8021Qcr]"). With an interleaved regulator, 392 the packet at the head of the queue is regulated based on its (flow) 393 regulation constraints; it is released at the earliest time at which 394 this is possible without violating the constraint. One key feature 395 of per-flow or interleaved regulator is that, it does not increase 396 worst-case latency bounds [le_boudec_theory_2018]. Specifically, 397 when an interleaved regulator is appended to a FIFO subsystem, it 398 does not increase the worst-case delay of the latter. 400 Figure 2 shows an example of a network with 5 nodes, per-class 401 queuing mechanism and interleaved regulators as in Figure 1. An end- 402 to-end delay bound for flow f, traversing nodes 1 to 5, is calculated 403 as follows: 405 end_to_end_latency_bound_of_flow_f = C12 + C23 + C34 + S4 407 In the above formula, Cij is a bound on the aggregate response time 408 of queuing subsystem in node i and interleaved regulator of node j, 409 and S4 is a bound on the response time of the queuing subsystem in 410 node 4 for flow f. In fact, using the delay definitions in 411 Section 4.2, Cij is a bound on sum of the delays 1,2,3,6 of node i 412 and 4,5 of node j. Similarly, S4 is a bound on sum of the delays 413 1,2,3,6 of node 4. A practical example of queuing model and delay 414 calculation is presented Section 7.4. 416 f 417 -----------------------------> 418 +---+ +---+ +---+ +---+ +---+ 419 | 1 |---| 2 |---| 3 |---| 4 |---| 5 | 420 +---+ +---+ +---+ +---+ +---+ 421 \__C12_/\__C23_/\__C34_/\_S4_/ 423 Figure 2: End-to-end latency computation example 425 REMARK: The end-to-end delay bound calculation provided here gives a 426 much better upper bound in comparison with end-to-end delay bound 427 computation by adding the delay bounds of each node in the path of a 428 flow [TSNwithATS]. 430 6. Achieving zero congestion loss 432 When the input rate to an output queue exceeds the output rate for a 433 sufficient length of time, the queue must overflow. This is 434 congestion loss, and this is what deterministic networking seeks to 435 avoid. 437 6.1. A General Formula 439 To avoid congestion losses, an upper bound on the backlog present in 440 the regulator and queuing subsystem of Figure 1 must be computed 441 during resource reservation. This bound depends on the set of flows 442 that use these queues, the details of the specific queuing mechanism 443 and an upper bound on the processing delay (4). The queue must 444 contain the packet in transmission plus all other packets that are 445 waiting to be selected for output. 447 A conservative backlog bound, that applies to all systems, can be 448 derived as follows. 450 The backlog bound is counted in data units (bytes, or words of 451 multiple bytes) that are relevant for buffer allocation. For every 452 class we need one buffer space for the packet in transmission, plus 453 space for the packets that are waiting to be selected for output. 454 Excluding transmission and preemption times, the packets are waiting 455 in the queue since reception of the last bit, for a duration equal to 456 the processing delay (4) plus the queuing delays (5,6). 458 Let 460 o nb_classes be the number of classes of traffic that may use this 461 output port 463 o total_in_rate be the sum of the line rates of all input ports that 464 send traffic of any class to this output port. The value of 465 total_in_rate is in data units (e.g. bytes) per second. 467 o nb_input_ports be the number input ports that send traffic of any 468 class to this output port 470 o max_packet_length be the maximum packet size for packets of any 471 class that may be sent to this output port. This is counted in 472 data units. 474 o max_delay45 be an upper bound, in seconds, on the sum of the 475 processing delay (4) and the queuing delays (5,6) for a packet of 476 any class at this ouput port. 478 Then a bound on the backlog of traffic of all classes in the queue at 479 this output port is 481 backlog_bound = ( nb_classes + nb_input_ports ) * 482 max_packet_length + total_in_rate* max_delay45 484 7. Queuing model 486 7.1. Queuing data model 488 Sophisticated queuing mechanisms are available in Layer 3 (L3, see, 489 e.g., [RFC7806] for an overview). In general, we assume that "Layer 490 3" queues, shapers, meters, etc., are precisely the "regulators" 491 shown in Figure 1. The "queuing subsystems" in this figure are not 492 the province solely of bridges; they are an essential part of any 493 DetNet relay node. As illustrated by numerous implementation 494 examples, some of the "Layer 3" mechanisms described in documents 495 such as [RFC7806] are often integrated, in an implementation, with 496 the "Layer 2" mechanisms also implemented in the same system. An 497 integrated model is needed in order to successfully predict the 498 interactions among the different queuing mechanisms needed in a 499 network carrying both DetNet flows and non-DetNet flows. 501 Figure 3 shows the general model for the flow of packets through the 502 queues of a DetNet relay node. Packets are assigned to a class of 503 service. The classes of service are mapped to some number of 504 regulator queues. Only DetNet/TSN packets pass through regulators. 505 Queues compete for the selection of packets to be passed to queues in 506 the queuing subsystem. Packets again are selected for output from 507 the queuing subsystem. 509 | 510 +--------------------------------V----------------------------------+ 511 | Class of Service Assignment | 512 +--+------+----------+---------+-----------+-----+-------+-------+--+ 513 | | | | | | | | 514 +--V-+ +--V-+ +--V--+ +--V--+ +--V--+ | | | 515 |Flow| |Flow| |Flow | |Flow | |Flow | | | | 516 | 0 | | 1 | ... | i | | i+1 | ... | n | | | | 517 | reg| | reg| | reg | | reg | | reg | | | | 518 +--+-+ +--+-+ +--+--+ +--+--+ +--+--+ | | | 519 | | | | | | | | 520 +--V------V----------V--+ +--V-----------V--+ | | | 521 | Trans. selection | | Trans. select. | | | | 522 +----------+------------+ +-----+-----------+ | | | 523 | | | | | 524 +--V--+ +--V--+ +--V--+ +--V--+ +--V--+ 525 | out | | out | | out | | out | | out | 526 |queue| |queue| |queue| |queue| |queue| 527 | 1 | | 2 | | 3 | | 4 | | 5 | 528 +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ 529 | | | | | 530 +----------V----------------------V--------------V-------V-------V--+ 531 | Transmission selection | 532 +----------+----------------------+--------------+-------+-------+--+ 533 | | | | | 534 V V V V V 535 DetNet/TSN queue DetNet/TSN queue non-DetNet/TSN queues 537 Figure 3: IEEE 802.1Q Queuing Model: Data flow 539 Some relevant mechanisms are hidden in this figure, and are performed 540 in the queue boxes: 542 o Discarding packets because a queue is full. 544 o Discarding packets marked "yellow" by a metering function, in 545 preference to discarding "green" packets. 547 Ideally, neither of these actions are performed on DetNet packets. 548 Full queues for DetNet packets should occur only when a flow is 549 misbehaving, and the DetNet QoS does not include "yellow" service for 550 packets in excess of committed rate. 552 The Class of Service Assignment function can be quite complex, even 553 in a bridge [IEEE8021Q], since the introduction of [IEEE802.1Qci]. 554 In addition to the Layer 2 priority expressed in the 802.1Q VLAN tag, 555 a DetNet relay node can utilize any of the following information to 556 assign a packet to a particular class of service (queue): 558 o Input port. 560 o Selector based on a rotating schedule that starts at regular, 561 time-synchronized intervals and has nanosecond precision. 563 o MAC addresses, VLAN ID, IP addresses, Layer 4 port numbers, DSCP. 564 ([I-D.ietf-detnet-dp-sol-ip], [I-D.ietf-detnet-dp-sol-mpls]) (Work 565 items are expected to add MPC and other indicators.) 567 o The Class of Service Assignment function can contain metering and 568 policing functions. 570 o MPLS and/or pseudowire ([RFC6658]) labels. 572 The "Transmission selection" function decides which queue is to 573 transfer its oldest packet to the output port when a transmission 574 opportunity arises. 576 7.2. Preemption 578 In IEEE Std 802.1Q, preemption is modeled as consisting of two MAC/ 579 PHY stacks, one for packets that can be interrupted, and one for 580 packets that can interrupt the interruptible packets. The Class of 581 Service (queue) determines which packets are which. Only one layer 582 of preemption is supported. DetNet flows pass through the 583 interrupting MAC. Only best-effort queues pass through the 584 interruptible MAC, and can thus be preempted. 586 7.3. Time-scheduled queuing 588 In [IEEE8021Qbv], the notion of time-scheduling queue gates were 589 introduced. On below every output queue (the lower row of queues in 590 Figure 3) is a gate that permits or denies the queue to present data 591 for transmission selection. The gates are controlled by a rotating 592 schedule that can be locked to a clock that is synchronized with 593 other relay nodes. The DetNet class of service can be supplied by 594 queuing mechanisms based on time, rather than the regulator model in 595 Figure 3. These queuing mechanisms are discussed in Section 8, 596 below. 598 7.4. Time-Sensitive Networking with Asynchronous Traffic Shaping 600 Consider a network with a set of nodes (switches and hosts) along 601 with a set of flows between hosts. Hosts are sources or destinations 602 of flows. There are four types of flows, namely, control-data 603 traffic (CDT), class A, class B, and best effort (BE) in decreasing 604 order of priority. Flows of classes A and B are together referred to 605 as AVB flows. It is assumed a subset of TSN functions as described 606 next. 608 It is also assumed that contention occurs only at the output port of 609 a TSN node. Each node output port performs per-class scheduling with 610 eight classes: one for CDT, one for class A traffic, one for class B 611 traffic, and five for BE traffic denoted as BE0-BE4 (according to TSN 612 standard). In addition, each node output port also performs per-flow 613 regulation for AVB flows using an interleaved regulator (IR), called 614 Asynchronous Traffic Shaper (ATS) in TSN. Thus, at each output port 615 of a node, there is one interleaved regulator per-input port and per- 616 class. The detailed picture of scheduling and regulation 617 architecture at a node output port is given by Figure 4. The packets 618 received at a node input port for a given class are enqueued in the 619 respective interleaved regulator at the output port. Then, the 620 packets from all the flows, including CDT and BE flows, are enqueued 621 in a class based FIFO system (CBFS) [TSNwithATS]. 623 +--+ +--+ +--+ +--+ 624 | | | | | | | | 625 |IR| |IR| |IR| |IR| 626 | | | | | | | | 627 +-++XXX++-+ +-++XXX++-+ 628 | | | | 629 | | | | 630 +---+ +-v-XXX-v-+ +-v-XXX-v-+ +-----+ +-----+ +-----+ +-----+ +-----+ 631 | | | | | | |Class| |Class| |Class| |Class| |Class| 632 |CDT| | Class A | | Class B | | BE4 | | BE3 | | BE2 | | BE1 | | BE0 | 633 | | | | | | | | | | | | | | | | 634 +-+-+ +----+----+ +----+----+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ 635 | | | | | | | | 636 | +-v-+ +-v-+ | | | | | 637 | |CBS| |CBS| | | | | | 638 | +-+-+ +-+-+ | | | | | 639 | | | | | | | | 640 +-v--------v-----------v---------v-------V-------v-------v-------v--+ 641 | Strict Priority selection | 642 +--------------------------------+----------------------------------+ 643 | 644 V 646 Figure 4: Architecture of a TSN node output port with interleaved 647 regulators (IRs) 649 The CBFS includes two CBS subsystems, one for each class A and B. 650 The CBS serves a packet from a class according to the available 651 credit for that class. The credit for each class A or B increases 652 based on the idle slope, and decreases based on the send slope, both 653 of which are parameters of the CBS. The CDT and BE0-BE4 flows in the 654 CBFS are served by separate FIFO subsystems. Then, packets from all 655 flows are served by a transmission selection subsystem that serves 656 packets from each class based on its priority. All subsystems are 657 non-preemptive. Guarantees for AVB traffic can be provided only if 658 CDT traffic is bounded; it is assumed that the CDT traffic has an 659 affine arrival curve r t + b in each node, i.e. the amount of bits 660 entering a node within a time interval t is bounded by r t + b. 662 [[ EM: THE FOLLOWING PARAGRAPH SHOULD BE ALIGNED WITH Section 9.2. ]] 664 Additionally, it is assumed that flows are regulated at their source, 665 according to either leaky bucket (LB) or length rate quotient (LRQ). 666 The LB-type regulation forces flow f to conform to an arrival curve 667 r_f t+b_f . The LRQ-type regulation with rate r_f ensures that the 668 time separation between two consecutive packets of sizes l_n and 669 l_n+1 is at least l_n/r_f. Note that if flow f is LRQ-regulated, it 670 satisfies an arrival curve constraint r_f t + L_f where L_f is its 671 maximum packet size (but the converse may not hold). For an LRQ 672 regulated flow, b_f = L_f. At the source hosts, the traffic 673 satisfies its regulation constraint, i.e. the delay due to 674 interleaved regulator at hosts is ignored. 676 At each switch implementing an interleaved regulator, packets of 677 multiple flows are processed in one FIFO queue; the packet at the 678 head of the queue is regulated based on its regulation constraints; 679 it is released at the earliest time at which this is possible without 680 violating the constraint. The regulation type and parameters for a 681 flow are the same at its source and at all switches along its path. 683 Details of end-to-end delay bound calculation in such a system is 684 described in [TSNwithATS]. 686 7.5. IntServ 688 In this section, a worst-case queuing latency calculating method is 689 provided. In deterministic network, the traffic of a flow is 690 constrained by arrival curve. Queuing mechanisms in a DetNet node 691 can be characterized and constrained by service curve. By using 692 arrival curve and service curve with Network Calculus theory 693 [NetCalBook], a tight worst-case queuing latency can be calculated. 695 Considering a DetNet flow at output port, R(s) is the cumulative 696 arrival data until time s. For any time period t, the incremental 697 arrival data is constrained by an arrival curve a(t) 699 R(s+t)-R(s) <= a(t), \any s>=0, t>=0 701 The scheduling that a relay node performs to a DetNet flow can be 702 abstracted as service curve. It describes the minimal service the 703 network can offer. The service curve b(t) of a node is defined as 704 below, if the accumulative input data R and output data R_out of the 705 node satisfies 707 R_out(t) >= inf(R(s) + b(t-s) ), \any s <=t 709 where the operator "inf" calculates the greatest lower bound in 710 period t. 712 By calculating the maximum vertical deviation between arrival curve 713 a(t) and service curve b(t), one can obtain the backlog bound in data 714 unit 716 Backlog_bound = sup_t(a(t) - b(t) ) 718 where operator "sup_t" calculates the minimum upper bound with 719 respect to t. The buffer space at a node should be no less than the 720 backlog bound to achieve zero congestion loss. 722 NOTE: Section 6.1 gives a general formula for computing the buffer 723 requirements. This is an alternative calculation based on the 724 arrival curve and service curve. 726 By calculating the maximum horizontal deviation between arrival curve 727 a(t) and service curve b(t), one can obtain the delay bound as below 729 Delay_bound = sup_s( inf_t( t>=0 | a(s) <= b(s+t) ) 731 where the operator " inf_t" calculates the maximum lower bound with 732 respect to t, the operator "sup_s" calculates the minimum upper bound 733 with respect to s. Figure 5 shows an example of arival curve, 734 service curve, backlog bound h, and delay bound v. 736 + bit . * 737 | . * 738 | . * 739 | * 740 | * . 741 | * . 742 | * | . .. Service curve 743 *-----h-|---. ** Arrival curve 744 | v . h Delay_bound 745 | | . v Backlog_bound 746 | |. 747 +-------.--------------------+ time 749 Figure 5: Computation of backlog bound and delay bound. Note that 750 arrival and service curves are not necessary to be linear. 752 Note that in the formula of Delay_bound, the service curve b(t) can 753 describe either per-hop scheduling that a DetNet node offers to a 754 flow, or concatenation of multiple nodes that represents end-to-end 755 scheduling that DetNet path offers to a flow. In the latter case, 756 the obtained delay bound is end-to-end worst case delay. To 757 calculate this, we should at first derive the concatenated service 758 curve. 760 Consider a flow traverse two DetNet nodes, which offer service curve 761 b1(t) and b2(t) sequentially. Then concatenation of the two nodes 762 offers a service curve b_concatenated as below 764 b_concatenated(t) =inf_s (b1(s) + b2(t-s) ) , \any 0 <=s <=t 766 The concatenation of service curve can be directly generalized to 767 include more than two nodes. 769 a_out(t) = sup_u( a(t+u) - b(u) ), \any u>=0 771 In DetNet, the arrival curve and service curve can be characterized 772 by a group of parameters, which will be defined in Section 8. 774 Integrated service (IntServ) is an architecture that specifies the 775 elements to guarantee quality of service (QoS) on networks. To 776 satisfied guaranteed service, a flow must conform to a traffic 777 specification (T-spec), and reservation is made along a path, only if 778 routers are able to guarantee the required bandwidth and buffer. 780 Consider the traffic model which conforms to token bucket regulator 781 (r, b), with 783 o Token bucket depth (b). 785 o Token bucket rate (r). 787 The traffic specification can be described as an arrival curve a(t) 789 alpha(t) = b + rt 791 This token bucket regulator requires that, during any time window of 792 width t, the number of bit for the flow is limited by alpha(t) = b + 793 rt. 795 If resource reservation on a path is applied, IntServ model on a 796 router can be described as a rate-latency service curve beta(t). 798 beta(t) = max(0, R(t-T)) 800 It describes that bits might have to wait up to T before being served 801 with a rate greater or equal to R. 803 It should be noted that, the guaranteed service rate R is a share of 804 link's bandwidth. The choice of R is related to the specification of 805 flows which will transmit on this node. For example, in strict 806 priority policy, considering a flow with priority j, its share of 807 bandwidth may be R=c-sum(r_i), i. 957 [RFC2212] Shenker, S., Partridge, C., and R. Guerin, "Specification 958 of Guaranteed Quality of Service", RFC 2212, 959 DOI 10.17487/RFC2212, September 1997, 960 . 962 [RFC6658] Bryant, S., Ed., Martini, L., Swallow, G., and A. Malis, 963 "Packet Pseudowire Encapsulation over an MPLS PSN", 964 RFC 6658, DOI 10.17487/RFC6658, July 2012, 965 . 967 [RFC7806] Baker, F. and R. Pan, "On Queuing, Marking, and Dropping", 968 RFC 7806, DOI 10.17487/RFC7806, April 2016, 969 . 971 10.2. Informative References 973 [bennett2002delay] 974 J.C.R. Bennett, K. Benson, A. Charny, W.F. Courtney, and 975 J.-Y. Le Boudec, "Delay Jitter Bounds and Packet Scale 976 Rate Guarantee for Expedited Forwarding", 977 . 979 [charny2000delay] 980 A. Charny and J.-Y. Le Boudec, "Delay Bounds in a Network 981 with Aggregate Scheduling", . 984 [IEEE802.1Qch] 985 IEEE, "IEEE Std 802.1Qch-2017 IEEE Standard for Local and 986 metropolitan area networks - Bridges and Bridged Networks 987 Amendment 29: Cyclic Queuing and Forwarding (amendment to 988 802.1Q-2014)", 2017, 989 . 991 [IEEE802.1Qci] 992 IEEE, "IEEE Std 802.1Qci-2017 IEEE Standard for Local and 993 metropolitan area networks - Bridges and Bridged Networks 994 - Amendment 30: Per-Stream Filtering and Policing", 2017, 995 . 997 [IEEE8021Q] 998 IEEE 802.1, "IEEE Std 802.1Q-2014: IEEE Standard for Local 999 and metropolitan area networks - Bridges and Bridged 1000 Networks", 2014, . 1003 [IEEE8021Qbu] 1004 IEEE, "IEEE Std 802.1Qbu-2016 IEEE Standard for Local and 1005 metropolitan area networks - Bridges and Bridged Networks 1006 - Amendment 26: Frame Preemption", 2016, 1007 . 1010 [IEEE8021Qbv] 1011 IEEE 802.1, "IEEE Std 802.1Qbv-2015: IEEE Standard for 1012 Local and metropolitan area networks - Bridges and Bridged 1013 Networks - Amendment 25: Enhancements for Scheduled 1014 Traffic", 2015, . 1017 [IEEE8021Qcr] 1018 IEEE 802.1, "IEEE P802.1Qcr: IEEE Draft Standard for Local 1019 and metropolitan area networks - Bridges and Bridged 1020 Networks - Amendment: Asynchronous Traffic Shaping", 2017, 1021 . 1023 [IEEE8021TSN] 1024 IEEE 802.1, "IEEE 802.1 Time-Sensitive Networking (TSN) 1025 Task Group", . 1027 [IEEE8023br] 1028 IEEE 802.3, "IEEE Std 802.3br-2016: IEEE Standard for 1029 Local and metropolitan area networks - Ethernet - 1030 Amendment 5: Specification and Management Parameters for 1031 Interspersing Express Traffic", 2016, 1032 . 1035 [le_boudec_theory_2018] 1036 J.-Y. Le Boudec, "A Theory of Traffic Regulators for 1037 Deterministic Networks with Application to Interleaved 1038 Regulators", . 1040 [NetCalBook] 1041 Le Boudec, Jean-Yves, and Patrick Thiran, "Network 1042 calculus: a theory of deterministic queuing systems for 1043 the internet", 2001, . 1045 [Specht2016UBS] 1046 J. Specht and S. Samii, "Urgency-Based Scheduler for Time- 1047 Sensitive Switched Ethernet Networks", 1048 . 1050 [TSNwithATS] 1051 E. Mohammadpour, E. Stai, M. Mohiuddin, and J.-Y. Le 1052 Boudec, "End-to-end Latency and Backlog Bounds in Time- 1053 Sensitive Networking with Credit Based Shapers and 1054 Asynchronous Traffic Shaping", 1055 . 1057 Authors' Addresses 1058 Norman Finn 1059 Huawei Technologies Co. Ltd 1060 3101 Rio Way 1061 Spring Valley, California 91977 1062 US 1064 Phone: +1 925 980 6430 1065 Email: norman.finn@mail01.huawei.com 1067 Jean-Yves Le Boudec 1068 EPFL 1069 IC Station 14 1070 Lausanne EPFL 1015 1071 Switzerland 1073 Email: jean-yves.leboudec@epfl.ch 1075 Ehsan Mohammadpour 1076 EPFL 1077 IC Station 14 1078 Lausanne EPFL 1015 1079 Switzerland 1081 Email: ehsan.mohammadpour@epfl.ch 1083 Jiayi Zhang 1084 Huawei Technologies Co. Ltd 1085 Q22, No.156 Beiqing Road 1086 Beijing 100095 1087 China 1089 Email: zhangjiayi11@huawei.com 1091 Balazs Varga 1092 Ericsson 1093 Konyves Kalman krt. 11/B 1094 Budapest 1097 1095 Hungary 1097 Email: balazs.a.varga@ericsson.com 1098 Janos Farkas 1099 Ericsson 1100 Konyves Kalman krt. 11/B 1101 Budapest 1097 1102 Hungary 1104 Email: janos.farkas@ericsson.com