Towards a PAR (or PARs) for
Pulsed Queues
Norman Finn
Huawei Technologies Co. Ltd
nfinn@nfinnconsulting.com
new-finn-pulsed-queuing-0821-v04

Why?
new-finn-pulsed-queuing-parts-1221-v01

Why a new PAR and document?
● Asynchronous Transmission Selection (ATS, IEEE Std 802.1Qcr) provides
bounded end-to-end delivery time and freedom from congestion loss, but
apparently requires per-stream state machines to be configured at each hop
along the path, and considerable computation effort when a stream is added
to the network.
● The Credit Based Shaper (CBS) can also, with sufficient analysis, provide
bounded delivery time and zero congestion, again with per-hop configuration
at stream add time.
● Cyclic Queuing and Forwarding (CQF, IEEE Std 802.1Q-2018 Annex T) provides
the same guarantees, with trivial calculations and no per-hop configuration
when adding a stream, but with much longer delivery times, and such poor
efficiency, scalability, and flexibility that CQF is not useful in its present state.
● We will show that Pulsed Queuing, Multi-CQF and Paternoster are (mostly)
special cases and/or optimizations of the more general Asynchronous Traffic
Shaping.
new-finn-pulsed-queuing-parts-1221-v01

Detailed descriptions● Mick Seaman has described the Paternoster shaping algorithm in
cr-seaman-paternoster-policing-scheduling-0519-v04.
● Norman Finn has described Multi-level Cyclic Queuing and
Forwarding (Multi-CQF) in new-finn-multiple-CQF-0921-v02, and amethod for synchronizing a CQF receiver with the transmitter fromwhich it is receiving, in new-finn-CQF-sync-method-1121-v1.

new-finn-pulsed-queuing-parts-1221-v01

What is Pulsed Queueing?
new-finn-pulsed-queuing-parts-1221-v01

What is Pulsed Queuing?
Pulsed Queuing has five parts:
1. A transmission selection algorithm, Pulsed Queuing, that divides a class-of-service
queue into some number of logical bins that are output in strict rotation at aconstant frequency;
2. An algorithm, multi-Cyclic Queuing and Forwarding (mCQF), for storing received
frames into Pulsed Queue bins based on the time of reception of the frame;
3. An algorithm, Paternoster, for storing received frames into Pulsed Queue bins
based on per-Stream bit/byte counters;
4. An algorithm, PQ Aggregation, for aggregating, disaggregating and reaggregating
streams into and out of compound streams that is suitable for use with Pulsed
Queuing;
5. A protocol for locking a CQF receiving to its transmitter; and6. A method for perfect syntonization of a region in the network, i.e. a means forbounding the cumulative difference in elapsed time as measured between any pairof nodes in the region over an arbitrary length of time.
new-finn-pulsed-queuing-parts-1221-v01

Current queuing models● Paternoster and Multi-CQF
have been described, so far, as
using two or more queues,
along with a timer mechanism
to enable one queue at a time,in sequence, for transmission
selection.
● A different class of service isused for each queue.

input ports or Streams
CQF time- orPaternoster byte-countbased queue selection

queues
P802.1Qbv timed
transmission gatespriority transmission selection
output port

new-finn-pulsed-queuing-parts-1221-v01

input ports or Streams

Pulsed Queuing● A “Pulsed Queuing” model ispreferable, going forward.
● Queue selection in the current
model becomes bin selectionin the Pulsed Queuing model.
● One class of service queue has
multiple bins that are rotated(enabled for transmission
selection) by an internal clock.

CQF time- orPaternoster byte-countbased bin selection

multiple bins in
one queue

time-based bin
rotationpriority transmission selection
output port

new-finn-pulsed-queuing-parts-1221-v01

8

Pulsed Queuing is similar to ATS.
● Pulsed Queuing “bins” are equivalent to assigning a number offrames the same ATS transmission eligibility time.
● The methods described here for assigning frames to a bin (mCQF
and Paternoster) differ in detail from those described for ATS.

new-finn-pulsed-queuing-parts-1221-v01

Multi-Cyclic Queuing and
Forwarding andPaternoster
new-finn-pulsed-queuing-parts-1221-v01

CQF problems: Inflexibility● Each CQF buffer is one classes of service queue, so that ScheduledTransmissions (802.1Qbv) can be used to rotate between them.
Double buffering (one filling, one draining) takes two Class ofService queues. This makes more than one rotation frequency
impractical.
● But, one rotation frequency is inflexible; a low frequency isrequired to support many slow streams, but this results in large
buffers and long per-hop latency for a fast streams.
● Streams with different bandwidth requirements have different
requirements for buffer rotation frequency.
new-finn-pulsed-queuing-parts-1221-v01

input ports or Streams

mCQF
supports
multipleclasses ofservice,each witha different
bufferrotationfrequency

CQF time- orPaternoster byte-countbased bin selection

FAST

HALF
FAST

multiple bins ineach Class ofService queue
SLOW
time-based bin
rotationpriority 5priority 4priority 3priority transmission selection
output port
new-finn-pulsed-queuing-parts-1221-v01

12

CQF problems: Link delay● With two buffers at each hop, one filling and one draining, link
delay, worst-case forwarding delay, and all timing uncertainties
must be subtracted from the buffer rotation time, reducing thetime available for data and/or reducing the buffer rotation
frequency. For many applications (e.g. service providers), thisbecomes untenable.
● By using more than two buffers, and divorcing the receive timeboundaries from the transmit time boundaries, the link delay andforwarding delay no longer directly affect the buffer rotation
frequency.
new-finn-pulsed-queuing-parts-1221-v01

CQF problems: Link delay: Two buffers
Device A(transmitter)In-synch:
WRONG

Device B(receiver)

Add dead
time:
RIGHT

Link
delay

Time à
fillingtransmitting

Link
delay
fillingtransmitting● Annex T of IEEE 802.1Q-2018 fixes long link delay by adding dead time,
which reduces the bandwidth available for CQF streams and sets aminimum cycle time.
new-finn-pulsed-queuing-parts-1221-v01

CQF problems: Link delay: Three buffers
Device A(transmitter)In-synch:
WRONG

Device B(receiver)

Link delay
offset:
RIGHT

Link
delay

Link
delay
fillingtransmitting

Time à
fillingfillingtransmitting● Offsetting the input clock by the link delay means that link delay does not
add to the required dead time. More bandwidth is available for CQF.
● Now, three buffers are required.
new-finn-pulsed-queuing-parts-1221-v01

CQF problems: Ingress conditioning● A stream reservation carried by CQF is implemented by reserving amaximum number of wire-time bits to be transmitted per bin cycle
time for the stream.
● But, MSRP and RAP, the stream reservation protocols, definereservations in terms of worst-case number of maximum-size
frames in a sliding window (MSRP) or as a bandwidth and worstcase burst size (RAP), which are appropriate for describing nonCQF talkers. However, this requires gross over-provisioning when
CQF, as described in Annex T of 802.1Q-2018, is employed.
● Using the Paternoster algorithm for ingress conditioning allows the
bandwidth/burst size characterization, and thus non-CQF talkers,
to be used efficiently with Pulsed Queuing.
new-finn-pulsed-queuing-parts-1221-v01

CQF problems: Ingress conditioning
Stream generated by application: 1 frame per ms
As output by Talker, with interference
1 ms measurement interval

MSRP reservation = 2 frames per 1 ms interval
1 ms cycle time on IEEE Std 802.1Q-2018 Annex T CQF
CQF reservation = 4 frames per 1 ms cycle.

● In a typical case, 4x over-provisioning is required to get from MSRP
to Annex T CQF.
new-finn-pulsed-queuing-parts-1221-v01

CQF problems: Ingress conditioning
Generated stream: 1 frame per ms
As output with interference
RAP reservation = 1 frame per ms, burst = 2
1 ms cycle time on mCQF
CQF reservation = 1 frame per 1 ms.

