Tuan-Minh Pham

Michel Minoux

Serge Fdida

Marcin Pilarski

Optimization of Content Caching in Content-Centric Networks

Keywords: Optimal caching, CCN, integer programming, stochastic programming, non-cooperative game

Video on demand (VoD) systems currently use content delivery networks (CDN) to distribute content to users, whose performance and effectiveness depends on the architecture, the number and the geographical location of CDN nodes deployed by CDN providers or ISP(s) itself. Content-Centric Networking (CCN), with the benefits of caching and sharing content by every node in the network, suggests an alternative: a collaborative caching system exploiting the maximum capacity of infrastructure for the high performance of video delivery services. However, a CCN-based architecture to support efficient VoD delivery raises important questions about the optimal routing and caching strategies with constraints on the architecture and capacities of the system. We investigate models and algorithms for addressing these optimization problems. We study different solutions for the routing and caching optimization problems and compare the solutions produced with the optimal solution under various assumptions. We also contribute to an analysis of the caching investment under the competition among multiple interconnected ISPs. Our numerical results show the influence of throwing caching at the problem in different locations, on the system performance and its related cost.

I. INTRODUCTION

The Internet has evolved towards an amazing machinery to distribute content at scale. Nevertheless, the current service model might not be appropriate and novel architectures have been proposed based on various Information-Centric Networking architectures. Among them CCN (and more recently NDN) has been widely studied over the last few years. ICN decouples the sender from the receiver and provides caching capabilities in the network. The content is then possibly made available closer to the user(s), not only reducing network traffic and delivery delays, but also reducing Mean Opinion Score (MOS) variance and increasing QoE for End-User [START_REF] Mok | Measuring the quality of experience of http video streaming[END_REF]. Besides the protocol issues raised by CCN, this solution triggers a potential for defining new roles and business opportunities for the various stakeholders, namely Internet Service Providers (ISP), Content Providers (CP) and Content Distribution Networks (CDN) [START_REF] Pham | Pricing in Information-Centric Network interconnection[END_REF].

In this paper, we explore solutions for optimizing the location of content. Our algorithm could be applied both in wired and wireless environments where caching content closer to the user is beneficial because of limited bandwidth or congestion risk. We consider the distribution of content, likely VoD, to end users connected either through their set top boxes or their wireless devices via a home gateway. We assume that the system is supported by the ability, for a provider to assess user's need thanks to a recommendation service alike those found in many professional VoD systems. Based on this information, we propose a strategy that optimizes the location of content towards users devices as well as routers with caching capabilities within the infrastructure of one ISP.

In the context of multiple ISPs, content demands can be serviced by a local ISP, a content provider, or other ISPs. In such contexts, ISPs are competitive with each others for minimizing their cost. Thus, we consider the following questions: Does an equilibrium exist and under which condition? At the equilibrium, what is the impact of caching investment on the utility of ISPs?

Our first contribution provides a feasible cache solution that minimizes the expectation of routing cost computed from the optimal routing solution. We formulate the optimization problem of CCN caching as a two-stage stochastic programming problem transformed to a deterministic multiscenario linear program. The main advance of the formulation is the deterministic evaluation of cost and constraints in a nondeterministic scenario involving the uncertainty of content demand. We investigate models and algorithms for addressing the routing and caching optimization problems. Several work has been devoted to the study of optimal caching in CCN [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF], [START_REF] Wang | Optimal cache allocation for content-centric networking[END_REF]. However, to the best of our knowledge, there were no attempt thus far to provide a formulation capturing the deterministic computation of cost and constraints while taking into account a set of content demand scenarios (i.e. a long time period, not just a snapshot of the system at a particular time).

We then extend our analysis of caching in a context of a single ISP to that in a multi-tiered hierarchy of interconnected ISPs. In a context of multiple ISPs, a decision of any ISP would have an impact on the strategies of the others while each ISP optimizes its decisions in an individual manner. We use a game-theoretical model to formulate the competition among multiple ISPs with regard to the impact of caching and congestion costs. Our numerical results infer that a local ISP cannot always receive a profit from its caching investment while it can always earn a profit from caching investment of other ISPs. The ISP can use our game-theoretical model to analyze its utility under competition with other ISPs by adapting the cost and revenue functions to various contexts.

The remainder of the paper is organized as follows. Section II reviews the related work. Section III is devoted to a brief description of the system under consideration. We state formally the caching problem in Section IV. Our models and algorithms for routing and content location are presented in Section V. Section VI describes our game-theoretical model for analyzing content caching in a multi-tiered hierarchy of interconnected ISPs. Section VII presents our evaluation and discussion of the performance of our solution, and the impact of caching investment of ISPs under the competition. Section VIII concludes the paper and highlights future work.

II. RELATED WORK

Information-Centric Networks are widely studied with solutions such as PSIRP [START_REF]Publish-subscribe internet routing paradigm (PSIRP) project[END_REF], DONA [START_REF] Koponen | A data-oriented (and beyond) network architecture[END_REF] or NDN [START_REF]NDN project[END_REF]. The CCN framework was first introduced by Van Jacobson and the PARC research group in [START_REF] Jacobson | Networking named content[END_REF], [START_REF]CCNx project[END_REF]. Various issues arising in CCNs have been considered such as content router issues [START_REF] Arianfar | On content-centric router design and implications[END_REF], data transfer modelling [START_REF] Carofiglio | Modeling data transfer in Content-Centric Networking[END_REF] or chunk-level caching [START_REF] Carofiglio | Experimental evaluation of memory management in Content-Centric Networking[END_REF]. Content caching was strongly investigated in different contexts in the Internet. Li et. al. addressed the optimal placement of web proxies for networks with a tree topology [START_REF] Li | On the optimal placement of web proxies in the Internet[END_REF]. Qiu et. al. proposed greedy algorithms to find the optimal location of web servers for real network topologies [START_REF] Qiu | On the placement of web server replicas[END_REF]. In [START_REF] Kangasharju | Object replication strategies in content distribution networks[END_REF], the authors proved that the optimization problem of object replication in CDNs is NP complete and proposed heuristics for finding nearoptimal solutions. In [START_REF] Yu | Tradeoffs in CDN designs for throughput oriented traffic[END_REF], Yu et. al. studied the impact of the number of servers and their locations on the aggregate throughput and operating cost in CDNs. However, the above solutions as well as the ones designed for current multi-cache networks such as the Web and CDNs are not applicable to a CCN environment due to CCN's unique properties including: 1) content is located by name instead of location, and 2) every ICN node can cache and serve the requested content.

Several papers were published to study the problem of content caching in CCN for better performance and efficient resource utilization. [START_REF] Psaras | Modelling and evaluation of CCN-caching trees[END_REF], [START_REF] Rossi | On sizing ccn content stores by exploiting topological information[END_REF], [START_REF] Rosensweig | Approximate models for general cache networks[END_REF], [START_REF] Fayazbakhsh | Less pain, most of the gain: Incrementally deployable ICN[END_REF]. In [START_REF] Rosensweig | Approximate models for general cache networks[END_REF], Rosensweig et. al. provide an approximate model for analyzing the performance of CCNs where contents are cached at each node along the path for delivering the requested contents to customers. Psaras et. al. consider the modelling and evaluation of caching policies based on Markov chains [START_REF] Psaras | Modelling and evaluation of CCN-caching trees[END_REF]. In [START_REF] Rossi | On sizing ccn content stores by exploiting topological information[END_REF], Rossi and Rossini propose a solution to the cache allocation problem for individual CCN routers by using centrality metrics such as betweenness, closeness and degree centralities. In [START_REF] Fayazbakhsh | Less pain, most of the gain: Incrementally deployable ICN[END_REF], the authors use trace-driven simulations to evaluate the performance benefits achieved by CCNs. Recently, Araldo et. al. propose a cost-aware cache decision policy whose objective is the cost reduction, contrarily to the above studies that focus on caching efficiency [START_REF] Araldo | Cost-aware caching: Caching more (costly items) for less (isps operational expenditures)[END_REF]. Our work is different as it considers the joint problem of routing and caching in a CCN context where any node can cache and share content. So far, there has been little discussion about the joint problem of routing and caching [START_REF] Jiang | Orchestrating massively distributed CDNs[END_REF], [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF], [START_REF] Wang | Optimal cache allocation for content-centric networking[END_REF]. In [START_REF] Wang | Optimal cache allocation for content-centric networking[END_REF], the cache allocation problem for CCNs is formulated as a 0-1 maximization problem featuring the structure of a knapsack problem. However the model relies on several simplifying assumptions such as fixed routing and without bandwidth constraints. In [START_REF] Jiang | Orchestrating massively distributed CDNs[END_REF], the authors study adaptive mechanisms to manage content replication and routing on a continuous basis. In [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF], the authors address the optimization of content caching and routing in a hierarchical tree network. However, to the best of our knowledge, there exists no attempt to provide a formulation capturing the deterministic computation of cost and constraints while taking into account a set of content demand scenarios (i.e. a long time period, not just a snapshot of the system at a particular time). In addition, no research has been found that surveyed competition among ISPs in a general multi-tiered hierarchy of interconnected ISPs with regard to the impact of caching and congestion costs. The model discussed below is intended to overcome such limitations.

III. SYSTEM DESCRIPTION

We consider a content delivery architecture involving a Content Provider (CP) and a set of user's set-top boxes (STBs) connected to the CP through a network path. The later is reduced to an intermediate router for simplification purposes and also because it is likely that in-network caching will mostly be beneficial at the edges, namely the intermediate router in our model. The system provides content delivery with quality of service constraints such as video-on-demand alike Netflix for a set of geographically dispersed users. Each user subscribing to such services is equipped with a STB that allows to cache content objects. An intermediate router between the CP and STBs can store other content objects depending on its storage capacity as well as the caching strategies of the system. The CP store all content objects that can be requested from users. Figure 1 illustrates the system including one root node that represents the CP, one intermediate node that is the intermediate router, and a set of STB nodes. A user requests content through its STB. Depending on the routing policy, a content request can be satisfied from any node including STBs, the intermediate node, or the root. Such an architecture optimizes the cost of content delivery by exploiting the capacity of content caching and content sharing among all nodes in the system.

The cost induced by the content delivery system is mostly the cost of transmission for moving content. Ideally, and as the last mile has limited resources (transmission and storage), we would like to opportunistically store the appropriate content as close as possible to the consumer or in a location that will benefit from the shared request of different users willing to consume the same content. A single ISP will benefit from serving users in the same neighborhood, or from one of its intermediate device, avoiding being charged for fetching the content from a competitor or directly from the Content Provider server.

We assume that the probability distribution representing the user preferences regarding content access is captured via a Zipf law [START_REF] Breslau | Web caching and Zipf-like distributions: Evidence and implications[END_REF], recognizing the diversity of content but also the existence of very popular ones. For this reason, it is possible that the system will face flash crowd when some extremely In order to optimize the content delivery cost under the system, we explore the strategy for caching content (placement) according to the user's needs, knowing that one can move content among nodes. Unlike other papers [START_REF] Jiang | Orchestrating massively distributed CDNs[END_REF] we do not provide adaptive mechanisms to manage content replication and routing on a continuous basis but rather consider a different time scale where ISPs can optimize the placement of their content on a daily basis, exploiting information about usage statistics and preferences that are developed in current recommendation services. Therefore, we assume that ISPs can update their policy for content replication and placement at best times in order to take into account the evolution of the demand and the changing popularity of content.

IV. PROBLEM STATEMENT

The deployment of a content delivery system exploiting the maximum capacity of caching and sharing content among nodes requires to optimize the replication of content objects in order to minimize routing costs under bandwidth constraints. Specifically, for a given cache location, we need to solve the problem of optimal routing under bandwidth constraints of the system. The problem of optimal routing is to decide which node should serve a piece of content requested by a given other node so that all content requests of users are satisfied and the total transmission cost is minimized. The cost of a candidate solution for optimal cache location is the cost of optimal routing. Hence, the problem of optimal cache location is to find a solution of locating content objects that optimizes the transmission cost under the optimal routing strategy subject to constraints on bandwidth and storage capacity.

In order to formally state the problem, we introduce the following notation:

• h is the intermediate node; r is the root node.

• I is the set of STB nodes; I 1 = I ∪ {h}, and I 2 = I ∪ {h, r}. • J is the set of content objects. Without loss of generality, we assume that content object j 1 is more popular than content object j 2 if j 1 < j 2 .

• n is the total number of STB nodes; m is the total number of content objects. • s I and s h are the number of content objects that can be stored at a STB and the intermediate node respectively. • c 0 is the capacity of the uplink (i, h) for each i ∈ I. c 0 is a small integer, specifying the maximum number of content objects stored at i which can be uploaded to other customers during a given time period (e.g. the peak hour time period in a typical day). We do not specify a downlink capacity because we assume that in all realistic scenarios for demands, the downlink capacity is sufficient to download the content objects required by any customer i (either from r, from h, or from another customer i ).

• y = (y ij ) (i ∈ I 1 , j ∈ J) is a candidate solution of cache location, where node i stores content j if y ij = 1, or not if y ij = 0. • d = (d ij ) (i ∈ I, j ∈ J) is content demand in a given scenario of demands where d ij is a 0-1 random variable. If node i requests content j, d ij = 1, otherwise d ij = 0.
The various random variables d ij are assumed to be independent.

• w 1 and w 0 are associated transmission costs when a content object is transmitted by a link between r and h, and a link between h and i ∈ I respectively. We assume w 1 > w 0 due to the fact that the connection between the intermediate server and the ISP network is long-distance and uses an expensive technology in data transmission. For content object j required by customer i ∈ I, the routing cost of satisfying that content request by node i ∈ I 2 , denoted by w ii j , is

• 0 if content object j is available at i (i.e. i = i, y ij = 1),

• w 0 if it is downloaded from h,

• 2w 0 if it is downloaded from another customer i = i,

• w 0 + w 1 if it is downloaded from r. For i ∈ I, i ∈ I 2 , and j ∈ J, the routing decision variable x ii j ∈ {0, 1} denotes whether or not content j required by node i is delivered from node i . The routing cost of a possible routing solution x for a scenario of content demand d and content caching y is

ϕ(x, y, d) = i∈I i ∈I2 j∈J w ii j x ii j d ij .
Problem 1 (Routing Problem): Given cache location (y ij ) where i ∈ I 1 and j ∈ J, and a scenario of content demand (d ij ) where i ∈ I and j ∈ J, find a routing solution (x ii j ), where i ∈ I, i ∈ I 2 and j ∈ J, satisfying all the requirements of the customers in order to minimize routing cost ϕ(x, y, d) subject to constraints on uplink bandwidth.

Suppose that we know the probability distribution of the possible scenarios of demands. Specifically, for each customer i, content j is required with a given probability p ij ≥ 0 (i.e. P {d ij = 1} = p ij , P {d ij = 0} = 1 -p ij ). For a given probability distribution of demands, we denote ψ(y) the expectation of routing cost with respect to a feasible caching location y. Then, the optimal caching problem is defined as follows.

Problem 2 (Caching Problem): Given the probability distribution of content demand, find y = (y ij ), where i ∈ I 1 and j ∈ J, in order to minimize ψ(y) subject to constraints on storage capacity.

Next section will develop our solution for solving the above optimization problems.

V. ALGORITHMS

A. Linear Programming Model

We consider the optimization problem of caching involving the uncertainty of content demand. Our goal is to find a feasible solution that minimizes the expectation of routing cost. Hence, the caching problem is a two-stage stochastic programming problem. Let x * be the optimal solution of the routing problem (i.e. the second-stage problem) for a scenario of demand d, and ϕ * (y, d) = ϕ(x * , y, d) be the optimal routing cost. Then, the expectation of routing cost for a candidate of caching solution is ψ(y) = E [ϕ * (y, d)]. The two-stage formulation of the stochastic programming model (P 1 ) for the optimal caching problem is given by:

Minimize ψ(y) = E [ϕ * (y, d)] Subject to: j∈J y ij s I ∀i ∈ I j∈J y hj s h y ij ∈ {0, 1} ∀i ∈ I 1 , j ∈ J where y = (y ij ) such that y ij ∈ {0, 1} for i ∈ I 1 and j ∈ J.
In order to solve efficiently the above two-stage stochastic program, we transform it into a deterministic multiscenario linear program. We consider s scenarios of content demand generated from the popularity distribution of content requests. Each scenario is obtained by drawing independently a value of each variable d ij according to the probability distribution

(p ij , 1 -p ij ). Let π k = π k ij be scenario k of content demand where k ∈ K and K = {1, 2, . . . , s} is the set of s scenarios. In scenario k, if content j is requested by customer i, π k ij = 1, otherwise π k ij = 0. We denote x k = x k
ii j a possible routing solution for content location (y ij ) and scenario k of content demand. The equivalent linear programming model (P 2 ) for the stochastic program (P 1 ) of the caching problem is given by:

Minimize 1 s k∈K ϕ x k , y, π k (1)
Subject to:

i∈I\{i } j∈J x k ii j c 0 ∀i ∈ I, k ∈ K (2) i ∈I2 x k ii j = π k ij ∀i ∈ I, j ∈ J, k ∈ K (3) j∈J y ij s I ∀i ∈ I (4) j∈J y hj s h (5) x k ii j y i j ∀i ∈ I, i ∈ I 2 , j ∈ J, k ∈ K (6) x k ii j ∈ {0, 1} ∀i ∈ I, i ∈ I 2 , j ∈ J, k ∈ K (7) y ij ∈ {0, 1} ∀i ∈ I 1 , j ∈ J (8)
In linear programming model (P 2 ), conditions (4) and ( 5) are storage capacity constraints. For each scenario k of content demand, a feasible routing solution has to satisfy constraints on uplink capacity (2), the content availability at a sending node [START_REF] Baev | Approximation algorithms for data placement problems[END_REF], the fulfilment of all content requests (3).

Unfortunately, data placement problems are NP-hard [START_REF] Baev | Approximation algorithms for data placement problems[END_REF]. This implies that no polynomial time algorithm is known that solves exactly any of these problems. It is time consuming to solve the huge linear programming model (P 2 ) when the size of the program is large (i.e. thousands of content objects, hundreds of nodes, and hundreds of scenarios). Hence, in the sequel we propose heuristic that provide a solution close to the optimal with a reduced computation time.

B. Heuristics for Optimal Routing

We first consider the routing subproblem and propose a heuristic algorithm, namely Closest and Least Busy Node First Routing (CLBR), which provides a near-optimal routing solution with linear time complexity. The main ideas underlying this heuristic procedure are that the cost of providing content from a node that is closer to the user is cheaper, and contents whose popularity is low are rarely cached in a STB. The algorithm uses a priority list of STBs which suggests which STB should provide a content object when several STBs hold the content object. The priority of STB i is

pri(i) = 1 j∈J p ij d ij . ( 9
)
The detail of all steps is summarized in Algorithm 1.

Proposition 1 shows two scenarios in which the heuristic algorithm provides the optimal solution to the routing problem.

Proposition 1: The CLBR algorithm provides the optimal routing cost if the uplink capacity is unlimited or if no STB is willing to share content.

Proof: Suppose the optimal solution is not the one produced by the algorithm. It means that one of policies 1-2 is suboptimal. Suppose policy 1 is suboptimal, it means that Algorithm 1 Closest and Least Busy Node First Routing (CLBR) When a user requests a content object through its STB, the request is satisfied by the following policies:

1) The local STB serves the request if the content object is available in its cache. 2) Otherwise, the intermediate node serves the request if the content object is available in its cache. 3) Otherwise, the node serving the request is the STB that has cached the content object and has the highest priority. 4) Otherwise, the root serves the request. there exist j ∈ J and i ∈ I such that y ij = 1, and either x ii j = 1, or x ihj = 1, or x irj = 1 where i ∈ I and i = i in the optimal solution. Suppose x ii j = 1, we build a feasible solution by changing x ii j to 0 and x iij to 1. Similarly, we can build a feasible solution when x ihj = 1, or x irj = 1. That feasible solution provides a lower cost, which contradicts the assumption. So, the optimal solution follows policy 1. Using similar arguments, we prove that the optimal solution follows policy 2, which demonstrates Proposition 1 when no STB is willing to share content.

Note that any feasible routing solution can be built by changing x irj to 0 and x ii j to 1 when content sharing is considered and the uplink capacity is unlimited. Using similar arguments used in the case of no sharing support, we prove that the algorithm provides the optimal solution when the uplink capacity is unlimited.

C. Heuristics for Optimal Caching

We propose a heuristic algorithm for finding an efficient solution to the caching problem, based on the local popularity of content requests. This heuristic is referred to as LPC. More specifically, the content object that a user requests with high probability will be stored locally in its STB. The entire process is presented in Algorithm 2.

Algorithm 2 High Local Popularity First Caching (LPC)

The policies of storing a content object locally are as follows:

1) For any STB, select the maximum number of content objects by descending priority of the content popularity. 2) For the intermediate server, select content objects that have not been cached in any STB by descending priority of the content popularity.

Proposition 2 shows a situation in which the LPC heuristic provides the optimal solution for the caching problem.

Proposition 2: The LPC algorithm provides the optimal solution if the intermediate node does not cache content and no STB is willing to share content.

Proof: Suppose the optimal solution is not the one produced by algorithm 2. It means that there exist j 1 , j 2 ∈ J and i k ∈ I in the optimal solution y = (y ij ) such that the request popularity of content j 1 is greater than the one of content j 2 , y i k j1 = 0, and y i k j2 = 1. We build a feasible solution y from y by changing y i k j1 to 1, and y i k j2 to 0. Let ψ s (y) be the total cost of s scenarios of content demands for the content location y. We denote d s ij the number of requests for content j required through STB i in these scenarios. Since no STB is willing to share content, following Proposition 1, the optimal routing cost can be computed by the CLBR algorithm. In addition, the intermediate node does not hold any content object. So, we have

ψ s (y) = d s i k j1 (w 0 + w 1 ) + ψ 0 ψ s (y ) = d s i k j2 (w 0 + w 1 ) + ψ 0 where ψ 0 = i ∈I2 j∈J\{j1,j2} w i k i j x i k i j d s i k j + i∈I\{i k } i ∈I2 j∈J w ii j x ii j d s ij
Since the request popularity of content j 1 is greater than that of content j 2 , we have

d s i k j1 > d s i k j2
. So, ψ s (y ) < ψ s (y). It follows that the feasible solution produces a lower cost, which contradicts the assumption. Hence, the algorithm delivers the optimal solution.

When the content demand of STBs is homogeneous (i.e. p ij = p i j = p j for ∀i = i), the cost of s scenarios of content demand is given by

ψ s (y) = s I +s h j=s I +1 nd j w 0 + m j=s I +s h +1 nd j (w 0 + w 1 ) (10)
where we recall that m denotes the number of content objects and d j is the total requests for content object j in all scenarios required by a STB. Assume that the popularity of a content request follows a Zipf distribution, then the request probability of content item of rank j is given by

p j = 1 j α m z=1 1 z α
where α is the value of the Zipf's exponent depending on the type of content. When very few popular content objects exist (i.e. p j → 0, d j → 0 as j is large), ψ s (y) is small. It follows that the result provided by the algorithm is close to the optimal when the value of the Zipf parameter for the popularity of content request is high. When the value of the Zipf parameter is small, we propose to use the adaptive popularity algorithm (APC) that adjusts the number of content objects stored locally to the content popularity. The basic idea of the APC algorithm is that the number of content objects stored locally is in proportion to the popularity of content request. For example, if the popularity of content request follows the Zipf distribution, the number of content object j stored locally is given by

s j = ns I + s h m j=1 m k=j+1 k α m k=j+1 k α .
Algorithm 3 Adaptive Popularity Caching (APC) 1) For content object j ∈ J, compute the number of copies s j stored locally in all STBs based on the popularity of content requests. 2) For j = 1 to m a) Store a copy of content object j in the intermediate server if the number of copies is less than n. b) Store a copy of content object j in STB i by descending priority of p ij until the number of copies reaches s j .

The detail of all steps is presented in Algorithm 3. Proposition 3 compares the results provided by the two algorithms.

Proposition 3: Suppose the content demand of STBs is homogeneous, the uplink capacity is unlimited, the intermediate server does not store any content object, the total storage capacity of all STBs is larger than or equal to m, and the popularity of a content object is uniform, the APC algorithm provides a better result than the LPC algorithm if

s I m < q -1 q + 1 (11)
where q = w 1 w 0

Proof: Since the uplink capacity is unlimited, the optimal routing can be computed by the CLBR algorithm. Because the content demand of STBs is homogeneous, the intermediate server does not store any content object, and the popularity of a content object is uniform, from [START_REF] Carofiglio | Modeling data transfer in Content-Centric Networking[END_REF], the cost of the solution provided by the LPC algorithm is given by ψ s LP C (y) = n (m -s I ) d j (1 + q) w 0 . When the content demand of STBs is homogeneous, the uplink capacity is unlimited, the intermediate server does not store any content object, the total storage capacity of all STBs is larger than or equal to m, and the popularity of a content object is uniform, by applying the CLBR algorithm for routing, the cost of the solution provided by the APC algorithm for the caching problem is 11) is satisfied, which proves the claim.

ψ s AP C (y) = nmd j 2w 0 -ns I d j 2w 0 . We have ψ s LP C (y) -ψ s AP C (y) > np j d j w 0 [(1 + q) (m -s I ) -2m] So, ψ s LP C (y) -ψ s AP C (y) > 0 if condition (

VI. COMPETITION AMONG MULTIPLE ISPS

We study the impact of caching under the competition among multiple ISPs (Fig. 2). Let N be a set of content providers. H is a set of local ISPs. G is a set of regional ISPs. We denote by C a hg (κ hg ) the cost function of caching investment of local ISP h ∈ H whose provider ISP is regional

(k ∈ K, K = {p} ∪ G ∪ H\ {h}). p k hg
is the transmission cost when one of q k hg content demands is fulfilled. p hg is the vector of all transmission cost of node h of g.

Suppose that the number of content demand q k hg is increasing in caching factor κ k and is decreasing in transmission cost p k hg . We consider a function of content demand as follows

q k hg = D 1 e 1-κ k p k hg -β k =k p k hg h =h,g =g p k h g ( 12
)
where β is a constant representing the sensitivity effects of demands on the cost of delivering a content item from k to ISP (h, g). Let c k hg ( q k hg ) be the congestion cost of a path from ISP (h, g) to node k, which is a function of the total content demands on the path. The congestion cost of a path increases if the total content demands on the path increases. Consider a linear function of congestion cost

c k hg q k hg = q k hg α (13)
where congestion factor α is a constant. We denote by C o hg ( p hg ) the cost when all content demands requested by node h of g are satisfied. C o hg ( p hg ) is the sum of the total congestion cost and the total transmission cost. Specifically, we have

C o hg ( p hg ) = k∈K c k hg q k hg + k∈K q k hg p k hg . (14)
Let ψ hg ( p hg ) be the revenue that ISP (h, g) receives when servicing all content demands from its users. Suppose that the revenue responded to content request is linear

ψ hg ( p hg ) = τ k∈K q k hg ( 15
)
where τ is the revenue of the ISP when it fulfills one content demand.

The utility of local ISP h of regional ISP g equals the revenue minus costs. We have

U hg ( p hg ) = ψ hg ( p hg ) -C o hg ( p hg ) -C a hg (κ hg ). (16)
Consider a noncooperative game played by all local ISPs adjusting their prices, to maximize their utility. The strategy

p * = p k hg : k ∈ K, h ∈ H, g ∈ G where p * hg = p k * hg
constitutes an equilibrium if p * solves the following optimization problems for all players (h, g) (i.e. local ISP h of regional ISP g) max

p hg U hg p hg , p * \ p * hg (17)
Proposition 4 shows a condition under which a Nash equilibrium exists. Details of the proof for the proposition is given in A.

Proposition 4: There exists a pure Nash equilibrium in the competition between ISPs if

p k hg ∈ 0, β + 2 β (τ -α) . (18)
Proposition 5 describes a pure Nash equilibrium where the decision of the ISPs on their prices and the caching factor are independent. It infers that a possible equilibrium under competition in ICNs is a state where all ISPs join together to exchange content and create a federated model (i.e. all ISPs share their cache and agree on a price).

Proposition 5: There is an equilibrium under which the caching factor has no effect on the decision of the ISPs:

p k * hg = β + 1 β (τ -α) . (19)

VII. EVALUATION

In this section, we evaluate the algorithm performance and impact of several parameters on the cost of the content delivery system in the context of one ISP. We then investigate the impact of caching investment of ISPs on their utility under the competition among multiple ISPs.

We first evaluate the LPC and APC algorithms under a practical setting. A video delivery network in practice uses ADSL/VDSL in rural and suburbia or DOCSIS/FTTH in urban areas as a data communications technology between end-users and an intermediate server. In both cases we do propose aggregation points like DSLAM (i.e. a digital subscriber line access multiplexer), HFC (i.e. a hybrid fiber-coaxial) or OLT (i.e. Optical Line Termination) with caching capacity. In the network modeled in this paper, the number of users managed by a DSLAM is 200 users on average with median about 400, however most DSLAMs are stack into tree-like structure due to the geographical arrangement of underlying network topology. In summary because of DSLAM stacking principle the number of connected end-users into a single access router may be estimated to be on average about 2000. The video catalog of a content provider is composed of several thousand titles (e.g. Netflix's catalog contains approximately 18,000 active titles [START_REF] Bellante | On Netflix catalog dynamics and caching performance[END_REF] and [START_REF] Zhou | Large-scale parallel collaborative filtering for the Netflix prize[END_REF] ). We compare the LPC heuristic and the APC heuristic under a scenario composed of 1000 STBs, and 10,000 content objects. We assume that a STB can store up to 5 content objects and the intermediate server can store up to 50 content objects. The uplink capacity between a STB and the intermediate server is c 0 = 2 content objects. The transmission cost between the intermediate server and the root, and the one between a STB and the intermediate server are set equal to w 1 = 9 and w 0 = 1 respectively. Using the above setting, we evaluate the heuristic algorithms under 100 scenarios of content demands when the content popularity follows the Zipf distribution with the exponent varying from 0.6 to 1.6. We observe the experimental results in Fig. 3. The APC algorithm provides a better result when the Zipf's exponent of the content popularity distribution is less than 1.4 whilst the LPC algorithm provides performs better for higher values of the Zipf's exponent.

Second, we study the impact of the uplink capacity on the routing cost. In our evaluation, the content popularity follows the Zipf distribution with the exponent α = 1.2. The uplink capacity varies between 0 and 5 and other parameters are similar to those of the setting of the first evaluation. In Fig. 4, we observe that the cost significantly decreases when the system offers more sharing opportunities up to a point when the cost reduces slowly. Indeed, it is observed that the costs provided by APC and LPC respectively decreases by 70% and 25% by obtaining content from neighbor STBs when the uplink capacity changes from 0 to 1. The result suggests that a network provider only needs a small uplink bandwidth for improving the performance of its content delivery system, which is especially important for a network provider using a popular ADSL technology whose uplink bandwidth is limited.

Third, we evaluate the impact of distributing a fixed storage capacity between the intermediate server and the STBs. We consider a scenario where n = 1000, m = 10, 000, w 1 = 3, w 0 = 2, and c 0 = 2 under 100 scenarios of content demands. We vary the storage capacity of the intermediate server or the STBs while keeping their total storage capacity fixed. Table I presents the parameter settings for the storage capacity in our evaluation. Figure 5 compares the routing cost of LPC in the case of adding storage capacity to the intermediate server (lines with circle markers) to the one in the case of adding storage capacity to the STBs (lines with upwardpointing triangle markers). Figure 5(a)-(b) shows the results when Zipf's exponent of the content popularity distribution is α = 0.8, and α = 1.2, respectively. We observe that adding storage capacity to the intermediate server is more valuable than adding storage capacity to the STBs when Zipf's exponent is low (i.e. α = 0.8), but the result is opposite when Zipf's exponent is high (i.e. α = 1.2). This implies that the content popularity has a major impact on the caching allocation policies.

For the purpose of comparison with optimal results, we now consider a limited size scenario composed of 10 STBs, 150 content objects, and 500 scenarios of content demands. In our evaluation, a STB can store one content object and the intermediate server can store up to 5 content objects. The uplink capacity between a STB and the intermediate server is 5 content objects. The transmission cost between the intermediate server and the root, and the one between a STB and the intermediate server are set equal to w 1 = 10 and w 0 = 1 respectively. We use the IBM ILOG CPLEX Optimizer to solve the linear programming model (P 2 ) in order to obtain optimal results. Figure 6 shows the results. We observe that the cost improves in the network where there are a few popular content objects, the results provided by the LPC and APC algorithms are close to the optimal result especially when the Zipf's exponent is high. In the figure, they are approximately 8 percent higher than the optimal result. Fig. 7. Utility of local ISP 1 of regional ISP 1 at equilibrium when local ISP 1 of regional ISP 1 increases its caching investment Finally, we study the impact of caching in a context of multiple ISPs including two regional ISPs and two local ISPs connected to each regional ISP. We consider the following function of caching cost

C a hg (κ hg ) = c 1 c 2 c 3 1-κ hg -c 1 c 2 c3
where c 1 , c 2 and c 3 are constants. The value of the function tends to infinite as κ → 1, and tends to zero as κ → 0. These properties of the caching cost function agree with the fact that it is mostly impossible for the ISP to cache all content objects in the Internet and the ISP does not pay a caching cost if he does not invest in a caching system. For illustration purposes, the parameters of the caching cost function are given by c 1 = c 3 = 1 and c 2 = 2. We set the parameters of the caching cost function [START_REF] Fayazbakhsh | Less pain, most of the gain: Incrementally deployable ICN[END_REF] to D = 100 and β = 2. The parameters of the congestion cost function ( 13) is α = 1.

The revenue of the ISP when fulfill one content demand in the revenue function ( 15) is τ = 3. The caching factor κ of local ISP 1 of regional ISP 1 varies between 0.4 and 0.9 while the caching factor of other ISPs is 0.4. Fig. 7 and Fig. 8 plot the utility of local ISP 1 of regional ISP 1 and local ISP 1 of regional ISP 2 respectively. Fig. 7 shows that the utility of a local ISP increases until its caching investment reaches a threshold, and then it drops sharply. The results infer that it is not profitable for a local ISP to have a huge investment in caching in order to cache both content items with high popularity and those with low popularity. Fig. 8 shows that the utility of other local ISPs increases when one local ISP invests in caching. It occurs because a local ISP can provide a better service to its customers when it receives data packet from a neighbor ISP rather than a content provider that is far from its location.

The above results demonstrate that we have designed an efficient and tractable solution for routing and caching strategies in a CCN-based architecture providing VoD services. The solution can be deployed using a recommendation service that extrapolates user's interest as this exist in many operational platforms today. The ISP can use this solution at best times, facing a change in the demand and/or to benefit from opportunities in resource availabilities. Fig. 8. Utility of local ISP 1 of regional ISP 2 at equilibrium when local ISP 1 of regional ISP 1 increases its caching investment VIII. CONCLUSION Our work introduces an architecture of VoD system on top of content-centric networking and addresses a joint optimization problem of content routing and content caching in the system. We believe such an architecture is highly beneficial in content delivery services as illustrated by our evaluation, which shows a significant improvement of performance with small investment in storage and bandwidth for content sharing. Our proposed heuristic algorithms for optimizing content routing and caching in the system were evaluated in both theoretical analysis and implementation, providing a practical solution to this problem. Our work also contributes to an analysis of caching investment in a context of multiple interconnected ISPs. The ISP can use our game-theoretical model to analyze its utility under competition with other ISPs by adapting the cost and revenue functions to various contexts. In future work, it would be of interest to consider storage costs in the objective function of the optimization problem, and to investigate their impact on the solutions obtained. APPENDIX A PROOF OF PROPOSITION 4 From ( 12), ( 13), ( 14), ( 15), ( 16 < 0. Thus, U hg is concave. Since a concave function is quasiconcave, U hg is quasiconcave. We have the sets of actions of all ISPs are nonempty compact convex subsets of a Euclidian space, and the utility function U hg of the ISPs are continuous and quasi-concave on their set of actions. Hence, there exists a pure Nash equilibrium.

Fig. 1 .

 1 Fig. 1. Content delivery system: (a) An example of a physical VoD system (b) Model

Proof:

  We differentiate U hg w.r.t p k hg , ∂U hg / ∂ p k hg , as computed in Appendix A. p k * hg = β+1 β(τ -α) is an equilibrium in the game. Indeed, substituting p k * hg = β+1 β(τ -α) , we find

Fig. 3 .

 3 Fig. 3. Comparison between the LPC algorithm and the APC algorithm

Fig. 4 .

 4 Fig. 4. Impact of uplink capacity

Fig. 5 . 2 0Fig. 6 .

 526 Fig. 5. Routing cost for LPC when distributing storage capacity between the server and STBs: (a) α = 0.8, (b) α = 1.2

  hg (κ hg ) By differentiating U hg w.r.t p k hg , we obtain β+2 β(τ -α) , we have ∂ 2 U hg / ∂ p k hg 2

  G, where κ hg ∈ [0, 1] is the caching factor. We will refer to local ISP h connected to regional ISP g as ISP (h, g). ISP (h, g) does not invest in caching if κ hg = 0, and it can cache all content items if κ hg = 1. Let q

	content providers p
						Content providers
			k=5
	regional ISP g									k=6
			1						2
						. . .
	ISP h
	k=1	1			2	k=2	k=3	1			2	k=4
	1	. . .	n	1	. . .	n	1	. . .	n	1	. . .	n
		STB
			Interest packet forwarded to the root can be
			satisfied by a local ISP, a regional ISP, or a
			content provider
	Fig. 2. Caching under competition among multiple ISPs
	ISP g ∈ k	hg be a number of
	content demands that are requested by STBs of ISP (h, g),
	and satisfied by node k

TABLE I

 I

	PARAMETER SETTINGS FOR EVALUATING THE IMPACT OF ADDING
		STORAGE CAPACITY
		(Server's capacity, STB's capacity,
		total capacity)
	Increase	(1000, 1, 2000),
	server's capacity	(2000, 1, 3000), (3000, 1, 4000),
		(4000, 1, 5000), (5000, 1, 6000)
	Increase	(1000, 1, 2000),
	STB's capacity	(1000, 2, 3000), (1000, 3, 4000),
		(1000, 4, 5000), (1000, 5, 6000)

ACKNOWLEDGMENTS

The work presented in this paper has been carried out at LIP6 (http://www.lip6.fr) and LINCS (http://www.lincs.fr). The first author was partially supported by MOET Grant B2016-SPH-17.


Claude Cibils

Hochschild cohomology algebra of radical square zero algebras

Keywords:

We compute the dimension at each degree of the Hochschild cohomology of a radical square zero finite dimensional algebra, in terms of the combinatorics of its quiver. The multiplicative structure is obtained as well, those algebras are finitely generated only for quivers without oriented cycles and for crowns.

Introduction

The Hochschild cohomology algebra of a finite dimensional algebra is not easy to compute in general. It gives inside to the homological global dimension (see [START_REF] Happel | Hochschild cohomology of finite-dimensional algebras[END_REF]) and is closely related to the deformations of the algebra via its value in degree 2 and suitable obstructions (see [START_REF] Gerstenhaber | On the deformations of rings and algebras[END_REF]). In [START_REF] Cibils | Rigid monomial algebras[END_REF][START_REF] Cibils | Rigidity of truncated quiver algebras[END_REF][START_REF] Cibils | 2-nilpotent and rigid finite dimensional algebras[END_REF][START_REF] Cibils | On the Hochschild cohomology of finite dimensional algebras[END_REF][START_REF] Cibils | Hochschild homology of an algebra whose quiver has no oriented cycles[END_REF] a classification of rigid families is performed and cohomology groups are described. Recently Holm obtained in [START_REF] Holm | The Hochschild cohomology ring of a modular group algebra: the commutative case[END_REF] an explicit computation for finite abelian group algebras; then A. Solotar and the author showed that for these algebras the Hochschild cohomology algebra is isomorphic to the tensor product of the group algebra and the usual cohomology algebra of the group ( [START_REF] Cibils | Hochschild cohomology algebra of abelian groups[END_REF]). Moreover a close relation seems to exist between the structure of the Hochschild cohomology algebra and the monoidal structure of the category of Hopf bimodules over a Hopf algebra, see [START_REF] Cibils | Tensor product of Hopf bimodules over a group algebra[END_REF].

In view of these results, it became interesting to write observations obtained some years ago: I lectured at Séminaire P. Dubreuil and M.-P. Malliavin in Paris (1990) on the additive structure of the Hochschild cohomology algebra of a radical square zero algebra; in Salt Lake City meeting on Homological methods in representation theory (1991) I lectured on the multiplicative aspects.

A radical square zero algebra is a finite dimensional algebra over a field k such that the square of its Jacobson radical is already zero. Since Hochschild cohomology is Morita invariant, we consider the corresponding basic algebra. More precisely, let Q be a connected and finite quiver and let (kQ) 2 be the quotient of the path algebra of Q by the two-sided ideal generated by paths of length 2. The case when the quiver is a crown is exceptional; out of this case, the dimension of each Hochschild cohomology vector space H n ((kQ) 2 , (kQ) 2 ) is the difference between the number of couples composed by a path of length n and an arrow sharing the same starting and ending vertices and the number of oriented cycles of length n-1. This computation can be performed using a reduced projective resolution presented in [START_REF] Cibils | Rigid monomial algebras[END_REF][START_REF] Cibils | Rigidity of truncated quiver algebras[END_REF] of an algebra having a maximal separable subalgebra. Then we are able to produce suitable models for the cochains vector spaces and coboundaries maps.

The cup-product (or Yoneda product) can also be described. We obtain that the Hochschild cohomology algebra is not finitely generated in general, except of course if Q has no oriented cycles -the Hochschild cohomology vanish in this case at high enough degrees -, and in the exceptional crown case. This result has to be compared with Venkov's Theorem ( [START_REF] Venkov | Cohomology algebras for some classifying spaces[END_REF] and also [START_REF] Benson | Representations and cohomology II[END_REF]): for finite group algebras the cohomology algebra is always finitely generated.

We will also relate the results with previous work on the deformation theory of square radical zero algebras from [START_REF] Cibils | 2-nilpotent and rigid finite dimensional algebras[END_REF]; cyclic and Hochschild homology of this class of algebras has been obtained in [START_REF] Cibils | Cyclic and Hochschild homology of 2-nilpotent algebras[END_REF].

The work presented in this paper has the advantage of being mostly selfcontained: once the correct framework is established, there is no difficulty for carrying on the observations. Partial aspects of the present computations have been written in a manuscrit by a former Diploma student M. Blater at Geneva in 1994. E. Marcos told me at the Conference on representations of algebras Geiranger (1996) that he has made computations for crowns, obtaining that the Hochschild cohomology algebra is finitely generated in that case. Notice also recent results on Hochschild homology of truncated and quadratic monomial algebras obtained by Sköldberg in [START_REF] Sköldberg | The Hochschild homology of truncated and quadratic monomial algebras[END_REF] using the minimal projective resolution of Annick and Green ( [START_REF] Anick | On the homology of quotients of path algebras[END_REF]).

Resolution and models

Let Λ be a finite dimensional k-algebra, where k is a field, affording a maximal semisimple algebra E which is separable; the Wedderburn-Malcev Theorem (see for instance [START_REF] Curtis | Methods of representation theory, Pure & applied mathematics[END_REF]) holds and we have a decomposition Λ = E ⊕ r where r is the Jacobson radical of Λ. Then the Hochschild cohomology of a Λ-bimodule M is the cohomology of the following complex of cochains (see [START_REF] Cibils | Rigid monomial algebras[END_REF][START_REF] Cibils | Rigidity of truncated quiver algebras[END_REF]):

0 → M E → Hom E-E (r, M ) → • • • → Hom E-E r ⊗ E n , M → • • • where M E = {m ∈ M | em = me for all e in M } and Hom E-E r ⊗ E n
, M is the vector space of E-bimodule morphisms from the tensor product over E of n copies of r to the E-bimodule M obtained by restricting the Λ actions. The coboundaries δ are given by

(δm)(x) = xm -mx for m ∈ M E and x ∈ r, δf (x 1 , . . . , x n+1 ) = x 1 f (x 2 , . . . , x n+1 ) + (-1) i f (x 1 , . . . , x i x i+1 , . . . x n+1 ) + (-1) n+1 f (x 1 , . . . , x n ) x n+1 for f ∈ Hom E-E r ⊗ E n
, M and where we have replaced the tensor product symbols by commas.

Of course, the interesting feature of this cochain complex in case of a square radical zero algebra is that the middle-sum terms of the coboundary vanish. We have

δf (x 1 , . . . , x n+1 ) = x 1 f (x 2 , . . . , x n+1 ) + (-1) n+1 f (x 1 , . . . , x n ) x n+1 .
Let now Q be a quiver, that is a finite oriented graph given by two sets, the set of vertices Q 0 and the set of arrows Q 1 , provided with two maps s and t : Q 1 → Q 0 corresponding to the source and the terminus vertices of each arrow. A path of length n is a sequence of arrows γ = a n • • • a 1 such that t(a i ) = s(a i+1 ) for each possible i. We put s(γ) = s(a 1 ) and t(γ) = t(a n ). We agree that a vertex e is a path of length zero with source and terminus vertices e itself.

The quotient of the path algebra of Q by the two-sided ideal generated by paths of length 2 can be described directly as follows: let kQ 0 be the semisimple commutative algebra which has Q 0 as a complete set of primitive orthogonal idempotents. Let also kQ 1 be the vector space which has Q 1 as a basis, equipped with its natural bimodule structure: ea = δ e,t(a) a and ae = δ e,s(a) a where e is a vertex, a is an arrow and δ x,y the Kronecker symbol having value 1 if x = y and 0 otherwise.

We denote (kQ) 2 the vector space kQ 0 ⊕ kQ 1 with the algebra structure given by (e, x)(e , x ) = (ee , ex + xe ).

This finite dimensional algebra has square zero Jacobson radical r = kQ 1 , and E = kQ 0 is a maximal semisimple subalgebra already separable. Actually any finite dimensional algebra having radical square zero over an algebraically closed field is Morita equivalent to an algebra (kQ) 2 , where Q has vertices given by the set of isomorphism classes of simple modules, and the number of arrows between two vertices is the dimension of Ext 1 between the corresponding simple modules.

We consider now more in detail the cochain space Hom E-E (r ⊗ E n , Λ), where the bimodule M is given by the algebra itself Λ = (kQ) 2 , where Q is an arbitrary quiver and k any field. First we have the following immediate result: Lemma 2.1 Let r = kQ 1 be the Jacobson radical of (kQ) 2 and let E = kQ 0 .

Then r ⊗ E n has a basis given by Q n , the set of paths of length n.

We introduce now the following notation: let X and Y be sets of paths. The set X//Y of parallel paths is the set of couples (γ, γ ) from X × Y such that s(γ) = s(γ ) and t(γ) = t(γ ). For example Q n //Q 0 is the set of oriented cycles of length n. In the following, we will denote kB the vector space having a given set B as a basis.

Lemma 2.2 For the algebra Λ = (kQ) 2 the vector space Hom

E-E r ⊗ E n , Λ is isomorphic to k (Q n //Q 0 ) ⊕ k (Q n //Q 1 ). Proof: Since Λ = E ⊕ r is a decomposition of Λ as a direct sum of E- bimodules, we have Hom E-E r ⊗ E n , Λ = Hom E-E r ⊗ E n , E ⊕ Hom E-E r ⊗ E n , r .
The kQ 0 -bimodule decomposition of r

⊗ E n = kQ n is among Q n , more precisely kγ is a one-dimensional sub-bimodule of r ⊗ E n for each γ ∈ Q n .
Moreover the action of the vertices are zero on γ except for t(γ) on the left and s(γ) on the right, this vertices acts as the identity: we say that kγ is of type (t(γ), s(γ)). The kQ 0 -bimodule decomposition of kQ 0 is among Q 0 , each vertex e provides a direct summand of type (e, e). Now we have that Hom E-E (U, V ) = 0 if U and V are simple E-bimodules not of the same type (this is Schur's Lemma which is immediate in this context). Finally we infer the following linear isomorphism

k (Q n //Q 0 ) → Hom kQ 0 -kQ 0 (kQ n , kQ 0 )
where (γ, e) ∈ Q n //Q 0 is sent to the elementary map which associates e to γ and 0 to any other path of Q n . Similarly we have that

(γ, a) → γ → δ γ,γ a is a linear isomorphism from k(Q n //Q 1 ) to Hom kQ 0 -kQ 0 (kQ n , kQ 1 ) . Remark 2.3 In degree 0, the vector space Λ E is identified with k(Q 0 //Q 0 )⊕ k(Q 0 //Q 1 ). Notice that Q 0 //Q 0 is simply Q 0 , and that Q 0 //Q 1 is the set of loops of Q.
We wish now to translate the coboundaries through these linear isomorphisms. Let

D : k (Q n //Q 0 ) -→ k (Q n+1 //Q 1 ) given by D(γ, e) = a∈Q 1 e (aγ, a) + (-1) n+1 a∈eQ 1 (γa, a)
where Q 1 e (resp. eQ 1 ) is the subset of Q 1 of arrows with prescribed source (resp. terminus) vertex e. Proposition 2. [START_REF] Cibils | Rigid monomial algebras[END_REF] The diagram where the vertical maps are given by the linear isomorphisms of Lemma 2.2, the coboundary map δ of the reduced complex of cochains at the top horizontal, and at the bottom the map

k (Q n //Q 0 ) ⊕ k (Q n //Q 1 ) 0 0 D 0 -→ k (Q n+1 //Q 0 ) ⊕ k (Q n+1 //Q 1 )
is commutative.

Verifications are straightforward, using that the algebra has zero radical square.

Remark 2.5 If Q has no oriented cycles, there is a path of maximum length m. From the above result we infer that H n (kQ) 2 , (kQ) 2 is zero for n > m

Hochschild cohomology

Since Hochschild cohomology is additive on a product of algebras, we will assume that the considered quivers are connected.

A c-crown is a quiver with c vertices cyclically labeled by the cyclic group of order c, and c arrows a 0 , • • • , a c-1 such that s(a i ) = i and t(a i ) = i + 1. A 1-crown is a loop, and a 2-crown is the two-way quiver. Theorem 3.1 Let Q be a connected quiver which is not a crown. Then for n > 0 we have

dim k H n (kQ) 2 , (kQ) 2 = | Q n //Q 1 | -| Q n-1 //Q 0 | . We also have dim k H 0 (kQ) 2 , (kQ) 2 = | Q 1 //Q 0 | +1.
Proof: We will show the probably most interesting observation of this work, namely that D is injective for a positive n and for quivers which are not crowns. We fix a notation: if γ is an oriented path of positive length, f (γ) and l(γ) denotes the first and last arrows of γ respectively. Moreover the support of an element x expressed in a basis B of a vector space is the subset of B determined by the non zero coefficients of x.

Let x = (γ,e)∈k(Qn//Q 0 ) x (γ,e) (γ, e) be an element of the kernel of D. We fix an oriented cycle (γ, e) in order to show that its field coefficient x (γ,e) is zero. The contribution of x (γ,e) (γ, e) in D(x) is

x (γ,e) ⎡ ⎣ a∈Q 1 e (aγ, a) + (-1) n+1 a∈eQ 1 (γa, a) ⎤ ⎦ .
Let us say that a vertex is concerned by an arrow a if it coincides with either the source or the terminus vertex of a. We claim first that if the vertex e is concerned by other arrows than f (γ) or l(γ), then x (γ,e) is already zero. Indeed, let a be such an arrow with for instance s(a) = e and a = f (γ); then the basis element (aγ, a) is not in the support of D(γ , e ) for any (γ , e ) other than (γ, e). To see this, suppose first that (aγ, a) = (a γ , a ); then a = a and γ = γ . Secondly suppose (aγ, a) = (γ a , a ); then a = a and a is the first arrow of γ: we have supposed this is not the case. When a is an arrow with t(a) = e and a = l(γ), the analogous proof applies.

We assume now we are in the leaving situation, that is Q 1 e = {f (γ)} and eQ 1 = {l(γ)}. Consider the "rotated" (γ, e) of (γ, e), namely remove f (γ) from the beginning of γ and add it at its end: if γ = l(γ) • • • a 2 f (γ) then γ = f (γ)l(γ) . . . a 2 and e = s(a 2 ) = t(f (γ)). Our second claim is that x (γ,e) = (-1) n x γ,e . Indeed we have that (f (γ)γ, f (γ)) is of course in the support of D(γ, e) and also in the support of D(γ, e) since (γf (γ), f(γ)) = (f (γ)γ, f (γ)). But (f (γ)γ, f (γ)) is not in any other support of the image by D of a basis element. To prove this, let first (γ , e ) be a cycle such that there exist a ∈ Q 1 e verifying (aγ , a) = (f (γ)γ, f (γ)). Then f (γ) = a and γ = γ . Let secondly (γ , e ) be a cycle such that there exist a ∈ e Q 1 with (γ a, a) = (f (γ)γ, f (γ)). Then a = f (γ), γ f (γ) = f (γ)γ and γ is the rotated γ of γ. We infer that the coefficient of (f (γ)γ, f (γ)) in D(x) is x (γ,e) + (-1) n+1 x (γ,e) . This has to be zero since we are assuming that D(x) = 0, and since Q n+1 //Q 1 is a basis.

The end of the proof is an induction process: if e is concerned by some other arrow than f (γ) or l(γ), we infer x (γ,e) = 0 by the first claim. The second claim provides our aim x (γ,e) = 0. If e is not concerned by other arrows than f (γ) or l(γ), we rotate γ and we analyze arrows at e. The process has a successful end: rotating n times (γ, e) returns to (γ, e) and at some rotation stage we have to meet an "exotic" arrow -not the first, not the last -, otherwise the connected quiver is a crown and γ some power of the minimal oriented cycle at one of its vertices.

The linear map D at zero degree is certainly not injective, since we know that H 0 (Λ, Λ) is always the center of Λ; for Λ = (kQ) 2 , a basis of the center is provided by the set of loops Q 1 //Q 0 together with the unit element of the algebra, namely the sum of all the vertices. Furthermore it is immediate to verify that the kernel of

D : k(Q 0 //Q 0 ) → k(Q 1 //Q 1 )
given by D(e, e) = a∈Q 1 e (a, a) -a∈eQ 1 (a, a) is indeed one-dimensional, generated by e∈Q 0 (e, e) (recall that Q is connected).

Before considering the exceptional crown case, we point out a fact from the previous dimensional computation.

Corollary 3.2

Let Q be a connected quiver which is not a crown, k be a field and (kQ) 2 the corresponding radical square zero algebra. The graded cohomology H * ((kQ) 2 , (kQ) 2 ) = ⊕ n≥0 H n ((kQ) 2 , (kQ) 2 ) is finite dimensional if and only if Q has no oriented cycles. More precisely, if there is an oriented cycle of length c, then H cn+1 ((kQ) 2 , (kQ) 2 ) = 0 for all positive n.

Proof:

We already noticed that if Q has no oriented cycles, the degree of the non-zero cohomology vector spaces is bounded by the maximal length of a path. We need to prove that the inequality

| Q n-1 //Q 0 | < | Q n //Q 1 | holds whenever Q n-1 //Q 0 is non empty. Consider the following set monomor- phism Q n-1 //Q 0 → Q n //Q 1
given by (γ, e) → (l(γ)γ, l(γ)) where l(γ) denotes as before the last arrow of γ. Since Q is not a crown, this map is not surjective.

Proposition 3.3 Let Q be a c-crown with c ≥ 2. The center of (kQ) 2 is one-dimensional. If the characteristic of k is not two, let n be an even multiple of c. Then dim k H n (kQ) 2 , (kQ) 2 = dim k H n+1 (kQ) 2 , (kQ) 2 = 1.
The cohomology vanishes in all other degrees. Moreover, a non-trivial n-cochain is provided by the sum of all the cycles of length n. A non-trivial n + 1-cochain is given by (aγ, a) for any chosen cycle γ of length n with first arrow denoted a.

If the characteristic of k is two, the above dimensions are valid for any multiple of c, the non-trivial cochains are given as before.

Proof: We have to consider the kernel of

D : k (Q n //Q 0 ) → k (Q n+1 //Q 1 ) .
Notice first that Q n //Q 0 and Q n+1 //Q 1 are empty if n is not a multiple of c. Now assume that c divides n and consider the cyclic group G = < t | t c = 1 > labeling the vertices of the crown; each cycle of length n is determined by its source and terminus vertex in G, hence we obtain a bijection between Q n //Q 0 and G. Similarly, each couple of Q n+1 //Q 1 is determined by their common source vertex, we also have a bijection with G. Through this bijections the map D becomes a linear endomorphism D of kG given by D (t i ) = t i + (-1) n+1 t i-1 . Now it is straightforward to verify that D has one-dimensional kernel given by the sum of elements of G if n is even, or for any n in case of characteristic two. If n is odd, D is injective for a field of characteristic not two.

The result follows, since the assumption c ≥ 2 insures enough distance between non-zero cochain vector spaces.

The case of a loop (c = 1) is special since there is no longer vanishing cochain vector spaces, and the coboundaries maps interact: Proposition 3. [START_REF] Cibils | Rigid monomial algebras[END_REF] Let Q be a loop a, the corresponding algebra (kQ) 2 is k[a]/a 2 . Assume k is not of characteristic two. For every n > 0, we have

dim k H n ((kQ) 2 , (kQ) 2 ) = 1.
If n is even (a n , a) generates linearly the cohomology at degree n; for n odd, (a n , 1) is a linear generator at degree n + 1.

If the characteristic of k is two, the coboundaries are zero and each Hochschild cohomology vector space is two-dimensional.

Cup-product

In the context of the reduced cochain complex of the beginning of Section 1, the cup-product is the following: let f and g be cochains of degree n and m respectively. Then f g is the cochain of degree n + m given by f g(x 1 , . . . , x n , y 1 , . . . , y m ) = f (x 1 , . . . , x n )g(y 1 , . . . , y m ).

As usual we have: δ(f g) = δf g + (-1) n g δf. This implies the existence of a well defined product in Hochschild cohomology. In case of a radical square zero algebra this can be easily described. Recall that if Q is connected and is not a crown, any cocycle can be represented as a linear combination of elements of Q n //Q 1 . Relations are provided by the image of D.

Lemma 4.1 If Q is a connected quiver which is not a crown, the cupproduct of elements of positive degree is always zero for the Hochschild cohomology of (kQ) 2 .

Proof: Consider elements of k (Q n //Q 1 ) and k(Q m //Q 1 ) as cochains representing cocycles, and recall that the corresponding E-bimodule morphisms have values in the radical. Since r 2 = 0, the cup product is already zero at the cochain level.

Lemma 4.2

The center of (kQ) 2 is isomorphic to the algebra k[l 1 , . . . , l r ] where {l 1 , . . . , l r } is the set of loops; each loop has square zero and is orthogonal to the others. Moreover, loops and elements of positive degree are orthogonal in Hochschild cohomology.

Let Q be a connected quiver which is not a crown. Let Z = k[l 1 , . . . , l r ] be the center of (kQ) 2 as above, and let X be a vector space of dimension i>0 dim k H i ((kQ) 2 , (kQ) 2 ) -this sum is finite if and only if Q has no oriented cycles, see Corollary 3.2 -. Consider on X the trivial Z-bimodule structure, i.e. l i x = xl i = 0 for all i and for all x ∈ X, the unit element acts of course as the identity. Proposition 4.3 Let Q be a connected quiver which is not a crown. Then the Hochschild cohomology algebra H * ((kQ) 2 , (kQ) 2 ) is isomorphic to Z ⊕X where the product is given by

(z, x)(z , x ) = (zz , zx + xz ).
Remark 4.4 Any finite subset of the above algebra generates a finite dimensional sub-algebra. Hence as soon as the quiver has an oriented cycle (but is not a crown), the Hochschild cohomology is not finitely generated.

We observe now that we retrieve the conditions obtained in [START_REF] Cibils | 2-nilpotent and rigid finite dimensional algebras[END_REF] in order to insure the rigidity of a radical square zero algebra:

dim k H 2 ((kQ) 2 , (kQ) 2 ) = | Q 2 //Q 1 |
which is exactly the number of unoriented triangles for such quivers. Proof: We have proved that the Hochschild cohomology of a c-crown (c ≥ 2) is non-zero only for degrees n and n + 1, where n is a multiple of c . At degree n the cohomology is linearly generated by the E-bimodule morphism

f n : r ⊗ E n → E
which sends each oriented cycle of length n to its source-terminus vertex. At degree n + 1, the cohomology is given by

g n : r ⊗ E n+1 → r
obtained through the choice of a particular oriented cycle γ of length n with first arrow called a: we have g n (aγ) = a and g n vanish on any other basis element. The element in cohomology does not depend on the choice of γ.

From this description, we obtain the following: since we know that f c = 0 in cohomology, we have (f c ) m = f c m . We know also that g c = 0, and we have g 2 c = 0. Moreover g c (f c ) m = (f c ) m g c = g c m .

The presentation follows, with f c = f and g c = g.

There is no difficulty in order to perform the analogous computations for a crown and we leave them to the reader.

Discussion:

The methods developed in this work can perhaps be extended in order to describe the Hochschild cohomology algebra of a truncated quiver algebra -every path of a given length is zero -. More generally, the monomial algebras -some chosen paths are zero -can perhaps also be reached. An interesting application will be to compute for a non-trivial 2-cocycle the obstructions in order to realize it as a non-trivial deformation of the algebra (see [START_REF] Gerstenhaber | On the deformations of rings and algebras[END_REF]).

Theorem 4 . 6

 46 Let k be a field and let Q be a c-crown with c ≥ 2. Then H * ((kQ) 2 , (kQ) 2 ) is isomorphic to k[f, g]/g 2 , where f and g are commuting variables of degrees c and c + 1 respectively (if k has characteristic two or if c is even, we put c = c; otherwise c = 2c).

  If Q is a 2-crown or a loop, H 2 ((kQ) 2 , (kQ) 2 ) = 0 regardless the characteristic of the field; other crowns has zero 2-cohomology. Then assume Q is not a crown. If Q has a loop, we know from Corollary 3.2 that H 2 ((kQ) 2 , (kQ) 2 ) = 0. Now assume Q has no loops; then

	Proposition 4.5 Let Q be a connected quiver. Then H 2 ((kQ) 2 , (kQ) 2 ) = 0
	if and only if
	1) Q has no loops,
	2) Q do not contain unoriented triangles, i.e. 3 vertices and 3 arrows
	not performing an oriented cycle.
	3) Q is not the 2-crown.

Proof:


Myriam Grillot

Jonathan Vayssières

Benoit Gaudou

Alassane Bah

Dominique Masse

An agent-based model to analyze the ecological functioning of agro-silvo-pastoral landscapes in West Africa

Keywords: Agent-based-model, agro-silvo-pastoral ecosystem, biomass flows, multi-scale analysis

come   L'archive ouverte pluridisciplinaire

Open Archive TOULOUSE Archive Ouverte (OATAO)

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible. This is an author-deposited version published in : http://oatao.univ-toulouse.fr/ Eprints ID : 17125

The contribution was presented at iEMSs 2016: http://www.iemss.org/sites/iemss2016/ Any correspondence concerning this service should be sent to the repository administrator: staff-oatao@listes-diff.inp-toulouse.fr

Abstract

Biomass recycling plays a major role in the functioning and sustainability of agro-silvo-pastoral ecosystems in West Africa. However, farming systems must adjust rapidly to changing landscapes. This abstract describes an Agent-Based Model (ABM) that analyzes nutrient (N) cycles within the village "terroir" agro-ecosystem to assess how changes in land use and farming practices affect croplivestock integration and spatial heterogeneity. The ABM is implemented on the GAMA platform (Generic Agent-based Modelling Architecture). Each simulated household is classified according to a farm type with a pre-defined biomass management strategy (use of crop products, manure, etc.). The model is spatially explicit, with biomass being moved across landscape units and through different ecosystem components: soil, plants, animals, humans, etc. Biomass flows are converted into N flows which are then used to calculate indicators such as N balance, N use efficiency, and the diversity and recycling indexes that characterize N cycles. The model was parameterized through on-farm measurements of crop and livestock productions (for the biophysical sub-system) and participatory workshops with farmers (for the decision sub-system). The model was validated on the basis of biomass flows observed in two villages in the Senegalese groundnut basin. The model is original in its multi-scale analysis of N cycles occurring at different organizational levels: plot, herd, household and landscape. For instance this highlights the consequences of households' choices at the plot scale for spatial heterogeneity at the landscape scale. This ABM is potentially generalizable for designing ecological intensification pathways in West African village "terroirs".