Inapproximability results and suboptimal algorithms for minimum delay cache placement in campus networks with content-centric network routers

Affiliation of Author(s):计算机科学与技术学院/人工智能学院/软件学院

Journal:JOURNAL OF SUPERCOMPUTING

Key Words:Inapproximability In-network caching Cache decision strategy Content-centric network

Abstract:We consider the cache placement problem in campus networks where routers have heterogeneous cache capacity and the objective is to minimize the total delay of all requests. We prove that the problem is NP-hard to approximate to within any factor less than n/m(epsilon) + poly(m), where n is the number of routers, m is the number of contents, epsilon is any fixed positive constant, and poly(m) is any polynomial function of m. We propose (exponential-time) exact algorithms based on integer linear programming and propose techniques to decompose the network and remove redundant variables for speeding up the computation. By relaxing the integer linear programs, we also propose three (polynomial-time) heuristic algorithms. Numerical results show that the proposed algorithms give a shorter delay than existing cache decision algorithms for content-centric networks.

ISSN No.:0920-8542

Translation or Not:no

Date of Publication:2019-08-01

Co-author:cb,Shen, Muhui,Zhao Yanchao

Correspondence Author:Xiaojun Zhu

Date of Publication:2019-08-01