Deterministic Networking (DetNet) Data Plane - guaranteed Latency Based Forwarding (gLBF) for bounded latency with low jitter and asynchronous forwarding in Deterministic Networks

1.1. Terminology

CaaS

Control as a Service. Cloud (compute) and network services to enable control (loops) with network connected devices, for example cars.¶

CQF

Cyclic Queuing and Forwarding. A queuing mechanism defined by annex T of IEEE802.1Q.¶

DT

Dead Time. A term from CQF indicating the time during each cycle in which no frames can be sent because the the receiving node could not receive it into the desired cycle buffer.¶

node

Term used to indicate a system that with respect to gLBF does not act as a host, aka: sender/receiver. This memo avoids the term router to avoid implying that this is an IP/IPv6 router, as opposed to an LSR (label switch router). Likewise, a node can also be an 802.1 bridge implementing gLBF.¶

TCQF

Tagged Cyclic Queuing and Forwarding. The mechanism specified in this memo.¶

1.2. Summary

This memo proposes a mechanism called "guaranteed Latency Based Forwarding" (gLBF) for hop-by-hop packet forwarding with per-hop deterministically bounded latency and minimal jitter.¶

gLBF is intended to be useful across a wide range of networks and applications with need for high-precision deterministic networking services, including in-car networks or networks used for industrial automation across on factory floors, all the way to ++100Gbps country-wide networks.¶

At its foundation, gLBF addresses the problems of burst accumulation and jitter accumulation across multiple hops.¶

Burst accumulation is the phenomenon in which bursts of packets from senders in admission-controlled network will increase across intermediate nodes. This can only be managed with exponential complexity in admission control processing and significantly worst-case increase in end-to-end latency and/or lowered maximum utilization. What is needed for dynamic, large-scale or easy to manage admission control solutions are forwarding mechanisms without this problem, so that admission control for bandwidth and jitter/buffer-requirements can be linear: decomposed into solely per-hop calculations independent of changes in prior-hop traffic characteristics. Without forwarding plane solutions to overcome burst accumulation, this is not possible¶

Existing solutions addressing burst-accumulation do this by maintaining inter-packet gaps on a per-flow basis, such as in TSN Asynchronous Traffic Shaping (TSN-ATS). gLBF instead ensures inter-packet gaps are always maintained without the need for per-flow state. The basic idea involves assigning a specific queuing delay budget for any given node and class of traffic. This budget is pre-known from admission control calculus. As the packet is transmitted, the actual queuing delay that was experienced by the packet at the node is subtracted from that budget and carried in a new header field of the packet. Upon receiving the packet, the subsequent node subjects the packet to a delay stage. Here the packet needs to wait for the time specified by that parameter before the node proceeds with regular processing of the packet. This way, any queuing delay variations are absorbed and deterministic delay without the possibility of burst accumulation can be achieved.¶

By addressing burst-accumulation, gLBF also overcomes the problem of jitter-accumulation. This is the second core problem of mechanisms such as TSN-ATS: Depending on the amount of competing admitted traffic on a hop at any point in time packets of a flow may experience zero to maximum delay across the hop. This is the per-hop jitter. This jitter is additive across multiple hope, resulting in the inability for applications requiring (near) synchronous packet delivery to solely rely on such mechanisms. It likewise limits the ability of high utilization of networks with large number of bounded latency flows.¶

The basic principle on which gLBF operates was already proposed by researchers in the early 1990th and called "Dampers". These dampers where not pursued or adopted due to the lack of network equipment capabilities back then. Only with recent and upcoming improvements in advanced forwarding planes will it be possible to build these technologies at scale and cost.¶

Contrary to other proposals, gLBF does not require network wide clock synchronization. Likewise, it does not need to maintain per-flow state at network nodes, as delay budget and the queuing delay variations that are to be absorbed are carried as part of the packets themselves, making them "self-contained". This eliminate the for the per-flow, per-hop state maintenance required by TSN-ATS, which involves scaling problems of signaling this per-flow state to every hop from the controller-plane as well as the high-speed networking hardware implementation cost of high-speed speed read/write memory access to retrieve, process and update these per-flow state variables for large number of flows.¶

