13
Cálculo de la Tabla de Enrutamiento
Dos métodos:
Enrutamiento estático: la tabla se determina al momento de "booteo". Las rutas no cambian. Es simple y no involucra overhead.
Enrutamiento dinámico: Se determina una tabla inicial y se mantiene según cambian las condiciones de la red. Se adapta automáticamente a fallas de la red.
El cálculo de la tabla de enrutamiento usa el algoritmo de Dijkstra.
14
Algoritmo de Dijkstra
Este algoritmo determina el camino más corto para llegar a cualquier nodo a partir de un nodo fuente.
Nodo fuente
15
Versión del Algoritmo de Dijkstra
Estructuras de datos:
D arreglo para distancia mínima a cada nodo.
R arreglo para próximo tramo a seguir en la ruta
Entrada: Grafo con arcos con peso reflejando distancia entre nodos. Nodo fuente.
Salida: D[i] conteniendo distancia más corta hasta i. R[i] siguiente tramo para llegar a nodo i.
El peso puede ser el número de switches en el camino, reflejar la capacidad de la conexión, o una política de administración.
Método ……..?
16
Versión del Algoritmo de Dijkstra, Método
Inicialice el conjunto S con todos los nodos excepto el fuente;
Inicialice el arreglo D tal que D[v] es el peso del arco (fuente,v). Si el arco no existe D[v] = infinito.
Inicialice el arreglo R tal que R[v]=fuente si un arco existe entre fuente y v, cero en otro caso.
While ( S != Ø) { /* aún queden nodos por alcanzar desde la fuente */ Seleccionar un nodo u tal que D[u] sea mínima; /* vecino más cercano */ if ( D[u] = infinito) { error: No existe trayectoria a los nodos de S; } Eliminar u de S; /* uno menos por considerar */ for ( cada nodo v tal que (u,v) es un arco ) { if (v ? S) { /* arcos a nodos no considerados */ c = D[u] + peso(u,v); if (c < D[v]) { /* nodo u da ruta más corta a v */ R[v] = R[u]; D[v] = c; } } }}
17
Enrutamiento por estado de enlace
También conocido como "trayectoria más corta primero" (Shortest Path First, SPF)
Cada switch envía mensajes con el estado de los enlace con sus switches vecinos.
Cada switch construye y mantiene el grafo con la información que recibe regularmente.
Cada switch ejecuta el algoritmo de Dijkstra para determinar la tabla de enrutamiento.
18
Cálculo Distribuido de Rutas
Cada switch envía periódicamente su tabla (vector) a los switches vecinos.
Luego de un rato cada switch "aprende" cual es la ruta más corta para llegar a cada nodo.
El resultado final es el mismo al algoritmo de Dijkstra.
El algoritmo más conocido se llama Algoritmo de vector de distancia. Éste envía un vector con pares (destino, distancia).
Cuando una tabla llega desde un vecino N, el switch examina cada entrada para determinar si el vecino produce una trayectoria más corta para un determinado destino que aquella en uso hasta ese momento.
19
Algoritmo de Vector de Distancia
Condición Inicial: Sólo una entrada con el switch local, con distancia cero y próximo tramo sin usar (null o algo así).
Entrada: Una tabla de enrutamiento, el peso para cada enlace vecino, un mensaje de enrutamiento desde un vecino.
Salida: Una tabla de enrutamiento actualizada.
Método:Repeat para siempre { Espere la llegada de un mensaje de enrutamiento. Sea N el vecino. for (cada entrada en la tabla que llego desde N) { Sea V el destino de esa entrada y D la distancia; C = D + peso para llegar a vecino N; if ( no existe ruta a V en tabla local ) { Agregar ruta a V con N como ruta y distancia C; } else if (la ruta existe y próximo tramo es N ) { Reemplace la distancia para llegar a V con C; } else if ( una ruta existe con mayor distancia que C) { cambie el próximo tramo a N y haga distancia=C; } }}
20
Ejemplos de Tecnologías WAN
ARPANET (Advanced Research Project Agency Net)
X.25 (nombre del estándar de la CCITT, hoy ITU)
ISDN (Integrated Services Digital Network)
Frame Relay (relé de tramas)
SMDS (Switched Multi-megabit Data Service)
ATM (Asynchronous Transfer Mode)
21
Tecnologías WAN
ARPANET: > 30 años , precursor de la Internet. Usaba líneas seriales a 56 Kbps.
X.25:
Cada red X.25 consiste de swithces X.25 conectados con líneas arrendadas.
Fue pensada para conectar terminales ASCII a computadores remotos.
Hoy no es muy usada por razón costo/tasa de transmisión.
ISDN (Integrated Services Digital Network):
Intenta integrar redes de datos de área extensa con servicio telefónico de voz.
El servicio Basic Rate Interface (BRI) provee dos canales de 64 Kbps (canales B) más uno de 16 Kbps (canal D) ó 2B+D.
El canal D es usado para señalización de discado digital y los otros para datos o voz.
64 kbps ha resultado ser poco para los estándares actuales => predicciones de éxito no se han cumplido.
22
Tecnologías WAN
Frame Relay
Fue pensada para transmisión de datos en bloques de 8 K bytes.
Idea original fue ofrecer conexiones entre 4 a 100 Mbps, pero los subscriptores han usado conexiones de sólo 1.5 Mbps ó 56 Kbps.
Servicio orientado a la conexión.
SMDS (Switched Multi-megabit Data Service)
Diseñada para transportar datos.
Un pequeño encabezado permite transportar paquetes de hasta 9188 bytes => bajo overhead.
Normalmente operan a mayor velocidad que Frame Relay
Servicio no orientado a la conexión
ATM
Idea es ofrecer servicios para transmisión de voz, vídeo, y datos.
Para alcanzar alta velocidad con poco retardo y bajas variaciones de retardo (bajo jitter), los datos son divididos en pequeñas celdas de tamaño fijo. 53 bytes = 5 Encabezado + 48 Datos
 Página anterior | Volver al principio del trabajo | Página siguiente  |