{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:25:23Z","timestamp":1753439123601,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,12,19]],"date-time":"2017-12-19T00:00:00Z","timestamp":1513641600000},"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":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,12,19]]},"abstract":"<jats:p>Fault-tolerant computer networks rely on mechanisms supporting the fast detection of link failures. Tomographic techniques can be used to implement such mechanisms at low cost: it is often sufficient to deploy a small number of tomography nodes exchanging probe messages along paths between them and detect link failures based on these messages. Our paper studies a practically relevant aspect of network tomography: the impact of the routing model.<\/jats:p>\n          <jats:p>While the relevance of the routing model on path diversity and hence tomography cost is obvious and well-known on an anecdotal level, we lack an analytical framework to quantify the influence of different routing models (such as destination-based routing) exists. This paper fills this gap and introduces a formal model for asymmetric network tomography and a taxonomy of path routing models. This facilitates algorithmic reasoning about tomographic placement problems and quantifying the difference between routing models. In particular, we provide optimal and near-optimal algorithms to deploy a minimal number of asymmetric and symmetric tomography nodes for basic network topologies (modelled as graphs) under different routing model classes. Interestingly, we find that in many cases routing according to a more restrictive routing model gives better results: compared to a more general routing model, computing a good placement is algorithmically more tractable and does not entail high monitoring costs, a desirable trade-off in practice.<\/jats:p>","DOI":"10.1145\/3154501","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Tomographic Node Placement Strategies and the Impact of the Routing Model"],"prefix":"10.1145","volume":"1","author":[{"given":"Yvonne-Anne","family":"Pignolet","sequence":"first","affiliation":[{"name":"ABB Corporate Research, Baden, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Viena, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gilles","family":"Tredan","sequence":"additional","affiliation":[{"name":"CNRS-LAAS, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,19]]},"reference":[{"volume-title":"Multiprotocol Label Switching Working Group. (June","year":"2009","key":"e_1_2_1_1_1","unstructured":"2009. Multiprotocol Label Switching Working Group. (June 2009 ). http:\/\/www.ietf.org\/html.charters\/mpls-charter.html 2009. Multiprotocol Label Switching Working Group. (June 2009). http:\/\/www.ietf.org\/html.charters\/mpls-charter.html"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626300"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2010.2103402"},{"volume-title":"Congressus Numerantium.","author":"Boothe P.","key":"e_1_2_1_4_1","unstructured":"P. Boothe , Z. Dvorak , A. Farley , and A. Proskurowski . 2007. Graph Covering via Shortest Paths . In Congressus Numerantium. P. Boothe, Z. Dvorak, A. Farley, and A. Proskurowski. 2007. Graph Covering via Shortest Paths. In Congressus Numerantium."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2620728.2620746"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2169535"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1364654.1364677"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948232"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885460"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11527954_6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0677"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/339331.339426"},{"key":"e_1_2_1_13_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2079296.2079320"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1594977.1592576"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948231"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452335.1452343"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2774993.2775005"},{"key":"e_1_2_1_19_1","first-page":"1765","article-title":"The internet topology zoo. Selected Areas in Communications","volume":"29","author":"Knight Simon","year":"2011","unstructured":"Simon Knight , Huan X Nguyen , Nick Falkner , Richard Bowden , and Matthew Roughan . 2011 . The internet topology zoo. Selected Areas in Communications , IEEE Journal on , Vol. 29 , 9 (2011), 1765 -- 1775 . Simon Knight, Huan X Nguyen, Nick Falkner, Richard Bowden, and Matthew Roughan. 2011. The internet topology zoo. Selected Areas in Communications, IEEE Journal on, Vol. 29, 9 (2011), 1765--1775.","journal-title":"IEEE Journal on"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2890955.2890960"},{"key":"e_1_2_1_21_1","volume-title":"Kulfi: Robust Traffic Engineering Using Semi-Oblivious Routing. arXiv.","author":"Kumar Praveen","year":"2016","unstructured":"Praveen Kumar , Yang Yuan , Chris Yu , Nate Foster , Robert Kleinberg , and Robert Soule . 2016 . Kulfi: Robust Traffic Engineering Using Semi-Oblivious Routing. arXiv. Praveen Kumar, Yang Yuan, Chris Yu, Nate Foster, Robert Kleinberg, and Robert Soule. 2016. Kulfi: Robust Traffic Engineering Using Semi-Oblivious Routing. arXiv."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028788.1028810"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.003"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2663716.2663723"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2663716.2663723"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2015.47"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90159-Y"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1096536.1096546"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535771.2535792"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.822655"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/885651.781069"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2398776.2398817"}],"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\/3154501","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:27Z","timestamp":1750212687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,19]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,12,19]]}},"alternative-id":["10.1145\/3154501"],"URL":"https:\/\/doi.org\/10.1145\/3154501","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2017,12,19]]},"assertion":[{"value":"2017-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}