Opposed to other damper proposals, gLBF also supports the queuing model and calculus of Urgency Based Scheduling (UBS, [UBS]), which is used by TSN-ATS. gLBF is intended to be a plug-in replacement for TSN-ATN or as a parallel mechanism beside TSN-ATS because it allows to keeping the same controller-plane design which is selecting paths for TSN-ATS, sizing TSN-ATS queues, calculating latencies and admitting flows to calculated paths for calculated latencies.¶

While gLBF as presented here is intended for use with IETF forwarding protocols and to provide DetNet QoS for bounded latency and lower bounded jitter, it would equally applicable to other forwarding planes, such as IEEE 802.1 Ethernet switching - assuming appropriate packet headers are defined to carry the hop-by-hop and end-to-end metadata required by the mechanism.¶

1.3. Application scenarios and use cases

gLBF addresses the same use cases that are targeted by deterministic networking and high-precision networking services in general. Common requirements of those services involve the need to provide service levels within very tightly defined service level bounds, in particular very specific latencies without the possibility of congestion-induced loss. The ability to provide services with corresponding service level guarantees enables many applications that would simply not be feasible without such guarantees. The following describes some use cases and application scenarios.¶

The development towards autonomous driving vehicles leads to new requirements and a high demand of computational resources that are often not available within a car. A solution is to reduce the in-car processing to a minimum, and to offload more computational expensive tasks to the cloud environment. Due to the safety implications and use cases, a delay in the transport of message from the cloud to the car and vice versa is often not acceptable. This includes application scenarios such as trajectory planning for driverless vehicles, but also emergency notifications to surrounding cars that require a fast delivery of messages to prevent a delayed action in case of an accident. While the usage of TSN for in-vehicle networks is already investigated and more mature, the usage of a real-time communication with guaranteed latencies for vehicles with to the cloud is still an open challenge.¶

Another use case that is important for the automotive industry is to further optimise the manufacturing process by taking into account more data sources. Since most of the SCADA systems and PLCs cannot connect to large data lakes and perform more advanced computational jobs, a real-time communication to the shop floor from a cloud instance does have several benefits. First of all does it integrate more data into the decision making process, since the control algorithms to automate manufacturing sites located in a cloud environment can take into account more variables than single plant control systems. Another aspect is also to reduce the resources on a particular factory floor or plant by transferring complex, recurring and more resource computational jobs to a cloud provider where a lack of computational power is not the limiting factor. However, in such cases it is important that associated control can still occur in real-time and according to very precise timing constraints. Such a development is already foreseen by trends such as Industry 4.0 and Control-as-a-Service (CaaS).¶

1.4. Background

The following background introduces and explains gLBF step by step. It uses IEEE 802.1 "Time Sensitive Networking" (TSN) mechanisms for reference, because at the time of this memo, TSN bounded latency mechanisms are the most commonly understood and deployed mechanisms to provide bounded latency and jitter services.¶

All mechanisms compared here are as well as those used by TSN based on the overall service design that traffic flows have a well-defined rate and burstyness, which are tracked by the controller-plane and called here the "envelope" of the flow.¶

The traffic model used for gLBF is taken from UBS gives the flow a rate r [bps/sec] and a burst size b [bits] and the traffic envelope condition is that the total number of bits w(t) over a period t [sec] of for the flow must be equal to or smaller than (r * t + b). In one typical case, a flow wants to send a packet of size b one every interval of p [sec]. This translates into a rate r = b / p for the flow because after the flow has sent the first packet of b bits, it will take p seconds until (r * t) has a size of b again: (r * t) = ((b / p) * p).¶

The controller-plane uses this per-flow information to calculate for each flow a path with sufficient free bandwidth and per-hop buffers so that the bounded end-to-end latency of packets can be guaranteed. It then allocates bandwidth and buffer resources to the flow so that further flows will not impact it.¶

