Algoritmos de búsqueda y ordenamiento - Analizador de redes

main1.png main2.png main3.png

Dos tareas comunes cuando se trabaja con arreglos de datos son buscar datos y organizar los datos usando algún orden, ascendente o descendente, alfabéticamente o numéricamente. Para realizar estas tareas eficientemente se siguen algoritmos de búsqueda y de ordenamiento. Un algoritmo sencillo para hacer búsquedas es la búsqueda lineal. Dos algoritmos de ordenamiento sencillos y bien conocidos son el ordenamiento de selección (Selection sort) y el ordenamiento por burbujas (Bubble sort). En esta experiencia de laboratorio completarás una aplicación para el monitoreo de flujo de redes para practicar la implementación del algoritmo de búsqueda lineal y algoritmos de búsqueda.

Objetivos:

  1. Implementar una modificación del algoritmo de búsqueda lineal.

  2. Practicar el ordenamiento de arreglos por selección y por método de "burbuja".

  3. Practicar el uso de objetos, estructuras de decisión y repetición.

  4. Aprender algunos métodos de la clase vector de C++.

Pre-Lab:

Antes de llegar al laboratorio debes:

  1. Repasar los algoritmos de búsqueda lineal, ordenamiento por selección y de burbuja.

  2. Estudiar el método size() de la clase vector de C++.

  3. Familiarizarte con los métodos de la clase Packet incluida en el archivo packet.h del proyecto NetworkAnalyzer.

  4. Estudiar los conceptos e instrucciones para la sesión de laboratorio.

  5. Tomar el quiz Pre-Lab, disponible en Moodle.

Comunicación entre computadoras

Las computadoras se comunican por medio del Internet utilizando el Protocolo de Internet (IP, por sus siglas en inglés). Cuando una computadora envía información (o mensaje) a otra computadora, la información se envía por Paquetes de Internet que contienen la dirección fuente ("source address"), que es la dirección de Internet de la computadora que está enviando la información, y la dirección del destino ("destination address"), que es dirección de Internet de la computadora que debe recibir el mensaje. Las direcciones de Internet se usan para guiar la información de una computadora a otra, pero, una vez el paquete llega a su destino, ¿quién se supone que reciba la información? ¿Cuál aplicación debe recibir la información?

Los paquetes de internet también deben especificar la aplicación que envía la información y la aplicación que debe recibirla. Podemos pensar que las direcciones de Internet son las direcciones de correo de una casa, y que las aplicaciones que envían y reciben la información son las personas que envían y reciben la correspondencia. Para enviar una carta por correo, hay que especificar a qué persona se le está enviando la carta. Esto corresponde a especificar la aplicación que recibe la información. Para identificar la aplicación fuente y la aplicación del destino, el protocolo de Internet usa lo que se conoce como números de puerto. Mirando la información del paquete, se puede identificar las direcciones y puertos de la fuente y del destino.

Por ejemplo, cuando la computadora que usas en un laboratorio se comunica con el servidor donde se encuentra el programa Moodle, los paquetes que llevan la información de tu computadora al servidor contienen la dirección de la fuente, que es la computadora del laboratorio, y la dirección del destinatario, que es el servidor de Moodle. El puerto fuente es el de tu buscador web y el puerto destinatario es el del servidor de Moodle.

Las direcciones de internet ocupan 4 bytes (32 bits) y usualmente se presentan al usuario como cadenas de 4 valores decimales. Cada valor decimal entre 0 y 255 es la representación decimal de uno de los 4 bytes: "(0-255).(0-255).(0-255).(0-255)". Algunos ejemplos de direcciones de IP son: 10.0.1.10, 192.168.10.11, 136.145.54.10.

Los números de puertos ocupan 2 bytes (16 bits). Por lo tanto, los valores para los números de puertos van de 0 a 65535. Algunos números de puertos asignados a aplicaciones de servicios conocidos son: 22 para ssh, 23 para telnet, 25 para smtp, 80 para http.

La aplicación que veremos hoy se puede utilizar para monitorear lo que se conoce como flujo en redes o "NetFlows". Un "NetFlow" se compone al unir los paquetes de una comunicación unidireccional entre las aplicaciones de dos computadoras. Por ejemplo, un "NetFlow" se puede componer de los paquetes usados para enviar la información desde tu navegador web a la aplicación http del servidor de Moodle.

La Figura 1 muestra la interfaz de la aplicación Network Analyzer.

figure1.png

Figura 1. Interfaz para manejar la aplicación de Network Analyzer.

Cada fila en la tabla de la Figura 1 contendrá un "NetFlow" compuesto de las direcciones de la fuente y del destinatario, los puertos de la fuente y del destinatario, el número de paquetes y el número de octetos (8 bits) en una comunicación unidireccional entre las computadoras fuente y destinataria, desde el puerto fuente al puerto destino.

La aplicación que completarás hoy le permitirá al usuario el analizar el estatus de una red. Entre otras cosas, le permitirá:

  • identificar cuáles comunicaciones transmiten la mayor cantidad de datos
  • identificar cuáles aplicaciones están corriendo en ciertas computadoras
  • identificar cuáles computadoras transmiten grandes cantidades de paquetes comparadas con la cantidad de datos

Bibliotecas

Para esta experiencia de laboratorio utilizarás objetos de clase vector, que se parecen a los arreglos, y necesitarás saber cómo usar el método size() de los objetos de clase vector. También debes familiarizarte con la biblioteca de la clase Packet que se define en este proyecto. La biblioteca Packet.h contiene los prototipos de los "setters" y "getters" necesarios para completar la información de un paquete de "NetFlow".

Sesión de laboratorio:

La aplicación que completarás hoy le permite al usuario subir un archivo que contenga expedientes de "NetFlow" utilizando el botón "Open NetFlow File", guarda los expedientes en un vector de paquetes, y los despliega en la tabla de contenido del interfaz de la aplicación como se muestra en la Figura 2.

figure2.png

Figura 2. Interfaz de la aplicación Network Analyzer con los paquetes de flujo de datos en una red.

El archivo que utilizarás para los ejercicios, network_sample.dat contiene expedientes de paquetes de "NetFlow" con el siguiente formato:

Source_Address Destination_Address Source_Port Destination_Port Octects Packets
136.145.181.130 136.145.181.227 5 33 764 16
136.145.181.101 136.145.181.213 37 40 48 4
136.145.181.151 136.145.181.60 45 21 316 9
136.145.181.165 136.145.181.19 8 39 795 24
136.145.181.53 136.145.181.174 34 21 79 22
136.145.181.40 136.145.181.140 58 22 186 5
136.145.181.33 136.145.181.209 76 25 614 13
136.145.181.175 136.145.181.38 30 39 100 8
136.145.181.126 136.145.181.99 57 33 965 14

Queremos declarar un vector que guarda objetos de tipo Packet, y entonces invocar la función miembro getSrcPort() al elemento 4 del vector (asuma que ya está lleno de información al declararlo). ¿Cuál de las siguientes instrucciones lograría esto? La respuesta correcta es la tercera opción. La primera opción declara el vector de objetos tipo Packet bien, pero invoca el método getSrcPort() incorrectamente. Queremos encontrar la información en el elemento 4. El método getSrcPort() puede ser invocado a objetos de clase Packet. El objeto netFlow es un vector, no un Packet.
La segunda opción no declara el vector bien. Además la instrucción de netFlow[i.getSrcPort()]; no está invocando el método getSrcPort() a uno de los objetos de netFlow si no a una variable i (que ni siquiera ha sido definida). La cuarta opción declara el vector bien, pero nuevamente utiliza netFlow[i.getSrcPort()].

Queremos recorrer un vector de objetos Packet, filtrando los elementos cuyos “Destination Address” y “Source Address” son iguales y inhabilitando los demás. ¿Cúal de los siguientes está correcto? La primera opción es la correcta. La segunda opción es incorrecta ya que elimina los elementos cuyos “Destination Address” y “Source Address” son iguales, y esos son los que queremos guardar. La tercera opción utiliza la función netdata.length(), la cual le corresponde a un string, pero los vectores utilizan la función size(). La cuarta opción intenta asignarle un 0 a la posición correspondiente del vector netdata, lo cual está incorrecto.

Ejercicio 1 - Familiarizarte con la clase Packet

Instrucciones

  1. Carga a QtCreator el proyecto NetworkAnalyzer. Hay dos maneras de hacer esto:

  2. Utilizando la máquina virtual: Haz doble "click" en el archivo NetworkAnalyzer.pro que se encuentra en el directorio /home/eip/labs/sorting-networkanalyzer de la máquina virtual.

  3. Descargando la carpeta del proyecto de Bitbucket: Utiliza un terminal y escribe el comando git clone http://bitbucket.org/eip-uprrp/sorting-networkanalyzer para descargar la carpeta sorting-networkanalyzer de Bitbucket. En esa carpeta, haz doble “click” en el archivo NetworkAnalyzer.pro.

  4. Abre el archivo packet.cpp. Estudia los atributos y métodos de la clase Packet.

  5. Los datos que maneja la aplicación NetworkAnalyzer están almacenados en un vector de objetos de clase Packet. El vector es una clase provista en el “Standard Template Library” de C++ que sirve para almacenar datos u objetos del mismo tipo. Al igual que los arreglos, los vectores asignan un índice (comenzando con el índice 0) a cada elemento que almacenan. El elemento i-ésimo de un vector V se puede acceder usando V[i]. La diferencia principal entre vectores y arreglos es que el tamaño de los vectores puede cambiar, no hay que definir un tamaño fijo de antemano como sucede con los arreglos.

  6. Un método met del objeto en la posición i en el vector puede accederse escribiendo V[i].met(). El contenido de todos los atributos de un objeto puede asignarse a otro objeto de la misma clase "a la vez". Por ejemplo, puedes asignar el contenido de todos los atributos del objeto en la entrada k del vector V a los atributos correspondientes del objeto en la entrada i del vector V escribiendo V[i]=V[k].

Ejercicio 2 - Filtrar comunicaciones

Instrucciones

  1. Abre el archivo Filter.cpp. En este ejercicio completarás las siguientes funciones que están contenidas en este archivo:

    • FilterBySrcAddr
    • FilterByDstAddr
    • FilterBySrcPort
    • FilterByDstPort

Cada una de estas funciones recibe un vector de objetos de clase Packet y una clave de búsqueda. Cada función (nota sus nombres) está relacionada a un atributo de la clase Packet y deberá "filtrar" los paquetes en el vector que correspondan a la clave. Para filtrar estos paquetes usarás una modificación del algoritmo de búsqueda lineal que consiste en hacer una búsqueda secuencial para encontrar todas las ocurrencias de un dato. En cada función, el algoritmo debe buscar en cada paquete del vector y desactivar los paquetes en los que el contenido del miembro de interés no es igual al de la clave de búsqueda. Para desactivar el paquete usa el método disable() de la clase Packet. El filtrado consiste en mantener solo los paquetes que corresponden a la clave.

Por ejemplo, si estás filtrando por Source Address y la clave de búsqueda es 136.145.181.130, la función FilterBySrcAddr mantendrá todos los paquetes del vector cuyo Source Address es 136.145.181.130 y desactivará todos los otros.

La siguiente figura es una foto del interfaz de la aplicación luego de filtrar los datos por Source Address con la clave 136.145.181.130.

figure3.png

Figura 3. Interfaz de la aplicación Network Analyzer con los paquetes de flujo de datos en una red filtrados por Source Address con clave 136.145.181.130.

Ejercicio 3 - Ordenar datos

Instrucciones

  1. Abre el archivo Sort.cpp. En este ejercicio completarás las siguientes funciones que están contenidas en este archivo:

    • SortBySrcAddr
    • SortByDstAddr
    • SortBySrcPort

    • SortByDstPort

      Cada una de esas funciones recibe un vector de clase Packet. Cada función (nota sus nombres) está relacionada a un atributo de la clase Packet y deberá "ordenar" los paquetes del vector de acuerdo al atributo de interés.

      La siguiente figura es una foto del interfaz de la aplicación luego de ordenar los datos por Source Address.

figure4.png

Figura 4. Interfaz de la aplicación Network Analyzer con los paquetes de flujo de datos en una red ordenados por Source Address.

  1. Completa la función SortBySrcAddr implementando el algoritmo de burbuja (Bubble Sort), ordenando los paquetes por el Source Address.

  2. Completa la función SortByDstAddr implementando el algoritmo de selección (Selection Sort), ordenando los paquetes por el Destination Address.

  3. Completa la función SortBySrcPort implementando el algoritmo de burbuja (Bubble Sort), ordenando los paquetes por el Source Port.

  4. Completa la función SortByDstPort implementando el algoritmo de selección (Selection Sort), ordenando los paquetes por el Destination Port.

Entregas

  1. Utiliza "Entrega 1" en Moodle para entregar el archivo Filter.cpp que modificaste en el Ejercicio 1. Recuerda utilizar buenas prácticas de programación, incluye el nombre de los programadores y documenta tu programa.

  2. Utiliza "Entrega 2" en Moodle para entregar el archivo Sort.cpp que modificaste en el Ejercicio 2. Recuerda utilizar buenas prácticas de programación, incluye el nombre de los programadores y documenta tu programa.

Referencias

[1] http://www.nextgigsystems.com/aggregation_switches/gigamon_filter_packets.html

[2] http://metaanalytics.org/web-analytics/social-network-analysis/

[3] http://www.java2novice.com/java-sorting-algorithms/quick-sort/

[4] http://intranet.deei.fct.ualg.pt/IC/t22.html

results matching ""

    No results matching ""