[General boards] [Fall 2018 courses] [Summer 2018 courses] [Winter 2018 courses] [Older or newer terms]

Random Early Detection(RED)


For RED, do we need to remember the formula for RED Drop Probabilities for final exam?


Not the exact formula. However, you should remember the general idea (it is zero if the buffer is not very full, it will start increasing after an average value and it becomes one if the average is too high.


Does it begin to increase after THE queue length average or at the minimum threshold?


It begins to increase once the average queue length surpasses the minimum threshold. Thats part of the reason it can be tolerant of short bursts but not long term congestion.


RED only looks at average queue (i.e., buffer occupancy) and not the current value of it. If this value is greater than the minimum threshold, it may drop the packet with a probability that depends on the average queue. If the average is greater than the maximum, the probability will be 1 (i.e., the packet will be dropped).


When it reaches probability of 1, does it mean all packets get dropped? That part is fuzzy to me.


Yup ! think about what that means: a drop probability of 1 means that you’re guaranteed to drop the packet each time


Yes, you are dropping every packet. Note that the idea is to send feedback faster and it usually take sometime after a packet is dropped for the sender to recognize it (it was demonstrated in the slides animation, in case you attended the classes!). Therefore, it makes sense to start dropping packets and sending feedback even before the buffer is full, because even though you send the feedback, you still receive a high volume of packets in the near future until the senders recognized the drop (through duplicate acks or timeouts) and reduce their rate. In other words, if the buffer size is increasing for some time and it is almost full (more than maximum threshold), you can be almost sure that this trends continue and the buffer will be completely full. So even if you do not drop these packets, you will have to drop future packets. Furthermore, because we are considering the average, usually the actual occupancy is higher than the average. On the other hand, if you drop every new packet ,the actual occupancy will start to decrease (because you continue to remove packets that are processed from the queue without adding anything new), which will ultimately reduces the average and you will stop dropping all packets and allow some packets to go into the buffer.