RCO2-2010-1

Redes de Computadores II: Diário de Aula 2010-1

Professor: Marcelo Maia Sobral (msobral@gmail.com)
Lista de email (forum): rco2@googlegroups.com
Atendimento paralelo: 2a e 4a de 10h às 12 h, 4a de 16h às 17h.

Bibliografia

• Antiga página da disciplina (2009-1 e 2009-2)

Listas de exercícios

• 1a lista de exercícios

10/02: Apresentação

Apresentação da disciplina: conteúdo, bibliografia e avaliação, laboratório.

12/02: Introdução

Apresentou-se uma visão geral dos conceitos sobre comunicação de dados, amparada em transparências. Nesta aula se planta a base para iniciar o estudo com maior profundidade da camada de enlace e da camada física.

19/02: Camada de enlace: introdução e serviços

Os serviços identificados na figura acima estão descritos abaixo. A eles foram acrescentados outros dois:

• Encapsulamento (ou enquadramento): identificação das PDUs (quadros) de enlace dentro de sequências de bits enviadas e recebidas da camada física
• Controle de erros: garantir que quadros sejam entregues no destino
  • Detecção de erros: verificação da integridade do conteúdo de quadros (se foram recebidos sem erros de bits)
• Controle de fluxo: ajuste da quantidade de quadros transmitidos, de acordo com a capacidade do meio de transmissão (incluindo o atraso de transmissão) e do receptor
• Endereçamento: necessário quando o enlace for do tipo multi-ponto, em que vários equipamentos compartilham o meio de transmissão (ex: redes locais e redes sem-fio)
• Controle de acesso ao meio (MAC): também necessário para meios compartilhados, para disciplinar as transmissões dos diversos equipamentos de forma a evitar ou reduzir a chance de haver colisões (transmissões sobrepostas)
• Gerenciamento de enlace: funções para ativar, desativar e manter enlaces

Nesta aula se criarão enlaces ponto-a-ponto entre computadores, usando o protocolo PPP. A partir de alguns experimentos se discutem os serviços da camada de enlace, em particular o enquadramento e detecção de erros.

Roteiro do primeiro laboratório

Foi apresentado como funciona o enquadramento (ou sincronização de quadro) do tipo sentinela (usado pelo PPP e HDLC). Nesse caso, usa-se uma flag delimitadora para informar o início e fim de quadro. Há uma segunda flag, chamada de escape (ESC), para evitar que um byte com o valor de flag delimitadora, o qual apareça em algum campo do quadro (ex: dados ou campos de controle) seja erroneamente interpretado como fim de quadro.

O roteiro foi executado até a análise de enquadramento do PPP. A detecção de erros ficou para a aula seguinte.

24/02: Camada enlace: detecção de erros

Finalização do roteiro 1, iniciado na aula de 19/02: fazer a injeção de erros (quadros corrompidos) no enlace.

Probabilidade de erros de transmissão (BER - Bit Error Rate), códigos de detecção de erro e CRC.

Há um resumo nas transparências.

O experimento com o gerador de CRC-16 do PPP pode ser repetido em casa. Ele é capaz de verificar um quadro PPP, que pode ser conseguido usando-se a opção record do pppd. Essa opção grava em um arquivo de log os conteúdos dos quadros PPP enviados e recebidos, que podem depois serem visualizados (ou terem seu bytes extraídos) com o utilitário pppdump. Porém o gerador de CRC-16 fornecido inclui dois arquivos contendo quadros PPP previamente coletados: quadro_correto.raw e quadro_errado.raw. Eles podem ser verificados com o programa fcs (o verificador de CRC-16):

# descompacta o arquivo do gerador de CRC-16
tar czf fcs-rfc.tgz
cd fcs

# Testa o quadro correto
./fcs quadro_correto.raw

# Testa o quadro_errado
./fcs quadro_errado.raw

Há um testador que modifica aleatoriamente uma certa quantidade de bits do quadro_correto.raw, até que encontre um caso em que o erro não seja detectado. Para usá-lo deve-se executar o programa testa.py:

# executa testa.py com 4 erros de bit por quadro gerados aleatoriamente
./testa.py 4

O código fonte do gerador de CRC-16 está no arquivo fcs-rfc.c, o qual foi obtido diretamente da RFC 1662.

26/02: Enlaces ponto-a-ponto entre roteadores

Nesta aula serão configurados enlaces entre dois roteadores Cisco usando os protocolos PPP e HDLC. O objetivo é ter um contato com esse tipo de equipamento, e ver os protocolos em ação. Além disto, será feita uma medição de vazão (throughput) com cada um dos protocolos.

• Roteiro da experiência
• Tutorial da interface de linha de comando Cisco (CLI)
• Resolução de problemas com PPP em roteadores Cisco

03/03: Controle de erros e de fluxo

Ver capítulo 11 do livro "Comunicação de Dados e Redes de Computadores", de Behrouz Forouzan (há uma cópia no xerox).

Resolver a 1a lista de exercícios.

Controle de erros implica garantir a entrega de quadros no destino. Assim, quadros recebidos com erros (i.e., quadros identificados pela detecção de erros como corrompidos) ou quadros extraviados (não recebidos) devem ser retransmitidos. Serviço implementado com protocolos do tipo ARQ (Automatic Repeat Request), tais como:

• Stop-and-Wait: só transmite o próximo quadro quando receber uma confirmação (ACK) do último quadro enviado. Retransmite o último quadro enviado se um tempo máximo de espera pelo ACK (ou timeout) for excedido.
• Go-Back-N: transmite até N quadros sem receber confirmação, quando então espera os ACK antes de enviar mais quadros. Caso exceda o timeout de um dos quadros enviados, retransmite todos os quadros a partir desse quadro.
• Selective Repeat: transmite até N quadros sem receber confirmação, quando então espera os ACK antes de enviar mais quadros. Caso exceda o timeout de um dos quadros enviados, retransmite somente esse quadro.

A rigor Stop-and-Wait ARQ já provê controle de erros, porém tem o potencial de causar uma baixa utilização do meio de transmissão. Os outros mecanismos, Go-Back-N e Selective Repeat, buscam melhorar o aproveitamento do meio, e assim estão também relacionados com o controle de fluxo. Esse serviço tem duas motivações principais:

1. Evitar que um transmissor mais rápido sobrecarregue um receptor
2. Melhorar o aproveitamento do meio de transmissão, quando há necessidade de confirmação de quadros e o meio apresentar um atraso de propagação significativo.

Desempenho do Stop-and-wait

O mecanismo Stop-and-wait apresenta desempenho que depende de seus parâmetros e de características físicas do enlace. Para avaliar seu desmepenho, deve-se determinar qual a taxa efetiva de transmissão que pode ser obtida. A taxa efetiva é definida com a razão entre quantidade de bits transmitidos (contidos em um ou mais quadros) e o tempo que foi necessário para que sejam entregues no destino. Quadros são considerados entregues somente quando o transmissor obtém uma confirmação do receptor. Isto não é a mesma coisa que a taxa de bits nominal do enlace, pois essa taxa informa o tempo que o transmissor leva para transmitir cada bit pelo meio de transmissão (ou melhor, o inverso de quanto tempo dura cada bit no meio). A taxa efetiva pode ser calculada descobrindo-se qual é a utilização do meio de transmissão. A utilização é um valor entre 0 e 1 que informa quanto tempo o meio foi de fato utilizado (i.e. quanto tempo o transmissor de fato precisou para transmitir um ou mais quadros), comparado com o tempo total necessário para fazer a entrega desses quadros. Por exemplo, se o transmissor levou 1 segundo para transmitir um quadro, e depois ficou 1 segundo esperando até receber a confirmação do receptor, a utilização será de 0.5 (o transmissor usou o meio durante 1 segundo, mas o tempo total para entregar o quadro foi de 2 segundos). Assim, as informações necessárias para calcular o desempenho do Stop-and-wait são:

• Taxa nominal de transmissão, ou taxa de bits ($B$): razão entre quantidade de bits que saem do transmissor e o tempo que leva para que saiam.
• Tempo de transmissão ($A_{t}$): tempo gasto pelo transmissor para transmitir um quadro. É o tempo gasto desde quando o primeiro bit do quadro começa a sair do transmissor, até quando o último bit termina de sair. Esse tempo depende da quantidade de bits transmitidos (F) e da taxa de bits nominal do meio (B): $A_{t}=F/B$
• Atraso de propagação ($A_{p}$): tempo gasto pelo sinal para se propagar desde o transmissor até o receptor. Independe da quantidade de bits transmitidos, pois é uma característica física do meio.
• Outros atrasos ($A_{o}$): outros atrasos envolvidos durante a entrega do quadro
• Tempo de envio ($A_{e}$): tempo necessário para que um quadro seja totalmente transmitido do transmissor até o receptor: $A_{e}=A_{t}+A_{p}$
• Tempo de entrega (A): tempo necessário para que um quadro seja entregue no receptor, i.e. desde o instante em que o quadro começa a ser transmitido até quando o reconhecimento chega ao transmissor:
  $A=A_{t}+2A_{p}+A_{t_{ACK}}+A_{o}$
• Utilização do meio (U): razão entre o tempo em que o meio foi de fato usado pelo transmissor para transmitir o quadro, e o tempo total necessário para que o quadro seja considerado entregue:
  $U={\frac {A_{t}}{A}}={\frac {A_{t}}{A_{t}+2A_{p}+A_{t_{ACK}}+A_{o}}}$
• Taxa efetiva de transmissão (E): a taxa de bits percebida pelo transmissor para fazer a entrega de quadros: $E=B\cdot U$
• Timeout ($T_{o}$): tempo máximo de espera por um reconhecimento.

05/03: Controle de erros e de fluxo

Ver capítulo 11 do livro "Comunicação de Dados e Redes de Computadores", de Berhouz Forouzan.

Análise do mecanismo ARQ Go-Back-N. Demonstração da melhoria da utilização do meio usando esse mecanismo, comparado ao Stop-and-Wait.

Na aula anterior foi visto que o mecanismo ARQ Stop-and-wait é eficaz no controle de erros. Isto significa que ele garante que um quadro seja entregue no destino. Além disto, o Stop-and-wait não se atrapalha se ocorrerem os seguintes erros de transmissão:

• Perda de quadro de dados (inclui quadro de dados recebido com erros e assim descartado).
• Perda de quadro ACK
• Quadro ACK atrasado, fazendo com que ocorra um timeout de espera por confirmação e consequente retransmissão

Ser eficaz no controle de erros não significa ser eficiente. Foi visto que se o atraso de propagação for da ordem de grandez do atraso de transmissão, a utilização do meio se reduz significativamente. Por exemplo, se o atraso de propagação for metade do de transmissão:

$U={\frac {A_{t}}{A_{t}+2A_{p}+A_{t_{ACK}}}}={\frac {A_{t}}{A_{t}+2A_{t}/2+A_{t_{ACK}}}}={\frac {A_{t}}{2A_{t}+A_{t_{ACK}}}}<{\frac {1}{2}}$

Já se esses dois atrasos forem iguais:

$U={\frac {A_{t}}{A_{t}+2A_{p}+A_{t_{ACK}}}}={\frac {A_{t}}{A_{t}+2A_{t}+A_{t_{ACK}}}}={\frac {A_{t}}{3A_{t}+A_{t_{ACK}}}}<{\frac {1}{3}}$

E assim, quanto maior for o atraso de propagação, pior será a utilização do meio de transmissão. A raiz do problema está no tempo em que o meio deixa de ser usado por causa do atraso de propagação. Isto também quer dizer que uma certa quantidade de quadros poderia ser transmitida enquanto não chega a confirmação do primeiro quadro. Essa melhoria no ARQ se chama controle de fluxo, pois visa regular a quantidade de quadros que podem ser enviados de acrodo com a capacidade do meio de transmissão e do sistema destino. O ARQ mais simples que implementa uma forma de controle de fluxo se chama Go-back-N.

Go-back-N transmite até uma certa quantidade de quadros, sem ainda ter recebido uma confirmação do primeiro quadro enviado. À medida que as confirmações forem recebidas, novos quadros podem ser enviados. Esse mecanismo está ilustrado na figura abaixo:

Figura 1: uma possível sequência de transmissão com Go-back-N

Para controlar a quantidade de quadros enviados usa-se a técnica de janela deslizante. A janela é o conjunto de quadros transmitidos e ainda não confirmados, e que precisam ser lembrados para caso seja necessário retransmiti-los. Assim, sempre que um novo quadro é transmitido aumenta-se o tamanho da janela em uma unidade, e quando um quadro é confirmado diminui-se o tamanho da janela em ao menos uma unidade. Há um tamanho máximo para a janela, que corresponde à quantidade máxima de quadros que podem ser transmitidos sem ter ainda uma confirmação de entrega. Esse tamanho máximo de janela é de grande importância para a eficiência do Go-back-N, pois tem influência direta na utilização máxima que pode ser obtida do meio de transmissão.

Um controle com janela deslizante precisa que se numerem os quadros sequencialmente, de forma a representar a ordem em que foram enviados. Assim, quadros fora de ordem não são aceitos no destino (ao menos no caso do Go-back-N). Por razões de praticidade, a quantidade de números de sequência necessária para o Go-back-N é igual ao tamanho máximo da janela + 1. Por exemplo, se o tamanho máximo da janela for 3, são necessários no mínimo 4 números de sequência (ex: 0 a 3). Se a quantidade de números de sequência for igual ao tamanho da janela, pode ocorrer um erro no controle de erros do mecanismo (tende descobrir que erro seria esse ...). A figura abaixo ilustra um exemplo em que se fazem transmissões de quadros com janela de tamanho máximo 3 (a janela a cada instante é destacada em amarelo, e os números correspondem aos números de sequência dos quadros):

Note que, assim como no Stop-and-wait, os quadros de reconhecimentos indicam qual o próximo quadro a ser aceito pelo destino. Além disso, o Go-back-N aceita reconhecimentos cumulativos. Quer dizer, se houver três quadros na janela de transmissão, e for recebido um reconhecimento relativo ao segundo quadro, o transmissor considera que tanto o primeiro quanto o segundo quadro foram recebidos com sucesso. Isto é possível pois nesse ARQ o receptor aceita apenas quadros em ordem.

Mas qual deve ser a utilização do meio de transmissão com o Go-back-N ? Para responder a essa questão devem-se considerar duas situações:

1. O atraso para receber o primeiro ACK é maior ou igual ao tempo de transmissão para enviar todos os quadros permitidos pelo tamanho máximo de janela: essa situação está mostrada na figura 1, que mostra uma sequência de transmissão. A utilização nesse caso será:
   $U={\frac {N\cdot A_{t}}{A_{t}+2A_{p}+A_{t_{ACK}}}}$
2. O atraso para receber o primeiro ACK é menor que o tempo de transmissão de uma janela de tamanho máximo: nesse caso, a utilização é máxima (= 1), pois todo o atraso de propagação é aproveitado para enviar quadros.

Falta ainda ver o que acontece em situações de erro ...

10/03: Controle de erros e de fluxo

Análise do mecanismo ARQ Selective Repeat. Análise de seu desempenho, comparado ao Stop-and-wait e Go-Back-N. Análise do desempenho dos mecanismos ARQ na ocorrência de erros. Experiências com um simulador de um enlace ponto-a-ponto.