C A P I T U L O  3

 

 

                                     INTRODUCCION

 

 

   En estebcapítulo estudiaremos el diseño de la capa 2, la capa de enlace de datos. Este estudio tiene que ver con los algoritmos para lograr una comunicación confiable y eficiente entre dos máquinas adyacentes en la capa de enlace de datos. Por adyacentes, queremos decir que las dos máquinas están conectadas físicamente por un canal de comunicaciones; la propiedad esencial de un canal que lo hace asemejarse a un alambre es que los bits se entregan con exactitud en el mismo orden en que fueron enviados.

   Desafortunadamente, los circuitos de comunicación cometen errores ocasionales. Además, tienen una tasa de datos finita y hay un retardo de propagación diferente de cero entre el momento en que se envía un bit y el momento en que se recibe. Estas limitaciones tienen implicaciones importantes para la eficiencia de la tranferencia de datos. Los protocolos usados para comunicaciones deben considerar todos estos factores.

 

 

 

 

3.1 CUESTIONES DE DISEÑO DE LA CAPA DE ENLACE DE DATOS

 

 

   La capa de enlace de datos tiene que desempeñar varias funciones específicas que incluyen proporcionar una interfaz de servicio bien definida con la capa de red, determinar la manera en que los bits de la capa física se agrupan en marcos, manejar los errores de tranmisión y regular el flujo de marcos para que los receptores lentos no sean abrumados por los transmisores rápidos.

 

 

3.1.1 SERVICIOS PROPORCIONADOS A LA CAPA DE RED

 

 

La función de la capa de enlace de datos es suministrar servicios a la capa de red. El servicio principal es la transferencia de datos de la capa de red en la máquina de origen a la capa de red en la máquina de destino. El trabajo de la capa de enlace de datos es transmitir los bits a la máquina de destino, para que puedan ser entregados a su capa de red, como se muestra en la figura 3-1(a). La  transmisión real sigue la trayectoria de la fig. 3-1(b), pero es más fácil pensar en términos de dos procesos de capa de enlace de datos que se comunican usando un protocolo de enlace de datos.

 

 

   Los servicios reales ofrecidos pueden variar de sistema en sistema. Tres posibilidades razonables que normalmente se proporcionan son:

 

·        Servicio sin acuse sin conexión.

·        Servicio con acuse sin conexión.

·        Servicio con acuse orientado a la conexión.

 

 

   El servicio sin acuse sin conexión consiste en hacer que la máquina de origen envíe marcos independientes a la máquina de destino sin pedir que ésta los reconozca o acuse su recibo. Si se pierde un marco debido a ruido en la línea, no se intenta recuperarlo en la capa de enlace de datos. Esta clase de servicio es apropiada cuando la tasa de errores es muy baja, por lo que la recuperación se deja a las capas más altas.

   El siguiente paso hacia arriba en cuanto a confiabilidad es el servicio con acuse sin conexión. Cuando se ofrece este servicio, aún no se usan conexiones, pero cada marco enviado es reconocido. Cuando se ofrece este servicio, aún no se usan conexiones, pero cada marco enviado es reconocido individualmente. De esta manea, el transmisor sabe si el marco ha llegado bien o no. Este servicio es útil en canales inestables, como los de los sistemas inalámbricos.

   El servicio más elaborado que puede proporcionar la capa de enlace de datos a la capa de red es el servicio orientado a la conexión. Con este servicio, las máquinas de origen y de destino establecen una conexión antes de transferir datos. Cada marco enviado a través de la conexión está numerado, y la capa de enlace de datos garantiza que cada marco enviado llegará a su destino. Se garantiza que cada marco será recibido exactamente una vez y que todos los marcos sean recibidos en el orden adecuado.

 

 

   Al usarse un servicio orientado a conexión, las transferencias tienen tres fases distintas. En la primera fase, la conexión se establece haciendo que ambos lados inicialicen las variables y contadores necesarios para seguir la pista de los marcos que han sido recibidos y los que no. En la segunda fase se transmiten uno o más marcos. En la tercera fase, la final, la conexión se cierra, liberando las variables, los buffers y otros recursos utilizados para mantener la conexión.

 

 

 

 

 

3.1.2  ENMARCADO

 

   El enfoque común es que la capa de enlace de datos divida el flujo de bits en marcos discretos y que calcule la suma de comprobación para cada marco. Cuando un marco llega al destino, se recalcula la suma de comprobación. Si la nueva suma de comprobación calculada es distinta de la contenida en el marco, la capa de enlace de datos sabe que ha ocurrido un error y toma medidas para manejarlo.

   La división en marcos del flujo de bits es más dificil de lo que parece a primera vista. Una manera de lograr esta división en marcos es introducir intervalos de tiempo entre los marcos, a semejanza de los espacios entre las palabras en el texto común. Sin embargo, las redes pocas veces ofrecen garantías sobre la temporización, por lo que es posible que estos intervalos sean eliminados o que puedan introducirse otros intervalos durante la transmisión.

  Dado que es demasiado riesgoso depender de la temporización para marcar el inicio y el final de cada marco, se han diseñado algunos métodos de enmarcado, acontinuación se mensionan cuatro:

 

1.- Conteo de caracteres.

2.- Caracteres de inicio y fin, con relleno de caracteres.

3.- Indicadores de inicio y fin, con relleno de bits.

