Monthly Archives: April 2009

Infocom 2009 : network statistics problems

Posted on by

Graph Sampling Techniques for Studying Unstructured Overlays
Amir Hassan Rasti Ekbatani (University of Oregon, US); Mojtaba Torkjazi (University of Oregon, US); Reza Rejaie (University of Oregon, US); Nick Duffield (AT&T Labs – Research, US); Walter Willinger (AT&T Labs – Research, US); Daniel Stutzbach (Stutzbach Enterprises LLC, US)
The question in this paper was how to collect network statistics (such as node degree) in peer-to-peer networks. Since peers join and leave, selecting a random peer is difficult because there are biases caused by high-degree peers and low-lifetime peers. One approach to correct for this is to use Markov chain Monte Carlo (MCMC) to sample from the nodes. This talk proposed respondent-driven sampling (RDS), a technique used to map social networks. The idea is to do a random walk on the network and gather statistics along the walk (not just at the end, as in MCMC). These measurements are biased, but then we can correct for the bias at the end (using something called the Hansen-Hurwitz estimator, which I don’t know much about). Experimental works showed a big improvement when vanilla MCMC and RDS were compared on hierarchical scale-free graphs.

A Framework for Efficient Class-based Sampling
Mohit Saxena (Purdue University, US); Ramana Rao Kompella (Purdue University, US)
This talk was about increasing the coverage of monitoring flows in networks. Currently routers sample flows uniformly, which catches the big “elephant” flows but not the low-volume “mouse” flows. In order to increase coverage, the authors propose dividing flows into classes and then sample the classes. So the architecture is to classify a packet first, then choose whether to sample it. The goal is to do a combination of sketching and hashing that shifts the complexity to slower memory, thereby saving costs. They use something called a composite Bloom filter to do this.

Estimating Hop Distance Between Arbitrary Host Pairs
Brian Eriksson (University of Wisconsin – Madison, US); Paul Barford (University of Wisconsin – Madison, US); Rob Nowak (University of Wisconsin, Madison, US)
Given a big network (like the internet) with N end hosts and M monitors, how can we estimate the hop distance between two end hosts from measurements between end hosts and monitors? This paper proposes using passive measurements, so that there may be many holes in the (N+M) \times (N+M) matrix of pairwise measurements. Their approach is to use a weighted version of multidimensional scaling (MDS) to deal with the holes. This approach can also be extended to deal with side information about the network topology (for example autonomous system IDs).

Advertisement

Infocom 2009 : general thoughts and assorted topics

Posted on by

This was my first time going to Infocom, and I had a good time, despite being a bit out of my element. The crowd is a mix of electrical engineers and computer scientists, of theorists, experimentalists, and industry researchers. Although I often would go to a talk thinking I knew what it would be about, I often found that it was rather different than what I expected. At first this was a little alienating, but in the end I found it refreshing to be introduced to a host of new ideas and problems. Unfortunately, the lack of familiarity may translate into some misunderstandings in these posts; as usual, clarifying comments are welcome!

Below are the papers I couldn’t categorize into other areas.

Dynamic Power Allocation Under Arbitrary Varying Channels – An Online Approach
Niv Buchbinder (Technion University, IL); Liane Lewin-Eytan (Technion, IL); Ishai Menache (Massachusetts Institute of Technology, US); Joseph (Seffi) Naor (Technion, IL); Ariel Orda (Technion, IL)
The model is that of an online power allocation problem wherein the gain of a fading channel h_t varies over time in an unpredictable manner. At each time we can choose a power P_t for the transmitter based on the past values h_1, h_2, \ldots, h_{t-1} and we will get a reward U(h_t, P_t) = \log(1 + h_t P_t). Subject to a total power constraint, what is the optimal allocation policy, in terms of competitive optimality vs. an algorithm that knew h_t in advance? They show lower bounds for any algorithm of O( \log H_{\max}/H_{\min}) for the competitive ratio and an achievable strategy by quantizing the possible fading values and executing an online allocations strategy for the discrete problem. Of course I went to this talk because it claimed to be about arbitrarily varying channels, but what was a little unconvincing to me was the abstraction — you have to choose not only a transmit power, but also a coding rate, so it’s unclear that in reality you will get \log(1 + h_t P_t) utility each time. There may be a way to justify this kind of modeling using some rateless code constructions, which seems like an interesting problem to think about. UPDATE: I looked at the paper and saw that they are considering a block fading channel so you get that utility for a block of channel uses, and that the channel gain for the given slot is revealed to the transmitter, so you don’t need to be fancy with the underlying communication scheme.

