Algo llamado FADA

Federated Advanced Directory Architecture

(IST-1999-13015 / IST-2001-35113)

Introducción

El modelo tradicional de construcción del software, monolítico y centralizado, ha resuelto y resuelve satisfactoriamente los problemas de cálculo y gestión de datos que se le han ido demandando hasta la fecha. Sin embargo, ese modelo llega a sus límites cuando las arquitecturas software van ganando complejidad. Paralelamente al incremento de la complejidad, a los sistemas se les demanda mayores niveles de disponibilidad, a la vez que se realiza su despliegue sobre infraestructuras frágiles, como puedan ser las nuevas redes inalámbricas (Wireless). La aparición de nuevos escenarios de ejecución de software, exige la adopción de nuevas soluciones. El paradigma peer to peer (P2P) en el contexto de una Scale-Free Network, ha arrojado nueva luz sobre lo que este paradigma aplicado a las tecnologías de la información pueden brindarnos.

La linea de investigación abierta con FADA (http://fada.sourceforge.net), aunque todavía dista de resolver todos los problemas planteados, ha proporcionado resultados alentadores en situaciones de fallo reiterado que, para otras tecnologías, habrían resultado catastróficos. Así pues, la infraestructura FADA abre una nueva línea de investigación en el desarrollo de aplicaciones distribuidas de tal forma que, a la vez que facilita la movilidad geográfica de las mismas, permite la autoorganización de los componentes y su resistencia a fallos aleatorios a imagen y semejanza de los organismos vivos, que han sido su fuente de inspiración.

Origen del proyecto

El proyecto FETISH (Federated European Tourism Information System Harmonisation IST-1999-13015) y su posterior evolución DAFNE (IST-2001-35113) fueron dos iniciativas de la comisión europea dentro del quinto programa marco, iniciadas en enero del año 2000. El proyecto FETISH/DAFNE nació con el objeto de facilitar una plataforma B2B a las PYMES Europeas, haciendo especial hincapié en las del sector turístico que, por su dispersión y escasa capacidad financiera, no tienen acceso a sofisticados sistemas de información, ni a canales de distribución masiva.

Como ejemplo paradigmático de PYMES a quienes se dirigía el proyecto tenemos restaurantes, pequeños hoteles, albergues, casas de turismo rural, etc... El objetivo final debía ser la integración de los servicios ofertados por cada una de estas PYMES, sin que la presencia en Internet les supusiese una inversión extra en temas no relacionados con su negocio (es decir, en sistemas de información). Para ello, se debía diseñar una infraestructura software (el middleware FADA) capaz de facilitar la interacción entre el software ya existente en las diferentes empresas, de un modo desatendido. En otras palabras, el sistema debía operarse automáticamente, sin intervención humana, y debía ser capaz de recuperarse ante fallos parciales, reorganizando el acceso a los servicios.

Por otro lado, al estar dirigido a empresas con poca o nula infraestructura, los requerimientos del sistema debían ser mínimos. Por lo tanto, puesto que el único elemento tecnológico común a, prácticamente, cualquier ciudadano es el teléfono móvil, el sistema debía ser capaz de integrar a éstos en la plataforma B2B.

Para evitar el riesgo de control indeseado, el sistema en su conjunto no podía pertenecer a nadie, lo que comportaría que nadie iba a proceder a su mantenimiento y operación. Así pues, había que eliminar la necesidad de mantenimiento y administración (eliminando así la mayor fuente de errores en los sistemas de información) y por tanto había que diseñar el sistema con capacidad de regeneración y autoorganización.

Escenario

En el escenario típico para el que se diseño el sistema, el propietario un pequeño negocio conectaría su teléfono móvil al inicio de su jornada laboral. Dentro del dispositivo, la aplicación/agenda en que se lleva el control de las reservas del, pongamos por ejemplo, restaurante se activaría registrándose (analizaremos después cómo) en la red. A partir de ese instante, todas las aplicaciones que lo deseen (y sepan cómo hacerlo) se encuentran en disposición de cooperar con el software que se ejecuta en el teléfono móvil.

El pequeño restaurante, tiene visibilidad en los portales de ocio, turísticos, de cadenas hoteleras, etc. Las reservas hechas a través de dichos canales, están consultando la disponibilidad de mesas que gestiona su teléfono móvil, y aceptando reservas en función de la disponibilidad de mesas, calendario. En el momento en el que, por las razones que fuera, el teléfono móvil deja de estar activo (apagado, fuera de cobertura...) el servicio desaparece de todos aquellos lugares desde los que sería posible utilizarlo. En el momento en que el teléfono reaparece en la red del operador (sea éste el que sea), el servicio reaparece en Internet y vuelve a integrarse en todas aquellas aplicaciones de reserva de las que formaba parte. Llegados a este punto, observamos que uno de los primeros problemas a resolver es el de las apariciones y desapariciones de los servicios con los consiguientes cambios de IP (dirección de Internet asignada a un ordenador / teléfono móvil).

El problema de la movilidad

En Internet (red IP), desde su concepción en 1969, se ha asumido que los servidores (y, por tanto, los servicios) son inamovibles. La red IP se diseñó como una red estática, con capacidad, eso si, de enrutamiento dinámico. Precisamente es su capacidad de enrutamiento dinámico la que ha sido la clave de su éxito. La red IP se autoreconfigura por construcción. Treinta años después, con la irrupción de las redes inalámbricas (wireless), contamos con gran cantidad de redes en las que los nodos que la conforman (potenciales servidores) cambian de ubicación constantemente. A pesar de ello, seguimos manteniendo el paradigma que tan buenos resultados ha dado: El servicio y el servidor están íntimamente ligados a una dirección IP, es decir, se suponen inmóviles.

Sin embargo, la realidad nos demuestra que los ordenadores cambian constantemente de ubicación (Laptops, PDAs, Teléfonos Celulares, etc...), que las redes ya no son infraestructuras fijas (disponemos de redes wireless como Bluetooth, GPRS, UMTS, WiFi 802.11, etc...). Por lo tanto, ¿por qué suponer que los servidores no van a cambiar de ubicación constantemente? ¿Qué necesidad hay de interrumpir el servicio por una cuestión de movilidad?

Volviendo a nuestro problema: Si el teléfono móvil cambia de operador al cambiar de celda, ¿el servicio que proporciona es el mismo?. Obviamente si. Sin embargo, no es así para el nivel de red. La idea debe ser, en consecuencia, la de obviar el nivel de red de transporte, para centrar la capacidad de movilidad en el servicio.

¿Qué significa movilidad de servicio?

Significa que para acceder a un determinado servicio, todo lo que se necesita es que éste exista, con independencia de su ubicación geográfica. El sistema debe resolver por nosotros la localización del servicio. De hecho, el que un servicio quede "ligado" a una determinada IP (esto es, a una ubicación geográfica) no es mas que una deficiencia en la capacidad de abstracción brindada por la pila (stack) de protocolos de red utilizado.

¿Cómo conseguir servicios móviles?

Para brindar servicios utilizables, a pesar de la movilidad del dispositivo que los soporta, necesitamos de una infraestructura que relacione el servicio (que así percibiremos como fijo) con el dispositivo que lo proporciona (que supondremos intrínsecamente móvil). La solución evidente, es la de disponer de una estructura de datos (directorio), por todos conocida, que mantenga la relación entre el elemento que deseamos percibir como inmóvil (el servicio) y el elemento móvil (en nuestro caso, el teléfono móvil) que nos proporcione un mecanismo de acceso universal al servicio.

FADA aparece como respuesta a esta necesidad. La red FADA se ha diseñado para ser un sistema de información distribuido, puesto que el uso de una solución centralizada hubiera generado la aparición de un "talón de Aquiles" (single point of failure) en el propio repositorio de servicios. FADA proporciona la referencia a cualquier elemento móvil, siendo capaz de soportar fallos parciales del sistema y recuperando, sin intervención humana, la funcionalidad completa del sistema.

¿Qué significa proporcionar un mecanismo de acceso universal a un servicio?

Imaginemos que, cuando fuéramos a hablar con alguien de distinta lengua, éste nos proporcionase un "aparato" que llevase a cabo la traducción de nuestro idioma al suyo. La comunicación entre individuos de diferentes orígenes se simplificaría muchísimo, puesto que bastaría el intercambio de "traductores" cada vez que deseáramos comunicarnos con alguien de diferente lengua. Sin embargo, eso plantea la dificultad de crear tantos aparatos traductores diferentes como combinaciones de lenguas sean posibles.

Un modo de simplificar el problema, sin restarle funcionalidad, es la de diseñar un traductor de cada lengua a una lengua común, acordada por todos previamente.

En este caso, nuestro interlocutor deberá proporcionarnos el traductor de la lengua común a la suya, porque se presupone que nosotros sabemos hacer la conversión de nuestra lengua materna a la lengua común y viceversa.

En el caso que nos ocupa. La lengua común escogida es Java™. La elección de Java™ como elemento común parecía evidente. Java™ produce código ejecutable independiente de la plataforma en la que se desarrolla, lo que nos garantiza su validez en cualquier ordenador, sistema operativo o dispositivo. Adicionalmente, Java™ permite la movilidad del código a través de la red (basándose en la mencionada independencia de plataforma que le caracteriza) en tiempo de ejecución.

Así, cada servicio susceptible de ser registrado en la red FADA, debe implementar un elemento software, al que denominaremos "proxy" (delegado), que facilita el acceso al servicio proporcionado. El proxy debe estar escrito en Java, para garantizar que podrá ser interpretado por cualquier combinación de hardware + sistema operativo que pueda encontrarse en Internet. Sin embargo, ¿cómo habla el proxy con el servicio para el que ha sido concebido?. La comunicación entre el proxy y el servicio, es algo que solo compete a quien lo proporciona, puesto que hablan en su "lengua nativa".

¿Cómo se ha diseñado la red FADA?

Para que un dispositivo pase a engrosar el conjunto de nodos que conforman el Directorio virtual FADA, notifica su presencia a uno o mas nodos, pasando formar parte activa de la infraestructura. Los nodos que forman el directorio FADA no siguen ningún orden preestablecido en sus conexiones [2,3]. Se dice que no siguen topología alguna, que es una red aleatoria [4].

Sin embargo, FADA no es una red absolutamente aleatoria. La red FADA es la primera infraestructura software que se ha diseñado de modo que conforme una Scale-Free Network [15], heredando así todas las propiedades de robustez y autoorganización que caracterizan a estas redes [18]. Por lo tanto FADA, como toda Scale-Free Network es una infraestructura recursiva [16,17] compuesta de elementos de la misma naturaleza que el todo: FADA es la suma de todos los nodos FADA.

Uso de la red FADA

El objetivo principal del directorio virtual formado por la federación de nodos FADA es el almacenamiento y recuperación de proxies de servicio. Un proveedor de servicio registra este proxy en un nodo FADA cualquiera. A partir de ese momento el proxy de servicio puede ser encontrado desde cualquier otro punto de la red.

Una de las características principales de FADA es la práctica ausencia de necesidad de mantener y actualizar el directorio de servicios. Un fallo en el lado del proveedor de servicios puede provocar la caída del servicio, con lo que el proxy de este servicio, si bien funciona perfectamente, no puede facilitar a los clientes el acceso a dicho servicio. Para evitar este problema es necesario ligar la existencia del proxy en el directorio FADA, a la vida del servicio mismo.

El modo en que FADA aborda esta cuestión es mediante el establecimiento de un "contrato de alquiler" (lease) entre el servicio y FADA, por el cual se establecen periodos de permanencia del servicio en la lista de servicios activos. Un proveedor de servicio no puede registrar un proxy en FADA a perpetuidad, si no que FADA le asegura que el proxy permanecerá en el registro de directorio por un tiempo determinado, negociable y negociado con el proveedor de servicio. FADA devuelve al proveedor de servicio un lease, una entidad que representa el intervalo de validez del registro del proxy. Los leases, como cualquier contrato de alquiler, tienen un periodo de vigencia pasado el cual caducan. La caducidad de un lease provoca la eliminación silenciosa del proxy de servicio del directorio FADA. Para evitar que el lease caduque, el proveedor de servicio debe renovar el contrato periódicamente. Cada vez que se renueva el contrato(lease) debe renegociarse de nuevo, con el nodo FADA correspondiente, el intervalo de vigencia del mismo.

Si se produce un fallo en el lado del servidor, a éste le resultara imposible renovar el lease. Una vez pasado el tiempo de lease, éste caduca, y el proxy de servicio al que va ligado desaparecerá de la red FADA. De este modo FADA solo ofrece a los clientes los proxies de los servicios que funcionan correctamente.

Recuperación de proxies de servicio

Un cliente de FADA realiza una búsqueda de proxies de servicio, dando una serie de parámetros como requisitos de la búsqueda. En función de estos parámetros, la infraestructura FADA seleccionan un grupo de proxies de entre todos los existentes en la red. El mas importante de estos parámetros es el mecanismo de acceso al servicio en que se basa el cliente (la interface Java). El cliente obtiene un conjunto de proxies que cumplen con los parámetros especificados. Este conjunto puede ser nulo, si los parametros fueron muy restrictivos, o no existe ningún proxy en todo el directorio que cumpla con los requisitos del cliente.

Una vez el cliente obtiene el conjunto de proxies que sabe manejar (porque conoce su contrato) puede seleccionar uno de ellos al azar, o afinar su búsqueda para escoger el que mejor se adapte a sus necesidades.

Búsqueda de proxies en el directorio FADA

Un cliente puede acceder a FADA escogiendo cualquiera de sus nodos. Cuando el cliente realiza una petición de búsqueda en un nodo, dicho nodo difunde esta petición a otros nodos [1,5]. Todos aquellos nodos que encuentran proxies que cumplan con los requisitos de la búsqueda, notifican dichos resultados al nodo que inicio la búsqueda. Al finalizarse la búsqueda el primer nodo devuelve los resultados al cliente.

Estos resultados son identificadores únicos en todo el directorio, lo que permite al cliente pedirle el proxy directamente al nodo que lo contiene. Esto permite al cliente y a los nodos del directorio ahorrar ancho de banda y tiempo al obtener los proxies, ya que no es necesario obtenerlos todos si solo se va a usar uno.

La búsqueda de proxies puede devolver un número exagerado de respuestas. Es necesario limitar el tamaño de la respuesta. La restricción de los resultados obtenidos, se puede aplicar en base a diversos mecanismos. El primero de ellos es el numero de saltos (hops) máximos que una petición de búsqueda puede dar a partir del nodo origen de la búsqueda. No deja de ser una medida de la distancia a la que vamos a buscar respuestas. De esta manera solo se transmite la petición a los nodos FADA que estén dentro de un radio determinado a partir del nodo origen. Al tratarse FADA de una Scale-Free Network, el radio seleccionado determina el tanto por ciento de la red que se explora en cada petición [16].

El segundo es el límite en el número de respuestas recolectadas. Típicamente, un cliente está interesado en obtener solo un proxy, aunque es posible que quiera obtener un número mayor, y hacer un filtrado local de los obtenidos. Cuando el nodo FADA interrogado por el cliente ha obtenido el número de respuestas deseado, dicho nodo devuelve los resultados al cliente. Como cabe dentro de lo posible que no existan suficientes respuestas para cumplir los requisitos del usuario, éste puede indicar también la duración deseada para la búsqueda. Si en ese intervalo de tiempo no se ha recibido el número solicitado de respuestas, el nodo FADA interrogado devolverá los resultados obtenidos hasta ese momento, descartando ulteriores respuestas para esa búsqueda.

Latencia (Delay) de la red: un problema

El tiempo transcurrido entre que se solicita un recurso en la red y éste se recibe depende de diferentes variables. La latencia (delay) de la red es una de ellas. Esta latencia puede variar ampliamente a lo largo del tiempo, especialmente en redes de área extensa (WAN), y esta fuera de la capacidad de predicción de cualquier usuario de dicha red. Este retardo de red introduce una dificultad adicional en el proceso de renovación de lease. Los leases deben ser renovados periódicamente para asegurar que no caducan. Esta periodicidad no puede ser muy alta, porque entonces se satura la red con mensajes de petición de renovación. Pero tampoco puede ser excesivamente baja, porque entonces se corre el riesgo de que los retardos intrínsecos de la red hagan que la petición de renovación llegue cuando el lease ya ha expirado y, por tanto, el proxy de servicio ya ha sido borrado.

Se requiere, entonces, ajustar la frecuencia de renovación, a las condiciones de transmisión de la red. Así pues, determinar las condiciones de transmisión de la red, es decir, la latencia, es la clave para optimizar la frecuencia de renovación de lease y ha sido uno de los grandes obstáculos que FADA resuelve.

El filtro de Kalman

La estrategia adoptada en la red FADA, es la de usar la técnica del filtrado de Kalman (Rudolf Kalman - http://www.cs.unc.edu/~welch/kalman/kalmanBiblio.htm) para obtener una estimación fiable del retardo [7,9,12]. El filtro de Kalman ofrece una estima de una cantidad (en nuestro caso retardo) a partir de muestras de dicha cantidad, incluso, cuando dicha muestra tiene una baja fiabilidad [10,11]. El filtro de Kalman ofrece la ventaja de elaborar una predicción, sin tener que almacenar la historia de la variable predicha y estableciendo el grado de confianza que se tiene de cada predicción hecha [8].

Con estas estimaciones en mano, sus márgenes de confianza, y el tiempo de caducidad del lease resulta posible calcular cuándo se debe transmitir la petición de renovación de un lease para garantizar su eficacia. Cabe, por supuesto, la posibilidad de que dicha petición llegue tarde, puesto que el retardo de la red es impredecible al cien por cien (en este momento la tasa de acierto con el modelo matemático aplicado es del 95%). Pero FADA incorpora mecanismos automáticos para registrar de nuevo los proxies de servicio que resulten, de este modo, borrados accidentalmente.

Regeneración y autoorganización de la red FADA

La caída de un nodo FADA no produce un fallo en el sistema, puesto que los nodos colaboran entre ellos para proporcionar la funcionalidad requerida a base de redundancia y apoyándose en la especial topología de la red FADA [18]. El proveedor de servicios, sin embargo, esta renovando su lease en un determinado nodo FADA. La red FADA provee de los mecanismos necesarios para detectar la caída de un nodo, y para desencadenar el registro de los proxies de servicio alojados en dicho nodo, en otro nodo cualquiera de la red. De esta manera se garantiza la alta disponibilidad del sistema. El concepto de redundancia aplicado, no ya a la red FADA, si no al conjunto de servicios que la utilizan y sobre la que se construyen, es el que permite el desarrollo de sistemas regenerativos (self-healing) tal y como propone Dave Sag en su artículo "Using Jini to Build a Catastrophe Resistant System" (http://www.onjava.com/pub/a/onjava/2002/05/01/911proof.html).

Esta aproximación al desarrollo de Software permite crear, por primera vez, infraestructuras tolerantes a fallos. A imagen y semejanza del comportamiento presentado por los seres vivos [19], FADA es una infraestructura diseñada, no solo para dar soporte a la movilidad de servicios, si no que garantiza la supervivencia de los servicios (y de las aplicaciones construidas aglutinando esos servicios). FADA facilita la distribución por la red (lo que significa la distribución por ubicaciones geográficas diferentes) de componentes de software y permite, por diseño, la regeneración de aplicaciones dañadas.

Seguridad

La descarga de código remoto abre la puerta a los usuarios maliciosos para romper la seguridad del sistema del usuario final. Para evitar este problema se ha dotado a FADA de los medios para firmar digitalmente tanto los datos como el código que viajan por la red. De esta manera se minimiza el riesgo inherente a la recepción de datos y, sobre todo, de código que proviene de una fuente remota.

Resultados obtenidos

La aplicación de nuevos paradigmas a la construcción de sistemas distribuidos, nos está enfrentando a problemas que, una vez resueltos, abren nuevas posibilidades al desarrollo de software.

Dentro del ámbito del FETISH / DAFNE, se han desarrollado nuevos compiladores para la generación de los stubs que implementan los protocolos adoptados, se han ideado mecanismos para atravesar firewalls de una manera transparente, se ha elaborado un nuevo modelo matemático para la predicción de latencias en red, se han desarrollado nuevos algoritmos de comportamiento del software que propician modelos de comportamiento complejos a través de sus interacciones (Scale-Free Networks), permitiendo la reacción del sistema a agresiones externas, etc...

En particular, es un hecho especialmente recalcable el haber establecido un nuevo escenario de integración, en el que las diferentes aplicaciones negocian cómo cooperar entre ellas, sin que ello requiera la intervención humana. El ámbito de aplicación ha ido mucho mas lejos de lo previsto al inicio del proyecto y FADA se esta utilizando no solo para integrar aplicaciones entre dispositivos móviles, sino que también para llevar integrar Web Services, en portales privados o las interacciones entre diferentes organismos de administraciones públicas.

Como conclusión, podemos afirmar que la adopción de modelos de comportamiento, inspirados en la biología, al diseño y construcción de software, marcan el punto de partida a una nueva generación de aplicaciones que, basándose en estas tecnologías, serán capaces de evolucionar al mismo ritmo en que lo hace el medio en que se ejecutan, recuperándose de fallos parciales sin que se resienta su funcionalidad.

Referencias:

Grafos

[1] Leqiang Bai, Hajime Maeda: A Broadcasting Algorithm with Time and Message Optimum on Arrangement Graphs. Journal of Graph Algorithms and Applications. http://www.cs.brown.edu/publications/jgaa/ vol. 2, no. 2, pp. 1-17 (1998)

[2] P. Berthomé, A. Ferreira, S. Perennes: Optimal Information Dissemination in Star and Pancake Networks.

[3] M. Frans Kaashoek, Andrew S. Tanenbaum, Susan Flynn Hummel, Henri E. Bal: An Efficient Reliable Broadcast Protocol

[4]John Sucec, Ivan Marsic: An Efficient Distributed Network-Wide Broadcast Algorithm for Mobile Ad Hoc Networks.

[5]Yu-Chee Tseng, Wu-Lin Chang, Jang-Ping Sheu: Efficient All-to-All Broadcast in Star Graph Interconnection Networks. Proc. Natl. Sci. Counc. ROC(A) Vol. 22, No. 6, 1998. pp. 811-819.

Jini en Internet

[6]Ahmed Al-Theneyan, Piyush Mehrotra, Mohammad Zubair: Enhancing Jini for Use Across Non-Multicastable Networks.

El filtro de Kalman

[7]Peter D. Joseph: Introductory Lesson to the Kalman Filter.

[8]Peter S. Maybeck: Stochastic models, estimation, and control. Volume 1.

[9]Patrick D. O'Malley: Use of a Kalman Filter to Improve Realtime Video Stream Image Processing: An Example.

[10]Phillip D. Stroud: A Recursive Exponential Filter For Time-Sensitive Data.

[11]Greg Welch, Gary Bishop: An Introduction to the Kalman Filter.

[12]Greg Welch, Gary Bishop: SCAAT: incremental Tracking with Incomplete Information.

Algoritmos y retardos de red

[13]Rene L. Cruz: A Calculus for Network Delay.

[14]D.L. Mills: Internet Delay Experiments (RFC889).

Scale-Free Networks

[15] Albert-László Barabási, E. Bonabeau: Scale-Free Networks, Scientific American 288, 60-69 (2003)

[16] Albert-László Barabási, Réka Albert:Emergence of scaling in random networks, Science 286, 509-512 (1999).

[17] Réka Albert, Albert-László Barabási: Dynamics of complex systems: Scaling laws for the period of Boolean Networks, Physical Review Letters 84, 5660-5663 (2000).

[18] R. Albert, H. Jeong: Error and attack tolerance in complex networks, Nature 406 , 378 (2000).

[19] J. Podani, Z.N. Oltvai, H. Jeong: Comparable system-level organization of Archaea and Eukaryotes, Nature Genetics 29, 54-56 (2001)