大规模通信网络中基于双曲嵌入的高性能路由理论与协议研究

It is fundamentally impossible to find and support a routing scheme which can provide delivery guarantee and minimized control overhead with the optimal path within the framework of present networking paradigm based on graph-theoretic abstraction of network topology. Therefore, next-generation network routing schemes require a paradigm shift. In this project, we provide a new routing paradigm based on the proposition that behind every real-world communication network, there exists an intrinsic metric space. By assigning to each node a new coordinate in this space, we can perform greedy routing with respect to these coordinates and achieve much better routing performance. .Our research agenda includes four related and clearly defined tasks: (1) demonstrate the existence of intrinsic metric space and verify its geometric properties (negatively curved); (2) build methodologies to explicitly reconstruct the intrinsic metric space by embedding the given network topology into a hyperbolic plane; (3) address challenges associated with using this new routing paradigm in practice; and (4) verify network performance of this new routing paradigm in real networking environments..Our project will open a new area of research focusing on construction of practically acceptable next-generation routing protocols based on mathematically rigorous routing algorithms.

路由是通信网最重要的功能。传统的基于网络拓扑信息的路由范式无法同时确保分组送达、支持网络扩展、优化路由度量和路由开销。本项目提出路由新范式，利用网络拓扑信息重建网络的内禀度量空间，并在其上通过空间坐标实现贪婪路由。在此范式下，通过测量和提炼现实网络拓扑的几何特性，定量分析路由在理论上所能达到的性能极限；通过引入双曲Voronoi图及其对偶图，揭示双曲空间的几何特性与路由性能之间的关联，为路由建模和性能分析提供系统的分析方法和数学工具；利用双曲几何来刻画内禀度量空间的性质，在贪婪紧致嵌入的基础上，通过研究低失真嵌入、在线增量嵌入和动态鲁棒嵌入等新兴双曲嵌入技术，为高性能路由的实现提供可行的新途径；实现高性能路由在真实网络环境下的测试系统，为路由理论的验证提供事实依据。.本项目将提出新的概念和思想，突破现有路由范式的理论限制，促进网络基础理论的创新，为我国网络通信产业的发展提供核心技术支持。

路由是通信网最重要的功能。传统的基于网络拓扑的路由范式无法同时确保分组送达、支持网络扩展、优化路由度量和路由开销。为此，本项目的研究提出新的路由范式，利用网络拓扑重建网络的内禀度量空间，并在其上通过空间坐标实现贪婪路由。研究双曲空间的几何特性与路由性能之间的关联，为路由建模和性能分析提供系统的分析方法和数学工具，为高性能路由的实现提供可行的新途径。探索上述新型路由理论在其它网络环境下的应用。实现实物验证平台和试验床，为路由理论的验证提供支撑，并促进理论成果向实际系统的转化。.本项目所取得的理论成果包括构建了内禀度量空间理论，利用双曲几何来刻画内禀度量空间的性质，为路由度量的选择和评价提供了坚实的理论基础。在贪婪紧致嵌入的基础上，通过实现低失真嵌入、在线增量嵌入和动态鲁棒嵌入等新兴双曲嵌入技术，为高性能路由的实现提供可行的新途径。通过引入四叉树路由作为双曲路由的离散化实现方法，将文献中已知的大部分路由方法（最短路径路由、基于地理位置的路由、基于度量空间的路由）纳入一个统一的理论框架，为系统分析和设计路由协议、定量研究路由性能提供了新的研究框架。针对某些有代表性的网络场景或特殊网络需求（如Internet路由表压缩、RFID物联网通信协议设计、多跳认知无线电网络的路径选择算法、以卫星为骨干的空天地一体化网络路由）设计了和实现了高效的网络协议解决方案。.在本项目的研究中进一步发现，社会网络与技术网络一样，也可在内禀度量空间中构造更加高效的信息传递机制。因而，将上述理论成果应用于设计社会网络合作模式下的信息分享机制和协同感知中的信息汇聚机制。基于抽象度量空间的路由还有助于提升网络安全。本项目利用抽象度量空间来刻画网络终端用户间的信任关系，结合一些新的密码学原语如基于信任的加密、基于信任的签名，构造出更加安全和有效的网络协议，应用于移动健康网络、在线社会网络、认知无线电网络、车联网等有特殊安全和隐私需求的网络场景。.本项目还实现了包括有线和无线部分的高性能路由协议的实物验证平台和试验床。利用软件无线电SORA技术来搭建无线接入节点。利用最新的软件定义网络OpenFlow技术实现了支持四叉树编址的SDN交换机原型机。除了为本项目的理论研究成果提供验证环境外，还规划了原型机在临近空间真实环境下大尺度组网演示验证。