Oleksiy Mazhelis

Martin Waldburger

Guilherme Sperb Machado

Burkhard Stiller

Pasi Tyrväinen

Retrieving Monitoring and Accounting Information From Constrained Devices in Internet-of-Things Applications

is envisioned to provide connectivity to a vast number of sensing or actuating devices with limited computational and communication capabilities. For the organizations that manage these constrained devices, the monitoring of each device's operational status and performance level as well as the accounting of their resource usage are of great importance. However, monitoring and accounting support is lacking in today's IoT platforms. Hence, this paper studies the applicability of the Constrained Application Protocol (CoAP), a lightweight transfer protocol under development by IETF, for efficiently retrieving monitoring and accounting data from constrained devices. On the infrastructure side, the developed prototype relies on using standard building blocks offered by the AMAAIS project in order to collect, pre-process, distribute, and persistently store monitoring and accounting information. Necessary on-device and infrastructure components are prototypically implemented and empirically evaluated in a realistic simulation environment. Experiment results indicate that CoAP is suited for efficiently transferring monitoring and accounting data, both due to a small energy footprint and a memory-wise compact implementation.

Introduction

Internet-of-Things (IoT) represents a vision for the future of information and communications technology wherein a variety of real-world "things" will be interacting and communicating with other virtual and physical entities through a global Internet infrastructure [START_REF] Atzori | The internet of things: A survey[END_REF]. It is envisioned that up to 50 Billion of devices will be Internet-connected by 2020 [START_REF]Ericsson: More Than 50 Billion Connected Devices[END_REF]. Many of these devices will be so-called constrained devices, i.e., devices with constraints on their memory size, computing power, communication capabilities, and/or available power [START_REF] Bormann | Terminology for Constrained Node Networks[END_REF].

In some application scenarios, e.g., as envisioned in the A 4 -Mesh project 3 , constrained devices are deployed in remote areas, where they run unattended for months or years, possibly without mains power. Users of these devices should have the possibility to monitor their operational status -e.g., available memory, remaining energy level, or detected errors -without the need to physically visit the deployment site. Resource usage may need to be accounted, too, both for network management purposes and, especially in case of multiple organizations requesting information from devices, for any potential charging and billing purpose. These information needs necessitate the implementation of an infrastructure to support an efficient monitoring and accounting for constrained devices.

The resource constraints of wireless sensor nodes impose constraints on suitable monitoring and accounting approaches and communication protocols. Since monitoring and accounting involves on-device metering of a device's technical parameters and resource usage, this metering process should be conservative in memory, code space, and power expenditure, to accommodate limited capabilities and restricted battery power of the devices. This may render an application of traditional approaches -e.g., those based on Simple Network Management Protocol (SNMP) [START_REF] Kuryla | Evaluation of the resource requirements of snmp agents on constrained devices[END_REF] -suboptimal for devices with strong resource constraints.

Hence, this paper aims at extending IoT applications with monitoring and accounting functionality. Rather than introducing a new communications protocol to implement this functionality, this paper focuses on studying the applicability of a standard communication protocol for constrained devices -in particular, the Constrained Application Protocol (CoAP) that was introduced as a lightweight alternative to HTTP and optimized to work in constrained environments [START_REF] Bormann | Coap: An application protocol for billions of tiny internet nodes[END_REF]. The research question addressed in this paper can be formulated as follows: Is it feasible to utilize CoAP as a transfer protocol for retrieving the information needed for monitoring and accounting purposes as metered on constrained devices?

To support the efficient processing and storage of this information, this work relies on using the accounting and monitoring infrastructure produced by the Accounting and Monitoring of Authentication and Authorization Infrastructure Services (AMAAIS) project [START_REF] Stiller | Accounting and monitoring of AAI services[END_REF] which provides components for accounting and monitoring of IT services. In response to the research question, the design and implementation of a prototype has been undertaken. Specifically, the functionality of AMAAIS is extended with (i) a metering component deployed on constrained devices in order to obtain relevant operational parameters and resource usage information, and (ii) a networked accounting application component. This networked accounting application is integrated with the core AMAAIS infrastructure and communicates with the metering component using CoAP as a transfer protocol. Finally, the performance of the prototype is evaluated regarding memory footprint and power consumption of the on-device metering process.

The reminder of this paper is organized as follows. In the next section, relevant terminology is introduced, and related work in the domain of constrained device management is overviewed. Key elements of the AMAAIS infrastructure are described in Section 3, along with the changes needed to make it applicable to a constrained environment. Details of the prototype implementation and its performance evaluation are presented in Section 4. Finally, in Section 5, obtained results are summarized, and directions to further work are outlined.

This section provides definitions for relevant terms, and overviews management mechanisms available for constrained devices in general and for retrieving monitoring and accounting information in particular.

Terminology. Constrained devices can be categorized into (i) Class-0 devices ( 10 kByte of RAM and 100 kByte of ROM) only capable of engaging in simple communication scenarios with the help of a proxy or gateway, (ii) Class-1 devices (≈10 kByte of RAM and ≈100 kByte of ROM) powerful enough to directly communicate with their peers in the Internet via lightweight protocols, and (iii) Class-2 devices (≈50 kByte of RAM and ≈250 kByte of ROM) whose capabilities are sufficient to support full-fledged protocols used in conventional network nodes [START_REF] Bormann | Terminology for Constrained Node Networks[END_REF]. Among these three categories, Class-1 devices, being both inexpensive and capable of communicating with their peers in the Internet, are believed to play an important role in emerging IoT applications [START_REF] Bormann | Coap: An application protocol for billions of tiny internet nodes[END_REF]. Class-1 devices therefore determine the main focus of this work.

The management of constrained devices requires a broad set of functionality to be implemented to efficiently configure, monitor, and control them. As these devices are managed as a part of the network to which they belong, the core operational network management functions that are conventionally grouped along the five functional areas of fault, configuration, accounting, performance and security [START_REF]TMN management functions[END_REF], are also relevant for managing constrained devices and networks thereof [START_REF] Ruiz | MANNA: a management architecture for wireless sensor networks[END_REF]. Many of these functions are enabled by the so-called metering process whereby technical parameters of a particular resource are identified and current usage of the resource is determined. The metering process can be triggered by signaling or other external polling events, or alternatively it can be performed periodically or according to a statistical sampling scheme [START_REF] Karsten | Charging for packet-switched network communication-motivation and overview[END_REF].

In the context of this paper, the focus is restrained to accounting functionality and performance management (specifically, performance monitoring) functions. Extensions to include other management functions are outside of the scope of this paper -they are left for further work.

Requirements for managing networks with constrained devices are being defined by the Constrained Management (COMAN) -a recently established IETF activity [START_REF] Ersue | Management of Networks with Constrained Devices: Use Cases and Requirements[END_REF]. On a general level of a management architecture/system, the set of requirements relevant to monitoring and accounting functions include the following needs: (i) to minimize the state maintained on constrained devices, (ii) to support devices that are not always on-line, (iii) to support lossy and unreliable links, through in-built resilience mechanisms and through a limited data rate, (iv) to keep the encoding of management data compact, and (v) to optionally compress management data or complete messages. At the implementation-level, with the aim of minimizing communication overhead, two mandatory requirements are stated:

-Avoid complex application layer transactions with large messages, since they require large memory buffers and increase the volume of re-transmissions.

-Avoid the fragmentation and reassembly of messages at multiple protocol stack layers, e.g., by limiting the size of application layer messages.

Ersue et al. [START_REF] Ersue | Management of Networks with Constrained Devices: Use Cases and Requirements[END_REF] specify a number of monitoring functions for Class-1 devices; among these, only the monitoring of device status and energy level are considered mandatory, whereas all other are optional to implement depending on the device type and management needs. The document also mandates a number of security functions, including the need for authentication and access control (both on constrained devices and in the management system) as well as the need for a security bootstrapping mechanism.

