La Capa de Red. La Capa de Red

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 perf

8 downloads 215 Views 392KB Size

Story Transcript

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 ruta Además, se debe considerar el tráfico, para que en el caso de que sea necesario, cambiar la ruta de los datagramas

Dr. Ivan Olmos

2

1

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

Dr. Ivan Olmos

3

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 involucra a la comunidad de Internet Por otro lado, los partidarios del servicio con conexión son las compañías telefónicas

Dr. Ivan Olmos

4

2

El enfoque sin conexión „

„

„

„

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 diseño Por lo anterior, se enfocan a que los DTE realicen el control de errores y el control de flujo Además, cada paquete debe llevar la dirección de destino completa, con el fin de que estos se pueden encaminar por vías distintas, si es necesario

Dr. Ivan Olmos

5

El enfoque sin conexión „

La propuesta de la comunidad de Internet se sustenta en el hecho de que los sistemas de cómputo son más poderosos y económicos, con lo cual el costo de un diseño de una subred no sería muy elevado (no se incluyen las tareas que las computadoras tienen que realizar)

Dr. Ivan Olmos

6

3

El enfoque con conexión „

Por otro lado, las empresas telefónicas sostienen lo siguiente: ‰

‰

‰

‰

Antes de enviar datos, se debe establecer una conexión entre el emisor y el receptor Al establecerse la conexión, se puede determinar la calidad de la conexión, así como el costo del servicio La comunicación es en ambas direcciones y los paquetes se entregan en secuencia Se proporciona control de flujo

Dr. Ivan Olmos

7

Comentarios „

„

La mayor complejidad en el diseño y la implementación en el esquema orientado a conexión está en la capa de red (subred) La mayor complejidad en el diseño y la implementación en el esquema sin conexión está en la capa de transporte (en cada computadora)

Dr. Ivan Olmos

8

4

Conexión vs. Sin Conexión „

Ambos enfoques actualmente tienen su representante operativo: ‰ ‰

„

„

Internet: sin conexión 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

Dr. Ivan Olmos

9

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

5

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

11

Subredes orientadas a Conexión „

„

Aquí, los enrutadores debe mantener una tabla con todos los circuitos virtuales que estén manejando (se asocia a cada circuito un número) Cada paquete que viaje, tiene que contener un campo para un número de circuito virtual, además de los números de secuencia, sumas de comprobación...

Dr. Ivan Olmos

12

6

Subredes orientadas a Conexión „

„

„

Cuando un enrutador recibe un paquete, conoce la línea por la cual llegó así como el correspondiente número de circuito virtual Cada computadora, al establecer una conexión de red, hace uso de una dirección libre de circuito virtual Dichos números de dirección son independientes de un sistema a otro

Dr. Ivan Olmos

13

Subredes orientadas a Conexión „

„

Como cada sistema es capaz de establecer una conexión, 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 dirección pueda purgarse de la tabla de los enrutadores

Dr. Ivan Olmos

14

7

Subredes basadas en Datagramas „

„

„

En este esquema, los enrutadores tienen una tabla que indica la línea de salida a usar para cada enrutador de destino posible Los datagramas contienen la dirección de destino completa En redes grandes, las direcciones pueden ser de varios bytes

Dr. Ivan Olmos

15

Ventajas y Desventajas „

„

Por una parte, el tamaño de las direcciones en cada paquete significa una carga extra de información, 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

8

Ventajas y Desventajas „

„

Otro balance es el tiempo que se requiere para establecer un circuito al inicio de la comunicación; más 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 más 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 más 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 perderán los paquetes que en ese momento se encontraban en el enrutador Dr. Ivan Olmos

18

9

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 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 entrada En una subred de circuitos virtuales, la decisión se toma al momento de establecer el camino del circuito (enrutamiento de sesión)

Dr. Ivan Olmos

20

10

Algoritmos de Enrutamiento „

Deben ofrecer propiedades como: ‰ ‰ ‰ ‰ ‰ ‰

Corrección Sencillez Robustez Estabilidad Equitatividad Optimalidad

Dr. Ivan Olmos

21

Algoritmos de Enrutamiento „

„

Los algoritmos deben planearse para soportar los cambios de la topología de la subred así como el tráfico sin requerir la paralización de actividades También se busca minimizar el retardo medio de los paquete así como aumentar al máximo el rendimiento de la red (normalmente se busca minimizar el número 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 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..) Dr. Ivan Olmos

