domain: math shs

text:
Jiří Vančura
email: jivancura@gmail.com

Research on the language barriers of students who use Khan Academy as a mathematics homework platform

Keywords: Homework, online assessment, language barrier, electronic resources

Homework is a routine practice in maths classes, and research has shown that the immediate feedback and acknowledgement of effort is important for students. Unfortunately, the traditional classroom setting does not allow for this degree of feedback. Khan Academy offers a free tool that allows teachers to monitor students' activity and provide them with feedback and guidance. In this study, we investigated one Czech high school's use of Khan Academy as a homework platform, focusing specifically on language barriers and their impact on the ability of non-native Englishspeaking students to benefit from Khan Academy. We found that students who faced a lower language barrier were able to make better use of Khan Academy's educational resources. Surprisingly, we also found that a reported language barrier does not significantly correlate with a student's English grades.

Introduction

Every student does maths homework during his or her high school studies. I remember doing most of mine on the way to school or during the break before my maths classes. At the beginning of each maths class, my teacher would walk around the classroom, checking some notebooks randomly to see if there was anything that looked like homework. Since I really enjoyed maths, I did most of my maths homework by myself and then lent it to others to copy. We did not receive much feedback on our homework, so it was no wonder that many students were not very motivated to do their homework on their own. Unfortunately, maths teachers in large classes did not have much of a choice back then. Today, however, new online technologies, such as Khan Academy (KA), offer individualisation, guidance and immediate feedback for students, as well as a great amount of data about student activity for teachers (Khan Academy, 2016a).

The Khan Academy (KA) is a non-profit organisation that runs the website www.khanacademy.org. Since 2008, it has undergone a great deal of development. What started as a list of instructional maths videos has developed into a network of vast educational resources, including interactive exercises covering mathematics, the natural sciences and more, from the elementary to the undergraduate level. Thanks to generous donors, KA is able to provide all of its content for free, and it probably will not be cancelled or monetised any time soon. At the moment, KA's exercises and most of its educational videos are offered in English only, as is the case with many other online resources. We therefore decided to investigate the effects of language barriers on the preferences and attitudes towards KA of students who practise maths using KA exercises.

Thematic Working Group 16

Proceedings of CERME10

Theory

Homework and feedback

Homework assignments are routine in most mathematics classes, including those in high schools in the Czech Republic. There is a great deal of evidence suggesting that monitoring students' work and acknowledging their efforts is very important for students, as it increases the effort they put into their homework [START_REF] Strandberg | Homework -is there a connection with classroom assessment? A review from Sweden[END_REF]. When teachers do not grade a homework assignment and return it promptly, students report feeling like they have wasted their time on this activity [START_REF] Strandberg | Homework -is there a connection with classroom assessment? A review from Sweden[END_REF][START_REF] Wilson | Student perspectives on homework[END_REF]. Students need to believe that their homework is meaningful and that teachers value their efforts [START_REF] Bempechat | The homework experience: Perceptions of low-income youth[END_REF].

When it comes to feedback, there are still important gaps in our understanding [START_REF] Shue | Focus on formative feedback[END_REF]. There is some evidence suggesting that when a task requires material or procedural understanding and analytical problem solving (e.g. mathematics), providing hints and allowing multiple attempts may lead to a greater increase in student performance than simply revealing the correct solutions [START_REF] Clarina | Multiple-try feedback and higher-order learning outcomes[END_REF][START_REF] Attali | Effects of multiple-try feedback and question type during mathematics problem solving on performance in similar problems[END_REF].

Students benefit greatly from timely and meaningful homework feedback. Unfortunately, it is often beyond a teacher's capacity to provide this to every student in a traditional classroom setting. However, technology might be able to help teachers with this. Moreover, technology can prevent misunderstandings between students, teachers and parents about the amount of time students spend on homework, as accurately estimating this can be difficult for teachers in the traditional classroom setting [START_REF] Strandberg | Homework -is there a connection with classroom assessment? A review from Sweden[END_REF].

Language barriers

We did not find many recent studies investigating English language barriers in terms of learning mathematics or learning in general. There have been some studies that have investigated non-native English-speaking students in an English-speaking environment, both at the high school [START_REF] Adams | Using inquiry to break the language barrier in chemistry classrooms[END_REF] and university [START_REF] Variawa | Identifying language as a learning barrier in engineering[END_REF] levels. However, these are not very relevant to our investigation, as they study foreign students in Englishspeaking communities and focus on different subjects (e.g. chemistry, engineering).

