Controle de congestionamento

Prévia do material em texto

2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
CAMADA	
  DE	
  REDE	
  
Controle	
  de	
  Conges<onamento	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   1	
  
Sarah Thomaz 
 
sarah@dca.ufrn.br 
 
Universidade Federal do Rio Grande do Norte 
Departamento de Engenharia da Computação e Automação 
DCA0113 – Redes de Computadores 
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
Camada	
  de	
  Rede	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   2	
  
CAMADA	
  FÍSICA	
  
CAMADA	
  DE	
  REDE	
  
CAMADA	
  DE	
  ENLACE	
  
CAMADA	
  DE	
  TRANSPORTE	
  
CAMADA	
  DE	
  APLICAÇÃO	
  
1 
2 
3 
4 
5 
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Introdução	
  
•  Roteamento	
  com	
  conhecimento	
  do	
  tráfego	
  
•  Controle	
  de	
  acesso	
  
•  Controle	
  de	
  tráfego	
  
•  Corte	
  de	
  carga	
  
Conteúdo	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   3	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Quando	
  há	
  um	
  número	
  excessivo	
  de	
  pacotes	
  trafegando	
  pela	
  
rede	
  podem	
  ocorrer	
  atrasos	
  ou	
  perdas	
  que	
  prejudicam	
  seu	
  
desempenho	
  
•  Tipicamente	
  resultado	
  da	
  saturação	
  dos	
  buffers	
  dos	
  roteadores	
  
•  Este	
  estado	
  da	
  rede	
  é	
  chamado	
  conges2onamento	
  
•  As	
  camadas	
  de	
  rede	
  e	
  transporte	
  possuem	
  responsabilidades	
  
de	
  lidar	
  com	
  conges<onamento	
  
•  Controle	
  de	
  conges2onamento	
  tem	
  como	
  obje<vo	
  garan<r	
  
que	
  a	
  rede	
  consiga	
  lidar	
  com	
  o	
  tráfego	
  oferecido	
  
Introdução	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   4	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Colapso	
  de	
  Conges<onamento:	
  
Introdução	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   5	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Controle	
  de	
  conges<onamento	
  vs	
  Controle	
  de	
  fluxo	
  
•  Controle	
  de	
  conges2onamento	
  
•  Garan<a	
  de	
  que	
  a	
  rede	
  seja	
  capaz	
  de	
  transportar	
  o	
  tráfego	
  oferecido	
  
•  É	
  uma	
  questão	
  global,	
  envolvendo	
  o	
  comportamento	
  de	
  toda	
  a	
  rede	
  
•  Controle	
  de	
  fluxo	
  
•  Está	
  relacionado	
  ao	
  tráfego	
  entre	
  um	
  transmissor	
  em	
  par<cular	
  e	
  um	
  
receptor	
  em	
  par<cular	
  (ponto	
  a	
  ponto)	
  
•  Garan<a	
  de	
  que	
  um	
  transmissor	
  rápido	
  não	
  transmita	
  dados	
  numa	
  
velocidade	
  maior	
  do	
  que	
  o	
  receptor	
  seja	
  capaz	
  de	
  tratá-­‐los	
  
Introdução	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   6	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Controle	
  de	
  conges<onamento	
  vs	
  Controle	
  de	
  fluxo	
  
•  Controle	
  de	
  conges2onamento	
  
•  Garan<a	
  de	
  que	
  a	
  rede	
  seja	
  capaz	
  de	
  transportar	
  o	
  tráfego	
  oferecido	
  
•  É	
  uma	
  questão	
  global,	
  envolvendo	
  o	
  comportamento	
  de	
  toda	
  a	
  rede	
  
•  Controle	
  de	
  fluxo	
  
•  Rede	
  com	
  links	
  de	
  1Mbps,	
  1000	
  computadores	
  
•  Metade	
  deles	
  tentando	
  transferir	
  a	
  100Kbps	
  
•  Excede	
  capacidade	
  total	
  da	
  rede	
  
Introdução	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   7	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Polí<cas	
  que	
  afetam	
  o	
  conges<onamento	
  
Introdução	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   8	
  
Camada	
   Polí2cas	
  
Transporte	
   •  Polí<ca	
  de	
  retransmissão	
  
•  Polí<ca	
  de	
  detecção	
  de	
  quadros	
  fora	
  de	
  ordem	
  
•  Polí<ca	
  de	
  ACK	
  (reconhecimento)	
  
•  Polí<ca	
  de	
  controle	
  de	
  fluxo	
  
Rede	
   •  Circuitos	
  virtuais	
  vs	
  datagramas	
  
•  Polí<ca	
  de	
  enfileiramento	
  de	
  pacotes	
  
•  Polí<ca	
  de	
  descarte	
  de	
  pacotes	
  
•  Algoritmo	
  de	
  roteamento	
  
•  Gerenciamento	
  do	
  tempo	
  de	
  vida	
  dos	
  pacotes	
  
Enlace	
   •  Polí<ca	
  de	
  retransmissão	
  
•  Polí<ca	
  de	
  detecção	
  de	
  quadros	
  fora	
  de	
  ordem	
  
•  Polí<ca	
  de	
  ACK	
  (reconhecimento)	
  
•  Polí<ca	
  de	
  controle	
  de	
  fluxo	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Fatores	
  que	
  causam	
  conges2onamento	
  nas	
  redes	
  
1.  Processamento	
  lento	
  ou	
  largura	
  de	
  banda	
  baixa	
  
•  Processadores	
  lentos	
  nos	
  roteadores	
  e/ou	
  enlances	
  com	
  largura	
  de	
  
banda	
  baixa	
  geram	
  filas	
  nos	
  buffers	
  
2.  Enlaces	
  de	
  saída	
  compar<lhados	
  
•  Se	
  o	
  buffer	
  é	
  pequeno,	
  pacotes	
  serão	
  perdidos	
  
•  Se	
  aumentar	
  o	
  buffer,	
  mais	
  -meouts	
  acontecerão	
  até	
  todos	
  os	
  
pacotes	
  serem	
  transmi<dos	
  com	
  sucesso,	
  gerando	
  duplicações	
  
Introdução	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   9	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Conges2onamento:	
  A	
  carga	
  é	
  (temporariamente)	
  maior	
  do	
  
que	
  os	
  recursos	
  (em	
  uma	
  parte	
  da	
  rede)	
  podem	
  tratar	
  
•  Duas	
  formas	
  de	
  tratar	
  o	
  conges<onamento:	
  
•  Aumentar	
  os	
  recursos	
  
•  Reduzir	
  a	
  carga	
  
•  Escala	
  do	
  tempo	
  para	
  impedir	
  o	
  conges<onamento:	
  
Introdução	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   10	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Forma	
  mais	
  básica	
  de	
  se	
  evitar	
  conges<onamentos:	
  
•  Criar	
  uma	
  rede	
  que	
  combine	
  bem	
  o	
  tráfego	
  que	
  ela	
  
transporta	
  
•  Enlaces	
  e	
  roteadores	
  atualizados	
  
•  Recursos	
  adicionados	
  dinamicamente:	
  
–  A<vando	
  roteadores	
  reservas	
  
–  Habilitando	
  linhas	
  usadas	
  apenas	
  como	
  backups	
  
•  Técnica	
  chamada	
  de	
  provisionamento	
  
•  Escala	
  de	
  tempo	
  de	
  meses,	
  controlada	
  pelas	
  tendências	
  de	
  tráfego	
  a	
  
longo	
  prazo	
  
Provisionamento	
  da	
  Rede	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   11	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Os	
  algoritmos	
  de	
  roteamento	
  podem	
  levar	
  em	
  consideração	
  
pesos	
  fixos	
  ou	
  variáveis	
  para	
  as	
  arestas	
  da	
  rede	
  
•  Ex:	
  Hops	
  (fixo),	
  atraso	
  (variável)	
  
•  U<lizando	
  fatores	
  variáveis	
  é	
  possível	
  adaptar	
  as	
  rotas	
  de	
  
acordo	
  com	
  a	
  carga	
  
•  Carga	
  (número	
  de	
  pacotes)	
  
•  Atraso	
  de	
  propagação	
  
•  Atraso	
  médio	
  de	
  enfileiramento	
  
•  Assim,	
  caminhos	
  com	
  menor	
  peso	
  favorecerão	
  caminhos	
  
menos	
  sobrecarregados	
  
Roteamento	
  com	
  Conhecimento	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   12	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Possível	
  problema:	
  Oscilação	
  das	
  tabelas	
  de	
  roteamento	
  
Roteamento	
  com	
  Conhecimento	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   13	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Técnica	
  u<lizada	
  em	
  redes	
  de	
  circuitos	
  virtuais	
  
•  Serviços	
  orientados	
  a	
  conexão	
  
•  A	
  ideia	
  é	
  simples:	
  não	
  monte	
  um	
  novo	
  circuito	
  virtual	
  a	
  menos	
  
que	
  a	
  rede	
  possa	
  transportar	
  o	
  tráfego	
  adicional	
  sem	
  ficar	
  
conges<onada	
  
•  Assim,	
  a	
  tarefa	
  é	
  es<mar	
  quantos	
  circuitos	
  caberão	
  dentro	
  da	
  
capacidade	
  da	
  rede	
  sem	
  causar	
  conges<onamento	
  
Controle	
  de	
  Acesso	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   14	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  O	
  controle	
  de	
  acesso	
  pode	
  ser	
  combinado	
  ao	
  roteamento	
  com	
  
conhecimento	
  de	
  tráfego	
  
•  Considera-­‐se	
  rotas	
  em	
  torno	
  dos	
  pontos	
  crí<cos	
  como	
  parte	
  do	
  
estabelecimento	
  de	
  uma	
  conexão	
  
Controle	
  de	
  Acesso	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES15	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Outra	
  estratégia	
  para	
  contornar	
  o	
  conges<onamento	
  é	
  fazer	
  
com	
  que	
  os	
  transmissores	
  reduzam	
  suas	
  transmissões	
  em	
  
situações	
  crí<cas	
  (prevenção	
  de	
  conges<onamento)	
  
•  Dois	
  problemas	
  a	
  serem	
  resolvidos:	
  
1.  Determinar	
  quando	
  o	
  conges<onamento	
  é	
  iminente	
  
2.  Os	
  roteadores	
  precisam	
  no2ficar	
  os	
  transmissores	
  que	
  estejam	
  
causando	
  o	
  conges<onamento	
  em	
  tempo	
  hábil	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   16	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Determinar	
  quando	
  o	
  conges<onamento	
  é	
  iminente:	
  
•  Monitoramento	
  dos	
  recursos	
  da	
  rede:	
  
1.  Médias	
  de	
  u<lização	
  dos	
  enlaces	
  de	
  saída	
  
2.  Enfileiramento	
  de	
  pacote	
  em	
  buffer	
  
3.  Número	
  de	
  pacotes	
  perdidos	
  em	
  função	
  de	
  buffering	
  insuficiente	
  
•  Das	
  3	
  alterna<vas	
  a	
  segunda	
  é	
  mais	
  ú2l.	
  A	
  1ª	
  não	
  está	
  
diretamente	
  relacionada	
  ao	
  conges<onamento,	
  uma	
  média	
  de	
  
50%	
  de	
  u<lização	
  do	
  enlace	
  pode	
  ser	
  pouco	
  para	
  um	
  tráfego	
  
constante,	
  mas	
  pode	
  ser	
  muito	
  para	
  um	
  tráfego	
  altamente	
  
variável.	
  Na	
  3ª	
  o	
  conges<onamento	
  já	
  terá	
  sido	
  estabelecido	
  
quando	
  os	
  pacotes	
  forem	
  perdidos	
  	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   17	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Determinar	
  quando	
  o	
  conges<onamento	
  é	
  iminente:	
  
•  Monitoramento	
  dos	
  recursos	
  da	
  rede:	
  
2.  Enfileiramento	
  de	
  pacote	
  em	
  buffer	
  
•  Se	
  d	
  >	
  threshold	
  então	
  reporte	
  conges2onamento	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   18	
  
Valor instântaneo do comprimento da fila 
Quão rápido o roteador vai esquecer dos valores antigos 
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Os	
  roteadores	
  precisam	
  no2ficar	
  os	
  transmissores	
  
que	
  estejam	
  causando	
  o	
  conges<onamento	
  em	
  
tempo	
  hábil	
  
•  Os	
  roteadores	
  precisam	
  iden<ficar	
  os	
  transmissores	
  
corretos	
  e	
  no<ficá-­‐los	
  sem	
  sobrecarregar	
  uma	
  rede	
  que	
  já	
  
está	
  conges<onada	
  (ou	
  prestes	
  a	
  ficar)	
  
•  Estratégias:	
  
–  Pacotes	
  reguladores	
  (choke	
  packets)	
  
–  Pacotes	
  reguladores	
  hop	
  a	
  hop	
  
–  No<ficação	
  explícita	
  de	
  conges<onamento	
  (ECN)	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   19	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Pacotes	
  reguladores	
  
•  O	
  modo	
  mais	
  direto	
  de	
  no<ficar	
  um	
  transmissor	
  sobre	
  o	
  
conges<onamento	
  é	
  comunicar-­‐lhe	
  diretamente	
  
•  Roteador	
  seleciona	
  um	
  pacote	
  conges<onado	
  e	
  envia	
  um	
  pacote	
  
regulador	
  de	
  volta	
  ao	
  host	
  de	
  origem	
  
•  O	
  pacote	
  original	
  pode	
  ser	
  marcado	
  (bit	
  no	
  cabeçalho)	
  de	
  modo	
  a	
  não	
  
gerar	
  mais	
  pacotes	
  reguladores	
  adiante	
  no	
  caminho	
  
•  Um	
  host	
  recebendo	
  um	
  choke	
  packet	
  deve	
  reduzir	
  seu	
  tráfego	
  para	
  
aquele	
  des<no	
  
•  Para	
  evitar	
  o	
  aumento	
  da	
  carga	
  na	
  rede	
  durante	
  um	
  momento	
  de	
  
conges<onamento,	
  o	
  roteador	
  pode	
  enviar	
  pacotes	
  reguladores	
  em	
  um	
  
ritmo	
  lento	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   20	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Pacotes	
  reguladores	
  
•  Padrão	
  
•  Somente	
  o	
  host	
  origem	
  do	
  pacote	
  tem	
  seu	
  tráfego	
  regulado	
  
•  Hop	
  a	
  hop	
  
•  Tem	
  efeito	
  em	
  todo	
  hop	
  que	
  o	
  pacote	
  regulador	
  passa	
  até	
  chegar	
  ao	
  
host	
  origem	
  (alívio	
  imediato	
  do	
  ponto	
  de	
  conges<onamento)	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   21	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Pacotes	
  reguladores	
  
a)  Afetando	
  apenas	
  a	
  origem	
  
b)  Afetando	
  hop	
  a	
  hop	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   22	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  No2ficação	
  explícita	
  de	
  conges2onamento	
  
•  ECN	
  (Explicit	
  Conges-on	
  No-fica-on)	
  
•  Usado	
  na	
  Internet	
  
