A Fast Heuristic Path Computation Algorithm for the Batch Bandwidth Constrained Routing Problem in SDN

Autor:	Ke Tang, Peng Yang, Dongjun Qian
Rok vydání:	2018
Předmět:	Computer science Bidirectional search Computation Solution set Graph partition Graph (abstract data type) Software-defined networking Algorithm Constrained Shortest Path First Running time
Zdroj:	Lecture Notes in Computer Science ISBN: 9783319973036 PRICAI (1)
DOI:	10.1007/978-3-319-97304-3_38
Popis:	This paper presents a new path computation algorithm for the batch bandwidth constrained routing problem, aiming to reduce the end-to-end running time of a routing algorithm while maintaining the quality of the solution set. The batch bandwidth constrained routing problem arises along with the emergence of the Software Defined Networking (SDN) framework. A network is a bidirectional graph and most bandwidth constrained routing algorithms use Constrained Shortest Path First (CSPF) algorithm to compute a path meeting a certain bandwidth demand. However, available CSPF algorithms’ time complexities have a super-linear relation with the graph size. In fact, we think the entire graph is unnecessary for bandwidth constrained routing algorithms in that a comparatively small subgraph can be enough to cover a feasible path. Based on this thought, we present an algorithm to figure out different subgraphs for different requests of a batch with the help of a graph partitioning process in advance. We achieve an end-to-end time saving of up to a proportion of 69% in our experiments.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::46e1dd139c77344638c4e69d8f1c368b https://doi.org/10.1007/978-3-319-97304-3_38 Zobrazit plný text záznamu