In this paper, we define the routing overhead as the amount of information needed to describe the changes in a network topology. We derive a universal lower bound on the routing overhead in a mobile ad-hoc network. We also consider a prediction-based routing protocol that attempts to minimize the routing overhead by predicting the changes in the network topology from the previous mobility pattern of the nodes. We apply our approach to a mobile ad-hoc network that employs a dynamic clustering algorithm, and derive the optimal cluster size that minimizes the routing overhead, with and without mobility prediction. We believe that this work is a fundamental and essential step towards the rigorous modeling, design and performance comparisons of protocols for ad-hoc wireless networks by providing a universal reference performance curve against which the overhead of different routing protocols can be compared.