The focus in this paper is on the acquisition of dynamic information for monitoring and accounting purposes, and an assumption is taken that static management information can be obtained out of band by other means. Specifically, this paper aims at equipping IoT applications with the mandatory monitoring functionality set in [START_REF] Ersue | Management of Networks with Constrained Devices: Use Cases and Requirements[END_REF], including device status monitoring and energy status monitoring, while also satisfying the respective other architectural-and implementation-level requirements.

Management architecture and protocols for constrained devices. The resource constraints of wireless sensor nodes impose constraints on suited communication protocols and management methods. In order to cope with the specifics of networked constrained devices, Ruiz et al. have introduced MANNA [START_REF] Ruiz | MANNA: a management architecture for wireless sensor networks[END_REF], a management architecture for Wireless Sensor Networks (WSN) based on manageragent interactions. The authors specified relevant management functions and considered the WSN information model, although an empirical evaluation of the proposed architecture has not been reported. Likewise, an agent-manager interaction is assumed in the WSN management system [START_REF] Ma | An efficient management system for wireless sensor networks[END_REF] which relies on SNMP and implements configuration, performance, and fault management functions for TinyOS devices. The system has been prototypically implemented; however, the performance of the management architecture and its overhead are not reported.

A number of studies were aimed at applying standard IP tools, such as SNMP and NETCONF [START_REF] Enns | Network Configuration Protocol (NETCONF)[END_REF] -a protocol used for manipulating the configuration of a network device -for device management purposes. Under the assumption that standard SNMP tools require a large Management Information Base (MIB) and result in noticeable message overhead, attempts are made at optimizing the SNMP architecture and tailoring these protocols, e.g., by limiting the set of functionality, or by introducing a gateway to mediate between standard protocols and tailor-made monitoring agents on constrained devices. In particular, this approach is followed by the LoWPAN Network Management Protocol (LNMP) [START_REF] Mukhtar | Lnmp -management architecture for ipv6 based low-power wireless personal area networks (6lowpan)[END_REF], 6LoWPAN-SNMP [START_REF] Choi | 6lowpan-snmp: Simple network management protocol for 6lowpan[END_REF], and EmNetS Management Protocol (EMP) [START_REF] Chaudhry | Emp: A network management protocol for ip-based wireless sensor networks[END_REF].

Kuryla and Schönwälder [START_REF] Kuryla | Evaluation of the resource requirements of snmp agents on constrained devices[END_REF] have studied the feasibility of implementing SN-MPv1 and SNMPv3 message processing models as an SNMP agent for Contiki OS. To meet the hardware constraints, only Get, GetNext and Set operations were implemented, and simplifications to the modular SNMP architecture were made. The implementation reportedly has a relatively modest memory footprint and a short processing delay of 40-120 ms; however, it does not support notifica-tions (Trap and Inform), and thus implies the need for the manager component to explicitly request information from an on-device agent. Sehgal et al. [START_REF] Sehgal | Management of resource constrained devices in the internet of things[END_REF] have empirically compared SNMP against a lightweight version of NETCONF, without subtree filtering and the edit-config operation, in the context of constrained devices. As NETCONF relies on the exchange of relatively large XML messages, its use in constrained devices results in longer processing time, as well as in an increased memory footprint [START_REF] Sehgal | Management of resource constrained devices in the internet of things[END_REF].

Instead of tailoring traditional protocols designed for non-constrained devices, an alternative approach is to re-use CoAP for device management purposes. CoAP is a new transfer protocol introduced as a lightweight alternative to HTTP. It is optimized to work in constrained environments [START_REF] Bormann | Coap: An application protocol for billions of tiny internet nodes[END_REF][START_REF] Shelby | Embedded web services[END_REF]. CoAP relies on UDP as a transport, and offers a simple in-built stop-and-wait reliability mechanism. It uses a compact four-byte binary header with a total header size of 10 to 20 Byte, and defines four methods -GET, POST, PUT, and DELETE -enabling a RESTful architectural style. Importantly, the protocol supports an asynchronous retrieval of information by using the "Observe" option: by issuing specially crafted GET requests, clients subscribe to the updates of a resource of interest; after that, the device asynchronously notifies its observers about resource changes, without the need for explicit polling requests. All that makes messages compact, minimizes the overall volume of the transferred data, and reduces the complexity of implementation -all crucial characteristics in constrained environments.

To the best knowledge of the authors, the use of CoAP for device management purposes has not been tried in practice yet, though this is considered in the LightweightM2M standard under development by OMA4 . Sehgal et al. [START_REF] Sehgal | Management of resource constrained devices in the internet of things[END_REF] suggest the suitability of CoAP for accessing on-device configuration data, while also indicating the lack of practical experience. For these considerations, the applicability of CoAP for the purpose of retrieving metering information from constrained devices is investigated in this paper.

Adapting AMAAIS infrastructure to IoT applications

The AMAAIS project aims at supporting the accounting and monitoring of IT services by offering a set of enabling components and facilitating their integration with an authentication and authorization infrastructure [START_REF] Stiller | Accounting and monitoring of AAI services[END_REF]. The infrastructure produced by AMAAIS is well suited for federatively aggregating, processing, and storing accounting and monitoring information. This infrastructure, however, has not been designed for constrained devices, and hence needs to be tailored to be suitable in constrained environments. This section overviews the AMAAIS infrastructure and considers the changes that are needed for making it work in applications with Class-1 devices.

The interplay of AMAAIS accounting applications and AMAAIS core components is visualized in Figure 1(a). Any service-specific Accounting Application (AA) is responsible for generating events, e.g., by parsing system log files and extracting any information of interest from them. Once a new event is created, the Accounting Client (AC) API is called. Both AA and AC are running on the same host as a daemon. Once an event generated by an AA is pushed to the AC, it enters the AC pipeline. The event will pass along the AC's pipeline, will be then transmitted to one or multiple Accounting Servers (AS), pass along the respective AS pipeline(s), and will be persisted to database eventually. The communication between AC and AS is based on exchanging Security Assertion Markup Language (SAML) messages. AC and AS pipelines are constituted from so-called Sources and Sinks. Sinks are used to receive and process events, and Sources are components that produce events. AMAAIS provides purpose-specific sub-types of Sinks and Sources. In principle, it is possible to enable monitoring and accounting functionality on constrained devices by deploying AA and AC components directly on the device. However, for Class-1 devices (which determine the main focus in this paper), this is not feasible due to memory constraints and the lack of Java support, not to mention a large computational and data communication overhead while being engaged in an exchange of SAML messages.

Hence, in order to cope with the limitations of constrained devices, it is reasonable to implement the AA and AC outside of any constrained device, for instance, on a gateway between constrained and unconstrained networks, or on another unconstrained node, as shown in Figure 1(b). This way, the functionality to be kept on constrained device can be limited to a lightweight agenta meter -responsible for executing the metering process and transmitting the metered information to the AA executed on a remote host by using a suitable communication protocol (thus, called Networked AA in Figure 1(b)). CoAP is used as a data transfer protocol for this part of the communication.

Prototype implementation. For prototyping purposes, existing AMAAIS components have been extended by a networked AA and an on-device meter, as described below.

The meter software agent has been implemented for TmoteSky, a sensor mote platform featuring an MSP430 16-bit 3.9 MHz CPU, a CC2420 radio chip, as well as 48 kByte of program flash and 10 kByte of RAM. A ready set of software components, including Contiki OS and networking libraries were utilized in the implementation. For evaluation purposes, the meter software has been deployed in the Cooja simulation environment, which emulates TmoteSky motes and enables a simultaneous simulation at network level, operating system level, and machine code instruction set level [START_REF] Osterlind | Cross-level sensor network simulation with cooja[END_REF].

