Jean-Philippe Georges

Nicolas Krommenacker

Thierry Divoux

Eric Rondeau

A design process of switched Ethernet architectures according to real-time application constraints ⋆

Keywords: real-time communications, Ethernet, Genetic Algorithms

Ethernet networks are based on a medium access method which is not deterministic. The use of such networks in factory environments (which are strongly time constraints) can absolutely not guarantee that the applications requirements will be respected. This paper presents a method based on genetic algorithms to minimize end-to-end delays by providing a good distribution of the devices on the network switches. The objective function is defined by using the network calculus which is a deterministic theory and enables to determine bounded delays. In this paper, a case study is described : theoretical results are verified by a real experimentation and compared with results obtained with a network simulator.

Introduction

The industrial communications are currently based on specific networks called fieldbuses such as FIP, Profibus (CENELEC (1996)), CAN. They interconnect Programmable Logical Controllers (PLC), CNC, robots . . . to exchange technical data for monitoring, controlling, and synchronizing industrial processes. Their main characteristic is to ensure that the end-to-end delays of messages remain limited, compared with the time-cycle of the applications. Thus, these networks are deterministic and some protocols satisfy the integrity constraints of the information. In opposition, the Ethernet networks based on the CSMA/CD protocol are more and more used to interconnect industrial devices. Some applications confirm this evolution in different industrial areas : cars (Jaguar), pharmaceutics (Boehringer Ingelheim), avionics [START_REF] Grieu | Preuve de déterminisme d'un réseau embarqué avionique[END_REF]) . . . Moreover, different organizations such as the Industrial Automation Networking Alliance (IAONA), the Industrial Ethernet Association (IEA) promote Ethernet as "the standard in the industrial environment". Finally research projects such as CIDER [START_REF] Alves | CIDER -envisaging a cots communication infrastructure for evolutionnary dependable real-time[END_REF]) study the use of Ethernet as an enabling technology for future dependable real-time systems.

Second level switches

Federative Switch Industrial Devices To interconnect Ethernet switches, different topologies can be used. [START_REF] Rüping | Analysis of switched Ethernet networks with different topologies used in automation systems[END_REF] shows that the hierarchical topology (figure 1) is the most efficient and therefore mainly used in factory networks. Industrial devices are distributed on second level switches which are directly connected to a federative switch. Moreover, this topology will support two supplementary mechanisms : full-duplex communications and micro-segmentation. The reason is that on shared Ethernet networks, collisions could occur, which is a non-deterministic issue. Now with micro-segmentation, each device is isolated in its own segment, so that with full-duplex, collisions are eliminated. In these conditions, the collision problem is shifted to congestion in switches. Thus the objective will be to control and to evaluate the switches congestion.

We propose to design a switched Ethernet architecture which satisfies the time requirements. Our objective is to optimize the network organization at the physical layer level. Switched networks design consists in distributing industrial devices on the different Ethernet switches in order to reduce the load of the backbone and of the switches. Figure 2 shows well that the distribution of the devices on the second level switches mathematically corresponds to the partitioning of the communication graph of these devices as described in section 2. As the graph partitioning is an NP-complete problem the Genetic Algorithms are suitable to solve this network segmentation problem. The Genetic Algorithms have already been used for networks performance optimisation [START_REF] Krommenacker | Genetic algorithms for industrial Ethernet network design[END_REF][START_REF] Krommenacker | Study of algorithms to define the cabing plan of switched Ethernet for real-time applications[END_REF]). The objective is to collect on the same switches the devices which exchange information. Thus, the criterion to minimize is the number of the graph edges cut by the partition. Indeed the end-to-end delay of a message exchanged between two actors belonging to the same partition will be reduced, because the number of crossed switches is minimized. Nevertheless, even if this delay is optimized, it is not guaranteed that it is lower than the application time constraints. That is why the optimization criterion has to explicitly take into account this delay, and more particularly in the worst case. The Network Calculus theory introduced by R. Cruz (see Cruz (1991a), Cruz (1991b)) enables to compute an upper-bound of the delay. It is presented in the section 4 and validated with a real experimentation.

Finally, the network design approach described in this paper is illustrated on a factory communication scenario. The obtained solution is evaluated on a real experimentation and with a network simulator. The results show the segmentation impacts on the temporal performances. Therefore, it is important to have a method to design a switched Ethernet industrial network in order to make it deterministic under some specific hypothesis.

2 Partitioning problem

Problem

The graph theory is often used to study networks topology. It is obviously true for switched Ethernet networks as shown by the figure 3 where the dot line represents the distribution of the devices on the two second level switches. In the graph, each industrial device is represented by a vertex and the network communication by an edge between two vertices, i.e. two devices. A partition of this graph will correspond to the mapping of the industrial devices on the different switches. If communications are not uniform across the graph, then it can be valuated by means of weight on the edges (for example, to represent the amount of data exchanged between two devices each second). The weighted graph partitioning problem can be stated as follows :

¡ ¢£ ¤ ¥ ¦ § ¨©¨£ ¢ ¨ ¡ ¢£ ¤ ¥ ¡ ¢£ ¤ ¥ ¡ ¢£ ¤ ¥¦ ¡ ¢£ ¤ ¥
Given a graph with vertex and edge weights, partition the vertices into disjoint subsets so that the sum of the vertex weights of each subset is closed to the average sum, and the total cost of the cut edges (edges that connect vertices in distinct subdomains) is minimized.

Let G = (V, E, w) be an undirected graph :

             V = {v 1 , v 2 , ..., v n } set of vertices E ⊆ V × V set of edges w : E -→ N weights of the edges
The k-way partitioning problem consists in dividing the vertices of a given graph into k disjoint subsets called partitions (P ) that are subject to some constraints. The partitioning problem can be expressed as the optimization of a single objective (i.e. the edge-cut) :

Objective: min i,j w ij = {w (v i , w j ) | v i ∈ P k , w j ∈ P l ∀k = l} Constraints:              k i=1 P i = V (1) P i ∩ P j = {∅} ∀i = j (2) |P 1 | ≈ |P 2 | ≈ • • • ≈ |P k | (3)
The objective is also to minimize the edge-cut under the constraint that each vertex is associated to a single partition (constraints (1) and ( 2)) and that the number of vertices in each partition

|P i | is balanced (constraint (3)).
The quality of a graph partitioning is a subjective measurement which depends on the nature of the application. Our objective is to minimize the traffic inside the federative switch and to balance the traffic on the second level switches : When we partition nodes into subgroups, it might happen that some subgroups support a higher traffic than other subgroups. To avoid this situation, we can partition nodes so that the traffic flows in subgroups are balanced. In the graph representation, it consists both in maximizing intra-group exchanges (the total amount of vertex weights assigned to each partition) and in minimizing the inter-group dialogues (minimizing the total weight of edge-cuts).

For the balancing problem, the sum of the vertices weights in each sub-group is controlled.

Even if this approach leads to optimise the end-to-end delays, it does not guarantee that they respect a predefined bound time. That is why in the following sections, we propose to use an objective function in which the endto-end delay is directly formulated.

3 Adaptation of the Genetic Algorithms to the network design

Introduction

The issue is to determine on which second level switch an industrial device has to be connected. The objective is to propose a segmentation scheme for which the maximum end-to-end delays are minimized in order to guarantee deterministic communications.

Before running a GA, it is necessary to define:

• the individuals on which it operates (encoding),

• the operators it uses,

• some parameters such as the population size . . . ,

• an objective function.

Coding structure

For the segmentation problem, several encoding methods could be defined. The most often used is the N-string representation. Each chromosome corresponds to one vector in which the i th element of an individual is j if the i th industrial device is connected to the second level switch labeled j. There are as many elements in the vector as factory devices in the network. The k-ary alphabet [1, 2, . . . , k] is used to code the switch label. For instance, the string [112332231] represents the mapping that assigns devices 1, 2, 9 to switch 1, devices 3, 6, 7 to switch 2 and devices 4, 5, 8 to switch 3. The figure 4 illustrates the encoding of this solution and the decoding of this solution.

Crossover and Mutation operators

In GA, these operators are the two most important space exploration operators. A crossover operator creates a new offspring chromosome by combining parts of the parents' chromosomes. A two-point crossover is used in our algorithm.

The crossover operator can generate illegal chromosomes. In the figure 6, an offspring violated the number of partitions constraint (3 groups are expected). A repairing procedure is defined : permutations are applied out of the cutpoints in order to preserve the scheme of parent chromosomes.

The mutation operator enables to introduce unexplored search space to the population. The most often used method is the bit-flip mutation. But it can 1 1 1 2 2 3 2 3 2 1 1 1 2 2 3 2 3 2 2 2 2 1 3 2 3 3 3 2 2 2 1 3 2 3 3 3 Parents Cut point 1 Cut point 2 1 1 1 1 3 2 2 3 1 1 1 1 3 2 2 3 2 2 2 2 2 3 3 3 2 2 2 2 2 3 3 1 1 1 2 2 3 2 3 2 1 1 1 2 2 3 2 3 2 2 2 2 1 3 2 3 3 3 2 2 2 1 3 2 3 3 1 1 1 1 3 2 2 3 1 1 1 1 3 2 2 3 2 2 2 2 2 3 3 3 2 2 2 2 2 3 3 2 2 2 1 3 3 3 3 3 2 2 2 1 3 3 3 3 3 2 2 2 3 3 2 3 3 3 2 2 2 3 3 2 3 3 3 Parent 3 2 1 3 3 1 2 1 3 2 2 3 3 1 1

Parameters setting

Goldberg (1989) defined conventional GA parameters such as population size (pop size ), crossover (p c ) and mutation (p m ) probabilities. They influence the performance of the algorithm. For example, the size of the initial population influences on the quality of the final solution to the detriment of the execution time. For our problem, optimal values have been computed in [START_REF] Krommenacker | Heuristiques de conception de topologies réseaux : Application aux réseaux industriels[END_REF].

Objective function

The quality of a solution will be defined according to the respect of the timeconstraints. Thus, to determine the quality of the segmentation, the evaluation function has to take into account the end-to-end delay. In previous works [START_REF] Kamen | Design and analysis of packet-switched networks for control systems[END_REF], [START_REF] Torab | Performance analysis of packet switched networks with tree topology[END_REF]), the objective consists in reducing the average end-to-end delays which are computed by using stochastic theory. As the question is to know if switched Ethernet guarantees the temporal constraints, a deterministic theory is necessary. The objective function is formulated as :

f = max i D i -T i
with i the message index, D i the message maximum end-to-end delay and T i the message time constraint). It has to be minimized until it becomes negative (for example, a control message has to be periodically received in a time interval lower than the Programmable Logical Controller time-cycle). The network calculus theory presented in section 4 enables to determine the upper-bound delays D i for each message.

Network calculus theory

The network calculus is a deterministic theory of the queuing systems. The main contributions are Cruz (1991a), Le [START_REF] Boudec | Network Calculus, A Theory of Deterministic Queueing Systems for the Internet[END_REF], [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF]. It is traditionally used for scheduling (Le [START_REF] Boudec | Application of network calculus to guaranteed service networks[END_REF], [START_REF] Cruz | Quality of service guarantees in virtual circuit switched networks[END_REF]) and for traffic regulation [START_REF] Chang | A min-plus system theory for constrained traffic regulation and dynamic service guarantees[END_REF]) to improve the Quality of Service. The Network Calculus is also more and more used to study Ethernet networks temporal performances [START_REF] Georges | Evaluation of switched Ethernet in an industrial context by using the network calculus[END_REF], [START_REF] Jasperneite | Deterministic real-time communication with switched Ethernet[END_REF]).

Traffic characterization

Since the industrial case gives concise information about communications, deterministic hypothesis on the traffic arrival can be supposed. The modelling of the incoming traffic is traditionally done by using a stochastic model (in [START_REF] Song | Time constrained communication over switched Ethernet[END_REF], it is a Bernouili process). In this paper, the arrival curve (Le Boudec and Thiran, 2001, definition 1.3.1) notion is chosen. In this model, the traffic is unknown but it is assumed that its arrival satisfies a time constraint. Typically, the quantity of data arrived at a time t will not be more than the arrival curve value at the time t. In fact, the arrival of data is assumed to be constrained by a (σ, ρ) envelop b (t) called leaky bucket (figure 8). If R(t) represents the instantaneous rate of data, C the capacity of the links on the network, σ the maximum amount of traffic that can arrive in a burst (initially, it would be the maximum frames length) and ρ an upper bound on the long-term average rate of the traffic flow, then ∀x, y; y ≥ x, x ≥ 0, the burstiness constraint is written R ∼ b which means :

y x R (t) dt ≤ min {C (y -x) , σ + ρ (y -x)} (1)
In the general case, the notion of arrival curves is usually associated with traffic smoothers because the traffic is unknown and has to be limited (for example for the Internet traffic [START_REF] Caponetto | Fuzzy traffic smoothing : Another step towards statistical real-time communication over Ethernet networks[END_REF] uses (σ, ρ) regulators).

In opposition, in an industrial context, the traffic is better known and it is possible to determine real constraints on the traffic arrival at the application layer such as the periodic messages transmissions during each PLC time-cycle.

Service modelling of the network devices

In this section, a switched network modelling is proposed. For this, it is necessary to describe the internal behavior of the network devices (the switches).

A switch is a complex system which introduces different mechanisms and different technologies. Some models have been proposed : in [START_REF] Song | Time constrained communication over switched Ethernet[END_REF] and in [START_REF] Jasperneite | Deterministic real-time communication with switched Ethernet[END_REF], a blackbox approach is used. In opposition, our contribution is to model in a constructive way as done by [START_REF] Giaccone | Delay bounds for combined input-output switches with low-setup[END_REF], but with a more detailed functional decomposition. [START_REF] Phipps | A guide to LAN switch architectures and performance[END_REF] and [START_REF] Seifert | The Switch Book[END_REF] decompose the switching architecture in three main functional components :

• the queuing model refers to the buffering and the congestion mechanisms located in the switch,

• the switching implementation refers to the decision making process within the switch (how and where a switching decision is made), • and the switching fabric is the path that data takes to move from one port to another one.

Switches are modelled as presented on the figure 9. It is the result of a study described in [START_REF] Georges | Comparison of switched Ethernet architectures models[END_REF] in which several models are built and compared. The model is constituted of a sequence of three basic elements : one multiplexer, one queue and one demultiplexer. In order to take into account the internal speed of a switch, the three following capacities will be used : C, the throughput inside the switch, C in , the throughput of arrival of data on input ports and C out , the output speed. In a first step, this traffic will be multiplexed with the others incoming data.

C in C (σ 1 , ρ 1 ) (σ * 1 , ρ 1 ) C out C C fifo output
Next, data frames are buffered in the shared-memory queue which processes them with a FIFO scheme (representation of Ethernet fairness). As switches are connected themselves or to station by links, the model has to be completed with queues in order to represent the time spent to transmit data on a link which has a capacity C out . In this work, the link transmission mode is supposed to be the full-duplex mode in order to avoid collision problems introduced in the half-duplex one. Thus, frames are finally transmitted on the medium at a rate (σ * 1 , ρ 1 ).

The objective is now to mathematically formulate the service offered by each of these elements and to propose a bound for the time needed to cross them.

For that, we introduce in a first time the network calculus approach of Cruz.

The quantity of data processed in the element is called the backlog ((Le Boudec and Thiran, 2001, definition 1.2.1)) and could be seen as the congestion value of the element. It is defined at time t by the amount of data which is already arrived at time t, minus the amount of data processes at the same time. In the network calculus theory, the delays correspond to the time needed to process the backlog. So, upper bounded delays depend in the worst case on the maximum backlog expression.

Let us consider now the first element used in the model of the figure 9. The multiplexer function consists in forwarding all the streams of the different input links in one output link. For L the maximum length of the frames and C 2 the capacity of the input link 2, (Cruz, 1991a, theorem 4.1) has defined that the transit delay of a 2 input-ports multiplexer FIFO is upper bounded by In the equation (2) (illustrated on the figure 10 where the burst length of the stream 1 is the longest), the maximum backlog value (number of data arrived minus number of forwarded data) is divided by the multiplexer forwarding rate.

D mux,1 (t) = 1 C out max t≥0 [b 1 (t) + b 2 (t + L/C 2 ) -C out t] (2)
The extension of Cruz work in [START_REF] Georges | Evaluation of switched Ethernet in an industrial context by using the network calculus[END_REF] provides directly : the delay applied to any bit entering in a FIFO m-inputs multiplexer from the stream i is upper-bounded by :

D mux,i = 1 C out min B mux,i , B mux,k (3)
where

B mux,i = m z=1;z =i b z σ i C i -ρ i + Lz Cz + (C i -C out ) σ i C i -ρ i B mux,k = min k;k =i m z=1;z =k b z σ k C k -ρ k -L k C k + Lz Cz + (C k -C out ) σ k C k -ρ k -L k C k -ρ i L i C i + L k
The second basic element of the figure 9, the FIFO queue, is constituted of one input buffer in which data are queued, and of one server which forwards this data. This element can be considered as a regulator (σ = 0, ρ = C out ) (Cruz (1991b)). Moreover, the FIFO queue can be viewed as a particular FIFO multiplexer, just with one input port. The analysis developped in [START_REF] Georges | Comparison of switched Ethernet architectures models[END_REF] will be used and therefore:

D f if o = 1 C out (C in -C out ) C in -ρ in σ in (4)
This equation can be easily obtained from the previous one, using the fact that there is only one input port.

Finally, the central demultiplexer function is to split the streams that arrive on the input link and to route them to the appropriate output links. In the Ethernet, this work consists to read the destination address at the beginning of the frame and to select in the forwarding table the output port. Moreover the routing strategy is fixed. Therefore it is assumed that the routing step is instantaneously achieved.

Towards an end-to-end delay evaluation function

In the previous section, upper-bounded delay equations have been proposed for crossing one switch. In these equations, the maximum delay D depends on the leaky bucket parameters : the maximum amount of traffic σ that can arrive in a burst and the upper-bound ρ on the long-term average rate. Consequently, we need to know the (σ, ρ) envelop at each point of the network. As shown by the figure 11, the problem is that we only know the initial arrival curve (σ 0 , ρ 0 ). The other arrival curves, for example after crossing the first switch (σ 1 , ρ 1 ), have to be determined. In order to resolve the evolution of the burstiness constraint of a flow, Cruz extends the previous method. For a system for which the arrival of data is constrained by b in (R in ∼ b in ) and for which the delay D for crossing the system is finite (D < +∞), he shows that the output of data is contrained by b out (R out ∼ b out ) with b out (x) defined for all x positive by:

(σ 0 , ρ 0 ) (σ 1 , ρ 1 ) (σ 2 , ρ 2 ) ? ? D switch D switch
b out (x) = b in x + D (5)
And if we develop the previous equation by using the relation (1), we have:

σ out = σ in + ρ in D (6) ρ out = ρ in
In the case of the figure 11, the arrival curve after crossing the first switch will be also defined by (σ 1 , ρ 1 ) = σ 0 + ρ 0 D switch , ρ 0 . This analysis is based on the fact that the arrival rate stays constant and that the delay is translated in a supplementary burst.

The method steps of the end-to-end delay resolution are :

(1) To identify all streams on each station and to determine the initial leaky bucket values.

(2) To identify the route of each stream (in switched Ethernet networks, paths are determined by the spanning tree).

(3) On each switch, to formulate all streams output burstiness equations as described in the equation 6. (4) To define the equation systems under the mathematical form a n σ 1 +b n σ 2 + ... + z n σ m = δ n . (5) To calculate the burstiness values. ( 6) To determine the end-to-end delay with

D i = σ h i -σ 0 i ρ i
where h represents the number of crossed switches minus one.

End-to-end delays over the complete network are obtained by computing the equation given at the last step of the method. For the evaluation function included in the Genetic Algorithm, all the maxima end-to-end delays are computed and the obtained value corresponds to the highest delay.

Validation of the method

In order to confirm the validity of the model, a set of experimental measurements has been carried out. In these experiments, the time needed to transmit one frame from the sender to the receiver on a switched Ethernet network is measured. These results will be then compared with the bound given by the network calculus applied on the model proposed in this paper and also compared with the delays provided by a network simulation tool, Comnet III (figure 15).

The platform is constituted of one Cisco Catalyst 2912 XL switch and three stations. Links are always configured at 10Mb/s in the full-duplex mode. garros periodically sends frames of 64 bytes of data (the minimum data length in an Ethernet frame) from the first Ethernet (eth1) to its second Ethernet interface (eth0). The period is fixed at 10 ms. In order to load the switch, a garros garros ferdrupt ferdrupt background traffic is generated : ferdrupt and drec send frames of 1500 bytes of data (the maximum data length in an Ethernet frame) each 5 ms to the Ethernet interface eth0 of garros.

¡¢£ ¡¢¤ drec drec σ¥ ¦ σ¥ § σ § § σ¨ § σ § ¦ σ¨¦ σ 0 1 σ 0 2 σ 0 3 σ 1 1 , σ 1 2 , σ 1 3 σ 2 1 , σ 2 2 ,
We apply now the method steps of the end-to-end delay resolution previously presented. First, we identify the initial leaky bucket values of each stream.

There are three streams in this network : from garros/eth1 to garros/eth0 (stream 1, initial leaky bucket b 0 1 (t)), from ferdrupt to garros/eth0 (stream 2, b 0 2 (t)) and from drec to garros/eth0 (stream 3, b 0 3 (t)). The parameters of the traffic generators give :

b 0 1 (t) = σ 0 1 + ρ 1 t = 72 + 7200t b 0 2 (t) = σ 0 2 + ρ 2 t = b 0 3 (t) = σ 0 3 + ρ 3 t = 1526 + 305200t
As shown on the figure 12, 6 unknowns have to be computed. Also, for each of the basic element of the switch model, we formulate all streams output burstiness. It gives the following equation system :

                                 C ρ 1 σ 1 1 = ρ 1 C + 1 σ 0 1 + σ 0 2 + ρ 1 +ρ 2 C-ρ 3 σ 0 3 + L 3 -(ρ 1 + ρ 2 ) L 3 C 3 + ρ 2 L 2 C 2 (1.1) Cout(C-(ρ 1 +ρ 2 +ρ 3 )) ρ 1 (C-Cout) σ 2 1 = ρ 1 (C-Cout) Cout(C-(ρ 1 +ρ 2 +ρ 3 )) + 1 σ 1 1 + σ 1 2 + σ 1 3 (1.2) C ρ 2 σ 1 2 = σ 0 1 + ρ 2 C + ρ 1 +ρ 3 C 2 -ρ 2 σ 0 2 + σ 0 3 + ρ 1 L 1 C 1 + ρ 3 L 3 C 3 (2.1) Cout(C-(ρ 1 +ρ 2 +ρ 3 )) ρ 2 (C-Cout) σ 2 2 = σ 1 1 + ρ 2 (C-Cout) Cout(C-(ρ 1 +ρ 2 +ρ 3 )) + 1 σ 1 2 + σ 1 3 (2.2) C ρ 3 σ 1 3 = σ 0 1 + σ 0 2 + ρ 3 C + ρ 1 +ρ 3 C 3 -ρ 3 σ 0 3 + ρ 1 L 1 C 1 + ρ 2 L 2 C 2 (3.1) Cout(C-(ρ 1 +ρ 2 +ρ 3 )) ρ 3 (C-Cout) σ 2 3 = σ 1 1 + σ 1 2 + ρ 3 (C-Cout) Cout(C-(ρ 1 +ρ 2 +ρ 3 )) + 1 σ 1 3 (3.2)
These equations are obtained by using the equations ( 3), ( 4) and ( 6). When the burstiness values σ are computed, the next step is to calculate

D 1 = σ 2 1 -σ 0 1 ρ 1
in order to determine the maximum end-to-end delay for the stream 1. The result gives : 3025 µs. This reference of 3025 µs will now be compared with the experimental measures. We obtain the results presented on the figure 13. Then, we used the simulation. In Comnet III, a network device such as a switch is modelled by using buffers to represent input and output ports on which are specified both buffer sizes and buffer processing times (CACI Products Company (1998)). It also uses internal buses for moving frames from one port to another one.

On this example, the simulation tool gives a maximum delay of 450 µs. First, if we compare it to the bound provided by the Network Calculus, we can conclude that the over-estimation of the network calculus is very important. But if we compare now this bound to the experimental results presented on the figure 13, we can remark that even if almost all measures are very inferior to this bound and to the simulation value, some measures tend to the calculus bound. Indeed, more than 62 % of the measures are inferior to 450 µs (the average of the measures is 608 µs). Some observed delays grow up to 2869 µs, i.e. nearly 6 times more. It shows that a simple capacity analysis (the load of the link between the switch and the network interface eth0 of garros is less than 50 %) is not sufficient to ensure that an Ethernet network will respect the industrial requirements. Moreover, it shows that calculus bounds are closed to the greatest measures since the over-estimation is only about 5 % of the maximum delay measured.

A case study

The first step is to determine the number of switches on which the application has to be distributed. It can be imposed by the designer who can also use graph partitioning techniques [START_REF] Adoud | Configuration of communication networks by analysing co-operation graphs[END_REF]). In order to show the benefits provided by the optimization of the segmentation of a switched Ethernet network, the factory communication scenario of the figure 14 is studied. Fifteen industrial devices have to be interconnected on three switches. The exchanges are represented on the figure 14(b). The weights defined on the exchange matrix represent the amount of data sent by a device to another one. For example, device 3 sends to device 11, 4 * (basic length) per time -cycle bytes per second. If it is supposed that the basic length is 64 bytes (minimum size of an Ethernet frame) and that a device sends a packet each 2 ms (P.L.C. time-cycle). So the rate of arrival of data from device 3 to 11 is 5, 12 kbytes/s.