4.- Violaciones de codificación de la capa fisica.

 

 

   El primer método enmarcado se vale de un campo del encabezado para especificar el número de caracteres en el marco. Cuando la capa de enlace de datos del destino ve la cuenta de caracteres, sabe cuántos caracteres siguen, y por tanto dónde está el fin del marco. Esta técnica se muestra en la figura 3-3(a) para cuatro marcos de 5, 5, 8 y 8 caracteres de longitud respectivamente. El problema con este algoritmo es que la cuenta puede alterarse por un error de transmisión, por esta razón, el método de conteo de caracteres ya casi no se usa en la actualidad.

 

   El segundo método de enmarcado supera el problema de resincronización tras un error al hacer que cada marco comience con la secuencia de caracteres ASCII DLE STX y termine con la secuencia DLE ETX. De esta manera, si el destino llega a perder la pista de los límites del marco, todo lo que tiene que hacer es buscar los caracteres DLE STX o DLE ETX para determinarlos. Hay un problema importante con este método cuando se transmiten datos binarios, como programas objeto o números de punto flotante. Una desventaja importante del uso de esta técnica de enmarcado es que está fuertemente atada a los caracteres de 8 bits en general y al código ASCII en particular. Por lo que tuvo que desarrollarse una técnica nueva que permitiera caracteres de tamaño arbitrario.

 

 

 

 

 

 

   La nueva técnica permite que los marcos de datos contengan un número arbitrario de bits y admite códigos de caracteres con un número arbitrario de bits por carácter. La técnica funciona de la siguiente manera. Cada marco comienza y termina con un patrón especial de bits, 01111110 llamado byte indicador. Cada vez que la capa de enlace de datos del transistor encuentra cinco unos consecutivos en los datos, automaticamente inserta un bit cero en la cadena de bits. Con el relleno de bits, el límite entre los dos marcos puede ser reconocido sin ambiguedades mediante el patrón indicador. Si el receptor pierde la pista de dónde está, todo lo que tiene que hacer es explorar la entrada en busca de secuencias indicadoras, pues sólo pueden ocurrir en los límites de los marcos y nunca en los datos.

   El último método enmarcado sólo se aplica a las redes en las que la codificación en el medio físico contiene cierta redundancia. Por ejemplo, algunas LAN codifican un bit de datos usando 2 bits físicos.

 

 

 

 

 

3.1.3  CONTROL  DE  ERRORES

 

   Habiendo resuelto el problema de marcar el inicio y el final de cada marco, llegamos al siguiente problema: cómo asegurar que todos los marcos sean entregados finalmente a la capa de red en el destino, en el orden apropiado.

   La manera normal de asegurar la entrega confiable de datos es proporcionar al transmisor realimentación sobre lo que está ocurriendo en el otro lado de la línea. Si el transmisor recibe un acuse positivo de un marco, sabe que el marco llegó correctamente. Por otra parte, un acuse negativo significa que algo falló y el marco debe transmitirse otra vez.

   Una complilación adicional surge de la posibilidad de que problemas de hardware pueden causar la desaparición de un marco completo (por ejemplo, por una ráfaga de ruido). En este caso, el receptor no reaccionará en absoluto, ya que no tiene razón para reaccionar. Esta posibilidad se maneja introduciendo temporizadores en la capa de enlace de datos. Cuando el transmisor envía un marco, generalmente también arranca un temporizador.

   Sin embargo, si el marco o el acuse se pierden , el temporizadorterminará, alertando al transmisor sobre un problema potencial. La solución obvia es simplemente transmitir de nuevo el marco. Sin embargo, aun cuando los marcos pueden transmitirse muchas veces, hay el peligro de que el receptor acepte el mismo marco dos o más veces. Para evitar que ocurra esto, generalmente es necesario asignar números de secuencia a los marcos de salida.

 

 

 

 

 

 

3.1.4 CONTROL  DE  FLUJO

 

 

   Esta situación puede ocurrir fácilmente cuando el transmisor opera en una computadora rápida y el receptor opera en una máquina lenta. El transmisor envía los marcos a alta velocidad hasta que satura por completo al receptor. Aun si la transmisión está libre de errores, en cierto punto el receptor simplemente no será capaz de manejar los marcos según van llegando y comenzará a perder algunos.

   La solución común es introducir un control de flujo para controlar la velocidad del transmisor de modo que no envíe a mayor velocidad que la que puede manejar el receptor. Este control de velocidad generalmente requiere algún mecanismo de retroalimentación, para que el transmisor pueda enterarse si el receptor es capaz de mantener el ritmo o no.

 

 

 

 

3.2DETECCION  Y  CORRECCION  DE  ERRORES

 

 

   Aunque los errores son raros en la parte digital, aún son comunes en los lazos locales. Es más, la comunicación inalámbrica se está volviendo más común, y las tasas de errores aquí son de magnitud mucho mayor que en las líneas de interconexión de fibra entre oficinas. La conclusión es: los errores de transmisión van a ser inevitables durante muchos años más. Los errores tienden a aparecer de dos formas: en ráfagas e individualmente. El que los errores lleguén en ráfaga tiene tanto ventajas como desventajas respecto a los errores aislados de un solo bit. La desventaja de los errores en ráfaga es que son mucho más difíciles de detectar y corregir que los errores aislados.

 

 

 

 