As the CoAP engine for Contiki OS, the Erbium CoAP implementation [START_REF] Kovatsch | A low-power coap for contiki[END_REF] has been used. The meter agent is responsible for gathering and transmitting the following attributes: event identifier, remaining battery level, operational status of the device, available memory, as well as the name of the device and the uptime at which the metering process has been performed. The number of packets sent, received, or dropped has not been metered in the prototype, as these attributes are considered optional for constrained devices. Along with the management attributes listed above, also temperature and light sensor readings are transferred. Integrating such application payload with the accounting and monitoring information within a single message allows data communications overhead to be minimized and hence battery lifetime at a device to be prolonged.

In order to avoid packet fragmentation and reassembly, the size of a CoAP message shall not be longer than 80 Byte [START_REF] Jennings | Media Types for Sensor Markup Language (SENML)[END_REF]. This is also important, since CoAP's "Observe" option assumes short notification messages, fitting into a single packet. Therefore, to keep messages compact and to simplify the implementation, a simple comma-separated value (CSV) format was used for message encoding. While the Efficient XML Interchange (EXI) representation defined by SenML [START_REF] Jennings | Media Types for Sensor Markup Language (SENML)[END_REF] may offer a more compact encoding that allows messages to be compressed to as little as 3% of the original size [START_REF] Shelby | Embedded web services[END_REF], the CSV encoding was also found sufficiently compact, allowing the message size to be below 80 Byte.

The metering process was implemented to be executed periodically, with a configurable metering interval. Both subscribing to periodic metering updates and setting of the metering interval are done in a RESTful manner by issuing GET (with the "Observer" option set) and PUT requests, respectively.

In order to reduce energy consumption by the transmitter, the meter uses the ContikiMAC radio duty cycling (RDC) protocol [START_REF] Dunkels | The ContikiMAC Radio Duty Cycling Protocol[END_REF]. Two versions of the meter were implemented:

-With RDC enabled all the time. This version is aimed at application scenarios where a device needs to be constantly available, e.g., for retrieving metered information or for device configuration. For instance, a weather monitoring station may need to be ready to deliver instant measurements of wind strength and direction whenever requested.

-With radio disabled between communication sessions and only being switched on for a relatively short duration of time (10 s) to acquire and transmit metered information or re-configure the device. This version is suitable for scenarios where energy efficiency is of prime concern, and where periods of unavailability can be tolerated.

The networked AA (NAA) has been implemented in Java and integrated with the AMAAIS core components 5 . For communication with constrained devices, the NAA employs the Californium Java framework6 that implements CoAP communication primitives. Once launched, the NAA connects to each of the constrained devices and subscribes to the metering information updates by issuing GET requests with the "Observe" option.

From that point on, the NAA periodically receives messages with metered information, parses them, and forms accounting events which are then dispatched, through the AC API, to a pre-defined processing pipeline. For prototypical purposes, a simple pipeline was configured consisting of a filtering Sink and two persistence Sinks as well as the respective communication channels between them. The filtering Sink allows individual attributes to be excluded from further processing; for simplicity, the filter in the prototype was configured to let all the event attributes pass. In turn, the persistence Sinks are responsible for storing newly created events in two separate databases.

Performance evaluation. As was discussed in Section 2, in applications dealing with constrained devices, the management functionality shall acquire and expose at the very minimum information about device status and about device energy parameters. Further, this functionality should require a minimal state to be maintained on the devices, support lossy and unreliable links, and keep the encoding of management data compact. Finally, authentication, access control, and security bootstrapping mechanisms shall be provided.

These requirements have been taken into account when designing and implementing the prototype. In particular, the prototype enables acquiring and delivering mandatory information, i.e., device status and energy level, as well as the optional information about available memory. By means of CoAP resilience mechanisms, support for lossy and unreliable network connection is provided. The use of CSV as a data encoding format allows the encoding to be compact and hence helps avoid any need for fragmentation and message reassembly. A compact representation, along with the RESTful methods of CoAP, also enable simple and small application level transactions. It shall be noted that security mechanisms were omitted when implementing the prototype; implementing them has been postponed until the CoAP DTLS security specifications are finalized.

The implementation of the meter is quite compact and requires only 1286 Byte of ROM and 158 Byte of RAM. Together with the operating system and other necessary libraries (RPL, uIP, ContikiMAC, Erbium, etc.), the overall application memory footprint is 48638 Byte of ROM and 8732 Byte of RAM.

Both versions of the meter were experimented with. The power consumption at a constrained device has been estimated with the help of the Contiki OS' Energest module [START_REF] Dunkels | Software-based sensor node energy estimation[END_REF], which traces the time a device spends in different modes of operation. Five different metering intervals were used: 10 s, 30 s, 120 s, 300 s, and 1200 s. For each metering interval value, the operation of the meter was simulated over a duration of 50 metering intervals, and the medians of the obtained power consumption estimates have been evaluated, as shown in Fig. 2. With the version of the meter with the RDC always on, the radio receiver periodically awakes, by default with a frequency of 8 Hz, to check for radio activity. This is valuable when a device needs to be always available for metering and/or reconfiguration. However, as a result, even for longer metering intervals, the incurred reception-related energy footprint remains significant (τ → ∞ ⇒ P rx → const > 0, where τ is the length of the metering interval), as visible in Fig. 2(a).

On the other hand, for the second version of the meter, which disables the radio completely between metering and communications sessions, the receptionrelated energy drainage is minimized (τ → ∞ ⇒ P rx → 0, cf. Fig. 2(b)). Due to this, the power consumption at the device decreases rapidly as the metering interval grows, at the expense of the device being available only periodically.

Assuming that a constrained device is powered by a pair of AA Zync-carbon batteries, the expected battery lifetime has been estimated and is reported in Table 1. As the table indicates, even with short metering intervals of 10 s, the battery lifetime is approaching half a year. With RDC always enabled, the battery lifetime increases insignificantly with the metering interval, extending the battery lifetime maximum by less than a month. On the other hand, when RDC is enabled periodically, the battery lifetime can be extended to 1.5 years and above, thus, approaching the self-discharge time of a battery. It shall be noted that energy consumption at a constrained device is affected by multiple factors, including the overhead of the routing protocol, the type of low power mode used, the time needed for sensors to initialize after being turned on again, etc. Therefore, the absolute numbers of energy consumption estimates reported above shall be used with care, as they are likely to differ to a certain extent depending on case-specific implementation details.

Summary and concluding remarks

The management of constrained devices in general, and in particular, the monitoring of their operational status and performance level, as well as the accounting of resource usage of these devices are of great importance for applications in the emerging IoT field. For organizations implementing or deploying IoT applications, the availability of monitoring and accounting information offers numerous benefits, such as better granularity of charging and billing information, support for device status monitoring and troubleshooting, and support for performance optimization and network planning.

This work has studied the applicability of CoAP, a lightweight IETF protocol under development, for acquiring and transmitting management information from the constrained devices. As a part of the study, a meter component responsible for acquiring and transmitting the management information has been prototypically implemented. On the infrastructure side, for storing, processing, and distributing management information retrieved from constrained devices, the meter has been integrated with AMAAIS core components, which provide standard building blocks for the accounting and monitoring of IT services.

Based on results obtained from experiments with the implemented prototype, CoAP has been found suitable for transferring monitoring and accounting information from constrained devices. Its strong sides include the simplicity and compactness of the implementation, as well as a small energy footprint attributed to a small size of messages being transferred and the use of the observer design pattern. The protocol is especially suitable in application scenarios where it is also utilized for exchanging application-specific information, since in this case the protocol implementation code can be reused and hence the size of memory required can be minimized.

