A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 8 Issue 2
Feb.  2021

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2021  >  8(2): 478-490
Xi Jin, Changqing Xia, Nan Guan and Peng Zeng, "Joint Algorithm of Message Fragmentation and No-Wait Scheduling for Time-Sensitive Networks," IEEE/CAA J. Autom. Sinica, vol. 8, no. 2, pp. 478-490, Feb. 2021. doi: 10.1109/JAS.2021.1003844
Citation: Xi Jin, Changqing Xia, Nan Guan and Peng Zeng, "Joint Algorithm of Message Fragmentation and No-Wait Scheduling for Time-Sensitive Networks," IEEE/CAA J. Autom. Sinica, vol. 8, no. 2, pp. 478-490, Feb. 2021. doi: 10.1109/JAS.2021.1003844
shu

Joint Algorithm of Message Fragmentation and No-Wait Scheduling for Time-Sensitive Networks

doi: 10.1109/JAS.2021.1003844
Funds:  This work was partially supported by National Key Research and Development Program of China (2018YFB1700200), National Natural Science Foundation of China (61972389, 61903356, 61803368, U1908212), Youth Innovation Promotion Association of the Chinese Academy of Sciences, National Science and Technology Major Project (2017ZX02101007-004), Liaoning Provincial Natural Science Foundation of China (2020-MS-034, 2019-YQ-09), and China Postdoctoral Science Foundation (2019M661156)
More Information
    Abstract
  • Time-sensitive networks (TSNs) support not only traditional best-effort communications but also deterministic communications, which send each packet at a deterministic time so that the data transmissions of networked control systems can be precisely scheduled to guarantee hard real-time constraints. No-wait scheduling is suitable for such TSNs and generates the schedules of deterministic communications with the minimal network resources so that all of the remaining resources can be used to improve the throughput of best-effort communications. However, due to inappropriate message fragmentation, the real-time performance of no-wait scheduling algorithms is reduced. Therefore, in this paper, joint algorithms of message fragmentation and no-wait scheduling are proposed. First, a specification for the joint problem based on optimization modulo theories is proposed so that off-the-shelf solvers can be used to find optimal solutions. Second, to improve the scalability of our algorithm, the worst-case delay of messages is analyzed, and then, based on the analysis, a heuristic algorithm is proposed to construct low-delay schedules. Finally, we conduct extensive test cases to evaluate our proposed algorithms. The evaluation results indicate that, compared to existing algorithms, the proposed joint algorithm improves schedulability by up to 50%.

     

    • FullText(HTML)
  • loading
    • References(43)
  • [1]
    P. Pop, M. L. Raagaard, M. Gutierrez, and W. Steiner, “Enabling fog computing for industrial automation through time-sensitive networking (TSN),” IEEE Commun. Stand. Mag., vol. 2, no. 2, pp. 55–61, Jul. 2018. doi: 10.1109/MCOMSTD.2018.1700057
    [2]
    J. Lee and S. Park, “Time-sensitive network (TSN) experiment in sensorbased integrated environment for autonomous driving,” Sensors, vol. 19, no. 5, pp. 1–11, May 2019. doi: 10.1109/JSEN.2018.2885905
    [3]
    L. Huang, Y. Liang, Y. Zhang, Y. Wang, and Q. Wang, “Time-sensitive network technology and its application in energy internet, ” in Proc. IEEE Int. Conf. Energy Internet, 2019, pp. 211–216.
    [4]
    J. Jiang, Y. Li, S. H. Hong, A. Xu, and K. Wang, “A time-sensitive networking (TSN) simulation model based on OMNET++, ” in Proc. IEEE Int. Conf. Mechatronics and Automation, 2018, pp. 643–648.
    [5]
    S. S. Craciunas, R. S. Oliver, M. Chmelík, and W. Steiner, “Scheduling real-time communication in IEEE 802.1 Qbv time sensitive networks, ” in Proc. 24th Int. Conf. Real-Time Networks and Systems, 2016, pp. 183–192.
    [6]
    Cisco Systems, Inc. (2020) Cisco industrial Ethernet 4000, 4010 and 5000 switch software configuration guide. [Online]. Available: https://www.cisco.com. Accessed on: May 20, 2020.
    [7]
    N. Semiconductors. (2016) SJA1105 product data sheet. [Online]. Available: https://www.nxp.com/docs/en/data-sheet/SJA1105.pdf. Accessed on: May 20, 2020.
    [8]
    F. Dürr and N. G. Nayak, “No-wait packet scheduling for IEEE time-sensitive networks (TSN)” in Proc. 24th Int. Conf. Real-Time Networks and Systems, 2016, pp. 203–212.
    [9]
    X. Jin, F. Kong, L. Kong, W. Liu, and P. Zeng, “Reliability and temporality optimization for multiple coexisting WirelessHART networks in industrial environments,” IEEE Trans. Ind. Elect., vol. 64, no. 8, pp. 6591–6602, 2017. doi: 10.1109/TIE.2017.2682005
    [10]
    J. Tang, B. Shim, and T. Q. Quek, “Service multiplexing and revenue maximization in sliced C-RAN incorporated with URLLC and multicast eMBB,” IEEE J. Sel. Area. Commun., vol. 37, no. 4, pp. 881–895, 2019. doi: 10.1109/JSAC.2019.2898745
    [11]
    L. Kong, M. Xia, X. Y. Liu, G. Chen, Y. Gu, M. Y. Wu, and X. Liu, “Data loss and reconstruction in wireless sensor networks,” IEEE Trans. Parall. and Distrib. Sys., vol. 25, no. 11, pp. 2818–2828, 2013.
    [12]
    R. S. Oliver, S. S. Craciunas, and W. Steiner, “IEEE 802.1 Qbv gate control list synthesis using array theory encoding, ” in Proc. IEEE Real-Time and Embedded Technology and Applications Symp., 2018, pp. 13–24.
    [13]
    X. Jin, C. Xia, N. Guan, C. Xu, D. Li, Y. Yin, and P. Zeng, “Real-time scheduling of massive data in time sensitive networks with a limited number of schedule entries,” IEEE Access, vol. 8, no. 1, pp. 6751–6767, 2020.
    [14]
    N. G. Nayak, F. Dürr, and K. Rothermel, “Incremental flow scheduling and routing in time-sensitive software-defined networks,” IEEE Trans. Ind. Informat., vol. 14, no. 5, pp. 2066–2075, 2017.
    [15]
    M. L. Raagaard, P. Pop, M. Gutiérrez, and W. Steiner, “Runtime reconfiguration of time-sensitive networking (TSN) schedules for fog computing, ” in Proc. IEEE Fog World Congress, 2017, pp. 1–6.
    [16]
    V. Gavriluţ, L. Zhao, M. L. Raagaard, and P. Pop, “AVB-aware routing and scheduling of time-triggered traffic for TSN,” IEEE Access, vol. 6, no. 11, pp. 75 229–75 243, 2018.
    [17]
    J. Falk, F. Dürr, and K. Rothermel, “Exploring practical limitations of joint routing and scheduling for TSN with ILP, ” in Proc. 24th Int. Conf. on Embedded and Real-Time Computing Systems and Applications, 2018, pp. 136–146.
    [18]
    A. Nasrallah, A. S. Thyagaturu, Z. Alharbi, C. Wang, X. Shao, M. Reisslein, and H. Elbakoury, “Performance comparison of IEEE 802.1 TSN time aware shaper (TAS) and asynchronous traffic shaper (ATS),” IEEE Access, vol. 7, no. 4, pp. 44 165–44 181, 2019.
    [19]
    L. Zhao, P. Pop, Z. Zheng, and Q. Li, “Timing analysis of AVB traffic in TSN networks using network calculus, ” in Proc. IEEE Real-Time and Embedded Technology and Applications Symp., 2018, pp. 25–36.
    [20]
    I. Ferretti and L. Zavanella, “Batch energy scheduling problem with nowait/blocking constraints for the general flow-shop problem,” Procedia Manufacturing, vol. 42, no. 4, pp. 273–280, 2020.
    [21]
    F. Della Croce, A. Grosso, and F. Salassa, “Minimizing total completion time in the two-machine no-idle no-wait flow shop problem,” J. Heuristics, vol. 19, no. 10, pp. 1–15, 2019.
    [22]
    X. Wang, K. Xing, Y. Feng, and Y. Wu, “Scheduling of flexible manufacturing systems subject to no-wait constraints via Petri nets and heuristic search,” IEEE Trans. Syst.,Man,and Cybern.:Syst., vol. 49, no. 12, pp. 1–12, 2019. doi: 10.1109/TSMC.2019.2951261
    [23]
    M. Behnam, R. Marau, and P. Pedreiras, “Analysis and optimization of the MTU in real-time communications over switched Ethernet, ” in Proc. 16th Conf. Emerging Technologies and Factory Automation, 2011, pp. 1–7.
    [24]
    M. Ashjaei, M. Behnam, L. Almeida, and T. Nolte, “MTU configuration for real-time switched Ethernet networks,” J. Syst. Architect., vol. 70, no. 4, pp. 15–25, 2016.
    [25]
    K. B. Gemlau, J. Peeck, N. Sperling, P. Hertha, and R. Ernst, “A new design for data-centric Ethernet communication with tight synchronization requirements for automated vehicles, ” in Proc. 45th Ann. Conf. IEEE Industrial Electronics Society, 2019, pp. 4489–4494.
    [26]
    N. Chaudhari, K. C. Ananthoju, and S. Isac, “Comparative analysis of large data transfer in automotive applications using Ethernet switched networks, ” in Proc. Symp. Int. Automotive Technology, 2019.
    [27]
    B. Shin, J. Abdullayev, and D. Lee, “An efficient MAC layer packet fragmentation scheme with priority queuing for real-time video streaming, ” in Proc. IEEE 41st Conf. Local Computer Networks, 2016, pp. 69–77.
    [28]
    J. Abdullayev, B. Shin, and D. Lee, “A dynamic packet fragmentation extension to high throughput WLANs for real-time H264/AVC video streaming, ” in Proc. 10th Int. Conf. Future Internet, 2015, pp. 1–4.
    [29]
    I. Suciu, X. Vilajosana, and F. Adelantado, “An analysis of packet fragmentation impact in LPWAN, ” in Proc. IEEE Wireless Communications and Networking Conf., 2018, pp. 1–6.
    [30]
    S. A. Awwad, N. K. Noordin, B. M. Ali, F. Hashim, and N. H. A. Ismail, “6LoWPAN route-over with end-to-end fragmentation and reassembly using cross-layer adaptive backoff exponent,” Wirel. Pers. Commun., vol. 98, no. 1, pp. 1029–1053, 2018. doi: 10.1007/s11277-017-4907-7
    [31]
    X. Bao, Y. Zhang, D. Guo, and M. Song, “An optimization model for fragmentation-based routing in delay tolerant networks,” Science China Information Sciences, vol. 59, no. 1, pp. 1–16, 2016.
    [32]
    N. Naaman and R. Rom, “Packet scheduling with fragmentation, ” in Proc. 21st Ann. Joint Conf. IEEE Computer and Communications Societies, 2002, pp. 427–436.
    [33]
    E. Suethanuwong, “Message fragmentation of event-triggered traffic in TTEthernet systems using the timely block method, ” in Proc. Int. Conf. Computational Techniques in Information and Communication Technologies, 2016, pp. 450–458.
    [34]
    N. Semiconductors. (2017) Software user manual for SJA1105TEL. [Online]. Available: https://www.nxp.com/docs/en/user-guide/UM10944.pdf. Accessed on: May 20, 2020.
    [35]
    S. M. Laursen, P. Pop, and W. Steiner, “Routing optimization of AVB streams in TSN networks,” ACM Sigbed Review, vol. 13, no. 4, pp. 43–48, 2016. doi: 10.1145/3015037.3015044
    [36]
    V. Gavrilut, B. Zarrin, P. Pop, and S. Samii, “Fault-tolerant topology and routing synthesis for IEEE time-sensitive networking, ” in Proc. 25th Int. Conf. Real-Time Networks and Systems, 2017, pp. 267–276.
    [37]
    P. Jayachandran and T. Abdelzaher, “A delay composition theorem for real-time pipelines, ” in Proc. 19th Eur. Conf. Real-Time Systems, 2007, pp. 29–38.
    [38]
    A. Cimatti, A. Franzen, A. Griggio, R. Sebastiani, and C. Stenico, “Satisfiability modulo the theory of costs: foundations and applications,” in Proc. Int. Conf. Tools and Algorithms for the Construction and Analysis of Systems, 2010, pp. 99–113.
    [39]
    E. B. Clark, T. A. Henzinger, H. Veith, and R. Bloem, “Satisfiability modulo theories, ” Handbook of Model Checking, pp. 305–343, 2018.
    [40]
    J. Liu, Real-time Systems. Upper Saddle River, USA: Prentice Hall, 2000.
    [41]
    N. C. Audsley, “On priority asignment in fixed priority scheduling,” Inf. Process. Lett., vol. 79, no. 1, pp. 39–44, 2001. doi: 10.1016/S0020-0190(00)00165-4
    [42]
    A. Saifullah, Y. Xu, C. Lu, and Y. Chen, “End-to-end delay analysis for fixed priority scheduling in WirelessHART networks, ” in Proc. 17th IEEE Real-Time and Embedded Technology and Applications Symp., 2011, pp. 13–22.
    [43]
    N. Bjorner and A. D. Phan, “vZ – maximal satisfaction with Z3, ” in Proc. 6th Int. Symp. Symbolic Computation in Software Science, 2014, pp. 1–9.
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(15)  / Tables(2)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1365) PDF downloads(56) Cited by()

    Highlights

    • Under no-wait scheduling, fragmentation algorithms affect transmission delay because smaller packets have higher parallelism. However, smaller packets introduce more fragmentation overhead.
    • An optimization-modulo-theories specification for the joint problem of message fragmentation and no-wait scheduling is proposed to improve the schedulability of time-sensitive networks and reduce the overhead of fragmenting and reassembling.
    • The worst-case delays of messages are calculated based on a recursive function, and two corollaries are proposed on how to construct low-delay transmissions.
    • Based on the two corollaries, a joint algorithm is proposed that uses packets from large to small to construct schedules under hard real-time constraints. Thus, the proposed joint algorithm can strike a balance between temporality and overhead.

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return