Further Details on
Cycle Identification
dv-yizhou-cycle-identification-details-1122-v02

Yizhou Li (Huawei)

Jeong-dong Ryoo (ETRI)

Guanhua Zhuang (Huawei)

Peng Liu (CMCC)

Shoushou Ren (Huawei)

Dong Li (Shenyang Institute of Automation)

Jiang Li (Huawei)

Wenbin Dai (Shanghai Jiao Tong University)

Nov, 20221

Recap and Goal
• dv-yizhou-cycle-identification-0922-v02 in September meeting• Showed the goal to improve the bandwidth utilization in small cycle• Discussed the cycle ambiguity problem when making dead time (DT) minimum toimprove the utilization• Proposed to use implicit reception time indicated by cycle id to determine to whichbin a frame goes in addition to direct hardware timestamp based one in 802.1Qdv• Provided three options to carry cycle id• Slides 4-8 recaps the basic concept of using cycle id. Please refer to theprevious slides for more details if needed.
• Goal of this deck of slides is to answer the questions received:• How to initialize the cycle id based system?
• How to compute cycle and buffer IDs as they have different ID spaces?
• How the mapping works when the #of bins(buffers) are different on two neighbornodes?
• How large should the cycle ID space be? What are the considerations when choosing
the field length of it?
2

Change log• dv-yizhou-cycle-identification-details-1122-v02：• Added clarifications for checksum re-compute, multiple cycle time and computation delay.
• Added explanation on cycle id = implicit pivot reception time
• Editorial changes from -v01

• dv-yizhou-cycle-identification-details-1022-v01:• Early dv-yizhou-cycle-identification-0922-v02 showed why and how to use implicit reception time indicated by cycle
id to determine to which bin a frame goes
• Provided further details on that cycle id based implicit time determination approach• Focus on the initialization, especially how to establish the cycle id mapping relations for the port pairs.

3

Goal - Improve the utilization in small cycle T
T1

Node A(transmitter)
Node B(software
receptiontime)
Node B(transmitter)

T2
DT

T1 rcvwindow

T3

T4

Low utilization
with large DTDT

T2 rcvwindow

Node A(transmitter)

Make DT Node Bminimum (software

T1

T2DT

T3

High utilization
with small DT

T4DT

T2 rcv window
T1 rcv window

Cycle
ambiguity timereceptiontime)DT

Node B(transmitter)

DTDT

DTtimetime• Why low utilization? DT is relatively too large to a cycle.
• A straightforward way to improve utilization: make DT minimum• Absorb only the preemption delay instead of the full time variation, i.e. curve out output delay and processing delay• A remaining problem: cycle ambiguity in software reception time based bin determination4

Propose to use the explicit cycle identification

Node A(transmitter)

T1

T2
DT

1

DT

Dead time imposed at each cycle/Time window for sending or receiving
frames (not a single frame)

T3

T4

DT

2

Cycle ambiguity time

Node B(softwarereception time)

Node B(transmitter)

1

11 2

2

DT

T1

T2

• Carry cycle id and change per hop• Use cycle id as pivot reception time
implicitly for output bindetermination instead of use
software reception time directly• Remove the ambiguity• Achieve the good utilization in small
cycles by making DT minimum

DT

T3

T4time5

How to carry a cycle id
1. R-tag (defined in 802.1CB)
Ethertype (F1-C1)

Reserved (16-bit)

Sequence number (16-bit)

Define a subtype flag and use the last 4-bit in Reserved field for cycle id.
Ethertype (F1-C1)

Reserved (16-bit)
Sequence number (16-bit)flag(1) Rsvd (11) Cycle id (4)6How to carry a cycle id (cont’d)
2. Define a new cycle-tag
Ethertype(cycle-tag)

Subtype Reserved Cycle ID(4-bit)(4-bit)(8-bit)7

How to carry a cycle id (cont’d)
3. Use vlan stacking + vlan mapping function• Inner vlan is used for cycle id, use ACL to map from ingress cycle id toegress cycle id• Outer vlan is used as normal vlan based mac learning and forwarding• Used in a controlled domain, may not be compatible with some existing svlan + c-vlan usage
Ethertype (s-vlan)