Within this framework, bounded latency mechanisms can in general be divided into "on-time" and "in-time" mechanisms.¶

2.1. Dampers

The principle of the mechanism presented here is the so-called "Damper" mechanism, first mentioned in the early 1990th, but never standardized back then, primarily because the required forwarding was considered to be too advanced to be supportable in equipment at the time. These limitations are not starting to be resolved, and hence it seems like a good time to re-introduce this mechanism.¶

The principle of damper based forwarding is easily explained: When a packet is sent by a node A, this node will have measured the latency L, how long the packet was processed by the node. The main factor of L is the queuing latency of the packet in A because of competing traffic sent to the same outgoing interface. Based on the admission control and queuing algorithms used in the node, there can be a known upper bound M(ax) for this processing latency though, and when the packet then arrives at the next-hop receiving node B, this node will simply further delay the packet by (B-L), and in result the packet will have synchronously been forwarded from A to B with a constant latency of M(ax).¶

+------------------------+      +------------------------+
| Node A                 |      | Node B                 |
|   +-+         +-+      |      |   +-+         +-+      |
|-x-|F|---------|Q|------|------|-x-|F|---------|Q|------|
|   +-+         +-+      | Link |   +-+         +-+      |
+------------------- ----+      +------------------------+
  |<--------- Hop A/B latency --->|

Figure 1 shows a single hop from node A to node B without Dampers.¶

A receives a packet. The F)orwarding module determines some outgoing interface towards node B where it is enqueued into Q because competing packets may already be in line to be sent from Q to B. This is because packets may be arriving simultaneously from multiple different input interfaces on A (not shown in picture), and/or the speed of the receiving interface on A is higher than the speed of the link to B.¶

Forwarding F can be L2 switching and/or L3 routing, the choice does not impact the considerations described here.¶

When the packet is finally sent from Q over link to B, B repeats the same steps towards the next (not shown) node.¶

(x) is the reception time of the packet in A and B, and the per-hop latency of the packet is xB - xA, predominantly determined by the time the packet has to wait in Q plus any other relevant processing latency, fixed or variable from F plus the propagation latency of the packet across link, which is predominantly determined by the serialization latency of the packet plus the propagation latency of the link, which is the speed of light in the material used, for example fiber, where the speed of light is 31 percent slower than across vacuum.¶

All the factors impacting the hop A/B latency other than Q in A are naturally bounded: A well defined maximum can be calculated or overestimated. The transmission of the packet from A to B is composed from the serialization latency of the packet which can be calculated from the packet length of the packet and per-packet-bit speed of the packet. The propagation latency through the link can be calculated from speed of light and material (speed of light is 31% slower through fiber than vacuum for example). And so on.¶

To have a guaranteed bounded latency through Q, an admission control system is required that tracks, accounts and limits the total amount of traffic through Q. Admission control mechanisms rely on knowing the maximum amount of bursts that each traffic flow can cause and adding up those bursts to determine the maximum amount of simultaneous packet data in Q that therefore impacts the maximum latency of each individual packet through Q.¶

With such an admission control system, one can therefore calculate a maximum hop A/B propagation latency MAX for a packet, but packets will naturally have variable hop A/B latency lower than MAX, based on differences in packet size and differences in competing traffic. In result, their relative arrival times xB in B will be different from their relative arrival times xA in A. This leads to so-called "burst-aggregation" and hence the problem that the admission control system can not easily calculate the maximum burst and latency through Q in B as it can do for Q in A.¶

If however packets could be made to be forwarded such that their Hop A/B latency would all be the same (synchronous, on-time), then the admission control system could apply the same calculus to B as it was able to apply to A. This is what damper mechanisms attempt to achieve.¶

+------------------------+      +------------------------+
| Node A                 |      | Node B                 |
|   +-+   +-+   +-+      |      |   +-+   +-+   +-+      |
|-x-|D|-y-|F|---|Q|------|------|-x-|D|-y-|F|---|Q|------|
|   +-+   +-+   +-+      | Link |   +-+   +-+   +-+      |
+------------------------+      +------------------------+
        |<- A/B in-time latency ->|
        |<--A/B on-time latency ------->|

