We present a new paradigm, called ''Global-ISP'' (G-ISP). Its goal is to solve, or at least alleviate, problems of inter-domain routing, such as slow convergence, and lack of QoS and multicast support. One of the most important properties of the proposed paradigm is that it can be gradually deployed on the Internet. A G-ISP can be viewed as an additional ISP that provides transit services to its customers over an overlay network. Because a G-ISP differs from a ''regular'' ISP, some extension to the standard BGP protocol is required. This extension and its effects on the BGP protocol are described in this paper. Algorithms for building a G-ISP overlay network and their applications are also presented.