Aproximación al modelamiento del enrutamiento en redes ...repository.udistrital.edu.co/bitstream/11349/5649/1/ARIZA DANILO... · El método simplex ... Programación en Java

Maestría en Ciencias de la Información y las Comunicaciones

1

Aproximación al modelamiento del enrutamiento en redes GMPLS con fines de optimización de

recursos

Danilo de Jesús Ariza Agámez

Universidad Distrital Francisco José de Caldas

Facultad de Ingeniería

Bogotá D.C., Colombia

Diciembre de 2015


2

Aproximación al modelamiento del enrutamiento

en redes GMPLS con fines de optimización de recursos

Danilo de Jesús Ariza Agámez

Trabajo presentado como requisito parcial para optar al título de:

Magister en ciencias de la información y las telecomunicaciones

Director:

Ph.D. Octavio José Salcedo Parra

Línea de Investigación: Investigación de operaciones,

enrutamiento

Universidad Distrital Francisco José de Caldas

Facultad de Ingeniería

Bogotá D.C., Colombia

Diciembre de 2015


3

Nota de aceptación

______________________________ ______________________________ ______________________________ ______________________________ ______________________________

__________________________________________ Firma del presidente del jurado

__________________________________________

Firma del jurado

__________________________________________ Firma del jurado

Bogotá D.C., diciembre de 2015

_


4


5

Dedicatorias

A Danilo Alejandro y Sebastián David, mis

grandes, amados, juiciosos y muy

inteligentes hijos. Dos enormes regalos del

creador.

A mi madre Lesbia Lidis y su gran amor y

devoción.

A Andrea y Olinda, otras dos madres que

me regaló la vida.

A mi adorada Brigitte, hermoso ser que me

enseñó a sentirme realmente amado.

A Laura Marcela, de quien espero siempre

tanto aprecio como el que siento por ella.

A Dalton y Whisky, hermosos ejemplares

de otras especies que siempre dispuestos

a dar y recibir amor.

A Ana Vicenta, Juan Bautista, Luis

Alfonso, León Santiago y Doyler

Medelson: seres queridos que se

encuentran en la gloria de Dios.


6

Agradecimientos

Expreso mis sinceros y profundos agradecimientos a la Facultad de ingeniería de

la Universidad Distrital Francisco José de Calda, a cada uno de los docentes del

programa de maestría en Ciencias de la Información y las Comunicaciones que

contribuyeron con esta etapa en mi proceso de formación.

Agradecimientos especiales al Maestro Octavio José Salcedo Parra, por sus

aportes, consejos y orientaciones en el desarrollo. Mil gracias Maestro.

.


7

Tabla de contenidos

PARTE I: CONTEXTUALIZACIÓN ............................................................................................... 10

Capítulo 1. Contextualización ................................................................................................. 11 1.1. Resumen ................................................................................................................................. 11 1.2. Abstract .................................................................................................................................. 12 1.3. Introducción ........................................................................................................................... 13 1.4. Formulación del problema ..................................................................................................... 14 1.5. Objetivos ................................................................................................................................ 15

1.5.1. Objetivo general ..............................................................................................................15 1.5.2. Objetivos específicos .......................................................................................................15

1.6. Justificación ............................................................................................................................ 16 1.7. Resultados esperados ............................................................................................................ 17

PARTE II: MARCO TEÓRICO ..................................................................................................... 19

Capítulo 2. Fundamentos de redes de transporte .................................................................... 20 2.1. Arquitectura genérica de las redes de trasporte ................................................................... 21 2.2. Redes ópticas y mecanismos de multiplexación .................................................................... 21

2.2.1. Multiplexación por División de Tiempo (TDM). ..............................................................22 2.2.2. Multiplexación por División de Longitud de Onda. .........................................................22 2.2.3. Conmutación de Fibra: ....................................................................................................23

2.3. Evolución de las redes ópticas ............................................................................................... 23 2.3.1. Redes ópticas de primera generación. ............................................................................24 2.3.2. Redes ópticas de segunda generación ............................................................................24 2.3.3. Redes ópticas de tercera generación. .............................................................................26

Capítulo 3. Fundamentos de MPLS y GMPLS ........................................................................... 28 3.1. Conmutación de paquetes y conmutación de etiquetas ....................................................... 28 3.2. Conmutación de etiquetas: paradigma de la tecnología MPLS ............................................. 29 3.3.1. LSR y LSP .............................................................................................................................. 30

3.3.2. Clases de Equivalencia de Reenvío (FEC) ........................................................................31 3.3.3. Apilamiento de etiquetas o túneles MPLS ......................................................................31

3.4. Noción básica de señalización ................................................................................................ 32 3.5. El paso a GMPLS ..................................................................................................................... 32 3.6. Génesis de GMPLS .................................................................................................................. 33 3.7. Requerimientos y restricciones asociadas a GMPLS .............................................................. 33

3.7.1. Limitaciones de la generalización de etiquetas: .............................................................33 3.7.2. Tipos de conmutación en Nodos de redes de transporte: ..............................................33 3.7.3. LSP en GMPLS: .................................................................................................................34 3.7.4. Granularidad del Ancho de banda: .................................................................................34 3.7.5. Bidireccionalidad de conexiones en GMPLS ...................................................................34 3.7.6. Planos de control y de datos separados .........................................................................35 3.7.7. Túneles y jerarquías en GMPLS .......................................................................................35

3.8. Señalización en GMPLS .......................................................................................................... 35 3.9. Mejoras de RSVP-TE para GMPLS........................................................................................... 36


8

3.9.1. Señalización de LSP jerárquicos ......................................................................................36 3.9.2. Mejoramiento de etiquetas ............................................................................................38

3.10. Enrutamiento ....................................................................................................................... 39 3.10.1. Enrutamiento IP e Ingeniería de Tráfico .......................................................................39

3.11. Enrutamiento en GMPLS ...................................................................................................... 39 3.11.1. Información de Enrutamiento requerida en redes GMPLS ...........................................40 3.11.2. Protocolos de Enrutamiento en GMPLS ........................................................................40

3.12. Ingeniería de Tráfico GMPLS ................................................................................................ 40 3.12.1. Atributos de enlaces de TE ............................................................................................41

3.13. Protocolos de soporte de Ingeniería de Tráfico GMPLS ...................................................... 41 3.13.1. OSPF-TE e IS-IS-TE .........................................................................................................42 3.13.2. Construcción de enlaces de Ingeniería de Tráfico ........................................................42 3.13.3. Regiones de Ingeniería de Tráfico y capas de conmutación .........................................42 3.13.4Topología virtual de red ..................................................................................................44 3.13.5. Protección H-LSP ...........................................................................................................45 3.13.6. Capacidades de adaptación ..........................................................................................46

3.14. PCE: Path Computation element .......................................................................................... 47 3.14.1. Arquitectura del modelo PCE ........................................................................................48

Capítulo 4. Contexto general del problema de cálculo de rutas ............................................... 51 4.1. Aspectos básicos de complejidad ........................................................................................... 51

4.1.2. Clases de Complejidad ....................................................................................................52 4.2. Representación de redes para cálculo de rutas ..................................................................... 53 4.3. Algoritmos de cálculo de la ruta más corta ............................................................................ 54

4.3.1. Algoritmo de Dijkstra ......................................................................................................55 4.3.2. Algoritmo de Bellman-Ford .............................................................................................56 4.3.3. Algoritmo de Johnson .....................................................................................................57

4.4. Extensión de algoritmos básicos para hallar múltiples rutas más cortas. ............................ 58 4.4.1. Algoritmo KSP ..................................................................................................................59

4.5 Restricciones de cálculo de rutas en GMPLS ........................................................................... 60 4.5.1. Restricciones asociadas con atributos de enlace y de ruta .............................................61 4.5.2. Restricciones asociadas con exclusión e inclusión ..........................................................62

Capítulo 5: Cálculo de rutas más cortas en ámbitos restringidos (CSPP) ................................... 62 5.1. Estado del arte del CSPP......................................................................................................... 63

PARTE III: PLANTEAMIENTO DE MODELOS .............................................................................. 67

Capítulo 6. Bases matemáticas asociadas con la solución del CSPP .......................................... 68 6.1 Elementos básicos de programación lineal ............................................................................. 68

6.1.2. Modelo de problemas de programación lineal ...............................................................68 6.1.4. Solución de problemas de programación lineal ..............................................................69 6.1.5. Solución de problemas de programación lineal. El método simplex ..............................70 6.1.6. Problema dual de un problema de programación lineal ................................................71

6.2. Elementos básicos de programación lineal entera ................................................................ 71 6.2.1. Relajación Lagrangiana ....................................................................................................72 6.2.2 Límite inferior de la función objetivo ...............................................................................73 6.2.3. Teorema de relajación Lagrangiana ................................................................................74 6.2.4. Algoritmo de optimización subgradiente ........................................................................75


9

Capítulo 7. Modelos formales de solución .............................................................................. 77 7.1. Modelamiento del problema usando programación lineal entera ........................................ 78 7.2. Algoritmo para hallar rutas factibles ...................................................................................... 80

7.2.1. Procedimiento FPDT de afinamiento para el problema JFP............................................81 7.2.2. Procedimiento de enumeración para el problema ......................................84

7.3. Algoritmo para el problema JMCSP ....................................................................................... 86 7.3.1. Procedimiento de afinamiento para JMCSP .............................................87 7.3.2. Procedimiento MCSPPE de enumeración para el problema JMCSP ...............................91

7.4 Algoritmo CSP con una restricción .......................................................................................... 93

Capítulo 8: Diseño e implementación ..................................................................................... 95 8.1. Ajuste de Pseudocódigos de algoritmos de solución ............................................................. 95

8.1.1. Pseudocódigo para hallar 3 rutas factibles .....................................................................96 8.1.2. Pseudocódigo del algoritmo para el problema 3MCSP ....................................................... 98 8.2 Flujo lógico del sistema ......................................................................................................... 100 8.3. Opciones de herramienta de simulación ............................................................................. 101

8.3.1. OPNET ............................................................................................................................102 8.3.2. NS-2 ...............................................................................................................................102 8.3.3. Programación en Java. ..................................................................................................102

8.4. Selección de herramienta .................................................................................................... 103

Capítulo 9: Evaluación de resultados, trabajos futuros y conclusiones. ................................... 105 9.1. Pruebas del algoritmo KSP ................................................................................................... 105 9.2 pruebas del algoritmo para manejo de restricciones ........................................................... 107 9.3 Trabajos futuros .................................................................................................................... 114 9.4. Conclusiones......................................................................................................................... 114

Referencias ........................................................................................................................... 118

PARTE IV: ANEXOS ................................................................................................................ 121

Codificación de clases para el algoritmo KSP .......................................................................... 122

Codificación del algoritmo CSP .............................................................................................. 143


10

PARTE I: CONTEXTUALIZACIÓN


11

Capítulo 1. Contextualización

1.1. Resumen

En el presente trabajo inicialmente se revisa conceptos fundamentales de redes

basadas en la tecnología GMPLS, enfatizando en el enrutamiento, que es el

intercambio de información requerida antes de realizar el cálculo de rutas. Se toma

en cuenta que las comunicaciones a través de la Internet, soportada por los

Proveedores de Servicios de Internet (ISP), cada día muestran mayores

requerimientos, obligando cada vez más a los ISP a hacer uso eficiente de sus

recursos al tiempo que satisfagan las necesidades de sus abonados. GMPLS, es

quizá la tecnología más llamada a contribuir con tales propósitos en razón a la

separación de los planos de control y de datos y al diseño de protocolos

orientados a la apropiada administración de recursos, sin embargo, las

complejidades subyacentes a las comunicaciones hacen del cálculo de rutas una

tarea también compleja debido a las variadas restricciones impuestas por las

comunicaciones. El cálculo restringido de rutas ha dado lugar a profundas

investigaciones sobre optimización, con el fin de lograr eficientes algoritmos. Para

la realización de este trabajo se ha dirigido la mirada al tratamiento matemático del

problema de cálculo de múltiples mejores rutas sujeto a múltiples restricciones, se

propone el uso de un conjunto de bloques algorítmicos y se destaca en ellos la

importancia del algoritmo KSP que calcula las K mejores rutas en un grafo. Se

presenta elementos del discurso matemático que de los algoritmos adoptados, se

realiza implementaciones de los mismos y pruebas que avalan su funcionamiento.

Palabras clave: GMPLS, Enrutamiento, optimización, Dijkstra, programación lineal


12

1.2. Abstract

In this work basic concepts of GMPLS-based technology, with emphasis on routing, which is the exchange of information required before performing route calculation networks is reviewed. It takes into account that communications via the Internet, supported by the Internet Service Providers (ISP), daily show higher requirements, forcing the ISP to make efficient use of their resources while meeting the needs of their subscribers. GMPLS, is perhaps the most called to contribute for such purposes due to the separation of control plane and data and design appropriately oriented resource management protocols, however, the underlying communications complexities make the calculation Route an equally complex task due to various constraints imposed by these communications. Calculating restricted routes has led to extensive research on optimization, in order to achieve efficient algorithms. To carry out this work has been directed to look mathematical treatment of the problem of calculation of multiple best paths subject to multiple restrictions, the use of a set of algorithmic blocks is proposed and excels in them the importance of calculating the best K routes (KSP) from a graph. Speech elements mathematical algorithms adopted, implementations thereof is performed and evidence supporting operation performed occurs. Keywords: GMPLS, routing, optimization, Dijkstra, linear programming.


13

1.3. Introducción

Las modernas redes de comunicación han transformado notablemente las formas

en que hoy desarrollamos nuestras diferentes actividades. Estamos altamente

influenciados por el uso de la Internet y cada día parece que la necesidad de su

uso es más creciente. En un mundo empresarial, en el que los ISP, buscan

mantenerse competitivos frente a las exigencias de sus abonados, existe la

necesidad de contar con infraestructuras soportadas por sólidas configuraciones

que den lugar al eficiente uso de los recursos sin que ello vaya en detrimento de

los intereses de los clientes. Para las modernas redes, una arquitectura soportada

en la tecnología GMPLS ayuda en el logro de sus propósitos, sin embargo

requiere de sólidas técnicas de enrutamiento frente a las crecientes exigencia de

los usuarios de hoy.

El presente trabajo aborda el problema del enrutamiento, en el cual no solo se

requiere calcular las mejores rutas, sino que estas deben satisfacer un conjunto de

restricciones asociadas con las métricas de la red. El trabajo está organizado de la

siguiente manera: una primera parte de contextualización dedicada precisamente

a indicar al lector las generalidades del resto del trabajo, contiene un capítulo que

incluye un breve resumen, formulación del problema, justificación, objetivos y

resultados espera obtener.

En la parte 2, correspondiente a marco teórico, se presenta un segundo capítulo

en que se aborda elementos fundamentales de redes de transporte, mecanismos

de multiplexación y la evolución de las redes ópticas. El capítulo 3 inicia con una

breve descripción de la conmutación de paquetes IP para luego describir la

conmutación de etiquetas, que es el paradigma fundamental de la tecnología

MPLS. Continúa el capítulo introduciendo otros conceptos básicos de MPLS para

luego pasar a la descripción de la generalización que da lugar a GMPLS, se

aborda de manera breve los aspectos que tienen que ver con la señalización, el

enrutamiento y los protocolas que les dan soporte. El capítulo continúa el

tratamiento de las restricciones propias del ámbito GMPLS. El capítulo 4 aborda el

problema de cálculo de ruta y los diferentes algoritmos de solución, ya que ellos

son la base de desarrollo de posteriores capítulos. Esta segunda parte finaliza con

el capítulo 5, donde se aborda específicamente el cálculo de rutas en ambientes

restringidos.


14

En la tercera parte, el capítulo 6 se dedica a una breve descripción de principios

matemáticos fundamentales que contribuyen con la solución del problema. El

capítulo 7 aborda los modelos y procedimientos formales adoptados, en el

capítulo 8 se presenta un diseño básico, la implementación mientras que en el

capítulo 9 se presenta la evaluación de resultados, posibles trabajos futuros y

conclusiones y las conclusiones. Luego de las conclusiones se presenta como

cuarta parte el código de las clases implementadas a manera de Anexos.

1.4. Formulación del problema

La Internet aprovecha los avances de las transmisiones ópticas que permiten

muchísimas comunicaciones simultáneas a través de un mismo cable [1], sin

embargo, al tiempo que avanzan las posibilidades tecnológicas en materia de

telecomunicación, también crece la demanda que presenta mayores exigencias a

la infraestructura de los Proveedores de Servicios de Internet (ISPs) [1]. Los

usuarios esperan siempre muy alta calidad de los servicios que contratan, pero por

un lado los ISP necesitan mantenerse competitivos y por otro, los elementos de la

infraestructura asociados a los recursos no están exentos de daños, fallas o

sobrecargas, siendo esto un factor llamado a generar dificultad en cuanto a la

garantía de los servicios en las condiciones esperadas.

El plano de control de GMPLS es responsable de la señalización y enrutamiento

que permiten la aplicación de ingeniería de tráfico, soporte del aprovisionamiento

de calidad de servicio (QoS). La finalidad de la ingeniería de tráfico (TE) es

optimizar el rendimiento de los recursos de red, redirigiendo el tráfico, sobre

recursos recargados, hacia otros posiblemente subutilizados. En el contexto del

enrutamiento GMPLS, la TE es aplicada, por ejemplo, mediante el balanceo de

cargas, que distribuye el flujo de red a través de múltiples rutas precalculadas,

entre los nodos origen y destino, de tal manera que se evite saturación de enlaces

y los efectos asociados.

Comúnmente los diferentes servicios presentan diferentes requisitos de QoS

relacionados, por ejemplo, con parámetros de ancho de banda, retardo, pérdida de

paquetes, costos, entre otros. A lo anterior se une el hecho que la transmisión a


15

través de redes ópticas de transporte de nueva generación hace necesario tomar

en consideración factores adicionales como el jitter o variación del retardo, la

probabilidad de bloqueo, la redundancia y la tolerancia a fallas, entre otros. Frente

a la necesidad de optimización de recursos y el alcance de diferentes objetivos

frecuentemente en conflicto, es deseable que la optimización del enrutamiento

GMPLS pueda expresarse matemáticamente considerando apropiadas métricas

asociadas a las nuevas exigencias impuestas por los servicios que prestan las

modernas redes de transporte. Frente a lo antes señalado vale la pena formular el

siguiente interrogante que orienta esta propuesta de investigación:

¿Están claramente definidos los referentes que, con fines de optimización de

recursos, caracterizan matemáticamente la funcionalidad de enrutamiento de las

redes GMPLS?

A través de esta propuesta se identifica, más que un problema, una oportunidad

de investigación en el hecho que el en contexto de las redes de transporte existe

la permanente necesidad de optimización de recursos. En este caso lo anterior

atañe a la necesidad de formulaciones que consideren restricciones y exigencias

asociadas a métricas de enrutamiento propias del contexto GMPLS y que

constituyan una aproximación a su descripción formal.

1.5. Objetivos

1.5.1. Objetivo general

Establecer un modelo que caracterice matemáticamente la función de

enrutamiento en redes GMPLS con fines de optimización de recursos.

1.5.2. Objetivos específicos

Establecer un estado del arte en el modelado de optimización del enrutamiento.

Establecer posibles formulaciones matemáticas de optimización del enrutamiento en redes GMPLS.


16

Simular las funcionalidades del enrutamiento en redes GMPLS a partir de

sus posibles formulaciones matemáticas.

Evaluar el comportamiento del enrutamiento en redes GMPLS frente a

manipulación de variables.

Establecer posibles criterios de optimización de recursos en redes GMPLS

con base en formulaciones matemáticas de la funcionalidad de

enrutamiento.

1.6. Justificación

Las redes de transporte, que soportan el cúmulo de servicios prestados a través

de la Internet, se han visto inmersas en procesos de evolución debidos en buena

medida al incremento de exigentes aplicaciones demandantes de altísimas tasas

de transferencia y capacidades de calidad de servicio. Al no resultar lo

necesariamente efectivo, el paradigma de conmutación de paquetes IP se

remplaza por el esquema MPLS, el que a su vez se generaliza para dar lugar a las

redes GMPLS. [1],[2]

Las modernas redes de transporte, basadas en buena medida en transmisión a

través de fibra óptica, requieren complejas funcionalidades de control debido a

múltiples exigencias y restricciones impuestas por los servicios que soportan. Los

actuales ISP, además de los requisitos de QoS que usualmente presentan las

aplicaciones (relacionados con ancho de banda, retardo, pérdida de paquetes),

deben considerar factores adicionales tales como el jitter o variación del retardo,

probabilidad de bloqueo, redundancia y tolerancia a fallas, elementos directamente

relacionados con múltiples objetivos que deben alcanzar en aras de mantenerse

competitivos, por tanto es pertinente abordar la optimización del enrutamiento de

tal manera que considere métricas asociadas a las nuevas complejidades.

Particularmente en la tecnología GMPLS, el plano de control coordina, entre otras,

la tarea de enrutamiento, para lo cual se vale de un conjunto de protocolos

específicos, ligados a principios de ingeniería de tráfico, que demandan la


17

aplicación de criterios de optimización de recursos, de tal manera que se pueda

prestar los servicios cumpliendo con parámetros de eficiencia. [1],[2].

Frente a la necesidad de aplicación de principios de ingeniería de tráfico

involucrados en el alcance de múltiples objetivos y teniendo en cuenta que, no

están totalmente definidos los referentes que, con fines de optimización de

recursos, caractericen matemáticamente la funcionalidad de enrutamiento de

redes GMPLS, resulta muy importante abordar este trabajo.

La utilidad de posibles formulaciones matemáticas que, dentro de ciertos límites,

se aproximen a una caracterización o modelo matemático de optimización que

considere los aspectos señalados en el párrafo anterior, y que permita establecer

criterios de eficiencia en el uso de los recursos de red, al tiempo que se alcance

los múltiples objetivos que comprometen a las redes de transporte, justifica

plenamente que se aborde el estudio aquí propuesto.

1.7. Resultados esperados

El desarrollo de la presente propuesta puede contribuir con el fortalecimiento de

elementos de análisis alrededor de la optimización de recursos en el contexto de

las redes de transporte, particularmente al interior del programa de Maestría en

Ciencias de la Información y las Telecomunicaciones de la Universidad Distrital

Francisco José de Caldas. Adicionalmente se considera que los estudios

realizados, y posibles resultados que de él se deriven, podrían ser de utilidad,

directa o indirectamente para:

Comunidad académica: la utilidad se vería representada en mayores referentes

conceptuales en relación con el tema de optimización de recursos en redes de

transporte y particularmente con los asociados a la funcionalidad de

enrutamiento en redes GMPLS.

Personal docente y directivo: les sería de utilidad en la medida que los

resultados del proyecto, o interrogantes y conclusiones que de él se deriven,


18

podrían constituir un punto de partida de futuras investigaciones relacionadas

con las temáticas abordadas en la propuesta.

Comunidad de Ingenieros: los resultados o conclusiones del estudio podrían

ser utilizados como fundamentos conceptuales que ayuden a sustentar criterios

técnicos en relación a la optimización de recursos en redes de transporte de

información.

Empresas proveedoras de servicios: Los resultados o conclusiones del

estudio podrían ser parte de los referentes conceptuales utilizados por empresas

Proveedoras de Servicios de Telecomunicaciones (TPS) y Proveedoras de

Servicios de Internet (ISP), toda vez que son estas organizaciones las que más

directamente se ven comprometidas en la administración de recursos en redes

de transporte.


19

PARTE II: MARCO TEÓRICO


20

Capítulo 2. Fundamentos de redes de transporte Se puede considerar una red de transporte como un conjunto de recursos de red

para transmitir datos de usuarios de redes en diferentes lugares. La Internet es

una compleja estructura de múltiples redes de trasporte propiedad de los ISP o

Proveedores de Servicios de Internet. Las redes de los ISP son heterogéneos

Sistemas Autónomos que cooperan entre ellos para formar la columna vertebral o

backbone de la Internet, y cuentan con una infraestructura de recursos para

prestar a sus abonados el acceso a la Internet y soportar los exigentes servicios a

los que acceden los usuarios [1]. La tecnología de interconexión al interior de las

redes de usuario es muy variada, lo que da lugar al uso de diferentes tecnologías

de conexión en las fronteras de las redes de usuario y la red de transporte. La

Figura 1 [1] ilustra la idea básica correspondiente al contexto de redes de

transporte.

Figura 2.1: Ilustración básica del funcionamiento de redes de transporte.


21

2.1. Arquitectura genérica de las redes de trasporte

Así como las arquitecturas de redes se representan mediante modelos de capas,

es útil ver una red de transporte desde la perspectiva de las funcionalidades de

sus nodos, lo que hace posible construir una descripción del modelo arquitectónico

al tiempo que facilita la comprensión de la misma. Una red de trasporte es vista

como una arquitectura formada por conjuntos de componentes con

funcionalidades relacionadas. A los conjuntos de funcionalidades se les conoce

con el nombre genérico de planos. De esta manera, un nodo con diferentes

componentes y funcionalidades está presente en la comunicación entre planos, es

decir, la comunicación entre planos se da en nodos individuales. Por otro lado, la

comunicación de componentes similares de nodos diferentes se da en un mismo

plano. Estas ideas se ilustran en la Figura 2.2, [1] donde la arquitectura de red se

compone de cuatro planos que son los planos de administración, señalización,

enrutamiento y de datos.

Figura 2. 2: Arquitectura de red compuesta por los planos de administración, señalización, enrutamiento y de datos.

2.2. Redes ópticas y mecanismos de multiplexación

A lo largo de la historia de la Internet, el medio de transmisión predominante en las

redes de ISP ha sido la fibra óptica. La transmisión por fibra óptica se ha valido de

técnicas de Multiplexación, como las que se describen brevemente a continuación.


22

2.2.1. Multiplexación por División de Tiempo (TDM).

El fundamento de TDM (Time Division Multiplexing) está en el hecho que el ancho

de banda de la señal portadora se comparte por múltiples flujos, asignándose a

cada flujo una ranura temporal de la señal. TDM típicamente maneja variadas

capacidades de transmisión, actuales investigaciones trabajan sobre lo que se

conoce como o Multiplexación por División de Tiempo Óptica u OTDM (Optical

Time Division Multiplexing). La Figura 2.3 [3] muestra una idea básica del

esquema de multiplexación TDM.

Figura 2. 3: Esquema de funcionamiento de la multiplexación TDM

2.2.2. Multiplexación por División de Longitud de Onda.

La técnica de Multiplexación por División de Longitud de Onda o WDM (Wavelegth

Division Multiplexing) coloca simultáneamente múltiples señales ópticas en la

misma fibra, cada señal se asocia con un canal de longitud de onda (lambda),

que transportan datos independientemente de los transportados por los otros

canales de la misma fibra. Es muy común que cada lamda en WDM transporte

flujos TDM.

WDM presenta las versiones CWDM (Coarse Wavelength Division Multiplexing) o

WDM gruesa, que multiplexa 18 canales con separaciones de 20nm entre canales;

y DWDM (Dense Wavelength Division Multiplexing) o WDM densa, que logra más


23

canales por fibra. DWDM cuenta con varias especificaciones caracterizadas por

menores separaciones, de 100, 50 o 25 Ghz. Existen dos tipos distintos de

switches WDM, que son Swithces OEO (Óptico-Electrónico-Óptico) y PXC o OOO

(Fotónico cross-connect o todo óptico). La Figura 2.4 [3] ilustra la idea del

esquema WDM.

Figura 2. 4: Esquema de funcionamiento de la multiplexación WDM

2.2.3. Conmutación de Fibra:

Un switch de fibra es un dispositivo que toma todos los datos de una fibra y los

replica a otra fibra, son usualmente dispositivos transparentes, lo que significa que

la señal entrante no se convierte al dominio eléctrico antes de ser transmitida.

2.3. Evolución de las redes ópticas

El enorme crecimiento en la demanda de ancho de banda, la creciente

complejidad de los servicios y aplicaciones que se dan sobre la Internet, hace que

la alta disponibilidad de capacidad de transmisión de la fibra óptica, no satisfaga

suficientemente las actuales necesidades de gestión de redes, esto plantea

exigencias que han motivado investigaciones y desarrollos en el campo óptico,


24

que han marcado etapas en su evolución, tal evolución permite clasificarlas redes

ópticas como redes de primera, segunda y tercera generación [4].

2.3.1. Redes ópticas de primera generación.

La impronta de las redes ópticas de primera generación es el uso de fibra óptica

como medio de transmisión, siendo la velocidad el elemento diferenciador frente a

redes basadas en otros medios. En estas redes, los nodos deben realizar tareas

de enrutamiento y conmutación, sobre los datos que usan el nodo como tránsito o

como destino, en el domino eléctrico, lo significa que las señales ópticas que

ingresan son convertidas al formato eléctrico y luego son convertidas al dominio

óptico para su reenvió [4]. Tomando en cuenta que las estadísticas de tráfico

señalan que en promedio aproximadamente el 85 % del tráfico usa los nodos

como tránsito, estas conversiones conllevan una ineficiente utilización de recursos,

lo que representa la más significativa limitación asociada a las redes ópticas de

primera generación.

2.3.2. Redes ópticas de segunda generación

Si a un nodo de una red de transporte se le releva de tareas de conversión al

dominio eléctrico, del tráfico dirigido a otros nodos, se lograría mayor eficiencia en

el uso de los recursos de red. Este es el paradigma de la segunda generación de

redes ópticas, con componentes capaces de colocar o extraer selectivamente

grupos de longitudes de onda, desde o hacia la fibra, esto se conoce como

enrutamiento y conmutación en el dominio óptico. Esta segunda generación está

marcada por la incorporación de la idea de capa óptica al modelo de transmisión.

La conmutación, enrutamiento y algunas tareas de control y gestión, pasan a

darse en el dominio óptico. A estas redes también se les llama redes de

enrutamiento de longitud de onda [4].


25

Figura 2. 5: Vista de red soportada en una capa óptica

Siguiendo la filosofía de los modelos en capas, la capa óptica presta servicios a la

capa de nivel superior, llamada capa cliente, en la que se encuentran tecnologías

como SONET/SDH, ATM, IP. El servicio consiste en el aprovisionamiento de las

rutas ópticas o lightpath para satisfacer requerimientos de conexión. Es posible el

uso de diferentes longitudes de onda a lo largo de la ruta siempre y cuando haya

conversores de longitud de onda para realizar la retransmisión, en caso contrario

se debe usar la misma lambda en todos los enlaces de la ruta. Es posible que en

la red se use una misma longitud como componente de diferentes rutas ópticas si

no comparten las mismas interfaces. La Figura 2.5 [3] muestra la relación de la

capa óptica y las capas clientes.

2.3.2.1. Hardware de redes ópticas de segunda generación La capa óptica de redes de segunda generación tienen parte de su soporte de

hardware en la aparición de Multiplexores Ópticos de Inserción Extracción

(OADM), Terminales Ópticos de Línea (OLT) y swithes conmutación óptica (OXC)

[3], [4].

Un OADM puede detectar señales de diferentes lambdas que viajan por una fibra

y procesar solo las que se requiera, permitiendo el paso de las demás sin ningún

procesamiento, reduciendo significativamente los costos de operación. Por otro

lado, un OLT se usa como punto de terminación en conexiones punto a punto para

multiplexar/demultiplexar las longitudes de onda que conforman las rutas ópticas,

también se encargan de la adaptación de señales entre las capas cliente y óptica.


26

Los OXC pueden conmutar una longitud de onda desde cualquiera de sus puertos

de entrada a cualquiera de salida, puede incluir o no conversión de longitud de

onda. La Figura 2.6 [3] ilustra un esquema de red que incluye elementos

asociados con el hardware de redes ópticas.

Figura 2. 6: Red óptica que ilustra algunos elementos de hardware

2.3.3. Redes ópticas de tercera generación.

En las redes de segunda generación, la función de enrutamiento corresponde a la

tarea de establecer una ruta frente a peticiones de conexión, lo que se conoce

como problema de Enrutamiento y Asignación de Longitud de Onda (RWA) [4], el

cual busca que el establecimiento de rutas optimice el uso de recursos. Dada la

altísima variabilidad del tráfico de información a través de la Internet, en la

actualidad el mayor interés se centra alrededor del enrutamiento dinámico, en el

que las conexiones se van estableciendo a medida que se van requiriendo y las

rutas son liberadas cuando ya no se necesitan. De igual manera se debe tener en

cuenta los requerimientos de calidad de servicio que presentan diferentes flujos,

por ejemplo, se debe considerar la alta sensibilidad al retardo que tiene la

transmisión de voz y video. Visto desde el ámbito administrativo de los ISP, que

requieren ser lo suficientemente competitivos, el enrutamiento resulta ser un

componente de fundamental que los impacta directamente, por lo cual se requiere

plataformas tecnológicas y procedimientos que lo soporten de forma eficiente.


27

En virtud de lo anterior parece claro que las redes de segunda generación no

satisfacen con suficiencia las necesidades de rápido y eficiente aprovisionamiento

de recursos que demanda el enrutamiento dinámico exigido por el tráfico de

Internet, ante lo cual la evolución de la capa óptica está llamada a proporcionar

capacidades que faciliten la administración de rutas de forma eficiente, incluyendo

el tratamiento de situaciones asociadas con fallas de red. Esto requiere la

incorporación de mayor inteligencia a la red, en el sentido que pueden

proporcionar rutas ópticas bajo demanda al tiempo que ofrece eficaces

mecanismos de recuperación.

La evolución mencionada en relación con la capa óptica marca la tercera

generación de redes ópticas, cuyo mayor desafío es la gestión de la misma,

usando software inteligente, que facilite, entre otras, la asignación y configuración

de rutas ópticas. En este sentido, una plataforma soportada en SONET/SDH es

insuficiente ya que, por ejemplo, usa ineficientemente el ancho de banda y el

enrutamiento se basa en demultiplexación que demanda conversiones óptico-

electrónicas. Además, al considerar las potencialidades de WDM, es acertado

pretender que las tecnologías de comunicación ópticas puedan transportar

paquetes IP directamente sobre DWDM, esto se conoce como redes ópticas de

tercera generación o redes de conmutación óptica de paquetes, en las que

enrutamiento y conmutación se realizan directamente en el dominio óptico.

Avances en el sentido de lo señalado, dan lugar a un replanteamiento de los

modelos arquitectónicos, llegándose a la arquitectura IP/WDM, la Figura 2.7 [1]

muestra un esquema de la evolución referida. Como importante alternativa de

gestión entra en escena GMPLS (Generalized Multiprotocol Label Switching).

GMPLS se tratará en este trabajo luego de tratar MPLS.


28

Figura 2. 6: Esquema de evolución de redes ópticas

Con estos elementos relacionados con algunas generalidades de las redes de

transporte y la evolución de redes ópticas se da por finalizado este capítulo, el

capítulo siguiente aborda elementos fundamentales de MPLS y GMPLS.

Capítulo 3. Fundamentos de MPLS y GMPLS

3.1. Conmutación de paquetes y conmutación de etiquetas

La conmutación de paquetes es un proceso de renvío basado en un identificador

lógico, el caso más representativo es la conmutación de paquetes IP, siendo la

dirección IP de destino el identificador asociado. Cada paquete IP se entrama


29

según la tecnología de enlace de datos, y en cada interfaz de la ruta se

desencapsula para leer la dirección IP y encapsularlo luego en una nueva trama

para su reenvío. La necesidad de desentramado en cada interfaz de la ruta se

constituye en la gran desventaja de la conmutación de paquetes IP, ya que este

proceso afecta la velocidad del reenvío.

3.2. Conmutación de etiquetas: paradigma de la tecnología MPLS

La necesidad de desentramar cada paquete IP en cada interfaz de la ruta, puede

considerarse parte del origen de investigaciones que dieron lugar a la conmutación

de etiquetas, lo cual hace parte del contexto de MPLS. En la conmutación de

etiquetas el envío se basa en la asociación de una etiqueta a cada paquetes

entramado, el paquete se reenvía en cada salto hacia el siguiente nodo en la ruta,

en función de la etiqueta entrante y con una nueva etiqueta saliente, de ahí que se

hable de intercambio y conmutación de etiquetas, sin que se requiera desentramar

completamente el paquete, ya que no se requiere leer la información de

direccionamiento IP [1], [2].

Las redes que funcionan bajo el paradigma de conmutación de etiquetas se llaman

redes MPLS o dominios MPLS. Como la etiqueta, se ubica entre los encabezados

de capa de enlace de datos y capa de red, desde el punto de vista del modelo

OSI, tiene sentido decir que la tecnología MPLS corresponde a una subcapa

intermedia entre las capas de enlace de datos y la capa de red. La Figura 3.1 [1],

ilustra la idea de la etiqueta como nuevo identificador para gestionar envíos.

Además de la ventaja dada por la conmutación de etiquetas, MPLS brinda

funcionalidades para mejor aprovechamiento de los recursos mediante la

adecuada distribución del tráfico, lo que corresponden a Ingeniería de Tráfico (TE)

[1].

Figura 3. 1: Etiqueta como identificador en la tecnología MPLS


30

3.3.1. LSR y LSP

Cada nodo de un entorno MPLS se conoce como Router de Conmutación de

Etiqueta o LSR (Label Switching Router). Cuando los paquetes, aún no

etiquetados, ingresan al dominio MPLS son recibidos por un LSR de entrada, el

cual los etiqueta según la pertenencia a flujos determinados, luego los envía a un

LSR vecino en el que se retira la etiqueta de entrada y se asigna una nueva para

el reenvío a otro LSR intermedio o al de salida. En el LSR de salida se retira la

etiqueta y se entregan a la red final de usuario. La ruta tomada por el flujo de

datos en las redes MPLS se conoce como Rutas Conmutadas por Etiquetas o LSP

(Label Switch Path). Las LSP en MPLS son unidireccionales, lo que hace

necesaria la configuración de otra LSP en sentido contrario entre los mismos

nodos extremos.

Cada LSR construye una tabla de reenvío, conocida como Tabla de Información

Base de Etiquetas de Reenvío o LFIB (Label Forwarding Information Base), que

guarda las asociaciones entre pares {interfaz de entrada, etiqueta de entrada} e

{interfaz de salida, etiqueta de salida}, lo que define la etiqueta e interfaz con que

se envía un paquete según la interfaz y etiqueta de entrada. La Figura 3.2 [1]

ilustra la idea básica del reenvío basado en la conmutación de etiquetas.

Figura 3. 2: Proceso de reenvío basado en la conmutación de etiquetas.

La tabla LFIB se construye con el concurso de un protocolo de señalización para

soportar el coherente uso de etiquetas, esto se basa en la información de las

tablas de enrutamiento de los LSR. En MPLS se usa protocolos de señalización


31

como LDP o Protocolo de Distribución de Etiquetas (Label Distribution Protocol) y

RSVP o Protocolo de Reserva de Recursos (Resource Reservation Protocol).

3.3.2. Clases de Equivalencia de Reenvío (FEC)

En MPLS una Clase de Equivalencia de Reenvío o FEC (Forwarding Equivalence

Class) corresponde a un grupo de paquetes tratados de la misma forma, enviados

por la misma ruta con la misma etiqueta, al ser, por ejemplo, paquetes con igual

prefijo de dirección IP destino o flujos con similares necesidades de tratamiento de

reenvío o pertenencia a alguna red privada. La asignación a una FEC se hace a la

entrada del dominio MPLS.

3.3.3. Apilamiento de etiquetas o túneles MPLS

Las pilas de etiquetas permiten crear túneles, o túneles de túneles, al agregar

múltiples LSP con el mismo etiquetado cuando las LSP comparten un conjunto de

nodos. A la entrada de cada túnel, a los paquetes de flujos agregados se aplica

una etiqueta adicional asociada con el túnel, sin remover la de entrada. La etiqueta

superior o última adicionada es la que se retira a la salida de un túnel. La última

etiqueta de la pila tiene un bit adicional que lo indica. El uso de pilas de etiquetas

tiene la ventaja de ahorro de procesamiento en los LSR, ya que por cada túnel,

tienen en su LFIB una única entrada que permite gestionar múltiples LSP. La

Figura 3.3 [1] muestra la idea asociada con el apilamiento de etiquetas o túneles

MPLS.

Figura 3. 3: Apilamiento de etiquetas, base para la creación de túneles en MPLS


32

3.4. Noción básica de señalización

La señalización corresponde al intercambio de mensajes de control para soportar

el establecimiento, mantenimiento, modificación y eliminación de rutas. En MPLS

el protocolo de señalización o de distribución de etiquetas opera entre pares de

LSR de tal modo que el LSR más cercano al origen, o LSR ascendente, sepa

cómo etiquetar los flujos hacia el LSR vecino más cercano al destino, o LSR

descendente.

El soporte de señalización en MPLS y GMPLS está en extensiones de los

protocolos RSVP y LDP, las que además cuentan con soporte para la ingeniería

de tráfico (TE). Las extensiones son CR-LDP o protocolo de enrutamiento basado

en restricciones y RSVP-TE para soportar reserva de recursos con

funcionalidades TE.

3.5. El paso a GMPLS

De manera simple se ve a GMPLS como Generalización de MPLS, pero es claro

tal generalización se relaciona con la heterogeneidad de las redes de transporte

en cuanto a las tecnologías de equipos que las componen, tanto que en un mismo

ISP hay segmentos formados por routers IP, switch de capa 2, switches

SONET/SDH, entre otros. La coexistencia compatible de variadas tecnologías

requiere suficiente capacidades de gestión. GMPLS surge del interés de

proporcionar mecanismos de control capaces de trabajar sobre cualquier

infraestructura sin importar su soporte en múltiples tecnologías, lo que sumado a

la actual necesidad de aprovisionamiento dinámico de rutas, se constituye en la

motivación de investigaciones alrededor de un plano de control suficientemente

inteligente que además permita ahorro de operaciones. En aras de la

generalización la lupa se dirigió hacia la similitud lógica de la conmutación de

longitudes de onda de WDM y la conmutación de etiquetas MPLS.


33

3.6. Génesis de GMPLS

La similitud lógica de la conmutación MPLS y WDM se refiere a que un switch

WDM toma lambdas entrantes, asociadas con un flujo, por una determinada

interfaz y retransmite con una lambda diferente por una interfaz de salida, por su

parte en la conmutación de etiquetas cada paquete entra por una interfaz, con una

etiqueta y es retransmitido por una interfaz de salida y otra etiqueta predefinida.

De aquí surge la idea de aplicar los principios de la señalización y enrutamiento

MPLS, dando origen al Multiprotocolo de Conmutación de Longitud de Onda o

MPλS (Multiprotocol Lambda Switching), en el que se tiene el mapeo {lambda

entrante, interfaz de entrada} a {lambda saliente, interfaz de salida} en los

dispositivos ópticos. El surgimiento de MPλS a partir del fundamento de MPLS,

llevó a la ampliación de las investigaciones para incluir otras tecnologías, como

conmutación de fibra, TDM, conmutación de capa 2, conmutación de

paquete/trama/celda, lo que condujo a formular los conceptos de MPLS

Generalizado o GMPLS [1].

3.7. Requerimientos y restricciones asociadas a GMPLS

La generalización GMPLS debe considerar algunas limitaciones y requerimientos,

algunas de ellas se comentan a continuación.

3.7.1. Limitaciones de la generalización de etiquetas:

La etiqueta en MPLS puede tener un valor arbitrario ya que ésta no representa

recurso físico alguno, mientras que, por ejemplo, en DWDM una etiqueta identifica

una lambda particular, lo que deja ver que en general no son de libre escogencia

al ser identificador de los recursos físicos conmutables (lambdas, ranuras de

tiempo, puertos o fibras específicas) [1].

3.7.2. Tipos de conmutación en Nodos de redes de transporte:

Un tipo de conmutación en un nodo de red de transporte se refiere a su capacidad

de multiplexado, demultiplexado y conmutación de unidades de datos. Entre los


34

diferentes tipos de conmutación en el ámbito de GMPLS se tiene conmutación de

paquetes etiquetados, conmutación de capa 2, TDM, WDM.

3.7.3. LSP en GMPLS:

En MPLS una LSP es una ruta definida en función de los LSR que la componen.

El establecimiento de rutas en redes de transporte basadas en GMPLS requiere la

programación de recursos para tomar tráfico entrante desde un recurso y enviarlo

a un recurso saliente. Puesto que en GMPLS las etiquetas se asocian a recursos

físicos, una LSP corresponde a una serie de dispositivos de retransmisión, la

respectiva programación para la entrega, las etiquetas que identifican recursos y

las interfaces de entrada y salida. La LSP en GMPLS también describe el estado

de rutas en el plano de control, es decir, en el plano de control existe información

del estado rutas o del LSP del plano de datos.

3.7.4. Granularidad del Ancho de banda:

La granularidad del ancho de banda se refiere a la mínima unidad de ancho de

banda asignable a un servicio. En MPLS puede ser del orden de bytes/seg, con lo

cual la capacidad de un enlace se puede dividir sin significativas limitantes entre

las LSP que lo comparten. Como en GMPLS existe asociación entre LSP y

recursos físicos, la división del ancho de banda se limita a las capacidades del

equipo de conmutación, siendo posible que el mínimo ancho de banda asignable

sea mucho mayor que el requerido para un servicio, para evitar el potencial

desperdicio, los mecanismos que soportan la transmisión deben tener en cuenta

esta restricción [1],[2].

3.7.5. Bidireccionalidad de conexiones en GMPLS

En MPLS la bidireccionalidad se logra mediante el establecimiento de dos LSP en

sentido contrario, en GMPLS el mismo propósito se logra asignando los recursos

al tiempo en ambas direcciones, necesitándose sólo un estado en el plano de

control, dando ahorro de memoria y procesamiento, facilidad y rapidez de

configuración [1].


35

3.7.6. Planos de control y de datos separados

Las redes de transporte transmiten gran cantidad de tráfico, por lo que los nodos

deben ser relevados de tareas de control asociadas con el examen de

encabezados, esto implica que los mensajes de control no viajen por los mismos

canales de datos, lo que corresponde a la separación de los planos de control y de

datos y su vez trae significativos desafíos de gestión a los protocolos GMPLS [1].

3.7.7. Túneles y jerarquías en GMPLS

La idea de pilas de etiquetas, para crear túneles de LSP, no se aplica

directamente en GMPLS debido a la asociación de etiquetas con recursos físicos.

La jerarquización de LSP en GMPLS está ligada a los tipos de conmutación, que a

su vez están atados a la granularidad. El anidamiento de LSP se da en función de

la jerarquía de tipos de conmutación, en los que una fibra puede anidar múltiples

canales de diferentes lambdas, cada canal puede anidar varias ranuras de tiempo

y éstas a su vez anidan paquetes IP, tal como lo sugiere la Figura 3.4 [1]. La

jerarquización hace eficiente el uso del ancho de banda y permite integrar

diferentes tipos de conmutación. Su aprovechamiento está ligado a apropiados

procedimientos de señalización, enrutamiento e ingeniería de tráfico.

Figura 3. 4: Jerarquía de tipos de conmutación

3.8. Señalización en GMPLS

En GMPLS la señalización se soporta en el protocolo RSVP-TE. Básicamente

RSVP reserva recursos a lo largo de una ruta para un flujo específico,

garantizando QoS y permitiendo indicar las necesidades de servicios. La

operación de RSVP se basa en siete mensajes de señalización que son: Path y


36

Resv, para establecer reservas para una sesión; PathTear y ResvTear, para

anular el estado de sesión y reservación; PathErr y ResvErr, para notificar errores,

y ResvConf, para confirmación de reserva [1].

RSVP-TE (RSVP para Ingeniería de Tráfico), es una extensión para distribución

de etiquetas sobre MPLS, soporta creación de rutas explícitas con o sin reserva de

recursos, es usado para crear, mantener y anular LSP, permitiendo re-

enrutamiento de túneles LSP para resolver problemas de caídas de red, cogestión

y cuellos de botella. Entre los puntos clave RSVP-TE están el uso de los mensajes

Path y Resv para petición y asignación de etiquetas, funcionalidades para

especificar una ruta explicita, especificar ancho de banda y otros parámetros y

para asociar un nuevo protocolo Hello a múltiples LSP relacionadas.

3.9. Mejoras de RSVP-TE para GMPLS.

En el caso de GMPLS el uso de RSVP-TE involucra nuevas extensiones basadas

en nuevos objetos, mensajes y procedimientos para administrar conexiones. Así

RSVP-TE y las mejoras para GMPLS se llama GMPLS RSVP-TE. Las mejoras se

refieren a los siguientes aspectos.

3.9.1. Señalización de LSP jerárquicos

La señalización GMPLS usa los LSPs jerárquicos. La siguiente Figura 3.5 [5]

muestra el establecimiento de una serie de LSPs a lo largo de un camino que

consiste de routers (R0, R1, R8 y R9), switches SONET (S2 y S7), switches OEO

(Ópticos Electro Óptico) WDM (O3 y O6) y switches fotónicos (P4 y P5) [5].


37

Figura 3. 5: Establecimiento de una serie de LSP a lo largo de una ruta con diferentes tipos de conmutación.

Se requiere el envío de mensaje PATH request, path1 para el establecimiento de

la LSP1 entre R0 y R9, se envía de R0 a R1. El router R1 activa la iniciación del

LSP2 entre R1 y R8. El LSP1 es anidado dentro del LSP0.

Los mensajes PATH: path1, path2, path3 siguen propagándose, y los LSPs siguen

anidándose hasta el establecimiento final del LSP0 entre R0 y R9. Un LSP se

establece cuando el mensaje Path completa su camino dentro de los LPSs de

orden superior y un mensaje RESV es recibido.

La figura 3.6 [5] muestra como el LSP4 es el LSP de más alto nivel, y de acuerdo

con la figura anterior es el que se establece primero, el LSP3 se establecido

dentro del LSP4, el LSP2 dentro del LSP3 y el LSP1 dentro del LSP2.


38

Figura 3. 6: Establecimiento de LSPs entre routers

3.9.2. Mejoramiento de etiquetas

Además del concepto de etiqueta generalizada, GMPLS introduce conceptos tales

como solicitud de etiqueta generalizada, conjunto de etiquetas y etiqueta sugerida.

3.9.3. Solicitud de etiqueta generalizada GMPLS generaliza el mensaje de solicitud de conexión para distinguirlo de una

solicitud no generalizada y permitir transportar detalles de parámetros adicionales

que especifican la solicitud. La solicitud de etiqueta generalizada da tres

características necesarias en el soporte de la LSP solicitada: El Tipo de

codificación, el Tipo de conmutación y el Tipo de datos.

3.9.4. Conjunto de etiquetas: Se utiliza para restringir rangos de etiquetas a usarse en una LSP. El receptor de

un conjunto debe restringir su opción de etiquetas del conjunto. Un conjunto de

etiquetas debe estar presente a través de múltiples saltos, cada nodo genera su

propio conjunto de etiquetas de salida, posiblemente basado en el conjunto de

etiquetas de entrada y las capacidades de hardware.

3.9.5. Etiqueta sugerida Introducida para reducir la latencia en el establecimiento de la LSP, cada LSR

selecciona una etiqueta que considere más apropiada y la señaliza en su trayecto

hacia adelante y comienza a programar su propio switch, asumiendo que la


39

etiqueta será la elegida. Al recibir la respuesta a la señalización, el mensaje ya

lleva una etiqueta. Si esta etiqueta confirma la escogencia sugerida ya que el

switch se encuentra programado. Cuando la programación del switch ya está

totalmente estabilizada, la respuesta respectiva de señalización puede seguir

enviándose en sentido ascendente.

3.10. Enrutamiento

3.10.1. Enrutamiento IP e Ingeniería de Tráfico

Previo a MPLS el enrutamiento ha correspondido en la selección del siguiente

salto en la ruta hacia el destino cada router, según el esquema de mejor esfuerzo,

toma la decisión de reenvío basado en la dirección destino y la información de su

tabla de enrutamiento. En grandes redes la construcción de las tablas depende de

los protocolos de enrutamiento de estado enlace, como OSPF e IS-IS [1].

Un significativo avance en el enrutamiento surge con las técnicas de Ingeniería de

Tráfico (TE), que colocan tráfico sobre rutas precalculadas, evitando sobreutilizar

o subutilizar enlaces, también permite la selección de enlaces para proporcionar la

calidad de servicio deseada o satisfacer restricciones que imponen las

aplicaciones. En las redes con ingeniería de tráfico los enlaces con tales

capacidades, se conocen como enlaces TE y corresponden a abstracciones de los

recursos de la red [1], [2].

3.11. Enrutamiento en GMPLS

En MPLS y GMPLS el enrutamiento realmente consiste en intercambio de

información útil para el cálculo de rutas, antes de la entrada en operación de

señalización que instalará la LSP [1], lo que involucra uso de ingeniería de tráfico.

La aplicación de ingeniería de tráfico requiere mucho más que la información de

estado de enlaces dada por los protocolos de enrutamiento, por lo cual un

elemento clave es la Base de Datos de Ingeniería de Tráfico (TED), que guarda

información de los enlaces de TE y es usada como insumo del cálculo de rutas.

Entre la información almacenada en la TED se encuentra Dirección de router, ID

del router en el otro extremo del enlace, Dirección IP de interfaz local, Dirección IP


40

de interfaz remota, Métricas de TE, Máximo Ancho de banda del enlace, Máximo

Ancho de banda que se puede reservar.

3.11.1. Información de Enrutamiento requerida en redes GMPLS

En GMPLS, además de la información guardada en la TED, se requiere

información relacionada con capacidades de conmutación de los LSR,

granularidad del ancho de banda, máximo y mínimo ancho de banda asignable,

información para tratar la necesidad de protección ante fallas de enlaces

individuales y cuáles enlaces TE serían afectados por una misma falla de

hardware, respecto a esto último se define los grupos de enlaces de riesgo

compartido (SRLG: Shared Risk Link Groups). Toda esta información debe ser

distribuida por los protocolos de enrutamiento GMPLS [1].

3.11.2. Protocolos de Enrutamiento en GMPLS

Los protocolos de enrutamiento GMPLS se fundamentan en extensiones de

protocolos IS-IS y OSPF. Aunque todos los routers participantes se instruyen para

realizar los reenvíos, no todos deben procesar la información de TE y GMPLS,

esta característica es conocida como intercambio opaco de información de

GMPLS y TE.

OSPF cuenta con la unidad básica de intercambio de información LSA (Link State

Advertisement) para las publicaciones de estado enlace, la cual posee un

indicador “opaco”, que permite a los routers determinar si la información no es

parte del enrutamiento IP.

3.12. Ingeniería de Tráfico GMPLS

En GMPLS los enlaces dinámicos de datos se añaden o eliminan con el fin de

alcanzar objetivos de ingeniería de tráfico. Un enlace TE corresponde a un enlace

de datos, pero también puede publicarse como agrupaciones de enlaces en

paralelo, e incluso a como una fracción de los recursos de un enlace. Una TE-LSP

es una LSP publicada como un enlace TE.


41

3.12.1. Atributos de enlaces de TE

Entre los atributos de enlace TE están el Tipo de enlace (punto a punto o

multiacceso), el identificador Link ID de enlace, direcciones IP de Interfaces local y

remota, identificador de enlaces local y remoto para enlaces no numerados. En

GMPLS otros atributos de enlace TE usados en cálculo de ruta basado en

restricciones son:

3.12.1.1 Métrica de Ingeniería Tráfico

3.12.1.2. Grupo administrativo: Algunos de valores identifican calidades de los enlaces que pueden ser

considerados para evitar o forzar su uso en el cálculo de ruta.

3.12.1.3. Tipo de protección de Enlace: Indica las capacidades de protección del enlace TE, su valor puede limitar el

cálculo a tomar aquellos enlaces que satisfagan las necesidades de protección.

3.12.1.4. El Grupo de Enlace de Riesgo Compartido (SRLG) A los que pertenece el enlace.

3.12.1.5 Descriptor de Capacidad de conmutación de interfaz Indica características de una interfaz de datos relacionada, entre la información

que atañe a este atributo se incluye el tipo de Capacidad de conmutación de la

interfaz, Tipo de codificación de datos (por ejemplo, Ethernet, SDH), Ancho de

banda de LSP máximo disponible para reserva según los niveles de prioridad.

3.13. Protocolos de soporte de Ingeniería de Tráfico GMPLS

La señalización se da a través de mensajes que viajan encapsulados en paquetes

IP, por lo cual se necesita las tablas de reenvío soportadas por protocolos como

OSPF o IS-IS. Si se ejecuta principios de ingeniería de tráfico, se requerirá

información de la topología de la red, en lo concerniente a switches de datos y

enlaces de TE, tal información constituye el insumo de la TED. Con el fin de

soportar el intercambio de mensajes que soportan el mantenimiento de la TED, se

introduce inicialmente en MPLS los protocolos OSPF-TE e ISIS-TE. Vale anotar

que existe la tendencia a ver a OSPF-TE como una OSPF extendida para soportar

la ingeniería de tráfico, esto no es del todo cierto ya que si bien OSPF-TE usa el


42

mismo mecanismo de distribución de publicaciones que OSPF, los dos protocolos

publican información para diferentes fines. OSPF-TE e IS-IS son descritos

brevemente a continuación.

3.13.1. OSPF-TE e IS-IS-TE

OSPF-TE utiliza la opción LSA OSPF opaca, la cual tiene alcance de área OSPF,

para realizar publicaciones que atañen a información de TE. El componente de TE

en cada nodo administra la respectiva TED y genera el grafo de TE de la red, base

para el cálculo de rutas. La información TE va organizada en conjunto de TLV. En

OSPF hay dos tipos de TLV que son: TLV Dirección del router, usado para dar a

conocer direcciones IP del controlador o identificador único del controlador que

hace la publicación. El otro es el TLV Enlace TE, usado para publicar atributos de

un enlace de TE. Estos atributos corresponden a sendas sub-TLV que son

anidados en TLV de orden superior. Actualmente, hay varias restricciones en el

uso de TLV TE. Mediante sub-TLVs de enlaces TE puede publicarse atributos del

enlace GMPLS TE.

Por su parte IS-IS-TE define un TLV de identificador de Router de Ingeniería de

Tráfico (TE Router ID TLV) y la TLV de Accesibilidad extendida. Al igual que con

OSPF-TE, GMPLS IS-IS-TE adiciona nuevas sub-TLV a la TLV IS-IS de

Accesibilidad extendida con el fin de publicar atributos de enlace TE como

identificadores de enlaces locales y remotos para enlaces TE no numerados, tipos

de protección de enlace, descriptores ISC y SRLGs.

3.13.2. Construcción de enlaces de Ingeniería de Tráfico

En GMPLS, la necesidad de cálculos de rutas con base en restricciones,

impuestas por la ingeniería de tráfico, demanda gran cantidad de publicaciones de

información de TE, sin embargo, el aprovechamiento de agrupaciones de enlaces

TE, con similares necesidades, facilita la publicación de múltiples enlaces como

uno solo.

3.13.3. Regiones de Ingeniería de Tráfico y capas de conmutación

GMPLS se concibe para atender necesidades de control de entornos con variadas

capacidades de conmutación (network layering). Si la conexión de nodos finales


43

requiere el concurso de diferente capacidad de conmutación, se puede pensar en

la jerarquía de capas de red según las capacidades de conmutación GMPLS. Tal

amalgama se compone de regiones TE, o segmentos caracterizados por un tipo

de conmutación, así como capas de conmutación, que se refieren a enlaces con

interfaces asociadas a iguales tipos de conmutación, codificación y granularidad.

Resulta claro que una región puede abarcar una o más capas de conmutación.

Una LSP se aprovisiona en una capa pese a poder desencadenar

reaprovisionamiento en múltiples capas e incluso regiones.

A mayor cantidad de capas de conmutación más exigencia al plano de control

GMPLS, en este caso se usa integración vertical o procedimientos en los que una

instancia del plano de control opera sobre más de una capa de conmutación

basado en H-LSP o LSP jerárquicas. Se debe afrontar tres importantes desafíos

en el cálculo de rutas: 1) necesidad de restringir el cálculo a enlaces con

capacidad de conmutación específica, 2) Si se supera el desafío 1, necesidad de

una capacidad de adaptación para colocar o extraer una carga útil SDH sobre uno

de los canales de longitud de onda en los enlaces CD y EF y 3) Resuelto 1 y 2, la

capacidad de los canales sólo será parcialmente utilizada, desperdiciado el resto

de ancho de banda.

En integración vertical, un nodo frontera de capa es un switch conectado a enlaces

TE con interfaces de varias capacidades de conmutación y capacidad de

adaptación para colocar/extraer una capa de menor capacidad de conmutación

en/de una con mayor capacidad. No hay forma que los nodos frontera publiquen

sus capacidades de adaptación, se asume que nodos con enlaces de dos

diferentes capacidades de conmutación pueden conmutar entre ellos, pero no

siempre es así.

Previo al ingreso a un nodo frontera, donde se resolvería el desafío 2, un ente de

cálculo puede sortear el desafío 1 usando enlaces con capacidad de conmutación

mayor o igual a la requerida. En lo que concierne al desafío 3, cuando llega un

mensaje LSP Setup que requiere acomodación a un nivel superior de capacidad

de conmutación, se da la configuración de una LSP jerárquica (H-LSP) que podrá

utilizarse como enlace de datos por una capa de conmutación de capacidad

inferior.


44

Los nodos extremos de la H-LSP pueden publicar la LSP como un enlace de TE

con la capacidad de conmutación asociada. Los nodos frontera de capa realizan la

preparación de tráfico, o refinamiento de granularidad de un túnel de granularidad

mayor a la requerida.

3.13.4Topología virtual de red

Vale aclarar que a menor nivel en la jerarquía de capas de conmutación, mayor es

la capacidad de conmutación, por ejemplo, las redes FSC constituyen la capa más

baja, mientras que las PSC, la más alta. La conectividad de extremos soportada

en el uso de H-LSP da lugar al concepto de Topología Virtual de Red (VNT), que

enruta tráfico de capas superiores que requieren una fina granularidad de

conmutación.

Un enlace TE puede soportarse en una H-LSP de una VNT de formas que podrían

combinarse, por ejemplo, crearse una H-LSP por la demanda del nodo frontera de

capa, necesitando que el ente de cálculo haga suposiciones respecto a los nodos

frontera involucrados y que tenga total visibilidad de la topología de la capa

servidor. Otra posibilidad es pre-establecer un conjunto de H-LSP que atraviesen

la capa de servidor y publicarlos para su uso en cálculo, pero se requiere conocer

los nodos frontera a conectar y el ancho de banda requerido, lo que podría llevar a

establecer una malla de H-LSP entre los nodos frontera, pero desperdiciando

mucho ancho de banda al reservar recursos para H-LSP sin tráfico. Una tercera

forma es la llamada H-LSP virtual, en la cual la H-LSP sobre se activa demanda,

pero haciendo visibles los enlaces TE asociados con el nodo de cálculo antes de

crear realmente las LSP. Las H-LSP son configuradas en los nodos frontera y se

publican como enlaces TE como parte de la VTN, pero sólo se señalizan ante la

presencia de un mensaje LSP Setup.

Como cuarta alternativa la comunidad CCAMP propone involucrar el concepto de

soft H-LSP, que corresponde a enlaces dinámicos semiaprovisionados, asignando

los recursos en todos los enlaces, pero no limitados a las conexiones cruzadas

LSP y se pueden compartir entre varios soft H-LSP. Cuando al nodo de entrada

llega un mensaje de configuración de LSP de capa superior, el softH-LSP se

activa y se envía un mensaje LSP Modify salto a salto, lográndo el no desperdician


45

los recursos de una soft H-LSP no usada al tiempo que está disponibles para su

uso.

Frente al impacto que genera los frecuentes cambios de topología de la red sobre

el enrutamiento, vale preguntarse ¿cuándo eliminar un enlace TE asociado a un

LSC H-LSP?, podría decirse que se desmonte inmediatamente después que la

última LSP de extremo a extremo se retira, pero si por algún motivo se da una

rápida secuencia de configuración y desmonte de una misma LSP, se tendría la

necesidad de configurar y desmontar la H-LSP que la soporta, por tanto se debe

pensar en un mecanismo que dé solidez al enrutamiento ante tal variabilidad o

situaciones en que una H-LSP activa no transporta tráfico o usa una fracción muy

pequeña de recursos [1].

Antes de desmontar la H-LSP se podría pensar en reconfigurar una LSP sobre

otra H-LSP existente apropiada, operación conocida como hacer antes de romper

(beforebreak), o quizá sobre una ruta a través de capas superiores y sobre la capa

de servidor usando otro H-LSP entre otro par de frontera. Una vez más, usar

“hacer antes de romper” para volver a situar la LSP de extremo a extremo. En

último caso se puede usar la anticipación de manera que una H-LSP de baja

prioridad sea desplazada por una solicitud de servicio de mayor prioridad, LSP

llevadas sobre la H-LSP desplazadas se desmontan y se debe buscar su

reconfiguración.

3.13.5. Protección H-LSP

Ante las necesidades de contar con robustos mecanismos de recuperación, se

puede crear dos H-LSP, de tal manera que una soporte el servicio y la otra esté

disponible a entrar en operación en caso que la principal falle, el nodo frontera de

capa puede formar dos enlaces paralelos basado en las H-LSP y publicar dos

enlaces separados (esquema 2). Aunque es similar en espíritu, los túneles

anidados pueden ser conmutados en la H-LSP paralela si el trabajo falla,

conceptualmente es diferente del modelo de un único enlace asociado con dos H-

LSP (esquema 1) por las siguientes razones.


46

En el esquema 1, el segundo H-LSP no puede ser utilizado para túneles

anidados desprotegidos, todos sus recursos están totalmente dedicados a

proteger los túneles anidados llevados por la primera H-LSP. En el

esquema 2 ambas H-LSP pueden ser utilizadas para transportar túneles

anidados sin protección no relacionados.

En el esquema 1 se garantiza que si hay recursos disponibles en la primera

H-LSP suficiente para anidar un túnel en particular, también hay recursos

en el segundo H-LSP para llevar el mismo túnel anidado durante la

protección. Este no es el caso en el esquema 2, porque otros túneles

pueden haber sido anidados dentro de la segunda H-LSP y por tanto

agotan los recursos.

En el esquema 1, la recuperación del servicio se realiza en el nivel de

enlace, mientras que en el esquema 2 se consigue en el nivel de túneles

anidados (es decir, nivel de trayecto).

3.13.6. Capacidades de adaptación

No existe hasta ahora un atributo de enlace TE para publicar las capacidades de

adaptación de la interfaz, tal conocimiento de las capacidades de adaptación

resulta importante como elemento de restricción en el cálculo de ruta con el fin de

disminuir la probabilidad de bloqueo. La información sobre capacidades de

conmutación debería incluir Capa de conmutación de la señal a ser adoptada o

extraída, Capa de conmutación de la H-LSP a ser creada y Ancho de banda

disponible con fines de terminación/adaptación.

Las descripciones presentadas hasta aquí, en relación con la evolución de las

redes de comunicaciones a través de fibra óptica, la necesidad de atender

requerimientos de QoS y aplicar principios de ingeniería de tráfico, dejan ver

complejidades involucradas en la transmisión de información a través de las redes

de trasporte, las mismas que motivan la realización del presente trabajo, en el que

se pretende abordar aspectos fundamentales relacionados con el soporte del

enrutamiento en redes GMPLS. Si se tiene en cuenta, por ejemplo, que el

enrutamiento GMPLS está llamado a considerar mecanismos de protección, uso


47

eficiente del ancho de banda, limitación del retardo, confiabilidad, entre otros, es

apropiado el tratamiento del problema dentro del contexto de cálculo de rutas más

cortas sometido al cumplimiento de restricciones, lo que no es exclusivo del área

de las redes de comunicaciones y que ampliamente se conoce en la literatura

como Constrainned Shortest Path Problem o CSPP y que se tratara en el siguiente

capítulo.

3.14. PCE: Path Computation element

Buena parte de las características del soporte de ingeniería de tráfico y

aprovisionamiento de QoS en redes GMPLS están basadas en algún algoritmo de

cálculo de rutas, generalmente teniendo en cuenta restricciones asociadas con las

exigencias de las comunicaciones de hoy. Lo que es claro que puede resultar en

una tarea compleja. La sección 2.13 se dedicó a las descripción de aspectos

relacionados con el enrutamiento en redes GMPLS, sin embargo no se ha hecho

referencia explícita sobre qué elementos de la red se encargan de realizar estos

cálculos, frente a lo cual resulta conveniente anotar que quizá, entre varias

alternativas, la que tiene más acogida es la basada en sistemas PCE o Path

Computation Element. El cual surge como una propuesta planteado por la IETF

con el fin de atender las complejidades de cálculos de ruta. El paradigma PCE

consiste en la asignación de uno o varios elementos de la red para realizar el

cálculo de rutas requeridas con base la topología de red [6]. En este sentido, cada

LSR de la red, con necesidades de establecimiento de rutas para envío de datos,

realiza una solicitud de cálculo (Path Computation Request) al PCE, quien realiza

el respectivo cálculo atendiendo las debidas restricciones del contexto, tales

restricciones están generalmente asociadas con la disponibilidad de dispositivos,

de ancho de banda, características de los enlaces, retardos, probabilidad de

bloqueo, entre otras. El algoritmo de cálculo compara los requerimientos con los

recursos disponibles, y con base en ello elabora una tabla en la cual registra solo

los enlaces que cumplen las condiciones establecidas. Luego se ejecuta el

procedimiento algorítmico para el cálculo de la mejor ruta con base en la tabla

construida. La Figura 3.8 [6] ilustra la idea básica de la operación del modelo PCE.


48

Figura 3. 7: Diagrama básico de la lógica de PCE

3.14.1. Arquitectura del modelo PCE

El modelo PCE para cálculo de ruta considera un conjunto de entidades, que son:

El PCC o Path Computation Client, que corresponde a cada uno de los LSR que realizan una solicitud de cálculo.

El PCE o Path Computation Element, que es la aplicación encargada de realizar el cálculo de ruta según requerimientos. Luego e calculada la ruta, el PCE envía la correspondiente información al cliente.

La TED o Traffic Engineering Database, correspondiendo a la tabla de enrutamiento de ingeniería de tráfico que se usa como insumo de cálculo por parte del PCE.

Path Computation Request, es la solicitud de cálculo de ruta emitida por el cliente al PCE.

Path Computation Response, representa la información de respuesta en, relación con la ruta calculada, envida por el PCE al PCC


49

La aplicación PCE puede residir en cualquiera de los nodos de la red, lo que se

conoce como modalidad composite, o en un equipo externo, en cuyo caso, detecta

toda la información del protocolo de enrutamiento utilizado para mantener

actualizada la TED, está última modalidad se conoce como external. La Figura 3.9

[6] muestra los esquemas básicos correspondientes a composite y external.

Figura 3. 8: Arquitectura de PCE

En un modelo centralizado, un único PCE es el responsable de realizar todos los

cálculos producto de las diferentes solicitudes, con fines de respaldo se designa

un PCE de backup que entra en funcionamiento en caso de falla del principal. En

un modelo distribuido, existen varios PCE en la red. El componente a través del

cual se administra las comunicaciones de Solicitud/Respuesta entre los PCC y los

PCE es el protocolo de comunicación PCE. El PCECP opera bajo el esquema

Cliente/Servidor, en el que, lógicamente los PCC son los clientes.

El contexto general de PCE contempla entre otros aspectos situaciones de cálculo

de una ruta por uno o por múltiples PCE, cálculo on-line y off-line, comunicación

inter PCE, PCECP inter-área.


50


51

Capítulo 4. Contexto general del problema de cálculo de rutas Aunque este trabajo se centra en problemas asociados con requerimientos de

enrutamiento en redes GMPLS, vale anotar que el cálculo de mejores rutas o de

rutas más cortas no es exclusivo del ámbito de las redes de comunicación, sino

que se encuentra por ejemplo en diferentes áreas, por lo que en general se

conoce como problema de la ruta más corta o SPP. Los principios que buscan

solución a problemas de ruta más corta se encuentran inicialmente en la teoría de

grafos, sin embargo el surgimiento de problemas que imponen condiciones

adicionales al cálculo ha dado lugar a una especialidad de SPP conocida como

problema de ruta más corta restringida (Constrainned Shortest Path Problem) o

CSPP, cuyo estudio formal exacto, para llegar a soluciones óptimas, involucra

áreas de la Investigación de operaciones, sin embargo, dada la complejidad de

este tipo de problemas también se ha abordado la búsqueda de métodos que

permiten hallar soluciones subóptimas aceptables desde el punto de vista práctico,

que son menos intensivos en carga computacional, estos se conocen como

esquemas o enfoques de aproximación.

En este capítulo se presenta primero una descripción del SPP y los algoritmos

básicos de solución más conocidos, los que a su vez hacen parte de

procedimientos más avanzados para resolver problemas más complejos.

Posteriormente se aborda lo correspondiente a CSPP y algunos enfoques de

solución.

4.1. Aspectos básicos de complejidad

Dado un algoritmo creado para resolver un problema, se requiere conocer su

rendimiento, en lo cual se tiene en cuenta su simplicidad y el uso eficiente de


52

recursos computacionales, como memoria y tiempo ejecución. Si nos referimos a

la cantidad de memoria requerida para el funcionamiento del algoritmo, se define

lo que se conoce como complejidad espacial, mientras que la medida de la

cantidad de tiempo necesaria para su ejecución se refiere a la complejidad de

tiempo.

El tiempo de ejecución de un algoritmo depende de factores como: las entradas, la

calidad del código, la velocidad de instrucciones de la máquina, la complejidad

intrínseca del algoritmo, entre otros. Se reconoce como medida teórica de la

complejidad de tiempo a una función matemática que limita el tiempo de ejecución

en función del tamaño de las entradas entendido este como el conjunto de

componentes sobre las que se ejecuta el algoritmo, ejemplo de ello es la

dimensión de un vector. En teoría indica el número de instrucciones

ejecutadas por una máquina ideal, con lo cual se busca medidas independientes

de la máquina. Un importante principio relacionado con la implementación de dos

versiones distintas de un mismo algoritmo es el principio de invarianza, el cual

establece que su diferencia en ejecución radica en un factor multiplicativo, en cuyo

caso se dice que los algoritmos son de orden

La ejecución de un algoritmo depende de la ejecución del número de operaciones

básicas de tiempo de ejecución constante. Si es el conjunto

de entradas posibles de un problema dado cuyo tamaño es n, y

es el conjunto de número de operaciones realizadas por el

algoritmo, entonces, el número de operaciones ejecutadas para resolver la entrada

es . En un algoritmo dado se distingue la complejidad de Peor caso,

complejidad de Mejor caso y complejidad de Caso promedio, las cuales se refieren

respectivamente a los números máximo, mínimo y promedio de operaciones

básicas a realizar para una entrada de tamaño n.

4.1.2. Clases de Complejidad

En el campo algorítmico se habla de problemas muy difíciles de resolver o que

desafían notablemente el uso de equipos computacionales. En este sentido se

clasifica las clases de complejidades.


53

4.1.2.1. Complejidad Clase P y Complejidad de Clase NP La complejidad clase P (Polinomial Time) consta de los problemas de decisión que

se pueden resolver en tiempo polinómico, por un algoritmo determinístico se

considera como problemas tratables, en el sentido que se pueden resolver en la

un tiempo razonable. Los problemas para los cuales el mejor caso tiene

complejidad superior a la polinomial se denominan problemas intratables. Por otro

lado, los problemas de decisión que son resueltos por un algoritmo no

determinístico en tiempo polinómico. Algunos de estos problemas se caracterizan

por el hecho de poder aplicarse un algoritmo de verificación de tiempo polinómico

para comprobar si una posible solución es o no valida. Esto lleva a un método de

resolución no determinística llamada heurística.

4.1.2.2. Complejidad de Clase NP-Completos y NP-duros Una gran cantidad de problemas de tipo NP son de extrema complejidad que son

los de peor caso de la clase NP. La Clase NP-Duro es el conjunto de los

problemas de decisión que contiene los problemas M tales que todo problema L

en NP puede ser transformado polinomicamente en M. Esta clase puede ser

descrita como los problemas de decisión que son al menos tan difícil como un

problema de NP.

4.2. Representación de redes para cálculo de rutas

Para efectos de cálculo de la ruta más corta, una red se representa como un grafo

, siendo el conjunto de | | nodos de la red y

, el conjunto de | | arcos o enlaces entre pares de nodos,

usamos para denotar un enlace que sale de del nodo y llega a . Se dice

que dos nodos cualesquiera están conectados si existe al menos una ruta

en el grafo con origen en y final en Una ruta desde un nodo origen

hasta un nodo destino es una secuencia de nodos

en los que las parejas están unidos por un enlace del grafo. La figura 4.1

[1] muestra un ejemplo de red señalando una métrica entre sus enlaces.


54

Figura 4. 1: Grafo de una red mostrando nodos, enlaces y sus métricas.

Con cada enlace se asocia un valor referente al costo de usarlo, denotado por

El costo de una ruta es la suma de los costos de los enlaces que la forman. Si

un nodo se cruza no más de una vez se dice que la ruta es simple o sin bucles.

Dado que la teoría de grafos en general contempla arcos de costos negativos,

positivos y cero, se debe manejar con cuidado estos costos, ya que pueden

producir inconsistencia de bucles negativos, aquellos en que la ruta costaría

menos cada vez que toma tales arcos.

4.3. Algoritmos de cálculo de la ruta más corta

Existen diferentes algoritmos de ruta más cortas desde el nodo fuente al destino,

aquí se describe brevemente algunos de ellos como soporte de este trabajo, que

involucra cálculos de ruta basada en restricciones. En todos se considera el hecho

que la ruta más corta entre cualquier par de nodos se compone de las rutas más

cortas, es decir, si es la ruta más corta entre los nodos , y cruza los

nodos , debe tomar la ruta más corta entre los nodos [1].

Además esta debe ser una ruta simple, ya que si tiene bucles se podría obtener

una ruta más corta eliminando los bucles. Otro principio importante que se

considera en el cálculo de ruta, es el hecho que si representa el costo o

distancia de la ruta más corta desde el nodo hasta el nodo entonces una ruta

de a es una ruta más corta si y solamente si para cada enlace

en el grafo [1].


55

4.3.1. Algoritmo de Dijkstra

Para hallar la ruta más corta desde un nodo origen hasta cualquier otro nodo

de un grafo , de nodos y costos no negativos mediante el Algoritmo de

Dijkstra [1], se tiene para pares de nodos adyacentes,

para pares no adyacentes (en la práctica se toma como la suma de costos de

todos los arcos). La matriz de adyacencias del grafo está dada por:

[ ]

El algoritmo usa un conjunto , que al inicio está constituido solo por el nodo

origen y un conjunto . Con base en el menor costo

en la primera iteración el algoritmo selecciona el nodo asociado al

menor costo de ruta, para incluirlo en , con lo cual se tiene la ruta más corta entre

origen y el seleccionado. En la segunda iteración se calcula los costos de rutas

que van de hasta los nodos que aún no pertenecen a , (de a

pasando por .

El vector fila de la fila de la matriz de adyacencia para la cual se toma

como vector estimado o inicial de costos de rutas desde hasta cada nodo ,

este vector, [ ] [ ] se modifica de tal manera

que se sustituye el costo actual por los resultados de cálculos que disminuyan el

respectivo costa de ruta, con lo que además se tiene la secuencia de nodos que la

componen. Este paso se repite hasta que todos los nodos del grafo hacen parte

del conjunto [ ].

4.3.1.1. Descripción formal del algoritmo de Dijkstra:

[ ] [ ]


56

Paso 1: Inicio del algoritmo

[ ]

Paso 2: obtención del siguiente nodo de

Hallar el nodo asociado a

Hacer

Paso 3: Actualización del vector de costos (operación conocida como relajación)

{ }

Los pasos 2 y 3 se repiten hasta , es decir hata que el conjunto quede

vacío. En cuanto a la complejidad de tiempo del algoritmo de Dijkstra se tiene que

esta es de .

4.3.2. Algoritmo de Bellman-Ford

Este algoritmo halla las rutas más cortas desde un nodo a los restantes de un

grafo de nodos, de tal manera que primero halla las rutas más cortas

compuestas por un enlace, luego las compuestas a lo sumo por dos enlaces,

luego las compuestas por tres enlaces a lo sumo y así sucesivamente [1].

4.3.2.2. Descripción formal del algoritmo de Bellman-Ford:



57

Paso 2: Actualización

Hallar el nodo asociado a

Hacer

Paso 3: Actualización. Para cada Calcular

{ }

Los pasos 2 y 3 se repiten hasta , es decir hata que quede vacío.

El algoritmo de Bellman-Ford se ejecuta en tiempo ): La inicialización toma

tiempo veces, cada una de las pasadas por los arcos toma , y el

bucle final requerido para la detección de bucle negativo toma tiempo .

4.3.3. Algoritmo de Johnson

En un algoritmo útil para hallar rutas más cortas entre los pares de nodos

en un grafo con algunos arcos de costos negativos. Transforma el grafo

en uno sin costos negativos, luego ejecuta el algoritmo de Dijkstra o Bellman-

Ford en . La transformación es tal que la ruta más corta entre dos nodos

de es también la ruta más corta entre dos nodos en [1]. La transformación

consiste en lo siguiente.

Agregar un nodo conectándolo a los demás con arcos de costo cero. Por tanto,

para todo ; para cada

Ejecutar el algoritmo de Dijkstra o Bellman-Ford en con como fuente para

hallar las estimaciones de distancia para todos los nodos .

Todos los arcos son re-ponderados según la fórmula:


58

Donde nuevo costo del arco , costo original del arco ,

son vectores de distancia hallados por el algoritmo Bellman-Ford para los

nodos de origen y de terminación de arco .

4.3.3.1. Descripción formal del Algoritmo de Johnson


Paso 2: Actualización Hallar el nodo asociado a

Hacer

Paso 3: Actualización. Para cada Calcular

{ }

Los pasos 2 y 3 se repiten hasta , es decir hata que quede vacío.

4.4. Extensión de algoritmos básicos para hallar múltiples rutas más cortas.

Atendiendo a necesidades particulares, hallar la ruta más corta no siempre es lo

mejor, muchas veces se requiere hallar dos o más rutas más cortas, una primera

idea frente al requerimiento de hallar rutas es hallar inicialmente la ruta más

corta entre origen y destino, eliminar un arco del grafo, hallar una nueva ruta más

corta y repetir este proceso hasta hallar las rutas necesitadas, sin embargo, esto

resulta poco útil y práctico [1]. Hay algoritmos que en cambio buscan sólo las rutas

que satisfacen las necesidades, uno de ellos guarda una lista de rutas

previamente halladas y una cola de mínima prioridad de candidatas, usa una


59

técnica de ramificación de rutas previamente halladas, y si se debe hallar la j-

esima ruta (con j > 2) y la anterior hallada tiene primeros arcos comunes con todas

las antes calculadas, esto corresponde al algoritmo KSP que se describe a

continuación.

4.4.1. Algoritmo KSP

El propósito del algoritmo KSP [1] es hallar las primeras K rutas más cortas a partir

de un grafo de red, los pasos que sigue el algoritmo son los siguientes:

Asignar como punto de ramificación al nodo final del tallo, o parte común de la

última ruta hallada y las anteriormente obtenidas.

Los arcos que inician en el punto de ramificación y pertenecientes a cualquiera

de las (j – 2) rutas halladas anteriormente se eliminan del grafo.

Hallar una o más rutas entre el punto de ramificación y el destino eliminando un

arco a la vez del segmento de la (J - 1)-esima ruta que interconecta el punto de

ramificación y el destino.

Hallar nuevas rutas candidatas dependientes del tallo a las recién calculadas. Si

una de estas no duplica una de las anteriores, se añaden a la cola de prioridad

min.

Una ruta candidata de costo mínimo se elimina de la cola de mínima prioridad

prioridad y se indica como la ruta j-ésima.

4.4.1.1. Descripción formal del Algoritmo KSP Inicialización

Paso 1: Hallar la primera ruta más corta


60

Paso 2: Hallar siguientes rutas

) [ ]

[ ])

) [ ]

) [ ]

[ ]

4.5 Restricciones de cálculo de rutas en GMPLS

Parte de la importancia de GMPLS radica en que los elementos de cálculo de ruta

tomen en cuenta un conjunto de restricciones. Los algoritmos tradicionales no

pueden tratar con la debida suficiencia restricciones relacionadas con inclusión o

exclusión de nodos o enlaces, requerimientos de ancho de banda, capacidad de

conmutación de enlaces, capacidad de protección, entre otras [1].


61

El ente de cálculo se encarga de hallar rutas más cortas que satisfagan un grupo

de restricciones y que compartan el menor número de arcos y nodos. En lugar de

considerar varias restricciones al tiempo, busca las que optimizan el uso de

recursos y satisfagan las necesidades de la mejor manera. Las principales

restricciones consideradas se relacionan con restricciones atributos de enlace y de

ruta, restricciones de exclusión y restricciones de inclusión [1].

4.5.1. Restricciones asociadas con atributos de enlace y de ruta

Un solo valor asociado a la preferencia de enlaces no cobija todas las

restricciones, es necesario considerar arreglos de atributos que contemplen tipo

de protección, Grupos de Enlaces de Riesgo Compartido (SRLGs), capacidad de

conmutación, Tipo de Codificación de datos, entre otros. Los atributos de ruta se

refieren a cualidades de una ruta o segmento que influye en el cálculo; todos los

enlaces que forman una ruta determinan el valor de atributo de ruta. Si una ruta P

se compone de un conjunto de enlaces L, el atributo de ruta será el agregado de

funciones de atributos de enlace. Una expresión genérica válida para el atributo de

una ruta P, con atributos de enlace sería la siguiente:

∑ ( )

Estos atributos de ruta pueden referirse a longitud o retardo de extremo a extremo,

variación de retardo, número de conversiones óptico-electrónicas, entre otros.

Las restricciones de tipo de enlace se abordan inicialmente realizando un recorrido

adicional a través de todos los arcos del grafo, aplicar las funciones de evaluación

especificando atributos del enlace representado por el arco. Si al menos una de

las pruebas no se satisface se debe eliminar el arco del grafo. La ejecución del

algoritmo para hallar dos o más rutas lo más disjuntas posible sobre el grafo

modificado dará como resultado rutas óptimas que cumplen las restricciones

dadas. Las restricciones de tipos de ruta se refieren a condiciones respecto a los

atributos de ruta, son particularmente importante en el ámbito de redes ópticas de

transporte, en las que se requiere un adecuado nivel de señales frente a la

presencia de deficiencias ópticas [1], también son importante al atender

restricciones relacionadas con el problema de superposición de grupos de enlaces


62

de riesgo compartido. Entre las alternativas de manejo de restricciones de ruta se

puede citar las descritas en siguientes subsecciones.

4.5.2. Restricciones asociadas con exclusión e inclusión

Las restricciones de exclusión precisamente están llamadas a excluir del cálculo

enlaces o nodos, se dividen en exclusiones globales, que indican nodos o enlaces

a excluir de cualquier ruta sin importar el orden, y exclusiones globales privadas,

que excluyen enlaces o nodos específicos de rutas específicas. Los algoritmos

basados en la eliminación de enlaces y nodos sólo permiten tratar exclusiones

globales, que son las usualmente consideradas. Por su parte las restricciones de

inclusión plantean el requisito de incluir determinados nodos y/o enlaces. Las

inclusiones privadas indican un orden en relación a nodos y/o enlaces a incluir, y

las inclusiones globales solo incluyen una lista ordenada de nodos. Los algoritmos

básicos aquí tratados sólo son útiles al tratar inclusiones globales, que son las que

usualmente se establecen [1].

Capítulo 5: Cálculo de rutas más cortas en ámbitos restringidos (CSPP) Los conceptos expuestos antes hacen referencia a las ideas básicas de cálculo de

rutas, pero los requerimientos de GMPLS hacen que se piense en el problema de

cálculo de mejores rutas sujetas a las restricciones impuestas, tales restricciones

pueden referirse a una amplia variedad, podrían presentarse, por ejemplo,

restricciones de inclusión o exclusión de conjuntos de nodos, restricciones de

número de saltos, disponibilidad de ancho de banda, limitaciones de retardo,

capacidades de respaldo, entre otras, dando lugar a un inmenso número de


63

posibles problemas. Nuevamente sobra decir que la búsqueda de soluciones al

problema de enrutamiento restringido no es exclusivo del área de las redes de

comunicación de datos, sino que también es aplicable a áreas como planeación de

la producción, toma de decisiones, redes de tráfico de vehículos, transporte de

energía, entre otras, por lo que al igual que los algoritmos presentados antes, las

soluciones se encuentran a partir de bases de conocimiento del ámbito de la

Teoría de Grafos e investigación de operaciones, en donde podemos encontrar

básicamente el enfoque heurístico, cuyo interés es hallar soluciones aproximadas

que satisfagan las necesidades prácticas, y el enfoque exacto o formal, sustentado

en modelos teóricos.

Es tan amplia la diversidad de problemas que cada uno de ellos origina rigurosos y

profundos estudios, encontrándose diferentes propuestas de solución, sin

embargo, todos buscan satisfacer requerimientos de economía en cuanto a

complejidad de tiempo de ejecución y de almacenamiento de la solución y la

eficiencia práctica. En particular, el cálculo de rutas en el contexto de las

modernas redes de transporte de información ha dado lugar a diferentes frentes

de intensas investigaciones, en gran medida marcadas por el interés de proponer

modelos matemáticos que contribuyan en la solución de un conjunto de

subproblemas según necesidades. El problema genérico básicamente consiste en

lo siguiente: a partir de un grafo ), de nodos, enlaces, y un conjunto de

límites de recursos , si además cada enlace utiliza unidades del

recurso , lo que se busca es hallar una o más rutas de menor

costo entre un nodo origen y un nodo destino que satisfaga las limitaciones

de recursos disponibles.

5.1. Estado del arte del CSPP

Un caso específico del cálculo restringido de rutas corresponde a la determinación

de la ruta más corta sujeto a una sola restricción, el cual ha sido estudiado

ampliamente, como se evidencia en [8], [9],[10],[11]. En [12] Jüttner et al dan

tratamiento al problema de enrutamiento con requerimientos de QoS considerando

la restricción de retardo. El tratamiento se basa en un método conocido como