The impact of the metering process on device battery lifetime depends on whether a constrained device needs to be constantly available. In case periods of unavailability can be tolerated, estimated battery lifetime is rather long, reaching 1.5 years in the experiments conducted. On the other hand, making a constrained device available all the time shortens the battery lifetime considerably, with the maximum of circa six months according to estimates obtained in the experiments.

The use of CoAP also imposes some constraints on the management functionality implementation. Specifically, it restricts the volume of information that can be retrieved without making the implementation more complex and/or less energy efficient. This is due to the fact that the use of the "Observe" option of the protocol assumes that information is transmitted within a single CoAP package, which, to avoid packet fragmentation and reassembly, effectively limits the size of a message to circa 80 Byte -leading in the prototype to a reduced number of messages transmitted, implying a positive effect on energy consumption.

The use of the "Observe" option also brings the need to confirm successful message reception, as otherwise, according to CoAP specifications, the subscription to metered information updates is canceled. This implies that a connection loss will nullify a subscription, and its re-initiation shall be implemented by the networked Accounting Application. It should be mentioned that the CoAP standardization process is not completed yet, and therefore some changes may still be introduced, possibly making these side effects less restrictive.

While this work was, thus, able to provide an answer to its research question, it sees several limitations that shall be addressed in future work. In particular, the prototype implementation shall be expanded to allow additional ways of triggering the metering process, include additional attributes to be metered at constrained devices, and allow a reconfiguration of metering process parameters. Once the specification of CoAP DTLS security is finalized, the prototype shall be equipped with the required security mechanisms. Finally, performance characteristics of the prototype shall be empirically evaluated in field experiments.

Fig. 1 .

 1 Fig. 1. AMAAIS components and adaptations for constrained environments

Fig. 2 .

 2 Fig.2. Power consumption at a constrained device, both total and according to modes of operation including CPU active (cpu), low power mode (lpm), transmission (tx), and reception (rx): (a) RDC always on; (b) RDC on periodically. Note that a logarithmic scale is used for the metering interval shown on the x-axis.

Table 1 .

 1 Estimated constrained device's battery lifetime (in days)

	Radio mode	Interval, s
		10 30 120 300 1200
	RDC is always enabled 169 189 194 197 196
	RDC is on periodically 167 324 484 550 588

https://a4-mesh.unibe.ch/

http://member.openmobilealliance.org/ftp/Public_documents/DM/ LightweightM2M/

Available at http://www.csg.uzh.ch/research/amaais.html

Available at http://people.inf.ethz.ch/mkovatsc/californium.php

Acknowledgements

This work has been performed partially in the framework of the AMAAIS project as part of the "AAA/SWITCH e-infrastructure for e-science" programme under the leadership of SWITCH, the Swiss National Research and Education Network, and has been supported by funds from the State Secretariat for Education and Research (SER). The work has been also partially carried out within the framework of the Internet of Things Program of TIVIT Oy nominated to organize and manage the programs of the Strategic Center for Science, Technology and Innovation in the field of ICT funded by the Finnish Funding Agency for Technology and Innovation (TEKES).


Sebastian Abt
email: sebastian.abt@h-da.de

Christian Dietz
email: christian.dietz@h-da.de

Harald Baier
email: harald.baier@h-da.de

Slobodan Petrović
email: slobodan.petrovic@hig.no

Passive Remote Source NAT Detection using Behavior Statistics Derived from NetFlow

Keywords: Network Address Translation, NAT detection, NetFlow, C4.5, SVM

Network Address Translation (NAT) is a technique commonly employed in today's computer networks. NAT allows multiple devices to hide behind a single IP address. From a network management and security point of view, NAT may not be desirable or permitted as it allows rogue and unattended network access. In order to detect rogue NAT devices, we propose a novel passive remote source NAT detection approach based on behavior statistics derived from NetFlow. Our approach utilizes 9 distinct features that can directly be derived from Net-Flow records. Furthermore, our approach does not require IP address information, but is capable of operating on anonymous identifiers. Hence, our approach is very privacy friendly. Our approach requires only a 120 seconds sample of NetFlow records to detect NAT traffic within the sample with a lower-bound accuracy of 89.35%. Furthermore, our approach is capable of operating in real-time.

Introduction

Network Address Translation (NAT) [START_REF] Egevang | The IP Network Address Translator (NAT). Request For Comments 1631[END_REF] is a technique commonly employed in computer networks to hide a number n of computing resources behind a, typically smaller, number m ≤ n of IP address resources. The motivation for deploying NAT nowadays is twofold: (i) IP address conservation and (ii) security. The first motivation comes with the continuing growth of the number of Internet connected devices and, consequently, the continuous depletion of public IP version 4 address resources. The second motivation is based on the assumption that utilizing NAT efficiently hides internal network structures to the outer world. In fact, directly connecting to a host behind a NAT gateway from outside the NAT network is typically not possible.

From a network management and network security point of view, NAT may not always be desirable or permitted: enterprise networks typically enforce strict security and management policies on connected devices in order to prohibit unwanted or illegal use of computing or network resources and to limit spread of malware. Such policies can be circumvented by connecting private devices to an enterprise network via NAT. Additionally, telecom operators and Internet Service Providers (ISPs) may prescribe bounds on the number of devices concurrently connected to a single Internet access point (e.g. 3G/4G connection sharing). Such limitations can easily be circumvented by connecting a NAT gateway to the Internet access point and covering further hosts behind this gateway.

In order to be able to identify such security and policy violations, we present a novel approach to remote source NAT detection by applying machine-learning algorithms to user behavior statistics derived from NetFlow [START_REF]NetFlow Services Solutions Guide. Internet resource[END_REF] data. Our approach works completely passively, i.e. it does not require interaction with the monitored hosts. It can be implemented at any position within a computer network and is capable of detecting NAT with just a 120 seconds sample of NetFlow records with a lower-bound accuracy of 89.35%, outperforming existing related work. Furthermore, our approach respects privacy of end-users, which is especially important for enterprise networks: as our approach is completely based on information derived from NetFlow data, no payload has to be processed. Additionally, our approach does not rely on original IP addresses. Instead, it is capable of operating on anonymized identifiers. Finally, due to the volume reduction performed by NetFlow, our approach is very light-weight and capable of operating at very high traffic rates. We refer to our approach as being remote, based on the locality of the observation point: we expect the NAT detector to be outside the NAT network. No such passive remote NetFlow based approach exists today.

The remainder of the paper is structured as follows: Section 2 introduces the necessary background on NAT, NetFlow and machine learning algorithms. Section 3 discusses related work in the field of NAT detection. Section 4 sketches our novel approach. Section 5 describes our testing environment and discusses the performance of our approach. Finally, the conclusion and outlook for future work is given in Sect. 6.

Background

This section introduces fundamentals of NAT (Sect. 2.1), NetFlow (Sect. 2.2) and machine learning (Sect. 2.3) which will be required in the rest of the paper.

Network Address Translation

Network Address Translation (NAT) [START_REF] Egevang | The IP Network Address Translator (NAT). Request For Comments 1631[END_REF] is a technique commonly employed in computer networks to hide a number n of computing resources behind a number m ≤ n of IP address resources. For NAT to work, at least one NAT gateway with two network interfaces, i.e. internal and external network interface, is required. By performing NAT, the NAT gateway connects the inside to the outside network and vice versa. addresses routable in the outside network. Inside, n ≥ m IP addresses may be used that potentially cannot be routed in the outside network. To connect the inside network with the outside network, the NAT gateway has to rewrite source or destination IP address of any outgoing or incoming IP packet, respectively. This process is commonly referred to as address translation. In order to avoid collisions and to correlate sessions when addresses are translated, NAT gateways maintain a session table containing a mapping of the original IP address, the NAT IP address it got rewritten to and the rewrite direction, i.e. inside vs. outside. We differentiate between the following NAT mechanisms:

Source NAT With source NAT, the IP addresses of the inside network are hidden from the outside network. For every outgoing packet, the NAT gateway has to rewrite the source IP address to one of the addresses assigned to its external interface. Source NAT is typically employed to connect one or more computing resources to the Internet (e.g. DSL dial-up). A typical source NAT setup is depicted in Fig. 1. Destination NAT In case of destination NAT, the NAT gateway translates destination IP addresses of incoming IP packets to specific addresses of the inside network. This mode of operation is commonly employed to forward specific ports to a specific host serving incoming requests on these ports. Static NAT Static NAT is a basic mode of operation in which the NAT gateway always translates one original IP address to the same NAT IP address. Hence, the NAT gateway maintains a static bijection. Dynamic NAT Dynamic NAT is a more complex mode of operation in which the NAT gateway maps IP addresses dynamically to a pool of NAT IP addresses. The condition for a mapping to happen is that the NAT IP address is currently not bound to a different original IP address, i.e. that there is no active entry in the session table for a specific NAT IP address. The actual mapping process is vendor specific. NAT overload NAT overload is commonly also referred to as Port and Address Translation (PAT) and is typically employed in source NAT scenarios.

In contrast to static and dynamic NAT, a NAT gateway configured with NAT overload not only translates the original IP address to the NAT IP address, but also rewrites source or destination port numbers of the underlying flows. This mode of operation is typically deployed in cases where n m. Additionally, this mode of operation is commonly found on smalloffice-home-office (SOHO) NAT gateways.

For the remainder of this work, when referring to NAT, we refer to source NAT with NAT overload configured in a usual way.

NetFlow

NetFlow is a technology first introduced by Cisco Systems [START_REF]NetFlow Services Solutions Guide. Internet resource[END_REF] that enables monitoring of network flows. A network flow is a unidirectional data stream between two communicating hosts that shares common attributes at the network (L3) and transport layers (L4). A network flow comprises packets offering the same source and destination IP addresses, source and destination port numbers, and the layer 4 protocol type number within a given period of time. More formally, we write a network flow as a 5-tuple, which we denote by f , i.e. we have f = (srcIP, dstIP, srcP ort, dstP ort, L4P roto). The attributes constituting a network flow f are called flow keys [START_REF] Claise | Specification of the IP Flow Information Export (IPFIX) Protocol for the Exchange of IP Traffic Flow Information[END_REF]. Using NetFlow, it is possible to collect and export statistics corresponding to network flows on IP routers. Specifically, using currently widely deployed versions of NetFlow, i.e. NetFlow versions 5 and 9, routers can export information on bytes and packets transferred, TCP flags set as well as start and end time of a flow and its time duration.

Being a compression function, NetFlow greatly reduces the amount of data to process. This is due to the fact that NetFlow not only aggregates consecutive IP packets sharing the same flow keys within a specific period of time, but alsoin contrast to e.g. the Deep Packet Inspection (DPI) based approaches -does not export any payload information. As benefit of this property, using NetFlow for NAT detection instead of full packet captures protects privacy of communicating hosts better than DPI based approaches can do. However, this limited amount of per-packet information possibly makes the detection process more difficult.

Machine Learning

As already mentioned in Sect. 1 our aim is to apply two machine learning algorithms to behavior statistics derived from NetFlow. The following two paragraphs briefly describe foundations of Support Vector Machines (SVMs) and the C4.5 decision tree algorithm. Finally, we formally describe the measures we use to compare our results.

Support Vector Machines An SVM is a supervised learning approach that can be applied to linear and non-linear classification problems [START_REF] Boser | A training algorithm for optimal margin classifiers[END_REF]. These are suitable for learning on a large set of examples and because of that they are commonly used in traffic classification [START_REF] Dyer | Peek-a-Boo, I Still See You: Why Efficient Traffic Analysis Countermeasures Fail[END_REF][START_REF] Li | A Semi-Supervised Network Traffic Classification Method Based on Incremental Learning[END_REF][START_REF] Tabatabaei | Early internet traffic recognition based on machine learning methods[END_REF] and anomaly detection systems [START_REF] Francois | SAFEM: Scalable analysis of flows with entropic measures and SVM[END_REF][START_REF] Hsu | Fast-Flux Bot Detection in Real Time[END_REF][START_REF] Barthakur | A Framework for P2P Botnet Detection Using SVM[END_REF]. Unlike other classification algorithms, SVMs tend to use all the available features by combining them in a linear way. In general, an SVM tries to fit a model to a given classification problem by computing a set of maximummargin hyperplanes separating the classes of interest. If the classes of a specific classification problem cannot be separated linearly using the feature vectors at hand, SVMs transform the input data, i.e. feature vectors, to higher-dimensional feature vectors by applying a kernel function K(x, y) to it. This process is referred to as the kernel trick.

C4.5 Decision Tree The C4.5 algorithm [START_REF] Quinlan | C4.5: programs for machine learning[END_REF] is one of the most popular decision tree algorithms. A decision tree is a tree structure that consists of decision nodes and leaves. Decision nodes consist of tests on features and leaves represent classes. C4.5 tries to fit a model to a given classification problem by recursively generating such trees. For each decision node, C4.5 computes normalized information gain of the remaining features. A feature is chosen as a decision criterion, i.e. as a new child node, if normalized information gain of a test computed on that feature is the maximum. This process is repeated for each decision node.

Performance Measures In machine learning, performance of algorithms is usually expressed in the number of false-positives, true-positives, false-negatives and true-negatives. Let X = {(x 1 , e 1 , c 1 ), (x 2 , e 2 , c 2 ), . . . , (x n , e n , c n )} denote a data set of n k-dimensional feature vectors x i ∈ R k (i, k, n ∈ N) with corresponding a-priori labels e i ∈ {0, 1} and labels c i ∈ {0, 1} assigned a-posteriori by a specific binary classifier C : R k → {0, 1}. Then, we measure false-positives

F P = {x i ∈ X |e i = 0 ∧ c i = 1}, true-positives T P = {x i ∈ X |e i = 1 ∧ c i = 1}, false-negatives F N = {x i ∈ X |e i = 1 ∧ c i = 0} and true-negatives T N = {x i ∈ X |e i = 0 ∧ c i = 0}.

Related Work

NAT detection is a long lasting field of research. As such, different active NAT detection approaches, i.e. approaches actively sending and receiving IP packets, were proposed in the past [START_REF] Rosenberg | Session Traversal Utilities for NAT (STUN). Request For Comments 5389[END_REF][START_REF] Wei | A New Method for Symmetric NAT Traversal in UDP and TCP[END_REF]. These approaches perform NAT detection from the inside network, usually initiated by a specific application. In contrast to this, our goal is a passive NAT detection from the outside network.

Several approaches for passive NAT detection from the outside of a network already exist. However, most of them rely on raw packet information. For example, Bellovin [START_REF] Bellovin | A technique for counting natted hosts[END_REF] presents, a method relying on special packet header fields, like for example the IP ID or TCP window size. Moreover in [START_REF] Bi | Security enhancement by detecting network address translation based on instant messaging[END_REF] a method for detecting NAT based on instant messaging traffic of different active hosts is described. In addition, Kohno et al. [START_REF] Kohno | Remote Physical Device Fingerprinting[END_REF] present a method to detect NAT based on passively fingerprinting devices by detecting clock skews in physical devices. Furthermore, recent research regarding tethering detection in mobile broadband networks contributes to the NAT detection problem as well. Schulz et al. [START_REF] Schulz | Tetherway: a framework for tethering camouflage[END_REF] describe a tethering detection approach combining and applying different techniques on three different classes of data, namely network layer data, application layer data as well as behavior and meta data. Even though their approach aims to perform the detection on the ISP side, it is rather specialized to mobile networks.

In contrast to all previous mentioned methods, our approach works completely passively and is based on NetFlow data only. In Krmíček et al. [START_REF] Krmíček | Netflow Based System for NAT Detection[END_REF], a NetFlow based system for NAT detection is introduced. However, [START_REF] Krmíček | Netflow Based System for NAT Detection[END_REF] utilizes IP ID and IP TTL information, which are limited to specific NetFlow versions not commonly available in ISP networks [START_REF] Steinberger | Anomaly detection and mitigation at Internet scale: A survey[END_REF]. Rui et al. [START_REF] Rui | Remote NAT Detect Algorithm Based on Support Vector Machine[END_REF][START_REF] Rui | Passive NATted Hosts Detect Algorithm Based on Directed Acyclic Graph Support Vector Machine[END_REF] propose approaches to NAT detection and size estimation of the inside network using SVM and directed acyclic graph SVM [START_REF] Platt | Large Margin DAGs for Multiclass Classification[END_REF], respectively. Their work relies on 8 features consisting of statistics of transferred IP packets as well as of a subset of flags of the TCP header. As this feature set can be derived from NetFlow data, we consider that work equivalent to our approach in terms of objectives. The set of network traces captured and used by Rui et al. [START_REF] Rui | Remote NAT Detect Algorithm Based on Support Vector Machine[END_REF] for training and evaluation consists of 1, 637, 550 packets of 5 hosts. One of the hosts under observation was not placed behind a NAT gateway (436, 320 packets), while the remaining four hosts generated NAT traffic (1, 201, 230 packets). Thus, approximately 75% of the traffic used for SVM training and testing was NAT traffic. By applying SVM with a radial basis function (RBF) kernel, Rui et al. achieved a detection accuracy of 71.08%. In order to increase accuracy, Rui et al. removed low-volume entries from their data set and achieved a maximum detection accuracy of 83.21%.

Passive Remote Source NAT Detection

The NetFlow based approach we propose in this paper is based on the assumption that traffic generated by multiple users/devices shows different behavior than traffic generated by a single user/device. Thus, we try to model user behavior by compiling vectors v i of 9 features derived from NetFlow records. The features we use can be categorized as being related to packet information and usage intensity (cf. Tab. 1) and are described in sections 4.2 and 4.3, respectively. None of the features relies on payload information and consequently privacy of monitored users is respected. All features can directly be derived from NetFlow.

Approach

The approach we propose is essentially based on two steps: first, we build a model of user behavior by training machine learning algorithms on a training data set derived from NetFlow. Afterwards, we apply this model to unknown traffic in order to solve our binary NAT/no-NAT classification problem. In order to be able to apply machine learning algorithms to our problem, we first need to derive descriptive features from the NetFlow records at hand.

Feature Extraction We compute feature vectors v i , i ∈ N for all NetFlow records f i within a distinct, non-overlapping time window W t of length 120 sec- Model Building Based on the feature vectors extracted as described above, we compute a model that we later use for solving our binary NAT/no-NAT classification problem. The model is built by feeding machine learning algorithms with labeled feature vectors during a training phase. The labeling is performed a-priori according to expert knowledge (cf. Sect. 5.1). After the model is built, previously unknown feature vectors can be classified.

Classification For classification, we feed a set of unlabeled feature vectors F Wt induced by the window W t to a previously trained model. On output, we receive a binary decision indicating NAT or no-NAT being present for a single feature vector, corresponding to a distinct source IP address of the given NetFlow records. This process is continuously repeated over time on a series of consecutive sets of unlabeled feature vectors {. . . , F W (t-1) , F Wt , F W (t+1) , . . .}. As our approach does not store or require any inter-window information, it is robust against changes in the network (e.g. joining or leaving subscribers).

Packet features

Packet features are features derived from NetFlow that are directly available in layer 3/4 headers of IP packets. Thus, these features by induction are related to user behavior. The packet features we use are: We expect these features to be highly dependent on user behavior as these features reflect the type of services a specific user consumes. For example, one user may regularly fetch its emails via IMAP while another user may use POP3 in order to access them. Hence, we assume these features to be able to distinguish NAT and no-NAT setups.

Intensity features

The intensity features are very high-level ones and can be directly retrieved from NetFlow records: byt Number of bytes exchanged within a flow. pkt Number of packets transmitted within a specific flow.

We expect both of these features to highly depend on user behavior and the consumed services as well as on the number of users typically being online at a specific point in time. Specifically, we expect more users to transfer more packets and bytes than a single user and vice versa. Thus, for a single IP address under observation, we expect these features to contribute to solving our binary NAT/no-NAT classification problem.

Validation

This section describes the validation process of our approach. First, we describe the setup and the data set used in Sect. 5.1. Afterwards, we describe and discuss the results we achieve in Sect. 5.2.

Setup

Data Collection The goal of our experiments was to achieve strong results that indicate performance of our NAT detection approach in real-world environments. Hence, we trained our classifiers on NetFlow data we got from a German ISP. The data were collected in the ISP's network during the time span of 8 days from September 4th, 2012 to September 11th, 2012. All NetFlow records belong to DSL subscriber traffic, with a majority of business customers, and have been anonymized using Xu et. al's cryptography-based prefix-preserving anonymization [START_REF] Xu | On the design and performance of prefix-preserving IP traffic trace anonymization[END_REF] prior to hand-over in order to further respect privacy of the ISP's subscribers. Our approach does not utilize IP address features for NAT detection. It only uses IP addresses as unique identifiers to correlate related flows within a specific period of time. Hence, our approach is specifically capable of operating completely on anonymized traces in order to protect privacy of endusers much better than, for instance, DPI-based approaches. In total, 6, 631, 383 anonymized NetFlow records containing both, NAT and no-NAT traffic, were used for training and validation 4 .

Labeling NetFlow records have been labeled according to expert knowledge of the sponsoring ISP. As the ISP provides managed services, it was able to label the NetFlow records based on the IP addresses of their customers. NetFlow records belonging to no-NAT traffic were labeled ntf, while NetFlow records stemming from NAT traffic were assigned a tf label. We are aware that this labeling approach may be error prone in a sense that a specific system in a customer's network may exhibit NAT-equivalent behavior (e.g. virtualization). However, the co-operating ISP assured that such systems are not prevalent, if present at all.

Datasets From this 6, 631, 383 NetFlow records, we used the first two days full of NetFlow records, i.e. 1, 795, 964, for training and the NetFlow records of the remaining six days, i.e. 4, 835, 419, for testing of machine learning algorithms. Derived from this number of NetFlow records we obtained 484, 499 feature vectors in total of which 79, 047 were used for training and 405, 452 for testing of algorithms. For the remainder of this paper, we refer to this data set as DS 1 . When analyzing the data at hand, we found that 76.3% of the training NetFlow records belong to no-NAT traffic. However, this majority of NetFlow records resulted in only 17.2% of feature vectors. Similarly, 42% of testing NetFlow records belonging to class no-NAT resulted in 8.3% of feature vectors. The reason for this imbalance is that feature vectors are extracted only if traffic related to a certain IP address occurred. An analysis of the data showed that many single users, i.e. no-NAT traffic, are active only for a few hours across a day. Because of that, no feature vectors could be extracted during several periods of time for no-NAT traffic. In contrast, NAT traffic showed almost constant levels of activity. As of the time of writing, we are not completely sure if this observation is immanent to NAT/no-NAT scenarios and could be exploited as additional feature or is related to the data at hand. Thus, in order to not introduce bias when applying machine learning algorithms to the given data, we derive a balanced reference data set for algorithm training by randomly sampling the feature vectors of the prevalent class NAT. This balanced data set is further referred to as DS 2 and its parameters in comparison to DS 1 are given in Tab. 2. Hence, accuracy achieved with this balanced data set DS 2 has to be regarded as lower bound.