Figure 2 shows the most simple to explain, but not implement, Damper mechanism to achieve exactly this. Node A measures the time at xA, sends this value in a packet header to B. B measures the time directly at reception of the packet in xB. It then delays the packet for a time (MAX-(xB-yA)). In result, the latency (yB-yA) will exactly be MAX, up to the accuracy of the damper.¶

The first challenge with simple approach is the need to synchronize the clocks between A and B, so that (xB-yA) can correctly be calculated.¶

+------------------------+      +------------------------+
| Node A                 |      | Node B                 |
|   +-+   +-+   +-+      |      |   +-+   +-+   +-+      |
|-x-|D|-y-|F|---|Q|----z-|------|-x-|D|-y-|F|---|Q|----z-|
|   +-+   +-+   +-+      | Link |   +-+   +-+   +-+      |
+------------------------+      +------------------------+
        |<- A/B in-time latency ->|
        |<--A/B on-time latency ------->|

Figure 3 shows how this can be resolved by also measuring the time at z. A calculates d = (MAX1-(zA-yA)) and sends d in a header of the packet to B. B then delays the packet in D by d relative to the also locally measured time xB. Because the calculation of d in A and the delay by d in D does not depend on clock synchronization between A and B anymore, this approach eliminate the need for clock synchronization.¶

But in result of this change, the measurement of latency incurred by transmitting the packet over link is also not included in this approach.¶

MAX1 in this approach is the bounded latency for all processing of a packet except for this link propagation latency P, equivalent to the speed of light across the transmission medium times the length of the medium, and MAX = MAX1 + P.¶

The serialization latencies latency across the sending interface on A and the receiving interface on B can be included in MAX1 though. It is only necessary for the measured timestamps zA and xB to be the logically for the same point in time assuming the link had a minimum length, e.g.: for a back to back connection. For example, the reference time is the time when the first bit of the packet can be observed on the shortest wire between A an B. A can most likely measure zA only some fixed offset o of time before r, hence needs to correct zA += o before calculating d. Likewise, B could for example only measure xB exactly after the whole packet arrived. this would be l * r later than the reference time, where r is the serialization rate of the receiving interface on B and l is the length of the packet. B would hence need to adjust d -= l * r to subtract this time from the time the packet needs to be delayed in D.¶

+------------------------+      +------------------------+
| Node A                 |      | Node B                 |
| +-+    +-+   +-+   +-+ |      | +-+    +-+   +-+   +-+ |
|-|F|--x-|D|-y-|Q|-z-|M|-|------|-|F|--x-|D|-y-|Q|-z-|M|-|
| +-+    +-+   +-+   +-+ |      | +-+    +-+   +-+   +-+ |
+------------------------+      +------------------------+
       |<- Dampened Q ->|              |<- Dampened Q ->|
             |<- A/B in-time latency ->|
             |<--A/B on-time latency ------->|

Figure 4 shows a further refined model for simpler implementation. Larger routers/switches are typically modular, and forwarding happens on a different modular component (such as a linecard) than the queuing for the outgoing interface. Expecting clock synchronization even within such a large device is undesirable.¶

In result, Figure 4 shows damper operation as occurring solely before enqueuing packets into Q and after dequeuing them. The Damper module measures the x timestamp, extracts d from the packet header, adjusts it according to the above described considerations and then delays the packet by that value and enqueues the packet afterwards. After the packet is dequeued, the Marking module measures the time z, adjusts it according to the previously described considerations calculates the value of d and overwrites the packet header before sending the packet.¶

2.2. Dampers and controller-plane

         Controller-plane:
        Path Control  and
         Admission Control
      ..     .      .      ..
     .       .       .       .
   +---+   +---+   +---+   +---+  Src---| A |---| B |---| C |---| D |
   +---+   +---+   +---+   +---+
     |       |       |       |
   +---+   +---+   +---+   +---+
   | E |---| F |---| G |---| H |--- Dst
   +---+   +---+   +---+   +---+