Lightweight Coloring and Desynchronization for Networks
Arik Motskin (Stanford University, US); Tim Roughgarden (Stanford University, US); Primoz Skraba (Stanford University, US); Leonidas Guibas (Stanford University, US)
This paper was on duty-cyling nodes in a sensor network to preserve power and avoid interference. In particular, we would like to color the n nodes of the network so that no two neighbors are awake at the same time (thereby improving coverage efficiency and lowering interference to a centralized receiver). This can be mapped to problem of allocating intervals on a circle of circumference T (the cycle time) such that two neighbors in the graph do not get overlapping intervals. Nodes with low degree should get longer intervals. The constraint in this assignment problem is that the solution must be decentralized and require minimal internal state and external inputs. They show an algorithm which uses one bit of local state to use O(d_{\max}) colors in O(\log n) time, and an algorithm with one bit of local state and one bit of external side information to color the graph with d_{\max} + 1 colors in d_{\max} \log n rounds.

Using Three States for Binary Consensus on Complete Graphs
Etienne Perron (EPFL, Switzerland); Dinkar Vasudevan (EPFL, Switzerland); Milan Vojnovic (Microsoft Research, UK)
This paper looked at a binary consensus problem that was seemed on the face of it quite different from the consensus algorithms that I work on. They consider a complete graph where every node has a an initial value that is either 0 or 1. The goal is to compute the majority vote in all the nodes in a distributed manner while requiring only a small state in each of the nodes. This is related to a standard voter model, in which nodes sample their neighbor and switch their vote if it is different. If we have 3 states, (0, e, 1), where e is “undecided” then we can make a rule where a node samples its neighbor and moves one step in direction reported by the neighbor. Different variants of the algorithm are also analyzed, and the error rate analysis seemed a bit hairy, involving ODEs and so on. What I was wondering at the end is the relationship of this algorithm to standard gossip with one bit quantization of messages.

Dinner in Rio de Janeiro

Posted on by

I’ve had two good dinners already here (for those who are meat eaters). I should hit the gym to convert all the protein into muscle! The first was at Via Sete, which has pretty tasty appetizers, salads, and grilled meats and fish. We got some crab cakes (bolinhos) and calamari with manioc flour batter (it’s much soggy than normal fried calamari). I had a salad with grilled meat which was delicious (and also not too heavy, which was nice). The next dinner was at Braseiro de Gávea, a more traditional Brasilian restaurant. It was packed and the food was delicious — you basically order a set of grilled meat and it comes with one zillion side dishes (like farofa with eggs and banana, surprisingly delicious). I didn’t get to take pictures, but I might add them in later. Note : one dish serves about 3.5 people, so 3 dishes was waaaay too much food for the 7 of us. Afterwards we hit up the Academia de Cachaça, which was appropriate since some of us were in academia. They have a crazy array of cachaças to try in a pleasant open-air environment.

Pictures from Hong Kong, etc.

Posted on by

I have been castigated for not putting up more pictures of my trip to Hong Kong on Ye Olde Blog, so I’ll give a quick pointer to my Picasa album which has a lot of the pictures. So here is a somewhat backdated post on the trip.

