jueves, 28 de febrero de 2013

AGREP (Aproximate GREP) Performance Analysis

For extra points, I took the task of testing AGREP with different length texts (T) searching for a certain pattern (P).

For this I used the same function that generates a certain length T, and then searched for a pattern in there. Initially this was very random, because with lengths of 100-1000 or so, the time variation was pretty much random depending on how busy the CPU was. This way a word with length 100 could had been searched slower than a word with length 1000.

To fix this, the T samples were generated from 1000 to 100000 characters each. Also, because 1 character or 20 of difference still doesn't make a difference, the samples are generated jumping 100 characters one T to the next. So, we generate T's with 1000, 1100, 1200, 1300, etc. length.

This way we can plot the T's length along with the time it took to search for P in there. The result of plotting that data is:

As we can see with a 80, 000 character T, the times are still pretty good, aproximating 0.06 seconds in the search of a pattern.

Now, comparing with the Knutt-Morris-Pratt and the Boyer Moore algorithms:



KMP behaves the worst of the three, with BM placing second.

In conclusion, AGREP is a pretty good string searching tool, which has great computing times, compared to my other implemented string searching algorithms.

Code used to generate the computing times:



Code used to graph the data (adjusting sizes and stuff for each algorithm):



miércoles, 27 de febrero de 2013

Laboratorio 4: Detección de Diagonales, Ángulos Arbitrarios y Segmentos Continuos de Líneas

Link al repositorio: https://github.com/synnick/viscomp

En la materia ya se trabajó con la detección de líneas, pero particularmente en líneas horizontales y verticales (de 180° y 90° respectivamente). Ahora, lo siguiente es trabajar con líneas de 45° (diagonales "perfectas") y ángulos arbitrarios, es decir, cualquier otro ángulo que no forme los antes mencionados.

Esto en teoría ya debería de haber sido posible desde el programa de la materia, pero debido a que calculaba solamente los ángulos de 90 y 180° usando los valores de los gradientes, se omitía cualquier otro ángulo real que pudiera tener un cierto pixel.

Para cambiar esto ahora se utiliza de nuevo (pero como prioridad) la función $arctan$ para calcular el ángulo de cada pixel. Inicialmente con cualquier variación en los valores de los gradientes estos ángulos variaban mucho, existiendo muchos diferentes ángulos que aunque fueran cercanos o similares, no se habrían podido agrupar para obtener el histograma de los $(\rho, \theta)$.

Para arreglar esto, los ángulos se agrupan en un determinado rango a partir de su proximidad. Por ejemplo, si se calcula un ángulo de 83° para un determinado pixel, y definimos rangos de 10 en 10° para agrupar los similares, ese ángulo de 83° se convertiría en uno de 80°, por estar más cerca al 80 que al 90.

Cada ángulo diferente de los nuevos, se pinta después de un nuevo color.


Identificación de segmentos continuos de líneas


Para poder identificar líneas continuas hago uso de BFS utilizado en posts anteriores, para poder pintar los vecinos de una línea determinada de un color.

Para poder hacerlo primero guardo todos los pixeles en los cuales se localizó alguna línea, y los pinto blancos en una imagen de salida, como la siguiente:



Con esta imagen, se buscan las líneas continuas con BFS, y se pintan de colores diferentes. El resultado: 


Algunas líneas se detectaron de forma excelente,sobre todo las verticales, otras contienen mucho ruido, por lo cual aparecen pixeles de múltiples colores en la vecinidad.

Código:

martes, 26 de febrero de 2013

Resumen: Modeling Mobility for Vehicular Ad Hoc Networks

Modeling Mobility for Vehicular Ad Hoc Networks

Amit Kumar Saha, Deparment of Computer Science

David B. Johnson, Deparment of Computer Science

La idea del modelo de movilidad descrito en el paper es hacer fácil el análisis de simulaciones realistas sobre movilidad, y desempeño de redes móviles ad hoc. 

Durante la década pasada, se ha hecho un gran progreso en los métodos para proporcionar conectividad de redes para usuarios de móviles. Entre tecnologías notables estan las redes basadas en infraestructuras y más recientemente redes móviles ad hoc. Ejemplos de redes basadas en infraestructuras incluyen redes de celulares e IEEE 802.11 (WiFi). El problema con estas redes es que dependen en la existencia de infraestructuras (puntos de acceso y estaciones base). Las redes móviles ad hoc, por otro lado, no requieren de tal infraestructura y por lo tanto prometen ser más fácil de colocar y más flexibles que las redes basadas en infraestructuras.

