Избегнување

 на  задушување  

Conges4on  avoidance  
 Behavior  of  a  TCP  Sender  
•  Sender  sends  “N”  bytes  (as  
much  as  credit  allows)  
•  Start  credit  (window  size)  is  
small  
–  To  avoid  overloading  network  
queues  
•  Increases  credit  exponen4ally  
–  To  gauge  network  capability  
 Behavior  of  a  TCP  Receiver  
•  Receiver  schedules  an  ACK  on  
receipt  of  “next  message.”  
•  TCP  acknowledges  the  next  
segment  it  expects  to  receive,  
not  the  last  segment  it  
received.  
–  In  the  example,  N+1  is  blocked,  
so  the  receiver  keeps  
acknowledging  N+1  (the  next  
segment  it  expects  to  receive).  
 TCP  Slow  Start  
•  If  ACK  acknowledges  
something  
–  Updates  credit  and  sends  
•  If  not,  presumes  it  
indicates  a  lost  packet  
–  Sends  first  
unacknowledged  message  
right  away  
–  Halves  current  credit  
(slows  down)  
–  Increases  slowly  to  gauge  
network  throughput  
 Mul4ple  Drops  in  TCP  
•  If  mul4ple  drops  occur  in  the  
same  session:  
–  Current  TCPs  wait  for  4me-­‐out  
–  Selec4ve  acknowledge  may  be  
a  workaround  
–  New  “fast  retransmit”  phase  
takes  several  round-­‐trip  4mes  
to  recover  
 Managing  Interface  Conges4on  
with  Tail  Drop  

•  Router  interfaces  experience  conges4on  when  the  

output  queue  is  full:  
–  Addi4onal  incoming  packets  are  tail-­‐dropped  
–  Dropped  packets  may  cause  significant  applica4on  
performance  degrada4on  
–  Tail  drop  has  significant  drawbacks  
 Tail  Drop  Limita4ons  
•  Tail  drop  should  be  avoided  because  it  contains  
significant  flaws:  
–  TCP  synchroniza4on  
–  TCP  starva4on  
–  No  differen4ated  drop  
 TCP  Synchroniza4on  

•  Mul4ple  TCP  sessions  start  at  different  4mes.  

•  TCP  window  sizes  are  increased.  
•  Tail  drops  cause  many  packets  of  many  sessions  to  
be  dropped  at  the  same  4me.  
•  TCP  sessions  restart  at  the  same  4me  
(synchronized).  
 TCP  Delay,  Jieer  and  Starva4on  

•  Constant  high  buffer  usage  (long  queue)  causes  

delay.  
•  More  aggressive  flows  can  cause  other  flows  to  
starve.  
•  No  differen4ated  dropping  occurs.  
 Summary  
•  TCP  sender  sends  as  many  bytes  as  credit  allows.  
TCP  receiver  acknowledges  the  next  segment  it  
expects  to  receive.  
•  TCP  uses  windowing  and  the  TCP  slow-­‐start  
mechanism  as  its  means  of  controlling  conges4on.  
•  By  default,  routers  resort  to  tail  drop,  relying  on  TCP  
conges4on  controls  when  queues  become  full.  
•  Tail  drop  causes  significant  issues  including  TCP  
synchroniza4on,  starva4on,  and  delay.  TCP  
synchroniza4on  decreases  the  average  u4liza4on  of  
network  links.  
 Random  Early  Detec4on  
•  Tail  drop  can  be  avoided  if  conges4on  is  prevented.  
•  RED  is  a  mechanism  that  randomly  drops  packets  
before  a  queue  is  full.  
•  RED  increases  drop  rate  as  the  average  queue  size  
increases.  
•  RED  result:  
–  TCP  sessions  slow  down  to  the  approximate  rate  of  
output-­‐link  bandwidth.  
–  Average  queue  size  is  small  (much  less  than  the  maximum  
queue  size).  
–  TCP  sessions  are  desynchronized  by  random  drops.  
RED  Profiles  
 RED  Modes  
•  RED  has  three  modes:  
–  No  drop:  When  the  average  queue  size  is  between  0  
and  the  minimum  threshold  
–  Random  drop:  When  the  average  queue  size  is  
between  the  minimum  and  the  maximum  threshold  
–  Full  drop  (tail  drop):  When  the  average  queue  size  is  
at  maximum  threshold  or  above  
–  Random  drop  should  prevent  conges4on  (prevent  tail  
drops)  
 TCP  Traffic  Before  RED  

•  TCP  synchroniza4on  prevents  average  link  u4liza4on  

close  to  the  link  bandwidth.  
•  Tail  drops  cause  TCP  sessions  to  go  into  slow  start.  
 TCP  Traffic  Aker  RED  

•  Average  link  u4liza4on  is  much  closer  to  link  

bandwidth.  
•  Random  drops  cause  TCP  sessions  to  reduce  window  
sizes.  
Applying  Conges4on  Avoidance  
 Summary  
