TEMA 4.

La capa de red

4.1. Introducción
La capa de red de un host emisor toma segmentos de la capa de transporte, encapsula cada segmento en un
datagrama (un paquete de la capa de red) y, a continuación, envía los datagramas al router más próximo. En el host
de recepción, la capa de red recibe los datagramas de su router más próximo, extrae los segmentos de la capa de
transporte y los entrega a la capa de transporte del host receptor. La función principal de los routers es reenviar los
datagramas desde los enlaces de entrada hasta los enlaces de salida.

4.1.1. Reenvío y enrutamiento

La función de la capa de red es transportar paquetes desde un host emisor hasta un host receptor. En esta tarea se
pueden identificar dos importantes funciones: el reenvío (forwarding) -cuando un paquete llega al enlace de entrada
de un router, este tiene que pasar el paquete al enlace de salida apropiado- y el enrutamiento (routing) -la capa de
red tiene que determinar la ruta que deben seguir los paquetes, mediante los llamados algoritmos de enrutamiento-.
El reenvío hace referencia a la acción local que realiza un router, mientras el enrutamiento es un proceso que realiza
la red en conjunto.
Todo router tiene una tabla de reenvío, que usa para determinar el enlace de salida al que tiene que mandar un
paquete en función de su cabecera. Será el algoritmo de enrutamiento el que determine los valores que se introducen
en las tablas de reenvío de los routers. Estos algoritmos pueden estar centralizados o descentralizados, como se verá
más adelante.
***Configuración de la conexión: existe esta tercera función de la capa de red, mediante la cual algunas arquitecturas
de la capa de red requieren que los routers a lo largo de la ruta seleccionada negocien entre sí para configurar el
estado antes de que puedan comenzar a fluir los paquetes de datos.

4.1.2. Modelos de servicio de red

El modelo de servicio de red define las características del transporte terminal a terminal de los paquetes entre el
emisor y el receptor. Algunos de los servicios que podría proporcionar la capa de red serían: la entrega garantizada,
entrega garantizada con retardo limitado, entrega de los paquetes en orden, ancho de banda mínimo garantizado,
fluctuación máxima garantizada -mismo intervalo de tiempo entre dos paquetes sucesivos transmitidos por el emisor
que entre su respectiva recepción en el destino-, servicios de seguridad -con una clave secreta solo conocida por los
hosts de origen y destino se cifra la carga útil de todos los datagramas-.
Sin embargo, la capa de red de Internet proporciona un único servicio conocido como servicio de mejor esfuerzo
(best-effort service). Con este servicio, la temporización relativa entre paquetes no está garantizada, tampoco que
estos se reciban en orden, ni siquiera se garantiza la entrega. Pero esto tiene razones válidas, como se verá más
adelante.
Por otra parte, otras arquitecturas han implementado modelos de servicio más allá del servicio de mejor esfuerzo,
como la arquitectura ATM, cuyos modelos de servicio más importantes son CBR (Constant Bit Rate) y ABR (Available
Bit Rate). CBR fue el primero en ser estandarizado y su objetivo es proporcionar un flujo de paquetes mediante un
conducto virtual tal que se garantice el retardo terminal a terminal, la variabilidad y la porción de pérdidas o retardos,
todo ello previamente especificado al establecer la conexión. Por su parte, con ABR si pueden tener lugar pérdidas,
pero no pueden reordenarse y garantiza la velocidad mínima; además, proporciona una realimentación que permite
que el emisor ajuste dicha velocidad mínima.
4.2. Redes de circuitos virtuales y de datagramas
Una capa de red también puede proporcionar un servicio con conexión o sin conexión, aunque no ambos a la vez. Las
redes de computadores que proporcionan un servicio del primer tipo se denominan redes de circuitos virtuales (VC),
mientras que en el segundo caso se llaman redes de datagramas.

4.2.1. Redes de circuitos virtuales

Muchas arquitecturas de redes alternativas (como ATM) utilizan conexiones en la capa de red, denominadas circuitos
virtuales. Un circuito virtual consta de una ruta entre los hosts de origen y destino; números de VC, un número para
cada enlace a lo largo de la ruta; y entradas en la tabla de reenvío de cada router existente a lo largo de la ruta. Un
paquete que pertenece a un circuito virtual transportará un número de VC en su cabecera. Dado que un circuito virtual
puede tener un número de VC diferente en cada enlace, cada router interviniente tiene que sustituir el número de VC
de cada paquete que le atraviesa por un nuevo número de VC. Este nuevo número de VC se obtiene de la tabla de
reenvío.
Cuando se configura un número de VC nuevo en un router, se añade una entrada a la tabla de reenvío. De igual forma,
cuando un VC termina, las entradas apropiadas de cada tabla a lo largo de la ruta se eliminan. El hecho de que en nºVC
del paquete varíe en cada router se debe a que de esta manera se simplifica considerablemente la configuración del
VC permitiendo un nºVC diferente en cada enlace a lo largo de la ruta.
En una red de circuitos virtuales, los routers tienen que mantener información de estado de la conexión para las
conexiones activas: se añade y se elimina una nueva entrada en la tabla de reenvío del router con cada creación y
liberación de una conexión. En este tipo de redes existen tres fases diferenciables:
1- Configuración del VC: la capa de transporte del emisor contacta con la capa de red, especifica la dirección del
receptor y espera a que la red configure el circuito, determinando la ruta para el paquete y el nºVC para cada
enlace de la misma, añadiendo las consiguientes entradas a las tablas de reenvío pertinentes.
2- Transferencia de datos: una vez establecido el circuito virtual, los paquetes comienzan a fluir.
3- Terminación del VC: cuando el emisor (o el receptor) le dice a la capa de red que quiere terminar el circuito
virtual, la capa de red informará al otro lado de la red de la terminación de la llamada y actualizará las tablas
de reenvío de cada uno de los routers de la ruta, indicando que ese circuito virtual y no existe.
Los mensajes que los sistemas terminales envían a la red para iniciar o terminar un VC y los mensajes pasados entre
los routers para configurar el VC se conocen como mensajes de señalización y los protocolos empleados para
intercambiar estos mensajes a menudo se denominan protocolos de señalización.

4.2.2. Redes de datagramas

En una red de datagramas, cada vez que un sistema terminal desea enviar un paquete marca el paquete con la
dirección del sistema terminal de destino y luego introduce el paquete en la red. Cuando un paquete llega a un router,
este utiliza la dirección de destino del paquete para buscar la interfaz del enlace de salida apropiado en la tabla de
reenvío. Después, el router reenvía intencionadamente el paquete a esa interfaz del enlace de salida.
Todas las direcciones de destino tienen una longitud de 32 bits. Con este tipo de tabla de reenvío, el router busca la
coincidencia de un prefijo de la dirección de destino del paquete con las entradas de la tabla; si existe una coincidencia,
el router reenvía el paquete a un enlace asociado con esa coincidencia. Cuando existen varias coincidencias, el router
aplica la regla de coincidencia con el prefijo más largo; es decir, busca la entrada más larga de la tabla con la que
exista una coincidencia y reenvía el paquete a la interfaz de enlace asociada con el prefijo más largo.
En una red de datagramas las tablas de reenvío son modificadas por los algoritmos de enrutamiento, normalmente
actualizándolas en intervalos de uno a cinco minutos. En una red de circuitos virtuales este proceso puede tener lugar
en intervalos del orden de microsegundos.
4.2.3. Orígenes de las redes de circuitos virtuales y de datagramas
La idea de un circuito virtual como principio de organización central tiene sus raíces en el mundo de la telefonía. Al
mantenerse la configuración y el estado de las llamadas en los routers de la red, una red de circuitos virtuales es
indiscutiblemente más compleja que una red de datagramas.
Por otro lado, Internet, como red de datagramas, creció a partir de la necesidad de conectar computadoras entre sí.
Con dispositivos terminales sofisticados, los arquitectos de Internet prefirieron hacer que el modelo de servicio de la
capa de red fuera lo más simple posible. Esto tiene consecuencias interesantes: puesto que el modelo impone unos
requisitos mínimos a la capa de red, esto hace que sea más fácil interconectar redes que utilizan tecnologías en la capa
de enlace muy diferentes; y la capacidad de añadir un nuevo servicio simplemente conectando un host a la red y
definiendo un nuevo protocolo de la capa de aplicación ha permitido a las nuevas aplicaciones implantarse en Internet
en un periodo de tiempo muy corto.

4.4. Protocolo de Internet (IP): reenvío y direccionamiento

Actualmente hay dos versiones en uso de IP: IPv4 e IPv6, este último propuesto para sustituir al primero. A
continuación, se estudiará IPv4.

4.4.1. Formato de los datagramas

-Nº de versión (4bits): especifica la versión del protocolo IP del datagrama, para saber cómo debe interpretarse el
resto de la información, ya que las distintas versiones de IP utilizan diferentes formatos de datagrama.
-Longitud de cabecera (4bits): determina dónde comienza realmente los datos del datagrama IP. La mayoría de
datagramas no contienen opciones, por lo que el datagrama IP típico tiene una cabecera de 20 bytes.
-Tipo de servicio: distinguen varios tipos de
datagramas (bajo retardo, alta tasa de
transferencia…)
-Longitud del datagrama (16 bits)
-Identificador, indicadores, desplazamiento de
fragmentación: tienen que ver con la
fragmentación IP, estudiada en apartados
posteriores. Ipv6 no permite la fragmentación en
los routers.
-Tiempo de vida (TTL): su fin es garantizar que los
datagramas no estarán eternamente en
circulación por la red. Se decrementa en una
unidad cada vez que un router procesa un
datagrama; al llegar a 0, el datagrama tiene que
ser descartado.

-Protocolo: solo se emplea cuando un datagrama IP alcanza su destino final, indicando el protocolo específico de la
capa de transporte (por ejemplo, 6 para TCP y 17 para UDP).
-Suma de comprobación de cabecera: se calcula tratando cada pareja de 2 bytes de la cabecera como un número y
sumando dichos números utilizando aritmética de complemento a 1. Un router calcula la suma de comprobación de
cabecera para cada datagrama IP recibido y detecta una condición de error si la suma de comprobación incluida en la
cabecera del datagrama no coincide con la suma de comprobación calculada. Normalmente, los routers descartan los
datagramas en los que se ha detectado que existe un error. Observe que la suma de comprobación tiene que volver a
calcularse y almacenarse en cada router, ya que el campo TTL y, posiblemente, también el campo de opciones
puedencambiar.
 ¿Por qué llevar a cabo una comprobación de errores tanto en la capa de transporte como en la capa de red?
En la capa IP solos se calcula la suma para la cabecera IP, mientras que en el caso de TCP/UDP se calcula sobre el
segmento completo. Además, TCP/UDP e IP no necesariamente tienen que pertenecer a la misma pila de protocolos,
por lo que se pueden estar manejando datos que no vayan a pasar de uno a otro.

-Direcciones IP de origen y destino.

-Opciones: fueron omitidas en IPv6, ya que complicaban el protocolo.

-Datos (carga útil).

Fragmentación del datagrama IP

