[논문]ATM LANE에서의 멀티미디어 방송형 트래픽의 Scalable한 관리를 위한 유전자 알고리즘 응용

김도훈

doi:10.3745/kipstc.2002.9c.5.725

문제 정의

특히 규모성을 제고하기 위하여 LANE 네트워크상에서 독립적으로 운용될 수 있는 가상 LAN인 ELAN 을 구성하여 계층화된 LANE 네트워크 운용하는 경우 직면하게 되는 LANE 분할문제(LANE Partition Problem, LPP)를 정의하였고 이를 해결하기 위한 의사결정모형과 해법을 제안하였다. 네트워크 관리자 관점에서 볼 때, LPP를 통한 ELAN 구성은 재처리되어야 할 방송형 서비스를 최소화하는 것을 목적으로 한다. 이 경우 LPP는 기존의 클러스터 용량제약하의 그래프 분할문제(CGPP)에서 ELAN 구성상의 기술적 특성을 반영하는 제약이 추가된 형태로 모형화되며, 여기서는 이를 일반화된 CGPP라고 하였다.
따라서 최적해를 구하는 것보다는 좋은 실현가능해를 빨리 제공해 줄 수 있는 해법이 현실적으로 더 바람직하다. 본 연구에서는 구현이 간단하고 거의 모든 경우에 적절한 시간 내에 최적해와 유사한 좋은 실현가능해를 제공해 주는 유전자 알고리즘(Genetic Algorithm, GA)을 제공한다. 이하에서는 먼저 LECS 엔진의 핵심인 GA의 설계요소를 간단히 설명하고, GA를 이용한 실험방식과 결과를 4.
본 연구에서는 기존 LANdegacy LAN) 확장에서 발생하는 제문제를 ATM기술을 이용하여 해결하기 위하여 LANE 방식을 도입할 때, LANE 네트워크의 최적 운영방안에 대하여 살펴보았다. 특히 규모성을 제고하기 위하여 LANE 네트워크상에서 독립적으로 운용될 수 있는 가상 LAN인 ELAN 을 구성하여 계층화된 LANE 네트워크 운용하는 경우 직면하게 되는 LANE 분할문제(LANE Partition Problem, LPP)를 정의하였고 이를 해결하기 위한 의사결정모형과 해법을 제안하였다.
않은 실정이다. 본 연구에서는 멀티미디어 환경에서의 계층적 LANE 운용에 초점을 맞추어, 방송형 트래픽의 효율적인 운용을 위한 ELAN 구성 (configuration) 모형과 엔진을 제안한다. 방송형 트래픽을 대상으로 하는 이유는, ELAN 구성에 의한 LANE 네트워크 운용을 살펴볼 때, 방송형 트래픽이 전체 네트워크 성능에 영향을 미치는 정도가 일반(unicast) 트래픽 보다 크기 때문이다.
또한 방송형 트래픽의 동적 변화(dynamic chan- ge)를 반영하기 위하여 짧은 단위시간 마다 ELAN의 재구성 (reconfiguration) 이 요구되므로, 오랜 시간이 소요되는 최적해 탐색법(exact solution method, 예를 들어, [4, 5, 8] 등을참조) 보다는 발견적 탐색법(heuristic)이 개발되어야 한다. 본 연구에서는 성능 및 계산속도 차원에서 GPP에 효과적인 것으로 알려진 유전자 알고리즘(Genetic Algorithm, GA) 을 도입하여 본 문제에 적합하도록 구현한다.
또한 GA를 이용한 문제해결기법을 제공하고, 실제 LANE 네트워크를 운영하는 캠퍼스 네트워크로부터 제공되는 다양한 데이터를 가지고 제안된 수리적 모형과 GA의 성능을 실험한다. 이를 통하여 LANE 네트워크 운용에 관한 유용한 시사점을 얻으며 이에 대해 고찰하고자 한다.
한다. 특히 방송형 트래픽 운영에 고유한 특성을 고려하여 규모성 문제를 보완하는 ELAN 분할문제를 살펴본다. 즉, LANE 네트워크의 시스템 요소들이 규모성 요구에 따른 용량제약하에서 운용될 때, 서로 다른 ELAN간 방송형 트래픽의 재처리 (re-treatment) 규모를 최소화하는 ELAN 구성문제를 다룬다.

가설 설정

