Design and Analysis of Low Complexity Network Coding Schemes
MetadataShow full item record
In classical network information theory, information packets are treated as commodities, and the nodes of the network are only allowed to duplicate and forward the packets. The new paradigm of network coding, which was introduced by Ahlswede et al., states that if the nodes are permitted to combine the information packets and forward a function of them, the throughput of the network can dramatically increase. In this dissertation we focused on the design and analysis of low complexity network coding schemes for different topologies of wired and wireless networks. In the first part we studied the routing capacity of wired networks. We provided a description of the routing capacity region in terms of a finite set of linear inequalities. We next used this result to study the routing capacity region of undirected ring networks for two multimessage scenarios. Finally, we used new network coding bounds to prove the optimality of routing schemes in these two scenarios. In the second part, we studied node-constrained line and star networks. We derived the multiple multicast capacity region of node-constrained line networks based on a low complexity binary linear coding scheme. For star networks, we examined the multiple unicast problem and offered a linear coding scheme. Then we made a connection between the network coding in a node-constrained star network and the problem of index coding with side information. In the third part, we studied the linear deterministic model of relay networks (LDRN). We focused on a unicast session and derived a simple capacity-achieving transmission scheme. We obtained our scheme by a connection to the submodular flow problem through the application of tools from matroid theory and submodular optimization theory. We also offered polynomial-time algorithms for calculating the capacity of the network and the optimal coding scheme. In the final part, we considered the multicasting problem in an LDRN and proposed a new way to construct a coding scheme. Our construction is based on the notion of flow for a unicast session in the third part of this dissertation. We presented randomized and deterministic polynomial-time versions of our algorithm.
undirected ring networks
Tabatabaei-Yazdi, Seyed (2011). Design and Analysis of Low Complexity Network Coding Schemes. Doctoral dissertation, Texas A&M University. Available electronically from
Showing items related by title, author, creator and subject.
Jiang, Shu (Texas A&M University, 2006-04-12)Camouflaging is about making something invisible or less visible. Network camouflaging is about hiding certain traffic information (e.g. traffic pattern, traffic flow identity, etc.) from internal and external eavesdroppers ...
Chandanala, Roja Ramani (2012-02-14)Network coding and duty-cycling are two popular techniques for saving energy in wireless sensor networks. To the best of our knowledge, the idea to combine these two techniques, for even more aggressive energy savings, ...
Suravarapu, Prasad Devi (Texas A&M University, 1995)In this thesis we analyze network traffic on a local area network in an academic environment. We analyze the trace based on transport-level and network-level applications. Networks conversations are studied using the newly ...