Some Theorems on the Instability of the Exponential Back-Off Protocol

摘要

A martingale method is used to study the backlog of packets awaiting to be retransmitted using the 'exponential backoff protocol'. Under certain conditions it is shown that the backlog is a positive submartingale whose expectations become infinite as time goes to infinity i.e. the system is unstable. On the other hand it is shown that the expected number of packets that have been blocked k times remains finite for all time and this extends a result of Hajek.