FORMALIZATION OF THE PROBLEM OF THE SDN NETWORK PARTITIONING INTO ROUTING ZONES

A. Kohan, Y. Kulakov, M. Sperkach, O. Zhdanova

Abstract


On of the key goals that should be solved to efficiently organize network routing is splitting the network to, in some sense, optimal set of routing zones. The work considers generalized mathematical formalization of the graph partition problem. Graph defines SDN network topology. According to this topology possible objective functions and constraints were formulated. Objective functions take into account cut parameters, subgraphs and\or cuts boundary vertices characteristics. Constraints take into account weights and probabilities .

Key words: software-defined networking, routing zones, graph partition, graph cut, total cut weight

кандидат технічних наук, Коган А. В., доктор технічних наук, професор, Кулаков Ю. О., кандидат технічних наук, Сперкач М. О., кандидат технічних наук, доцент, Жданова О. Г. Формалізація задачі розбиття мережі SDN на зони маршрутизації / Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського”, Україна, Київ

 Однією з ключових задач, що повинні бути розв’язані для організації ефективної маршрутизації в мережах, є розбиття всієї мережі на оптимальну в деякому сенсі кількість зон маршрутизації. В роботі розглядається узагальнена математична формалізація задачі розбиття графу, який описує фізичну топологію мережі SDN. Відповідно цієї топології були сформульовані можливі цільові функції та визначені обмеження задач розбиття графу. Цільові функції враховують параметри розрізів, підграфів та/або характеристики граничних вершин розбиття. Обмеження враховують ваги та ймовірності виключення/виходу з ладу вершин і ребер.

Ключові слова: програмно-конфігурована мережа, зони маршрутизації, граф, розбиття графу, розріз графу, гранична вершина, сумарна вага розрізу.


Full Text:

PDF

References


O ́ Briain Diarmuid. Network Revolution - Software Defined Networking and Network Function Virtualisation playing their part in the next Industrial Revolution / Diarmuid O ́ Briain, David Denieffe, Yvonne Kavanagh and Dorothy Okello // Symposium on Transformative Digital Technologies. Kamapla. – 2016. рр. 1-8.

Wang Runxin. QoS-aware Multipathing in Datacenters Using Effective Bandwidth Estimation and SDN / Runxin Wang, Simone Mangiante, Alan Davy, Lei Shi, Brendan Jennings. – 2016. – рр. 359-364.

Caria Marcel. SDN Partitioning: A Centralized Control Plane for Distributed Routing Protocols / Marcel Caria, Admela Jukan, Marco Hoffmann // Networking and Internet Architecture. – 2016. – рр. 1-14.

Arlimatti Shivaleela. Minimization of Communication Cost between Controller Domains with Graph Partitioning Algorithms / Shivaleela Arlimatti, Suhaidi Hassan and Adib Habbal // Revista de la Facultad de Ingeniería U.C.V. – 2016. – Vol. 31 – N°5.– рр. 1-8.

Xiao P. The SDN controller placement problem for WAN / P. Xiao, W. Qu, H. Qi, Z. Li and Y. Xu // 2014 IEEE/CIC International Conference on Communications in China (ICCC), Shanghai. – 2014. – pp. 220-224.

Christian Schulz. Graph Partitioning and Graph Clusteringin Theory and Practice // Institute for Theoretical Informatics Karlsruhe Institute of Technology (KIT). – May 20, 2016. – рр. 24-187.

References:

Diarmuid O ́ Briain, David Denieffe, Yvonne Kavanagh and Dorothy Okello. Network Revolution - Software Defined Networking and Network Function Virtualisation playing their part in the next Industrial Revolution. Symposium on Transformative Digital Technologies. Kamapla.  2016. – рр. 1-8.

Runxin Wang, Simone Mangiante, Alan Davy, Lei Shi, Brendan Jennings. QoS-aware Multipathing in Datacenters Using Effective Bandwidth Estimation and SDN. – 2016. – рр. 359-364.

Marcel Caria, Admela Jukan, Marco Hoffmann. SDN Partitioning: A Centralized Control Plane for Distributed Routing Protocols. Networking and Internet Architecture. – 2016. – рр. 1-14.

Shivaleela Arlimatti, Suhaidi Hassan and Adib Habbal. Minimization of Communication Cost between Controller Domains with Graph Partitioning Algorithms. Revista de la Facultad de Ingeniería U.C.V. – 2016. – Vol. 31 – N°5.– рр. 1-8.

P. Xiao, W. Qu, H. Qi, Z. Li and Y. Xu, "The SDN controller placement problem for WAN," 2014 IEEE/CIC International Conference on Communications in China (ICCC). Shanghai. – 2014. – pp. 220-224.

Christian Schulz. Graph Partitioning and Graph Clusteringin Theory and Practice. Institute for Theoretical Informatics Karlsruhe Institute of Technology (KIT). – May 20, 2016. – рр. 24-187.




DOI: https://doi.org/10.26886/2414-634X.3(22)2018.3

Refbacks

  • There are currently no refbacks.