File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Some combinatorial optimization problems related to network encoding complexity
Title  Some combinatorial optimization problems related to network encoding complexity 

Authors  
Advisors  Advisor(s):Han, G 
Issue Date  2014 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Citation  Xu, L. [徐力]. (2014). Some combinatorial optimization problems related to network encoding complexity. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5194786 
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 peertopeer 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 sourcesink pairs. Let ci denote the minimum size of edgecut between ith sourcesink pair for 1 ≤ i ≤ l. Then, by Menger’s theorem, there exists a group of ci edgedisjoint paths (Menger’s paths) between ith sourcesink pair. Although within the same group these paths are edgedisjoint, 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 abovementioned 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, twoway 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 encoding complexity in undirected networks has seen little progress. Consider an undirected network G with l sourcesink pairs. For i = 1, 2, . . . , l, let ci denote the minimum size of vertexcut between ith sourcesink pair. I study H (c1, c2, . . . , cl), the minimum number of hubs needed in an undirected network with mincut constraints. The function H is closely related to network encoding 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 pathsearching algorithm, the analysis of which is instrumental for the derivations of the tight upper bounds. 
Degree  Doctor of Philosophy 
Subject  Computer networks  Mathematical models Coding theory Combinatorial optimization 
Dept/Program  Mathematics 
Persistent Identifier  http://hdl.handle.net/10722/197559 
HKU Library Item ID  b5194786 
DC Field  Value  Language 

dc.contributor.advisor  Han, G   
dc.contributor.author  Xu, Li   
dc.contributor.author  徐力   
dc.date.accessioned  20140527T23:16:44Z   
dc.date.available  20140527T23:16:44Z   
dc.date.issued  2014   
dc.identifier.citation  Xu, L. [徐力]. (2014). Some combinatorial optimization problems related to network encoding complexity. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5194786   
dc.identifier.uri  http://hdl.handle.net/10722/197559   
dc.description.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 peertopeer 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 sourcesink pairs. Let ci denote the minimum size of edgecut between ith sourcesink pair for 1 ≤ i ≤ l. Then, by Menger’s theorem, there exists a group of ci edgedisjoint paths (Menger’s paths) between ith sourcesink pair. Although within the same group these paths are edgedisjoint, 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 abovementioned 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, twoway 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 encoding complexity in undirected networks has seen little progress. Consider an undirected network G with l sourcesink pairs. For i = 1, 2, . . . , l, let ci denote the minimum size of vertexcut between ith sourcesink pair. I study H (c1, c2, . . . , cl), the minimum number of hubs needed in an undirected network with mincut constraints. The function H is closely related to network encoding 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 pathsearching algorithm, the analysis of which is instrumental for the derivations of the tight upper bounds.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  Creative Commons: AttributionNonCommerical 3.0 Hong Kong License   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.subject.lcsh  Computer networks  Mathematical models   
dc.subject.lcsh  Coding theory   
dc.subject.lcsh  Combinatorial optimization   
dc.title  Some combinatorial optimization problems related to network encoding complexity   
dc.type  PG_Thesis   
dc.identifier.hkul  b5194786   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Mathematics   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5353/th_b5194786   