Paweł Marciniak
email: pawel.marciniak@gmail.com

Nikitas Liogkas
email: nikitas@cs.ucla.edu

Arnaud Legout
email: arnaud.legout@sophia.inria.fr

Eddie Kohler
email: kohler@cs.ucla.edu

Small Is Not Always Beautiful *

Peer-to-peer content distribution systems have been enjoying great popularity, and are now gaining momentum as a means of disseminating video streams over the Internet. In many of these protocols, including the popular BitTorrent, content is split into mostly fixed-size pieces, allowing a client to download data from many peers simultaneously. This makes piece size potentially critical for performance. However, previous research efforts have largely overlooked this parameter, opting to focus on others instead.

This paper presents the results of real experiments with varying piece sizes on a controlled Bit-Torrent testbed. We demonstrate that this parameter is indeed critical, as it determines the degree of parallelism in the system, and we investigate optimal piece sizes for distributing small and large content. We also pinpoint a related design tradeoff, and explain how BitTorrent's choice of dividing pieces into subpieces attempts to address it.

Introduction

Implementation variations and parameter settings can severely affect the service observed by the clients of a peer-to-peer system. A better understanding of protocol parameters is needed to improve and stabilize service, a particularly important goal for emerging peer-to-peer applications such as streaming video.

BitTorrent is widely regarded as one of the most successful swarming protocols, which divide the content to be distributed into distinct pieces and enable peers to share these pieces efficiently. Previous research efforts have focused on the algorithms believed to be the major factors behind Bit-Torrent's good performance, such as the piece and peer selection strategies. However, to the best of our knowledge, no studies have looked into the op-timal size of content pieces being exchanged among peers. This paper investigates this parameter by running real experiments with varying piece sizes on a controlled testbed, and demonstrates that piece size is critical for performance, as it determines the degree of parallelism available in the system. Our results also show that, for small-sized content, smaller pieces enable shorter download times, and as a result, BitTorrent's design choice of further dividing content pieces into subpieces is unnecessary for such content. We evaluate the overhead that small pieces incur as content size grows and demonstrate a trade-off between piece size and available parallelism. We also explain how this trade-off motivates the use of both pieces and subpieces for distributing large content, the common case in BitTorrent swarms.

The rest of this paper is organized as follows. Section 2 provides a brief description of the Bit-Torrent protocol, and describes our experimental methodology. Section 3 then presents the results of our experiments with varying piece sizes, while Section 4 discusses potential reasons behind the poor performance of small pieces when distributing large content. Lastly, Section 5 describes related work and Section 6 concludes.

Background and Methodology

BitTorrent Overview BitTorrent is a popular peer-to-peer content distribution protocol that has been shown to scale well with the number of participating clients. Prior to distribution, the content is divided into multiple pieces, while each piece is further divided into multiple subpieces. A metainfo file containing information necessary for initiating the download process is then created by the content provider. This information includes each piece's SHA-1 hash (used to verify received data) and the address of the tracker, a centralized component that facilitates peer discovery.

In order to join a torrent-the collection of peers participating in the download of a particular content-a client retrieves the metainfo file out of band, usually from a Web site. It then contacts the tracker, which responds with a peer set of randomly selected peers. These might include both seeds, who already have the entire content and are sharing it with others, and leechers, who are still in the process of downloading. The new client can then start contacting peers in this set and request data. Most clients nowadays implement a rarest-first policy for piece requests: they first ask for the pieces that exist at the smallest number of peers in their peer set. Although peers always exchange just subpieces with each other, they only make data available in the form of complete pieces: after downloading all subpieces of a piece, a peer notifies all peers in its peer set with a have message. Peers are also able to determine which pieces others have based on a bitfield message, exchanged upon the establishment of new connections, which contains a bitmap denoting piece possession.

Each leecher independently decides who to exchange data with via the choking algorithm, which gives preference to those who upload data to the given leecher at the highest rates. Thus, once per rechoke period, typically every ten seconds, a leecher considers the receiving data rates from all leechers in its peer set. It then picks out the fastest ones, a fixed number of them, and only uploads to those for the duration of the period. Seeds, who do not need to download any pieces, follow a different unchoke strategy. Most current implementations unchoke those leechers that download data at the highest rates, to better utilize seed capacity.

Experimental Methodology

We have performed all our experiments with private torrents on the PlanetLab platform [START_REF] Bavier | Operating System Support for Planetary-Scale Network Services[END_REF]. These torrents comprise 40 leechers and a single initial seed sharing content of different sizes. Leechers do not change their available upload bandwidth during the download, and disconnect after receiving a complete copy of the content. The initial seed stays connected for the duration of the experiment, while all leechers join the torrent at the same time, emulating a flash crowd scenario. The number of parallel upload slots is set to 4 for the leechers and seed. Although system behavior might be different with other peer arrival patterns and torrent configurations, there is no reason to believe that the conclusions we draw are predicated on these parameters.

The available bandwidth of most PlanetLab nodes is relatively high for typical real-world clients. We impose upload limits on the leechers and seed to model more realistic scenarios, but do not impose any download limits, as we wish to observe differences in download completion time with varying piece sizes. The upload limits for leechers follow a uniform distribution from 20 to 200 kB/s, while the seed's upload capacity is set to 200 kB/s. We collect our measurements using the official (mainline) BitTorrent implementation, instrumented to record interesting events. Our client is based on version 4.0.2 of the official implementation and is publicly available for download [START_REF]BitTorrent instrumented client[END_REF]. We log the client's internal state, as well as each message sent or received along with the content of the message. Unless otherwise specified, we run our experiments with the default parameters.

The protocol does not strictly define the piece and subpiece sizes. An unofficial BitTorrent specification [3] states that the conventional wisdom is to "pick the smallest piece size that results in a metainfo file no greater than 50-75 kB". The most common piece size for public torrents seems to be 256 kB. Additionally, most implementations nowadays use 16 kB subpieces. For our experiments, we always keep the subpiece size constant at 16 kB, and only vary the piece size. We have results for all possible combinations of different content sizes (1 MB, 5 MB, 10 MB, 20 MB, 50 MB, and 100 MB) and piece sizes (16 kB, 32 kB, 64 kB, 128 kB, 256 kB, 512 kB, 1024 kB, and 2048 kB).

Results

Our results, presented in this section, demonstrate that small pieces are preferable for the distribution of small-sized content. We also discuss the benefits and drawbacks of small pieces for other content sizes, and evaluate the communication and metainfo file overhead that different piece sizes incur for larger content.

Small Content

Even though most content distributed with Bit-Torrent is large, it is still interesting to examine the impact of piece size on distributing smaller content. In addition to gaining a better understanding of the trade-offs involved, it may also sometimes be desirable to utilize BitTorrent to avoid server overload when distributing small content, e.g., in the case of websites that suddenly become popular. Figure 2 shows the median download completion times of the 40 leechers downloading a 5 MB file, for different numbers of pieces, along with standard deviation error bars. Clearly, smaller piece sizes enable faster downloads. In particular, performance deteriorates rapidly when increasing the piece size beyond 256 kB. The same observations hold for experiments with other small content (1 and 10 MB).

To better illustrate the benefits of small pieces, Figure 1 shows the cumulative distribution functions (CDF) of leecher download completion times for 16 and 512 kB pieces (graphs (a) and (b)). With small pieces, most peers complete their download within the first 100 seconds. With larger pieces, on the other hand, the median peer completes in more than twice the time, and there is greater variability. The reason is that smaller pieces let peers share data sooner. As mentioned before, peers send out have messages announcing new pieces only after downloading and verifying a complete piece. Decreasing piece size allows peers to download complete pieces, and thus start sharing them with others, sooner. This increases the available parallelism in the system, as it enables more opportunities for parallel downloading from multiple peers.

This benefit is also evident when considering peer upload utilization, which constitutes a reliable metric of efficiency, since the total peer upload capacity represents the maximum throughput the system can achieve as a whole. Figure 1 shows utilization scatterplots for all five-second time intervals during the download (graphs (c) and (d)). Average upload utilization for each of 5 experiment runs is plotted once every 5 seconds. Thus, there are five dots for every time slot, representing the average peer upload utilization for that slot in the corresponding run. The metric is torrent-wide: for those five seconds, we sum the upload bandwidth expended by leechers and divide by the available upload capacity of all leechers still connected to the system. Thus, a utilization of 1 represents taking full advantage of the available upload capacity. As previously observed [START_REF] Legout | Clustering and Sharing Incentives in BitTorrent Systems[END_REF], utilization is low at the beginning and end of the session. During the majority of the download, however, a smaller piece size increases the number of pieces peers are interested in, which leads to higher upload utilization.

These conclusions are reinforced by the fact that small pieces enable the seed to upload less duplicate pieces during the beginning of a torrent's lifetime. Figure 3 indeed plots the number of pieces (unique and total) uploaded by the single seed in our 5 MB experiments, for two representative runs. Although the seed finishes uploading the first copy of the content at approximately the same time in both cases (vertical line on the graphs), it uploads 139% more duplicate data with larger pieces (5120 kB for 512 kB pieces vs. 2144 kB for 16 kB pieces), thus making less efficient use of its valuable upload bandwidth. Avoiding this waste can lead to better performance, especially for low-capacity seeds [START_REF] Legout | Clustering and Sharing Incentives in BitTorrent Systems[END_REF]. This behavior can be explained as follows. The official BitTorrent implementation we are using always issues requests for the rarest pieces in the same order. As a result, while a leecher is downloading a given piece, other leechers might end up requesting the same piece from the seed. With smaller pieces, the time interval before a piece is completely down- Unique line represents the pieces that had not been previously uploaded, while the Total line represents the total number of pieces uploaded so far. The vertical line denotes the time the seed finished uploading the first copy of the content to the system. The duplicate piece overhead is significantly lower for small pieces.

loaded and shared becomes shorter, mitigating this problem. This could be resolved by having leechers request rarest pieces in random order instead.

In summary, small pieces enable significantly better performance when distributing small content. As a result, the distinction of pieces and subpieces that the BitTorrent design dictates is unnecessary for such content. For instance, in our 5 MB experiments, pieces that are as small as subpieces (16 kB) are optimal. Thus, the content could just be divided into pieces with no loss of performance.

Piece Size Impact

Before investigating the impact of piece size on the distribution of larger content, let us first examine the advantages and drawbacks of small pieces. We have seen that their benefits for small content are largely due to the increased peer upload utilization such pieces enable. Since small pieces can be downloaded sooner than large ones, leechers are able to share small pieces sooner. In this manner, there is more data available in the system, which gives peers a wider choice of pieces to download. In addition to this increased parallelism, small pieces provide the following benefits (some of which do not affect our experiments).

• They decrease the number of duplicate pieces uploaded by seeds, thereby better utilizing seed upload bandwidth.

• The rarest-first piece selection strategy is more effective in ensuring piece replication. A greater number of pieces to choose from entails a lower probability that peers download the same piece, which in turn improves the diversity of pieces in the system.

• There is less waste when downloading corrupt data. Peers can discover bad pieces sooner and re-initiate their download.

On the other hand, for larger content, the overhead incurred by small pieces may hurt performance. This overhead includes the following.

• Metainfo files become larger, since they have to include more SHA-1 hashes. This would increase the load on a Web server serving such files to clients, especially in a flash crowd case.

• Bitfield messages also become larger due to the increased number of bits they must contain.

• Peers must send more have messages, resulting in increased communication overhead.

In the next section, we shall see that these drawbacks of small pieces outweigh their benefits, for larger content. Thus, the choice of piece size for a download should take the content size into account.

Larger Content

Figure 4 shows the download completion times of the 40 leechers downloading a 100 MB file for different piece sizes. We observe that small pieces are no longer optimal. In this particular case, sizes around 256 kB seem to perform the best. Experiments with other content sizes (20 and 50 MB) show that the optimal piece size increases with content size. For instance, for experiments with a 50 MB content, the optimal piece size is 64 kB. Note that the unofficial guideline for choosing the piece size, mentioned in Section 2, would yield sizes of 32 and 16 kB for a 100 MB and 50 MB content respectively, a bit off from the optimal values.

In an effort to better understand this trade-off regarding the choice of piece size, we evaluate the metainfo file and communication overhead. The former is shown in Figure 5. As expected, small pieces produce proportionately larger metainfo files (note that the x axis is logarithmic). 16 kB pieces, for instance, produce a metainfo file larger than 120 kB, as compared to a less than 10 kB file for 256 kB pieces. For large content in particular, this might have significant negative implications for the Web server used to distribute such files to clients.

Bitfield messages become proportionately larger too. For instance, for the 100 MB content, these messages are 805 and 55 bytes for 16 and 256 kB pieces respectively. Figure 6 communication overhead due to bitfield and have messages, expressed as a percentage of the total upload traffic per peer. The overhead ranges from less than 1% for larger piece sizes to around 9% for 16 kB pieces. However, it is not clear that this overhead is responsible for the worse performance of smaller pieces. Although these control messages do occupy upload bandwidth, they do not necessarily affect the data exchange among peers, and thus their download performance. For example, looking at the corresponding overhead for smaller content, we observe that the overhead curve looks very similar. This indicates that increased communication overhead is most likely neither the cause of the worse performance of small pieces for larger content, nor does it explain the observed trade-off. In the next section, we formulate two hypotheses that might help identify the true cause of this behavior.

In summary, when distributing larger content, the optimal piece size depends on the content size, due to a trade-off between the increased parallelism small pieces provide and their drawbacks. BitTorrent arguably attempts to address this tradeoff by further dividing pieces into subpieces, to get the best of both worlds: subpieces increase opportunities for parallel downloading, while pieces mitigate the drawbacks of small verifiable units.

Discussion

The results presented in the previous section point to a hidden reason behind the poor performance of small pieces when distributing large content. We have two hypotheses that might help explain that.

First, small pieces reduce opportunities for subpiece request pipelining. In order to prevent delays due to request/response latency, and to keep the download pipe full most of the time, most Bit-Torrent implementations issue requests for several consecutive subpieces back-to-back. This pipelining, however, is restricted within the boundaries of a single piece. This is done in order to use available bandwidth to download complete pieces as soon as possible, and share them with the rest of the swarm. Similarly, peers do not typically issue a request for subpieces of another piece to the same peer before completing the previous one. Thus, for a content with 32 kB pieces, for instance, only two subpiece requests per peer can be pending at any point in time. For small content, the impact of reduced pipelining is negligible, as the download completes quickly anyway. For larger content, however, it might severely affect system performance, as it limits the total number of simultaneous requests a peer can issue. Additionally, this matter gains importance as available peer bandwidth rises, since the request/response latency then starts to dominate time spent on data transmission.

Furthermore, small pieces may incur slowdown due to TCP effects. With a small piece size, a given leecher is more likely to keep switching among peers to download different pieces of the content. This could have two adverse TCP-related effects: 1) the congestion window would have less time to ramp up than in the case of downloading a large piece entirely from a single peer, and 2) the congestion window for unused peer connections would gradually decrease after a period of inactivity, due to TCP congestion window validation [START_REF]TCP Congestion Window Validation[END_REF], which is enabled by default in recent Linux kernels, such as the ones running on the PlanetLab machines in our experiments. A large piece size, on the other hand, would enable more efficient TCP transfers due to the lower probability of switching from peer to peer. Note, however, that, even in that case, there is no guarantee that all subpieces of a piece will be downloaded from the same peer.

Related Work

To the best of our knowledge, this is the first study that systematically investigates the optimal piece size in BitTorrent. Bram Cohen, the protocol's creator, first described BitTorrent's main algorithms and their design rationale [START_REF] Cohen | Incentives Build Robustness in Bit-Torrent[END_REF]. In version 3.1 of the official implementation he reduced the default piece size from 1 MB to 256 kB [START_REF]BitTorrent mailing list: Poor Performance with Version 3.1?[END_REF], albeit without giving a concrete reason for doing so. Presumably, he noticed the performance benefits of smaller pieces.

