DRRInputArbiter
- Status
- Known issues
- Responsible
The Input Arbiter module multiplexes the eight input FIFOS to the internal bus. Initially, the referee implements a round-robin (RR) algorithm, which copies one packet from each queue at a time.
Although simple and practical, this approach has some performance problems when some port receives small length packets, or have different receiving speeds, these ports will experience higher delay and will even drop packets if they become full. This happens because the copy of a big package from another queue is equivalent to copy not just one, but various packages from these ones, so, if you keep copying one packet from each fifo at a time, the queues throuput will be unbalanced.
For example, we have only two queues, the first of which receives 800 bytes packets, while the latter receives 50 bytes packets, so the same rate. Every visit to the scheduler, the first row deliver a quantity of data equivalent to 16 packets of the second, so she may eventually fill up and lose packets.
Our proposal was to implement the algorithm Deficit Round-Robin (you can read at this link) to do the multiplexing, this should help to even the ports data throuput and prevent possible packets loses. Our goal is to have an average number of bytes (quantum) when visiting each fifo, and so there will be a "fair" distribution of resources.
This technique is described as following: Each time one of the queues is visited by the arbiter (he visits them one after another), it receives QUANTUM credits of words to copy (24 words in this case), or it's credits are resetted if there are no packets to copy. If the queue's packet is bigger than that, she accumulates the credits to the next visit; if not, she copies a number of packets equivalent to her credits. This algorithm summarizes the process:
1 - If the queue is empty, zero her credits 2 - Otherwise, add Quantum to the queue credits 2.1 - If the size of the first package is less than credits 2.1.1 - Copy the whole package, credits = credits - packet size 2.2 - If there is another packet in the queue, go to 2.1; if not, visit next queue
The following changes were made in the input arbiter module: - Change the input fifos fallthrough fifos; - Place a 16-bit register for each row, credit counter; - An extra stage in the state machine to measure the size of packets; - Place a packet header reader; - Change the module to communicate with the CPU for it to report claims of each row and get the new values for the quantums.
The modules were changed input_arbiter (contains the algorithm), the in_arb_regs (to create the registers of communication with the CPU) and udp_defines (which contains the names of registers and constants used). A test was done to test the performance of the new algorithm. In this testbench we used the version of the arbitrator who does not communicate with the CPU and has quantums packet of 1522 bytes.
We runned two simple testbenches comparing both RR and DRR Input Arbiter's. We inject 8Kbytes of data to each FIFO and checked the throughput. On the first test, the packets size are according to the following values:
Queue 0: 16 150 Queue 1: 150 300 Queue 2: 300 500 Queue 3: 500 700 Queue 4: 700 900 Queue 5: 900 1100 Queue 6: 1100 1300 Queue 7: 1300 1522On the second, all queues received packets with the size 16-1522 bytes. These plots show us the effectiveness of the technique:
The full regression test is yet to be done.