PDF de programación - Prácticas de redes de ordenadores - ARQ

UUnniivveerrssiiddaadd PPoolliittééccnniiccaa ddee CCaarrttaaggeennaa

EEssccuueellaa TTééccnniiccaa SSuuppeerriioorr ddee IInnggeenniieerrííaa ddee

PPRRÁÁCCTTIICCAASS DDEE RREEDDEESS DDEE OORRDDEENNAADDOORREESS

TTeelleeccoommuunniiccaacciióónn



Propuesta del Trabajo de Prácticas 2007

Simulación de algoritmos Automatic Repeat Request (ARQ)



Profesores:

Esteban Egea López
Juan José Alcaraz Espín
Joan García Haro



2

3

1.1
1.2

Índice.
Índice. .............................................................................................................................................................................. 2
1 Consideraciones generales. ...................................................................................................................................... 3
Objetivos.......................................................................................................................................................... 3
Introducción..................................................................................................................................................... 3
1.2.1
Qué deben hacer los alumnos................................................................................................................... 3
Cómo está organizada esta propuesta....................................................................................................... 3
1.2.2
1.2.3 Mecanismos Automatic Repeat reQuest (ARQ) ...................................................................................... 3
1.2.4
Go-Back-N............................................................................................................................................... 4
1.2.5
Retransmisión Selectiva........................................................................................................................... 4
1.2.6
Rendimiento teórico de los mecanismos de ARQ.................................................................................... 7
Fases del desarrollo del simulador y medidas a realizar .......................................................................................... 7
Escenario 1. Algoritmo Go-Back-N................................................................................................................. 8
2.1
Escenario 2: Selective Repeat. Un temporizador ............................................................................................. 8
2.2
Escenario 3: Selective Repeat. Múltiples temporizadores. .............................................................................. 9
2.3
Sugerencias para la implementación........................................................................................................................ 9
Consejos para la depuración y verificación del módulo................................................................................... 9
3.1
Consejos para una mayor claridad en el código............................................................................................. 10
3.2
Gestión eficiente de la memoria..................................................................................................................... 10
3.3
Toma de muestras .......................................................................................................................................... 10
3.4
Selección de semillas ..................................................................................................................................... 11
3.5
Ejecuciones más rápidas ................................................................................................................................ 11
3.6
Realización de réplicas................................................................................................................................... 12
3.7
Uso de la librería de plantillas STL................................................................................................................ 13
3.8
4 Material a entregar y criterios de evaluación ......................................................................................................... 14
4.1 Memoria y Código ......................................................................................................................................... 14
Criterios de evaluación................................................................................................................................... 14
4.2
4.3
Grupos de una ó tres personas........................................................................................................................ 14
5 Bibliografía ............................................................................................................................................................ 15



1 Consideraciones generales.

1.1 Objetivos

En este trabajo de prácticas los alumnos realizarán por parejas un simulador de algoritmos clásicos ARQ, es decir,
Go-Back-N y Selective Repeat. Los alumnos deben desarrollar y depurar el simulador y extraer y analizar una serie de
resultados. Tanto los algoritmos como los resultados a presentar se detallan en esta memoria.

1.2 Introducción

1.2.1 Qué deben hacer los alumnos
Los alumnos deben implementar por parejas básicamente dos módulos simples en C++ y NED llamados
respectivamente transmisor y receptor. Lo que deben hacer estos módulos se detalla en esta propuesta. Estos
módulos deberán ser incorporados al entorno de simulación OMNET++, es decir, se añadirán el resto de módulos que
sean necesarios. Con el simulador completo, se deberán tomar una serie de medidas, que quedarán recogidas en una
memoria final, junto con el código comentado.

Las funcionalidades de los módulos deben realizarse de forma incremental. Para verificar el funcionamiento de dichas
funcionalidades se proponen una serie de escenarios de simulación. Para cada uno de estos escenarios se plantean una
serie de experimentos de los que el alumno deberá obtener unas medidas concretas y extraer conclusiones. El
alumno deberá programar la toma de muestras para la obtención de estas medidas.

Se deberá entregar una memoria del trabajo realizado. El contenido de la memoria y los criterios de evaluación
también están descritos en esta propuesta. Conviene destacar por adelantado que para alcanzar el aprobado no es
necesario que se implementen en su totalidad los algoritmos y medidas propuestos en esta memoria.

1.2.2 Cómo está organizada esta propuesta.
En los apartados ¡Error! No se encuentra el origen de la referencia. a 1.2.6 de la introducción se proporciona al
alumno una visión general de los mecanismos de ARQ y de las funcionalidades que se van a implementar.
En el apartado 2 se describen uno a uno los escenarios que se deben configurar y se especifican las medidas que se
deben tomar en cada uno de ellos.
En el apartado 3 se dan algunas sugerencias y “pistas” para la realización de este trabajo.
Finalmente en el apartado 4 se especifican los criterios de evaluación y en 0 se da una breve reseña bibliográfica que
se recomienda consultar para resolver dudas y profundizar en los aspectos descritos.

1.2.3 Mecanismos Automatic Repeat reQuest (ARQ)
Los mecanismos ARQ son algoritmos genéricos de control de flujo y control de errores extremo a extremo [2-3].
Aunque habitualmente se describen en la capa de enlace, se emplean también en capas superiores, con las
modificaciones pertinentes. Por ejemplo, las diferentes versiones de TCP emplean variantes de estos algoritmos para
el control de errores extremo a extremo y control de la congestión de red.

Estos algoritmos basan su funcionamiento en el uso de detección de errores, temporizadores, paquetes de
reconocimiento positivo (ACK) y negativo (NACK) y retransmisiones de los diferentes tipos de paquetes Para
explicar su funcionamiento supondremos que existen dos estaciones (transmisor, tx y receptor, rx), conectadas
directamente con un enlace bidireccional. El enlace viene descrito por una velocidad de transmisión binaria (V), una
probabilidad de error de bit (BER) y un retardo de propagación extremo a extremo (Tprop). Estos tres parámetros
definen el enlace para cada sentido independientemente.

De manera general el funcionamiento de estos algoritmos es el siguiente: el transmisor encapsula los datos en tramas
de nivel de enlace (DATA) y los envía al receptor. Cada trama se numera consecutivamente, mediante un número de
secuencia, de manera que se pueda garantizar la entrega ordenada al nivel superior. La trama de enlace incluye un
campo de verificación de trama (CRC) de manera que el receptor puede comprobar si la trama ha sido dañada en el
tránsito. En este caso la trama se descarta. En caso contrario, se envía al transmisor una trama de reconocimiento, que
incluye el número de secuencia de la trama recibida correctamente. El transmisor debe retransmitir las tramas que no
han sido recibidas correctamente. Para evitar que el protocolo quede bloqueado, es necesario utilizar temporizadores

para la retransmisión de las tramas. Los distintos algoritmos ARQ definen la forma en particular en la que se deben
emplear los distintos tipos de tramas y los temporizadores para implementar el comportamiento deseado.
El control de flujo se realiza mediante la técnica de ventana deslizante. En esencia, esta técnica consiste en limitar el
número máximo de tramas en tránsito. Es decir, el número de tramas que han sido enviadas pero no han sido
reconocidas. A este número se le denomina tamaño máximo de ventana, W. El transmisor mantiene un buffer con