정보화 사회가 가속화 되어감에 따라 광역 네트워크를 필요로 하게 되었다. 최근 많은 통신 네트워크에서 데이터 트래픽이 급격히 증가하게 된 원인은 새로운 멀티미디어 기술 및 개인 단말시스템의 발전에서 비롯되었다고 할 수 있다. 이로 인해 네트워크의 대역폭(Bandwidth) 확장과 광대역통합망인 WAN(Wide Area Network)에서 효율적인 네트워크 프로토콜을 필요로 하게 되었고 더욱 새로운 응용 서비스의 요구가 발생하였으며 여러 통신 기술(TCP/IP, ATM, SDH/SONET, WDM)들이 발전해 왔다[1,2].

멀티미디어 콘텐츠 응용은 재전송 요청과 수신을 반복하는 일반 데이터 트래픽과 달리 전송 지연에 민감한 특성을 가지며, End-To-End 형태로 구성되어 있는 현재 인터넷 환경에서는 전송되는 전송 스트림의 QoS를 보장하기 위한 여러 연구들이 진행되고 있다.

본 논문에서는 네트워크를 셀 단위로 구분하고 유전 알고리즘을 적용하여 대체 경로를 찾는 알고리즘을 제한하였다. 이는 유전 알고리즘을 전체 네트워크에 적용하였을 때보다 연산시간을 단축할 수 있는 장점이 있을 뿐만 아니라, 네트워크 경로 상에서 특정 라우터가 손상되었을 경우 손상 라우터를 우회하는 대체 경로 설정에 유리한 특성이 있다[3,4].

논문에서 제안한 알고리즘은 목적지에서 인접한 라우터로 이동한 후 일정크기의 셀을 구성하고 일정 크기의 홉만큼 최적경로에 위치한 라우터를 탐색한다. 이 라우터를 중심으로 클러스터의 경계에 위치한 일정크기 홉 간격의 라우터를 검색한 후 역으로 일정크기 홉간격의 라우터를 첫 번째 라우터가 위치한 클러스터를 경계로 탐색한다. 탐색된 라우터들을 기준으로 첫 번째 찾는 방법과 같이 반복 수행하여 셀을 증식시켜 나간다. 이후 생성된 셀들의 공통 영역을 바탕으로 셀 내부에서 유전 알고리즘을 적용하고 도출된 경로로부터 양 셀 간 경합으로 우성인 경로를 취합한다. 이러한 절차를 목적지가 마지막 셀에 포함될 때까지 셀을 증식시키며 수행을 반복한다. 또한, 실험을 통하여 네트워크에서 특정 라우터의 이상으로 대체경로의 설정시 본 논문에 제안한 알고리즘이 기존 Dijkstra 알고리즘이나 기존 유전자 교배연산에 기초한 라우팅유전 알고리즘보다 대체경로 설정에 우수한 지를 분석하였으며 그에 따른 지연시간과 비용(Cost)값을 측정하였다.

유전 알고리즘을 이용한 이동 에이전트 경로 탐색기법은 최단거리 알고리즘의 방향성을 이용하여 라우팅시 최적 경로를 탐색하는 알고리즘이다.

클라이언트로부터 요청된 정보를 전달하기 위해 서버쪽에서는 클라이언트로 최단 경로를 탐색하기 위해 에이전트 컨트롤러를 이용하여 경로에 위치한 라우터들을 검색하고 그들을 통해 서로 간의 최단거리를 검색하도록 하였다. 그리고 노드 장애시 클라이언트 쪽의 “Path Modification”을 통해 장애노드를 포함하고 있는 셀에서 재설정 작업을 시행하도록 하였다.

네트워크 내에서 일정 변심거리에 의해 클러스터형식의 셀을 증식시켜 그 안에서 최저비용을 지불하는 경로를 선택하는데 <그림 1>의 “Internet Route's” 안에 보이는 C₁, C₂, C₃, C₄,⋯, C_n, 들이 제안한 알고리즘에 의해 생성된 셀이며 Cs₁, Cs₂, Cs₃, Cs₄,⋯, Cs_n는 각 셀 간의 중복된 라우터들의 그룹이다.

2.2.1. 동작 모델

