Student Member, IEEE Ahmadreza Montazerolghaem

Member, IEEE Mohammad Hossein Yaghmaee

Load-balanced and QoS-aware Software-defined Internet of Things

Keywords: IoT softwarization, Software-defined networking, Large-scale IoT network, Load balancing, Fuzzy logic. ! IoT Communication Network IoT Servers IoT Gateways Traditional Switches IoT Devices Bandwidth Centric Delay Centric Best Effort

Internet of Things (IoT) offers a variety of solutions to control industrial environments. The new generation of IoT consists of millions of machines generating huge traffic volumes; this challenges the network in achieving the Quality of Service (QoS) and avoiding overload. Diverse classes of applications in IoT are subject to specific QoS treatments. In addition, traffic should be distributed among IoT servers based on their available capacity. In this paper, we propose a novel framework based on Software-defined Networking (SDN) to fulfill the QoS requirements of various IoT services and to balance traffic between IoT servers simultaneously. At first, the problem is formulated as an Integer Linear Programming (ILP) model that is NP-hard. Then, a predictive and proactive heuristic mechanism based on time-series analysis and fuzzy logic is proposed. Afterwards, the proposed framework is implemented in a real testbed, which consists of the Open vSwitch, Floodlight controller, and Kaa servers. To evaluate the performance, various experiments are conducted under different scenarios. The results indicate the improved IoT QoS parameters, including throughput and delay, and illustrate the non-occurrence of overload on IoT servers in heavy traffic. Furthermore, the results show improved performance compared to similar methods.

INTRODUCTION

I NTERNET of things has become one of the major and fascinating topics in the networking field over the last few years [START_REF] Chang | Internet of things (iot) and new computing paradigms[END_REF]- [START_REF] Liu | Efficient ddos attacks mitigation for stateful forwarding in internet of things[END_REF]. IoT gives access to information at any time and place. However, this causes the network to deal with a huge amount of traffic data. In the coming years, traffic volume as well as the number of IoT devices will grow exponentially. This issue is more critical in large-scale industrial IoT as the information and data management are more sensitive and vital in industries [START_REF] Vögler | A scalable framework for provisioning large-scale iot deployments[END_REF]. In IoT, a large number of heterogeneous devices are constantly exchanging heavy traffic from the network to servers [START_REF] Verma | A survey on network methodologies for real-time analytics of massive iot data and open research issues[END_REF]. In this case, an improper traffic distribution between the servers causes some of them to face resource scarcity and thus become overload. Moreover, since there are different traffic classes in IoT, existing mechanisms may not satisfy the necessary QoS requirements (e.g., bandwidth and delay) for this huge traffic volume [START_REF] Brogi | Qos-aware deployment of iot applications through the fog[END_REF], [START_REF] Awan | Modelling qos in iot applications[END_REF].

Fig. 1 illustrates an IoT abstract model. This model shows that the sensed or measured traffic in the infrastructure (the sensing layer) is conveyed to IoT servers via different paths in a communication network (the network layer). IoT servers offer different IoT applications and services as Over the next few years, with an increase in the traffic volume collected and sent from the infrastructure to IoT servers, not only will IoT servers face overload, but also the communication network will fail to satisfy the QoS of traffic. In this paper, we have considered this issue as a best path selection problem, so that the selected path establishes the QoS of the IoT traffic classes, and balances the load of IoT servers (Fig. 2). The knowledge regarding available resources of servers, network topology, active paths, and QoS parameters of the network, such as link's bandwidth and delay are among the challenges of the problem.

With the emergence of Software-defined networking (SDN) technology, the entire network and its elements are viewed as a virtual network (global view), which is controlled using applications and APIs as well as a logically centralized controller. This causes the network resources (in- cluding servers) to be managed efficiently and on-demand, ensuring a more effective QoS. In fact, SDN is a dynamic, flexible, and manageable architecture that separates the control plane from the data plane. The data plane includes simple forwarding devices such as OpenFlow switches whereas the control plane consists of controller and various network applications such as routing, firewall, load balancing, monitoring [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF]- [START_REF] Quan | Adaptive transmission control for software defined vehicular networks[END_REF]. The OpenFlow protocol [START_REF] Mckeown | Openflow: enabling innovation in campus networks[END_REF] is also responsible for establishing communication between the two planes using a set of messages. In other words, collecting statistics or installing rules is performed using messages, such as Features-request/reply, Packet-In or Flow-mod. The statistics collected can be related to network topology, bandwidth and link delay, type of flows, etc.

Motivations

Why do we need a scalable IoT infrastructure? Scalability will be key to handling the explosive growth in the IoT. This means that IoT applications must have the ability to support an increasing number of connected devices, users, application features, and analytics capabilities, without any degradation in the QoS. Scalable IoT applications are also essential to monitoring, securing, and managing an increasing number of devices through a proportionate increase in the resources. The traffic and number of IoT devices will grow exponentially in the coming years. Knowing that the IoT infrastructure is a key service in next-generation network, it is vital to design and develop high performance and scalable communication infrastructure with QoS support. Moreover, for future large-scale IoT, it will be necessary to collect and transfer information from each sensor. With the overall modern IoT road map, both the number of sensors and the sampling frequency on a sensor will increase dramatically. Therefore, this will create a huge traffic load which should be efficiently routed and balanced across the network and IoT servers.

Contributions

Our study mainly aims at scalable managing the IoT traffic using SDN. In this regard, by applying SDN in IoT, we provide a resource and QoS conscious framework. In this framework, we seek to choose the best path among the existing paths for each of the IoT traffic classes in a way that the load balance of IoT servers is established, and the QoS of the traffic class is satisfied. Consequently, we propose a modular controller that uses fuzzy logic and the Normalised Least Mean Squares (NLMS) prediction system. We focus on proactive resource management that is based on predictions of future workload based on the past workload. The most important method in this area is time-series analysis. Timeseries analysis could be used to detect repeating patterns in the workload or to estimate future values for resource allocation. In order to apply time-series analysis in resource management or load balancing, a certain metric will be periodically sampled at fixed intervals. The result will be a time-series containing a sequence of last observations. Timeseries methods extrapolate this sequence to predict future values. Some of the methods used for this purpose are Moving Average, Autoregression, Autoregressive-Moving-Average (ARMA), exponential smoothing, and machine learning techniques [START_REF] Nikravesh | Measuring prediction sensitivity of a cloud auto-scaling system[END_REF]. We utilize the work of [START_REF] Garroppo | On traffic prediction for resource allocation: A chebyshev bound based allocation scheme[END_REF] that proposes a comparative analysis among prediction techniques, used for developing a dynamic prediction based the resource allocation strategy. Among these techniques, the NLMS predictor is the one providing the best trade-off between complexity, accuracy, and responsiveness.

To summarize, the main contributions of this article are:

• We design a novel SDN-based control and management framework for IoT, • We define the problem of preventing overload occurrence on IoT servers along with increasing the QoS as an optimization problem, • We prove NP-hardness of the defined optimization problem with limited resources, • We provide a predictive and proactive heuristic method based on time-series analysis and fuzzy logic, • We design modules as well as a flowchart of the proposed framework, • We implement the proposed framework in a real testbed, • We evaluate the performance of the implemented framework under different experiments and scenarios.

Organization

Our paper is organized as follows: Section 2 refers to the related work. The proposed model and framework are discussed in Section 3. Section 4 includes the implementation and performance evaluation of the framework. Finally, the conclusions and future work are provided in Section 5.

RELATED WORK

Research communities investigate different aspects of IoT, and they provide surveys regarding IoT issues and challenges [START_REF] Gardašević | The iot architectural framework, design issues and application domains[END_REF]- [START_REF] Ngu | Iot middleware: A survey on issues and enabling technologies[END_REF] that should be addressed such as security and privacy [START_REF] Medaglia | An overview of privacy and security issues in the internet of things[END_REF]- [START_REF] Farris | A survey on emerging sdn and nfv security mechanisms for iot systems[END_REF], architectural issue [START_REF] Gubbi | Internet of things (iot): A vision, architectural elements, and future directions[END_REF], big data [START_REF] Chen | Big data: A survey[END_REF], [START_REF] Strohbach | Towards a big data analytics framework for iot and smart city applications[END_REF] as well as energy efficiency [START_REF] Kaur | An energy-efficient architecture for the internet of things (iot)[END_REF] and QoS [START_REF] Brogi | Qos-aware deployment of iot applications through the fog[END_REF]- [START_REF] White | Quality of service approaches in iot: A systematic mapping[END_REF]. This section discusses state-of-the-art research that uses SDN technology in IoT. Application of SDN technology in IoT has received considerable attention over the past few years.

In [START_REF] Liu | Sdn-based data transfer security for internet of things[END_REF] a SDN-based data transfer security model for IoT is designed that attempts to improve the availability of secure applications, and to actively respond to network threats. The authors of [START_REF] Jararweh | Sdiot: a software defined based internet of things framework[END_REF] propose a centralized control system for IoT security (SDSec) and storage (SDStore) services. The authors discuss that SDSec can provide visibility for all the traffic flows in the network. As a result, it makes it possible to figure out suspicious traffic. The authors of [START_REF] Bera | Soft-wsn: Softwaredefined wsn management system for iot applications[END_REF] offer a software-defined wireless sensor network framework (Soft-WSN) to support IoT service provisioning. Similarly, [START_REF] Galluccio | Sdn-wise: Design, prototyping and experimentation of a stateful sdn solution for wireless sensor networks[END_REF] introduces SDN-WISE that provides a flexible vendor-independent policy implementation in WSN for IoT application. SDN-WISE propounds APIs that allow software developers to implement the SDN controller. Wu et al. [START_REF] Wu | Ubiflow: Mobility management in urban-scale software defined iot[END_REF] offer UbiFlow, the software-defined IoT model for flow control and management of mobility. UbiFlow partitions the IoT network into the small network. Each network is administered by a physically distributed SDN controller. The IoT devices in each network could connect to different access points depending on their locations. In [START_REF] Kakiz | A novel sdn-based iot architecture for big data[END_REF], kakiz et al. propose an IoT architecture based on SDN to overcome big data issues. Also, [START_REF] Din | Sdiot: Software defined internet of thing to analyze big data in smart cities[END_REF] focuses on analyzing big data in smart cities using SDN. An energy efficient routing in IoT through the use of a SDN controller is described in [START_REF] Kharkongor | A sdn controller with energy efficient routing in the internet of things (iot)[END_REF]. In [START_REF] Deng | An application-aware qos routing algorithm for sdn-based iot networking[END_REF], the authors propose a QoS routing algorithm for SDN-based IoT systems based on the simulated annealing algorithm. In addition, saha et al. [START_REF] Saha | Sway: Traffic-aware qos routing in software-defined iot[END_REF] use the K-shortest paths algorithm in SDN controller to calculate a feasible routing path by taking into account the QoS requirements of each IoT packet.

While much prior research has suggested the potential benefits of applying SDN in computer networks in order to facilitate network management, there has only been few studies about the practical approaches of applying SDN in IoT [START_REF] Bizanis | Sdn and virtualization solutions for the internet of things: A survey[END_REF]. Additionally, the whole concept of SD-IoT is in its infancy and standardization efforts in terms of framework, protocols, applications, and assessment tools are still underway. Also, as discussed earlier, the proposed ideas are mostly preliminary proposals about softwarization of WSNs; or they focus on security and big data challenges of IoT. Here, we pay particular attention to management of resources as well as QoS. To the best of our knowledge, there are no studies concerning a comprehensive approach for combining IoT server load balancing with IoT QoS mechanism. Therefore, the exploration of such an approach is timely and crucial, especially considering the rapid development of IoT applications and the emergence of SDN. In this paper, we propose a SDN-based architecture for IoT applications, so that both the path and server selection can be managed together to improve QoS for the IoT users, and to balance traffic between IoT servers simultaneously.

