Improving Centralized Path Calculation Based on Graph Compression

Zhenglian Li＊, Lixin Ji, Ruiyang Huang, Shuxin Liu

National Digital Switching System Engineering& Technological R&D Center, Zhengzhou, China

I. INTRODUCTION

How to efficiently search the shortest path given a weighted graph is extremely important problem in communication networks. This is a stronger requirement when Software-defined networking (SDN) is proposed. SDN decouples the network control plane from the data forwarding plane. The control plane is centrally deployed in the commodity device, called controller, which handles the global network view. In this context, the legacy distributed routing algorithm which always calculates the shortest path based on a locally small network topology is transformed into centralized routing algorithm (i.e., routing applications upon the controller) which calculates the shortest path based on the largely global network topology. The existing typical shortest path algorithm is insufficient in efficiency. efficient approach of the single source shortest path problem on SDN-enabled communication networks is an extremely important requirement.

Since the most well-known algorithm for finding a single-source shortest path ---Dijkstra’s algorithm, a large number of approaches have been proposed to improve the performance of shortest path algorithms using various techniques and heuristics. In the early time, some works mainly shifts different constraints to vary the time complexity in path calculations,such as single-source shortest path, k-shortest paths, etc. Other works focuses on designing an efficient tree structures to improve the Dijkstra’s algorithm, such as Fibonacci-heap min-priority queue0.

Recently, some state-of-art approaches have been proposed to improve the performance of shortest path algorithms using different graph representations 0-0. The literature 0 improved the path calculation based on the search strategy by adjusting the weighted value and removing the large number of irrelevant nodes.In the same time, some works devote into programming optimized network structure so that the path calculation is much more efficient,finding the shortest path based on graph partitioning00, for example. Especially, literature 0 gives an extended Dijkstra’s algorithm in Open Flow-enabled SDN networks. The core idea is mining the available network features to reduce the time of path search. They simplify the original graph by clustering nodes, and then search for the path based on the generated graph.

More recently, SDN oriented routing algorithms have been rise up. Gastelo 0 aims to develop a genetic algorithm (GA) to solve a network routing protocol problem, and implement it on the new SDN architecture. Shahid et al. 0 focused on implementing innovtive routing using software defined networking.The goal of this work is to restructure the SDN controller (Floodlight) so that it can collect the actual bandwidth of all the links in the network and use this information to calculate optimal path with highest bandwidth path instead of the default least hop path. Literature0 proposed link failure recovery using shortest path fast rerouting technique in SDN. Jiang et al.0 extends the well-known Dijkstra’s shortest path algorithm to consider not only the edge weights but also the node weights for a graph derived from the underlying SDN topology.And Xu et al. 0 propose propose an efficient shortest-path query algorithm (BBQ) used on large-scale graphs. a novel fast shortest-path queries on large-scale graphs. It reduces the running time of shortest-path query via tree decomposition and used in the SDN. Our work exploit a different idea, reducing a original graph into a compression one.

In this paper, we exploit the compression graph, one of branches in the field of graph representation, to improve the performance of the shortest path algorithm. In the remaining sections, we firstly describe the problem based on the representation in the graph theory. And then we propose a new improved single-source shortest path algorithm based on compression graph. Finally, we implement a centralized version of our algorithm based on the Ryu, and validate that its complexity always be bounded by the complexity of Dijkstra’s algorithm.

The authors try to improve the performance of finding shortest path by using a form of graph representation, path compression.

II. THE PROBLEM STATEMENT

In a SDN-enabled network, letG=(V,E,w)be a globally directed graph maintained by the controller, andG′= (V,E′,w) the compressed graph that is produced based on graphG,whereVrepresents node set,Erepresents edge set,E′ represents a set of edges produced by using a well-defined compression function, andwrepresents weight function with non-negative value for each edgee∈E.Letsandtbe the pairwise nodes, wheres∈Vrepresents the source andt∈Vrepresents the destination. The single-pair shortest path problem is to search the path with the minimum cost of edges fromstot.

III. SHORTEST PATH USING COMPRESSION

Typically, there are two representations for graphs, adjacency matrix and adjacency list.The former usesO(n2) space but deciding adjacency with constant time. The later usesO((n+m)log2n) space and deciding adjacency takesO(log2n)time. In this paper, we use two matrices with maximumelements to represent the graph in normal and reverse represents [0] which is easily used to developing parallel algorithms. For efficient implementation and to save storage, the matrix can also be represented as a linear array withentries.

Such graph representation stores all paths from every possible node to all reachable nodes in the graph. There are several advantages using this representation. First, it takesa linear time to examine the path existence.Second, it could search sub-paths of nodes of in-degree and out-degree of 1.

Algorithm 1. Path compression algorithm.

Algorithm 2. Shortest path algorithm with path compression.

Based on the graph representation, we generate graphG′= (V,E′,w) by typical path compression onG=(V,E,w). It reduces the number of nodes and edges necessary to compute paths. The compression function is summarized as algorithm 1.

