{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:26:38Z","timestamp":1756383998494,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:00:00Z","timestamp":1708560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2024,2,22]]},"abstract":"<jats:p>Network Calculus (NC) is a method for providing certification evidence in networked systems, ensuring proper functioning of time-critical traffic. Traditional NC analyses focus on feedforward networks that are networks without cyclic dependencies. However, some methods, like the fix-point method and turn prohibition, apply NC to non-feedforward networks but exhibit limitations in stability, adaptability, and flexibility. We propose an alternative method, service partitioning, supported by theorems and lemmas, to address these limitations. Service partitioning breaks cyclic dependencies in non-feedforward networks using a breaking method that leverages Quality of Service (QoS) mechanisms (Weighted Round-Robin, Static Priority, Time-Aware Shaper), by assigning flows that form cycles to distinct buffers with dedicated service allocations. This method offers enhanced flexibility by allocating different network resources to buffers based on multi-class scheduling during the breaking process. In contrast to existing methods, service partitioning does not require rerouting or additional hardware and avoids deriving invalid solutions. The paper investigates the performance of service partitioning in terms of flexibility, result tightness, adaptability, and stability to show that service partitioning is superior to existing methods. One limitation of service partitioning is that it cannot fully break cyclic dependencies in some scenarios, requiring the assist from solving methods, which can be used to apply network calculus to networks with cyclic dependencies. However, when combined with solving methods, service partitioning can still improve solution quality, reducing potentially invalid results in simulated ring networks by over 30% compared with results derived by solving methods alone.<\/jats:p>","DOI":"10.1145\/3649477.3649495","type":"journal-article","created":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T23:05:43Z","timestamp":1708729543000},"page":"32-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Breaking Cyclic Dependencies for Network Calculus using Service Partitioning"],"prefix":"10.1145","volume":"51","author":[{"given":"Boyang","family":"Zhou","sequence":"first","affiliation":[{"name":"Lehigh University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Isaac","family":"Howenstine","sequence":"additional","affiliation":[{"name":"EAB"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liang","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of Toledo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"Bondorf","sequence":"additional","affiliation":[{"name":"Ruhr University Bochum"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,2,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45318-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3043600"},{"key":"e_1_2_1_3_1","volume-title":"Proc. of QEST","author":"Scheffer Alexander","year":"2021","unstructured":"Alexander Scheffer. Network calculus for bounding delays in feedforward networks of FIFO queueing systems. In Proc. of QEST, 2021."},{"key":"e_1_2_1_4_1","first-page":"19","article-title":"an efficient parallel network calculus library","author":"Stea Giovanni","year":"2022","unstructured":"Giovanni Stea. Nancy: an efficient parallel network calculus library. SoftwareX, 19, 2022.","journal-title":"SoftwareX"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQOS52092.2021.9521335"},{"key":"e_1_2_1_6_1","volume-title":"Network calculus: Application to an industrial automation network","author":"Kerschbaum Sven","year":"2012","unstructured":"Sven Kerschbaum, Kai-Steffen Hielscher, Ulrich Klehmet, and Reinhard German. Network calculus: Application to an industrial automation network. 2012."},{"key":"e_1_2_1_7_1","volume-title":"Proc. of EAI ValueTools","author":"Bondorf Steffen","year":"2014","unstructured":"Steffen Bondorf and Jens Schmitt. The DiscoDNC v2: A comprehensive tool for deterministic network calculus. In Proc. of EAI ValueTools, 2014."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.813040"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3356401.3356418"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS46320.2019.00035"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2017.8046319"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/icc.2011.5963105"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2021.102250"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.61110"},{"key":"e_1_2_1_16_1","volume-title":"Proc. of the CRTS workshop","author":"Mifdaoui Ahlem","year":"2017","unstructured":"Ahlem Mifdaoui and Thierry Leydier. Beyond the accuracy-complexity tradeo's of compositional analyses using network calculus for complex networks. In Proc. of the CRTS workshop, 2017."},{"key":"e_1_2_1_17_1","volume-title":"Equivalent versions of total flow analysis. arXiv preprint arXiv:2111.01827","author":"Plassart St\u00b4ephan","year":"2021","unstructured":"St\u00b4ephan Plassart and Jean-Yves Le Boudec. Equivalent versions of total flow analysis. arXiv preprint arXiv:2111.01827, 2021."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/WCSP.2019.8927901"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2858767"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1587\/transcom.2021ITI0001"},{"volume-title":"July","year":"2022","key":"e_1_2_1_21_1","unstructured":"Google. OR-tools official website, July 2022. https:\/\/developers.google.com\/optimization."}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649477.3649495","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649477.3649495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:56:53Z","timestamp":1750291013000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649477.3649495"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,22]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,2,22]]}},"alternative-id":["10.1145\/3649477.3649495"],"URL":"https:\/\/doi.org\/10.1145\/3649477.3649495","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2024,2,22]]},"assertion":[{"value":"2024-02-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}