PDF de programación - Redes tema9 sistemas

La fuente original de gran parte de las imágenes presentadas en esta lección son cortesía
del texto docente “Redes y Transmisión de Datos” P. Gil, J. Pomares, F. Candelas. Servicio

de Publicaciones Universidad de Alicante.

Redes (9359). Curso 2010-11
Ingeniería Técnica en Informática de Sistemas (plan 2001)

Pablo Gil Vázquez ([email protected])
Grupo de Innovación Educativa en Automática

© 2010 GITE – IEA

Redes (9359). Curso 2010-11
Ingeniería Técnica en Informática de Sistemas (plan 2001)

BLOQUE I: INTRODUCCIÓN.

Tema 1: Introducción a las redes de computadores.

BLOQUE II. NIVEL FÍSICO.

Tema 2: Transmisión de señales.
Tema 3: Codificación de la información.
Tema 4: Medios de transmisión.

BLOQUE III. NIVEL DE ENLACE.

Tema 5: Diseño del nivel de enlace y control de errores.
Tema 6: Control de flujo en el nivel de enlace.
Tema 7: Protocolos estandarizados del nivel de enlace.

BLOQUE IV. NIVEL DE RED.

Tema 8: Diseño del nivel de red.
Tema 9: Encaminamiento en el nivel de red

Pablo Gil Vázquez ([email protected])
Grupo de Innovación Educativa en Automática

© 2010 GITE – IEA

1

Contenidos

1. Introducción.
2. Tipos y protocolos de encaminamiento.

2.1. Protocolos ‘GATEWAY’ Interior (IGP)
2.2. Protocolos ‘GATEWAY’ Exterior (EGP)
2.3. Protocolos basados en estado del enlace.
2.4. Protocolos basados en vector de distancia.

1
1
-
0
1
0
2

i


.
s
a
m
e
t
s
S
e
d
a
c
i
t



á
m
r
o

f

n

I


3. Algoritmos de calculo de ruta para encaminamiento.

i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–


s
e
d
e
R

1
1
-
0
1
0
2

.
s
a
m
e
t
s
S

e
d
a
c
i
t



i

á
m
r
o

f

n

I


i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–



s
e
d
e
R

3.1. Algoritmo de Dijkstra (estado de enlace).
3.2. Algoritmo de Bellman-Ford (vector de distancia).

4. Protocolos de Encaminamiento estandarizados.

4.1. OSPF
4.2. RIP

IX. Encaminamiento en el nivel de red

3

Introducción

Las funciones más importantes del
nivel de red son:

 Encaminamiento de la información.
 Control de la congestión.

RED 1

10.1.0.0/16

RED 3

10. 3.0.0/16

ROUTER2

RIP

Definición de encaminamiento:

ROUTER1

ROUTER5

RED 2

10.2.0.0/16 2

ROUTER3

 Calcular la ruta óptima de los paquetes

para que lleguen a su destino.

INTERNET

ROUTER4

BGP

ROUTER6

RED 1

10.1.0.0/16

ROUTER7

RED 2

10.2.0.0/16

ROUTER8

OSPF

RED 3

10. 3.0.0/16

Imágenes cortesía de “Redes y Transmisión de datos”. P. Gil y otros. Servicio de Publicaciones Universidad de Alicante.

IX. Encaminamiento en el nivel de red

4

2

Contenidos

1. Introducción.
2. Tipos y protocolos de encaminamiento.

2.1. Protocolos ‘GATEWAY’ Interior (IGP)
2.2. Protocolos ‘GATEWAY’ Exterior (EGP)
2.3. Protocolos basados en estado del enlace.
2.4. Protocolos basados en vector de distancia.

1
1
-
0
1
0
2

i


.
s
a
m
e
t
s
S
e
d
a
c
i
t



á
m
r
o

f

n

I


3. Algoritmos de calculo de ruta para encaminamiento.

3.1. Algoritmo de Dijkstra (estado de enlace).
3.2. Algoritmo de Bellman-Ford (vector de distancia).

4. Protocolos de Encaminamiento estandarizados.

4.1. OSPF
4.2. RIP

IX. Encaminamiento en el nivel de red

