Prácticas de Infraestructuras de Redes / Redes entre Pares

Grupo de Sistemas y Comunicaciones

Universidad Rey Juan Carlos

Curso 2006-07


[ Calendario de clases | Foro | Prácticas | Información general ]



Índice General


Normativa

Se van a realizar varias prácticas durante el curso. Como veis, cada práctica lleva asociada una fecha de entrega. Las prácticas entregadas hasta su fecha serán puntuadas de 0 a 10. Aceptaremos la entrega de una práctica hasta 4 semanas después de su fecha de entrega, o hasta la fecha del examen final, lo que ocurra antes. Estas prácticas entregadas tarde serán puntuadas de 0 a 8. Las prácticas no entregadas en estos periodos se considerarán no presentadas.

Cada práctica tendrá un peso proporcional al número de semanas que tiene asignada. Para aprobar la asignatura hay que presentar todas las prácticas.

La nota de prácticas se obtiene como sigue: la nota de cada práctica se multiplicará por su número de semanas correspondiente. La suma de estos valores, normalizada a un valor entre -3 y 3, será la nota de prácticas. Si la nota es negativa la calificación de las prácticas será NO APTO.

Práctica 1: Complejidad polinómica

La sucesión de Fibonacci, $F(i)$, se define de la siguiente manera (para $i \ge 0$):

\begin{displaymath}F(0)=0\end{displaymath}


\begin{displaymath}F(1)=1\end{displaymath}


\begin{displaymath}F(i)=F(i-1)+F(i-2), i>1.\end{displaymath}

El cálculo de un término $F(i)$ de esta sucesión se puede hacer de dos formas:

Usando el lenguaje de programación que quieras de entre los disponibles en el laboratorio (C, C++, Ada, Java, etc.), haz un programa ``fibo1'' que calcule el $n$-simo término de la sucesión de Fibonacci de manera recursiva, y otro llamado ``fibo2'' que lo calcule de manera iterativa. Estos programas deben aceptar un argumento, que será el número $n$, y mostrar por pantalla únicamente un número, que será el valor del término $F(n)$.

Utilizando la orden ``time'' del sistema, calcula el tiempo en modo usuario (línea ``user'' de la salida de time) que tarda cada uno de los dos programas en hallar los términos 5, 10, 15, 20, 25, 30, 35, 40, 41, 42, 43, 44 y 45 de la sucesión, y muéstralos en una tabla.

Parte opcional

Adicionalmente a los dos programas pedidos, podéis realizar de manera opcional una versión ``memoizada'', que consiste en:

Llamad a este nuevo programa ``fibo3'' y calculad el tiempo que tarda con los mismos valores que los anteriores.

Fecha de entrega

Hasta el jueves 26-10-2006.

Forma de entrega

Por correo electrónico a anto@gsyc.escet.urjc.es.

El mensaje debe llevar como asunto IR-P2P P1 y contener:

Práctica 2: Sonda

En esta práctica queremos estudiar si es cierto que es distinta la latencia del ancho de banda existente entre dos equipos en Internet. Para ello haremos un programa que hace pings ICMP, y permite estimar estos valores (latencia y ancho de banda) con ellos.

El programa que vais a hacer recibe un nombre de máquina. El programa entonces hará pings ICMP con distintos tamaños de paquete (man ping), que luego usará para evaluar latencia y ancho de banda. Usad el tamaño de paquete mínimo (idealmente 0, pero al no ser esto posible, usad el menor disponible) y un tamaño grande, para que los resultados sean significativos.

Para el tamaño mínimo de paquete el programa debe hacer 20 pings, y considerará la mitad del valor más pequeño obtenido como la latencia $L$ entre los equipos. Tened en cuenta que los tiempos que devuelve ping son de ida y vuelta (RTT, round-trip time), y por eso dividimos por 2. Tened también en cuenta que hay encaminadores que filtran los paquetes de ping (todos o los mayores de un tamaño).

Para el tamaño grande $K$ de paquete el programa debe hacer 20 pings, y guardar la mitad del retardo medio obtenido. Una vez obtenidos estos datos, el ancho de banda se puede estimar suponiendo que el retardo medio $t$ observado para un paquete de tamaño $K$ bits es la suma de su tiempo de transmisión y la latencia $L$. Por lo tanto, el ancho de banda $B$ se puede obtener como

\begin{displaymath}B \approx \frac{K}{t-L}.\end{displaymath}