In order to verify that a hierarchical switched Ethernet architecture could be used in this example, with end-to-end delays always lower than the timecycle, the Genetic Algorithm with the objective function computed with the network calculus is launched. An arbitrary distribution and an optimized solution are compared. The first one distributes devices {1, 2, ...5} on the first switch, {6, ...10} on the second one, {11, ...15} on the third one. The GA provides the following distribution called 'optimized' architecture and collects the industrials devices {1, 4, 6, 7, 14} on the first switch, {8, 9, 11, 12, 15} on the second one, {2, 3, 5, 10, 13} on the third one. The results are confronted with those provided by Comnet III (figure 15). Moreover, in order to improve the performance evaluation of the design process, experimental measurements have been carried out both for the arbitrary and the optimized architectures. The principle of these measures is the same than for the validation of the method presented in section 4.4. Using the network calculus, the worst communication delays have been identified : exchange from 12 to 1 for the arbitrary topology and exchange from 6 to 11 for the optimized topology. They are given on the table 1. To note that for the arbitrary architecture, the network calculus investigates up to 188 unknowns burtiness values when for the optimized solution, the number of unknowns is only 160. It is due to the fact that paths are shorter in the optimized solution. That could be seen as a first indicator of the interest of our proposition.

The table 1 shows that delays can be reduced if a methodology for distributing the industrial devices on the switches is applied. Indeed, in the optimized solution, the network calculus theory guarantees that maximum delays will be smaller than the time-cycle (2ms), when the non-optimized distribution exceeds it. The simulator results also show that the end-to-end delays are reduced. To note that, the results provided by the simulator are lower than the time-cycle. So the arbitrary solution could be considered as suitable regarding the application constraints. Nevertheless, the experimental measurements confirm the network calculus results. In fact, the values obtained by simulation represent more the more frequent case than the worst one. The simulation does not provide such formal validation due to its probabilistic approach. The set of experimental measures validate the design process presented in this paper.

And more generaly, this case study shows the pertinence of the method : to provide an optimized segmentation for which we are sure that the application constraints will be respected.

Conclusion

In this paper, an algorithm to design hierarchical switched Ethernet networks has been given. The optimization heuristic used is the Genetic Algorithm for which a new objective function has been developed. This function evaluates the maximum end-to-end delays of the messages over the network. Bounds are computed by using the network calculus theory, which considers the worst case. Thus, from a well-known incoming traffic, it is possible to guarantee deterministic performances for the communication architecture. This approach enables to valid the network topology and proposes a distribution of the industrial devices which respects the temporal application constraints, even if this heuristic does not provide the best solution.

In future works, the presented method will be analyzed in order to improve the convergence of the algorithm. Indeed, its running time is important (2 minutes for the case study described in the paragraph 5). It is not a problem for the design of static applications. Nevertheless, it has to be reduced for applications which dynamically evolve in terms of number of interconnected devices, traffic flows and default occurrences.

Supplementary constraints could be taken into account such as the cabling cost, the location of the end equipments which limits the number of possible solutions (and the algorithm execution time, since the search space is reduced). The method could be also recursively processed in order to get a n levels hierarchical topology as it is done with the spectral algorithm [START_REF] Simon | Partitioning of unstructured problems for parallel processing[END_REF]).

Figure 1 .

 1 Figure 1. Hierarchical topology for switched Ethernet networks

Figure 2 .

 2 Figure 2. The segmentation problem is a graph partitioning one.

Figure 3 .

 3 Figure 3. Representation of a switched Ethernet network by a graph.

  Figure 4. Encoding network topology

  Figure 5. Two-point crossover operator

  Figure 6. Repairing step

  Figure 7. Mutation operators

  Figure 8. Traffic upper bounding

  Figure 9. Switch model

Figure 10 .

 10 Figure 10. Backlog evolution inside a two-inputs multiplexer FIFO

Figure 11 .

 11 Figure 11. Burstiness along a switched Ethernet network.

Figure 12 .

 12 Figure 12. The experimental platform.

Figure 13 .

 13 Figure 13. End-to-end delays of each frames sent by garros (stream 1) in µs on the network of the figure 12.

  Figure 14. The case study network.

Figure 15 .

 15 Figure 15. The network simulator Comnet III

Table 1

 1 Performance of the architectures (values are in millisecond)

	architecture	network calculus comnet experimental
	arbitrary	2, 55	1, 68	2, 38
	optimized	1, 96	1, 53	1, 94


Patrice Bellot

Antoine Doucet

Sairam Kamps

Marijn Gabriella Koolen

Josiane Preminger

S Geva

S Gurajada

J Kamps

G Kazai

M Koolen

A Mishra

V Moriceau

J Mothe

M Preminger

E Sanjuan

R Schenkel

X Tannier

M Theobald

M Trappett

A Trotman

M Sanderson

F Scholer

Q Wang

Report on INEX 2013

INEX investigates focused retrieval from structured documents by providing large test collections of structured documents, uniform evaluation measures, and a forum for organizations to compare their results. This paper reports on the INEX 2013 evaluation campaign, which consisted of four activities addressing three themes: searching professional and user generated data (Social Book Search track); searching structured or semantic data (Linked Data track); and focused retrieval (Snippet Retrieval and Tweet Contextualization tracks). INEX 2013 was an exciting year for INEX in which we consolidated the collaboration with (other activities in) CLEF and for the second time ran our workshop as part of the CLEF labs in order to facilitate knowledge transfer between the evaluation forums. This paper gives an overview of all the INEX 2013 tracks, their aims and task, the built test-collections, and gives an initial analysis of the results.

Introduction

Traditional IR focuses on pure text retrieval over "bags of words" but the use of structuresuch as document structure, semantic metadata, entities, or genre/topical structure-is of increasing importance on the Web and in professional search. INEX has been pioneering the use of structure for focused retrieval since 2002, by providing large test collections of structured documents, uniform evaluation measures, and a forum for organizations to compare their results.

INEX 2013 was an exciting year for INEX in which we continued as part of CLEF for the second year, motivated by the desire to foster further collaboration and facilitate knowledge transfer between the evaluation forums. In total four research tracks were included, which studied different aspects of focused information access: Social Book Search Track investigating techniques to support users in searching and navigating collections of digitised or digital books, metadata and complementary social media. The Social Book Search Task studies the relative value of authoritative metadata and user-generated content using a test collection with data from Amazon and Library-Thing. The Prove It Task asks for pages confirming or refuting a factual statement, using a corpus of the full texts of 50k digitized books.

Linked Data Track investigating retrieval over a strongly structured collection of documents based on DBpedia and Wikipedia. The Ad Hoc Search Task has informational requests to be answered by the entities in DBpedia/Wikipedia. The Jeopardy Task asks for the (manual) formulation of effective SPARQL queries with additional keyword filters, aiming to express natural language search cues more effectively.

Tweet Contextualization Track investigating tweet contextualization, helping a user to understand a tweet by providing him with a short background summary generated from relevant Wikipedia passages aggregated into a coherent summary.

Snippet Retrieval Track investigate how to generate informative snippets for search results. Such snippets should provide sufficient information to allow the user to determine the relevance of each document, without needing to view the document itself.

Both Tweet Contextualization and Snippet retrieval use the same XML'ified corpus of Wikipedia, and address focused retrieval in the form of constructing some concise selection of information in a form that is of interest to NLP researchers (tweet contextualization) and to IR researchers (snippet retrieval).

In the rest of this paper, we discuss the aims and results of the INEX 2013 tracks in relatively self-contained sections: the Social Books Search track (Section 4), the Linked Data track (Section 2), and the paired Tweet Contextualization (Section 5) and Snippet Retrieval (Section 3) tracks. We end with an outline of the plans for INEX 2014, again held as part of CLEF 2013 in Sheffield, UK.

Linked Data Track

In this section, we will briefly discuss the INEX 2013 Linked Data Track (addressing the searching structured or semantic data theme). Further details are in [START_REF] Gurajada | Overview of the INEX 2013 linked data track[END_REF].

Aims and Tasks

The goal of the Linked Data track was to investigate retrieval techniques over a combination of textual and highly structured data, where RDF properties carry additional key information about semantic relations among data objects that cannot be captured by keywords alone. We intend to investigate if and how structural information could be exploited to improve ad-hoc retrieval performance, and how it could be used in combination with structured queries to help users navigate or explore large result sets via Ad-hoc queries, or to address Jeopardystyle natural-language queries which are translated into a SPARQL-based query format. The Linked Data track thus aims to close the gap between IR-style keyword search and Semantic-Web-style reasoning techniques. Our goal is to bring together different communities and to foster research at the intersection of Information Retrieval, Databases, and the Semantic Web.

For INEX 2013, we explored two different retrieval tasks that continue from INEX 2012:

• The classic Ad-hoc Retrieval task investigates informational queries to be answered mainly by the textual contents of the Wikipedia articles.

