留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

面向航天器综合测试系统的Web缓存替换策略

杜建海 吕江花 高世伟 李倩倩 李勤勇 马世龙

杜建海, 吕江花, 高世伟, 等 . 面向航天器综合测试系统的Web缓存替换策略[J]. 北京航空航天大学学报, 2018, 44(8): 1609-1619. doi: 10.13700/j.bh.1001-5965.2017.0591
引用本文: 杜建海, 吕江花, 高世伟, 等 . 面向航天器综合测试系统的Web缓存替换策略[J]. 北京航空航天大学学报, 2018, 44(8): 1609-1619. doi: 10.13700/j.bh.1001-5965.2017.0591
DU Jianhai, LYU Jianghua, GAO Shiwei, et al. A Web cache replacement strategy for spacecraft comprehensive testing system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(8): 1609-1619. doi: 10.13700/j.bh.1001-5965.2017.0591(in Chinese)
Citation: DU Jianhai, LYU Jianghua, GAO Shiwei, et al. A Web cache replacement strategy for spacecraft comprehensive testing system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(8): 1609-1619. doi: 10.13700/j.bh.1001-5965.2017.0591(in Chinese)

面向航天器综合测试系统的Web缓存替换策略

doi: 10.13700/j.bh.1001-5965.2017.0591
基金项目: 

国家自然科学基金 61300007

中央高校基本科研业务费专项资金 YWF-15-GJSYS-106

中央高校基本科研业务费专项资金 YWF-14-JSJXY-007

软件开发环境国家重点实验室自由探索基金 SKLSDE-2015ZX-09

软件开发环境国家重点实验室自由探索基金 SKLSDE-2014ZX-06

详细信息
    作者简介:

    杜建海  男, 博士研究生。主要研究方向:机器学习、软件测试

    吕江花  女, 博士, 讲师。主要研究方向:机器学习、软件测试、形式化方法

    高世伟  男, 博士, 工程师。主要研究方向:软件测试、形式化方法、企业信息化、复杂系统评价

    李勤勇  男, 博士研究生。主要研究方向:决策支持系统、模型管理

    马世龙  男, 博士, 教授。主要研究方向:机器学习、软件测试、形式化方法、软件工程

    通讯作者:

    吕江花, E-mail: jhlv@nlsde.buaa.edu.cn

  • 中图分类号: TP301.6;TP393.0

A Web cache replacement strategy for spacecraft comprehensive testing system

Funds: 

National Natural Science Foundation of China 61300007

the Fundamental Research Funds for the Central Universities YWF-15-GJSYS-106

the Fundamental Research Funds for the Central Universities YWF-14-JSJXY-007

State Key Laboratory of Software Development Environment Free Exploration Fund SKLSDE-2015ZX-09

State Key Laboratory of Software Development Environment Free Exploration Fund SKLSDE-2014ZX-06