El resultado de esta práctica tiene que ser un programa que se llame probe y que reciba en su línea de comandos la máquina que debe sondear. Una posible ejecución del programa podría ser:

 
$ probe gsyc.escet.urjc.es
Latencia: 
0.89 ms
Ancho de banda:
1568 Kbps

Tened cuidado con los tamaños, porque hay que saber si son en bits, octetos, kilos (1000) o Ks (1024). En particular, Kbps son kilobits por segundo. También debéis tener en cuenta las cabeceras ICMP e IP que realmente llevan los paquetes.

Cuando tengáis el programa funcionando, haced al menos 20 pruebas con él y guardad los resultados. Las pruebas deben sondear equipos por distintas zonas de Internet (lo notaréis por las latencias observadas). Nos tenéis que enviar las pruebas y resultados.

Parte opcional

Como parte opcional, quien quiera puede hacer que se calculen retardos para distintos tamaños de paquete y use estos valores para obtener una recta de mínima distancia a esos valores (recta de regresión lineal). Con dicha recta, la latencia será el valor en 0 de la misma y el ancho de banda la inversa de su pendiente. Para un caso concreto nos interesa que nos deis la fórmula de la recta (que da el retardo estimado dada la longitud del paquete), y los valores estimados de latencia y ancho de banda.

En este caso, no es necesario que vuestro programa haga todos los cálculos. El programa puede obtener los retardos y luego a mano o con programas de procesamiento matemático podéis calcular la recta. Sin embargo, se valorará que el proceso sea lo más automático posible.

Para este caso haced las mismas pruebas de la parte obligatoria con él y guardad los resultados. Nos tenéis que enviar las pruebas y resultados.

Fecha de entrega

Hasta el jueves 9-11-2006.

Forma de entrega

Por correo electrónico a anto@gsyc.escet.urjc.es. El mensaje debe llevar como asunto IR-P2P P2 y contener:

Práctica 3: Carreras en la web

En esta práctica queremos estudiar si es cierto lo que hemos contado en clase de que la línea recta puede no ser la distancia más corta entre dos puntos. Para ello vamos a echar carreras entre descargas de páginas web. En la práctica teneis que hacer un programa que arranque simultáneamente tres descargas de la misma página web e informe del tiempo de descarga de cada una. Para que las tres descargas sean distintas, una de ellas se conectará directamente al servidor de web de la página, mientras que cada una de las otras dos usará un proxy web distinto. Luego os pedimos que penséis cómo podríais intentar mejorar el rendimiento de vuestro programa si teneis más de dos proxies disponibles.

No se espera que en esta práctica desarrolléis vuestro propio cliente HTTP (aunque si queréis lo podeis hacer; mirad la práctica de la asignatura Redes de Área Local de ITIS). Lo que os sugerimos es que hagáis un script que invoque a clientes (no interactivos) disponibles. Un posible candidato es wget. Este cliente también puede dialogar con proxies web.

Es muy importante que al pedir una página a un proxy le digáis que no os dé una copia que pueda tener en caché. Si usáis wget, mirad en la página de manual como activar esta opción. Si usáis otro navegador, debes asegurarte que usa:

Pragma: no-cache
en sus peticiones HTTP.

Para localizar proxies web que podais usar, podeis hacer búsquedas en la web. Por ejemplo, yo he encontrado esta lista.

El resultado de esta práctica tiene que ser un programa que se llame race y que reciba en su línea de comandos las URL de los dos proxies a usar y de la página a descargar. El programa debe arracar las tres descargas simultáneamente, y cuando las tres hayan finalizado informar de lo que ha tardado cada una. Dejamos a vuestra elección qué hacer con la página una vez descargada. Una posible ejecución del programa podría ser:

race http://proxy1.com:8080 http://proxy2.com:9090 http://www.google.com/pp.html
Ruta por http://proxy2.com:9090: 0:05.08
Ruta directa: 0:05.66
Ruta por http://proxy1.com:8080: 0:10.11
Observad que los resultados aparecen ordenados por tiempo. El tiempo se presenta en el formato del comando time, que es minutos:segundos.centésimas. Podeis usar este comando para temporizar una descarga.

Teneis que controlar posibles errores. En particular, si un proxy no responde vuestro programa no debe insistir.

Cuando tengáis el programa funcionando, haced la menos 20 pruebas con él, y guardad los resultados. Las pruebas deben usar varios proxies y páginas web. Nos tenéis que enviar las pruebas y resultados. Marcad claramente en cuántos y cuáles casos las rutas indirectas han sido más rápidas.

