Accurate monitoring for the link bandwidth usage of network is important to a variety of network applications. In this paper, a monitoring model on the bandwidth usage of a given set of links is first proposed so as to minimize the overhead imposed by the monitoring procedure on the underlying network. Secondly it is proved that the problem of finding the monitoring model with a minimum overhead is NP-complete. Finally the model is extended by exploiting the flow constraints to further reduce the overhead for monitoring the link bandwidth usage.