Protocolo de janela deslizante - Sliding window protocol
Um protocolo de janela deslizante é um recurso dos protocolos de transmissão de dados baseados em pacotes . Os protocolos de janela deslizante são usados onde a entrega confiável de pacotes é necessária, como na camada de enlace de dados ( camada 2 do OSI ), bem como no protocolo de controle de transmissão (TCP). Eles também são usados para melhorar a eficiência quando o canal pode incluir alta latência .
Os sistemas baseados em pacotes baseiam-se na ideia de enviar um lote de dados, o pacote , junto com dados adicionais que permitem ao receptor garantir que foram recebidos corretamente, talvez uma soma de verificação . O paradigma é semelhante a uma janela que desliza para o lado para permitir a entrada de novos pacotes e rejeitar os que já foram confirmados. Quando o receptor verifica os dados, ele envia um sinal de confirmação , ou "ACK", de volta ao remetente para indicar que ele pode enviar o próximo pacote. Em um protocolo simples de solicitação de repetição automática (ARQ), o remetente para após cada pacote e espera que o receptor faça o ACK. Isso garante que os pacotes cheguem na ordem correta, pois apenas um pode ser enviado por vez.
O tempo que leva para o sinal ACK ser recebido pode representar uma quantidade significativa de tempo em comparação com o tempo necessário para enviar o pacote. Nesse caso, a taxa de transferência geral pode ser muito menor do que teoricamente possível. Para resolver isso, os protocolos de janela deslizante permitem que um número selecionado de pacotes, a janela , seja enviado sem ter que esperar por um ACK. Cada pacote recebe um número de sequência e os ACKs enviam de volta esse número. O protocolo rastreia quais pacotes foram aceitos e, quando eles são recebidos, envia mais pacotes. Dessa forma, a janela desliza ao longo do fluxo de pacotes que constituem a transferência.
As janelas deslizantes são uma parte fundamental de muitos protocolos. É uma parte fundamental do protocolo TCP, que permite inerentemente os pacotes chegarem fora de ordem e também é encontrado em muitos protocolos de transferência de arquivos como UUCP-g e ZMODEM como uma forma de melhorar a eficiência em comparação com protocolos sem janela como XMODEM .
Conceito básico
Conceitualmente, cada parte da transmissão (pacotes na maioria das camadas de enlace de dados, mas bytes no TCP) recebe um número de sequência consecutivo exclusivo e o receptor usa os números para colocar os pacotes recebidos na ordem correta, descartando os pacotes duplicados e identificando os que faltam . O problema com isso é que não há limite para o tamanho do número de sequência que pode ser necessário.
Ao colocar limites no número de pacotes que podem ser transmitidos ou recebidos a qualquer momento, um protocolo de janela deslizante permite que um número ilimitado de pacotes seja comunicado usando números de sequência de tamanho fixo. O termo "janela" no lado do transmissor representa o limite lógico do número total de pacotes ainda a serem confirmados pelo receptor. O receptor informa ao transmissor em cada pacote de confirmação o tamanho máximo atual do buffer do receptor (limite da janela). O cabeçalho TCP usa um campo de 16 bits para relatar o tamanho da janela do receptor ao remetente. Portanto, a maior janela que pode ser usada é 2 16 = 64 kilobytes.
No modo de inicialização lenta, o transmissor começa com uma contagem baixa de pacotes e aumenta o número de pacotes em cada transmissão após receber pacotes de confirmação do receptor. Para cada pacote de confirmação recebido, a janela desliza por um pacote (logicamente) para transmitir um novo pacote. Quando o limite da janela é atingido, o transmissor envia um pacote para um pacote de confirmação recebido.
Se o limite da janela for de 10 pacotes, então no modo de início lento, o transmissor pode começar a transmitir um pacote seguido por dois pacotes (antes de transmitir dois pacotes, um pacote ack deve ser recebido), seguido por três pacotes e assim por diante até 10 pacotes. Mas depois de atingir 10 pacotes, as transmissões adicionais são restritas a um pacote transmitido para um pacote de confirmação recebido. Em uma simulação, parece que a janela está se movendo por uma distância de pacote para cada pacote de confirmação recebido. No lado do receptor, a janela também move um pacote para cada pacote recebido.
O método da janela deslizante garante que o congestionamento de tráfego na rede seja evitado. A camada de aplicação ainda estará oferecendo dados para transmissão ao TCP sem se preocupar com os problemas de congestionamento do tráfego da rede, já que o TCP no remetente e no receptor implementa janelas deslizantes de buffer de pacote. O tamanho da janela pode variar dinamicamente dependendo do tráfego da rede.
Para obter a maior taxa de transferência possível , é importante que o transmissor não seja forçado a interromper o envio pelo protocolo de janela deslizante antes de um tempo de retardo de ida e volta (RTT). O limite da quantidade de dados que ele pode enviar antes de parar para aguardar uma confirmação deve ser maior do que o produto de atraso da largura de banda do link de comunicação. Se não for, o protocolo limitará a largura de banda efetiva do link.
Motivação
Em qualquer protocolo de comunicação baseado em solicitação de repetição automática para controle de erros , o receptor deve reconhecer os pacotes recebidos. Se o transmissor não receber uma confirmação dentro de um tempo razoável, ele reenvia os dados.
Um transmissor que não obtém uma confirmação não pode saber se o receptor realmente recebeu o pacote; pode ser que tenha sido perdido ou danificado na transmissão. Se o mecanismo de detecção de erros revelar corrupção, o pacote será ignorado pelo receptor e uma confirmação negativa ou duplicada será enviada pelo receptor. O receptor também pode ser configurado para não enviar qualquer confirmação. Da mesma forma, o receptor geralmente não tem certeza se suas confirmações estão sendo recebidas. Pode ser que uma confirmação foi enviada, mas foi perdida ou corrompida no meio de transmissão. Nesse caso, o receptor deve reconhecer a retransmissão para evitar que os dados sejam continuamente reenviados, mas, caso contrário, deve ignorá-los.
Operação de protocolo
O transmissor e o receptor têm, cada um, um número de sequência atual n t e n r , respectivamente. Cada um deles também tem um tamanho de janela w t e w r . Os tamanhos das janelas podem variar, mas em implementações mais simples eles são fixos. O tamanho da janela deve ser maior que zero para que qualquer progresso seja feito.
Como normalmente implementado, n t é o próximo pacote a ser transmitido, ou seja, o número de seqüência do primeiro pacote ainda não transmitido. Da mesma forma, n r é o primeiro pacote ainda não recebido. Ambos os números aumentam monotonicamente com o tempo; eles apenas aumentam.
O receptor também pode rastrear o número de sequência mais alto já recebido; a variável n s é um a mais que o número de seqüência do maior número de seqüência recebido. Para receptores simples que aceitam apenas pacotes em ordem ( w r = 1), é o mesmo que n r , mas pode ser maior se w r > 1. Observe a distinção: todos os pacotes abaixo de n r foram recebidos, nenhum pacote acima n s foram recebidos, e entre n r e n s , alguns pacotes foram recebidos.
Quando o receptor recebe um pacote, ele atualiza suas variáveis apropriadamente e transmite uma confirmação com o novo n r . O transmissor rastreia a confirmação mais alta que recebeu n a . O transmissor sabe que todos os pacotes até, mas não incluindo n a , foram recebidos, mas não tem certeza sobre os pacotes entre n a e n s ; ou seja, n a ≤ n r ≤ n s .
Os números de sequência sempre obedecem à regra de que n a ≤ n r ≤ n s ≤ n t ≤ n a + w t . Isso é:
- n a ≤ n r : O maior reconhecimento recebido pelo transmissor não pode ser maior do que o maior n r reconhecido pelo receptor.
- n r ≤ n s : O intervalo de pacotes totalmente recebidos não pode se estender além do final dos pacotes parcialmente recebidos.
- n s ≤ n t : O maior pacote recebido não pode ser maior que o maior pacote enviado.
- n t ≤ n a + w t : O maior pacote enviado é limitado pela maior confirmação recebida e pelo tamanho da janela de transmissão.
Operação do transmissor
Sempre que o transmissor tem dados para enviar, ele pode transmitir até w t pacotes antes da última confirmação n a . Ou seja, ele pode transmitir o número do pacote n t desde que n t < n a + w t .
Na ausência de um erro de comunicação, o transmissor logo recebe uma confirmação de todos os pacotes que enviou, deixando n a igual a n t . Se isso não acontecer após um atraso razoável, o transmissor deve retransmitir os pacotes entre n a e n t .
As técnicas para definir "atraso razoável" podem ser extremamente elaboradas, mas afetam apenas a eficiência; a confiabilidade básica do protocolo de janela deslizante não depende dos detalhes.
Operação do receptor
Cada vez que um pacote numerado x é recebido, o receptor verifica se ele cai na janela de recepção, n r ≤ x < n r + w r . (Os receptores mais simples só precisam rastrear um valor n r = n s .) Se cair dentro da janela, o receptor o aceita. Se for numerado n r , o número da sequência de recebimento é aumentado em 1 e, possivelmente, mais se outros pacotes consecutivos foram recebidos e armazenados anteriormente. Se x > n r , o pacote é armazenado até que todos os pacotes anteriores tenham sido recebidos. Se x ≥ n s , o último é atualizado para n s = x +1.
Se o número do pacote não estiver na janela de recepção, o receptor o descarta e não modifica n r ou n s .
Quer o pacote tenha sido aceito ou não, o receptor transmite uma confirmação contendo o n r atual . (A confirmação também pode incluir informações sobre pacotes adicionais recebidos entre n r ou n s , mas isso só ajuda a eficiência.)
Observe que não adianta ter a janela de recepção w r maior do que a janela de transmissão w t , porque não há necessidade de se preocupar em receber um pacote que nunca será transmitido; o intervalo útil é 1 ≤ w r ≤ w t .
Intervalo de número de sequência obrigatório
Até agora, o protocolo foi descrito como se os números de sequência fossem de tamanho ilimitado, sempre crescente. No entanto, em vez de transmitir o número de seqüência completo x em mensagens, é possível transmitir apenas x mod N , para alguns N finitos . ( N geralmente é uma potência de 2. )
Por exemplo, o transmissor só receberá confirmações na faixa de n a a n t , inclusive. Uma vez que garante que n t - n a ≤ w t , há no máximo w t +1 números de sequência possíveis que podem chegar a qualquer momento. Assim, o transmissor pode decodificar inequivocamente o número de sequência, desde que N > w t .
Uma restrição mais forte é imposta pelo receptor. A operação do protocolo depende do receptor ser capaz de distinguir de forma confiável novos pacotes (que devem ser aceitos e processados) de retransmissões de pacotes antigos (que devem ser descartados e a última confirmação retransmitida). Isso pode ser feito com o conhecimento do tamanho da janela do transmissor. Depois de receber um pacote com o número x , o receptor sabe que x < n a + w t , então n a > x - w t . Assim, os pacotes numerados x - w t nunca mais serão retransmitidos.
O menor número de sequência que receberemos no futuro é n s - w t
O receptor também sabe que o transmissor do n um não pode ser maior do que o mais alto reconhecimento já enviou, que é n r . Portanto, o maior número de sequência que poderíamos ver é n r + w t ≤ n s + w t .
Assim, há 2 w t números de sequência diferentes que o receptor pode receber em qualquer uma vez. Portanto, pode parecer que devemos ter N ≥ 2 w t . No entanto, o limite real é menor.
O insight adicional é que o receptor não precisa distinguir entre números de sequência que são muito baixos (menores que n r ) ou que são muito altos (maiores ou iguais a n s + w r ). Em ambos os casos, o receptor ignora o pacote, exceto para retransmitir uma confirmação. Assim, é necessário apenas que N ≥ w t + w r . Como é comum ter w r < w t (por exemplo, ver Go-Back-N abaixo), isso pode permitir um w t maior dentro de um N fixo .
Exemplos
A janela deslizante mais simples: pare e espere
Embora comumente distinto do protocolo de janela deslizante, o protocolo ARQ stop-and-wait é, na verdade, a implementação mais simples possível dele. A janela de transmissão é de 1 pacote e a janela de recepção é de 1 pacote. Assim, N = 2 números de sequência possíveis (convenientemente representados por um único bit ) são necessários.
Exemplo de ambigüidade
O transmissor envia alternadamente pacotes marcados como "ímpar" e "par". Os agradecimentos também dizem "ímpar" e "par". Suponha que o transmissor, tendo enviado um pacote ímpar, não espere por uma confirmação ímpar e, em vez disso, envie imediatamente o seguinte pacote par. Ele pode então receber uma confirmação dizendo "esperando um próximo pacote ímpar". Isso deixaria o transmissor em um dilema: o receptor recebeu os dois pacotes ou nenhum?
Go-Back-N
Go-Back-N ARQ é o protocolo de janela deslizante com w t > 1, mas um w r = 1 fixo . O receptor se recusa a aceitar qualquer pacote, exceto o próximo na sequência. Se um pacote for perdido em trânsito, os pacotes seguintes serão ignorados até que o pacote ausente seja retransmitido, uma perda mínima de um tempo de ida e volta . Por esse motivo, é ineficiente em links que sofrem freqüentes perdas de pacotes.
Exemplo de ambigüidade
Suponha que estejamos usando um número de sequência de 3 bits, como é típico para HDLC . Isso dá N = 2 3 = 8. Como w r = 1, devemos limitar w t ≤7. Isso ocorre porque, após a transmissão de 7 pacotes, existem 8 resultados possíveis: Em qualquer lugar de 0 a 7 pacotes poderiam ter sido recebidos com sucesso. São 8 possibilidades, e o transmissor precisa de informações suficientes na confirmação para distingui-las todas.
Se o transmissor enviar 8 pacotes sem esperar por confirmação, ele poderá se encontrar em um dilema semelhante ao caso de parar e esperar: a confirmação significa que todos os 8 pacotes foram recebidos com sucesso ou nenhum deles?
Repetição seletiva
O caso mais geral do protocolo de janela deslizante é ARQ de Repetição Seletiva . Isso requer um receptor muito mais capaz, que pode aceitar pacotes com números de sequência maiores do que o atual n r e armazená-los até que a lacuna seja preenchida.
A vantagem, entretanto, é que não é necessário descartar os dados corretos seguintes por um tempo de ida e volta antes que o transmissor possa ser informado de que uma retransmissão é necessária. Portanto, isso é preferido para links com baixa confiabilidade e / ou um produto de alto atraso de largura de banda .
O tamanho da janela w r só precisa ser maior do que o número de pacotes perdidos consecutivos que podem ser tolerados. Assim, pequenos valores são populares; w r = 2 é comum.
Exemplo de ambigüidade
O protocolo HDLC extremamente popular usa um número de sequência de 3 bits e tem provisão opcional para repetição seletiva. No entanto, se a repetição seletiva for usada, o requisito de que n t + n r ≤ 8 deve ser mantido; se w r for aumentado para 2, w t deve ser diminuído para 6.
Suponha que w r = 2, mas um transmissor não modificado seja usado com w t = 7, como é normalmente usado com a variante go-back-N de HDLC. Além disso, suponha que o receptor comece com n r = n s = 0.
Agora, suponha que o receptor veja a seguinte série de pacotes (todos módulo 8):
- 0 1 2 3 4 5 6 (pausa) 0
Como w r = 2, o receptor aceitará e armazenará o pacote final 0 (pensando que é o pacote 8 da série), ao mesmo tempo que solicita uma retransmissão do pacote 7. No entanto, também é possível que o transmissor não tenha recebido nenhuma confirmação e retransmitiu o pacote 0. Neste último caso, o receptor aceitaria o pacote errado como pacote 8.
A solução é o transmissor limitar w t ≤6. Com esta restrição, o receptor sabe que, se todos os reconhecimentos foram perdidos, o transmissor teria parado após o pacote 5. Quando se recebe pacote 6, o receptor pode-se inferir que o transmissor recebeu a confirmação para o pacote 0 (do transmissor n um ≥1) e, portanto, o seguinte pacote numerado 0 deve ser o pacote 8.
Extensões
O protocolo pode ser estendido de muitas maneiras:
- Os exemplos acima presumem que os pacotes nunca são reordenados na transmissão; eles podem ser perdidos no trânsito ( a detecção de erros torna a corrupção equivalente à perda), mas nunca parecerão fora de ordem. O protocolo pode ser estendido para suportar reordenação de pacotes, desde que a distância possa ser limitada; o módulo do número de sequência N deve ser expandido pela distância máxima de solicitação incorreta.
- É possível não reconhecer todos os pacotes, desde que uma confirmação seja enviada eventualmente se houver uma pausa. Por exemplo, o TCP normalmente reconhece cada segundo pacote.
- É comum informar o transmissor imediatamente se uma lacuna na sequência do pacote for detectada. O HDLC tem um pacote REJ (rejeitar) especial para isso.
- Os tamanhos de janela de transmissão e recepção podem ser alteradas durante a comunicação, desde que os seus restos soma dentro do limite de N . Normalmente, cada um deles recebe valores máximos que respeitam esse limite, mas o valor de trabalho em qualquer momento pode ser menor que o máximo. Em particular:
- É comum reduzir o tamanho da janela de transmissão para diminuir a transmissão para corresponder à velocidade do link, evitando saturação ou congestionamento .
- Uma simplificação comum da repetição seletiva é chamada de SREJ-REJ ARQ. Isso opera com w r = 2 e armazena pacotes após um intervalo, mas permite apenas um único pacote perdido; enquanto espera por esse pacote, w r = 1 e se um segundo pacote for perdido, nenhum outro pacote será armazenado em buffer. Isso fornece a maior parte do benefício de desempenho do protocolo de repetição seletiva completo, com uma implementação mais simples.
Veja também
Referências
- Comer, Douglas E. "Internetworking with TCP / IP, Volume 1: Principles, Protocols, and Architecture", Prentice Hall, 1995. ISBN 0-13-216987-8
links externos
- RFC 1323 - Extensões TCP para alto desempenho
- Escala da janela TCP e roteadores quebrados , 2004
- Demonstração da janela deslizante ( Flash necessário)