Interconnection and routing modeling on ISP services and networks

Abstract

The Internet is a network of networks owned and operated by a very large number of different companies, known as Internet service providers (ISPs). Extensive interconnection between ISPs makes end-users to presume the global connectivity, whenever they log on to the Internet regardless of which ISP services and networks they use. Therefore the issue of ISP interconnection is expected to be more and more important in the Next Generation Network (NGN), wherein the types of services and networks will be far more diversified. In this thesis, we deal with some new interconnection problems on ISP services and networks that can be considered from a single ISP’s perspective. This thesis falls into three parts. The first part deals with a key decision on its network management for a single ISP, which is to determine not only with which other ISPs to interconnect but also under which agreements. For ISPs, there are three common types of interconnection agreements: private peering, public peering and transit. Commonly given as input data in this situation are: a set of Border Gateway Protocol (BGP) addresses with traffic demands to support, and a set of candidate service providers (private peering/transit providers and Internet exchanges) for the interconnection agreements. Each candidate provider is assumed, besides being capacitated, to have the interconnection cost function as well as the routing information for its related agreement plan. The problem then becomes to find a cost-minimizing set of service providers which meets all addresses’ demands without violating both the capacity and the service quality constraints. We show that the problem is NP-hard, and formulate it as a mixed-integer programming model, for which we propose a heuristic algorithm. Extensive computational experience with as many as eight practical instance scenarios shows the remarkable performance of the proposed algorithm of rapidly generating near-optimal solutions. The second part of this t...