Brice Goglin
email: brice.goglin@inria.fr

Towards the Structural Modeling of the Topology of next-generation heterogeneous cluster Nodes with hwloc

Parallel computing platforms are increasingly complex, with multiple cores, shared caches, and NUMA memory interconnects, as well as asymmetric I/O access. Upcoming architectures will add a heterogeneous memory subsystem with non-volatile and/or high-bandwidth memory banks.

Parallel applications developers have to take locality into account before they can expect good efficiency on these platforms. Thus there is a strong need for a portable tool gathering and exposing this information. The Hardware Locality project (hwloc) offers a tree representation of the hardware based on the inclusion of CPU resources and localities of memory and I/O devices. It is already widely used for affinity-based task placement in high performance computing.

We present how hwloc represents parallel computing nodes, from the hierarchy of computing and memory resources to I/O device locality. It builds a structural model of the hardware to help application find the best resources fitting their needs. hwloc also annotates objects to ease identification of resources from different programming points of view. We finally describe how it helps process managers and batch schedulers to deal with the topology of multiple cluster nodes, by offering different compression techniques for better management of thousands of nodes.

Introduction

High performance computing relies on powerful computing nodes made of tens of cores and accelerators such as GPUs or Xeon Phi. The architecture of these servers is increasingly complex because these resources are interconnected by multiple levels of hierarchical shared caches and a NUMA memory interconnect. Execution performance now significantly depends on locality, i.e. where a task runs with respect to its data allocation in memory, or with respect to the other tasks it communicates with. It had a critical impact on the performance of parallel applications for a long time, from distributed computing [START_REF] Szalay | The importance of data locality in distributed computing applications[END_REF] to single servers [START_REF] Steckermeier | Using locality information in userlevel scheduling[END_REF].

Performance optimization of parallel applications requires a thorough knowledge of the hardware, and many research projects aim to model the platform to tackle this challenge. Besides analytic performance models, one solution consists in structural modeling of the hardware resource organization. Indeed, parallel developers need such information to properly use the platform. hwloc (Hardware Locality) is the de facto standard software for representing CPU and memory resources, and for binding software tasks in a portable and abstracted manner [START_REF] Broquedis | hwloc: a Generic Framework for Managing Hardware Affinities in HPC Applications[END_REF].

We identify two major types of affinity. First, tasks have affinities for hardware resources they use. This includes memory banks, caches and TLBs that contain some of their data as well as I/O devices such as accelerators and network interfaces. Moving a task away from one core can cause the performance to vary depending on the cores' locality with regard to the I/O devices used by the task [START_REF] Moreaud | Impact of NUMA Effects on High-Speed Networking with Multi-Opteron Machines[END_REF]. The second kind of affinity is between tasks. Indeed, parallel applications often involve communication, synchronization and/or sharing between some of the processes or threads. It usually means that related tasks should be placed on neighbor cores to optimize the communication/synchronization performance between them [START_REF] Song | Feedback-Directed Thread Scheduling with Memory Considerations[END_REF]. However, the affinity can also be reversed when single tasks have strong needs. For instance, memory-intensive applications may want to avoid sharing memory links or caches with others [START_REF] Kim | Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture[END_REF].

Applications can have several of these types of affinities simultaneously, even with conflicting needs. We envision two ways to deal with these needs. First, tasks can be placed on the hardware resources according to their affinities. For instance, MPI process placement based on the communication scheme and on the platform topology is a very active area of research [START_REF] Hoefler | Generic Topology Mapping Strategies for Large-scale Parallel Architectures[END_REF][START_REF] Subramoni | Design of a Scalable InfiniBand Topology Service to Enable Network-Topology-Aware Placement of Processes[END_REF][START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF]. Then, the actual communication between tasks can be adapted to the existing placement. For instance, the existence and the size of a shared cache between processes can be a reason to switch from one communication strategy to another [START_REF] Buntinas | Cache-Efficient, Intranode Large-Message MPI Communication with MPICH2-Nemesis[END_REF][START_REF] Ma | Locality and Topology aware Intra-node Communication Among Multicore CPUs[END_REF]. The locality of I/O devices can also be used to better tune collective operations [START_REF] Moreaud | Adaptive MPI Multirail Tuning for Non-Uniform Input/Output Access[END_REF][START_REF] Goglin | Dodging Non-Uniform I/O Access in Hierarchical Collective Operations for Multicore Clusters[END_REF]. Moreover, batch schedulers or process managers try to manage clusters of such heterogeneous nodes in a global manner, making locality an important aspect, outside of nodes as well.

This paper describes how hwloc has evolved into the de facto central place for gathering locality information about all hardware subsystems in parallel platforms. Our contributions include a structural model based on physical locality and inclusion, as discussed in Section 2. This strategy is already successfully used by many high performance computing software for querying locality information. Then Section 3 describes how hwloc exposes a portable and abstracted view of the hardware by combining topology information from many sources, including operating systems, domain-specific libraries and platform-specific instructions. We finally present in Section 4 a contribution to the way batch schedulers and process managers apply cluster-wide allocation or placement policies. hwloc lets them manipulate, summarize, compress and/or compare the topologies of multiple nodes from the front-end.

Modeling the Structure of Computing Platforms

hwloc is now used by most MPI implementations, many batch schedulers and parallel libraries 1 . We explain in this section why hwloc's structural model is a good solution for their needs.

Modeling Platform for Performance Analysis

The complexity of modern computing platforms makes them increasingly harder to use, causing the gap between peak performance and application performance to widen. Understanding the platform behavior under different kinds of load is critical to performance optimization. Performance counters is a convenient way to retrieve information about bottlenecks for instance in the memory hierarchy [START_REF] Treibig | Likwid: A lightweight performance-oriented tool suite for x86 multicore environments[END_REF] and apply feedback to better schedule the next runs [START_REF] Song | Analytical Modeling and Optimization for Affinity Based Thread Scheduling on Multicore Systems[END_REF]. The raw performance of a server may also be measured through different memory access workloads to predict the behavior of kernels [START_REF] Putigny | A Benchmark-based Performance Model for Memory-bound HPC Applications[END_REF]. However these strategies remain difficult given the number of parameters that are involved (memory/cache replacement policy, prefetching, bandwidth at each hierarchy level, etc.), many of them being poorly documented.

At the scale of a cluster, performance evaluation has been a research topic much earlier because network communication caused slowdowns long before servers became hierarchical (when multicore and NUMA processors emerged). The LogP model [START_REF] Culler | LogP: Towards a Realistic Model of Parallel Computation[END_REF] may be used to describe the network performance and build a hierarchy of processors based on this experimental distance for better process placement [START_REF] Hu Chen | MPIPP: An Automatic Profile-guided Parallel Process Placement Toolset for SMP Clusters and Multiclusters[END_REF]. Improved performance models have been proposed since then to offer realistic simulation on larger platforms [START_REF] Casanova | Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms[END_REF]. These approaches may also be combined for inter-node and intra-node communication so as to weight the communication performance of all combinations of cores before scheduling jobs [START_REF] Rodrigues | Multi-core aware process mapping and its impact on communication overhead of parallel applications[END_REF]. Such an approach may actually also help experimentally rebuilding the entire topology of the clusters for better task placement [START_REF] González-Domínguez | Automatic Mapping of Parallel Applications on Multicore Architectures using the Servet Benchmark Suite[END_REF].

These results however lack a precise description of the structural model of the machine. Experimental measurement cannot ensure the reliable detection of the hierarchy of computing and memory resources such as packages, cores, shared caches and NUMA nodes. Indeed, they impact performance in a different way, and it may vary significantly with the workload (memory footprint vs cache size, number of processes involved vs memory bandwidth, etc.). It explains why performance models only give hints about the impact of the platform on performance. On the other hand, the structural modeling of the platform gives precise performance reports. OpenMP thread scheduling [START_REF] Broquedis | ForestGOMP: an efficient OpenMP environment for NUMA architectures[END_REF] or MPI process placement [START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF] are examples of scheduling opportunities that can benefit from deep platform topology knowledge.

Structural Modeling of the Hardware as a Tree

The organization of computing resources in clusters is hierarchical: a cluster contain servers that contain processor packages, that contain cores, that optionally contain several hardware threads. Current AMD Opteron processors (63xx) also have an intermediate level called Compute Unit between packages and cores. Moreover, from a locality point of view, memory resources such as caches and NUMA nodes can be considered as embedded into such computing resources: indeed NUMA nodes are usually attached to sets of cores2 , while caches are usually placed between some cores and the main memory, Therefore we can sensibly extend a hierarchy of computing resources to a hierarchy of memory resources as depicted in Figure 1.

We represent the entire machine as a tree of resources organized by locality: the more the hardware threads share common ancestors (same NUMA node, shared caches, or even same core), the better locality between them is. This approach has several advantages:

• First the tree representation of the topology is very convenient because it exposes the natural inclusion-based organization of the platform resources. Indeed binding memory near a core or finding a shared cache between cores only requires to walk up the tree until we find the relevant ancestor object and/or walk down to iterate over children. We can easily iterate over cores and threads close to a given object in the tree, a very common operation in locality-aware runtimes.

Another solution would be to represent the structure as the generic graph whose nodes are resources and edges are physical connections. However, the concepts of inclusion, container parent and contained children would not be obvious, making application queries less convenient.

• Secondly, this logical organization based on locality solves many portability issues by hiding platform specific parameters. Indeed vendor-specific configurations, BIOS or software upgrades may change the numbering of resources even if the processors are identical3 . Therefore relying on hardware numbering of resources to perform explicit task placement makes programs non-portable, even to a similar platform with the same processors but a different BIOS (see Section 3.3).

On the other hand, relying on hwloc's logical numbering of resources to perform explicit task placement makes programs more portable as it is based on the actual physical localities.

• Third, using a tree-structure is a good trade-off between performance and precision: while using a graph to represent the architecture would be more precise in some cases, tree algorithms are often much more efficient in both memory and time. Indeed, process placement techniques often rely on graph partitioning techniques (a communication graph must be mapped onto an architecture graph) which are much more efficient when generic graphs are replaced with trees. For instance, the Scotch partitioning software supports a Tleaf architecture definition for enabling specifically optimized algorithms on hierarchical platforms [START_REF] Pellegrini | Scotch and libScotch 5.1 User's Guide[END_REF].

hwloc builds a Tree of Objects, from the root Machine (a single-image shared-memory system) to the leaves Processing Units (PU, that corresponds to hardware threads, logical processors, etc). It is based on the natural inclusive order of computing resources and the locality of memory resources. Each hwloc object is characterized by a type, some hardware characteristics such as a package number, and some optional parameters such as local cache or memory sizes. hwloc does not enforce the vertical ordering between these levels in the tree because some most modern processors may have two NUMA nodes per package (see Figure 1) while some Itanium machines have multiple packages per NUMA node. hwloc just moves larger objects above smaller ones depending on the architecture inclusion characteristics.

The hwloc model is further extended to include I/O devices by attaching I/O objects based on their locality. If a PCI bus is close to a NUMA node, the corresponding hwloc objects are attached as additional children to this NUMA node object, as depicted on Figure 2. The hwloc programming interface allows walking the tree edges to find ancestors or child objects of a given type (e.g. when looking for the NUMA node close to a given core), iterate over objects of a same type (e.g. when binding processes on cores), etc. hwloc offers a convenient way to apply mapping policies [START_REF] Hursey | Advancing Application Process Affinity Experimentation: Open MPI's LAMA-Based Affinity Interface[END_REF] or partitioning algorithms by matching applications affinity graphs onto the hwloc tree of hardware resources [START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF]. More use cases and hwloc v1.0 early design details are presented in [START_REF] Broquedis | hwloc: a Generic Framework for Managing Hardware Affinities in HPC Applications[END_REF].

Limits to the Tree Model

We explained in the previous section why modeling the structure of a parallel platform as a tree is convenient, we now list several drawbacks of this approach.

One critique against the model is its lack of topology information within single levels of the tree. For instance, Xeon E5 and Xeon Phi processors are actually made of cores connected by an internal ring. hwloc only exposes them as an unordered list of cores, without any information about distances between specific cores. The upcoming Intel Knights Landing processor will even interconnect core tiles by a mesh [13]. Although this knowledge has been used to improve memory allocation in Knights Corner Xeon Phi [START_REF] Gerofi | Part II, chapter Exploiting Hidden Non-uniformity of Uniform Memory Access on Manycore CPUs[END_REF], it remains hardly usable for applications in practice. Therefore, it is not clear yet if exposing such information would be of a lot of interest to hwloc users.

The same argument could apply to the NUMA memory interconnect since it is not always a complete graph. Indeed the performance of remote NUMA node memory access may vary with the physical distance 4 . This organization is available as a latency matrix (reported by the hardware ACPI tables, or provided by micro-benchmarks) and exposed by hwloc to annotate the set of NUMA node objects. Moreover, hwloc uses this information to create additional hierarchical Group objects that contain close NUMA nodes. Large NUMA platforms are therefore represented with a hierarchy of Groups between the Machine and NUMA node objects so that the physical organization as racks and blades is exposed 5 . Another issue with the tree model is upcoming architectures with different kinds of memory. For instance, the Intel Knights Landing processor will feature high-bandwidth memory (MCDRAM) inside the package while still using normal (DDR) external memory [13]. It means that each core may have two distinct local NUMA nodes, hence two parents: a normal one, and a faster but smaller one. Another constraint is that memory allocation should not go into the smaller and faster MCDRAM unless specifically requested. It means that the normal memory should appear closer to cores than the MCDRAM (even if the MCDRAM is physically closer). hwloc therefore currently exposes the MCDRAM as another NUMA node object on the side as shown on Figure 3. This work is part of a larger rework on the hwloc memory model. Indeed, upcoming non-volatile memory DIMMs will also be attached to processors and be byte-accessible. The exact way these new memories will be exposed to the operating system is still under standardization. But we envision the idea of moving NUMA node objects to the side and rather attach them to processor like I/O devices.

Finally, considering the variety of network fabrics, the hwloc tree model does not work well for representing multiple machines and their interconnection network. This issue will be addressed specifically in Section 4.5.

Discovering and Organizing Hardware Information

We describe in this Section how hwloc discovers the existing computing, memory and I/O resources, as well as their locality before explaining how they are actually exposed within the tree in a abstracted and portable manner.

Where and How to Gather Topology Information

The importance of locality led many developers to retrieve topology information within their applications or libraries. Unfortunately, this work is difficult because of the amount and variety of the sources of locality information, ranging from operating system, to direct hardware query and high-level tools.

Linux is widely used in high performance computing. Unfortunately, its ability to report topology information was designed over more than ten years and therefore suffers from a partial and non-uniform interface. Many hardware details are available from the sysfs virtual file system (/sys) but it misses processor details (only available in /proc/cpuinfo) and I/O information such as network connectivity. Moreover, some of these files are in human-readable format, while some other pieces of information are split into many different machine-readable files. Extracting locality information from an application is therefore a lot of work.

Convenient topology discovery should be available in higher-level libraries that hide the difficulty of parsing low-level system files or architecture-specific registers. On Linux, numactl 6 possesses knowledge of NUMA, CPU and I/O localities but lacks caches. Moreover, its programming interface is unstable, and it was primarily designed for binding tasks: it cannot be used for querying details about hardware characteristics. Some processors have dedicated instructions for retrieving topology information such as CPUID on x86. However, applications relying on this feature need to be updated for every new microarchitecture because special values with new meanings are often added and have to be supported. The operating system usually takes care of these cases, so these processor-specific instructions should not be needed in topology-aware applications, as long as the OS is recent enough. As shown on Figure 4, many libraries exist for querying the topology of specific subsystems, for instance pciutils for PCI 7 , libibverbs for InfiniBand, CUDA for NVIDIA GPUs, etc. Unfortunately, there is almost no interoperability between these libraries and other topology-related tools. Therefore, we often have to combine information extracted from different sources, which can be a tricky process: for instance, it is necessary to query sysfs, pciutils and CUDA when looking for the locality of a NVIDIA GPU with regard to host CPUs. Some higher level tools such as lscpu or lshw8 merge the information from several sources but they were only designed for displaying the topology, without any programming interface for querying. In addition, some non-Linux operating systems may have better interfaces but they lack part of the information. For instance, Solaris does not report cache information, but the CPUID instruction may detect it on x86 platforms.

In conclusion, all these sources of information still have to be used concurrently for a developer to gather locality information about all hardware resources. There is therefore a need for a portable, system-wide topology discovery tool that combines all these pieces and exposes the information in a convenient and portable programming API. hwloc has been designed from the start to be this needed portability layer.

Combining Multiple Sources

hwloc's discovery mechanism is based on several components9 , each gathering information from some specific sources (operating system, hardware, low-level libraries, etc.), as described on Figure 5. These components are ordered by priority that we defined empirically based on the completeness and reliability of the information they provide. Each component also defines a list of conflicting components to avoid redundant topology information (that could even be different in case of bugs).

If any, the operating-system-specific component is loaded first (on Linux, it reads CPU, cache and NUMA information from /proc and /sys virtual files). Then, the CPU-specific component is invoked to add missing information (the x86 component detects additional CPU and cache characteristics). Then a PCI component takes care of gathering the locality of PCI bus, before I/O-specific components attach objects describing GPUs, NIC, accelerators, etc. This component model lets user or administrator tune the information gathering process in case of buggy information. For instance, some Linux kernels report buggy cache information for AMD processors, that may be worked around by loading the x86 component first (the Linux component then only discovers what x86 did not). The user is advised when such a workaround is recommended but it should not be automatically enabled. Indeed the exact list of affected platforms is hard to define and may even change in the future. The only exception is for platform-specific components (for BlueGene/Q and Fujitsu Sparc-based servers) which are automatically enabled because it is known that only one model of these exists and that their operating-system topology support will remain poor.

Finally some global components are standalone and cannot be combined because they already provide all topology information (XML and Synthetic topologies are described in Section 4).

Locating and Identifying Resources

Applications typically use the hwloc tree for locating where they are currently running, finding neighbor objects, consulting object attributes (see Section 3.4), and binding tasks or memory. There is a need for easy ways to locate and identify specific objects in a portable and abstracted manner. Figure 6: Numbering of the processing units (PU) and NUMA nodes on dual-package dual-core hyper-threaded platforms. Two inter-dependent tasks running on logical processors 0 and 1 are actually not close to each other on these platforms. The binding cannot be portable unless it is specified as positions within the hierarchy of resources instead of as PU numbers. Memory binding is also non-portable because the relative ordering of NUMA nodes is different.

Computing and memory resources can be identified by indexes provided by the hardware and operating system (for instance the hardware thread that executes a given task). Unfortunately, these indexes are not portable from one machine to another because different vendors, BIOS versions or operating systems often use different ways to order CPU cores. It leads to cases where a standard dual-package platform can have up to 8 different numbering schemes in practice (see examples on Figure 6). hwloc therefore provides all these resources with a logical index that is portable because it is defined by the position in the hierarchical tree. Application may use such indexes to find out where they are running or where memory buffers are allocated, or bind new tasks to specific cores and memory buffers to specific NUMA nodes.

Managing I/O devices is more difficult because there are many kinds of these, and because applications do not actually natively use them like CPUs or memory. Indeed applications communicate on the network using Sockets, write to files, or use CUDA or OpenCL structures for running kernels on GPUs. They use such software handles instead of using PCI devices explicitly, so offering the locality of PCI devices is not actually useful to end-users. hwloc therefore offers different ways for application to locate the I/O devices they want to use:

• hwloc inserts OS device objects in the topology tree to represent these software handles (CUDA device, network interface, etc.) inside the corresponding physical devices (PCI objects). They are annotated with a kind attribute and a name in particular that lets applications identify them (see eth1 and cuda0 among others on Figure 2, or cuda0 and mic1 on Figure 7). An application willing to use the first CUDA device just has to ask for the first OS device of kind CUDA, walk up the tree to find out which NUMA node is physically close to the corresponding GPU, and optionally walk down to find the local cores.

• hwloc provides interoperability helpers for the majority of user-space interfaces to highperformance devices (OpenCL, CUDA, Intel Xeon Phi co-processors, etc.). They translate application software handles into hwloc concepts and the corresponding locality information.

For instance an application using InfiniBand will be able to retrieve the hwloc locality of the struct ibv_device that it already uses for posting RDMA requests.

Binding a process on cores close to a given device is such a common need (especially to perform device micro-benchmarking), that hwloc can do it automatically. For instance, the hwloc-bind command-line tool can be used as follows to execute the given program close to the OS device identified by its name with the os= prefix:

$ hwloc-bind os=mlx4_0 infiniband_benchmark $ hwloc-bind os=cuda1 cuda_benchmark $ hwloc-bind os=mic0 xeon_phi_benchmark

Exposing Hardware Characteristics

hwloc represents computing and memory objects using an exhaustive set of widespread resource types (PU, core, cache, package, NUMA node, machine, PCI, etc.). They may have type-specific attributes such as the memory size for NUMA nodes, the cache type and size, or bus ID for PCI devices. However, these static attributes cannot exhaustively cover the wide variety of hardware characteristics such as the CPU model and features, GPU memory and processor details, network address configuration, etc. To be as descriptive as possible, hwloc even allows objects to be annotated with custom attributes. They are store as pairs of key and value strings, such as Address=00:11:22:33:44:55. To avoid requiring many string operations in applications, this mechanism is only used for uncommon attributes (widely-used attributes such as cache sizes are still stored as static fields within the object structure). This feature is notably used by Intel and Oracle-specific drivers for dynamically optimizing the Open MPI implementation on their platforms.

Each object usually contains at most a few key-value pairs, especially OS devices that describe GPU characteristics, NIC addresses, etc. (see Figures 7 and8). These can be useful to distinguish between otherwise identical devices in a node or identical hosts in a network. Indeed, we need to Figure 8: Textual dump of some attributes gathered by hwloc for OS devices describing a CUDA GPU (cuda0), a Xeon Phi co-processor (mic1) and a InfiniBand HCA (mlx4 0). identify network hosts and switches in order to manage clusters (as further discussed in Section 4.5). Similarly, we need to distinguish between processes executed on local or remote identical accelerators (e.g. Xeon Phi). MPI implementations such as Open MPI use hwloc SerialNumber attribute to detect whether two MPI processes are executed on the same machine, inside accelerators or not, and to choose the communication strategies accordingly.

Managing Heterogeneous Clusters of Nodes

We now look at managing with hwloc the topologies of multiple nodes, such as a cluster. This is used for batch schedulers such as Slurm or Torque and process launchers found in most MPI implementations [START_REF] Hursey | Advancing Application Process Affinity Experimentation: Open MPI's LAMA-Based Affinity Interface[END_REF]. They gather computing node topologies on the front-end and apply clusterwide locality-aware allocation or placement algorithms. We first describe the actual needs of these hwloc users.

Different Needs