3.2.1  CODIGOS  DE  CORRECCION  DE  ERRORES

 

 

   Los diseñadores de redes han desarrollado dos estrategias básicas para manejar los errores. Una es incluir suficiente información redundante en cada bloque de datos transmitido. La otra estrategia es incluir sólo suficiente redundancia para que el receptor sepa que ha ocurrido un error. La primera estrategia utiliza códigos de corrección de errores; la segunda usa códigos de detección de errores.

   Dadas dos palabras código cualesquiera, digamos 10001001 y 10110001, es posible determinar cuántos bits correspondientes difieren. En este caso difieren tres bits. Para determinar la cantidad de bits diferentes basta aplicar una operación OR exclusivo a las dos palabras código y contar la cantidad de bits 1 en el resultado. La cantidad de posiciones de bit en la que difieren dos palabras código se llama distancia de Hamming. Su significado es que, si dos palabras código están separadas una distancia de Hamming d, se requerirán d errores de un bit para convertir una en la otra. Las propiedades de detección y corrección de errores de un código dependen de su distancia de Hamming. Cuando el receptor ve una palabra código no válida, sabe que ha ocurrido un error de transmisión.

   Los códigos de Hamming sólo pueden corregir errores individuales. Sin embargo, hay un truco que puede servir para que los códigos de Hamming corrijan errores en ráfaga. Se dispone como matriz una secuencia de k palabras código consecutivas, con una palabra código por fila. Para corregir los errores en ráfaga, los datos deben transmitirse una columna a la vez, comenzando por la columna de la extrema izquierda.

 

 

3.2.2  CODIGOS  DE  DETECCION  DE  ERRORES

 

 

   Los códigos de corrección de errores a veces se utilizan para la transmisión de datos; por ejemplo, cuando el canal es símplex, por lo que no pueden solicitarse retransmisiones. Sin embargo con mayor frecuencia se prefiere la detección de errores seguida de la retransmisión porque es más eficiente.

   Si se agrega un solo bit de paridad a un bloque y el bloque viene muy alterado por una ráfaga de errores prolongada, la probabilidad de que se detecte el error es de .5, lo que difícilmente es aceptble. Puede mejorarse mucho la probabilidad considerando a cada bloque por enviar como una matriz rectangular de n bits de ancho y k bits de alto. Se calcula por separado un bit de paridad para cada columna y se agrega a la matriz como última fila. La matriz se transmite entonces fila por fila. Al llegar el bloque, el receptor comprueba todos los bits de paridad. Si cualquiera de ellos está mal, solicita la retransmisión del bloque.

   Aunque el esquema anterior puede seer adecuado en algunos casos, en la práctica se usa otro método muy difundido: el código polinómico(también conocido como código de redundancia cíclica o código CRC). Los códigos polinómicos se basan en el tratamiento de cadenas de bits como representaciones de polinomios con coeficientes de 0 y 1 solamente. Un marco de k bits se considera como la lista de coeficientes de un polinomio con k que van de xk-1 a x0.

   Cuando se emplea el método de código polinómico, el transmisor y el receptor deben acordar un polinomio generador, G(x), por adelantado. Tanto los bits mayor como menor del generador deben ser 1. Para calcular la suma de comprobación para un marco con m bits, correspondiente al polinomio M(x), el marco debe ser más largo que el polinomio generador.

   Por último, y lo que es más importante, un código polinómico con r bits de comprobación detectará todos los errores en ráfaga de longitud menor igual a r. un error en ráfaga de longitud k puede representarse mediante xI(xk-1+…….+1), donde i determina la distancia a la que se encuentra la ráfaga desde el extremo derecho del marco recibido. También puede demostrarse que, cuando ocurre una ráfaga de errores mayor que r+1, o cuando ocurren varias ráfagas más cortas, la probabilidad de que un marco incorrecto no sea detectado es de 1/2 a la r, suponiendo que todos los patrones de bits sean igualmente probables.

 

Tres polinomios se han vuelto estándares internacionales:

 

*CRC-12                      = X12 + X11 + X3 + X2 + X1 + 1

 

*CRC-16                      = X16 + X15 + X2 + 1

 

*CRC-CCITT               = X16 + X12 + X5 + 1

 

   Los tres contienen x +1 como factor primo. CRC-12 se usa cuando la longitud de un carácter es de 6 bits. Los otros dos se usan con caracteres de 8 bits. Durante décadas se ha supuesto que los marcos para los que se generan sumas de comprobación contienen bits aleatorios. Todos los análisis de algoritmos de suma de comprobación se han hecho bajo este supuesto. En fechas más recientes, la inspección de datos reales ha mostrado que este supuesto es equivocado. Como consecuencia, en algunas ciscunstancias los errores no detectados son mucho más comunes de lo que se pensaba anteriormente.

 

 

 

 

3.3PROTOCOLOS  ELEMENTALES  DE  ENLACE  DE  DATOS

 

 

 

   Para comenzar, estamos suponiendo que en las capas física, de enlace de datos y de red hay procesos independientes que se comunican pasdando mensajes de un lado a otro. En algunos casos, los procesos de la capa física y de la de enlace de datos se ejecutan en un procesador dentro de un chip especial de E/S y los de la capa de red lo hacen en la CPU principal, pero también puede haber otras implementaciones.

   En lo qe concierne a la capa de enlace de datos, el paquete pasado a ella a través de la interfaz desde la capa de red es de puros datos, qe deben seer entregados bit por bit a la capa de red del destino. El hecho de que la capa de red del destino pueda interpretar parte del paquete como un encabezado no es de importancia para la capa de enlace de datos. Cuando la capa de enlace de datos acepta un paquete, lo encapsula en un marco agregando un encabazado y una cola de enlace de datos. Por tanto, un marco consiste en un paquete incorporado más cierta información de control. Luego el marco se transmite a la otra capa de enlace de datos. Supondremos que existen procedimientos de biblioteca to_physical_layer (a la capa física) para enviar un marco y from_physical_layer (de la capa física) para recibir un marco. El hardware transmisor calcula y agrega la suma de comprobación, por lo que el software de la capa de enlace de datos no necesita preocuparse por ella.

 

 

 

 

 

 

   La capa de enlace de datos no se quedará en un ciclo cerrado esperando un evento, como hemos sugerido, sino que recibirá una interrupción, la que hará que suspenda lo que estaba haciendo y proceda a manejar el marco entrante. Cuando llega un marco al receptor, el hardware calcula la suma de comprobación. Si la suma de comprobación es incorrecta (es decir, si hubo un error de transmisión), la capa de enlace de datos es informada (event=cksum_err). Si el marco entrante llega sin daño, la capa de enlace de datos también es informada (event=frame_arrival) para que pueda adquirir el marco e inspeccionarlo usando from_physical_layer. Tan pronto como la capa de enlace de datos receptora adquiere un marco sin daños, revisa la información de control del encabezado y, si todo está bien, pasa la parte que corresponde al paquete a la capa de red. En ninguna circunstancia se entrega un encabzado de marco a la capa de red.

   Hay una buena razón por la que la capa de red nunca debe recibir ninguna parte de el encabezado del marco: mantener completamente separados el protocolo de red y el de enlace de datos.

 

   Se definen 5 estructuras de datos: Boolean, Seq_nr, Packet, Frame_kind, Frame. Un Boolean (Boleano) es un tipo enumerado que puede tener los valores true y false. Un Seq_nr (numero de secuencia) es un entero pequeño que sirve para enumerar los marcos, a fin de distinguirlos. Estos numeros de secuencia van de cero hasta Max_Seq (inclusive), que se define en cada protocolo que lo necesita. Un Packet es la unidad de información intercambiada entre la capa de red y la de enlace de datos en la misma maquina, o entre capas de red pares. En nuestro modelo siempre contiene Max_pkt bytes, pero en la pratica seria de longuitud variable.

 

