第３８卷
Ｖ０ｌ＿３８ 第１２期
ＮＯ．１２ 计算机工程
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ２０１２年６月
Ｊｕｎｅ ２０１２
・多媒体技术及应用・ 文章编号：１０ｏ ＿３４２８（２０１２）１２—＿ｏ２２争＿＿ｏ３ 文献标识码：Ａ 中蟹分类号ｔ ＴＰ３
基于视频块的结构化时移流查询模型
于静洋ａ Ｓ任小金 ，
（河南大学ａ．计算机与信息工程学院；ｂ．网络信息中心，河南开封４７５００４）
摘要：针对基于结构化Ｐ２Ｐ的时移流系统的维护开销较大、扩展性较差等问题，提出一个基于视频块的结构化时移流查询模型。根据节
点缓存的首视频块进行分层，通过节点注册缓存中所有视频块的方法，降低层节点需要维护的路由信息，解决系统中缓存视频块不能完全
找到的问题。实验结果表明，该模型具有较高的缓存命中率、较好的查询性能和较低的维护开销。
关健词：时移流；查询性能；视频块；层节点；系统开销
Ｓｔｒｕｃｔｕｒｅｄ Ｔｉｍｅ－ｓｈｉｆｔｅｄ Ｓｔｒｅａｍｉｎｇ Ｑｕｅｒｙ Ｍｏｄｅｌ
Ｂａｓｅｄ ０ｎ Ｖｉｄｅｏ Ｂｌｏｃｋ
ＹＵ Ｊｉｎｇ—ｙａｎｇ ．ＲＥＮ Ｘｉａｏ－ｊｉｎ“
（ａ．Ｃｏｌｌｅｇｅ ｏｆＣｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ；ｂ．Ｎｅｔｗｏｒｋ Ｉｎｆｏｒｍａｔｉｏｎ Ｃｅｎｔｅｒ，Ｈｅｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｋａｉｆｅｎｇ ４７５００４，Ｃｈｉｎａ）
ＩＡｂｓｔｒａｅｔ］Ｉｎ ｔｈｅ ｃｕｒｒｅｎｔ，ｔｈｅ ｓｔｒｕｃｔｕｒｅｄ Ｐ２Ｐ—ｂａｓｅｄ ｔｉｍｅ—ｓｈｉＲｅｄ ｓｔｒｅａｍｉｎｇ ｓｙｓｔｅｍ ｅｘｉｓｔｓ ｔｈｅ ｐｒｏｂｌｅｍｓ ｔｈａｔ ｔｈｅ ｃｏｐｙ ｏｆ ｓｃａｌａｂｉｌｉｔｙ ｉｓ ｂａｄ ａｎｄ ｔｈｅ ｍａｉｎｔｅｎａｎｃｅ ｃｏｓｔｓ ａｒｅ ｈｉｇｈｅｒ．Ｆｏｒ ｒｅｓｏｌｖｉｎｇ ｔｈｅ ｐｒｏｂｌｅｍｓ，ａ ｓｔｒｕｃｔｕｒｅｄ ｑｕｅｒｙ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ｖｉｄｅｏ ｂｌｏｃｋ ｆｏｒ ｔｉｍｅ—ｓｈｉｆｔｅｄ ｓｔｒｅａｍｉｎｇ ｉｓ ｐｒｏｐｏｓｅｄ．Ｂｙ
ｔｈｅ ｈｉｅｒａｒｃｈｙ ｄｉｖｉｄｅｄ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｆｉｒｓｔ ｖｉｄｅｏ ｂｌｏｃｋ ｉｎ ｔｈｅ ｃａｃｈｅ ｏｆ ｎｏｄｅ ａｎｄ ａＵ ｖｉｄｅｏ ｂｌｏｃｋ ｉｎ ｔｈｅ ｃａｃｈｅ ｒｅｇｉｓｔｅｒｅｄ．ｉｔ ｍａｋｅｓ ｔｈｅ ｒｏｍｉｎｇ
ｉｎｆｏｒｍａｔｉｏｎ ｒｅｄｕｃｅｄ ｗｈｉｃｈ ｌａｙｅｒ ｎｏｄｅ ｎｅｅｄｓ ｔｏ ｍａｉｎｔａｉｎ ａｎｄ ｔｈｅ ｐｒｏｂｌｅｍ ｒｅｓｏｌｖｅｄ ｗｈｉｃｈ ｔｈｅ ｃｏｐｙ ｏｆ ｔｉｍｅ—ｓｈｉｆｔｅｄ ｓｔｒｅａｍｉｎｇ ｃａｎ ｎｏｔ ｂｅ ｆｕｌｌｙ ｆｏｕｎｄ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｏｔｈｅｒ ｍｏｄｅｌ，ｔｈｉｓ ｍｏｄｅｌ ｈａｓ ａ ｂｅｔｔｅｒ ｃａｃｈｅ ｈｉｔ ｒａｔｉｏ，ｂｅｔｔｅｒ ｌｏｏｋｕｐ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｌｏｗｅｒ ｍａｉｎｔｅｎａｎｃｅ
ｏｖｅｒｈｅａｄ． ［Ｋｅｙ ｗｏｒｄｓｌ ｔｉｍｅ－ｓｈｉｆｔｅｄ ｓｔｒｅａｍｉｎｇ；ｑｕｅｒｙ ｐｅｒｆｏｒｍａｎｃｅ；ｖｉｄｅｏ ｂｌｏｃｋ；ｌａｙｅｒ ｎｏｄｅ；ｓｙｓｔｅｍ ｏｖｅｒｈｅａｄ
ＤＯｈ １０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１２．１２．０６７
１概述
时移视频流是一种允许用户在观看直播视频的过程中进 行暂停、快进、快退、跳转等操作的服务，具有数据量大、
实时性要求高等特点，时移视频流对网络带宽、存储设备等
资源的需求较高，而传统的时移视频流服务是基于客户／服务 器模型的，在这种结构中，服务器容易形成瓶颈，因此，存
在单点失效、可扩展性差等问题。
为减少服务器端的带宽需求，近年来，人们开始研究基 于Ｐ２Ｐ＿Ｊ 的时移视频流 Ｊ，基于Ｐ２Ｐ的时移流可以降低服
务器的负担，并具有较好的可扩展性，但目前的系统仍然存
在一些问题，文献［３］设计了一个Ｐ２ＴＳＳ系统，在Ｐ２ＴＳＳ中，
由于其下层路由机制使用Ｐｓｅｕｄｏ—ＤＨＴ Ｊ，未考虑实际网络延
迟信息，因此平均延迟较大，另外，由于Ｐ２ＴＳＳ仅缓存开始
视频块后的视频块，因此所有参与节点都不缓存首视频块，
并且存在系统中存在的缓存块无法找到的问题。文献［４】针对
Ｐ２ＴＳＳ的这些问题，设计了ＤＲＰ－ＤＨＴ结构，从而提高了平 均查询延迟并解决了首视频块的缓存问题。ＤＲＰ—ＤＨＴ虽然改
进了系统的平均查询延迟并解决了首视频块的缓存问题，但
是由于其桥节点需要索引本层内所有节点以及所有桥节点的
信息，因此仍然存在３个问题：（１）桥节点容易形成瓶颈，可
扩展性较差；（２）系统中存在的时移流块副本无法完全找到；
（３）维护开销较大。 针对这些问题，本文设计一个基于视频块的结构化时移
流查询模型－－－ＶＢＤＨＴ（Ｓｔｒｕｃｔｕｒｅｄ Ｔｉｍｅ．ｓｈｉｆｔｅｄ Ｓｔｒｅａｍｉｎｇ Ｑｕｅｒｙ Ｍｏｄｅｌ Ｂａｓｅｄ ｏｎ Ｖｉｄｅｏ Ｂｌｏｃｋ），ＶＢＤＨＴ依据节点缓存
的第１个视频块进行分层，选择性能较高的节点作为层节点， 层节点负责所有的注册和路由信息，节点注册其缓存中的所
有视频块。
２基于视频块的结构化时移流查询模型
与ＤＲＰ－ＤＨＴ相似，在ＶＢＤＨＴ中，节点分为层节点和 层内节点。层节点是通过层内节点选举产生的，具有更高的
性能，层内节点为层上的普通节点。每个节点有２个ＩＤ，层 ＩＤ和层内ＩＤ，相同层的节点形成一个Ｃｈｏｒｄｔ６１环，并推举出
本层的一个节点为层节点，所有层节点也形成一个环，从而
形成分层结构。层ＩＤ通过哈希缓存中的第１个视频块索引
获得，层内ＩＤ使用文献［７］中的方法计算，使用文献［７】的方 法可以提高视频块的下载速度。
２．１ ＶＢＤＨＴ结构 在ＶＢＤＨＴ中，每个节点有２个ＩＤ，记为 ／ ，￡，表示
层ＩＤ， 表示层内ＩＤ。层节点是本层中具有更多资源的节
点，所有层节点形成Ｃｈｏｒｄ环。同一层内节点也形成一个 Ｃｈｏｒｄ环。层节点中有２套路由表，分别用于在层节点之间
的路由信息，即层问路由信息和层内节点之间的路由信息。
层内节点仅１套路由表，为层内节点之间的路由信息，节点
的路由表根据Ｃｈｏｒｄ协议生成，每个层内节点有一个指针分
别指向本层的层节点。图１为一个ｈ层ＶＢＤＨＴ实例，Ⅳ１ 、 Ⅳ１２０、Ⅳ】引、ⅣＩ”、Ⅳｌ 为层Ｉ中的节点，Ⅳ２ 、Ⅳ２３２、Ⅳ２４８、
Ⅳ２ 为层２中的节点， 、Ⅳ＾”、 ６６为层ｈ中的节点。其
作者倚介：于静洋（１９８０－），女，讲师、硕士，主研方向：视频流技 术，分布式计算；任小金，副教授、博士 收稿日期：２０１１—１０—２５ Ｅ－ｍａｉｌ：ｙｊｙ＠ｈｅｎｕ．ｅｄｕ．ｃ
ｎ ２２６ 计算机工程 ２０１２年６月２Ｏ日
中，Ｎｌ２０、Ｎ２４８、Ｎｈ 为层节点；Ｎｌ”、Ｎ２＂、 为分别是１、
２、ｈ层的备用层节点。图１表示层节点Ⅳｌ卯和层内节点Ⅳ 的路由表指针，Ⅳ，”的２套路由表分别指向层间和层内，Ⅳ
仅１套路由表，用于层内的路由。
圉圉圉
Ｎ／２￣的路由表 Ｎ１ ４８的路由表
图１ ＶＢＤＨＴ结构
２．２节点加入和离开 当一个节点需要播放一个时移流时，首先哈希需要播放
的时移流的首视频块的索引，并发送查询到层节点，查询内 容为这个值。根据哈希值在层节点中进行查询，如果查询到
相应的层节点，节点即加入本层，并设置自己的层ＩＤ为此哈
希值，层内ＩＤ通过文献［７］中的方式计算，加入协议使用
Ｃｈｏｒｄ的加入协议；如果此层不存在，产生一个新的层，此
节点作为本层的层节点。
当一个节点需要离开系统时，如果此节点为层节点，则
通知备份层节点接替自己的工作，备份层节点成为本层层节 点，并发布相应信息到层节点形成的环上，如果是层内节点，
则按Ｃｈｏｒｄ的离开协议即可。
２．３ ＶＢＤＨＴ上的注册 为了能共享缓存中的视频块，节点必须注册缓存中的视
频块。视频流为连续的视频块，每个视频块有一个索引值ｉ，
因此，在ＶＢＤＨＴ中，关键字为视频块的索引。文献【３—４］仅 注册缓存视频块的首视频块，这样容易造成系统中存在的缓
存视频块无法找到的情况，因此，在ＶＢＤＨＴ中，为了能够
尽可能地从节点缓存中获取视频块，每个节点注册缓存中的
所有视频块的索引，注册仅在层节点形成的环上注册。当一 个节点开始播放某一视频块时，首先哈希这个视频块的索引
值，然后运行注册程序ｒｅｇｉｓｔｅｒ（ｋｅｙ，ｖａｌｕｅ），其中，ｖａｌｕｅ为本
节点的网络地址、层地址、层内地址、注册时间、缓存大小
等信息。节点在播放视频块的同时开始缓存视频块，以便于
节点及时共享自己的缓存内容。
２．４ ＶＢＤＨＴ上的查询 当一个节点查询一个视频块ｉ时，发送ｒｅｔｒｉｅｖａｌ（／，ｉｉ）到层
节点形成的环上，其中，ｉｉ为发送节点的层内地址，ｒｅｔｒｉｅｖａｌ
（ｉ，ｉｉ）与Ｃｈｏｒｄ中的ｒｅｔｒｉｅｖａｌ（ｉ）不同之处在于ｒｅｔｒｉｅｖａｌ（／，ｉｉ）增加
了层内地址参数，其他与Ｃｈｏｒｄ中的ｒｅｔｒｉｅｖａｌ（ｉ）相同。
由于本文使用文献【７］中的方法生成层内地址，因此通过
比较层内地址的ＩＤ可以返回距离查询节点较近的节点，从而 提高视频块下载的速度。所有查询在层节点形成的环上进行。 当找到关键字ｉ的层节点时，如果层节点上没有此视频块的
注册信息，则返回空，如果有，则比较注册信息中的节点的 层内地址与查询节点的层内地址，并按距离最近的原则返回
相应注册的节点的ＩＰ等信息到发送节点。然后发送节点根据
返回的信息进行视频块的下载和播放。例如图１中节点 ”
查询视频块１，首先节点 ＂发送ｒｅｔｒｉｅｖａｌ（１，３３）到ｈ层的层
节点 ， 收到查询信息后，根据关键字１，找到索引节
点Ⅳ１ ，Ⅳ１ 为１层层节点，Ⅳ１ 上有视频块１的所有注册 信息，Ⅳｌ 计算与 ”的层内ＩＤ最近的层１内的节点，然后
返回此节点的网络地址、缓存大小等信息到发送节点 ”，
”收到返回信息后即可下载并播放视频块１。如果层１不
存在，则 发送请求视频块１的请求到服务器，从服务器
获取视频块１。
２．５层节点生成 层节点是本层节点中具有更多资源的节点，资源包括可
用带宽和存储容量。当一个节点需要加入某层时，如果系统
中还不存在这个层，则这个节点即作为本层的层节点，如果 层存在则作为层内节点加入到层。当一个结点 已经在层内
存在一段时间后，例如一个小时，结点ｎ可根据自身当前的
资源状况决定是否申请成为层节点。如果节点 具有一定的
资源，则与层节点协商，两者比较其资源情况，如果节点
的资源情况明显好于目前的层节点，则 拷贝层节点中的路
由信息，成为层节点，目前的层节点则成为层内节点。原层 节点中增加一条指向目前层节点的指针，以便其他节点与其
联系时，更换其层节点指针。如果ｎ的资源情况没有明显好
于目前的层节点，则ｎ接下来申请备用层节点，并与备用层
节点进行交互，过程和申请层节点类似，如果申请成功，则
成为备用层节点，备用层节点成为层内节点。
３实验结果与分析 为了评价ＶＢＤＨＴ，在ＰｌａｎｅｔＳｉｍ Ｊ上实现ＶＢＤＨＴ，缓存
算法使用ＩＰＰＩ＿４ Ｊ，ＩＰＰＩ是ＩＰＰ 的改进，ＩＰＰＩ针对ＩＰＰ中节点
的缓存内容从加入系统时间时所在的视频块或者初始播放视
频时间所在的视频块的下一个视频块开始存储所造成的问
题，因此，把初始存贮位置设在加入系统时间时所在的视频
块或者初始播放视频时间所在的视频块开始存储，从而提高
系统性能。 节点按照均匀分布的方式进入系统并一直保持到视频播
放过程结束。视频长度 为６０ ０００ Ｓ，比特率为１ Ｍｂ／ｓ，视 频块Ｑ设为１０ Ｓ。设置加入的节点５０％请求实时视频块，５０％
请求时移视频块。 执行２组模拟实验，第１组实验测试缓存性能，用具有
无限缓存空间的代理模式作为一个基线系统（称为Ｐｒｏｘｙ），无
限缓存空间的代理模式是系统能够达到的最好的缓存模型。
把ＶＢＤＨＴ、ＤＲＰ．ＤＨＴ、Ｐｓｅｕｄｏ—ＤＨＴ一起与基线系统的缓存
性能做比较。客户端缓存大小设置从１０ ＭＢ、５０ ＭＢ、１００ ＭＢ、
５００ ＭＢ、１ ０００ ＭＢ、５ ０００ ＭＢ、１０ ０００ ＭＢ到无限缓存字节。 使用缓存命中率作为评价标准。缓存命中率是在缓存中命中
的请求数与总的请求数的比值。缓存命中率越高，说明系统 能够更好地利用缓存数据，从而减少对服务器的访问次数，
降低服务器的压力。第２组实验测试查询性能和系统开销。
在这组实验中，为了简便，设置客户端缓存大小相等，每节 点为５００ ＭＢ缓存，则每节点可以存储５Ｏ个视频块。
３．１缓存命中率 第１组模拟实验中测试系统的缓存性能。假定１ ０００个
节点加入系统。图２分别列出了客户端缓存大小的增长与缓
存命中率的关系，其中，Ｐｒｏｘｙ表示的命中率是能够达到的