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 thesis presents an interprovider service class mapping framework for a single ISP providing end-to-end quality of service (QoS) across multiple differentiated services (DiffServ) networks. Although DiffServ model has been prevailed as a scalable solution to provide QoS over the Internet, QoS is yet to be widely deployed. A key factor holding back widespread QoS adoption is the absence of suitable methodologies to identify a set of feasible paths meeting the QoS requirement between two end-users. Such a feasible path is generated by checking in a hop-by-hop manner that the customer’s QoS requirement can effectively be mapped into the existing service classes specifically defined by each intermediary ISP on the end-to-end connection. The obvious challenge in this process lies in significant inconsistencies in class specifications defined by ISPs. The framework we therefore address encompasses a mechanism of generating feasible paths with end-to-end QoS guarantees, and a set of functions mediating the inconsistent class definitions in order to smooth the process for the interprovider service class mapping.
The last part of this thesis considers a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. Although this part deals with a somewhat different subject from the above two parts, they have something in common in solution approaches. Apply for its solution is an approach based on column generation, hitherto successful only to the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the column generation technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to get an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in the quality of solutions generated and in the solution time.
인터넷은 네트워크들의 네트워크로, 매우 많은 수의 각기 다른 회사들, 일명 인터넷 접속서비스 제공사업자들 (Internet Service Providers, ISPs), 에 의해서 소유되고 운영되고 있다. 전세계 모든 사업자들이 서로 직간접적으로 상호접속하고 있어, 최종 사용자들은 그들이 어떤 ISP 서비스와 네트워크를 사용하던지 간에 인터넷에 접속할 때마다 보편적 연결성을 기대하게 된다. 따라서 인터넷 상호접속 이슈는 서비스들과 네트워크들이 좀 더 다양해질 것으로 보이는 차세대 네트워크(Next Generation Network, NGN) 또는 광대역 통합망(Broadband convergence Network, BcN)에서 그 중요성이 더욱 증대될 것으로 전망된다. 본 논문에서는 하나의 사업자 관점에서 고려될 수 있는 ISP 서비스와 네트워크에 관한 몇 가지 새로운 상호접속 문제들을 다루고 있다.
본 논문은 세 가지 주요 파트들로 나뉜다. 첫 번째 파트는 하나의 서비스 사업자가 자신의 네트워크를 관리하는데 있어 중요한 의사결정문제를 다루고 있는데, 이는 자신의 고객 트래픽을 교환하기 위해 어떤 다른 사업자들과 어떤 상호접속 협약을 맺을 것인지를 결정하는 것이다. 서비스 사업자들 간에는 세 가지 일반적인 형태의 상호접속 협약들, 사적 동등접속(Private peering), 공공교환 동등접속(Public peering), 중계접속(Transit), 이 존재한다. 이러한 상황에서 그 문제는 일반적으로 다음과 같은 입력정보가 주어진다. 1) 의사결정 사업자가 지원하는, 즉 전송하거나 받는, 트래픽 수요들의 BGP(Border Gateway Protocol) 주소지들의 집합과 2) 그 세 가지 상호접속 협약들에 대해 협약 가능한 사업자들의 집합(사적 동등접속 및 중계접속 사업자들, 공공교환점들). 각 협약가능 사업자는 접속 용량에 대한 제약이 주어지며, 관련 협약 계획에 따른 경로 정보 및 상호접속 비용 함수를 가지고 있다고 가정된다. 그러면 그 문제는 서비스의 질과 용량 제약을 위배하지 않으면서 모든 주소지들의 수요들을 만족하는 서비스 제공자들의 최소 비용 집합을 구하는 것이 된다. 우리는 그 문제가 계산 복잡도(Computational complexity) 측면에서 NP-hard임을 보이고, 혼합정수계획(Mixed-integer programming) 모델을 세우며, 그 모델에 대한 발견적 해법을 제안한다. 여덟 개의 현실적인 시나리오들을 가지고 이루어진, 포괄적인 실험 결과는 그 제안된 알고리즘이 빠른 시간 내에 근사 최적해들을 제공함을 보여주고 있다.
본 논문의 두 번째 파트는 하나의 서비스 사업자가 다수의 DiffServ 네트워크들을 거쳐 종단간(End-to-end) 서비스 질(Quality of service, QoS)을 제공하기 위한 사업자간 서비스 클래스 매핑(Mapping) 구조(Framework)를 제안하고 있다. DiffServ 모델은 현재 인터넷 상에서 QoS를 제공하는 확장성(Scalable) 있는 해법으로 각광받고 있지만, QoS는 아직 널리 확산되지 못하고 있다. QoS 확산을 저해하는 주요 요인들 중 하나는 종단간 사용자들간의 QoS 요구사항을 만족하는 가능 경로들을 확보하는 적당한 방법론이 없다는 것이다. 그러한 가능 경로는 고객 QoS 요구사항이, 종단간 경로 상의 각 중계 사업자에 의해 개별적으로 정의된 서비스 클래스들로 적절히 매핑될 수 있는지 매 홉(Hop-by-hop)마다 체크함으로써 생성된다. 이러한 프로세스에서 분명한 어려움은 사업자간에 정의된 클래스들의 명세가 판이하게 다르다는 것이다. 그러므로 우리가 제시하고자 하는 구조는 종단간 QoS가 보장된 가능 경로들을 생성하는 메커니즘 및 사업자간 서비스 클래스 매핑 프로세스를 원활하게 하기 위해 불일치된 클래스 정의들을 조정하는 함수들을 포함하고 있다.
본 논문의 마지막 파트는 다양한 용량, 고정비, 변동비를 가지는 복수 차량 유형들을 고려한 차량경로문제를 다루고 있다. 비록 이 파트가 위의 두 파트와 다소 다른 주제를 다루고 있지만, 해 접근방법 면에서 공통점을 가지고 있다. 우리는 그 문제에 대한 하나의 해법으로, 지금까지 서비스 시간대 제약이 존재하는 차량경로문제에만 성공적으로 적용되어 왔던 열생성(Column generation) 기반의 접근방법을 제안한다. 먼저 최적 정수해에 근접한 선형계획해(Linear Programming (LP) solution)를 제공할 수 있도록 그 문제에 대한 정수계획모델을 제시하고, 그것의 선형계획완화문제(LP relaxation)를 열생성 기법으로 푼다. 우리는 효과적으로 가능 열들을 생성하기 위해 전형적인 차량경로문제에 개발되었던 두 가지 동적계획(Dynamic programming) 개념들을 약간 수정하여 사용한다. 이렇게 얻어진 최적해에 근접한 하한을 가지고, 하나의 가능 정수해를 얻기 위해 분지-한계(Branch-and-Bound)법을 수행한다. 기존의 벤치마크 실험 예제들을 가지고 이루어진 실험결과는 우리의 접근방법이 기존의 모든 다른 알고리즘들보다 해의 질이나 시간 면에서 뛰어난 성능을 보임을 뒷받침해주고 있다.
