On node capacity allocation and upper bound in node-capacitated graphs

Abstract

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.