On my first night there we went to Gaia Veggie Shop (大自然素食) in Mongkok for dinner. It’s an all-vegetarian place (with dishes containing egg marked on the menu). One of the dishes I liked best was a simple stir-fried pea shoots with ginger. I had forgotten how tasty pea shoots are, and the simplicity of the dish really brought out their flavor (this is the Cantonese style, I guess). The other option for dinner was Modern Toilet, a toilet-themed restaurant which may be worth a try later, although I was told the food wasn’t as good. I tried to take pictures of my restaurant adventures there (see the link). It’s spoiled me from eating Americanized Chinese food. Sidharth, my host, lives in a “market town,” which means he walks through a fresh produce market to get home every day. I got to try a lot of exciting fruits that are hard to get the US, including mangosteen, dragonfruit, lanzones, sitaphal (which I have only had in India, and is soooooo good), and even a durian shake (my second ever).

Being able to be in a place for more than one week was a real blessing, because I could go to some nieghborhoods more than once, and by the second week I would even leave without taking my guidebook or map with me, and just trust my memory and a hastily scribbled set of directions. Hong Kong is a pretty safe city, so wandering around and getting lost was a good and fun strategy. I’m sure people around me are sick of me talking about all the cool things I saw there, the quirky fun facts, and my love of the transit system there.

The coolest thing about transit in Hong Kong is the Octopus card, an transit card that works on all transit systems, various convenience stores (7-11 is everywhere there!), and even the CUHK cafeterias. You can add money to your card at 7-11, and there’s a deposit to get the card, so you can go to a negative balance (once) if you don’t have quite enough to get home. A close second is the red minibus system. These are 16-seater minibuses that run all night between different locations in Hong Kong. There are two that I used that went to CUHK, one from Mongkok and one from Causeway Bay. You pay something like 20 HKD and then once the bus is full it takes off at breakneck speed, only pulling over when someone calls out to the driver to stop. There’s a speedometer in the bus that starts beeping when the driver goes over 80 km/hr. Since I always took them late at night, the experience was a bit like being in a careening stick of dynamite. Exhilarating!

Oh, and we got some research ideas/projects started too.

Greetings from Infocom 2009

Posted on by

Greeting to you, patient (and probably bored) readers! I’m in Rio de Janeiro for Infocom 2009 and yes, I am going to be blogging a bit about it. The conference is little out of my bailiwick, at least so far. I go to sessions and think I might know what the talk is about, based on the title, only to find out I’m completely wrong. It’s good though, and as a challenge to myself I will try to blog about some of the talks a bit (I guess I gave up on finishing my ITA reminiscences).

So keep tuned!

Ways to keep track of ideas

Posted on by

For as long as I’ve been doing research, I’ve tried to come up with a “system” that works for keeping track of the loose ideas that filter through during talks or in idle moments. Earlier on, the focus was on recording technologies — scraps of paper, an audio tape recorder, the Palm Pilot and its inscrutable Graffiti. The Moleskine reared its sightless head, promising an end to the torment of lost epiphanies. The sad truth of course is that progress doesn’t come in lightning flashes of brilliance while strolling down a boulevard, but instead in obsessive fits and starts. So instead I’m trying to settle on a simpler method of keeping track of research questions — a text file.

Once the medium is fixed (and mutable), the central question is taxonomy. For a while I was using subject matter — Shannon theory, networking, etc. More recently I decided that it’s better to classify things by “how much I have thought about them.” I have 5 categories :

  1. Pie-in-the-sky : wow, that seems interesting… I should think about it for more than 5 minutes…
  2. Nebulous hand-waving : there’s a problem there, but what is the right framework?
  3. Percolating : ok, but what is the actual formal problem?
  4. In progress : finding the proof in the pudding.
  5. Writing : oh no, a deadline! Gotta figure out how to fit the page limit!

This seems to be working ok for me at the moment, but it’s chasing a moving target, it seems. Do any of you readers have systems that have worked out for you? Yes, this is a blatant plea to those lurkers out there…