A new look at wireless scheduling with delayed information

The performance of wireless scheduling algorithms directly depends on the availability and accuracy of channel state information (CSI) at the scheduler. As CSI updates must propagate across the network, they are delayed as they arrive at the controller. In this paper, we analyze the effect that delayed CSI has on the throughput performance of scheduling in wireless networks. By accounting for the delays in CSI as they relate to the network topology, we revisit the comparison between centralized and distributed scheduling, which is analyzed as a trade-off between using delayed CSI and making imperfect scheduling decisions. In particular, we prove that there exist conditions under which distributed scheduling outperforms the optimal centralized scheduling policy. We characterize the point at which distributed scheduling outperforms centralized scheduling for tree networks, illustrating the impact of topology on throughput.