Stylianos Georgoulas
email: s.georgoulas@surrey.ac.uk

Klaus Moessner
email: k.moessner@surrey.ac.uk

Alexis Mansour
email: a.mansour@surrey.ac.uk

Menelaos Pissarides
email: m.pissarides@surrey.ac.uk

Panagiotis Spapis
email: pspapis@di.uoa.gr

A Fuzzy Reinforcement Learning Approach for Pre-Congestion Notification based Admission Control

Keywords: Admission Control, Pre-Congestion Notification, Fuzzy Logic, Reinforcement Learning, Quality of Service, Autonomic Management

Admission control aims to compensate for the inability of slowchanging network configurations to react rapidly enough to load fluctuations. Even though many admission control approaches exist, most of them suffer from the fact that they are based on some very rigid assumptions about the perflow and aggregate underlying traffic models, requiring manual reconfiguration of their parameters in a "trial and error" fashion when these original assumptions stop being valid. In this paper we present a fuzzy reinforcement learning admission control approach based on the increasingly popular Pre-Congestion Notification framework that requires no a priori knowledge about traffic flow characteristics, traffic models and flow dynamics. By means of simulations we show that the scheme can perform well under a variety of traffic and load conditions and adapt its behavior accordingly without requiring any overly complicated operations and with no need for manual and frequent reconfigurations.

Introduction

The envisioned dynamicity of future Internet networks, where applications with different service requirements may appear makes Quality of Service (QoS) provisioning and service continuity a challenging issue that traditional traffic engineering approaches, usually based on offline optimizations through bandwidth provisioning, may not be able to address efficiently. Towards this end, dynamic service management functions such as admission control can play a significant role with respect to supporting QoS for application flows during the actual service delivery time, helping to overcome the inability of slow-changing network configurations to react adequately fast to shorter-term load fluctuations. Even though admission control is a well-studied subject [START_REF] Wright | Admission Control In Multi-Service IP Networks: A Tutorial[END_REF][START_REF] Lima | Admission Control in Multiservice IP Networks: Architectural Issues and Trends[END_REF], most of the existing schemes suffer from the fact that they are based on some very rigid assumptions about the per-flow and aggregate underlying traffic models, requiring therefore manual reconfiguration of their parameters in a "trial and error" fashion as soon as the original assumptions stop being valid, in order to keep performing well [START_REF] Breslau | Comments on the Performance of Measurement-Based Admission Control Algorithms[END_REF]. That is they employ some tuning parameters that need to be initially manually set and also readjusted as soon as the traffic and network characteristics change.

The idea of mechanisms able to self-adapt and self-configure as the conditions change has been around for quite some time under the generic term autonomic management and has been gaining steadily increasing interest during the past few years. In that context, past and existing projects [START_REF]EU FP7 UniverSelf project website[END_REF] have been working towards inducing self-* behavior in Internet communication mechanisms. In this direction, in this paper we propose a novel, autonomic admission control scheme based on the increasingly popular Pre-Congestion Notification (PCN) framework put forward by IETF [START_REF] Eardley | Pre-Congestion Notification Architecture[END_REF]. The proposed solution adapts autonomically to the characteristics of the traffic flows and underlying network traffic and can perform well under a variety of traffic and load conditions without making any assumptions about traffic models, flow dynamics and characteristics and with no need for manual and frequent reconfigurations.

The rest of this paper is organized as follows; in Section 2 we present the underlying concepts behind PCN, the variations of this approach and its limitations, as well as some existing approaches towards introducing autonomic behavior into PCN. In Section 3 we present in detail our scheme and in Section 4 we evaluate its performance under a variety of traffic and load conditions. Finally, in Section 5 we conclude, summarizing our findings, while we also give some directions for future work.

2

Pre-Congestion Notification based Admission Control

PCN, which targets core/fixed network segments, defines a new traffic class that receives preferred treatment by PCN-enabled nodes, similar to the expedited forwarding per-hop behavior in Differentiated Services [START_REF] Blake | An Architecture for Differentiated Services[END_REF], aiming to minimize the packet loss rate (PLR) for loss-intolerant flows. The PCN framework provides two main functionalities that are admission control (AC) and flow termination (FT) [START_REF] Menth | A Survey of PCNbased Admission Control and Flow Termination[END_REF]. AC, as also aforementioned, decides on whether new flow requests should be admitted or rejected based on the current network conditions whereas FT is a control function that tears down already admitted flows in case of overloads that might occur, in spite of AC, due to rerouted traffic (i.e. in case of link failures and other unexpected events). AC targets the "normal operations" phase of a network whereas FT can be seen as a radical measure for use only in emergency situations and should be avoided as much as possible (it is more acceptable to deny a flow session than to allow it to start with high uncertainty about the chances of completing, which renders the session useless [START_REF] Lundqvist | Edge-Based Differentiated Services[END_REF]).

In order to support both these functionalities PCN introduces an admissible and a supportable rate threshold (AR(l), SR(l)) for each link l of the network, which create three different load regimes. If the PCN rate r(l) is below AR(l), there is no precongestion and -from that link's point of view-further flows can be admitted in the ingress-egress path(s) to which it belongs to. If the PCN traffic rate r(l) is above AR(l), the link is AR-pre-congested and no further flows should be admitted depend-ing also on how much the rate exceeds AR(l). If the PCN rate r(l) is above SR(l), the link is SR-pre-congested and in this state some of the existing flows should be additionally terminated, depending also on how much the rate exceeds SR(l). Both the AC and FT mechanisms are triggered based on packet markings; that is PCN nodes mark traffic accordingly depending on whether it exceeds AR(l) or SR(l), the egress nodes evaluate the packet markings and deduce on the admission control and -if neededflow termination decisions. The above are illustrated in Fig. 1. PCN-based AC can be performed in various ways [START_REF] Menth | A Survey of PCNbased Admission Control and Flow Termination[END_REF]. In its Probe Based AC (PBAC) version the markings on probe packets only are evaluated and the admission control decision is derived. In the Observation Based AC (OBAC) version, no probe packets are sent and a single marked packet of the "main flows" aggregate traffic is considered enough to set the AC status for the involved ingress-egress pair(s) to reject for the subsequent time period. Finally, in the Congestion Level Estimate (CLE) Based AC (CLEBAC) version, no probe packets are sent and at regular intervals the percentage of marked versus total packets of the "main flows" aggregate traffic is evaluated and the AC status is set to accept or reject, depending also on whether the CLE value is below or above a predefined threshold value.

The main deficiency of PCN-based AC is that even though the possible marking behaviors and the possible AC mechanisms are described in detail [START_REF] Eardley | Pre-Congestion Notification Architecture[END_REF][START_REF] Menth | A Survey of PCNbased Admission Control and Flow Termination[END_REF], the way to actually set the marking thresholds so as to achieve the desired QoS targets is not addressed. While there has been considerable work [START_REF] Menth | Performance Evaluation of PCN-based Admission Control[END_REF][START_REF] Menth | Applicability of PCN-based Admission Control[END_REF][START_REF] Zhang | Performance Evaluation of Pre-Congestion Notification[END_REF] in evaluating the performance of the various versions of PCN-based AC schemes in (mostly) single link topologies, these works assume that the marking thresholds and the other involved PCN parameters (e.g. the CLE threshold value) can also be derived and set in the first place; in principle they evaluate the performance of the schemes as a function of their involved parameters without though providing any guidelines on how these parameters should be set if the schemes were to be applied in a practical networking scenario. This means that in order to apply PCN-based AC even for a single path consisting of 10 links there exist 10 distinct marking threshold values that need to be manually adjusted so that the combined marking behavior along all these links, when used in the AC mechanism, guarantees the desired QoS targets. Thus, when network characteristics such as links capacities and/or flows characteristics change, these thresholds have to be manually readjusted until these QoS targets are again met. In principle a network administrator would have to continuously monitor and intervene and update the parameters until an acceptable level of performance is acquired. Apart from the added human effort this would also mean considerable amount of downgraded performance until the manual parameter fine-tuning led to the correct parameter settings.

These shortcomings were recently acknowledged and some approaches towards inducing autonomic behavior in PCN-based AC have emerged [START_REF] Latre | An Autonomic PCN based Admission Control Mechanism for Video Services in Access Networks[END_REF][START_REF] Roosbroeck | Optimized Network Utilization through Buffering in PCN enabled Multimedia Access Networks[END_REF][START_REF] Latre | PCN Based Admission Control for Autonomic Video Quality Differentiation: Design and Evaluation[END_REF]. The main concept behind these CLEBAC approaches is that the maximum traffic variability can be considered as a good metric to be taken into account when setting the marking threshold. If the marking threshold at one link is set as equal to link capacity -maximum traffic variability, then packet marking would occur only when indeed there is no "space" left for any additional traffic without risking packet losses. To account for the fact that the future maximum traffic variability may be different than the existing measured one, the approaches further reduce the marking threshold by multiplying the existing maximum traffic variability with a ∆ value [START_REF] Latre | An Autonomic PCN based Admission Control Mechanism for Video Services in Access Networks[END_REF][START_REF] Roosbroeck | Optimized Network Utilization through Buffering in PCN enabled Multimedia Access Networks[END_REF] and also by "adding" the traffic demands of future flows [START_REF] Latre | PCN Based Admission Control for Autonomic Video Quality Differentiation: Design and Evaluation[END_REF]. These concepts are shown in Fig. 2 which is borrowed from [START_REF] Latre | An Autonomic PCN based Admission Control Mechanism for Video Services in Access Networks[END_REF] (GoalRate corresponds to the link capacity). [START_REF] Latre | An Autonomic PCN based Admission Control Mechanism for Video Services in Access Networks[END_REF].

Fig. 2. Marking threshold adjustment based on maximum traffic variability

Apart from the fact that the correct ∆ value needs to be manually set, these approaches also ignore the effect of buffering in routers when setting the marking threshold, as well as don't account for any flows terminating (in all evaluation scenarios once a flow is admitted it is assumed that it doesn't terminate). In other words these works evaluate only how fast the schemes start reacting to congestion being built up in a constantly increasing load environment. That is they focus on the very limited time period during which the network moves from uncongested to congested conditions but they do not try to capture the long-term performance of the schemes in environments with flows arriving and terminating. In addition from a practical implementation point of view they require calculation of the maximum traffic variability and adjustment of the marking threshold on a per packet basis (in Gbps links this would mean millions of times per second) as well as keeping track and updating of the flow characteristics at all routers, even core ones [START_REF] Latre | PCN Based Admission Control for Autonomic Video Quality Differentiation: Design and Evaluation[END_REF].

In our scheme, which will be described in detail in the following Section, we aim to address the long-term performance of PCN-based AC in environments with flow arrivals and terminations without inducing significant processing overhead (calculations and adjustments many times per second) or requiring any state or flow statistics being kept and updated at any routers. Through the use of machine learning, the AC controller is able, starting from some default marking threshold value, to converge to a set of rules that drive the marking behavior and threshold value readjustment, autonomically and on a per scenario basis as the traffic and network characteristics require.

Fuzzy Q-Learning PCN-based Admission Control

Fuzzy Q-Learning has been extensively used in the literature, e.g. see [START_REF] Razavi | A Fuzzy Reinforcement Learning Approach for Self-Optimization of Coverage in LTE Networks[END_REF][START_REF] Dirani | Self-organizing networks in next generation radio access networks: Application to fractional power control[END_REF] to introduce autonomic capabilities in network control systems, and is a combination of fuzzy logic [START_REF] Chen | Introduction to Fuzzy Sets, Fuzzy Logic and Fuzzy Control Systems[END_REF] with Q-learning (type of Reinforcement Learning (RL)) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] that aims to combine the robustness of a rule based fuzzy system with the adaptability and learning capabilities of Q-learning. In this Section we highlight the main concepts and benefits of this approach and its applicability in the context of PCN-based AC.

Fuzzy Q-Learning Concepts

