NetSE: Small: Load Balancing by Network Curvature Control

该项目探索网络的拓扑/几何结构与其流量负载模式之间的相互作用，最终目标是得出基于曲率控制的新的负载平衡算法。在现实中观察到的现象是业务强烈集中在链路/节点的一些小子集上。这可以在互联网(主干)、电网(线路过载)、车辆交通、生物体内的新陈代谢交换等中看到。这种现象-质心的出现-不能完全用局部重尾范式来解释，但这里提供了强有力的证据，表明这是由底层网络的大范围双曲线结构决定的一般特征。在这里，双曲线是一个比喻，指的是这样一个事实，即像互联网服务提供商(ISP)这样的网络表现得像负弯曲的黎曼流形，其中鞍形是最直观的可视化。行为是指在停电或耗电等扰动下承载流量并控制流量的稳定性或不稳定性(例如，抖动)的测地线流。拟议研究的第一部分将致力于改进实网络可用负曲黎曼流形识别的准则。在开发了基于角度不足/过剩和聚集系数的直观标准之后，Gromov瘦三角形条件(TTC)和四点条件(FPC)将根据图表的大小进行缩放，以变得与真实网络相关，无论其大小多么惊人，但仍然是有限的。这导致了特定比例的格罗莫夫双曲图的新概念，RocketFuel数据库已经提供了一个例子。贝尔实验室提供的真实网络、传感器网络、空中交通管制，甚至新陈代谢和神经系统网络将被用作试验床。接下来，拥塞分析的第一步是开发特定于网络的质心或质心概念，数学界已经知道它的黎曼流形版本。虽然在模拟中质心似乎与最大交通量的点重合，但一个重要的研究里程碑将是对这一事实的理论证明。在曲率谱的另一端，有强有力的证据表明，如果Dijkstra路由算法包含等成本路径的随机化，则一致正曲线网络上的流量是平衡的。通过重新分配链路权重，使得得到的网络是正曲线的，基于改进网络的路由将平衡负载。如果网络的欧拉特性显示没有障碍，则通过所谓的Yamabe流算法进行重新分配，该算法具有分散的结构，因此将与诸如洪泛之类的网络算法相结合。最后，算法将被赋予自适应控制结构，这意味着一旦达到正曲率，它将根据网络中断、闪点等需要不断更新链路权重。拟议研究的智能优点是，它将采用粗几何？过去几年来，粗几何已经悄悄地渗透到有线和无线网络、自主代理、协作控制，甚至生物化学等不同领域？沿着与复杂现实网络相关的特定尺度的重新表述，这并不太符合格罗莫夫双曲线图的数学理想化。当然，研究中最具变革性的部分是基于改进的正曲线网络上的路由的负载均衡。后者将把像Yamabe Flow这样的曲率平滑算法带到现实世界中，Yamabe Flow在证明有史以来最著名的数学难题之一--Poincarée猜想--中发挥了重要作用。拟议活动的更广泛影响是，它将促进电气工程系、计算机工程组和数学系最具理论性的几何/拓扑组之间的重点突出、应用驱动的多学科合作。联合研讨会、小组会议、新课程开发等将造就一批新的工科学生，他们精通粗几何知识，到目前为止，这还不是传统工程课程的一部分。在整个项目过程中，将保持与贝尔实验室的广泛合作

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