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.

The Probability Factor in the Creation vs Evolution Debate

In this post I want to examine the debate of creation vs evolution from a different angle. I am neither in favor of one or the other, but before you dismiss me as an ignoramus, hear me out. Indeed, I am somewhat Christian by “faith”, though I do have several qualms with philosophical aspects of Christianity. Nevertheless, in the realm of science vs religion, I believe that there is a very important aspect that has been left out of the public debates, most likely because the average listener/debater is not an expert in probability theory. However, I will try to present this argument in a simplified manner using a numbered outline..

1) The theory of evolution is often viewed at a very macroscopic model with too many unknown variables and is thus difficult to verify, even if the probabilistic principles driving various aspects of the theory are sound.

At the top level, you have natural selection determining which animals “tend” to survive and which “tend” to die. This is largely based on the existing environment and the survival and propagation of a particular species, which is correlated with certain “favorable” traits obtained through either mutation or sexual reproduction. Note that the number of factors (e.g. environment, interactions and behavior, genetic traits) are huge and therefore very difficult to analyze jointly. Experiments can only verify that certain aspects hold statistically in isolation (or using only a small subset of factors). Complete, joint experimentation is too complex and takes too long to conduct.

2) There exists a truly probabilistic element in the universe, namely, that particles exhibit probabilistic wave functions.

I’m not a physicist, but from what I know that according to quantum mechanics, before observing any particle, the particle exists only as a probabilistic wave function which collapses upon observation. It is entirely possible (though not probable) for a baseball to be thrown horizontally and yet curve upward into space. In any case, to analyze sexual reproduction or gene mutations at the quantum scale is intractible. Hence evolution is still modeled based on statistical experiments at a higher level. Hence, while some mistaken quantum physics to support the theory of evolution, this is not true, though it is philosophically “consistent” with evolution.

3) What is often measured is the “average case” or “high probability” behavior, not the “ground truth”.

This is hopefully self-explanatory and is related to the above argument (intractibility). A simple illustration is brownian motion (the precise behavior of molecules) for an object at rest (a macroscopic, average behavior). One might perform kinematic experiments based on modeling the object as a whole, instead of accurately measuring the precise locations and trajectories of its individual particles.

4) The laws guiding the universe are assumed to be stationary.

Stationarity is a concept derived from the theory of random processes which states that what has happened, is happening, and will happen in the future (as time goes to infinity) will always follow the same distribution. Stationarity is an extremely important assumption required for the scientific method to hold, since, given that a result is validated, then it has always held in the past, holds in the present, and will always hold in the future. Otherwise all experimental results are meaningless.

5) 3-4 makes a strong case against young earth creationism, but only “with high probability”.

Stationarity can make a strong case against young earth creationism for two reasons: it supports the big bang with high probability. If the physical laws have always held as they do now, based on astronomical data there should be a singularity (with very high probability) around 13-14 billion years back in history. It also makes a case for the accuracy of radioactive carbon dating.

6) Interestingly, young earth creationism is also consistent with scientific theory based on 3 and 4.

Why? If the world indeed operates based on nondeterminism, then however negligible the probability of young earth creationism, there is still a non-zero probability that universe arranged itself accordingly in 7 days, just as there is a negligible (but non-zero) probability that the universe exists in its current state at the present time! To understand this, one needs to remove the paradigm of thinking in terms of “wholes”. We are not discussing the average behavior of macroscopic objects, but rather each individual quark, boson, muon, etc. in the observable universe. The reason why our observed universe has near zero chance of existing is a simple consequence of the sheer number of particles in the known universe, and the fact that they each exhibit probabilistic wave functions.

Hence, even if observable evidence points to the big bang “on average”, the universe need not always behave “on average”. Christians believe that with God all things are possible (though not necessarily probable)–and in this case God needs only operate within His own designed physical rules! Hence young earth creationism is consistent with scientific theory under the “guidance” of a non-quantum Cause.

7) Young earth creationism can not be experimentally verified. (i.e. it is philosophically valid, but can not be considered science.)

Unfortunately, due to its extremely low probability of occurence, it is nearly impossible to experimentally validate the 7 days of creation theory. The only tools that can be used to support young earth creationism is suggestive evidence (e.g. almost every nation had a “dragon” in its mythology/folklore, suggesting that humans might have lived among dinosaurs). Otherwise, it must be accepted by “blind faith”.

Another way to think about it is the following: If you saw a “miracle”, could you repeat it?

Conclusion: I am not the most eloquent writer, but hopefully this post has helped you to think “outside the box” regarding the debate that has been all over the news since… 1844. And hopefully those of you who are on different sides of the spectrum can develop an appreciation for one another’s viewpoints.

Michael Righi Arrest Case

A man was falsely accused of violating the law…

http://www.michaelrighi.com/2007/09/01/arrested-at-circuit-city

… and the system fought hard to convict him.

He managed to win the trial.

 http://www.michaelrighi.com/2007/09/20/success/

Kudos Michael, and thank you for bringing this corruption and injustice into the public spotlight.

Shai Avidan of Merl (now hired by Adobe) published a really cool seamless (and non-uniform) image resizing algorithm at SIGGRAPH this year. The visual effects of this algorithm are amazing to watch!

The end of the video also inadvertently teaches you how to cleanly remove your (not-so) significant other seamlessly from all of your digital photos. =O

Decoupling

The below is slightly paraphrased…

Me: There are a lot of cute classy women in NY.
Mod: :OOO
Me: but it looks like most ppl are couples already
Me: So most of the cute womens have a bf standing beside them =[
Mod: you’ll just have to decouple some of them
Me: omg
Mod: LOL
Me: Yes, I don’t like their inflexibility. I would like to recouple them with my own class.

http://en.wikipedia.org/wiki/Decoupling Also, in computer science, highly coupled code refers to code so intricately intertwined that neither can exist without the other. This inflexibility is usually the result of poor design.

Me: “i would like to uh… rearrange your system of equations so that you are independent from your bf”

I should be shot if I ever use any of these pickup lines.

“If you were sin^2(x), I would want to be cos^2(x) so that together we could be 1.”

“Are you singular? I find that hard to believe since you rank so high on my scale.”

“Hi, my memory is faulty and I seem to be lost. Can you allocate me a pointer to your address?”

“Do you mind if we research each other a little? If we’re lucky, we might yield some good results that will eventually lead to a proposal.”

Yep, they came up during random conversations, and they’re not all mine. Please don’t look at me weird.  =[

Great musical comedies

I think it’s about time to revive this blog, although the result may be far less “theory-centric” than it was originally intended to be. But hopefully I will provide more thought-provoking posts from here on out. Before anything substantial though, here are some great links to some great comedic musicians. Igudesman and Joo have the best duets ever!

Mozart Bond

Riverdancing Violinist

Rachmaninoff had BIG hands

Happy Mother’s Day!

Thank God for mommies! Here’s Jay Chou’s “Listen to Mother” song in a cappella.

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!

Happy Pi day!