relajación de multiplicadores de Lagrange. La propuesta hace uso del concepto de

costos agregados y brinda un método eficiente para hallar el mejor multiplicador


64

de Lagrange. La ventaja del método es que también brinda un límite inferior de la

solución óptima teórica junto con el resultado. Se reporta que las pruebas dan una

muy pequeñas diferencias entre el límite inferior y el costo de la ruta encontrada,

lo que habla muy bien de la calidad sus resultados, además, mediante sucesivas

aplicaciones del proceso de relajación, se tiene una fácil manera de controlar el

equilibrio entre el tiempo de funcionamiento del algoritmo y la calidad de las rutas

encontradas. Por otra parte en [13] Kuipers el al hacen un estudio detallado de

algoritmos que también atienden el enrutamiento con QoS con una restricción. En

[14] Chen et al, reconociendo que el problema de cálculo de la ruta más

económica en relación al retardo se constituye en un problema NP completo, se

resalta la importancia de las investigaciones que han dado lugar a algoritmos

heurísticos para hallar soluciones aproximadas, particularmente las basadas en

enfoques de discretización del retardo del enlace o costo del enlace. Con base en

ello proponen dos técnicas para reducir el nivel de error introducido en la

discretización, logrando bases para el diseño de algoritmos más rápidos y la

reducción de la sobrecarga de procesamiento. En [15] Santos et al introducen un

algoritmo para cálculo restringido y, pese a ser un problema NP duro, se

demuestra que ciertas instancias del problema en grandes redes se puede

resolver en un tiempo razonable en comparación con las necesidades, comparan

además el desempeño de la propuesta con relajación Lagrangiana y las basadas

en KSP mostrando en ciertos casos significativas ventajas.

El mayor interés en relación con los objetivos del presente trabajo, en razón a los

requerimientos de GMPLS, apunta a los casos de múltiples restricciones, sin

embargo se encuentra pocos resultados que sean lo suficientemente satisfactorio,

bien sea por las limitaciones mismas de la solución propuesta o por su poca

utilidad práctica y bajo desempeño. Por ejemplo, en [16] Xue el al proponen un

algoritmo de tempo de solución aproximadamente polinomial, aplicable al contexto

de enrutamiento con QoS y múltiples restricciones, pero en la práctica presenta la

desventaja de alto tiempo promedio de ejecución.

Siendo relevante considerar la complejidad computacional, en [17] Kuipers et al

destacan la complejidad del problema de enrutamiento basado en múltiples

restricciones y el sinnúmero de investigaciones que ha originado, así como la

creencia de que el enrutamiento exacto de QoS es intratable en la práctica, frente


65

a lo cual se plantea sin embargo que nadie ha estudiado los peores casos que

conducirían a afirmar la intratabilidad práctica del problema, y en cambio

presentan argumentos que apuntan a la posibilidad de lo contrario. Apoyados en la

descripción de condiciones que afectan significativamente la complejidad del

enrutamiento con requerimientos de calidad de servicio, realizan análisis

aproximados y pruebas de simulación. Específicamente consideran que las

condiciones que más significativamente afectan la posibilidad de tratar el problema

son: la topología de la red, la granularidad del ancho de banda de los enlaces la

correlación entre pesos de enlaces y las restricciones. El adecuado tratamiento de

estas condiciones puede llevar en la práctica a hacer más manejable la solución

del problema.

Liu and Ramakrishnan en [18] trabajaron sobre un algoritmo de cálculo de

múltiples rutas más cortas sujeto a múltiples restricciones, el algoritmo se conoce

como A*Prune y se encarga de listar, en orden ascendente según la longitud, las

primeras K rutas sujetas a múltiples restricciones. En cada iteración, el algoritmo

descarta todas las rutas que violan las restricciones, manteniendo únicamente las

que podrían ser clasificadas como factibles, de las cuales finalmente se obtienen

las óptimas. El criterio fundamental de selección se basa en una función obtenida

mediante agregación de costos hasta nodos intermedios basado en el uso del

algoritmo de Dijkstra. Los resultados experimentales muestran que A * Prune es

comparable con los mejores algoritmos basados en aproximaciones conocidos

hasta entonces.

En [19] Hart et al describen fundamentos que indican cómo la información

disponible sobre un contexto o dominio, útil principalmente para el tratamiento

heurístico de la solución del problema, se puede incorporar en el tratamiento

matemático formal generalizado, y se aplica en la formulación de un algoritmo. Al

final demuestra, que bajo ciertas condiciones el algoritmo es óptimo en el sentido

de examinar el menor número de nodos necesarios para garantizar una solución

de mínimo costo. En [20] Li et al documentan una técnica de anticipación de rutas

basado en búsquedas iterativas que usan el número de saltos como la función de

costo.


66

Una interesante línea de investigación la constituye un enfoque basado en

multiplicadores de Lagrange, en el cual inicialmente se resuelve un problema

Lagrangiano Dual (LD) que permite hallar un límite inferior para la ruta óptima,

luego de ello, con el límite superior dado por el costo de una ruta factible, se aplica

un procedimiento orientado a acortar la diferencia entre los límites inferior y

superior. Los primeros aportes en esta línea se deben a Handler y Zang, quienes

en [21] reportan el uso de la versión de Yen del algoritmo KSP [22]. El trabajo

reportado en [23] por Beasley et al es una de las primeras propuestas de la

relajación Lagrangiana en que se considera múltiples restricciones, el problema

LD se resuelve mediante un procedimiento subgradiente mientras que la diferencia

de los límites inferior y superior se acorta mediante tres procedimientos de

búsqueda. En redes de gran tamaño cobra importancia una etapa de pre-

procesamiento con el fin de reducir el tamaño del problema, quizá la más

significtiva propuesta para el caso de una sola restricción fue planteada por por

Dumitrescu y Boland en [24], quienes reportan que el algoritmo de Configuración

de Etiqueta Modificada (MLSA) es competitivamente comparable a al propuesto

por por Beasley y Christofides [23]. Las investigaciones en esta línea siguen

apuntando a la búsqueda de mejoras sobre las diferentes propuestas existentes

con el fin de contar con algoritmos que realicen el cálculo de múltiples rutas más

cortas considerando múltiples restricciones.


67

PARTE III: PLANTEAMIENTO DE MODELOS


68

Capítulo 6. Bases matemáticas asociadas con la solución del CSPP

Con motivo de la realización del presente trabajo, la revisión y análisis de la

bibliografía consultada deja ver diferentes enfoques soportados en diferentes

fundamentos matemáticos para abordar el problema Constrained Shortest Path,

entre los cuales se encuentra, la programación dinámica y la programación lineal

entera. Luego de su análisis con el fin de adoptar una formalización de posibles

aportes de solución del problema, el enfoque que parece ser más atractivo es el

de programación lineal entera razón por la cual este capítulo se dedica a la

revisión de los conceptos relevantes que soportan la propuesta finalmente

presentada.

6.1 Elementos básicos de programación lineal

La programación lineal es un campo de aplicación de principios matemáticos

orientado resolver problemas de optimización asociados con una función objetivo y

un conjunto de restricciones.

6.1.2. Modelo de problemas de programación lineal

El modelo de problemas del ámbito de la programación lineal tiene la siguiente

estructura general [25].


69

Donde algunas de las variables del problema pueden estar obligada a

tomar valores positivos o negativos o no estar limitadas en cuanto a su signo, sin

embargo, es muy usual la exigencia de no negatividad para esta variables. La

variable es una función objetivo de carácter lineal. Las inecuaciones lineales

constituyen un conjunto de restricciones. A una tupla se le

llama solución factible si cumple todas las restricciones establecidas, al conjunto

de todas las soluciones factibles e le llama precisamente conjunto factible o región

factible, por otro lado, la solución factible en la que la función objetivo alcanza su

valor óptimo, máximo o mínimo según lo requerido, recibe el nombre de solución

óptima [25].

Un problema dado de programación lineal podría alcanzar su valor óptimo en una

o varias tuplas del conjunto factible, en el último caso se dice que el problema

tiene múltiples soluciones. También puede darse el caso de problemas que no

tienen solución óptima, bien sea porque el conjunto factible es vacío o porque no

está acotado.

6.1.4. Solución de problemas de programación lineal

Antes de entrar a detallar algunos aspectos de la solución de problemas de

programación lineal resulta conveniente tratar un importante concepto asociado

con ello, el de conjuntos convexos. En el caso de una región del plano de o

una región del espacio intuitivamente se puede ver que el conjunto es

convexo si cualquier par de punto en se puede unir mediante un segmento de

recta totalmente contenido en [25]. Para el espacio , aunque no es posible

representarlo de forma gráfica, formalmente se dice que un conjunto es

convexo si para todo par de tuplas se tiene que el conjunto

está totalmente contenido en [25].

Un importantes resultado de la programación lineal establece que si es un

conjunto convexo cerrado y acotado, la función objetivo asociada con un

problema de programación lineal, toma su valor óptimo en uno de los vértices de

si la función alcanza su óptimo en más de un vértice, también lo alcanza en

cualquier combinación lineal de ellos [25]. En el caso particular de una región

plana cerrada, acotada y convexa esto último significa que, graficando la región


70

plana limitada por las rectas asociadas con las restricciones, solo se debe revisar

el valor de la función en los vértices de la región y ver cuál de ellos es el óptimo.

Un método alternativo se basa en el uso de las curvas de nivel de la función

objetivo , las cuales se obtienen haciendo

donde con lo cual se tiene .

Luego se calcula el vector gradiente de , que es un vector perpendicular a las

curvas de nivel y el sentido del mismo indica la dirección de aumento de la función

objetivo. El gradiente se define en términos de las derivadas parciales de

mediante:

(

*

6.1.5. Solución de problemas de programación lineal. El método simplex

El método Simplex es un procedimiento sistemático usado en programación lineal,

principalmente cuando hay muchas variables y muchas restricciones, se parte del

análisis de un vértice inicial, estudiando si en él se encuentra la solución óptima, si

no hay solución óptima en el vértice, por no ser una región acotada o por ser una

región vacía, con lo cual se tiene una conclusión para el problema. En otro caso se

pasa a otro vértice en el que se mejora el valor de la función objetivo [25].

Generalmente se trabaja con el problema, dado en forma canónica, expresando

las restricciones en forma de matriz, es decir:

Donde


71

(

, (

, (

,

6.1.6. Problema dual de un problema de programación lineal

Con todo problema de programación lineal se encuentra asociado otro problema

conocido como problema dual, de tal manera que si el problema original o primal

es de maximización, entonces el problema dual es de minimización [25].

Específicamente se tiene que si el problema primal es:

El problema dual es:

Donde el superíndice se refiere a la trasposición de matrices.

Entre los fundamentos de programación lineal relacionados con la dualidad

encontramos que el dual de un problema dual el problema primal. Encontramos

también que ambos problemas tienen solución óptima o ninguno de los dos la

tiene. En el primer caso se tiene que las soluciones del primal y dual

respectivamente coinciden, es decir: .

La importancia de la dualidad radica en que a veces es más fácil resolver el

problema dual que el primal y partir de la solución óptima de uno de los problemas

se obtiene información muy importante que conduce a la solución del otro.

6.2. Elementos básicos de programación lineal entera

En el área de la programación lineal, nos podemos encontrar con problemas en

que hay variables limitadas a tomar sus valores de subconjunto de números

enteros, en cuyo caso nos encontramos en el campo de la programación lineal


72

entera [25]. Si la limitación es solo para algunas de las variables tenemos un

problema mixto, si todas las variables deben ser enteras el problema es puro y si

las variables solo pueden tomar los valores 0 y 1 el problema es binario. Un

enfoque válido de solución es resolver el problema de programación lineal

asociado, aquel en el que no se toma en cuenta la condición de valores enteros

para las variables, y si no resulta en soluciones enteras, se prosigue a emplear un

método específico para resolver el problema entero, entre los métodos existentes

para hallar solución de problemas de PLE, se destaca el método de corte o

algoritmo fraccional de Gromory y el método Branch and Bound o ramificación y

acotado [25]. El método de Branch and Bound inicia resolviendo el problema de

programación lineal asociado y verifica si se cumple la condición de valores

enteros para las variables, con lo cual el PLE ya estaría resuelto, en caso contrario

prosigue con una etapa denominada Branch o ramificación, consistente en la

división del problema en dos nuevos problemas, lo cuales se obtienen imponiendo

excluyentes que separan las oportunidades del problema original, pero eliminando

en ambas partes la solución no entera del problema original.

6.2.1. Relajación Lagrangiana

Una parte importante del soporte de desarrollo del presente trabajo considera la

solución de problemas PLE, mediante el procedimiento conocido como Relajación

de Lagrange o Relajación Lagrangiana [25], razón por la cual conviene presentar

los fundamentos más relevantes aquí utilizados. Para la comprensión del método

resulta útil considerar inicialmente la necesidad de resolver el siguiente problema,

en el que A, C, b, c, d tienen entradas enteras:

Sea . Si primero se aborda la búsqueda de la solución

asociada solo con el conjunto se tendrá un grado de dificultad mucho mayor si


73

se considera además la restricción . En esta situación comienza a ser

importante el concurso del método del método de Relajación de Lagrange, el cual

aplica una idea orientada a relajar las complicaciones de las restricciones

incorporándolas en la función objetivo a través del asocio con un parámetro ,

conocido como multiplicador de Lagrange. La reformulación del problema es la

siguiente:

A la anterior formulación se le denomina subproblema Lagrangiano y al mismo se

refiere la siguiente función Lagrangiana del parámetro

La solución del problema definido mediante la función de la ecuación , no

necesariamente resulta ser una solución factible del verdadero problema a

resolver en razón a que se ha eliminado la restricción [25], pero si es cierto

que tal solución brinda importantes luces hacia la búsqueda de la solución del

problema original, tal como se enuncia a continuación.

6.2.2 Límite inferior de la función objetivo

Para cualquier vector de multiplicadores, el valor de la función dada en

es un límite inferior de la función objetivo del problema original definido

mediante , sin embargo, para obtener una mejor cota inferior, es decir un

valor mayor que esté más cerca del valor óptimo del problema original, se puede

hallar el valor máximo de los valores es decir hallar .

El problema de hallar el máximo de se conoce como problema de los

multiplicadores de Lagrange o problema Lagrangiano dual asociado con el


74

problema definido en . Al ser una cota superior, es claro que el máximo de

no supera el valor del óptimo de la función objetivo.

6.2.3. Teorema de relajación Lagrangiana

El teorema que se veremos aquí indica que el mecanismo de la relajación

Lagrangiana [25] se constituye en una posibilidad de solución de problemas de

programación lineal, lo importante de ello es que algunas veces el problema

relajado es mucho más fácil de resolver que el problema original, su enunciado es

el siguiente:

Dado el problema de programación lineal definido por:

Si se aplica el procedimiento de relajación Lagrangiana mediante relajación de la

restricción entonces el valor óptimo es igual al valor óptimo

de la función objetivo del problema

Con el fin de tener una ilustración gráfica de la relajación dual, vemos primero que

la función es cóncava y lineal a trozos, esto en razón a que es el mínimo de

una colección finita de funciones lineales de . Por lo anterior, el problema de

hallar puede ser reformulado como un problema de programación lineal con un

gran número de restricciones. Si es una función diferenciable, el método del

crecimiento de mayor pendiente para la maximización de está dado por la

siguiente secuencia de iteraciones:

( )

Pero en este caso no es diferenciable, lo que conduce a que no siempre

existe el gradiente, por tanto es necesario extender el concepto de gradiente al

caso de funciones cóncavas no diferenciables. El concepto es el siguiente:


75

Sea una función cóncava . Un vector tal que

se denomina subgradiente de en El conjunto de todos los subgradientes de

en se simboliza mediante en . Un importante resultado que establece una

condición necesaria y suficiente para el valor máximo de una función cóncava está

dado en el siguiente lema:

Lema: sea una función cóncava. Un vector maximiza la función

sobre si y solo si 0 pertenece al conjunto de subgradientes de en .

6.2.4. Algoritmo de optimización subgradiente

Con base en los resultados antes señalados, en esta parte se presenta la

extensión del algoritmo de crecimiento de mayor pendiente [25], el cual puede ser

usado para maximizar una función cóncava no diferenciable. Los pasos del

algoritmo son los siguientes:

Paso 1: Seleccionar un vector de inicio

Paso 2: Dado seleccionar un subgradiente de la función en .

Si , entonces es óptimo, con lo cual el algoritmo termina, de lo contrario continuar.

Sea donde es un valor positivo correspondiente a un

tamaño de paso. Incrementar e ir al paso 2.

Generalmente solo se emplea subgradientes extremos. Un típico valor para

está dado por:

‖ ‖

Donde es un estimado del valor óptimo.

En la práctica el criterio de detención raramente se alcanza, por lo que

el algoritmo se hace detener luego de haber realizado un número determinado de

iteraciones.


76


77

Capítulo 7. Modelos formales de solución En relación con la definición del problema se recuerda aquí que dado un grafo

), de nodos , enlaces, y un conjunto de límites asociados

con métricas , en el cual cada enlace consume o se asocia con una

cantidad de la métrica . Lo que se busca es hallar la ruta de

menor costo entre un nodo origen y un nodo destino , de tal manera que se

satisfaga las limitaciones impuestas por la disponibilidad de recursos.

Se recuerda que el modelado del contexto del problema corresponde a un grafo

), de nodos , enlaces . Con cada enlace se asocia un

costo no negativo , así como pesos no negativos donde

. El costo de una ruta y el peso de la misma están dados

respectivamente en términos de las sumas de los costos y los pesos de

los enlaces que componen la ruta [8], [9], esto significa que:

∑

∑

Una ruta desde el nodo hasta el nodo se considera factible si satisface las

restricciones asociadas con los recursos existentes, con lo cual, la

tarea inicial es hallar la ruta más conveniente que satisfaga múltiples restricciones,

se convierte en hallar la mejor ruta factible entre los extremos involucrados.

Mientras que el problema de hallar múltiples rutas entre dos extremos teniendo

que satisfacer múltiples restricciones consiste en hallar un subconjunto de

rutas factibles de menor costo.


78

7.1. Modelamiento del problema usando programación lineal entera

Para efectos de la formulación del problema se define los siguientes términos:

( )

( )

Si para una red de enlaces, se define un vector columna de componentes

mediante ( ( ) ) Se tiene que una ruta simple entre y

queda asociada con un vector que cumple las siguientes condiciones:

∑

∑

∑

∑

Se puede verificar que la expresión (7.2) indica que en cualquier nodo intermedio

un arco saliente de debe estar en la ruta si un arco entrante también está.

Mientras que las expresiones (7.3) y (7.4) indican que debe haber en la ruta un

arco saliente de y uno entrante a

Con base en lo anterior y en otras consideraciones propias de la naturaleza del

problema, se define:

Conjunto de vectores que satisfacen (7.2) a (7.5)

Vector fila de los costos de los enlaces ( )

( ): Vector fila de pesos de los enlaces asociados con el peso

Vector columna de elementos de los pesos límites. Matriz donde la fila es el vector .


79

Con base en lo anterior se presenta la formulación del problema en términos de

programación lineal entera dada a continuación:

{

Un valor representa el costo de una ruta óptima asociada con un A la

luz del método de relajación de Lagrange, y para un vector fila de multiplicadores

de Lagrange no negativos , la tarea de hallar una cota inferior

se transforma en el siguiente problema de relajación de Lagrange.

{

Dado que es constante, el problema se reduce a la consecución de la ruta más

corta con respecto la función longitud de arco asociada con los multiplicadores de

Lagrange, a lo cual le sigue el cálculo del límite inferior con base en la ecuación

(7.6). La correspondiente función longitud de arco está dada por:

∑

Para efectos de simplificación de cálculos asociados con el recorte de la diferencia

entre la cota inferior y la cota superior, lo ideal es contar con un límite inferior lo

más grande posible, esto se logra resolviendo el problema

Si se encuentra una ruta factible mientras se resuelve el problema dual, se

tendrá entonces una cota superior de ya que


80

7.2. Algoritmo para hallar rutas factibles

El algoritmo general que busca resolver el problema JMCSP presentado aquí hace

uso de un procedimiento orientado a la solución del subproblema JFP, que

básicamente consiste en la determinación de un conjunto de J rutas factibles, el

cual no necesariamente contiene las J mejores rutas. La secuencia básica de este

procedimiento, denominado FindFP, se presenta a continuación.

Como se puede ver, el algoritmo FindFP se vale de un procedimiento (Rutas

Factibles – Afinamiento de Dirección), cuyo principal objetivo es hallar un vector de

multiplicadores de Lagrange pero también es posible que encuentre rutas

factibles, FindFP devuelve una variable booleana , el conjunto y el

vector de multiplicadores de Lagrange. Si la variable toma el valor

verdadero, es porque será un conjunto no vacío de rutas factibles, de no ser así

será necesario el uso de un segundo procedimiento (Ruta Factible

Enumeración de Rutas) el cual toma el hallado por con lo que calcularía

un peso asociado al vector de multiplicadores de Lagrange, el peso se define

mediante la expresión:

∑

El procedimiento enumera las rutas más cortas con respecto a hasta hallar

rutas factibles o hasta que se dé una condición de finalización. Este

procedimiento devuelve los parámetros y con igual significado que los

correspondientes a Un interés particular, desde el punto de vista de ahorro

de procesamiento, es el valor de dado por minimice la cantidad de rutas a

enumerar. Los fundamentos de están en la teoría poliedral [26], con base en

la cual nos referimos a una ruta como un punto en una

región factible definida por inecuaciones asociadas con los pesos límites


81

7.2.1. Procedimiento FPDT de afinamiento para el problema JFP

Un importante requerimiento al hallar rutas factibles mediante es contar con el

que permita encontrarse con el menor número de rutas no factibles antes de lograr

el conjunto de rutas factibles o bien que se haya examinado toda la región

factible. Para un dado y un , se denota por es el conjunto de rutas

más cortas con respecto a Para valores grande de lo ideal es tener

conocimiento de la cantidad de rutas a ser enumeradas antes de hallar el número

requerido de rutas factibles, incluso, para pequeños valores de aún se puede

tener información respecto a la probabilidad de que una ruta sea factible. En este

contexto se dice que una ruta es r-factible si para Una

ruta es factible si es r-factible para todo

Si ya se ha hallado el conjunto mediante un algoritmo KSP, se puede hallar la

cantidad de rutas en que son r-factible, con base en lo cual se tiene que la

probabilidad de que una ruta hallada a lo largo de la dirección sea r-factible

está dada por mientras que la probabilidad de que sea factible está

dada por ∏ . Teniendo en cuenta los fundamentos de la distribución de

probabilidad de una variable aleatoria binomial, se encuentra que el valor

esperado del número de rutas factibles es , lo que significa que para minimizar

el número de rutas no factibles se debe maximiza el valor de , lo que en últimas

corresponde a la maximización de . En esto se considera como función objetivo

la referente al mínimo error cuadrático medio normalizado dada a continuación, en

la que es un valor de referencia preestablecido.

∑(

)

Hallar el máximo de significa lo mismo que buscar el mínimo valor de la función

∏ , esta función es cóncava con respecto a cada uno de los

valores de y alcanza su valor mínimo cuando . Cuando la ecuación

(7.9) se transforma en

∑(

*

∑

∑


82

Encontrándose que en la ecuación (7.9) lleva a la maximización de

La conveniencia del uso de la función definida en (7.9) radica en que es una

función simétrica con respecto a los valores de y que el principio de Purkies [27]

garantizan que la solución del problema es a favor de un que hace cada

cercano a . La solución ideal se daría con . El acercamiento de a

resulta en acercamientos a la maximización de Se debe entonces abordar la

búsqueda de la solución de la expresión (7.9) para esto se enfrenta mediante un

procedimiento basado en la técnica gradiente de un paso descendente, en la que

paso a paso se actualiza el valor de partiendo de un valor inicial, el

procedimiento matemático de actualización, en el que se halla un valor a partir

de un anterior, corresponde al dado en la siguiente ecuación:

Siendo un parámetro que controla la agresividad de la búsqueda. El código del

procedimiento es el siguiente:


83

∑

( )

| |

∑(

)


84

En el Paso 0 se selecciona un valor inicial de que pueda dar un bajo valor inicial

de . Las variables y guardan los mejores valores actuales de y de la

función objetivo. En cada iteración el algoritmo compara los respectivos valores y

actualiza si es necesario, en caso contrario, si la diferencia supera un cierto

valor de tolerancia , el valor de se reduce a la mitad y la búsqueda

comienza sobre la mejor solución actual, pero con un tamaño de paso más fino, de

otro modo, la búsqueda continúa con el actual.

En lo referente a la complejidad de tiempo se tiene que esta es de

Lo cual se prueba con base en el algoritmo de Gotthilf

[28], el peor tiempo tomado por es de en cada

iteración para clasificar rutas más cortas. Puesto que y

repite un número fijo de veces en el peor de los casos, se llega al resultado

indicado.

7.2.2. Procedimiento de enumeración para el problema

Si el componente no puede hallar rutas factibles, el algoritmo

usará el procedimiento , el cual mantiene una enumeración de las rutas más

cortas con respecto a los encontrados por hasta hallar rutas factibles o

hasta examinar toda la región factible. Se podría usar con un gran valor de

hasta hallar rutas factibles, sin embargo, en grandes redes esto demandaría

mucho espacio de memoria, por lo que, con fines de enumeración de rutas, se

considera como base el algoritmo propuesto en [24] y aplicar además una prueba

de viabilidad.

El procedimiento contempla inicialmente lo siguiente:

Calcular las longitudes según la ecuación (7.8).

Hallar el árbol inverso de ruta más corta enraizado en con respecto a

Siendo la ruta en desde hasta

Calcular la función de costo reducido ( ) [ ]

Ordenar, ascendentemente respecto a todos los arcos salientes de cada

nodo denotando por el arco saliente de que sigue en el

orden clasificado.


85

Sea la cola de rutas candidatas (que contiene sólo la ruta más

corta).

Luego de la fase inicial, entra en un ciclo, en el cual, si en una cierta

iteración, es la ruta más corta en la cola , el algoritmo elimina de la cola y

luego agrega un conjunto de rutas candidatas que son desviaciones de . Una ruta

candidata desviada de a partir del nodo toma el arco y se escribe,

usando el operador concatenación ⊲⊳, mediante ⊲⊳ ⊲⊳ ,

donde es el tramo de que va desde hasta y un tramo que va

desde hasta el destino En general, la representación de una ruta desviada

de una ruta se puede abreviar como ⌌ ⌍ para un extraído de

y valores de precalculados. Vale la pena indicar, tal como lo sugiere la figura 4,

que nada impide que un nodo en ya se encuentre en el tramo , lo que

significa que algunas de las rutas en la cola no son rutas simples. La lógica

necesidad de trabajar sólo con rutas simples, nos lleva a restringir conjunto de

arcos en que pueden considerarse como puntos de desvió para generar rutas

candidatas.

Los arcos aptos para desviación a partir de una ruta ⌌ ⌍ en , escrita

como . ⊲⊳ ) ⊲⊳ son aquellos arcos en tales que

o es el primer nodo en que aparece en . Inicialmente

y y se pueden escribir como ⌌ ⌍. Cualquier ruta en puede

almacenarse usando espacio, todas ellas se almacenan en lista

encadenada. El pseudocódigo de es el siguiente:

| |


86

( )

( ⊲⊳ ⊲⊳ )

(

)

⌌ ⌍

En los pasos 1 a 14 la actual ruta más corta primero se elimina de la cola y

luego se intenta hallar una ruta candidata mediante desviación. El paso 10 evalúa

la longitud de una potencial ruta candidata desviada por el arco . Si la

longitud es mayor que , se detiene el chequeo de otro nodo saliente del nodo

en razón a que una ruta desviada a través de cualquier arco sucesivo violaría esta

condición ya que los arcos fueron ordenados en orden creciente del costo

reducido. Esto garantiza que cualquier ruta candidata admitida en tiene una

longitud que no supera el valor El paso 11 asegura que el arco a través del

cual la ruta se desvía no va inmediatamente hacia atrás a un nodo precedente.

Los pasos 7 y 12 hacen el chequeo de factibilidad sobre pesos de restricciones.

7.3. Algoritmo para el problema JMCSP

El algoritmo FindFP, basado en los procedimientos y , abordados en la

sección anterior, apunta a la solución del subproblema , consistente en hallar

rutas factibles sujetas a múltiples restricciones. Sin embargo, el problema principal

consiste en hallar las rutas más cortas, entre todas las rutas factibles también

sujetas a múltiples restricciones, este es el problema que se trata en esta

sección. El algoritmo que atiende la solución del problema requiere la

determinación de un conjunto de de rutas factibles de menor costo. La idea en

este punto parte del supuesto que y

son,

respectivamente las rutas más caras y más económicas en el conjunto .


87

Recuérdese que se define como el valor del dominio de tal que

para todo del dominio se tiene , de forma análoga se define

invirtiendo el sentido de la desigualdad. El algoritmo de solución

propuesto halla primero un vector que indique la mejor dirección de búsqueda y

luego enumera las rutas más cortas a lo largo de tal dirección, al tiempo que

gradualmente realiza, lo que en la literatura relacionada se conoce como el cierre

de brecha entre los valores límite y

Como se muestra luego de este párrafo, la lógica básica del algoritmo de solución,

denominado , hace uso del procedimiento , antes descrito, así como de

y , los cuales serán descritos posteriormente. Inicialmente

llama al procedimiento para hallar un conjunto de rutas factibles, lo

que podría dar además la ruta más cara en . Lógicamente, es una cota

superior de por lo cual se somete al procedimiento , que

devuelve el parámetro , que da la mejor dirección de búsqueda, y el parámetro

, que es un límite superior minimizado de Estos dos parámetros se pasan

al procedimiento , que primero calcula un peso Lagrangianizado usando

la ecuación (7.7) y luego enumera las rutas más cortas con respecto a hasta que

se encuentra un conjunto con la tolerancia especificada. La lógica del

algoritmo se muestra en la siguiente secuencia de pasos.

.

7.3.1. Procedimiento de afinamiento para JMCSP

Con el fin de garantizar que en últimas se resuelva el problema JMCSP por parte

de MCSPPE de la forma más eficiente, el devuelto por MCSPDTHi debe dar la


88

mejor dirección de búsqueda, así como un límite inferior maximizado de . No

resulta conveniente el uso del procedimiento en razón a que este ignora el

costo. El pseudocódigo de se presenta a continuación.

En el anterior secuencia las variables y

son respectivamente los actuales

mejores valores de la dirección de búsqueda, cota inferior y cota superior de los

costos de ruta. El valor inicial de es el encontrado por . i

hace a su vez repetitivos llamados a un procedimiento auxiliar de afinamiento

, similar a , cuya finalidad principal es tratar de optimizar los valores

y

. En las diferentes iteraciones se le proporciona diferentes valores de

con el fin de garantizar la búsqueda en diferentes regiones del espacio de

soluciones. El pseudocódigo de es el siguiente.

,

⌊ ⌋

∑

∑(

)


89

En este punto vale la pena destacar las principales diferencias entre

. Inicialmente se señala que, para el caso de , el valor de usado

en la formulación de la función objetivo dada por la ecuación (9), se toma en el

paso 1 como ⌊ ⌋, es decir el piso del producto Puesto que el valor

obtenido de MCSPDTHi está en el rango , debe ser menor que . Por

otro lado el conjunto de rutas más cortas, se halla con respecto a la ecuación

(7.7). Dado que el costo está involucrado, optimizando el único multiplicador para

el caso de una sola restricción no es ya un asunto trivial. MCSPDT se encarga de

esto así como del caso de múltiples restricciones. También se tiene aquí que una

vez hallado , se calcula un límite inferior mediante donde es la

ruta más corta en (La primera dada por ). Si es mayor que la mejor cota

inferior , se actualiza

y mantiene el correspondiente. Además, si en

hay o más rutas factibles se actualiza la mejor cota superior utilizando para

ello la de menor costo en lo que se hace en los pasos 6 a 8. Por último, se

realiza la prueba mediante la cual una ruta con longitud mayor que sería

no factible o tendría un costo mayor que . Lo que permite usar

como la

longitud máxima de ruta en .

Ahora en este punto retomamos las ideas geométricas tratadas en xx para explicar

cómo diferentes valores de se relacionan con los límites inferiores. Para el caso

de una restricción, con el único multiplicador , el peso Lagrangizado de una ruta

es , el cual corresponde a un conjunto de líneas paralelas en el plano

para un cierto valor de . Si por ejemplo establecemos

trataría de encontrar un tal que contenga 50% de las rutas factibles.

Suponiendo que el conjunto de líneas correspondientes a la resultante son

paralelas con la línea AB en la figura. 9(a), el límite inferior sería el valor c del

punto donde AB se cruza con la línea límite (la línea vertical sólida). Si en cambio

se toma , el para un ideal de tendría aproximadamente el 90% de


90

las rutas factibles, este porcentaje mayor de rutas factibles, indica que las líneas

resultantes deben ser paralelo con AB giradas en sentido horario un cierto ángulo,

por ejemplo, ser paralelo con DE. En los casos de menor porcentaje de rutas

factibles, asociados con menores valores de , el resultante correspondería a

un conjunto de líneas paralelas con AB giradas en sentido anti horario por un

ángulo. En cualquier caso se puede encontrar una diferente cota inferior.

Para el caso con dos restricciones. El peso Lagrangianizedo se expresa mediante

, que para un determinado corresponde a un conjunto de

planos paralelos en el espacio . Con , se tendría un valor de

tal que entre las rutas en , 50% de ellas son restricción-1 factible y el otro 50%

son restricción-2 factible. Suponiendo que los correspondientes planos son

paralelos con el plano ABD en la Fig. 9(b). Entonces, en caso que , el

mayor porcentaje de rutas restricción-r factibles necesitadas, el conjunto de planos

que corresponden a la resultante λ estaría en paralelo con ABD girados a lo largo

de la dirección de c por un cierto ángulo (por ejemplo, a ABE). Para valores

menores de los planos serían paralelos con ABD girado en sentido contrario a

la dirección de c por un cierto ángulo. En todo caso, al igual que el caso de una

restricción, se puede encontrar una cota inferior chequeando el valor c del punto

que se encuentra tanto en la línea de límite ( y el primer plano

que toca una ruta cuando se mueve a lo largo de la dirección .

Figura 7. 1: Relación entre h y el límite inferior

Para los casos de tres o más restricciones aunque no es posible

visualizarlo geométricamente, se tendría también que valores muy grandes o muy

pequeños de darían una pequeña cota inferior (ver Fig. 7.1.a como ejemplo), lo

que lleva a pensar en un mejor valor de comprendido entre 0 y para obtener

un límite inferior cercano al óptimo. Si las rutas están uniformemente distribuidas


91

en el área, hay alta probabilidad de que 0.5K sea el mejor valor de . Para el

ejemplo de la Fig. 9 (a), con = podría terminar con cualquiera de las tres

líneas (o cualquiera de los tres planos de la 7.2. b).

Lo anterior sustenta el llamado que se hace del procedimiento por

parte de , iniciando con , y luego considerando valores mayores

y menores dados por , , y así sucesivamente, siendo un

tamaño de paso del orden de las centésimas. En cualquier de las dos direcciones

se detiene si el límite inferior detiene su crecimiento o si está fuera del intervalo

[ ]

7.3.2. Procedimiento MCSPPE de enumeración para el problema JMCSP

El procedimiento de enumeración de rutas , mostrado luego de este

párrafo, trabaja con el valor recibido y calcula primero el peso usando la

ecuación (7) e inicializa en vacío el conjunto . Posteriormente enumera las rutas

más cortas con respecto a . Las rutas factibles encontradas las va añadiendo a

, pero si en ya hay rutas, la actual ruta más cara se reemplaza por la más

reciente encontrada. Esto se realiza hasta agotarse las rutas candidatas en la cola

o se alcanza la tolerancia de optimalidad.

| | | |

| |


92

( )

( ⊲⊳ ⊲⊳ )

( )

⌌ ⌍

Tal como lo muestra el código anterior, en la fase de inicialización, luego de

calcular el peso , se calculan las rutas a la inversa más cortas y la función de

costo reducido con respecto a . Además, el límite superior se aumenta en un

pequeño valor, esto último en razón a que inicia vacío y se debe hallar primero

rutas factibles para llenarlo, además se requiere que todas las rutas admitidas en

tengan costo menor que . En un caso especial, en que hay rutas factibles, el

procedimiento podría pasar por alto algunas que han sido halladas exitosamente

por si no se incrementa el valor de .

En los pasos 3 a 9 se actualizan los valores de y la actual ruta más cara en

. En 10 a 12 se evalúa si está dentro rango de optimalidad dado en función

del valor de y del actual límite inferior. Los pasos 16 y 21 corresponden a un

control basado en el costo adicional que asegura que un ruta en debe tener un

costo inferior a . El paso 19 asegura que una ruta en debe tener una longitud

menor que .

Cuando alcanza rutas factibles por primera vez, se identifica la ruta más cara

en y toma como valor el costo de esa ruta y el procedimiento poda la cola

removiendo todas las rutas cuya longitud supera el valor . Luego se da


93

una secuencia de iteraciones en que la actual en se remplaza por una ruta

en de costo menor y se procede a identificar la nueva ruta más cara en ,

actualiza el valor de y poda . El algoritmo también usa un valor que indica

el máximo número de iteraciones.

Los algoritmos y tienen el mismo peor de los casos de complejidad

de tiempo. Debido a Lemas 3, 5 y 7 podemos concluir que la complejidad del

algoritmo de DT es ). En la práctica, usualmente

elegimos un número para M tal que , haciendo que la complejidad sea

. En comparación con FPPE y MCSPPE, otros procedimientos llamados

por DT sólo utilizan insignificante espacio de memoria. Así, la complejidad del

espacio total de DT sigue siendo

7.4 Algoritmo CSP con una restricción

Una muy interesante propuesta, a la que se refiere aquí como algoritmo CSP y

que atiende el caso de una restricción, se presenta por Lozano y Madaglia en [11].

En el proceso se construye una ruta parcial incluyendo los nodos ya visitados, el

costo acumulado de la ruta está dado por la función objetivo . La lógica del

algoritmo muestra que este registra la totalidad de rutas posibles entre el par de

nodos origen y destino, lo que garantiza el hallazgo de la mejor ruta . La idea

fundamental del algoritmo es la poda, como sucede con otras propuestas, tales

como A*Prune de Liu y R. Ramakrishnan [18]. La fortaleza del algoritmo depnde

de la eficiencia del mecanismo de poda, en [11] se detalla los mecanismos de

dominancia, corte e infactibilidad.

Un procedimiento a partir del Grafo G y la información correspondiente a origen,

destino y restricción, asociado con la solución del problema corresponde a un

procedimiento 1, basado en una función recursiva que inicia a operar luego de la

fase de inicialización de la ruta parcial así como los parámetros de costo y

tiempo se presenta en el siguiente bloque de pseudocódigo.

CSP1


94

Un segundo bloque algorítmico, que hace uso de la función recursiva CSP, la que

cada vez que es llamada al final del nodo la información de la mejor ruta

conocida es registrada globalmente. El algoritmo usa diferentes estrategias de

poda que son descritas en [11]. El correspondiente pseudocódigo se muestra a

continuación.

Posteriormente en este trabajo se muestra resultados de instancias de ejecución de la implementación de este algoritmo como parte de la validación de los fundamentos matemáticos aquí expuestos, en el aparte de Anexos se incluye el código de la implementación.


95

Capítulo 8: Diseño e implementación

8.1. Ajuste de Pseudocódigos de algoritmos de solución

Las pruebas en este trabajo se basan en la simulación de la topología

considerando solo dos restricciones y el cálculo de las tres mejores rutas, con lo

cual el problema JFP consiste en hallar un conjunto de 3 rutas factibles,

contenido en el conjunto de todas las rutas factibles (problema 3FP). Mientras

que el problema JMCSP consiste en hallar el conjunto de las 3 rutas factibles

de menor costo (problema 3MCSP). Con fines de diseño se reduce las

consideraciones iniciales a lo siguiente.

*

+

∑

∑

∑

*

+


96

La factibilidad de la ruta se da si:

∑

∑

( ) : Vector fila de pesos 1 de los enlaces

( ) : Vector fila de pesos 2 de los enlaces

*

+ Matriz con filas y

8.1.1. Pseudocódigo para hallar 3 rutas factibles

8.1.2.1 Pseudocódigo del Procedimiento 3FPDT

(

)

[ ]

( )

| |

((

)

(

)

+


97

[ ]

8.1.2.2. Pseudocódigo del Procedimiento

| |

( ( ) ( )

)


98

( ⊲⊳ ⊲⊳ )

( (

) (

)

)

⌌ ⌍

8.1.2. Pseudocódigo del algoritmo para el problema 3MCSP

.

8.1.2.1. Pseudocódigo del procedimiento MCSPDTHi

8.1.2.2. Pseudocódigo del procedimiento MCSPDT

,

⌊ ⌋


99

[(

⌊ ⌋

⌊ ⌋)

( ⌊ ⌋

⌊ ⌋)

]

[ ]

⌊ ⌋

⌊ ⌋

⌊ ⌋

⌊ ⌋

8.1.2.3. Pseudocódigo del procedimiento MCSPPE

| | | |

| |

( )

( ⊲⊳ ⊲⊳ )


100

( )

⌌ ⌍

8.2 Flujo lógico del sistema

Atendiendo a la lógica de llamado a los procedimientos pseudocodificados, se ve

entonces que la solución, llamada DT hace uso de los bloques, Find3FP,

MCSPDTHi e MCSPPE, pero el bloque FindFP usa el procedimiento de

afinamiento MCSPDT en lugar de MCPDT. La Figura 7.1 muestra una vista de

alto nivel del bloque global, y la figura 7.2 presenta una vista del procedimiento

FindFP. Vale resaltar que los fundamentos matemáticos del algoritmo

corresponden a la implementación del algoritmo KSP (K Shortest Path), el que a

su vez encuentra su elemento básico en el algoritmo de Dijkstra y las

consideraciones de lógica planteadas en el aparte de algoritmos para cálculo de

ruta presentados en el capítulo 4.


101

Figura 8. 1: Bloque para hallar el conjunto de 3 mejores rutas, Hace uso del Procedimiento Find3FP.

Figura 8. 2: Esquema lógico del procedimiento que hallar un conjunto de tres rutas factibles, no necesariamente las mejores.

8.3. Opciones de herramienta de simulación

Atendiendo a la necesidad de implementar pruebas de simulación se considera

diferentes herramientas, las cuales se describen brevemente a continuación.


102

8.3.1. OPNET

Es una herramienta que ofrece una amplia variedad de componentes que brindan

soporte a al modelamiento y simulación de redes de diferentes tecnologías. Sin

embargo se requiere la compra de la licencia apropiada, entre la académica y la

comercial.

OPNET Modeler cuenta con una interfaz gráfica de usuario con editores para la

creación, modificación y verificación de modelos, para la implementación de

simulaciones. Los modelos de simulación son construidos de forma jerárquica.

Entre los niveles con que cuenta están: Nivel de red, para modelar topologías de

red y configuración global; nivel de nodo, considera la estructura interna de los

dispositivos del nivel de red; nivel de procesos, contempla las funcionalidades de

equipos del nivel de nodos.

8.3.2. NS-2

NS-2 es una herramienta de simulación de redes, se basa en el lenguaje de

programación OTcl para definir el escenario de simulación. El núcleo del simulador

es la cantidad de modelos de protocolos de red que han sido escritos en C++, y el

resto está en OTcl. Como el código fuente está disponible hay muchos módulos

externos para NS-2 que por defecto NS-2 no trae y permite el desarrollo de

modelos que son experimentales y que no son soportados por la industria.

El diseño del simulador separa los datos del control por medio del uso de: (i) C++

para datos y (ii) OTcl para el control. En la práctica algunos de los modelos de

protocolos están en OTcl.

8.3.3. Programación en Java.

Las características fundamentales del lenguaje Java lo muestran como una

plataforma de desarrollo con apropiado soporte para las técnicas de desarrollo

OOP y en resumen a la reutilización de componentes de software. El lenguaje ha

sido diseñado para trabajo en entornos de redes contienen una gran biblioteca de

clases para la utilización del protocolo TCP/IP, incluyendo HTTP y FTP. Otra

importante propiedad es que el compilador de Java traduce los archivos de clases


103

a código de bytes, que puede ser interpretado por todas las máquinas que den

soporte a un visualizador de que funcione con Java.

Java es una plataforma cuyo código no se rompe con facilidad frente a errores de

programación. Así la flexibilidad de declaración y manejo de tipos en C y C++ se

torna en restricciones en Java, donde no es posible la conversión forzada (cast) de

enteros en punteros y no ofrece soporte a los punteros que permitan saltarse

reglas de manejo de tipos. Además de lo anterior vale la pena resaltar la seguridad

del lenguaje, lo cual es muy importante al trabajar en entornos de redes.

8.4. Selección de herramienta

Para efecto de la realización de pruebas de los algoritmos el conjunto de

algoritmos, se selecciona como opción de desarrollo de simulación la

programación en Java, utilizando como entorno de desarrollo la herramienta

NetBeans IDE 7.4 usando para ello un computador Intel Core I 5, con 8 GB de

memoria RAM y disco duro de 500 GB. Se opta por esta opción atendiendo las

características descrita anteriormente, su robustez para el desarrollo de

aplicaciones empresariales dada la escalabilidad y flexibilidad que permite un

diseño a través de patrones, portabilidad de la aplicación a través de diferentes

sistemas operativos y arquitecturas, disponibilidad de librerías open source

relacionadas con las necesidades del presente trabajo. La figura 8.3 muestra una

vista de la interfaz inicial del NetBeans y una porción del listado de clases

desarrolladas en lo que concierne al algoritmo KSP.


104

Figura 8.3: Interfaz de desarrollo de NetBeans IDE 7.4


105

Capítulo 9: Evaluación de resultados, trabajos futuros y conclusiones. Para efectos de muestra y evaluación de resultados en el presente trabajo,

inicialmente se presenta un conjunto de instancias de ejecución del algoritmo KSP,

en donde se puede ver elementos gráficos que hacen parte del desarrollo,

mediante lo cual se realiza las pruebas de funcionamiento de las soluciones

planteadas en lo que concierne a esta parte. Posteriormente se presenta

resultados numéricos de la ejecución del algoritmo CSP aquí implementado y su

comparación y análisis frente a otras propuestas debidamente validadas.

9.1. Pruebas del algoritmo KSP

Atendiendo al análisis de requisitos y a los fundamentos matemáticos de los

modelos analizados se encuentra la necesidad de la implementación del algoritmo

KSP para hallar las mejores rutas. La lógica y el pseudocódigo de este algoritmo

fueron presentados en el capítulo 4 y hace parte de los bloques para cálculos con

restricciones presentados anteriormente. Hasta este punto se destaca como

resultado, en favor de la optimización de recursos y del alcance de los objetivos

propuestos, la puesta a prueba del algoritmo que obtiene las tres mejores rutas,

una muestra de ello se da en la Figura 9.1, la que presenta uno de los grafos de

prueba y las tres mejores rutas correspondientes a diferentes pares de nodos

origen destino. Es de aclarar que la aplicación se puede ejecutar con una mayor

cantidad de grafos de prueba, como los mostrados en la Figura 9.2, verificando así

la funcionalidad del algoritmo y la aplicación de los fundamentos matemáticos

esbozados como soporte.


106

Figura 9.1: Grafo de prueba y las tres mejores rutas entre diferentes pares de nodos origen destino

Figura 9.2: Otros grafos de prueba generados por la aplicación

La Figura 9.3 muestra otro caso de ejecución en los que a partir de un grafo, se

obtiene el conjunto de tres mejores rutas entre diferentes pares origen destino.


107

Figura 9.3: Tres mejores rutas en un grafo de 21 nodos

En el aparte correspondiente a Anexos se presenta el código de las clases que

soportan el funcionamiento de esta parte del trabajo.

9.2 pruebas del algoritmo para manejo de restricciones

En lo relacionado con manejo de restricciones se realiza una aplicación CSP

(Constrained Shortest Path) a la cual, a través de una clase principal, se le

proporciona un archivo de configuración que indica el nodo origen, el nodo

destino, la cantidad total de nodos, la cantidad total de arcos, y un valor límite

asociado con una restricción. La estructura original del grafo usado, con 264346

nodos y 733846 arcos, está contenida en otro archivo referenciado por archivo de

configuración, sin embargo el archivo que contiene la estructura del grafo se

puede modificar para que contenga un menor número de nodos y de arcos, con

base en lo cual se realiza las diferentes pruebas aquí señaladas.

Tras la ejecución del algoritmo se obtiene como resultado la información de la ruta

calculada, correspondiente a la secuencia de nodos que la componen y el tiempo

de ejecución empleado. La figuras 9.4 muestra una parte de la salida dada para un

par de nodos origen y destino especificados, también se resalta el tiempo de

ejecución en un recuadro verde. La variable tiempo de ejecución será la que se

tome en cuenta más adelante como criterio de evaluación de la pertinencia del

algoritmo. Las figuras 9.5 a 9.7 muestran resultados de otras ejecuciones con

diferentes nodos de origen y destino.


108

Figura 9.4: Nodo de origen 20, nodo de destino 50

Figura 9.5: Nodo de origen: 1, nodo de destino: 254346

Figura 9.6: Nodo de origen: 100, nodo de destino: 164346

Figura 9.7: nodo de origen: 200, nodo de destino: 5000

Para analizar la validez o pertinencia del algoritmo implementado primero se

compara los resultados aquí obtenidos, relativos a tiempo promedio de ejecución,

con los reportados en [15] por Santos et al. Se aprovecha la posibilidad de ajustar

las cantidades de nodos y arcos en el archivo que define la estructura del grafo,

con lo cual se llevó a cabo instancias de ejecución que permitieran la comparación

con los resultados de [15]. Siguiendo parámetros de evaluación de [15] se usa una

constante de estrechez o coeficiente de restricción, en relación al uso del recurso

este parámetro se define por:

Donde y

son las rutas que respectivamente minimizan costos y consumo de

recursos, mientras que es la función de consumo de recurso de una ruta .


109

Se puede notar, de acuerdo con la correspondiente expresión, que los valores de

están en el intervalo [ ] Valores pequeños de se asocian con mayor presión

o escasez en relación con el uso del recurso mientras que valores mayores

corresponden a mayor flexibilidad o menor es restricciones. Se usa aquí

como valores de para efectos de reportes de resultados de las

pruebas. La tabla 9.1 muestra los resultados obtenidos por el algoritmo CSP

implementado aquí, para diferentes combinaciones de números de números de

nodos y números de arcos y los correspondientes a las instancias reportadas en

[15]. La primera columna de la Tabla 9.1 muestra el número de arcos, la segunda

muestra el número de nodos. Para el valor , las columnas 3, 4 y 5 dan

respectivamente los valores promedios de tiempos de ejecución del algoritmo

, valores promedios de tiempo de ejecución para el algoritmo y la razón

entre los dos valores promedios ( ). Las ternas de columnas 6 a 8 y 9 a 11

dan los valores de las tres mediciones anteriores, pero para los valores de

y respectivamente.

# Nodos # Arcos

CSP LRA LRA/CSP CSP LRA LRA/CSP CSP LRA LRA/CSP

10000 15000 0,00833 0,6 72 0,00833 0,6 72 0,00833 0,6 72

10000 25000 0,01667 0,7 42 0,01667 0,7 42 0,01667 0,7 42

10000 50000 0,01667 1,1 66 0,01667 1,1 66 0,01667 1,1 66

10000 100000 0,03333 1,8 54 0,03333 1,8 54 0,03333 1,8 54

10000 150000 0,05833 2,5 42,8571 0,05833 2,5 42,8571 0,05000 2,8 56

10000 200000 0,05833 2,7 46,2857 0,13333 2,7 20,25 0,06667 2,8 42

20000 30000 0,01667 1,2 72 0,01667 1,2 72 0,01667 1,2 72

20000 50000 0,02500 1,5 60 0,02500 1,5 60 0,02500 1,5 60

20000 100000 0,05000 2,3 46 0,05000 2,3 46 0,05000 2,4 48

20000 200000 0,09167 3,7 40,3636 0,07500 3,7 49,3333 0,10000 3,9 39

20000 300000 0,14167 4,8 33,8824 0,12500 4,9 39,2 0,15833 5 31,57895

20000 400000 0,14167 5,9 41,6471 0,23333 5,9 25,2857 0,15000 6,2 41,33333

40000 60000 0,04167 2,4 57,6 0,04167 2,4 57,6 0,04167 2,4 57,6

40000 100000 0,06667 3 45 0,06667 3 45 0,06667 3,1 46,5

40000 200000 0,10000 4,9 49 0,10000 4,9 49 0,10000 5,1 51

40000 400000 0,17500 7,7 44 0,21667 7,8 36 0,17500 8,3 47,42857

40000 600000 0,24167 10,7 44,2759 0,25833 10,9 42,1935 0,25833 11,7 45,29032

40000 800000 0,32500 13 40 0,43333 13,4 30,9231 0,35833 14,4 40,18605

48,7235

44,8641

49,47542 Tabla 9.1: Comparación de resultados con el algoritmo LRA reportado en [15]


110

Los tres valores de la última fila corresponden a la media geométrica de los

valores de la columna, se considera esta media en lugar de la media aritmética ya

que en general la media aritmética de un conjunto de reales positivos es mayor o

igual que la correspondiente media geométrica, esto evita ser demasiado

optimistas en cuanto a resultados obtenidos a partir de un número relativamente

pequeño de pruebas, con lo que se tiene una comparación más confiable del

factor que relaciona las dos medidas. Con estos resultados se muestra que en

promedio la ejecución del algoritmo para cálculo de rutas con una restricción

es aproximadamente 47,7 veces más rápido que el presentado en [15], sin

embargo, teniendo en cuenta que los resultados de las implementaciones

reportadas en [15] fueron realizadas en un computador Pentium III de un Ghz y

512 K de memoria RAM, según Dongarra [31] y las características del equipo en

que se realizaron las pruebas del algoritmo , se encuentra que este último

equipo es aproximadamente 4,5 veces más rápido que el usado en [15], por lo que

es más acertado decir que en promedio la el factor más apropiado está alrededor

de 10,6 ( ⁄ ), lo cual representa una ganancia significativa frente a un

algoritmo cuya lógica es el producto de propuestas de hace cerca de una década.

La segunda comparación, considerando el tiempo de ejecución del algoritmo para

hallar la mejor ruta, se realiza frente a la propuesta Interactive Search Strategy

Algorithm (ISSA) presentado por Pugliese y Guerriero en [10], quien a su vez

también compara sus resultados con los de Santos et al [15], en la Tabla 9.2 se

muestran los resultados de cinco conjuntos de resultados reportados en [10] y los

obtenidos mediante el algoritmo CSP trabajado aquí, estos son los mismos usados

para la comparación con [15].

Los cinco valores de la última fila corresponden a la media geométrica de los

valores de las respectivas columnas y se usan por las mismas razones que se usó

en el análisis de la comparación con [15]. Según estos resultados se encuentra

que la ejecución del algoritmo para cálculo de rutas con una restricción es en

promedio aproximadamente 28,5 veces más rápido que el presentado en [10], sin

embargo, dadas las características del equipo usado en [10] y las del equipo en

que se montó el algoritmo según Dongarra [31], encontramos que este último

equipo es aproximadamente 3,4 veces más rápido que el de Pugliese [10], por lo

que se puede decir que el promedio la el factor más apropiado es aproximado a


111

alrededor de ( ⁄ ), notándose nuevamente la importancia y pertinencia de

esta propuesta.

# Nod # Arc CSP ISSA 1 Fact ISSA 2 Fact ISSA 3 Fact ISSA 4 Fact ISSA 5 Fact

10000 15000 0,0083 0,087 10,45 0,081 9,78 0,080 9,607 0,080 9,63 0,0830 9,963

10000 25000 0,0167 0,161 9,66 0,156 9,39 0,158 9,480 0,163 9,76 0,1727 10,36

10000 50000 0,0167 0,420 25,20 0,354 21,26 0,346 20,785 0,362 21,69 0,3820 22,92

10000 100000 0,0333 0,769 23,08 0,659 19,77 0,648 19,429 0,706 21,17 0,7689 23,07

10000 150000 0,0583 1,049 17,98 0,982 16,84 1,035 17,745 1,171 20,07 1,3294 22,79

10000 200000 0,0583 1,462 25,06 1,340 22,98 1,434 24,581 1,631 27,97 1,7998 30,86

20000 30000 0,0167 0,300 18,01 0,300 18,01 0,300 17,986 0,296 17,78 0,2962 17,77

20000 50000 0,0250 0,573 22,91 0,565 22,58 0,566 22,658 0,581 23,25 0,6008 24,03

20000 100000 0,0500 1,343 26,87 1,231 24,63 1,246 24,923 1,314 26,28 1,3892 27,78

20000 200000 0,0917 2,867 31,27 2,655 28,96 2,522 27,509 2,784 30,36 2,9632 32,33

20000 300000 0,1417 4,222 29,80 3,796 26,80 3,956 27,924 4,365 30,81 4,8212 34,03

20000 400000 0,1417 5,593 39,48 5,110 36,07 5,318 37,537 5,995 42,32 6,6840 47,18

40000 60000 0,0417 1,337 32,09 1,207 28,96 1,247 29,920 1,276 30,61 1,2909 30,98

40000 100000 0,0667 2,203 33,04 2,202 33,03 2,258 33,875 2,368 35,52 2,4539 36,81

40000 200000 0,1000 5,332 53,32 4,875 48,75 4,892 48,917 5,388 53,88 5,7613 57,61

40000 400000 0,1750 11,232 64,18 9,798 55,99 9,496 54,262 10,611 60,63 11,793 67,39

40000 600000 0,2417 15,951 66,00 14,650 60,62 15,916 65,857 18,384 76,07 23,389 96,78

40000 800000 0,3250 21,266 65,43 20,340 62,59 23,025 70,846 26,647 81,99 29,642 91,21

28,65 26,50 27,021 29,15 31,48

Tabla 9.2: Comparación de resultados con el algoritmo ISSA reportado en [10]

La validación de resultados de este trabajo continua con la realización de una

tercera comparación, tomando en cuenta una restricción, se realiza con los

resultados dados por el algoritmo TSA (three-stage approach) reportados por Zhu

y Wilhelm en [30] quienes ponen a prueban su propuesta TSA a partir de

adaptaciones a de las pruebas realizadas por Beasley y Christofides [23] usando

grafos de 100 a 500 nodos y de 959 959 a 4978 arcos con diferentes costos. Zhu y

Wilhelm [30] definen un valor umbral como el número de instancias resueltas

con el algoritmo de comparación que se requieren para igualar el tiempo total

empleado por su algoritmo TSA. El valor del umbral está dado por:


112

{

Donde y

corresponden a los valores de tiempo empleado por TSA en las

dos primeras etapas, mientras que y son respectivamente los tiempos

promedios que toma una ejecución en la tercera etapa de TSA y el tiempo

promedio del algoritmo de comparación X. Se puede notar, según la definición del

valor de umbral, que si el tiempo promedio de ejecución del algoritmo de

comparación X es menor que el tiempo promedio de la etapa 3 del algoritmo TSA,

se considera que el algoritmo X supera en desempeño al TSA. En el caso de este

trabajo este valor corresponde al número de ejecuciones que podrían ser resueltas

por el algoritmo CSP antes de que comience a valer la pena el uso de TSA.

# de Nodos # de arcos CSP

100 959 0,00051 0,14 0,00016 400

100 959 0,00051 0,13 0,00016 371,428571

100 959 0,00051 0,135 0,00016 385,714286

200 1971 0,0006 0,625 0,00094

200 1971 0,00059 0,516 0,00093

200 1971 0,00058 0,59 0,00093

200 1971 0,00057 0,58 0,00094

500 4978 0,00094 1,094 0,00297

500 4978 0,00099 0,891 0,00187

500 4978 0,001 0,995 0,00245 Tabla 9.3: Comparación de resultados con el algoritmo TSA reportado en [30]

La Tabla 9.3 resume los datos de comparación de desempeño de los algoritmos

CSP y TSA [30], en la columna 6 se observa los valores de umbrales, hallados a

partir de los tiempos empleados por cada una de la etapas del algoritmo TSA,

según se reporta en [30] (columnas 4 y 5) los tiempos empleados por el algoritmo

CSP (columna 3). Atendiendo a la definición y significado del valor de umbral, el

valor en 7 de las 10 entradas en la tabla, indican, que sin importar el número de

problemas resueltos, la duración de las ejecuciones de CSP en esos caso siempre


113

es menor que el de TSA, mostrando con cierta claridad mayor eficiencia de CSP

sobre TSA.

Aprovechando el mismo escenario de prueba con el algoritmo TSA, La Tabla 9.4

muestra los datos que permiten comparar los resultados dados por el algoritmo

CSP con el algoritmo LSA (Labeling and Scaling Algorithms) de Dumitrescu y

Boland [24]. Las dos primeras columnas muestran los números de nodos y

números de arcos de las pruebas, las columnas 3 y 4 muestran respectivamente

los promedios de tiempos de ejecución de las diferentes instancias de pruebas

dados por LSA y CSP. La columna 5 muestra el factor de mejoría de rapidez de

ejecución de CSP frente a LSA, el cual se obtiene dividiendo el tiempo de LSA por

el de CSP. Según lo anterior se tiene entonces que el algoritmo CSP

implementado en el desarrollo de este trabajo es más rápido que el LSA [24] en un

factor que se encuentra entre 6,06 y 9,8, siendo mayor la mejoría en casos de

redes de menor tamaño. Al igual que la primera comparación reportada aquí, se

tiene en cuenta que los resultados obtenidos en [24] se dieron en un equipo Intel

Dual core de 3.2 GHz y 2 GB de memoria RAM, según Dongarra [31] y las

características del equipo en que se implementó CSP, se encuentra que este

último es aproximadamente 4 veces más rápido que el usado por [24], por lo que

resulta prudente afirmar que CSP es más rápido en un factor que se encuentra

entre 1,5 y 2,4, lo que representa una mejora significativa frente a un algoritmo

que en su aparición marco un importante salto en la solución del problema.

# de Nodos # de arcos LSA CSP Factor (LSA/ CSP)

100 959 0,005 0,00051 9,80392157

100 959 0,005 0,00051 9,80392157

100 959 0,005 0,00051 9,80392157

200 1971 0,005 0,0006 8,33333333

200 1971 0,004 0,00059 6,77966102

200 1971 0,006 0,00058 10,3448276

200 1971 0,006 0,00057 10,5263158

500 4978 0,006 0,00094 6,38297872

500 4978 0,006 0,00099 6,06060606 Tabla 9.4: Comparación de resultados con el algoritmo LSA


114

9.3 Trabajos futuros

Se considera que a futuro se debe continuar con la revisión de fundamentos de

optimización, que permitan continuar explorando el universo de posibilidades en

cuanto a mejora de algoritmos de cálculo de ruta que consideren mayor número

de restricciones. El fin es mejorar el desempeño de los algoritmos y que tales

mejoras sean tenidas en cuenta como posibles incorporaciones en los protocolos

de agentes de cálculo de rutas en ambientes reales. Es mucho lo que sigue por

investigar en cuanto a la optimización, más si se tiene en cuenta la creciente

demanda por parte de las redes de usuarios.

Dada la complejidad del problema de cálculo de rutas en ámbitos restringido,

también se debe continuar con el enfoque heurístico, de tal manera que si bien

este no produce optimalidad total, esto se puede compensar con la notable

disminución en tiempo de ejecución y uso de recursos de procesamiento del

sistema.

9.4. Conclusiones

El marcado desarrollo y evolución de las tecnologías de transmisión a través de

fibra óptica ha ido de la mano de la creciente demanda de capacidad por parte de

los usuarios de la internet, lo que a su vez ha traído la necesidad de desarrollo de

tecnologías que sean capaces de aprovechar lo más posible las capacidades que

ofrece la fibra óptica como medio de transmisión. En este orden de ideas a través

de este trabajo, además de introducir el marco contextual de las redes de

comunicación modernas, se resalta la necesidad de optimización de los recursos

asociados con la infraestructura tecnológica de los ISP y su funcionamiento. Lo

anterior ha conducido al análisis del problema de cálculo de mejores rutas, viendo

en ello que en buena medida las investigaciones y desarrollos alrededor de tal

problema están marcados por el uso de fundamentos matemáticos propios del

área de investigación de operaciones y consideraciones que atañen la complejidad

de solución del mismo, lo que hace parte de las ciencias de la computación.


115

La solución del problema de cálculo de mejores rutas en ámbitos restringidos,

como es el caso de las redes GMPLS, ha dado y seguirá dando lugar a la

búsqueda de formulaciones o modelos matemáticos que soporten diferentes

propuestas de solución, que atiendan problemas del núcleo general, pero con

características particulares. Se puede encontrar situaciones en las que se debe

atender con mayor énfasis las necesidades de rutas de respaldo frente a la falla

de rutas principales, o se puede privilegiar la optimización de combinaciones de

diferentes métricas tales como requerimientos de ancho de banda, la

confiabilidad, el costo, la probabilidad de bloqueo, la variación del retardo, entre

otras, lo que sustenta la necesidad de principios de optimización como algunos de

los señalados aquí.

El propósito principal del presente trabajo fue el planteamiento de un modelo

matemático que caracterice el enrutamiento en redes GMPLS considerando la

necesidad de optimización de recursos, su directa relación con el control de las

métricas de enrutamiento y el mejor aprovechamiento de las posibilidades de

transmisión a través de la fibra óptica. En este sentido se ha estudiado con

importante nivel de detalle el problema de cálculo de múltiples rutas sujeto a

múltiples restricciones llegando a ver que las más importantes líneas de solución

se dan a partir de formulación de problemas de programación lineal entera. Se ha

llegado a la implementación de un bloque algorítmico que realiza la búsqueda de

las tres mejores rutas y otro que realiza el cálculo de rutas considerando una

restricción. Con base en lo cual se puede afirmar que en relación a la pregunta de

investigación planteada en el anteproyecto de este trabajo, (¿Están claramente

definidos los referentes que, con fines de optimización de recursos, caracterizan

matemáticamente la funcionalidad de enrutamiento de las redes GMPLS?), se

puede afirmar que existen notables fundamentos que abordan su solución pero en

definitiva no es un problema totalmente resuelto y, en razón a las crecientes

demandas a las tecnologías, muy seguramente no se llegará a la solución

definitiva, sino que por el contrario siempre habrá variantes que darán lugar a

tareas investigativas, que lleven a sus desarrolladores a empaparse de la

naturaleza de problema general y los principales fundamentos de soporte de

solución.


116

Como consecuencia de la elaboración del presente trabajo se ha tenido el pretexto

para realizar un juicioso análisis de diferentes propuestas de solución a problemas

de cálculo de rutas, lo que proporciona los elementos para abordar la adaptación

de propuestas de solución a una situación particular, específicamente se tiene los

siguientes logros.

Se presenta una descripción de los fundamentos de la tecnología GMPLS,

precedida de la evolución de las tecnologías de transmisión a través de

fibra. Destacando en ello sus exigentes requerimientos y la necesidad de

creación de protocolos que particularmente atiendan las necesidades de

optimización de recursos.

Implementación de una versión del algoritmo KSP con base en los bloques de

Pseudocódigo y fundamentos matemáticos analizados. El algoritmo calcula las

tres mejores rutas para diferentes pares de extremos a partir de un grafo

generado por la misma aplicación. La validez del cálculo es soportado por los

fundamentos matemáticos subyacentes.

Implementación de un algoritmo de cálculo de rutas considerando una

restricción. La validez del cálculo está soportada por los fundamentos

matemáticos subyacentes, de tal manera que la evaluación de resultados se

centra en el tiempo de ejecución requerido para realizar el cálculo. Los

resultados obtenidos se comparan con los reportados en varias de las

referencias analizadas y se encuentra que el algoritmo implementado es en

general más rápido que los usados como referencia de comparación.


117

Adaptación de un algoritmo a partir de formulaciones de modelos de la

programación lineal entera, el cual permite establecer criterios de ajustes de la

capacidad de la infraestructura física de tal manera que se tenga ganancias en

optimización. El algoritmo combina la técnica de relajación de Lagrange con

un método basado en clasificación de rutas para encontrar múltiples rutas

más cortas sujetas a múltiples restricciones aditivas. El algoritmo se centra

en reconocimiento de que los multiplicadores de Lagrange utilizado en el

procedimiento de enumeración ruta debe no sólo dar un casi optimizado

límite inferior, sino lo más importante, debe dar la mejor dirección de

búsqueda que haría minimizar el número de rutas no factibles encontradas.

Se tiene además el reconocimiento de la necesidad de considerar diferentes

variantes del problema de cálculo de rutas y el consecuente requerimiento de

abordar contenidos para modelar situaciones cuya solución privilegien unas

métricas sobre otras, esto se refuerza o evidencia a través de la validación

realizada mediante la implementación y prueba del algoritmo, el modelo que lo

soporta valida una situación particular. Los valores obtenidos en la simulación

podrían respaldar el ajuste de elementos de la infraestructura lógica y física de

la red.

Aunque el estado del arte del tema trabajado cuenta con numerosos estudios que

abordan el problema general de cálculo de rutas en entornos restringidos y en

particular su aplicación a las redes de comunicación, el desarrollo de este trabajo

se constituye en un mínimo aporte a nuestra comunidad académica.

El desempeño del algoritmo presentado tal vez no se encuentra dentro de los

rangos deseados, como para ser tenido en cuenta como parte de la

implementación de protocolos en el ámbito de GMPLS, sin embargo representa un

sincero intento y aplicación de grandes esfuerzos de investigación que dejan ver

que el problema tratado está lejos de ser resuelto. El algoritmo se verificó a través

de experimentos simulados logrando poner a prueba la aplicación de

formulaciones matemáticas en problemas de redes de comunicación.


118

Referencias [1] Ferrel, A., Bryskin I (2006). GMPLS Architecture and Applications. The

Morgan Kaufmann Publishers.San Francisco, CA

[2] RFC: 3945 Generalized Multi-Protocol Label Switching. (GMPLS) Architecture

[3] Ramaswami, K. Sivarajan, G. Sasaki. Optical Network. A practical Perspective.

Third Edition (2010)

[4] G. A. Puerto L. Redes de conmutación de paquetes ópticos basadas en el

intercambio de etiquetas multiplexadas por subportadora. Tesis Doctoral

Universidad de Valencia 2007.

[5] Á. Belda Angela (2002). Arquitectura GMPLS, Generalized Multiprotocol Label

Switching.R.

[6] R. Bustos. Evaluación de la complejidad a variaciones del algoritmo Dijkstra

sobre arquitectura Path Computation Element (PCE) en ambientes GMPLS.

[8] M. Ziegelmann, “Constrained shortest paths and related problems”, Ph.D.

dissertation, Universität des Saarlandes, 2001.

[9] P. Festa. Constrained shortest path problems: state-of-the-art and recent

advances. Department of Mathematics and Applications, University of Napoli

FEDERICO II, Italy.

[10] L. D. P. Pugliese “Models and Methods for the Constrained Shortest Path Problem and its variants,” Networks, nov. 2010.

[11] L. Lozano and A. L. Medaglia, “On an exact method for the constrained

shortest path problem,” Comp. & Oper. Res., vol. 40, no. 1, 2013.


119

[12] A. Jüttner, B. Szviatovszki, I. Mëcs and Z. Rajkö, “Lagrange relaxation based

method for the QoS routing problem,” INFOCOM, 2001.

[13] F. Kuipers, P. V. Mieghem, T Korkmaz, and M. Krunz, “An overview of

constraint-based path selection algorithm for QoS routing,” IEEE Comm. Mag.,

2002.

[14] S. Chen, M. Song and S. Sahni, “Two techniques for fast computation of

constrained shortest paths,” IEEE/ACM Trans. Networking, vol. 16, no. 1, 2008.

[15] L. Santos, J. Coutinho-Rodrigues and J. R. Current, “An improved solution

algorithm for the constrained shortest path problem,” Transport. Res. Part B:

Method., vol. 41, no. 7, 2007.

[16] G. Xue, W. Zhang, J. Tang, and K. Thulasiraman, “Polynomial time

approximation algorithms for multi-constrained QoS routing,” IEEE/ACMTrans.

Networking, vol. 16, no.3, 2008.

[17] F.A. Kuipers and P. Van Mieghem, “Conditions that impact the complexity of

QoS routing,” IEEE/ACM Trans. Networking, vol. 13, no. 4, 2005.

[18] G. Liu and R. Ramakrishnan, “A*prune: An Algorithm for Finding K Shortest

Paths Subject to Multiple Constraints,” INFOCOM, 2001.

[19] P. E. Hart, N. J. Nilsson and B. Raphael, “A formal basis for the heuristic

determination of minimum cost paths,” IEEE Trans. Sys.Sci. and Cyber., vol. 4, no.

2, 1968.

[20] Y. Li, J. Harms and R. Holte, “Fast exact multiconstrained shortest path

algorithms,” IEEE ICC, 2006.

[21] G. Y. Handler and I. Zang, “A dual algorithm for the constrained shortest path

problem,” Networks, vol. 10, no. 41980.


120

[22] J. Y. Yen, “Finding the K shortest loopless paths in a network,” Management

Sci., vol. 17, no.11, 1971.

[23] J. Beasley and N. Christofides, “An algorithm for the resource constrained

shortest path problem,” Networks, vol. 19, no. 4, 1989.

[24] I. Dumitrescu and N. Boland, “Improved preprocessing, labeling and scaling

algorithm for the weight-constrained shortest path problem,” Networks, vol. 42,

2003.

[25] A. Schrijver, Theory of Linear and Integer Programming, John Wiley, 1986.Y.

[26] Aneja, V. Aggarwal, and K. Nair, “Shortest chain subject to side Conditions,”

Networks, vol. 13, 1983.

[27] M. Desrochers and F. Soumis, “A generalized permanent labeling algorithm for

the shortest path problem with time windows,” Info.Sys. and Oper. Res., vol. 26,

1988.

[28] Z. Gotthilf and M. Lewenstein, “Improved algorithms for the k simple shortest

paths and the replacement paths problems”, Inf. Process. Lett., vol. 109, 2009

[29] D. Eppstein, “Finding the k shortest paths,” SIAM J. Computing, vol. 28, 1998.

[30] Zhu X. Wilhelm WE A three-stage approach for the resource constrained

shortest path as a subproblem in column generation. Computers & Operations

Research. 2012]

[31] Donagarra JJ. Performanceof various computers using standard linear

equations software. Technical report CS-89-85. University of Tennessee, USA:

2009.


121

PARTE IV: ANEXOS


122

Codificación de clases para el algoritmo KSP Kshortestpath.java import java.util.Comparator; import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map; import KSP.algorithms.shortestpath.ShortestPathAlgorithm; import org.apache.commons.collections15.ListUtils; import org.apache.commons.collections15.Transformer; import org.apache.commons.collections15.functors.MapTransformer; import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath; import edu.uci.ics.jung.graph.DirectedOrderedSparseMultigraph; import edu.uci.ics.jung.graph.Graph; import edu.uci.ics.jung.graph.util.EdgeType; public class SuurballeTarjan<V, E> extends ShortestPathAlgorithm<V, E> { public SuurballeTarjan(Graph<V, E> graph, Transformer<E, Number> nev) { this(graph, nev, null); } private final Comparator<E> defaultComparator = new Comparator<E>() { @Override public int compare(E o1, E o2) { return o1.equals(o2) ? 0 : 1; } }; private final Comparator<E> comparator; public SuurballeTarjan(Graph<V, E> graph, Transformer<E, Number> nev, Comparator<E> comparator) { super(graph, nev); if (comparator == null) this.comparator = defaultComparator; else this.comparator = comparator; } public List<List<E>> getDisjointPaths(V source, V target) { if (dijkstra.getDistance(source, target) == null) return null; // target is not reachable! List<E> sp = dijkstra.getPath(source, target); Map<V, Number> lengthMap = dijkstra.getDistanceMap(source); Transformer<E, Double> lengthTrans = lengthTransformation(graph, MapTransformer.getInstance(lengthMap)); Graph<V, E> revG = reverseEdges(graph, sp); DijkstraShortestPath<V, E> revDijkstra = new DijkstraShortestPath<V, E>( revG, lengthTrans); if (revDijkstra.getDistance(source, target) == null) { List<List<E>> result = new LinkedList<List<E>>(); result.add(sp); return result; }


123

List<E> revSp = revDijkstra.getPath(source, target); validate(source, target, sp, graph); validate(source, target, revSp, revG); LinkedList<E> spCopy = new LinkedList<E>(sp); List<List<E>> paths = findTwoWays(sp, revSp); if (paths == null) { LinkedList<List<E>> result = new LinkedList<List<E>>(); result.add(spCopy); return result; } for (List<E> path : paths) validate(source, target, path, graph); return paths; } private void validate(V source, V target, List<E> path, Graph<V, E> graph) throws AssertionError { if (!graph.isSource(source, path.get(0))) throw new AssertionError("invalid source"); Iterator<E> it = path.iterator(); E e1 = it.next(); while (it.hasNext()) { E e2 = it.next(); if (!graph.isSource(graph.getDest(e1), e2)) throw new AssertionError("invalid path"); e1 = e2; } if (!graph.isDest(target, path.get(path.size() - 1))) throw new AssertionError("invalid destination"); } private List<List<E>> findTwoWays(List<E> path1, List<E> path2) { final V source = graph.getSource(path1.get(0)); final V target = graph.getDest(path1.get(path1.size() - 1)); Iterator<E> it1 = path1.iterator(); while (it1.hasNext()) { E e1 = it1.next(); Iterator<E> it2 = path2.iterator(); while (it2.hasNext()) { E e2 = it2.next(); if (comparator.compare(e1, e2) == 0) { // for multigraph if (graph.isSource(source, e1) || graph.isSource(source, e2) || graph.isDest(target, e1) || graph.isDest(target, e2)) return null; // Removing required edge it1.remove(); it2.remove(); break; // inner loop } } }


124

if (path1.isEmpty() || path2.isEmpty()) return null; // no disjoint solution found List<E> union = ListUtils.union(path1, path2); // concatenate List<E> p1 = recombinePaths(path1, target, union); if (p1 == null) return null; List<E> p2 = recombinePaths(path2, target, union); if (p2 == null) return null; if (!union.isEmpty()) throw new AssertionError("BUG"); List<List<E>> solution = new LinkedList<List<E>>(); solution.add(p1); solution.add(p2); return solution; } private List<E> recombinePaths(List<E> path, V target, List<E> union) { LinkedList<E> p = new LinkedList<E>(); // provides getLast p.add(path.get(0)); union.remove(path.get(0)); V curDest; while (!(curDest = graph.getDest(p.getLast())).equals(target)) { boolean progress = false; for (E e : union) if (graph.isSource(curDest, e)) { p.add(e); progress = true; union.remove(e); break; } if (!progress) return null; if (union.isEmpty()) { if (!graph.isDest(target, p.getLast())) { throw new AssertionError("bug"); } else break; } } return p; } private Graph<V, E> reverseEdges(Graph<V, E> graph, List<E> path) { if (graph == null || path == null) throw new IllegalArgumentException(); Graph<V, E> clone = new DirectedOrderedSparseMultigraph<V, E>(); for (V v : graph.getVertices()) clone.addVertex(v); for (E e : graph.getEdges()) clone.addEdge(e, graph.getEndpoints(e));


125

for (E link : path) { V src = clone.getSource(link); V dst = clone.getDest(link); clone.removeEdge(link); clone.addEdge(link, dst, src, EdgeType.DIRECTED); } return clone; } private Transformer<E, Double> lengthTransformation(Graph<V, E> graph1, Transformer<V, Number> slTrans) { Map<E, Double> map = new HashMap<E, Double>(); for (E link : graph1.getEdges()) { double newWeight = nev.transform(link).doubleValue() - slTrans.transform(graph1.getDest(link)).doubleValue() + slTrans.transform(graph1.getSource(link)).doubleValue(); map.put(link, newWeight); } return MapTransformer.getInstance(map); } } Eppstein.java package KSP.algorithms.shortestpath.ksp; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Set; import org.apache.commons.collections15.Transformer; import org.apache.commons.collections15.functors.MapTransformer; import edu.uci.ics.jung.graph.Graph; public class Eppstein<V, E> extends KShortestPathAlgorithm<V, E> { public Eppstein(Graph<V, E> graph, Transformer<E, Number> nev) { super(graph, nev); } private final class WeightedPath implements Comparable<WeightedPath> { private final Set<V> path_vertices; private final List<E> path_edges; private double weight; private V lastV; public WeightedPath(V start) { weight = 0.0; path_edges = new LinkedList<E>(); path_vertices = new HashSet<V>(); path_vertices.add(start); lastV = start; } public WeightedPath(WeightedPath copy) {


126

weight = copy.weight; path_edges = new LinkedList<E>(copy.path_edges); path_vertices = new HashSet<V>(copy.path_vertices); lastV = copy.lastV; } public void addHop(E via, Double weight, V v) { this.weight += weight; path_edges.add(via); path_vertices.add(v); lastV = v; } public V getLast() { return lastV; } public boolean contains(V v) { return path_vertices.contains(v); } public List<E> getPath() { return path_edges; } @Override public int compareTo(WeightedPath o) { if (weight < o.weight) return -1; else if (weight > o.weight) return 1; int sizeDiff = path_edges.size() - o.path_edges.size(); if (sizeDiff < 0) return -1; else if (sizeDiff > 0) return 1; return 0; } @Override public String toString() { return path_vertices + ";" + path_edges + ";" + weight; } } private Transformer<E, Double> prepareTransformations(V target) { Map<V, Double> lengthMap = new HashMap<V, Double>(); // d(x, t) Map<E, Double> edgeMap = new HashMap<E, Double>(); for (V v : graph.getVertices()) { Number dist = dijkstra.getDistance(v, target); if (dist != null) // target is reachable from v. lengthMap.put(v, dist.doubleValue());


127

else { // Block edges from or to unreachable vertices. for (E e : graph.getIncidentEdges(v)) edgeMap.put(e, Double.POSITIVE_INFINITY); } } for (E e : graph.getEdges()) { if (edgeMap.get(e) == null) { // Only consider edges to reachable vertices. double l = nev.transform(e).doubleValue() /* l(e) */ + lengthMap.get(graph.getDest(e)) /* d(head(e), t) edgeMap.put(e, l); } } return MapTransformer.getInstance(edgeMap); } @Override protected List<List<E>> getShortestPathsIntern(V source, V target, int k) { PriorityQueue<WeightedPath> prioQ = new PriorityQueue<WeightedPath>(); List<List<E>> found_paths = new LinkedList<List<E>>(); Transformer<E, Double> delta = prepareTransformations(target); prioQ.add(new WeightedPath(source)); while (!prioQ.isEmpty() && found_paths.size() < k) { WeightedPath curPath = prioQ.poll(); // get & remove next shortest V curV = curPath.getLast(); if (curV.equals(target)) { found_paths.add(curPath.getPath()); continue; } for (V nextV : graph.getSuccessors(curV)) { if (curPath.contains(nextV)) continue; // Prevent looping! for (E e : graph.findEdgeSet(curV, nextV)) { if (Double.isInfinite(delta.transform(e))) continue; // Skip unreachable vertices. WeightedPath tmpPath = new WeightedPath(curPath); tmpPath.addHop(e, delta.transform(e), nextV); prioQ.add(tmpPath); } } } return found_paths; } } KShortestPathAlgorithm.java package KSP.algorithms.shortestpath.ksp;


128

import java.util.ArrayList; import java.util.List; import KSP.algorithms.shortestpath.ShortestPathAlgorithm; import org.apache.commons.collections15.Transformer; import edu.uci.ics.jung.graph.Graph; public abstract class KShortestPathAlgorithm<V, E> extends ShortestPathAlgorithm<V, E> { protected KShortestPathAlgorithm(Graph<V, E> graph, Transformer<E, Number> nev) { super(graph, nev); } public final List<List<E>> getShortestPaths(final V source, final V target, int k) { if (k < 1) throw new AssertionError(); if (check(source, target)) return new ArrayList<List<E>>(); // Let concrete implementation calculate paths. return getShortestPathsIntern(source, target, k); } private boolean check(V source, V target) { if (!graph.containsVertex(source) || !graph.containsVertex(target)) throw new AssertionError( "The source or the target node does not exist!"); return source.equals(target); } } Yen.java package KSP.algorithms.shortestpath.ksp; import java.util.ArrayList; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.PriorityQueue; import java.util.Set; import org.apache.commons.collections15.ListUtils; import org.apache.commons.collections15.Predicate; import org.apache.commons.collections15.Transformer; import edu.uci.ics.jung.algorithms.filters.EdgePredicateFilter; import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath; import edu.uci.ics.jung.graph.Graph; public class Yen<V, E> extends KShortestPathAlgorithm<V, E> { public Yen(Graph<V, E> graph, Transformer<E, Number> nev) { super(graph, nev); } private final class WeightedPath implements Comparable<WeightedPath> { private final List<E> path;


129

private final double weight; public WeightedPath(List<E> path) { this.path = path; double tmp = 0.0; for (E e : path) tmp += nev.transform(e).doubleValue(); this.weight = tmp; } public List<E> getPath() { return path; } @Override public int compareTo(WeightedPath o) { if (weight < o.weight) return -1; else if (weight > o.weight) return 1; // from here on equal weight int sizeDiff = path.size() - o.path.size(); if (sizeDiff < 0) return -1; else if (sizeDiff > 0) return 1; return 0; } @Override public String toString() { return path + ";" + weight; } } @Override protected List<List<E>> getShortestPathsIntern(final V source, final V target, int k) { LinkedList<List<E>> found_paths = new LinkedList<List<E>>(); PriorityQueue<WeightedPath> prioQ = new PriorityQueue<WeightedPath>(); DijkstraShortestPath<V, E> blockedDijkstra; if (dijkstra.getDistance(source, target) == null) return found_paths; found_paths.add(dijkstra.getPath(source, target)); while (found_paths.size() < k) { List<E> curShortestPath = found_paths.getLast(); int maxIndex = curShortestPath.size(); for (int i = 0; i < maxIndex; i++) { List<E> head = curShortestPath.subList(0, i /* excluded */); V deviation = head.isEmpty() ? source : graph.getDest(head .get(i - 1));


130

Graph<V, E> blocked = blockFilter(head, deviation, found_paths); blockedDijkstra = new DijkstraShortestPath<V, E>(blocked, nev); Number dist = blockedDijkstra.getDistance(deviation, target); if (dist == null) continue; List<E> tail = blockedDijkstra.getPath(deviation, target); List<E> candidate = new ArrayList<E>(i + tail.size()); candidate.addAll(head); candidate.addAll(tail); boolean duplicate = false; for (WeightedPath path : prioQ) if (ListUtils.isEqualList(path.getPath(), candidate)) { duplicate = true; break; } if (!duplicate) prioQ.add(new WeightedPath(candidate)); } if (prioQ.isEmpty()) break; // We have not found any new candidate! else found_paths.add(prioQ.poll().getPath()); } return found_paths; } private Graph<V, E> blockFilter(List<E> head, V deviation, List<List<E>> foundPaths) { final Set<E> blocked = new HashSet<E>(); for (E e : head) for (E e2 : graph.getIncidentEdges(graph.getSource(e))) blocked.add(e2); for (List<E> path : foundPaths) if (path.size() > head.size() && ListUtils .isEqualList(path.subList(0, head.size()), head)) for (E e : path) if (graph.isSource(deviation, e)) { blocked.add(e); break; // Continue with next path. } EdgePredicateFilter<V, E> filter = new EdgePredicateFilter<V, E>( new Predicate<E>() { @Override public boolean evaluate(E e) { return !blocked.contains(e); } }); return filter.transform(graph);


131

} } ShortestPathAlgorithm.java package KSP.algorithms.shortestpath; import java.util.Map; import org.apache.commons.collections15.Transformer; import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath; import edu.uci.ics.jung.algorithms.shortestpath.ShortestPath; import edu.uci.ics.jung.graph.Graph; public abstract class ShortestPathAlgorithm<V, E> implements ShortestPath<V, E> { protected final Graph<V, E> graph; protected final DijkstraShortestPath<V, E> dijkstra; protected final Transformer<E, Number> nev; protected ShortestPathAlgorithm(Graph<V, E> graph, Transformer<E, Number> nev) { if (graph == null) throw new IllegalArgumentException("No graph given"); if (nev == null) throw new IllegalArgumentException(); this.graph = graph; this.nev = nev; this.dijkstra = new DijkstraShortestPath<V, E>(graph, nev); } @Override public final Map<V, E> getIncomingEdgeMap(V source) { throw new AssertionError("not implemented"); } } AbstractAlgorithmStatus.java package KSP.algorithms; public abstract class AbstractAlgorithmStatus { private final String label; public AbstractAlgorithmStatus(String label) { this.label = label; } public final String getLabel() { return label; } public abstract Number getValue(); public abstract Number getMaximum(); public final int getRatio() { return (int) Math.round(getValue().doubleValue() / getMaximum().doubleValue() * 100.0); } } KSP.KSP Java Result: 1 IAlgorithm.java package KSP.algorithms; import java.util.List;


132

public interface IAlgorithm { public void performEvaluation(); public List<AbstractAlgorithmStatus> getStati(); } FullyMeshedEdgeGenerator.java package KSP.graph.generators; import KSP.graph.IEdge; import KSP.graph.IVertex; public final class FullyMeshedEdgeGenerator<V extends IVertex, E extends IEdge> extends RandomEdgeGenerator<V, E> { public FullyMeshedEdgeGenerator() { super(1.0); } } IEdgeGenerator.java package KSP.graph.generators; import KSP.graph.IEdge; import KSP.graph.ILayer; import KSP.graph.IVertex; public interface IEdgeGenerator<V extends IVertex, E extends IEdge> { public void generate(ILayer<V, E> g); } RandomEdgeGenerator.java package KSP.graph.generators; import KSP.graph.IEdge; import KSP.graph.ILayer; import KSP.graph.IVertex; import KSP.utils.distributions.UniformStream; public class RandomEdgeGenerator<V extends IVertex, E extends IEdge> implements IEdgeGenerator<V, E> { private final double p; public RandomEdgeGenerator(double p) { this.p = p; } @Override public void generate(ILayer<V, E> g) { UniformStream rnd = new UniformStream(); for (V v : g.getVertices()) for (V w : g.getVertices()) { if (v.equals(w)) continue; if (rnd.nextDouble() <= p) g.addEdge(g.getEdgeFactory().create(), v, w); } } } ReachabilityEnsuringEdgeGeneratorWrapper.java package KSP.graph.generators; import java.util.ArrayList;


133

import java.util.List; import KSP.graph.IEdge; import KSP.graph.ILayer; import KSP.graph.IVertex; import KSP.utils.distributions.UniformStream; import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath; import edu.uci.ics.jung.graph.util.Pair; public final class ReachabilityEnsuringEdgeGeneratorWrapper<V extends IVertex, E extends IEdge> implements IEdgeGenerator<V, E> { private final IEdgeGenerator<V, E> generator; public ReachabilityEnsuringEdgeGeneratorWrapper( IEdgeGenerator<V, E> generator) { this.generator = generator; } @Override public void generate(ILayer<V, E> g) { generator.generate(g); UniformStream rnd = new UniformStream(); List<V> vs = new ArrayList<V>(g.getVertices()); DijkstraShortestPath<V, E> dsp = new DijkstraShortestPath<V, E>(g); List<Pair<V>> unreachables = new ArrayList<Pair<V>>(); List<Pair<V>> removeUnreachables = new ArrayList<Pair<V>>(); for (V v : g.getVertices()) for (V w : g.getVertices()) if (dsp.getDistance(v, w) == null) unreachables.add(new Pair<V>(v, w)); while (!unreachables.isEmpty()) { int num = rnd.nextInt(g.getVertexCount() - 1); V v = vs.get(num); int num2 = rnd.nextInt(g.getVertexCount() - 1); V w = vs.get(num2); if (!v.equals(w) && g.findEdge(v, w) == null) { g.addEdge(g.getEdgeFactory().create(), v, w); dsp.reset(); for (Pair<V> p : unreachables) { V v2 = p.getFirst(); V w2 = p.getSecond(); if (dsp.getDistance(v2, w2) != null) removeUnreachables.add(p); } for (Pair<V> p : removeUnreachables) unreachables.remove(p); removeUnreachables.clear(); } } } } WaxmanGraphGenerator.java package KSP.graph.generators;


134

import java.awt.geom.Point2D; import java.awt.geom.Rectangle2D; import java.util.HashMap; import KSP.graph.IEdge; import KSP.graph.ILayer; import KSP.graph.IVertex; import KSP.utils.distributions.UniformStream; public final class WaxmanGraphGenerator<V extends IVertex, E extends IEdge> implements IEdgeGenerator<V, E> { private final double alpha; private final double beta; private final boolean bidirectional; private HashMap<V, Point2D> pos; private static final UniformStream rnd = new UniformStream(); public WaxmanGraphGenerator(double alpha, double beta, boolean bidirectional) { if (Double.isNaN(alpha) || Double.isInfinite(alpha) || Double.isNaN(beta) || Double.isInfinite(beta)) throw new IllegalArgumentException(); if (!(0 < alpha && beta <= 1)) throw new IllegalArgumentException(); this.alpha = alpha; this.beta = beta; this.bidirectional = bidirectional; } @Override public void generate(ILayer<V, E> g) { Rectangle2D.Double bounds = new Rectangle2D.Double(0.0, 0.0, 1.0, 1.0); pos = new HashMap<V, Point2D>(g.getVertexCount()); for (V v : g.getVertices()) pos.put(v, new Point2D.Double(rnd.nextDouble(), rnd.nextDouble())); final double L = Math.sqrt(bounds.width * bounds.width + bounds.height * bounds.height); // sqrt(2) for (V v : g.getVertices()) for (V w : g.getVertices()) { if (v == w) continue; final double d = pos.get(v).distance(pos.get(w)); final double p = rnd.nextDouble(); final double p_waxman = alpha * Math.exp(-d / (beta * L)); if (p < p_waxman) { if (g.findEdge(v, w) == null) g.addEdge(g.getEdgeFactory().create(), v, w); if (bidirectional && g.findEdge(w, v) == null) g.addEdge(g.getEdgeFactory().create(), w, v); } } } /** @return A map with the positions for the last graph generation. */ public HashMap<V, Point2D> getPositions() {


135

return pos; } } Transformers package KSP.graph.transformers; import org.apache.commons.collections15.Transformer; public interface IEdgeWeightTransformer<E> extends Transformer<E, Number> { public void set(E e, Number w); } AbstractLayerStack.java package KSP.graph; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import KSP.utils.AbstractChangeable; import org.apache.commons.collections15.iterators.UnmodifiableIterator; public abstract class AbstractLayerStack<L extends ILayer<? extends IVertex, ? extends IEdge>> extends AbstractChangeable implements Iterable<L> { protected final List<L> layers; protected AbstractLayerStack() { layers = new LinkedList<L>(); } public boolean isEmpty() { return layers.isEmpty(); } @Override public final Iterator<L> iterator() { return UnmodifiableIterator.decorate(layers.iterator()); } public void addLayer(L layer) { // Adds the graph to graph list. if (layers.add(layer)) fireStateChanged(new LayerChangedEvent<L>(this, layer, false)); else throw new AssertionError("graph"); } } IEdge.java package KSP.graph; public interface IEdge { public int getId(); } ILayer.java package KSP.graph; import org.apache.commons.collections15.Factory; import edu.uci.ics.jung.graph.Graph; public interface ILayer<V extends IVertex, E extends IEdge> extends Graph<V, E> { public int getLayer(); public String getLabel();


136

public Factory<E> getEdgeFactory(); } IVertex.java ackage KSP.graph; public interface IVertex { public int getId(); public String getLabel(); } LayerChangedEvent.java package KSP.graph; import javax.swing.event.ChangeEvent; @SuppressWarnings("serial") public class LayerChangedEvent<L extends ILayer<? extends IVertex, ? extends IEdge>> extends ChangeEvent { public final L g; public final boolean remove; public LayerChangedEvent(Object source, L g, boolean remove) { super(source); this.g = g; this.remove = remove; } } DefaultSelectionTreeModel.java package KSP.gui.components.selectionpanel; import javax.swing.event.TreeModelListener; import javax.swing.tree.TreeModel; import javax.swing.tree.TreeNode; import javax.swing.tree.TreePath; import KSP.gui.components.LayerViewer; public class DefaultSelectionTreeModel implements TreeModel { protected interface IProxy { Object getChildAt(int index); int getChildCount(); } private abstract class ObjectSelectionProxy implements IProxy { protected abstract Object[] extractSelectedObjects(LayerViewer<?, ?> vv); protected abstract String getObjectName(); @Override public Object getChildAt(int index) { if (owner == null || owner.getGraphPanel() == null || index < 0) return null; for (LayerViewer<?, ?> vv : owner.getGraphPanel().getViewers()) { Object[] sel = extractSelectedObjects(vv); if (sel == null) continue; if (index < sel.length) return sel[index]; index -= sel.length; } // not found or index out of bounds return null; }


137

@Override public int getChildCount() { int length = 0; if (owner != null && owner.getGraphPanel() != null) { // add pickedstate selections of each viewer for (LayerViewer<?, ?> vv : owner.getGraphPanel().getViewers()) { Object[] sel = extractSelectedObjects(vv); length += (sel == null) ? 0 : sel.length; } } return length; } @Override public String toString() { return getObjectName() + " (" + getChildCount() + ")"; } } public class EdgeSelectionProxy extends ObjectSelectionProxy { @Override protected String getObjectName() { return "Edges"; } @Override protected Object[] extractSelectedObjects(LayerViewer<?, ?> vv) { return vv.getPickedEdgeState().getSelectedObjects(); } } public class VertexSelectionProxy extends ObjectSelectionProxy { @Override protected String getObjectName() { return "Vertices"; } @Override protected Object[] extractSelectedObjects(LayerViewer<?, ?> vv) { return vv.getPickedVertexState().getSelectedObjects(); } } public class RootProxy implements IProxy { private IProxy[] selectionModules; public RootProxy(IProxy vertexsel, IProxy edgesel) { this(new IProxy[] { vertexsel, edgesel }); } public RootProxy(IProxy[] selectionModules) { if (selectionModules == null) throw new IllegalArgumentException(); for (IProxy proxy : selectionModules) if (proxy == null) throw new IllegalArgumentException(); this.selectionModules = selectionModules;


138

} @Override public int getChildCount() { return selectionModules.length; } @Override public Object getChildAt(int index) { return selectionModules[index]; } } private SelectionPanel owner; private IProxy root; public DefaultSelectionTreeModel() { root = createRoot(); } protected IProxy createRoot() { return new RootProxy(new VertexSelectionProxy(), new EdgeSelectionProxy()); } public SelectionPanel getOwner() { return owner; } public void setOwner(SelectionPanel owner) { this.owner = owner; } @Override public Object getChild(Object parent, int index) { if (parent instanceof IProxy) return ((IProxy) parent).getChildAt(index); else if (parent instanceof TreeNode) return ((TreeNode) parent).getChildAt(index); else return null; } @Override public int getChildCount(Object parent) { if (parent instanceof IProxy) return ((IProxy) parent).getChildCount(); else if (parent instanceof TreeNode) return ((TreeNode) parent).getChildCount(); else return 0; } @Override public int getIndexOfChild(Object parent, Object child) { if (parent == null || child == null) return -1; else { int num = getChildCount(parent); for (int i = 0; i < num; i++) if (getChild(parent, i).equals(child)) return i; return -1;


139

} } @Override public Object getRoot() { return root; } @Override public boolean isLeaf(Object node) { return getChildCount(node) == 0; } @Override public void addTreeModelListener(TreeModelListener l) { } @Override public void removeTreeModelListener(TreeModelListener l) { } @Override public void valueForPathChanged(TreePath path, Object newValue) { } } SelectionPanel.java package KSP.gui.components.selectionpanel; import KSP.gui.components.GraphPanel; import KSP.gui.components.LayerViewer; import KSP.gui.components.TreePanel; @SuppressWarnings("serial") public final class SelectionPanel extends TreePanel { private SelectionTreeItemListener listener; public SelectionPanel(GraphPanel<?, ?> graphpanel) { this(new DefaultSelectionTreeModel(), graphpanel); } public SelectionPanel(DefaultSelectionTreeModel model, GraphPanel<?, ?> graphpanel) { super(graphpanel); getTree().setModel(model); model.setOwner(this); getTree().setRootVisible(false); listener = new SelectionTreeItemListener(this); getTree().addMouseListener(new SelectionPanelMouseAdapter(this)); } @Override protected void onLayerViewerAdd(LayerViewer<?, ?> vv) { vv.getPickedVertexState().addItemListener(listener); vv.getPickedEdgeState().addItemListener(listener); } @Override protected void onLayerViewerRemove(LayerViewer<?, ?> vv) { vv.getPickedVertexState().removeItemListener(listener);


140

vv.getPickedEdgeState().removeItemListener(listener); } @Override public void update() { getTree().updateUI(); } }


141

SelectionPanelMouseAdapter.java package KSP.gui.components.selectionpanel; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.event.MouseAdapter; import java.awt.event.MouseEvent; import javax.swing.JMenuItem; import javax.swing.JPopupMenu; import javax.swing.JTree; import javax.swing.tree.TreePath; import KSP.graph.IEdge; import KSP.graph.IVertex; import KSP.gui.components.GraphPanel; import KSP.gui.components.LayerViewer; import edu.uci.ics.jung.visualization.picking.PickedState; public final class SelectionPanelMouseAdapter extends MouseAdapter { private JPopupMenu popup = new JPopupMenu(); private SelectionPanel owner; public SelectionPanelMouseAdapter(SelectionPanel owner) { if (owner == null) throw new IllegalArgumentException(); this.owner = owner; } @Override public void mousePressed(MouseEvent e) { handlePopup(e); } @Override public void mouseReleased(MouseEvent e) { handlePopup(e); } private void handlePopup(MouseEvent e) { if (e.isPopupTrigger()) { JMenuItem mi; popup.removeAll(); final JTree tree = (JTree) e.getSource(); if (!tree.isSelectionEmpty()) { // Clear selected mi = new JMenuItem("Remove selected"); mi.addActionListener(new ActionListener() { @SuppressWarnings("unchecked") @Override public void actionPerformed(ActionEvent e2) { GraphPanel<?, ?> gp = owner.getGraphPanel(); if (gp == null) return;


142

// Deselect all selected objects. for (TreePath path : tree.getSelectionPaths()) { Object last = path.getLastPat


143

Codificación del algoritmo CSP Clase: AproxBucket.java /** * Data structure for an aproximate bucket. Used for the SP implementation package edu.udistri.copa.JCSP; public class AproxBucket { private AproxBucket down; private AproxBucket up; private VertexCSP entrance; /** * Key of the bucket, also is the lower bound * of the bucket */ private int key; /** * upper is the upper bound of the bucket */ private int upper; /** * lower is the upper bound of the bucket */ private int lower; public AproxBucket(VertexCSP v, int nKey, int delta){ down = null; up = null; entrance = v; key = nKey; lower = key*delta; upper = (key+1)*delta-1; } /** * Insert a vertex in the bucket. * @param v Vertex being inserted */ public void insertVertexDist(VertexCSP v){ //System.out.println("Entrando "+ v.getID() + " FO : " + v.getMinCost() ); entrance.insertVertexDist(v); } public void insertVertexTime(VertexCSP v){ //System.out.println("Entrando "+ v.getID() + " FO : " + v.getMinCost() ); entrance.insertVertexTime(v); } /** * * @return */ public AproxBucket deleteLabeledBucket() { if(up!=null){ up.down = null; return up;


144

} return null; } public void deleteToPassDist(VertexCSP v){ entrance = entrance.getBRigthDist(); v.fastUnlinkDist(); } public void deleteToPassTime(VertexCSP v){ entrance = entrance.getBRigthTime(); v.fastUnlinkTime(); } public boolean deleteToMoveDist(VertexCSP v){ if(entrance.getID() == v.getID()){ entrance = entrance.getBRigthDist(); } return v.unLinkVertexDist(); } public boolean deleteToMoveTime(VertexCSP v){ if(entrance.getID() == v.getID()){ entrance = entrance.getBRigthTime(); } return v.unLinkVertexTime(); } public AproxBucket deleteBucketToEmpty(){ if(up!=null){ up.down = null; return up; } return null; } public AproxBucket deleteBucket(){ if(up!=null){ up.down = down; if(down != null){ down.up = up; }else{ return null; } } else{ if(down != null){ down.up = null; return down; }else{ return null; } } return null; } public int getKey(){ return key; }


145

public int getLowerBound() { return lower; } public int getUpperBound() { return upper;//No me gusta llamar a delta así } public VertexCSP getEntrance(){ return entrance; } public AproxBucket getUP(){ return up; } public AproxBucket getDown(){ return down; } public void setUP(AproxBucket v){ up = v; } public void setDown(AproxBucket v){ down = v; } public void turnTheBucket(){ entrance= entrance.getBRigthDist(); } public void turnTheBucketTime(){ entrance= entrance.getBRigthTime(); } } Bucket.java package edu.udistri.copa.JCSP; public class Bucket { private VertexCSP entrance; private int key; /** * Create an instance of a bucket. If a bucket * is opened, a new vertex is being added * @param v */ public Bucket(VertexCSP v, int nKey){ entrance = v; key = nKey; } public Bucket(int nKey){ key = nKey; } /** * Insert a vertex in the bucket. * @param v Vertex being inserted


146

*/ public void insertVertexDist(VertexCSP v){ if(entrance!=null){ entrance.insertVertexDist(v); }else{ entrance = v; } } public void insertVertexTime(VertexCSP v){ if(entrance!=null){ entrance.insertVertexTime(v); }else{ entrance = v; } } /** * * @param v * @return */ public boolean deleteLabeledVertexDist(){ //Delete entrance / FIFO policy entrance = entrance.getBRigthDist(); boolean emp = entrance.getBLeftDist().unLinkVertexDist(); if(emp){ entrance = null; return true; } return false; } public boolean deleteLabeledVertexTime(){ //Delete entrance / FIFO policy entrance = entrance.getBRigthTime(); boolean emp = entrance.getBLeftTime().unLinkVertexTime(); if(emp){ entrance = null; return true; } return false; } public boolean deleteToMoveDist(VertexCSP v){ if(entrance.getID() == v.getID()){ entrance = entrance.getBRigthDist(); } if(v.unLinkVertexDist()){ entrance = null; return true; } return false; } public boolean deleteToMoveTime(VertexCSP v){ if(entrance.getID() == v.getID()){ entrance = entrance.getBRigthTime();


147

} if(v.unLinkVertexTime()){ entrance = null; return true; } return false; } public int getKey(){ return key; } public void setKey(int nKey){ key = nKey; } public VertexCSP getEntrance(){ return entrance; } public boolean empty() { if(entrance!=null){ return false; } return true; } } Clase: DataHandler.java package edu.udistri.copa.JCSP; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.Random; import java.util.StringTokenizer; public class DataHandler { // Name of the instance String CvsInput; // Number of arcs int NumArcs; // Number of nodes static int NumNodes; // Destinantion node int LastNode; // Source node int Source; // All the arcs in the network stored in a vector where Arcs[i][0]= Tail for arc i and Arcs[i][1]= Head for arc i static int[][] Arcs; // The distance attribute for any arc i static int[] Distance; // The time attribute for any arc i


148

static int[] Time; // Data structure for storing the graph private CSPGraph Gd; // Read data from an instance public DataHandler(Settings Instance) { CvsInput = Instance.DataFile; NumArcs = Instance.NumArcs; NumNodes = Instance.NumNodes; LastNode = Instance.LastNode; Source = Instance.Source; Arcs = new int[Instance.NumArcs][2]; Distance = new int[Instance.NumArcs]; Time = new int[Instance.NumArcs]; Gd = new CSPGraph(NumNodes); } // This procedure creates the nodes for the graph public void upLoadNodes(){ // All nodes are VertexCSP except the final node for (int i = 0; i < NumNodes; i++) { if(i!=(LastNode-1)){ Gd.addVertex(new VertexCSP(i) ); } } // The final node is a FinalVertexCSP FinalVertexCSP vv = new FinalVertexCSP(LastNode-1); Gd.addFinalVertex(vv); } // This procedure returns a graph public CSPGraph getGd() { return Gd; } // This procedure reads data from a data file in DIMACS format public void ReadDimacs() throws NumberFormatException, IOException { File file = new File(CvsInput); BufferedReader bufRdr = new BufferedReader(new FileReader(file)); String line = null; String[] readed = new String[5]; int row = 0; int col = 0; upLoadNodes(); while ((line = bufRdr.readLine()) != null && row < NumArcs + 1) { StringTokenizer st = new StringTokenizer(line, " "); while (st.hasMoreTokens()) { // get next token and store it in the array readed[col] = st.nextToken(); col++; } if (row >= 1) { Arcs[row - 1][0] = (Integer.parseInt(readed[1]) - 1);


149

Arcs[row - 1][1] = (Integer.parseInt(readed[2]) - 1); Distance[row - 1] = Integer.parseInt(readed[3]); Time[row - 1] = Integer.parseInt(readed[4]); // Add edges to the network Gd.addWeightedEdge( Gd.getVertexByID(Arcs[row - 1][0]), Gd.getVertexByID(Arcs[row - 1][1]),Distance[row - 1], Time[row - 1] , row-1); } col = 0; row++; } } } Clase: DukqstraDist package edu.udistri.copa.JCSP; public class DukqstraDist { public int C; private int Delta; private CSPGraph G; private Bucket[] lowLevelBuckets; private AproxBucket[] highLevelBuckets; private AproxBucket baseAproxBucket; private AproxBucket topAproxBucket; /** * Index where the Low level starts */ private int indexL; private int dL; /** * Index where the high level starts */ private int indexK; private int dK; private int Snum; private int numHigh; private int numNodes; private int iH; private int jH; public DukqstraDist(CSPGraph g, int source) { G=g; // C es el max arco C= G.getCd(); double x = (int)(Math.log(Math.sqrt(C))/Math.log(2))+0.0; Delta = (int)(Math.pow(2,x)); numHigh = (int)(((C+1)/Delta))+1; //System.out.println(numHigh); lowLevelBuckets = new Bucket[Delta]; highLevelBuckets = new AproxBucket[numHigh];


150

G.getVertexByID(source).setMinDist(0); Snum = 0; numNodes = G.getNumNodes(); indexL = 0; dL = 0; indexK = 1; dK = Delta; iH = -1; jH = -1; Bucket st =new Bucket(G.getVertexByID(source), 0); lowLevelBuckets[0] = st; //AproxBucket st2 =new AproxBucket(G.getVertexByID(source), 0); initializeBuckets(); baseAproxBucket = null; topAproxBucket = null; } /** * Run Dijkstra's algorithm for distance */ public void runAlgDist() { int numN = numNodes; VertexCSP vi; int di; int ti; int lowIterator = 0; boolean empty; while (Snum < numN) { while (lowIterator < Delta) { vi = lowLevelBuckets[lowIterator].getEntrance(); di = vi.getMinDist(); ti = vi.getMaxTime(); empty = deleteToLabel(lowIterator); Snum++; EdgeCSP e = vi.getReversedEdges(); int dj; VertexCSP vj; while (e != null) { vj = e.getTarget(); dj = vj.getMinDist(); if (dj > di + e.getWeightDist()) { int ndj = di + e.getWeightDist(); // dMap.put(vj.getID(), ndj); vj.setMinDist(ndj); vj.setMaxTime(ti + e.getWeightTime()); if (ndj < dK) { if (vj.isInserteDist()) { moveToLow(dj, ndj, vj);


151

} else { vj.setInsertedDist(); insertLow(ndj, vj); } } else { if (vj.isInserteDist()) { moveBucketToBucket(dj, ndj, vj); } else { vj.setInsertedDist(); firstInsertion(ndj, vj); } } } e = e.getNext(); } if(empty){ lowIterator = moveInLow(lowIterator); } } stepForwardInDist(); lowIterator = whereToStart(); } } private int whereToStart() { for (int i = 0; i < Delta; i++) { if(!lowLevelBuckets[i].empty()){ return i; } } return Delta; } /* VertexCSP entrance = baseAproxBucket.getEntrance(); boolean emp=false; int dv; while (!emp) { emp = baseAproxBucket.deleteToMove(entrance); dv= entrance.getMinDist(); lowLevelBuckets[dv-dL].insertVertex(entrance); entrance = baseAproxBucket.getEntrance(); }*/ private void stepForwardInDist() { if (baseAproxBucket!=null) { indexL= baseAproxBucket.getKey(); dL = indexL*Delta; VertexCSP entrance = baseAproxBucket.getEntrance(); entrance.getBLeftDist().unlinkRighBoundDist(); int dv; while(entrance!=null){ baseAproxBucket.deleteToPassDist(entrance); dv= entrance.getMinDist(); lowLevelBuckets[dv-dL].insertVertexDist(entrance);


152

entrance = baseAproxBucket.getEntrance(); } highLevelBuckets[iH]=null; int oldBaseKEy= baseAproxBucket.getKey(); baseAproxBucket = baseAproxBucket.deleteBucketToEmpty(); if(baseAproxBucket!=null){ iH = posCalculator(baseAproxBucket.getKey(), oldBaseKEy); }else{ iH=-1; jH=-1; } } indexK= indexL + 1; dK = indexK*Delta; } /*VertexCSP entrance = baseAproxBucket.getEntrance(); boolean emp=false; int dv; while (!emp) { emp = baseAproxBucket.deleteToMove(entrance); dv= entrance.getMinTime(); lowLevelBuckets[dv-dL].insertVertex(entrance); entrance = baseAproxBucket.getEntrance(); }*/ /** * Insert a vertex to the key-L low bucket * @param ndj d(v) , tentative shortest path * @param v vertex being inserted */ private void insertLow(int ndj, VertexCSP v){ lowLevelBuckets[ndj - dL].insertVertexDist(v); } private void moveToLow(int dj, int ndj, VertexCSP v){ if(dj<dK){ lowLevelBuckets[dj - dL].deleteToMoveDist(v); insertLow(ndj, v); }else{ int key = keyCalculator(dj); boolean empty = deleteToMove(key, v); insertLow(ndj, v); if(empty){ deleteBucket(key); } } } private void deleteBucket(int key) { int pos = posCalculator(key, baseAproxBucket.getKey()); AproxBucket del = highLevelBuckets[pos]; if(del.getDown()==null){ baseAproxBucket = del.getUP(); if(del.getUP()==null){ topAproxBucket = null; iH = -1;


153

jH = -1; }else{ iH = posCalculator(del.getUP().getKey(), key); baseAproxBucket.setDown(null); } }else{ if(del.getUP()!=null){ del.getDown().setUP(del.getUP()); del.getUP().setDown(del.getDown()); }else{ jH = posCalculator(del.getDown().getKey(), baseAproxBucket.getKey()); topAproxBucket = del.getDown(); topAproxBucket.setUP(null); } } highLevelBuckets[pos]= null; } /** * Insert * @param key * @param clueKey * @param v */ private void insert(int key, int clueKey, int ndj, VertexCSP v ) { int pos = posCalculator(key, baseAproxBucket.getKey()); if(highLevelBuckets[pos] != null){ highLevelBuckets[pos].insertVertexDist(v); }else{ AproxBucket theNewBucket = new AproxBucket(v, key,Delta ); highLevelBuckets[pos] = theNewBucket; if(ndj < baseAproxBucket.getLowerBound()){ int deltaPos =key - baseAproxBucket.getKey() ; baseAproxBucket.setDown(theNewBucket); theNewBucket.setUP(baseAproxBucket); baseAproxBucket = theNewBucket; iH += deltaPos; if(iH<0){ iH+= numHigh; } } else if(ndj> topAproxBucket.getUpperBound()){ int deltaPos = key - topAproxBucket.getKey(); topAproxBucket.setUP(theNewBucket); theNewBucket.setDown(topAproxBucket); topAproxBucket = theNewBucket; jH += deltaPos; if(jH>=numHigh){ jH-=numHigh; } }else{ int cluePos = posCalculator(clueKey, baseAproxBucket.getKey());


154

AproxBucket aux = highLevelBuckets[cluePos]; boolean inserted = false; while(aux!= null && !inserted){ if(ndj > aux.getUpperBound()){ theNewBucket.setUP(aux.getUP()); theNewBucket.setDown(aux); aux.getUP().setDown(theNewBucket); aux.setUP(theNewBucket); inserted =true; } aux = aux.getDown(); } } } } /** * Insertion of node to a bucket (only first time) * @param ndj key of the bucket * @param v vertex being inserted */ private void firstInsertion(int ndj,VertexCSP v){ int key = keyCalculator(ndj); if(baseAproxBucket!=null){ int pos = posCalculator(key, baseAproxBucket.getKey()); if(highLevelBuckets[pos] != null){ highLevelBuckets[pos].insertVertexDist(v); } else{ AproxBucket theNewBucket = new AproxBucket(v, key, Delta); highLevelBuckets[pos] = theNewBucket; if(ndj < baseAproxBucket.getLowerBound()){ int deltaPos = key- baseAproxBucket.getKey(); baseAproxBucket.setDown(theNewBucket); theNewBucket.setUP(baseAproxBucket); baseAproxBucket = theNewBucket; iH += deltaPos; if(iH<0){ iH+= numHigh; } } else if(ndj> topAproxBucket.getUpperBound()){ int deltaPos = key -topAproxBucket.getKey(); topAproxBucket.setUP(theNewBucket); theNewBucket.setDown(topAproxBucket); topAproxBucket = theNewBucket; jH += deltaPos; if(jH>=numHigh){ jH-=numHigh; } } else{ AproxBucket aux = baseAproxBucket.getUP();


155

boolean inserted = false; while(aux!= null && !inserted){ if(ndj < aux.getLowerBound()){ theNewBucket.setUP(aux); theNewBucket.setDown(aux.getDown()); aux.getDown().setUP(theNewBucket); aux.setDown(theNewBucket); inserted =true; } aux = aux.getUP();//Upward iteration } } } }else{ AproxBucket theNewBucket = new AproxBucket(v, key, Delta); int pos = key-indexK; iH = pos; jH = pos; highLevelBuckets[pos] = theNewBucket; baseAproxBucket= theNewBucket; topAproxBucket = theNewBucket; } } /** * Delete the entrance vertex of the baseBucket */ private boolean deleteToLabel(int lowIter){ return lowLevelBuckets[lowIter].deleteLabeledVertexDist(); } private int moveInLow(int lowIter){ while(lowIter<Delta){ if(!lowLevelBuckets[lowIter].empty()){ return lowIter; } lowIter++; } return lowIter; } /** * Delete temporaly a node to move from an aproximate bucket to another * @param key Key of the bucke where v is * @param v Vertex being moved * @return true if the bucket got empty */ private boolean deleteToMove(int key , VertexCSP v){ int pos = posCalculator(key, baseAproxBucket.getKey()); AproxBucket b = highLevelBuckets[pos]; return b.deleteToMoveDist(v); }


156

/** * Move a vertex from one bucket to another * @param oldKey Key where the vertex is * @param newKey Key where the vertex have to be * @param v Vetex to be moved */ private void moveBucketToBucket(int dj, int ndj, VertexCSP v){ int oldKey = keyCalculator(dj); int newKey = keyCalculator(ndj); if(oldKey!=newKey){ boolean empty = deleteToMove(oldKey, v); insert(newKey, oldKey, ndj, v); if(empty){ deleteBucket(oldKey); } } } public void resetBucketMap(int source){ C= G.getCt(); double x = (int)(Math.log(Math.sqrt(C))/Math.log(2))+0.0; Delta = (int)(Math.pow(2,x)); Snum = 0; indexL = 0; dL = 0; indexK = 1; dK = Delta; lowLevelBuckets = new Bucket[Delta]; numHigh = (int)(((C+1)/Delta))+1; highLevelBuckets = new AproxBucket[numHigh]; Bucket st =new Bucket(G.getVertexByID(source), 0); lowLevelBuckets[0] = st; initializeBuckets(); iH = -1; jH = -1; baseAproxBucket = null; topAproxBucket = null; } private void initializeBuckets() { if(Delta>1){ for(int i = 1 ; i<Delta; i++){ lowLevelBuckets[i]= new Bucket(i); } } } private int keyCalculator(int dj){ return (int)(dj/Delta); } private int posCalculator(int key , int baseKey ) { int pos = iH + key - baseKey; if(pos>=numHigh){ return pos-numHigh; }else if(pos<0){


157

return pos+numHigh; }else{ return pos; } } } Clase: DukqstraTime package edu.udistri.copa.JCSP; public class DukqstraTime { public int C; private int Delta; private CSPGraph G; private Bucket[] lowLevelBuckets; private AproxBucket[] highLevelBuckets; private AproxBucket baseAproxBucket; private AproxBucket topAproxBucket; /** * Index where the Low level starts */ private int indexL; private int dL; /** * Index where the high level starts */ private int indexK; private int dK; private int Snum; private int numHigh; private int numNodes; private int iH; private int jH; public DukqstraTime(CSPGraph g, int source) { G=g; C= G.getCt(); double x = (int)(Math.log(Math.sqrt(C))/Math.log(2))+0.0; Delta = (int)(Math.pow(2,x)); numHigh = (int)(((C+1)/Delta))+1; //System.out.println(numHigh); lowLevelBuckets = new Bucket[Delta]; highLevelBuckets = new AproxBucket[numHigh]; G.getVertexByID(source).setMinTime(0); Snum = 0; numNodes = G.getNumNodes(); indexL = 0; dL = 0; indexK = 1; dK = Delta; iH = -1;


158

jH = -1; Bucket st =new Bucket(G.getVertexByID(source), 0); lowLevelBuckets[0] = st; //AproxBucket st2 =new AproxBucket(G.getVertexByID(source), 0); initializeBuckets(); baseAproxBucket = null; topAproxBucket = null; } /** * Run Dijkstra's algorithm for Time */ public void runAlgTime() { int numN = numNodes; VertexCSP vi; int di; int ti; int lowIterator = 0; boolean empty; while (Snum < numN) { while (lowIterator < Delta) { vi = lowLevelBuckets[lowIterator].getEntrance(); di = vi.getMaxDist(); ti = vi.getMinTime(); empty = deleteToLabel(lowIterator); Snum++; EdgeCSP e = vi.getReversedEdges(); int tj; VertexCSP vj; while (e != null) { vj = e.getTarget(); tj = vj.getMinTime(); if (tj > ti + e.getWeightTime()) { int ntj = ti + e.getWeightTime(); // dMap.put(vj.getID(), ndj); vj.setMinTime(ntj); vj.setMaxDist(di + e.getWeightDist()); if (ntj < dK) { if (vj.isInsertedTime()) { moveToLow(tj, ntj, vj); } else { vj.setInsertedTime(); insertLow(ntj, vj); } } else { if (vj.isInsertedTime()) { moveBucketToBucket(tj, ntj, vj); } else { vj.setInsertedTime();


159

firstInsertion(ntj, vj); } } } e = e.getNext(); } if(empty){ lowIterator = moveInLow(lowIterator); } } stepForwardInTime(); lowIterator = whereToStart(); } } private int whereToStart() { for (int i = 0; i < Delta; i++) { if(!lowLevelBuckets[i].empty()){ return i; } } return Delta; } /* VertexCSP entrance = baseAproxBucket.getEntrance(); boolean emp=false; int dv; while (!emp) { emp = baseAproxBucket.deleteToMove(entrance); dv= entrance.getMinDist(); lowLevelBuckets[dv-dL].insertVertex(entrance); entrance = baseAproxBucket.getEntrance(); }*/ private void stepForwardInTime() { if (baseAproxBucket!=null) { indexL= baseAproxBucket.getKey(); dL = indexL*Delta; VertexCSP entrance = baseAproxBucket.getEntrance(); entrance.getBLeftTime().unlinkRighBoundTime(); int dv; while(entrance!=null){ baseAproxBucket.deleteToPassTime(entrance); dv= entrance.getMinTime(); lowLevelBuckets[dv-dL].insertVertexTime(entrance); entrance = baseAproxBucket.getEntrance(); } highLevelBuckets[iH]=null; int oldBaseKEy= baseAproxBucket.getKey(); baseAproxBucket = baseAproxBucket.deleteBucketToEmpty(); if(baseAproxBucket!=null){ iH = posCalculator(baseAproxBucket.getKey(), oldBaseKEy); }else{


160

iH=-1; jH=-1; } } indexK= indexL + 1; dK = indexK*Delta; } /** * Insert a vertex to the key-L low bucket * @param ndj d(v) , tentative shortest path * @param v vertex being inserted */ private void insertLow(int ndj, VertexCSP v){ lowLevelBuckets[ndj - dL].insertVertexTime(v); } private void moveToLow(int dj, int ndj, VertexCSP v){ if(dj<dK){ lowLevelBuckets[dj - dL].deleteToMoveTime(v); insertLow(ndj, v); }else{ int key = keyCalculator(dj); boolean empty = deleteToMove(key, v); insertLow(ndj, v); if(empty){ deleteBucket(key); } } } private void deleteBucket(int key) { int pos = posCalculator(key, baseAproxBucket.getKey()); AproxBucket del = highLevelBuckets[pos]; if(del.getDown()==null){ baseAproxBucket = del.getUP(); if(del.getUP()==null){ topAproxBucket = null; iH = -1; jH = -1; }else{ iH = posCalculator(del.getUP().getKey(), key); baseAproxBucket.setDown(null); } }else{ if(del.getUP()!=null){ del.getDown().setUP(del.getUP()); del.getUP().setDown(del.getDown()); }else{ jH = posCalculator(del.getDown().getKey(), baseAproxBucket.getKey()); topAproxBucket = del.getDown(); topAproxBucket.setUP(null); }


161

} highLevelBuckets[pos]= null; } /** * Insert * @param key * @param clueKey * @param v */ private void insert(int key, int clueKey, int ndj, VertexCSP v ) { int pos = posCalculator(key, baseAproxBucket.getKey()); if(highLevelBuckets[pos] != null){ highLevelBuckets[pos].insertVertexTime(v); }else{ AproxBucket theNewBucket = new AproxBucket(v, key, Delta); highLevelBuckets[pos] = theNewBucket; if(ndj < baseAproxBucket.getLowerBound()){ int deltaPos =key - baseAproxBucket.getKey() ; baseAproxBucket.setDown(theNewBucket); theNewBucket.setUP(baseAproxBucket); baseAproxBucket = theNewBucket; iH += deltaPos; if(iH<0){ iH+= numHigh; } } else if(ndj> topAproxBucket.getUpperBound()){ int deltaPos = key - topAproxBucket.getKey(); topAproxBucket.setUP(theNewBucket); theNewBucket.setDown(topAproxBucket); topAproxBucket = theNewBucket; jH += deltaPos; if(jH>=numHigh){ jH-=numHigh; } }else{ int cluePos = posCalculator(clueKey, baseAproxBucket.getKey()); AproxBucket aux = highLevelBuckets[cluePos]; boolean inserted = false; while(aux!= null && !inserted){ if(ndj > aux.getUpperBound()){ theNewBucket.setUP(aux.getUP()); theNewBucket.setDown(aux); aux.getUP().setDown(theNewBucket); aux.setUP(theNewBucket); inserted =true; } aux = aux.getDown(); } } }


162

} /** * Insertion of node to a bucket (only first time) * @param ndj key of the bucket * @param v vertex being inserted */ private void firstInsertion(int ndj,VertexCSP v){ int key = keyCalculator(ndj); if(baseAproxBucket!=null){ int pos = posCalculator(key, baseAproxBucket.getKey()); if(highLevelBuckets[pos] != null){ highLevelBuckets[pos].insertVertexTime(v); } else{ AproxBucket theNewBucket = new AproxBucket(v, key,Delta); highLevelBuckets[pos] = theNewBucket; if(ndj < baseAproxBucket.getLowerBound()){ int deltaPos = key- baseAproxBucket.getKey(); baseAproxBucket.setDown(theNewBucket); theNewBucket.setUP(baseAproxBucket); baseAproxBucket = theNewBucket; iH += deltaPos; if(iH<0){ iH+= numHigh; } } else if(ndj> topAproxBucket.getUpperBound()){ int deltaPos = key -topAproxBucket.getKey(); topAproxBucket.setUP(theNewBucket); theNewBucket.setDown(topAproxBucket); topAproxBucket = theNewBucket; jH += deltaPos; if(jH>=numHigh){ jH-=numHigh; } } else{ AproxBucket aux = baseAproxBucket.getUP(); boolean inserted = false; while(aux!= null && !inserted){ if(ndj < aux.getLowerBound()){ theNewBucket.setUP(aux); theNewBucket.setDown(aux.getDown()); aux.getDown().setUP(theNewBucket); aux.setDown(theNewBucket); inserted =true; } aux = aux.getUP();//Upward iteration } } } }else{


163

AproxBucket theNewBucket = new AproxBucket(v, key, Delta); int pos = key-indexK; iH = pos; jH = pos; highLevelBuckets[pos] = theNewBucket; baseAproxBucket= theNewBucket; topAproxBucket = theNewBucket; } } /** * Delete the entrance vertex of the baseBucket */ private boolean deleteToLabel(int lowIter){ return lowLevelBuckets[lowIter].deleteLabeledVertexTime(); } private int moveInLow(int lowIter){ while(lowIter<Delta){ if(!lowLevelBuckets[lowIter].empty()){ return lowIter; } lowIter++; } return lowIter; } /** * Delete temporaly a node to move from an aproximate bucket to another * @param key Key of the bucke where v is * @param v Vertex being moved * @return true if the bucket got empty */ private boolean deleteToMove(int key , VertexCSP v){ int pos = posCalculator(key, baseAproxBucket.getKey()); AproxBucket b = highLevelBuckets[pos]; return b.deleteToMoveTime(v); } /** * Move a vertex from one bucket to another * @param oldKey Key where the vertex is * @param newKey Key where the vertex have to be * @param v Vetex to be moved */ private void moveBucketToBucket(int dj, int ndj, VertexCSP v){ int oldKey = keyCalculator(dj); int newKey = keyCalculator(ndj); if(oldKey!=newKey){ boolean empty = deleteToMove(oldKey, v); insert(newKey, oldKey, ndj, v); if(empty){


164

deleteBucket(oldKey); } } } private void initializeBuckets() { if(Delta>1){ for(int i = 1 ; i<Delta; i++){ lowLevelBuckets[i]= new Bucket(i); } } } private int keyCalculator(int dj){ return (int)(dj/Delta); } private int posCalculator(int key , int baseKey ) { int pos = iH + key - baseKey; if(pos>=numHigh){ return pos-numHigh; }else if(pos<0){ return pos+numHigh; }else{ return pos; } } } Clase: EdgeCSP package edu.udistri.copa.JCSP; public class EdgeCSP { private int eDist; private int eTime; private EdgeCSP nextE; private int id; private VertexCSP source; private VertexCSP target; public EdgeCSP(int d , int t, VertexCSP nT, VertexCSP nH, int nid) { // TODO Auto-generated constructor stub eDist = d; eTime = t; this.source = nT; this.target = nH; this.id = nid; }


165

public void addNextCommonTailEdge(EdgeCSP e){ if(nextE!= null){ nextE.addNextCommonTailEdge(e); } else{ nextE = e; } } public EdgeCSP getNext() { return nextE; } public void setNextE(EdgeCSP e ){ nextE = e; } public int getWeightDist(){ return eDist; } public int getWeightTime(){ return eTime; } public VertexCSP getSource(){ return source; } public VertexCSP getTarget(){ return target; } public int getID() { return id; } public EdgeCSP findEdgebyTarget( VertexCSP targetT) { if(targetT.getID() == this.target.getID()) { return this; }else{ if(nextE!= null) { return nextE.findEdgebyTarget(targetT); } } return null; } public int getCompareCriteria(){ return target.getMinDist() + target.getMinTime(); }


166

} Clase: FinalVertexCSP package edu.udistri.copa.JCSP; import java.util.ArrayList; public class FinalVertexCSP extends VertexCSP { // Node id private int id; // SP stuff private VertexCSP bLeft; private VertexCSP bRigth; private EdgeCSP reverseEdges; // Bounds int minDist; int maxTime; int minTime; int maxDist; private boolean inserted; int c=0; int d=0; public FinalVertexCSP(int i) { super(i); id = i; inserted = false; minDist = infinity; minTime = infinity; maxTime = 0; maxDist = 0; bLeft = this; bRigth = this; } public int getID() { return id; } public void addReversedEdge(EdgeCSP e) { if(reverseEdges!=null){ reverseEdges.addNextCommonTailEdge(e); }else


167

reverseEdges = e; } public EdgeCSP findEdgeByTarget(VertexCSP target){ if(reverseEdges!=null){ reverseEdges.findEdgebyTarget(target); } return null; } public EdgeCSP getReversedEdges() { if(reverseEdges!= null){ return reverseEdges; }return new EdgeCSP(1,1, this,this , -1); } public void setMinDist(int c){ minDist = c; } public int getMinDist(){ return minDist; } public void setMaxTime(int mt){ maxTime = mt; } public int getMaxTime(){ return maxTime; } public void setMinTime(int t){ minTime = t; } public int getMinTime(){ return minTime; } public void setMaxDist(int md){ maxDist = md; } public int getMaxDist(){ return maxDist; } /** * Unlink a vertex from the bucket * @return true, if the buckets gets empty */


168

public boolean unLinkVertexDist(){ if(bRigth.getID() == id){ bLeft=this; bRigth=this; return true; }else{ bLeft.setRigthDist(bRigth); bRigth.setLeftDist(bLeft); bLeft = this; bRigth = this; return false; } } /** * Insert a vertex in a bucket. * New vertex is inserted on the left of the bucket entrance * @param v vertex in progress to be inserted */ public void insertVertexDist(VertexCSP v) { v.setLeftDist(bLeft); v.setRigthDist(this); bLeft.setRigthDist(v); bLeft = v; } public void setLeftDist(VertexCSP v){ bLeft= v; } public void setRigthDist(VertexCSP v){ bRigth= v; } public VertexCSP getBLeftDist(){ return bLeft; } public VertexCSP getBRigthDist(){ return bRigth; } public void setInsertedDist(){ inserted = true; } public boolean isInserteDist(){ return inserted; } public void reset(){ inserted = false; } public void setBounds(int MT, int MD){ maxDist = MD- minDist; maxTime = MT - minTime; }


169

public void CSP(int PTime, int PDist,ArrayList<Integer> path) { // Add node id to path path.add(id); // If the path is feasible and updates the primal bound the information on the best solution found is updated if(PDist<=CSPGraph.PrimalBound && PTime<=CSPGraph.TimeC){ // Update the best solution known CSPGraph.Path.clear(); CSPGraph.Path.addAll(path); CSPGraph.TimeStar=PTime; CSPGraph.PrimalBound=PDist; } // Remove the node id to backtrack path.remove((path.size()-1)); } } Clase: CSPGraph package edu.udistri.copa.JCSP; import java.util.ArrayList; import java.util.Collection; import java.util.Set; import org.jgrapht.EdgeFactory; import org.jgrapht.Graph; public class CSPGraph implements Graph<VertexCSP, EdgeCSP> { // The nodes static VertexCSP[] vertexes; // Number of nodes private int numNodes; //SP stuff private int Cd; private int Ct; // Time constraint static double TimeC; // Primal bound static double PrimalBound; // The best solution found is globally stored here static ArrayList<Integer> Path; // The time for the best solution found (the distance is stored in the primal bound) static double TimeStar; // Binary indicator to know if visiting a node creates a cycle static int[] Visited = new int[DataHandler.NumNodes]; public CSPGraph( int numNodes) { super(); this.numNodes = numNodes;


170

Cd=0; Ct=0; vertexes = new VertexCSP[numNodes]; Path= new ArrayList<Integer>(); } @Override public EdgeCSP addEdge(VertexCSP sourceVertex, VertexCSP targetVertex) { // TODO Auto-generated method stub return null; } public int getNumNodes() { return numNodes; } public VertexCSP getVertexByID(int id){ return vertexes[id]; } public EdgeCSP addWeightedEdge(VertexCSP sourceVertex, VertexCSP targetVertex, int d, int t, int id) { if(d>Cd){ Cd=d; } if(t>Ct){ Ct=t; } vertexes[targetVertex.getID()].addReversedEdge(new EdgeCSP(d, t, targetVertex , sourceVertex, id)); vertexes[sourceVertex.getID()].magicIndex.add(id); return null; } @Override public boolean addEdge(VertexCSP sourceVertex, VertexCSP targetVertex, EdgeCSP e) { return false; } @Override public boolean addVertex(VertexCSP v) { vertexes[v.getID()] = v; return true; } public boolean addFinalVertex(FinalVertexCSP v) { vertexes[v.getID()] = v; return true; } @Override public boolean containsEdge(VertexCSP sourceVertex, VertexCSP targetVertex) {


171

// TODO Auto-generated method stub return false; } @Override public boolean containsEdge(EdgeCSP e) { // TODO Auto-generated method stub return false; } @Override public boolean containsVertex(VertexCSP v) { // TODO Auto-generated method stub return false; } @Override public Set<EdgeCSP> edgeSet() { // TODO Auto-generated method stub return null; } @Override public Set<EdgeCSP> edgesOf(VertexCSP vertex) { // TODO Auto-generated method stub return null; } @Override public Set<EdgeCSP> getAllEdges(VertexCSP sourceVertex, VertexCSP targetVertex) { // TODO Auto-generated method stub return null; } @Override public EdgeCSP getEdge(VertexCSP sourceVertex, VertexCSP targetVertex) { // TODO Auto-generated method stub return null; } @Override public EdgeFactory<VertexCSP, EdgeCSP> getEdgeFactory() { // TODO Auto-generated method stub return null; } @Override public VertexCSP getEdgeSource(EdgeCSP e) { // TODO Auto-generated method stub return null; }


172

@Override public VertexCSP getEdgeTarget(EdgeCSP e) { // TODO Auto-generated method stub return null; } @Override public double getEdgeWeight(EdgeCSP e) { // TODO Auto-generated method stub return 0; } @Override public boolean removeAllEdges(Collection<? extends EdgeCSP> edges) { // TODO Auto-generated method stub return false; } @Override public Set<EdgeCSP> removeAllEdges(VertexCSP sourceVertex, VertexCSP targetVertex) { // TODO Auto-generated method stub return null; } @Override public boolean removeAllVertices(Collection<? extends VertexCSP> vertices) { // TODO Auto-generated method stub return false; } @Override public EdgeCSP removeEdge(VertexCSP sourceVertex, VertexCSP targetVertex) { // TODO Auto-generated method stub return null; } @Override public boolean removeEdge(EdgeCSP e) { // TODO Auto-generated method stub return false; } @Override public boolean removeVertex(VertexCSP v) { // TODO Auto-generated method stub return false; } @Override public Set<VertexCSP> vertexSet() { // TODO Auto-generated method stub


173

return null; } public int getCd() { return Cd; } public int getCt() { return Ct; } public void resetNetwork(){ for (int i = 0; i < numNodes ; i++) { vertexes[i].reset(); } } public void SetConstraint(double timeC) { this.TimeC=timeC; } public void setPrimalBound(int bound) { this.PrimalBound=bound; } } Clase: CSPMain import java.io.IOException; import java.util.ArrayList; public class CSPMain { public static void main(String[] args) throws IOException, InterruptedException { // Read a config file with the instance information String ini = "Config.txt"; Settings Instance; Instance= new Settings(ini); // Read the data file and store the data on a DataHandler DataHandler data = new DataHandler(Instance); data.ReadDimacs(); // Create the network and set the time constraint CSPGraph network = data.getGd();


174

network.SetConstraint(Instance.TimeC); // Create two threads and run parallel SP for the initialization Thread tTime = new Thread(); Thread tDist = new Thread(); // Begin the time count double Atime = System.nanoTime(); // Reverse the network and run SP for distance and time DukqstraDist spDist = new DukqstraDist(network, Instance.LastNode-1); DukqstraTime spTime = new DukqstraTime(network, Instance.LastNode-1); tDist = new Thread(new ShortestPathTask(1, spDist, null)); tTime = new Thread(new ShortestPathTask(0, null, spTime)); tDist.start(); tTime.start(); tDist.join(); tTime.join(); // MD is the distance for the best time path int MD=network.getVertexByID(Instance.Source-1).getMaxDist(); // Set the first primal bound network.setPrimalBound(MD); ///////////////////////////////////// CSP ///////////////////////////////////////////////////////////// // Create an empty path ArrayList<Integer> Path = new ArrayList<Integer>(); // CSP the origin node network.getVertexByID(Instance.Source-1).CSP(0, 0, Path); // Report the results System.out.println("Tiempo de ejecución: "+(System.nanoTime()-Atime)/1000000000); System.out.println("***************SOLUCIÓN ÓPTIMA*****************************"); System.out.println("Distancia: "+network.PrimalBound); System.out.println("Tiempo: "+network.TimeStar); System.out.println("Ruta öptima: "+network.Path); } } Clase: Settings package edu.udistri.copa.JCSP; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.StringTokenizer; public class Settings { String DataFile;


175

int NumArcs; int NumNodes; int LastNode; int Source; double TimeC; public Settings(String ConfigFile) throws IOException{ File file = new File(ConfigFile); BufferedReader bufRdr = new BufferedReader(new FileReader(file)); String line = null; String [][] readed = new String [6][2]; int row = 0; int col = 0; //read each line of text file while((line = bufRdr.readLine()) != null && row < 6) { StringTokenizer st = new StringTokenizer(line,":"); while (st.hasMoreTokens()) { //get next token and store it in the array readed[row][col] = st.nextToken(); col++; } col = 0; row++; } DataFile=readed[0][1]; NumArcs=Integer.parseInt(readed[1][1]); NumNodes=Integer.parseInt(readed[2][1]); TimeC=Double.parseDouble(readed[3][1]); Source=Integer.parseInt(readed[4][1]); LastNode=Integer.parseInt(readed[5][1]); } } Clase: ShortestPathTask package edu.udistri.copa.JCSP; public class ShortestPathTask implements Runnable { private DukqstraDist spDist;


176

private DukqstraTime spTime; private int algoRuning; public ShortestPathTask(int quienEs, DukqstraDist dD, DukqstraTime dT) { //quienES 1 Dist, 0 Time; algoRuning = quienEs; if(quienEs==1){ spDist = dD; }else{ spTime = dT; } } @Override public void run() { // TODO Auto-generated method stub if(algoRuning==1){ spDist.runAlgDist(); }else{ spTime.runAlgTime(); } } } Clase: VertexCSP package edu.udistri.copa.JCSP; import java.util.ArrayList; public class VertexCSP { // This array contains the indexes for all the outgoing arcs from this node ArrayList<Integer> magicIndex; // Labels double LabelTime1; double LabelTime2; double LabelTime3; double LabelDist1; double LabelDist2; double LabelDist3; // Boolean that tells if the node is visited for first time boolean firstTime = true; // Bounds to reach the end node int minDist; int maxTime; int minTime; int maxDist; // SP stuff public static final int infinity = (int)Double.POSITIVE_INFINITY; private EdgeCSP reverseEdges; private int id; private VertexCSP leftDist; private VertexCSP rigthDist; private VertexCSP leftTime;


177

private VertexCSP rigthTime; private boolean insertedDist; private boolean insertedTime; public VertexCSP(int i) { id = i; insertedDist = false; minDist = infinity; minTime = infinity; maxTime = 0; maxDist = 0; leftDist = this; rigthDist = this; leftTime = this; rigthTime = this; LabelTime1 = Double.POSITIVE_INFINITY; LabelDist1 = Double.POSITIVE_INFINITY; LabelTime2 = Double.POSITIVE_INFINITY; LabelDist2 = Double.POSITIVE_INFINITY; LabelTime3 = Double.POSITIVE_INFINITY; LabelDist3 = Double.POSITIVE_INFINITY; magicIndex = new ArrayList<Integer>(); } public int getID() { return id; } public void addReversedEdge(EdgeCSP e) { if(reverseEdges!=null){ reverseEdges.addNextCommonTailEdge(e); }else reverseEdges = e; } public EdgeCSP getReversedEdges() { if(reverseEdges!= null){ return reverseEdges; }return new EdgeCSP(1,1, this,this , -1); } public void setMinDist(int c){ minDist = c; } public int getMinDist(){ return minDist; }


178

public void setMaxTime(int mt){ maxTime = mt; } public int getMaxTime(){ return maxTime; } public void setMinTime(int t){ minTime = t; } public int getMinTime(){ return minTime; } public void setMaxDist(int md){ maxDist = md; } public int getMaxDist(){ return maxDist; } /** * Unlink a vertex from the bucket * @return true, if the buckets gets empty */ public boolean unLinkVertexDist(){ if(rigthDist.getID() == id){ leftDist=this; rigthDist=this; return true; }else{ leftDist.setRigthDist(rigthDist); rigthDist.setLeftDist(leftDist); leftDist = this; rigthDist = this; return false; } } public boolean unLinkVertexTime(){ if(rigthTime.getID() == id){ leftTime=this; rigthTime=this; return true; }else{ leftTime.setRigthTime(rigthTime); rigthTime.setLeftTime(leftTime); leftTime = this; rigthTime = this;


179

return false; } } public void fastUnlinkDist(){ leftDist=this; rigthDist=this; } public void fastUnlinkTime(){ leftTime = this; rigthTime = this; } public void unlinkRighBoundDist() { rigthDist = null; } public void unlinkRighBoundTime() { rigthTime = null; } /** * Insert a vertex in a bucket. * New vertex is inserted on the left of the bucket entrance * @param v vertex in progress to be inserted */ public void insertVertexDist(VertexCSP v) { v.setLeftDist(leftDist); v.setRigthDist(this); leftDist.setRigthDist(v); leftDist = v; } public void insertVertexTime(VertexCSP v) { v.setLeftTime(leftTime); v.setRigthTime(this); leftTime.setRigthTime(v); leftTime = v; } /** * Distance basic methods */ public void setLeftDist(VertexCSP v){ leftDist= v; } public void setRigthDist(VertexCSP v){ rigthDist= v; } public VertexCSP getBLeftDist(){ return leftDist; } public VertexCSP getBRigthDist(){ return rigthDist;


180

} public void setInsertedDist(){ insertedDist = true; } public boolean isInserteDist(){ return insertedDist; } /** * Time basic methods */ public void setLeftTime(VertexCSP v){ leftTime= v; } public void setRigthTime(VertexCSP v){ rigthTime= v; } public VertexCSP getBLeftTime(){ return leftTime; } public VertexCSP getBRigthTime(){ return rigthTime; } public void setInsertedTime(){ insertedTime = true; } public boolean isInsertedTime(){ return insertedTime; } public void reset(){ insertedDist = false; } // This is the CSP procedure public void CSP(int PTime, int PDist, ArrayList<Integer> path) { // if a node is visited for first time, sort the arcs if (this.firstTime) { this.firstTime = false; this.Sort(this.magicIndex); leftDist = null; rigthDist = null; reverseEdges = null; } // Label update changeLabels(PTime, PDist); // Check for cycles if (CSPGraph.Visited[id]==0) {


181

// Add the node to the path path.add(id); // Update the visit indicator CSPGraph.Visited[id]=1; // CSP all the head nodes for the outgoing arcs for (int i = 0; i < magicIndex.size(); i++) { // Update distance and time int NewTime = 0; int NewDist = 0; NewTime = (PTime + DataHandler.Time[magicIndex.get(i)]); NewDist = (PDist + DataHandler.Distance[magicIndex.get(i)]); // Pruning strategies: infeasibility, bounds and labels if (NewTime <= (CSPGraph.TimeC - CSPGraph.vertexes[DataHandler.Arcs[magicIndex.get(i)][1]].getMinTime()) && NewDist <= (CSPGraph.PrimalBound - CSPGraph.vertexes[DataHandler.Arcs[magicIndex.get(i)][1]].getMinDist()) && !CSPGraph.vertexes[DataHandler.Arcs[magicIndex.get(i)][1]].CheckLabels(NewTime, NewDist)){ // If not pruned the CSP travels to the next head node CSPGraph.vertexes[DataHandler.Arcs[magicIndex.get(i)][1]].CSP(NewTime, NewDist, path); } } // Updates path and visit indicator for backtrack path.remove((path.size() - 1)); CSPGraph.Visited[id]=0; } } private void Sort(ArrayList<Integer> set) { QS(magicIndex, 0, magicIndex.size()-1); } public int colocar(ArrayList<Integer> e, int b, int t) { int i; int pivote, valor_pivote; int temp; pivote = b; valor_pivote = CSPGraph.vertexes[DataHandler.Arcs[e.get(pivote)][1]].getCompareCriteria(); for (i=b+1; i<=t; i++){ if (CSPGraph.vertexes[DataHandler.Arcs[e.get(i)][1]].getCompareCriteria() < valor_pivote){ pivote++; temp= e.get(i); e.set(i, e.get(pivote)); e.set(pivote, temp); } } temp=e.get(b); e.set(b, e.get(pivote));


182

e.set(pivote, temp); return pivote; } public void QS(ArrayList<Integer> e, int b, int t) { int pivote; if(b < t){ pivote=colocar(e,b,t); QS(e,b,pivote-1); QS(e,pivote+1,t); } } public boolean CheckLabels( double PTime, double PDist) // Label pruning strategy { if((PTime >= LabelTime1 && PDist >= LabelDist1) || (PTime >= LabelTime2 && PDist >= LabelDist2) || (PTime >= LabelTime3 && PDist >= LabelDist3)){ return true; } return false; } private void changeLabels(int PTime, int PDist) { // Stores the best distance if (PDist <= LabelDist1) { LabelTime1 = PTime; LabelDist1 = PDist; // Stores the best time } else if (PTime <= LabelTime2) { LabelTime2 = PTime; LabelDist2 = PDist; // Replaces the third label } else { LabelTime3 = PTime; LabelDist3 = PDist; } } public int getCompareCriteria(){ return getMinDist(); } }

Documents

Aproximación al modelamiento del enrutamiento en redes ...repository.udistrital.edu.co/bitstream/11349/5649/1/ARIZA DANILO... · El método simplex ... Programación en Java