Understanding Stop & Wait Protocol in Computer Networks

Redes de Computadores Protocolo Stop & Wait Departamento de Inform tica da FCT/UNL 1

Objectivos da lio A Internet n o garante a entrega dos pacotes pois pode perd -los ou entreg -los de forma desordenada Torna-se ent o necess rio encontrar uma forma de transferir dados de forma fi vel entre dois computadores Nesta li o veremos o protocolo mais simples que existe para o realizar o protocolo stop & wait 2

Todas as coisas so difceis antes de se tornarem f ceis Thomas Fuller 3

Hipteses e Objectivo Nos canais, os frames com erros s o recusados pelos mecanismos de controlo de erros e assim os erros s o transformados em perdas (omiss es) A rede tamb m pode introduzir perda de pacotes ou altera o da ordem de entrega dos mesmos A rede pode perder pacotes, mas n o os perde a todos, mais tarde ou mais cedo alguns pacotes v o chegar ao receptor Objectivo: pretende-se transferir dados de forma fi vel e maximizar a taxa de transfer ncia, ou d bito, extremo a extremo 4

Problemas necess rio controlo de erros e controlo de fluxo extremo a extremo. O controlo de erros dever mascarar a perda de pacotes e a sua chegada fora de ordem. O controlo de fluxos dever impedir um emissor demasiado r pido de afogar um receptor lento. Emissor Receptor Tempo 5

Confirmaes de Recepo (ACKs) Emissor Receptor Tempo ACK = Acknowledgement (confirma o ou aviso de recep o = podes continuar) 6

Perda de Pacotes Emissor Receptor Emissor Receptor Tempo Tempo (a) (b) 7

Alarmes Temporizados Emissor Receptor Tempo dura o do alarme alarme A terminologia usada em ingl s nas redes de computadores e nos sistemas distribu dos corresponde ao momento de fim do temporizador do alarme: timeout 8

Anomalias e Alarmes Emissor Receptor Emissor Receptor Tempo dura o do alarme alarme prematuro Duplicado Duplicado 9

Anomalias Conjugadas Emissor Receptor Tempo p1 p1aceite alarme prematuro p1 p1aceite em duplicado p2 p3 p3aceite mas falta p2 10

Problemas ainda mal resolvidos A solu o anterior n o resolve ainda o problema da perda de um ACK, a qual pode conduzir aceita o de um pacote em duplicado O mesmo problema poder ser introduzido por um receptor lento (face ao timeout) a enviar o ACK Um alarme (timeout) mal regulado, muito curto por exemplo, poder conduzir ao mesmo problema Na verdade as velocidades relativas do emissor e receptor podem n o ser constantes, nem conhecidas a priori Note-se que uma dura o de alarme muito elevada, uma solu o simplista, leva a uma recupera o demasiado lenta de uma perda 11

Nmeros de sequncia A solu o consiste em introduzir n meros de sequ ncia nicos para cada pacote. Estes n meros permitem ao receptor distinguir dados esperados, dados repetidos, etc. Tradicionalmente, para se poupar espa o nos cabe alhos, interessa minimizar o n mero de bits a usar. O n mero de sequ ncia pode ent o ser reutilizado ciclicamente desde que n o se introduza confus o caso a ordem das mensagens possa ser trocada Cabe alhos anteriores Cabe alhos dos n veis inferiores C digo opera o N mero de sequ ncia Cabe alho Dados ou payload Payload do datagrama UDP Application data (Payload) 12

Protocolo stop & wait Emissor Receptor Tempo Data1,1 Data1aceite Ack,1 alarme prematuro Data1,1 duplicado ignorado Data2,2 Ack,1 Data2,2 Data2aceite 13

Funcionamento Emissor: Por cada pacote a transmitir, d -lhe um n mero de sequ ncia novo, transmite-o e activa um alarme. Depois: - Se chega um ACK com o n mero de sequ ncia esperado - passa adiante - Se o temporizador dispara reenvia o pacote e activa de novo o alarme - Se chega um ACK com n mero de sequ ncia errado - ignora-o Receptor: Sempre que recebe um pacote: -Envia um ACK do ltimo pacote correctamente recebido. Se o pacote novo guarda-o, sen o ignora-o 14

Correo (Safety) Admitindo que a rede mais tarde ou mais cedo consegue que uma mensagem seja entregue ao receptor, isto , que a rede permite sempre algum progresso mesmo que pequeno: O protocolo garante (tente demonstar): -Que cada pacote corretamente entregue ao receptor -Que esse pacote n o confundido com outro -Que todos os pacotes chegar o ao receptor 15

Regulao dos Alarmes O valor do temporizador do alarme (timeout) importante para a recupera o de erros Um valor demasiado grande leva a que o emissor seja lento a recuperar dos erros Um valor demasiado curto leva a duplicados in teis Em qualquer caso a corre o n o est em causa desde que se use sempre um alarme e o receptor envie sistematicamente um ACK perante todos os pacotes recebidos, maus ou bons Para evitar repeti es in teis o valor pode ser folgado poss vel tentar estimar um valor mais adequado Pense como 16

Desempenho sem Erros Dois computadores A e B ligados por um canal directo com 10.000 Km de comprimento e o d bito de 1 Mpbs Pacotes com 1.000 bytes Ignoram-se os bits dos cabe alhos Ignora-se o tempo de transmiss o de um ACK Ignora-se o tempo de processamento Tempo de propaga o = 10.000 / 200.000 = 50 ms, RTT = 100 ms 1000 bytes = 8.000 bits = 8 . 103 Tempo de transmiss o = 8 . 103/ 106= 8 ms Quanto tempo leva o emissor a colocar cada pacote no receptor ? Qual a diferen a para um protocolo em que o emissor estivesse sempre a emitir? 17

Desempenho do Protocolo Stop & Wait Emissor Receptor TT Data TT= tempo de transmiss o TP Total = TT + 2 x TP TP= tempo de propaga o TP Ack tempo Cada pacote leva 8 ms a transmitir, mas em cada ciclo de 108 ms apenas se transmite um pacote 1.000 pacotes levam 108 segundos a transferir ao inv s de 8 segundos O desempenho real 8/108 7,4% do m ximo te rico 18

Taxa de Utilizao do Canal Tu= Tt/ (Tt+ 2 x Tp) ou Tu= Tt/ (Tt+ RTT) Tu- taxa de utiliza o Tt- tempo de transmiss o de uma mensagem, Tp- tempo de propaga o de extremo a extremo RTT - tempo de ida e volta (2 x TP) 19

Dbito, RTT e Taxa de Utilizao Taxa de utiliza o de um canal pelo protocolo stop & wait numa transfer ncia entre dois computadores ligados directamente por um canal sem erros, usando pacotes de 10.000 bits, variando o d bito e o RTT. Taxa Utiliza o D bito (Mbps) TT RTT (ms) Coment rios (ms) 99% 1 10 0,1 D bito baixo, RTT desprez vel 50% 100 0,1 0,1 D bito razo vel, RTT desprez vel 33% 1 10 20 D bito baixo, RTT baixo 0,5% 100 0,1 20 D bito razo vel, RTT baixo 4,8% 1 10 200 D bito baixo, RTT alto 0,05% 100 0,1 200 D bito razo vel, RTT alto 0,005% 1000 0,01 200 D bito alto, RTT alto 20

Canais de Dbito Elevado Quando os canais t m d bito muito elevado, o tempo de transmiss o diminui drasticamente. Por exemplo, se um canal tem a capacidade de 1 Gbps, transmitir 10.000 bits leva 10-5segundos, isto , 10 micro segundos Se o RTT for de alguns milissegundos, a taxa de utiliza o do canal tende sempre para valores muito baixos. Nestes casos, o d bito til m dio extremo a extremo permitido pelo protocolo tende para: D bito til m dio extremo a extremo do protocolo S&W = Dimens o do pacote / RTT O d bito til extremo a extremo diz-se goodput em ingl s 21

Mquinas de Estados com Aces Evento1/ [ Condi o1] Evento3/ [ Condi o3] A es1 A es3 Estado 0 (inicial) Estado 1 Evento6/ [ Condi o6] Evento2/ [ Condi o2] Evento4/ [ Condi o4] A es6 A es2 A es4 Estado 2 Estado 3 Evento5/ [ Condi o5] A es5

Mquinas de Estados com Aces Emissor Stop & Wait got Data from application { packet.opCode = Data; packet.sequence = seq; send(packet); startTimer(duration); } got any other event {} got timeout { send(packet); startTimer(duration); } State 0 State 1 initialize seq got Acki&& i == seq got any other event { stopTimer(); seq ++; } {}

Mquinas de Estados com Aces Receptor Stop & Wait got packet Datai got any other event { if ( i == seq ) { deliver Datai sendAck(i) seq++ } else { sendAck(i-1) } } {} State 0 initialize seq

Concluses Mesmo que um canal ou a Internet tenham erros e perdam pacotes poss vel realizar um protocolo de transfer ncia fi vel de dados nos extremos Acab mos de ver um, tamb m conhecido por stop & wait Infelizmente tem um desempenho fraco quando o tempo de tr nsito extremo a extremo significativo face ao tempo de transmiss o O emissor avan a ao ritmo permitido pelo RTT, pois O receptor n o pode emitir um novo pacote enquanto n o chegar o ACK do ltimo pacote emitido 25