Research on Wide Area Industrial Internet Scheduling Algorithm Based on Service Reachability
-
摘要: 工业互联网业务呈现出小规模、确定性的特征，通常运行在大规模、异构的网络环境中，业务的调度与功能链的编排难以与异构承载网资源匹配。基于此该文提出非工作保持型的多节点联合调度模型，首先采用全路径时间协调算法，将功能链从空间维度的拓扑编排扩展至时空维度；其次，针对网络节点中的同步调度问题，提出了基于紧急度的流调度算法来平滑时延抖动，进一步，将时间触发调度延拓到大规模、异构且非同步的承载网中，提出了虚拟到达队列编排算法，利用业务同步机制替代时间同步，保障了业务确定的可达性需求。仿真实验表明该文所提算法可提升业务的可达性，保障其满足及时性、准时性、协同性需求。Abstract: In the large-scale and heterogeneous network environment, the industrial Internet service has the characteristics of small scale and certainty, so it is difficult to match the resources of the heterogeneous bearer network with the scheduling of the service and the orchestration of the function chain. Based on this, a multi-node joint scheduling model based on Non-workconserving is proposed. First, the full-path time coordination algorithm is adopted to extend the function chain from the spatial dimension topological orchestration to the space-time dimension; Then, aiming at the problem of synchronous scheduling in network nodes, a flow scheduling algorithm based on urgency is proposed to smooth delay jittering, furthermore, time-triggered scheduling is extended to large-scale, heterogeneous and non-synchronous bearer networks. A virtual arrival queue scheduling algorithm is proposed, which uses service synchronization mechanism instead of time synchronization to ensure the reachability requirements of service determination. Simulation results show that the algorithm proposed in this paper can improve the accessibility of the service and ensure service can reach in time, on time or cooperatively.
-
Key words:
- Industrial internet /
- Deterministic network /
- Reachability /
- Business orchestration /
- Non-workconsering
-
表 2 全路径时间协调算法伪代码
全路径时间协调算法伪代码 (1) IF 不需要应用层编排 THEN (2) WHILE ${\boldsymbol{S}}$$\ne \varnothing$ (3) REMOVE P FROM S (4) Solve LP(P) (5) IF LP(P)具有可行解 THEN (6) ${{\boldsymbol{X}}^*}$成为LP(P)的最优基础解 (7) IF${{\boldsymbol{X}}^*}$满足约束条件 THEN (8) IF $\cos t({X^*}) < F$ THEN (9) 保留${{\boldsymbol{X}}^*}$，更新$F$ (10) ELSE (11) IF $\cos t({\rm{LP} }(P)) \ge F$ THEN (12) 进行剪枝 (13) ELSE 划分子问题 (14) ELSE (15) IF Q.count > 1 THEN (16) 对Q快速排序 (17) ELSE Return (18) FOR i 0 to Q.count – 1 BY 1 DO (19) $T_{Ai}^{ {j_{{\rm{con}}} } } = {T_{Pi} } + {\rm{Random}}$, $T_E^{{P_i}} = T_A^{{P_i}} - {T_{Pi}}$ (20) END 
下载: 导出CSV
表 3 实验结果1
P 虚拟到达(ms) 观测窗口(ms) 误差(ms) P1 12.384206 13.021408 0.637202 P2 11.253912 11.687653 0.433741 P3 10.897265 11.327356 0.430091
下载: 导出CSV
表 4 实验结果2
P 虚拟到达(ms) 观测窗口(ms) 误差(ms) P1 15.725614 27.684932 11.959318 P2 11.687306 24.394108 12.706802 P3 10.433697 25.870495 15.436798
下载: 导出CSV
表 6 SP算法实验结果
流 最小时延(ns) 最大时延(ns) 抖动(ns) DE1_1 5999 41599 35600 DE2_1 4799 24899 20100 DE2_2 4799 26233 21234 DE3_1 4799 33899 29100 DE3_2 4799 35233 30434 BG 17999 1829770 1811771
下载: 导出CSV
表 7 UIS算法实验结果
流 最小时延(ns) 最大时延(ns) 抖动(ns) DE1_1 42299 43299 1000 DE2_1 26299 27299 1000 DE2_2 27633 28633 1000 DE3_1 36299 37299 1000 DE3_2 37633 38633 1000 BG 72568 1829770 1757202
下载: 导出CSV
-
[1] 王俊文. 未来工业互联网发展的技术需求[J]. 电信科学, 2019, 35(8): 26–38. doi: 10.11959/j.issn.1000-0801.2019201WANG Junwen. Technical requirement of future industrial internet[J]. Telecommunications Science, 2019, 35(8): 26–38. doi: 10.11959/j.issn.1000-0801.2019201 [2] 黄韬, 汪硕, 黄玉栋, 等. 确定性网络研究综述[J]. 通信学报, 2019, 40(6): 160–176. doi: 10.11959/j.issn.1000-436x.2019119HUANG Tao, WANG Shuo, HUANG Yudong, et al. Survey of the deterministic network[J]. Journal on Communications, 2019, 40(6): 160–176. doi: 10.11959/j.issn.1000-436x.2019119 [3] NASRALLAH A, THYAGATURU A S, ALHARBI Z, et al. Ultra-low latency (ULL) networks: The IEEE TSN and IETF DetNet standards and related 5G ULL research[J]. IEEE Communications Surveys & Tutorials, 2019, 21(1): 88–145. doi: 10.1109/COMST.2018.2869350 [4] CAO Jiuyue, ZHANG Yan, AN Wei, et al. VNF-FG design and VNF placement for 5G mobile networks[J]. Science China Information Sciences, 2017, 60(4): 040302. doi: 10.1007/s11432-016-9031-x [5] YE Zilong, CAO Xiaojun, WANG Jianpin, et al. Joint topology design and mapping of service function chains for efficient, scalable, and reliable network functions virtualization[J]. IEEE Network, 2016, 30(3): 81–87. doi: 10.1109/MNET.2016.7474348 [6] BECK M T, BOTERO J F, and SAMELIN K. Resilient allocation of service function chains[C]. 2016 IEEE Conference on Network Function Virtualization and Software Defined Networks, Palo Alto, USA, 2016: 128–133. doi: 10.1109/NFV-SDN.2016.7919487. [7] MAXIM D and SONG Yeqiong. Delay analysis of AVB traffic in time-sensitive networks (TSN)[C]. The 25th International Conference on Real-Time Networks and Systems, Grenoble, France, 2017: 18–27. doi: 10.1145/3139258.3139283. [8] CAO Jingyue, CUIJPERS P J L, BRIL R J, et al. Tight worst-case response-time analysis for Ethernet AVB using eligible intervals[C]. 2016 IEEE World Conference on Factory Communication Systems, Aveiro, Portugal, 2016: 1–8. doi: 10.1109/WFCS.2016.7496507. [9] MOHAMMADPOUR E, STAI E, MOHIUDDIN M, et al. Latency and backlog bounds in time-sensitive networking with credit based shapers and asynchronous traffic shaping[C]. The 30th International Teletraffic Congress, Vienna, Austria, 2018: 1–6. doi: 10.1109/ITC30.2018.10053. [10] THIELE D, ERNST R, and DIEMER J. Formal worst-case timing analysis of Ethernet TSN's time-aware and peristaltic shapers[C]. Proceedings of 2015 IEEE Vehicular Networking Conference, Kyoto, Japan, 2015: 251–258. doi: 10.1109/VNC.2015.7385584. [11] CRACIUNAS S S, OLIVER R S, CHMELÍK M, et al. Scheduling real-time communication in IEEE 802.1Qbv time sensitive networks[C]. The 24th International Conference on Real-Time Networks and Systems, Brest, France, 2016: 183–192. doi: 10.1145/2997465.2997470. [12] NAYAK N G, DÜRR F, and ROTHERMEL K. Incremental flow scheduling and routing in time-sensitive software-defined networks[J]. IEEE Transactions on Industrial Informatics, 2018, 14(5): 2066–2075. doi: 10.1109/TII.2017.2782235 [13] NOVAK A, SUCHA P, and HANZALEK Z. Efficient algorithm for jitter minimization in time-triggered periodic mixed-criticality message scheduling problem[C]. The 24th International Conference on Real-Time Networks and Systems, Brest, France, 2016: 23–31. doi: 10.1145/2997465.2997481. [14] WAN Tao and ASHWOOD-SMITH P. A performance study of CPRI over Ethernet with IEEE 802.1Qbu and 802.1Qbv enhancements[C]. 2015 IEEE Global Communications Conference, San Diego, USA, 2015: 1–6. doi: 10.1109/GLOCOM.2015.7417599. [15] CHITIMALLA D, KONDEPU K, VALCARENGHI L, et al. 5G fronthaul-latency and jitter studies of CPRI over Ethernet[J]. Journal of Optical Communications and Networking, 2017, 9(2): 172–182. doi: 10.1364/JOCN.9.000172 [16] LIEBEHERR J and YILMAZ E. Workconserving vs. non-workconserving packet scheduling: An issue revisited[C]. 1999 Seventh International Workshop on Quality of Service. IWQoS'99. (Cat. No.98EX354), London, UK, 1999: 248–256. doi: 10.1109/IWQOS.1999.766500. [17] HAN K E, SONG J, KIM D U, et al. Grant-aware scheduling algorithm for VOQ-based input-buffered packet switches[J]. ETRI Journal, 2018, 40(3): 337–346. doi: 10.4218/etrij.2017-0057 [18] MEI Lichun, QIAO Lufeng, CHEN Qinghua, et al. A Packet Dispatching Scheme with Load Balancing Based on iSLIP for Satellite Onboard CIOQ Switches[M]. LIANG Qilian, MU Jiasong, WANG Wei, et al. Communications, Signal Processing, and Systems. Singapore: Springer, 2016: 77–85. doi: 10.1007/978-981-10-3229-5_9. [19] AKGÜNGÖR A P and KORKMAZ E. Investigating parameter interactions with the factorial design method: Webster's optimal cycle length model[J]. Tehnički Vjesnik, 2018, 25(S2): 391–395. doi: 10.17559/TV-20170908185847 [20] KOLPAKOV R M and POSYPKIN M A. On the best choice of a branching variable in the subset sum problem[J]. Discrete Mathematics and Applications, 2018, 28(1): 29–34. doi: 10.1515/dma-2018-0004 [21] MEDHAT A M, CARELLA G, LÜCK C, et al. Near optimal service function path instantiation in a multi-datacenter environment[C]. The 11th International Conference on Network and Service Management, Barcelona, Spain, 2015: 336–341. doi: 10.1109/CNSM.2015.7367379. [22] DIEMER J, THIELE D, and ERNST R. Formal worst-case timing analysis of Ethernet topologies with strict-priority and AVB switching[C]. The 7th IEEE International Symposium on Industrial Embedded Systems, Karlsruhe, Germany, 2012: 1–10. doi: 10.1109/SIES.2012.6356564. -
下载:
图(9) / 表(7)
计量
- 文章访问数: 849
- HTML全文浏览量: 476
- PDF下载量: 89
- 被引次数: 0
