02 - Estrutura de Protocolos

Projeto e Validao de Protocolos

Projeto e Validao de Protocolos para Computadores Estrutura de ProtocolosPedro Frosi Rosa, PhD [email protected]

All rights reserved to Pedro Frosi Rosa, PhD

1


Estrutura de um Protocolo

Primeira aula foram abordados alguns problemas relacionados ao projeto de protocolos Dois tipos de erros so muito dificeis de evitar: Projetar um conjunto incompleto de regras Projetar regras que so contraditrias Nesta aula vamos ver modos de garantir que um conjunto de regras , ao mesmo tempo, completo e consistente Ser preciso na especificao Modularidade e Estrutura


2


Caso Tpico

Servidor de Arquivo e Servidor de Impresso

d

Servidor A

Servidor B

p


3


Estrutura bsica

Todas as regras, formatos e procedimentos acordado entre A e B so o protocolo O protocolo formaliza as interaes padronizando o uso do canal de comunicao O protocolo, portanto, pode conter acordos sobre os mtodos usados para: Iniciao e terminao das trocas de dados Sincronizao entre transmisso e recepo Formatao e codificao dos dados Estas fases podem ser definidas em mais de um nvel de abstrao4



Exemplos de nveis de abstrao

Formataosinais eltricos

bits smbolos/caracteres

campos da primitiva quadro/pacote


5


Os elementos de um protocolo

A especificao consiste de cinco partes distintas. Para ser completa, cada especificao deve incluir: Servios a serem oferecidos pelo protocolo Definio do ambiente no qual o protocolo ser executado Vocabulrio das primitivas usadas para implementar o protocolo Codificao (formato) de cada primitiva no vocabulrio Regras procedimentais para garantir a consistncia nas trocas de primitivas O ltimo elemento da especificao do protocolo o mais dificil de projetar e o mais complicado de verificar6



Um exemplo

Especificao do servio O propsito do protocolo transferir arquivos de texto como uma sequncia de caracteres atravs de uma linha telefnica durante o qual protege contra erros de transmisso, assumindo que todos os erros podem ser detectados O protocolo transferncia de arquivo num canal fullduplex Acks e Nacks so enviados pelo canal (B->A) em reconhecimento s transmisses de A->B, e vice-versa Cada primitiva tem duas partes: mensagens e controle no sentido inverso7



Um exemplo.

O Ambiente... Consiste minimamente de dois usurios do servio de transferncia de arquivo e um canal de transmisso O usurios submetem uma requisio para transferncia de arquivo e esperam at a sua concluso O canal de transmisso pode causar distores arbitrrias nas primitivas, mas, no perde, no duplica, no insere e nem reorganiza primitivas Assume-se que um nvel inferior ser responsvel por corrigir distores e gerar mensagens de erros


8


Um exemplo..

Vocabulrio Define trs tipos de mensagens Ack: para reconhecimento positivo Nack: para reconhecimento negativo Err: para primitivas de erro V={Ack,Nack,Err} Cada tipo de primitiva pode posteriormente ser refinada em vrias mensagens de nveis inferiores


9


Um exemplo...

Formato da primitiva Campo de controle: identifica o tipo da primitiva Campo de dados: conjunto de cdigos de caracteresControle Dados

Em uma representao C-like ter-se-a: enum control {Ack,Nack,Err}; struct primitiva {

enum control tag; unsigned char data; };10



Um exemplo....

Regras procedimentais Para este protocolo foram informalmente descritas como: 1. Se a recepo anterior foi livre de erro, a prxima mensagem no sentido contrrio levar um ACK; Caso contrrio levar um NACK 2. Se a recepo anterior foi um NACK, ou foi uma primitiva de ERR, retransmite a primitiva antiga; qualquer outro caso procure por uma nova primitiva para transmisso Para formalizar estas regras podemos usar diagramas de estado, expresses algbricas, descrio na forma de programa, etc11



Um exemplo.....next:o receive Nack:i

Ack:i next:o

Err:i

Ack:o

Ack:o

Nack:o


12


Um exemplo......

Falhas do Projeto Transmisso de dados em um sentido s pode comear se houve uma transmisso de dados no sentido contrrio Quem decide como o canal vai ser iniciado ou encerrado? Maior deficincia: O receptor deve decidir se ou no um dado, que foi recebido corretamente, e armazenado temporariamente na varivel i, deve ser aceito (por ex. salvo em um arquivo) Dados duplicados recebidos corretamente, no deveriam ser aceitos. Este problema no tem soluo pelas regras procedimentais listadas no protocolo13



Um exemplo.......

Vejamos o que acontece com os dois processos abaixo: 1. Processo A inicia a transferncia enviando deliberadamente uma mensagem de erro para B 2. Suponha-se que A tenta transmitir letras de a a z e B responde enviando na ordem inversa O diagrama da prxima figura mostra a sequncia de eventos que leva a uma duplicidade ser aceita como correta


14


Um exemplo........

Diagrama de Ordem TemporalA next accept z err nack z ack a => err nack z => err nack a B next

ack z accept z

accept a


15


Um exemplo.........

O protocolo deste muito simples A descrio informal convicente, sendo que baseados nesta descrio poucos duvidariam da correteza dele A especificao incompleta, e, qualquer implementao baseada nela resultariam em erros subtos durante a troca de dados Este exemplo mostra-nos que mesmo o mais simples dos protocolos exige uma boa disciplina de projeto e ferramentas analticas eficazes


16


Servio e Ambiente

Para completar uma tarefa abstrata como transferir um arquivo, um protocolo deve efetuar um leque de funes de baixo-nvel tais como sincronizao e recuperao de erro A realizao de um servio especfico depende de certas consideraes feitas sobre o ambiente no qual o protocolo executado Por exemplo: recuperao de erro deve corrigir o comportamento oferecido pelo meio de transmisso Tipos de comportamentos sero abordados oportunamente Neste curso vamos nos concentrar na estrutura adequada para a especificao dos servios17



Servio e Ambiente.

Se um problema muito grande para ser abordado de uma vez; ele deve ser quebrado em problemas menores... Muitas funes abstratas so definidas e implementadas em termos de contrutores subjacentes, onde cada nvel esconde certas propriedades indesejveis do canal de comunicao, transformando-o em um meio mais idealizado Por exemplo, considere que queremos implementar um protocolo para transmisso de dados que oferece codificao de caracteres em tuplas de 7 bits cada, e um rudimentar detector de erro baseado em paridade Este protocolo prov dois servios: codificao e deteco de erros18



Servio e Ambiente..

Pode-se separar estes servios em dois mdulos funcionais, chamados sequencialmente, construindo um canal virtual

P2

P1

P1

P2

De fato, cada camada oferece um servio diferente e implementa um protocolo separado A primeira camada implementa P1 => formato 8 bits A segunda camada implementa P2 => formato 7 bits19



Servio e Ambiente...

P2 no v e nada sabe sobre o 8 bit adicionado e controlado por P1 A nica coisa que ele sabe que o canal mais confivel do que diretamente sobre o meio P1 oferece um canal virtual para P2, mas, ao mesmo tempo, ele transparente para P2 Dois conceitos fundamentais em protocolo: Transparente: alguma coisa que existe, mas parece no existir Virtual: alguma coisa que parece existir, mas no existe de fato20



Servio e Ambiente....

Para P1, o significado dos bits no importa - apenas o nmero de bits; de modo similar nem P1, nem P2, conhece qualquer coisa a respeito do protocolo de nvel superior, ie.encapsulamento de n nveis Pn P2 P1 P0 P1 P2 Pn

Cada nvel encerra os dados transmitidos em uma nova capsula, consistindo de um header e/ou trailer, antes de pass-lo a um prximo nvel O formato de nveis superiores no precisam ser preservados21



Servio e Ambiente.....

O princpio de projeto hierrquico bem conhecido em programao sequencial, mas relativamente novo em sistemas distribudos Camadas ajudam a indicar a estrutura lgica do protocolo separando detalhes de alto-nvel dos de baixo-nvel Quando o protocolo muda ou deve ser estendido fcil reescrev-lo ou troc-lo No incio dos anos 70, a ISO reconheceu a necessidade de padronizao e criou o modelo OSI baseado em camadas....


