by
Abstract
The Internet has a life of its own. Traffic on the net exhibits many biological traits, according to those who create mathematical models of Internet behavior.
Degeneration and death were popular topics as the American Association for the Advancement of Science began its annual meeting in Anaheim, California, held January 21-26, 1999. On the first morning, a session about apoptosis was overflowing, while just down the corridor a concurrent session about explosive growth, ironically, had a comfortable amount of elbow room. The topic was not cancer cells but Internet behavior.
Perhaps people chose to skip the session called "Internet Research as an Experimental Science" because they thought it was all about mathematics, and would therefore be complicated. They would have been surprised.
Vern Paxson of Lawrence Berkeley Laboratories may be partly at fault. He had titled his talk "Why Understanding Anything About the Internet is Painfully Hard." The reward for sitting through the session was an astounding idea: Modeling Internet behavior requires a new mathematics, the same kind of complex formulas that can sometimes model the phenomena of nature.
What makes the Internet's behavior really hard to understand, said Paxson, is that it's a complex system, like a living organism or a natural ecosystem. "It's an immense moving target," he explained. "Things change all the time."
In January 1990, he said, there were only 200,000 Internet hosts. A year ago, there were 30 million. Today there are 43 million. "If you blink," read the slide he was showing at that moment, "you're out of date."
At his own workplace, Lawrence Berkeley Labs, World Wide Web traffic has doubled every six weeks since 1994. "We didn't anticipate that growth," Paxson said. "Even the dreamers didn't anticipate that growth." Nor did they anticipate the unpredictable nature of the traffic patterns.
Internet traffic has proved frustratingly resistant to modeling for such interesting purposes as trying to predict whether we have the infrastructure to accommodate its continuing growth. To model its behavior, mathematicians first turned to the tool that had proven useful for modeling the best analogy they could think of: the telephone system. This tool - Poisson theory, a classic branch of probability theory expounded by French mathematician Simeon Denis-Baron Poisson in 1837 - has proved catastrophically inappropriate.
Paxson flashed on the screen a slide of an hour-long trace of connections from the Digital Equipment Corporation (now Compaq) to the Internet in 1994. Used to predict the pattern of Internet traffic across various units of time with Poisson modeling, it generated a six-second unit of Internet traffic that showed a "peaky" pattern (as Paxson described it, looking at the slide). A ten-minute predicted pattern was "bumpy," and a one-hour tracing looked "smooth."
But prediction did not match reality. At the smallest scale, the actual traffic data during that period did look like the model. But at longer time scales, Paxson said, "the 'burstiness' does not go away. The character of it is not changed at all. If you delete the x-axis, you couldn't tell at all [what time scale you're seeing]. This is a real problem for the Poisson model."
The pattern Paxson described fits nicely with the much newer concept of fractal geometry - a strange but beautiful mathematics of fractional dimensions, non-standard sizes, and, as the next speaker described it, "self-symmetry."
"Just as a biologist examines slides under a microscope," AT&T mathematician Anna Gilbert had written in the abstract of her presentation, "an Internet researcher explores data with a mathematical microscope, looking for hidden structure and pervasive features at different levels within the data." Her own talk focused on the similarity between Internet behavior and fractal mathematics - not to mention even newer concepts that derive from the newfound relationship between the two.
Coastlines look the same no matter what scale you use to observe them, whether one meter or 10 kilometers, said Gilbert, explaining the property of self-symmetry. Water levels in flood plains show the same behavior when measured by time series analysis. The pattern looks the same at all scales; it doesn't "smooth out" as you take a larger view.
Beyond Poisson and even beyond fractals, Anna Gilbert said, "investigating [Internet] traffic measurements has led to a new mathematics of multifractals, new statistical tools for analyzing the data." She proceeded with an account of how she can represent Internet behavior (the time and frequency in which packets pass a particular point) in ways analogous to musical score (in which time and frequency are also represented). She had demonstrated how she can "measure the geometric wierdness of a set where all the points share the same spikiness." Her descriptions of excursions beyond fractals were fascinating, but opaque; the audience had no questions.
Fractals and their theoretical descendants have succeeded as models for the behavior of the Internet - where the Poisson model failed - because the telephone system is not a good analogy. When you make a phone call, you occupy one dedicated line until you hang up; delivery is immediate and direct. The Internet acts more like a package delivery service. It picks up a very large number of packages and delivers them from "node" to "node" until they all reach their destinations. The packages can travel over any route, and can arrive out of order. Further, some go through one main post office, but others go through different routing centers. Also like the postal service, the Internet slows down when demand gets heavy (think about Christmas). When demand gets too heavy, the Internet simply throws excess parcels away.
In 1993, a paper by the session's chairman, Walter Willinger of AT&T, proposed that one could describe this kind of traffic as a fractal. "This was a bombshell," Paxson said. "It electrified the community." But it was clearly the right idea, he added. By now there is "very strong empirical evidence" that the behavior of human populations as they log on to and use the Web fits a fractal pattern.
Another speaker at the session presented such evidence. In Japan, Misako Takayasu of Keio University has found a way to measure the passage of Internet packets traveling to and from Tokyo. Measuring from a packet's origin to the first node it passes, she said, its behavior is very "Poisson-like," but somewhere between the fourth and seventh junction it becomes ever more fractal-like.
Takayasu's team has been trying to understand what happens when the junctions are so jammed that the system begins to throw packets away. The analogy she chose for Internet traffic was infectious disease. Her slide showed a rank of schoolchildren sitting at desks.
If you ignore the immune system, she said, Internet traffic behaves very like an infectious disease viewed from the vantage point of the organism. Infection and recovery rates are dependent on interactions between neighbors and on the distance between them; so are the recovery rates of overcrowded Internet nodes (called routers). An infection can overburden and eradicate a host; on the other hand, a host can also recover. So can a router.
"This is one of the simplest trivial stochastic models," Takayasu said. "Many models having different evolution properties converge to the contact model." (In her abstract, she also used the term "evolve" to describe the future of the Internet.)
Going beyond modeling, Takayasu's team used the Internet as an experimental organism, sending packets to and from the most congested points, predicting what would happen at times of high congestion and measuring the actual behavior of the packets. Curiously, like the overworked executive who functions best under pressure, "the network can transport packets most efficiently at the critical point between congestion and the non-congestion phase," she said (making yet another analogy, to phase transition in physical chemistry.) "If we can control to the critical point," she predicted, "we can make it an efficient system."
Will the Internet get so crowded it eventually breaks down? someone asked Paxson during the discussion. Everyone's crystal ball fails about two years out, he responded, but he went on: "The network has basic mechanisms within itself to avert a collapse. . . . The system is very elastic."
The Internet might never have survived at all, added the final speaker, Deborah Estrin of the University of Southern California, if it had been built as a rigid and stable steady-state entity. "Robustness," she concluded, "is the ability to continue to operate in the existence of continual component change."
Sound familiar? Mathematicians may not yet understand the Internet's behavior, but biologists can certainly recognize some of its qualities.
Lois Wingerson is editor in chief of HMS Beagle.
Caleb Brown is an illustrator and biologist living in Montana. By day he drives a delivery van, and by night he draws pictures with his computer.
Collaborative Advanced Internet Research Network - test bed for advanced computer network protocols research and development. Strictly for the network-savvy.
Internet Monitoring - sites that track Internet traffic.
Cooperative Association for Internet Data Analysis - tools and other resources to monitor, predict, and analyze Internet traffic behavior on current and advanced networks.
National Laboratory for Applied Network Research - technical, engineering, and traffic analysis support of NSF high-performance connections sites and network service providers.
National Coordination Office for Computing, Information, and Communications - an overview of federal government research activities including President Clinton's initiative, "Information Technology for the Twenty-First Century."
Association for Computing Machinery - a wealth of publications, conferences, and resource archives related to information technology.
The Fractory - interactive tool for exploring and creating fractals.