Interference is not noise

This paper looks at the problem of designing wireless medium access algorithms. Inter-user interference at the receivers is an important characteristic of wireless networks. We show that decoding (or canceling) this interference results in significant improvement in the system performance over protocols that either treat interference as noise, or explicitly avoid interference at the receivers by allowing at most one of the transmitters in its range to transmit. This improvement in performance is realized by means of a medium access algorithm with: (a) polynomial computational complexity per timeslot, (b) polynomially bounded expected queue-length at the transmitters, and (c) a throughput region that is at least a polylogarithmic fraction of the largest possible throughput-region under any algorithm operating using that treats interference as noise. Thus, the hardness of low-delay network scheduling (a result by Shah, Tse and Tsitsiklis [1]) is an artifact of explicitly avoiding interference, or treating it as noise and can be overcome by a rather simple medium access algorithm that does not require information theoretic "block codes".