There's a new article on up at Notices of the AMS entitled Mathematics and the Internet: A Source of Enormous Confusion and Great Potential, by Willinger, Alderson, and Doyle.
It's an interesting read, although I've heard some of the main points in talking with them before. In terms of specific examples of how problems in the modeling of the Internet arose, my take on their take of the history is that the trouble started with the well-known Faloutsos^3 paper (On Power-Law Relationships on the Internet Topology), which first appeared in SIGCOMM 1999, and which claimed that the degree distribution of the Internet's router-level topology followed a power law. It has been argued that there are a number of flaws with this paper, most notably in the underlying data, as described in this article, making their conclusions on the power-law relationship unreliable. (Given my recent posts and corresponding discussions on the SIGCOMM PC meeting, it's interesting to reflect on the importance this paper has played after being published in SIGCOMM.) The second part of this troublesome history is the subsequent work of Barabasi and Albert, who leveraged this result to help proclaim that the underlying mechanism of the Internet topology is preferential attachment, explaining this power law behavior. The authors discuss how this claim was made without sufficient validation, and argue that there are other optimization-based models that much better explain the guiding mechanisms behind the Internet topology, based on actual Internet engineering.
To start, I should admit not-so-humbly that I think the authors could have mentioned my very-relevant survey and editorial on these issues (the editorial, in particular, discusses the validation issue in this context). But leaving that aside, it's an interesting read with many possible lessons to draw or questions to think about. Are we insufficiently critical at early stages (e.g., conference publications), so that once a result is accepted, it becomes difficult to point out where it may be flawed? How do we deal with "noisy" network data in analysis? Are we getting to the point where only teams from Microsoft, Google, Akamai or AT&T (or some other big company) can publish in certain areas of networking because they're the only ones that can get good enough data? What are the useful ways mathematicians can contribute to the study of networking topology (yet another power law model does not seem to be compelling)?
I have to admit, I have a side worry with this appearing in the AMS. Given how it sometimes appears that mathematicians view computer scientists, I worry that this article will reinforce the belief in the minds of some mathematicians that computer science is "non-serious" or "non-rigorous", which clearly wasn't the intention of the authors. The problem of explaining the history of "enormous confusion" and "great potential" is the risk that too many readers will focus on the former rather than the latter.
Subscribe to:
Post Comments (Atom)
8 comments:
Michael Mitzenmacher wrote:
I have to admit, I have a side worry with this appearing in the AMS. Given how it sometimes appears that mathematicians view computer scientists, I worry that this article will reinforce the belief in the minds of some mathematicians that computer science is "non-serious" or "non-rigorous",....I think TCS today has a serious/rigorous mathematical aspect, as well as a technology driven non-serious/non-rigorous aspect. In the long run, it is quite plausible that the mathematical parts of TCS would be absorbed by mathematics departments (in which it fits scientifically and culturally), and the non-rigorous parts would find their home in more engineering-oriented Computer Science and Engineering (as well as Computer and Electrical Engineering and similar) departments.
There is an analogy here between where TCS is today and the subject of Probability and Statistics. Fifty years ago (Kolmogorov notwithstanding) few people would have considered it as a branch of mathematics. Fifty years and a couple of Fields medal and an Abel prize later, the mathematical aspects of the subject can be considered to be well represented inside most mathematics departments, while the more applied/data-driven parts are scattered in other departments (such as Statistics, Bio-statistics, Finance, Operations Research etc.) where they fit in more naturally.
Once such a split occurs in TCS, this continuous tension between rigorous/non-rigorous TCS (as exemplified by the Koblitz article a while back) would disappear and we will all rest easy.
Having worked in Internet topology discovery, I have to say I believe the work is closer to natural science than mathematics: one attempts to understand the system based on necessarily incomplete observations.
In my mind, computer science is not pure mathematics, pure engineering, or pure science, but instead a composite of the three. While different sub-fields tend towards one extreme or another, IMHO, the most interesting work touches on all three elements.
I read this paper not as a potential slur on the rigor of computer science, but rather a call for theorist to get their hands a little dirty, experimentalists to formalize their assumptions, and maybe for the two groups to meet somewhere in the middle.
I agree with Rob Sherwood. In matters involving Internet architecture and infrastructure, it's necessary to acquire a fair amount of background and experience before making conjectures.
As for mathematicians getting good enough data to do networking research, computer scientists don't necessarily get access to that data either (unless they work at one of the companies you stated, and then, they only get their data). This is a common complaint among network researchers, engineers, etc. But you could try getting involved with some of the IETF and IRTF working groups where these issues are studied.
The article is remarkable for its polemic tone and name-dropping fatuity. A paraphrased quote from Ulam is referred to twice: “…a reminder of a telling comment attributed to S. Ulam (slightly paraphrased, though), who said ‘Ask not what mathematics can do for [the Internet]; as what [the Internet] can do for mathematics.’” The first occurrence of the paraphrase of Ulam paraphrasing John F. Kennedy was bad enough; the self-congratulatory second occurrence is risible: “Multiscale representations of networks is an area where Ulam’s paraphrased quote is highly appropriate.” Much of the article is consumed with invidious comparisons of scale-free, preferential attachment network models of the internet with the authors’ own HOT (”highly organized/optimized tolerances/tradeoffs”) models: “In view of such a simple physical explanation of the origins of node degree variability in the Internet’s router-level topology, Stogartz’ question, paraphrasing Shakespeare’s Macbeth, ‘…power law scaling, full of sound and fury, signifying nothing?’ has a resounding affirmative answer.” The authors seem to suggest by this precious literary reference that a scale-invariant model of the Internet is a “tale told by an idiot.”
Its authors spare no opportunity to criticize their competition, as well as mathematicians and physicists generally, whom they regard as foppish, insular ivory tower aesthetes, whose nostrils are unacquainted with the bracing scent of an expertly soldered electrical connection.
The authors’ case against scale-invariant network models seems to proceed by gratuitous, autistic repetition. The section on the “Scale-Free Internet Myth” begins with a general statement whose pejorative adjectives make it unverifiable in-principle : the alleged “scale-free nature of the internet…has remained a constant source of enormous confusion within the scientific community.” The statement appears to lack substantive sociological content. In case Internet researchers had hoped to latch on to some secondary aspect of scale-invariant network models, the authors write, “What about power-law node distributions?…Recognizing their irrelevance is clearly the beginning of the end of scale-free network models of the PA [preferential attachment] type, as far as the Internet is concerned.” Later, in case the futility of modeling the Internet with scale-invariant networks was lost on us, they write, “given the specious nature of scale free networks of the PA-type for modeling Internet related connectivity structures… .” In marked contrast, the authors suggest that their own HOT models of Internet connectivity will be more mathematically interesting “… and certainly more relevant and hence more rewarding than that of the scale-free models of the PA type.” In the section on the need for a mathematical theory of internet connectivity of use to engineers, the authors caution against the use “..models like the scale-free network models of the PA type that ignore any particulars of the underlying system.” In the section on network dynamics, the authors state that “…currently proposed network models such as the scale-free models of PA type cannot account for such interactions.”
For the authors, the phrase “scale-free network models of the PA type” has the effect of uttering “Niagra Falls” in an Abbot and Costello sketch.
It may be that their toy HOT models of the Internet are superior to scale-free, preferential attachment network models. Unfortunately, the authors seem incapable of formulating a tempered, scientific claim without trashing prior research. One senses that the authors were deeply wounded by proponents of scale-free, preferential attachment networks. Perhaps the publication of this contemptuous, condescending article in the Notices of the American Mathematical Society was cathartic for them.
The authors propose the use of linear programming (the only mathematics to appear in the article) to understand network traffic analysis. They conclude that power-law node-degree distributions cannot arise in linear programming models of network traffic analysis, because the authors only see simple objective functions, matrices and systems of inequalities in these models. Ordinarily one would have to prove that no such connection exists, but this does not stop the authors from concluding that if they do not see a mathematical connection, that it does not exist. A similar logical failure affects their critique of data collection techniques. The authors fail to show that errors introduced by the traceroute network utility are sufficient to falsify the conclusion that the Internet is scale invariant. If the Internet is not scale invariant, this is not because of methodological problems with data collection. The authors are so dismissive of any attempt to measure what they claim one would want to measure, that one wonders how they could possibly demonstrate or refute any measurable properties of the Internet whatsoever.
Anonymous 4,5, and 6 (who I assume are the same person): You seem to be falling into the pattern you're accusing the authors of -- attacks on what they wrote not based on logic, scientific evidence, or factual argument, but based on how they are arguing.
If you want to discuss the science, I'd suggest you start with the authors' articles on the subject, such as references [33] and [34].
Consider the authors' PNAS article The "Robust Yet Fragile Nature" of the Internet [PNAS October 11 2005, vol. 102, no. 41, pp 14497–14502]. I have been unable to locate this citation in the bibliography of the AMS Notices article. Table 1 of this PNAS article shows that with the exception of node degree distribution, scale-free and HOT networks have the opposite properties, and that HOT networks are closer to the Internet than scale-free networks. In the case of node degree distribution, scale-free networks and HOT networks predict power law node degree distributions.
They write, "...Table 1 shows that SFnet and HOTnet are opposite in essentially every meaningful sense."
For the authors, the one sense in which the two models agree, namely power-law node degree distributions, is not "essentially meaningful."
Let's compare this with the AMS Notices article.
"What about power law node degree distributions? They clearly are a non-issue in this engineering-based, first-principles approach, just as they should be, based on our observation earlier that present measurement techniques are incapable of supporting them."
This statement does not rule out the possibility that improved future measurement techniques may support power law node degree distributions. Their own HOT models support them, as indicated by their Table 1. If present measurement techniques are incapable of supporting power law node degree distributions, the models may nevertheless predict this phenomenon. Verification, in that case, would have to await more accurate measurement techniques.
It is misleading not to mention that power law node distributions arose in their own HOT models as documented in their PNAS 2005 article. This can be stated without minimizing the evident superiority of the HOT models. But the authors seem determined to deny that power law node degree distributions play any role whatsoever.
"Recognizing their irrelevance is clearly the beginning of the end of the scale-free network models of the PA [preferential attachment type], as far as the Internet is concerned."
Why are they irrelevant if they arose in the authors' HOT models, as documented in their 2005 PNAS article? Wouldn't this act of recognition similarly invalidate their own HOT models, if these predict power law node degree distributions, as their own paper indicates? Is there no duty to admit that some of the HOT models predict power law node degree distributions, but those models must be rejected in favor of HOT models that predict highly variable node degree distributions?
"What about replacing power-laws by the somewhat more plausible assumption of high variability in node degrees? While the answer of the scale-free modeling approach consists of tweaks to the PA mechanism... the engineering-based approach demystifies high-variability in node degrees altogether by identifying its root cause... . In view of such a simple physical explanation of the origins of node degree variability in the Internet’s router-level topology, Strogatz’ question, paraphrasing Shakespeare’s Macbeth, “... power-law scaling, full of sound and fury, signifying nothing?” [52] has a resounding affirmative answer."
Following the reference to Shakespeare, a model of the internet which predicts node degree power law scaling is a "tale told by an idiot." According to their PNAS article, their own HOT models predict this. Do the authors have no obligation to the readers of their AMS Notices survey article to document and explain this discrepancy? A more tempered statement than the emphatic and even insulting dismissal of power law node degree distributions is warranted, given that the uncited 2005 paper shows agreement between HOT models and scale-free models on this point. At least the PNAS 2005 article recognizes that both the scale-free and HOT models differ from the Internet over node degree distribution.
Post a Comment