여기서는 방송형 데이터 전송에서 서로 다른 ELAN에 속한 LEC 송/수신쌍을 cut-pair 라고 부르고, cut-pair간 방송형 데이터 수요를 재처리 수요 (re-treatment demand)라고 부를 것이다. 또한 재처리 수요가 발생시키는 제반 비용이 cut-pair간 수요량(재처리 수요량)에 비례한다고 가정한다. 따라서 효과적인 ELAN 구성을 위한 LANE 분할문제(LANE Partition Problem, LPP) 의목적은 임의의 두 LEC들이 서로 다른 ELAN에 편성됨에 따라 발생하는 재처리 수요의 총합을 최소화시키는 것이다.
이상에서 살펴 본 LPP는, 먼저 어떤 단위 시구간(unit time interval)에서2)LANE 네트워크 내 모든 LEC 간의 방송형 트래픽 수요가 주어진 것으로 가정한다. 또한 (a) 단위시간 동안 BUS가 감당할 수 있는 방송형 트래픽 규모의 상한(房), (b) 단위시간동안 하나의 LEG?} 받아들일 수 있는 방송형 트래픽 규모의 상한(GJ, (c) 구성가능한 최대 ELAN 개수 化)와 같은 파라미터들이 각 장비의 종류와 용량에 따라 주어지는 것으로 가정한다’ 이 경우 LPP의 실현가능한 ^(fe asible solution)상기한 제약조건들 (a)〜(c)을 만족하도록 LANE 네트워크 내 LEC들이 클러스터링(clustering)된 모양으로 볼 수 있다.

제안 방법

