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

Robin Munk, Matthias Rost, Harald Racke, Stefan Schmid

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

2 Zitate (Scopus)

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.

OriginalspracheEnglisch
Titel2021 IFIP Networking Conference, IFIP Networking 2021
Herausgeber (Verlag)Institute of Electrical and Electronics Engineers Inc.
ISBN (elektronisch)9783903176393
DOIs
PublikationsstatusVeröffentlicht - 21 Juni 2021
Veranstaltung20th Annual IFIP Networking Conference, IFIP Networking 2021 - Virtual, Espoo, Finnland
Dauer: 21 Juni 202124 Juni 2021

Publikationsreihe

Name2021 IFIP Networking Conference, IFIP Networking 2021

Konferenz

Konferenz20th Annual IFIP Networking Conference, IFIP Networking 2021
Land/GebietFinnland
OrtVirtual, Espoo
Zeitraum21/06/2124/06/21

Fingerprint

Untersuchen Sie die Forschungsthemen von „It's Good to Relax: Fast Profit Approximation for Virtual Networks with Latency Constraints“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren