PDF de programación - Qué es Internet

¿Qué es Internet?

Juan Díez-Yanguas Barber

Contenidos

Introducción y algoritmo de Dijkstra
Open Shortest Path Protocol (OSPF)
Protocolo de Pasarela Frontera (BGP)
Punto Neutro
Core Router
Tipos de acuerdo: Peering y Tránsito IP
ISP Tier 1, 2, 3
Topología
Cables Submarinos

2

¿Qué es Internet?

Tiene sus orígenes en 1969 con
ARPANET (Advanced Research Projects
Agency Network)
Conglomerado de múltiples redes de
varias empresas

3

Internet como conjunto de redes

AS 1239
Sprint

AS 3549

Global Crossing

AS 8297
Teleglobe

AS: Autonomous System
BGP: Border Gateway Protocol

BGP

4

Sistema Autónomo

Compuesto de un conjunto de encaminadores
y redes gestionados por una única organización
Los encaminadores intercambian información
mediante protocolo de encaminamiento común
Salvo avería un AS está conectado (teoría de
grafos)
IRP: Interior Router Protocol
ERP: Exterior Router Protocol

5

Sistema Autónomo

Protocolo implementado dentro de un AS no necesita ser
implementado fuera

Subnetwork

1.2

R3

R2

Subnetwork

2.1

R6

Subnetwork

1.1

R5

Subnetwork

2.2

Subnetwork

1.3

R1

R4

Subnetwork

1.4

Autonomous System 1

Interior router protocol
Exterior router protocol

R7

Subnetwork

2.4

R8

Subnetwork

2.3

Autonomous System 2

Figure 19.5 Application of Exterior and Interior Routing Protocols

6

Algoritmo de Dijkstra

Encontrar las rutas más cortas entre
un nodo origen dado y todos los
demás nodos, desarrollando los
caminos en orden creciente de
longitud

7

Algoritmo de Dijkstra

Actúa en etapas
Tras la etapa k-ésima se han determinado los caminos
más cortos a los nodos k más cercanos al origen
especificado
Los nodos más cercanos se almacenan en conjunto T
Paso k+1 se añade a T todo aquel nodo que presente
el camino más corto desde el nodo origen y no este
ya incluido
A medida que se incorporan nodos a T se define su
camino desde el origen

8

Algoritmo de Dijkstra

(Formalmente)

N = Conjunto de nodos en la red
s = Nodo origen
T = Conjunto de nodos incorporados
por el algoritmo

9

Algoritmo de Dijkstra

(Formalmente)

w(i, j) = Coste desde nodo i hasta j

w(i, i) = 0
w(i, j) = ∞ Si i y j no están
directamente conectados
w(i, j) ≥ 0 Si i y j están directamente
conectados

10

Algoritmo de Dijkstra

(Formalmente)

L(n) = Coste en curso obtenido para el
camino de mínimo coste del nodo s al
nodo n
Al finalizar el algoritmo L(n)
corresponde al del camino de mínimo
coste de s a n en el grafo

11

Algoritmo de Dijkstra

(Formalmente)

Tres pasos
Repetir pasos 2 y 3 hasta T = N
T = N: Las rutas finales han sido
asignadas a todos los nodos de la red

12

Algoritmo de Dijkstra

(Formalmente)

Inicialización

T = {s} T solo tiene nodo origen
L(n) = w(s, n), para n ≠ s Coste inicial
de rutas a los nodos vecinos es el
asociado a los enlaces

13

Algoritmo de Dijkstra

(Formalmente)

Obtención del siguiente nodo

Buscar nodo vecino que no este en T con
camino de menor coste desde s.
También se incorpora el enlace desde ese nodo
hasta un nodo de T que forma parte del camino
Añadir x a T incorporando también enlace
desde x que contribuye a L(x) como la
componente de menor coste (el último salto en
la ruta)
Encontrar x /2 T tal que L(x) = min
j /2T

L(j)

14

Algoritmo de Dijkstra

(Formalmente)

Actualización de los caminos de
mínimo coste
Si el último término es el mínimo, el
camino desde s hasta n es ahora el
camino desde s hasta x concatenado
con el enlace desde x hasta n

L(n) = min [L(n), L(x) + w(x, n)] para todo n /2 T

15

Algoritmo de Dijkstra (Ejemplo)

8

2

5

3

1
7

1

2

3
6

3

2

2

3

3

1

1

5
8

2

6

4

5

4

1
1

16

Algoritmo de Dijkstra (Ejemplo)

17

Algoritmo de Dijkstra (Ejemplo)

