Preview only show first 6 pages with water mark for full document please download

Transcript

Redes (IS20) Ingeniería Técnica en Informática de Sistemas http://www.icc.uji.es ÍNDICE CAPÍTULO 5: Subcapa de acceso al medio 1. El problema del reparto del canal 2. Protocolos de contención 3. Protocolos libres de colisiones 1. El problema del reparto del canal Curso 2002-2003 - Redes (IS20) -Capítulo 5 1 1. El problema del reparto del canal Tipos de redes: de difusión y canal punto a punto • Ejemplo de redes de difusión: LAN • Diferentes topologías de LAN: – Bus: estaciones conectadas mediante “taps” a un canal lineal o bus. La transmisión de una estación en ambos sentidos es recibida por las demás estaciones. En los extremos del bus un terminador elimina las señales que le llegan del bus. – Anillo: bucle cerrado de repetidores unidos por enlaces punto a punto. Transmisión bit a bit. Enlace unidimensional (circular). Una estación se conecta a la red mediante un repetidor. Los datos se transmiten en tramas. Las estaciones recogen una copia de la trama que circula. Cuando la trama alcanza la estación que la envío es eliminada de la red ¿Quién gana el acceso al canal compartido en redes de difusión? Protocolo de control de acceso al medio (MAC) Curso 2002-2003 - Redes (IS20) -Capítulo 5 2 1 1. El problema del reparto del canal 1. El problema del reparto del canal ¿Cómo compartir el canal entre usuarios competidores? • Reparto estático del canal – Multiplexación por división de frecuencia (FDM) • • • • Ancho de banda dividido en N bandas privadas: cada usuario usa una Si hay más de N usuarios se le deniega el uso a algunos Si hay menos de N usuarios se desperdicia ancho de banda Los canales pueden estar inactivos la mayor parte del tiempo – Multiplexación por división de tiempo (TDM) • A cada usuario se le asigna un cierto intervalo de tiempo (ranura) • Se mandan ranuras de diferentes usuarios una detrás de otra • Si un usuario no usa su ranura se envía vacía (se desperdicia) – Solución: TDM asíncrona: o de contención de reserva a turnos (libre de colisiones) • Reparto dinámico del canal – Protocolos de acceso múltiple. Veamos unos supuesto previos Curso 2002-2003 - Redes (IS20) -Capítulo 5 3 1. El problema del reparto del canal Reparto dinámico: supuestos • Modelo de estación: N estaciones independientes que generan tramas y se bloquean hasta transmisión trama con éxito • Canal único: Todas las estaciones pueden transmitir y recibir en él • Colisión: La transmisión simultánea de tramas puede llevar a colisiones. Una trama en colisión debe ser retransmitida Las redes puede usar: • Tiempo continuo: la transmisión de una trama puede empezar en cualquier momento, no hay reloj ni división de tiempo • Tiempo ranurado: el tiempo se divide en intervalos discretos (ranuras). La transmisión de tramas comienza al inicio de una ranura. El contenido de una ranura puede ser: tramas, estar inactiva, transmisión con éxito o colisiones • Detección de portadora (LAN): Las estaciones detectan si elcanal está o no en uso. Si está en uso ninguna estación lo usará hasta que este inactivo de nuevo. • Sin detección de portadora (redes satélite): Las estaciones no detectan si el canal está en uso, transmiten siempre y después comprueban si ha habido éxito. Curso 2002-2003 - Redes (IS20) -Capítulo 5 4 2 2. Protocolos de contención 2. Protocolos de contención 2.1. ALOHA puro 2.2. ALOHA ranurado 2.3. Protocolos con detección de portadora (CSMA) 5 Curso 2002-2003 - Redes (IS20) -Capítulo 5 2. Protocolos de contención 2.1. ALOHA puro (1970) • Las estaciones transmiten cuando tengan tramas para enviar • Hay colisiones (total o parcial) y destrucción de tramas • Los usuarios “escuchan” el canal, tras un retardo si no éxito en transmisión se retransmite después de un tiempo arbitrario • Estados de las estaciones 1) Escritura en canal 2) Esperando 3) Verificación transmisión a) si éxito Æ ir 1 b) sino retransmitir Æ ir 2 2.2. ALOHA ranurado (1972) • Duplica la capacidad de ALOHA puro • Se divide el tiempo en ranuras (discretas) • Solo se permite iniciar la transmisión al principio de una ranura Curso 2002-2003 - Redes (IS20) -Capítulo 5 6 3 2. Protocolos de contención 2.2. Protocolos con detección de portadora (CSMA) • Se pretende mejorar el desempleo del canal • Se comprueba primero si el canal está ocupado: – Se espera que se libere o se transmite • Hay diferentes variantes: – CSMA 1-persistente: • Se escucha el canal – si está ocupado: espera que el canal quede libre – si está libre (en reposo): inicia la transmisión de la trama • Si hay colisión la estación espera un tiempo aleatorio y comienza de nuevo • El retardo de propagación puede llevar a colisiones – CSMA No persistente: • Se escucha el canal – Si está ocupado espera un tiempo aleatorio y vuelve a intentarlo – si está libre (en reposo): inicia la transmisión de la trama • Si hay colisión la estación espera un tiempo aleatorio y comienza de nuevo Curso 2002-2003 - Redes (IS20) -Capítulo 5 7 – CSMA p-persistente : para canales ranurados 2. Protocolos de contención • Se escucha el canal y si está en reposo (ranura libre) – las estaciones transmiten con probabilidad p – La estación se espera a la siguiente ranura con probabilidad 1-p • Si en ese tiempo otra estación ha comenzado a transmitir esperará un tiempo aleatorio y comenzará de nuevo • Si canal ocupado espera la siguiente ranura y aplica el algoritmo de nuevo – CSMA/CD con detección de colisiones • • • • • Si medio libre la estación transmite, sino escucha y espera hasta libre. Cesa la transmisión en cuanto se detecta una colisión (señal de alerta) Tras envío de señal de alerta se espera un tiempo aleatorio y nuevo intento Se ahorra tiempo y ancho de banda. Se usa en LAN en subcapa MAC Si t es el tiempo para que una señal se propague entre dos estaciones, si en 2t no se ha detectado es que no hay colisión • Tres estados posibles: contención, transmisión o inactivo Curso 2002-2003 - Redes (IS20) -Capítulo 5 8 4 3. Protocolos libres de colisiones 3. Protocolos libres de colisiones 3.1. Protocolo de mapa de bits 3.2. Protocolo de conteo descendente binario 3.3. Protocolo de recorrido de árbol adaptable 3.4. Protocolo por turnos basado en testigo Curso 2002-2003 - Redes (IS20) -Capítulo 5 9 3. Protocolos libres de colisiones 3. Protocolos libres de colisiones • Los protocolos anteriores dan pie a conflictos ya que las estaciones acceden al canal sin ninguna “contención” • Los siguientes protocolos intenta evitar las colisiones mediante un esquema de reservas o turnos • Para líneas de transmisión largas y tramas cortas el efecto de las colisiones se vuelve cada vez un problema más grave • Examinaremos algunos protocolos que resuelven la contención del canal sin que haya colisiones • Supondremos N estaciones cada una con una dirección única de 0..(N-1) ¿Qué estación toma el canal tras una transmisión exitosa? • Supondremos intervalos de contención discretas Curso 2002-2003 - Redes (IS20) -Capítulo 5 10 5 3. Protocolos libres de colisiones 3.1. Protocolo de Mapa de bits • Cada periodo de contención consta de N ranuras • La transmisión se inician con un periodo de realización de reservas de N ranuras, la estación que quiere transmitir pone un bit 1 durante su ranura de contención • Después se realiza la transmisión de las estaciones en orden • Al acabar las transmisiones reservadas se inicia otro periodo de contención • Se llama protocolo de reserva • Tenemos una información extra de 1 bit por estación Curso 2002-2003 - Redes (IS20) -Capítulo 5 11 3. Protocolos libres de colisiones 3.2. Protocolo de conteo descendente binario • Se usan direcciones binarias (igual longitud) para las estaciones • La competencia por el canal se produce usando las direcciones • Ejemplo: A(1010), B(1101), C(1110), D(0110) – Si una estación quiere usar el canal difunde su dirección como una cadena binaria de bits comenzando por el bit de orden mayor – Se aplica un OR al bit – Regla de arbitraje: se comprueba el bit alto de las estaciones si alguna tiene un 1, se descantan las estaciones que tienen un cero – La estación C transmitirá una trama primero ya que tiene la mayor dirección – Después vuelve a competir por el canal (se produce otro ciclo de concurso por el canal) Curso 2002-2003 - Redes (IS20) -Capítulo 5 12 6 3. Protocolos libres de colisiones Comparación de Protocolos • Los protocolos se evalúan según lo bien que funcionan – Se mide el retardo con baja carga y la eficiencia del canal en carga alta • • • • Carga baja: mejor los de contención ALOHA Carga alta: protocolo libre de colisiones Se pueden combinar ambas: Protocolo de contención limitada La probabilidad de que una estación adquiera el canal aumenta al disminuir el número de estaciones • Los protocolos de contención limitada dividen las estaciones en grupos: – – – – Si una estación por grupo: protocolo de conteo descendente binario Cuantas más estaciones por grupo (ranura) más probabilidad de colisión Si solo un grupo con todas: ALOHA ranurado Queremos asignar estaciones a ranuras de forma dinámica • Muchas estaciones por intervalo si carga baja • Pocas por ranura cuando carga alta Curso 2002-2003 - Redes (IS20) -Capítulo 5 13 3. Protocolos libres de colisiones 3.3. Protocolo de recorrido de árbol adaptable • Se organizan las estaciones como hojas de un árbol • En un momento concreto solo compiten por el canal las estaciones de una rama del árbol • Ejemplo: 8 estaciones intentando transmitir – Después de la transmisión de una trama todas intentan adquirir el canal – Si ninguna adquiere el canal o hay colisión durante la ranura 1 solo las estaciones por debajo del nodo 2 podrán competir – Se busca en la rama izquierda y después en la derecha y si colisión se va bajando – Ej. Quieren transmitir G y H G gana el canal Curso 2002-2003 - Redes (IS20) -Capítulo 5 14 7 3. Protocolos libres de colisiones 3.4. Protocolo por turnos basado en testigo • Circula por la red un testigo (patrón de bits) que habilita al poseedor para transmitir • Si una estación tiene datos que transmitir adquiere el testigo y realiza la transmisión. Al acabar pone de nuevo el testigo en la red • Si una estación no tiene datos pasa el testigo nada más recibirlo • Usado en topologías: token bus (anillo lógico), token ring Curso 2002-2003 - Redes (IS20) -Capítulo 5 15 8