Mohammad Noormohammadpour

Cauligi S Raghavendra

Srikanth Kandula

Sriram Rao

Ming Hsieh

QuickCast: Fast and Efficient Inter-Datacenter Transfers using Forwarding Tree Cohorts

Keywords: Software Defined WAN, Datacenter, Scheduling, Completion Times, Replication

Several organizations have built multiple datacenters connected via dedicated wide area networks over which large inter-datacenter transfers take place. Since many such transfers move the same data from one source to multiple destinations, using multicast forwarding trees can reduce bandwidth needs and improve completion times. However, using a single forwarding tree per transfer can lead to poor performance as the slowest receiver dictates the completion time for all receivers. Using multiple forwarding trees per transfer alleviates this concernthe average receiver could finish early; however, if done naively, bandwidth usage would also increase and it is apriori unclear how best to partition receivers, how to construct the multiple trees and how to determine the rate and schedule of flows on these trees. This paper presents QuickCast, a first solution to these problems. Using simulations on real-world network topologies, we see that QuickCast can speed up the average receiver's completion time by as much as 10× while only using 1.04× more bandwidth; further, the completion time for all receivers also improves by as much as 1.57× faster at high loads. Thereby, while some implementation challenges remain, we advocate using a cohort of forwarding trees.

I. INTRODUCTION

Software Defined Networking (SDN) is increasingly adopted across Wide Area Networks (WANs) which allows for careful monitoring and management of networks. Large cloud providers, such as Microsoft [1] and Google [2], have built large scale dedicated networks to connect their datacenters that can be operated using SDN. According to prior work, these networks, which we refer to as SD-WAN, connect dozens of datacenters for increased reliability and performance [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF]- [START_REF] Jimenez | Building express backbone: Facebooks new long-haul network[END_REF].

Employing geographically distributed datacenters has many benefits in supporting users and applications. Replicating objects across multiple datacenters improves user-access latency, availability and fault tolerance. For example, Content Delivery Networks (CDNs) replicate objects (e.g. multimedia files) across many cache locations, search engines distribute large index updates across many locations regularly, and VMs are replicated for scale out of applications.

Many inter-datacenter transfers are Point to Multipoint (P2MP) which move the same data form one source to multiple destinations. A P2MP transfer is a special case of multicasting with a single source and a fixed set of receivers known upon arrival of the transfer. These properties together provide an opportunity for network optimizations, such as sizable reductions in bandwidth usage and faster completion times by using carefully selected forwarding trees.

We review several approaches for performing P2MP transfers. One can perform P2MP transfers as many independent point-to-point transfers [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF], [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF], [START_REF] Kandula | Calendaring for wide area networks[END_REF], [START_REF] Jin | Optimizing bulk transfers with software-defined optical wan[END_REF] which waste bandwidth and increase completion times. Internet multicasting approaches [START_REF] Deering | Host Extensions for IP Multicasting[END_REF] build multicast trees incrementally as new receivers join multicast sessions. This can lead to far from optimal multicast trees that use more bandwidth and uneven distribution of load. Application layer multicasting builds endhost based overlay networks that mimic multicast trees [START_REF] Banerjee | Scalable application layer multicast[END_REF]. This may lead to poor performance due to limited visibility into network link level status and lack of control over how traffic is directed in the network. Peer-to-peer file distribution techniques [START_REF] Sherwood | Slurpie: a cooperative bulk data transfer protocol[END_REF], [START_REF] Pouwelse | The Bittorrent P2P File-Sharing System: Measurements and Analysis[END_REF] aim to maximize throughput per receiver which can be far from a globally optimal solution. Centralized multicast tree selection approaches [START_REF] Cao | Datacast: A scalable and efficient reliable group data delivery service for data centers[END_REF] operate on regular and structured topologies of networks inside datacenters and cannot be easily extended to inter-datacenter networks. Other related work either have objectives other than minimizing completion times of inter-datacenter transfers [START_REF] Shen | Reliable multicast routing for softwaredefined networks[END_REF], [START_REF] Huang | Multicast traffic engineering for software-defined networks[END_REF] or do not consider the inter-play among many ongoing interdatacenter transfers for global network-wide optimization [START_REF] Ogawa | One-to-many file transfers using multipath-multicast with coding at source[END_REF].

A recent solution called DCCast [START_REF] Noormohammadpour | DCCast: Efficient Point to Multipoint Transfers Across Datacenters[END_REF] aims to reduce tail completion times of P2MP transfers. DCCast employs a central traffic engineering server with a global view of network status, topology and resources to select forwarding trees over which traffic flows from senders to all receivers. Despite offering bandwidth savings and reduced tail completion times, DCCast can suffer from significant increase in completion times when forwarding trees are large which can occur when P2MP transfers have many receivers. This can cause significant contention across transfers due to many overlapping edges and increase completion times.

In this paper, we propose a new rate-allocation and tree selection technique called QuickCast with the aim of minimizing average completion times of inter-datacenter transfers. QuickCast reduces completion times by replacing a large forwarding tree with multiple smaller trees each connected to a subset of receivers which we refer to as a cohort of forwarding trees. QuickCast applies the fair sharing scheduling policy which we show through simulations and examples minimizes contention for available bandwidth across P2MP transfers compared to other classic scheduling policies.

We demonstrate the effect of bottlenecks, and hence contention, on forwarding trees using an example. Figure 1 shows a scenario where two senders (top nodes) are transmitting over forwarding trees and they share a link, x → y. Since data is transmitted with the same rate over all edges of forwarding trees, and assuming fair division of bandwidth, all receivers will complete at 2T . Using multiple trees, in this case two for the green sender, each tree can be scheduled independently, and thereby reducing completion time of the two receivers on the right from 2T to T . That is, we create a new tree that excludes the bottleneck link, x → y.

To replace a large tree with a cohort of trees, we propose partitioning receiver sets of P2MP transfers into multiple subsets and using a separate forwarding tree per subset. This approach can significantly reduce completion times of P2MP transfers. We performed an experiment with DCCast over random topologies with 50 nodes to determine if there is benefit in partitioning all P2MP transfers. We simply grouped receivers into two subsets according to proximity, i.e., shortest path hop count between receiver pairs, and attached each partition with an independent forwarding tree (DCCast+2CL). As shown in Figure 2, this reduced completion times by 50% while increasing bandwidth usage by 6% (not shown).

Partitioning receivers is a complex non-trivial problem. To minimize additional bandwidth usage and completion times, partitioning should be only applied to some P2MP transfers to avoid creation of additional bottlenecks. For example, using more than one tree for the dashed blue transfer (on left) in Figure 1 will increase contention and will hurt completion times. By carefully selecting P2MP transfers that benefit from partitioning and using an independent forwarding tree per partition, we can considerably improve average completion times with small extra bandwidth usage. We refer to this approach as selective partitioning. We limit the number of partitions per transfer to two to minimize bandwidth overhead of additional edges, minimize contention due to overlapping trees and limit the number of network forwarding entries. This is however an open problem and it is unclear what the optimal approach is or whether there is an approach that always leads to optimal solution.

We investigate various scheduling policies namely FCFS used in DCCast, Shortest Remaining Processing Time (SRPT) and fair sharing based on Max-Min Fairness (MMF). Although SRPT is optimal for minimizing mean completion times on a single link, we find that MMF can offer much lower completion times over forwarding trees as they grow and as offered load increases both of which increase contention over available bandwidth. In such scenarios, any fair sharing approach over forwarding trees may offer better completion times and higher average utilization compared to both SRPT and FCFS. One such example is later shown in Figure 4 and discussed in §III-A.

Using a cohort of forwarding trees per P2MP transfer can also increase reliability in two ways. First, in case of a link failure, using more than one tree makes it less likely that all receivers are impacted. In case subsequent trees are constructed in a link disjoint manner, no single link failure can disconnect all receivers. Second, by mitigating the effect of bottleneck links, a number of receivers will complete reception earlier which reduces the likelihood of data loss due to failures.

To evaluate QuickCast, we perform extensive simulations using both synthetic and real inter-datacenter traffic patterns over real WAN topologies. We find that performance gain of QuickCast depends on the offered load and show that under heavy loads, QuickCast can improve mean times by as much as 10× and tail times by as much as 1.57× while imposing up to 4% increase in bandwidth usage compared to DCCast. Although QuickCast can offer significant gains, it is not clear how close our partitioning and rate-allocation approaches are to optimal. According to our simulations in §IV-E, we anticipate the additional cost of multiple forwarding trees to be small on average compared to using a single tree per transfer. This however remains to be demonstrated implementation-wise. Also, other fair sharing policies besides MMF should be explored and in general, domain or application specific policies may be used for higher performance.

II. ASSUMPTIONS AND PROBLEM STATEMENT

Similar to prior work on inter-datacenter networks [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF], [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF], [START_REF] Kandula | Calendaring for wide area networks[END_REF], [START_REF] Jin | Optimizing bulk transfers with software-defined optical wan[END_REF], [START_REF] Noormohammadpour | DCCast: Efficient Point to Multipoint Transfers Across Datacenters[END_REF], [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF], we assume a SD-WAN managed by a Traffic Engineering (TE) server which receives transfer requests from end-points, performs rate-allocations and manages the forwarding plane. Transfers arrive at the TE server in an online fashion and are serviced as they arrive. Requests are specified with four parameters of arrival time, source, set of receivers and size (volume in bytes). End-points apply rate-limiting to minimize congestion. We consider a slotted timeline to allow for flexible rate-allocation while limiting number of rate changes to allow time to converge to specified rates and minimize rate-allocation overhead [START_REF] Kandula | Calendaring for wide area networks[END_REF], [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF]. We focus on long running transfers that deliver large objects to many datacenters such as applications in [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF]. For such transfers, small delays are usually acceptable, including overhead of A directed edge from x to y G A directed inter-datacenter network graph T Some directed tree connecting a sender to its receivers

V G V G V G and V T V T V T Set of vertices of G and T E G E G E G and E T E T E T Set of
S R i Source datacenter of R i A R i Arrival time of R i V R i Original volume of R i in bytes V r R i Residual volume of R i , (V r R i = V R i at t = A R i ) D D D R i Set of destinations of R i n
Maximum subsets (partitions) allowed per receiver set

