Planificación y Optimización Paralela de Redes Logísticas de Transporte
Conceptos y Estado del arte
Introducción
El objetivo de este capítulo es hacer una breve introducción a una serie de conceptos necesarios para comprender la función que realiza la aplicación. Los sistemas de suministro de gas o cual es el significado de su optimización no suelen ser conocidas por el público general. Además todos los apartados reflejados en el Capítulo 2: Aplicación, tienen su correspondencia directa con un apartado de este capítulo para facilitar la consulta.
Posteriormente hablaremos del estado del arte en lo que se refiere a optimización matemática y computación distribuida utilizando servicios web. Estos dos factores son definitorios en este proyecto y hemos creído oportuno comentar como funcionan. Mención especial merece el resolutor CPLEX sobre el que se ejecutan algoritmos para resolver problemas de optimización lineal entera mixta (MILP). Se ha optado por dejar de lado temas que no se tocan en el proyecto o que no sean de interés para el mismo. Aunque ciertamente se podría escribir cientos de líneas sobre que es un servicio web y cómo funcionan sus diferentes tipos, hemos creído oportuno mencionar únicamente el estado de las tecnologías que usamos y dar unas cuantas pinceladas de las que no utilizamos pero se llegaron a considerar para el proyecto. Esto último se realizará en el Capítulo 3: Desarrollo.
Gran parte de la carga de trabajo del proyecto ha consistido en investigar y comprender estos sistemas, por lo que esta sección sirve a su vez como una demostración de los conceptos asimilados.
Redes Logísticas de Transporte de Gas
Antes de entrar en más detalle en la aplicación, vamos a hablar de los objetos con los que trabaja la misma. Las redes logísticas de gas son una clase especial de redes logísticas en las que se planifica como transita el gas por una serie de conducciones desde los puntos de suministro (Ya sean plantas de regasificación donde llegan barcos cargados de gas natural licuado, como conexiones internacionales de gasoductos) hasta los puntos de demanda.
La finalidad de las mismas es satisfacer esta demanda. Queda fuera del alcance de este proyecto determinarla, pero merece la pena mencionar que es una tarea que se realiza por métodos estadísticos y en la que intervienen factores de lo más variado: Número de personas a satisfacer, industrias de la zona, época del año, tiempo meteorológico, etc, consiguiendo valores que se aproximan mucho a la demanda real. Hablamos por tanto de un modelo guiado por demanda. En la vida real, el suministro de gas es un sector estratégico para el país y por tanto incurrir en el desabastecimiento de la población o de la industria puede suponer fuertes multas para la empresa encargada de realizarlo. Es más, no solo el desabastecimiento: estas empresas están obligadas por ley a disponer de una cantidad mínima de reserva para tener margen de maniobra en el caso de que surgiese algún imprevisto. Conociendo todo lo anterior queda claro que cualquier modificación que se realice en el sistema tiene que estar precedida de suficientes estudios de viabilidad que la avalen.
Por otro lado, a veces no basta con que el modelo cumpla los requisitos para ciertos parámetros porque, como en todo, existe cierta incertidumbre en el proceso. Una tormenta puede retrasar la llegada a puerto de un barco, se tienen que tener en cuenta posibles paradas por mantenimiento que hagan que una parte del sistema deje de conducir gas… Por tanto el sistema tiene que ser tolerante a estos cambios y seguir pudiendo suministrar la capacidad requerida. Por decirlo de otra forma, aunque un sistema produzca una gran cantidad de beneficio para unos parámetros concretos, si es inestable, cualquier imprevisto provocará una multa que dará al traste con toda la planificación. La inherente imprevisibilidad de estos acontecimientos hace imposible saber que efectos producirían en el suministro a no ser que se haga alguna clase de estudio previo. Un análisis de sensibilidad como el que propone este proyecto es idóneo para comprobarlo. Por poner un ejemplo, sigamos con el caso del barco que se retrasa. Si tenemos un modelo al que llega una cierta capacidad de suministro y que funciona durante n periodos. ¿Qué ocurre si es necesario que opere durante más tiempo con la misma capacidad? Basta con variar el parámetro que controla los periodos entre n y n+k y comprobar a partir de cuál de ellos el problema deja de tener solución. Esta sería la tolerancia del sistema al desabastecimiento.
Pasemos a hora a conocer en detalle que compone una red de suministro de gas. Cada una de estas redes cuenta con una serie de elementos básicos.
Componentes
Suministro
Como ya se ha dicho, los puntos de suministro son los lugares por los que entra gas al sistema. Esto puede tomar varias formas, desde gasoductos conectados con otros países, puertos a los que llegan buques cargados de gas licuado (previamente es necesario convertirlo de nuevo en gas en una planta regasificación) o directamente, puntos de extracción. Sin embargo y a la hora de planificar, el único parámetro que nos interesa es cuanta capacidad pueden suministrar.
Conducciones
Las conducciones o gasoductos son las tuberías por las que circula el gas. Pueden tener uno o más puntos de demanda en los que el gas abandona el sistema y que es necesario satisfacer de forma que no se produzca inanición en los consumidores. Además es necesario que la presión del gas en el interior de los mismos esté dentro de los parámetros de seguridad.
Almacenamiento
El gas se almacena de manera temporal en determinadas cantidades en unas instalaciones subterráneas. En estas instalaciones se puede introducir o extraer gas a una tasa variable y tienen una capacidad máxima que no se puede superar.
Estaciones de compresión
Mediante las estaciones de comprensión se aplica presión al gas de manera que puedan vencer las diferencias de nivel y el rozamiento de las tuberías. Si la necesidad de utilizar las estaciones de compresión se reduce, el consumo general es menor y por tanto mayor beneficio para la empresa siempre que se satisfaga la demanda. Por supuesto las estaciones de compresión pueden trabajar a varias intensidades y su consumo depende como es obvio de estas.
Modelado
Crear un modelo matemático de la red es siempre una tarea complicada y puede crearse un modelo tan complejo como se desee.
Para empezar hay que comentar que el modelo se mueve en dos dimensiones: espacial y temporal. En la primera entra en juego la colocación de los diversos elementos dentro del modelo. La dimensión temporal viene determinada por el carácter multiperiodo del modelo. Para cada periodo habrá que definir unas variables de entrada para cada elemento y el modelo se encargará de devolver una salida en función de las mismas y posiblemente del estado en el periodo anterior. Vamos a analizar cada elemento en función de los parámetros citados, a saber variables de entrada, variables de salida y restricciones que debe cumplir. Este sistema de restricciones nos vendrá bien luego a la hora de definir le modelo en un lenguaje de optimización matemática.
Suministro
El modelo de suministro consta únicamente de una variable que índica la cantidad de gas que entra en el sistema en cada periodo y punto de suministro. La única restricción que se debe cumplir es que no exceda la capacidad límite del sistema.
Conducciones
En esta versión del modelo se contemplan conducciones en las que el gas puede circular en ambas direcciones, pero solo en una de ellas en un periodo dado. Por tanto:
- Variables de entrada: La cantidad de gas que hay en la tubería en el instante cero.
- Variables de salida: Por cada periodo, la dirección en la que circula el gas, el flujo de entrada y el de salida.
- Restricciones:
- El flujo de salida en un instante dado es igual al flujo de entrada en ese instante más la cantidad de gas que contenía la tubería en el instante anterior menos la cantidad que queda en el instante actual. Hay que restar además el gas que sale de la tubería hacia el exterior del sistema para satisfacer una demanda.
- La cantidad de gas que hay en la tubería no excede las limitaciones estructurales de la misma.
Almacenamiento
El modelo de almacenamiento también es bidireccional, esto permite tanto la introducción de gas en el depósito como su extracción, pero una vez más solo una de las dos operaciones está permitida por periodo.
- Variables de entrada: Cantidad de gas en el almacenamiento en el instante inicial.
- Variables de salida: Cantidad de gas, dirección y tasa de entrada/salida en cada periodo.
- Restricciones:
- El almacén no excede una capacidad máxima.
- El estado del almacén en un instante es el estado en el instante anterior más el flujo de entrada/salida.
Estaciones de compresión
El modelo permite que cambie la dirección de compresión de una estación en cada período, si es necesario. Ya que se trata del objeto cuyo consumo se intenta modelar, es el más complicado de todos.
- Variables de entrada: Número de posiciones de funcionamiento, flujo mínimo y máximo que soporta cada una de ellas y consumo de las mismas.
- Variables de salida: Dirección de bombeo y cantidad bombeada.
- Restricciones:
- La cantidad bombeada en un momento dado está dentro de los parámetros de seguridad y se bombea en una única dirección.
- La cantidad bombeada en un momento dado está dentro de los parámetros de seguridad y se bombea en una única dirección.
Una vez definidos los modelos de los elementos individuales hay que modelar el sistema en sí. Al final, este no es más que un sistema de interconexiones entre cada uno de ellos. Se debe cumplir que en cualquiera de los nodos del sistema (Lugares en los que se conectan dos o más elementos) la cantidad de gas que entre y salga del mismo sea igual. Por lo tanto y para seguir con el método anterior se añade una restricción extra por nodo reflejando esta situación.
Programación matemática
Programación Lineal
La programación lineal es un tipo de programación matemática para resolver problemas lineales, en especial problemas logísticos. La programación lineal estudia la optimización (minimización o maximización) de una función lineal que satisface un conjunto de restricciones lineales de igualdad y/o desigualdad.
Definimos un problema lineal como un problema que puede ser representado de la forma canónica:
Minimizar: cT x
Sujeto a: Ax ≤ b
y: x ≥ 0
donde x es el vector de variables a ser determinadas, cT y b vectores de coeficientes conocidos (cT traspuesto) y A una matriz de coeficientes conocidos a su vez. Esta clase de problemas pueden ser resueltos en tiempo polinomial.
Un modelo de programación lineal consta de varias partes:
- Variables de decisión: Representan los elementos del sistema a modelar que son controlables por el decisor.
- Restricciones: Representan las limitaciones de los recursos o las imposiciones físicas de la realidad. Se representan como ecuaciones o inecuaciones. Para un modelo de gas, podrían ser las capacidades máximas de los almacenes o el límite de presión de las estaciones de compresión.
- La función objetivo: Es el valor que se intenta maximizar o minimizar. En nuestro caso es la función que define el consumo de las estaciones de compresión.
Programación lineal entera mixta (MILP)
Si en un problema de de programación lineal se exige que algunas de las variables desconocidas (el vector x en el ejemplo anterior) sean enteras, nos encontramos con un problema de programación lineal entera mixta. Esto presenta dos inconvenientes. Por un lado esta clase de problemas son NP-difíciles. Por el otro un análisis de sensibilidad sobre sus parámetros no puede hacerse analíticamente. El primero de los inconvenientes sin embargo no es tal para este proyecto en particular debido a que existen resolutores comerciales de problemas MILP muy eficientes como CPLEX. Para llevar a cabo esta tarea dispone de métodos como el de branch & bound y el de los planos cortantes que explicaremos en la siguiente sección.
Una vez definidas estas partes, el problema y su solución puede representarse en un espacio de n dimensiones, siendo n el número de variables de decisión. Las restricciones acotan una parte de este espacio y dan lugar a una "región de factibilidad". Si esta es vacía entonces el problema no tendrá solución. Si no lo es, dependiendo de si está acotada podemos hablar de problemas acotados (con una o múltiples soluciones) y no acotados (con infinitas soluciones).
Programación por restricciones
La programación por restricciones es un paradigma de programación en el cual las relaciones entre variables vienen dadas por restricciones. La principal diferencia entre este paradigma y el más clásico de programación imperativa es que las restricciones no se ejecutan secuencialmente como es el caso de las instrucciones en un programa imperativo. Esto hace que la programación por restricciones sea un tipo de programación declarativa.
Como se ha explicado antes, el modelo del sistema de gas se expresa como un conjunto de variables y otro de restricciones que simulan el comportamiento. Usando el modelo de programación lineal descrito en el apartado anterior es posible formular todo el modelo como un programa, de tal forma que pueda ser analizado por un intérprete y resuelto. Sin embargo esto puede no ser trivial como veremos a continuación.
Hacia OPL
La programación lineal y la optimización combinatoria son problemáticas generales y comunes en muchas áreas de la ingeniería y la computación, como la planificación, secuenciación, configuración, diseño, administración y asignación de recursos. Sin embargo, es un reto el hecho de expresarlos, formularlos y formalizarlos adecuadamente.
Lenguajes algebraicos de modelado
Los lenguajes de modelado de problemas de optimización son lenguajes declarativos con una sintaxis próxima a la especificación matemática de estos de problemas. En esencia constituyen una interfaz de programación declarativa a través de la cual se utiliza el resolutor lineal de una forma más cómoda y productiva para el diseñador. Suelen disponer de recursos específicos para ayudar a la depuración del modelo. En el siguiente esquema hemos representado su ubicación en el proceso de resolución de un problema de optimización:
Aunque existen muchos lenguajes algebraicos de modelado para problemas de programación lineal (tales como Lingo, GAMS, o OML de Microsoft), se ha optado por utilizar para este proyecto el lenguaje OPL (de las siglas en inglés de “Optimization Programming Language”), un lenguaje con una gran capacidad expresiva cuyo principal interés reside en el soporte para programar con restricciones y planificación. Además, cuenta con interesantes posibilidades de interconexión e integración con fuentes de datos y entornos de desarrollo de software. Así pues, es la opción ideal para administrar aplicaciones de localización, distribución y asignación de recursos, como es el caso de la tarea aquí desarrollada.
OPL
OPL es un lenguaje de modelado diseñado específicamente para problemas de optimización. La principal diferencia con otros lenguajes de modelado presentes en el mercado es que incluye soporte tanto para el propio modelado y la búsqueda de la solución como para la programación de restricciones. Por decirlo de otra manera, OPL permite especificar no solo el problema sino también el procedimiento de búsqueda asociado a ese problema. Por tanto OPL aúna tanto la programación matemática como la programación por restricciones de la que hemos hablado antes.
Las limitaciones e inconvenientes derivados del uso de OPL (tales como restricciones SOS1 y SOS2 pueden ser superadas manipulando el modelo generado con OPL desde un lenguaje (C#, Java, C++) que disponga de una interfaz (API) con OPL.
CPLEX
IBM ILOG CPLEX es un software de optimización creado por Robert E. Bixby y que persigue resolver problemas de programación lineal usando diferentes lenguajes para describirlos, entre ellos OPL, y utilizando el método simplex para hallar una solución. Este es un algoritmo relativamente complejo que vamos a explicaremos más adelante. Sobre CPLEX merece la pena mencionar que hoy en día es uno de los optimizadores más utilizados tanto a nivel de investigación como en el mundo empresarial. Debido a la potencia del mismo y a la gran cantidad de posibilidades que ofrece no es una herramienta al alcance del público general debido a que comprar una licencia para el uso completo del mismo requiere una importante inversión. La posibilidad de poder trabajar con CPLEX es uno de los aspectos más llamativos del proyecto y gran parte del tiempo y del esfuerzo invertido en el mismo ha recaído en comprender como funciona el optimizador y cuales son las posibilidades que ofrece.
La versión puesta a nuestra disposición incluye una interfaz basada en Eclipse que permite facilitar el uso, pero debido a la naturaleza de la aplicación que hemos desarrollado, se ha tenido que prescindir de la misma y utilizar CPLEX como una biblioteca que se añade a Visual Studio y que permite realizar las llamadas desde C#. Aunque realizar ciertas tareas requiere un conocimiento más profundo de CPLEX, la flexibilidad que esto permite compensa de sobra este inconveniente.
Un problema de programación lineal puede, para ser resuelto con CPLEX, dividirse en dos partes: Un fichero con el modelo y la extensión .mod y otro con los datos que se van a ejecutar en dicho modelo y con la extensión .dat. Aunque esta división no es absolutamente necesaria, facilita la tarea a la hora de hacer trabajar un mismo modelo con diferentes baterías de datos como se da en el caso de este proyecto.
El Método Simplex
Para explicar como funciona este algoritmo, volvamos por un momento a la representación gráfica de un modelo de programación lineal. La región del espacio definida por las restricciones no es más que un objeto geométrico de n dimensiones limitado por una serie de "caras". Esta estructura se llama Politopo y es la generalización a n dimensiones de los polígonos (dos dimensiones) y los poliedros (3 dimensiones).
Un tetraedro es un 3-politopo, un espacio tridimensional limitado por 4 planos. En un modelo de programación lineal cada cara representaría una restricción.
En especial, para el método simplex nos interesan los politopos convexos. En un politopo convexo dos puntos cualesquiera del mismo quedan unidos por una línea que está completamente contenida dentro del propio politopo. Los límites exteriores del politopo son denominados hiperplanos, que una vez más no son más que la generalización del plano a n dimensiones (De hecho un politopo de n dimensiones está limitado por hiperplanos de n-1 dimensiones) Un hiperplano divide el espacio de dimensión n en dos hemiespacios de la misma dimensión que el espacio original. Se cumple además que estos hemiespacios son convexos.
Con todo lo anterior podemos llegar a la representación de un politopo convexo de n dimensiones como una intersección de hemiespacios. Esta intersección puede representarse de forma matricial, ya que un hemiespacio se representa con una inecuación del tipo
a1x1+a2x2+...+anxn ≤ b
a11x11+a12x12+...+a1nx1n ≤ b1
a21x21+a22x22+...+a2nx2n ≤ b2
a31x31+a32x32+...+a3nx3n ≤ b3
.
.
an1xn1+an2xn2+...+annxnn ≤ b4
Siendo los coeficientes a números reales. Al final se puede reducir cualquier problema de programación lineal a este esquema de minimizar
c · x
Sujeto a:
Ax = b con xi ≥ 0
siendo x el vector de dimensión n con las variables de decisión del programa, c otro vector de dimensión n con los coeficientes de la función objetivo, A una matriz de dimensión n·p y b un vector de dimensión p con constantes. A esta representación se le llama forma estándar. Debido a que A multiplicado por x es igual a b, se hace necesario introducir una columna más en la matriz del problema original con variables que permitan expresar la igualdad. Estas variables se denominan variables de holgura si suman (para convertir ≤ en =) o de exceso si restan (para convertir ≥ en =) He aquí un ejemplo:
3x1+4x2 ≤ 6 pasa a ser 3x1+4x2+x3 = 6 (x3 variable de holgura)
3x1+4x2 ≥ 6 pasa a ser 3x1+4x2-x3 = 6 (x3 variable de exceso)
Volviendo a la representación espacial, se puede demostrar por métodos matemáticos que si la función objetivo presenta un mínimo dentro de la región factible (dentro del politopo), este valor se presenta también en al menos uno de sus puntos extremos, esto es en uno de los vértices del politopo. Por tanto, encontrar el valor que hace que la función objetivo devuelva un valor óptimo podría limitarse a explorar todos los vértices del politopo. Por desgracia, el número de vértices crece de forma exponencial al número de restricciones y debido a esto resulta impracticable utilizar este método en cualquier problema de programación lineal medianamente complejo.
Sin embargo y asimismo, también se puede demostrar que si uno de estos vértices no es el mínimo de la función objetivo existe al menos una arista que sale del vértice a lo largo de la cual la función es estrictamente decreciente. Sabiendo esto, el algoritmo simplex explora el politopo moviéndose entre vértices cada vez con un mejor valor de la función objetivo. Se procede de este modo hasta que se encuentra un mínimo o se da con un vértice no acotado, en cuyo caso el problema no tiene solución. Debido a que el número de vértices es finito el algoritmo siempre termina, aunque esto puede llevar ciertamente bastante tiempo si hubiese que visitarlos todos. En cualquier caso, como la dirección de exploración es siempre la misma se espera que el número de vértices visitados sea pequeño.
Para hallar la solución del programa lineal hace falta por tanto proceder en dos fases: Primero encontrar un vértice inicial desde el que empezar a buscar y segundo aplicar el algoritmo que se mueve entre los vértices. La primera parte puede o no ser trivial y en caso de no serlo se resuelve aplicando una versión modificada del algoritmo al problema inicial.
La eficiencia del algoritmo en el caso medio está en el orden polinómico.
Branch & Bound
El método simplex funciona bien a al hora de resolver problemas de programación lineal. Sin embargo, como ya se ha comentado, los problemas a los que nos enfrentamos en este proyecto requieren que ciertas variables sean enteras, lo que los convierte en problemas enteros lineales mixtos. En este escenario, el método simplex no es suficiente para hallar una solución, sin embargo puede utilizarse junto con otros algoritmos para hallar una solución de manera eficiente: Uno de estos algoritmos es el de branch & bound.
La idea de este método consiste en dividir el problema MILP en varios grupos. A continuación, estimando una serie de cotas para los mismos, se pueden descartar algunos de estos grupos. De esta forma se descartan candidatos en masa hasta que únicamente queda un conjunto con una posible solución o no quedan más conjuntos, en cuyo caso el problema sería irresoluble. Las fases de división (Branch) y acotación (Bound) son las que dan nombre al algoritmo.
Para un problema MILP, este es el esquema que permite encontrar la solución utilizando el método de branch & bound:
- Partiendo del problema inicial, se relajan las restricciones, de tal manera que se permite que las variables enteras tomen valores reales. Se haya la solución de este problema de programación lineal (En nuestro caso, usando el método Simplex) obteniendo una valor óptimo (cota inferior del óptimo para el problema MILP, ya que este solo añade restricciones extra al problema de programación lineal) y los valores de los parámetros (reales) que permiten alcanzar esa solución.
- Utilizando estos valores reales, se divide el problema en dos o más subproblemas. Por ejemplo, si en el problema inicial relajado, x debía tomar un valor mayor o igual que 0 y para el óptimo toma un valor de 21.2, podemos dividir el problema inicial relajado en dos: uno en el que x está en el rango de 0 a 21 y otro en el que es mayor que 21.
- Evaluamos los subproblemas con el método simplex una vez más y continuamos bifurcando para la misma u otras variables hasta que no se satisfaga que solo exista un valor entero impuesto por las restricciones de la bifurcación. Cuando lleguemos a este punto tenemos una solución entera candidata a resolver el problema.
- La bifurcación continúa por las distintas ramas del árbol. Sin embargo, si ya tenemos un candidato, la evaluación de cualquier nodo que de un valor peor que la solución candidata implica que podemos descartar esa rama con seguridad debido a que no contiene ninguna solución mejor que la que tenemos, incluso si relajásemos las restricciones.
- Si llegamos a otra solución entera mejor que la candidata, esta se actualiza y se sigue el proceso. Así mismo, si un nodo no tiene solución se descarta.
- Llegaremos a un punto en el que no existan nodos por explorar. La solución candidata en este momento representa el óptimo del problema MILP.
Planos Cortantes
Otro método que se usa en conjunción con el anterior para resolver problemas MILP. En este caso, se comienza igualmente con una relajación de las restricciones del problema. Con el problema ya relajado, se usa un resolutor de problemas de programación lineal. Si está solución asigna valores enteros a las variables, es también la solución óptima del problema sin relajaciones MILP. En caso contrario, se añade una restricción adicional al mismo. Si, volviendo a la representación gráfica del problema, vemos el espacio de soluciones como un politopo, esta nueva restricción no será más que un plano que la cortará y lo restringirá aún más. El método se repite de nuevo sobre el nuevo politopo.
Hacen falta métodos específicos para cada clase de problema si queremos encontrar planos que formen caras del politopo de soluciones enteras, ya que estos son los que más restringen el espacio de soluciones. Se ha demostrado que siempre existe un plano de este tipo que separa cualquier solución real de las soluciones enteras. Actualmente se está llevando una gran investigación en este campo para distintos tipos de problemas de optimización bajo el framework "Polyhedral combinatorics" de Aardal y Weismantel, 1997.
Algoritmos: El método de Branch & Cut
Usando los dos métodos anteriores (tres sin contamos Simplex que ambos usan) llegamos al método de "Branch & Cut". Este consiste únicamente en aplicar Planos Cortantes hasta que no se consigue encontrar ningún plano que constriña más la solución. En el espacio resultante se usa entonces "Branch & Bound" para hallarla. Este es el principal algoritmo que usa CPLEX (Con muchas más optimizaciones, por supuesto) para hallar la solución de un problema MILP.
Paralelismo
Como se mencionaba en la introducción de este documento, la finalidad de la aplicación es realizar estudios de sensibilidad de los modelos en función de un parámetro que podrá elegir el usuario. Si definimos la granularidad de ejecutar los modelos para cada uno de los parámetros por separado como la cantidad de computo que se puede hacer sin tener que transmitir información de uno a otro, observamos que la granularidad de este problema es completa. Por tanto, deberíamos tratar de explotar esto lo más posible y la mejor forma de hacerlo es realizar los cálculos simultáneamente. Para esto vamos a recurrir a una serie de conceptos que definimos a continuación.
Clúster de computadores
Un clúster de computadores es un conjunto de computadores interconectados entre sí de tal manera que a efectos de realizar ciertas tareas actúan como uno solo. Estos computadores ejecutan cada uno su propia instancia de un sistema operativo.
Debido al relativo bajo coste de un procesador de propósito general y al aumento de la velocidad de las redes también a un reducido coste, un clúster es normalmente más eficiente con respecto al costo que un único computador con la misma capacidad y velocidad.
Para aprovechar al máximo la capacidad de cálculo de cada uno de ellos, tiene que existir un nodo que controle al resto o al menos una capa intermedia de middleware desde la que se gestione la carga de cada uno de los nodos.
Computación en la nube
"La nube" es uno de los términos más en boga últimamente. Nos referimos a la nube como una infraestructura compleja que ofrece capacidad de cálculo y almacenamiento como un servicio a una serie de usuarios heterogéneos. Estos usuarios acceden a la nube a través de navegadores web o de ligeras aplicaciones de escritorio (Como la que se usa en este proyecto) o aplicaciones móviles. Según su despliegue podemos hablar de varios tipos de nubes:
- Publicas: El almacenamiento, las aplicaciones y los servicios son ofrecidas al público general por un proveedor de servicio.
- De comunidad: Son compartidas por una serie de organizaciones con preocupaciones comunes (Mismo sector, necesidades de seguridad, etc)
- Privada: Una única organización opera la nube, normalmente una empresa que ofrece los servicios a sus empleados.
- Híbrida: Incluye dos o más tipos de las anteriores entrelazadas.
Debido a la cantidad de secretos industriales que entran en juego en este proyecto, se pueden barajar dos posibilidades: La primera sería utilizar una nube privada, gestionada por la empresa que utilice la aplicación (En este caso, Enagás). La segunda sería colocarla en una nube pública que ofreciese suficiente seguridad como para poder realizar el envío de mensajes sin que estos fuesen interceptados y descodificados. Aunque la primera parece, a priori, mejor poder externalizar la gestión de la infraestructura que da apoyo a la aplicación (Como en el caso de colocarla en un servidor externo de Amazon, por ejemplo) es algo deseable y que a la larga provoca grandes ahorros económicos. Esto se debe a que en general, esta clase de nubes públicas se pagan por uso: solo se pagaría por los recursos utilizados en el momento en el que se realiza el análisis, sin necesidad de realizar mantenimiento de ningún tipo si ocurre lo contrario. Se entrará más afondo en las utilizaciones en esta clase de nubes públicas en el capítulo 4: Posibles ampliaciones.
Sobre los modelos de servicio que ofrece la nube, existen tres niveles: Infraestructura (Ofrecer máquinas, virtuales o no), plataforma (Ofrecer bases de datos, sistemas operativos, etc) o software (Aplicaciones concretas). El segundo es la que más nos interesa. El modelo de Plataforma Como Servicio (Platform as a Service o PaaS) permite al usuario crear software y colocarlo en el proveedor, que ofrece la red, los servidores y el almacenamiento.
Servicios Web
Un servicio web es un sistema software diseñado para ofrecer interacción entre ordenadores. Esto se realiza a base de pares petición-respuesta codificados como mensajes de texto en formato .xml.
Un servicio web posee una interfaz en WSDL (del inglés Web Service Description Language o Lenguaje de Descripción de Servicios Web) que no es más que un lenguaje basado en XML que puede ser leído por una máquina y que describe de que forma puede ser llamado un servicio web, que parámetros admite y que estructuras de datos devuelve. La estructura básica de un fichero en WSDL consta de los siguientes apartados
- <types>: Tipos de datos usados en los mensajes
- <message>: Elementos del mensaje cada uno de un tipo definido en la parte anterior
- <portType> Operaciones permitidas y mensajes intercambiados
- <binding> Protocolos de comunicación usados
Gracias a esto, un servicio web es idóneo para intercambiar datos entre aplicaciones, independientemente del lenguaje en que estén programadas y de las máquinas en las que se encuentren las mismas.
Otra de las principales ventajas de los servicios web es que en gran medida son independientes de las aplicaciones que los consumen, lo que hace que a la hora de realizar modificaciones en uno de los dos extremos –aplicación o servicio- no tengamos que realizar ajustes en el otro. Dada la repercusión que tiene hoy día el paradigma de programación orientada a componentes, se cree que esta flexibilidad aportada por los servicios web los ayudará a tener mucha presencia en adelante y revertirá en un mayor uso de estos, aumentándose la cantidad y calidad de los servicios web.
Sin embargo, no están exentos de algunos inconvenientes importantes. Entre estos encontramos por un lado un pobre desarrollo de transaccionabilidad y de rendimiento de procesamiento si se compara con otros modelos de programación distribuida. El problema del rendimiento viene intrínsecamente ligado a la propia naturaleza del servicio, dado que está basado en XML. La otra gran desventaja es de seguridad, y es que al basarse en HTTP, pueden transgredir las reglas de los firewall.
Llamada a procedimiento remoto
Un servicio web puede ser usado de varias formas diferentes. Para este proyecto en particular nos interesa el de “Llamada a procedimiento remoto” (Remote Procedure Call o RPC) Este es un proceso de comunicación que provoca que una subrutina sea ejecutada en espacio de direcciones dife- rente (en nuestro caso, una máquina diferente) y que provee la forma de hacerlo sin tener que administrar directamente la tarea, únicamente haciendo una llamada a subrutina como si se tratase de la misma máquina. Esto sigue un paradigma cliente-servidor, siendo el cliente la máquina que realiza la petición y el servidor la que ejecuta el método y devuelve los resultados de dicha ejecución. Durante una invocación a un procedimiento remoto se realizan una serie de pasos
- El cliente ejecuta localmente un segmento de código (stub) que adecua los parámetros para realizar la llamada (Por ejemplo, los punteros tienen que ser convertidos ya que no tienen sentido en el espacio de memoria de la otra máquina).
- Este mismo segmento de código empaqueta los parámetros en un mensaje y hace una llamada al sistema para enviar dicho mensaje. Este empaquetamiento se conoce como “marshalling” y es similar a la serialización.
- El sistema operativo del cliente envía el mensaje a la máquina que actúa como servidor
- El sistema operativo del servidor pasa los parámetros al “stub” del mismo
- Este último hace la llamada al procedimiento.
- La respuesta se envía al cliente siguiente la secuencia inversa.
SOAP
Los mensajes que se describen en el apartado anterior requieren enviarse bajo cierto protocolo para que puedan transitar por la red y recibirse correctamente en su destino. El protocolo que usamos para ello se denomina SOAP (Simple Object Access Protocol o Protocolo de Acceso a Objeto Simple) Este es una especificación para el intercambio de información estructurada (Básicamente, archivos .xml) en el marco de un servicio web. Usualmente utiliza otro protocolo de la capa de Aplicación del modelo OSI, siendo el más notable de ellos HTTP.
SOAP proporciona un framework de mensajería sobre el que se puede construir el servicio web. Consta de tres partes:
- Un envoltorio, que define que es un mensaje y como procesarlo.
- Unas reglas de codificación para expresar las instancias de tipos de datos definidos por las aplicaciones.
- Un convenio para representar las llamadas a procedimientos y las respuestas de estos.
Así mismo, un mensaje SOAP está estructurado también en tres partes: Envoltorio, cabecera y contenido.
Como se ha comentado, SOAP puede utilizar HTTP como protocolo de la capa de aplicación para transporte. Además de esto, se puede utilizar HTTPS, lo que es muy relevante para la aplicación ya que los datos que se envían bien podrían declararse secreto industrial.
La Pila de Protocolos del Servicio Web
Una vez definidos todos los conceptos y protocolos anteriores vamos a ver como se estructuran dentro del servicio web. Esta estructura sigue un esquema de capas o bloques, apilados uno encima del otro en lo que se llama la Pila de Protocolos del Servicio Web. Esta incluye cuatro capas, de arriba a abajo en la pila:
- Protocolo de transporte: Se encarga de llevar los mensajes entre aplicaciones basadas en red e incluye protocolos como el citado HTTP, SMTP o FTP.
- Protocolo de mensajería: Se encarga de codificar los mensajes como XML para que puedan ser leídos por ambas partes de la conexión. Actualmente los más usados son XML-RPC, WS-Adressing y SOAP.
- Protocolo de descripción: Se usa para describir la interfaz pública del servicio web. El lenguaje WSDL es el estándar para este propósito.
- Protocolo de descubrimiento: Centraliza un registro común de servicios web a través de la red de forma que sea más fácil descubrir que servicios están disponibles. Es de menor interés para este proyecto.