● mCQF uses Paternoster byte counters, and more than 2 bins, sothat one frame can be deposited in each bin. No overprovisioning,
except to accommodate frequency differences.
new-finn-pulsed-queuing-parts-1221-v01

CQF problems: miscellaneous● mCQF provides a means for adding a fixed delay along a path forevery frame in a stream, in order to equalize delivery times along
multiple paths. This solves the problem of excess data at a multipath merge point after the healing of a failed faster path.
● Having multiple cycle times allows faster streams to use smaller,
faster-cycling buffers, instead of occupying lots of space in slowercycling buffers.
● The paternoster counters allow strict syntonization to be relaxed,
at a negligible cost in over-provisioning, given that Pulsed Queuing,by its nature, requires some over-provisioning as the cost of
reduced calculation and configuration requirements.
new-finn-pulsed-queuing-parts-1221-v01

Pulsed Queuing
Aggregation andDisaggregation
new-finn-pulsed-queuing-parts-1221-v01

PQ Aggregation and Disaggregation
We will look at aggregation and disaggregation in three sections:
1. Aggregation without changing bin rotation frequency.
2. Aggregation with increased bin rotation frequency.
3. Performing both aggregation and disaggregation in a single node.

new-finn-pulsed-queuing-parts-1221-v01

1. Aggregation with constant bin frequency● We will not look at protocols for encapsulating streams.
● Using .1CB Stream Identification, we can encapsulate them and use a single
stream identification unit. (Encapsulation increases the aggregate
bandwidth of the streams, and must be accounted for in the reservation.)● We can choose to not encapsulate, use one stream identification unit percomponent stream, and give all of the streams the same stream_handle.

● As long as we do not shift any stream to a faster or slower bin
rotation frequency, the only effect that aggregation has on mCQF
or Paternoster is to change the amount of per-stream state.
● This works because aggregation/disaggregation does not alter the principlethat frames that start in the same bin stay in the same bin.
new-finn-pulsed-queuing-parts-1221-v01

1. Aggregation with constant bin frequency
P0

1Gb/s

P1

10Gb/s

P3

P0-5

P4
P2
P5
6
6 input paternoster
streams counters

10Gb/sn binssize X
freq. νone mCQF
timer orpaternoster
counterP03

n binssize X
freq. ν

1Gb/s

P124

n binssize X
freq. νP5

mCQF orpaternoster● Streams can be split and merged arbitrarily.
● Fewer counters needed; it still works because all streams share one bin.
● Faster links mean that more streams can be carried in that one bin.
new-finn-pulsed-queuing-parts-1221-v01

1. Aggregation with constant bin frequency
P0

1Gb/s

P1

10Gb/s

P3

P0-5

P4
P2
P5
6
6 input paternoster
streams counters

10Gb/sn binssize X
freq. νone mCQF
timer orpaternoster
counterP03

n binssize X
freq. ν

1Gb/s

P124

n binssize X
freq. νP5

mCQF orpaternoster● Streams can be split and merged arbitrarily.
● Fewer counters needed; it still works because all streams share one bin.
● Faster links mean that more streams can be carried in that one bin.
● But, constant-frequency aggregation does not improve latency, and it
does not reduce buffer space; it only reduces state.
new-finn-pulsed-queuing-parts-1221-v01

2. Aggregation with increased bin frequency● If we reduce the increase the bin rotation frequency (shorten thecycle time), then we can reduce the latency and buffer
requirements in the intermediate nodes.

new-finn-pulsed-queuing-parts-1221-v01

2. Aggregation with increased bin frequency
P0

1Gb/s

P1

10Gb/sP3

10Gb/s
Pagg

P4

1Gb/s

P124

P2
P5
6
6 input paternoster
streams counters

P03

n binssize X
freq. νn binssize X
freq. ν2 bins,size X/10
freq. 10νmCQF or
ptrnstrcounterm binssize X/10
freq. 10νP5

