Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection

Dada la estructura de una red y un conjunto de demandas, el routing and spectrum assignment (RSA) problem consiste en establecer los lightpaths para un conjunto de demandas de tráfico, cada una de las cuales está expresada en términos de un nodo de origen, un nodo de destino y una cantidad de slots....

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, Flavia, Lebon, Juan Pablo, Marenco, Javier
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2023
Materias:
Ciencias Informáticas
RSA
programación lineal entera
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/166457
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-166457
record_format dspace
spelling I19-R120-10915-1664572024-05-28T20:10:01Z http://sedici.unlp.edu.ar/handle/10915/166457 Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection Integer programming formulations for the survivable routing and spectrum assignment problem with path protection Bonomo, Flavia Lebon, Juan Pablo Marenco, Javier 2023-09 2023 2024-05-28T13:13:30Z es Ciencias Informáticas RSA programación lineal entera Dada la estructura de una red y un conjunto de demandas, el routing and spectrum assignment (RSA) problem consiste en establecer los lightpaths para un conjunto de demandas de tráfico, cada una de las cuales está expresada en términos de un nodo de origen, un nodo de destino y una cantidad de slots. Dado que cada lightpath está determinado por una ruta y un canal, el RSA consiste en encontrar una ruta y asignar un intervalo de slots para cada demanda. Para operar adecuadamente la red, se deben tener en cuenta las siguientes restricciones: 1. continuidad: los slots utilizados deben ser los mismos en todos los enlaces de cada ruta; 2. contiguidad: los slots asignados a una demanda deben ser contiguos; 3. no-solapamiento: en cada enlace, cada slot debe ser asignado a lo sumo a una demanda. El survivable RSA with path protection es una variante de RSA, que corresponde a solicitar dos lightpaths para cada demanda: un camino titular y un camino de backup (con una fracción de los slots demandados originalmente), que respeten las restricciones de RSA y que usen el mismo conjunto de slots. Este problema es NP-hard y ha recibido atención por parte de la comunidad especializada en los últimos años. En este trabajo se proponen distintos modelos de programación lineal entera para este problema, y se estudia su performance en la práctica sobre topologías reales. Se presentan además familias de desigualdades válidas para una de estas formulaciones, y se estudia su impacto en la resolución computacional de esta formulación. Sociedad Argentina de Informática e Investigación Operativa Objeto de conferencia Resumen http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf 165-165
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
RSA
programación lineal entera
spellingShingle Ciencias Informáticas
RSA
programación lineal entera
Bonomo, Flavia
Lebon, Juan Pablo
Marenco, Javier
Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection
topic_facet Ciencias Informáticas
RSA
programación lineal entera
description Dada la estructura de una red y un conjunto de demandas, el routing and spectrum assignment (RSA) problem consiste en establecer los lightpaths para un conjunto de demandas de tráfico, cada una de las cuales está expresada en términos de un nodo de origen, un nodo de destino y una cantidad de slots. Dado que cada lightpath está determinado por una ruta y un canal, el RSA consiste en encontrar una ruta y asignar un intervalo de slots para cada demanda. Para operar adecuadamente la red, se deben tener en cuenta las siguientes restricciones: 1. continuidad: los slots utilizados deben ser los mismos en todos los enlaces de cada ruta; 2. contiguidad: los slots asignados a una demanda deben ser contiguos; 3. no-solapamiento: en cada enlace, cada slot debe ser asignado a lo sumo a una demanda. El survivable RSA with path protection es una variante de RSA, que corresponde a solicitar dos lightpaths para cada demanda: un camino titular y un camino de backup (con una fracción de los slots demandados originalmente), que respeten las restricciones de RSA y que usen el mismo conjunto de slots. Este problema es NP-hard y ha recibido atención por parte de la comunidad especializada en los últimos años. En este trabajo se proponen distintos modelos de programación lineal entera para este problema, y se estudia su performance en la práctica sobre topologías reales. Se presentan además familias de desigualdades válidas para una de estas formulaciones, y se estudia su impacto en la resolución computacional de esta formulación.
format Objeto de conferencia
Resumen
author Bonomo, Flavia
Lebon, Juan Pablo
Marenco, Javier
author_facet Bonomo, Flavia
Lebon, Juan Pablo
Marenco, Javier
author_sort Bonomo, Flavia
title Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection
title_short Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection
title_full Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection
title_fullStr Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection
title_full_unstemmed Modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection
title_sort modelos de programación lineal entera para el survivable routing and spectrum assignment problem with path protection
publishDate 2023
url http://sedici.unlp.edu.ar/handle/10915/166457
work_keys_str_mv AT bonomoflavia modelosdeprogramacionlinealenteraparaelsurvivableroutingandspectrumassignmentproblemwithpathprotection
AT lebonjuanpablo modelosdeprogramacionlinealenteraparaelsurvivableroutingandspectrumassignmentproblemwithpathprotection
AT marencojavier modelosdeprogramacionlinealenteraparaelsurvivableroutingandspectrumassignmentproblemwithpathprotection
AT bonomoflavia integerprogrammingformulationsforthesurvivableroutingandspectrumassignmentproblemwithpathprotection
AT lebonjuanpablo integerprogrammingformulationsforthesurvivableroutingandspectrumassignmentproblemwithpathprotection
AT marencojavier integerprogrammingformulationsforthesurvivableroutingandspectrumassignmentproblemwithpathprotection
_version_ 1807223039980470272

Ejemplares similares