End-to-End Routing Algorithm Based on
Max-Flow Min-Cut in SDN Controllers
Nada Alzaben*, Daniel W. Engels*** Dept. of Computer Science, College of Computer Science and Information, Princess Nourah Bint Abdulrahman
University, Riyadh, Saudi Arabia**AT&T Center for Virtualization, Southern Methodist University, Dallas, USA
nialzaben@pnu.edu.sa, Daniel.w.engels@gmail.com
Abstract— In this paper, we present seven novel Max-Flow Min-Cut (MFMC) based algorithms that solve the flow routing
problem in the Software Defined Network Controller. Our algorithms identify potential traffic bottlenecks using the MFMC cut,and they avoid the bottlenecks during flow route construction through their choice of the cut edge added to the route. Ouralgorithms utilize either a random edge selection, a shortest path edge selection, or an edge capacity-based selection from the set ofcut edges. Our simulation results show improvement in the network performance when using MFMC and shortest path edge
selection compared to simple shortest path first algorithms, such that the mean wait time is reduced by 15.1%, the mean slowdown
is reduced by 5.1%, reducing the maximum completion time by 9.6%, and increasing the mean throughput by 18.3%. Therefore, byexplicitly considering congestion in routing decisions, better network performance is achieved.
Keyword— Heuristic algorithm, Peer-to-peer computing, Routing, Software defined networking.
Nada Alzaben. This author became a Member (M’18) of IEEE in 2018. Saudi citizen born in Riyadh, Saudi Arabia. Received her B.S.
(2001) and M.S. (2012) in computer science and information from King Saud Univ. in Riyadh, Saudi Arabia.
She is currently working on her Ph.D. in computer science at Southern Methodist Univ., Dallas, TX, USA. Her research interests
include network communications, routing and scheduling, network performance analysis. She is a Lecturer in computer science andinformation college at Princess Nourah Bint Abdulrahman Univ., Riyadh, Saudi Arabia. Previously she worked as a senior programmer atKing Saud Univ. She has 5 research publications in the field of computer networks and AI.

Dr. Daniel W. Engels received his Ph.D. from the Massachusetts Institute of Technology. Born in the US.
Dr. Engels is currently Head of AI, Cyber security Science and Analytics, at HSBC. Previously, Dr. Engels was a professor atSouthern Methodist University (SMU) where he was one of the creators of, and the first Director of, the Master of Science in Data
Science (MSDS) program where he grew the program from 0 students to more than 300 students in its first two years of operation In
addition to his data science expertise, Dr. Engels is an expert in security and in RFID and IoT technologies, systems, andapplications. He was one of the founders of the IEEE International Conference on RFID, and he was the Chair of the IEEE
Technical Committee on RFID in 2011 and in 2012. Dr. Engels is the former Director of Research of the Auto-ID Labs at MIT,
where he led the development of several RFID protocols including the original “Gen2” protocol, and he is an original member of theresearch team that founded the Auto-ID Center at MIT and created the EPC System.
He has over 100 peer reviewed publications and 8 issued U.S. patents in data science, RFID, RFID applications, Internet ofThings, security, embedded computing, and computer-aided design. Dr. Engels received the 2014 AIM Ted Williams Award inrecognition of his contributions to the AIDC industry. Dr. Engels is a member of AIDC 100 and is a Senior Member of IEEE.