home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.lbl.gov / 2014.05.ftp.ee.lbl.gov.tar / ftp.ee.lbl.gov / email / red_atm.notes < prev    next >
Text File  |  1996-05-29  |  2KB  |  40 lines
  1. Notes on implementing RED with ATM:  Sally Floyd, October 1995.
  2.  
  3. Computing the average queue size in hardware:
  4. This could be done in the background.  This would also avoid the messy 
  5. software algorithm in the paper for taking account of queue idle times.
  6.  
  7. What to do when we detect the first cell of a new packet, and the
  8. average queue size is between the min and max queue threshold
  9. (that is, we have to decide whether or not to drop that packet):
  10.  
  11. One possibility would be to count arriving packets (via counting the
  12. first cell of each arriving packet).  One could increment the counter
  13. once for each arriving packet, and then decide (quickly) whether to
  14. drop that packet.
  15.  
  16. The second possibility, when there was less danger of immediate buffer
  17. overflow, would be to (effectively) increment the counter for each
  18. arriving cell, and therefore to have each cell be equally likely to be
  19. marked. And then when a cell was marked, the switch would wait to
  20. discard the next arriving complete packet of cells for that VC.  In this
  21. way, the chance of a VC being marked would be proportional to the number
  22. of arriving cells for that VC, not to the number of arriving packets.
  23.  
  24. An intermediate strategy would be, when the first cell of a new packet
  25. arrives, to "weight" that packet by the number of cells in either this
  26. packet or the previous packet on that VC (if something like that is easy
  27. to find out about).  In this way, you could still have the chance that a
  28. VC is marked be proportional to the number of arriving cells rather than
  29. the number of arriving packets, and at the same time be asking the
  30. question "should I drop this packet", rather than "should I drop the
  31. next packet that arrives for this VC"?
  32.  
  33. RED allows you to have a large buffer to accomodate transient
  34. congestion, while ensuring that the large buffer won't be full all of
  35. the time.  In doing this, RED ensures that most packet drops are
  36. "controlled" drops, not drops that are forced by a buffer overflow.  So
  37. RED would also work well in conjunction with a packet-discard strategy
  38. for ATM switches.
  39.  
  40.