Protocolos de Acesso ao Meio - midiacom.uff.brdebora/redes1/pdf2/04_redes1.pdf · protocolo de acesso. ... Passagem de Permissão - Token Passing O token ... permissão livre O momento

1Prof. Débora C. Muchaluat Saade

Mestrado em Engenharia de TelecomunicaMestrado em Engenharia de TelecomunicaççõesõesRedes de Computadores I

DisciplinaDisciplina: : Redes de Computadores I

Protocolos de Acesso ao Meio

Profa. Débora Christina Muchaluat Saade

[email protected]

Protocolos Protocolos de de Acesso ao MeioAcesso ao Meio

Profa. DProfa. Déébora Christina Muchaluat Saadebora Christina Muchaluat Saade

deboramsdeborams@[email protected]

Departamento de Engenharia de TelecomunicaDepartamento de Engenharia de Telecomunicaçções ões -- UFFUFF

6

Redes de Computadores IRedes de Computadores I

Tipos de ProtocolosTipos de Protocolos

��Protocolos de Acesso Baseados em ContenProtocolos de Acesso Baseados em Contençção ão

��Protocolos de Acesso Ordenado sem ContenProtocolos de Acesso Ordenado sem Contenççãoão



7


Protocolos de Acesso baseados em Contenção

Protocolos de Acesso baseados em Contenção

9


Protocolos de Acesso Protocolos de Acesso Baseados em ContenBaseados em Contenççãoão

��Retardo de transferência não limitadoRetardo de transferência não limitado

��Ausência de equidadeAusência de equidade

�� Instabilidade em sobrecargaInstabilidade em sobrecarga



10


Protocolos de Acesso Protocolos de Acesso Baseados em ContenBaseados em Contenççãoão

��AlohaAloha��SlottedSlotted--AlohaAloha��CSMACSMA��CSMACSMA--CDCD��CSMACSMA--CACA

11


AlohaAloha



12


AlohaAloha

15


Timeout + BackoffTransmissor 1

AlohaAloha

RR 11

TempoTT22TT11



16


AlohaAloha

Tempo

RR22

Timeout + Backoff

Transmissor 2

TT11 RR 11TT22

20


AlohaAloha

TT11

TempoTT22

Tempo perdido com colisão



21


AlohaAloha

Tempo

Menor tempo perdido com colisão

22


Slotted AlohaSlotted Aloha



23



TempoTT11 TT22

25



TempoTT11 TT22



26



Tempo ocioso

TempoTT11

27


Aloha X SlottedAloha X Slotted--AlohaAloha

TT11

Tempo ocioso

TT11

Aloha

Slotted-Aloha



28


Aloha X SlottedAloha X Slotted--AlohaAloha

Tempo de Desperdício

Tempo de Desperdício

Aloha

Slotted-Aloha

29


AlohaAloha

��EficiênciaEficiência•• Aloha 18%Aloha 18%•• Slotted Aloha 37%Slotted Aloha 37%

��Não tem equidadeNão tem equidade��Não tem prioridadeNão tem prioridade��Retardo de transferência aleatRetardo de transferência aleatóóriorio�� Instabilidade em sobrecargaInstabilidade em sobrecarga



31


CSMACSMA

Carrier Sense Multiple Access

32


CSMA (Carrier Sense Multiple Access)CSMA (Carrier Sense Multiple Access)



34


CSMACSMA

TempoTT11 TT22

35


CSMACSMA

Tempo

TT11

TT22



36


CSMACSMA

TempoTT11

TT22

37


CSMACSMA

TempoTT11

TT22

Colisão



39


CSMACSMA

RR 11

Tempo


TT11

TT22

40


CSMACSMA

Tempo

RR22 RR22


TT11

TT22

RR 11



41


CSMA 1CSMA 1--Persistente Persistente

EstaEstaçção Ativaão Ativa

TransmiteTransmite

ColisãoColisão??

Sim

Não

Sim

Não

Meio LivreMeio Livre??

Retardo AleatRetardo Aleatóóriorio

43



Meio LivreMeio Livre?? Retardo AleatRetardo Aleatóóriorio

TransmiteTransmite

ColisãoColisão??

Sim

Não

Sim

Não

Retardo AleatRetardo Aleatóóriorio

TTéécnica CSMA Não Persistentecnica CSMA Não Persistente



45


CSMACSMA--NPNP

Tempo

T1

46


Tempo

T1

T2

CSMACSMA--NPNP



47


Tempo

T1

T2

TT33

CSMACSMA--NPNP

48


Tempo

T1

T2

TT33

CSMACSMA--NPNP



49


Tempo

T1

T2

TT33

