NetSE: Small: Load Balancing by Network Curvature Control

University Of Southern California, Los Angeles CA

Investigators

Abstract

This project explores the interplay between the topology/geometry of networks and their traffic load pattern with the ultimate objective of deriving new load-balancing algorithms based on curvature control. The phenomenon that is observed in reality is the strong concentration of the traffic on some small subsets of links/nodes. This can be seen in the Internet (?backbone?), in the power grid (?line overload?), in vehicular traffic, in metabolic exchange in living organisms, etc. This phenomenon?the emergence of the centroid?cannot be completely accounted for by the local heavy-tailed paradigm, but strong evidence is provided here that this is a general feature dictated by the large-scale hyperbolic structure of the underlying network. Here, hyperbolic is a metaphor to refer to the fact that such networks as the Internet Service Provider (ISP) behave like negatively curved Riemannian manifolds, of which the saddle is the most intuitive visualization. Behavior refers to the geodesic flow, which carries the traffic and controls its stability or instability (e.g., fluttering) under such perturbation as outage or power depletion. The first part of the proposed research will be devoted to refining criteria for real networks to be identifiable with negatively curved Riemannian manifolds. After developing intuitive criteria based on angle deficit/excess and clustering coefficient, the Gromov Thin Triangle Condition (TTC) and Four-Point Condition (FPC) will be scaled by the size of the graph to become relevant to real networks, which, no matter how awesome their sizes, are nevertheless finite. This leads to the new concept of scale-specific Gromov hyperbolic graphs, of which the Rocketfuel data base already provides an example. Such real-life networks as those provided by Bell Labs, sensor networks, air traffic control, even metabolic and nervous system networks will be used as testbeds. Next, the first step towards congestion analysis is the development of a network-specific concept of centroid or center of mass, already known in the mathematical community in its Riemannian manifold version. While in simulation the centroid has appeared to coincide with the point of maximum traffic, an important research milestone will be the theoretical justification of this fact. At the other end of the curvature spectrum, there is strong evidence that traffic on uniformly positively curved networks is balanced, provided the Dijkstra routing algorithm incorporates a randomization of the equal cost paths. The preceding leads to the culmination of the research: by reassigning link weights so that the resulting network is positively curved, the routing based on the modified network would balance the load. Provided that the Euler characteristic of the network reveals no obstructions, the reassignment is carried over by the so-called Yamabe flow algorithm, which has a decentralized structure and hence would mesh with such network algorithms as flooding. Finally, the algorithm will be given an adaptive control structure, meaning that once it reaches positive curvature, it will continuously update the link weights as necessitated by network outages, flash points, etc. The intellectual merit of the proposed research is that it will take coarse geometry?which has over the past few years silently pervaded such diverse fields as wired and wireless networks, autonomous agents, cooperative control, even biochemistry?along its scale-specific reformulation relevant to complex real-life networks, which do not quite fit the mathematical idealization of Gromov hyperbolic graphs. Certainly, the most transformative part of the research is the load-balancing based on routing on a modified positively curved network. The latter will bring to the real world such curvature smoothing algorithms as the Yamabe flow, which was instrumental in the proof of one of the most celebrated mathematical puzzles of all times?the Poincar´e conjecture. The broader impact of the proposed activity is that it will foster a well-focused, application-driven multidisciplinary collaboration between the Department of Electrical Engineering, the Computer Engineering group, and the most theoretical geometry/topology group of the Department of Mathematics. Joint seminars, group meetings, new course development, etc. will create a new breed of engineering students, knowledgeable in coarse geometry, which has so far not been part of the traditional engineering curriculum. Extensive collaboration with Bell Labs will be maintained throughout the project