Adding Definition to Active Probing

By: 
Sridhar Machiraju, Darryl Veitch, François Baccelli, and Jean C. Bolot
Appears in: 
CCR April 2007

Active probing techniques have overwhelmingly been based on a few key heuristics. To progress to the next level a more powerful approach is needed, which is capable of filtering noise effectively, designing (and defining) optimal probing strategies, and understanding fundamental limitations. We provide a probabilistic, queueing-theoretic treatment that contributes to this program in the single hop case. We provide an exact inversion method for cross traffic distributions, rigorous system identifiability results to help determine what active probing can and can’t achieve, a new approach for treating queueing theoretic ‘noise’ based on conditioning, and cross traffic estimators with enhanced properties.

Public Review By: 
Constantine Dovrolis

As an active worker in active probing and available bandwidth estimation I am excited whenever I see papers that provide a deeper, probabilistic understanding of this very interesting, and important in practice, research area. This is one of these papers, and I would not hesitate to rank it as one of the best I have read so far. It focuses on the hardest problem, in my opinion, in active probing: how to estimate the distribution of cross traffic from end-to-end measurements.
Before we get too excited though, note that the paper studies a single-hop model. The extension to a multi-hop path, which may or may not be feasible, is left for future work. The reader should note that estimating the cross traffic distribution is much harder than estimating the average available bandwidth. Even though the latter has received much attention in the last five years, the former has only been studied in a Sigmetrics’05 paper that we wrote with M. Jain (“End-to-end estimation of the available bandwidth variation range”), to the extent of my knowledge.
Talking about related work that the authors have missed, I suggest that the interested reader also looks at the Infocom’06 paper by P. Haga et al. (“Understanding packet pair separation beyond the fluid model: the key role of traffic granularity”), and an older paper by V. Sharma and R. Mazumdar published in the Performance Evaluation Journal in 1998 (“Estimating traffic parameters in queueing systems with local information'”). Also, a “must-read'” in this area are the two papers published by X. Liu et al. in the IMC’04 and ’05 conference (references [9] and [10] in the paper). Those papers show both the benefits of packet-train probing, as the train length increases, and also the additional challenges that multi-hop paths present.
One of the points I do not agree with in this paper is the description of the previous work in the area of available bandwidth estimation as “heuristic.” At least according to the Merriam-Webster dictionary, a heuristic is only based on experimental or trial-and-error methods. Most of the available bandwidth estimation papers I am familiar with are based on a mathematical analysis of the fluid-traffic model (see the Sigcomm’02 paper that we co-authored with M.Jain, for instance). The fluid-traffic model is very simple, of course, and it does not capture salient characteristics of real Internet traffic. The same argument, however, to a different degree, applies to all traffic models. The two key assumptions stated in Section 3 of this paper are also not as “innocent” as they sound at first, as I will explain in the next paragraph. So, in my opinion, the difference with previous work is that this paper is based on a certain probabilistic model of the traffic, which is more realistic than the fluid-traffic model but probably still incorrect, and not that this is the first rigorous method proposed in this area. Also, as two of the reviewers point out, the two key assumptions that the paper makes (see Section-3) are described as just “technical,” but they do play a major role in the analysis, they are not sufficiently validated, and they are probably not true in practice. Specifically, the independence assumption for the variable R_n is examined just for a single OC-3 trace in Section 6-1, and as one of the reviewers point out, this assumption may not hold when the cross traffic is correlated in the measurement time scale, or when the cross traffic is responsive to congestion (e.g. TCP). The second assumption, namely that {R_n} forms an ergodic Markov chain is also fairly strong, and the conditions under which it holds are not investigated at all.
The rather negative previous comments should not dilute the main message of this public review, which is that this paper provides a deeper understanding of what we can, and what we cannot, infer about cross traffic using active probing. It may also lead to more accurate estimation methods/tools than what we already have, but that part remains to be seen.