Some previous research efforts have looked into the impact of piece size in other peer-to-peer content distribution systems. Hoßfeld et al. [START_REF] Hoßfeld | Influence of the Size of Swapping Entities in Mobile P2P File-Sharing Networks[END_REF] used simulations to evaluate varying piece sizes in an eDonkey-based mobile file-sharing system. They found that download time decreases with piece size up to a certain point, confirming our observations, although they did not attempt to explain this behavior. The authors of Dandelion [START_REF] Sirivianos | Dandelion: Cooperative Content Distribution with Robust Incentives[END_REF] evaluate its performance with different piece sizes, and mention TCP effects as a potential reason for the poor performance of small pieces. However, small pieces in that system may also be harmful because they increase the rate at which key requests are sent to the central server. CoBlitz [START_REF] Park | Scale and Performance in the CoBlitz Large-File Distribution Service[END_REF] faces a similar problem with smaller pieces requiring more processing at CDN nodes. The authors end up choosing a piece size of 60 kB, because that can easily fit into the default Linux outbound kernel socket buffers. The Slurpie [START_REF] Sherwood | Slurpie: A Cooperative Bulk Data Transfer Protocol[END_REF] authors briefly allude to a piece size trade-off, and mention TCP overhead as a drawback of small pieces. Lastly, during the evaluation of the CREW system [START_REF] Deshpande | CREW: A Gossip-based Flash-Dissemination System[END_REF], the authors find a piece size of 8 kB to be optimal for distributing a 800 kB content, but they do not attempt to explain that.

Conclusion

This paper presents results of real experiments with varying piece sizes on a controlled BitTorrent testbed. We show that piece size is critical for performance, as it determines the degree of parallelism in the system. Our results explain why small pieces are the optimal choice for small-sized content, and why further dividing content pieces into subpieces is unnecessary for such content. We also evaluated the overhead small pieces incur for larger content, and discussed the design trade-off between piece size and available parallelism.

It would be interesting to investigate our two hypotheses regarding the poor performance of small pieces with larger content. We would also like to extend our conclusions to different scenarios, such as video streaming, which imposes additional realtime constraints on the protocol.

  Utilization (d) Piece size of 512 kB

Figure 1 :

 1 Figure1: CDFs of peer download completion times and scatterplots of average upload utilization for five-second time intervals when distributing a 5 MB content (averages over 5 runs). Small pieces shorten download time and enable higher utilization.

Figure 2 :

 2 Figure 2: Download completion times for a 5 MB content (medians over 5 runs and standard deviation error bars). Smaller pieces clearly improve performance.

Figure 3 :

 3 Figure3: Number of pieces uploaded by the seed when distributing a 5 MB content, for two representative runs. The Unique line represents the pieces that had not been previously uploaded, while the Total line represents the total number of pieces uploaded so far. The vertical line denotes the time the seed finished uploading the first copy of the content to the system. The duplicate piece overhead is significantly lower for small pieces.

  Figure4shows the download completion times of the 40 leechers downloading a 100 MB file for different piece sizes. We observe that small pieces are no longer optimal. In this particular case, sizes around 256 kB seem to perform the best. Experiments with other content sizes (20 and 50 MB) show that the optimal piece size increases with content size. For instance, for experiments with a 50 MB content, the optimal piece size is 64 kB. Note that the unofficial guideline for choosing the piece size, mentioned in Section 2, would yield sizes of 32 and 16 kB for a 100 MB and 50 MB content respectively, a bit off from the optimal values.In an effort to better understand this trade-off regarding the choice of piece size, we evaluate the metainfo file and communication overhead. The former is shown in Figure5. As expected, small pieces produce proportionately larger metainfo files (note that the x axis is logarithmic). 16 kB pieces, for instance, produce a metainfo file larger than 120 kB, as compared to a less than 10 kB file for 256 kB pieces. For large content in particular, this might have significant negative implications for the Web server used to distribute such files to clients.Bitfield messages become proportionately larger too. For instance, for the 100 MB content, these messages are 805 and 55 bytes for 16 and 256 kB pieces respectively. Figure6additionally shows the

Figure 4 :

 4 Figure 4: Download completion times for a 100 MB content (medians over 5 runs and standard deviation error bars). Small pieces are no longer optimal.

Figure 5 :

 5 Figure 5: Metainfo file sizes for distributing a 100 MB content. Smaller pieces produce proportionately larger files.

Figure 6 :

 6 Figure 6: Communication overhead due to bitfield and have messages when distributing a 100 MB content. Small pieces incur considerably larger overhead.

Acknowledgments We are grateful to Michael Sirivianos, Himabindu Pucha, and the anonymous reviewers for their valuable feedback.


Zakaria Chekoubi
email: zakaria.chekoubi@univ-lorraine.fr

Nathalie Sauer
email: nathalie.sauer@univ-lorraine.fr

Wajdi Trabelsi
email: wajdi.trabelsi@icn-artem.com

Lgipm

The Integrated Production-Inventory-Routing Problem of EOL products with simultaneous delivery and pickup

Keywords: Integrated Production-Inventory-Routing Problem, Dynamic lot-sizing, Remanufacturing, VRP with Simultaneous Pickup and Delivery, Reverse Logistics, Mixed Integer Linear Programming (MILP)

Production, inventory and distribution with returns management are three key decisions in closed-loop supply chain planning. In order to achieve an effective operational performance level, it is important for these three decisions to be integrated, especially in closed-loop supply chains (CLSC) with remanufacturing operation. In this paper, we address the integrated optimization of Production, Inventory control and Routing decisions with remanufacturing of End-Of-Life (EOL) products (IPIRP-R) related to supplying several customers from a central plant. In particular, we consider a CLSC in which two production lines and a fleet of homogenous capacited vehicle, who make multiple trips over the planning horizon, are available to manufacture new products, remanufacture EOL products, deliver final products and pickup EOL ones, respectively. The aim of solving the IPIRP-R model is to minimize jointly the total production, setup, inventory and routing cost over a finite planning horizon. The originality of our study lies in the fact of jointly treating the single-item capacitated lot-sizing with remanufacturing and the vehicle routing problem with simultaneous pick-up and delivery in a single framework. Computational experiment is conducted on a set of randomly generated instances. An illustrative example to illustrate the relevance of our model is given.

I. INTRODUCTION

Managing returns flow within a close-loop supply chain is considered as a business opportunity for many companies. Today, many firms have initiated efforts to incorporate the concept of reverse logistics in their regular production, inventory and distribution decision systems for several reasons such as the increasing concern for environment, restrictions of applicable government regulations and laws on recycled products and waste disposal, the growing energy consumptions, and the stiff competition between the firms. The integration of these three decisions on the context of reverse supply chains offers tremendous cost savaging opportunities to firms. Moreover, integrating productioninventory-distribution decisions into a single problem is almost indispensable and relevant for some type of goods in particular perishable or time-sensitive goods [START_REF] Chekoubi | The integrated production-inventory-routing problem in the context of reverse logistics: The case of collecting and remanufacturing of EOL products[END_REF]. In this direction, the Integrated Production-Inventory-Routing Problem (IPIRP), which aims to jointly minimize production, inventory, setup and routing costs, has drawn the attention of many researchers since the seminal work of [START_REF] Chandra | Coordination of production and distribution planning[END_REF] who studied the economic value of integrating and coordinating production and routing decisions. The authors found that integrating these decisions may lead to savings ranging from 3 % to 20 % in comparison with the traditional sequential approach, in which routing decisions are made after the production plan has been determined [START_REF] Miranda | A decomposition heuristic for a rich production routing problem[END_REF]. Afterwards, several studies suggested both mathematical formulations and procedures to solve various variants of the problem. Most of the research on the IPIRP has focused on a scenario with a single production facility that produces one product and owns a limited fleet of homogeneous vehicles [START_REF] Miranda | A decomposition heuristic for a rich production routing problem[END_REF]. Solution methods for this problem include mathematical programming-based heuristics [START_REF] Absi | A two-phase iterative heuristic approach for the production routing problem[END_REF][START_REF] Chitsaz | A Unified Decomposition Matheuristic for Assembly, Production, and Inventory Routing[END_REF], B&C algorithms [START_REF] Adulyasak | Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems[END_REF][START_REF] Ruokokoski | Efficient formulations and a branch-and-cut algorithm for a production-routing problem[END_REF], Benders-based B&C [START_REF] Adulyasak | Benders decomposition for production routing under demand uncertainty[END_REF], B&P-based heuristics [START_REF] Bard | Heuristics for a multiperiod inventory routing problem with production decisions[END_REF][START_REF] Bard | The integrated production-inventory-distribution-routing problem[END_REF], Greedy Randomized Adaptive Search Procedure (GRASP) [START_REF] Boudia | A reactive GRASP and path relinking for a combined production-distribution problem[END_REF], Adaptive Large Neighborhood Search (ALNS) [START_REF] Adulyasak | Optimization-based adaptive large neighborhood search for the production routing problem[END_REF] and Genetic Algorithm with Population Management (GAPM) [START_REF] Boudia | A memetic algorithm with dynamic population management for an integrated productiondistribution problem[END_REF].

Besides integrating operations forward, closed-loop supply chain optimization showed a further reduction in environmental impact [START_REF] Savaskan | Closed-loop supply chain models with product remanufacturing[END_REF]. Return flow processes in a closedloop supply chain usually consists of (1) product collection from consumers; (2) reverse logistics to take collected products back; (3) screening, assorting and disposal to specify the most economically attractive reuse alternatives; (4) remanufacturing; and (5) remarketing to produce and utilize new markets [START_REF] Iassinovskaia | The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains[END_REF]. The remanufacturing operation consists on transforming end of-life returned products into usable products through refurbishment, repair or upgrading [START_REF] Chekoubi | The integrated production-inventory-routing problem in the context of reverse logistics: The case of collecting and remanufacturing of EOL products[END_REF]. Moreover, since the importance of considering remanufacturing in closed-loop supply chain was stressed by [START_REF] Savaskan | Closed-loop supply chain models with product remanufacturing[END_REF], the research on remanufacturing had mainly focused on inventory system with remanufacturing [START_REF] Decroix | Optimal policy for a multiechelon inventory system with remanufacturing[END_REF][START_REF] Tao | Approximation balancing policies for inventory systems with remanufacturing[END_REF], economic aspect of remanufacturing [START_REF] Geyer | The economics of remanufacturing under limited component durability and finite product life cycles[END_REF][START_REF] Chen | The co-opetitive strategy of a closed-loop supply chain with remanufacturing[END_REF], and marketing issues [START_REF] Atasu | Remanufacturing as a marketing strategy[END_REF][START_REF] Agrawal | Remanufacturing, third-party competition, and consumers' perceived value of new products[END_REF]. However, little has been revealed when remanufacturing is not only involved with inventory decisions but also with routing decisions [START_REF] Qiu | Production routing problems with reverse logistics and remanufacturing[END_REF]. Furthermore, addressing the IPIRP in the context of closed-loop supply chain is important because in addition to economic benefits, environmental benefits due to extension of the product useful life, reduced energy and material consumption, pollution prevention, and other sustainability benefits can be expected [START_REF] Qiu | Production routing problems with reverse logistics and remanufacturing[END_REF].

Our goal through this paper is to bridge these gaps by extending our previous study [START_REF] Chekoubi | The integrated production-inventory-routing problem in the context of reverse logistics: The case of collecting and remanufacturing of EOL products[END_REF] insofar we propose a novel MILP model for the IPIRP with remanufacturing (IPIRP-R) of EOL products considering a typical direct-inverse distribution with simultaneous pickups and deliveries performed by a fleet of homogeneous capacited vehicle.

The recent work of [START_REF] Qiu | Production routing problems with reverse logistics and remanufacturing[END_REF] is considered as the first study that investigates the same problem as ours by introducing a mixed integer programming model for the integrated production routing problem with reverse logistics and remanufacturing. They proposed a novel branch-and-cut guided search algorithm as solution method. The difference of our study compared to theirs, lies in the formulation of the proposed model and the fact that they consider a typical IPIRP integrating the Vendor Manager Inventory (VMI) policy, the thing we are not considering.

The contributions of this paper can be summarized as follows. First, we introduce a variant of the IPIRP with a direct-reverse distribution and remanufacturing. The directreverse distribution with simultaneous pickups and deliveries is now mixed with capacitated vehicle routing problems, which has never been investigated in the IPIRP literature. Second, we formulate a new MILP formulation for the IPIRP-R. Finally, we conduct extensive computational experiments on a set of randomly generated instances to evaluate the performance of the proposed MILP model and provide remarks and conclusions for future works.

The remainder of the paper is organized as follows: Section 2 briefly describes the considered problem as well as the assumptions considered during the development of our model. The MILP formulation integrating production with remanufacturing, inventory and routing decisions is presented in Section 3. Section 4 is devoted to computational experiments and the obtained results. Finally, concluding remarks and future research perspectives are highlighted in Section 5. We assume that the central plant does not require any delivery or pickup ( = = 0, ∀ ∈ ). At the central plant are located two production systems, respectively for manufacturing and remanufacturing of serviceables products and returned EOL products. Each production line has a limited production capacity and has its own set-up cost. Both production line systems are based on the economic lot-sizing production strategy of a single product and have to fulfill all demand requirements of each period over the finite planning horizon either by manufacturing new products (serviceables) or by remanufacturing returned EOL products or both. It means that the remanufactured products will be of the same quality as new products and backlogging is not allowed. In addition, a unitary production cost occurs for manufacturing (resp., remanufacturing) a new product (resp., returned product) in each period. Also, manufacturing and remanufacturing operations lead times are supposed to be zero. Regarding customers, we consider that their requests for delivery and pickups are deterministic and known for all planning horizon periods. Also, we assume that the initial stocks of serviceables and returns are both null (zero initial stocks conditions) and there is a positive demand in the first period. Moreover, new manufactured (resp., remanufactured) products are stored in the serviceables (resp., returns inventory) without exceeding its capacity and each inventory has its own holding cost. A fleet of homogeneous vehicles based at the central plant is available for distribution of the product to customers. We assume that each customer with no requests should not be visited ( > 0 ˄ ≤ ). Each vehicle departing from and returning back to the central plant, can visit several customers only once in a route without exceeding its capacity . Furthermore, a vehicle can only perform a single tour in each period and the split deliveries and pickups are not allowed. The studied system can be modelled as shown in FIG. 1.

The IPIRP-R problem consists of determining how much items to manufacture, remanufacture, store and distribute through optimal routes over a finite multi-period planning horizon. The objective is to jointly minimize the setup, manufacturing, remanufacturing, holding and routing costs.

III. MATHEMATICAL FORMULATION

This section presents the main notation and a mathematical formulation that integrates production, inventory and routing decisions with remanufacturing in a single framework. Before describing the MILP model, let us introduce the following additional notation:

C. Decision variables

: Quantity of products manufactured at period t;

: Binary variable which is equal to 1 if > 0, and 0 otherwise : Inventory level of serviceables at the end of period : Quantity of products remanufactured at period t : Binary variable which is equal to 1 if > 0, and 0 otherwise : Inventory level of returns at the end of period : Delivered demand up to node and carried in arc ( , ) at period : Picked-up demand up to node and carried in arc ( , ) at period : Binary variable which is equal to 1 if vehicle travels from location to location at period , and 0 otherwise.

Using the above parameters and variables, the full integrated model can be formulated as follows (Model IPIRP-R):

min = ( | | . + . + ℎ . + . + . + ℎ . ) + . ∈ + . | | ∈ ∈ ∈ (1)
s.t. = + + -∑ ∈ ∀ ∈ = -+ ∑ ∈ ∀ ∈ (3)
= 0; = (4)

0 ≤ ≤ ∀ ∈ (5) 0 ≤ ≤ ∀ ∈ (6) ≤ min ∈ ; . ∀ ∈ (7) ≤ min{ ∈ ; . ; } ∀ ∈ (8) ∈ ≤ 1 ∀ ∈ ; ∀ ∈ (9) ∈ ≤ 1 ∀ ∈ ; ∀ ∈ (10)
∈ ∈ = 1 ∀ ∈ ; ∀ ∈ (11) ∈ - ∈ = 0 ∀ ∈ ; ∀ ∈ ; ∀ ∈ (12)
∈ - ∈ = ∀ ∈ ; ∀ ∈ (13)
∈ - ∈ = ∀ ∈ ; ∀ ∈ (14)
+ ≤ . ∈ ∀ , : ≠ ∈ ; ∀ ∈ (15) = 0 ∀ ∈ ; ∀ ∈ (16) = 0 ∀ ∈ ; ∀ ∈ (17) ∈ {0, 1} ∀ ( , : ≠ ) ∈ ; ∀ ∈ ; ∀ ∈ (18) ∈ {0, 1} ; ∈ {0, 1} ∀ ∈ (19) , , , , , , ∈ ℤ
∀ ( , : ≠ ) ∈ ; ∀ ∈ (20)
Objective function (1) minimizes the total manufacturing, remanufacturing, inventory and routing cost. Equations ( 2)-( 4) are the inventory balance equations and initial inventories conditions for serviceable and return products respectively. Inequalities (5)-( 6) limit the maximum capacity of serviceable and returned products not to be exceeded at the end of each period. Inequalities ( 7)-( 8) represents the manufacturing (resp., remanufacturing) capacity constraints and guarantee that there is manufacturing (resp., remanufacturing) of new products (resp. return-products) in a period t only if the manufacturing production line (resp., remanufacturing production line) is set up at the beginning of the period t. Equations ( 9)-( 12) are the classical vehicle routing constraints. Constraints ( 13)-( 14) guarantee that the delivery and pickup demands at customer ∈ are satisfied. Constraint [START_REF] Iassinovskaia | The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains[END_REF] guarantees that the total load on the vehicle does not exceed its capacity. Constraints ( 16)- [START_REF] Tao | Approximation balancing policies for inventory systems with remanufacturing[END_REF] ensures that the vehicle leaves the central plant without any pickup demand load and reaches the depot after delivering all the demands. Finally, constraints ( 18)-( 20) provides the domain of the variables.