•  RED  is  a  mechanism  that  randomly  drops  packets  before  a  
queue  is  full,  preven4ng  conges4on  and  avoiding  tail  drop.  
•  RED  operates  by  increasing  the  rate  at  which  packets  are  
dropped  from  queues  as  the  average  queue  size  increases.  
•  RED  has  three  modes  of  opera4on:  no  drop,  random  drop,  
and  full  drop  (tail  drop).  
•  With  RED,  TCP  global  synchroniza4on  is  eliminated  and  the  
average  link  u4liza4on  increases.  
•  RED  is  most  useful  in  enterprise  and  service  provider  
networks  on  output  interfaces  where  conges4on  is  
expected  to  occur.  Edge  routers  or  switches  typically  
classify  and  mark  packets  as  they  enter  the  network.  
 Weighted  Random  Early  Detec4on  
•  WRED  can  use  mul4ple  different  RED  profiles.  
•  Each  profile  is  iden4fied  by:  
–  Minimum  threshold  
–  Maximum  threshold  
–  Maximum  drop  probability  
•  WRED  profile  selec4on  is  based  on:  
–  IP  precedence  (8  profiles)  
–  DSCP  (64  profiles)  
•  WRED  drops  less  important  packets  more  
aggressively  than  more  important  packets.  
•  WRED  can  be  applied  at  the  interface,  VC,  or  class  
level.  
 Class-­‐Based  WRED  
•  Class-­‐based  WRED  is  available  when  configured  
in  combina4on  with  CBWFQ  only.  
•  Using  CBWFQ  with  WRED  allows  the  
implementa4on  of  DiffServ  Assured  Forwarding  
PHB.  
•  Class-­‐based  configura4on  of  WRED  is  iden4cal  to  
standalone  WRED.  
WRED  Building  Blocks  
 WRED  Profiles  

•  WRED  profiles  can  be  manually  set.  

•  WRED  has  8  default  value  sets  for  precedence-­‐based  
WRED.  
•  WRED  has  64  default  value  sets  for  DSCP-­‐based  WRED  
 IP  Precedence  and  
Class  Selector  Profiles  
 DSCP-­‐Based  WRED  
(Expedited  Forwarding)  
 DSCP-­‐Based  WRED  
(Assured  Forwarding)  
EXPLICIT  CONGESTION  
NOTIFICATION  
 Explicit  Conges4on  No4fica4on  
•  TCP  conges4on  controls  are  not  suited  to  
applica4ons  that  are  sensi4ve  to  delay  or  packet  
loss.  
•  ECN  (RFC  3168)  removes  need  to  rely  on  packet  
loss  as  a  conges4on  indicator.  
•  ECN  marks  packets  instead  of  dropping  them  
when  the  average  queue  length  exceeds  a  
specific  threshold  value.  
•  Routers  and  end  hosts  can  use  ECN  marking  as  a  
signal  that  the  network  is  congested  and  send  
packets  at  a  slower  rate.  
ECN  Field  Defined  
 ECN  and  WRED  
•  ECN  is  an  extension  to  WRED.  
•  Conges4on  in  WRED  is  indicated  based  on  the  
average  queue  length  exceeding  a  specific  
threshold  value.  
•  If  the  number  of  packets  in  the  queue  is  below  
the  minimum  threshold,  packets  are  transmieed.  
–  Treatment  is  iden4cal  to  a  network  using  only  WRED.  
•  If  the  number  of  packets  in  the  queue  is  above  
the  maximum  threshold,  packets  are  tail-­‐
dropped.  
–  Treatment  is  iden4cal  to  a  network  using  only  WRED.  
 ECN  and  WRED  (Cont.)  
•  If  the  number  of  packets  in  the  queue  is  between  the  
minimum  and  maximum  threshold,  one  of  three  
scenarios  can  occur:  
–  ECN-­‐capable  endpoints  and  WRED  determine  that  the  
packet  should  be  dropped  based  on  the  drop  probability:  
•  ECT  and  CE  bits  for  the  packet  are  changed  to  1  and  the  packet  is  
transmieed.  
–  Non  ECN-­‐capable  endpoints:  
•  The  packet  may  be  dropped  based  on  the  WRED  drop  
probability.  
–  The  network  is  experiencing  conges4on:  
•  Both  the  ECT  and  CE  are  already  set.  The  packet  is  transmieed  
and  no  further  marking  is  required.  
 Module  Summary  
•  By  default,  routers  use  tail  drop  as  a  means  of  conges4on  
control  when  an  output  queue  is  full.  Tail  drop  treats  all  
traffic  equally  and  does  not  differen4ate  between  classes  
of  service.  When  tail  drop  is  in  effect,  packets  are  dropped  
un4l  the  conges4on  is  eliminated  and  the  queue  is  no  
longer  full.  
•  Conges4on  avoidance  techniques,  such  as  RED,  monitor  
network  traffic  loads  in  an  effort  to  an4cipate  and  avoid  
conges4on  at  common  network  boelenecks.  Conges4on  
avoidance  is  achieved  through  packet  dropping.  
•  WRED,  the  Cisco  implementa4on  of  RED,  combines  the  
capabili4es  of  the  RED  algorithm  with  IP  precedence  or  
DSCP.  
•  ECN  is  an  extension  to  WRED  that  enables  flow  control  and  
conges4on  signaling  without  requiring  packet  drops.