Una red ad hoc emergente es una red ad hoc-vehicular, en la cual los vehículos constituyen nodos móviles en la red. Como resultado, ciertas preocupaciones tradicionales con los nodos móviles como eficiencia de energía, ya no son de gran importancia. 

Las redes ad hoc-vehiculares deberían permitir que existan aplicaciones que mejoran la seguridad y conforte de pasajeros dentro de vehículos, posiblemente en ese orden de importancia. Las investigaciones en el área de redes ad hoc móviles han dado un gran progreso hacia el hacer tales redes más prácticas así que puedan ser lanzadas en aplicaciones reales.

Aúnque las instalaciones en el mundo real son mucho más esenciales para entender la efectividad y desempeño de una red ad-hoc, la simulación provee algunas ventajas sobre el despliegue actual de la red. Particularmente , las simulaciones son rápidas y repetibles y es posible con simulaciones aislar parámetros que afectan el desempeño del diseño. El aislamiento de parámetros es esencial para entender el efecto de cada parámetro en el diseño. También las simulaciones permiten probar un diseño en una gran variedad de escenarios y valores de parámetros, lo que es difícil o imposible en los despliegues reales.

Algunas de las más importantes propiedades de una población de usuarios móvil, son las características y patrones de la movilidad de los usuarios. En la simulación de sistemas móviles, es importante usar un modelo de movilidad realista, así que los resultados de la evaluación a partir de la simulación reflejen correctamente el desempeño en el mundo real del sistema. Sin embargo, la mayoría de los modelos de movilidad usados en las herramientas actuales de simulación como ns-2 no son realistas. 

El paper propone un modelo de movilidad realista basado en tráfico vehicular, útil para evaluar redes ad hoc vehiculares.

Generación del Mapa de Modelo para la simulación

Para el modelado del mapa, la US. Census Bureau tiene disponible un mapa detallado de calles para todos los Estados Unidos. Estos mapas, contienen información geográfica y cartográfica selecta, y están disponibles gratuitamente para el público.

Para cada segmento de camino en un mapa, se extraen las coordenadas de fin e inicio del camino y se convierten en coordenadas x, y. Después se representa internamente el conjunto de caminos en un grafo en cual las intersecciones entre caminos son representadas por nodos.

Una región de ejemplo que aparece en el paper, es la siguiente:

Región A: 2400m x 2400m

Protocolo DSR

Se utiliza un protocolo de ruteo de origen, es decir, cada paquete enviado usando DSR conteniendo una ruta origen. El protocolo DSR consiste en dos mecanismos: Descubrimiento de rutas y Mantenimiento de rutas. Para realizar un descubrimiento de ruta para un destino D, un nodo origen S realiza un broadcast con un ROUTE REQUEST que se satura por la red de una forma controlada. Esta solicitud es contestada por un ROUTE REPLY por cualquiera, ya sea D o algún otro nodo que conoce una ruta a D. Para reducir la frecuencia y propagación de un ROUTE REQUEST cada nodo agresivamente atrapa las rutas origen que el nodo aprende o escucha. El mantenimiento de ruta detecta cuando algún link por el cual se transmite algún paquete de datos se rompe. Cuando tal ruptura existe, un ROUTE ERROR es enviado  S. Al recibirlo, S puede usar cualquier otra ruta a D que esté en su cache de rutas, o S puede iniciar una nueva Route Discovery hacia D.

Se evalúa el desempeño del protocolo DSR en los escenarios que corresponden a la Región A descrita anteriormente, usando el simulador de redes ns-2 versión 2.1b8a, con extensiones de movilidad del proyecto Monarch.

Esta versión modela la capa física y la capa Mac que incluye el modelado de colisiones, captura, propagación y demás. La interfaz red es modelada usando la Lucent/Agere WaveLAN/ORiNOCO IEEE 802.11, la cual tiene una transmisión nominal en un rango de 250m y una tasa de datos de 2 Mbps.

Se simularon 150 nodos en la red con un rango de transmisión de 500 m. Se evaluó el desempeño del DSR siguiendo los siguientes parámetros:
  • Tasa de Entrega de Paquetes: La fracción de los paquetes de datos originales enviados por la capa de aplicación en el origen que son exitosamente enviados a la capa de aplicación del destino deseado.
  • Latencia de Entrega de Paquetes: El promedio de las latencias para los paquetes de datos exitosamente enviados desde el origen hasta el destino. Esta métrica solo tiene sentido para paquetes enviados exitosamente.
  • Gasto general de paquetes: El número total de gasto general de paquetes, no contando los paquetes de datos, que son enviados por el protocolo de ruteo. 
Un ejemplo de simulaciones hechas para la región anterior:


Escenarios de conectividad que corresponden a la Región A mostrada anteriormente, con un rango de transmisión de 250m.

Conclusión: 

El paper habla sobre un nuevo modelo propuesto acerca de redes ad hoc móviles, y el uso del simulador de redes NS-2 para modelar la capa física  y la capa MAC, y con ello simular colisiones, capturas y otros eventos de redes. También hace una mención a la importancia de realizar estas simulaciones por motivos de la rápidez y capacidad de repetirlas.

Referencias:

Sugerencias a Proyectos

A continuación escribiré sobre recomendaciones a los proyectos de mis compañeros, en base a lo que han descrito de sus funcionalidades hasta el momento.

Alarma Inteligente para Auto
Blog: http://ubicomputo.blogspot.mx/

Una idea interesante sería conectar de alguna forma la alarma a un dispositivo que a su vez estuviera conectado a Internet. De esta forma cuando la alarma sea activada, se podría enviar alguna notificación por correo, o a una aplicación propia el momento exacto en el que la alarma se active.

Esto serviría por ejemplo cuando el auto esta estacionado cerca de casa o trabajo, donde se tiene acceso a una red a la cual se puede conectar. Si alguien intentara robar el automóvil, o simplemente se activara la alarma por error y el dueño recibiría una notificación y podría reaccionar en el momento en el que ocurrió.

Alarma Inteligente (Para despertarse)
Blog: http://3-its.blogspot.mx/

Una idea que se tenía en un proyecto previo donde queríamos hacer una alarma interactiva, era el poner algún juego mental o quiz para poder desactivar la alarma. Esto ayudaría a la persona a por lo menos tener que pensar y despertar un poco más, evitando simplemente presionar un botón para cancelarla.

Casa Inteligente (Seguridad)
Blog: http://3puntosteam.blogspot.mx/

Una recomendación para éste proyecto es definir un alcance. Es sobre seguridad en una casa, por lo cual asegurar puertas y ventanas cubre una parte importante, pero también es un problema el hecho que las personas ya entren, es decir deberían considerar también algún sistema de alarmas o seguridad. La parte del apagado automático de luces y demás es interesante, pero no me parece tanto relacionado con el tema de seguridad.

En si, me parece que deben definir en que se van a concentrar, seguridad en la casa inteligente, o comodidad y automatización.

Galería Inteligente
Blog: http://ultimo-sem.blogspot.mx/search/label/Computo%20Ubicuo

Con NFC se podrían hacer cosas interesantes en por ejemplo un museo. Dispositivos cercanos con una cierta aplicación podrían recibir información e imagenes que tengan que ver con la pintura, escultura o dinosaurios que estén observando. Combinando sensores de moviendo se sabría cuando alguien esta observando una determinada pieza del museo.

Oficina Personalizada, Carro NXP, Garage Inteligente (Nosotros mismos)

Oficina: http://pepgonzalez.blogspot.mx/2013/02/campos-de-estudio-oficina-personalizada.html#comment-form
Carro NXP: http://inteligentsystems.wordpress.com/

Una cosa que pensé mientras leía las descripciones de los primeros dos proyectos (muy buenos por cierto) es que al igual que nosotros tendrían alguna llave electrónica (en nuestro caso el smartphone).

En caso de ser robada (asumiendo que es robada por el hecho de saber que es una llave electrónica para el auto, oficina, garage) se debería considerar algún sistema de seguridad para poder bloquear la llave electrónica y que no se pueda abrir más con ese dispositivo.

