Generación de mapas

Con ciertas técnicas se pueden generar mapas tan maravillosos como este. (Amit Patel)

La generación de mapas de forma automática es una tarea realmente fascinante, donde se pueden desarrollar y aplicar muy diversas técnicas matemáticas y de computación (análisis de grafos, reconocimiento de patrones, fractales, etc.) Es uno de esos casos en los que muy diversas materias se reúnen en la resolución de un problema tan concreto y aparentemente lúdico.

Lo primero que se nos viene a la cabeza preguntar es: ¿quién necesita mapas imaginarios? Son clásicos los mapas de ficción que aparecen (generalmente como hoja desplegable) en los libros de género fantástico, con los cuales el autor nos presenta el imaginario mundo en el que se desarrolla la historia. Lo normal ha sido encargar a un dibujante que plasme las calenturientas ideas del autor en un mapa más o menos detallado. De lo primero que se dan cuenta quienes intentan semejante cosa es lo difícil que resulta crear desde cero un mapa mínimamente creíble.

La Tierra Media de J.R.R. Tolkien es un ejemplo "de libro" de un mapa inverosímil.

Los juegos de rol y de estrategia son otros clientes habituales de los mapas imaginarios. Pero ha sido la llegada de los juegos por ordenador la que ha disparado la necesidad de generar infinitos mapas automáticamente, usando la potencia computacional y todo un arsenal de técnicas relacionadas con la Inteligencia Artificial.

Juegos como Sid Meier's Civilization usan intensivamente los mapas generados automáticamente.

Aparte de todos estos usos, como tantos problemas interesantes, se puede abordar la generación de mapas por el simple placer intelectual y, por qué no negarlo, convertirla en una afición bastante friki. Esto es lo que hace el maravilloso bot de Twitter (@unchartedatlas), creado por Martin O'Leary, que me ha inspirado esta serie de artículos.

The Outer Plains of West nou-Soal pic.twitter.com/O58vKeBBY5

— Uncharted Atlas (@unchartedatlas) 28 de agosto de 2017

Este fascinante programa genera cada hora automáticamente un nuevo mapa aleatorio completo con sus ríos, mares, montañas, ciudades e incluso topónimos. Yo de mayor querría hacer algo lo mitad de bueno que esto.

Fractal o no fractal, esa es la cuestión

António Miguel de Campos - Wikipedia

Si la propia naturaleza en muchas ocasiones utiliza fractales, ¿por qué no aprovecharlos para nuestros mapas imaginarios? Los fractales son, en términos muy simples, objetos matemáticos cuya estructura se repite a diferentes escalas.

Para la creación de un paisaje fractal, generalmente se usan polígonos que se van subdividiendo en otros similares, desplazando aleatoriamente el punto central que comparten. Esto se muestra muy bien en la imagen animada anterior, en la que se usan triángulos como base para la generación del terreno.

A pesar de que los fractales imitan bastante bien las formas naturales, hay autores que sostienen que no representan correctamente ciertos procesos clave, como la erosión. Otro incoveniente es que distintas formas del terreno tienen distintas propiedades fractales, por lo que el uso de una función fractal general para todo el mapa no siempre es posible.

Atacando el problema sin fractales

Existen muchas formas de afrontar este problema sin usar fractales. Es un área bastante autodidacta, donde cada autor va modelando a su manera personal, aunque, como ocurre a menudo, las soluciones van convergiendo a una serie de técnicas. Cada una de estas técnicas intenta imitar un proceso, formación o erosión natural, y se van aplicando paso a paso, de manera acumulativa, hasta que finalmente obtenemos el mapa terminado. Es, por tanto, un proceso mucho más "dirigido" por la mano del creador que el proceso fractal que, al menos aparentemente, sería una solución puramente matemática.

Rejilla base

Rejilla hexagonal

Lo más sencillo es crear una rejilla ortogonal (de "cuadraditos") o hexagonal (como un panal de abejas). Si queremos más realismo, tendremos que irnos a una rejilla más compleja de polígonos irregulares (el bot de O'Leary lo hace precisamente de esta manera).

Un caso especial son los mapas para juegos de estrategia, en los que la dinámica del juego suele restringir el tipo de rejilla que se puede usar. También es posible en estos casos, primero generar el mapa con una rejilla irregular y luego adaptarle otra rejilla para los movimientos del juego.

Una forma común de realizar la distribución de la rejilla es mediante diagramas de Voronói. En este caso, las "semillas" serían unos puntos distribuidos más o menos aleatoriamente, y la forma de cada celda se adaptaría hasta ocupar el área más cercana a cada punto.

Caracterización de las celdas

Diagrama de Voronói correspondiente al mapa que se ve al principio de este artículo, con las celdas caracterizadas como tierra, mar y lagos. (Amit Patel)

El siguiente paso va a ser la asignación de distinta naturaleza ("tierra", "mar", etc.) a las celdas de la rejilla. Esto crea la distribución general del mapa.

Una distribución completamente aleatoria daría lugar a mapas muy extraños, por lo que se suelen usar ciertas estrategias, las cuales van a tender a darnos con más probabilidad un tipo de mapa frente a otros (por ejemplo, islas en lugar de continentes). También se puede partir de una forma base creada por un diseñador, si se trata de un encargo para un juego, por ejemplo.

Mapa de elevación

Mapa de elevación (Erik Nordeus)

Un paso clave para hacer un mapa es asignar a cada celda su elevación o altura de terreno. Esto, a la larga, va a definir todos los accidentes geográficos del mapa (cordilleras, ríos, etc.) e indirectamente también la ubicación de las ciudades y otros elementos extra.

Las celdas de mar tendrán elevación cero y, a partir de ahí habrá que ir asignando las alturas siguiendo una cierta estrategia. Aquí tampoco sería realista dejarlo todo al azar. Esta nueva caracterización del terreno es muy similar en concepto a la que hemos visto en el anterior punto, pero distinta en cuanto al algoritmo y parámetros a utilizar. Estos parámetros van a depender de en qué medida queremos generar terrenos preferentemente montañosos o llanos.

Distribución del agua

Los grafos dirigidos nos permiten representar el flujo del agua.

La consecuencia directa del mapa de elevación es la pendiente que van a seguir los flujos de agua. Será necesario crear un grafo dirigido (conjunto de nodos con aristas que tienen una dirección asignada) sobre el mapa de elevación, que irá indicando el camino siempre desde las celdas más altas a las más bajas. Luego aplicaremos algún tipo de algoritmo que simule la "inundación del terreno" y vaya marcando las celdas por las que discurriría el agua.

Los ríos y lagos aparecerán en las zonas donde la humedad supera un cierto umbral. Una vez establecidas estas zonas húmedas, será fácil asignar a cada celda un nivel de humedad decreciente según lo lejos que esté del agua. La caracterización de humedad va a ser clave para el siguiente punto.

Biomas

En Biología, es común agrupar los biomas según temperatura y precipitaciones.

Vamos a tomar prestado de la Biología el concepto de bioma, de una manera bastante laxa, en este caso para representar en diferentes colores o texturas distintas formas de vegetación (pradera, bosque, tundra, etc.)

Usando las elevaciones y los grados de humedad que hemos calculado, no es difícil hacer una correlación entre cada pareja (altura, humedad) y un color en el mapa. También es posible incluir representaciones más artísticas de cada bioma, aunque esto es más propio de la generación de paisajes que de simples mapas.

Añadiendo ruido

Celda con ruido (Amit Patel)

Después de todo lo explicado anteriormente, nuestro mapa parecerá más bien un conjunto de polígonos con colores que un verdadero terreno. Hay que darle alguna forma de irregularidad que lo haga más natural a la vista. Esto es lo que llamamos "ruido", y se hace mediante distintos algoritmos que incluyen alguna forma de aleatoriedad.

En el ejemplo de la imagen, se ha subdividido una diagonal y se han ido moviendo de su lugar los puntos de división de manera aleatoria. También es posible añadir ruido sin cambiar la forma, haciendo que los colores de celdas adyacentes se mezclen en los bordes.

Para saber más

Muchísima información interesante se puede obtener siguiendo a @redblobgames en Twitter. Tiene una demo online donde se pueden experimentar en tiempo real muchos de los conceptos que he introducido en este artículo.

El creador del Uncharted Atlas tiene un tutorial con mucha información sobre cómo está hecho ese bot.

En la Voronoi Wiki hay enlaces a multitud de artículos sobre el uso de este tipo de diagramas.

También es muy recomendable este fascinante generador online de mundos fractales.

Diffie y Hellman

Cabecera del mítico artículo de Diffie y Hellman

En 1976, los profesores Whitfield Diffie y Martin Hellman publicaron un histórico artículo donde sentaron las bases de lo que hoy conocemos como criptografía de clave pública. Voy a explicar las bases del protocolo criptográfico que inventaron, conocido como protocolo de Diffie-Hellman.

Fundamentos matemáticos

El concepto clave es el de raíz primitiva. Dado un número primo p, siempre existe un número entero g menor que él que cumple una curiosa propiedad. Dicha propiedad consiste en que elevando g a todas las potencias entre 1 y p-1, el resto de dividir dicho resultado entre p es el mismo conjunto (desordenado) de números entre 1 y p-1.

Lo vemos mejor con un ejemplo. En la siguiente tabla tenemos en la primera columna todos los números k entre 1 y 22. En la segunda el resultado de 7^k. En la tercera columna está el resto (que se anota como mod) de dividir la segunda columna entre 23. Como vemos, la tercera columna es el mismo conjunto de números k, pero desordenados. Decimos entonces que 7 es la raíz primitiva (también llamado generador) de 23:

k     b = 7^k              7^k mod 23
----------------------------------
1     7                      7 
2     49                     3 
3     343                    21 
4     2401                   9 
5     16807                  17 
6     117649                 4 
7     823543                 5 
8     5764801                12 
9     40353607               15 
10    282475249              13 
11    1977326743             22 
12    13841287201            16 
13    96889010407            20 
14    678223072849           2 
15    4747561509943          14 
16    33232930569601         6 
17    232630513987207        19 
18    1628413597910449       18 
19    11398895185373143      11 
20    79792266297612001      8 
21    558545864083284007     10
22    3909821048582988049    1

Dado cualquier número b perteneciente a la tercera columna, conociendo que g=7 y p=23, decimos que su correspondiente k (primera columna) es su logarítmo discreto (denotado ind_7,23). La notación es la siguiente:

k = ind_g,p(b)

Su utilidad en criptografía deriva del hecho de que el logarítmo discreto de números muy grandes es muy costoso computacionalmente. Si utilizamos un número primo p suficientemente grande, será fácil obtener los valores de b a partir de k, pero casi imposible obtener los diferentes valores de k a partir de los de b.

Supongamos que, conociendo el número primo p y su raíz primitiva g, elegimos al azar dos números X_A y X_B , menores que p. Después realizamos estas operaciones:

Y_A = g^X_A mod p

Y_B = g^X_B mod p

Es decir, estamos convirtiendo valores de la primera columna de nuestra tabla en los de la tercera, o sea, lo que antes llamamos operación fácil.

Ahora volvamos a hacer la misma operación, pero usando los resultados anteriores Y en lugar de g:

K_AB = Y_B^X_A mod p

K_BA = Y_A^X_B mod p

En este momento podemos aplicar la propiedad conmutativa, es decir, que para cualesquiera números a, b y c se cumple que:

A partir de ello fácilmente se extrae que K_AB = K_BA. Hemos producido un valor al que llamaremos simplemente K, el cual es derivado de operaciones relativamente fáciles de hacer. Lo interesante de todo esto es que es muy difícil obtener K, aún conociendo p, g, Y_A e Y_B, si no se conoce al menos uno de los X_A y X_B. Esto implicaría resolver el logarítmo discreto (o índice) ind_g,p, que es lo que antes hallamos casi imposible si p es muy grande.

Diffie y Hellman recibieron el Premio Turing en 2015 por sus aportaciones en criptografía.

Protocolo de intercambio de claves

A partir de las propiedades matemáticas explicadas en el apartado anterior, es fácil construir un protocolo de intercambio de claves, donde los datos intercambiados por canales inseguros serían los valores que no importa hacer públicos (p, g, Y_A e Y_B), y mantendremos en secreto en un extremo X_A y en el otro X_B. Usando ambos por separado cada extremo puede obtener K, que será la clave simétrica utilizada para las comunicaciones encriptadas.

El protocolo completo es:

1. Ambos extremos Ana y Benito acuerdan un número primo p y su raíz primitiva o generador g. Siguiendo el mismo ejemplo anterior, elegimos p=23 y g=7.
2. Cada uno por separado elige un número menor que p al azar. Supongamos que eligen X_A=3 y X_B=15.
3. También por separado computan la función Y = 7^X mod 23. En este ejemplo los resultados son: Y_A=21 e Y_B=14.
4. Ahora intercambian los dos resultados. Ana entrega a Benito su Y_A, y por su parte Benito entrega a Ana su Y_B.
5. Ambos extremos calculan por separado: K = 14³ mod 23 = 7 (en el lado de Ana). K = 21¹⁵ mod 23 = 7 (en el lado de Benito).
6. Ahora utilizan K=7 como clave simétrica para intercambiar cualquier mensaje.

Como podemos observar, los únicos valores que se han intercambiado (y por lo tanto pueden ser conocidos por un tercero) son p=23, g=7, Y_A=21, Y_B=14. Como vimos en el apartado anterior, la clave K=7 no se podría obtener a partir de esos cuatro valores, mientras p sea lo suficientemente grande (bastante más grande que 23, por supuesto).

Normalmente, se llama clave privada o parte privada de la clave a los valores X_A y X_B, que no son conocidos más que por cada comunicante, y clave pública o parte pública de la clave a Y_A e Y_B, que son conocidos por todo el que tenga acceso al medio.

La conjetura de Diffie-Hellman

Las matemáticas implicadas en el protocolo de Diffie-Hellman son muy complejas. Es interesante, sin embargo, saber que el elemento clave es un problema que podemos enunciar simplificadamente como:

"Dado un número generador g y dos valores g^x y g^y, obtenidos de números aleatorios x e y, ¿cuál es el valor de g^xy?"

Diffie y Hellman supusieron que resolver este problema (conocido desde entonces como DHP, Diffie-Hellman Problem) es muy costoso computacionalmente, aunque no lo demostraron. En criptoanálisis se utiliza una variante del mismo (denominada DDHP, Decisional Diffie-Hellman Problem), el cual consiste en saber si g^XY es distinguible de un valor generado aleatoriamente. Hasta el momento nadie ha demostrado que no exista una solución factible computacionalmente.

Aunque el método de Diffie-Hellman tal cual no es muy usado actualmente, varios protocolos criptográficos muy utilizados se basan en la misma suposición de que el problema DDHP no se puede resolver.

El ataque del hombre en el medio

El protocolo de Diffie-Hellman es muy resistente a los ataques pasivos, es decir, donde el intruso se limita a escuchar. Sin embargo, tiene una vulnerabilidad importante cuando el atacante es activo y puede modificar los mensajes en el tránsito. Este tipo de ataques se conocen como man-in-the-middle (hombre en el medio).

Efectivamente, si se observa detalladamente el protocolo explicado anteriormente, vemos que el atacante Carlos podría sustituir los valores Y_A e Y_B de Ana y Benito por sus propios valores Y_CA e Y_CB calculados por él. Ni Ana ni Benito conocían con anterioridad la elección de su comunicante, por lo que no podrán darse cuenta de que en realidad proceden de Carlos. El atacante conoce (porque están en claro) los valores p, g, Y_A e Y_B, por lo que puede acordar con cada extremo su propia clave simétrica K_Ay K_B, respectivamente.

El resultado de todo esto es que Carlos puede desencriptar, encriptar y modificar todos los mensajes entre Ana y Benito, haciendolos pasar por mensajes legítimos del otro extremo. Pocos ataques criptográficos pueden ser tan devastadores como éste.

En la Universidad de Stanford.

Autoridades de certificación

La problemática del hombre en el medio es común a todos los sistemas de criptografía asimétrica. La solución siempre pasa por encontrar un tercero en el que todos confían para verificar la identidad del los extremos de la comunicación. A esta fuente confiable la llamaremos autoridad de certificación (certification authority). No deja de ser una variante de la forma clásica de identificarse mediante un pasaporte o documento sellado por una autoridad competente. Al fin y al cabo, el pasaporte es aceptado según la confianza que tenga el receptor en la autoridad que lo ha sellado.

En el caso del protocolo Diffie-Hellman, podemos establecer un repositorio centralizado donde los participantes registren la parte pública de sus claves, en el ejemplo Y_A e Y_B. Al negociar el inicio de la comunicación, cuando se intercambian claves, Ana y Benito comunicarán con la autoridad para verificar que son las auténticas y no han sido modificadas en el medio. En la práctica algo parecido es lo que ocurre día a día cuando conectamos, por ejemplo, con nuestro banco por Internet. Necesitamos verificar que las páginas que estamos viendo proceden realmente del banco y no de un atacante que quiera quedarse con nuestro dinero.

La solución, en todo caso, es recursiva, dado que el canal que nos comunica con la autoridad también puede ser comprometido por el atacante y por tanto alguien tendrá que haber "certificado al certificador". En la práctica, existen unas pocas autoridades de máximo nivel, que están en manos de empresas (como la famosa Verisign) que todos los comunicantes tienen por confiables universalmente, las cuales a su vez certifican a autoridades más pequeñas a nivel local. Todo esto ha dado lugar a un floreciente negocio que no está exento de peligros.

En un tema del curso estudiaremos cómo funcionan las cadenas de firmantes que verifican la identidad de las personas y los sitios en Internet, así como el funcionamiento de la negociación de conexión con sitios seguros en Internet.

TCP/IP (13): Adaptación a IPv6

En el anterior artículo cantábamos las bondades de IPv6, y al mismo tiempo nos lamentábamos de que su implantación no sea aún total. Hoy vamos a estudiar cómo es la adaptación de IPv4 a IPv6 y las dificultades que encierra.

El rediseño de las cabeceras y de las propias direcciones hacen incompatibles los protocolos IPv4 y IPv6. Los nodos que implementen distintas versiones no pueden comunicarse directamente entre ellos. Para paliar este problema se han previsto distintas técnicas y adaptaciones transitorias:

Transcripción directa de direcciones

Cada dirección IPv4 tiene una dirección IPv6 equivalente, convertible fácilmente. El prefijo ::ffff: indica una dirección IPv4 traducida a IPv6. Los últimos 32 bits (que serían dos grupos hexadecimales) corresponden a la propia dirección IPv4. Para mayor comodidad, se acepta la notación híbrida, dejando la dirección IPv4 en su formato original, como en el siguiente ejemplo:

150.200.1.10

se traduce en

::ffff:150.200.1.10

También existe la transcripción inversa (dirección IPv6 a IPv4), pero lógicamente no puede hacerse de uno a uno, al ser mayor el espacio de direcciones IPv6. Ciertos bloques de direcciones IPv4 se han reservado para mapear direcciones IPv6.

Doble pila

Los nodos que soportan IPv6 lo hacen normalmente mediante una doble pila o una pila híbrida, de manera que puedan manejar paquetes de ambos protocolos. Todos los sistemas operativos modernos lo incorporan por defecto para facilitar la transición.

Hay que tener en cuenta que, aunque el sistema operativo soporte IPv6, no siempre el software de aplicación puede hacer uso de él. Será necesario en ese caso actualizar ese software a una versión superior que sí lo soporte.

Servidores proxy

Se pueden usar servidores específicos a nivel de aplicación (proxies) para dar acceso a los nodos que sólo soportan IPv6 a servidores remotos que sólo soportan IPv4. Esto se puede hacer mediante mecanismos específicos denominados NAT64 y DNS64.

Tunneling

Cuando un nodo o red IPv6 tiene que atravesar otra red que sólo soporta IPv4 para alcanzar sus destinos se les llama nodo o red aislados. En este caso, han de usarse técnicas de tunneling (encapsulado de paquetes) para atravesar la ruta. En este caso IPv4 (o incluso UDP) funciona como una especie de capa de enlace entre nodos IPv6. Las técnicas son variadas según los fabricantes.

También existe el tunneling de IPv4 dentro de IPv6, para equipos que no soportan doble pila, pero se usa mucho menos.

Tunneling automático

En contraposición al tunneling usado para atravesar otras redes, los mecanismos de tunneling automático proveen un mecanismo de transición para conectividad entre nodos IPv4 e IPv6. Se han desarrollado varias técnicas, de las cuales vamos a profundizar en las más extendidas: 6to4 y Teredo.

6to4

Es el método recomendado por el RFC 3056. Se determinan los extremos del túnel mapeando ciertas direcciones IPv4 llamadas anycast (direcciones que representan a determinados nodos dentro de cualquier red, es decir, obvian la parte netid de la dirección).

Este sistema tiene la ventaja de que no necesita la colaboración de los proveedores de Internet. Funciona automáticamente sobre la red IPv4. Sólo es necesario que el router que da acceso a la red soporte el uso del prefijo especial 2002::/16.

Cuando un paquete IPv4 entra en la red IPv6, el router convierte su dirección IP a una con el prefijo 2002::/16. A la salida de la red, la dirección se puede volver a convertir a su forma original.

Una buena pregunta que tienes que estar haciéndote es qué podemos hacer si la dirección de destino es IPv6 y no se puede convertir a IPv4. En ese caso, el paquete se envía a la dirección anycast 192.88.99.1. En el otro extremo de la red, confiamos en que algún router esté escuchando esa dirección y pueda encontrar al destino.

Un inconveniente importante de este mecanismo es que la dirección IP del nodo que envía el paquete no puede ser privada (colisionaría con cualquier otra en la red de destino). 

Teredo

Teredo es un mecanismo de tunneling que no necesita que la dirección origen sea pública, lo que lo hace más universal.

En este caso se utiliza UDP como medio de encapsulamiento. Tiene la ventaja sobre 6to4 de poder atravesar enrutadores que estén usando NAT (un mecanismo de traducción de direcciones entre redes que explicamos en otro artículo de esta serie).
Los equipos Windows (a partir de Vista) incluyen ambas técnicas por defecto. Los equipos Linux sólo incorporan 6to4 por defecto y Teredo se puede instalar aparte.

TCP/IP (12): El deseado IPv6

¿POR QUÉ IPv6?

En el anterior artículo, hablamos del agotamiento de las direcciones IP y de las piruetas que han tenido que hacerse para mantener el viejo IPv4 en funcionamiento. 

IPv4 se desarrolló a finales de la década de los 1970 para el Ministerio de Defensa de EEUU, y se publicó en 1980 como RFC 760. La fortaleza de su diseño ha hecho que durante décadas siga siendo la base de prácticamente todas las comunicaciones no sólo en Internet, sino incluso en redes locales e intranets. Pocos desarrollos tecnológicos en la historia han sido tan exitosos y se han mantenido sin cambios por tanto tiempo. Sin embargo, el tamaño de su espacio de direcciones se ha mostrado insuficiente ante el boom que ha sufrido Internet. Esta situación ya era preocupante a principios de este siglo.

Mucho antes, a finales del siglo XX, la IETF se puso a trabajar en una nueva versión de IP. Se llamó IPv6 porque el número de versión 5 ya se había usado para un protocolo orientado a conexión, complementario de IPv4, que no llegó a cuajar.

Hay que tener claro que la adopción de IPv6 es la única solución que va a permitir a Internet seguir desarrollándose. Por tanto, su uso generalizado solo es cuestión de tiempo, a pesar de la lentitud y poco entusiasmo con los que ha ido siendo adoptado por los proveedores de Internet.

NUEVO ESPACIO DE DIRECCIONES

El espacio de direcciones que introduce IPv6 es de 128 bits, frente a los 32 de IPv4. La cantidad de direcciones posibles que surge de esta longitud no sólo es suficiente para cualquier uso futuro, sino que resulta inimaginable para la mente humana. Sólo decir que en este espacio hay varios miles de cuatrillones de direcciones para cada persona del planeta.

Esta enorme extensión en el espacio de direcciones no es arbitraria, sino que ha sido pensada más allá de evitar el simple agotamiento. La idea es que, usando este espacio tan amplio, sea posible desarrollar mecanismos de rutado mucho más eficientes. Las técnicas de agregación de rutas permitirán que diferentes partes de Internet puedan usar prefijos comunes de manera estructurada.

NOTACIÓN DE DIRECCIONES

Lógicamente, al aumentar tanto de tamaño, la forma de representar los dígitos de las direcciones debe cambiar con respecto a IPv4. La representación común es de números hexadecimales de 16 bits cada uno, separados por el signo de dos puntos (:). Se forman, por tanto, ocho grupos con cuatro dígitos hexadecimales cada uno. Por ejemplo:

3ffe:1900:4545:3:200:f8ff:fe21:67cf

Los ceros a la izquierda en cada grupo no se escriben. Las letras hexadecimales se escriben en minúsculas por convención.

Dado que esta notación aún es incómoda de usar por su longitud, se permite abreviarla usando ciertas convenciones:

Los grupos de ceros consecutivos se pueden omitir colocando dos veces los dos puntos en su lugar. Por ejemplo:

fe80:0:0:0:200:f8ff:fe21:67cf

se puede abreviar a 

fe80::200:f8ff:fe21:67cf

Si hay más de una secuencia de ceros, se abreviará la más larga de ellas, pero nunca más de una. Esto es para evitar representaciones ambiguas. Por ejemplo:

fe80:0:0:0:200:0:0:67cf

se abrevia a 

fe80::200:0:0:67cf

pero NO se puede escribir:

fe80::200::67cf

Si las secuencias de ceros a abreviar son de igual longitud, se elige la que está más a la izquierda. Por ejemplo:

fe80:0:0:1:200:0:0:67cf

se abrevia a 

fe80::1:200:0:0:67cf

Usando este tipo de notación, es muy simple escribir las típicas direcciones de loopback (::1 por 0:0:0:0:0:0:1) e inespecificada (:: por 0:0:0:0:0:0:0:0). 

Sin embargo, surgen problemas para integrar las direcciones en protocolos preexistentes, que usan los dos puntos para otros fines. Concretamente, para las URL (localizador universal de recurso) e URI (identificador universal de recurso), es necesario usar corchetes para delimitar la dirección IPv6. Por ejemplo:

http://[3ffe:1900:4545:3:200:f8ff:fe21:67cf]/index.html

En los localizadores de tipo UNC (convención uniforme de nombres), propio de los protocolos de Microsoft, la solución adoptada es usar un dominio DNS específico (ipv6-literal.net), cambiando además los símbolos de dos puntos (: y ::) por guiones (- y  --). Por ejemplo;

3ffe-1900--f8ff-fe21-67cf.ipv6-literal.net

Aunque éste es un dominio real registrado por Microsoft, las direcciones normalmente son resueltas por el propio software sin necesidad de llamadas a los servidores DNS.

CARACTERÍSTICAS NUEVAS EN IPv6

Aparte de la ampliación del espacio de direcciones, el nuevo protocolo lógicamente incorpora nuevas funcionalidades, así como correcciones de problemas que se han ido detectando en su antecesor:

- Redefinición de multicast y broadcast

En IPv6 se redefine el funcionamiento del multicast (envío de paquetes a varios nodos) y el broadcast (envío de paquetes a todos los nodos). En realidad se unifican ambos conceptos, los cuales tenían en IPv4 diferentes mecanismos. En IPv6 se solucionan muchas de las dificultades que había para implementar emisiones multicast. Por ejemplo, la adaptación entre las direcciones de unicast (punto a punto) y multicast es automática por el diseño, sin necesidad de los complejos mecanismos de IPv4. Cualquier dirección IPv6 tiene asignada por sí misma, sin configuración adicional, un conjunto amplio de direcciones multicast usables globalmente.

Una de esas direcciones multicast predefinidas es precisamente la de "todos los nodos" (ff02::1), equivalente a la tradicional dirección de broadcast (255.255.255.255).

- Nuevas funciones de autoconfiguración

Aparte de las tradicionales configuraciones manuales o dinámicas (DHCPv6), los nodos pueden autoconfigurarse usando un mecanismo más avanzado basado en el protocolo ICMPv6. En él, los propios encaminadores de la red informan en todo momento de los parámetros de la red y enrutado disponible, mediante la llamada autoconfiguración de direcciones sin estados (SLAAC).

- Seguridad "de serie"

Los protocolos de encriptación y autenticación IPsec, opcionales en IPv4, están ahora implementados obligatoriamente.

- Enrutamiento más ágil

Las cabeceras de los paquetes IPv6 están rediseñadas para acelerar el procesamiento en los enrutadores. Esto se consigue aún cuando el tamaño de las cabeceras sea que las de IPv4, mediante un diseño más eficiente:

• Los campos que se usan raramente se mueven a extensiones opcionales de la cabecera.
• No se admite la fragmentación de paquetes en ruta. 
• Los paquetes sólo se pueden fragmentar de extremo a extremo, usando una técnica de descubrimiento del tamaño máximo del camino (PMTU discovery).
• Se elimina la redundancia en el control de errores (checksum). La integridad es competencia de las otras capas de red (enlace y/o transporte). Es innecesario que la capa IP tenga que calcular también el checksum.
• El concepto de TTL (tiempo de vida) se rediseña a uno más lógico de límite de saltos (hop limit).
• Se incorpora el concepto de jumbogramas (paquetes de hasta 4 gigabytes de tamaño) para aplicaciones específicas.

TCP/IP (11): Agotamiento de direcciones IP

Las organizaciones que asignan las direcciones IP.

A pesar de lo flexible y adaptable que se ha mostrado la especificación IP a lo largo de los años, existe un aspecto que los diseñadores originales no fueron capaces de prever: el extraordinario crecimiento que ha sufrido Internet en el número de nodos conectados.

Cuando se diseñó el estándar TCP/IP, la informática estaba dominada por mainframes y casi no existían los ordenadores personales. El espacio de direcciones se diseñó para números del orden de cientos de redes con miles de nodos. Con la invasión posterior de los ordenadores personales, los móviles inteligentes y todo tipo de dispositivos, se ha creado una demanda de direcciones del orden de miles de redes con millones de nodos.

Aparte del problema que acarrea el crecimiento de las tablas de rutado de las pasarelas, provocando un esfuerzo de procesamiento adicional, el principal escollo es el agotamiento del espacio de direcciones. El esquema original de direcciones no puede incorporar el número de redes que actualmente hay en funcionamiento.

Por tanto, dentro del ámbito del protocolo IPv4 (el más usado) ha sido necesario crear nuevos mecanismos de rutado que permitan compartir direcciones de red entre varias redes físicas. Concretamente, la mayor escasez de direcciones está en las redes medianas de tipo B, las cuales han ido adoptando direcciones tipo C o A a base de compartir el espacio de tipo B con otras redes parecidas. 

Por otra parte, existe una nueva forma de direccionamiento propio de la versión IPv6 que termina con esas limitaciones. Sin embargo, la compatibilidad con este protocolo se ha retrasado mucho. Incluso bastante entrado el siglo XXI todavía el uso de direcciones IPv6 sigue sin estar completamente implantado. Las razones de este retraso serían motivo de otro artículo.

El fundamento de la reorganización de direcciones IPv4 es el principio que establece que cada red tiene libertad de modificar las direcciones y rutas, siempre que dichas modificaciones permanezcan ocultas para las demás localidades. Esto ha dado lugar a una serie de técnicas de rutado independientes entre sí, que dan solución a la reutilización de direcciones de red. 

TÉCNICAS PARA MINIMIZAR LAS DIRECCIONES DE RED

Traducción de direcciones (NAT)

La técnica denominada traducción de direcciones o NAT (Network Address Translation) es la que nos permite, por ejemplo, conectar muchos dispositivos en casa, pero contratando sólo una dirección IP con el proveedor de Internet. También se usa en redes corporativas de tamaño medio.

La forma en que esta técnica ahorra direcciones IP es parecida a la de una centralita de teléfonos, donde un mismo número externo da acceso a muchas extensiones internas.

El funcionamiento de NAT recuerda al de las centralitas telefónicas.

En una red de este tipo, los nodos dentro de la red tienen asignadas direcciones IP privadas, que están en unos rangos que por convención no son enrutables en la red de redes. Estas direcciones son:

- Todas las que empiezan por 10 (clase A).
- De 172.16 a 172.31 y 169.254 (clase B).
- Todas las que empiezan por 192.168 (clase C).

Cuando un paquete sale de la red, el router sustituye la dirección IP privada por otra externa, de manera que el paquete puede seguir su camino por Internet.

Pero surge un problema. Los paquetes que salen tienen vía libre, pero ¿y los que vienen de vuelta? Si muchas direcciones privadas usan la misma IP pública ¿cómo sabe el router colocar de nuevo la dirección correcta? Para ello necesita mantener una tabla donde lleva la cuenta de las conexiones y sus destinatarios, igual que haría una eficiente operadora en la centralita de teléfonos.

En routers baratos es común que el tamaño de la tabla de NAT sea pequeño, alguna vez pasará que se agote y tengamos que apagar y encender el router. Ya sabéis, la solución a todos los problemas.

Una limitación importante de la NAT es que sólo funciona con transparencia cuando las conexiones se originan en el interior. Si un nodo de Internet intenta abrir conexión con un nodo interno, no va a poder porque su dirección es privada. La solución es abrir un puerto del router, asignando que todo el tráfico que venga por ese puerto vaya a un nodo específico. En las redes domésticas es común tener que abrir puertos para los juegos en red, incluso tener que configurarlos manualmente.

Pasarelas transparentes

Esta solución se basa en ahorrar direcciones tipo B a base de integrar redes medianas en el espacio de direcciones de otras redes tipo A.

Se trata de una multiplexación de direcciones a través de nodos dedicados que despachan a toda una red local a partir de una red ámplia tipo A. La pasarela transparente se encarga de que los nodos de la red local puedan comunicarse con la WAN como si realmente estuvieran conectados a ella. De esta manera, la LAN funciona integrada en la red ámplia sin ocupar una dirección de red propia.

La pasarela se llama transparente porque ni los nodos de la LAN ni de la WAN se dan cuenta de su existencia. Estas pasarelas no ofrecen todos los servicios convencionales y, por ejemplo, no responden a las peticiones de eco ping.

Proxy ARP

El proxy ARP (también llamado ARP sustituto, ARP promiscuo y ARP hack) es una forma de que varias redes físicas medianas compartan la misma dirección de red. Además de ésta, tiene utilidad en otras situaciones.

Por ejemplo, es muy común que un determinado entorno físico se subdivida en subredes sólo por conveniencia administrativa, sin que existan verdaderas separaciones físicas (p.e. cuando se usan bridges en vez de gateways) quedando la red en una estructura transparente.También puede pasar que los nodos no tengan capacidad para mantener sus tablas de rutas, o para responder adecuadamente a las redirecciones, o no soporten un sistema de subredes. En todos estos casos, se deben enviar los datagramas como si todo fuese una misma red.La forma de gestionar estas subredes "virtuales" es precisamente desmontando el sistema de ruteo de la red de redes. Los nodos no harán distinción alguna en las direcciones; todas serán consideradas como accesibles directamente.

Esto supone un problema: si se está considerando que cualquier dirección es accesible directamente en la red, ¿cómo comunicarse con las redes que están fuera de ésta? ¿Cómo diferenciar unas direcciones de otras? Para solucionar éste problema, las pasarelas deben soportar una versión del protocolo ARP llamada proxy ARP.

El proxy ARP se basa en un "truco" consistente en engañar a los nodos, haciéndoles creer que se trata de una sóla red , mientras que las pasarelas sí conocen que la red está estructurada en redes físicas. Esto se consigue proporcionando una máscara ficticia a los nodos, y otra real a las pasarelas. Así, los datagramas dirigidos al exterior serán manejados correctamente por las pasarelas, mientras que los internos serán enviados directamente.

Para usar el proxy ARP debe tenerse en cuenta dos precauciones:

* Se debe desactivar los mensajes ICMP de petición de máscara. La existencia de dos máscaras distintas crearía confusión, pues ni los nodos ni las pasarelas deben conocer otra máscara además de la suya.

* Los nodos que tengan más de una interfaz (p.e. con otra red aparte) deben conocer la máscara real, pues tienen que saber qué interfaz usar en cada caso.

Por ejemplo, el ordenador A (128.6.4.2) quiere comunicarse con el B (128.6.3.12), pero no sabe que éste se encuentra en otra red, pues le engaña la máscara ficticia (255.255.0.0). Por tanto, en vez de buscar en la tabla de rutas la pasarela adecuado, envía un mensaje ARP: "¿podría el nodo 128.6.3.12 enviarme su dirección Ethernet?". Por supuesto, ese nodo nunca lo oirá, pues está en otra red. El único que lo sabe es la pasarela, que, al oír la pregunta, contesta haciéndose pasar por el destinatario: "Soy yo; mi dirección es 2:E0:0:CD:1". Esa dirección es en realidad la del propio gateway, que se encargará luego de reenviar el datagrama a su verdadero destino. Mientras tanto, el "engañado" nodo A dejará registrada en su tabla ARP la dirección de la pasarela como si fuese la del nodo B. A partir de ahora todo lo que mande allí pasará por la pasarela.

El efecto es el mismo que si el nodo ampliase su tabla de rutas. El control de rutado ha pasado a nivel de la tabla ARP. Los nodos que funcionan así se ven descargados del trabajo de mantener una tabla de rutas.

Los inconvenientes del Proxy ARP son principalmente dos:

* Sólo se puede usar en instalaciones que usan ARP para la resolución de direcciones (normalmente las Ethernet).

* Tiene un agujero de seguridad, pues permite la técnica llamada spoofing, consistente en que un nodo indica ser otro para interceptar datagramas. El software de monitorización contra esta técnica no puede coexistir con el Proxy ARP, pues generaría alertas con gran frecuencia.

Direccionamiento de subred (subnetting)

Jon Postel, uno de los creadores de las subredes IP.

Esta técnica es una de las más extendidas, y se ha incluido como parte de los estándares TCP/IP.

Consiste en compartir una dirección de red tipo B entre varias redes, subdividiendo internamente el espacio como si fueran de tipo C. Esto se consigue subdividiendo la parte hostid de las direcciones tipo B de tal manera que parte de él identifique a las subredes.

Este cambio sólo afecta ligeramente a la interpretación de las direcciones IP; es por ello que se ha extendido como un estándar.

Este tipo de direccionamiento jerárquico lleva también a un rutado jerárquico. El resto de Internet ve todo el conjunto como una sola red tipo B, sin fijarse en la subdivisión del campo hostid. De esta manera se cumple la norma de que el rutado desde el exterior no se debe ver afectado. Todo el tráfico externo se concentra en uno varios puntos desde donde se despacha según el campo de subred (segundo nivel de jerarquía).

Una gran ventaja de este tipo de direccionamiento es que la ruta no necesita saber muchos detalles sobre los destinos distantes. Un inconveniente es lo difícil que resulta cambiar a posteriori una jerarquía de este tipo ya establecida.

El algoritmo de rutado se ve modificado por el uso de direcciones de subred. El uso del rutado de subred ha de cumplir dos reglas:

1) Se debe usar el rutado de subred entre M y N, a no ser que exista un solo camino más corto entre M y cualquier red física que sea subred de N.

