Redes de Computadores Redes de Computadores

Artur ArsenioRedes de Computadores 2010/2011

Departamento de Engenharia Informtica1

Redes de ComputadoresRedes de Computadores

Camada Transporte


Departamento de Engenharia Informtica2 Camada de Transporte

Camada Aplicao Reviso

Princpios e caracteristicas dos protocolos da camada de aplicao

A Web e o HTTP (Hypertext Transfer Protocol) Transferncia de Ficheiros (File Transfer)

File Transfer Protocol (FTP) Correio Electrnico

SMTP: Simple Mail Transfer Protocol, POP3, IMAP Servio de nomes da Internet

DNS: Domain Name System protocol Partilha de Ficheiros Peer-to-Peer (P2P)

Princpios e caracteristicas dos protocolos da camada de aplicao

A Web e o HTTP (Hypertext Transfer Protocol) Transferncia de Ficheiros (File Transfer)

File Transfer Protocol (FTP) Correio Electrnico

SMTP: Simple Mail Transfer Protocol, POP3, IMAP Servio de nomes da Internet

DNS: Domain Name System protocol Partilha de Ficheiros Peer-to-Peer (P2P)

aplicao

transporte

rede

lgica

fsica



Camada Transporte

Objectivos:

Aprender sobre os protocolos da camada de transporte da Internet, e principios destes. Objectivos:

Aprender sobre os protocolos da camada de transporte da Internet, e principios destes.

Servios da camada de transporte Multiplexagem e desmultiplexagem Transporte no orientado ligao: UDP Princpios da transferncia fivel de dados Transporte orientado ligao: TCP

transferncia fivel de dados controlo do fluxo Gesto de ligaes

Principios do controlo do congestionamento Controlo de congestionamento do TCP

Segue Capitulo 3 do livro de J.F Kurose e K.W. Ross

aplicao

transporte

rede

lgica

fsica



Servios e Protocolos de Transporte

Os protocolos da camada de transporte executam-se nossistemas terminais e fornecem um servio de comunicao ao nvel lgico entre as aplicaes

lado emissor: quebra as mensagens da aplicao em segmentos, repassa-os para a camada de rede

lado receptor: remonta as mensagens a partir dos segmentos, repassa-as para a camada de aplicao

Protocolos de transporte: TCP, UDP

aplicaotransporte

redeligaofsica

redeligaofsica

aplicaotransporte

redeligaofsica

redeligaofsica

redeligaofsicarede

ligaofsica

redeligaofsica

transportelgico

end 2 end



Camadas de Transporte vs Rede

camada de rede Transferncia de dados

entre sistemas terminais No reconhecem, nem

actuam, sobre informao adicionada pela camada de transporte

camada de transporte comunicao lgica entre

processos depende de, e estende,

os servios da camada de rede

Analogia domstica:12 crianas enviam cartas a

12 crianas processos = crianas mensagens da aplicao =

cartas nos envelopes Sistemas terminais = casas protocolo de transporte =

Ana e Joaquim protocolo da camada de

rede = servio postal

Analogia domstica:12 crianas enviam cartas a

12 crianas processos = crianas mensagens da aplicao =

cartas nos envelopes Sistemas terminais = casas protocolo de transporte =

Ana e Joaquim protocolo da camada de

rede = servio postal

As entidades da camada de transporte trocam entre si segmentos ou TPDUs (Transport Protocol Data Unit)

processo

TCP

ou

UDP

socket

IP



Protocolos da Camada de Transporte Internet

Comunicao fivel; com garantia de entrega na ordem de extremo a extremo unicast (TCP)

controlo de congesto controlo de fluxo estabelecimento e gesto de ligaes (setup)

Protocolo leve; entrega no fivel; sem garantia de controlo de fluxo, controlo da congesto, ou entrega na ordem; de um extremo para um ou mais extremos (unicast ou multicast): UDP

Entrega de dados entre processos Deteco de erros

Servios da camada de Rede IP: servio de entrega no fivel entre sistemas terminais: melhor esforo

Servios no disponveis: garantias de atraso mximo garantias de largura de banda mnima



Servios da camada de transporte Reviso



Principios do controlo do congestionamento

Controlo de congestionamento do TCP









Multiplexagem e Desmultiplexagem

Entrega dos segmentos recebidos ao socket correcto

Desmultiplexagem-receptorrene dados de muitos sockets e coloca o cabealho (usado depoispara a desmultiplexagem)

Multiplexagem-emissor

mensagem

segmento

datagrama HtHn M

Ht M

M

Encapsulamento



Computador recebe os datagramas IP cada datagrama possui os

endereos IP da origem e do destino

cada datagrama transporta 1 segmento da camada de transporte

se sem fragmentao IP

cada segmento possui nmeros das portas origem e destino (lembrar: nmeros de portas bem conhecidas para aplicaes especficas)

O sistema terminal usa os endereos IP e os nmeros das portas para direccionar o segmento ao socket apropriado

Como funciona a Desmultiplexagem

porto emissor porto receptor32 bits

dados daaplicao

(mensagem)

outros camposdo cabealho

formato do segmento TCP/UDPNmeros ds portos: 16 bits (0 65535)

0 1023 restritos para uso por aplicaes conhecidas e.g. HTTP no porto 80, FTP no 21 (www.iana.org)



Criar sockets com nmeros de portoDatagramSocket mySocket1 = newDatagramSocket();

DatagramSocket mySocket2 = newDatagramSocket(9157);

socket UDP identificado pelo par endereo IP destino nmero do porto destino

Atribuio de nmeros de portos: Lado cliente aplicao: deixa a

camada de transporte atribuir o nmero porto de forma transparente

Laso servidor da aplic. Atribui um nmero de porto especifico

Quando o receptor recebe segmento UDP:

verifica nmero do porto de destino no segmento

encaminha o segmento UDP para o socket com aquele nmero de porto

Datagramas IP com diferentes endereos IP origem e/ou nmeros de porta origem podem ser encaminhados para o mesmo socket

Desmultiplexagem sem Ligao



Desmultiplexagem sem Ligao (cont.)

DatagramSocket serverSocket = new DatagramSocket(6428);

ClienteIP:B

P2

clienteIP: A

P1P1P3

servidorIP: C

SP: 6428DP: 9157

SP: 9157DP: 6428

SP: 6428DP: 5775

SP: 5775DP: 6428

SP (source port) fornece endereo de retornoSP (source port) fornece endereo de retorno

Multiplexagem Desmultiplexagem



Socket TCP identificado pela qudrupla:

endereo IP origem nmero da porta origem endereo IP destino nmero da porta destino

receptor usa todos os quatro valores para direccionar o segmento para o socket apropriado

Servidor pode dar suporte a muitos sockets TCP simultneos

cada socket identificado pela sua prpria qudrupla

Servidores Web tm socketsdiferentes para cada ligao cliente

HTTP no persistente tersockets diferentes para cada pedido

Desmultiplexagem com Ligao



ClienteIP:B

P1

clienteIP: A

P1P2P4

servidorIP: C

SP: 9157DP: 80

SP: 9157DP: 80

P5 P6 P3

D-IP:CS-IP: AD-IP:C

S-IP: B

SP: 5775DP: 80

D-IP:CS-IP: B

Desmultiplexagem com Ligao (cont.)

Desmultiplexagem



ClienteIP:B

P1

clienteIP: A

P1P2

servidorIP: C

SP: 9157DP: 80

SP: 9157DP: 80

P3

D-IP:CS-IP: AD-IP:C

S-IP: B

SP: 5775DP: 80

D-IP:CS-IP: B

Desmultiplexagem com Ligao Servidor Web com Threads

P4Desmultiplexagem



Multiplexagem e Desmultiplexagem Reviso








Servidor Web com Threads




Servidor Web com Threads



Protocolo de transporte mnimo (adiciona pouco ao IP)

Servio de (Des)Multiplexagem Simples deteco de erros

Servio melhor esforo, segmentos UDP podem ser:

perdidos entregues aplicao fora de

ordem Sem ligao

no h setup UDP entre emissor, receptor

cada segmento UDP tratado independentemente dos outros

elimina estabelecimento de ligao

o que pode causar atraso simples: no se mantm estado

da ligao ao nvel da camada de transporte

nem no emissor, nem no receptor

cabealho de segmento reduzido emissor pode transmitir a

qualquer ritmo, to rpido quanto desejado (e possvel)

no h controlo de congesto

UDP: User Datagram Protocol

Vantagens do UDP

[RFC 768]Protocolo de transporte da Internet



Aplicao Internet

correio electrnico

acesso em terminal remoto

Web

transferncia de ficheiros

streaming multimedia

servidor de ficheiros remoto

Telefone sobre Internet

Gesto de redes

Protocolo de encaminhamento

Traduo de nomes

Protocolo da

camada de aplicao

SMTP

telnet

HTTP

FTP

HTTP(ex. YouTube), RTP

NFS

Proprietrios (Skype)

SNMP

RIP

DNS

Protocolo de

transporte usado

TCP

TCP

TCP

TCP

tipicamente UDP

tipicamente UDP

tipicamente UDP

tipicamente UDP

tipicamente UDP

tipicamente UDP

Aplicaes Internet: protocolos de aplicao e de transporte Recapitular



Utilizado para aplicaes multimdia tolerantes a perdas sensveis taxa de transmisso

Outras aplicaes: DNS (nomes) SNMP (gesto de redes)

Uma aplicao pode incluir mecanismos de transferncia de dados fivel, mesmo usando UDP ao nvel de transporte

acrescentar fiabilidade na camada de aplicao

recuperao de erro especfica aplicao

porto origem porto dest.

32 bits

Dados de aplicao(mensagem)

Formato do segmento UDP

comprimento checksum

Comprimento em bytes do segmento UDP, incluindo cabealho

soma de verificao(checksum)

Caracteristicas e Formato das Mensagens UDP



Soma de Verificao (checksum) UDP

Emissor trata contedo do segmento como

sequencia de inteiros de n-bits (16 bits) campo checksum inicializado a zero

Mtodo Soma-Modular

emissor coloca complemento do valor da soma no campo checksum soma (adio usando complemento de 1) do

contedo do segmento (RFC[1071] para detalhes sobre algoritmo eficiente de calculo)

Mtodo Parity byte or parity word

checksum: exclusive-or do contedo do segmento

Receptor calcula checksum do segmento

recebido anexado com o valor de checksum enviado

clculo usando exclusive-or ou soma-modular conforme algoritmo usado pelo emissor

verifica se novo checksumcalculado palavra com n

0s (Mtodo Parity byte or parity word)

1s (Mtodo Soma-Modular) NO - erro detectado SIM - nenhum erro detectado

Receptor calcula checksum do segmento

recebido anexado com o valor de checksum enviado

clculo usando exclusive-or ou soma-modular conforme algoritmo usado pelo emissor

verifica se novo checksumcalculado palavra com n

0s (Mtodo Parity byte or parity word)

1s (Mtodo Soma-Modular) NO - erro detectado SIM - nenhum erro detectado

Objectivo: detectar erros (ex.: bits trocados) no segmento transmitidoErros devido por exemplo a rudo nas ligaes fisicas ou na memria do router, ...



1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1soma de verificao

(checksum)

Checksum Internet Erros

Mtodo Parity byte or parity word

1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1

1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0

0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1

Mtodo da soma-modular

soma de verificao(checksum)



checksum


mtodo parity-byte

mtodo da soma-modular

Erros de transmisso que originem o flip de apenas 1 bit da mensagem, oude um nmero impar de bits, iro ser detectados checksum incorrecto

dois bits errados podem no ser detectados se bits esto na mesma posio em duas palavras diferentes

Erros de transmisso que originem o flip de apenas 1 bit da mensagem, oude um nmero impar de bits, iro ser detectados checksum incorrecto

dois bits errados podem no ser detectados se bits esto na mesma posio em duas palavras diferentes

0

0

1

0 1

1

Para uma seleco aleatrea de bits erradamente transmitidos, a probabilidade de um erro de doisbits no ser detectado

1/n no mtodo parity-byte menor a 1/n no mtodo da

soma-modular

Para uma seleco aleatrea de bits erradamente transmitidos, a probabilidade de um erro de doisbits no ser detectado

1/n no mtodo parity-byte menor a 1/n no mtodo da

soma-modular

0

0

0

01

Flip de dois bits no detectado

Flip de dois bits detectado!

1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1



Transporte sem Ligao: UDP Reviso















Importante nas camadas de transporte e ligao de dados

Princpios de Transferncia fivel de dados- Reliable Data Transfer (rdt)

Camada de aplicao

Camada de transporte

Camada de rede

As caractersticas do canal de comunicao no fivel que est por baixo determinam a complexidade do protocolo de transferncia de dados fivel

Com um canal fivel, nenhum bit est corrompido ou est perdido, e todos so entregues na ordem com que foram enviados

As caractersticas do canal de comunicao no fivel que est por baixo determinam a complexidade do protocolo de transferncia de dados fivel

Com um canal fivel, nenhum bit est corrompido ou est perdido, e todos so entregues na ordem com que foram enviados



ladoemissor

Ladoreceptor

rdt_send(): chamado da camada de cima, (e.g. pela aplicao). Envia dados paraentrega camada superior do receptor

udt_send(): chamado pela entidade de transporte rdt, para transferir pacotes parao receptor atravs de um canal no fivel

rdt_rcv(): chamado quando ospacotes chegam ao canal no ladodo receptor

deliver_data(): chamadopor rdt para entregar dados camada superior

Transferncia de dados fivel: Implementao



Vamos desenvolver incrementalmente os lados do emissor e receptor do protocolo de transferncia de dados fivel (rdt)

Considerar apenas transferncia de dados unidirecional mas a informao de controlo flui em ambos os sentidos

Usar mquinas de estados finitas (FSM) para especificar o emissor e o receptor

estado1

estado2

evento que causa transio de estado

aces a executar na transio de estadoestado: quando se esperam eventos.

Quando num estado, o prximo estado unicamente determinado peloprximo evento

eventos

aces

Transferncia de dados fivel Metodologia

Estado inicial

- Nenhuma aco no evento, ou nenum evento ocorre quando aco executada



Canal de transmisso que est por baixo perfeitamente fivel no h erros nos bits no h perda de pacotes

Mquinas de estados separadas para o emissor e o receptor emissor envia dados para o canal receptor l os dados do canal

Canal de transmisso que est por baixo perfeitamente fivel no h erros nos bits no h perda de pacotes

Mquinas de estados separadas para o emissor e o receptor emissor envia dados para o canal receptor l os dados do canal

rdt1.0: transferncia de dados fivel sobre canal fivel

Esperadados de

cimapacket = make_pkt(data)udt_send(packet)

rdt_send(data) Esperadados de

baixo

rdt_rcv(packet)

emissor receptor

extract(packet, data)deliver_data(data)



A questo: como recuperar esses erros? confirmaes positivas (acknowledgements, ACKs)

receptor informa, explicitamente, o emissor que recebeu um pacote sem erros confirmaes negativas (negative acknowledgements NAKs)

receptor informa, explicitamente, o emissor que o pacote recebido tem erros emissor retransmite o pacote quando recebe o NAK

Protocolos rdt baseados na retransmisso Conhecidos como protocolos ARQ (Automatic Repeat reQuest) Novos mecanismos em rdt2.0 (para alm de rdt1.0):

Deteco de erros Resposta (feedback) do receptor:

mensagens de controlo (ACK,NAK) receptor emissor Retransmisso em caso de erros

A questo: como recuperar esses erros? confirmaes positivas (acknowledgements, ACKs)

receptor informa, explicitamente, o emissor que recebeu um pacote sem erros confirmaes negativas (negative acknowledgements NAKs)

receptor informa, explicitamente, o emissor que o pacote recebido tem erros emissor retransmite o pacote quando recebe o NAK

Protocolos rdt baseados na retransmisso Conhecidos como protocolos ARQ (Automatic Repeat reQuest) Novos mecanismos em rdt2.0 (para alm de rdt1.0):

Deteco de erros Resposta (feedback) do receptor:

mensagens de controlo (ACK,NAK) receptor emissor Retransmisso em caso de erros

rdt2.0: canal introduz erros nos bits

Canal que est por baixo pode trocar bits nos pacotes introduzindo erros - no perde pacotes



rdt2.0: Especificao da Mquina de Estados

extract(rcvpkt,data)deliver_data(data)udt_send(ACK)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

udt_send(NAK)

rdt_rcv(rcvpkt) && corrupt(rcvpkt)

Esperadados de

baixo

Emissor Receptor

Esperadados de

cima

sndpkt = make_pkt(data, checksum)udt_send(sndpkt)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

udt_send(sndpkt)

rdt_rcv(rcvpkt) && isNAK(rcvpkt)EsperaACK ou

NAK

rdt_send(data)

predicado



Wait for call from above

snkpkt = make_pkt(data, checksum)udt_send(sndpkt)




udt_send(sndpkt)

rdt_rcv(rcvpkt) &&isNAK(rcvpkt)

udt_send(NAK)


Wait for ACK or

NAK Wait for call from

below

rdt_send(data)

rdt2.0: Funcionamento sem ErrosEmissor Receptor



Wait for call from above

snkpkt = make_pkt(data, checksum)udt_send(sndpkt)




udt_send(sndpkt)

udt_send(NAK)


Wait for ACK or

NAK Wait for call from

below

rdt_send(data)

rdt2.0: Cenrio de Erros

rdt_rcv(rcvpkt) &&isNAK(rcvpkt)

Emissor Receptor



Tratamento de duplicados emissor acrescenta nmero de

sequncia a cada pacote emissor retransmite o pacote

corrente se o ACK/NAK se corromper

receptor descarta (no os entrega aplicao) pacotes duplicados

O que acontece se os ACKs ou os NAKs se corromperem?

O emissor no sabe o que se passou no receptor!

A simples retransmisso pode originar pacotes duplicados

O que fazer? Emissor envia ACKs/NAKs

referentes aos ACK/NAK do receptor?

E se se perder os ACK/NAKdo emissor?

Retransmite-se!?

parar e esperarStop and wait

rdt2.0 mau funcionamento

Emissor envia um pacote e espera pela resposta do receptor



sndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)

rdt_send(data)

udt_send(sndpkt)

rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) )


rdt_send(data)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt)

udt_send(sndpkt)

rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isNAK(rcvpkt) )

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt)

Esperadados 0 de cima

esperaACK ouNAK 0

Esperadados 1 de cima

esperaACK ouNAK 1

rdt2.1: Emissor trata ACK/NAKs corrompidos



sndpkt = make_pkt(NAK, chksum)udt_send(sndpkt)

rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq0(rcvpkt)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt)

extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)

rdt_rcv(rcvpkt) && (corrupt(rcvpkt)

sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)

rdt_rcv(rcvpkt) && not corrupt(rcvpkt) &&has_seq1(rcvpkt)

rdt_rcv(rcvpkt) && (corrupt(rcvpkt)

sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)

sndpkt = make_pkt(NAK, chksum)udt_send(sndpkt)

Esperadados 0 de baixo

Esperadados 1 de baixo

rdt2.1: Receptor, trataACK/NAKs corrompidos



rdt2.1: discusso

Emissor: N de sequncia adicionado a

cada pacote bastam dois ns de sequncia

(0,1) Tem de se verificar se

ACKs/NAKs recebidos esto corrompidos

duplicou o n de estados O estado tem de se lembrar se

o pacote corrente tem o n de sequncia 0 ou 1

Receptor: Tem de verificar se recebeu

pacotes duplicados o estado indica se se

espera um pacote com o n de sequncia 0 ou 1

nota: receptor no tem como saber se o ltimo ACK/NAK foi recebido correctamente pelo emissor



rdt2.2: Protocolo sem NAKs

A mesma funcionalidade do rdt2.1, mas usando apenas ACKs

ao invs de NAK, receptor envia um ACK por cada pacote recebido sem erro

receptor tem de incluir explicitamente o n de sequncia do pacote a ser confirmado, isto , ACKed

A recepo de dois ACKs seguidos para o mesmo pacote no emissor resulta na mesma aco que um NAK: retransmisso do pacote seguinte ao ltimo pacote enviado sem erro

A mesma funcionalidade do rdt2.1, mas usando apenas ACKs

ao invs de NAK, receptor envia um ACK por cada pacote recebido sem erro

receptor tem de incluir explicitamente o n de sequncia do pacote a ser confirmado, isto , ACKed

A recepo de dois ACKs seguidos para o mesmo pacote no emissor resulta na mesma aco que um NAK: retransmisso do pacote seguinte ao ltimo pacote enviado sem erro



aguardachamada 0

de cima


rdt_send(data)

udt_send(sndpkt)

rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isACK(rcvpkt,1) )

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0)

aguardaACK

0

Emissor parcial (fragmentoFSM do emissor)

aguarda

0 de baixo

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)

extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK,1, chksum)

udt_send(sndpkt)

rdt_rcv(rcvpkt) && (corrupt(rcvpkt) ||has_seq1(rcvpkt))

udt_send(sndpkt)Receptor parcial

rdt2.2: fragmentos do emissor e receptor



rdt3.0: canais com erros e perdas

Nova hiptese: canal de transmisso que est por baixo tambm pode perder pacotes (dados ou ACKs)

Para recuperar da perda de pacotes, usa-se checksum, n de sequncia, ACKs e retransmisses

Mas como determinar a perda de pacotes?

Nova hiptese: canal de transmisso que est por baixo tambm pode perder pacotes (dados ou ACKs)

Para recuperar da perda de pacotes, usa-se checksum, n de sequncia, ACKs e retransmisses

Mas como determinar a perda de pacotes?

Abordagem: o emissor aguarda um tempo razovel pelo ACK retransmite se nenhum ACK for recebido neste intervalo se pacote (ou ACK) estiver apenas atrasado (e no perdido):

retransmisso provoca um pacote duplicado, mas o uso do n de sequncia possibilita deteco correcta no receptor

receptor deve especificar n de sequncia do pacote sendo reconhecido requisitos adicionais

Receptor tem de incluir em cada ACK o n de seq. do pacote que est a confirmar requer temporizador (timer)

Abordagem: o emissor aguarda um tempo razovel pelo ACK retransmite se nenhum ACK for recebido neste intervalo se pacote (ou ACK) estiver apenas atrasado (e no perdido):

retransmisso provoca um pacote duplicado, mas o uso do n de sequncia possibilita deteco correcta no receptor

receptor deve especificar n de sequncia do pacote sendo reconhecido requisitos adicionais

Receptor tem de incluir em cada ACK o n de seq. do pacote que est a confirmar requer temporizador (timer)



rdt3.0: emissor

sndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)start_timer

rdt_send(data)

EsperaACK 0


Esperachamada 1

de cima

sndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)start_timer

rdt_send(data)




stop_timer

stop_timer

timeout

udt_send(sndpkt)start_timer

timeout

rdt_rcv(rcvpkt)

Esperachamada 0

de cima

EsperaACK 1

rdt_rcv(rcvpkt)

udt_send(sndpkt)start_timer



rdt3.0: em aco

Alternating-bit protocol



rdt3.0: em aco



rdt3.0: Funcionamento do stop-and-wait

emissor

ltimo bit do 1 pacotetransmitido, t = L / R

chegada do 1 bit do pacotechegada do ltimo bit do primeiro pacote, envia ACK

ACK chega, envia prximo pacote, t = RTT + L / R

1 bit do 1 pacote transmitido, t = 0

receptor

Desprezando

durao do ACK tempo de processamento atraso de filas de espera atrasos nos ns intermdios

RTT



Desempenho do rdt3.0stop-and-wait

Exemplo: Ligao de 1 Gbps Tempo de propagao extremo-a-extremo de 15 ms pacote de 1KB

rdt3.0 funciona, mas o desempenho...

Ttransmisso =L (tamanho pacote em bits)

10^9 b/seg= 8 seg

Uemissor: utilizao ou eficincia fraco do tempo que o emissor est ocupado a enviar

U em is s o r

= .0 0 8

3 0 .0 0 8 = 0 .0 0 0 2 7

m ic r o s e c

L / R

R T T + L / R =

8kb/pacote

R (ritmo de transmisso, bps)=

Pacote de 1KB cada 27 mseg - dbito de 37kB/seg numa ligao de 1 GbpsO protocolo de comunicao limita o uso dos recursos fsicos!



Protocolos de janela (em pipeline)

Tcnica de janela (pipeline): o emissor envia mltiplos pacotes de seguida, sem esperar pela confirmao de cada um

Intervalo dos nmeros de sequncia tem de aumentar (do n de bits para a numerao de pacotes)

Armazenamento no emissor e/ou no receptor

Tcnica de janela (pipeline): o emissor envia mltiplos pacotes de seguida, sem esperar pela confirmao de cada um

Intervalo dos nmeros de sequncia tem de aumentar (do n de bits para a numerao de pacotes)

Armazenamento no emissor e/ou no receptor

(a) operao do protocolo stop-and-wait (b) operao do protocolo com pipeline

Duas formas genricas de protocolos de janela: Go-back-N, Repetio Selectiva



Protocolos de janela (pipeline): maior utilizao

1 bit transmitido, t = 0

emissor receptor

ltimo bit do 1 pacotetransmitido, t = L / R

1 bit do pacote chegaltimo bit do pacote chega, envia ACK

ACK chega, enviaprximo pacotet = RTT + L / R

ltimo bit do 2o pacote chega, envia ACKltimo bit do 3 pacote chega, envia ACK

Aumenta a utilizaopor um factor de 3!

0008,0008,30

024,0

/RTT

/3tx ==

+

=

RL

RLU

RTT



Voltar atrs: Go-back-N (GBN)Emissor:

Cabealho do pacote com k-bits para o n de sequncia ([0,2k-1] modulo 2k) Protocolo de janela deslizante (Sliding-window protocol)

janela de tamanho N - at N pacotes consecutivos, ainda no confirmados Janela desliza para a frente ao longo dos nmeros de sequncia medida que recebe ACKs

ACK(n): confirma todos os pacotes at o n de sequncia n ACK cumulativo, podem ser recebidos ACKs duplicados (ver receptor)

temporizador nico para o pacote mais antigo por confirmar

timeout(n): retransmite pacote n e pacotes de n de seq. superior na janela

envia um n mximo de pacotes de seguida, sem esperar por ACKs

nmeros de sequncia



GBN: Mquina de estados estendida do emissor

ACK basedNAK free

base = 1nestseqnum = 1


Num cenrio mais realista

Se janela cheia, pacotes colocados em fila de espera Ou implementao de semforos



Receptor simples: ACK: envia sempre ACK com n de seq. mais elevado para os pacotes recebidos

correctamente e ordenadamente pode gerar ACKs duplicados s tem de memorizar o n de sequncia esperado: expectedseqnum

Pacotes fora de ordem: 1. descarta (no armazena) - no h necessidade de armazenamento (buffers) no receptor2. Reconfirma o ltimo pacote que chegou na ordem

GBN: Mquina de estados estendida do receptor

expectedseqnum = 1Make_pkt(sndpkt,0, ACK, checksum)



GBN em aco



Receptor reconhece (ACKed) individualmente de todos os pacotes correctamente recebidos

armazena pacotes em fila de espera, conforme necessrio, para posterior entrega, em-ordem, camada superior

Emissor apenas reenvia pacotes para os quais o ACK no tenha sido recebido

temporizador no emissor para cada pacote sem ACK Janela do emissor

N nmeros de sequncia consecutivos novamente limita os nmeros de sequncia dos pacotes

enviados, por confirmar

Repetio Selectiva (Selective-Repeat)

Problema com GBN: Se relao (janela N x atrasos no canal) grande => pipeline pode ficar cheio em caso de erro num s pacote



(a) Viso dos nmeros de sequncia no emissor

(b) Viso dos nmeros de sequncia no receptor

Repetio Selectiva: janela do emissor e receptor



1. Dados para enviar: se o prximo n de seq

disponvel cabe na janela, envia o pacote

2. Timeout Temporizador(n) expirou:

reenvia pacote n, reinicia o temporizador

3. ACK(n) em [sendbase,sendbase+N]: marca pacote n como

confirmado se n o pacote mais antigo

por confirmar, avana a base da janela para o prximo pacote por confirmar

Pacote n em [rcvbase, rcvbase+N-1] envia ACK(n)

fora de ordem: armazena

Por ordem: entrega (tambm entrega os pacotes

em ordem na fila de espera)

avana a janela para o prximopacote ainda no recebido

Pacote n em [rcvbase-N,rcvbase-1] ACK(n)

Doutro modo: ignora

receptoremissor

Repetio Selectiva



Repetio Selectiva em aco

Janela do emissor

Janela do receptor



Repetio Selectiva: dilema

Exemplo: Ns de seq.: 0, 1, 2, 3 Dimenso da janela =3

Dados duplicados so passados incorretamente como novos em (a)

O receptor no v diferenas entre os dois cenrios!

Qual a relao entre o nmero de ns de sequncia disponveis e a dimenso da janela? Tamanho janela (2k-1)/2 Na realidade, pode occorrer na rede a reordenao de pacotes



Princpios da transferncia fivel de dados Reviso





transferncia fivel rtd1.0: canais fiveis

rtd2.0 canal introduz erros nos bits

2.1 ACKs e NAKs corrompidos

2.2 Sem NAKs

rtd3.0 canais com erros e perdas

Protocolos com paralelismo (em pipeline)

Go-back-N

Repetio Selectiva

transferncia fivel rtd1.0: canais fiveis

rtd2.0 canal introduz erros nos bits

2.1 ACKs e NAKs corrompidos

2.2 Sem NAKs

rtd3.0 canais com erros e perdas

Protocolos com paralelismo (em pipeline)

Go-back-N

Repetio Selectiva

Documents

Redes de Computadores Redes de Computadores