본 논문에서 제안한 알고리즘의 기본 동작은 에이전트에 의해 초기화를 진행한 후 셀을 증식하며 각 셀 내의 에이전트들을 통해 셀 내의 유전알고리즘을 이용하여 최적경로를 구하고 인접 셀과 최적경로 비교를 통해 서로 간의 우열을 가리는 과정을 거쳐 목적지까지 도달하는 과정으로 이루어지며, <그림 2>는 이러한 과정을 나타내는 모델이다[5].

2.2.2. 셀 생성 과정

제안한 알고리즘의 셀들은 3-블록(Block)으로 구성되어 있다. 1-블록은 시작 셀의 경계점을 생성하고 다음 라우터로 에이전트를 이주시키는 기능을 수행한다. 2-블록은 경합을 위한 셀 2개로 구성되어 있으며 2개의 셀 중 각각의 유전 알고리즘을 실행을 통한 최단경로를 찾는 기능을 수행하며 3-블록은 관문 역할을 하고 1-블록 역할과 함께 다음 2-블록 계층을 생성하는 역할을 수행한다.

<그림 3>은 제안한 알고리즘에서의 에이전트에 의한 셀 형성에서 3-블록 단계 형태를 나타낸다.

(가) 1-블록

목적지(Destination point)로부터 바로 옆에 인접한 라우터의 에이전트로부터 초기화 과정을 수행한다. 초기화 수행을 시작한 라우터를 중심으로 변심거리 ϵ홉인 기존 알고리즘 경로내의 라우터 Rn를 검색한다.

C₀은 초기화 과정에 의해 생성된 첫 번째 셀의 관할 안에 있는 라우터들의 그룹이이며 그에 대한 영역의 크기는 식 2-3과 같다.

(나) 2-블록

1-블록 과정에서 셀 중심 에이전트 A₁로부터 검색된 라우터 Rn 로부터 ϵ홉이며 시작 에이전트(라우터)와 변심거리 ϵ근처에 포함되는 라우터 1개를 검색한다. 만약 그 라우터가 폭주가 있을 경우나 장애가 발생하였을 경우 주변 근거리에 위치한 라우터를 선별한다. <그림 4>은 셀의 영역에서 셀 에이전트 증식에 대한 그림이다.

검색된 라우터로부터 거리는 ϵ홉이며 시작라우터의 클러스터 경계 근방에 위치하고 있고 이전에 검색된 라우터 R 근처의 라우터를 검색하여 에이전트를 이주한다. 이주된 에이전트에 의해 초기화 과정을 수행한 후 첫 번째 블럭과 두 번째 블록간의 교집합 Cs₁과 Cs₂를 구한다.

그리고 C₁과 C₂의 라우터 그룹의 교집합(τ)을 구한다.

(다) 3-블록

2-블록의 에이전트들간 각각 ϵ홉의 거리에 위치하며 기존 알고리즘 근처에 위치하는 라우터에 에이전트를 이식한다. 다음 절차로 이주된 에이전트에 의해 초기화 과정을 수행하여 각 셀 간의 관할 구역을 설정한 후 2-블록과 3-블록간의 교집합(Cs₃, Cs₄)을 구한다.

집합 Cs₁, Cs₂, Cs₃, Cs₄ 에 대하여 유전 알고리즘을 이용해 시작지점과 마지막 지점을 단위 셀로 하여 최적 경로를 구한다.

<그림 5>는 제안 알고리즘의 적용 예를 나타낸 것으로서, 점선 부분은 기존 라우팅 알고리즘을 적용하여 방향성을 부여한 부분이며, 실선 부분은 기존 라우팅 알고리즘의 방향성을 바탕으로 제안 알고리즘의 수행과정을 나타낸다.

본 논문에서 제안한 알고리즘의 수행 절차를 간단히 살펴보면 다음과 같다.

본 논문에서 제안한 경로탐색 유전 알고리즘의 성능평가를 위해 기존 유전 알고리즘에서 제시한 Munetomo 알고리즘과 최적 경로 탐색 알고리즘인 Dijkstra 알고리즘과의 전송지연 및 처리율을 비교하고 분석하였다. 실험을 위한 시뮬레이션 모델은 네트워크 모델 설정의 민감성을 반영하여 구성에 필요한 기본적인 요소를 포함시켰고 이동 에이전트의 특성을 실험할 수 있도록 검증된 토플로지를 확장하였다[6,7].

셀 범위는 최적 셀 크기의 실험에 의하여 셀 거리를 5로 설정하였으며 그에 따른 셀의 관할 구역을 3으로 설정하였다. 그리고 실험군내의 라우터 군집은 300개로 하였으며 수행횟수는 100으로 하였다. 표 1은 경로 탐색을 위하여 셀의 영역을 구하기 위한 초기 설정을 위한 파라미터를 나타낸다.

3.2.1. 실험에 필요한 셀의 크기 결정

본 논문에서는 300개의 라우터를 갖는 하이브리드토폴로지의 환경의 시뮬레이션 모델에 적합한 셀의 크기를 결정하여야 한다. 제안한 알고리즘에서는 4개 이상의 셀이 형성되어야 실험이 가능하며, 이를 본 실험에 사용된 토폴로지에 적용하면 10홉 이하의 홉 수가 형성된다. 11홉 이상의 홉 수에서는 본 실험에서 요구된 4개 이상의 셀이 형성되지 않기 때문에 본 실험환경에 적합하지 않다.

또한, 4홉 이하 경우는 Control 셀이 셀 간의 중첩부분이 생기지 않으므로 Control 셀이 형성 되지 않으므로 실험 환경을 만족시킬 수 없다. 이에 본 실험을 만족하기 위해서는 홉 수가 5홉에서 10홉 사이에서 셀의 크기를 결정하여야 한다. 실험에서 연산시간이 적을수록 신뢰도가 높아지므로 적용한 셀의 크기는 연산시간이 가장 작은 5홉으로 결정하였다.

3.2.2. 제안한 알고리즘의 대체 경로 설정에 따른 성능 비교 분석

(가) 대체 경로 설정 연산 지연 시간 비교

시뮬레이션 토폴로지 상에서 100번 라우터를 손상시켜 대체 경로를 설정할 때 Dijkstra 알고리즘, Munetomo 알고리즘과 제안한 알고리즘의 대체 경로 설정에 따른 연산 시간을 비교하였다.

<그림 6>은 대체 경로 설정에 따른 연산 시간을 비교한 그래프이다.

이 결과에 따르면 제안한 알고리즘은 연산 시간이 약 0.32초 정도로 나타나며, Munetomo 알고리즘은 약 0.44초, Dijkstra 알고리즘은 약 0.63초로 나타났다. 이는 제안한 알고리즘이 Dijkstra 알고리즘보다 대체 경로 설정에 따른 연산 시간이 약 2배정도 빠르다는 것을 보여 주고 있으며, Munetomo 알고리즘보다는 약 37.5% 정도의 대체 경로 설정 연산 시간이 빠르다는 것을 보여 주고 있다. 이는 제안한 알고리즘은 각 셀 내에서 2순위의 경로 정보를 가지고 있기 때문에 연산 시간이 Dijkstra 알고리즘이나 Munetomo 알고리즘보다 짧은 것이다[8,9].

(나) 대체 경로 처리 비용(cost) 비교

네트워크 경로 상에서 특정 라우터가 손상되었을 경우 손상 라우터를 우회하는 대체 경로를 설정하여야 한다. 본 실험에서는 Dijkstra 알고리즘과 Munetomo 알고리즘과의 대체 경로 설정을 비교 분석해 보았다.

시뮬레이션 토폴로지 상에서 100번 라우터를 손상시켜 Dijkstra 알고리즘, Munetomo 알고리즘과 제안한 알고리즘의 대체 경로가 어떻게 설정되는지 실험해 보았다. 먼저 Dijkstra 알고리즘은 102-168-169-177 로 대체 경로를 설정하여 패킷을 전송하였으며, Munetomo 알고리즘도 Dijkstra 알고리즘과 동일한 대체 경로를 설정하였다. 제안한 알고리즘은 67-99-98-103으로 대체 경로를 설정하였다. <그림 7>에서는 3가지 알고리즘 모두 거쳐 가는 라우터의 수는 기존 2개에서 3개로 증가하였음을 보여주고 있다. 비용(cost)면에서는 Dijkstra 알고리즘과 Munetomo 알고리즘은 기존의 경로보다 대체 경로의 비용(cost)이 146이 증가하였으며 제안한 알고리즘은 115의 비용이 증가함을 알 수 있다. 이것은 비용측면에서 볼 때 제안한 알고리즘이 Dijkstra 알고리즘과 Munetomo 알고리즘보다 비용면에서 31이 감소함을 보여 주고 있다. 이 실험 결과로 볼 때 제안한 알고리즘이 대체 경로 설정에서는 최적 경로 설정 알고리즘인 Dijkstra 알고리즘과 기존 유전 알고리즘인 Munetomo 알고리즘보다 우수하다는 것을 알 수 있다.

대체 경로 설정 이후 전체 경로 비용에서 비교해 볼 때 Dijkstra 알고리즘의 경로 전체 경로 비용은 2,418이고, Munetomo 알고리즘의 경우 전체 경로 비용은 2,494이며, 제안한 알고리즘은 전체 경로 비용이 2,412로 나타났다. 이는 대체 경로가 설정되었을 때 최적성을 비교해 보면 Dijkstra 알고리즘보다 경로 비용이 6(0.63%)이 감소하였고, 대체 경로 설정 이후에서는 기존의 Dijkstra 알고리즘보다 최적성이 우수하다는 것을 알 수 있다. 또한 기존 유전 알고리즘인 Munetomo 알고리즘과 비교해 볼 때 경로 비용이 72(3.25%)가 감소하였는데, 이는 기존 유전 알고리즘보다 최적성이 우수하다는 것을 증명한 것이다. 따라서 제안 알고리즘의 손상경로에 대한 대체 경로 설정 시 비용측면에서의 최적성 성능에 대한 값은 Dijkstra 알고리즘이나 Munetomo 알고리즘보다 우수함을 증명하였다. <그림 7>는 대체 경로 설정에 따른 경로 설정을 나타내고 있다.

본 논문에서는 기존 유전 알고리즘과 이동에이전트에 대해 분석하고 기존 유전 알고리즘보다 향상된 유전 알고리즘을 이용하여 대체 경로 탐색 기능을 향상 시키는 알고리즘을 제안하였다. 이전 연구에서 최적경로 알고리즘으로 알려진 Dijkstra 알고리즘은 네트워크가 손상되었을 경우 대체 경로 설정에 지연이 발생하는 약점이 있었다. 이를 개선하기 위하여 유전 알고리즘을 이용한 대체 경로 설정기능을 추가하여 제안한 경로탐색 알고리즘의 대체 경로 설정 연산시간이 단축됨을 확인할 수 있었다. 이는 손상된 네트워크의 셀 안에서 제 2순위의 경로를 확보하고 있으므로 Dijkstra 알고리즘보다 신속하게 대체경로를 설정하는 기능에서 비롯되었다. 유전 알고리즘의 분산처리를 위해 도입한 라우터 그룹 단위인 셀은 경로 설정시 유전 알고리즘을 시행하는 단위로 전체 네트워크의 탐색 지연시간을 단축하는 방안으로 제시하였다.

실험을 통한 결과는 제안한 알고리즘이 네트워크 경로 상에서 특정 라우터가 손상되었을 경우 손상 라우터를 우회하는 대체 경로 설정에 따른 경로 처리 비용과 연산시간을 Dijkstra 알고리즘과 Munetomo 알고리즘에 비교 분석하였다. 실험 결과 대체 경로 처리비용에서는 제안한 알고리즘이 Dijkstra 알고리즘과 Munetomo 알고리즘보다 대체 경로 설정에 따른 경로처리 비용을 약 27%정도 감소시키며, 대체 경로 설정에 따른 연산시간이 Dijkstra 알고리즘보다 약 2배 정도가 빠르다는 것을 보여 주었다. 이는 라우터의 손상시 대체 경로 설정에서는 본 논문에서 제안한 알고리즘이 Dijkstra 알고리즘이나 Munetomo 알고리즘보다 우수하다고 할 수 있다.