2 of 19

Background

Problem: Programmer can only tweak scheduler parameters within switch, cannot modify scheduler algorithmic logic

Programmable scheduler that can process at line rate?

3 of 19

Programming Model

Scheduling Transaction
Scheduling Tree
Shaping Transaction

4 of 19

Scheduling transactions

Data structure: PIFO (push-in, first out)

Insert packet into arbitrary position in priority queue
DEQ from head

Transaction is block of code executed on a packet to determine rank within PIFO

“rank” - schedule order, lower is earlier

5 of 19

Example

STFQ (start time fair queueing)

Queues packets based on start time

Start time/rank computation

Start time is the max(previous flow(packet) finish time, current virtual time)

Internal variables on switch

Last_finish, virtual time

6 of 19

Limitation of single PIFO?

7 of 19

Limitation of single PIFO?

Can’t reorder already buffered packets

Scheduling tree

8 of 19

Scheduling tree

Stack PIFOs in tree structure

PIFO entry holds either a packet (at leaf) or a reference to another PIFO (at parents)
Adds indirection on parent nodes, can reorder across PIFO children

ENQ traverse from leaves to root

Scheduling transaction at each node

DEQ traverse from root to leaves

9 of 19

Example

HPFQ (hierarchical packet fair queueing)

Flows are separated into classes (AB/CD) -> (Left, Right)
Adds bandwidth allocation at each node (class)
Needs reordering of already buffered packets to work

10 of 19

Shaping transaction

Non-work conserving schedulers

Programs the time when packets are scheduled

Defers ENQ into parent PIFOs, based on time

Example: rate-limiting

11 of 19

Discussion - Non-work conserving schedulers

Shashank - “I understand how they are implemented in this abstraction, but I am just confused on the advantages and disadvantages compared to a work conserving scheduler.”

Example: Stop-and-Go - frames packets arriving within a time frame, provides “bounded delay” for real-time applications

12 of 19

Some limitations

Can’t reorder multiple packets references with only a single insertion

Ex. pFabric
Would like to order p1(9) and p1(8) in front of p0(7) when p1(6) is inserted
PIFO tree result: p1(9), p0(7), p1(8) , p1(6)

p1(8) not re-ordered

Output rate limiting

Once packet enters parent PIFO, free to transmit at line rate
Shaping transaction only provides input rate limiting

13 of 19

Hardware Design - Mesh of PIFO Blocks

Each PIFO block represents a level in PIFO tree

Multiple logical PIFOs

Atom pipeline

Executes scheduling/shaping transaction

Support 1 ENQ + DEQ into PIFO block per cycle

Operation specifies logical PIFO ID

14 of 19

Hardware Design - PIFO Block

Flow scheduler - support ENQ/DEQ of PIFO block

Internal PIFO consisting only of head elements of flows

Assume packets within flows have increasing ranks

Significantly reduces hardware logic

Rank store - FIFO order of each flow’s packets

Next packet from flow

15 of 19

Hardware Design - Flow Scheduler

2 ENQs + 1 DEQ per cycle

Insert - new flow
Pop - packet is picked

Reinsert - if more packets remaining from existing flow

ENQ compares ranks to determine push position
DEQ compares logical PIFO ID and rank to determine head element

Multiple flows associated with a logical PIFO

16 of 19

Hardware Design - Overhead

5-level PIFO mesh
1 GHz, good enough for 64 x 10Gbps

Limit of 2048 flows to meet timing requirement
4% additional area

17 of 19

Discussion - Flow limitation

Xiao - “While the system scales to 2048 flows, it falls short of fully supporting the 60K flows required for the finest granularity scheduling (such as per-packet scheduling). I wonder whether PIFO can be implemented on programmable switches with line-rate performance.”

18 of 19

Discussion - Usefulness

Asmita - “I wonder if such chips were manufactured, the compiler was written, etc. Also, to what extent is programmable scheduling even needed”

Vinay - “Did network operators provide any insights on if they need to have programmable schedulers and if so, what the design requirements are? As the authors themselves point out, the irony is that pFabric itself could not be implemented in a programmable manner (which is what the authors wanted to do when they started this project)”

19 of 19

Discussion - Formalization

Divya - “One thing I was wondering about was: the authors mentioned that there was no clear check as to whether some algorithm could be implemented using PIFO. I wonder if such a thing has been formalized now.”