This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
en:group:seminars:20090401 [2009/04/03 16:10] admin created |
en:group:seminars:20090401 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ---- tabledata ---- | + | |
| - | ---------------- | + | ---- dataentry seminar ---- |
| + | date_dt : 2009-04-01 | ||
| + | title : QoS Network Coding | ||
| + | speaker : Amir Hesam Salavati | ||
| + | affiliation : Sharif University of Technology. | ||
| + | time : 16h15-17h15 | ||
| + | room : BC129 | ||
| + | table : seminars | ||
| + | =================== | ||
| + | template:datatemplates:seminar | ||
| + | ----------------------- | ||
| + | |||
| + | |||
| + | ==== 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. | ||