La Capa de Red
Dr. Ivan Olmos
La Capa de Red
Orientada a llevar los paquetes desde el origen hasta el destino Aqu, se debe conocer perfectamente el esquema de la subred para escoger la mejor ruta Adems, se debe considerar el trfico, para que en el caso de que sea necesario, cambiar la ruta de los datagramas
Dr. Ivan Olmos
La Capa de Red
Esta capa se debe de encargar de manejar las diferencias que pudieran existir entre la red de origen y la de destino La capa de red debe ofrecer una interfaz bien definida a la capa de transporte, en la cual, los servicios proporcionados deben ser:
Independientes de la tecnologa de la subred La capa de transporte debe estar aislada de la cantidad, tipo y topologas de las subredes presentes Las direcciones de la capa de transporte debe tener un orden uniforme
Dr. Ivan Olmos
La Capa de Red
La capa de red se puede disear:
Orientada a la conexin Sin conexin
Los partidarios del servicio sin conexin involucra a la comunidad de Internet Por otro lado, los partidarios del servicio con conexin son las compaas telefnicas
Dr. Ivan Olmos
El enfoque sin conexin
Se plantea que la nica tarea de la capa de red es encaminar bits de un DTE a otro DTE Se toma de antemano que la subred es inherentemente inestable, sin importar su diseo Por lo anterior, se enfocan a que los DTE realicen el control de errores y el control de flujo Adems, cada paquete debe llevar la direccin de destino completa, con el fin de que estos se pueden encaminar por vas distintas, si es necesario
Dr. Ivan Olmos
El enfoque sin conexin
La propuesta de la comunidad de Internet se sustenta en el hecho de que los sistemas de cmputo son ms poderosos y econmicos, con lo cual el costo de un diseo de una subred no sera muy elevado (no se incluyen las tareas que las computadoras tienen que realizar)
Dr. Ivan Olmos
El enfoque con conexin
Por otro lado, las empresas telefnicas sostienen lo siguiente:
Antes de enviar datos, se debe establecer una conexin entre el emisor y el receptor Al establecerse la conexin, se puede determinar la calidad de la conexin, as como el costo del servicio La comunicacin es en ambas direcciones y los paquetes se entregan en secuencia Se proporciona control de flujo
Dr. Ivan Olmos
Comentarios
La mayor complejidad en el diseo y la implementacin en el esquema orientado a conexin est en la capa de red (subred) La mayor complejidad en el diseo y la implementacin en el esquema sin conexin est en la capa de transporte (en cada computadora)
Dr. Ivan Olmos
Conexin vs. Sin Conexin
Ambos enfoques actualmente tienen su representante operativo:
Internet: sin conexin ATM: con conexin
Internet se ha propagado debido a la gran flexibilidad que ofrece ATM actualmente es el esquema de alta velocidad dominante, aunque de alto costo
Dr. Ivan Olmos
Conexin vs. Sin conexin
En el esquema orientado a la conexin, se establecen circuitos virtuales (los paquetes siguen la misma ruta marcada por el primero de ellos) En el esquema sin conexin, los paquetes enviados se conocen como datagramas (no se determinan rutas por adelantado, esto es, dos datagramas pueden seguir rutas distintas a su destino)
Dr. Ivan Olmos
10
Conexin vs. Sin conexin
Generalmente las subredes de datagramas son ms robustas y se adaptan mejor a fallas y congestionamiento
Dr. Ivan Olmos
11
Subredes orientadas a Conexin
Aqu, los enrutadores debe mantener una tabla con todos los circuitos virtuales que estn manejando (se asocia a cada circuito un nmero) Cada paquete que viaje, tiene que contener un campo para un nmero de circuito virtual, adems de los nmeros de secuencia, sumas de comprobacin...
Dr. Ivan Olmos
12
Subredes orientadas a Conexin
Cuando un enrutador recibe un paquete, conoce la lnea por la cual lleg as como el correspondiente nmero de circuito virtual Cada computadora, al establecer una conexin de red, hace uso de una direccin libre de circuito virtual Dichos nmeros de direccin son independientes de un sistema a otro
Dr. Ivan Olmos
13
Subredes orientadas a Conexin
Como cada sistema es capaz de establecer una conexin, se pueden presentar inconvenientes cuando se establecen conexiones al mismo tiempo en los dos extremos que se desean comunicar Cada proceso debe indicar cuando ha terminado de usar un circuito virtual, de modo que la direccin pueda purgarse de la tabla de los enrutadores
Dr. Ivan Olmos
14
Subredes basadas en Datagramas
En este esquema, los enrutadores tienen una tabla que indica la lnea de salida a usar para cada enrutador de destino posible Los datagramas contienen la direccin de destino completa En redes grandes, las direcciones pueden ser de varios bytes
Dr. Ivan Olmos
15
Ventajas y Desventajas
Por una parte, el tamao de las direcciones en cada paquete significa una carga extra de informacin, que puede llegar a ser muy significativa (datagramas) Por otro lado, en los circuitos virtuales se hace uso de espacios de tabla en los enrutadores Espacio de memoria del enrutador desperdicio del ancho de banda
Dr. Ivan Olmos 16
Ventajas y Desventajas
Otro balance es el tiempo que se requiere para establecer un circuito al inicio de la comunicacin; ms sin embargo, posteriormente los paquetes saben exactamente por donde encaminarse, por lo que no se pierde tiempo En la subred de datagramas, se requiere un proceso ms complejo para decidir por donde se encaminar el paquete
Dr. Ivan Olmos
17
Ventajas y Desventajas
Los circuitos virtuales permiten manejar el problema del congestionamiento en la subred En una subred de datagramas, es ms complicado manejar dicho problema Los circuitos virtuales son vulnerables, ya que si se cae un enrutador, todos los circuitos virtuales de su tabla dejaran de funcionar Por el contrario, si se cae un enrutador de datagrama, solo se perdern los paquetes que en ese momento se encontraban en el enrutador
Dr. Ivan Olmos 18
Algoritmos de Enrutamiento
Dr. Ivan Olmos
19
Algoritmos de Enrutamiento
Es aquella parte del software (de la capa de red) que se encarga de decidir la lnea de salida por la que se transmitir un paquete de entrada En una subred de datagramas, sta decisin se realiza en cada enrutador para cada paquete de entrada En una subred de circuitos virtuales, la decisin se toma al momento de establecer el camino del circuito (enrutamiento de sesin)
Dr. Ivan Olmos
20
10
Algoritmos de Enrutamiento
Deben ofrecer propiedades como:
Correccin Sencillez Robustez Estabilidad Equitatividad Optimalidad
Dr. Ivan Olmos
21
Algoritmos de Enrutamiento
Los algoritmos deben planearse para soportar los cambios de la topologa de la subred as como el trfico sin requerir la paralizacin de actividades Tambin se busca minimizar el retardo medio de los paquete as como aumentar al mximo el rendimiento de la red (normalmente se busca minimizar el nmero de escalas, ya que esta variable influye en un mejor rendimiento y un menor retardo)
Dr. Ivan Olmos
22
11
Algoritmos de Enrutamiento
Se clasifican en dos grupos:
Algoritmos no adaptables: se calcula las rutas de flujo desde un principio, las cuales se cargan en los enrutadores Algoritmos adaptables: modifican las rutas de acuerdo a la topologa presente en un instante de tiempo dado, as como consideran el trfico. Dichos algoritmos varan de acuerdo a la forma de obtencin de su informacin as como la mtrica en la cual se basen (distancia, nmero de escalas, tiempo de trnsito..)
Dr. Ivan Olmos 23
Algoritmos de Enrutamiento
Para encontrar las rutas ms optimas, los algoritmos de enrutamiento hacen uso del principio de optimacin, que dice: Si un enrutador K se encuentra en la ruta ptima del enrutador I al enrutador J, entonces la trayectoria ptima de K a J se encuentra en la misma ruta
Dr. Ivan Olmos
24
12
Algoritmos de Enrutamiento
A partir del principio de optimacin, se puede deducir que todas las rutas ptimas a un destino comn forman un rbol con raz en el destino, conocido como rbol de ascenso Dichos rboles no necesariamente son nicos Los rboles tienen una gran propiedad: no contienen ciclos
Dr. Ivan Olmos
25
Enrutamiento por Trayectoria Corta
Al manejarse el trmino enrutamiento por trayectoria ms corta, se debe de definir la mtrica bajo la cual se trabaja:
Mtrica basada en escalas Mtrica basada en distancia Mtrica basada en el retado de encolamiento Mtrica basada en el trfico medio Mtrica basada en el ancho de banda Mtrica basada en el costo de comunicacin...
Dr. Ivan Olmos
26
13
Algoritmo de Dijkstra
Uno de los algoritmos ms populares para encontrar las trayectorias ms cortas (en base a cierta mtrica), es el algoritmo de Dijkstra El algoritmo es el siguiente:
Suponga que se desea encontrar la ruta ms corta entre el nodo A y el nodo Z de un grafo Sea T el conjunto de vrtices en el grafo, L[x] la longitud asociada desde A hasta el nodo x, C[x] el camino asociado desde A hasta el nodo x, W(v,x) peso asociado del vrtice v al vrtice x
Dr. Ivan Olmos 27
Algoritmo de Dijkstra
1.
Para todo x T | x A hacer:
L[x] = , C[x] =
2. 3. 4.
5.
L[A] = 0, C[A] = A Sea v = A, T = T {A} Si v = Z, finalizar (camino mnimo de A a Z: C[v] con longitud L[v]) Para cada vrtice x adyacente a v | x T hacer:
L[x] = min {L[x], L[v] + W(v,x)} Si L[v] + W(v, x) < L[x] hacer:
C[x] = C[v] {x}
Dr. Ivan Olmos
28
14
Algoritmo de Dijkstra
6.
Hacer:
v = min {L[x] | x T} T = T {v}
7.
Regresar a paso 4
Dr. Ivan Olmos
29
Algoritmo de Dijkstra
Por ejemplo, sea el siguiente grafo, obtener el camino mnimo de A a D
B 2 A 6 G
Dr. Ivan Olmos
7 2 E 1 2 4 F 2 2
C 3 D 2 H
30
15
Algoritmo de Dijkstra
T 1 L C L C L C L C L C L C L C L C A 0 A 0 A 0 A 0 A 0 A 0 A 0 A 0 A B 2 AB 2 AB 2 AB 2 AB 2 AB 2 AB 2 AB C 9 ABC 9 ABC 9 ABC 9 ABC 9 ABC 9 ABC D 10 ABEFHD 10 ABEFHD E 4 ABE 4 ABE 4 ABE 4 ABE 4 ABE 4 ABE F 6 ABEF 6 ABEF 6 ABEF 6 ABEF 6 ABEF G 6 AG 6 AG 5 ABEG 5 ABEG 5 ABEG 5 ABEG 5 ABEG H 9 ABEGH 8 ABEFH 8 ABEFH 8 ABEFH
Camino ms corto por Inundacin
Cada paquete de entrada se enva por todas las salidas disponibles, excepto la de entrada Problema: generacin de un gran flujo de datos Solucin:
Limitar el nmero de saltos de un paquete, incluyendo una variable que lleve el conteo Control de cada enrutador sobre los paquetes que a enviado. Para evitar que la lista crezca demasiado, con una variable se puede establecer hasta que paquete ya se proces
Dr. Ivan Olmos
32
16
Camino ms corto por Inundacin
Una forma ms efectiva es la inundacin selectiva, en la cual el paquete solo es enviado por las direcciones ms cercanas al destino En general, la inundacin no es eficiente, pero s muy robusta En este esquema, siempre se es posible encontrar la ruta ms corta, debido a que se prueban todas las rutas posibles en paralelo
33
Dr. Ivan Olmos
Comentario
Tanto el algoritmo de Dijkstra, como el de inundacin, consideran exclusivamente la topologa y no la carga Un algoritmo de enrutamiento que considera ambas variables es el enrutamiento basado en el flujo
Dr. Ivan Olmos
34
17
Enrutamiento basado en el Flujo
Basado en los siguientes conceptos:
En algunas redes, la tasa media de flujo para cada par de nodos es estable y predecible Si se conoce la capacidad y el flujo promedio, es posible calcular el retardo promedio por medio de la teora de colas De los retardos promedio de todas las lneas, se obtiene el retardo medio para un paquete de la subred completa ponderado por el flujo
Dr. Ivan Olmos
35
Enrutamiento basado en el Flujo
Para usar la tcnica, se debe conocer:
La topologa de la subred La matriz de trafico Fij (de un enrutador i a un enrutador j cualquiera) La matriz de capacidad Cij de cada enlace Un algoritmo de enrutamiento
El algoritmo de enrutamiento a usar sirve para determinar las rutas que se usarn para cada enlace
Dr. Ivan Olmos
36
18
Enrutamiento basado en el Flujo
Por ejemplo, suponga el siguiente grafo, del cual obtenemos la matriz de flujo ilustrada
A A B 20 20 C 10 20 E 20 50 20 F D 10 D E F B C
9 BA 4 CBA 1 DF BA 7 EA 4 FEA
B
9 AB 8 CB 3 DFB 2 EFB 4 FB
C
4 ABC 8 BC 3 DC 3 EC 2 FEC
D
1 ABFD 3 BFD 3 CD 3 ECD 4 FD
E
7 AE 2 BFE 3 CE 3 DCE 5 FE
F
4 AEF 4 BF 2 CEF 4 DF 5 EF -
Dr. Ivan Olmos
37
Enrutamiento basado en el Flujo
En la matriz anterior, los pesos de cada arco representan la capacidad del enlace (en kbps) Cada entrada de la matriz consta de dos elementos:
El nmero de paquetes promedio que circula por el enlace y, El camino a seguir desde el origen hasta el destino
Dr. Ivan Olmos 38
19
Enrutamiento basado en el Flujo
En base a la informacin anterior, se puede obtener el flujo total que circula por cada enlace Adems, si suponemos un tamao medio de paquete = 800 bits, se puede obtener el nmero medio de paquetes, C, para cada enlace
Dr. Ivan Olmos
39
Enrutamiento basado en el Flujo
De esta informacin, se puede derivar el retardo medio por lnea, haciendo uso de la teora de colas: T = 1 / (C - ) Con toda la informacin anterior, se puede obtener el retardo promedio considerando toda la subred Para el ejemplo anterior, se tiene la siguiente tabla (el peso representa la relacin entre los paquetes que circulan por un enlacen entre el total de los paquetes que circulan por la subred)
Dr. Ivan Olmos
40
20
Enrutamiento basado en el Flujo
i 1 2 3 4 5 6 7 8 Lnea AB BC CD AE EF FD BF EC i (paq / seg) 14 12 6 11 13 8 10 8 Ci (kbps) 20 20 10 20 50 10 20 20 Ci (paq / seg) 25 25 12.5 25 62.5 12.5 25 25 Ti (mseg) 91 77 154 71 20 222 67 59 Peso 0.171 0.146 0.073 0.134 0.159 0.098 0.122 0.098
Dr. Ivan Olmos
41
Enrutamiento Dinmico
Dr. Ivan Olmos
42
21
Enrutamiento Dinmico
En la prctica, los enrutamientos dinmicos son los usados actualmente Existen dos algoritmos muy empleados
Enrutamiento por vector de distancia Enrutamiento por estado de enlace
Dr. Ivan Olmos
43
Enrutamiento por Vector de Distancia
Cada enrutador mantendr una tabla en la cual se da la mejor distancia conocida a cada destino, as como la lnea a usar para llegar ah Los enrutadores intercambian sus tablas con sus vecinos inmediatos, con lo cual mantienen actualizadas sus tablas Las entradas en la tabla comprenden la lnea de salida al destino as como la estimacin del tiempo o distancia a ese destino (la mtrica puede variar)
Dr. Ivan Olmos
44
22
Enrutamiento por Vector de Distancia
Por ejemplo, suponga el siguiente grafo, en el cual, a partir del nodo J se desea definir la mejor ruta para llegar al destino G Para ello, el enrutador J debe recibir las tablas de sus vecinos, cada una con las mejores rutas hacia los diversos destinos Adems, el enrutador J debe ser capaz de calcular el retardo presente en ese instante a cada uno de sus vecinos
45
Dr. Ivan Olmos
Enrutamiento por Vector de Distancia
A
A
0 12 25 40 14 23 18 17 21 9 24 29
I
24 36 18 27 7 20 31 20 0 11 22 33
H
20 31 19 8 30 19 6 0 14 7 22 9
K
21 28 36 24 22 40 31 19 22 10 0 9
Nuevo retardo estimado Lnea
8 20 28 20 17 30 18 12 10 0 6 15 A A I H I I H H I K K
F E
A B C D E F G H I J K L
Retardo del nodo J al nodo x:
10
12
Nuevo tabla de enrutamiento
23
Enrutamiento por Vector de Distancia
Notemos que los vecinos, de antemano, deben conocer las distancias a todos los nodos Por tanto, se debe tener un proceso previo que calcule dichas distancias Adems, se tiene un problema grave, conocido como conteo a infinito
Dr. Ivan Olmos
47
Enrutamiento por Vector de Distancia
A CASO CUANDO SE DA DE ALTA EL NODO A B
v
C
v
D
v
E
v
1 1 1 1 B 1 3 3 5 5 M
v
2 2 2 C 2 2 4 4 6 M
v
3 3 D 3 3 3 5 5 M
v
4 E
v
Inicialmente Tras 1 intercambio Tras 2 intercambios Tras 3 intercambios Tras 4 intercambios
A CASO CUANDO SE DA DE BAJA EL NODO A
4 4 4 4 6 M
Inicialmente Tras 1 intercambio Tras 2 intercambios Tras 3 intercambios Tras 4 intercambios M
48
Dr. Ivan Olmos
24
Enrutamiento por Vector de Distancia
Para tratar de resolver el problema, se han propuesto algoritmos como el horizonte dividido Sin embargo, dichas mejoras no funcionan del todo bien, por lo que ste algoritmo se abandono, dando paso a uno totalmente nuevo, conocido como enrutamiento por estado de enlace
Dr. Ivan Olmos
49
Enrutamiento por Estado de Enlace
Basado en los siguientes conceptos:
Descubrir a sus vecinos y conocer sus direcciones de red Medir el retardo o costo para cada uno de sus vecinos Construir un paquete que indique lo que acaba de aprender Enviar el paquete a todos los dems enrutadores Calcular la trayectoria ms corta a todos los dems enrutadores
Dr. Ivan Olmos 50
25
Enrutamiento por Estado de Enlace
Para conocer quienes son sus vecinos de un nodo X, se enva un paquete por cada lnea punto a punto que tenga acceso El enrutador vecino, al recibir dicho mensaje, genera una respuesta indicando quin es Un problema que se puede presentar es cuando dos o ms enrutadores estn conectados por medio de una LAN y no por medio de un enlace punto a punto
51
Dr. Ivan Olmos
Enrutamiento por Estado de Enalce
Cada enrutador debe conocer el costo asociado a cada enlace Si no es as, el enrutador X puede enviar un paquete de eco, el cual, al ser recibido por el enrutador del otro extremo, debe regresarlo lo ms pronto posible Con ello, el enrutador X puede calcular el retardo dividiendo entre dos el tiempo tomado por el paquete de eco
52
Dr. Ivan Olmos
26
Enrutamiento por Estado de Enlace
El tiempo de retardo puede o no considerar la carga de cada enlace Si se desea considerar, el temporizador del paquete debe iniciarse desde el momento en el cual se forma en la cola para ser enviado En caso contrario, dicho temporizador solo se debe activar al momento que el paquete de eco se encuentre al frente de dicha cola
Dr. Ivan Olmos
53
Enrutamiento por Estado de Enlace
Incluir la carga de cada enlace favorece a escoger la lnea menos saturada, y por ende, facilitar el flujo de los paquetes Sin embargo, puede provocar que varios enrutadores seleccionen casi al mismo tiempo la lnea menos saturada, con lo cual, se convertir en la ms suturada, induciendo nuevamente al problema de lneas saturadas
Dr. Ivan Olmos
54
27
Enrutamiento por Estado de Enlace
Una vez recabada la informacin anterior, se construyen los paquetes a enviar a los vecinos, conteniendo:
Identidad del transmisor Nmero de secuencia Edad Lista de vecinos, citando los retardos asociados
Dr. Ivan Olmos
55
Enrutamiento por Estado de Enlace
B 4 A 5 E 1
C 3 D 6 7 F
A Sec. Edad B E 4 5
B Sec. Edad A C F 4 2 6
C Sec. Edad B D E 2 3 1
D Sec. Edad C F 3 7
E Sec. Edad A C F 5 1 8
F Sec. Edad B D E 6 7 8
Dr. Ivan Olmos
56
28
Enrutamiento por Estado de Enlace
Una vez que cada enrutador tenga sus paquetes construidos, falta distribuirlos La distribucin es un proceso delicado, ya que puede inducir a inconsistencias, mquinas inalcanzables, ciclos, etc. En primera instancia, se puede usar inundacin
Dr. Ivan Olmos
57
Enrutamiento por Estado de Enlace
Para mantener controlada la inundacin, cada paquete mantiene un nmero de secuencia, el cual se incrementa en uno al enviarse por un enrutador Los enrutadores llevan la secuencia de cada par (enrutador origen, secuencia), para evitar reenviar aquellos que ya han sido procesados
Dr. Ivan Olmos
58
29
Enrutamiento por Estado de Enlace
Para evitar que se agote el nmero se secuencia (se llegue a su mximo), se suelen emplear nmeros grandes (por ejemplo, 232) Adems, existen problemas como:
Un enrutador deje de funcionar, con lo cual, se reiniciar su nmero de secuencia Se puede corromper el nmero de secuencia al momento de ser enviado
Dr. Ivan Olmos
59
Enrutamiento por Estado de Enlace
La solucin a dichos problemas es incluir una edad a cada paquete; as, despus de determinado tiempo, la informacin proveniente del enrutador ser descartada (conteo de forma descendiente) Lo anterior es posible debido a que la generacin de paquetes se puede establecer cada 10 minutos, por ejemplo
Dr. Ivan Olmos
60
30
Enrutamiento por Estado de Enlace
Algunas mejoras se pueden hacer a este algoritmo:
Por ejemplo, se puede implementar que, cuando un enrutador reciba un nuevo paquete, no lo enve inmediatamente; en cambio, se programa para esperar determinado tiempo; si en ese tiempo recibe un nuevo paquete del mismo enrutador origen, compara la secuencia de los paquetes: si son iguales, se descarta el duplicado; en caso contrario, se desecha el paquete ms viejo
Dr. Ivan Olmos 61
Enrutamiento por Estado de Enlace
Una vez que un enrutador tiene todos los paquetes completos de todos los enrutadores, puede construir el grafo de la subred Con la informacin anterior, puede ejecutar el algoritmo de Dijkstra para localizar las rutas ms ptimas
Dr. Ivan Olmos
62
31
Enrutamiento Jerrquico
Las subredes generalmente son grandes, por lo que mantener tablas en un enrutador correspondientes al resto de los mismos puede llegar a ser inapropiado Para evitar este problema, se ha optado por el enrutamiento jerrquico, en el cual, los enrutadores solo conocen la forma de enrutar paquetes dentro de cierta regin (de enrutadores), pero no conocen como hacerlo fuera de ella
Dr. Ivan Olmos
63
Enrutamiento Jerrquico
TABLA COMPLETA PARA 1A
1B 1B 1C 1B 1B 1B 1B 1C 1C 1C 1C 1C 1C 1C 1B 1C 1C 1 1 2 3 3 4 3 2 3 4 4 4 5 5 6 5
1B 1A 1C
2A 2B 2C 2D
1C 2A 2B 2C 2D 3A 3B
TABLA JERARQUICA PARA 1A
1A 1B 1C 2 3 4 5 1B 1C 1B 1C 1C 1C 1 1 2 2 3 4
3A 3B 4B
4A
5B 5A 5C 5D
4A 4B 4C 5A 5B 5C
4C
5E
DESTINOS
5D 5E
32
Enrutamiento para Mquinas Mviles
En la actualidad, con el advenimiento de los sistemas porttiles, surge la necesidad de mantenerlos comunicados Bsicamente, podemos identificar dos tipos de usuarios mviles:
Usuarios migratorios, los cuales se mueven de un lugar a otro, haciendo uso de la red solo cuando se conectan a una red local Usuarios errantes, los cuales hacen su cmputo en movimiento, manteniendo la conexin en todo momento
Dr. Ivan Olmos
65
Enrutamiento para Mquinas Mviles
En el enrutamiento para mquinas mviles, se presupone que tienen una localidad base Una de las formas de enrutar paquetes a usuarios mviles es enviar los paquetes a su localidad base y sta, se encargue de enviar la informacin al host mvil, en donde quiera que se encuentre
Dr. Ivan Olmos
66
33
Enrutamiento para Mquinas Mviles
Las localidades mantendrn dos tipos de centinelas:
Agentes forneos, que llevan el registro de todos los usuarios que visitan el rea Agentes de base, que llevan el registro de todos los usuarios mviles cuya base est en el rea, pero que actualmente estn visitando otra rea
Dr. Ivan Olmos
67
Enrutamiento para Mquinas Mviles
Normalmente, cuando un sistema visita una localidad, se realiza un proceso de registro como el siguiente:
Los agentes forneos regularmente verifican si ha ingresado un visitante por medio de un mensaje; si no es as, el visitante puede difundir un paquete con el objetivo de hacer notar su presencia
Dr. Ivan Olmos
68
34
Enrutamiento para Mquinas Mviles
El host mvil se registra con el agente forneo, dando su direccin base y su direccin de enlace de datos actual, as como cierta informacin de seguridad El agente forneo localiza al agente base del host mvil, mandando la direccin de red del agente forneo, as como la informacin de seguridad (autenticacin)
Dr. Ivan Olmos
69
Enrutamiento para Mquinas Mviles
El agente de base del host mvil verifica la autenticidad del mensaje con respecto al usuario mvil Si supera la condicin anterior, el agente forneo recibe el reconocimiento del agente de base. Acto seguido, el agente forneo registra al usuario mvil y le hace de su conocimiento el hecho
Dr. Ivan Olmos
70
35
Enrutamiento para Mquinas Mviles
Con lo anterior, si se generan paquetes para el usuario mvil, el agente de base intercepta dichos paquetes, envindolos a la nueva localidad (temporal) del usuario mvil El agente forneo donde se encuentra el usuario mvil recibir dichos paquetes, retirar la informacin aadida por el agente de base y, por medio de un marco de enlace de datos, se lo enviar al usuario mvil
Dr. Ivan Olmos
71
Enrutamiento para Mquinas Mviles
Adems, el agente de base le indicar al transmisor que enve el resto de los paquetes encapsulndolos para el agente forneo donde se encuentra el usuario mvil
Dr. Ivan Olmos
72
36
Enrutamiento por Difusin
Cuando se desea enviar informacin a un conjunto de host, ser necesario implementar alguna tcnica de difusin Hasta el momento, dos tcnicas saltan para implementarse:
Envo simultneo de un paquete a todos los destinos (difusin) Inundacin
Dr. Ivan Olmos
73
Enrutamiento por Difusin
Otra forma de difusin es el enrutamiento multidesino A cada paquete, se le incluye un grupo de destinos Cada enrutador, al recibir el paquete, hace una copia del mismo a los destinos indicados (tipo multicast) Adems, en las nuevas copias solo se indican los destinos asociados a cada ruta
Dr. Ivan Olmos 74
37
Enrutamiento por rbol de Extensin
En los rboles de extensin, se conectan de manera lgica los enrutadores de una red, sin contener ciclos Si cada enrutador conoce de manera precisa las ramas del rbol, se pueden hacer copias de paquetes por las mismas, aprovechando muy bien el ancho de banda (no se generan copias innecesarias)
Dr. Ivan Olmos
75
Reenvo por Trayectoria Invertida
En esta tcnica, se busca simular el comportamiento de un rbol de extensin, a pesar de no conocerlo explcitamente Para ello, cuando un enrutador recibe un paquete de difusin, verifica si este lleg por la lnea preferida. Si es as, significa que el paquete tiene una alta probabilidad de que haya seguido una buena ruta desde el origen
Dr. Ivan Olmos
76
38
Reenvo por Trayectoria Invertida
En tal caso, el enrutador debe colocar una copia en todas las salidas disponibles, excepto por la que lleg En caso de no recibirse por la ruta habitual, dicho paquete debe ser descartado Con ello, se est controlando al mismo tiempo el exceso de flujo innecesario en segmentos de la red
Dr. Ivan Olmos
77
Enrutamiento por Multitransmisin
Otra tcnica en la cul se puede enviar informacin a un grupo de host Aqu es necesario que los host se renan en grupos (numerados), accin que deben conocer perfectamente los enrutadores De esta forma, cada enrutador conocer los grupos a los cuales puede acceder
Dr. Ivan Olmos
78
39
Enrutamiento por Multitransmisin
En base a los grupos asociados a cada enrutador, se forman rboles de extensin que cubran cada enrutador de la subred Con ello, cuando se realice una multitransmisin a un grupo o grupos determinados, se seguirn los rboles de extensin para llegar a los destinos
Dr. Ivan Olmos
79
Enrutamiento por Multitransmisin
1 2 2
1, 2 1, 2 2
2 1, 2
1, 2 2
1 1 1 1
Dr. Ivan Olmos
80
40
Algoritmos de Control de Congestionamiento
Dr. Ivan Olmos
81
Control de Congestionamiento
El congestionamiento se presenta cuando existen demasiados paquetes en la subred Estos se pueden originar por varias causas:
Si varios paquetes de varias lneas de entrada de un enrutador desean salir por una sola lnea La velocidad de las CPUs de los enrutadores Lneas con poco ancho de banda (modernizacin de solo un segmento de la subred)
Dr. Ivan Olmos
82
41
Control de Congestionamiento
Cuando un enrutador, por una causa o por otra, no se puede deshacer de los paquetes con la misma rapidez con que los recibe, tender a perder paquetes (la memoria es limitada) El congestionamiento tiende a alimentarse a si mismo y empeorar
Dr. Ivan Olmos
83
Control de Congestionamiento
Las tcnicas de control de congestionamiento suelen confundirse con el control de flujo
En el control de flujo, se implementan algoritmos para evitar que un emisor rpido sature a un emisor lento En contraparte, el control de congestionamiento busca que la subred sea capaz de transportar el trfico ofrecido
La confusin se origina debido a que algunos algoritmos de congestionamiento mandan mensajes pidiendo bajar la velocidad de trans.
Dr. Ivan Olmos
84
42
Control de Congestionamiento
De manera conceptual, los algoritmos de control de congestionamiento se dividen en dos grupos:
Los de ciclo abierto, los cuales tratan de evitar el problema con un buen diseo Los de ciclo cerrado, los cuales tratan de resolver el problema una vez que se ha dado
Dr. Ivan Olmos
85
Control de Congestionamiento
Un punto a decidir es cuando se genera un congestionamiento. Para ello, se toman aspectos como:
Porcentaje de paquetes descartados Longitud promedio de las colas Cantidad de paquetes descartados por el temporizador Retardo promedio de los paquetes
Dr. Ivan Olmos
86
43
Control de Congestionamiento
Una vez que se ha detectado un congestionamiento, los algoritmos de ciclo cerrado tienen que informar del hecho a los vecinos
Se puede informar con paquetes o, Se puede notificar por medio de algn bit en cada uno de los paquetes de salida
Dr. Ivan Olmos
87
Control de Congestionamiento
De entrada, cuando se piensa en congestionamiento, dos soluciones son las ms obvias:
Aumentar los recursos de la subred Disminuir la carga de trabajo
Sin embargo, dichas soluciones, en ocasiones no son viables
Dr. Ivan Olmos
88
44
Mtodos de Ciclo Abierto
Dr. Ivan Olmos
89
Prevencin
stos mtodos tratan de alcanzar su meta implementando ciertas polticas Por ejemplo, en la capa de enlace de datos se busca implementar temporizadores que eviten hasta cierto grado precipitar el inicio de una retransmisin Tambin, se busca que los acuses de recibo no generen una carga extra a la red
Dr. Ivan Olmos
90
45
Prevencin
En la capa de red, se busca encontrar, por ejemplo, tamaos de colas de espera para los enrutadores, tanto para las lneas de salida como las de entrada Lo anterior debe tener en cuenta un tamao que no induzca a que los paquetes en espera finalicen sus temporizadores
Dr. Ivan Olmos
91
Conformacin de Trfico
La naturaleza del flujo en una red no es constante, generalmente se presenta por rfagas Si fuera constante, sera fcilmente predecible y, por ende, se evitaran los congestionamientos Una forma de atacar el problema es obligar a la transmisin de los paquetes a una tasa predecible, como en las redes ATM A dicha forma de trabajo se conoce como conformacin de trfico
Dr. Ivan Olmos
92
46
Conformacin de Trfico
La conformacin de trfico se puede aplicar de manera natural a las subredes de circuitos, aunque tambin se puede adaptar a las subredes de datagramas Normalmente se verifica que se cumpla con la tasa promedio prometida Para ello, se deben analizar los alcances de los elementos de interconexin que se usen en la subred (p.e., la velocidad de los ruteadores)
Dr. Ivan Olmos
93
Algoritmo de Cubeta con Goteo
Es un esquema conceptual en el cual, a los ruteadores de les ve como a una cubeta:
La cubeta tiene cierto agujero en el fondo, por la cual sale de forma constante cierta cantidad de agua, mientras la misma tenga agua Si la velocidad con la que se introduce agua es mayor a la velocidad del goteo, eventualmente se llenar la cubeta, empezando a derramar agua
Dr. Ivan Olmos
94
47
Algoritmo de Cubeta con Goteo
A los enrutadores se les ve de manera similar:
Cada enrutador tiene una capacidad para almacenar marcos Estos marcos son despachados con cierta velocidad de salida Si la velocidad de entrada de marcos es mayor que la salida, eventualmente se saturar la memoria del enrutador, provocando que pierda marcos
Dr. Ivan Olmos 95
Algoritmo de Cubeta con Goteo
Con estas consideraciones, se puede planificar la velocidad de envo de un emisor sin que se produzcan prdidas en los enrutadores Otra variante de ste esquema es la cubeta con fichas, la cual permite acelerar el goteo si existen rfagas de flujo, as como la reservacin de transmisin para emisores Una variante interesante en la cubeta con fichas, es que est solo pierde fichas, no paquetes
Dr. Ivan Olmos
96
48
Mtodos de Ciclo Cerrado
Dr. Ivan Olmos
97
Control de Congestionamiento en Redes de Circuito Virtual
Una vez que se ha detectado un congestionamiento en una subred de circuito virtual, se debe actuar para evitar que empeore Una forma es restringir la apertura de nuevos circuitos, tcnica conocida como control de admisin
Dr. Ivan Olmos
98
49
Control de Admisin
La idea es simple: si se ha detectado un congestionamiento, no se establecen circuitos virtuales nuevos hasta que haya desaparecido el problema Tambin se puede optar por establecer cuidadosamente nuevos circuitos, pero por rutas no congestionadas
Dr. Ivan Olmos
99
Control de Admisin
Otra forma alternativa, dentro de los circuitos virtuales, es negociar un acuerdo sobre el volumen y trfico para cada circuito, con lo cual se reservarn recursos por donde pase el circuito Sin embargo, esta ltima tcnica tiende a desperdiciar recursos
Dr. Ivan Olmos
100
50
Paquetes de Estrangulamiento
Otra forma de manejar los congestionamientos es por medio de paquetes de estrangulamiento (aplicable tanto a subredes de circuito virtual como de datagramas) La idea consiste en verificar, por medio de una variable, el flujo en un enlace
Dr. Ivan Olmos
101
Paquetes de Estrangulamiento
Esta variable oscila en el rango de 0 a 1 Cuando se acerca a 1, indica que el flujo para un enlace de salida se est volviendo muy alto. Por tanto, el enrutador debe realizar lo siguiente:
Genera un paquete de estrangulamiento al origen, indicndole que baje el ritmo de transmisin Por otro lado, marca un bit en el paquete de salida, para evitar que ms adelante se generen paquetes de estrangulamiento
Dr. Ivan Olmos 102
51
Paquetes de Estrangulamiento
El host de origen, al recibir el paquete de estrangulamiento, debe reducir su velocidad en un determinado porcentaje El host, una vez que haya reducido su velocidad, esperar un tiempo aleatorio (durante el cual har caso omiso de nuevos paquetes de estrangulamiento), para posteriormente verificar si hay ms paquetes de estrangulamiento Si los hay, reduce an ms su velocidad. Si no los hay, vuelve a la velocidad normal
Dr. Ivan Olmos 103
Paquetes de Estrangulamiento
Notemos que este enfoque no se bloquea totalmente a un emisor, simplemente se le obliga a reducir la velocidad de transferencia Sin embargo, se corre el riesgo que algunos emisores hagan caso omiso de dicho mensaje
Dr. Ivan Olmos
104
52
Encolamiento Justo
Para evitar este problema, se puede optar por simular una cola para cada origen. As, cuando la lnea de salida se encuentre desocupada, se manda el paquete almacenado en la cola correspondiente Sin embargo, notemos que los paquetes pueden diferir en tamao, por lo que los host con paquetes ms grandes obtendrn un ancho de banda mayor que los host con paquetes de menor tamao
Dr. Ivan Olmos
105
Encolamiento Justo Ponderado
Para resolver este problema, se ha propuesto que el enrutador, en vez de mandar paquete por paquete de cada cola, enve byte a byte De esta manera, el tamao de los paquetes ser independiente 1 2 3 4 5 6 8
Dr. Ivan Olmos 106
53
Paquetes de Estrangulamiento por Escala
Un problema que tienen los paquetes de estrangulamiento es el hecho de que solo van a surtir efecto hasta que hayan llegado al host origen Notemos que mientras se propaga dicho paquete, continuar generndose la misma cantidad de flujo
Dr. Ivan Olmos
107
Paquetes de Estrangulamiento por Escala
Una forma alternativa es que, cada vez que el paquete de estrangulamiento visite un nodo, este reduzca su velocidad de manera inmediata Este enfoque obliga a destinar ms memoria al flujo (ya que del lado del emisor se sigue manteniendo la velocidad de transferencia); sin embargo, del lado del receptor, se disminuye de manera ms rpida la carga
Dr. Ivan Olmos
108
54
Desprendimiento de Carga
Si a pesar de recurrir a todas las artimaas disponibles, no se puede controlar el congestionamiento, los enrutadores pueden recurrir al desprendimiento de carga Esta tcnica consiste en tirar o eliminar aquellos paquetes que los enrutadores ya no pueden manejar
Dr. Ivan Olmos
109
Interredes
Dr. Ivan Olmos
110
55
Interredes
Debido a que se tienen diversas tecnologas de red, surge el problema de cmo comunicar estas tecnologas Cuando se unen dos o ms redes, forman una interred Se pueden usar diversos dispositivos de interconexin, los cuales trabajan a diversos niveles (de enlace de datos, de red, ...)
Dr. Ivan Olmos
111
Interredes
Ejemplos de elementos de interconexin son:
Repetidores, los cuales se encargan de amplificar una seal de entrada (a nivel fsico) Los puentes, los cuales reciben, almacenan y reenvan marcos al nivel de la capa de enlace de datos. Adems, tiene la capacidad de hacer cambios menores a los marcos
Dr. Ivan Olmos
112
56
Interredes
Los enrutadores multiprotocolo, son dispositivos que trabajan en la capa de red (conceptualmente son similares a los puentes). stos toman un paquete de entrada y lo colocan por alguna lnea de salida. Las lneas de salida pueden pertenecer a redes diferentes y usar protocolos distintos Existen otros dispositivos, como las pasarelas de transporte y las de aplicacin
Dr. Ivan Olmos
113
Interredes
El manejo de la interconexin de dos redes distintas es complejo Dentro de las combinaciones, existe el caso cuando, tanto el host origen como el destino, estn en la misma clase de red Una problemtica al realizarse el traslado del origen al destino, es que el paquete cruce por distintas clases de red
Dr. Ivan Olmos
114
57
Proceso de Tnel
Por ejemplo, si deseamos enviar un paquete IP de una red Ethernet a otra, se coloca primero el paquete IP en un marco Ethernet; despus, al llegar dicho paquete a un enrutador multiprotocolo, ste retira el paquete IP y lo coloca en el campo de carga til del paquete de red WAN De esta manera, puede viajar a travs de toda la subred y, al llegar a la red destino, simplemente desempaquetarlo y entregarlo
Dr. Ivan Olmos
115
Fragmentacin
Una complicacin adicional surge al trabajar con interredes, ya que estas suelen manejar tamaos de paquetes distintos Para atacar este problema, se pueden llevar a cabo dos esquemas de fragmentacin:
Transparente No transparente
Dr. Ivan Olmos
116
58
Fragmentacin Transparente
En este esquema, cuando un paquete es demasiado grande para enviarse, se fragmenta, pero es reensamblado inmediatamente del otro lado de la lnea De esta manera, se hace transparente el paso de un paquete a travs de la red Sin embargo, tiene el inconveniente de que cada elemento de interconexin (pasarelas) debe tener la capacidad de desensamblar y reensamblar paquetes, y no los host
Dr. Ivan Olmos 117
Fragmentacin no transparente
Por el contrario, este esquema, desde un inicio, fragmenta al paquete para ser enviados a travs de la red, y ste, solo es reensamblado en el destino Al igual que en el caso anterior, se tienen diversos inconvenientes. Por ejemplo, se aumenta la carga extra, cada host debe tener la capacidad de desensamblar y reensamblar paquetes Sin embargo, tiene la ventaja que se se pueden enviar los paquetes por vas alternas y no por una sola va
Dr. Ivan Olmos 118
59
SUBRED
INTERRED
INTERRED
60
