Procedimiento de recuperación de paquetes perdidos para protocolos de transmisión de paquetes.

Un procedimiento de transmitir datos desde un origen a través de una pluralidad de canales,

que comprende las etapasde:

a) disponer los datos a transmitir como un conjunto ordenado de símbolos de entrada;

b) generar una pluralidad de símbolos de salida para cada uno entre la pluralidad de canales, en donde cada símbolo desalida es generado por las etapas de:

1) seleccionar, de un alfabeto de claves, una clave I para el símbolo de salida que está siendo generado, en donde elalfabeto de claves contiene muchos más miembros que el número de símbolos de entrada en el conjunto ordenado desímbolos de entrada, de modo que pueda ser generado un número efectivamente ilimitado de símbolos de salida quesean generalmente independientes entre sí;

2) determinar un peso, W(I), como una función de I, en que los pesos W son enteros positivos que varían entre almenos dos valores y son mayores que uno para al menos algunas claves en el alfabeto de claves;

3) seleccionar W(I) de los símbolos de entrada según una función de I, formando así una lista AL(I) de W(I) símbolosde entrada asociados al símbolo de salida; y

4) calcular un valor B(I) del símbolo de salida a partir de una función de valor predeterminado de los W(I) símbolos deentrada asociados;

c) paquetizar al menos uno entre la pluralidad de símbolos de salida en cada uno entre una pluralidad de paquetes; y

d) transmitir la pluralidad de paquetes por la pluralidad de canales;

en el cual al menos dos entre la pluralidad de canales llevan paquetes que contienen símbolos de salida generados convalores distintos para la clave I, de modo que un destinatario pueda descodificar el conjunto ordenado de símbolos deentrada a partir de un cierto número de símbolos de salida igual a, o levemente mayor que, el número de símbolos deentrada en el conjunto ordenado de símbolos de entrada, suponiendo que los símbolos de entrada y los símbolos desalida representan el mismo número de bits de datos.

Procedimiento de recuperación de paquetes perdidos para protocolos de transmisión de paquetes Antecedentes de la invención La presente invención se refiere a la codificación y descodificación de datos en sistemas de comunicación y, más específicamente, a sistemas de comunicación que codifican y descodifican datos para tener en cuenta errores y brechas en los datos comunicados, y para utilizar eficazmente los datos comunicados que emanan desde más de un origen.

La transmisión de ficheros entre un remitente y un destinatario por un canal de comunicaciones ha sido tema de mucha bibliografía. Preferiblemente, un destinatario desea recibir una copia exacta de los datos transmitidos por un canal por un remitente, con cierto nivel de certeza. Allí donde el canal no tiene fidelidad perfecta (lo que abarca la mayoría de todos los sistemas físicamente realizables) , una preocupación es cómo tratar los datos perdidos o desfigurados en la transmisión. Los datos perdidos (borrados) son a menudo más fáciles de tratar que los datos desfigurados (errores) , porque el destinatario no siempre puede decir cuándo los datos desfigurados son datos recibidos con errores. Muchos códigos de corrección de errores han sido desarrollados para corregir borrados (los llamados “códigos de borrado”) y / o errores (“códigos correctores de errores” o “ECC”) . Habitualmente, el código específico usado se escoge en base a alguna información acerca de las infidelidades del canal a través del cual se están transmitiendo los datos y la naturaleza de los datos que se están transmitiendo. Por ejemplo, allí donde se conoce que el canal tiene largos periodos de infidelidad, un código de errores de ráfaga podría ser el más adecuado para esa aplicación. Allí donde solamente se esperan errores breves e infrecuentes, un código de paridad sencilla podría ser lo mejor.