It
1
2
3
4
5
6

1

T

{1}
{1, 4}
{1, 2, 4}
{1, 2, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}

8

2

2

5

2

4

2
3

1
7

L(2)
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]

3
6

3

3

1

1

L(3)
5 [1-3]
4 [1-4-3]
4 [1-4-3]
3 [1-4-5-3]
3 [1-4-5-3]
3 [1-4-5-3]

L(4)
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]

L(5)

∞ [-----]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]

L(6)

∞ [-----]
∞ [-----]
∞ [-----]
4 [1-4-5-6]
4 [1-4-5-6]
4 [1-4-5-6]

1

Nodo en T

Árbol Expansión

3

1

1

5

5

8

2

4

6

17

Algoritmo de Dijkstra (Ejemplo)

It
1
2
3
4
5
6

1

T

{1}
{1, 4}
{1, 2, 4}
{1, 2, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}

8

2

2

5

2

4

2
3

1
7

L(2)
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]

3
6

3

3

1

1

L(3)
5 [1-3]
4 [1-4-3]
4 [1-4-3]
3 [1-4-5-3]
3 [1-4-5-3]
3 [1-4-5-3]

L(4)
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]

L(5)

∞ [-----]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]

L(6)

∞ [-----]
∞ [-----]
∞ [-----]
4 [1-4-5-6]
4 [1-4-5-6]
4 [1-4-5-6]

1

Nodo en T

Árbol Expansión

3

1

1

5

5

8

2

4

6

17

Algoritmo de Dijkstra (Ejemplo)

It
1
2
3
4
5
6

1

T

{1}
{1, 4}
{1, 2, 4}
{1, 2, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}

8

2

2

5

2

4

2
3

1
7

L(2)
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]

3
6

3

3

1

1

L(3)
5 [1-3]
4 [1-4-3]
4 [1-4-3]
3 [1-4-5-3]
3 [1-4-5-3]
3 [1-4-5-3]

L(4)
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]

L(5)

∞ [-----]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]

L(6)

∞ [-----]
∞ [-----]
∞ [-----]
4 [1-4-5-6]
4 [1-4-5-6]
4 [1-4-5-6]

1

Nodo en T

Árbol Expansión

3

1

1

5

5

8

2

4

6

17

Algoritmo de Dijkstra (Ejemplo)

It
1
2
3
4
5
6

1

T

{1}
{1, 4}
{1, 2, 4}
{1, 2, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}

8

2

2

5

2

4

2
3

1
7

L(2)
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]

3
6

3

3

1

1

L(3)
5 [1-3]
4 [1-4-3]
4 [1-4-3]
3 [1-4-5-3]
3 [1-4-5-3]
3 [1-4-5-3]

L(4)
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]

L(5)

∞ [-----]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]

L(6)

∞ [-----]
∞ [-----]
∞ [-----]
4 [1-4-5-6]
4 [1-4-5-6]
4 [1-4-5-6]

1

Nodo en T

Árbol Expansión

3

1

1

5

5

8

2

4

6

17

Algoritmo de Dijkstra (Ejemplo)

It
1
2
3
4
5
6

1

T

{1}
{1, 4}
{1, 2, 4}
{1, 2, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}

8

2

2

5

2

4

2
3

1
7

L(2)
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]

3
6

3

3

1

1

L(3)
5 [1-3]
4 [1-4-3]
4 [1-4-3]
3 [1-4-5-3]
3 [1-4-5-3]
3 [1-4-5-3]

L(4)
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]

L(5)

∞ [-----]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]

L(6)

∞ [-----]
∞ [-----]
∞ [-----]
4 [1-4-5-6]
4 [1-4-5-6]
4 [1-4-5-6]

1

Nodo en T

Árbol Expansión

3

1

1

5

5

8

2

4

6

17

Algoritmo de Dijkstra (Ejemplo)

It
1
2
3
4
5
6

1

T

{1}
{1, 4}
{1, 2, 4}
{1, 2, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}

8

2

2

5

2

4

2
3

1
7

L(2)
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]

3
6

3

3

1

1

L(3)
5 [1-3]
4 [1-4-3]
4 [1-4-3]
3 [1-4-5-3]
3 [1-4-5-3]
3 [1-4-5-3]

L(4)
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]

L(5)

∞ [-----]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]

L(6)

∞ [-----]
∞ [-----]
∞ [-----]
4 [1-4-5-6]
4 [1-4-5-6]
4 [1-4-5-6]

1

Nodo en T

Árbol Expansión

3

1

1

5

5

8

2

4

6

17

Algoritmo de Dijkstra (Ejemplo)

It
1
2
3
4
5
6

1

T

{1}
{1, 4}
{1, 2, 4}
{1, 2, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}

8

2

2

5

2

4

2
3

1
7

L(2)
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]
2 [1-2]

3
6

3

3

1

1

L(3)
5 [1-3]
4 [1-4-3]
4 [1-4-3]
3 [1-4-5-3]
3 [1-4-5-3]
3 [1-4-5-3]

L(4)
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]
1 [1-4]

L(5)

∞ [-----]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]
2 [1-4-5]

L(6)

∞ [-----]
∞ [-----]
∞ [-----]
4 [1-4-5-6]
4 [1-4-5-6]
4 [1-4-5-6]

1

Nodo en T

Árbol Expansión

3

1

1

5

5

8

2

4

6

17

Algoritmo de Dijkstra (Ejemplo)

V2
2

3
6

V3
5

2 2

3

3

1

1

V6

•

5
8

2

4

1
V4

1
1

T = {1}

•
V5

0

V1

5

3

1
7

V2
2

3
6

V3
4

2 2

3

3

1

1

V6

•

5
8

2

4

1
V4

1
1

2
V5

T = {1, 4}

8

2

8

2

8

2

8

2

5

3

1
7

5

3

1
7

0

V1

0

V1

0

V1

8

2

8

2

5

3

1
7

V2
2

3
6

V3
4

2 2

3

3

1

1

1
1

1
V4
T = {1, 2, 4}

2
V5

5

V2
2

3
6

V3
3

3

2 2

3

3

1

1

1
1

2
V5
T = {1, 2, 3, 4, 5, 6}

V6

•

4

V6

5
8

2

5
8

2

4

4

V2
2

3
6

2 2

3

3

V3
3

5
8

4

V6

1

5

V2
2

3
6

V3
3

5
8

3

2 2

3

1

4

V6

4

2

1
Table 12.2 Example of Least-Cost Routing Algorithms (using Figure 12.2)
1
V4

1
V4

V1

V1

1
7

1
7

1
1

0

0

3

1

2

4

2
V5

2
V5

1
1

1
V4

T = {1, 2, 3, 4, 5}

T = {1, 2, 4, 5}

(a) Dijkstra'a Algorithm (s = 1)

Iteration

1
2
3
4
5
6

T

L(4)

L(3)

L(2)

Path
1 - 3

L(6)
•
Figure 12.10 Dijkstra's Algorithm Applied to Graph of Figure 12.2
•
•
4
4
4

{1}
{1, 4}
{1, 2, 4}
{1, 2, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}

1 - 4 - 5
1 - 4 - 5
1 - 4 - 5
1 - 4 - 5
1 - 4 - 5

Path
1 - 4
1 - 4
1 - 4
1 - 4
1 - 4
1 - 4

Path
1 - 2
1 - 2
1 - 2
1 - 2
1 - 2
1 - 2

1 - 4 - 5 - 3
1 - 4 - 5 - 3
1 - 4 - 5 - 3

L(5)
•
2
2
2
2
2

1 - 4 - 3
1 - 4 - 3

Path
—

2
2
2
2
2
2

5
4
4
3
3
3

1
1
1
1
1
1

Path
—
—
—

1 - 4 - 5 - 6
1 - 4 - 5 - 6
1 - 4 - 5 - 6

(b) Bellman-Ford Algorithm (s = 1)

h

Lh(2)

Path

Lh(3)

Path

18
Lh(4)

Path

Lh(5)

Path

Lh(6)

Path

Estrategias de encaminamiento IRP

- Vector distancia -

Cada nodo intercambia información con
nodos vecinos (nodos directamente
conectados a la misma red)
Cada nodo mantiene un vector de costes
por enlace para cada red directamente
conectada y vectores de distancia y de
siguiente salto para cada destino
Se usa en RIP (Routing Information Protocol)

19

Estrategias de encaminamiento IRP

- Estado del enlace -

Al iniciar el nodo este calcula los costes del
enlace en cada una de sus interfaces de red
El encaminador anuncia el conjunto de costes de
enlace a los demás nodos de la topología de red
(no sólo vecinos)
El encaminador monitoriza los costes de los
enlaces
Ante un cambio significativo el nodo notifica de
nuevo su conjunto de costes de enlace a todos
los nodos de la topología

20

Estrategias de encaminamiento IRP

- Estado del enlace -

Cada nodo puede construir la topología completa
y calcular el camino más corto a la red de destino
Los nodos construyen sus tablas de
encaminamient