Christian Oko

Obinna

Nkechinyere Igbo

Elem

Igbo Michael Elem

Evaluation of Petro Physical Properties of the Reservoirs in XY Field Gulf of Mexico (GOM)

Keywords: Basin Morphology, Gulf of Mexico, Permeability, Porosity, Reservoir Sand, Shale Volume, Water Saturation, Well Logs. I

Evaluation of Petro Physical Properties of the Reservoirs in XY Field Gulf of Mexico (GOM)

INTRODUCTION

The study area, XY field Gulf of Mexico, is an ocean basin that lies between North American plate and the Yucatan block. Its depocenter consists of sediments that have been deposited in time from the Jurassic period through to the Holocene period with thickness of about 20km [START_REF] Ananev | Geology and petroleum potential of the Gulf of Mexico, Cuba[END_REF]. Sediments from the North American continent filled almost half of the basin, primarily by offlap of the northern margin and northwestern margin. The basin currently has an abyssal plain that lies at a depth of 3km [START_REF] Bryant | Physiographyandbathymetry[END_REF].

In the east, the Gulf floor is dominated by morphology akin to the Late Quaternary Mississippi fan while the northern Gulf margin shows a bathymetrically complex morphology that terminated abruptly in the Sigsbee escarpment in the west and merged into the Mississippi fan in the east [START_REF] Steffens | Quantitative bathymetric analyses of selected deep water siliclastic margins :receiving basin configurations for deep water fan systems[END_REF]. In the west, the Gulf margin shows intermediate width that is bathymetrically complex. In recent times, the shelf edge reflects a well-defined increase in basinward gradient lying generally at a depth of about 100-120 m. The northern, eastern and northwestern Gulf of Mexico is bounded by broad and low-gradient shelves with thickness that range from 100 to 300 km in the landward direction. Presently, the Florida and Yucatan platforms, which bound the Gulf basin on the east and south, persist as sites of carbonate deposition.

Onshore, the north and northwest Gulf margin shows broad coastal plain. At the lower coastal plain, Neogene and Quaternary strata underlies the flat and low-relief surface plain while the upper plain shows a modest relief that is less than 100m created by the incision of Quaternary strata into older Neogene, Paleogene, and Late Cretaceous strata through numerous small and large rivers. Various sediments from Cenozoic, Mesozoic, and remnant Paleozoic uplands which includes, the Lower Cretaceous limestone-capped Edwards Plateau, the Sierra Madre Oriental of Mexico, Ouachita Mountains of southern Arkansas, the Trans-Pecos mountains of West Texas, and the Cumberland Plateau and southern Appalachian Mountains of northern Mississippi and Alabama, bounds the Gulf basin [START_REF] Ettensohn | The Appalachian foreland basin in the eastern United States[END_REF].

The northeastern Gulf basin merged into the south Atlantic coastal plain across northern Florida with the structural basin boundary generally placed very close to the current west coast of the Florida peninsula [START_REF] Miall | The Sedimentary Basins of the United States and Canada: Sedimentary basins of the World[END_REF].

II. MATERIALS

Materials used for this research work includes PETREL software, TECHLOG software, ECLIPSE software and other research and training materials.

DATA INVENTORY

Summary of dataset used for the purpose of this research work is presented on table shown below;

Table 1. Data Inventory Table for the six wells of interest  WELL LOG DATA

All the wells had caliper (CILD), Sonic (DT), Gamma Ray (GR), resistivity (ILD), porosity (PHIT), spontaneous potential (SP), and clay volume (VCL). Four wells had fluid saturation (SFLU) and three wells had caliper (CAL), density porosity (DPHI), density (RHOB), density correction (DRHO), resistivity (ILM), neutron (NPHI).

 GEOLOGICAL SETTING

Gulf of Mexico Basin is ranked among the world's great petroleum mega-provinces, with hydrocarbon production history of more than 100 years. It is a rift basin located between North America and the Yucatan Block. The field is adjacent to the Caribbean Sea and surrounded by Eastern Mexico, Texas, the Southeastern Gulf States of the United States, and Cuba.

STRUCTURAL MODELING

A structural model is regarded as the skeleton or container of the subsurface. It is the geological model of the area otherwise called the Geomodel [START_REF] Ewing | Structural framework[END_REF]. To model any geologic subsurface, the modeler starts with a sound structural framework of the area which represents the relation between the faults and the seismic horizons showing the important layers of interest [START_REF] Schlumberger | Petrel property modeling[END_REF]. Structural modeling in Petrel involves Pillar Gridding, Fault Modeling, and Horizon picking (Layering).

Fault Modeling: The first step in fault modeling with petrel involves defining the faults of interest [START_REF] Adeeba | Reservoir Modeling with Petrel and Simulation run with FrontSim[END_REF]. This helps to define the shape of each fault that must be modeled. The process was achieved by generating "Key Pillars". Pillar Gridding: Pillar gridding involves making grids based on the already defined faults. In this stage, a set of pillars was inserted in between interpreted faults and in every corner of the grids in the entire project area. The result of this process is a "Skeleton grid", defined by all the faults and all the pillars. Layering: After the fault modeling and the pillar gridding process, horizons were inserted into the faulted 3D grid. The 3D grid was converted to time/depth by associating it with time/depth maps and well tops. After inserting the horizons, the zones of interest (based on geological input such as isochors) were inserted, and the final step was to make fine-scale layerings suitable for property modeling.

Figure 3. Fault and Horizon structural frameworks

 Property Modeling

Property modeling involves filling the 3D grid cells with discrete/continuous properties. The goal is to achieve a realistic property model by using all geological information available to build the model [START_REF] Schlumberger | Petrel property modeling course[END_REF]. The Property modeling of the field was done with Petrel software and the process was split into three steps:

Geometrical modeling: This involves using some predefined functions to generate properties such as Bulk Volume, Depth, Height above Contact, and more [START_REF] Ajeet | Seismic Velocity Model Buildin: An aid for better understanding of subsurface-A case study from Cambay Basin, India[END_REF]. These properties are very important in volumetric evaluations and in mathematical operations between petrophysical properties (e.g. for Sw transforms).

Facies modeling: This involved the population of discrete data such as lithofacies, into 3D grid cells. This helps to give true understanding of the geological processes, and to capture facies architectures like reservoir connectivity, high level of heterogeneity and to confirm descriptive facies information such as shape, size, orientation, proportion, distribution and statistics. RESULTS AND DISSCUSSIONS

Petrophysical Evaluation

Petrophysical evaluation carried out on the measured log using the resistivity (ILD), gamma ray (GR), and crossplot of neutron (NPHI) and density (RHOB) logs indicated the presence of hydrocarbon within intervals of high resistivity and neutron density crossovers. This is the case in the two control wells, Agate and Diamond wells as can be seen in figure 8, below. Due to lack of neutron and density logs on wells Apatite, Calcite, Copper and Jasper, conclusions could not be made on the presence of hydrocarbons on the different reservoir intervals.

Average porosity across the reservoirs is 0.30 -0.40. Kobe reservoir contains gas while the other reservoir contains oil.

Figure 8. Result showing reservoirs of interest and hydrocarbon type throughout the column of well Agate

Petrophysical Properties

Shale Volumes (Vsh) were computed using gamma ray log; the reservoir versus non-reservoir was delineated by applying cut-off of 80% computed volume of shale with the guide of spontaneous potential (SP) and deep resistivity logs for wells Agate and Diamond. Computed Vsh was used to effective porosity to discount for the effects of clay bound water. The average porosity values ranged from 15 -35% and 10 -30%, Permeability averages of about 43mD -75mD and 45mD -118mD, and water saturation values averaging from 14.7% -76.6% and 13.8% -82% were gotten across the reservoirs in wells Agate and Diamond respectively.

Figure 9. Result of the shale volume and effective porosity curves generated for well Agate

Figure 1 .

 1 Figure 1. Physiographic elements of the Gulf basin, showing adjacent North America. The white outline shows approximate geological limits of the basin.  WELL LOCATION The six wells of interest are located on the Texas-Louisiana shelf. The shelf has a thickness of about 100km off the Rio Grande in Texas and more than 200km in the southern part of Texas-Louisiana boundary. Large amounts

