Resumen de Redes

Maximiliano Illbele illbelemaxi@gmail.com

8 de julio de 2014

Indice

1. La capa de Red 31.1. Sıntesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2. Diseno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1. Conmutacion de paquetes de almacenamiento y reenvıo . 41.2.2. Servicios proporcionados a la capa de Transporte . . . . . 41.2.3. Implementacion del servicio No orientado a la conexion . 51.2.4. Implementacion del servicio Orientado a la conexion . . . 61.2.5. Comparacion entre las subredes de CV y las de datagramas 7

1.3. Algoritmos de enrutamiento . . . . . . . . . . . . . . . . . . . . . 81.3.1. Clasificacion de algoritmos de enrutamiento . . . . . . . . 91.3.2. Principios de Optimizacion . . . . . . . . . . . . . . . . . 101.3.3. Enrutamiento por la ruta mas corta . . . . . . . . . . . . 111.3.4. Inundacion . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3.5. Enrutamiento por Vector de Distancia Ford y Fulkerson . 131.3.6. Enrutamiento por estado de Enlace . . . . . . . . . . . . . 151.3.7. Enrutamiento Jerarquico . . . . . . . . . . . . . . . . . . 211.3.8. Enrutamiento por Difusion . . . . . . . . . . . . . . . . . 221.3.9. Enrutamento por Multidifusion . . . . . . . . . . . . . . . 221.3.10. Enrutamiento para Hosts moviles . . . . . . . . . . . . . . 221.3.11. Enrutamiento en redes ad Hoc . . . . . . . . . . . . . . . 221.3.12. Busqueda de nodos en redes de igual a igual . . . . . . . . 22

1.4. Algoritmos de Control de Congestion . . . . . . . . . . . . . . . . 221.4.1. Principios Generales . . . . . . . . . . . . . . . . . . . . . 241.4.2. Polıticas de prevencion de Congestion . . . . . . . . . . . 281.4.3. Control de congestion en Subredes de Circuitos virtuales . 281.4.4. Control de congestion en Subredes de Datagramas . . . . 281.4.5. Desprendimiento de Carga . . . . . . . . . . . . . . . . . . 281.4.6. Control de Fluctuacion . . . . . . . . . . . . . . . . . . . 29

1.5. Calidad del Servicio (397) . . . . . . . . . . . . . . . . . . . . . . 291.5.1. Interconectividad (Internetworking) . . . . . . . . . . . . 29

2. Concatenar circuitos virtuales 31

1

3. Conectionless Interconectividad 32

4. Entunelamiento 33

5. Internetwork Routing 34

6. Fragmentacion 36

7. Esquema de numeracion de Fragmentos 37

8. La capa de Red de Internet 388.1. El protocolo IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

8.1.1. Encabezado de Protocolo IP . . . . . . . . . . . . . . . . 408.1.2. Direcciones IP . . . . . . . . . . . . . . . . . . . . . . . . 428.1.3. Mascaras de red . . . . . . . . . . . . . . . . . . . . . . . 43

9. CIDR 46

10.NAT 4710.1. Protocolos de Control . . . . . . . . . . . . . . . . . . . . . . . . 48

11.ARP 4811.1. RARP, BOOTP, DHCP . . . . . . . . . . . . . . . . . . . . . . . 49

11.1.1. RARP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4911.1.2. BOOTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4911.1.3. DHCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

11.2. Protocolos de control de Internet . . . . . . . . . . . . . . . . . . 5011.3. OSPF - The interior gateway routing protocol . . . . . . . . . . . 5011.4. BGP - The exterior gateway routing protocol . . . . . . . . . . . 5111.5. Internet Multicasting . . . . . . . . . . . . . . . . . . . . . . . . . 5111.6. Mobile IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5111.7. IPv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

12.Ipsec 5412.1. Implementacion de IPsec en IPv4 . . . . . . . . . . . . . . . . . . 54

12.1.1. Bump In the Stack BITS . . . . . . . . . . . . . . . . . . 5412.1.2. Bump in The Wire (BITW) . . . . . . . . . . . . . . . . . 54

12.2. Funcionamiento general de IPsec . . . . . . . . . . . . . . . . . . 5512.2.1. 2 Maneras de Proteger los Datagramas . . . . . . . . . . . 5512.2.2. Modos de operacion de IPSec . . . . . . . . . . . . . . . . 56

13.La capa de transporte 5713.1. Servicios que realiza para capas superiores . . . . . . . . . . . . . 5713.2. Primitivas de la capa de transporte . . . . . . . . . . . . . . . . . 5813.3. berkeley sockets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5813.4. Elementos de los protocolos de la capa de transporte . . . . . . . 5813.5. Metodo de Tomlinson . . . . . . . . . . . . . . . . . . . . . . . . 60

2

13.5.1. Direcionamiento . . . . . . . . . . . . . . . . . . . . . . . 6113.5.2. Establecer una Conexion . . . . . . . . . . . . . . . . . . . 6213.5.3. Cerrar una Conexion . . . . . . . . . . . . . . . . . . . . . 6213.5.4. Control de Flujo y buffering . . . . . . . . . . . . . . . . . 6413.5.5. Multiplexado . . . . . . . . . . . . . . . . . . . . . . . . . 6413.5.6. Recuperarse a una caıda . . . . . . . . . . . . . . . . . . . 64

14.TCP 6614.1. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6614.2. Encabezado TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

1. La capa de Red

1.1. Sıntesis

Antes de desarrollar la unidad vamos a dejar en claro con que sistema dered vamos a trabajar:

Se trabajara con un sistema cuyas componenetes principales de hardwareson:

El equipo de la empresa portadora. (Enrutadores conectados medi-ante lıneas de transmision).

El equipo del cliente.

Un host puede estar conectado a un enrutador mediante:

Una lınea alquilada.

Una LAN conectada a un enrutador que es propiedad de un cliente quienlo maneja, este enrutador tambien tiene una lınea alquilada.

Los enrutadores del cliente son considerados como parte de la subredporque se valen de los mismos algoritmos que los enrutadores de la empresaportadora.

La funcion de la Capa de RedLa capa de red entre otras cosas se ocupa de llevar los paquetes desde un

Host de origen a uno de Destino.Observacion: llegar a un host de Destino puede requerir muchos saltos por

enrutadores intermedios.

Algunas preocupaciones

¿Que debe hacer la capa de Red para poder enviar paquetes?

La capa de red debe elegir las rutas adecuadas a traves de ella.

¿Que informacion debe conocer la capa de red para escoger las rutas paraenviar paquetes?

La capa de red debe conocer la Topologıa de la subred de Comunicacion.

3

¿Que problemas pueden suceder si la capa de red no escoge bien las rutasque deben tomar los paquetes?

Se puede sobrecargara alguna de las lıneas de comunicacion y los enruta-dores asociados a ellas.

Ademas algunos enrutadores se pueden caer y pueden quedar inactivos.

¿Que pasa cuando el origen y el destino estan el redes diferentes? es decir:cuando las redes tienen distintas tecnologıas.

El paquete debe ser adaptado, ya que muchas veces los formatos y tamanosmaximos difieren de una red a otra.

Figura 1: El entorno de los protocolos de la capa de red

1.2. Diseno

1.2.1. Conmutacion de paquetes de almacenamiento y reenvıo

1. Un host transmite al enrutador mas cercano un paquete que tiene paraenviar.

2. El paquete se almacena allı hasta que haya llegado por completo, a fin deque la suma de verificacion pueda comprobarse.

3. Despues se envıa al siguiente enrutador de la ruta, hasta que llegue al hostde destino donde se entrega.

1.2.2. Servicios proporcionados a la capa de Transporte

Hay dos bandos con relacion al diseno de la capa de red:

4

1. El primero es la comunidad de Internet

La tarea del enrutador es solo mover bits de un lado a otro.

La subred es inherentemente inestable, esto implica que los hostsdeben aceptar esta condicion, y efectuar ellos mismos el control deflujo y el control de errores.

El servicio de red NO debe ser orientado a la conexion, esto impli-ca que solo debe contar con las primitivas send packet y receivepacket.

No debe efectuarse ningun ordenamiento de paquetes.

Cada paquete se transportara de manera independiente a sus ante-cesores, por eso debe llevar una direccion de destino completa.

2. El segundo Bando son las Companıas telefonicas

La subred debe proporcionar un servicio confiable, orientado a laconexion.

La calidad del servicio es el factor dominante.

Observacion: sin conexion en la subred tal calidad es muy difıcil dealcanzar, especialmente para el trafico de tiempo real como la voz yel video.

3. Estos dos bandos se ejemplifican con Internet y con las redes ATM respec-tivamente

1.2.3. Implementacion del servicio No orientado a la conexion

Con un Servicio No orientado a la conexion los paquetes se colocan individ-ualmente en la subred y se enrutan de manera independiente.

A los paquetes se les llama datagramas y la subred se conoce como: subredde datagramas.

Situacion

Suponga que el proceso P1 es un host H1 tiene un mensaje largo M para unproceso P2 que esta en H2 presente en una LAN con enrutador F .

1. P1 entrega M a la capa de transporte y le indica que lo envıe a P2 de H2.

2. El codigo de la capa de transporte se ejecuta en H1 y coloca un encabezadode transporte a M y entrega el resultado a la capa de red.

3. Si el M es mas largo que el tamano maximo de paquete, la capa de redlo tiene que dividir en varios paquetes y enviar cada uno de ellos a travesdel enrutador mediante algun protocolo punto a punto.

5

4. Cada enrutador tiene una tabla interna que le indica a donde enviarpaquetes para cada destino posible.

Observacion: una entrada de la tabla es un par que consiste en un destinoy la lınea de salida del enrutador que utilizara para ese destino.

5. Cuando llega un paquete a un enrutador se lo almacena unos momentospara comprobar su suma de verificacion, despues se reenvıa a su destinode acuerdo con la tabla del enrutador.

6. Si un paquete llega a un enrutador F se encapsula en un trama de CEDy se envıa a H2 a traves de la LAN.

Observacion: el algoritmo que maneja las tablas y que realiza las decisionesde enrutamiento se conoce como algoritmo de enrutamiento.

Figura 2: Enrutamiento dentro de una subred de datagramas

1.2.4. Implementacion del servicio Orientado a la conexion

Si se usa el servicio orientado a la conexion, antes de poder enviar cualquierpaquete de datos es necesario establecer una ruta del enrutador de origen al dedestino.

Esta conexion se conoce como Circuito Virtual CV, y la subred se conocecomo subred de circuitos virtuales.

Cuando se establece una conexion, se elige una ruta de la maquina de origena la de destino como parte de la configuracion de la conexion.

Esta ruta se almacena en tablas dentro de los enrutadores.Esta ruta se usa para todo el trafico que fluye a traves de la conexion.Cuando se libera la conexion tambien se termina el CV.Con el servicio orientado a la conexion cada paquete lleva un identificador

que indica a cual CV pertenece.

6

Situacion

Un host H1 inicio conexion con un identificador 1.Luego otro Host H3 inicia conexion con identificador 1, y ambos hosts estan

conectados al mismo enrutador A.Problema: aunque A puede saber con facilidad cuales paquetes de conexion

1 provienen de H1 y cuales de H3, los siguientes enrutadores conectados a A nopueden saberlo.

Solucion: A asigna un identificador de conexion diferente al trafico salientepara la conexion de H3.

Es decir, los enrutadores requieren de la capacidad de reemplazar identifi-cadores de conexion en los paquetes salientes.

A esto se lo conoce como Conmutacion de etiquetas.

Figura 3: Enrutamiento dentro de una subred de CVs

Los CV permiten que los paquetes contengan numeros de circuito en lugarde direcciones de destino completas.

El precio que se paga por el uso de CV’S es el espacio de la tabla de losenrutadores.

El uso de CV’S requiere una fase de configuracion que consume tiempoy recursos.

Determina lo que hay que hacer con un paquete de datos en una subred deCV’s es facil.

El enrutador usa el numero de circuito para buscar en una tabla y encontrarhacia donde va el paquete.

1.2.5. Comparacion entre las subredes de CV y las de datagramas

Con respescto a la cantidad de entradas en la tabla de enrutamiento

7

Una subred de datagramas necesita tener una entrada para cada destinoposible, mientras que una subred de CV’S solo necesita una entrada porCV.

¿Con respecto a la ocurrencia de congestion cual es mejor?

Los CV evitan congestiones en la subred pues los recursos pueden reser-varse por anticipado al establecer la conexion. Una vez que comienzana llegar los paquetes, estaran ahı el ancho de banda y la capacidad deenrutamiento necesarias.

En una subred de datagramas en mas difıcil evitar congestiones.

¿Con respecto a la caıda de enrutadores cual es mejor?

Problema de vulnerabilidad de los CV: si se cae un enrutador y se pierdesu memoria, todos los CV que pasen por el tendran que abortarse.

Pero si se cae un enrutador de datagramas solo sufriran los usuarios cuyospaquetes estaban encolados en el enrutador en el momento de la falla, ydependiendo de si habıa confirmado o no su recepcion, tal vez ni siquieratodas ellas.

Asunto Subred de Datagramas Subred de Circuitos virtualesConfiguracion

del No necesaria RequeridaCircuito

Cada paquete contiene Cada paquete contieneDireccionamiento la direccion de un numero de

origen y de destino CV cortoInformacion Los enrutadores no Cada CV requiere espacio de

de contienen informacion de estado tabla del enrutadorEstado de las conexiones por conexion

Cada paquete Ruta escogida cuandoEnrutamiento se enruta se establece el CV, y todos

independientemente los paquetes siguenesa ruta

Efecto de Ninguno, excepto Terminan todos los CV’sfallas del para paquetes perdidos que pasan a travesenrutador durante una caıda del enrutador

Calidad del Difıcil Facil si se puedenServicio reservar recursos

Control de Difıcil Facil si se puedenCongestion reservar recursos

1.3. Algoritmos de enrutamiento

El algoritmo de enrutamiento es aquella parte del software de la capade red encargada de decidir la lınea de salida por la que transmitira un paqutede entrada.

Un enrutador realiza dos procesos internos:

Reenvıo: maneja cada paquete conforme llega, buscando en las tablas deenrutamiento la lınea de salida por la cual se enviara.

Enrutamiento: es responsable de llenar y actualizar las tablas de en-rutamiento, es ahı donde entra en accion el algoritmo de enrutamiento.

8

Propiedades que todo algoritmo de enrutamiento debe tener

Robustez

Optima

Equidad

Sencillez

Estabilidad

Robustez: una vez que una red entra en operacion, debera funcionar contin-uamente durante anos.

Durante ese periodo, habra fallas de hardware y de software de todo tipo.Los Hosts, enrutadores y lıneas fallaran en forma repetida y la topologıa

cambiara muchas veces.El algoritmo de enrutamiento debe ser capaz de manejar los cambios de

topologıa y trafico sin requerir que aborten todas las actividades en todos losHosts y el reinicio de la red con cada caıda de un enrutador.

Optimizacion: Idea

Minimizar el retardo medio de los paquetes.

Aumentar al maximo la velocidad real de transporte en la red.

Estas dos metas tambien estan en conflicto.

Observacion: como termino medio muchas redes intentan minimizar el numerode saltos que tiene que dar un paquete.

La reduccion de la cantidad de saltos reduce el retardo y tambien el consumode ancho de banda, lo que a su vez mejora la velocidad real de transporte.

Equidad y optimizacion son con frecuencia metas contradictorias.Por ende se requiere un punto medio entre la eficiencia global y la equidad

hacia las conexiones individuales.

Supongamos que hay suficiente Trafico en:→AA′,

→BB′ y

→CC ′ para saturar las

lıneas horizontales.

Para aumentar el flujo maximo total el trafico de→

XX ′ debe suspender porcompleto.

Existen algoritmos de enrutamiento que nunca alcanzan el equilibrio, sinimportar el tiempo que permanezcan operativos.

Un algoritmo estable alcanza el equilibrio y lo conserva.

1.3.1. Clasificacion de algoritmos de enrutamiento

Los algoritmos de enrutamiento pueden agruparse en dos clases: segun seadapten o no a las distintas circunstacias.

9

Figura 4: El conflicto entre equidad y optimizacion

Los algoritmos no adaptivos no basan sus decisiones de enrutamiento enmediciones o estimaciones del trafico y las topologıas actuales.

La decision de que ruta se usara para ir de I a J se toma por adelantado.

A esto se lo conoce como enrutamiento estatico.

Los algoritmos adaptivos cambian sus decisiones de enrutamiento parareflejar cambios de topologıa, y por lo general tambien el trafico.

Los algoritmos adaptivos difieren en:

• El lugar donde obtienen su informacion: localmente en los enruta-dores adyacentes o en todos los enrutadores.

• El momento de cambio de sus rutas: es decir de sus tablas de en-rutamiento, las opciones varıan desde: cada cierta cantidad de se-gundos, cuando cambia la carga o cuando cambia la topologıa.

• La metrica usada para la optimizacion: puede ser la distancia, elnumero de saltos o el tiempo estimado de transito . . . .

1.3.2. Principios de Optimizacion

Se puede armar un grafo de la subred:

Cada nodo representa un enrutador.

Cada arco del grafo representa una lınea de comunicacion.

Principio de Optimizacion: si el enrutador J esta en un ruta optima delenrutador I al enrutador K, entonces la ruta optima de J a K esta en la mismaruta.

Consecuencias del principio de optimizacion

10

La existencia de arboles sumideros en una subred conexa.

Un arbol sumidero es un arbol generador con raız r tal que para todonodo n distinto de r hay exactamente una ruta de n a r en el arbol.

Figura 5: Una subred y su arbol sumidero

La meta de los algoritmos de enrutamiento es descubrir y utilizar losarboles sumideros dde todos los enrutadores.

1.3.3. Enrutamiento por la ruta mas corta

Algoritmo de enrutamiento de caminos mas cortos.Idea: para elegir una ruta entre un par de enrutadores, encontrar en el grafo

una de las rutas mas cortas entre ellas.

¿Como medir la longitud de una ruta?

Mediante el numero de saltos.

Otra medida es la distancia geografica en Km.

Sin embargo tambien son posibles otras metricas.

En el caso mas general las etiquetas de los arcos podrıan calcularse comofuncion de: la distancia, ancho de banda, trafico medio, costo de comunicacionlongitud media de las colas, retardo medio y otros factores.

Idea: usar Dijkstra.

11

1.3.4. Inundacion

Otro algoritmo estatico es la inundacion, en la que cada paquete de entradase envıa por cada una de las lıneas de salida, excepto aquella por la que llego.

El problema de esta idea es que genera grandes cantidades de paquetes du-plicados salvo que se tomen algunas medidas para limitar el proceso.

Soluciones:

1. Integrar un contador de saltos en el encabezado de cada paquete, quedisminuya con cada salto y el paquete se descarte cuando el contado lleguea 0.

Lo ideal es inicializar el contador de saltos con la longitud de la rutaentre el origen y el destino.

Si el emisor desconoce el tamano de la ruta puede inicializar el contadoral peor caso, es decir, al diametro total de la subred.

2. Llevar un registro de los paquetes difundidos para evitar enviarlospor segunda vez.

Hacer que el enrutador de origen ponga un numero de secuencia encada paquete que recibe de sus hosts.

Cada enrutador necesita de una tabla donde para cada enrutador de ori-gen hay una lista con los numeros de secuencia originados en ese enrutadorque ya ha visto.

Luego si un paquete de entrada esta en la lista, no se difunde.

Para evitar que las listas crezcan sin lımites, para un enrutador de origenademas de una lista se debe incluir un contador k.

Este contador indica que todos los numeros de secuencia hasta k ya hansido vistos.

Inundacion Selectiva

Idea: los enrutadores no envıan cada paquete de entrada por todas las lıneas,sino solo por aquellas que van aproximadamente en la direccion correcta.

Para poder ampliar inundacion selectiva se requiere la siguiente informacion

Saber en que direccion va cada lınea.

Saber en que direccion esta el destino.

Conclusion: la inundacion no es practica en la mayorıa de las aplicacionespero tiene algunos usos, por ejemplo, en aplicaciones militares, en aplicacionesdistribuidas de base de datos.

La inundacion siempre elige la ruta mas corta posible porque escoge en par-alelo todas las rutas posibles.

En consecuencia ningun otro algoritmo puede producir un retardo mas corto.(Si ignoramos la sobrecarga generada por el proceso de inundacion mismo).

12

Asumimos que se tiene la subred de la siguiente figura:

B

4

0000000000000003 _C

4

///////////////2

PPPPPPPPPPPPPPP

A5

WWWWWWWWWWWWWWWWWWWWWWWWWWWWW

2~~~~~~~~

1OOOOOOOOOOOOOOO D

3 _G

E2

_

3

���������������F

1~~~~~~~~

Se desea enviar un paquete del nodo A al nodo D usando inundacion.Contando la transmision de un paquete a lo largo de una lınea como una

carga de uno.

¿Cual es la carga total generada si se usa inundacion selectiva, un campode conteo de saltos es usado y es inicialmente fijado en 4?

HACER

1.3.5. Enrutamiento por Vector de Distancia Ford y Fulkerson

Los algoritmos de enrutamiento por vector de distancia AEVD hacen quecada enrutador mantenga una tabla.

Estas se actualizan intercambiando informacion con los vecinos.Este algoritmo se utilizo en Internet con el nombre de RIP.En el AEVD cada enrutador mediante una tabla de enrutamiento indizada

por cada enrutador en la subred.Cada entrada comprende la lınea preferida de salida hacia ese destino

y una estimacion del tiempo o distancia a ese destino.

¿Cual podrıa ser la metrica usada?

La cantidad de saltos, el retardo de tiempo en milisegundos, el numero totalde paquetes encolados a lo largo de la ruta, . . .

Se supone que el enrutador conoce la “distancia” a cada uno de susvecinos.

Si la metrica es de saltos, la distancia es un salto.

Si la metrica es la longitud de la cola, el enrutador simplemente examinacada cola.

Si la metrica es el retardo, el enrutador puede medirlo con paquetes deECO que el receptor simplemente marca con la hora y los regresa tanrapido como puede.

13

Si cada t msegs, cada enrutador envıa a todos sus vecinos una lista de susretardos estimados a cada destino y tambien recibe una lista parecida de cadavecino.

Supongamos que la tabla Tx acaba de llegar del vecino X al enrutador E.Sea Xi la estimacion es Tx respecto a la “distancia” que le toma llegar al

enrutador i desde X.Si E sabe que el retardo a X es de mx.E sabe que la “distancia” al enrutador i a traves de X es de: Xi + mx.Efectuando el calculo anterior para cada vecino de E, E puede encontrar la

estimacion que parezca ser la mejor (de la “distancia” a i), y usar esa estimacion.Ası, como la lınea correspondiente, en su nueva tabla de enrutamiento.Si T es la tabla actualizada de E, entonces para el enrutador i:

T [i] =⟨mın{Mx + Xi : X vecino de E}, V

⟩Donde mın{Mx + Xi : X vecino de E} ocurre para el vecino V .

Observar que la vieja tabla de enrutamiento no se usa en ese calculo.

Figura 6: Subred y Entrada de A,I,H,K y la nueva tabla de J

Evaluacion del AEVD: reacciona con rapidez a las buenas noticias, pero conlentitud ante las malas.

Considere un enrutador cuya mejor ruta al destino X es larga si en el sigu-iente intercambio del vecino A informa repentinamente un retardo corto a X,el enrutador simplemente se conmuta a modo de usar la lınea a A para enviartrafico hasta X.

Supongamos que la metrica de retardo es el numero de saltos.Las buenas noticias se difunden a razon de un salto por intercambio.En una subred cuya ruta mayor tiene una longitud de N saltos, en un lapso de

N intercambios todo el mundo sabra sobre las lıneas y enrutadores recientementerevividos.

14

La razon de porque las malas noticias viajan con lentitud es: ningun enruta-dor jamas tiene un valor mayor en mas de una unidad que el mınimo de todossus vecinos.

Gradualmente todos los enrutadores elevan cuentas hacia el “infinito”, peroel numero de intercambios requeridos depende de valor numerico usado para elinfinito.

Si la metrica usada es el numero de saltos, es prudente hacer que el numeroinfinito sea igual a la ruta mas larga mas 1.

Si la metrica es el retardo de tiempo no hay un lımite superior biendefinido, se necesita un valor alto para evitar que una ruta con un re-tardo grande sea tratada como si estuviera desactivada.

A este problema se lo conoce como el problema de la cuenta hasta el in-finito.

Se han hecho varios intentos para resolverlo pero ninguno funciona bien engeneral.

La esencia del problema consiste en que cuando X indica Xi a E, E no tieneforma de saber si el destino i esta en alguna ruta en funcionamiento.

Figura 7: El problema de la cuenta hasta el infinito

1.3.6. Enrutamiento por estado de Enlace

En el algoritmo de enrutamiento de estado de enlace (AEEE) cada enruta-dor debe hacer lo siguiente:

1. Encontrar sus vecinos, aprender sus direcciones de Red.

2. Medir la demora o los costos para cada uno de sus vecinos.

15

3. Construir un paquete diciendo a todos que la aprendio.

4. Mandar el paquete a todos los enrutadores.

5. Computar el camino mas corto para todos los enrutadores

Toda topologıa y todos los retardos se miden y se distribuyen a cada enruta-dor entonces puede usarse el algoritmo de Dijkstra para encontrar la rutamas corta a los demas enrutadores.

1. Sabemos que cuando un enrutador se pone en funcionamiento su primeratarea es averiguar quienes son sus vecinos la pregunta es: ¿Como se haceesto?

Se realiza enviando un paquete Hello especial a cada lınea punto a punto.Se espera que el enrutador del otro extremo regrese una respuesta indicando

quien es.Observacion: estos nombres deben ser globalmente unicos.2. El algorimo requiere que cada enrutador tenga una idea razonable del

retardo a cada uno de sus vecinos ¿Como se hace esto?Una forma de determinarlo es enviar un paquete ECHO especial a traves

de la lınea.Una vez que llegue al otro extremo, este debe regresarlo rapidamente.Metodo 1: si se mide el tiempo de ida y vuelta, se divide por dos, el enrutador

emisor puede tener una idea razonable del retardo.Problema: asume de manera implıcita que los retardos son simetricos y esto

no siempre pasa.Un aspecto importante es si se debe tener en cuenta la carga al medir el

retardo.

Para considerar la carga, el temporizador debe iniciarse cuando el pa-quete ECHO se ponga en la cola.

Para ignorar la carga, el temporizador debe iniciarse cuando el paqueteECHO alcanza el frente de la cola

¿Que consecuencias trae la inclusion de los retardos en las mediciones?

Cuando un enrutador puede escoger entre dos lıneas con el mismo ancho debanda, una con carga alta contigua1 y otra sin ella, considerara como ruta mascorta la de la lınea sin carga.

Esta seleccion resultara en un mejor desempeno, pero como siempre tambienhay un argumento en contra de la inclusion de la carga en el calculo del retardo.

Idea: cada enrutador construye un paquete de estado de enlace (LSP)que contiene los siguientes codigos:

La indentidad del emisor.

Un numero de secuencia.

1contigua: al lado

16

Figura 8: Subred en la que las Partes E y O estan conectadas por 2 lıneas

Una edad.

Una lista: {Vecinos - Retardo}.

17

B2 _

6

000000000000000 C3

@@@@@@@@

A

5 @@@@@@@@

4~~~~~~~~

D

E

1

���������������

8_F

7

~~~~~~~~

ASeq

EdadB 4E 5

BSeq

EdadA 4C 2F 6

CSeq

EdadB 2D 3E 1

DSeq

EdadC 3F 7

ESeq

EdadA 5C 1F 8

FSeq

EdadB 6D 7E 8

¿Cuando se pueden construir los paquetes de estado de enlace?

Construirlos de manera periodica, es decir a intervalos regulares.

Construirlos cuando ocurra un evento significativo, como la caıda o lareactivacion de la lınea o de un vecino o el cambio apreciable de suspropiedades.

Problema: la parte mas complicada del algoritmo es la distribucion con-fiable de los paquetes de estado del enlace.

La idea fundamental es usar inundacion para distribuir los paquetes de es-tado del enlace.

Se usa inundacion donde se lleva registro de los paquetes difundidos, es decir:

A fin de mantener controlada la inundacion, cada paquete contiene unnumero de secuencia que se incrementa con cada paquete nuevo enviado(desde su enrutador de origen).

Los enrutadores llevan registro de todos los pares:⟨Enrutador de origen -

Secuencia⟩

que ven y al llegar un paquete de estado de enlace a un enruta-dor se lo verifica contra la lista de paquetes ya vistos (para su enrutadorde origen):

18

• Si es nuevo (nuevo numero de secuencia mayor que los anteriores), sereenvıa a traves de todas las lıneas, excepto por aquella desde dondellego.

• Si es duplicado (numero de secuencia mayor visto, pero repetido) sedescarta.

• Si llega un paquete con un numero de secuencia menor que el mayorvisto hasta el momento, se rechaza como obsoleto debido a que elenrutador tiene datos mas recientes.

Problema 1: si los numeros vuelven a comenzar, SE ARMA2.Solucion: se usa un numero de longitud suficientemente grande para que pase

Muucho en dar la vuelta, por ejemplo 32 bits.Problema 2: que se de vuelta un bit en el numero de secuencia.Solucion: como proteccion contra los errores en las lıneas enrutador - enruta-

dor, se confirma la recepcion de todos los paquetes de estado del enlace.Entonces harıa falta que antes de actualizarse el numero de secuencia mas

grande, el enrutador mande una confirmacion de recepcion al transmisor y luegoespera una respuesta afirmativa o negativa del transmisor.

Caso afirmativo se actualiza en numero de secuencia mas grande.

Caso contrario se descarta el paquete que se recibio por estar errado.

Problema 3: se cae un enrutador (de origen).Sitruacion: al caer se perdera el registro de su numero de secuencia, si cuando

vuelve comienza en 0 nuevamente, se rechazara el siguiente paquete.Solucion la informacion de los enrutadores solo expira (a lo largo de la red)

cuando el enrutador esta caido.

¿Cuando se puede detectar que un enrutador esta caido?

Cuando se actualicen las tablas de enrutamiento y se manden los paquetesHello, se pueden detectar que el enrutador esta caıdo.

Ahora una vez que detecto que un enrutador esta caıdo procede de la sigu-iente forma:

Se propaga la informacion de este hecho por toda la red.

Se hace que la informacion asociada al enrutador caıdo expire3.

De esta manera cuando el enrutador vulva a la vida, puede comenzar sin prob-lemas con el numero de secuencia 0.

Problema 4: que un paquete quede de por vida dando vuelta en a red.Solucion: Incluir un campo de edad en cada paquete.

Se disminuye la edad una vez por segundo.

2vamo a echa mocoooo!3ya sean paquetes pendients a enviar, numero de secuencia mas grande recibido , . . .

19

Los enrutadores tambien decrementan el campo de edad durante el procesoinicial de inundacion.

Se descarta el paquete cuya edad sea 0.

Algunos refinamientos al algoritmo

Una vez que un paquete de estado del enlace llega a un enrutador para serinundado, no se encola para transmision inmediata. En vez de ello, entra en unbufer de almacenamiento donde se espera un tiempo breve.

Si antes de transmitirlo, llega otro paquete de estado del enlace provenientedel mismo origen, se comparan sus numeros de secuencia.

Si son iguales se descarta el duplicado.

Si son diferentes se descarta el mas viejo.

El buffer de paquetes para un enrutador contiene una celda por cadapaquete de estado de enlace recien llegado, pero aun no procesado por completo.

Una fila de la tabla del bufer de paquetes de un enrutador contiene:Origen del paquete, numero de secuencia, edad, datos de los estados de

enlace.Banderas que pueden ser:

Banderas de confirmacion de recepcion: indica a donde tiene que enviarsela confirmacion de recepcion del paquete.

Banderas de envıo: significan que el paquete debe enviarse a traves de laslıneas indicadas.

Si llega un duplicado mientras el original aun esta en el bufer, los bits delas banderas tiene que cambiar

Una vez que el enrutador ha acumulado un grupo completo de paquetes deestado de enlace, puede construir el grafo de la subred completa.

Cada enlace se representa dos veces, una para cada direccion. Los dos valorespueden promediarse o pueden ser usados por separado.

Luego se ejecuta localmente Dijkstra para construir la ruta mas corta atodos lso destinos posibles.

Los resultados de este algoritmo pueden instalarse en las tablas de en-rutamiento, y la operacion normal puede reiniciarse.

Conclusion: a medida que la subred crece en decenas de miles o cientos demiles de nodos, la probabilidad de falla ocasional de un enrutador deja de serinsignificante.

El algoritmo por estado se usa ampliamente en las redes actuales.

20

Figura 9: El bufer de paquetes para el enrutador B

1.3.7. Enrutamiento Jerarquico

A medida que crece el tamano de las redes, tambien lo hacen, las tablas deenrutamiento del enrutador.

Estas tablas le consumen al enrutador memoria y tiempo de CPU para exam-inarlas y mas ancho de banda para enviar informe de estado de los enrutadores.

La subred puede crecer hasta cierto punto en el que no es mas factible quecada enrutador tenga una entrada para cada uno de los demas enrutadores, porlo que el enrutamiento debera hacerse de manera jerarquica (como ocurre en lared telefonica).

Cuando se usa un enrutamiento jeraquico:

Los enrutadores se dividen en regiones.

Cada enrutador conoce todos los detalles para enrutar paquetes a destinosdentro de su propia region.

Un enrutador no sabe nada de la estructura interna de las regiones en lasque no esta.

Problema: en las redes enormes, una jerarquıa de dos niveles puede ser in-suficiente.

Solucion: tal vez sea necesario agrupar las regiones en clusteres, los clusteresen zonas, las zonas en grupos, . . .

Si el enrutador es jerarquico, en su tabla de enrutamiento hay:

Entradas para todos los enrutadores locales.

Entradas para las demas regiones en las que no esta el enrutador.

Observacion: el precio que se paga con enrutamiento jerarquico es una lon-gitud de ruta mayor.

21

Figura 10: Enrutamiento jerarquico

Ejercicio

En un esquema de enrutamiento jerarquico se tiene M regiones de N en-rutadores cada una y hay una region de P enrutadores (P < N).

Considerando todas las tablas de enrutamiento, ¿cuantas filas hay en totalpara almacenar?

Deduzca un formula para su respuesta

1.3.8. Enrutamiento por Difusion

1.3.9. Enrutamento por Multidifusion

1.3.10. Enrutamiento para Hosts moviles

1.3.11. Enrutamiento en redes ad Hoc

1.3.12. Busqueda de nodos en redes de igual a igual

1.4. Algoritmos de Control de Congestion

Introduccion

Cuando la cantidad de paquetes descargados en la subred por los hostsesta dentro de su capacidad de conduccion, la cantidad de paquetes entrega-dos es proporcional al numero enviado.

Entonces cuando hay demasiados paquetes presentes en la subred (o en unaparte de ella) hay una degradacion de desempeno. Esta situacion se llama con-gestion.

A medida que aumenta el trafico, llega un punto en que los enrutadores yano pueden manejarlo y comienzan a perder paquetes.

22

Situacion: si comienzan a llegar muchos paquetes por algunas lıneas de en-trada y todas necesitan la misma lınea de salida.

¿Que sucedera con esos paquetes?

Se generara una cola, y si no hay suficiente memoria para almacenar todoslos paquetes algunos de ellos se perderan.

Figura 11: Cuando se genera demasiado trafico ocurre congestion y se degradarapidamente el desempeno

El control de congestion se ocupa de asegurar que la subred sea capaz detransportar el trafico ofrecido.

Es un asunto global en el que interviene el comportamiento de todos loshosts, todos los enrutadores, el proceso de almacenamiento y reenvıo dentro delos enrutadores y todos los demas factores que tienden a disminuir la capacidadde transporte de la subred.

¿Que significa la presencia de congestion en la subred?

Significa que la carga es temporalmente superior en una parte del sistema ala que pueden manejar los recursos.

2 Tipos de soluciones

Aumentar los recursos.

Disminuir la carga.

La adicion de memoria puede ayudar hasta cierto punto, ya que se de-mostro que si los enrutadores tienen memoria infinita mas la congestionempeora en lugar de mejorar esto se debe a que para cuando los paquetesllegan al principio de la colas su temporizados ha terminado (repetidamente) yse han enviado duplicados.

23

Todos estos paquetes seran reenviados al siguiente enrutador, aumentandola carga en todo el camino hasta su destino.

A su vez los procesadores lentos tambien pueden causar congestion ya que silas CPU’s de los enrutadores son lentas para llevar a cabo las tareas requeridas,las colas pueden alargarse, aun cuando haya un exceso de capacidad de lınea.

De la misma manera pueden causar congestion las lıneas que tienen pocoancho de banda, porque probablemente la cola de una lınea de salida de pocoancho de banda se va agrandar si otras lıneas tienen mayor ancho de banda yestan recibiendo muchos paquetes destinados a la lınea de salida.

Conclusion: la actualizacion de lıneas sin cambiar y los procesadores por logeneral ayudar un poco, pero con frecuencia simplemente solo desplaza el cuellode botella a otra parte o el problema real es un desajuste de lar partesdel sistema.

Este problema persistira hasta que todos los componentes estan en equilibrio.

1.4.1. Principios Generales

¿Como identificar congestiones?

Observacion importante: el enfoque que se explicara a continuacion puedeusarse tanto en subredes de CV como en subredes de datagramas.

Idea gruesa: monitorear el uso de las lıneas de salida del enrutador, directa-mente fijarse como estan la lıneas de salidas, lo que se propone es asociar a unavariable real con valores entre 0 y 1, que representa la utilizacion de la lıneas( % de uso de la lınea).

Una forma de calcular U (que se actualiza periodicamente):

Unuevo = a ∗ Uant + (1− a) ∗ f

a : rapidez con la que el enrutador olvida la historia reciente4

• si el impacto es grande a va a ser cercano a 1.

• si el impacto del valor anterior no es muy importante porque las cosascambian muy rapido entonces a va a tender a 0.

f: muestra del uso instantaneo de la lınea.

Una vez que U sobrepasa un determinado valor, la lınea de salida entra enun estado de advertencia . . .

¿Como se trabaja con ese estado de advertencia?

Cuando llega un paquete nuevo se revisa para ver si su lınea de salida esta enestado de advertencia:

Si esta en estado de advertencia se realiza un ACCCION:

Ver Listado de ABAJO4la importancia

24

Se pueden usar otros conceptos como tamano de la cola, tamano del bufer uotras ideas . . .

Entonces U va a representar distintos estados: como tamano de la cola, loque si no va a ser que: 0 < U < 1.

Listado: ideas para controlar congestion

Control de admision: si un camino esta congestionado y quiere ser utiliza-do nuevamente no se va a admitir, es decir no se van a crear CVs (circuitosvirtuales) hasta que desaparezca esa condicion . . . (Severo).

Sıntesis: “la red esta congestionada, deja de usarse TODA”

Permitir el establecimiento de nuevos CVs, pero enrutando cuidadosa-mente los circuitos nuevos por otras rutas que no tengan problemas.

Negociar un acuerdo, entre el host y la subred cuando se establece un CV.

Busca evitar la congestion, no como las anteriores.

Busca reservar los recursos que va a necesitar durante la transmision. “es-pecifica el volumen y la forma del trafico, la calidad de servicio requeridoy otros parametros”.

Estos recursos se asignan, “de esta manera va a ser poco probable que seden congestiones”.

Si se llena hipotesis del profe: “no se asignan mas”.

¿Como actuar cuando nos llega un paquete a una lınea que esta enestado de advertencia?

1. Metodo de bit de advertencia:

Senalar el estadorde advertencia activando un bit especial en el encabezadodel paquete.

Indica que ese paquete paso por una lınea, que estaba en dicha condi-cion, cuando el paquete llega a su destino, se manda una confirmacion derecepcion al host de origen.

¿Como actua? el origen reduce el trafico hacia el destino.

El origen monitorea la fraccion de confirmaciones de recepcion conel bit activado y ajusta su tasa de transmision de manera acorde, entanto los bits de advertencia continuan fluyendo, el origen continuadisminuyendo su tasa de transmision.

“Si hay algun camino en estado de advertencia entre el host de origeny destino tiende a reducir su velocidad”.

(No tiene que haber caminos con enrutadores en estado de adver-tencia) “en caso contrario el host de origen puede incrementar lavelocidad de transferencia”.

25

El problema es que el bit de advertencia tiene que ir y volver elmensaje con la confirmacion por un camino “saturado”.

2. Metodo de paquetes reguladores:

El esquema funciona de la siguiente forma: yo le mando un paquete reg-ulador al host de origen, simplemente le digo que para tal destino tengoproblemas “la ruta para ese destino pasa por una lınea congestionada”.

La forma de evitar que no se generen muchos paquetes reguladores tieneun encabezado, la idea es que no se repitan todos.

Cuando el host de origen recibe un paquete regulador: en este se indica elX en el cual debe reducir el porcentaje X.

Y lanza un timer donde para que no le lleguen todos los paquetes regu-ladores. . .

Si al terminar el timer, no llego ningun paquete regulador el host puedeaumentar la velocidad. . .

Idea: aumentar polinomial la velocidad y reducir exponencial . . . (paracontrolar la congestion rapidamente).

Debido a que otros paquetes dirigidos al mismo destno probablemente yaestan en camino y generaran mas paquetes reguladores el host debe ignorarlos paquetes reguladores que se refieran a ese destino por un intervalo detiempo fijo.

Una vez que haya expirado ese tiempo, el host escucha mas paquetesreguladores durante otro intervalo.

26

Caracterısticas

Manejo de la tasa e datos de transmision de un Host.

• Por lo general el primer paquete regulador causa que la tasa sereduzca en 0,5 con respesto a su tasa anterior, siguiente causauna reduccion de 0,25 . . .

• Los incrementos se dan en aumentos mas pequenos para que lacongestion no se vuelva a generar rapidamente.

Variacion de paquetes reguladores

• Los enrutadores pueden mantener varios umbrales.

• Dependiendo de que umbral se ha rebasado, el paquete reguladorpuede contener una advertencia suave, una severa o un ultima-tum.

3. Metodo de paquetes reguladores de salto por salto:

La idea es que en este algoritmo ademas los enrutadores en la ruta reduz-can la tasa de transferencia, “el paquete regulador ejerza su efecto en cadasalto que da”.

Cuando el paquete regulador llega a un enrutador F se le obliga a F areducir el flujo al siguiente enrutador D.

Desventaja: reducir la velocidad es mas caro porque necesito una especiede buffer, en el ejemplo de ariba F para reducir su flujo, como ya tieneuna cola para mandar, va a necesitar guardar los paquetes.

En sıntesis reduzco la velocidad de atras para adelante mas rapido.

Se da un alivio inmediado a F con esto metodo pero requiero la ayuda demas memoria en los enrutadores.

Saltos por salto

E◦ // F◦ // ◦Destino

Paquete regulador es con respecto a un Host de destino, i.e: sereducen las velocidades de todos los enrutadores que van a ese camino.

Ejercicio

¿Que ventajas ofrece el algoritmo de paquetes reguladores frente al de bit deadvertencia?

No necesita que el paquete de confirmacion pase por un circuito conges-tionado.

DESVENTAJA: El metodo de paquetes reguladores crea nuevos paquetes.

El host puede ignorar paquetes reguladores por un intervalo . . . en el meto-do de paquetes reguladores

La parte de los paquetes de recepcion de confirmacion NO cambia . . .

27

El bit de advertencia obliga a ver todas las confirmaciones que van llegan-do.

Otra ventaja: si a lo largo de la ruta hay varios enrutadores con problemassolamente manda advertencias el primero y no todos los congestionadosen la ruta, aunque tambien es una cosa pequena . . .

Ventaja grande de paquetes reguladores: aviso no pase por un lugar con-gestionado entonces evito que se pierda . . .

Problema de paquetes reguladores: a altas velocidades o distancias grandes,el envıo de un paquete regulador los host de origen no funcionan bienporque la reaccion es muy lenta.

La diferencia no es tan grande: La idea de circuito virtual es para siempre,en cambio los datagramas se realizan los cambios muy cada tanto.

1.4.2. Polıticas de prevencion de Congestion

1.4.3. Control de congestion en Subredes de Circuitos virtuales

1.4.4. Control de congestion en Subredes de Datagramas

1.4.5. Desprendimiento de Carga

Los algoritmos anteriores los Hosts y en algunos casos los enrutadoes reducenla tasa de transferencia. Pero si ninguno de ellos elimina la congestion vale laidea de Desprendimiento de Carga:(TIRAR PAQUETES).

Observacion: La congestion se vacia rapido porque elimino k paquetes deuna.

Estrategia: si puedo descartar paquetes antes que se llene el buffer puedoelegir a quien puedo descartar, porque no todos los paquetes tienen la mismaimportancia. Es decir me aseguro que todo lo que es vital llegue.

Algunos criterios para descartar paquetes

En la transferencia de archivos es mas importante un paquete viejo queuno nuevo5.

En la transferencia multimedia es mas importante los paquetes viejos quelos paquetes nuevos6

Segun la importancia de los paquetes

Las aplicaciones deben mandar sus paquetes con clases de prioridades paraindicar su importancia, luego os enrutadores descartan primero los de menorprioridad.

En la realidad en la Internet se utilizan desprendimiento de carga mas quelos hots reducen las tasas de transferencia....

5Como el vino6Teorıa de la leche: la leche nueva sabe mas fresca que la vieja)

28

Algoritmo de deteccion temprana aleatoria

La idea que usa TCP: cuando no me llega la confirmacion de recepcion de unpaquete asumo que el problema es por congestion entonces reduzco la tasa deenvıo, disenado para redes cableadas “fibra optica, coaxil”, confiable, entoncessuele ser muy raro la perdida de paquetes, por ello se supone que si no mellego una confirmacion de recepcion de un paquete asumo que el paquete fuedescartado por alguna congestion en algun lugar de la red y reduzco la tasa detransferencia.

Funcionamiento: para detectar cuando comenzar a descartar paquetes los en-rutadores mantienen un promedio movil de sus longitudes de cola, cuando estasen algunas lıneas sobrepasan el mbral, se dice que la lınea esta congstionada.

U = longitudes de cola

Debido a que tal vez el enrutador no puede saber cual origen esta causando lamayorıa de los problemas, probablemente lo mejor que se puede hacer es elegirun paquete al azar de la cola que puso en marcha la accion.

Luego se procede a descartar el paquete y no reportarlo, por lo tanto elorigen notara la falta de confirmacion de recepcion y respondera disminuyendola velocidad de transmision.

Observacion: no es perfecto porque no tiene en cuenta la importancia de lospaquetes, pero tenıan miedo de que todos transmitan a prioridad alta todos susmensajes.

“Este algoritmo asume que la gente es egoista” por lo tanto todos los paque-tes tiene la misma prioridad.

1.4.6. Control de Fluctuacion

1.5. Calidad del Servicio (397)

1.5.1. Interconectividad (Internetworking)

Hasta ahora supusimos implıcitamente que hay una red homogenea y quecada maquina usa el mismo protocolo en cada capa.

En la practica existen muchas redes diferentes.Estudiaremos los problemas que surgen cuando dos o mas redes se juntan

formando una interred (internet).Pasando en limpio, interred: es una subred que esta formada por varias

tecnologıas.La capa de red debe encargarse que lleguen bien los paquetes independientes

de las tecnologıas que atraviesan.Ejemplos: de distintas tecnologıas

Casi todas las instalaciones UNIX ejecutan TCP/IP.

Muchos negocios grandes tiene mainframes que ejecutan SNA de IBM.

Una cantidad considerable de companıas telefonicas operan redes ATM.

29

Algunas LANs de Pc usan Novell NCP/IPx o AppleTalk.

Redes inalambricas

Figura 12: Una coleccion de rdes interconectadas

Porque yo quiero conectar redes diferentes voy a tener en cuenta que losusuarios de cualquiera de ellas quieran comunicarse o quieran acceder a losdatos de las demas.

En la siguiente tabla estan algunas diferencias que pueden ocurrir en la capade red:

Aspecto algunas posibilidadesServicio ofrecido sin conexiones, orientado a la conexion

Protocolos IP, IPX, SNA, ATM , MPLS , Adssad, . . .Direccionamiento Plano (802) o jerarquico (IP)

Multidifusion Presente o ausente (igual difusion)Tamano de paquete Cada red tiene su maximoCalidad de servicio Presente o ausenteManejo de errores Entrega confiable, ordenada, desordenadaControl de flujo Ventana corrediza, control de tasa, ninguno

Control de congestion paquetes reguladores, bitSeguridad encriptacion , reglas implıcitas

Parametros Diferentes, timersContabilidad por paquete , por byte, ninguna

La conciliacion de estas diferencias es lo que hace mas difıcil la interconexionde redes que la conexion de una sola red.

30

Situaciones

Cuando los paquetes de una red orientada a la conexion deben transitaruna red no orientada, los paquetes deben reordenarse.

Algo que el emisor no espera y el receptor no esta preparado para manejaresta situacion.

Considerar diferentes tamanos maximos de paquetes.

Pueden ser necesario conversiones de direcciones

Es por ello que con frecuencia se necesitaran conversiones de protocoloEn la realidad en la capa de red puede haber enrutadores que pueden conec-

tar dos capas de red diferentes.El enrutador puede ser capaz de traducir entre los formatos de paquetes,

pero esto es cada vez menos comun.Un enrutador que puede manejar multiples protocolos se llama enrutador

multiprotocolo.

2. Concatenar circuitos virtuales

Segun el modelo de circuitos virtuales concatenados se construye una rutauniendo CVs de la siguiente manera:

1. La subred construye un CV al enrutador mas cercano a la red de destino.

2. Luego la subred construye un CV de ese enrutador a una puerta deenlace externa.

3. Este proceso continua hasta llegar al host de destino.

Una vez que comienzan a fluir los paquetes de datos por la ruta creada, cadapuerta de enlace retransmite los paquetes de entrada y hace las conversionesentre los formatos de paquetes y los numeros de CV segun sea necesario.

Cada puerta de enlace, mantiene tablas, que indica los CVs que pasan atraves suyo, a donde se deben enrutar y el nuevo numero de CV.

El modelo de CVs concatenados tiene en esencia las mismas ventajas que eluso de CVs en una sola subred:

Prefija un camino para mandar de un camino de A a B, porque se producemenos congestion en las redes virtuales que en las de datagramas.

Pueden reservarse buferes por adelantado, puede garantizarse la secuenciay tiene encabezados cortos.

El modelo de CVs concatenados tiene en esencia las mismas Desventajas queel uso de CVs en una sola subred:

Desventajas:

31

Figura 13: Interconectividad mediante circuitos virtuales concatenados

Si se cae un enrutador todo lo que pasaba por ahı se pierde, en cambio enlas redes de datagrama en una cierta cantidad de pasos se va a registrarque esta caıda una ruta.

La falta de enrutamiento alterno para evitar rutas congestionadas.

La vulnerabilidad a fallas de los enrutadores a lo largo de la ruta.

3. Conectionless Interconectividad

El enfoque de datagramas suele usar multiples rutas y lograr de este modoun ancho de banda mayor que en el modelo de CVs concatenados.

Pero, no hay garantıa que los paquetes lleguen a destino en orden, suponiendoque lleguen.

Problema 1: si cada red tiene su propio protocolo de capa de red, no esposible que un paquete de red transite por otra.

Solucion 1: usar enrutadores multiprotocolo tratando de traducir de un for-mato a otro pero a menos que los dos formatos sean parientes cercanos, con losmismos campos de informacion es muy difıcil convertirlos, por esto los paquetesde datagramas son difıciles de traducir por eso no usan pero sı las CVs.

Solucion 2: disenar un paquete universal de interred y hacer que todoslos enrutadores lo reconozcan.

Este enfoque es el que tiene IP,un paquete disenado para llevarse a muchasredes.

El problema es ponerse de acuerdo, y generalmente hay preferencia por laspatentes y negocios.

Problema 2: manejar distintas formas de direccionamiento.

32

Figura 14: Una interred no orientada a la conexion

Solucion: en el mejor de los casos se tendrıa que mantener una base de datosde las conversiones de direcciones de redes diferentes.

Evaluacion: un host de internet esta intentando mandar un paquete IP a unhost en una red SNA adyacente.

Se podrıa pensar en una conversion entre direcciones IP y SNA en ambasdirecciones pero el concepto de lo que es direccionable es diferente:

En IP solo las Hosts (las tarjetas de red) tienen direcciones.

En SNA entidades diferentes a los hosts (por ejemplo dispositivos de hard-ware) pueden tener direcciones.

Conclusion: las propiedades del enfoque de datagramas para la interconec-tividad son las mismas que de las subredes de datagramas:

Mayor potencial de congestion pero mayor potencial para adaptarse a el

La robustez ante fallas de los enrutadores.

La necesidad de encabezados mas grandes.

4. Entunelamiento

Problema: asumimos que el host de origen H1 y de destino H2 estan en unamisma clase de red, pero hay una red distinta en el medio.

H1, H2 : Ethernet, TCP/IP.

X (la del medio): WAN (ATM)

33

H1// X // H2

Solucion: usar entunelamientoIdea: meter un paquete dentro de otro de esta manera me independizo de la

idea de tener que traducir de un paquete/direccion a otra.Paso a Paso:

1. Para enviar un paquete IP a H2, H1 construye un paquete P que contienela direccion IP de H2.

2. Luego H1 lo inserta a P en una trama Ethernet dirigida al enrutadormultiprotocolo y lo pone en la lınea Ethernet de H1.

3. Cuando el enrutador multiprotocolo recibe la trama, retira el paquete IP,lo inserta en el campo de carga util del paquete de capa de red de laWAN y dirige este ultimo a la direccion de la WAN de otro enrutadormultiprotocolo (conectado a la Ethernet de H2).

4. Cuando llega allı, el enrutador multiprocolo retira el paquete IP y lo envıaa H2 en una trama Ethernet.

Figura 15: Entunelamiento de un paquete de Paris a Londres

Ipv6enrutador multiprotocolo→ ipv4

enrutador multiprotocolo→ Ipv6

5. Internetwork Routing

Como hacer el enrutamiento cuando tengo varias redes con distintas tec-nologıas.

El enrutamiento en una interred es parecido al enrutamiento en una sola red,pero con algunas complicaciones adicionales.

Primero se construye un grafo de la interred

34

Los nodos son enrutadores multiprocesador.

Los lados son entre enrutadores multiprocesador.

Figura 16: Una interred y su grafo asociado

Una vez construido el grafo, pueden aplicarse los algoritmos de enrutamientoconocidos, como el algoritmo de vector de distancia y el de estado de enlace, algrupo de enrutadores multiprocolo.

Esto da un algoritmo de enrutamiento de dos niveles:

1. En cada red se utiliza un protocolo de puerta de enlace interior(IGP).

2. Entre las redes se utiliza un protocolo de puerta de enlace exterior(EGP).

De hecho, debido a que esas redes son independientes, cada una puede utilizarun algoritmo distinto.

Proceso para enviar un paquete de un host a otro

1. Un paquete de interred tıpico parte de su LAN hacia el enrutador multi-protocolo local.

2. Al llegar ahı, el codigo de la capa de red decide por cual enrutador multi-procolo reenviara el paquete, usando sus propias tablas de enrutamiento.

3. Si ese enrutador puede alcanzarse usando el protocolo de la red nativa delpaquete, este se reenvıa directamente por ahı.

4. De otra manera se envıa por tunel, encapsulado en el protocolo requeridopor la red que interviene.

35

5. Este proceso se repite hasta que el paquete llega a la red de destino.

Diferencias entre el enrutamiento entre las redes y el enrutamiento dentrode las redes:

El primero con frecuencia requiere el cruce de fronteras internacionales,de pronto entran en juego varias leyes distintas.

Dentro de una sola red, normalmente se aplica un solo algoritmo de cargo,sin embargo redes diferentes pueden estar bajo administraciones difer-entes, en una ruta puede ser mas barata que en otras.

La calidad del servicio ofrecia por diferentes redes puede ser distinta y estapuede ser una razon para escoger una ruta u otra.

6. Fragmentacion

Cada red impone un tamano maximo a sus paquetesLas cargas utiles maximas van desde 48bytes (celdas ATM) hasta 65515

bytes (paquetes IP) aunque el tamano de la carga util en las capas superiorescon frecuencia es mas grande.

Problema: un paquete grande quiere viajar a traves de una red cuyo tamanomaximo de paquete es demasiado pequeno.

Solucion: las puertas de enlace dividen los paquetes en fragmentos enviandocada fragmento como paquete de interred individual.

Las redes de conmutacion de paquetes tambien tienen el problema de unirnuevamente los fragmentos.

Existen dos estrategias opuestas para recombinar los fragmentos y recuperarel paquete original.

Hacer Transparente la fragmentacion causada por una red de paquetepequeno a las demas redes subsiguientes por las que debe pasar el paquetepara llegar a su destino final

• Con este metodo la red de paquete pequeno tiene puertas de enlace(enrutadores especializados) que interactuan con otras redes.

• Cuando un paquete de tamano excesivo llega a una puerta de enlace,esta lo divide en fragmentos.

• Todos los fragmentos se dirigen a la misma puerta de enlace de salida,donde se recombinan las piezas.

• Las redes ATM tiene hardware especial para esta estrategia

Desventajas:

1. La puerta de enlace de salida debe saber cuando ha recibido toadaslas piezas por lo que debe incluirse un campo de conteo o un bitde fin de paquete en cada paquete7.

7desventaja mas importante

36

2. Todos los paquetes deben salir por la misma puerta de enlace: estopuede bajar un poco el desempeno.

3. Hay una sobrecarga para reemsanblar y volver a fragmentar repeti-damente un paqute grande que pasa por varias redes de paquetepequeno.

Abstenerse de recombinar los fragmentos en las puertas de enlace inter-medias

• Una vez que se ha fragmentado un paquete, cada fragmento se tratacomo si fuera un paquete original. Todos los paquetes pasan por lapuerta de enlace de salida.

• La recombinacion Ocurre en el host de destino.

• IP funciona de esta manera.

Desventajas:

1. Requiere que todos los host sean capaces de hacer el reensamble.

2. Al fragmentarse un paquete grande, aumenta la sobrecarga total,pues cada fragmento debe tener un encabezado8.

Figura 17: (a) Transparente (b) No transparente

7. Esquema de numeracion de Fragmentos

El protocolo de interred define un tamano de fragmento elemental.

8desventaja mas importante

37

Al fragmentarse un paquete todas las partes son iguales al tamano de frag-mento elemental, excepto la ultima que puede ser mas corta.

El encabezado de interred debe proporcionar:

El numero de paquete original.

El desplazamiento de bit o byte en el paquete original.

Un bit que indique que el ultimo fragmento elemental contenido en elpaquete de interred es el ultimo del paquete original.

Figura 18: Ver explicacion abajo

Fragmentacion cuando el tamano de datos elemental es de 1 byte(a) paquete original que contiene 10 bytes de datos(b) Fragmentos tras pasar a traves de una red con un tamano maximo de 8

bytes(c) Fragmentos tras pasar a traves de una puerta de enlace de tamano 5.

8. La capa de Red de Internet

Diseno principal para Internet

1. Asegurese de que funciones.

2. Pensar simple.

3. Elija opciones claras.

4. Explote la modularidad.

5. Prevea la heterogeneidad.

38

6. Evite opciones y parametros estaticos, evitar decisiones fijas.

7. Busque un buen diseno, no es necesario que sea perfecto.

8. Sea estricto cuando envıe y tolerante cuando reciba.

9. Piense en la capacidad de crecimiento (escalabilidad).

10. Considere el desempeno y el costo (performance).

Figura 19: Internet es un conjunto interconectado de muhas redes

8.1. El protocolo IP

1. Toma flujos de datos y los divide en “Datagramas” de hasta 64K cadauno.

En la practica IP usa datagramas de hasta 1500bytes, para evitar eltema de fragmentacion, (decision de eficiencia) pero rrompe abstrac-ciones porque la capa de red no necesita saber la maxima capacidadde la trama ethernet.

2. Se puede fragmentar en el camino: fragmentos “elementales”

Supongamos que el emisor manda un datagrama K a un receptor,esprobable que exista un router al medio que divida el mensaje y elreceptor recibe dos mensajes y debe ser capas de unirlo, es decir quela fragmentacion no necesariamente la hace el emisor.

IP piensa en el mundo, 10.000 Km por ello puede ser necesario que almedio necesite dividir el mensaje. Por esto permite sobre la marchafragmentar.

39

Por que la capa de red vuelve a dividir los mensajes: porque la capade red comunica redes a larga distancia, y basicamente la analogia es:capa de enlace a nivel LAN, capa de Red es a nivel WAN , entoncesla fragmentacion a nivel de red, se hace lo mismo pero viendolo desdeun nivel mas alto. Lo unico que cambia es la escala.

3. Los fragmentos enviados por la red contienen un numero de fragmentoselementales del datagrama original.

4. Cuando llegan todos los fragmentos, se reensamblan y pasan a la capasuperior.

8.1.1. Encabezado de Protocolo IP

Figura 20: El encabezado de IPv4 (protocolo Internet)

1. Version (4bits): IPv4 - IPv6.

2. IHL (4bits): longitud del encabezado medido en “palabras” de 4bytes=32bits.

Valor mınimo: 5 sin opciones.

Valor maximo: 15 ∗ 4 = 60B de info, 40B para opciones (no siempresuficiente).

3. Tipo de servicio (6 bits): 3 para prioridad, y 3 de Delay, Throughput yReliability. (Entrega rapida o precisa, rapida por ejemplo en la multimedia,o precisa cuando mandamos archivos). Todos estos campos se ignoran enla practica por los routers.

4. Longitud Total (16 bits): del datagrama, que cada uno de esos es un byte,cada uno de esos es un byte (cambio de escala). por lo tanto el tamanomaximo es 216 = 64KB

40

5. Identificacion (16 bits): indica a que datagrama pertenece este fragmento(todos los fragmentos de un mismo datagrama tienen el mismo valor)

Cantidad de Datagramas posibles 2 ∗ ∗16 = 64KB

6. BIT DF (dont Fragment) 1 bit, indico que no lo fragmente: porque el quelo recibe no tiene capacidad de reemzamblar, por ejemplo porque no tienememoria suficiente.

7. BIT MF More fragment, siguen mas fragmentos, todos los fragmentos lotienen prendido menos el ultimo, para elegir siempre que mande los distin-tos fragmentos por el mismo lado y ahorro calcular por donde mandarlo.

8. Fragment offset (desplazamiento de fragmento) (13 bits) podemos tenerhasta 8192 fragmentos de un datagrama, esto indica donde empieza elfragmento, dentro del datagrama entero porque puede contener varios...8192 fragementos: ⇒ de 8 bytes, porque me paso del maximo permitidode paquete.

Pero el maximo datagrama no puede tener mas de 64KB.

9. TTL: time to live (8 bits), se usa para limitar el tiempo de vida de unpaquete y evitar congestion.

En teorıa cuenta segundos de vida, pero en la practica cuenta cantidad desaltos de un enrutador a otro.

Cada router lo decrementa y cuando llega a 0 se descarta.

10. Protocolo: indica que protocolo de la capa mas alta usa, rrompe abstrac-cion mal, esto refleja que protocolo esta mas arriba para mejorar su efi-ciencia por ejemplo (TCP,UDP).

11. Header Checksum: (16 bits) , suma de verificacion, cuando se calcula elCRC, debe recalcularse en cada salto si cambia TTL.

12. Direccion de origen y destino: 32 bits cada una.

13. Campos opcionales: Sirven para debuggear cosas o para experimentar, sonde longitud variable.

El orden de como se disenaron los campos importa, por ejemplo el primeroes la version porque si no se que es el paquete no puedo hacer nada.

Campos Opcionales

Opcion DescripcionSeguridad Especifica que tan secreto es el datagrama

Enrutamiento estrictodesde el origen indica la ruta completa a seguir

Enrutamiento libre Da una lista de enrutadoresdesde el origen que no deben evitarseRegistrar ruta Hace que cada enrutador agregue su direccion IP

Marca de Tiempo Hace que cada enrutador agregue su direccion y su marca de tiemposu direccion y su marca de tiempo

No hace falta decir que la idea de seguridad es MALA.

41

8.1.2. Direcciones IP

Cada host o router tiene una direccion IP que lo identifica en la red.

Son de 32 Bits de la forma A.B.C.D donde cada uno es un numero de 8bits.

Cada direccion IP denota una direccion de red mas una direccion de Host

• Los bits mas significativos, a la izq, denotan la red.

• Los bits menos significativos, a la derecha, denotan el host.

El espacio de direcciones se dividio originalmente en 4 clases.

Figura 21: Formatos de direccion IP

Clases:

A Unicast9, 128 redes de 16 millones de hosts cada una.

B (unicast) 16382 redes de 64K cada una.

C (unicast) 2 millones de redes, 256 host cada una.

D Multicast (multidifusion): las direcciones de IP no pertenecen a un hostsino a un grupo de hosts (que se suscriben a esa IP).

E NO SE USARON.

La idea es Aumentar las redes y disminuir las host.Direcciones de IP Comunes

9Una direccion de IP solo puede pertenecer a un host

42

Existen determinadas direcciones comodın, como para mandar a mi propiamaquina, pero distinto puerto.

Si pongo Todos unos en la parte de red, estoy haciendo un Broadcast a nivelde red: Mando a todos los puertos.

Loopback: se usan para debuggiar como el Localhost, que a diferencia detodos 0, esta realmente va a la capa de red, e internamente de manda a la capade red, en cambio el 0 se queda ahi.

Figura 22: Direcciones IP especiales

El problema con la division original de clase es que la clase B es demasi-ado grande y la clase C es demasiado chica, entonces se desperdician muchasdirecciones.

Solucion: necesitamos una manera mas precisa/flexible.Idea: una red grande (por ejemplo una clase B) la subdividimos en partes

mas chicas, subredes mascaras de red.Estas mascaras son invisibles desde afuera de la red.Luego primero se rutea a la red grande y despues se divide de acuerdo a la

mascara.

8.1.3. Mascaras de red

Una mascara es una direccion de IP de 32 bits que consiste de 1s seguidosde 0s y denota un numero de hosts.

Ejemplo:

1111 1111. 1111 1111. 1111 1100 0000 0000

En decimal: 255. 255 . 252 .0

Esta mascara permite 210 hosts = 1024.

43

Figura 23: Una red de clase B dividida en 64 subredes

La red clase B del ejemplo 216host: 64K hosts.Ejemplo Supongamos que comienza en 130.50.0.0 y termina en 130.50.255.255

Queremos definir 3 subredes:

1. S1: Comenzando en 130.50.4.0 y terminando en 130.50.7.255.

2. S2: Comenzando en 130.50.8.0 y terminando en 130.50.11.255

3. S3: Comenzando en 130.50.12.0 y terminando en 130.50.15.255

Cuantos Hosts tienen S1 S2 S3

HACERLas mascaras se usan por los routers para determinar a que subred se debe

reenviar un paquete.

Cuando llega un paquete, se hace un AND binario entre la direccion dedestino del paquete y la mascara.

Si el resultado es la direccion de origen de la subred, se reenvia a esasubred.

Si no, se intenta con las otras subredes, y finalmente se descarta .

Situacion

Supongamos que llega un paquete con destino: 130.50.15.61000 0010 .0011 0010 .0000 1111 .0000 0110

AND 1111 1111 .1111 1111 .1111 1100 . 0000 0000130. 50. 12. 0

Es al origen de S1? (130.50.4.0) NO.

44

Es al origen de S2? (130.50.8.0) NO.

Es al origen de S3? (130.50.12.0) SI ⇒ Reenviar.

Hay algunas mascaras que denotan algunos rangos imposibles y en ese caso...

COMPLETAR

Situacion

Supongamos que llega un paquete con destino 130.50.5.61000 0010. 0011 0010. 0000 0101. 0000 0110

AND 1111 1111. 1111 1111. 1111 1100. 0000 0000130 .50 .4 .0

Es el origen de S1? (130.50.1.0) SI

Situacion

Supongamos que llega un paquete con destino 131.51.5.61000 0010. 0011 0011. 0000 0101. 0000 0110

AND 1111 1111. 1111 1111. 1111 1100. 0000 0000130 .51 .4 .0

Se descarta . . .Notacion:Si tenemos una red que empieza en 130.50.4.0 y tiene mascara de red:1111 1111. 1111 1111. 1111 1100 . 0000 00000podemos denotarla como 130.50.4.0/22, donde 22= numero de bits en 1 a la

izquierda de l mascara.El origen de una subred denota el tamano maximo de hosts que puede al-

bergar. Por ejemplo, supongamos que inicia en 130.50.8.01000 0010 . 0011 0010 . 0000 1000 . 0000 0000Esta red puede crecer hasta 211 hosts = 2048Dicha mascara es: 255.255.248.01111 1111 . 1111 1111. 1111 1000.0000NOTA: antes solo crecıa hasta 1024 hosts.

Mascaras Tamano maximoMascara para 16 hosts :Tenemos la subred que inicia en:130.50.8.01000 0010. 0011 0010. 0000 1000. 0000 0000Si quisieramos hacer la red mas grande, deberıamos elegir otra mascara:Por ejemplo: 255.255.128.0Que me albergarıa 215 = 32K Hosts.Esto harıa que la red llegue hasta 130.50.135.255.Pero escibimos la macara entera:1111 1111. 1111 1111. 1000 0000. 0000 0000

45

Ningun paquete que se haga AND con esta mascara me da la IP de origende la subred (130.50.8.0).

MORALEJA: la cantidad maxima de hosts se da por la cantidad de 0s ala derecha del ultimo 1 en la direccion de origen

1000 0010. 0011 0010. 0000 1 000. 0000 00000Idea buscar el primer 1 de derecha a izq cuando puedo alojar

9. CIDR

Aun ası se encontro que las redes divididas en clases son problematicas paraasignar (se desperdician muchas direcciones).

Con CIDR se permiten direcciones de cualquier tamano.Pero ahora hace falta que los routers conozcan las mascaras de red (antes

ocultas)Universidad Primer direccion ultima dir Cuantas Notacion

Cambridge 194.24.0.0 194.24.7.255 2048 194.24.0.0/21Edinburgh 194.24.8.0 194.24.11.255 1024 194.24.8.0/22(Available) 194.24.12.0 194.24.15.255 1024 194.24.12/22

Oxford 194.24.16.0 194.24.31.255 4096 194.24.16.0/20

MascarasCambridge: 194.24.0.0 ⇒ 194.24.7.255Mascara: 194.24.0.0/21 o 255.255.248.0248 se escibe : (1111 1000)Maximo permitido 2048 Hosts.Un problema de CIDR es que hay demasiadas entradas de ruteo.Esto se puede solucionar usando entradas agregadas.Por ejemplo una red que engloba todas las anteriores es:194.24.0.0/19 que tiene: 213 = 8192 Hosts.Que van desde 194.24.0.0 ⇒ 194.24.31.255

46

10. NAT

“Quedan pocas direcciones IP en el mundo.”Para evitar dar direcciones IP reales, en una LAN se pueden usar direcciones

internas:10.0.0.0 ⇒ 224 Hosts.172.16.0.0 ⇒ 220 Hosts.192.168.0.0 ⇒ 216 Hosts.y luego se utiliza un “Proxi NAT” que tiene una direccion unica real, y

traduce los paquetes de ida y vuelta.

Figura 24: Colocacion y funcionamiento de una caja NAT

Cuando un paquete esta por salir, el NAT reemplaza la direccion de origenpor la propia, y genera un nuevo puerto de origen que se usa como ındice en unatabla interna. Luego guarda en la tabla interna la direccion de origen internamas el puerto de origen.

Cuando llega un paquete el NAT reenvıa de acuerdo al puerto de destino delpaquete entrante, restableciendo la direccion y puerto de destino.

Ejemplo Host local: 192.168.1.1 ← SRCProxy NAT N: 200.16.17.1 H envıa un datagrama con direccion y puerto de

origen (192.168.1.1,80).N reenvıa (200.16.17.1,1234)Y guarda en TABLA[1234] = (192.168.1.1,80)Llega un paquete a N con destino (200.16.17.1,1234)El proxy encuentra que TABLA[1234] = (192.168.1.1,80) y lo reenvıaProblemas:

1. No vale que las IPs son unicas (si la aplicacion usa la dir. De IP en elPayload se arma lio).

2. El protocolo IP se torna como orientado a la conexion.

47

3. RROMPE ABSTRACCION, se basa en la existencia de “puertos” de lacapa superior (TCP o UDP).

4. Atrasa la adopcion de IPv6.

10.1. Protocolos de Control

ICMP: para debuggear la red mensajes tıpicamente enviados por routers.Los principales tipos de mensaje ICMP

Tipo de mensaje DescripcionDestination unreachable El paquete no se pudo entregar

Time exceeded Campo de tiempo de vida = 0Parameter problem campo de encabezado no valido

Source quench paquete reguladorRedirect Ensena a un enrutador sobre geografıa

Echo Pregunta a una maquina si esta vivaEcho reply Sı estoy viva

Timestamp request Misma solicitud de eso, pero con marca de tiempoTimestamp reply Misma que respuesta de eco, pero con marca de tiempo

11. ARP

Adress Resolution ProtocolARP: situado entre la capa de red y la CED.Se usa para descubrir la MAC asociada a una direccion IP.A dos niveles: Local y proxyARP

Figura 25: Tres redes/24 interconectadas;dos Ethernet y un anillo FFDI

Ejemplo

Envıo un paquete de 1 a 2: responde diciendo “Soy yo”.

Envıo un paquete de 1 a 4: mas difıcil 2 soluciones:

48

1. Proxy ARP: el ruter E3 contesta y el host 1 guarda (IP,E3)

2. Si el destino es una red remota, de inmediato se rutea afuera (massimple pero menos eficiente).

Se usa un cache interno para minimizar los pedidos.

11.1. RARP, BOOTP, DHCP

11.1.1. RARP

RARP: reverse ARP: dado una MAC encontrar el IP asociado, ejemplo unamaquina sin HD, Bootea y pide su IP.

Funciona en una red local solamente

11.1.2. BOOTP

BOOTP: como RARP pero a traves de redes, no solo LANs, se deben con-figurar las tablas de asignacion de IPs manualmente.

11.1.3. DHCP

DHCP: como BooTp pero no requiere que el (IP,MAC) este configuradomanualmente (se define un rango).

Tiene modos manual y automatico.Se utiliza un agente de retransmision DHCP en cada LAN para proveer

acceso al servidos DHCP remoto.Tambien soporta “leasing” temporal de direcciones.

Figura 26: Funcionamiento de DHCP

49

11.2. Protocolos de control de Internet

Internet consiste de sistemas autonomos conectados por un esqueleto de red.Ruteo entre sistemas autonomos (que pueden tener su propio ruteo interno.Ruteo interno (IGP)Se utilizo inicialmente RIP: ruteo por vector de distancia, luego se utilizo es-

tado de enlace.Actualmente se usa OSPF

11.3. OSPF - The interior gateway routing protocol

OSPF: open shortest path first, se transforma la red en un grafo dirigido concostros (que representan: distancia, retado, etc.)

Figura 27: (a) Un sistema autonomo, (b) representacion grafica de (a)

OSPF define jerarquıas y areas: cada sistema autonomo tiene un area de reddorsal (back bone), fuera de su aream su topologıa y detalles son invisibles.

Entonces hay 3 tipos de ruteo

1. Ruteo interno de un area (facil, se usa ruteo normal).

2. Ruteo entre areas: 3 pasos

De origen a Back bone.

De Back bone a destino.

Dentro del destino

3. Entre sistemas autonomos: EGP

Los cinco tipos de mensajes de OSPF:

50

Figura 28: Relacion entre sistemas autonomos, redes dorsales y areas en OSPF

Tipo de mensaje DescripcionHello Descubre quienes son los vecinos

Link state update Proporciona los costos del emisor a sus vecinosLink state ack Confirma la recepcion de la actualizacion del estado de enlace

Database description Anuncia que actualizaciones tiene el emisorLink state request Solicita informacion del socio

11.4. BGP - The exterior gateway routing protocol

Protocolo de puerta de enlace de frontera.Las conexiones entre ASs son generalmente entre areas grandes (paises), por

lo que hay que tener en cuenta las polıticas de trafico y no solo elegir la rutamas conveniente!

(Por ejemplo rute entre Israel y Siria).Por esto los routers se configuran manualmente.Atacando BGPBGP: es un protocolo no asegurado, las rutas declaradas no esan aseguradas,

se puede “mentir” y rromper todo en internet.Ataques:

1. Hacerse pasar por un BGP (o incluso ser dueno de uno).

2. Bloquear trafico.

3. Hacer que el trafico vaya a un lugar para ser espiado.

11.5. Internet Multicasting

11.6. Mobile IP

51

Figura 29: (a) conjunto de enrutadores de BGP (b) informacion enviada a F

11.7. IPv6

“Se acaban las direcciones IPv4”Objetivos:

1. Tener muchas direcciones de IP.

2. Reducir tamanos de las tablas de ruteo.

3. Simplificar el protocolo.

4. Brindar seguridad.

Para (1) IPv6 provee direcciones de 16Bytes (miles de direcciones por metrocuadrado).

Para (2) se utilizan encabezados de extension para reemplazar las opcionesde IPv4. Los routers pueden ignorarlos.

Para (3) IPv6 simplifica los campos del encabezado IP.Traffic class: prioridad para evitar la congestion “Multimedia Vs file trans-

fer” Flow: una etiquera especial de flujo, por ejemplo para determinar un anchode banda especial. Payload Lenght: Cuantos bytes siguen a los 40 del encabeza-do. Next headear: indica que tipo de encabezado de extension sigue, o si es el fi-nal y es un datagrama TCP o UDP (vuelve a rromper abstracciones). Hop Limit:Igual a TTl de IPv4.

Diferencias con IPv4

No hay campo IHL: el encabezado ahora tiene tamano fijo.Protocolo: no es necesario, el campo “next header” dice si sigue un encabeza-

do de extension o termina y es un paquete TCP o UDP.No hay fragmentos estan en los encabezados de extension.

52

Figura 30: Encabezado fijo del IPv6 (obligatorio)

No hay mas suma de verificacion: mejor performance.Encabezado de extension Descripcion

Opciones salto por salto Informacion diversa para los enrutadoresOpciones de destino Informacion adicional para el destino

Enrutamiento ruta total o parcial a seguirFragmentacion Manejo de fragmentos de datagramasAutenticacion Verificacion de la identidad del emisorCarga util de Informacion sobre el

seguridad encriptada contenido encriptado

Figura 31: Encabezados de extension salto por salto para datagramas grandes(jumbogramas)

53

Figura 32: Encabezado de extension para enrutamiento

12. Ipsec

IPsec: Internet Protocolo security.Estandares de la IETF (Internet Engineering Task Force).Disenado para IPv6 pero tambien se puede usar con IPv4.Puede proteger datagramas entre:

2 Hosts (Host to Hosts).

1 Router y un Host (Host to network).

2 Routers (Network to Network).

12.1. Implementacion de IPsec en IPv4

Implementar Host to Host es el ideal, llamado “integrated Mode” pero re-quiere cambiar todas las capas de red de cada Host.

¿Como implementar IPsec en red ya existentes sin tener que cambiar todo?

Cambiar solamente los Routers.

Patchear no intrusivamente los host.

12.1.1. Bump In the Stack BITS

IPsec intercepta los paquetes y los modifica.Ventaja: funciona en cualquier dispositivo IP.Desventaja: esfuerzo duplicado.

12.1.2. Bump in The Wire (BITW)

Similar a BITS pero sin tocar el HW/SW anterior.

54

Figura 33: BITS

Figura 34: BITW

12.2. Funcionamiento general de IPsec

Cuando dos Hosts se quieren comunicar usando IPsec deben

1. Acordar que parametros de comunicacion van a usar.

Maneras/protocolos para proteger los datagramas.

Modos de operacion de IPsec

2. Acordar que tipos de algoritmo criptograficos se van a usar para codificardatos.

3. Intercambiar claves seguras para procesar los datos.

4. Luego puede comenzar la comunicacion

12.2.1. 2 Maneras de Proteger los Datagramas

1. Encapsulating security Payloads (ESP): provee confidencialidad o integri-dad de los payloads, o ambos (Modo protegido).

2. Authentication Headers (AH): provee integridad de los payloads y auten-ticacion de origen.

55

12.2.2. Modos de operacion de IPSec

Transporte:

Se modifica a los encabezados (no se usa mas IPv4 sino que es IPv4 +IPsec).

Mas eficiente pero requiere que todos los soporten.

Rompe potencialmente NAT.

Figura 35: Transporte

Tunel:

Se encapsula a todo el datagrama (con el encabezado), que se pone en unnuevo datagrama IP (con un nuevo encabezado).

Igual que en las “VPNs” = Virtual Private Networks

Mas compatible pero mas costoso.

Figura 36: Tunel

56

13. La capa de transporte

13.1. Servicios que realiza para capas superiores

la capa de transporte provee:

Un servicio confiable a sus usuarios(orientado a la conexion) (El que nosfocalizaremos en la materia).

Un servicio eficiente a sus usuarios (no orientado a la conexion).

Diferencia con la capa de redLa de red (routers, etc) usualmente esta en la parte de la operadora de red

(ISP) mientras que la de transporte en la punta de conexion, es de los usuarios.Si la capa de red por ejemplo pierde paquetes, la capa de transporte se tiene

que encargar de solucionarlo.El servicio de transporte se ofrece a programadores/usuarios, las de mas

abajo no.Debe ser facil de usar!No debe exponer ninguna cuestion interna (retransmisiones, fragmentacion,

etc)La diferencia entre la capa de red se encarga de llevar un paquete a otro,

pero el paquete nunca sube.La capa de transporte rearma el paquete y se ejecuta en nuestra computa-

dora.Esta capa, va a ser la primera en que su capa superior es una capa de

aplicacion por lo que la interfaz debe ser mas simple, facil de usar.

Figura 37: Anidamiento de los TPDUs, los paquetes y las tramas

57

Figura 38: Diagrama de estado de un esquema sencillo de manejo de conexiones.Las transiciones escritas en cursiva son causadas por llegadas de paquetes. Laslınes continuas muestran la secuencia de estados del cliente. Las lınes puntuadasmuestran la secuencia de estados del servidor

13.2. Primitivas de la capa de transporte

Primitivas simples de la capa de transporte:Primitiva Paquete enviado SiginificadoLISTEN (ninguno) Se bloquea hasta que algun proceso intenta la conexion

CONNECT CONNECTION REQ. Intenta activamente establecer una conexionSEND DATA Envıa informacion

RECEIVE (ninguno) Se bloquea hasta que llega un paquete DATADISCONNECT DISCONNECTION REQ. Este lado quiere liberar la conexion

13.3. berkeley sockets

Las primitivas de comunicacion dadas son abstractas y no se usan en lapractica, sino que se usan los sockets de Berkeley.

Primitiva SiginificadoSocket Crea un nuevo punto terminal de comunicacionBind adjunta una direccion local a un socket

Listen Anuncia la disposicion a aceptar conexiones: indica el tamano de la colaAccept Bloquea al invocador hasta la llegada de un intento de conexion.

Connect Intenta establecer activamente una conexionSend Envıa datos a traves de la conexion

Receive Recibe datos de la conexionClose Libera la conexion

Importante: Close es de liberacion simetrica: cuando un lado cierra la conexionaun se pueden recibir mensajes hasta que el otro tambien la cierra.

(Antisimetrica es cuando se corta unidireccionalmente la comunicacion).

13.4. Elementos de los protocolos de la capa de transporte

Servicio Orientado a la Conexion

58

SIMILARIDAD CON CAPA DE ENLACEEl servicio orientado a la conexion de la capa de transporte envıa flujos de

bytes en cada paquete, y debe verificar que llegan en orden (y sin duplicar nicon errores).

Los protocolos se parecen a los de ventana deslizante de la capa de enlacede datos.

Hay una complicacion agregada: como la capa de transporte puede ser muchomas lenta que la fısica, la capa de red funciona como buffer y entonces puedenhaber mas paquetes duplicados son “almacenados” y entregados fuera de ordeno repetidos.

Con retransmisiones y confirmaciones (acknowledgments) de recepcion. Haymuchos paquetes dando vuelta.

El problema es cuando un paquete viejo tiene un numero de secuencia validaen una conexion nueva.

Figura 39: TSAPs: direccion interna de cada maquina (puerto en TCP/IP)NSAPs: direccion en capa de red (direccion IP en TCP/IP) y conexiones detransporte

Soluciones Para evitar que paquetes viejos causen confusion, se puede:

Utilizar TSAPs (puerto) desechables: no es muy util porque ya no sabemosa donde esta escuchando un servicio.

Abrir conexion con numero de secuencia: cada conexion lleva un identifi-cador que se va incrementando en nuevas conexiones, y evita confusion depaquetes atrasados en conexiones diferentes.

Problema: tenemos que recordar el numero “actual”, pero si se pierde lamemoria hay dificultades.

No hago nada: pero asumo que las capas de abajo me salvan las papas.

59

Figura 40: (a) Entorno de la capa de enlace de Datos ,(b) Entorno de la cpa detransporte

Usar una subred restringida. (sentido direccional a la red).

Colocar un contador de saltos en cada paquete.

Marcar el tiempo de cada paquete.

13.5. Metodo de Tomlinson

Se calcula un numero T que nos da el tiempo de vida de un paquete de capade transporte, queremos numerar a los paquetes de manera que su numero desecuencia se corresponda con su edad.

Debemos correlacionar el tiempo real con el de los numeros de secuencia.Cada conexion va a comenzar con un numero de secuencia inicial, que se va

a ir incrementando con cada pquete enviado.Igual que en la CED, a diferencia que el numero de secuencia inicial va a

cambiar de conexion en conexion.Se usa el reloj interno de cada maquina para elegir el numero de secuencia.Aun si se resetea la maquina el reloj interno sigue funcionando . . .Idea: T es tal que para cuando el reloj interno da una vuelta entera, el

paquete atrasadp (que podıa causar problemas).Cuando se cae una maquina y se resetea, debemos esperar T para asegu-

rarnos que no haya problemas.Para evitar la espera, podemos poner una restriccion a los numeros de se-

cuencia utilizados.Debemos enviar mensajes mas lento que como crece el reloj (en la practica

no hay problema)Idea asegurarse de no caer in the forbidden sectionPuedo caer tanto por mandar lento (caigo en la parte superior) o por mandar

rapido en la parte inferior de la region prohibida.Ejemplo:

T = 60segs, pulso del reloj 1 por segundo.

60

En t = 30segs un paquete se manda con numero secuencia 80.

El host se cae y se reinicia.

En t = 70 segs se reabre la conexion con numero inicial de secuencia 70.

Durante 15segs se envıan los paquetes numerados del 70 al 80.

En t=85 segs se envıa el paquete numerado 80

Figura 41: (a) Los TPDUs no pueden entrar a la zona prohibida (envıo demasi-ado rapido) (b) EL problema de la sincronizacion (envıo demasiado lento)

13.5.1. Direcionamiento

61

13.5.2. Establecer una Conexion

Para ponerse de acuerdo en los numeros iniciales de secuencia se ejecuta unprotocolo de 3 ias: 3 way handshake.

Ojo: hay que tener en cuenta que pueden haber mensajes de inicio de conexiontambien retrasados y descartados por el emisor.

Figura 42: Tres escenarios para establecer una conexion usando un acuerdo detres vias, CR significa Connection Request

(a) Opreracion Normal.

(b) Connection Request duplicada vieja que aparece de la nada.

(c) Connextion request duplicada y Ack duplicada.

13.5.3. Cerrar una Conexion

Liberacion antisimetrica, peligro de “abrupt disconnection with loss of data”.Queremos hacer liberacion “Simetrica” sin perdida de datos.Es imposible poner de acuerdo si se depende de un ultimo mensaje que se

puede perder o no.

(a) Caso normal del acuerdo de tres vıas.

(b) Perdida de la ultima Ack.

(c) Respuesta Perdida.

(d) Respuesta perdida y perdida de los DRs subsecuentes.

62

Figura 43: Desconexion abrupta con perida de datos

Figura 44: El problema del acuerdo Bizantino

Agregar temporizadorCada mensaje tiene un TimeOut que intenta retransmitir ese mensaje que

recibioN veces, si ahı falla cierro la conexion unilateralmente.Puede demorar tiempos en liberar la conexion.Peor caso:Todos los DRs iniciales se pierden y el emisor libera la conexion mientra que

el otro no es por ello que se implementan “timer keep alive” ver si esta vivo.

63

Figura 45: Cuatro escenarios de un protocolo para liberar una conexion

13.5.4. Control de Flujo y buffering

Se utiliza ventana deslizante como en CED.Pero como tenemos muchas conexiones, debemos manejar buffers dinamica-

mente para almacenar las ventanas de transmision y de recepcion.El receptor le va informando dinamicamente al emisor cuando puede enviar

paquete.Por dos razones:Memoria insuficiente no quiero que me llene el buffer.Velocidad de red provoca congestion.Actualemente como la memoria es barata el cuello de botella se produce en

la capacidad de carga de la red.Luego el contro se usa para regular la velocidad de transferencia y evitar

congestion.

13.5.5. Multiplexado

13.5.6. Recuperarse a una caıda

El protocolo TCP es orientado a la conexion por eso si se cae tenemos quever como solucionarlo.

SituacionEmisor manda un mensaje y espera un ak.LUego de esto el receptor le manda el mensaje a la de arriba y se rrompe y

se cae.Supongo que tengo algo que luego de resetearlo puedo recuperar el caso,pero el problema de carrera es , me llego bien (tengo que avisarle arriba), y

se caeentonces hay una posible condicion de carrera.

64

Figura 46: Asignacion dinamica de buffers. Las flechas muestra la direccion detransmision, los puntos suspensivos (...) indican una TPDU perdida

Vamos a analizar los distinto casos:S0 No esperaba un akS1 Esperaba un akDiferentes estrategias que tiene el emisor que manda, cuando le llega el

emisor diciendo “me caı”.SI O SI EL FLUJO DE DATOS TIENE QUE SER CONFIABLE

Figura 47: Diferentes combinaciones de la estrategia cliente servidor

PARCIALLLLLMoraleja: solo la capa N+1 puede recuperar la caıda de N .Si se cae el host, entero no se puede salvar la conexion de manera confiable.

65

14. TCP

Tcp provee un servicio confiable sobre IP.Conexiones full duplex (ida y vuelta), y punto a punto.No hay multicasting o Broadcasting.

Se establecen sockets entre el emisor y el receptor

Contienen IP mas el puerto.

Pueden tener varias conexiones a la vez.

Los puertos son naturales < 64k y los mas importantes son los < 1024

Puerto Protocolo Uso21 FTP Transferencia de archivos23 TELNET Conexion remota25 SMTP e-mail69 TPFP Simple transferencia de archivos79 FINGER Observa informacion sobre el usuario80 HTTP World Wide Web110 POP-3 Acceso remoto al e-mail119 NNTP USENET News

Los “daemons” son los procesos que atienden en un puerto en un servidor.

Para evitar cargar recursos se usa un daemon inetd, que los carga endemanda.

Una conexion TCP provee un flujo de datos (no de mensajes - los bor-de/lımites no se preservan).

14.1. Funcionamiento

1. Se divide el flujo a enviar en segmentos (cada uno tiene un encabezado de20 bytes).

2. El protocolo es basicamente ventana deslizante de tamano variable.

3. El numero ACK indica el proximo numero de secuencia (Byte esperado).

ACK es el ultimo que espero, por el tema del orden (No el ultimo q llegobien).

66

Figura 48: (a) cuatro segmentos de 512 bytes enviados como datagramas IPindependientes (b) Los 2048 Bytes de datos que se agregan a la aplicacion enuna sola llamada a Read

14.2. Encabezado TCP

Figura 49: Encabezado TCP

1. Puertos de origen y de destino.

2. Numeros de secuencia (el primer byte de este segmento).

3. Numero de Acknowledgment: indica el proximo byte esperado, no el ultimorecibido.

67

4. Longitud del encabezado TCP: cantidad en palabra (de 4 bytes) del en-cabezado, necesario porque tenemos opciones.

5. Banderas:

a) URG: datos urgentes(apuntador urgente: el deplazamiento a partirdel numero actual de secuencia en el que se encuentran los datosurgentes).

b) ACK:

Seteado indica que hay un Ack con piggybacking (y por lo tantoel numero de ack es valido).

No seteado: el segmento no contiene una informacion de recep-cion.

c) PSH: Push Data Inmediatly: el que recibe tiene que pasar todo loque tiene la capa superior.

d) RST: reestablece una conexion confundidad (caıda de Host, etc).Tambien se usa para rechazar segmento.

e) SYN: establece una conexion

Para iniciar una conexion (Call REQ), se setea SYN = 1 y ack= 0.

Para aceptar una pedido de conexion (Call ACC) se setea SYN= 1 y ack = 1.

f ) FIN: libera la conexion (pero continua recibiendo, lo que implica queFIN tiene numero de secuencia).

6. Tamano de ventana: cantidad de bytes que pueden enviarse comenzandopor el byte cuya recepcion se ha confirmado.

0 es cuando no hay buffer libre y se debe parar el envıo.

A veces 64K es demasiado poco:

RFC 1323 provee una “escala de ventana” variable hasta 230Bytes

7. Suma de verificacion: incluye el encabezado, los datos y el “pseudo en-cabezado”.

Ayuda a entregar paquetes mal entregador.

8. Opcionales: incluye el mecanismo para que cada host especifique la maxi-ma carga util que acepta.

Se anuncia en las CALL REQ y CALL ACC

Por defecto, 536 bytes de carga util.

68

Figura 50: “Pseudo encabezado, contiene las direcciones IP ¿es bueno o malo?”

69