Introduction
Background and motivation
Programmable scheduler
PIFO
PIEO
AIFO
Time-sensitive scheduling model
TS and non-TS flows
Time gating mechanism
TAS
CQF
Motivating example
Design
Design insights
-
The transmission order of TS packets on a switch may not be identical to their arrival order. Since we aim to use a single FIFO to schedule TS packets, TS packets in the queue should be arranged in strict ascending order of their transmission time. It is different from AIFO because the packets in the queue of AIFO are not necessarily arranged in strict rank order (see Fig. 3 in [15] for details). However, the arrival order of TS packets may not be the transmission order. We call it disordered problem. The disordered problem of TS packets needs to be solved when using a single FIFO. TS packets need to be cached when disordered packets exist.
-
Non-TS packets must not interfere with the scheduling of TS packets. Non-TS packets share the same FIFO queue with TS packets, and there is no physical isolation between them. We call it shared queue problem. If a non-TS packet is admitted into the FIFO queue unreasonably, it may hinder the scheduling of subsequent TS packets. To maintain the correctness of TS scheduling, non-TS packets need to be aggressively dropped when there is only a single FIFO.
Programming framework
FIFO
Ingress Admission (IA)
LstPktTime
and NxtTSIdx
, and two tables, Index Table (abbreviated as IdxTbl) and Sequence Table (abbreviated as SeqTbl). For the disordered problem, IA uses NxtTSIdx
, IdxTbl and SeqTbl to obtain the eligible time of TS packets within the time complexity of O(1)
. Besides, IA uses a few registers for TS packets’ reordering. For the shared queue problem, IA uses LstPktTime
to track the transmission time of the last packet in the FIFO queue and NxtTSIdx
to track the next TS packet to be enqueued.Egress Admission (EA)
Packet attributes
-
type: This attribute indicates whether the packet is a TS or non-TS packet. Packet scheduling algorithms treat the two types of packets differently.
-
\(flow\_id\): This attribute indicates to which flow the packet belongs.
-
\(period\_id\): This attribute indicates that the packet is the \(period\_id\)-th packet of a flow during the hyper period. The hyper period is the least common multiple of all flow periods. The transmission timetable for TS packets repeats over during the hyper period. In practice, such attributes can be tagged on the sender side and thus can be obtained when the packet arrives.
-
\(eligible\_time\)(\(t_{elig}\)): This attribute indicates when the packets are eligible to be transmitted. Once that time is reached, the packet should be sent immediately. Note that the network-wide global synchronization clock is used as the wall clock. The \(t_{elig}\) of TS and non-TS packets are calculated differently. The \(t_{elig}\) of TS packets is pre-calculated and static, while the \(t_{elig}\) of non-TS packets needs to be calculated dynamically based on the pre-planned \(t_{elig}\) of TS packets.
-
rank: This attribute indicates the priority of a packet and is identical to rank in AIFO. The rank of packets is considered the same in the TSN scheduling algorithm. This attribute enables AIAO to express other non-TSN scheduling algorithms.
Queue primitives
Primitive | Function |
---|---|
enqueue(pkt) | inserts a packet or a sequence of packets into the end of the FIFO queue |
dequeue() | takes a packet from the head of the FIFO queue |
drop(pkt) | discards a packet, preventing it from entering the FIFO queue |
store(pkt) | puts a TS packet into a register and returns the register’s address |
retrieve(addr) | retrieves a TS packet from the register indicated by its address addr |
Programming functions
-
getEligibleTime function: This function takes the packet of a flow to be enqueued as an argument and assigns a possible eligible time for that packet as dictated by the scheduling algorithm being programmed. The eligible time of a TS packet is calculated in advance. The eligible time of a non-TS packet is determined dynamically based on the eligible time of the last packet in the FIFO queue and the eligible time of the next TS packet to be enqueued. Two tables, IdxTbl and SeqTbl, are used to record the eligible time of TS packets.
LstPktTime
state variable is used to track the eligible time of the last packet in the FIFO queue, andNxtTSIdx
state variable is used to track the index of the next TS packet that is to be enqueued. This index is used to look up the eligible time of this packet in the SeqTbl. -
getRank function: This function takes the packet of a flow to be enqueued as an argument and assigns rank to the packets as dictated by the scheduling algorithm being programmed.
-
isAdmitted function: This function takes a packet of a flow as an argument and determines whether the packet can be admitted to the queue based on the rank or \(t_{elig}\) of the packet. The function has three types of return results, ADMIT, STORE and DROP. DROP means a packet cannot enter the FIFO. ADMIT means a packet immediately enters the FIFO. STORE means a TS packet is temporarily stored in a register. When AIAO is programmed to support TSN, \(t_{elig}\) is usually used to determine whether to be admitted. When AIAO is used to program non-TSN algorithms, the rank is often used to determine whether to be admitted.
Expressiveness
O(1)
(Line 3), and SeqTbl is used to obtain the \(t_{elig}\) of the packet within the time complexity of O(1)
(Line 4).LstPktTime
state variable. Thus the \(t_{elig}\) of a BE packet is identical to LstPktTime
(Line 6).NxtTSIdx
state variable (Line 15), it means this packet is not the packet being waited for, but the packet was sent after the packet was waited for, which is the disordered problem. Thus the current packet enters the register, and the address of this register is returned (Line 16). The returned address needs to be updated in the address field of the corresponding table entry in SeqTbl (Line 17). The packet is temporarily stored in the register. Thus STORE is returned (Line 18). If the current packet is the TS packet being waited for (Line 19), there is no disordered problem. The tables and state variables need to be updated (Line 20). First, the address field of the packet in SeqTbl is reset to null to indicate that the packet does not need to be buffered. Second, the TS packet is now the last packet in the FIFO queue and then the \(t_{elig}\) of this packet is updated to LstPktTime
. Third, NxtTSIdx
should be updated to the current index+1 (Line 14). If the packets corresponding to the new NxtTSIdx
have arrived in advance, the packets are taken out from their register, and the update operation is repeated (Lines 16-18). All the TS packets are admitted into the FIFO queue, and ADMIT is returned (Line 26).LstPktTime
plus its transmission delay does not exceed the \(t_{elig}\) of the next TS packet, and there are no TS packets in the registers (Line 30), it means that this BE packet will not interfere with the scheduling of the next TS packet, then the BE packet is admitted into the FIFO queue (Line 31). Otherwise, the BE packet is dropped (Line 33).O(1)
directly(Line 3). Note that the \(t_{elig}\) of multiple TS packets sent in the same time slot is when the time slot starts. The \(t_{elig}\) of multiple TS packets is identical. This does not affect the egress scheduling of the FIFO queue. A non-TS packet’s \(t_{elig}\) is tracked by LstPktTime
(Line 5). Similarly, the rank of packets in CQF is identical and thus is set to be 0 (Line 9).LstPktTime
should add the transmission delay of the TS packet(Line 13).NxtTSIdx
(Line 21). Note that NxtTSIdx
in CQF has a different meaning in TAS. If the LstPktTime
plus the transmission delay of this non-TS packet does not exceed NxtTSIdx
, the non-TS packet is admitted (Line 18). Otherwise, it is dropped (Line 20). Besides, NxtTSIdx
needs to be updated to the moment when the transmission of the packet ends (Line 17). Note that for each increase in the length of the slot in the global clock, NxtTSIdx
automatically adds 1.Implementation
NxtTSIdx
is matched against the SeqTbl to get the eligible time for the next TS packet that is expected to enqueue. The Rank Selector is the key scheduling module in the ingress stage. It reads the register LstPktTime
, which indicates when the last packet in the FIFO queue is expected to finish the dequeue operation. Then it calculates if the arriving packet should enqueue by comparing the eligible time of the next TS packet and the expected dequeue time of the current non-TS packet (④). Next, the Rank Selector grants the next packet based on the result and issues the enqueue operation. Finally, both NxtTSIdx
and LstPktTime
are updated accordingly. In the last step(⑤), Transmission Module issues a dequeue operation when the current time exceeds the eligible time of the packet on the head of the queue.Preliminary results
Hardware Implementation | Slice LUTs | Block RAMs |
---|---|---|
Standard CQF | 25536 (48.00%) | 82.50 (58.93%) |
AIAO-based CQF | 26419 (49.66%) | 71.05 (50.75%) |