2) Todas las subredes bajo una misma dirección de red deben ser contiguas (estar conectadas físicamente entre ellas), las máscaras deben ser uniformes en todas ellas y todas las máquinas deben usar el rutado de subred.

En el algortimo estándar de rutado, se conoce siempre el formato de las direcciones, pues los primeros tres bits de cada dirección codifican el tipo de red (A, B, C o D). En el rutado de subred esto no es posible, por lo que es necesaria la presencia de un campo en las tablas de rutado con la máscara de subred. Por tanto, las tablas de rutas deben tener al menos tres campos: máscara, dirección de red y dirección de salto siguiente.

Direccionamiento de superred

Una técnica totalmente diferente para evitar el agotamiento del espacio de direcciones es la llamada CIDR (Classless Inter-Domain Routing, rutado sin tipo entre dominios), donde se agrupan un conjunto de redes de tipo C contiguas en un registro de dos campos compuesto por la dirección más pequeña del grupo y un conteo del número de direcciones que lo componen.

P. ej. el registro {192.5.48.0, 3} identifica el grupo de direcciones 192.5.48.0, 192.5.49.0 y 192.5.50.0.

En la práctica, este sistema se modifica un poco, requiriendo que cada grupo de direcciones sea potencia de dos y usando una máscara de bits para identificar el tamaño del grupo, en lugar del conteo.

P. ej. el rango de direcciones entre 234.170.168.0 y 234.170.175.255 genera la máscara de bits 255.255.248.0, poniendo a 1 los bits que coinciden en todas las direcciones del grupo. Las pasarelas en las redes que usen este sistema han de tener un software de rutado especial para CIDR.