Embed Size (px)
Citation preview
Figueiredo – 2011
Redes de ComputadoresAula 6
Aula passadaCamada de transporteMultiplexaçãoPrincípios de transmissão confiávelStopandwait
Aula de hojeEficiênciaGoBack NSelective Repeat
Figueiredo – 2011
Eficiência do Stop-and-Wait
Início da transmissão
tempo tempo
Fim da transmissão
Recebe confirmação
Pacote L bytes
Taxa de transmissão R
Propagação p
Vazão máxima do canal?
Utilização?
Muito ruim!
Figueiredo – 2011
Eficiência do Stop-and-WaitPacote L bytes
Taxa de transmissão R
Propagação p
Vazão = L / (L/R + 2p)
Ex. L = 1000 bytes, R = 1Gbps, p = 10ms
V = 400Kbps
Apesar do enlace ser de 1Gbps!
U = 0.4/1000 = 0.0004!
Como melhorar eficiência?
Figueiredo – 2011
Protocolos com Pipeline
Problemas que teremos que resolver?Significado do ACK, número de sequência, ordenação, bufferização
Pipeline: transmissor permite múltiplos pacotes “em trânsito”, antes de receber ACK
Figueiredo – 2011
Vazão com Pipeline
Tx P1
tempo tempo
Rx ACK 1
Supor pipeline de 3 pacotesGanho na vazão?Ganho na utilização?Transmissão de 3 pacotesVazão 3 vezes maior!
Tx P2
Tx P3
Rx ACK 2
Rx ACK 3
Tx ACK 1
Tx ACK 2
Tx ACK 3Tx P4
Tx P5
Tx P6
Figueiredo – 2011
Protocolos com Pipeline (ou Janela)
Go-back NTx poder ter até N pacotes sem ACK no pipelineRx transmite ACKs cumulativos
Não envia ACK se tiver faltando na sequência
Tx tem timer para pacote mais antigo sem ACK
Retransmite todos os pacotes se timer expira
Selective Repeat:Tx pode ter até N pacotes sem ACK no pipelineRX envia ACK individual para pacotesTx mantém um timer para cada pacote
Retransmite somente o pacote se timer expira
Figueiredo – 2011
Go-Back-NSender:
k-bit seq # in pkt header“window” of up to N, consecutive unack’ed pkts allowed
❒ ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”❍ may receive duplicate ACKs (see receiver)
❒ timer for each in-flight pkt❒ timeout(n): retransmit pkt n and all higher seq # pkts in window
Figueiredo – 2011
GBN: sender extended FSM
Wait start_timerudt_send(sndpkt[base])udt_send(sndpkt[base+1])…udt_send(sndpkt[nextseqnum1])
timeout
rdt_send(data)
if (nextseqnum < base+N) { sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum) start_timer nextseqnum++ }else refuse_data(data)
base = getacknum(rcvpkt)+1If (base == nextseqnum) stop_timer else start_timer
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
base=1nextseqnum=1
rdt_rcv(rcvpkt) && corrupt(rcvpkt)
Λ
Figueiredo – 2011
GBN: receiver extended FSM
ACK-only: always send ACK for correctly-received pkt with highest in-order seq #
may generate duplicate ACKsneed only remember expectedseqnum
out-of-order pkt: discard (don’t buffer) -> no receiver buffering!Re-ACK pkt with highest in-order seq #
Wait
udt_send(sndpkt)
default
rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum)
extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(expectedseqnum,ACK,chksum)udt_send(sndpkt)expectedseqnum++
expectedseqnum=1sndpkt = make_pkt(expectedseqnum,ACK,chksum)
Λ
Figueiredo – 2011
GBN inaction
Figueiredo – 2011
Selective Repeatreceiver individually acknowledges all correctly received pkts
buffers pkts, as needed, for eventual in-order delivery to upper layer
sender only resends pkts for which ACK not received
sender timer for each unACKed pkt
sender windowN consecutive seq #’sagain limits seq #s of sent, unACKed pkts
Figueiredo – 2011
Selective repeat: sender, receiver windows
Figueiredo – 2011
Selective repeat
data from above :if next available seq # in window, send pkt
timeout(n):resend pkt n, restart timer
ACK(n) in [sendbase,sendbase+N]:
mark pkt n as receivedif n smallest unACKed pkt, advance window base to next unACKed seq #
sender
pkt n in [rcvbase, rcvbase+N-1]
❒ send ACK(n)❒ out-of-order: buffer❒ in-order: deliver (also
deliver buffered, in-order pkts), advance window to next not-yet-received pkt
pkt n in [rcvbase-N,rcvbase-1]
❒ ACK(n)
otherwise: ❒ ignore
receiver
Figueiredo – 2011
Selective repeat in action
Figueiredo – 2011
Selective repeat: dilemma
Example: seq #’s: 0, 1, 2, 3window size=3
receiver sees no difference in two scenarios!incorrectly passes duplicate data as new in (a)
Q: what relationship between seq # size and window size?
