Métodos implementados en computador y sistemas informáticos de regulación automática de la cantidad de datos transmitidos entre dispositivos conectados a una red
SECTOR DE LA TÉCNICA
La presente invención se encuadra en el sector de la calidad de servicio en las comunicaciones por Internet, es decir, en los sistemas que necesitan realizar transmisiones cumpliendo unos requisitos de tiempo dados.
ESTADO DE LA TÉCNICA
Internet es una red planetaria a la que se conectan una amplísima diversidad de dispositivos y que está formada por múltiples tramos de comunicaciones directas punto a punto, de cable o inalámbricos, de distintas características. Cualquier pareja de dispositivos conectados a Internet pueden transmitirse datos, pero los tiempos empleados en tales transmisiones no son deterministas (predecibles y acotados [1]) debido a diversos factores: protocolos de comunicación con elementos estocásticos, componentes hardware y software que no son de tiempo real duro, etc. Todo esto lleva a que las transmisiones de datos entre cualesquiera dos dispositivos que se encuentren conectados a Internet consuman un período de tiempo probabilístico, el cual suele exhibir además cambios bruscos de régimen y ráfagas rápidas.
Si un nodo conectado a Internet quiere recibir repetidamente datos de múltiples fuentes, como es el caso en aplicaciones de monitorización remota, broadcasting multimedia, teleoperación, etc., donde hay una serie de sensores de los que se desea recibir información periódicamente, esta estocasticidad en los tiempos de envío y recepción de datos hace difícil cumplir los requisitos temporales, es decir, los tiempos de transmisión requeridos por la tarea. Por tanto, es necesario proveer a estas aplicaciones de mecanismos que permitan reaccionar ante esas variaciones de tiempo.
Una posible aproximación es regular la cantidad de información que se transmite para la tarea, de modo que cuando se prevean mayores retardos se solicite menor información, y al contrario; los retardos, al tener una fuerte dependencia con la cantidad de datos transmitidos, admiten este tipo de regulación, cuyo objetivo es mantener en un nivel constante y adecuado, en el sentido estadístico, los tiempos de transmisión.
La regulación de la cantidad de datos circulando en sistemas de transmisión es un campo en el que ya se han realizado diversos desarrollos, como se resume a continuación.
En las patentes [2] se presenta un método para regular la operación del buffer de decodificación de un sistema de transmisión en el que la tasa de transmisión se ajusta según los cambios en los retardos existentes y la ocupación del buffer de codificación, para así evitar over ño ws y underñowsen el citado buffer.
En las patentes [3] se regula el ancho de banda (aumentándolo o disminuyéndolo) en una plataforma de transporte multi-servicio; para ello, se compara el ancho de banda ocupado por el flujo actual con el ancho de banda distribuido.
Las patentes [4], referidas a aplicaciones de transferencia de voz, proponen una regulación basada en el control de la tasa de paquetes perdidos. Así, es posible tener diferentes tasas de paquetes perdidos dependiendo de que el modo de codificación/decodificación a usar sea más o menos riguroso: si el modo es poco riguroso, se aumenta la tasa de paquetes perdidos, disminuyendo así el retraso.
La patente [5] presenta un servidor de medios con dispositivos QoS (Quality of Service, es decir, que tienen capacidades para adaptarse a distintos requisitos de calidad del servicio) y no-QoS conectados, que limita el ancho de banda a estos últimos para garantizar las transmisiones de los primeros.
La regulación de la cantidad de información a transmitir abordada por todos estos trabajos se trata también desde métodos estadísticos, por ejemplo en la patente [6], orientada a tecnologías wireiess) [7], para transmisión de vídeo en redes narrow-band, y [8], donde se utiliza SPC (Statistícai Process Control, técnicas para el control estadístico de la calidad de los procesos) con el objetivo de saber si una serie de eventos están cumpliendo los SLAs (Service Levei Agreemenf) que se tienen como objetivo; si no es así, se toman una serie de acciones para lograr dicho cumplimiento.
Por otra parte, en la literatura científica pueden encontrarse también métodos que regulan los tiempos de transmisión, típicamente en el área de multimedia [9], pero no ofreciendo garantías estadísticas de tiempos de transmisión, como el método descrito en el presente documento.
DESCRIPCIÓN DE LAS FIGURAS
Figura 1. Elementos principales de un sistema en el que se pueden implantar la presente invención. Nodo consumidor de datos (1), nodo productor de datos (2), caminos de transmisión (3l, 32, 3n).
Figura 2. Subsistemas que componen la presente invención, junto con las comunicaciones
principales que se intercambian. Nodo consumidor de datos (1), nodo productor de datos (2), subsistema receptor (4), subsistema estimador (5), subsistema regulador (6).
Figura 3. Procedimiento para el mantenimiento/actualización de la información interna guardada en el subsistema receptor.
Figura 4. Procedimiento para el mantenimiento/actualización de la información interna guardada en el subsistema estimador.
Figura 5. Procedimiento general de toma de decisiones sobre la siguiente densidad de datos a solicitar al nodo productor implantado en el subsistema regulador.
Figura 6. Procedimiento A del subsistema regulador.
Figura 7. Procedimiento B del subsistema regulador.
Figura 8. Pasos del procedimiento B de la opción de mejora para el caso en que la plataforma computacional que lo ejecute soporte paralelismo hardware. Thread (7), parejas de tiempo (8), conjuntos de parejas de tiempo (9), tripias de salida (10).
DESCRIPCIÓN DETALLADA DE LA INVENCIÓN
La presente invención consiste en un sistema de procesamiento de datos para la regulación automática de la cantidad de información que se transmite entre dos dispositivos conectados a Internet, caracterizado por que, a pesar del comportamiento estocástico de las transmisiones, garantiza estadísticamente que la probabilidad de que dicha transmisión se realice al menos a una frecuencia predeterminada sea mayor o igual que una dada y además, lo consigue transmitiendo la mayor cantidad de datos posible. Asimismo, supone modificaciones mínimas en el software y hardware que existan en el camino de transmisión.
Los requisitos para utilizar este sistema son los siguientes:
Hay un camino de transmisión en Internet secuencia de tramos físicos de cable o inalámbricos que permiten comunicaciones a lo largo de la misma que conecta dos nodos, un productor de cierto tipo de datos (2) y un consumidor de los mismos (1) (Fig. 1). Puede haber múltiples caminos de transmisión (3i, 32, 3n) entre los nodos consumidor (1) y productor de datos (2), así como otros posibles nodos en el camino de transmisión.
El consumidor (1) solicita repetidamente datos al otro, indicándole cuántos de ellos quiere, lo cual llamaremos densidad de los datos, no solicitando nuevos datos hasta que no le lleguen los de la iteración anterior Sin pérdida de generalidad se pude suponer que la densidad pertenece a un conjunto finito de posibles valores
previamente acordado por ambos nodos, es decir que es un número natural en el intervalo [0,ZM], siendo 0 la densidad más baja, D-l la más alta y D el número de densidades.
El consumidor (1) necesita que la transmisión de datos, desde el momento en que la envía al productor (2) hasta el momento en que se dispone a enviar la siguiente, tenga una probabilidad mínima dada n de tardar como máximo un período de tiempo preestablecido t (o una frecuencia preestablecida 1/t).
El consumidor (1) es capaz de realizar su función recibiendo una densidad no máxima de datos, aunque posiblemente funcione con menor efectividad en ese caso.
El nodo productor (2) debe enviar exactamente la cantidad de datos pedida por el consumidor (1).
Ni el nodo consumidor (1) ni el productor (2) ni los nodos intermedios del camino de transmisión pueden asumir modificaciones importantes en su software y/o hardware, ya sea porque son plataformas altamente cerradas o por motivos de reducción de coste de implantación, u otros.
El contexto descrito con estos requisitos es suficientemente general como para que se encuentre en múltiples aplicaciones de red, algunas de ellas de uso masivo: broadcasting, teleoperación, monitorización, vigilancia remota, etc. Por ejemplo, si los datos transmitidos son imágenes provenientes de una cámara o de un sensor similar es fácil enviar sólo una cierta cantidad de los mismos desde el nodo productor (2) al nodo consumidor (1), ya sea mediante técnicas de compresión de datos o de selección, y aún así seguirán siendo útiles para su uso (aunque será deseable recibir el máximo posible), siempre que lleguen con una cierta frecuencia mínima. Si, además, se requiere que usuarios no especializados puedan recibir esas imágenes mediante una conexión estándar a Internet, no se pueden considerar el uso de protocolos especiales de comunicaciones o el de segmentos de red u ordenadores con características específicas de tiempo real.
En el caso de que un mismo productor (2) sea capaz de proveer a un mismo consumidor (1) con diversos tipos de datos, y se desee que cada uno esté regulado para conseguir los objetivos descritos anteriormente, se puede replicar el sistema objeto de la presente invención tantas veces como tipos de transmisiones de datos existan (véase de nuevo la Fig. 1), todos ellos funcionando de manera independiente para obtener los mejores resultados posibles dados los elementos compartidos que encuentren entre el consumidor (1) y el productor (2); es decir el presente sistema puede utilizarse para regular múltiples transmisiones de datos simultánea e independientemente sin necesidad de sufrir ninguna modificación. Por tanto, a partir de este
punto se describirá el caso de transmitir un sólo tipo de datos.
La presente invención se caracteriza por ser capaz de decidir en cada iteración de envío- recepción de datos entre consumidor (1) y productor (2), cuántos de estos datos (densidad) deben transmitirse para que se cumplan simultáneamente dos cosas: a) que exista una probabilidad, mayor o igual que una dada, ji, de que el tiempo que transcurra para completar la transmisión sea menor o igual que un tiempo predeterminado t, y b) que la densidad de datos sea la máxima posible que permita el objetivo a).
El sistema consiste en un soporte hardware/software de ejecución, que puede ser cualquier computador o conjunto de computadores con capacidad suficiente para realizar operaciones con números reales, acceso a un reloj local, así como a una interfaz de conexión con el camino de transmisión, y de un conjunto de procedimientos ejecutados por tal(es) ordenador(es) que se describen más adelante. El sistema en su conjunto admite como entrada el tiempo que se desea que dure la transmisión de datos en el peor caso, t, la probabilidad mínima con la que se desea cumplir ese tiempo, jt, y la lista de posibles densidades de datos que el consumidor (1) puede solicitar al productor (2); da como salida, antes de cada iteración de transmisión, la máxima densidad de esa lista que se le debe solicitar al productor (2) para satisfacer el tiempo t con probabilidad igual o mayor que jt.
Con más detalle, este sistema consta de tres subsistemas, el subsistema receptor (4), el subsistema estimador (5) y el subsistema regulador (6) (ver Fig. 2). El subsistema receptor (4) hace de intermediario entre el consumidor (1) y el productor (2), y también toma medidas de tiempo sencillas; el subsistema estimador (5) se ocupa de mantener actualizadas estimaciones de probabilidad de cumplir tiempos en las transmisiones; el subsistema regulador (6) se encarga de tomar decisiones sobre la cantidad de datos a transmitir en cada iteración, ejecutando efectivamente la función de regulación que satisface los requisitos de tiempo real.
Tbdos estos subsistemas pueden ejecutarse sobre cualquier nodo que se halle en el camino de transmisión, incluso pueden coincidir en el mismo nodo, pudiendo ser asimismo el nodo o los nodos que los ejecuten máquinas dedicadas exclusivamente a la función de estos subsistemas o no (por ejemplo, se pueden situar en el mismo ordenador del productor (2) o del consumidor (1), como implementaciones puramente software, compartiendo plataforma computacional con aquéllos, pero no es necesario hacerlo así).
La secuencia de funcionamiento del sistema completo es la siguiente: el nodo consumidor (1) realiza una comunicación inicial dirigida a cada uno de los tres subsistemas, en la que les configura sus parámetros (flechas punteadas en la Fig. 2; esto puede repetirse en cualquier otro momento, para que reinicien sus procedimientos y borren toda la información recabada hasta
entonces); tras estos envíos de reinicio, el nodo consumidor (1) comienza las solicitudes repetidas de datos (flechas continuas en la Fig. 2): primero le pide al subsistema regulador (6) una decisión sobre la densidad de datos a usar lo cual hará que el regulador se comunique a su vez con el subsistema estimador (5) para conseguir estimaciones de probabilidad de tiempos de transmisión, como se explica más adelante; luego le solicita al subsistema receptor (4) que realice la transmisión de datos; el subsistema receptor (4), al recibir esta solicitud, toma medidas de tiempo, redirige la petición de datos hacia el productor (2), le comunica al subsistema estimador (5) los datos de tiempo recabados para que éste mantenga información actualizada sobre las probabilidades de completar una transmisión en el tiempo x y finalmente devuelve los datos pedidos hacia el consumidor (1).
Subsistema Receptor
El subsistema receptor (4) consiste en un sistema de procesamiento de datos caracterizado por dos funciones: a) medir los tiempos en que se completan las transmisiones de datos entre consumidor (1) y productor (2), y b) hacer de intermediario en dichas transmisiones.
A este subsistema se le pueden hacer dos tipos de peticiones, ambas por parte del consumidor (1): peticiones de reinicio, en las que se le pide que elimine cualquier información previa recabada (no hay parámetros específicos de funcionamiento que haya que proporcionarle en este tipo de petición), y peticiones de transmisión de datos con cierta densidad (donde se le indica esa densidad). Para realizar esas funciones, el subsistema receptor (4) necesita tomar medidas de tiempo de un reloj local de su propio nodo y hacer cálculos con números naturales y reales, por lo que puede implementarse bien como algoritmo software, bien como sistema electrónico hardware; en el primer caso utilizará las facilidades ya existentes en el nodo para comunicarse por Internet, mientras que en el segundo debe disponer de los interfaces necesarios para poder atender a las comunicaciones del consumidor (1) y para enviar las suyas propias a los otros subsistemas.
Este subsistema mantendrá internamente cierta información, que puede definirse matemáticamente como una pareja (ó, f), con <5E [0,D-1], El valor ó es la densidad que se solicitó en la última petición de transmisión de datos del consumidor (1), y tes el tiempo, según el reloj local, en que llegó al subsistema receptor (4) esa petición por parte del consumidor (1). Si no ha habido ninguna transmisión de datos aún, y también tras la recepción de cualquier petición de reinicio por parte del consumidor (1), el valor de <5 será D (densidad inválida).
El mantenimiento de esta información interna se realiza mediante la siguiente secuencia,
a ejecutar en cada iteración de transmisión de datos que ocurra en el sistema (Fig. 3): el subsistema receptor (4) mide el tiempo local ta en que le llega la petición de transmisión de datos del consumidor (1), la cual viene con una densidad a pedirle al productor (2), ó'; envía esa petición hacia el productor (2); a continuación, si ó' = ó, calcula la diferencia d=ta-t, que es el tiempo que ha tardado en completarse la petición de datos anterior incluyendo los períodos de tiempo consumidos en todos los procesos y nodos involucrados en esa transmisión (no sólo los retardos de comunicaciones por la red), y envía una petición de actualización de información estimada al subsistema estimador (5) con ese valor d calculado y también con el tiempo ta, a continuación espera a que el productor (2) le devuelva los datos que ha generado para esa petición; sustituye entonces la pareja almacenada internamente por (ó', ta); finalmente reenvía de vuelta los datos transmitidos desde el productor (2) hacia el consumidor (1).
Subsistema Estimador
El subsistema estimador (5) consiste en un sistema de procesamiento de datos caracterizado por procesar los tiempos medidos por el receptor para cada densidad de datos que existe en el sistema, generando información interna acerca de la probabilidad de que la siguiente petición de datos tarde en completarse un tiempo igual o menor a x.
A este subsistema se le pueden hacer tres tipos de peticiones: a) [por parte del consumidor] una petición de inicialización, en la que se le dan los parámetros necesarios para su funcionamiento y se le solicita que borre toda la información recabada hasta el momento, b) [por parte del receptor] una petición de actualización de la información interna de estimación, y c) [por parte del regulador] una petición de estimación de la probabilidad de que la siguiente transmisión tarde x o menos tiempo, para todas las densidades de datos en las que se disponga de tal estimación.
Para realizar estas funciones, el subsistema estimador (5) necesita hacer cálculos con números naturales y reales, por lo que puede implementarse bien como algoritmo software, bien como sistema electrónico hardware; en el primer caso utilizará las facilidades ya existentes en su nodo para comunicarse por Internet, mientras que en el segundo debe disponer de los interfaces necesarios para poder atender a las comunicaciones que le lleguen y para generar las suyas propias, así como de potencia suficiente como para ejecutar el procedimiento de estimación de probabilidades que se menciona al final de este apartado (la generación del vector y).
Los parámetros que el consumidor (1) debe enviarle al subsistema estimador (5) en la petición de reinicio son los siguientes: n, el mínimo número de transmisiones a monitorizar antes
de poder generar ninguna estimación de probabilidad para una densidad de datos determinada; a, el tiempo máximo en segundos durante el que se consideran válidos los valores de tiempo recabados en las transmisiones de una densidad de datos determinada (puede ser 0 para anular el efecto de este parámetro, considerándose entonces válidos todos los valores recabados, aunque sean muy antiguos); y finalmente el valor de x establecido para este tipo de transmisiones de datos. Ante esta petición de inicialización el subsistema estimador (5) establecerá los parámetros a los valores recibidos y eliminará toda la información interna recabada hasta entonces.
La información interna que el subsistema estimador (5) genera y mantiene durante las iteraciones de transmisión permite deducir la probabilidad estimada de que el tiempo de transmisión para una densidad dada sea menor o igual que x, o bien permite deducir que no se dispone de esa estimación aún. Esta información consiste en un vector z=<z¡,z2,...,zm> de elementos z=(<% c¡, F¡), donde m<D, Vi j 6^ ó¡, <5,£ [0, D-l], y c,£ {0,1}, siendo m la longitud de z, D el número finito de densidades de datos que es posible pedirle al productor (2), <5 una de esas densidades, c, un indicador que vale 1 si el conjunto r ha sido modificado desde la última vez que se atendió una petición del subsistema regulador (6) o 0 si no, y r¡ un conjunto de r elementos {(di, tai),(d2, ta),...,(dr, £»-)}, posiblemente vacío, con los datos de tiempo recogidos para las transmisiones ya realizadas con la densidad <5*. El vector zno contendrá ningún elemento z, para una densidad para la que no se haya completado nunca una transmisión de datos. Tras una inicialización del subsistema estimador (5), z estará vacío.
La información de zes actualizada (Fig. 4) cada vez que llega una petición al respecto del subsistema receptor (4), la cual contendrá una densidad <5, un valor dy un tiempo ta (tal y como se ha explicado en el apartado dedicado al subsistema receptor (4)). Esta actualización se realiza mediante la siguiente secuencia: en caso de que no exista ningún elemento z¡ en el vector z que contenga la densidad <5, se añade un elemento nuevo z¡=(d, 1, {(d, ta)}); si por el contrario ya existe un elemento z,= (<5, c r¡), se sustituye éste por (<5, 1, r, U {(d,ta)}), y, luego, si a> 0, se eliminan del conjunto r, U {(d,ta)} que hay en el nuevo z, pares (d\ ta') que cumplan tj < ta-a, empezando por los más antiguos (los de menor tá), y mientras que la eliminación de un par no haga que la cardinalidad resultante del conjunto sea inferior a n.
El subsistema estimador (5) también puede recibir del subsistema regulador (6) una petición sobre las probabilidades estimadas de que una transmisión de datos tarde un tiempo x o menos en completarse. En tal caso responderá con esa información, contenida en un vector y=<yh yz, ym> de la misma longitud que z, cuyos elementos serán pares y¡ = (ó¡, Jt¡) con los
mismos valores de <5, que los correspondientes elementos de z, donde ^ [0,1 ] será la
probabilidad estimada de que la transmisión de esa densidad se complete en o menos tiempo. Las densidades para las que el subsistema estimador (5) no haya podido estimar apropiadamente no aparecerán en ninguna pareja del vector y.
El procedimiento para calcular el vector y a partir de la información interna almacenada en el vector z, es decir para calcular los valores nh puede ser cualquier método que sirva para estimar las probabilidades descritas a partir de los datos almacenados en el vector z, teniendo en cuenta que el sistema completo será más efectivo (cumplirá mejor sus objetivos) cuanto más cercanas a la realidad sean esas probabilidades estimadas.
Subsistema Regulador
El subsistema regulador (6) consiste en un sistema de procesamiento de datos que, dadas unas estimaciones de probabilidad generadas en el vector y por el subsistema estimador (5), y dada también la densidad S0 que el consumidor (1) pidió en la última transmisión de datos completada cualquier valor de densidad si aún no ha habido ninguna iteración de transmisión de datos, da como salida la densidad de datos que debería pedirse en la siguiente transmisión para cumplir los objetivos del sistema completo, es decir devuelve la máxima densidad que consiga probabilidad igual o mayor que ji de que la transmisión se complete en un tiempo x o menos.
Además de las peticiones por parte del consumidor (1) para decidir densidades, el subsistema regulador (6) puede recibir otras donde se le solicite que reinicie sus parámetros a unos valores determinados. Los parámetros que debe recibir en una petición de ese tipo son: p E [0,1], que es una diferencia mínima de probabilidad que tiene que haber entre la actual probabilidad de cumplir con el tiempo x y la probabilidad deseada n, para que el regulador decida incrementar la densidad actual; u'E(0,l], que es un factor que regula en cuánto se reduce, como máximo, la densidad actual en caso de que haya que bajar de densidad; y u+E (0,1], que es un factor que regula en cuánto se aumenta, como máximo, la densidad actual en caso de que haya que aumentar de densidad. Mientras no reciba ninguna petición de este tipo, el subsistema regulador (6) toma los siguientes valores por defecto: p=0.05, u'=l, v+=\.
Para realizar sus funciones el subsistema regulador (6) necesita hacer cálculos con números naturales y reales, por lo que puede implementarse o bien como algoritmo software, o bien como sistema electrónico hardware; en el primer caso utilizará las facilidades ya existentes en su nodo para comunicarse con el consumidor (1) y con el subsistema estimador (5) (puede
ser por Internet, si éstos se ejecutan en nodos separados de la red), mientras que en el segundo caso debe disponer de los interfaces necesarios para hacer estas comunicaciones, ya sean locales o también a través de Internet. Al contrario que otros subsistemas, el regulador no genera ni mantiene información interna.
Cada vez que recibe una petición de decisión desde el consumidor (1), junto con la densidad ó0 que se usó en la última iteración, el regulador (ver Fig. 5) envía una petición al subsistema estimador (5) para que le remita su información interna, es decir el vector y = <yi, yz, ym> cuyos elementos son pares yr(8it ji¡), descrito en el apartado anterior Con esta información ejecuta el siguiente procedimiento: si en el vector.y no existe ninguna pareja (óh n¡) con <5, = 8o, no tiene información suficiente para decidir y por tanto termina de servir la petición devolviendo al consumidor (1) la misma densidad ó0; si existe tal pareja, jt¡< n y ó0= 0, no está cumpliendo la probabilidad pedida n pero tampoco estima que pueda hacerlo, con lo que devuelve la misma densidad óo al consumidor (1); si existe tal pareja, n¡ < n y óo> 0, no está cumpliendo la probabilidad pedida n pero puede reducir la densidad de datos para intentar cumplirla, lo que hace ejecutando el sub-procedimiento A que se describe en el siguiente párrafo; finalmente, si existe tal pareja y n¡ ir, está cumpliendo la probabilidad pedida n y puede intentar aumentar la densidad respecto a la última que se solicitó, por lo que ejecuta el subprocedimiento B que se describe debajo.
El sub-procedimiento A (ver Fig. 6) trata de disminuir la densidad de datos transmitidos, si es posible, para aumentar la probabilidad de recibirlos antes de un tiempo t, siendo esta disminución proporcional a la diferencia o error n-jt¡ existente en las probabilidades; en particular se calcula 8 = min(<50-l, ó0(l-(jwr())ir). Si <5=0 o no hay información en el vector y acerca de la densidad ó , o si existe una pareja (8 fij) en el vector y pero Jtj a n;, devuelve ó como resultado y termina; en otro caso repite el salto a una densidad menor de la misma manera, pero empezando en 8o=8.
El sub-procedimiento B (ver Fig. 7) trata de aumentar la densidad de datos a transmitir saltando a una densidad de datos que esté situada a una distancia proporcional al error en probabilidad, si es posible, puesto que se están cumpliendo las condiciones establecidas; para ello, se define la longitud del salto x = (D-l-80) (jit -rc)u+, y se calcula la nueva densidad 8 = 80+x; si x=0 o no existe información sobre 8 en el vector yo bien existe una pareja (8, n¡) en el vector y pero Jtj a rc, devuelve ó como resultado y termina el sub-procedimiento; en otro caso cambia el tamaño del salto &x=x-\ y repite éste tomando como nueva densidad 8= ó0+x.
Se propone a continuación un sistema de procesamiento de datos caracterizado por el
almacenamiento en el vector z de información más detallada que la descrita en los apartados anteriores y también por la producción de un vector y con estimaciones de probabilidad Jt¡ de alta calidad. La realización de esta opción no afecta más que al subsistema estimador (5), salvo las peticiones de reinicio que éste recibe del consumidor (1), que deben modificarse ligeramente y por tanto influyen también en la realización de este último; en particular esas peticiones se enriquecen con la adición de un nuevo parámetro y, un número natural que indica cuántos valores de tiempo de transmisión se usarán, como mínimo, al considerar los últimos tiempos recibidos de una densidad como parte de algún grupo de tiempos anteriores que compartan características estadísticas similares. Por defecto, y=n {n es otro de los parámetros de la petición de reinicio, y fue descrito en el apartado del subsistema estimador (5)).
El vector z que ha sido descrito en el apartado correspondiente al subsistema estimador (5) está compuesto de elementos z,=(<5 c¡, r¡), cada uno de los cuales corresponde a una densidad <5, que se ha usado en alguna transmisión y contiene una lista de tiempos r¡ medidos al completar transmisiones de datos. La presente opción de mejora propone sustituir dentro de cada elemento z¡, la lista de tiempos r¡ por una serie de listas de tiempos, cada una conteniendo aquellos tiempos de transmisión d que han demostrado un comportamiento estadístico similar lo que denominaremos un régimen, de modo que, cuando haya que predecir el tiempo que tardará la siguiente transmisión en completarse si se pide una cierta densidad, se tendrá mucha más información que si se usa sólo el sistema descrito en párrafos anteriores. Además, cada régimen así almacenado en z,se acompañará de la definición de la mejor distribución de probabilidad que modela sus tiempos de transmisión. Para esto último se propone el uso de una distribución log- logística tri-paramétrica [10], cuya función de distribución de probabilidad es:
siendo a 0, b > 0 y c > 0 los parámetros (números reales) que definen por completo esta distribución (la tripla (a,b,c) es la que se almacenará junto con cada régimen de z¡) y x 0 un tiempo en completar una transmisión (número real) para la densidad correspondiente a z¡.
Más concretamente, el vector zquedará definido matemáticamente como z=<zi,Z2,...,zm>, con elementos z;=(<5 c A¡, B s,) asociados a cada densidad á donde <5, y c, son y se actualizan de la misma forma descrita en el apartado dedicado al subsistema estimador (5), mientras que Ah B¡ y s, sustituyen a r¡. El componente /i, se define como un vector de regímenes A¡=<tu, h,..., t¡> formados con los tiempos de transmisión de datos de esa densidad, siendo definido cada
**(Ver fórmula)**
0)
régimen como ty/=( Ay, Ai,y), donde Dij={{di, tai), (d2, tai),..., {dr, t3r)} es una lista de tiempos de transmisión, posiblemente vacía, que comparten similitudes estadísticas, y Atf,yun modelo (a,b,c) log-logístico tri-paramétrico de los tiempos {di, d2,dr}, el cual puede ser (-1,-1,-1) para indicar que aún no ha podido calcularse. A su vez, Bj={{di, tai), (d2, tai),.... (dr, taq)} es un buffer de tiempos de transmisión, posiblemente vacío, que está en espera de convertirse en un nuevo régimen o de añadirse a un régimen existente. Finalmente, s¡ es un número natural que indica el estado en el que se encuentra la estimación para la densidad <5,: 0 * esperando a poder extender un régimen existente, >0 » extendiendo el régimen existente cuyo índice sea s¡.
En esta opción de mejora el procedimiento para calcular las probabilidades m que necesita el subsistema regulador (6) a partir de los datos de z es como sigue: para cada z,=(<5/, c,, A¡, B¡, s,), si Si = 0, no se generará ningún elemento correspondiente en el vector y para la densidad S¡, mientras que si s¡> 0 es porque los tiempos se están comportando como los del régimen srésimo, por tanto se generará un elemento y¡=(ój, Jt¡) cuyo n¡ será igual al resultado de evaluar la ecuación (1) usando como parámetros (a,b,c) los guardados en ese régimen S/-ésimo de A¡ y como valor de la variable x el número x.
Por otra parte, el procedimiento para mantener actualizado el vector z es más complicado. Se ejecutará en cada petición, desde el receptor hasta el estimador de actualización de la información estimada por este último. Esa petición, como ya se ha descrito en el apartado dedicado al subsistema estimador (5), indica qué densidad ó se está pidiendo, qué tiempo d tardó en completarse la última transmisión de esa misma densidad y en qué momento ta se inició esa última transmisión. La actualización de zcon esa información es como sigue: en caso de que no exista ningún elemento z, en el vector z que contenga la densidad 6, se añade un elemento nuevo z,{ó, 1, A¡, Bi,s¡) con s¡= 0, B,= {{d, ta)} y A, = <t,¡>, donde, a su vez, tn = (Ai, Mu), Dn = {(d, ta)} y Mu = (-1,-1,-1); si, por el contrario, ya existe un elemento z¡ = (ó, 1, A¡, Bh s,), se sustituye éste por (S, 1, A¡, B¡,s'). Los nuevos parámetros A¡, B¡ ys' se construyen según el subprocedimiento W descrito más adelante. Este sub-procedimiento necesita a su vez ejecutar otros sub-procedimientos: el sub-procedimiento X, que calcula el mejor modelo probabilístico (a,b,c) para un conjunto de parejas de tiempos de transmisión {{di, tai), (d2, ta2), (dq, ta9)}, el sub
procedimiento Y que hace lo mismo que el X pero para múltiples conjuntos de tiempos de transmisión, obteniendo para cada uno su mejor modelo, y el sub-procedimiento Z, que devuelve una medida numérica de la bondad de un cierto modelo probabilístico (a,b,c) para explicar un cierto conjunto de parejas de tiempos de transmisión {{di, tai), {d2, ta2), {dq, taq)}. Se explican estos sub-procedimientos en los siguientes párrafos, desde el de nivel menos abstracto hasta el
de nivel más abstracto.
El sub-procedimiento Z recibe como entrada un modelo (a,b,c) de distribución de probabilidad log-logística tri-paramétrica y un conjunto de parejas de tiempos de transmisión {{di, t3i), {Ü2, ta2), -, {dq, taq)}. En primer lugar calcula el modelo equivalente al (a,b,c) de una distribución de probabilidad logística bi-paramétrica, consistente en dos parámetros (ti,o) [11], mediante las siguientes ecuaciones:
A continuación transforma los tiempos de transmisión {di, d2,..., dq} de las parejas recibidas en un nuevo conjunto {e3, eq} según la siguiente ecuación:
Finalmente utiliza el método de bondad de ajuste Anderson-Darling para distribuciones log-logísticas bi-paramétricas [12], pasándole como entradas (ti, o) y {ei, e*}, el cual
devuelve un valor-p de bondad de ajuste (un número real entre 0 y 1, más alto conforme mejor
de este sub-procedimiento Z.
El sub-procedimiento X recibe como entrada un conjunto de parejas de tiempos de transmisión {(di, tai), (d2, ta2),..., (dq, ta,)} y devuelve como salida el mejor modelo (a,b,c) log- logístico tri-paramétrico que podría explicar los elementos {di, d2,..., dq}. Esto lo realiza en dos pasos consecutivos. El primer paso está basado en el método de estimación de los momentos [13] y encuentra una primera aproximación a esos parámetros, (ao,bo,co), mediante la resolución de las siguientes ecuaciones:
ti = ln(ó)
o = c
**(Ver fórmula)**
sea la bondad de ajuste [13]) y una decisión H de si el modelo probabilístico explica los datos de tiempo (que valdrá 0 si el modelo los explica o 1 si no). El valor-p y la decisión H son las salidas
**(Ver fórmula)**
bn = median\d.- a0|
c0 = mm\
«o +
2>0/?(l + c,l-c)
**(Ver fórmula)**
donde p es la función matemática beta [14]. La ecuación mostrada para co no tiene solución cerrada, por lo que sólo se puede aproximar numéricamente, mediante un procedimiento de optimización iterativo. Esta opción de mejora propone el uso de un algoritmo Levenberg- Marquardt [15] para ello, que use como semilla inicial co= 0.05 y un intervalo de búsqueda co G [0.05,1].
El segundo paso del sub-procedimiento X encuentra el valor definitivo de la tripla (a,b,c) resolviendo las siguientes ecuaciones para las variables a, b y c, basadas en una estimación de máxima verosimilitud [13] donde existen las siguientes restricciones: aG (0, minfc/,}), b G (0,oo) y c G [0.05,1). De nuevo, resolver estas ecuaciones es un procedimiento de optimización numérica, dado que no hay solución cerrada. Esta opción de mejora se basa en utilizar un algoritmo Levenberg-Marquardt para ello, utilizando como solución inicial la tripla (a0,b0,co) generada por el paso W y provisto de las expresiones del Jacobiano de esas ecuaciones para acelerar los cálculos. Además, si la plataforma de ejecución que soporta al sub-procedimiento X dispone de multitarea hardware, los tres sumatorios de la ecuación (2) se implementan más eficientemente mediante un esquema de reducción paralela: cada thread (7) puede calcular una suma parcial de un rango del espacio de iteraciones, y posteriormente esas sumas parciales se acumulan para obtener el resultado final. Adicionalmente, se desacoplan los pasos del subprocedimiento X mediante un esquema de tipo pipeline. Este pipeline contempla las siguientes etapas (ver Fig. 8): creación del conjunto de parejas de tiempos, XI, estimación de los parámetros iniciales, X2, cómputo de los valores definitivos de los parámetros (a,b,c) resolviendo la ecuación 2, X3, y finalmente salida ordenada de dichos parámetros, X4. Cada paso se asocia a una etapa del esquema de tipo pipeline de forma que distintos threads (7) pueden procesar en paralelo distintos conjuntos de parejas de tiempo que estén siendo procesadas en distintas etapas. Adicionalmente, las etapas X2 y X3 también exhiben un paralelismo espacial, es decir podemos tener varios threads (7) ejecutando al mismo tiempo el proceso X2 con distintos conjuntos de parejas de tiempo, y que los resultados de este procesamiento alimenten otro conjunto de threads (7) encargados del proceso X3. Si explotamos este paralelismo y queremos obtener a la salida los resultados en el mismo orden en el que llegaron a la entrada los conjuntos de parejas de tiempo, los procesos XI y X4 deben ser serie (ejecutados por un único thread (7)), de forma
que XI etiquete los conjuntos y X4 reordene la salida acorde a dichas etiquetas. Este esquema en pipeline se describe gráficamente en la Fig. 8, en la que se aprecia que sólo hay un thread (7) ejecutando los procesos XI y X4, pero que hay varios threads (7) ejecutando X2 y X3, y por tanto, varias triplas (aQ,bQ,CQ) y (a,b,c) en vuelo.
/ \
1+1/c 2b d -a
1 le
(d'-ap'-ay + b*
| 'a' h | = argmin(abc) | n | 2b1/c y | ' | |
| c | | cb | be ^ | (« | l-af + b^ |
| \ y | | | r | | |
(2)
-wln(ft) n
-i+ly
c c
ln
ln(íf -oj-2
d.- a'
v M
//, \i/c ^ d - a
+ 1
El sub-procedimiento Y consiste en realizar varias llamadas al sub-procedimiento X, cada una con un conjunto distinto de parejas de tiempos. Todos los modelos resultantes de las 10 llamadas al sub-procedimiento X forman la salida de este sub-procedimiento Y.
El sub-procedimiento W construye los nuevos parámetros Al, B¡ y si de z, a partir de los actuales, A¡, B¡ys¡. Lo primero que hace son las asignaciones Al = A¡, B¡ = B¡ y si = s¡. Luego realiza tres acciones distintas, dependiendo de que se den sendas condiciones:
1) Si s,= 0 y la longitud de B¡ es igual a n-1 (n es un parámetro de funcionamiento ya 15 descrito en el subsistema estimador (5)), forma un conjunto F¡= B¡ U {(dta)}, siendo
d el valor de tiempo recibido en la petición en curso del subsistema receptor (4). Luego llama al sub-procedimiento X con ese conjunto F¡, obteniendo así un modelo (a,b,c), con el cual llama a su vez al sub-procedimiento Z, obteniendo un valor-p y una decisión H, de forma que si esto ha dado como resultado que el modelo (a,b,c) explica 20 los datos de tiempo (es decir, si H es 0), se añade a A¡ un nuevo régimen t¡(k+i) =
(D,(k+i), Mi(k+i)) con Di(k+i)= F¡ y Mi(k+i)= (a,b,c) y se asignan s! - k+1 y B¡ - 0, mientras que si el modelo no explica los datos se extrae de B¡ el elemento más antiguo (con t3 menor) y se añade el elemento (d, t¡), dejando inalterados Al y si;
2) Si s,= 0 y la longitud de B¡ no es igual a n-1 (será menor), forma un conjunto F¡ = B¡ U {{d, ta)}, luego construye otro conjunto G¡a partir de los elementos de F¡, pero sólo con las y parejas de valores de tiempos más recientes según los respectivos ta, o bien con todos los valores de tiempos de F¡ si el tamaño de F¡ es menor que y. Se recopilan entonces una serie de conjuntos Th T2,..., 7a> estando cada 7} formado por la unión del conjunto F¡ y de todas las parejas de tiempos almacenadas en el régimen D¡¡ (contenido en el elemento ty de Al). Luego se llama al sub-procedimiento Y, dándole como entrada cada uno de los conjuntos 7} así formados y obteniendo como salida, para cada uno, un modelo (a,b,c)¡. Se llama al sub-procedimiento Z con ese modelo y los mismos tiempos, obteniendo así un valor-p y una decisión H para cada conjunto T¡, y, finalmente, si existen algunos de esos modelos que son considerados válidos (H=0), se escoge aquel Z);y que haya dado mayor valor-p, se le añaden las parejas del conjunto F¡, sustituyendo en A¡ al régimen anterior junto con el modelo (a,b,c)¡ encontrado, se asigna su índice de régimen j a s¡, y se asigna el conjunto vacío a B¡. Si no existe ningún modelo válido (todas las H=l) se dejan s¡, B¡ y A¡ inalterados;
3) Si s¡> 0, se extiende el régimen actual D¡(S¡) con el nuevo tiempo recibido, formando un conjunto de parejas de tiempo F¡= D¡(S¡)U {(d', ta)}, se llama al sub-procedimiento X con ese conjunto F¡, obteniendo un modelo (a,b,c), luego se llama al subprocedimiento Z con ese modelo y con el mismo conjunto, obteniendo un valor-p y una decisión H, y, en caso de que la decisión indique que el modelo explica el conjunto de tiempos (H=0), se sustituye en A¡ el régimen de índice s¡, que será el elemento t¡(S¡) = {Di(sí), Mi(Si)) por la nueva pareja {F¡, (a,b,c)), dejando inalterados s¡ y B¡, mientras que, si el modelo no explica los tiempos (H=l), se asigna B¡ = {(d, ta)}, si = 0 y se deja inalterado A/.
MODOS DE REALIZACIÓN DE LA INVENCIÓN
La presente invención puede realizarse en una diversidad de situaciones. En este apartado consideraremos aquéllas en las que el nodo consumidor (1) sea un ordenador con sistema operativo, sin especiales capacidades de cómputo (puede ser un tablet, un smartphone, un PC estándar etc.), mientras que el nodo productor (2) será un PC estándar con sistema operativo, capacidad de multiprocesamiento y dotado de una serie de sensores o dispositivos generadores de datos. El consumidor (1) desea recibir repetidamente datos de cada uno de esos dispositivos, y que todas esas transmisiones estén reculadas nara maximizar la cantidad de datos recibidos y
al mismo tiempo conseguir que los tiempos de transmisión sean menores que uno predeterminado para cada dispositivo. Asimismo, cada dispositivo sera capaz de proveer un conjunto distinto de densidades de datos. Nótese que esta situación incluye la de cualquier sistema que sólo tenga un dispositivo generador de datos.
La realización preferida del sistema en tal caso es como sigue.
Se implantara un subsistema receptor (4) por cada dispositivo capaz de producir datos, mediante un algoritmo software implantado en el mismo lenguaje de programación que use la aplicación del consumidor (1) encargada de recibir esos datos; todos estos subsistemas se ejecutaran en el mismo nodo que el consumidor (1), y responderán a las peticiones de la aplicación, que serán realizadas mediante llamadas de procedimiento locales, y contendrán la información y seguirán la secuencia explicadas en el apartado de descripción detallada. Las comunicaciones que estos subsistemas hagan con el resto de subsistemas se realizaran a través del protocolo TCP/iPpor lo que cada uno de ellos reservara y mantendrá un punto de conexión o Socket TCP para ello, asociado a un puerto que no se utilice para otra finalidad en el nodo del consumidor (1).
Se implantara un subsistema estimador (5) por cada dispositivo capaz de producir datos, implementándolo mediante un algoritmo software que incluya la opción de mejora descrita en apartados anteriores y que esté escrito en el mismo lenguaje de programación que la aplicación del productor (2) encargada de recabar esos datos de los dispositivos disponibles en el nodo del productor (2). Tbdos los subsistemas estimadores se ejecutaran en el nodo del productor (2), y recibirán las peticiones de los correspondientes subsistemas receptores y del consumidor (1) a través de comunicaciones TCP/IP por lo que se asignara a cada estimador un puerto de comunicaciones bidireccional TCP que no se use para otra finalidad en el nodo del productor (2), y cada estimador lo mantendrá abierto para sus funciones de comunicación.
Se implantara un subsistema regulador (6) por cada dispositivo capaz de producir datos, implementándolo mediante un algoritmo software escrito en el mismo lenguaje de programación que use la aplicación del consumidor (1) encargada de recibir esos datos; todos estos subsistemas se ejecutaran en el mismo nodo que el consumidor (1), y responderán a las peticiones del mismo, que serán realizadas mediante llamadas de procedimiento locales, y contendrán la información y seguirán la secuencia explicadas en el apartado de descripción detallada. Las comunicaciones que estos subsistemas hagan con el resto de subsistemas se realizaran a través del protocolo TCP/iPpor lo que cada uno de ellos reservara y mantendrá un punto de conexión o Socket TCP para ello, asociado a un puerto que no se utilice para otra finalidad en el nodo del consumidor (1).
En caso de que se desee minimizar el número de puertos de conexión utilizados por los subsistemas, se añadirá en el nodo consumidor (1) y en el productor (2) un concentrador software consistente en un algoritmo que reciba peticiones de comunicaciones en un sólo puerto, las cuales deberán contener el identificador del subsistema de destino, y que las reenvíe mediante llamadas locales hacia el mencionado subsistema.
Referencias
[1] Liu P.X., Meng M.Q-H., Gu J., Yang S.X., Hu C., "Control and Data Transmission for Internet Robotics", IEEE Intl. Conf. on Robotics & Automation, pp. 1659-1664, 2003.
[2] Wells N.D., "Buffer Resynchronisation in a variable transmission rate coder", patents GB2274041 (B); GB2274041 (A), 1994-07-06.
[3] Cheng L., Zhang J., Zhao J. "Method for implementing automatic grading bandwidth regulation on multi-service transmission platform", patents CN101184041 (A); CN101184041 (B), 2008-05-21.
[4] Rong E, Qi F., Method for realizing dynamic jitter buffering regulation in speed sound transmission course, patents CN1677954 (A); CN100417129 (C), 2005-10-05.
[5] Sparrell C.J., Vasilevsky A.D., Ruszczyk C., Zhang J., Local area-networked system having intelligent traffic control and efficient bandwidth management, patent US7529263 (Bl), 2009-05-05.
[6] Huang S., Data transmission rate regulation method, device and wireless access point, patent CN103532669 (A), 2014-01-22.
[7] Ge J., Regulation and control method for video transmission on narrow-band network, patent CN103269458 (A), 2013-08-28.
[8] Falk W., Thomas D.W., Managing service level agreements using statistical process control in a networked computing environment, patent US2012131172 (Al), 2012-05-24.
[9] Wang X., Schulzrinne H., "Comparison of Adaptive Internet Multimedia Applications", IEICE Transactions on Communications, Vol. E82-B, No. 6, 1999.
[10] Ahmad J., Sinclair C.D., Werritty A., "Log-logistic flood frequency analysis", Journal of Hydrology, 98, pp. 205-224, 1988.
[11] Balakrishnan N., Handbook of the Logistic Distribution. Marcel Dekker, New York. ISBN 0-8247-8587-8, 1992.
[12] D'Agostino R.B., Stephens M.A. (eds), Goodness-of-Fit techniques, New York: Marcel
Dekker, 1986.
[13] Walpole R.E., Myers R.H., Myers S.L., Ye K.E., Probability and Statistics for Engineers and Scientists, Pearson, ISBN 978-0321629111, 2011.
[14] Askey R.A., Roy R., Beta function, in Olver, Frank W. J.; Lozier, Daniel M.; Boisvert, 5 Ronald F.; Clark, Charles W., NIST Handbook of Mathematical Functions, Cambridge
University Press, ISBN 978-0521192255, 2010.
[15] Eligius M.T.H., Boglárka G.-T.. Introduction to Nonlinear and Global Optimization, Springer, ISBN 978-0-387-88669-5, 2010.
