A New QoS Routing Northbound Interface for SDN

Main Article Content

Siamak Layeghy
Farzaneh Pakzad
Marius Portmann


Constraint Programming, Software Defined Networking, Northbound Interface, Quality of Service Routing, MiniZinc


In this paper, we introduce SCOR (Software-defined Constrained Optimal Routing), a new Software Defined Networking (SDN) Northbound Interface for QoS routing and traffic engineering. SCOR is based on constraint-programming techniques and is implemented in the MiniZinc modelling language. It provides a powerful, high-level abstraction layer, consisting of 10 basic constraint-programming predicates. A key feature of SCOR is that it is declarative, where only the constraints and utility function of the routing problem need to be expressed, and the complexity of solving the problem is hidden from the user, and handled by a powerful generic solver. We show that the interface (set of predicates) of SCOR is sufficiently expressive to handle all the known and relevant QoS routing problems. We further demonstrate the practicality and scalability of the approach via a number of example scenarios, with varying network topologies, network sizes and number of flows.

Abstract 490 | PDF Downloads 14 HTML Downloads 0


Al-Fares, M.; Loukissas, A.; Vahdat, A. (2008). A scalable, commodity data center network architecture. Paper presented at the Proceedings of the ACM SIGCOMM 2008 conference on Data communication, Seattle, WA, USA.

Bartak, R. (1999). Constraint Programming: In Pursuit of the Holy Grail. Paper presented at the In Proceedings of the Week of Doctoral Students (WDS99 -invited lecture).

Berde, P.; Gerola, M.; Hart, J.; Higuchi, Y.; Kobayashi, M.; Koide, T.; Lantz, B.; O'Connor, B.; Radoslavov, P.; Snow, W.; Parulkar, G. (2014). ONOS: towards an open, distributed SDN OS. Paper presented at the Proceedings of the third workshop on Hot topics in software defined networking, Chicago, Illinois, USA.

Bertsekas, D. P. (1998). Network optimization: continuous and discrete models. Belmont Massachusetts, USA: Athena Scientific.

Chen, S.; Nahrstedt, K. (1998). An overview of quality-of-service routing for next-generation high-speed networks: problems and solutions. Network, IEEE, 12(6), 64-79. doi:10.1109/65.752646

Curado, M.; Monteiro, E. (2004). A survey of QoS routing algorithms. Paper presented at the International Conference on Information Technology (ICIT 2004), Istanbul, Turkey.

Ferguson, A. D.; Guha, A.; Liang, C.; Fonseca, R.; Krishnamurthi, S. (2013). Participatory networking: an API for application control of SDNs. SIGCOMM Comput. Commun. Rev., 43(4), 327-338. doi:10.1145/2534169.2486003

Gallager, R. G. (1977). A Minimum Delay Routing Algorithm Using Distributed Computation. IEEE Transactions on Communications, 25(1), 73-85. doi:10.1109/TCOM.1977.1093711

Hartert, R.; Filsfils, C.; Vissicchio, S.; Telkamp, T.; Schaus, P.; Francois, P.; Bonaventure, O. (2015). A Declarative and Expressive Approach to Control Forwarding Paths in Carrier-Grade Networks. Paper presented at the ACM Conference on Special Interest Group on Data Communication - SIGCOMM '15, New York.

Kreutz, D.; Ramos, F. M. V.; Verissimo, P. E.; Rothenberg, C. E.; Azodolmolky, S.; Uhlig, S. (2015). Software-Defined Networking: A Comprehensive Survey. Proceedings of the IEEE, 103(1), 14-76. doi:10.1109/JPROC.2014.2371999

Layeghy, S.; Pakzad, F.; Portmann, M. (2016). SCOR: Software-defined Constrained Optimal Routing Platform for SDN. arXiv preprint arXiv:1607.03243.

Ma, Q.; Steenkiste, P. (1997). Quality-of-Service Routing for Traffic with Performance Guarantees. In A. Campbell & K. Nahrstedt (Eds.), Building QoS into Distributed Systems (pp. 115-126): Springer US.

Marriott, K.; Stuckey, P. J.; Koninck, L. D.; Samulowitz, H. (2014). A MiniZinc Tutorial. Retrieved from https://www.minizinc.org/downloads/doc-latest/minizinc-tute.pdf

McKeown, N. (2009). Software-defined networking. INFOCOM keynote talk, 17(2), 30-32.

Mir, N. (2014). Computer and Communication Networks, 2nd Edition (Vol. 1). London: Prentice Hall.

Mitchell, S.; OSullivan, M.; Dunning, I. (2011). PuLP: a linear programming toolkit for python. The University of Auckland, Auckland, New Zealand, http://www.optimization-online.org/DB_FILE/2011/09/3178. pdf

Moreira Jr, W. A. M.; Aguiar, E.; Abelém, A.; Stanton, M. (2008). Using multiple metrics with the optimized link state routing protocol for wireless mesh networks. SimpˆUsio Brasileiro de Redes de Computadores e Sistemas DistribuIdos

Nethercote, N.; Marriott, K.; Rafeh, R.; Wallace, M.; Banda, M. ?. G. ?. d. l. (2014). Specification of MiniZinc. In NICTA (Ed.). Victoria Research Lab, Melbourne, Australia: NICTA

Nethercote, N.; Stuckey, P. J.; Becket, R.; Brand, S.; Duck, G. J.; Tack, G. (2007). MiniZinc: Towards a Standard CP Modelling Language. In C., Bessière (Ed.), Principles and Practice of Constraint Programming – CP 2007 (Vol. 4741, pp. 529-543): Springer Berlin Heidelberg.

Patel, M.; Chandrasekaran, R.; Venkatesan, S. (2004). Efficient Minimum-Cost Bandwidth-Constrained Routing in Wireless Sensor Networks. Paper presented at the International Conference on Wireless Networks.

Rossi, F.; Beek, P. V.; Walsh, T. (Eds.). (2006). Handbook of constraint programming (Vol. 1). UK: Elsevier.

Walkowiak, K. (2006). Maximizing residual capacity in connection-oriented networks. Journal of Applied Mathematics and Decision Sciences, 2006, 18. doi:10.1155/jamds/2006/72547

Yap, K.-K.; Huang, T.-Y.; Dodson, B.; Lam, M. S.; McKeown, N. (2010). Towards software-friendly networks. Paper presented at the Proceedings of the first ACM asia-pacific workshop on Workshop on systems, New Delhi, India.