P P P j i Set of receivers of R i in partition j ∈ {1, . . . , n} q i Total bytes used to deliver O i to D D D R i T j i
Forwarding tree for partition j ∈ {1, . . . , n} of R i Le e's total outstanding load, i.e., Le = i,j e∈T

j i V r R i f j i (t) Transmission rate of R i on T j i at timeslot t γ j i (t) Whether R i is transmitted over T j i at timeslot t θ j i,e Whether edge e ∈ E G E G E G is on T j i ν i,j,v Whether v ∈ D D D R i is in P P P j i M M M j i {∇ ∇ ∇ | ∇ ∇ ∇ ⊂ V G V G V G , ∇ ∇ ∇ ∩ {P P P j i ∪ S R i } = ∅, (V G V G V G -∇ ∇ ∇) ∩ {P P P j i ∪ S R i } = ∅} E(∇ ∇ ∇) {e = (x, y) | x ∈ ∇ ∇ ∇, y ∈ (V G V G V G -∇ ∇ ∇)}
centralized scheduling and network configurations. To reduce configuration overhead (e.g. latency and control plane failures [START_REF] Liu | Traffic engineering with forward fault correction[END_REF]), we assume that a forwarding tree is not changed once configured on the forwarding plane. To reduce complexity we assume that end-points can accurately rate-limit data flows and that they quickly converge to required rates; that there are no packet losses due to congestion, corruption or errors; and that scheduling is done for a specific class of traffic meaning all requests have the same priority.

A. Problem Formulation

Earlier we showed that partitioning of receiver sets can improve completion times. However, to further improve completion times, partitioning should be done according to transfer properties, topology and network status. Optimal partitioning for minimization of completion times is an open problem and requires finding solution to a complex joint optimization model that takes into account forwarding tree selection and rateallocation, which we have formulated in this section. Table I provides the list of variables we have used.

We formulate the problem as an online optimization scenario. Assuming a set of requests R i , i ∈ {1 . . . I} already in the system, upon arrival of new request R I+1 , an optimization minimize i∈I I I j∈{1,...,n}

|P P P j i | t>A R I+1 (t -A R I+1 )γ j i (t) t >t (1 -γ j i (t )) + i∈I I I q i n |E G E G E G | i∈I I I V R i subject to
Calculate total bandwidth usage:

(1)

q i = e∈E G E G E G ( j∈{1,...,n} θ j i,e )V r R i ∀i
Demand satisfaction constraints:

(2)

t γ j i (t)f j i (t) = V r R i δ ∀i, j
Capacity constraints:

(3)

i∈I I I j∈{1,...,n} θ j i,e f j i (t) ≤ Ce ∀j, t, e
Steiner tree constraints [START_REF] Stanojevic | An exact algorithm for steiner tree problem on graphs[END_REF]:

(4) e∈E(∇ ∇ ∇) θ j i,e ≥ 1 ∀i, j, ∇ ∈ M M M j i
Basic range constraints: problem needs to be formulated and solved to find rateallocations, partitions and forwarding trees. Figure 3 shows the overall optimization problem. This model considers up to n ≥ 1 partitions per transfer. Demands of existing requests are updated to their residuals upon arrival of new requests.

(5) γ j i (t) = 0, f j i (t) = 0 ∀i, j, t < A R I+1 (6) f j i (t) ≥ 0 ∀i, j, t (7)
θ j i,e ∈ {0, 1} ∀i, j, e (8)
γ j i (t) ∈ {0, 1} ∀i, j, t (9)
ν i,j,v ∈ {0, 1} ∀i, j, v ∈ D D D R i (10) γ j i (t) = 0 ∀i, j, t < A R i
The objective is formulated in a hierarchical fashion giving higher priority to minimizing mean completion times and then reducing bandwidth usage. The purpose of γ j i (t) indicator variables is to calculate the mean times: the latest timeslot over which we have f j i (t) > 0 determines the completion time of partition j of request i. These completion times are then multiplied by partition size to create the total sum of completion times per receiver. Constraint 4 ascertains that there is a connected subgraph across sender and receivers per partition per request which is similar to constraints used to find minimal edge Steiner trees [START_REF] Stanojevic | An exact algorithm for steiner tree problem on graphs[END_REF]. Since our objective is an increasing function of bandwidth, these constraints eventually lead to minimal trees connecting any sender to its receivers while not increasing mean completion times (the second part of objective is necessary to ensure no stray edges).

B. Challenges

We focus on two objectives of first minimizing completion times of data transfers and minimizing total bandwidth usage. This is a complex optimization problem for a variety of reasons. First, breaking a receiver set to several partitions leads to exponential number of possibilities. Moreover, the optimization version of Steiner tree problem which aims to find minimal edge or minimal weight trees is a hard problem [START_REF] Stanojevic | An exact algorithm for steiner tree problem on graphs[END_REF]. Completion times of transfers then depend on how partitions are formed and which trees are used to connect partitions to senders. In addition, the scenario is naturally an online problem which means even if we were able to compute an optimal solution for a given set of transfers in a short amount of time, we still would not be able to compute a solution that is optimal over longer periods of time due to incomplete knowledge of future arrivals.

III. QUICKCAST

We present our heuristic approach in Algorithm 1 called QuickCast with the objective of reducing mean completion times of elastic P2MP inter-datacenter transfers. We first review concepts behind design of this heuristic, namely rateallocation, partitioning, forwarding tree selection and selective partitioning. Next, we discuss how Algorithm 1 realizes these concepts using two procedures one executed upon arrival of new transfers and the other per timeslot.

A. Rate-allocation

To compute rates per timeslot, we explore well-known scheduling policies: FCFS, SRPT and fair sharing. Although simple, FCFS can lead to increased mean times if large transfers block multiple edges by fully utilizing them. SRPT is known to offer optimal mean times over a single link but may lead to starvation of large transfers. QuickCast uses fair sharing based on MMF policy.

To understand effect of different scheduling policies, let us consider the following example. Figure 4 shows a scenario where multiple senders have initiated trees with multiple branches and they share links along the way to their receivers. SRPT gives a higher priority to the top transfer with size 10 and then to the next smallest transfer and so on. When the first transfer is being sent, all other transfers are blocked due to shared links. This occurs again when the next transfer begins. Scheduling according to FCFS leads to same result. In this example, mean completion times for both FCFS and SRPT is about 1.16× larger than MMF. In Section IV, we perform simulation experiments that confirm the outcome in this example. We find that trees grow larger and under high utilization, the benefit of using MMF over FCFS or SRPT becomes more significant due to increased contention. We also realize that tail times grow much faster for SRPT compared to both MMF and FCFS (since it also suffers from the starvation problem) while scheduling over forwarding trees with many receivers, and that increases SRPT's mean completion times.

B. Partitioning

There are two configuration parameters for grouping receivers into multiple partitions: partitioning criteria and number of partitions. In general, partitioning may lead to higher bandwidth usage. However, it may be the case that a small increase in bandwidth usage can considerably improve completion times. Efficient and effective partitioning to minimize completion times and bandwidth usage is a complex open problem. We discuss our approach in the following.

1) Partitioning Criteria:

We focus on minimizing extra bandwidth usage while breaking large forwarding trees via partitioning. Generally, one could select partitions according to current network conditions, such as distribution of load across edges. However, we notice that network conditions are continuously changing as current transfers finish and new transfers arrive. Minimizing bandwidth on the other hand appears as a globally desirable objective for partitioning and was hence chosen. To find partitions, QuickCast groups receivers according to proximity until we are left with desired number of groups each forming a partition. Distance between two receivers is computed as the number of hops on the shortest path between them. With this approach, a partition requires minimal number of edges to connect the nodes within. Reassigning any receiver to other partitions will increase the number of edges and thus consumed bandwidth.

2) Number of Partitions:

The right number of partitions per transfer depends on factors such as topology, number of receivers, forwarding trees of other transfers, source and destinations of a transfer, and overall network load. In the extreme case of N partitions, a P2MP transfer is broken into N unicast transfers which significantly increases bandwidth usage. Partitioning is most effective if forwarding trees assigned to partitions do not increase overall contention for network bandwidth, i.e., the number of overlapping edges across new trees is minimal. Therefore, increasing number of partitions to more than connectivity degree of datacenters may offer minor gains or even loss of performance (e.g., in case of Google B4 [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF], the minimum and maximum connectivity degrees are 2 and 4, respectively). From the practical aspect, number of partitions and hence forwarding trees determines the number of Group Table rules that need to be setup in network switches. Therefore, we focus on partitioning receivers into up to 2 groups each assigned an independent forwarding tree. Exploration of effects of more partitions is left for future work.

C. Forwarding Tree Selection

After computing two partitions, QuickCast assigns an independent forwarding tree per partition using tree selection approach presented in [START_REF] Noormohammadpour | DCCast: Efficient Point to Multipoint Transfers Across Datacenters[END_REF] which was shown to provide high bandwidth savings and improved completion times. It operates by giving a weight of W e = (L e + V R ) (see Table I for definition of variables) and then selecting the minimum weight forwarding tree. This technique allows load balancing of P2MP data transfers over existing trees according to total bandwidth scheduled on the edges. It also takes into account transfer volumes while selecting trees. Particularly, larger transfers are most likely assigned to smaller trees to minimize bandwidth usage while smaller transfers are assigned to least loaded trees (regardless of tree size). This approach becomes more effective when a small number of transfers are orders of magnitude larger than median [START_REF] Roy | Inside the social network's (datacenter) network[END_REF], as number of larger forwarding trees is usually significantly larger than smaller trees on any graph.

D. Selective Partitioning

Partitioning is beneficial only if it decreases or minimally increases bandwidth usage and contention over resources which necessitates selectively partitioning the receivers. When we choose the two partitions by grouping receivers and after selecting a forwarding tree for every group, QuickCast calculates the total weight of each forwarding tree by summing up weights of their edges. We then compare sum of these two weights with no partitioning case where a single tree was used. If the total weight of two smaller trees is less than some partitioning factor (shown as p f ) of the single tree case, we accept to use two trees. If p f is close to 1.0, partitioning occurs only if it incurs minimal extra weight, i.e., (p f -1) times weight of the single forwarding tree that would have been chosen if we applied no partitioning. With this approach, we most likely avoid selection of subsequent trees that are either much larger or much more loaded than the initial tree in no partitioning case. Generally, an effective p f is a function of traffic distribution and topology. According to our experiments with several traffic distributions and topologies, choosing it in the range of 1.0 ≤ p f ≤ 1.1 offers the best completion times and minimal bandwidth usage.

