虚拟路由表压缩与查找算法研究

发布时间：2018-05-19 04:15

本文选题：网络虚拟化 + 虚拟路由器　；参考：《清华大学》2016年博士论文

【摘要】：网络虚拟化技术通过对网络硬件基础设施的资源进行复用,可以以较低的经济成本建立多个虚拟网络。这些虚拟网络可以为有不同需求的用户提供服务,也可以为各种网络创新研究提供真实的部署验证环境,加快互联网的创新进程。虚拟路由器是构建虚拟网络的核心设备,其转发技术的研究对于提高虚拟网络的性能具有重要意义。本文针对虚拟路由器的独立转发与合并转发两种机制展开研究,分别提出相应的路由表(Forwarding Information Base,FIB)压缩与查找算法,取得的主要研究成果如下:(1)针对虚拟路由器独立转发机制中路由表的存储开销随虚拟路由器实例数量的增加而线性增长的挑战,提出路由表快速压缩算法US,通过改变路由表的trie树结构,可将前缀数量压缩到原来的65%。该算法不仅可以保证压缩后路由表在最坏情况下的更新性能,而且可以与大部分现有的路由表压缩与查找算法联合使用。(2)针对虚拟路由器独立转发机制中路由器片内内存容量有限的问题,提出基于最小完美哈希表的MPHL路由表查找算法,将路由表的片内内存占用降到理论最低。克服了最小完美哈希表不支持增量更新的缺点,提出MPHL算法的快速更新机制,平均更新复杂度为O(1)。算法对IPv4、IPv6两种路由表的平均查找复杂度均为O(1)。(3)针对虚拟路由器合并转发机制中现有查找算法速度较慢、支持虚拟路由表个数较少的问题,提出一种基于布隆过滤器的路由表查找算法,实现了查找速度与虚拟路由表个数无关,查找速度接近片外访存速度。在此基础上提出AE压缩算法,将查找方案的片内内存占用减少1/3。(4)设计实现了支持快速转发的虚拟网络平台MAVIN,提出可对各虚拟网络进行二层隔离的MAC编址机制,与隧道虚拟化机制相比,避免了分组转发时封装解封装导致的额外转发开销。本文对MAVIN平台的转发性能与可扩展性进行了全面评价。
[Abstract]:By reusing the resources of network hardware infrastructure, network virtualization technology can set up multiple virtual networks at low cost. These virtual networks can provide services for users with different needs, and can also provide real deployment and verification environment for various network innovation studies, thus speeding up the innovation process of the Internet. Virtual router is the core device to construct virtual network. The research of forwarding technology is of great significance to improve the performance of virtual network. In this paper, two mechanisms of independent forwarding and merge forwarding of virtual routers are studied, and the corresponding routing table forwarding Information base FIB-compression and lookup algorithms are proposed, respectively. The main research results are as follows: 1) aiming at the challenge that the storage overhead of routing table in the independent forwarding mechanism of virtual router increases linearly with the increase of the number of virtual router instances. By changing the trie tree structure of the routing table, the prefix number can be compressed to the original 65. The algorithm can not only guarantee the update performance of the compressed routing table in the worst case, Moreover, it can be used in conjunction with most existing routing table compression and lookup algorithms. Aiming at the problem of limited in-chip memory capacity in the independent forwarding mechanism of virtual routers, a MPHL routing table lookup algorithm based on minimum perfect hash table is proposed. Reduce the in-chip memory footprint of the routing table to the theoretical minimum. In order to overcome the shortcoming that the minimum perfect hash table does not support incremental update, a fast updating mechanism of MPHL algorithm is proposed, with an average updating complexity of OF-1. The average lookup complexity of the algorithm for IPv4 / IPv6 routing tables is O ~ (1) / n ~ (3). In order to solve the problem of the slow speed of the existing search algorithms and the small number of virtual routing tables in the merging and forwarding mechanism of virtual routers, the proposed algorithm has the following advantages: 1. A routing table lookup algorithm based on Bloom filter is proposed. The lookup speed is independent of the number of virtual routing tables, and the lookup speed is close to the output-memory speed. On this basis, the AE compression algorithm is proposed, and the in-chip memory footprint of the lookup scheme is reduced by 1 / 3. 4) the virtual network platform MAVIN, which supports fast forwarding, is designed and implemented, and the MAC addressing mechanism, which can separate each virtual network layer 2, is proposed. Compared with the tunneling virtualization mechanism, the additional forwarding overhead caused by encapsulation and unencapsulation of packet forwarding is avoided. This paper evaluates the forwarding performance and extensibility of MAVIN platform.
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP393.0

【相似文献】