Rule based fuzzy systems have been extensively applied with success in many diverse application areas due to their similarity to human perception and reasoning, their intuitiveness and their simplicity. The main concept is that, contrary to classical set theory, the sets used for representing their input and output parameters are fuzzy; meaning that their elements have degrees of membership that represent the degree of truth of a statement. The process of mapping the input values into membership functions (MFs) is called "fuzzification". After this first step, membership functions are combined in fuzzy "if…then" rules to make inferences and finally the "defuzzification" phase produces a crisp output value. In principle the idea of fuzzy inference systems is that at every point in time and for a unique set of input parameter values, multiple rules can be triggered with a different degree of truth (strength) and their individual outputs are then "combined" to derive a unique crisp output value. Fuzzy inference systems offer robustness and smooth reaction [START_REF] Chen | Introduction to Fuzzy Sets, Fuzzy Logic and Fuzzy Control Systems[END_REF] however they do require the existence of an expert to define the appropriate rule-set. The main challenge is therefore to be able to generate the appropriate rule-set without the existence of a direct trainer. Reinforcement learning can be applied in this context to drive the generation of the appropriate rule-set based on the interactions with the environment. Q-learning belongs to the Temporal Difference (TD) methods which are one of the three main types of Reinforcement Learning methods, the other two being Dynamic Programming and Monte Carlo methods [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. TD methods combine the pros of the other two types of RL methods; that is, they don't require an accurate model of the environment (contrary to Dynamic Programming) and are suitable for step-by-step incremental computations (contrary to Monte Carlo methods). Q-learning works by learning an action-value function based on the interactions of an agent (controller) with the environment and the instantaneous reward it receives. The objective of an agent is to find, by trying out all the possible actions when being in a given state, the action that maximizes its long term reward. The detailed mathematical foundation and formulation of Q-learning can be found in [START_REF] Razavi | A Fuzzy Reinforcement Learning Approach for Self-Optimization of Coverage in LTE Networks[END_REF][START_REF] Dirani | Self-organizing networks in next generation radio access networks: Application to fractional power control[END_REF][START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] therefore it is not repeated here, due to space limitations; the core Q-learning algorithm [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] is provided though, so as to highlight the parameters involved in it and consequently in our evaluation in the following Session.

Initialise Q(s,α) arbitrarily (1)
Repeat (2) Initialize s (3) Repeat ( 4) Choose α from s using policy derived from Q (e.g. ε-greedy) (5) Take action α, observe r, s' ( 6)

Q(s,α)=Q(s,α)+a*[r+γ*max α' Q(s',α')-Q(s,α)] (7) s←s' (8) until s is terminal (9)
In every step of the Q-learning algorithm, the agent/controller observes the environment (line 5) and deduces in which state s it currently resides based on the input parameter values. It then (100-ε) % of the time takes the action with the highest Q value and ε% of the time it takes another action randomly from the set of available actions (line 5). This is called the exploration/exploitation tradeoff which aims to ensure the agent is allowed to move into "unchartered territory" instead of solely relying on what it has learnt so far. After taking the action the agent receives an instantaneous reward r, observes to which state s'this action led it into (line 6) and updates the corresponding Q value (line 7). Parameter a (0<a≤1) is the learning rate which determines how much the agent values the newly acquired knowledge compared with the existing one and γ (0≤γ<1) is the discount factor which defines how much expected future rewards affect decisions now. Low γ means the agent pays little attention to the future whereas high γ means that potential future rewards have a major influence now; that is the agent is willing to accept some short-term loss in return for long-term gain.

Q-learning is an attractive method of learning because of the simplicity of the computational demands per step and also because of proof of convergence to a global optimum, avoiding all local optima, as long as the Markov Decision Process (MDP) requirement is met; that is the next state depends only on the current state and the taken action (it is worth noting that the MDP requirement applies to all RL methods). It can also be easily combined with fuzzy logic and provide the association between the states and the available actions, which is the same as constructing the fuzzy logic "if…then" engine; the only additional step required being the distribution of the reinforcement/reward signal among multiple simultaneously triggered "if…then" rules due to the overlapping of the fuzzy input sets. This distribution can be done proportionally to the strength with which each rule is triggered so that rules (states) triggered with high strength -and contributing therefore more to the output action-are rewarded (or penalized) more compared to rules triggered with lower strength [START_REF] Razavi | A Fuzzy Reinforcement Learning Approach for Self-Optimization of Coverage in LTE Networks[END_REF][START_REF] Dirani | Self-organizing networks in next generation radio access networks: Application to fractional power control[END_REF].

Applicability to PCN-based Admission Control

In our CLEBAC PCN-based AC approach we assume that there is a PCN agent/controller running at every PCN node and we define two input parameters for each controller and one output parameter; the input parameters are the traffic rate (as % of the link capacity) and its "trend" over the past T seconds. To define the trend of the traffic rate we split the T second interval into two intervals (t-T, t-T/2] and (t-T/2, t], calculate the traffic rate into each one individually and calculate the trend as:

trend (t-T,t) = rate (t-T/2,t] -rate (t-T,t-T/2] ( 1
)
As output parameter we define the adjustment X of the marking threshold compared to its current setting; that is the marking threshold after each action becomes:

ThresholdRate new =ThresholdRate current + defuzzified(X) (2)
The individual "if…then" rules for driving the marking behavior are therefore of the kind "if the traffic rate is VERY HIGH (POSITIVE BIG) and the trend is VERY HIGH (POSITIVE BIG) then the threshold adjustment is NEGATIVE BIG". This rule intuitively states that if the traffic is very high and keeps increasing then the marking threshold should be reduced a lot so that packet marking should be accelerated and subsequent flows should be rejected. The membership functions for the input and output parameters used in our evaluation are summarized in Table 1. Since each of the input parameters and the output parameter can be categorized as being Negative Big (NB), Negative Small (NS), Zero (ZE), Positive Small (PS) and Positive Big (PB) this means that the rule-set consists of 25 "if…then" rules with each rule having 5 possible output actions. The objective of the learning process is therefore for the controller to derive the optimal output action for each one of the 25 rules.

This way the controller attempts, based on the available actions, to learn the policy that maximizes the long-term utilization while at the same time avoiding situations that can lead to packet loss. Setting P to a considerably high negative value can force the controller to prioritize the packet loss rate objective -which is the primary objective of PCN-over the maximization of the utilization. One additional aspect also mentioned above is that in order to enable the learning phase, the evolution of the controlled system between successive states should be mainly due to the control action (strictly speaking, theoretically only due to the control action in order for the MDP requirement to be fully met). Since the outcome of the packet marking must be reflected in the subsequent admission control decisions, the control periodicity for the marking threshold adjustment S must be set to a reasonably high value that will allow for flows to arrive and be accepted or rejected. In the former case the evolution of traffic will be due both to new flows starting and existing flows terminating whereas in the latter case it will be due to existing flows being terminated. If, however, S is set to a very low value then the traffic evolution will be mainly (or only) due to the inherent burstiness of existing traffic; and this traffic evolution is not affected by the control action.

Performance Evaluation

In order to evaluate the performance of our scheme (we will be referring to it as FQL PCN) we ran simulations with the publicly available NS-2 simulator [START_REF]The NS-2 network simulator[END_REF] using the topology of Fig. 3, in which we assume that 3 types of users request the streaming of MPEG-4 encoded video from a streaming media server through a PCN domain and at different quality levels (low, average, high) so as to have traffic sources with different bandwidth requirements and traffic characteristics in our simulations. Since the transmission from the media server is done through a 200Mbps link and the links in the PCN domain are set to 100Mbps, congestion may occur only at the PCN ingress router, meaning that in this topology only one PCN controller is needed to monitor the state of the outgoing link and perform packet marking. In addition, given the simulation setup, the utilization of this link alone is adequate for use in the reward function, since the utilization of the downstream link (between the PCN interior router and the PCN exterior router) is identical.

Regarding the video streams we used traffic traces from [20] with the high quality streams having peak rate 3.1Mbps and average rate 0.58Mbps, the average quality streams having peak rate 1.5Mbps and average rate 0.18Mbps and the low quality streams having peak rate 1.5Mbps and average rate 0.11Mbps. To test our scheme under a variety of load conditions and flow arrival/departure dynamics we considered various scenarios with per quality type flow inter-arrival times 1sec, 2sec and 3sec (exponentially distributed) and flow durations 350sec and 1200sec, also exponentially distributed. The first duration could, for example, correspond to music video clips whereas the second to episodes of a TV series. Every scenario was run for 7200sec simulated time and 10 times with different random number generator seeds.

Regarding the scheme's parameters we fixed the monitoring interval T to be equal to 5sec, the control periodicity S to be equal to 1sec and the marking threshold was initially set equal to 95% of the link capacity. Regarding the marking behavior, we employed the exhaustive threshold marking approach [START_REF] Menth | A Survey of PCNbased Admission Control and Flow Termination[END_REF], which marks all packets on a link when the metered rate exceeds the marking threshold rate. For the admission control decision we also assumed that whenever CLE>0 then the AC status should be set to reject. With respect to the Q-learning specific parameters we set P equal to -20 to "force" the controller to learn to avoid taking actions that may lead to packet losses. The discount factor γ was set equal to 0.95 and ε for the exploration/exploitation tradeoff was set equal to 0.05, meaning that with 95% probability the action with the higher Q value is taken during the learning period. Regarding the learning rate since the environment is non-deterministic (due to the probabilistic flow arrivals/departures and the inherent burstiness of the traffic, taking an action from a given state can lead to different states and rewards) we used the learning rate for the non-deterministic version of Q-learning. In this version, the practice is to begin with a higher learning rate and reduce it during the learning process by employing the following formula: a(s,α)= amax/(1+visits(s,α))

The learning rate used to update each state-action pair ("if…then" rule) is reduced every time this state-action pair is visited; a max was set equal to 0.1. Due to space limitations only the obtained results for two scenarios will be presented; similar results and conclusions were drawn from all the tested scenarios. It is also worth noting that all the aforementioned parameters were fixed and remained unchanged throughout all scenarios and all simulation runs within each scenario.

Scenario 1 (inter-arrival time=1sec, video duration=1200sec)

Fig. 4 shows the outcomes of one out of the ten simulation runs. FQL PCN is able, after the initial period of PLR due to the high initial marking threshold, to reduce and vary the marking threshold so that PLR is equal to zero for most of the time and the utilization stays at high levels. During the initial period of PLR spikes (first 660sec on average among all simulation runs), PLR stays well below 0.5% whereas for the rest of the simulation runs the PLR spikes account in total for 12sec (on average among all runs) with a maximum PLR value of less than 10 -4 (it is worth noting that according to [START_REF] Pinson | Video Performance Requirements for Tactical Video Applications[END_REF], for MPEG-4 video this latter value of PLR can be considered tolerable). To illustrate the effect of learning in the rules used by the controller, in Fig. 5 we show the incurred PLR and the variation of the marking threshold rate for a fuzzy logic (FL PCN) controller that uses the same initial rules fed to the FQL controller, without though any further updates to the rules through learning. As Fig. 5 shows for the FL PCN scheme there exist PLR spikes for the whole duration of the simulations due to the fact that the initially set rules are not optimized and are not adapted towards an optimized behavior. In contrast the FQL PCN scheme, starting by exactly the same -apparently not optimized rule-set-is able through the learning process to redefine the rules accordingly. The FL PCN scheme achieves higher utilization (not shown due to space limitations) but since the primary PLR objective is violated, this increased utilization is of no real practical importance.

4.2

Scenario 2 (inter-arrival time=2sec, video duration=350sec) Fig. 6. Incurred PLR for the FQL PCN scheme and the FL PCN scheme.

As Fig. 6 shows for different flow arrival/departure dynamics the behavior of the FQL PCN scheme is similar to the previous scenario with an initial period of PLR spikes (reduced though due to the overall lighter load conditions) and some infrequent PLR spikes for the remainder of the simulations. The FL PCN scheme, similar to the previous scenario, is hindered by its static and not optimized rule-set.

Conclusions and Future Work

In this paper we presented a novel scheme towards PCN-based admission control. Through the use of Fuzzy Q-learning the scheme is able to autonomically adapt its marking behavior so that it meets the traffic and network requirements. The scheme requires no a priori knowledge about traffic flow or network characteristics, traffic models and flow dynamics and is able to adapt accordingly and on a per scenario basis without requiring any manual reconfiguration of its involved parameters on a per scenario basis. In addition it doesn't require any complicated and overly frequent calculations or keeping and updating of any state in any routers.

In the future we will attempt to further optimize our scheme and improve its convergence properties, by examining the use of different input parameters and reward functions, assess its behavior and performance in multi-agent/controller environments required in larger, more realistic, network configurations and compare it with the existing autonomic and adaptive PCN-based AC schemes.

Fig. 1 .

 1 Fig. 1. PCN rates and behavior.

Fig. 3 .

 3 Fig. 3. Simulation topology.

Fig. 4 .

 4 Fig. 4. Incurred PLR, marking threshold rate and utilization for the FQL PCN scheme.

Fig. 5 .

 5 Fig. 5. Incurred PLR and marking threshold rate for the FL PCN scheme.

Table 1 .

 1 Input and output MFs of the controller.One important element, as in every application of RL, is the instantaneous reward function since it fundamentally defines what the controller attempts to learn to optimize in the long-term. In our case we set the reward function as follows:

		Traffic Rate	Trend of Traffic Rate	Adjustment (kbps)
	NB	(piece-wise linear) -∞, 0.4, 0.8	(piece-wise linear) -∞, -0.5015,	(triangular) -45, -35, -25
			-0.003
	NS	(triangular) 0.78, 0.805, 0.83	(triangular) -0.035, -0.0075, 0.02	(triangular) -38, -20.5, -3
	ZE	(triangular) 0.82, 0.845, 0.87	(triangular) 0.015, 0.215, 0.28	(triangular) -5, 0, 5
	PS	(triangular) 0.86, 0.895, 0.93	(triangular) 0.025, 0.0325, 0.04	(triangular) 3, 9.5, 16
	PB	(piece-wise linear) 0.92, 1, +∞	(piece-wise linear) 0.035, 1, +∞	(triangular) 14, 16, 18
		Utilization, if Packet Loss Rate=0 Reward=൜ P, if Packet Loss Rate ≠0

Acknowledgements. The research leading to these results has been performed within the UniverSelf project (www.UniverSelf-project.eu) and received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement no 257513. The authors would also like to thank Zwi Altman and Richard Combes from France Telecom Orange Labs and Rouzbeh Razavi from Alcatel Lucent Bell Labs Ireland for their valuable support and advice.


Samuel Marchal

Thomas Engel

Large Scale DNS Analysis

Keywords: Security monitoring, DNS data, storage facilities

In this paper we present an architecture for large scale DNS monitoring. The analysis of DNS traffic is becoming of first importance currently, as it allows to monitor the main part of the interactions on the Internet. DNS traffic can reveal anomalies such as worm infected hosts, botnets or spam participating hosts. The efficiency and the speed of detection of such anomalies rely on the capacity of DNS monitoring system to treat quickly huge quantity of data. We propose a system that leverages distributed processing and storage facilities.

Introduction

The DNS service [START_REF] Mockapetris | Rfc 1034: Domain names -concepts and facilities[END_REF][START_REF] Mockapetris | Rfc 1035: Domain names -implementation and specification[END_REF] is the glue that holds and drives the current Internet. In addition to a basic and essential function that maps names to IP addresses, attackers also leverage DNS to enhance the impact of attacks. For instance Fast Flux networks and Double Flux networks are the typical crimeware supporting infrastructures. Fluxing techniques allow to relocate hosts providing malware rapidly, while keeping the same contact reference: the domain name. In order to detect such a behaviour and to be able to identify domain names implicated in criminal activities, the fine choice of the DNS features is paramount. Behind the concern of malicious domains, the question arises of automatically discovering the activity type of domain. The other big issue is the storage facilities to use for these features to have a fast access to them.

Passive DNS Analysis

Early phase of research

Studies on several malicious activities showed that they can be characterized by statistical properties of basic protocol fields (TTL, Request type, domain names). This is a good starting point that still needs to be extended with derived metrics suited for detecting deviations from a normal profil. Major issues with data mining for DNS data are related to identify relevant features that can be used to detect abnormal behaviour.

In [START_REF] Marchal | DNSSM: A large scale passive DNS security monitoring framework[END_REF], we present the first steps of our work showing the utility of DNS features in the identification of domain activities. This presents a passive DNS security monitoring framework called DNSSM whose architecture for DNS data capture (see Figure 1) is based on the technique of Weimer [START_REF] Weimer | Passive dns replication[END_REF]. We collect DNS responses sent to a recursive server and extract ten features for each domain to build a representative pattern of it. We use common features of DNS data mining such as the TTL or the number of IP addresses associated to a single domain. Additionally we introduce new features such as an entropy based IP dispersion index that depicts the number of different networks in a pool of IP addresses and thus shows the potential geographical dispersion of physical machines.

These patterns can be further used for comparison with other domain patterns in order to raise singular anomalies, or to group them corresponding to their similarities. We present a method that offers two methods: first, through a Web Interface where the analyst can easily see the characteristics of a domain and compare them to the average or to extreme values of numerical features. Second, we present an automatic analysis leveraging the k-means clustering method [START_REF] Hartigan | A k-means clustering algorithm[END_REF] based on ten DNS features. Data mining 300 MB of DNS responses allows to group together domains participating to CDNs, domains that performs user tracking services or very popular domains such as google.com or facebook.com. Through this analysis of a small dataset, we show that DNS features are significant in domain activity.

Distributed data storage

A critical requirement for such an architecture is the large quantity of data that has to be processed and stored. Our experience in deploying a passive DNS monitoring tool showed that for a regional backbone network, the daily quantity of data can easily reach 1 GB per day. In our first trial, we have implemented the storage system using a relational database system (MySQL). Since tracking malicious domains over a monthly basis can lead to deal with data quantities in the tenths of GBs such that we have to leverage distributed storage and retrieval solutions. Existing approaches leverage efficient key-value storage systems (see Cassandra [START_REF] Lakshman | Cassandra: structured storage system on a p2p network[END_REF] or [START_REF] Lerner | At the forge: Redis[END_REF]).

Most activities related to DNS security monitoring require small processes running over a very large database. For instance, looking for the IP address corresponding to a domain is an easy task, but requires to mine a huge volume of data. Thus, the paradigm has shifted from a highly computational to a dataintensive problem. We propose to use the popular Hadoop framework [START_REF] White | Hadoop: The Definitive Guide[END_REF] in order to distribute both the computations and data storage.

Hadoop implements the MapReduce [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF][START_REF] Lin | Data-Intensive Text Processing with MapReduce[END_REF] design pattern, which is designed for data-intensive problems and to distribute computing of large datasets on clusters of computers. However, for achieving the same task as the centralized approach of MySQL, the design of our DNS analysis algorithm has to be rethought, because mapping is applied onto each piece of distributed data, on each machine. Basically data is processed to extract required features, with the domain name being the key. Later, these key features are used to aggregate results, because all outputs of the mappers with the same key are sent a unique reducer in charge of producing the final result. This is an issue we are addressing to build the architecture proposed in Figure 1.

Related Work

The first work of Florian Weimer [START_REF] Weimer | Passive dns replication[END_REF], opened the door to DNS analysis with a first proposal to analyse passively collected DNS data. Based on this work, a lot of research has been done to detect DNS anomalies such as DNS tunnel in [START_REF] Born | Detecting dns tunnels using character frequency analysis[END_REF] or FastFlux and botnet in [START_REF] Perdisci | Detecting malicious flux service networks through passive analysis of recursive dns traces[END_REF][START_REF] Antonakakis | Building a dynamic reputation system for dns[END_REF] and [START_REF] Bilge | Finding malicious domains using passive dns analysis[END_REF]. These papers present data mining techniques leveragning several DNS features and mainly supported by machine learning in automatic detection. The difference to our work is that DNSSM doesn't relies on labeled data as it uses unsupervised clustering techniques. Dealing with large quantities of DNS data has already been addressed in [START_REF] Plonka | Context-aware clustering of dns query traffic[END_REF], where Plonka et al. use binary trees to store DNS data using mapped IP addresses as keys.

Conclusion and Future Work

In this paper, we present a method to identify and compare domain names activities leveraging features that are extracted from DNS response packets. We propose an architecture to collect and mine data manually or automatically. We showed in a small scale analysis (around 300 MB of data) the ability of our framework to group domain names regarding their activities using the k-means clustering method. We are currently extending this architecture to fit with bigger volume of DNS data by using a distributed data storage and computation system (Hadoop).

In further work we will use this new data storage architecture to apply our technique to bigger data sets such as those from recursive DNS servers from an ISP or similar in order to detect more DNS anomalies. We also plan to extend the approach with more relevant features that can typify traffic more accurately. Finally, passive DNS data will be correlated with data gathered from honeypots to protect a targeted network from malicious domains.

Fig. 1 .

 1 Fig. 1. Hadoop-based DNSSM architecture


Kevin Dominik Korte
email: k.korte@jacobs-university.de

Anuj Sehgal

Jürgen Schönwälder
email: j.schoenwaelder@jacobs-university.de

A Study of the RPL Repair Process Using ContikiRPL

Keywords: Low-power Lossy Networks, RPL Routing, RPL SNMP MIB module, Experimental Evaluation

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The emergence of embedded devices capable of wireless communications is leading to a materialization of an Internet of Things. However, since most such embedded devices do not use an IEEE 802.11 WiFi interface [START_REF] Durvy | Making Sensor Networks IPv6 Ready[END_REF], interconnecting them with the existing Internet infrastructure requires the development of protocols and systems that take into account the low-power and lossy radio standards currently used in embedded networks. To avoid the emergence of devices that are not interoperable and neither documented, the IETF developed the 6LoWPAN standard [START_REF] Hui | Compression Format for IPv6 Datagrams over IEEE 802.15.4-Based Networks[END_REF][START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF] to enable IPv6 networking over the IEEE 802.15.4 radio standard, which is commonly used in embedded networks [START_REF] Kushalnagar | IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement and Goals[END_REF].

The emergence of a standardized IP-based wireless sensor network framework made it apparent that traditional routing schemes, even if they work well on wired networks, are not designed to operate well under the constraints set by wireless sensor networks. Several manufacturers, especially in the field of home automation [START_REF] Martocci | Building Automation Routing Requirements in Low-Power and Lossy Networks[END_REF], have addressed this issue by developing their own proprietary routing solutions. Integrating such systems with the largely standards reliant Internet poses quite a challenge and as such, the IETF developed the RPL routing protocol to address routing in low-power lossy networks in a standard way [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]. In fact, RPL has been developed keeping in mind the constraints posed by the 6LoWPAN adaptation layer, thereby making it a good choice for routing in embedded IPv6 networks.

RPL is designed to consider any specific objective functions, or a combination of objective functions, while choosing a route. Energy available on the path or looseness of the link are two examples of such objective functions that can be imposed in order to obtain routes via RPL. Since RPL is flexible enough to be extended to suit any objective functions, it is possible to attain reasonably good performance in any given situation. However, this flexibility also introduces the peril of encountering a situation where a complex objective function could make the decision making process cost more energy and time than a simple but fixed approach. These combination of advantages and possible pitfalls associated with using RPL make it important to fully understand this routing protocol, which is expected to become the default method for routing in 6LoWPAN networks.

While a number of studies on RPL [START_REF] Tripathi | A Performance Evaluation Study of RPL: Routing Protocol for Low Power and Lossy Networks[END_REF][START_REF]Performance Evaluation of Routing Protocol for Low Power and Lossy Networks (RPL)[END_REF][START_REF] Ko | Evaluating the Performance of RPL and 6LoWPAN in TinyOS[END_REF][START_REF] Ko | ContikiRPL and TinyRPL: Happy Together[END_REF] have already addressed the issues relating to the efficiency of routes discovered and the protocol overhead, this study focuses on node failures within networks using the RPL routing protocol and the ability of the network to recover from these situations. For the purpose of this analysis the RPL implementation provided as part of the Contiki OS [START_REF] Dunkels | Contiki -A Lightweight and Flexible Operating System for Tiny Networked Sensors[END_REF] has been utilized. An implementation of the RPL MIB objects [START_REF] Korte | Definition of Managed Objects for the IPv6 Routing Protocol for Low power and Lossy Networks (RPL)[END_REF] within the Contiki SNMP implementation [START_REF] Kuryla | Implementation and Evaluation of the Simple Network Management Protocol over IEEE 802.15[END_REF][START_REF] Kuryla | Evaluation of the Resource Requirements of SNMP Agents on Constrained Devices[END_REF] allows us to access the necessary data and monitor the routing tree state while a network is deployed.

The following sections of this paper present a discussion of the related work in performance evaluation of RPL, followed by an overview on the RPL routing protocol. An analysis of the RPL rebuild process, along with results, is then presented before conclusion.

Related Work

The authors of [START_REF] Ko | Evaluating the Performance of RPL and 6LoWPAN in TinyOS[END_REF] presented an experimental evaluation of the TinyOS RPL stack named TinyRPL. In their study they come to the conclusion that RPL is not less efficient than the Collection Tree Protocol currently used by TinyOS. To arrive at this conclusion they look at both, the packet reception ratio and the control packet overhead. They also note that RPL, while in storing mode provides backwards routes, which enable communication both from the leaf to the root and vice versa. While this study is interesting, it does not cover the recovery performance of RPL in case of node failures.

In [START_REF] Ko | ContikiRPL and TinyRPL: Happy Together[END_REF] J. Ko et al. evaluate the interoperability of TinyRPL and ContikiRPL implementations. Their work shows that both implementations perform quite well independently. However, they do not perform as well when interoperating. As a result of this outcome they define achieving fast interoperability between the two implementations as one of their future goals. Interoperability of standardized protocols is quite important and this study brings forth important results for the two most popular sensor network operating systems thereby highlighting performance issues that will be addressed in future revisions. However, this study too falls short of analyzing the effect of rebuilds in an RPL tree forced by node failures.

An overview of the weaknesses and strengths of the multiple facets of RPL is provided in [START_REF] Clausen | A critical evaluation of the IPv6 Routing Protocol for Low Power and Lossy Networks (RPL)[END_REF]. In this work, the authors analyze all the different operations and features of the RPL routing protocol in order to provide a better understanding of the strengths and weaknesses this protocol might have. They have also supplemented their study with simulations performed in ns2 and on a wireless sensor network testbed. Their experimental investigation, however, unlike ours is focused upon the multiple timers that assist the trickle algorithm used by RPL and this is used in order to perform a critical evaluation of the workings of RPL. In contrast, our work is focused upon the actual performance of the RPL rebuild mechanisms, rather than a critical assessment of it.

According to Tripathi et al. [START_REF] Tripathi | A Performance Evaluation Study of RPL: Routing Protocol for Low Power and Lossy Networks[END_REF], the results obtained from a simulated network using the RPL routing protocol are also very promising. They come to the conclusion that a network relying solely on global repairs will not be efficient and that therefor the focus has to be on local repair mechanisms. This is the only other study, thus far, which discusses the rebuild process of RPL, however, it is not the main focus. Furthermore, since these tests were performed using a sim-

A Brief Overview of RPL

An analysis of the routing requirements in the low-power and lossy networks area [START_REF] Martocci | Building Automation Routing Requirements in Low-Power and Lossy Networks[END_REF][START_REF] Brandt | Home Automation Routing Requirements in Low-Power and Lossy Networks[END_REF][START_REF] Pister | Industrial Routing Requirements in Low-Power and Lossy Networks[END_REF] led to the development of the RPL routing protocol [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] by the IETF's RoLL working group. To fulfill the multitude of requirements for routing protocols applied in low-power and lossy networks, RPL supports three traffic patterns, namely, point-to-point, point-to-multipoint and multipoint-to-point, as well as an extendable number of objective functions. These objective functions can target the different requirements of the routing tree, such as energy conservation or fastest delivery.

The RPL routing tree is a Destination Oriented Directed Acyclic Graph, in short a DODAG. The construction of a DODAG is started by the root node by broadcasting a DODAG Information Object (DIO). The DIO message contains the configuration of the DODAG, such as its traffic pattern, objective function or rebuild cycle. A node receiving the DIO checks whether it is already a part of this particular DODAG. In case the node is already aware of the DODAG, but the newly received DIO gives it a better rank in the tree, it deletes the old information and proceeds as if it had no prior information regarding the DODAG.

On the other hand, in case the node does not know about the DODAG, it will join the DODAG by storing the information provided by the DIO, computing its own rank using the objective function and informing the parent about this action by a message. The node then propagates the DIO further to its neighborhood, which repeats the action until all nodes have joined the DODAG.

In order to prevent loops from being created in the routing tree, a node is forbidden from selecting a parent with a rank lower than its own current rank. While this does a good job at keeping loops out of the DODAGs, for completeness, RPL is nonetheless equipped with a method to detect loops within the DODAG. In order to detect loops, every routing node in a path prefixes it's own IP header to the packet and every receiving node checks whether any of the prefixed headers has its own IP address as the source address. If the node finds its own IP address a loop is detected. However, unlike loops, one of the main problems in low-power lossy networks is the possibility of nodes disappearing from the network, for example, because they run out of battery power or the link conditions degrade significantly. RPL has a system of methods to route through multiple parents and through siblings to repair the network in order to combat such scenarios of nodes disappearing from a network. The simplest, most useful, but also the most costly repair method, as such, is the global repair of the routing tree. During this process the root node increases the version number of the RPL DODAG and forces a rebuild of the entire DODAG. As is the case with the build process, this rebuild method also guarantees a loop free and best possible routing tree according to the objective function in use.

Since it would be counter productive to rebuild the entire DODAG each time a single node disappears, for smaller problems or between rebuilds, RPL has two prominent local repair methods. The first one allows routing through siblings in range, when a sibling is a node with the same rank. The second method is to switch parents. In Figures 1 and2 one can see the two repair processes, where nodes 2 and 8 are failing, and node 4 is routing through its sibling, while node 10 changes its parent.

Analysis of the ContikiRPL Rebuild Process

Experimental Setup

For the analysis of the RPL rebuild process the RPL implementation provided with the Contiki OS was used. Contiki supports many embedded development platforms, of which some of the popular ones can be seen in Table 1. It is quite clear that each platform offers highly variant capabilities in terms of RAM, flash, clock speed and architecture utilized.

While it might be the first instinct to choose the platform that appears to have the most RAM and flash memory available, this may not be the best strategy as the platform architecture influences the amount of actual resources available. For instance, the Redbee Econotag has a 32-bit ARM7 architecture, which causes it to load the entire program code into RAM before execution unlike the AVR or MSP430. Also, a 32-bit architecture means that machine code produced is generally larger in size than on the 8-bit AVR platform. However, a more thorough analysis of ContikiRPL's resource usage is needed before a platform can be chosen.

The ContikiRPL implementation takes up a lot of memory resources on target platforms. For instance, ContikiRPL on a MSP430 processor based RPL router like the TelosB or TMote Sky platform occupies close to 50kB of flash memory [START_REF] Clausen | A critical evaluation of the IPv6 Routing Protocol for Low Power and Lossy Networks (RPL)[END_REF]. Similarly, on an AVR based platform ContikiRPL also occupies nearly 50kB of flash storage, but more importantly takes up nearly 6kB of RAM, which exclude the MICAz and RZ-Raven USB platforms. While this means that the Atmel RZ-Raven platform does have some RAM left to accommodate other applications as well, in reality the services provided by Contiki itself occupy most of the available RAM thereby not leaving much for a custom application.

As such, a Redbee Econotag was utilized as the target hardware platform, since it provides enough resources to run RPL without issues. The Econotag has a Freescale MC13224v ARM7 microcontroller with 96kB RAM and 128kB Flash and a 802.15.4 radio interface, all of which leave enough resources available even after the basic Contiki installation is used on the device. Furthermore, all nodes in an RPL network need to function in the router mode and as such the Econotag, due to its high RAM and Flash availability, was the most suitable target platform.

For the first three experiments, a network of six Econotags was set up in a linear topology indicated in Figure 3. In this topology, a simple objective function was used, which adds one to the parent rank for white nodes, for nodes with diagonal shading it adds one in the fallback parent testing and 8 in all other cases. This makes the previous white node in the tree the preferred parent to the following couple and secondary parent to its partnering diagonally shaded node. In the parent testing scenario, it also makes the diagonally shaded node the secondary parent to the following nodes and sibling in all other tests. This allows for an analysis of the working of sibling and parent relationships on leaf nodes, as well as their preferential treatment.

For the further experiments on changes within the mesh, the topology was extended to include an additional row of two nodes, as seen in Figure 4. The marking of the nodes and the objective function follow the same pattern as for Figure 3. The additional node marked as "C", in Figures 3 and4, was used to confirm that the local repair did not effect other branches of the network. As such, the local repair counter, as well as the global repair counter were monitored on this node.

The different aspects of the RPL rebuild process that were analyzed during this study are discussed further within their own sub-sections.

Fallback Parent

The aim of the first analysis was to look at the time it took for a node to switch from a failed parent to a secondary parent. Therefore, node two and four were switched off, forcing node three to switch to node one as its only available parent.

To monitor the time it took till node three was reachable again, node three was constantly contacted using ICMP echo requests. Additionally, the counter for the parent switch, which is provided by Contiki RPL, was checked afterwards to ensure the switch over had occurred as expected. To ensure that no rebuild took place, SNMP was used to monitor the DODAG version number of node three, as well as its local and global repair counters. The experiment was repeated until the standard deviation was one tenth of the average or less and until at least 20 values have been collected. Table 2 shows the timeouts, runtimes and the standard deviations for this experiment. As one can see, the average unreachable time of the node during a rebuild was around three and a half minutes.

DIO Timer and Fallback Parent

In an additional step, the DIO Timers were altered to check whether this would influence the behavior of the nodes. After building a DODAG with the new values, the experiment from the previous section was repeated by switching off node 2. Once again, SNMP was used to monitor the version number and counters to ensure that no global repair was taking place.

An overview of the results can be seen in Table 3. These results show that the time it takes for a child to switch from one of the parents to another is not dependent on the time between two DIO messages. Since Contiki relies on its own neighborhood discovery methods to detect failing parents and does not rely on counters between two DIO messages, this can be taken as a confirmation that the Destination Advertisement Object (DAO) and DIO exchange between the node is not affected by the failing node. It also means that extra care has to be taken when selecting the parameters of Contiki's RIME stack in different situations.

Route Lifetime

Another counter that affects the expiration of the downwards routes is the route lifetime counter. By default Contiki sets it to infinity meaning that only when a DAO announcing a change arrives, the nodes will change the routes. Setting it to any other value means that the route is only valid for this number of seconds and that an update is needed afterwards or the route is deleted.

If the time taken for route establishment and parent failure is known in advance, it would be possible to have small timeouts here. For example, the speed of many mobile nodes and their transmission range is known beforehand. This information might be a useful tool to set the timeout to a value forcing a reset when nodes are likely to leave the transmission range.

However, when dealing with static nodes failing due to energy problems or external influences, changing the route lifetime will only drain the nodes of energy as it forces them to send unnecessary announcements and in the worst case the node will fail right after renewing the lifetime. It should also be noted that in some scenarios, for example when having an energy aware objective function, the objective function might poison its rank when routes should be disregarded and the functionality might be doubled.

Fallback Sibling

The secondary fallback method provided by RPL is to route packets through a connection with a sibling. To force a node to use a connection through a sibling, nodes two and three were switched off, leaving node four with only the option to switch to its sibling, node one, in order to establish a working connection. Again ICMP echoes were sent to determine the time it took to find a working route. The values for the DODAG version number and the local repair counter as well as the global repair counter were retrieved. This again helped to ensure that no global repair had occurred but the local repair had taken place.

Table 4 gives the monitored values as well as their standard deviation. The time to rejoin is longer as it involves sending out a solicitation object and DIOs before the node is able to rejoin the tree.

Greediness of Nodes

Another problem when considering the routing tree is that a node may be trying to optimize itself to have as many parents as possible. To control how Contiki handles the greediness of the nodes, nodes one, two and four were switched on in different orders and the status of the RPL parents recorded in node four. The rank of the nodes was also monitored using the SNMP agent running on the nodes. The obtained results showed that ContikiRPL optimizes its rank and is not greedy about its parents. For the node sequence two, four and one, the status of node four with a rank of two and node two as its parent was correct. For the node sequence one, four and two, however, the rank was still correct but the nodes did not forget about the parent. Upon a failure in node two, however, node one was not chosen as a fallback but a local repair was triggered instead. While this behavior means that the node appears to function properly, it makes automated monitoring difficult since the internal state is not consistent with the expected behavior.

Poisoned Tree

The RPL specification defines that upon performing a local repair, a router must poison its routes to indicate that it is moving and to prevent a parent attaching itself to one of its children. To check whether the routers properly poison the downwards routes, the network was set up as shown in the extended network in Figure 4, with node one being turned on after the network is stable. This way node four did not consider one as a parent. Then node two was turned off forcing node three and four to change their parents and thus change their rank, which required them to poison the routes to trigger a full rebuild of their subtree.

During this process nodes three, four and five were monitored. To check the time needed for the local repair to be completed and the message runtimes before and afterwards, ICMP echo messages were used. To verify the repair process, the repair counters for both the global and the local repair on these three nodes were monitored.

Using SNMP it was discerned that the local repair counter on node two increased. The resulting data from this experiment can be seen in Table 5, which illustrates the speed of local repair in case the nodes receive a poisoned rank message. Seeing that the time to reach node five is more then twice as long as the time needed to reach nodes three and four, it is confirmed that Contiki RPL poisons and rebuilds its subtrees as required by RPL.

In a second step, node two was turned on again. This step confirmed that Contiki is not poisoning its subtree wrongly, since a node should only do so if it cannot maintain its current or higher rank. This confirms the behavior found in the greediness analysis, since the node did not forget the old parent.

Rebuild Build Memory

The last experiment focuses on the global rebuild of the DODAG. During a rebuild, a new DODAG is constructed basing itself on the objective function. Since a simple counter function is used, the current state of the DODAG should not influence the new DODAG. In our experiment, the DODAG rebuild was triggered after node two was switched off and the preferred parents and rank of each node was recorded using SNMP. Afterwards, node two was switched on again and preferred parents and rank recorded again. As expected, it turned out that the DODAG was rebuilt without the consideration of the state of the previous DODAG. Thus, the optimal DODAG, according to the objective functions was reached. It was also possible to confirm the result of the greediness analysis, as in all cases, that the best parent was chosen for the rank calculation.

Conclusion

In order to perform this study we designed and implemented an RPL-MIB using the Contiki SNMP agent. The RPL-MIB was utilized in order to study the behavior of the local repair mechanism of RPL. Our analysis has shown that the proposed RPL repair mechanisms work fairly well when given the time needed and that Contiki follows the required path poisoning whenever a local repair takes place, or the rank of the node worsens. It could also be seen that there is little difference between the time it takes to switch from the preferred parent, to the time it takes to switch to a completely new subtree. This leaves the time it takes to find a dead parent as the more important focus point when considering the maximum time allowed for an RPL DODAG to be repaired after a nodes failure or movement. While route timeouts and global repairs offer a working solution in some scenarios, it has to be carefully weighed against the extra energy used.

Fig. 1 .

 1 Fig. 1. A DODAG before the repair process. Borders of inactive nodes and routes are dotted. The shaded node (Node 0) is the sink. (Numbers inside the circles represent the node IDs, while the numbers adjacent to the circles are the rank of each node.)

Fig. 2 .

 2 Fig. 2. A DODAG after the local repairs to a DODAG. Borders of inactive nodes and routes are dotted, repaired routes are marked Green. The shaded node (Node 0) is the sink. (Numbers inside the circles represent the node IDs, while the numbers adjacent to the circles are the rank of each node.)

Fig. 3 .

 3 Fig. 3. The topology; Node 0 is the sink node, nodes with diagonal shading have a modified objective function, the dotted line indicates secondary routes and arrowheads indicate children relations.

Fig. 4 .

 4 Fig. 4. The extended topology; Node 0 is the sink node, nodes with diagonal shading have a modified objective function, the dotted lines indicate secondary routes and arrowheads indicate children relations.

Table 1 .

 1 Computing Resources of Embedded Platforms

	Platform	RAM Flash Clock Speed Architecture
	MICAz	4 kB 128 kB	8 MHz	8-Bit AVR
	Atmel RZ-Raven	16 kB 128 kB	8 MHz	8-Bit AVR
	Atmel RZ-Raven USB 8 kB 128 kB	8 MHz	8-Bit AVR
	TelosB / TMote Sky 10 kB 16 kB	8 MHz	16-Bit MSP430
	Redbee Econotag	96 kB 128 kB	24 MHz	32-Bit ARM7

Table 2 .

 2 Parent Fallback Time

	Monitored Value	Average σ
	ICMP Runtime before disconnect 43.4ms 0.8ms
	ICMP Runtime after fallback	43.8ms 1.0ms
	ICMP Timeouts	211s	19.4s

Table 3 .

 3 DIO Timer and Fallback Time

	DIO Timer Average ICMP Timeout
	2 3	203s
	2 5	215s
	2 7	214s
	2 9	214s
	2 12	211s

Table 4 .

 4 Sibling Fallback Time

	Monitored Value	Average σ
	ICMP Runtime before disconnect 43.5ms 0.8ms
	ICMP Runtime after fallback	43.6ms 0.9ms
	ICMP Timeouts	236s	13s

Table 5 .

 5 Poisoning the Sub-DODAG

	Monitored Value	Node 3 σ Node 4 σ Node 5 σ
	ICMP Runtime before disconnect 44.3ms 0.7ms 44.8ms 0.3ms 63.4ms 0.9ms
	ICMP Runtime after fallback	44.2ms 0.8ms 44.9ms 0.6ms 62.3ms 1.2ms
	ICMP Timeouts	235s	12s	234s	6s	265s	18s