NetSE: Small: Load Balancing by Network Curvature Control

这个项目探讨了网络的拓扑/几何结构与其流量负载模式之间的相互作用，最终目标是基于曲率控制导出新的负载平衡算法。在现实中观察到的现象是流量强烈集中在一些小的链路/节点子集上。这可以在互联网上看到（？骨干？），在电网（？线路过载？），在交通工具中，在生物体中的代谢交换中，等等。这种现象？质心的出现不能完全占本地重尾范式，但强有力的证据是，这是一个普遍的特点，由大规模的双曲线结构的基础网络。在这里，双曲是一个比喻，指的是这样一个事实，即互联网服务提供商（ISP）这样的网络表现得像负弯曲的黎曼流形，其中鞍是最直观的可视化。行为是指测地线流，它承载流量并控制其稳定性或不稳定性（例如，颤动）。拟议的研究的第一部分将致力于细化标准的真实的网络是可识别的负弯曲黎曼流形。在开发出基于角度亏损/过剩和聚类系数的直观标准之后，格罗莫夫薄三角形条件（TTC）和四点条件（FPC）将根据图的大小进行缩放，以变得与真实的网络相关，无论它们的大小有多可怕，它们都是有限的。这导致了尺度特定的格罗莫夫双曲图的新概念，其中Rocketfuel数据库已经提供了一个例子。贝尔实验室提供的真实网络、传感器网络、空中交通管制，甚至新陈代谢和神经系统网络都将被用作测试平台。接下来，进行拥堵分析的第一步是开发特定于网络的质心或重心概念，该概念在数学界已经以其黎曼流形版本而闻名。虽然在模拟中的质心似乎与最大流量点重合，但一个重要的研究里程碑将是这一事实的理论依据。在曲率谱的另一端，有强有力的证据表明，在均匀正弯曲的网络上的流量是平衡的，只要Dijkstra路由算法包含了等成本路径的随机化。前面的研究导致了研究的高潮：通过重新分配链路权重，使得到的网络是正弯曲的，基于修改后的网络的路由将平衡负载。如果网络的欧拉特性没有显示出障碍，则通过所谓的Yamabe流算法进行重新分配，Yamabe流算法具有分散的结构，因此可以与洪泛等网络算法相结合。最后，该算法将被赋予一个自适应控制结构，这意味着一旦它达到正曲率，它将不断更新的链接权重所需的网络中断，闪点等智力的优点，拟议的研究是，它将采取粗糙的几何形状？在过去的几年里，它已经悄悄地渗透到有线和无线网络、自治代理、合作控制甚至生物化学等不同领域。沿着其与复杂现实生活网络相关的特定于尺度的重新表述，这并不完全符合Gromov双曲图的数学理想化。当然，最具变革性的研究部分是基于路由的负载平衡的修改正弯曲的网络。后者将给真实的世界带来像Yamabe流这样的曲率平滑算法，这是有史以来最著名的数学难题之一的证明。庞加莱猜想。拟议活动的更广泛的影响是，它将促进电气工程系，计算机工程组和数学系最理论的几何/拓扑组之间的重点突出，应用驱动的多学科合作。联合研讨会、小组会议、新课程开发等将培养出一批新的工程专业学生，他们精通粗糙几何，而迄今为止，这还不是传统工程课程的一部分。与贝尔实验室的广泛合作将在整个项目中保持

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