mCqF orptnstrcounters● Frames go from regular bins to tiny bins as they become eligible.
● Each small bin holds only one or a few frames of the aggregate stream.
● Any given component stream (P0, etc.) skips most of the small bins.
● Buffer space and per-hop latency are reduced in intermediate node.
new-finn-pulsed-queuing-parts-1221-v01

2. Aggregation with increased bin frequency● We are using a simple model for aggregating the streams; theoriginal, slow bins are fed the smaller, faster bins in no particularorder, except that we guarantee that each slow bin will be emptied
on time.
● If the small bin/small cycles are kept in phase with the edge nodes,
then mCQF timing can actually be used at the disaggregation point,
dumping 10 fast bins into one slow bin. Otherwise, Paternosterlike byte counters are required.
● Note that the order of the component streams’ frames in thefaster aggregate stream is arbitrary and variable; the only
requirement is that they all meet their original large-bin timing.
new-finn-pulsed-queuing-parts-1221-v01

3. Aggregation/disaggregation in one node
10 1ν streams
A9-5
in 1 10ν aggregate
10 1ν streams
B9-5
in 1 10ν aggregate

A4-0

B4-0

A9-5
B9-5
A4-0
B4-0

10 1ν streams A0-4, B5-9
in 1 10ν aggregate
10 1ν streams B0-4, A5-9
in 1 10ν aggregate● Each component flow is spread, 1 frame per cycle; only one or two
frames of the aggregate are present in the node at any one moment.
● The flows A0-A4 and B0-B4 arrive at the same time, but must exit spreadout over 10 cycles. Same for A5-A9 and B5-B9, a little later.
● In this case, 5x buffers are required, and thus 5x latency. We’re back to
our original problem with big buffers and large per-hop latency.
new-finn-pulsed-queuing-parts-1221-v01

3. Aggregation/disaggregation in one node
● There Ain’t No Such Thing As A Free Lunch.
● Remember that the component streams’ frames are in noparticular order. All of the frames for a new aggregate can arrive atonce, after a long pause.
● Therefore, when the component streams are split and merged, thebuffers required are equivalent to those required if no aggregation
had been performed.
● We can mitigate this, by paying close attention to fan-in, linkspeeds, and which streams aggregate in which ways. You candistribute the component flows’ packets so that they better fit therequirements of the next re-aggregation.
● This is called Asynchronous Traffic Shaping.
new-finn-pulsed-queuing-parts-1221-v01

3. Aggregation/disaggregation in one node
● Fundamentally, if you have a number of uncoordinated TSN flows
passing through one port, you can be unlucky and have all of them
arrive at once. In that case, all have to be buffered and they take awhile to transmit. In the worst case, that happens at every hop.
mCQF and Paternoster assume that worst case, and thus get awaywith trivial shaping (pulsed queues).
● If you take advantage of low fan-in, higher-speed links, and fullknowledge of the characteristics of the flows, you can improve on
the worst case. This is why ATS gives lower latency.
● There Ain’t No Such Thing As A Free Lunch.
new-finn-pulsed-queuing-parts-1221-v01

CQF Transmitter-toReceiver Synchronization
new-finn-pulsed-queuing-parts-1221-v01

The proposed solution
Nearby Cycle
Start timemeasured

Device A(transmitter)

Time
MarkerFrame

Before:
WRONG

Device B(receiver)

Link
delay

CQF Phase
OffsetMessage

DIFFERENCE
TIME in CQF
Phase Offset
MessageappliedNew receive
Cycle
Start time

Time à

new-finn-pulsed-queuing-parts-1221-v01

After:
RIGHT
Link
delay

