-
Notifications
You must be signed in to change notification settings - Fork 141
DRRNetFPGA
- Status
- Known issues
- Authors
Although not well defined, Fairness is a desirable feature in networking systems, especially when there is contention for resources in network. A fair node in network can provide bandwidth guarantee for different flows, independent of other flows resource request. In this project, we implemented a fair queuing scheme using Deficit Round Robin (DRR) algorithm which is generic in terms of number of flows it can handle and the policy by which it can distinguish flows.
- Install the NetFPGA Base Package
- Install the NetFPGA Beta-Plus Package
Download from Releases
Simple FFIO queues do not achieve fairness. Those flows that generate more traffic are getting more bandwidth than the others. Therefore, we are looking for other queuing schemes to achieve fairness and guarantee bandwidth. Probably the most natural queuing scheme that provides fairness, is bit by bit fair queuing, in which we send packets belonging to different flows into different queues and then at each round serve one bit from each queue. (In weighted version, the number of bits served may be more than one)
The problem with this approach is that it handles flows as stream of bits not packets. If instead, we serve one packet in each round, the scheme will not be fair since the flows with larger packets will get more than their fair share of bandwidth. One good alternative algorithm that is both simple and solves the above problems, is DRR. Incoming packets in a stream are being sent to different queues based on the flow they belong to. Then, at each round, each of the queues will be given some number of bytes of credit to be served. If the next packet in line is small enough to be served using that much credit, it will be served and the credit is reduced. Otherwise, it will not be served at current round and the credit will remain for next rounds until the flow accumulate enough credit to be able to have one packet served. If after serving a packet from a flow, that flow has some remaining credit and still has packets to be served, the serving process will continue until it is not possible to serve more packets from that flow (i.e. that queue runs out of credit). Then the reaming credit will be saved for that flow until the next round, unless there were no more packets from that flow in the queue. In the later case, all the credit will be lost. (In other words, there is no credit reservation, if the flow does not need its credit at the current time) Note that the amount of credit given to each queue in each round may vary from one queue to another, resulting in different bandwidth assignment to different flows. For more information about DRR algorithm, see "Efficient Fair Queueing Using Deficit Round-Robin," M. Shreedhar and G.Varghese, Proceedings of the ACM Sigcomm '95 and IEEE/ACM Transactions on Networking 4(3):375-385, June 1996.
In our implementation, the DRR module can be instantiated with arbitrary number of queues, where each queue will be used for one class of packets. We can specify the credit per round (in bytes) that is credited to each queue using the register interface. In order to decide on the queue that a particular packet should be sent to, we must place another module right before the DRR module (called packet classifier). Packet classifier may use an arbitrary criterion for classifying packets, it can be based on input port, ToS bits or source IP address prefix; but in all those cases, we don't need to do any change to DRR module. Packet classifier will simply add a control message (with the control bus value equal to 55H) at the beginning of each packet and specifies the class that the packet belongs to (i.e. queue number) and the number of bytes and words in packet. (These can be obtained from IO module headers)
In current distribution, we have a sample packet classifier module that can do classification based on input queue or ToS bits.
DRR just affect the outgoing rate of flows, therefore, we can not have a regression test for verifying it. (Regression tests can not easily measure rate). As a result, the only test that we have right now is for DRR basic forwarding functionality.
To use DRR module, put it wherever in pipeline that is desired, with a packet classifier connected just before it. Instantiate the genric_DRR.v with desired number of priority queues. write a packet classification module that does the classification based on any desired criterion (there is a simple example in distribution that does classification based on input port or ToS), and you are good to go.