capítulo 4 - capa de red

Capa de Red 4-1

Captulo 4: Capa Red - I ELO322: Redes de Computadores

Agustn J. Gonzlez Este material est basado en:

Material de apoyo al texto Computer Networking: A Top Down Approach Featuring the Internet. Jim

Kurose, Keith Ross.

Capa de Red 4-2

Captulo 4: Capa de Red Objetivos de captulo: Entender los principios detrs de los servicios de la capa de red: Ruteo (seleccin de la ruta) Cmo funciona un router Tpicos avanzados: IPv6 Aplicacin e implementacin en la Internet

Capa de Red 4-3

Captulo 4: Capa de Red 4.1 Introduccin 4.2 Circuitos virtuales

y redes de datagramas 4.3 Qu hay dentro de

un router? 4.4 IP: Internet

Protocol Formato de Datagrama Direccionamiento IPv4 ICMP IPv6

4.5 Algoritmos de ruteo Estado de enlace Vector de Distancias Ruteo Jerrquico

4.6 Ruteo en Internet RIP OSPF BGP

4.7 Ruteo Broadcast y multicast

Capa de Red 4-4

Capa red (network layer) Transporta segmentos de fuente

a destino En origen encapsula segmentos

en datagramas En destino entrega segmentos a

capa transporte Hay protocolos capa red

(network) en cada terminal y router

Router examina campos de cabecera en todos los datagramas IP que pasan por l

network data link physical








application transport network data link physical

application transport network data link physical

Capa de Red 4-5

Funciones claves de la capa de red Ruteo: determinar ruta para los paquetes desde fuente a destino. Algoritmos de Ruteo Re-envo (forwarding): mover paquetes desde una entrada del router a la salida apropiada.

Analoga: Ruteo: proceso de

planear viaje de fuente a destino

Re-envo (forwarding): proceso de transitar a travs de una interseccin

Capa de Red 4-6

Funciones de ruteo y reenvo

Capa de Red 4-7

Establecimiento de Conexin Fuera de ruteo y re-envo, el establecimiento de la

conexin es la 3ra funcin de importancia en algunas arquitecturas de redes: ATM, frame relay, X.25

En algunas redes, antes que los datagramas fluyan, los dos hosts y los routers que intervienen establecen una conexin virtual Routers se involucran en las conexiones

Diferencia en servicio de conexin de capas red y transporte: Red: conexin entre dos terminales (hosts) Transporte: conexin entre dos procesos

Capa de Red 4-8

Modelos de servicio de Red Q: Cul es el modelo de servicio para el canal que transporta los datagramas desde Tx a Rx? Sera bueno contar con:

Servicios para datagramas individuales:

Entrega garantizada Entrega garantizada con

retardo inferior a X [ms] (e.g. 40 ms)

Servicios para un flujo de datagramas:

Entrega de datagramas en orden

Garanta de bandwidth mnimo para el flujo

Restricciones sobre cambios en el intervalo (tiempo) entre paquetes

Seguridad

Capa de Red 4-9

Modelos de servicio de capa de red:

Arquitectura de la Red

Internet

ATM

ATM

Modelo de servicio best effort CBR ABR

Bandwidth None constant Rate guaranteed minimum

Loss No Yes no

Order No Yes yes

Timing no yes no

Realimentacin de Congestin no (inferida en capa 4 va prdidas) no Congestin yes

Garantas ?

CBR: Constant bit rate ABR: Available bit rate

Capa de Red 4-10

Captulo 4: Capa de Red 4. 1 Introduccin 4.2 Circuitos virtuales




4.5 Algoritmo de ruteo Estado de enlace Vector de Distancias Ruteo Jerrquico

4.6 Ruteo en la Internet RIP OSPF BGP


Capa de Red 4-11

Servicios con y sin conexin de la capa de Red Las redes de datagramas proveen servicio sin conexin en su capa de red (caso Internet) Redes de VC (Virtual Circuit) proveen servicio de conexin en su capa de red (e.g. ATM) Anlogo a los servicios de capa transporte, pero: Servicio es: terminal-a-terminal (host-to-host) No hay opcin: la capa de red provee slo uno u otro (es tipo circuito virtual o es datagrama, no ambos) Implementacin: en la red interna (core)

Capa de Red 4-12

Circuitos virtuales (VC)

Hay tres fases identificables: Establecimiento de la llamada, Transferencia de datos, y Trmino de la llamada

Cada paquete lleva un identificador del VC (no direccin de mquina destino)

Cada router en el camino de fuente a destino mantiene el estado por cada conexin que pasa por l

Enlace y recursos del router (ancho de banda, buffers) pueden ser asignados al VC

Camino de fuente a destino se comporta como un circuito telefnico Para implementar un VC la red acta desde fuente a destino

Capa de Red 4-13

Implementacin de VC Un VC consiste de: 1.Camino desde fuente a destino 2.Nmeros de VC, un nmero por cada enlace a lo largo del camino 3.Entradas en tablas de re-envo en los routers a lo largo del camino Los paquetes que pertenecen a un VC llevan el nmero de VC correspondiente en cada enlace. El nmero de VC debe ser cambiado en cada enlace. El nuevo nmero de VC es tomado de la tabla de re-envo

Capa de Red 4-14

Tabla de reenvo 12 22 32

1 2 3

VC number

interface number

Incoming interface Incoming VC # Outgoing interface Outgoing VC #

1 12 3 22 2 63 1 18 3 7 2 17 1 97 3 87

Router mantiene informacin del estado de la conexin

Capa de Red 4-15

Implementacin de VC: Establecimiento del circuito virtual

Capa de Red 4-16

Redes de Datagramas Tx pone direccin destino en paquete. No hay estado mantenido en cada router por cada conexin. Paquetes se reenvan usando su direccin de terminal destino.

Capa de Red 4-17

Tabla de re-envo IP Rango de direcciones destinos Enlace Interfaz 11001000 00010111 00010000 00000000 a 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 a 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 a 2 11001000 00010111 00011111 11111111 en otro caso 3

4000 millones de Posibles entradas

Capa de Red 4-18

Coincidencia del prefijo ms largo

Prefijo Coincidente Interfaz del Enlace 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 Otro caso 3

Direccin destino: 11001000 00010111 00011000 10101010

Ejemplos

Direccin destino: 11001000 00010111 00010110 10100001

Qu interfaz?

Qu interfaz?

Capa de Red 4-19

Red de Datagrama o de VC: Por qu? Internet Protocol (IP) Datos intercambiados entre

computadores Servicio elstico, sin

requerimientos de tiempo estricto.

Sistemas terminales inteligentes (computadores) Se pueden adaptar, hacer control,

recuperacin de errores Red interna simple, la complejidad

en periferia

Muchos tipos de enlaces Caractersticas diferentes: satlite,

radio, fibra, cable Es difcil uniformar servicios: tasas,

prdidas, BW

ATM Evoluciona desde la telefona Conversacin humana:

Tiempos estrictos, requerimientos de confiabilidad

Necesidad de servicios garantizados

Sistemas terminales torpes Telfonos Complejidad dentro de la red

Capa de Red 4-20

Por qu es ms fcil ofrecer calidad de servicio en ATM que en redes de datagramas? Es ms simple porque en la etapa de

establecimiento de la conexin se define una ruta nica, lo cual hace posible hacer reserva de recursos en cada router y enlace de la ruta.

En redes de datagramas los paquetes toman distintas rutas segn las condiciones de la red y por ello la reserva de recursos no es posible.

?

Capa de Red 4-21








Capa de Red 4-22








Capa de Red 4-23 Capa de Red 4-23

Un router en Internet tiene la tabla adjunta. Indique cuntas direcciones IP son resumidas en la entrada que sale por enlace 2.

Prefijo Coincidente Interfaz del Enlace 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 Otro caso 3

Son todas la IP que parten con ese prefijo, menos las que tienen prefijo para enlace 1. Esto es 2(3+8)-28= 2048-256 = 1792


Captulo 4: Capa de Red 4. 1 Introduccin 4.2 Circuitos virtuales y

redes de datagramas 4.3 Qu hay dentro de un

router? 4.4 IP: Internet Protocol

Formato de Datagrama Direccionamiento IPv4 ICMP IPv6





Capa de red en Internet

Tabla de Re-envo

Funciones de la capa de red en host y router :

Protocolos de ruteo Seleccin de ruta RIP, OSPF, BGP

Protocolo IP Direccionamiento Formato de datagramas Manejo de paquetes

Protocolo ICMP Reporta errores Info para router

Capa transporte: TCP, UDP, SCTP, DCCP, etc

Capa enlace de datos

Capa fsica

Capa de red

SCTP: Stream Control Transmission Protocol (ao 2000) DCCP: Datagram Congestion Control Protocol (ao 2006)


ver length

32 bits

data (largo variable, tpicamente un

segmento TCP o UDP)

16-bit identifier

header checksum

time to live

32 bit source IP address

head. len

type of service

flgs fragment offset upper layer

32 bit destination IP address

Options (if any)

Formato del datagrama IPv4 Largo total datagrama (bytes)

Nmero de versin Protocolo IP = 4

Largo encabezado (bytes)

tipo de datagrama Para fragmentacin y re-ensamble mx. nmero

de tramos restantes (decrementado en

cada router)

A qu protocolo superior corresponden los

datos TCP, UDP, etc E.g. marcas de tiempo, grabar ruta tomada, especifica lista de router a visitar.

Cunta ineficiencia hay en TCP?

20 bytes de TCP 20 bytes de IP = 40 bytes + datos

capa aplicacin


Fragmentacin y re-ensamble IP Cada enlace de red tiene un MTU

(max. transmission unit), es el mayor tamao de un frame en la capa enlace. Diferentes tipos de enlaces

tienen diferentes MTUs Por esto es que un datagrama IP

grande debe ser dividido (fragmented) en la capa de red Un datagrama se convierte en varios datagramas Se rearma en el destino final Bits del encabezado IP se usan

para identificar y ordenar fragmentos relacionados

fragmentation: in: one large datagram out: 3 smaller datagrams

reassembly


ID =x

offset =0

fragflag =0

largo =4000

ID =x

offset =0

fragflag =1

largo =1500

ID =x

offset =185

fragflag =1

largo =1500

ID =x

offset =370

fragflag =0

largo =1040

Un datagrama grande es transformado en varios datagramas ms pequeos

Fragmentacin y re-ensamble IP Ejemplo 4000 byte datagram (20 bytes

header IP + 3980 en campo datos datagrama)

MTU = 1500 bytes

1480 bytes en campo de datos de datagrama

offset en bloques de 8 bytes 1480/8 = 185

byte insertado en posicin 370*8=2960 Largo datos ltimo = 3980-1480-1480 = 1020 Ms header => 1040

Ms fragmentos?


Fragmentacin y re-ensamble

ID =x

offset =0

fragflag =0

largo =4000

ID =x

offset =0

fragflag =1

largo =1500

ID =x

offset =185

fragflag =1

largo =1500

ID =x

offset =370

fragflag =0

largo =1040

Mltiplo de 8

Posicin al re-ensamble = offset*8

Ms fragmentos?


Un destino de una red IP recibe un fragmentos de tamaos 444, 444 y 253, Qu puede decir usted respecto del MTU ms pequeo de la ruta? Si los tres fragmentos corresponden al mismo datagrama original Cul es el tamao del datagrama enviado?

Como se trata de fragmentos, el paquete original fue dividido en fragmentos que quepan en el MTU ms pequeo de la ruta. El MTU debe ser superior o igual a 444, e inferior a (20+424+8)=452.

Suponiendo que son los nicos fragmentos y no se ha perdido ninguno, el datagrama original es de tamao 20+(444-20)+(444-20)+(253-20)= 1101 bytes.

?


Direccionamiento IP: introduccin Direccin IP: identificador

de 32-bit del host, interfaz del router

Interfaz: conexin entre host y router, enlace fsico Router tpicamente tiene

mltiples interfaces (bocas) Host puede tener mltiples

interfaces Direccin IP est asociada a

cada interfaz

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2 223.1.3.1

223.1.3.27

223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 1 1


Sub-redes Direccin IP:

Direc. sub-red (bits ms significativos)

Direc. del host (bits menos significativos)

Qu es una sub-red? Grupo de mquinas que poseen

la misma direccin de sub-red (parte ms significativa)

Se podran interconectar sin tener un router (e.g. con un switch o hub) Red consiste de 3 sub-redes

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2 223.1.3.1

223.1.3.27

LAN

Las direcciones IP estn organizadas jerrquicamente


Sub-redes 223.1.1.0/24 223.1.2.0/24

223.1.3.0/24

Receta Para determinar las sub-

redes, desconectar las interfaces del router para crear redes tipo islas independientes.

Cada red independiente es una sub-red.

Mscara de sub-red: /24 => 24 primeros bits Comunes, direccin de subred


Sub-redes

Cuantas hay? 223.1.1.1

223.1.1.3

223.1.1.4

223.1.2.2 223.1.2.1

223.1.2.6

223.1.3.2 223.1.3.1

223.1.3.27

223.1.1.2

223.1.7.0

223.1.7.1 223.1.8.0 223.1.8.1

223.1.9.1

223.1.9.2


Direccionamiento IP: CLASES Clases (el pasado, algo del lenguaje se ha mantenido) Porcin de direccin de la red (sub-red) se hace de

tamao fijo Ejemplo: Clase C

11001000 00010111 00010000 00000000

Parte sub-red

Parte host

Classful addresing: Esquema original (con clases A, B, C, D, E)

Clase A = subnet /8 Clase B = subnet /16 Clase C = subnet /24


Qu es una direccin IP privada? Al comienzo se pens que cada mquina deba

tener una direccin nica en el planeta. Esto no fue siempre necesario pues redes

privadas, como aquellas que conectan mquinas en una industria, no requieren conexin a Internet.

Para este propsito se reserv una subred de cada clase para crear redes privadas. stas son:

10.0.0.0/8 con 224 direcciones => 00001010.xxxxxxxx.X.X 172.16.0.0/12 con 220 direcciones => 10101100.0001xxxx.X.X 192.168.0.0/16 con 216 direcciones => 11000000.10101000.XX


Agotamiento de Direcciones IP Conforme ms subredes se crearon y conectaron

a Internet, las direcciones IP se comenzaron a agotar.

Se desarrollaron dos estrategias para extender el uso de Ipv4: Flexibilizar el tamao de las subredes:surge Classless

InterDomain Routing (CIDR). Permitir acceso a Internet de redes privadas a travs

del uso de NAT (Network Address Translation)


Direccionamiento IP: CIDR CIDR: Classless InterDomain Routing Porcin de direccin de la red (subred) se hace de

tamao arbitrario (no mltiplo de 8) Formato de direccin: a.b.c.d/x, donde x es el # de

bits de la direccin de sub-red

11001000 00010111 00010000 00000000

Parte sub-red

Parte host

200.23.16.0/23


Cuntas mquinas puede usted conectar a la sub-red 200.1.17.128/26?

32-26=6 => hay 64 direcciones IP, de las cuales 62 puedo asignar a mquinas.

?


Direcciones IP: Cmo obtener una?

Q: Cmo es que un host obtiene su direccin IP?

Configurada por el administrador en un archivo Windows: control-panel->network->configuration-

>tcp/ip->properties Linux: /etc/network/interfaces

Va protocolo de configuracin dinmica DHCP: Dynamic Host Configuration Protocol: el host obtiene la direccin dinmicamente desde un servidor plug-and-play (ms adelante)

Capa de Red 4-43

importante

importante

Capa de Red 4-44

Capa de Red 4-45


Direcciones IP: Cmo obtener una?

Q: Cmo la red obtiene la direccin de subred? parte comn ms significativa de la direccin IP.

A: Obteniendo una porcin del espacio de direcciones del proveedor ISP.

ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... .. . . Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23 Tambin podran haberse definido redes de distinto tamao.

Capa de Red 4-47

Direccionamiento IP: la ltima palabra...

Q: Cmo un ISP obtiene un bloque de direcciones?

A: ICANN: Internet Corporation for Assigned Names and Numbers Asigna direcciones Administra DNS Asigna nombre de dominio, resuelve disputas

Para Amrica Latina la oficina es LACNIC: http://lacnic.net/


NAT: Network Address Translation Motivacin: Cmo podemos dar salida a Internet a una red con direcciones

privadas? Usamos un representante. La idea es usar slo una direccin IP para acceder al mundo exterior:

No necesitamos asignacin de un rango del ISP: slo una direccin externa es usada por todos los equipos internos

Podemos cambiar la direccin de equipos en red local sin notificar al mundo exterior

Podemos cambiar ISP sin cambiar direcciones de equipos en red local

Equipos dentro de la red no son explcitamente direccionables o visibles desde afuera (una ventaja de seguridad).


NAT: Network Address Translation

10.0.0.1

10.0.0.2

10.0.0.3

10.0.0.4

138.76.29.7

red local (e.g., red en la casa)

10.0.0/24

resto del Internet

Datagramas con fuente o destino en esta red tienen

direcciones 10.0.0/24 (Tambin se puede usar: 192.168.0/24

172.16.0/24)

Todos los datagramas saliendo de la red local tienen la

misma direccin NAT IP: 138.76.29.7,

pero diferentes nmeros de puerto


NAT: Network Address Translation Implementacin ruteador NAT:

Para Datagramas salientes: remplazar (IP fuente, # puerto) de cada datagrama saliente por (IP NAT, nuevo # puerto)

. . . Clientes y servidores remotos respondern usando (IP NAT, nuevo # puerto) como direccin destino. Recordar (en tabla de traduccin NAT) cada par de traduccin (IP fuente,

# puerto) a (IP NAT, nuevo # puerto)

Para Datagramas entrantes: remplazar (IP NAT, nuevo # puerto) en campo destino de cada datagrama entrante por correspondiente (IP fuente, # puerto) almacenado en tabla NAT



10.0.0.1

10.0.0.2

10.0.0.3

10.0.0.4

138.76.29.7

1: host 10.0.0.1 enva datagrama a 128.119.40, 80

1

S: 10.0.0.1, 3345 D: 128.119.40.186, 80

NAT table WAN side addr LAN side addr 138.76.29.7, 5001 10.0.0.1, 3345

S: 128.119.40.186, 80 D: 10.0.0.1, 3345

4

S: 138.76.29.7, 5001 D: 128.119.40.186, 80 2

2: NAT router cambia la direccin fuente del datagrama de 10.0.0.1, 3345 a 138.76.29.7, 5001, actualiza la tabla

S: 128.119.40.186, 80 D: 138.76.29.7, 5001

3

3: Respuesta llega a la direccin destino: 138.76.29.7, 5001

4: NAT router cambia direccin destino del datagrama de 138.76.29.7, 5001 a 10.0.0.1, 3345



Campo nmero de puerto es de 16 bits: Mx. ~65,000 conexiones simultneas con una

nica direccin IP dentro de la LAN! NAT es controversial: Routers deberan procesar slo hasta capa 3 Viola argumento extremo-a-extremo

Los NAT deben ser tomados en cuenta por los diseadores de aplicaciones, eg, aplicaciones P2P

En lugar de usar NAT, la carencia de direcciones debera ser resuelta por IPv6


La red wifi de la USM usa direcciones IP privadas Qu hace posible que usted pueda acceder a Internet? Puede usted instalar un servidor (web por ejemplo) conectado a esta red inalmbrica? Sera accesible desde la misma red wifi? Sera accesible desde Internet?

La presencia de un NAT. S. S. No. Nota: Lo ltimo puede ser S indicando el uso de port forwarding en el NAT (tema no cubierto en el ramo, pero puede ser de su conocimiento)

?


Un alumno se conecta va ssh desde la red con NAT en su casa a un servidor en la Universidad. Si deja su conexin inactiva por un largo rato, al volver detecta que est cada. Explique cmo el servidor NAT puede causar tal prdida de conexin.

El servidor NAT mantiene una tabla con los puertos que han sido asignados a flujos provenientes de la red privada. Si no hay actividad luego de un rato, este puerto es liberado para ser asignado a otros flujos de datos. En este caso la conexin ssh ya no funciona porque el puerto asignado en el NAT ya no pertenece a esa conexin.

?


En un cyber caf todos los usuarios navegan en Internet y salen

a travs de un nico NAT. Analizando el trfico que sale del cyber caf hacia Internet cmo podra usted estimar cuntos clientes estn usando su red? Se sabe que la capa IP de cada computador usa nmeros de identificacin secuenciales en cada datagrama saliente.

Basta con observar cuntas secuencias de nmeros de identificacin estn saliendo. El nmero de secuencias indicar el nmero de capas IP enviando paquetes y ser el nmero de clientes del cyber caf.


ICMP: Internet Control Message Protocol Usado por hosts & routers para

comunicar informacin a nivel de la red Reporte de errores: host

inalcanzable, o red, o puerto, o protocolo

Echo request/reply (usado por ping) Usado por traceroute (TTL expired,

dest port unreachable) Opera en capa transporte:

ICMP son llevados por datagramas IP

Mensajes ICMP: tipo y cdigo de error, ms primeros 8 bytes del datagrama que caus el error

Type Code description 0 0 echo reply (ping) 3 0 dest. network unreachable 3 1 dest host unreachable 3 2 dest protocol unreachable 3 3 dest port unreachable 3 6 dest network unknown 3 7 dest host unknown 4 0 source quench (congestion control - seldom used) 8 0 echo request (ping) 9 0 route advertisement 10 0 router discovery 11 0 TTL expired 12 0 bad IP header


Traceroute e ICMP La fuente enva una serie de

segmentos UDP al destino Primero usa TTL=1 Luego usa TTL=2, etc. Nmero de puerto (probablemente) no

usado en destino

Cuando el n-simo datagrama llega a n-simo router: Router descarta el datagrama, y Enva a la fuente un mensaje ICMP

TTL expirado (tipo 11, cdigo 0) Mensaje incluye nombre del router y

direccin IP

Cuando mensaje ICMP llega, la fuente calcula el RTT

Traceroute hace esto 3 veces Criterio de parada Segmento UDP eventualmente

llega al host destino Host destino retorna paquete

ICMP puerto inalcanzable (tipo 3, cdigo 3)

Cuando la fuente recibe este ICMP, para.


IPv6 Motivacin Inicial: espacio de direcciones de

32-bit pronto sern completamente asignadas. Motivacin adicional: Formato de encabezado debera ayudar a acelerar el

procesamiento y re-envo (por aumento de tasas en red)

Cambiar encabezado para facilitar QoS (Quality of Service)

Formato de datagrama IPv6: Encabezado de largo fijo de 40 bytes (se duplic) Fragmentacin no es permitida


Encabezado IPv6 Prioridad: identifica prioridad entre datagramas en flujo Flow Label: identifica datagramas del mismo flujo. (concepto de flujo no est bien definido). Next header: identifica protocolo de capa superior de los datos


Otros cambios de IPv4 a v6 Checksum: eliminada enteramente para reducir tiempo de

procesamiento en cada router al ser redundante, ya est en capa transporte y enlace (Ethernet)

Options: permitidas, pero fuera del encabezado, indicado por campo Next Header

ICMPv6: nueva versin de ICMP Tipos de mensajes adicionales, e.g. Paquete muy grande (usado en el

descubrimiento de MTU: unidad mxima de transmisin) Funciones para administrar grupos multicast


Transicin de IPv4 a IPv6 No todos los routers pueden ser actualizados

(upgraded) simultneamente No es posible definir un da para cambio da de

bajada de bandera Cmo operar la red con routers IPv4 e IPv6

mezclados? Tunneling: IPv6 es llevado como carga en

datagramas IPv4 entre routers IPv4


Tunneling A B E F

IPv6 IPv6 IPv6 IPv6

tnel Vista lgica:

Vista fsica: A B E F

IPv6 IPv6 IPv6 IPv6

C D

Flow: X Src: A Dest: F data

A-a-B: IPv6


E-a-F: IPv6

IPv4


Src:B Dest: E

B-a-C: IPv6 dentro

de IPv4

IPv4


Src:B Dest: E

B-a-C: IPv6 dentro

de IPv4


Por qu el protocolo IPv6 decidi eliminar el

campo de suma de chequeo que s tiene IPv4?

Porque as cada paquete puede ser procesado ms rpidamente al no requerir recalcular una suma de chequeo cada vez que el hop limit cambiaba.

Capa de Red 4-66








Capa de Red 4-67

1

2 3

0111

valor del IP destino en cabecera de paquete

routing algorithm

local forwarding table header value output link

0100 0101 0111 1001

3 2 2 1

Interaccin de ruteo y re-envo

Capa de Red 4-68

u

y x

w v

z 2

2 1

3

1

1

2

5 3

5

Grafo: G = (N,E) N = conjunto de routers = { u, v, w, x, y, z } E = conjunto de enlaces ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

Abstraccin de la red va un Grafo

Costo del enlace: BW, congestin, $

Capa de Red 4-69

Abstraccin de Grafos : costos

u

y x

w v

z 2

2 1

3

1

1

2

5 3

5 c(x, y) = costo de enlace (x, y) - e.g., c(w,z) = 5 costo siempre puede ser 1, inversamente relacionado al ancho de banda, o directamente relacionado a la congestin

Costo de la ruta (x1, x2, x3,, xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp)

Pregunta: Cul es la ruta de mnimo costo entre u y z ?

Algoritmo de ruteo: algoritmo que encuentra el costo mnimo

Capa de Red 4-70

Clasificacin de los algoritmos de ruteo Segn si usa informacin global o

descentralizada? Global: Todos los routers conocen la

topologa completa y costos de enlaces

Algoritmos de estado de enlace (link state)

Descentralizada: El router conoce vecinos

conectados fsicamente y el costo del enlace a ellos.

Proceso iterativo de cmputo e intercambio de informacin con sus vecinos

Algoritmos de vector de distancia

Segn si es esttico o dinmico?

Esttico: Rutas cambian poco en el tiempo Dinmico: Rutas cambian ms rpidamente

Actualizaciones peridicas En respuesta a cambios de

costos de enlaces

Capa de Red 4-71








Capa de Red 4-72

Un Algoritmo de ruteo estado de enlace Algoritmo de Dijkstra Supone topologa de red y costos

de enlaces conocidos a todos los nodos Se logra va difusin de

estado de enlace Todos los nodos tienen la

misma informacin Se calcula el camino de costo

menor desde un nodo (fuente) a todos los otros Determina tabla de re-envo

para ese nodo Iterativo: despus de k iteraciones,

se conoce el camino de menor costo a k destinos (ver los valores de p(v) en el camino resultante)

Notacin: c(x,y): costo del enlace desde

nodo x a y; = si no es vecino directo

D(v): valor actual del costo del camino desde fuente a destino v.

p(v): nodo predecesor a v en el camino de fuente a v.

N': conjunto de nodos cuyo camino de costo mnimo ya se conoce

Capa de Red 4-73

Modelo abstracto para la red Por qu no se incluyen los computadores fuente y destino?

Capa de Red 4-74

Algoritmo de Dijsktra Notacin: c(x,y): costo del enlace desde nodo x a y; = si no es vecino directo D(v): valor actual del costo del camino desde fuente a destino v. p(v): nodo predecesor a v en el camino de fuente a v. N': conjunto de nodos cuyo camino de costo mnimo (desde origen) ya se conoce

Inicializacin: N' = {u} for todos los nodos v if v es vecino de u then D(v) = c(u,v) else D(v) = Loop find w not in N' tal que D(w) es un mnimo agregue w a N' actualiza D(v) para todo v adyacente a w que no est en N' usando: D(v) = min( D(v), D(w) + c(w,v) ) /* nuevo costo a v es el costo del camino actual a v o el costo del camino ms corto conocido a w ms el costo de w a v*/ until todos los nodos estn en N'

Capa de Red 4-75

Algoritmo de Dijkstra

Capa de Red 4-76

Capa de Red 4-77








Capa de Red 4-78

Algoritmo Vector de Distancia Ecuacin de Bellman-Ford Define dx(y) := costo del camino de menor costo de x a y

Entonces: dx(y) = min {c(x,v) + dv(y) } v es vecino de x Donde min es tomado sobre todos los vecinos v de x

x v1

v2 y

dv2(y)

dv1(y) c(x,v1)

c(x,v2)

Capa de Red 4-79

Capa de Red 4-80

Algoritmo Vector de Distancia (2) Dx(y) = costo mnimo estimado de x a y Vector de distancia: Dx = [Dx(y): y N ] Nodo x conoce el costo a cada vecino v:

c(x,v) Nodo x mantiene Dx = [Dx(y): y N ] Nodo x tambin mantiene los vectores de

distancia de sus vecinos Para cada vecino v, x mantiene

Dv = [Dv(y): y N ]

Capa de Red 4-81

Algoritmo Vector de distancia Idea bsica: Cada nodo enva peridicamente su vector de distancia estimada

a sus vecinos Cuando el nodo x recibe un nuevo vector de dist. estimado

desde un vecino, ste actualiza su propio vector de dist. usando la ecuacin de B-F:

Dx(y) minv{c(x,v) + Dv(y)} para cada nodo y en N

Si el vector de dist. cambia entonces el nodo x enva su nuevo vector a sus vecinos, y ellos a su vez pueden actualizar sus vectores de distancia

Bajo condiciones normales, el valor estimado de Dx(y) converge al menor costo real dx(y)

Capa de Red 4-82

Algoritmo Vector de Distancia (4) Iterativo y asincrnico: cada

iteracin local es causada por: Cambio en costo de enlace local Actualizacin de vector por

mensaje de vecino Distribuido: Cada nodo notifica a sus vecinos

slo cuando su vector cambia Vecinos entonces notifican a sus

vecinos si es necesario

wait for (cambio en costo de enlace local o llegada de mensaje desde vecino)

recalcule DV estimado

if (DV a cualquier destino ha cambiado)

notificar a vecinos

Cada nodo:

Capa de Red 4-83

x y z x y z

0 2 7

from

cost to

from

from

x y z x y z

0 2 3 from

cost to x y z

x y z

0 2 3 from

cost to

x y z x y z

cost to x y z

x y z

0 2 7 from

cost to x y z

x y z

0 2 3 from

cost to

x y z x y z

0 2 3 from

cost to x y z

x y z

0 2 7 from

cost to x y z

x y z

7 1 0

cost to

2 0 1

2 0 1 7 1 0

2 0 1 7 1 0

2 0 1 3 1 0

2 0 1 3 1 0

2 0 1

3 1 0 2 0 1

3 1 0

time

x z 1 2

7

y

node x table

node y table

node z table

Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{ 2+0 , 7+1 } = 2

Dx(z) = min{c(x,y) + Dy(z), c(x,z) +Dz(z)} = min{ 2+1 , 7+0 } = 3

Ejemplo: Vector de distancia

Capa de Red 4-84

Vector de distancia: cambios en costos de enlaces

x z 1 4

50

y 1

En el tiempo t0, y detecta un cambio en costo de enlace, actualiza su DV e informa a sus vecinos. En el tiempo t1, z recibe la informacin de y, tambin actualiza su tabla. Calcula un nuevo costo para x y le enva su Vector a sus vecinos. En el tiempo t2, y recibe la actualizacin de z y actualiza su tabla de distancia. Los costos mnimos de y no cambian, y no enva ningn nuevo mensaje a z.

Cambios en costos de enlaces: nodo detecta un cambio de costo en uno de sus

enlaces actualiza informacin de ruteo, recalcula vector

de distancia si hay cambio en DV notifica a sus vecinos

Capa de Red 4-85

Vector de distancia: cambio en costo de enlaces

x z 1 4

50

y 60

Cambio en costos de enlaces: buenas noticias viajan rpido noticias malas viajan lento Cmo pasa esto?

Capa de Red 4-87

Vector de distancia: cambio en costo de enlaces

x z 1 4

50

y 60

Qu pasa si el enlace se cae? Su costo es , =>

Reversa envenenada: Si Z routea a travs de Y para llegar a X:

Z le dice a Y que su distancia a X es infinita (para que Y no rutee a X va Z); es decir, cuando Z informa a Y, Z pretende tener distancia infinita a todos los destinos alcanzables va Y.

Resuelve completamente el problema de contar hasta el infinito? No, por qu?

Capa de Red 4-88

Si no tenemos reversa envenenada explique qu ocurre en la siguiente red (slo tres routers) cuando el enlace x-y se corta:

Se producira un aumento paulatino de la distancia para llegar de Y y Z a X hasta llegar al valor mximo para la distancia.

Inicialmente, Y llega a X con costo 3 y Z llega a X con costo 4. Cuando el enlace se corta, Y cree tener una ruta a X de distancia 5 va Z. Luego Z cambia su distancia a X a 6. Esto se repite hasta llegar al valor mximo para la distancia.

X z

Y 3 1

Capa de Red 4-89

Para este caso, qu ocurre cuando s ocupamos reversa envenenada y se corta el enlace x-y?

El algoritmo converge rpidamente. Inicialmente Y llega a X con distancia 3 y Z llega a X con

distancia 4; pero como Z lo hace va Y, Z inform a Y que su distancia a X es infinita. As cuando se cae el enlace, Y no encuentra enlace alternativo a X y actualiza su distancia a X a infinito, ante lo cual Z tambin la actualiza a infinito.

X z

Y 3 1

Capa de Red 4-90

Comparacin de algoritmos de estado de enlace (LS) y vector de distancia (DV) Complejidad de mensajes LS: con n nodos, E enlaces, O(nE)

mensajes son enviados DV: slo intercambios entre

vecinos Tiempo de convergencia vara

Rapidez de convergencia LS: O(n2), algoritmo requiere

O(nE) mensajes Puede tener oscilaciones

DV: tiempo de convergencia vara Podra estar en loops Problema de cuenta infinita

Robustez: qu pasa si un router funciona mal?

LS: Nodos pueden comunicar costo

incorrecto de un link Cada nodo computa slo su propia

tabla DV:

DV nodo puede comunicar costo de camino incorrecto

La tabla de cada nodo es usada por otros

error se propaga a travs de la red

Capa de Red 4-91

Mencione una desventaja y una ventaja del algoritmo de ruteo Estado de Enlace versus el de Vector de Distancia. Desventaja: Estado de enlace requiere propagar

anticipadamente la informacin de cada enlace a todos los nodos de la red.

Ventaja: Estado de enlace converge rpidamente una vez que un enlace cambia su costo y ste ha sido propagado.

Capa de Red 4-92

Supongamos que a usted le piden hacer un programa computacional (en el lenguaje que usted maneje) para encontrar la ruta ms corta entre dos ciudades. Si la entrada para el programa es una tabla con todos los caminos entre ciudades adyacentes sealado ciudad origen, destino y distancia entre ellas, usara alguna versin del algoritmo Estado de Enlace o Vector de Distancia?. Explique.

Elijo estado de enlace, debido a que el cmputo se debe hacer centralizadamente y en el archivo se cuenta justamente con la informacin de los nodos y enlaces del grafo donde aplicar el algoritmo de Dijkstra.

Capa de Red 4-93


y redes de datagramas

4.3 Qu hay dentro de un router?

4.4 IP: Internet Protocol Formato de Datagrama Direccionamiento IPv4 ICMP IPv6




Capa de Red 4-94

Escala: con 200 millones de destinos:

No podemos almacenar todos los destinos en tablas de ruteo!

Los intercambios de tablas de ruteo inundaran los enlaces!

Autonoma administrativa Internet = red de redes Cada administrador de red

puede querer controlar el ruteo en su propia red

Ruteo Jerrquico Nuestro estudio del ruteo hasta ahora es

idealizado. Suponemos que: Todos los routers son idnticos La red es plana esto no es verdad en la prctica

Capa de Red 4-95

Ruteo Jerrquico Agrupar router en

regiones de administracin nica, sistemas autnomos (autonomous systems o AS)

Routers en el mismo AS usan el mismo protocolo de ruteo Protocolo de ruteo intra-

AS Routers en diferentes AS

pueden correr diferentes protocolos intra-AS

Router de borde (Gateway router)

Tienen enlace directo a routers en otros sistemas autnomos

Capa de Red 4-96

Ruteo Jerrquico

Capa de Red 4-2


redes de datagramas 4.3 Qu hay dentro de

un router? 4.4 IP: Internet Protocol




4.7 Ruteo Broadcast y multicast (no ser cubierto)

Capa de Red 4-3

Ruteo intra-AS Ya hemos visto los algoritmos de ruteo, veremos

ahora cmo son aplicados en Internet. AS: autonomous systems Tambin son conocidos como Interior Gateway Protocols

(IGP) Protocolos de ruteo Intra-AS ms comunes:

RIP: Routing Information Protocol (vector-distancia)

OSPF: Open Shortest Path First (Dijkstra)

IGRP: Interior Gateway Routing Protocol (propietario de Cisco)

Capa de Red 4-4


redes de datagramas 4.3 Qu hay dentro de

un router? 4.4 IP: Internet Protocol





Capa de Red 4-5

RIP ( Routing Information Protocol) Algoritmo de vector de distancia Incluido en BSD-UNIX en 1982 Mtrica de distancia: # de hops (mx = 15 hops)

DC

BAu v

w

x

yz

Destino hopsdesde A u 1 v 2 w 2 x 3 y 3 z 2

Capa de Red 4-6

Avisos de RIP Vector de Distancia: intercambia avisos entre

vecinos cada 30 sec va mensajes de respuesta RIP (tambin conocidos como avisos RIP)

Cada aviso: lista de hasta 25 redes destinos dentro del AS

La mtrica de costo usada es el nmero de hops, es decir, cada enlace tiene costo unitario.

Nmero de hops: es el nmero de subredes atravesadas desde la fuente a la subred del destino, incluyendo esta ltima.

Network Layer 4-105

RIP: Example

Destination Network Next Router Num. of hops to dest.

w A 2 y B 2 z B 7 x -- 1 . . ....

w x y

z

A

C

D B

Routing/Forwarding table in D

.

Network Layer 4-106

RIP: Example

Destination Network Next Router Num. of hops to dest.

w A 2 y B 2 z B A 7 5 x -- 1 . . ....

Routing/Forwarding table in D

w x y

z

A

C

D B

Dest Next hops w - 1 x - 1 z C 4 . ...

Advertisement from A to D

.

Network Layer 4-107

RIP: Link Failure and Recovery

If no advertisement heard after 180 sec --> neighbor/link declared dead

routes via neighbor invalidated

new advertisements sent to neighbors

neighbors in turn send out new advertisements (if tables changed)

link failure info quickly (?) propagates to entire net

poison reverse used to prevent ping-pong loops (infinite distance = 16 hops)

Network Layer 4-108

RIP Table processing

RIP routing tables managed by application-level process called route-d (daemon)

advertisements sent in UDP packets, periodically repeated

physical

link

network forwarding (IP) table

Transprt (UDP)

routed

physical

link

network (IP)

Transprt (UDP)

routed

forwarding table

Redes de Computadores ILI-256 - Primer Semestre 2014

Captulo 4 Capa de Red

Ing. Oscar Encina C. [email protected]

Departamento de Informtica

Campus Santiago-San Joaqun

Captulo 4: Capa Red - ICaptulo 4: Capa de RedCaptulo 4: Capa de RedCapa red (network layer)Funciones claves de la capa de redFunciones de ruteo y reenvoEstablecimiento de ConexinModelos de servicio de RedModelos de servicio de capa de red:Captulo 4: Capa de RedServicios con y sin conexin de la capa de RedCircuitos virtuales (VC)Implementacin de VCTabla de reenvoImplementacin de VC: Establecimiento del circuito virtualRedes de DatagramasTabla de re-envo IPCoincidencia del prefijo ms largoRed de Datagrama o de VC: Por qu?Por qu es ms fcil ofrecer calidad de servicio en ATM que en redes de datagramas?Captulo 4: Capa de RedCaptulo 4: Capa de RedNmero de diapositiva 23Captulo 4: Capa de RedCapa de red en InternetCaptulo 4: Capa de RedFormato del datagrama IPv4Fragmentacin y re-ensamble IPFragmentacin y re-ensamble IPFragmentacin y re-ensambleUn destino de una red IP recibe un fragmentos de tamaos 444, 444 y 253, Qu puede decir usted respecto del MTU ms pequeo de la ruta? Si los tres fragmentos corresponden al mismo datagrama original Cul es el tamao del datagrama enviado?Captulo 4: Capa de RedDireccionamiento IP: introduccinSub-redesSub-redesSub-redesDireccionamiento IP: CLASESQu es una direccin IP privada?Agotamiento de Direcciones IPDireccionamiento IP: CIDRCuntas mquinas puede usted conectar a la sub-red 200.1.17.128/26?Direcciones IP: Cmo obtener una?Nmero de diapositiva 43Nmero de diapositiva 44Nmero de diapositiva 45Direcciones IP: Cmo obtener una?Direccionamiento IP: la ltima palabra...NAT: Network Address TranslationNAT: Network Address TranslationNAT: Network Address TranslationNAT: Network Address TranslationNAT: Network Address TranslationLa red wifi de la USM usa direcciones IP privadas Qu hace posible que usted pueda acceder a Internet? Puede usted instalar un servidor (web por ejemplo) conectado a esta red inalmbrica? Sera accesible desde la misma red wifi? Sera accesible desde Internet?Un alumno se conecta va ssh desde la red con NAT en su casa a un servidor en la Universidad. Si deja su conexin inactiva por un largo rato, al volver detecta que est cada. Explique cmo el servidor NAT puede causar tal prdida de conexin.Nmero de diapositiva 55Captulo 4: Capa de RedICMP: Internet Control Message ProtocolTraceroute e ICMPCaptulo 4: Capa de RedIPv6Encabezado IPv6Otros cambios de IPv4 a v6Transicin de IPv4 a IPv6TunnelingNmero de diapositiva 65Captulo 4: Capa de RedInteraccin de ruteo y re-envoAbstraccin de la red va un GrafoAbstraccin de Grafos : costosClasificacin de los algoritmos de ruteoCaptulo 4: Capa de RedUn Algoritmo de ruteo estado de enlaceModelo abstracto para la redAlgoritmo de Dijsktra Algoritmo de DijkstraNmero de diapositiva 76Captulo 4: Capa de RedAlgoritmo Vector de DistanciaNmero de diapositiva 79Algoritmo Vector de Distancia (2)Algoritmo Vector de distanciaAlgoritmo Vector de Distancia (4)Nmero de diapositiva 83Vector de distancia: cambios en costos de enlacesVector de distancia: cambio en costo de enlacesVector de distancia: cambio en costo de enlaces (e.g. incremento de costo)Vector de distancia: cambio en costo de enlacesSi no tenemos reversa envenenada explique qu ocurre en la siguiente red (slo tres routers) cuando el enlace x-y se corta:Para este caso, qu ocurre cuando s ocupamos reversa envenenada y se corta el enlace x-y?Comparacin de algoritmos de estado de enlace (LS) y vector de distancia (DV)Mencione una desventaja y una ventaja del algoritmo de ruteo Estado de Enlace versus el de Vector de Distancia.Supongamos que a usted le piden hacer un programa computacional (en el lenguaje que usted maneje) para encontrar la ruta ms corta entre dos ciudades. Si la entrada para el programa es una tabla con todos los caminos entre ciudades adyacentes sealado ciudad origen, destino y distancia entre ellas, usara alguna versin del algoritmo Estado de Enlace o Vector de Distancia?. Explique.Captulo 4: Capa de RedRuteo JerrquicoRuteo JerrquicoRuteo JerrquicoCaptulo 4: Capa de RedNetwork_4.6.pdfCaptulo 4: Capa Red - IVCaptulo 4: Capa de RedRuteo intra-ASSlide 4RIP ( Routing Information Protocol)Avisos de RIPSlide 7OSPF (Open Shortest Path First)OSPF caractersticas avanzadas (no en RIP)OSPF JerrquicoSlide 11Ruteo inter-AS en internet: BGPIntroduccin a BGPDistribucin de informacin de alcanzabilidadPor qu la diferencia entre ruteo Intra- e Inter-AS ?Capa de red: Resumen

capítulo 4 - capa de red

Documents