컴퓨터의 이용이 통신기술의 발달과 함께 다양화, 고도화되면서 분산형 통신망의 효과적 설계 및 운영은 최근들어 많은 관심을 끌고 있다. 특히 통신망이 제공하는 다양한 서어비스의 질을 좌우하는 자 관리시스템(operating system)중 효과적인 경로선정(routing) protocol의 설계는 통신량 통제(flow control) 방식과 함께 매우 중요한 부분을 차지하고 있다.
본 연구는 이러한 효과적인 routing protocol의 설계 및 시스템 분석에 필요한 분석적 도구를 제공하는데 그 목적을 둔다.
연구대상은 음성전송이나 화일(file)전송 등에 쓰일 수 있는 경로선정 알고리즘(routing algorithm)의 개발과 시스템의 여러 모수(parameter) 값의 변화에 따른 서어비스 질의 변화를 예측하는 민감도 분석이다.
이를 위한 이론적 기초로서 다중선택 혼합 정수계획(multiple choice mixed integer programming), 승산식의 penalty 시스템, Kuhn-Tucker 최적화 조건에 대한 implicit function theorem 등이 이용되었다.
본 연구를 그 이론적 배경에 따라 구분하면 다음과 같다.
(1) 다중선택 혼합정수 계획문제를 풀기 위한 발견적 해법(heuristic)의 개발
(2) 불연속 해공간(discrete solution space)를 갖는 경로선정문제를 풀기 위한 해법의 개발
(3) 전송선의 용량, 각 switching node 사이의 통신량, 전송선의 error rate, 등의 변화 및 전송선의 고장이 통신망의 성능과 서어비스의 질에 미치는 영향을 분석하기 위한 수학적 기법의 개발
첫째, 다중선택 혼합정수 계획문제를 풀기위해 개발된 발견적 해법은 최적 경로선정이나 최적 통신량 배분문제의 목적변수가 선형인 경우에 적용될 수 있는데 그 효율성은 범용 패키지인 APEX III와의 비교를 통해서 입증되었다.
둘째, 불연속 해공간을 갖는 문제로서 음성이나 화일전송의 경로선정문제를 풀기 위한 해법역시 비록 최적해를 보장할 수는 없으나 문제의 난이도를 고려해 볼 때 매우 고무적인 효과를 보여 주고 있다. 더우기 그 이론적 배경이 되는 승산식의 penaly 시스템은 비슷한 형태로 안정화되는 여러 다른 분야의 문제에도 효과적으로 적용될 수 있다.
마지막으로 여러 시스템 모수에 대한 민감도 분석은 Kuhn-Tucker 최적화 조건에 관한 implicit function theorem이 경로선정이나 통신량 배분문제에도 효과적으로 사용될 수 있음을 보여 주었다. 분석을 가능케 하기 위해 실제 가동중인 통신망에서의 통신량 배분형태는 이론적인 최적배분형태(optimal static flow configuration)와 근사적으로 일치한다고 가정하였으며 이를 통해 문제를 multicommodity network flow 문제로 정식화하였다. 대개의 한계분석(marginal analysis)이 그러하듯이 본 연구도 여러 시스템 모수의 변화가 극소량이라는 가정으로부터 출발하였는데 몇가지 예제를 통하여 비교적 적지 않은 양의 변화에 대해서도 그 결과는 성공적으로 적용될 수 있음이 확인되었다.
결과적으로 본 연구에서 제시한 여러 분석적 기법들은 효율적인 경로선정 알고리즘의 설계나 시스템의 보다 완벽한 분석에 그 이론적 기초를 제공하고 있는데 앞으로 이를 바탕으로 한 본격적 연구가 기대된다.
