research-article

Unicast and multicast QoS routing with soft-constraint logic programming

Authors:

Stefano Bistarelli,

Francesca Rossi,

Francesco SantiniAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 12, Issue 1

Article No.: 5, Pages 1 - 48

https://doi.org/10.1145/1838552.1838557

Published: 26 November 2010 Publication History

Abstract

We present a formal model to represent and solve the unicast/multicast routing problem in networks with quality-of-service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or 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 soft-constraint logic programming (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. delay ≤ 40 ms), thus finding a solution to QoS routing problems. C-semiring 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.

References

[1]

Apt, K. R. and Wallace, M. 2007. Constraint Logic Programming Using Eclipse. Cambridge University Press, Cambridge, UK.

Digital Library

[2]

Barabasi, A. L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509.

[3]

Berman, L., Kou, L., and Markowsky, G. 1979. A fast algorithm for steiner trees. Acta Informatica 15, 2, 141--145.

[4]

Bistarelli, S. 2004. Semirings for soft constraint solving and programming. Lecture Notes in Computer Science, vol. 2962. Springer, Berlin, Germany.

Digital Library

[5]

Bistarelli, S., Frühwirth, T., and Marte, M. 2002a. Soft constraint propagation and solving in CHRS. In Proceedings of the ACM Symposium on Applied Computing (SAC'02). ACM Press, New York, NY, 1--5.

Digital Library

[6]

Bistarelli, S., Gabrielli, M., Meo, M. C., and Santini, F. 2007. Timed concurrent constraint programs. In Proceedings of the 5th Workshop on Quantitatine Aspects of Programming Languages (QAPL).

[7]

Bistarelli, S. and Gadducci, F. 2006. Enhancing constraints manipulation in semiring-based formalisms. In Proceedings of the European Conference on Artificial Intelligence (ECAI). 63--67.

Digital Library

[8]

Bistarelli, S., Montanari, U., and Rossi, F. 1995. Constraint solving over semirings. In Proceedings of the International Conference on Artificial Intelligence. Morgan Kaufman, 624--630.

Digital Library

[9]

Bistarelli, S., Montanari, U., and Rossi, F. 1997a. Semiring-based constraint logic programming. In Proceedings of the International Conference on Artificial Intelligence. Morgan Kaufman, San Francisco, CA, 352--357.

Digital Library

[10]

Bistarelli, S., Montanari, U., and Rossi, F. 2002b. Soft constraint logic programming and generalized shortest path problems. J. Heur. 8, 1, 25--41.

Digital Library

[11]

Bistarelli, S., Montanari, U., and Rossi, F. 2006. Soft concurrent constraint programming. ACM Trans. Comput. Logic 7, 3, 563--589.

Digital Library

[12]

Bistarelli, S., Montanari, U., and Rossi, F. March 1997b. Semiring-based constraint solving and optimization. J. ACM 44, 2, 201--236.

Digital Library

[13]

Bistarelli, S., Montanari, U., Rossi, F., and Santini, F. 2007. Modelling multicast qos routing by using best-tree search in and-or graphs and soft constraint logic programming. Electr. Notes Theor. Comput. Sci. 190, 3, 111--127.

[14]

Bistarelli, S. and Santini, F. 2008. A formal and practical framework for constraint-based routing. In Proceedings of ICN. IEEE Computer Society Press, Los Alamitos, CA, 162--167.

Digital Library

[15]

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.

[16]

Chen, S. and Nahrstedt, K. 1998. An overview of quality of service routing for next-generation high-speed networks: Problems and solutions. IEEE Netw. 12, 6, 64--79.

Digital Library

[17]

Chen, S., Nahrstedt, K., and Shavitt, Y. 2000. A QoS-aware multicast routing protocol. In Proceedings of INFOCOM. 1594--1603.

[18]

Cohen, R. and Havlin, S. 2003. Scale-free networks are ultrasmall. Phys. Rev. Lett. 90, 5, 058701.

[19]

Cormen, T. T., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA.

Digital Library

[20]

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.

[21]

Cui, B. and Warren, D. S. 2000. A system for tabled constraint logic programming. In Proceedings of the 1st International Conference on Computational Logic (CL'00). Springer-Verlag, Berlin, Germany, 478--492.

Digital Library

[22]

de Nicola, R., Ferrari, G. L., Montanari, U., Pugliese, R., and Tuosto, E. 2003. A formal basis for reasoning on programmable qos. In Verification: Theory and Practice, N. Dershowitz, Ed. Lecture Notes in Computer Science, vol. 2772. Springer, Berlin, Germany, 436--479.

[23]

Faloutsos, M., Faloutsos, P., and Faloutsos, C. 1999. On power-law relationships of the internet topology. In Proceedings of SIGCOMM. ACM Press, New York, NY, 251--262.

Digital Library

[24]

Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY.

Digital Library

[25]

Georget, Y. and Codognet, P. 1998. Compiling semiring-based constraints with CLP (FD, S). In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP'98). Springer-Verlag, Berlin, Germany, 205--219.

Digital Library

[26]

Hirsch, D. and Tuosto, E. 2005. Shreq: Coordinating application level QoS. In Proceedings of the 3rd IEEE International Conference on Software Engineering and Formal Methods (SEFM'05). IEEE Computer Society Press, Los Alamitos, CA, 425--434.

Digital Library

[27]

Jaffar, J. and Maher, M. J. 1994. Constraint logic programming: A survey. J. Log. Programm. 19/20, 503--581.

[28]

Kompella, K. and Awduche, D. 2001. Notes on path computation in constraint-based routing. Internet Draft.

[29]

Korkmaz, T. and Krunz, M. 2001. Multi-constrained optimal path selection. In Poceedings of INFOCOM. 834--843.

[30]

Kuipers, F. A., Korkmaz, T., Krunz, M., and Mieghem, P. V. 2004. Performance evaluation of constraint-based path selection algorithms. IEEE Netw. 18, 5, 16--23.

Digital Library

[31]

Loo, B. T., Hellerstein, J. M., Stoica, I., and Ramakrishnan, R. 2005. Declarative routing: Extensible routing with declarative queries. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM'05). ACM Press, New York, NY, 289--300.

Digital Library

[32]

Ma, Q. and Steenkiste, P. 1997. Quality of service routing for traffic with performance guarantees. In Proceedings of the IFIP International Workshop on Quality of Service. 155--126.

[33]

Mammeri, Z. 2004. Towards a formal model for QOS specification and handling in networks. In Proceedings of IWQoS. 148--152.

[34]

Martelli, A. and Montanari, U. 1978. Optimizing decision trees through heuristically guided search. Comm. ACM 21, 12, 1025--1039.

Digital Library

[35]

Masip-Bruin, X., Yannuzzi, M., Domingo-Pascual, J., Fonte, A., Curado, M., Monteiro, E., Kuipers, F. A., Mieghem, P. V., Avallone, S., Ventre, G., Aranda-Gutiérrez, P. A., Hollick, M., Steinmetz, R., Iannone, L., and Salamatian, K. 2006. Research challenges in qos routing. Comput. Comm. 29, 5, 563--581.

Digital Library

[36]

Mieghem, P. V., Neve, H. D., and Kuipers, F. A. 2001. Hop-by-hop quality of service routing. Comput. Netw. 37, 3/4, 407--423.

Digital Library

[37]

Mieghem, P. V. and Vandenberghe, L. 2006. Trade-off curves for QoS routing. In Proceedings of INFOCOM.

[38]

Mohri, M. 2002. Semiring frameworks and algorithms for shortest-distance problems. J. Autom. Lang. Comb. 7, 3, 321--350.

Digital Library

[39]

Moy, J. 1998. RFC 2328: OSPF version 2. Standard. RF 2328. www.rfc-archieve.org/.

[40]

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.

[41]

Paul, P. and Raghavan, S. V. 2002. Survey of qos routing. In Proceedings of the 15th International Conference on Computer Communication (ICCC'02). International Council for Computer Communication, Washington, DC, 50--75.

Digital Library

[42]

Ramakrishnan, I. V., Rao, P., Sagonas, K. F., Swift, T., and Warren, D. S. 1995. Efficient tabling mechanisms for logic programs. In Proceedings of the International Conference on Logic Programming. The MIT Press, Cambridge, MA, 697--711.

[43]

Régin, J.-C., Petit, T., Bessière, C., and Puget, J.-F. 2000. An original constraint based approach for solving over constrained problems. In Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming (CP'02). Springer-Verlag, Berlin, Germany, 543--548.

Digital Library

[44]

Rosen, E., Viswanathan, A., and Callon, R. 2001. Multiprotocol label switching architecture. RFC 3031. www.rfc-archive.org/.

[45]

Rouskas, G. N. and Baldine, I. 1997. Multicast routing with end-to-end delay and delay variation constraints. IEEE J. Select. Areas Commun. 15, 3, 346--356.

Digital Library

[46]

Schrijvers, T. and Warren, D. S. 2004. Constraint handling rules and tabled execution. In Proceedings of ICLP. B. Demoen and V. Lifschitz, Eds. Lecture Notes in Computer Science, vol. 3132. Springer, Berlin, Germany, 120--136.

[47]

Smyth, M. B. 1978. Power domains. J. Comput. Syst. Sci. 16, 1, 23--36.

[48]

Tarjan, R. E. 1979. A unified approach to path problems. Tech. rep. STAN-CS-79-729. Stanford University, Stanford, CA.

Digital Library

[49]

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/.

[50]

Wang, B. and Hou, J. 2000. Multicast routing and its QoS extension: Problems, algorithms, and protocols. IEEE Netw. 14, 22--36.

Digital Library

[51]

Wang, Z. 1999. On the complexity of quality of service routing. Inf. Process. Lett. 69, 3, 111--114.

Digital Library

[52]

Wang, Z. and Crowcroft, J. 1996. Quality-of-service routing for supporting multimedia applications. IEEE J. Select. Areas Commun. 14, 7, 1228--1234.

Digital Library

[53]

Wilson, N. 2004. Bounds and pre-processing for local computation of semiring valuations. In Proceedings of the ECAI Workshop on Local Computation for Logics and Uncertainty.

[54]

Winter, P. 1987. Steiner problem in networks: A survey. Netw. 17, 2, 129--167.

Digital Library

[55]

Xiao, X. and Ni, L. M. 1999. Internet QoS: A big picture. IEEE Netw. 13, 2, 8--18.

Digital Library

[56]

Younis, O. and Fahmy, S. 2003. Constraint-based routing in the Internet: Basic principles and recent research. IEEE Commun. Surv. Tutor. 5, 1, 2--13.

Digital Library

Cited By

Bistarelli SRossi FSantini F(2021)Kruskal with embedded C-semirings to solve MST problems with partially-ordered costsInformation Processing Letters10.1016/j.ipl.2021.106107169(106107)Online publication date: Aug-2021
https://doi.org/10.1016/j.ipl.2021.106107
Ait Wakrime ARekik MJabbour S(2019)Cloud service composition using minimal unsatisfiability and genetic algorithmConcurrency and Computation: Practice and Experience10.1002/cpe.528232:15Online publication date: 11-Apr-2019
https://doi.org/10.1002/cpe.5282
Wakrime AJabbour S(2017)Formal Approach for QoS-Aware Cloud Service Composition2017 IEEE 26th International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE)10.1109/WETICE.2017.61(30-35)Online publication date: Jun-2017
https://doi.org/10.1109/WETICE.2017.61
Show More Cited By

Index Terms

Unicast and multicast QoS routing with soft-constraint logic programming

Recommendations

Integration of explicit effective-bandwidth-based QoS routing with best-effort routing

This paper presents a methodology for protecting low-priority best-effort (BE) traffic in a network domain that provides both virtual-circuit routing with bandwidth reservation for QoS traffic and datagram routing for BE traffic. When a QoS virtual ...
Provisioning QoS guarantee by multipath routing and reservation in Ad hoc networks
Abstract
In this paper, a QoS multipath source routing protocol (QoS-MSR) is proposed for ad hoc networks. It can collect QoS information through route discovery mechanism of multipath source routing (MSR) and establish QoS route with reserved bandwidth. ...
Multicast QoS Routing Using Collaborative Path Exploration
AINA '10: Proceedings of the 2010 24th IEEE International Conference on Advanced Information Networking and Applications

Quality of Service (QoS) is one of the most active research areas in networking. The most fundamental requirement for QoS routing is the ability to find and maintain a network path that provides the required network resources between two or more nodes. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 12, Issue 1

October 2010

334 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/1838552

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 November 2010

Accepted: 01 November 2009

Revised: 01 February 2009

Received: 01 September 2007

Published in TOCL Volume 12, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
283
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)3

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bistarelli SRossi FSantini F(2021)Kruskal with embedded C-semirings to solve MST problems with partially-ordered costsInformation Processing Letters10.1016/j.ipl.2021.106107169(106107)Online publication date: Aug-2021
https://doi.org/10.1016/j.ipl.2021.106107
Ait Wakrime ARekik MJabbour S(2019)Cloud service composition using minimal unsatisfiability and genetic algorithmConcurrency and Computation: Practice and Experience10.1002/cpe.528232:15Online publication date: 11-Apr-2019
https://doi.org/10.1002/cpe.5282
Wakrime AJabbour S(2017)Formal Approach for QoS-Aware Cloud Service Composition2017 IEEE 26th International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE)10.1109/WETICE.2017.61(30-35)Online publication date: Jun-2017
https://doi.org/10.1109/WETICE.2017.61
Terenziani PAndolina APiovesan L(2017)Managing Temporal Constraints with Preferences: Representation, Reasoning, and QueryingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.269785229:9(2067-2071)Online publication date: 1-Sep-2017
https://doi.org/10.1109/TKDE.2017.2697852
Kotronis VKlöti RRost MGeorgopoulos PAger BSchmid SDimitropoulos XGodfrey BCasado M(2016)Stitching Inter-Domain Paths over IXPsProceedings of the Symposium on SDN Research10.1145/2890955.2890960(1-12)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.1145/2890955.2890960
Abramkina OShuvalov V(2016)About one of the methods for solving problems in QoS routing2016 International Siberian Conference on Control and Communications (SIBCON)10.1109/SIBCON.2016.7491669(1-4)Online publication date: May-2016
https://doi.org/10.1109/SIBCON.2016.7491669
Wakrime AJabbour SBelabed A(2016)Web Service Composition as minimal unsatisfiability2016 International Conference on Electrical and Information Technologies (ICEIT)10.1109/EITech.2016.7519651(61-66)Online publication date: May-2016
https://doi.org/10.1109/EITech.2016.7519651
Wakrime AJabbour S(2015)Minimum Unsatisfiability based QoS Web Service Composition over the Cloud Computing2015 15th International Conference on Intelligent Systems Design and Applications (ISDA)10.1109/ISDA.2015.7489174(540-545)Online publication date: Dec-2015
https://doi.org/10.1109/ISDA.2015.7489174
Wakrime AJabbour S(2015)On QoS web service composition using satisfiability2015 5th International Conference on Information & Communication Technology and Accessibility (ICTA)10.1109/ICTA.2015.7426929(1-6)Online publication date: Dec-2015
https://doi.org/10.1109/ICTA.2015.7426929
Santini FYautsiukhin A(2015)Quantitative Analysis of Network Security with Abstract ArgumentationRevised Selected Papers of the 10th International Workshop on Data Privacy Management, and Security Assurance - Volume 948110.1007/978-3-319-29883-2_3(30-46)Online publication date: 21-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-29883-2_3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents