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:

As MEF projetadas podem ser minimizadas (terem menos estados) ?
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

Modele a garantia de entrega como uma MEF, de forma que se combinem os comportamentos de receptor e transmissor em uma única MEF
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

OBS:

M: numero de sequência de recepção
N: numero de sequência de transmissão

O formato de quadros no protocolo

SKB: uma estrutura de dados para representar pacotes no kernel Linux

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 notifica
timeout: notificado pelo poller via método handle_timeout

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

byte: notificado pelo poller via método handle
timeout: notificado pelo poller via método handle_timeout

Esses eventos devem ser tratados por meio das respectivas máquinas de estados. Para diferenciá-los, uma forma é declarar um tipo Evento, o qual encapsule o tipo de evento e os dados a ele associados. Por exemplo, no caso do ARQ na versão C++ (a classe Frame não está descrita):

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

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

  // esta struct descreve um Evento
  struct Evento {
    TipoEvento tipo;
    Frame * frame_ptr;

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

    // construtor com parâmetros: cria um evento Payload ou Quadro
    // o objeto Frame representa tanto um payload quanto um quadro
    Evento(TipoEvento t, Frame * a_frame) : tipo(t), frame_ptr(a_frame) {}
  };

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

... e na versão Python (note o uso de type annotation, enum, e attrs):

from enum import Enum
import attr

class TipoEvento(Enum):
  'Identificadores para tipos de eventos'
  Payload = 1
  Timeout = 2
  Quadro = 3

@attr.s
class Evento:
  'Representa um evento, contendo seu tipo e os dados a ele associados'
  tipo = attr.ib(default=TipoEvento.Timeout)
  msg = attr.ib(factory=bytes)


class ARQ (Layer):
  # demais métodos

  def handle_fsm(e:Evento):
    '''executa a MEF, passando como parâmetro um evento'''
    pass

Atividade

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

PTC29008: Projeto 1: Garantia de entrega

Índice