•  Não	
  envia	
  pacotes	
  adicionais	
  
•  Ao	
  invés	
  disso,	
  “marca”	
  um	
  pacote	
  (cabeçalho)	
  que	
  ao	
  
chegar	
  no	
  des<no	
  será	
  u<lizado	
  para	
  alertar	
  a	
  necessidade	
  
de	
  no<ficação	
  ao	
  transmissor	
  
•  A	
  no<ficação	
  será	
  então	
  adicionada	
  em	
  um	
  pacote	
  de	
  
resposta	
  do	
  receptor	
  ao	
  transmissor	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   23	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  No2ficação	
  explícita	
  de	
  conges2onamento	
  
Controle	
  de	
  Tráfego	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   24	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Quando	
  nenhum	
  dos	
  métodos	
  anteriores	
  fizer	
  o	
  conges<onamento	
  
desaparecer:	
  corte	
  de	
  carga	
  
•  Analogia:	
  rede	
  elétrica	
  -­‐>	
  blackout	
  em	
  certas	
  áreas	
  para	
  salvar	
  a	
  rede	
  como	
  um	
  todo	
  
•  Quando	
  os	
  roteadores	
  estão	
  inundados	
  de	
  pacotes	
  que	
  não	
  podem	
  
manipular,	
  eles	
  simplesmente	
  os	
  descarta	
  
•  Questão	
  principal:	
  Quais	
  pacotes	
  descartar?	
  
•  Polí2ca	
  do	
  vinho:	
  quanto	
  mais	
  velho	
  melhor	
  
•  Ex:	
  Transferência	
  de	
  arquivo	
  
•  Polí2ca	
  do	
  leite:	
  quanto	
  mais	
  novo	
  melhor	
  
•  Ex:	
  Mídia	
  em	
  tempo	
  real	
  
•  Polí2ca	
  da	
  prioridade:	
  Marcar	
  os	
  pacotes	
  para	
  indicar	
  a	
  rede	
  qual	
  a	
  importância	
  
deles	
  (descartando	
  assim	
  os	
  menos	
  importantes)	
  
•  Detecção	
  aleatória	
  prematura	
  (RED)	
  
Corte	
  de	
  Carga	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   25	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Detecção	
  Aleatória	
  Prematura	
  
•  RED	
  (Random	
  Early	
  Detec-on)	
  
•  Consiste	
  em	
  descartar	
  pacotes	
  antes	
  que	
  seja	
  tarde	
  demais	
  
•  Os	
  roteadores	
  mantem	
  uma	
  média	
  acumulada	
  do	
  tamanho	
  
de	
  suas	
  filas	
  
•  Quando	
  o	
  tamanho	
  médio	
  (AvgLen)	
  da	
  fila	
  em	
  algum	
  enlace	
  
ultrapassa	
  determinado	
  patamar	
  (minThreshold),	
  o	
  enlace	
  é	
  
considerado	
  conges<onado	
  e	
  uma	
  pequena	
  fração	
  dos	
  
pacotes	
  é	
  descartada	
  aleatoriamente	
  
Corte	
  de	
  Carga	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   26	
  
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Detecção	
  Aleatória	
  Prematura	
  
Corte	
  de	
  Carga	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   27	
  
MinThreshold MaxThreshold 
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Detecção	
  Aleatória	
  Prematura	
  
Corte	
  de	
  Carga	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   28	
  
Avr = média de tamanho da fila 
MaxThres = threshold máximo 
MinThres = threshold mínimo 
 
2014.2	
  
Sarah	
  Thomaz	
  2014.2	
  
•  Camada	
  de	
  Rede:	
  Qualidade	
  de	
  Serviço	
  
•  Como	
  adequar	
  as	
  necessidade	
  de	
  rede	
  das	
  
aplicações?	
  
Próxima	
  Aula	
  
DCA0113	
  .	
  REDES	
  DE	
  COMPUTADORES	
   29