 ICACT20210213 Slide.01
[Big Slide]
[YouTube] |
Chrome  Click!! |
 |
Hello everyone, my name is Nada Alzaben and on behalf of my adviser Dr. Engels and myself, I would like to present for the ICACT 2021 conference a solution to an optimization problem. We present a solution to the end-to-end routing in SDN controllers using max-flow min-cut routine selection algorithm.
|
| ICACT20210213 Slide.02
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
To begin with the question why end to end routing we say that with the exponential growth of communication networks along with the need to share information over it some of which are in the form of video files that consume the network traffic, these files need to be transmitted from one end to another end using the same path. Therefore, end to end routing became critically important.
|
| ICACT20210213 Slide.03
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Routing is the process of finding a communication path between two devices in the network to transfer information flows from one device to another. We define the problem as: Given an arbitrary graph G=(V,E) and a set of flows F, where each edge on the graph has a capacity that represent the maximum number of flows that can be transmitted at a time on that edge, and each flow is characterized by the number of packets it holds and a release time, non-preemptively route all flows on graph G to optimize some objective function.
|
| ICACT20210213 Slide.04
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
The Software Defined Network is a network model that splits the network functionality into two separate planes: control plane and data plane. The control plane is placed in the SDN controller and the data plane in the network switches. The controller is responsible of finding the routes for the network flows, since it holds a global view of the network, then it loads the route into the network switches to forward the flow from its source to the destination.
|
| ICACT20210213 Slide.05
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Shortest Path algorithms are most widely used in end-to-end routing algorithms, however, they do not consider explicitly bottlenecks when routing which results in poor performance in high load networks. The shortest path based algorithms consider the shortest distance path or the minimum hops path. Bottlenecks in networks occur when a high traffic flow demands to be routed over a set of edges where the number of flows are exceeding the edge capacity which leads to congestion at the edges. The Shortest Path finds the shortest path available and sends the traffic which most likely will meet in a specific path segment which causes the bottleneck problem. Clearly, the routing algorithm that will resolve or at least minimize the occurrence of bottleneck problem has to consider congestion explicitly within its algorithm.
Routing on the World Wide Web has self similarity traffic which tends to be heavy tailed distribution file size and that self similarity effects the network performance. One common heavy tailed distribution is the Pareto distribution which we adopt for our flow size distribution.
|
| ICACT20210213 Slide.06
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
We propose an algorithm that is based on the max-flow min cut theory, that was developed in 1950 by Fulkerson and Shannon. Its is a polynomial time algorithm meaning the algorithm can solve a problem optimally in polynomial time bounded by an upper bound equal to the number of edges time the maximum number of packet flows. The MFMC identifies the minimum number of edges with maximum flow capacity such that if removed it will partition the network in that the source node is disconnected from the destination.
|
| ICACT20210213 Slide.07
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
The flow routing process happens in two steps: selecting a flow from the flow set then find a route for that flow. Our algorithm is used for the second step of this process, finding a path. We utilize the MFMC process in partitioning the network by a recursive loop of cuts where each cut contains a set of minimum number of edges with their removal the source and the destination are disconnected. The bandwidth of a path is defined as the minimum edge capacity in the path
|
| ICACT20210213 Slide.08
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Here we can see the code of how our algorithm works. The input values are an undirected network graph G and a flow f, and the output is a path for that flow. The function, find path in graph, first checks if the source and destination of the flow are connected. If so, it will get the minimum edge cut set and then pick an edge e=(e1,e2) from the set. Then it appends that edge to the path list. If the selected edge contains both source and destination it will return the path, otherwise, it will set node e2 as the new source and node e1 as the new destination, then recursively run the function on the two partitioned networks. This loop of partitioning continues until the path is constructed.
|
| ICACT20210213 Slide.09
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
In our MC suite of algorithms, we have five variations. Each algorithm is varying in the decision criteria it adopts for picking the edge from the cut set. We can see in the table that MC1 and MC2 selects a random edge from the cut set, however, MC2 selects the edge that does not cause any cycles in the path. MC3 bases its selection on being part of a minimum hop path from the source to the destination. MC4 and MC5 are based on the available capacity of the edges, where MC4 selects the edge with minimum capacity which is the most congested and MC5 select the one with maximum capacity which is the least congested.
|
| ICACT20210213 Slide.10
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
To illustrate how our algorithm works we will take this example of finding a path from node s to node d using MC5.
|
| ICACT20210213 Slide.11
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
The algorithm finds that the maximum flow capacity that could be sent from the s to d is 4. then it finds the minimum number of edges with that maximum capacity. Once the edges are cut we pick from the cut set the edge with maximum available capacity and save it as part of our path.
|
| ICACT20210213 Slide.12
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
After that, the end node of the picked edge becomes our new d node. The cutting process loops again and again the edge with maximum capacity is picked.
|
| ICACT20210213 Slide.13
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
The process recursively loops until we construct our path that connects s to d.
|
| ICACT20210213 Slide.14
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
The path from s to d is found
|
| ICACT20210213 Slide.15
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Our network simulator is developed in Python
and it models an un-directed graph using two network topology: Mesh network and Barabasi Albert network.
Our mesh network is a partial mesh because it gave us a distinctive difference in our objective functions compared to the full connected mesh. And the Barabasi Albert network (AB), which adopts the concept of generating networks based on power law degree distribution, is generated using Networkx library.
The size of the network ranges from 10 to 50 nodes. For each generated network we randomly set each edge capacity between 1 and 10.
In general, a set of flows are randomly generated and simulate an online flows where clairvoyant is not enabled and we non-preemptively route them over the network graph
Each flow is described with source node, destination node, release time either identical or arbitrary, and flow size in either Gaussian or Pareto distribution.
The simulation calculates as network optimization factors: the mean wait time which is the average delay rate, the mean slowdown, the maximum completion time, and the mean throughput.
|
| ICACT20210213 Slide.16
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
We evaluate our MC suite of algorithms, compared to the traditional shortest path algorithms, considering minimum distance or minimum hops in Dynamic Shortest Path with minimum distance(we abbreviate it by DSP-md), dynamic shortest path with minimum hops(the DSP-mh). Also, we evaluate our algorithm to the least congested paths the Dynamic shortest path inverted weight DSP-inv which is the maximum distance.
|
| ICACT20210213 Slide.17
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
In the next slides we present and analyze the results of our simulation. All the objective functions in concern were calculated and analyzed and compared to the shortest path algorithms.
|
| ICACT20210213 Slide.18
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
For the objective function minimizing the mean wait time, regardless of network topology, we found that from the MFMC variation only MC3 minimizes the mean wait time more than the DSP-md, DSP-mh, DSP-inv on average by 18.4%, 11.7% and 15.3%, respectively. Moreover, we have found that the mean wait time is minimized with flows with Pareto size distribution more than with flows of Gaussian size distribution by 20.6% and 16.1%, respectively. However, the other variation MC1,MC2,MC4 and MC5 have increased the mean wait time over all DSP on average by 16.4%.
As an illustration, we give an example of routing in BA network with arbitrary released time flows with pareto size distribution
|
| ICACT20210213 Slide.19
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
In the effort of minimizing the mean slowdown we found that MC3 minimize it slightly more than all DSP algorithms on average by 6.1%. Moreover, we have found that the mean slowdown of MC3 compared to DSP-md is minimized with flows with Pareto size distribution more than with flows of Gaussian size distribution by 12% and 8.4%, respectively. However, the other variation MC1,MC2,MC4 and MC5 have increased the mean slowdown over all DSP on average by 5% as illustrated in the Fig which is an example of routing in BA network with arbitrary released time flows with pareto size distribution
|
| ICACT20210213 Slide.20
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
In the effort of minimizing the maximum completion time we found that MC3 minimizes it more than all DSP algorithms on average by 9.6%. Moreover, we have found that the maximum completion time for MC3 compared to DSP-md is minimized with flows with Pareto size distribution more than with flows of Gaussian size distribution by 18.2% and 7.5%, respectively. However, the other variation MC1,MC2,MC4 and MC5 have increased the maximum completion time over all DSP algorithms on average by 5.7% . In the Fig we illustrate an example of routing in BA network with arbitrary released time flows with Pareto size distribution
|
| ICACT20210213 Slide.21
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
To maximize the mean throughput, we also found that MC3 maximized the mean throughput more than all DSP on average by 18.3%. Moreover, we have found that the mean throughput is maximized with flows with Pareto size distribution same as with flows of Gaussian size distribution by 18.6% and 17.2%, respectively. However, MC2 have not increased the mean throughput over the DSP, it has minimized it by 5.4%, As for MC1, MC4,MC5, they maximized the mean throughput more than all DSP on average by 9.0%
|
| ICACT20210213 Slide.22
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Here we present the results of our algorithms compared to shortest path algorithms in maximizing the mean throughput. Positive values mean the MC algorithm is performing better. In this table we can see that MC3 has performed better than the other variations.
In all our simulations we found that the constrain on flow release time, either arbitrary or identical, didn’t have any impact on the evaluation on our objective functions. The min-cut algorithm that chooses its path based on minimum hop performed better in minimizing the mean wait time, minimizing the maximum completion time and maximizing the mean throughput, however, it has insignificant change in the mean slowdown.
|
| ICACT20210213 Slide.23
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
To optimize the end to end routing in the Software Define Network controllers a routing algorithm should be used to maximize performance of the network.
Our simulation showed that the novel max-flow min-cut based algorithm, MC3,with a decision based on minimum hops performed better compared to the traditional shortest path algorithm variants. Our algorithms are topology independent and flow release time independent.
Since network bottlenecks causes performance degradation, our Max-Flow Min-Cut based algorithms explicitly identify the bottlenecks through the min cut edges which holds the least available flows, and, by choosing the edge on the shortest dynamic path, our algorithm is able to find paths that yield significant improvement over the commonly used shortest path algorithms.
The diversity of our MFMC suite of algorithms demonstrates that a shortest path approach, such as MC3, as opposed to a balanced or longer path approach, yields the best expected performance across a broad range network types and flow size distributions
|
| ICACT20210213 Slide.24
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Thank you |
