Tuan-Minh Pham

Thi-Thuy-Lien Nguyen

Serge Fdida
email: serge.fdida@lip6.fr

Huynh Thi

Thanh Binh
email: minhpt@hnue.edu.vn

Online Load Balancing for Network Functions Virtualization

Network Functions Virtualization (NFV) aims to support service providers to deploy various services in a more agile and cost-effective way. However, the softwarization and cloudification of network functions can result in severe congestion and low network performance. In this paper, we propose a solution to address this issue. We analyze and solve the online load balancing problem using multipath routing in NFV to optimize network performance in response to the dynamic changes of user demands. In particular, we first formulate the optimization problem of load balancing as a mixed integer linear program for achieving the optimal solution. We then develop the ORBIT algorithm that solves the online load balancing problem. The performance guarantee of ORBIT is analytically proved in comparison with the optimal offline solution. The experiment results on real-world datasets show that ORBIT performs very well for distributing traffic of each service demand across multipaths without knowledge of future demands, especially under high-load conditions.

I. INTRODUCTION

Communication networks have been growing rapidly with an increased growth of network-based services over the past decades. In such a context, network service providers have to reduce their operational costs and time-to-market for network services in order to adapt their business to on-demand customer needs. Responding to these objectives, Network Functions Virtualization (NFV) is a recent trend of network transformation that helps service providers offer new and multiple services in a more agile and cost-effective way. By building a virtualized infrastructure where network functions (e.g., Network Address Translation (NAT), Deep Packet Inspection, firewall) are softwarized and virtualized instead of embedded in specialized hardware devices (i.e., middlebox), NFV has the potential to revolutionize the entire telecommunication industry [START_REF]Network function virtualization research group[END_REF], [START_REF] Etsi | Network Functions Virtualisation: Architectural Framework, standard no[END_REF].

Despite the potential of NFV, critical considerations in traffic engineering must be taken into account to maintain strict performance requirements of virtual network functions (VNF), alike in traditional networks [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF]. In this context we tackle the value of using load balancing (LB) to support NFV deployment. Indeed, LB is an important approach to traffic engineering in the Internet as it splits the traffic among multiple paths in order to optimize link utilization, reduce congestion, and minimize delay of data flows in the network. However, to the best of our knowledge, there has been no attempt thus far to propose an effective solution for online load balancing using multipath routing in NFV.

A widely used load balancing technique is ECMP (Equalcost Multipath). The principle of ECMP is that the total traffic going out from one network node will be divided equally over all the shortest paths to the same destination with the same cost. Many routing protocols like Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS) support ECMP [START_REF] Moy | OSPF version 2[END_REF], [START_REF] Callon | Use of OSI IS-IS for routing in TCP/IP and dual environments[END_REF]. Constraints on the shortest path routing and equal load sharing makes the problem complex. It becomes even more difficult when considering the NFV characteristics such as the service function chaining (SFC) and the virtualization capacity at nodes and links of the NFV infrastructure (NFVI).

In this paper, we address an optimization problem of load balancing for NFV, which takes into account the fundamental features of NFV, constraints on the NFVI resource, and ECMP routing. The first main contribution of the paper is an analysis and modeling of the load balancing problem using ECMP for NFV. We formulate the optimization problem of load balancing across multiple paths in NFV as a Mixed Integer Linear Programming (MILP) model. The second important contribution is the ORBIT algorithm that provides an efficient solution for the online load balancing problem. The performance guarantee of ORBIT is analytically proved in comparison with the optimal offline solution.

We evaluated our load balancing solution using two realworld datasets. The results show that ORBIT can provide a solution that is close to optimal. Specially, our algorithm performs more efficiently in a large-scale NFVI under high traffic load conditions. Our solution can be deployed in a SDN network controller where the forwarding rules can be distributed to the forwarding plane of a network switch by using OpenFlow [START_REF] Mckeown | OpenFlow: Enabling Innovation in Campus Networks[END_REF].

The rest of the paper is organized as follows. Section II reviews the related work. Section III describes the load balancing problem across multiple paths and formulates the optimization problem as a MILP model. Section IV describes our proposed algorithm for solving the online version of the problem and our theoretical analysis of the algorithm performance. Section V presents the performance evaluation of our solution. Section VI concludes the paper and highlights future work.

II. RELATED WORK

Many problems arising in the implementation of network functions virtualization have been considered such as the performance and architecture of NFV, and VNF management. The research team of Internet Research Task Force (IRTF) and European Telecommunications Standards Institute (ETSI) are both developing standards for NFV [START_REF]Network function virtualization research group[END_REF], [START_REF] Etsi | Network Functions Virtualisation: Architectural Framework, standard no[END_REF]. Some research results about NFV are summarized in [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF], [START_REF] Xia | Optical service chaining for network function virtualization[END_REF]. More recent results about the performance of NFV are mentioned in [START_REF] Elias | Optimization Models for Congestion Mitigation in Virtual Networks[END_REF]- [START_REF] Leivadeas | Dynamic traffic steering of multi-tenant virtualized network functions in sdn enabled data centers[END_REF]. There are many studies about load balancing for IP network in the current Internet architecture. [START_REF] Fortz | Internet traffic engineering by optimizing OSPF weights[END_REF]- [START_REF] Patel | Ananta: Cloud scale load balancing[END_REF]. However, so far, no research has been found that surveyed an optimal model and efficient online algorithms for load balancing across multiple paths for NFV.

Several papers were published to study the traffic engineering problem in NFV for better performance and efficient resource utilization [START_REF] Mohammed | SDN controller for network-aware adaptive orchestration in dynamic service chaining[END_REF]- [START_REF] Leivadeas | Dynamic traffic steering of multi-tenant virtualized network functions in sdn enabled data centers[END_REF]. In [START_REF] Mohammed | SDN controller for network-aware adaptive orchestration in dynamic service chaining[END_REF], the authors provide the SDN controller's design for load-balanced network resources usage. In their design, if a switch is considered overloaded, the orchestrator redirects the active data delivery paths to other switches. In [START_REF] Leivadeas | Dynamic traffic steering of multi-tenant virtualized network functions in sdn enabled data centers[END_REF], Leivadeas et al. propose a heuristic algorithm for dynamic traffic steering across single paths in SDN enabled data centers. Our work is different as it considers the problem of load balancing using multiple paths. A closely related study to ours is the one conducted by Zhang et al. [START_REF] Zhang | Routing Algorithms for Network Function Virtualization Enabled Multicast Topology on SDN[END_REF]. However, the authors only consider issues of load balancing specific to multicast, and ignore several important features of NFV.

The key difference of our work compared to previous studies on the traffic engineering problem in NFV is that we take into account ECMP routing and the fundamental features of NFV such as SFC and virtualization capacity at both NFVI nodes and links. These factors make the problem under our consideration practical but more complex. In our previous work [START_REF] Pham | Load balancing using multipath routing in network functions virtualization[END_REF], we propose an offline approximation algorithm for load balancing using multipath routing in NFV. In this paper, we study the optimization model and online algorithm for load balancing across multiple paths in NFV. In addition, we aim to provide the performance guarantee of the online algorithm in comparison with the optimal offline solution.

III. PROBLEM FORMULATION

Network Functions Virtualization is based on virtualization technologies such as those used in cloud computing. A NFV framework includes three components which are VNF, NFVI and NFV management system [START_REF] Etsi | Network Functions Virtualisation: Architectural Framework, standard no[END_REF]. In the NFVI, the network functions can be deployed as software that can run in virtual machines on the standard multi-core microprocessor architecture ×86 to handle the data flow. One service demand of NFV may require a network service including many VNFs, in which the VNFs can be processed in a given sequence (e.g., NAT is required to be processed after the firewall function). When processing a service demand, the NFV management system determines the location required to deploy a VNF based on resources available on NFVI. Unlike single-path routing schemes, load balancing strategies split traffic among several paths in order to avoid congestion. The NFV system supporting load balancing both selects the routing paths and splits traffic among them under constraints on NFVI resources and the requirement of the service demand. With the incorporation of the SFC feature of NFV, every data flow of the demand is required to go through a sequence of VNFs dynamically allocated on NFVI nodes according to the demand requirement. We aim to solve the optimization problem of load balancing using ECMP in order to minimize the maximum link utilization of data flows in NFV.

NFVI is modeled as a directed graph G = (V, E), which consists of a set of nodes V and directed links E. A node represents a commodity hardware device that can instantiate a VNF flexibly according to dynamic service demands. Let C 1,e and C 2,v denote respectively the bandwidth capacity of link e ∈ E and the computing capacity of node v ∈ V . F is a set of VNFs available on NFVI. We denote by D a set of service demands. A service demand d ∈ D is characterized by a source s d , a destination t d , demand volume h d , and a service function chain F d ⊂ F . Let k vdi be a parameter that equals to 1 if and only if node v can provide the ith VNF of demand d. Throughout the paper, we will use v and t for a node, e for a link, and d for a demand unless stated otherwise.

We define w = (w e : e ∈ E) to be a link metric vector of links on NFVI. According to service demands, a link metric vector, available system resources and ECMP routing, the system decides a flow allocation vector x(w) = (x epd : e ∈ E, d ∈ D, p ∈ P d ) where P d is a set of flows for demand d, and x epd is the traffic rate on link e of flow p of demand d when the system uses the link metric vector w. We denote by i e and j e the starting node and terminating node of link e, respectively.

Our objective is to find a link metric vector w and a flow allocation vector x(w) in order to minimize the maximum link utilization of data flows and satisfy all requirements of service demands under constraints on NFVI resources. x(w) is determined according to ECMP routing for each w.

We formulate the problem of load balancing using ECMP as a MILP model that allows us to obtain the optimal solution. For convenience, we summarize our notations in Table I.

The variables of our model are as follows:

• w e is a non-negative integer variable that represents the metric of link e. • l vt is a non-negative integer variable that is the length of the shortest-path from v to t (v = t). • x epd is a non-negative continuous variable that represents the traffic on link e of flow p associated with a demand d. • g vt is a non-negative continuous variable whose value is traffic assigned to outgoing links of node v that belongs to the shortest-paths from v to t.

x epd = 0, ∀d, ∀v, v = s d , v = t d (1)
{p,e:ie=s d }

x epd = h d , ∀d (2)
{p,e:je=t d }

x epd = h d , ∀d (3)
The capacity constraint on a link is

p,d x epd rC 1,e , ∀e. (4)
The constraint on traffic splitting according to ECMP is given by

