Redes entre Pares

Grupo de Sistemas y Comunicaciones

Universidad Rey Juan Carlos

Curso 2007-08

[ Calendario de clases | 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: Caminos de distancia mínima

Un problema clásico en redes es la búsqueda del camino de distancia (o coste) mínima entre dos nodos de una red. En esta primera práctica se os pida que resolváis este problema en una red dada por sus nodos y enlaces.

El enunciado lo tenéis como Problem C: Plagiarism! en la siguiente dirección: http://appsrv.cse.cuhk.edu.hk/~ acmprog/web2006/contest/contest2006/Problem2006.pdf.

Aparte de la prueba de ejemplo que aparece en ese enunciado, debéis hacer al menos dos pruebas más, cada una de al menos 20 nodos.

Fecha de entrega

Hasta el jueves 25-10-2007. El valor de esta práctica es de 1 semana.

Forma de entrega

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

El mensaje debe llevar como asunto P2P P1 y contener:

Práctica 2: Sonda

En esta práctica queremos estudiar si es posible estimar la latencia, el ancho de banda y la tasa de pérdidas entre dos equipos en Internet. Para ello haremos un programa que hace pings ICMP, y permite estimar estos valores (latencia, ancho de banda y tasa de pérdidas) 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 (mirad la página de manual, man ping), que luego usará para evaluar latencia, ancho de banda y tasa de pérdidas. Usad el tamaño de paquete mínimo (idealmente 0, pero al no ser esto posible, usad el menor disponible; mirad la página de manual, man ping) 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). Puede que algunas máquinas no se puedan usar para esta práctica.

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}

Finalmente, el programa debe calcular el número $p$ de pings que se han perdido (de los 40 enviados), y con ello calcular la tasa de pérdidas (en porcentaje) como

\begin{displaymath}p*100/40.\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.es
Latencia: 
0.89 ms
Ancho de banda:
1568 Kbps
Tasa de pérdidas
0

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.

Esta práctica es una clara candidata a ser realizada en alguno de los lenguajes de script de Unix o Linux. Mirad en este enlace un libro y "chuletas" para programar en estos lenguajes.

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 8-11-2006. El valor de esta práctica es de 2 semanas.

Forma de entrega

Por correo electrónico a anto@gsyc.es. El mensaje debe llevar como asunto 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). Lo que os sugerimos es que hagáis un script que invoque a clientes (no interactivos) disponibles1. 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 cómo 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 podáis usar, podéis 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. Para elegir proxy que esté bien situado como nodo intermedio, buscad las rutas más eficientes en http://www.akamai.com/html/technology/dataviz2.html.

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 29-11-2007. El valor de esta práctica es de 2 semanas.

Forma de entrega

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

Práctica 4: Posicionamiento en Internet

En esta práctica vamos a combinar Vivaldi con el mecanismo de "gossipping" para asignar posiciones en un espacio euclideo de 3 dimensiones a nodos en Internet. Para ello vamos a simular el algoritmo distribuido completo del sistema Vivaldi (presentado en la transparencia número 16 en clase), donde los sondeos de hacen de forma aleatoria uniforme enter todos los nodos del sistema.

Lo que tenéis que hacer es un programa que se llame position y que va a leer de la entrada estándar los datos de la red y de la simulación. Los datos de la red que se leerán son:

De la simulación lo que se va a leer es el número de rondas $r$ a simular.

Inicialmente todos los nodos tendrán una posición $p_i=(x_i,y_i,z_i)$ aleatoria, donde cada uno de los valores $x_i$, $y_i$ y $z_i$ es un valor aleatorio entre 0 y 100, y como error estimado $e_i=1$. Los parámetros del algoritmo de Vivaldi a usar son $c_c=0,25$ y $c_e=0,3$.

La simulación a implementar va a consistir de $r$ rondas. En cada ronda, cada nodo $i$ de la red va a elegir otro nodo $j$ aleatoriamente con probabilidad uniforme, va a obtener el RTT real $L_{ij}$ con ese nodo, y la posición $x_j$ y el error estimado $e_j$ del mismo (en una implementación real estos datos se obtendrían sondeando al propio nodo, en la versión simulada basta con acceder a las variables del programa). Con estos datos y sus propios datos $x_i$ y $e_i$, el nodo $i$ calcula su nueva posición y su nuevo error estimado. Además mostrará por la salida estándar el proceso realizado con una línea como la siguiente: 

Ronda 7, nodo 5 sondea al nodo 10, nueva posicion (0.45, 12.34, 8.00) error 0.89
Al final de cada ronda se debe calcular el error cuadrático del conjunto de posiciones como se describe en la transparencia 5.

Podéis utilizar la siguiente estructura para vuestro programa: 

repetir r veces
   para i=1 a n hacer
     elegir nodo j aleatoriamente
     obtener RTT, posición y error de j
     actualizar posición de i
     imprimir nueva posición
   fin para
   imprimir error cuadrático
fin repetir

Parte obligatoria

La entrada de vuestro programa vendrá dada de la siguiente forma:

Debéis hacer al menos 3 pruebas de vuestro programa. Una de ellas debe ser de al menos 20 nodos. Tenéis que entregar la entrada y la salida de cada prueba.

Una posible prueba puede ser la siguiente, que representa la simulación de 20 rondas en una red de 4 nodos emplazados en los vértices de un rectángulo de lados de longitud 3 y 4. 

20 4
4.0 3.0 5.0
5.0 3.0
4.0

Parte optativa

Como parte optativa podéis hacer que cada nodo $i$ elija el nodo $j$ de entre una muestra de todos los nodos de la red, muestra que se irá actualizando según una versión del algoritmo Newscast que se describió en clase.

El proceso sería el siguiente. La primera línea de la entrada tendrá un tercer número $w$, que es el tamaño de la muestra a mantener en cada nodo. Cada nodo tendrá continuamente una muestra de todos los nodos de la red, y para cada nodo de la muestra la ronda en que se generó la entrada correspondiente.

En la simulación cada nodo llena su muestra inicialmente con $w$ nodos elegidos con probabilidad uniforme de entre toda la red, todos ellos con número de ronda 0. Luego, en cada ronda, el nodo $i$ elige un nodo $j$ al azar de su muestra, intercambia con él posición, error, y la muestra actual completada con la identidad de $i$ y la ronda actual ($j$ hace algo similar), y finalmente trunca la unión de las dos muestras (la propia y la obtenida de $j$) al tamaño $w$ despreciando las entradas más antiguas.

Haz al menos 3 pruebas del nuevo programa. Una de ellas debe ser de al menos 20 nodos. Tenéis que entregar la entrada y la salida de cada prueba.

Una posible prueba puede ser la siguiente, que es la simulación anterior con un tamaño de muestra de 2. 

20 4 2
4.0 3.0 5.0
5.0 3.0
4.0

Fecha de entrega

Hasta el jueves 10-1-2008. El valor de esta práctica es de 4 semanas.

Forma de entrega

Por correo electrónico a anto@gsyc.es. El mensaje debe llevar como asunto P2P 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 (sólo en C; 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 2) 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

Hemos realizado una implementación en Java de la transformada de Luby y una interfaz similar a los sockets. No está completamente estable y requiere leer algo de documentación para entender cómo usarla. Quien quiera hacer la práctica con esta implementación en lugar de la implementación en C, que me contacte.

Fecha de entrega

Hasta el día posterior al del examen final. El valor de esta práctica es 3 semanas.

Podéis entregar la práctica hasta el día 30 de enero inclusive. Los que la hayáis entregad yo podéis mejorarla y entregarla de nuevo. Se tendrá en cuenta el haber entregado la práctica en el plazo inicial establecido en la calificación de la misma.

Forma de entrega

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

Sobre este documento...

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 2008-01-23

Notas al pie

... disponibles1
Documentación sobre scripts en Unix: Mirad en este enlace un libro y "chuletas" para programar en estos lenguajes.

Antonio Fernandez 2008-01-23