D. Illustrative example

In order to illustrate some key features of our model, we provide a solution of an illustrative example with | | = 5, | | = 3 and | | = 5 . FIG. 2 shows, for each period, serviceables inventory level, returns inventory level, manufactured lot-sizes, remanufactured lot-sizes, delivery quantities to be distributed and pickup quantities to be collected. FIG. 3 shows the total cost and its distribution according to the integrated operations considered. Finally, FIG. 4 shows the routing decisions for each period.

For example, at the beginning of period one the manufacturing lot-sizes and the quantities to be delivered are of the same values, namely 201 units, which means that we manufacture the same amount of requested deliveries to meet all delivery demands occurring in this period. Therefore, the inventory level of serviceable products at the end of the first period is 0 + 201 -201 = 0 (assuming that initial inventory level of serviceables product to be 0 ( = 0 )), which corresponds to the initial inventory of serviceable products in the second period. Regarding the level of return-products inventory, the same analysis applies. Thereby, the inventory level of inventory products at the end of the first period is 0 + 54 -0 = 54 (assuming that initial inventory level of return inventory to be 0 ( = 0)), which corresponds to the initial inventory of return inventory in the second period. We can observe that no operation of remanufacturing was carried out, which is quite normal because the EOL product are collected and returned after the vehicles goes back to the central plant at the end of period one.

By performing the same analysis and calculations, one can obtain the manufacturing lot-sizes, remanufacturing lot-sizes, inventory levels for both serviceables and return inventories also the amounts of deliveries and pickups to be distributed and to be collected for the remaining of periods. Note that no manufacturing operation is performed, instead a remanufacturing one occurs in period three, and therefore the final inventory level of serviceables products is null. From figure 3 it is easy to notice that the costs related to production and transport operations are significant and represent respectively 42.67% and 41.61% of the total integrated cost against the costs related to holding and setups operations who come in third and fourth place respectively and represent 13.35% and 2.32% of the total integrated cost, respectively. From figure 4 we can notice that only 3 vehicles were used in period one and two vehicles in period 2 and 3 to perform routes among the 5 vehicles allowed on the entire planning horizon.

IV. COMPUTATIONAL EXPERIMENTS

A. Instances Generation

In this section we provide computational experiments conducted on a set of a randomly generated instances. The MILP model was coded in Eclipse Java Oxygen and solved using IBM ILOG CPLEX 12.7 solver on a PC with a CPU Core i5 2.40 GHz processor and 4 GB RAM. An acceptable computational time of 1 hour is set for each instance. Furthermore, all CPLEX parameters were set up to their default values for all numerical tests. The conducted tests were performed using several randomly generated instances based on some adapted data sets from the literature of the single lot-sizing with remanufacturing problem and those from the integrated production-routing problem in particular research works of [START_REF] Sifaleras | Variable neighborhood search for the economic lot sizing problem with product returns and recovery[END_REF]24] Travel cost from node i to node j = ( -) + ( -) + 0.5

Maximum number of vehicles over the planning horizon

| | = max (∑ ∑ ∈ ∈ ; ∑ ∑ ∈ ∈ )

B. Numerical Results

In order to evaluate the efficiency and the limits of our integrated model (IPIRP-R), this section provides the computational results on the random instances described in the previous section.

The obtained results using CPLEX solver are shown in TABLE 2. Columns 2-4 show the number of customers, number of periods and the maximum number of vehicles to be used, respectively. Columns 5 shows the total cost average calculated based on instances solved to optimality. Finally, columns 6 shows the average of CPU time, in seconds. The symbol " †" means that CPLEX Solver failed to return a feasible solution for the corresponding instances within the 1hour time limit. In general, we can easily observe that CPLEX solver can only solve to optimality instances with | | = 5 customers for a planning horizon with | | = {3, 6, 9} time periods after 1-hour of computing time. Moreover, in some cases, the solver may have found an optimal solution but it is not able to prove it because of the poor quality of the lower bounds and needs more time to prove it. This is the case, for example, for the instances with | | = {10, 15} costumers for most period times, whose feasible solutions was found in one hour. Another disadvantage of solving the integrated model is that CPLEX solver is unable to provide feasible solutions for most of the instances with | | ≥ 20 for all time periods of the planning horizon. This gives us a strong proof about the complexity of the integrated model that can be explained by the fact that each of the considered problems is NP-hard [START_REF] Chekoubi | The integrated production-inventory-routing problem in the context of reverse logistics: The case of collecting and remanufacturing of EOL products[END_REF]. Therefore, the use of approximate resolution approaches seems logical and essential to use, especially the heuristic and metaheuristics methods to solve the integrated model in order to achieve good quality solutions within reasonable times for all medium and large instances. Based on the results obtained, an interesting perspective for future research is to study the complexity of the IPIRP-R problem and develop an effective heuristic procedure to solve it by combining mathematical programming and heuristic methods in order to find better solutions for medium and large-instances. Another interesting line of research is to extend the MILP formulation in order to include the case of stochastic requests for deliveries and pickups as well as multiple products, heterogeneous fleet of vehicles and time windows. Considering these three new features would result in a more complex scenario, which is often found in industrial real-life applications.

  II. PROBLEM DESCRIPTION In this section, we provide a formal description of the Integrated Production, Inventory, Distribution problem with remanufacturing addressed in this paper, denoted IPIRP-R and present the assumptions we considered in the development of the MILP formulation model. let = ( , ) defines a complete directed graph network, where = {0, 1, 2, … , | |} is the set of nodes and = {( , ): , ∈ , ≠ } is the set of arcs. The central plant is denoted by node {0} and = \{0} denotes the set of customers. Each arc ( , ) ∈ has a non-negative symmetric travelling cost denoted that represents the cost of reaching node from node and satisfying triangular inequality (i.e., + ≥ ). Each customer ∈ requires a dynamic demand for delivery and pickup in each period ∈ , where = {1, 2, … , | |} denoted respectively and .

  FIG. 1 ILLUSTRATION OF THE STUDIED CLOSED-LOOP SUPPLY CHAIN SYSTEM

FIG. 3

 3 FIG. 3 INTEGRATED PRODUCTION-INVENTORY-ROUTING PLAN OF THE ILLUSTRATE EXAMPLE

  . The generated data instances, consist of problems with | | = {3, 6 , 9} and | | = {5, 10, 15, 20}. We generate 10 instances for each combination of customers number | | and number of time periods | | according to the patterns shown in TABLE1, resulting in a total of 12 problems with 120 instances.

  V. CONCLUDING REMARKS AND FUTURE WORKS In this paper, we proposed a new MILP formulation to represent and solve the IPIRP with remanufacturing of EOL products. The new model considered a new feature namely a fleet of homogenous capacited vehicles. We used a commercial solver to solve a set of 120 randomly generated instances. Numerical results that the solver was able to solve optimally the instances with | | = 5 and | | = {3,6,9}, and near-optimal solutions were found for most of the instances with | | = 10 customers and | | = {3,6,9} periods.

TABLE 1

 1 PARAMETERS USED TO GENERATE RANDOM INSTANCES

	Unitary production cost for manufacturing new product				= 10
	Fixed manufacturing setup cost			= 500
	Unit inventory holding cost for manufacturing serviceable product		ℎ = 1
	Manufacturing production line capacity at period t	= 2 •	∑	∈	∑ ∈
	Maximum inventory level of serviceable products at period t	= 2 •	∑	∈	∑ ∈	• | |
	Unitary production cost for returned product remanufacturing a				= 2
	Fixed remanufacturing setup cost			= 500
	Unit inventory holding cost for return-product remanufacturing		ℎ = 0.8

TABLE 2 SUMMARY

 2

			OF COMPUTATIONAL RESULTS FROM CPLEX SOLVER
	((*) SIGNIFICATES THAT THE AVERAGE VALUE WAS CALCULATED BASED
		ONLY ON THE FEASIBLE SOLVED INSTANCES)
	Prob#	| |	| |	| |	Av. Total cost	Av. CPU (s)
	1		3	6	11502,44	5,3163
	2	5	6	1 2	22522,56	201,35
	3		9	18	33654,7	959,1457
	4		3	13	21042,5 (*)	>3600
	5	10	6	24	56744 (*)	>3600
	6		9	37	60957,11 (*)	>3600
	7		3	18	29986,4 (*)	>3600
	8	15	6	36	56793,5 (*)	>3600
	9		9	54	†	>3600
	10		3	25	40007,22 (*)	>3600
	11	20	6	50	†	>3600
	12		9	72	†	>3600


Murad Abuaisha
email: murad.abuaisha@ucalgary.ca

David Eaton

Jeffrey Priest

Ron Wong

Simulating HF using FDEM: Effects of pre-existing joints, induced microseismicity and fluid diffusion

Introduction

Hydraulic fracturing (HF) is routinely used in the development of unconventional oil and gas reservoirs. Optimization of this technique requires a detailed understanding of how fractures propagate away from the wellbore especially when existing natural fractures are present. Here we present a numerical study undertaken, using a Finite-Discrete Element Modelling (FDEM) approach to investigate HF growth and induced microseismicity. The first part of the study considers an application of the FDEM called the Y-Geo code that assumes inviscid fluid and accounts for fluid flow only in the fractures, which is convenient for fast fracturing. The Y-Geo code is used here to study the induced microseismicity due to shear slip of critically stressed pre-existing joints. The Y-Geo code is then upgraded to account for fluid leak-off from fractures as well as fluid diffusion in the porous media (the Irazu code). Fluid leak-off and fluid diffusion require long simulation times depending on the permeability of the medium, and are important for simulating Diagnostic Fracture Injection Tests (DFITs). The Irazu code is utilized here to investigate the general response of fluid diffusion and fluid pressure due to changing fluid viscosity as result of changing temperature.

Background

In the FDEM framework, the domain is discretized into elastic triangular elements. The initial elastic deformation of the medium during fluid pressure injection in a borehole is captured by FEM. However, once the medium is fractured, the DEM is used to capture the positions and interaction of fractured blocks. Figure 1: Penalty coefficients and fracture energies for different modes of fracturing adopted in FDEM [START_REF] Lisjak | A preliminary evaluation of an enhanced FDEM code as a tool to simulate hydraulic fracturing in jointed rock masses[END_REF].

In FDEM penalty coefficients and fracture energies, related to the cohesive and shear strength of the rock, are used to enable the transition from FEM to DEM behaviour. Figure 1 shows the modelling parameters assigned to different modes of fracturing that occur based on the stress-strain response of the rock. This approach is capable of simulating fracture evolution patterns during HF simulations.

Induced microseismicity due to shear slip (Y-Geo code)

The model adopted to study microseismicity by Y-Geo code is shown in Fig. 3(a). It is a 8m x 8m fractured medium (close to the wellbore), fluid is injected at constant rate 20 l/s. Figure 3b shows the fracture patterns for two cases of different far-field stresses at time 1.36 ms after initiation of injection. The applied stress state gives rise to different patterns of fluid-driven fractures. Once the growing fracture intersects a pre-existing joint, the joint exploits fluid pressure and leads it to the tips where fracture initiation is accomplished with minimum work. As joints represent planes of weakness, they fracture with less energy and consequently increase the extent to which fluid-driven fractures can reach for the same injected energy. Figure 4 shows the microseismic events locations due to fracturing. It is clear that events are following the patterns of the fluid-driven fractures. However, it is also clear that there are some scattered microseismic incidents that are incited by the deformation of the medium (joint shear slippage) (Fig. 4(a)). Figure 5 shows the magnitudes of the events (as shown in Fig. 4) which range between -4 and -5 as observed in the induced HF microseismicity. It is worthwhile to mention that joint shear slippage can also be caused by fluid diffusion altering critically stressed joints. 7 shows the injected net fluid pressure profile over a time span of ∼45 seconds. Figure 8 shows the contours of the diffused fluid pressure and fracture patterns for the two schemes of injection and for the two possibilities of fluid viscosity. The contours of net fluid pressure and fracture patterns are plotted for different times corresponding to the letters (a to h) in Fig. 7. The letters (a to d) are for the case of viscosity µ = 1 × 10 -3 Pa.s, meanwhile the letters (e to h) are for µ = 0.5 × 10 -3 Pa.s. The letters are picked up such that: 1) a and e correspond to a state in the fracture growing regime (after the fracturing threshold); 2) b and f at the shut down time of 9.1 s; 3) c and j at the state of leak-off (after shut down and before diffusion in the medium); and 4) d and h are during the diffusion process (Fig. 8).

Conclusions

We have been able to observe that pre-existing joints create a pre-fracturing stress state that affects the patterns of the very initiated fractures and increases the threshold of fracturing. It is also noticed that isolated single pre-existing joints lead to asymmetric fracture growth with tendency for fractures to initiate away from the joints, i.e. possible asymmetric seismicity [START_REF] Shapiro | Fluid-induced seismicity: Pressure diffusion and hydraulic fracturing[END_REF]. However, rock joints increase the extent to which fluid-driven fractures can reach. It is also clear that once a joint is intersected by a fluid-driven fracture, it becomes easier for new fractures to initiate at the joint tips. Induced seismicity study showed that microseismic events due to joint shear slippage can be created by rock deformation only. Such events can go as far as the fluid-driven fractures as long as there are critically stressed joints that might be activated (Fig. 4(b)). We also concluded that changing fluid temperature can considerably change the viscosity of the working fluid and consequently the entire response of fluid diffusion in the porous medium.

Figure 2 :

 2 Figure 2: Conceptual graph that illustrates the implementation of fluid diffusion and leak-off in the FDEM approach.

Figure 2

 2 Figure2illustrates the concept of implementing fluid diffusion and leak-off in the FDEM approach (the Irazu code). The mechanical solver of the Y-Geo code (Fig.1) is used. Besides, fluid diffusion and fracture leak-off are implemented by considering the existence of flow channels that coincide with the edges of the triangular elements in the initial mesh. The nodes of the triangular elements represent virtual reservoirs where fluid pressure and fluid mass are sequentially calculated. According to the fluid compressibility law, fluid injected at node N will give rise to increased fluid pressure , fluid will then flow to next nodes (virtual reservoirs) through the flow channels due to pressure gradients.

Figure 3 :

 3 Figure 3: a) The model of the simulations used in the Y-Geo code. b) Fracture patterns for the cases of isotropic and anisotropic stress states in a heavily fractured rock formation at time of 1.36 ms since injection. The trajectories are plotted in the field of velocity magnitude.

  At time 1.40 ms Figure 4: Microseismic event locations due to fracturing with an isotropic far-field stress state. Microseismic events are following fracture topology except for some scattered locations created by fracturing elastic waves/formation deformation.

Figure 6 :

 6 Figure 6: (a) The geometry and boundary conditions of domain chosen for the HF simulations (Irazu code).

  Figure

Figure 8 :

 8 Figure 8: Fluid driven fracture patterns and diffused fluid pressure contours for the two schemes of injection and for tow different values of fluid viscosity, i.e. µ = 1 × 10 -3 Pa.s corresponding to T = 20 • C and µ = 0.5 × 10 -3 Pa.s corresponding to T = 55 • C. These contours and fracture patterns are plotted for several injection times which correspond to the letters (a to h) in Fig. 7.


Julian Leonhard

Marie-Minerve Louërat

Hassan Aboushady

Ozgur Sinanoglu

Haralampos-G Stratigopoulos

Mixed-Signal IP Protection Against Piracy Based on Logic Locking

I. INTRODUCTION

During its lifetime an integrated circuit (IC) may be subjected to various types of attacks. Threats can be categorized into Hardware Trojans, reverse engineering, counterfeiting, and side-channel attacks [START_REF] Rostami | A primer on hardware security: Models, methods, and metrics[END_REF]. Hardware security aims at understanding security breaches in ICs and developing mechanisms for detecting attacks or preventing them by implementing countermeasures for on-chip resilience. Hardware security has been studied extensively for digital ICs recently, but for analog, mixed-signal, and RF ICs the solution space is still largely unexplored [START_REF]Trusted analog/mixed-signal/RF ICs: A survey and a perspective[END_REF].

In this work, we focus on the problem of IC/IP piracy, which includes reverse engineering and counterfeiting. In particular, we develop a countermeasure for mixed-signal IC/IP piracy that is based on design locking. Locking aims at modifying the design, in order to introduce k key bits. There is only one valid combination of key bits, i.e. the secret key, that can result in correct functionality for any input. Otherwise, if an invalid key is applied, then the functionality will be corrupted for some or all inputs.

There are various techniques for locking digital ICs, known as logic locking techniques. The earliest logic locking techniques aimed at inserting key-gates into the design [START_REF] Roy | Ending piracy of integrated circuits[END_REF], i.e. XOR and XNOR gates, controlled by the key bits. Researchers are working in parallel trying to show the vulnerabilities of existing logic locking techniques, proposing attacks that can break them: (i) The brute-force attack sequentially applies keys until the valid one is found; (ii) The SAT attack, the most lethal attack based on a Boolean satisfiability solver, can recover the secret key with very reasonable effort [START_REF] Subramanyan | Evaluating the security of logic encryption algorithms[END_REF]; (ii) Removal attacks aim at identifying and removing the added protection logic; (iv) Approximate attacks aim at extracting a key that establishes an incorrect yet approximate functionality. The most recent state-of-the-art logic locking technique is Stripped-Functionality Logic Locking (SFLL) [START_REF] Yasin | Provably-secure logic locking: From theory to practice[END_REF] and provides quantifiable resilience against these attacks.

Locking analog ICs is very challenging as the key bits need to be introduced in a way that nominal performance is not degraded. Techniques for locking of analog ICs are proposed in [START_REF] Hoe | Towards secure analog designs: A secure sense amplifier using memristors[END_REF]- [START_REF] Wang | Thwarting analog IC piracy via combinational locking[END_REF], [START_REF] Jayasankaran | Towards provably-secure analog and mixed-signal locking against overproduction[END_REF], [START_REF] Volanis | Analog performance locking through neural networkbased biasing[END_REF] and are illustrated in Fig. 1. Specifically, in [START_REF] Hoe | Towards secure analog designs: A secure sense amplifier using memristors[END_REF], a locking technique for sense amplifiers is proposed based on locking the body biasing of the transistor input pair. The locking mechanism is based on an architecture that comprises memristor crossbars. In [START_REF] Rao | Protecting analog circuits with parameter biasing obfuscation[END_REF], it is proposed to replace transistors within the biasing circuit with parallel-connected transistors whose gates are controlled by key-bits. The keybits enable transistors whose aggregate width equals that of the original transistor. In [START_REF] Wang | Thwarting analog IC piracy via combinational locking[END_REF], it is shown how to redesign the [START_REF] Rao | Protecting analog circuits with parameter biasing obfuscation[END_REF]; (c) locking of current mirrors [START_REF] Wang | Thwarting analog IC piracy via combinational locking[END_REF]; (d) locking mixed-signal circuits via logic locking of their digital section [START_REF] Leonhard | Mixlock: Securing mixed-signal circuits via logic locking[END_REF]; (e) logic locking of the digital optimizer in the calibration feedback loop [START_REF] Jayasankaran | Towards provably-secure analog and mixed-signal locking against overproduction[END_REF]; (f) locking through neural network-based biasing [START_REF] Volanis | Analog performance locking through neural networkbased biasing[END_REF].

current mirrors providing the biasing so as to insert key-bits. In [START_REF] Jayasankaran | Towards provably-secure analog and mixed-signal locking against overproduction[END_REF], it is proposed to lock the calibration feedback loop via logic locking of the digital optimizer that is part of the loop, such that it generates the wrong tuning settings unless the valid key is applied. In [START_REF] Volanis | Analog performance locking through neural networkbased biasing[END_REF], it is proposed to add on-chip a neural network that is trained to map the secret analog key, which is in the form of analog DC voltages presented as inputs to the neural network, to the correct biases.

The secret key management scheme is common for all locking techniques and includes storing the secret key on-chip in a tamper-proof memory or generating it on-chip; in the latter case, a Physical Unclonable Function (PUF) can be utilized to even produce chip-unique keys.

In this work, we propose a technique called MixLock that is based on locking a mixed-signal circuit via logic locking of its digital section [START_REF] Leonhard | Mixlock: Securing mixed-signal circuits via logic locking[END_REF].

II. MIXLOCK

MixLock aims at securing mixed-signal IPs against piracy through a logic locking mechanism applied to the circuit's digital section, as illustrated in Fig. 1(d). Only when the valid key is provided the mixed-signal circuit performs its intended function. Otherwise, for invalid keys the mixed-signal performances are pushed outside of their specification, i.e., they are locked. MixLock presents several appealing properties. It is nonintrusive since it does not alter the analog section, which is key for its wide adoption by designers. Modifications in the digital section do not affect mixed-signal performance either. It incurs low area and power overheads since area and power are dominated by the analog section which is left intact. It is fully-automated since logic locking adds only one extra synthesis step. Finally, this concept is applicable to a wide range of mixed-signal circuits such as PLLs, RF transceivers, data converters, etc.

Breaking Mixlock will require either recovering the secret key via a logic locking attack or trying to unlock directly mixed-signal performances by applying an iterative multiobjective optimization algorithm. The latter is unlikely to succeed since mixed-signal performances do not show a smooth monotonic relationship with the key bits. Regarding the former attack, Mixlock is independent of the underlying logic locking technique, but to achieve strong digital security Mixlock uses the state-of-the-art SFLL logic locking mechanism [START_REF] Yasin | Provably-secure logic locking: From theory to practice[END_REF].

III. RESULTS AND DEMONSTRATOR

To demonstrate MixLock, we used as case study a bandpass (BP) Σ∆ ADC whose block-level schematic is shown in Fig. 2. A Σ∆ ADC is decomposed into a Σ∆ modulator, which is the analog section, and a decimation filter, which is the digital section. In this case, Mixlock naturally locks the decimation filter. SFLL was used to guarantee strong digital security; in particular, a 64-bit resilience against the SAT attack was obtained. By simulating thousands of randomly chosen invalid keys we confirmed that Mixlock achieves strong analog security; in particular, the main Signal-to-Noise Ratio (SNR) performance was degraded dramatically below its specification. Fig. 3 considers an arbitrarily selected incorrect key and compares the transient and frequency responses of the unlocked and a locked Σ∆ ADC. The locked Σ∆ ADC presents a large amount of glitches in its transient response, which translate to a high noise floor in the frequency response, resulting in corrupted SNR.

In addition, we demonstrated Mixlock in an audio application [START_REF] Leonhard | Mixed-signal hardware security using Mixlock: Demonstration in an audio application[END_REF]. The demonstrator, illustrated in Fig. 4, emulates a microphone for capturing a sound source, signal processing for digitizing the input audio, and a speaker for listening back the sound source. MixLock is used to lock the Σ∆ ADC in the signal processing chain. The effect of locking on audio quality can be measured by the glitches introduced from the locking operation that can be heard as noisy "cracks". This demonstrator helps us in essence to listen to the effect of locking. Audio samples include speech recordings in German and English and professional music recordings of various genres. The interested reader can download and listen to the output audio samples from this link: https://nuage.lip6.fr/s/CYowe89aXBe6rsP. The downloadable archive includes the output audio samples in the case of the unlocked design, where the valid key is applied, and locked designs where a random invalid key is applied.

Fig. 1 .

 1 Fig. 1. Locking techniques for analog ICs: (a) locking biases based on memristor crossbars [6]; (b) obfuscating biasing transistors [7]; (c) locking of current mirrors[START_REF] Wang | Thwarting analog IC piracy via combinational locking[END_REF]; (d) locking mixed-signal circuits via logic locking of their digital section[START_REF] Leonhard | Mixlock: Securing mixed-signal circuits via logic locking[END_REF]; (e) logic locking of the digital optimizer in the calibration feedback loop[START_REF] Jayasankaran | Towards provably-secure analog and mixed-signal locking against overproduction[END_REF]; (f) locking through neural network-based biasing[START_REF] Volanis | Analog performance locking through neural networkbased biasing[END_REF].