While the damper mechanism described so far can be realized with different queuing mechanisms and hence different calculus for every interface for which bounded latency can be supported, the role of the controller plane involves other components beside admission control, and those need to be possible to tightly be coupled with admission control for efficient use of resources.¶

Figure 5 shows the most common problem. The controller-plane needs to provide for a new traffic flow from Src to Dst a path through the network and reserve the resources. The most simple form for just bandwidth reservation is called Constrained Shortest Path First (CSPF). With the need to also provide end-to-end latency guarantees in support of bounded latency, not only does the path calculation becomes more complex, but many per-hop bounded latency queuing mechanisms support also to select more than one per-hop latency on the hop, and the controller-plane needs to determine for each hop of a possible hop, which one is best.¶

In result, the controller-plane needs to know exactly what parameters the bounded latency queuing mechanism on each hop/interface can have to perform these operations, and standardization of these parameters ultimately results in standardizing the bounded latency queuing mechanism - and not only the damper part.¶

3.1. Damper with UBS queuing/calculus

guaranteed Latency Based Forwarding (gLBF) is using the queuing model of Urgency Based Scheduling (UBS), which is also used in TSN Asynchronus Traffic Shaping (TSN-ATS). This allows gLBF to re-use or co-develop one and the same controller-plane and its optimization algorithms for bandwidth and latency control for TSN-ATS or a DetNet L3 equivalent thereof and gLBF. Hence, gLBF should provide the most easily operationalised on-time solution for networks that want to evolve from an in-time model via TSN-ATS, or that even would want to operate both options in parallel.¶

Effectively, gLBF replaces the per-flow interleaves regulators of UBS with per-flow stateless damper operations. Where UBS only provides for in-time latency guarantees, gLBF provides in result in-time latency service, but with fundamentally the same calculus as UBS.¶

   +-----------------------------------------------+
   | UBS strict priority Queuing block             |
   |                                               |
   |               +--------------+   +----------+ |
   | +-------+   /-| Prio 1 queue |---|          | |
   | | Packet|  /  +--------------+   | Strict   | |
-->| | Prio  |->         ...         -| Priority | |--->
   | | enque |  \  +--------------+   | Schedule | |
   | +-------+   \-| Prio 8 queue |---|          | |
   |               +--------------+   +----------+ |
   +-----------------------------------------------+

Strict Priority Scheduling removes packets always from the highest priority queue (1 is highest) that has a pending packet and forward it. UBS defines two options for the traffic model traffic flows. The more flexible one defines that each flow specifies a rate r and a maximum burst size b (in bits).¶

In result, the bounded latency of a packet in priority 1 is (roughly) the latency required to serialize the sum of the bursts of all the flows admitted into priority 1. The bounded latency of a packet in priority 2 is that priority latency plus the latency required to serialize the sum of the bursts of all the flows admitted into priority 2. And so on.¶

3.2. gLBF processing

The following text extends/refines the damper processing as necessary for gLBF.¶

   +------------------------+       +------------------------+
   | Node A                 |       | Node B                 |
   | +-+    +-+   +-+   +-+ |       | +-+    +-+   +-+   +-+ |
 --|-|F|--x-|D|-y-|Q|-z-|M|-|-------|-|F|--x-|D|-y-|Q|-z-|M|-|--->
IIF| +-+    +-+   +-+   +-+ |OIF IIF| +-+    +-+   +-+   +-+ |OIF
   +------------------------+       +------------------------+
          |<- Dampened Q ->|               |<- Dampened Q ->|
                |<- A/B in-time latency -->|
                |<--A/B on-time latency -------->|

The Delay module retrieves the delay from a packet header fields, requirements for that packet header field are defined in Section 3.4.¶

Because serialization speeds on the Incoming InterFace (IIF) will be different for different IIF, and because D will likely need to compensate the measured time x based on the packet length and serialization speed, an internal packet header should maintain this information. Note that this is solely an implementation consideration and should not impact the configuration model of gLBF.¶

