DetNet Shaofu. Peng
Internet-Draft Aihua. Liu
Intended status: Standards Track ZTE
Expires: 11 September 2023 Peng. Liu
China Mobile
Dong. Yang
Beijing Jiaotong University
10 March 2023
Generic Packet Timeslot Scheduling Mechanism
draft-peng-detnet-packet-timeslot-mechanism-01
Abstract
IP/MPLS networks use packet switching (with the feature store-and-
forward) and are based on statistical multiplexing. S tatistical
multiplexing is essentially a variant of time division multiplexing,
which refers to the asynchronous and dynamic allocation of link
timeslot resources. In this case, the service flow does not occupy a
fixed timeslot, and the length of the timeslot is not fixed, but
depends on the size of the packet. Statistical multiplexing has
certain challenges and complexity in meeting deterministic QoS, and
its delay performance is closely related to the used queueing
mechanism. This document further describes a generic time division
multiplexing scheme in IP/MPLS networks, which we call packet
timeslot scheme. It aims to make the control plane easier to
calculate the delay performance and more flexible to allocate
deterministic resources, and make the data plane create more flexible
timeslot mapping.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 11 September 2023.
Peng, et al. Expires 11 September 2023 [Page 1]
Internet-Draft Packet Generic Timeslot March 2023
Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1. Path Calculation and Timeslot Resource Reservation . . . 7
3.2. Timeslot Resource Access . . . . . . . . . . . . . . . . 8
4. Relationship between Residency Delay and Timeslot Mapping . . 8
5. Global Timeslot ID . . . . . . . . . . . . . . . . . . . . . 10
5.1. Fixed Timeslot Mapping . . . . . . . . . . . . . . . . . 10
5.2. Unfixed Timeslot Mapping . . . . . . . . . . . . . . . . 13
6. Queue Design . . . . . . . . . . . . . . . . . . . . . . . . 14
6.1. Full Queues . . . . . . . . . . . . . . . . . . . . . . . 15
6.2. Non-full Queues . . . . . . . . . . . . . . . . . . . . . 15
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15
8. Security Considerations . . . . . . . . . . . . . . . . . . . 16
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 16
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.1. Normative References . . . . . . . . . . . . . . . . . . 16
10.2. Informative References . . . . . . . . . . . . . . . . . 16
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16
1. Introduction
IP/MPLS networks use packet switching (with the feature store-and-
forward) and are based on statistical multiplexing. The discussion
of supporting multiplexing in the network was first seen in the time
division multiplexing (TDM), frequency division multiplexing (FDM)
and other technologies of telephone communication network (using
circuit switching). Statistical multiplexing is essentially a
variant of time division multiplexing, which refers to the
asynchronous and dynamic allocation of link resources. In this case,
the service flow does not occupy a fixed timeslot, and the length of
the timeslot is not fixed, but depends on the size of the packet. In
Peng, et al. Expires 11 September 2023 [Page 2]
Internet-Draft Packet Generic Timeslot March 2023
contrast, synchronous time division multiplexing means that a
sampling frame (or termed as time frame) includes a fixed number of
fixed length timeslots, and the timeslot at a specific position is
allocated to a specific service. The utilization rate of link
resources in statistical multiplexing is higher than that in
synchronous time division multiplexing. However, if we want to
provide deterministic end-to-end delay in packet switching networks
based on statistical multiplexing, the difficulty is greater than
that in synchronous time division multiplexing. The main challenge
is to obtain a certain queuing delay, which is closely related to the
queuing mechanism used in the network.
In addition to IP/MPLS network, other packet switching network
technologies, such as ATM, also discuss how to provide corresponding
transmission quality guarantee for different service types. Before
service communication, ATM needs to establish a connection to reserve
virtual path/channel resources, and use fixed-length short cellS and
timeslots. The advantage of short cellS is small interference delay,
but the disadvantage is low encoding efficiency. The mapping
relationship between ATM cells and timeslots is not fixed, so it
still depends on a specific cellS scheduling mechanism (such as
[ATM-LATENCY]) to ensure delay performance. Although the calculation
of delay performance based on short and fixed-length cells is more
concise than that of IP/MPLS networks based on non-fixed-length
packets, they all essentially depend on the queue mechanism.
[CQF] introduce a hybrid of asynchronous and synchronous time-
division multiplexing method based on fixed-length cycle in Ethernet
LAN. [Multi-CQF] is a further enhancement of the classic CQF to be
applicable to IP/MPLS networks. Generally, the service flow is not
mapped to a fixed cycle at the network entrance, but dynamically
selects an idle cycle, which can be regarded as asynchronous, but the
intermediate node is based on a fixed and inherent cycle mapping,
which can be regarded as synchronous. CQF with 2-buffer mode or
Mult-CQF with 3-buffer mode only uses a small number of cycles to
establish the inherent cycle mapping between a port-pair of two
adjacent nodes, which can minimize the residence delay in the node
and ensure end-to-end jitter at the same time. The inherent cycle
mapping is independent of the service and is also irrelevant to the
resource reservation of the service. That is, the cycle of CQF/Mult-
CQF is not a resource that is open to the service and can be
reserved. [Multi-CQF] describes the deterministic behavior for each
cycle-level based on traditional bandwidth resource allocation, with
cycle-based admission control. However, overprovisioning (i.e.,
burst / cycle is larger than service bandwidth) may affect the
service scale that can support. Alternatively, other literatures
have also been discussing the cycle-based resource allocation, which
mainly affects the sending cycle selected for the service flow on the
Peng, et al. Expires 11 September 2023 [Page 3]
Internet-Draft Packet Generic Timeslot March 2023
entry node, but does not change the inherent cycle mapping in the
network. The path composed of inherent cycle mapping relationship is
like a highway without traffic lights along the way. Traffic control
can only be implemented at the entrance of the path, so it may be
possible to avoid car conflict of multiple paths at the intermediate
nodes, but not always likely. In addition, since the number of
cycles used by CQF/Multi-CQF is small, such as 3 or 4, it is not easy
to determine whether the cycle conflict of service flows on multiple
paths is true or false conflict.
In order to improve the service scale supported by the network, this
document further discusses a generic time division multiplexing
scheduling mechanism using timeslot resource in IP/MPLS networks,
which we call packet timeslot scheduling mechanism. The timeslot
resource is the enhancement of bandwidth resource, has the feature of
time awareness, is visible and assignable to the service. From the
perspective of data plane, the timeslot resource is a time interval
that can continuously send packets, while from the control plane, it
is the amount of bits in the time interval (e.g, the total amount of
bits that can be reservable, and the amount of unreserved bits).
Based on the timeslot resources, the control plane is easier to
reserve strictly non-conflicting resources for different paths that
can get deterministic delay performance, and the data plane can
create more flexible (i.e., not inherent, but based on reservation)
timeslot mapping to avoid conflicts.
2. Terminology
The following terminology is introduced in this document:
Timeslot: The smallest unit of packet timeslot scheduling. It needs
to design a reasonable value, such as 10us, to send at least one
complete packet.
Timeslot Scheduling: The packet is stored in the buffer
corresponding to a specific timeslot, then sent in that timeslot.
Incoming Timeslot: For an intermediate node in a specific path, the
timeslot contained in the packet received from the upstream node
(i.e., the outgoing timeslot of the upstream node) is its
incoming timeslot.
Outgoing Timeslot: For an intermediate node in a specific path, when
it continues to send packets received from the upstream node to
downstream nodes, according to resource reservation or certain
rules, it chooses to send packets in the specified timeslot,
which is the outgoing timeslot.
Peng, et al. Expires 11 September 2023 [Page 4]
Internet-Draft Packet Generic Timeslot March 2023
Ongoing Sending Timeslot: For an intermediate node in a specific
path, it continues to send packet received from the upstream node
to the downstream node. When the packet arrives at the outgoing
port, the timeslot at which the outgoing port is currently in the
sending state is the ongoing sending timeslot. Note that the
ongoing sending timeslot is not the outgoing timeslot.
Scheduling Period: The period of the packet timeslot scheduling
mechanism implemented by the network node, including a fixed
number of timeslots, for example, the scheduling period is fixed
to include 100 timeslots.
Ongoing Sending Period: The scheduling period which the ongoing
sending timeslot belongs to.
Service Burst Interval: The traffic specification of deterministic
services generally follows the principle of generating a specific
burst amounts within a specific length of cyclic burst interval.
For example, a service generates 1000 bits of burst per 1 ms,
where 1 ms is the service burs interval.
Orchestration Period: The orchestration Period is adopted by the
control plane according to the needs of all deterministic
services. The timeslot resources within the orchestration period
can be allocated for services, i.e., which timeslots are occupied
by services and how many bits are occupied in timeslots. The
orchestration period is the Least Common Multiple of all service
burst intervals. It is also a multiple of the scheduling period.
3. Overview
This scheme introduces the time-division multiplexing scheduling
mechanism based on the fixed length timeslot in the IP/MPLS network.
Note that the time-division multiplexing here is a L3 packet-level
scheduling mechanism, rather than the TDM port (such as SONET/SDH)
implemented in L1. The latter generally involves the time frame and
the corresponding framing specification, which is not necessary in
this document.
As shown in Figure 1, the packet timeslot scheduling behavior
implemented by the intermediate node P passing through multiple
deterministic paths on the outgoing port (P-PE2).
Peng, et al. Expires 11 September 2023 [Page 5]
Internet-Draft Packet Generic Timeslot March 2023
+---+ +---+ +---+
|PE1| --------------- | P | --------------- |PE2|
+---+ +---+ +---+
Orchestration Period
+-+-+-+-+-+-+-+-+-+-+
|0|1|2|3| ... ... |N|
+-+-+-+-+-+-+-+-+-+-+
^ ^
reserve slots: | | reserve slots:
a,b,c | | x,y
path-1 -------------------------o--|---------------->
path-2 -------------------------|--o---------------->
| |
access slots: | | access slots:
a',b',c' v v x',y'
/ +-------------------+ ___
| | queue-0 @slot-0 | / \
| +-------------------+ | |
| | queue-1 @slot-1 | | |
Scheduling < +-------------------+ |
Period | | ... ... | | ^
| +-------------------+ | |
| | queue-n @slot-n | \___/
\ +-------------------+
Figure 1
Where, both the orchestration period and the scheduling period
consist of multiple timeslots, the total amount of bits that can be
reservable or sent in each timeslot can be set, generally not
exceeding the product of the total bandwidth of the link multiplied
by the timeslot length. The scheduling period of all nodes in the
network does not need to be synchronized, and phase difference is
allowed.
In the figure, path-1 and path-2 allocate timeslot resource from the
orchestration period of link P-PE2 respectively. Path-1 reserves
timeslot a, b, c from orchestration period, and finally accesses
timeslot a', b', c' from scheduling period. Path-2 reserves timeslot
x, y from orchestration period, and finally accesses timeslot x', y'
from scheduling period. There is a mapping relationship function
between the timeslot i of orchestration period and the timeslot i' of
scheduling period, i.e., i' = f(i). There are many mapping options,
such as a'=a, a'=a+offset, a'=a%(n+1), and a'=random(a), etc.
Peng, et al. Expires 11 September 2023 [Page 6]
Internet-Draft Packet Generic Timeslot March 2023
In the current version, we mainly discuss the case that the length of
the scheduling period is the same as that of the orchestration
period. For the case that the orchestration period is longer than
the scheduling period, it will be discussed in later versions.
The scheme involves two aspects: the path calculation and timeslot
resource reservation in the control plane, and timeslot resource
access in the data plane.
3.1. Path Calculation and Timeslot Resource Reservation
The control plane (centralized controller or distributed protocol)
can reserve corresponding timeslot resources along the deterministic
path. Note that a path may carry multiple services, then the path
will reserve timeslot resources for the combined services, and may
reserve the bit resources in multiple timeslots at the same time in
the orchestration period.
During resource reservation, it is necessary to distinguish the
requirements between low latency service and non-low latency service
. For low latency service requirements, the physical offset between
the reserved outgoing timeslot and the incoming timeslot is small;
while for non-low latency service requirements, this physical offset
can be large.
The timeslot resource reservation of multiple path will generate
multiple incoming/outgoing timeslot mapping relationships on node P.
In particular, for two mapping relationships, they have the same
incoming timeslot, but may map to different outgoing timeslots. For
example:
The timeslot mapping relationship created by the path-1:
<(incoming port a, incoming slot number 3), (outgoing port b,
outgoing slot number 60)>
The timeslot mapping relationship created by the path-2:
<(incoming port a, incoming slot number 3), (outgoing port b,
outgoing slot number 61)>
Special care should be taken not to confuse the use of different
mapping relationships. For specific service flows, P need to
explicitly use specific timeslot mapping relationships.
It is recommended to reserve timeslot resources on the outgoing port
of each hop from the headend of the path to the endpoint, that is,
first determine the timeslot reserved for the first hop, then
Peng, et al. Expires 11 September 2023 [Page 7]
Internet-Draft Packet Generic Timeslot March 2023
determine the timeslot reserved for the second hop based on the
result of the first hop, and so on. This is because the timeslot
first selected on the headend is important to the service flow. We
assume that the service flow has a periodic arrival time, and there
is a fixed position relationship between the arrival time and the
orchestration period of the first hop's outgoing port, so selecting
the timeslot close to the arrival time or within the expected offset
range in the orchestration period can minimize the residency delay of
the packet, or make it within the expected range, on the headend.
3.2. Timeslot Resource Access
The entry node of the path needs to maintain the timeslot resource
information with the granularity of service/aggregate service, so
that the service flow can access its timeslot resources. However,
the intermediate node does not need to maintain this state.
The entry node determines the appropriate outgoing timeslot and sends
the packet according to the maintained mapping relationship between
the service and the outgoing timeslot, and the periodic arrival time
of the service flow.
The relationship between the incoming timeslot and the outgoing
timeslot can be installed on the intermediate node or carried in the
packet, so that the packet can access the corresponding outgoing
timeslot on the intermediate node.
It should be noted that the forwarding outgoing port for the service
flow is still determined according to the traditional routing
entries, but the outgoing timeslot used by the packet is also
determined according to the timeslot resource reservation
information.
4. Relationship between Residency Delay and Timeslot Mapping
Suppose a path contains three nodes P1, P2, and P3 in turn along the
forwarding direction, with a timeslot length of K, and a single
orchestration period contains M timeslots.
In order to facilitate the allocation of timeslot resources, it is
necessary to know the phase difference between timeslots between two
adjacent nodes. Consider that P1 sends a detection packet from the
end (or head, the process is similar) of a timeslot i on the outgoing
port (link P1-P2) to P2. After a certain link propagation delay
(D_propagation), the packet is received by the incoming port of P2,
and i is regarded as the incoming timeslot by P2. The packet finally
arrives at the outgoing port (link P2-P3) after the intra-node
forwarding delay (D_forwarding) including parsing, table lookup,
Peng, et al. Expires 11 September 2023 [Page 8]
Internet-Draft Packet Generic Timeslot March 2023
internal fabric exchange, etc. At this time, the current ongoing
sending timeslot is j, and there is time T_12 left before the end of
the timeslot j. This at least means that the packet must not access
slot j when it continues to forward to node P3. Based on the above
information, the resource reservation should select the outgoing
timeslot after j for the incoming timeslot i, such as j+1, j+2, etc,
depending on whether they have free resources.
Assuming that the outgoing timeslot selected by node P2 for incoming
timeslot i is j+x, the residency delay of node P2 can be evaluated as
follows:
Best residency-delay = D_ forwarding + T_12 + (x-1)*K
Worst residency-delay = D_ forwarding + T_12 + (x+1)*K
The best residency delay occurs when the packet is received at the
end of incoming timeslot i and sent at the head of outgoing slot j+x;
The worst residency delay occurs when the packet is received at the
head of incoming timeslot i and sent at the end of outgoing timeslot
j+x. The delay jitter within the node is 2*K. However, it does not
accumulate with the number of hops, that is, the end-to-end delay
jitter is also 2*K.
As shown in Figure 2, a path from headend H to endpoint E passes
through n intermediate nodes (M1, M2, ..., Mn). Suppose that for
each intermediate node Mi, the intra-node forwarding delay is F_i,
the remaining time from the end of the mapped ongoing sending
timeslot is T_i, the number of timeslots offset by outgoing timeslot
relative to ongoing sending timeslot is X_i, then the end to end
delay can be evaluted as follows:
Best e2e-delay = sum(F_i + T_i + X_i*K) - K, 1<=i<=n
Worst e2e-delay = sum(F_i + T_i + X_i*K) + K, 1<=i<=n
+---+ +---+ +---+ +---+ +---+
| H | --- | M1| --- | M2| --- ... --- | Mn| --- | E |
+---+ +---+ +---+ +---+ +---+
Figure 2
Peng, et al. Expires 11 September 2023 [Page 9]
Internet-Draft Packet Generic Timeslot March 2023
It can be seen that in order to determine which outgoing timeslot is
reserved, it is necessary to first determine the ongoing sending
timeslot that the incoming timeslot falls into. Assume that
according to the actual detection, P2 obtains the mapping between the
incoming timeslot i and the ongoing sending timeslot j, then we can
get the ongoing sending timeslot b that any incoming timeslot a falls
into.
b = |j+a-i|%M
5. Global Timeslot ID
The outgoing timeslots we discussed in the previous sections are all
local timeslots for nodes. This section discusses the situation
based on global timeslot.
Global timeslot refers to that all nodes in the path are identified
with the same timeslot number. The advantages are that the resource
reservation based on global timeslots is simple. There is no need to
establish a local timeslot mapping relationship on each node or in
packets. The packet only needs to carry the unique global timeslot
number. However, the disadvantage is that the latency performance of
the path is not controlled, which depends on the phase difference
between the inherent scheduling periods between the adjacent nodes.
5.1. Fixed Timeslot Mapping
So far, the packet timeslot scheduling scheme presented above is to
reserve a fixed outgoing timeslot for services in the orchestration
period, even if global slot-id is used.
As the example shown in Figure 3, each scheduling period contains 6
timeslots. Node V has three connected upstream nodes U1, U2, and U3.
During each hop forwarding, the packet accesses the outgoing timeslot
corresponding to the global slot-id and forwards to the downstream
node with the global slot-id unchanged. For example, U1 sends some
packets with global slot-id 0, termed as g0, in the outgoing timeslot
0. The packets with other global slot-id 1~5 are similarly termed as
g1~g5 respectively. The figure shows the scheduling results of these
6 batches of packets sent by upstream nodes when node V continues to
send them.
Peng, et al. Expires 11 September 2023 [Page 10]
Internet-Draft Packet Generic Timeslot March 2023
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
U1 | g0| g1| g2| | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
1 2 3 4 5 0 1 2 3 4 5 0 1 2 3
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
U2 | | | g3| g4| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
5 0 1 2 3 4 5 0 1 2 3 4 5 0 1
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
U3 | g5| | | | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
V | | | | g3| g4| g5| g0| g1| g2| | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Figure 3
In this example, the mapping relationship of the outgoing timeslot
from U1 and the ongoing sending timeslot of V is i -> i, so the
reserved outgoing timeslot for the incoming timeslot i is i+6. The
mapping relationship of the outgoing timeslot from U2 and the ongoing
sending timeslot of V is i -> i-1, so the reserved outgoing timeslot
for the incoming timeslot i is i. And, the mapping relationship of
the outgoing timeslot from U3 and the ongoing sending timeslot of V
is i -> i+1, so the reserved outgoing timeslot for the incoming
timeslot i is i+6-1.
The residence delay per hop depends on the phase difference of the
scheduling period between upstream node (U) and this node (V), i.e.,
the difference between the scheduling period of the upstream node (U)
and the ongoing sending period of this node (V).
Let P_uv be the phase difference of the scheduling period between
upstream node (U) and this node (V), we can compute T_uv as follows:
P_uv = T_uv + (i-j)*length(timeslot), where i is the incoming
tiemslot id, j is the ongoing sending timeslot id, T_uv the
remaining time from the end of timeslot j.
Peng, et al. Expires 11 September 2023 [Page 11]
Internet-Draft Packet Generic Timeslot March 2023
If P_uv < length(timeslot), P_uv = P_uv + length(scheduling
period) - length(timeslot)
Else, P_uv = P_uv - length(timeslot)
For example, the packets g3 sent by upstream node U2 falls into the
ongoing sending timeslot 2 of node V, it can be sent in outgoing
global timeslot 3. In this case, the residency delay in the node V
is small. While, the packets g5 sent by upstream node U3 falls into
the ongoing sending timeslot 0 of node V, so it needs to wait for
timeslot 0, 1, 2, 3, 4 to be sent in global outgoing timeslot 5. In
this case, the residency delay in the node V is large.
For example, the packets g0 sent by upstream node U1 fall into the
ongoing sending timeslot 0 of node V, the packets need to wait for
the end of the ongoing sending period to be sent in the global
outgoing timeslot 0 in the next round of scheduling period, which
will introduce a large node residency delay. It should be noted that
in this case, the packets g0, when they fall into the ongoing sending
timeslot 0, cannot be placed in the buffer corresponding to timeslot
0. Instead, it needs to be stored in a buffer prior to the packet
timeslot scheduler (such as the buffer on the input port side) for a
fixed latency (such as a fixed timeslot) and then released to the
timeslot scheduler. This fixed-latency buffer is only created for
specific upstream nodes. It can be determined according to the
initial detection result of the mapping relationship between the
outgoing timeslot of the upstream node and the ongoing sending
timeslot of this node. If the initial detection result is slot-id i
-> slot-id i, it needs to be introduced, otherwise it is unnecessary.
After the introduction of fixed-latency buffer, the new detection
result will no longer be i -> i.
Generally, the residency delay of node V can be evaluated as follows:
Best residency-delay = D_ forwarding + P_uv
Worst residency-delay = D_ forwarding + P_uv + 2*K
The best residency delay occurs when the packet with global slot-id i
is received at the end of global incoming timeslot and sent at the
head of global outgoing timeslot i; The worst residency delay occurs
when the packet is received at the head of global incoming timeslot
and sent at the end of global outgoing timeslot i. The delay jitter
within the node is 2*K. However, it does not accumulate with the
number of hops, that is, the end-to-end delay jitter is also 2*K.
Peng, et al. Expires 11 September 2023 [Page 12]
Internet-Draft Packet Generic Timeslot March 2023
As shown in Figure 2, a path from headend H to endpoint E passes
through n intermediate nodes (M1, M2, ..., Mn). Suppose that for
each intermediate node Mi, the intra-node forwarding delay is F_i,
the phase difference of the scheduling period between upstream node
and this node is P_uv_i, then the end to end delay can be evaluted as
follows:
Best e2e-delay = sum(F_i + p_uv_i + K) - K, 1<=i<=n
Worst e2e-delay = sum(F_i + p_uv_i + K) + K, 1<=i<=n
5.2. Unfixed Timeslot Mapping
Unfixed timeslot mapping is similar to cell scheduling in ATM.
During each hop forwarding, the packets dynamically maps to an idle
local outgoing timeslot according to the global slot-id, according to
the principle of minimum offset (or expected offset range) between
the global slot-id and local slot-id, but the sending packets still
carry the global slot-id without changed. In this case, the delay
performance is related to the mapping algorithm (i.e., the scheduling
algorithm) adopted. The suggested scheduling algorithm will be
discussed in later versions.
As the example shown in Figure 4, each scheduling period contains 6
timeslots. Node V has three connected upstream nodes U1, U2, and U3.
Node U1 dynamically maps the packets with global slot-id 0,1,2 to the
outgoing timeslot 3,4,5 respectively, node U2 dynamically maps the
packets with global slot-id 3,4,5 to the outgoing timeslot 4,5,0
respectively, and node V dynamically map the packets with global
slot-id 0~5 to the outgoing timeslot 4,5,1,0,2,3 respectively.
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
U1 | | | | g0| g1| g2| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
U2 | | | | | g3| g4| g5| | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
V | | | | | g0| g1| g3| g2| g4| g5| | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Peng, et al. Expires 11 September 2023 [Page 13]
Internet-Draft Packet Generic Timeslot March 2023
Figure 4
Because the service flow arrived at the network entry node is
periodic, each entry node should maintain state about a fixed mapping
relationship between global slot-id and the actual outgoing slot-id
for each flow, so that it is more likely that a fixed runtime mapping
relationship will appear on each intermediate node to avoid jitter.
However, the characteristics of unfixed timeslot mapping determine
that this fixed runtime mapping relationship is not always
guaranteed. For example, with the addition or deletion of service,
the mapping status of global slot-id to the actual outgoing slot-id
may have to be updated on the entry node, which will correspondingly
lead to changes in the runtime mapping relationship on the
intermediate node.
The main purpose of global slot-id is used in the timeslots resource
allocation. Within the resource planning of the controller, the
timeslot resources identified by each global slot-id are allocated
for multiple limited service flows without conflict. Intuitively, if
all service flows access the outgoing timeslot according to the fixed
timeslot mapping mode, there is no timeslot conflict, that is, the
total timeslot resources can meet all limited service requirements;
Unfixed timeslot mapping mode is to dynamically access the nearby
idle outgoing timeslots without introducing timeslot conflicts, and
it will not lead to the result that the total timeslot resources are
not enough. How to predict whether the nearest outgoing timeslot is
idle is the focus of the selected scheduling algorithm.
Assume that the packets with global slot-id i accessing the outgoing
timeslot j nearby do not make no resources available when the packets
with global slot-id j arrive now or soon, the delay performance of
unfixed timeslot mapping mode is better than synchronous packet
timeslot scheduling.
Best residency-delay = D_ forwarding + t_uv
Worst residency-delay = D_ forwarding + t_uv + 2*K
where, t_uv <= T_uv
6. Queue Design
The number of tiemslot queues should be designed according to the
number of timeslots included in the scheduling period. Each timeslot
corresponds to a separate queue (or queue group), in which the
buffered packets must be able to be sent within a timeslot.
Peng, et al. Expires 11 September 2023 [Page 14]
Internet-Draft Packet Generic Timeslot March 2023
The length of the queue, i.e., the total number of bits that can be
reserved or sent for a timeslot, does not have to be set to be
exactly equal to the link rate multiplied by the timeslot. This is
because the bandwidth requirements of other non-deterministic
services and protocols running in the network should also be
considered.
6.1. Full Queues
When the scheduling period length is equal to the orchestration
period length, the node will implement full queues. The advantage is
that the actual forwarding resources are the same view as the
resources used for reservation, so that the resource reservation
process is simple. However, the disadvantage is that because the
scheduling period is generally large to cover all services
requirements, the number of queues maintained by the node will be
large.
For example, if the accumulated length of all queues supported by the
hardware is 4G bytes, the queue length corresponding to a timeslot of
10us at a port rate of 100G bps is 1M bits, then a maximum of 32K
timeslot queues can be provided, and the maximum length of the
orchestration period supported is 320ms. However, considering the
queue resource requirements of other non-deterministic services, the
packet timeslot function can only use some of the queue resources,
such as 10K~20K queues. In this case, the length of the
orchestration period supported by the node is 100~200 ms.
6.2. Non-full Queues
When the length of the scheduling period is less than the length of
the orchestration period, the node will implement a non-full queues.
The advantages and disadvantages are opposite to the full queues
option. The actual forwarding resources are inconsistent with the
view of the resources reservation, so that the resource reservation
process is complex. But the number of queues maintained by the node
is small.
More discussion on non-full queue option will be provided in later
versions.
7. IANA Considerations
TBD.
Peng, et al. Expires 11 September 2023 [Page 15]
Internet-Draft Packet Generic Timeslot March 2023
8. Security Considerations
TBD.
9. Acknowledgements
TBD.
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
10.2. Informative References
[ATM-LATENCY]
"Bounded Latency Scheduling Scheme for ATM Cells", 1999,
<https://ieeexplore.ieee.org/document/780828/>.
[CQF] "Cyclic Queuing and Forwarding", 2017,
<https://ieeexplore.ieee.org/document/7961303>.
[Multi-CQF]
"Multiple Cyclic Queuing and Forwarding", 2021,
<https://www.ieee802.org/1/files/public/docs2021/new-finn-
multiple-CQF-0921-v02.pdf>.
Authors' Addresses
Shaofu Peng
ZTE
China
Email: peng.shaofu@zte.com.cn
Aihua Liu
ZTE
China
Email: liu.aihua@zte.com.cn
Peng, et al. Expires 11 September 2023 [Page 16]
Internet-Draft Packet Generic Timeslot March 2023
Peng Liu
China Mobile
China
Email: liupengyjy@chinamobile.com
Dong Yang
Beijing Jiaotong University
China
Email: dyang@bjtu.edu.cn
Peng, et al. Expires 11 September 2023 [Page 17]