We distinguish the following possible needs in topology-aware cluster-management tools: Number of Cores: A batch scheduler does not need any knowledge of compute nodes as long as jobs request resources in terms of nodes instead of cores. However that is hardly the case, and the scheduler usually has to know at least the number of cores within each node. MPI process launchers also have this requirement for starting the right number of processes per node. This already raises the question of defining a Core: does the application want a real core or just a hardware thread? Giving real cores requires actual topology information.

Hierarchy of Resources: Clever resource allocation also tries to avoid breaking resource sets in pieces. For instance a scheduler processing a request for 6 cores among servers containing either two 6-core processors or two 4-core processors may want to allocate one entire 6-core processor (to avoid breaking one 4-core in two halves). Such strategies need the knowledge of the hierarchy of resources within each compute node.

Basic Attributes: Some object attributes are needed if the application can request specific kinds of CPUs or accelerators. Attributes such as indexes or memory size (see Section 3.3) are required once the batch scheduler reserves some processors and/or memory to isolate each job with mechanisms such as Linux cgroups. This information is also useful to runtimes such as MPI process launchers [START_REF] Hursey | Advancing Application Process Affinity Experimentation: Open MPI's LAMA-Based Affinity Interface[END_REF], or placement algorithms such as TreeMatch [START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF] that map tasks to hardware resources.

Full Attributes: When job allocation or task placement is performed using I/O locality, or when runtimes adapt their decisions to specific object information, the full topology of the machine is required.

We describe in the next sections how hwloc addresses these requirements.

Full XML Topologies

Managing the topology of multiple nodes requires a way to manipulate remote node topologies. We explained in the previous section that the full details of the topology may not be useful in all cases. However hwloc still supports that need anyway by allowing compute nodes to dump their entire topology to a XML file (or memory buffer) that can be transferred through a network and reloaded by the manager remotely. The loaded topology is strictly identical except that it cannot be used for actually binding task and memory since the local hardware is different. This is useful for developing topology-aware algorithms and testing on a variety of different platform topologies without actually having access to these platforms. But it is also already widely used by batch schedulers and MPI process launchers: each compute node sends a XML copy of its local topology to the front-end node which implements the allocation/placement policy clusterwide, before actually starting processes on the compute nodes. This strategy matches the Full Attributes case in Section 4.1.

XML also has the advantage of being very easy to load, much easier than rereading topology information from the different sources as explained in Section 3.2. Gathering the topology information natively on Linux indeed implies to read information from several hundreds of files under /sys and /proc. A naive MPI implementation running one process per core would load the topology once per core, causing all these files to be accessed by all cores simultaneously. Table 1 shows that the native Linux discovery does not scale well with the number of cores working in parallel (contention in the Linux kernel file-system locking code). On the other hand, XML import scales well. It also shows that very large machines may benefit from always loading from XML (up to 70x faster) even when not performing multiple discoveries simultaneously. Table 1: hwloc topology discovery time depending on the source, either native Linux discovery, or XML import. On each host, we measure the time for a single discovery on one core, and for all cores discovering simultaneously their own copy of the topology. However the XML export has the drawback of putting pressure on the network and front-end node by transferring lots of data from compute nodes. Indeed the size of hwloc XML exports scales in O(P log P ) with P the number of cores 10 . Deeper hierarchies also generate slightly larger XMLs (O(log D) where D is the number of hierarchy levels in the machine) but we do not expect many new hierarchy levels to appear in hardware in the future.

Table 1 shows that current computing nodes generate XML files whose size varies from tens to hundreds of kilobytes. It is hard to predict whether the actual transfer of tens of thousands of such files on a supercomputer would be an important issue in term of performance. At least, the workload on the front-end for processing these XML topologies will likely be problematic. Therefore there is a need for alternative ways to describe the topologies of remote nodes.

Synthetic Topology Description

We explained in Section 4.1 that many use cases do not actually require the full details of the compute nodes. The entire topology may therefore be replaced with only the relevant topology information. hwloc provides the concept of Synthetic Topologies to tackle this need: the topology may be exported or created as a string describing the hierarchy of computing and memory resources. Each element of the string describes the children of each object specified by the previous element (which type and how many of them below). Our dual-processor 8-core hyper-threaded Intel Xeon and SGI Altix UV hosts are respectively described as: This approach is sufficient for the Hierarchy of Resources case in Section 4.1. Moreover this description is software-independent: it is identical for all cluster nodes of the same kind, and it only changes if hardware is modified. The manager on the front-end may therefore describe many nodes with the same string (usually less than one hundred characters). Such a factorization is not possible with XML exports because of several host-dependent attributes (network addresses, hostname, etc.). This will be further discussed in Section 4.4.

The synthetic description may even be further simplified to only report certain types of resources by ignoring some levels before exporting the synthetic description. For instance it may only report the number of NUMA nodes, cores and threads, which are the most widely used resources (Number of Cores case).

NUMANode:2 Core:8 PU:2 NUMANode:20 Core:8 PU:1 However this approach is not sufficient as soon as the manager requires Basic Attributes for actual process placement or processor/memory reservation. To address this need, the synthetic description may also include the most widely used attributes such as memory sizes and physical resource numbering: NUMANode:2(memory=34330173440) Package:1 L3:1(size=20971520) L2:8(size=262144)

L1d:1(size=32768) L1i:1(size=32768) Core:1 PU:2(indexes=2*16:1*2) Group0:10 NUMANode:2(memory=34338770944) Package:1 L3:1(size=25165824) L2:8(size=262144) L1d:1(size=32768) L1i:1(size=32768) Core:1 PU:1

Resource numbering is only displayed if non linear. 2*16:2*1 is a hierarchical round-robin specification describing that physical PU indexes are ordered as 0, 16, 1, 17, ..., 14, 30, 15, 31 on our dual-Xeon host. One drawback of synthetic topology description is that it does not currently support I/O devices. This would require to define which I/O devices are most-likely useful to add to the synthetic description (current servers contains several dozens of PCI devices, most of them being virtual and uninteresting for locality problems). This feature is currently under early design for future hwloc releases.

Differences Between (Almost) Identical Cluster Nodes

XML and synthetic topology descriptions have both advantages and drawbacks, but the gap between them is quite large. One way to bridge that gap is to factorize similarities between different nodes described as XML. It is an interesting approach in clusters to avoid having to manipulate a huge number of topologies at the same time on the front-end. We identified three actual possible differences between cluster node topologies:

• different kinds of nodes (e.g. compute node vs fat node vs GPU nodes): topologies are very different;

• modified nodes (BIOS upgrade, software update, or hardware replacement): topologies may be different;

• similar nodes with different identification numbers such as network addresses, hostname, etc.

In the similar case, only some key/value pair attributes are modified. In other cases, the tree structure can be different. Therefore, we added to hwloc the ability to compute the difference between 2 similar nodes by recording which attributes have been modified. This lossless compression consist in identifying a few reference nodes whose topologies will be entirely stored (uncompressed). All other nodes are then compressed by only storing the difference between their topology and one of the references. This feature is already used in the netloc submodule of hwloc (further described in Section 4.5).

Table 2: Memory consumed when loading the topologies of all nodes of a cluster within a single process. Topologies were either stored as full topologies (uncompressed), or as a few reference full topologies and many differences against one of these references. 11 . Each cluster is made of different kinds of nodes (6 for Plafrim and 5 for Avakas), but we observe more reference topologies (respectively 18 and 12) because of the modified case above. However, many topologies can indeed be reduced from several hundreds of kilobytes down to 1 or 2 kB of differences in memory. Full topologies seem bigger in the compressed case because the share of fat nodes among reference topologies is higher.

Each difference is actually made of about 10 key/value pair attribute changes. We could even improve compression further by ignoring keys that are not needed by the target application (for instance the platform serial number, or the MAC addresses if only InfiniBand is used).