Results and Discussion

We apply two well-known machine learning algorithms, i.e. Support Vector Machines and C4.5 decision tree algorithm described in the previous section. As sketched in Sect. 4.1 we first train models using our training data sets. Afterwards we apply the testing data sets to models derived during training in order to validate the results. The classification results are depicted in Tab. 2. using the imbalanced data set DS 1 we achieve an accuracy of 95.35% in case of C4.5 and an accuracy of 95.10% for SVM. When applying C4.5 and SVM to the balanced data set DS 2 we achieve an accuracy of 89.35% and 81.29%, respectively. The results show that learning with biased data indeed leads to better results. As of the time of writing, however, it is unclear whether imbalance found in DS 1 should indeed be considered bias or is a valuable feature of NAT that could be exploited for NAT detection.

When comparing C4.5 and SVM, the results indicate that C4.5 seems to be more robust to changes in data than SVM as accuracy of C4.5 is only 6 percentage points lower, while it decreases by 13.81 percentage points in case of SVM. Thus, C4.5 in this experiment seems to generalize much better than SVM does. Additionally, time to build the model, i.e. time of training, of C4.5 is much lower (avg. 7.32 seconds) than model build time of SVM (avg. 1366.99 seconds). Similarly, classification with C4.5 requires only 2.22 seconds on average while SVM requires 1371.46 seconds on average for all given feature vectors. These results show that C4.5 can indeed be used to solve our binary NAT/no-NAT decision problem in real-time. Using C4.5, we achieve a lower-bound of accuracy of 89.35% which outperforms the existing approach of Rui et al. [START_REF] Rui | Remote NAT Detect Algorithm Based on Support Vector Machine[END_REF].

Conclusion and Future Work

NAT detection is important to enforce management and security policies in today's networks. In this paper, we present a novel remote source NAT detection approach based on user behavior statistics derived from NetFlow data, working completely passively. In order to solve our binary NAT/no-NAT classification problem, we train machine learning algorithms using 9 distinct features related to user behavior. All features can directly be derived from NetFlow records and do not depend on any payload information. As our approach does not require IP addresses to be valid, IP address anonymization can be applied to further increase privacy of end users. Validation of our approach is performed on real NetFlow traces sponsored by a German ISP and shows that our approach is capable of detecting NAT with a lower-bound accuracy of 89.35% in not more than 120 seconds, after initial training.

During our work, we recognized two additional phenomena of NAT that we will exploit in future work in order to develop a combined NAT detection approach with increased accuracy: First, we noticed that consumer NAT gateways typically perform source port translation on outgoing packets, i.e. apply NAT overload. Translation is performed in a deterministic way according to specific programmatic conditions. We will investigate if such regularity can be spotted and correlated to NAT. Second, we observed that SYN packet size can be extracted from NetFlow records in case of unsuccessful communication attempts (e.g. connection trials to unavailable email or web servers). As different operating systems show differently sized SYN packets, we plan on using this observation to infer the number of different operating systems emitting traffic for one and the same IP address. We believe this to be a strong indicator for NAT. Furthermore, we will be deploying our approach in the data sponsoring ISP's network for further evaluation and improvement. We will also be working towards estimating the size of an inside NAT network in order to improve, for instance, botnet size estimation.

Fig. 1 .

 1 Fig. 1. A typical source NAT setup.

  Based on these definitions, we compute accuracy = |T P |+|T N | |T P |+|T N |+|F P |+|F N | of our classifier C, where |.| denotes the cardinality of a finite set. For the remainder of this work, we use accuracy as a measure to compare results obtained from different classifiers.

tcp

  Number of TCP NetFlow records. udp Number of UDP NetFlow records. dns Number of NetFlow records belonging to DNS, i.e. destination port 53. smt Number of NetFlow records belonging to SMTP, i.e. destination port 25. mai Number of NetFlow records belonging to Email traffic, i.e. destination port 25, 110, 143 , 587, 993 or 995. syn Number of NetFlow records with SYN flag set. rst Number of NetFlow records with RST flag set.

Table 1 .

 1 Features used for behavior-based NAT detection. onds 3 . More specifically, we correlate all flows within the window W t based on the source IP addresses. For each unique source IP address being present in NetFlow records with start time stamp in the window W t , we compute features as listed in sections 4.2 and 4.3. Basically, our feature extraction process aggregates multiple distinct NetFlow records and correlates information based on IP addresses. The result is a set F Wt containing one feature vector v i per distinct IP address.

	Name Description	Packet Intensity
	tcp Number of TCP NetFlow records, if any	x	-
	udp Number of UDP NetFlow records, if any	x	-
	dns Number of DNS NetFlow records, if any	x	-
	smt Number of SMTP NetFlow records, if any	x	-
	mai Number of NetFlow records belonging to email protocols	x	-
	syn Number of NetFlow records with SYN flag set	x	-
	rst	Number of NetFlow records with RST flag set	x	-
	byt Bytes transferred in flows	-	x
	pkt Packets transmitted in flows	-	x

Table 2 .

 2 5 , to the labeled data sets DS 1 and DS 2 Data sets used and accuracy of behavior based approach.

	NetFlow records	Feature vectors	Accuracy
	Data set Total Training Testing Total Training Testing C4.5 SVM
	DS1 6,631,383 1,795,964 4,835,419 484,499 79,047 405,452 95.35% 95.10%
	DS2 6,631,383 1,795,964 4,835,419 90,864 25,256 65,608 89.35% 81.29%

Empirical analysis showed that using a window of length 120 seconds yields the best results.

We are permitted to share the data set used for validation with researchers in anonymized and partially sanitized format under NDA. Please contact the first author if you would like to have access to this data set for related research.

[START_REF] Dyer | Peek-a-Boo, I Still See You: Why Efficient Traffic Analysis Countermeasures Fail[END_REF] We use the WEKA J48 implementation of C4.5 and WEKA's SVM implementation.

Acknowledgment

This work has been supported by the German Federal Ministry of Education and Research under grant number 03FH005PB2 (INSAIN) and by CASED.


Patrick Poullie
email: poullie@ifi.uzh.ch

Burkhard Stiller
email: stiller@ifi.uzh.ch

Fair Allocation of Multiple Resources Using a Non-monetary Allocation Mechanism

Keywords: Resource Allocation, Fairness, Multiple Resources

The fair allocation of scarce resources is relevant to a wide field of applications. For example, cloud resources, such as CPU, RAM, disk space, and bandwidth, have to be shared. This paper presents a mechanism to find fair allocations of multiple divisible resources, which, contrary to other mechanisms, is applicable to but not limited to the example above. Wide applicability of the mechanism is achieved by designing it (1) to scale with the number of consumers and resources, (2) to allow for arbitrary preference functions of consumers, and (3) to not rely on monetary compensation. The mechanism uses a mathematical definition of greediness to balance resources consumers receive and thereby to compute a fair allocation.

Problem Description and Related Work

The fair allocation of scarce resources is relevant to a wide field of applications. The fair sharing of bandwidth is a classical network resource allocation problem. However, shared systems also bear allocation problems where more than one resource has to be divided, e.g., the cloud computing paradigm allows different stakeholders to share different resources like CPU, RAM, disk space, and bandwidth. When demands for resources are different, it is necessary to allocate consumers different bundles in oder to maximize satisfaction. In particular, allocating resources independently of each other (based on some fairness criteria, e.g., proportional fairness) may yield overall allocations that are inefficient. Finding an allocation that is fair and efficient is non trivial.