Fig. 2 .Fig. 3 .

 23 Fig. 2. The Bandpass Σ∆ ADC used as case study.

Fig. 4 .

 4 Fig. 4. Mixlock demonstration in an audio application.

ACKNOWLEDGMENTS

This work has been carried out in the framework of the ANR STEALTH project with N o ANR-17-CE24-0022-01. J. Leonhard has a fellowship from the doctoral school EDITE de Paris.


Antonios Pavlidis

Marie-Minerve Louërat

Eric Faehn

Anand Kumar

Haralampos-G Stratigopoulos

SymBIST: Symmetry-based Analog/Mixed-Signal BIST

I. INTRODUCTION

The large number of Integrated Circuits (ICs) deployed in modern safety-and mission-critical applications has created an increasing interest to avoid IC malfunctions in the field and reduce the test escapes down to sub-ppm levels. Regarding Analog and Mixed-Signal (A/M-S) ICs, many case studies have shown that the standard specification tests performed on Automated Test Equipment (ATE) offer no guarantee to meet this quality requirement [START_REF] Hashempour | Test time reduction in analogue/mixedsignal devices by defect oriented testing: An industrial example[END_REF]. To this end, performing defect-oriented Built-In Self-Test (BIST) on top of the standard specification tests and proving high defect coverage can address safety concerns. The premise of BIST in this context is that it can detect latent defects and defects that will be triggered in the context of system operation in the field provoked by environmental stress.

In this paper, we present a defect-oriented BIST strategy for A/M-S ICs, called symmetry-based BIST or SymBIST. We demonstrate how SymBIST can be successfully applied to a 65nm 10-bit Successive Approximation Register (SAR) Analog-to-Digital Converter (ADC) IP by ST Microelectronics.

Existing works on ADC BIST focus on functional BIST [2]- [START_REF] Laraba | Exploiting pipeline ADC properties for a reduced-code linearity test technique[END_REF]. The main reason for the lack of defect-oriented ADC BIST solutions is the long ADC simulation time, typically in the order of hours, which prohibits a defect simulation campaign. Thanks to the fast test time accomplished by SymBIST, and by using the recent mixed-signal defect simulator Tessent R DefectSim by Mentor R , A Siemens Business [START_REF] Sunter | Using mixed-signal defect simulation to close the loop between design and test[END_REF], we were able to run very fast in a automated workflow defect simulation for hundreds of defects and compute defect coverage for the entire IP.

II. SymBIST PRINCIPLE

The proposed SymBIST paradigm exploits existing symmetries into an A/M-S design and builds invariant properties that should hold true only in defect-free operation.

The underlying observation is that symmetries are inherent to virtually all A/M-S designs. Inherent symmetries exist thanks to fully-differential (FD) signal processing, complementary signal processing, and replication of identical blocks. For example, for node pairs carrying FD or complementary signals we can build an invariance in the form of V 1 + V 2 = α, where V 1 and V 2 are the nodes' voltages and α is a constant, i.e., in the case of FD signals α = 2V cm, where V cm is the common mode voltage [START_REF] Stratigopoulos | An adaptive checker for the fully differential analog code[END_REF]. Symmetries can also be created artificially with reconfiguration using switches, duplication of blocks, or pseudo-duplication of blocks.

These invariances can be checked with a window comparator circuit implementing a comparison window [-δ, δ], δ > 0, to account for process, voltage, and temperature variations. If the invariant signal slides outside the window, then this points to defect detection.

III. SymBIST APPLIED TO SAR ADC IP

The top-level of the SAR ADC IP architecture is illustrated in Fig. 1. The circuit accepts a FD analog input ∆IN=IN + -IN -. The SAR algorithm is implemented into the main SAR CELL block whose block-level architecture is shown in Fig. 2.

Looking into the architecture of the SAR ADC IP, we identified 6 invariances that hold true for any FD input ∆IN and at every conversion cycle and cover the entire A/M-S part of the SAR ADC IP. The same test stimulus is used for checking all of these invariances. In particular, the FD input ∆IN stays constant at a DC value which can be set arbitrarily and a 5bit digital counter is used that generates all possible 2 5 bit combinations at the inputs B< 0 : 4 > and B< 5 : 9 > of the two sub-DACs composing the 10-bit DAC. The rationale for this dynamic part of the test stimulus is that it excites all A/M-S sub-blocks. If the 6 invariances are checked sequentially, the test is completed very fast in 6 * 2 5 • (1/f clk ) = 1.23µsec, where f clk = 156MHz is the sampling clock frequency. This time equals about 16x the time to convert one analog input sample. A simple window comparator is designed for checking an invariance composed of voltage followers and an operational amplifier. Overall, the BIST infrastructure is totally transparent to the IP incurring no performance penalties and is estimated to incur a very low and justifiable area overhead below 5%. Furthermore, the BIST can be interfaced with a standard digital test access mechanism based on two external pins which is the minimum.

IV. RESULTS

Defects are assigned a relative likelihood of occurrence as explained in [START_REF] Sunter | Using mixed-signal defect simulation to close the loop between design and test[END_REF]. For this reason, we report the Likelihood-Weighted (L-W) defect coverage computed by the Tessent R DefectSim tool [START_REF] Sunter | Using mixed-signal defect simulation to close the loop between design and test[END_REF]. To reduce defect simulation time, we use the stop-on-detection and Likelihood-Weighted Random Sampling (LWRS) options [START_REF] Sunter | Using mixed-signal defect simulation to close the loop between design and test[END_REF]. When the LWRS option is used, the 95% confidence interval of the L-W defect coverage is also reported [START_REF] Sunter | Using mixed-signal defect simulation to close the loop between design and test[END_REF]. We rely on a standard defect model based on shortand open-circuits and 50% variation in passive components.

Fig. 3 shows in blue the invariant signal that corresponds to the sum of the differential inputs DAC+ and DAC-of the comparator. This signal should be around 1.6V in defectfree operation. In this simulation, the stop-on-detection was disabled. The two dashed horizontal lines correspond to the comparison window which has limits at δ = 5σ such that yield loss is negligible. The instantaneous glitches are due to the switching operation, either due to changes in the input digital test stimulus or due to the sampling and conversion operations. A clocked comparator is used to check the invariance with the checks performed when the node voltages are settled, thus no defect detection is flagged when the glitches exceed the range. The yellow, red, and purple curves in Fig. 3 show the same invariant signal in the presence of a defect in three different blocks. As it can be seen from Fig. 3, while the defect in V cm generator is detectable during the entire test duration, the defects within the sub-DAC1 and SC array are detectable during specific conversion periods.

Table I shows for the various individual sub-blocks of the SAR ADC IP and for its complete A/M-S part the total number of defects, the number of defects simulated, the total defect simulation time, and the L-W defect coverage values achieved using SymBIST. For the entire A/M-S part of the IP, the defect coverage is 86.96% ± 3.67%. As a comparison, for two considerably smaller industrial A/M-S IPs, namely a bandgap and a power-on-reset circuit, the reported defect coverage values are 74% and 51%, respectively [START_REF] Sunter | Using mixed-signal defect simulation to close the loop between design and test[END_REF].

The low defect coverage for some sub-blocks can be explained by the non-detection of defects with very high likelihood of occurrence. In fact, the absolute defect coverage is considerably higher.

The defect simulation times are proportional to the number of defects simulated, as well to the detection time stamps since the stop-on-detection option is used. For defects that are not detected the test ends up being exhaustive.

Fig. 1 :

 1 Fig. 1: Top-level architecture of SAR ADC.

Fig. 2 :

 2 Fig. 2: SARCELL block-level architecture.

Fig. 3 :

 3 Fig. 3: Defect detection by checking an invariance signal.

TABLE I :

 I L-W defect coverage results.

ACKNOWLEDGEMENT

The authors would like to acknowledge the financial support in the framework of the ANR EDITSoC project with N o ANR-17-CE24-0014-02. The authors would like also to thank Stephen Sunter from Mentor, A Siemens Business, for the technical advice on the defect simulator.