File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Some combinatorial optimization problems related to network encoding complexity

TitleSome combinatorial optimization problems related to network encoding complexity
Authors
Advisors
Advisor(s):Han, G
Issue Date2014
PublisherThe 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
AbstractNetwork 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.
DegreeDoctor of Philosophy
SubjectComputer networks - Mathematical models
Coding theory
Combinatorial optimization
Dept/ProgramMathematics
Persistent Identifierhttp://hdl.handle.net/10722/197559

 

DC FieldValueLanguage
dc.contributor.advisorHan, G-
dc.contributor.authorXu, Li-
dc.contributor.author徐力-
dc.date.accessioned2014-05-27T23:16:44Z-
dc.date.available2014-05-27T23:16:44Z-
dc.date.issued2014-
dc.identifier.citationXu, 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.urihttp://hdl.handle.net/10722/197559-
dc.description.abstractNetwork 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.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.subject.lcshComputer networks - Mathematical models-
dc.subject.lcshCoding theory-
dc.subject.lcshCombinatorial optimization-
dc.titleSome combinatorial optimization problems related to network encoding complexity-
dc.typePG_Thesis-
dc.identifier.hkulb5194786-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineMathematics-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b5194786-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats