推荐星级：
- 1
- 2
- 3
- 4
- 5
命名数据网络下基于K-medoids的簇内Hash路由机制
资料介绍
命名数据网络(Named Data Networking,NDN)是以内容为中心的新型网络架构,其随处缓存策略存在缓存冗余过多、邻居缓存利用率低等问题,导致缓存空间的浪费及缓存效率的低下.本文提出的融合沿路径非协作和路径外协作的缓存路由机制(K-Medoids Hash Routing,KMHR),使用K-medoids算法选取层次簇内的中心点,并针对不同流行度的内容分别采用Hash路由及最短路径路由,保证簇内高流行度内容的精确定位和唯一性,降低缓存冗余,提高缓存效率.通过真实网络拓扑仿真得出,KMHR机制具有最低的请求时间、最优的路由增益和较少的缓存内容数量.
部分文件列表
| 文件名 | 大小 |
| 命名数据网络下基于K-medoids的簇内Hash路由机制.pdf | 940K |
部分页面预览
（完整内容请下载后查看）10
Vol． 45 No． 10
Oct． 2017
第
期
电
子
学
报
2017
10
ACTA ELECTRONICA SINICA
年
月
K- medoids
命名数据网络下基于
的
Hash
簇内
路由机制
， ，
鄢 欢 高德云 苏 伟
(
，
北京交通大学电子信息工程学院 北京
100044)
:
( Named Data Networking，NDN) ，
是以内容为中心的新型网络架构 其随处缓存策略存在
摘
要
命名数据网络
、 ， ．
缓存冗余过多 邻居缓存利用率低等问题 导致缓存空间的浪费及缓存效率的低下 本文提出的融合沿路径非协作和
( K-Medoids Hash Routing，KMHR) ，
使用
K-medoids
，
算法选取层次簇内的中心点 并针对不
路径外协作的缓存路由机制
Hash
， ， ，
路由及最短路径路由 保证簇内高流行度内容的精确定位和唯一性 降低缓存冗余 提
同流行度的内容分别采用
．
高缓存效率 通过真实网络拓扑仿真得出
，KMHR
、
机制具有最低的请求时间 最优的路由增益和较少的缓存内容数量
．
:
;
; K-medoids
; Hash
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
命名数据网络 层次簇
算法
路由
:
TP393
:
A
: 0372-2112 ( 2017) 10-2313-10
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 10． 001
文献标识码
文章编号
电子学报
K-medoids Based Intra-Cluster Hash Routing for
Named Data Networking
YAN Huan，GAO De-yun，SU Wei
( College of Electronics and Information Engineering，Beijing Jiaotong University，Beijing 100044，China)
Abstract: Named Data Networking ( NDN) is a new content-centric architecture． Its original Leave Copy Everywhere
( LCE) strategy has many shortcomings，for instance，massive cache redundancy and poor utilization of neighbors’cache，
which waste cache space and lower cache efficiency． We proposed a routing scheme named K-Medoids Hash Routing ( KM-
HR) combining on-path non-cooperation and off-path cooperation schemes． K-medoids algorithm is used to select some con-
tent routers as medoids in hierarchical clusters． And for different popularity of contents，we choose Hash routing or the shor-
test path routing separately． KMHR locates and insures the uniqueness of contents with high popularity in the cluster，which
significantly reduces cache redundancy and improves cache efficiency． Based on the real world network topology，simulation
results show that KMHR has the shortest request time，optimal routing gain and fewer cached contents．
Key words: named data networking; hierarchical cluster; K-medoids algorithm; Hash routing
［3］
NDN
ICN
，
的一种典型架构 其用内容名称路由取代
是
1
引言
［4］
IP
， (
并且路由器具有缓存功能 称为内容路
地址路由
，
随着面向内容的应用极速增长 人们对于信息服
) ， ，
由器 也可以响应用户的请求 从而减少用户的访问
［1］
．
务及数据内容的需求也不断增加 根据思科的预测
，
，
时间 降低内容源服务器的负载
．
2019
，
年 互联网视频相关的流量将占据所有消费者
到
NDN
LCE，
原始的缓存路由机制为随处缓存机制
80%
．
以上 而现有互联网以主机为中心
互联网流量的
的网络架构及端到端的传输范式将难以满足未来信息
( Information Cen-
( Interest) ( Forwarding Infor-
包按照转发信息表
即请求
mation Base，FIB)
，
的条目寻找所需内容 并在待定兴趣
．
，
服务发展的要求 因此 信息中心网络
( Pending Interest Table，PIT) Interest
表
中记录
Interest
包的转发
包转发的反向路
( Content
［2］
tric Network，ICN)
，
将信息内容本身作为通信主体 不
．
痕迹 应答数据
( Data)
包沿着
， ．
再关注内容的位置 是对现有互联网架构的变革 其中
，
，
径返回 并依次缓存在内容路由器的内容缓存
: 2016-06-15;
: 2016-06-18;
:
责任编辑 郭游
收稿日期
修回日期
:
基金项目 国家
973
( No． 2013CB329100) ;
( No． 61232017)
国家自然科学基金重点项目
重点基础研究发展规划
2314
2017
年
电
子
学
报
［3］
Store，CS)
．
，
但相对于数量庞大的内容而言 缓存空
． ， ，
心层和边缘层 其中 核心层路由器无缓存空间 仅提供
中
． ，
间极其有限 此外 每个内容路由器无区别的缓存内容
，
快速转发和路由 且该路由器组成唯一的无簇首的核
，
将导致网络中存在大量的缓存冗余 不仅浪费稀缺的
( Core Cluster，CC) ．
，
边缘层的路由器有缓存功能
心簇
，
缓存空间 而且缓存的内容被频繁替换使得缓存效率
，
尽可能地响应用户请求 且该内容路由器可分为多个
．
低下 因此
LCE
．
机制虽易于部署但可行性较差
( Edge Cluster，EC) ，
每个簇包含三类内容路由
边缘簇
， ，
为减少缓存冗余 提高缓存效率 国内外的研究人
:
，
，
:
器 簇首 网关和成员 功能分别为
簇首是其他成员及网关选举出来的簇控制器 功
Hash
．
员提出了多种优化方案 这些方案根据路由及缓存的
( on-path) ( off-path) ，
根
，
位置可以分为沿路径
据内容路由器之间是否协作可分为协作式及非协作
LCE
与路径外
．
映射的更新
能是收集和维护内容流行度排序及
网关是两个簇之间的边界内容路由器 功能是判
Hash
，
．
．
机制即为沿路径非协作式机制 文献
式 上述的
，
．
标志位
断请求内容在本簇的流行度排序 维护
成员是除了簇首和网关之外的内容路由器 成为
接入内容路由器的成员同样计算请求内容的流行度排
Hash
［5］
提出了另一种沿路径非协作机制
Prob( p)
即每个内
．
p
容路由器采用固定的概率 缓存内容
．
［6］
Probcache
容路由器的缓存概率 使距离内容请求者近的内容路
，Probcache
通过动态估计路径的缓存容量得到内
，
． ，
标志位 其他成员则检测标志位 执行相
序 维护
应的路由机制
内容提供者和内容请求者不是簇成员 因此二者
，
．
由器以更大的概率缓存内容
属于沿路径协
，
［5］
［7］
．
作式缓存路由机制 同类的机制还有
LCD ，Betw
，
，
的移动并不会影响簇结构 使得层次簇网络模型具有
［8］
CATT ． LCD
中只有缓存命中处的下游内容路由器缓
．
良好的移动性
2． 1
簇首选举
． Betw
存内容
中介 中 心 性
CATT
要求内容仅缓存在传输路径上具有最大
( Betweenness Centrality) ．
的 内 容 路 由 器
［12］
基于权重的边缘簇首选举算法是对文献 中方
，
机制利用势能路由转发请求 并将内容随机缓存
，
案的改进 如公式
( 1)
．
所示 该算法包含三个影响因子
:
－ 1
，
在沿路径的某个内容路由器处 并相互通告缓存信息
．
d
， T
传输时延 和权重跳数
v
H ．
为
v
邻居节点度的倒数
v
上述优化机制中不同路径的内容路由器独立地做
，
了确保计算是在相同维度下进行 我们将这三个影响
， ，
出缓存决策 易产生重复缓存 因此文献
［9］－［11］
提
．
因子进行归一化处理 最终具有最小权重的节点将被
，
出路径外协作式缓存路由方案来减少缓存冗余 提高
．
选举为簇首
［9］
． CoRC
邻近内容路由器的缓存利用
Hash
为固定长度的内容发布者标识
机制 将内容名称
1 /d
T
H
v
v
v
W =
v
+
+
α
3
( 1)
α
α
1
2
( Publisher Identifi-
avg( 1 /d)
avg( T)
avg( H)
+ = 1．
α α
er，PID) ，
并根据
PID
，
进行分区 内容路由器通过查找
， ， ， ，
其中 α α α 是权重因子 且 α
1
+
2
3
1
2
3
－ 1
PID
， ．
转发请求 且只缓存属于本分区的内容 文献
［10］
( 1) ，d
中
v ．
是节点 的邻居节点数量 若
d
在公式
v
v
，
针对视频流点播服务提出一种协作缓存策略 即将内
， v ．
越小 则说明节点 的邻居节点越多 邻居节点度倒数
V0
Hash
，
到相应的内容路由器 并引入协作路由表
容序号
1
－ 1
－ 1
avg( d
)
=
d
( i
( V ) ) ， ( V )
∈Ω Ω
0
的平均值
是所有节点的集合
∑
i
0
及协作缓存表记录其他内容路由器的路由和缓存信
V
i
= 1
0
［11］
． SCAN
息
机制 的内容路由器通过扫描内容路由表找
．
M
，
到邻近内容 同时采用布隆过滤器压缩需交互的内容
1
T
传输时延 定义为
v
T =
v
t ，
vj
t
其中 是从节
vj
∑
M
，
路由表 缓解可扩展性问题
．
j = 1
v
j ( v
到相邻节点 的传输时延 ∈Ω
( V ) ，j ( M) ，M
∈Ω
0
点
以上文献设计的沿路径缓存路由机制无法有效利
＜ V ) ， ( M)
Ω
0
v ． ，
是节点 相邻节点的集合 显然 传输时
，
用路径外的缓存资源 而路径外缓存路由机制则缺乏
， ． ，
延越小 散播消息的速度越快 同样 平均传输时延
avg
．
对缓存通告开销及内容请求特征方面的考虑 因此本
V0
1
，
文采纳二者的优势 提出基于
K-medoids
Hash
的簇内
( T) =
T ( i
i
( V ) ) ．
∈Ω
0
∑
V
i = 1
0
． ，
路由机制 该机制在层次簇网络架构下 通过执行
Hash
H
．
描述了簇内的拓扑关系 为了减少收
权重跳数
v
;
算法唯一地定位并缓存高流行度内容 对于低流行度
，
集和发布消息的开销 从簇首到其他簇内节点的跳数
， ，
的内容 则用最短路径路由获取 并以概率缓存在沿路
．
越小越好 因此权重跳数的计算公式为
:
， ， ．
径的非中心点中 从而降低缓存冗余 提高缓存命中 此
1
1
1
1
2
j
， ，
外 通告消息的范围缩小到各簇 降低通告开销
．
H =
v
H +
v
H +
v
H
( 2)
β
β
β ∑
3
1
2
v
n
n
j = 3 n
1
2
j
2
层次簇网络模型
n ，n ，…，n
2
v
分别是到节点 的距离为
j
1
，2
跳 跳和
其中
1
1
2
j
( 2 ) ． H ，H ，…，H
多跳 大于 跳 的节点数量 分别是与节
v
，
本文提出的层次簇网络模型共有两层 分别为核
v
v
全部评论(0)