23

Algoritmos de Enrutamiento „

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 ó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 optimación, se puede deducir que todas las rutas óptimas a un destino común forman un árbol con raíz 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 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 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...

Dr. Ivan Olmos

26

13

Algoritmo de Dijkstra „

„

Uno de los algoritmos más populares para encontrar las trayectorias más cortas (en base a cierta métrica), es el algoritmo de Dijkstra El algoritmo es el siguiente: ‰

‰

Suponga que se desea encontrar la ruta más corta entre el nodo A y el nodo Z de un grafo Sea T el conjunto de vértices 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 vértice v al vértice x Dr. Ivan Olmos

27

Algoritmo de Dijkstra Para todo x ∈ T | x ≠ A hacer:

1. •

L[x] = ∞, C[x] = ∅

L[A] = 0, C[A] = A Sea v = A, T = T – {A} Si v = Z, finalizar (camino mínimo de A a Z: C[v] con longitud L[v]) Para cada vértice x adyacente a v | x ∈ T hacer:

2. 3. 4.

5. • •

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 Hacer:

6. • •

7.

v = min {L[x] | x ∈ T} T = T – {v}

Regresar a paso 4

29

Dr. Ivan Olmos

Algoritmo de Dijkstra „

Por ejemplo, sea el siguiente grafo, obtener el camino mínimo de A a D B 2

C

7 2 E

A 1

6

2

F

3

2

D 2

2

4

G

H Dr. Ivan Olmos

30

15

Algoritmo de Dijkstra T 1

2

3

4

5

6

7

8

A

B

C

D

E

F

G

L

0













H ∞

C

A















L

0

2









6



C

A

AB









AG



L

0

2

9



4



6



C

A

AB

ABC



ABE



AG



L

0

2

9



4

6

5



C

A

AB

ABC



ABE

ABEF

ABEG



L

0

2

9



4

6

5

9

C

A

AB

ABC



ABE

ABEF

ABEG

ABEGH

L

0

2

9



4

6

5

8

C

A

AB

ABC



ABE

ABEF

ABEG

ABEFH

L

0

2

9

10

4

6

5

8

C

A

AB

ABC

ABEFHD

ABE

ABEF

ABEG

ABEFH

L

0

2

9

10

4

6

5

8

C

A

AB

ABC

ABEFHD

ABE

ABEF

ABEG

ABEFH

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: ‰

‰

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ó

Dr. Ivan Olmos

32

16

Camino más corto por Inundación „

„ „

Una forma más efectiva es la inundación selectiva, en la cual el paquete solo es enviado por las direcciones más cercanas al destino En general, la inundación no es eficiente, pero sí muy robusta En este esquema, siempre se es posible encontrar la ruta más corta, debido a que se prueban todas las rutas posibles en paralelo

Dr. Ivan Olmos

33

Comentario „

„

Tanto el algoritmo de Dijkstra, como el de inundación, consideran exclusivamente la topología 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 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

Dr. Ivan Olmos

35

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

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

B

C

D

E

F

-

9 AB

4 ABC

1 ABFD

7 AE

4 AEF

B

9 BA

-

8 BC

3 BFD

2 BFE

4 BF

C

4 CBA

8 CB

-

3 CD

3 CE

2 CEF

D

1 DF BA

3 DFB

3 DC

-

3 DCE

4 DF

7 EA

2 EFB

3 EC

3 ECD

-

5 EF

4 FEA

4 FB

2 FEC

4 FD

5 FE

-

A B

C

20

20 A

10 20

20 E

D

20 50

10 F

E F

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 número 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 información anterior, se puede obtener el flujo total λ que circula por cada enlace Además, si suponemos un tamaño medio de paquete µ = 800 bits, se puede obtener el número medio de paquetes, µC, para cada enlace

Dr. Ivan Olmos

39

Enrutamiento basado en el Flujo „

„

„

