In this thesis, we propose a combined optimization problem of determining optimal locations of switches and interconnections that can be applied to the area of designing Asynchronous Transfer Mode Local Area Network (ATM-LAN) with emphasis on connection-oriented data service. While pure location design problems have received much attention in the past, the combined location and interconnection problem has escaped the existing literature to our knowledge. The suggested optimization model is formulated as a binary integer programming problem and solved using Lagrangian relaxation technique. By solving the problem, overall network topology and capacities of chosen switches/links are determined. In the model, traffic demands between origin-destination node pairs are assumed known. Linear functions are used for modeling both switch and link costs. According to computational results maximum allowable error range was typically 5-9%. Execution time was around 2-3 minutes for the largest sample problem solved. For further research more accurate cost models should be used. Also, routing-based traffic must be taken into account. Meantime, the proposed formulation can be used in designing practical ATM-LANs.
본 논문에서는 기존에 널리 사용되는 근거리 통신망을 시대적 요구인 고속 다중매체 서비스 실현을 위한 차세대 통신기법인 비동기전송방식 (ATM) 기술을 이용하여 통합, ATM의 주요 특성과 몇 가지 부수적인 특성을 가지는 새로운 통신망을 합리적으로 설계하기 위한 일환으로 토폴로지, 스위치와 링크의 위치 및 용량을 최적으로 구하는 문제를 제기하였다. 제시된 문제는 ATM 표준의 특성을 살려 연결형 트래픽에 중점을 두었으며 이진 정수계획법의 형태로 기술하였다. 라그랑쥐 완화기법을 이용하여 해를 구하였으며 이 때 임의의 최종전달노드 쌍에 대한 트래픽 요구수준이 알려져 있는 것으로 가정하였다. 스위치 및 링크의 비용 모형으로는 선형함수를 사용하였다. 라그랑쥐 완화기법을 적용하여 6-30개의 노드 수를 가지는 다양한 문제들의 해를 구한 결과 5-9% 가량의 최대허용가능 오차를 얻었으며 해를 구하는 시간으로 최대 2-3분 정도 소요됨을 관찰하였다. 향후 본 연구를 개선하기 위하여 현실에 좀 더 부합하는 비선형 형태의 비용 모형을 사용할 필요가 있으며 상이한 형태의 트래픽이 혼재하는 통신망의 경우까지도 함께 고려하는 경우라면 더욱 좋을 것이다. 한편 본 연구에서 제시된 수리적 모형 및 방법만으로도 연결형 통신망을 일차적으로 설계하는데 유용한 도구가 될 것이다.