5

Tipos y protocolos de encaminamiento

 Protocolos de ‘gateway’ interior (IGP: Interior Gateway Protocol).

 Se usan para intercambiar información de enrutamiento dentro de un mismo

sistema de red autónomo. Un sistema autónomo, no es más que un conjunto de
redes administradas bajo un mismo dominio (es decir, por un mismo
administrador).

 Se suelen emplear en redes LAN.
 Ejemplos: RIP y OSPF.

 Protocolos de ‘gateway’ exterior (EGP: Exterior Gateway Protocol).

 Se usan para intercambiar información de enrutamiento entre distintos sistemas

de red autónomos.

 Se suelen emplear en redes WAN.
 Ejemplos: BGP.

i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–


s
e
d
e
R

1
1
-
0
1
0
2

.
s
a
m
e
t
s
S

e
d
a
c
i
t



i

á
m
r
o

f

n

I


i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–



s
e
d
e
R

IX. Encaminamiento en el nivel de red

6

3

1
1
-
0
1
0
2

i


.
s
a
m
e
t
s
S
e
d
a
c
i
t



á
m
r
o

f

n

I


i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–


s
e
d
e
R

1
1
-
0
1
0
2

.
s
a
m
e
t
s
S

e
d
a
c
i
t



i

á
m
r
o

f

n

I


i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–



s
e
d
e
R

Tipos y protocolos de encaminamiento

 Ejemplo IGP: RIP (Routing Information

Protocol) es un protocolo de
encaminamiento dinámico usado en
redes gestionadas por una única
organización (LAN).

 Su descripción y análisis está

publicada en RFC1721-1723 para la
v.2 y RFC1058 para la v.1.

 Ejemplo EGP: BGP (Border Gateway

Protocol) es un protocolo de
encaminamiento usado con conjuntos
de redes gestionadas por distintas
organizaciones (WAN).

RED 1

10.1.0.0/16

RED 3

10. 3.0.0/16

ROUTER2

RIP

ROUTER1

ROUTER5

RED 2

10.2.0.0/16 2

ROUTER3

INTERNET

ROUTER4

BGP

ROUTER6

RED 1

10.1.0.0/16

 Se emplean arquitectura TCP/IP.
 Estándar de encaminamiento en

Internet.

 Su descripción para la v.4. en RFC

1771.

IX. Encaminamiento en el nivel de red

ROUTER7

RED 2

10.2.0.0/16

ROUTER8

OSPF

RED 3

10. 3.0.0/16

Imagen cortesía de “Redes y Transmisión de datos”. P. Gil y otros. Servicio de Publicaciones

Universidad de Alicante.

7

Tipos y protocolos de encaminamiento

 Protocolos basados en vector de distancia.

 Éste tipo de protocolos permiten calcular la distancia para llegar a un nodo

destino situado en cualquier red, y la dirección necesaria para llegar hasta ese
nodo destino. Ejemplos: RIP e IGRP.

 Las rutas calculadas por unos routers pueden ser empleadas por otros.
 Los routers se intercambian periódicamente la información de rutas que

disponen. Algoritmos de cálculo de ruta: Bellman-Ford

 Protocolos basados en estado del enlace.

 Se crean tablas de encaminamiento basándose en información de la topología, a
partir de paquetes denominados de estado de enlace que se intercambian todos
los routers que forman la red para describir y determinar el estado de los
distintos enlaces. Ejemplos: OSPF

 La ventaja de estos protocolos es que cada router calcula de manera

independiente la ruta óptima hacia un nodo destino. Esto permite que la ruta
calculada por un router no depende de la calculada por otro. Algoritmo de cálculo
de ruta: Dijkstra.

IX. Encaminamiento en el nivel de red

 Ejemplos: OSPF.

8

4

Contenidos

1. Introducción.
2. Tipos y protocolos de encaminamiento.

2.1. Protocolos ‘GATEWAY’ Interior (IGP)
2.2. Protocolos ‘GATEWAY’ Exterior (EGP)
2.3. Protocolos basados en estado del enlace.
2.4. Protocolos basados en vector de distancia.

1
1
-
0
1
0
2

i


.
s
a
m
e
t
s
S
e
d
a
c
i
t



á
m
r
o

f

n

I


3. Algoritmos de calculo de ruta para encaminamiento.

i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–


s
e
d
e
R

1
1
-
0
1
0
2

.
s
a
m
e
t
s
S

e
d
a
c
i
t



i

á
m
r
o

f

n

I


i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–



s
e
d
e
R

3.1. Algoritmo de Dijkstra (estado de enlace).
3.2. Algoritmo de Bellman-Ford (vector de distancia).

4. Protocolos de Encaminamiento estandarizados.

4.1. OSPF
4.2. RIP

IX. Encaminamiento en el nivel de red

9

Algoritmos de encaminamiento: Métricas

 Número de saltos. Número de ‘routers’ o encaminadores por los que

pasará un paquete.

 Ancho de banda: Capacidad de datos del enlace. Es decir, velocidad

de transmisión máxima que soporta el enlace.

 Carga: Número de paquetes que están gestionando un router o que

está soportando un enlace en un determinado instante de tiempo.

 Coste: Valor arbitrario que suele basarse en un valor ponderado o no
obtenido a partir del ancho de banda del enlace, el coste económico o
cualquier otra medida y que es asignado por el administrador del
sistema autónomo.

 Tasa de errores: Número de bits erróneos que se producen en cada

enlace.

 MTU: Longitud máxima de datos de la trama de nivel de enlace que

puede ser aceptada por todos los enlaces de la ruta.

IX. Encaminamiento en el nivel de red

10

5

Algoritmos de encaminamiento

 Algoritmos de coste mínimo:

 Algoritmos de trayectoria más corta en coste: Dijkstra.
 Algoritmos de enrutamiento por vector de distancia: Bellman-Ford.

 Los algoritmos usados en conmutación de paquetes y redes de tipo

INTERNET basan sus decisiones en criterios de mínimo coste.

 Una variante de estos algoritmos es usado en INTERNET por el

protocolo RIP.

1
1
-
0
1
0
2

i


.
s
a
m
e
t
s
S
e
d
a
c
i
t



á
m
r
o

f

n

I


i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–


s
e
d
e
R

IX. Encaminamiento en el nivel de red

11

Algoritmos de encaminamiento

 Algoritmo de Dijkstra: Algoritmo de mínimo coste entre un nodo origen

y uno destino.

VARIABLES:

• n dž N: conjunto de nodos de la red
• s: nodo origen

• T: lista de nodos incorporados por

PASOS:

1.- INICIO:

• T={s} y L(n)=w(s,n), con n≠s.

2.- NODO SIGUIENTE:

• Encontrar el nodo x dž N, L(x)=min L(j)

con x,j no dž T.

el algoritmo

• Añadir x a T: T={s,…,x}

• w(i,j): coste del enlace directo del

3.-ACTUALIZAR EL CAMINO DE COSTE

nodo i al nodo j.

MINIMO.

• L(n): Coste en curso desde el nodo

• Calcular L(n)=min{L(n) , L(x)+w(x,n)}

s al nodo n.

con n no dž T.

• Caminos desde s al resto de nodos

4.- FINAL: Cuando todos los nodos han

de N.

sido añadidos a T.

1
1
-
0
1
0
2

.
s
a
m
e
t
s
S

e
d
a
c
i
t



i

á
m
r
o

f

n

I


i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–



s
e
d
e
R

IX. Encaminamiento en el nivel de red

12

6

Algoritmos de encaminamiento

 Ejemplo

Imagen de la imagen original cortesía de “Comunicaciones y Redes de Computadores” Williams Stallings. Ed. Prentice Hall. 6º Edición (pág. 323).

1
1
-
0
1
0
2

i


.
s
a
m
e
t
s
S
e
d
a
c
i
t



á
m
r
o

f

n

I


i



n
e
a
c
n
c
é
T
a
í
r
e
n
e
g
n



i

I

–


s
e
d
e
R

IX. Encaminamiento en el nivel de red

13

Algoritmos de encaminamiento

 Ejemplo

1
1
-
0
1
0
2

.
s
a
m
e
t
s
S

e
d
a
c
i
t



i

á
m