The Queuing module is logically as described in UBS, except that the priority of a packet in gLBF is not selected based on per-flow state, but instead an appropriate packet header field of the packet is looked up in the Packet Prio Enque stage of Q and the packet accordingly enqueued based on that fields value. Possible options for indicating such a priority in a packet header field are defined below in Section 3.4.¶

Like Q, M also needs to look up the packet priority to know MAX1 for the packet and hence calculate d that it rewrites in the packet header.¶

The overall configuration data model to be defined for gLBF is hence the configuration data model for UBS, which is a set of priority queues and their maximum size, and in addition for gLBF for each of these queues a controller-plane calculated MAX maximum latency value to be used by M.¶

Given how the node knows the serialization speed of OIF, MAX1 for each of the queues could automatically be derived from the maximum length in bytes for each of the UBS priority queues, but this may not provide enough flexibility for fine-tuning (TBD), especially when packet downgrade as describe below is used.¶

TBD: paint a small yang-like data model, even though its trivial, like in the TCQF draft. This should primarily include additional diagnostic data model elements, such as maximum occupancy of any of the priority queus and number of overruns.¶

3.3. Error handling

A well specified standard for a damper mechanism such as described in this document needs to take care of error cases as well. The prime error condition is, when the sending node A of a gLBF packet recognizes that the packet was enqueued for longer than MAX1 and hence the to-be-calculated delay to be put into the packet would have to be < 0.¶

In this case, error signaling, such as ICMPv6/ICMP needs to be triggered (throttled !), and the packet be discarded - to avoid failure of admission control / congestion further down the path for other packets as well.¶

The data model (below) describes an optional data model that allows instead of discarding of the packet to signal an ECN like mechanism together with lower-priority forwarding of such packet to inform the receiver directly about the problem and allow the application to deal with such conditions better than through other error signaling.¶

3.4. Data Model for gLBF packet metadata

gLBF is specifically designated to support per-hop, per-flow stateless operations because it does not require any per-flow, but only per-packet metadata for its processing. While it is possible to¶

3.5. Ingress and Egress processing

4.1. gLBF versus UBS / TSN-ATS

By relying on [UBS] for both the traffic model as well as the bounded latency calculus, gLBF should be easy to operationalize by relying on controller-plane implementations for TSN-ATS: UBS/TSN-ATS and gLBF provide the same bounded latency and use the same model to manage bandwidth for different flows: By calculating which flow needs to go on which hop into which priority queues.¶

The main change to a UBS/TSN-ATS controller-plane when using gLBF is that when a flow is to be admitted into the network, removed, or rerouted. In UBS, each of these operations imply that the controller-plane needs to signal to each node along the path the traffic flow parameters so the forwarding plane can establish the per-hop,per-flow state for the flow. Depending on network configuration this will also imply configuration of the next-hop for the flow for the routing.¶

For gLBF hop-by-hop operations, the first hop needs to receive the per-path or per-hop priority information that is then imposed into an appropriate packet header for the flows packets.¶

4.2. first-hop policing

In gLBF, the controller-plane has to perform this action only against the ingress node to the gLBF domain. The traffic parameters such as rate and burst size are only relevant to establish a policer so that the flow can not violate the admitted traffic parameters for the flow. This "policing" on the first hop is actually a function independent of gLBF, UBS or any other method used across the path.¶

4.3. path steering

gLBF operated independently of the path steering mechanism, but the controller-plane will very likely want to ensure that gLBF (or for that matter any DetNet) traffic does not unexpectedly gets rerouted by in-networking routing mechanisms because normally it will or can not reserve resources for such re-routed flows on such arbitrary failure paths without significant additional effort and/or waste of resources.¶

A.1. High speed example pseudocode instead of reference pseudocode

This memo does not describe a normative reference code that aligns with the normative functional description above Section 3. The primary reason is that a naive 1:1 implementation of the functional description would lead to inferior performance. Nevertheless, the feasibility of high speed implementations is an important factor in the ability to deploy mechanisms like gLBF. Therefore, this appendix describes considerations for such high speed implementations including pseudocode for on possible option.¶