0 g iet - {p,d:t d =t} x epd (1 -u et ) {d:t d =t} h d , ∀t, ∀e. (5)
Constraint [START_REF] Callon | Use of OSI IS-IS for routing in TCP/IP and dual environments[END_REF] assures that if link e belongs to one of the shortest-paths from node i e to node t then its flow to node t is equal to g iet , a value common to all links outgoing from node i e and belonging to the shortest-paths to destination t.

We express the condition of the shortest path routing as follows:

p x epd u et d h d , ∀d, ∀e (6)
1 -u et d l jet d + w e -l iet d (1 -u et d ) M z , ∀d, ∀e (7)
where M z is the maximum link capacity. Constraint ( 6) forces the zero flow to t d (x epd = 0) in the case when link e is not on the shortest-path to t d . Constraint [START_REF] Xia | Optical service chaining for network function virtualization[END_REF] assures that if u et d = 1, then link e is on the shortest-path to t d ; if u et d = 0, then link e is not on the shortest-path to t d .

The link weights need to be larger than or equal to 1. Thus,

w e 1, ∀e. (8)
Constraints ( 9), ( 10), ( 11), ( 12) and ( 13) guarantee that any flow of demand d must go through its VNFs.

x epd {e :j e =ie}

x e pd -M z (1 -b epd ) , ∀d, ∀e, ∀p

x epd {e :j e =ie}

x e pd , ∀d, ∀e, ∀p

The total computing resource required to provide VNFs for all flows through node v is limited by computing resource of node v. We represent this constraint on node capacity as follows:

d,i R v (k vdi {p,e:je=v} x epd , F di ) C 2,v , ∀v (14)
where R v (x, f ) = xr vf , ∀v ∈ V , ∀f ∈ F . r vf is the amount of computing resources required to process function f with one unit of traffic rate at node v.

As mentioned before, we aim at minimizing the maximum utilization over all links. The objective function is U (w) = r. Our MILP formulation of the load balancing problem, which allows us to obtain exact solutions, can be effectively solved for moderate network size by a MILP solver such as CPLEX [START_REF]IBM ILOG CPLEX Optimizer[END_REF]. However, it requires the entire service demands to be known. In the sequel we propose an online algorithm that provides a load balancing solution for each demand on the fly.

IV. ONLINE SOLUTION

In this section, we present the algorithm ORBIT (Online algorithm foR load BalancIng in network funcTions virtualization) which is designed to effectively address the online case of the load balancing problem in NFV.

A. Algorithm Description

The basic idea of ORBIT is to regularly adjust a part of the traffic passing through a partition of NFVI. We divide NFVI into partitions in which the connection between distinct partitions is limited. By routing traffic through a partition, we restrict the possibility of using unnecessarily bottleneck link between partitions, thus improving network utilization and avoiding congestion. The detail of all steps is presented in Fig. 1.

In the preparation phase, we divide NFVI into κ partitions with each partition including a maximum of n/κ nodes while minimizing the capacity of the edges between separate partitions, in which κ and ε are the algorithm parameters. Particularly, we find Λ(κ, ε) = {G i (V i , E i ) : i = 1 . . . κ} by solving a (κ, ε) balanced partition problem. We evaluate the link metric vector used as an input of ORBIT by solving the MILP formulation using the set of service demands requested previously.

The main point of the ORBIT algorithm lies in the computation of traffic flows routed through a partition of NFVI according to the demand requirement and current situation of NFVI. Specifically, when a new demand arrives, we adjust traffic volume of a flow going through G i ∈ Λ(κ, ε) until the traffic requirement of demand d is satisfied. The algorithm then distributes traffic of demand d through G i according to ECMP. We denote by π i the sum of the bandwidth capacity of the edges in a minimum spanning tree of G i . Let q i be a set of demands, in which demand d is included in q i , if and only if G i can provide all VNFs of d. The traffic volume of a flow going through G i depends on both the requirements of demand d and the cost π i associated with G i . In each adjustment, the ratio of demand bandwidth allocated to the flow through G i is computed as follows:

z i ← z i (1 + 1/π i ε) + 1/(π i |Q(d)|) (15)
where

Q(d) = {q i : d ∈ q i }.
In summary, the ORBIT algorithm first divides NFVI into κ partitions by solving a (κ, ε) balanced partition problem. It then computes the traffic volume of a demand routed through a partition according to formula [START_REF] Burns | Path selection and bandwidth allocation in MPLS networks[END_REF]. A traffic flow passing through a partition is routed according to ECMP. We will discuss the selection of the algorithm parameters in section V. In the following section, we analyze the performance of ORBIT for online load balancing of service demands across multiple paths.

Data: NFVI G = (V, E), C 1,e , C 2,v , w, κ, ε Result: Multipath routing solution upon demand arrival 1: find Λ(κ, ε) = {G i (V i , E i ) : i = 1 . . . κ} by solving a (κ, ε) balanced partition problem 2: initialize Q = {q i : q i = ∅, i = 1 . . . κ} 3: initialize z i = 0, i = 1 . . . κ 4: while true do for all G i ∈ Λ(κ, ε) do 7:

if <G i can provide all VNFs of d> then 8:

q i = q i ∪ {d} 9: end if 10:
end for 11:

Q(d) = {q i : d ∈ q i } 12: if Q(d) = ∅ then 13:
Reject demand d and go to line 4

while i:qi∈Q(d) z i < 1 do 16:
for all q i ∈ Q(d) do 17:

z i ← z i (1 + 1/π i ε) + 1/(π i |Q(d)|)

B. Theoretical Analysis

In order to analyze the algorithm performance, we consider the following minimization problem as the primal program P, which is given by Minimize i=1...κ

π i z i (16)
Subject to:

i∈Q(d) z i 1, ∀d ∈ D ( 17
)
z i 0, ∀1 i κ (18)
The dual problem D of the primal problem P is as follows:

Maximize d∈D ζ d
Subject to:

d:i∈Q(d) ζ d π i , ∀1 i κ (19)
ζ d 0, ∀d ∈ D (20)
In the online version of P (i.e., the online primal program), the constraints are given to the algorithm one-by-one. In the online version of D (i.e., the online dual program), a new variable ζ d is introduced and the set of constraints in which ζ d appears is also updated when a new demand d arrives. The performance of an online solution is represented by the competitive ratio that is the ratio between the cost of the online solution and that of the optimal offline solution. Lemma 1 to 3 will give the foundation to derive the competitive ratio of ORBIT.

Lemma 1: The ORBIT algorithm produces a feasible solution for the online primal load balancing problem.

Proof: Consider a constraint i∈Q(d) z i 1 in P. When demand d arrives, ORBIT increases the values of the variables z i until the constraint is satisfied. Hence, the solution produced by ORBIT is feasible, which demonstrates the claim.

Lemma 2 presents a feasible solution provided by ORBIT for the online version of D. We add ζ d ← ζ d + 1 between line 18 and 19 in the ORBIT algorithm in order to find a solution for D.

Lemma 2: A feasible solution for the online dual load balancing problem is obtained by dividing the online dual solution which ORBIT produces by cε log κ where c is a constant. The cost of the feasible solution is

D f = D o /(cε log κ).
Proof: We first prove by induction that, for ∀d ∈ D,

z i 1 κ 1 + 1 π i ε d:i∈Q(d) ζ d -1 . (21)
Initially, z i = 0 and ζ d = 0, so ( 21) is true. Let consider an iteration in which ζ k increases by 1. We denote by z i,1 and z i,2 the values of z i before and after the increment, respectively. Using [START_REF] Burns | Path selection and bandwidth allocation in MPLS networks[END_REF], we have

z i,2 = z i,1 1 + 1 π i ε + 1 π i |Q(d)| = 1 κ 1 + 1 π i ε d:i∈Q(d)\{k} ζ d -1 × 1 + 1 π i ε + 1 π i |Q(d)| . ( 22
)
Since |Q(d)| κ, we find

z i,2 1 κ 1 + 1 π i ε d:i∈Q(d) ζ d -1 . (23)
Thus, ( 21) is true for ∀d ∈ D.

Due to the fact that the algorithm never increases

z i if z i 1, combining |Q(d)| 1, π i
1 and (15), we have z i 3. From this inequality and ( 21), we find

3 1 κ 1 + 1 π i ε d:i∈Q(d) ζ d -1 . ( 24
)
Using the fact that ε 1, π i 1, simplifying (24), we obtain

d:i∈Q(d) ζ d log (3κ + 1) (1 + π i ε) = π i O (ε log κ) .
(25) From ( 25), dividing the solution by cε log κ where c is a constant, we obtain a feasible solution for the online dual load balancing problem with the cost D f = D o /(cε log κ), which proves the claim.

Let P o and D o be the values of the objective function of the solutions that ORBIT produces for the online primal and dual programs, respectively. Let ∆P o and ∆D o be the changes of P o and D o in an iteration of ORBIT. Lemma 3 gives a comparison between ∆P o and ∆D o .

Lemma 3: In each iteration of the ORBIT algorithm, the relationship between the online primal and dual solutions that ORBIT produces is given by ∆P o 2∆D o .

Proof: From the cost function ( 16) of the primal program and the adjustment function [START_REF] Burns | Path selection and bandwidth allocation in MPLS networks[END_REF], we have

∆P o = i:qi∈Q(d) π i z i π i ε + 1 π i |Q(d)| = i:qi∈Q(d) z i ε + 1 |Q(d)| (26)
Since constraint ( 17) is infeasible when ORBIT updates the primal and dual solutions, we find ∆P o 2. In addition, the change in the dual cost is 1. Thus, we obtain ∆P o 2∆D o , which proves the claim.

We are almost ready to derive the competitive ratio of the ORBIT algorithm that is introduced in the following proposition.

Proposition 1: ORBIT produces an online load balancing solution which is O(ε log κ)-competitive.

Proof: First, by Lemma 1 the online solution produced by the ORBIT algorithm is feasible. From Lemma 3 and the fact that initially P o = D o = 0, we find that the ORBIT algorithm produces online primal and dual solutions such that P o 2D o . By Lemma 2, we get a feasible solution for the online dual program with value D f = D o /(cε log κ) where c is a constant. Therefore, we find P o 2D f (cε log κ). Using this inequality and the weak duality theorem, we obtain that the primal solution is at most 2cε log κ times the optimal primal solution, which demonstrates the proposition.

V. EVALUATION

In this section, we describe the setting of our experiments using two real-world datasets. We then analyze the experimental results including the impact of the algorithm parameters and the evaluation of algorithm performance in comparison with the optimal and offline solutions.

In our experiments, we use two real-world datasets that contain the network topology and traffic matrices measured at different times. The first dataset is the Internet2 research network including a topology of 12 nodes, 30 links and traffic matrices with 130 demands [START_REF]Internet2 research network topology and trafc matrix[END_REF]. The traffic traces are recorded for a duration of 30 minutes. The second dataset is the Geant dataset that contains a topology of 22 nodes and 72 links and traffic matrices with 250 demands. The traffic volume of demands in our experiments is a half of total traffic traces over four months in the Geant network. In our experiments, we consider four VNFs available on NFVI. The computing capacity, the resource requirements of a VNF, and the SFC of each demand are randomly generated. In the experiments, we solve the MILP formulation for 10 service demands to compute a weight system for ORBIT. In the preparation phase of ORBIT, we use a multilevel graph partitioning algorithm for dividing NFVI into κ partitions [START_REF] Hendrickson | A multilevel algorithm for partitioning graphs[END_REF].

We first evaluate the performance of ORBIT when varying the value of the algorithm parameters in order to gain insight into the parameter setting of ORBIT in practice. Fig. 2 shows the maximum link utilization and the demand acceptance ratio obtained by ORBIT for various ε when κ = 2 and κ = 3 in the experiments using the two datasets. We observe that the best value of ε for ORBIT is not affected by the number of partitions κ. Specifically, ORBIT obtains better results when ε = 3 and ε = 1 in the experiments using dataset Internet2 and Geant respectively. Thus, we use these values of ε for other experiments. Fig. 3 and4 show the maximum link utilization and the demand acceptance ratio obtained by ORBIT for various κ and the two datasets. We observe that ORBIT achieves better results when κ increases until a threshold is reached, beyond which further increase in κ degrades performance. Particularly, the algorithm obtains the best performance in both the maximum link utilization and the demand acceptance ratio when κ = 3 in the experiment using dataset Internet2 and κ = 2 in the experiment using dataset Geant. The reason is that ORBIT balances traffic over the partitions according to not only the number of partitions, but also the resource capacity of a partition. Under a high value of κ, ORBIT is likely prevented from distributing a flow through a small partition due to the lack of resource, resulting in worse performance. When we choose a different set of traffic demands in both datasets, the performance improvement also occurs at values of κ between 2 and 3. It suggests that we can obtain an appropriate value of κ for a specific NFVI by observing the algorithm behaviour in a time duration. Second, we analyze the performance of the ORBIT algorithm in comparison with the optimal solution. We use the IBM ILOG CPLEX Optimizer to solve the MILP model in order to obtain the optimal results. Fig. 5 provides a comparison of the maximum link utilization obtained by ORBIT and the optimal solution. In both datasets, the results provided by ORBIT are close to the optimal solution. Specially, we observe that ORBIT obtains slightly better results in the experiments using the Geant dataset. This occurs because when NFVI is divided into several partitions, ORBIT can use both the shortest paths and many near-optimal paths. Finally, in order to evaluate the performance of ORBIT in a large scenario we develop an offline solution based on a basic heuristic method called simulated annealing [START_REF] Kirkpatrick | Optimization by simmulated annealing[END_REF] for comparison purposes. As shown in Fig. 6 and7, ORBIT outperforms the offline solution in term of both the maximum Comparison between ORBIT and an offline solution using Geant link utilization and demand acceptance ratio when the number of service demands is large. We argue that ORBIT is more efficient in this case due to the support of near-optimal paths for load balancing in a heavy loaded network.

The above results demonstrate that we have designed an efficient solution for online load balancing in NFV. ORBIT achieves good performance in terms of the link utilization and demand acceptance ratio in comparison with the optimal and offline solutions, especially when the network load is high.

VI. CONCLUSION

We addressed the optimization problem of load balancing in NFV, which is important for guaranteeing the high performance requirements of a network function in a virtualized environment. We formulated the problem as a MILP model to compute the optimal solution. We developed the ORBIT algorithm that provides an efficient solution for online load balancing. As demonstrated through theoretical analyses, the performance of ORBIT is O(ε log κ)-competitive where ε and κ are the algorithm parameters associated to graph partitioning on NFVI. Using two real-world datasets, we performed several experiments in which the result provided by ORBIT is close to the optimal solution. Importantly, the experiment results show that ORBIT works very well in comparison with an offline solution when the network load is high. This is obviously an important aspect for the practical deployment of our load balancing solution.

Although focusing on load balancing across multipaths according to ECMP, we believe the model and algorithm developed in this study can be exploited in the procedures of optimizing several performance metrics of other multipath routing schemes in NFV. Possible extensions of our results include an evaluation of the impact of ORBIT on congestion control when considering a delay guarantee in a demand, a more detailed analysis taking into account demand statistics of end-users in the network partitioning phase of ORBIT, or the capability of meeting a Service Level Agreement (SLA) when an infrastructure failure event occurs in NFV. It will be valuable to study also the performance impacts and economics of NFV in a mobile and multiple providers environment as in [START_REF] Pham | DTN support for news dissemination in an urban area[END_REF], [START_REF] Pham | Analysis of ISP caching in information-centric networks[END_REF].

ex

  epd (k iedi + k jedi ) > 0, ∀d, ∀i, ∀p, h d > 0 (9) e x epd > 0, ∀d, ∀p, h d > 0 (10) 0 x epd M z b epd , ∀d, ∀e, ∀p

5 :

 5 if <a new demand d arrives> then 6:

Fig. 1 .

 1 Fig. 1. The ORBIT algorithm

3 Fig. 2 .Fig. 3 .NumberFig. 4 .

 3234 Fig. 2. Impact of parameter ε on the algorithm performance

Fig. 5 .Fig. 6 .Number

 56 Fig. 5. Comparison between ORBIT and the optimal solution

  We now present the constraints. The conditions of flow balance at one node are given by

			TABLE I
		SUMMARY OF NOTATIONS
	Notation			Meaning
	V	The set of NFVI nodes
	E	The set of directed links on NFVI
	F	The set of VNFs available on NFVI
	D	The set of service demands
	n	The number of NFVI nodes
	m	The number of service demands
	C 1,e	Bandwidth capacity of link e ∈ E
	C 2,v	Computing capacity of node v ∈ V
	ie	The starting node of link e ∈ E
	je	The terminating node of link e ∈ E
	h d	The traffic volume of demand d ∈ D
	s d	The source node of demand d ∈ D
	t d	The destination node of demand d ∈ D
	F di	The ith service function required by demand d ∈ D
	P d	The set of traffic flows of demand d
	χe	The total traffic rate of all data flows going through link e
	we	A non-negative integer variable that represents the metric
		of link e
	lvt	A non-negative integer variable that is the length of the
		shortest path from node v to node t
	x {p,e:ie=v}	x epd -	{p,e:je=v}

epd A non-negative continuous variable that represents the traffic on link e of flow p of demand d gvt A non-negative continuous variable whose value is traffic assigned to outgoing links of node v that belongs to the shortest paths from node v to node t uet A binary variable that equals to 1 if and only if link e is on a shortest path to node t b epd A binary variable that equals to 1 if and only if flow p of demand d uses link e k vdi A parameter that equals to 1 if and only if node v can provide the ith VNF of demand d r A non-negative continuous variable that is the maximum utilization over all links r vf The computing resources required to process function f with one unit of traffic rate at node v w A link metric vector of links on NFVI, w = (we : e ∈ E) x A traffic allocation vector for all demands, x = x epd : e ∈ E, p ∈ P d , d ∈ D χ e /C 1,e . The maximum utilization over all links is represented by the dependent variable r = max e {χ e /C 1,e }.

ACKNOWLEDGMENT

This work was partially supported by project B2016-SPH-17 from the Vietnam Ministry of Education and Training.


Recherches linguistiques de Vincennes 43 -2014 -p. 97-122

Eric Corre Université Sorbonne Nouvelle -Paris 3 Preverbs in Russian: situation or viewpoint aspect?

1-Introduction

Many languages use adpositional morphemes, either verbal prefixes (henceforth, preverbs) or particles, as a means to extend the morphological possibilities, and consequently the lexical inventory, of verbs. Such morphemes traditionally add spatial and/or directional, temporal and/or aspectual, or simply idiosyncratic, information to a verb's root. In Russian, where the system of temporal marking is impoverished (reduced to one present-future tense and one past tense), preverbs are used to encode such distinctions. Each verb is either soveršennyj ("accomplished", translated as "perfective", henceforth pf) or nesoveršennyj ("unaccomplished", translated as "imperfective", henceforth imp). The vast majority of base verbs (or simplex stems) are imp, but there are exceptions. The addition of a preverb systematically derives a corresponding pf verb, as in (1) :

(1) a-Poka on e-l buterbrod, za-zvoni-l telefon.

while 3SG eat.IPFV-PST.3SG sandwich, za-ring.PF-PST.3SG phone "While he was eating the sandwich, the phone rang." b-On s'-e-l buterbrod i lëg spat'.

3SG s'-eat.PFV-PST.3SG sandwich and go.PFV.PST.3SG to-bed "He ate (finished eating) his sandwich and went to bed."

This example has an Acccomplishment VP: the (a) sentence, which describes a progressive event, require the use of the imp bare verb, while the (b) sentence, which force a perfective viewpoint, has the preverb s'-added to the imp root, and the verb becomes pf. This contrast raises the question of the role of the preverb: does it encode viewpoint aspect, i.e., the perfective viewpoint much like the simple past in English, or is it, rather, a telicizer which adds an inherent limit to the verb's denotation, or does it fulfil both functions?

Aktionsart, or situation aspect (henceforth, SA), concerns innner aspect, i.e., whether a given VP implies an inherent endpoint to the event. Viewpoint aspect (henceforth, VA), or outer aspect, concerns the relation between the event and a temporal interval: the perfective viewpoint includes both endpoints of the event within a closed temporal interval, while the imperfective viewpoint includes part of the event within an open interval. The data in (1) are incomplete; they suggest that the morphology -presence vs. absence of the preverb -affects both SA and VA. But the base verb, i.e. the morphologically imp verb in Russian, can in fact express perfective VA:

(2) Včera Ivan gotovi-l, stira-l bel'ë i smotre-l televizor.

yesterday Ivan cook.IPFV-PST.3SG wash.IPFV-PST.3SG linen and watch.IPFV-PST.3SG television "Yesterday Ivan cooked, washed clothes and watched TV".

In (2), the event is presented perfectively, i.e., with both endpoints included in the assertion time: at UT, Ivan has finished cooking, washing his clothes and watching TV. Yet statements like these do not require a preverb. Such data are problematic for proponents of preverbs as markers of VA. This paper will defend the somewhat unorthodox view that viewpoint perfective aspect is not marked by the preverbs, that viewpoint aspect is neutral in Russian, and that it is SA that is grammaticized. VA is merely inferred through compositional restrictions or simply correlations. It is organized as follows: after discussing the classification into three types of preverbs found in the literature (section 2), we will show that is is possible to provide a unified account of the functional role of preverbs, that of marking telicity (section 3), but crucially, not telicity as generally discussed in the literature. Instead, the case of podelimitative verbs, a special class of prefixed pf verbs which resist traditional telicity tests, will help us establish the notion of telicity as terminativity (section 4). Section 5 will take up the discussion of the exact role of the preverbs in marking SA or VA, and will conclude in favor of the former hypothesis.

Three types of preverbs in Slavic

The divisions into aspectual types of preverbs has a long history in Slavic linguistics. The overarching distinction has been that between the formal category of aspect (vid) and the lexical category of Aktionsart (sposoby dejstvija, or "modes of action"). It has been assumed that all the preverbs have semantic content, although this content may not be perceptible because of a semantic overlap with the meaning of the verb [START_REF] Isacenko | Grammatičeskij stroi russkogo jazyka v sopostavlenii s slovackim : morfologija, čast' 2[END_REF]. The loss of the tense system in Old Russian gave the preverbs new life, however, as they were called upon to ensure the aspectual-temporal marking no longer available on the verb. Slavic aspect is considered to be typologically exceptional [START_REF] Comrie | Aspect[END_REF][START_REF] Tournadre | Typologie des aspects verbaux et intégration à une théorie du TAM[END_REF]), since it relies so heavily on derivational morphology to encode grammatical distinctions, blurring the boundaries between SA and VA. A long-standing tradition distributes the preverbs over three main categories according to their aspect or Aktionsart function.

2.1. Meaning-modifying, lexical or "specialized perfectives" [START_REF] Janda | Aspectual clusters of Russian verbs[END_REF] There are twenty or so preverbs which constitute the privileged means whereby Russian derives new verbal lexemes. The principle is as follows: a simplex (in the vast majority of cases an imp, dynamic or not) verb, e.g. bit', 'beat, hit', combines with one or more of the twenty prefixes, deriving a new lexical unit which are automatically pf.

(3) u-bit' (čeloveka), 'kill (a man)'; raz-bit' (stakan), 'break (a glass)'; po-bit' (sobaku), 'beat a dog'; pro-bit' (dorogu), 'open up (road)'; za-bit' (trevogu), 'raise (the alarm)'… Then, as the system rests on aspectual pairing, an imp partner is now needed for these new verbs. This is achieved through the regular process of secondary imperfective (SI) suffixation by means of -a/-iva/-yva suffixes (depending on the stem):

(4) u- bi-va-t'; ; raz-bi-vat'; po-bi-vat'; pro-bi-vat'; za-bi-vat'. u-STEM-2.IPFV-INF 1 2.2. Purely perfectivizing or empty preverbs, or "natural perfectives" [START_REF] Janda | Aspectual clusters of Russian verbs[END_REF] At the other end of the spectrum is the "empty" preverb, discussed by [START_REF] Maslov | Vid i leksičeskoe značenie glagola v sovremennom russkom literaturnom jazyke ("Aspect and the lexical meaning of verbs in Russian contemporary literary language")[END_REF], [START_REF] Vinogradov | Russkij jazyk [The Russian Language[END_REF], [START_REF] Tixonov | K voprosu o čistovidovyx pristavkax v sovremennom russkom jazyke [Empty prefixes in modern Russian[END_REF], [START_REF] Avilova | Vid glagola i semantika glagol'nogo slova [Verb aspect and the semantics of the verbal word[END_REF], among others. These preverbs form an aspectual pair with the base verb without changing its meaning. For example, the base imp verb pisat', 'write', is paired with napisat' , "preverbna-write", which is used whenever the notion pisat' is used in a perfective context.

(5) pisat '/na-pisat', 'write'; čitat'/pro-čitat', 'read'; delat'/s-delat', 'do'; gotovit'/pri-gotovit', 'prepare'; stroit'/po-stroit', 'build'; slyšat'/u-slyšat', 'hear'; myt'/vy-myt', 'wash'; platit'/ zaplatit', 'pay', portit'/is-portit', 'waste, damage'… One overwhelming piece of evidence in favor of the purely functional role of the empty preverb is that these prefixed perfectives do not derive a secondary imp, although it would be morphologically possible to do so: *napisyvat', *sdelyvat', *postraivat', *zaplačivat', etc., do not exist.

The concept of aspectual pairing has generally been described in semantic terms: the most natural aspectual verbal pair is one in which the imp verb denotes the development phase of the dynamic event while the prefixed pf verb indicates attainment of the telos, deriving an accomplishment or an achievement. This process has had the effect of excluding stative verbs, which lack a telos, activity verbs, which are atelic, and degree achievement verbs, which lack an inherent final point. Yet, with few exceptions, all verbs in Russian have an aspectual correlate. This has led some authors, notably Filip (2006), to call into question the systematic telicity-marking role of the preverbs: states, activities and degree achievements being deprived of a telos in their denotation, the preverb cannot mark telicity. In section 4, we will see that it is possible to give a unified account of pf prefixation if we relax the requirement that preverbs indicate the attainment of the lexical telos.

2.3. "Superlexical preverbs", "procedurals" [START_REF] Forsyth | A Grammar of Aspect. Usage and Meaning in the Russian verb[END_REF] or "complex acts" [START_REF] Janda | Aspectual clusters of Russian verbs[END_REF] The superlexical preverbs yield complex events. They take an activity verb as input and impose a (temporal or quantificational) limit of some kind on the activity. They thus contribute to event structure (hence the term "superlexical"). However, they are generally denied full grammatical status because they do not constitute a perfect pf correlate to an imp verb; they can be left unpaired. For example, from the imp base Activity verb kričat', "shout", the following verbs can be derived with a "superlexical" preverb:

(6) Kričat' > za-kričat' (ingressive, 'start to shout') / po-kričat' (delimitative, 'shout for a while')/ na-kričat'-sja (cumulative, 'shout a lot' ) / po-krik-ivat' (distributive, 'shout from time to time or at several people') / krik-nut' (semelfactive, 'give one shout').

The linguists who classify superlexicals as a functional category distinct from meaningmodifying preverbs [START_REF] Smith | The Parameter of Aspect[END_REF][START_REF] Binnick | Time and the Verb: A Guide to Tense and Aspect[END_REF], Svenonius 2004[START_REF] Ramchand | Time and the event: The semantics of Russian prefixes[END_REF]) essentially base their classification on the contrast between the spatial and idiosycratic meanings provided by the latter and the more systematically temporal readings for the former. As Lakorczyk (2010) notes for Polish, however, this classificatory choice is not supported by syntactic, semantic and morphological evidence.

First, the predictability of the meanings of the superlexicals is not as systematic as has been claimed. Even one of the most common of this class of preverbs, inceptive za-, is subject to idiosyncratic constraints, just like any other lexical preverb : "Ivan sat down and started working

Za-is felicitous only if the inchoation or ingression occurs against the background of its absence, i.e. if the entity that initiates a process functions on a binary mode [START_REF] Paillard | L'inchoation entre préverbes et auxiliaires[END_REF]. This explains why (7a) is felicitous, and (7b) is not.