Parte opcional

Finalmente, suponed que tenéis un fichero con muchos proxies web que podríais utilizar para vuestro programa. Pensad en alguna forma de aprovechar este hecho para reducir el tiempo de la descarga más rápida. Posiblemente tengáis que hacer vuestras propias pruebas de latencia y mantener la historia de anteriores descargas. Detalla tanto como puedas (o te atrevas).

Fecha de entrega

Hasta el jueves 23-11-2006.

Forma de entrega

Por correo electrónico a anto@gsyc.escet.urjc.es. El mensaje debe llevar como asunto IR P3 y contener:

Práctica 4: Base de referencia en Internet

En esta práctica vamos a asignar posiciones en un espacio euclideo de 3 dimensiones a 4 nodos en Internet, usando para ello el algoritmo distribuido más sencillo del sistema Vivaldi (presentado en la transparencia número 15 en clase).

Lo que tenéis que hacer es un programa que se llame coordinates y que va a tener predefinidos internamente los cuatro nodos a posicionar. Las posiciones iniciales de los mismos las podéis tomar, por ejemplo, como $(0,0,0)$, $(100,0,0)$, $(0,100,0)$ y $(0,0,100)$. Luego, realizará el siguiente procesamiento 20 veces. Vuestro programa obtendrá, para cada nodo, la latencia real entre ese nodo y cada uno de los demás. Según obtenga cada latencia la usará para modificar su propia posición según describe el algoritmo distribuido simple de Vivaldi (transparencia 15). Utilizad 1 como valor de $\delta$.

Podéis utilizar la siguiente estructura para vuestro programa:

repetir 20 veces
  para i=1 a 4 hacer
    para cada j distinto de i
      obtener latencia de i a j
      actualizar posición de i usando la latencia obtenida
    fin para
  fin para
fin repetir

Para actualizar la posición necesitáis calcular la distancia estimada entre el nodo $i$ y el $j$ y el vector de fuerza unitario entre ellos. Si las posiciones actuales son $(x_i, y_i, z_i)$ y $(x_j, y_j. z_j)$, la distancia es

\begin{displaymath}
d(i,j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2},\end{displaymath}

y el vector unitario se puede calcular como

\begin{displaymath}
u(i,j)=((x_i-x_j)/d(i,j), (y_i-y_j)/d(i,j), (z_i-z_j)/d(i,j)).\end{displaymath}

Con estos valores se puede calcular el error $e$ cometido como la diferencia entre la latencia real y la estimada (la distancia), y actualizar (cada coordenada de) la posición del nodo $i$ usando este error y el vector unitario. El programa debe mostrar cada vez que procese una latencia, el valor de la misma y la nueva posición del nodo tras procesarla.

Parte obligatoria

Podéis suponer que las latencias entre los nodos son fijas y simétricas (la misma en ambos sentidos). Los valores son, para cada par de nodos del 1 al 4: 40 ms de latencia del nodo 1 al 2, 50 ms del 1 al 3 y 30 ms del 1 al 4; 30 ms de latencia del nodo 2 al 3 y 50 ms del 2 al 4; 40 ms de latencia del nodo 3 al 4.

Parte optativa

Un problema que debéis resolver es el cálculo de latencias entre nodos distantes. Para ello debéis elegir como nodos distantes servidores públicos de ping o traceroute (que puede usarse en lugar de ping, man traceroute), con lo que podréis obtener las latencias entre ellos. Puedes encontrar muchos servidores en http://www.traceroute.org. Vuestro programa debe pedir al servidor remoto que sondee al otro nodo y extraer la información de latencia que devuelva. Debéis elegir nodos que estén en distintos países. Además es deseable que sus latencias sean significativas (más de 100 ms).

Fecha de entrega

Hasta el día del examen de teoría.

Forma de entrega

Por correo electrónico a anto@gsyc.escet.urjc.es. El mensaje debe llevar como asunto IR P4 y contener:

Práctica 5: Códigos de fuente digital

Para poder transmitir información a través de la red, muchas veces tenemos que tener en cuenta el hecho de que puede haber pérdidas, retrasos, duplicación de los paquetes... todos estos problemas se resuelven utilizando un protocolo como TCP para realizar la transmisión. Sin embargo, a pesar de que TCP es el protocolo más habitual, no es el único.

