An important requirement for the effective scheduling of parallel applications on large heterogeneous clusters is a current view of system resource availability. Maintaining such a view is a time consuming problem, potentially O(N^2). Although CPU availability is relatively easy to monitor, interconnecting network bandwidth varies not only with network topology, but also with message size and even with respect to the load of the communicating nodes. This paper describes a method for predicting a cluster?s network performance for the purpose of scheduling parallel applications. The method generates a cluster-specific network model which can predict the latency of communications between any pair of nodes in linear time and under any computational and/or communication load conditions. The paper also presents the models generated for the Centurion cluster at the University of Virginia and the Orange Grove cluster at Syracuse University. A study of the prediction accuracy of the method under various load conditions by comparison to experimental measurements indicates an average prediction error of approximately 5% with the maximum encountered prediction error of less than 9%.