TCP: Overview
 dados full-duplex:
 ponto-a-ponto:

um transmissor, um receptor
 confiável, seqüêncial ->
stream:

mensagens não são delimitadas
socket
port
buffers de transmissão e de
recepção
aplicação
envia dados
aplicação
lê dados
TCP
buffe de tx

byte
 pipelined: transmissão de vários
pacotes sem confirmação (ACK)
 Controle de congestionamento e
de fluxo definem o tamanho da
janela de transmissão

RFCs: 793, 1122, 1323, 2018, 2581
TCP
buffer de rx

transmissão bi-direcional na
mesma conexão
MSS: maximum segment size
 orientado a conexões:

handshaking (troca de
mensagens de controle)
inicializa o estado do
transmissor e do receptor
antes da troca de dados
 controle de fluxo:

transmissor não esgota a
capacidade do receptor
socket
port
segment
Cap. 3: Camada de Transporte
1
Estrutura do Segmento TCP
32 bits
URG: dados urgentes
(pouco usado)
ACK: campo de ACK
é válido
PSH: acelera entrega
dos dados p/ app. no
receptor(pouco usado)
RST, SYN, FIN:
gerenc. de conexão
(comandos de
estabelec. e término)
porta origem
porta destino
número de seqüência
número de reconhecimento
tam. não
UA P R S F
cabec.usado
checksum
contagem por
bytes de dados
(não segmentos!)
janela de recep.
dados urgentes
Opções (tamanho variável)
dados de aplicação
(tamanho variável)
número de bytes
que o receptor
está pronto para
aceitar
Internet
checksum
(como no UDP)
Cap. 3: Camada de Transporte
2
Números de Seqüência e ACKs do TCP
Números de seqüência:
 número do primeiro
byte de dados no
segmento TCP
ACKs:
 número do próximo
byte esperado do
outro lado
 ACK cumulativo Q:
como o receptor trata
segmentos foram de
ordem?
• descarta?
• bufferiza para entrega
posterior em ordem?

A especificação do
TCP não define, fica a
critério do
implementador!
Host A
Usuário
digita
‘C’
Host B
host confirma
recepção de
‘C’, e ecoa o
’C’ de volta
host confirma
recepção
do ‘C’ ecoado
cenário telnet simples
Cap. 3: Camada de Transporte
tempo
3
TCP: transferência de dados confiável
evento: dados recebidos
da aplicação acima
cria, envia segmento
wait
espera
for
por
event
evento
transmissor simplificado, assumindo
que não há controle de fluxo nem de
congestionamento
evento: temporização esgotada
para segmento com seq = y
retransmite segmento
evento: ACK recebido,
com número de ACK = y
processamento do ACK
Cap. 3: Camada de Transporte
4
TCP:
transferência
confiável
Transmissor
TCP simplificado
00 sendbase = initial_sequence number
01 nextseqnum = initial_sequence number
02
03 loop (forever) {
04
switch(event)
05
event: dados recebidos da aplicação acima
06
cria segmento TCP com número de seqüência nextseqnum
07
if (temporizador ainda não iniciado)
08
inicia temporizador
09
passa segmento ao IP
10
nextseqnum = nextseqnum + length(data)
11
break;
12
event: esgotamento de temporizador
13
retransmite segmento não reconhec. com menor núm. seq.
14
inicia temporizador
15
break;
16
event: ACK recebido, com valor y no campo de ACK
17
if (y > sendbase) { /* ACK cumulativo de todos os dados até y */
18
sendbase = y
19
if (ainda há segmentos com reconhecimento pendente)
20
inicia temporizador
21
}
21
break;
22 } /* end of loop forever */
Cap. 3: Camada de Transporte
5
TCP: cenários de retransmissão
Host A
X
loss
Host B
Seq=92 temp.
Host B
Seq=92 temp.
temporização
Host A
tempo
Cenário com perda
do ACK
Temporização prematura,
ACKs cumulativos
Cap. 3: Camada de Transporte
6
TCP: cenários de retransmissão
Seq=92 temp.
Host A
tempo
Host B
X
loss
Efeito de
ACKs cumulativos
Cap. 3: Camada de Transporte
7
TCP Fast Retransmit:
detecta perda antes do timeout
Geração de ACK
[RFC 1122, RFC 2581]
Evento
Ação do TCP Receptor
segmento chega em ordem,
não há lacunas,
segmentos anteriores já aceitos
Atrasa o ACK. Espera até 500ms
pelo próximo segmento. Se não chegar,
envia segmento “vazio” com ACK
segmento chega em ordem,
não há lacunas,
um ACK atrasado pendente
imediatamente envia um ACK
cumulativo
segmento chega fora de ordem
número de seqüência chegou
maior: lacuna detectada
envia ACK duplicado, indicando número
de seqüência do próximo byte esperado
(menor núm. seq. na lacuna)
chegada de segmento que
parcial ou completamente
preenche a lacuna
Reconhece (ACK) imediatamente se o
Segmento começa na borda inferior
da lacuna
Cap. 3: Camada de Transporte
8
TCP Fast Retransmit
 TCP interpreta a recepção de ACKs
duplicados como a perda do segmento
enviado posteriormente àquele ao qual os
ACKs se referem

retransmite o segmento após 3 ACKs duplicados
 Permite detectar a perda de um pacote de
maneira mais rápida (antes do timeout)
Cap. 3: Camada de Transporte
9
TCP:
transferência
confiável
Transmissor
TCP simplificado
Incluindo
“Fast Retransmit”
00 sendbase = initial_sequence number
01 nextseqnum = initial_sequence number
02
03 loop (forever) {
04
switch(event)
05
event: dados recebidos da aplicação acima
06
cria segmento TCP com número de seqüência nextseqnum
07
if (temporizador ainda não iniciado)
08
inicia temporizador
09
passa segmento ao IP
10
nextseqnum = nextseqnum + length(data)
11
break;
12
event: esgotamento de temporizador
13
retransmite segmento não reconhec. com menor núm. seq.
14
inicia temporizador
15
break;
16
event: ACK recebido, com valor y no campo de ACK
17
if (y > sendbase) { /* ACK cumulativo de todos os dados até y */
18
sendbase = y
19
if (ainda há segmentos com reconhecimento pendente)
20
inicia temporizador
21
}
22
else { /* recebeu ACK duplicado */
23
incrementa o contador de ACKs duplicados para segmento y
24
if (número de ACKs duplicados para segmento y for igual a 3)
25
/* TCP Fast Retransmit */
26
re-envia segmento com número de seqüência y
27
}
21
break;
Cap. 3: Camada de Transporte
10
22 } /* end of loop forever */
TCP Round Trip Time e Temporização
Q: como escolher o
valor da
temporização
(timeout) do TCP?
 maior que o RTT
nota: RTT é variável
 muito curto:
temporização
prematura
 retransmissões
desnecessárias
 muito longo: a reação à
perda de segmento fica
lenta

Q: Como estimar o RTT?
 SampleRTT: tempo medido da
transmissão de um segmento até a
respectiva confirmação
 ignora retransmissões e
segmentos reconhecidos de
forma cumulativa
 SampleRTT varia de forma rápida, é
desejável um “amortecedor” para a
estimativa do RTT
 usar várias medidas recentes,
não apenas o último SampleRTT
obtido
Cap. 3: Camada de Transporte
11
TCP Round Trip Time e Temporização
EstimatedRTT = (1-x) * EstimatedRTT + x * SampleRTT
 Média ponderada
 valor típico de x = 0.1: história (representada pela
estimativa anterior) tem mais peso que o último RTT medido
 influência de uma dada amostra decresce de forma
exponencial
Definindo a temporização
 EstimtedRTT mais uma “margem de segurança”
 grandes variações no EstimatedRTT
 maior margem de segurança
Temporização = EstimatedRTT + 4*Desvios
Desvio = (1-x) * Desvio +
x * |SampleRTT - EstimatedRTT|
Cap. 3: Camada de Transporte
12
TCP Estabelecimento de Conexão
TCP transmissor estabelece
conexão com o receptor antes
de trocar segmentos de dados

inicializar variáveis:



números de seqüência
buffers, controle de fluxo
(ex. RcvWindow)
cliente: iniciador da conexão
Socket clientSocket = new
Socket("hostname","port
number");

servidor: chamado pelo cliente
Socket connectionSocket =
welcomeSocket.accept();
Three way handshake:
Passo 1: sistema final cliente envia
TCP SYN ao servidor
 especifica número de seqüência
inicial
Passo 2: sistema final servidor que
recebe o SYN, responde com
segmento SYN,ACK



reconhece o SYN recebido
aloca buffers
especifica o número de
seqüência inicial do servidor
Passo 3: o sistema final cliente
reconhece o SYN,ACK
Cap. 3: Camada de Transporte
13
TCP Estabelecimento de Conexão
cliente
servidor
Connection
request
Connection
granted
Connection
open
Cap. 3: Camada de Transporte
14
TCP Término de Conexão
Fechando uma conexão:
cliente fecha o socket:
clientSocket.close();
cliente
servidor
close
Passo 1: o cliente envia o
segmento TCP FIN ao servidor
close
responde com ACK. Fecha a
conexão, envia FIN.
espera temp.
Passo 2: servidor recebe FIN,
closed
Cap. 3: Camada de Transporte
15
TCP Término de Conexão
Passo 3: cliente recebe FIN,
responde com ACK.

Entra em “espera
temporizada” - vai
responder com ACK a
eventuais FINs recebidos
cliente
servidor
closing
closing
Passo 4: servidor, recebe ACK.
Conexão fechada.
espera temp.
• se o ACK original do
cliente se perder
closed
closed
Cap. 3: Camada de Transporte
16
TCP Controle de Conexão
Estados do Cliente
Cap. 3: Camada de Transporte
17
TCP Controle de Conexão
Estados do Servidor
Cap. 3: Camada de Transporte
18
TCP: Controle de Fluxo
controle de fluxo
transmissor não deve
esgotar o buffer do
receptor enviando
dados rápido demais
RcvBuffer = tamanho do Buffer de recepção do TCP
RcvWindow = total de espaço livre no buffer
receptor: explicitamente
informa o transmissor sobre
a quantidade de área livre
no buffer (que varia
dinamicamente)
 campo RcvWindow no
cabeçalho do segmento
TCP
transmissor: mantém a
quantidade de dados
pendentes (transmitidos
mas ainda não reconhecidos)
menor que a quantidade
expressa no último
RcvWindow recebido
armazenamento de recepção
Cap. 3: Camada de Transporte
19
Princípios de Controle de Congestionamento
Congestionamento:
 informalmente: “muitas fontes enviando dados acima da
capacidade da rede de tratá-los”
 diferente de controle de fluxo!


controle de fluxo: considera transmissor e receptor apenas
controle de congestionamento: visão global da rede
 sintomas:
perda de pacotes (saturação de buffer nos roteadores)
 atrasos grandes (filas nos buffers dos roteadores)
 um dos 10 problemas mais importantes na Internet!

Cap. 3: Camada de Transporte
20
Causas/custos do congestionamento: cenário 1
 dois transmissores,
dois receptores
 um roteador com
buffers infinitos
 link compartilhado
 não há retransmissão
C: capacidade do link
λin: taxa de transm.
λout: taxa de recep.
 grandes atrasos
quando
congestionado
 máxima vazão
obtenível
Cap. 3: Camada de Transporte
21
Causas/custos do congestionamento: cenário 2
 um roteador com buffers
finitos
 transmissor reenvia pacotes perdidos
Cap. 3: Camada de Transporte
22
Causas/custos do congestionamento: cenário 2
l = l in
< C/2 
in
sem perdas:

“perfeita” retransmissão, somente quando há perdas:

retransmissão de pacotes atrasados (não perdidos) torna
in
perfeito) para o mesmo
(tráfego bom); enquanto
l

lout
l
=
in
lout
l > lout
in
l
in
maior (que o caso
“custos” do congestionamento:
 mais trabalho (retransmissões) para uma certa quantidade de dados originais
 retransmissões desnecessárias: enlace transporta várias cópias do mesmo
pacote
Cap. 3: Camada de Transporte
23
Causas/custos do congestionamento: cenário 3
 quatro transmissores
 caminhos com múltiplos saltos
 temporizações/retransmissões
Q: o que acontece quando
e l aumentam ?
in
l
in
Cap. 3: Camada de Transporte
24
Causas/custos do congestionamento: cenário 3
Outro “custo” do congestionamento:
 quando pacote é descartado, qualquer capacidade de transmissão
que tenha sido anteriormente usada para aquele pacote é
desperdiçada!
Cap. 3: Camada de Transporte
25
Abordagens do problema de controle de
congestionamento
Existem duas abordagens gerais para o problema
de controle de congestionamento:
Controle de congestionamento
fim-a-fim:
 não usa realimentação
explícita da rede
 congestionamento é inferido
a partir das perdas e dos
atrasos observados nos
sistemas finais
 abordagem usada pelo TCP
Controle de congestionamento
assistido pela rede:
 roteadores enviam
informações para os sistemas
finais
 bit único indicando o
congestionamento (SNA,
DECbit, TCP/IP ECN,
ATM)
 a taxa máxima aceitável
pode ser notificada
explicitamente ao
transmissor pela rede
Cap. 3: Camada de Transporte
26
TCP: Controle Congestionamento
 Controle fim-a-fim (não há assistência da rede)
 A taxa de transmissão é limitada pelo tamanho da janela
 Dois limites: CongWin (janela de congestionamento) e RcvWindow

Na prática: janela = min{CongWin, RcvWindow}
Congwin
RcvWindow
 w segmentos, cada um com MSS bytes enviados em um RTT:
vazão =
w * MSS
Bytes/seg
RTT
Cap. 3: Camada de Transporte
27
TCP: Controle Congestionamento
 “teste” para reconhecer a
taxa possível:



idealmente: transmitir tão
rápido quanto possível
(Congwin tão grande
quanto possível) sem
perdas
aumentar Congwin até que
ocorra perda
(congestionamento)
perda: diminuir Congwin,
então ir testando
(aumentando) outra vez
 duas “fases””
 slow start
 AIMD - congestion
avoidance
 variáveis importantes:
 Congwin
 threshold: define o
limite entre a fase slow
start e a fase
congestion avoidance
Cap. 3: Camada de Transporte
28
AIMD (Additive-Increase,
Multiplicative-Decrease)
redução multiplicativa


aumenta a janela de 1 a
cada RTT
diminui a janela por um
fator de 2 em caso de
evento perda
 Evento de perda: 3 ACKs
duplicados
 Adotado no TCP Reno
(versão mais recente)
Janela de Congestionamento
TCP congestion avoidance:
 AIMD: aumento aditivo,
24K
16K
8K
tempo
Cap. 3: Camada de Transporte
29
TCP Slowstart
Host A
inicializar: Congwin = 1
para (cada segmento reconhecido
Congwin++
até (evento perda OU
CongWin > threshold)
RTT
algoritmo Slowstart
Host B
 aumento exponencial (por
RTT) no tamanho da janela
(não tão lento!)
 evento de perda : timeout
(Tahoe TCP) e/ou 3 ACKs
duplicados (Reno TCP)
tempo
Cap. 3: Camada de Transporte
30
TCP: Congestion Avoidance
Congestion avoidance
/* acabou slowstart
*/
/* Congwin > threshold */
Até (evento perda) {
cada w segmentos reconhecidos:
Congwin++
}
threshold = Congwin/2
Congwin = 1
realiza slowstart
1: TCP Reno pula a fase slowstart (recuperaçaõ rápida)
após três ACKs duplicados
Cap. 3: Camada de Transporte
31
TCP Tahoe Vs. TCP Reno
TCP Reno após 3
ACKs duplicados
(AIMD)
TCP Tahoe (sempre)
ou
TCP Reno após
timeout
Cap. 3: Camada de Transporte
32
TCP: Congestion Avoidance
(Tahoe TCP)
Congestion avoidance
/* acabou slowstart (CongWin > threshold) */
/* Inicia congestion avoidance: crescimento
linear de CongWin */
Até (novo evento de perda - qualquer) {
a cada w segmentos reconhecidos:
CongWin++
}
/* após evento de perda */
threshold = CongWin/2
CongWin = 1
realiza slowstart até threshold
reinicia congestion avoidance
Cap. 3: Camada de Transporte
33
TCP: Congestion Avoidance
(Reno TCP)
Congestion avoidance
/* acabou slowstart (CongWin > threshold) */
/* Inicia congestion avoidance: crescimento
linear de CongWin */
Até (novo evento de perda) {
a cada w segmentos reconhecidos:
CongWin++
}
threshold = CongWin / 2
se timeout:
CongWin = 1
realiza slowstart até threshold
senão, se 3 ACKs duplicados:
CongWin = thresholdd
reinicia congestion avoidance
Cap. 3: Camada de Transporte
34
TCP: Eqüidade (fairness)
Objetivo: se N sessões TCP
devem passar pelo mesmo
gargalo, cada uma deve obter
1/N da capacidade do enlace
conexão TCP 1
conexão TCP 2
roteador com
gargalo de capacidade R
Cap. 3: Camada de Transporte
35
Porque o TCP é justo?
Duas sessões competindo pela banda:
 O aumento aditivo fornece uma inclinação de 1, quando a vazão aumenta
 redução multiplicativa diminui a vazão proporcionalmente
R
divisão igual da banda
perda: reduz janela por um fato de 2
congestion avoidance: aumento aditivo
perda: reduz janela por um fator de 2
congestion avoidance: aumento aditivo
Vazão da Conexão 2
R
Cap. 3: Camada de Transporte
36
Capítulo 3: Resumo
 princípios por trás dos serviços
da camada de transporte:
multiplexação/demultiplexação
 transferência de dados
confiável
 controle de fluxo
 controle de congestionamento
 instanciação e implementação na
 UDP
 TCP

A seguir:
 saímos da “borda” da
rede (camadas de
aplicação e de
transporte)
 vamos para o “núcleo” da
rede


Camada de Rede
Camada de Enlace
Cap. 3: Camada de Transporte
37
Anexos:
Cap. 3: Camada de Transporte
38
Estudo de caso: controle de
congestionamento do serviço ATM ABR
ABR: Available Bit Rate
células RM (Resource Management) :
“serviço elástico”
 se o caminho do transmissor
está pouco usado:
 transmissor pode usar a
banda disponível
 se o caminho do transmissor
está congestionado:
 transmissor é limitado a
uma taxa mínima garantida


enviadas pelo transmissor,
entremeadas com as células de dados
 bits nas células RM são usados pelos
comutadores (“assistida pela rede”)
 NI bit: não aumentar a taxa de
transmissão (congestionamento
leve)
 CI bit: indicação de
congestionamento: restringir a
taxa de transmissão
 as células RM são devolvidos ao
transmissor pelo receptor, com os bits
de indicaçaõ intactos
Cap. 3: Camada de Transporte
39
Estudo de caso: controle de
congestionamento do serviço ATM ABR
 campo ER (explicit rate) de dois bytes nas células RM


comutador congestionado pode reduzir o valor de ER nas células
o transmissor envia dados de acordo com a menor vazão máxima suportada
no caminho (i.e., pelo comutador mais congestionado)
 bit EFCI nas células de dados: marcado como 1 pelos comutadores
congestionados

se a célula de dados que precede a célula RM tem o bit EFCI com valor 1, o
receptor marca o bit CI na célula RM devolvida
Cap. 3: Camada de Transporte
40
TCP: modelagem da latência
Q: Quanto tempo demora para
receber um objeto de um servidor
Web após enviar um pedido?
estabelecimento de conexão TCP
 atraso de transferência de dados

Notação, hipóteses:





Assuma um enlace entre o cliente
e o servidor com taxa de dados R
Assuma: janela de
congestionamento fixa, W
segmentos
S: MSS (bits)
O: tamanho do objeto (bits)
não há retransmissões (sem
perdas e corrupção de dados)
Dois casos a considerar:
WS/R > RTT + S/R: ACK para o primeiro segmento retorna
antes de se esgotar a janela de transmissão de dados
 WS/R < RTT + S/R: espera pelo depois de esgotar a janela de
transmissão de dados

Cap. 3: Camada de Transporte
41
TCP: modelagem da latência
K:= O/WS
Caso 1: latencia = 2RTT + O/R
Caso 2: latencia = 2RTT + O/R
+ (K-1)[S/R + RTT - WS/R]
Cap. 3: Camada de Transporte
42
TCP Modelagem de Latência: Slow Start
 Agora suponha que a janela cresce de acordo com os procedimentos
da fase slow start.
 Vamos mostrar que a latência de um objeto de tamanho O é:
Latency  2 RTT 
O
S
S

 P  RTT    (2 P  1)
R
R
R

onde P é o número de vezes que o TCP fica bloqueado no servidor:
P  min{Q, K  1}
- onde Q é o número de vezes que o servidor ficaria bloqueado se
o objeto fosse de tamanho infinito.
- e K é o número de janelas que cobrem o objeto.
Cap. 3: Camada de Transporte
43
TCP Modelagem de Latência: Slow Start (cont.)
Exemplo:
O/S = 15 segmentos
inicia
conexão TCP
pede
objeto
K = 4 janelas
primeira janela
= S/R
RTT
segunda janela
= 2S/R
Q=2
terceira janela
= 4S/R
P = min{K-1,Q} = 2
Servidor bloqueado P=2 times.
quarta janela
= 8S/R
transmissão
completa
objeto
entregue
tempo no
cliente
tempo no
servidor
Cap. 3: Camada de Transporte
44
TCP Modelagem de Latência: Slow Start (cont.)
S
 RTT  tempo quando o servidor inicia o envio do segmento
R
até quando o servidor recebe reconhecimento
2k
1
S
 tempo para enviar a k-ésima janela
R
inicia
conexão TCP
pede
objeto

tempo de bloqueio após a
S
k 1 S 



RTT
2
 R
k-ésima janela
R 
RTT
primeira janela
= S/R
segunda janela
= 2S/R
terceira janela
= 4S/R
P
O
latencia  2 RTT   TempoBloqueio
R
p 1
p
P
O
S
S
  2 RTT   [  RTT  2k 1 ]
R
R
k 1 R
O
S
S
  2 RTT  P[ RTT  ]  (2 P  1)
R
R
R
quarta janela
= 8S/R
objeto
entregue
tempo no
cliente
transmissão
completa
tempo no
servidor
Cap. 3: Camada de Transporte
45