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). 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 !

A modelagem da garantia de entrega

A garantia de entrega deve ser feita com um mecanismo ARQ do tipo pare-e-espere. A máquina de estados finitos a seguir resume o comportamento do ARQ para o protocolo de comunicação.

A MEF do ARQ: N é o número de sequência de envio, e M o de recepção

Um possível modelo de software (esboço do diagrama de classes)

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:
   // 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(Evento & e);
};

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

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).

Atividade

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

Conjunto de mensagens (vocabulário) e regras de procedimento (gramática)

O protocolo proposto no projeto 1 deve ser especificado. Isso implica sua descrição sem ambiguidades, para que possa ser corretamente implementado. A especificação envolve a definição do serviço oferecido, seu vocabulário e sintaxe, sua gramática, e a verificação de seu comportamento. Sua implementação se chama entidade de protocolo, sendo composta por software e (por vezes) hardware.

Diagrama simplificado da entidade de protocolo

A entidade de protocolo a ser desenvolvida implica pelo menos:

• Especificar e implementar a interface de acesso ao protocolo para seus usuários.
• Definir um vocabulário de mensagens, e a sintaxe abstrata dessas mensagens.
• Modelar as regras de procedimento, que determinam as sequências de mensagens e eventos aceitas pelo protocolo.
• Especificar a codificação das mensagens, o que se denomina sua sintaxe concreta.

Vocabulário

Um protocolo envolve intercâmbio de mensagens entre duas ou mais entidades. O conjunto de mensagens que compõe o protocolo é chamado de vocabulário.

Ex: um protocolo do tipo stop-and-wait possui um vocabulário dado por:

$M=\lbrace data_{0},~data_{1},~ack_{0},~ack_{1}\rbrace$

Essas mensagens podem ser usadas em sequências como mostrado neste diagrama de sequência temporal:

Cada mensagem carrega alguma informação composta por dados (o conteúdo gerado pela aplicação) e meta-dados (o conteúdo de controle gerado e usado pelo próprio protocolo). O formato das mensagens é dado pela 'sintaxe do protocolo, e existem diferentes métodos para sua descrição. Esse aspecto do protocolo deve ser trabalhado mais adiante.

Regras de procedimento

Intercâmbios de mensagens entre entidades de um protocolo devem respeitar regras quanto às sequências válidas de mensagens. O conjunto dessas regras é chamado de regras de procedimento (procedure rules).

Um protocolo é um sistema a eventos-discretos. Isso significa que as ações em um protocolo ocorrem em instantes pontuais, e não continuamente. Essas ações, ou acontecimentos, são chamadas de eventos. Por exemplo, a recepção ou envio de uma mensagem, a ocorrência de timeout, o início ou término de uma sessão são eventos ao longo de uma comunicação. Assim, um protocolo interage com seu ambiente (canal de comunicação, usuário), sendo acionado por eventos (ex: recepção de mensagem) que são respondidos com a realização de ações (ex: envio de mensagem). Seu comportamento depende do histórico de eventos passados, o que é chamado de estado. Esse tipo de sistema demanda modelos específicos para a descrição das sequências possíveis de eventos, incluindo a informação sobre o estado do protocolo.

Um diagrama de sequência temporal, como mostrado no exemplo do protocolo stop-and-wait, apesar de ilustrativo não pode ser usado para especificar as regras de um protocolo. Esse tipo de diagrama é útil para apresentar uma sequência específica de troca de mensagens, mas não todas as sequências possíveis. Quer dizer, ele não tem expressividade para especificar todas as possíveis sequências de mensagens durante as comunicações. Outros tipos de diagramas e métodos formais devem ser usados nesse caso.

Máquinas de Estados Finitos

• Capítulo 8 de Design and Validation of Computer Protocols

O protocolo stop-and-wait usado como exemplo envia uma mensagem por vez, aguardando sua confirmação para enviar uma nova mensagem. Caso a confirmação não seja recebida, a última mensagem é retransmitida. Um exemplo de protocolo que usa esse tipo de mecanismo de controle de erros é o MAC CSMA/CA do padrão IEEE 802.11. Uma versão para o stop-and-wait usa um bit para numerar mensagens, de forma a evitar a duplicação de mensagens no receptor. Assim, seu vocabulário é composto pelas mensagens msg0, msg1, ack0, ack1. As regras de procedimento desse protocolo podem ser ilustradas usando diagramas de máquinas de estados finitos, como mostrado a seguir:

Máquinas de estados finitos do transmissor para o ARQ stop-and-wait

Máquinas de estados finitos do receptor para o ARQ stop-and-wait

Uma máquina de estados finitos (ou simplesmente MEF) é composta de um conjunto de estados (as bolas) e transições (as setas). Um estado representa uma instância de comportamento do sistema (ex: ocioso, espera), e uma transição representa uma mudança de estado. Uma transição possui um estado inicial e um ou mais estados finais, além de uma condição para que ocorra (a isso se chama evento). Esse modelo básico de MEF possui expressividade para modelar alguns sistemas, e apresenta diversas propriedades importantes para analisar o comportamento desses sistemas.

Formalmente, uma MEF é definida pela tupla (Q, q0, S, T), sendo:

• Q: um conjunto não-vazio de estados
• q0: um elemento de Q denominado estado inicial
• S: um conjunto de eventos (ou mensagens), o qual forma um vocabulário
• T: uma relação de transição de estados

A relação de transição de estados T é usualmente representada por uma tabela cujas linhas contêm o estado inicial, uma ação, e o estado final. No caso da MEF do transmissor do protocolo stop-and-wait, essa tabela poderia ser:

Estado inicial	Ação	Estado final
0	envia m0	1
1	recebe ack1	2
1	recebe ack0	0
1	timeout	0
2	envia m1	3
3	recebe ack0	0
3	recebe ack1	2
3	timeout	2

Para o projeto do protocolo de comunicação, a MEF tem duas finalidades:

• Modelar as regras de procedimento do protocolo: a MEF torna possível conceber o comportamento do protocolo, definindo o que deve ser feito a depender das mensagens recebidas e transmitidas, entre outros eventos. Além disso, mecanismos internos do protocolo também podem ser modelados com MEF (ex: enquadramento).
• Verificar o comportamento do protocolo: o projeto do protocolo pode esconder problemas sutis e difíceis de identificar. Existem técnicas e ferramentas que auxiliam na verificação da correção das regras de procedimento do protocolo, evidenciando problemas tais como impasses e perdas de sincronismo.

Num primeiro momento, as MEF serão utilizadas para modelar o protocolo de comunicação. Seu uso para verificar a correção do protocolo deve ser realizado após ter sido construído um protótipo.