Un Frame (marco) esta compuesto de 4 campos: Kind, Seq, Ack e Info. Los primeros 3 contienen informacion de control y el ultimo puede contener los datos por tranferir. Estos campos de control constituyen en conjunto el ancabezado del marco. El campo Kind indica si hay datos en el marco. Los campos Seq y Ack se emplean para numeros de secuencia y acuses de recivo respectivamente. El campo info de un marco de datos contiene un solo paquete; el campo info de un marco de control no se usa.

 

En la mayoria de los protocolos suponemos un canal inestable que pierde marcos completos ocasionalmente. Para poder recuperarse de tales calamidades, la capa de enlace de datos transmisora debe arrancar un temporizador o reloj interno cada ves que envia un marco. Si no obtiene respuesta tras transcurrir cierto intervalo de tiempo predeterminado, el temporizador termina y la capa de enlace de datos recive una señal de interrupcion.

 

Los procedimientos Start_timer y Stop_timer sirven para arrancar y parar respectivamente el temporizador. Las terminaciones por temporizador solo son posibles cuendo el temporizador esta funcionando.

 

 

 

 

 

3.3.1  UN  PROTOCOLO  SIMPLEX  SIN  RESTRICCIONES

 

 

   Los datos se transmiten sólo en una dirección; las capas de red tanto del transmisor como del receptor siempre están listas, el tiempo de procesamiento puede ignorarse, hay un espacio infinito de buffer y, lo mejor de todo, el canal de comunicación entre las capas de enlace de datos nunca tiene problemas ni pierde marcos. Este protocolo completamente irreal, al que apodaremos "utopía".

   El protocolo consiste en dos procedimientos diferentes, uno transmisor y uno receptor. El transmisor se ejecuta en la capa de enlace de datos de la máquina de origen y el receptor se ejecuta en la capa de enlace de datos de la maquina de destino. El transmisor está en un ciclo while infinito que sólo envía datos a la línea tan rápidamente como puede. El cuerpo del ciclo consiste en tres acciones: obtener un paquete de la capa de red, construir un marco de salida usando la variable s y enviar el marco a su destino. El receptor es igualmente sencillo. De inicio, espera que algo ocurra, siendo la única posibilidad la llegada de un marco sin daños. Por último, la parte de datos se pasa a la capa de red y la capa de enlace de datos se retira para esperar el siguiente marco.

 

 

 

 

 

3.3.2  PROTOCOLO  SIMPLEX  DE  PARADA  Y  ESPERA

 

 

 

   El problema principal que debemos resolver aquí es cómo evitar que el transmisor sature al receptor enviando datos a mayor velocidad de la que este último puede procesarlos. En esencia, si el receptor requiere un tiempo delta t para ejecutar from_physical_layer más to_network_layer, el transmisor debe transmitir a una tasa media menor que un marco por tiempo delta t.

   En ciertas circunstancias restringidas, el transmisor podría introducir simplemente un retardo en el protocolo 1 y así reducir su velocidad lo suficiente para vitar que se sature el receptor. Sin embargo, es más común que la capa de enlace de datos tenga varias líneas a las cuales atender, y el intervalo de tiempo entre la llegada de un marco y su procesamiento puede variar considerablemente. El problema con este enfoque es que es demasiado conservativo. Conduce a un aprovechamiento del ancho de banda muy por debajo del óptimo.

   Una solución más general para este dilema es hacer que el receptor proporcione realimentación al transmisor. Tras haber pasado un paquete a su capa de red, el receptor envía un pequeño marco ficticio de regreso al transmisor que, de hecho, autoriza al transmisor para transmitir el siguiente marco. Los protocolos en los que el transmisor envía un marco y luego espera un acuse antes de continuar se denominan de parada y espera.

 

 

   Ya que sólo es importante la llegada del marco en el transmisor, no su contenido, el receptor no necesita poner ninguna información específica en él. Aunque el tráfico de datos en este ejemplo es símplex, yendo sólo del transmisor al receptor, los marcos sí viajan en ambos sentidos. En consecuencia, el canal de comunicación entre las dos capas de enlace de datos necesita ser capaz de transferencia bidireccional de información.

 

 

 

 

 

 

3.3.3  PROTOCOLO  SIMPLEX  PARA  UN  CANAL  RUIDOSO

 

 

   Consideremos ahora la situación normal de un canal de comunicación que comete errores. Los marcos pueden llegar dañados o perderse por completo.

 

REDES  DE COMPUTADORAS

 

ESPECIFICACION Y VERIFICACION DE PROTOCOLOS.

 

        Los protocolos realistas, y los programas que los implementan, con frecuencia son complicados. En consecuencia, se requiere mucha investigacion para encontrar tecnicas matematicas formales con las cuales especificar y verificar los protocolos. En las secciones siguientes veremos algunos mmodelos y tecnicas. Aunque estamos estudiandolos en el contexto de la capa de enlace de datos, tambien son aplicables a otras capas.

 

        MODELOS DE MAQUINA DE ESTADO FINITO.

 

        Con esta tecnica, cada maquina de protocolo (es decir, transmisor receptor) siempre esta en un estado especifico en cualquier instante. Su estado consiste en todos los valores de sus variables, incluido el contador de programa.

 

        Tipaicamente, los estados se escogen como aquellos instantes en que la maquina de protocolo esta esperando que ocurra el siguiente evento. En este punto el estado de la maquina de protocolo esta determinado por completo por los estados de las variables, el numero de estados es entonces 2 a la N donde N es el numero de bits necesarios para representar todas las variables combinadas.

        El sistema completo es la combinacion de todos los estados de las dos maquinas protocolo y del canal. El estado del canal tiene cuatro posibles estados: un marco 0 o un marco 1 vajando del transmisor al receptor un marco de acuse que va en el otro sentido o un canal vacio. Si  modelamos el trqansmisor y el receptor como si ambos tuvieran 2 estados, el sistema completo tiene 16 estados diferentes.

 

        Las transiciones ocurren cuando sucede algun evento. Para una maquina de protocolopodria ocurrir una transicion al enviar un marco, al terminar un temporizador, al ocurrir un temporizador etc.

        A un estado en particular se le designa estado inicial. Este estado corresponde a la descripcion del sistema cuando comienza a funcionar, desde el estado inicial pueden alcanzarse algunos o quiza todos los demas estados mediante una secuencia de trancisiones.

 

        El analisis de asequiibilidad puede servir para detectar una variedad de errores en la especificacion  del protocolo.Por ejemplo, si es posible que ocurra cierto marco en cierto estado y la ma2uina de estado finito no indica la accion a tomar, la especificacion esta en error (incompleta).

 

        Una de las propiedades que debe tener un protocolo con un numero de secuencia de un bit es que sin importar la secuencia de eventos que ocurra el receptor nunca debe de entregar dos paquetes impares sin haber intervenido un paquete par, y al revez.

 

        Otro requisito semejante es que no debe haber trayectorias en las que el transmisor pueda cambiar de estado dos veces (por ejemplo de 0 a 1 y de regreso a 0 ) mientras el estado del receptor permanezca constante. De existir tal trayectoria en la secuencia correspondiente de eventos se perderian dos marcos sin posibilidad de recuperacion y sin que el receptor se diera cuenta. La secuencia de paquetes entregados tendra un hueco no detectado de dos paquetes.

        Otra propiedad importante de un protocolo es la ausencia de interbloqueos. Un interbloqueo es una sustitucion en la que el protocolo no puede seguir avanzando (es decir, entregando paquetes a la capa de red), sea  cual sea la secuencia de eventos que ocurra. En los terminos del modelo grafico un interbloqueo se caracteriza por la existencia de un subconjunto de estados que es alcanzable desde el estado inicial y que tiene dos propiedades:

 

                1.- No hay transcicion hacia afuera del subconjunto.

 

                2.- No hay transciciones en el subconjunto que causen un avance.

 

        Una vez en el estado de interbloqueo, El protocolo permanece ahi eternamente.

 

        MODELOS DE RED PETRI

 

        Una red petri tiene cuatro elementos basicos: lugares transcisioenes arcos y señales. Un lugar representa un estado en el que puede estar (parte del) sistema. Se indica una transicion  mediante una barra horizontal o vertical cada transicion tiene 0 a mas arcos de entrada. Que llegan de sus lugares de entrada y cero o mas arcos de salida que van a sus lugares de salida.

 

        SE habilita una transicion si hay cuandomenos una  señal de entrada en cada uno de sus lugares de entrada. Cualquier transicion habilitada puede dispararse a voluntad, quitando una señal de cada lugar de salida. Si es diferente el numero de arcos de entrada y de salida no se conservaran las señales, Si se habilitan dos o mas transiciones cualquiera de ellas puede dispararse. La decision de disparo de una trransicion es indeterminada por lo que las redes de petri son utiles para modelar protocolos.

 

        A diferencia del modelo de maquina de estado finito, aqui no hay estados compuestos; el estado del transmisor el estado del canal y el estado del receptor se representan por separado.

        Las redes petri pueden servir para detectar fallas de protocolo de una manera parecida a como se hace con maquinas de estado finito. Por ejemplo, si alguna secuencia de disparo incluyera la transicion 10 dos vecessin interponerse la transcion 11, el protocolo seria incorrecto. El concepto de interbloqueo en una red petri es semejante a su contraparte en una maquina de estado finito.

 

        Las redes petri pueden servir para detectar fallas de protocolo de una manera parecida como se hace con maquinas de estado finito. Las redes petri pueden representarse convenientemente en una forma algebraica semejante a una gramatica, cada transicion contribuye a una regla gramatica. Cada regla espeifica lugares de entrada y salida de transicion.

 

        EJEMPLOS DE ROTOCOLOS DE ENLACE DE DATOS.

 

        En las siguientes secciones examinaremos varios protocolos de enlace de datos de amplio uso, el primerom HDLC, es comun en X25 y muchas otras redes. Despues examinaremos protocolos de enlace de datos usados en internet y enn las redes ATM respectivamente.

 

        HDLC Control de enlace de datos de alto nivel.

        Todos estos protocolos se basan en el mismo principio. Todos estan orientados a bits y se usan el relleno de bits para lograr la transparencia de los datos; difieren solo en aspectos menores aunqeu irritantes. El analisis de los protocolos orientados a bits que haremos a continuacion pretende ser una introduccion general. Si desea los detalles especificos de cualquier protocolo consulte la definicion adecuada.

        Todos los protocolos orientados a bits usan la estructura de marco mostrada. El campo de direccion es de importancia primordial en als lineas con multiples terminales pues sirve para identificar una de las terminales.

 

 

        El campo de control se usa  para numeros de secuencia acuses y otros propositos como se explicara posteriormente. El campo de datos puede contener informacion arbitraria; puede ser de longitud arbitraria aunque la eficiencia de la suma de comprobaciondecae al aumentar el tamaño del marco debido a la mayor probabilidad de multiples errores en rafaga.

        El campo suma de comprobacion es una bariacion menor del bien conocido codigo de redundancia ciclica, usando CRC-CCITT como generador de polinomios. La variacion consiste en permitir la deteccion de bytes de indicacion perdidos.

 

        El bit S/F significa Sondeo /Final. Se usa  cuando una computadora esta sondeando un grupo de terminales, cuando se usa S la computadora esta invitando a la terminal excepto el ultimo tienen el bit S/F puesto en S. El ultimo se pone en F.

        Los diferentes tipos de marcos de supervision se distinguen por el campo de tipo. El tipo 0 es un marco de acuseque sirve para indicar el siguiente marco esperado El tipo 1 es un marco de acuse negativo sirve para indicar que se ha detectado un error de transmision.

        El tipo 2  reconoce todos los marcos hasta pero sin incluir siguiente al igual que receive reary pero le dice al transmisor que detenga el envio.

        El tipo 3 Solicita la retransmision de solo el marco especificado.

 

        La tercera clase de marco es el marco sin numero que a veces se usa para propositos de control aunque tambien puede servir para llevar datos cuando se solicita un servicio no confiable sin conexion.

 

        Todos los protocolos proporcionan un comando disc, que permite a una maquina anunciar que va  a ser desactivada. Tambien cuentan con un comando que permite a una maquina que acaba de regresar y esta en linea anunciar su presencia y obligar el regreso a cero de todos los numeros de secuencia, este comando es SNMR.

 

        Los marcos FRMR contienen un campo de datos de 24 bits que indica por que se rechazo el marco los datos incluyen wl campo de control del marco rechazado los parametros de la ventana y un conjunto de bits que señalan marcos especificos.

        Los marcos de control pueden  perderse o dañarse igual que los datos por lo que deben ser recoocidos tambien se proporciona un marco de control especial para este proposito llamado UA (Acuse sin numero). Dado que solo puede estar pendiente un marco de control nunca hay ambiguedades sobre el marco de control que esta siendo reconocido.

        Los marcos de control restante tienen que ver con la inicializacion sondeo e informe de estado, tambien hay un marco de control que puede contener informacion arbitraria  UI. Estos datos no se pasan a la capa de red pues son para la capa de enlace de datos misma.

 

 

        LA CAPA DE ENLACE DE DATOS EN INTERNET

 

        Internet consiste en maquinas individuales (host enrutadores) y la infraestructura en comunicacion que las conecta. Dentro de un solo edificio, las LAN se usan ampliamente para la interconexion pero la mayor parte de la infraestructura de area intensa esta contruida a partir de arrendadas punto a punto.

 

        En la practica la comunicacion punto a punto se utiliza principalmente en dos situaciones:

 

1)    Miles de organizaciones tienen una o mas LAN cada una con cierta cantidad de hosts( computadoras personales, estaciones de trabajo servidores etc.) junto con un router. Con frecuencia los enrutadores se conectan a una LAN principal.Tipicamente todas la  conexiones al mundo exterior pasan a travez de uno o dos enrutadores distantes.Son estos enrutadores y sus lineas arrendadas los que conformasn las subredes de comunicacion sobre las que esta construida la internet.

2)    En la que las lineas punto a punto desempeñan un papel principal en Internet, son los millones de personas que tienen conexiones caseras a Internet a travez de modems I lineas telefonicas de discado. Generalmente, lo que ocurre es que la PC casera  llama a un proveedor de internet que es una compañia comercial como America on line, compuserve etc. esta PC funciona solo como terminal orientada a caracteres y en esta modalidad el usuario puede ingresar comandos y ejecutar programas pero los servicios graficos de linternet, como la world wide web no estan disponibles. Esta manera de trabajar se llama cuenta de armazon.

 

Como alternativa la PC casera puede llamar al enrutador del proveedor del servicio de internet y entonces actuar como host de internet. Con este enfoque estan disponibles todos los servicios de internet incluidos los graficos.

 

        Tanto para la conexion por linea arrendado de enrutador a enrutador como como para la conexion conmutada de host a enrutador, se requiere  de un protocolo panto a punto de enlace de datos en la linea para manejo de marcos control de errores y las demas funciones de la capa de enlace de datos que hemos estudiado en este capitulo. Dos protocolos de este tipo se usan ampliamente en internet SLIP,PPP.

 

        SLIP Es el mas viejo de los protocolos; fue diseñado para trabajar estaciones de trabajo SUN a Internet a travez de una linea de discado usando un modem.La estacion envia paquetes IP en bruto a travez de la linea con un Byteindicador especial al final para delimitar el marco .

 

        Algunas implementaciones delk SLIP agregan un byte indicador tanto al principio como al final de cada paquete IP  enviado. Aun que aun se utiliza ampliamente SLIP tiene algunos problemas serios, Primero SLIP no efectua deteccion o correccion de errores por lo que es responsabilidad de las capas superiores detectar y recuperar marcos perdidos dañados o fusionados. Solo reconoce IP.

                Ademas cada lado debe conocer por adelantado  la direccion IP del otro ninguna de las dos direcciones  puede asignarse dinamicamente durante el establecimiento del enlace. SLIP no proporciona ninguna forma de verificacion de autenticidad  y no es un standard aprobado en internet.

 

        PPP-PROTOCOLO PUNTO A PUNTO.

 

        La PPP realiza deteccion de errores reconoce multiplies protocolos permite la negociacion de direcciones de IP en el momento de la conexion permite la verificacion de autenticdad y tiene muchas mejoras con respecto a SLIP. El futuro esta claramente en PPP no solo en las lineas por discado sino en las lineas arrendadas de enrutador a enrutador.

        El formato del marco PPP se escogio de modo que fuera muy parecido al formato de marco HDLC. La diferencia principal entre estos dos es que el primero esta orientado a caracteres no a bits. En particular, PPP, como SLIP, usa relleno de caracteres en las lineas por discado con modem, por lo que todos los marcos tienen un numero entero de bytes.

        Toddos los marcos PPP comienzan con el Byte indicador estandard, luego viene el ampo de direccion que va seguido del campo de control, y despues el de protocolo despues viene el campo de carga util, este es de longitud variable hqasta algun maximo negociado si la longitud no se negocia con LCP durante el establecimiento de la linea se usa una longitud predeterminada de 1500 bytes. De ser necesario se puede incluir un relleno despues de la carga.

        Despues del campo de carga util viene el campo de suma de comprobacion que normalmente es de dos bytes pero puede negociarse una suma de comprobacion de 4 bytes.

        En resumen PPP es un mecanismo de enmarcado multiprotocolo adecuado para usarse a travez de modems, lineas de serie de bits HDLC, SONET y otras capas fisicas. Maneja deteccion de errores, negociacion de opciones, comprension de encabezados opcionalmente transmision de confiable de marcos HDLC.

        Cuando la linea esta muerta no hay presencia de una portadora de capa fisica y no existe una conexion de capa fisica. Una vez establecida la conexion fisica la linea pasa a establecer. En ese punto comienza la negociacion de opciones LCP que de tener exito conduce a validar. Al entrar en la fase de red se invoca el protocolo NCP apropiado para configurar la capa de red. Si la configuracion tiene exito se llega a abierta y puede comenzar el transporte de datos.Al terminar el transporte se pasa a terminar de donde regresa a muerta al desactivarse la portadora.

 

        Los cuatro tipos de configuracion permite que el iniciador proponga valores de opcion y que el contador la sacepte o las rechace . En el ultimo caso el contestador puede hacer una propuesta alterna o anunciar que no esta dispuesto a negociar las opciones en absoluto. Las opciones negociadas y sus valores propuestos son parte de lso paquetes LCP.

 

        Los codigos de terminacion sirven para desactivar una linea cuando ya no se necesita. Los codigos de rechazo-codigo y rechazo prtocolo son usados por el contestador para indicar que recibio algo que no entiende. Esta situacion puede significar que ha ocurrido un error de transmision no detectado pero mas probablemente significa que el iniciador y el contestador estan ejecutando versiones diferentes del protocolo LCP Los codigos ECO sirven para probar la calidad de la linea .

 

PROTOCOLO DE VENTANA CORREDIZA

 

 

     En los protocolos previos, los marcos de datos se trasmiten en una sola dirección, Una manera de lograr la trasmisión diplex integral es tener dos canales de comunicación separados y usar cada uno para trafico de datos simples. Si se hace esto, tenemos dos circuitos separados, cada no con un canal “directo” y un canal “en reversa”, el ancho de la banda del canal de reversa se desperdicia casi por completo.

 

 

     Analizando el campo de tipo (kind)en el encabezado de un marco de entrada, el receptor puede saber si el marco es de dato o de acuse.

 

     Al llegar un marco de datos, en lugar de enviar inmediatamente un marco de control independiente, el receptor se aguanta y espera hasta que la capa de red le pase el siguiente paquete, él cause viaja gratuitamente en el siguiente marco de datos de salida. La técnica de retardar temporalmente los acuses para que puedan colgarse del siguiente marco de datos de salida se conoce como incorporación.

 

     La ventaja principal de usar la incorporación en lugar de tener marcos de cause independientes es un mejor aprovechamiento del ancho de la banda disponible del canal. El campo ack(cause) cuesta solo unos cuantos bits, un marco aparte requeriría de un encabezado, él cause y una suma de comprobación.

 

    El protocolo 3 puede fallar en ciertas condiciones peculiares relacionadas con la terminación temprana de la temporizacion. Los tres protocolos siguientes son más robustos y continúan funcionando aun en condiciones patológicas. Los tres primeros pertenecen a la clase de protocolos llamados protocolos de ventana corrediza. Los tres difieren en cuanto a eficiencia, complejidad y requerimientos de buffer, como se explicara después.

 

     La esencia de todos los protocolos de ventana corrediza es que, en cualquier instante, el trasmisor mantiene u grupo de números de secuencia que corresponde a los marcos que tiene permitido enviar. Se dice que estos marcos caen dentro de la ventana receptora correspondiente al grupo de marcos que tiene permitido aceptar.

 

     En algunos protocolos las ventanas son de tamaño fijo, pero en otros pueden crecer y disminuir a medida que se envían  y se reciben loa marcos.

 

     Los números de secuencia de la ventana del trasmisor  representan marcos enviados pero aun no reconocidos, así la ventana mantiene continuamente una lista de marcos no reconocidos.

 

     Dado que los marcos que están en la ventana pueden perderse o dañarse, el trasmisor debe mantener todos estos en su memoria para su posible retransmisión. Por tanto, si el tamaño máximo de la ventana es n, el trasmisor necesita n buffer para contener los marcos no reconocidos.

 

     La ventana de la capa de enlace de datos receptor corresponde a los marcos que puede aceptar. Todo marco que caiga fuera de la ventana se descartare sin comentarios.

 

 

 

