面向ICN的可扩展名字路由机理研究

发布时间：2019-03-12 13:35

【摘要】：内容分发和获取已成为互联网的主要应用,而网络体系结构依然沿用主机为中心的端到端设计。为彻底解决应用需求和体系结构间的矛盾,新型网络体系结构-信息中心网络(Information-Centric Networking,ICN)被提出。ICN以内容作为网络的首要对象,以高效地内容分发和获取为目标,已成为未来网络研究的热点之一。名字路由作为ICN的核心,通过内容名字而非地址获取内容。然而,由于海量内容名字以及内容命名的位置无关设计,导致ICN名字路由在规模和性能两方面均面临严峻的可扩展问题挑战。本文从可扩展路由理论出发,基于几何路由从名字解析角度探索可行的可扩展名字路由方案,主要从可扩展名字路由设计和基于几何路由的可扩展优化两方面展开研究。(1)从overlay角度解决ICN路由可扩展问题。虽然ICN名字解析路由多采用overlay设计,但面临两方面问题:底层拓扑采用传统路由,本身存在可扩展问题;覆盖网拓扑与底层拓扑不一致,易产生长路径。针对以上问题,本文提出基于overlay的几何名字路由方案,分别在网络拓扑和名空间拓扑上解决以上问题。针对底层路由可扩展问题,提出通用几何路由框架,适用于任意几何路由。针对长路径问题,提出基于双层群组划分策略的名字解析系统,至多两跳完成名字解析,通过与几何路由框架结合,保证总能找到较近解析节点。理论分析和实验结果均表明该方案达到了规模和性能可扩展的折中。(2)从underlay角度解决ICN路由可扩展问题。通过分析几何路由度量空间和DHT键值空间的特性,提出基于underlay的几何名字路由方案,将几何路由和基于DHT的名字解析系统置于相同度量空间,保证拓扑一致性。首先,基于符号空间层次划分思想提出基于树的度量空间T;然后,基于T提出了贪心嵌入和名字映射方案。内容名字直接映射为度量空间坐标,以内容坐标为目的通过贪心转发实现名字发布或解析,有效降低了路径延展度和路由表规模。同时,针对解析信息分布不均衡问题,提出不等概率编码和注册转发的负载均衡策略,显著提高了节点解析负载均衡。(3)动态拓扑可能导致路由更新可扩展问题。对于几何路由,节点加入或删除可能引起大量节点甚至整个拓扑重新嵌入,导致大规模坐标更新;对于基于underlay的几何名字路由,坐标更新和拓扑变化可能导致大规模解析信息更新。针对以上问题,本文提出支持动态拓扑的几何路由和几何名字路由。首先,分析几何路由动态问题的原因,提出维度扩展在线嵌入策略,基于该策略进一步提出比特串前缀嵌入以实现动态几何路由,有效避免了节点坐标更新,继而避免由坐标更新导致的解析更新;随后,提出基于粗粒度拓扑信息的名字映射以支持基于underlay的动态几何名字路由,实现了拓扑无关性和解析负载均衡的折中,满足解析负载均衡同时,减少了拓扑变化导致的解析更新。(4)虽然几何路由路由表只保存邻居坐标,但其面临坐标长度可扩展问题,即简洁贪心嵌入问题。长坐标使得数据包头部过大,造成网络资源浪费。针对这一问题,本文提出一种简洁前缀嵌入方案,通过压缩关键路径上节点坐标保证简洁性。首先,提出了重路径分解和宽路径分解两种路径分解方法,自底向上地从生成树中寻找关键路径;然后,提出压缩嵌入方法,基于关键路径自顶向下地实现生成树简洁嵌入。理论分析和实验均表明方案同时满足贪心特性和简洁特性。对于任意拓扑,贪心嵌入后坐标长度上界为多项式对数比特。
[Abstract]:Content distribution and access have become the primary application of the Internet, and the network architecture continues to follow the host-centric end-to-end design. In order to thoroughly solve the contradiction between application requirements and architecture, a new network architecture-information-center networking (ICN) is proposed. ICN, as the primary object of the network, has become one of the hot spots of future network research. The name route is the core of the ICN, and the content is not obtained by the content name instead of the address. However, due to the massive content name and the location-independent design of the content naming, the ICN's name routing is faced with a severe and scalable challenge in both scale and performance. Based on the theory of the extensible route, this paper, based on the geometric routing, explores the feasible extensible name routing scheme from the name resolution angle, which is mainly based on the extensible name route design and the extensible optimization based on the geometric routing. (1) The problem of ICN routing can be solved by the overlay angle. Although the ICN's name resolution route is more than the overlay design, it faces two problems: the underlying topology adopts the traditional route, and there is an extension problem in itself; the overlay network topology is not consistent with the bottom layer topology, and the long path is easy to be generated. In view of the above problems, this paper proposes a geometric name routing scheme based on overlay, which solves the above problems in the network topology and the name space topology, respectively. This paper presents a general-purpose geometric routing framework for arbitrary geometric routing, aiming at the problem of the scalability of the bottom-layer routing. In order to solve the problem of long path, a name resolution system based on a two-layer group partition strategy is proposed. At most two hops complete the name resolution, and by combining with the geometric routing framework, it is ensured that the closer analytical nodes can always be found. Both the theoretical analysis and the experimental results show that the scheme has reached the trade-off of scale and performance. (2) The problem of ICN routing can be solved from the underlay angle. By analyzing the characteristics of the geometric routing metric space and the DHT key value space, a geometric name routing scheme based on the underlay is proposed, and the geometric routing and the DHT-based name resolution system are placed in the same metric space to ensure the topological consistency. First, a tree-based metric space T is proposed based on the symbol-space-level partitioning concept; then, the greedy embedding and the name mapping scheme are proposed based on the T. The content name is directly mapped to the coordinate of the metric space, and the name distribution or resolution is realized by the greedy forwarding based on the content coordinates, so that the path extension and the size of the routing table are effectively reduced. At the same time, aiming at the problem of unbalanced information distribution, the load balancing strategy of unequal probability coding and registration and forwarding is proposed, and the load balance of the node analysis is obviously improved. (3) The dynamic topology may cause the routing update to be extended. For geometric routing, the addition or deletion of a node may cause a large number of nodes and even the entire topology to be re-embedded, resulting in large-scale coordinate updates; for the underlay-based geometric name routing, the coordinate update and the topology change may result in large-scale resolution information updating. In view of the above problems, this paper proposes to support the geometric routing and the geometric name routing of the dynamic topology. firstly, the reason of the dynamic problem of the geometric routing is analyzed, the on-line embedding strategy of the dimension extension is proposed, the bit string prefix embedding is further proposed based on the strategy, the dynamic geometric routing is realized, the node coordinate updating is effectively avoided, the analytical update caused by the coordinate updating is avoided, The name mapping based on the coarse-grained topology information is proposed to support the dynamic geometric name routing based on the underlay, and the compromise between the topology independence and the analysis load balance is realized, and the analysis load balancing is satisfied, and the analytical update caused by the topology change is reduced. (4) Although the geometry routing table only saves the neighbor coordinates, it faces the problem of the extension of the coordinate length, that is, the simple greedy embedding problem. The long coordinates cause the head of the data packet to be too large to cause the waste of network resources. In order to solve this problem, this paper proposes a simple prefix embedding scheme, which guarantees the simplicity by compressing the coordinates of the nodes on the critical path. First, two path decomposition methods of re-path decomposition and wide path decomposition are proposed, and the key path is searched from the bottom up in the spanning tree; then, the compression embedding method is put forward, and the generation tree is simple and embedded based on the key path top-down. Both the theoretical analysis and the experiment show that the scheme can satisfy the greedy character and the simple character at the same time. For any topology, the upper bound of the coordinate length after the greedy embedding is a polynomial log bit.
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP393.02

【参考文献】