The proposed solution:transmitter’s end
1. Device A transmits a Timing Marker Frame. This can be any frame, but
it must carry an identification value (TMFID) that changes with eachtransmission.
2. After transmitting the Timing Marker Frame, Device A recovers thetime at which the first bit of the frame was transmitted from the
hardware. IEEE Std 802.3 Clause 90 specifies a method foraccomplishing this.
3. Device A then transmits a CQF Phase Offset Message that contains a)
the TMFID of a Timing Marker Frame, and b) the difference, in local
time, between the start of a recent transmission cycle and the Timing
Marker Frame transmission time recovered in step 2, above.
(Specifically, [time of start of cycle] – [time of start of transmission].)Typically, this time difference would be expressed in increments ofnanoseconds or finer. The cycle chosen may be such that the timedifference is positive or negative.
new-finn-pulsed-queuing-parts-1221-v01

The proposed solution:
receiver’s end
1. Device B receives a Timing Marker Frame. It records the time ofarrival of the first bit of the frame (again, IEEE Std 802.3 clause90), and the TMFID of the frame.
2. Device B receives a CQF Phase Offset Message with a TMFID
matching a recently-recorded Timing Marker Frame.
3. The time of reception of the Timing Marker Frame, plus the(signed) time difference carried in the CQF Phase Offset Message,
is the local time at which the receive cycle that corresponds tothe transmission cycle selected by the transmitter for reporting in
the CQF Phase Offset Message, should have started (or should
start, if in the future). This establishes the cycle start time for thereceiver’s input gates in local time.
new-finn-pulsed-queuing-parts-1221-v01

Syntonization for
Pulsed Queuing
new-finn-pulsed-queuing-parts-1221-v01

Syntonization for Pulsed Queuing● mCQF, i.e. assigning received frames to PQ bins based purely ontime of arrival, requires “perfect” syntonization (frequency lock)over the lifetime of a stream. We will discuss what this means afollowing slide.
● Paternoster, i.e. assigning received frames to PQ bins based on perstream per-port byte counters, can be useful either with orwithout syntonization. If used without, then a degree of overprovisioning is required to prevent buffer overflow at the slowest
port along the path.

new-finn-pulsed-queuing-parts-1221-v01

mCQF Syntonization● In mCQF, frames travel in lock-step, always staying together in the samebin across the network. This requires that all nodes in the network be
perfectly syntonized, in the sense that the difference between two
nodes in the cumulative number of bin rotation cycles that haveoccurred must be bounded, no matter how long they have beenrunning. Otherwise, bins can be delivered to a node faster than it canempty them, and TSN fails.
● The principles used in the IEEE Std 802.1Q-2018 scheduled transmission
feature are adequate to ensure this, i.e. a synchronized start time and arational frequency in seconds. Although synchronized time is notnecessary for the operation of mCQF, synchronizing the clocks ensuresthat, in the long term, they are perfectly syntonized.
● See also new-finn-CQF-sync-method-09-21-v1.
new-finn-pulsed-queuing-parts-1221-v01

Summary
new-finn-pulsed-queuing-parts-1221-v01

Summary● Pulsed Queuing, Multi-CQF and Paternoster are, for the most part,simply special cases of the more general Asynchronous Traffic
Shaping.
● Syntonizing the nodes’ clocks enables an alternative ATS
implementation, Multi-CQF, that reduces the state machinesrequired.
● Pulsed Queuing, Multi-CQF and Paternoster techniques clarify thetradeoffs available for ATS among compute time, configuration
time, overprovisioning, and implementation cost.
● Given the fundamental limitations of the problem space, these
tradeoffs can be useful.
new-finn-pulsed-queuing-parts-1221-v01

Working towards a PAR
new-finn-pulsed-queuing-parts-1221-v01

Elements to consider for a PAR
We should consider the following elements for a PAR scope:
1. Provide descriptions of CQF and Paternoster, but based on ATS,rather than 802.1Qbv scheduling.
2. Provide a protocol for synchronizing a CQF transmitter to its
receiver.
3. Describe the operation of multiple classes of CQF service (multiCQF).
4. Describe how to maintain TSN QoS when aggregating anddisaggregating compound Streams.
5. Provide any managed objects needed to control these features.
new-finn-pulsed-queuing-parts-1221-v01

Thank you
new-finn-pulsed-queuing-parts-1221-v01