西南大学学报 (自然科学版)  2019, Vol. 41 Issue (10): 125-132.  DOI: 10.13718/j.cnki.xdzk.2019.10.017
0
Article Options
  • PDF
  • Abstract
  • Figures
  • References
  • 扩展功能
    Email Alert
    RSS
    本文作者相关文章
    马蕾
    胡晨光
    张婷
    许兆一
    刘银龙
    欢迎关注西南大学期刊社
     

  • 内容中心网络中基于AHP和GRA的路由策略    [PDF全文]
    马蕾1, 胡晨光1, 张婷2, 许兆一2, 刘银龙3     
    1. 北京电子科技职业学院 电信工程学院, 北京 100176;
    2. 北京建筑大学 电气与信息工程学院, 北京 100044;
    3. 中国科学院 信息工程研究所, 北京 100093
    摘要:多径路由是内容中心网络(Content Centric Networking,CCN)的关键技术之一,能够充分利用网络中的内容副本,降低内容服务器负载和内容获取时延.然而,多径路由在优化网络性能的同时,会带来网络流量冗余,降低网络资源利用率.为了提高CCN中路径选择的精准性,提出了一种基于层次分析(Analytic Hierarchy Process,AHP)和灰度关联分析(Grey Relation Analysis,GRA)的路由策略.首先,分析CCN中影响路由性能的各种因素,并利用AHP确定各因素的权重.然后,利用GRA对可用路径进行排序,并选择最佳的转发路径.仿真结果表明,与已有路由策略相比,所提路由策略在服务器负载、缓存替换率等方面具有较好的性能.
    关键词内容中心网络    路由    层次分析法    灰度关联分析    

    随着互联网用户规模的增长和网络应用的普及,互联网流量近年来呈现爆发式的增长.据思科报告预测[1]:2021年,全球互联网用户将增长至46亿,全球互联网数据流量将达到3.3ZB(2016年的3倍),其中视频流量的占比将从2016年的73%增长至82%.互联网流量(特别是视频流量)的快速增长,使得当前互联网中以IP地址为中心、端到端通信为主要通信模式的IP协议暴露出越来越多的不足,如内容分发效率低、移动性支持不足等.因此,国内外学者相继提出了许多新型的互联网体系架构,其中具有代表性的是内容中心网络[2](Content-Centric Networking,CCN). CCN网络更加关注内容本身而不是数据内容所在位置,通过利用网内缓存、多径路由等机制来提高网络中内容分发效率.

    多径路由是CCN的核心机制之一,通过向所有可用端口同时发送内容请求,可以有效利用网络中缓存的内容副本,使得内容获取时延最小.但是,同时向所有端口发送请求会导致内容数据的重复传输,浪费大量的网络资源.因此,为了在内容获取时延和网络利用率间取得平衡,许多研究者对CCN中的路由策略进行了研究.

    目前,对CCN中多径路由策略研究主要分为3类:基于网络的路由优化策略、基于内容的路由优化策略和基于用户的路由优化策略.基于网络的路由优化策略是指在进行路由选择(即兴趣包转发端口选择)时,基于网络状态选择最佳的路由方式.例如,文献[3]提出了一种基于链路状态的路由策略,该策略基于到达内容发布者的跳数来选择路由路径;文献[4]提出了一种基于时间的兴趣包路由转发策略,该策略选择到达内容发布者往返时延最小的路径进行转发兴趣包.基于内容的路由优化策略是指在进行路由选择时,优先选择与请求内容所在区域一致的端口进行路由.例如,文献[5]提出了一种基于内容轨迹的多路径路由策略,该策略是通过记录网络中内容的流动轨迹来获悉内容在网络中的分布情况,当有用户请求该内容时优先将请求包路由至内容所在区域,从而降低内容获取时延.文献[6]提出了一种基于内容位置的路由方法,该方法首先对内容进行分类,然后根据历史信息统计不同类型内容所在的位置,最后根据请求内容类型进行路由.基于用户的路由优化策略是指在进行路由选择时,优先选择具有相同兴趣偏好、位置或社交关系的用户所在端口进行路由.例如,文献[7]提出了一种基于用户偏好的路由策略,该策略中优先将兴趣包转发至具有相同或相似偏好的用户所在的端口上,以提升缓存利用率和降低服务器负载.文献[8]提出了一种基于社交关系和缓存状态的路由策略,该策略是将请求数据包优先转发至与请求用户社交关系密切的用户所在的端口,以提高请求命中率.上述研究,虽然都能够在一定程度上降低内容获取时延和源服务器负载,但是由于只考虑了网络、内容和用户三者中的一个或两个层次,无法实现网络性能最优.

    针对CCN中路由策略存在的不足,本文结合层次分析和灰度关联分析提出一种融合网络层、内容层和用户层多种因素的路由策略.首先,基于AHP确定网络层、内容层和用户层中各因素的权重,然后基于GRA选择最佳的路由端口.仿真结果表明,本文所提策略在服务器负载、缓存替换率和内容获取时延方面具有更优的综合性能.

    1 CCN中的多径路由

    CCN通信由内容请求者驱动,内容数据以内容块(chunk)进行传输. CCN有两种类型的数据包:Interest包和Data包,两种包中都包含内容名称.路由节点上有3个数据结构完成转发,分别为:转发信息表(forwarding information table,FIB)、内容缓存(Content Store,CS)和待定兴趣表(Pending Interest Table). FIB由路由协议生成,是转发Interest的依据,可以有一个或多个出口,CS用来存储已经转发的Data包,以供其他用户使用,PIT表里记录的是已经转发但尚未被响应的Interest包及其到达接口.

    当内容请求者需要请求内容时,首先广播Interest包,当Interest包到达路由节点时,路由节点会根据Interest包中的内容名称查找CS.如果CS中有被请求的内容,则响应该请求;如果没有,则查找PIT,如果PIT中有该内容名称条目,则在该条目中增加该Interest包到达的Face(节点接口),如果没有,则查找FIB.如果在FIB中找到,则按照路由规则向接口表中的一个或多个接口转发Interest包,并在PIT中记录,否则,丢弃该Interest包.当Interest包到达内容服务器或者存储Interest包内容名称对应内容的路由节点时,Data包按照Interest包的反向路径回传至请求节点,如图 1.

    图 1 CCN路由模式

    在CCN网络中,内容请求者除了可以从内容服务器直接获取内容外,还可以从缓存该内容的路由节点获取,这种多源特性和Interest包多接口转发机制,使得CCN可以天然支持多路径路由.多径路由对于降低服务器负载、优化网络资源、平衡网络流量具有很大作用.但是,为了满足同一个内容请求,多径路由机制可能会使得相同内容通过多个路径并行传输至请求节点,导致相同内容的重复传输,从而导致网络中存在大量冗余流量,因此如何在多个可用接口(路径)中寻找一条最优的路径是CCN多径路由需要解决的主要问题之一.

    2 基于AHP和GRA的路由策略

    由于CCN支持多径路由,为实现内容获取时延与网络冗余流量的有效平衡,本文所提策略综合考虑网络、内容和用户多方面因素,基于AHP和GRA从多个可用接口(路径)中选择最佳的接口(路径).

    2.1 确定路由策略影响因素

    在最佳路径(接口)选择中,需要综合考虑以下因素:

    1) 网络因素:由于CCN网络支持网内缓存,各路由节点除了具有转发功能外,还可以缓存途经该节点的内容数据.路由策略的性能很大程度上取决于内容在路由节点上的缓存状态,而路由节点的缓存判决主要基于节点度数、介数、缓存空间等因素.另外,Data数据包传输过程受路由节点间的链路时延和传输速率影响较大.因此,在进行CCN路由优化时,需要考虑与网络相关的节点度数、介数、缓存空间、链路时延、传输速率等因素.

    2) 内容因素:由于内容流行度、内容大小等因素会对网络中缓存决策产生一定的影响,因此在进行CCN路由优化时,需要考虑与内容相关的内容流行度、内容大小等因素.

    3) 用户因素:由于具有相同偏好的用户往往会访问相同的内容,将Interest包发送给与该请求用户偏好相似度越高的用户所在的路由节点(接口),能够在该路由节点获取请求内容的概率越大,因此在进行CCN路由优化时,需要考虑用户偏好相似度.

    综上,在基于AHP和GRA进行路由优化时,需要综合考虑的因素包括节点度数、节点介数、节点缓存空间、节点间链路时延、节点间传输速率、内容流行度、内容大小、用户偏好相似度.

    2.2 基于AHP计算各因素的相对权重

    接下来,本文采用AHP确定上述因素的权重. AHP是定性和定量相结合的多因素指标的决策分析方法,通过将影响某一决策目标的各个因素进行量化、对比,初步分析各个因素的重要程度,并通过一致性检验降低主观因素的影响,使得决策结果更加科学、客观[9].其主要步骤如下:

    1) 建立路由策略(即,接口选择)的层次结构

    根据影响CCN路由策略考虑的上述因素,建立接口选择的三层结构,如图 2所示.

    图 2 CCN接口选择层次结构图

    2) 构建判别矩阵

    将影响路由策略的因素表示为C1C2C3,…,CnCiCj间的相对重要性表示为aij,并基于aij构建判别矩阵A.

    $ A = \left[ {{a_{ij}}} \right] = \left[ {\begin{array}{*{20}{c}} 1&{{a_{12}}}&{ \cdot \cdot \cdot }&{{a_{1n}}}\\ {\frac{1}{{{a_{12}}}}}&1&{ \cdot \cdot \cdot }&{{a_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {\frac{1}{{{a_{1n}}}}}&{\frac{1}{{{a_{2n}}}}}&{ \cdot \cdot \cdot }&1 \end{array}} \right] $ (1)

    其中,aii=1,aji=1/aij>0(ij=1,2,…,n). aij的值可根据资料数据、专家系统或用户服务体验调查等方式来确定,通常采用1~9标度法[10],取值标度表如表 1所示.

    表 1 aij的取值标度表

    3) 计算各因素权重

    基于判别矩阵A,计算其最大特征值λmax,并基于其对应的特征方程AW=λmaxW求出特征向量WW即为各因素的权重值.

    4) 一致性检验

    由于判别矩阵A构建过程中存在一定的主观性,为降低由此导致的权重值不合理性,因此需要对A进行一致性检验、调整.采用一致性指标CI与随机一致性指标RI的比值CR作为标准,若CR<0.1,则矩阵具有可接受的一致性,否则重新构建判别矩阵.其中$ {C_I} = \frac{{{\lambda _{\max }} - n}}{{n - 1}}$n为矩阵阶数;随机一致性指标R表 2所示[11].

    表 2 随机一致性指标表

    最终,确定各因素的相对权重W(w1w2w3,…,wn).

    2.3 基于GRA计算最佳路由选择

    GRA是一种多属性决策算法,通过判断待选方案与理想方案的关联关系来判别待选方案的优劣程度.待选方案与理想方案关联性越高,则该待选方案越接近理想方案,性能越佳.基于GRA的最佳路由计算方法主要步骤如下:

    1) 构建判决矩阵

    设有m个可选路由Ri(i=1,2,…,m),每个可选路由有n个属性Ci.路由Ri的各个属性值为hij,则判决矩阵H

    $ \mathit{\boldsymbol{H}} = \left[ {{h_{ij}}} \right] = \begin{array}{*{20}{c}} {\begin{array}{*{20}{l}} {{C_1}}\\ {\left[ {\begin{array}{*{20}{l}} {{h_{11}}}\\ {{h_{21}}}\\ \vdots \\ {{h_{m1}}} \end{array}} \right.} \end{array}}"{\begin{array}{*{20}{l}} {{C_2}}\\ {{h_{12}}}\\ {{h_{22}}}\\ \vdots \\ {{h_{m2}}} \end{array}}"{\begin{array}{*{20}{l}} { \cdot \cdot \cdot }\\ { \cdot \cdot \cdot }\\ { \cdot \cdot \cdot }\\ {}\\ { \cdot \cdot \cdot } \end{array}}"{\begin{array}{*{20}{l}} {{C_n}}\\ {\left. {\begin{array}{*{20}{l}} {{h_{1n}}}\\ {{h_{2n}}}\\ \vdots \\ {{h_{mn}}} \end{array}} \right]\begin{array}{*{20}{c}} {{R_1}}\\ {{R_2}}\\ \vdots \\ {{R_m}} \end{array}} \end{array}} \end{array} $ (2)

    2) 判决矩阵无量纲化

    由于决定路径性能优劣的各因素(或属性)的性质不同,有些是增益型(即值越大越好,如缓存空间、传输速率等),有些是成本型(即值越小越好,如链路时延),需要对各属性进行归一化,将矩阵H转换为无量纲矩阵B,其元素bij按如下方法计算.

    对于增益型因素,归一化为

    $ {b_{ij}} = \frac{{{h_{ij}} - \mathop {\min }\limits_i {h_{ij}}}}{{\mathop {\max }\limits_i {h_{ij}} - \mathop {\min }\limits_i {h_{ij}}}} $ (3)

    对于成本型因素,归一化为

    $ {b_{ij}} = \frac{{\mathop {\max }\limits_i {h_{ij}} - {h_{ij}}}}{{\mathop {\max }\limits_i {h_{ij}} - \mathop {\min }\limits_i {h_{ij}}}} $ (4)

    3) 理想路由接口

    对于特定内容的Interest数据包路由转发,其理想接口的参考参数向量X0=(h01h02,…,h0n)T,并根据上述方法进行归一化得到b0j.参考向量的选择与相应的请求内容、请求用户和网络拓扑相关,针对网络拓扑、用户请求内容以及用户业务体验选择满足用户需求的理想路由接口对应的参考向量.

    4) 计算关联矩阵

    计算可选路由接口对应参数与理想路由接口对应参考参数的相关值rij.

    $ {r_{ij}} = \frac{{\mathop {\min }\limits_i \mathop {\min }\limits_j {b_{0j}} - {b_{ij}} + \mathop {\max }\limits_i \mathop {\max }\limits_j {b_{0j}} - {b_{ij}}}}{{{b_{0j}} - {b_{ij}} + \mathop {\max }\limits_i \mathop {\max }\limits_j {b_{0j}} - {b_{ij}}}} $ (5)

    进而得到相关矩阵R=(rij)m×n.

    5) 计算灰度关联值

    计算各可选路由接口对应参数与参考参数向量的灰度关联值为

    $ {r_{ij}} = \sum\limits_j {{\omega _j}{r_{ij}}} $ (6)

    则路由接口灰度关联系数向量为T=(r1r2,…,rn).

    6) 路由接口选择

    按照ri的大小进行排序,ri最大的网络接口即为最佳路由接口.

    本文所提方法不仅综合考虑了影响路由性能的网络因素、内容因素和用户因素,而且还采用层次分析法确定了最佳路由评价体系中定性指标的量化,一致性检验可以降低主观因素的影响,使得结果客观、科学,并用灰度关联对可用路由进行综合评价,从而能够获取最优的路由接口.

    2.4 基于AHP和GRA路由策略流程

    基于AHP和GRA路由策略的实现流程如图 3所示.

    图 3 基于AHP和GRA路由策略流程图

    主要步骤如下:

    步骤1:CCN路由节点收到来自于某一接口或用户的Interest数据包,依次在CS、PIT和FIB中进行内容名称匹配检索.若CS或PIT有匹配项,则按照CCN标准协议进行返回Data数据包或在PIT表中添加到达接口;若CS和PIT均没有匹配项,而FIB中有匹配项,则执行步骤2;

    步骤2:收集Interest数据包中内容名称对应内容的流行度、内容大小,收集备选接口对应路由节点的度数、介数、缓存空间以及当前路由节点与各备选接口路由节点间的链路时延和传输速率,收集请求用户与网络中其他用户的偏好相似度;

    步骤3:按照2.2节方法,基于AHP计算步骤2中收集的各因素的相对权重;

    步骤4:按照2.3节方法,基于GRA从可选路由接口中选择最佳接口;

    步骤5:将Interest数据包从所选最佳接口转发出去.

    按照步骤1至步骤5继续转发Interest数据包,直至到达包含请求内容的节点(内容服务器或路由节点).

    3 仿真与分析

    为验证所提基于AHP和GRA的路由策略(AHP and GRA based Routing Strategy,AGRS)的性能,本文采用ndnSIM对其进行仿真,并与基于广播的路由策略(Broadcast based Routing Strategy,BRS)和基于用户偏好相似度的多径路由策略(User Preference based Multipath Routing Strategy,UPMR).仿真过程中的缓存策略采用随处缓存(Leave Copy Everywhere,LCE)[12]和概率缓存(Prob-λ)机制,缓存替换策略最近最少使用(Least Recently Used,LRU)替换机制.

    本文仿真过程中的主要参数设置如表 3

    表 3 仿真参数表

    在对本文所提AGRS策略进行仿真时,每个中间路由节点按照2.4节所描述的流程来选择最佳路由接口转发,其中各因素的相对重要性可参照文献[3-8]中的描述给出.

    表 4 各因素的相对重要表

    计算可得CR=0.098 7<0.1,各因素的权重为:W(w1w2w3,…,w8)=(0.034 6,0.038 7,0.127 1,0.116 7,0.100 3,0.147 1,0.213 0,0.222 4).

    为降低单次仿真结果存在的偶然性,对3种路由策略分别仿真10次,并取10次仿真结果进行平均.在AGRS、BRS和UPMR 3种路由策略下,内容服务器的负载情况如图 4所示.由图 4可以看出,本文所提AGRS的服务器负载最小.这是因为BRS是向所有可用接口都转发Interest包,UPMR只考虑了用户层面的偏好相似度和网络层面的链路时延和传输速率,而AGRS综合考虑了网络、内容和用户3个层面的因素.因此,BRS向所有可用接口转发Interest数据包,会导致大量的冗余传输,增加了服务器负载,性能最差;而BRS能够最好地利用中间路由节点的缓存内容,降低了到达服务器的Interest包的个数,从而减小了内容服务器负载,性能最佳.

    图 4 不同路由策略下的内容服务器负载

    图 5给出了AGRS、BRS和UPMR 3种路由策略下,网络中缓存替换率的仿真结果.由图可以看出,BRS的缓存替换率最高,UPMR次之,AGRS最小.这是因为,BRS将Interest数据包转发至所有可用接口,使得内容Data数据包会通过不同的路径回传至请求用户,从而导致这些路径上的中间路由节点会频繁地进行缓存替换. UPMR和AGRS则分别考虑了多种因素来减少发送接口的数目或选择性能好的接口来转发,与BRS相比,均具有较低的缓存替换率.由于AGRS在进行路由接口选择时,兼顾了比UPMR更多的因素,因此AGRS的缓存替换率最小.

    图 5 不同路由策略下路由节点的缓存替换率

    图 6给出了AGRS、BRS和UPMR 3种路由策略下,内容获取时延的仿真结果.由图可以看出,BRS和AGRS具有较低的获取时延.这是因为,BRS向所有可用接口转发Interest包,可以快速到达包含请求内容的服务器或路由节点,从而可以降低内容获取时延.虽然UPMR和AGRS在进行路由接口选择时都考虑链路时延和传输速率,但是UPMR没有考虑网络拓扑信息(比如节点度数、介数等)导致Interest包到达包含请求内容的服务器或路由节点的概率会降低,从而使得UPMR的时延比AGRS较大.

    图 6 不同路由策略下的内容获取时延

    图 4图 6可以看出,由于AGRS综合考虑了网络、内容和用户三方面的因素,使得Interest包在转发过程中可以选择最佳的接口进行路由,即在少量增加内容获取时延的情况下可以大幅降低服务器负载和路由节点缓存替换率,从而使得AGRS具有最佳的综合性能.此外,还可以看出,缓存策略对AGRS的性能产生一定的影响,即:概率缓存的性能要优于LCE缓存,这是因为LCE会导致大量的冗余缓存,降低网络中内容的多样性,从而降低网络性能.

    4 结语

    本文针对CCN的多径路由优化问题,提出了一种基于AHP和GRA的路由策略.首先,确定了影响CCN路由性能的因素;然后,基于AHP确定各因素的权重;最后,基于GRA选择最佳的路由接口来转发Interest数据包.所提策略能够在少量提高内容获取时延的情况下大幅降低内容服务器负载和路由节点的替换率,使得网络综合性能最佳.

    参考文献
    [1]
    Cisco Visual Networking Index: Forecast and Trends. 2017-2022 White Paper[EB/OL] https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white-paper-c11-741490.html.
    [2]
    JACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking Named Content[J]. Communications of the ACM, 2012, 55(1): 117-124. DOI:10.1145/2063176.2063204
    [3]
    HOQUE A K M M, AMIN S O, ALYYAN A, et al. Nisr[C]//Proceedings of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking-ICN'13, Hong Kong, China, August 12, 2013.
    [4]
    CHOI W, RAMNEEK, SEOK W. Time-Based Forwarding Control in Content Centric Networking[C]//201618th International Conference on Advanced Communication Technology (ICACT), Pyeongchang Kwangwoon Do, South Korea, January 31-February 3, 2016.
    [5]
    张岩, 黄韬, 刘江, 等. 基于内容轨迹的内容中心网络多径路由策略[J]. 北京邮电大学学报, 2014, 37(3): 98-103.
    [6]
    GARCIA-LUNA-ACEVES J J, BARIJOUGH M M. Efficient Multicasting in Content-Centric Networks Using Locator-Based Forwarding State[C]//2017 International Conference on Computing, Networking and Communications (ICNC), Silicon Valley, CA, USA, January 26-29, 2017.
    [7]
    江欣伟.基于用户偏好的内容中心网络路由与缓存策略研究[D].北京: 北京邮电大学, 2018.
    [8]
    QU D, WANG X, HUANG M, et al. A Cache-Aware Social-Based QoS Routing Scheme in Information Centric Networks[J]. Journal of Network and Computer Applications, 2018, 121: 20-32. DOI:10.1016/j.jnca.2018.07.002
    [9]
    张菁芳, 李佳承, 陈俊国, 等. 基于层次分析法的医院财务信息化绩效评价指标体系研究[J]. 西南大学学报(自然科学版), 2017, 39(2): 114-120.
    [10]
    白思俊. 系统工程[M]. 3版. 北京: 电子工业出版社, 2013.
    [11]
    方国华. 多目标决策理论、方法及其应用[M]. 北京: 科学出版社, 2011.
    [12]
    张国强, 李杨, 林涛, 等. 信息中心网络中的内置缓存技术研究[J]. 软件学报, 2014, 25(1): 154-175.
    Routing Strategy in Content-Centric Networking Based on AHP and GRA
    MA Lei1, HU Chen-guang1, ZHANG Ting2, XU Zhao-yi2, LIU Yin-long3     
    1. College of Telecom Engineering, Beijing Polytechnic, Beijing 100176, China;
    2. School of Electric and Information Engineering, Beijing University of Civil Engineering and Architecture, Beijing 100044, China;
    3. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
    Abstract: Multipath routing is one of the key technologies of Content-Centric Networking (CCN), which can make full use of content copies in the network and reduce content server overload and content acquisition delay. However, while optimizing network performance, multipath routing will bring network traffic redundancy and reduce network resource utilization. In order to improve the accuracy of path selection in CCN, a routing strategy based on Analytic Hierarchy Process (AHP) and Grey Relation Analysis (GRA) is proposed in this paper. First, various factors affecting routing performance in CCN are analyzed, and the weight of each factor is determined based on AHP. Then, GRA is used to sort the available paths and choose the best forwarding path. The simulation results show that compared with the existing routing strategies, the proposed routing strategy has better performance in terms of server overload and cache replacement rate.
    Key words: content-centric networking (CCN)    routing    analytic hierarchy process (AHP)    grey relation analysis (GRA)    
    X