Multiple Node Topology

Finally, we look at how to manage a full, cluster-wide topology. In hwloc 1.4, we introduced a Custom API to assemble the topologies of multiple nodes into a global single one. It lets the application build a hierarchy of Groups (that represent switches) and attach topologies as children.

However, the resulting topology must respect hwloc's tree model while networks interconnecting nodes may be a random graph. We explained in Section 2.3 that latency matrices can be used to annotate some levels of the tree but this idea is only satisfying for simple topologies such as NUMA interconnects or package rings. high performance fabrics can be made of dragonfly or torus topologies that cannot be represented as such an annotated tree. Moreover, the Custom API always attaches node topologies by the root of their tree (the entire Machine object, see Figure 9). This is inconsistent with the network locality inside the nodes because network interfaces (or InfiniBand HCAs) are often attached to a single NUMA node, and because there can be multiple interfaces per node.

Therefore, assembling multiple nodes into a global hwloc topology tree does not seem convenient. That is why the Custom API has been removed from the upcoming hwloc 2.0 release. There is an ongoing work to develop a hwloc submodule called netloc that will not enforce a tree model [START_REF] Goglin | netloc: Towards a Comprehensive View of the HPC System Topology[END_REF].

There is a netloc graph describing the network and there are hwloc topologies for each node. In addition netloc also offers ways to translate handles from one world (hwloc OS devices for NICs) to the other (NIC ports in the network graph). One drawback of this new approach is that there is no global structure describing the entire cluster. This would be an issue if batch schedulers or process managers had cluster-wide algorithms handling both the inter-node and intranode cases simultaneously. Fortunately, there is no such need: the inter-node policy may be applied by weighting nodes based on their number of cores, while the intra-node policy is applied later separately.

Conclusion and Future Works

The increasing complexity of computing platforms raises the need for developers to understand the hardware organization and adapt their application layout. As part of the overall optimization process, there is a strong need for a tool modeling the platform, and hwloc is currently the most popular software for exposing a structural view of the topology of CPUs and memory. This approach is orthogonal to experimental performance models that give hints about the actual behavior of the resources exposed by hwloc.

We have presented in this article why and how the hwloc model has been designed as a hierarchical structural model, describing the locality of computing, memory and I/O resources. It combines locality information from many sources and offers APIs to interoperate with device-specific libraries. The hwloc tree also exposes many hardware attributes to help applications identify the resources they use, place tasks near them or adapt their behavior to their locality. hwloc also offers ways to manipulate the topology of multiple nodes so that batch schedulers or MPI process managers may apply resource allocation and task placement policies between nodes and inside nodes. Multiple node topologies can be consulted offline, compared, compressed or synthetized depending on the actual topology information requirements.

All the features listed in this paper are actually implemented and ready to use in hwloc releases 12 . On-going work is now focusing on support for next-generation memory architectures with different kinds of memory (high-bandwidth, non-volatile) as discussed in Section 2.3.

Passing

Figure 2 :

 2 Figure2: Topology of a dual-Xeon E5 host with GPUs (cuda0, cuda1), network (eth1), InfiniBand (mlx4 0) and disk (sda) connected to different packages, simplified and reported by hwloc's lstopo tool.

Figure 3 :

 3 Figure 3: hwloc's view of a quad-core processor with 1GB of high-bandwidth memory (HBM) and 1GB of normal memory.

Figure 4 :

 4 Figure 4: Overview of existing sources of locality information on Linux.

Figure 5 :

 5 Figure 5: hwloc's component-based organization.

  PU numbering by NUMA node first, then by core, then by PU. PU numbering by core first, then by PU, then by NUMA node; out-of-order NUMA node numbering.

Figure 7 :

 7 Figure7: Object attributes include cache types (L1i, L3, etc), memory sizes, PCI device and vendor numbers, PCI link speed, Xeon Phi memory and cores, CUDA memory and multiprocessors, as well as CPU vendor and model (not displayed here).

NUMANode: 2

 2 Package:1 L3:1 L2:8 L1d:1 L1i:1 Core:1 PU:2 Group:10 NUMANode:2 Package:1 L3:1 L2:8 L1d:1 L1i:1 Core:1 PU:1

Figure 9 :

 9 Figure 9: Custom topology made of 3 servers assembled by their Machine root object. They are actually physically connected to the network by their eth0 and eth1 interfaces that are close to their second NUMA node.

Table 2

 2 presents the memory occupancy improvement based on the compression of the topologies of two clusters

  Interface. The 20th European MPI User's Group Meeting (EuroMPI 2013), pages 163-168, Madrid, Spain, September 2013. ACM.

	[13] Intel	Corporation.	What	public	disclosures	has	Intel	made	about
	Knights	Landing?

A non-exhaustive list of hwloc users is available on the project webpage http://www.open-mpi.org/projects/ hwloc/.

Old architectures such as Itanium even had each NUMA node attached to several processors.

For instance, Processing Unit (PU) #0 and #4 are close in Figure1while #1 is located in another processor (not displayed).

On a 12-processor SGI Altix UV2000, the stream Triad benchmark bandwidth drops from 31GB/s locally, to 7.4GB/s when accessing memory from the neighbor NUMA nodes, and down to

5.3GB/s from the farthest NUMA node.

Some examples of latency-based grouping are available at https://www.open-mpi.org/projects/hwloc/ lstopo/.

http://oss.sgi.com/projects/libnuma/

http://mj.ucw.cz/sw/pciutils/

http://ezix.org/project/wiki/HardwareLiSter

hwloc v1.11 embeds

OS components, 6 I/O, 1 platform-specific, 1 CPU-specific, and 3 global components.

The XML file contains one line per object, and those lines contain bitmasks (representing the object locality) whose sizes are proportional to processor numbers.

The hwloc-compress-dir utility was used.

hwloc is available from http://www.open-mpi.org/projects/hwloc/ under the BSD license.

Acknowledgments

Some of cluster node topologies used in this study were provided by the computing facilities MCIA (Mésocentre de Calcul Intensif Aquitain) of the Université de Bordeaux and of the Université de Pau et des Pays de l'Adour. Some experiments presented in this paper were carried out using the PLAFRIM experimental testbed, being developed under the Inria PlaFRIM development action with support from Bordeaux INP, LaBRI and IMB and other entities: Conseil Régional d'Aquitaine, Université de Bordeaux and CNRS (and ANR in accordance to the programme d'investissements d'Avenirs, see https: //www.plafrim.fr/).


Radu Cârpa
email: radu.carpa@ens-lyon.fr

Marcos Dias

Olivier Assunção

Laurent Glück

Jean-Christophe Lefèvre
email: jean-christophe.mignot@ens-lyon.fr

Mignot

Responsive Algorithms for Handling Load Surges and Switching Links On in Green Networks

Reducing the energy consumed by wired computer networks is a challenge that has been actively investigated over the past few years. A popular mechanism proposed to reduce the consumption aims to put links and line cards to sleep mode during off-peak hours. Such a mechanism, however, decreases the available network capacity and increases the risk of congestion if traffic rises unexpectedly. This paper proposes a solution to rapidly react to network bursts and turn-on sleeping links, which we term as SegmenT Routing based Energy Efficient Traffic Engineering for switching ON (STREETE-ON). The proposed algorithm was implemented in the OMNeT++ network simulator using state-of-art dynamic graph algorithms. In such a way, we achieved execution times of tens of milliseconds for a 50-node network. Experimental results show that STREETE-ON can effectively prevent network congestion, avoid turningon unneeded links, and preserve good energy-efficiency of the network.

I. INTRODUCTION

The rising traffic demands of today's services -e.g. those relying on cloud computing, video-on-demand, and big-data processing -continue to demand increasing data transfer rates from underlying networks. Network operators, who feel continuous pressure to differentiate and deliver quality of service, often tackle this challenge by expanding network capacity, hence constantly adding new equipments and links, or increasing the rates of existing links. Certain studies, however, argue that if traffic continues to grow at the current rate, in less than 20 years network operators may reach an energy capacity crunch where the power grid may be unable to provide the energy the overall network requires [START_REF] Kilper | Energy challenges in access and aggregation networks[END_REF].

Major organisations have been trying to minimise the energy consumption of their infrastructure by reducing the number of required equipments and maximising utilisation. Google, for instance, created custom Software Defined Network (SDN) devices and prioritised traffic in order to achieve near-100% utilisation of intra-domain links [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF]. With an intelligent traffic orchestration, Google is able to reduce the energy consumption while providing high quality of service. However, such a traffic regulation requires full knowledge of communicating applications and their demands; factors over which ordinary network operators usually do not have control. As a result, they provision network capacity to handle peak load, while devices consume energy even under low utilisation. Evidence shows that the utilisation of production 100Gbps links can be as low as 10% during normal operation [START_REF]Geant network looking glass and usage map[END_REF].

As network equipments usually draw the same amount of power regardless of their utilisation [START_REF] Chabarek | Power awareness in network design and routing[END_REF], a commonly exploited means to reduce the energy consumed by a network consists in setting its equipments to low power modes when partially used, or switching them off completely. While turning links off is a widely exploited technique at a conceptual level, most previous work does not consider dynamic networks. The literature describes several techniques, including Mixed Integer Linear Programming (MILP) formulations that are solved offline and rely on estimated traffic matrices [START_REF] Van Heddeghem | A quantitative survey of the power saving potential in ip-overwdm backbone networks[END_REF]. Complex linear programming formulations, heuristics and metaheuristics have shown that substantial energy savings can be achieved. However, these approaches are often slow, taking tens of minutes to compute a solution. Arguably, their viability is justified by assuming that network traffic varies slowly and presents diurnal patterns; periods of low traffic at night and peak demand during the day.

This assumption, however, does not hold true at short time scales [START_REF] Schmidt | Gaussian traffic revisited[END_REF]. The shorter the interval over which the average traffic is measured, the more variations become noticeable. A slow variation when measuring traffic per day may contain multiple bursts when zoomed in and analysed at smaller scales. Moreover, previous work highlights that traffic bursts are more visible when flow aggregation is low, which usually corresponds to a moment of low network utilisation. Considering traffic bursts at small scales is important in order to determine when network equipments should be brought back to fully operational state after being shut down to save energy. It is important under such scenarios to react quickly to bursts when links that have been previously turned off become necessary.

The literature has thus far mostly overlooked the problem of turning links on. One of the exceptions [START_REF] Yang | Towards fast rerouting-based energy efficient routing[END_REF] aims to partition the network over cycles. At each cycle, a single link can be turned off and the traffic is rerouted over the remaining links. Reacting to congestion is achieved by turning on the respective link. A distributed approach is also proposed [START_REF] Bianzino | Grida: A green distributed algorithm for backbone networks[END_REF] where a node evaluates at a random time interval whether its adjacent links should be turned on; a solution that reacts slowly to network changes. Another approach consists in turning-on all links at a pre-defined time in the morning, when traffic increases [START_REF] Francois | Optimizing link sleeping reconfigurations in isp networks with off-peak time failure protection[END_REF]. If an unexpected burst happens during the night, however, certain network links will remain in low power consumption mode. A previous work uses traffic matrices to estimate the best links to be turned on [START_REF] Kamola | Shortest path green routing and the importance of traffic matrix knowledge[END_REF], considering only the actual network state. In this work, we propose schemes to react fast to traffic bursts in operators' core networks and to switch on previously turned-off links as quick as possible. Our solution aims to complement previous work by enabling fast reaction to unexpected network events while further optimisation can be performed in background using the previously proposed solutions. We analyse the impact of traffic variations in an energy-optimised topology and evaluate the trade-offs between energy savings and packet loss while attempting to minimise the number of times links are turned-off /on. In particular, we evaluate the impact of the time needed for the solution to react to network changes.

The rest of this paper is structured as follows. Section II introduces the notations and formalises the problem. Our solution is presented in Section III and the results are presented and discussed in Section IV. Section V describes ongoing work, and Section VI concludes the paper.

II. FORMAL DESCRIPTION OF THE LINKS-ON PROCESS

The challenge of turning links off for reducing the energy consumption of networks was frequently considered by the research community. In this work, we consider unexpected traffic bursts in a network with links that have been turned off. Our goal is to react as fast as possible by turning links back on to avoid congestion.

This section presents our assumptions, introduces the notations used in the paper, and provides an abstract graph formulation of the problem.

A. Network Context

The work takes into account an operator network with the following characteristics: a) Virtual Tunnels: We assume that a full mesh of virtual tunnels among the nodes of the network allows to change the path of the data passing through the network dynamically. All the data entering the network domain at a source node s and travelling towards the destination node d will be transmitted through the tunnel s → d. The paths of tunnels are modified to route the traffic through the links kept on and avoid switched off links.

A classical way to create virtual tunnels consists in using the MPLS protocol as forwarding dataplane and the RSVP-TE protocol to signal the tunnels and change their paths.

b) Monitoring the Bandwidth: Network nodes are capable to monitor the bandwidth used by each of the virtual tunnels starting at a given node. c) Centralised Management: A centralised path computation engine is available on the network and has the ability to collect statistics from nodes and change the paths of data flows in the network.

d) Unidirectional Links: We assume that links can be turned on and off independently in each direction without affecting the opposite direction. For example, in long-distance optical links, the transponders may be unidirectional. Turning a link off will correspond to turning off the transponder and part of the line card.

e) Homogeneous Links: We assume that the network link speeds and their energy consumption are homogeneous.

B. Graph Modelling

Consider a representation of the network by a connected directed graph G(V, E). Each network device corresponds to a vertex v ∈ V and each link to an edge e ∈ E. A function c : E → R + represents the capacities of the edges, i.e. the link speed. A function l : E → R + represents the length (cost) of the edge.

The traffic entering the network at the source node s ∈ V and flowing towards the egress destination node d ∈ V is defined as the flow f s,d 0. In this work we assume that there is no traffic from a node to itself, i.e. ∀s ∈ V, f s,s = 0. Intuitively, ∀d ∈ V , the value of f s,d will be computed by the node s by monitoring the bandwidth passing through the virtual tunnel s → d.

A network-wide traffic matrix T M = [f i,j ] is a square matrix where each case i, j corresponds to the value of the flow f i,j (Figure 1c). We consider that this traffic matrix is assembled on the network controller by collecting the data from all the nodes.

A path P = (e 1 , e 2 , ...) is a sequence of edges such that ((e i = (a, b) and e i+1 = (c, d)) ⇒ b = c). The length of a path P = (e 1 , e 2 , ...) is the sum of the lengths of the edges in the path: l(P) = e∈P l(e). A shortest path from the node s to d is a path such that there is no other path P with l(P ) < l(P).

For each (s, d) ∈ V 2 , s = d, there exists at least one path from s to d and the tunnel s → d transporting the flow f s,d always traverses the network via the shortest path from s to d in G. The selection among multiple shortest paths of the same length is randomly-deterministic, i.e. the first path found during the computations is chosen. It depends on the initial construction of the in-memory data structure, but it is always the same for a given in-memory structure.

The utilisation of an edge in the graph G with a certain traffic matrix T M is represented by the function u G,T M : E → [0, 1] defined as the sum of the flows passing through the edge divided by the capacity of the edge.

