{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T19:21:51Z","timestamp":1784661711346,"version":"3.55.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,5]],"date-time":"2021-03-05T00:00:00Z","timestamp":1614902400000},"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":[[2021,3,5]]},"abstract":"<jats:p>Emerging software-defined and programmable networking technologies enable more adaptive communication infrastructures. However, leveraging these flexibilities and operating networks more adaptively is challenging, as the underlying infrastructure remains a complex distributed system that is a subject to delays, and as consistency properties need to be preserved transiently, even during network reconfiguration. Motivated by these challenges, we propose Latte, an automated approach to minimize the latency of network update schedules by avoiding unnecessary waiting times and exploiting concurrency, while at the same time provably ensuring a wide range of fundamental consistency properties like waypoint enforcement. To enable automated reasoning about the performance and consistency of software-defined networks during an update, we introduce the model of timed-arc colored Petri nets: an extension of Petri nets which allows us to account for time aspects in asynchronous networks, including characteristic timing behaviors, modeled as timed and colored tokens. This novel formalism may be of independent interest. Latte relies on an efficient translation of specific network update problems into timed-arc colored Petri nets. We show that the constructed nets can be analyzed efficiently via their unfolding into existing timed-arc Petri nets. We integrate Latte into the state-of-the-art model checking tool TAPAAL, and find that in many cases, we are able to reduce the latency of network updates by 90% or more.<\/jats:p>","DOI":"10.1145\/3453953.3453957","type":"journal-article","created":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T04:12:32Z","timestamp":1615003952000},"page":"14-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Latte"],"prefix":"10.1145","volume":"48","author":[{"given":"Niels","family":"Christensen","sequence":"first","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Glavind","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ji\u0159\u00ed","family":"Srba","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,3,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Pica8 p3297 data sheet 2014. https:\/\/www.pica8.com\/wp-content\/uploads\/ pica8-datasheet-48x1gbe-p3297.pdf.  Pica8 p3297 data sheet 2014. https:\/\/www.pica8.com\/wp-content\/uploads\/ pica8-datasheet-48x1gbe-p3297.pdf."},{"key":"e_1_2_1_2_1","unstructured":"Trisul network analytics 2017. https: \/\/www.trisul.org\/blog\/analysing-ssh\/post.html.  Trisul network analytics 2017. https: \/\/www.trisul.org\/blog\/analysing-ssh\/post.html."},{"key":"e_1_2_1_3_1","volume-title":"https:\/\/dev.to\/onmyway133\/ how-to-calculate-packet-size-in-voip--54ac","author":"Dev","year":"2018","unstructured":"Dev IO. https:\/\/dev.to\/onmyway133\/ how-to-calculate-packet-size-in-voip--54ac , 2018 . Dev IO. https:\/\/dev.to\/onmyway133\/ how-to-calculate-packet-size-in-voip--54ac, 2018."},{"key":"e_1_2_1_4_1","first-page":"1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"107","author":"Amiri Saeed Akhoondian","year":"2018","unstructured":"Saeed Akhoondian Amiri , Szymon Dudycz , Stefan Schmid , and Sebastian Wiederrecht . Congestion-free rerouting of flows on dags. In 45th International Colloquium on Automata, Languages, and Programming (ICALP) , volume 107 , pages 143: 1 -- 143 :13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik , 2018 . Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht. Congestion-free rerouting of flows on dags. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107, pages 143:1--143:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_2_1_5_1","first-page":"1","volume-title":"28th International Telecommunication Networks and Applications Conference (ITNAC)","author":"Fouad Aly Wael Hosny","year":"2018","unstructured":"Wael Hosny Fouad Aly and Yehia Kotb . Towards SDN fault tolerance using Petri-nets . In 28th International Telecommunication Networks and Applications Conference (ITNAC) , pages 1 -- 3 . IEEE, 2018 . Wael Hosny Fouad Aly and Yehia Kotb. Towards SDN fault tolerance using Petri-nets. In 28th International Telecommunication Networks and Applications Conference (ITNAC), pages 1--3. IEEE, 2018."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36046-6_8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3232755.3232776"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524332"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218382"},{"key":"e_1_2_1_10_1","volume-title":"Google routing blunder sent japan's internet dark on friday","author":"Chirgwin Richard","year":"2017","unstructured":"Richard Chirgwin . Google routing blunder sent japan's internet dark on friday . 2017 . https: \/\/www.theregister.co.uk\/2017\/08\/27\/google_ routing_blunder_sent_japans_internet_dark\/. Richard Chirgwin. Google routing blunder sent japan's internet dark on friday. 2017. https: \/\/www.theregister.co.uk\/2017\/08\/27\/google_ routing_blunder_sent_japans_internet_dark\/."},{"key":"e_1_2_1_11_1","volume-title":"Communications of the ACM","author":"Clark David","year":"2016","unstructured":"David Clark , Jennifer Rexford , and Amin Vahdat . A purpose-built global network: Google's move to SDN . Communications of the ACM , 2016 . David Clark, Jennifer Rexford, and Amin Vahdat. A purpose-built global network: Google's move to SDN. Communications of the ACM, 2016."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28756-5_36"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.102.12"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2016.21"},{"key":"e_1_2_1_15_1","volume-title":"arXiv preprint arXiv:1710.11583","author":"Feamster Nick","year":"2017","unstructured":"Nick Feamster and Jennifer Rexford . Why (and how) networks should run themselves. arXiv preprint arXiv:1710.11583 , 2017 . Nick Feamster and Jennifer Rexford. Why (and how) networks should run themselves. arXiv preprint arXiv:1710.11583, 2017."},{"key":"e_1_2_1_16_1","volume-title":"Model checking data flows in concurrent network updates (full version). arXiv preprint arXiv:1907.11061","author":"Finkbeiner Bernd","year":"2019","unstructured":"Bernd Finkbeiner , Manuel Gieseking , Jesko Hecking-Harbusch , and Ernst-R\u00a8udiger Olderog . Model checking data flows in concurrent network updates (full version). arXiv preprint arXiv:1907.11061 , 2019 . Bernd Finkbeiner, Manuel Gieseking, Jesko Hecking-Harbusch, and Ernst-R\u00a8udiger Olderog. Model checking data flows in concurrent network updates (full version). arXiv preprint arXiv:1907.11061, 2019."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2876749"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2017.8171348"},{"key":"e_1_2_1_19_1","volume-title":"Performance Evaluation Review","author":"Foerster Klaus-Tycho","unstructured":"Klaus-Tycho Foerster , Thomas Luedi , Jochen Seidel , Performance Evaluation Review , Vol. 48 , No. 3, December 2020 25 and Roger Wattenhofer. Local checkability, no strings attached:(a) cyclicity, reachability, loop free updates in SDNs. Theoretical Computer Science, 709:48--63, 2018. Klaus-Tycho Foerster, Thomas Luedi, Jochen Seidel, Performance Evaluation Review, Vol. 48, No. 3, December 2020 25 and Roger Wattenhofer. Local checkability, no strings attached:(a) cyclicity, reachability, loop free updates in SDNs. Theoretical Computer Science, 709:48--63, 2018."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3281411.3281432"},{"key":"e_1_2_1_21_1","first-page":"539","volume-title":"Rohan Gandhi, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Jennifer Rexford, and Roger Wattenhofer. Dynamic scheduling of network updates. In ACM SIGCOMM Computer Communication Review","author":"Jin Xin","year":"2014","unstructured":"Xin Jin , Hongqiang Harry Liu , Rohan Gandhi, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Jennifer Rexford, and Roger Wattenhofer. Dynamic scheduling of network updates. In ACM SIGCOMM Computer Communication Review , volume 44 , pages 539 -- 550 . ACM , 2014 . Xin Jin, Hongqiang Harry Liu, Rohan Gandhi, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Jennifer Rexford, and Roger Wattenhofer. Dynamic scheduling of network updates. In ACM SIGCOMM Computer Communication Review, volume 44, pages 539--550. ACM, 2014."},{"key":"e_1_2_1_22_1","first-page":"99","volume-title":"Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI'13)","author":"Kazemian Peyman","year":"2013","unstructured":"Peyman Kazemian , Michael Chang , Hongyi Zeng , George Varghese , Nick McKeown , and Scott Whyte . Real time network policy checking using header space analysis . In Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI'13) , pages 99 -- 111 , 2013 . Peyman Kazemian, Michael Chang, Hongyi Zeng, George Varghese, Nick McKeown, and Scott Whyte. Real time network policy checking using header space analysis. In Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI'13), pages 99--111, 2013."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111002"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486001.2486005"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2964791.2901476"},{"key":"e_1_2_1_26_1","volume-title":"ACM","author":"Ludwig Arne","year":"2015","unstructured":"Arne Ludwig , Jan Marcinkowski , and Stefan Schmid . Scheduling loop-free network updates: It's good to relax! In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 13--22 . ACM , 2015 . Arne Ludwig, Jan Marcinkowski, and Stefan Schmid. Scheduling loop-free network updates: It's good to relax! In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 13--22. ACM, 2015."},{"key":"e_1_2_1_27_1","first-page":"15","volume-title":"Proc. 13th ACM Workshop on Hot Topics in Networks (HotNets)","author":"Ludwig Arne","unstructured":"Arne Ludwig , Matthias Rost , Damien Foucard , and Stefan Schmid . Good network updates for bad packets: Waypoint enforcement beyond destination-based routing policies . In Proc. 13th ACM Workshop on Hot Topics in Networks (HotNets) , page 15 . ACM, 2014. Arne Ludwig, Matthias Rost, Damien Foucard, and Stefan Schmid. Good network updates for bad packets: Waypoint enforcement beyond destination-based routing policies. In Proc. 13th ACM Workshop on Hot Topics in Networks (HotNets), page 15. ACM, 2014."},{"key":"e_1_2_1_28_1","first-page":"20","volume-title":"Proc. 12th ACM Workshop on Hot Topics in Networks (HotNets)","author":"Mahajan Ratul","unstructured":"Ratul Mahajan and Roger Wattenhofer . On consistent updates in software defined networks . In Proc. 12th ACM Workshop on Hot Topics in Networks (HotNets) , page 20 . ACM, 2013. Ratul Mahajan and Roger Wattenhofer. On consistent updates in software defined networks. In Proc. 12th ACM Workshop on Hot Topics in Networks (HotNets), page 20. ACM, 2013."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737980"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2016.2599640"},{"key":"e_1_2_1_31_1","first-page":"1","volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI'13)","author":"Monsanto Christopher","year":"2013","unstructured":"Christopher Monsanto , Joshua Reich , Nate Foster , Jennifer Rexford , and David Walker . Composing software defined networks . In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI'13) , pages 1 -- 13 , 2013 . Christopher Monsanto, Joshua Reich, Nate Foster, Jennifer Rexford, and David Walker. Composing software defined networks. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI'13), pages 1--13, 2013."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2620728.2620747"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2377677.2377748"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3021426.3021437"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2015.09.035"},{"key":"e_1_2_1_39_1","series-title":"LNCS","first-page":"453","volume-title":"Application and Theory of Petri Nets (APTN'93)","author":"van der Aalst W. M. P.","year":"1993","unstructured":"W. M. P. van der Aalst . Interval timed coloured Petri nets and their analysis . In Application and Theory of Petri Nets (APTN'93) , volume 691 of LNCS , pages 453 -- 472 . Springer , 1993 . W. M. P. van der Aalst. Interval timed coloured Petri nets and their analysis. In Application and Theory of Petri Nets (APTN'93), volume 691 of LNCS, pages 453--472. Springer, 1993."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCNC.2016.7440631"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2017.96"},{"key":"e_1_2_1_42_1","first-page":"73","volume-title":"Proc. 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI'15)","author":"Zhou Wenxuan","year":"2015","unstructured":"Wenxuan Zhou , Dong Jin , Jason Croft , Matthew Caesar , and P Brighten Godfrey . Enforcing customizable consistency properties in software-defined networks . In Proc. 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI'15) , pages 73 -- 85 , 2015 . Wenxuan Zhou, Dong Jin, Jason Croft, Matthew Caesar, and P Brighten Godfrey. Enforcing customizable consistency properties in software-defined networks. In Proc. 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI'15), pages 73--85, 2015."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0026-2714(91)90007-T"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453953.3453957","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453953.3453957","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:51Z","timestamp":1750193271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453953.3453957"}},"subtitle":["Improving the Latency of Transiently Consistent Network Update Schedules"],"short-title":[],"issued":{"date-parts":[[2021,3,5]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3,5]]}},"alternative-id":["10.1145\/3453953.3453957"],"URL":"https:\/\/doi.org\/10.1145\/3453953.3453957","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":[],"published":{"date-parts":[[2021,3,5]]},"assertion":[{"value":"2021-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}