{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T15:54:26Z","timestamp":1782834866199,"version":"3.54.5"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007569","name":"Carl-Zeiss-Stiftung","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007569","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,6,13]]},"abstract":"<jats:p>\n            Networks are integral parts of modern safety-critical systems and certification demands the provision of guarantees for data transmissions. Deterministic Network Calculus (DNC) can compute a worst-case bound on a data flow's end-to-end delay. Accuracy of DNC results has been improved steadily, resulting in two DNC branches: the classical algebraic analysis and the more recent optimization-based analysis. The optimization-based branch provides a theoretical solution for tight bounds. Its computational cost grows, however, (possibly super-)exponentially with the network size. Consequently, a heuristic optimization formulation trading accuracy against computational costs was proposed. In this article, we challenge optimization-based DNC with a new algebraic DNC algorithm. We show that:\n            <jats:list>\n              <jats:list-item>\n                <jats:p>no current optimization formulation scales well with the network size and<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>algebraic DNC can be considerably improved in both aspects, accuracy and computational cost.<\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>\n          <jats:p>To that end, we contribute a novel DNC algorithm that transfers the optimization's search for best attainable delay bounds to algebraic DNC. It achieves a high degree of accuracy and our novel efficiency improvements reduce the cost of the analysis dramatically. In extensive numerical experiments, we observe that our delay bounds deviate from the optimization-based ones by only 1.142% on average while computation times simultaneously decrease by several orders of magnitude.<\/jats:p>","DOI":"10.1145\/3084453","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Quality and Cost of Deterministic Network Calculus"],"prefix":"10.1145","volume":"1","author":[{"given":"Steffen","family":"Bondorf","sequence":"first","affiliation":[{"name":"University of Kaiserslautern, Kaiserslautern, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Nikolaus","sequence":"additional","affiliation":[{"name":"University of Kaiserslautern, Kaiserslautern, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens B.","family":"Schmitt","sequence":"additional","affiliation":[{"name":"University of Kaiserslautern, Kaiserslautern, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2015.20"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9153-1"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 10th International Conference on Performance Evaluation Methodologies and Tools (ValueTools).","author":"Bondorf Steffen","year":"2016","unstructured":"Steffen Bondorf and Fabien Geyer . 2016 . Generalizing Network Calculus Analysis to Derive Performance Guarantees for Multicast Flows . In Proceedings of the 10th International Conference on Performance Evaluation Methodologies and Tools (ValueTools). Steffen Bondorf and Fabien Geyer. 2016. Generalizing Network Calculus Analysis to Derive Performance Guarantees for Multicast Flows. In Proceedings of the 10th International Conference on Performance Evaluation Methodologies and Tools (ValueTools)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCN.2010.5735738"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4108\/icst.Valuetools.2014.258167"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE Conference on Computer Communications (INFOCOM). 235--243","author":"Bondorf Steffen","unstructured":"Steffen Bondorf and Jens B. Schmitt . 2015. Boosting Sensor Network Calculus by Thoroughly Bounding Cross-Traffic . In Proceedings of the IEEE Conference on Computer Communications (INFOCOM). 235--243 . Steffen Bondorf and Jens B. Schmitt. 2015. Boosting Sensor Network Calculus by Thoroughly Bounding Cross-Traffic. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM). 235--243."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4108\/eai.14-12-2015.2262565"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of GI\/ITG International Conference on Measurement, Modelling and Evaluation of Dependable Computer and Communication Systems (MMB & DFT).","author":"Bondorf Steffen","unstructured":"Steffen Bondorf and Jens B. Schmitt . 2016. Improving Cross-Traffic Bounds in Feed Forward Networks -- There is a Job for Everyone . In Proceedings of GI\/ITG International Conference on Measurement, Modelling and Evaluation of Dependable Computer and Communication Systems (MMB & DFT). Steffen Bondorf and Jens B. Schmitt. 2016. Improving Cross-Traffic Bounds in Feed Forward Networks -- There is a Job for Everyone. In Proceedings of GI\/ITG International Conference on Measurement, Modelling and Evaluation of Dependable Computer and Communication Systems (MMB & DFT)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 13th International Conference on Quantitative Evaluation of Systems (QEST).","author":"Bondorf Steffen","unstructured":"Steffen Bondorf and Jens B. Schmitt . 2016. Should Network Calculus Relocate? An Assessment of Current Algebraic and Optimization- based Analyses . In Proceedings of the 13th International Conference on Quantitative Evaluation of Systems (QEST). Steffen Bondorf and Jens B. Schmitt. 2016. Should Network Calculus Relocate? An Assessment of Current Algebraic and Optimization- based Analyses. In Proceedings of the 13th International Conference on Quantitative Evaluation of Systems (QEST)."},{"key":"e_1_2_1_10_1","unstructured":"Anne Bouillard. 2014. Algorithms and efficiency of Network calculus. Habilitation thesis \u00c9cole Normale Sup\u00e9rieure. (2014).  Anne Bouillard. 2014. Algorithms and efficiency of Network calculus. Habilitation thesis \u00c9cole Normale Sup\u00e9rieure. (2014)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2008.04.008"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4108\/ICST.VALUETOOLS2008.4349"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833708"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.016"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Anne Bouillard and Giovanni Stea. 2015. Exact Worst-Case Delay in FIFO-Multiplexing Fee  Anne Bouillard and Giovanni Stea. 2015. Exact Worst-Case Delay in FIFO-Multiplexing Fee","DOI":"10.1109\/TNET.2014.2332071"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10626-007-0028-x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/WFCS.2008.4638728"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 6th European Congress on Embedded Real Time Software and Systems (ERTS) .","author":"Boyer Marc","year":"2012","unstructured":"Marc Boyer , Nicolas Navet , and Marc Fumey . 2012 . Experimental assessment of timing verification techniques for AFDX . In Proceedings of the 6th European Congress on Embedded Real Time Software and Systems (ERTS) . Marc Boyer, Nicolas Navet, and Marc Fumey. 2012. Experimental assessment of timing verification techniques for AFDX. In Proceedings of the 6th European Congress on Embedded Real Time Software and Systems (ERTS) ."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the IEEE Conference on Computer Communications (INFOCOM).","author":"Bu Tian","year":"2002","unstructured":"Tian Bu and Don Towsley . 2002 . On Distinguishing between Internet Power Law Topology Generators . In Proceedings of the IEEE Conference on Computer Communications (INFOCOM). Tian Bu and Don Towsley. 2002. On Distinguishing between Internet Power Law Topology Generators. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM)."},{"key":"e_1_2_1_21_1","volume-title":"Performance Guarantees in Communication Networks","author":"Chang Cheng-Shang","unstructured":"Cheng-Shang Chang . 2000. Performance Guarantees in Communication Networks . Springer-Verlag , New York, NY . Cheng-Shang Chang. 2000. Performance Guarantees in Communication Networks. Springer-Verlag, New York, NY."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.61109"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.61110"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646464.691395"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 6th European Congress on Embedded Real Time Software and Systems (ERTS).","author":"Frances Fabrice","year":"2006","unstructured":"Fabrice Frances , Christian Fraboul , and J\u00e9r\u00f4me Grieu . 2006 . Using Network Calculus to optimize the AFDX network . In Proceedings of the 6th European Congress on Embedded Real Time Software and Systems (ERTS). Fabrice Frances, Christian Fraboul, and J\u00e9r\u00f4me Grieu. 2006. Using Network Calculus to optimize the AFDX network. In Proceedings of the 6th European Congress on Embedded Real Time Software and Systems (ERTS)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2016.7402269"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2013.40"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787479"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1450058.1450083"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1987.1096719"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12104-3_18"},{"key":"e_1_2_1_33_1","volume-title":"In Proceedings of the 24th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS). 313--318","author":"Lampka Kai","unstructured":"Kai Lampka , Steffen Bondorf , and Jens B. Schmitt . 2016. Achieving Efficiency without Sacrificing Model Accuracy: Network Calculus on Compact Domains . In In Proceedings of the 24th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS). 313--318 . Kai Lampka, Steffen Bondorf, and Jens B. Schmitt. 2016. Achieving Efficiency without Sacrificing Model Accuracy: Network Calculus on Compact Domains. In In Proceedings of the 24th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS). 313--318."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45318-0"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2008.04.002"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the IEEE International Conference on Emerging Technologies and Factory Automation (ETFA). 1--8.","author":"Li Xiaoting","year":"2010","unstructured":"Xiaoting Li , Jean-Luc Scharbarg , and Christian Fraboul . 2010 . Improving end-to-end delay upper bounds on an AFDX network by integrating offsets in worst-case analysis . In Proceedings of the IEEE International Conference on Emerging Technologies and Factory Automation (ETFA). 1--8. Xiaoting Li, Jean-Luc Scharbarg, and Christian Fraboul. 2010. Improving end-to-end delay upper bounds on an AFDX network by integrating offsets in worst-case analysis. In Proceedings of the IEEE International Conference on Emerging Technologies and Factory Automation (ETFA). 1--8."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2830865.2830893"},{"key":"e_1_2_1_38_1","unstructured":"Frank Ruskey. 2003. Combinatorial Generation. Working version of book in progress.  Frank Ruskey. 2003. Combinatorial Generation. Working version of book in progress."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 20th Conference on Computers and Their Applications (CATA). 326--332","author":"Schi\u00f8ler Henrik","year":"2005","unstructured":"Henrik Schi\u00f8ler , Jan Jakob Jessen , Jens Dalsgaard Nielsen , and Kim Guldstrand Larsen . 2005 . Network Calculus for Real Time Analysis of Embedded Systems with Cyclic Task Dependencies . In Proceedings of the 20th Conference on Computers and Their Applications (CATA). 326--332 . Henrik Schi\u00f8ler, Jan Jakob Jessen, Jens Dalsgaard Nielsen, and Kim Guldstrand Larsen. 2005. Network Calculus for Real Time Analysis of Embedded Systems with Cyclic Task Dependencies. In Proceedings of the 20th Conference on Computers and Their Applications (CATA). 326--332."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2008.228"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of GI\/ITG International Conference on Measurement, Modelling and Evaluation of Computer and Communication Systems (MMB).","author":"Schmitt Jens B.","year":"2008","unstructured":"Jens B. Schmitt , Frank A. Zdarsky , and Ivan Martinovic . 2008 . Improving Performance Bounds in Feed-Forward Networks by Paying Multiplexing Only Once . In Proceedings of GI\/ITG International Conference on Measurement, Modelling and Evaluation of Computer and Communication Systems (MMB). Jens B. Schmitt, Frank A. Zdarsky, and Ivan Martinovic. 2008. Improving Performance Bounds in Feed-Forward Networks by Paying Multiplexing Only Once. In Proceedings of GI\/ITG International Conference on Measurement, Modelling and Evaluation of Computer and Communication Systems (MMB)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.813040"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/PCCC.2010.5682300"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.1.83"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2671008"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084453","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:22Z","timestamp":1750217422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084453"}},"subtitle":["Design and Evaluation of an Accurate and Fast Analysis"],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,6,13]]}},"alternative-id":["10.1145\/3084453"],"URL":"https:\/\/doi.org\/10.1145\/3084453","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}