Lyes Hamidouche

Sébastien Monnet
email: sebastien.monnet@univ-smb.fr

Pierre Sens

Dimitri Refauvelet

Toward heterogeneity-aware device-to-device data dissemination over Wi-Fi networks

Keywords: device-to-device, efficient data dissemination, Wi-Fi Direct, heterogeneity, energy efficiency

Toward heterogeneity-aware device-to-device data dissemination over Wi-Fi networks

I. INTRODUCTION

Mobile devices, such as smartphones or tablets have became ubiquitous. Their computing, storage and networking capacities are improving fast. A direct consequence is that mobile applications need an increasing amount of battery and network bandwidth. The data assets used by mobile applications are constantly increasing in size and quality. Even if the storage problem of these devices is no longer a big concern thanks to the increase of storage capacities and the possibility to extend it through removable devices such as SD cards and USB drives, disseminating voluminous data through wireless networks remains a complex task.We focus on the particular case where mobile devices are used by large-scale events participants. In this case, the devices have to be feeded with data at the beginning of the event (technical documentations, presentations, videos, . . . ).

To circumvent the bandwidth capacity limit, we have proposed an approach relying on D2D communications to speedup the transfers [START_REF] Hamidouche | Edwin: Leveraging device-to-device communications for efficient data dissemination over wi-fi networks[END_REF]. Several others works in the literature also use technologies such as Wi-Fi Direct and/or Bluetooth to tackle wireless infrastructures scalability issues. An important part of the research about the use of these communication focuses on data offloading [START_REF] Dimatteo | Cellular traffic offloading through WiFi networks[END_REF], [START_REF] Rebecchi | Device-to-device data offloading: from model to implementation[END_REF], [START_REF] Andreev | Cellular traffic offloading onto network-assisted device-to-device connections[END_REF], [START_REF] Pyattaev | Proximitybased data offloading via network assisted device-to-device communications[END_REF] or video streaming [START_REF] Yoon | On-demand video streaming in mobile opportunistic networks[END_REF], [START_REF] Lee | Movi+: Opportunity extension for mobile peer-to-peer video on demand[END_REF], [START_REF] Keller | MicroCast : Cooperative Video Streaming on Smartphones Categories and Subject Descriptors[END_REF].

However, even if the global energy consumption is often taken into account [START_REF] Sung | Energy-aware algorithms for network-assisted device-to-device content delivery networks[END_REF], [START_REF] Wang | Energy-aware resource allocation for device-to-device underlay communication[END_REF], [START_REF] Nobach | Towards Decentralized, Energy-and Privacy-Aware Device-to-Device Content Delivery[END_REF], individual battery levels are seldom taken into account. Nevertheless, if we look at a large set of mobile devices, e.g. during a large-scale event, we observe devices with different performances, networking capabilities, and remaining battery capacity. While D2D connections are very beneficial for QoS scalability and network performance, their use is greedy in terms of energy.

In our previous work, we have paid attention to limit the global amount of energy consumed. For instance, we have made the pragmatic choice to keep a centralized orchestrator permitting to avoid many control message exchanges among devices. Our goal in this paper is not to reduce the global battery use anymore; instead, our first contribution is to preserve the batteries having the shortest remaining capacity, in order to try to let a minimal level of remaining battery after the data dissemination.

The device heterogeneity is also a matter of bandwidth. Our second contribution is to take advantage of the good bandwidth of some devices to speedup data dissemination. Obviously, our two contributions are linked: our approach will not overuse a device having a good bandwidth, it will even be preserved if its battery reaches a given threshold. Luckily, there is a good correlation: devices having a good battery are often the most recent ones, and also have good networking capacities.

This paper is structured as follows. Section II recalls the background, describes our previous contribution and related works. Then, Section III presents the model of our system and the algorithms that we propose. Section IV gives an evaluation of our approach for data dissemination, and finally, section V concludes.

II. RELATED WORK

D2D technologies constitute an interesting candidate to tackle the performance and scalability issues of wireless networks. In fact, collaborative networking-based solutions help to increase a network's overall throughput and thus reduce the durations of data transfers. Traditional P2P approaches such as Bittorrent [START_REF] Toole | BitTorrent Architecture and Protocol[END_REF] or Gnutella [START_REF] Ripeanu | Peer-to-peer architecture case study: Gnutella network[END_REF] that have been initially introduced to solve scalability issues in wired networks do not consider some aspects of mobile devices such as their limited power, and radio interferences.

The emergence of D2D technologies such as Bluetooth and Wi-Fi Direct brings autonomous networking capabilities to mobile devices. The works in the literature tackle different issues related to D2D communications, such as infrastructures offloading [START_REF] Dimatteo | Cellular traffic offloading through WiFi networks[END_REF], [START_REF] Rebecchi | Device-to-device data offloading: from model to implementation[END_REF], [START_REF] Andreev | Cellular traffic offloading onto network-assisted device-to-device connections[END_REF], [START_REF] Pyattaev | Proximitybased data offloading via network assisted device-to-device communications[END_REF], opportunistic data dissemination [START_REF] Yoon | On-demand video streaming in mobile opportunistic networks[END_REF], [START_REF] Lee | Movi+: Opportunity extension for mobile peer-to-peer video on demand[END_REF], [START_REF] Keller | MicroCast : Cooperative Video Streaming on Smartphones Categories and Subject Descriptors[END_REF], [START_REF] Golrezaei | Device-to-device communications for wireless video delivery[END_REF], [START_REF] Gong | Design and evaluation of a wifi-direct based lte cooperative video streaming system[END_REF], resource allocation [START_REF] Lee | Online channel allocation for full-duplex device-to-device communications[END_REF] or distributed caching [START_REF] Pan | Efficient data dissemination for wi-fi peerto-peer networks by unicasting among wi-fi p2p groups[END_REF], [START_REF] Chen | Caching policy optimization for d2d communications by learning user preference[END_REF]. Asadi et al. [START_REF] Asadi | A survey on device-to-device communication in cellular networks[END_REF] have provided a very complete and detailed survey on this topic.

Before using D2D communications, it is usually necessary to perform a set-up phase. Cherif et. al [START_REF] Cherif | P2p group formation enhancement for opportunistic networks with wi-fi direct[END_REF] have investigated the problem of group formation in Wi-Fi Direct, their solution relies on electing backup Group Owners (GO) in order to speed up the re-creation of the group when the current GO disappears. In the same axis, Li et al. [START_REF] Li | Channel access proposal for enabling quick discovery for d2d wireless networks[END_REF] proposed to use a dedicated common channels to enhance the discovery of communication groups in D2D networks.

The advents in wireless networks permit the simultaneous use of multiple channels to increase their communication efficiency. The use of this mode of operation is getting more and more popular and will face new challenges such as spectrum efficiency, load balancing between licensed and unlicensed channels. . . Naslcheraghi et al. [START_REF] Naslcheraghi | Full-duplex device-to-device collaboration for low-latency wireless video distribution[END_REF] rely on full duplex enabled devices to increase data throughput in the network their simulations have shown that the devices have important gains in high intra and inter cluster interferences. Lee et al. [START_REF] Lee | Online channel allocation for full-duplex device-to-device communications[END_REF] focuses on bringing the newly arrived devices of a D2D network the most suitable channels for D2D networks. With the churn that a mobile network can sustain, it is important to always provide efficient channels for newly arrived devices. Their online algorithm was able to converge quickly and performs with a performance close to the optimal that an offline scheduling algorithm with prior information of the arrival of mobile devices.

Concerning data distribution, Pan et al. [START_REF] Pan | Efficient data dissemination for wi-fi peerto-peer networks by unicasting among wi-fi p2p groups[END_REF] have pointed the lack of efficiency of broadcasting through Wi-Fi Direct groups. They have proposed data dissemination models based on Wi-Fi Direct API model and compared a ring-based and tree-based multi-group Wi-Fi Direct network.

Closer to our works, MicroCast [START_REF] Keller | MicroCast : Cooperative Video Streaming on Smartphones Categories and Subject Descriptors[END_REF] and MoVi/MoVi+ [START_REF] Yoon | On-demand video streaming in mobile opportunistic networks[END_REF], [START_REF] Lee | Movi+: Opportunity extension for mobile peer-to-peer video on demand[END_REF] simultaneously use server downlink and direct communications among mobile devices to improve on-demand video. They both rely on using a unique downlink with the server that hosts the information (video data) and use their ability to establish spontaneous D2D communications to exchange data. Keller et al [START_REF] Keller | MicroCast : Cooperative Video Streaming on Smartphones Categories and Subject Descriptors[END_REF] (MicroCast) propose on a set of mechanisms that provides the ability to improve data retrieval among devices by relying on the broadcast nature of Wi-Fi networks. Adapting such kind of solution for large scale networks would require an important control to make sure all the packets are received by devices. Furthermore, broadcasting will provoke many retransmissions due to network interferences, which slows down data dissemination.

The authors of [START_REF] Yoon | On-demand video streaming in mobile opportunistic networks[END_REF] and [START_REF] Lee | Movi+: Opportunity extension for mobile peer-to-peer video on demand[END_REF] use adhoc communications between devices to improve network QoS for collaborative ondemand video. They rely on a centralized system architecture to achieve their performance goals. In fact, they use centralized infrastructure devices as supervisors for the state of the network and the interferences fluctuations to opportunistically trigger exchanges between devices. In our approach, the fluctuations of wireless interferences help to define a limit of mobile devices that communicate simultaneously in the network. This simulation degree can vary depending on network environment conditions. In their work, the authors have also focused on improving the switch between adhoc and infrastructure Wi-Fi. Using Wi-Fi Direct for D2D communications between devices relies on the same mechanisms with infrastructure Wi-Fi and current commercial devices are capable of handling simultaneously a communication group and an infrastructure link with access points. By using this mechanism, we are able to establish D2D connections only while needed and adapt the parallelism degree in the network.

Concerning power management, it is a very important aspect in mobile networking and D2D communications make no exception. In fact, exploiting D2D communications to improve infrastructure QoS helps to reduce overall networking time. However, it has an important energy cost. Globally reducing network overall power consumption is important, however, by not considering the state of the individual mobile devices that participate to the network, some devices can be overused in comparison with their neighbors. Furthermore, in the current mobile devices ecosystem, we have a considerable heterogeneity of mobile devices. Their characteristics (Battery life, computing capacity, bandwidth, . . . ) vary depending on their brand, their model, . . . . Moreover, several devices can have a half charged battery. To the best of our knowledge, most of the contributions around power efficiency in D2D networks tackle the problem with the goal of reducing the network overall consumption and do not consider the heterogeneity of the mobile devices in terms of remaining battery capacity. Nobach et al. [START_REF] Nobach | Towards Decentralized, Energy-and Privacy-Aware Device-to-Device Content Delivery[END_REF] treat the problem of the security and power consumption that mobile devices face while actively scanning to discover the nearby devices of the network. Power saving and content delivery efficiency are two important and conflicting aspects in D2D-based communication networks. Sung et al. [START_REF] Sung | Energy-aware algorithms for network-assisted device-to-device content delivery networks[END_REF] contribution consists in two algorithms for packet routing and scheduling in order to balance between these two factors. Their simulation for small-scale networks ha shown the possibility of balancing between a longer D2D networking and a better content delivery performance.

With the heterogeneity of mobile devices, treating all the de-vices in the same way can lead to important over-participation of the first devices to acquire data. This can lead to important battery losses among these devices. It is thus mandatory to consider the devices separately while disseminating data in a D2D based network. The devices with the weakest batteries that participate to the dissemination should be protected of any overuse in the network. This is particularly important when considering the concerns of a company that animates large scale events (such as Magency [START_REF]Magency[END_REF]), where it is mandatory to leave the devices with enough battery to last all along the event. It is even preferable to increase the overall power consumption if it provides the ability to preserve the weakest devices from being overused. However, the use this kind of approach would requires the approval of users to consume more energy to save bad devices batteries, but when the devices are lent to users (like during large scale events), it becomes simpler to implement them. In practice, when a user refuses to share his device's energy, his device is considered as a weak battery one.

III. CONTRIBUTION

In our previous work [START_REF] Hamidouche | Edwin: Leveraging device-to-device communications for efficient data dissemination over wi-fi networks[END_REF], we have presented EDWiN, our approach to leverage D2D communications among Wi-Fi Direct enabled devices in order to improve the network Quality of Service for data dissemination. The algorithms that we introduce here are an extension of our previous work [START_REF] Hamidouche | Edwin: Leveraging device-to-device communications for efficient data dissemination over wi-fi networks[END_REF] that takes into account the energy and the bandwidth of each device. In this section we first describe the architecture and the model of the considered system, providing the necessary background concerning EDWiN; then we describe the proposed algorithms.

A. Architecture

Wi-Fi Network

Wi-Fi Direct In our study, we focus on the the case of Wi-Fi infrastructures that are used to host large scale events. Figure 1 represents the architecture of our system. It consists in:

The server : the node hosting the data to be downloaded by mobile devices; Wi-Fi infrastructure : it consists in routers, wireless controllers and access points. It is used to create a network that the mobile devices will connect to, as the only link with the server;

Mobile devices : the nodes accessing data, these devices are also Wi-Fi Direct enabled. The goal is to disseminate the data hosted by the server on all the mobile devices as fast as possible. The server must be able to provide the devices the data they require and leave enough bandwidth for other applications that communicate through the same medium. We pragmatically use the server as a scheduler. The network's global state is then maintained with control messages exchanged with the clients (mobile devices). Thus, data transfers and exchanges between devices can be easily scheduled as the server has a global view, maintaining a "Network State Table" (N ST ) that holds all the information about the devices (including disseminated chunks).

System representation: Depending on the network that has to be covered by a Wi-Fi infrastructure, the number of the servers, routers and access points (APs) can vary. In our study we focus on a part of such a network. We the consider a Wi-Fi network N which is composed of |N | mobile devices that are connected to one single server S, through a single access point. The server disseminates a voluminous data to the mobile devices. This data is split into chunks in order to quickly increase the number of data sources in the network (smaller chunks will be transfered faster, new sources will be available sooner). As our goal is to offload the infrastructure, we restrict the number of concurrent downloads from the server to one. In practice this parameter can vary depending on the infrastructure and the bandwidth that has to be left for other network usages.

As D2D exchanges require a connection establishment that lasts a non negligible time, it is better for devices to exchange the maximum amount of data possible at each D2D connection.

Wireless networks interferences depend on the environment and are difficult to model or reproduce. Obviously, the more parallel exchanges there are, the more interferences there will be. Our approach is thus tunable, a limit upon the "parallelism degree" can be set. It corresponds to the maximum number of devices authorized to exchange data simultaneously in the network. We note this parameter maxP ara.

Device representation: Every mobile device d ∈ N is defined by parameters that are used by our algorithms to schedule the exchanges between devices:

State : defines the current networking state of the device. A device can be idle or exchanging with another device or the server; Chunks : is a set representing the chunks that have been retrieved by the device; Battery life : in seconds, represents the remaining battery of the device; Networking battery loss factor : represents the battery loss speed of the device when networking intensively ; Device-to-device throughput : represents the throughput of the device when sending data through a D2D connection. During an event, the battery of the mobile devices should last long enough to let all the participants use them all along the day. This means that each battery should remain over a given level at the end of the dissemination. We thus set a parameter which is the minimal battery threshold under which our solution prevents a device from being overused by D2D communications. At any time the network is thus partitioned into two sets of devices that we call "Good" and "Bad" depending if the remaining battery is above, resp. below the threshold. Obviously, the partitions are dynamic: a device considered as "Good" can become "Bad" if it consumes too much power (for instance, old devices usually consume their battery faster than recent ones). We observed on a set of devices that are used during large-scale events that their battery life and battery loss speed vary depending on the age and the model of the devices 1 .

The device-to-device throughput also varies a lot among devices. Devices have different Wi-Fi chips, and usually recent devices are equipped with cutting edge chips capable to handle higher data throughput than old ones. Leveraging "fast" devices can help to reduce the total dissemination time, however, it is important to pay attention to their battery usage.

In our previous work [START_REF] Hamidouche | EDWiN: leveraging device-to-device communications for efficient data dissemination over Wi-Fi networks[END_REF], we considered only homogeneous configurations. We mainly focused on the importance of parameters such as the parallelism degree and the data size and their impact on the data dissemination performance.

In the following of this paper, we focus on the battery and bandwidth throughput heterogeneity. In terms of energy usage, our goal is not to reduce the global consumption, but to prevent the device batteries to go under a given level. If the global network battery use is a little bit higher, it is not a problem as long as the devices with the worst batteries consume less energy.

Our goal remains to reduce the dissemination completion time of voluminous data over Wi-Fi networks by using parallel D2D connections between devices. Furthermore, we want to offload the networking infrastructure (Wi-Fi Access Points, routers and servers). Considering our case study, a dissemination happens generally at the beginning of a large scale event or at the update of a voluminous data.

In the remainder of this section we detail three different approaches that help to reduce data dissemination time with different considerations of the network.

B. Naive dissemination algorithms

Initially, the purpose of our algorithm is to quickly increase the number of data sources in the network and the exchanges between devices. The dissemination starts when the server sends the first chunk to a device randomly selected then the server is acknowledged by the devices at every end of transfer or exchange between devices. In order to replicate the chunks uniformly, the server uses a "rarest first" policy to select the data chunks to transfer/exchange among mobile devices. Thus, there are quickly many replicas of the chunks on 1 observations made on the devices provided by Magency [START_REF]Magency[END_REF] for their customers different devices, which favours the D2D exchanges among the mobile devices. In order to use D2D connections efficiently, the server selects pairs of devices which have the maximal hamming distance on their chunk-sets. In other words, the server selects the devices having the maximum amount of data to exchange. While there are available devices and the number of active devices activeDevices has not reached the maximum parallelization limit maxP ara, the server schedules as much D2D exchanges as possible.

