jueves, 29 de enero de 2009

Avoiding JINI lease failures using the Kalman Filter

Introducting the scenario

This paper explains how we avoid JINI lease failures, building a distributed directory service (FADA -Federated Advanced Directory Architecture), which is key component of the Digital Business Ecosystem project (DBE from now on).

As we introduce before, FADA is a distributed directory of services that has been used by the DBE project. It is written in Java, and uses the Jini Networking Technology as base. The DBE members will offer their services through FADA, and those services need a way to be searched, and a starting point to find them and use them.

Every service provider will provide with a Java class called the service proxy. Those service proxies are downloaded by clients and executed in the local client's Java Virtual Machine (JVM from now on). These proxies will communicate from the client with the real service. Thus proxies are a consistent unified way to access services from anywhere in the world. These service proxies must be stored in some place and FADA is that place. FADA is a distributed network of FADA nodes that collaborate to provide with a distributed database of service proxies.

Distributed Systems

A distributed system is a set of entities that exist in geographically distinct places and collaborate to provide a functionality. The difference with traditional or non-distributed systems is that in the latter all components of the system exist in the same place, and communication between them is achieved via the computer buses, which are fast, reliable and always up and working. The difference with centralized remote systems is that in the latter there is a single node that acts as referee for the communication between all collaborating entities, while in a real distributed system all components are self contained (although they need to communicate with their peers to provide the system functionality).

A distributed system has several advantages over non-distributed systems:

  • A centralized system offers a single point of failure, which is the central server. If this node crashes the system functionality is damaged, even if the rest of entities are up an running, because they are not able to collaborate anymore.
  • A distributed system, if so designed, is much easier to scale, and the throughput is dramatically improved by scalability.
  • Price is also an issue: it is much cheaper to make several low-cost entities to collaborate than to make a single entity more powerful. Example: If top technology gave you a 100 MIPS CPU, pushing technology to achieve a 200 MIPS CPU is much more expensive than scaling a system with 20 5 MIPS CPUs to 40 5 MIPS CPUs. And, if well designed, the throughput will be much higher, as 40 CPUs are able to work in parallel, while a single CPU can do only a few things per cycle (if it is able to do several things in a single CPU cycle).

But it also has some drawbacks:

  • In a non-remote system all components are physically in the same place. Communication is achieved by the internal buses. A failure is unlikely to happen.
  • In a centralized remote system communication is easily managed by a single node. There is no need to synchronize with any other peer, as the notion of event ordering and control is managed by the central node.
  • A truly distributed system has to deal with network failures, and since no single part is self contained, every involved entity must be aware of such failures.
  • A truly distributed system has to deal with out of order service requests and transaction control in a much more complicated way than centralized or stand-alone systems.

The trend in the last years is going towards truly distributed systems, in which data replication is also an issue to be considered. In a centralized system, if the central host goes down everything is lost. In a distributed system, if some host goes down the information can have been replicated over several other hosts to provide high availability. The conclusion is that advantages overcome difficulties in design and implementation of distributed systems.

Kinds of failures

When a running program gets in a situation where a critical error has occurred and there is no way to continue from that state, execution is simply aborted. For example, if it has to do some calculations based on two variables, a and b, and it must compute a/b, and both a and b equal zero, there is no way to continue once you get the undefinite number 0/0. Or, if the program has a pointer and it is expected to do something with data that is supposed to be where the pointer points, but the pointer value is null (points nowhere) there is no way for the program to continue. Of course, all these conditions can be checked beforehand by the programmer, and try to avoid the conditions that lead to this kind of errors, known as fail-stop errors.

Another kind of error are known as the Bizantium errors. This is when some internal program state (for instance, some variables) are computed without triggering a fail-stop error, but their state is inconsistent and will make calculations based on them to be erroneous. These errors are harder to detect and prevent.

Distributed systems share these kinds of errors with their non-distributed counterparts, and it also has another kind of errors (shared with centralized remote systems): partial failures.

Say you have to perform an action that requires two remote operations that can only be performed once (for instance, you have to take money from an account and transfer it to another). If everything is OK money is first substracted from the first account, then that amount is added to the second account. Now imagine something gets in the way of the first remote operation. Something we are not aware of. The money is therefore not substracted from the first account, and it was added to the second. You have just given away an amount of money. Your boss will fire you off shortly after he realizes your mistake.

You could go one step further and request an acknowledgement for every remote operation. This eliminates the above conditions, you think. Right? Wrong!

Imagine you decide to reverse the order of the operations. Both of them have to be achieved at once in order to finalize the transaction, so no matter which order you call them the result (in case everything runs fine) will be the same. Now imagine you add an amount of money to one account, wait for the acknowledgement, then substract that amount from the second account. What happens if you don't receive the acknowledgement for the first operation? What has happened? Didn't the operation take place? Or it did but the acknowledgement got lost in the way? You don't know, and you just can't call the operation again (if you've already learned the lesson).

This example shows one of the most frustrating experiences with distributed systems: things are quite different from stand-alone systems.

Availability of services

Imagine you're offering a service to someone. You could advertise your service by a number of means. One of them could be to join a repository where users look for services. This repository can be a distributed system or not, but the important thing here is that your service will be remotely accessed by clients. Imagine a client wants to contact your service and goes to the repository, and it finds a reference to your service. The client tries to contact your service, but he gets no response from you, because your service (due to unknown causes) has crashed. He tries later to see if you have realized the fact and solved the problem, but he sees you haven't. After several tries he gives up and tries another service. Another client tries to contact your service, and he runs into the same trouble. All clients wish the repository to have a way to discard non-working services to avoid waste of time, bandwidth and money. One way the repository could achieve that is by periodically polling the state of the registered services. But if there are hundreds of services it means that the repository has to initiate several hundreds of connections to keep the `database' clean.

One of the solutions to this overload problem is to reverse the actions. The service itself is the only responsible to grant the service availability, so it must make aware the repository of the fact that the service is still working.

When the service is registered in the repository the latter doesn't grant the registration forever. Instead it says something like “OK, I will store your service here for the next 5 minutes. If in that time I don't have news from you, I'll assume you have crashed, and delete you from the repository”. Now every service must renew the registration in order to not to be deleted. If a service crashes it won't be able to renew its registration, and after the specified period of time the repository”will delete the service from its registry. If the service is alive it will renew the registration for an extended amount of time.

Services get an entity called Lease upon registration in the repository. The Lease entity has already been used in DHCP, Jini and now in the FADA.

The service proxy registration lease

All registered services get a registration lease upon registration request. This lease is an object that identifies the registration, and has an internal counter that, when arrives to zero, deregisters the service proxy from the FADA infrastructure. The lease is said to have `expired'. This approach leads to an automatic cleanup of service proxies whose real service is not reachable anymore, thus eliminating the need to maintain the database of registered proxies.

This mechanism is used extensively in Jini, and has been inherited by FADA. The idea of the lease has already been used in Java distributed garbage collection, and other domains as DHCP, the dynamic host configuration protocol. Instead of having a server periodically polling the state of the client, it is the client that periodically renews interest in some item, in this case, the registration. This approach frees the server side of much of its work, and distributes the load among clients (in this case service providers are clients of the FADA).

Leasing and network delays

Jini already offers the concept of lease and the mechanisms to obtain, renew and cancel leases, but the classes that offer automated lease renewal are designed and implemented thinking in the low delays of a LAN, for which Jini was thought. In our case we'll be dealing with the high delays of the Internet, and the standard Jini behavior must be modified.

The situation in Jini is the following: Jini Lookup Servers and services are within the same LAN. The service, upon registration in the Jini Lookup Server, gets a Lease for its registration. This Lease object has a method that tells the date of expiration. Getting the actual time it is easy to compute the remaining time before lease expiration and service proxy deregistration. But the lease renewal operation takes some time, part of which is due to CPU time used for calculations, and part of which is used in the transmission of the physical frame on the LAN. In a LAN the network delays are quite low, and usually under a fixed worst-case value. If we make sure we perform the call to lease renewal before deadline minus delay time happens, we will make sure the lease has been renewed in time.

But in the Internet, where FADA is supposed to work, the distribution of the delays is quite different. Network delay is dependent of many factors as frame length, congestion state of the links, state of the routers, damage on the physical connections that lead to alternate paths searching and reconfiguration of path tables in the routers, etc. Those factors are beyond our reach. We must be able to estimate the worst delay in a given instant.

The Fetish toolkit class FetishImpl will take care of registering services in the FADA, and it will obtain the lease for those registrations. This lease is wrapped by the FADA in a new class that implements the interface FetishLease, a descendant of the standard Jini Lease. This class keeps information needed by the FetishImpl.

A new class called FetishLeaseRenewalManager has also been provided. It is very similar to the Jini LeaseRenewalManager, from which the name has been taken and modified. It does the same basic job as the mentioned Jini LeaseRenewalManager, but with a very important difference. Instead of presuming a low delay, that will be under a fixed value, when a FetishLease is given to the FetishLeaseRenewalManager for renewal it first attempts a renewal, and calculates the round-trip time of the RMI call. This round-trip time gives a hint of the network delay that should be taken into account when renewing the lease (if the lease renewal request is started before the lease expires, but the network delay is very high, the request can finally arrive at destination well after the lease has already expired).

But this round-trip time is not enough, as it is an instant value of the state of the network, but that state might evolve to better or worse conditions. If it evolves to worse conditions we'll be late. If it evolves to better conditions we'll be wasting time and bandwidth. Averaging the last 5 values is definitely not enough, as we still get a very wiggly measure. We need another approach.

The Kalman Filter

In 1960, R.E. Kalman published a paper describing a recursive solution to the discrete-data linear filtering problem.

The Kalman filter is a set of mathematical equations that provides an efficient computational (recursive) solution of the least-squares method. The filter is very powerful in several aspects: it supports estimations of past, present, and even future states, and it can do so even when the precise nature of the modeled system is unknown.

This approach is what we needed: a mathematical model that was able to predict the future state of the network. Not only the Kalman filter gives the best estimation for the next value, but it also gives the error variance, which is much more useful in our case, as we do not need the exact predicted value, but an upper bound for that prediction. In other words: we don't need to know that the most probable next delay time will be, but what is the confidence interval for that value, and use the worse value as our estimation.

The Kalman filter as-is, though, did not fit our case, as it makes some assumptions that didn't hold true. It assumes the real value is disturbed by a white noise signal. In our case the delay evolution of the network is not a continous function, but we can model it as an average continous function disturbed by another function. This other function doesn't follow a gaussian distribution. Further investigation led us to a different formulation of the Kalman filter, in which some of the calculations had been changed to fit the case. The noise added to the signal was supposed to follow an exponential distribution, and the filter was used at intervals of time, between which the filter was kind of `resetted'. Although not exactly our case, it did much better fit it. Simulation and experiments have shown a much better response than simple averaging: the failure rate of the modified Kalman filter was much lower. We call a failure a lease that couldn't be renewed in time.

The figure shows the behavior of the filter we're using when facing Internet delays. We implemented a simple server that received a request of a client, waited a random time (whose distribution was uniform around ±30% of a constant time, that was modifiable at run-time) and then issued the response. The spikes correspond to the Internet delays. The filter adapts quickly to new conditions on the network, although not so quickly that it would follow the previously sampled value, which would render the filter useless.

Even with the Kalman filter we still needed to ensure that service proxy registrations where not deleted from the registry when the service was still alive. A reregistration method was added to the class FetishImpl, that could be used by the FetishLeaseRenewalManager. Reregistration method registers the service proxy again, but it keeps the same parameters: attributes (given by the service provider), the interfaces implemented (given by the proxy itself) and ServiceID (given by Jini and FADA, but kept the same by FetishImpl and FetishLeaseRenewalManager). Even when a lease is not renewed in time, the state of the FADA remains stable, and users will only notice a delay in the response or a miss in the lookup, that will be fixed on the next lookup.

An experiment done over a period of 24 hours showed that, with a lease time of 30 seconds (which is really short; Jini generally gives lease times of around 5 minutes) only 107 of the lease renewals arrived late. The total amount of renewal attempts was around 720. This throws a failure rate of around 14.86%. The service registration, after the 24 hours period, still kept the same ServiceID of the initial registration, and the service was still findable and callable.

In RFC889, p. 11, section 3.3, a formulation of the filter used in IP routers is given. It is very similar to the already chosen one, that is based in the Kalman formulation. The same document also gives some statistics about the usual delays found in the Internet. Delays depend on many parameters, such as packet length, bit rate of middle networks, congestion, etc. Packet loss is also significant.


Distributed systems, though harder to develop, offer a number of advantages that overcomes their drawbacks, such as availability, load distribution and location.

The FADA architecture is a distributed repository of services that relies on Jini and extends its functionality to work in the Internet.

The high delays of the Internet are a serious problem to be treated, and a good estimation of their values is needed in order for things to work properly.

The Kalman filter formulation is a good starting point for estimating these delays. One of its derivatives has shown good performance in the FADA envionment, and has been adopted as the solution to the problem.


miércoles, 28 de enero de 2009

Algo llamado FADA

Federated Advanced Directory Architecture

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


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.


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.


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.



[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)