Abstract: By taking the popularity character of the media program and the cost of the transmission network into consideration, a novel caching utility function is proposed. A Network Cost Based streaming media cache allocation and replacement (NCB) algorithm is designed for multi-server streaming application. Simulation proves that, by employing the NCB algorithm, the cache hit rate can be improved obviously and the total network cost can be decreased effectively. In the Internet streaming application environment, where the network connections between content servers and caching proxy are heterogeneous, the amount of streaming programs is huge, the NCB shows good performance.