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

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

项目编号： No.61201240

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 电子学与信息系统

项目作者： 张驰

作者单位： 中国科学技术大学

项目金额： 27万元

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

中文关键词： 路由；协议；性能分析；嵌入；双曲空间

英文摘要： 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 mathemat

英文关键词： Routing；Protocol；Performance Analysis；Embedding；Hyperbolic Space