I wrote below about rebuttals, and how the reviews were obscure and vague that I was unable to tell whether the reviewers appreciated the paper or not. I assumed it meant it was in a weak reject-weak accept range.
For two of them, it was weak accept. But the third one gave us a puzzler: "Strong reject- I have strong arguments against acceptance." Then why doesn't you review say so? Why was I unsure earlier reading the review whether you liked the paper or not? I mean, "strong arguments"!
Turns out the paper got accepted anyway as a short paper, which is what it was (you can submit to NOMS as 4 pages or 8 pages, and we went for four), so I'm not particularly bitter. But I certainly hope that when I write a review recommending strong rejection, I make it clear enough why. It was very instructive to view the reviews without the grades, it's a good exercise when writing a review to check whether one can guess the rating from the text.
Thursday, November 12, 2009
Efficient Navigation in Scale-Free Newtorks Embedded in Hyperbolic Metric Spaces
Efficient Navigation in Scale-Free Newtorks Embedded in Hyperbolic Metric Spaces, Dmitri Krioukov, Fragkiskos Papadopoulos, Marian Boguna, Amin Vahdat, Arxiv:0805.1266v1, May 2008.
Some related version was submitted to a SIGMETRICS workshop.
This paper shows that you can create some random topologies using some simple rules in hyperbolic graphs such that these graphs exhibit similar properties than Internet AS topologies (clustering properties, triangles, node degrees).
Within the hyperbolic space with the associated distance, the paper observes that greedy routing work pretty near optimal (where optimal is shortest path) for these topologies. It thus conjectures that, if one could map the Internet AS topology to a hidden hyperbolic topology, one could use this topology to do routing relatively efficiently.
This is very cute, and indeed if you could identify an underlying hidden metric space under the graph topology, that'd be great. A few thoughts quickly come to mind though: first, shortest path is not what's happening in between ASes anyway, so there's another step to take right there. Another thought is that, hyperbolic topology have an inherent scalability issue: because you can cram more points within the space (it's "larger" in some sense), then you have to use more bits to describe each point. An example: in Euclidean geometry, I can put n points equally spaced and use log(n) bits to describe each position. In hyperbolic geometry, I would need n bits to describe each position, since they would be at 1/k^n for them to be equidistant. So I can put infinitely many of them on (0,1], but with O(n) bits for each position. So greedy routing does simplify to some extent, but since O(n) bits gives me shortest path routing in Euclidean space, there's no benefit from that perspective.
Another question is this: some properties are similar in the AS-topology, and in the hyperbolic generated graph. But to what extent the graphs are truly isomorphic? Li, Alderson, Tanaka, Doyle, Willinger have this paper where they confront analysis based on this kind of high level similarities, which could lead to drastically different conclusions. So proceed with caution, it's a treacherous path. But if it leads somewhere, it could have dramatic impact.
Some related version was submitted to a SIGMETRICS workshop.
This paper shows that you can create some random topologies using some simple rules in hyperbolic graphs such that these graphs exhibit similar properties than Internet AS topologies (clustering properties, triangles, node degrees).
Within the hyperbolic space with the associated distance, the paper observes that greedy routing work pretty near optimal (where optimal is shortest path) for these topologies. It thus conjectures that, if one could map the Internet AS topology to a hidden hyperbolic topology, one could use this topology to do routing relatively efficiently.
This is very cute, and indeed if you could identify an underlying hidden metric space under the graph topology, that'd be great. A few thoughts quickly come to mind though: first, shortest path is not what's happening in between ASes anyway, so there's another step to take right there. Another thought is that, hyperbolic topology have an inherent scalability issue: because you can cram more points within the space (it's "larger" in some sense), then you have to use more bits to describe each point. An example: in Euclidean geometry, I can put n points equally spaced and use log(n) bits to describe each position. In hyperbolic geometry, I would need n bits to describe each position, since they would be at 1/k^n for them to be equidistant. So I can put infinitely many of them on (0,1], but with O(n) bits for each position. So greedy routing does simplify to some extent, but since O(n) bits gives me shortest path routing in Euclidean space, there's no benefit from that perspective.
Another question is this: some properties are similar in the AS-topology, and in the hyperbolic generated graph. But to what extent the graphs are truly isomorphic? Li, Alderson, Tanaka, Doyle, Willinger have this paper where they confront analysis based on this kind of high level similarities, which could lead to drastically different conclusions. So proceed with caution, it's a treacherous path. But if it leads somewhere, it could have dramatic impact.
Thursday, October 22, 2009
IEEE NOMS rebuttal.
I had no clue that IEEE NOMS would have a rebuttal phase. We only submitted to the conference mostly because it was in Japan (if accepted, we'll combine with a trip to the mothership) and the deadline coincided with our post-doc taking a paternity leave, so was not aware of the process of the conference.
I found the rebuttal phase from the reviewer point of view quite useless during the Globecom PC. From the author point of view, the sample is much smaller; it is quite strange that the reviews are provided without the grade, so I'm unable to say if the reviewers liked the paper or not. Obviously they are in between, they don't think it's the best or worst thing ever, but it's hard to decipher if it's leaning one way or the other. I guess it's mostly due to the format of the question, which emphasizes both positive and negative: strength, weakness and detailed (editorial) comments.
I'm not sure how to reply to the reviews, though, not knowing if the job is to not screw it up, or if it's pointless to try to change someone's mind (can a reviewer of an unconvincing paper be turned around in 3,000 characters?)
I found the rebuttal phase from the reviewer point of view quite useless during the Globecom PC. From the author point of view, the sample is much smaller; it is quite strange that the reviews are provided without the grade, so I'm unable to say if the reviewers liked the paper or not. Obviously they are in between, they don't think it's the best or worst thing ever, but it's hard to decipher if it's leaning one way or the other. I guess it's mostly due to the format of the question, which emphasizes both positive and negative: strength, weakness and detailed (editorial) comments.
I'm not sure how to reply to the reviews, though, not knowing if the job is to not screw it up, or if it's pointless to try to change someone's mind (can a reviewer of an unconvincing paper be turned around in 3,000 characters?)
An Analysis of Packet Sampling in the Frequency Domain
An Analysis of Packet Sampling in the Frequency Domain, Luigi Alfredo Grieco, Chadi Barakat, in Proc. of ACM SIGCOM IMC'09, November 2009, Chicago.
I have been looking with great interest at the technical program for IMC'09 (see here and a few more papers to come). I have to say the stuff from other communities look quite exciting. Grass greener and all.
Anyway, this paper is a very cute (and simple) thing: it considers the Fourier transform of the packet size from a source-destination pair, and assesses a rule for the sampling rate in order to avoid aliasing effects when reconstructing the signal from the Fourier transform.
This is somewhat preliminary and applications to compressing the signal or to use it for anomaly detection are not presented (but hinted at). I would have thought the community of traffic measurement would have done this kind of transforms on the signal a long time ago.
I have been looking with great interest at the technical program for IMC'09 (see here and a few more papers to come). I have to say the stuff from other communities look quite exciting. Grass greener and all.
Anyway, this paper is a very cute (and simple) thing: it considers the Fourier transform of the packet size from a source-destination pair, and assesses a rule for the sampling rate in order to avoid aliasing effects when reconstructing the signal from the Fourier transform.
This is somewhat preliminary and applications to compressing the signal or to use it for anomaly detection are not presented (but hinted at). I would have thought the community of traffic measurement would have done this kind of transforms on the signal a long time ago.
On the Interplay Between Routing and Signal Representation for Compressive Sensing in Wireless Sensor Networks
On the Interplay Between Routing and Signal Representation for Compressive Sensing in Wireless Sensor Networks, Giorgio Quer, Riccardo Masiero, Danilele Munaretto, Michele Rossi, Joerg Widmer, Michele Zorzi.
This paper addresses the same problem as the paper right below. Actually, it's interesting that both papers cite versions each other, which is quite rare.
This paper is a bit more optimistic in the use of compressed sensing in conjunction with routing and data aggregation in sensor networks, but still raises some issues into which random projection would be best for real data (the best results are obtained for synthetic data). It seems there is a trial-and-error phase to see what compressed sensing bring to this problem, with no definite answer thus far.
Disclosure: one of the authors here, Joerg, is my colleague in Munich.
This paper addresses the same problem as the paper right below. Actually, it's interesting that both papers cite versions each other, which is quite rare.
This paper is a bit more optimistic in the use of compressed sensing in conjunction with routing and data aggregation in sensor networks, but still raises some issues into which random projection would be best for real data (the best results are obtained for synthetic data). It seems there is a trial-and-error phase to see what compressed sensing bring to this problem, with no definite answer thus far.
Disclosure: one of the authors here, Joerg, is my colleague in Munich.
Spatially-Localized Compressed Sensing and Routing in Multi-Hop Sensor Networks
Spatially-Localized Compressed Sensing and Routing in Multi-Hop Sensor Networks, Sungwon Lee, Sundeep Pattem, Maheswaran Sathiamoorthy, Bhaskar Krishnamachari, Antonio Ortega in Proc. of the 3rd International Conference on GeoSensor Networks, 2009.
This paper considers the use of compressed sensing with data aggregation in sensor networks. The paper proposes a clustering scheme to compressed the data along the cluster, and reconstruct the data later (either independently within a cluster, or jointly, assuming some spatial correlation between the clusters). The results are not very promising for the approach, once energy costs (for transmission) are taken into account. But there are not too many references using compressed sensing in concert with routing applications.
This paper considers the use of compressed sensing with data aggregation in sensor networks. The paper proposes a clustering scheme to compressed the data along the cluster, and reconstruct the data later (either independently within a cluster, or jointly, assuming some spatial correlation between the clusters). The results are not very promising for the approach, once energy costs (for transmission) are taken into account. But there are not too many references using compressed sensing in concert with routing applications.
Wednesday, October 21, 2009
Space-Code Bloom Filter for Efficient Per-Flow Traffic Measurement
Space-Code Bloom Filter for Efficient Per-Flow Traffic Measurement Abhishek Kumar, Jun (Jim) Xu, Jia Wang, Oliver Spatschek, Li (Erran) Li, in Proc. of the 3rd ACM SIGCOMM conference on Internet Measurement 2003.
The paper uses a bloom filters for counting traffic. It does so by having l Bloom filters (BF), and each time a flow comes in, it chooses one of the l BFs at random. The idea is that, by counting how many different BFs are hit by the request, one can assess an estimate of the number of packets. If the BFs are chosen with equal probability, then after l log(l) packets, all of the l would return a positive reply to a query membership for the packet. Of course, that would restrict the counting to low values, so they don't select the BF uniformly, but at random with a geometric distribution.
If that reminds you of the paper below, it's basically the same idea (the authors were most likely unaware of that paper, since they don't cite it, and don't make use of the theory developed in the Flajolet/Martin paper).
The theory should be a bit more involved than Flajolet/Martin since the BF introduce some noise (false positive) that basically would tend to overestimate a bit the packet count if the F/M analysis was used straight out of the box. So this paper derives another way of inverting the counting from the BFs which, in the simulations, does not skew either over/under but seems to have its error centered around the original value.
Anyway, it seems that this counting using geometric random variables is quite popular a structure.
The paper uses a bloom filters for counting traffic. It does so by having l Bloom filters (BF), and each time a flow comes in, it chooses one of the l BFs at random. The idea is that, by counting how many different BFs are hit by the request, one can assess an estimate of the number of packets. If the BFs are chosen with equal probability, then after l log(l) packets, all of the l would return a positive reply to a query membership for the packet. Of course, that would restrict the counting to low values, so they don't select the BF uniformly, but at random with a geometric distribution.
If that reminds you of the paper below, it's basically the same idea (the authors were most likely unaware of that paper, since they don't cite it, and don't make use of the theory developed in the Flajolet/Martin paper).
The theory should be a bit more involved than Flajolet/Martin since the BF introduce some noise (false positive) that basically would tend to overestimate a bit the packet count if the F/M analysis was used straight out of the box. So this paper derives another way of inverting the counting from the BFs which, in the simulations, does not skew either over/under but seems to have its error centered around the original value.
Anyway, it seems that this counting using geometric random variables is quite popular a structure.
Subscribe to:
Posts (Atom)