THE PROPOSED MODEL AND FRAMEWORK

In this section, we introduce the mathematical system model and the novel SDN-based framework in a respective order.

The System Model

The notations used in this subsection are described in Table 1. Assume that an IoT communication network can be modeled as graph G = (V, E), where V represents the set of switches, and E indicates the set of links. Let |V | = v and |E| = e be the number of switches and number of links, respectively. This graph connects l IoT gateways to z IoT servers (Fig. 2). IoT gateway is a bridge which connects between communication network (servers/switches) and sensor network (IoT devices). It is responsible for protocol conversion and data fusion of different sensor data. Each link (i, j) ∈ E has a delay d i,j and bandwidth b i,j . The resource consumption of each IoT server is also denoted by r. Here, ρ represents the remaining resources of each The maximum network bandwidth Dp

The maximum acceptable delay Hp

The maximum number of permissible hops Rp

The maximum server resources IoT server. Generally h is considered as a hop count. The hop count and resources are assumed to be non-negative.

There are three types of IoT traffic on this network (delaycentric, bandwidth-centric, and best-effort). The goal is to find the best path from the source node s (the IoT gateway) to the target node t (the most appropriate IoT server) which satisfies the resource limits of the servers as well as QoS of traffic. In other words, the objective of the problem is balancing the load of IoT servers, and satisfying the QoS in order to efficiently use resources and consequently achieve low delay and high throughput. In this regard, to guarantee QoS requirements, we are seeking the shortest path for besteffort traffic, minimum-delay path for delay-centric traffic, and maximum-bandwidth path for bandwidth-centric traffic.

Prior to proposing the SDN-based heuristic approach, we prove that the problem of load-balancing and QoS-aware routing in the IoT network with resource limitation is an ILP problem and is, therefore, NP-hard. Proposition 1. The joint load-balance and QoS-aware routing problem in an IoT communication network with limited server resources is an ILP problem.

Proof: Let P be the set of all the routes from s to t. For any path p ∈ P , a binary variable u p is introduced. Also, q p , r p , and ρ p are used to denote QoS, resource consumption, and remaining resources of p, respectively. The optimization problem is:

maximize p f p u p (1)
subject to:

f p = p (αq p -βr p ), ∀p ∈ P (2) q p = γ b p B p -δ d p D p -ϑ h p H p , ∀p ∈ P (3) b p ≤ b i,j u p , (i, j) ∈ p, ∀p ∈ P (4) d p = (i,j)∈p d i,j u p , ∀p ∈ P ( 5
)
h p = (i,j)∈p |{i, j}|u p , ∀p ∈ P (6) r p ≤ ρ p R p u p , ∀p ∈ P (7) b p ≤ B p , d p ≤ D p , h p ≤ H p , ρ p ≤ R p , ( 8
) 0 ≤ q p ≤ 1, 0 ≤ r p ≤ 1, (9) 0 ≤ α ≤ 1, 0 ≤ β ≤ 1, ( 10
) p u p = 1, (11)
p (γ + δ + ϑ)u p = 1, (12)
Variables:

u p ∈ {0, 1}, γ, δ, ϑ ∈ {0, 1}, q p , r p , b p , d p , h p ≥ 0
This model seeks to find the path p, so that f p is maximized (Eq. ( 1)). Here, f p is a function of both the QoS and server consumable resources of the path p (Eq. ( 2)). The α and β coefficients provide a trade-off between QoS and resources. The objective is to achieve the highest weighted sum of QoS and resources. With f p being maximized, a path can be explored that has the highest weighted sum of QoS and server resources. The q p depends on the traffic class, while γ, δ and ϑ show which traffic is related to which of the three traffic classes (bandwidth-centric, delay-centric, and best-effort traffic, respectively). This model seeks to find the maximum-bandwidth, minimum-delay or shortest path by Eq. ( 3) and with respect to the traffic classes.

Here, b p , d p and h p represent the bandwidth, delay, and length of p, respectively (Eq. ( 4)-( 6)). Eq. ( 7) ensures that the server consumable resources associated with the path p are less than its remaining resources. Moreover, B p , D p , H p and R p are the maximum network bandwidth, maximum acceptable delay, maximum number of permissible hops, and maximum server resources, respectively (Eq. ( 8)). The existence of these parameters causes the q p and r p values fall to between 0 and 1 (Eq. ( 9)), and therefore Eq. ( 2) normalizes. For this reason, α and β coefficients are between 0 and 1 as well (Eq. ( 10)). Eq. ( 11) guarantees that exactly one path is selected. Furthermore, each time the model is solved, the best path is obtained for one of the traffic classes (Eq. ( 12)). Although the objective function and constraints are linear, the binary variable u p renders the model an ILP which is generally NP-hard, and cannot be solved in polynomial time [START_REF] Papadimitriou | On the complexity of integer programming[END_REF]. To overcome this drawback, a SDN-based framework is proposed.

The SDN-based Heuristic Approach

To reduce time complexity, the problem is decomposed into two subproblems (server selection subproblem and path selection subproblem), which are solved in two phases.

In this regard, an SDN-based framework is proposed for the IoT communication network which considers the subproblems as SDN modules (select least-load iot server module and select QoS-aware route module) in the application plane. This framework benefits from SDN's ability to provide a global view of the entire network and thereby provides the route QoS and server load balancing. In this regard, the appropriate server is first selected, and then an appropriate path with respect to the selected server is found.

The Proposed Framework

Our goal is to move towards the Software-defined IoT so that conscious traffic management is feasible for the IoT. To this end, we propose the framework, as presented in Fig. 3. The architecture of this framework is compatible with the ONF (Open Networking Foundation) SDN [START_REF]Onf sdn model[END_REF] and the IoT reference model (Fig. 1) consisting of three layers that interact with each other through a series of interfaces. The IoT device layer includes sensing and metering devices as well as IoT gateways. Traffic is aggregated by these IoT gateways. Accordingly, traffic is achieved through OpenFlow switches and flows into the layer of IoT servers by managing the SDN controller. The controller has a global view of resources, traffic, and the IoT network. Thereby, an appropriate path and server for each traffic class are considered with the help of OpenFlow protocol. Therefore, it provides control, management, scalability, and flexibility for large-scale IoTs. Fig. 4 shows a general example of how the IoT traffic management is governed by the controller. Upon receiving the first message from any traffic class, the OpenFlow switch encapsulates it within a Packet-In message, and then sends it to the controller to determine the appropriate path and server. The controller installs the response with the Flow-mod message on track switches. Then, the traffic is exchanged between the IoT gateway and IoT server. Thus, effective traffic routing is realized. Now, the main remaining issue is the architecture as well as the performance of the controller, which are discussed in the following subsections.

3.2.2

The Proposed Controller Fig. 5 shows the architecture of the proposed controller. It builds a clear distinction between data logic and management based on the modular structure. The IoT traffic and two types of management datagrams flow into the data and control planes (sFlow and OpenFlow), respectively. The Network Statistics Measurement module is capable of collecting detailed data from the topology state, traffic flows, switches, and links using OpenFlow messages. The IoT Traffic Classification module categorizes the IoT traffic into three classes. The sFlow protocol [START_REF]sflow protocol[END_REF] provides the consumable resources statistics of IoT servers for the controller using the sFlow Agent (embedded within the servers) and the sFlow Collector. The CPU and memory are the most important of these resources. In other words, the servers load status is sent to the Collector module by the sFlow Agent via the sFlow protocol. The sFlow Agent uses a sampling method to capture CPU and memory statistics from the server. sFlow Datagrams are used to forward the sampled statistics to a sFlow Collector in order to store in the database for analysis purpose.

In order to react faster to CPU and memory variations, the controller has to be predictive-driven, and for this reason we have used time-series analysis. The NLMS algorithm [START_REF] Haykin | Adaptive filter theory[END_REF] is one of the best options in this regard, since it can create a compromise between complexity, accuracy, and responsiveness [START_REF] Garroppo | On traffic prediction for resource allocation: A chebyshev bound based allocation scheme[END_REF]. The NLMS Prediction System module is then applied to analyze and predict future CPU and memory values of the servers. This module uses historical data collected in the database (the details of this module are given in the subsection 3.2.2.1). Due to the equitable and proactive distribution of load between IoT servers, each IoT server is provided with a load window. With respect to the NLMS module output, the Fuzzy System module set the size of these windows. The greater the size of a server load window, the lesser the load (the details of this module are described in the subsection 3.2.2.2). Finally, the Select Leastload IoT Server module chooses a server with the maximum available resources. This server has the largest load window size. Then, the Select QoS-aware Route module finds the path with the desired QoS of the classified traffic for achieving the selected server.

The flowchart of the controller is shown in Fig. 6. Time is divided into τ intervals. For the time-series analysis, the server resources should be sampled at specific time periods. The result is a time series containing a series of last observations. Here, c k τ and m k τ represent the values sampled by the sFlow Agent from the CPU and memory of the server k at the current τ , respectively (box 1). These values are stored as historical data in the database (box 2). So, there are two vectors

X k τ (CP U ) = [c k τ , c k τ -1 ..., c k τ -φ+1 ] and X k τ (M emory) = [m k τ , m k τ -1 , ..., m k τ -φ+1
] containing φ of the previous observations for each server k available. As a result, the estimated value of c k and m k for the next τ (i.e., c k τ +1 and m k τ +1 ) is obtained by the NLMS Prediction System (box 3). W k τ +1 is the window size of the server k in the next τ , and ω k τ +1 is its rate of variations. The Fuzzy System is responsible for determining ω k τ +1 with respect to c k τ +1 , and m k τ +1 (box 4). W k τ +1 is then obtained from the recurrence relation

W k τ + (ω k τ +1 × W k τ )
, and therefore the vector

[W 1 τ +1 , W 2 τ +1 , ..., W z τ +1
] for the whole server z is available (box 5). Among these servers, a server with a higher W τ +1 is selected as the least-loaded server (first box 6). At the same time, the topology, traffic type, and link statistics are identified (second box 6). All possible paths to the selected server are obtained as the set P (box 7). Now, the bandwidth and delay of candidate path are calculated, and then maintained in the two arrays

k k c m   NLMS prediction system 1 1 [ , ,..., ] k k k m m m        1 1 [ , ,..., ] k k k c c c        1 1 ( , ) k k c m     Fuzzy system 1 k    1 1 ( ) k k k k W W W           0 , 1 k k W W  
Select the maximum as the least-load IoT server

1 k W   1 2 1 1 1 [ , ,..., ] z W W W      

Network Statistics Measurement

IoT , , CPU and memory consumption, and is also able to estimate their future values. The details are illustrated in Fig. 7. The input of the system consists of the two vectors X k τ (CP U ) and X k τ (memory), seeking to minimize the mean-square error. The output of this system includes c k τ +1 and m k τ +1 , which are obtained based on the equations ( 13) and ( 14) as well as the two filters g τ and y τ :

i j i j i j B u d , , , (1 )
i j i j i j b B u   
c k τ +1 = g τ X k τ T (CP U ) (13)
m k τ +1 = y τ X k τ T (memory) (14)
For each new data, filters are updated based on the following recurrence equations:

g τ = g τ -1 + µ ε k τ -1 (c)X k τ -1 (CP U ) X k τ -1 (CP U ) 2 (15)
y τ = y τ -1 + µ ε k τ -1 (m)X k τ -1 (memory) X k τ -1 (memory) 2 (16)
Moreover, errors are obtained from the following equations:

ε k τ (c) = c k τ +1 -c k τ +1 (17)
ε k τ (m) = m k τ +1 -m k τ +1 (18)
Note that y 0 and g 0 are initialized (usually with the value of 0). Moreover, µ is a constant parameter called the step size (0 < µ < 2).

3.2.2.2 The proposed fuzzy system for controlling the load window size of IoT servers: As mentioned before,

+ 1 1 ˆi c  i  i i g Input ∑ 1 ]    i  + - - Error Output 1 1 1 1 1 1 ( ) [ , ,..., ] i i i i CPU c c c       1 i c  1 i m  + Input ∑ ∑ ( ) k c   + - - Error Output 1 k m   1 i toq  1 k c   ( ) k m   1 ˆk c   1 ˆk m   g  y  1 1 X ( ) [ , ,..., ] k k k k CPU c c c          1 1 X ( ) [ , ,..., ] k k k k Memory m m m          Figure 7
. The proposed NLMS system for resource estimation in this paper, a window-based load-balancing method is presented. In this method, a window is used to limit traffic sent to the servers. We use fuzzy logic to pinpoint the window size. The proposed Fuzzy System is shown in Fig. 8. As can be observed in Fig. 8, in this method, a fuzzy controller is embedded in order to dynamically change the window size. The fuzzy controller uses c k τ +1 and m k τ +1 as the input, and ω k τ +1 as the output. Their membership functions are fine-tuned using expert knowledge as well as repeated experiments (Fig. 9). The system performance depends strongly on the membership In addition, the fuzzy inference method is Mamdan, while the Center of Gravity (CoG) is used for defuzzification.

ˆk m   1 ˆk c   1 1 W   2 1 W   3 1 W   1 z W   1 1    2 1    3 1    1 z   
In the next step of the fuzzy system design process, the fuzzy rules base is defined (Table 2). The rules are constructed to indicate that greater consumable resources cause higher load; therefore, the size of the window should be smaller. The opposite of this is true as well.

IMPLEMENTATION AND PERFORMANCE EVALUA-TION

The Implementation Testbed

In this study, a testbed is provided based on the Kaa IoT platform [START_REF]Kaa project wiki[END_REF] in order to evaluate the efficiency of the proposed framework (Fig. 10). Kaa is a flexible open source platform for building and managing applications in IoT. Kaa IoT platform consists of Kaa servers and endpoint SDKs. Kaa server implements the back-end part of the platform, and uses Apache ZooKeeper for services coordination. It is comprised of the control, operations, and bootstrap services. An endpoint SDK is a library, which can be used to create clients [START_REF]Kaa project wiki[END_REF].

Fig. 11 illustrates the testbed, which its topology includes three Kaa servers, two Kaa endpoint SDKs, seven OpenFlow switches, and one SDN controller. Further, Kaa servers are Kaa Sandbox [START_REF]Kaa project wiki[END_REF]. Kaa Sandbox is a Kaa instance, which is presented as a stand-alone virtual machine. Kaa uses a random basic mechanism to distribute loads between servers. We use Open vSwitch v2.4.1 [START_REF]Open vswitch[END_REF] and Floodlight v1.2 [START_REF]Floodlight controller[END_REF] to implement OpenFlow switches and controller, respectively. The Floodlight SDN controller is a multi-threaded Javabased controller that uses Netty framework [START_REF]Netty framework[END_REF]. Open vSwitch is a software implementation of a virtual network switch, which supports OpenFlow protocol.

The requirements for the implementation of the proposed method is given in Table 3. The Floodlight controller is run on an HP G9 DL580 hardware. In addition, Kaa servers are run on three Quantic servers (QSR model). The background traffic is generated by using the iPerf Figure 11. The testbed of the proposed framework [START_REF]Network monitoring tool[END_REF], which sends packets at a constant rate. The designed systems and modules are implemented on the controller. Each test is run for three times, and their mean value is considered as the result. Further, φ and µ are considered to have the values of 30 and 0.8, respectively, as based on the performed results analysis, these values provide satisfactory efficiency. Several experiments are conducted to tune these parameters. Also, the bandwidth of each link is 10 Mbps. Table 4 illustrates the details of the network configuration used to perform the experiments. The Load Balancing by Server Response Time (LBBSRT) [START_REF] Zhong | Lbbsrt: An efficient sdn load balancing scheme based on server response time[END_REF], History Window Weighted Average Response Time (HWAR) [START_REF] Montazerolghaem | A load scheduler for sip proxy servers: design, implementation and evaluation of a history weighted window approach[END_REF], and Transaction Least-Work-Left (TLWL) [START_REF] Jiang | Design, implementation, and performance of a load balancer for sip server clusters[END_REF] methods are the most important comparison algorithms in this regard. LBBSRT uses the controller to obtain the response time of each server in order to select a server with minimum the response time. In this regard, the controller sends multiple Packet-out messages to the switches with time interval t and records the transmission time. HWAR is based on the history of the server's response time, which is used to estimate the load being currently processed on 2). Fig. 12 shows the MATLAB Rule Viewer. On the left side, the rules are numbered 1 through 25. These rows of rules apply across each column representing the variables. The leftmost 2 columns are the inputs and below them, the corresponding values chosen for each. The ). This will send less load to the server k and prevent overload. The reverse is also true. If the resource consumption of the server k decreases, then the size of the window will increase, thus sending more load to the server k.

The Experimental Results

In this section, the results of seven experiments are presented. The purpose of the first experiment is to compare the proposed method with other methods in terms of throughput and delay. The second experiment examines the proposed method in different traffic class scenarios. In this experiment, four scenarios are designed according to the traffic classes. In the third experiment, we examine more closely the traffic classes. In this regard, we carefully examine three flows of each traffic class in terms of path bandwidth and delay. Experiment 4 examines how load distribution is performed in the proposed method despite background traffic? The fifth experiment discusses the fairness of the proposed method in distributing the load between servers. Experiment 6 shows how the failure of the switches affects the quality of service. Finally, the seventh experiment analyses the designed controller.

First Experiment: comparison with other mechanisms

Regardless of the traffic class, two groups of Kaa endpoints are used to inject the load on the network in the first experiment (the Kaa endpoints send traffic to the Kaa cluster). Each of these groups generates traffic from 50 to 650 messages per second (mps). Figs. 14 and 15 demonstrate the throughput and response time of servers. Based on the observations, when there is no control for distributing traffic between the Kaa servers, the throughput decreases after the total traffic reaches 700 mps (Fig. 14a), indicating that the capacity of the whole servers is approximately 700 mps. After this threshold, due to the lack of an overload control mechanism, the servers are overloaded, and as a result, the throughput is dropped sharply. This trend continues by increasing the traffic volume until the throughput becomes zero. As shown in Fig. 15a, the servers' response time is almost zero before being overloaded; then, it heavily increases and reaches about 1000 ms. Figs. 14b and 15b represent the basic function of Kaa. As mentioned above, the distribution of the load between the Kaa servers is random in this method, resulting in a relative improvement in performance compared to the method with no control. Accordingly, the drop in throughput and the increase in response time occurs in this method with less intensity. The LBBSRT mechanism uses the servers' response time to estimate their load. Although this criterion is not as accurate as the estimation of resources available to servers, it increases the throughput and reduces the response time compared to the two previous methods (Figs. 14c and15c).

Finally, Figs. 14d and 15d suggest a good performance of the framework proposed in this paper to achieve high throughput and low response time. This framework has been able to provide a precise estimate of server load by proactive resource management, and thus, prevented the servers from overloading and its negative consequences by appropriate load distribution. In this method, the minimum throughput is about 500 mps, while the maximum response time is less than 200 ms. The throughput of all methods in the BW and D-centric scenarios is almost higher than that of the BE-centric scenario, as the shortest path is not usually the highest quality path (Fig. 16). For this reason, the average delay in the BEcentric scenario is higher than that of the rest of the scenarios (Fig. 17). The results of the combined scenario are between the results of three other scenarios, while the results of the BW and D-centric scenarios are almost identical. However, the throughput of methods in the BW-centric scenario is slightly more, and the methods' delay is slightly lower in the D-centric scenario.

By increasing the traffic to up to 700 mps, the throughput increases in all methods and then, decreases in traffic of 900 mps, except for the method suggested in this paper. The proposed method has the maximum throughput in all scenarios even in heavy traffic at 900 mps. Then, HWAR, TLWL, and LBBSRT methods have the most throughput, respectively. The reason for higher throughput of HWAR algorithm compared to other two algorithms is that this algorithm considers the history response times rather than the last response time. The lowest throughput belongs to Round-Robin and Random methods (Fig. 16). In the Round-Robin (RR) algorithm, if the previous packet was assigned to server M , the next message is allocated to server (M + 1)modN , where N is again the number of servers in the cluster.

The methods can be categorized in terms of delay as follows (Fig. 17):

• First category: the least delay including the proposed method; • Second category: the moderate delay including methods of HWAR, TLWL, and LBBSRT; • Third category: the highest delay including Round-Robin and Random methods. Note that the delay of the methods in the second and third categories has a cubic growth at 900 mps.

Figs. 18 and 19 illustrate the load balance between the three Kaa servers by different methods before (traffic of 500 mps) and after overloading (traffic of 900 mps). As observed, the CPU utilization of all scenarios is higher in traffic 900 mps. The resources of some Kaa servers are saturated even in this traffic and in the BE-centric scenario. For example, the Kaa server 3 and Kaa server 1 are saturated in the RR and Random methods, respectively (Fig. 19c). In the BE-centric scenario, the CPU utilization is more than that of other scenarios, and even the load balance between servers fails to operate well because these types of traffic are inherently looking for the nearest server without considering the resources. In the proposed method, the CPU utilization of the three servers is very small and close to each other. The Random method has the worst load distribution due to its lack of knowledge about server resources. The load distribution in TLWL, HWAR, and LBBSRT methods becomes worse in traffic of 900 mps compared to the traffic of 500 mps. However, the proposed method performs better in the load balance independent of traffic and scenario.

Third experiment: QoS of the IoT traffic classes

In the third experiment, we investigated the flows in the proposed method in detail. In this regard, three sample flows (F1, F2, and F3) are considered from three traffic classes in 100 seconds. Fig. 20 depicts path bandwidth and delay of these flows. As illustrated in Fig. 20, the proposed method has considered paths for F1-D to F3-D with a small delay (Fig. 20a). In addition, the paths considered for F1-BW to F3-BW have the highest bandwidth (Fig. 20b). F1-BE to F3-BE paths have a moderate delay and bandwidth. This suggests that the proposed framework has been able to provide QoS for different flows of IoT, as a result of using the SDN technology. Fig. 21 shows the consumption resources of servers and the total throughput of flows in each traffic class. The consumed CPU and memory in all three classes are very low and almost equal (∼ 21%). The throughput of all three classes is also equal and very close to the offered load, as the controller decides for each traffic class according to its nature (Fig. 20).

Fourth Experiment: load balancing in unequal conditions

The fourth experiment involves two scenarios with different background traffic. In Scenario 1, the background traffic of all three Kaa servers is 100 mps while it is 100 mps, 200 mps, and 400 mps for servers 1 to 3 in scenario 2, respectively. The constant traffic of 900 mps is injected into the network for 100 seconds.

Fig. 22 represents the service rate for the Kaa servers. In Scenario 1, since the background traffic of all three servers is equal, then, the service rate of all three servers is equal to approximately 300 mps (Fig. 22a). In other words, the traffic of 900 mps is equally distributed between the three servers. In Scenario 2, the service rate of server 1 is roughly 512 mps, which is the twice of the service rate of server 2 (256 mps) (Fig. 22b), because the background traffic and the consumption resources of server 2 are twice of the server 1. Therefore, in the proposed framework, each server serves according to its background traffic. This experiment indicates that the controller is completely aware of the resources available to the servers.

Fifth Experiment: fairness analysis