Without considering the battery life, the first devices to receive chunks will often be selected for exchanges with the other devices. This high activity may cause an important energy consumption on some devices. In the meantime, other devices use a much smaller amount of energy for exchanging (the energy consumption is not well balanced). This naive algorithm has been introduced and detailed in our previous contribution [START_REF] Hamidouche | Edwin: Leveraging device-to-device communications for efficient data dissemination over wi-fi networks[END_REF].

The performance in terms of dissemination time is good, however, unfortunately in practice, the high activity can occur on devices having bad or low-level batteries. In this case, they will have less chances to last for the rest of the event.

C. Battery aware D2D dissemination algorithm

Considering the battery life of the devices is important to permit to every user device to last the event.We observed, through measurements driven on devices loaned by Magency, that the throughput using Wi-Fi Direct connections was more than 10 times slower than the throughput using an access point. This is due to the connection times that are not negligible but also, and mainly because the transfers themselves are slower. A D2D network hyperactivity on a device could provoke important battery consumption and hinder the user from using its mobile device all along the event.

Algorithm 1 Battery aware dissemination policy end if 14: end while In order to protect the devices having bad or low-level batteries, we do not use them for D2D exchanges. Furthermore, when a bad device downloads data from the server, it downloads all the data in one time to limit the number of connections/disconnections.

In order to have enough parallel transfers between devices, the server disseminates enough chunks to keep as many devices active in parallel as the parallelism degree (maxP ara) allows. Then the server sends data to devices with weak batteries, sequentially. If a node which was first considered as good becomes bad (beacause it has use too much its battery) it will enter the bad set, and the missing data will be downloaded directly from the server. If the bad set becomes empty, then the server helps the good devices, as in the naive approach. Algorithm 1 describes how the server handles the transfers in the network.

If there never bad devices in the network, the server simply acts with the same behaviour as the naive algorithm.

D. Battery and bandwidth aware approach

The heterogeneity does not only come from battery levels. Some devices have more recent Wi-Fi chips and are able to handle higher data throughput. Taking into consideration this parameter provides the ability to improve the network performance and reduce the global dissemination time. Giving priority to several devices having a large bandwidth could help to quickly obtain fast data sources and thus, to speed up the global dissemination. These particular data sources (several devices having both a good remaining battery and a large bandwidth) can thus be used to feed the other devices.

We propose an approach that takes into account both battery and bandwidth heterogeneity. We do not assume that devices with a good bandwidth are also those having a good battery. However, in practice, recent devices usually have a better battery and a larger bandwidth. These two parameters seems correlated. In our approach presented below, we rely on devices having both a good battery and a large bandwidth (when they exist in the system).

Algorithm 2, executed at the beginning and at the end of each transfer, describes the server's scheduling policy. Inside the good devices set, it considers devices based on their bandwidth throughput. We call "Fast", the devices that have a data throughput greater that a defined limit minF astBW . Fast devices can exchange quicker data inside their set than with other devices. From line 1 to 5, the algorithm computes the different sets of devices based on the idle devices characteristics.

Then, if there are currently no transfer from the server in progress (AP.state = Idle, Algorithm 2 line 6), the server triggers a transfer through the AP by calling the function scheduleAP T ransf er(). This function's behavior depends on the state of the network. If there are not enough fast data sources (the fast devices), the server prioritizes the data dissemination on these devices. Then, if there are no good devices available, the server disseminates data to bad devices.

Concerning D2D exchanges, the server selects fast devices that have retrieved all the data as data sources for other good devices with lower throughput and finally to bad devices Trigger exchange between p.device1 and p.device2

if d = N il then 27:
data ← chunksF orDevice(d)

28:

Send(< data, d >)

29:

end if 30: end function in order to disseminate chunks in one connection. It is a way to prevent the bad devices from multiple connection establishments that could waste their energy. Note that the devices having a bad/low battery will get filled at the end. This allows the server to estimate the time they'll have to wait before getting served, permitting these fragile devices to go into sleep mode.

If the devices having both a good battery and a good bandwidth have already retrieved all the data, the server schedules exchanges between devices by prioritizing fast transfers as described by Algorithm 3. When no such good device is available, the algorithm falls back on the naive approach, based on the hamming distance computed on the chunk sets (selectHamming()).

IV. EXPERIMENTATION AND EVALUATION

A. Evaluation conditions

We evaluated our approach using Peersim [START_REF]Peersim[END_REF], a discrete event simulator. In order to calibrate our simulator, we have run extended measurements on hardware loaned by Magency [START_REF]Magency[END_REF]. This experiment campaign has allowed us to observe the behavior of a Wi-Fi infrastructure centralized on end if 14: end function a single access point; to measure Wi-Fi Direct connection establishment times, unidirectionnal and bidirectionnal D2D throuputs, battery consumption under various conditions. Our prototype is composed of two layers: (i) an applicative layer and (ii) a transport layer. The applicative layer implements the different exchanges between devices. The transport layer, which we calibrate with the preliminary measures, permits to compute latencies and bandwidth between pair of nodes.

For the evaluation of our approach, we simulate a network of 200 mobile devices that have to retrieve a 500M Bytes data block. This data is split into 10 chunks (50M Bytes each). Only 33 devices are authorized to exchange simultaneously in the network (maxP ara) 2 . The devices download from the server (AP) at a 10M Bytes/second data rate. For D2D transfers, the data rate varies depending on the device that is considered. We have observed, that depending on the brand of a device, or its operating system, the data rate of D2D connections vary. For instance, we have observed practical data rate of 1M byte/s between a pair of our Apple iPad Air Tablets, whereas, with a Samsung Galaxy S7, we have observed a 4M bytes/s data rate. We use these observed data rates as values to define slow and fast devices. Based on devices that are distributed to the attendees of corporate events, we observed that the battery life depends on their age and condition. The good devices we simulate here have a 12 hours battery life and the bad devices have a 8 hours battery life which is also the battery level threshold under which a device gets "protected" by our approach (minBattery).

In terms of energy saving, our goal is not to reduce the overall network consumption. Instead, we try to preserve the devices with the weakest batteries from important battery losses. In terms of bandwidth heterogeneity, our goal is to reduce dissemination time, by quickly disseminating all the data to fast devices. Then the approach rely on these nodes to transfer the data to other device using one single connection, reducing the number of connection establishments.

We have chosen to not simulate the network interference because it depends on the environment and it is hard to model 2 More explanations on the parallelization limit can be found in [START_REF] Hamidouche | Edwin: Leveraging device-to-device communications for efficient data dissemination over wi-fi networks[END_REF]. correctly, and even real experiments in presence of interference are hardly reproducible. It is thus important to notice that our simulator gives results considering an ideal, interferencefree environment. However, as detailed in [START_REF] Hamidouche | Edwin: Leveraging device-to-device communications for efficient data dissemination over wi-fi networks[END_REF] our approach provides the ability to vary the parallelization degree in order to lower the interference level.

The performance metrics that we evaluate in our study are the following.

• The completion time : the time it takes to disseminate the data to all the devices. It represent the performance of the dissemination. We have observed that using the naive approach most of the nodes get completed close to the completion time (in a short time frame).

•

The estimated remaining battery : the estimated remaining battery at the end of the dissemination. We first evaluate the ability of our approach to preserve a minimum amount of battery on fragile devices (to allow its user to attend the event). We also evaluate the impact of the proportion of devices having a bad battery, or a large bandwidth on the completion time. Our goal being to preserve the bad batteries while still offering a good performance in terms of completion time.

B. Considering battery duration

We remind here that the objective is not to reduce the network global energy usage but to preserve low level batteries. Figure 2 shows the remaining battery difference in comparison with the naive approach for various percentages of bad devices in the network. We measure here the average estimated remaining battery in the network, the mean remaining battery for the "bad" devices and the worst device battery. We observe, that for the worst devices the battery-aware approach saves up to 2 hours of battery on the bad devices in comparison versus the naive approach. We also observe that the global battery use in the network is better with the battery aware approach, except for 40% of bad devices in the network. This is thanks to the fact that in the battery-aware approach, "bad" devices do not need to create D2D links with other devices, there are less connections/disconnections, saving networking time, and thus battery.

Figure 3 shows the impact of the percentage of bad devices on the completion time. There again, we compare the performance of the naive dissemination approach that considers all the devices in the same way versus the battery aware approach. We observe that under 30% of bad devices in the network, the battery aware approach outperforms the naive approach. As in the naive approach we already limit the number of parallel transfers, there is no more parallel transfers than in the batteryaware approach; furthermore, in the battery-aware approach, we save some connection/disconnection time as mentioned above.

However, for a higher proportion of bad devices, we can observe a performance loss. In fact, as we can see in Figure 4; which shows the evolution of the number of completed node in both good and bad device sets and the whole network; all the good devices retrieve the whole data quickly while the bad devices are still downloading from the server. When there are too many devices with a bad battery the sequential download by these devices as a strong impact on the completion time.

Using this approach might prevent from important battery losses of the worst devices, but it can cause a performance drop of the dissemination when the proportion of device having a low-level battery is too hight.

C. Considering battery duration and bandwidth

Figure 5 show the completion time while varying the percentage of fast devices (device with high bandwidth) in the network. In these simulations, there are 40% of bad devices (devices with a low-level battery). We measure the impact of the percentage of fast devices on the performance of the network. We observe that, by using a hybrid approach we have better completion time than with the battery-aware approach only: it is worth taking bandwidth heterogeneity into account. We also observe, that , as expected, increasing the proportion of those devices in the network improves the performance of the dissemination.

Figure 6 shows the percentage of battery gain we obtain when using the hybrid approach in comparison with the battery-aware approach. We observe that we have a better energy gain. By considering the use of fast devices in the dissemination, data sources with the whole data appear quickly in the network. The other mobile devices receive the whole data in one connection from another devices. Leaving the bad devices as the last to get data from the server permits to save their energy and retrieve data at the end of the dissemination. We also observe that the energy gain increases with the increase of the proportion of fast devices. In fact, thanks to a higher number of fast D2D nodes in the network, the devices with good batteries retrieve the whole data faster, the devices with weak batteries wait less to get data. Thus, devices spend less time networking and save energy.

To put it in a nutshell, preventing devices with bad batteries from any exchange with other devices can be efficient, but only when their proportion is small. It can even provide a performance gain thanks to a lower number of connections/ disconnections. When their proportion is too big, the sequential transfers from the server to the bad devices take too much time, even after the good devices have finished their exchanges, end are completed.

If the devices bandwidth are heterogeneous, it is worth . Battery gain comparison between the energy aware approach and the hybrid ( Energy + bandwidth) approach taking this into account. As expected, this provides the ability to save dissemination time (performance gain), but also energy (a shorter dissemination consumes less energy).

V. CONCLUSIONS AND FUTURE WORK

In this paper, we focused on the impact of devices heterogeneity in a D2D based data dissemination system. We proposed two dissemination approaches: one that considers the case where the devices differ only in terms of battery and one that considers an heterogeneity in terms of both battery and network bandwidth.

To prevent an overuse of the devices with weak batteries we prevent them from participating to the energy-consuming D2D exchanges. We also leverage devices having both a good battery and a good Wi-Fi chip to enhance the dissemination performance while still preserving low-battery devices.

We have discussed in our evaluations how performance could be impacted by the proportion of devices which batteries should be preserved. We have shown that when the proportion is small it is possible to preserve the bad batteries with no performance degradation, but a small performance gain. Furthermore taking into account network bandwidth heterogeneity can enhance both the completion time and the energy saving.

In the future, we plan to investigate how the network bandwidth heterogeneity can be used to disseminate data from a device with high data throughput to several devices with smaller bandwidth. We also plan to study other dissemination strategies, using hierarchical topologies.

Figure 1 .

 1 Figure 1. System representation

1 :

 1 I ← { ∀ d ∈ N ; d.state = Idle } 2: good ← { ∀ d ∈ I ; d.battery ≥ minBattery } 3: bad ← { ∀ d ∈ I ; d.battery < minBattery } 4: Disseminate chunks to devices d ∈ good until activeN odes >= maxP ara -2 5: while ¬disseminationF inished do until bad = ∅ or disseminationF inished 10:

else 11 :

 11 send data to d, ∀ d ∈ bad 12: keep scheduling exchanges among devices ∈ good 13:

Algorithm 2

 2 Battery and bandwidth aware dissemination algorithm 1: I ← { ∀ d ∈ N ; d.state = Idle } 2: good ← { ∀ d ∈ I ; d.battery ≥ minBattery } 3: bad ← { ∀ d ∈ I ; d.battery < minBattery } 4: f ast ← { ∀ d ∈ good ; d.bandwidth ≥ minF astBW } 5: f astCompleted ← { ∀d ∈ f ast; d.completed = T rue } 6: if AP.state = Idle then end if 10: p ← selectExchange() 11: while p = N il and activeDevices < M axP ara -2 do 12:

Algorithm 3 2 :

 32 Exchange selection function 1: function selectExchange() if |f astCompleted| > 0 then 3:f ast ← f astCompleted.pop()

Figure 2 .Figure 3 .

 23 Figure 2. Remaining battery difference with battery aware approach in comparison with the naive approach

Figure 4 .

 4 Figure 4. Completion evolution with battery aware approach with 40% of bad devices in the network.

  t im e(s) Battery aware Battery and bandwidth aware

Figure 5 .

 5 Figure 5. Performance of Bandwidth aware approach in comparison with bandwitdh aware approach

Figure 6

 6 Figure 6. Battery gain comparison between the energy aware approach and the hybrid ( Energy + bandwidth) approach


Pedro Henrique Penna

Henrique C Freitas

João Caram

Márcio Castro

Using The Nanvix Operating System in Undergraduate Operating System Courses

Operating Systems (OSs) have an important position in the Computer Science curriculum. When students face this subject, they study core concepts, mechanisms and strategies that apply to several fields. To support practical lectures in an OSs course, instructors may adopt an OS on which students can work, exercising their knowledge and enhancing their practical skills. In this context, we present Nanvix, a new OS designed to address this use in undergraduate OSs courses. We introduce a flexible assignment-based teaching methodology for our OS, and we assess the effectiveness of this methodology by applying it in the OSs course of the Pontifical Catholic University of Minas Gerais. When using Nanvix, the average score of the students in the course increased in 11.2%, and the failure rate dropped 47.7%. Moreover, we observed that with Nanvix students got more motivated and interested in the OSs field.

I. INTRODUCTION

Operating Systems (OSs) play an important role in the software stack. They act as a hardware manager by multiplexing access to resources, ensuring data protection and integrity, and enforcing protocols and policies. Beyond that, OSs extend the functionalities of the underlying hardware, presenting the user a programming interface that is more pleasant to deal with. In summary, without OSs, programmers would have to worry about machine intricacies, ending up to be less productive [START_REF] Tanenbaum | Modern Operating Systems[END_REF].

Given the importance of OSs nowadays, it is simple to highlight some extra points that turn them into a significant subject to Computer Science (CS) curriculum. First, OSs help students to design, implement and hack complex computing systems. Also, they introduce core concepts, mechanisms and strategies which can be applied to several fields of CS.

Teaching methodologies in OSs can follow several approaches. One that is widely adopted and mixes theory with practice works as follows. The instructor divides the OSs course into two parts: theoretical and practical lectures. In the former, he/she introduces students to the main concepts and principles of OSs, usually using some supporting material, such as textbooks. In this first part, the goal is to provide students with a solid foundations in the field. In practical lectures on the other hand, the instructor assigns activities to students so that they can exercise their theoretical knowledge. Here, the instructor often alternates between user-and kernellevel activities, possibly using some supporting OS [START_REF] Christopher | The nachos instructional operating system[END_REF], [START_REF] Holland | A new instructional operating system[END_REF], [START_REF] Hovemeyer | Running on the bare metal with geekos[END_REF], [START_REF] Pfaff | The pintos instructional operating system kernel[END_REF], [START_REF] Tanenbaum | Operating Systems: Design and Implementation[END_REF], [START_REF] Da Costa | Nke-um nanokernel educacional para microprocessadores arm[END_REF].

With this kind of software, students have at their disposal an OS on which they can work, exercising their theoretical knowledge and enhancing their practical skills. Unfortunately, existing OSs lack in several points. Some are restricted to run in simulators, while others run on hardware, but are too large to offer a pleasant learning rate to students; some provide no teaching material neither grading suggestions, whereas others impose a strict teaching methodology that may not reflect the instructor needs; and finally, some embrace outdated features, while others support modern features, but ask students to implement most of them, which can be overwhelming depending on the course schedule.

In this context, the goal of this work is to present Nanvix, a new OS that we designed and implemented from scratch to tackle the aforementioned problems. Nanvix may be used by instructors to introduce students to core OS concepts, which are common across the general purpose, real-time and embedded systems. In addition, this work introduces a flexible teaching methodology that may be used with Nanvix. We present an evaluation of our methodology and OS, when we applied both in the OSs course of the CS Undergraduate Program at Pontifical Catholic University of Minas Gerais (PUC Minas). Our work differs from previous ones in several points. First, in contrast to related software, Nanvix: i. is smaller, hence making kernel hacking easier; ii. is fully featured, thus enabling instructors to better meet their teaching needs; iii. runs in virtual machines and on real hardware, which further motivate students; iv. is shipped with an extensive documentation, hence saving instructor's time; and v. presents an internal structure that is similar to Unix and targets Posix specification, thus making students face a realistic environment.

Second, this work introduces a flexible assignment-based teaching methodology that may be used with Nanvix. This type of methodology enables instructors to better meet their course schedule and it is absent in related OSs. Finally, this work presents a quantitative evaluation of the use of our OS. To the best of our knowledge, such evaluation is hardly found in the literature, thus reinforcing the our main contributions.

The remainder of this work is organized as follows. In Section II, we discuss related work. In Section III, we present the internals of Nanvix. In Section IV, we introduce the teaching methodology that may be used with our OS. In Section V, we present a qualitative and quantitative evaluation of our Nanvix-based teaching methodology. In Section VI, we expose our conclusions and future perspectives of this work.

II. RELATED WORK

To support practical lectures in OSs courses, several OSs narrowed for this goal are available. In the sections that follow, we briefly discuss some of the most popular, and then contrast them with Nanvix. For a more detailed discussion on this topic, we refer the reader to [START_REF] Anderson | A survey of contemporary instructional operating systems for use in undergraduate courses[END_REF], [START_REF] Hwang | Blended learning for teaching operating systems with windows[END_REF], [START_REF] Laadan | Structured linux kernel projects for teaching operating systems concepts[END_REF], [START_REF] Cox | Xv6, a simple unix-like teaching operating system[END_REF].

Minix is one of the first successful instructional OSs introduced by Vrije University [START_REF] Tanenbaum | Operating Systems: Design and Implementation[END_REF]. It is fully featured and accompanies a well known textbook, but it presents some drawbacks which turn it inconvenient to be used in OS courses. First, Minix is a large system, when compared to related OSs. Second, besides the practical activities that are presented in Minix's textbook, no teaching methodology is suggested with it. It is up to the instructor to decide how to introduce Minix to students. Finally, it embraces outdated features, such as a segmentation-based paging system with no swapping.

Nachos is an OS, developed at University of California, Berkley [START_REF] Christopher | The nachos instructional operating system[END_REF]. It runs in a simulated MIPS environment as a user-level Unix process, and it was designed so as to provide a minimum working example of a system. Nachos accompanies a series of assignments which are built on top of one another and students work on major portions of the OS. Nachos instructors observed that their system and assignment-based teaching methodology helped students to further consolidate their understanding in OSs. However, they reported that they were not able to find a textbook that covered many of the concepts used in Nachos, thus stepping the learning rate.

GeekOS is an OS developed at University of Maryland, College Park. It is structured as a monolithic kernel and provides the bare-bone features of a modern OS. Based on this system, students work in a series of assignments which are built on the top of one another. An evaluation of GeekOS is presented in [START_REF] Hovemeyer | Running on the bare metal with geekos[END_REF], and the results showed that students found that GeekOS helped them to understand OS concepts though the course. Moreover, results unveiled that students felt motivated on having GeekOS to run on real hardware.

Table I highlights the main differences between the aforementioned OSs and Nanvix. In contrast, Nanvix is fully featured (complete), and it accompanies a flexible assignmentbased teaching methodology that enables instructors to better meet their schedule and teaching needs. Moreover, Nanvix features a Unix System V architecture and Posix compliance, thus making students face a realistic environment. Besides this, Nanvix is smaller, hence making kernel hacking easier; it is shipped with an extensive documentation, thus saving instructor's time; and it runs in virtual machines (easy to debug) and on real hardware (further motivating). Nanvix is an OS that we designed from scratch to be small and simple, and yet fully featured. It originally targets x86-based PCs and features virtual-memory based on paging, a hierarchical Unix file system based on inodes, a uniform device driver interface, and a preemptive prioritybased scheduler. Nanvix is under active development, with growing interests on both education and research. This work is grounded on Nanvix 1.2, but all its releases are available at wwww.github.com/nanvix/nanvix. In the paragraphs that follow, we briefly detail the internals of Nanvix. For a more detailed discussion of our OS we refer the reader to [START_REF] Penna | The Nanvix Operating System[END_REF].

The architecture of Nanvix is outlined in Figure 1. It presents a similar structure to Unix System V [START_REF] Bach | The Design of the UNIX Operating System[END_REF], and it has been intentionally designed this way because it is adopted in some successful OSs, such as Linux. Nanvix is structured in two layers. The kernel (bottom layer), seats on top of the hardware and runs in privileged mode. Its job is to (i) extend the underlying hardware so that an easier-to-program interface is exported to the higher layer; and (ii) multiplex hardware resources among several users. The userland (top layer), relies on Posix system calls exported by the kernel and it is the place where user software run in unprivileged mode.

The kernel presents a tiny monolithic architecture (7k loc), and it is structured in four subsystems: the hardware abstraction layer; the memory management system; the process manager; and the file system. The hardware abstraction layer interacts directly with the hardware and exports to the other subsystems a set of well-defined low-level routines. The job of the hardware abstraction layer is to isolate, as much as possible, all the hardware intricacies, so that the kernel can easily be ported to other compatible platforms.

The memory manager provides a flat virtual memory abstraction. It does so by having two modules working together: the paging and virtual memory allocator. The former deals with paging, keeping in memory those pages that are more frequently used, and swapping out to disk those that are not. The virtual memory allocator, on the other hand, relies on the paging module to create higher-level abstractions called memory regions, and thus enable advanced features such as shared memory regions, on-demand loading and lazy coping.

The process manager handles creation, termination, scheduling, synchronization and communication of processes. Processes are single-threaded entities and are created on demand, either by the system itself or the user. Scheduling is based on preemption, and in userland it happens whenever a process runs out of quantum or blocks awaiting for a resource. In ker- nel land, processes run in nonpreemptive mode and scheduling occurs when a processes voluntarily foes to sleep. In addition, the process manager exports inter-process communication facilities, such as Posix pipes and shared memory regions.

The file system provides a uniform interface for dealing with hardware resources. It extends the device driver interface and creates on top of it the file abstraction. Files can be accessed through a unique pathname, and may be shared among several processes. The Nanvix file system is compatible with the one present in Minix, it adopts an hierarchical inode structure, and features mounting points and disk block caching.

IV. TEACHING WITH NANVIX

In this section, we detail the assigned-based teaching methodology that we propose to be used with our Nanvix. In contrast to related approaches, ours is designed so that instructors may: (i) carry out practical activities in any order they want; and (ii) be free to propose their own activities. First, we present an overview of it, then we introduce the underlying principles that we considered when designing the assignments, and next we present each of them in turn. In the end, we present the evaluation method that we adopted to assess the effectiveness of our Nanvix-based teaching methodoly.

A. Assignments Organization

Table II presents an overview of the five assignments that are shipped with Nanvix. These assignments are designed for a one semester-course, and may be assigned in arbitrary order. We suggest that the instructor to take about 10-15 minutes every week to discuss with the students what problems they are facing and how they can address them. With respect to grading, we do not pin down a specific scheme, because administrative questions may differ from one course to another. However, we suggest some considerations in the evaluation of assignments.

B. Assignment Principles

Improve Existing Features. Students work improving existing functionalities, rather than building entire system's components from scratch. This way, they can focus more on core design aspects, thus increasing their learning rate.

Freedom in Design. Creativity is an important skill for computer scientists. We encourage this by designing assignments in such a way that students are free to choose whatever data structures and algorithms they want.

Encourage Realistic Solutions. High performance is an important requirement for an OS and it is usually challenging to deliver. To motivate students to work towards this, each assignment is shipped with a micro-benchmark which they can use to evaluate their solution. We suggest that the more students score on these benchmarks, the more they are rewarded.

Teamwork. In industry, software is developed by having tens of small and self-organizing teams to collaborate with one another. To replicate such environment, assignments are designed to be accomplished by a team of 2-4 students.

Detailed Documentation. An OS that serves as a supporting teaching tool to theoretical lectures should be well documented, otherwise instructors and students will have difficulties on using it. To address this problem, we provide a detailed documentation of both the kernel and assignments.

C. Process Scheduling and Semaphore Implementation

In the educational version of Nanvix, processes are scheduled based on a round-robin policy, and no process synchronization mechanism is available. We therefore ask students to (i) implement a priority scheduler; and (ii) implement semaphores in kernel land and export this feature through the system call interface to userland. Students are free to choose their own design. However, they should follow the system specification for the semaphore implementation, which is compatible with Posix, and should benchmark their solutions by running a Producer-Consumer example that is provided.

In this assignment, students learn how the OS schedules processes to execution, how complex scheduling policies may be built on top of simpler ones, and how synchronization primitives may be implemented. In addition, students learn the importance of dynamic priority scheduling; have insights about how to design fair semaphores; and learn how to add new system calls to an OS's kernel.

Students should have about six weeks to work on this assignment, three weeks for each part. With respect to grading, we suggest the instructor to reward with extra points those students that have implemented a dynamic priority scheduling policy in the first activity, and semaphores with access verification and/or fair scheduling in the second one.

D. Page Replacement

In the educational version of Nanvix, pages are evicted from main memory and swapped out to disk in a first-in-firstout fashion with a local-replacement policy. Such strategy is simple to implement, but it leads to a poor performance when compared to other strategies. To solve this problem, students are asked to implement a more efficient page eviction algorithm. To encourage them to work on realistic solutions, we require students to evaluate the performance of their strategy with a matrix multiplication benchmark that we provide.

With this assignment, students learn important principles on system design. First, they further understand how the OS provides the illusion of a large memory to users, through the virtual memory and paging techniques. Second, students work deepen their knowledge on how the paging system works internally. Finally, students learn how a smart eviction strategy may lead to a good system's performance.

Students should have about four weeks to work on this assignment: one week to first understand how the existing paging system works, two weeks to implement a more efficient page eviction algorithm, and another week to perform benchmark evaluation and final adjustments on their solution. With respect to grading, we suggest the instructor to reward students according to the robustness of their solution.

E. I/O Prefetching

In Nanvix, the disk buffer cache features synchronous reads and asynchronous write operations, but it lacks prefetching support for sequential reads. To further enhance the file system's performance, we ask students to implement this latter feature. To accomplish so, they have to add a read ahead function in the buffer cache, then they have to hack the read() system call to make use of this new operation; and finally they have to benchmark their solution.

With this assignment, students learn several lessons. First, they learn how prefetching can boost the performance of the system. Second, while working with the the buffer cache, students will have to deal with race conditions, and thus exercise their previous knowledge on process synchronization. Finally, students work with a core subsystem of the device system, thereby further understanding how it works as a whole.

Students should have about four weeks to work on this assignment: one week to first understand how the buffer cache subsystem works, two weeks to implement the block read ahead operation, and another week to hack the read() system call and evaluate their solution. With respect to grading, we suggest instructors to reward students according to the simplicity of their solution -the solution should take no more than a hundred lines of code.

F. Exploiting Security

In this assignment we students to seek and exploit security breaches in Nanvix. Intentionally, five vulnerabilities were left open in the system: (i) password cracking by brute-force attacking the passwords file; (ii) privilege escalation by editing the unprotected system's initialization file; (iii) kernel panic by writing random content in memory with the read() system call; (iv) memory dump using the write() system call; and (v) denial of service with a fork-bomb attack.

Students should browse the system call interface of the file system, and they learn two topics on information security with a hands-on cracking approach. First, they understand how vulnerabilities may be exploited and compromise sensitive information. Second, they are encouraged to rethink about software design, in what concerns information security.

What concerns course schedule, students should have about three weeks to work on this assignment: one week for learning how Nanvix deals with security, another week for seeking and exploiting security breaches, and a final week for writing reports about the encountered vulnerabilities. Regarding grading, we suggest instructors to reward students according to the number of security breaches they have exploited.

G. Evaluation Method

In order to evaluate the teaching methodology that we propose, we applied it in the undergraduate OSs course of PUC Minas. We measured the performance and motivation of students by observing their score on exams and assignments, and compiling their feedback from emails and surveys that we distributed, respectively.

At PUC Minas, undergraduate computer science students take the OSs course in their fifth academic semester. In this course that lasts about 16 weeks (64 hours), lectures are strictly theoretical and practical topics such as shell and concurrent programming are covered in extra-class assignments. To introduce our methodology, we adopted the following method.

In a first academic year, we kept the aforementioned teaching approach, but we gathered statistics about the performance of students on exams to find out what were the main challenges that they faced. Then, in a second academic year, we used this information to apply a slightly different teaching approach, in which we kept traditional lectures, but we adopted assignments in Nanvix. Again, we gathered statistics about what difficulties students experienced on exams. However, in addition, we asked students to answer a short survey about their thoughts on Nanvix being used for practical assignments.. Finally, in a third academic year, we used our previous experience to re-redesign the OSs course at PUC Minas. In this new version of the course, we kept the normal course schedule and assignments in Nanvix, but additionally we reserved some lectures to introduce the internals of our OS, and we allocated a partial-time teaching assistant to help students with their questions. In order to evaluate the effectiveness of this new version of the course, we gathered statistics about the performance of students on exams, and we also asked them to answer the same survey from the previous academic year.

V. TEACHING METHODOLOGY EVALUATION

In this section, we discuss the results that we observed when we applied our teaching methodology in the Operating Systems course of PUC Minas. First, we discuss the background experience we had when introducing our Nanvix-based methodology, and then we move on to an evaluation of the assignments and the teaching methodology itself.

A. Background Experience

In the first academic year, we observed that students had difficulty on the process and memory management topics. Their average score on exams in these subjects were 53.9% and 51.1%, respectively. To address this problem, in the second academic year we applied students to the Process Scheduling, Page Replacement and I/O Prefetching assignments in Nanvix. With this redesign, we observed a 68.1% and 59.1% raise in the average student score, in the process and memory management subjects respectively.

To redesign the OSs course for the third academic year, we considered the performance of students on exams in the previous academic year and their answers to a survey that we distributed. The answers to this survey are outlined in Figure 2. According to the survey, about 80% of the students answered that our assignment-based approach helped them to better understand some concepts and principles that were introduced in the lectures. Additionally, about 35% of the students reported that Nanvix helped them in practical topics. When we asked students to give us their thoughts about our assignment methodology, about 50% of them asked us for practical lectures on Nanvix, 20% suggested us to introduce our OS in theoretical lectures, and about 45% asked for the Security assignment.

Based on this previous experience, in the third academic year, we applied to students the Process Scheduling, Semaphores, and Security assignments. Moreover, we alternatively also let students work on the Page Replacement assignment for extra points. In this redesign, we found out that (i) Nanvix helped 83.8% and 40.5% of the students, in theoretical and practical topics, respectively; and (ii) that 5.6% and 13.9% of the students complained about the schedule and the difficulty of assignments, respectively.

B. Assignments Evaluation

Figures 4 and3, presents the score of the students in the assignments. These results were gathered during the third academic year from a sample of 44 students.

In the Process Scheduling assignment 34 students submitted their solutions on schedule. In average, 81% of them completed the requested tasks, and 58% implemented a prioritybased scheduler. They reported that the difficulty of the assignment was adequate, and the hardest part was to understand how priorities were assigned by the kernel.

In the Semaphores assignment, 15 students submitted their solutions on schedule. In average, 90% them were able to successfully complete the requested tasks, and 30% of have finished the extra ones. Students reported that the assignment was challenging, but it helped them to understand how the kernel manipulates the state of processes under the hood. Concerning the difficulty of the assignment, students found that the hardest part was to write the system call for manipulating the semaphore itself. According to them, at first it was not clear how to properly put processes to sleep and wake them up, but once they figured out that the process management module exported routines for doing so, these tasks became straightforward. In the Security assignment, 31 students submitted their solutions on schedule. In average, 93.9% of them were able to find at least three vulnerabilities in the system, and 59.1% succeeded on exploiting more than three vulnerabilities. Students reported that the assignment was challenging, but fun. They enjoyed to deal with information security with a hands-on approach, and according to them, the privilege escalation and memory dump security breaches were the hardest to exploit.

In the Page Replacement assignment, 10 students submitted their answers on schedule. In average, 83.3% were able to successfully complete the requested task. The most popular solution among the students was the second chance algorithm, and 26.7% of them implemented the not recently used page replacement policy. They found that the difficulty of the assignment was adequate, and that the hardest part was to know how to correctly inspect page table entries.

C. Course Evaluation

During the three academic years we measured the performance and motivation of students. These results are presented in Table III and discussed next. In a long-term perspective, our teaching methodology helped students to enhance their performance in the OSs course. With Nanvix, the average score of students increased in 11.2% and the failure rate dropped in 47.7%. Furthermore, the number of students who scored more than 75% increased from 7% to 21% along these academic years, which shows that our Nanvix-based methodology motivated students to work hard and also to push up their score in the course.

Additionally, during the two last academic years, several students reported us that they enjoyed working with Nanvix. Figure 5 presents a compilation of the feedback that we received from students on emails, surveys and exams. In this chart, keywords that have higher counts appear bigger than those that have lower counts. Students found that Nanvix has helped them to consolidate principles and concepts that they studied in theoretical lectures, learn about OS's internals, and fell further motivation and interest for the field.

VI. CONCLUSIONS AND FUTURE PERSPECTIVES

In this work, we (i) present Nanvix, an OS to be used in OSs courses as supporting software; (ii) introduce a flexible assignment-based teaching methodology that may be used with it; and (iii) we presented an evaluation of this methodology when applied in the OSs course in PUC Minas.

To introduce our teaching methodology, we adopted an incremental three-year method. In the first one, we kept traditional lectures and assignments; in the second year, we kept traditional lectures, but we adopted assignments in Nanvix; and finally in the third academic year, we introduced Nanvix in theoretical lectures and applied assignments on it. With our teaching methodology, the average score of students in the OSs course increased in 11.2%, and the failure rate dropped to 47.7%. Moreover, students found that Nanvix helped them to consolidate OS principles and felt more motivated.

Besides PUC Minas, Nanvix is already in use in the Federal University of Santa Catarina (Brazil) and University of Grenoble Alpes (France). In future work, we intend to extend and improve our teaching methodology based on the experience of instructors of these partner universities.

Fig. 1 .

 1 Fig. 1. Nanvix architecture.

Fig. 2 .

 2 Fig. 2. Survey results for second academic year.

Fig. 3 .

 3 Fig. 3. Assignments evaluation detailed.

Fig. 4 .

 4 Fig. 4. Assignments evaluation overview.

Fig. 5 .

 5 Fig. 5. Qualitative evaluation of Nanvix.

TABLE I COMPARISON

 I BETWEEN OPERATING SYSTEMS.

	Name	Complete?	Teaching Methodology	Comments
	Minix	yes	none	outdated features
	Nachos	no	assignments, not flexible	does not run on hardware
	GeekOS	no	assignments, not flexible	no Posix compliance
	Nanvix	yes	assignments, flexible	Unix and Posix support
	III. THE NANVIX INSTRUCTIONAL OPERATING SYSTEM

TABLE II ASSIGNMENTS

 II SHIPPED WITH NANVIX.

	Subject	Assignment Name	Activities	Duration
	Process	Process Scheduling Implement a priority scheduler	3 weeks
	Management	Semaphores	Implement semaphores in kernel	3 weeks
	Memory Management	Page Replacement	Implement page eviction	4 weeks
	I/O Management	Prefetching	Implement disk block prefetching 4 weeks
	File Systems and Security	Security	Exploit security breaches	3 weeks

TABLE III COURSE

 III EVALUATION.

	Academic Year Failure Rate Average Score
	1st year	53.3%	57.9%
	2nd year	16.0%	67.6%
	3rd year	27.9%	65.2%


Per-Lennart François Hild

Frederick A Larsson

Leckie

Localization due to

may come


José M Araújo

Carlos E T Dórea
email: cetdorea@ufba.br

Controlled Invariant Polyhedral Sets for Constrained Discrete-Time Descriptor Systems

Keywords: Descriptor systems, set invariance, constraints

This paper addresses the problem of constructing controlled invariant polyhedral sets for linear discrete-time descriptor systems subject to state and control constraints and persistent disturbances. Regardless the large number of contributions on set invariance for linear systems in the standard form, there are few works dealing with set invariance properties in the case of descriptor systems. Here, assuming regularity and causality of the descriptor system, the state equations are written in such way that standard algorithms can be directly applied. Moreover, state and control constraints can be enforced through a piecewise linear delayed state feedback. A numerical example is presented to illustrate these ideas.

Introduction

Descriptor systems is an important class of linear systems, also called generalized state space, or singular systems and yet implicit systems when algebraic equations are present. Very important works have built a rich theoretical and applied framework on the subject [START_REF] Luenberger | Time-invariant descriptor systems[END_REF], [START_REF] Yip | Solvability, controllability, and observability of continuous descriptor systems[END_REF], [START_REF] Cobb | Feedback and pole placement in descriptor variable systems[END_REF], [START_REF] Dai | Singular control systems[END_REF] and [START_REF] Lewis | A survey of linear singular systems[END_REF]. The design of constrained control systems is very useful in practice, since certain requirements of supply or safety impose limits on physical quantities. The use of the set-invariance concept is a efficient way of dealing with constrained control systems (see [START_REF] Blanchini | Set invariance in control[END_REF], [START_REF] Dórea | A,B)-invariance conditions of polyhedral domains for continuous-time systems[END_REF] and [START_REF] Dorea | A,B)-invariant polyhedral sets of linear discrete-time systems[END_REF] and references therein). Several works concerning constrained control for standard state-space systems can be found in the literature [START_REF] Blanchini | Ultimate boundedness control for uncertain discrete-time systemsvia setinduced Lyapunov functions[END_REF], [START_REF] Vassilaki | Feedback control in linear discrete-time systems under state and control constraints[END_REF] and [START_REF] Vassilaki | Constrained regulation of linear continuous-time dynamical systems[END_REF]. For the class of descriptor linear systems, however, the contributions on the characterization of controlled invariance over polyhedral sets are not so numerous. Some important works on positive invariance under linear pole placement design can be found on literature [START_REF] Georgiou | A design approach for constrained regulation in discrete singular systems[END_REF], [START_REF] Tarbouriech | Positively invariant-sets for singular discrete-time systems[END_REF], [START_REF] Castelan | Simple and weak ∆-invariant polyhedral sets for discrete-time singular systems[END_REF], [START_REF] Tarbouriech | An eigenstructure assignment approach for constrained linear continuous-time systems[END_REF] and [START_REF] Lin | Set invariance conditions for singular linear systems subject to actuator saturation[END_REF]. However, the use of linear feedback may lead to very conservative solutions, not coping with severe control constraints or high amplitude disturbances. In this note, controlled invariance of polyhedral sets for discrete time linear descriptor systems is analyzed. By assuming that the system is regular and causal, the state equation can be rewritten in an augmented form which gives the possibility of applying available methods for characterization of controlled invariance for polyhedral sets in standard linear systems. A delayed state-feedback control law can then be synthesized to enforce the constraints. A numerical example is presented in order to illustrate the effectiveness of the proposal.

Contribution for Technological Innovation

Descriptor systems arise from a diversity of areas, such economics, chemical and electrical [START_REF] Luenberger | Time-invariant descriptor systems[END_REF]. The control of this class of models is very important, since a series of requirements of quality, reliability and safety are involved. In many cases, physical constraints are inherent, and comprising operational limits of supply/safety. The setinvariance for control under constraints is well developed for systems in the classical state representation. For descriptor model a few works have contributed in this aspect. The present paper tries to rise new ideas in this direction.

Preliminaries

The nth-dimensional system under study is in the form of a perturbed descriptor statespace representation:

(

1) = ( ) ( ) ( ) Ex k Ax k Bu k Dd k + + + (1)
in which , ,

n m p x u d ∈ ℜ ∈ ℜ ∈ ℜ .
The disturbance amplitude is supposed to be bounded for all instants k. When ( ) = < rank E q n , without loss of generality, the state vector can be partitioned:

1 2 ( 1) ( 1) = ( 1) x k x k x k +   +   +   (2)
and the system matrices can be written:

11 12 1 1 21 22 2 2 0 = , = , = , = 0 0 q A A B D I E A B D A A B D                         (3)
The hypothesis that the system is causal assures that 22

A is invertible [START_REF] Dai | Singular control systems[END_REF]. In this case, manipulations on the systems matrices leads to the form:

( ) ( 1) = ( ) ( ) ( 1)
( 1)

d k x k Ax k Bu k Cu k D d k   + + + + +   +   % % % % (4)
in which

A A A A B A A B A B A A A A A A A A B A A B - - - - - -     - -     - - - -     % % 1 1 12 22 2 1 1 1 1 22 2 22 21 1 12 22 22 2 0 0 = , = ( ) D A A D C D A B A A D A A A D - - - - -   -       - - - -     % %
Now, one can see that one-step forward terms in control input and in disturbance appear. This is not a problem for the disturbance, since it is not measured. For the control input, it is convenient to consider it as another state variable. The augmented state vector is then:

( 1) ( 1) = ( 1) x k k u k χ +   +   +   (5)
The augmented state equation are now given as:

( ) ( 1) = ( ) ( 1)
( 1) 0 0

d k D A B C C k k u k d k I I χ χ       +   + + ∆ + +         +         % % % % % (6)
In which

( 1) = ( 1) ( ) u k u k u k ∆ + + -
. This is a standard state-space model with state vector ( ) ( )

T T T x k u k     and bounded disturbance ( ) ( 1)
T T T d k d k   + 
 , and application of well-established algorithms for standard systems is straightforward. It should be noticed that this extended system has n m + eigenvalues: (i) q finite eigenvalues of (1);(ii) n q eigenvalues equal to 0 corresponding to infinite eigenvalues of (1); and m eigenvalues equal to 1 corresponding to the control input dynamics. In the next section, this representation will be useful for the characterization of controlled invariance of polyhedral sets that represent constraints on state variables and control inputs.

Solution of Constrained Control Problem

Controlled Invariance

Assume that system (1) is subject to the following state and control constraints:

( ) = { : }, ( ) = { : }, ( ) = { : } x k x Gx u k u Uu u k u L u ρ υ ϕ ∈ Ω ≤ ∈ ≤ ∆ ∈ ∆ ∆ ∆ ≤ U V ( 7
)
The disturbance is supposed to be bounded as follows:

( ) = { : } d k d Vd µ ∈ ≤ D ( 8
)
Considering the augmented representation, the constraints on state and control can be written as:

0 ( ) = { : }, = , = 0 G k U ρ χ χ χ ρ ρ υ     ∈ Γ ≤         G G
and the bounds on the disturbance as:

( ) 0 = { : }, = , = ( 1) 0 d k V d d d k V µ µ µ µ       ∈ Ψ ≤       +       V V
The goal now is to construct a control law which enforces the constraints, for all disturbances in Ψ . Such a construction will be based on the following concept [START_REF] Blanchini | Ultimate boundedness control for uncertain discrete-time systemsvia setinduced Lyapunov functions[END_REF]: Definition 4.1 A set is λ-contractive controlled invariant with respect to system (6) and constraints ( 7),( 8) if for any ( )

k χ ∈ Γ , u ∃∆ such that ( ) ( 1) = ) ( 1) ( 1) 0 0 d k D A B C C k k u k d k I I χ χ λ       +   + + ∆ + + ∈ Γ         +         % % % % % with 0 1 λ < ≤ .
The constrained control problem can then be solved by computing * Γ , the maximal controlled invariant set contained in Γ [START_REF] Dorea | A,B)-invariant polyhedral sets of linear discrete-time systems[END_REF][START_REF] Blanchini | Ultimate boundedness control for uncertain discrete-time systemsvia setinduced Lyapunov functions[END_REF]. Hence, if the initial state is consistent with the algebraic equation: Once the maximal controlled invariant is obtained, a piecewise linear control law can be computed that assures the respect to constraints [START_REF] Blanchini | Ultimate boundedness control for uncertain discrete-time systemsvia setinduced Lyapunov functions[END_REF]:

21 1 22 2 2 2 0 = (0) (0) (0) (0) A x A x B u D d + + + (9
( 1) = [ ( )] = [ ( ), ( )] u k k x k u k φ χ φ ∆ + (10)
One can see that such control law is delayed with respect to the augmented state vector.

Admissible Initial Conditions

In the previous subsection, the issue of consistency of initial conditions was mentioned. The control law [START_REF] Vassilaki | Feedback control in linear discrete-time systems under state and control constraints[END_REF] enforces state and control constraints as long as the initial state satisfies * (0) χ ∈ Γ . However, differently from standard linear systems, (0) χ may not be consistent, i.e., may not satisfy the algebraic equation [START_REF] Blanchini | Ultimate boundedness control for uncertain discrete-time systemsvia setinduced Lyapunov functions[END_REF]. In this case, a jump can occur for = 0 k and this is unpredictable due the disturbance (0) d .

Let (0 )

x + be the state after the jump. The dynamic part of state vector does not experiment jumps in = 0 k . It can be verified by changing the representation of (1) into a canonical representation where the dynamic and algebraic equations are decoupled [START_REF] Castelan | Simple and weak ∆-invariant polyhedral sets for discrete-time singular systems[END_REF]. Hence 1

1 (0 ) = (0) x x + .
The algebraic portion can be made explicit from ( 9):

1 1 1 2 22 21 1 22 2 22 2 (0 ) = (0) (0) (0) x A A x A B u A D d + - - - - - - (11)
The consistency of the initial condition can be treated on the basis of the following definition.

Definition 4.2: Consider the set * Γ , controlled invariant with respect to the system (6) and constraints [START_REF] Dórea | A,B)-invariance conditions of polyhedral domains for continuous-time systems[END_REF], [START_REF] Dorea | A,B)-invariant polyhedral sets of linear discrete-time systems[END_REF]. The set of admissible initial states is defined by:

{ } * = (0) : (0) : (0 ) , (0) ad x u x d + Λ ∈ Ω ∃ ∈ ∈ Γ ∀ ∈ U D .
Let now * Γ be the polyhedral set

{ } * * * = :
x G x ρ Γ ≤ . In this case, the set of admissible initial states is also a polyhedron, given by the set of

1 2 (0) = (0) (0) T T T x x x     such that (0) u ∃ which satisfies, (0) Vd µ ∀ ≤ : * * * * 1 1 1 1 22 21 22 2 22 2 0 0 (0) (0) (0) 0 0 I G G G x u d A A A B A D U ρ υ - - -                           + + ≤ - - -                             (12)
Since (0) d is not measured, its influence can be taken into account by considering the worst case row-by-row. Define then the vector:

* 1 22 2 0 = max 0 i d i G d A D µ σ - ≤       -       -               V (13)
The variable (0) u can be eliminated by a projection computed like in [START_REF] Dorea | A,B)-invariant polyhedral sets of linear discrete-time systems[END_REF], resulting in the following polyhedron on 1 x :

{ } 1 1 1 1 1 = (0) : (0) x x H x h Λ ≤ (14)
The set of admissible initial states is then given by: [ ]

1 1 0 = (0) : (0) ad h H x x G ρ         Λ ≤               (15)

Numerical Example

Consider the same system used in [START_REF] Tarbouriech | Positively invariant-sets for singular discrete-time systems[END_REF][START_REF] Castelan | Simple and weak ∆-invariant polyhedral sets for discrete-time singular systems[END_REF][START_REF] Tarbouriech | An eigenstructure assignment approach for constrained linear continuous-time systems[END_REF]:

1 0 0 1.2 0 0 0 1 0 = 0 1 0 , = 1 0.7 1 , = 1 1 , = 1 0 0 0 2 0.5 1.2 0.5 2 1 E A B D                 -- - -                 - -        
The following state and control constraints [START_REF] Dórea | A,B)-invariance conditions of polyhedral domains for continuous-time systems[END_REF], [START_REF] Dorea | A,B)-invariant polyhedral sets of linear discrete-time systems[END_REF] are imposed: ,| | 10, = 1, 2

s s i G x u i ρ ≤ ≤ with 0 1 0.9318 1 = 1 0 0.1164 , = 2 0 0 1 1 s s G ρ         - -            
The disturbances are bounded as | ( ) | d k γ ≤ . By application of the algorithm proposed in [START_REF] Dorea | A,B)-invariant polyhedral sets of linear discrete-time systems[END_REF], it was verified that the maximal controlled invariant polyhedron contained in the set of constraints, with a contraction rate = 0.99 λ , is non-empty for = 1.082115 max γ γ ≤ . Figure 1 shows the controlled invariant polyhedron for = 1 γ projected onto control and state spaces, where it can be noticed that the original polyhedron of the constraints in states is itself controlled invariant. These results are better than those obtained by the pole placement control law proposed in [START_REF] Castelan | Simple and weak ∆-invariant polyhedral sets for discrete-time singular systems[END_REF], where = 0.208815 max γ .

A piecewise control law that enforces the constraints can be computed as in [START_REF] Blanchini | Ultimate boundedness control for uncertain discrete-time systemsvia setinduced Lyapunov functions[END_REF].

However, it turns out that for this example, with = 1 ( 1) =

( ) = ( ) ( ) u k F k F x k F u k χ ∆ + +
computed by linear programming as in [START_REF] Vassilaki | Feedback control in linear discrete-time systems under state and control constraints[END_REF][START_REF] Vassilaki | Constrained regulation of linear continuous-time dynamical systems[END_REF], leading to 0.9370 0.7409 0 0.8944 0.4852 = 0.7146 0.1915 0 0.0385 1.8254

F - -     - - -   .
It should be noticed that due to the null column in F , the closed-loop augmented systems has: (i) 4 finite eigenvalues in 0.6663 , 0.4669 -, 0.0329 -, 0.0305 , and (ii) 1 eigenvalue equal to 0, corresponding to the infinite pole of (1). Its confirms stability of the system under closed-loop.

The set of admissible initial states coincides with the initial polyhedron. A simulation was carried out with initial conditions [ ]

(0) = 1.649 0.2354 0 T x - , [ ] (0 )

Conclusions and Future Works

A characterization of controlled invariance of polyhedral sets was proposed for descriptor linear discrete time systems, based on an augmented state-space representation in the form of a classical linear system. Under this representation, standard algorithms can be used to compute controlled invariant sets. Then, a delayed state feedback law can be synthesized to solve a control problem under state and control constraints for systems subject to bounded disturbances. Through a numerical example, it was shown that the proposed controller can outperform linear ones proposed in literature. Future works will focus the study of the solution to the problem by means of static and dynamic output feedback laws, already characterized in [START_REF] Dórea | Output-feedback controlled invariant polyhedra for constrained linear systems[END_REF] for classical linear systems. The design of a control law for simultaneous regularization and constraints satisfaction will be also investigated.

  k → ∞ , guaranteeing asymptotic stability.

Fig. 1 .

 1 Fig. 1. Projection onto the control space (a) and the state space (b) of the controlled invariant polyhedron computed with 1 γ = , together with a control and a state trajectory.

  disturbances are depicted in figure1.

Acknowledgments. The Authors would like to thank to their Institutions and to PROAP/CAPES for financial support.