Moreover, except for the case of distributive and delimitative po-(henceforth, po-delim), all of the superlexicals give rise to telic readings. Even the case of po-delim verbs needs to be qualified for Russian, since more and more of them actually do occur as normal pf partners of bare imp verbs and test as telic (see section 4). Furthermore, even if some superlexicals are indeed unpaired pf verbs (e.g., the verb kričat' does not derive secondary imperfectives: *zakrikivat', *nakrikivat'sja, do not exist), many other pf superlexicals in Russian are paired with an imp verb obtained by regular secondary imperfectivization (SI):

(8) za-govori-t' / za-govar -iva -t',"start talking" This section has shown that the three traditional categories largely overlap, both in their morphological form and their grammatical behavior. The overwhelming generalization that emerges from the data presented above is that the addition of a preverb almost invariably (save for po-delim) turns an atelic predicate (an imp verb) into a telic predicate (a pf verb). I will therefore endorse the claims made by [START_REF] Borer | The Normal Course of Events[END_REF] and [START_REF] Lakorczyk | Decomposing Slavic Aspect: the Role of Aspectual Morphology in Polish and other Slavic Languages[END_REF] that Russian preverbs are all telicity markers, with the proviso that the term telicity needs to be somewhat revised and extended. In particular the term must include po-delim verbs, which behave more and more frequently as telic partner verbs in Russian. We will adopt a more "relaxed" notion of telicity similar to what [START_REF] Mehlig | Aspect and bounded quantity complements in Russian[END_REF] and [START_REF] Padučeva | Formal and informal semantics of telicity[END_REF] refer to as terminativity.

3-Are the preverbs exponents of "pre-functional" telicity or full telicity?

We noted immediately above that the vast majority of preverbs turn a base imp verb into a telic pf verb. This overwhelming observation should lead all authors to agree on the basic Aktionsart function of Russian aspect: it is situation aspect (SA) that is grammaticized in Russian. However, as we also saw above, superlexicals seem to be a mixed category: some of these pf verbs occur with an imp partner while others do not. For this reason, some scholars, such as Schoorlemmer (2004) and [START_REF] Filip | On accumulating and having it all. Perfectivity, prefixes and bare arguments[END_REF][START_REF] Filip | Events and maximalization: the case of telicity and perfectivity[END_REF] deny a full grammatical function for the preverb.

In this section we will first discuss the influential work of Hana Filip which assigns a prefunctional status to these preverbs. We will then argue for an alternative model, based on [START_REF] Borer | The Normal Course of Events[END_REF], [START_REF] Mehlig | Aspect and bounded quantity complements in Russian[END_REF][START_REF] Lakorczyk | Decomposing Slavic Aspect: the Role of Aspectual Morphology in Polish and other Slavic Languages[END_REF], in which all prefixes are grammatical exponents of telicity, and the semantic notion of telicity is instantiated syntactically through a quantity range assignment to an Asp head, AspQ (cf. Borer 2006:159). We will propose that this quantity assignment is not strict quantization, which poses the existence of an incremental relation that maps part of an individual to part of an event; rather it is terminativity.

Preverbs as contributing a pre-functional level

For [START_REF] Filip | Events as Grammatical Objects, from the Combined Perspectives of Lexical Semantics, Logical Semantics and Syntax[END_REF][START_REF] Filip | On accumulating and having it all. Perfectivity, prefixes and bare arguments[END_REF][START_REF] Filip | Events and maximalization: the case of telicity and perfectivity[END_REF], who is strongly inspired by the quantization model of Krifka, preverbs are not direct markers of telicity; telicity is, rather, epiphenomenal. [START_REF] Filip | Events as Grammatical Objects, from the Combined Perspectives of Lexical Semantics, Logical Semantics and Syntax[END_REF] observes that some preverbs, particularly the na-and po-superlexicals, pose a "quantization puzzle" in the sense that they do not give rise to quantized readings. [START_REF] Filip | On accumulating and having it all. Perfectivity, prefixes and bare arguments[END_REF][START_REF] Filip | Events and maximalization: the case of telicity and perfectivity[END_REF] wants to preserve the insight that preverbs are lexical operators which merely add additional content (space, manner, etc.) for the calculation of telicity cum quantization based on the presence of the MAXE operator and a scalar structure. The MAXE operator is "a monadic operator, such that MAXE (∑) ⊂ ∑, which maps sets of partially ordered events ∑ onto sets of maximal events MAXE (∑)" (Filip 2008: 219). The preverb merely "adds meaning components that contribute to specifying a criterion for the ordering of events in their denotation. In this way, prefixes contribute to licensing the application of MAXE." (Filip 2008: 244) What this implies is that preverbs express the maximality of the eventuality of a process verb, but they do not do so directly; rather, they specify the mode of execution of that maximality, which can differ according to the preverb used. Filip emphasizes the fact that "the MAXE operator contributes to the expression of directed path structures in space and time, cardinality, measure, etc., i.e., components that have independently been uniformly represented by means of scales". (2008: 245) The hypothesis that preverbs are "scale-inducing expressions" is supported by the fact that many imp base lexemes have several pf partners, as shown in the following pair of sentences:

(9) a-Gde moj zelënyj sviter ? Ja xocu idti v nëm v magazin. "Where's my green sweater? I want to wear it to go to the store." On ešče mokryj, ja ego po-stira-l.

(# vy-stira-l) "He washed his jacket and pants (…), and when everything had dried off, ironed all of these."

3SG
http://www.ruscorpora.ru/search-main.html#) [Example from Svestinskaja 1995:172] In ( 9a), what matters in the discourse context is that the sweater is wet, rather than its having undergone a whole process leading up to it being clean; for that reason, vy-would be infelicitous because it would imply a maximal degree of change on the "dirty clean" scale. Vy-is felicitous in (b) for opposite reasons: the context makes it clear that what is at stake is to reach an ideal state of cleanliness for the dirty object, and po-cannot express that. Still, pf verbs with po-, such as postiral in (9), test as telic (see the discussion below).

A more serious argument in favor of Filip's model comes from the behavior of po-delim verbs, which generally test as atelic although they are pf. They stubbornly resist the za-test (the in x-time frame adverbial test), and are compatible with durative adverbials: Po-indicates that the predicates' natural (lexical) terminus is not accessible. [START_REF] Flier | The scope of prefixal delimitation in Russian[END_REF] referred to these verbs as "consummations"; [START_REF] Kučera | A semantic model of verbal aspect[END_REF] dubbed them "atelic events".

A last piece of evidence brought by Filip to confirm the lexical (pre-functional) status of preverbs is the fact that they are retained in secondary imperfectivization (cf. example 4). Instead, one may say that the secondary imp suffix (-iva/-yva) undoes the telicity of the preverb in the pf verb. This is the path taken by Borer and Lakorczyk, to be discussed in section 5.

Filip is certainly correct to defend the hypothesis that preverbs are all lexical, that is, derivational. Russian does not possess a single meaningless prefix dedicated to marking telicity in the functional structure projected by the verb. On the other hand, one may ask: why should that be necessary? Typological studies on the grammaticalization of tense and aspect markers (e.g., [START_REF] Bybee | The Evolution of Grammar -Tense, Aspect and Modality in the Languages of the World[END_REF] have established that whenever lexical elements change their function from lexical to grammatical, they retain some of their initial lexical content, which becomes more abstract. Such diachronic change accounts for crosslinguistic variation in the expression of notions such as perfectivity. Many scholars have noted that a Russian prefixed pf verb does not have the same grammatical function as a perfective (i.e., simple past) English verb: while the former always denote the attainment of a limit, the latter simply express closure of the event. We noted that in examples (1b) and (2) above, the prefixed pf s'ela buterbrod, "ate a sandwich" in (1b) indicates that the event of eating the sandwich attained its completion point, it is a case of telicity cum quantization: the total consumption of the entity affected ensures that all of the event is over. Not so in (2), where the imp verb has retrospective meaning only: the sentence is uncommitted as to the actual completion of the events, and the imp verb is used. In both cases, English has to use the simple past, which shows that it is not construed in the same way.

In conclusion, there is no contradiction in the fact that lexical material such as prepositionallike elements that grammaticalize may keep some of their lexical content (here, attainment of a completion point) while at the same time taking on a grammatical function (marking telicity). Filip's model is also partly falsified by the fact that Russian seems to be developing a default perfectivizer: po (section 4).

What is telicity?

The above discussion has called into question the traditional view of telicity. In the literature, it has been defined as the presence of an inherent enpoint [START_REF] Vendler | Verbs and times[END_REF][START_REF] Dowty | Word Meaning and Montague Grammar[END_REF], or in terms of event-argument homomorphism [START_REF] Krifka | The origins of telicity[END_REF][START_REF] Tenny | Aspectual roles and the syntax-semantics interface[END_REF]). However, as [START_REF] Borer | The Normal Course of Events[END_REF] notes, there are several types of telicity. The test of in-x time frame adverbials probes for a very particular type of telicity, that which exists at the end of the event. Borer points out that an in-adverbial by itself does not make an atelic event telic: [examples from Borer 2005: 142] Borer proposes that in x-time is a modifier of quantity, not an operator. It "equates the time of culmination with the actual end of the event itself" (2005: 143). For Borer, quantity readings also exist in the presence of intermediate culminations. She proposes that telic predicates, or Quantity predicates, as she calls them, are predicates that are non homogeneous.

Homogeneity is defined by the properties of being cumulative and divisive. John read books is cumulative, for example, because "John read books" + "John read books" = "John read books". It is also divisive because "a part of 'John read books' = "John read books". Predicates that are both cumulative and divisive are atelic, which is why (11b) and (12c) are rejected. Predicates that are not cumulative or not divisive are telic. For example, John read three books is not cumulative ("John read 3 books" + "John read 3 books" = "John read 6 books"); "John read 6 books" is not in the denotation of the predicate "John read 3 books".

Likewise, John read 3 books is not divisive: "a part of 'John read 3 books' ≠ "John read 3 books". The important property is that of divisiveness. A sentence like "John read many books" implies divisiveness: "a part of 'John read many books' ≠ John read many books (but John read a few books). Read many books exemplifies an intermediate culmination of the type Borer claims is nevertheless telic, although the quantity of books remains indefinite, so that the endpoint remains vague. Similarly, the examples in (13) are telic:

(13) a-Kim ate more than enough meat. b-We filled the room with smoke.

A predicate becomes telic at the point at which it becomes non homogeneous. In (13a), the point at which Kim ate enough meat is the endpoint. It is sufficient for there to be a quantity, which is either non divisive or non homogeneous, for a telic reading of a predicate. This definition is valid for Russian, where even perfectivizing preverbs may allow the expression of a vague quantity:

(14) On vy-pi-l nemnogo vod-y.

3SG vy-drink.PFV-PST.3SG a-little water-GEN "He drank a little water." (Padučeva & Pentus 2008: 200) note that the predicate in ( 14) is not cumulative: "if one goes on drinking, then one would, possibly, drink much water". It is not quantized either: "for some preceding interval drink some water is also true, because the predicate has the subinterval property". Rather, I propose that the event is divisive: a part of 'he drank a little water' ≠ 'he drank a little water', but "he drank very little water"). The event is therefore telic because at some point it became non homogeneous. This example shows that the preverb is the exponent of terminativity, not necessarily telicity understood as strict quantization.

These examples show that the in x time adverbial test is epiphenomenal: it probes for telicity-as-finality. Other tests are needed. One test that does not only test finality and duration is the cumulativity test proposed by (Lakorczyk 2010: 63): it consists in coordinating two time adverbials with a given predicate. A predicate that yields either a one-event or a two-event interpretation is atelic, while a predicate that only yields a two-event interpretation is telic: (15a) is ambiguous: the sentence is felicitous if it describes either two episodes of eating meat distributed over two days, or two distinct episodes of eating meat (on each day). But for (b) and (c), only the latter interpretation obtains: (b) cannot mean that part of the 300 grams of meat gets eaten on Monday, and the other part on Tuesday; likewise, (c) does not entail that he ate enough meat on Monday and more than enough on Tuesday. Sentences (b) and (c) force us to understand that two distinct episodes of eating the specified quantity of meat occurred.

For Russian, this test shows that imp verbs systematically test as atelic. More importantly, it helps establish the fact that most pf procedurals (the "superlexicals") are also telic (contra Filip). For example, a za-verb, which is ingressive ("start doing something") tests as telic although it focuses only the beginning point of the event and lacks duration. Filip's quantization puzzle disappears; na-verbs are in fact also telic, as well as some po-verbs: Only (16a), with the imp verb, can mean that the smoking episodes can extend randomly over both days. The pf verbs all imply that there were distinct episodes of smoking. Even (c), with po-delim, lexically encodes "the semantics of the end" in its meaning (Padučeva & Pentus 2008: 209): "On pokuril" means "he smoked for a while and then stopped'": it gives rise to two events. In the examples above, only the imp verb, which is both cumulative and divisive, is truly atelic.

This "relaxed" notion of telicity is discussed in the Slavic literature. Padučeva & Pentus (2008:193) observe that in English the verb form does not express terminativity, whereas in Russian it normally does, strongly so, even sometimes beyond finality, denoting a post-state: The pf verb in (17b) is felicitous if the post-state holds after 9. A Russian pf is often truthconditionally equivalent to an English resultative perfect. Such post-state telicity may be enforced by the semantics of a given prefix.

It seems, therefore, that the concept of terminativity is more appropriate to describing the semantics of Russian prefixed pf verbs. As [START_REF] Padučeva | Formal and informal semantics of telicity[END_REF] and [START_REF] Mehlig | Aspect and bounded quantity complements in Russian[END_REF] note, all prefixed pf verbs have the "semantics of the end lexically encoded in their meaning" (ibid.). Crucially, however, terminativity need not cover the whole interval; it is not synonymous with quantized. The difference it allows between "absolute-terminative and relative-terminative predications" (Mehlig 2008: 258) is best observed by comparing different pf verbs for one single imp root. Let us consider example (9), repeated in (18). Although the sentence with po-is felt to be less resultative than it would be with the empty preverb vy-, it is nevertheless telic: (18) describes two distinct episodes of washing a sweater. It means that some washing was done on the sweater, without specification of the final state of cleanliness of the entity. As [START_REF] Jablonska | When the prefixes meet the suffixes[END_REF] says of po-in Polish: it "introduces an arbitrary Reference Time that seals off the event." (367)

The preceding sections have shown that all preverbs, which morphologically perfectivize an imp root in Russian, can be considered as telic if the notion of telicity is revised so that finality as measured by the in-test is just one case among others. A more adequate notion is terminativity (Padučeva & Pentus, Mehlig 2008), understood as a functional operation whereby a preverb added to an atelic imp root encodes a semantics which includes the end of the event. This generalization is supported by the overwhelming empirical fact that adding a preverb in Russian automatically makes an imp root pf. This approach has the advantage of avoiding the three-fold distinction among preverbs that obscures the regularities observed, while preserving Filip's insight that prefixation retains a strong lexical origin. I concur with Lakorczyk's observation that "it might be that what Filip suggests characterized an older stage in the development of Slavic aspect, but the functional role of prefixes [in Russian] has since been grammaticalized to a degree that can no longer be denied" (83).

A question remains concerning po-delimitative verbs, which still test as atelic with respect to the za-test. However, as we have seen, po gives rise to several types of terminative events when accompanied by temporal adverbials. This will be illustrated in the next section.

Narrowing down telicity cum terminativity: the case of po-verbs

Many scholars have noted that the preverb po-is currently extending it use and might even become a generalized pf marker in Russian [START_REF] Comrie | Aspect[END_REF][START_REF] Camus | Quelques considérations sur le préverbe po-en russe contemporain[END_REF][START_REF] Šmelev | Leksii po russkoj aspektologii[END_REF][START_REF] Dickey | Aspectual pairs, goal orientation and po-delimitatives in Russian[END_REF][START_REF] Guiraud-Weber | Le préverbe po-en russe moderne[END_REF][START_REF] Lakorczyk | Decomposing Slavic Aspect: the Role of Aspectual Morphology in Polish and other Slavic Languages[END_REF]). As Lakorczyk (2010) writes, "Slavic languages seem to be settling on a default perfectivizer -i.e., one that is most frequently applied to new verbs" (73). This seems to indicate that the grammaticalisation of SA is becoming firmly entrenched in Russian.

