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);
};

As sequências de processamento do protocolo

O protocolo até o momento apresenta funcionalidades elementares que o tornam capaz de estabelecer enlaces rudimentares. Dois blocos funcionais importantes foram definidos:

• Framing (enquadramento): cuida da delimitação de quadros e da detecção de erros.
• ARQ (garantia de entrega): define o formato de quadro e trata dos mecanismos para entrega e retransmissão.

A estrutura atual do protocolo

Presentemente apenas o enquadramento foi implementado e de forma simplificada. No caso, supôs-se que as pontas de enlace se revezam entre transmissões e recepções, de forma que as sequências de envio e recepção de cada lado do enlace são predefinidas. Em outras palavras, o protótipo atual do protocolo não é capaz de reagir assincronamente aos eventos a que está sujeito em situações usuais: a qualquer instante pode-se receber um quadro ou haver a necessidade de transmitir um quadro. Para que o protocolo seja de fato funcional, nenhuma suposição pode ser feita sobre as sequências de quadros recebidas e transmitidas, tampouco as velocidade relativas das aplicações que se comunicam por meio do enlace. Isso implica repensar o modelo de sistema do protocolo para que ele possa atender esses eventos.

A busca de soluções para o protocolo inicia com uma investigação sobre as sequências de processamento que podem ocorrer. A figura a seguir identifica três sequências representativas (há algumas outras, mas essas são esclarecedoras):

Algumas sequências de processamento do protocolo

Deve-se observar que as sequências apresentadas na figura possuem diferentes origens, como se pode ver pelas setas numeradas:

• Envio: esta sequência inicia com (1) o surgimento de uma mensagem fornecida por uma aplicação. Essa mensagem deve então (2) ser encapsulada em um quadro de dados na subcamada ARQ. Em seguida, o quadro gerado em ARQ (3) deve ser delimitado e transmitido pela subcamada de enquadramento. Ao final, a subcamada de enquadramento (4) deve receber o quadro de confirmação transmitido pelo outro lado do enlace, e esse quadro (5) deve ser repassado para a subcamada ARQ.
• Recepção: esta sequência inicia com (1) a recepção de um byte vindo do transceiver RF (subcamada PHY). Se, após a recepção desse byte, um quadro completo e livre de erros foi recebido, (2) ele é repassado à subcamada ARQ. Se for um quadro de dados, uma confirmação é gerada e transmitida via subcamada de enquadramento, conforme passos 3 e 4, e (5) o conteúdo do quadro é entregue à aplicação. Se for um quadro de confirmação, os passos 3 a 5 não são executados.
• Timeout e retransmissão: na ocorrência de um (1) timeout na subcamada ARQ, o último quadro de dados é retransmitido, conforme passos 2 e 3.

Do ponto de vista do modelo de sistema, uma questão importante trata da identificação e tratamento dos eventos pelo protocolo. Conforme as sequências exemplificadas, há estes eventos:

• mensagem vinda da aplicação: pode ser feita de forma síncrona, o que implica a aplicação enviar uma mensagem e ficar bloqueada até que o protocolo confirme sua entrega.
• bytes vindos da camada física: pode ser feito de forma síncrona ou assíncrona. No primeiro caso, a aplicação deve esperar que o protocolo receba algum quadro. No segundo, quadros podem ser recebidos a qualquer momento e então serem notificados para a subcamada ARQ.
• timeout: tempos máximos de espera devem interromper ações em andamento e serem tratados.

Assim, devem-se:

1. Definir um modelo de software para o protocolo: do ponto de vista da estrutura, parece mais simples que cada subcamada seja implementada como uma classe, e que o protocolo como um todo seja uma composição de objetos dessas classes. Do ponto de vista do comportamento, deve-se especificar como a aplicação interage com o protocolo, e como os diferentes eventos são tratados pelo protocolo.
2. Investigar técnicas para atendimento de eventos: o protocolo deve ser capaz de atender eventos conforme a necessidade. Isso envolve identificar mecanismos e facilidades apropriados da plataforma de software (sistema operacional, bibliotecas de programação). Na verdade, isso já foi estudado quando se viu a integração do protocolo com o subsistema de rede do Linux.

Atividade

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