{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T21:27:25Z","timestamp":1783114045349,"version":"3.54.6"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,10,1]],"date-time":"2010-10-01T00:00:00Z","timestamp":1285891200000},"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":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>We present a formal model to represent and solve the unicast\/multicast routing problem in networks with<jats:italic>quality-of-service<\/jats:italic>(QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or<jats:italic>and-or<\/jats:italic>graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e.g., bandwidth). The second step consists in writing this graph as a program in<jats:italic>soft-constraint logic programming<\/jats:italic>(SCLP): the engine of this framework is then able to find the best paths\/trees by optimizing their costs and solving the constraints imposed on them (e.g.<jats:italic>delay<\/jats:italic>\u2264 40 ms), thus finding a solution to QoS routing problems.<jats:italic>C-semiring<\/jats:italic>structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved. The article highlights the expressivity of SCLP.<\/jats:p>","DOI":"10.1145\/1838552.1838557","type":"journal-article","created":{"date-parts":[[2010,11,3]],"date-time":"2010-11-03T14:16:37Z","timestamp":1288793797000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Unicast and multicast QoS routing with soft-constraint logic programming"],"prefix":"10.1145","volume":"12","author":[{"given":"Stefano","family":"Bistarelli","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Perugia, Perugia, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ugo","family":"Montanari","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesca","family":"Rossi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Padova, Padova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Santini","sequence":"additional","affiliation":[{"name":"Universit\u00e0 \u201cG. d'Annunzio\u201d Pescara, Pescara, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,11,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apt K. R. and Wallace M. 2007. Constraint Logic Programming Using Eclipse. Cambridge University Press Cambridge UK. Apt K. R. and Wallace M. 2007. Constraint Logic Programming Using Eclipse. Cambridge University Press Cambridge UK."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_3_1","first-page":"141","article-title":"A fast algorithm for steiner trees","volume":"15","author":"Berman L.","year":"1979","journal-title":"Acta Informatica"},{"key":"e_1_2_1_4_1","series-title":"Lecture Notes in Computer Science","volume-title":"Semirings for soft constraint solving and programming","author":"Bistarelli S."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/508791.508793"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 5th Workshop on Quantitatine Aspects of Programming Languages (QAPL).","author":"Bistarelli S."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the European Conference on Artificial Intelligence (ECAI). 63--67","author":"Bistarelli S."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on Artificial Intelligence. Morgan Kaufman, 624--630","author":"Bistarelli S."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Conference on Artificial Intelligence. Morgan Kaufman","author":"Bistarelli S."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013609600697"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149118"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/256303.256306"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2007.07.008"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICN.2008.12"},{"key":"e_1_2_1_15_1","unstructured":"Bueno F. Cabeza D. Carro M. Hermenegildo M. Lopez P. and Puebla G. 1997. The CIAO Prolog System Reference Manual. The CIAO System Documentation Series--TR CLIP3\/97.1. School of Computer Science University of Madrid Madrid Spain. Bueno F. Cabeza D. Carro M. Hermenegildo M. Lopez P. and Puebla G. 1997. The CIAO Prolog System Reference Manual. The CIAO System Documentation Series--TR CLIP3\/97.1. School of Computer Science University of Madrid Madrid Spain."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.752646"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of INFOCOM. 1594--1603","author":"Chen S."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.90.058701"},{"key":"e_1_2_1_19_1","unstructured":"Cormen T. T. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA. Cormen T. T. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Crawley E. Nair R. Rajagopalan B. and Sandick H. 1998. A framework for QoS-based routing in the Internet. Informational. RFC 2386. www.rfc-archieve.org. Crawley E. Nair R. Rajagopalan B. and Sandick H. 1998. A framework for QoS-based routing in the Internet. Informational. RFC 2386. www.rfc-archieve.org.","DOI":"10.17487\/rfc2386"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 1st International Conference on Computational Logic (CL'00)","author":"Cui B."},{"key":"e_1_2_1_22_1","volume-title":"Verification: Theory and Practice","author":"de Nicola R.","year":"2003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_24_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &amp; Co. New York NY. Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &amp; Co. New York NY."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP'98)","author":"Georget Y."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SEFM.2005.40"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)90033-7"},{"key":"e_1_2_1_28_1","unstructured":"Kompella K. and Awduche D. 2001. Notes on path computation in constraint-based routing. Internet Draft. Kompella K. and Awduche D. 2001. Notes on path computation in constraint-based routing. Internet Draft."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Korkmaz T. and Krunz M. 2001. Multi-constrained optimal path selection. In Poceedings of INFOCOM. 834--843. Korkmaz T. and Krunz M. 2001. Multi-constrained optimal path selection. In Poceedings of INFOCOM. 834--843.","DOI":"10.1109\/INFCOM.2001.916274"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2004.1337731"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080091.1080126"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the IFIP International Workshop on Quality of Service. 155--126","author":"Ma Q."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQOS.2004.1309371"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/359657.359664"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2005.06.008"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(01)00222-5"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of INFOCOM.","author":"Mieghem P. V."},{"key":"e_1_2_1_38_1","first-page":"321","article-title":"Semiring frameworks and algorithms for shortest-distance problems","volume":"7","author":"Mohri M.","year":"2002","journal-title":"J. Autom. Lang. Comb."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Moy J. 1998. RFC 2328: OSPF version 2. Standard. RF 2328. www.rfc-archieve.org\/. Moy J. 1998. RFC 2328: OSPF version 2. Standard. RF 2328. www.rfc-archieve.org\/.","DOI":"10.17487\/rfc2328"},{"key":"e_1_2_1_40_1","unstructured":"O'Madadhain J. Fisher D. White S. and Boey Y. 2003. The JUNG (Java Universal Network\/Graph) framework. Tech. rep. University of California Irvine Irvine CA. O'Madadhain J. Fisher D. White S. and Boey Y. 2003. The JUNG (Java Universal Network\/Graph) framework. Tech. rep. University of California Irvine Irvine CA."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 15th International Conference on Computer Communication (ICCC'02)","author":"Paul P."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the International Conference on Logic Programming. The MIT Press","author":"Ramakrishnan I. V."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming (CP'02)","author":"R\u00e9gin J.-C."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Rosen E. Viswanathan A. and Callon R. 2001. Multiprotocol label switching architecture. RFC 3031. www.rfc-archive.org\/. Rosen E. Viswanathan A. and Callon R. 2001. Multiprotocol label switching architecture. RFC 3031. www.rfc-archive.org\/.","DOI":"10.17487\/rfc3031"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.564133"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of ICLP. B. Demoen and V. Lifschitz, Eds. Lecture Notes in Computer Science","volume":"3132","author":"Schrijvers T."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90048-X"},{"key":"e_1_2_1_48_1","volume-title":"A unified approach to path problems. Tech. rep. STAN-CS-79-729","author":"Tarjan R. E."},{"key":"e_1_2_1_49_1","unstructured":"Vazquez A. Pastor-Satorras R. and Vespignani A. 2002. Internet topology at the router and autonomous system level. http:\/\/artiv.org\/pdf\/cond-mat\/0206084v\/. Vazquez A. Pastor-Satorras R. and Vespignani A. 2002. Internet topology at the router and autonomous system level. http:\/\/artiv.org\/pdf\/cond-mat\/0206084v\/."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.819168"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00206-3"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.536364"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the ECAI Workshop on Local Computation for Logics and Uncertainty.","author":"Wilson N.","year":"2004"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/34233.34235"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.768484"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2003.5342226"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1838552.1838557","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1838552.1838557","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:11Z","timestamp":1750250471000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1838552.1838557"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1145\/1838552.1838557"],"URL":"https:\/\/doi.org\/10.1145\/1838552.1838557","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}