A Game-Theoretic Analysis of Inter-Session Network Coding
A Game-Theoretic Analysis of Inter-Session Network Coding
复制标题
DOI：
10.1109/icc.2009.5198609
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
Hamed Mohsenian Rad;Jianwei Huang;V. Wong;S. Jaggi;R. Schober
中科院分区：
文献类型：
--
作者：
Hamed Mohsenian Rad;Jianwei Huang;V. Wong;S. Jaggi;R. Schober
网络编码文献中的一个常见假设是，用户是合作的，不会追求自己的利益。然而，这一假设在实践中可能会被违反。在本文中，我们分析了有线网络中的会话间网络编码，假设用户是自私的，作为战略球员，以最大限度地提高自己的效用。我们证明了纳什均衡的存在性，广泛的效用函数。在某些条件下，纳什均衡的数量可以很大（甚至无限），这与传统的数据包转发的类似游戏设置形成鲜明对比。然后，我们描述了最坏情况下的效率界限，即，价格的无政府状态（PoA），相比最佳和合作的网络设计。我们表明，通过使用一种新的歧视性定价方案，收费编码和转发的数据包不同，我们可以提高PoA的情况下，一个单一的定价方案正在使用。然而，PoA仍然比不应用网络编码的情况下更差。这意味着会话间网络编码对策略行为更敏感。例如，对于仅两个网络编码流共享单个瓶颈链路的情况，在某些纳什均衡处的效率可以低至48%。这些结果推广了著名的结果，保证67%的效率界限所示的Johari和Tsitsiklis为传统的数据包转发网络。
A common assumption in the network coding literature is that the users are cooperative and will not pursue their own interests. However, this assumption can be violated in practice. In this paper, we analyze inter-session network coding in a wired network, assuming that the users are selfish and act as strategic players to maximize their own utility. We prove the existence of Nash equilibria for a wide range of utility functions. The number of Nash equilibria can be large (even infinite) under certain conditions, which is in sharp contrast to a similar game setting with traditional packet forwarding. 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 that charges encoded and forwarded packets differently, we can improve PoA in comparison with the case where a single pricing scheme is being used. However, PoA is still worse than the case when network coding is not applied. This implies that intersession network coding is more sensitive to strategic behavior. For example, for the case where only two network coding flows share a single bottleneck link, the efficiency at certain Nash equilibria can be as low as 48%. These results generalize the well-known result of guaranteed 67% efficiency bounds shown by Johari and Tsitsiklis for traditional packet forwarding networks.