This thesis investigates three different optimization problems in designing multimedia communication networks. The problems are formulated as integer programming models to investigate analytically where the objective functions are expressed in the operation and/or installation cost of the associated networks.
The first model considers a multicast routing problem to find the minimum cost tree where the whole communication link delay on each path(route) of the tree is subject to a given delay allowance. The problem is formulated as an integer programming problem by using path variables. An associated problem reduction property is then characterized to reduce the solution space. Moreover, a polynomial time column generation procedure is exploited to solve the associated linear programming relaxation with such solution space reduced. Therewith, a branch-and-price algorithm is derived to obtain the optimal integer solution(tree) for the problem. Computational results show that the algorithm can solve practical size problems in a reasonable time.
The second model considers the problem of locating the wavelength converter in an optical Wavelength Division Multiplexing(WDM) network. The problem is formulated as an integer programming problem by using path variables. In order to solve the associated linear programming relaxation which has exponentially many variables, a polynomial time column generation procedure is exploited. Therewith, an LP-based branch-and-bound algorithm is derived to obtain the optimal integer solution for the problem. Computational results show that the algorithm can solve practical size problems in reasonable time.
The last model considers an optimal video file allocation problem in a video-on-demand (VOD) network which is inatwo-level hierarchical topology with the higher level sub-network for distributed servers and the lower level sub-network for local servers. The objective of the problem is to find an optimal video allocation strategy, giving both the optimal types of videos and the optimal copies of each video type to be carried at each distributed server and also each local server, that minimizes the associated total allocation(including inventory) cost subject to each server capacity. The problem is formulated as a mixed integer programming problem with parameters representing all the possible combinations of those video types and copies. In the analysis, the problem is transformed into a binary integer programming problem, for which a column generation problem is exploited to solve the associated linear programming relaxation. The column generation problem is also formulated as a mixed integer programming problem but smaller than the original problem. However, it is NP-Complete. Computational results show that the associated column generation algorithm with three exploited valid inequalities applied and a branch-and-bound procedure can together solve practical size problems in reasonable time.
본 논문에서는 멀티미디어 통신망의 설계 최적화 문제에 관해서 연구한다. 세부적으로 멀티케스트 네트워크에서 경로 설정 문제, 파장 분할 다중화 방식(Wavelength Division Multiplexing)의 네트워크에서 파장 변환기(Wavelength converter)설치 위치 결정 문제 마지막으로 Video-On-Demand 네트웍크에서 비디오 파일 저장 위치 결정 문제에 대해서 다루고 있다.
첫번째 모델은 멀티케스트 네트워크에서 경로 설정 문제이다. 멀티케스트 네트워크는 실시간 멀티미디어 서비스를 제공하기 위한 것으로 트래픽 소스와 목적지 사이의 전송 지연이 중요한 고려 사항이 되고 있다. 본 연구에서는 이러한 전송 지연을 고려하여 대상 문제를 정수 계획법 모형으로 만들었으며, 해 공간(Solution space)를 줄일 수 있는 몇가지 성질을 발견하였다. 이러한 성질을 적용한 후, 열 생성(Column generation) 방법을 이용하여 최적해를 얻을 수 있는 방법을 개발하였다. 여러 가지 예제를 이용하여 개발된 알고리즘의 효율성이 평가되었다.
두번째 모델은 파장 분할 다중화 방식의 네트워크에서 파장 변환기 설치 위치 결정 문제이다. 파장 분할 다분화 방식에서는 광섬유에서 사용할 수있는 파장의 수가 제한되어 있기 때문에 이를 극복하기 위해 파장 변환기가 개발되고 있다. 이러한 변환기를 설치할 위치를 결정하는 문제를 다루었다. 대상 문제는 정수 계획법 모형으로 만들어지며, 열 생성 방법을 이용한 알고리즘을 제시하였다. 열 생성을 위한 부문제를 풀기 위한 최적 알고리즘이 제안되었다. 제안된 알고리즘을 이용하여 여러 가지 예제에 적용하여 효율성이 평가되었다.
세번째 모델은 VOD 네트워크에서 비디오 파일 저장 위치 결정문제이다. 이 문제는 네트워크에 저장되는 비디오 저장 비용과 서비스를 제공하는 서버와 수요자 사이의 전송 지연을 고려하여 최적의 비디오 파일 할당 방식을 정하는 문제이다. 대상 문제는 혼합 정수 계획법 모형으로 만들어지며, 열 생성 방법을 이용한 알고리즘을 제시하였다. 열 생성을 위한 부문제의 최적해를 얻기 위한 방법으로 몇가지 부등식을 제시하였다. 제안된 전체 알고리즘과 부등식을 이용하여 여러 가지 예제에 적용하여 개발된 알고리즘의 효율성이 평가되었다.