La Capa de Rediolmos/redes/Red-RESUMEN.pdfruta Además, se debe considerar el tráfico, para ... Calcular la trayectoria más corta a todos los demás enrutadores. ... algoritmo de

La Capa de Red

Dr. Ivan Olmos 1

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

Dr. Ivan Olmos 2

esquema de la subred para escoger la mejor ruta

� Además, se debe considerar el tráfico, para que en el caso de que sea necesario, cambiar la ruta de los datagramas

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

Dr. Ivan Olmos 3

definida a la capa de transporte, en la cual, los servicios proporcionados deben ser:� Independientes de la tecnología de la subred� La capa de transporte debe estar aislada de la cantidad,

tipo y topologías de las subredes presentes� Las direcciones de la capa de transporte debe tener un

orden uniforme

La Capa de Red

� La capa de red se puede diseñar:� Orientada a la conexión� Sin conexión

� Los partidarios del servicio sin conexión

Dr. Ivan Olmos 4

� Los partidarios del servicio sin conexión involucra a la comunidad de Internet

� Por otro lado, los partidarios del servicio con conexión son las compañías telefónicas

Conexión vs. Sin Conexión

� Ambos enfoques actualmente tienen su representante operativo:� Internet: sin conexión� ATM: con conexión

Dr. Ivan Olmos 5

� ATM: con conexión

� Internet se ha propagado debido a la gran flexibilidad que ofrece

� ATM actualmente es el esquema de alta velocidad dominante, aunque de alto costo

Conexión vs. Sin conexión

� En el esquema orientado a la conexión, se establecen circuitos virtuales (los paquetes siguen la misma ruta marcada por el primero de ellos)En el esquema sin conexión, los paquetes

Dr. Ivan Olmos 6

� En el esquema sin conexión, los paquetes enviados se conocen como datagramas (no se determinan rutas por adelantado, esto es, dos datagramas pueden seguir rutas distintas a su destino)

Conexión vs. Sin conexión

� Generalmente las subredes de datagramas son más robustas y se adaptan mejor a fallas y congestionamiento

Dr. Ivan Olmos 7

Algoritmos de Enrutamiento

Dr. Ivan Olmos 8


� Es aquella parte del software (de la capa de red) que se encarga de decidir la línea de salida por la que se transmitirá un paquete de entrada

� En una subred de datagramas, ésta decisión se realiza en cada enrutador para cada paquete de

Dr. Ivan Olmos 9

realiza en cada enrutador para cada paquete de entrada

� En una subred de circuitos virtuales, la decisión se toma al momento de establecer el camino del circuito (enrutamiento de sesión)


� Deben ofrecer propiedades como:� Corrección� Sencillez� Robustez

Dr. Ivan Olmos 10

� Robustez� Estabilidad� Equitatividad� Optimalidad


� 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

Dr. Ivan Olmos 11

� Algoritmos adaptables : modifican las rutas de acuerdo a la topología presente en un instante de tiempo dado, así como consideran el tráfico. Dichos algoritmos varían de acuerdo a la forma de obtención de su información así como la métrica en la cual se basen (distancia, número de escalas, tiempo de tránsito..)


� Para encontrar las rutas más “optimas”, los algoritmos de enrutamiento hacen uso del principio de optimación , que dice:Si un enrutador K se encuentra en la ruta

Dr. Ivan Olmos 12

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

Enrutamiento por Trayectoria Corta

� Al manejarse el término “enrutamiento por trayectoria más corta”, se debe de definir la métrica bajo la cual se trabaja:� Métrica basada en escalas

Métrica basada en distancia

Dr. Ivan Olmos 13

� Métrica basada en distancia� Métrica basada en el retado de encolamiento� Métrica basada en el tráfico medio� Métrica basada en el ancho de banda� Métrica basada en el costo de comunicación...

Algoritmo de Dijkstra

1. Para todo x ∈ T | x ≠ A hacer:• L[x] = ∞, C[x] = ∅

2. L[A] = 0, C[A] = A3. Sea v = A, T = T – {A}4. Si v = Z, finalizar (camino mínimo de A a Z: C[v]

Dr. Ivan Olmos 14

4. Si v = Z, finalizar (camino mínimo de A a Z: C[v] con longitud L[v])

5. Para cada vértice 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}

Algoritmo de Dijkstra

6. Hacer:• v = min {L[x] | x ∈ T}• T = T – {v}

7. Regresar a paso 4

Dr. Ivan Olmos 15

7. Regresar a paso 4

Camino más corto por Inundación

� Cada paquete de entrada se envía por todas las salidas disponibles, excepto la de entrada

� Problema : generación de un gran flujo de datos� Solución :

Dr. Ivan Olmos 16

� Limitar el número 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ó

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

Dr. Ivan Olmos 17

Si se conoce la capacidad y el flujo promedio, es posible calcular el retardo promedio por medio de la teoría de colas� De los retardos promedio de todas las líneas, se

obtiene el retardo medio para un paquete de la subred completa ponderado por el flujo

Enrutamiento basado en el Flujo

� Para usar la técnica, se debe conocer:� La topología de la subred� La matriz de trafico Fij (de un enrutador i a un

enrutador j cualquiera)La matriz de capacidad C de cada enlace

Dr. Ivan Olmos 18

� 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 usarán para cada enlace

Enrutamiento Dinámico

Dr. Ivan Olmos 19

Enrutamiento Dinámico

� En la práctica, los enrutamientos dinámicos son los usados actualmente

� Existen dos algoritmos muy empleados� Enrutamiento por vector de distancia

Dr. Ivan Olmos 20

� Enrutamiento por vector de distancia� Enrutamiento por estado de enlace

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 línea a usar para llegar ahí

� Los enrutadores intercambian sus tablas con sus vecinos inmediatos, con lo cual mantienen

Dr. Ivan Olmos 21

vecinos inmediatos, con lo cual mantienen actualizadas sus tablas

� Las entradas en la tabla comprenden la línea de salida al destino así como la estimación del tiempo o distancia a ese destino (la métrica puede variar)

Enrutamiento por Vector de Distancia

A B C D 0 24 20 21 8 A

12 36 31 28 20 A

25 18 19 36 28 I

40 27 8 24 20 H

A A I H K Línea

ABCD

Nuevo retardoestimado

EF G H

I J K L

40 27 8 24 20 H

14 7 30 22 17 I

23 20 19 40 30 I

18 31 6 31 18 H

17 20 0 19 12 H

21 0 14 22 10 I

9 11 7 10 0 -

24 22 22 0 6 K

29 33 9 9 15 K

DEFGHIJKL

Nuevo tabla deenrutamientoRetardo del nodo

J al nodo x:8 10 12 6

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

Dr. Ivan Olmos 23

vecinos� Construir un paquete que indique lo que acaba de

aprender� Enviar el paquete a todos los demás enrutadores� Calcular la trayectoria más corta a todos los

demás enrutadores


� Para conocer quienes son sus vecinos de un nodo X, se envía un paquete por cada línea punto a punto que tenga acceso

� El enrutador vecino, al recibir dicho mensaje, genera una respuesta indicando quién es

Dr. Ivan Olmos 24

genera una respuesta indicando quién es� Un problema que se puede presentar es

cuando dos o más enrutadores están conectados por medio de una LAN y no por medio de un enlace punto a punto


B CA B C D E F

Sec. Sec. Sec. Sec. Sec. Sec.4

2

Dr. Ivan Olmos 25

A D

E F

Edad Edad Edad Edad Edad Edad

B 4 A 4 B 2 C 3 A 5 B 6

E 5 C 2 D 3 F 7 C 1 D 7

F 6 E 1 F 8 E 8

4 3

5

8

71 6


� Una vez que cada enrutador tenga sus paquetes construidos, falta distribuirlos

� La distribución es un proceso delicado, ya que puede inducir a inconsistencias,

Dr. Ivan Olmos 26

que puede inducir a inconsistencias, máquinas inalcanzables, ciclos, etc.

� En primera instancia, se puede usar inundación


� Para mantener controlada la inundación, cada paquete mantiene un número de secuencia , el cual se incrementa en uno al enviarse por un enrutador

Dr. Ivan Olmos 27

enviarse por un enrutador� Los enrutadores llevan la secuencia de cada

par (enrutador origen, secuencia), para evitar reenviar aquellos que ya han sido procesados


� Una vez que un enrutador tiene todos los paquetes completos de todos los enrutadores, puede construir el grafo de la subred

Dr. Ivan Olmos 28

subred� Con la información anterior, puede ejecutar el

algoritmo de Dijkstra para localizar las rutas más óptimas

Enrutamiento Jerárquico

� Las subredes generalmente son grandes, por lo que mantener tablas en un enrutador correspondientes al resto de los mismos puede llegar a ser inapropiadoPara evitar este problema, se ha optado por el

Dr. Ivan Olmos 29

� Para evitar este problema, se ha optado por el enrutamiento jerárquico , en el cual, los enrutadores solo conocen la forma de enrutar paquetes dentro de cierta región (de enrutadores), pero no conocen como hacerlo fuera de ella

Enrutamiento Jerárquico

1A

1B

1C

2A 2B

2C

2D

1B 1B 1

1C 1C 1

2A 1B 2

2B 1B 3

2C 1B 3

2D 1B 4

TABLA COMPLETA PARA 1A

1A - -

1B 1B 1

1C 1C 1

TABLA JERARQUICAPARA 1A

3A

3B

4A

4B

4C

5B

5A

5E

5D

5C

2D 1B 4

3A 1C 3

3B 1C 2

4A 1C 3

4B 1C 4

4C 1C 4

5A 1C 4

5B 1C 5

5C 1B 5

5D 1C 6

5E 1C 5

1C 1C 1

2 1B 2

3 1C 2

4 1C 3

5 1C 4

DESTINOS

Enrutamiento para Máquinas Móviles

� En la actualidad, con el advenimiento de los sistemas portátiles, surge la necesidad de mantenerlos comunicados

� Básicamente, podemos identificar dos tipos de usuarios móviles :

Dr. Ivan Olmos 31

usuarios móviles :� 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 cómputo en movimiento, manteniendo la conexión en todo momento


� En el enrutamiento para máquinas móviles, se presupone que tienen una localidad base

� Una de las formas de enrutar paquetes a usuarios móviles es enviar los paquetes a su

Dr. Ivan Olmos 32

usuarios móviles es enviar los paquetes a su localidad base y ésta, se encargue de enviar la información al host móvil, en donde quiera que se encuentre


� Las localidades mantendrán dos tipos de centinelas:� Agentes foráneos , que llevan el registro de

todos los usuarios que visitan el área

Dr. Ivan Olmos 33

� Agentes de base , que llevan el registro de todos los usuarios móviles cuya base está en el área, pero que actualmente están visitando otra área


� Normalmente, cuando un sistema visita una localidad, se realiza un proceso de registro como el siguiente:� Los agentes foráneos regularmente verifican si ha

Dr. Ivan Olmos 34

� Los agentes foráneos 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


� El host móvil se registra con el agente foráneo, dando su dirección base y su dirección de enlace de datos actual, así como cierta información de seguridadEl agente foráneo localiza al agente base del host

Dr. Ivan Olmos 35

� El agente foráneo localiza al agente base del host móvil, mandando la dirección de red del agente foráneo, así como la información de seguridad (autenticación)


� El agente de base del host móvil verifica la autenticidad del mensaje con respecto al usuario móvil� Si supera la condición anterior, el agente foráneo

recibe el reconocimiento del agente de base. Acto

Dr. Ivan Olmos 36

recibe el reconocimiento del agente de base. Acto seguido, el agente foráneo registra al usuario móvil y le hace de su conocimiento el hecho

Algoritmos de Control de

Congestionamiento

Dr. Ivan Olmos 37

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 líneas de entrada de

Dr. Ivan Olmos 38

� Si varios paquetes de varias líneas de entrada de un enrutador desean salir por una sola línea� La velocidad de las CPU’s de los enrutadores� Líneas con poco ancho de banda (modernización

de solo un segmento de la subred)


� Las técnicas de control de congestionamiento suelen confundirse con el control de flujo� En el control de flujo, se implementan algoritmos para

evitar que un emisor rápido sature a un emisor lento� En contraparte, el control de congestionamiento busca que

Dr. Ivan Olmos 39

� En contraparte, el control de congestionamiento busca que la subred sea capaz de transportar el tráfico ofrecido

� La confusión se origina debido a que algunos algoritmos de congestionamiento mandan mensajes pidiendo bajar la velocidad de trans.


� De manera conceptual, los algoritmos de control de congestionamiento se dividen en dos grupos:� Los de ciclo abierto, los cuales tratan de evitar el

Dr. Ivan Olmos 40

� Los de ciclo abierto, los cuales tratan de evitar el problema con un buen diseño� Los de ciclo cerrado, los cuales tratan de resolver

el problema una vez que se ha dado

Métodos de Ciclo Abierto

Dr. Ivan Olmos 41

Conformación de Tráfico

� La naturaleza del flujo en una red no es constante, generalmente se presenta por ráfagas

� Si fuera constante, sería fácilmente predecible y, por ende, se evitarían los congestionamientosUna forma de atacar el problema es obligar a la

Dr. Ivan Olmos 42

� Una forma de atacar el problema es obligar a la transmisión de los paquetes a una tasa predecible, como en las redes ATM

� A dicha forma de trabajo se conoce como conformación de tráfico

Conformación de Tráfico

� La conformación de tráfico se puede aplicar de manera natural a las subredes de circuitos, aunque también se puede adaptar a las subredes de datagramasNormalmente se verifica que se cumpla con la tasa

Dr. Ivan Olmos 43

� Normalmente se verifica que se cumpla con la tasa promedio prometida

� Para ello, se deben analizar los alcances de los elementos de interconexión que se usen en la subred (p.e., la velocidad de los ruteadores)

Algoritmo de Cubeta con Goteo

� A los enrutadores se les ve de manera similar:� Cada enrutador tiene una capacidad para

almacenar marcos

Dr. Ivan Olmos 44

� 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

Métodos de Ciclo Cerrado

Dr. Ivan Olmos 45

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

Dr. Ivan Olmos 46

empeore� Una forma es restringir la apertura de nuevos

circuitos, técnica conocida como control de admisión

Control de Admisión

� La idea es simple: si se ha detectado un congestionamiento, no se establecen circuitos virtuales nuevos hasta que haya desaparecido el problema

Dr. Ivan Olmos 47

desaparecido el problema� También se puede optar por establecer

cuidadosamente nuevos circuitos, pero por rutas no congestionadas

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

Dr. Ivan Olmos 48

tanto a subredes de circuito virtual como de datagramas)

� La idea consiste en verificar, por medio de una variable, el flujo en un enlace


� 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á

Dr. Ivan Olmos 49

esperará un tiempo aleatorio (durante el cual hará caso omiso de nuevos paquetes de estrangulamiento), para posteriormente verificar si hay más paquetes de estrangulamiento� Si los hay, reduce aún más su velocidad. Si no los

hay, vuelve a la velocidad normal


� 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

Dr. Ivan Olmos 50

� Sin embargo, se corre el riesgo que algunos emisores hagan caso omiso de dicho mensaje

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

Dr. Ivan Olmos 51

host origen� Notemos que mientras se propaga dicho

paquete, continuará generándose la misma cantidad de flujo

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 inmediataEste enfoque obliga a destinar más memoria

Dr. Ivan Olmos 52

� Este enfoque obliga a destinar más 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 más rápida la carga

Desprendimiento de Carga

� Si a pesar de recurrir a todas las artimañas disponibles, no se puede controlar el congestionamiento, los enrutadores pueden recurrir al “desprendimiento de carga”

Dr. Ivan Olmos 53

recurrir al “desprendimiento de carga”� Esta técnica consiste en tirar o eliminar

aquellos paquetes que los enrutadores ya no pueden manejar

Documents

La Capa de Rediolmos/redes/Red-RESUMEN.pdfruta Además, se debe considerar el tráfico, para ... Calcular la trayectoria más corta a todos los demás enrutadores. ... algoritmo de