News Release
A New Effort to Analyze Interactive Computing on the Internet
 |
|
This image illustrates a scientific "collaboration network," with each line, or edge, representing a joint paper involving two authors. A mathematical description of this network is strikingly similar to one describing information sharing across Internet nodes. Click here for a high-resolution version of this image.
|
Previously, dealing with any complex system in the binary world is usually very difficult," said Graham, a professor in the Jacobs School of Engineering's Department of Computer Science and Engineering and Akamai Professor in Internet Mathematics in the Department of Mathematics. "But now, with our new understanding of the structure of networks, we basically have a new game plan."
The need for such fundamental research has become increasingly apparent as the number of Internet hosts, which grows by more than 50 percent annually, reaches more than 300 million by the end of 2004. "We now have a monstrous amount of data, but how you deal with it cleverly is a huge challenge," said Graham. "For example in bioinformatics, there is a huge biological network for which structure emerges. And every Web page is a node that is related through hyperlinks to a network of billions of other nodes."
Analysis of the Internet as a platform for interactive computing is challenging not because it is decentralized, but also because it continually changes. Knowing the average number of "hops" needed for one Internet node to communicate with another has not usually been required by organizations involved in interactive computing. But many organizations are painfully aware that latency and reliability, and in some cases survival, can be affected by the path of interactive computations.
The ITR grant to Graham is one of six totaling more than $9 million to UCSD faculty in 2004, the fifth and final year of the ITR program, which has committed a total of more than $1 billion to innovative, high-payoff research and education. (To read about all six ITR grants involving UCSD faculty as principal or co-principal investigators, click here.)
Graham, principal investigator of the interactive computing project, and Princeton University computer science Professor Andrew C. Yao, co-principal investigator, will take advantage of relatively succinct mathematical descriptions of the structure of the Internet, first derived in 1999, to rigorously analyze interactive computing. They will study major, open problems in communication complexity, information theory, quantum information processing, and the analysis of online algorithms.
Networked computers continually share information with one another, and users become aware of reliability issues only when systems fail. One of the most challenging problems that Graham and Yao will address is how to analyze networks that are changing dynamically while relying only on partial information. They hope to effectively model complex behaviors in a variety of ways, such as exploiting the discovery that realistic networks have power law degree distributions.
For example, when the size distribution of Internet nodes is graphed, it is immediately apparent that the vast majority of them are about the size of personal homepages and only a few are as big as CNN. In mathematical terms, the number of nodes of size K is proportional to 1 divided by K raised to the 2.1 power. Such power laws, which have been used to describe everything from social and biological networks, are proving to be invaluable in the analysis of the Internet. "With these power law descriptions, we are now able to do more quantitative analysis than we ever have before," said Graham. "It's like nature finally gives us a break."
Since realistic networks grow and contract, Graham and Yao will consider online models that combine deletion and attachment steps. By adding new nodes and new edges, with their respective probabilities, they will generate power law graphs with exponents between 2 and 3.
A project summary is at www.math.ucsd.edu/~fan/.
Note to editors: A high-resolution illustration of a modeled network described by Graham is available upon request.
Media Contacts
Rex Graham
Jacobs School of Engineering
858-822-3075
rgraham@soe.ucsd.edu