martes, 15 de junio de 2010

Green Networking

Hace un par de semanas participé en el workshop Energy Efficiency and Networking organizado por el IMDEA Networks, donde varios (brillantes) investigadores presentaron sus trabajos/ideas sobre el presente y futuro del tan cacareado "Green Networking". La verdad es que este tema es interesantísimo y dará mucho "juego" a los investigadores, aunque me queda la duda del impacto real que puedan tener estas propuestas a la hora de rebajar las emisiones de CO2.

Una cifra demoledora que se comentó en el workshop, es que hoy en día el gasto energético de las TIC (Tecnologías de la Información y Comunicaciones) es comparable con el del sector aeronáutico, y las estimaciones es que siga subiendo. Como era de suponer, el gran "vampiro eléctrico" son las granjas de servidores que representan casi la mitad de ese gasto (las cifras bailan un poco, dependiendo de la fuente). Las redes de transmisión tampoco se quedan atrás, representando sobre un 26% del gasto total de las TIC (otra vez, depende de la fuente). Por ejemplo, un dato que da mucho que pensar es el del consumo de las redes Ethernet, en donde este crece de forma exponencial según aumentamos el rate de la tarjeta... y todo esto en modo idle, es decir, ¡¡¡sin enviar ni recibir, sólo por estar activa!!!.

Para mitigar el problema de consumo de Ethernet, por ejemplo, ECMA International ha publicado un estándar conocido como proxZzzy (chulo el nombre) en donde sitúan un proxy en medio de uno o varios equipos y el resto de Internet. Cuando un equipo detecta un estado idle, se lo comunica al proxy y se va a "dormir" (modo de bajo consumo). El proxy detectará paquetes destinados al "PC durmiente" y lo despertará si es necesario.

Algunos son pesimistas. Se dice que la reducción del consumo energético será marginal y cara, por lo que muchos fabricantes y/o proveedores de servicio no los adoptarán. De todos modos, esto es algo que aún está comenzando y hay mucho campo para seguir investigando. Yo por mi parte, ya he puesto un par de PFCs sobre el tema, a ver si contribuímos a pintar de verde nuestras redes :-)


lunes, 7 de junio de 2010

P2P video caching

Han pasado más de dos años desde mi última entrada, así que ahora me dedicaré a escribir entradas cortas, para intentar escribir más cosas que se me ocurren.

Ahora mismo estamos trabajando en P2P video caching (PVC). ¿Cuál es la idea detrás del PVC? Bueno, es algo parecido a tener un cliente estilo BitTorrent para YouTube. Sería algo así como tener los contenidos (vídeos) en los propios equipos de los usuarios una vez se los descargan.

Algunos dirán que esto es precisamente lo que hace BitTorrent. Sí, pero con una pequeña diferencia. En BitTorrent el usuario decide mover, borrar o copiar el fichero, mientras que en PVC el usuario "reserva" espacio en su disco para hacer cache (guardar y reemplazar) de los videos que baja, pero que él en principio no volverá a ver (y si quiere volver a verlos, sólo tiene que acceder a su cache).

Existen varios problemas a los que nos estamos enfrentando. El primero de ellos, y el más gordo, es cómo poder simular el comportamiento de usuarios para elegir, descargar y visualizar los videos. Es decir, simular el acceso en YouTube. Actualmente tenemos un crawler de YouTube, que obtiene los vídeos más recientes cada 15 minutos y luego, también con 15 minutos de intervalo, se dedica a capturar el número de vistas totales de cada uno de los vídeos que tenemos almacenados. Esto lo estamos haciendo con la API de YouTube que nos está dando varios problemas, ya que devuelve varios errores (no los culpo, ahora mismo llevamos una semana y unos 30,000 vídeos).

Una vez tengamos datos realistas de YouTube, lo siguiente será diseñar una arquitectura que funcione bien de forma descentralizada. Tenemos que contestar las siguientes dudas:
  • ¿Qué pasa si el usuario tiene la cache llena? Tendremos que borrar ficheros antiguos, pero igual los antiguos son muy populares.
  • ¿Es bueno guardar el fichero que estamos bajando? A lo mejor varios usuarios ya tienen ese vídeo.
  • ¿Cómo localizamos el contenido? ¿Bootstrap server? ¿Método gossip (inundación)?
  • ¿Cómo afecta el churn (entradas y salidas de usuarios al sistema)? Un usuario que sale del sistema "se lleva" su cache. ¿Y si las copias que dicho usuario tenía eran las únicas en el sistema?
  • ¿Qué pasa cuando un contenido se vuelve popular/impopular? ¿Existen suficientes/demasiadas copias en el sistema?
Queda mucho por hacer, pero ya iré poniendo resultados de esta investigación.

lunes, 5 de mayo de 2008

Televisión y vídeo en Internet (con redes P2P)

¿Quién podía imaginar hace 30 años que la televisión se podría transmitir por Internet?. Bueno... difícil... porque pocos sabían lo que era Internet, pero incluso las transmisiones digitales de TV eran casi imposibles de pensar. Hoy en día es posible "ver" canales de TV por Internet. Existen varias cadenas que incluso ponen vídeos sueltos en sus páginas para que los usuarios los puedan ver.

Recordemos lo que nos dice IP: "yo presto un servicio best-effort... haré lo posible por llevar tus datos desde A hasta B, pero no te aseguro nada". En concreto, no asegura que los datos, si llegan, lleguen en un cierto tiempo (quiero que lleguen en 5 segundos como máximo). Y esto es un gran problema en la TV o streaming de video como se llama de forma más pomposa.

Otro gran problema de IP es que, aunque existen los mecanismos, multicast no funciona en la realidad ya que los ISPs (Proveedores de Acceso a Internet) filtran ese tráfico. Recordemos que multicast es buenísmo para TV: el que envía el vídeo sólo debe generar una copia, independientemente del número de clientes que quieran recibir ese vídeo. Hoy en día, si 10 clientes quieren ver un canal, el que envía el vídeo debe enviar 10 copias del mismo vídeo (con lo que eso conlleva con respecto al "ancho de banda" necesario en el lado del servidor de vídeo).

Este último problema se puede resolver con técnicas de Peer-to-Peer (P2P) realizando ese multicast (no exactamente lo mismo) en la propia aplicación. En este caso, existen varias técnicas para crear lo que se conoce como ALM (Application-Level Multicast):
  • Push-tree: en este caso se creará un árbol multicast a nivel de aplicación. Es decir, tendremos un equipo que será la raíz del árbol y diferentes nodos en el siguiente nivel. De ese nivel bajaremos a equipos que estarán a otro nivel, hasta llegar a las "hojas" de dicho árbol, donde se terminará la transmisión. Se dice que es "push" porque un nodo en el árbol sabe a qué otros nodos debe enviar copias de lo que ha recibido (a sus hijos).
  • Pull-mesh: este es el método más utilizado por las aplicaciones actuales (SopCast, PeerCast, Ants, etc.) para transmitir vídeo en tiempo real con P2P. En este caso no tenemos un árbol sino una topología desestructurada (tampoco es una red mallada totalmente). La idea es que cada nodo tendrá "conocimiento" de otros nodos a los que les irá pidiendo (pull) datos. Otros nodos harán lo mismo con este primero.

Aunque pull-mesh sea el más utilizado, lo que nos gusta a nosotros los "investigadores" es bailar con la más fea. ¿Cómo mejorar el rendimiento del push-tree?. Bueno, existen un montón de artículos explicando cómo construir un árbol de la forma más eficiente, pero como ya hay un montón de gente haciendo esto, vamos a por algo más complicado.

Imaginemos que en el árbol que vemos en la figura de arriba, el nodo 0 decide irse a dormir. Ya digo que existen un montón de algoritmos para re-hacer el árbol, pero aún así, esto llevará su tiempo, con lo cual tendremos a un montón de nodos con sus pantallas en negro durante un cierto período.

Existe un método de codificación de vídeo bastante en moda en la parte de investigación que se llama MDC (Multi-Description Coding). La idea es bastante sencilla: divido un vídeo en varias partes (no a lo largo del tiempo, sino en el mismo instante). Un ejemplo fácil (recordemos que un vídeo no es más que una secuencia de imágenes): cojo una imagen y la divido en dos partes -los píxeles impares por un lado y los pares por otro-. Fijémosnos en que las dos partes tienen menos calidad que la original, pero si tenemos ambas y las unimos, tendremos la calidad original. Pues ahora imaginemos que tenemos dos ficheros: video-par.mp4 y video-impar.mp4. Si enviamos ambos streams, utilizando caminos diferentes, un receptor podría ver el vídeo a una calidad "baja" si recibe uno de los dos streams, pero a una calidad total si recibe los dos. En este caso, la probabilidad de tener la pantalla en negro es la prob. de que ninguno de los dos streams llegue.

Pues juntando las ideas de Push-tree y MDC sale la idea de múltiples árboles. Cada nodo formará parte de tantos árboles como partes tenga el vídeo (en el ejemplo anterior, dos árboles). Imaginemos que el árbol de la figura anterior es el que distribuye el video-par.mp4. En ese caso vemos que el nodo 7 es hijo del 4. En el otro árbol, el que distribuye el video-impar.mp4, podríamos tener una distribución diferente, y por ejemplo el nodo 7 ser hijo del 1 directamente.

Hay un montón de cosas que tenemos que tener en cuenta. Por ejemplo, los nodos "hoja" son los más felices del mundo: reciben tráfico sin tener que enviárselo a nadie. Bueno, pues podemos hacer un algoritmo en el que si un nodo es hoja en un árbol, tenga que ser un nodo "padre" en otro árbol (ver Splitstream).

jueves, 27 de marzo de 2008

Redes Peer-to-Peer

¡Las vueltas que da la vida! Uno comienza trabajando en Bluetooth mucho antes que lo metiesen en todos los teléfonos móviles y acaba trabajando en redes peer-to-peer (p2p) cuando es algo más viejo que Matusalem.

La verdad es que siempre me interesó saber cómo demonios iba tan rápido el BitTorrent. Bajarse cosas con el torrent (legales, por supuesto) es cosa de la velocidad de línea que tengas (nota mental: hablar de velocidad de línea, que mis alumnos me lo agradecerán).

Pero no hay nada perfecto. Con sistemas estilo eMule (red edonkey), uno tiene una sección de búsqueda y luego sólo hay que darle al botón de descargar, cuando encontramos lo que queremos. Sin embargo, en otros clientes nos encontramos con otros problemas a la hora de descargar contenido. Esto es así de complicado, ya que utilizan lo que se llama la DHT (Distributed Hash Table). Vayamos desmenuzando cada una de estas palabras.

Hash. No es más que un valor generado a partir de otro utilizando una función. Por ejemplo: hash = funcion (dirección IP). La función puede ser cualquiera (buena, claro) como por ejemplo las SHA que son muy utilizadas. La SHA1 genera un hash de 160 bits, independientemente del argumento que se le ponga (si metemos una dirección IPv4 nos dará un hash de 160 bits, y si metemos una dirección IPv6 nos dará otro hash, pero también de 160 bits). Lo importante de todo esto, es que podemos identificar cosas diferentes, utilizando la misma notación (si tengo un fichero de vídeo y le calculo su SHA1, me dará un identificador de 160 bits, y si tengo un fichero de audio, su hash será otro identificador de 160 bits). Estas funciones no son elegidas al azar, ya que deben cumplir muchas cosas. Una de ellas es la siguiente: dados dos valores a y b, los hashes generados f(a) y f(b) serán distintos. Lógicamente, hay una pequeña probabilidad que esto no ocurra, pero esto ya depende de lo bueno que sea el método. A quien le interese, hay un problema estadística muy interesante, en donde se trata de buscar la probabilidad de que, dado un conjunto de personas en una sala, dos personas tengan la misma fecha de nacimiento (Birthday Paradox).

Table. En este caso, se generarán identificadores (hashes) para cada nodo de la red peer-to-peer, pero también para los objetos que se estén compartiendo (cada fichero que se comparta, tendrá su correspondiente identificador o hash). La tabla en este caso, es una lista, almacenada en cada nodo, de los diferentes identificadores que ese nodo sabe (no tenemos porqué saber todos los identificadores de la red p2p, pero sí una visión parcial de la misma).

Distributed. Más o menos ya lo he explicado en el párrafo anterior. Los identificadores de la red p2p estarán distribuidos entre todos los nodos que la forman.

Por ejemplo. En la red Kademlia (más o menos famosa, porque eMule soporta esta red), cada nodo (ordenador, equipo) tendrá un identificador de 160 bits (como se ha comentado anteriormente, la probabilidad de que dos equipos tengan el mismo identificador, es muy baja). Podemos representar a cada equipo en un círculo, como en la siguiente figura. A cada objeto (fichero de vídeo, imagen, audio, etc.) que cada equipo comparta, tendrá también un identificador de la misma longitud.

Imaginemos que arranco mi Kademlia (nodo A) y me dan un identificador A0B1A (está en hexadecimal) y tengo dos ficheros que quiero compartir (00000 y CCCCC). Uno de los primeros pasos es detectar a otros equipos que ya formen parte de la red p2p y almacenaré sus identificadores y sus correspondientes direcciones IP y puertos en mi tabla DHT (esto es más complicado, pero para nosotros nos sobra). Imaginemos que sólo consigo un equipo (nodo B) en esa tabla y tiene como identificador CCCC0 y dirección IP 163.117.139.X.

El paso más importante es el de distribuir mi información local en la red P2P. Para ello, enviaré un mensaje a la red por cada objeto que quiera compartir (en nuestro ejemplo, dos). La idea clave de todo es lo siguiente: cada nodo de la red P2P, almacenará un localizador para aquellos objetos cuyo identificador esté muy próximo al propio identificador del nodo. Por ejemplo, cuando nuestro nodo arranca, querrá informar a la red que él tiene los objetos cuyos identificadores son el 00000 y el CCCCC. Comencemos por el último.

Como el nodo en cuestión sólo tiene un punto de contacto en la red (CCCC0), le mandaremos un mensaje diciéndole que tenemos un objeto cuyo identificador es el CCCCC. Si este nodo, no tiene constancia de que exista otro nodo en la red, con un idenficador más parecido, él se encargará de mantener el localizador de este objeto (CCCCC -objectID- y CCCC0 -nodeID- se parecen mucho). Por lo tanto, el nodo B almacenará un localizador diciendo: si alguien me pregunta por el localizador CCCCC, yo le responderé que es el nodo A (guardo también su IP y puerto) quien lo tiene. Fijaros que pueden haber más equipos que tengan ese objeto. Pues el nodo B tendrá varios localizadores para el mismo objeto.

En la figura podéis ver un ejemplo de qué pasaría si el nodo 3D8C7810 quiere localizar el objeto D78AE154. Buscaría en su tabla DHT y el nodoID más parecido sería el D0017854. Le enviaremos un mensaje a ese que a su vez buscará en su tabla, encontrando que el más parecido al objeto buscado es el D785DD10. Este haría lo mismo hasta que encontramos un nodo (D78AE135) que es el más cercano de toda la red a dicho objeto y que, por lo tanto, debería tener el localizador para dicho objeto.