The fifth experiment is conducted to verify the fairness of the proposed method. Therefore, two groups of Kaa endpoints inject traffic in four 250-second intervals. Fig. 23 indicates the server's throughput in 1000 seconds with total traffic of 700 mps. In the interval of [0, 250] sec, only group Average CPU Usage (%) Average Memory Usage (%) 1 injects BW traffic. As a result, this class owns the total capacity of the system, which is 700 mps. In the interval [250, 500] sec, the group 1 injects BW and D traffic. In this case, the capacity of the system is equally divided between the two classes of traffic (approximately 358 mps). In the interval [500, 750] sec, group 2 injects BE traffic, in addition to group 1. In this case, the capacity is equally divided between the three classes (approximately 232 mps). Eventually, the combined traffic is also injected into the network in the interval [750, 1000] sec, and the throughput of each of the four classes is equal to approximately 174 mps. Generally, the system's capacity is divided between traffic fairly and independently from the class.

Sixth Experiment: failure assessment in QoS

The sixth experiment examined the impact of the failure in QoS. In this experiment, the traffic of 900 mps is injected into the network for 1000 seconds, and three switches are damaged in three stages. The results are shown in Fig. 24. Before the failure of S5, all network paths are available, and the delay is negligible. With the S5 failure, paths containing the S5 are out of reach, resulting in an increase in the delay. However, the controller directs traffic flows from alternative paths, and therefore, delays are acceptable. Then, S3 is failed and thus, the delay increases again. However, the traffic passes through the S6-S7-S4-S2-S1 path with the controller management, and the delay returns to the normal limit below 200 ms. Finally, S2 fails, and only the S6-S7-S4 path and server 3 are available. In this case, the delay increases to more than 200 ms. Therefore, there is no exponential growth in the delay in any of these failures, due to having a global view by the controller, which can select the best alternative paths and servers with a significant impact on QoS.

Seventh Experiment: controller performance

The final experiment evaluates the performance of the proposed SDN-based controller. Table 5 represents the efficiency of the proposed controller in different traffic. As presented in Table, the controller has been able to handle almost all requests with low response time. Further, its modules do not have overhead because of low CPU utilization and memory. Therefore, the probability of an overload in the controller is very low, and it is not a bottleneck. For a closer look at the two approaches, the ILP Model (optimal solution) for limited cases (limited sources and destinations) of the problem is compared with the SDNbased controller (near-optimal solution). Note that given that the ILP problem is NP-hard, the optimal solution cannot be achieved in polynomial time and increasing the size of the problem exponentially increases the time of ILP Model. We use CPLEX solver to solve ILP Model. In Table 6, the solution value and execution time is provided for various inputs for the two methods. This table shows the proposed SDN-based controller is able to closely resembles the result of ILP. As is evident in this table, execution time significantly increases for ILP method, whereas SDN-based controller has a slow growth. In fact, the proposed framework is a heuristic method to solve global load-balanced and QoSaware routing problem in a IoT communication network.

CONCLUSION AND FUTURE WORK

The traffic management of millions of heterogeneous devices emerging in IoT field is one of the most important aspects in IoT. The rapid evolution of IoT and the different QoS requirements of its traffic classes demand an integrated IoT resource management framework. In addition, IoT suffers from the lack of informed mechanisms for balancing the load of its servers.

The present study proved that balancing the load of IoT servers and simultaneously, satisfying the QoS of IoT traffic is an NP-hard problem considering the resource constraints and massive traffic volume. For this reason, this research provided a novel SDN-based control and management framework for IoT, which supported load balance and QoS simultaneously. In this regard, we designed a predictive and proactive controller equipped with modules based on OpenFlow, sFlow, time-series analysis, and fuzzy logic. The proposed framework was implemented in a real testbed, including Open vSwitch, Floodlight controller, and Kaa IoT servers. To the best of our knowledge, this study practically conducted wide experiments under various scenarios on the Kaa IoT platform, and presented its results for the first time. While utilizing server resources optimally, achieving high throughput and low response time indicate the proper performance of the proposed framework. Achieving fairness, reducing the impact of failure in QoS, and better performance are among other achievements of the proposed framework compared to similar methods.

As our future work, we plan to study the IoT QoS management in the distributed SDN control plane and multi-domain network. Finally, "designing more advanced policies for estimating the IoT servers load," "providing IoT services as softwarization," and "developing IoT framework based on Network Functions Virtualization (NFV) for energy and QoS management" are among the most important future works of the paper [START_REF] Sarrigiannis | Online vnf lifecycle management in a mec-enabled 5g iot architecture[END_REF].

Figure 1 .

 1 Figure 1. An IoT abstract model

Figure 2 .

 2 Figure 2. The best path selection problem to achieve the load balancing of IoT servers and to ensure QoS of IoT traffic

Figure 3 .

 3 Figure 3. The proposed SDN-based IoT framework

Figure 4 .Figure 5 .

 45 Figure 4. An example of software-defined IoT traffic management

  [b 1 , b 2 , ..., b p ] and [d 1 , d 2 , ..., d p ] (first box 8). The equation b p = min{b i,j |(i, j) ∈ p, p ∈ P } explains the bandwidth measurement in the path, where b p is the available bandwidth for the path p, while b i,jis the available bandwidth for any link (i, j) in the path. Available link bandwidth is calculated based on the link utilization rate u i,j and maximum possible link capacity B i,j through the equation b i,j = B i,j × (1 -u i,j ). The equation d p = (i,j)∈p d i,j formulates the delay in the path p where d p refers to the path delay and d i,j indicates the delay of each link (i, j), of which the path p is composed. The IoT traffic class is then specified (second box 8), and accordingly the appropriate path is selected (box 9). Finally, suitable rules are developed (box 10).3.2.2.1 The proposed NLMS system for the load prediction of IoT servers: This system can detect patterns ofSampling of server resources by sFlow agentSave to the database as a history ( , )

Figure 6 .

 6 Figure 6. The flowchart of the proposed controller

Figure 8 .Figure 9 .

 89 Figure 8. The proposed fuzzy system for size control of load windows

Figure 10 .

 10 Figure10. Basic Kaa IoT platform[START_REF]Kaa project wiki[END_REF]

  ω k τ +1 (window variations) [-0.6, 0.4] c k τ +1 (sample of CPU usage) [0, 1] m k τ +1 (sample of memory usage) [0, 1] W k 0 (window size in τ = 0) 1 Traffic load (total) 100-900 mps Background load 100-400 mps y 0 (memory filter with τ = 0) 0 g 0 (CPU filter with τ = 0) 0 servers. HWAR selects a server with the smallest amount of this history. It has an infinite memory capable of recording an immense number of response time values (keeps track of the whole history). TLWL selects a server that has the least work, where work (i.e., load) is based on the relative estimates of transaction costs. In other words, TLWL estimates the server load based on the weighted average of transactions that are currently handled by a server. In this regard, this method maintains a set of counters includes the weighted number of transactions assigned to each server. A new request is allocated to the server with the lowest counter. Figs. 12 and 13 illustrate the relationship between the input and the output values of the proposed fuzzy system. By following these figures, the relations between two inputs ( c k τ +1 , m k τ +1 ) and output (ω k τ +1 ) can be obtained. Based on the performed evaluations, the best range of changes for ω k τ +1 is the interval of [-0.6, 0.4]. The proposed fuzzy rule base has 25 rules (Table

Figure 12 .

 12 Figure 12. The fuzzy system output for [0.628, 0.623]

Figure 13

 13 Figure 13. ω k τ +1 versus c k τ +1 and m k τ +1

4. 2 . 2

 22 Second Experiment: QoS and load balancing in different scenarios In the second experiment, regardless of groups generating traffic, the traffic is injected into the network with different

  (a) No control. (b) Basic Kaa mechanism. (c) LBBSRT mechanism. (d) Proposed mechanism.

Figure 14 .

 14 Figure 14. Servers' throughput by increasing traffic

Figure 15 .

 15 Figure 15. Servers' response time by increasing traffic

Figure 16 .Figure 18 .

 1618 Figure 16. The throughput of different traffic classes in different methods

Figure 19 .Figure 20 .

 1920 Figure 19. The CPU utilization of servers with different traffic classes in various methods (traffic of 900 mps)

Figure 21 .

 21 Figure 21. The consumption of resources and the throughput of traffic flows in the proposed method (total traffic=700 mps)

Figure 22 .

 22 Figure 22. The service rate for Kaa servers in the proposed method with different background traffic (total traffic=900 mps)

Figure 23 .Figure 24 .

 2324 Figure 23. Fairness analysis of the proposed method (total traffic=700 mps)

l = 50 ,

 50 z = 10 l = 60, z = 15 l = 70, z = 20 l = 80, z = 25 v = 8, e = 11 v = 10, e = 15 v = 12, e = 19 v = 14, e = 23

Table 1

 1

		Key Nomenclatures
	V	Set of switches
	E	Set of links
	P	Set of all the routes from s to t
	v	The number of switches
	e	The number of links
	l	The number of IoT gateways
	z	The number of IoT servers
	d i,j	Delay of link (i, j) ∈ E
	b i,j	Bandwidth of link (i, j) ∈ E
	r	The resource consumption of each IoT server
	ρ	The remaining resources of each IoT server
	h	Hop count
	s	Source node (the IoT gateway)
	t	Target node (the most appropriate IoT server)
	qp	QoS of path p ∈ P
	rp	Resource consumption of server on path p ∈ P
	bp	Bandwidth of path p ∈ P
	dp	Delay of path p ∈ P
	hp	Length of path p ∈ P
	Bp

Table 2

 2

				Fuzzy Rules Base (ω i τ +1 changes)
	τ +1 m i	c i τ +1	very low	low	medium	high	very high
	very low	very fast increase (vfi)	fast increase (fi)	increase (i)	very slow decrease (vsd)	slow decrease (sd)
	low		fast increase (fi)	increase (i)	slow increase (si)	slow decrease (sd)	decrease (d)
	medium	increase (i)	slow increase (si)	no change (nc)	decrease (d)	fast decrease (fd)
	high		very slow decrease (vsd)	slow decrease (sd)	decrease (d)	fast decrease (fd)	very fast decrease (vfd)
	very high	slow decrease (sd)	decrease (d)	fast decrease (fd)	very fast decrease (vfd)	extremely decrease (ed)

Table 3 Testbed

 3 Characteristics for the Experiments

			IoT		SDN	OpenFlow	IoT	Background Traffic
			Servers		Controller	Switches	Gateways	Generator
	Software	Kaa Sandbox		Floodlight v1.2	Open vSwitch v2.4.1	Endpoint SDKs	iPerf
	Quantity CPU	3 Dual Core 1.8GHz	1 Xeon E5645 2.4GHz *	7 Dual Core 1.8GHz	2 Xeon E5645 2.4GHz	1 Dual Core 1.8GHz
	RAM		2 GB		4 GB	1 GB	4 GB	2 GB
	Operating System	CentOS v7.2		Linux kernel v3.10	Linux kernel v3.10	CentOS v7.2	Red Hat v6
		* 6 cores -12 threads
	Floodlight Controller
	Kaa Server 1
	Kaa Server 2
	Kaa Server 3
	Kaa Server 4
	Kaa Cluster			Kaa Server 3
		S2	S4
				S7
	S1	S5			Kaa Endpoints
	S3	S6
	Kaa Server 2	OpenFlow	Kaa Endpoints
		Switches

sFlow Kaa Server 1 (Kaa SDK's) (Kaa SDK's) (Kaa Sandbox) (Kaa Sandbox) (Kaa Sandbox) Group 1 Group 2

Table 4 Key

 4 Setup for Experiments (Properties and Parameters)

	Parameter	Properties
	Number of iterations	3 times for each test
	φ (filter order)	30
	µ (step size)	0.8
	Bandwidth of each link	10 Mbps

Table 5

 5 Proposed Controller Performance

	Total traffic (mps)	100	300	500	700	900	1100
	Throughput (fps) ∼	98	297	496	695	894	1093
	Average response time (ms) ∼	14.55	23.75	32.97	44.86	59.68	68.97
	CPU consumption (%) ∼	4.47	8.65	12.75	16.53	25.76	38.97
	Memory consumption (%) ∼	4.01	7.97	10.64	15.75	22.64	33.89

Table 6

 6 Comparison between SDN-based framework and ILP model


Jean-Marc Deshouillers

Adri Án Ubis
email: adrian.ubis@uam.es

INTEGRAL POINTS ON CONVEX CURVES

Keywords: 2010 Mathematics Subject Classification. 11P21. Key words and phrases. Lattice points, convex curves, Farey fractions

We estimate the maximal number of integral points which can be on a convex arc in R 2 with given length, minimal radius of curvature and initial slope.

To the memory of Javier Cilleruelo

Introduction

Evaluating the number of integral points (points with integral coordinates) on finite continuous curves in R 2 is a fairly general Diophantine question. Since the distance between two distinct elements in Z 2 is at least 1, on a simple curve with length there cannot be more than + 1 integral points, a bound which is only achieved for some linear curves.

Besides the study of specific curves, the first general result is due to Jarník [START_REF] Jarník | Über Gitterpunkte auf konvexen Kurven[END_REF] who proved in 1925 that the number of points on a strictly convex arc y = f (x) of length is at most 3(4π) -1/3 2/3 + O( 1/3 ), and that this bound is reached for some arc. From there Jarník deduced a similar result for strictly convex simple closed curves, giving the optimal bound 3(2π) -1/3 2/3 + O( 1/3 ).

In 1963, Andrews [START_REF] Andrews | A lower bound for the volume of strictly convex bodies with many boundary lattice points[END_REF] gave an upper bound for the number N of integral points on the boundary of a strictly convex body in R n in terms of the volume V of that body, which is N V 1/3 when n = 2. Grekos [START_REF] Grekos | Sur le nombre de points entiers d'une courbe convexe[END_REF], in 1988, revisited Jarník's method in the case of strictly convex flat C 2 curves, i.e. curves Γ for which the length = (Γ) is smaller than the minimum of the radius of curvature along Γ. Denoting by r = r(Γ) this minimal radius of curvature and by N = N (Γ) the number of integral points on Γ, he first obtains the upper bound (1.1) N ≤ 2 r -1/3 .

With an unspecified constant, this result can be derived from [START_REF] Andrews | A lower bound for the volume of strictly convex bodies with many boundary lattice points[END_REF].

The second result of [START_REF] Grekos | Sur le nombre de points entiers d'une courbe convexe[END_REF] implies that, up to the constant, (1.1) is best possible, as long as Γ is not too flat -i.e. log / log r > 2/3 -and the lower bound he obtains for families of curves is uniform in terms of the slope w = w(Γ) of the curve (i.e. the tangent of its angle with the x-axis).

The relevance of the slope is pointed out in [START_REF] Deshouillers | Integral points on a very flat convex curve[END_REF]: Grekos and the first named author of the present paper showed that for any strictly convex C 2 curve with a tangent at the origin parallel to the x-axis, the number of its integral points satisfies (1.2) N ≤ 2 /r + /r + 1, a quantity which is essentially less than r -1/3 when log / log r < 2/3. On the other hand, for any α ∈ [1/3, 2/3] they also constructed curves Γ for which N > 0.79 r -1/3 and log / log r = α.

Our main result expresses how the maximal number of integral points on a very flat strictly convex C 2 curve depends on the rational approximation of its slope. In particular, we show that (1.1) is essentially best possible for any fixed initial slope in the case ≥ r 2/3 , which slightly improves on the result of Grekos ( ≥ C r 2/3+ ).

Let us first precise our notation. A strictly convex C 2 curve Γ is (the image of) a C 2 map γ = (x, y) from [0, 1] to R 2 such that x y -x y never vanishes. Up to an isometry which preserves Z 2 (composition of symmetries with respect to the axes or the main bisectors) we may assume that 0 ≤ y (0) ≤ x (0); we then let w = w(Γ) = y (0)/x (0) which belongs to [0, 1]. The radius of curvature of Γ at the point (x(t), y(t)) is given by r(t) = (x 2 + y 2 ) 3/2 /|x y -x y | and we let r = r(Γ) = min t∈[0,1] r(t). We recall that = (Γ) denotes the length of Γ and N = N (Γ) the number of its integral points. We consider curves satisfying (Γ) ≤ r(Γ) and notice that they are really graphs (or arcs) y = f (x).

A real number x can be decomposed in a unique way as x = x +{x}, where x is a rational integer called the integral part of x and {x} is a real number in [0, 1). If {x} = 1/2, there exists a unique integer [x] such that x = |x -[x]| < 1/2; if {x} = 1/2, we define [x] to be x ; in both cases, we call [x] the nearest integer to x.

Finally, for functions f and g ≥ 0, we will also use either f = O(g) or f g as shortcut for |f | ≤ Cg for some positive constant C; f g meaning both f g and g f . With those convention and notation, we have Theorem 1.1 (Main result). There exist two positive numbers c 1 and c 2 having the following property: for any r ≥ ≥ 1 and w ∈ [0, 1], the maximum N w, ,r of N (Γ) where Γ are curves with (Γ) = , r(Γ) = r and w(Γ) = w satisfies N w, ,r ≤ c 2 1 + min( r -1/3 , δ w, r -1 ) (1.3) and c 1 1 + min( r -1/3 , δ w, r -1 ) ≤ N w, ,r , (1.4) with δ w,x = min q∈N (qx + qw ) for x > 0.

Remark 1.2. In the excluded case < 1 we trivially have N w, ,r = 1. When < r 1/3 , Theorem 1.1 says that N w, ,r 1, so the result does not depend on the slope w. The same happens when > r 2/3 , since then the result simply claims that N w, ,r /r 1/3 (due to the inequality δ w,x ≥ x); this is a slight extension of Grekos work [START_REF] Grekos | Sur le nombre de points entiers d'une courbe convexe[END_REF], since he proved it for r 2/3+ . We shall actually show that the result for = r 2/3 /12 implies the case ≥ r 2/3 /12. In that sense, we shall be able to assume that

(1.5) 1 ≤ ≤ r 2/3 /12. Remark 1.3. If w = 0, we have q = 1 and then (1.3) reads N 0, ,r ≤ c 2 (1 + 2 r -1
) which is, up to a constant factor, the first result of [START_REF] Deshouillers | Integral points on a very flat convex curve[END_REF].

Remark 1.4. The construction used in [START_REF] Deshouillers | Integral points on a very flat convex curve[END_REF] for the above mentioned lower bound consists in considering, for α ∈ [1/3, 2/3], curves (selected parts of parabolas) with given r, = r α and w = r -1/3 .

Remark 1.5. It may seem curious to restrict the consideration of the slope to one end point of the curve and one may ask what about the other end, or another point of the curve. Indeed, the consideration of the slope w is relevant only when is less than r 2/3 , in which case the curve is extremely flat and the slope of the tangent can be considered as constant over the whole curve. We let the Reader make this point precise.

Remark 1.6. Following the suggestion of the referee -which the authors thank for it-some illustrations are introduced to help the reader to follow the geometric constructions. On purpose, in the illustrated case, the point D introduced in Lemma 2.2 has a negative ordinate and an abscissa larger than .

Theorem 1.1 is completely uniform, with δ w,x measuring how well w can be approximated by rationals with small denominator. From this result we can derive precise consequences for curves which begin with a fixed rational or irrational slope.

For any w irrational number, we are going to measure its good approximation by rationals by the exponent

β = β(w) = lim sup j→∞ β j
where (a j /q j ) j∈N is the continued fraction of w and β j is defined by the equation

w - a j q j = q -β j j
. This is the same as the irrationality exponent defined in [2, page 168].

If w is a rational number, we define β(w) = ∞. It is known that 2 ≤ β ≤ ∞ and that in that range the set of real numbers with exponent β has Hausdorff measure 2/β (Jarník-Besicovitch). We are going to show that this exponent determines also the number of integral points on curves with initial slope w.

Theorem 1.7 (Curves with fixed initial slope). Let 1/3 < α < 2/3. Let w be an irrational number with β(w) = β. Then, we have

lim sup r→∞ log N w,r α ,r log r = α - 1 3 and lim inf r→∞ log N w,r α ,r log r = min α - 1 3 , 2α -1 + 1 -α β .
In the previous result we excluded the ranges α ≤ 1/3 and α ≥ 2/3 because on them we trivially have

lim r→∞ log N w,r α ,r log r = max 0, α - 1 3 ,
and in particular the result does not depend on w.

Upper bounds

We use what is defined in the previous section. We begin by recalling an upper bound obtained in [START_REF] Grekos | Sur le nombre de points entiers d'une courbe convexe[END_REF] which does not depend on the initial slope (this can also be derived from the bound in [START_REF] Andrews | A lower bound for the volume of strictly convex bodies with many boundary lattice points[END_REF]). This result directly follows from the understanding of the case = r 1/3 . We are going to give an arithmetic proof based on looking at the slopes between consecutive integral points. We hope this will make easier to understand the lower bounds described in section 3.

N w, ,r ≤ 2 r 1/3 + 2.
Proof. The result is a direct consequence of the fact that a curve with length = r 1/3 cannot have more than two integral points. Suppose this were not true. We can assume that 0 ≤ w = tan(θ 0 ) ≤ 1 and x (t), y (t) > 0 throughout the curve. The maximal slope that the curve can reach corresponds to the case of an arc of a circle of radius r, in which case that slope would be w 1 = tan(θ 0 + 2πr ). Since /r = 1/r 2/3 ≤ 1 and w ≤ 1, we have w 1 ≤ w + r . Then, if (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ) are three integral points on the curve with

x 1 < x 2 < x 3 , we have: (a, b) = (x 2 , y 2 ) -(x 1 , y 1 ) and (A, B) = (x 3 , y 3 ) -(x 2 , y 2 ) satisfy a + A < , w ≤ b a < B A ≤ w + r .
Since a, A, b, B are natural numbers, this implies

1 2 < 1 Aa ≤ B A - b a < r which gives > r 1/3 , a contradiction.
We now begin the study of an upper bound for slopes w that are near to a rational a/q with small q. The tools will be geometric in nature. In the case w = 0, in [START_REF] Deshouillers | Integral points on a very flat convex curve[END_REF] it was shown that one can bound the number of integral points on the curve by the number of horizontal lines y = n, n ∈ Z that touch the curve. We shall do the same for the case w = a/q with the "rational" lines y = a q x + n q . The following lemma is essentially in [START_REF] Deshouillers | Integral points on a very flat convex curve[END_REF]. By using that lemma we are going to prove the following result Lemma 2.3. Let 3 < ≤ r/3. Then Γ is included in a parallelogram with two sides parallel to the y axis, two sides having slope w and such that the size of the sides parallel to the y axis is at most 1.6 2 /r and its projection over the x axis has length 1.02 .

Proof. We can assume that 0 ≤ w = tan θ ≤ 1. Throughout the proof of this lemma, we consider coordinates in the frame (A, i, j), with A = (x(0), y(0)) and i (resp. j) is a unitary vector parallel to the x-axis (resp. y-axis). Notice that in the previous lemma we have

|CD| = r - √ r 2 -2 . Figure 2. Illustration of Lemma 2.3 A |A C | = C D Γ 1.02 P Q K j i θ ϕ We begin by showing that |CD| ≤ 0.6 2 /r. To prove it is equivalent to show √ r 2 -2 ≤ r -0.6 2 /r. Both r 2 -2 and r -0.6 2 /r are positive so it is equivalent to r 2 -2 ≥ r 2 -1.2 2 + 0.36 4 /r 2 , i.e. 0.2 2 ≥ 0.36 4 /r 2 , or ( /r) 2 ≤ 0.2/0.36; but we have ( /r) 2 ≤ 1/9 < 0.2/0.36 = 5/9.
Since ≤ r/3, we further deduce that |CD| ≤ 0.6 2 /r ≤ 0.2 and

|AD| = |AC| 2 + |CD| 2 ≤ √ 1.04 ≤ 1.02 , so for any point k = (x k , y k ) in the triangle ACD, we have x k ≤ 1.02 .
On the line x = 1.02 , we consider the point P which is also on the line AC and Q which is also on the line AD. We have the following properties:

(i) Any point in Γ is in the triangle AP Q. (ii) |P Q| ≤ 1.6 2 /r.
The first property is clear. Let us prove the second: if ϕ is the angle between AC and AD, since |CD| ≤ 0.2 , we have

|ϕ -θ| ≤ arctan(0.2) + π 4 ≤ 0.983
which implies cos(ϕ -θ) ≥ 0.55 and since ϕ -θ is the angle between AD and i, the horizontal component of the point D satisfies

x D ≥ 0.55|AD| ≥ 0.55 .

Let C 1 be the intersection of the line AC with the line x = x D . Since θ ∈ [0, π 4 ], we have

|C 1 D| = |CD| cos θ ≤ √ 2|CD| ≤ 0.6 √ 2 2 r and so |P Q| = 1.02 x D |C 1 D| ≤ 1.02 0.55 0.6 √ 2 2 r ≤ 1.6 2 r .
Now the triangle AP Q is contained in the unique parallelogram AP QK satisfying the properties in the statement of the lemma.

We can put the parallelogram from Lemma 2.3 inside one with two sides having rational slope a/q and the other two sides being vertical. This gives the following result. Let q ≥ 1 and 0 ≤ a ≤ q with (a, q) = 1. If 3 < < r/3 then Γ is included in a parallelogram with two sides parallel to j, two sides having slope a/q and the size of the sides parallel to j is at most 1.02 |w -a/q|+1.6 2 /r. Now, it is possible to control the integral points inside such a parallelogram by grouping them onto lines of slope a/q, the number of those lines being easy to understand. Lemma 2.5 (Integral points in a rational parallelogram). Let q and a be coprime integers with q ≥ 1 and a ≥ 0, let u, v, h, k be real numbers with h > 0 and k > 0 and let P be the parallelogram with vertices (u, v), (u, v + h), (u + k, v + ak/q), (u + k, v + h + ak/q). The number of straight lines with slope a/q which contain at least one integral point from P is at most equal to qh + 1.

Proof. Let y = ax/q+m be the equation of such a straight line. Since it contains at least one integral point, mq is an integer j. Since it contains one point in P, we have v ≤ au/q + j/q ≤ v + h. Thus the number of straight lines we are counting is at most the number of integers j in the interval [vq -au, (v + h)q -au], whence the result.

4. Illustration of Lemma 2.5 (a = 2, q = 3, h = 16 3 ) (u, v) (u, v + h) (u + k, v + ak/q) (u + k, v + h + ak/q)
With the two previous results we can finally prove our upper bound for the number of integral points on Γ.

Theorem 2.6 (Upper bound for "rational" slopes). Let 3 < ≤ r/3 and Γ with (Γ) = be such that for any M ∈ Γ, r(M ) ≥ r. Then for any q ≥ 1, a ≥ 0 and (a, q) = 1, we have

N (Γ) ≤ 2.04q w - a q + 3.2q 2 r + 2.
Proof. By Proposition 2.4, Γ is contained in a parallelogram P, and by Lemma 2.5 the number of lines with slope a/q inside that parallelogram which contain at least one integral point is at most

q 1.02 w - a q + 1.6 2 r + 1.
Now, each integral point on Γ is contained on one of those lines. Moreover, since Γ is strictly convex, each line cannot contain more than two points, so the result follows.

Notice that by choosing the best a/q possible in Theorem 2.6 we get the bound N w, ,r 1 + δ w, r -1 from Theorem 1.1 , and considering also Proposition 2.1 we have (1.3). In the following section we shall show that those bounds are the only restrictions for N w, ,r .

Lower bound for "irrational" slopes

The proof of Proposition 2.1 shows a relationship between integral points on the curve and rational slopes. For obtaining lower bounds, both Jarník [START_REF] Jarník | Über Gitterpunkte auf konvexen Kurven[END_REF] and Grekos [START_REF] Grekos | Sur le nombre de points entiers d'une courbe convexe[END_REF] used Farey fractions as slopes in order to build curves with many integral points. We begin by writing a general result capturing those ideas. Lemma 3.1 (Curve with Farey tangents). Let I be an interval contained in [0, 1] with |I| ≤ 1/30. Let M ∈ N and F M be the family of Farey fractions with denominators up to M . If |F M ∩ I| ≥ 3, then there exists a twice differentiable curve Γ ⊂ R 2 such that (i) its length is at most 32M 3 |I|, (ii) its radius of curvature at each point is in the interval [ 1 16 M 3 , 16M 3 ], (iii) it has at least |F M ∩ I| -1 points with integer coordinates, (iv) the slope at its initial point is

h 1 +h 2 k 1 +k 2 , with h 1 /k 1 and h 2 /k 2 being the first two terms in F M ∩ I. Proof. Let I = [s, s + ∆s]; let us write the elements of F M in increasing order h 0 k 0 < s ≤ h 1 k 1 < h 2 k 2 < . . . < h N k N ≤ s + ∆s < h N +1 k N +1 .
We are going to use those elements to build our curve. We first list N -1 points with integer coordinates, which will be on the curve:

(x 1 , y 1 ) = (0, 0) and ∀j ∈ [2, N -1] : (x j , y j ) = (x j-1 , y j-1 )+(λ j k j , λ j h j ) with λ j = [M 2 /k 2 j ]; we recall that [x] denotes the nearest integer to x. Next, we fix the slope of the curve at the point (x j , y j ) to be tan

θ j = h j + h j+1 k j + k j+1
for 1 ≤ j ≤ N . We are going to use Proposition 6.2 to make sure that a curve satisfying those requirements and the ones in the statement of the lemma does exist. In fact, in order to build the curve between A = (x j-1 , y j-1 ) and B = (x j , y j ), since the line between them has slope tan θ = h j /k j , we check that

tan θ j-1 -tan θ = h j-1 + h j k j-1 + k j - h j k j = - 1 k j (k j-1 + k j ) tan θ j -tan θ = h j+1 + h j k j+1 + k j - h j k j = 1 k j (k j+1 + k j ) . Now, k j+1 + k j > M because otherwise (h j+1 + h j )/(k j+1 + k j ) would be a Farey fraction in F M between h j /k j and h j+1 /k j+1 . Thus, k j+1 + k j ∈ [M, 2M ] for every j, so that tan θ j-1 -tan θ tan θ j -tan θ = - k j+1 + k j k j-1 + k j ∈ [-2, -1/2],
and then by applying Lemma 6.1 we have

α β = tan(θ j-1 -θ) tan(θ j -θ) ∈ [-3, -1/3]. Also |AB| tan θ j -tan θ = λ j h 2 j + k 2 j 1/(k j (k j+1 + k j )) = λ j k 2 j (k j+1 + k j ) 1 + (tan θ) 2 so that |AB| tan θ j -tan θ ∈ 1 2 M 3 , 3 √ 2M 3 ,
and then by Lemma 6.1 we have

|AB| β = |AB| tan(θ j -θ) ∈ 1 3 M 3 , 9M 3 .
By Proposition 6.2 we can build a curve between A and B with radius of curvature between M 3 /16 and 16M 3 , and joining those pieces the same is true between (x 1 , y 1 ) and (x N -1 , y N -1 ).

Moreover, by our definition of the curve, in order to finish the proof we just have to show that its length satisfies the condition in the statement of the lemma. But by convexity and considering the slope of the curve we have Length(Γ) ≤ ∆x + ∆y ≤ 2∆x. On the other hand, by the mean value theorem and our control over the curvature of the curve we have ∆s ≥ ∆ dy dx ≥ 1 16M 3 ∆x so finally Length(Γ) ≤ 32M 3 ∆s and the result follows.

In order to take advantage of the previous result we need to control the distribution of Farey fractions in certain intervals. The question is that for N w, ,r we are interested in the Farey fractions near w, and that depends on whether w is near a rational with small denominator or not. In the first case, that rational repels other rationals, so we would not have other Farey fractions. In the second one, we should have the amount of Farey fractions that would be expected from probabilistic reasoning.

The problem with the analysis in [4, Lemme 3] and [6, Corollary 1] is that their counting of Farey fractions on an interval I only takes into account its length |I| and does not capture the subtlety described in the previous paragraph. We solve that problem with the following result.

Lemma 3.2 (Farey fractions in an interval

). There exists a constant C > 1 such that for any a, q coprime natural numbers with a/q +1/q 2 < 1 and M with M q > C, z > C, the number of Farey fractions with denominators up to M in the interval a q , a q + z M q is at least π -2 z(M/q). Remark 3.3. Notice that for z < 1 the only possible Farey fraction is a/q, so there is a sudden change in behaviour when z increases (especially if q is much smaller than M ).

Proof. We need to count the coprime h, k with 1

≤ k ≤ M such that 0 < h k - a q < z M q which is equivalent to 0 < qh -ak < zk M .
By restricting to M/2 < k < M we see that the number of Farey fractions we want to control is at least

J = M 2 <k<M m< z 2 qh-ak=m (h,k)=1
1.

We can parametrize the integer solutions of qh -ak = m as k = qj -am h = aj -sm with 1 ≤ a ≤ q the inverse of a modulo q and s = aa-1 q . Also, (h, k) = 1 is equivalent to (j, m) = 1, and thus

J = m< z 2 x 2 <j-δm<x (j,m)=1
1 with x = M/q and δ = a/q. Since d|l µ(d) = 0 for l > 1 and equals 1 for l = 1 we have

J = m< z 2 x 2 <j-δm<x d|j d|m µ(d).
By writing j = j * d and m = m * d and rearranging the sums we have

J = d< z 2 µ(d)F (d) with F (d) = m * < z 2d x 2d <j * -δm * < x d 1.
We split the sum as

J = d< y 2 µ(d)F (d) + y 2 ≤d< z 2 µ(d)F (d)
with y = min(z, x). We can estimate

F (d) = m * < z 2d x 2d + O(1) = zx 4d 2 + O z + x d so d< y 2 µ(d)F (d) = d< y 2 µ(d) zx 4d 2 + O z + x d so by using ∞ d=1 µ(d)d -2 = ζ(2) -1 = 6/π 2 we have
S D,D m * < z 2D x 4D <j * -δm * < x D D (log D) 2 m * < z 2D D (log D) 2 z (log D) 2 .
Then, by splitting the sum into dyadic intervals we have

y 2 ≤d< z 2 µ(d)F (d) y 2 ≤2 n < z 2 z (log 2 n ) 2
z so this sum is at most zx/4π 2 for x > C for C large enough, so that we finally get

J ≥ zx 4 5 π 2 - zx 4 1 π 2 = zx π 2 .
Now we are going to build curves with many integral points by using Farey fractions. But we are going to do it just in the "irrational" case, namely when w is not near to a rational with small denominator. Afterwards we shall see that in the other case, the "rational" case, we shall need other tools. Theorem 3.4 (Lower bound for "irrational" slopes). There exists a constant C > 1 such that: for every r, > 1 with 800C 2 r 1/3 < < r 2/3 and w ∈ (0, 1), if there is no rational a/q with q ≤ 800C 4 r 2/3 / and |w -a/q| ≤ 1/qr 1/3 then we can build a curve Γ in R 2 satisfying the following properties:

(i) Γ is twice differentiable and its radius of curvature is always in the range [C 3 r/32, 32C 3 r],

(ii) the length of Γ is less than , (iii) the initial slope of Γ is w,

(iv) |Γ ∩ Z 2 | ≥ 1 3200π 2 C r -1/3 . Proof.
Dirichlet lemma tells us that there is always an irreducible rational a/q with q < r 1/3 such that |w -a q | ≤ 1 qr 1/3 , and by our hypotheses we can assume that q > 800C 4 r 2/3 / .

We shall be able to choose C as the maximum of 8π 2 and the constant in the statement of Lemma 3.2. Pick M = C[r 1 /3 ]. By applying Lemma 3.1 with the interval I = [a/q, a/q+ /400C 3 r] and by Lemma 3.2, since M > Cq and z = M r q 400C 3 > C we can build a curve Γ with at least zM/q π 2 -1 ≥

zM/q 2π 2 = 1 2π 2 400C 3 r M 2 ≥ 1 1600π 2 C r 1/3
points with integer coordinates, with radius of curvature always in the range [M 3 /16, 16M 3 ], length at most 32M 3 /400C 3 r ≤ 3 4 and with initial slope

tan θ = a + h 2 q + k 2 .
In order to finish building our curve Γ, we only need to fix the problem that the initial slope should be w = tan θ w instead of tan θ, but

| tan θ -tan θ w | ≤ a + h 2 q + k 2 - a q + a q -w ≤ 1 qM + 1 qr 1/3 ≤ 1 400C 4 r .
Then, if w ≤ a+h 2 q+k 2 , by prolonging Γ to the left maintaining the curvature constant we can make sure that the initial slope is w and the length of Γ will be the length of Γ plus at most the length of an arc of a circle of radius 16M 3 and angle θ -θ w , namely

Length(Γ) ≤ 3 4 + (θ -θ w )(16M 3 ) ≤ 3 4 + 1 400C 4 r 16M 3 ≤ ,
by the inequality θ -θ w ≤ tan θ -tan θ w . On the other hand, in the case w > a+h 2 q+k 2 , we shall delete the first part of Γ to get Γ, precisely until the slope is w. In doing so, we delete some of the points with integer coordinates belonging to Γ. By construction, the number of points which we counted previously and we are deleting now is at most 1 plus the number of Farey fractions with denominator up to M in the interval a q , w .

Since the distance between two consecutive Farey fractions is at least M -2 , the number of them in that interval is at most

1 + M 2 |w - a q | ≤ 1 + M 2 1 qr 1/3 ≤ 1 400C 2 r -1/3 .
Thus, the number of "surviving" integral points is at least

1 1600π 2 C l r 1/3 - 1 400C 2 r -1/3 ≥ 1 3200π 2 C r 1/3 .

Lower bound for "rational" slopes

Now we are going to handle the "rational" case, that is when w is near to a rational a/q with small q. In this case, the method of Farey fractions stops working when < r 2/3-, since then there will not be any rational with denominator up to r 1/3 in the interval ( a q , a q + r ). We know from the proof of Theorem 2.6 that in this case we can essentially control the amount of points in the curve by the number of lines y = a q x + n q , n ∈ Z that touch the curve (since by convexity the curve cannot have more than two points on a line).

Then, in order to build a curve with many integral points, we shall explicitly choose a sequence of integral points ((x n , y n )) 0≤n≤N , with (x n , y n ) belonging to the the line y = a q x + n q such that they can be put on a curve with the requested curvature, slope and length.

From the point of view of slopes, we can say that the fractions relevant to the problem can be parametrized in terms a, q. We shall split the proof into two parts: the first one will work for w very near a/q (with q small), and the second one for w near to a/q, but not that much.

Theorem 4.1 (First lower bound for "rational" slopes). Let C > 1, r, > 1 with (800C 4 ) 2 r 1/3 < < r 2/3 , w ∈ (0, 1) and |w -a/q| ≤ /25r for some irreducible rational a/q with q < 800C 4 r 2/3 / , we can build a curve Γ in R 2 satisfying the following properties:

(i) Γ is twice differentiable and its radius of curvature is always in the range [r/16, 16r], (ii) the length of Γ is less than , (iii) the initial slope of Γ is w,

(iv) |Γ ∩ Z 2 | ≥ 1 4 + 1 4 1 (800C 4 ) 6 q 2 /
r. Proof. We can assume that q 2 /r ≥ (800C 4 ) 6 since otherwise we just need to build a curve with at least one integral point, which is trivial. Let us suppose that w ≥ a/q, the other case being similar. Define Ω = q[kr/q 2 ] with k = (800C 4 ) 2 and consider the sequence (x j , y j ) 0≤j≤N with x 0 = 0, y 0 = 0,

∆x j = Ω -a -(j -1)q[Ω 3 /r] ∆y j = a q ∆x j + 1 q ,
with ∆b j = b j -b j-1 , a the number between 1 and q which is the inverse of a modulo q and N = [(1/k)r/qΩ 2 ]. The definition implies that x j , y j ∈ Z. Also, our hypotheses imply that Ω > 800Cq, Ω 3 /r ≥ 1 so that

(4.1) Ω 1 - 1 400C
< Ω -q -N qΩ 3 /r < ∆x j < Ω and in particular ∆x j > 0.

We are going to see that it is possible to build a curve Γ which satisfies the conditions of the statement and contains the previous sequence of points. First we fix the slope of Γ at the point (x j , y j ), with 1 ≤ j ≤ N -1, to be tan θ j = ∆y j+1 + ∆y j ∆x j+1 + ∆x j = a q + 1 q 2 ∆x j+1 + ∆x j .

Now, to see that a curve satisfying the curvature condition in the statement does exist, it is enough to see that we can apply Proposition 6.2 with A = (x j-1 , y j-1 ), B = (x j , y j ), T A and T B lines with slopes tan θ j-1 and tan θ j respectively, and ρ = r. Since the line between A and B has slope tan θ = ∆y j ∆x j = a q + 1 q 1 ∆x j by using (4.1) we have

tan θ j-1 -tan θ = 1 q ∆(∆x j ) ∆x j (∆x j-1 + ∆x j ) = - [Ω 3 /r] 2Ω 2 (1 -) 2 , tan θ j -tan θ = - 1 q ∆(∆x j+1 ) ∆x j (∆x j+1 + ∆x j ) = [Ω 3 /r] 2Ω 2 (1 -) 2 , with 0 < , < 1/400C, so tan θ j-1 -tan θ tan θ j -tan θ ∈ [-1/(1 -1/400C) 2 , -(1 -1/400C) 2 ]
and since C ≥ 1 , by Lemma 6.1 , we have

α β = tan(θ j-1 -θ) tan(θ j -θ) ∈ [-3, -1/3]. Moreover |AB| = s∆x j with 1 < s < 2 and β = tan(θ j -θ) = t(tan θ j - tan θ) with 1/2 < t < 3, hence |AB| βρ = s∆x j rt(tan θ j -tan θ) = s t Ω(1 -) r[Ω 3 /r]/2Ω 2 (1 -) 2 = = 2s t (1 -)(1 -) 2 Ω 3 /r [Ω 3 /r] ∈ [1/3, 9],
for some 0 < , < 1/400C, so indeed we can build a suitable curve between A and B. By convexity , the length of Γ is at most

j≤N (∆x j + ∆y j ) ≤ j≤N 3∆x j ≤ 3( 1 k r qΩ 2 )Ω ≤ 6 k 2 l ≤ 800 .
Then, the curve Γ we have just built, beginning at the point (x 1 , y 1 ), satisfies all the requirements but not necessarily the one about the initial slope. By (4.1) we have

tan θ 1 - a q = 1 q 2 ∆x 2 + ∆x 1 ≤ 1 q 1 (1 -1/400C)Ω ≤ 4 k r ≤ /r 800 .
so the condition w -a/q < /25r implies that

| tan θ 1 -w| < 1 20 r .
Thus, as in the proof of Theorem 3.4, it is enough to enlarge the curve Γ by an arc of a circle of radius at most 16r and angle at most /20r. Then, the expanded curve will satisfy the initial condition and have length at most 800 + 16r 1 20 l r < .

Theorem 4.2 (Second lower bound for "rational" slopes). Let C > 1, r, > 1 with (800C 4 ) 2 r 1/3 < < r 2/3 and w = tan θ w with 0 < w < 1 and /25r < |w -a/q| ≤ 1/qr 1/3 for some irreducible rational a/q with q < 800C 4 r 2/3 / . We can build a curve Γ in R 2 satisfying the first three properties in Theorem 4.1 and

|Γ ∩ Z 2 | ≥ 1 4 + 1 4 1 (800C 4 ) 6 q w - a q .
Proof. We can assume that q |w -a/q| ≥ (800C 4 ) 6 . We also suppose that w ≥ a/q. We proceed to build the sequence and the curve as in the proof of Theorem 4.1 , but define

Ω = q 1 q(qw -a)
.

By our hypotheses we again have Ω > 800Cq and Ω 3 /r ≥ 1, so that the curvature condition is satisfied (since those inequalities are the only thing about Ω that we used to get the curvature condition in the proof of Theorem 4.1). Now, we are going to keep just the part of the curve which has the first M = 1 (800C 4 ) 6 q w -a q points from the sequence. This is possible since

M ≤ N = [(1/k)r/qΩ 2 ] occurs whenever w - a q ≥ 16 k 2 r ,
which is true due to our hypothesis |w -a/q| ≥ /25r. Thus, this curve also has the desired number of integral points. Moreover, its length is at most

j≤M (∆x j + ∆y j ) ≤ j≤M 3∆x j ≤ 3M Ω ≤ 800 .
It remains to see what with the initial slope. We have

∆x 1 = Ω -a = 1 qw -a -δq
for some 0 < δ < 2, hence the slope of the line between (x 0 , y 0 ) and (x 1 , y 1 ) is

tan θ = a q + 1 q 1 1 qw-a -δq = a q + w -a/q 1 -δq(qw -a) = w + δ(qw -a) 2 1 -δq(qw -a) and since |q(qw -a)| ≤ 1/4 we have 0 < tan θ -w < 4(qw -a) 2 ≤ 4 r 2/3 ≤ 1 1600 r . Moreover 0 < tan θ 1 -tan θ ≤ Ω r ≤ 1 r(qw -a)
≤ 1 1600 r since we assumed q |w -a/q| ≥ (800C 4 ) 6 . Thus, finally we have 0 < tan θ 1 -w < 1 800 r so we can finish as in the proof of Theorem 4.1 by enlarging the curve to the left of (x 1 , y 1 ) with an arc of a circle.

Proofs of the main results

We begin by proving Theorem 1.1. First we are going to show that, as mentioned in Remark 1.2, we can restrict ourselves to the case ≤ r 2/3 /12. If r 2/3 , Theorem 1.1 says that N w, ,r r -1/3 . Thus, by cutting a curve of length > r 2/3 /12 into pieces of length between r 2/3 /24 and r 2/3 /12 we see that applying the bound N w, ,r r -1/3 for ≤ r 2/3 /12 implies the same bound for > r 2/3 /12. Regarding the lower bound, we can assume first that r is sufficiently large, since in the case ≤ r 1 trivially N w, ,r 1. We begin by building a curve Γ 1 with initial slope w ≤ 1, length (500r) 2/3 /24 and radius of curvature larger than 500r, with r 1/3 integral points. If this curve ends at a point A with slope tan θ 1 , we build another curve Γ 2 with the same conditions but initial slope tan(θ 1 + 2r -1/3 ). Consider the point B such that the line passing through A and B has slope tan(θ 1 + r -1/3 ) and the distance from A to B equals r 2/3 . By an integral translation, we can assume that the initial point B of Γ 2 is at distance at most 1 from B. This implies that

|AB| = r 2/3 + O(1) ∼ r 2/3 , tan(AB, T A ) = -r -1/3 + O( 1 r 2/3 +O(1)
) ∼ -r -1/3 with T A the line tangent to Γ 1 at A, and tan(AB, T B ) ∼ r -1/3 with T B the line tangent to Γ 2 at B. Then, we can apply Proposition 6.2 with ρ = 250r to join Γ 1 to Γ 2 so that the full curve is C 2 and of length O(r 2/3 ). We continue this procedure with curves Γ 1 , Γ 2 , Γ 3 , . . ., joining Γ i to Γ i+1 until we get a C 2 curve Γ with length at most , radius of curvature at least r and ( /r 2/3 )r 1/3 = r -1/3 integral points. After the last paragraph, we can assume ≤ r 2/3 /12. Let q 0 be a natural number for which the minimum δ w, r -1 = min q∈N (q r -1 + qw ) is reached, and let a 0 = [q 0 w]. This implies (a 0 , q 0 ) = 1, and applying Proposition 2.1 and Theorem 2.6 with a 0 and q 0 we have (5.1) N w, ,r 1 + min( /r 1/3 , δ w, r -1 ).

For l r 1/3 this implies N w, ,r 1. In this range it is trivial to build a curve satisfying the curvature condition and with at least one integral point, so that N w, ,r 1.

Then we can assume Kr 1/3 < ≤ r 2/3 /12 for any fixed constant K. Then we can apply either Theorem 3.4 or Theorem 4.1 or Theorem 4.2 in order to get the bound N w, ,r 1 + min( /r 1/3 , ( qw + q /r)).

for some q ∈ N, which clearly implies N w, ,r 1 + min( r -1/3 , δ w, r -1 ) so from this and (5.1) we deduce Theorem 1.1. Now we are going to derive Theorem 1.7 from Theorem 1.1. For w rational this deduction is trivial. For w irrational, let us pick any r sufficiently large, and choose the pair of convergents q j , q j+1 of w such that (5.2) q j ≤ r 1/3 < q j+1 .

In this range 1 2q j q j+1 ≤ w -a j q j ≤ 1 q j q j+1 ≤ 1 q j r 1/3 and we can show that min(r -1/3 , δ w, r -1 ) ≤ min(r -1/3 , q j w +q j r -1 ) ≤ 10 min(r -1/3 , δ w, r -1 ) with = r α . The first inequality comes from the definition of δ w, r -1 ; if the second were not true we would have δ w, r -1 < r -1/3 10 and then q < r 1/3 10 , qw < r -1/3 10 for the q such that δ w, r -1 = qw + q r -1 , and this would the inequality (qq j ) -1 ≤ |w -a q | + |w -

a j q j |, a = [qw].
Then, by Theorem 1.1 we have N = N w,r α ,r min r α-1/3 , q j r 2α-1 + r α /q β j -1 j since q j+1 q β j -1 j

. This also gives the inequality q j ≤ r 1/3 q β j -1 j

. By choosing r 1/3 = q j we have q j r 2α-1 = (r α-1/3 ) 2 ≥ r α-1/3 so N r α-1/3 and the result for the upper limit follows. On the other hand, any r in the range (5.2) can be written as r q 3θ j with 1 ≤ θ ≤ β j -1 or, in other terms, q j r with 1/3(β j -1) ≤ ≤ 1/3. Then N min(r α-1/3 , r +2α-1 + r α-(β j -1) ). Now, we want to compute the minimum of this function N = N ( ) in the interval 1/3(β j -1) ≤ ≤ 1/3. Since r α-1/3 is constant in , we only need to look at the minimum of the second term. Moreover, both at = 1/3(β j -1) and = 1/3 we have N ( ) r α-1/3 , so we only need to check the case in which the second term has a minimum in the interior of the interval, and this happens at = (1 -α)/β j whenever

1 3(β j -1) < 1 -α β j < 1 3 .
The second inequality is always true, but the first amounts to

β j > 1 + 1 2 -3α .
In this case, the minimum for the second term is r 2α-1+ 1-α β j . This implies the result for the lower limit.

Appendix

Lemma 6.1 (Trigonometric lemma). Let tan θ and tan(θ + β) be in the interval [s, s + ∆s] ⊂ [0, 1], with 0 ≤ ∆s < 1/2. Then we have

1 -∆s ≤ tan(θ + β) -tan θ (1 + (tan θ) 2 ) tan β ≤ 1 -∆s 1 -2∆s .
Proof. The formula for the tangent of the sum of two angles gives

tan(θ + β) -tan θ = tan β 1 + (tan θ) 2 1 -tan θ tan β , which implies | tan β| ≤ | tan(θ + β) -tan θ|(1 + | tan β|) ≤ ∆s(1 + | tan β)
so that | tan β| ≤ ∆s/(1 -∆s). Substituting this bound into the previous identity ends the proof.

The following result is essentially a variation on construction in [START_REF] Grekos | Sur le nombre de points entiers d'une courbe convexe[END_REF].

Proposition 6.2. Let A and B be two points in the euclidean plane E = R 2 , T A ( resp. T B ) be a straight line containing A ( resp. B) and α, β, ρ 1 , ρ 2 , ρ be real numbers such that

(i) tan(AB, T A ) = α and tan(AB, T B ) = β, (ii) β ∈ (0, 1/3], α ∈ [-3β, -β/3] and 0 < ρ ≤ min(ρ 1 , ρ 2 ), (iii) |AB| ∈ [(1/3)βρ , 9βρ].
There exists a two times differentiable curve with end points A and B, which admits for tangent at the point A ( resp. B) the line T A ( resp. T B ), such that its radius of curvature is always between ρ/250 and 250 max(ρ 1 , ρ 2 ) and which takes the value

(1 + α 2 ) 3/2 ρ 1 ( resp. (1 + β 2 ) 3/2 ρ 2 ) at the point A( resp. B).
We first prove a technical Lemma, in the spirit of Lemma 1 in [START_REF] Grekos | Sur le nombre de points entiers d'une courbe convexe[END_REF].

Lemma 6.3. Let ρ > 0, a < b, β > 0, α = -λβ with λ ∈ [1/3, 3] be real numbers such that (6.1) (1/3)βρ ≤ b -a ≤ 9βρ.
There exists a differentiable real function f defined on [a, b] such that

(i) f (a) = α and f (b) = β, (ii) f (a) = 1/ρ 1 , f (b) = 1/ρ 2 , (iii) ∀x ∈ [a, b] : 0.01/ max(ρ 1 , ρ 2 ) ≤ f (x) ≤ 100/ρ, (iv) b a f (t)dt = 0.
Proof. We consider the points M A = (a, α) and M B = (b, β). The slope of the segment M A M B lies in the interval [0.3/ρ, 12/ρ]: we have indeed

0.3 ρ ≤ 4 9ρ ≤ (4/3)β 3βρ ≤ β(1 + λ) b -a = β -α b -a = β(1 + λ) b -a ≤ 4β βρ/3 = 12 ρ .
This implies that the straight lines D A passing through M A and having the slope 0.01/ρ < 0.3/ρ and the lines D B passing through M B and having the slope 100/ρ > 12/ρ will meet at a point M 1 = (x 1 , y 1 ) with a < x 1 < b and α < y 1 < β.

We now consider the function We incorporate this last relation in (6.3) and get 2I 1 /(ρβ 2 ) ≤ 99.99 × 0.9981λ 2 + 0.01 -100λ 2 < 0.01 -0.19λ 2 < -0.011, which proves that I 1 is negative. For δ positive and sufficiently small, we also have b a (h 1 (x)+2δ)dx < 0. We can then slightly modify the function h 1 + δ to get a function f 1 (x) which satisfies the conditions (i), (ii) and (iii) of Lemma 6.3 and such that J 1 = b a f 1 (x)dx < 0.

In a similar way, considering first the straight lines ∆ A (resp. ∆ B ) passing through M A (resp. M B ) and having the slope 100/ρ (resp. 0.01/ρ), one can construct a function f 2 (x) which satisfies the conditions (i), (ii) and (iii) of Lemma 6.3 and such that J 2 = b a f 2 (x)dx > 0.

The function f defined by f (x) = (J 2 f 1 (x) -J 1 f 2 (x))/(J 2 -J 1 ) satisfies the conditions (i), (ii), (iii) and (iv) of the Lemma 6.3.

For a two times differentiable function g, we denote by rad g (x) its radius of curvature at the point x, given by (6. Relations (i), (ii) and (iii) come directly from Lemma 6.3 and (6.5). Relation (ii) of Lemma 6.3 implies that for all x one has 0.01ρ ≤ 1/F (x) ≤ 100 max(ρ 1 , ρ 2 ); so F is increasing and then |F (x)| ≤ max(|α|, β) ≤ 1; relation (iv) easily follows from those relations and (6.5).

Proof of Proposition 6.2. Let a be a real number and let b = a+|AB|. We consider a direct orthonormal basis of E, in which the coordinates of A (resp. B) are (a, 0) (resp. (b, 0)). The parameters ρ, ρ 1 , ρ 2 , a, b, α, β satisfy the conditions of Corollary 6.4; we can thus consider a function F satisfying Corollary 6.4. The graph of F satisfies Proposition 6.2.

Proposition 2 . 1 (

 21 Local upper bound). For any r, ≥ 1 we have

Figure 1 . 2 AΓLemma 2 . 2 .

 1222 Figure 1. Illustration of Lemma 2.2

Figure 3 . 4 A 1 Proposition 2 . 4 (

 34124 Figure 3. Illustration of Proposition 2.4

Figure

  Figure 4. Illustration of Lemma 2.5 (a = 2, q = 3, h = 16 3 )

2 µ 4 5 π 2 .

 242 (z + x) log y) so for z, x > C with C large enough we have d< y (d)F (d) ≥ zx To control the other sum let us look at S D,D = D≤d<D µ(d)F (d) for any x ≤ D ≤ D ≤ 2D. Rearranging the sums we have |S D,D | ≤ m * < z 2D x 4D <j * -δm * < x D a j * ,m * <d<b j * ,m * µ(d) for some a j * ,m * , b j * ,m * in the interval [D, 2D]. Thus, applying the prime number theorem we have

1 = b a h 1 From ( 6 . 2 )so y 1 β 2 ≤

 11622 h 1 defined on [a, b], linear on [a, x 1 ] and on [x 1 , b] and which takes the values: h 1 (a) = α, h 1 (x 1 ) = y 1 and h 1 (b) = β. Let us show that I (x)dx < 0. We have 2I 1 = (x 1 -a)(α + y 1 ) + (b -x 1 )(β + y 1 ); The coordinates of the point M 1 are defined by (6.2) y 1 -α x 1 -a = 0.01/ρ and β -y 1 b -x 1 = 100/ρ, from which we get 2I 1 = ρ 100(y 2 1 -α 2 ) + 0.01(β 2we can compute y 1 and get 1 ρ = 100(y 1 -α) + 0.01(βy 1 ) -a)/(ρβ) ∈ [1/3, 9] and λ ∈ [1/3, 3], we have -99.893λ ≤ -100λ+1/3-0.01 ≤ 99.99(y 1 /β) ≤ 9-(100λ+0.01) < 0, and 0.9981λ 2 .

Corollary 6 . 4 .

 64 Let min(ρ 1 , ρ 2 ) ≥ ρ > 0, a < b, β ∈ (0, 1/3], α = -λβ with λ ∈ [1/3, 3] be real numbers such that(6.6) 1/3βρ ≤ b -a ≤ 9βρ.There exists a two times differentiable real function F defined on [a, b] such that(i) F (a) = F (b) = 0, (ii) F (a) = α, F (b) = β, (iii) We have rad F (a) = ρ 1 (1 + α 2 ) 3/2 and rad F (b) = ρ 2 (1 + β 2 ) 3/2 , (iv) ∀x ∈ [a, b] : rad F (x) ∈ [0.01ρ, 300 max(ρ 1 , ρ 2 )].Proof. For the given parameters ρ, ρ 1 , ρ 2 , a, b, β, λ, we construct a function f satisfying the conditions of Lemma 6.3. We define ∀x ∈ [a, b] : F (x) =x a f (t)dt.

Acknowledgements

This work has been initiated during a visit of J-M D. at ICMAT (Madrid); both authors have been partially supported by the grant MTM2014-56350-P. J-M D. also acknowledges the support on the CE-FIPRA project 5401 and the ANR-FWF project MuDeRa.