When Computers Talk, Old Rules Are Silenced
Armed with little more than a stopwatch and a good understanding of statistics, A.K. Erlang went to a small village shortly after the turn of the century and began timing phone calls on the local switchboard. His goal was to figure out which percentage of callers had to wait for an available line.
Out of that simple project came the basis for something called queuing theory and a formula that is still used to help communications companies design their systems to meet the needs of everything from small communities to global networks.
While it still works for voice calls, Erlang’s formula began to crumble with the advent of the fax machine and data communications, including the Internet.
Much to their astonishment, scientists have learned that Erlang’s simple formula--based on the assumption that there is an average length for phone calls and a mean traffic rate--isn’t going to work for anything but voice communications. Instead of the low rumble of the telephone, scientists grappling with Internet traffic have found themselves faced with a Gatling gun.
“Erlang’s formula started to break down when computers started talking to computers,” said Robert Calderbank, vice president for information sciences research at AT&T; Labs in Florham Park, N.J. “When fax machines and computers started using the network instead of just people, the statistics of traffic started to change.”
Calderbank heads an AT&T; research project set up to study how digital traffic flows through the Internet and what role users play in that process. Until they understand that, they don’t have a prayer of designing systems that will meet the needs of the 21st century.
The first discovery was a whopper. Traffic on the World Wide Web comes in bursts, rather than in steady flows, and the same patterns of bursts are repeated regardless of whether the time interval studied is a few seconds long or a millionth of a second.
“It’s a true fractal,” said Walter Willinger, a member of Calderbank’s team. By that he means patterns that repeat themselves, regardless of the time interval. Such “self-similar” patterns have been found throughout nature, giving rise to a new field of mathematics called fractals.
“With fractals you look at a coastline and it looks wiggly, and then you look at a smaller piece of the coastline and it still looks wiggly, and then you look at an even smaller segment, and it’s still wiggly,” Calderbank said. “It looks the same at all distance scales.”
Similarly, the same “bursty” patterns of Web traffic appear over and over again, regardless of whether the time studied is a millisecond or a second.
That “bursty” pattern is one of the chief reasons networks experience those irritating delays familiar to all Web users, Willinger said.
“The network can be filled up in short periods of time during which the user will get very bad performance,” Willinger added. “If you try to go to a Web server and download a document, you might have to wait a couple of seconds or even longer just to get connected. One of the links along the Web server can be so congested for a small period of time that when you try to use it you don’t get any response.”
And those delays will surely increase as traffic on the Internet continues to grow at its explosive rates.
“Once you understand [the bursting effect] you can start dealing with questions like, ‘How can I control it, how can I manage it, what can I do with it?” Willinger said.
But why would digital traffic be that different from voice communications, especially in today’s global networks? Why don’t the peaks and valleys offset each other, since peak demands in Los Angeles are at different times than in London, for example?
The answer, Calderbank said, lies in how we use the Net.
In voice communications, we make short phone calls and long phone calls, and they tend to average out. But differences in the amount of data we ship over the Internet are far more extreme, ranging from very short, such as e-mail, to “incredibly long,” such as sending a portfolio of high-resolution images, Calderbank said.
“So there is a tremendous variability in the length of the sessions” when computers are talking with other computers, he added. That variability is probably six times greater on the Web than with voice calls, he said.
“That accounts for the bursting effect” seen in the studies, he said.
Anna Gilbert has been using “a kind of microscope” to study the level of traffic on AT&T;’s network over the last six years.
“It allows you to zoom in on particular times,” she said. Through a technique called “wavelet decomposition,” Gilbert can break down the packets of digital information at any point in time.
It was by plotting that information that scientists discovered the fractal nature of Internet traffic.
“The bottom line of the self-similar behavior has shown that it is solely due to how users make use of the Web,” Willinger added, because of the extreme variability in the length of sessions.
The researchers said they are not yet clear on why or how that should be the case, and that’s the immediate goal of their work. Network designers want to know precisely what is causing the bursting so they can build better systems for the future. And for that, the researchers are concentrating on analyzing very short periods of time, down to fractions of a millionth of a second.
“It’s a little like analyzing earthquakes in Southern California,” Calderbank said. “Something very interesting happened in a very short period of time, and it’s important to understand exactly what happened in that very small amount of time.”
Lee Dye can be reached via e-mail at leedye@compuserve.com.
