TY - GEN
T1 - It's Good to Relax
T2 - 20th Annual IFIP Networking Conference, IFIP Networking 2021
AU - Munk, Robin
AU - Rost, Matthias
AU - Racke, Harald
AU - Schmid, Stefan
N1 - Publisher Copyright:
© 2021 IFIP.
PY - 2021/6/21
Y1 - 2021/6/21
N2 - This paper proposes a new approximation algorithm for the offline Virtual Network Embedding Problem (VNEP) with latency constraints. Our approximation algorithm Flex allows for (slight) violations of the latency constraints in order to greatly lower the runtime. It relies on a reduction to the Restricted Shortest Path Problem (RSP) and leverages a classic result by Goel et al. We complement our formal analysis with a simulation study demonstrating our algorithm's computational benefits. Our results generalize to any other additive edge metric, as e.g., hop count or even packet loss probability.
AB - This paper proposes a new approximation algorithm for the offline Virtual Network Embedding Problem (VNEP) with latency constraints. Our approximation algorithm Flex allows for (slight) violations of the latency constraints in order to greatly lower the runtime. It relies on a reduction to the Restricted Shortest Path Problem (RSP) and leverages a classic result by Goel et al. We complement our formal analysis with a simulation study demonstrating our algorithm's computational benefits. Our results generalize to any other additive edge metric, as e.g., hop count or even packet loss probability.
UR - http://www.scopus.com/inward/record.url?scp=85112798816&partnerID=8YFLogxK
U2 - 10.23919/IFIPNetworking52078.2021.9472197
DO - 10.23919/IFIPNetworking52078.2021.9472197
M3 - Conference contribution
AN - SCOPUS:85112798816
T3 - 2021 IFIP Networking Conference, IFIP Networking 2021
BT - 2021 IFIP Networking Conference, IFIP Networking 2021
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 21 June 2021 through 24 June 2021
ER -