• The Jeopardy task employs natural-language Jeopardy clues which are manually translated into a semi-structured query format based on SPARQL with keyword conditions.

Test Collection

The Linked Data track used a subset of DBpedia 3.8 and YAGO2s together with a recent dump of Wikipedia core articles (dump of June 1st, 2012). Valid results are entities occurring in both Wikipedia and DBpedia (and hence in YAGO), hence we provided a complete list of valid URIs to the participants. In addition to these reference collections, we will also provide two supplementary collections: 1) to lower the participation threshold for participants with IR engines, a fusion of XML'ified Wikipedia articles with RDF properties from both DBpedia and YAGO2s, and 2) to lower the participation threshold for participants with RDF engines, a dump of the textual content of Wikipedia articles in RDF. Participants are explicitly encouraged to make use of more RDF facts available from DBpedia and YAGO2s, in particular for processing the reasoning-related Jeopardy topics.

The goal of the Ad-hoc Task is to return a ranked list of results in response to a search topic that is formulated as a keyword query. Results had to be represented by their Wikipedia page ID's, which in turn had to be linked to the set of valid DBpedia URI's. A set of 144 Adhoc task search topics for the INEX 2013 Linked Data track had been released in March 2013 and was made available for download from the Linked Data Track homepage. In addition, the set of QRels from the 2012 Ad-Hoc Task topics was provided for training.

These are familiar IR topics, an example is: As in 2012, the Jeopardy task continued to investigate retrieval techniques over a set of natural-language Jeopardy clues, which were manually translated into SPARQL query patterns with additional keyword-based filter conditions. A set of 105 Jeopardy task search topics, out of which 74 topics were taken over from 2012 and 31 topics were newly added to the 2013 setting. 72 single-entity topics (with one query variable) were also included into the set of 144 Ad-hoc topics. All topics were made available for download in March 2013 from the Linked Data Track homepage. In analogy to the Ad-hoc Task, the set of topics from 2012 was provided together with their QRels for training. An example topic is:

<topic id="

Results

In total, 4 ad-hoc search runs were submitted by 3 participants and 2 valid Jeopardy! runs were submitted by 1 participant. Assessments for the Ad-hoc Task were done on Amazon Mechanical Turk by pooling the top-100 ranks from the 4 submitted runs in a round-robin fashion. Conversely, the top-10 results were pooled from the 3 Jeopardy submissions for the single-entity topics and by pooling the top-20 for the multi-entity topics, respectively, again in a round-robin fashion. A total of 72 Ad-hoc topics and 77 Jeopardy topics were assessed.

The TREC-eval tool was adapted to calculate the following well-known metrics [START_REF] Amer-Yahia | XML search: languages, INEX and scoring[END_REF][START_REF] Kamps | INEX 2007 evaluation measures[END_REF] used in ad-hoc and entity ranking settings: Precision, Recall, Average-Precision (AP), Mean Average Precision (MAP), Mean Reciprocal Rank (MRR), and Normalized Discounted Cumulated Gain (NDCG).

Given the low number of submissions, it is difficult to draw general conclusions from the runs, but individual participants found various interesting results demonstrating the value of the build test collection for research in this important emerging area. We hope and expect that the test collection will be (re)used by researchers for future experiments in this active area of research. The track will team up with the CLEF QA track, and continue the Jeopardy task focusing on complex questions.

Outlook

The Linked Data Track was organized towards our goal to close the gap between IR-style keyword search and Semantic-Web-style reasoning techniques. The track thus continues one of the earliest guiding themes of INEX, namely to investigate whether structure may help to improve the results of ah-hoc keyword search. A key contribution is the introduction of a new and much larger supplementary XML collection, coined Wikipedia-LOD v2.0, with XML-ified Wikipedia articles which were additionally annotated with RDF properties from both DBpedia 3.8 and YAGO2. However, due to the very low number of participating groups, in particular for the Jeopardy, detailed comparisons of the underlying ranking and evaluation techniques can only be drawn very cautiously.

Snippet Retrieval Track

In this section, we will briefly discuss the INEX 2013 Snippet Retrieval Track (one of the tracks addressing the focused retrieval theme). Further details are in [START_REF] Trappett | Overview of the INEX 2013 snippet retrieval track[END_REF].

Aims and Task

The goal of the snippet retrieval track is to determine how best to generate informative snippets for search results. Such snippets should provide sufficient information to allow the user to determine the relevance of each document, without needing to view the document itself. This allows the user to quickly find what they are looking for.

A set of topics (or queries) was provided, each with a corresponding set of search results. Participants were then tasked with automatic generation of text snippets describing each document returned by a query. Returned snippets were limited to a maximum of 180 characters. The snippets may be created in any way-they may consist of summaries, passages from the document, or any other text at all.

Collection

The topics for the 2013 track have been reused from the 2012 Snippet Retrieval track. There were 35 topics in total -10 originally taken from the INEX 2010 Ad Hoc Track, and 25 created specifically for the Snippet Retrieval track in 2012, with the goal being to create topics requesting more specific information than is likely to be found in the first few paragraphs of a document.

Each topic contains a short content only (CO) query, a phrase title, a one line description of the search request, and a narrative with a detailed explanation of the information need, the context and motivation of the information need, and a description of what makes a document relevant or irrelevant.

For each topic, there is a corresponding set of twenty documents -the search results for the topics. These XML documents are based on a dump of the English language Wikipedia, from November 2012 -the same collection as the Tweet Contextualisation track.

Assessment and Evaluation

To determine the effectiveness of the returned snippets at allowing a user to determine the relevance of the underlying document, manual assessment is used. Both snippet-based and document-based assessment are used.

The documents are first assessed for relevance based on the snippets alone, as the goal is to determine the snippet's ability to provide sufficient information about the document. Each topic within a submission is assigned an assessor. The assessor, after reading the details of the topic, reads through the top 100 returned snippets, and judges which of the underlying documents seem relevant based on the snippets alone.

To avoid bias introduced by assessing the same topic more than once in a short period of time, and to ensure that each submission is assessed by the same assessors, the runs are shuffled in such a way that topics from each submission are spread evenly amongst all assessors.

Additionally, each of the 20 documents returned for each of the 35 topics is assessed for relevance based on the full document text. This full set of 700 documents is assessed multiple times, by separate assessors. The majority judgment formed by all of the document assessments is treated as a ground truth.

Submissions are evaluated by comparing the snippet-based relevance judgements with the document-based relevance judgements, which are treated as a ground truth.

The primary evaluation metric used is the geometric mean of recall and negative recall (GM). A high value of GM requires a high value in recall and negative recall -i.e. the snippets must help the user to accurately predict both relevant and irrelevant documents. If a submission has high recall but zero negative recall (e.g. in the case that everything is judged relevant), GM will be zero. Likewise, if a submission has high negative recall but zero recall (e.g. in the case that everything is judged irrelevant), GM will be zero.

Details of additional metrics used are given in [START_REF] Trappett | Overview of the INEX 2013 snippet retrieval track[END_REF].

Results

In the 2013 Snippet Retrieval track, 4 runs were submitted, from 2 participating groups. In addition, a baseline run was generated and evaluated, consisting of the first 180 characters of each document.

As of this writing, only preliminary results have been released. While each of the submissions have had their snippets assessed, the set of full-text documents has been assessed only once. The final set of results will use the majority opinion of multiple document assessors as its ground truth relevance judgments. This will be released at a later date, once further document assessment has been completed.

The initial results have all runs scoring highly on recall, but poorly on negative recall. This indicates that while users are able to easily identify most irrelevant results based on snippets alone, poor snippets are causing users to miss over half of all relevant results.

Social Book Search Track

In this section, we briefly discuss the INEX 2013 Social Book Search (SBS) Track. Further details can be found in [START_REF] Koolen | Overview of the INEX 2013 social book search track[END_REF].

Aims and Tasks

Prompted by the availability of large collections of digitized books, the SBS Track aims to promote research into techniques for supporting users in searching, navigating and reading full texts of digitized books and associated metadata. This year, the track ran two tasks: the Social Book Search task and the Prove It task:

1. The Social Book Search (SBS) task, framed within the scenario of a user searching a large online book catalogue for a given topic of interest, aims at exploring techniques to deal with both complex information needs of searchers-which go beyond topical relevance and can include aspects such as genre, recency, engagement, interestingness, and quality-and heterogeneous information sources including user profiles, personal catalogues, professional metadata and user-generated content.

2. The Prove It (PI) task aims to test focused retrieval approaches on collections of books, where users expect to be pointed directly at relevant book parts that may help to confirm or refute a factual claim;

In addition to these task, the Structure Extraction (SE) task ran at ICDAR 2013 [START_REF] Doucet | Overview of the ICDAR 2013 Competition on Book Structure Extraction[END_REF], with the aim of evaluating automatic techniques for deriving structure from OCR and building hyperlinked table of contents. The extracted structure could then be used to aid navigation inside the books.

Test Collections

For the SBS task a new type of test collection has been developed. Unlike traditional collections of topics and topical relevance judgements, the task is based on rich, real-world information needs from the LibraryThing (LT) discussion forums and associated user profiles of LT members. The collection consists of 2.8 million book descriptions from Amazon, including reviews, and is enriched with user-generated content from LT. For the information needs we used the LT discussion forums. We selected 380 discussion threads which focus on members asking for book recommendations on various topics. The initial messages in these threads often contain detailed descriptions of what the members are looking for. The relevance judgements come in the form of suggestions from other LT members in the same discussion thread. We hired trained annotators to indicate whether the person suggesting the book has read it and whether their recommendations had a positive, neutral or negative sentiment. From these we then derived relevance values for the suggested books, combining the topic creator's feedback on the recommendations with the opinions of those who recommended them. The final set of judgements contain an average of 16 book suggestions per topic. Note that the judgements are independent of the submitted runs, which avoids pooling bias. Previously we investigated the reliability of using forum suggestions for evaluation and found they are complete enough, but different in nature (leading to different system ranking) from editorial judgements based on topical relevance [START_REF] Koolen | Social Book Search: The Impact of Professional and User-Generated Content on Book Suggestions[END_REF].

The PI task builds on a collection of over 50,000 digitised out-of-copyright books (about 17 million pages) of different genre marked up in XML. The task was first run in 2010 and was kept the same for 2011 and 2012. Since the topic statements are generally complex, relevance judgements in 2012 were collected on the atomized statements, meaning that assessors were asked to judge each aspect of each statement, from which the final judgments (weather a book page confirms or refutes the statement) were compiled. This year the aim was to evaluate book-pages not only on whether they contained information confirming or refuting a statement, but also whether the book is authoritative and of an appropriate genre and subject matter such that a reader would trust the information within.

The SE task at ICDAR2013 used a subset of the PI task's collection and required participants to extract the tables of contents for 1,000 digitized books. For the first time in 2013, the ground truth production was performed by an external provider, and partly funded by the Seventh Framework Program (FP7) of the EU Commission. In previous years this was done by the task participants.

Results

Eight teams together submitted 34 runs to the SBS task and two teams submitted 12 runs to the PI task. The SBS task evaluation has shown that the most effective systems use all available book information-professional metadata and user-generated content-and incorporate either the full topic statement, which includes the title of the topic thread, the name of the discussion group, the full first message that elaborates on the request and the query generate by annotators, or a combination of the title and the query. None of the groups used user profile information for the runs they submitted. Analysis of the individual topics revealed that there is a large set of topics on which all systems fail to retrieve relevant results. This is probably due to the incompleteness of book suggestions and the vagueness and complexity of the topic statements. Next year, we will select only topics that are well-defined and have enough discussion in the thread to signal relative completeness of the suggestions.

For the PI task, we expect to have crowdsourced relevance judgments from Mechanical Turk with book appropriateness and evaluation results in time for the INEX proceedings. Evaluation results so far with relevance judgments for the statements split into their atomic aspects indicate that performance increases when matching named entities (persons and locations) from the statements with named entities in the pages.

A total of 9 organizations signed up to the SE task, 6 of which submitted runs. This increase in active participants is probably a direct result of both 1) the availability of training data and 2) the removal of the requirement for participating organizations to create part of the ground truth. This round of the competition further demonstrated encouraging progress, as for the first time since the competition started, one organization has beaten the baseline BookML format provided by MDCS (Microsoft Development Center Serbia) in 2008.

Outlook

Next year, we continue with the SBS task to further investigate the role of professional and user-generated information, but focus more on the recommendation aspect of the task. A larger set of user profiles will be incorporated to allow both content-based recommendation and collaborative filtering techniques. In addition, there will be the new Interactive SBS task. The CLEF-CHiC Lab will not continue next year, but the Interactive task of CHiC will move to the SBS Track and use the same A/LT collection. The organisers of the Interactive task feel the A/LT collection and LT forum topics offer a better use case for Interactive IR experiments dealing with heterogeneous metadata.

The PI task attracted no new participants in the last two years and will not continue next year.

The SE task will continue exclusively at ICDAR, where it has been jointly running for several years. With the discontinuation of the PI task and the introduction of the Interactive task, the focus of the track is shifting more towards the A/LT collection, leaving little connection with the SE task.

Tweet Contextualization Track

In this section, we will briefly discuss the INEX 2013 Tweet Contextualization Track (one of the two tracks addressing the focused retrieval theme). Further details are in [START_REF] Bellot | Overview of the INEX 2013 tweet contextualization track[END_REF].

Aims and Tasks

Text Contextualization differs from text expansion in that it aims at helping a human to understand a text rather than a system to better perform its task. For example, in the case of query expansion in IR, the idea is to add terms to the initial query that will help the system to better select the documents to be retrieved. Text Contextualization on the contrary can be viewed as a way to provide more information on the corresponding text in the objective to make it understandable and to relate this text to information that explains it.

In the context of micro-blogging, which is increasingly used for many purposes such as for on-line client and audience fishing, contextualization is specifically important since 140 characters long messages are rarely self-content. This motivated the proposal in 2011 of a new track at Clef INEX lab of Tweet Contextualization.

The use case is as follows: given a tweet, the user wants to be able to understand the tweet by reading a short textual summary; this summary should be readable on a mobile device without having to scroll too much. In addition, the user should not have to query any system and the system should use a resource freely available. More specifically, the guideline specified the summary should be 500 words long and built from sentences extracted from a dump of WikiPedia. WikiPedia has been chosen both for evaluation purpose and because this is an increasing popular resource while being generally trustable.

Running since 2010 as a complex QA track at INEX, the results showed that only systems that efficiently combine passage retrieval, sentence segmentation and scoring, named entity recognition, text POS analysis, anaphora detection, diversity content measure as well as sentence reordering are effective.

Test Collection

The document collection has been built based on a recent dump of the English Wikipedia from November 2012. All collections are made available on the task website as well as an API to use online indexes powered by Indri. Programs to automatically generate the collections from WikiPedia repositories are also available. Generated documents from Wikipedia dump, consist of a title (title), an abstract (a) and sections (s). Each section has a sub-title (h). Abstract and sections are made of paragraphs (p) and each paragraph can contain entities (t) that refer to other Wikipedia pages.

Over 2012 and 2013 editions, evaluated topics were made of 120 (60 topics each year) tweets manually collected by organizers. These tweets were selected and checked, in order to make sure that:

• They contained "informative content" (in particular, no purely personal messages);

Only non-personal accounts were considered (i.e. @CNN, @TennisTweets, @PeopleMag, @science. . . ).

• The document collection from Wikipedia contained related content, so that a contextualization was possible.

From the same set of accounts, more than 1,800 tweets were then collected automatically. These tweets were added to the evaluation set, in order to avoid that fully manual, or not robust enough systems could achieve the task. All tweets were then to be treated by participants, but only the 120 short list was used for evaluation. Participants did not know which topics were selected for evaluation.

These tweets were provided in a text-only format without metadata and in a JSON format with all associated metadata, an example is:

"text":"007 in #SKYFALL's Floating Dragon casino. #SKYFALL IS OUT ON BLU-RAY/DVD TODAY IN THE UK! http://t.co/kTj5d0Ux", "metadata":"result_type":"recent", "id":303481535074549763, "from_user_id_str":"389229444", "from_user":"007", "geo":null, "from_user_id":389229444, "id_str":"303481535074549763", "iso_language_code":"en", "to_user_id_str":"0", "to_user":null, "from_user_name":"James Bond", "to_user_name":null </txt> </topic>

Measures

Tweet contextualization is evaluated on both informativeness and readability. Informativeness aims at measuring how well the summary explains the tweet or how well the summary helps a user to understand the tweet content. On the other hand, readability aims at measuring how clear and easy to understand the summary is. Informativeness measure is based on lexical overlap between a pool of relevant passages (RPs) and participant summaries. Once the pool of RPs is constituted, the process is automatic and can be applied to unofficial runs. The release of these pools is one of the main contributions of Tweet Contextualization tracks at INEX [START_REF] Sanjuan | Overview of the inex 2010 question answering track (qa@inex)[END_REF]. By contrast, readability is evaluated manually and cannot be reproduced on unofficial runs. In this evaluation the assessor indicates where he misses the point of the answers because of highly incoherent grammatical structures, unsolved anaphora, or redundant passages. Since 2012, readability is evaluated in the context of the tweet. Passages not related to the tweet are considered as unreadable.