La transmisión de ficheros entre múltiples remitentes y / o múltiples receptores por un canal de comunicaciones también ha sido tema de mucha bibliografía. Habitualmente, la transmisión de ficheros desde múltiples remitentes requiere la coordinación entre los múltiples remitentes para permitir que los remitentes minimicen la duplicación de esfuerzos. En un típico sistema de múltiples remitentes que envían un fichero a un receptor, si los remitentes no coordinan qué datos transmitirán y cuándo, sino que, en cambio, simplemente envían segmentos del fichero, es probable que un receptor reciba muchos segmentos duplicados inservibles. De manera similar, allí donde distintos receptores se incorporan a una transmisión desde un remitente en distintos momentos en el tiempo, una preocupación es cómo asegurar que todos los datos que reciben los receptores desde el remitente sean útiles. Por ejemplo, supongamos que el remitente está transmitiendo continuamente datos acerca del mismo fichero. Si el remitente solamente envía segmentos del fichero original y se pierden algunos segmentos, es probable que un receptor reciba muchos segmentos duplicados inservibles antes de recibir una copia de cada segmento en el fichero.

Otra consideración al seleccionar un código es el protocolo usado para la transmisión. En el caso de la intrared global de redes conocida como “Internet” (con “I” mayúscula) , se usa un protocolo de paquetes para el transporte de datos. Ese protocolo se llama el Protocolo de Internet o “IP”, para abreviar. Cuando un fichero, u otro bloque de datos, ha de ser transmitido por una red del IP, se divide en símbolos de entrada de igual tamaño y los símbolos de entrada se colocan en paquetes consecutivos. Al estar basado en paquetes, un esquema de codificación orientado a paquetes podría ser adecuado. El “tamaño” de un símbolo de entrada puede ser medido en bits, ya sea que el símbolo de entrada esté o no efectivamente dividido en un flujo de bits, donde un símbolo de entrada tiene un tamaño de M bits cuando el símbolo de entrada se selecciona entre un alfabeto de 2M símbolos.

El Protocolo de Control de Transporte (“TCP”) es un esquema de control de paquetes punto a punto de uso común, que tiene un mecanismo de acuse de recibo. El TCP es bueno para las comunicaciones de uno a uno, donde tanto el remitente como el destinatario acuerdan cuándo tendrá lugar y se recibirá la transmisión, y ambos acuerdan cuáles transmisores y receptores se usarán. Sin embargo, el TCP a menudo no es adecuado para comunicaciones de uno a muchos o de muchos a muchos, o allí donde el remitente y el destinatario determinan independientemente cuándo y dónde transmitirán o recibirán datos.

Al usar el TCP, un remitente transmite paquetes ordenados y el destinatario acusa recibo de cada paquete. Si se pierde un paquete, no se enviará ningún acuse de recibo al remitente y el remitente reenviará el paquete. La pérdida de paquetes tiene un cierto número de causas. En Internet, la pérdida de paquetes a menudo ocurre porque la congestión esporádica causa que el mecanismo de almacenamiento temporal en un encaminador colme su capacidad, forzándolo a descartar paquetes entrantes. Con protocolos tales como TCP / IP, el paradigma de acuse de recibo permite que los paquetes se pierdan sin fallo total, dado que los paquetes perdidos pueden ser simplemente retransmitidos, bien en respuesta a una falta de acuse de recibo o bien en respuesta a una solicitud explícita del destinatario. En cualquier caso, un protocolo de acuse de recibo requiere un canal de retorno desde el destinatario al remitente.

Aunque los protocolos basados en acuse de recibo son generalmente adecuados para muchas aplicaciones y, de hecho, se usan extensamente por la Internet actual, son ineficaces y, a veces, completamente inviables para ciertas aplicaciones. En particular, los protocolos basados en acuse de recibo responden mediocremente en redes con altas latencias, altas tasas de pérdida de paquetes, altas y bajas no coordinadas de destinatarios y / o ancho de banda sumamente asimétrico.

La alta latencia se da allí donde los acuses de recibo se toman un largo tiempo para viajar desde el destinatario de regreso al remitente. La alta latencia puede dar como resultado que el tiempo global antes de una retransmisión sea prohibitivamente largo. Las altas tasas de pérdida de paquetes también causan problemas allí donde varias retransmisiones del mismo paquete pueden dejar de llegar, lo que conduce a un largo retardo para obtener el último, o los pocos últimos, paquetes sin suerte.

Las “altas y bajas no coordinadas de destinatarios” se refieren a la situación donde cada destinatario puede incorporarse a, y abandonar, una sesión de transmisión en marcha, según su propio criterio. Esta situación es típica en Internet, los servicios de próxima generación tales como el “vídeo a petición” y otros servicios a ser ofrecidos por los proveedores de red en el futuro. En el típico sistema, si un destinatario se incorpora a, y abandona, una transmisión en marcha sin la coordinación de los remitentes, el destinatario probablemente percibirá una pérdida de un gran número de paquetes, con patrones de pérdidas ampliamente dispares percibidos por los distintos destinatarios.

El ancho de banda asimétrico se refiere a la situación donde un trayecto inverso de datos desde el destinatario al remitente (el canal de retorno) está menos disponible, o es más costoso, que el trayecto directo. El ancho de banda asimétrico puede hacer que sea prohibitivamente lento y / o caro para el destinatario acusar recibo de paquetes frecuentemente y los acuses infrecuentes de recibo pueden nuevamente introducir retardos.

Además, los protocolos basados en acuses de recibo no se adaptan bien para la difusión, donde un remitente está enviando simultáneamente un fichero a múltiples usuarios. Por ejemplo, supongamos que un remitente está difundiendo un fichero a múltiples destinatarios por un canal satelital. Cada destinatario puede experimentar un patrón distinto de pérdida de paquetes. Los protocolos que dependen de datos de acuse de recibo (ya sea positivo o negativo) para el suministro fiable del fichero requieren un canal de retorno desde cada destinatario al remitente, y esto puede ser prohibitivamente caro de proporcionar. Además, esto requiere un remitente complejo y potente, para ser capaz de gestionar debidamente todos los datos de acuse de recibo enviados desde los destinatarios. Otro inconveniente es que si distintos destinatarios pierden distintos conjuntos de paquetes, la redifusión de paquetes perdidos solamente por unos pocos de los destinatarios causa la recepción de paquetes duplicados inservibles por parte de otros destinatarios. Otra situación que no se gestiona... [Seguir leyendo]

1. Un procedimiento de transmitir datos desde un origen a través de una pluralidad de canales, que comprende las etapas de:

a) disponer los datos a transmitir como un conjunto ordenado de símbolos de entrada;

b) generar una pluralidad de símbolos de salida para cada uno entre la pluralidad de canales, en donde cada símbolo de salida es generado por las etapas de:

1) seleccionar, de un alfabeto de claves, una clave I para el símbolo de salida que está siendo generado, en donde el alfabeto de claves contiene muchos más miembros que el número de símbolos de entrada en el conjunto ordenado de símbolos de entrada, de modo que pueda ser generado un número efectivamente ilimitado de símbolos de salida que sean generalmente independientes entre sí;

2) determinar un peso, W (I) , como una función de I, en que los pesos W son enteros positivos que varían entre al menos dos valores y son mayores que uno para al menos algunas claves en el alfabeto de claves;

3) seleccionar W (I) de los símbolos de entrada según una función de I, formando así una lista AL (I) de W (I) símbolos de entrada asociados al símbolo de salida; y

4) calcular un valor B (I) del símbolo de salida a partir de una función de valor predeterminado de los W (I) símbolos de entrada asociados;

c) paquetizar al menos uno entre la pluralidad de símbolos de salida en cada uno entre una pluralidad de paquetes; y

d) transmitir la pluralidad de paquetes por la pluralidad de canales;

en el cual al menos dos entre la pluralidad de canales llevan paquetes que contienen símbolos de salida generados con valores distintos para la clave I, de modo que un destinatario pueda descodificar el conjunto ordenado de símbolos de entrada a partir de un cierto número de símbolos de salida igual a, o levemente mayor que, el número de símbolos de entrada en el conjunto ordenado de símbolos de entrada, suponiendo que los símbolos de entrada y los símbolos de salida representan el mismo número de bits de datos.

2. El procedimiento de la reivindicación 1, en el cual el origen comprende un único origen que genera valores para la clave I para el único origen y distribuye paquetes de salida por la pluralidad de canales, de modo que el contenido de información recibido desde dos cualesquiera entre la pluralidad de canales no sea enteramente duplicativo.

3. El procedimiento de la reivindicación 1, en el cual los valores para la clave I son seleccionados independientemente para cada uno entre la pluralidad de canales, de modo que el contenido de información recibido desde dos cualesquiera entre la pluralidad de canales no sea enteramente duplicativo.

4. El procedimiento de la reivindicación 1, en el cual la etapa de determinación comprende las etapas de:

calcular, según una función predeterminada de I y una distribución de probabilidades, dicho peso W (I) , en donde la distribución de probabilidades es sobre al menos dos enteros positivos, al menos uno de los cuales es mayor que uno;

calcular una entrada de lista para la lista AL (I) ; y repetir la etapa de calcular una entrada de lista para la lista AL (I) hasta que se calculen W (I) entradas de la lista.

5. El procedimiento de la reivindicación 4, en el cual la etapa de determinar W (I) comprende una etapa de determinar W (I) de modo que W se aproxime a una distribución predeterminada sobre el alfabeto de claves.

6. El procedimiento de la reivindicación 5, en el cual la distribución predeterminada es una distribución uniforme.

7. El procedimiento de la reivindicación 5, en el cual la distribución predeterminada es una distribución de curva de campana.

8. El procedimiento de la reivindicación 5, en el cual la distribución predeterminada es tal que W=1 tiene una probabilidad de 1/K, donde K es el número de símbolos de entrada en el fichero de entrada, y W=i tiene una probabilidad de 1/i (i-1) para i=2, ..., K.

9. El procedimiento de la reivindicación 5, en el cual la distribución predeterminada es tal que, dados parámetros R1 y R2 afinables, y siendo K el número de símbolos de entrada en el fichero de entrada, el peso W=1 tiene una probabilidad

proporcional a R1/K, los pesos en una clase de peso bajo, que oscila entre el peso W=2 y el peso W=K / R2-1, tienen una probabilidad proporcional a 1 / (W (W-1) (1-W-R2 / K) ) y los pesos en una clase de peso alto, que oscilan desde el peso W=K / R2 hasta el peso W=K, tienen una distribución de probabilidad seleccionada.

10. Un aparato para transmitir datos desde un origen a través de una pluralidad de canales, que comprende:

a) medios para disponer los datos a transmitir como un conjunto ordenado de símbolos de entrada;

b) medios que generan una pluralidad de símbolos de salida para cada uno entre la pluralidad de canales, en donde 5 dichos medios están configurados para generar cada símbolo de salida:

1) seleccionando, entre un alfabeto de claves, una clave I para el símbolo de salida que está siendo generado, en donde el alfabeto de claves contiene muchos más miembros que el número de símbolos de entrada en el conjunto ordenado de símbolos de entrada, de modo que pueda ser generado un número efectivamente ilimitado de símbolos de salida que sean generalmente independientes entre sí;

2) determinando un peso, W (I) , como una función de I, en donde los pesos W son enteros positivos que varían entre al menos dos valores y son mayores que uno para al menos algunas claves en el alfabeto de claves;

3) seleccionando W (I) de los símbolos de entrada según una función de I, formando así una lista AL (I) de W (I) símbolos de entrada asociados al símbolo de salida; y

4) calculando un valor B (I) del símbolo de salida a partir de una función de valor predeterminado de los W (I) símbolos 15 de entrada asociados;

c) medios para paquetizar al menos uno entre la pluralidad de símbolos de salida en cada uno entre una pluralidad de paquetes; y

d) medios para transmitir la pluralidad de paquetes por la pluralidad de canales, en donde al menos dos entre la pluralidad de canales llevan paquetes que contienen símbolos de salida generados con valores distintos para la clave I, de modo que 20 un destinatario pueda descodificar el conjunto ordenado de símbolos de entrada a partir de un cierto número de símbolos de salida iguales a, o levemente mayores que, el número de símbolos de entrada en el conjunto ordenado de símbolos de entrada, suponiendo que los símbolos de entrada y los símbolos de salida representen el mismo número de bits de datos.