Mudanças entre as edições de "PTC-2017-2"
Linha 589: | Linha 589: | ||
== DICA para desenvolvimento do protocolo == | == DICA para desenvolvimento do protocolo == | ||
+ | <!-- | ||
+ | #*# Obtenha o [http://tele.sj.ifsc.edu.br/~msobral/ptc/serialemu.c código-fonte do serialemu] | ||
+ | #*# Compile-o com este comando: <syntaxhighlight lang=bash> | ||
+ | aluno@M2:~$ gcc -o serialemu serialemu.c -lutil -lpthread | ||
+ | </syntaxhighlight> | ||
+ | --> | ||
Para desenvolver o protocolo, há duas opções: | Para desenvolver o protocolo, há duas opções: | ||
# ''Implementá-lo diretamente na plataforma proposta, composta por PC com Linux e Arduino:'' isso envolve implementar o protocolo no Linux e também no Arduino. | # ''Implementá-lo diretamente na plataforma proposta, composta por PC com Linux e Arduino:'' isso envolve implementar o protocolo no Linux e também no Arduino. | ||
# ''Implementar um protótipo no Linux usando um programa emulador de link serial:'' isso faz uso do programa '''serialemu''', que emula um link serial com determinada taxa de bits, BER e atraso de propagação. Para usá-lo deve-se fazer o seguinte: | # ''Implementar um protótipo no Linux usando um programa emulador de link serial:'' isso faz uso do programa '''serialemu''', que emula um link serial com determinada taxa de bits, BER e atraso de propagação. Para usá-lo deve-se fazer o seguinte: | ||
− | #*# Obtenha o [http://tele.sj.ifsc.edu.br/~msobral/ptc/ | + | #*# Obtenha o [http://tele.sj.ifsc.edu.br/~msobral/ptc/Serialemu.zip código-fonte do serialemu] |
+ | #*# Descompacte o arquivo ''Serialemu.zip'', e entre no subdiretório ''Serialemu''. | ||
#*# Compile-o com este comando: <syntaxhighlight lang=bash> | #*# Compile-o com este comando: <syntaxhighlight lang=bash> | ||
− | aluno@M2:~$ | + | aluno@M2:~/Serialemu$ make |
</syntaxhighlight> | </syntaxhighlight> | ||
+ | #*# Copie o programa compilado para algum subdiretório mais conveniente ... por exemplo, ''/home/aluno'', e depois mude para esse subdiretório: <syntaxhighlight lang=bash> | ||
+ | cp dist/Debug/GNU-Linux/serialemu /home/aluno/ | ||
+ | cd /home/aluno | ||
+ | </bash> | ||
#*# Execute-o de forma que ele apresente suas opções de execução: <syntaxhighlight lang=bash> | #*# Execute-o de forma que ele apresente suas opções de execução: <syntaxhighlight lang=bash> | ||
aluno@M2:~$ ./serialemu -h | aluno@M2:~$ ./serialemu -h |
Edição das 14h45min de 25 de agosto de 2017
Projeto de Protocolos: Diário de Aula 2017-2
Professor: Marcelo Maia Sobral
Encontros: 5a feira/9:40, 6a feira/9:40 (Semana A)
Atendimento paralelo: 6a de 8:30 às 9:30 h / 6a de 13:30 às 14:30 h
Referências complementares
- ASN.1
- Internet Standard 68 (ABNF)
- SDL Forum
- RFC-1317: On the Design of Application Protocols
- Protocol Design Beyond Graph-Based Models
- Protocol Design (entrevista)
- Inrodução a C++ (com referências bibliográficas)
Avaliações
As avaliações são de dois tipos:
- Projetos: feitos em equipes de até dois alunos, são desenvolvidos ao longo da disciplina. Os resultados parciais devem ser entregues por meio de relatórios parciais, e o resultado final deve ser demonstrado na prática e descrito em um relatório conclusivo.
- Tarefas: feitas individualmente, e servem para ajustar os conceitos dos projetos (podem aumentá-los ou reduzi-los).
Aluno | Projeto 1 | Projeto 2 | Projeto 3 | FINAL |
---|
Obs: D* = não fez a avaliação.
Softwares
- Compilador ASN.1
- ANTLR (Another Tool for Language Recognition)
- APG (ABNF Parser Generator)
- SPIN Model Checker
27/07: Introdução
- Caracterização de protocolos por meio de um exemplo: sintaxe, comportamento, temporização, semântica. Princípios de projeto e propriedades desejáveis de protocolos. Análise de um protocolo real.
- Projeto 1: um protocolo de comunicação
- Projeto 2: um protocolo de aplicação
- Projeto 3: implementação de um protocolo padrão segundo uma especificação
Um protocolo é uma parte muito importante de um sistema de comunicação. A comunicação de dados pode ser entendida como troca de informação entre dois dispositivos através de algum meio de comunicação. A comunicação ocorre no âmbito de um sistema de telecomunicações, composto por equipamentos (hardware) e programas (softwares). Um sistema básico de comunicação de dados se constitui de cinco componentes:
- A mensagem: a informação a ser transmitida. O conteúdo da mensagem, seja um texto, música, video, ou qualquer outro tipo de informação, é representada por conjuntos de bits (dígitos binários).
- Transmissor: dispositivo que transmite a mensagem.
- Receptor: dispositivo que recebe a mensagem.
- Meio de comunicação: caminho físico por onde viaja a mensagem do transmissor até o receptor.
- Protocolo: conjunto de regras que governa a comunicação de dados.
Os sistemas de comunicação reais, incluídas as redes de computadores, são bem mais complexos do que esse modelo simplificado. No entanto, todos podem ser entendidos, em alguma medida, a partir desse modelo. Nesta disciplina estudam-se princípios e técnicas para projeto de protocolos, incluindo formas de verificar a consistência e correção de seu funcionamento.
Serviço e Protocolo
Um sistema de comunicação provê serviços para as aplicações ou usuários realizarem ações que envolvam a comunicação entre sistemas através de uma rede. Por exemplo, existem serviços para transferência de arquivos, reprodução remota de videos e músicas, execução remota de programas, pesquisa por informação, e muitos outros. O conceito de serviço está relacionado ao de protocolo. Um serviço é provido por entidades que interagem de acordo com um protocolo. Assim, um serviço é um dos elementos envolvidos na especificação de um protocolo. As figuras a seguir mostram a relação entre esses conceitos, primeiro apresentando somente a visão de um serviço para um usuário, e, em seguida, a relação entre serviço e protocolo.
Um serviço visto por um usuário
O serviço provido pelo protocolo
Protocolos reais
Que protocolos existentes despertam suas curiosidades sobre os detalhes de seus projetos ? Identifiquem alguns protocolos, e anotem suas finalidades e características.
Protocolo | Finalidade | Características | |
---|---|---|---|
NTP | Sincronizar os relógios dos computadores ligados a rede. | Utiliza uma versão do algoritmo de Marzullo para determinar o tempo dos servidores corrigindo os efeitos da variação da latência da rede. Utiliza uma hierarquia mestre-escravo onde o servidor envia o horário UTC aos equipamentos da rede, enviando as informações por UDP. | |
FTP | Transferência de arquivos entre máquinas em uma rede TCP/IP | Utiliza um modelo cliente-servidor para a transferência de arquivos em ambas as direções (download e upload) de maneira eficaz. Estabelece duas conexões TCP paralelas: uma para controle (persistente) e outra para dados (não-persistente). Caracteriza-se por ser um protocolo de padrão aberto. | |
SSH | Transferência remota de arquivos criptografados entre duas entidades. | Modelo de comunicação é cliente e servidor, utilizando para geração das chaves públicas o algoritmo RSA. A porta padrão do servidor SSH é a porta 22. | |
TELNET | Fornece as regras básicas para ligar um cliente a um intérprete de comando (servidor). | O protocolo Telnet baseia-se em uma conexão TCP para enviar dados em formato ASCII codificados em 8 bits entre os quais se intercalam sequências de controle Telnet. Ele fornece, assim, um sistema orientado para a comunicação, bidirecional (half-duplex), codificado em 8 bits, fácil de aplicar. | |
SMTP | Usado para a transferência de e-mail | Funciona como roteador do correio eletrônico. É transmitido sobre o protocolo TCP, sendo composto por 3 entidades: Agente do usuário, emissor e receptor. A comunicação entre o emissor e receptor é feita através do código ASCII. | |
RTP | É um protocolo de redes utilizado para entregar áudio e vídeo sobre IP. | É implementado tipicamente sobre UDP e usado em conjunto com o RTCP (RTP Control Protocol). Enquanto o RTP lida com a mídia em sí, o RTCP monitora as estatísticas de transmissão e o Controle de Qualidade e lida com a sincronização de multiplos streams. | |
SSH | Protocolo de rede que estabelece uma conexão criptografada em meio de comunicação não seguro na estrutura cliente-servidor. | O cliente conecta-se ao servidor através de autenticação com troca de chaves (um exemplo de troca de chaves é a de Diffie-Hellman). Ao iniciar a comunicação a autenticação e criptografia são negociados entre as entidades e a comunicação é estabelecida de forma segura, possibilitando o acesso remoto de dispositivos e transferência de arquivos. Implementado sobre o TCP. |
Análise dos protocolos
De acordo com Gerard Holzmann, no capítulo 2 de seu livro Design and Validation of Computer Protocols, um protocolo é composto por cinco elementos:
- O serviço oferecido pelo protocolo
- As considerações sobre o ambiente em que o protocolo é executado
- O vocabulário de mensagens usadas para implementar o protocolo
- A codificação (ou formato) de cada mensagem do vocabulário
- O comportamento, definido por regras de intercâmbio responsáveis pela consistência das trocas de mensagens
Com base nesses elementos, deve-se complementar ou adequar a análise dos protocolos selecionados:
Protocolo | Serviço | Ambiente de execução | Vocabulário | Codificação | Comportamento | |
---|---|---|---|---|---|---|
NTP | Sincronização dos relógios dos computadores ligados a rede. | Usa um canal UDP para intercâmbio de mensagens. Pode perder mensagens. Latências de transmissão variáveis (ex: devido a congestionamentos) podem ocorrer. | NTP Data packet | binária (ver RFC 5905) | Há um bom resumo neste documento. | |
FTP | Transferência de arquivos entre computadores conectados em uma rede. | Usa dois canais TCP paralelos para intercâmbio de de dados de controle e arquivos. Garante confiabilidade, ou seja, entrega do arquivo enquanto protege de erros de transmissão. | Conjunto de comandos: USER, PASS, LIST, STOR, PORT, QUIT. | Textual (ASCII ou EBCDIC) ou binária. ( ver RFC 959) | 1- Cliente realiza conexão de controle (porta 21) com servidor (modo passivo ou ativo). 2- Com a confirmação positiva, servidor mantém a conexão de controle aberta e aguarda as solicitações de transferência. 3- Em modo de execução ativo o servidor inicia a conexão de dados. 4- Em modo de execução passivo o cliente inicia a conexão de dados para iniciar a transferência. | |
SSH | Transferência remota de arquivos criptografados entre duas entidades. (ver RFC 4253) | TCP/IP atuando acima da camada de transporte e por meio da porta 22 | SSH_MSG_USERAUTH_REQUEST, SSH_MSG_USERAUTH_FAILURE, SSH_MSG_USERAUTH_SUCCESS e outras mensagens (ver RFC 4253) | ISO-10646 UTF-8 (ver RFC 3629) | (ver Cisco - Protocol Basics: Secure Shell Protocol) | |
SMTP | Envio de transferência de e-mail | Funciona online, encapsulado em um pacote TCP/IP, por padrão na porta 25. | HELO: Inicia a comunição. Mail from: Endereço do remetente. 250 OK: Confirmação de recebmento. RCPT TO: Endereço do destinatário. DATA: Corpo da mensagem. | ASCII | A lógica de trabalho é quase a mesma utilizada pelo correio convencional, sendo que o SMTP atua praticamente como o carteiro. Após serem capturadas, as mensagens são enviadas para ele que, em seguida, encaminha os e-mails aos destinatários finais. https://blog.saphir.com.br/smtp-o-que-e-e-como-funciona/ | |
TELNET | Permitir obter uma interface de terminais e aplicações pela Internet. | Baseia-se em uma conexão TCP para enviar dados entre os quais se intercalam sequências de controle Telnet. Ele fornece, assim, um sistema orientado para a comunicação, bidirecional (half-duplex). | https://tools.ietf.org/html/rfc854 | Codificado em formato ASCII de 8 bits. | As opções do Telnet afetam separadamente cada direção do canal de dados. Assim, cada extremidade pode negociar com as opções, ou seja, definir as opções desejadas, como utilizar (DO), não utilizar (DON' T), permitir que a outra extremidade utilize (WILL), não permitir que a outra extremidade utilize (WON' T). Desta maneira, cada uma das partes pode emitir um pedido de utilização de uma opção. A outra parte deverá, então, responder se aceita ou não a utilização da opção.
http://br.ccm.net/contents/286-o-protocolo-telnet#qual-e-o-principio-das-opcoes-negociadas | |
RTP | Entrega de áudio e vídeo sobre IP. | implementado sobre canal UDP. Apresenta perda. | RTP Header | Binária. | Overview interessante do protocolo | |
SSH | Protocolo de rede que estabelece uma conexão criptografada em meio de comunicação não seguro na estrutura cliente-servidor. | Utiliza TCP como canal de comunicação. Geralmente utilizado para acesso remoto. | As mensagens possuem suas próprias RFCs e podem ser conferidas no item 10.1 de RFC 4251 | ISO-10646 UTF-8 | Resumo neste documento (em inglês) |
28/07: Diretrizes para projeto de um protocolo
Propriedades desejáveis de um protocolo
Ainda segundo Gerard Holzmann, no capítulo 2 de seu livro Design and Validation of Computer Protocols, um protocolo possui algumas propriedades desejáveis:
- Simplicidade: um protocolo bem estruturado pode ser construído com um pequeno número de partes bem projetadas e bem entendidas.
- Modularidade: um protocolo que realiza uma função complexa pode ser construído com partes menores que interagem de maneira simples e bem definida. Cada parte menor é um protocolo leve que pode ser desenvolvido separadamente, verificado, implementado e mantido.
- Adequação: um protocolo bem formado não é incompleto, nem possui funções que nunca são de fato utilizadas. Um protocolo bem formado se limita aos recursos existentes, além de ser estável e adaptável.
- Robustez: um protocolo robusto deve funcionar bem em condições normais, e também em situações imprevistas. Ele deve conseguir lidar com cada possível sequência de ações, em todas as possíveis condições. Ele deve ter um projeto mínimo, de forma a remover considerações não essenciais que poderiam impedir sua adaptação a condições não antecipadas.
- Consistência: protocolos não devem apresentar interações que os levem a falhar, tais como deadlocks, livelocks e terminações inesperadas.
A figura a seguir mostra a arquitetura do protocolo de enlace PPP como exemplo de simplicidade e modularidade:
Robustez e consistência são aspectos comportamentais do protocolo, que envolvem portanto a dinâmica de seu funcionamento. O comportamento de um protocolo pode ser descrito de algumas formas, sendo usual utilizar diagramas. A figura a seguir apresenta o comportamento em alto-nível do protocolo PPP (mas não significa que dela se possa concluir que ele seja robusto ou consistente):
Diretrizes de projeto
No mesmo capÍtulo 2 de seu livro, Gerard Holzmann enumera dez regras de projeto de um protocolo:
- Definição do problema: certifique-se de que o problema esteja bem definido, com a identificação de todos os critérios de projeto, requisitos e restrições antes de iniciar um projeto.
- Definição do serviço: deve-se definir o serviço a ser realizado em cada nível de abstração antes de decidir que estruturas devem ser usadas para implementá-los (o que vem antes de como).
- Funcionalidades externas primeiro: projete a funcionalidade externa antes da interna. Primeiro considere a solução como uma caixa-preta e decida como ela interage com seu ambiente. Depois decida como a caixa-preta pode ser organizada internamente. Provavelmente isso consiste de caixas-pretas menores que podem ser refinadas de forma similar.
- Mantenha a simplicidade: protocolos extravagantes são mais propensos a ter bugs que protocolos simples. Eles são mais difíceis de implementar, verificar e comumente menos eficientes. Existem poucos problemas realmente complexos em projetos de protocolos. Problemas que aparentam serem complexos costumam ser problemas misturados. A tarefa dos projetistas é identificar os problemas mais simples, separá-los, e então resolvê-los individualmente.
- Preservar independência: não conectar o que for independente, o que significa separar questões ortogonais.
- Mantenha o projeto extensível: não introduza o que for imaterial. Não restrinja o que for irrelevante. Um bom projeto é facilmente extensível, e resolve uma classe de problemas ao invés de uma única instância.
- Crie um protótipo: antes de implementar um projeto, crie um protótipo de alto-nível, e verifique se os critérios do projeto são atingidos.
- Torne-o eficiente: implemente o projeto, meça seu desempenho e, se necessário, otimize-o.
- Verifique a implementação: confira se a implementação final otimizada é equivalente ao protótipo de alto-nível que foi verificado.
- Não pule as regras 1 a 7
TAREFA: um protocolo simples
Uma placa de aquisição de dados possui um conjunto de sensores, cujas medições são realizadas com diferentes frequências. Essa placa envia suas medições para um servidor de armazenamento, que as registra em algum tipo de repositório. O período entre envios da placa é parametrizável, e cada envio de dados pode conter um ou mais valores de medições. Cada medição é composta por uma identificação sobre a grandeza medida, seu timestamp e seu valor. Sendo assim:
1. Especifique o serviço provido pelo protocolo
Exemplo |
---|
|
2. Faça considerações sobre o ambiente de execução do protocolo (ex: o tipo de canal de comunicação usado e suas características)
Exemplo |
---|
|
3. Defina seu vocabulário, e também a codificação de mensagens a ser adotada
Exemplo |
---|
|
4. Descreva seu comportamento
Ao final, implemente esse protocolo usando seus conhecimentos sobre redes de computadores e sistemas distribuídos. OBS:
- o canal de comunicação deve ser baseado em um protocolo de transporte. Isso elimina a possibilidade de usar protocolos de aplicação, tais como HTTP (e, por consequência, implementar algo na fa forma de web service ou coisa parecida)
- as medições devem ser garantidamente entregues no servidor, e sem erros.
A implementação deve ser feita por meio de um protótipo composto por:
- uma emulação da placa de aquisição de dados
- o servidor de coleta de dados
A entrega da especificação e do protocolo implementado deve ser feita até dia 04/08.
03/08: Projeto 1: um protocolo de comunicação
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.
O transceiver RF APC 220
O transceiver RF a ser utilizado se chama APC 220. Alguns documentos podem ser úteis:
Um primeiro experimento
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:
- Configurar dois transceivers RF
- Conectá-los a dois computadores diferentes usando adaptadores USB
- 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.
- Escrever um programa que se comunique por meio dos transceivers. Para isso podem ser úteis:
A serial modelada como uma classe C++ |
---|
#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 */
#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;
}
|
Configuração no VirtualBox
O transceiver deve ser conectado a porta USB do computador. O Linux o reconhece e cria o arquivo de dispositivo /dev/ttyUSB0 a ele associado. Com isso a máquina virtual VirtualBox deve ser configurada da seguinte forma:
- Habilitar a primeira porta serial (COM1)
- O modo dessa serial deve ser Dispositivo no hospedeiro
- O caminho do dispositivo deve ser /dev/ttyUSB0
TAREFA: início do protocolo de enlace
Implemente a delimitação de mensagens do seu protocolo de enlace, de forma que mensagens de tamanho variável possam ser transmitidas e corretamente recebidas. Essas mensagens pode ter entre 8 e 512 bytes. Em seguida, use-as para transmitir um pequeno arquivo através do enlace sem-fio.
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.
10/08: Projeto 1: Sincronização e enquadramento
- Anatomia de um processo em memória no Linux: revisão sobre uso de memória e sua relação com variáveis, objetos e parâmetros em programas C/C++
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 |
Atividade
- Escolha uma abordagem viável para o protocolo de enlace a ser desenvolvido
- Modele a abordagem usando uma máquina de estados finitos de comunicação, de forma a facilitar sua implementação. Alguns textos introdutórios sobre MEF:
- 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:
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
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);
}
|
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;
}
}
algumas coisas prontas para ajudar |
---|
int Enquadramento::recebe(char * buffer_out) {
char byte;
while (true) {
porta.read(&byte, 1);
if (handle(byte)) {
memcpy(buffer_out, buffer, n_bytes);
return n_bytes;
}
}
}
|
11/08: Projeto 1: enquadramento
O tipo de enquadramento escolhido na aula anterior primeiro foi implementado numa plataforma composta por um computador com Linux. O próximo passo é implementá-lo no Arduino, de forma que se consigam transmitir quadros entre Arduino e computador Linux.
A atividade de hoje envolve:
- Integrar o transceiver RF no Arduino, de acordo com este tutorial.
- Implementar o enquadramento no Arduino ... ver referência sobre uso da serial
- Transmitir quadros do Arduino para o computador Linux: esses quadros devem ter comprimento entre 8 e 256 bytes, e conter dados de fácil verificação
- Transmitir quadros do computador Linux para o Arduino
Um programa de teste para receber bytes da serial |
---|
#include <iostream>
#include "Serial.h"
using namespace std;
int main() {
Serial rf("/dev/ttyUSB0", B9600);
char buffer[32];
int c = 0;
while (true) {
n = rf.read(buffer, 32);
cout.write(buffer, n);
c += n;
if (c > 19) {
c = 0;
cout << endl;
}
}
}
|
DICA para desenvolvimento do protocolo
Para desenvolver o protocolo, há duas opções:
- Implementá-lo diretamente na plataforma proposta, composta por PC com Linux e Arduino: isso envolve implementar o protocolo no Linux e também no Arduino.
- Implementar um protótipo no Linux usando um programa emulador de link serial: isso faz uso do programa serialemu, que emula um link serial com determinada taxa de bits, BER e atraso de propagação. Para usá-lo deve-se fazer o seguinte:
- Obtenha o código-fonte do serialemu
- Descompacte o arquivo Serialemu.zip, e entre no subdiretório Serialemu.
- Compile-o com este comando:
aluno@M2:~/Serialemu$ make
- Copie o programa compilado para algum subdiretório mais conveniente ... por exemplo, /home/aluno, e depois mude para esse subdiretório:
cp dist/Debug/GNU-Linux/serialemu /home/aluno/ cd /home/aluno </bash> #*# Execute-o de forma que ele apresente suas opções de execução: <syntaxhighlight lang=bash> 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)
- 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: ... e anote os dois caminhos informados pelo serialemu: eles são as duas portas seriais que correspondem às pontas do link serial emulado.
aluno@M2:~$ ./serialemu -B 9600 /dev/pts/17 /dev/pts/2 aluno@M2:~$
- 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 + Arduino. Assim, o uso do emulador de serial tem por finalidade somente facilitar o desenvolvimento dos mecanismos básicos do protocolo.
17/08: Projeto 1: mecanismos básicos de um protocolo de comunicação
Um protocolo de comunicação pode incorporar um subconjunto de mecanismos elementares para que o serviço seja devidamente provido. Diferentes autores enumeram esses mecanismos, para fins de fácil compreensão. Por exemplo, Georg Holzmann no cap. 2 de Design and Validation of Computer Protocols identifica os seguintes tipos de mecanismos:
- Início e término de intercâmbio de dados
- Sincronização de transmissores e receptores
- Detecção e correção de erros de transmissão
- Formatação e codificação de dados
Mais especificamente, Controle de erros é detalhado no cap. 3 e Controle de fluxo no cap. 4.
Hartmut Konig, no cap. 5 de Protocol Engineering, 2nd ed. identifica estes mecanismos:
- Controle de erros
- Sincronização
- Gerenciamento de conexão
- Codificação e decodificação de PDU
- Ajustes em tamanhos de PDUs
- Sequenciamento
- Controle de fluxo
- Controle de taxa
Outro autor, Robin Sharp, no cap. 4 de Principles of Protocol Design, identifica estes mecanismos:
- Controle de sequência e de erros
- Controle de fluxo
- Indicação de mudança de estado do par
- Mudança de modo de serviço
- Multiplexação e separação
- Segmentação e remontagem
- Priorização
Como se pode notar, essas classificações possuem sobreposições, porém também sensíveis diferenças. Por vezes é questão de nomenclatura, em outras de ênfase em aspectos de um protocolo. No nosso caso, devemos conhecer e entender esses mecanismos para identificar quais deles são úteis para nosso protocolo de comunicação. Para realizar essa análise, antes de mais nada devemos definir o serviço a ser provido por nosso novo protocolo.
Essas funções de protocolo, para melhor entendimento e definição, devem, sempre que possível, ser relacionadas com o conceito de camadas (ver, por exemplo modelo de referência OSI). A figura a seguir resume alguns termos elementares que aparecem em um modelo em camadas (N é o número da camada), sendo eles:
- PDU: unidade de dados do protocolo (coloquialmente: pacote)
- SDU: unidade de dados de serviço (payload, carga do pacote)
- PCI: informações de controle do protocolo (cabeçalho)
- SAP: ponto de acesso a serviço, ou uma identificação usada para requisitar serviços de um protocolo (ex: endereço IP para protocolo IP, port para protocolo TCP)
Definição do protocolo
Especifique seu protocolo, iniciando pelo serviço a ser oferecido. Em seguida, enumere e descreva os mecanismos a serem utilizados para implementar as funções de seu protocolo.
Serviço:
- protocolo de enlace ponto-a-ponto, para camada física do tipo UART
- encapsulamento de mensagens entre 8 e 256 bytes
- recepção de mensagens livres de erros
- garantia de entrega
- controle de acesso ao meio
- conectado (estabelecimento de sessão)
24/08: Projeto 1: controle de erros
- Implementação de Checksum
- Implementação de CRC em software
- Implementação do CRC-16 para PPP (RFC 1662)
- A Painless Guide to CRC Error Detection Algorithms, 3rd Edition por Ross Williams
- Um pequeno resumo sobre CRC (obtido do livro Comunicação de Dados e Redes de Computadores, de William Stallings)
O controle de erros envolve:
- Detecção de erros: cada mensagem recebida deve ter verificada a integridade de seu conteúdo. Mensagens corrompidas devem ser rejeitadas (descartadas)
- Recuperação de erros: mensagens descartadas devido a erros podem ser recuperadas. Existem duas abordagens:
- Correção de erros: mensagens incluem bits de redundância que possibilita, dentro de certos limites, corrigir bits corrompidos.
- Retransmissão: mensagens descartadas são simplesmente retransmitidas
O protocolo de comunicação a ser desenvolvido no projeto 1 deve receber apenas mensagens corretas. Para isso, pelo menos deve ser implementada uma função de detecção de erros.
Detecção de erros
A detecção de erros implica adiciona à mensagem transmitida uma certa quantidade de bits de redundância. Os valores desses bits são determinados com base no conteúdo da mensagem. Na recepção, calcula-se novamente o valor dos bits de redundância e compara-se com os bits de redundância incluídos na mensagem. Se forem iguais, presume-se que mensagem está correta.
Bits de redundância para detecção de erros
A detecção de erros envolve basicamente a escolha de uma dentre duas técnicas:
- Checksum (soma de verificação): os bits de redundância são calculados como uma soma de todos os octetos da mensagem.
- CRC (verificação de redundância cíclica): os bits de redundância são calculados usando uma forma de álgebra polinomial.
Atividade
- Analise e escolha uma das técnicas para detecção de erros para seu protocolo.
- Implemente a técnica escolhida.
Exemplo da classe Enquadramento com métodos para cálculo e verificação de CRC |
---|
#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 {Q0, Q1, Q2};
// 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);
// verifica o CRC do conteúdo contido em "buffer". Os dois últimos
// bytes desse buffer contém o valor de CRC
bool check_crc(char * buffer, int len);
// gera o valor de CRC dos bytes contidos em buffer. O valor de CRC
// é escrito em buffer[len] e buffer[len+1]
void gen_crc(char * buffer, int len);
// calcula o valor de CRC dos bytes contidos em "cp".
// "fcs" deve ter o valor PPPINITFCS16
// O resultado é o valor de CRC (16 bits)
// OBS: adaptado da RFC 1662 (enquadramento no PPP)
uint16_t pppfcs16(uint16_t fcs, char * cp, int len);
};
#endif
|
25/08: Projeto 1: Garantia de entrega no protocolo de enlace
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 ndesta descrição de mecanismos ARQ, incluindo uma análise simplificada de seu desempenho.
Escolha do mecanismo ARQ a ser utilizado no protocolo de enlace
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:
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:
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.
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:
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
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:
![]() |
![]() |
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
O protocolo de comunicação deve ser modelado com uma MEF. Algumas funções do protocolo podem ser convenientemente representadas com MEF, tais como:
- Enquadramento (framing)
- Garantia de entrega (mecanismo ARQ)
- Gerenciamento de conexão
- Controle de acesso ao meio
Tendo como base a garantia de entrega, modele-a com uma MEF. Para isso identifique os componentes da MEF capazes de representar as regras de procedimento dessa função do protocolo: estados, eventos e transições. Em seguida, faça um diagrama da MEF da garantia de entrega.