Temporal Issues in Cyber-Physical Systems

David Broman, Patricia Derler, John Eidson

Abstract


This paper reviews the use of time, clocks, and clock synchronization protocols in cyber-physical systems (CPS). Recent advances in the area of timing suggest avenues of research and potential new application areas. We discuss how introducing timestamps and clocks can help overcome issues such as latency, jitter, and determining correct execution order. Furthermore, we show how system complexity can be reduced and distribution as well as parallelism can be done deterministically. We also point to recent work in raising time to first class citizen status in modeling and implementation. In particular, we describe design and execution environments of CPS and specialized hardware such as predictable timing architectures where time plays a key role.

Keywords


Timestamps; Clocks; Synchronization; Ordering; Simultaneity; Discrete event systems; Distributed control; Real-time systems; PTIDES

Full Text:

PDF

References


Timing Committee Telecommunications and Timing Group- Range Commanders Council, “IRIG Serial time code formats,” September, 2004. [Online]. Available: http://www.irigb.com/pdf/wp-irig-200-04.pdf

NIST, “Radio station WWV.” [Online]. Available: http://www.nist.gov/ pml/div688/grp40/

H. Kopetz, Real-Time Systems : Design Principles for Distributed Embedded Applications. Springer, 1997.

J. Rushby and W. Steiner, “TTA and PALS: Formally veried design patterns for distributed cyber-physical systems,” in 30th IEEE/AIAA Digital Avionics Systems Conference (DASC), Seattle, WA, 2011.

ARINC, “ARINC 653 family of standards,” November, 2010. [Online]. Available: https://www.arinc.com/cf/store/

As-2d2 Deterministic Ethernet And Unified Networking, “AS6820 Time-Triggered Ethernet,” SAE, Standard Specification, November 1, 2011.

L. Atzori, A. Iera, and G. Morabito, “The internet of things: A survey,” Computer Networks, vol. 54, no. 15, pp. 2787–2805, 2010.

M. Zorzi, A. Gluhak, S. Lange, and A. Bassi, “From today’s intranet of things to a future internet of things: a wireless-and mobility-related view,” Wireless Communications, IEEE, vol. 17, no. 6, pp. 44–51, 2010.

ITU, “Network synchronization and time distribution performance,” 2013. [Online]. Available: http://www.itu.int/en/ITU-T/studygroups/2013-2016/15/Pages/q13.aspx

M. Ouellette, K. Ji, S. Liu, and H. Li, “Using IEEE 1588 and boundary clocks for clock synchronization in telecom networks,” Communications Magazine, IEEE, vol. 49, no. 2, pp. 164–171, 2011.

J. Vig, “Quartz crystal resonators and oscillators for frequency control and timing applications - a tutorial,” April, 2012. [Online]. Available: http://www.ieee-uffc.org/frequency-control/learning-vig-tut.asp

Rakon, “RFPO40 SMD Oven Controlled Crystal Oscillator,” 2013.[Online]. Available: http://www.rakon.com/products/families/ocxo-ocso

Symmetricom, “SA.45s CSAC,” 2013. [Online]. Available: http: //www.symmetricom.com/products/frequency-references/

“Circular T,” BUREAU INTERNATIONAL DES POIDS ET

MESURES, Tech. Rep. 303, April 10 2013.

A. Gupta, “Mitigation of GPS vulnerability using time transfer over microwave systems,” Telcordia -NIST - ATIS Workshop on Synchronization in Telecommunication Systems, 2013.

——, “GPS spoofing: A brief survey of methods, effects and counter measures,” Telcordia -NIST - ATIS Workshop on Synchronization in Telecommunication Systems, 2012.

J. Merrill, “GPS vulnerability and backing up critical infrastructure,” Telcordia -NIST - ATIS Workshop on Synchronization in Telecommunication Systems, 2012.

