Node mobility and physical channel effects cause the quality of links in wireless networks to fluctuate randomly. At the network layer, these changes are accommodated by the control information (overhead) of routing protocols. We provide lower bounds on the minimum average control overhead of deterministic routing protocols. When routing devices use noisy, out-of-date, or guess topology information, routing errors will occur. The number of "routing errors" experienced by well known routing schemes grows non-trivially with increased estimation noise. Route error growth is a novel characterization of protocol robustness for switched packet networks. This work motivates an information theoretic view of routing protocols.