Figure 2 .

 2 Figure 2. (a) Showing the wells location in the GoM (b) Showing enlarged view of the wells in the study location. (C) Showing wells location on a 2D Petrel windowIII. METHODAn integrated approach was applied in this study. The knowledge from the various subsurface disciplines was employed to develop 3D Reservoir Model of the field with the help of Schlumberger Oilfield Services Software (PETREL, TECHLOG AND ECLIPSE) in Portharcourt. Interdisciplinary reviews and interpretations were provided at each milestone of this project to ensure consistency in the geological, geophysical and reservoir engineering concepts of the study.The processes employed in the study include:  Data load, QA/QC, and data conditioning  Sonic log calibration (TDR generation)  Synthetic generation  Well-to-seismic tie  Seismic interpretation (fault and horizon interpretation)  Generating surfaces for the reservoirs of interest  Velocity modeling  Time to Depth conversion  Structural modeling of faults and horizons  3D grid model building (static), zoning and layering of the grids  Property modeling  Data analysis

Figure 4 .Figure 5 .

 45 Figure 4. Pillar grid fault framework

ISSN

  This involves the interpolation and simulation of continuous data such as porosity, permeability and saturation into the 3D grid cells[START_REF] Schlumberger | Petrel Advanced property modeling, training and exercise[END_REF]. The petrophysical properties vary from facies to facies i.e. different petrophysical property distributions in different facies with spatial variations for each petrophysical parameter.

Figure 6 .

 6 Figure 6. 3D Grid showing (A) facies distribution and (B) Porosity distribution  Model UpscalingModel upscaling involves merging the fine cells of the 3D Grid to obtain a coarse model while still preserving the geologic features important to the reservoir flow dynamic. For this study a 4:1 flow-based upscale was performed to

Figure 7 .

 7 Figure 7. Showing fine scale and coarse scale 3D grid geomodel IV.RESULTS AND DISSCUSSIONS

V. CONCLUSION

In conclusion, this research work evaluated the petrophysical properties of the reservoir sand bodies of XY field Gulf of mexico (GOM). Six wells of interest were picked for this study. Existing seismic, together with available well logs were interpreted. Thus, the Horizons (layer tops) representing the six reservoirs of interest were picked while faults were interpreted to define the storage container boundaries. Structural and petrophysical analysis of the field was done and the results from the study shows that the average porosity values of the field ranged from 15% -35% and 10% -30% in wells Agate and Diamond Permeability values of 43mD -75mD and 45mD -118mD, and water saturation values averaging from 14.7% -76.6% and 13.8% -82% were gotten across the reservoirs in wells Agate and Diamond respectively.

Due to lack of neutron and density logs on wells Apatite, Calcite, Copper and Jasper, conclusion could not be made on the petrophysical properties of the wells on the different reservoirs intervals.


Son-Hai Ha
email: sonhai.ha@orange.com

Patrick Brown
email: patrick.brown@orange.com

Pietro Michiardi
email: pietro.michiardi@eurecom.fr

Resource Management for Parallel Processing Frameworks with Load Awareness at Worker Side

Keywords: big data, cloud computing, resource usage slack, scheduling, feedback

Many resource management systems and large-scale data processing frameworks use a reservation-based model for managing resources and scheduling tasks. We observe from the reported traces of Facebook and Google that this model leads to resource being wasted because the tasks do not use effectively the allocated resources. We confirm the problem with a trace of our production cluster. We propose an algorithm to estimate the resource usage at worker nodes. This estimation is used as an input for the scheduler at the resource manager. We verify the stability of the new system in a simulator and develop a prototype of this approach for YARN. Our results in the simulator show that the new model can flexibly match the actual demand of the workload to the capacity of the cluster avoiding resources over-reserved by users. Comparing the worst scenario of our management model and the best scenario of the reservation model, we obtain almost the same performance and comparable system stability. In practice, our prototype for YARN completes jobs faster from 23% to 44%.

I. INTRODUCTION

To analyze large datasets, it has become typical to use clusters of machines to execute jobs consisting of many tasks. The types of computations people run have diversified from MapReduce batch jobs to a very rich type of jobs, including interactive analytics, stream and graph processing, iterative machine learning, MPI-style computations, and complex pipelines. Recent resource management systems such as Mesos [START_REF] Hindman | Mesos: A platform for fine-grained resource sharing in the data center[END_REF], Omega [START_REF] Schwarzkopf | Omega: flexible, scalable schedulers for large compute clusters[END_REF], Hadoop YARN [START_REF] Vavilapalli | Apache hadoop yarn: Yet another resource negotiator[END_REF], Kubernetes [START_REF] Rensin | Kubernetes-scheduling the future at cloud scale[END_REF], and Corona [START_REF] Facebook | Scheduling MapReduce jobs more efficiently with Corona[END_REF] are popular frameworks to run these workloads.

We observe that these cluster management frameworks use reservation-based model for scheduling tasks. However, from our trace and from data of different studies [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of heterogeneous resources in datacenters[END_REF], [START_REF] Grandl | Multi-resource packing for cluster schedulers[END_REF], [START_REF] Reiss | Heterogeneity and dynamicity of clouds at scale: Google trace analysis[END_REF], we see that this model is not an optimal choice for scheduling since it leads to resource being wasted. A reservation-based model uses a resource vector ă resourceA, resourceB, ... ą to describe the resource demand of task. The resource management system reserves a resource segment on its managed nodes with fundamental requirement: resource demand cannot exceed the capacity that the node can provide at the time. In practice, there are also other parameters for a scheduler to place a task on a node such as data-locality, fairness,... In this paper we focus on the resource demand vector and the node capacity when considering a location for placing task. The reservation model assumes that users know in advance the resource that their jobs need, but in practice jobs at different phases have different resource demands; different tasks in the same phase may also have different resource demands; and even the same tasks at different moments require different type of resources.

A static resource configuration for a job or for a task is not an optimal approach.

Our motivation is to enhance the existing resource management infrastructures by scheduling tasks with the reference to the current utilization at each worker node in the cluster. In the reservation model, a popular approach is to learn the workload resource in advance to determine the optimized reservation of each jobs [START_REF] Grandl | Multi-resource packing for cluster schedulers[END_REF], [START_REF] Rasley | Efficient queue management for cluster scheduling[END_REF]. Another is to over-commit server resources to cope with the variability of workload resource usage [START_REF] Verma | Large-scale cluster management at google with borg[END_REF]. While the former needs to accurately track resource usage of identical or similar workloads in advance, the latter consists in allocating applications more server resources than the servers can actually provide. This reduces system stability during peak time and requires detailed observation on the workloads.

In this paper, we introduce a method to estimate the resource usage on worker nodes and determine the available resource that we can use for placing tasks for the parallel processing frameworks without sacrificing the system stability and without the necessity to learn exactly the resource consumption of each job in the workload in advance.

With the new approach, we prove that there is a better way to manage the cluster resources for parallel processing frameworks. When we apply this approach to the real systemin our case Hadoop YARN -we show that cluster performance improves. Using Hive Testbench [START_REF] Shanklin | Testbench for Apache Hive at any data scale[END_REF], which is a standard large scale system benchmarking for Hive, we observe jobs complete 23% -44% faster in average.

In addition, we provide a tracing tool1 to track the cluster utilization on YARN, which can study various workloads and learn job resource demand. We also introduce a simulator to simulate the system and replay trace with information on real usage of jobs, enabling new ideas for scheduling or to study the response of different monitoring parameters when running production workloads. We also present a prototype implementation2 of the proposed method for YARN which considers the current resource utilization at node for scheduling, to improve the job performance.

In section III, we present our problem statement which is verified by our tracing tool on a production cluster at Orange (France Telecom). We propose a new algorithm to improve resource usage efficiency in section IV and then develop a simulator to replay the trace and to verify the stability of our approach in section V. In section VI, we show how our prototype performs on a YARN cluster. Even though we only apply these ideas to YARN -a Hadoop resource management system, we believe that our approach can be applied to other distributed platforms as well.

II. RELATED WORKS

Cluster are generally under-utilized because of either resource usage slack or allocation slack. The resource usage slack represents the resource that is allocated to jobs but not used by jobs. In some contexts, this is also called overallocation. The allocation slack is the available resource that is not allocated because of some system constraints or because of a lightweight workload.

In order to increase resource utilization, jobs and tasks are profiled to study resource demands or to estimate jobs and tasks runtime. So that identical jobs can be scheduled more efficiently [START_REF] Rasley | Efficient queue management for cluster scheduling[END_REF], [START_REF] Delgado | Hawk: Hybrid datacenter scheduling[END_REF], [START_REF] Delgado | Eagle: A better hybrid data center scheduler[END_REF], [START_REF] Curino | Reservation-based scheduling: If you're late don't blame us![END_REF] or tasks are placed on node more optimized [START_REF] Grandl | Multi-resource packing for cluster schedulers[END_REF]. The authors in [START_REF] Grandl | Multi-resource packing for cluster schedulers[END_REF] state that the current scheduling algorithms which are only based on one or two types of resource (memory and CPU) are not optimal. They introduces Tetris which schedules jobs based on the 4 kinds of task demand: disk, network, CPU, and memory. Tasks are profiled on resource demands and packed on worker node to optimize for job makespan, solve the resource fragmentation and over-allocation problem. For makespan, they reduce 29% comparing to the Capacity Scheduler and 27.5% comparing to the Dominant Resource FairShare scheduler [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of heterogeneous resources in datacenters[END_REF]. In [START_REF] Curino | Reservation-based scheduling: If you're late don't blame us![END_REF] Curino et al. claim that the lack of predictability and time-awareness is the key limitation for modern frameworks. With Rayon, they attempt to increase the utilization of the cluster by providing a declarative resource demand language (RDL) so that job submitters can declare all of their demands at submission time. By using a global view on the resource needs of all jobs, the cluster management system can reserve resources ahead and ensure predictable resource-allocation for production jobs and also minimal latency for best-effort jobs.

Another approach is resource over-subscription. While static over-subscription enables conservative and predictable oversubscription, dynamic over-subscriptions shown to make oversubscription more robust and precise for utilizing the actual slack resources. Dynamic over-subscription has been deployed in Borg [START_REF] Verma | Large-scale cluster management at google with borg[END_REF] and Mesos [START_REF] Nielsen | Turbocharging your Mesos cluster with oversubscription[END_REF]. Borg [START_REF] Verma | Large-scale cluster management at google with borg[END_REF] gives the tasks a fixed amount of resources in the beginning and slowly reduces the task reservations to the actual usage with a safety margin. The reduced amount is advertised as free resource and allowed for other jobs to use. They claim that the reclaimed resources can be used for 20% more of workload while the system stability is maintained. Mesos takes similar approach but only reclaims resources from best-effort workloads. While Borg and Mesos manage the prediction for reservation per task, we estimate the resource usage per node.

III. PROBLEM STATEMENT

In one study of Google [START_REF] Reiss | Heterogeneity and dynamicity of clouds at scale: Google trace analysis[END_REF], we see that even if cluster resource are fully allocated to jobs or applications, the real resource utilization is around 40 to 50% of the allocated one. Another study on Facebook MapReduce workload trace [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of heterogeneous resources in datacenters[END_REF] shows that resource is allocated to job but jobs cannot use all of them. We claim that the problem happens because of the reservation model.

A. Tracing tool

To analyse the efficiency of the reservation/allocation model in the context of YARN, we develop a light-weight application that keeps track of the cluster utilization at our production cluster including CPU, memory, storage I/O, and network I/O. The profiling service is composed of an observer and several trackers. A tracker is installed at each worker node. It polls the NodeManager to know if there are containers assigned to the NodeManager and tracks the resources used by such containers during their execution. A container in YARN is a Java process that runs the task. Resource used by these Java processes is limited by the user's reservation. The profiling service logs the CPU utilization, memory usage, network I/O, and disk I/O during the container lifetime. After the containers complete their tasks, these logs are sent to a collected node which also runs the observer. The observer polls the YARN Timeline Server, which is a logging service of YARN, to track the creation and completion of new jobs. When there is new job finished on the cluster, the observer collects the job information and the container metadata, acquires the logs of the containers running the tasks, and merges them with the resource utilization which is produced by the tracker. The merged information is stored in JSON format for analyzing.

B. Cluster Resource Usage

The cluster has 3 master nodes which are installed with master services and 6 worker nodes to run the tasks. Nodes in this cluster have 24 cores and 64GBs of memory. YARN is configured to used 144 cores and 324GBs of memory for container allocation and execution. Job types are varied from interactive jobs to batch jobs but the majority of them are short batch jobs. Users submit jobs through hive, pig, oozie, and Spark. We perform our profiling service during one week and log around 8000 jobs in which there are 110000 containers.

We define the allocation efficiency as the ratio of total resource used to the resource allocated for container during its lifetime. E c " ř n i"0 u i ř n i"0 r i where -E c is the allocation efficiency of the container c n is the duration of the container u i is the resource used at time i r i is the resource reserved at time i Figure 1 shows the cumulative distribution of the allocation efficiency. We present the container, job, and user allocation efficiency. Container allocation efficiency is the ratio of the total resource used and the total resource allocated to a container. Job is a group of containers. Job allocation efficiency is the ratio between the total resource used and the total resource allocated by all containers that belong to the jobs. Similarly, user executes multiple jobs on a cluster. We define the user allocation efficiency as the ratio of the total resource used and the total resource allocated by all containers that belong to all the user's jobs.

Concerning CPU usage, 60% of the containers use less than their allocation. However, they can use the resource upto 2 times their allocation. CPU over-utilization in some jobs can be explained by two reasons. i) The default setting of YARN ii) The majority of our observed jobs are short duration batch jobs which are CPU hungry [START_REF] Shi | Clash of the titans: Mapreduce vs. spark for large scale data analytics[END_REF]. We believe when the cluster has more interactive jobs which requires user input with long idle time, or when the cluster was configured with cgroups for CPU isolation, resource usage slack will appear clearer.

Concerning memory usage, each container's memory is isolated inside each JVM. YARN is able to control the memory that a container uses. 90% of the containers use less than 50% of the memory that is reserved. 90% of the applications use less than 24% of the memory that they reserve. 90% of the users use less than 35% of the memory that they reserves. This may be a result of bad configuration. For example, we see that all the containers that run the application masters only occupy at most 35% of the memory. Our first question is if there is a way to avoid this mis-configuration? Mappers and Reducers do not have the same load, so there is no common size for memory that they need. Our second question is that if we can find a dynamic value to represent the reservation of mappers and reducers? We present our approach to answer these questions in section IV.

Our results indicate that we need a better way to allocate the resource on the cluster and preferably an automatic way which does not require human intervention and tunning. If the scheduler is aware of the actual load on each worker node, it can decide to push more container to that node without hurting the performance of other containers running on the same node. Increasing concurrency level of job can reduce job makespan. This is the seed for our idea in the next section.

IV. ESTIMATION-BASED SCHEDULING

Nodes in a cluster generally do not have the same load simultaneously. Reservation-based scheduling treating all nodes as the same is clearly not optimal. Scheduling based on real utilization at worker nodes (WNs) can be an alternative way to effectively utilize the resources. It allows the system to dynamically adapt to the current state of each WN in the whole cluster. However, as we have learned so far, tasks and resources allocation cannot only be based on real resource utilization. We take two examples, one with memory and one with CPU. Task needs a few seconds to load data to memory, or longer if data is retrieved remotely via the network. Scheduling based on the instant value of memory utilization may lead us to assign too many tasks because some of the tasks are at the start-up time. Similarly, the CPU utilization varies erratically during job execution time. If we consider only the instant load of the CPU which can be a short decline at peak time, we may assign too many tasks to a heavy loaded node which will introduce the costly context switching.

To get the advantages of both paradigms (reservation and real usage), we propose a mechanism which takes into account both the reservation and the real utilization at node. The main idea is doing an estimation on the resource that the task can use by i) taking the reference on the actual usage at WNs by averaging (eq. 1), this averaging method also prevents the estimation to vary too fast and with high amplitude, ii) preparing for the low usage of the resource at the start-up time of the tasks (eq. 2) iii) correcting the estimation when it goes wrong because of sudden utilization spikes (eq. [START_REF] Vavilapalli | Apache hadoop yarn: Yet another resource negotiator[END_REF].

Assume that we have a cluster with one resource manager (RM) and several worker nodes for executing the tasks. Denote by U Rpnq , the utilization of resource R measured at time n and sent by a worker node to the RM. We assume the time is discretized. The nodes of the cluster periodically send to the RM the current level of utilization of the resources. The resource manager updates its estimate, E UR pnq , of the resource R with the measurement U Rpnq sent by the node to which R is attached, and its previous estimate, E UR pn´1q , with an averaging formula:

E UR pnq " p1 ´αqE UR pn´1q `αU Rpnq (1)
where α is a damping factor. As an important advantage compared to today's RM solutions, this method allows adjusting the estimate of the level of utilization of resource R with a correcting factor composed of the measured utilization level at the node. This allows for the RM to allocate supplementary jobs if the utilization level is lower than the reservation, or on the contrary to avoid allocating more jobs if the utilization level is too high.

Denote by RR J the resource requirement for a resource of the same type as resource R declared by a job J. When the RM decides to allocate RR J of resource R to job J at time n, the RM instantly updates the current value of its estimate of that resource usage, E UR pnq , in the following way:

E UR pnq Ð Ý E UR pnq `RR J
(2) This allows for the RM to allocate at least as many jobs using R as it would basing only on reserved resources. The RM can take instant decisions without having to wait to "learn" how much resource the job will effectively use. So equations 1 and 2 allow simultaneously to "learn" how much resources the jobs are using by taking into account the resource usage measurements (cf. equation 1) and to take instantly into account the resource requested reservation (cf. equation 2). A user submitting a job may now not worry about a precise estimation of the resources that her job will consume. A resource requirement for her job are only used as a gross estimate to know if there is enough space for it to run. Even if it is overestimated or mis-configured, the update performed by equation 1 will allow the over-estimated resources to not be blocked indefinitely until the job stops. If we apply these to the cases where jobs are idle in an intermittent manner such as interactive jobs waiting for user inputs, or real time services at low load moment, the blocked resources by user's reservation can be reclaimed for other jobs during these idle periods.

The current resource usage at a node may increase suddenly due to external load by other applications, by a sudden input from user of interactive jobs, or by the arriving at peak time of data processed by real time services. We correct the resource estimation with equation 3 to prevent later scheduling decision overloading the node.

E UR pnq " U Rpnq if E UR pnq ă U Rpnq
(3) The damping factor can control how fast the estimation adapts to the real utilization at the node. When the damping factor is too small, it takes long time for the estimation to converge to the real utilization and leave resource wasted. Let n J be the execution time of task J, we apply equation 4 when task J finishes to remove the residual estimation for task J from the estimation for the node.

E UR pnq Ð Ý E UR pnq ´p1 ´αq nJ RR J (4) V. EVALUATION ON SIMULATOR
To study the performance of the new scheduling model, we develop a simulator to replay the trace that we collected with our profiling tool. The simulator simulates a cluster with many nodes. Each node is defined with a number of cores and an amount of memory. When assigning a task to a node, the simulator priories the node that has more resources. Input tasks are parsed from the trace that we analyzed in section III. They are queued to run in FIFO order based on the creation time.

We classified resources into two different types: compressible and non-compressible resources. Compressible resources are rate-based like processing power, network I/O bandwidth, and disk I/O bandwidth. If these resources are overloaded, the task will not crash but slow down. In our simulator, when all the tasks demand the CPU resource more than the capacity of the node, some of the tasks will be served only a part of their demands, the remains will be served in the next second. This is to simulate the context switching penalty.

On the other hand, non-compressible ones are like memory or disk space which will cause the task to crash if it is over-used. If the crashed task is an important task like the application master in YARN which manages the whole job or a critical task in the middle of a complex data flow, the penalty of crashing is worse. In our simulator, when memory demanded reaches the node capacity, all the demanding task will break and send back to the scheduler for later execution. Our simulator treats all tasks equally so there is no dependence between tasks. Therefore, if one task fails, only that task will be re-scheduled.

A. Avoiding the reservation bottleneck

The goal of our first experiment is to show if the new model can avoid resource wastage because of user over-demand and avoid the reservation bottleneck. In this experiment, the simulated cluster composes of 8 worker nodes. Each node is set with 32 GBs of memory and 24 cores. In each node, 28 GBs of memory and 18 cores are configured for the parallel processing framework to use. The workload are parsed from a one-day trace on our production cluster which contains about 18000 Figure 2 shows the utilization for the whole cluster which is a summation of all node at the same point in time. In the legends, the capacity is the total capacity of the cluster. The allowance is the desired maximum utilization that we would like to have. In the reservation model, the allowance is the configured node capacity that the administrator configures at each node. The estimation is our current estimation on the resource usage of the cluster. The gap between the allowance and the estimation is the available resources that we can allocate tasks. The gap between the allowance and the capacity can be used as a safety margin for our estimation algorithm since sometimes the estimation and the real utilization can exceed the allowance and cause tasks to break. The reservation is the total resource reserved by all executing tasks at the current time. The reservation model allocates tasks based on the reservation while the estimation model allocates them based on the current estimation.

We show 16% faster completion times of all tasks in the trace when our estimation algorithm is applied. The top strip shows that the reservation model gets bottleneck because users over-demand for memory resource. With the traditional reservation scheduling, even if we always have tasks to execute, the node will only use around 50% of the available memory. This leads to longer time to finish the workload. With the estimation algorithm (the bottom strip in the two figures), the system learns the resource usage by the workload and automatically shift the bottleneck from memory resource to CPU resource which the best response that the system should have. We observe that there is zero task failed because of the memory consumption in the test.

B. Avoiding memory saturation

Because of the resource usage slack, our scheduling model likely assigns more concurrent tasks to the node than the reservation model. If disk swapping is disabled, tasks will crash when the memory of the system saturates. We would like to confirm the response of our scheduling model when memory is the main constraint on the cluster.

To simulate the case where memory is the bottleneck, we create one simulated cluster with eight slave nodes. Each node has 32 GBs of memory and 64 cores. Nodes were configured to allow the utilization of memory to go up to 28 GBs, and of CPU to go up to 58 cores when executing tasks. Note that one core and one GB of memory are assigned by default to the OS and the other applications.

We replay also the trace of one day of our production cluster. The task durations fall in between several seconds and 1000 seconds, but the majority of them have duration from 10 to 100 seconds. In this experiment, we assume that users know in advance the memory that their task needs. So the resource reservation for each task is the exact maximum memory and CPU used. This setting is called Extreme Fit Reservation. To implement this setting, we replace the old reservation value of the memory in the trace with the maximum memory used by the task. This setting is the ideal case for the reservation model because: i) it minimizes the resource usage slack so all the tasks will complete fastest. ii) it guaranties that, at any moment, the total consumption of memory of all tasks will not be higher than the allowance. Therefore there is no task failed because of insufficient memory and every task has its resource ready for use. However, applying this workload to our estimation algorithm will place it in the worst situation to avoid memory saturation and container crashes.

Figure 3 is our simulation results where the top strip is for the reservation model, and the bottom strip is for the estimation model. We select damping factor of 0.125 (see the next section for a discussion on the sensitivity of the damping factor). Even though this is an ideal scenario for the reservation model and our estimation model in its most disadvantaged scenario, the performance of the two models is almost similar. Through several test runs, we observe a failure rate of 0,37% (or 64/17385 failed tasks) which does not impact the job performance.

C. Damping Factor Sensitivity

The only parameter in our algorithm is the damping factor in equation 1. The damping factor controls how fast the estimation adapts to the real utilization at worker nodes. The damping factor has an impact on the stability of the system.

When the damping factor is zero, our model acts like a reservation model which is the most stable but also more resource wasted. When it is one, the system depends only on the current load at the worker nodes, which wastes less resource but is also less stable.

We define the stability of the system as the failure count of the executed tasks (assuming disk swapping is isolated). Large clusters focus on resource isolation to keep system stability, while small clusters often squeeze for every bit of performance from the hardware. The reason for reservation model to be popular in many resource management systems is that it is simple and it provides resource isolation protection for tasks. That means job j reserves an amount of resource r for task t, that resource r will be kept until task t finishes. The best scenario happens when users know in advance the demand of theirs tasks. This is why there are two approaches to improve resource utilization for reservation model: i) learn the exact demand of tasks so that in later runs the system can prepare resource better or the user can reserve better. The benefit of this method is that the stability of the system is preserved because the total consumption of resource never exceeds the capacity of the system. However it requires to learn the resource usage of identical tasks. Even though it is proved that this method can improve the performance [START_REF] Grandl | Multi-resource packing for cluster schedulers[END_REF], applying the resource usage learnt from identical tasks to different data may result in different resource usage, which may give unexpected performance. ii) over-subscribe the cluster. The benefit of this method is that it just needs the administrators to observe the global load of cluster and configure the resource and the workload to best fit their cluster. This requires human intervention some stability studies for the workload (like borg [START_REF] Verma | Large-scale cluster management at google with borg[END_REF] has done to choose safety margin when doing resource reclaiming for over-subscribing).

We repeat the experiment in V-B with different settings for the damping factor to study the stability of the system. We compare the impact of the damping factor for the test case with the Resource Requested by Users (RRU) and for the test case with Extreme Fit Reservation (EFR). In figure 4 we presents the fraction of crashed tasks to the total submitted tasks and the completion times of the workloads for different damping factors. For EFR, failure count starts to raise when damping factor is 0.1 while it does so for RRU when the damping factor is 0.175. We observe that completion times for the workloads on the system decrease until the damping factor reaches 0.3 (and stay constant after) even though we have more crashed tasks and we have to re-schedule them. Note that in our simulator as with Map and Reduce tasks, tasks are not depended on each other so a failed task will not cause other tasks to fail. However, in practice, tasks may have dependency and the penalty of task crashing can be critical. It is preferable to select the damping factor with low value. We care for system stability so we select the damping factor of 0.125 for all of our tests in the simulator and in the real implementation.

VI. EVALUATION ON REAL SYSTEM

We implement our solution for YARN as a prototype to study the performance that we can get in practice. In YARN, the term container often means a task or a group of tasks executed inside a Java Virtual Machine (JVM). When discussing about the container, we means the task or the process that run inside the JVM. In this paper, we only consider the case of one task per JVM. Figure 5 indicates the parameters that we consider when allocating resource to node. While the original YARN only takes into account the allowance (the static resource capacity of node configured by administrators) and the current allocation (total reservation by all users), we consider also the real capability of the node, the current node utilization and the aggregated utilization of all containers. The node utilization is the current utilization of all applications and OS on the whole node. The aggregated container utilization is the total resource utilized by only the YARN containers.

Described in figure 6 is our prototype for YARN. At node registering process, worker nodes report to the Resource Manager their real resource capacity together with the configured capacity set by administrators which we call the "allowance". A resource monitoring service is added to track the resource usage of node. This service can run the estimation described in section IV at a worker node to shift the overhead from the Resource Manager RM to the NodeManager (NM). Running the estimation at worker side will introduce a small amount of allocating latency at maximum of two heartbeats due to RM waiting for the resource update from NM. Running the estimation at master side increases the heartbeat processing time which is critical for big clusters with thousands of nodes. For small clusters, we prefer to calculate at the master side, while for big clusters, we prefer doing it at worker side. The dash line is the feedback flow when we run the estimation at Finding the available memory of the system is a delicate task. Memory in Linux is managed by pages and each application has a virtual memory space which has each page mapped to another page in the physical memory space. Because of the optimization of the OS, the unused memory can be used for page caching to increase application performance and the system will dump the inactive page cache if needed to satisfy allocation requests. Therefore the free memory reported in /proc/meminfo file is alway low. It is not a good measure for the available memory because not all cache is needed and useful for improving application performance. Recent Linux kernels built from 2016 provide an estimation on how much memory is available for starting new applications without pushing the system into swap. This is a good estimation of the space available for containers. However, this information is not available in older kernels. For those kernels, we estimate the available memory by the free memory size and half of the inactive page size.

We extend the heartbeat content of NM to include the node utilization and the aggregated utilization of current containers. These heartbeats are sent to RM every second or few seconds depending on the size of the cluster. Upon receiving the heartbeat, the RM calculates the availability of the resources of each node as follow (see figure 5):

Denote by AR the allowed resource on node A. AR is the desired level of utilization that we would like node A to achieve when executing tasks on that node. Let ACU be the current aggregated resource utilization of all tasks executed on node A. We define the available configured resource by: available_conf igured_resource " AR ´ACU [START_REF] Facebook | Scheduling MapReduce jobs more efficiently with Corona[END_REF] Denote by RU the Resource Usage Estimation that we calculated by applying the algorithm on section IV and by NC the capacity of the node. We find the available node resource by: available_node_resource " NC ´RU [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of heterogeneous resources in datacenters[END_REF] The available resource is the min() of eq. 5 and eq. 6.

In our prototype for YARN, we only consider CPU and memory. In order not to completely redesign the YARN scheduling system, our "available resource" is only used to rescale the node total resource capacity as presented to Yarn scheduling. We scale up the total resource configured for the node if the available resource is positive and scale down if the available is negative. In the class "RMNode" which is managed by the main RM service, we add the information about the real capacity of node. In the class "SchedulingNode", we store the information of the current resource usage of node. We mostly modified the "abstract scheduler" class which is the base of all YARN schedulers. In this class, we "refresh" or "rescale" the capacity of the worker node and update the total capacity of the cluster after each estimation is received. Other decision making process and scheduling policies of FairShare, Capacity, and FIFO scheduler are kept as is.

B. System under test

To evaluate our new scheduler, we deploy a cluster with 6 Virtual Machines (VM) on OpenStack, each of them is configured with 8 virtual cores, 8 GBs of memory, and 160 GBs HDD. VMs are installed with Ubuntu LTS 16.04, Java OpenJDK 1.8, Hadoop 2.7.1, and Hive 2.1.0. We take the result of original YARN (version 2.7.1) as the base to compare with the improvement made by the modified YARN.

The original Yarn is configured with the minimum allocation set to 1 core and 1 GBs of memory. YARN is allowed to use at most: 7 cores and 7 GBs of memory. We leave the remaining resources to the OS and other utilities. For the prototype, the allowance is set similarly. For doing the estimation of node resource usage, we set the damping factor α to 0.125 as the in previous section.

C. Workloads

In order to make the evaluation repeatable, we use the standard TPC-DS benchmark which is de-facto industry standard benchmark for measuring the performance of decision support solutions. This TPC-DS benchmark is re-implemented for Hive which is published as Hive Testbench [START_REF] Shanklin | Testbench for Apache Hive at any data scale[END_REF] by HortonWorks. The test was run with 200GB of data input (scale factor 200), partitioned by day. In this experiment, we focus on memory and CPU resources. Therefore, before each query is executed, we balance the blocks of HDFS files across the cluster once to maximize data-locality and to minimize the chance that the network becomes the bottleneck. A total of 60 queries were run as-is with no additional hinting, and there was no special tuning used for any of the queries. Some of the queries can be complex queries involving multiple tables and generating large intermediate datasets. Others can be queries that return large amounts of data for further processing by other tools.

Our algorithm is just a method to estimate how much resource the node does have and it do not change any scheduling policies of the schedulers like the Capacity scheduler, the FairShare scheduder, and the FIFO scheduler of YARN. Therefore, we run the query serially and only make sure that the query can fill-up the cluster with parallel tasks on each node. Queries were executed in 3 times on MapReduce engine. In this setting, a query is a chain of MapReduce jobs, one MR job's output is another MR job's input. We notice that some of the jobs in the chain may not occupy the whole cluster, but the majority of them are able fill up the cluster. We also note that the containers are generated by the same query, so the containers are rather homogeneous, which is rather a pessimistic assumption for our algorithm.

D. Results

Figure 7: CDF for speed-up factor of all queries in the tests when comparing to original YARN as base

The speed-up factor is measured as the ratio of the completion time of the query on new system to the completion time of query on the original system. We report in figure 7 the cumulative distribution function of the speedup factors for all 60 executed queries. Queries having value for speedup factor larger than one completed faster than their version executed in standard Yarn. We reported the results of 2 different settings: Est_3G and Est_2G. In "Est_3G" and "Est_2G" users request 3 GBs and 2GBs of memory for each task, respectively. Almost all of the queries improve their completion time. A few of them show similar or longer completion times. As we investigate, these queries have many small stages in the data processing pipeline which cannot take the advantages of parallelism. In average, the queries in the "Est_3G" test complete 23% faster, and the queries in the "Est_2G" test complete 44% faster. "Est_2G" completes faster than "Est_3G" since the actual resource demand of tasks is less than 2 GBs of memory, the system needs less time to converge to the real utilization of nodes. We also ran tests with "Est_1G" but we did not presented in the figure because tasks often failed for both reservation model and estimation model because the memory usage of the task exceeded the user reservation for the task. We also confirm that during Est_3G and Est_2G tests very few tasks failed.

VII. CONCLUSION

The reservation model is simple and is a popular model for current resource management frameworks. However, it will waste resources and needs careful monitoring by cluster administrators. In this work, we aim to introduce a new and simple model for resource management which is based on resource usage feedback from worker nodes. This model helps to avoid reservation bottleneck by users over estimating their needs and to effectively utilize the resources without sacrificing for system stability or without the necessity to learn the workload resource usage.

In addition, we introduce a tracing tool to collect the job utilization, an algorithm to improve scheduling decision, a simulator to replay the trace and to study the stability of the system, and a new improved YARN that is aware of the resource usage at worker nodes.

With the tracing tool, we show that the reservation model leaves a large potential space for improving resource utilization and avoiding wasting resources. With the simulator, we prove that there is a better model to allocate resource to tasks without sacrificing system stability. With our modified YARN, we show that we can reduce the completion time for the jobs from 23% to 44% on the diversified Hive Testbench.

A thorough test on the real system with heterogeneous worker nodes would be the extension of our paper. We mainly focused on batch tasks. It would be interesting in a next step to take into account interactive tasks.

Figure 1 :

 1 Figure 1: Cumulative distribution function of container's allocation efficiency

Figure 2 :

 2 Figure 2: Memory and CPU utilization of the cluster when reservation model is used (top figures) and when the estimation model is used (bottom figures).

Figure 3 :

 3 Figure 3: Resource utilization for the reservation model (top strip) and the estimation model (bottom strip) shows almost identical performance. The reservation model in its ideal scenario where it knows the maximum resource usage of task. The reservation model in its worst scenario to avoid tasks crash where it schedule based on the past estimation in a memoryconstraint cluster with tied reservation from user

Figure 4 :

 4 Figure 4: Fraction of crashed tasks to the total submitted tasks because of memory over-demanded

Figure 5 :

 5 Figure 5: Node parameters to consider for scheduling

Figure 6 :

 6 Figure 6: Implementation of the new YARN

Yarn Tracking is published at https://bitbucket.org/hasonhai/yarntracking

Yarn Prototype is published at https://github.com/hasonhai/hadoop

ACKNOWLEDGMENT

The research leading to these results has received funding from Orange SA and the EU commission in call H2020-644182, project "IOStack".


Fares Triki
email: fares@triki.org

Leverage Bubbles

Keywords: Financial Crises, Rational bubbles, Dynamic Leverage Ratio, Mark to Market accounting, Asset pricing, Macroprudential Regulation, Market Liquidity JEL Classification: G01, G14, G18, G20, G28

This paper investigates the relation between liquidity and asset prices. It shows that, when banks balance sheets are marked to market and banks are targeting a financial leverage level -a situation similar to current environment -formation of Leverage Bubbles of important size is highly likely. This paper studies the Leverage Bubble phenomenon and suggests a new regulation rule based on a Dynamic Leverage Ratio (DLR) rule.

1 Introduction

Introduction

There is hardly a unique market consensus about future firms dividends or future defaults or liquidity risk. Different investors use different prediction and information extraction techniques1 leading ineluctably to a variety of opinions. The observed price on the market is an equilibrium price of all supplies and demands and hardly reflect a consensus price. Moreover all participants are not equally informed. Information gathering cost and technology advance is not equally distributed among all participants. Advanced players like banks are more prone to access and process information when less specialized players would read information from these investors action and would be sensible to their opinions and recommendations. Bubbles and overreaction are the product of such market imperfections. In common knowledge, Bubbles are typically defined as a dramatic asset price increases followed by a collapse. In a more formal definition, bubbles arise if the asset price exceeds its "fundamental value". Before the recent worldwide commodities and housing bubble (2003)(2004)(2005)(2006)(2007) there have been famous historical bubbles that already attract important attention from economist and public2 . Fascination for bubbles lead to various modeling suggestions in the literature: there are models where agents are rational and information is symmetric3 , models where agents are rational and information asymmetric4 , and models where agents are irrational5 . Although this literature did not stressed enough the role of the trading constraints. Indeed, traders not only react to fundamental information, they can also respond to other needs like regulation requirement, risk management constraints, or predefined trading strategies. For instance, [START_REF] Triki | Liquidity and leverage[END_REF] provide empirical evidence that banks and financial intermediaries manage very closely their leverage. In this paper we also argue that banks and financial intermediaries leverage strategy lead to the formation of endogenous rational bubble. This paper extends then the literature on asset bubbles. It also represents a contribution to recent works about financial instability factors. Here, banks assets and liabilities accumulation are the product of continuous re-leveraging of balance sheet and induce the overshoot of asset prices. This could explain the empirical relevance of banks assets or credits growth as a bubble or pre-crisis indicator6 . Finally this work is part of recent efforts to understand the efficiency of current regulation in avoiding financial instability and to suggest new regulation ideas. This paper is organized as follow: The first part is an attempt to throw light on the procyclical effects of financial institutions active leveraging in presence of illiquidity and Mark to Market accounting rules. In a second part asset prices overshoot is derived. In a third part it draws a framework were, in a rational equity bubble setting, the bubble component comes from this price overshoot. Finally, within the conclusion and policy recommendations section, I suggest a new regulation rule based on a Dynamic Leverage Ratio (DLR) that would protect the financial system from leverage bubbles.

Active leveraging

We can distinguish two categories of investors: investors that do not actively manage their leverage like household and other non financial firms, and investors that actively leverage their position (use the extra capital to build extra leveraged positions) like banks and financial intermediaries7 . I first provide a simple illustration of what is leverage. For this purpose I use a stylized bank balance sheet that is divided in two parts: Assets part and Liabilities and Equity part.

Asstes

Liability Securities (S)

Equity (E) Debt (D)

Fig. 1: Simplified balance sheet

Leveraging can be defined as the use of debt to increase the return to equity. I use a measure of leverage that is L: the Debt over Assets ratio:

L = D S
Since the value of the assets must balance the value of the liabilities, the leverage level L varies between zero and one. Zero means a non leverage situation where all securities are financed by equity. One means full or infinite leverage situation where all securities are financed by repo. In practice the full leverage is never reached because of collateralizing and margin calls. In current financial system regulation the balance sheets are continuously marked to market. Banks and financial intermediaries balance sheets reflect immediately any changes in asset prices. As a consequence, asset prices fluctuations have an instant impact on the net worth of the financial system participant. The fluctuation of the asset prices not only affect the net worth of the financial institution it also affects their leverage. It is important to see that leverage is negatively correlated with assets prices excess return over the risk free rate 8 . We provide a simple illustrative example where the banks assets return is 12% and the risk free interest rate is assumed to be 5%: The leverage decreases from 80% to 75%. It is then inversely related to total assets growth over the debt growth rate. The same principle applies for the effect of housing prices on a mortgage Loan To Value (LTV). When the price of a consumer's house goes up his net worth increases, and thus his mortgage LTV goes down. The average leverage appears to be fairly constant thought the business cycles of 2000-2003 and 2003-2009. This suggests that banks use to manage very closely their leverage and manage their asset to target a constant leverage. This evidence is similar to Adrian and Shin (2008) finding on US commercial banks leverage behavior10 .

Assets Liability S t = 100 E t = 20 D t = 80 L=80% ⇒ Assets Liability S t+1 = 112 E t+1 = 28 D t+1 = 84 L=75%

Price overshoot

In this framework I assume a simple strategy of active leveraging: banks are targeting a constant level of leverage D t /S t = L. Figure 3 gives evidence of such practice in Europe and US. In addition, commercial banks in some countries like Canada11 and more recently Switzerland have a leverage ratio limit defined by the regulators. Since this level is lower then the level practiced in other countries Banks naturally choose to target the regulatory leverage.

In the presence of continuous use of Mark to Market (MtM) valuation, targeting a constant level of leverage cannot be achieved without active re-leveraging. As noted earlier the balance sheets of financial institutions reflects immediately any change in asset prices.

Assets

Liability

S t E t D t L t = Dt St ⇒ Assets Liability S t (1 + R t+1 ) E t+1 D t (1 + R) L t+1 = Dt(1+R) St(1+Rt+1)
Fig. 4: Asset fluctuation effect on the balance sheet

The leverage continuously moves with the asset price evolution. And the leverage growth can be related to asset prices growth by the following relation: Leverage growth is negatively related to total assets excess return. How would the financial institution react to variation in leverage when targeting a level of L? It would naturally need to re-leverage its position by buying or selling more assets and by increasing or decreasing their borrowing.

L t+1 = D t (1 + R) S t (1 + R t+1 ) = 1 + R 1 + R t+1 L ∆L t+1 L t = -(R t+1 -R) (3.1)
P t / / P * t+1 / / P t+1 Leveraging [Q 0 → Q 1 → ...] 5 5 l l l l l l l l l l l l l l l
Lets call P * t+1 the price resulting from an initial price shock and Q 0 = Q t the quantity of assets banks and financial intermediaries holds before the re-leverage or de-leverage. I denote the fundamental price return:

R F t+1 = P * t+1 -P t P t
R F t+1 represents the price percentage change that would prevail in the absence of leverage targeting. ∆Q 1 denotes the quantity of asset purchased by the investor to regain the leverage level of L. It is then the solution of:

D t (1 + R) + ∆Q 1 P * t+1 S t (1 + R F t+1 ) + ∆Q 1 P * t+1 = L
Resolving this equation leads to:

∆Q 1 = S t P * t+1 L 1 -L (R F t+1 -R) (3.2)
An important recent finance literature diverges from the classical assumption of market efficiency [START_REF] Grossman | On the impossibility of informationally efficient markets[END_REF], [START_REF] Kyle | Continuous auctions and insider trading[END_REF], [START_REF] Glosten | Bid, ask and transaction prices in a specialist market with heterogeneously informed traders[END_REF], [START_REF] Grossman | Liquidity and market structure[END_REF] 12 and shows that asymmetric information introduces a slope in the demand and supply curve. I call γ the elasticity of the price with respect to the quantity Q of assets held by banks and financial intermediaries:

γ = ∆P/P ∆Q/Q
In an efficient market γ is null. When there are market imperfections γ is strictly positive. It is out of the scope of this paper to model market imperfections, whereas a straightforward theory explaining the potential positiveness of γ is the following: Uniformed investors read information from the quantity traded by informed investors. The reason why there are uninformed players is simple: information is not a free good. It is costly to collect and to analyze.

We can think about banks and financial intermediaries as investors detaining private clients information. We can also see them as financial market industries where the information marginal cost is much lower then an average size investor. This makes banks and financial intermediaries price setters: an asset purchase from these investors puts upward pressure on its price. Equivalently, an asset sell puts downward pressure on the price. 13 Investors response to a price shock is assumed instantaneous. Using the price elasticity definition equation 3.2 translates to:

∆P 1 = γ t+1 L 1 -L P t (R F t+1 -R) (3.3)
Where ∆P 1 is the price reaction to asset quantity change. Since asset prices moved by ∆P 1 the leverage is again affected. The price movement translates to further price purchases or sales by banks and financial intermediaries in order to keep the leverage constant. Again the purchases or sales translates into price reaction:

∆P 0 = P * t+1 -P t ' ' O O O O O O O O O O O ∆P 1 " " F F F F F F F F F ... > > > > > > > > > > ∆P ∞ ∆Q 1 < < x x x x x x x x x ∆Q 2 = = { { { { { { { { { ... = = { { { { { { { { {
The equation driving the successive changes in prices is also derived from the active leverage targeting strategy.

∆P i+1 = γ t+1 L (1 -L) ∆P i , with i = 1, .., +∞ (3.4)
A simple way to derive it is to first notice that

∆D i+1 ∆E i = L 1 -L
where ∆D i+1 is the variation in debt needed to cover additional assets purchase/sale when the equity value moves by ∆E i . The net wealth of the financial institution between i and i + 1 moves because of asset price overshoot ∆P i and the MtM net gain/loss is ∆E i = Q i ∆P i . It follows that

P i ∆Q i+1 = L (1 -L) Q i ∆P i
which lead to equation 3.4. Convergence to zero of the series ∆P i requires to have:

13 Note that γ is not the price elasticity of demand or supply and Qt is not the quantity of total asset demanded or supplied on the market at time t. Qt is instead the volume of assets hold by banks and financial intermediaries since they are the usual informed players. γ is indeed the elasticity of the price with respect to the quantity of asset held by banks and financial intermediaries. Document de Travail du Centre d'Economie de la Sorbonne -2009.39

γ t+1 L (1 -L) < 1
This condition is necessary to have a finite equilibrium prices P t+1 = P ∞ . In an efficient market, γ is null, and there is no further price adjustment. In imperfect market, γ is strictly positive but assumed small enough to ensure the convergence of ∆P i . Figure 3 shows that worlds top banking institutions held on average about 6 percent of capital. A simple rule of targeting a leverage of 94% would mean that the price converges only when γ is lower than 6%.

Frictions on the market measured by γ are also called market illiquidity. In a highly illiquid market where banks transaction has an important impact on assets prices the convergence condition can be violated. A way to fix that is to set γ as function of the overshoot reaction level saying that the higher the deviation from the fundamental price the more visible the missprice14 . A state dependant γ is also one way of ensuring the non negativity of prices15 .

To summarize, when the asset prices return differs from the liability interest rate, there is a series of position adjustment made by financial institution practicing an active leverage targeting. This adjustment is procyclical as active leveraging overshoots up or down the price excess return. The series of position adjustment made by financial institution is assumed instantaneous. Denoting R t+1 the price return at time t + 1 after the overshoot occurs, I find that the excess return caused by the leveraging effect is proportional to the initial "fundamental" excess return over the risk free rate:

R t+1 -R F t+1 = γ t+1 L (1 -L) -γ t+1 L R F t+1 -R (3.5)
The series of position adjustment may not be assumed instantaneous. This is beyond the scope of our model whereas it is important to point out some interesting facts. When the overshoot is not instantaneous, the price convergence may not be fully realised before another fundamental shock lead to a new series of adjustment. This would partly explain the so called asset price momentum puzzle. An initial positive shock makes the prices continue to rise until convergence or a new "fundamental" chock happens. It is also interesting to see that the momentum level is a function of the market illiquidity or friction factor γ and the level of leverage L. The higher the leverage and the the higher the illiquidity the higher the convergence time of the series ∆P i . As seen earlier the convergence to a new price is not guaranteed for high levels of market illiquidity. When adjustment are not instantaneous, the new asset price is not necessarily undefined. But asset prices momentum is infinite and it only disappears with an opposite new fundamental shock.

Rational Leverage bubble framework

Stock prices are usually expressed as the expected value of future dividends D. Using a constant discount rate R the stock price P t is:

P t = +∞ j=1 1 1 + R j E t D t+j
Since [START_REF] Leroy | The present-value relation: Tests based on implied variance bounds[END_REF] and [START_REF] Shiller | Do stock prices move too much to be justified by subsequent changes in dividends?[END_REF] papers showing the excess volatility of the stock prices compared to the dividends, new subsequent works have been done to depart from this representation. The rational bubbles literature is based on rational expectation and the same dividend/price fundamental relation:

P t = E t (P t+1 + D t+1 ) /(1 + R)
In rational bubble models the expected capital gains growth is slower then R and the transversality condition is violated:

lim T →∞ 1 1 + R T E T P F T +1 = 0
This non null entity is the bubble component B t . The equity price is defined as:

P t = P F t + B t P F t = +∞ j=1 1 1 + R j E t D t+j
where P F t is the fundamental price. Using market efficiency condition and rational expectations, it appears that B t has to follow a discounted martingale:

E t B t+1 = (1 + R) B t
This condition allows multiple settings for B t . In the literature, most of the rational bubbles settings are driven by an exogenous factor. However endogenous rational bubble can exist. [START_REF] Froot | Intrinsic bubbles: The case of stock prices[END_REF] provide and test an "intrinsic bubble" model where the bubble component is a deterministic non linear function of the dividends. The authors interpret this specification as a systematic overreaction of stock prices to dividend news. Although this specification uses intrinsic market information about dividends in the bubble factor specification, it does not explain the endogenous systematic overreaction. The leverage bubbles can be an alternative setting for a rational bubble where the overreaction is endogenously formed by the active leveraging behavior and the Document de Travail du Centre d'Economie de la Sorbonne -2009.39 It is not obvious how a deterministic endogenous bubble can take place in a rational expectation agents market. It is puzzling to say that prices overshoot the fundamental level by a deterministic component when all agents are aware of such phenomenon. This is maybe a common problem with all endogenous rational bubble model. In exogenous bubbles models, like [START_REF] Blanchard | Bubbles, rational expectations and financial markets[END_REF] model, the bubble is there because of an exogenous, usually undefined, trigger. [START_REF] Froot | Intrinsic bubbles: The case of stock prices[END_REF] had a similar comment in the introduction of their dividend overreaction rational bubble: "It is difficult to believe that the market is literally stuck for all time on a path along which price dividend ratios eventually explode. If the market began on such a path, surely investors would at some point attempt the kind of infinite horizon arbitrage that rules bubbles out in theoretical models. [...] Perhaps agents do not really have as clear a picture of the distant future as the simplest rational-expectations models suggest"

There is maybe a way to explain how rational expectation and deterministic endogenous bubble can coo-exist in the Leverage Bubble model. As a matter of fact γ t , the elasticity of asset prices, is function of agents reaction to changes in trades sizes. Having a non deterministic γ t makes it hard to infer the fundamental price from the market prices. So even when agents are rational, arbitrage is made hard to achieve.

Another common problem raised by [START_REF] Blanchard | Bubbles, rational expectations and financial markets[END_REF] is the fact that negative bubbles cannot exist. Although, the probability that the stock price becomes zero is small and can be ignored like commonly done in the periodically collapsing bubbles literature. Moreover as [START_REF] Weil | On the possibility of price decreasing bubbles[END_REF] notice if we assume that fundamentals, here the fundamental asset return, depends on the presence of bubble the negativity of bubble term is no more a theoretical constraint.

Policy recommendation

This chapter highlights the paper's conclusions and recommendations for policy markers:

1. Active leveraging may lead to asset prices overshoot It seems now natural to say that active leveraging may have asset pricing implication. However this statement is not as natural and intuitive as it seems. In the financial press and other market commentary, one is used to hear critics about excessive leverage building and procyclical leveraging. From the empirical revelation of Adrian and Shin (2008) paper, the procyclical nature of leverage behavior has retained the attention Document de Travail du Centre d'Economie de la Sorbonne -2009.39 of commenters and policy maker17 . However it is maybe more important to say that active leveraging, even when countercyclical, may lead to price overshoot. For instance, maintaining a constant leverage has never been seen as a potential danger since regulators in some countries are imposing a leverage limit and thus are happy with banks maintaining a constant leverage. In this paper I show that a simple constant leverage targeting rule may lead to a rational bubble formation when market is not perfectly liquid.

2. Leverage without MtM accounting does not lead to bubble formations.

It is hard to believe that regulators should constraint the active leveraging since it is the nature of banks activities. Instead they may be tempted by reviewing the MtM accounting principle. In current regulation, balance sheets are continuously marked to market and this is what causes market participant balance sheet adjustments and active leveraging behavior. Nevertheless there are no yet a serious alternative to the Mark to Market rule. And accountants will argue that leverage impact is not caused by MtM accounting. Rather, MtM accounting reveals it.

3. Given current financial institutions leverage level, only a small illiquidity is needed to make the overshoot effect important and persistent

The price overshoot is highly sensitive to γ. For the condition 0 ≤ γ ≤ 1-L L to be satisfied in current levels of banks leverage, γ shouldn't exceed a level of about 4%. What means that banks should be able to double their assets without moving the price by more than 4%. In addition, the more γ is close to 4% the more the overshoot factor tends to infinity and a γ of only 2% would overshoot the excess return by 100%. This shows that the described phenomenon is not marginal and that when the market shows signs of illiquidity the presence such leverage bubble is very likely.

4. The ideal remedy would be a contracyclical dynamic leverage ratio (DLR) limit

Mark to Market is a natural and "fair" valuation rule. And active leveraging, i.e. borrowing to invest, is the nature of financial institutions business. Since then, the most efficient way for regulators to avoid leverage bubbles formation is to impose an appropriated leverage ratio limit that would be function of asset prices growth. From equation 3.1:

∆L L = -(R t+1 -R)
Leverage ratio limit should grow by the exact amount of price excess return over borrowing rate but in the opposite direction. When banks target this contracyclical maximum allowed leverage level, there is no incentive for leverage motivated trading. This is because changes in prices do not lead anymore to a gap between the targeted leverage and the observed one. In addition, the leverage ratio limit also plays its traditional role of prohibiting excessive leverage building.

A bandwidth within which the leverage limit is allowed to move should also be defined. It is important to set a lower limit not to constraint banks too much in booming periods allowing them to remain profitable. And more importantly the upper limit of the band would prohibit a too high level of leverage, equivalent to a high level of risk, that would result from prices depreciation. This upper limit should be set to current regulation levels18 . The DLR band is assumed to be [75%-95%]. The FTSE index return is assumed to be the benchmark for asset growth and the Euribor the benchmark for the borrowing rate. I use quarterly growth rate and a quarterly update of the DLR. The simulation starts with a leverage limit of 75% in December 1999. This is because after a booming period the leverage limit is likely to reached the lower band limit of 75%.

The figure shows a contracyclical shape of leverage: During the booming years of 2003-2007 the DLR varies around the lower limit when in during depressed market periods of 2000-2003 and 2007-2009 the leverage limit grows up to reach the higher limit of 95%. What is important to retain is that the DLR allows no leverage overshoot whiting the DLR band.

Whereas, when the DLR reaches one of the band's limit, the rule that protect form price overshoot is no more active.

Conclusion

This paper provides a model for asset price overshoot generated by banks balance sheet adjustments. This asset price overshoot follows a discounted martingale and is coherent with a rational bubbles framework. A single bubble model cannot certainly explain the entire asset prices boom and crash phenomenon.

Other potential balance sheet driven causes of price distortion can be regulatory arbitrages, maturity mismatch, or the use of short history in risk management practices. Moreover, in boom and crash situations there are interactions due to banks inter-linkage and to macroeconomics feedbacks that would impact banks behavior and prices. Nevertheless the aim of this framework is to shed the light on an important bubbles driver that is active leveraging, and to provide with a regulation rule to protect the financial system from leverage bubbles.

Document de Travail du Centre d'Economie de la Sorbonne -2009.39

Fig. 2 :

 2 Fig. 2: Leverage fluctuation example

Fig. 3 :

 3 Fig. 3: Commercial banks leverage targeting Figure 3 shows the average leverage of a set 9 of main US and European (Den-8 Here I assume that the financial institution borrows at the risk free rate although in general interest rate payed on depts should be used 9 The full banks set is:

Fig. 6 :

 6 Fig. 6: The contracyclical dynamic of the DLR

  Barclays, Hsbc Holdings, Lloyds, Northern Rock, Royal Bank Of Scotland, Danske Bank, Bnp Paribas, Credit Mutuel Group, Societe Generale, Bayerische Hypo-Und Vereinsb, Bayerische Landesbank, Commerzbank, Dresdner Bank, Banca Carige, Banca Monte Dei Paschi Siena, Intesa Sanpaolo, Unicredit, Banco Bilbao Vizcaya Argenta, Banco Popular Espanol, Banco Santander, Nordea Bank, Svenska Handelsbanken-A, Bank Of America, Citigroup, Jpmorgan Chase & Co, Wachovia Corp, Wells Fargo & Co. The Leverage shown is the average Leverage of available quarterly data in Bloomberg.

Fundamental analysis, historical prices patterns, prices momentum, macro indicators, forecasting of agents behavior, ...

The Dutch Tulip Mania (1634-1637), the Mississippi Bubble (1719-1720) and the South Sea Bubble (1720). More recently, one can cite the internet bubble(1996)(1997)(1998)(1999)(2000).

Although in a complete market where information is symmetric the formation of persistent miss-pricing is very unlikely. Tiroles(1992) showed that, assuming rational expectations and a finite number of participants, in a market equilibrium with complete information a bubble cannot exist.

[START_REF] Allen | Churning bubbles[END_REF],[START_REF] Allen | Finite bubbles with short sale constraints and asymmetric information[END_REF]

Shiller (2005) describes a model of "irrational exuberance" bubbles. When asset prices start to rise, the success of some investors attracts public attention. New investors extrapolate recent price action far into the future and enter the market. By buying more assets they put an upward pressure on prices. Document de Travail du Centre d'Economie de laSorbonne -2009.39

For example[START_REF] Borio | Asset prices, financial and monetary stability: exploring the nexus[END_REF] were able to predict about 80% of crises since the 1970s using the excess of credit growth.

[START_REF] Triki | Liquidity and leverage[END_REF] paper showed that financial intermediaries and investment banks have been actively building leverage in recent booming period in opposition to household and non financial firms. Document de Travail du Centre d'Economie de laSorbonne -2009.39

[START_REF] Triki | Liquidity and leverage[END_REF] uses aggregate US commercial banks data from 1963 to 2006 to show that leverage growth have been fairly insensitive to asset growth.

In Canada the leverage ratio is limited to 95% (Assets are limited to 20 times the capital size). Document de Travail du Centre d'Economie de laSorbonne -2009.39

There has also been empirical works pointing out the non null slope of demand curves for assets (Some early examples are[START_REF] Shleifer | Do demand curves for stocks slope down?[END_REF] and Loderer, Cooney and van Drunen (1991)) Document de Travail du Centre d'Economie de la Sorbonne -2009.39

In practice one can think about crisis situations where the panic and uncertainty are important enough to lead to a high sensitivity to negative asset quantity variations. In such situations price movement overshoot can be significatively high to be qualified as market crash.

The positive likelihood of negative prices, although small, is a shortcoming that the simple setting with constant γ would share with other rational bubble models. Document de Travail du Centre d'Economie de laSorbonne -2009.39

One can show that EtLB t+1 = (1 + R) LBt Document de Travail du Centre d'Economie de la Sorbonne -2009.39

[START_REF] Triki | Liquidity and leverage[END_REF] found out that security dealers and brokers have a Leverage level growth positively related to the asset growth. Document de Travail du Centre d'Economie de laSorbonne -2009.39

In the illustrative example I use the current leverage ratio limit in Canada Document de Travail du Centre d'Economie de laSorbonne -2009.39

+ + 8 8 q q q q q q q q q q q q q q q q q q q q q q q q q q q q 3 3 I assume a simple pricing kernel that has two distinct states in a risk neutral agents populated world. The world has a probability p u of being in the 'up' state and p d = 1 -p u to be in the 'down' state. In this setting the fundamental price return is R F u in the 'up' state and R F d in the 'down' state. And the risk free rate is constant and is equal to R.

If we assume γ constant for a matter of simplicity, the expected return rate is equal to:

Since in a risk neutral world the expected fundamental price return is the risk free rate E t R F t+1 = R it follows that:

Which shows that the leverage bubble is coherent with the definition of a rational expectation bubble. It follows a martingale 16 and thus does not affect the first moment of the price. The leverage bubble LB t = P t -P F t is derived from equation 4.1 :