PTC29008: Projeto 1: um protocolo de comunicação

Próxima aula

Um protocolo de comunicação está relacionado aos mecanismos necessários para a entrega de mensagens entre duas aplicações quaisquer. Considerando uma arquitetura de redes em camadas como TCP/IP, protocolos de comunicação correspondem às camadas de enlace até transporte. Questões como garantia de entrega, controle de sequência, tratamento de erros, sincronização, estabelecimento e término de sessão, multiplexação e delimitação de mensagens, entre possivelmente outras, fazem parte do projeto de tais protocolos. Para introduzir o projeto de um protocolo de comunicação, o primeiro projeto da disciplina envolve um protocolo para estabelecimento de enlace sem-fio ponto-a-ponto.

Considere o caso de uma nova interface de rede sem-fio composta por um transceiver RF capaz de transmitir a distâncias de até 1 km. No caso de distâncias como essa, a taxa de transmissão possível de ser obtida é de 2400 bps, porém distâncias menores possibilitam taxas maiores, até um máximo de 19200 bps. Esse transceiver pode ser usado como uma interface serial do tipo UART. Portanto, com ele podem-se criar enlaces de média distância e baixas taxas de transmissão.

O transceiver RF usado como UART proporciona uma camada física, cuja interface de acesso a serviço oferece operações de envio e recepção de bytes. Nenhuma facilidade para delimitação de mensagens, endereçamento, sincronização e tratamento de erros é fornecida. De fato, tais serviços devem ser implementados em um protocolo de enlace que use esse transceiver como camada física.

O projeto 1 envolve o desenvolvimento de um protocolo de comunicação usando esse transceiver RF, de forma a oferecer um serviço de comunicação com essas características.

Um primeiro experimento

• A classe Serial (C++)
• pySerial: módulo Python para comunicação serial
• Serial Programming HOWTO
• Serial Programming/Serial Linux
• Documentação sobre termios

O primeiro contato com o transceiver RF envolve escrever um programa que transmita a mensagem Hello world! de um computador a outro usando um enlace sem-fio. Para isso, deve-se:

1. Configurar dois transceivers RF
2. Conectá-los a dois computadores diferentes usando adaptadores USB
3. Testar a comunicação usando programa para comunicação serial (ex: gtkterm, picocom, minicom). OBS: ver esta observação sobre um detalhe quanto ao uso do transceiver via USB.
4. Escrever um programa que se comunique por meio dos transceivers.

A serial modelada como uma classe C++

Uma implementação da classe Serial #ifndef SERIAL_H #define SERIAL_H #include <termios.h> class Serial { public: Serial(); Serial(const char * path, int rate); Serial(const Serial& orig); virtual ~Serial(); int get() { return tty_fd;} bool cca(); int write(const char * buffer, int len); int read(char * buffer, int len); int read(char * buffer, int len, bool block); char read_byte(); private: int tty_fd; }; #endif /* SERIAL_H */ serial.h #include <iostream> #include "Serial.h" using namespace std; int main() { Serial rf("/dev/ttyUSB0", B9600); string msg = "um teste ...\r\n"; char buffer[32]; int n = rf.write(msg.c_str(), msg.size()); cout << "Enviou " << n << " bytes" << endl; n = rf.read(buffer, 32); cout << "Recebeu " << n << " bytes: "; cout.write(buffer, n); cout << endl; } main.cpp: exemplo de uso da classe serial

Emulador de link serial

O programa serialemu emula um link serial com determinada taxa de bits, BER e atraso de propagação. Para usá-lo deve-se fazer o seguinte:

1. Obtenha o código-fonte do serialemu
2. Descompacte o arquivo Serialemu.zip, e entre no subdiretório Serialemu.
3. Compile-o com este comando:

   aluno@M2:~/Serialemu$ make
   

4. Copie o programa compilado para algum subdiretório mais conveniente ... por exemplo, /home/aluno, e depois mude para esse subdiretório:

   aluno@M2:~/Serialemu$ cp -a dist/Debug/GNU-Linux/serialemu /home/aluno/
   aluno@M2:~/Serialemu$ cd /home/aluno
   aluno@M2:~/$
   

5. Execute-o de forma que ele apresente suas opções de execução:

   aluno@M2:~$ ./serialemu -h
   Uso: ./serialemu [-b BER][-a atraso][-f][-B taxa_bits] | -h
   
   BER: taxa de erro de bit, que deve estar no intervalo  [0,1]
   atraso: atraso de propagação, em milissegundos.
   taxa_bits: taxa de bits em bits/segundo
   -f: executa em primeiro plano (nao faz fork)
   

6. Execute-o então da forma desejada, selecionando a taxa de bits (default: ilimitada), BER (default: 0) e atraso de propagação (default: 0). O serialemu automaticamente vai para segundo plano (daemonize), liberando o terminal. Ex:

   aluno@M2:~$ ./serialemu -B 9600
   /dev/pts/17 /dev/pts/2
   aluno@M2:~$
   

   ... e anote os dois caminhos informados pelo serialemu: eles são as duas portas seriais que correspondem às pontas do link serial emulado.
7. Execute seu protocolo usando essas portas seriais virtuais.

Mesma que se opte pelo uso do emulador de serial, deve-se notar que, ao final, o protocolo deve ser demonstrado na plataforma Linux com o transceiver RF. Assim, o uso do emulador de serial tem por finalidade somente facilitar o desenvolvimento dos mecanismos básicos do protocolo.

O transceiver RF APC 220

O transceiver RF a ser utilizado se chama APC 220. Alguns documentos podem ser úteis:

• Data sheet
• Manual
• Um tutorial
• Outro tutorial

Início do protocolo de enlace

• DICA: Ver capítulo 11 do livro "Comunicação de Dados e Redes de Computadores", de Behrouz Forouzan, ou capítulo 5 do livro "Redes de Computadores" de Andrew Tanenbaum.

O protocolo de enlace a ser desenvolvido se destina a links com baixa taxa de transmissão e suscetíveis a erros frequentes. As mensagens são curtas (<= 256 bytes), e transmitidas de forma confiável. Antes de de fato especificar esse protocolo, pode ser útil primeiro tentar transmitir mensagens de forma unidirecional, sem qualquer controle de erros. Essa é a função mais básica do protocolo, pois envole delimitar mensagens enviadas e recebidas.

O enquadramento é uma função do protocolo de enlace responsável por delimitar quadros na interface com a camada física. Deve-se ter em mente que a camada física oferece um serviço de envio e recepção de sequências de bytes sem qualquer estrutura. Cabe à camada de enlace delimitar as unidades de dados de protocolo (PDU) dentro dessas sequências de bytes.

Existe mais de uma abordagem para delimitar quadros (ver mais no capítulo 11 de Data Communications and Computer Networks, de Behoruz Forouzan, e capítulo 5 de Redes de Computadores e a Internet, de James Kurose e Keith Ross):

Abordagem	Descrição	Exemplos
Quadros de tamanho fixo / duração definida	Quadros têm sempre mesmo comprimento ou duração	ATM, TDMA-based
Sentinela	padrão de bits/bytes delimita quadros	PPP, HDLC
Contador / duração	Cabeçalho contém duração ou comprimento do quadro	IEEE 802.11
Presença/ausência de portadora	Ausência de portadora delimita quadros	IEEE 802.11, IEEE 802.3

Modelagem do comportamento

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 de bate-papo, 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 de bate-papo usado como exemplo envolve a comunicação entre múltiplos usuários por meio de um servidor. Seu vocabulário é composto pelas mensagens INICIO, STATUS, DATA. 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 cliente do protocolo de bate-papo

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 de bate-papo, essa tabela poderia ser:

Estado inicial	Ação	Estado final
0	! INICIO	1
1	?STATUS=OK	2
1	?STATUS=Err	0
1	Timeout	0
2	Disconnect	0
2	? DATA	2
2	! DATA	3
3	?STATUS	2
3	Disconnect	0
3	Timeout	0

O tipo de máquina de estados que se usará em projeto de protocolos é do tipo estendida. Com ela se podem modelar sistemas concorrentes que interagem por meio de trocas de mensagens. A comunicação entre MEF desse tipo se faz por meio de canais de comunicação e duas primitivas de comunicação: envio e recepção. A notação para o envio e recepção é mostrado a seguir:

• Envio: o envio é indicado por um rótulo de transição (ou evento) no formato nome_de_canal!mensagem. Ex: canal_tx!123 indica o envio da mensagem 123 por meio do canal canal_tx.
• Recepção: a recepção é indicada por um rótulo de transição (ou evento) no formato nome_de_canal?mensagem. Ex: canal_rx?123 indica a recepção da mensagem 123 por meio do canal canal_rx.

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

1. Escolha uma abordagem viável de enquadramento para o protocolo de enlace a ser desenvolvido
2. Modele a abordagem usando uma máquina de estados finitos estendida, de forma a facilitar sua implementação. Alguns textos introdutórios sobre MEF:
3. Implemente a abordagem escolhida

Implementação do enquadramento

A técnica de enquadramento escolhida é a do tipo sentinela. Mais especificamente, escolheu-se a versão dessa técnica implementada pelo protocolo PPP:

• Usa-se a flag 7E (01111110) como delimitador de quadros
• Usa-se um byte de escape 7D (01111101) para preenchimento de octeto
• O transmissor deve fazer pelo menos o escape dos bytes 7E e 7D que aparecerem no conteúdo do quadro
  • Cada byte que sofrer o escape deve ser modificado por meio de um XOR 20. Ex: se o byte a sofrer escape for 7E, ele deve ser modificado para 5E (7E XOR 20 = 5E).

Uma máquina de estados para o receptor é esta:

Versão alternativa da MEF

Além disso, uma possível implementação dessa função do protocolo poderia ser esta:

#ifndef FRAMING_H
#define FRAMING_H

#include <cstdint>
#include "Serial.h"

class Enquadramento {
 public:
  Enquadramento(Serial & dev, int bytes_min, int bytes_max);
  ~Enquadramento();
 
  // envia o quadro apontado por buffer
  // o tamanho do quadro é dado por bytes 
  void envia(char * buffer, int bytes);
 
  // espera e recebe um quadro, armazenando-o em buffer
  // retorna o tamanho do quadro recebido
  int recebe(char * buffer);
 
 private:
  int min_bytes, max_bytes; // tamanhos mínimo e máximo de quadro
  Serial & porta;  
  char buffer[4096]; // quadros no maximo de 4 kB (hardcoded)
 
  enum Estados {Ocioso, RX, ESC};
 
  // bytes recebidos pela MEF até o momento  
  int n_bytes; 
 
  // estado atual da MEF
  int estado;
 
  // aqui se implementa a máquina de estados de recepção
  // retorna true se reconheceu um quadro completo
  bool handle(char byte);
 
};

#endif

A implementação da máquina de estados

A declaração acima sugere implementar a MEF a partir do método handle da classe Enquadramento. Esse método deve ser executado para cada byte recebido, representando o tratamento de um evento pela MEF. Uma forma usual e direta de implementar uma MEF faz uso de uma estrutura do tipo switch-case. Essa abordagem se baseia em um modelo de programação estruturada. Basicamente ele depende de um algoritmo que executa um procedimento do sistema dependendo de seu estado atual e do evento. A seleção do procedimento se faz com uma estrutura switch-case. O exemplo abaixo mostra o esqueleto de uma MEF implementada usando essa técnica.

// o tratador de eventos de uma MEF hipotética
// A MEF aqui representada nada faz de útil ... 
bool Enquadramento::handle(char byte) {
  switch (estado) {
    case Ocioso: // estado Ocioso
      estado = RX; // muda para RX
      break;
    case RX: // estado RX
      estado = ESC; // muda para ESC
      break;
    case ESC: // estado ESC
      estado = Ocioso; // muda para Ocioso
      break;
  }
}

Atividade

algumas coisas para ajudar

#include <iostream> //#include <iomanip> #include <fstream> #include <stdio.h> #include <errno.h> #include "Enquadramento.h" using namespace std; void dump(char * buffer, int len) { int m = 0, line = 0; while (m < len) { printf("%02X: ", line*16); for (int n=0; n < 16 and m < len; n++, m++) { int x = (unsigned char)buffer[m]; printf("%02X ", x); } puts(""); line++; } } int main(int argc, char * argv[]) { Serial dev("/dev/ttyUSB0", B9600); Enquadramento proto(dev, 8, 32); char quadro[32]; proto.envia("1234567890", 10); // ou: // int bytes = proto.recebe(quadro); // dump(quadro, bytes); } main.cpp para enviar ou receber um único quadro

1. Implemente a MEF de recepção do enquadramento
2. Escreva um programa que transmita pela serial sequências de caracteres como estas:

   ~abcedf1234567~
   ~abcedf}^1234567~
   ~abcedf012}]9876~
   ~}]}^}]}]}]}^}^}^}]}]}]~
   

   ... e use seu programa de recepção para recebê-las pela serial e identificar os quadros recebidos. Use o serialemu para conectar as seriais desses dois programas.
3. Escreva o método envia da classe Enquadramento, e modifique o programa de teste de envio para usá-lo para transmitir sequências arbitrárias de bytes.
4. Teste a capacidade de recuperar o sincronismo da técnica de enquadramento escolhida. Para isso, modifique o programa de teste para que, propositalmente, transmita quadros com erro de delimitação.