Rate adaptation using acknowlegement feedback: throughput upper bounds

We consider packet-by-packet rate adaptation to maximize the throughput over a finite-state Markov channel. To limit the amount of feedback data, we use past packet acknowledgements (ACKs) and past rates as channel state information. It is known that the maximum achievable throughput is computationally prohibitive to determine. Thus, in this paper we derive two upper bounds on the maximum achievable throughput, which are tighter than previously known ones. We compare the upper bounds with a known myopic rate-adaptation policy. Numerical studies over a wide range of SNR suggest that the myopic rate-adaptation policy is close to the upper bounds and may be adequate in slowly time-varying channels.