For the purposes of this study, we define a language barrier as English language difficulties, as perceived by students when interacting with the Khan Academy website.

Khan Academy

KA has been providing interactive exercises for only a few years, so it has not yet been heavily researched. However, videos have been used for educational purposes for decades. Two recent studies have investigated data from several Massive Open Online Courses to determine the attributes of the more engaging videos [START_REF] Guo | How video production affects student engagement: An empirical study of MOOC videos[END_REF][START_REF] Kim | Understanding in-video dropouts and interaction peaks in online lecture videos[END_REF]. In our previous study, we concluded that KA's videos align well with most of the aforementioned recommendations (Vančura, in press). Our investigation into the possible impact of KA as a homework platform on student attitudes towards mathematics demonstrated that negative impacts are very unlikely (ibid).

A large study was also conducted concerning the implementation of KA in U.S. classrooms [START_REF] Murphy | Research on the Use of Khan Academy in Schools[END_REF]. The results revealed that only 45% of American students reported being able to learn new skills using KA without teacher assistance. We found similar results (46%) in our previous study (Vančura, in press).

Context

In this study, student participants were assigned homework on a weekly basis in the form of KA's interactive exercises. Every exercise consists of a series of problems related to very specific topics. In the exercise shown in Figure 1, students are asked to practise estimating equation solutions using graphs. Specifically, students are required to select the shape of the graph for function g [1]; to graph the function g using the interactive graphing tool [2]; and to estimate the lower solution of equation f(x) = g(x), where function f is given by the graph. Students move on to the next problem until they solve the exercise correctly. If they cannot solve the problem, there are hints [4] that demonstrate step-by-step solutions. Even after the whole solution is revealed, students are still required to graph the function g and estimate the solution correctly. Only then can they continue on to the next problem. Students can also watch instructional videos that explain the solutions to a sample problem in detail [5]. Each student's progress is captured and displayed at the bottom of the screen [6]. Students receive a check mark for solving the problem correctly on the first try without any hints. They get an x mark for entering the wrong solution and a light bulb icon for solving the problem correctly on the first try with some hints.

In order for students to successfully finish an exercise, they must get five (or sometimes three) check marks in a row (i.e. solve five problems on the first try without any hints). This multiple-try mechanism aligns well with the findings on feedback [START_REF] Attali | Effects of multiple-try feedback and question type during mathematics problem solving on performance in similar problems[END_REF]. However, this feedback does not tell students where they have made their mistakes, and it usually provides only one way to solve a problem. Some exercises consist of multiple-choice answers, and students might be tempted to guess the solutions-although the requirement of solving five problems in a row makes guessing time consuming. For example, even if students were able to narrow the choices down to two, they would still need to answer 62 questions on average in order to get 5 in a row correct. If students guessed blindly from 4 choices, they would need to answer 458 questions on average.

Another important tool that KA offers is the teacher dashboard, which allows teachers to monitor student activity. Teachers can see when students work on exercises, which exercises they work on and how well they solve the problems. Teachers can even see the amount of time students spend on each problem, as well as the total time they spend on KA. This data allows teachers to monitor, acknowledge and assess students' homework objectively and meaningfully. Moreover, in our study, these attributes allowed teachers to grade homework on a weekly basis.

Based on the results of one SRI study [START_REF] Murphy | Research on the Use of Khan Academy in Schools[END_REF], student participants were not required to learn new skills on KA; rather, they had to practise skills they had already acquired.

Methodology

Research questions

1. Does a student's language barrier influence whether he or she prefers KA homework over homework from traditional textbooks?

2. How does the language barrier influence students' attitudes towards KA and their ability to learn maths while using it?

As the research progressed, we saw that language barriers did play an important role, which made us add a third question of interest:

3. Can the language barriers of individual students be easily and reliably estimated (i.e. by asking the student's English teacher)?

Data collection

We developed two surveys based on the surveys used in the SRI study [START_REF] Sri | Research on the Use of Khan Academy in Schools, surveys[END_REF], although we added some questions about English language usage and omitted some questions that were irrelevant to our investigation. The first survey was administered in December 2015, and the second was administered in June 2016. Both surveys contained several pairs of verification questions to detect inconsistencies or carelessly filled-out surveys. To measure the language barrier, we used Likert-scale questions, such as, "My limited English knowledge prevents me from using Khan Academy effectively." To measure the preference for the KA homework platform, we used Likertscale questions, such as, "I prefer to solve examples from common textbooks rather than from Khan Academy." Surveys were administered during an ordinary maths class so that the students had no reason to hurry. We also collected students' midterm and final grades in mathematics and English for the 2015-2016 school year.

At the beginning of September 2016, we asked the students' English teachers to estimate the reading and listening abilities of the participating students, as well as the effects of the students' language barriers when using English mathematical software. The teachers were asked to use the Common European Framework of Reference for Languages (A1-C2) for their estimations (Council of Europe, 2016), which were then recoded on a scale of 1-6.

Participants and criteria of analysis

The first survey was administered to 141 non-native English-speaking students aged from 15 to 20 years old from 7 maths classes in 2 Prague high schools. For the second survey, the participants included 83 students from 5 out of the 7 classes that participated in the first survey. All of the students were learning English as their second or third language. A total of 64 students participated in both surveys. The students in our study were taught by six different English teachers, who were asked to estimate the students' language barriers. The author of this paper was the maths teacher for two of the seven classes. Therefore, we looked for relative patterns (i.e. connections between the students' language barriers and their learning independence) rather than for absolute results. When investigating absolute results, such as student preference for KA over traditional textbooks, we also considered the differences between the students who were taught by the researcher and those who were not.

To measure the language barriers, we required Cronbach's alpha to be greater than 0.7, which is generally considered to be an acceptable level of consistency. When it came to correlations and hypothesis testing, we used the 5% significance level.

Results

In the first survey, students reported a strong preference for KA over traditional textbooks (Vančura, in press). This preference decreased significantly in the second survey, although KA was still preferred. In both surveys, the students who were taught by the researcher did not report a stronger preference for KA than the other students. Students' preference for KA was significantly correlated with reported language barriers (see Figure 2). Students with greater language barriers tended to prefer KA less. Even so, students who reported significant difficulties with English preferred KA over traditional textbooks.

Both surveys revealed a significant connection between the students' reported language barriers and several other factors. In both surveys, students with lower language barriers a. found KA videos and exercises to be more helpful for them (correlations 0.18-0.45); b. reported higher autonomy when learning new skills using KA (0.17-0.28); and c. reported a more adequate understanding of their skills while working in KA (0.22-0.29).

The reported levels of language barriers decreased slightly between the two surveys, but this decrease was not statistically significant. Surprisingly, the reported language barriers did not significantly correlate (-0.02, 0.14) with the English grades. We assumed that different teachers would have different grading strategies and standards, so we normalised the English grades within the groups of students taught by each teacher. The resulting correlation increased slightly to 0.16, which is still insignificant in our case. We also calculated the correlation between English grades and the decrease of language barriers between the two surveys; again, the correlation was insignificant (0.02). Driven by these results, we asked the English teachers to evaluate the students' English listening and reading skills, which correlated moderately (0.45, 0.48) with the language barriers reported by the students.

Conclusions and discussion

Homework remains an important part of mathematics education in the Czech Republic. KA can provide students with guidance and immediate feedback, which we believe is the main factor that leads students to prefer KA over traditional textbooks. The decrease in KA preference over time may be attributed to the novelty of this new system wearing off. Still, it is worth noting that even six months (and many working hours) later, KA remained the preferred choice of the majority of the student participants.

We found that language barriers play an important role in both preference and reported utilisation of KA. Students with greater English-language capabilities reported a higher ability to use KA learning resources, which we believe to be a strong factor behind their stronger preference for KA over traditional textbooks. We can assume that similar patterns would appear with other online educational resources-the number and quality of which continues to grow rapidly, and which would take a great deal of time to translate into Czech. Notably, KA is one of the most-translated educational resources in the Czech Republic. However, despite great effort from the non-profit organisation Khanova Škola (Khanova škola, o.s., 2016), only about 35% of KA's videos have subtitles, while fewer than 1% have Czech dubbing. If we want students to benefit from these growing resources, then we need to prepare our students for learning in English.

The last result of our study was that students' English grades did not significantly correlate with their reported language barriers (i.e. the 'best' English students did not typically feel better able to overcome their language barriers than the struggling students). This pattern held true even after six months of using KA. We assumed that the students would learn to overcome these barriers over time, as they used the English resources over the course of the study. Our study did indeed show that the reported language barriers decreased slightly, albeit insignificantly.

The teachers' evaluation of the students' English reading and listening skills correlated significantly (0.45, 0.48) with the language barriers reported by the students, so such evaluation could provide a very rough estimate of the language barriers faced by a group of students. However, this correlation was not strong enough to provide a reliable estimate of the barriers faced by the individual students, as it only explained about 23% of it (0.48 2 = 0.23). Ultimately, we were unable to find a quick and reliable way to estimate the individual students' self-reported language barriers.