Es algo complicado pensar en ello, porque tendría que estar conectado de alguna manera el automóvil a alguna red para poder comprobar si la llave aun es válida, pero igual que la recomendación a la alarma inteligente, podría simplemente estar conectado a una red cercana (casa, trabajo, redes públicas).

lunes, 25 de febrero de 2013

Tarea 4: Detección de Líneas

Link al repositorio: https://github.com/synnick/viscomp

La Tarea 4 consiste en la detección de líneas en una imagen para lo cual se hace uso de la transformada de Hough. Las imagenes de prueba usadas fueron:





Pre procesamiento

Previo a la detección de líneas, es necesario que las imagenes de entrada se encuentren binarizadas. Para comprender más sobre como binarizar una imagen, véase éste post.

Detección de Líneas

El método de detección consiste en calcular las gradientes vertical y horizontal de una cierta imagen, para calcular en base a ellos el ángulo de un cierto pixel en la imagen. Los gradientes se calculan utilizando máscaras de convolución, como la máscara de Sobel para bordes horizontales y la máscara para bordes verticales (para comprender más acerca de las máscaras de convolución y como aplicarlas, véase éste post).

Los gradientes anteriores serán dos "imagenes nuevas" (solo representamos las matrices con los valores de los pixeles, no se guardan como salida '.png'), en las cuales de igual manera que la imagen de entrada, solo contarán con valores binarios (0 o 255, negro o blanco). 

En base a los gradientes, se calcula el ángulo para cada pixel, dependiendo de los valores del gradiente horizontal y el gradiente vertical en dicho pixel. En una imagen binarizada, podemos tomar en cuenta lo siguiente:

Sí $g_{x} = 0$ y $g_{y} = 0$ , $ \theta = Nulo (no hay ángulo)$
Sí $g_{x} = 255$ y $g_{y} = 0$ , $ \theta = 0°$
Sí $g_{x} = 0$ y $g_{y} = 255$ , $ \theta = 90°$

También se toma en cuenta la fórmula:

$\theta = \arctan ( g_y / g_x)$

Donde $\theta$ es el ángulo, $\arctan$ es la función matemática arco tangente, $g_{y}$ el gradiente vertical y $g_{x}$ el gradiente horizontal.

Con cada ángulo además calculamos una variable rho con la siguiente fórmula:

$ \rho = x \cos ( \theta ) + y \sin ( \theta) $

que servirá para generar una matriz, donde cada índice $(x, y)$ tendrá su par $(\rho, \theta)$.

Para poder detectar líneas con está matriz, debemos de ahora crear otra lista (o diccionario en mi caso), donde para cada par diferente $(\rho, \theta)$ sumaremos un contador por cada vez que se encuentre en un pixel. Este diccionario nos ayudará a determinar cuales pixeles son líneas y cuales no, ya que entre más repeticiones tenga un par $(\rho, \theta)$ es más probable que todos los pixeles que tengan ese par sean una misma línea.

Al final, pintamos los pixeles que seleccionemos como líneas en base al diccionario anterior. Para efecto demostrativo, el programa pinta las líneas verticales de color azul, y las líneas horizontales de color rojo.

Los resultados, junto a la cantidad de pixeles horizontales y verticales, son los siguientes:



Los valores son similares lo cual es bueno debido a que el Sudoku es básicamente una tabla simétrica con cuadros. La diferencia entre las cantidades de pixeles es debido a los números dentro de ciertas celdas de la tabla, que funcionan como ruido al detectar pequeñas líneas en ellos.



Aquí los valores en la cantidad de pixeles son idénticos, por tratarse de una imagen simétrica con la misma cantidad de líneas horizontales y verticales.



En esta imagen observamos que existen mayor cantidad de líneas horizontales que verticales. Esto lo podemos comprobar al observar las cantidades de pixeles detectadas, siendo un mayor número los pixeles horizontales que los verticales.

Por alguna razón cerca de los finales de las líneas se localiza una linea contraria (al final de las líneas verticales aparecen pequeñas lineas horizontales y viceversa).

Código:


Tarea 4: Calidad de Servicio - PS3 Media Server

Para esta Tarea escogí realizar diferentes pruebas de calidad de servicio (Quality of Service -QoS) a la aplicación PS3 Media Server, a través de una red Infinitum inalámbrica.

PS3 Media Server

