Constrained Subgraph Selection over Coded Packet Networks

Kharazmi University, Iran
Wednesday, 19 August, 2015
2:30 – 3:30 pm
Room 833, Ho Sin Hang Engineering Building

The problem of establishing connections in coded packet networks can be decomposed into two parts: (i) subgraph selection and (ii) determining the code to use over the subgraph. These two parts are very different problems, because coding applies techniques from information theory and coding theory, while subgraph selection generally uses techniques from networking theory. This talk deals with the subgraph selection to achieve certain communication objectives. Indeed, due to inherent benefits of network coding over routing, such as higher throughput, higher reliability, higher security, cheaper routing costs networks, and lower delays, research efforts have been developed to enhance conventional IP-based architectures and protocols with the quality of service (QoS) support using concept of network coding. In this talk, we study the problem of subgraph selection over coded packet networks to meet QoS requirements.  For this purpose, we first propose a path-based formulation for the problem and prove that this problem is NP-hard. Then, in order to obtain an exact solution, we present a decomposition approach in which the problem is decomposed into master problem and subproblems, and the solution is built up successively by feasible path generation.


Mohammad Ali Raayatpanah received his PhD from Tehran University, Tehran, Iran, in 2013. He is currently an assistant professor of Applied Mathematics, Faculty of Mathematical Sciences and Computer, Kharazmi University, Tehran, Iran.

His research interests include the diverse topics of network flow theory and communications with an emphasis on design network, embedded network, dynamic network, network coding, sensor networks, and quality of service applications in communication systems.