C. Curry and G. Jolly, “GPS jamming quantifying the threat interference of GPS anti-jam techniques with accurate time determination,” Telcordia -NIST - ATIS Workshop on Synchronization in Telecommunication Systems, 2013.

M. Weiss, “One way GPS time transfer,” 2013. [Online]. Available: http://tf.nist.gov/time/oneway.htm

IEEE Instrumentation and Measurement Society, “1588: IEEE standard for a precision clock synchronization protocol for networked measurement and control systems,” IEEE, Standard Specification, July 24, 2008.

D. Vook, B. Hamilton, A. Fernandez, J. Burch, and V. Srikantam,“Update on high precision time synchronization,” in Proceedings of the 2005 Conference on IEEE-1588, Zurich, CH, 2005.

D. Mohl and M. Renz, “Improved synchronization behavior in highly cascaded networks,” in International IEEE Symposium on Precision Clock Synchronization for Measurement, Control and Communication, Vienna, AT, 2007.

M. Lipinski, T. Wlostowski, J. Serrano, P. Alvarez, J. David, G. Cobas, A. Rubini, and P. Moreira, “Performance results of the first white rabbit installation for cngs,” in International IEEE Symposium on Precision Clock Synchronization for Measurement, Control and Communication, San Francisco, CA, 2012.

IEEE Computer Society, “IEEE standard for information technology– local and metropolitan area networks– part 3: CSMA/CD access method and physical layer specifications amendment 7: Media access control (mac) service interface and management parameters to support time synchronization protocols,” IEEE, Standard Specification, 2011.

B. Liskov, “Practical uses of synchronized clocks in distributed systems,” Distributed Computing, vol. 6, no. 4, pp. 211–219, 1993.

J. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford, “Spanner: Google’s Globally-Distributed Database,” in 10th USENIX Symposium on Operating Systems Design and Implementation, Hollywood, CA, 2012.

K. Harris, “An application of IEEE 1588 to industrial automation,” in Precision Clock Synchronization for Measurement, Control and Communication, 2008. ISPCS 2008. IEEE International Symposium on. IEEE, 2008, pp. 71–76.

M. Shepard, D. Fowley, R. Jackson, and D. King, “Implementation of IEEE Std.-1588 in a Networked I/O Node,” in Proceedings of the 2003 Workshop on IEEE-1588, NIST publication NISTIR 7070, Gaithersburg, MD, 2003. [Online]. Available: http://www.nist.gov/publication-portal.

cfm

Bruel & Kjaer, “Features and specifications,” 2013.

[Online]. Available: http://www.bksv.com/products/frontends/lanxi/ features-and-specifications.aspx

H. Mach, E. Grim, O. Holmeide, and C. Calley, “PTP enabled network for flight test data acquisition and recording,” in Precision Clock Synchronization for Measurement, Control and Communication, 2007.

ISPCS 2007. IEEE International Symposium on. IEEE, 2007, pp. 110– 115.

F. Steinhauser, C. Riesch, and M. Rudigier, “IEEE 1588 for time synchronization of devices in the electric power industry,” in Precision Clock Synchronization for Measurement Control and Communication (ISPCS), 2010 International IEEE Symposium on. IEEE, 2010, pp.

–6.

M. Lixia, C. Muscas, and S. Sulis, “Application of IEEE 1588 to the measurement of synchrophasors in electric power systems,” in Precision Clock Synchronization for Measurement, Control and Communication, 2009. ISPCS 2009. International Symposium on. IEEE, 2009, pp. 1–6.

M. Antonello, B. Baibussinov, P. Benetti, F. Boffelli, E. Calligarich, N. Canci, S. Centro, A. Cesana, K. Cieslik, D. Cline et al., “Precision measurement of the neutrino velocity with the ICARUS detector in the CNGS beam,” Journal of High Energy Physics, vol. 2012, no. 11, pp. 1–21, 2012.

