Multiwavelength optical network is promising to support the increasing bandwidth requirement of the Internet. $\emph{Reconfigurability}$ is one major feature in optical networks. This feature allows us to adapt the network topology to changed network state by reconfiguring the virtual topology with specific $\emph{reconfiguration policy}$. The objective of the reconfiguration that is carried out in response to changing traffic patterns is to improve network performance in terms of maximum throughput. However it is not the best way for maintaining or improving the network performance to reconfigure the virtual topology whenever traffic pattern changes. Therefore a frequency of the reconfiguration is controlled by a proper reconfiguration policy in a way to reduce the disruption of the connections.
Virtual topology design and reconfiguration problem can be solved in mathematical formulation given many constraints and changed traffic matrix. But this optimization problem is known as NP-complete problem. Linear formulation problem by L (Linear Programming) package is optimized and exactly correct but its computation time is not tractable and takes so much time to apply dynamic traffic pattern change in real networks. Heuristic approaches can make solve large problem instances of the virtual-topology design and reconfiguration problem.
Therefore we propose a $\emph{multi-stage reconfiguration}$ mechanism which is multi-stage decision process for reconfiguration instant. This heuristic counts the continual approximation by using predicted traffic with reward-cost function as reconfiguration policy. Therefore it is possible to adapt the virtual topology to the changed traffic positively. And it is based on $\emph{enhanced node exchange}$ algorithm which is proposed in this thesis also. This heuristic algorithm finds the best traffic adaptive virtual topology in a way to minimize the average weighted packet hop count. It is more progressive heuristic than conventional node exchange scheme in lightpath utilization respect.
Simulation results show that our proposed algorithm has more stable characteristics after reconfiguration processes are done according the traffic pattern changes. We quantified the benefits and effectiveness of our proposed approach compared with conventional approach, e.g. more than 80% of each time traffic changes show better performance compared with conventional approach.
In order to evaluate our proposed heuristics, we implemented the reconfiguration mechanism on the MP $\lambdaS$ simulator to rearrange the lightpath dynamically. As a result, it shows the possibility of practical use of our proposed one in the high utilization of network resource and the effectiveness of packet delay over the lightpath by implementing it to the network simulator. By this, we prove that our proposed heuristic shows better performance and efficient.
파장 분할 광 네트워크는 급증하는 인터넷 트래픽의 대역폭을 제공하기에 매우 유용한 기술로 인식되어지고 있다. 가상망 설계와 가상망 재구성은 이러한 광 네트워크의 큰 특징 중의 하나로써 적절한 재구성 정책을 이용하여 가상망의 형태를 다시 조정함으로써 네트워크 상태의 변화에 적절하게 대응할 수 있도록 한다. 가상망 재구성의 목적은 트래픽 패턴이 변화함에 따라 네트워크의 성능이 저하되는 것을 방지하기 위해 가상망을 변화된 트래픽 패턴을 수용하는 형태로 구성하는 것이다. 그러나 네트워크의 성능을 유지하거나 개선하기 위해 트래픽 패턴이 바뀔 때마다 항상 가상망을 재구성하는 것만이 최적의 방법은 아니다. 네트워크 성능 측면에서 가상망 재구성 프로세스 자체에 비용이 소요되므로 적절한 재구성 정책을 통해 경제적인 가상망 재구성이 이루어져야 한다.
일반적으로 가상망의 설계와 재구성 문제는 네트워크를 구성하는 자원과 서비스되는 트래픽 사이의 성능 지수 관련 제한 조건들을 고려하여 모형화 할 수 있다. 그러나 이러한 모형의 최적화 문제는 NP-complete 문제로 잘 알려져 있듯이 네트워크에 적용하기에는 어려운 문제가 존재한다. 상용화된 선형 프로그래밍 패키지를 이용하여 선형 계산 문제가 최적화 될 수는 있으나 네트워크의 규모에 따라 계산 시간은 지수적으로 증가하기 때문에 트래픽 패턴의 변화에 따라 동적으로 재구성 기법을 적용하기가 용이하지 않다. 따라서 여러가지 휴리스틱 방법을 통한 접근이 가상망 설계와 재구성 분야에서 이루어지고 있다.
본 논문에서 제안하는 트래픽 예측 기반의 다단계 재구성 기법은 재구성이 이루어지는 시점의 트래픽 변화 뿐 만이 아니라 앞으로의 트래픽 패턴 변화를 예측하고 이를 반영한 재구성 정책을 결정함으로써 트래픽 변화에 보다 적응할 수 있는 재구성 기법이다. 즉, 재구성을 결정해야 하는 시점에서부터 트래픽 변화의 예측이 가능한 시점까지의 모든 가능한 재구성 경로들 중에서 재구성의 목적과 비용을 둘 다 고려하여 트래픽 패턴이 변화하는 상황에 가장 최적화된 재구성 경로를 결정하게 된다. 그리고 전체의 경로를 이루는 각 시점에서 기존의 휴리스틱들의 단점을 보완한 안정적인 재구성 기법인 개선된 노드 교환 기법을 제시한다.
제안하는 기법이 기존 알고리즘들에 비해 보다 안정적이고 트래픽 변화에 잘 적응할 수 있는 특징을 보여준다는 것을 실험을 통하여 확인하였다. 또한 네트워크의 규모 변화나 토폴로지의 변화에도 유연하게 대응할 수 있으며, 네트워크 자원의 활용과 광경로를 통한 트래픽 전송 지연의 개선에도 큰 효과를 보임을 알 수 있다. 그리고 제안된 기법의 응용성 평가를 위해 네트워크 시뮬레이터에 구현함으로써 제안된 기법들의 실용성과 네트워크 적용성을 보여준다.