No todos los protocolos de la capa de enlace pueden transportar paquetes de la capa de red del mismo tamaño (por
ejemplo, las tramas Ethernet pueden transportar hasta 1500 bytes). La cantidad máxima de datos que una trama de
la capa de enlace puede transportar se conoce como unidad máxima de transmisión (MTU, Maximum Transmission
Unit).
La solución consiste en fragmentar los datos del datagrama IP en dos o más datagramas IP más pequeños,
encapsular cada uno de los datagramas IP más pequeños en una trama de la capa de enlace distinta y enviar dichas
tramas a través del enlace de salida. Cada uno de estos datagramas más pequeños se conocen como fragmentos. Los
fragmentos tienen que ser reensamblados antes de llegar a la capa de transporte del destino. Los diseñadores de IPv4
decidieron dar el trabajo de reensamblar los datagramas a los sistemas terminales en lugar de a los routers de red.
Cuando un host de destino recibe una serie de datagramas procedentes del mismo origen, tiene que
determinar si alguno de esos datagramas son fragmentos de algún otro datagrama original más grande. Si algunos
datagramas son fragmentos, tiene que determinar además cuándo ha recibido el último fragmento y cómo debe
ensamblar los fragmentos que ha recibido para formar el datagrama original. Para que el host de destino pueda llevar
a cabo estas tareas de reensamblado, se incluyeron los campos identificación, indicador y desplazamiento de
fragmentación en la cabecera del datagrama IP. Cuando un router necesita fragmentar un datagrama, cada datagrama
resultante (es decir, cada fragmento) se marca con la dirección de origen, la dirección de destino y el número de
identificación del datagrama original. Cuando el destino recibe una serie de datagramas procedentes del mismo host
emisor, puede examinar los números de identificación de los datagramas para determinar cuáles de ellos son
fragmentos de un mismo datagrama más largo.
Puesto que IP es un servicio no fiable, es posible que uno o más de los fragmentos nunca lleguen a su destino.
Por esta razón, con el fin de que el host de destino esté absolutamente seguro de que ha recibido el último fragmento
del datagrama original, el último fragmento tiene un bit indicador puesto a 0, mientras que los demás fragmentos
tienen el bit indicador puesto a 1. Además, para que el host de destino determine si falta un fragmento (y también
para que pueda reensamblar los fragmentos en el orden apropiado), se utiliza el campo desplazamiento (especificado
en unidades de fragmentos de 8 bytes) para especificar en qué posición dentro del datagrama IP original encaja el
fragmento.

4.4.2. Direccionamiento IPv4

Puesto que todos los hosts y todos los routers son capaces de enviar y recibir datagramas IP, IP requiere que cada
interfaz (límites enlace-host o enlace-router) tengan su propia dirección IP. Por tanto, técnicamente, una dirección IP
está asociada con una interfaz. Las direcciones IP tienen 32 bits, y normalmente se expresan utilizando la notación
decimal con punto, en la que cada byte se escribe en formato decimal y se separa mediante un punto del resto.
Cada interfaz debe tener una dirección IP única, aunque una parte de esta estará determinada por la subred a la que
está conectada. En la notación [Link]/yy, /yy se denomina máscara de subred e indica que los yy bits más a
la izquierda define la dirección de subred.
La estrategia de asignación de direcciones en Internet se conoce como Enrutamiento entre dominios sin clase (CIDR,
Classless Interdomain Routing). Según esta estrategia, la dirección IP a.b.c.d/x se divide en dos partes, donde la
primera viene dada por los primeros x bits. Los x bits más significativos constituyen la parte de red, comúnmente
denominada prefijo. Normalmente una organización tiene asignado un bloque se direcciones contiguas. Los 32-x bits
restantes pueden emplearse para diferenciar los dispositivos internos de la organización.
Antes de adoptarse el enrutamiento CIDR, la parte de red estaba restringida a longitudes de 8, 16 o 24 bits, es quema
conocido como enrutamiento con clases, denominadas respectivamente clase A, B y C.
Existe otro tipo de dirección IP: la dirección IP de difusión [Link]. Cuando un host envía un datagrama con
esta dirección, el mensaje se entrega a todos los hosts existentes en la misma subred.
Cómo obtener un bloque de direcciones
Para obtener un bloque de direcciones IP que puede ser utilizado dentro de una subred, un administrador de red tiene
que contactar en primer lugar con su ISP, el cual le proporcionará direcciones extraídas de un bloque de direcciones
mayor que ya habrá sido asignado al ISP.
Las direcciones IP son gestionadas por la entidad ICANN (Internet Corporation for Assigned Names and Numbers), que
también gestión los servidores raíz DNS.

Cómo obtener una dirección de host: Protocolo de configuración dinámica de host

Una vez que una organización ha obtenido un bloque de direcciones, puede asignar direcciones IP individuales a las
interfaces de sus hosts y routers. Las direcciones de host también se pueden configurar manualmente, pero
frecuentemente ahora esta tarea se lleva cabo utilizando el Protocolo de configuración dinámica de host (DHCP,
Dynamic Host Configuration Protocol). DHCP permite a un host obtener automáticamente una dirección IP. Un
administrador de red puede configurar DHCP de modo que un host dado reciba la misma dirección IP cada vez que se
conecte a la red, o un host puede ser asignado a una dirección IP temporal que será diferente cada vez que el host
se conecte a la red. Además de la asignación de direcciones IP a los hosts, DHCP también permite que un host obtenga
información adicional, como por ejemplo su máscara de subred, la dirección del router del primer salto (a menudo
denominado router de pasarela (gateway) predeterminado) y la dirección de su servidor DNS local. Gracias a la
capacidad de DHCP de automatizar el proceso de conexión de un host a una red, a menudo se dice que es un protocolo
plug-and-play. DHCP es un protocolo en cuatro pasos: descubrimiento del servidor con el que interactuar (emplea la
dirección IP de difusión), oferta del servidor, solicitud y ACK.

Traducción de direcciones de red (NAT)

Un ámbito de direcciones privadas hace referencia a una red cuyas direcciones solo tienen significado para los
dispositivos internos de dicha red. El router NAT se comporta de cara al exterior como un único dispositivo con una
dirección IP única, ocultando los detalles de la red doméstica al mundo exterior. Puesto que todos los datagramas que
reciba vendrán dirigidos a la misma dirección IP, el router NAT almacena una tabla de traducciones NAT en la que
incluye los números de puerto y las direcciones IP de los mensajes que transmite al exterior; así sabe a qué host interno
debe reenviar un datagrama que le llegue del exterior.
Problemas: los nº puerto deberían emplearse para direcciones de procesos, no para hosts; viola el enfoque terminal
a terminal.

UPnP: Universal Plug and Play

Permite a un host descubrir y configurar un traductor NAT próximo.
Requiere que tanto el host como el traductor NAT sean compatibles
con UPnP. UPnP permite a hosts externos iniciar sesiones de
comunicación con hosts conectados a través de un traductor NAT
utilizando TCP o UDP.

4.4.3. Protocolo de mensajes de control de

Internet (ICMP)
Los hosts y routers utilizan ICMP (RFC 792) para intercambiarse
información acerca de la capa de red. El uso más típico es la generación
de informes de error. En sentido arquitectónico, ICMP se encuentra
justo encima de IP, es decir, los mensajes ICMP son transportados
como carga útil de IP. Los mensajes ICMP tienen un campo de tipo y un
campo de código, y contienen la cabecera y los 8 primeros bytes del datagrama IP que ha dado ligar a la generación
del mensaje ICMP, de modo que el emisor puede determinar qué datagrama ha producido el error.
4.4.4. IPv6
El hecho de que el espacio de direcciones IP de 32 bits comenzara a agotarse propició el desarrollo del protocolo IPv6,
con un espacio de direcciones mayor y que aprovechó la oportunidad para ajustar y aumentar otros aspectos de IPv4.

Formato del datagrama IPv6

-Cabecera de 40 bytes.

-No permite la fragmentación.

-Etiqueta de flujo identifica los datagramas

pertenecientes al mismo flujo de datos.

-Siguiente cabecera indica el protocolo de la capa

superior al que se entregará el contenido del datagrama
(mismo código que para IPv4).

Transición de IPv4 a Ipv6

No todos los routers pueden ser actualizados simultáneamente, por lo que se emplea la denominada tunelización.
Supóngase que dos nodos IPv6 quieren comunicarse utilizando datagramas IPv6, pero están conectados entre sí
mediante routers IPv4 (túnel), que no pueden manejar datagramas IPv6. Mediante la tunelización, el nodo IPv6 emisor
toma el datagrama IPv6 completo y lo incluye en el campo de datos de un datagrama IPv4, que seá direccionado a
través del túnel como si fuera cualquier otro datagrama. Una vez el datagrama llega al router IPv6 de destino, este
determinará que el datagrama IPv4 contiene un datagrama IPv6, que será extraído y enrutado exactamente igual que
se hubiera recibido un datagrama IPv6.

4.5. Algoritmos de enrutamiento

Normalmente, un host está conectado directamente a un router, el router predeterminado para el host (router de
primer salto). Nos referiremos al router predeterminado del host de origen como router de origen, y haremos lo
mismo con el denominado router de destino, reduciendo el proceso de enrutamiento de un paquete entre hosts a
hacerlo entre estos routers.

Para formular los problemas de enrutamiento se utilizan grafos. Un grafo G=(N, E) es un conjunto N de nodos y una
colección E de aristas, donde cada arista es una pareja de nodos de N. Una arista también tiene asociado un valor
que representa su coste; en este caso, puede representar la velocidad del enlace, o su coste monetario, por ejemplo.

El proceso de enrutamiento trata de encontrar la ruta de coste mínimo entre el origen y el destino. Para ello, se
emplean los denominados algoritmos de enrutamiento, que atienden a distintas clasificaciones:
-Algor. enrutam. global: utiliza el conocimiento total y completo acerca de la red, disponiendo de toda la información
acerca de la conectividad y de los costes de los enlaces. A menudo se denominan algoritmos de estado de enlaces (LS,
Link-State).
-Algor. enrutam. descentralizado: el cálculo se realiza de manera iterativa y distribuida. Ningún nodo tiene toda la
información acerca de coste de todos los enlaces de la red; en lugar de ello, al principio, cada nodo solo conoce los
costes de sus propios enlaces. Después, a través de un proceso iterativo, cada nodo calcula gradualmente hacia un
destino o conjunto de destinos. Más adelante se verá el algoritmo de vector de distancias (DV, Distance-Vector).
-Algoritmos estáticos o dinámicos: en los primeros las rutas cambian muy lentamente con el tiempo, a menudo por
intervención humana. En el segundo caso, se modifican los caminos de enrutamiento a medida que la carga de tráfico
o la topología de la red cambian.
-Algoritmos sensibles o no sensibles a la carga: en los algoritmos sensibles a la carga, los costes del enlace varían de
forma dinámica para reflejar el nivel actual de congestión del enlace subyacente. De esta forma, si se asocia un coste
alto a un enlace congestionado, el algoritmo intentará evitar dicho enlace.
4.5.1. Algoritmo de enrutamiento de estado de enlaces (LS)
El conocimiento completo de la red se consigue haciendo que cada nodo difunda paquetes del estado de los enlaces
a todos los demás nodos de la red. De esta forma, cada nodo puede ejecutar el algoritmo LS y calcular el mismo
conjunto de rutas de coste mínimo que cualquier otro nodo.
El algoritmo presentado a continuación se conoce como algoritmo de Dijkstra, que calcula la ruta de coste mínimo
desde un nodo origen (al que denominaremos u) hasta todos los demás nodos de la red. Este algoritmo es iterativo y
tiene la propiedad de que después de la k-ésima iteración, se conocen las tutas de coste mínimo hacia k nodos destino
y entre las rutas de coste mínimo a todos los nodos de destino, estas k rutas tendrán los k costes más pequeños.
Algoritmo de estado de enlaces para el nodo de origen u (para N nodos en la red)
N’: subconjunto de nodos cuya ruta de coste mínimo desde el origen es conocida.
D(v): coste de la rutad e coste mínimo desde el origen hasta el nodo v.
Inicialización:
N’ = {u}
for todo nodo v{
if v es un vecino de u
then D(v) = c(u,v)
else D(v) = ∞

Bucle
Encontrar w no perteneciente a N’ tal que D(w) sea un mínimo
Añadir w a N’
Actualizar D(v) para cada vecino v de w, que no pertenezca a N’:
D(v) = min( D(v), D(w) + c(w,v) )
/* el nuevo coste a v es o bien el antiguo coste a v o el coste
de la ruta de coste mínimo a w más el coste desde w a v */
until N’= N

Cuando el algoritmo LS termina, se tiene para cada nodo su predecesor a lo largo de la ruta de coste mínimo desde el
nodo de origen. Para cada predecesor, también se tiene su predecesor, de modo que se puede construir la cuta
completa desde el origen a todos los destinos.
La complejidad de este algoritmo tiene una complejidad O(n2), teniendo que buscar un total de n(n+1)/2 nodos en el
caso más desfavorable.

4.5.2. Algoritmo de enrutamiento por vector de distancias (DV)

Este algoritmo es distribuido -cada nodo intercambia información con sus vecinos directamente conectados-, iterativo
-el proceso continúa hasta que no hay disponible más información para ser intercambiada- y asíncrono -no requiere
que todos los nodos operen sincronizados entre sí-.
Para comprender este algoritmo, es importante comprender una relación importante entre los costes de las rutas de
coste mínimo. Siendo dx(y) el coste de la ruta de coste mínimo desde el nodo x al nodo y, los costes mínimos están
relacionados mediante la ecuación de Bellman-Ford. La solución proporciona las entradas de la tabla de reenvío del
nodo x.
𝑑𝑥 (𝑦) = 𝑚í𝑛𝑣 { 𝑐(𝑥, 𝑣) + 𝑑𝑣 (𝑦) }, 𝑑𝑜𝑛𝑑𝑒 𝑚í𝑛𝑣 𝑠𝑒 𝑐𝑎𝑙𝑐𝑢𝑙𝑎 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜𝑠 𝑙𝑜𝑠 𝑣𝑒𝑐𝑖𝑛𝑜𝑠 𝑑𝑒 𝑣.

Cada nodo x comienza con Dx(y), una estimación de la ruta de coste mínimo desde sí mismo al nodo y, para todos los
nodos de N; el conjunto de estas estimaciones para todos los nodos se denominará vector de distancias del nodo x.
En este algoritmo, cada nodo mantiene la siguiente información: coste c(x,v) , vector de distancias del nodo x y los
vectores de distancias de cada uno de sus vecinos. Cuando un nodo x recibe un nuevo vector de distancias procedente
de cualquiera de sus vecinos, guarda dicho vector y luego utiliza la ecuación anterior para actualizar su propio vector
de distancias. En casa de que este cambie, el nodo x enviará su nuevo vector de distancias a cada uno de sus vecinos.
Algoritmo por vector de distancias (DV) (Se ejecuta en cada nodo x)
Inicialización:
for todos los destinos y pertenecientes a N:
Dx(y) = c(x,y) /* si y no es un vecino, entonces c(x,y) = ∞ */

for cada vecino w

Dw(y) = ? para todos los destinos y pertenecientes a N

for cada vecino w

enviar vector de distancias Dx = [Dx(y): y perteneciente N] a w

Bucle
wait (hasta ver una variación en el coste de enlace de un vecino w
o hasta recibir un vector de distancias de algún vecino w)

for cada y perteneciente a N:

Dx(y) = minv{c(x,v) + Dv(y)}

if Dx(y) varía para cualquier destino y

enviar vector de distancia Dx = [Dx(y): y perteneciente N] a todos los vecinos

forever

Cambios en el coste de los enlaces y fallo de los enlaces

En el caso de que el coste de un enlace disminuya, el algoritmo se ejecuta con normalidad. Sin embargo, cuando el
coste del enlace aumenta surge un problema: se necesitan varias iteraciones para
actualizar correctamente las rutas de coste mínimo (problema de la cuenta hasta
infinito), generando bucles de enrutamiento entre nodos. Para salvar este
inconveniente, puede utilizarse una técnica conocida como inversa envenenada:
si z enruta a través de y para llegar a x, entonces z anunciará a y que su distancia
a x es infinita (aunque esto sea mentira), manteniendo esta “mentira” mientras
continúe enrutando a x a través de y. De esta manera, y creerá que no dispone de
una ruta hacia x, por lo que nunca intentará enrutar hacia x a través de z. Sin
embargo, para bucles que impliquen tres o más nodos esta técnica no es efectiva.
Comparación de los algoritmos LS y DV
-Complejidad del mensaje: LS requiere que todos los nodos conozcan el coste de cada enlace de la red, y un cambio
en dichos costes conlleva anunciarlo a todos los nodos. Por su parte, DV solo necesita que se intercambie la
información entre los vecinos directamente conectados en cada iteración.
-Velocidad de convergencia: LS es de orden O(N2), mientras que DV puede converger muy lentamente y pueden
aparecer bucles de enrutamiento, demás de sufrir también el problema de la cuenta hasta infinito.
-Robustez: con LS, un nodo calcula solo su propia tabla de reenvío, es decir, los cálculos de rutas son algo
independientes entre sí, proporcionando un mayor grado de robustez. Con DV, un nodo puede anunciar rutas de coste
mínimo incorrectas a cualquiera o a todos los destinos.

4.5.3. Enrutamiento jerárquico

Se han estudiado dos algoritmos tomando la red simplemente como una colección de routers interconectados, todos
ellos ejecutando el mismo algoritmo. En la práctica, este modelo de conjunto homogéneo de routers es demasiado
simplista por dos razones: la escala, ya que cuando el número de routers comienza a hacerse grande, la sobrecarga de
aplicar estos algoritmos se hace prohibitiva, y la autonomía administrativa, ya que una organización debería poder
operar y administrar su red como deseara siempre que sea posible conectar su red a otras redes externas.
Estos dos problemas pueden resolverse organizando los routers en sistemas autónomos (AS, Autonomous System),
con cada AS formado por un grupo de routers que normalmente se encuentran bajo el mismo control administrativo,
ejecutando todos ellos el mismo algoritmo y disponiendo de información acerca de ellos. El algoritmo de enrutamiento
que se ejecuta dentro de un AS se conoce como protocolo de enrutamiento interno del sistema autónomo. Por
supuesto, será necesario conectar los AS entre sí, luego uno o más routers (routers gateway o de pasarela) tendrán la
tarea adicional del reenvío de paquetes a los destinos externos.
Para el caso en que el AS de origen tenga dos o más enlaces que le llevan al AS de destino, el primero deberá aprender
qué destinos son alcanzables a través de cada AS y propagar dicha información de alcanzabilidad a todos sus routers,
de manera que cada router pueda configurar su tabla de reenvío para gestionar los destinos externos. Estas dos tareas
son realizadas por el protocolo de enrutamiento entre sistemas autónomos.

4.6. Enrutamiento en Internet

4.6.1. Enrutamiento interno de un sistema autónomo de Internet: RIP
El Protocolo de Información de enrutamiento (RIP, Routing Information Protocol; RFC 1058, 2453) es un protocolo
de vector de distancias que opera de forma muy similar al protocolo DV ideal anteriormente visto. RIP utiliza como
métrica de coste el recuento de saltos, es decir, cada enlace tiene un coste de 1; en RIP los costes se definen realmente
desde el router de origen a una subred de destino, denominando salto al número de subredes que se atraviesan al
seguir la ruta más corta.
El coste máximo está limitado a 15, luego el uso de RIP está limitado a sistemas autónomos con un diámetro de menos
de 15 saltos. El vector de distancias para cualquier router es la estimación actual de la ruta más corta desde dicho
router a las subredes del AS. Cada router mantiene una tabla RIP conocida como tabla de enrutamiento, que incluye
tanto el vector de distancias del router como la tabla de reenvío del mismo.
En RIP, las actualizaciones de enrutamiento son intercambiadas entre los vecinos aproximadamente cada 30s. Por ello,
si un router no tiene noticias de su vecino al menos una vez cada 180s, considera que ese vecino ya no es alcanzable
(o bien ha muerto o bien el enlace ha fallado). En este caso, se modifica la tabla de enrutamiento local y luego se
propaga a los routers vecinos alcanzables.
Los routers se envían entre sí mensajes RIP utilizando UDP en el puerto 520.
Normalmente se implanta en los ISP de nivel inferior y en las redes empresariales.

4.6.2. Enrutamiento interno de un sistema autónomo en Internet: OSPF

El protocolo Primero la ruta abierta más corta (OSPF, Open Shortest Path First; RFC 2328) fue concebido como el
sucesor de RIP, ofreciendo una serie de funcionalidades avanzadas. Básicamente, es un protocolo de estado de enlaces
que utiliza la técnica de inundación de información de estado de los enlaces y el algoritmo de Dijkstra. Un router
construye un mapa topológico completo del sistema autónomo y a continuación ejecuta el algoritmo Dijkstra para
determinar un árbol de rutas más cortas a todas las subredes con él mismo como nodo raíz.
Es el administrador de la red el que configura los costes de los enlaces individuales, por lo que puede decidir hacer
todos los costes igual a 1, proporcionando un enrutamiento en número de saltos, o puede definir los pesos de los
enlaces de manera inversamente proporcional a la capacidad de los mismos, con el fin de disuadir al tráfico de utilizar
los enlaces con ancho de banda menor.
Con OSPF, un router difunde la información de enrutamiento a todos los demás routers del AS, no solo a sus routers
vecinos. Esta difusión se realiza cuando se produce un cambio en el estado de un enlace, o periódicamente (al menos
una vez cada 30min) aunque el estado no haya cambiado.
Los routers se envían entre sí mensajes OSPF transportados directamente por IP, siendo el número del protocolo de
la capa superior igual a 89. Así, OSPF tiene que implementar por sí mismo funcionalidades como la transferencia de
datos fiable.
Entre las funcionalidades avanzadas que presenta OSPF son: su mayor seguridad, ya que permite la autenticación de
los paquetes transmitidos (ya sea por autenticación simple o por MD5); la posibilidad de usar varias rutas de igual
coste; tiene soporte integrado para enrutamiento por unidifusión y por multidifusión; y soporte para definir una
jerarquía dentro de un mismo dominio de enrutamiento.
Respecto al aspecto de la jerarquización, OSPF puede configurarse en áreas que ejecutan su propio algoritmo de
enrutamiento OSPF, con routers de frontera de área para enrutar los paquetes fuera del área, y una única área del AS
que actúa como área troncal, cuya misión es enrutar el tráfico entre las demás áreas del sistema autónomo,
conteniendo a todos los routers de frontera del AS.

4.6.3. Enrutamiento entre sistemas autónomos: BGP

La versión 4 del Protocolo de pasarela de frontera (BGP, Border Gateway Protocol; RFC 4271) proporciona a cada
sistema autónomo mecanismos para obtener información acerca de la alcanzabilidad de las subredes de los AS
vecinos, propagar información de alcanzabilidad a todos los routers internos del sistema autónomo, y determinar
buenas rutas a las subredes basándose en la información de alcanzabilidad y la política del AS. Resumidamente, BGP
permite a cada subred anunciar su existencia al resto de subredes, garantizando que todos los AS sepan que dicha
subred existe y cómo llegar hasta ella.
Fundamentos de BGP
En BGP, las parejas de routers intercambian información de enrutamiento a través de conexiones TCP (puerto 179)
semipermanentes. Normalmente, existe una conexión TCP BGP pata cada enlace que conecta directamente dos
routers que se encuentran en sistemas autónomos diferentes, y también entre los routers internos de un AS. Así, los
extremos de la conexión se denominan pares BGP y a la propia conexión TCP sesión BGP; si abarca dos AS se
denominará sesión externa BGP (eBGP), si se trata de routers del mismo AS, sesión interna BGP (iBGP).
En BGP, los destinos no son hosts sino prefijos CIDR, representando cada prefijo una subred o una colección de
subredes.
Atributos de ruta y rutas BGP
En BGP, un sistema autónomo se identifica mediante su numero de sistema autónomo (ASN, Autonomous System
Number; RFC 1930) globalmente único. Estos números, al igual que las direcciones IP, son asignados por los registros
regionales de la ICANN.
Cuando un router anuncia un prefijo en una sesión BGP, incluye una serie de atributos BGP; un prefijo junto con sus
atributos se denomina ruta. Dos de los atributos más importantes son: AS-PATH, que contiene los ASN de los sistemas
autónomos a través de los que ha pasado el anuncio del prefijo; y NEXT-HOP, que proporciona el enlace crítico entre
el protocolo de enrutamiento interno y el protocolo de enrutamiento entre sistemas autónomos, de manera que el
siguiente salto (NEXT-HOP) es la interfaz de router que inicia la secuencia de sistemas autónomos (AS-PATH).
Cuando un router de pasarela recibe un anuncio de un router, utiliza su política de importación para decidir si aceptar
o filtrar una ruta y si debe definir determinados atributos. La política de importación puede filtrar una ruta porque el
AS puede no querer enviar tráfico a través de uno de los AS de la ruta, o porque ya disponga de una ruta preferible.
Selección de la ruta BGP
Las entradas para el proceso de selección de ruta son todas las rutas que han sido aprendidas y aceptadas por el router.
Si existen dos o más rutas al mismo prefijo, BGP invoca secuencialmente las siguientes reglas de eliminación hasta
quedarse con una ruta:
-Asignación de un valor de preferencia local a las rutas (decisión política), de manera que se eligen las rutas con valores
más altos.
-Selección de la ruta con el camino de sistemas autónomos más corto.
-Selección de la ruta con el router del siguiente salto (NEXT-HOP) más próximo, es decir, para el que el coste de la ruta
de coste mínimo es más pequeño.
-Si aún quedase más de una ruta, se utilizan los identificadores BGP para la selección.
Política de enrutamiento
• Todo el tráfico que entra en una red terminal tiene que estar destinado a dicha red, y todo el tráfico que sale
de una red terminal tiene que haber sido originado en esa red. Para evitar que una red terminal reenvía datos
entre redes troncales, esta anunciará que no tiene ninguna ruta a ningún otro destino excepto a ella misma.
• Cualquier tráfico que fluya a través de la red troncal de un ISP debe tener su origen o su destino (o ambos) en
una red que sea un cliente de dicho ISP; en cualquier otro caso, el tráfico deberá ser expulsado de la red del
ISP. Esto es así para evitar que redes troncales carguen con cargas y costes ajenos a su ISP.

4.7. Enrutamiento por difusión y por multidifusión

En el enrutamiento por difusión, la capa de red proporciona un servicio de entrega para un paquete enviado desde
un nodo de origen a todos los demás nodos de la red; el enrutamiento por multidifusión permite a n único nodo de
origen enviar una copia de un paquete a un subconjunto de los restantes nodos de la red.

4.7.1. Algoritmos de enrutamiento por difusión

El método más simple y directo para llevar a cabo la comunicación por difusión es que el nodo emisor envíe una copia
distinta del paquete a cada destino, denominado unidifusión por N vías. Si bien no se necesita ningún nuevo protocolo
de enrutamiento, ni una duplicación de paquetes ni una funcionalidad de reenvío, este método presenta varios
inconvenientes, como su ineficiencia o la sobrecarga y complejidad añadida por la necesidad de conocer todos los
destinos a priori. Por ello, está claro que serán interesantes otros métodos.
Inundación no controlada

El nodo de origen envía una copia del paquete a todos sus vecinos, y cuando cada uno de estos recibe un paquete de
difusión, lo duplica y lo reenvía a todos sus vecinos (excepto al vecino del que ha recibido el paquete). Aunque esto
presenta varios errores fatales: si el grafo presenta ciclos, entonces una o más copias de cada paquete de difusión
podrían estar dando vueltas indefinidamente; y la posibilidad de multiplicación incesante de paquetes (tormenta de
difusión) podría hacer que la red quede inutilizada.
Inundación controlada
Para evitar una tormenta de difusión, un nodo decide cuándo inundar o no con un paquete. En la práctica, esto puede
hacer de varias formas.
En la inundación controlada por el número de secuencia, un nodo de origen incluye su dirección y un número de
secuencia de difusión en cada paquete de difusión antes de enviarlo. Cada nodo mantiene una lista con la dirección
de origen y el número de secuencia de cada paquete que ha recibido, de tal manera que puede comprobar si ya ha
recibido un paquete, para eliminarlo sí ya lo había recibido con anterioridad.
Un segundo método sería el reenvío por el camino inverso (RPF, Reverse Path Forwarding), en el que cuando un
router recibe un paquete de difusión con una determinada dirección de origen, transmite el paquete solo si este le ha
llegado a través del enlace que pertenece a su propia ruta de unidifusión más corta que lo conecta con el origen; en
otro caso, descarta el paquete, puesto que sabe que ya ha recibido o recibirá una copia de ese paquete a través de
dicha ruta más corta.
Difusión por árbol de recubrimiento

Aunque los métodos de inundación controlada evitan las tormentas de difusión, no evitan completamente la
transmisión de paquetes de difusión redundantes; idealmente, cada nodo tendría que recibir solo una copia. Esto
puede conseguirse haciendo que los nodos de la red construyan un árbol de recubrimiento (no contiene ciclos), en el
que un nodo solo reenviará el paquete de difusión a sus vecinos del árbol de recubrimiento.
La principal complejidad de este método es la creación y mantenimiento del árbol de recubrimiento, para lo que se ha
desarrollado muchos algoritmos. Aquí solo consideraremos un algoritmo simple: el método basado en un nodo
central. Con este algoritmo, se define un nodo central, denominado punto de cita o núcleo, y a continuación, los nodos
envían al nodo central mensajes de unidifusión de unión al árbol. Estos mensajes de unión se renvían hasta que llegan
a un nodo que ya pertenece al árbol, de manera que la ruta que ha seguido el mensaje defina la rama del árbol de
recubrimiento que va desde el centro hasta el nodo arista que inicio el mensaje de unión al árbol.
4.7.2. Multidifusión
En la multidifusión un paquete se entrega a solo un subconjunto de los nodos de la red. Esto presenta dos problemas:
cómo identificar a los receptores y cómo dirigir un paquete a esos receptores; que el emisor conozca las identidades
y direcciones de todos los receptores resultaría inviable.
Por estas razones, en la arquitectura de Internet un paquete de multidifusión se direcciona utilizando la indirección
de direcciones, que utiliza un único identificador para el grupo de receptores, conocido como grupo de multidifusión
(en este caso, el identificador es una dirección IP de multidifusión de clase D). Sin embargo, aún persiste la dificultad
de que cada host tengo una dirección IP de unidifusión única que es completamente independiente de la dirección del
grupo de multidifusión. Además, se plantean un montón de preguntas: ¿cómo se inicia y termina un grupo? ¿Cómo se
elige la dirección de grupo? ¿Cómo se añaden nuevos hosts al grupo?... Todas las respuestas a estas preguntas implican
al Protocolo de gestión de grupos de Internet (IGMP, Internet Group Management Protocol; RFC 3376).
Protocolo de gestión de grupos de Internet (IGMP)
IGMP proporciona los medios a un host para informar a su router conectado (router de primer salto) de que una
aplicación que se ejecuta en el host desea unirse a un grupo de multidifusión especificado. Puesto que el ámbito de
interacción de IGMP está limitado a un host y al router al que está conectado, se requiere otro protocolo para
coordinar a los routers multidifusión a través de Internet: los algoritmos de enrutamiento por multidifusión.
Algoritmo de enrutamiento por multidifusión
El objetivo de estos algoritmos es encontrar un árbol de enlaces que conecte todos los routers que tienen hosts
conectados que pertenecen al grupo de multidifusión; por supuesto, el árbol puede contener routers que no tengan
hosts conectados que pertenecen a este grupo.
El enrutamiento por multidifusión que utiliza un árbol compartido por el grupo está basado en la construcción de un
árbol que incluye todos los routers buscados. En la práctica, se utiliza el método basado en un nodo central para
construir el árbol, siendo los routers de frontera de los hosts pertenecientes al grupo de multidifusión los que inician
los mensajes de unión al árbol.
El enrutamiento por multidifusión utilizando un árbol basado en el origen construye un árbol de enrutamiento por
multidifusión para cada origen existente en el grupo de multidifusión. En la práctica, se utiliza un algoritmo RPF (con
x como nodo de origen) para construir un árbol de reenvío por multidifusión para los datagramas de multidifusión que
tienen su origen en x. El algoritmo RPF estudiado anteriormente necesita un pequeño ajuste: un router multidifusión
que recibe paquetes de multidifusión y que no tiene hosts conectados unidos a dicho grupo enviará un mensaje de
poda a su router inmediatamente anterior; si un router recibe mensajes de poda procedentes de cada uno de los
routers situados por debajo, puede entonces reenviar hacia arriba un mensaje de poda. Esto evitaría la recepción de
mensajes de multidifusión no deseados.

Enrutamiento por multidifusión en Internet

El primer protocolo de enrutamiento por multidifusión utilizado en Internet fue el Protocolo de enrutamiento por
multidifusión por vector de distancias (DVMRP, Distance-Vector Multicast Routing Protocol; RFC 1075), que
implementa árboles basados en el origen, con reenvío de camino inverso y poda.
Quizá el protocolo de enrutamiento por multidifusión más ampliamente utilizado sea el protocolo de enrutamiento
PIM (Protocol-Independet Multicast; RFC 3973 (modo denso), RFC 4601 (modo disperso)). En el modo denso, los
miembros del grupo de multidifusión están localizados de forma densa, es decir, muchos o la mayoría de los routers
del área necesitan involucrarse en el enrutamiento de los datagramas de multidifusión; emplea una técnica de reenvío
de camino inverso con inundación y poda. En el modo disperso, el número de routers con miembros del grupo
conectados es menor con respecto al número total de routers, por lo que se utilizan puntos de cita para configurar el
árbol de multidifusión.