Sesión Laboratorio 12: Práctica 5-1

• Tiempo: 2h
• Fecha: Jueves 9 de Mayo de 2024
• Objetivos de la sesión:
  • Presentar la práctica 5
  • Aprender a acceder a los píxeles de las imágenes
  • Utilizar los filtros de imágenes para simular el tráfico en la red
  • Usar los deslizadores para simular los umbrales de carga en los nodos

Contenido

• Introducción
• ¡A practicar!
• Resumen de tareas a realizar
• Conclusiones
• Autores
• Licencia
• Enlaces

Introducción

Vamos a añadir algunas mejoras para visualizar mejor la red aleatoria y los datos que la configuran.

Una conexión un peso

En esta versión de la red todos los pesos tienen el mismo valor, aún así estaría bien visualizar los pesos asociados a cada conexión.

Para conseguirlo, vamos a cambiar un poco la función que se ocupa de pintar las conexiones entre nodos drawNet.

Igual que hicimos para mostrar información extra en los nodos, vamos a mostrar el peso de cada conexión en el punto medio de cada una de las líneas.

Esta es la nueva función drawNet.

// Dibujar la red en el canvas
function drawNet(nnodes) {
  // Dibujamos las conexiones entre nodos
  nnodes.forEach(nodo => {
    nodo.conexiones.forEach(({ nodo: conexion, peso }) => {
      ctx.beginPath();
      ctx.moveTo(nodo.x, nodo.y);
      ctx.lineTo(conexion.x, conexion.y);
      ctx.stroke();

      ctx.font = '12px Arial';
      ctx.fillStyle = 'black';
      ctx.textAlign = 'center';
      pw = "N" + nodo.id + " pw " + peso;
      const midX = Math.floor((nodo.x + conexion.x)/2);
      const midY = Math.floor((nodo.y + conexion.y)/2);
      ctx.fillText(pw, midX, midY);  

    });
  });

  let nodoDesc; // Descripción del nodo

  // Dibujamos los nodos
  nnodes.forEach(nodo => {
    ctx.beginPath();
    ctx.arc(nodo.x, nodo.y, nodeRadius, 0, 2 * Math.PI);
    ctx.fillStyle = 'blue';
    ctx.fill();
    ctx.stroke();
    ctx.font = '12px Arial';
    ctx.fillStyle = 'white';
    ctx.textAlign = 'center';
    nodoDesc = "N" + nodo.id + " delay " + Math.floor(nodo.delay);
    ctx.fillText(nodoDesc, nodo.x, nodo.y + 5);
  });
}

Resultado

Ahora la red que deberíamos ver se parece a la de la imagen.

Un poco de espacio por favor

A veces los nodos salen apelotonados unos encima de otros. Y cuesta entender la configuración de red de manera visual.

Así que vamos a hacer algunos cambios en la función que genera la red crearRedAleatoriaConCongestion para que la distribución de los nodos en el canvas sea un poco más uniforme.

Como siempre, hay muchas posibles soluciones, después de probar varias cosas, me he decidido por una que no es perfecta, pero da un resultado aceptable.

Si te fijas en la imagen, verás una cuadrícula.

He dividido el eje x en 5 secciones porque es el número máximo de nodos que puedo tener.

Y el eje y por la mitad, para alternar entre la parte de arriba y la de abajo.

Una vez que me sitúo en un cuadrante, elijo unas coordenadas xy de manera aleatoria.

En cada iteración me aseguro de cambiar de cuadrante, en el eje x de manera consecutiva, y en el eje y de manera aleatoria.

javascript: Cada nodo en su cuadrante

Así queda la función crearRedAleatoriaConCongestion:

// Función para generar una red aleatoria con nodos en diferentes estados de congestión
function crearRedAleatoriaConCongestion(numNodos, numConexiones) {
  
  const nodos = [];
  let x = 0, y = 0, delay = 0;
  let nodoActual = 0, nodoAleatorio = 0, pickNode = 0, peso = 0;
  let bSpace = false;

  const xs = Math.floor(canvas.width / numNodos);
  const ys = Math.floor(canvas.height / 2 );
  const xr = canvas.width - nodeRadius;
  const yr = canvas.height - nodeRadius;
  let xp = nodeRadius;
  let yp = nodeRadius;
  let xsa = xs;
  let ysa = ys;

  // Generamos los nodos
  for (let i = 0; i < numNodos; i++) {

    //var random_boolean = Math.random() < 0.5;
    if (Math.random() < 0.5) {
      yp = nodeRadius;
      ysa = ys;
    } 
    else {
      yp = ys;
      ysa = yr;
    }

    x = randomNumber(xp, xsa); // Generar coordenada x aleatoria
    y = randomNumber(yp, ysa); // Generar coordenada y aleatoria

    xp = xsa;
    xsa = xsa + xs;

    if ( xsa > xr && xsa <= canvas.width ) {
      xsa = xr;
    }

    if ( xsa > xr && xsa < canvas.width ) {
      xp = nodeRadius;
      xsa = xs;
    }    

    delay = generarRetardo(); // Retardo aleatorio para simular congestión
    nodos.push(new Nodo(i, x, y, delay)); // Generar un nuevo nodo y añadirlo a la lista de nodos de la red
  }

Resultado

Con este cambio conseguimos que la mayoría de las veces, los nodos estén más separados y que no se solapen.

Una red más realista

Conectar los nodos de manera aleatoria ha estado bien para comenzar.

Pero no nos queda una red realista, o lógica. Lo normal es enlazar un nodo con los nodos más cercanos.

También estaría bien, que el peso de cada conexión fuese la distancia entre los nodos.

Y sería más claro si evitamos nodos doblemente enlazados. Aunque esto puede hacer que algunas rutas no sean las que esperamos, ya verás por qué lo digo.

javascript: Nodos más sofisticados

Para poder hacer lo que nos hemos propuesto necesitamos nodos más inteligentes, necesitamos la siguiente funcionalidad:

• Saber si un nodo está conectado a otro.
• Calcular la distancia entre dos nodos.
• Encontrar el nodo más alejado.
• Encontrar el nodo más cercano.

Ok, vamos paso a paso.

Nuevo método de la clase Nodo: isconnected

Recibe como parámetro el id del nodo para comprobar si el nodo está en nuestro array de conexiones.

Y devuelve true si está en la lista de conexiones, y false si no lo está.

La dificultad de este método está en recorrer una lista de objetos conexión, y que cada uno contiene un nodo y un peso.

Si tenemos clara la estructura de datos que estamos utilizando, es sencillo implementar la funcionalidad para encontrar lo que buscamos.

  // Método para saber si un nodo está en la lista de conexiones de otro
  isconnected(idn) {

    let isconnected = false;

    this.conexiones.forEach(({ nodo: conexion, peso }) => {      
      if (idn == conexion.id) {
        //console.log("id nodo conectado:" + conexion.id);
        isconnected = true;
      }      
    });
    
    return isconnected;
  }

Nuevo método de clase Nodo: node_distance

Si le pasamos las coordenadas (x,y) de otro nodo de la red, nos devuelve la distancia.

  // Método para saber la distancia entre dos nodos
  node_distance(nx, ny) {

    var a = nx - this.x;
    var b = ny - this.y;
        
    return Math.floor(Math.sqrt( a*a + b*b ));

  }

Nuevo método de clase Nodo: far_node

Si le pasamos una lista de nodos, es capaz de encontrar el nodo más alejado.

Y devuelve un objeto que contiene la posición, el identificador del nodo y la distancia.

Esto es muy útil porque nos ahorra tiempo.

  // Método para encontrar el nodo más alejado
  far_node( nodos ) {

    let distn = 0;
    let cnode = this.id;
    let distaux = 0;
    let pos = 0;
    let npos = 0;

    for (let nodo of nodos) {
      distaux = this.node_distance(nodo.x, nodo.y);
  
      if (distaux != 0 && distaux > distn) {
        distn = distaux;
        cnode = nodo.id;
        npos = pos;
      }

      pos += 1;
    }
  
    return {pos: npos, id: cnode, distance: distn,};

  }

Nuevo método de clase Nodo: close_node

Si le pasamos una lista de nodos, es capaz de encontrar el nodo más cercano.

Y devuelve un objeto que contiene la posición, el identificador del nodo y la distancia.

Fíjate que para encontrar el nodo más cercano, partimos del más alejado y vamos iterando hasta encontrar el nodo más cercano, y que no es el propio nodo.

  // Método para encontrar el nodo más cercano
  close_node( nodos ) {

    let far_node = this.far_node( nodos );
    let cnode = far_node.id;
    let distn = far_node.distance;
    let distaux = 0;
    let pos = 0;
    let npos = 0;    
  
    for (let nodo of nodos) {
      distaux = this.node_distance(nodo.x, nodo.y);
  
      if (distaux != 0 && distaux <= distn) {
        distn = distaux;
        cnode = nodo.id;
        npos = pos;
      }

      pos += 1;
    }
  
    return {pos:npos, id: cnode, distance: distn,}
  
  }

Una nueva manera de conectar nodos

Para tener una red aleatoría un poco más realista necesitamos cambiar la función crearRedAleatoriaConCongestion.

Ya hemos resuelto la parte de situar los nodos de manera aleatoria pero uniforme dentro del canvas.

Eso nos va a generar redes distintas por la disposición de los nodos.

Y ahora tenemos que cambiar la manera de conectar los nodos.

Lo que vamos a hacer es recorrer la lista de nodos, y para cada uno, encontrar los nodos más cercanos en función del valor de la variable numConexiones.

En nuestro ejemplo tiene un valor constante de 2, eso quiere decir que cada nodo tendrá como máximo dos conexiones a otros nodos.

Y también puede tener 1 o ninguna.

Esto es muy interesante porque para calcular la ruta más corta debe existir una conexión entre los nodos en la dirección correcta.

Si el nodo cercano que hemos encontrado no está conectado al nodo en el nos encontramos, lo añadimos a su lista de conexiones.

Y si ya hay una conexión en cualquiera de los dos sentidos, no se añade una nueva conexión al nodo actual.

Para hacer todo esto utilizamos los nuevos métodos de la clase Nodo que hemos creado.

Fíjate que para no cambiar la lista de nodos, hacemos una copia cada vez que saltamos al siguiente nodo.

Esta copia nos sirve para encontrar los N nodos más cercanos consecutivos, porque cuando encontramos un candidato lo sacamos de la lista para que no vuelva a ser elegido.

  // Conectamos los nodos
  // Seleccionamos los nodos más cercanos teniendo en cuenta la distancia
  // Seleccionamos tantos nodos como indica la variable numConexiones
  // El nodo será candidato siempre que no estén ya conectados
  for (let nodo of nodos) {
   //console.log("id: " + nodo.id + " distancia al nodo: " + nodo.node_distance(nodos[0].x, nodos[0].y));

    const clonedArray = [...nodos];

    for (let j = 0; j < numConexiones; j++) {
      let close_node = nodo.close_node(clonedArray);
      //console.log(close_node);

      if (!nodo.isconnected(close_node.id) && !clonedArray[close_node.pos].isconnected(nodo.id)) {
        // Añadimos una nueva conexión
        // Con el nodo más cercano y la distancia a ese nodo como el peso de la conexión
        nodo.conectar(clonedArray[close_node.pos], close_node.distance);
      }

      // Eliminamos el nodo seleccionado del array clonado para evitar que 
      // vuelva a salir elegido con splice.
      // 0 - Inserta en la posición que le indicamos.
      // 1 - Remplaza el elemento, y como no le damos un nuevo elemento se queda vacío.      
      clonedArray.splice(close_node.pos, 1);
    }

  }

Ahora nuestra red tiene un aspecto más natural.

Y si calculamos la ruta mínima ves que tiene sentido y nos muestra la ruta a través de la red, saltando de nodo en nodo.

Ahora el peso de la conexión se puede tener en cuenta porque es coherente.

Probando con diferentes redes

Prueba a obtener el camino mínimo con diferentes configuraciones de red.

Ruta mínima obtenida.

Otro ejemplo.

Si te fijas la ruta pasa por el nodo 3, aunque hay una conexión directa del nodo 3 al 4.

Pero si te fijas, verás que la conexión va del nodo cuatro al 2, por lo tanto no la podemos utilizar, porque va en la dirección contraria.

Es decir, nuestra red es un grafo dirigido, y esto lo hace un poco más interesante.

Ahora que tenemos nuestra red adecuada para enviar datos

Ya tenemos todo lo necesario para completar la práctica con éxito.

Ánimo.

¡A practicar!

Si no lo has hecho ya, practica con lo que hemos visto en esta sesión.

Resumen de tareas propuestas

• Implementa los ejemplos de esta sesión y guárdalos en la carpeta P5

Conclusiones

Estamos preparados para enviar nuestros datos multimedia a través de la red de redes.

Autor

Jesús Parrado Alameda (jesusgpa)

Creditos

• Creado a partir del contenido generado por el profesor Jose María Cañas
• Creado a partir del contenido generado por el profesor Juan Gonzalez-Gomez

Licencia

Enlaces

• Universidad Rey Juan Carlos de Madrid
• Escuela Técnica Superior de Ingeniería de Telecomunicaciones (URJC)