Justice Router ftw?

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.

Summer in New York

Aside from the cultural and artistic aspects of the City, there are other perks that come with being in New York. For example, see below:

link: http://creativeclass.typepad.com/photos/uncategorized/2007/04/03/singles_2.jpg

I didn’t realize LA was so bad. I hate LA. And don’t even get me started on the pollution and traffic. Seriously, LA drivers are the worst (both aggressive AND careless).

Anyhow, I will be going to New York this summer for an internship at IBM Watson. Wish me luck!

Idiots at Verizon

I really, really can’t believe this. How do you get a job when you can’t even do basic math? GG America.

Too geeky or not too geeky

If you could choose to be very geeky or to be totally non-geek, what would you choose?

For me, this is a very tough question.

My favorite pastime as a toddler (i.e. 3 years old) was doing arithmetic. Since I could not write at the time, I would literally ask my parents to write for me while I solved addition and subtraction problems for fun. I could do long multiplication and division and understand decimals at the age of 5. Today, I dream graphical pictures of optimization and game theoretical problems. It would be a waste, as some people say, for me not to pursue a lifestyle of pure geekhood, which is, of course, the path of academia or research. I am not saying that academia is an easy path; no, it is a path far more grueling than a phd. You have to LOVE what you are doing, or you will never survive. You have to ENJOY being a geek.

But I never chose to be a geek; I was born one. And for me, it’s a path of comfort and security. Since very few people can do what I do, companies will always want me. I will never be low on demand.

The downside of being genetically disposed toward geekiness, however, is if you wish you could be something else. I, for one, would like to live as a non-geek for a few years. I could learn useful business and communications skills. Perhaps if I had the courage to confront my weaknesses, I could make more friends, be more social, have more fun, find a girlfriend, etc. But it’s a far bigger jump for me than for others, which makes that non-geek lifestyle all the more appealing. Of course, I’m sure some people who do not have my uncanny (dis)abilities would envy me for excelling in what I do.

After all, do we not all want what we can not have?

Actually, I’m not as bad as I made myself to be above. I try my best to balance my life with sports and “real world” contact over the weekends. I can’t live forever inside a theory box.

Mathematics owns you.

I’ve noticed that for as long as I’ve been alive, there are always people who sneer and jest at nerds, or in general, people who take interest in mathematics. Just recently, I was tutoring someone, and someone not much younger or older than I walked by and smirked at me in disdain. Well, I went on my business and ignored him. People who do not realize the importance and the contribution of mathematics to society should be left alone in their own little world.

But just so that you are not put in danger of being regarded as an ignoramus, I’d like to offer some pieces of a grand view of how mathematics is intricately involved in our daily lives.

1) Mathematics makes a real difference in this world aside from the boisterious interpersonal tactics and politics repeated in every epoch throughout history. It is said that history repeats itself, but the only reason why history can make that gradual change is due to the development of several things: better modes of transportation and communication, better ways to count money, better ways to manage a company–all motivated, designed, and guided by principles of mathematics. So the next time you’re watching a movie or tv series, or some sappy drama from Japan or Korea, remember: if it were not for math, you would probably be working on a farm, picking corn or rice or whatever grows where your race is from.

2) Mathematics makes you smarter than you think you can be. If you hate studying, fine. Go find a lazy job. But know this: mathematics can STRETCH the mind. And this is not purely genetic: of course some people are born naturally gifted in mathematics, but look at all the foreign countries and how their students slaughter Americans at math. But my main point is: you don’t have to be #1, but at least, for the sake of humanity, feign some interest/appreciation for mathematics. It makes you smarter.

3) Most importantly, your life is controlled by mathematics, unless you’re one with nature and live in the forest. Yes, you heard me right–CONTROLLED. The table lamp and the light in your room, the computer you use to do work and play games, the tv that you watch every evening, the refrigerator, the published copy of the book you’re reading, or the xeroxed copy of that book chapter, the bed you sleep on, the clothes you wear, the medicine you take when you’re sick, the house you live in, the car you drive, the bus you take to school or work… NONE of this came about without the advancement of mathematics, whether it be in the field of physics, chemistry, biology, material sciences, engineering, or economics. Remove mathematics from any one of these fields, and your world falls apart. So the next time you’re driving around in your souped up automobile staring down the nerds at school, or when you’re bullying that small, nerdy freshman and taking his lunch money, just remember: you have just proven to yourself that you are controlled by mechanical engineering and economics, which are controlled by mathematics. You think you’re owning the apostles of mathematics, but in reality, mathematics owns you.

There may be many more points I could make, but I think this is sufficient. Don’t hate on the nerds. All your futures are belong to us!