{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:26:12Z","timestamp":1772119572691,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T00:00:00Z","timestamp":1692316800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T00:00:00Z","timestamp":1692316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Event Dyn Syst"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Network Calculus (NC) is an algebraic theory that represents traffic and service guarantees as curves in a Cartesian plane, in order to compute performance guarantees for flows traversing a network. NC uses transformation operations, e.g., min-plus convolution of two curves, to model how the traffic profile changes with the traversal of network nodes. Such operations, while mathematically well-defined, can quickly become unmanageable to compute using simple pen and paper for any non-trivial case, hence the need for algorithmic descriptions. Previous work identified the class of piecewise affine functions which are ultimately pseudo-periodic (UPP) as being closed under the main NC operations and able to be described finitely. Algorithms that embody NC operations taking as operands UPP curves have been defined and proved correct, thus enabling software implementations of these operations. However, recent advancements in NC make use of operations, namely the\n                    <jats:italic>lower pseudo-inverse<\/jats:italic>\n                    ,\n                    <jats:italic>upper pseudo-inverse<\/jats:italic>\n                    , and\n                    <jats:italic>composition<\/jats:italic>\n                    , that are well-defined from an algebraic standpoint, but whose algorithmic aspects have not been addressed yet. In this paper, we introduce algorithms for the above operations when operands are UPP curves, thus extending the available algorithmic toolbox for NC. We discuss the algorithmic properties of these operations, providing formal proofs of correctness.\n                  <\/jats:p>","DOI":"10.1007\/s10626-022-00373-5","type":"journal-article","created":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T04:02:26Z","timestamp":1692331346000},"page":"181-219","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Extending the network calculus algorithmic toolbox for ultimately pseudo-periodic functions: pseudo-inverse and composition"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9111-7471","authenticated-orcid":false,"given":"Raffaele","family":"Zippo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5277-0267","authenticated-orcid":false,"given":"Paul","family":"Nikolaus","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5310-6763","authenticated-orcid":false,"given":"Giovanni","family":"Stea","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,18]]},"reference":[{"key":"373_CR1","doi-asserted-by":"crossref","unstructured":"Andreozzi M, Conboy F, Stea G, Zippo R (2020) Heterogeneous systems modelling with adaptive traffic profiles and its application to worst-case analysis of a DRAM controller. In: 2020 IEEE 44th annual computers, software, and applications conference (COMPSAC). IEEE, pp 79\u201386","DOI":"10.1109\/COMPSAC48688.2020.00020"},{"key":"373_CR2","doi-asserted-by":"crossref","unstructured":"Bauer H, Scharbarg J-L, Fraboul C (2010) Worst-case end-to-end delay analysis of an avionics AFDX network. In: 2010 design, automation & test in Europe conference & exhibition (DATE 2010). IEEE, pp 1220\u20131224","DOI":"10.1109\/DATE.2010.5456993"},{"issue":"4","key":"373_CR3","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1109\/TNET.2002.801404","volume":"10","author":"JC Bennett","year":"2002","unstructured":"Bennett JC, Benson K, Charny A, Courtney WF, Le Boudec J-Y (2002) Delay jitter bounds and packet scale rate guarantee for expedited forwarding. IEEE\/ACM Trans Network 10(4):529\u2013540","journal-title":"IEEE\/ACM Trans Network"},{"key":"373_CR4","doi-asserted-by":"crossref","unstructured":"Bondorf S, Schmitt JB (2014) The DiscoDNC v2 \u2013 A comprehensive tool for deterministic network calculus. In: Proc. of the international conference on performance evaluation methodologies and tools. ValueTools \u201914, pp 44\u201349. https:\/\/dl.acm.org\/citation.cfm?id=2747659","DOI":"10.4108\/icst.valuetools.2014.258167"},{"key":"373_CR5","doi-asserted-by":"publisher","DOI":"10.1002\/9781119440284","volume-title":"Deterministic network calculus: from theory to practical implementation","author":"A Bouillard","year":"2018","unstructured":"Bouillard A, Boyer M, Le Corronc E (2018) Deterministic network calculus: from theory to practical implementation. Wiley, Hoboken"},{"key":"373_CR6","doi-asserted-by":"crossref","unstructured":"Bouillard A, Cottenceau B, Gaujal B, Hardouin L, Lagrange S, Lhommeau M, Thierry E (2009) COINC library: a toolbox for the network calculus. In: Proceedings of the 4th international conference on performance evaluation methodologies and tools, ValueTools (Vol. 9, p. 01).","DOI":"10.4108\/ICST.VALUETOOLS2009.8045"},{"issue":"1","key":"373_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10626-007-0028-x","volume":"18","author":"A Bouillard","year":"2008","unstructured":"Bouillard A, Thierry \u00c9 (2008) An algorithmic toolbox for network calculus. Discrete Event Dynamic Systems 18(1):3\u201349","journal-title":"Discrete Event Dynamic Systems"},{"key":"373_CR8","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.peva.2020.102124","volume":"143","author":"M Boyer","year":"2020","unstructured":"Boyer M, Graillat A, de Dinechin BD, Migge J (2020) Bounding the delays of the MPPA network-on-chip with network calculus:models and benchmarks. Perform Evaluation 143:102\u2013124. https:\/\/doi.org\/10.1016\/j.peva.2020.102124","journal-title":"Perform Evaluation"},{"key":"373_CR9","doi-asserted-by":"publisher","unstructured":"Boyer M, Stea G, Sofack WM (2012) Deficit Round Robin with network calculus. In: 6Th international ICST conference on performance evaluation methodologies and tools, cargese, corsica, france, october 9-12, 2012, pp 138\u2013147. https:\/\/doi.org\/10.4108\/valuetools.2012.250202","DOI":"10.4108\/valuetools.2012.250202"},{"key":"373_CR10","doi-asserted-by":"crossref","unstructured":"Chang C-S (2000) Performance guarantees in communication networks. Springer, New York","DOI":"10.1007\/978-1-4471-0459-9"},{"key":"373_CR11","doi-asserted-by":"crossref","unstructured":"Charara H, Scharbarg J-L, Ermont J, Fraboul C (2006) Methods for bounding end-to-end delays on an AFDX network. In: 18th Euromicro conference on real-time systems (ECRTS\u201906). IEEE, p 10","DOI":"10.1109\/ECRTS.2006.15"},{"issue":"1","key":"373_CR12","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1109\/18.61109","volume":"37","author":"RL Cruz","year":"1991","unstructured":"Cruz RL (1991) A calculus for network delay, part I: network elements in isolation. IEEE Trans Inform Theory 37(1):114\u2013131","journal-title":"IEEE Trans Inform Theory"},{"issue":"1","key":"373_CR13","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1109\/18.61110","volume":"37","author":"RL Cruz","year":"1991","unstructured":"Cruz RL (1991) A calculus for network delay, part II: network analysis. IEEE Trans Inform Theory 37(1):132\u2013141","journal-title":"IEEE Trans Inform Theory"},{"issue":"4","key":"373_CR14","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/j.comnet.2003.12.004","volume":"44","author":"M Fidler","year":"2004","unstructured":"Fidler M, Sander V (2004) A parameter based admission control for differentiated services networks. Comput Netw 44(4):463\u2013479","journal-title":"Comput Netw"},{"issue":"9","key":"373_CR15","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1109\/JPROC.2002.802002","volume":"90","author":"V Firoiu","year":"2002","unstructured":"Firoiu V, Le Boudec J-Y, Towsley D, Zhang Z-L (2002) Theories and models for internet quality of service. Proc IEEE 90(9):1565\u20131591","journal-title":"Proc IEEE"},{"key":"373_CR16","doi-asserted-by":"crossref","unstructured":"Guan N, Yi W (2013) Finitary real-time calculus: efficient performance analysis of distributed embedded systems. In: 2013 IEEE 34Th real-time systems symposium, pp 330\u2013339","DOI":"10.1109\/RTSS.2013.40"},{"key":"373_CR17","unstructured":"IEEE: Time-sensitive networking (TSN) task group (2020) [Online]. https:\/\/1.ieee802.org\/tsn\/. Accessed: 2022-05-16"},{"key":"373_CR18","doi-asserted-by":"crossref","unstructured":"Lampka K, Bondorf S, Schmitt JB, Guan N, Yi W (2017) Generalized finitary Real-Time calculus. In: Proc. of the 36th IEEE international conference on computer communications (INFOCOM 2017)","DOI":"10.1109\/INFOCOM.2017.8056981"},{"issue":"3","key":"373_CR19","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1109\/18.669170","volume":"44","author":"J-Y Le Boudec","year":"1998","unstructured":"Le Boudec J-Y (1998) Application of network calculus to guaranteed service networks. IEEE Trans Inf Theory 44(3):1087\u20131096. https:\/\/doi.org\/10.1109\/18.669170","journal-title":"IEEE Trans Inf Theory"},{"issue":"3","key":"373_CR20","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1109\/18.669170","volume":"44","author":"J-Y Le Boudec","year":"1998","unstructured":"Le Boudec J-Y (1998) Application of network calculus to guaranteed service networks. IEEE Trans Inform Theory 44(3):1087\u20131096","journal-title":"IEEE Trans Inform Theory"},{"key":"373_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45318-0","volume-title":"Network calculus: a theory of deterministic queuing systems for the internet","author":"J-Y Le Boudec","year":"2001","unstructured":"Le Boudec J-Y, Thiran P (2001) Network calculus: a theory of deterministic queuing systems for the internet. Springer, Berlin"},{"issue":"3-4","key":"373_CR22","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1561\/1300000059","volume":"11","author":"J Liebeherr","year":"2017","unstructured":"Liebeherr J (2017) Duality of the max-plus and min-plus network calculus. Foundations and Trends in Networking 11(3-4):139\u2013282. https:\/\/doi.org\/10.1561\/1300000059","journal-title":"Foundations and Trends in Networking"},{"key":"373_CR23","doi-asserted-by":"crossref","unstructured":"Maile L, Hielscher K-S, German R (2020) Network Calculus results for TSN: an introduction. In: 2020 information communication technologies conference (ICTC). IEEE, pp 131\u2013140","DOI":"10.1109\/ICTC49638.2020.9123308"},{"issue":"4","key":"373_CR24","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1109\/LNET.2019.2927143","volume":"1","author":"E Mohammadpour","year":"2019","unstructured":"Mohammadpour E, Stai E, Boudec J-YL (2019) Improved delay bound for a service curve element with known transmission rate. IEEE Netw Lett 1 (4):156\u2013159","journal-title":"IEEE Netw Lett"},{"key":"373_CR25","doi-asserted-by":"publisher","unstructured":"Mohammadpour E, Stai E, Boudec J-YL (2022) Improved network calculus delay bounds in time-sensitive networks. IEEE\/ACM Transactions on Networking, https:\/\/doi.org\/10.1109\/TNET.2023.3275910","DOI":"10.1109\/TNET.2023.3275910"},{"key":"373_CR26","doi-asserted-by":"crossref","unstructured":"Pollex V, Lipskoch H, Slomka F, Kollmann S (2011) Runtime improved computation of path latencies with the real-time calculus. In: Proceedings of the 1st international workshop on worst-case traversal time, pp 58\u201365","DOI":"10.1145\/2071589.2071597"},{"key":"373_CR27","unstructured":"RealTime-at-Work: RTaW-Pegase (min +) library (2022) https:\/\/www.realtimeatwork.com\/rtaw-pegase-libraries\/. Accessed: 2022-04-05"},{"key":"373_CR28","doi-asserted-by":"crossref","unstructured":"Rehm F, Seitter J, Larsson J-P, Saidi S, Stea G, Zippo R, Ziegenbein D, Andreozzi M, Hamann A (2021) The road towards predictable automotive high-performance platforms. In: 2021 design, automation & test in europe conference & exhibition (DATE). IEEE, pp 1915\u20131924","DOI":"10.23919\/DATE51398.2021.9473996"},{"key":"373_CR29","doi-asserted-by":"crossref","unstructured":"Schmitt JB, Roedig U (2005) Sensor network calculus\u2013a framework for worst case analysis. In: International conference on distributed computing in sensor systems. Springer, pp 141\u2013154","DOI":"10.1007\/11502593_13"},{"key":"373_CR30","doi-asserted-by":"crossref","unstructured":"Tabatabaee SM, Le Boudec J-Y (2022) Deficit round-robin: A second network calculus analysis. IEEE\/ACM Transactions on Networking","DOI":"10.1109\/RTAS52030.2021.00022"},{"issue":"12","key":"373_CR31","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1587\/transcom.2021ITI0001","volume":"104","author":"SM Tabatabaee","year":"2021","unstructured":"Tabatabaee SM, Le Boudec J-Y, Boyer M (2021) Interleaved weighted Round-Robin: a network calculus analysis. IEICE Trans Commun 104 (12):1479\u20131493","journal-title":"IEICE Trans Commun"},{"key":"373_CR32","doi-asserted-by":"crossref","unstructured":"Zhang J, Chen L, Wang T, Wang X (2019) Analysis of TSN for industrial automation based on network calculus. In: 2019 24th IEEE international conference on emerging technologies and factory automation (ETFA). IEEE, pp 240\u2013247","DOI":"10.1109\/ETFA.2019.8869053"},{"issue":"10","key":"373_CR33","doi-asserted-by":"publisher","first-page":"10291","DOI":"10.1109\/TIE.2020.3021638","volume":"68","author":"L Zhao","year":"2021","unstructured":"Zhao L, Pop P, Zheng Z, Daigmorte H, Boyer M (2021) Latency analysis of multiple classes of AVB traffic in TSN with standard credit behavior using Network Calculus. IEEE Trans Ind Electron 68(10):10291\u201310302. https:\/\/doi.org\/10.1109\/TIE.2020.3021638","journal-title":"IEEE Trans Ind Electron"},{"key":"373_CR34","doi-asserted-by":"publisher","unstructured":"Zippo R, Stea G (2022a) Nancy: an efficient parallel Network Calculus library. SoftwareX, https:\/\/doi.org\/10.1016\/j.softx.2022.101178","DOI":"10.1016\/j.softx.2022.101178"},{"key":"373_CR35","doi-asserted-by":"publisher","unstructured":"Zippo R, Stea G (2022b) Computationally efficient worst-case analysis of flow-controlled networks with Network Calculus. IEEE Transactions on Information Theory, https:\/\/doi.org\/10.1109\/TIT.2023.3244276","DOI":"10.1109\/TIT.2023.3244276"}],"container-title":["Discrete Event Dynamic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-022-00373-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10626-022-00373-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-022-00373-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,11]],"date-time":"2023-09-11T07:12:54Z","timestamp":1694416374000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10626-022-00373-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,18]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["373"],"URL":"https:\/\/doi.org\/10.1007\/s10626-022-00373-5","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-1689536\/v1","asserted-by":"object"}]},"ISSN":["0924-6703","1573-7594"],"issn-type":[{"value":"0924-6703","type":"print"},{"value":"1573-7594","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,18]]},"assertion":[{"value":"25 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of Interests"}}]}}