또한 설비용량이 ELAN 구성에 미치는 영향을 분석(민감도 분석, sensitivity analysis)하기 위하여, 현재 사용 중인 제품사양(Cc = 5, 000, (* = 65, 000)을 기준으로 제품사양을 각각 5 등급으로 나누어 실험하였다. 각 제품사양의 조합별로 초기 개체집단을 달리하면서 5번씩 실험하였다. 특히 현 제품사양에 대해서는 서로 다른 세 가지 방송형 트래픽 패턴을 비교하였다.
또한 교차와 돌연변이의 비율은 GA 성능과 속도에 거의 영향을 미치지 않는 것으로 보인다. 따라서 실제 실험에서도 교차와 돌연변이의 비율을 각각 50% 와 10%로 고정하였다.
또한 GA를 이용한 문제해결기법을 제공하고, 실제 LANE 네트워크를 운영하는 캠퍼스 네트워크로부터 제공되는 다양한 데이터를 가지고 제안된 수리적 모형과 GA의 성능을 실험한다. 이를 통하여 LANE 네트워크 운용에 관한 유용한 시사점을 얻으며 이에 대해 고찰하고자 한다.
또한 설비용량이 ELAN 구성에 미치는 영향을 분석(민감도 분석, sensitivity analysis)하기 위하여, 현재 사용 중인 제품사양(Cc = 5, 000, (* = 65, 000)을 기준으로 제품사양을 각각 5 등급으로 나누어 실험하였다. 각 제품사양의 조합별로 초기 개체집단을 달리하면서 5번씩 실험하였다.
있었다. 또한 주요 파라미터인 LEC의 용량과 BUS의 용량이 네트워크 관리차원에서 가지는 영향을 분석하였다. 즉, 최적 ELAN 구성형태가 LEC 용량보다는 BUS 용량에 더 민감하게 반응함을 알 수 있었다.
이 경우 LPP는 기존의 클러스터 용량제약하의 그래프 분할문제(CGPP)에서 ELAN 구성상의 기술적 특성을 반영하는 제약이 추가된 형태로 모형화되며, 여기서는 이를 일반화된 CGPP라고 하였다. 마지막으로 GPP 문제에 대한 해법으로 개발된 유전자 알고리즘(GA)을 수정하여 본 연구의 LPP 모형에 적합한 해법을 개발하였으며, 이를 실제 캠퍼스 LANE 네트워크에 적용한 실험 결과를 소개하였다.
본 연구를 위해 개발된 GA에서는 임의의 실현가능한 해가 그룹-번호 표현방식 (group-number representation meth od)0)] 따라 개체 (chromosome)로 부호화(encoding)된다. 예를 들어, 아래 개체에서 i번째 노드의 값이 s(Mk)이면, 노드 i는 s번째 클러스터에 속함을 나타낸다.
사전실험 결과를 바탕으로, 우선 최대 세대수를 각각 100, 200, 300으로, 개체집단의 규모를 또한 각각 50과 100으로 구분하였다. 또한 설비용량이 ELAN 구성에 미치는 영향을 분석(민감도 분석, sensitivity analysis)하기 위하여, 현재 사용 중인 제품사양(Cc = 5, 000, (* = 65, 000)을 기준으로 제품사양을 각각 5 등급으로 나누어 실험하였다.
특히 방송형 트래픽 운영에 고유한 특성을 고려하여 규모성 문제를 보완하는 ELAN 분할문제를 살펴본다. 즉, LANE 네트워크의 시스템 요소들이 규모성 요구에 따른 용량제약하에서 운용될 때, 서로 다른 ELAN간 방송형 트래픽의 재처리 (re-treatment) 규모를 최소화하는 ELAN 구성문제를 다룬다. 이러한 ELAN 구성문제는 그래프 분할문제(Graph Partitioning Problem, GPP)의 일반화된 형태로 정식화되며, 이 문제 또한 NP-complete 류(class)에 속함을 보일 것이다.
특히 현 제품사양에 대해서는 서로 다른 세 가지 방송형 트래픽 패턴을 비교하였다. 즉, 방송형 트래픽이 균등하게 (uniform) 분포하면서도 많이 발생하는 경우(dense mode, 유형 1)와 적게 발생하는 경우(sparse mode, 유형 2), 그리고 특정 노드를 중심으로 불균등하게 분포하는 경우(hub spike mode, 유형 3)를 서로 비교하였다.
볼 것이다. 특히 GA 계산속도와 성능에 영향을 줄 수 있는 최대 세대수, 개체집단의 규모, 교차와 돌연변이의 비율 등을 집중적으로 비교한다. 또한 최근 m세대 동안 가장 좋은 목적 함수 값을 갖는 개체가 변하지 않으면 최대 세대수 예 도달하기 전에도 GA를 종료할 수 있도록 하였다.
살펴보았다. 특히 규모성을 제고하기 위하여 LANE 네트워크상에서 독립적으로 운용될 수 있는 가상 LAN인 ELAN 을 구성하여 계층화된 LANE 네트워크 운용하는 경우 직면하게 되는 LANE 분할문제(LANE Partition Problem, LPP)를 정의하였고 이를 해결하기 위한 의사결정모형과 해법을 제안하였다. 네트워크 관리자 관점에서 볼 때, LPP를 통한 ELAN 구성은 재처리되어야 할 방송형 서비스를 최소화하는 것을 목적으로 한다.
각 제품사양의 조합별로 초기 개체집단을 달리하면서 5번씩 실험하였다. 특히 현 제품사양에 대해서는 서로 다른 세 가지 방송형 트래픽 패턴을 비교하였다. 즉, 방송형 트래픽이 균등하게 (uniform) 분포하면서도 많이 발생하는 경우(dense mode, 유형 1)와 적게 발생하는 경우(sparse mode, 유형 2), 그리고 특정 노드를 중심으로 불균등하게 분포하는 경우(hub spike mode, 유형 3)를 서로 비교하였다.

대상 데이터

그러나 특정 돌연 변이연산자가 다른 연산자에 비해 명백히 우수하거나 열등한 결과를 제공하지는 않는 것으로 보인다[1, 3]. 따라서 본 연구에서는 구현과 실행이 간단하여 전체 GA의 계산속도에 심각한 영향을 미치지 않는 전치방식⑴을 돌연 변이연산자로 채택한다. 또한 돌연변이가 실현 불가능한 개체를 생성할 경우에는 손상 회복 과정 없이 개체집단(population)에서 제거한다.
본 논문에서는 그 동안 캠퍼스 및 기업형 네트워크의 대안으로 도입이 급속히 진행된 반면에, 실제 운용상의 문제에 대한 경영과학적 연구는 많지 않은 LANE 네트워크를 대상으로 한다. 특히 방송형 트래픽 운영에 고유한 특성을 고려하여 규모성 문제를 보완하는 ELAN 분할문제를 살펴본다.
사전실험은 10개의 노드를 가지는 모의 네트워크를 가지고 시행되었다. 본 연구에서 제안하는 GA는 모든 사전실험에서 매우 빠른 시간 안에 최적해를 찾았으며, 최대 세대수 100에 도달하기 훨씬 이전에 최적해를 발견하였다(이 때 m = 10으로 하였음).
실험대상으로는 모두 37개의 LEC를 가지는 어느 한 대학의 캠퍼스 네트워크를 선정하였다. 이하의 자료는 이 대학의 실제 LANE 네트워크의 주요 파라미터를 정보보안 차원에서 약간 변조한 것이다.

이론/모형

intra-ELAN 트래픽에 속하는지 in- ter-ELAN 트래픽에 속하는지는, 개체표현과 연관된 적절한 자료구조를 참조하여。(|丫|) 내에 파악할 수 있으며, 따라서 해당 개체가 유발하는 총비용은。(|归|) 내에 계산할 수 있다. 또한 세대(generation)를 거듭하면서 최적해에 가까운 개체를 선별해 나가기 위하여, 가장 많이 이용되는 확률 바퀴 (roulette wheel) 방법을 적용한다.

성능/효과

실험 결과의 분석에 앞서서, 실험으로부터 얻어진 기초적인 통계를 소개하면 다음과 같다. GA가 최적해 또는 근사 최적해로 수렴하는 속도는 평균 21.17초(표준편차 7.69초)로, 이는 본 연구에서 제안된 모형과 문제해결기법이 실제 네트워크가 방송형 트래픽 변화에 동적으로 적응하기 위해 필요한 충분한 시간을 확보할 수 있음을 의미한다. 또한 각 실험조합마다 5번씩 반복된 결과에서 얻은 비용함수의 최대 값과 최소 값의 차이는 평균 3% 이내였으며, dense mode의 수요 그래프를 대상으로한 25개의 실험조합에서 6번은 최대값과 최소 값의 차이가 없었다(이 경우, 최적해를 찾았을 가능성이 높다고 판단된다).
한 노드 클러 스터 에 속하는 간선비용의 총합과 클러스터의 크기(클러스터에 포함되는 노드의 수)의 곱이 BUS에서 단위시간 동안 처리해야 될 방송형 트래픽 규모가 되기 때문에, 제약조건 (2)는 이 값이 BUS의 용량 Cb를 초과할 수는 없다는 것을 의미한다. 또한 (3)은 각 노드(LEC)에서 단위시간 동안 동시에 처리해야 하는 최대 방송형 트래픽 규모는 해당 클러스터에 포함되는 간선비용의 총합이 되므로, 이 값이 LEC의 용량 CL 보다는 클 수 없다는 것을 말한다. 결국 LPP는 통상적인 클러스터 용량 제약을 가지는 CGPP[5]에 제약조건 (2)가 추가된 형태의 일반화된 CGPP(generalized CGPP)로 규정된다.
69초)로, 이는 본 연구에서 제안된 모형과 문제해결기법이 실제 네트워크가 방송형 트래픽 변화에 동적으로 적응하기 위해 필요한 충분한 시간을 확보할 수 있음을 의미한다. 또한 각 실험조합마다 5번씩 반복된 결과에서 얻은 비용함수의 최대 값과 최소 값의 차이는 평균 3% 이내였으며, dense mode의 수요 그래프를 대상으로한 25개의 실험조합에서 6번은 최대값과 최소 값의 차이가 없었다(이 경우, 최적해를 찾았을 가능성이 높다고 판단된다).
특히 GA 계산속도와 성능에 영향을 줄 수 있는 최대 세대수, 개체집단의 규모, 교차와 돌연변이의 비율 등을 집중적으로 비교한다. 또한 최근 m세대 동안 가장 좋은 목적 함수 값을 갖는 개체가 변하지 않으면 최대 세대수 예 도달하기 전에도 GA를 종료할 수 있도록 하였다. 여기서 파라미터 m에 대해서도 사전실험을 통하여 적절한 값의 범위를 추정한다.
시행되었다. 본 연구에서 제안하는 GA는 모든 사전실험에서 매우 빠른 시간 안에 최적해를 찾았으며, 최대 세대수 100에 도달하기 훨씬 이전에 최적해를 발견하였다(이 때 m = 10으로 하였음). 또한 교차와 돌연변이의 비율은 GA 성능과 속도에 거의 영향을 미치지 않는 것으로 보인다.
실험 결과, 현재 주먹구구식으로 운용되는 방식에 비해 보다 효율적인 ELAN 구성형태를 발견할 수 있었으며, 결과적으로 보다 적은 수의 ELAN을 관리하면서 운영상의 복잡성을 줄이고 재처리가 필요한 트래픽 규모도 감소시킬 수 있었다. 또한 주요 파라미터인 LEC의 용량과 BUS의 용량이 네트워크 관리차원에서 가지는 영향을 분석하였다.
있음을 알 수 있다. 실험결과 실험대상 세 가지 유형의 트래픽 패턴에 대해서 LANE 네트워크를 7개의 ELAN으로 분할하여 운영하는 것이 최적이라는 결과를 얻었다. 이 결과는 실제로 운영되는 ELAN 갯수인 9보다 적은 7개의 ELAN 을 운영함으로써, 운영상의 복잡성을 줄임과 동시에 cut-pair 의 갯수와 재처리되어야 하는 방송형 트래픽 규모도 감소시킬 수 있음을 보여준다.
실험결과 최대 세대수를 300으로 한 경우에는 모든 경우에서 쵝대 세대수에 도달하기 이전에 근사 최적해(near op timal solution)로 수렴하였으며, 개체집단의 규모를 100으로 하는 것이 약간의 계산속도 증가에 비하여 보다 좋은 결과를 보였다. 이하의 논의에서는 최대 세대수와 개체집단의 규모를 각각 300과 100으로 한 결과만을 소개한다.
실험결과 실험대상 세 가지 유형의 트래픽 패턴에 대해서 LANE 네트워크를 7개의 ELAN으로 분할하여 운영하는 것이 최적이라는 결과를 얻었다. 이 결과는 실제로 운영되는 ELAN 갯수인 9보다 적은 7개의 ELAN 을 운영함으로써, 운영상의 복잡성을 줄임과 동시에 cut-pair 의 갯수와 재처리되어야 하는 방송형 트래픽 규모도 감소시킬 수 있음을 보여준다. 즉, 주어진 트래픽 유형 1, 2, 3 에 대하여 본 연구에서 제안된 LANE 분할방식을 적용함으로써, 기존의 운영방식을 고수할 경우에 발생되는 간선- 컷 규모보다 각각 10.
이 결과는 실제로 운영되는 ELAN 갯수인 9보다 적은 7개의 ELAN 을 운영함으로써, 운영상의 복잡성을 줄임과 동시에 cut-pair 의 갯수와 재처리되어야 하는 방송형 트래픽 규모도 감소시킬 수 있음을 보여준다. 즉, 주어진 트래픽 유형 1, 2, 3 에 대하여 본 연구에서 제안된 LANE 분할방식을 적용함으로써, 기존의 운영방식을 고수할 경우에 발생되는 간선- 컷 규모보다 각각 10.22%, 11.81%, 7.40% 만큼 개선된 결과를 얻었다. 쉽게 예상할 수 있는 바와 같이, hub-spike형 트래픽 분포를 보이는 유형 3의 경우에 개선된 정도가 상대적으로 적으며, 트래픽 분포가 적은(sparse) 유형 2의 경우에 가장 큰 효과를 볼 수 있다.
또한 주요 파라미터인 LEC의 용량과 BUS의 용량이 네트워크 관리차원에서 가지는 영향을 분석하였다. 즉, 최적 ELAN 구성형태가 LEC 용량보다는 BUS 용량에 더 민감하게 반응함을 알 수 있었다. 이는 LEC 장비 선정 (예컨대 용량결정, 가격 대비 효율평가 등)어】 있어서 보다 신중한 의사결정이 요구됨을 의미한다.

후속연구

본 연구에서 제안하는 LPP 모형을 바탕으로, 실제 LANE 및 MPOA 네트워크 관리에서 필요한 여러 정책적 요소들을 고려하는 확장된 실시간 네트워크 운용모형을 개발할 수 있을 것이다. 이는 또한 LECS와 같이 네트워크 관리를 전담하는 서버에 소프트웨어 형태로 탑재되어 네트워크 관리자의 의사결정을 지원하고 자동화하는 목적으로도 활용될 수 있다.
현재 실험대상 LANE 네트워크는 시행착오적(trial-and-error) 방법에 의하여 모두 9개의 ELAN으로 고정적으로 분할되어 운용되고 있다. 본 연구에서는 제안된 LPP 모형과 해법에 의한 실험을 통하여 이러한 주먹구구식 운영을 평가하고보다 발전적인 대안을 제시할 것이다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

ATM LANE에서의 멀티미디어 방송형 트래픽의 Scalable한 관리를 위한 유전자 알고리즘 응용
A Genetic Algorithm Application to Scalable Management of Multimedia Broadcast Traffic in ATM LANE Network 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

ATM LANE에서의 멀티미디어 방송형 트래픽의 Scalable한 관리를 위한 유전자 알고리즘 응용 A Genetic Algorithm Application to Scalable Management of Multimedia Broadcast Traffic in ATM LANE Network 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

김도훈 (12)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

ATM LANE에서의 멀티미디어 방송형 트래픽의 Scalable한 관리를 위한 유전자 알고리즘 응용
A Genetic Algorithm Application to Scalable Management of Multimedia Broadcast Traffic in ATM LANE Network 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper