This is an open access article published by the IET under the Creative Commons Attribution-NonCommercial-NoDerivs License (http://creativecommons.org/licenses/by-nc-nd/3.0/)
In this study the authors are interested in safety-critical real-time applications implemented on distributed architectures supporting the time-sensitive networking (TSN) standard. The on-going standardisation of TSN is an IEEE effort to bring deterministic real-time capabilities into the IEEE 802.1 Ethernet standard supporting safety-critical systems and guaranteed quality-of-service. TSN will support time-triggered (TT) communication based on schedule tables, audio-video-bridging (AVB) flows with bounded end-to-end latency as well as best-effort messages. The authors first present a survey of research related to the optimisation of distributed cyber-physical systems using real-time Ethernet for communication. Then, the authors formulate two novel optimisation problems related to the scheduling and routing of TT and AVB traffic in TSN. Thus, the authors consider that they know the topology of the network as well as the set of TT and AVB flows. The authors are interested to determine the routing of both TT and AVB flows as well as the scheduling of the TT flows such that all frames are schedulable and the AVB worst-case end-to-end delay is minimised. The authors have proposed an integer linear programming formulation for the scheduling problem and a greedy randomised adaptive search procedure-based heuristic for the routing problem. The proposed approaches have been evaluated using several test cases.
References
-
-
1)
-
6. Eppstein, D.: ‘Finding the K shortest paths’, SIAM J. Comput., 1999, 28, (2), pp. 652–673 (doi: 10.1137/S0097539795290477).
-
2)
-
7. Krommenacker, N., Rondeau, E., Divoux, T.: ‘Genetic algorithms for industrial Ethernet network design’. Proc. of IEEE Int. Workshop on Factory Communication Systems, 2002, pp. 149–156.
-
3)
-
37. Zhao, L., Xiong, H., Zheng, Z., et al: ‘Improving worst-case latency analysis for rate-constrained traffic in the Time-Triggered Ethernet network’, IEEE Commun. Lett., 2014, 18, (11), pp. 1927–1930 (doi: 10.1109/LCOMM.2014.2358233).
-
4)
-
8. Tămaş-Selicean, D., Pop, P., Madsen, J.: ‘Design of mixed-criticality applications on distributed real-time systems’. , Technical University of Denmark, 2014.
-
5)
-
22. Craciunas, S.S., Serna Oliver, R.: ‘Combined task-and network-level scheduling for distributed time-triggered systems’, Real-Time Syst., 2016, 52, (2), pp. 161–200 (doi: 10.1007/s11241-015-9244-x).
-
6)
-
12. Specht, J., Samii, S.: ‘Urgency-based scheduler for time-sensitive switched ethernet networks’. Proc. of Euromicro Conf. on Real-time Systems, 2016, pp. 75–85.
-
7)
-
25. Pozo, F., Steiner, W., Rodríguez-Navas, G., et al: ‘A decomposition approach for SMT-based schedule synthesis for time-triggered networks’. Proc. of Conf. on Emerging Technologies AND Factory Automation, 2015, pp. 1–8.
-
8)
-
38. Tămaş-Selicean, D., Pop, P., Steiner, W.: ‘Timing analysis of rate constrained traffic for the TTEthernet communication protocol’. Proc. Int. Symp. on Real-Time Distributed Computing, 2015, pp. 119–126.
-
9)
-
1. Rushby, J.: ‘A comparison of bus architectures for safety-critical embedded systems’. , Computer Science Laboratory, SRI International, 2001.
-
10)
-
27. Craciunas, S.S., Serna Oliver, R., Chmelík, M.: ‘Scheduling real-time communication in IEEE 802.1Qbv time sensitive networks’. Proc. of Int. Conf. on Real-Time Networks and Systems, 2016.
-
11)
-
42. Garey, M.R., Johnson, D.S.: ‘Computers and intractability: a guide to the theory of NP-completeness’ (W. H. Freeman & Co., 1979, 1st edn.).
-
12)
-
24. Steiner, W.: ‘Synthesis of static communication schedules for mixed-criticality systems’. Proc. Int. Symp. on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops, 2011, pp. 11–18.
-
13)
-
10. Konak, A., Smith, A.E.: ‘Network reliability optimization’, in Resende, Mauricio G.C., Pardalos, Panos M (Eds.): ‘Handbook of optimization in telecommunications’ (Springer, 2006, 1st edn.), pp. 735–760.
-
14)
-
40. Bordoloi, U., Aminifar, A., Eles, P., et al: ‘Schedulability analysis of ethernet AVB switches’. Proc. Embedded and Real-Time Computing Systems and Applications Conf., 2014, pp. 1–10.
-
15)
-
19. Tămaş-Selicean, D., Pop, P., Steiner, W.: ‘Design optimization of TTEthernet-based distributed real-time systems’, Real-Time Syst., 2014, 51, (1), pp. 1–35 (doi: 10.1007/s11241-014-9214-8).
-
16)
-
11. Gavrilut, V., Tămaş-Selicean, D., Pop, P.: ‘Fault-tolerant topology selection for TTEthernet networks’. Proc. Safety and Reliability of Complex Engineered Systems Conf., 2015, pp. 4001–4009.
-
17)
-
28. Dürr, F., Nayak, N.G.: ‘No-wait packet scheduling for IEEE time-sensitive networks (TSN)’. Proc. Int. Conf. on Real-Time Networks and Systems, 2016.
-
18)
-
3. SAE: ‘AS6802: time-triggered ethernet’., 2011, p. 108.
-
19)
-
30. Saket, R., Navet, N.: ‘Frame packing algorithms for automotive applications’, J. Embedded Comput., 2006, 2, (1), pp. 93–102.
-
20)
-
31. EtherCAT Technology Group, ‘ETG 1000 EtherCAT Specification’ (EtherCAT Technology Group, 2013, 1st edn.).
-
21)
-
23. Steiner, W.: ‘An evaluation of SMT-based schedule synthesis for time-triggeredmulti-hop networks’. Proc. Real-Time Systems Symp., 2010, pp. 375–384.
-
22)
-
9. Kuo, W., Prasad, V.R.: ‘An annotated overview of system-reliability optimization’, IEEE Trans. Reliab., 2000, 49, (2), pp. 176–187 (doi: 10.1109/24.877336).
-
23)
-
16. Herpel, T., Kloiber, B., German, R., et al: ‘Routing of safety-relevant messages in automotive ECU networks’. Proc. Vehicular Technology Conf. Fall, 2009, pp. 1–5.
-
24)
-
13. Gavrilut, V., Pop, P.: ‘Traffic class assignment for mixed-criticality frames in TTEthernet’. SIGBED Review, 2016.
-
25)
-
2. Decotignie, J.D.: ‘Ethernet-based real-time and industrial communications’, Proc. IEEE, 2005, 93, (6), pp. 1102–1117 (doi: 10.1109/JPROC.2005.849721).
-
26)
-
35. Alderisi, G., Patti, G., Bello, L.: ‘Introducing support for scheduled traffic over IEEE audio video bridging networks’. Proc. Emerging Technologies Factory Automation Conf., 2013, pp. 1–9.
-
27)
-
41. De Azua, J.A.R., Boyer, M.: ‘Complete modelling of AVB in network calculus framework’. Proc. Int. Conf. on Real-Time Networks and Systems, Versaille, France, 2014, pp. 55–64.
-
28)
-
39. Diemer, J., Thiele, D., Ernst, R.: ‘Formal worst-case timing analysis of Ethernet topologies with strict-priority and AVB switching’. Proc. IEEE Intl. Symp. on Industrial Embedded Systems, 2012, pp. 1–10.
-
29)
-
33. Mikolasek, V., Ademaj, A., Racek, S.: ‘Segmentation of standard Ethernet messages in the Time-Triggered Ethernet’. Proc. Int. Conf. on Emerging Technologies and Factory Automation, 2008, pp. 392–399.
-
30)
-
36. Scharbarg, J.-L., Ridouard, F., Fraboul, C.: ‘A probabilistic analysis of end-to-end delays on an AFDX avionic network’, IEEE Trans. Ind. Inf., 2009, 5, (1), pp. 38–49 (doi: 10.1109/TII.2009.2016085).
-
31)
-
43. Valiant, L.G.: ‘The Complexity of enumeration and reliability problems’, SIAM J. Comput., 1979, 8, (3), pp. 410–421 (doi: 10.1137/0208032).
-
32)
-
18. Al Sheikh, A., Brun, O., Chéramy, M., et al: ‘Optimal design of virtual links in AFDX networks’, Real-Time Syst., 2013, 49, (3), pp. 308–336 (doi: 10.1007/s11241-012-9171-z).
-
33)
-
26. Suethanuwong, E.: ‘Scheduling time-triggered traffic in TTEthernet systems’. Proc. of Conf. on Emerging Technologies Factory Automation, 2012, pp. 1–4.
-
34)
-
17. Pedreiras, P., Almeida, L.: ‘Message routing inmulti-segment FTT networks: the isochronous approach’. Proc. of Parallel and Distributed Processing Symp., 2004, pp. 122–129.
-
35)
-
34. Meyer, P., Steinbach, T., Korf, F., et al: ‘Extending IEEE 802.1 AVB with timetriggered scheduling: a simulation study of the coexistence of synchronous and asynchronous traffic’. Proc. IEEE Vehicular Networking Conf., 2013, pp. 47–54.
-
36)
-
4. ARINC: ‘Aircraft data network, part 7, avionics full-duplex switched ethernet network’. , 2009.
-
37)
-
38)
-
32. Ayed, H., Mifdaoui, A., Fraboul, C.: ‘Frame packing strategy within gateways for multicluster avionics embedded networks’. Proc. Emerging Technologies Factory Automation, 2012, pp. 1–8.
-
39)
-
14. Wang, B., Hou, J.C.: ‘Multicast routing and its QoS extension: problems, algorithms, and protocols’, IEEE Netw., 2000, 14, (1), pp. 22–36 (doi: 10.1109/65.819168).
-
40)
-
5. Feo, T.A., Resende, M.G.C.: ‘A probabilistic heuristic for a computationally difficult set covering problem’, Oper. Res. Lett., 1989, 8, (2), pp. 67–71 (doi: 10.1016/0167-6377(89)90002-3).
-
41)
-
20. Laursen, S.M., Pop, P., Steiner, W.: ‘Routing optimization of AVB streams in TSN networks’. SIGBED Review, 2016.
-
42)
-
29. Pop, P., Eles, P., Peng, Z.: ‘Schedulability-driven frame packing for multicluster distributed embedded systems’, ACM Trans. Embedded Comput. Syst., 2005, 4, (1), pp. 112–140 (doi: 10.1145/1053271.1053276).
-
43)
-
21. Zhang, L., Goswami, D., Schneider, R., et al: ‘Task-and network-level schedule co-synthesis of Ethernet-based time-triggered systems’. Proc. of Asia and South Pacific Design Automation Conf., 2014, pp. 119–124.
-
44)
-
15. Grammatikakis, M.D., Hsu, D., Kraetzl, M., et al: ‘Packet routing in fixed-connection networks: a survey’, J. Parallel Distrib. Comput., 1998, 54, (2), pp. 77–132 (doi: 10.1006/jpdc.1998.1483).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cps.2016.0021
Related content
content/journals/10.1049/iet-cps.2016.0021
pub_keyword,iet_inspecKeyword,pub_concept
6
6