In this paper we propose a rate-efficient peer-topeer architecture for video multicasting over the Internet. The limited capacity of the Internet hosts and the heterogeneous property of their access links are the main challenges of the peer-to-peer video multicasting over the Internet. Although, the rateoptimized overlay tree construction is a NP-hard problem, we propose a number of distributed and efficient protocols for rate-efficient overlay tree construction. Our proposed protocols include efficient join, improvement, overlay tree refinement and an optimum rate allocation protocol. The simulation results show the efficiency of the proposed protocols in rate-efficient overlay tree construction. We show that through combination of the efficient join protocol, tree refinement operations and an optimum rate allocation algorithm we can achieve a suboptimum overlay tree.