PS3 Media Server o PMS, es un serrvidor media uPnP DLNA.


DLNA (Digital Living Network Alliance) es un estándar que permite a los dispositivos digitales como PCs, televisiones, smartphones conectados en una red, compartir datos entre sí, de ser compatibles.

Los dispositivos DLNA-compatibles sirven dos funciones diferentes. 'Servidores' que distribuyen multimedia como imagenes, música, o videos, y 'clientes' que reciben y reproducen dichos datos.

Usando el PS3 como cliente, y una PC ejecutando PMS como servidor, es posible reproducir imagenes, videos o música almacenada en el servidor a través de la red local.

Calidad de Servicio

Al hacer el ejemplo con una red inalámbrica, el setup es similar al siguiente (omitiendo el dispositivo de audio):


Los factores que se tomarán en cuenta (explicados en el post de laboratorio) son los siguientes:
  • Jitter
  • Bit rate
  • Pérdida de Paquetes
  • Latencia
Bit Rate

El bit-rate básicamente es la velocidad de transmisión con la que cuenta la aplicación para trabajar. Aquí el hecho de que se trata un servidor DLNA, es decir, las transmisiones son locales, ayudan bastante a aumentar el bit-rate, lo cual hace que no sea un factor real que afecte en la calidad de servicio.

Con PMS es sencillo monitorear el bit rate debido a que muestra como va cambiando junto al máximo de toda la sesión. Al pausar el video o no reproducirlo, este lógicamente se encontrará en 0 debido a que no se está enviando nada. Pero al  ir reproduciendo el video, el bit rate aumenta y varía con el tiempo, entre 0 y MAX, MAX posiblemente cambiando también.


Current bitrate representa la velocidad de transmisión actual (11 Megabytes por segundo) y Peak bitrate el máximo al que ha llegado en la sesión actual.

Pude observar dos cosas muy importantes:
  • Tomando en cuenta que no tenía ninguna otra aplicación utilizando la red, el promedio en el bitrate rondaba los 11 Mb/s - 12 Mb/s sin ninguna interferencia notable
  • Al bajar de 10 Mb/s, el vídeo se congelaba proporcionalmente al disminuir la velocidad.
Conclusión con el bit rate: Asumiendo que el servicio es utilizado por sí solo, es decir sin utilizar alguna otra aplicación que pudiera limitar el bit rate que PMS utiliza, se comporta de forma excelente sin lag o interferencia notable. Pero esto no siempre es así, normalmente las personas tienen sus smartphones conectados a su red mientras ven películas con este tipo de streams, o existe alguna otra persona simultáneamente realizando alguna otra tarea, lo que afectaría el desempeño de PMS.

Pérdida de Paquetes

Como se menciona en el post de laboratorio, la pérdida de paquetes no es realmente significativa en la calidad de servicio si el bit rate es alto. Entre más incrementa el bit rate, menos es la probabilidad de que exista pérdida de paquetes.

De igual manera, realizando una medición de pérdida de paquetes mediante el uso de Wireshark, podemos ver que esto es cierto. Para ver los paquetes perdidos durante una sesión TCP, primero es necesario aislar dicha sesión de las demás, dando click a un cierto paquete que sepamos que pertenece a dicha sesión y seleccionando Follow TCP Stream. Esto nos presenta una ventana con los paquetes filtrados para mostrar solo los que pertenecen a esta comunicación. Ya con esto, se agrega un nuevo filtro "and tcp.analysis.lost_segment" para poder mostrar los paquetes perdidos. En este caso no apareció ningún paquete que se haya perdido durante la comunicación como se puede observar.



Conclusión: Como trabajamos con velocidades considerablemente altas de bit rate, la pérdida de paquetes no es significativa, agregando además que se trata de una red local.

Latencia (Delay)

Desde el momento de saber que PMS funciona con tecnología DLNA, es decir, en redes locales podemos predecir que la latencia no es un factor real (el servidor y el cliente se encuentran en la misma red), pero de igual manera podemos comprobarlo.

Para medir la latencia, utilicé simplemente ping, haciendo un ping desde la IP del servidor (PC) a la IP del cliente (PS3). Los resultados (cubriendo las IPs por motivos de seguridad) son los siguientes:


Aquí obtenemos un promedio de 3ms en los tiempos, con un máximo de 5ms. El tiempo es excelente como se esperaba, por ser un simple envío a una red local.

Conclusión: La latencia no es factor en el caso de PMS, debido principalmente a que la comunicación entre cliente y servidor se realiza en una red local, y los tiempos de envío y regreso (round trip) son demasiado pequeños.

Jitter

Para estudiar el jitter o (packet delay variation), se hace uso de Wireshark de nuevo, realizando una gráfica de tiempos sobre las transmisiones entre el cliente y servidor (PC y PS3). Esto se puede acceder en la pestaña de Statistics-> Flow graph. Con esto podemos crear un gráfico del flujo de la sesión TCP, mostrando los tiempos en los que se envían y reciben los datos.


Observando a la izquierda, tenemos los tiempos en los que se fueron enviando los paquetes (desde el punto 0 cuando se inicio la medición, en adelante).

Graficando las variaciones en los tiempos, podemos ver los cambios de forma más sencilla:
Conclusión: Existe jitter en la transmisión de datos entre el cliente y servidor, debido a que ciertos paquetes son enviados más rápidamente que otros.


domingo, 24 de febrero de 2013

Laboratorio 4: Calidad de Servicio

A continuación se describirán algunos factores que afectan la calidad de servicio (Quality of Service - QoS) en aplicaciones o servicios, principalmente streams de video, videojuegos en línea, Voz IP, etc.

Latencia

La latencia es una medida de el retraso que existe entre el envío de un cierto paquete, y la respuesta recibida. 



Los problemas con la latencia ocurren cuando un cierto paquete tome una gran cantidad de tiempo (relativo a las redes de telecomunicaciones), para llegar a su destino debido a que se queda colgado en largas colas o toma rutas más largas para evitar congestión. 

Herramientas como ping y traceroute miden la latencia determinando el tiempo que toma a un paquete determinado para viajar desde un origen hasta un destino y de vuelta. En conexiones DSL o Internet por cable, las latencias de menos de 100 ms (milisegundos) son típicas y menos de 25ms son deseadas.

Efecto en la Calidad de Servicio

El retraso casado por este efecto, puede acumularse sobre el tiempo, donde una excesiva latencia puede causar que aplicaciones como juegos en línea o streams de video sean altamente afectados.

Bit Rate

Si otros usuarios comparten los mismos recursos de la red, el bit rate que es usado por un cierto stream de datos puede ser muy bajo para los servicios dados (streams multimedia, juegos en línea, etc) si cada stream de datos obtiene la misma prioridad.

La limitación del bit rate para una aplicación multimedia puede llevar a cargas lentas de vídeos o en algunos casos largos tiempos de buffering. En el caso de los videojuegos en línea, el efecto principal sería el LAG (el retraso entre la acción que realiza un jugador y la respuesta o reacción del juego).



En la imagen anterior se puede observar un efecto común de un bit rate limitado, el LAG. El esqueleto rojo y azul de la derecha es la posición en la cual el jugador cliente presiono el botón de disparar. En el tiempo que toma en enviar la información del comando presionado al servidor, el otro jugador ya cambió de posición hacia donde se encuentra el soldado. Normalmente esto significaría que el disparo se daría por fallado, aun cuando el  jugador cliente apuntaba directamente al soldado, pero los juegos de hoy en día implementan LAG compensation para arreglar esto, moviendo a todos los jugadores a la posición que estaban al momento de recibir el comando y restando la latencia.

Pérdida de Paquetes

Los routers pueden fallar al entregar algunos paquetes si los datos están corruptos o llegan cuando los buffers están llenos. La aplicación que recibe el paquete suele solicitar que la información sea retransmitida, causando retrasos severos en la transmisión.

En altas velocidades de bit rate, la pérdida de paquete no es tan notable, debido a que al existir una alta velocidad, la retransmisión de dicho paquete no afecta la transmisión de los demás. Esto es ilustrado en la siguiente gráfica.



Jitter (Packet Delay Variation - PDV)

Los paquetes desde el origen llegan a la destinación con diferentes retrasos. Un retraso de un paquete varía con su posición en las colas de los routers a través del camino entre el origen y el destino, y esta posición puede variar de forma impredecible. 