More Information
  • 摘要:

    航天器一般为复杂系统,其作为典型安全苛刻系统,在综合测试过程中会产生大量测试数据。在查询这些测试数据时,现有的B/S数据查询技术,每次查询时采用从数据库服务器中获取数据的方式,极大地消耗了数据库服务器的资源,占用了大量的网络带宽,导致系统的整体性能下降,用户体验不佳。通过对安全苛刻系统综合测试数据特点和用户查询特征的分析,基于经典Web缓存替换算法GDSF,提出一种适用于B/S数据查询系统的Web缓存替换算法GDSF-STW。该算法是在GDSF算法的基础上,引入了数据流挖掘中的时间衰减模型,并采用滑动时间窗口的思想,提高缓存命中率,从而提高系统的性能,改善用户体验。通过GDSF-STW与LRU、LFU、LFU-DA、GDSF等经典算法进行实验对比,结果表明,GDSF-STW算法具有更好的缓存命中率。

     

  • 图 1  Web缓存

    Figure 1.  Web caching

    图 2  GDSF-STW算法流程图

    Figure 2.  GDSF-STW algorithm flowchart

    图 3  命中率与衰减因子的关系

    Figure 3.  Relationship between hit ratio and decay factor

    图 4  命中率与滑动时间窗口大小的关系

    Figure 4.  Relationship between hit ratio and sliding window size

    图 5  命中率与缓存容量的关系

    Figure 5.  Relationship between hit ratio and cache capacity

    图 6  各算法命中率与缓存容量的关系

    Figure 6.  Relationship between hit ratio and cache capacity among multiple algorithms

    表  1  航天器综合测试数据表结构示例

    Table  1.   Spacecraft comprehensive testing data table structure example

    字段名称中文描述数据类型备注填写举例
    TIME时间信息TIMESTAMP主键
    2017-08-08
    09:00:00.000
    X001X001NUMBER3.38
    X002X002NUMBER9.88
    XXXXXXXXNUMBER38.08
    下载: 导出CSV

    表  2  日志记录格式

    Table  2.   Logging format

    日志记录
    参数
    参数列表
    说明
    日志记录
    参数示例
    查询提交时间查询参数列表包括多行,每行表示一条参数信息
    2017-03-19 08:08:31
    航天器型号XXXXXXXX
    测试阶段PHASE1
    查询开始时间2017-03-18 21:06:48
    查询结束时间2017-03-18 23:09:16
    是否查询源码信息true
    查询参数个数3
    DATE1, XX, XX, XX, …;
    查询参数列表DATE2, XX, XX, XX, …;
    DATE3, XX, XX, XX, …;
    下载: 导出CSV

    表  3  事务记录格式

    Table  3.   Transaction record format

    事务记录项事务记录项说明事务记录项示例
    查询提交时间事务TID随查询提交时间的增长而增长,相邻2个
    2017-03-19 08:08:31
    查询事务的TID相差1
    事务TID999888
    访问Web对象个数189
    XXXXXXXX_DATE1_XX_XX_XX_8_1000000xxxx
    Web对象列表Web对象列表用来记录Web对象的名称,每一行表XXXXXXXX_DATE2_XX_XX_XX_9_1000000xxxx
    示一个Web对象
    XXXXXXXX_DATEn_XX_XX_XX_3_100000xxxxx
    下载: 导出CSV
  • [1] KASTANIOTIS G, MARAGOS E, DOULIGERIS C, et al.Using data envelopment analysis to evaluate the efficiency of Web caching object replacement strategies[J].Journal of Network and Computer Applications, 2011, 35(2):803-817. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=JJ0226205436
    [2] ALI W, SHAMSUDDIN S M, ISMAIL A S.A survey of Web caching and prefetching[J].International Journal of Advances in Soft Computing and its Applications, 2011, 3(1):18-44. http://d.old.wanfangdata.com.cn/OAPaper/oai_doaj-articles_50ee21c55b6b53067008dc7ac8adeba5
    [3] PODLIPNIG S, BÖSZÖRMENYI L.A survey of Web cache replacement strategies[J].ACM Computing Surveys(CSUR), 2003, 35(4):374-398. doi: 10.1145/954339
    [4] CHENG K, KAMBAYASHI Y. Advanced replacement policies for WWW caching[C]//1st International Conference on Web-Age Information Management(WAIM 2000). Berlin: Springer, 2000: 239-244.
    [5] 张震波, 杨鹤标, 马振华.基于LRU算法的Web系统缓存机制[J].计算机工程, 2006, 32(19):68-70. doi: 10.3969/j.issn.1000-3428.2006.19.025

    ZHANG Z B, YANG H B, MA Z H.Web cache mechanism based on LRU algorithm[J].Computer Engineering, 2006, 32(19):68-70(in Chinese). doi: 10.3969/j.issn.1000-3428.2006.19.025
    [6] BRESLAU L, CAO P, FAN L, et al. Web caching and Zipf-like distributions: Evidence and implications[C]//18th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE Press, 1999, 1: 126-134.
    [7] SELVAKUMAR S, SAHOO S K, VENKATASUBRAMANI V.Delay sensitive least frequently used algorithm for replacement in Web caches[J].Computer Communications, 2004, 27(3):322-326. doi: 10.1016/S0140-3664(03)00215-9
    [8] YANG Q, ZHANG H H.Integrating Web prefetching and cach-ing using prediction models[J].World Wide Web, 2001, 4(4):299-321. doi: 10.1023/A:1015185802583
    [9] SHI L, ZHANG Y. Optimal model of Web caching[C]//4th International Conference on Natural Computation. Piscataway, NJ: IEEE Press, 2008, 7: 362-366.
    [10] STAROBINSKI D, TSE D.Probabilistic methods for Web cach-ing[J].Performance Evaluation, 2001, 46(2):125-137. https://www.sciencedirect.com/science/article/pii/S0166531601000451
    [11] 黄学雨, 钟艳青.基于多Markov链预测模型的Web缓存替换算法[J].微电子学与计算机, 2014, 31(5):36-40. http://d.old.wanfangdata.com.cn/Periodical/wdzxyjsj201405009

    HUANG X Y, ZHONG Y Q.Web cache replacement algorithm based on multi-Markov chains prediction model[J].Microelectronics & Computer, 2014, 31(5):36-40(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/wdzxyjsj201405009
    [12] MA K, YANG B, YANG Z, et al.Segment access-aware dynamic semantic cache in cloud computing environment[J].Journal of Parallel and Distributed Computing, 2017, 110:42-51. doi: 10.1016/j.jpdc.2017.04.011
    [13] YANG Q, ZHANG H H, LI T Y. Mining Web logs for prediction models in WWW caching and prefetching[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2001: 473-478.
    [14] SATHIYAMOORTHI V.A novel cache replacement policy for Web proxy caching system using Web usage mining[J].International Journal of Information Technology and Web Engineering (IJITWE), 2016, 11(2):1-13. doi: 10.4018/IJITWE
    [15] ALI W, SHAMSUDDIN S M, ISMAIL A S.Intelligent Web proxy caching approaches based on machine learning techniques[J].Decision Support Systems, 2012, 53(3):565-579. doi: 10.1016/j.dss.2012.04.011
    [16] ELAARAG H. A quantitative study of Web cache replacement strategies using simulation[M]//ELAARAG H. Web proxy cache replacement strategies. Berlin: Springer, 2013: 17-60.
    [17] KASTANIOTIS G, MARAGOS E, DIMITSAS V, et al. Web proxy caching object replacement: Frontier analysis to discover the good-enough algorithms[C]//The 15th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems. Piscataway, NJ: IEEE Press, 2007: 132-137.
    [18] OLANREWAJU R F, BABA A, KHAN B U I, et al. A study on performance evaluation of conventional cache replacement algorithms: A review[C]//20164th International Conference on Parallel, Distributed and Grid Computing (PDGC). Piscataway, NJ: IEEE Press, 2016: 550-556.
    [19] 高世伟, 吕江花, 乌尼日其其格, 等.航天器测试需求描述及其自动生成[J].北京航空航天大学学报, 2015, 41(7):1275-1286. http://bhxb.buaa.edu.cn/CN/abstract/abstract13322.shtml

    GAO S W, LV J H, WUNIRI Q Q G, et al.Spacecraft test requirement description and automatic generation method[J].Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(7):1275-1286(in Chinese). http://bhxb.buaa.edu.cn/CN/abstract/abstract13322.shtml
    [20] 陈辉. 载人航天器综合测试数据平台的设计与实现[D]. 北京: 北京航空航天大学, 2007: 12-27.

    CHEN H. Design and implementation of integration test data platform for manned spacecraft[D]. Beijing: Beihang University, 2007: 12-27(in Chinese).
    [21] 李先军. 面向航天器测试的测试语言及系统关键技术研究[D]. 北京: 北京航空航天大学, 2011: 12-27.

    LI X J. Research on key technologies of spacecraft test-oriented test language and system[D]. Beijing: Beihang University, 2011: 12-27(in Chinese).
    [22] 周扬发. Web代理服务器的缓存技术研究[D]. 北京: 北京邮电大学, 2014: 11-13. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y2724873

    ZHOU Y F. Research on caching technology of Web proxy ser-ver[D]. Beijing: Beijing University of Posts and Telecommunications, 2014: 11-13(in Chinese). http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y2724873
    [23] KREMPL G, ŽLIOBAITE I, BRZEZIN'SKI D, et al.Open cha-llenges for data stream mining research[J].ACM SIGKDD Explorations Newsletter, 2014, 16(1):1-10. doi: 10.1145/2674026
    [24] MARGARA A, URBANI J, VAN HARMELEN F, et al.Streaming the Web:Reasoning over dynamic data[J].Web Semantics:Science, Services and Agents on the World Wide Web, 2014, 25:24-44. doi: 10.1016/j.websem.2014.02.001
    [25] GUO Y, WANG G, HOU F, et al.Recent frequent item mining algorithm in a data stream based on flexible counter windows[J].Journal of Software, 2014, 9(1):258-263. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=Doaj000003663114
    [26] LI F, SUN Y, NI Z, et al. The utility frequent pattern mining based on slide window in data stream[C]//201215th International Conference on Intelligent Computation Technology and Automation(ICICTA). Piscataway, NJ: IEEE Press, 2012: 414-419.
    [27] JIANG X, PANG Y, PAN J, et al.Flexible sliding windows with adaptive pixel strides[J].Signal Processing, 2015, 110:37-45. doi: 10.1016/j.sigpro.2014.08.004
    [28] LIU X, IFTIKHAR N, XIE X. Survey of real-time processing systems for big data[C]//Proceedings of the 18th International Database Engineering & Applications Symposium. New York: ACM, 2014: 356-361.
    [29] GIANNELLA C, HAN J W, PEI J, et al.Mining frequent patterns in data streams at multiple time granularities[J].Next Generation Data Mining, 2003, 212:191-212. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=wjfz201707007
    [30] CHANG J H, LEE W S. Findingrecent frequent itemsets adaptively over online data streams[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. NewYork: ACM, 2003: 487-492.
    [31] PATIL J B, PAWAR B V. Trace driven simulation of GDSF# and existing caching algorithms for Web proxy servers[C]//The 9th WSEAS International Conference on Data Networks, Communications, Computers. Athens: WSEAS, 2007: 378-384.
    [32] 肖敬伟. 基于数据挖掘的缓存替换算法研究[D]. 北京: 北京交通大学, 2015: 11-13. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y2915471

    XIAO J W. Cache replacement algorithms based on data mining[D]. Beijing: Beijing Jiaotong University, 2015: 11-13(in Chinese). http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y2915471
    [33] CAO P, IRANI S. Cost-aware WWW proxy caching algorithms[C]//Proceedings of the USENIX Symposium on Internet Technologies and Systems Monterey. Berkeley: USENIX, 1997: 193-206.
  • 加载中
图(6) / 表(3)
计量
  • 文章访问数:  646
  • HTML全文浏览量:  113
  • PDF下载量:  568
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-09-25
  • 录用日期:  2017-10-27
  • 网络出版日期:  2018-08-20

目录

    /

    返回文章
    返回
    常见问答