基于自相似流的星上虚拟信道调度算法研究

南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (3): 515–521.

基于自相似流的星上虚拟信道调度算法研究

底晓强1,2* , 刘永霞1

出版日期:2018-05-23 发布日期:2018-05-23
作者简介:1. 长春理工大学计算机科学技术学院，长春，130022； 2. 长春理工大学空间光电技术国家地方联合工程研究中心，长春，130022
基金资助:
国家863计划(2015AA015701)，吉林省教育厅科研项目((JJKH20170630KJ)

Satellite Virtual Channel Scheduling Algorithms based on Self-Similar Traffic

Xiaoqiang Di1,2*, Yongxia Liu1

Online:2018-05-23 Published:2018-05-23
About author:1. School of Computer Science and Technology，Changchun University of Science and Technology, Changchun 130022, China; 2. NUERC of Space and Optoelectronics Technology, Changchun University of Science and Technology, Changchun 130022, Jilin, China

摘要/Abstract

摘要： 为分析虚拟信道调度算法对高级在轨系统(advanced orbit systems, AOS)中物理信道利用率的影响，研究了自相似流量模型下，先来先服务(FCFS)和时间片轮询(RR)虚拟信道调度算法的时延与积压。由于网络流量具有自相似特性，首先使用快速傅里叶变换(FFT)生成AOS自相似流量，然后对FCFS和RR虚拟信道调度算法进行仿真。仿真结果表明，到达数据量较少时，两种调度算法性能相当；到达数据量较大时，RR调度算法的时延和积压要明显小于FCFS调度算法，因此RR算法性能优于FCFS算法，使信道的利用率较高。研究结果可为AOS虚拟信道调度算法的设计提供参考。

Abstract: Considering the influence of virtual channel (VC) scheduling algorithm on the utilization of physical channel in AOS space communication system, we study the delay and backlog performance of first-come-first-served (FCFS) and round-robin (RR) VC scheduling algorithms in the self-similar traffic model. As the network traffic has self-similar characteristics, we adopt fast Fourier transform (FFT) approach to generate AOS self-similar traffic. Simultaneously, based on the self-similar traffic model, FCFS and RR VC scheduling algorithms are simulated on the Matlab simulation platform. The simulation results show that when the time is short and the amount of data arrived is small, the performances of the two kinds of scheduling algorithms are equivalent in AOS design; but if the amount of data arrived is large and simulation time is long enough, the delay and backlog of RR scheduling algorithm are obviously smaller than FCFS scheduling algorithm’s. Consequently, RR algorithm performance is significantly better than FCFS algorithm, RR can make the physical channel achieve higher utilization. It illustrates that the results of the study can serve as a reference for the design of AOS virtual channel scheduling algorithms.

底晓强1,2* , 刘永霞1. 基于自相似流的星上虚拟信道调度算法研究[J]. 南京大学学报(自然科学版), 2018, 54(3): 515–521.

Xiaoqiang Di1,2*, Yongxia Liu1. Satellite Virtual Channel Scheduling Algorithms based on Self-Similar Traffic[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(3): 515–521.

参考文献

[1] CCSDS. AOS space data link protocol. Recommendation for space data system standards. CCSDS 732.0-B-2. Washington DC: CCSDS 2006. (请核对修改是否正确) [2] 田庄, 张庆君. 载人航天器AOS虚拟信道调度策略研究. 航天器工程, 2006, 15(2): 20-26. (Tian Z, Zhang Q J. Research on manned spacecraft AOS virtual channel scheduling strategy. Spacecraft Engineering, 2006, 15(2): 20-26.) (未找到本条文献英文信息，请核对) [3] 刘立士, 李清凡, 田野等. 基于帧紧迫度的边界可移动虚拟信道调度算法. 科学技术与工程, 2014, 14(17): 97-103. (Liu L S, Li Q F, Tian Y, et al. A virtual channels scheduling algorithm of moving boundary based on frame urgency. Science Technology and Engineering, 2014, 14(17): 97-103.) [4] 赵运弢, 冯永新, 刘恒驰等. 基于自相似业务流的AOS延时累积调度算法. 系统工程与电子技术, 2015, 37(2): 417-422. (Zhao Y T, Feng Y X, Liu H C, et al. Scheduling algorithm of delay accumulated adaptive polling based on AOS self-similar traffic. Systems Engineering and Electronics, 2015, 37(2): 417-422.) [5] Leland W E, Taqqu M S, Willinger W, et al. On the self-similar nature of ethernet traffic (extended version). ACM/IEEE Transactions on Networking, 1994, 2(1): 1-15. [6] Crovella M E, Bestavros A. Self-similarity in world wide web traffic: Evidence and possible causes. IEEE/ACM Transactions on Networking, 1997, 5(6): 835-846. [7] Paxson V E, Floyd S. Wide-area traffic: The failure of poisson modeling. In: Conference on Communications Architectures, Protocols and Applications. London UK: ACM, 1994: 257-268. [8] Kadloor S, Gong X, Kiyavash N, et al. Low-cost side channel remote traffic analysis attack in packet networks. In: IEEE International Conference on Communications (ICC). Cape Town, South Africa: IEEE, 2010: 1-5. [9] Menth M, Schmid M, Heiss H, et al. MEDF-a simple scheduling algorithm for two real-time transport service classes with application in the UTRAN. In: The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies. San Francisco, USA: IEEE, 2003, 2: 1116-1122. [10] Norros I, Mannersalo P, Wang J L. Simulation of fractional brownian motion with conditionalized random midpoint displacement. Advances in Performance Analysis, 1999, 2: 77-101. (请核对年份) [11] 张华川, 田杰, 许静. 自相似网络流量模拟的分布式系统的设计与实现. 电子学报, 2009, 37(4A): 31-35, 30. (Zhang H C, Tian J, Xu J. The design and implementation of distributed system for self-similar network traffic simulation. Acta Electronica Sinica, 2009, 37(4A): 31-35, 30.) [12] Perrin E, Harba R, Jennane R, et al. Fast and exact synthesis for 1-D fractional Brownian motion and fractional Gaussian noises. IEEE Signal Processing Letters, 2002, 9(11): 382-384. [13] 吕军. 自相似网络流量的处理和分析. 清华大学学报(自然科学版), 2008, 48(7): 1186-1189. (Lü J. Analysis and processing of self-similar network traffic data. Journal of Tsinghua University (Science and Technology), 2008, 48(7): 1186-1189.) [14] Ledesma S, Liu D R. Synthesis of fractional gaussian noise using linear approximation for generating self-similar network traffic. ACM SIGCOMM Computer Communication Review, 2000, 30(2): 4-17. [15] 梁智涛, 何慧, 李斌. 自相似流量生成算法研究. 微计算机信息, 2008(6): 219-221, 193. (Liang Z T, He H, Li B. The study of algorithms generating self-similar traffic. Microcomputer Information, 2008(6): 219-221, 193.) [16] 张宾, 杨家海, 吴建平. Internet流量模型分析与评述. 软件学报, 2011, 22(1): 115-131. (Zhang B, Yang J H, Wu J P. Survey and analysis on the internet traffic model. Journal of Software, 2011, 22(1): 115-131.) [17] Norros I. On the use of fractional Brownian motion in the theory of connectionless networks. IEEE Journal on Selected Areas in Communications, 1995, 13(6): 953-962. [18] Paxson V. Fast, approximate synthesis of fractional Gaussian noise for generating self-similar network traffic. ACM SIGCOMM Computer Communication Review, 1997, 27(5): 5-18. [19] 曹坤勇, 于盛林. 基于正交小波变换的噪声下1/f类分形信号的恢复. 南京航空航天大学学报, 2004, 36(2): 245-248. (Cao K Y, Yu S L. Restoration of noisy 1/f-type fractal signal based on orthonormal wavelet transform. Journal of Nanjing University of Aeronautics & Astronautics, 2004, 36(2): 245-248.) [20] 朱灵蕾, 姚远程, 秦明伟. 自相似业务量生成方法研究及改进. 计算机工程, 2016, 42(7): 54-58. (Zhu L L, Yao Y C, Qin M W. Research and improvement of self-similar traffic generation method. Computer Engineering, 2016, 42(7): 54-58.)

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed