Virtual Network Embedding as Boolean Satisfiability

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00381975" target="_blank" >RIV/68407700:21240/24:00381975 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/ICTAI62512.2024.00063" target="_blank" >https://doi.org/10.1109/ICTAI62512.2024.00063</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/ICTAI62512.2024.00063" target="_blank" >10.1109/ICTAI62512.2024.00063</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Virtual Network Embedding as Boolean Satisfiability

Popis výsledku v původním jazyce

We address the Virtual Network Embedding (VNE) problem in which the task is to map a virtual network onto a given physical substrate network so that the CPU and bandwidth capacity constraints are met. Following the success of Boolean Satisfiability (SAT) methods in areas such as Multi-Agent Path Finding (MAPF), we propose in this paper a novel SAT-based approach for solving the VNE problem. As in MAPF, the various constraints that define the VNE problem are encoded into the SAT models incrementally and via lazy refinements so as to keep the models simple. We also propose various model relaxations and concomitant solution extraction post-processing procedures. Through experiments, we show that our SAT-based approach outperforms other state-of-the-art approaches on a number of VNE instances.

Název v anglickém jazyce

Virtual Network Embedding as Boolean Satisfiability

Popis výsledku anglicky

We address the Virtual Network Embedding (VNE) problem in which the task is to map a virtual network onto a given physical substrate network so that the CPU and bandwidth capacity constraints are met. Following the success of Boolean Satisfiability (SAT) methods in areas such as Multi-Agent Path Finding (MAPF), we propose in this paper a novel SAT-based approach for solving the VNE problem. As in MAPF, the various constraints that define the VNE problem are encoded into the SAT models incrementally and via lazy refinements so as to keep the models simple. We also propose various model relaxations and concomitant solution extraction post-processing procedures. Through experiments, we show that our SAT-based approach outperforms other state-of-the-art approaches on a number of VNE instances.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-31346S" target="_blank" >GA22-31346S: logicMOVE: Logické uvažování v plánování pohybu pro mnoho robotických agentů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 2024 IEEE 36th International Conference on Tools with Artificial Intelligence (ICTAI)

ISBN

979-8-3315-2724-2

ISSN

1082-3409

e-ISSN

2375-0197

Počet stran výsledku

9

Strana od-do

387-395

Název nakladatele

IEEE Computer Society

Místo vydání

Los Alamitos

Místo konání akce

Washington, DC

Datum konání akce

28. 10. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—