PDF de programación - 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 perfectamente el

esquema de la subred para escoger la mejor
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

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

Conexión vs. Sin Conexión

 Ambos enfoques actualmente tienen su

representante operativo:
Internet: sin conexión
ATM: con 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

5

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

6

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

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

9

Algoritmos de Enrutamiento

 Deben ofrecer propiedades como:

Corrección
Sencillez
Robustez
Robustez
Estabilidad
Equitatividad
Optimalidad

Dr. Ivan Olmos

10

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

11

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

12

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

13

Algoritmo de Dijkstra

1. Para todo x ˛ T | x „ A hacer:

•

L[x] = ¥

, C[x] = ˘

L[A] = 0, C[A] = A

2.
3. Sea v = A, T = T – {A}
4. Si v = Z, finalizar (camino mínimo de A a Z: C[v]
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}

Dr. Ivan Olmos

14

Algoritmo de Dijkstra

6. Hacer:

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

•

•

7. Regresar a paso 4
7. Regresar a paso 4

Dr. Ivan Olmos

15

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

16

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

17

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
La matriz de capacidad C 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

18

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
Enrutamiento por vector de distancia
Enrutamiento por estado de enlace

Dr. Ivan Olmos

20

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

21

Enrutamiento por Vector de Distancia

A

E

I

B

F

J

C

G

K

D

H

L

40
40

14

23

25

12

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

24

29

18

17

21

9

I
24

36

18

27
27

7

20

31

20

0

11

22

33

H
20

31

19

8
8

30

19

6

0

14

7

22

9

K
21

28

36

24
24

22

40

31

19

22

10

0

9

Nuevo retardo

estimado

Línea

8

20

28

20
20

17

30

18

12

10

0

6

15

A

A

I

H
H

I

I

H

H

I

-

K

K

Retardo del nodo
J al nodo x:

8 10 12 6

Nuevo tabla de
enrutamiento

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

23

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

24

Enrutamiento por Estado de Enlace

A

4
4

5

B

2

C

1

6

E

8

F

3

7

D

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

Dr. Ivan Olmos

25

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,
que puede inducir a inconsistencias,
máquinas inalcanzables, ciclos, etc.
 En primera instancia, se puede usar

inundación

Dr. Ivan Olmos

26

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

27

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
subred

 Con la información anterior, p