Un método para evaluar una anchura de banda disponible en un trayecto de transferencia de datos que transfiere datos entre nodos de comunicación de datos de una red de datos,

comprendiendo: suministrar (13) paquetes de sonda que recorren el trayecto de transferencia de datos durante funcionamiento en tiempo real del trayecto de transferencia de datos; en respuesta al recorrido del trayecto de transferencia de datos por dichos paquetes de sonda, y durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos, suministrar datos de estimación para uso en estimar la anchura de banda disponible; y producir (17) una estimación de la anchura disponible durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos, incluyendo aplicar una operación de filtro Kalman a dichos datos de estimación durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos, caracterizado porque dicha operación de filtro Kalman usa parámetros de combinación para uso en combinar dichos datos de estimación con información actual de estado de filtro para producir nueva información de estado de filtro, y en el que dicha aplicación incluye suministrar dichos parámetros de combinación para uso en dicha operación de filtro

Campo de la invención

La presente invención se refiere generalmente a redes de datos y, más particularmente, a la evaluación de trayectos de transferencia de datos en redes de datos.

Antecedentes de la invención

Los documentos listados a continuación son incorporados en esto por referencia:

G. Bishop y G. Welch, "Una introducción al filtro Kalman", Special Internet Group on Computer Graphics and Interactive Techniques (SIGGRAPH) 2001, Curso 8.

K. Jacobsson, H. Hjalmarsson, N. Möller y K.H. Johansson, "Estimación de tiempo de retardo de ida y vuelta (RTT: Round-Trip delay Time y anchura de banda para aplicaciones de control de congestión en redes de comunicación", en Conferencia sobre Decisión y Control (CDC) del IEEE, Memorias de 2.004, Paradise Island, Bahamas, 2004.

M. Jain y C. Dovrolis, "Carga de trayecto: una herramienta de medición para anchura de banda disponible de extremo a extremo". En Memorias de curso de mediciones pasivas y activas (PAM), 2.002.

M. Jain y C. Dovrolis, "Anchura de banda disponible de extremo a extremo: metodología de medición. Dinámica y relación con rendimiento de Transmission Control Protocol (TCP)". En Memorias de Association for Computing Machinery Special Interest Group on Data Communication (ACM Sigcomm), 2.002.

S. Keshav, "Un procedimiento de control-teórico para control de flujo". En Memorias de Association for Computing Machinery Special Interest Group on Data Communication (ACM Sigcomm)'91, páginas 3 a 15, Zurich, Suiza, septiembre de 1.991.

M. Kim y B. Noble, "Estimación ágil estable de red", Departamento de Ingeniería Eléctrica y Ciencia de Ordenadores de la Universidad de Michigan. CSE-TR-432-00. 2.000.

M. Kim y B. Noble, "Estimación de red móvil", Cómputo y Operación en Red Móvil, Association for Computing Machinery Mobile Computing and Networking (ACM MOBICOM), Roma, Italia 2.001,

B. Melander, M. Björkman y P. Gunninberg, "Un nuevo método de análisis y sondeo de extremo a extremo para estimar estrangulamientos de anchura de banda", Memorias de Globecomm'00 del IEEE, San Francisco, EE.UU. noviembre 2.000.

A Pasztor y D. Weiteh, "La dependencia del tamaño de paquete de métodos semejantes a par de paquetes", en Memorias, Décimo Seminario Internacional sobre Calidad de Servicio (IWQoS 2002), Miami Beach, EE.UU. mayo

2.002.

V. Ribeiro, R.Riedi, R. Baraniuk, J. Navratil, L. Cottrell, "Barrido en frecuencia de trayecto: estimación eficiente de anchura de banda disponible para trayectos de red", en Memorias de Seminario de mediciones pasivas y activas (PAM), 2003.

A. Shriram, M. Murray, Y. Hyun, N. Brownlee, A. Broido, M. Fomenkov y KC. Claffy, "Comparación de herramientas públicas de estimación de anchura de banda de extremo a extremo en enlaces de alta velocidad" en Seminario de mediciones pasivas y activas (PAM), 2.005.

R.D, Nowak y M.J. Coates, "Tomografía de red que usa paquetes de unidifusión juntos entre sí", Patente de EE.UU.

6.839.754 (2.005).

M.J. Coates y R.D. Nowak, "Inferencia secuencial de Monte Carlo de retardos internos en redes de datos no fijas". Actas del IEEE sobre procesamiento de señales, 50(2): 366-367, febrero 2.002.

S. Ekelin y M. Nilsson, "Supervisión continua de anchura de banda disponible por un trayecto de red", Segundo Seminario Nacional Sueco de Operación en Red de Ordenadores, Karlstad, Suecia, 23-24 de noviembre, 2004.

R. Prasad, M. Murray, C. Dovrolis, K.C. Claffy, "Estimación de anchura de banda: métrica, técnicas de medición y herramientas", Revista Redes del IEEE (2003).

La capacidad de medir la anchura de banda disponible de extremo a extremo por un trayecto en una red de datos es útil en varios contextos, incluyendo verificación de acuerdo de nivel de servicio (SLA: Service Level Agreement), observación de red y selección de servidor. La observación pasiva de la anchura de banda disponible de un trayecto de red de extremo a extremo es posible en principio siempre que pueda accederse a todos los nodos de red en el trayecto. Sin embargo, esto es típicamente imposible y la estimación de la anchura de banda disponible de extremo a extremo es efectuada típicamente por sondeo activo del trayecto de red. La anchura de banda disponible puede ser estimada inyectando tráfico de sondas dentro de la red y analizando después los efectos observados de tráfico cruzado en las sondas. Esta clase de medición activa necesita solo acceso a los ordenadores nodales (nodos) de emisor y receptor, y no precisa acceso a ninguno de los nodos intermedios en el trayecto entre el emisor y el receptor.

Procedimientos convencionales para sondeo activo necesitan la inyección de tráfico de paquetes de sonda dentro del trayecto que interesa a una velocidad que sea suficiente transitoriamente para usar toda la anchura de banda disponible y causar congestión. Si solo son usados un número pequeño de paquetes de sonda, entonces la congestión transitoria producida puede ser absorbida por colas de memoria intermedia en los nodos. Por consiguiente, no se causa pérdida de paquetes sino más bien solo un incremento pequeño de retardo de trayecto de unos pocos paquetes. La medida deseada de la anchura de banda disponible es determinada basada en el incremento de retardo. Paquetes de sonda pueden ser enviados en pares o en trenes, a diversas velocidades de paquetes de sonda. La velocidad de paquetes de sonda donde el retardo de trayecto empieza a aumentar corresponde al punto de congestión y, por tanto, es indicativa de la anchura de banda disponible. Paquetes de sonda también pueden ser enviados tal que varía la separación temporal entre paquetes de sonda dentro de un tren dado, de modo que cada tren puede cubrir un margen de velocidades de sondas.

Soluciones convencionales tales como las mencionadas anteriormente no producen estimaciones en tiempo real de la anchura de banda disponible o no producen estimaciones suficientemente precisas de la anchura de banda disponible, o ambas. Estas soluciones también tienden a exigir recursos significativos de procesamiento de datos o recursos significativos de memoria, o ambos.

Por tanto, es deseable proveer lo necesario para una solución de sondeo activo que pueda estimar la anchura de banda disponible de un trayecto en una red de datos sin las dificultades antes mencionadas de soluciones convencionales.

Sumario de la invención

Realizaciones ejemplares de la invención proveen lo necesario para modelar una condición en un trayecto de transferencia de datos apropiadamente para permitir el uso de un procedimiento basado en filtro para proporcionar una estimación de la condición. Esto permite estimaciones precisas en tiempo real de la condición con exigencias modestas de recursos de procesamiento de datos y de memoria.

Descripción breve de los dibujos

La Figura 1 ilustra operaciones ejemplares que pueden ser realizadas según la invención.

La Figura 2 ilustra esquemáticamente un aparato para evaluar un trayecto de transferencia de datos según realizaciones ejemplares de la invención.

La Figura 3 ilustra gráficamente un modelo lineal por tramos utilizado por realizaciones ejemplares de la invención.

Descripción detallada

Realizaciones ejemplares de la invención proveen lo necesario para estimación rápida y precisa de una condición dependiente del tiempo asociada con un trayecto de red con conmutación de paquetes, por ejemplo, un trayecto entre dos ordenadores nodales o nodos de red en Internet u otra red IP (Internet Protocol). Sondeo activo es usado en combinación con filtración para estimar variables de modelo de red relacionadas con la condición que interesa. Entonces, la estimación de la condición que interesa es obtenida basada en las variables estimadas.

Las propiedades del trayecto de red son muestreadas transmitiendo paquetes de sonda en un modelo específico a través del trayecto de red. Sus marcadores de tiempo son grabados al emitir y al recibir, proporcionando una medición de una cantidad relacionada con las variables de modelo de red. Esto es repetido una y otra vez mientras sea deseado para rastrear la condición que interesa.

El uso de filtración permite la estimación en tiempo real. Para... [Seguir leyendo]

1. Un método para evaluar una anchura de banda disponible en un trayecto de transferencia de datos que transfiere datos entre nodos de comunicación de datos de una red de datos, comprendiendo:

suministrar (13) paquetes de sonda que recorren el trayecto de transferencia de datos durante funcionamiento en tiempo real del trayecto de transferencia de datos;

en respuesta al recorrido del trayecto de transferencia de datos por dichos paquetes de sonda, y durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos, suministrar datos de estimación para uso en estimar la anchura de banda disponible; y

producir (17) una estimación de la anchura disponible durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos, incluyendo aplicar una operación de filtro Kalman a dichos datos de estimación durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos,

caracterizado porque

dicha operación de filtro Kalman usa parámetros de combinación para uso en combinar dichos datos de estimación con información actual de estado de filtro para producir nueva información de estado de filtro, y en el que dicha aplicación incluye suministrar dichos parámetros de combinación para uso en dicha operación de filtro.

2. El método de la reivindicación 1, en el que uno de dichos parámetros de combinación es un parámetro de temporización asociado con dichos paquetes de sonda.

3. El método de la reivindicación 2, incluyendo transmitir una secuencia de dichos paquetes de sonda por el trayecto de transferencia de datos a una velocidad de transmisión, y en el que dicho parámetro de temporización es dicha velocidad de transmisión.

4. El método de la reivindicación 3, incluyendo proporcionar una indicación de dicha velocidad de transmisión en uno de dichos paquetes de sonda.

5. El método de la reivindicación 2, incluyendo proporcionar dicho parámetro de temporización en uno de dichos paquetes de sonda.

6. El método de cualquiera de las reivindicaciones 1 a 5, incluyendo proporcionar uno de dichos parámetros de combinación en uno de dichos paquetes de sonda.

7. Un aparato para evaluar una anchura de banda disponible en un trayecto de transferencia de datos que transfiere datos entre nodos de comunicación de datos de una red de datos, comprendiendo:

una unidad (24) de producción de datos para recibir paquetes de sonda que han recorrido el trayecto de transferencia de datos durante el funcionamiento en tiempo real del trayecto de transferencia de datos, respondiendo dicha unidad de producción de datos al recorrido del trayecto de transferencia de datos por dichos paquetes de sonda para producir, durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos, datos de estimación para uso en estimar la anchura de banda disponible;

una unidad de estimación (26, 28) acoplada a dicha unidad de producción de datos para producir una estimación de la condición durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos, incluyendo dicha unidad de estimación un filtro Kalman para aplicar una operación de filtro Kalman a dichos datos de estimación durante dicho funcionamiento en tiempo real del trayecto de transferencia de datos, caracterizado porque dicha operación de filtro Kalman usa parámetros de combinación para combinar dichos datos de estimación con información actual de estado de filtro para producir nueva información de estado de filtro; y porque el aparato comprende además unidades (25; 27) acopladas a dicha unidad de estimación para proporcionarla dichos parámetros de combinación para uso endicha operación de filtro.

8. El aparato de la reivindicación 7, en el que dicha unidad de estimación y una porción de dicha unidad de producción de datos están situadas de modo físicamente separadas del resto de dicha unidad de producción de datos.

9. El aparato de cualquiera de las reivindicaciones 7-8, en el que uno de dichos parámetros de combinación es un parámetro de temporización asociado con dichos paquetes de sonda.

10. El aparato de la reivindicación 9, en el que dicho parámetro de temporización es una velocidad de transmisión a la que dichos paquetes de sonda han sido transmitidos por el trayecto de transferencia de datos.

11. El aparato de cualquiera de las reivindicaciones 7 a 10, en el que dichas unidades están acopladas a dicha

unidad de producción de datos para extraer una indicación de dicha velocidad de transmisión desde uno de dichos paquetes de sonda.

12. El aparato de cualquiera de las reivindicaciones 7 a 11, en el que dichas unidades están acopladas a dicha unidad de producción de datos para extraer dicho parámetro de temporización de uno de dichos paquetes de sonda.

13. El aparato de cualquiera de las reivindicaciones 7 a 12, en el que dichas unidades están acopladas a dicha unidad de producción de datos para extraer uno de dichos parámetros de combinación de uno de dichos paquetes de sonda.