03/08/95
CONTACT: Stanford University News Service (650) 723-2558
STANFORD -- Take the average number of vehicles on any Los Angeles freeway during Friday evening rush hour, multiply it by a million, and you still won't come close to the digital traffic that moves each second on the information superhighway.
Imagine having new exits appear - and old ones disappear - on a daily basis, and detours greeting you every 50 yards. The infrastructure of the Internet is similarly changing and growing at an explosive speed.
A person doesn't expect to take Highway 101 to San Francisco today, and then tomorrow discover both 101 and 280 closed, said Serge Plotkin, assistant professor of computer science at Stanford University. But a situation like that frequently can happen on the Internet. Meanwhile, a third “highway” twice the size of 101 may open up. In another 24 hours, he said, all three routes may be operating at the same time.
Plotkin, 34, is what one might call the theoretician behind the cybertraffic engineer. Plotkin is researching how best to manage the flow of information through computer networks without causing system overload - essentially an on-line gridlock. He was recently granted one of Stanford's first Terman Fellowships, an award to support the research of junior faculty in engineering and science.
Today, there are millions of computer users who interact with each other through the Internet. There are even more who communicate via the "old-fashioned" telephone. Whether it be a computer line, telephone line or even a cable television line, currently there is no one vehicle through which different types of information such as video, data or voice can all be transmitted. A movie on cable, for example, cannot be transmitted over a telephone line.
A new technology is being developed to encompass the various media so that different digital data all will be compatible with each other, Plotkin said. This technology is called asynchronous transfer mode (ATM).
"I would say it's not a very revealing name," he said. "But it is what one would call backbone technology; it does not define why, but how we transmit information." This concept in itself may not spark the interest of the average computer user. However, the ATM Forum, a consortium of government agencies and corporations, are supporting a universal standard that will overcome current restrictions on different types of information. Long-distance telephone companies are especially keen. Their interest means that asynchronous transfer mode technology will most likely become the de facto communication standard of the future, Plotkin said. His own research is currently being funded by the National Science Foundation and the Army Research Office.
A network operating with this technology will have thousands of switches in various locations moving information around. Switches can simply be imagined as boxes that take an input stream of data, "switch" it - some are sent to the left, some to the right - and forward the information on its way. This stream of data, or cell (a basic unit of transmission), carries "administrative" information that will allow a switch to determine which way the cell should go. In this way, a document can tell a switch it needs to go to Boston, for example.
Individual home users will be connected to these local switches by twisted-pair cable, similar to telephone wire. Switches will be connected to each other with high-capacity fiber-optic cable.
Routing information through networks is one of the main problems that Plotkin is working on. Let's say there are switches in New York, Los Angeles, Chicago, San Francisco and Hawaii, he said, standing up to draw a colorful diagram on his worn whiteboard. (In reality, there will of course be many more switches per city.) If a user in San Francisco wants to talk to someone in New York, should the information go through Chicago or Los Angeles?
"If everything goes through L.A., you're going to overload that part of the system, and local customers are going to suffer,” he said.
When this occurs, some information may have to be re- routed through a different switch. Since bytes travel at very high speeds, however, many bytes are sent before the first one ever reaches its destination, and when some are re-routed, the user will probably lose information.
“The delay going from San Francisco to New York through Chicago is not equal to the delay going through L.A.,” Plotkin said. "Therefore, you have to deal with synchronization."
Plotkin is trying to eliminate, or at least minimize, re- routing and come up with routing strategies that will work reasonably well. He said that the current standards do not suggest re-routing strategies due to the cost and complexities involved.
The key question, therefore, is determining how much increase in transmission capacity can be achieved for the same proportional number of rejected requests, or “busy" signals. To return to the pipe metaphor, Plotkin is trying to increase the volume of water that can flow through pipes of certain size from here to San Francisco, by sending some water through one pipe and the rest through another.
Any transmission, be it video, data or a telephone call, is first broken down into basic units called cells. Those cells associated with the same transmission follow the same route. The shortest and apparently most efficient route, as shown on the network simulation drawing, would be to have any call from A to D go through the B and C switches on an ABCD path.
But as the grey line on the graph shows, relatively soon users begin to receive "busy signals" as switches B and C get overloaded. The potential for gridlock is high because all information will be taking the same route. Using an alternative like AEFCD might lead to better efficiency, even though the route is longer. The difficulty is knowing when to make that alternative decision, and which alternative route to choose.
The dotted line to the right of the graph represents the theoretical physical limitations of the network, assuming that the best routing choices could be made all the time. The solid line represents the results of a decision-making strategy developed by Plotkin's group.
"The problem," Plotkin said, "is that in real networks, there are so many alternatives to the ABCD path. The question is, what alternative should we use and when should we start using it? The main point of my research is that you shouldn't wait until switch B is dead from overload. My work is searching for mathematically sound ways of making the decision to start using a new path even before the old one is overloaded."
Plotkin is currently working together with Ram Ramakrishnan of AT&T to design strategies specifically for their future switches. The long-distance telephone company has given him several possible network topologies - who is connected to whom, how many customers, perceived type of usage - and Plotkin and his students are trying to adjust their strategies to work as well as possible under those specific constraints.
Students and former students who have contributed to this research include Anil Kamath and Omri Palmon, both doctoral candidates in computer science; former student Orli Waarts, now a postdoctoral student at the University of California-Berkeley; and Rainer Gawlick, a doctoral student at the Massachusetts Institute of Technology.
The result of their work should be to expand the capacity of the global computer network. Future networks will support various types of multimedia applications, including teleconferencing and video-on-demand, Plotkin said. Teleconferencing will allow a user in Ohio, for example, to participate in a live lecture transmitted from Stanford. Video-on-demand will be a sophisticated on-line pay-per-view service, in which a person sitting in his living room can "demand" any movie he wants without needing to know what will be offered on which channel at what time.
Today's technology is very limiting in terms of capacity, and will not allow the implementation of these applications because they require immense resources. A 100-page document may take up to one-half megabyte of information. For a home user who requests video-on-demand, however, one-half megabyte will correspond to only a couple of seconds of a two-hour movie.
"Each session of such video-on-demand will take more and more resources, and at some point, the resources are going to run out," Plotkin said.
The problem, therefore, lies in managing the resources of a network such that communication links will not be overloaded with information. "What type of resources, among many, am I talking about?" Plotkin said. "Bandwidth."
Bandwidth refers to a physical limitation - dependent on type of hardware and communication link - on the amount of information that can be transmitted through a certain link. To return to the pipe metaphor, a pipe can carry only so much water. The volume will depend on the diameter of the pipe.
"So I send a message to this PC," he said, pointing to his wide-screen monitor, "and it propagates through some link, and it comes out [in San Francisco]. What is the maximum number of bytes I can send that will still go through?"
It is difficult to figure out how much transmission capacity these future computer links must be designed for without knowing exactly what kind of services will be offered and how much capacity each will require. In addition, consumer usage patterns of the future cannot be predicted because there are no previous data to rely on. Therefore, both the absolute transmission capacity of links and the market or consumer need for such capacity have to be considered. Some users may want a clean connection with no “noise,” while others may be willing to get some noise for a cheaper rate. And what if all links are full? Should companies start designing "busy" signals? If users do get a busy signal, how long will they have to wait to get their movie?
“We have to design strategies that do not rely on our knowledge of the future,” Plotkin said. Like looking for a needle in a haystack, he is trying to find the optimal solution to a problem with many different variable combinations. The trick is to invent shortcuts that will allow him to skip looking at some of these possible solutions.
This article was written by Jee-Young Shin, a science writing intern at Stanford News Service.
-jb-
950308Arc5336.html
This is an archived release.
This release is not available in any other form.
Images mentioned in this release are not available online.
Stanford News Service has an extensive library of images,
some of which may be available to you online.
Direct your request by EMail to newslibrary@stanford.edu.