PTC29008: Projeto 1: Garantia de entrega

• 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 garante que uma mensagem foi entregue ao destino. Enquanto uma mensagem não tiver sua entrega assegurada, ela permanece na fila de saída mantida no transmissor pelo protocolo.

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:

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

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.

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 !