For a given network G and a traffic matrix T M, we define the set of links at critical load CL G,T M = {e ∈ G | u G,T M (e) > α}. It contains the links with an utilisation higher than α in G. For example, if α = 0.8, CL G will contain the links with an utilisation higher then 80%. Throughout this paper we'll refer to links in CL as "links close to congestion".

III. STREETE-ON

A. Problem Statement

Figure 1 illustrates our algorithm. Let G be the initial network topology, we introduce G such that V = V and E ⊂ E, i.e. a subset of links is switched off. An example of G and G can be seen in Figure 1a and1b.

A novelty is that the algorithm uses both the energy-efficient network topology G and the initial full network G in order to take a decision. We consider that the best quality of service that a network can provide is achieved by keeping all the links on. Hence, we leverage knowledge about the all-on network to decide which links are the best candidates to be turned on and avoid congestion.

Starting from the energy efficient network topology G , it uses the traffic matrix to find the links at critical load CL G . The full network topology G is then used to select good candidate links. The algorithm finishes by doing a rapid inmemory simulation of turning those links on and estimating the impact of a decision without actually turning links on in the physical network. Whenever the computation decides that it is worth turning links on to reduce the utilisation of links from CL, the decision is sent to network nodes and the physical links are turned on.

The controller hence aims to solve the following problem: if CL G ,T M = ∅, find a subset of edges ⊇ (E \ E ), such that, by inserting them into G , CL G ,T M would become an empty set.

B. Algorithm

Algorithm 1 details our solution. Our greedy heuristic consists in first trying to turn-on the links which are off in the energy-optimised network G , but would have a high utilisation in G (lines 3 and 8). By using this heuristic we

Algorithm 1 STREETE-ON 1: procedure STREETE-ON(G, G , T M) 2: result ← ∅ 3: candidateLinks ← E \ E 4: congested ← CL G ,T M 5: changed ← true 6:
while congested = ∅ and changed = true do for all e ∈ sorted(candidateLinks, uG,T M) do return result 29: end procedure prioritise turning on the links which would create shortcuts for large flows. For example, in Figure 1 the link ab is selected as a candidate by analysing the traffic matrix and the two topologies. It is a link which is off in G , but would transfer much data in G (the flows f a,b and f a,c ).

At lines 11-12 the algorithm simulates turning the link on and estimates the congestion after this operation. At lines 13-20 it tests if congestion decreased. If yes, the link will be scheduled to be turned on in the physical network, else the link is not scheduled for ignition.

"congestion decreased" at line 13 is defined as:

• solving all the congestion: congested af ter = ∅

(∃f ∈ congested s.t. u G ,T M (f ) decreased)
Sometimes a combination of links must be turned on to be able to avoid congestion. The while loop at line 6 ensures the repetition of the algorithm until the congestion is solved.

The presented algorithm hides a complex operation in accesses to CL at lines 4, 12 and 24: recomputing the shortest paths to estimate the load of links and find the congested ones.

A naive approach for recomputing the shortest paths uses The maximum theoretical complexity of this algorithm is the same as static Dijkstra computations. However, in practice it proves itself much faster.

C. Implementation

As stated beforehand, we use network tunnels to transparently reroute traffic. However, the protocol usually used to signal virtual tunnels, RSVP-TE, scales badly with network size. The worst case number of states that a network device must keep active for a full mesh of virtual tunnels is O(|V | 2 ) and in industry it is considered a best practice to not use RSVP-TE to signal a full mesh of tunnels.

To reduce the complexity, we use the SPRING protocol, which is a mix of source routing and shortest path routing protocols. Due to its source routing nature, changes in the paths of a tunnel must be applied only on the node situated at the inbound end of the tunnel. No time and signalling are lost re-configuring the midpoint devices. This enables fast flow setup and easy reconfiguration of virtual circuits with minimum overhead. Moreover, for a full mesh of virtual tunnels, each node must keep exactly |V | -1 states: one per each tunnel which starts at the concerned node. An interested reader can relate to our previous work [START_REF] Carpa | Improving the energy efficiency of software-defined backbone networks[END_REF] or to the draft IETF RFC [START_REF] Filsfils | Segment routing architecture[END_REF] for a more detailed overview of the SPRING protocol, which is a very efficient way to simplify the implementation compared to MPLS + RSVP-TE.

IV. PERFORMANCE ANALYSIS

The proposed STREETE-ON algorithm was implemented in the OMNeT++ discrete event simulator [START_REF]OMNeT++ Discrete Event Simulator[END_REF]. The STREETE-ON algorithm is executed by a centralised controller when a link at critical load is detected. Figure 2c shows the load distribution in a network before executing any turn-on algorithm. The small black lines represent the links in a sleep state, while the dotted ones are active only in one direction. The colour illustrates the utilisation of the links.

A. Analysed Algorithms

We evaluate the performance of our solution against the following intuitive algorithms which allow to take fast turnon decisions:

• Turn on the links in the inverse order that they were switched off. Hereafter we refer to this algorithm as lastoff.

• Turn on all the links, referred to as allon.

• Turn on the links concentrically around the most congested one; hereafter referred to as locality. Similarly to STREETE-ON, the examined algorithms simulate the turn-on process in memory. Only after choosing all the links that must be turned-on, the decision is applied to the physical network.

a) lastoff: the algorithm 2 consists in turning-on one by one the links in the inverse order they were switched off until congestion is avoided. At line 3, the last turned-off link is selected among those being off, after that the link is scheduled to be turned-on at lines 4-5. The operation is repeated until the congestion is solved or all the links are turned-on.

Algorithm 2 lastoff 1: result ← ∅ 2: while CL G ,T M = ∅ and E \ E = ∅ do 3: e ← lastT urnedOf f (E \ E ) 4: E ← E ∪ {e} 5:
result ← result ∪ {e} 6: end while b) allon: the algorithm 3 turns-on all the links (lines 2-3) as soon as a link at critical load is detected in the network (line 1).

Algorithm 3 allon

1: if CL G ,T M = ∅ then 2: result ← E \ E 3: E ← E 4: else 5:
result ← ∅ 6: end if c) locality: at line 3, the algorithm 4 searches for the link with the highest utilisation in G . After that, at line 5 it executes an Breadth-first search algorithm to traverse the graph up to a maximum depth given in parameter and to extract all the sleeping links. All the found links are turned on. If the congestion is not avoided, the algorithm is repeated with larger depth until turning on all the links or avoiding the congestion.

The algorithm corresponds hence to turning-on links in cycles around the one with the highest utilisation.

Algorithm 4 locality

1: result ← ∅ 2: depth ← 1 3: maxe = maxU tilizationLink(CL G ,T M ) 4: while E \ E = ∅ and CL G ,T M = ∅ do 5: toT urnOf f ← (E \ E ) ∩ linksInBF S(G, maxe, depth) 6: E ← E ∪ toT urnOf f 7:
result ← result ∪ toT urnOf Each link in OMNeT++ was simulated with a speed of 3Gbps. The propagation delay was given as the bird-fly distance by Google Maps API.

To validate our solution on a realistic use case, we used the Germany 50 (Figure 2) topology and associated traffic matrices from SNDLib [START_REF]SNDlib: a library of test instances for Survivable fixed telecommunication Network Design[END_REF]. The network has 50 routers and 176(88•2) links . However, using the real traffic matrices from SNDLib also has its shortcomings, since the distribution of the loads throughout the network is stable. For example, in Figure 2a we observe that the most loaded links are concentrated around the node situated in Frankfurt, which corresponds to reality as Frankfurt is a major international interconnect node. Unfortunately, most traffic matrices from SNDLib have a similar distribution of the load.

To be able to analyse the efficiency of the algorithms, we would like to test them with different load distributions. When comparing two algorithms on the same network topology, one may behave better when the network load is concentrated in the centre, while another when the load is at the extremities or is uniformly distributed.