[gLBF] describes two approaches for possible optimized hardware implementation approaches for gLBF. One using "Push In First Out" (PIFO) queues, the other one times FIFO queues. The following is a representation and explanation of that second approach because it is hopefully more feasible for nearer term hardware implementations given the fact that scalable FIFO high-speed hardware implementations are still a matter for research.¶

However, the timed FIFO style algorithm presented here is also subject to possible scalability challenges for hardware because it requires for each outgoing interface O(IIF * priorities^2) number of FIFO queues, where IIF is the number of (incoming) interfaces on the node, and priorities is the number of priority levels desired (TSN allows up to 8). If however the priority of flows (packets) used is not per-hop but the same for every hop (per-path), then the number is just (IIF * priorities).¶

A.2. UBS high speed implementations

The algorithm for the pseudocode shown in this appendix further down in this section is based on the analysis of gLBF behavior done in and for [gLBF]. This analysis re-applies the same type of analysis and algorithm that was done in [UBS] and can be used to implement TSN-ATS in high speed switching hardware. Therefore, this appendix will start by explaining the UBS mechanisms.¶

UBS (see [UBS], Figure 4), logically consists of two separate stages. The first stage is a per priority, per incoming interface (IIF) interleaved regulator. An interleaved regulator is a FIFO where dequeuing of the queue head packet (qhead) is based on the per-flow state of qhead.¶

A target departure time for that qhead is calculated from the flow state of the packet maintained on the router across packets and once that departure time is reached, the packet is passed to one of the egress strict priority queues. This is called interleaved regulator, because the FIFO will have packets from multiple flows (all from the same incoming interface and outgoing priority), hence 'interleave', and regulator because of the delaying of the packet up to the target departure time.¶

The innovation of interleaved regulators as opposed to the prior per-flow shapers as used in [RFC2210] is the recognition and mathematical proof that the arrival and target departure times of all packets received from the same IIF (prior hop node) and the same egress priority will be in order and that they can be enqueued into a single FIFO where the per-flow processing only needs to happen for the qhead. Without (anything but negligible) added latency vs. per-flow shapers.¶

With this understanding, the interleaved regulator and following strict priority stage can easily be combined into a single queuing stage with appropriate scheduling. In this "flattened" approach, each logical egress strict priority queue consists of the per-IIF interleaved regulator (FIFO queue) for that priority.¶

Scheduling of packets on egress does now need to perform the per-queue processing of the per-flow state of the qhead, and then take the target departure time of that packet into account, selecting the interleaved regulator with the highest priority and earliest target departure time qhead.¶

A.3. gLBF compared to UBS

In gLBF, the very same line of thoughts as in UBS can be applied and are the basis for the described algorithm and shown pseudocode.¶

In glBF, the order of packets in their arrival and target departure times depends on the egress priority, the IIF, but also on the priority the packet had on the prior hop (pprio). All packets with the same (IIF,prio,prio) will arrive in the same order in which they need to depart, and in which it is therefore possible to use a FIFO to enqueue the packets and only do timed dequeuing of the qhead.¶

Both prio and pprio are of interest, because when gLBF uses an encapsulation allowing per-hop priority indications, its priority on each hop can be different. In UBS, priority can equally be different across hops for the same packet, but the prior hop priority is not necessary to put packets into separate interleaved regulators because UBS targets in-time delay, where the interleaved regulator does (only) need to compensate for burst accumulation, but in gLBF the delay to be introduced depends on the damper value which depends on the prior hop priority and in result, the order in which in gLBF packets should depart (absent any burst accumulation) depends also on the prior hop priority.¶

Because gLBF does not deal with per-flow state on the router as UBS does in its interleaved regulators, the FIFOs for gLBF are called timed FIFOs in this memo and not interleaved regulators¶

A.4. Comparison to normative behavior

