Overhead in Communication Systems as the Cost of Constraints

This dissertation develops a perspective for studying overhead in communication systems that contrasts the traditional viewpoint that overhead is the 'non-data' portion of transmissions. By viewing overhead as the cost of constraints imposed on a system, information-theoretic techniques can be used to obtain fundamental limits on system performance. In principle, protocol overhead in practical implementations can then be benchmarked against these fundamental limits in order to identify opportunities for improvement. We examine three sources of overhead that have been studied in both information theory and networking using different models and metrics. For multi-access communication systems, we compute constrained capacity regions for two binary additive channels with feedback and develop inner and outer bounds on the capacity region of the packet collision channel with feedback that appear to be tight numerically. We develop bounds on the protocol overhead required to meet an average delay constraint and then use these bounds to characterize rate-delay tradeoffs for communicating a bursty source over a noisy channel. Finally, we study information-theoretic security in timing channels and show that non-zero secrecy rates can be achieved over the wiretap timing channel using a deterministic encoder.