Jean-Francois Grailet

Fabien Tarissan

Benoit Donnet

TreeNET: Discovering and Connecting Subnets

Since the early 2000's, the Internet topology has been an attractive and important research topic, either for developing data collection mechanisms, and for analyzing and modeling the network. Beside traditional aspects of the Internet topology (i.e., IP interface, router, and AS levels), recent researches focused on intermediate promising visions of the topology, namely Point-of-Presence (PoP) and subnets (i.e., a set of devices that are located on the same connection medium and that can communicate directly with each other at the link layer).

This paper focuses on network subnet discovery by proposing a new tool called TreeNET. One of the key aspects of TreeNET is that it builds a tree representing the way subnets are located with respect to each other. This tree allows TreeNET to obtain additional information on the network, leading to better analysis of the collected data. In this paper, we demonstrate the potential of TreeNET through the evaluation of its key algorithmic steps and the study of measurements collected from the PlanetLab testbed.

I. INTRODUCTION

The Internet is made of a vast set of heterogeneous and interconnected entities enabling the communication between millions of machines. Typically, this network is described as a graph where nodes refer to IP interfaces, routers, or autonomous systems (ASes) and edges depict their relations [START_REF] Pastor-Satorras | Evolution and Structure of the Internet: A Statistical Physics Approach[END_REF]. For now fifteen years, advanced mechanisms have been developed to collect data revealing the topology of the Internet at those different levels [START_REF] Donnet | Internet topology discovery: a survey[END_REF]. However, recent researches have suggested to extend the view of the traditional Internet topology to Point-of-Presence (PoP) [START_REF] Shavitt | Geographical Internet PoP level maps[END_REF], [START_REF] Feldman | A structural approach for PoP geo-location[END_REF] and sub-networks [START_REF] Tozal | TraceNET: an Internet topology data collector[END_REF], [START_REF] Tozal | Estimating network layer subnet characteristics via statistical sampling[END_REF], [START_REF] Gunes | Inferring subnets in router-level topology collection studies[END_REF], [START_REF] Tozal | Subnet level network topology mapping[END_REF]. This paper follows this line of research by proposing a new tool named TreeNET dedicated to the Internet topology discovery integrating sub-network information.

A sub-network (or, simply, subnet) refers to a set of devices that are located on the same connection medium and that can communicate directly with each other at the link layer [START_REF] Mogul | Internet standard subnetting procedure[END_REF]. The subnet level is a way to enrich router level maps with subnet level connection information [START_REF] Tozal | TraceNET: an Internet topology data collector[END_REF]. Subnet discovery presents some similarities with alias resolution [START_REF] Keys | Internet-scale IP alias resolution techniques[END_REF]. Indeed, alias resolution follows the goal of aggregating several IP addresses (appearing in various traces) of a router into a single identifier. Similarly, subnet detection aims at identifying multiple links (appearing to be separate) and at combining them to represent their single hop connection medium (pointto-point or multi-access) [START_REF] Gunes | Inferring subnets in router-level topology collection studies[END_REF]. Considering subnet maps instead of classical IP interfaces, routers, or ASes level maps is a way to deepen our understanding of the Internet topology, in particular topological features of ISP networks.

Previously, techniques have been proposed to obtain information on subnets. One can cite for instance IGMP prob-ing [START_REF] Marchetta | Topology discovery at the router level: a new hybrid tool targeting ISP networks[END_REF] that can be used to detect subnets [START_REF] Mérindol | On the impact of layer-2 on node degree distribution[END_REF]. But due to filtering done by operators, it becomes less and less usable in practice [START_REF] Marchetta | Quantifying and mitigating IGMP filtering in topology discovery[END_REF], making this inference technique outdated. The most promising approach proposed recently relies on TraceNET [START_REF] Tozal | TraceNET: an Internet topology data collector[END_REF]. This tool works as traceroute [START_REF] Jacobson | traceroute," UNIX[END_REF] in the sense that it detects subnets on a given path between a source and a destination. Building on this tool, the same authors developed ExploreNET [START_REF] Tozal | Subnet level network topology mapping[END_REF] in order to improve TraceNET by discovering individual subnets rather than subnets on an end-to-end path. ExploreNET also presents techniques for sampling subnets in a targeted domain and inferring their global characteristics (such as mean subnet degree, subnet prefix length distribution, etc.) [START_REF] Tozal | Estimating network layer subnet characteristics via statistical sampling[END_REF]. However, ExploreNET does not provide any guarantee on the soundness of the inferred subnets or any metric to evaluate them. Furthermore, it tends to fragment large subnets into several smaller (and incomplete) ones.

In this paper, we introduce TreeNET, a new tool dedicated to the collection and manipulation of subnet topology information. 1 This tool overcomes the issues mentioned above by introducing a refinement phase and a classification of the inferred subnets for qualitative evaluation purposes. Moreover, TreeNET also introduces a tree-like structure able to show how subnets are located with respect to each other with the help of Paris traceroute [START_REF] Augustin | Avoiding traceroute anomalies with Paris traceroute[END_REF]. Using specific interfaces found in subnets and the way they are located in the network, our tool is also able to achieve router inference through alias resolution techniques, eventually leading to a complete router -subnet representation of the targeted network.

In order to assess the performance of TreeNET, we thoroughly study a private academic ground truth network and several ASes. All networks are analyzed with both TreeNET and ExploreNET for the sake of comparison and we demonstrate that TreeNET provides more accurate results than the state of the art. In addition to this comparative study, we also assess our alias resolution method on a publicly available dataset [START_REF] Madhyastha | iPlane: An information plane for distributed services[END_REF].

The remainder of this paper is organized as follows: Sec. II describes in details TreeNET, our tool for discovering subnetwork topology of a targeted domain; Sec. III evaluates the performance of TreeNET and compares it to the state of the art tool (i.e., ExploreNET); finally, Sec. IV concludes this paper by summarizing its main achievements and discussing potential future research directions.

II. TREENET

This section introduces TreeNET, our new tool for revealing subnets. We first provide a broad overview of how TreeNET works (Sec. II-A), before introducing the vocabulary associated to the tool (Sec. II-B). We also detail in the remaining sections the four different steps of TreeNET, namely the network pre-scanning (Sec. II-C), the subnet inference (Sec. II-D), the tree construction (Sec. II-E), and the router inference (Sec. II-F).

A. Overview

TreeNET is a topology discovery tool that infers the subnets of a targeted network and relies on them to infer the whole topology (at the router and subnet level), or more precisely the whole visible topology (i.e., containing all the interfaces that are responsive to probes). To do so, it follows four steps that we briefly describe in the next paragraphs.

First of all, TreeNET performs a network pre-scanning which consists in listing every potential IP interface of the targeted domain, using its IPv4 prefix as input. All listed interfaces are then probed in order to only consider responsive interfaces during the subsequent steps for the sake of efficiency.

Then, TreeNET moves to the subnet inference step which aims at identifying the subnets inside the targeted domain. These subnets typically encompass all the IP interfaces which were responsive during pre-scanning. To do so, TreeNET relies on the inference mechanisms provided by ExploreNET in order to list all potential subnets. In addition, TreeNET performs refinements over the measured subnets in order to ensure their soundness when they seem incomplete or partial. Both approaches require additional probing, hence the need for filtering only responsive IP interfaces in the first step. The subnet inference step ends when all responsive IP addresses from the previous step have been considered.

Next, during the tree construction step, TreeNET builds a tree depicting the way subnets are located with respect to each other. This tree is built using Paris traceroute [START_REF] Augustin | Avoiding traceroute anomalies with Paris traceroute[END_REF] towards every inferred subnet, as a set of traceroute paths from a same vantage point typically forms a directed acyclic graph (at worst) or a tree (at best). The tree is rooted at the traceroute vantage point and the leaves are the inferred subnets themselves.

Finally, the router inference step relies on the location details obtained thanks to the tree structure to apply alias resolution techniques [START_REF] Keys | Internet-scale IP alias resolution techniques[END_REF], eventually leading to the discovery of routers providing access to the measured subnets.

At the end, the tree with inferred routers describes the full router -subnet topology discovered by TreeNET when targeting the initial domain. The code of TreeNET is freely available at https: //github.com/JefGrailet/treenet.

B. Terminology

