NetSE: Small: Load Balancing by Network Curvature Control

NetSE：小型：通过网络曲率控制进行负载平衡

• 批准号: 1017881
• 负责人: Edmond Jonckheere
• 金额: $ 50万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017881&HistoricalAwards=false
• 关键词: NetSE; Small; Load; Balancing; Network

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

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