LARAC-SN and Mole in the Hole: Enabling Routing through Service Function Chains
Van Bemten A, Guck JW, Vizarreta P, Machuca CM, Kellerer W (2018)
Publication Type: Conference contribution
Publication year: 2018
Publisher: Institute of Electrical and Electronics Engineers Inc.
Pages Range: 168-176
Conference Proceedings Title: 2018 4th IEEE Conference on Network Softwarization and Workshops, NetSoft 2018
Event location: Montreal, QC, CAN
ISBN: 9781538646335
DOI: 10.1109/NETSOFT.2018.8460128
Abstract
With the emergence of Software-Defined Networking (SDN) and Network Function Virtualization (NFV), the problem of centralized routing through intermediate specified nodes (for which several candidates can be defined) has become an important issue. Indeed, an SDN controller routing flows through Service Function Chains (SFCs) has to efficiently solve this problem to achieve the online provisioning of routing requests and the online placement of Virtual Network Functions (VNFs). In this paper, we propose two algorithms for solving this problem. First, we propose LARAC for specified nodes (LARAC-SN), a fast and close to optimal algorithm for finding the constrained shortest path (CSP) visiting an ordered set of specified nodes. Second, we propose Mole in the Hole (MITH), a graph transformation algorithm which can force any state-of-the-art routing algorithm to visit an ordered set of specified nodes. While LARAC-SN is bounded to the specific CSP problem and can only handle one candidate per specified node, MITH can be used for any routing problem and can deal with several candidates per specified node. Through evaluations, we show that LARAC-SN is fast and close to optimal (its optimality gap stays lower than 1.62% in average) and that MITH has the potential of reaching optimality for any problem, but at the cost of a higher runtime.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Van Bemten, A., Guck, J.W., Vizarreta, P., Machuca, C.M., & Kellerer, W. (2018). LARAC-SN and Mole in the Hole: Enabling Routing through Service Function Chains. In 2018 4th IEEE Conference on Network Softwarization and Workshops, NetSoft 2018 (pp. 168-176). Montreal, QC, CAN: Institute of Electrical and Electronics Engineers Inc..
MLA:
Van Bemten, Amaury, et al. "LARAC-SN and Mole in the Hole: Enabling Routing through Service Function Chains." Proceedings of the 4th IEEE Conference on Network Softwarization and Workshops, NetSoft 2018, Montreal, QC, CAN Institute of Electrical and Electronics Engineers Inc., 2018. 168-176.
BibTeX: Download