Tempo ocioso Tempo ocioso

CSMACSMA--NPNP

53


CSMA/CDCSMA/CD

Carrier Sense Multiple Accesswith Collision Detection



54


TT22

CSMA/CDCSMA/CD

TempoTT11

TT33

ColisãoColisãoColisão

55



Meio LivreMeio Livre??

Inicia Inicia TransmissãoTransmissão

Sim

Não

Sim

Não

ColisãoColisão?? InterrompeInterrompeTransmissãoTransmissão

Incrementa contadorIncrementa contadorde de nnúúmeromero de de colisõescolisões

ReforReforççoo dedeColisãoColisão (JAM)(JAM)

Atraso AleatAtraso Aleatóóriorioponderado peloponderado pelo

nnúúmeromero de de colisõescolisões

TerminaTerminaTransmissãoTransmissão

Retransmissão

TTéécnica CSMA/CDcnica CSMA/CD



56


CSMA/CD CSMA/CD -- RetransmissãoRetransmissão

��Espera AleatEspera Aleatóória Exponencial Truncadaria Exponencial Truncada•• se houve colisão, espera tempo aleatse houve colisão, espera tempo aleatóório entre 0 e rio entre 0 e

limitelimite•• o limite o limite éé dobrado a cada colisão sucessiva atdobrado a cada colisão sucessiva atéé o o

nnúúmero mmero mááximo de colisões. Se não conseguir ximo de colisões. Se não conseguir transmitir aborta.transmitir aborta.

•• retardo de transmissão pequeno no comeretardo de transmissão pequeno no começço e o e grande depois, impedindo sobrecargagrande depois, impedindo sobrecarga

•• padrão IEEE 802.3: limite dobra atpadrão IEEE 802.3: limite dobra atéé 10 tentativas, 10 tentativas, depois permanece inalterado atdepois permanece inalterado atéé no mno mááximo 16 ximo 16 tentativastentativas

60


AA BB

CSMA/CDCSMA/CD

Início da transmissãoInIníício da transmissãocio da transmissão



61


AA BB

CSMA/CDCSMA/CD

B detecta o meio livree inicia a transmissão

B detecta o meio livreB detecta o meio livree inicia a transmissãoe inicia a transmissão

62


AA BB

CSMA/CDCSMA/CD




63


AA BB

CSMA/CDCSMA/CD

B detecta a colisãoB detecta a colisãoB detecta a colisão

64


CSMA/CDCSMA/CD

AA BB



65


CSMA/CDCSMA/CD

A recebe o pacote enviado por B, enão sabe que seu pacote sofreu colisãoA recebe o pacote enviado por B, eA recebe o pacote enviado por B, e

não sabe que seu pacote sofreu colisãonão sabe que seu pacote sofreu colisão

AA BB

67


AA BB

CSMA/CDCSMA/CD

Início da transmissãoInIníício da transmissãocio da transmissão



68


AA BB

CSMA/CDCSMA/CD

B detecta o meio livree inicia a transmissão

B detecta o meio livreB detecta o meio livree inicia a transmissãoe inicia a transmissão

69


AA BB

CSMA/CDCSMA/CD




70


AA BB

CSMA/CDCSMA/CD

B detecta a colisãoB detecta a colisãoB detecta a colisão

71


AA BB

CSMA/CDCSMA/CD

A detecta a colisãoA detecta a colisãoA detecta a colisão



72


CSMA/CDCSMA/CD

��M >= 2 C Tp M >= 2 C Tp -- Banda BBanda Báásicasica•• M M éé o tamanho do pacote em bitso tamanho do pacote em bits•• C C éé a taxa de transmissão da rede em bpsa taxa de transmissão da rede em bps•• Tp Tp éé o tempo de propagao tempo de propagaçção do sinal no meio ão do sinal no meio

(considerando retardo de repetidores)(considerando retardo de repetidores)

��M >= 4 C Tp M >= 4 C Tp -- Banda LargaBanda Larga

73


CSMA/CDCSMA/CD

��Eficiência: 98%Eficiência: 98%�� InstInstáável em alto trvel em alto trááfegofego��Retardo aleatRetardo aleatóório não limitadorio não limitado�� InjustoInjusto��Distância mDistância mááxima entre dois nxima entre dois nóós s éé limitada pelo limitada pelo

protocolo de acessoprotocolo de acesso



75


CSMA/CACSMA/CA

Carrier Sense Multiple Accesswith Collision Avoidance

76


CSMA/CACSMA/CA

�� Escuta o meio verificando se estEscuta o meio verificando se estáá livre, se estiver, livre, se estiver, transmite, senão aguarda o fim da transmissãotransmite, senão aguarda o fim da transmissão

�� Depois de cada transmissão, a rede entra no modo de Depois de cada transmissão, a rede entra no modo de intervalos de tempo (slots)intervalos de tempo (slots)

�� Cada estaCada estaçção que deseja transmitir escolhe ão que deseja transmitir escolhe aleatoriamente um slot para iniciar sua transmissãoaleatoriamente um slot para iniciar sua transmissão

�� Quem escolher o menor slot, transmite primeiro e ganha Quem escolher o menor slot, transmite primeiro e ganha o meioo meio

�� Se mais de uma estaSe mais de uma estaçção sortear o mesmo slot => colisãoão sortear o mesmo slot => colisão�� Se nenhuma estaSe nenhuma estaçção transmitir, a rede entra no modo ão transmitir, a rede entra no modo

CSMA comum, podendo ocorrer colisõesCSMA comum, podendo ocorrer colisões�� Detecta colisão pela ausência do ACK (reconhecimento)Detecta colisão pela ausência do ACK (reconhecimento)



77


CSMA/CACSMA/CA

Tempo

Slots CSMAcomum

Slots Slots

80


Protocolos de Acesso Ordenado

Protocolos de Acesso Ordenado



81


Protocolos de Acesso OrdenadoProtocolos de Acesso Ordenado

��Retardo de transferência limitadoRetardo de transferência limitado

�� Justo (Justo (““fairfair””))

��EstEstáável em sobrecargavel em sobrecarga

83


Protocolos de Acesso OrdenadoProtocolos de Acesso Ordenado

��PollingPolling

��Token Passing Token Passing -- Passagem de PermissãoPassagem de Permissão



84


PollingPolling

�� Topologia: barraTopologia: barra�� EstaEstaçção central: controladoraão central: controladora�� EstaEstaçções sões sóó transmitem quando interrogadas transmitem quando interrogadas

pela controladora da redepela controladora da rede�� Se não tiver quadro a transmitir, envia um Se não tiver quadro a transmitir, envia um

quadro de status avisando a controladoraquadro de status avisando a controladora

85


PollingPolling

�� JustoJusto��PrioridadePrioridade��Retardo de transferência limitadoRetardo de transferência limitado��EstEstáável em sobrecargavel em sobrecarga�� Interface simples de pequeno custoInterface simples de pequeno custo��Problema de confiabilidade devido a estrutura Problema de confiabilidade devido a estrutura

centralizadacentralizada�� Interessante quando caracterInteressante quando caracteríísticas das estasticas das estaçções ões

são bem conhecidas, podendo ser usadas para são bem conhecidas, podendo ser usadas para determinar a disciplina de passagem de controledeterminar a disciplina de passagem de controle



95


Passagem de Permissão Passagem de Permissão -- Token PassingToken Passing

��O token (permissão) O token (permissão) éé passado seqpassado seqüüencialmente encialmente de uma estade uma estaçção para outraão para outra

��SSóó quem tem o token pode transmitirquem tem o token pode transmitir��Topologia: anel (Token Ring) ou barra (Token Topologia: anel (Token Ring) ou barra (Token

Bus)Bus)•• na topologia em barra, a ordem lna topologia em barra, a ordem lóógica não gica não éé

necessariamente a ordem fnecessariamente a ordem fíísicasica•• na topologia em anel as ordens lna topologia em anel as ordens lóógica e fgica e fíísica sica

coincidem. coincidem.

96


Token RingToken Ring

��TTéécnica mais antiga paracnica mais antiga para o o anelanel, , proposta emproposta em1969 1969 porpor Farmer e NewhallFarmer e Newhall

��Permissão circulaPermissão circula no no anelanel��Ao querer transmitirAo querer transmitir, a , a estaestaçção espera pela ão espera pela

permissão livrepermissão livre, , altera para ocupadaaltera para ocupada e e transmite transmite seusseus dados dados em seguidaem seguida

��A A transmissoratransmissora éé responsresponsáável pela retirada da vel pela retirada da mensagemmensagem do do anelanel e e pela inserpela inserçção daão da nova nova permissão livrepermissão livre

��O O momentomomento de de inserinserççãoão de de umauma nova nova permissão permissão livrelivre no no anel varia conformeanel varia conforme o o tipotipo de de operaoperaççãoão



97



�� Single PacketSingle Packet�� Single TokenSingle Token�� Multiple TokenMultiple Token

Single Packet



TR

Single Packet

L

TR

Single Packet

L



TR

Single Packet

L

TR

Single Packet

L



TTRR

Single Packet

O

R T

Single Packet

O



R T

Single Packet

O

R T

Single Packet

O



R T

Single Packet

O

R T

Single Packet

O



R T

Single Packet

O

TR

Single Packet

O



TR

Single Packet

O

TR

Single Packet



R T

Single Packet

O

R T

Single Packet

O



Single Packet

L

Single Packet

L



Single Packet

L

T

R

Single Packet

O



T

R

Single Packet

O

T

R

Single Packet

O



Single Token

TR

Single Token

L



TR

Single Token

L

TR

Single Token

L



TR

Single Token

L

TR

Single Token

O



R T

Single Token

O

R T

Single Token

O



R T

Single Token

O

R T

Single Token

O



R T

Single Token

O

R T

Single Token

O



TR

Single Token

O

TR

Single Token

O



TR

Single Token

L

R T

Single Token

L



R T

Single Token

L

T

R

Single Token

O



T

R

Single Token

O

T

R

Single Token

O



Multiple Token

T1R 1

Multiple Token

L



T1R 1

Multiple Token

L

Multiple Token

T1R 1

L



Multiple Token

T1R 1L

Multiple Token

T1R 1O



Multiple Token

T1R 1

O

Multiple Token

T1R 1

O



Multiple Token

T1R 1

O

Multiple Token

T1R 1

O



Multiple Token

T1R 1

O

L

Multiple Token

T1R1

O

L



Multiple Token

T1R 1

T2

R 2

O

L

Multiple Token

T1R 1

T2

R 2

O

O



Multiple Token

T1R 1

T2

R 2

O

O

Multiple Token

T1R 1

T2

R 2

O

O



Multiple Token

T1R 1

T2

R 2

O

O

L

Multiple Token

T1R 1

T2

R 2

O

O

L



Multiple Token

T1R 1

T2

R 2

OL

Multiple Token

T1R 1

T2

R 2

O

L



Multiple Token T2

R 2

O

L

Multiple Token T2

R 2

L



Multiple Token T2

R 2

L

Multiple Token T2

R 2

L



Multiple TokenT2

R 2

L

Multiple Token

L



172



�� EficiênciaEficiência�� EquidadeEquidade�� PrioridadePrioridade�� Retardo de transferênciaRetardo de transferência�� Estabilidade em sobrecargaEstabilidade em sobrecarga

173


Latência do AnelLatência do Anel

��Latência = soma do retardo dos repetidores e do Latência = soma do retardo dos repetidores e do tempo de propagatempo de propagaçção no anelão no anel

��Podem existir tantos bits circulando quanto sua Podem existir tantos bits circulando quanto sua latência permitirlatência permitir

��A latência pode ser aumentada introduzindo um A latência pode ser aumentada introduzindo um buffer de retardo em qualquer estabuffer de retardo em qualquer estaççãoão



174


��Se a latência for desprezSe a latência for desprezíível, os três vel, os três tipos de operatipos de operaçção têm o mesmo ão têm o mesmo desempenhodesempenho

��O instante de tempo em que a O instante de tempo em que a estaestaçção termina de transmitir ão termina de transmitir ééigual ao instante em que chega o igual ao instante em que chega o úúltimo bit transmitido de volta a ltimo bit transmitido de volta a origemorigem

ComparaComparaçção entre os ão entre os Tipos de OperaTipos de Operaçção do Token Ringão do Token Ring

175


�� L= L= latêncialatência; t = tempo de ; t = tempo de transmissãotransmissão de 1 de 1 quadroquadro

�� Se L Se L ≤≤≤≤≤≤≤≤ t, single token e multiple t, single token e multiple token token são mais eficientes que são mais eficientes que single packetsingle packet

�� O O instanteinstante de tempo de tempo em queem que a a estaestaççãoãoterminatermina de de transmitirtransmitir éé maior ou igualmaior ou igualao instante em que chegaao instante em que chega o o primeiroprimeiro bit bit transmitidotransmitido de de voltavolta a a origemorigem




176


�� L= L= latêncialatência; t = tempo de ; t = tempo de transmissãotransmissão de 1 de 1 quadroquadro

�� Se L Se L > t, multiple token > t, multiple token éé maismaiseficiente queeficiente que single token single token queque éémais eficiente quemais eficiente que single packetsingle packet

�� O O instanteinstante de tempo de tempo em queem que a a estaestaççãoãoterminatermina de de transmitirtransmitir éé menor quemenor que o o instante em que chegainstante em que chega o o primeiroprimeiro bitbittransmitidotransmitido de de voltavolta a a origemorigem


Documents

Protocolos de Acesso ao Meio - midiacom.uff.brdebora/redes1/pdf2/04_redes1.pdf · protocolo de acesso. ... Passagem de Permissão - Token Passing O token ... permissão livre O momento