A Survey on Hash-Based Packet-Processing Algorithms

Sometime way back, Graham Comorde invited me to a DIMACS workshop on Algorithms for Next Generation Networks, where I talked the usual talk about hash tables, Bloom filters, and things. The organizers later had the wherewithal to undertake putting together a book or collected chapters on the topic, and asked us (us being, of course, me and my student Adam Kirsch) for a chapter related to the talk. Adam was just finishing his thesis, and was willing to take on modifying his thesis to form the basis for a survey chapter. I wrote up a section or two, and for good measure, we got George Varghese, who is the world expert -- and author of the book Network Algorithmics -- to join in as well. (In particular, we really wanted George's much more practical perspective on what works and what doesn't!) The result here is a hopefully pleasant light read on current goings-on in the area of hash-based network algorithms, attempting to blend and show the connections between theory and practice.

There's still time for feedback for the final version; please mail me if you have any constructive suggestions.

Voting and Anti-Voting

While at NZIMA, I listened to Dominic Welsh's talks on Markov chains. It was a general talk, with a large chunk devoted to rapid mixing and applications. At some point he brought up the voter and anti-voter model, problems that I heard about a long time ago in the distant past, and that raised some questions in my mind.

The voter model can be expressed as follows. We have an undirected graph G, where each vertex has a label. For convenience, let's assume the labels are in {0,1}, although larger alphabets are possible. At each time step, a vertex x is chosen uniformly at random, and x chooses a neighbor y uniformly at random. Then x changes its label to match y's label. This is a Markov chain with absorbing states with all vertices having the same label. It's natural to ask things like what is the probability that you end up in the all 0/all 1 state from a given configuration.

If the graph is d-regular, and you start in a state with k 0's and n-k 1's, a simple argument gives that the probability of eventually being absorbed into the all 0 case is k/n. (Exercise Left To Reader.) Things seem to get more complicated for more general graphs. Here are some interesting questions that come to mind. Note: I don't know which are open and which aren't...

1. Given a graph G and a starting configuration of labels, is there a polynomial time algorithm for computing the probability of being absorbed into the all 0 state? Or could a hardness result be proved? [My guess is there's a hardness result in there somewhere.]
   
2. Given a star graph (one node in the center, connected to n-1 other vertices) and a starting configuration, what is the probability of being absorbed into the all 0 state (preferably in some natural closed form)? In particular, if you start with a 1 in the middle and a 0 everywhere else, what is this probability as a function of n? Notice that by symmetry here one can easily compute these values in polynomial time; the question is whether there are pleasant equations. [On some reflection, it's clear there will be nice equations; this is almost a birth-death chain with an added "phase" needed to track the center vertex. Exercise left to reader...]
   
3. Similar questions to 1/2, but ask about the expected time/distribution of time until absorption.

Perhaps more interesting is the anti-voter model, which works just like the voter model, except that x changes its label to disagree with y's label. (Here the {0,1} alphabet is the most sensible.) Now we do not have absorbing states; we have a stationary distribution. But again one can ask similar questions:

1. Given a graph G and a configuration of labels, is there a polynomial time algorithm for compute the stationary probability for that state?
2. Are there natural families of graphs for which the stationary distribution for the anti-voting model has an easily expressible form? [d-regularity no longer seems to be enough...]
   

Obviously, one can argue about the importance of these questions, but I would just take the point of view that such easily expressible and seemingly natural questions about basic Markov chains are always interesting in their own right.

Shopping Period Lecture

One of the great Harvard "traditions" that I enjoyed as a student is the "shopping period". Students don't pre-register for classes; they spend the first week "shopping" whatever classes they like, and then choose what ones they want to take. (I'll talk more about the "politics" of shopping -- the pros and cons -- next time.)

Because of this, rather than dive right into material the first class for my Algorithms and Data Structures class, besides going over the syllabus and requirements, I do something that at least I consider fun. We talk about how to get fair bits from a biased coin. The class starts with the classic brain-teaser: suppose you have a coin that may be biased. How can we flip that coin to decide something fairly, like who should pay for lunch?

[The simple solution to this question, unless I'm mistaken, is commonly attributed to von Neumann.]

Starting from there, I try and take the class through a series of questions, leading up to how to efficiently extract lots of random bits from a sequence of biased flips. The method I base the lecture on is due to Yuval Peres [(see "Iterating von Neumann's Procedure for Extracting Random Bits," Annals of Statistics, March 1992)], and I learned about it at some point in graduate school at Berkeley. I try to run this lecture in a very back-and-forth manner, asking questions of the students and trying to get them to answer. (I also do this a bunch during the semester, with varying degrees of success...) Here's a version of my notes, with the various questions.

For the students who decide not to take the course, I figure at the very least they've learned something interesting that they can take with them. Also, it's conceivably the only time students will hear the word "entropy" in a computer science class, so I think it's worthwhile for that alone. Somehow, this problem fascinates people. Way back when I had more energy, I wrote a Dr. Dobb's article on it to show it to a wider audience, and there's been lots of related research on the problem. In some sense, this problem is the pre-history of all the randomness extraction work that has come since.

The Hiring Problem and Lake Wobegon Strategies

Continuing the "and now a word from our sponsors" riff, I'll describe a paper (to appear at SODA) that's joint with several people at Yahoo! Research, and started on a visit there.

We're looking at a situation similar to the well-known "secretary problem". For those unaware of the secretary problem, it goes like this: you need to hire a new secretary. There are n applicants, and you will interview them in a random order. The result of each interview is the relative rank of the applicant against those you have already interviewed. ("This applicant was the 3rd best so far.") After each interview, you have to decide whether to hire that applicant before the next interview; once you pass on an applicant, they're gone. Your goal is to maximize the probability that you hire the best of the n applicants. What's your optimal strategy? (I won't give away the answer for those who haven't seen the problem; it's easily found online.)

In our setting, we are considering growth strategies for a small startup company. Each applicant has a quality score, which we take to be uniform on [0,1], that we learn in the course of the interview. Unlike the secretary problem setting, we want more than one employee, although there is not a fixed number of employees we are aiming for. We simply want to grow, balancing the tradeoff between the speed of growth and the quality of new employees.

In the paper, we consider the strategies where we choose to hire an applicant only if their quality score is above the average of the current employees. (We study both the mean average and the median average.) We call these strategies Lake Wobegon strategies, after the fictional town of Lake Wobegon, where

all the women are strong, all the men are good looking, and all the children are above average.

Here, everyone we hire is above average (at least when we hire them). Google claims to use this strategy.

I should hasten to emphasize that (despite the Google claim) we feel that the hiring problem is about hiring employees just as much as the secretary problem is about hiring a secretary: very little. Rather, it's an abstraction, leading to problems about random processes and decision-making in the context of incomplete information. I've given the talk about this work a few times, and some people get hung up on setting it up as an optimization problem and determining the optimal strategy. You could, I suppose, but you'd have to be precise about the tradeoff about growth speed vs. quality, and the abstraction is already removed quite a bit from reality. I personally think it's simply interesting to consider how growth processes like this work under Lake Wobegon strategies; does anyone know of any related examples in nature?

If you're a puzzle person, then you might consider the following: suppose we start with a single person, of quality 1/2, and then interview until we hire n people. Which strategy will lead to higher average quality -- hiring above the median, or hiring above the mean? (Or are they asymptotically the same?)

The hiring problem leads to a great deal of curious mathematical fun : lognormal distributions, the Berry-Esseen inequality, the difference between hiring above the median and hiring above the mean (yes, they're very different!), and potentially lots of open problems and further variations to look at. Hopefully, the problem will become at least a fraction as popular as the secretary problem has.

I'm not sure why people at Yahoo were interested in this. In this case, I think they too got caught up in the mathematics of the problem. I'm glad that in the research labs, people still just follow their curiosity from time to time, even if the immediate application isn't obvious.

Negative Dependence

I lost sleep last night trying to prove a collection of random variables were negatively associated.

Negative dependence is one of those nice tricks that hardly ever gets used because it usually ends up being harder than it should be. While there are many flavors of negative dependence, the most natural is probably "negative assocation". The intuition is simple -- given a collection of random variables, if when one goes up that means the others should go down, then they are negatively associated. More formally, given any monotone non-decreasing function f of a subset of the variables, and a monotone non-decreasing function g of another disjoint subset of the variables, if f goes up, g should go down. Proving this holds formally is often more difficult than one would expect.

Why should we care? Well, it turns out that if a collection of random variables are negatively associated, then even though they are dependent, you can just apply your standard Chernoff bounds to them, without a care. Chernoff bounds (and other tail probability bounds) pop up in many arguments, but they can be very difficult to deal with when the random variables are dependent. Usually, you have to switch to a martingale argument, since standard Chernoff bounds apply only to independent random variables. If you can get negative dependence, it's much cleaner.

The best introduction to negative dependence is probably this surveyish article by Dubhashi and Ranjan. The focus is on how balls and bins problems are a natural example of negative dependence -- if a ball lands in one bin, it can't be in any other! Naturally, this explains my interest.

For example, the following problem came up for me some years ago in this paper. Suppose we thrown n points uniformly at random on the boundary of the unit circle. We want bounds on the number of arcs of length larger than say c/n for some constant c. If arc lengths were independent, we could just apply a Chernoff bound, easy enough. But of course they're dependent -- the sum of the arc lengths is 1! Intuitively, though, if one arc gets longer, then the others must get shorter, so there should be negative dependence. We proved what we needed to get the Chernoff bound, but it wasn't pretty. (I've since seen that a stronger version of this result is given as an exercise on negative association in the very nice-looking draft monograph by Dubhashi and Panconesi; to tell the truth, I'd like to see it worked out, as it seems to me that the conditioning is a bit subtle, but then again, geometry confuses me.)

In fact, in that paper we actually wanted a similar result in the following setting. Suppose one throws n points uniformly at random into a fixed region (say, for example, the unit square, or to avoid boundary issues, the 2-d unit torus). We want bounds on the number of Voronoi cells of size larger than say c/n for some constant c. If Voronoi cell sizes were independent, we could just apply a Chernoff bound, easy enough. But of course they're dependent! Intuitively, though, if one cell gets bigger, then the others must get smaller, so there should be negative dependence. Or maybe that isn't the case. Now I can't remember if I ever found an example that led me to believe it wasn't the case... Anyhow, we couldn't prove negative dependence easily, so we ended up using an uglier martingale argument that sufficed.

I was surprised at the time that I couldn't find any reference to type of this problem in the geometric literature. If negative dependence of Voronoi regions in random settings is still open (and true!), I'd be happy to ponder it with anyone who has a better sense of geometry than I do. In general, the area of negative dependence seems like a promising area for additional results.

Why Simple Hash Functions Work Well

On my publications page there is a recently finished new paper I'm quite excited about. Part of that excitement is because it's (finally!) my first paper with my remarkable colleague Salil Vadhan. The rest is because I think it answers a question that's been bothering me for nearly a decade.

A fair bit of my research has been on hashing, and often I end up doing simulations or experiments to check or demonstrate my results. For many analyses of hashing processes -- including Bloom filters or the power of two choices, we (or at least I) assume the hash function is truly random -- that is, each element is independently mapped to a uniform location by the hash function. This greatly helps in the analysis. Such an assumption is downright painful to strict theorists (like Salil, who has questioned me about this for years), who rightly point out that hash functions being used are not anything close to truly random, and in fact truly random functions would be far too expensive in terms of space to even write down in practice.

Of course theorists have developed ways to deal with this -- with the seminal work being Carter and Wegman's introduction of universal hashing. The key idea is that you choose a hash function at random from a small family of hash functions that are easy to compute and require little space to express, and this choice guarantees some random property, even it is is not as strong as choosing a truly random hash function. For example, the basic universal hash function families guarantee that for any elements x and y in the universe, if you choose a hash function uniformly from the family, then the probability that x and y land in the same bucket is 1/#of buckets. That is, the collision probability of any specific pair is what it should be. Once you consider 3 elements at the same time, however, the probability that all 3 land in the same bucket need not be (1/# of buckets)^2, as it would be for a truly random hash function.

The most used variation is probably k-wise independent hash families, which have the property that when a hash function is chosen from that family, any collection of k elements are independently and uniformly distributed.

A negative with using these weakened hash families is that usually, naturally, you get weaker results from the analysis than you would using truly random hash functions. A fine example of this is the recent work by Pagh, Pagh, and Ruzic on Linear Probing with Constant Independence. With truly random hash functions, linear probing takes expected search time O(1/(1-alpha)) where alpha is the load on the hash tale. They show that using pairwise (2-wise) independence linear probing can take time O(log n) on average -- it no longer depends on the load. Using 5-wise independence they get expected time polynomial in 1/(1-alpha). That's a great result, although there's still a gap from truly random.

The real problem though, is the following: pretty much whenever you do an experiment on real data, even if you use a weak hash function (like a pairwise independent hash function, or even just some bits from MD5), you get results that match the truly random analysis. I've found this time and time again in my experiments, and it's been noted by other for decades. That's part of the reason why when I do analysis, I don't mind doing the truly random analysis. However, it leaves a nagging question. What's going on?

The obvious answer is that there is also randomness in the data. For example, if your data items were chosen uniformly from the universe, then all you would need from your hash function is that it partitioned the universe (roughly) equally into buckets. Such a broad assumption allows us to return to the truly random analysis. Unfortunately, it's also amazingly unrealistic. Data is more complicated than that. If theorists don't like the idea of assuming truly random hash functions, you can imagine practitioners don't like the idea of assuming truly random data!

For years I've wanted an explanation, especially when I get a paper review back that questions the truly random analysis on these grounds. Now I think I have one. Using the framework of randomness extraction, we can analyze the "combination" of the randomness from choosing the hash function and the randomness in the data. It turns out that even with just pairwise independent hash functions, you only need a small amount of randomness in your data, and the results will appear uniform. The resulting general framework applies to all of the above applications -- Bloom filters, multiple-choice hashing, linear probing -- and many others.

In the next post, I'll give a few more details.