In this thesis, the fundamental experimental observation is that, on the Internet and other networks, traffic seems to concentrate quite heavily on some very small subsets. The main result in here is that this phenomenon is not, in general, related to the popular “heavytailed” phenomenon, but is a consequence of the negative curvature of the network. The mathematical analysis and simulation results confirm this striking traffic pattern specific to negatively curved networks from both the theoretical and practical points of view. Furthermore, this thesis addresses another fundamental question: if congestion does not necessarily occur at vertices with high degree, nor at the so-called highly connected “core,” then what are the congestion points? It is shown that the congestion points are the points relative to which the network has low moment of inertia. That single point relative to which the network has a well-defined minimum is referred to as the centroid, the point through which most of the traffic transits. Probably the most important result as far as protocol design is concerned is that load balancing can be achieved by a routing table designed on the basis of a virtual network in which the link weights have been adjusted to correct the curvature from negative to positive. The latter mathematical technique is reminiscent of the Yamabe flow and the Poincaré conjecture. The practical implementation of this concept on the ns-2 network simulator indicates a significant reduction of the congestion.
|Commitee:||Baryshnikov, Yuliy, Bonahon, Francis, Krishnamachari, Bhaskar|
|School:||University of Southern California|
|School Location:||United States -- California|
|Source:||DAI-B 69/12, Dissertation Abstracts International|
|Subjects:||Systems science, Computer science|
|Keywords:||Coarse geometry, Curvature, Heavy-tail, Load balancing, Network congestion, Network traffic|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be