EDP들의 참조 테이블을 이용한 실용적인 경로 설정 및 파장 할당 알고리즘

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 정보통신 / 31권 / 2호 / 123 ~ 130페이지
· 저자명 : 김명희, 방영철, 정민영, 이태진, 추현승

초록

경로 설정 및 파장 할당(Routing and Wavelength Assignment) 문제는 파장 할당 전송 기법(Wavelength Division Multiplexing)을 기반으로 하는 광 네트워크에서 중요한 분야이다. 경로 설정 및 파장 할당 문제는 선형 프로그램(Linear Programming)과 그래프 컬러링(Graph Coloring)의 조합으로 해결되거나, 경로 선택에 기반한 그래프 알고리즘에 의해서 해결된다. 이와 같은 방법은 복잡하며 휴리스틱 알고리즘(heuristic algorithm)이 요구된다. 본 논문에서는 각각의 연결 요구에 대한 최대한의 EDPs(Edge Disjoint Paths)를 구함으로써 경로 설정 및 파장 할당 문제를 효율적으로 해결하는 새로운 방법을 제안한다. 이렇게 구한 EDPs는 참조 테이블에 저장되고 가중치 매트릭스의 갱신에 사용된다. 각 연결 요구에 대한 경로는 순서대로 가중치 매트릭스를 참조하여 결정한다. 본 논문에서 제안하는 알고리즘이 현재 실질적으로 효율적이라 알려진 BGAforEDP(Bounded Greedy Approach for EDP)보다 약 50%의 수행 시간 내에 같거나 작은 파장 수를 사용하여 연결 요구를 만족시켜주고 있음을 시뮬레이션을 통해서 확인할 수 있다.

참고자료

· 없음