PTC29008: Projeto 1: Garantia de entrega

Próxima aula

• Seção sobre Entrega confiável no capítulo 3 do livro Redes de Computadores, 6a ed., de J. Kurose e K. Ross

A garantia de entrega pode ser definida como um serviço do protocolo que possibilita que o transmissor se certifique de que uma mensagem foi entregue ou não ao destino. Enquanto uma mensagem não tiver sua entrega assegurada, ela permanece na fila de saída mantida no transmissor pelo protocolo. Esse serviço tipicamente é implementado usando algum mecanismo ARQ.

Mecanismos ARQ (Automatic Repeat reQuest) podem ser incorporados a protocolos para garantir a entrega de mensagens, preservando a ordem de envio e buscando eficiência no uso do canal. Tais mecanismos se baseiam em alguns elementos:

• Mensagens de dados
• Mensagens de confirmação positiva (ACK) e negativa (NAK)
• Numeração de sequência de mensagens
• Retransmissão de mensagens perdidas ou recusadas

Maiores detalhes podem ser lidos nesta descrição de mecanismos ARQ, incluindo uma análise simplificada de seu desempenho.

Escolha do mecanismo ARQ a ser utilizado no protocolo de enlace

• ARQ Híbrido

Qual dentre os mecanismos ARQ deve ser o mais apropriado para o tipo de enlace do protocolo ?

Dentre os três mecanismos ARQ elementares, pare-e-espere atende plenamente a necessidade de garantia de entrega e eficiência no uso do canal de comunicação do protocolo de enlace. Isso se conclui com a análise de utilização do canal usando pare-e-espere. Sendo B a taxa de bits, F o tamanho de quadro, e L a distância a ser percorrida pelo sinal no enlace, a utilização do canal pode ser estimada desta forma:

$B=9600bps$
$F=1024bytes$
$F_{ack}=4bytes$
$L=1000m$
$A_{t}={\frac {F}{B}}={\frac {1024*8}{9600}}=853ms$

$A_{tack}={\frac {F_{ack}}{B}}={\frac {4*8}{9600}}=3.33ms$

$A_{p}={\frac {L}{c}}={\frac {1000}{3\cdot 10^{8}}}=3.33us$

$U={\frac {A_{t}}{A_{t}+A_{tack}+2\cdot A_{p}}}=0.996$

Portanto, a utilização do meio seria no máximo em torno de 0.99 (ou 99%).

Modelagem do mecanismo ARQ

O mecanismo ARQ pare-e-espere deve ser modelado antes de ser implementado no protocolo. Sua disposição na estrutura do protocolo deve ser esta:

Assim, a subcamada ARQ envia e recebe quadros de dados e de confirmação da subcamada inferior (detecção de erros + enquadramento). O mecanismo ARQ implementado nessa subcamada pode ser modelado como duas máquinas de estado finitas: uma para transmissão e outra para recepção:

MEF para a transmissão do ARQ

MEF para a recepção do ARQ

Duas questões despontam quanto à modelagem com máquinas de estados finitos:

1. As MEF projetadas podem ser minimizadas (terem menos estados) ?
2. As MEF podem ser combinadas em uma nova MEF que contenha o comportamento tanto do transmissor quanto do receptor ?

Para investigar essas questões, devem-se estudar máquinas de estados finitos no contexto de protocolos de comunicação. MEF é uma ferramenta de modelagem útil para representar o comportamento ou regras de procedimento (proceding rules) de protocolos.

Atividade: MEF da garantia de entrega do protocolo de comunicação

1. Modele a garantia de entrega como uma MEF, de forma que se combinem os comportamentos de receptor e transmissor em uma única MEF
2. Implemente sua garantia de entrega como uma nova subcamada de seu protocolo !

O formato de quadros no protocolo

O quadro possui um cabeçalho com dois campos:

• Controle: contém tipo de quadro (ACK ou DATA) e número de sequẽncia (0 ou 1)
• Proto: contém o tipo de conteúdo transportado pelo quadro (OBS: este campo existe somente em quadros do tipo DATA)

O campo FCS, ao final do quadro, contém o valor do código CRC-16-CCITT. Esse campo ocupa 2 bytes, sendo o primeiro o LSB (Least Significant Byte) do código CRC, e o último o MSB.

O formato de um quadro

Diferenciação de eventos nas MEF do protocolo

O componente ARQ está sujeito a pelo menos três tipos de eventos:

• payload: notificado quando a aplicação chama o método envia do Protocolo
• quadro vindo do Enquadramento: notificado pelo Enquadramento por meio do método receive
• timeout: notificado de alguma forma ainda a ser determinada

O componente Enquadramento, por sua vez, responde a dois eventos:

• byte: notificado pela Serial por meio de seu método read
• timeout: notificado de alguma forma ainda a ser determinada

Esses eventos devem ser tratados por meio das respectivas máquinas de estados. Para diferenciá-los, uma forma é declarar um tipo Evento privativo, o qual encapsule o tipo de evento e os dados a ele associados. Por exemplo, no caso do ARQ:

class ARQ : public Layer {
 public:
   // métodos públicos

 private:
  enum TipoEvento {Payload, Quadro, Timeout};

  // esta struct descreve um Evento
  struct Evento {
    TipoEvento tipo;
    char * ptr;
    int bytes;

    // construtor sem parâmetros: cria um Evento Timeout
    Evento() { tipo = Timeout;}

    // construtor com parâmetros: cria um evento Payload ou Quadro
    Evento(TipoEvento t, char * p, int len) : tipo(t), ptr(p), bytes(len) {}
  };

  // executa a MEF, passando como parâmetro um evento
  void handle_fsm(Evento & e);
};

Atividade

1. Implemente a garantia de entrega do seu protocolo, levando em conta os tipos de eventos que devem ser tratados