Peer-to-Peer media streaming service has gained tremendous momentum in recent years. However, a number of challenges intrinsic in Peer-to-Peer media streaming have not been addressed. In this paper, we propose a peer-to-peer substrate for supplying ondemand media streaming service, called LRONet, which mainly addresses the key technical issue constructing a locality-aware P2P overlay network with high scalability and manageability. Based on modeling the underlying physical network as a random graph with power-law distributions, we theoretically analyze the performance of LRONet. Numerical results show that LRONet can fully utilize the locality of underlying physical network so that the bandwidth consumption can be effectively saved.