Po-is the most polysemous prefix of all; it usually has the following senses: "think", "work", "believe", "feel".

The use that poses a problem for quantized accounts of telicity is delimitative po-(in c). It denotes limited duration for an atelic event and thus tests as atelic in the za -test, as we have seen. Recall, however, that the za-test probes for one case of telicity, the one that measures the attainment of the telos or inherent boundary. The za-test does not apply here, because the event has no telos: po-indicates limited duration and thus has the effect of stripping the predicate's denotation of a telos.

If we want to preserve the overwhelming empirical generalization that all preverbs in Russian make an imp root pf, we want to preserve the insight that all preverbs impose a boundary on the event. At this point we will introduce some facts which modify the assertion generally made about po-delim verbs.

4.1. What po-delim verbs are not Some of the claims made in the literature about the po-delim pf verbs are not verified.

Extension of functional scope

In Russian, "delimitative" po-verbs display a tendency to develop into real perfective partner verbs" (Šmelev & Zaliznjak 1997: 112). They are clearly extending their functional scope, and are not systematically atelic; some even test as telic with the za-frame adverbial test [START_REF] Mehlig | Aspektsemantik, Satzsemantik und Negation[END_REF]:

(20) a-My po-krasi-l-i zabor časa dva i se-l-i zavtrakat'

1PL po-paint.PFV-PST-3PL fence.ACC hours two and sit.PFV-PST-3PL for-breakfast "We painted (on) the fence for two hours and sat down to have breakfast."

b-My po-krasi-l-i zabor za dva časa.

1PL po-paint.PFV-PST-3PL fence.ACC in two hours "We painted the fence in two hours."

There's not a great distance between the delimitative in (20a), "painted on the fence" to a real resultative in (20b), "painted the fence". Many verbs show this semantic variability.

po-delim verbs do not necessarily indicate short duration

Many authors have noted that in fact they express indefinite duration. (Isačenko 1960[START_REF] Flier | The scope of prefixal delimitation in Russian[END_REF][START_REF] Dickey | Aspectual pairs, goal orientation and po-delimitatives in Russian[END_REF]. The short duration reading is usually inferred; it is easy to override the inference, as in the following example: In ( 21), we infer that the person smoked the whole cigar, because now he wants to throw away the stub and cannot find a trash can; the duration of the event would be the same if instead the natural perfective was used (vykuril sigaretu). This minimal pair shows that what is at stake with po-is not lexical telicity (presence of the event's inherent culmination), but rather terminativity: po-indicates that an entire episode of smoking took place, regardless of the final state of the (often unexpressed) affected object or of the duration of the episode.

Lexical restrictions

Although the number of imp roots that derive a po-pf verb is very large, they are subject to lexical restrictions having to do with the presence or absence of scales in the semantics of the base verb. From that perspective, po-is no different from the other preverbs that are also subject to constraints. This suggests that there is no reason to exclude po-from the class of purely perfectivizing or meaning-modifying preverbs. Change of state verbs illustrate a restriction of the use of vy-vs. po-perfectives [START_REF] Svetsinskaja | Le préverbe vy-en russe contemporain : étude sémantique et syntaxique[END_REF]. ( 22 The intransitive change of state verbs in (22a) do not accept po-verbs, because they denote an absolute change of state; vy-is a good candidate for these verbs precisely because it indicates that the undergoer (patient, theme) ends up in the state that corresponds to an ideal (abstract) model of what the bare root means: "completely dry, grown, ripe, healthy". Po-is possible, however, with the transitive change-of-state verbs in (22b): these roots denote a nonnecessary final state; po-is appropriate because it indicates a less than complete degree on the scale of treatment / drying / painting / washing, etc. Moreover, the degree achievements in (22c), which do not encode a final point, accept only a po-pf partner.

What po-delim verbs are.

Our discussion leads to the conclusion that po-delim verbs are a special case of terminative (telic) verbs. The type of bound they impose on the event is not an inherent one (the bound that the natural telos of the predicate entails), but an external type of bound. As has often been noted, po-imposes temporal definiteness. For [START_REF] Flier | The scope of prefixal delimitation in Russian[END_REF], a po-verb denotes relative change: it takes as input a homogeneous event (an atelic activity) and delimits it on the temporal axis. According to [START_REF] Mehlig | Glagol'nyj vid i vtoričnaja gomogenizacija oboznačaemoj situacii posredstvom kvantifikacii: k upotrebleniju delimitativnogo sposoba dejstvija v russkom jazyke ("Verbal aspect and the secondary homogeneization of a described situation by means of quantification: use of the delimitative Aktionsart in Russian"). In Semantika i struktura slavjanskogo vida (The Semantics and Structure of Russian Aspect)[END_REF], the role of po-verbs in aterminatives is to provide "external bounding" by focusing on a certain quantity of the homogeneous temporal continuum, that is, a limited period of its duration, so that the output is "arbitrary boundedness" of the event (262). For Sémon (1986), as well, contrary to other prefixed pf verbs, po-verbs do not describe the endpoint of action, but the amount of process that the speaker judges "congruent" (sufficient) in a given stretch of discourse. Finally, for [START_REF] Dickey | Aspectual pairs, goal orientation and po-delimitatives in Russian[END_REF], po-verbs identify a situation as unique in a sequence or a set of events. It is the reason why such verbs pass the temporal adverbial test of telicity proposed above.

Although full discussion of po-verbs would take us too far afield, there is a growing consensus that the language is changing, with po-delim verbs being often indistinguishable from normal po-pf verbs. In many cases, they perform the same function as a pure perfectivizer by placing the events in a narrative succession of non-overlapping situations; then they co-occur naturally with purely perfectivizing prefixed verbs:

(23) Eto ved ' tuda-sjuda-obratno, po-e-l, po-čita-l this is here-there-back, po-eat.PFV-PST.3SG , po-read.PFV-PST.3SG

i u-pa-l lico-m v podušk-u. Dickey notes the important grammatical function of the preverb po-in the aspectual system of Russian; it allows "the extension of the aspect opposition to atelic activity predicates … [it] allow[s] activity predicates to be sequenced in time on a par with telic predicates" (2006: 16). Without po-, the aspect opposition would "be restricted to accomplishment and achievement predicates", much as in Czech and Bulgarian, where aspect is more lexical (cf. [START_REF] Lakorczyk | Decomposing Slavic Aspect: the Role of Aspectual Morphology in Polish and other Slavic Languages[END_REF]. In sentence ( 23), the sequencing of the events in time invalidates the use of bare imp verbs; the pure perfectives (s'el, pročital) are not possible either because they would require the presence of a completely affected argument, which is not available. Po-thus fills an important grammatical role, akin to that played by lexical telicity with empty preverbs: the po-verb indicates "contingent" telicity, which we express by the general term of terminativity. For accomplishment and achievement predicates, terminativity translates into lexical telicity (attainment of the final point), whereas for activities and some state predicates, terminativity means contingent telicity, i.e. what Dickey calls the expression of "tangential consequences" for the event, as opposed to its natural consequence as expressed by the pure preverb in conjunction with a bare imp root.

As it is sometimes very difficult to draw the line between a po-delim and a normal po-pf partner verb, a careful corpus search would be necessary. In the following example, drawn from [START_REF] Dickey | Aspectual pairs, goal orientation and po-delimitatives in Russian[END_REF], the po-delim verb takes an accusative object, i.e. a "single referential object", a construal which is normally possible only with pure perfectivizers.

(24) Ja po-ši-l vsë, kak nado: štaniki, pidžačok, a soročečku iz nosovogo platka.

1SG po-sew.PFV-PST.1SG all as necessary "I sewed everything like it should be: little pants, a little jacket, and a little night shirt out of a handkerchief."

[example from Dickey 2006: 24] These facts lead Dickey to define an aspectual pair as "not a function of a dictionary, but a condition of mutual activation linking two verbs of opposing aspects at a given stage in the development of a discourse". (ibid.:33) In this section I have examined the puzzle posed by po-delim verbs, which often test as atelic in the za-frame adverbial test, yet yield positive results in other telicity tests, such as the time adverbial test. The former test probes for mereological telicity, that which covers the whole interval, including the beginning point and focusing on the endpoint: this explains why a sentence like on počital knigu čas, "he po-read the book for an hour", is possible. Po-picks an arbitrary temporal interval in the event and simply seals it off, which a specialized preverb (pro-in pročital knigu, "read the book through") does not do, as it fixes the natural bound for the event, by definition. The latter test (the time-adverbial test) probes for a relaxed notion of telicity, that which I call terminativity, which simply measures the end of an event: on that count, on počital knigu means "He read the book for a while and then he stopped reading." Following a number of authors, I also noted that the language is changing and that po-delim perfectives often behave as normal perfective telic partners of imp bare verbs, except for the attainment of the inherent culmination. I therefore proposed a more general definition of telicity for Russian, which I call terminativity, similar to the concept developed by Padučeva & Pentus, and Mehlig (2008). The advantage of this revised conception of telicity is that it provides a single function for all the preverbs, avoiding postulating a special case for podelimitatives, and na-cumulatives. It gives more flesh to the concept of perfectivity which, as will be demonstrated below, need not be ascribed to the expression of viewpoint aspect.

This will be the topic of the last section: if po-delim perfectives induce terminativity, wouldn't it be better to assume that alongside the telicizing role of preverbs, one must assign them another function, that of marking viewpoint aspect? And what is left of the preverb when the operation of secondary imperfectivization (SI) occurs? I turn to these topics in the concluding section.

Are preverbs telicizers or perfectivizers?

According to [START_REF] Smith | The Parameter of Aspect[END_REF], viewpoint aspect (outer aspect) establishes a relation between the assertion time (AT) and the event time (ET). If ET is included in AT, there is an external view of the situation seen as a whole, whatever its actual length; the situation is temporally bounded, producing the perfective viewpoint (PfV). If, on the other hand, AT is included in ET, there is an internal view of the situation; the situation is temporally unbounded, deriving the imperfective viewpoint (ImpV). VA aspect then composes with SA to yield different aspectual construals of situations: for atelic situations (Activities and States), application of the PfV yields events that merely terminate: For Accomplishments and Achievements, application of the same operator gives events that culminate:

(26) John read the book John finished reading the book [START_REF] Lakorczyk | Decomposing Slavic Aspect: the Role of Aspectual Morphology in Polish and other Slavic Languages[END_REF] uses a time adverbial test to avoid confusing atelicity and imperfectivity; only events with the PfV "can have an inclusive reading with respect to a time interval, i.e. they do not need to fill the whole time interval" (55), while events with ImpV can only have a durative reading:

(27) Between 2 and 3, John read a book (durative or inclusive) Between 2 and 3, John was reading a book (only durative)

In Russian, as already noted in the introduction, an imp verb normally produces an unbounded (view from within) interpretation [START_REF] Klein | A time-relational analysis of Russian aspect[END_REF]:

(28) Ivan čita-l knig-u (kogda my vo-š-l-i v komnat-u)
Ivan read.IPFV-PST.3SG book-ACC (when 1PL vo-go.PFV-PST-1PL in room-ACC)

"Ivan was reading a book when we entered the room."

Crucially, however it does not necessarily derive an ImpV reading, even in the presence of a temporal adverbial:

(29) "Čto ty dela-l včera c dvux do trëx.? "

What.ACC 2SG do.IPVF-PST.2SG yesterday from 2 to 3

"Čita-l knig-u, smotre-l televizor…"

read.IPFV-PST.1SG book-ACC, watch.IPFV-PST.1SG television.ACC "What did you do yesterday from 2 to 3? "I read a book, watched TV."

The normal way of asking about one's past (and bounded) activities is by using the imp verb, as in ( 29). This shows that the imp verb does not necessarily encode the ImpV. The verbs in (29) are most naturally translated as simple pasts in English, indicating that both bounds of the event are included in the assertion time. However, a pf verb always denotes a closed interpretation, i.e. it invariably produces the PfV. A useful test is to add the adverb uže, "already", to an imp or a pf verb, as in (30a-c).

(30) a-" Vot, ot-stuč-is' sejčas, Raisa Vasil'evna, prikaz." well, ot-type. In (30a-b), the combination of uže and the imp verb pisal is ambiguous between an ImpV (was already writing) and a PfV (have already written). However, (30c), with the prefixed pf verb napisal, has only a completive sense (have already written); it illustrates the PfV.

Clearly, it would be incorrect to assign the PfV aspect function to the preverb (e.g., na-in napisal), since the imp verb expresses the PfV just as well. I thus arrive at the same conclusion as [START_REF] Lakorczyk | Decomposing Slavic Aspect: the Role of Aspectual Morphology in Polish and other Slavic Languages[END_REF]: "Viewpoint aspect in languages such as Polish and Russian is marked by zero morphology."(90). VA is expressed in Russian by means of correlations or compositional restrictions such as the following:

Morphology of verb:

Situation type: Viewpoint type:

Base imp verb atelic perfective or imperfective viewpoint. Preverb + base imp verb telic perfective viewpoint.

In Russian, a base imp verb denotes an atelic eventuality which receives either a PfV or an ImpV reading. The addition of a preverb to the base imp verb makes it terminative/telic, deriving a PfV reading. We conclude that the preverb has a telicizing/terminative function. Therefore, it is SA that is grammaticized in Russian, not VA.

I will conclude this study with two arguments, which also apply to Polish [START_REF] Lakorczyk | Decomposing Slavic Aspect: the Role of Aspectual Morphology in Polish and other Slavic Languages[END_REF], to show that preverbs do not have a viewpoint aspect function (i.e., are not perfectivizers): 1) preverbs are found in forms that do not have to have PfV interpretation, namely, secondary imperfective (SI) forms; 2) preverbs do not have a VA interpretation at all in non-finite forms (nominals), where no temporality can be retrieved.

Secondary imperfectivization (SI) and preverbs.

SI is a regular morphological process whereby a prefixed pf verb derives its imp partner via a/-iva/-yva suffixation (or exceptionally, suppletion). Examples (3) and (4) are repeated as (31), with the SI formations added:

(31) base imp verb: bit', "beat, hit". a-prefixed perfectives: u-bit' (čeloveka), 'kill (a man)'; raz-bit' (stakan), 'break (a glass)'; pobit' (sobaku), 'beat a dog'; pro-bit' (dorogu), 'open up (road)'; za-bit' (trevogu), 'raise (the alarm)' b-secondary imperfectives: (4) u- bi-va-t; raz-bi-vat'; po-bi-vat'; pro-bi-vat'... u-STEM-2.IPFV-INF [START_REF] Filip | On accumulating and having it all. Perfectivity, prefixes and bare arguments[END_REF][START_REF] Filip | Events and maximalization: the case of telicity and perfectivity[END_REF] used SI as an argument for denying a telicizing function to the preverb, since the preverb remains in SI formations. The question is to determine the grammatical function of SI. The regular and inflectional-like nature of this process has led many authors (e.g., [START_REF] Zucchi | Incomplete events, intensionality and imperfective aspect[END_REF] to analyse it as a progressive operator, taking as input a culminated event (e.g., ubit') and yielding an imperfective event (ubivat'), much like the in English. The problem for that account is that a SI verb behaves exactly like a bare imp verb: it can denote either a progressive (32a) or a bounded event, as in (32b):

(32) a-Kogda ja pri-së-l, oni za-kaz-yva-l-i bljuda. (32b) illustrates a very frequent use of imp verbs in conversations, in which the addressee is reminded by the speaker of a fact that she should have been aware of; [START_REF] Forsyth | A Grammar of Aspect. Usage and Meaning in the Russian verb[END_REF] calls it the "statement of fact" convention; the SI suffix -yva is not a marker of ImpV. Rather it behaves like any other bare imperfective and can be temporally unbounded as well as bounded. I thus concur with Lakorcyk (2010) in analyzing the SI suffix as an atelicizer, which simply undoes the telicity of the preverb, but crucially not as a progressive (ImpV) operator.

Further confirmation of this function comes from the behavior of nominals.

Nominals

Deverbal nominals in Russian take an -'e/-'ë/-ie suffix, added to a verb stem regardless of its aspect and voice. The verb is pf and reflexive (with the suffix -sja) in (a), bare imp in (b), prefixed pf in (c), and bare imp in (d). Semantically, the deverbal nominal denotes a result in (a), a process in (c), a process or a result in (b), and more idiosyncratically, an entity in (d). The fact that an eventive nominal formed from an imp (33 b, d) as well as a pf (a, c) verb, is compatible with an imperfective construal, e.g. with the preposition pri, "during", as in (34 a-d), suggests that the eventive nominal simply lacks VA: "During the writing of new chapters he understood...

The choice between the pf or the imp base for deriving the nominal seems to depend on the absence vs. presence of an object, and/or the nature of the direct object (single referential object vs. generalized object). (34a) and (b) have a singular delimited (referential) object which requires a perfective base; (34c) and (d) create contexts which require the use of the imp base: there is no object in (c) -the activity of writing is focussed -while (d) has a plural object. Such facts suggest that it is not VA but SA that dictates the choice of the base form of a derived nominal, including presence/absence of a bound and focus on the process or the result.

This observation is confirmed by the interpretation of the nominalizations of SI verbs: these always denote atelic processes, never results, and do not introduce any temporal effects which would suggest a progressive VA interpretation: The data shown here indicate that SA alone is grammaticalized in Russian, and that the contribution of the preverb is limited to its Aktionsart function of marking telicity/terminativity. The role of SI is to undo the telicity inherent in the preverb + bare imp base.

CONCLUSION:

This paper has presented the complex data of verbal prefixation in Russian, and has assessed its role in the marking of situation and viewpoint aspect. It has defended the view that telicity is a robust functional feature which finds its grammatical exponent in the pure perfective preverbs. This view, defended by [START_REF] Borer | The Normal Course of Events[END_REF], and [START_REF] Lakorczyk | Decomposing Slavic Aspect: the Role of Aspectual Morphology in Polish and other Slavic Languages[END_REF] for Polish, is based on the generalization that a preverb invariably makes an imp atelic root telic. Concurrent models were examined, e.g. that of [START_REF] Filip | On accumulating and having it all. Perfectivity, prefixes and bare arguments[END_REF][START_REF] Filip | Events and maximalization: the case of telicity and perfectivity[END_REF], which seeks to retain the strong lexical (derivational) nature of the preverbs and deprives the preverb of a generalized telicizing function, preserving the classification into three types of preverbs. Instead, it was shown that there was a large overlap in the properties of the purely perfectivizing, the meaning-modifying and the superlexical preverbs: all yield telic readings, with the possible exception of po-delim pf verbs. It was further noted that even if the purely perfectivizing preverbs have grammaticalized to a large extent, they still retain part of their lexical substance and have not been replaced by a single empty prefix to do the job, confirming typological studies on the grammaticization of tense and aspect markers [START_REF] Bybee | The Evolution of Grammar -Tense, Aspect and Modality in the Languages of the World[END_REF]. It was also observed that both the superlexicals and the purely perfectivizing are subject to lexical constraints, just like the meaning-modifying preverbs.

In turn, the behavior of the superlexicals forced us to relax the exclusive definition of telicity found in the literature, viz. telicity as quantization. It was suggested that nonhomogeneity or non-divisiveness alone can support a telic reading. Following the model of [START_REF] Borer | The Normal Course of Events[END_REF], I endeavored to show that final telicity is just one case of telicity, with many other preverbs in Russian (na-, po-) encoding either non divisiveness or "post-state" telicity. Then, the behavior of po-delim verbs, which are currently extending their functional use in Russian, provided a further argument in favor of the relaxed view of telicity advocated above: even if po-delim verbs do not encode lexical telicity (i.e., presence of an inherent culmination in the verb's denotation), they mark terminativity, i.e. they encode a semantics of the end, which I called terminativity, following Paduceva &[START_REF] Padučeva | Formal and informal semantics of telicity[END_REF][START_REF] Mehlig | Aspect and bounded quantity complements in Russian[END_REF].

Finally, the data about po-delim verbs raised the question of the expression of viewpoint aspect: it was shown that both bare impf and secondary imp verbs, can give rise to an imperfective as well as a perfective viewpoint interpretation; however, pf verbs only yield a perfective viewpoint interpretation. With the observation that eventive nominals, derived from a pf or an imp verb, are deprived of any viewpoint construal, we were comforted in the conclusion already arrived at by [START_REF] Kiss | The Function and Syntax of the Verbal Particle[END_REF] for Hungarian, that it is situation aspect, not viewpoint aspect, that is grammaticized in Russian. The latter is merely inferred compositionally.

  Motor za-rabota-l motor za-work.PFV-PST.3SG "The motor started functioning" b-*Ivan se-l za stol i za-rabota-l Ivan sit.PFV-PST.3SG at table and za-work.PFV-PST.3SG

  still wet 1SG 3SG.ACC po-wash.PFV-PST.3SG (vy-wash.PFV-PST.3SG) "It is still wet, I washed it." b-On vy-stira-l pidžak i brjuki (…) a kogda vsë vy-sox-l-o, 3SG vy-wash.PFV-PST.3SG jacket and pants… and when all vy-dry.PFV-PST-

  polčasa Petia po-read.PFV-PST.3SG book-ACC for half-an-hour / in half-an-hour "Petia read (from) the book for half an hour / *in half an hour."

  ran once in two months b-*Kim ran in two months. (12) a-Kim loved Robin twice last summer. b-Kim loved Robin twice in three months. c-??Kim loved Robin in three months.

  ate meat on Monday and Tuesday (one or two events) b-Kim ate 300 grams of meat on Monday and Tuesday (two events) c-Kim ate more than enough meat on Monday and Tuesday (two events)[examples adaptedfrom Lakorczyk 2010:63]

  On kuri-l v ponedel'nik i vo vtornik (1 or 2 events) 3SG smoke.IPFV-PST.3SG on Monday and on Tuesday "He smoked on Monday and on Tuesday" b-On za-kuri-l v ponedel'nik i vo vtornik (2 events) 3SG za-smoke.PFV-PST.3SG on Monday and on Tuesday "He lit up a cigarette on Monday and on Tuesday." c-On po-kuri-l v ponedel'nik i vo vtornik (2 events) 3SG po-smoke.PFV-PST.3SG on Monday and on Tuesday "He smoked a bit on Monday and on Tuesday."

  Vanja pro-snu-l-sja vsego za 5 minut Vanja pro-wake.up.PFV-PST.3SG-REFL only in 5 minutes "Vania woke up in only 5 minutes." b-V 9 časov Vanja uže pro-snu-l-sja at 9 a.m. Vanja already pro-wake.up.PFV-PST.3SG-REFL "At 9 o'clock Vania was / had already woken up."

  Ja po-stira-l sviter v ponedel'nik i vo vtornik. (2 events) 1SG po-wash.PFV-PST.3SG sweater.ACC on Monday and on Tuesday

(

  ite, (…) vot ja id-u po ulice, po-kuri-l, say-IMP.2PL here 1SG walk.IPFV-PRS.1SG down street po-smoke.PFV-PST.1SG nado vy-kinu-t' okurok, a urny net ni odnoj." necessary vy-throw.away-INF butt but trashcan not a single"Tell me, here I am, walking down the street, I've just had a smoke, now I have to throw away the cigar butt and there's not a single trash can."

  and u-fall.down.PFV-PST.3SG face-INS in pillow-ACC "He was like, moving about here and there all the time, he ate first, read a bit, and fell crashing head first into the pillow."[Russian National Corpus]

  John read books #John finished reading books; John stopped reading books.

  .PFV-INF > na-write-NMLZ "to write" "writing, inscription" d-rva-t' > rva-n'ë tear.IPFV-INF > tear-NMLZ "to tear" "torn clothes"

  po-stro-eni-i model-i pri po-build-NMLZ-DAT model-GEN "during the construction of the model" b-pri na-pisa-ni-i roman-a pri na-write-NMLZ-DAT novel-GEN "during the writing of the novel" c-Eto očen' meša-et mne pri pisa-ni-i it.N much disturb-PRS.3SG me.DAT pri write-NMLZ-DAT "It disturbs me a lot during my writing." d-Pri pisa-ni-i nov-yx glav on ponja-l... , pri write-NMLZ-DAT new-GEN.PL chapter.GEN.PL 3SG understand.PFV-PST.3SG

  sound-GEN.PL on record.LOC.SG "the registration of sounds on a record" po-kaz-yva-nie kartin-ok po-show-2.IPFV-NMLZ painting-GEN.PL "the showing/display of paintings."

za-STEM -INF / za-STEM-2.IPFV-INF

	za-pet' / za-pe-va-t', "start singing"
	na-gulja -t '-sja	/ na-gul -iva -t' -sja, "walk to one's heart's content";

na-STEM-INF-REFL / na-STEM-2.IPFV-INF-REFL

	na-es-t'-sja / na-eda-t'-sja, "eat a lot".

cool.PF-PST.3SG

	19)
	a-Inchoation:
	po-exa-t',	po-ljubi-t'
	c-delimitative:
	po-kolo-l	drova		s polčasa i	ušël,
	'The coffee has cooled down a bit.'
	e-resultative:
	po-stroi-t'	dom,	, po-čini-t'	časy
	po-build.PFV-INF house.ACC po-fix.PFV-INF watch. ACC
	'build a house', 'fix a watch'.
	f-perfectivizing:
	po-duma-t',	po-rabota-t',	po-veri-t',	po-čuvstvova-t',

po-go.PFV-INF po-love.PFV-INF "set off", "fall in love" b-distributive-cumulative: po-ubi-va-l by vsex! po-kill.PF-DISTR-PST.3SG COND all.ACC.PL 'I'd kill them all one after the other!' po-chop.PFV-PST.3SG wood.ACC.PL half-an-hour and left 'He chopped at some wood for a half-hour and left' d-attenuative/limitative: kofe po-osty-l coffee.NOM popo-think.PFV-INF, po-work.PFV-INF, po-believe.PFV-INF, po-feel.PFV-INF

po-get.lean.PFV-INF po-get.old.PFV-INF

	)
	a-vy-soxnu-t', / vy-ras-ti,	/ vy-zre-t';	/ vy-zdorove-t',
	vy-dry.PFV-INF vy-grow.PFV-INF vy-mature.PFV-INF	vy-cure.PFV-INF
	'dry'	'grow (up)'	'come to maturation" 'get cured'
	*po-soxnu-t' /*po-ras-ti	/*po-zre-t'	/*po-zdorove-t'
	'treat (a patient)' 'dry'	'wash (clothes)' 'paint'	"shave"
				[examples from Svetsinskaja 1995: 170]
	c-po-xud-et'	/ po-stare-t',
	"lose weight',	"get old".

po-dry.PFV-INF po-grow.PFV-INF po-mature.PFV-INF po-cure.PFV-INF

b-vy-leči-t' / vy-suši-t' / vy-my-t' / vy-krasi-t', / vy-bri-t', vy-treat.PFV-INF vy-dry.PFV-INF vy-wash.PFV-INF vy-paint.PFV-INF vy-shave.PFV-INF 'cure (a patient)' 'dry(off)' 'wash (clothes)' 'paint' "shave" po-leči-t' / po-suši-t' / po-my-t' / po-krasi-t', / po-bri-t', po-treat.PFV-INF po-dry.PFV-INF po-wash.PFV-INF po-paint.PFV-INF po-shave.PFV-INF *vy-xud-et' / *vy-stare-t', vy-get.lean.PFV-INF vy-get.old.PFV-INF "lose weight', "get old".

Secondary imperfective suffixation will be glossed as "2.IPFV", as in the example provided.

3SG already sit.IPFV-PST.3SG and write.IPFV-PST.3SG