Computer Science – Information Theory
Scientific paper
2009-04-19
Computer Science
Information Theory
50 pages. To be presented at ICC 2009. Submitted to IEEE Transactions on IT
Scientific paper
A common assumption in the existing network coding literature is that the users are cooperative and non-selfish. However, this assumption can be violated in practice. In this paper, we analyze inter-session network coding in a wired network using game theory. We assume selfish users acting strategically to maximize their own utility, leading to a resource allocation game among users. In particular, we study the well-known butterfly network topology where a bottleneck link is shared by several network coding and routing flows. We prove the existence of a Nash equilibrium for a wide range of utility functions. We show that the number of Nash equilibria can be large (even infinite) for certain choices of system parameters. This is in sharp contrast to a similar game setting with traditional packet forwarding where the Nash equilibrium is always unique. We then characterize the worst-case efficiency bounds, i.e., the Price-of-Anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a novel discriminatory pricing scheme which charges encoded and forwarded packets differently, we can improve the PoA. However, regardless of the discriminatory pricing scheme being used, the PoA is still worse than for the case when network coding is not applied. This implies that, although inter-session network coding can improve performance compared to ordinary routing, it is significantly more sensitive to users' strategic behaviour. For example, in a butterfly network where the side links have zero cost, the efficiency can be as low as 25%. If the side links have non-zero cost, then the efficiency can further reduce to only 20%. These results generalize the well-known result of guaranteed 67% worst-case efficiency for traditional packet forwarding networks.
Huang Jianwei
Jaggi Sidharth
Mohsenian-Rad Amir-Hamed
Schober Robert
Wong Vincent W. S.
No associations
LandOfFree
Inter-Session Network Coding with Strategic Users: A Game-Theoretic Analysis of Network Coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Inter-Session Network Coding with Strategic Users: A Game-Theoretic Analysis of Network Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inter-Session Network Coding with Strategic Users: A Game-Theoretic Analysis of Network Coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-329669