From the perspective of a single vantage point, a subnet can be seen as a set of N responsive interfaces (all being part of a continuous block of M hypothetical interfaces) made of three important components, all of them being depicted in Fig. 1. First, the Ingress router refers to the last router crossed by a packet before reaching the subnet of interest. Second, the Contra-Pivot interface is the IP interface belonging to the subnet that is located on the Ingress router (black circles on Fig. 1). Finally, the Pivot interface refers to any other IP interface in the subnet, all located at the same hop count (gray squares on Fig. 1).

By definition, the Contra-Pivot interface is located at the hop count required to reach a Pivot interface minus one. As such, the Contra-Pivot interface demarcates the subnet under exploration. Finally, in order to ease the subnets location, we introduce the notion of Neighborhood as a location bordered by a set of subnets located at, at most, one hop from each other. From a physical point of view, subnets bordering a same neighborhood should be connected through one router or a mesh of Layer-2/Layer-3 devices.

C. Network Pre-scanning

The very first step of TreeNET consists in listing all IP addresses of the targeted domain, either provided as single addresses, either as IPv4 prefixes. After a shuffling step, which prevents TreeNET from probing consecutive addresses during the next steps (to mitigate network delays), each listed address is probed to check its liveness. Multi-threading is used to make this step as fast as possible.

Due to networking issues, some addresses might not reply during this first probing phase. This is why TreeNET conducts a second pre-scanning phase during which the timeout delay used in the first phase is doubled to get as many responsive addresses as possible. An optional third pre-scanning phase can also be conducted.

When a probed address replies within the expected delay, it is saved in a structure we will refer to as the IP dictionary. It stores all responsive IP interfaces and related data, such as the timeout delay which was used when it first replied. All next probes targeting this interface will use this timeout delay to guarantee new responses.

As unresponsive IP interfaces do not appear in the dictionary, they will not be probed again during the next TreeNET steps, such as subnet inference, where all potential IP interfaces of a subnet under exploration are considered, one at a time. Therefore, by listing only responsive IPs with a preliminary multi-threaded step, TreeNET buys time for subsequent algorithmic steps.

D. Subnet Inference and Refinement

After the end of the pre-scanning phase, TreeNET infers all subnets containing the IP addresses in the IP dictionary by relying on the subnet inference techniques implemented in ExploreNET. The algorithm starts by probing a given target address (with ICMP ECHO requests, naked or wrapped in UDP or TCP) and estimating its distance from the vantage point as a TTL value. Then, it builds a small subnet (/31 or /30) which encompasses it, sending additional probes on close IP addresses (e.g., which differs by one bit in the two last bits) with the same TTL as the one required to reach the initial target. This first step also considers adjustments of the TTL value used while probing IP addresses other than the target in case the initial target address was a Contra-Pivot interface.

The next step consists in growing the initial subnet by iteratively decrementing its prefix length while checking that the new addresses are indeed part of it. This verification step involves additional probing during which the TTL of the probe packets varies to confirm the position of the targeted IP addresses. ExploreNET eventually stops growing a subnet in two distinct scenarios. In the first scenario, ExploreNET discovers that a new address is not part of the subnet (e.g., second Contra-Pivot interface, interface located at the Pivot TTL plus one, etc.). In such a case, it increments the subnet prefix length by one and returns it together with the list of its responsive interfaces. The second scenario happens when, at a given iteration, the total amount of responsive interfaces within the new subnet is below a threshold value that depends on the current prefix length. Then, ExploreNET stops iterating and returns the subnet with its prefix length incremented by one and the list of its responsive interfaces. Upon receiving the final subnet as inferred by ExploreNET, TreeNET also merges the result with previously inferred subnet(s) which cover(s) the same address ranges to ensure the uniqueness of each subnet at the end of the inference.

It is important to understand that, when a large subnet lacks of responsive interfaces, ExploreNET tends to fragment it into several smaller subnets containing groups of responsive interfaces with only one of them containing a valid Contra-Pivot interface, meaning that only this subnet can be considered as sound. To overcome this issue, TreeNET introduces a refinement phase which aims at ensuring any inferred subnet features a valid Contra-Pivot interface. The idea of the refinement phase is the following: TreeNET takes subnets that miss a Contra-Pivot and adjusts their sizes in order to find it. This consists in iteratively decrementing the prefix length of the incomplete subnet and probing the new addresses with the TTL that matches the hypothetical hop count of the Contra-Pivot interface. This refinement by expansion stops as soon as one or several Contra-Pivot candidates are found, or when the subnet starts overlapping other measured sound subnets whose TTL to reach Pivot interfaces is different from the one to reach a Pivot in the subnet being expanded. It also stops when the subnet becomes larger than a /20, as no /19 were observed with neither ExploreNET neither TreeNET. The fact that a subnet can have several Contra-Pivot candidates can be due to networking issues (e.g., redirections) or network policies, such as routers having a back-up interface for a subnet in case the first one failed. The absence of visible Contra-Pivot interface is most probably due to networking issues. In a sense, TreeNET applies a best effort policy while refining subnets.

The fact that a subnet can feature a single, several, or no Contra-Pivot motivates the introduction of a classification which can be used to assess the accuracy and soundness of the measurements. It is worth noticing here that IP addresses can respond with TTL that does not match the expected Pivot TTL or Contra-Pivot TTL. We will refer to such addresses as outliers and our classification takes into account such cases. Each subnet is therefore labeled as Accurate (i.e., it features a single Contra-Pivot interface and no outlier), Odd (i.e., it features two or more Contra-Pivot interfaces and/or some outliers), or Shadow (i.e., no valid Contra-Pivot interface could be found, with or without outliers).

Furthermore, when a subnet is classified as Accurate, each missing IP address that was responsive during pre-scanning is added to this subnet in order to have a list of live interfaces as complete as possible for each subnet. Finally, Shadow subnets are expanded until they collide with sound (i.e., Accurate or Odd) subnets at the very end of the subnet inference. The purpose of this last refinement is to obtain an upper bound on their size.

E. Tree Construction

Once the targeted domain has been completely analyzed, TreeNET performs Paris traceroute measurements towards each inferred subnet, using a Pivot interface as destination.

Having routes to every subnet provides knowledge on how they are located with respect to each other. Taking benefit of such an additional information, TreeNET builds a tree rooted at the vantage point and whose leaves are the measured subnets. Each internal node of depth N is labeled with an interface that appears at the N th position in one or several traces. The immediate result of this construction is that internal nodes actually represent Neighborhoods. Moreover, the labels of internal nodes can be used to identify the subnets that act as a link between two routers: one has simply to check that a label belongs to a subnet occurring at the same depth. To illustrate this construction, Fig. 2 shows the same topology as shown in Fig. 1 but as a tree, with the horizontal arrows highlighting the subnets acting as links between two routers.

In order to be faithful to the measured topology, the tree should reduce the impact of routing issues caused by traffic engineering (e.g., load balancing [START_REF] Augustin | Measuring load-balanced paths in the Internet[END_REF]). For example, several subnets sharing the same Ingress router should have routes of the same length with the same last replying interfaces, but differences can still occur on the rest of the routes. As a consequence, the tree could feature several branches for these subnets and partial representation of their Neighborhood, rather than having a single branch at the end of which one can obtain a complete representation of the Neighborhood bordering those subnets. To avoid this situation, TreeNET allows internal nodes to have more than one label in such a way that the Neighborhood information in deeper nodes is not lost. As a result, internal nodes with multiple labels constitute no longer a single Neighborhood but rather a superposition of several Neighborhoods. For the sake of simplicity, we will refer to these nodes as multi-label nodes. Post-processing of the fully built tree can however isolate Neighborhoods of a multi-label node from each other.

The process of the tree construction is fully described in Algorithm 1. Starting with an empty tree, the algorithm inserts sequentially new subnets in two steps. The first one consists in finding the insertion point defined as the deepest internal node that shares a common label (line 11). In TreeNET, this step is efficiently implemented using additional data structures to avoid visiting the whole tree. Once the insertion point has been found, all missing internal nodes (if any) and the leaf corresponding to the subnet are inserted (lines 3 -10). The second step consists in moving from the insertion point to the root of the tree while inserting new labels whenever the route differs from current information stored in the tree (lines 12 -23). In particular, for each node, if the label from the route of the new subnet already appears in another internal node of the tree at the same depth, it is merged with the current node (lines 19 -21). The final result is a tree in which every label should appear only once.