Es usado frecuentemente como una medida de la variabilidad sobre el tiempo de la latencia de los paquetes a través de una red. Una red con una latencia constante, no tiene variación (jitter). Es expresado como un promedio de la desviación de la latencia. El término estándar para el jitter es packet delay variation (retraso en la variación del paquete). 

Para medir esta variación, es posible utilizar Wireshark y sus herramientas estadísticas para obtener una gráfica sobre el tiempo de una cierta "conversación".



Entrega fuera de orden

Cuando una colección de paquetes relacionados es ruteada por una red, diferente paquetes pueden tomar diferentes rutas, cada una resultando en un retraso diferente. El resultado es que los paquetes llegan en diferente orden del que fueron mandados. Este problema requiere que protocolos especiales los reordenen a un estado definido cuando lleguen a su destino.

Los streams de videos y Voz IP son dramáticamente afectados por ambos la latencia y la falta de orden de secuencia.

Referencias:

jueves, 21 de febrero de 2013

2nd Assignment: String Matching

For this assignment we had to program two algorithms of string matching and report and experiment different the worst-time complexity of them. The algorithms are:
  • Knuth-Morris-Pratt
  • Boyer-Moore
Before explaining the algorithms, I will explain a simple and basic way of finding a sub-string in a string, so we can compare it with the algorithms for better understanding.

The Basic Way

So the basic way of searching for a sub-string within a string would be pretty obvious, searching and comparing every character of the string with the sub-string in a very inefficient way. The code that does this is as follows:

The Python script



Example Run:


With this search algorithm, we did 21 comparisons in a T with length n = 7 and using a P with length m = 3. So we compare every character in T, m times, which is very inefficient.

Knutt-Morris-Pratt Algorithm

The KMP algorithm is a very easy to understand and somewhat acceptable algorithm for string searching. The principle is the same as the basic naive way, but instead of keep searching when we find a mismatch between a character in the string and the pattern, we shift a k number of characters ahead, k being the number of matches that we'd already found.

Let T = 'ASASDAA', so n = 7
and P = 'ASD', so m = 3


P is found in the 2 index of T.

So, in the first comparisons (column  1) we find two letters, but the third one doesn't match. According to the algorithm we can advance 2 positions (we matched 2 letters, and found a mismatch). In the next comparisons we find the pattern, so we can advance m positions. Finally, the number of remaining letters in T is 2, which is less than m so we can skip the comparisons at the end and just finish the execution.

The Python script:


Running the previous example:


Worst Case Complexity

It's easy to think of a way that would make this algorithm behave the worst way. We know that the shift is going to be 1 when we find a match. So if we find m - 1 matches (all except the last character) and then we find a mismatch, we already compared m - 1 characters in vain, so to create a worst case we can repeat this pattern k times, and add the correct match at the end.

An example using k = 100 and 'K' as the filler character would be:

"ASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASKASD"

Analyzing this worst case string with the algorithm gives us:


399 Comparisons with T of length 300

To better analyzing the worst case and, let's plot the growth of the comparisons while the length increases:

                   Worst Case T analysis                                                  A regular T analysis.


The growth is linear as we can see. So even in a worst case scenario, the complexity is O(m + n).


Time


The growth of the time while T's length increases. As we can see the efficiency is clearly good, because we get 0.1 seconds with a 10, 000 length T.

Boyer-Moore Algorithm


This algorithm was somewhat tricky to understand, and even so I had to guide myself using the C code in this page. The principle is that we had to do some pre-processing before we start searching for the string.

In this pre-processing we define two arrays (in my case, a list and a dictionary). This is so we can define "rules" to shift faster ahead and avoid unnecessary comparisons.

Bad character Rule


The Bad character rules is applied when a character that we are comparing in T is not in P. To fill this array (which is a dictionary in my case) we first we check every character in T. If it is not in P, we assign that character the value m (length of P). Otherwise, we will assign it a value from searching that character in P from right to left.

So the Bad Character dictionary for the 'ASASDAA' example is:

{'A': 2, 'S': 1, 'D': 0}
  • A is in the position 2 (counting from 0 to m - 1) from right to left.
  • S is in the position 1 from right to left.
  • D is in the position 0 from right to left.

The Python script:



Running the previous example:


Worst Case Complexity

The worst case complexity would be repeating the word one time after another k number of times. Something like:

P = ASD          T = ASDASDASDASDASD....

Comparations

                   Worst Case T analysis                                                  A regular T analysis.


We can see that even in a worst-case scenario, the growth is linear, approximately 1/2 n. This shows that the  Boyer-Moore algorithm is the most efficient one for every length of T. 

Time Analysis


The algorithm is incredibly fast, completing searches in  0.06 seconds with a 10, 000 length T.

References:

miércoles, 20 de febrero de 2013

Laboratorio 3: Convex Hull, Dilatación

Link al repositorio: https://github.com/synnick/viscomp


En esta semana trabajamos con lo que es obtener el Convex Hull de una imagen, que es básicamente un polígono que recubre todo el contorno de la imagen. Para poder realizarlo es necesario contar con otras funcones programadas previamente en los posts de la materia y laboratorio. 

Obtención de contornos (Opcional, puede usarse una imagen dibujada en cualquier herramienta)

En el post de Laboratorio 2 y la Tarea 1 de la materia, trabajamos dos formas distintas de obtener los contornos (para más explicación de como se obtienen ver los respectivos posts). Es necesario utilizar alguno para obtener una imagen binaria con el fondo siendo negro y los bordes blancos. Esto debido a que el convex hull se dibujará alrededor de los contornos y es necesario saber identificarlos del resto de la imagen.

En este caso, como el punto de interés es el convex hull, dibuje directamente imagenes de prueba en KolourPaint para Linux y las utilicé con el programa.

Imagen Usada:


Como se puede ver es una imagen con fondo totalmente negro, con solo una figura aleatoria. 

Localización de Contornos

Esta parte es obligatoria, y para hacerlo se hace uso del algoritmo BFS programado en la Tarea 2 de la materia (de nuevo, ver el post para más información). En dicho post se utilizaba el algoritmo para localizar figuras y el fondo, por lo cual buscabamos un punto negro y pintabamos todos sus vecinos que fueran de su mismo color de algún color aleatorio.


Ahora, haremos algo parecido pero con los contornos (buscando pixeles blancos), con el objetivo de usar BFS para obtener todos sus puntos y después poder aplicar un algoritmo para calcular el convex hull.

Para poder hacer esto forzosamente tenemos que marcar los puntos recorridos para evitar loops infinitos al buscar el contorno, por lo cual pintamos los contornos de rojo.


Pintando todos los contornos rojos sabemos que recorrimos todos los puntos del contorno. Todos estos puntos se guardan en una lista, que utilizará el algoritmo de convex hull para encontrar los vértices del polígono envolvente.

Gift Wrapping

Uno de los múltiples algoritmos para obtener el convex hull de un set de puntos es Gift Wrapping, también conocido como Jarvis's march. El funcionamiento se basa en dos principios:

  • Se inicia a un punto extremo dentro de los puntos del contorno, normalmente el que se encuentre más a la izquierda.
  • En cada paso, se prueba cada punto de los puntos y se encuentra cual hace la vuelta más larga hacia la derecha. Este punto debe estar en el contorno.
La siguiente imagen explica bien estos conceptos:

Aplicando este algoritmo, localizamos los puntos del convex hull y los pintamos de color verde para demostración:


Lo siguiente es dibujar líneas entre ellos, la forma en la que lo hice fue utilizando Tkinter, colocando la imagen original (binarizada) como fondo, y dibujando líneas azules entre los puntos del convex hull sobre el Canvas. El resultado es así:


Las líneas azules envuelven correctamente el contorno blanco (como un regalo, por eso Gift Wrapping). 

Ejemplos de funcionamiento con tiempo de operaciones (medido desde la recolección de puntos del contorno, hasta la localización de los puntos del convex hull):

Imagen Original
Convex Hull
Tiempo (s)


0.54566693306


2.74937391281


2.74453306198


3.45063400269

Código



Dilatación

Otra cosa que implementé fue dilatación, que como el nombre podría indicar (por su contraparte física) consiste en ampliar o engordar algunas partes de una imagen. Típicamente, lo que se utiliza como entrada es una imágen binarizada, a la cual se le engordaran los pixeles blancos, pero en mi caso lo utilicé en los puntos negros. La imagen de ejemplo es la siguiente:






Código:



Referencias: