Redes de broadcast

• En una red de broadcast la cuestión principal es como determinar quien usa un canal para el cual existe competencia. Los protocolos para esto pertenecen a un subnivel del nivel de enlace que se llama el subnivel de MAC (Medium Access Control, o control de acceso al medio). Es muy importante en las LANs, que normalmente usan canales de broadcast.
• Se puede asignar un solo canal de broadcast usando un esquema estático o dinámico.
• Asignación estática. Se usa algún tipo de multiplexación (MDF o MDT) para dividir el ancho de banda en $N$ porciones, de que cada usuario tiene uno. Problemas:
  • Si menos de $N$ usuarios quieren usar el canal, se pierde ancho de banda.
  • Si más de $N$ usuarios quieren usar el canal, se niega servicio a algunos, aun cuando hay usuarios que no usan sus anchos de banda alocados.
  • Porque el tráfico en sistemas computaciones ocurre en ráfagas, muchos de los subcanales van a estar desocupados por mucho del tiempo.
• Asignación dinámica. Usa el ancho de banda mejor. Hay muchos protocolos basados en cinco suposiciones principales:
  • Modelo de estación. Hay $N$ estaciones independientes que generan marcos para la transmisión. La probabilidad de generar un marco en el período $delta\; t$ es $lambda\; delta\; t$, donde $lambda$ es un constante. Después de generar un marco una estación hace nada hasta que se transmita el marco con éxito.
  • Canal único. Hay un solo canal disponible para la comunicación. Todos pueden transmitir usándolo y pueden recibir de él.
  • Choques. Si se transmiten dos marcos simultáneamente, se chocan y se pierden ambos. Todas las estaciones pueden detectar los choques.
  • Tiempo continuo o dividido. En el primer caso se puede empezar con la transmisión de un marco en cualquier instante. En el segundo se parte el tiempo con un reloj de maestro que las transmisiones empiezan siempre al inicio de una división.
  • Detección del portador o no. Las estaciones pueden detectar que el canal está en uso antes de tratar de usarlo, o no. En el primer caso ninguna estación trataré transmitir sobre una línea ocupada hasta que sea desocupada. El el último las estaciones transmiten y solamente luego pueden detectar si hubo un choque.

ALOHA

• Desarrollado en los años 70 en Hawaii, ALOHA es un sistema de broadcast que usa el radio. Hay dos versiones, ALOHA puro y ALOHA dividido, que son distintos en el tratamiento del tiempo.
• ALOHA puro. Los usuarios pueden transmitir marcos en cualquier instante. Habrá choques, y los marcos que chocan se destruirán. Empero, un emisor siempre puede detectar un choque escuchando al canal.
  • Con una LAN el feedback es instantáneamente, pero con un satélite hay un retraso de 270 msegs.
  • Si hubo un choque el emisor espera un período aleatorio y manda el marco de nuevo. ¿Por qué aleatorio? Porque si no, los mismos marcos chocarán repetidamente.
  • Este tipo de sistema donde usuarios múltiples comparten un canal en una manera que puede producir conflictos se llama un sistema de contienda.
• En ALOHA puro un traslapo de solamente un bit entre dos marcos es suficiente para destruir ambos. Dado que los usuarios pueden transmitir en cualquier instante, una pregunta interesante es cuál es la utilización máxima del canal.
  • Asume que hay un número infinito de usuarios que pueden transmitir marcos. Todos los marcos tienen el mismo tamaño, y el tiempo para transmitir un marco es $t$.
  • Asume que en un período $t$ el número de intentos de transmisión tiene una distribución Poisson con una media $G$. Nota que las transmisiones pueden ser tanto marcos nuevos como retransmisiones de marcos que chocaron.
  • Si la probabilidad que un marco no choque en un período $t$ es $P$₀, la utilización es $S\; =\; GP$₀. Podemos ver $S$ como el número de marcos nuevos que los usuarios pueden producir por $t$ para un estado en equilibrio.
  • Si queremos transmitir con éxito un marco en tiempo $t$₀+t, necesitamos que no se inicie la transmisión de otro marco entre $t$₀ y $t$₀ + 2t (de otra manera habría un traslapo). Ve el dibujo.

    

  • La probabilidad que se genera 0 marcos en un período $t$ es dada por la distribución Poisson como $e-G$. En un período de $2t$ es $e-Ge-G=\; e-2G$. Esto es $P$₀. Por lo tanto, $S\; =\; Ge-2G$.
  • La utilización máxima ocurre con $G\; =\; 0,5$, con $S\; =\; 1/2e$, o 0,184. Es decir, la utilización máxima del canal es solamente 18% cuando todos pueden transmitir en cualquier instante.
• ALOHA dividido. Este sistema dobla la capacidad de ALOHA puro. Se divide el tiempo en intervalos discretos; cada intervalo corresponde a un marco. Los usuarios están de acuerdo en los límites de los intervalos (por ejemplo, tienen un reloj de maestro). Se pueden transmitir los marcos solamente a los inicios de los intervalos.
  • Para evaluar la utilización de este método, podemos usar el mismo análisis como con ALOHA puro.
  • Ahora para evitar un traslapo solamente necesitamos que no se inicie la transmisión de otro marco en el intervalo de $t$₀+t (es decir, en el mismo intervalo en que transmitimos el marco de interés).
  • Por lo tanto la probabilidad que se genera ningún marco en el período vulnerable es $e-G$. Entonces $S\; =\; Ge-G$. Si $G=1$, $S=0,368$. Entonces 37% de los intervalos están vacíos, 37% tienen un marco, y 27% son choques.
  • Con $G$ mayor tenemos menos intervalos vacíos pero el número de choques crece de manera exponencial.

Protocolos de acceso múltiple con sentido de portador

• La mejor utilización con ALOHA fue solamente $1/e$. Esto quizás no sea sorpresa, cuando consideramos que nadie presta atención a las acciones de otros. En las redes de área local las estaciones pueden detectar que pasa en la media y adaptar su comportamiento de acuerdo con esto. Los protocolos de este tipo se llaman protocolos con sentido de portador.
• CSMA de persistencia 1. CSMA es Carrier Sense Multiple Access, o acceso múltiple con sentido de portador. Cuando una estación tiene datos para mandar, primer examina si alguien está usando el canal. Espera hasta que el canal esté desocupado y entonces transmite un marco. Si hay un choque, espera un período aleatorio y trata otra vez.
  • Persistencia 1 significa que la estación transmite con una probabilidad de 1 cuando encuentra el canal desocupado.
  • El retraso de propagación tiene gran afecto al rendimiento del protocolo. Hay una probabilidad que poco después una estación manda un marco otra estación también trata de mandar un marco. Si la señal de la primera no ha llegado a la segunda, la segunda detectará un canal desocupado, mandará su marco, y producirá un choque. Cuanto más grande el retraso, tanto peor el rendimiento del protocolo.
  • Aunque todavía hay la probabilidad de choques, este protocolo es mejor que ALOHA porque las estaciones no transmiten en la mitad de otra transmisión.
• CSMA sin persistencia. Es menos ávido que el protocolo anterior. Antes de mandar prueba el canal y manda si nadie lo está usando. Si el canal está ocupado, no lo prueba constantemente hasta que esté desocupado, sino espera un período aleatorio y repite el algoritmo. La utilización es mejor pero los retrasos para mandar los marcos son más largos.
• CSMA de persistencia $p$. Es para los canales con tiempo dividido. Si el canal está desocupado, transmite con una probabilidad de $p$. Con una probabilidad de $1-p$ espera hasta el próximo intervalo y repite el proceso. Se repite el proceso hasta que se mande el marco o haya un choque, en cual caso espera un período aleatorio y empieza de nuevo. Si el canal originalmente está ocupado el protocolo espera hasta el próximo intervalo y entonces usa el algoritmo.

  

Protocolos de CSMA con la detección de choques

• Los protocolos de CSMA son un mejoramiento sobre ALOHA porque aseguran que ninguna estación transmite cuando detecta que el canal está ocupado. Un segundo mejoramiento es que las estaciones terminan sus transmisiones tan pronto como detectan un choque. Esto ahorra tiempo y ancho de banda. Los protocolos de esta clase se llaman CSMA/CD (Carrier Sense Multiple Access with Collision Detection, o CSMA con la detección de choques).
• Después de detectar un choque, una estación termina su transmisión, espera un período aleatorio, y trata de nuevo.
• Los choques ocurren en el período de contienda. La duración de este período determina el retraso y la utilización del canal. Para asegurar que tiene control del canal, ¿cuánto tiempo debe esperar una estación? Supongamos que el tiempo para una señal propagar entre las dos estaciones más separadas es $t$.
  • Esperar solamente $t$ no es suficiente. ¿Por qué?
  • Supon que una estación transmite un bit al tiempo $t$₀. Poco antes $t$₀+t, otra estación, que no ha recibido el bit transmitido, manda su bit propio. Inmediatamente detecta que hay un choque, pero la primera estación no detectará el choque hasta $t$₀+2t.
  • En un cable coaxial de 1 km, $t\; =$ 5 microsegundos.

Protocolos libre de choques

• Los períodos de contienda son un problema mayor cuando los cables son largos (retraso de propagación es mayor) y los marcos son cortos (el overhead del los periodos de contienda juega un papel mayor). Esto es el caso en las redes de fibra óptica.
• Podemos eliminar completamente la posibilidad de choques en el período de contienda. En estos protocolos asumimos que las $N$ estaciones tienen direcciones únicas de 0 a $N-1$.
• Protocolo de bit-map. El período de contienda consiste en $N$ intervalos. Si la estación 0 tiene un marco para mandar, transmite un bit de 1 en el intervalo 0. Ninguna otra estación puede transmitir en este intervalo. En general, la estación $j$ transmite un bit de 1 en el intervalo $j$ si tiene un marco para mandar. Después de los $N$ intervalos del período de contienda, todas las estaciones saben cuales quieren transmitir marcos. En este punto transmiten en orden.
  • Porque todas están de acuerdo en el orden de transmisiones, nunca habrá choques.
  • Después de la última transmisión de un marco, un nuevo período de contienda empieza.
  • El overhead es solamente un bit por marco.
• Protocolo de cuenta atrás binaria. Reduce el overhead usando direcciones binarias para las estaciones. El período de contienda ahora tiene solamente $log$₂N intervalos, que es la longitud de la dirección de cada estación (por ejemplo, direcciones son 0000, 0001, etc.). Cada estación que quiere mandar un marco transmite el bit más alta de su dirección en intervalo 0, el próximo en intervalo 1, etc. Se hacen un OR de los bits en el canal. Cuando una estación ve un 1 en un intervalo en que el bit que transmitió fue 0, abandona el intento de transmitir en este turno. Finalmente solamente la estación con la dirección más alta transmite su marco después del período de contienda.
  • Si en el formato de los marcos la dirección del emisor es el primer campo, ¡este protocolo tiene ningún overhead!
  • Para mantener la justicia del algoritmo se cambia la asignación de las direcciones. Después de transmitir se asigna una estación la dirección 0 y aumentan las otras.

IEEE 802.3 y Ethernet

• IEEE 802.3 es un protocolo de CSMA/CD con persistencia de 1 para las LANs.
  • Cuando una estación quiere transmitir, escucha al cable.
  • Si el cable está ocupado, la estación espera hasta que esté desocupado; de otra manera transmite inmediatamente.
  • Si hay un choque, las estaciones involucradas esperan por períodos aleatorios.
• Historia:
  • Después de ALOHA y el desarrollo del sentido de portador, Xerox PARC construyó un sistema de CSMA/CD de 2,94 Mbps para conectar más de 100 estaciones de trabajo en un cable de 1 km. Se llamaba Ethernet (red de éter).
  • Xerox, DEC, y Intel crearon un estándar para un Ethernet de 10 Mbps. Esto fue el baso para 802.3, que describe una familia de protocolos de velocidades de 1 a 10 Mbps sobre algunos medios.
• Cables:
  • 10Base5 (Ethernet gruesa). Usa un cable coaxial grueso y tiene una velocidad de 10 Mbps. Los segmentos pueden ser hasta 500 m en longitud con hasta 100 nodos. Se hacen las conexiones usando derivaciones de vampiro: se inserta un polo hasta la mitad del cable. La derivación es dentro un transceiver, que contiene la electrónica para la detección de portadores y choques. Entre el transceiver y el computador es un cable de hasta 50 m. A veces se pueden conectar más de un computador a un solo transceiver. En el computador hay un controlador que crea marcos, hace checksums, etc.
  • 10Base2 (Ethernet delgada). Usa un cable coaxial delgado y dobla más fácilmente. Se hacen las conexiones usando conectores de T, que son más fáciles para instalar y más confiables. Ethernet delgada es más barata y más fácil instalar pero los segmento pueden ser solamente 200 m con 30 nodos. En 10Base2 el transceiver está en el computador con el controlador.
  • La detección de derivaciones malas, rupturas, y conectores flojos es un gran problema con ambas. Un método que se usa es la medición de la propagación y la reflexión de un pulso en el cable.
  • 10Base-T. Simplifica la ubicación de rupturas. Cada estación tiene una conexión con un hub (centro). Los cables normalmente son los pares trenzados. La desventaja es que los cables tienen un límite de solamente 100 m, y también el costo de un hub puede ser alto.
  • 10Base-F. Usa la fibra óptica. Es cara pero buena para las conexiones entre edificios (los segmentos pueden tener una longitud hasta 2000 m).
  • Para eliminar el problema con las longitudes máximas de los segmentos, se pueden instalar repetidores que reciben, amplifican, y retransmiten las señales en ambas direcciones. La única restricción es que la distancia entre cualquier par de transceivers no puede ser más de 2,5 km y no puede haber más de cuarto repetidores entre transceivers.
• Codificación de Manchester. En 802.3 no hay ningún reloj de maestro. Este produce un problema en la detección de bits distintos (por ejemplo, ¿cómo se detectan dos bits de 0 en vez de tres?). En la codificación de Manchester se usan dos señales para cada bit. Se transmite un bit de 1 estableciendo un voltaje alto en el primer intervalo y un voltaje bajo en el segundo (un bit de 0 es el inverso). Porque cada bit contiene una transición de voltajes la sincronización es sencilla.
• Marcos:

  

  • El preámbulo es 7 bytes de bits que se alternan. La codificación de Manchester de esto produce una onda que el receptor puede usar para sincronizar su reloj con el emisor. Después está el inicio del marco.
  • La dirección de destino puede tener un bit alto de 1, que indica la dirección de un grupo. Todas las estaciones reciben los marcos que tienen este bit encendido, lo que permite el multicast. Una dirección de todos unos es para el broadcast. El próximo bit distingue entre las direcciones locales y las globales, que son únicas en el mundo.
  • La longitud no puede ser 0; un marco debe ser por lo menos 64 bytes. Hay dos razones. Simplifica la distinción entre marcos válidos y basura producida por choques. Más importante permite que el tiempo para mandar un marco es suficiente para detectar un choque con la estación más lejana. Para una LAN de 10 Mbps con una longitud máxima de 2500 metros y cuatro repetidores, el marco mínimo debe tomar 51,2 microsegs, que corresponde a 64 bytes. Se rellena si no hay suficientes datos. Nota que con redes más rápidas se necesitan marcos más largo o longitudes máximas más cortas.
  • El checksum es CRC.
•   Algoritmo de retiro de manera exponencial binaria. Después de un choque se divide el tiempo en intervalos de $2t$, que es 51,2 microsegs. Después del choque $i$ cada estación elige un número aleatorio entre 0 y $2i-1$ (pero con un máximo de 1023) y espera por un período de este número de intervalos. Después de 16 choques el controlador falla. Este algoritmo adapta automáticamente al número de estaciones que están tratando de mandar.
• Con más y más estaciones y tráfico en una LAN de 802.3, se satura la LAN. Una posibilidad para aumentar el rendimiento del sistema sin usar una velocidad más alta es una LAN 802.3 conmutada.
  • El conmutador consiste en un backplane en que se insertan 4 a 32 tarjetas que tienen uno a ocho puertas de (por lo general) 10BaseT.
  • Cuando un marco llega en la tarjeta, o se reenvía a una estación conectada a la misma tarjeta o se reenvía a otra tarjeta.
  • En un diseño cada tarjeta forma su propio dominio de choques. Es decir, cada tarjeta es un LAN, y todas las tarjetas pueden transmitir paralelamente.
  • Otro diseño es que cada puerta forma su propio dominio de choques. La tarjeta guarda los marcos que llegan en RAM y los choques son raros. Este método puede aumentar el rendimiento de la red un orden de magnitud.
  • Se pueden conectar un hub a una puerta también.
• Además de 802.3, existen 802.4 (bus de token) y 802.5 (anillo de token). La idea es que las estaciones alternan en el uso del medio (intercambiando un token, que representa el turno). La ventaja es que el tiempo máximo de espera para mandar un marco tiene un límite. En el bus de token se usa un medio de broadcast, mientras que en el anillo de token se usan enlaces de punto-a-punto entre las estaciones.

Bridges

• Los bridges (puentes) son dispositivos que conectan las LANs. Razones para tener LANs múltiples:
  • Dueños autónomos (por ejemplos, departamentos distintos en una empresa)
  • Distancia entre grupos
  • Carga
  • Distancia entre computadores que debieran estar en la misma LAN
  • Confiabilidad: por contraste con un repetidor, un bridge puede rechazar basura de un nodo defectivo
  • Seguridad (restringir la propagación de marcos confidenciales)
• Se necesitan bridges distintos para conectar cada combinación de 802.x y 802.y. Los protocolos tienen formatos de marco distintos, velocidades distintas, y longitudes máximas de marco distintas.
• Bridge transparente. Este tipo de bridge no requiere ningún cambia a hardware o software. Hay que conectarlo y no más.
  • El bridge opera en un modo donde acepta todos los paquetes de la LAN (modo promiscuo). Con cada marco el bridge tiene que decidir si reenviarlo o descartarlo. Busca la dirección del destino en una tabla de hash dentro del bridge para determinar la línea de salida.
  • Al principio las tablas de todos los bridges son vacías. Porque no saben dónde están los destinos, los bridges reenvían marcos a todas las LANs.
  • Para llenar las tablas se usan un algoritmo de aprender atrás. Porque los bridges aceptan todos los marcos transmitidos en sus LANs, pueden notar las direcciones de fuente en los marcos. Con estas pueden guardar las LANs de las cuales los marcos originan. Entonces un bridge puede determinar a través de qué LAN se puede alcanzar una estación.
  • Porque la topología de las LANs puede cambiar, se expiran las entradas en las tablas después de algunos minutos. Si una máquina no transmite nada por algunos minutos, para mandar un paquete a él se deben inundar la red.
  • Para aumentar la confiabilidad del sistema a veces se usan más de un bridge para conectar dos LANs, que puede producir problemas con la inundación de marcos (ciclos son posibles).
  • La solución de este problema es que los bridges se comunican para construir un árbol. Los bridges hacen broadcasts de sus números de serie para elegir la raíz, y entonces pueden construir el árbol.
•   Bridge de ruteo de fuente. La desventaja con los bridges transparentes es que malgastan ancho de banda (usan solamente un subconjunto de la topología, el árbol). Con el ruteo de fuente, cada fuente sabe el camino óptimo a cada destino posible.
  • Para encontrar las rutas las estaciones mandan un marco descubridor que es reenviado por cada bridge. Las respuestas incluyen el camino tomado por el marco.
  • Un problema es que este método puede producir una explosión en el número de marcos descubridores.

LANs de velocidad alta

• FDDI (Fiber Distributed Data Interface). Es una LAN de anillo de token que corre con una velocidad de 100 Mbps sobre distancias hasta 200 km con hasta 1000 estaciones conectadas. Se lo puede usar como un LAN normal pero el uso más común es para conectar LANs de cobre.
  • Consiste en dos anillos que transmiten en sentidos contrarios. Si hay una ruptura (por ejemplo, debido a un fuego) se pueden conectar los dos anillos en uno.
  • En vez de la codificación de Manchester usa un esquema que se llama 4 de 5: se usan cinco bits para codificar cada cuatro. Dieciséis combinaciones son datos y otras son para control. Para sincronizar se usa un preámbulo largo y se requiere que los relojes son estables dentro de 0,005%.
  • Debido a la longitud potencial del anillo una estación puede generar un nuevo marco inmediatamente después de transmitir un marco, en vez de esperar su vuelta (como en 802.5). Pueden estar algunos marcos en el anillo a la vez.
  • FDDI también tiene un modo síncrono donde cada marco contiene cuatro canales de T1; puede haber hasta 16 marcos síncronos cada 125 microsegundos.
• Fast Ethernet (Ethernet rápida). Ya que FDDI no tenía éxito en el mercado de LANs (sino en el mercado de backbones), se desarrolló 802.3u, o Fast Ethernet. La idea es preservar los formatos de paquetes, las interfaces, etc., pero reducir el tiempo por bit de 100 nsegs a 10 nsegs (es decir, 100 Mbps).
  • Se usan solamente los cables de 10Base-T porque tienen muchas ventajas. El problema es que el par trenzado de clase 3 (el más común) no puede portar señales de 200 megabaud (100 Mbps con la codificación de Manchester) sobre 100 metros.
  • La solución para clase 3 es usar cuatro pares trenzados que tienen una señalización de 25 MHz, solamente 25% más rápida que con 802.3. De los cuatro, uno es siempre al hub, uno es siempre desde el hub, y los dos otros son conmutables. Se eliminan la codificación de Manchester (no es necesario en este caso con los relojes de hoy y distancias menos de 100 metros) y se usa la señalización ternaria. Entonces con tres pares se pueden transmitir 27 símbolos, o 4 bits a la vez.
  • Con la clase 5 el sistema es más sencillo porque el cable puede manejar 100 Mbps. Es full dúplex y compatible con FDDI. Hay también un estándar para fibra óptica que permite distancias hasta 2 km entre la estación y el hub.
  • Los hubs normalmente apoyan ambos 10 Mbps y 100 Mbps, que permite las instalaciones mezcladas.
• HPPI (High-Performance Parallel Interface). Fue desarrollado por Los Alamos para conectar los supercomputadores. Principios de diseño: chips estándares, ninguna opción, y rendimiento.
  • Tiene velocidades de 800 Mbps y 1600 Mbps. El primer es suficiente para 30 marcos por segundo de $1024\times 1024$ pixels de 24 bits cada uno. Usa un conmutador de crossbar.
  • El cable contiene 50 pares trenzados (32 de datos, otros de control), es simplex, y tiene una longitud máxima de 25 metros. Se transfiere una palabra cada 40 nsegs. Se usan dos cables para la velocidad más alta.
  • Los marcos tienen 256 palabras. Se limita la detección de errores a un bit de paridad por palabra y una palabra de paridad por marco; otros checksums eran demasiado lentos.
• Fibre channel. La idea fue reemplazar los pares trenzados de HPPI con una sola fibra. Por desgracia es mucho más complicado, y por lo tanto más caro y difícil de implementar. Apoya velocidades de 100, 200, 400, y 800 Mbps.