vlan-tag (16-bit)

Ethertype (c-vlan)

Cycle id (16-bit)

ACL example: if-match cvlan-id cycle-id-in
remark cvlan-id cycle-id-out8

Further details on Cycle id9

Conceptually cycle id = pivot reception time
• Conceptually Cycle id = pivot reception time of the frame.

• It is a direct timestamp for cycle start time of the frame’s transmission bin on upstream node’s
output port
• Consequently it indicates the pivot reception time of the frame with no/little time variation
experienced on the downstream node’s input port
Pivot reception time.

ACycle id indicates theaccurate cycle startingtime.

BReception time ≠ Pivot reception time, directly
using reception time may cause ambiguity issue- Output delay variation at the upstream- No 1st bit hardware timestamp available- Reception time determination happens atprocessing- Packet processing is system clock based

Reception Time

Cycle idA

Cycle id

Cycle id = Pivot reception time conceptually(As the propagation delay between A & B hasno variation).

B
Reception time on system clock ≠ Pivot reception
time
So use the implicit pivot reception time indicatedby cycle id instead of the direct reception time
here.
Reception Time10Some assumptions in this deck to simplify theillustration• Only one priority class uses Qdv mechanisms at a physical port.
• The configuration and calculation is for that priority.
• Cycle time Tc remains the same for the same priority in the domain.
• The slides provide a practical way in implementation as example, but
it is not the only way.
• Try to reuse terms defined in new-finn-multiple-CQF-0921-v02 as
much as possible

11Terms – buffer related• n: the number of physical ports. Range: 0 ~ n-1• Bi,o: the number of buffers required for the input and output port pair(i, o)• Bo：the number of physical output buffers on port o.
Bo = Max(Bi,o), i = 0 ~ n-1 on a given port o• buf_id ：• id assigned to the physical buffer in which a frame should be placed at output
port o when the frame is processed.
• buf_id  [0, Bo -1]

Note: All values are integers

12Terms – latency related• TV: sum of the frame-based time variations• Include output delay variation, processing delay variation and link delay variation• Link delay is the first-bit-out to last-bit-in delay that varies with packet size

• TVi,o: TV value for the input and output port pair (i, o).
• Calculate Bi,o as follows:
Bi,o = floor(TVi,o / Tc) +4 --- baseline
Node A(transmitter)

Node B(software
receptiontime)

T1

T2

T3

• Max receiving window time interval Tc+TVio• # of receiving buffer to accommodate the max
receiving window time:
floor((Tc+TVi,o)/ Tc) + 2 = floor(TVi,o/ Tc) + 3• # of sending buffer = 1• Hence, Bi,o = receiving buffer + sending buffer= floor(TVi,o/ Tc) + 4• Special cases:T4

T1 rcv window= Tc+TVio•use one less buffer, i.e. Bi,o = floor(TVi,o / Tc) +3•

Node B(transmitter)•time

rev window spans over 2 cycles in case of lucky or intentional cycle
phase shift between A & B. We assume A&B independently run
cycles here, hence always use at least the baseline calculation

Use more buffers, i.e. Bi,o = floor(TVi,o / Tc) +5/6/../n•

Introduce intentional extra delay, e.g. to balance replicated frames
over diff paths

13Terms – cycle related• cycle_id: cycle id assigned to a frame when the frame is placed to abuffer with buf_id at an output port o• Max value of cycle_id C is limited by the field length, e.g. if length is 4, then C= 16, so that cycle_id [0, 15]• C is the same for all ports on all nodes in a domain• increments (modulo C) each cycle time

• N: the least common multiple over all Bo and C in a node. Value of N
can be different on the nodes.
• Si: Each input port i assigns each received frame a logical buffer
selector Si, which is an integer in the range 0 through N-1, and which
increments (modulo N) each cycle. The value of Si is si.
• si is directly used by data frames, not for (cycle) mapping determination
frames.

Note: All values are integers

14

4 steps in initialization and determination inthe following slides• Step 1: Base parameter provisioning
One-time static
calculation and• Step 2: Initialization of buffer selector and output buffers provisioning• Step 3: Determination of cycle id mapping relation for port pair (i,o)• Step 4: Determination of output cycle id and buffer id for data frame• This step is for real data traffic, not part of initialization and provisioning.
for each data frame

15

Example Step 1– base parameter provisioning
Logical Buffer
Selector Si

PhysicalBuffers1

s10 1 2 3 4 5 … 21 22 23

52s20 1 2 3 4 5 … 21 22 23

63s30 1 2 3 4 5 … 21 22 23

74s40 1 2 3 4 5 … 21 22 238••••

The node has n=8 port.
Cycle time Tc is set and time variation TVi,o for port pair (i,o) is known.
Calculate Bi,o = floor(TVi,o / Tc) +4 and Bo is the max(Bi,o) for a port o.
Assume the calculation results of the number of physical buffers Bo oneach port:• B5 = B7 = 6, B6 = B8 = 4• B1 – B4 not shown, assume all are 4• Assume Max # of cycle_id C = 8, cycle_id [0, 7]• i.e. length of cycle_id = 3 bit. (This is for picture simplicity. In reality,it should be larger)• Then N = 24 (the least common multiple of 4,6,8)• Logical buffer selector Si makes value si rotate between 0 – 23.
• Note: It is the index assignment for calculation simplicity. No real
buffer attached.
16

Example Step 2 – initialization of buffer
selector and output buffers
System Clock T
Synchronizedinitialization

1

Logical Buffer
Selector S

PhysicalBuffers
52

63748

• All the ports of a node use the same system time T. T is the time elapsed(in nanosecond) from the latest system startup. All the components inthe node can use T as a time source.
• System Synchronized Initialization:• Initialize the starting time for Si and buf_id on all ports to be
multiple of N*Tc.
• Logically make the position and shifting for all Si the same, thus asingle selector S can be used to simplify the implementation. Let s
be the value of the selector S.
• Facilitate halfway port enabling• Initialize s = 0 and the transmitting buffer id = 0 on all ports• increments (modulo N) each cycle• At any time T, the following computations hold• s = (T mod (N*Tc)) / Tc ---- “/” is floor division• buffer id currently transmitting frames on port o:
Tx-buf-id = s mod Bo• cycle id used by currently transmitting buffer:
Tx-cycle-id = s mod C17

Example Step 3 – Determination of cycle id mapping relation
for port pair (i,o)
Pre-requisite:• Node A & B have run their cycles independently with cycle TcAB

System Clock T

System Clock T
PhysicalBuffers

12

Logical Buffer
Selector SPurpose: For the input and output port pair (i, o) on B, determine mapping
parameter Mi,o so that a stable cycle mapping equation cycle_id_out =(cycle_id_in + Mi,o) mod C can be used for future data frames over port pair (i,o)
no matter what time variation are experienced by that frame.

Computemapping
relation

56

12

Logical Buffer
Selector S

PhysicalBuffers
Worst casecycle_id_out55
Worst casecycle_id_out66
Worst casecycle_id_out7

3478

347
Worst casecycle_id_out88

Mapping determination frame: special frame to determine the cycle mapping
relation between two neighbors during system initialization and auditing. Itexperiences the least time variation• Shortest frame – 64B• Highest priority
Cycle mapping relation computation example:• B receives the mapping determination frame from port 2• Assume B’s system time is T. Compute the potential worst case s for the frame
over each output port o as：
so = ((T + TV2,o) mod (N*Tc)) / Tc
• Compute cycle_id_out for the potential worst case frame over each outputport o as：
cycle_id_outo = (so + 1) mod C• Compute Mi,o = (cycle_id_outo - cycle_id_ini + C) mod C• Assume the frame carries cycle_id_in = 7 from the incoming port 2 andthe computed cycle_id_out is 2 on output port 5, thenM2,5 = (2-7+8) mod 8 = 3• Mi,o can be simplified to Mi for a port i if Mi takes Max(Mi,o) for a specific i.
That will make the # of mapping parameters O(n) instead of O(n2), n=#of ports.
18

Example Step 4 – Data frames: determination ofoutput cycle id and buffer idAB

System Clock T

System Clock TPhysicalBuffers

PhysicalBuffers

Mapping table
12

Logical Buffer
Selector S

Output cycle id:

5162M2,5 = 3frame withcycle_id_out• cycle_id_outo = (cycle_id_ini + Mi,o) mod C• e.g. as M2,5 = 3 for port pair (2,5), the cycle_id determination
is defined as
cycle_id_out = (cycle_id_in + 3) mod 85637374848

Output buffer id:• Cycle id used by currently transmitting buffer:
Tx-cycle-id = s mod C• Compute the id offset between targeting placement buffer
and current transmitting buffer as：
offset = (cycle_id_outo - Tx-cycle-id + C) mod C• Compute the buf_id on port o to place the frame as:buf_ido = (s + offset) mod Bo

19

Summary of calculations – on each node, for eachpriority
Step 1: Base parameter
provisioning
Step 2: Initialization ofbuffer selector andoutput buffers

1.

Set cycle time Tc and time variation TVi,o for port pair (i,o)

2.

Calculate number of physical buffers Bo on each port o as:• Bi,o = floor(TVi,o / Tc) +4• Bo = max(Bi,o) for port o3.

Calculate N = the least common multiple of Bo and C

4.

Start system synchronized initialization on every node for buffer selector S and ports

5.

Use Mapping Determination Frame to calculate the mapping relation value Mi,o for port pair (i,o)
as follows:

Step 3: Determination ofcycle id mapping relation

Step 4: Data framemapping

One-time static
calculation andprovisioning• so = [((T + TVi,o) mod (N*Tc)) / Tc]• cycle_id_outo = (so + 1) mod C• Mi,o = (cycle_id_outo - cycle_id_ini + C) mod C

6.

For an incoming frame for port pair (i,o), calculate the output cycle id cycle_id_outo and output
buffer id buf_ido• output cycle id: cycle_id_outo = (cycle_id_ini + Mio) mod C• output buffer id:•••

for each data frame

Tx-cycle-id = s mod Coffset = (cycle_id_outo - Tx-cycle-id + C) mod C
buf_ido = (s + offset) mod Bo20

Choice of cycle id length• Number of cycle id C = 2L where L is the length in bits of cycle id• C should be larger than the number of physical buffer Bo on any porto in step 1 base parameter provisioning• Discuss: L to be at least 5？
• C = 32 (L = 5)should be sufficiently large as it can support a 32-buffer port.
• If we make L=8, that would allow 256-buffer on any port.

• Preferred way of tagging (back to slide 6-8)?

21

Checksum re-compute
Will Checksum be required to re-compute per hop?
- Yes as the cycle id is changed every hop, but it does not introduce additional
cost.
- Checksum re-compute is always performed in normal forwarding at theintermediate nodes regardless of whether any header value changes.
- Hence no additional checksum re-compute cost caused by cycle id change perhop.
- If VLAN variant tagging is used, it is equivalent to normal VLAN mapping
procedures in switch implementation.

22

Support of multiple time cycles
The slides showed the example for a single priority traffic class which has asingle time cycle. It can also support multiple time cycles if CQF
enhancement mechanisms are enabled on multiple priority traffic classes.

- Use the multiple cycle time picture in new-finn-multiple-CQF-0921-v02 asexample.
Compute the cycle
mapping relations foreach class independently- Each priority traffic class to establish the cycle mapping relations
independently.
23

Computation delay considerations- Most computation is one-time thing at the initialization. Not
contribute to the data plane delay.
- For each data frame, it is simply a mapping from cycle_id_in tocycle_id_out and determination of buffer id using add operations.
- Additional computation delay for each data frame is negligible.

24

Takeaways and Discussions• Cycle id conceptually is an implicit pivot reception time of the frame.
Not impacted by the time variation experienced by the frame.
• It helps to remove the ambiguity of cycle identification and improvethe bandwidth utilizations when software reception time is used.
• The calculations for initialization and mapping relation establishment
are feasible.
• Per-frame data plane computation is simple.
- Good or bad idea for inclusion in Qdv?

25