Three metrics were used: Relevancy (or Relaxed) metric, counting passages where the T box has not been checked (Trash box if the passage does not make any sense in the context of the previous passages); Syntax, counting passages where the S box was not checked either (i.e, the passage has no syntactic problems), and the Structure (or Strict) metric counting passages where no box was checked at all. In all cases, participant runs were ranked according to the average, normalized number of words in valid passages.

Results

A total number of 13 teams from 9 countries (Brasil, Canada, France, India, Ireland, Mexico, Russia, Spain, USA) submitted runs to the Tweet Contextualization track in 2013. Overall, informativity and readability scores are this year strongly correlated (Kendall test: τ > 90%, p < 10 -3 ) which shows that all systems have integrated these two constrains.

This year, the best participating systems used advanced hashtag preprocessing algorithms. The best run on informativeness used all available tweet features, and was ranked second on readability. The best scoring run on readability used state of the art NLP tools, and was second best on informativeness. The best scoring approach of 2012 rank now third on informativeness, signaling the importance of hashtag processing for the tweets of 2013.

All participants but two used language models, however informativeness of runs that only used passage retrieval is under 5%. Terminology extraction and reformulation applied to tweets was also used in 2011 and 2012. Appropriate stemming and robust parsing of both tweets and wikipedia pages are an important issue.

All systems having a run among the top five in informativeness used the Stanford Core NLP tool or the TreeTagger. Automatic readability evaluation and anaphora detection helps improving readability scores, but also informativeness density in summaries. State of the art summarization methods based on sentence scoring proved to be helpful on this task. Best runs on both measures used them.

Finally, this time the state-of-the-art system proposed by organizers since 2011 combining LM indexation, terminology graph extraction and summarization based on shallow parsing was not ranked among the ten best runs which shows that participant systems improved on this task over the three editions.

Outlook

In 2014 Tweet Contextualization will reuse data released by RepLab (CLEF e-reputaion lab). These are tweets in two languages (English and Spanish) with extra tags: target entity, opinion and priority. The user case could be the following. Given a tweet x that has been labeled as carrying a strong negative opinion about some entity y described by a WikiPedia page, "explain why tweet x could damage the e-reputation of y".

A pilot task in Spanish involving six participants just started to try to deal with humorous tweets and is under evaluation. Spanish has almost as many NLP resources than English so it is easy for a participant to deal with both languages, however evaluating readability in Spanish appears to be different due to the average sentence length and strong grammatical structure.

Envoi

This complete our walk-through of INEX 2013. INEX 2013 focused on three themes: searching professional and user generated data (Social Book Search track); searching structured or semantic data (Linked Data track); and focused retrieval (Snippet Retrieval and Tweet Contextualization tracks). The last two tracks use the same Wikipedia corpus and both address focused retrieval in the form of constructing some concise selection of information in a form that is of interest to NLP researchers (tweet contextualization) and to IR researchers (snippet retrieval)

The INEX tracks cover various aspects of focused retrieval in a wide range of information retrieval tasks. This overview has only touched upon the various approaches applied to these tasks, and their effectiveness. The online proceedings of CLEF 2013 contains both the track overview papers, as well as the papers of the participating groups. The main result of INEX 2013, however, is a great number of test collections that can be used for future experiments, and the discussion amongst the participants that happens at the CLEF 2013 conference in Valencia and throughout the year on the discussion lists.

INEX 2014 will continue the successful collaboration with CLEF, further integrating its activities into the CLEF labs organization. The Social Book Search Track will continue strong, and will focus on the interface between search and recommendation using the profiles of LibraryThing users. the CHIC@CLEF lab will team up with INEX and promote usercentric studies into book search and exploration. INEX has a long history of "interactive" tracks in 2004-2010, and we are very excited about a return of this user-centered focus in close coupling with the system-centered evaluation tasks. The Tweet Contextualization Track will continue with the main task as well as the tweets and resources of the online reputation management (CLEF RepLab) lab. Finally, the Linked Data Track will continue with its Jeopardy task in close collaboration with the CLEF QA lab.


Melanie Krug

Dr Peter Wick
email: peter.wick@empa.ch

Dr Anna E Louw-Gaume

Dr Melanie Kucki

Harald F Krug

Kostas Kostarelos

Bengt Fadeel

Kenneth A Dawson

Dr Anna Salvati

Ester Vµzquez

Dr Laura Ballerini

Dr Mauro Tretiach

Dr Fabio Benfenati

Dr Emmanuel Flahaut

Dr Laury Gauthier

Maurizio Prato

Dr Alberto Bianco

Prof. H F Krug

Prof K Kostarelos

Prof B Fadeel

Prof K A Dawson

Prof E Vµzquez

Prof M Prato

Classification Framework for Graphene-Based Materials

Improved vocabulary/coordinated terminology for structural characterization * Classification within the proposed grid prevents ad hoc naming * Better comparisons between carbon allotropes * Fitting the "molecule of interest" into the classification grid and its position determines which reference GBM should be included in biological experiments * Standard analytical methodology for benchmarking of materials * Future comparative studies possible through minimal material characterization * Aid in structure-activity analogies for predictive toxicology * Support the peer-review process * Clear-cut guidelines for regulatory purposes e

Introduction

Graphene is the enabling material of the 21st century and there are high expectations for its potential applications. A clear and consistent system describing the various derivatives of graphene promotes a precise vocabulary for the family of graphene-based materials. This will be a prerequisite, for example, to understand structure-activity relationships in the context of human health and safety and to avoid generalizations about the capabilities and limitations of graphenebased materials. Within the European Unions GRAPHENE Flagship project, three physical-chemical descriptors specific for graphene were defined to assist in the classification of graphene-based materials.

Graphene, a Carbon Material with Great Potential

"Carbon, the basis of all known life on earth, has surprised us once again." This statement stems from the press release by the Royal Swedish Academy of Sciences regarding their decision to award the 2010 Nobel Prize in Physics "for the groundbreaking experiments regarding the two-dimensional material graphene". [1] In just 10 years graphene has become a lodestar for researchers all over the world. While the media is boosting the public profile of graphene through the reference to "miracle material of the 21st century", [2,3] the number of scientific papers on graphene also exceeded 3000 per year in 2010. [4] The commercial interest in graphene is also reflected by a recent review of the patent landscape of graphene by the UK Intellectual Property office. Graphene patent applications have doubled between 2010 and 2012 and that there has been an order of magnitude difference in the yearly publication figures over the last five years, with a total of 8416 patents worldwide by February 2013. [5] It is anticipated that graphene will withstand the normal seven-step sequence for any new technology: hope-hype-boom-bust-disillusionment-shakeout-profitability and meet expectations for profitability even faster than the other carbon allotropes. [6] Graphene is expected to be at the focus of even greater interest for industrial applications when mass-produced graphene will have the same outstanding performance as the best samples produced in research laboratories. [3] Recently, a roadmap for graphene was published, highlighting its future path in the fields of electronics, photonics, composite materials, energy generation and storage, sensors, metrology, and biomedicine. [3] However, to realize such potentials, the health and environmental impact of the family of graphene materials should be thoroughly evaluated. Although this area will profit from existing knowledge and concepts for the nanosafety hazard and risk assessment of other nanomaterials, there are still various hurdles to overcome. [7][8][9] 3. Confusion and Inconsistency in Naming the Family of Graphene-Based Materials One concern in graphene research is that, similar to carbon nanotubes, the term graphene is used in a generic manner and not in a precise way by scientists to describe many graphene-based materials (GBMs) they have synthesized and studied. [10] The inconsistency in naming arises not only in connection with the use of graphene for isolated singleatom-thick sheets, but also by its reference to related two-dimensional sheetlike and flake carbon forms. [10] Thus, a clear, consistent, and widely accepted system of describing and naming the various derivatives of graphene still needs to be developed. Solving this standardization and nomenclature issue will be of paramount importance to avoid misleading understanding and interpretation amongst all the stakeholders (i.e., researchers, industry, governments, and in particular, regulatory authorities), for whom the science-based assessment of graphene toxicity and environmental, health, and safety concerns carries priority. [11]

Classification Approach for Graphene-Based Materials

