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

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

doi:10.13700/j.bh.1001-5965.2017.0591

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

doi: 10.13700/j.bh.1001-5965.2017.0591

1.
北京航空航天大学计算机学院, 北京 100083
2.
北京航天控制仪器研究所, 北京 100039

基金项目:

国家自然科学基金 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
计量
- 文章访问数: 764
- HTML全文浏览量: 154
- PDF下载量: 570
- 被引次数: 0
出版历程
- 收稿日期: 2017-09-25
- 录用日期: 2017-10-27
- 网络出版日期: 2018-08-20

A Web cache replacement strategy for spacecraft comprehensive testing system

1.
School of Computer Science and Technology, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
2.
Beijing Institute of Aerospace Control Devices, Beijing 100039, China

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

Corresponding author: LYU Jianghua, E-mail: jhlv@nlsde.buaa.edu.cn

摘要

摘要:
航天器一般为复杂系统，其作为典型安全苛刻系统，在综合测试过程中会产生大量测试数据。在查询这些测试数据时，现有的B/S数据查询技术，每次查询时采用从数据库服务器中获取数据的方式，极大地消耗了数据库服务器的资源，占用了大量的网络带宽，导致系统的整体性能下降，用户体验不佳。通过对安全苛刻系统综合测试数据特点和用户查询特征的分析，基于经典Web缓存替换算法GDSF，提出一种适用于B/S数据查询系统的Web缓存替换算法GDSF-STW。该算法是在GDSF算法的基础上，引入了数据流挖掘中的时间衰减模型，并采用滑动时间窗口的思想，提高缓存命中率，从而提高系统的性能，改善用户体验。通过GDSF-STW与LRU、LFU、LFU-DA、GDSF等经典算法进行实验对比，结果表明，GDSF-STW算法具有更好的缓存命中率。
- 航天器综合测试数据 /
- Web缓存替换算法 /
- 数据流挖掘 /
- 数据查询 /
- 安全苛刻系统
Abstract:
As a typical safety critical system, spacecraft is generally a complex system, which could produce a large amount of test data during the comprehensive testing process.When querying these test data, the existing B/S data query technology obtains data from the database server for each query, which greatly consumes the database server resources, takes up a lot of network bandwidth, and results in pooroverall performance of the system and poor user experience.Based on the classical Web cache replacement algorithm GDSF, this paper proposes a Web cache replacement algorithm GDSF-STW which is suitable for B/S architecture data query system by analyzing the characteristics of test data of the safety critical system and the behavior of user query.Based on the classical Web cache replacement algorithm GDSF, this algorithm introduces the time decay model in data mining and adopts the idea of sliding time window to improve the cache hit rate, system performance, and user experience. Finally, the experimental results show that the GDSF-STW has a better hit rate by comparing the GDSF-STW with the classical algorithms such as LRU, LFU, LFU-DA and GDSF.
- spacecraft comprehensive testing data /
- Web cache replacement algorithms /
- data stream mining /
- data query /
- safety critical system

HTML全文

图 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
X001	X001	NUMBER		3.38
X002	X002	NUMBER		9.88
┇	┇	┇		┇
XXXX	XXXX	NUMBER		38.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
事务TID		999888
访问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

参考文献(33)

[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.