Inter-Session Network Coding with Strategic Users: A Game-Theoretic Analysis of the Butterfly Network
Inter-Session Network Coding with Strategic Users: A Game-Theoretic Analysis of the Butterfly Network
复制标题
DOI：
10.1109/tcomm.2013.021413.110555
复制
发表时间：
2009-04
影响因子：
8.3
通讯作者：
Hamed Mohsenian Rad;Jianwei Huang;V. Wong;S. Jaggi;R. Schober
中科院分区：
文献类型：
--
作者：
Hamed Mohsenian Rad;Jianwei Huang;V. Wong;S. Jaggi;R. Schober
我们用博弈论分析了有线网络中的会话间网络编码。我们假设用户是自私的，并作为战略球员，以最大限度地提高自己的效用，这将导致用户之间的资源分配游戏。特别是，我们研究了一个蝴蝶网络，其中的瓶颈链路共享网络编码和路由流。我们假设使用成对XOR操作执行网络编码。我们证明了纳什均衡的存在性，为广泛的效用函数。我们还表明，纳什均衡的数量可以很大（甚至无限）的某些参数的选择。这与传统数据包转发的类似游戏设置形成鲜明对比，其中纳什均衡总是唯一的。我们描述了最坏情况下的效率界，即，无政府状态价格（PoA），与最优合作网络设计相比。我们表明，通过使用一个歧视性的定价方案，收费编码和转发的数据包不同，我们可以提高PoA的情况下，使用单一的定价方案相比。然而，即使当使用歧视性定价方案时，PoA仍然比不应用网络编码时的情况更差。这意味着，虽然会话间网络编码可以提高性能相比，路由，它是更敏感的用户的策略行为。
We analyze inter-session network coding in a wired network using game theory. We assume that users are selfish and act as strategic players to maximize their own utility, which leads to a resource allocation game among users. In particular, we study a butterfly network, where a bottleneck link is shared by network coding and routing flows. We assume that network coding is performed using pairwise XOR operations. We prove the existence of Nash equilibrium for a wide range of utility functions. We also show that the number of Nash equilibria can be large (even infinite) for certain choices of parameters. This is in sharp contrast to a similar game setting with traditional packet forwarding, where the Nash equilibrium is always unique. We characterize the worst-case efficiency bound, i.e., the Price-of-Anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a discriminatory pricing scheme which charges encoded and forwarded packets differently, we can improve the PoA in comparison with the case where a single pricing scheme is used. However, even when a discriminatory pricing scheme is 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 routing, it is much more sensitive to users' strategic behavior.