Recently, the first nomenclature for 2D carbon forms was published and the motivation for this article was given by the statement "Precise names promote precise ideas". [10] Underlying this attempt towards a more rational graphene nomenclature is a set of definitions based on the fact that graphene materials should be defined by morphological descriptors. For example, typical dimensions could be described by graphenespecific variables such as thickness (layer number) and lateral size. [4,10] In this Essay we would like to build on previous work that attempted to highlight the importance of graphene structural characteristics as determinants of their implications in health and safety. We present an approach (depicted in Figure 1) that supports the structural notation of GBMs, a term in line with that proposed previously. [10] Our nomenclature model considers the number of graphene layers, the average lateral size, and the carbon-tooxygen (C/O) atomic ratio as the three fundamental properties that cover the largest set of current graphene materials encountered in practice and that are the subject of biological testing and of biosafety concern. The two morphological characteristics are included because GBMs consist of not only single-layer graphenes but also few-layer graphenes (i.e., 2-10 layers), graphene oxide (GO, normally a single layer), reduced graphene oxide (rGO; normally a single layer), graphene nanosheets, ultrafine graphite (i.e., more than 10 graphene sheets but below 100 nm in thickness), graphene ribbons, and graphene dots. [9,10] Furthermore, it has been emphasized recently that little is known about the possible differences in the biological behavior of graphene types having differnet layer numbers and lateral sizes and these topics deserve thorough analysis. [9] The addition of the C/O ratio as a functional attribute can be justified by the fact that GBMs are both structurally and chemically heterogeneous. The family of GBMs includes materials with widely variable surface oxygen content and thus, surface chemistry can influence biocompatible dispersion potential and colloidal behavior. [4,9,12] For example, GO and rGO are emerging as popular materials in nanocarbon research, not only as carbon building blocks for biomedical applications but also as starting materials to produce graphene-based materials. [10,11] Our classification framework provides a starting point for the categorization of distinct graphene types within a grid arrangement according to three easy-to-measure and quantifiable characteristics. It is also important to state at this stage that future studies on graphenes biological significance might reveal other important health and safety assessment criteria for graphene. Our proposed methodology could be validated by biologists and nanotoxicologists working with graphene in order to understand relationships between graphene physicochemical characteristics and safety considerations. [10,11] Validation of the proposed methodology will also be given high priority by authors of this article, as members of the GRAPHENE Flagship project. The role of the GRAPHENE Flagship project in the determination of GBM structuresafety relationships is highlighted below.

GBM Structure-Safety Relationships: The Role of the EU GRAPHENE Flagship: The GRAPHENE Flagship is a 10year project and the European Unions biggest research initiative ever with a budget of one billion EURO (http:// graphene-flagship.eu/). This project is tasked to take graphene from the realm of academic laboratories into European society in the space of ten years and to generate economic growth, new jobs, and new opportunities. [13] A specific research program of the flagship (and in which authors of this article participate) is intended to reveal the relationshipes between the material structure and toxicological functions for different types of graphene materials. The adoption of a clear nomenclature framework to reflect the different structural and chemical characteristics of GBMs will greatly help in this endeavor. In combination with the adoption of benchmarked biological assays that offer reliably specific toxicological endpoints, we envision a platform by which all graphene materials will be assessed.

Biological and Toxicological Relevance of Fundamental Properties of GBMs

The biological significance of GBM properties such as layer number, lateral dimension, surface chemistry, surface area, and material purity have already been highlighted. [4,8,9] The layer number determines the thickness, the specific surface area, and bending elasticity with expected outputs such as higher adsorptive capacity for GBM-type molecules when the layer number decreases and increased stiffness/ rigidity during cellular interactions when the material thickness increases. As the lateral sizes of GBMs span several orders of magnitude, from the nanoscale to the microscale (i.e., 10 nm up to > 20 mm), it is important to specify the lateral dimension since this parameter determines the maximum size and degree of deformability of the material which are key variables for cellular uptake, renal clearance, transport across the blood-brain barrier, and many other biological interactions that depend on particle size. [4,14,15] The understanding of the biological relevance of the C/O atomic ratio requires a more detailed examination. From a surface science perspective, it should be considered that members of the GBM family do not have a standard surface. For example, pristine graphene and GO differ in their surface hydrophobicity/hydrophilicity. For the former, the surface is hydrophobic while for GO, surfaces consist of hydrophobic islands with hydrophilic regions showing various degrees of basal reactivity. Graphene oxide could be considered as derivatized graphene with a myriad of oxygen functionalities due to the introduction of carbonyl, hydroxy, and epoxy groups on the planar surfaces and edges of the carbon sheets during graphite oxide exfoliation. Therefore, graphite oxidation endows single-or few-layered GO with the great advantages of improved solubility or dispersibility in aqueous solutions and reasonable colloidal stability. [11,12] Since the coverage with oxygen atoms varies depending on the degree of oxidation during the preparation of GO, it is imperative to understand that these production processes will contribute to the inhomogeneity of the final GO product. Typically, GO with chemical compositions corresponding to a C/O ratio of 4:1 to 2:1 are produced. Graphene can also be transformed into reduced rGO and this will increase the C/O ratio to approximately 12:1 but values as large as 246:1 have recently been reported. [9,12,16] The significance of investigating the three fundamental properties should also be viewed in terms of the relationship between physicochemical characteristics and the health and environmental risks of any nanomaterial. The importance of these characteristics for ecological sustainability is noteworthy as these characteristics might modulate GBM-organism interactions and thus the transfer and impact of GBMs through the food chain and ecosystems. [17] A comparison study that reviewed toxicological aspects of GO in relation to its synthesis techniques found that thickness and lateral dimensions are the structural properties that vary the most. [7] In analogy to the requirement that graphene sheets must be of an appropriate size (i.e., size tuning of the lateral dimension) to suitably interface with biological systems, evidence is accumulating that cell viability and toxicity responses can be modulated by controlling the GBM surface oxygen content. [4,18,19] Although we wish to highlight the biological significance of these three graphene-specific properties, it is important to also consider in toxicological assays other generic evaluation criteria, as is valid for most other nanomaterials. For example, sample impurities in graphene samples might cause nonspecific interference in toxicological studies [4] and, in addition, once GBMs are introduced into a living system, a new biological "identity" may be adopted, as determined by the biomolecules that adsorb to the material surface. [20] Graphene offers a large available surface for the adsorption of proteins and other biomolecules and this should also be taken into account when attempting to determine/resolve the overall health, safety, and toxicity impact of GBMs.

Experimental Methodologies to Measure the Three Classification Parameters

Table 1 summarizes the basic analytical techniques for the measurement of the three fundamental GBM classification parameters of interest. Suitable references are also included which provide a detailed and thorough description of appropriate experimental methodologies to study these properties, and it is important that researchers are welltrained in the appropriate methodologies and incorporate more than one testing method in their characterization efforts.

Summary and Outlook

Consensus is accumulating that clarity in the nomenclature of GBMs is needed. The proposed classification framework, as an initial reference system for graphene biologists/ toxicologists, will help to determine the role of the three physicalchemical properties on the health and safety profile of GBMs. It will contribute to the avoidance of generalizations about the capabilities and limitations of GBMs that can raise false expectations and unnecessary safety concerns. [12] Other benefits that might stem from the adoption of the classification and mapping approach are summarized in Table 2.

There are indeed numerous long-term benefits for all players in the graphene-biological community if diligence is shown by all in characterizing their materials and describing them according to layer number, lateral size, and surface chemistry rather than using ad hoc sample names. [4] Finally, it is important to keep in mind that the set of critical nanosafety evaluation criteria for GBMs will grow in the future in order to reach a consensus on the health and environmental safety risks of graphene smart materials such as functionalized GBMs.

Table 1: Analytical techniques for the classification of GBMs. [a] . GBM-specific property and suitable analytical tools for the classification of GBMs Number of layers (thickness) TEM [21] AFM [21] Raman spectroscopy [21,22] Optical absorbance measurements [23] Lateral size TEM [21] SEM [21] AFM [24] Atomic C/O ratio XPS [13,16] Elemental analysis (ICP-MS) [25] [a] TEM: transmission electron microscopy, SEM: scanning electron microscopy, AFM: stomic force microscopy, ICP-MS: inductively coupled plasma mass spectrometry.

Table 2: Potential benefits associated with adoption of GBM nomenclature.

Peter

  Wick heads the Research Laboratory for Materials-Biology Interactions at Empa, the Federal Laboratories for Materials Science and Technology, Switzerland. He studied and received his PhD in Cell and Molecular Biology from the University of Fribourg (Switzerland). In 2002 he moved to Empa and started his research career in nanosafety. He is a board member of the Swiss Action Plan for Synthetic Nanomaterials and member of the editorial board of the journal Nanotoxicology.

Figure 1 .

 1 Figure 1. Classification grid for the categorization of different graphene types according to three fundamental GBM properties: number of graphene layers, average lateral dimension, and atomic carbon/oxygen ratio. The different materials drawn at the six corners of the box represent the ideal cases according to the lateral dimensions and the number of layers reported in the literature. The values of the three axes are related to the GBMs at the nanoscale, but it is feasible to expand the values to the microscale.

The authors gratefully acknowledge financial support from EU FP7-ICT-2013-FET-F GRAPHENE Flagship project (no. 604391). All authors are members of the EU GRAPHENE flagship project (Work package 2 Health & Environment). We thank AndrØ Niederer (Empa) for assistance with the graphics.