I can’t believe I still have this amusing rant from a few years back:
The Justice Router: A New Approach to “Fair” Queueing
Inspiration
For a whole year, I have been living off of Verizon DSL and sharing my connection with 8 people. Verizon is pretty lame; it caps our upload at approximately 10kB/s, meaning that between the 8 of us, resources are scarce. Unfortunately, among the 8 of us, there are resource hogs who like to download 5 movies at a time while BT-ing 3 other movies, which floods our network with tons of ACK packets and slows our internet speed to a complete halt. To give you an idea of how terrible this situation is: my average ping time is around 1/2 second. On a bad day, my ping time is around 3-5 seconds.
First of all, I am very respectful toward network usage. If I find that the ping time goes above 200-300 milliseconds, I will graciously cancel one of my two downloads or turn off AIM. Moreover, when I am playing a game, I make sure that I do not download or upload anything. My upload rate is usually below 2kB/s at a “busy” time.
Unfortunately, just because you follow rules of your own doesn’t mean others comply to it. I decided to go talk to people individually about network usage. Unfortunately, one particular person, who will go unnamed for now, gave me an attitude. Apparently I can’t talk sense into some people. To this day, he still hogs the bandwidth without regards to others.
Thanks to him, I’ve developed a new idea for queueing/packet-switching networks. I propose a method which I call Justice Routing.
Some background information
Normally, when people describe a fair queueing system, their aim is to get packets through the network with a speed proportional to their length. Therefore, every packet (of the same type) has equal transmission rate in bits/second. Most packet-switching networks have priority classes for video/sound/data packets. Streaming video packets generally get high priority, because the application on the other side needs to constantly buffer these packets to provide high quality of service (good display). Fair queueing and priority queueing are age-old problems, but they fail to address the bigger problem in a shared network–that is, network hogs.
Why does network hogging increase latency so drastically? To analyze this, we assume an M/G/1 queueing system and notice that the waiting time is proportional to the second moment of a packet service time, and inversely proportional to 1 – (arrival rate/service rate). Never mind the first part; the second part (inverse proportionality) is more important. Suppose someone is uploading ACK packets at a rate of 500 every second on average, and the router can process 1000 packets per second on average. Then 1 – (arr/serv) = 1 – 500/1000 = .5. Take the inverse, and we get 2. Now suppose someone adds a couple BT’s to his downloads and uploads at a terrifying rate. Now we have 950 packets being sent out every second. The service rate is still 1000 per second. Now we get a factor of 1/(1-950/1000) = 20! Our waiting time has increased tenfold, even though the total upload rate has not even doubled. Try increasing the upload rate another 50 packets/second, and you get an infinite waiting time! Notice that you get a much better performance downloading at half your rate than you do at full rate, hence having 1 or 2 concurrent downloads is considered good manner, while flooding the network with 8 downloads is very bad manner. Fortunately, buffers are limited in size and often smartly designed so that they drop packets if queue sizes grow too large. Using an exponential backoff mechanism (e.g. TCP/IP) for retransmission, we’ll never have infinite waiting time. But we will still have terrible 10 second waiting times. WHATEVER SHALL WE DO???
Solution–The Justice Router
The Justice Router will analyze the source and type of each incoming packet and keep a counter for each source. Every few seconds, the router will compare the counters with a certain threshold and then reset the counters. If Mr. Bacon’s counter number is higher than the threshold, his computer will receive a violation. His upload will be capped at a lower rate each time a violation is received. Violations are handed out ever so often, so that eventually a stubborn network hog will have his connection reduced to a very small fraction of the total bandwidth. However, if he behaves himself, his violations will eventually go away after some time, and full network capacity will be restored. While administrators often block or disconnect people for flooding, this router will administer justice by itself.
Unfortunately however, the design of the Justice Router is inherently “merciful.” If a person’s upload is capped, he will be less likely to receive a violation. Below a certain rate, he will no longer receive any more violations. Thus the router’s violation scheme ought to be adaptive. The next section describes a scheme for harsher sentencing.
Three-strikes-and-you’re-out
In order to exact greater punishment, I propose the three-strikes-and-you’re-out policy. When Bacon receives “mercy” for the first time (i.e. his upload cap goes below the violation threshold), he will receive a strike. After the cap increases again and decreases below the threshold, he receives another strike. After three strikes, Bacon is disconnected from the router for the same amount of time that he has been connected since the beginning of his router farm life. If there was a year of Bacon, there will be a year without him, and everyone will be happy and healthy. Now keep in mind that after Bacon is readmitted to the router, the router still keeps track of his complete history. If within the next 30 minutes, he gets 3 strikes, Bacon will be out of the Justice Router for another 1 year and 30 minutes.
Justice is served with a plate of ham and spicy pork.
Posted by bkungfoo 
Posted by bkungfoo 
Posted by bkungfoo 
