The Internet is composed of many distinct networks, operated by independent Internet Service Providers (ISPs). The traffic and economic relationships of ISPs are mainly decided by their routing policies. However, in today's Internet, overlay routing, which changes traffic routing at the application layer, is rapidly increasing and this challenges the validity of ISPs' existing agreements. We study here the economic implications of overlay routing for ISPs, using an ISP interconnection business model based on a simple network. We then study the overlay traffic patterns in the network under various conditions. Combining the business model and traffic patterns, we study the ISPs' cost reductions with Bill-and-Keep peering and paid peering. We also discuss the ISPs' incentive to upgrade the network under each peering strategy.

Multihoming is widely used by Internet service providers (ISPs) to obtain improved performance and reliability when connecting to the Internet. Recently, the use of overlay routing for network application traffic is rapidly increasing. As a source of both routing oscillation and cost increases, overlay routing is known to bring challenges to ISPs. In this paper, we study the interaction between overlay routing and a multihomed ISP's routing strategy with a Nash game model, and propose a routing strategy for the multihomed ISP to alleviate the negative impact of overlay traffic. We prove that with the proposed routing strategy, the network routing game can always converge to a stable state, and the ISP can reduce costs to a relatively low level. From numerical simulations, we show the efficiency and convergence resulting from the proposed routing strategy. We also discuss the conditions under which the multihomed ISP can realize minimum cost by the proposed strategy.