Network virtualization is a technology of running multiple heterogeneous network architectures on the shared substrate network. One of the crucial algorithmic components in network virtualization is virtual network embedding that provides a way to allocate the physical network resources, e.g., link bandwidth and CPU to virtual network requests. Despite significant research efforts on virtual network embedding in wired network, little attention has been made to that in wireless networks, which is becoming important due to the rapid growth of wireless networks and the need to share those networks among different business sectors/users. In this paper, we study the root causes of new challenges of virtual network embedding in wireless networks, and propose a new embedding algorithm that efficiently use the resources of the physical substrate network.
네트워크 가상화란 하나의 공통 물리 네트워크에서 여러 가지 이질적인 네트워크들을 서로 간섭 없이 동시에 동작시키는 기술이다. 네트워크 가상화 기술을 이용하면 연구자는 하나의 네트워크에서 여러 개의 네트워크 실험을 동시에 진행할 수 있고, 어떤 인터넷 서비스 제공자는 서로 다른 컨텐츠 제공자들 에게 자신의 네트워크 자원을 빌려 줄 수 있다. 이 외에도 많은 응용분야가 있는 네트워크 가상화 기술은 미래 인터넷의 핵심 기술 중 하나로 손꼽히고 있다. 가상 네트워크 임베딩 문제란 구현하고자 하는 가상 네트워크들을 물리 네트워크에 효율적으로 매핑 및 자원 할당하는 방법을 찾는 문제이다. 이 문제는 현재까지 거의 유선 물리네트워크 환경에서만 고려되었데, 본 학위논문에서는 무선 물리 네트워크에서의 가상 네트워크 임베딩 문제에 대한 연구를 다루었다.
무선 네트워크에 존재하는 링크 간 간섭으로 인해 임베딩 문제는 무선 네트워크에서 더 복잡해진다. 첫째, 유선 네트워크에서는 어떤 임베딩에 대해 그것이 실현 가능한지를 쉽게 확인 할 수 있으나, 무선 네트워크에서의 어떤 임베딩에 대한 실현가능성을 확인 하는 문제는 NP-Hard 문제로 연역 될 수 있다. 본 학위논문에서는 이에 대해 실현가능한 임베딩에 대한 두 가지 충분조건을 제시하며, 이를 이용해 근사적으로 임베딩의 실현가능성을 판명한다. 둘째, 무선 네트워크 환경에서는 주어진 가상 네트워크 임베딩 문제에 대한 여러 가지 대안들에 대해 어떤 것이 더 적합한지 판단하는 것이 모호할 수 있다. 한 가상 네트워크를 임베딩 함으로써 물리 네트워크의 사용 가능한 자원량이 감소하게 되므로 이 감소량이 적을 수록 더 좋은 임베딩 방법이라 할 수 있다. 유선 네트워크 에서는 이 값을 쉽게 구할 수 있지만, 무선 네트워크에서는 간섭의 영향에 의해 이를 정확하게 산출하는 것이 거의 불가능하다. 이에 대해 본 학위논문에서는 무선 네트워크에서의 임베딩에 대한 새로운 성능 측도를 제시하며, 그 측도를 바탕으로 가중 길이에 기반한 효율적인 임베딩 방법을 제안한다.