Formally an allocation problem can be defined as follows. Let A = {a 1 , a 2 , . . . , a m } be a set of consumers and R = {r 1 , r 2 , . . . , r n } be a set of resources. When resources are divisible function q : R → IR maps each resource to the amount that is available of it. Any partition of R into m bundles {b 1 , b 2 , . . . , b m } is called an allocation, whereas consumer a i receives bundle b i . Consumer a i 's appreciation for a bundle is given by a i 's preference function p i that maps every bundle to a real number expressing the consumers valuation for the bundle, e.g.,

a i prefers b 2 to b 1 , if p i (b 1 ) < p i (b 2
). The problem is to find an allocation with certain characteristics, where the two most prominent characteristics are fairness and efficiency. In particular, an allocation has the characteristic that it is fair, if no consumer prefers another consumer's bundle to his bundle [START_REF] Brams | Mathematics and Democracy[END_REF], which can be expressed mathematically as ∀1 ≤ i, j ≤ m : p i (b i ) ≥ p i (b j ). Further, an allocation is efficient, if it is pareto-efficient, i.e., no allocation exists that makes at least one consumer better off without making any other worse off [START_REF] Brams | Mathematics and Democracy[END_REF].

An allocation mechanism is an algorithm to find an allocation for an allocation problem. Many allocation mechanisms are presented throughout literature and shown to produce fair or efficient allocations [START_REF] Brams | Mathematics and Democracy[END_REF][START_REF] Moulin | Fair Division and Collective Welfare[END_REF]. Based on a requirements analysis the following three requirements for general applicability of allocation mechanisms were identified.

(1) Scalability -For many applications, it is important that an allocation mechanism is computationally feasible despite a large number of consumers and resources. This is not the case for all allocation mechanisms, for example, [START_REF] Herreiner | A Simple Procedure for Finding Equitable Allocations of Indivisible Goods[END_REF] can ensure envy-freeness and pareto-efficiency but does not scale.

Demanding scalability with the number of consumers implies that this number is not bounded. For example, [START_REF] Brams | Fair Division of Indivisible Items Between Two People with Identical Preferences: Envy-freeness, Pareto-optimality, and Equity[END_REF][START_REF] Brams | The Undercut Procedure: An Algorithm for the Envy-free Division of Indivisible Items[END_REF] are constrained to two consumers. Demanding scalability with the number of resources implies that this number is also not bounded. Scheduling algorithms typically consider the allocation of only one resource (or at least interchangeable resources). Hence, they cannot be applied, when two or more non-interchangeable resources, with inter-depending utilities, have to be allocated. (2) Arbitrary preference functions -It is desirable that allocation mechanisms need to make as little assumptions on consumers' preference functions as possible. For example, [1, p. 271 et seq.] and [START_REF] Schulman | Allocation of Divisible Goods Under Lexicographic Preferences[END_REF] assume that the valuation of a bundle does not depend on the ratio of resources in it. This assumption appears too simplistic for many use cases.

(3) No monetary compensation -Many allocation mechanisms [START_REF] Yang | VCG-Kelly Mechanisms for Allocation of Divisible Goods: Adapting VCG Mechanisms to One-Dimensional Signals[END_REF][START_REF] Chorppath | Almost Budget-balanced Mechanisms for Allocation of Divisible Resources[END_REF][START_REF] Jain | An Efficient Nash-implementation Mechanism for Network Resource Allocation[END_REF] involve money. It is assumed that if a consumer does not get a large bundle of resources, but therefore can hold on to most of its money, the outcome is fair. However, monetary compensation for missing resources may be perceived as a consolidation price.

Since no allocation mechanism exists, which suffices all three criteria, this proposal here closes this gap by an allocation mechanism for multiple divisible resources.

Approach

The allocation mechanism is round-based. Each round every consumer demands a bundle that he wishes to receive (which depends on his preference function). However, consumers will only receive bundles when the process stops, i.e., after the last round. Demands of the same round are input to a mathematical function g to assess the proportionality of every demand. In particular, g maps every demand to a real number, that expresses its proportionality, and therefore can be associated to the greediness of the consumer that made it. The number is returned to the respective consumer who should take it into account when making the demand in the next round, i.e., if a consumer receives a number greater zero (which implies that he made an exproportional demand) he should demand a smaller bundle in the next round. Therefore, the progression of demands is influenced by the feedback consumers receive, which is determined by g. The definition of g is, therefore, closely considered in Section 2.1. When the process stops, each consumer receives the bundle he demanded in the last round. In case the sum of demands exceeds the resource supply, bundles have to be shaped, which is done in proportion to the consumers' greediness (which is defined by g and the last demanded bundle), i.e., the bundle that a greedy consumer receives will be trimmed stronger than the bundle a moderate consumer receives. This gives incentives to consumers, to take the feedback about their greediness into account, as they may suffer from strongly trimmed resource bundles.

Greediness

For an arbitrary round in the allocation mechanism, let d i,j ≥ 0 be the demand of consumer a i for resource r j . For any resource r j , amount f s(r j ) = q(r j ) ÷ m is the equal-share of resource r j for any consumer, i.e., the resource is divided equally among all consumers. Then d i,j -f s(r j ) is the amount of resource r j that consumer a i demands beyond his equal-share (if the difference is negative, a i is willing to release some of his equal-share). If d i,j > f s(r j ), other consumers have to release some of their equal-share of r j in order to cover for a i 's additional demand. Therefore, the additional demand should be added to the greediness of a. If d i,j ≤ f s(r j ) consumer a i 's greediness should decrease. However, in this case, only to an extend that other consumers benefit from the release, which applies, when other consumers request r j beyond their equal-share. This notion can be expressed as follows. Define α(r j ) as the sum of what consumers demand beyond their equal-share of r j , i.e., α(r j ) = m i=1 max 0, d i,j -f s(r j ) , and β(r j ) as the sum of what consumers release of r j , i.e., β(r j ) = -1• m i=1 min 0, d i,j -f s(r j ) . The greediness of consumer a i is defined as g(a i ) = n j=1 g(d i,j ), where

g(d i,j ) := d i,j -f s(r j ) if d i,j -f s(r j ) ≥ 0 d i,j -f s(r j ) • min 1, α(rj ) β(rj )
else.

Meeting the Three Criteria

Because this allocation mechanism only considers demands made by consumers but not directly their preference functions, no assumptions need to be made on the preference functions (req. ( 2)). Since consumers do not need to communicate with each other but must announce their demands to a central entity (a condition that is given when users compete for cloud resources) that calculates g, consumers can run on different machines. This allows to add machines if the number of consumers is large (and run consumers with complex preference functions on dedicated machines). Because the computation of g is linear in the number of consumers and resources (cf. Section 2.1), the central entity scales and, therefore, req. (1) is met. No monetary compensation is needed (req. ( 3)) to ensure a fair and efficient outcome, because the mechanism streamlines the proportionality of bundles consumers receive based on their equal-share.

Final Remarks

An allocation mechanism for multiple divisible resources and an arbitrary number of consumers was presented. It can be applied to cloud resource allocation problems but is not limited to such scenarios. The mechanism scales and does neither need to make assumptions on the consumers' preference functions nor does it use monetary compensation. Due to the comprehensible definition of greediness it utilizes, it is expected to yield fair and efficient allocations. Since resulting allocations depend on consumer behavior, game-theoretic analysis and simulations will be deployed to formally evaluate (i) how fair and efficient resulting allocations are and (ii) if it is prone to strategic demand statements.

Acknowledgments

This work was supported partially by the SmartenIT and the FLAMINGO projects funded by the EU FP7 Program under Contract No. FP7-2012-ICT-317846 and No. FP7-2012-ICT-318488, respectively. The authors wish to thank T. Bocek and M. Waldburger for their enlightening discussions and input.