Introduction

Dynamic priority is required in network scheduling algorithms.

Current Problems:

1. The switches schedule package is mainly based on coarse-grained queue-level priorities, which is insufficient** to support a broad class of scheduling algorithms that require the importance of packets to change as a function of the time** it has spent inside the network.
2. Switch-level support for multiple fine-grained priority levels can help the realizaitonrealization of the scheduling algorithms. But still has challenges.
   1. implementing strict and fine-grained priority levels is expensive
   2. Switch-level support for priorities does not allow for dynamic changes to the importance of a packet during its stint inside the switch buffer.

Solutions:

Introduce calendar queue abstraction, which is fit for scheduling algorithms that require prioritization and performs dynamic escalation of packet priorities.

Background

Reconfigurable switches

Assume that the programmable scheduling is used in conjunction with a reconfigurable switch. Eg, Reconfigurable Match Table (RMT) model:

1. The package arrives at the switch
2. Header files are extracted via the user-defined programmable parser
3. fields are passed into the pipeline of user-defined programmable M+A stages.
4. Each stage matches a subset of extractedremovedextracted removed headers and performs a simple process on the header.

Switch also provide several hardware features:

​ Stateful memory, computation primitives, the ability to recirculate or generate special datapath packets using timers

Switch metadata:

​ queue lengths, congestion status, and bytes transmttedtransmitted can also be used in packet processing

Traffic Manager

Responsible for two tasks

1. Buffering packets when many input ports agree trying to send packets to the same output port simultaneously

   Each output port has a fixed number er FIFO buffers.

   Once a packet is transmitted from the ingress ingress buffer to the **FIFO queue, it cannot be dropped.

2. Schedule packets at each output port so another server can receive them.

   Since each output port has multiple FIFO buffers, TM uses a combination of factors to determine which queue to dequeue from.

   1. Each queue has a priority
   2. .Within a priority level, lines are scheduled in weighted round-robin-robin order.
   3. Each line can be limited to a maximum rate and can be moved or paused.

TM maintains each queue’s status such that TM can use them to perform buffering and scheduling

.Programmable Scheduling (prior work)

Recent proposals for programmable scheduling propose additional switch hardware in the TM to make the scheduling decision programmable.

PIFOs enable programmable scheduling using a programmable priority queue** to express custom scheduling algorithms. And the rank determines the packet’s order in the priority queue.

Packet Scheduling using Programmable Calendar Queues

Drawbacks of existing priority queue schemes:

Many scheduling algorithms cannot be realized using fine-grained priority queuing schemes methods if the computed rank needs to fall within a finite range. E.g., fair queue or earliest deadline first (EDF)

Programmable Calendar Queues (MCQs)

Calendar Queue abstraction has a fixed number of buckets or FIFO queues, each of which stores packets scheduled for the the ext N periods.

Scheduling algorithms using CQ will do the following:

1. choose a future period from [0, N-1] to enqueue the packet int.
2. pPeriodicallydecideperiodically decide when a period is over and moves on to the next period.
3. When when the CQ advances to the next period, the pipeline state has to be suitably modified to ensure the appropriate computation of ranks for incoming packets.

Interface methods

1. CQ.enqueue(n): Used by the ingress pipeline to schedule the current packet n periods into the future.
2. CQ.dequeue(): Used by the egress pipeline to obtain a buffered packet, if any, for the current period.
3. CQ.rotate(): Used by the pipelineschannels to advance the CQ so that it can start transmitting packets for the next period.

Programmable Scheduling using ng MCQs

various scheduling algorithms can be realized using Calendar Queues in conjunction with a pro- grammable packet processing pipeline.

Weighted Fair Queueing

Earliest Deadline First

Leaky Bucket Filter

Implementing PCQs in Hardware

Calendar Queues can be implemented on programmable switches using mutable switch state, multiple FIFO queues, the ability to create and recirculate packets selectively, and the ability to pause/resume queueslinesqueues lines or alter queue priorities directly in the data plane.

Implementation overview:

Each period in the CQ is mapped to a single FIFO queue within a set of queueslinesqueues lines associated with the outgoing port

.The ingress pipeline computes which pe- riod or queue each incoming packet is enqueued into

The queue corresponding to the current period has the highest priority level, this; this queue is the head queue

.The queue corresponding to the next period has a lower priority level and is active/unpaused.

Implementation details:

1. Initiate Rotation

When: initiate rotation when the head queue is empty.

How: Check the queue id from which the packet was dequeued to infer whether the head queue is empty

1. Drain queue

   when: When a rotation begins, we recirculate a particular rotate packet to the ingress pipeline so that it stops enqueuing packets in the head queue and begins draining it. andAndand it also ensures that the head queue is completely drained, and no more packets are enqueued into it till the rotation finishes.

   How: the ingress enqueues a particular marker packet into the head queue after updating the head of the calendar queue

2. Finish Rotation

   when: marker packet is the last packet to be enqueued into the head queue, and its arrival at the egress pipeline means the queue in queue line is completely drained.

   How :

   1. The marker packet is recirculated back to the ingress pipeline, informing the ingress pipeline that it is safe to reuse the queue for future periods.
   2. The ingress changes the priority of the justemptiedjust emptied queue to the owest and alsopausesalso pauses it, essentially pushing the queue line to the end of the CQ.

Analysis

First, CQs maintain a state at the granularity of physical switch queues instead of individual packets or flows.

At any given point in time, there is a designated head queue that is responsible for providing the packets that are to be transmitted.

The rotation operation involves changing just the metadata of the queue and that of at most three lines. This combination of factors allows us to bolt-onboltonbolt-on bolt on the PCQ abstraction onto a traditional TM.

Extensions

Evaluation

Evaluate the practical feasibility, expressiveness, and per- formanceperformance of Calendar Queues by implementing them on a programmable Barefoot Tofino switch and realizing two clasclass- SoCal classical scheduling algorithms using CQs.

Conclusion

Programmable Calendar Queues enables enable the efficient realization of several classical scheduling algorithms

.It is implemented efficiently on today’s programmable switches by dynamically changing the priority of queues.

PCQsMCQs can realize interesting LSTF, Fair Queueing, and fabric fabric variants to provide stronger delay guarantees, burst-friendly fairness, and starvation-free prioritization of short flows, respectively.

---

• ← Previous Post
• Next Post →