Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Photonic Network Communications 3/2021

26-10-2021 | Original Paper

A novel flow routing algorithm based on non-dominated ranking and crowd distance sorting to improve the performance in SDN

Authors: Alireza Shirmarz, Ali Ghaffari

Published in: Photonic Network Communications | Issue 3/2021

Login to get access
share
SHARE

Abstract

Software-defined network (SDN) is an architecture with a physical or conceptual central controller. This architecture separates data and control plane causing network flexibility, programmability, and manageability. A packet when is received by the forwarding element (FE) as the first packet of the flow is forwarded towards the controller in the packet-in message; then, the controller decides for all packets belonging to the flow. The controller imposes the rule for the flow to the FE; thus, the FE acts based on the matching rules with the ingress packet in the flow table. Routing can be done by considering performance metrics to improve entire network performance in SDN. Performance and cost metrics include utilization, delay, jitter, packet loss ratio (PLR), blocking probability (BP), and link cost, so an optimized path selection is a multi-objective optimization problem and NP-Hard that we will consider. In this paper, we try to provide a comprehensive algorithm for optimizing the entire network performance in SDN. We propose the novel algorithm for flow routing based on three steps: (1) a linear algorithm is developed to extract the path between each source and destination in the controller, (2) non-dominated ranking is used to categorize the extracted paths, and finally, (3) the crowd distance sorting algorithm is implemented to select the optimized route from all performance dimensions. To evaluate the proposed algorithm, the shortest path and greedy-based routing algorithms will be simulated by Java, and the simulation results show that the proposed optimization algorithm improves the all mentioned performance criteria, simultaneously.
Literature
1.
go back to reference Masoudi, R., Ghaffari, A.: Software defined networks: a survey. J. Netw. Comput. Appl. 67(May), 1–25 (2016) CrossRef Masoudi, R., Ghaffari, A.: Software defined networks: a survey. J. Netw. Comput. Appl. 67(May), 1–25 (2016) CrossRef
2.
go back to reference Shirmarz, A., Ghaffari, A.: An autonomic software defined network (SDN) architecture with performance improvement considering. J. Inf. Syst. Telecommun. 8(2), 1–9 (2020) Shirmarz, A., Ghaffari, A.: An autonomic software defined network (SDN) architecture with performance improvement considering. J. Inf. Syst. Telecommun. 8(2), 1–9 (2020)
3.
go back to reference Pan, J., Paul, S., Jain, R.: A survey of the research on future internet architectures. Commun. Mag. IEEE 49(7), 26–36 (2011) CrossRef Pan, J., Paul, S., Jain, R.: A survey of the research on future internet architectures. Commun. Mag. IEEE 49(7), 26–36 (2011) CrossRef
4.
go back to reference Maksymyuk, T., Jo, M.: An IoT based monitoring framework for software defined 5G mobile networks. In: ACM, pp. 7–10, 2017. Maksymyuk, T., Jo, M.: An IoT based monitoring framework for software defined 5G mobile networks. In: ACM, pp. 7–10, 2017.
5.
go back to reference Shirmarz, A., Ghaffari, A.: Performance issues and solutions in SDN-based data center: a survey. J. Supercomput., 2020. Shirmarz, A., Ghaffari, A.: Performance issues and solutions in SDN-based data center: a survey. J. Supercomput., 2020.
6.
go back to reference Bannour, F., Souihi, S., Mellouk, A.: Distributed SDN control: survey, taxonomy, and challenges. IEEE Commun. Surv. Tutorials 20(1), 333–354 (2018) CrossRef Bannour, F., Souihi, S., Mellouk, A.: Distributed SDN control: survey, taxonomy, and challenges. IEEE Commun. Surv. Tutorials 20(1), 333–354 (2018) CrossRef
7.
go back to reference Karakus, M., Durresi, A.: A survey: control plane scalability issues and approaches in software-defined networking (SDN). Comput. Networks 112, 279–293 (2017) CrossRef Karakus, M., Durresi, A.: A survey: control plane scalability issues and approaches in software-defined networking (SDN). Comput. Networks 112, 279–293 (2017) CrossRef
8.
go back to reference Hoffmann M. et al.: SDN and NFV as enabler for the distributed network cloud. Mob. Networks Appl., pp. 1–88, 2017. Hoffmann M. et al.: SDN and NFV as enabler for the distributed network cloud. Mob. Networks Appl., pp. 1–88, 2017.
9.
go back to reference Of, I., Cities, S.: Internet protocol data communication service – IP packet transfer and availability performance parameters Recommend. 2016. Of, I., Cities, S.: Internet protocol data communication service – IP packet transfer and availability performance parameters Recommend. 2016.
10.
11.
12.
go back to reference Oran, D., Oran, D.: RFC 1142 (IS-IS Protocol) (1990) Oran, D., Oran, D.: RFC 1142 (IS-IS Protocol) (1990)
13.
go back to reference Meyer, D.: RFC 4274 (BGP-4 Protocol Analysis) (2006) Meyer, D.: RFC 4274 (BGP-4 Protocol Analysis) (2006)
14.
go back to reference Karakus, M., Durresi, A.: Quality of service (QoS) in software defined networking (SDN): a survey. J. Netw. Comput. Appl. 80, 200–218 (2017) CrossRef Karakus, M., Durresi, A.: Quality of service (QoS) in software defined networking (SDN): a survey. J. Netw. Comput. Appl. 80, 200–218 (2017) CrossRef
15.
go back to reference Guck, J.W., Van Bemten, A., Reisslein, M., Kellerer, W.: Unicast QoS routing algorithms for SDN: A comprehensive survey and performance evaluation. IEEE Commun. Surv. Tutorials 20(1), 388–418 (2018) CrossRef Guck, J.W., Van Bemten, A., Reisslein, M., Kellerer, W.: Unicast QoS routing algorithms for SDN: A comprehensive survey and performance evaluation. IEEE Commun. Surv. Tutorials 20(1), 388–418 (2018) CrossRef
16.
go back to reference Li, Z.: Solving the multi-constrained path selection problem by using depth first search 1. In: 2nd Int’l Conf. on Quality of Service in Heterogeneous Wired/Wireless Networks (2005) Li, Z.: Solving the multi-constrained path selection problem by using depth first search 1. In: 2nd Int’l Conf. on Quality of Service in Heterogeneous Wired/Wireless Networks (2005)
17.
go back to reference Wang, Z., Crowcroft, J., Criterion, A.S.: Quality-of-service routing for supporting multimedia applications. In: 1228 IEEE Journal on Selected Areas in Communications, 14(7), 1228–1234 (1996) Wang, Z., Crowcroft, J., Criterion, A.S.: Quality-of-service routing for supporting multimedia applications. In: 1228 IEEE Journal on Selected Areas in Communications, 14(7), 1228–1234 (1996)
18.
go back to reference Routing, M.Q., Xue, G., Member, S., Zhang, W., Tang, J.: Polynomial time approximation algorithms for multi-constrained QoS routing. IEEE/ACM Trans. Netw. 16(3), 656–669 (2008) CrossRef Routing, M.Q., Xue, G., Member, S., Zhang, W., Tang, J.: Polynomial time approximation algorithms for multi-constrained QoS routing. IEEE/ACM Trans. Netw. 16(3), 656–669 (2008) CrossRef
19.
go back to reference Alpar Juttner, Z.R., Szviatovszki, B., Mecs, I.: Lagrange relaxation based method for the QoS routing problem. In: IEEE Infocom, 2, pp. 859–868 (2001) Alpar Juttner, Z.R., Szviatovszki, B., Mecs, I.: Lagrange relaxation based method for the QoS routing problem. In: IEEE Infocom, 2, pp. 859–868 (2001)
20.
go back to reference Chen, S., Song, M., Sahni, S.: Two techniques for fast computation of constrained shortest paths. IEEE ACM Trans. Netw. 16(1), 105–115 (2008) CrossRef Chen, S., Song, M., Sahni, S.: Two techniques for fast computation of constrained shortest paths. IEEE ACM Trans. Netw. 16(1), 105–115 (2008) CrossRef
21.
go back to reference Shirmarz, A., Ghaffari, A.: Taxonomy of controller placement problem ( CPP ) optimization in software defined network ( SDN ): a survey. J. Ambient Intell. Humaniz. Comput., 0123456789 (2021) Shirmarz, A., Ghaffari, A.: Taxonomy of controller placement problem ( CPP ) optimization in software defined network ( SDN ): a survey. J. Ambient Intell. Humaniz. Comput., 0123456789 (2021)
22.
go back to reference Singh, A.K., Srivastava, S.: A survey and classification of controller placement problem in SDN. Int. J. Netw. Manag. 28(3), 1–25 (2018) CrossRef Singh, A.K., Srivastava, S.: A survey and classification of controller placement problem in SDN. Int. J. Netw. Manag. 28(3), 1–25 (2018) CrossRef
23.
go back to reference Jalili, A., Keshtgari, M., Akbari, R.: Optimal controller placement in large scale software defined networks based on modified NSGA-II. Appl. Intell. 48(9), 2809–2823 (2018) CrossRef Jalili, A., Keshtgari, M., Akbari, R.: Optimal controller placement in large scale software defined networks based on modified NSGA-II. Appl. Intell. 48(9), 2809–2823 (2018) CrossRef
24.
go back to reference Egilmez, H.E., Civanlar, S., Tekalp, A.M.: An optimization framework for QoS-enabled adaptive video streaming over openflow networks. IEEE Trans. Multimedia 15(3), 710–715 (2012) CrossRef Egilmez, H.E., Civanlar, S., Tekalp, A.M.: An optimization framework for QoS-enabled adaptive video streaming over openflow networks. IEEE Trans. Multimedia 15(3), 710–715 (2012) CrossRef
25.
go back to reference Beshley, M., Seliuchenko, M., Panchenko, O., Polishuk, A.: Adaptive flow routing model in SDN. In: IEEE CADSM , pp. 21–25 (2017) Beshley, M., Seliuchenko, M., Panchenko, O., Polishuk, A.: Adaptive flow routing model in SDN. In: IEEE CADSM , pp. 21–25 (2017)
26.
go back to reference Mehboob, U., Qadir, J., Ali, S., Vasilakos, A.: Genetic algorithms in wireless networking: techniques, applications, and issues. Soft Comput. (2017) Mehboob, U., Qadir, J., Ali, S., Vasilakos, A.: Genetic algorithms in wireless networking: techniques, applications, and issues. Soft Comput. (2017)
27.
go back to reference Zhoulaian, E., Mirabedini, S.J., Sadeghzadeh, M.: Multi-objective routing by using non-dominated sorting genetic algorithm in computer networks. Int. J. Comput. Sci. Netw. Solut. 2(7), 29–41 (2014) Zhoulaian, E., Mirabedini, S.J., Sadeghzadeh, M.: Multi-objective routing by using non-dominated sorting genetic algorithm in computer networks. Int. J. Comput. Sci. Netw. Solut. 2(7), 29–41 (2014)
28.
go back to reference Oh, S., Lee, J., Lee, K., Shin, I.: RT-SDN: adaptive routing and priority ordering for software-defined real-time networking. Springer Int. Publ. AG, part Springer Nat., (2018) Oh, S., Lee, J., Lee, K., Shin, I.: RT-SDN: adaptive routing and priority ordering for software-defined real-time networking. Springer Int. Publ. AG, part Springer Nat., (2018)
29.
go back to reference Zhao, Z., Wu, B., Xiao, J., Hu, Z.: Joint optimization of flow entry aggregation and routing selection in software defined wireless access networks. Springer Int. Publ. AG, pp. 834–839 (2018). Zhao, Z., Wu, B., Xiao, J., Hu, Z.: Joint optimization of flow entry aggregation and routing selection in software defined wireless access networks. Springer Int. Publ. AG, pp. 834–839 (2018).
30.
go back to reference Fei, X., Liu, F., Xu, H., Jin, H.: Adaptive VNF scaling and flow routing with proactive demand prediction. In: IEEE Conference on Computer Communications, pp. 486–494 (2018). Fei, X., Liu, F., Xu, H., Jin, H.: Adaptive VNF scaling and flow routing with proactive demand prediction. In: IEEE Conference on Computer Communications, pp. 486–494 (2018).
31.
go back to reference Bagci, K.T., Member, S., Tekalp, A.M.: Dynamic resource allocation by batch-optimization for value-added video services over SDN. IEEE Trans. Multimed. 20(11), 3084–3096 (2018) CrossRef Bagci, K.T., Member, S., Tekalp, A.M.: Dynamic resource allocation by batch-optimization for value-added video services over SDN. IEEE Trans. Multimed. 20(11), 3084–3096 (2018) CrossRef
32.
go back to reference Cai, L., Chen, D., Zhang, L.: A strategy of dynamic routing based on SDN. In: The 35th Annual IEEE International Conference on Computer Communications, ICMSIE, pp. 373–378 (2017) Cai, L., Chen, D., Zhang, L.: A strategy of dynamic routing based on SDN. In: The 35th Annual IEEE International Conference on Computer Communications, ICMSIE, pp. 373–378 (2017)
33.
go back to reference Huang, M., Liang, W., Xu, Z., Xu, W., Guo, S., Xu, Y.: Dynamic routing for network throughput maximization in software-defined networks. In: The 35th Annual IEEE International Conference on Computer Communications (2016). Huang, M., Liang, W., Xu, Z., Xu, W., Guo, S., Xu, Y.: Dynamic routing for network throughput maximization in software-defined networks. In: The 35th Annual IEEE International Conference on Computer Communications (2016).
34.
go back to reference Lin, R.: A bat algorithm for SDN network scheduling. EURASIP J. Wirel. Commun. Netw. 1687–1499, 1–9 (2018) Lin, R.: A bat algorithm for SDN network scheduling. EURASIP J. Wirel. Commun. Netw. 1687–1499, 1–9 (2018)
35.
go back to reference Tomovic, S., Lekic, N., Radusinovic, I.: A new approach to dynamic routing in SDN networks. In: Proceedings of the 18th Mediterranean Electrotechnical Conference MELECON, vol. 2012(315970), pp. 18–20 (2016). Tomovic, S., Lekic, N., Radusinovic, I.: A new approach to dynamic routing in SDN networks. In: Proceedings of the 18th Mediterranean Electrotechnical Conference MELECON, vol. 2012(315970), pp. 18–20 (2016).
36.
go back to reference Rego, A., Sendra, S., Jimenez, J.M., Lloret, J.: OSPF routing protocol performance in software defined networks. In: 4th International Conference on Software Defined Systems, SDS 2017, pp. 131–136 (2017). Rego, A., Sendra, S., Jimenez, J.M., Lloret, J.: OSPF routing protocol performance in software defined networks. In: 4th International Conference on Software Defined Systems, SDS 2017, pp. 131–136 (2017).
37.
go back to reference Li, G., Qian, Y., Liu, L., Yang, Y.R.: JMS: Joint bandwidth allocation and flow assignment for transfers with multiple sources. In: Proceedings - 2018 IEEE 3rd International Conference on Data Science in Cyberspace, DSC 2018, pp. 123–130 (2018). Li, G., Qian, Y., Liu, L., Yang, Y.R.: JMS: Joint bandwidth allocation and flow assignment for transfers with multiple sources. In: Proceedings - 2018 IEEE 3rd International Conference on Data Science in Cyberspace, DSC 2018, pp. 123–130 (2018).
38.
go back to reference Shirmarz, A., Ghaffari, A.: An adaptive greedy flow routing algorithm for performance improvement in a software‐defined network. In: Int. Numer. Model. Electron. Networks, Devices, Fields-Wiley online Libr., March, pp. 1–21 (2019). Shirmarz, A., Ghaffari, A.: An adaptive greedy flow routing algorithm for performance improvement in a software‐defined network. In: Int. Numer. Model. Electron. Networks, Devices, Fields-Wiley online Libr., March, pp. 1–21 (2019).
39.
go back to reference Wang, X., Zhang, Q., Ren, J., Xu, S., Wang, S., Yu, S.: Toward efficient parallel routing optimization for large-scale SDN networks using GPGPU. J. Netw. Comput. Appl. 113, 1–13 (2018) CrossRef Wang, X., Zhang, Q., Ren, J., Xu, S., Wang, S., Yu, S.: Toward efficient parallel routing optimization for large-scale SDN networks using GPGPU. J. Netw. Comput. Appl. 113, 1–13 (2018) CrossRef
Metadata
Title
A novel flow routing algorithm based on non-dominated ranking and crowd distance sorting to improve the performance in SDN
Authors
Alireza Shirmarz
Ali Ghaffari
Publication date
26-10-2021
Publisher
Springer US
Published in
Photonic Network Communications / Issue 3/2021
Print ISSN: 1387-974X
Electronic ISSN: 1572-8188
DOI
https://doi.org/10.1007/s11107-021-00951-x