E. QuickCast Algorithm

A TE server is responsible for managing elastic transfers over inter-datacenter network. Each partition of a transfer is managed independently of other partitions. We refer to a transfer partition as active if it has not been completed yet. TE server keeps a list of active transfer partitions and tracks them at every timeslot. A TE server running QuickCast algorithm uses two procedures as shown in Algorithm 1.

1) Submit(R, n, p f ): This procedure is executed upon arrival of a new P2MP transfer R. It performs partitioning and forwarding tree selection for the new transfer given its volume, source and destinations. We consider the general case where we may have up to n partitions per transfer. First, we compute edge weights based on current traffic matrix and volume of new transfer. We then build the agglomerative hierarchy of receivers using average linkage and considering proximity as clustering metric. Agglomerative clustering is a bottom up approach where at every level the two closest clusters are merged forming one cluster. The distance of any two clusters is computed using average linkage which is the average over pairwise distances of nodes in the two clusters. The distance between every pair of receivers is the number of edges on the shortest path from one to the other. It should be noted that although our networks are directed, all edges are considered to be bidirectional and so the distance in either direction between any two nodes should be the same. When the hierarchy is ready, we start from the level where there are n clusters (or at the bottom if total number of receivers is less than or equal to n) and compute the total weight of n forwarding trees (minimum weight Steiner trees) to these clusters. We move forward with this partitioning if the total weight is less than p f times weight of the forwarding tree that would have been selected if we grouped all receivers into one partition. Otherwise, the same process is repeated while moving up one level in the clustering hierarchy (one less cluster). If we accept a partitioning, this procedure first assigns a forwarding tree to every partition while continuously updating edge weights. It then returns the partitions and their forwarding trees.

2) DispatchRates(): This procedure is executed at the beginning of every timeslot. It calculates rates per active transfer partition and according to MMF rate-allocation policy. New transfers arriving somewhere within a timeslot are allocated rates starting next timeslot. To calculate residual demands needed for rate calculations, senders report back the actual volume of data delivered during past timeslot per partition. This allows QuickCast to cope with inaccurate rate-limiting and packet losses which may prevent a transfer from fully utilizing its allotted share of bandwidth.

IV. EVALUATIONS

We considered various topologies and transfer size distributions as in Tables II andIII. For simplicity, we considered a uniform capacity of 1.0 for all edges, accurate ratelimiting at end-points, no dropped packets due to congestion or corruption, and no link failures. Transfer arrival followed a Poisson distribution with rate of λ. For all simulations, we considered a partitioning factor of p f = 1.1 and timeslot width of δ = 1.0. Unless otherwise stated, we assumed a fixed λ = 1.0. Also, for all traffic distributions, we considered an average demand equal to volume of 20 full timeslots per transfer. For heavy-tailed distribution that is based on Pareto distribution, we used a minimum transfer size equal to that of 2 full timeslots. Finally, to prevent generation of intractably CAPe ← CAPe -RATE P , ∀e ∈ T P ; return RATE P , ∀P ∈ P P P large transfers, we limited maximum transfer volume to that of 2000 full timeslots. We focus on scenarios with no link failures to evaluate gains.

Algorithm 1: QuickCast Submit (R, n, p f ) Input: R(V R , S R , D D D R ), n (= 2 in this paper), p f , G, Le for ∀e ∈ E G E G E G (

A. Comparison of Scheduling Policies over Forwarding Trees

We first compare the performance of three well-known scheduling policies of FCFS, SRPT and fair sharing (based on MMF). We used the weight assignment in [START_REF] Noormohammadpour | DCCast: Efficient Point to Multipoint Transfers Across Datacenters[END_REF] for forwarding tree selection and considered Random topology in Table II. We considered both light-tailed and heavy-tailed distributions. All policies used almost identical amount of bandwidth (not

Name Description

Random

Randomly generated and strongly connected with 50 nodes and 150 edges. Each node has a minimum connectivity of two. GScale [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF] Connects Google datacenters across the globe with 12 nodes and 19 links. Cogent [START_REF]The Internet Topology Zoo[END_REF] A large backbone and transit network that spans across USA and Europe with 197 nodes and 243 links.

TABLE III TRANSFER SIZE DISTRIBUTIONS USED IN EVALUATION

Name Description

Light-tailed According to Exponential distribution.

Heavy-tailed

According to Pareto distribution. Facebook Cache-Follower [START_REF] Roy | Inside the social network's (datacenter) network[END_REF] Generated across Facebook inter-datacenter networks running cache applications. Facebook Hadoop [START_REF] Roy | Inside the social network's (datacenter) network[END_REF] Generated across Facebook inter-datacenter networks running geo-distributed analytics. shown). Under light load, we obtained results similar to scheduling traffic on a single link where SRPT performs better than fair sharing (not shown). Figure 5 shows the results of our experiment under heavy load. When the number of receivers is small, SRPT is the best policy to minimize mean times. However, as we increase the number of receivers (larger trees), fair sharing offers better mean and tail times. This simply occurs because the contention due to overlapping trees caused by prioritizing transfers over one another (either according to residual size for SRPT or arrival order for FCFS) increases as more transfers are submitted or as transfers grow in size.

B. Bandwidth usage of partitioning techniques

We considered three partitioning techniques and measured the average bandwidth usage over multiple runs and many timeslots. We used the topologies in Table II

Scheme Details

QuickCast Algorithm 1 (Selective Partitioning).

QuickCast(NP)

QuickCast with no partitioning applied. QuickCast(TWO)

QuickCast with two partitions always.

patterns of Table III. Figure 6 shows the results. We calculated the lower bound by considering a single minimal edge Steiner tree per transfer. Other schemes considered are: Random(Uniform Dist) breaks each set of receivers into two partitions by randomly assigning each receiver to one of the two partitions with equal probability, Agg(proximity between receivers) clusters receivers according to closeness to each other, and Agg(closeness to source) clusters receivers according to their distance from source (receivers closer to source are bundled together). As can be seen, Agg(proximity between receivers), which is used by QuickCast, provides the least bandwidth overhead (up to 17% to lower bound). In general, breaking receivers into subsets that are attached to a sender with minimal bandwidth usage is an open problem.

C. QuickCast with different partitioning approaches

We compare three partitioning approaches shown in Table IV. We considered receiver sets of 5 and 10 with both lighttailed and heavy-tailed distributions. We show both mean (top row) and tail (bottom row) completion times in the form of a CDF in Figure 7. As expected, when there is no partitioning, all receivers complete at the same time (vertical line in CDF). When partitioning is always applied, completion times can jump far beyond the no partitioning case due to unnecessary creation of additional bottleneck links. The benefit of QuickCast is that it applies partitioning selectively. The amount of benefit obtained is a function of partitioning factor p f (which for the topologies and traffic patterns considered here was found to be most effective between 1.0 and 1.1 according to our experiments, we used 1.1). With QuickCast, the fastest receiver can complete up to 41% faster than the slowest receiver and even the slowest receiver completes up to 10% faster than when no partitioning is applied.

D. QuickCast vs. DCCast

We now compare QuickCast with DCCast using real topologies and inter-datacenter transfer size distributions, namely Cogent(Cache-Follower) and GScale(Hadoop) shown in Tables II andIII. Figure 8 shows the results. We considered 10 receivers per P2MP transfer. In all cases, QuickCast uses up to 4% more bandwidth. For lightly loaded scenarios where λ = 0.01, QuickCast performs up to 78% better in mean times, but about 35% worse in tail times. The loss in tail times is a result of rate-allocation policy: FCFS performs better in tail times compared to fair sharing under light loads where contention due to overlapping trees is negligible (similar to single link case when all transfers compete for one resource). For heavily loaded scenarios where λ = 1, network contention due to overlapping trees is considerable and therefore QuickCast has been able to reduce mean times by about 10× and tail times by about 57%. This performance gap continues to increase in favor of QuickCast as offered load grows further. In general, operators aim to maximize network utilization over dedicated WANs [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF], [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF] which could lead to heavily loaded time periods for example due to bursty transfer arrivals.

In a different experiment, we studied the effect of number of replicas of data objects on performance of DCCast and QuickCast as shown in Figure 9 (please notice the difference in vertical scale of different charts). Bandwidth usage of both schemes were almost identical (QuickCast used less than 4% extra bandwidth in the worst case). We considered two operating modes of lightly to moderately loaded (λ = 0.01) and moderately to heavily loaded (λ = 0.1). QuickCast offers most benefit when number of copies grows. When the number of copies is small, breaking receivers into multiple sets may provide limited benefit or even degrade performance as resulting partitions will be too small. This is why mean and tail times degrade by up to 5% and 40% across both topologies and traffic patterns when network is lightly loaded, respectively. Under increasing load and with more copies, it can be seen that QuickCast can reduce mean times significantly, i.e., by as much as 6× for Cogent(Cache-Follower) and as much as 16× for GScale(Hadoop), respectively. The sudden increase in tail times for GScale topology is because this network has only 12 nodes which means partitioning while making 10 copies may most likely lead to overlapping edges across partitioned trees. This can be addressed by reducing p f to minimize unnecessary partitioning.

E. Complexity 1) Group Table Entries:

We performed simulations over 2000 timeslots with λ = 1.0 (heavily loaded scenario) and number of copies set to 10. With GScale(Hadoop) setting, the maximum number of required Group Table entries was 455 and the average of maximum rules for all nodes observed over all timeslots was 166. With Cogent(Cache-Follower) setting, which is more than 10 times larger than GScale, we observed a maximum of 165 and an average of 9 Group Table entries for the maximum observed by all nodes over all timeslots. We considered the highly loaded case as it leads to higher number of concurrent forwarding trees. Currently, most switches that support Group Tables offer a maximum of 512 or 1024 entries in total. In this experiment, a maximum of one Group Table entry per transfer per node was enough as we considered switches that support up to 32 action buckets per entry [START_REF]Understanding how the openflow group action works[END_REF] which is more then total number of receivers we chose per transfer. In general, we may need more than one entry per node per transfer or we may have to limit the branching factor of selected forwarding trees, for example when Group Table entries support up to 8 action buckets [START_REF]HP 5130 EI Switch Series OpenFlow Configuration Guide[END_REF].

2) Computational Complexity: We computed run-time on a machine with a Core-i7 6700 CPU and 24GBs of memory using JRE 8. We used the same transfer size properties mentioned at the beginning of this section. With GScale(Hadoop) setting and λ = 0.01, run-time of procedure Submit increased from 1.44ms to 2.37ms on average while increasing copies from 2 to 10. With the same settings, runtime of procedure DispatchRates stayed below 2µs for varying number of copies. Next, we increased both load and network size by switching to Cogent(Cache-Follower) setting and λ = 1.0. This time, run-time of procedure Submit increased from 3.5ms to 35ms and procedure DispatchRates increased from 0.75ms to 1.6ms on average while increasing copies from 2 to 10. Although these run-times are significantly smaller than timeslot widths used in prior works which are in the range of minutes [START_REF] Jin | Optimizing bulk transfers with software-defined optical wan[END_REF], [START_REF] Zhang | Guaranteeing deadlines for interdatacenter transfers[END_REF], more efficient implementation of proposed techniques may result in even further reduction of run-time. Finally, with our implementation, memory usage of QuickCast algorithm is in the order of 100's of megabytes on average.

V. DISCUSSION

1) Handling rate-limiting inaccuracies: Rate-limiting is generally not very accurate, especially if done in software. To deal with inaccuracies and errors, every sender should report back to the TE server at the end of every timeslot and specify how much traffic it was able to deliver. TE server will deduct these from the residual demand of requests. Rate-allocation continues until a request is completely satisfied.

2) Receiver feedback to sender: One can use a point to point scheme for receiver feedback by installing proper forwarding rules. Over wired networks and with rate-limiting, dropped packets due to congestion and corruptions are expected to be low. Therefore, Negative Acknowledgement (NAK) can be used to minimize receiver feedback size. 3) Handling network capacity loss: Link/switch failures may occur in a real setting. In case of a failure, the TE server can be notified by a network element that detects the failure. The TE server can then exclude the faulty link/switch from topology and re-allocate all requests routed on that link using their residual demands. After new rates are allocated and forwarding trees recomputed, forwarding plane can be updated and new rates can be given to end-points for rate-limiting. 4) TE server failure: Another failure scenario is when TE server stops working. It is helpful if end-points are equipped with some distributed congestion control mechanism. In case TE server fails, end-points can roll back to the distributed mode and determine their rates according to network feedback.

VI. CONCLUSIONS AND FUTURE WORK

In this paper, we presented QuickCast which reduces mean completion times of P2MP transfers across datacenters. We showed that by breaking receiver sets of P2MP transfers with many receivers into smaller subsets and using a separate tree per subset, we can reduce completion times. We proposed partitioning according to proximity as an effective approach for finding such receiver subsets, and showed that partitioning need be applied to transfers selectively. To do so, we proposed a partitioning factor that can be tuned according to topology and traffic distribution. Further investigation is required on finding metrics to selectively apply partitioning per transfer. In addition, we performed experiments with well-known rate-allocation policies and realized that Max-Min Fairness provides much lower completion times compared to both SRPT and FCFS over large forwarding trees. As a future direction, one may drive a more effective joint partitioning, rate-allocation and forwarding tree selection algorithm by approximating a solution to optimization model we proposed.

Fig. 3 .

 3 Fig. 3. Online optimization model, variables defined in Table I

RECEIVERSFig. 4 .

 4 Fig. 4. Fair sharing can offer better mean times compared to both SRPT and FCFS while scheduling over forwarding trees, all links have capacity of 1

  Variables defined in Table I) Output: Pairs of (Partition, Forwarding Tree) ∀α, β ∈ D D D R , α = β, DIST α,β ← number of edges on the shortest path from α to β; To every edge e ∈ E G E G E G , assign weight We = (Le + V R ); Find the minimum weight Steiner tree T R that connects S R ∪ D D D R and its total weight W T R ; for k = n to k = 2 by -1 do Agglomeratively cluster D D D

Fig. 5 .

 5 Fig. 5. Performance of three well-known scheduling policies under heavy load (forwarding tree selection according to DCCast)

Fig. 7 .

 7 Fig. 7. Comparison of partitioning approaches in TableIV

Fig. 8 .

 8 Fig. 8. Comparison of completion times of and bandwidth used by QuickCast vs. DCCast (Normalized by minimum in each category)

Fig. 9 .

 9 Fig. 9. Comparison of completion times of QuickCast and DCCast (Normalized by minimum in each category) by number of object copies

  COUNTe ← COUNTe -1, ∀e ∈ T P ;

			R using average linkage and
		distance metric DIST calculated in previous line until only
		k clusters left forming P P P i R , i ∈ {1, . . . , k};
	foreach i ∈ {1, . . . , k} do
		, weight of minimum weight Steiner tree that connects S R ∪ P P P i Find W T P P P i R R ;
	if	i∈{1,...,k} W T P P P i R	≤ p f × W T R then
		foreach i ∈ {1, . . . , k} do
		Find the minimum weight Steiner tree T P P P i R connects S R ∪ P P P i R ;	that
		R Le ← Le + V R , ∀e ∈ T P P P i	;
		Update We = (Le + V R ) for all e ∈ E G E G E G ;
		return P P P i R as well as T P P P i
			V r P δ );
	P P P ← P P P -{P };

R

, ∀i ∈ {1, . . . , k};

Le ← Le + V R , ∀e ∈ T R ; return D D D

R and T R ; DispatchRates () Input: Set of active request partitions P P P, their current residual demands and forwarding trees V r P , T P , ∀P ∈ P P P, and δ Output: Rate per active request per partition for next timeslot COUNTe ← number of forwarding trees T P , ∀P ∈ P P P sharing edge e, ∀e ∈ E G E G E G ; P P P ← P P P and CAPe ← 1, ∀e ∈ E G E G E G ; while |P P P | > 0 do foreach P ∈ P P P do SHARE P ← min e∈T P ( CAPe COUNTe ); P ← a partition P with minimum SHARE P value; RATE P ← min(SHARE P ,

TABLE IV EVALUATION

 IV OF PARTITIONING TECHNIQUES FOR P2MP TRANSFERS


Samir Adly
email: samir.adly@unilim.frmichel.thera@unilim.fr

Daniel Goeleven
email: daniel.goeleven@univ-reunion.fr

Michel Th Éra

Periodic Solutions of Evolution Variational Inequalities -a Method of Guiding Functions * * *

Keywords: Variational inequality, Differential inclusion, Topological degree, Guiding function, Periodic solution 2000 MR Subject Classification 49J40, 49J20, 35K85

This paper focuses on a part of the presentation given by the third author at the Shanghai Forum on Industrial and Applied Mathematics (Shanghai 2006). It is related to the existence of a periodic solution of evolution variational inequalities. The approach is based on the method of guiding functions.

Introduction

Variational inequalities provide a broad unifying setting for the study of optimization and equilibrium problems which have their origin in various areas such as economics and engineering. The theory of variational inequalities started around 40 years ago in two different areas: partial differential systems with G. Stampacchia and his collaborators and mathematical programming with R. Cottle.

Infinite-dimensional variational inequalities were developed for studying free boundary problems defined by non-linear partial differential equations arising mostly in unilateral mechanics.

They have numerous applications as it is well-known. Let us mention for instance the books by Baiocchi and Capello [START_REF] Baiocchi | Variational and Quasi-variational Inequalities: Applications to Free Boundary Problems[END_REF] and Kinderleherer and Stampacchia [START_REF] Kinderlehrer | An Introduction to Variational Inequalities and Their Applications[END_REF] for the abstract theory and by Glowinski, Lions and Trémolière [START_REF] Glowinski | Analyse numérique des inéquations variationnelles, Tome 1: Théorie générale premières applications[END_REF] for the numerical analysis. The reader is also referred to the recent book by Giannessi [START_REF] Giannessi | Constrained Optimization and Image Space Analysis[END_REF] and the references therein. The well-known generalization by Stampacchia of the Lax-Milgram lemma for coercive bilinear forms to convex sets, published in Comptes Rendus de l'Académie des Sciences in 1964 (see [START_REF] Stampacchia | Formes bilinéaires coercitives sur les ensembles convexes[END_REF]), is the starting point of the theory of infinite-variational inequalities. This famous result was extended some years later by Lions and Stampacchia [START_REF] Lions | Inéquation variationnelles non coercives[END_REF] to not necessarily coercive bilinear forms and has an important application in the theory of elliptic and parabolic operators and in problems with unilateral constraints (Signorini's problem for example). We would like to mention the abstract regularity theorem for variational inequalities associated to nonlinear monotone operators obtained by Brezis and Stampacchia [START_REF] Brezis | Sur la régularité de la solution d'inéquations elliptiques[END_REF] which applies to the case of a convex set defined via an obstacle from above and an obstacle from below.

The theory of finite-dimensional variational inequalities is related to finite-dimensional optimization and in particular to nonlinear programming. It was developed independently by the mathematical programming community first by Cottle [START_REF] Cottle | Nonlinear Programs with Positively Bounded Jacobians[END_REF] and later by several authors. The reader could find a nice survey on finite-dimensional variational inequalities and the references therein in the book by Facchinei and Pang [START_REF] Facchinei | Finite Dimensional Variational Inequalities and Complementarity Problems[END_REF]. We would like to mention particularly the work by Robinson [START_REF] Robinson | Generalized equations and their solutions, part I: Basic theory[END_REF] in connection with generalised equations, who developed an original framework to obtain qualitative and numerical results for variational inequalities in analogy with classical Newton-type methods.

This note focuses on a specific part of a general talk given at the Shanghai Forum on Applied and Industrial Mathematics in May 2006 and is related to a previous work of the same authors (see [START_REF] Adly | A continuation method for a class of periodic evolution variational inequalities[END_REF]). It concerns the existence of a T -periodic solution u ∈ C 0 ([0, T ]; R n ) of the evolution variational inequality:

du dt (t) + F (u(t)) -f (t) ∈ -∂ϕ(u(t)), a.e. t ∈ [0, T ]. (1.1)
In this problem the solution u satifies

du dt ∈ L ∞ (0, T ; R n ), (1.2)
u is right-differentiable on [0, T ), (1.3)
u(0) = u(T ). (1.4)
We suppose that F : R n → R n is a continuous map, ϕ : R n → R is a convex function,

f ∈ C 0 ([0, +∞[ ; R n ) is such that df dt ∈ L 1 loc (0, +∞; R n )
and T > 0 is a prescribed period and as it will be recalled later, ∂ϕ is the convex subdifferential of ϕ.

The paper is organized as follows. In Section 2, we recall some materials. A particular attention is given to the Brouwer topological degree, since it will play a central role in the proof of the results. In Section 3, we recall the existence and uniqueness result by Schowalter [START_REF] Showalter | Monotone Operators in Banach Spaces and Nonlinear Partial Differential Equations[END_REF], and we see how the problem of the existence of a periodic solution to the evolution problem (1.1) is equivalent to the existence of a fixed point of the Poincaré operator associated to the problem under consideration. Finally, Section 5 is devoted to the main theorem (Theorem 4.1) which proves the existence of a periodic solution, using the method of guiding functions.

2 Brouwer Topological Degree and the Resolvent Operator J ϕ λ It is well-known that the degree theory is a powerful tool for the study of the existence of a solution to a nonlinear equation f (x) = 0, where f is a continuous function defined on the closure Ω of a bounded subset Ω of R n , with values in R n and such that 0 is outside the image of the boundary ∂Ω of Ω.

In the sequel, the scalar product on R n is denoted as usual by • , • and • is the associated norm. For r > 0, we note B r := {x ∈ R n : x < r}, B r = {x ∈ R n : x ≤ r} and

∂B r := {x ∈ R n : x = r} = B r \ B r .
If f : B r → R n is continuous and 0 ∈ f (∂B r ), then the Brouwer topological degree of f with respect to B r and 0 is well-defined (see, e.g., [START_REF] Lloyd | Degree Theory[END_REF][START_REF] Mawhin | Continuation theorems and periodic solutions of ordinary differential equations, Topological Methods in Differential Equations and Inclusions[END_REF]) and is denoted by deg(f, B r , 0).

Let us now recall some properties of the topological degree that we will use later.

Proposition 2.1 (1) If 0 ∈ f (∂B r ) and deg(f, B r , 0) = 0, then there exists x ∈ B r such that f (x) = 0.

(

) Let ϕ : [0, 1] × B r → R n , (λ, x) → ϕ(λ, x), be continuous such that, for each λ ∈ [0, 1], one has 0 ∈ ϕ(λ, ∂B r ). Then the map λ → deg(ϕ(λ, • ), B r , 0) is constant on [0, 1]. ( 2
) 3
Let us denote by id R n the identity mapping on R n . We have

deg(id R n , B r , 0) = 1. (4) If 0 ∈ f (∂B r ) and α > 0, then deg(αf, B r , 0) = deg(f, B r , 0) and deg(-αf, B r , 0) = (-1) n deg(f, B r , 0). ( 5
) If 0 ∈ f (∂B r ) and f is odd on B r (i.e., f (-x) = -f (x), ∀ x ∈ B r ), then deg(f, B r , 0) is odd. (6) Let f (x) = Ax -b, with A ∈ R n×n being a nonsingular matrix and b ∈ R n . Then deg(f, A -1 b + B r , 0) = sgn(det A) = ±1.
Let V ∈ C 1 (R n ; R) and suppose that there exists r 0 > 0 such that, for every r ≥ r 0 , 0 ∈ ∇V (∂B r ). Then deg(∇V, B r , 0) is constant for r ≥ r 0 and one defines the index of V at

infinity "ind(V, ∞)" by ind(V, ∞) := deg(∇V, B r , 0), ∀ r ≥ r 0 .
Let us now recall some basic properties on convex functions defined on R n . Given a convex function ϕ : R n → R, it is well-known (see [START_REF] Rockafellar | Convex Analysis[END_REF]) that

(a) ϕ is continuous, (b) For all x ∈ R n , the directional derivative of ϕ at x ∈ R n in the direction ξ ∈ R n , i.e., ϕ (x; ξ) = lim α↓0 ϕ(x + αξ) -ϕ(x) α ,
exists and is finite for every ξ ∈ R n (see, e.g., [10, p. 164]), (c) For all x ∈ R n , the convex subdifferential of ϕ at x is a nonempty compact and convex subset of R n and is defined by

∂ϕ(x) = {w ∈ R n : ϕ(v) -ϕ(x) ≥ w, v -u , ∀ v ∈ R n }, and w ∈ ∂ϕ(x) ⇐⇒ w, ξ ≤ ϕ (x; ξ), ∀ ξ ∈ R n . (2.1)
Since the subdifferetial operator is a maximal monotone operator (see for instance Brezis for the Hilbert setting and Rockafellar for the reflexive Banach setting), for each λ > 0 the resolvent operator J ϕ λ : R n → R n defined by

y → J ϕ λ (y) = (I + λ∂ϕ) -1 (y)
is well-defined and is a contraction on R n , i.e.,

J ϕ λ (x) -J ϕ λ (y) ≤ x -y , ∀ x, y ∈ R n , ∀ λ > 0.
Hence J ϕ λ is continuous on R n . For simplicity, we note P ϕ instead of J ϕ 1 when the parameter λ = 1.

The Poincaré Operator

Let us first recall some general existence and uniqueness result (see, e.g., [START_REF] Showalter | Monotone Operators in Banach Spaces and Nonlinear Partial Differential Equations[END_REF]). Theorem 3.1 Let ϕ : R n → R be a convex function. Let F : R n → R n be a continuous operator such that, for some ω ∈ R, F + ωI is monotone, i.e.,

F (x) -F (y), x -y ≥ -ω x -y 2 , ∀ x, y ∈ R n . Suppose that f : [0, +∞) → R n satisfies f ∈ C 0 ([0, +∞); R n ), df dt ∈ L 1 loc (0, +∞; R n ).
Let u 0 ∈ R n and 0 < T < +∞ be given. There exists a unique u

∈ C 0 ([0, T ]; R n ) such that du dt ∈ L ∞ (0, T ; R n ), (3.1)
u is right-differentiable on [0, T ), (3.2)

u(0) = u 0 , (3.3) du dt (t) + F (u(t)) -f (t) ∈ -∂ϕ(u(t)), a.e. t ∈ [0, T ]. (3.4) Remark 3.1 Suppose that F : R n → R n is of the type F (x) = Ax + Ψ (x) + F 1 (x), ∀ x ∈ R n , where A ∈ R n×n is a real matrix, Ψ ∈ C 1 (R n ; R) is convex and F 1 is Lipschitz continuous, i.e., F 1 (x) -F 1 (y) ≤ k x -y , ∀ x, y ∈ R n
for some constant k > 0. Then F is continuous and F + ωI is monotone provided that

ω ≥ sup x =1 -Ax, x + k.
We note that if F is k-Lipschitz, then F + kI is monotone.

Remark 3.2 Let u : [0, T ] → R be the unique solution of (3.1)-(3.4). Then using (3.4) and (2.1), we have

du dt (t) + F (u(t)) -f (t), ξ + ϕ (u(t); ξ) ≥ 0, ∀ ξ ∈ R n , a.e. t ∈ [0, T ].
Let T > 0 be given. Theorem 3.1 enables us to define the one parameter family {S(t) : 0 ≤ t ≤ T } of operators from R n into R n as follows: where 0 ≤ α < 1. Then

∀ y ∈ R n , S(t)y = u(t), (3.5
S(t)z -S(t)y 2 ≤ z -y 2 e 2ωt , ∀ t ∈ [0, T ].
The conclusion follows.

Let us now consider the Poincaré operator S(T ) : R n → R n ; y → S(T )y. Theorem 3.2 ensures that S(T ) is Lipschitz continuous, i.e., S(T )y -S(T )z ≤ e ωT yz , ∀ y, z ∈ R n . Remark 3.3 ( i ) Note that if F is continuous and monotone, then Theorem 3.2 holds with ω = 0. In this case, the Poincaré operator S(T ) is nonexpansive, i.e.,

S(T )y -S(T

)z ≤ y -z , ∀ y, z ∈ R n .
(ii) If F is continuous and strongly monotone, i.e., there exists α > 0 such that

F (x) -F (y), x -y ≥ α x -y 2 , ∀ x, y ∈ R n ,

Periodic Solutions

Definition 4.1 Let Ω ⊂ R n be a given subset of R n . We say that V ∈ C 1 (R n ; R) is a guiding function for (1.2) on Ω provided that F (x) -f (t), ∇V (x) + ϕ (x; ∇V (x)) < 0, ∀ x ∈ Ω, t ∈ [0, T ]. (4.1)
Remark 4.1 ( i ) Suppose that there exists a guiding function V ∈ C 1 (R n ; R) for (1.2) on ∂B r (r > 0), i.e.,

F (x) -f (t), ∇V (x) + ϕ (x; ∇V (x)) < 0, ∀ x ∈ ∂B r , t ∈ [0, T ].
Then for any τ ∈ [0, T ], we have

deg(∇V, B r , 0) = (-1) n deg(id R n -P ϕ (id R n -F + f (τ )), B r , 0). ( 4.2)
(ii) Suppose that there exists a guiding function

V ∈ C 1 (R n ; R) for (1.2) on Ω R := {x ∈ R n : x ≥ R} = R n \ B R , R > 0.
Then for r ≥ R and any τ ∈ [0, T ], we have

ind(V, ∞) = (-1) n deg(id R n -P ϕ (id R n -F + f (τ )), B r , 0).
Proposition 4.1 Suppose that there exists R > 0 such that

F (x) -f (t), ∇V (x) < 0, ∀ x ∈ R n , x ≥ R, t ∈ [0, T ]. (4.3)
Then for r ≥ R and any τ ∈ [0, T ], we have

ind(V, ∞) = deg(f (τ ) -F, B r , 0).
Proof Let r ≥ R be given and let h :

[0, 1] × B r → R n , (λ, y) → h(λ, y) := λ∇V (y) + (1 -λ)(f (0) -F (y)). We claim that h(λ, y) = 0, ∀ y ∈ ∂B r , λ ∈ [0, 1]. Indeed, suppose by contradiction that λ∇V (y) + (1 -λ)(f (τ ) -F (y)) = 0 for some y ∈ ∂B r and λ ∈ [0, 1]. Then λ ∇V (y), f(τ ) -F (y) = -(1 -λ) f (τ ) -F (y) 2 .
(4.4)

Obviously λ = 0. Indeed, if λ = 0, we obtain f (τ )-F (y) = 0, a contradiction to condition (4.3) since y ∈ ∂B r and r ≥ R. Thus (4.4) yields ∇V (y), f(τ ) -F (y) < 0 which also contradicts

(4.3). Thus deg(∇V, B r , 0) = deg(h(1, • ), B r , 0) = deg(h(0, • ), B r , 0) = deg(f (τ ) -F, B r , 0).
Theorem 4.1 We make the assumptions that f ∈ C 0 ([0, +∞); R n ) and df dt ∈ L 1 loc (0, +∞; R n ). Let ϕ : R n → R be a convex function. Let F : R n → R n be a mapping such that F + ωI is monotone for some ω ∈ R. Suppose that there exist constants C 1 ≥ 0 and C 2 ≥ 0 such that

F (x), x + ϕ (x; x) ≤ C 1 x 2 + C 2 x , ∀ x ∈ R n . (4.5)
Let T > 0 be given. Assume that there exists a (guiding

) function V ∈ C 1 (R n ; R) and R > 0 such that F (x) -f (t), ∇V (x) + ϕ (x; ∇V (x)) < 0, ∀ x ∈ R n , x ≥ R, t ∈ [0, T ]. (4.6)
Then there exists at least one

u ∈ C 0 ([0, T ]; R n ) such that du dt ∈ L ∞ (0, T ; R n ), u(0) = u(T ), (4.7) du dt (t) + F (u(t)) -f (t) ∈ -∂ϕ(u(t)), a.e. t ∈ [0, T ]. (4.8)
Proof We will prove that there exists r 0 > R such that for any τ ∈ [0, T ] we have

deg(id R n -S(T ), B r , 0) = deg(id R n -P ϕ (id R n -F + f (τ )), B r , 0) = (-1) n ind(V, ∞), ∀ r ≥ r 0 .
Let us first remark that without loss of generality, we may assume C 1 > 0. We set

r 0 := R e C1T + C 2 C 1 (e C1T -1) + T 0 f (s) e C1s ds.
Step 1 We claim that if y ∈ R n , y = r with r ≥ r 0 , then

S(t)y ≥ R, ∀ t ∈ [0, T ].
Suppose by contradiction that there exists t * ∈ [0, T ] such that S(t * )y < R. We know that

u( • ) ≡ S( • )y satisfies du dt (t) + F (u(t)) -f (t) ∈ -∂ϕ(u(t)), a.e. t ∈ [0, T ], (4.9)
and thus

du dt (t * -t) + F (u(t * -t)) -f (t * -t) ∈ -∂ϕ(u(t * -t)), a.e. t ∈ [0, t * ]. (4.10)
Setting

Y (t) = u(t * -t), t ∈ [0, t * ],
we derive

- dY dt (t) + F (Y (t)) -f (t * -t) ∈ -∂ϕ(Y (t)), a.e. t ∈ [0, t * ]. (4.11)
Thus

dY dt (t), ξ ≤ F (Y (t)) -f (t * -t), ξ + ϕ (Y (t); ξ), ∀ ξ ∈ R n , a.e. t ∈ [0, t * ].
For ξ = Y (t), we have Hence, y < r 0 , a contradiction.

dY dt (t), Y (t) ≤ F (Y (t)) -f (t * -t), Y (t) + ϕ (Y (t); Y (t)) ≤ C 1 Y (t) 2 + C 2 Y (t) + f (t * -t) Y (t) , a.e. t ∈ [0, t * ]. Thus 1 2 d dt Y (t) 2 ≤ C 1 Y (t) 2 + (C 2 + f (t * -t) ) Y (t) , a.e. t ∈ [0, t * ]. Using Lemma 3.1 with α := 1 2 , w( • ) := Y ( • ) 2 , a( • ) := C 1 and b( • ) := C 2 + f (t * -• ) , we obtain Y (t) ≤ Y (0) e C1t + t 0 C 2 e C1(t-s) ds + t 0 f (t * -s) e C1(t-s) ds, ∀ t ∈ [0, t * ].
Step 2 Let r ≥ r 0 be given. We claim that there exist ε > 0 and T * ∈ (0, T ] such that

F (x) -f (t), ∇V (y) + ϕ (x; ∇V (y)) < 0, ∀ x ∈ R n , y ∈ R n , y = r, x -y ≤ ε, t ∈ [0, T * ].
Indeed, recalling that the mapping (z, ξ) → ϕ (z; ξ) is upper semicontinuous (see, e.g., [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]), we note that the mapping (t, x, y) → F (x)f (t), ∇V (y) + ϕ (x; ∇V (y)) is upper semicontinuous on [0, T ] × R n × R n and if y ∈ R n and y = r ≥ r 0 ≥ R, then (by condition (4.6))

F (y)f (0), ∇V (y) + ϕ (y; ∇V (y)) < 0.

Thus, for t > 0 close to 0, let us say t ≤ T * ; and x close to y, let us say xy ≤ ε, ε > 0, small; we have F (x)f (0), ∇V (y) + ϕ (x; ∇V (y)) < 0.

Step 3 We claim that there exists T ∈ (0, T * ] such that

S(t)y -y ≤ ε, ∀ y ∈ ∂B r , ∀ t ∈ [0, T ].
Indeed, by contradiction, suppose that there exist sequences t n ∈ [0, T * n ] (n ∈ N, n ≥ 1) and y n ∈ R n , y n = r, such that S(t n )y ny n > ε. Taking a subsequence if necessary, we may assume that t n → 0+ and y n → y * ∈ ∂B r . On the other hand, we have

S(t n )y n -y n = S(t n )y n -S(t n )y * + S(t n )y * -y n ≤ S(t n )y n -S(t n )y * + S(t n )y * -y n .
Then using Theorem 3.2, we obtain

S(t n )y n -y n ≤ √ e 2wtn y n -y * + S(t n )y * -y n .
Using the continuity of the map t → S(t)y, we see that S(t n )y ny n → 0, a contradiction.

Step This contradicts relation (4.12).

Step 5 Thanks to Step 4 of this proof, we may use the invariance by homotopy property of the topological degree and see that This is a contradiction to (4.14).

deg(id R n -S(T ), B r , 0) = deg(H T (1, • ), B r , 0) = deg(H T (0, • ), B r , 0) = deg(-∇V, B r , 0) = (-1) n deg(∇V, B r , 0). Step 6 Let H : [0, 1] × B r → R n , (λ, y) → H(λ, y) := y -S((1 -λ)T + λT )y. We claim that H(λ, y) = 0, ∀ y ∈ ∂B r , λ ∈ [0,
Step 7 Thanks to Step 6 of this proof, we may use the invariance by homotopy property of the topological degree and see that deg(id Finally, for any τ ∈ [0, T ], we also have (see Remark 4.1) (-1) n ind(V, ∞) = deg(id R n -P ϕ (id R n -F + f (τ )), B r , 0). It results that, for r > 0 large enough, we have deg(id R n -S(T ), B r , 0) = 0 and the existence of a fixed point for the Poincaré operator follows from the existence property of the topological degree.

  ) u being the unique solution on [0, T ] to the evolution problem (3.1)-(3.4). Note that ∀ y ∈ R n , S(0)y = y. Lemma 3.1 (See [21]) Let T > 0 be given and let a, b ∈ L 1 (0, T ; R) with b(t) ≥ 0, a.e. t ∈ [0, T ]. Let the absolutely continuous function w : [0, T ] → R + satisfy (1α) dw dt (t) ≤ a(t)w(t) + b(t)w α (t), a.e. t ∈ [0, T ],

w 1 -Theorem 3 . 2

 132 α (t) ≤ w 1-α (0)e t 0 a(s)ds + t 0 e t s a(q)dq b(s)ds, ∀ t ∈ [0, T ]. Suppose that the assumptions of Theorem 3.1 hold. ThenS(t)y -S(t)z ≤ e ωt yz , ∀ y, z ∈ R n , t ∈ [0, T ].Proof Let y, z ∈ R n be given. We have d dt S(t)y + F (S(t)y)f (t), S(t)z -S(t)yϕ(S(t)z) + ϕ(S(t)y) ≤ 0, a.e. t ∈ [0, T ], d dt S(t)z + F (S(t)z)f (t), S(t)z -S(t)yϕ(S(t)y) + ϕ(S(t)z) ≤ 0, a.e. t ∈ [0, T ]. It results that d dt (S(t)z -S(t)y), S(t)z -S(t)y ≤ ω S(t)z -S(t)y 2 -[F + ωI](S(t)z) -[F + ωI](S(t)y), S(t)z -S(t)y , a.e. t ∈ [0, T ]. Our hypothesis ensures that F + ωI is monotone. It results that d dt S(t)z -S(t)y 2 ≤ 2ω S(t)z -S(t)y 2 , a.e. t ∈ [0, T ]. (3.6) Using Lemma 3.1 with w( • ) := S( • )z -S( • )y 2 , a( • ) := 2ω, b( • ) = 0 and α = 0, we get

then

  Theorem 3.2 holds with ω = -α < 0 and the Poincaré operator S(T ) is a contraction. According to (3.5), the unique solution to the problem (3.1)-(3.4) satisfies, in addition, the periodicity condition u(0) = u(T ) if and only if y is a fixed point of S(T ), that is, S(T )y = y. Thus the problem of the existence of a periodic solution to the evolution problem (3.1)-(3.2) and (3.4) reduces to the existence of a fixed point for S(T ).

0 C 2 e 0 f

 020 Since Y (t * ) = u(0) = S(0)y = y and Y (0) = u(t * ) = S(t * )y, we get y ≤ S(t * )y e C1t * + t * C1(t * -s) ds + t * 0 f (t *s) e C1(t * -s) ds < R e C1T + C 2 C 1 (e C1T -1) + T (s) e C1s ds = r 0 .

4 0 -F-F

 40 Let H T : [0, 1] × C r → R n , (λ, y) → H T (λ, y) := y -(1λ)∇V (y) -S(λT )y. We claim that the homotopy H T is such that 0 = H T (λ, y), ∀ y ∈ ∂B r , λ ∈ [0, 1]. By contradiction, suppose that there exists y ∈ R n , y = r and λ ∈ [0, 1] such that y -(1λ)∇V (y) -S(λT )y = 0. Then S(λT )yy = -(1λ)∇V (y) and thus S(λT )yy, ∇V (y) = -(1λ) ∇V (y) 2 ≤ 0. (4.12) On the other hand, we know that d dt S(t)y, v -S(t)y + ϕ(v)ϕ(S(t)y) ≥ -F (S(t)y) + f (t), v -S(t)y , ∀ v ∈ R n , a.e. t ∈ [0, T ]. (4.13) Thus d dt S(t)y, ∇V (y) + ϕ (S(t)y; ∇V (y)) ≥ -F (S(t)y) + f (t), ∇V (y) , a.e. t ∈ [0, T ]. (S(s)y) + f (s), ∇V (y)ϕ (S(s)y; ∇V (y))ds.Step 1 of this proof ensures thatS(t)y ≥ R, ∀ t ∈ [0, λT ] ⊂ [0, T ]. Step 3 of this proof guarantees that S(t)yy ≤ ε, ∀ t ∈ [0, λT ] ⊂ [0, T ].Then using Step 2 of this proof, we may assert that the map s → F (S(s)y)f (s), ∇V (y) + ϕ (S(s)y; ∇V (y)) is upper semicontinuous and strictly negative on [0, λT ]. Thus λT 0 (S(s)y) + f (s), ∇V (y)ϕ (S(s)y; ∇V (y))ds > 0. We obtain S(λT )yy, ∇V (y) = λT 0 d ds S(s)yds, ∇V (y) > 0.

-F

  [START_REF] Adly | A continuation method for a class of periodic evolution variational inequalities[END_REF]. By contradiction, suppose that there exists y ∈ R n , y = r and λ ∈ [0, 1] such that y = S((1λ)T + λT )y. Set h := (1λ)T + λT . We have y = S(h)y and thusV (y) = V (S(h)y).(4.14)On the other hand,d dt S(t)y, v -S(t)y + ϕ(v)ϕ(S(t)y) ≥ -F (S(t)y) + f (t), v -S(t)y , ∀ v ∈ R n, a.e. t ∈ [0, )y, ∇V (S(t)y) + ϕ (S(t)y; ∇V (S(t)y)) ≥ -F (S(t)y) + f (t), ∇V (S(t)y) , a.e. t ∈ [0, T ]. (4.16) Step 1 of this proof ensures that S(t)y ≥ R, ∀ t ∈ [0, T ]. The map s → F (S(s)y)f (s), ∇V (S(s)y) + ϕ (S(s)y; ∇V (S(s)y)) is upper semicontinuous and (by condition (4.6)) strictly negative on [0, T ]. Thus, using (4.16), we obtain V (S(h)y) -V (y) = (S(s)y) + f (s), ∇V (S(s)y)ϕ (S(s)y; ∇V (S(s)y))ds > 0.

  R n -S(T ), B r , 0) = deg(H(0, • ), B r , 0) = deg(H(1, • ), B r , 0) = deg(id R n -S(T ), B r , 0).In conclusion, for all r ≥ r 0 , we havedeg(id R n -S(T ), B r , 0) = deg(id R n -S(T ), B r , 0), deg(id R n -S(T ), B r , 0) = (-1) n deg(∇V, B r , 0). Thus deg(id R n -S(T ), B r , 0) = (-1) n ind(V, ∞).

Project supported by the Australian Research Council (No. DP077014) and the STIC-AMSUD Program "Optimisation Énergétique".


Museum and culture studies traditionally approach social issues related to national museum narratives by critically analyzing the historical development and orderings of collections and their functions. Studies may investigate museums' representational practices in interpretations of the 'other,' for example, or the role of official and state narratives in history museums' constructions of national identity, or scientific paradigms in natural history museums' orderings and material culture. Often these histories are told from the perspectives of 'insiders' who relate the motives of actors engaged in producing narratives of a national character, namely, collectors, state authorities and museum founders (Roberts 1997).

. The purpose of this paper is to develop a perspective on visitors' agency that moves away from a focus on 'practices of inwardness' and 'kinds of interiority, in other words what goes on 'inside' the individual in entanglements with museum objects, to instead locate experience in the entanglements themselves.

Introduction

Museum and culture studies traditionally approach contemporary social issues related to national museum narratives by critically analyzing the historical development and orderings of collections and their functions. Studies may investigate museums' representational practices in interpretations of the 'other' (see [START_REF] Farago | Transforming Images. New Mexican Santos in-between Worlds[END_REF], for example, or the role of official and state narratives in history museums' constructions of national identity [START_REF] Wertsch | Voices of Collective Remembering[END_REF], or scientific paradigms in natural history museums' orderings and material culture [START_REF] Knell | The Culture of English Geology[END_REF]. Often these histories are told from the perspectives of 'insiders' who relate the motives of actors engaged in producing narratives of a national character, namely, collectors, state authorities and museum founders [START_REF] Roberts | From Knowledge to Narrative. Educators and the Changing Museum[END_REF]). However, the consumption of narratives is typically not included in these accounts. While historical and social science perspectives on national museums may acknowledge that visitors bring their identities, memories, and previous knowledge into the museum experience, problems of actors' meaning making and identity formation are not the analytical focus. As a consequence, conceptualizations of visitor agency often remain implicit and under-theorized in analyses of how national museums "make new realities thinkable" [START_REF] Bennett | Civic Laboratories: Museums, Cultural Objecthood, and the Governance of the Social[END_REF].

At the same time, it is apparent that perspectives on the nature of relations between objects and persons do shape notions of agency and mediation in museological investigations. [START_REF] Preziosi | The Museological Object: Art Museums and the Staging of Knowledge[END_REF], for example, speaks of early museums' aims to improve the minds and values of the working class through exposure to art and curiosities previously reserved for the elite, [START_REF] Duncan | Civilizing Rituals[END_REF] describes how public museums have been intertwined with moral ideals and civilizing rituals from their very inception, and [START_REF] Bennett | Civic Laboratories: Museums, Cultural Objecthood, and the Governance of the Social[END_REF] discusses the ordering of relations between objects and persons in terms of enabling different kinds of interiority. Tellingly, in these studies and in museology in general, agency is analytically and empirically explored in terms of the productive power of museums, not visitors. This trend has been the subject of critique in recent research [START_REF] Mctavish | Thinking Through Critical Museum Studies[END_REF][START_REF] Trodd | The Discipline of Pleasure; Or, How Art History Looks at the Art Museum[END_REF].

This paper takes up the critique of museological approaches that situate agency in museum expertise and practices of cultural objecthood rather than in visitors' encounters. Specifically, I take up from a sociocultural perspective the tensions between attributing museum objects an agency that is provisional, in flux, and reconfigurable while at the same time envisaging the effect of museum object on self in terms of a direct, unmediated process. The purpose of this paper is to develop a perspective on visitors' agency that moves away from a focus on 'practices of inwardness' and 'kinds of interiority, in other words what goes on 'inside' the individual in entanglements with museum objects, to instead locate experience in the entanglements themselves. In this way, it is proposed, it may be possible to analytically and empirically situate the narrative performance of museums in the public sphere.

The discussion is organized as follows. First, I explore the concept of interiority in psychology and its implications for understanding relations between objects and the ways in which they are experienced. I then introduce a sociocultural perspective on the significance of mediated activity and the social origins of mind in order to extend the concept of interiority, drawing on the work of [START_REF] Vygotsky | Mind in Society. The Development of Higher Psychological Processes[END_REF], [START_REF] Bakhtin | Speech Genres and Other Late Essays[END_REF] and [START_REF] Wertsch | Vygotsky and the Social Formation of Mind[END_REF][START_REF] Wertsch | Voices of Collective Remembering[END_REF]. I conclude by considering the potential of a dialogic, sociocultural approach to narrative for studies of public and social discourse within but also outside of national museums.

Interiority and Methodological Implications

Interiority is a general term that refers to the inner nature of mental and spiritual life, inviting associations with a range of psychological perspectives on human development and behaviour from the past century. These include Wundt' s introspective psychology in the 1880s, Jung' s theory of symbols and shared archetypes in a collective unconscious in the 1930s and 40s, and Piaget's concept of autistic thought from the 1950s. However, as [START_REF] Vygotsky | Mind in Society. The Development of Higher Psychological Processes[END_REF] points out, a shared characteristic of psychological theories that focus on internal, mental processes is a method of research that implicitly, if not explicitly relies on a stimulus-response framework. This framework serves the purpose of providing a context for the researcher to develop descriptions of processes "presumed to have been elicited by the stimulus" (Vygotsky 1978, p. 59). Although interpretations of the consequences of a response may vary, research aimed at uncovering interiority processes will apply variations of this approach. This means that psychological phenomena are ultimately explained as products of individual mental structures.

How is a stimulus-response framework apparent in museum research? Much of the research in visitor and learning studies is influenced by this methodological approach, for example, grounded in behaviourist and constructivist perspectives on human learning and development. There is a political aspect to this focus as well, in that quantitative methods used to assess learning results, or what [START_REF] Bennett | Civic Laboratories: Museums, Cultural Objecthood, and the Governance of the Social[END_REF] calls museums' 'civic yield,' scientifically address problems of accountability and the need to secure government funding for museums as educational institutions [START_REF] Lindauer | What to Ask and How to Answer: A Comparative Analysis of Methodologies and Philosophies of Summative Exhibit Evaluation[END_REF].

In art museum research, notions of interiority are intertwined with long traditions of reception theories. Here, aesthetic response is equated with cognitive activity, and relations between perception, object and the beholder's experience are explored as such (see [START_REF] Kesner | The Role of Cognitive Competence in the Art Museum Experience[END_REF]. Emphasis is placed on universal, ahistorical aspects of an object's formal characteristics, the structure and organization of which constitute its essence in immediate and unmediated reception. Fredric Jameson describes this as "some 'pre-established harmony' between the structures of the mind (and ultimately of the brain) and the order of the outside world" (1972, p. 110). Interestingly, although newer museology is more interested in 'network' approaches from the social sciences than in generating verifiable learning results, questions of what constitutes 'reception' seem to be similarly based on the premise of an unmediated, cognitive response to objects. This premise often remains implicit, however, for as Knox et al. point out, "researchers are not primarily interested in individuals at all, but in the dynamics of certain kinds of network structure . . . most of these cultural studies have not used ethnography, but have instead concentrated on historical case studies using documentary data" (2005, p. 13).

Furthermore, the notion of a direct correspondence between museum object and beholder's perception is often at the core of museology investigations into how the collecting and ordering of objects in art museums affects cultural competence and networks of art production and consumption. In Bennett's research on the production of cultural objecthood in national historical museums, there is interest in "…whether, and, if so, how the forms of objecthood that are produced by museums are characterized by a similar internal complexity that gives rise to similarly complex and dynamic forms of interiority on the part of persons who become entangled with them" (2005, p. 8). On the whole, I maintain that embodied in approaches to analyzing the roles of national museums in producing a collective identity and public memory is a cognitivist understanding of relations between objects and persons.

Mediation Concept

How might a concept of interiority be 'extended' to analytically and empirically embrace the social and cultural sphere? From a sociocultural perspective, the concept of mediation developed by Vygotsky and others is central to overcoming behaviourism's problematic stimulus-response model. Rather than severing the active subject from the world of objects in a stimulus-response framework, sociocultural perspectives analyze cognition as "individuals-acting-with-mediational-means" (Wertsch 1991, p. 12). This means that relations between human action and the cultural, institutional, and historical settings in which action occurs are always conceived as mediated [START_REF] Wertsch | Sociocultural Studies of Mind[END_REF]. From infancy, humans first participate in their surroundings, and semiotic, cultural 'tools,' particularly language, mediate their actions and meaning making. Human cognition thus develops through processes of participating, negotiating, and interacting in cultural and social practices. This is what researchers mean when they speak of 'social origins of mind' [START_REF] Polman | Mastery and Appropriation as Means to Undersatnd the Interplay of History Learning and Identity Trajectories[END_REF].

The essential role of culturally developed tools in mediating understanding is fundamental to what is referred to as the sociocultural tradition. Therefore, in museums, a sociocultural perspective situates processes of interiority in the social sphere by focusing on naturally occurring human activity in encounters with museum artefacts. Importantly, this perspective has methodological implications, in that human activity -and not products of mental structures -is the unit of analysis. Rather than behaviourist analyses of how external factors stimulate response in the brain, ethnographic methods are used to understand how and whether cultural tools and artefacts are made relevant in social interactions and other forms of public discourse. Consequently, analyses of human action are obliged to include observations of the specific social, linguistic, and historically variable settings. It is in this way that the social sphere enters into analyses of encounters with museum objects, making it possible to situate museum visitors within a spatio-temporal context.

Narrative as a Mediating Tool

What are some of the mediating tools afforded by museum settings? The museum's architecture, objects, orderings, exhibitions, thematic content, practices of looking, conversations, physical interactions, labels, websites, podcasts, blogs, catalogues and other texts are some of the resources that may mediate experience. An intrinsic aspect of many of these affordances is that of narrative. Accordingly, emphasis is often placed in museum and culture studies on the narrative performance of museums. How may narrative performance be understood from a sociocultural perspective?

Museum research often deals with narrative as a cognitive instrument, wielded by museums to mould and fashion the beliefs and behaviours of their visitors. In other words, narrative research often operates with a transmission-absorption model of learning, attempting to get inside individual minds to determine and improve the affect of museum narratives on their experiences, behaviours, and interpretations [START_REF] Roberts | From Knowledge to Narrative. Educators and the Changing Museum[END_REF]. It is precisely this approach to narrative that [START_REF] Wertsch | Voices of Collective Remembering[END_REF] addresses and unpacks in his analysis of Soviet ideology in Russian national museums. In his critique of institutional perspectives on narration in national museums, Wertsch applies a sociocultural perspective in order to distinguish between what he calls narrative production and narrative consumption.

First, Wertsch makes distinctions between kinds of narratives in museums according to their functions and characteristics. He identifies specific narratives that are produced to relate historical events and the characteristics, and points to the 'schematic templates' that these stories of national identity often share. Second, Wertsch draws on Bakhtin to argue the dialogical function of these narratives and sheds light on how visitors master and appropriate meanings that emerge in their encounters with museum exhibitions [START_REF] Wertsch | Voices of Collective Remembering[END_REF]. Mastery is a term that describes 'knowing how to use' historically and culturally developed narratives and forms of knowledge, and points to how people's skills in reproducing this knowledge renders them legitimate participants in social systems. Appropriation, although intrinsically linked to mastery, implies a personal stake in the meanings put forth, what [START_REF] Bakhtin | Speech Genres and Other Late Essays[END_REF] refers to as the "expressive aspect" of utterances. Appropriation stems from Bakhtin's use of the term prisvoenie: (pri) "forward" and (svoi) a reflexive form "on oneself," or "to make one's own" (Wertsch 2002, p. 120). In appropriation, specific narratives, as cultural tools, thus become more identity than knowledge resources, "a means for anchoring or constructing one's sense of who one is" (ibid). Central to Wertsch's argument is that it is possible for people to master national narratives without appropriating them as their own. Therefore, analysis of interaction and discourse in situ makes it possible to discern 'who owns the meaning' in the consumption of narratives. This is illustrated empirically in Wertsch's interviews with museum visitors and Russian citizens. The dialogic function of national narratives is revealed as embedded in concrete discourses that people master as part of their national identity, but also as to contestation, negotiation, appropriation, and in some cases, 'disappropriation' [START_REF] Bakhtin | Speech Genres and Other Late Essays[END_REF][START_REF] Wertsch | Voices of Collective Remembering[END_REF]. It is in this sense that mastery and appropriation are useful in conceptualizing the narrative performance of national museums. In understanding narrative as embedded in concrete discourses that persons may or may not choose to appropriate, visitors are endowed with agency not found in cognitive, transmission theories of reception [START_REF] Pierroux | Communicating Art in Museums[END_REF]. Instead of ideological demonstrations or (ultimately) linguistic structures, then, narratives enter into human activity as mediational means, "part of the 'cultural tool kit' that characterizes a sociocultural setting" (Wertsch 2002, p. 57). It is through analyzing the dialogic function of narratives in national museums, that is, how narratives are made relevant in specific socio-historical settings, that the performative aspects of narrative production and consumption are revealed (Pierroux 2006, in press).

Networks and Multiple Timescales

Although analysis of interaction and discourse may shed light on how museum narratives and other tools mediate visitor experience and meaning making, ethnographic methods do not necessarily entail a micro-approach to museum research. Ethnographic methods are also used to understand how networks of relations make the world meaningful to people [START_REF] Knox | Social Networks and Spatial Relations: Networks as Method, Metaphor, and Form[END_REF], and there is increasing interest in network theories in museum research. In particular, Latour's Actor Network Theory (ANT) is used to examine the processes of making national museums, the specific forms of expertise that produce museum 'objects,' and how forms of cultural objecthood give rise to similarly complex forms of interiority [START_REF] Bennett | Civic Laboratories: Museums, Cultural Objecthood, and the Governance of the Social[END_REF]. Artefacts, from policy documents to orderings of museum objects, play an important role in all of these processes, and [START_REF] Latour | On Recalling ANT[END_REF] refers to the significance of analyzing both human and 'non-human' agents in actor networks.

However, from a sociocultural perspective, it may be argued that intentionality, a uniquely human characteristic, is not captured in network theories that confer an agency to 'non-human' artefacts that is on par with humans. Furthermore, it has been proposed that network theories operate with spatial metaphors, tracing human activity and public memory in spatially organized sets of data and entanglements of artefacts [START_REF] Middleton | The Social Psychology of Experience[END_REF]. In contrast, sociocultural approaches are equally concerned with the temporal aspects of situated activities, that is, how human intentions, cultural artefacts, and institutional frameworks, comprising multiple timescales and individual trajectories, intersect in situ [START_REF] Lemke | Across the Scales of Time: Artifacts, Activities, and Meanings in Ecosocial Systems[END_REF]Ludvigsen et al. forthcoming).

The point to be made here is that the making of national museums involves multiple timescales and activities at individual, social and institutional levels. Sociocultural approaches are sensitive to the task of choosing a unit of analysis that corresponds with the genetic domain under inquiry. In this way, problems of interiority at an individual level are not conflated with institutionalizing processes and the fabricating of cultural objecthood in national museums.

Interiority in the Public Sphere

In this paper I have considered the problem of interiority from a sociocultural perspective. I have argued that visitor agency is often neglected in museology discourse, and that the experience of museum objects is framed, implicitly if not explicitly, in terms of a stimulus-response. Vygotsky's concept of mediating tools was introduced as a means of shifting focus from a transmission model of cognition to a concern with the context of the physical and social arena in which museum visitors act and interact with each other and museum collections. I have pointed to the significance of narrative as a mediating tool in museums, and the possibility of mastering but not appropriating institutionalized discourses. This dialogical of narrative allows for a concept of visitor agency in processes of meaning making. Finally, the problem of conflating types and levels of activity was raised, drawing attention to the analytical and empirical challenges of museum research.

A concern with visitor agency is particularly important in understanding national museums today, as new forms of social software -blogs, wikis, podcasts, and YouTube -are being used to shape museum discourse in the public sphere. Just as visitors' agency within museums may be understood in terms of a mediated, dialogical relationship to objects and their narratives, so too may this understanding be extended to relations between visitors and national museums in a larger cultural context. Therefore, museology needs a concept of interiority grounded in a sociocultural concern with the connections that visitors construct between disciplinary content, narratives, objects and experiences within national museums and, equally important, how these intersect with experiences outside museums. In light of the access to knowledge resources that we have in our global society today, extending notions of interiority into the public sphere seems an important task for national museums setting the frames for their positions as cultural institutions in the future.