unidad 3 redes

5/11/2018 Unidad 3 REDES - slidepdf.com

http://slidepdf.com/reader/full/unidad-3-redes-55a2327db89ed 1/45

qwertyuiopasdfghjklzxcvbnmq

wertyuiopasdfghjklzxcvbnmqw

ertyuiopasdfghjklzxcvbnmqwe

tyuiopasdfghjklzxcvbnmqwert

uiopasdfghjklzxcvbnmqwertyu

opasdfghjklzxcvbnmqwertyuio

asdfghjklzxcvbnmqwertyuiopa

dfghjklzxcvbnmqwertyuiopasd

ghjklzxcvbnmqwertyuiopasdfg

jklzxcvbnmqwertyuiopasdfghj

zxcvbnmqwertyuiopasdfghjklz

cvbnmqwertyuiopasdfghjklzxc

bnmqwertyuiopasdfghjklzxcvb

mqwertyuiopasdfghjklzxcvbnm

qwertyuiopasdfghjklzxcvbnmq

Investigación de La Unidad3.

Materia: Redes.

Maestro: Carlos Lopez May

15/11/2011

Integrantes:Gamboa Canto Luis JorgeDzic Chim Gracialiano.Orrega Erguera PedroAke Delgado EleazarPacheco Reyes Arturo



q y p g j q



3.1 Conmutación de circuitos.

La conmutación de circuitos es un tipo de comunicación que establece o crea un canal

dedicado (o circuito) durante la duración de una sesión. Después de que es terminada la sesión

(e.g. una llamada telefónica) se libera el canal y éste podrá ser usado por otro par de usuarios.

El ejemplo más típico de este tipo de redes es el sistema telefónico la cual enlaza segmentos de

cable para crear un circuito o trayectoria única durante la duración de una llamada o sesión. Los

sistemas de conmutación de circutos son ideales para comunicaciones que requieren que los

datos/infiormación sean transmitidos en tiempo real.

http://www.eveliux.com/mx/conmutacion-de-circuitos-y-paquetes.php

3.2 Conmutación de mensajes.

Este es el enlace entre el subsistema ASI-1 y la red ATN, se encarga de recibir y transmitir

los mensajes ubicándolos en los buzones correspondientes para su posterior traslado e

incorporación en la base de datos. El Sistema de Conmutación de Mensajes permite e

tratamiento de los mensajes recibidos y enviados realizando las validaciones y almacenamiento en

la base de datos. Los mensajes recibidos se validan a fin de ser separados y almacenados en su

respectiva posición dentro de la Base de Datos, donde esperan ser revisados y/o corregidos por e

operador del sistema.

Este sistema puede distinguir entre un NOTAM nuevo, reemplazo y cancelación. El sistema

permite trabajar con NOTAM locales e internacionales, estableciendo para los NOTAM locales una

numeración consecutiva automática independiente de la serie emitida.






3.3 Conmutación de paquetes.

Principios de la conmutación de paquetes:

Hasta antes de la década de 1970, el método más utilizado era la Conmutación de

Circuitos, el cual, debido al calificativo de ineficiente que recibió de muchas personas que

sostenían que no era ágil para las conexiones de datos y sobre todo por lo que dos dispositivos

conectados en red tienen que transmitir y recibir datos a una misma velocidad, lo cual limita la

utilidad de la red, entronces aparece la Conmutación de Paquetes y con ello sus respectivas

técnicas.

Un Paquete es un grupo de información que consta de dos partes: los datos propiamente

dichos y la información de control, en la que está especificado la ruta a seguir a lo largo de la redhasta el destino del paquete. Mil octetos es el límite de longitud superior de los paquetes, y si la

longitud es mayor el mensaje se fragmenta en otros paquetes.

Ventajasg0enerales:

- Los paquetes forman una cola y se transmiten lo más rápido posible

- Permiten la conversión en la velocidad de los datos.

- La red puede seguir aceptando datos aunque la transmisión se hará lenta.

- Existe la posibilidad de manejar prioridades(si un grupo de información es más importante que

los otros, será transmitido antes que dichos otros).

Tamaño del paquete:



Tamaño del paquete:

Está en relación con el tiempo de transmisión, es decir: Supongamos que tenemos que transmitir

un paquete de cuarenta octetos con tres octetos de cabecera desde la estación X a la estación Y

por medio de los nodos a y b; entonces el paquete irá primero desde la estación X al nodo a, y unavez recibido completo en el nodo a, se enviará al nodo b y cuando haya recibido el nodo b

completo al paquete se enviará a la estación Y. El tiempo de transmisión(despreciado el tiempo de

conmutación) será de: 129 (43 octetos * 3 transmisiones del paquete ).

Comparaciones Técnicas entre la Conmutación de Circuitos y de Paquetes

Para referirnos a este tema, en primer lugar abordaremos lo que se conoce con el nombre de

Prestaciones y luego se analizarán otras características:

Prestaciones:

Retardo de Propagación: Tiempo en el paso de información

entre nodo y nodo.

- Tiempo de transmisión: Tiempo que tarda el transmisor en enviar el bloque.

- Retardo de nodo: Tiempo que un nodo tarda para la comutación.

Otras características en:

Conmutación de circuitos:



Conmutación de Paquetes:

>- Los datos deben ser convertidos de Analógicos a Digitales por medio de un circuito virtual antes

de la transmisión.

- Tienen bits suplementarios relativos.

- Existe retardo previo a la transmisión.

> Datagramas:

>- Su llegada es en orden diferente.

- No existe establecimiento de llamada(son rápidos para mensajes cortos).

http://www.uazuay.edu.ec/estudios/sistemas/teleproceso/apuntes_1/conmutacion_paquetes.ht

m#principios1

3.3.1 Topología de las redes de paquetes.

TOPOLOGÍAS DE LAS REDES DE PAQUETES.

Estas son las topologías usadas para la distribución de paquetes, al igual que sus descripciones,

ventajas y desventajas.

Topología de bus

La topología de bus es la manera más simple de organizar una red. En la topología de bus, todos

los equipos están conectados a la misma línea de transmisión mediante un cable, generalmente

coaxial. La palabra “bus” hace referencia a la línea física que une todos los equipos de la red.

La ventaja de esta topología es su facilidad de implementación y funcionamiento. Sin embargo,

esta topología es altamente vulnerable, ya que si una de las conexiones es defectuosa, esto afecta

a toda la red.

Topología de estrella

En la topología de estrella, los equipos de la red están conectados a un hardware denominado

concentrador. Es una caja que contiene un cierto número de sockets a los cuales se pueden

conectar los cables de los equipos. Su función es garantizar la comunicación entre esos sockets.

A diferencia de las redes construidas con la topología de bus, las redes que usan la topología de

estrella son mucho menos vulnerables, ya que se puede eliminar una de las conexiones fácilmente

desconectándola del concentrador sin paralizar el resto de la red. Sin embargo, una red con

topología de estrella es más cara que una red con topología de bus, dado que se necesita

hardware adicional (el concentrador).

T l í ill

http://www.uazuay.edu.ec/estudios/sistemas/teleproceso/apuntes_1/conmutacion_paquetes.htm#principios1







Topología en anillo

En realidad, las redes con topología en anillo no están conectadas en bucles. Están conectadas a

un distribuidor (denominado MAU, Unidad de acceso multiestación) que administra la

comunicación entre los equipos conectados a él, lo que le da tiempo a cada uno para “hablar”.

Las dos topologías lógicas principales que usan esta topología física son la red en anillo y la FDDI

(interfaz de datos distribuidos por fibra). Transmisión continua, Ventana de transmisión.

Característica de algunos protocolos de conmutación de paquetes (X.25).

En otros protocolos a veces se imita poniendo números de secuencia en los campos de datos.

Será necesario para aprovechar la característica, tener un sistema de numeración de tramas

(Frame Relay, X25, etc).

Se trata de que el asentimiento de un paquete (desde que sale el último bit del paquete hasta

que llega el asentimiento) tarde menos que el envío de toda una secuencia de tramas numeradas

(o de una parte de la misma).

Así se aprovecha siempre el canal y se puede realizar envío contínuo.

Ventana de transmisión:

Wt= 1 + TAS/RI

TAS = Tiempo transcurrido desde que se envía el último bit de una trama hasta que se recibe e

último bit del asentimiento.

RI = Retardo de transmisión de una trama.

También hay protocolo orientados a diferentes tipos de conexión, aquí se describen las siguientes

Protocolos orientados a conexión y no-conexión

Los protocolos pueden ser orientados a conexión y orientados a no-conexión. Los orientados a

conexión, las entidades correspondientes mantienen las información del estatus acerca dedialogo que están manteniendo.

Esta información del estado de la conexión soporta control de error, secuencia y control de flujo

entre las correspondientes entidades. Es decir, La entidad receptora le avisa a la entidad

transmisora si la información útil llego correctamente, si no es así también le avisa que vuelva a

retransmitir.

El control de error se refiere a una combinación de detección de error (y corrección) y

reconocimiento (acknowledgment). El control de secuencia se refiere a la habilidad de cadaentidad para reconstruir una serie de mensajes recibidos en el orden apropiado. El control de flujo

se refiere a la habilidad para que ambas partes en un dialogo eviten el sobreflujo de mensajes



se refiere a la habilidad para que ambas partes en un dialogo eviten el sobreflujo de mensajes

MTU, Maximum Transfer Unit (unidad de transferencia máxima). Es el tamaño máximo de

paquete que se puede dar en una capa de la arquitectura de protocolos (generalmente la capa de

enlace de datos)

Por tanto si algún paquete que viene de una red con un tamaño mayor que la MTU de la red

actual, el gateway entre la primera y la segunda red debe adaptar el tamaño de dicho paquete a la

MTU de la red actual mediante una fragmentación.

La posibilidad de reensamblado es opcional en el caso en que dicho paquete vuelva a una red con

una MTU mayor que la actual, pero no suele hacerse por necesitar esta opción de un

procesamiento mayor.

Los protocolos orientados a conexión operan en tres fases.

La primera fase es la fase de configuración de la conexión, durante la cual las entidades

correspondientes establecen la conexión y negocian los parámetros que definen la conexión.

La segunda fase es la fase de transferencia de datos, durante la cual las entidades

correspondientes intercambian mensajes (información útil) bajo el amparo de la conexión.

Finalmente, la última fase, fase de liberación de la conexión, en la cual ambas entidades se ponen

de acuerdo para terminar la conexión. Un ejemplo de la vida diaria de un protocolo orientado a

conexión es una llamada telefónica. La parte originadora (el que llama) deberá primero “marcar”el número del teléfono usuario (abonado) destino. La infraestructura telefónica deberá asignar e

circuito extremo-extremo, entonces hace timbrar el teléfono del usuario destino. Al momento que

éste levanta el teléfono se establece la llamada o conexión y ambos empiezan a conversar. En

algún momento, alguno de los dos cuelga, y la conexión de termina y se libera el circuito

Entonces se termina la llamada.

Los protocolos orientados a no-conexión difieren bastante a los orientados a conexión, ya que

estos (los de no-conexión) no proveen capacidad de control de error, secuencia y control de flujo

Los protocolos orientados a no-conexión, están siempre en la fase de transferencia de datos, y no

les interesa las fases restantes de configuración y liberación de una conexión.

Los protocolos orientados a no-conexión se emplean en aplicaciones donde no se requiera mucha

precisión. Tal es el caso de la voz, música o el video. Pero en cambio en aplicaciones donde se

requiera mucha precisión [transacciones electrónicas bancarias, archivos de datos, comercio

electrónico, etc.] se utilizarían los protocolos orientados a conexión.

Protocolos ORIENTADOS A BITS y ORIENTADOS A BYTE (caracter)

BYTE oriented protocols

En cualquier sesión de comunicación entre dispositivos, códigos de control son usados para



Interchange) o código EBCDIC (Extended Binary Coded Decimal Interchange Code). En contraste,

los protocolos orientados a bits confian en bits individuales para códigos de control. Los

protocolos orientados a Byte transmiten los datos como si fueran cadenas de caracteres. Elmétodo de transmisión es asíncrono. Cada caracter es separado de un bit de inicio y un bit de

paro o termino, y no es necesario un mecanismo de reloj.

Ejemplos de caracteres usados: SYN (synchronize), SOH (start of header), STX (start of text), ETX

(end of text).

BIT oriented protocols

En una transmisión orientada a bit, los datos son transmitidos como constantes ráfagas de bits.

Antes de que la transmisión de datos empiece, caracteres especiales de sincronía son transmitidospor el transmisor, así el receptor puede sincronizarse a sí mismo con la ráfaga de bits. Este patrón

de bits es comunmente representado en una cadena de 8 bits.

SDLC (Synchronous Data Link Control) de IBM es un protocolo orientado a bits. Su caracter de

sincronia (sync) es la cadena de bits 01111110, y esto es seguido por una dirección de 8 bits, un

campo de control y por por los datos (información útil). Una vez que el sistema receptor recibe

esas tramas iniciales, empieza a leer 8 bits a la vez (1 byte) desde la cadena de bits hasta que

aparezca un error o una bandera de término. Los protocolos SDLC y HDLC (High-level Data Link

Control) de IBM son orientados a bit. HDLC es usado comúnmente en las redes de conmutación

de paquetes X.25, SDLC es un subconjunto de HDLC.

Los protocolos orientados a bits son los usados comúnmente en la transmisión en las redes de

datos LAN y WAN.

http://www.mitecnologico.com/Main/TopologiaRedesDePaquetes

3.3.2 Datagramas y circuitos virtuales

Técnicas de Conmutación:

>Para la utilización de la Conmutación de Paquetes se han definido dos tipos de técnicas: los

Datagramas y los Circuitos Virtuales.

> Datagramas:

>- Considerado el método más sensible

- No tiene fase de establecimiento de llamada

- El paso de datos es más seguro

- No todos los paquetes siguen una misma ruta

- Los paquetes pueden llegar al destino en desorden debido a que su tratamiento esindependiente.






>- Son los más usados

- Su funcionamiento es similar al de redes de conmutación de circuitos.

- Previo a la transmisión se establece la ruta previa a la transmisión de los paquetes por medio depaquetes de Petición de Llamada (pide una conexión lógica al destino) y de Llamada Aceptada (en

caso de que la estación destino esté apta para la transmisión envía este tipo de paquete );

establecida la transmisión, se da el intercambio de datos, y una vez terminado, se presenta el

paquete de Petición de Liberación(aviso de que la red está disponible, es decir que la transmisión

ha llegado a su fin)

- Cada paquete tiene un identificador de circuito virtual en lugar de la dirección del destino

- Los paquetes se recibirán en el mismo orden en que fueron enviados.

http://www.uazuay.edu.ec/estudios/sistemas/teleproceso/apuntes_1/conmutacion_paquetes.ht

m#principios1

3.3.2.1 Estructura de conmutadores

Un conmutador es un dispositivo de interconexión de redes de otros dispositivos o computadoras.

Conocido también como “switch”, el conmutador es un aparato que interconecta dos o más

segmentos de una misma red para el enlace de datos, funcionando como un puente. Se dice queen una “red en estrella” el conmutador es el centro.

La funcionalidad de un conmutador está dada por la multiplicación de redes y datos a transmitir,con la subsiguiente necesidad de un orden y sistematización para su operación. Un conmutadorfunciona como un filtro en la red, mejorando el rendimiento y la seguridad de las conexiones alprovocar una fusión de éstas.

Un conmutador se usa comúnmente en una red telefónica, por ejemplo, en una empresa,permitiendo que todos los teléfonos personales estén conectados entre sí para la ejecución dellamadas internas y para la transmisión de llamadas externas. Pero también se emplean conmucha más complejidad los conmutadores en una red informática, conectando puertos unos conotros y redes unas con otras.

Los puentes o conmutadores pueden conectarse a su vez entre sí, pero sólo puede existir un únicocamino entre dos puntos de la red. De lo contrario, puede ocurrir un “bucle” en la red y latransmisión de datos se altera, creando una espiral infinita. Así, se producen las “inundaciones” enla red, como consecuencia de las cuales las comunicaciones fallan.

Los conmutadores pueden clasificarse en “store-and-forward” (que almacenan cada grupo de

datos en un buffer antes de retransmitirlo), el “cut-through” (minimizan la demora de losprimeros, reduciendo el tiempo de almacenamiento de la información), el “adaptative-cut-through” (soportan procesos de los dos tipos anteriores), el “layer 2 switches” (funcionan como

multi-puertos) y otros.

El uso de los conmutadores está muy difundido en la actualidad y si bien se utilizan en procesos




http://www.definicionabc.com/general/sistematizacion.php



http://www.definicionabc.com/tecnologia/almacenamiento.php








El uso de los conmutadores está muy difundido en la actualidad y si bien se utilizan en procesos

En esta sección se describen las características recomendables propias de los conmutadores.

• STP (Spanning Tree Protocol, protocolo del árbol de expansión)

El protocolo STP se utiliza para calcular la mejor ruta entre conmutadores cuando existen variosconmutadores y varias rutas en la red. Esto es necesario para evitar el envío de datos por variasrutas a la vez, lo que redunda en duplicación de los datos. En las redes grandes es esencial quelos conmutadores admitan este protocolo, el cual no suele estar disponible en los conmutadorespequeños.

• Compatibilidad con VLANLas redes VLAN sirven para segmentar la red en grupos de equipos con necesidades decomunicación similares, de manera que se reduce el tráfico en la red. Esta configuración puedeutilizarse en redes de cualquier tamaño, pero resulta especialmente útil cuando se instalanpocos conmutadores pero de gama alta. Los conmutadores de bajo costo no suelen ser

compatibles con las redes VLAN. Esto no resulta importante en las redes pequeñas, pero lacompatibilidad con las redes VLAN es esencial en las redes de gran tamaño.

• Conectividad de vínculo ascendenteLos vínculos ascendentes se utilizan para conectar conmutadores en una red. Mientras que todoslos conmutadores pueden conectarse mediante vínculos Ethernet ordinarios, los conmutadoresde gama alta admiten vínculos de mayor velocidad que utilizan protocolos troncales diseñadospara conexión entre conmutadores.

• ConsolidaciónLa incorporación de otras funciones en el conmutador puede reducir los costos y mejorar laadministración. Por ejemplo, los conmutadores de bajo costo destinados a las sucursales

pequeñas pueden incluir un enrutador y un servidor de seguridad e incluso un módem de bandaancha. Además de la reducción de costos, también se simplifica la administración, ya que setrabaja con una sola unidad física. Los conmutadores superiores también pueden incorporar unmódulo enrutador, denominado conmutador de nivel 3, así como otras funciones de equilibriode carga y servidor de seguridad. Ello también mejora la administración de la red. Este tipo deconsolidación debe considerarse con detenimiento, ya que puede comportar una menorresistencia porque, en caso de error del conjunto de la unidad, todos los servicios consolidadosquedarían anulados.

Clases de conmutadores

En esta sección se definen varias clases de conmutadores. Estas clases son flexibles y puede darseel caso de que un modelo específico de un fabricante pertenezca a varias clases debido a lasopciones de actualización, mientras que dos modelos diferentes de un mismo fabricante puedenpertenecer a la misma clase. Las clases de conmutadores descritas en esta sección son:

• Clase 1: Conmutadores fijos inferiores

• Clase 2: Conmutadores flexibles inferiores

•

Clase 3: Conmutadores de gama media•

Clase 4: Conmutadores superiores



p

La conmutación de paquetes es el envío de datos en una red de computadoras. Un paquete es un

grupo de información que consta de dos partes: los datos propiamente dichos y la información de

control, que especifica la ruta a seguir a lo largo de la red hasta el destino del paquete. Existe unlímite superior para el tamaño de los paquetes; si se excede, es necesario dividir el paquete en

otros más pequeños.

http://es.wikipedia.org/wiki/Conmutaci%C3%B3n_de_paquetes

3.3.3 Encaminamiento en redes de paquetes.

ENCAMINAMIENTO EN REDES DE CONMUTACIÓN DE PAQUETES

El problema del encaminamiento

Consiste en cómo establecer una ruta óptima para una instancia de comu- nicación desde una

fuente a un destino. La ruta elegida debe optimizar en lo posible algún parámetro o conjunto

de parámetros, como el retardo de tránsito, el número de saltos, el tamaño de las colas, el

caudal de salida. . .

En general, las decisiones de encaminamiento son incrementales. Cada nodo de

conmutación sólo debe decidir a qué nodo adyacente debe transmitir los datos, quedando así

establecida la parte correspondiente de la ruta.

Para calcular las rutas se usa un algoritmo de encaminamiento, que dado un destino

decide la línea de salida adecuada. Es necesario además una estructura de información donde

almacenar localmente los pares (destino- línea de salida) resultantes, que recibe el nombre de

tabla de encaminamiento. Asímismo, los nodos deben coordinar el cálculo de las rutas e infor-

marse entre sí de los cambios que se produzcan por ejemplo en la topología de la red, tarea que es

llevada a cabo por un protocolo de encaminamiento.

Propiedades exigibles a los algoritmos de encaminamiento:

Deben ser robustos, capaces de adaptarse a los posibles cambios de to- pología (fallos, bajas

o altas en enlacesy nodos) sin necesidad de abortar y reinicializar toda la red.

Deben ser estables, en el sentido de converger a un resultado de la forma más rápida posible.

No deben generar bucles en el encaminamiento.

Si no hay ningún motivo no deben favorecer a algunos usuarios frente a otros.

http://es.wikipedia.org/wiki/Red_de_computadoras



http://es.wikipedia.org/wiki/Informaci%C3%B3n










Clasificación de los algoritmos de

encaminamiento

Estáticos o no adaptativos: Las rutas soncalculadas de

antemano y cargadas en los nodos durante su inicialización y permanecen invariantes durante

largos períodos de tiempo.

Dinámicos o adaptativos: Cambian sus decisiones de encaminamiento para reflejar

cambios en la topología y/o en el tráfico. Pueden diferir en los instantes de adaptación

(de manera periódica o cuando cambie de manera significativa la topología o el tráfico) y en la

forma de obtener la información y tomar las decisiones:

• Aislados: Los nodos basan sus decisiones en información obtenida localmente.

• Centralizados: Un nodo de control utiliza la información obtenida de todos los nodos de la

red y toma las decisiones de encaminamiento, que transmite posteriormente al resto de

los nodos de la red.

• Distribuidos: Las decisiones de encaminamiento se toman localmente en los nodos y

se basan en información que obtienen de parte (sólo adyacentes) o de la totalidad del

resto de nodos.

En lasredes actuales el encaminamiento es dinámico y distribuido.



Principio de optimización

Si modelamos la red como un grafo etiquetado, esto es, como una colección de nodos y enlaces

punto a punto y acada enlace le asignamos un valor que representa el coste de enviar un paquete por

dicho enlace, que será función de uno o más parámetros según lo que interese optimizar, el coste de

una ruta se obtiene a partir de la suma delcoste de cada uno de sus enlaces.

Principio de optimización: Cualquier subcamino dentro de un camino óptimo es, a su vez,

óptimo.

Como consecuencia del principio de optimización:

El conjunto de rutas óptimas a un destino dado desde cualquier nodo forma un árbol, que

puede no ser único, cuya raíz es el nodo destino, y que se conoce como árbol sumidero

(sink tree).

Las decisiones de encaminamiento se pueden tomar localmente.

El cálculo de los caminos óptimos puede llevarse a cabo de manera distribuida.

Los algoritmos de encaminamiento intentaránobtener rutas lo más aproximadas a las del árbol

sumidero.

A continuación se muestra una red de ejemplo y el árbol sumidero para el nodo B, tomando

como métrica el número de saltos.



B

AC

E

F D

G

J

I

H

NL

K M O

B

AC

E

F D

G

JI

H

NL

K M O



Ejemplos de algoritmos de encaminamiento

Shortest Path

En el algoritmo Shortest Path con los costes asignados a cada enlace se calcula, para cada par de

nodos, la ruta de menor coste total, es decir, el camino más corto.

Hay varios algoritmos propuestos para ello, aunque quizá el

más popular seael de Dijkstra.

El algoritmo de Dijkstra es iterativo. Tras la k-ésima iteración, para una fuente se conocen los

caminos de coste mínimo a kno

dos destino, y entre loscaminos

de coste mínimo atodos

losno

dosdestino, estos k caminos tienen los k menores costes.

Una vez conocidas las mejores rutas entre cada par de nodos, se construyen las tablas de

encaminamiento.

Este algoritmo de encaminamiento por sí solo y de forma es- tática raras veces se usa como

tal, pero las técnicas para hallar elcamino más corto son ampliamente usadas en otros algoritmos

de encaminamiento.

Multipath

Dado que, en general, se obtienen mejores prestaciones repar- tiendo el tráfico entre varias

rutas, una mejora del algoritmo Shor- test Path consiste en tomar las N mejores rutas entre cada par

de nodos, y repartir el tráfico entre ellas en base aalgún criterio, por ejemplo, prioridad del tráfico,

o simplemente de forma aleatoria asignando a cada una de ellas una determinada probabilidad. Es-

te algoritmose denomina encaminamiento de caminos múltiples o Multipath.



Aleatorio

En este algoritmo cada nodo elige de forma aleatoria una línea de salida de entre las posibles.

Si la red es rica en conexiones, el algoritmo aleatorio hace un excelente uso de las rutas

alternativas, conviertiéndolo en un algoritmo muy robusto, aunque en general muy poco eficiente

y de

bajas prestaciones.

Flooding

Es un sencillo algoritmo de encaminamiento estático, donde cada paquete recibido en un nodoes reenviado por todas las líneas, excepto por la que llegó. Obviamente, si no se toman medidas

para parar la explosión de paquetes, el número de duplicados crece indefinidamente. Una forma

de hacerlo consiste en incluir un contador que se decrementa en cada salto, y cuando llega a cero,

el paquete se descarta. Este contador debe inicializarse al número de saltos entre fuente y

destino. Si éste no fuese conocido, debe ser inicializado a la distancia mayor (en saltos) entre

cualesquiera dos nodos de la red.

Aplicaciones del Flooding:

Aplicaciones sensibles a pérdidas, dada su enorme robustez, ya que es prácticamnete imposible

que un paquete no llegue a su destino.

Aplicaciones de difusión (broadcast).

Evaluación de otros otros algoritmos, ya que al elegir todos los caminos, también elige el

más corto.



Hot Potato

Un sencillo algoritmo dinámico aislado es el Hot Potato, que consiste en reenviar cada paquete

hacia la línea que posee menos paquetes en cola, independientemente de cuálsea su destino.

Unaposible variación consiste en asignar costes a las líneas de salida, y basar la decisión en los

tamaños de las colas y en los

costes.

Aprendizaje hacia atrás

Es también un algoritmo dinámico aislado, que consiste en que cada nodo atravesado por unpaquete aprenda de éste donde está su nodo fuente, para cuando tenga que encaminar un

paquete hacia él.Para ello, debe incluirse en los paquetes la dirección del nodo fuente y un contador

que se incrementa en cada salto. Los nodos irán registrando en una tabla la información obtenida

de los paquetes vistos, descubriendo tras cierto tiempo la ruta de menor número de saltos a

cada nodo.



Algoritmos centralizados

Cada cierto tiempo cada nodo envía a un nodo central, RCC (Routing Control Center), la

información de estado que ha po- dido recoger localmente, como una lista de nodos

adyacentes, longitudes actuales de sus colas, tráfico procesado por línea, etc.

Basado en toda la información, el RCC calcula la mejor ruta para cada par de nodos, por

ejemplo con un algoritmoShortest Path, construye las tablas de encaminamiento y las envía a los

nodos.

Ventajas:

El RCC posee una información muycompleta, por lo que sus decisiones son casi perfectas.

Se libera a los nodos de tener que ejecutar algoritmos de encaminamiento.

Inconvenientes:

Si el tráfico y la topología son muy cambiantes son necesarios cálculos muy frecuentes con el

consiguiente exceso de carga en la red.

Vulnerabilidad del RCC: Problemas si se cae el RCC o si algún nodo no puede comunicarse

con el RCC, por caídas en la ruta usada para tal efecto.

Los nodos próximos al RCC pueden sufrir un peor servicio al estar las líneas más cargadas con

tráfico de control.

Los nodos próximos al RCC conocen las nuevas tablas antes que los más alejados, lo que puede

dar lugar a inconsistencias en el encaminamiento.



Vector de Distancias

Es un algoritmo de encaminamiento iterativo, asíncrono y distribuido. Es distribuido porque

cada nodo recibe cierta infor- mación de sus vecinos, recalcula las tablas de encaminamiento y

distribuye los resultados de vuelta a sus vecinos. Es iterativo porque este proceso continúa hasta

que no se intercambia más información entre los vecinos (se detiene a sí mismo). Y es asín- crono

porque no precisa que todos los nodos operen al unísono. Estas tres características lo convierten

en un algoritmo muy in- teresante.

La estructura de datos principal del algoritmo es la tabla de distancias que se mantiene en

cada nodo, que contiene una fila para cada destino de la red y una columna para cada vecino

directo del nodo.

La entrada (i, j) de la tabla para un nodo X da la distancia estimada de X a i a través del

vecino j, y se calcula como:

DX(i, j) = c(X, j) + mínwD j(i, w)

siendo w cualquier vecino de j.

Cada cierto tiempo, cada nodo recibe de (y envía a) sus vecinos una lista de la distancia estimada a

cada nodo de la red (distancia=∞ si ésta es desconocida). Esta lista recibe el nombre de vector

de distancias. Suponiendo que cada nodo conoce la distancia a sus vecinos, el cálculo de las tablas

de encaminamiento con las líneas de salida de la mejor ruta a cada nodo destino es inmediato. Cabe

resaltar que en el cálculo de las nuevas tablas no intervienen las tablas antiguas.



A continuación se muestran los vectores de distancias y la nueva tabla de encaminamiento

para A resultado de la ejecución del algoritmo.

A B

D

C E

Vectores recibidos por A de sus vecinos:

Destino B C D

A 5 4 6

B 0 9 3

C 12 0 3

D 6 6 0

E 2 7 5

Distancia a A de cada vecino:

AB AC AD

4 6 2

Nueva tabla de encaminamiento para A, que distribuirá a sus vecinos:

Destino Distancia Línea de salida

A 0 -

B 4 B

C 5 D

D 2 D

E 6 B



Este algoritmo tiene un serio inconveniente: aunque las bue-

nas noticias (como que un nodo que había caído se recupera) se extienden rápidamente, las malas

noticias (como la caída de un nodo) se propagan más lentamente. Este hecho se conoce como el

problema de cuenta hasta infinito, ya que infinito (nodo inalcanzable) es el valor que debería

hallarse en las tablas para dicho nodo caído. Obviamente, dependerá del valor numérico elegido

para representar infinito, el número de intercambios necesarios para alcanzar dicho valor. En el

caso del número de saltos, debe elegirse la longitud del camino más largo más uno. Más problemá- tico

es, por ejemplo, el caso del retardo, pues un retardogrande hacia un nodo podría inducir a error

al considerar al nodo encuestión caído.

A B C D E A B C D E

Inf. Inf. Inf. Inf.

1 Inf. Inf. Inf. 1 2 Inf. Inf.

Inicialmente

Tras 1 intercambio Tras 2

intercambios

1 2 3 4

3 2 3 4 3 4 3 4

Inicialmente

Tras 1 intercambio Tras 2 intercambios

1 2 3 Inf. Tras 3intercambios

5 4 5 4 Tras 3 intercambios

1 2 3 4 Tras 4intercambios

5 6 5 6 Tras 4 intercambios

7 6 7 6 ... ... ... ...

Inf. Inf. Inf. Inf.

Tras 5 intercambios

Contar desde infinito Contar hasta infinito



Se han propuesto muchas soluciones para el problema de contar

hasta infinito, como el algoritmo Split Horizon. Este algoritmo funciona exactamente igual que el

algoritmo de Vector de Distan- cias, salvo que la distancia a un nodo i es enviada como infinita

sobre la línea usada para enviar paquetes hacia i, haciendo así que la cuenta hacia infinito sea

mucho más rápidaque sin usar este algoritmo. Aún siendo ampliamente usado, sin embargo el

algoritmo falla en algunos casos.

A B C D E A B

1 2 3 4 InicialmenteC

Inf. 2 3 4 Tras 1intercambio Caida enlace C-D

Inf. Inf. 3 4 Tras 2 intercambiosInf. Inf. Inf. 4 Tras 3 intercambios D Inf. Inf. Inf. Inf. Tras 4 intercambios

Contar hasta infinitocon "Split Horizon"

Caso donde falla el "Split Horizon"

Por último señalar que el encaminamiento Vector de Distan-

cias, ideado por Bellman y mejorado por Ford y Flukerson, tam- bién recibe el nombre de Bellman-

Ford distribuido en honor a sus inventores. Fue el algoritmo inicial de ARPANET y desde entonces

se ha utilizado en muchos protocolos, entre ellos el RIP (Routing Information Protocol) de

Internet y el BGP (Border Gateway Protocol).



Estado de Enlace

Es también un algoritmo de encaminamiento distribuido e iterativo, cuyo funcionamiento

puede resumirse en cinco partes. Ca- da nodo debe:

1.Descubrir a sus vecinos y aprender sus direcciones de red.

2. Medir el coste a cada vecino.

3. Construir un paquete con esa información.

4. Enviar ese paquete a todos los nodos de la red.

5. Calcular el camino más corto a cada nodo.

Construcción de lospaquetes de estado del enlace

Los paquetes de estado del enlace deben llevar la dirección del emisor, un número de secuencia

y una lista de vecinos con los retardos estimados hasta ellos. La construcción y distribución de

estos paquetes puede hacerse periódicamente, o cuando ocurre algún hecho significativo, como

la caída o recuperación de una línea o de un nodo.

Distribución de lospaquetes de estado del enlace

Es una parte complicada del algoritmo, ya que el hecho de que algunos nodos reciban los

paquetes primero, y por tanto también cambien su forma de encaminar, puede llevar a

inconsistencias.

Para distribuir los paquetes de estado se puede usar el algoritmo Flooding, usando un número

de secuencia en cada paquete para controlar la explosión de paquetes.



Cálculo de las nuevas rutas

Una vez recibidos todos los paquetes de estado de todos los nodos, puede usarse un

algoritmo Shortest Path, como el de Dijkstra, para hallar el camino más corto a cada destino.

El algoritmo de Dijkstra calcula el camino de coste mínimo desde un nodo fuente al resto

de nodos de la red. Es un algoritmo iterativo que necesita k iteraciones para obtener los caminos

óptimos a k nodos destino.

Ejemplo

Como ejemplo, vamos a considerar la red de la figura, y vamos a calcular los caminos de coste mínimode A a cada destino posible,

utilizando el algoritmo de Dijkstra.

5

B 3 C

2 5

A 2 3 1 F

1 2 D E

1

El algoritmo consta de un paso de inicialización, seguido de un

bucle, que se ejecuta tantas veces como nodos haya en la red. Al terminar, se habrán calculado los

caminos más cortosdesde el nodo fuente a cualquier otro nodo de la red.



Consideramos la notación:

c(i, j): coste del enlace del nodo i al nodo j. Si los nodos i y j no están conectados

directamente, entonces c(i, j) = ∞. Suponemos que c(i, j) = c(j, i), aunque el algoritmo

funciona igualaunque no sean iguales.

D(v): coste del camino menos costoso desde el nodo fuente al destino v, en esta iteración del

algoritmo.

p(v): nodo previo(vecino a v) a lo largo del camino decoste mínimo desde la fuente a v.

N: conjunto de nodos para los que se conoce definitivamente el camino de coste mínimo desde

la fuente.

El pseudocódigo sería de la forma:

Inicialización: N={A}

para cada nodo v,

si v es adyacente a A, entonces D(v) = c(A,v)

si no, D(v) = inf

Bucle (hasta que todos los nodos estén enN):

buscarw

no enN tal

que D(w) sea mínimo añadir w a N

actualizar D(v) para cada v adyacente a w

que todavía no esté en N:

D(v) = mín(D(v),D(w)+c(w,v))



En este caso el resultado de la ejecución del algoritmo es:

it N D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),

0 A 2,A 5,A 1,A

1 AD 2,A 4,D 2,D

2 ADE 2,A 3, E

3 ADEB 3, E

4 ADEBC5 ADEBCF

Por último decir que este algoritmo fue y es ampliamente usado

en las redes actuales. Por ejemplo, el protocolo OSPF (Open Shortest Path First), usado en

Internet, utiliza un algoritmo de este tipo.



Encaminamiento intra SA en Internet

Históricamente, se han venido usando en mayor medida dos protocolos de encaminamiento en

el interior de los SA de Internet:

RIP (Routing Information Protocol) OSPF (Open

Shortest Path First)

RIP

RIP utiliza el algoritmo Vector de Distancias, con métrica el número de saltos. El coste

máximo de un camino está limitado a 15 saltos, por lo que se limita el alcance de RIP a SA que

tengan menos de 15 saltos de diámetro. Los vectores de distancia se intercambian entre vecinos

cada 30 segundos, empleando mensajes RIP de actualización.

Si un router no tiene noticias de uno de sus vecinos en 180 segundos, considerará que éste

es inalcanzable. Cuando esto ocurre, modifica la tabla de encaminamiento local y propaga esta

información.

OSPF

OSPF utiliza el algoritmo Estado de Enlace. Propaga la información de estado de enlace

mediante Flooding y utiliza el algoritmo de Dijkstra para el cálculo de los caminos de coste mínimo.

No impone ninguna métrica concreta, el coste de cada enlace se fija por el administrador de la

red.

Las actualizaciones se hacen cuando un nodo se da cuenta de que hay un cambio en el estado

de un enlace, o periódicamente cada 30 minutos aunque no se haya producido ningún cambio

local.Soporta jerarquía dentro de un SA. Cada SA puede configurarse en áreas y cada área ejecutar

su propio algoritmo de encaminamiento de estado de enlace OSPF. Dentro de cada área uno o

más routers frontera de área son los responsables de encaminar los paquetes hacia fuera del área.



Encaminamiento jerárquico

Hasta ahora hemos considerado una red como un conjunto de routers interconectados que

ejecutan el mismo algoritmo para calcular las rutas. En la práctica no es así, por dos motivos fun-

damentalmente:

Escala: Según crece la red lo hace el número de routers y la sobrecarga debida al cálculo,

almacenamiento y distribución de la información de encaminamiento se hace prohibitiva.

Autonomía administrativa: Deseo de cada compañía de ad- ministrar su red de forma

autónoma, aunque pueda seguir accediendo a y ser accesible por el exterior.

Estos problemas pueden solventarse organizando los routers en regiones o sistemas autónomos

(SA).Todos los routers dentro de un SA ejecutan el mismo algoritmo de encaminamiento intra-

dominio y tienen información unos de otros. Para conectar los SA entre sí, uno o más routers decada

SA, conocidos como routers frontera, tendrán que responsabilizarse del encaminamiento de

paquetes hacia fuera, utilizando un algoritmo de encaminamien- to interdominio.

El problema de escala está resuelto, ya que cada router intra SA sólo necesita conocer los

routers de su SA. El de autoridad administrativa también, porque dentro de cada SA se puede usar

cualquier algoritmo intradominio, siempre que los routers frontera sean capaces de ejecutar

algoritmos interdominio que conecten ese SA con los demás.



La figura muestra una red formada por tres SA. Se destaca la ruta utilizada para encaminar los

datos de H1 a H2, resultado de la combinación de las rutas obtenidas por los algoritmos de

encaminamiento inter e intradominio.

B.a

C.b

a b

SA C

A.a

a

A.c

SA B

c

a

b H2

c

H1 d

b

SA A

Protocolo de encaminamiento Protocolo de encaminamiento inter−SA

intra

−SA

Tabla deencaminamiento

Encaminamiento inter SA en Internet: BGP

BGP (Border Gateway Protocol) es el protocolo de encaminamiento entre sistemas autónomos

actualmente en uso en Internet.

Es un protocolo de vector de rutas, donde routers BGP vecinos intercambian información

sobre rutas (lista de SA en el camino hacia cierto destino e identidad del router BGP de próximo

salto).

Cada SA se identifica por un número (NSA), que es globalmente único y es asignado, como las

direcciones IP, por el ICANN.

A diferencia de los altoritmos de encaminamiento intradominio, en los que se trata de

buscar rutas óptimas en base a algún criterio, aquí se priman priman factores políticos que

pueden invalidar ciertas rutas por restricciones administrativas (se controla el tráfico que dejan



pueden invalidar ciertas rutas por restricciones administrativas (se controla el tráfico que dejan

Encaminamiento mediante difusión o broadcast

En algunas aplicaciones, un nodo necesita enviar simultánea- mente mensajes a todos nodos

de la red. Este procedimiento se denomina difusión (broadcast).

Existen varios métodos:

Un paquete por destino: Supone un elevado gasto de ancho de banda y que sea necesario

conocer la lista de destinos.

Flooding: Da lugar a un elevado gasto de ancho de banda.

Spanning Tree: Basado en la idea de un Sink Tree invertido (el destino en el Sink Tree pasa a ser

la fuente en el Spanning Tree), cada nodo hace flooding del paquete por las líneas del árbol,

generándose así el número mínimo de paquetes necesario para la difusión. El problema

radica en la necesidad de que cada nodo conozca algún Spanning Tree para la fuente.

Reverse Path Forwarding: En este algoritmo, si un paquete llega por la línea usada para

encaminar hacia la fuente del broadcast (la que se utiliza para encaminar paquetes en modo

unicast desde ese nodo hasta la fuente) se hace flooding, y en caso contario se descarta como

posible duplicado. No requiere que lo nodos conozcan árbol alguno. Tampoco se requieren

listas de destinos ni mecanismos para detener la explosión de paquetes. Cada nodo sólo

necesita conocer la mejor línea de salida en modo unicast hasta la fuente.



SpanningTree

A

4 3

B

2 C 1

2 2 D

E F1

3 1

G

Reverse Path Forwarding

A

4 3

B

C2

1

2 2 D

E F 1 3

1 G



Encaminamiento multicast

Ciertas aplicaciones precisan la entrega de paquetes provenientes de uno o más emisores a un

grupo de receptores.

En lugar de un paquete para cada destino, la fuente envía un único paquete a una dirección

multicast, que es conocida por todos los nodos que intervienen en la comunicación (grupo

multicast) y el algoritmo de encaminamiento debe encargarse de que dicho paquete llegue a todos

los miembros del grupo.

G1 G1

7 2

5 G1

8 G1 1

4 FUENTE 6

G2

3 G2

G3

El objetivo del encaminamiento multicast es encontrar un árbol de enlaces entre todos losrouters que disponen de hosts directamente conectados que pertenezcan al grupo multicast.

Se han adoptado dos aproximaciones para determinar los árboles de encaminamiento

multicast, que difieren en virtud de si se utiliza un único árbol compartido para distribuir el

tráfico de todos los emisores del grupo, o si se construye un árbol específico para cada emisor en

particular.



Árbol de grupo compartido

En este caso, todos los paquetes enviados al grupo de multidifusión son encaminados a

través del mismo árbol, independientemente del emisor.

Una aproximación al cálculo de un árbol multicast compartido es la basada

en un nodo central o punto de encuentro. En este caso, se elige en primer lugar el nodo

central, al que deben unirse todos los nodos pertenecientes al grupo, enviando mensajes unicast.

A medida que se envían los mensajes de unión, los caminos que siguen definen las ramas del

árbol entre los routers que se unen y el centro.

Un router que recibe un datagrama para enviar desde uno de sus hosts directamenteenlazados unifunde el datagrama al punto de encuentro, y éste lo multidifunde a través del

árbol de grupo compartido.

Árbol basado en fuente

Se construye un árbol multicast para cada fuente. Cada árbol puede cal- cularse como la

unión de los caminos unicast de menor coste de cada fuente a cada uno de los demás routers con

hosts pertenecientes al grupo. Con este método se necesita que cada router conozca los árboles

para cada fuente, por lo que suele utilizarse el algoritmo de camino inverso en el que cada routersi recibe un paquete por el enlace óptimo hacia la fuente lo transmite por todos sus enlaces de

salida y en otro caso lo descarta.

Para evitar la transmisión hacia routers que no forman parte del grupo, un router que no

tenga hosts adheridos a ese grupo, cuando recibe un paquete para ese grupo envía un mensaje

de poda al router que se lo mandó. Si un router recibe mensajes de poda desde cada uno de sus

routers hacia abajo, envía un mensaje de poda hacia arriba.



Árbol de grupo compartido

A

4 3

B

2

C

1

2 2 D

E F1

3 1

G

centro

Árbol basado en fuente

fuente

A

4 3

B

C2

1

2 2 D

E F 1 3

1 G



Eytan M

Diapositiva 35

Encaminamiento multicast en Internet

DVMRP: Vector de Distancias Multicast

DVMRP implementa árboles basados en la fuente con encaminamiento de camino

inverso y poda. Usa un algoritmo de Vector de Distancias que permite a cada router

calcular el enlace saliente, en su camino de vuelta más corto a cada fuente.

PIM: Protocolo Independiente Multicast

No hace ninguna suposición sobre el protocolo de encaminamiento unicast

subyacente.

Prevé dos escenarios de distribución multicast:

Modo denso: La mayoría de los routers del área están involucrados en el multicast,

porque los miembros del grupo están concentrados.

Modo disperso: Son pocos los routers con miembros directamente en- lazados,

porque los miembros del grupo están dispersos.

Y en función de elloofrece dos modos de operación:

PIM denso: Usa una técnica basada en fuente con encaminamiento de camino

inverso con poda, similar a DVMRP.

PIM disperso: Se basa en un punto de encuentro (centro) al que los routers

envían mensajes de unión.

3.3.4 Gestión de tráfico.

es una actividad de administración de la red telefónica cuyo objetivo es asegurar que el

mayor número posible de llamadas telefónicas son conectadas a su destino.

Principios de gestión de tráfico

Mantener todos los circuitos ocupados con llamadas exitosas.

Utilizar todos los circuitos disponibles.

http://es.wikipedia.org/w/index.php?title=Red_telef%C3%B3nica&action=edit&redlink=1






Eytan M

Diapositiva 36

Dar prioridad a aquellas llamadas que para su conexión requieren el mínimo número de

circuitos o enlaces cuando todos los circuitos disponibles están ocupados.

Inhibir congestión central y evitar que se difunda.

Basado en estos principios, el departamento de gestión de red del operador telefónicodesarrolla planes y estrategias para controlar y manejar el tráfico telefónico.

Principios operacionales

Debe existir un foco de congestión antes de que se considere una acción de control

Resolver problemas locales antes de involucrar áreas distantes

Usar controles expansivos antes de usar controles protectivos

Terminología

Intento: un intento de obtener el servicio de un recurso, por ejemplo, un intento de

llamada sobre un circuito.

Toma: un intento exitoso, esto es, un llamada llevada sobre un circuito.

Desborde: un intento no exitoso de obtener un recurso (circuito) sobre la ruta escogida).

Utilización

Ocupación: medida de la carga llevada por un servidor (circuito), expresada comoporcentaje.

Intensidad de tráfico: medida de la carga llevada por un recurso, expresada en erlangs.

Tiempo: medición de la duración de una toma exitosa.

Tiempo de expiración: medida del retraso en la obtención de un recurso.

Llamadas rechazadas: una toma sobre un circuito entrante que es rechazada por el

procesador central.

Respuesta: señal de retorno indicando que la llamada ha sido contestada.

Ocupado: condición de un recurso que está siendo utilizado en una toma. Se aplica

normalmente en servicio al cliente.

Congestión: estado en el cual el establecimiento de una nueva llamada no es posible

debido a falta de acceso a un recurso.

http://es.wikipedia.org/wiki/Erlang






Eytan M

Diapositiva 37

la gestion de trafico es una accion muy frecuente a as tecnicas de la comunicacion de la

red el los codigos

http://es.wikipedia.org/wiki/Gesti%C3%B3n_de_tr%C3%A1fico

3.3.5 Control de congestión.

Definición de Congestión

Fenómeno producido cuando a la red (o parte de ella) se le ofrece más tráfico del que

puede cursar.

Causa: Las memorias temporales de los nodos se desbordan.

Los paquetes se reciben demasiado deprisa para ser procesados (se llena memoria de

entrada).

Demasiados paquetes en la memoria de salida esperando ser asentidos (se llena memoria

de salida).

Control de flujo vs Control Congestión

Control de congestión: intenta asegurar que la subred sea capaz de transportar el tráfico

ofrecido.

Control de flujo: tráfico punto a punto entre un transmisor y un receptor. Evita que un

transmisor rápido sature a un receptor lento.

El control de flujo es una técnica más de control de congestión.

Técnicas de Control de Congestión

Bucle Abierto: La idea es prevenir e intentar solucionar el problema antes de que se

produzca. Para ello hay que diseñar la red de manera adecuada, actuando sobre

diferentes parámetros a diferentes niveles.

Bucle Cerrado: Son métodos reactivos, es decir, se actúa cuando aparece el problema,

basándose en el presente estado de la red.

Bucle Abierto

Niveles en los que se actúa:






Eytan M

Diapositiva 38

„ Transporte

Š Retransmitir si vencen los temporizadores

Š Descarte de tramas. Desorden en mensajes.

Š Control de flujo (ventanas).

„ Red

Š Descarte de paquetes.

Š C.V. vs Datagramas.

Š Algoritmos de encaminamiento: balanceo de carga entre

líneas.

Š Tiempo de vida de los paquetes.

„ Enlace

Š Parecido a los anteriores, pero entre nodos.

Š Colas de los routers (teoría de colas).

Š Asentimientos: piggybacking

Bucle Cerrado

Suelen hacerse en tres fases:

„ Monitorización: para detectar cuándo y dónde sucede la congestión:

Š Ocupación de enlaces y buffers.

Š Porcentaje de paquetes descartados.

Š Número de retransmisiones.

Š Retardos y jitter.

„ Reacción: enviar información a los puntos en los que se pueda actuar contra la

congestión.

Š Enviar paquetes especiales a las fuentes.

Š Utilizar bits reservados en el campo de control del protocolo.



Eytan M

Diapositiva 39

Š Enviar paquetes solicitando información explícita sobre

congestión.

„ Ajustar la operación del sistema.

Š Reducir velocidad.

Š Prohibir nuevas conexiones.

Š Tirar paquetes.

Otra clasificación puede ser:

„ Contrapresión

„ Paquetes de obstrucción

„ Señalización implícita de congestión

„ Señalización explícita de congestión

Contrapresión

Técnica punto a punto

Se puede propagar hacia atrás

Se puede utilizar a nivel de enlace o de conexiones lógicas:

„ Contrapresión en conexiones lógicas con mucho tráfico, sin afectar a las de menor carga.

Paquetes de obstrucción

Paquete generado por un nodo congestionado hacia un nodo origen. Ejemplo:

„ Paquete Ralentización del Emisor

(“Source Quench”) usado en ICMP.

Posible enviar paquete de obstrucción antes de llegar a la congestión.

Es una técnica ineficiente

Señalización Implícita



Eytan M

Diapositiva 40

El propio emisor detecta la posible congestión:

„ Aumenta el retardo de propagación.

„ Se rechazan paquetes.

Responsabilidad de los sistemas finales y no de los nodos intermedios.

Señalización Explícita

La red alerta a los sistemas finales de la congestión y éstos toman medidas para reducir la

carga.

Sentido de la señalización:

„ Hacia atrás

„ Hacia adelante

Técnicas divididas en tres categorías:

„ Binarias

„ Basadas en crédito

„ Basadas en velocidad

Técnicas de Señalización Explícita

Binarias

„ El nodo congestionado activa un bit en un paquete. El emisor disminuye su flujo de

tráfico por la conexión lógica.

Basadas en crédito

„ Cuando el emisor agota su crédito, debe esperar a que se le conceda más.

Basadas en velocidad



Eytan M

Diapositiva 41

„ El emisor tiene un límite en la velocidad de transmisión por una conexión lógica. Los

nodos intermedios pueden enviar paquetes hacia el emisor para variar dicho límite.

Algoritmos de Control de Congestión

Veremos:

„ Descarte de paquetes (bucle cerrado)

„ Paquetes reguladores (bucle cerrado)

„ Traffic Shapping (bucle abierto)

Cuando un nodo tiene saturados sus recursos (buffers), se tiran paquetes:

„ Datagramas se pierden.

„ C.V. se retransmite.

Problema 1: si el paquete recibido es un ACK y se tira por no tener espacio para guardarlo,

se origina una retransmisión.

„ Solución: reservar posiciones en el buffer para análisis de tráfico. Si es ACK seacepta y si no, se tira.

Problema 2: ¿Cómo se asignan buffers a las lineas de entrada y de salida?

Descarte de paquetes

Problema 2 (continuación) se proponen tres tipos de técnica para realizar esa asignación:

„ Asignación dinámica (en base al uso): No es eficiente, porque si una línea se carga,

acapara todos los recursos (inanición de las otras).

„ Asignación fija: No es eficiente ya que podemos tener líneas con buffers vacíos y

otras saturadas.

„ Subóptima: Mezcla de las anteriores. Se reserva un número fijo de posiciones en el

buffer para cada línea y el sobrante se asigna dinámicamente.



Eytan M

Diapositiva 42

Paquetes reguladores

También conocidos como choke packet. Los nodos monitorizan las líneas de salida,

asociándoles un peso en función del uso:

a,U i ∈ [0,1]

0 no se transmite actualmente

f

1 se está transmitiendon a permite dar mayor o menor importancia a la historia reciente.

Si U > Uumbral la línea se pone en alerta.


Si se tiene que encaminar por una línea en alerta:

„ Se envía al origen un paquete regulador.

„ El paquete se encamina normalmente, activando un bit que informa a los siguientenodos que el origen está avisado.

Recibido el aviso, el origen:

„ Disminuye el tráfico.

„ Pasado un tiempo sin recibir paquetes de regulación, se vuelve a subir la tasa.


Variaciones:

„ Mandar paquetes reguladores con información de estado (grave, muy grave, etc.)

„ Monitorizar también el tamaño de las colas.

„ Pedirle al nodo anterior, que encamine por otro nodo.



Eytan M

Diapositiva 43

Traffic Shapping

Objetivo: adecuar el tráfico de salida de un host con independencia de los patrones de

tráfico generado, evitando ráfagas. Se trata de mantener el

tráfico constante, en definitiva, regular la tasa media de transmisión.

Relación con protocolos de ventana:

„ El protocolo de ventana limita el número de paquetes en tránsito, pero no la

velocidad con la que se ponen en la red.

„ El traffic shapping regula la tasa a la que la información es enviada a la red.

IMPORTANTE: se requiere un acuerdo entre el usuario y el proveedor de red.

„ Si el tráfico inyectado se adecúa al perfil pactado, el proveedor cursa dicho tráfico por la

red. De otra forma, el tráfico se tira.

Ejemplos:

„ Leaky Bucket

„ Token Bucket

Leaky BucketEste mecanismo convierte un flujo desigual de paquetes de un host, en un flujo continuo

de paquetes hacia la red, moderando las ráfagas.

Leaky Bucket+

Ejemplo

„ (a) – Salida del host

„ (b) – Salida del bucket

Implementación:

„ El leaky bucket consiste en una cola finita.

„ Al llegar un paquete, si hay espacio, se almacena. En caso contrario, se descarta.

„ En cada pulso de reloj, se transmite un paquete (si existe)



Eytan M

Diapositiva 44

Usado en redes ATM.

Token Bucket

Leaky Bucket impone un patrón de salida rígido tasa promedio.

En token bucket se permite picos de tráfico durante un pequeño intervalo.

Funcionamiento:

„ La cubeta (bucket) contiene fichas (tokens).

„ Las fichas se insertan en la cubeta cada T seg.

„ Para transmitir, el emisor debe consumir una ficha.

„ Si no existe ficha, se espera.

unidad 3 redes

Documents