De esta información, se puede derivar el retardo medio por línea, haciendo uso de la teoría de colas: T = 1 / (µC - λ) Con toda la información anterior, se puede obtener el retardo promedio considerando toda la subred Para el ejemplo anterior, se tiene la siguiente tabla (el peso representa la relación 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

Línea

λi (paq / seg)

Ci (kbps)

µCi (paq / seg)

Ti (mseg)

Peso

1

AB

14

20

25

91

0.171

2

BC

12

20

25

77

0.146

3

CD

6

10

12.5

154

0.073

4

AE

11

20

25

71

0.134

5

EF

13

50

62.5

20

0.159

6

FD

8

10

12.5

222

0.098

7

BF

10

20

25

67

0.122

8

EC

8

20

25

59

0.098

Dr. Ivan Olmos

41

Enrutamiento Dinámico

Dr. Ivan Olmos

42

21

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 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 línea 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 línea de salida al destino así como la estimación del tiempo o distancia a ese destino (la métrica 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 Además, 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

B

A

F

C

G

E

I

J

K

D

H

L

A B C D E F G H I J K L

Retardo del nodo J al nodo x:

Nuevo retardo estimado

A

I

H

K

0

24

20

21

8

A

12

36

31

28

20

A

25

18

19

36

28

I

40

27

8

24

20

H I

Línea

14

7

30

22

17

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

8

10

12

6

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 Además, se tiene un problema grave, conocido como conteo a infinito

47

Dr. Ivan Olmos

Enrutamiento por Vector de Distancia A CASO CUANDO SE DA DE ALTA EL NODO A

A CASO CUANDO SE DA DE BAJA EL NODO A

B

C

D

E

∞ 1 1 1 1

∞ ∞ 2 2 2

∞ ∞ ∞ 3 3

∞ ∞ ∞ ∞ 4

B

C

D

E

v

v

v

v

v

1 3 3 5 5 M

v

2 2 4 4 6 M

v

3 3 3 5 5 M

Dr. Ivan Olmos

v

4 4 4 4 6 M

Inicialmente Tras 1 intercambio Tras 2 intercambios Tras 3 intercambios Tras 4 intercambios

Inicialmente Tras 1 intercambio Tras 2 intercambios Tras 3 intercambios Tras 4 intercambios M 48

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 demás enrutadores Calcular la trayectoria más corta a todos los demás enrutadores Dr. Ivan Olmos

50

25

Enrutamiento por Estado de Enlace „

„ „

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

Dr. Ivan Olmos

51

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 más pronto posible Con ello, el enrutador X puede calcular el retardo dividiendo entre dos el tiempo tomado por el paquete de eco

Dr. Ivan Olmos

52

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 línea menos saturada, y por ende, facilitar el flujo de los paquetes Sin embargo, puede provocar que varios enrutadores seleccionen casi al mismo tiempo la línea menos saturada, con lo cual, se convertirá en la más suturada, induciendo nuevamente al problema de líneas saturadas

Dr. Ivan Olmos

54

27

Enrutamiento por Estado de Enlace „

Una vez recabada la información anterior, se construyen los paquetes a enviar a los vecinos, conteniendo: ‰ ‰ ‰ ‰

Identidad del transmisor Número de secuencia Edad Lista de vecinos, citando los retardos asociados

55

Dr. Ivan Olmos

Enrutamiento por Estado de Enlace

B

A

B

C

D

E

F

Sec.

Sec.

Sec.

Sec.

Sec.

Sec.

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

C

2

4

3 D

A 1

5 E

6 8

7 F

Dr. Ivan Olmos

56

28

Enrutamiento por Estado de Enlace „

„

„

Una vez que cada enrutador tenga sus paquetes construidos, falta distribuirlos La distribución es un proceso delicado, ya que puede inducir a inconsistencias, máquinas inalcanzables, ciclos, etc. En primera instancia, se puede usar inundación

Dr. Ivan Olmos

57

Enrutamiento por Estado de Enlace „

„

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 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 número se secuencia (se llegue a su máximo), se suelen emplear números grandes (por ejemplo, 232) Además, existen problemas como: ‰

‰

Un enrutador deje de funcionar, con lo cual, se reiniciará su número de secuencia Se puede corromper el número de secuencia al momento de ser enviado

Dr. Ivan Olmos

59

Enrutamiento por Estado de Enlace „

„

La solución a dichos problemas es incluir una “edad” a cada paquete; así, después de determinado tiempo, la información proveniente del enrutador será descartada (conteo de forma descendiente) Lo anterior es posible debido a que la generación 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 envíe 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 más 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 información anterior, puede ejecutar el algoritmo de Dijkstra para localizar las rutas más óptimas

Dr. Ivan Olmos

62

31

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 inapropiado 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

63

Dr. Ivan Olmos

Enrutamiento Jerárquico TABLA COMPLETA PARA 1A

1B

1B

1B

1

1C

1C

1

2A

1B

2

2B

1B

3

1A

-

-

2C

1B

3

1B

1B

1

2D

1B

4

1C

1C

1

3A

1C

3

2

1B

2

3B

1C

2

3

1C

2

4A

1C

3

4

1C

3

5C

4B

1C

4

5

1C

4

5D

4C

1C

4

5A

1C

4

5B

1C

5

5C

1B

5

5D

1C

6

5E

1C

5

2A 2B

1A

2C

1C

2D

3A

4A 3B

5A

4B 4C

DESTINOS

5B

5E

TABLA JERARQUICA PARA 1A

32

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: ‰

‰

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

Dr. Ivan Olmos

65

Enrutamiento para Máquinas Móviles „

„

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 localidad base y ésta, se encargue de enviar la información al host móvil, en donde quiera que se encuentre

Dr. Ivan Olmos

66

33

Enrutamiento para Máquinas Móviles „

Las localidades mantendrán dos tipos de centinelas: ‰

‰

Agentes foráneos, que llevan el registro de todos los usuarios que visitan el área 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

Dr. Ivan Olmos

67

Enrutamiento para Máquinas Móviles „

Normalmente, cuando un sistema visita una localidad, se realiza un proceso de registro como el siguiente: ‰

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

Dr. Ivan Olmos

68

34

Enrutamiento para Máquinas Móviles ‰

‰

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 seguridad 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)

Dr. Ivan Olmos

69

Enrutamiento para Máquinas Móviles ‰

‰

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 seguido, el agente foráneo registra al usuario móvil y le hace de su conocimiento el hecho

Dr. Ivan Olmos

70

35

Enrutamiento para Máquinas Móviles „

„

Con lo anterior, si se generan paquetes para el usuario móvil, el agente de base intercepta dichos paquetes, enviándolos a la nueva localidad (temporal) del usuario móvil El agente foráneo donde se encuentra el usuario móvil recibirá dichos paquetes, retirará la información añadida por el agente de base y, por medio de un marco de enlace de datos, se lo enviará al usuario móvil

Dr. Ivan Olmos

71

Enrutamiento para Máquinas Móviles „

Además, el agente de base le indicará al transmisor que envíe el resto de los paquetes encapsulándolos para el agente foráneo donde se encuentra el usuario móvil

Dr. Ivan Olmos

72

36

Enrutamiento por Difusión „

„

Cuando se desea enviar información a un conjunto de host, será necesario implementar alguna técnica de difusión Hasta el momento, dos técnicas saltan para implementarse: ‰

‰

Envío simultáneo de un paquete a todos los destinos (difusión) Inundación

Dr. Ivan Olmos

73

Enrutamiento por Difusión „ „ „

„

Otra forma de difusión 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) Además, en las nuevas copias solo se indican los destinos asociados a cada ruta Dr. Ivan Olmos

74

37

Enrutamiento por Árbol de Extensión „

„

En los árboles de extensión, se conectan de manera lógica 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

Reenvío por Trayectoria Invertida „

„

En esta técnica, se busca simular el comportamiento de un árbol de extensión, a pesar de no conocerlo explícitamente Para ello, cuando un enrutador recibe un paquete de difusión, verifica si este llegó por la línea 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

Reenvío 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 Multitransmisión „

„

„

Otra técnica en la cuál se puede enviar información a un grupo de host Aquí es necesario que los host se reúnan en grupos (numerados), acción 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 Multitransmisión „

„

En base a los grupos asociados a cada enrutador, se forman árboles de extensión que cubran cada enrutador de la subred Con ello, cuando se realice una multitransmisión a un grupo o grupos determinados, se seguirán los árboles de extensión para llegar a los destinos

79

Dr. Ivan Olmos

Enrutamiento por Multitransmisión

1

1

2

2

1, 2 1, 2

2

1, 2

2

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 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)

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 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 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.

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 diseño 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 algún 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 más 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

Métodos de Ciclo Abierto

Dr. Ivan Olmos

89

Prevención „

„

„

Éstos métodos tratan de alcanzar su meta implementando ciertas políticas Por ejemplo, en la capa de enlace de datos se busca implementar temporizadores que eviten hasta cierto grado precipitar el inicio de una retransmisión También, se busca que los acuses de recibo no generen una carga extra a la red

Dr. Ivan Olmos

90

45

Prevención „

„

En la capa de red, se busca encontrar, por ejemplo, tamaños de colas de espera para los enrutadores, tanto para las líneas de salida como las de entrada Lo anterior debe tener en cuenta un tamaño que no induzca a que los paquetes en espera finalicen sus temporizadores

