With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
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.
Advisor: | Jonckheere, Edmond |
Commitee: | Baryshnikov, Yuliy, Bonahon, Francis, Krishnamachari, Bhaskar |
School: | University of Southern California |
Department: | Electrical Engineering |
School Location: | United States -- California |
Source: | DAI-B 69/12, Dissertation Abstracts International |
Source Type: | DISSERTATION |
Subjects: | Systems science, Computer science |
Keywords: | Coarse geometry, Curvature, Heavy-tail, Load balancing, Network congestion, Network traffic |
Publication Number: | 3341712 |
ISBN: | 978-0-549-97348-5 |