P. Moreira, J. Serrano, T. Wlostowski, P. Loschmidt, and G. Gaderer, “White rabbit: Sub-nanosecond timing distribution over ethernet,” in Precision Clock Synchronization for Measurement, Control and Communication, 2009. ISPCS 2009. International Symposium on. IEEE, 2009, pp. 1–5.

G. Gaderer, P. Loschmidt, E. G. Cota, J. H. Lewis, J. Serrano, M. Cattin, P. Alvarez, P. M. Oliveira Fernandes Moreira, T. Wlostowski, J. Dedic, C. Prados, M. Kreider, R.Baer, S.Rauch, and T.Fleck, “The white rabbit project,” in Int. Conf. on Accelerator and Large Experimental Physics Control Systems, Kobe, Japan, 2009.

A. Benveniste and G. Berry, “The synchronous approach to reactive and real-time systems,” Proceedings of the IEEE, vol. 79, no. 9, pp. 1270–1282, 1991.

T. A. Henzinger, B. Horowitz, and C. M. Kirsch, “Giotto: A timetriggered language for embedded programming,” in EMSOFT 2001, vol. LNCS 2211. Tahoe City, CA: Springer-Verlag, 2001, pp. 166–184.

A. Ghosal, T. A. Henzinger, D. Iercan, C. M. Kirsch, and

A. Sangiovanni-Vincentelli, “A hierarchical coordination language for interacting real-time tasks,” in Sixth Annual Conference on Embedded Software (EMSOFT). Seoul, Korea: ACM, 2006.

W. Pree and J. Templ, “Modeling with the timing definition language (TDL),” in Automotive Software Workshop San Diego (ASWSD) on Model-Driven Development of Reliable Automotive Services, ser. LNCS.

San Diego, CA: Springer, 2006.

Y. Zhao, J. Liu, and E. A. Lee, “A programming model for

time-synchronized distributed real-time systems,” in 13th IEEE Real Time and Embedded Technology and Applications Symposium, 2007. RTAS ’07, April 2007, pp. 259 – 268. [Online]. Available: http://chess.eecs.berkeley.edu/pubs/325.html

P. Derler, J. Eidson, S. Goose, E. A. Lee, and M. Zimmer,

“Deterministic execution of ptides programs,” EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2013-65, May 2013. [Online]. Available: http://www.eecs.berkeley.edu/Pubs/ TechRpts/2013/EECS-2013-65.html

K. M. Chandy and J. Misra, “Distributed simulation: A case study in design and verification of distributed programs,” IEEE Trans. on Software Engineering, vol. 5, no. 5, pp. 440–452, 1979.

J. Eker, J. W. Janneck, E. A. Lee, J. Liu, X. Liu, J. Ludvig,

S. Neuendorffer, S. Sachs, and Y. Xiong, “Taming heterogeneity—the Ptolemy approach,” Proceedings of the IEEE, vol. 91, no. 2, pp. 127–144, 2003. [Online]. Available: http://www.ptolemy.eecs.berkeley.edu/publications/papers/03/TamingHeterogeneity/

P. Derler, J. Eidson, E. A. Lee, S. Matic, and M. Zimmer, “Modelbased development of deterministic, event-driven, real-time distributed systems,” in International Workshop on Model-Based Design with a Focus on Extra-Functional Properties (MBDEFP), 2011. [Online]. Available: http://chess.eecs.berkeley.edu/pubs/895.html

J. Zou, S. Matic, and E. Lee, “PtidyOS: A lightweight microkernel for Ptides real-time systems,” in Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, April 2012.

G. C. Buttazzo, Hard real-time computing systems: predictable scheduling algorithms and applications, 3rd ed. Springer, 2011.

R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenstr¨om, “The Worst-Case Execution-Time Problem - Overview of Methods and Survey of Tools,” ACM Transactions on Embedded Computing Systems, vol. 7, pp. 36:1– 36:53, May 2008.

R. Wilhelm, D. Grund, J. Reineke, M. Schlickling, M. Pister, and C. Ferdinand, “Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems,” IEEE Transactions on Computer Aided Design, vol. 28, no. 7, pp. 966 – 978, 2009.

