NDN中缓存布局策略的研究

NDN中缓存布局策略的研究摘 要命名数据网络（Named Data Networking ，NDN）为开发全新的网络架构，以符合新兴的通讯需求，并取代现有的 TCP/IP 协议。本文首先介绍了 NDN 网络的产生背景，然后从 NDN 总体架构、协议包类型、节点结构以及运行过程等几个方面详细介绍了NDN。缓存是 NDN 中很重要的部分，是不同于 IP 网络的核心。本文主要关注 NDN的缓存放置策略问题，根据 NDN 现有的路由缓存放置策略存在的问题，从缓存命中率和网络负载两个性能指标出发，提出改进的缓存放置策略。NDN 默认的缓存放置策略是 LCE（Leave Cache Everywhere）策略。LCE 策略是指在数据包返回到数据请求者的过程中，在该路径上的每一点进行该数据内容的缓存。LCE 策略本身没有什么协同机制，会造成缓存的冗余和缓存多样性的降低。本文通过考虑距离和节点缓存能力两个因素提出了一种新型的加权缓存放置策略 ProbCache。仿真结果表明，改进后的缓存放置策略相对于 LCE 策略来说，能提升 70%左右的缓存命中率，减少 10%左右的网络负载流量，对 NDN 网络的性能进行了提升。关键词 命名数据网络（NDN） 缓存放置策略 缓存命中率 网络负载流量I目 录第一章 绪论 .11.1 设计背景 .11.2 研究的主要问题 .21.3 设计结构 .2第二章 命名数据网络架构研究 .32.1 NDN 总体架构 .32.2 NDN 协议包类型 .52.3 NDN 节点结构 .52.4 NDN 运行过程 .62.5 NDN 研究重点 .72.5.1 NDN 命名机制.72.5.2 NDN 安全机制.82.5.3 NDN 路由转发机制.82.5.4 NDN 内容缓存机制.92.6 本章小结.9第三章 NDN 缓存技术研究.103.1 NDN 缓存新特征及挑战 .103.1.1 缓存透明化 .103.1.2 缓存泛在化 .113.1.3 缓存细粒度化 .113.2 NDN 缓存性能优化研究 .123.2.1 缓存大小规划 .123.2.2 缓存空间共享优化 .133.2.3 缓存放置策略优化 .143.2.4 缓存替换策略优化 .153.2.5 缓存内容可用性优化 .153.3 本章小结.16第四章 命名数据网络缓存放置策略优化 .174.1 LCE 策略 .174.2 Hash - Routing 策略 .184.3 CL4M 策略 .19II4.4 改进策略 ProbCache.204.5 本章小结.21第五章 仿真分析 .225.1 仿真环境及参数设置.225.2 仿真结果及分析.225.2.1 缓存命中率结果 .225.2.2 网络负载流量结果 .245.2.3 仿真结果分析 .255.3 本章小结.26第六章 总结与展望 .276.1 设计总结.276.2 未来展望.271第 1 章 绪论1.1 设计背景经过 50 多年的发展，互联网的使用已发生了巨大的变化，现在互联网的主要使用需求是内容的获取和分发，信息共享已经成为中心。与此同时，基于 TCP/IP 的现代互联网也暴露出越来越多的不适应。在可扩展性方面，由于信息技术的飞速发展，导致IP 地址的不够用，互联网流量激增，路由表超线性增长。为了适应这些变化，国内外提出了“改良型”和“革命型”两种主要的改革方案。而以不改变 IP 网络主机中心地位的“改良型”方案由于并未触及到互联网的核心问题以及利益冲突等各方面原因并不能彻底地解决现在互联网的问题。所以“革命型”方案越来越受到重视。“革命型”方案提出了“面向数据的网络体系架构”DONA 1， “内容中心网络”CCN2， “信息网络”NetInf 3， “发布/订阅式互联网路由范例”PSIRP 4等网络架构。这些方案都主张改变 IP 主机中心的地位。近些年来国内外学术界提出了一种新的以信息为中心的网络体系架构，即 NDN（Information Centric Network） ，得到了大部分科学家的重视和认同。其中最具有代表性的是加州大学洛杉矶分校团队提出的面向内容的网络体系架构，即 NDN（Named Data Networking） 。NDN与IP网络很是相似，仍然延续了常用的七层沙漏模型。区别在于，NDN改变当前互联网主机- 主机通信模式，使用数据名字而不是IP 地址进行数据传递，让数据本身成为因特网架构中的核心要素。相比IP网络，NDN有两个突出的特点：一是NDN路由器可以缓存数据包，即NDN路由器能够重复使用数据，方便请求相同数据的用户；二是NDN 自身就能保证它所传送的信息内容的安全，确保内容的完整性和可靠性。在未来以内容分发为主的互联网中，NDN的提出将具有很大的研究意义。NDN网络的构建包含诸多关键性技术，例如命名技术、路由技术、缓存技术、安全技术等等。在这篇设计里我们将重点讨论缓存技术。缓存是临时文件的交换区，是一种处理方式，在NDN中内容存储器Content Store相当于路由器中的缓冲存储器，在NDN中使用缓存能够大幅提升网络使用效率，有效地缓解互联网带宽和负载的压力。NDN网络中每个节点都有一定的存储功能，用户会对所请求的内容发送兴趣包，当兴趣包在网络中某一个节点的缓存里找到请求内容后，内容将作为响应沿着兴趣包传播的路径原路返回，此时称为请求在节点缓存命中。缓存的研究主要有两个方面：一是单个节点缓存内容的替换策略，另一个是判定内容是否被节点缓存或者在何处放置的缓存位置判决策略。目前国内外对于NDN网络缓存放置策略的研究已经比较成熟，提出了LCE（Leave Cache Everywhere） 、LCD（Leave Cache Down） 、MCD（Move Cache Down）等相关算法。网内缓存技术在NDN 中扮演着重要的角色，缓存策略的好坏对于NDN的性能具有较大的影响，对缓存策略的研究具有很重要的意义。21.2 研究的主要问题NDN网络本文将以NDN网络为研究对象，深入研究它的网络架构和关键技术。并着重介绍NDN网络的缓存技术，包括NDN缓存的特征，所面临的问题和挑战，以及目前学术界对NDN缓存的研究等。然后我们会着重分析 NDN的缓存放置策略，对比现有的不同策略，并尝试提出新的策略，然后通过matlab仿真软件进行仿真验证。1.3 设计结构本文第二章将深入介绍命名数据网络 NDN 的网络架构、协议包类型、节点结构以及 NDN 网络在节点的运行过程，然后还将介绍下 NDN 的一些重点机制，如命名机制、安全机制、路由机制、缓存机制等。本文第三章重点介绍 NDN 缓存技术的研究现状，包括 NDN 缓存的特点、问题和挑战、性能优化的一些方法策略等，包括缓存的大小规模、缓存的放置和缓存的替换等等。本文第四章介绍目前研究出来的 NDN 缓存放置的策略算法。并在此基础上介绍自己提出的缓存放置的算法。本文第五章是利用 matlab 软件进行仿真及相应结果分析，比较各种 NDN 缓存放置策略的优缺点。本文第六章是总结本次毕业设计所做的工作，以及对未来的研究方向作出展望。3第 2 章 命名数据网络架构研究2.1 NDN 总体架构NDN（Named Data Networking） ，即命名数据网络，是根据现有网络为基础衍生出来的全新的网络架构，它能够有效地解决目前互联网存在的一些问题，并且可以实现基于现有网络的增量部署。针对IP网络为终端之间的交流设计了过多的协议的情况下，NDN把更多空间的利用放在内容分配上。由于现在的 IP网络架构不能满足广泛的应用，并且以获取经济利益为目的的恶意袭击行为越来越多。在这种背景下，NDN网络提出了内容中心模型，使得网络的细腰部分从IP地址变为数据名字来完成数据传播，使得数据本身成为网络架构中的核心内容。传统的IP网络七层沙漏中的细腰部分是网络能够透明传输的核心： IP数据包。正是因为IP 数据包的透明传输使得现在现在的互联网在发展的 50多年里为人们的社会和工作带来了巨大的变化，但是这种“host-to-host”的主机通信模式的数据传输已经不能适应现在以内容为中心的网络现状。而NDN正是发现了这一点，所以在细腰结构中将IP数据包变成了数据内容块。从网络整体架构来讲，NDN就是将的内容的存储放到了网络实体本身，而不是仅仅放在服务商提供的服务器上，用内容的名字替代网络中的实体，将内容分布式得存储于网络节点中，能够有效地降低请求的响应时间，提高网络的负载能力。图2-1便是 NDN沙漏模型的示意图，以及与IP模型的对比。从图中不难看出，内容是NDN 的核心，除此以外还有上层对应的安全层和底部的对应缓存路由，缓存存储，缓存转发的策略层。图2-1 NDN与IP 沙漏模型对比4根据图2-1 中的细腰模型，数据层之上放置的是支持不同应用的应用层，该应用层还能够提供对数据内容的安全性检测，以及判断内容可不可信等，从而保证数据的安全性和可信性。NDN实现这一点，我们可以理解为在内容层和应用层之间存在有一个安全层，保证传输数据本身的安全性和可靠性，实现对转发数据安全性的直接保障。策略层位于数据内容层的下面。策略层的主要功能与TCP/IP协议中的传输层功能以及部分的网络层的功能相似，提供了路由转发以及内容缓存等相关的策略。根据最新NDN 更新表明，该策略层会决定数据请求兴趣包广播的路径，并且需要按照请求发送的路径原路返回到请求数据的客户端。NDN每一个网路节点的转发、缓存等，都需在该策略层确定。NDN网络与IP网络中转发机制最大的不同点在于，NDN每一个节点会有自己专门用于存储的空间内容存储器CS，NDN不仅完成转发功能，还可以对转发的内容进行缓存，以便后续需求可以直接从该空间中获取，而不用重复地从数据提供源那里获取，大大地提高了效率。而根据张丽霞教授团队进行NDN的简单语音业务的应用的实验结果表明，即使网络运行过程中，部分链路中断，也不会对语音业务的运行产生太大的影响。这就说明，实现网络本身的存储化后，可以使切换过程中产生的数据继续在某些节点中可以找到，可以就近重新获取，从而保证了网路的通畅，同时也减少了时延，提高了用户使用的友好度。因此，从这些例子中我们可以看到，策略层的使命便是保持通信的顺畅，策略层也是NDN结构中重要的一环。策略层之下则是提供支持传输的协议以及物理链路。为了实现与当前IP网络的共存，NDN 的设计初衷里，也考虑了网络的兼容性问题。所以，NDN 结构可以依靠UDP，P2P， Broadcast等IP方式实现，以重叠网方式使用现有的 IP网路，如图2-1所示；除此以外，NDN也可以作为全新的架构，基于Open Flow实现。目前对于Open Flow 的研究还在进行当中。策略层和安全层的设计使得NDN网络具有了与IP网络区别的两大特征：第一，NDN通过安全层直接保障了数据本身的安全性，而不是像IP网络那样对数据传输通道或者终端进行保障。NDN对于传输的设备和终端设备没有任何要求，因为数据本身就是安全的；第二，NDN可以充分利用现有的网络连接方式，比如蓝牙，Wi-Fi，移动网络等，实现连接方式多样化，并且在动态环境中可以更加灵活地选择最优化连接方式。NDN是一种新提出的网络架构提案，除了有着比较清晰的革命性策略以外，为了考虑过渡性，它也实现了与IP网络很好的兼容。NDN类似于IP的超集，是一种像“通用的覆盖”的网络：NDN可以在IP网络上运行，也可以在其它的环境下运行；而同时，相对应的，IP网络也可以在NDN上运行。在IP网络历史上存在了很久的基础设施服务，诸如DNS（Domain Network Server，域名服务器）命名传统、域间路由协议和策略、以及命名空间的管理等服务，都可以很好地在NDN 上使用。而一些新兴的IP路由协议，如OSPF（开放式最短路径优先） 、IS-IS（中间系统到中间系统的路由选择协议） 、5BGP（边界网关协议） 5，等都可以在NDN网络中部署，与IP并行。因此，NDN的优势在于内容分发，而不是基于应用的通信，强大的安全性和移动性的支持会逐渐显现，使得用户能够相对轻松地接受。2.2 NDN 协议包类型图2-2 NDN 协议包类型如图2-2 所示，NDN网络中存在有兴趣包（Interest）和数据包（Data ）两种类型的协议包。兴趣包（Interest）是由数据请求用户发送的数据请求包，包含请求的内容的名称，请求的等级排序以及用来检测重复的随机数Nonce等。数据包（Data）则是由数据提供者返回给数据请求者的数据包，包含数据名称，数据提供者的签名，数据内容等信息。数据请求者发送的兴趣包，经过节点转发到数据提供者，然后数据提供者按照兴趣包的传输路线将数据包发送出去，这就是NDN 网络里包的流转过程。我们在兴趣包和数据包中，没有看到任何有关于源，转发点，接口等节点的地址信息。兴趣包的名字决定路由转发的线路，而数据包的返回路线则是根据之前既定的请求路线而定。这就证明了NDN中数据内容的中心性。2.3 NDN 节点结构NDN节点包括路由器节点和端节点两种，节点内部结构如图2-3所示所示。内容存储器Content store （CS）是NDN节点的缓存部分，能够缓存转发过的数据以备以后使用，采用的缓存替换策略为最近最少使用置换（Least Recently Used ，LRU）算法和最不经常使用置换（Least Frequently Used，LFU）来最大限度地缓存内容。兴趣请求表Pending Interest Table（PIT）的作用是存储已发送的数据请求或这些请求各自的到达接口，PIT中的条目会在匹配数据传回并完成转发后被擦除。实际中，需要为6PIT条目设置一个较短的超时时间，以最大化PIT的使用率。通常超时稍大于包的回传时间。如果超时过早发生，数据包将被丢弃。传回的数据包会在Content store 中存储。转发信息表Forwarding Information Base（FIB） ，可以通过在节点间传播名字前缀公告建立，然后利用FIB 中记录的信息转发兴趣包。由下图可以看出，FIB 中有多个设备或进程的转发接口，因此可以支持多径转发。CS、 PIT和FIB 是NDN节点中三个最重要的组成部分。图2-3 NDN 节点结构示意图2.4 NDN 运行过程数据请求者发出兴趣包就触发了NDN的一个对话。为了接收数据，一个数据请求者发出一个带有可以识别所需信息的名字的兴趣包。NDN路由器节点接收到兴趣包后，会现在自己的CS中进行名字前缀的匹配，如果有的话会把数据包直接发回给数据请求者。如果没有的话，将会匹配PIT，查询在这个节点里是否曾经有过相同的内容请求信息，如果有的话会按照历史记录找到存放该信息的节点，进行转发。如果也没有的话，将匹配FIB表，将所需内容的信息登记，并向下一个节点转发，然后重复以上过程，直到找到数据包为止。数据包的返回与兴趣包的发送过程相类似，如果CS中已经有该数据包的存在，则删掉，如果没有的话则继续匹配PIT，如果匹配的话登记信息，没有的话转向FIB登记信息。再转向下一节点，重复以上过程。因为NDN的数据包跟数据提供者的位置和数据请求者的位置是没有关系的，所以NDN路由节点可以把它存到存储器中满足未来的需求。一个兴趣包通过每一跳对应于7一个数据包，所以NDN网络实现了基于跳数的流量平衡。但在NDN对话运行过程中其中需要注意的几个问题是：1）数据包满足兴趣包的前提是：兴趣包的数据名称是数据包的数据名称的前缀，数据包的名字信息中包含但不仅仅是兴趣包的名字信息；2）当一个包到达一个接口进行名字查找时进行的是：最长前缀匹配查找，因为内容本身的名称是复杂的，可以动态生成，类似于当前的动态Web，动态内容和静态内容相结合。3）在超出一定的时间限度后没有回应，或者已经将该请求的数