This thesis deals with an offline routing problem, which can be used as an explicit routing procedure in MPLS(Multiprotocol Label Switching) network, for traffic engineering. This problem is foiiliulated as an MIP(Mixed Integer Programming) with the objective function which is to minimize the sum of the maximum link utilization for load balancing (link utilization) and the routing cost. Constraints are composed of link capacity restriction and demand requirement that has origin-destination pair, bandwidth requirement and hop restriction. The problem is proved to be NP-hard so that the Lagrangean relaxation method is applied to propose a Lagrangean heuristic. To test the effectiveness & efficiency of the proposed algorithm, computational experiments are performed with numerical instances. The experiment results show that the proposed algorithm solves the problem within a reasonable time.
본 논문은 MPLS(Multiprotocol Label Switching) 네트워크에서 명시적 경로 설정 절차로써 이용될 수 있는 오프라인 라우팅 문제를 다루었다. 이 문제는 부하 분배(Load balancing)을 위한 최대 링크 이용율과 경로 설정 비용의 합을 최소화하는 목적함수를 가진 혼합정수계획법으로 정식화 된다. 제약식은 링크 용량(Capacity) 제약과 출발노드 및 도착노드, 대역폭 (Bandwidth) 요구량, 홉(Hop) 제약을 갖는 수요(Demand)의 요구제약으로 이루어졌다. 이 문제는 NP-hard이므로 라그랑지안 완화법(Lagrangean Relaxation)을 적용하여 라그랑지안 발견적 방법(Heuristic)이 제안된다. 제안된 알고리즘의 효과성과 효율성을 검사하기 위해서 실험이 수행되었다. 실험 결과는 제안된 알고리즘이 수긍할 만한 시간안에 문제를 푼다는 것을 알려준다.
