In this thesis, we study node capacity allocation schemes and multicasting schemes to achieve single multicast capacity in node-capacitated graphs. Node-capacitated graphs are closely connected P2P overlay networks, and has potential to capture configurable nature of wireless relay networks.
Although techniques for solving optimization problems can be used for node-capacitated graphs, it does not give any connection between graph parameters such as topology or node capacity setting and optimal strategies to achieve capacity. Accordingly, rather than just solving optimization problems for arbitrary graphs, we consider some structured node-capacitated graphs, and try to find an optimal node capacity allocation scheme and multicasting scheme for them without applying numerical methods to solve optimization problems. In addition, an upper bound called multi-region cut set bound is proposed, The key is that, rather than considering only 2 regions for a cut, it considers cuts separating a graph into multiple regions each of which corresponds to a source or a receiver.
We study layered node-capacitated graphs with node upload capacity, and derive explicit characterization of single multicast capacity of maximally connected, layered graphs. For such graphs, it is shown that ratio-based node capacity allocation and routing achieve multicast capacity. In addition, some examples of other layered graphs are examined.
본 논문에서는 노드에 용량이 있는 그래프에서 하나의 멀티캐스트 세션이 있는 경우의 전송 용량을 다룬다. 노드에 용량이 있는 그래프는 P2P 오버레이 네트워크와 깊은 연관이 있으며, 무선 릴레이 네트워크가 가지고 있는 링크별로의 전송량을 조절할 수 있는 특성을 캡쳐할 수 있는 가능성이 있다.
노드에 용량이 있는 그래프를 분석하는 데 있어서 최적화 문제를 푸는 기법을 사용할 수 있으나, 이는 그래프의 토폴로지, 노드 용량과 같은 네트워크 인자들과 전송 용량을 달성하는 기법 간의 연관성을 보여주지 못한다. 그에 따라, 임의의 그래프에 대해 최적화 문제를 풀기보다, 특정 구조를 가진 그래프를 가정하고, 이에서 전송 용량을 달성하는 노드 용량 할당 방법 및 멀티캐스트 기법을 다룬다. 또한, 다지역 컷셋 바운드를 제안한다. 이것의 핵심은, 기존 컷셋 바운드가 네트워크를 2 구역으로 나누는 컷을 생각하는 것이 아닌, 송신 노드 혹는 수신 노드에 해당되는 여러 구역으로 나누는 컷을 고려하는 것이다.
본 논문에서는 계층적인 구조를 가지는 그래프를 다루고, 그러한 구조 상에서 최대한 연결이 되어 있는 형태의 그래프에서의 전송 용량을 명확한 형태로 유도하였다. 이러한 그래프에서 비율을 기반으로 한 노드 용량 할당 방법과 라우팅 기법이 전송 용량을 달성함을 보였다. 또한, 다른 형태의 계층형 그래프에 해당되는 예에 대하여 분석하였다.