DeficitRoundRobinRouterBackplane
status
Regression test
Contacting Group
Fair queuing is a technique that allows each flow passing through a network device to have fair share of network resources. Previous schemes for fair queuing that achieved nearly perfect fairness were expensive to implement; specifically, the complexity to process a packet in these schemes was O(log n) , where n is the number of active flows. This is expensive at high speeds.The design is effective in reducing latency for small packets from one port in the presence of saturating traffic of large packets.The design demonstrates that lightweight Fair Queuing algorithms can be useful for simple arbitration without introducing an additional queuing stage which increase both complexity and latency.
Ordinary round-robin servicing of queues can be done in constant time. The major problem is the unfairness caused by possibly different packet sizes used by different flows.Our scheme is modification of round-robin servicing using DRR algorithm applied on NetFPGA platform.We use round-robin servicing with a quantum of service assigned to each queue; the only difference from traditional round-robin is that if a queue was not able to send a packet in the previous round because its packet size was too large, the remainder from the previous quantum M added to the quantum for the next round.
Deficit Round Robin is one of the most successful algorithms to approximate Fair Queuing with minimal computational overhead. Deficit Round Robin places the size of each packet in a register then compares packet size with deficit counter which incremented by quanta at each round and forwards packets if packet size is less than deficit counter value, after forwarding packet deficit counter is decremented by packet size value. Thus a scheduler scheduling one queue with large packets and one queue with small packets will allow a proportional number of small packets through for each large packet forwarded. This simple algorithm emulates Fair Queuing with a very low computational overhead and is one of the most practical techniques for approximating Fair Queuing.(the following link show DRR example).
- We add eight counters to each of the eight input queues (Deficit counters) and the logic necessary to extract the size of each packet from IOQ header and store size value in eight registers.
- For each HOL (Head of Line) packet:
- if its size is <= (quantum + credit) send and save excess inside deficit counter.
- otherwise save entire quantum.
- If no packet to send, reset counter (to remain fair).
We developed two testbenches comparing both RR & DRR Input Arbiter’s. First we build a top module that Rx queues core & DRR module are instantiated, then we perform a testbench by injecting random packets size in each Rx queues & monitoring the output statistical values that used in plotting graphs.
- we Inject 100 packets of random size in each Rx queues.
- Change every time quantum value then run testbench.
- we plot total throughput.
- we plot Fairness Index according to Fairness Equation.
From previous graphs it’s clear that there’s inverse relationship between fairness & throughput so we choose the suitable quantum which achieve approximated fairness with low maximum throughput(Quantum~=500-600 Bytes).
- We Inject 100 packets of random size with certain different average in each Rx queues.
- Measure throughput of each queue for DRR & RR as shown.
It’s clear that DRR provides isolation property which satisfies fairness, however RR provides higher throughput but it’s fairness nihilistic.
So, when Quantum increased ….. DRR converges to RR.
We perform real hardware experiment by using Ostinato Ethernet Packet Generator, we connect NetFPGA port 0 (nf2c0) with eth0 & NetFPGA port 1(nf2c1) with eth1, then we generate random packets & transmit them from eth0 to eth1, To Check design functionality.
Full Regression test isn't finished yet, there's some technical errors face us that we are working on it.