We generated multiple traffic matrices based on those from SNDLib. Each generated traffic matrix corresponds to a random permutation of the values of the 2450 flows. As a result, sometimes the most intensive flows have to traverse the entire network, other times are isolated at an extremity. Figure 2b shows different distributions of the initial network load.

To test the turn-on algorithms, we start by executing a turn-off algorithm which puts the least utilised links to sleep until no more links can be turned-off without provoking a congestion. After that, we increase the initial network load by an additive factor γ every second. The value of a flow at the time t of a simulation is equal to f a,b (t) = f a,b (0) * (1+γ * t).

To easily visualise the influence of this parameter, Figure 3 shows the variation of the total network load with different values of γ for a fixed traffic matrix. Hence, γ defines the speed of the increase of the traffic flows and allows to test the reactivity of the algorithm. In the most aggressive case, with γ = 0.08, the network load almost doubles in 5 seconds.

A total of 640 simulation runs were executed. Corresponding to 80 runs per γ with 20 different random load distribution per γ. Each simulation correspond to 50 seconds of network lifetime, as shown in Figure 3.

C. Avoiding Congestion

Intuitively, one can think that algorithms which turn-on multiple links at a time will result in a faster avoidance of the congestion, meaning that the network will not reach a state when packets will start being dropped in router queues.

Simulation results summarised in Figure 4 partially confirm that statement. Allon has the lowest number of lost packets, while STREETE-ON tends to have slightly worse results compared to other algorithms. However, it must be noted that the difference in number of lost packets is counted in tens of packets. With the simulated link speeds of 3Gbps (250k 1500byte packets per second) it corresponds to less than 0.05% packet lost on the link.

The results in terms of lost packets are difficult to evaluate, because they depend on many parameters. We can however affirm that under the tested network conditions with α = 0.8, with the propagation delay of Germany 50, with the tested traffic and selected γ values, all solutions are good in avoiding the congestion and only few packets are lost.

The results from Figure 4 include only the lost packets until the all-on network G become congested (part under the black 'congestion' line in Figure 3).

As the values do not differ much for different γ-values, we describe results for every second value of γ in Figure 4.

D. Impact on Energy Efficiency

Figure 5 shows the mean number of links on during the 50 seconds of simulation run. Each boxplot represents the distribution of the means over 100 runs of simulations for a corresponding γ. Each mean is calculated from samples taken every 1 second, i.e. it is a mean of 50 values: number of links on at t=1, t=2, ..., t=50.

When links are only turned on, the lower the boxplot, the more conservative the algorithm is, avoiding to turn-on unnecessary links. If all the links have the same transmission rate and energy consumption, turning-on less links results in less energy being consumed. Hence, the energy efficiency is better. Moreover, when used together with a turn-off algorithm, avoiding to turn-on unneeded links allows to avoid wakingup network interfaces which will be turned-off shortly after, effectively reducing the number of interface's power cycles.

It may be seen that with low values of γ, all the algorithms behave similarly. This is due to the network rarely reaching a congested state. In the small number of cases where turning on was necessary, the congestion was avoided by activating links at a time near the end of the simulation.

The allon algorithm is worse than others as it unnecessarily turns on all the network at the smallest sign of congestion. This tendency is also preserved at highest values of γ.

It is interesting to compare how our algorithm behaves when compared to other conservative algorithms like lastoff. Even though all the flows in the network increase by the same factor each second, turning on the last turned-off link is not the best solution. Actually, it will turn-on too many links. STREETE-ON is able to solve the congestion with less links. As expected, in terms of energy efficiency, the locality algorithm does not perform well. It turns-on many links around the place of congestion, which is sub-optimal. Hence, we can affirm that STREETE-ON can achieve better energy-efficiency for a network while avoiding congestion as good as the other analysed algorithms.

E. Computational Time

The simulations were performed on an Intel Xeon E5-2620 v2 processor running at 2.10GHz. The average execution time on all the simulation runs of STREETE-ON was of 33ms on the Germany 50 network. The maximum recorded execution time of the algorithm reached 150ms.

The implementation using the state of art dynamic graph allpair shortest path algorithm showed a very promising result, reducing the computational time from a couple of seconds observed in the case of a naive implementation with statistic Dijkstra computations.

The values of the executed time were computed via standard C++ tools: std::clock() and the CLOCKS_PER_SEC constant.

V. LIMITATIONS OF THE ANALYSIS

Multiple factors can change the outcome of the presented analysis. For example, the speed at which traffic increases may influence packet loss. We analysed this factor using the parameter γ, but under very fast traffic increase, such as when a link utilisation abruptly goes from 0 to 1, the following factors should be considered:

• Time to detect the traffic increase on network nodes.

• Network propagation time to inform the controller.

• Execution time of the algorithm. For any chosen algorithm, the first two factors will be equal and can hardly be optimised. However, the last factor depends on the computational complexity of the algorithm. The algorithm D-RRL used in our solution has an expensive worst-case complexity, but the worst-case does not happen in practice. Although preliminary tests on a 100-node network showed that the computational time of our solution starts to exceed one second -which is still a good result -we think that it may become a limiting factor in very large networks.

An interesting observation about the use of shortest path routing is that in some cases the congestion is worsened by turning on a link, which may not be intuitive. Figure 6 illustrates such a case. Two flows are routed in the network and, when the link hd is down, the flows take a detour over longer paths. As a result, none of the links is at critical load. If we turn-on the link, the flows are rerouted over hd and its utilisation rises almost leading to a congestion. The lines 24 -27 of STREETE-ON algorithm (Alg. 1) are used as a workaround to avoid never turning the links on. However, this solution is disputable. The analysis is performed here considered homogeneous links, whereas STREETE-ON can be extended to consider heterogeneous link speeds. We have chosen the value 0.8 for λ empirically, where a link is considered at high load and therefore close to congestion when it is 80% utilised. With smaller values of λ, less links will be turned off. With higher values, there is more probability to start dropping packets in router queues.

VI. CONCLUSION

Solutions for improving the energy efficiency of wired computer networks propose to turn the links off to reduce energy consumption. This paper proposed a reactive algorithm which dynamically monitors the network utilisation and turns the links back on when a state close to congestion is detected. The algorithm analyses simultaneously the actual state of the network with links turned off (G ), and the all-on state (G) in order to choose the best candidate links to be switched on. It provides a fast solution which rapidly reacts to a risk of congestion while avoiding to turn-on too many links, thus keeping a low energy consumption by the network.

  links (CL G ) e) (Ordered) candidate links f) Link turned on

Figure 1 :

 1 Figure 1: STREETE-ON: simulating the all-on network view to select the best link(s) to turn on

9 :

 9 sorted in descending order of utilisation in G 10: if congested = ∅ then 11: E ← E ∪ {e} Turn on the link e 12: congested af ter ← CL G ,T M 13: if congestion decreased then 14: if congested = ∅ and CLG,T M = ∅ then 25:result ← result ∪ (E \ E )

Figure 2 :

 2 Figure 2: Examples of G and G in the Germany 50 network

Figure 3 :

 3 Figure 3: Influence of γ on total injected traffic.

Figure 4 :

 4 Figure 4: Number of lost packets with different values of γ.

Figure 5 :

 5 Figure 5: Number of on with different values of γ.

9 fFigure 6 :

 96 Figure 6: Congestion avoidance by turning off

  • or not creating new congested links, while decongesting at least one of them: ( e s.t. e / ∈ congested and e ∈ congested af ter ) and (∃f s.t. f ∈ congested and f / ∈ congested af ter ) • or not creating new congested links, while decreasing the utilisation of at least one of congested: ( e s.t. e / ∈ congested and e ∈ congested af ter ) and

ACKNOWLEDGMENTS

This work is financially supported by the CHIST-ERA STAR [17] project.