Limitations and future research

The small size of our sample made it impossible for us to find small correlations or inconspicuous patterns. Larger samples would have also allowed us to verify our results at a higher confidence level. The disconnection between the reported language barriers and the students' English grades could also be a local phenomenon, since every Czech school has its own curriculum.

In this study, we relied mostly on students' opinions, which might not have been completely accurate (i.e. even though students reported that they could make good use of KA resources, that does not necessarily mean that they did).

The results also showed that the English courses currently being offered to students might not be sufficient to prepare them to learn mathematics in English using tools like KA. Therefore, determining how to help students learn in English might be an interesting question for researchers and a challenge for both maths and English teachers.

While KA offers a great variety of exercises, its narrow focus (i.e. graphing quadratic functions in vertex forms) and repetitive nature might produce very formal knowledge that cannot be transferred.

In future study, we would like to investigate what students actually learn using KA and how it might be affected by their language barriers.

As with every digital resource, KA sometimes experiences technical problems. Exercises can fail to load properly and data might not show up in the teacher dashboard. Therefore, it is a good idea to consider possible technical problems before judging students too quickly.

Figure 1 :

 1 Figure 1: Interactive exercise (Khan Academy, 2016b)

Figure 2 :

 2 Figure 2: Student preference for the KA homework platform by language barrier in the first survey

Proceedings of CERME10


Bastien Confais

Adrien Lebre

Benoît Parrein

A Tree-Based Approach to locate Object Replicas in a Fog Storage Infrastructure

Fog Computing infrastructures have been proposed as an alternative to Cloud Computing to provide computing with low latency for the Internet of Things (IoT). A few storage systems have been proposed to store data in those infrastructures. Most of them are relying on a Distributed Hash Table (DHT) to store the location of objects which is not efficient because the node storing the location of the data may be placed far away from the object replicas. In this paper, we propose to replace the DHT by a tree-based approach mapping the physical topology. Servers look for the location of an object by requesting successively their ancestors in the tree. Location records are also relocated close to the object replicas not only to limit the network traffic when requesting an object, but also to avoid an overload of the root node. We also propose to modify the Dijkstra's algorithm to compute the tree used. Finally, we evaluate our approach using the object store InterPlanetary FileSystem (IPFS) on Grid'5000 using both a micro experiment with a simple network topology and a macro experiment using the topology of the French National Research and Education Network (RENATER). We show that the time to locate an object in our approach is less than 15 ms on average which is around 20% better than using a DHT.

I. INTRODUCTION

While largely adopted, the Cloud Computing relies on few datacenters located far from the users. This model cannot satisfy the new constraints of the Internet of Things (IoT), especially in terms of latency and reactivity. The Fog Computing approach proposed by Cisco in 2012 [START_REF] Bonomi | Fog Computing and Its Role in the Internet of Things[END_REF] consists in deploying from micro to femto datacenters geographically distributed, at the Edge of the network. The proximity to the users enables the Fog infrastructure to provide low latency computing.

Although object stores provide locality and scalability which are two good properties for Fog Computing infrastructures [START_REF] Confais | Performance analysis of object store systems in a Fog/Edge Computing Infrastructures[END_REF], the records containing the location of all objects replicas are often stored without any locality. Most of the time, a Distributed Hash Table (DHT) is used for this purpose [START_REF] Anglano | Using chord for meta-data management in the n3fs distributed file system[END_REF], [START_REF] Dick | Flower-CDN: A hybrid P2P overlay for Efficient Query Processing in CDN[END_REF], [START_REF] Benet | IPFS -Content Addressed, Versioned, P2P File System[END_REF]. When an object is requested, two sites have to be reached: a first one to determine the object location and a second one to actually retrieve the requested object. Finally, a local replica is created to improve the performance for future accesses and the location record in the DHT is updated to reflect this new location. All objects are replicated where they are accessed but the location record is not relocated, we claim that locating an object may be expensive.

In this paper, we propose a location management approach in which the location of objects is replicated on the fly in a tree. Our approach is inspired by the Domain Name System (DNS) [START_REF] Mockapetris | Domain names -concepts and facilities[END_REF] and by some Content Network Delivery [START_REF] Karger | Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web[END_REF] protocols. Its main characteristic is to take into account the physical network topology to relocate the location record along the routing path to the object's replicas. To achieve this, our proposal also includes a method to generate a tree from a network topology adapted to Fog environment. Evaluations using the object store InterPlanetary FileSystem (IPFS) [START_REF] Benet | IPFS -Content Addressed, Versioned, P2P File System[END_REF] on the Grid'5000 testbed [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF] shows our approach reduces the time to locate an object by 20% on average.

The remaining of the paper is organised as follows. In Section II, we describe why a DHT is not adapted for Fog infrastructures. We give a technical background to understand our protocol and we present the assumptions we made in our work. In Section III, we describe our protocol and discuss our method to build the tree. Our approach is then evaluated in Section IV, and finally, related works are presented in Section V before concluding in Section VI.

II. TECHNICAL BACKGROUND

Writing objects on the closest Fog site is a valuable property for an object store working in a Fog infrastructure in order to reduce the access times [START_REF] Confais | Performance analysis of object store systems in a Fog/Edge Computing Infrastructures[END_REF]. A global DHT spread among all nodes is used to store the relation between each object's name and the location of its replicas. Accessing a DHT to find the location of an object has many drawbacks. Soliciting a remote site to get the location of an object impacts the reading performance because the network latency to reach the site storing the location record may be high. The performance of the remote site is also impacted because answering external queries increases the load of the servers. Finally, it prevents the system from working in case of network partitioning: if a site is isolated from the others, nodes cannot locate the objects stored on it. This approach is used in storage solutions such as IPFS, which is an object store relying on a BitTorrent like protocol to exchange the objects between the nodes and on a Kademlia DHT to store the location of these objects.

Two properties are expected from an efficient location management system in a Fog infrastructure. First, location records should be found close to the site accessing the object and secondly we should benefit from data movements between sites to improve the locality: when a site accesses an object and relocates it, other sites should be able to locate this new replica by reaching a closer site than the original one. We illustrate these properties using Figure 1 showing different points of presence of the French NREN (RENATER) topology but also their physical connections with their network link latencies (see https://renater.fr for more details). We consider this network latency as the distance between the sites. This locality cannot be provided by a DHT where the site storing the location of the object is determined by a hash function.

Because the DHT is not able to provide physical locality and to relocate the records storing the location of object replicas close to where they are needed, we propose a protocol inspired by the Domain Name System (DNS). In the DNS protocol, a resolver who wants to perform a query, first requests a root node and if the root node cannot answer to the query directly, it indicates to the resolver which server is the most able to answer. This mechanism is similar to the hops performed in a DHT but with a major difference: it is possible to choose the node storing the location of object replicas instead of using a hash function. It is also possible to control the servers that a node needs to reach to perform a query.

In addition to managing the location through a hierarchical approach, we build a tree overlay on top of the graph shown in Figure 1. We propose in Section III-B, to use a modified version of the Dijkstra's algorithm that generates the tree shown in Figure 2.

III. A TREE BASED APPROACH FOR OBJECT LOCALISATION

This section first describes how our protocol works, then proposes an algorithm to generate the tree we rely on.

In our work, we make several assumptions. First, we work in a context where objects are immutable and therefore all replicas have the same content and are consistent. Second, the requests are sent in an iterative way. In other words, the node that looks for an object, sends the queries to the different nodes. Although the recursive approach is more efficient, most DHT works in an iterative manner [START_REF] Dabek | Designing a DHT for low latency and high throughput[END_REF]. In this study, we kept this approach for fairness reason even if a recursive approach may be easily implemented in next version of our protocol. Finally, we point out that a request does not lead to know the location of all object replicas but only the closest ones in order to reduce access time at its minimum.

A. Protocol description

We propose to distribute the records storing the location of object replicas inside a tree. Like in the DNS protocol, the different names are spread over different servers organised in a hierarchical way. The tree is composed of the different sites of Fog and is browsed from the current site to the root. If the location of a replica of the object is not found at a given level, the parent node is requested. Contrary to the DNS where a resolver first requests the root node, our protocol uses a bottom-up approach. We consider the tree is organised according to the physical topology including the links latencies in order to minimize the time to find the node storing a replica of the object. In other words, the parent of each node is physically close and looking for the location of the object by requesting it, is faster than requesting the parent of the parent. It also limits the network traffic to a small part of the topology.

Figure 2 also shows the location records organisation. The edges between the nodes correspond to physical network links. Each node is able to answer to all requests for objects stored in their subtree, and more specifically, the root node located in Site 6 is able to provide an answer to all the requests. The root node was chosen because of its central position in the physical topology. We consider each site is composed of a "storage backend" and a "location tree server". The "storage backend" is in charge of storing the objects but also of retrieving them from other sites when it is not stored locally. The "location tree server" is responsible for storing the association between an object's name and all sites on which a replica is stored. Concretely, they store location records composed of an object's name and the address of a storage node storing the replicas for this object. For a given object, a server stores at most one record per replica. Figure 2 also shows an example of location record. For instance, there is two location records for the object stored on Site 4: one on Site 4 and one on each site located at an upper level in the tree (Site 6 and Site 3 in the example).

Figure 3(a) shows a first reading process when the object is accessed from Site 2. Because the local storage node does not store a replica of the requested object, the location process is started. The first location tree server to be requested is the local one. Because no location record is stored on it, the storage node requests the parent of this location tree server (i.e., Site 5). The process continues until one location server can answers. In the worst case, the location is found on the root location server (i.e., Site 6). Once the closest location is found, the object stored on Site 4 is relocated locally and new location records are created asynchronously. The storage node sends a message to the location tree servers from the closest one to the one on which the location was found. In this way, sites that are in the subtree of the new created replica will be able to find it during the next read.

We point out, it could be possible not to use "location records" but to store directly object replicas within the tree, avoiding to first determine the location of an object before actually retrieving a replica. However, this strategy is not efficient in term of space usage.

Figure 3(b) shows that when Site 7 requests the object previously relocated in Site 2. The reading process is the same as previously described but the replica from Site 2 is now accessed thanks to the location record found on Site 5. There is no need to reach and update the root metadata server on Site 6, because Site 7 and Site 2 are sibling nodes.

To conclude on this section, we argue our protocol is more adapted for Fog infrastructures than the DHT because location is found along the physical path from the current node to the root node. Finally, in addition to reducing the lookup latency, creation of location records enables the sites to locate reachable objects replicas in case of network partitioning, increasing Fog sites autonomy.

B. Tree computation

As shown in Section III-A, the total latency to find a location increases with the depth of the tree. Our goal is to create a tree in which object's location can be found in a few low latency hops. The classical algorithm to compute the shortest paths from a source node to all the other nodes is the Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]. The generated shortest paths may be seen as a tree with the source node as a root. Therefore, we propose to reuse this algorithm to generate our tree. Nevertheless, some improvements need to be made. The first drawback of the Dijkstra's algorithm is that the root node needs to be specified manually. In order to choose the "best" root node, we compute the tree with each node as source and select the one with the lowest weight. The second drawback is that the traditional cost function does not reflect the way our protocol requests the nodes. Because our protocol is iterative, deeper a link is, more used it is. For instance, in the tree of Figure 2, the distance between Site 7 and Site 6 contains two times the use of the link between Site 7 and Site 5. We propose to use the cost function presented in Equation 1 that reflects this iterative approach.

f c =   parent(node) i=root d (i, parent (i)) × depth (i)   + d (parent (node) , node) × depth (node) (1)
The generated tree shown in Figure 4 is very flat and cannot be used because sites cannot benefit from relocations and access the root node directly. In order to generate a deeper tree, we propose to relax the constraint used in the Dijkstra's algorithm. Instead of selecting a position if it reduces the total weight, we propose to select a position if it does not increase the latency by a factor greater than c in case of the new position of the node is deeper in the tree. Figure 2 shows the tree generated when c = 1.2.

IV. EXPERIMENTAL EVALUATION

We now compare experimentally our approach to a Kademlia DHT [START_REF] Maymounkov | Kademlia: A Peer-to-Peer information system based on the XOR metric[END_REF] in a micro and a macro benchmark.

A. Material and Method

We performed our experiments on the Grid'5000 testbed [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF] using the object store IPFS. In order to mitigate our development efforts, we implemented our approach using several DNS servers to store location records. We used the BIND DNS server as a "location tree server" and we modified the routing mechanism used in IPFS to request those DNS servers in a bottom-up manner rather than the DHT.

We use the topologies shown in Figures 7 and2 for micro and macro benchmark respectively. Objects are written on the first site (in blue in the Figures) and then they are accessed in parallel from other sites. In each read, each object is accessed from one and only one site that did not access it previously. In this way, we never read objects that have been locally stored and for which determining their location is not needed.

Accesses are performed in parallel. We measure the time to access a location record for each object and the number of network links crossed to reach it (the number of hops). Different replication levels in the DHT are evaluated in order to be fair with our approach which relocates location records on the fly. We call "DHT kx", the DHT storing x replicas of each key. The object repository of IPFS and the zone file of the DNS servers are stored in a tmpfs in order to prevent any impact from the underlying filesystem. Network latencies are emulated using the Linux Traffic Control Utility (tc). Network bandwidth between the sites is set to 1 Gbps. We use 1 000 objects with a size of 4 KB each. Because we measure only the time to locate the objects, their size does not impact our results. All experiments were performed 10 times. Standard deviations are not represented but are all around 0.01 s. We perform micro benchmarks on the topology shown in Figure 7 to first validate our experimental plan. This topology is manually built from 5 sites of the Wondernetwork matrix of latencies (see https://wondernetwork.com/pings).

B. Micro benchmarks

The time to locate objects is shown in Figure 5(a), for both the DHT and our approach when objects are accessed for the first time. Objects are sorted from the time to locate them. It appears that our approach need 1.982 s to locate the 1 000 objects, which is faster than a DHT with only one replica (about 4.794 s) and not so far a DHT with 3 replicas (about 1.740 s). We nevertheless point out that in the first read, our approach relies only one location record. Vertical black lines in Figure 5(a) show the theoretical values delimiting groups of objects for which the location record is reached with the same network latency in our approach. In the first read, because each site locates objects with a different latency, we observe 4 different periods (one every 250 objects) separated by 3 different theoretical thresholds. For instance before the first threshold we mostly observe objects read from Site 4, for which the location of object replicas is stored locally. The second group is almost composed of objects read from Site 3 for which the location of objects is found on Site 1, reachable in 13 ms. From object 500 to 750, we observe objects read from Site 5. Finally, after the last threshold, we observe the objects read from Site 2 which need to reach Site 5 and Site 4 to locate them. Because objects are sorted by the time to locate them and because this time is not constant for each site, theoretical thresholds do not delimit exactly what is happening site by site. To deeply understand the behaviour of each site, we split the Figure 5(a) according to the site requesting each object. Figure 5(b) shows the time to locate an object is not the same for each site because the network latency to connect them is different. For instance, in the DHT, Site 4 cannot reach another node in less than 114 ms because it does not have closer neighbour whereas Site 3 can reach Site 1 in 13 ms. We do not observe non-linearity in our approach for a given site because each of them finds all the location records from the same location. We point out the tail for last objects is due to a bad parallelism of IPFS we checked with sequential accesses (not presented here due to space constraints).

Figure 6 shows that in a second and a third read, the time to locate the objects does not vary with the DHT but decreases in our approach that creates new location records when objects are accessed. For the third read, our approach becomes better than the DHT using 3 replicas: location records are close to the sites which need them instead of being spread uniformly. We need 1.417 s to locate the 1 000 objects whereas the DHT needs 2.206 s in this case. Because new location records are created according to object's access, these theoretical thresholds vary with the different reads. Therefore, for the second read, location is found locally for 333 objects because Site 5 now store the location for objects that have been read from Site 2 in the first read. A similar observation is made on Site 2 for which objects are located from Site 5 instead of Site 4.

The conclusion of this experiment is that by requesting close nodes first and by creating new location records read after read, our approach reduces significantly the access times.

C. Macro benchmark

In order to evaluate our approach, we use the original tree in Figure 2 that have been computed using our approach presented in Section III-B. For the DHT-based approach, compute the shortest path (using the traditional Dijkstra's algorithm) in the underlying network, so that each hop has the lowest latency as possible. The consequence is the DHT benefits from optimal network routing paths whereas our approach is constrained by the tree. We perform the same experiment as in the previous section. 1 000 objects are written on Site 1 and are read successively from other sites. Writing on the Site 1 is the worst case possible because for the first access, all sites have to reach the root node.

Figure 8 shows the times to locate the objects in the first read, the third and in the sixth read. Because of the high number of sites, we performed the experiment with the DHT up to 6 replicas for a fair comparison.

We observe that for all reads, our approach has a better performance than the DHT, especially because in our approach, the closest nodes are requested first. Figure 8(a) shows time to locate the objects for the first read. The gap we observe around 600 objects corresponds to the objects from which location record is accessed in 1 hop (accesses from Sites 5, 3 and 8) and objects that are located with 3 physical hops (Sites 2, 4 and 7). In the third read, shown in Figure 8(b), our approach becomes better than the DHT with 3 replicas because of the relocation, but we point out the number of location records is different for each object. For instance an object read from Site 6, then from Site 5 benefits only from 2 replicas when the third read is performed. Contrary to this, an object accessed from Site 2 and then from Site 4 benefits from 5 sites storing at least one location record in the third read. Finally, Figure 8(c) shows better performance in our approach because when location is not stored locally, it is requested on a closer node.

These experiments show that our approach, by creating new location records on the fly, on the path to the root of the tree by taking into account the physical topology enables the nodes to locate the objects with lower access times than using a DHT.

V. RELATED WORKS

Many works propose to add locality in DHT but most papers only consider "routing locality". That is, only nodes with an identifier comprised between the identifier of the source node and the identifier of the destination node can be reached during a lookup. This strategy enables nodes to access the closest replica in the identifier space. This strategy is proposed by many DHT using a Plaxton routing [START_REF] Plaxton | Accessing nearby copies of replicated objects in a distributed environment[END_REF] to access the closest replica without requesting a node that is further than it. For instance, Zhao et al. proposed Tapestry [START_REF] Zhao | Tapestry: A resilient global-scale overlay for service deployment[END_REF], a DHT in which the time to reach a key is proportional to the distance to reach the node storing the key. Yalagandula et al. [START_REF] Yalagandula | A scalable distributed information management system[END_REF] point out that routing locality is not sufficient and they propose a DHT providing path convergence. The advantage is to enable administrative isolation between some sets of nodes, enabling sites to work in case of network partitioning, just like in our Fog Computing approach. As summarized by Castro et al. [START_REF] Castro | Topology-Aware Routing in Structured Peer-to-Peer Overlay Networks[END_REF], the main drawback of those approaches is that the distance is computed in the nodes identifier space that does not reflect the physical topology. To solve this problem, it is possible either to select the nodes' identifiers or to change the DHT routing tables according to the network topology but these proposals are difficult to implement.

We also mention that comparing a DHT based-approach with the DNS has been already done several times [START_REF] Cox | Serving DNS Using a Peer-to-Peer Lookup Service[END_REF], [START_REF] Pappas | A comparative study of the dns design with dht-based alternatives[END_REF]. Pappas et al. [START_REF] Pappas | A comparative study of the dns design with dht-based alternatives[END_REF] already showed the DNS approach has a better availability due to the hierarchical caches and also because the average path length to reach the record is shorter. But their experimentation is not fair because they did not use the same number of nodes in the DHT and in the DNS approach. Moreover, this study does not consider physical locality and is not proposed in a Fog Context.

Finally, Content Delivery Networks (CDN) sometimes rely on a tree [START_REF] Benoit | Optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks[END_REF] but contrary to our approach the data are always written at the root, leading to use different trees, depending on the site the object has been written on.

VI. CONCLUSION AND FUTURE WORK

In this paper, we introduced a new protocol inspired by the DNS to store the location of objects in a Fog infrastructure. We explained how our protocol works, how to compute the tree used, and we evaluated it on the Grid'5000 testbed. The benchmark showed that requesting close nodes first and relocating location records leads to better access times than the DHT. In addition to provide a faster lookup process for objects with a lot of accesses, our protocol also enable the sites to retrieve the closest replica of the objects. Our protocol may benefit several applications like Content Delivery Networks (CDN), P2P approaches like video sharing or the management of virtual machines or container images that all use immutable objects and may be deployed in a Fog environment. Evaluating non-deterministic algorithms to generate our tree and considering a dynamic topology with churn and fault tolerance will be addressed in a future work.

Fig. 1 :

 1 Fig. 1: Part of the French National Research and Education Network physical topology.

Fig. 2 :

 2 Fig. 2: Tree overlay generated from the French NREN topology, showing the location records of an object stored on Site 4.

Fig. 3 :

 3 Fig. 3: Sequence diagrams of network traffic when a client reads an object first from Site 2 (a) and secondly from Site 7 (b).

Fig. 4 :

 4 Fig.4: Intermediate tree generated with our cost function of the Dijkstra's algorithm (total weight: 49). This tree is not adapted to our protocol.

Fig. 5 :

 5 Fig. 5: Mean times to find the location of objects in the first read for all sites (a) and for each site (b). Objects are sorted by their location time.

Fig. 6 :

 6 Fig.6: Mean times to find the location of objects in the second read for all sites (a) and for each site (b). Objects are sorted by their location time.

Fig. 7 :

 7 Fig. 7: Tree used for the micro benchmark (total weight: 612). Accessed objects are written on the site in blue.

Fig. 8 :

 8 Fig. 8: Times to locate objects in the first, the third and the sixth read.