حداقل چارچوب مدیریت هزینه کش برای شبکه های اطلاعات محور با برنامه نویسی شبکه A minimum cost cache management framework for information-centric networks with network coding

In the past decade, multimedia content has become the dominating traffic over the Internet [2–۴]. The increasing demand for media-rich content calls for more efficient methods for content retrieval. To this end, Information-centric network (ICN) is a promising design approach that fulfills such a demand by introducing content access by name and enabling in-network caching [5,6]. In ICNs, a content router (CR) with in-network caching capability can buffer some (usually popular) data chunks for future access [7]. Innetwork caching can greatly reduce the retrieval delay of content, the traffic in the network, and the service load on the servers [8,9]. To manage in-network caches in ICNs, two major issues need to be jointly considered. One is the caching strategy that determines which data chunks shall be cached at each CR, and the other is content routing that determines where to route content requests and how to deliver content. In the literature, there are two types of caching strategies: noncooperative and cooperative. In non-cooperative caching strategies, a CR opportunistically caches the received data, which may lead to frequent cache updates, sub-optimal cache allocation and caching duplication [8]. In cooperative caching strategies, a CR can collaborate with its neighboring CRs to determine which set of data chunks to cache [9–۱۲]. For content routing, there are two different ways to utilize the in-network caches. One is to only use caches along the path to the original content server for that request and the other is to utilize all nearby caches. The former does not require any cooperation among CRs but may exhibit potentially longer content retrieval delay. The latter requires cooperation among CRs to forward the request to the nearest off-path caches [13]. Either way is closely coupled with content caching. In this paper, we will focus on cohoperative caching strategy and content routing to fully utilize all distributed in-network caches. To enable cooperation among distributed CRs, a cache management framework is needed to collect cooperation-related information (e.g., request rates and the current cache status) and make caching and routing decisions. Software defined networking (SDN), which physically decouples the control plane and data plane, can satisfy this requirement [14,15]. Typically, on the control plane, a controller is responsible for collecting network information and making routing decisions that will be configured at routers. On the data plane, routers forward packets according to the flow tables configured by the controller. Over the past few years, many new controllers have been designed by using powerful multicore servers to handle a large number of data flows in big networks. For example, McNettle [16] can manage around 20 million requests per second for a network with 5000 switches. Recently, preliminary studies have been conducted to enable cache management in ICNs based on SDN [17,18]. However, these studies mainly focused on how to incorporate cache related operations into the existing SDN architecture and did not discuss the actual caching strategy. In this paper, we will go one step further to study caching strategy and content routing of ICNs based on SDN with the aim of minimizing both the network bandwidth and cache cost, which is the total cost of bandwidth and cache consumption in the whole network. Specifically, we will employ linear network coding (LNC) to jointly optimize caching strategy and content routing to minimize the network bandwidth and cache cost. We use an example shown in Fig. 1 to illustrate the benefits of using caching and LNC in ICNs. In this figure, a network consists of eight routers (v1–v8), and two servers (s1 and s2). The users are all connected to routers v1, v5, and v6 and request a piece of content, denoted as f1, that contains two equal-sized data chunks, A and B. We assume that each link has a unit cost to transmit one data chunk and a router has a unit cost to cache one data chunk. In terms of the total cost, i.e., the sum of bandwidth cost and cache cost, we have the following results in three different content delivery scenarios: • In Fig. 1(a), we consider a basic scenario with no in-network cache, so the best way to obtain the designated content is by utilizing multicast with which seven links are used in the routing tree. In this case, there is non in-network cache used. For each data chunk, 7 links will be used and each link has unit capacity. Therefore, to transmit two data chunks, the cache cost is 0 and the bandwidth cost is 2 × ۷ =۱۴٫ The total cost is 0 + 14 =14. • In Fig. 1(b), we further assume that there are four CRs (v2, v4, v7 and v8) and each of them can cache only one data chunk. In this scenario, we consider an ICN without LNC, so each CR can cache one original data chunk. Fig. 1(b) shows the optimal caching strategy and content routing, in which the bold symbol shown on each CR denotes the data chunk cached at the CR. In this case, a total of 4 data chunks are cached in CRs, and transmitting the two data chunks requires 7 units of bandwidth consumption. Therefore, to transmit two data chunks, the cache cost is 4 and the bandwidth cost is 7. The total cost is 4 + 7 =11, representing a 21.42% improvement. • Fig. 1(c) shows the scenario with the optimal cache management in ICNs with LNC. In this case, the CRs can cache the linear combination of the original data chunks; and to recover the original data chunks A and B, a user only needs to obtain any two linearly independent coded data chunks. With the optimal solution, each router (i.e., v1, v5 and v6) can download two coded data chunks from its two nearest CRs, thus CRs only need to cache 3 data chunks and the bandwidth cost is 6 units. Therefore, the total cost is 3 + 6 =9. Compared to the best solution in Scenario 1, the optimal solution for scenario 3 achieves a 35.71% improvement; and compared to the best solution in Scenario 2, it achieves 18.18% improvement. The above example demonstrates the advantage of jointly considering in-network caching strategy and content routing with LNC in ICNs, which motivates the work of this paper. The main contributions of this paper are summarized as follows. • We propose a novel SDN-based framework to facilitate the implementation of caching strategy and content routing in ICNs with LNC. The framework is based on the emerging concept of SDN, in which a controller is responsible for determining the optimal caching strategy as well as the optimal content routing via LNC. • We formulate an optimal cache management problem for ICNs with LNC under a given cache strategy as an integer linear programming (ILP) problem. Based on this basic ILP, we further develop the ILP formulation to minimize the total network bandwidth cost and cache cost by jointly considering caching strategy and content routing. • We develop an efficient network coding based cache management (NCCM) algorithm to obtain a near-optimal cache management solution. Based on Lagrangian relaxation, the formulated problem can be relaxed and then decomposed into a linear programming problem and several simple integer maximum weight placement problems, all of which can be solved optimally within polynomial time. • We conduct extensive experiments to compare the performance of the proposed NCCM algorithm with the lower bound of the ILP formulation. We also compare the performance of the proposed NCCM algorithm with three upper bounds of the problem, i.e., no cache (no-Cache), random cache (r-Cache) and greedy cache (g-Cache) strategies. Simulation results validate the effectiveness of the proposed NCCM algorithm and the framework. The rest of the paper is organized as follows. We discuss related work in Section 2. In Section 3, we introduce a general cache management framework for ICNs based on SDN. Next, we formulate the optimal cache management problem for ICNs with LNC, which aims to minimize the network bandwidth cost and cache cost by exploiting in-network caches and LNC in Section 4. To solve the problem in practice, in Section 5, we design an efficient algorithm based on Lagrangian relaxation. We then conduct extensive experiments to illustrate the performance of our framework in Section 6. Finally, we discuss the applicability of the proposed scheme in Section 7, and we conclude the paper in Section 8.