Technology is moving forward at an ever-quickening pace all fields of communications. As individuals around the world gain connectivity, try to keep up with the newest cellular phone or the fastest Internet service, all these separate communications networks are converging into what are called next convergence networks. The next convergence network will be the convergence of wired and wireless networks. As a long time, wired communication and wireless communications have been mutually separated. But, as the diversities of communication devices are increasing, the need of customers’ unification of several different services is incrementing.
This thesis investigates two problems in related with multicast and resource allocation in next generation network. We present formulations and the heuristics.
First, Reliable overlay multicast trees for private Internet broadcasting with multiple sessions are discussed and heuristic is proposed to solve the reliable overlay multicast trees. With rapid advances of computing technologies and high speed networks, various high volume multimedia services have become popular in the Internet. Private Internet broadcasting is a typical way to support these services and overlay multicast technology is known to be a promising solution to support this method. In an overlay multicast network, members are dynamically joining or leaving their multicast group. To reduce frequent updates of multicast members and provide a reliable multicast route, overlay multicast trees are investigated. The problem is formulated as a binary integer programming which maximizes the minimum link reliability for all multicast sessions. Tabu search heuristic is developed with repeated intensification and diversification. Robust computational result is obtained that is comparable to the optimal solution and applicable in real time.
Second, the problem of maximizing the minimum end-to-end data rate considering traffic demand in multi-hop and multi-channel wireless mesh network is discussed and heuristic is proposed to solve the problem. Wireless mesh network is built on a mix of fixed and mobile nodes interconnected via wireless links to form a large-scale multi-hop wireless communication network. In near future, wireless mesh network will provides attractive services such as public services, peer-to-peer communication, mobile Internet access and video-on-demand (VOD) in rural areas because of low costs. In wireless mesh network, each node has multiple network interface cards and there are several orthogonal channels based on IEEE 802.11 standards. In this paper, we consider source-destination pairs in wireless mesh network that each pair has traffic demand. The problem is formulated as a binary integer programming which maximizes the minimum end-to-end data rate considering traffic demand. Tabu search heuristic is developed with repeated intensification and diversification. Robust computational result is obtained that is comparable to the optimal solution and applicable in real time.
유선과 무선통신의 장대한 발전이 있어 왔다. 최근에는 유무선 네트워크의 컨버전스가 최대 이슈가 되고 있는데, 이는 고유한 영역을 구성하고 있던 유선통신, 무선통신, 방송 등 이전까지는 독립적으로 구축 및 운용되고 있었던 각 부문간에 서비스 및 네트워크 인프라 차원의 통합 또한 융합이 이루어지고 있다. 이는 통신 서비스 사용자로 하여금 다양한 요구를 이끌어내고 있으며, 인프라측면에서도 고속 광대역 통신망을 통한 네트워크가 필요하게 되었다.
이 논문에서는 컨버전스 네트워크 문제를 풀기 위해, 크게 오버레이 멀티캐스트와 무선 메쉬 네트워크로 나누어서 문제를 보고 있다.
오버레이 멀티캐스트는 멀티캐스트가 도입되지 않은 기존의 인터넷 망에서 유니캐스트 전송을 사용하고, 각 지역에 중계기 서버를 설치하여 원격 송신자의 멀티캐스트 트래픽을 저장 혹은 캐싱 (caching) 한 후에 해당 지역 사용자에게 멀티캐스트 혹은 유니캐스트로 중계하는 기술이다. 기존의 IP 멀티캐스트는 서비스 측면과 기술적 측면에서 실패한 경우가 많다. 서비스 측면에서는 사용자가 매력을 느낄 수 있는 클라이언트 애플리케이션이 다양하지 못한 문제가 있다. 기술적인 측면에서는 IP 멀티캐스트 라우팅의 구조적 취약성, 고비용 관리, 도메인 간의 프로토콜 통일 등의 문제가 있다. 이런 문제를 해결하기 위해 나온 것이 오버레이 멀티캐스트이다. 기존의 IP 멀티캐스트는 네트워크 상의 라우터에서 패킷 복사 및 중계가 수행되는 반면에, 오버레이 멀티캐스트는 호스트 단말에서 패킷 복사 및 중계가 이루어진다. 이와 같이 인터넷 망의 멀티캐스트 라우터의 도움 없이도 멀티캐스 서비스를 실현시킬 수 있는 측면에서 많은 관심을 불러일으키고 있다.
일반적으로 무선망은 점 대 점, 점 대 다점의 구조를 가지고 있으나, 최근에는 유선망과 같이 다점 대 다점의 그물망 구조를 가지는 무선망에 대한 관심이 높아지고 있다. 무선 메쉬 네트워크는 추가적인 설치가 없이도 확장이 용이하며, 이에 따른 망 설치의 신속성 및 경제성, 확장성의 장점이 있다. 최근에는 애드 혹 라우팅에 대한 표준화와 IEEE 802.11 에서의 무선 랜을 기반으로 무선 메쉬 네트워크 표준화가 진행되고 있다. 또한, 일부는 IEEE 802.15와 IEEE 802.16의 표준화도 같이 진행되고 있다. IEEE 802.11 표준화 기구는 물리계층 (physical layer)을 중심으로 한 IEEE 802.11a/b/g을 확장하기 위해 노력하고 있으며, 무선 메쉬 네트워크에 적합한 새로운 표준인 IEEE 802.11s을 연구하고 있다. 또한, 홈 네트워킹을 위한 IEEE 802.15와 차세대 고정 및 이동 기술을 위한 IEEE 802.16도 계속해서 연구되고 있는 상황이다.
본 논문에서는 크게 컨버전스 네트워크를 실현하기 위해서 두 개의 문제, 즉 오버레이 멀티캐스트에서의 개인 인터넷 방송 상황에서의 신뢰성 있는 멀티캐스트 구성 문제와 무선 메쉬 네트워크에서 각 사용자 간의 트래픽 요구량을 고려하여 최소 단 대 단 데이터율을 최대화 시키는 문제를 다루고자 한다.
첫 번째, 개인 인터넷 방송을 오버레이 멀티캐스트 구조에 대해서 살펴보고, 멀티캐스트 트리를 구성하는 문제를 수리 모형화 한다. 수립된 수리 모형에 적합한 타부 서치 휴리스틱 방법을 제시하고, 제시된 방법을 최적화 상용 프로그램인 CPLEX와 비교 분석을 한다. 실험 결과 제안된 타부 서치 휴리스틱은 최적값과 비교해도 큰 차이가 나지 않으면서도 시간적으로도 절약되는 효과를 가져 왔다.
두 번째, 멀티 홉, 멀티채널 무선 메쉬 네트워크의 특징을 알아보고 무선 메쉬 네트워크 상에서 데이터 트래픽 요구량을 가지는 여러 소스-데스티네이션 쌍을 가정할 때, 각 쌍에서의 데이터 트래픽 요구량을 고려하여 최소 단-대-단 데이터율을 최소화하도록 하는 문제를 수리 모형화 한다. 수립된 모형에 적합한 타부 서치 휴리스틱 방법을 제시하고, 최적화 프로그램인 CPLEX와 성능 비교 및 분석을 한다. 실험 결과 제안된 타부 서치 휴리스틱은 최적 값과 비교해도 큰 차이가 나지 않으면서도 시간적으로도 절약되는 효과를 가져 왔다.