It's Good to Relax: Fast Profit Approximation for Virtual Networks with Latency Constraints

Robin Munk, Matthias Rost, Harald Racke, Stefan Schmid

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2021 IFIP Networking Conference, IFIP Networking 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9783903176393
DOIs
StatePublished - 21 Jun 2021
Event20th Annual IFIP Networking Conference, IFIP Networking 2021 - Virtual, Espoo, Finland
Duration: 21 Jun 202124 Jun 2021

Publication series

Name2021 IFIP Networking Conference, IFIP Networking 2021

Conference

Conference20th Annual IFIP Networking Conference, IFIP Networking 2021
Country/TerritoryFinland
CityVirtual, Espoo
Period21/06/2124/06/21

Fingerprint

Dive into the research topics of 'It's Good to Relax: Fast Profit Approximation for Virtual Networks with Latency Constraints'. Together they form a unique fingerprint.

Cite this