Note that, the direct path is flagged with 0/1. We can use reverse matrix to mark candidate nodes. The algorithm 1 can be implemented by cloning the candidate nodes into an independent reduced matrix with flags. By path compression, we can get the compressed graph with mark and reverse matrix.

The path compression reduces a number of edges and nodes that make the search take less time than searching in the entire graph. The shortest path algorithm based on path compression is listed in algorithm 2.

Where the functionShortest Path() calculates the shortest distance betweensandtusing reduced graph.

IV. PERFORMANCE EVALUATION

This section evaluates our algorithm with sparse graph and dense graph respectively. Our evaluation is carried out based on mininet0, a simulated environment for SDN. We generate two different switch network topologies, the sparse one and dense one. We implement our algorithm as routing app based on Ryu 0, a typical open source SDN controller. We compare our algorithm with Ryu’s pre-installed routing app based on the Dijkstra’s algorithm,GA algorithm[8] and BBQ [12].

The results can be shown in figure 1. We can see that, our algorithm works in better and improved performance on both types of networks than Dijkstra and GA. And more efficiency than BBQ when the number of edge become a larger one both in the sparse and dense network. As the network size increases,time-savings in performance will more, and this phenomenon is more remarkable in the sparse networks, since the sparse network will be reduced into a smaller one by ignoring irrelative links.

V. CONCLUSION

Motivated by the efficient requirement of centralized path calculation based on the largely global network topology in the SDN-enabled network, this paper improves the performance of finding shortest path by using a form of graph representation, path compression. First,we design our routing algorithm based on the reduced graph. Second, we reconstruct the reduce graph in the Ryu’s network view, and implement our routing algorithm as a routing app. Finally, the experiments provide evidence that the proposed approach outperforms the given typical algorithms as the the network size increase both on the sparse and dense networks. The future works is as follows. First we will try to other typical path compressions,and evaluate it using real network topology.Then we will deploy our approach into our software-de fined campus network.

Fig. 1. Performance of proposed algorithm.

ACKNOWLEDGMENTS

This work is supported by the National Natural Science Foundation of China (No.61521003).

[1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C.Stein, “Dijkstra’s Algorithm. Introduction to Algorithms”, (Second ed.). Section 24.3: pp. 595–601. MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

[2] F. Khamayseh and N. Arman, “An Efficient Multiple Source Single Destination (MSSD) Heuristic Algorithm Using Nodes Exclusions”,International Journal of Soft Computing, Vol. 10, 2015.

[3] H.N. Djidjev, G.E. Pantziou, and C.D. Zaroliagis,“Improved Algorithms for Dynamic Shortest Paths”,Algorithmica,vol. 28, 2000, pp. 367–389.

[4] N. Arman, “Parallel Algorithms for the Generalized Same Generation Query in Deductive Databases”,Journal of Digital Information Management, vol. 4, no. 3, 2006, pp. 192-196.

[5] W. Yahya1, A. Basuki2, J. Jiang, “The Extended Dijkstra’s-based Load Balancing for Open Flow Network”,International Journal of Electrical and Computer Engineering, vol. 5, no. 2, 2015, pp.289-296.

[6] J. Zhang, J. Li, X. Fan, Z. Deng, “Research on Real-Time Optimal Path Algorithm of Urban Transport”,TELKOMNIKA Indonesian Journal of Electrical Engineering, vol. 12, no. 5, 2014, pp.3515-3520.

[7] Y. Huang, Q. Yi, and M. Shi, “An Improved Dijkstra Shortest Path Algorithm”.Proc.The 2nd International Conference on Computer Science and Electronics Engineering, 2013, pp. 226-229.

[8] DA Lau Gastelo. Design & Implementation of a Genetic Algorithm for scalable shortest path routing in SDN controllers.University of Pisa,2015, pp. 22-41.

[9] A Shahid ， J Fiaidhi ， S Mohammed, “Implementing Innovative Routing Using Software Defined Networking (SDN)”,International Journal of Multimedia and Ubiquitous Engineering, vol.11, no. 2, 2016, pp. 159-172.

[10] V Muthumanikandan， C Valliyammai, “Link Failure Recovery Using Shortest Path Fast Rerouting Technique in SDN.”Wireless Personal Communications, vol. 9, 2017, pp. 1-21.

[11] JR Jiang， HW Huang， JH Liao， SY Chen,“Extending Dijkstra’s shortest path algorithm for software defined networking”,Proc.Network Operations & Management Symposium, 2014,pp. 1-4.

[12] Q Xu， X Zhang， J Zhao， X Wang, “Fast shortest-path queries on large-scale graphs”,Proc. IEEE International Conference on Network Protocols, 2016, pp. 1-10.

[13] The Mininet. http://mininet.org/

[14] The Ryu Controller. http://osrg.github.io/ryu/