22


Servio e Ambiente......

Cada camada define um conjunto de servios distinto e implementa protocolos especficos camada O formato usado por uma camada completamente independente dos formatos usados pelas demais camadas Exemplo: Camada de rede envia pacotes; Camada de enlace envia framesn+1 Servio primtiva protocolo

n

A

B interface

n-1

provedor de servio


23


Vocabulrio e Formato..

Cabealhos e Trailers Com os mtodos de estruturao descritos anteriormente, mtodos de formatao de dados de alto nvel mais sistemticos podem ser construdos At este momento foi silenciado a respeito de erros de transmisso Se o contador perdido, ou, Se o caracter ETX, ou DLE, for corrompido, estas tcnicas falham

Como veremos adiante, esquemas de deteco de erro requerem transmisso de informaes redundantes Se controle de fluxo, campo com nmero de sequncia...All rights reserved to Pedro Frosi Rosa, PhD

26


Vocabulrio e Formato...

Todo este overhead justificvel e deve ser agrupado em pores diferentes da primitiva, encapsulando os dados: Deste modo, o STX expandido para ser a estrutura do cabealho ETX incrementado para ser o Trailer Por razes bvias contadores de byte so colocados no Cabealho e checksums so colocados nos trailers O formato das primitivas so portanto definidas com um conjunto ordenado de trs elementos: formato = { header , dados , trailer }


27


Vocabulrio e Formato....

O cabealho e o trailer podem ser refinados em subconjuntos ordenados chamados campos de controle. Exemplos: cabealho = { tipo , destino , janela , contador , prioridade } trailer = { checksum , endereo de retorno }STX cabealho dados trailer ETX

tipo ; dest ; seqnr ; count

checksum ; ret addr


28


Regras Procedimentais

Viu-se at este momento grande similaridade entre as tarefas de projeto de protocolo e o desenvolvimento de software Uma diferena importante que as regras procedimentais (procedure rules) so interpretadas paralelamente por dois ou mais mdulos (muito provavelmente em maquinas diferentes) O efeito de cada nova regra adicionada ao conjunto frequentemente muito maior do que se possa imaginar Para se convencer da corretude do projeto necessrio alguma coisa melhor do que a reflexo informal Infelizmente a ferramenta mais popular para isto o Diagrama de Ordem TemporalAll rights reserved to Pedro Frosi Rosa, PhD

29


Projeto Estruturado de Protocolos

Projeto de protocolos toca em vrias reas Algumas destas reas so bem conhecidas Outras estamos somente no comeo do entendimento Por ex., o nvel fsico do modelo OSI/ISO: Conhece-se precisamente qual o comportamento caracterstico dos diferentes tipos de informao que so levados Quo rpido pode-se transmitir dados neles Qual a taxa mdia de bit error resultante H vrias tcnicas para codificao binria em sinais analgicos Conhece-se bem tcnicas de sincronizao sender/receiver30



Projeto Estruturado de Protocolos.

Bem mais acima depara-se com problemas de projeto de rede Roteamento atravs de redes Dimensionamento preciso da estrutura de redes Interconexo de vrias redes via gateways Desenvolvimento em um nvel superior de disciplinas para controle e avoidance de congestionamento Notamos que para a parte fsica existem vrias tcnicas que podem resolver problemas de projeto, contudo os problemas esto apenas comeando: divisar conjunto de regras completas e no ambguas para troca de informao em um sistema distribudo31



Projeto de protocolos: Simplicidade

Caso para protocolos Light-weight Um protocolo bem estruturado pode ser feito a partir de um pequeno nmero de pedaos bem projetados e bem conhecidos Para entender o protocolo basta entender os pedaos Protocolos feitos deste modo so mais fceis de entender, de implementar, mais apropriados para verificar e manter Um protocolo Light-weight simples, robusto e eficiente


32


Projeto de protocolos: Modularidade

Hierarquia de Funes Um protocolo que executa uma funo complexa pode ser feito de pedaos que interagem de um modo simples e bem definido Cada mdulo, um pedao, um protocolo light weight Funes ortogonais no podem ser misturadas, elas so projetadas como entidades independentes Cada mdulo individualmente no faz suposies sobre o trabalho de outros, nem mesmo a presena Controle de erro e controle de fluxo so funes ortogonais


33


Projeto de protocolos: Protocolos Bem Formados

Um protocolo bem formado NO : Over-specified: no h regras no alcanveis ou no utilizadas Under-specified: ou incompleto, ie, durante sua execuo podem ser requeridas regras que levaro a uma recepo indefinida Bounded: no pode ultrapassar limites definidos do sistema (ambiente), como capacidade da fila de mensagens Self-stabilizing: quando erro arbitrrio muda o estado do protocolo, este deve retornar a um estado conhecido Self-adapting: pode se adaptar em certas circunstncias34



Projeto de protocolos: Robustez

Como disse Polybius: It is chiefly unexpected occurrences which require instant consideration and help. No difcil projetar protocolos que trabalham em circunstncias normais o inesperado que torna o projeto um desafio, ie, o protocolo deve ser preparado para tratar apropriadamente todas as aes que ocorram, em qualquer sequncia, sob quaisquer condies O protocolo deve fazer suposies mnimas sobre o ambiente para evitar dependncias de caractersticas que mudem35



Projeto de protocolos: Consistncia

Existem alguns modos padronizados e temidos nos quais um protocolo pode falhar: Deadlocks: situao na qual no haver um prximo estado Livelocks: sequncias na execuo, repetidas indefinidamente, sem fazer qualquer progresso No k-limited: SM no finita No reinicivel: no possvel a partir de um dado estado voltar ao estado inicial Terminao imprpria: finalizao sem satisfazer as condies apropriadas de encerramento36



Regras de ouro de projeto

So 10, sendo que justamente a 10 a mais importante: 1. Certificar-se que o problema foi bem especificado 2. Definir os servios em cada nvel de abstrao 3. Delinear as funcionalidades externas antes das internas 4. Manter o projeto simples 5. No ligar o que independente, que tem ortogonalidade 6. No introduzir o que no concreto; no restringir o que irrelevante; um bom projeto open-ended; um projeto resolve uma classe de problemas 7. Antes de implementar, faa um prottipo de alto-nvel, e verifique que os critrios de projeto foram alcanados37



Regras de ouro de projeto.8. Implementar o projeto, medir seu desempenho, e se necessrio, otimiz-lo 9. Garantir que a implementao final, otimizada, equivalente ao projeto de alto-nvel que foi verificado 10. A mais importante; No pular as regras de 1 a 7

A regra mais violada esta dcima


38


Entidades de Padronizao

Muitos grupos de padronizao, em vrias literaturas referenciados como corpos, esto em atividade na rea de comunicao de dados. Exemplos: NIST (national institute for science and technology) (NBS) FTSC (federal telecommunications standard committee) IEEE (institute of electrical and electronics engineers) ISO (international standardzation organization) CCITT (comit consultatif international tlgraphique et tlphonique) que hoje parte da ITU (international telecommunications union)


39


Entidades de Padronizao...

A ISO inclui muitos protocolos nacionais, como da ANSI (american national standards institute) Organizao da ISOISO TC TC97 SC6 WG1 WG SC TC TC97 - padres para computadores SC6 - telecomunicao WG1 - protocolos para enlaces de dados

Protocolo ASCII referenciado como ISO standard 64640



Entidades de Padronizao....

CCITT uma entidade nacional Francesa, formada em 1956 pela unio de duas entidades CCIT (telegrfica) e CCIF (telefnica)CCITT SG SGVII WP2 WP SG SGVII - redes de comunicao de dados WP2 - interfaces de rede

IFIP (International Federation for Information Processing), embora no seja diretamente ligada padronizao de protocolos41



Entidades de Padronizao.....

Certamente a padronizao, em si mesma, no resolve todos os problemas envolvidos no projeto de protocolos Quo bom um padro internacional que seja incompleto ou at mesmo com erros? O grupos de padronizao se deparam com os mesmos problemas Para tanto existem mtodos para projetar e descrever protocolos, e, ainda, mtodos eficientes para testar protocolos submetidos s entidades de padronizao ESTELLE SDL Redes de Petri42


Documents

02 - Estrutura de Protocolos