Whereas the normative description described D, Q and M blocks, where the D block performs the dampening, and the Q block performs the priority queuing block, in the high speed hardware optimization, these are replaced by a single DQ block where the packets are enqueued into a single stage per-(IIF,pprio,prio) FIFO (similar to UBS) and then the dampening happens (similar to UBS) on dequeuing from that stage by the damper time but scheduling/prioritizing packets based on their prio.¶

   +------------------------+       +------------------------+
   | Node A                 |       | Node B                 |
   | +-+    +-------+   +-+ |       | +-+    +-------+   +-+ |
 --|-|F|--x-| DQ y  |-z-|M|-|-------|-|F|--x-| DQ y  |-z-|M|-|--->
IIF| +-+    +-------+   +-+ |OIF IIF| +-+    +-------+   +-+ |OIF
   +------------------------+       +------------------------+
          |<- Dampened Q ->|               |<- Dampened Q ->|
                 |<- A/B in-time latency ->|
                 |<--A/B on-time latency -------->|

In the normative definition, the damper value to be put into the packet depended on the time y, where the packet left the damper stage D and entered the priority queue stage Q. Simplified, the damper value is (MAX1 - (z - y)).¶

In the high-speed implementation, the packets are not passed from a damper state queue to a priority queue. Instead they stay in the same queue. This is on one hand one of the core reasons why this approach can support high speed - it does not require two-stage enqueuing/dequeing/ But it eliminates also the ability to take a time stamp at time y.¶

To therefore be able to replicate the normative gLBF behavior with a single stage, it is necessary in the marking stage M (where the new damper value is calculated), to somehow know y.¶

Luckily, y is exactly the target departure time of the packet for the D and therefore also the DQ stage, so already needs to be calculated on entry to DQ by calculation: y = (x + damper - <details>), as explained below.¶

The pseudocode consists of glbf_enqueue() describing the enqueuing into the DQ stage, and glbf_dequeue() describing the dequeuing from the DQ stage. glbf_dequeue() (synchronously) calls glbf_send() which represents the marking stage M.¶

A.5. Pseudocode

void glbf_enqueue(pak,oif) {
  tdamp = pak.header.tdamp // damper value from packet
  prio  = pak.header.prio  // this hops packet prio
  pprio = pak.header.pprio // previous hops packet prior
  iif   = pak.context.iif  // incoming interface of packet

  ta = adj_rcv_time(now(),                  \[1]
                    pak.context.iif.speed,
                    pak.context.length)

  td = now() + ta // (dampened earliest) departure time
  pak.context.max1 = max1\[oif,prio]
  enqueue(pak, td, q(oif,iif,prio,pprio))
}

time_t adj_rcv_time(now, speed, length) {
  time_t now
  int speed, length

  return now - length * 8 / speed - FUDGE
}

void glbf_dequeue(oif) {
  next_packet: while(1) {
    tnow = now()
    ftd = tnow + 1  // time of first packet to send
    fq = NULL      // queue of first packet to send
    foreach prio in maxpriority...minpriority {
      foreach iif in iifs {
        foreach pprio in priorities}
          // find qhead with earliest departure time
          if (q = q(oif,iif,prio,pprio).qhead) {
            td = q.qhead.td   // target (departure) time
            if td < ftd
              ftd = td
              fq = q
            }
          }
        }
      }
      if fq { // found packet
        pak = dequeue(q,oif)
        glbf_send(oif,tnow,pak)
        break next_packet
      }
    }
  }
}

void glbf_send(oif,tnow,pak) {
  qtime = tnow - pak.context.td          // \[1]
  td = pak.context.max1 - qtime - FUDGE2 // \[2]
  pak.header.tdamp = td
  serialize(oif,pak)
}

A.6. Performance considerations

IEEE 802.1 PTP clock synchronization does need to capture the accurate arrival time of PTP packets. It is also measuring the residency time of PTP packets between receiving and sending the packet with an accuracy of nsec and add this to a PTP packet header field (correctionField). Given how this needs to be a hardware supported functionality, it is unclear whether there is a relevant difference supporting this for few PTP signaling packets as compared to a much larger number of gLBF data packets - or whether it is a good indication of the feasibility packet processing steps gLBF requires.¶