Interesting People mailing list archives
IP: Erlang's Forumla in the Digital Age
From: Dave Farber <farber () cis upenn edu>
Date: Wed, 14 Apr 1999 06:33:20 -0400
We, in the field knew this for a long time, now it is press feed. djf From: The Old Bear <oldbear () arctos com> Subject: Erlang's Forumla in the Digital Age INNOVATION Old rule doesn't apply in new age: Experts find Erlang phone formula fails to explain digital traffic jams by Lee Dye LA Time Syndicate 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, a vice president for 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 said. "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." Those delays will surely increase as traffic on the Internet continues to grow. "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 email, to "incredibly long," such as sending a portfolio of high-resolution images, Calderbank 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. 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 tattle 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."
Current thread:
- IP: Erlang's Forumla in the Digital Age Dave Farber (Apr 14)