This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:group:seminars:20090401 [2009/04/07 11:17] 127.0.0.1 external edit |
en:group:seminars:20090401 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 14: | Line 14: | ||
| ==== abstract ==== | ==== abstract ==== | ||
| - | 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. | + | 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. | ||