Some combinatorial optimization problems related to network encoding complexity

Abstract

Network coding is a novel technique to improve the throughput of networks to transfer messages from sources to sinks. Before the birth of network coding, intermediate nodes can only forward the received messages. In a network coding scheme, the intermediate nodes are allowed to mix the received messages from different incoming links. Network coding has found a wide range of applications, such as peer-to-peer networks, distributed storage and content distribution. The theory of network encoding complexity aims to deal with the question what the minimum number of encoding nodes needed in networks is. In order to tackle this question, we convert it into a combinatorial optimization problem.

For directed networks, I examine the number of “mergings”, a special type of graph structure. Consider an acyclic directed network G with l source-sink pairs. Let ci denote the minimum size of edge-cut between i-th source-sink pair for 1 ≤ i ≤ l. Then, by Menger’s theorem, there exists a group of ci edge-disjoint paths (Menger’s paths) between i-th source-sink pair. Although within the same group these paths are edge-disjoint, the paths from different groups may have to merge with each other. It is known that by choosing Menger’s paths appropriately, the number of mergings among different groups of Menger’s paths is always bounded by a constant, which is independent of the size of G. The tightest such constant for the all the above-mentioned networks is denoted byM(c1, c2, . . . , cl) when all sources are distinct, and by M∗(c1, c2, . . . , cl) when all sources are identical. It turns out that M and M∗ are closely related to the network encoding complexity for a variety of networks, such as multicast networks, two-way networks and networks with multiple sessions of unicast. Computation of these two important functions, however, appears to be rather difficult; so far there are no explicit formulas for M and M∗ for a generic parameter c1, c2, . . . , cl. In this thesis, I derive exact values of and tighter bounds on M and M∗ for some parameters, and establish the inequality relationships between M and M∗. For undirected networks, I examine the number of “hubs”, the vertices of degree at least three. Compared to directed networks, study on network en-coding complexity in undirected networks has seen little progress. Consider an undirected network G with l source-sink pairs. For i = 1, 2, . . . , l, let ci de-note the minimum size of vertex-cut between i-th source-sink pair. I study H (c1, c2, . . . , cl), the minimum number of hubs needed in an undirected network with min-cut constraints. The function H is closely related to network en-coding complexity for undirected networks. I prove that under some constraints, regardless of the size of the undirected networks, such minimum number is always bounded above and I derive tight upper bounds for some special parameters. In particular, for two pairs of sources and sinks, I present a novel path-searching algorithm, the analysis of which is instrumental for the derivations of the tight upper bounds.