En esta práctica vamos a utilizar códigos de fuente digital para transmitir ficheros utilizando UDP. En LT.zip tenéis los ficheros fuente (solo en C, me temo; mirad la parte opcional para otros lenguajes) que vamos a usar. Tenéis que escribir dos programas, un emisor y un receptor.

El emisor generará bloques codificados de un fichero y se los enviará al receptor usando UDP. El receptor utilizará estos bloques para recuperar el fichero original.

Para ello, podéis usar como modelo los programas emisor.c y receptor.c que os damos. El primero sólo genera un bloque codificado y lo envía. El otro recibe hasta tener el fichero completo. Mirad el código fuente. Como veis, estos programas usan las funciones de codificación y decodificación que tenéis definidas en el fichero fbp.h. Estas funciones implementan la Transformada de Luby, como vimos en clase.

Programa emisor

El emisor deberá aceptar 6 parámetros en la línea de comandos:

Su misión es generar bloques codificados y enviarlos uno a uno como datagramas UDP independientes a la máquina y puerto UDP especificados. Enviará hasta que el receptor le envíe un mensaje indicando que ha recibido el fichero completo.

Dado que UDP no está orientado a conexión, y que los bloques codificados son independientes entre sí, podrán ejecutarse varios emisores en paralelo que envíen al mismo receptor (siempre que el fichero a enviar y el tamaño de bloque sea el mismo). Abajo vemos cómo podemos hacer que un único receptor pueda confirmar el fichero a varios emisores.

Programa receptor

El receptor deberá aceptar 2 parámetros en la línea de comandos:

El programa receptor escuchará en el puerto especificado, irá recibiendo datagramas y se los pasará al decodificador. Cuando el decodificador termine, deberá mostrar por pantalla una línea que indique la eficiencia de recepción (el cociente entre el número de bloques del fichero original y el número de bloques codificados que han sido necesarios para recuperarlo).

Además, debe enviar un mensaje a cada emisor indicando que ha recibido el fichero completo. Para ello una forma sencilla es, una vez recibido el fichero completo, esperar unos segundos (por ejemplo un minuto) antes de finalizar, y responder a cada nuevo mensaje recibido de un emisor con un mensaje indicando que el fichero se ha recibido completamente. Esta no es la única forma, y sois libres de usar otra, siempre que funcione y me la describáis al entregar la práctica.

Por ejemplo, si estamos transmitiendo el fichero /usr/share/misc/pci.ids, con un tamaño de bloque de 500 bytes, tendremos que hacerlo así:

emisor /usr/share/misc/pci.ids 500 0.1 0.3 localhost 5000

Si este fichero ocupa 291359 bytes, tendrá un total de 583 bloques. Si el decodificador necesita 666 para recuperar el fichero original, el receptor deberá mostrar por pantalla:

receptor /tmp/file 5000
Fichero recibido correctamente. Eficiencia de recepción: 0.88

Parte obligatoria

Con los dos programas que debéis escribir, tenéis que realizar pruebas con distintos ficheros, parámetros c y delta. El significado de estos parámetros podéis verlo en aquí.

Utilizad ficheros (os sugiero al menos 4) de tamaño grande (al menos 1 Mb), y 5 tamaños de bloque distintos (por ejemplo, desde 100 hasta 10000). Para cada caso, usad los valores más eficientes de delta y c, que podáis encontrar en c-delta-table.txt (la redundancia media que hay que añadir se da en la columna mean(E), para cada combinación de número de bloques, delta y c). Probad cada caso con 1 y dos emisores. Luego haced una tabla con los distintos casos, dando la eficiencia observada.

Para realizar las pruebas, debéis utilizar como directorio de destino uno que esté en un directorio local a la máquina (por ejemplo, /tmp), para evitar latencias debidas al NFS.

Parte opcional

Sólo se suministra las funciones de codificación y decodificación en C. Como parte opcional podéis hacer recubrimientros de estas funciones en otros lenguajes (Java, Ada, etc.). Si queréis, la parte obligatoria la podéis hacer en el lenguaje correspondiente, una vez el recubrimiento funcione.

Fecha de entrega

Hasta el jueves 11-1-2007.

Forma de entrega

Por correo electrónico a anto@gsyc.escet.urjc.es. El mensaje debe llevar como asunto IR P5 y contener:

Sobre este documento...

Prácticas de Infraestructuras de Redes / Redes entre Pares

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -no_navigation -split 0 index

The translation was initiated by Antonio Fernandez on 2007-01-10


Antonio Fernandez 2007-01-10