The topic of my talk is QoS network coding. I’ve divided my presentation to two parts. In the first part, I will briefly explain the algorithm that I suggested in my thesis for providing QoS using network coding. The algorithm is a decentralized optimization method to find minimum cost QoS flow subgraphs in network coded multicast schemes. The main objective of this algorithm is to find minimum cost subgraphs that also satisfy user-specified QoS constraints, namely, rate and end-to-end delay constraints. I will only discuss the case of one and multiple multicast sessions in wired networks and leave the extensions to wireless networks for whomever interested.

In the second part of my talk, I will discuss a new idea about QoS network coding which I am currently working on. In summary, I think one of the biggest advantagess of network coding over routing is its ability to solve some NP-complete routing problems in polynomial time, or more precisely, in transforming NP-Complete problems to polynomial time ones. A good example is finding the minimum cost multicast subgraphs, which is know as finding Steiner trees problem in routing area. Lun et al. (2006) have shown that while Steiner trees problem belongs to the NP-complete class, by using network coding, the equivalent problem could be solved in polynomial time.

Since many QoS routing problems are NP-complete (and this is why there are many heuristic algorithms to provide QoS using routing), we are working on finding polynomial time solutions for the equivalent QoS network coding problems.