Fig. 3 illustrates the tree construction on a toy example. Given the topology shown in Fig. 3(a), possible Paris traceroute to subnets S 1 , S 2 , and S 3 could be {1, 2, 4}, {1, 3, 5}, and {1, 3, 4, 6} respectively. The insertion of S 1 and S 2 is then rather simple, as Fig. 3 set ← NODESATDEPTH(N , P .getDepth())

19:

for M ∈ set do 20:

if L ∈ M .getLabels() then 21:

P .merge(M )

22:

P ← P .getParent() 23:
return is obviously the node having the label 4. As the parent node does not have the label 3, such a label is added; however, label 3 already appears in the tree, therefore the branch is merged with the node containing both labels 2 and 3. In the final tree, all non-null (i.e., not 0.0.0.0) labels appear only once.

As implied in the previous paragraph, the routes obtained with Paris traceroute are not always complete, i.e., they feature 0.0.0.0 interface(s) along the way. As TreeNET does not consider these labels while looking for the insertion point, this leads to one branch per distinct interface following a 0.0.0.0 interface. While this does not affect deeper internal nodes, this can lead to splitting a large internal node into several ones. Specially when the interface is labeled as 0.0.0.0 due to a delay or a black-listing of the vantage point by that interface, preventing it from replying to any subsequent probe. This typically occurs with the first hops to a remote network (which are often common to all routes): some routes will feature the proper interface(s) while others will not.

To mitigate this issue, TreeNET always starts building the tree using only subnets that feature a complete route (i.e., with no occurrence of 0.0.0.0). Then, before inserting any subnet with an incomplete route, TreeNET finds the most similar route already stored in the tree and replaces 0.0.0.0 interface(s) of the incomplete route with the interface(s) at the same index(es) in the selected route.

F. Router Inference

A fully built tree provides a good knowledge of the topology, as it gives an idea of how many interfaces border an internal node, which is either a Neighborhood, either a superposition of Neighborhoods. Given #L the amount of labels of a node, #S the amount of children subnets, #I the total amount of labels from child internal nodes, and #C the amount of crossed subnets (i.e., subnets which contain the label of a child internal node), the amount N of interfaces an internal node is given by

N = #L + #I + #S -#C. (1)
The amount of labels #L can be assimilated to the number of interfaces through which packets enter the Neighborhood(s), while #I + #S -#C refers to the number of outgoing interfaces.

Not only the tree provides an idea of the number of interfaces of each internal node, but it also gives some of these interfaces. The labels themselves are interfaces, but moreover, subnets classified as Accurate during subnet inference feature a valid Contra-Pivot interface which, by definition, is the interface of a router. Odd subnets also feature at least one valid Contra-Pivot. Therefore, for each internal node, one can list all labels and each Contra-Pivot of each child Accurate or Odd subnet. Then, one can use an alias resolution technique on them to infer one or several routers. After that, internal nodes do not need to be abstracted as Neighborhoods (or superimpositions) any longer, and one can build a full routersubnet topology of the measured network. The alias resolution also helps to disambiguate multi-label nodes, as interfaces of routers belonging to distinct (superposed) Neighborhoods should never be associated together.

In TreeNET, the router inference consists in a combination of three different alias resolution techniques: Ally [START_REF] Spring | Measuring ISP topologies with Rocketfuel[END_REF], IP-ID counter velocity check (which is reminiscent of Radar-Gun [START_REF] Bender | Fixing Ally's growing pains with velocity modeling[END_REF]), and reverse DNS association.

For every interface of an internal node/Neighborhood, TreeNET collects i IP-IDs (i is at least three) and evaluates the wall clock time (in microseconds) between the acquisition of each ID, leading to i -1 delays. While the wall clock time might not be necessarily faithful to the delay between the generation of two IP-IDs on a remote device, it is a reasonable and exploitable estimation. In addition to the IP-IDs and delays, the reverse DNS for each IP address is also retrieved when available.

Once all the aforementioned data has been collected for every interface, the association process starts. When IP-IDs and associated delays are available, TreeNET first considers association by Ally. The idea of Ally is very simple: one probes a first interface, retrieves an IP-ID x, then obtains another IP-ID y from a second interface, and a third ID z from the first one. If the inequality x < y < z with z -x being reasonably small is verified, one can assume both probed interfaces actually belong to the same router. Therefore, in the context of TreeNET, one just has to find a triplet of IP-IDs from two distinct interfaces which form a succession to use Ally. To locate IP-IDs chronologically, each collected ID has an associated token, an integer unique to each probe that is given by a counter incremented each time a token is drawn.

However, the IP-ID counters can evolve quite fast, therefore mitigating the efficiency of Ally in many cases. To overcome this issue, the second technique implemented in TreeNET rather estimates the velocity of each counter for each interface (the three IP-ID mentioned above) and associates interfaces together when their velocity is similar, which is the same idea as RadarGun [START_REF] Bender | Fixing Ally's growing pains with velocity modeling[END_REF]. This is why delays between getting each IP-ID are being collected.

However, the velocity of a counter is not constant and fluctuates, and to model this, TreeNET does not compute a single velocity per interface but rather a range of velocities, with a velocity being computed for every pair of consecutive IP-IDs. Moreover, as IP-ID counters are encoded on 16 bits, they can rollover on a regular basis, and it is not unlikely to have two or more rollovers for interfaces belonging to routers dealing with large traffic. For every pair of consecutive IP-IDs (denoted as i and i + 1 and the delay between those IP-IDs is denoted d i ), we consider a variable x i to model the amount of rollovers. In Fig. 4, we illustrate the data involved in our alias resolution technique based on IP-ID counter velocity and the variables for each pair of consecutive IP-IDs.

To be able to compute coherent velocities, one must find a value for every x i such that the velocities are reasonably close to each other. Our approach consists in assigning a value from 0 to a maximum (e.g., 50) to x 0 and, for each value, resolving i -2 equations to find every x i with i being greater than 0. The equation is the following

i 1 -i 0 + 65535 × x 0 d 0 = i i+1 -i i + 65535 × x i d i . ( 2
)
As it is possible to have the inequality i i+1 < i i due to a rollover between the first IP-ID of the pair and the second one, we replace -i i by +(65535-i i ) when this occurs to accurately express the amount of times the counter was incremented.

Since it is extremely rare to find an integer, non-zero solution for every x i , we rather solve such equations in the real domain and round the results afterwards. If all solutions are positive and if the rounding error (i.e., the difference between the rounded result and the real value) is below a threshold (e.g., 0.35), the rounded solutions are kept, otherwise the next value for x 0 is being considered until the maximum. If the maximum value is reached without finding a solution, we consider the counter to have an infinite velocity, represented by the range [0, 65535].

If an integer value is found for every x i , the velocities are obtained with the following formula:

v i = i i+1 -i i + 65535 × x i d i . (3)
Of course, if i i is greater than i i+1 , the term -i i is again replaced with +(65535 -i i ).

The final step consists in retrieving the maximum and minimum velocity obtained for the IP addresses. Afterwards, interfaces are associated if their respective ranges of velocity overlap. As we observed several ranges being very close to each other without overlapping, we added a tolerance value (e.g., 0.3) which slightly extends the largest range such that it overlaps close ranges. Finally, it is worth noting we always associate together interfaces for which the velocity is computed as infinite (i.e., [0, 65535]).

If neither Ally nor the velocity range technique can be used, reverse DNS association is considered. It is worth noting that if IP-IDs are available and if the two previous techniques rejected the association, reverse DNS is not considered. In other words, reverse DNS is the last resort technique. The technique itself is very simple: splitting the DNS of two IP interfaces at dots, they will be associated if and only if they have the same amount of components and if only the first ones differ between both IP addresses. We did not elaborate our reverse DNS technique further because of the need for additional inputs, such as the naming conventions found in a particular network.

III. EVALUATION

In this section, we evaluate the performance of TreeNET. We first provide preliminary results for our three alias resolution scheme (Sec. III-A) and, next, we compare subnet inference of TreeNET with ExploreNET (Sec. III-B) on a ground truth and several ASes. We also mention some preliminary results which could guide future study of the measured ASes (Sec. III-C). Subnets and aliases collected during our measurement campaign are freely available: https:// github.com/JefGrailet/treenet/tree/master/ v2/Measurements

A. Alias Resolution

To assess our alias resolution scheme described in Sec. II-F, we relied on a dataset provided by iPlane [START_REF] Madhyastha | iPlane: An information plane for distributed services[END_REF]. It is made of a list of 57,806 routers with their aliases as observed in iPlane traceroute. Aliases are determined by using standard IP-ID technique and identical return TTLs when probed at the same time. It should be noted that this dataset is updated every two months and that our GitHub repository provides the dataset which was available at the time of our measurements.

For each alias (given as a list of interfaces), we run our resolution technique and define an accuracy rate, i.e., the size (i.e., amount of interfaces) of the largest alias inferred by TreeNET for this list divided by the number of responding interfaces from that list. As a consequence, a value of 1 means that we obtain the same results as iPlane with respect to responsive interfaces. On the contrary, a value of 0 means that we are not able to identify the listed interfaces as aliases at all. Measurements were done on November 19 th , 2015, collecting four IP-IDs for each responsive interface.

On the set of 57,806 routers, 26% of them were not responding to our probes. No accuracy rate has been computed on those routers. The accuracy rate for the remaining 74% of the routers is given, as a cumulative distribution function, on Fig. 5. The most important result here is that, in 55% of the cases, our alias resolution provides the same results as the iPlane dataset. The second main result is that, for a bit more than 70% of the dataset, we have an accuracy rate of at least 50%. Those results are promising and we leave as a future work a better characterization of our alias resolution technique and potential improvements of it. In particular, we plan to elaborate on the amount of collected IP-IDs and the effects of other parameters of our velocity-based technique we previously mentioned.

B. Subnet Inference

In order to evaluate the subnet inference proposed by TreeNET with respect to ExploreNET, we implemented a slightly edited version of ExploreNET using the same input/output schemes as TreeNET and targeted different ASes as well as a ground truth network (an academic network for which we have access to the actual topology -access to that network topology is, obviously, not allowed outside the campus) with both of them.

We decided to conduct measurements on three ASes: AS224, AS5400 and AS30781. The first two are comparable regarding the amount of hypothetical IP addresses (a bit more than one million in both cases) but have a different role in the Internet topology: AS224 is a stub AS (i.e., all traffic coming in and out of it goes through a single path) while AS5400 is a transit AS (i.e., it acts as a link between other ASes). AS30781, on the other hand, is another transit AS but of a much smaller scale (with a maximum of 45,824 hypothetical IP addresses), which is interesting for a comparison with AS5400. The datasets we obtained from them are available on https://github.com/JefGrailet/ treenet/tree/master/v2/Measurements.

In the case of the ground truth, we were able to check the results with a network administrator, and discovered that 86.3% of our measured subnets were correct in terms of prefix with respect to the actual topology, the problematic results being caused by very specific cases. These difficult cases notably included loop-back interfaces from distinct subnets (sometimes /32 subnets) whose TTL were similar and for which the IPv4 addresses were consecutives, and were therefore considered to be on the same subnet. The inferred routers were also confirmed by the actual network, therefore demonstrating the relevancy of the tree structure and proving again the accuracy of our alias resolution scheme.

To assess the soundness of subnets measured by TreeNET, we introduce the notion of credibility of a subnet. A subnet is considered as credible if less than 10% of its listed interfaces are Contra-Pivot candidates and more than 70% of them are Pivot interfaces, as we consider a subnet cannot be sound if more than 20% of its interfaces are outliers. These numbers are however arbitrary and could be adapted for specific networks where the amount of outliers is assumed to be high. The purpose of this metric is to evaluate if an Odd subnet is a good measurement, an Accurate subnet being de facto credible while Shadow subnets are never considered as credible.

Finally, we also use two additional metrics on datasets obtained through ExploreNET: redundancy and encompassed ratios. The redundancy ratio denotes how many subnets in the datasets are equivalent with previously listed subnets, since ExploreNET does not merge similar subnets like TreeNET does. The encompassed ratio, on the other hand, quantifies how many subnets inferred by ExploreNET are strictly smaller than overlapping subnets obtained by TreeNET, in order to check if the latter handles large subnets better than the former.

Our results are presented in Table I. One can immediately notice a striking improvement due to TreeNET. It is indeed remarkable how TreeNET is able to infer a smaller amount of subnets than ExploreNET while covering much more addresses and having a high proportion of Accurate subnets. The ratios of incomplete, redundant, and encompassed subnets for each network further demonstrate that the refinements operated by TreeNET over the results of ExploreNET drastically improves the inferred subnets regarding both credibility (in the broad sense) and coverage of the measured networks.

Furthermore, the introduction of Odd subnets in TreeNET overcomes a limitation of ExploreNET: indeed, the latter assumes that a subnet necessarily owns a single Contra-Pivot interface. Therefore, ExploreNET can stop the inference when it discovers two potential Contra-Pivot interfaces at once. Unfortunately, this prevents it from properly inferring a large subnet when there is, for example, a back-up Contra-Pivot interface. It also tends to ignore outliers (e.g., an IP interface located at the Pivot TTL + 1, which can occur due to specific network policies), that could appear in measurements conducted by TreeNET due to subnet merging. Thus, not only the refinements help to find sounder subnets, but they also relax the definition of a subnet to some extent and allows the discovery of more exotic network configurations.

C. Preliminary results

Even if the focus of this paper is the description and evaluation of TreeNET, we can already provide directions for future analysis of the networks measured with it. In particular, the datasets we collected can be analyzed to compute the distribution of the subnet prefix lengths in each AS and our ground truth. A first look at Fig. 6 already highlights an interesting property: the proportion for each prefix length varies from one network to another, and while /31 and /30 subnets are inevitably the most common ones (as already observed with ExploreNET [START_REF] Tozal | Subnet level network topology mapping[END_REF]), other prefix lengths are not used in the same manner by each network.

For example, /24 subnets are particularly common in our dataset from AS224, which is a stub AS. An interesting perspective for future research would be to compare the results obtained by TreeNET on several stub ASes to determine if the proportion of /24 subnets is a common feature of stub ASes or an AS224 specificity.

However, an in-depth analysis of the data would require more metrics and modeling formalisms suited for routersubnet topologies, which are left for future work.

IV. CONCLUSION

In this paper, we introduced TreeNET, a new tool collecting and manipulating subnet topology information to discover the router -subnet topology of a target network. Using as a basis ExploreNET, a state of the art subnet inference tool, TreeNET adds subnet refinement mechanisms along with a tree-like structure which not only gives an overview of the network but also eases router discovery via alias resolution techniques.

We were able to demonstrate the benefits of TreeNET regarding subnet inference through a comparative study with ExploreNET on a ground truth network and several ASes. We also obtained promising results for the alias resolution scheme currently implemented in TreeNET, both on our private ground truth and a publicly available dataset provided by iPlane. The datasets we obtained from the mentioned ASes and the aliases list provided by iPlane we used are publicly available on https://github.com/JefGrailet/ treenet along with the sources of TreeNET.

Future works involve in-depth evaluation of TreeNET (in particular the efficiency of the pre-scanning phase and the alias resolution scheme compared to RadarGun), large-scale measurement campaigns and in-depth study of our datasets through modeling formalisms suited for router -subnet topologies. We are also planning to use TreeNET to elaborate Layer-2 devices inference techniques in the long term.

Fig. 1 .

 1 Fig. 1. Illustration of Contra-Pivot, Pivot, and Neighborhood notions.

Fig. 2 .

 2 Fig. 2. Topology from Fig. 1 seen as a tree -horizontal arrows highlights the subnets acting as links between two routers.

3 : 4 :← N 5 :

 345 (b) shows. Fig. 3(c) and 3(d) illustrates how the insertion of S 3 occurs. The insertion point Algorithm 1 Insertion of a subnet in the tree Require: N , root node of the tree 1: procedure INSERT(Node N , Subnet S) if N .getNextChild(R[N .getDepth() + 1]) == ∅ then Prev for i ← N .getDepth() : R.getLength() do

Fig. 3 .

 3 Fig. 3. Example of the tree constructed by Algorithm 1 on a toy example.

Fig. 4 .

 4 Fig. 4. Schematic view of the data used for the velocity range technique.

Fig. 5 .

 5 Fig. 5. Preliminary performance results for our alias resolution scheme.

/Fig. 6 .

 6 Fig. 6. Distribution of the subnet prefix length in the observed networks.

  TreeNET and ExploreNET for several ASes and our ground truth.

		AS224		AS30781		AS5400		Ground truth
		TreeNET ExploreNET	TreeNET ExploreNET	TreeNET ExploreNET	TreeNET ExploreNET
	# hypothetical IPs	1,115,392		45,824		1,385,472		5,888
	# inferred subnets	3,053	68,635	1,195	6,606	1,769	7,398	124	1,024
	# covered IPs	446,750	200,021	21,408	8,228	104,468	11,055	3,956	1,818
	Accurate subnets	69.9%	36.7%	76.1%	45.6%	74.0%	39.8%	75.8%	45.3%
	Odd subnets	23.8%	/	20.0%	/	12.3%	/	17.7%	/
	Shadow subnets	6.3%	/	3.9%	/	13.7%	/	6.5%	/
	Credible subnets	88.2%	36.7%	88.0%	45.6%	79.8%	39.8%	84.7%	45.3%
	Incomplete subnets	/	63.3%	/	54.4%	/	60.2%	/	54.7%
	Redundant subnets	/	56.3%	/	57.7%	/	42.8%	/	49.9%
	Encompassed subnets	/	72.5%	/	66.3%	/	63.0%	/	54.3%
				TABLE I
		Comparison between

Available at https://github.com/JefGrailet/treenet. Data discussed in this paper is also available at https://github.com/ JefGrailet/treenet/tree/master/v2/Measurements

ACKNOWLEDGMENTS

This work is partially funded by the European Commission funded mPlane ICT-318627 project.


Fabien Tarissan
email: fabien.tarissan@ens-cachan.fr

Yannis Panagis
email: ioannis.panagis@jur.ku.dkurska.sadl@jur.ku.dk

Urška Šadl

Selecting the cases that defined Europe: complementary metrics for a network analysis

Keywords: Citation networks, Directed acyclic graphs, Relative in-degree, Average longevity, Authority scores, European Court of Justice

Do case citations reflect the "real" importance of individual judgments for the legal system concerned? This question has long been puzzling empirical legal scholars. Existing research typically studies case citation networks as a whole applying traditional network metrics stemming from graph theory. Those approaches are able to detect globally important cases, but since they do not take time explicitly into account, they cannot provide a comprehensive account of the dynamics behind the network structure and its evolution.

In this paper we provide such a description, using two node importance metrics that take time into account to study important cases in the Court of Justice of the European Union over time. We then compare cases deemed as important by the metrics, with a set of 50 cases selected by the Court as the most important (landmark) cases.

Our contribution is twofold. First, with regard to network science, we show that structural and time-related properties are complementary, and necessary to obtain a complete and nuanced picture of the citation network. Second, with regard to the case law of the Court, this study provides empirical evidence clarifying the motivation of the Court when selecting the landmark cases, revealing the importance of symbolic and historical cases in the selection. In addition, the temporal analysis sheds new light on the network properties specific to the landmark cases that distinguishes them from the rest of the cases. We validate our results by providing legal interpretations that sustain the highlights provided by the proposed network analysis.

I. INTRODUCTION

The Court of Justice of the European Union (the Court) is often considered as the most powerful international court in the world [START_REF] Alter | The new terrain of international law: Courts, politics, rights[END_REF]. Legal scholars have often emphasized its key role in the European integration process, typically relying on a handful of landmark judgements in which the Court defined the European legal order citealec.

When the Court in 2004 at a point of the biggest enlargement of the European Union from 15 to 25 members selected its "50 signature cases" for the newcomers, its selection closely matched the scholarly selection. These cases are considered as important pre accession case law 1 (also referred to as landmark cases) and are publicly accessible on the Court's website. By contrast, the selection criteria are not accessible to the general public. Internal documents of the Court, however, indicate that the main criteria were first, whether the judgements were unanimously recognized as leading cases, structuring the legal order of the Community, and second, generally considered as important references in the area. So far, the relevance of those criteria was not examined empirically because it was simply assumed that these judgements were the landmark judgements with continuous relevance for European law.

The purpose of this paper is precisely to investigate this question by relying on the graph of citations extracted from the judgements. Indeed, as many real-world networks, the structure of case law networks can be analysed using graphs, where nodes stand for the judgements and links depict the connections between them, that is, the references to previous judgements. This induces a directed acyclic graph (DAG) on which one can rely to detect important legal decisions. Although recent, this approach has attracted considerable attention and has been applied to a series of jurisdictions [START_REF] Smith | The Web of Law[END_REF]- [START_REF] Tarissan | Analysing the first case of the international criminal court from a network-science perspective[END_REF].

In this context, the fact that judgements rely on former ones to motivate their decisions led the community to focus in particular to degree-related properties. The intuition is that an important judgement should be widely referred to, thus leading to a greater degree than other judgements. In this regard, the oft-used authority score, initially proposed by Kleinberg in the context of web searching [START_REF] Kleinberg | Authoritative sources in a hyperlinked environment[END_REF], has been widely used to identify the landmark decisions and gain a general overview of the structure of the case law of individual courts. To further refine the analysis and develop dedicated metrics accounting for the moment at which the judgements are issued (that is, at the time when the cases are decided) Tarissan and Nollez-Goldbach in a more recent study [START_REF] Tarissan | Analysing the first case of the international criminal court from a network-science perspective[END_REF], [START_REF] Tarissan | Temporal properties of legal decision networks: A case study from the international criminal court[END_REF] proposed to rely on the temporal properties induced by the DAG structure. The study showed that this approach provides an alternative point of view of what is considered as an important decision through time and what can be labeled as rising star decisions that might become important reference points in the future.

Following these promising results, this paper investigates whether the selection of landmark cases by the Court matches an objective selection that relies on citation-based properties, using network analysis. In addition, we assess for the first time the relevance of the authority score compared to timerelated properties. Rather than confronting the two notions, the analysis reveals first, that the points of view provided are complementary and second, that by combining them it is possible to produce a more precise picture of the evolution of the importance of individual cases over time. This further provides a deeper and more nuanced insight into how international courts develop international law and the role that the landmark cases play in this process.

The remainder of the paper is organised as follows. First we present the existing work related to network analyses in the context of law (Section II) before providing the background necessary for the study (Section III). Then we turn to the network analysis, relying first on a static point of view (Section IV) before investigating how the evolution of the importance of the cases over time impact the analysis (Section V). Finally, we conclude the paper by laying the foundations for future research (Section VI).

II. RELATED WORK

Several previous studies combined law and computer science, to either model legal reasoning or to extract information from legal databases. Most recently, a new line of research has emerged, which considers legal decisions as complex networks [START_REF] Smith | The Web of Law[END_REF]. This originated from studies that analysed the evolution of the jurisprudence of the American Supreme Court through direct references (citations) between judgements [3]- [START_REF] Clough | Transitive reduction of citation networks[END_REF]. The approach has then been applied to various national settings, ranging from the Canadian [START_REF] Neale | Citation Analysis of Canadian Case Law[END_REF] to the Italian [START_REF] Agnoloni | The Case Law of the Italian Constitutional Court between Network Theory and Philosophy of Information[END_REF], the Dutch [START_REF] Winkels | Determining Authority of Dutch Case Law[END_REF], and the French [START_REF] Bourcier | Codification, law article and graphs[END_REF], [START_REF] Boulet | A network approach to the french system of legal codes -part i: analysis of a dense network[END_REF] legal systems.

With regard to international courts, Derlen et al., and Mirshavalad et al., [START_REF] Koniaris | Network Analysis in the Legal Domain: A complex model for European Union legal sources[END_REF], [START_REF] Derlen | Goodbye van gend en loos, hello bosman? using network analysis to measure the importance of individual cjeu judgments[END_REF], [START_REF] Mirshahvalad | Significant communities in large sparse networks[END_REF] applied network analysis to the case law of the Court of Justice, presenting the application of PageRank [START_REF] Brin | Reprint of: The anatomy of a large-scale hypertextual web search engine[END_REF] and community detection techniques [START_REF] Mirshahvalad | Significant communities in large sparse networks[END_REF] to get an overview of the structure of the Court's network. The same authors in [START_REF] Koniaris | Network Analysis in the Legal Domain: A complex model for European Union legal sources[END_REF] examined the structural properties of the case law and the legislative network of the European Union without quantifying the importance of individual nodes-cases. Lupu and Voeten [START_REF] Lupu | Precedent in international courts: a network analysis of case citations by the european court of human rights[END_REF] studied the case law of the European Court of Human Rights using hubs and authorities as proxies for statistical analysis of the case law properties. Tarissan and Nollez-Goldbach [START_REF] Tarissan | Analysing the first case of the international criminal court from a network-science perspective[END_REF], [START_REF] Tarissan | Temporal properties of legal decision networks: A case study from the international criminal court[END_REF] conducted research on the International Criminal Court, and Pelc [START_REF] Pelc | The politics of precedent in international law: A social network application[END_REF] on the Appellate Body of the World Trade Organisation. Puig provided another interesting application of network analysis to international dispute resolution (without, however, considering individual decisions) [START_REF] Puig | Social capital in the arbitration market[END_REF], focusing on arbitrator patterns and importance of individual arbiters in the field of international arbitration.

To the best of our knowledge, this study is the first that a) provides a temporal perspective in the analysis of the case law of the European Court of Justice and b) combines structural (in-degree, authority scores) and time related (relative indegree, average longevity) properties.

III. DATASET AND METHODOLOGY A. Network analysis

It is common to represent a citation network as a directed graph G = (V, E). In our context, a node v ∈ V represents the judgement in a case -identified by its CELEX number2 and a link (u, v) ∈ E between two nodes u and v exists if the case u cites the case v. Although this representation does not directly account for temporal properties, temporal aspects are encoded in this formalism since time induces a natural acyclic property; a judgement cannot refer to a future judgement.

Depicting a citation network as a directed graph enables the analysis of its structure. To this purpose, the standard approach consists entails relying on the number of times a node is cited by another one. More formally, if v ∈ V is a node, we denote by

C in (v) = {u ∈ V | (u, v) ∈ E} the set of decisions that cite v and we call deg in (v) = |C in (v)| the in-degree of v.
Intuitively a high in-degree indicates that a decision is used to ground many future decisions thus quantifying its importance. In the context of judicial networks, a variant of this notion is also referred to as the authority score [START_REF] Fowler | The authority of Supreme Court precedent[END_REF], [START_REF] Winkels | Determining Authority of Dutch Case Law[END_REF] introduced by Kleinberg [14] in the context of web searching.

However, the acyclic property led to the criticism of degreerelated properties for being strongly biased towards old nodes that have obviously more opportunities to get cited. In the example of Fig. 1 for instance, although D1 attracts more citations than D4 (leading to the interpretation that D1 is more important than D4), one could argue that D4 is actually more important as it has attracted all possible citations it could get from the subsequent cases.

To overcome this issue, Tarissan and Nollez-Goldbach [START_REF] Tarissan | Temporal properties of legal decision networks: A case study from the international criminal court[END_REF] proposed to put this absolute value into perspective by dividing the number of citations by the number of citations that a node could have possibly had. Formally, let date(v) the date at which v ∈ V is issued and Future(v) = {u ∈ V | date(u) > date(v)} the set of decisions issued after v, one defines the relative in-degree of v as:

deg rel in (v) = deg in (v) |Future(v)|
The authors of [START_REF] Tarissan | Temporal properties of legal decision networks: A case study from the international criminal court[END_REF] also highlighted that another aspect might help identify important decisions. Indeed, several stud-ies [START_REF] Fowler | The authority of Supreme Court precedent[END_REF], [START_REF] Whalen | Modeling Annual Supreme Court Influence: The Role of Citation Practices and Judicial Tenure in Determining Precedent Network Growth[END_REF] highlighted the fact that, while most decisions cease to be cited after a while (they depreciate), landmark decisions depreciate at a slower rate (they tend to be cited for a longer period). Relying on this observation, they proposed to use the time between the date of two related decisions as an indicator of the importance of the decision being cited.

More formally, if we define the temporal distance of a link (u, v) ∈ E as the value td(u, v) = d(u)d(v), then one can define the average longevity lg(v) of v as the average temporal distance over all links towards v:

lg(v) = u∈Cin(v) td(u, v) deg in (v)
The intuition is that a high average longevity of a decision means that this decision is being used to ground future decisions as time passes, thus indicating that it is a good candidate for a landmark decision.

B. European Court of Justice

In this study we use the case law of the Court of Justice, which is publicly available. The Court is the main judicial institution in the European Union, whose task is to ensure that in the interpretation and the application of the European Treaties, the law is observed (Article 19). The Court is composed of 28 judges, one from each Member State, and 11 Advocates General, who assist it. It decides approximately 600 cases per calendar year.

The dataset we used consists of 5 599 judgements and Court Opinions from the Court of Justice of the European Union, issued from 1954 until March, 17 th 2002, day when the 50 landmark cases were released. All case law is available at EUR-Lex, the official portal of European Union law 3 . By taking into account the citation information published by EUR-Lex, we built the corresponding case-to-case citation network, which in turn consists of all the aforementioned cases as nodes and 13 609 edges-case citations. In addition, we extracted the following information:

1) The 50 landmark decisions: Internal documents of the Court suggest that the Research and Documentation department prepared the list of 50 cases of the Court and the General Court after consultations with the presidents of both courts, and that the selections were approved by the Presidents of the Courts4 . To be included in the selection the judgments had to be unanimously recognized as leading cases, structuring the legal order of the Community, and generally considered as important references in the area. Note that the frequency of citations in subsequent judgements was not the only factor 5 .

Also, the Court provided two lists, distinguishing cases before 2001 from cases after 2001. In this study, we focus exclusively on the former, which contains the best known cases in European law.

2) Classification of the Court: When the Court decides a case, the Research and Documentation Directorate -supervised by reporting judges in individual cases -assigns it one or more classifications, depending on the legal questions considered in the case 6 . The objective is to facilitate the work of the Court as well as research. The classifications are fed into several databases, including EURLEX, the main online gateway to EU legislation and case law 7 . They are available on the official website, where they are stored as bibliographical information under the category subject matter (that is as metadata). The metadata contains several subject matters and we use the primary classification that designates the content of the case most generally, to avoid too many subgroups. We correct for that classification if the subsequent keywords assigned to the case provide a closer description of the content of the case (that is, when they all fall under the second most general classification, indicating that the primary classification might not be the most general or misguided).

3) Additional classification: As an alternative to the Court's classification, we systemmatized the landmark cases on the basis of close reading, and existing literature, which investigated the different aspects of landmark decisions [START_REF] Sadl | The role of effet utile in preserving the continuity and authority of european union law:: Evidence from the citation web of the preaccession case law of the court of justice of the eu[END_REF], [START_REF] Maduro | The past and future of EU law: the classics of EU law revisited on the 50th anniversary of the Rome Treaty[END_REF]. In particular, the cases are systematized on the basis of their intrinsic properties, such as: (1) their practical and symbolic importance. For instance, according to this criterion cases like that the literature considers as "fundamental" will be classified as cases with mainly symbolic importance (referred to further as symbolic), while other, which are discussed for their relevance for solving concrete problems, will be classified as cases that had primarily practical importance (practical);

(2) the Courts law-making initiative (establishment of new judge-made principles vs. interpretation of Treaty Articles). This category divides historic cases in two subcategories, distinguishing between outcomes that were not strictly based on the Treaty Articles (judge made), and cases, which were grounded in the interpretation of concrete Treaty Articles (treaty); (3) juridical consequences and effects (did the Court limit or mitigate the consequences of its rulings in practice (yes) or not (no)); (4) according to their age (old, decided between 1954 and 1979 vs. new, decided between 1980 and 2001); and (5) the subject of protection, which can be the individual (referred to further as category A), the authority of the legal order (category B), the functioning of the internal market (category C), and the general principles of EU law (category D).

C. The network under study

To juxtapose the vision of the Court to the objective measures of case importance on the basis of network analysis, we applied the following process: from the dataset, we extracted all the citations from all cases until March 17 th , 2002, constructed the network of citations to precedent, computed on it the different metrics described in Section III-A, and filtered out all cases decided after 2001 in order to simulate the fact that those cases were not taken into account in the selection of the 50 landmark cases.

IV. STATIC ANALYSIS

In this section, we investigate whether the selection made by the Court of Justice of the European Union when selecting the 50 landmark cases in 2002 matched the point of view provided by the network analysis of the citation process. To do so, we compare the list of the 50 landmark cases of the Court to the list of the 50 most important cases according to network analysis, with respect to the different metrics presented in Section III-B. The rationale is the following: if the criterion for selecting the 50 cases is objectively the importance of the judgements measured by its ability to serve as a grounding base for many future decisions, then this should be reflected in the analysis of its citation patterns.

We start by conducting the analysis on the complete network (Section IV-A) before focusing on the classification provided by the Court (Section IV-B).

A. Categories

Table I presents the results obtained by taking into account all the cases. Absolute values in Table 1 stand for the number of common cases 8 between the list made by the Court and the one identified by network analysis (row entitled Total in the table). In order to better understand the impact of each metric, we also provide the distribution of the common cases according to the additional classification presented in Section III-B3. The percentage stands for the proportion of common cases in each category. For example, if we look at the category "Age", 41% of the top 50 cases based on the indegree that are common with the 50 landmark cases, belong to the category "old" whereas the rest 59% to the category "new".

Table I shows that network analysis and the Court's selection match poorly. The most efficient property in this regard is the simple in-degree but it only succeeds in detecting 17 landmark cases (33%). In addition, if we use all four properties, we only increase this amount to 23 (46%). Obviously, the Court does not solely rely on the objective importance of cases, which confirms the relevance of the question of hidden criteria made by the Court to pick out those cases.

With regard to the different aspects highlighted by the computed metrics, one can see that, as underlined in Section III-A, relative in-degree and average longevity provide a contrasting view. Relative in-degree focuses on recent cases (80% of detected landmarks are recent) while average longevity focuses on old cases (100% of detected landmarks are old). This last argument is strengthened by the fact that old cases are not numerous in the selection of the Court. Similarly, one can observe that in-degree is biased towards old cases, retrieving 8 this is equivalent to the recall used in Information Retrieval contexts.

53% of old landmark cases, while detecting only 30% of the new ones.

From a legal perspective, the results obtained on the classification used in this study are compelling. If one focuses for instance on the importance of the landmark cases, it is remarkable that most network metrics (if not all) capture landmark cases that have or had a practical importance (they solved concrete legal issues), leaving the cases that had a more symbolic character (they did not solve concrete problems but defined the nature of the legal system and its fundamental features) undetected (although this is alleviated by the fact that practical cases make up more than 80% of listed cases). This is an interesting finding since it provides empirical evidence that the motivation of the Court when selecting the landmark cases was to take into account cases that are not widely used and cited but important on a more general or principled level.

B. Classification of the Court

One limitation of the analysis presented above is that it aggregates all information contained in the dataset and puts at the same level all topics addressed by the Court. In order to provide a more nuanced picture of which cases are important according to their main subject matter as explained in Section III-B2, we extracted the sub-networks according to the classification provided by the Court 9 and conducted a similar study as above. Note that this process has a strong impact on the structure of the networks since each sub-network now only contains links between its nodes, thus discarding citations between cases related to different topics.

Results are presented in Table II. Each category is given with the number of n landmark cases selected by the Court (1st column). The remaining columns indicate the number of common cases in the n most important cases with respect to the different metrics. For instance, since the topic "Institutions" contains 6 landmark cases listed by the Court, we computed how many of those 6 cases are present in the 6 most important cases according to network analysis (3 for in-degree, authority and relative in-degree, only 2 for average longevity).

Table II presents interesting outcomes. First, it shows that taking the legal context of a case into account before quantifying its importance impacts the results. In that regard, it is remarkable that landmark cases related to the "Free movement of goods" and "Institutions" are well captured by all different metrics. Almost 50% of related landmark cases listed by the Court are indeed identified as important by the network analysis.

By contrast, it is surprising that landmark cases related to other fields, such as "Competition" for instance, are not listed as the most important decisions within their categories. This of course depends to a large extent on small the size of the category, in the 50 cases' sample. The categories "Brussels Convention", "External relations" and "Taxation" are not captured by the metrics but they are also poorly represented in the selection of landmark cases, thus leading to inconclusive results.

In order to have a better view of what impact the legal context has on the analysis, we also computed the ranks of individual cases in the complete network and compared them to the rank in their corresponding sub-networks. Results are presented in Table III below. The results presented in this table contrast with the ones of Table II. When focusing in particular on the 10 most important cases, it is clear that the analysis greatly benefited from the adjustment of the computations to include their most relevant legal context. Such additional information increased the importance of the cases with respect to their subject matter.

V. EVOLUTION OF THE IMPORTANCE

The analysis conducted in Section IV enables us to objectively quantify the importance of landmark cases, in particular those selected by the Court. The analysis nonetheless points to another conclusion: namely, when selecting landmark cases, the Court tried to provide a historical perspective of what was considered important. Translated into the network approach conducted in this paper, this means that the coefficients capturing the importance of a case might have been high at some point in the past but were low in 2002. In this case the importance of the case will remain undetected by the static analysis performed so far.

In order to assess this claim, we conducted a temporal analysis by studying how the different metrics evolved over time. We mimicked the growth of the network and computed the values of the coefficients at each time step and for each case. It should be pointed out that for the in-degree and the longevity, the value of the coefficient can only grow by definition of the metrics. This is not the case for the authority score and the relative in-degree, which is why we exclusively focus on those two properties in the remaining of the paper.

This perspective allows us to investigate two questions that we address in the remaining of the section: is there any specific profile in the evolution of the properties for landmark cases that distinguish them from regular cases (Section V-A)? Does this historical perspective provide an explanation for the presence of landmark cases undetected in the previous analysis (Section V-B)?

A. Profile of the landmark cases

The first question we address is whether the landmark cases have a particular profile that distinguishes them from regular (non-landmark) cases. In particular, how and when do they gain authority in the networks?

Figure 2 presents the evolution of the importance of the landmark cases according to their authority scores (left) and relative in-degree (right) and compares it to the regular cases. It shows that for the two properties, landmark cases have a profile which clearly differs from the profile of regular cases. Focusing on the relative in-degree for instance, all cases experience a slow but steady decline of the value. This is expected since, as new cases are decided, it becomes more difficult for a case to maintain the ratio computed by the metric. However, one can see that the relative in-degree is always significantly higher than the relative in-degree of regular cases.

Regarding the authority score, one can also notice a clear distinction between landmark cases (straight black line) and regular cases (grey line) 10 . More importantly, there seems to be a maturation process spanning several years before the landmark cases obtain their maximal value. Then one can observe a sharp decline of the authority and finally a clear regain of importance at the end, leading to the impression that landmark cases might have a different maturation process.

Investigating this question in detail, we used the additional classification presented in Section III-B3 to study whether any specific properties of the landmark cases might explain this evolution. It resulted that, as shown on the left part of Figure 2, symbolic cases (dashed line marked with a triangle) and practical cases (dashed line marked with a square) have very different profiles. Symbolic cases tend indeed to have a very long maturation process, leading such cases to have very low authority according to the network analysis (even lower than average regular cases) before gaining their fame long time after being issued (30 years in average). This is in sharp contrast with the profile of practical cases that start loosing their authority after 20 years.

These findings confirm the theory of incremental decision making of courts [START_REF] Dothan | Reputation and Judicial Tactics: A Theory of National and International Courts[END_REF], according to which courts postpone the full effect of decisions that introduce legally of politically contentious principles in order to preserve their authority and 10 the result is the same in average if we take a random selection of 50 regular cases instead of all regular cases. legitimacy.

B. Remembrance of the past

The conclusions drawn from the study of the evolution of the authority of the cases question the relevance of assessing the importance of a case at a specific time. When dealing with a specific topic in particular, it is very likely that important cases are taking the lead against formerly important cases related to the same issue. In fact, this is how the law evolves.

To illustrate this point, we focus in the following on the landmark cases that concern the "Free movement of goods" (as subject matter). This category is interesting in this context for two reasons: first, it is the category which contains the most landmark cases [START_REF] Bourcier | Codification, law article and graphs[END_REF] listed by the Court, revealing the particular emphasis that the Court placed on this topic, and second, this category is the one where the Court's and the network's points of view match best. Indeed, almost half of the cases were considered important by all applied metrics (see Table II), begging the question why other landmark cases were not considered important.

Figure 3 presents the evolution of the authority score (left) and the relative in-degree (right) as a function of time for the landmark decisions related to the "Free movement of goods". This plot is related to the static analysis of Section IV as the values at the very end of the plot are the ones used to rank the cases. Focusing in particular on the authority scores, one can see that Dassonville (61974CJ0008) is the most important one, followed by Cassis de Dijon (61978CJ0120), then Keck and Mithouard (61991CJ0267), Comm v GE (Beer purity) (61984CJ0178), etc.

Figure 3 provides several interesting observations. First, it clearly strengthens our assumption regarding the forgot-1967 1971 1975 1979 1983 1987 1991 1995 Relative in-degree Fig. 3. Free movement of goods ten cases which were important in the past. Van Gend (61962CJ0026) in particular was one of the less important cases in 2002 and, as such, not identified as an important case by network analysis in Section IV. However, the temporal approach reveals that it has been a key case in the seventies, before it depreciated. At that point, namely, the Dassonville and the Cassis de Dijon cases were decided and took the lead in legal development. This shows that adding a temporal perspective to a more structural network analysis is essential in order to obtain a comprehensive picture of case importance. Second, the comparison between the evolution of authority scores and relative in-degree shows that while authority scores can detect such shifts between leading cases in a particular context, relative in-degree provides a more precise vision of the evolution of importance. Focusing on Cassis de Dijon for instance, the evolution of its authority score seems to indicate a sharp increase of importance (along with Dassoville, although even sharper) before a clear decline. This perspective is contrasted with the evolution of its relative in-degree showing a steady importance over time.

As pointed out previously, the natural evolution of relative in-degree is to decrease over time since the value is a ratio whose denominator grows as the network grows. Thus a prolonged steady value for Cassis de Dijon reveals that, although the authority scores seems to indicate a decline of authority, the case was actively referred to by the judges over an extended period of time when they had to decide cases that concerned the "Free movement of goods" .

In this regard, the evolution of Dassonville is even more spectacular since its value increases over time. Thus not only the case gained authority as suggested by the authority score but it became more frequently cited as time passed. Finally, the relative in-degree also highlights the emerging importance of Keck (61991CJ0267), undetected if using only authority score, that seems to coincide with the two former cases. This analysis thus suggests that the evolution of importance of Dassonville, Cassis de Dijon and Keck is related and should be analysed together in order to obtain a comprehensive understanding of the evolution of this area of law (the free movement of goods).

From a legal perspective, the outcome of the above network analysis matches the legal doctrinal perspective, and further refines it. Namely, in Dassonville, which was decided in 1974, the Court struck down national measures that hindered trade between Member States. It was seen by some commentators as a paradigm shift in EU law, see [START_REF] Maduro | The past and future of EU law: the classics of EU law revisited on the 50th anniversary of the Rome Treaty[END_REF] p. 456). However, the Court did not use the potential that it created for legal development immediately (what we referred to above as incrementalism). Dassonville remained somewhat dormant until Cassis de Dijon was decided in 1979, and revealed its potential (hence the relative in-degree of Dassonville began to increase in the early 1980s, as shown in Figure 3). Cassis the Dijon, by way of comparison, clarified a specific aspect of the case law that Dassonville left open (the mutual recognition principle). Both cases became popular with litigants as they allowed them to fight more and more national measures that protected "domestic" products and trade. This litigation continued until the Court explicitly reversed its permissive Dassonville approach in Keck that immediately applied to all contested measures and trade, in 1993, and, as shown in Figure 3, became an instant landmark. For some time after 1993, the litigants continued to invoke Dassonville to clarify whether any of its aspects were still valid (also reflected in the upward citation trend in Figure 3). These developments are reflected by the complementary network metrics.

In conclusion, the analysis conducted on the "Free movements of goods" illustrates the fact that the perspective provided by the authority score and the relative in-degree are complementary and, combined, can provide a more accurate vision of the evolution of the case law.

VI. CONCLUSIONS

In this paper we studied the use of structural (in-degree, authority) and time-related (relative in-degree, average longevity) properties in interpreting the structure of citation networks, focusing on the case citation network of the Court of Justice of the European Union. Thereby, we assessed whether the selection of landmark cases from the Court can be justified by the application of those metrics. Our results show that a static analysis focusing then only on the latest snapshot of the network can detect nearly half of cases that are considered landmark. This confirms in part the theory that the Court uses other criteria to select important cases. We obtained slightly better results when we dealt with subnetworks, induced by the case topics, where one can observe that for each network the top-10 with respect to a metric, gives a good idea of which are the objectively important cases per area.

The use of the evolving network as a testbed where we incrementally compute authority scores and relative in-degrees, yields compelling results. First of all, it is quite obvious that landmark cases indeed have a very specific profile: The computed metrics for landmark cases are on average a few orders of magnitude higher than those of an average case. Among them, cases of doctrinal importance obtain high authority scores almost 30 years after they were decided. This is in sharp contrast with cases of more practical substance that gain value at least a decade after the were decided, before they depreciate at a point where they are substituted by another practical case.

As regards the comparison of the different metrics used in this paper, we can clearly see that the metrics are complementary, for both the static and the evolutionary network study. Average longevity allows to detect cases that are diachronic on purely legal criteria, whereas relative in-degree spots the rising stars, which is expected as it favours newer judgements. Indegree performs also rather well. It is not surprising that some of the important cases are well cited, however the less cited cases sink according to this metric. It is then the evolution of metrics that unveils the importance of the latter. In the evolutionary study, it becomes clear that authority allows to succession of authoritative case, which is in fact inline with the judicial interpretation of the Court's doctrine. On the other hand, relative in-degree, despite the fact that it favours the more recent cases, shows that cases with authoritative profile, retain their high ranking through the lapse of time, which in turn gives us good candidates for landmark judgments.

All in all, we believe our methodology provides with a useful framework to study the importance of case-law by leveraging the citation network and the available metadata on the case. We seek to extend our methods by defining new metrics or combinations of the existing ones and by extending our study to bi-partite networks, e.g. countries-cases, actorscases, etc.

Fig. 1 .

 1 Fig. 1. Example of a DAG depicting citations processes

NUMBER

  OF LANDMARK CASES IN LIST OF THE 5, 10 AND 50 MOST IMPORTANT CASES ACCORDING TO THE NETWORK ANALYSIS.

			Network		In-degree top 5 top 10 top 50 top 5 top 10 top 50 Authority	Rel. in-degree top 5 top 10 top 50	Longevity top 5 top 10 top 50
			Complete		4	5	17	1	1		8	1	1	10	1	3	7
			Sub-network	11	14	26	8	10		19	10	12	26	5	14	20
				Ratio		2.75	2.8	1.5	8	10		2.4	10	12	2.6	5	4.67	2.9
										TABLE III
		0.10 0.12				Authority score Landmark cases All Symbolic Practical		Regular cases All		0.007 0.008 0.009			Relative in-degree	Landmark cases Regular cases
	Average value	0.04 0.06 0.08										0.003 0.004 0.005 0.006
		0.02										0.001 0.002
		0 0.00	5	10	15 Number of years since issued 20 25 30	35	40	45	0 0.000	5	10	15 Number of years since issued 20 25 30	35	40	45
									Fig. 2. Landmark vs. regular cases

These were cases, which the acceding Member States had to translate into their respective official languages. See http://curia.europa.eu/jcms/jcms/Jo2 14955/

http://eur-lex.europa.eu/content/help/faq/celex-number.html

http://eur-lex.europa.eu

Internal Memorandum of the Court (Sep.[START_REF] Mirshahvalad | Significant communities in large sparse networks[END_REF] 2003), see[START_REF] Sadl | A "selfie" from luxembourg : The court of justice and the fabrication of the pre-accession case-law dossiers[END_REF]

Internal Memorandum of the Court (May 17, 2002), see[START_REF] Sadl | A "selfie" from luxembourg : The court of justice and the fabrication of the pre-accession case-law dossiers[END_REF]

For more detailed information on the role of the Research and Documentation Directorate, see Research and Documentation Directorate, CURIA, http://curia.europa.eu/jcms/jcms/Jo2 11968/ direction-de-la-recherche-et-documentation (last accessed Mar. 11, 2016).

EUR-LEX, http://eur-lex.europa.eu/homepage.html (last visited Mar. 11, 2016).

Due to space limitation and the focus of our study, we limited the analysis to subject matters (classifications of the Court) that contain at least one landmark case.

This research is partly funded by the Danish National Research Foundation Grant no. DNRF105 and conducted under the auspices of iCourts, the Danish National Research Foundations Centre of Excellence for International Court

Category

In