Dr. Ivan Olmos

91

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 congestionamientos 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

Dr. Ivan Olmos

92

46

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 datagramas 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)

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 envío de un emisor sin que se produzcan pérdidas en los enrutadores Otra variante de éste esquema es la cubeta con fichas, la cual permite acelerar el goteo si existen ráfagas de flujo, así como la reservación de transmisión para emisores Una variante interesante en la cubeta con fichas, es que está solo pierde fichas, no paquetes

Dr. Ivan Olmos

96

48

Métodos 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, técnica conocida como control de admisión

Dr. Ivan Olmos

98

49

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 También se puede optar por establecer cuidadosamente nuevos circuitos, pero por rutas no congestionadas

Dr. Ivan Olmos

99

Control de Admisión „

„

Otra forma alternativa, dentro de los circuitos virtuales, es negociar un acuerdo sobre el volumen y tráfico para cada circuito, con lo cual se reservarán recursos por donde pase el circuito Sin embargo, esta última técnica 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, indicándole que baje el ritmo de transmisión Por otro lado, marca un bit en el paquete de salida, para evitar que más 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 más paquetes de estrangulamiento Si los hay, reduce aún más 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 línea de salida se encuentre desocupada, se manda el paquete almacenado en la cola correspondiente Sin embargo, notemos que los paquetes pueden diferir en tamaño, por lo que los host con paquetes más grandes obtendrán un ancho de banda mayor que los host con paquetes de menor tamaño

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, envíe byte a byte De esta manera, el tamaño de los paquetes será independiente 1

4

2

5

3

6

7

9

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á generándose 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 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

Dr. Ivan Olmos

108

54

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” Esta técnica consiste en tirar o eliminar aquellos paquetes que los enrutadores ya no pueden manejar

Dr. Ivan Olmos

109

Dr. Ivan Olmos

110

Interredes

55

Interredes „

„

„

Debido a que se tienen diversas tecnologías de red, surge el problema de cómo comunicar estas tecnologías Cuando se unen dos o más redes, forman una interred Se pueden usar diversos dispositivos de interconexión, los cuales trabajan a diversos niveles (de enlace de datos, de red, ...)

Dr. Ivan Olmos

111

Interredes „

Ejemplos de elementos de interconexión son: ‰

‰

Repetidores, los cuales se encargan de amplificar una señal de entrada (a nivel físico) Los puentes, los cuales reciben, almacenan y reenvían marcos al nivel de la capa de enlace de datos. Además, 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 línea de salida. Las líneas de salida pueden pertenecer a redes diferentes y usar protocolos distintos Existen otros dispositivos, como las pasarelas de transporte y las de aplicación

Dr. Ivan Olmos

113

Interredes „

„

„

El manejo de la interconexión de dos redes distintas es complejo Dentro de las combinaciones, existe el caso cuando, tanto el host origen como el destino, están en la misma clase de red Una problemática 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 Túnel „

„

Por ejemplo, si deseamos enviar un paquete IP de una red Ethernet a otra, se coloca primero el paquete IP en un marco Ethernet; después, 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 través de toda la subred y, al llegar a la red destino, simplemente desempaquetarlo y entregarlo

Dr. Ivan Olmos

115

Fragmentación „

„

Una complicación adicional surge al trabajar con interredes, ya que estas suelen manejar tamaños de paquetes distintos Para atacar este problema, se pueden llevar a cabo dos esquemas de fragmentación: ‰ ‰

Transparente No transparente

Dr. Ivan Olmos

116

58

Fragmentación Transparente „

„

„

En este esquema, cuando un paquete es demasiado grande para enviarse, se fragmenta, pero es reensamblado inmediatamente del otro lado de la línea De esta manera, se hace transparente el paso de un paquete a través de la red Sin embargo, tiene el inconveniente de que cada elemento de interconexión (pasarelas) debe tener la capacidad de desensamblar y reensamblar paquetes, y no los host Dr. Ivan Olmos

117

Fragmentación no transparente „

„

„

Por el contrario, este esquema, desde un inicio, fragmenta al paquete para ser enviados a través 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 vías alternas y no por una sola vía Dr. Ivan Olmos

118

59

SUBRED

INTERRED

INTERRED

60

Get in touch

Social

© Copyright 2013 - 2024 MYDOKUMENT.COM - All rights reserved.