J. Knoop, L. Kovcs, and J. Zwirchmayr, “Symbolic Loop Bound Computation for WCET Analysis,” in Perspectives of Systems Informatics, ser. LNCS, E. Clarke, I. Virbitskaite, and A. Voronkov, Eds. Springer, 2012, vol. 7162, pp. 227–242.

J. Gustafsson, A. Ermedahl, C. Sandberg, and B. Lisper, “Automatic derivation of loop bounds and infeasible paths for WCET analysis using abstract execution,” in Proceedings of the 27th IEEE International Real-Time Systems Symposium (RTSS’06). IEEE, 2006, pp. 57–66.

P. Cousot and R. Cousot, “Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints,” in Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, ser. POPL ’77. New York, USA: ACM Press, 1977, pp. 238–252.

C. Ferdinand and R. Wilhelm, “Efficient and precise ache behavior prediction for real-time systems,” Real-Time Systems, vol. 17, no. 2, pp. 131–181, 1999.

Y.-T. Li and S. Malik, “Performance analysis of embedded software using implicit path enumeration,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, no. 12, pp. 1477–1487, 1997.

S. A. Edwards and E. A. Lee, “The case for the precision timed (pret) machine,” in Proceedings of the 44th annual conference on Design automation, June 2007, pp. 264 – 265.

I. Liu, J. Reineke, D. Broman, M. Zimmer, and E. A. Lee, “A PRET Microarchitecture Implementation with Repeatable Timing and Competitive Performance,” in Proceedings of the 30th IEEE International Conference on Computer Design (ICCD 2012). IEEE, 2012.

E. Lee and D. Messerschmitt, “Pipeline interleaved programmable dsp’s: Synchronous data flow programming,” Acoustics, Speech and Signal Processing, IEEE Transactions on, vol. 35, no. 9, pp. 1334–1345, 1987.

R. Banakar, S. Steinke, B. Lee, M. Balakrishnan, and P. Marwedel, “Scratchpad memory: A design alternative for cache on-chip memory in embedded systems,” in In Tenth International Symposium on Hardware/ Software Codesign (CODES), Estes Park. ACM, 2002, pp. 73–78.

S. Andalam, P. Roop, and A. Girault, “Predictable multithreading of embedded applications using PRET-C,” in Proceedings of the 8th IEEE/ACM International Conference on Formal Methods and Models for Codesign (MEMOCODE). IEEE, 2010, pp. 159–168.

M. Schoeberl, “A Java processor architecture for embedded real-time systems,” Journal of Systems Architecture, vol. 54, no. 1-2, pp. 265 – 286, 2008.

D. Broman, E. A. Lee, S. Tripakis, and M. T¨orngren, “Viewpoints, formalisms, languages, and tools for cyber-physical systems,” in Proceedings of the 6th International Workshop on Multi-Paradigm Modeling, 2012.

Modelica—A Unified Object-Oriented Language for Physical Systems Modeling—Language Specification, 2012, http://www.modelica.org.

MathWorks, “The Mathworks - Simulink - Simulation and Model-Based Design,” http://www.mathworks.com/products/simulink/ [Last accessed:May 8, 2013].

D. Broman and J. G. Siek, “Modelyze: a gradually typed host language for embedding equation-based modeling languages,” EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2012-173, June 2012.

D. Broman, “High-confidence cyber-physical co-design,” in Proceedings of the Work-in-Progress (WiP) session of the 33rd IEEE Real-Time Systems Symposium (RTSS 2012), 2012, p. 12.

D. Broman, M. Zimmer, Y. Kim, H. Kim, J. Cai, A. Shrivastava, S. A. Edwards, and E. A. Lee, “Precision Timed Infrastructure: Design Challenges,” in Proceedings of the Electronic System Level Synthesis Conference (to appear). IEEE, 2013.


Refbacks

  • There are currently no refbacks.