UN PROTOCOLO DE VENTANA  CORREDIZA DE UN BIT.

 

     Antes de lidiar con el caso general, examinaremos un protocolo de ventana corrediza de un tamaño máximo de ventana de uno.

 

    Como los demás, comienza por definir algunas variables. Next-frame-to-send indica que marco esta tratando de enviar el trasmisor. En ambos casos, 0 y 1 son las únicas posibilidades.

 

     Normalmente, una de las dos capas de enlace de datos es la que comienza. Solo uno de los programas de capa de enlace de datos debe contener las llamadas de procedimiento to-physical-layer y star- taimer fuera del ciclo principal. El campo de acuse contiene el numero del ultimo marco recibido sin error. Si el numero  de secuencia no concuerda debe continuar intentando enviar el mismo marco. Por cada marco que se recibe se envía un marco de regreso.

 

     Ahora examinemos el protocolo 4 para ver que tan flexible es ante situaciones patológicas. Suponga que A esta tratando de enviar su marcó 0 a b y que B esta tratando de enviar u marco  0 A. Suponga que A envía un marco a B, pero que el intervalo de temporizacion es un poco corto.

 

     En consecuencia, podría terminar su temporizacion repetidamente enviando una serie  de marcos idénticos, todos con sec=0 y ack=1.

 

     Cada vez que llega un duplicado rechazado B envía A un marco que contiene seq= 0 y ack=0. Tarde o temprano uno de estos llegara correctamente A  haciendo que A empiece a enviar el siguiente paquete. Ninguna combinación de marcos perdidos o terminaciones prematuras puede hacer que el protocolo entregue paquetes duplicados a cualquiera de las capas de red, ni que omita un paquete, ni que entre  un ínter bloqueo.

 

 

UN PROTOCOLO QUE USA REGRESAR.

 

     Hasta ahora hemos supuesto prácticamente que el tiempo de trasmisión requerido para que un marco llegue al receptor mas el necesario para que el acuse regrese es insignificante.

 

     Por ejemplo, considera un canal de satélite de 50kbps con un retardo de propagación de ida y vuelta de 500msec.

 

     El problema entes descrito puede verse como una consecuencia de la regla que requiere que el trasmisor espere un acuse antes de enviar oto marco. Si relajamos esta restricción, puede lograrse una eficiencia mucho mejor. Básicamente la solución esta en permitir que el trasmisor envió hasta w marcos antes de bloquearse, en lugar de solo uno. Con una selección adecuada de w, el trasmisor podrá trasmitir marcos continuamente durante un tiempo igual al tiempo de transitó de ida y vuelta sin llenar la ventana.

 

     Esta técnica se conoce como entubamiento. Él envió de marcos en entubamientos por un canal inestable presenta problemas más serios. Primero ¿ qué ocurre si en marco a la mitad de una serie larga sé dala o se pierde?. Al llegar a un marco dañado al receptor obviamente debe descartarse, pero, ¿qué debe hacerse con los marcos correctos que se le siguen?.

 

     Hay dos enfoques básicos ara manejar los errores durante el entubamiento. Una manera  llamada regresa a n el que el receptor simplemente descarte todos los marcos subsecuentes sin enviar acuses de rescate. Otra manera para manejar los errores al transmitir marcos en cascada, llamada repetición selectiva, consiste en hacer que la capa de enlace de datos receptor, almacene todos los datos correctos a continuación del equivocado.

 

 

PROTOCOLO USANDO REPETICIÓN SELECTIVA.

 

     El protocolo 5 funciona bien si los errores son subsecuentes, pero si la línea es mala se desperdicia mucho ancho de banda en los marcos retransmitidos. Una estrategia alterna en el manejo de errores es permitir que el receptor acepte y coloque en Buffer los marcos que siguen a un marco dañado o perdido. Tal protocolo no rechaza marcos porque se daño o se perdió un marco anterior.

 

     La recepción no secuencial introduce ciertos problemas que no se presentan en los protocolos en los que los marcos solo se aceptan en orden. Podemos ilustrar el problema fácilmente con un ejemplo. Suponga que tenemos un numero de secuencia de 3 bits, por, o que se permite al trasmisor enviar hasta 7 marcos antes de requerírsele esperar un acuse. El trasmisor ahora trasmite los marcos 0 a 6. La ventana al receptor le permite aceptar cualquier marco con un numero de secuencia del 0 al 6 inclusive. Los 7 marcos llegan correctamente, por lo que el receptor los reconoce y avanza su ventana parea permitir la recepción de 7,0,1,2,3,4 o 5. Los Buffers se marcan como vacíos.

 

     La esencia del problema es que, una vez que el receptor ha avanzado su ventana, el nuevo intervalo de números de secuencia valida se traslapa con el anterior.

    

     El siguiente grupo de marcos podría ser de duplicados ( Sí se perdieran todos los acuses) o de nuevos (sí se recibieron todos los acuses.

     El pobre receptor no tiene manera de distinguir entre estos 2 casos.