Selfish Caching Games on Directed Graphs
Selfish Caching Games on Directed Graphs
复制标题
DOI：
10.1109/tnet.2020.3047940
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Qian Ma;E. Yeh;Jianwei Huang
中科院分区：
文献类型：
--
作者：
Qian Ma;E. Yeh;Jianwei Huang
缓存网络可以通过缓存更接近用户的内容来降低访问内容的路由成本。然而，缓存节点可能属于不同的实体，为了最大化自己的利益而表现出自私行为，这往往会导致整个网络的性能下降。虽然已经有大量的文献关于将内容分配给缓存以最大化社会福利，但对自私缓存行为的分析在很大程度上还没有被探索。本文将缓存节点的自私行为建模为具有异质内容热度的任意有向图上的自私缓存博弈。研究了自私缓存博弈中纯策略纳什均衡(PSNE)的存在性，并从社会福利的角度分析了其效率。我们证明了PSNE并不总是存在于任意拓扑的缓存网络中。然而，如果网络没有混合请求环，即每个边至少被一个内容请求遍历的有向环，我们证明了PSNE总是存在的，并且可以在多项式时间内找到。此外，通过正确选择请求转发路径，可以避免混合请求循环。然后，我们证明了如果我们允许任意的内容请求模式，纳什均衡的效率可以被无政府状态的价格(POA)所捕获，并且增加额外的缓存节点会使POA变得更糟，即发生缓存悖论。然而，当缓存节点具有同类请求模式时，我们证明了即使允许任意拓扑，POA也是有界的。我们进一步分析了计算能力有限的缓存节点的自私缓存博弈，证明了在某些感兴趣的情况下，存在一个近似的PSNE且POA有界。仿真结果表明，增加网络中的缓存容量可以提高纳什均衡的效率，而增加额外的缓存节点会降低纳什均衡的效率。
Caching networks can reduce the routing costs of accessing contents by caching contents closer to users. However, cache nodes may belong to different entities and behave selfishly to maximize their own benefits, which often lead to performance degradation for the overall network. While there has been extensive literature on allocating contents to caches to maximize the social welfare, the analysis of selfish caching behaviors remains largely unexplored. In this paper, we model the selfish behaviors of cache nodes as selfish caching games on arbitrary directed graphs with heterogeneous content popularity. We study the existence of a pure strategy Nash equilibrium (PSNE) in selfish caching games, and analyze its efficiency in terms of social welfare. We show that a PSNE does not always exist in arbitrary-topology caching networks. However, if the network does not have a mixed request loop, i.e., a directed loop in which each edge is traversed by at least one content request, we show that a PSNE always exists and can be found in polynomial time. Furthermore, we can avoid mixed request loops by properly choosing request forwarding paths. We then show that the efficiency of Nash equilibria, captured by the price of anarchy (PoA), can be arbitrarily poor if we allow arbitrary content request patterns, and adding extra cache nodes can make the PoA worse, i.e., cache paradox happens. However, when cache nodes have homogeneous request patterns, we show that the PoA is bounded even allowing arbitrary topologies. We further analyze the selfish caching games for cache nodes with limited computational capabilities, and show that an approximate PSNE exists with bounded PoA in certain cases of interest. Simulation results show that increasing the cache capacity in the network improves the efficiency of Nash equilibria, while adding extra cache nodes can degrade the efficiency of Nash equilibria.