Alexander Frömmgen

Björn Richerzhagen

Julius Rückert

David Hausheer

Ralf Steinmetz

Alejandro Buchmann

Towards the Description and Execution of Transitions in Networked Systems

Today's distributed systems have to work in changing environments and under different working conditions. To provide high performance under these changing conditions, many distributed systems implement adaptive behavior. While simple adaptation through parameter tuning can only react to a limited range of conditions, a switch between different mechanisms at runtime enables broader adaptivity. However, distributed systems that switch mechanisms at runtime lack a clear abstraction for the adaptive behavior and, thus, usually interleave the adaptation and actual application logic. This leads to complex and error-prone systems that are hard to maintain and not easy to extend. In this paper, we analyze the adaptations of two distributed systems from different application domains. We identify recurring requirements as well as life cycles of transitions between mechanisms. Based on this, we present a framework that provides a clear abstraction of the underlying transition logic and manages the transitions at runtime. The concept is applied to the two example systems to practically evaluate its benefits. We show that our approach leads to less complex realizations of the adaptive behavior and allows new mechanisms to be integrated easily.

Introduction

Today's distributed systems operate in challenging environments with rapidly changing working conditions. In order to provide high performance in such dynamic environments, systems need to be highly adaptive. However, simple adaptations by means of configuration parameter adjustments can only react to a limited range of conditions. As distributed systems can be described as a combination of multiple functional blocks, in the following called Mechanisms, the ability to switch between mechanisms at runtime and the possibility to extend the system by novel mechanism, proved to provide greater flexibility and enables the system to adapt to a wider range of environmental conditions [START_REF] Richerzhagen | Bypassing the Cloud: Peer-assisted Event Dissemination for Augmented Reality Games[END_REF][START_REF] Wichtlhuber | TRANSIT: Supporting Transitions in Peer-to-Peer Live Video Streaming[END_REF]. In the following, such switches between mechanisms are referred to as Transitions.

While this idea is appealing, so far, there exists neither a systematic approach of how to generically integrate multiple mechanisms in a complex distributed system, nor how to systematically execute and coordinate transitions between mechanisms at runtime. The latter is especially challenging as it requires a deep understanding of mechanism life cycles and a generic approach for state transfers between mechanisms in transition. As adaptivity has complex implications for the overall system, an explicit design of transition-enabled adaptive behavior is necessary and essential. So far, existing adaptive distributed systems lack a clear separation of concerns between the logic realizing adaptivity (the transition logic) and the actual application logic. A general concept to design and implement systems that allow for adaptivity in all key aspects is missing so far.

In this work, we propose a formal description of adaptivity through transitions and provide system developers with a sophisticated framework to describe and realize mechanism transitions in distributed systems. The approach allows mechanisms to be easily added over time to address new scenarios. Furthermore, the framework enables a clear separation of concerns between the transition and application logic. To identify the relevant functionality for the framework, two state-of-the-art systems (Bypass [START_REF] Richerzhagen | Bypassing the Cloud: Peer-assisted Event Dissemination for Augmented Reality Games[END_REF] and Transit [START_REF] Wichtlhuber | TRANSIT: Supporting Transitions in Peer-to-Peer Live Video Streaming[END_REF]) targeting different application domains are analyzed. Even though both systems proved already that they highly benefit from adaptive behavior, a systematic approach to describe this behavior is missing so far. Based on the results, a first general design for the execution of transitions is derived and applied to the analyzed systems. By following the presented design, the mechanisms still define their application-specific interfaces. Additionally, transition-enabled mechanisms follow a common life cycle approach, managed by the framework. This allows us to (i) define Elementary Transitions between mechanism instances that can be performed during runtime and (ii) easily add new (specialized) mechanisms and transitions to an existing system. First proof-of-concept applications and initial evaluation results show that the approach is well-suited to describe and enable generic adaptivity in distributed systems by supporting mechanism transitions. As this work concentrates on the description and execution of transitions, the highly domain-specific adaptation decisions (based on performance models such as queuing models) are not discussed. However, our work poses a first step towards a generalization of the decision process by providing a unified description and handling of transitions in distributed systems.

The remainder of the paper is structured as follows: Section 2 presents the analysis of two existing adaptive systems and the derivation of requirements for the transition execution framework. The developed methodology, the derived life cycles and the framework is presented in Section 3 and discussed in Section 4. Subsequently, Section 5 presents related work and Section 6 concludes the paper.

Requirements Derivation

In this section, we analyze two state-of-the-art distributed systems and derive requirements for a transition framework.

Analysis of Bypass

Bypass [START_REF] Richerzhagen | Bypassing the Cloud: Peer-assisted Event Dissemination for Augmented Reality Games[END_REF] provides low-latency event dissemination for interactive mobile augmented reality games. In the targeted application scenario most events generated by mobile players are only relevant within a given area of interest around the player's current position. Therefore, once groups of nearby players are detected, the system adapts to local event delivery via ad hoc dissemination protocols. Depending on relevant environmental conditions (e.g. the group size), the local dissemination protocol is reconfigured or replaced. The original paper showed the benefit of adaptations to two local dissemination protocols: (i) a range-limited broadcast scheme and (ii) a probabilistic, gossip-like scheme. The authors further mention the possibility to switch between physical layer protocols, such as Wi-Fi ad hoc and Bluetooth. This leads to an architecture with a set of potential compositions as shown in Figure 1. The reconfigurations, i.e. the transitions between the local dissemination protocols, are not explicitly modeled in [START_REF] Richerzhagen | Bypassing the Cloud: Peer-assisted Event Dissemination for Augmented Reality Games[END_REF]. Instead, they are interweaved with the application logic and part of a predefined adaptation strategy at the cloudbased controller. Thus, no existing implementation for the recurring handling of transitions is used. This raises concerns as to how maintainable the adaptation implementation is, in particular how feasible it is to add new dissemination protocols, and how to implement the complex switch between these at runtime. We argue that a systematic methodology and a framework which supports this with well-defined interfaces for transition-enabled mechanisms significantly reduces the complexity of implementing and extending an adaptive distributed system.

Furthermore, the authors show that some nodes utilize different dissemination protocols. This causes approximately 40% of the overall message loss. We therefore propose an explicit life cycle management for the mechanisms involved in a transition. The coordinated life cycle has to enable a smooth handoff between two mechanisms, thereby reducing the amount of lost events caused by the transition itself.

The additionally possible transitions between Wi-Fi ad hoc and Bluetooth impose challenges to the existing transition handling. First of all, the establishment of the Bluetooth connection requires at least a short period of time, which causes an increased latency. Second, the establishment of the connections might fail for multiple reasons, which has to be compensated by the application. Switching between Wi-Fi and Bluetooth also affects the currently utilized dissemination protocol. Furthermore, sophisticated protocols require a specific physical layer protocol as they rely on assumptions regarding communication characteristics such as range or reliability. Therefore, we propose to build compositions of transitions to reflect dependencies, e.g. a transition between physical layer protocols might depend on a transition of the dissemination protocol.

As the aforementioned challenges are recurring for transitions in adaptive distributed systems, they should be handled by a transition framework to reduce the complexity. Depending on the mechanisms, state such as routes or neighbor tables are maintained that could benefit the target mechanism. Transferring state requires domain-specific knowledge, while conceptually being part of the transition logic. A transition framework needs to provide ways to utilize such knowledge in the transition handling to benefit the overall system.

Analysis of Transit

The streaming system Transit [START_REF] Wichtlhuber | TRANSIT: Supporting Transitions in Peer-to-Peer Live Video Streaming[END_REF] realizes an overlay-based multicast service that adapts to a wide range of working conditions. For this, a main feature of the system is to flexibly adapt its overlay topology, which is used to distribute the video streams among participants in the system. The adaptivity is realized by different sets of topology optimizations (cf. Figure 2). These optimizations are usually executed in a distributed manner at the participants, also called peers in the following. While Transit includes several other mechanisms that realize adaptivity, including an extension [START_REF] Rückert | Software-Defined Multicast for Over-the-Top and Overlay-based Live Streaming in ISP Networks[END_REF] for network-layer multicast, in the following, we focus on overlay topology optimizations as they promise to have great potential for the adaptation considerations in this work. A challenging use case for topology adaptations are flash crowds, which are common to large-scale (video) streaming events. A large number of users needs to be quickly connected to the system. While in non-flash crowd times complex optimizations are reasonable to gradually improve the delivery process, here it is essential to quickly attach new peers to the topology and serve them with a low startup delay. One way to achieve this is to build topologies where many peers have free upload slots. Complex topology optimizations that could interfere with the attachment process should be disabled during the massive join phases of a flash crowd. Both can be achieved by defining topology optimizations strategies that define which optimizations are run. Therefore, as the topology adaptation logic is already modularized, this part of the system could greatly benefit from well-defined interfaces for transition-enabled components. Even though transitions between topology optimizations seem less complex as transitions in Bypass, a unified transition model which covers recurring challenges would improve the current systems and allow to build more complex systems easily.

Design and Description Methodology

Analysis of Transition Life Cycles

The systematic development of adaptive distributed systems requires abstractions. In the following, the Elementary Transition is introduced as the basic building block. Therefore, the Life Cycle of an elementary transition is defined based on the life cycle of the involved components. As the execution of a mechanism (e.g. Bypass's dissemination protocol) can be distributed over multiple nodes, we use Components as the smallest unit which is exchanged through a transition. A component implements all mechanism logic that is executed on a single node. Thus, the Broadcast components at multiple nodes together represent the Broadcast Dissemination mechanism in the distributed system.

To allow the application developer to abstract from the transition logic, a proxy [START_REF] Gamma | Design Patterns: Elements of Reusable Object-oriented Software[END_REF] component is used instead of the actual component. This proxy intercepts all method invocations and forwards them to the currently active component instance. This enables a clear separation of concerns, as it strictly separates the application logic from the transition logic. The application only interacts with the proxy. A transition affects the inner workings of the proxy while leaving the reference to the proxy and the interface for the application unchanged. The proxy hides the exchange of the Source component with the Target component 4 . Additionally, the proxy instance ensures a thread-safe transition in a multithreaded environment. A transition between two components, for example, might not be executed while one thread is executing the source component (more precisely: while at least one method of the source component instance is part of a current execution stack). Similar problems might occur for application layer protocols, e.g. finishing a communication sequence before executing the transition. This follows the idea of quiescence as discussed by Pissias et al. [START_REF] Pissias | Framework for Quiescence Management in Support of Reconfigurable Multi-threaded Component-based Systems[END_REF]. Components on different nodes interact, thereby forming a mechanism.

Our analysis of the existing adaptive systems and their requirements lead to two kinds of elementary transitions, the runrun and the flip transition. Their most important difference is the life cycle and the parallel usage of the involved components. The flip transition does not execute both components in parallel and, thus, executes a hard switch, whereas the runrun transition smoothes the transition and executes both components in parallel for a short period of time, enabling a handover of, e.g., protocol state. Even though the runrun transition seems to be favorable, the flip transition is sometimes beneficial or even required due to resource constraints. For example, most mobile devices do not support the parallel usage of infrastructure Wi-Fi and Wi-Fi ad hoc, the parallel usage of Wi-Fi and LTE causes a higher energy consumption, and exclusive used software handles, e.g. established socket connections, cannot be shared. In the following, we discuss both transition types in detail.

Flip Transitions

The flip transition executes an abrupt switch between the source and target component. Figure 4 shows the life cycle of a component for such a transition. We model the life cycle as a mealy state machine which exchanges messages between the coordinating instance (the transition engine) and the component. Therefore, the state transitions of the state machine are annotated with the triggering messages (the input) which are sent to the component (above the bar) and the expected answer when the new state is reached (below the bar). For example, the transition engine signals an init to a newly created component. Once the component followed its internal initialization steps, it signals finished back to the transition engine leading to the Initialized state. During the initialization, the component executes preparation tasks such as allocating memory. The proxy ensures that methods of the component are not yet invoked. After the component has started successfully, and therefore can use the shared resources, it reaches the Running state and is used by the application. In case the component start fails, e.g. due to a network connection failure, it reaches the Aborted state. From the software engineering point of view, the actual constructor logic is distributed among the init and the start state transition.

Based on the component life cycle, we specify the life cycle of the flip transition (Figure 5). We denote messages exchanged with the components with an according prefix (src:, trg:). The parent:-prefix is used for message exchanges with the local transition engine as discussed later in this section. As the start of the target component may fail, the Initialized state has two outgoing state transitions. In case of a success, the flip transition finishes. Otherwise, the local transition engine decides, based on the specification of the application developer, if a new recovery component instance should be initialized or the transition fails. Please note that the details of these steps are skipped in the figure due to clarity. Runrun Transitions To reduce the performance degradation during the transition and allow a smooth transition, the runrun transition deactivates the source component when the target component is already running. This interweaving requires both components to be executed in parallel. The component life cycle reflects this with additional states (cf. Figure 6). The main difference is the state transition to the Active state and, thus, to the internal Running state. The Active-state additionally contains an In Shutdown state. Methods of the component can be executed during both internal active states. As the state transition to the Running state may fail, there is a state transition to the Aborted state as well. Additionally, the source component can be triggered to return to the Running state. In the Active state, the component can execute a state transition to the Cleaned Up state and clean up. Based on this component life cycle, we define the life cycle of an elementary runrun transition (Figure 7). As the source component can be used in the In Shutdown state, the proxy can always forward method invocations, and therefore never blocks the application. This holds even for the time during the state transitions to the Parallel Active and the Aborted state. In case the start of the target component fails, the transition can always return to the source component. As the local transition engine coordinates the execution of a transition, it triggers the state transition to the Clean up and the Rollback state. Even though the component life cycle introduces a strict contract for the components, it allows easily integrating new mechanisms.

A Framework for Transition Description and Execution

Based on the two identified transition types and their life cycles, a systematic description and framework support for transitions is possible. In the following, we propose a transition description language, possible framework support, and suitable visualizations.

The transition description language allows to specify all available transitions and their affected components, as illustrated in Listing 1.1. As typical use cases have only a limited number of possible transitions, the exhaustive description of all transitions is without difficulty. Based on the described transitions, a Global Transition Engine coordinates Local Transition Engines to execute distributed transitions. As both analyzed distributed systems have a centralized instance (the Cloud Server for Bypass and the Tracker for Transit), the assumption of a global transition engine is reasonable.

The coordination and synchronization of the proxies can be implemented efficiently. As in the two example applications multiple nodes execute the same transitions, the global transition engine does not require a huge and complex state machine (e.g. a Cartesian product of the involved life cycle states). Instead, a single state at the global transition engine can represent multiple states of the nodes. For scalability reasons, the global transition engine could use sub coordinators to handle the coordination messages. As this work focuses on the description and execution of transitions, a central coordinator is assumed. However, for future work, the methodology could be extended to support applications with a decentralized transition control.

The transition engines use the additional information from the transition description to control the transition execution. For example, the time the transition stays in the parallel active state (line 4), and the timeout which leads to a rollback of the transition (line 7) can be specified. In case a 'best effort' approach is sufficient, it is also possible to partly deactivate the transition coordination.

During both kinds of transition, state from the source component can be transferred to the target component. This state is represented by the references of the component and class instances which the source component transfers to the target component. As the transitions in the two analyzed systems both transfer this state in the life cycle state transition to the Running state, the framework makes this state transfer explicit and supports it in the transition description language (Listing 1.1 line 3). Components which only implement the stateless strategy pattern [START_REF] Gamma | Design Patterns: Elements of Reusable Object-oriented Software[END_REF] do not require state transfer. § ¤ Additional domain specific transition logic can be added in the host language and is invoked by the transition engine during the life cycle events. Such additional transition logic can, for example, be used to perform more complex state transfers involving the transformation of data. Even though both evaluated systems are based on Java, the presented approach is agnostic of the utilized programming language. The explicit notation of the transitions allows a clear separation between components and transitions and, this way, enables a systematic development of distributed adaptive systems. A framework which explicitly supports transitions between components and manages their execution provides multiple additional benefits. Besides development and debugging support, it can, for example, monitor and ensure that only one transition per proxy instance is executed at the same time, and started transitions finally terminate.

Traditionally, there are two viewpoints on systems, the structural and the behavioral [START_REF] Hilliard | Recommended Practice for Architectural Description of Softwareintensive Systems[END_REF]. The composition of components describes structural properties, whereas the execution of a transition is behavior which changes the structure. We propose a combined view as a class diagram (Figure 8). The ternary association connects the source and the target component with the specific transition logic. The stereotypes TransitionEnabled and TransitionLogic are resolved to implementations of the corresponding interfaces. The transferred state (more precisely, the transferred references to other objects) is visualized as well.

Discussion

To assess the impact of the proposed design methodology, the presented concepts were applied on both systems. For the existing transitions between local dissemination protocols in Bypass, the new version which leverages the framework reduces the transition specific lines of code to roughly 20% of the original code. This greatly reduces the complexity of the implementation. Even more important, the transition-specific source code is no longer part of the application logic but instead encapsulated by the transition engine, providing separation of concerns. Additionally, this reduces the error probability, as proved transition handling code is reused. In addition to porting Bypass to our framework, we added new component that encapsulate the physical layer protocols as proposed by the authors. Therefore, the existing interaction via Wi-Fi ad hoc was realized as a component instance as shown in Figure 1. Additionally, we added a component instance that enables local communication via Bluetooth and defined a runrun transition between both instances (cf. Listing 1.2). Our implementations show that Bypass benefits from the concept of parallel and sequential transitions. Switching the local dissemination protocol after the physical protocol switched successfully, is defined as a sequential transition (Listing 1.2), composed of two elementary transitions. In case the connection setup using Bluetooth fails, the overall transition returns to a well-defined system state. Considering the life cycle of a runrun transition (Figure 7), the transition enters the Aborted state and consequently recovers by just continuing to use Wi-Fi as active component instance. Composing transitions out of elementary transitions is straight forward with the presented framework, as they can easily be described in the transition description language. Thereby, common pitfalls such as illegal combinations or undefined transitions are detected early. The abstraction of the underlying life cycle enables more complex combinations. For future work, it is interesting to combine constraints on the possible component compositions and properties of the compositions, e.g. as proposed by [START_REF] Frömmgen | A Property Description Framework for Composable Software[END_REF], to further support the developer, e.g. verify legal transitions. Applying the concept to transitions between topology optimization strategies in Transit was possible in a straightforward manner with very localized changes at the respective components. As an extension, the concept of so called Optimization Providers was introduced to bundle sets of currently active topology optimizations. The transition framework was then used to allow for flip transitions between different provider implementations. As topology optimizations and their execution are decoupled by design, there was no need to consider optimizations and providers that are active in a parallel manner. Providers that reuse topology optimization instances (in case two providers include similar optimizations) benefit from the automatic state transfer of the framework. As a side effect, the approach showed to be very helpful to rapidly define and evaluate new optimization combinations for new scenarios. With the legacy implementation, this requires large changes to various parts of the optimization implementations, thus heavily mixing adaptation and application behavior.

Related Work

Compositional adaptation [START_REF] Mckinley | Composing Adaptive Software[END_REF] is an established concept for adaptive systems. Many systems [START_REF] Felber | Towards reliable CORBA: Integration vs. service approach[END_REF][START_REF] Sadjadi | MetaSockets: Design and Operation of Runtime Reconfigurable Communication Services: Experiences with Auto-adaptive and Reconfigurable Systems[END_REF][START_REF] Sadjadi | ACT: An Adaptive CORBA Template to Support Unanticipated Adaptation[END_REF] leverage proxies to enable transparent dynamic composition for the application or extend the host language to enable adaptive behavior [START_REF] Kasten | Separating Introspection and Intercession to Support Metamorphic Distributed Systems[END_REF]. Sadjadi et al. [START_REF] Sadjadi | MetaSockets: Design and Operation of Runtime Reconfigurable Communication Services: Experiences with Auto-adaptive and Reconfigurable Systems[END_REF] use this concept for communication systems and adapt between different forward error correction schemes in the network. However, these systems lack a model for the actual transition life cycle and state transfer. Additionally, they do not provide abstractions for multiple (parallel or sequential) transitions, even though their proxies can be distributed.

Many component-based systems benefit from an explicit component life cycle. In OSGi [START_REF]OSGi Service Platform Core Specification[END_REF], for example, bundles and their components follow a clear life cycle. This enables OSGi to install, update, remove, start, and stop components at runtime without stopping the system. The different components are loosely coupled using service bindings. Even though our presented component life cycle is inspired by the bundle life cycle in OSGi, we consequently enhance this concept to model the life cycle of transitions between components in distributed environments. This reduces the switching costs and allows transfer state and composed transitions. The handling of service bindings is hidden by the proxies.

IBM proposes the MAPE-K concept for autonomic control loops [START_REF]An Architectural Blueprint for Autonomic Computing[END_REF]. In this model, the Autonomic Manager manages the tasks monitor, analyze, plan, and execute as well as the globally shared knowledge. Effectors perform changes on Managed Elements, which represent any adaptive software/hardware component. Our proxies represent a special of managed element with clearly modeled transition capabilities. The transition description is globally shared knowledge.

Ferreira et al. [START_REF] Ferreira | A-OSGi: A Framework to Support the Construction of Autonomic OSGi-Based Applications[END_REF] developed A-OSGi to support the construction of autonomic OSGi-based applications. Therefore, they integrate the MAPE-K approach into OSGi. Concentrating on the monitoring, the actual adaptations are simple service binding changes, bundle starts, or changes of service properties. A detailed concept for more complex component exchanges and state transfer is missing.

The knowledge about valid configurations and component compositions is important to deal with reconfiguration consistency. Batista et al. [START_REF] Batista | Managing Dynamic Reconfiguration in Component-based Systems[END_REF], for example, model this and use it to check reconfigurations, but do not investigate the actual transitions which lead to these configurations. As our current solution concentrates on the description and the life cycle of transitions, integration of both approaches might allow to reason about consistent and legal transitions.

Coulson et al. [START_REF] Coulson | The Design of a Configurable and Reconfigurable Middleware Platform[END_REF] propose a middleware approach for reconfigurable distributed systems. The middleware is utilized in the publish/subscribe system GREEN [START_REF] Sivaharan | GREEN: A Configurable and Re-configurable Publish-Subscribe Middleware for Pervasive Computing[END_REF] to enable reconfiguration of multiple publish/subscribe-specific components. However, they do not provide a clear description of the reconfiguration possibilities. Transitions in between configurations and implications such as state transfer and life cycle management are not detailed.

Conclusion and Future Work

In this paper, we identified recurring requirements to handle adaptive behavior in distributed systems. Based on this, we proposed a framework which supports two transition life cycles and provides a clear abstraction of the underlying complex transition logic. The concept was applied to two example systems to practically evaluate its benefits. In both cases, the approach leads to less complex realizations of adaptivity and allows new mechanisms to be integrated easily.

For future work, we consider to leverage the proposed concept and methodology to design and study a new class of highly adaptive distributed systems that were not feasible so far. While the proposed approach builds the foundation for this, additional support for more dependencies between transitions and according coordination strategies, e.g. a decentralized coordination, need to be developed as next steps.

Fig. 1 :

 1 Fig. 1: Overview of Bypass and the possible transitions.

Fig. 2 :

 2 Fig. 2: Exemplary mechanisms and transitions in Transit.

Fig. 3 :

 3 Fig.3: Mechanisms comprise concurrently executed components on multiple nodes, each managed by a proxy instance.

Figure 3

 3 Figure 3 illustrates the overall architecture with multiple nodes, each executing components managed by proxies. The proxies are managed by the Local Transition Engine, which in turn is coordinated by the Global Transition Engine.Components on different nodes interact, thereby forming a mechanism.Our analysis of the existing adaptive systems and their requirements lead to two kinds of elementary transitions, the runrun and the flip transition. Their most important difference is the life cycle and the parallel usage of the involved components. The flip transition does not execute both components in parallel and, thus, executes a hard switch, whereas the runrun transition smoothes the transition and executes both components in parallel for a short period of time, enabling a handover of, e.g., protocol state. Even though the runrun transition seems to be favorable, the flip transition is sometimes beneficial or even required due to resource constraints. For example, most mobile devices do not support the parallel usage of infrastructure Wi-Fi and Wi-Fi ad hoc, the parallel usage of Wi-Fi and LTE causes a higher energy consumption, and exclusive used software handles, e.g. established socket connections, cannot be shared. In the following, we discuss both transition types in detail.

Fig. 4 :

 4 Fig. 4: Single component life cycle of a flip transition.

Fig. 5 :

 5 Fig. 5: Overall life cycle of a flip transition.

Fig. 6 :

 6 Fig. 6: Single component life cycle of a runrun transition.

Fig. 7 :

 7 Fig. 7: Overall life cycle of a runrun transition.

Fig. 8 :

 8 Fig. 8: UML visualization of transitions and the composition variability of components.

§ ¤ 1

 1 define elementary transition WiFi2BT 2 from WiFiAdHoc to Bluetooth type runrun; 3 define elementary transition Gossip2BC 4 from Gossip to Broadcast type runrun; 5 define sequential transition SeqTrans (WiFi2BT, Gossip2BC); ¦ ¥ Listing 1.2: An elementary transition from Wi-Fi to Bluetooth composed with a subsequent dissemination protocol transition.

In the following, component is used instead of component instance.

Acknowledgments

This work has been funded by the German Research Foundation (DFG) within the Collaborative Research Center (CRC) 1053 -MAKI.


domain: spi info math

text:
ML estimation in the presence of a nuisance vector

Using the Expectation Maximization (EM) algorithm

Or the Bayesian Expectation Maximization (BEM) algorithm

Cances Jean-Pierre (Octobre 2009), Xlim UMR 7252

The scope of this paper is to give a general framework to use two recent sophisticated algorithms for signal processing communication applications: EM and BEM algorithms. Some contexts of application are then illustrated as application examples.

I. General Framework for EM algorithm :

We denote with r a random vector obtained by expanding the received modulated signal r(t) onto a suitable basis, and we indicate with b a deterministic vector of parameters to be estimated from the observation of the received vector r. Assume that r also depends on a random nuisance parameter vector a independent of b and with a priori probability density function (pdf) () p a . The problem addressed here is to find the ML estimate b of b, that is to say, the solution of: The likelihood function to be maximized with respect to the trial value  b of b is obtained after elimination of the nuisance parameter vector a as follows:

In order to solve (1), we take the derivative of ln ( ) p  rb with respect to  b and we equate it to zero, that is: [START_REF] Xie | Two EM-type channel estimation algorithm for ofdm with transmitter diversity[END_REF] In other words, the ML estimate b of b is that value that nulls the conditional a posteriori expectation of the derivative with respect to  b of the conditional log-likelihood function (LLF) ln ( , ) p  r a b . Finding the solution of ( 4) is not trivial, since  b appears in both factors of the integrand. Thus, we try an iterative procedure that produces a sequence of values () ˆn b hopefully converging to the desired solution. In particular, we use the previous sequence value ( 1) ˆn b to resolve the conditioning on the first factor of the integrand, and we find the current solution [START_REF] Zhang | Iterative Carrier Phase Recovery Suited to Turbo-Coded Systems[END_REF] If the sequence of estimates () ˆn b yielded by (5) converges to a finite value, that value is a solution of ML equation ( 4) [START_REF] Moon | The expectation-maximization algorithm[END_REF]. Observe now that the first factor of the integrand in [START_REF] Zhang | Iterative Carrier Phase Recovery Suited to Turbo-Coded Systems[END_REF] does not depend on () ˆn b . Therefore, we can bring the derivative back out of the integral and obtain the equivalent equation: [START_REF] Helstrom | Elements of Signal Detection & Estimation[END_REF] that is, the estimate () ˆn b maximizes the conditional a posteriori expectation of the conditional LLF ln ( , ) p

( ) ( , ) ln ( ) ( ) ( , ) (
 r a b :   ( ) ( -1) ˆârg max ( , ) nn    b b b b (7-a)   ( 1) ( -1)
-(i) expectation step (E-step)   ( 1) ( 1) ˆ( , ) ln ( ) , nn Q E p    a b b z b r b (8-a) -(ii) maximization step (M-step)   ( ) ( 1)
ˆârg max ( ,

) nn Q     b b b b (8-b)
converges to the ML estimate under mild conditions [START_REF] Feder | Parameter estimation of superimposed signals using the em algorithm[END_REF][START_REF] Georghiades | Sequence estimation in the presence of random parameters via the EM algorithm[END_REF]. To make (8-a) (8-b) equivalent to (7-a) (7-b), we observe that, by using Bayes rule and considering that the distribution of a does not depend on the parameter vector to be estimated: Therefore, substituting ( 9) in (8-a), we get :

( ) ( , ) ( , ) ( ) ( ,
( [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate[END_REF] The second term I 2 in [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate[END_REF] does not depend on  b , and as far the M-step is concerned, it can be dropped. Consequently, the estimation procedure given by (7-a) (7-b) and the EM algorithm defined by (8-a) (8-b), yield the same sequence of estimates. We explicitly observe that the solution of (1) can be found iteratively be only using a posteriori probabilities

II. Application of EM to Synchronization for SISO-based receivers :

EM-based synchronization

We show here how to apply the general framework of the previous section to the estimation of the synchronization parameters for a digital data-modulated bandpass signal. In this context, the nuisance parameter vector a contains the values of the N unknown (hence random) transmitted symbols, that is,

  0 1 1 , , , T N a a a    a
. Those symbols take values in an M-point constellation  (M-PSK, M-QAM,…). Thus, the vector a has a probability mass function (pmf) ()

P  a  , with   0 1 1 , , , N         and N  
. The vector b contains the synchronization parameters to be estimated, that is,

 

, , ,

T A     b
where , , , A    are the channel gain, symbol timing, carrier frequency, and phase offsets, respectively. Here, the synchronization parameters are assumed as constant within the received code block. This has the advantage of simplifying notably the processing required by the estimation algorithm. Furthermore, for the sake of simplicity, we will consider in the sequel an AWGN channel as well. Hence, the baseband received signal r(t) can be written as:

N jt k k r t A a g t k T e w t             ( 11
)
where T is the symbol period, g(t) is a unit-energy (square-root raised-cosine) pulse, and w(t) is complex-valued AWGN with power spectral density 2.N 0 (assumed to be known). Neglecting irrelevant terms independent of a and b, the conditional LLF of ( 11) is  

               ( 13
)
is obtained by precompensating the received signal by the trial value    , then applying the result to the matched filter g(-t), and finally sampling the matched filter output at the trial instant .

t k T    . Substituting (12) into (7-b) and dropping the terms which do not depend on  b , we get:

* 1 ( -1) ( -1) . 0 1 2 2 ( -1) 0 ˆ( , ) 2. .Re ( , ) ( , ). ( ,
) ( , )

N n n j kk k N n k k A a p d z v e A a p d                             
N n n j kk k N n k k A z v e A                    b b r b rb (16)
We emphasize the similarity between ( 12) and ( 16): the latter is formally obtained from the former by simply replacing the terms

rb

. The new estimate () ˆn b at the nth step is then determined by applying (7-a) and therefore by maximizing

( -1) ( , ) n   bb ,
given by ( 16) with respect to  b . The corresponding result is:

1 ( ) ( ) * ( -1) ˆ, 0 , arg max ( , ). ( , ) N n n n kk k zv                rb (17-a) () ˆn      1 * ( -1) ( ) ( ) 0 ( , ). [ , ] N n n n kk k zv      rb (17-b) 1 * ( -1) ( ) ( ) 0 () 1 ( 1) 0 ( ,
).

[ , ] ˆ( ,

) N n n n kk k n N n k k zv A            rb rb (17-c)
The obtained solution can be interpreted as an iterative synchronization procedure, which can be referred to as soft-decision-directed (SDD) synchronization. What we call here soft decisions are the a posteriori average values We now concentrate on the evaluation of the marginal a posteriori symbol probabilities. Whereas for uncoded transmission the usual assumption is that data symbols are independent and equally likely (yielding ()

N PM   a  for all N  
), for a coded transmission with code rate , we only have a subset N B  of all possible sequences corresponding to N M  legitimate encoder output sequences. Therefore, taking into account that the APP of the symbol sequence a is given by:

( ). ( , ) ( , ) ( ). ( , ) B Pp P Pp           a r a b a r b a r a b   (18)
and assuming that: , () 0,

N MB P B           a    (19) we get: ( , ) , ( , ) ( , ) 0,
B p B p P B                   r a = b r a b a r b     (20)
which relates the APP of the symbol sequence to the conditional likelihood function. Note that the result for uncoded transmission is obtained from (20) by taking N B  . Finally, the marginal APP related to a symbol a k is obtained summing the symbol sequence APPs (20) over all symbols a i with i ≠ k. Evaluation of the APPs according to (20) yields a computational complexity that increases exponentially with the sequence length N, as all possible data sequences must be enumerated. However, in systems where the received signal can be modeled as a Markov process, the marginal symbol APPs can be efficiently obtained using the BCJR algorithm with a complexity that grows only linearly with the sequence length N.

Using a simple gate function for h(t) instead of the square-root raised-cosine filter, we can completely compute ).

( -1) ( , ) n   bb . We have: .2. . . ( , ) ( ). . ( .
jt k z v r t e h t k T dt              (21)
j k T j T kk T z v A a e e                            (23)
For the computation of

( -1) ( , ) n k  rb
, we suppose that a simple BPSK is used and we get:

( -1) () ( , ) tanh( ) 2 n nk k La   rb ( 24
)
with n denoting the nth corresponding turbo iteration. Then, combining (23) and (24) we eventually obtain:

N nj L k k k N j j k T j T nk k k v A a p d z v e La T A A a e e e                                                           a a r b a ( 25
)
Looking for a maximum value in (25) with tentative values ,    constitutes a highly complicated task. One way of simplifying this problem would be to expand ( , )

L v    as a Fourier serie [START_REF] Zhang | Iterative Carrier Phase Recovery Suited to Turbo-Coded Systems[END_REF].

III. General Framework for BEM algorithm :

In order to introduce the key differences between EM and BEM, we recall the main properties of EM. Let

  0 1 1 , ,..., T L    
denote an L-dimensional deterministic vector to be estimated from an N-dimensional received vector

0 1 1 [ , ,..., ] T N R R R   R
of noisy data (with N ≥ L). The ML estimation of  is the solution of the problem [START_REF] Helstrom | Elements of Signal Detection & Estimation[END_REF] arg max ( )

ML r L      (26)
where ( ) log ( )

r Lf   r
 is a log-likelihood function and () f xy denotes the probability density function (pdf) of the random vector X conditioned on the event    Yy . Solving the problem (26) in a direct fashion requires a closed form expression for () r L   but, even if this expression is available, the search for its maximum may entail an unacceptable computational burden. When this occurs, a feasible alternative can be offered by the EM algorithm [START_REF] Moon | The expectation-maximization algorithm[END_REF][START_REF] Feder | Parameter estimation of superimposed signals using the em algorithm[END_REF]. The EM approach develops from the assumption that a complete data vector

0 1 1 [ , ,..., ] T P C C C   C
(with P ≥ N) is observed in place of the incomplete data set R. The vector C is characterized by a couple bof relevant properties: (1) it is not observed directly but, if available, would ease the estimation of  ; (2) R can be obtained from C through a many-to-one mapping ()  C R C . In practice, in communication problems, C is always chosen as a superset of the incomplete data [START_REF] Feder | Parameter estimation of superimposed signals using the em algorithm[END_REF], that is,

[ , ] T T T  C R I ( 27
)
where the so-called imputed data I are properly selected to simplify the ML estimation problem [START_REF] Moon | The expectation-maximization algorithm[END_REF]. In particular, when  consists of all transmitted channel symbols, I collects all the unwanted random parameters (fading, phase jitter, …) affecting the communication channel. These choices lead to hard detection algorithms often having an acceptable complexity and capable of incorporating the statistical properties of the channel parameters.

In the following, the complete data vector C will be always structured as in (27).

Given C, the auxiliary function :

    ( , ) ( ) , log ( ) ,

log ( ). ( , )

.

i EM c Q E L Ef f f d            I I S Rr C R r r,i i r i         ( 28
)
is evaluated, where

 .

E X denotes the statistical average with respect to a random vector X and S i is the space of I. The, this function is employed in the following two-step procedure generating successive approximations   () , 1, 2,...

k k   of ML  (1):
(1) Expectation step--( , )

EM Q   in (28) is evaluated for () k EM     (2) Maximization step--given () k EM  , the next estimate ( 1) k EM  
is computed as:

( 1) ( ) arg max ( , ), 0,1,...

kk EM EM EM Qk       (29)
An initial estimate (0) EM  of  must be provided for the algorithm start-up. In digital communication problems, proper initialization of the EM algorithm is usually accomplished exploiting the information provided by known symbol pilots [START_REF] Moon | The expectation-maximization algorithm[END_REF]. It can be proved that, under mild conditions, the sequence  

() k EM 
converges to the true ML estimate ML  of (1), provided that the existence of local maxima does not prevent it. Avoiding this requires an accurate initial estimation (0) EM  whose choice, for this reason, is of crucial importance [2].

The BEM algorithm : The unknown vector

  0 1 1 , ,..., T L    
mentioned in the previous paragraph can also be modeled as a random quantity, when its joint pdf f() is available. In this case the MAP estimate MAP  of  , given the observed data vector r, can be evaluated as:  . Solving (30) remains a formidable task for the same reasons previously illustrated for the ML problem (1). In principle, however, an improved estimate of  can be evaluated via the MAP approach since statistical information about channel uncertainty are exploited. Since there is a strong analogy between the ML problem (26) and the MAP one (30), it is not surprising that an expectation-maximization procedure, dubbed Bayesian EM (BEM) [START_REF] Chiavaccini | MAP symbol estimation in the presence of random parameters via a generalized EM algorithm[END_REF][START_REF] Gelman | Bayesian Data Analysis[END_REF], for solving the latter, is available. The BEM algorithm evolves through the same iterative procedure, as the EM, but with a different auxiliary function [START_REF] Chiavaccini | MAP symbol estimation in the presence of random parameters via a generalized EM algorithm[END_REF], namely:

arg max ( ) MAP r M      (30)
      ( , ) ( ) , log , , log ( , , ). ( )
. i BEM C c Q E M Ef f f d        S Rr C R r r i i r, i         (31)
A clear relationship can be established between the BEM And the EM algorithms. In fact, factoring the pdf ( , , ) f ri as:

( , , ) ( , ). ( )

f f f  r i r i    (32)
and substituting (32) into (31) produces ( , ) ( , ) ( )

BEM EM Q Q I        (33)
where ( ) log ( ) If   . Equation (33) shows that the difference between ( , )

BEM Q   (31) and
( , )

EM Q   (28
) is simply a bias term () I  favoring the most likely values of  . It is worth noting that, if a priori information about  were unavailable and, consequently, a uniform pdf was selected for () f  , the contribution from () I  would turn into a constant in (33), that is, it could be neglected. Therefore, the BEM encompasses the EM as a special case and, since the former benefits by the statistical information about  , it is expected to provide improved accuracy with respect to the latter. For the same reason, an increase in the speed of convergence and an improved robustness against the choice of the initial conditions could be offered by the BEM.

SISO Data detection in the presence of parametric uncertainty via the BEM Technique

In this section we show how the BEM technique can be employed to derive SISO algorithms for detecting digital signals transmitted over channels with parametric uncertainty and memory. A single-user transmission over a single input-single output channel is considered for simplicity, but the proposed approach can be extended to an arbitrary number of users and to MIMO system without any substantial conceptual problem.

Here, we assume that the kth component of the received data vector R can be expressed as:

( , )

k k k R g N  DA ( 34
)
where D = (,.,) k g expresses the known functional dependence of the channel on both the transmitted symbols and its parametric uncertainty. In particular, we focus on conditional finite memory channels, that is, on random channels such that: 12 ( , ) ( , , ,..., , )

c k k k k k k L g g D D D D     D A A ( 35
)
where L c denotes the channel memory. The goal is to devise a MAP SISO detection algorithm given the observed data R = r and a statistically known parameter vector A. In data detection problems involving the EM technique, two different choices have been usually suggested for the imputed data I and the parameter vector  :

(1) and = (2) and =  

I A D I D A   ( 36
)
It is extremely important to comment now on the meaning and the consequences of these choices. In the first case, both EM and BEM-based algorithms aim at producing hard estimates of the transmitted data. The only substantial difference between these two classes of strategies is that BEM allows to exploit the data statistics, that is, their APRP's, in the detection algorithm, since () I  in (33) turns into: . In other words, employing the EM (BEM) technique leads to hard-in (soft-in) hard-output detection algorithms. In the second case, both EM and BEM-based algorithms estimate the random parameters of the communication channel in a direct frashion. Nonetheless, they can be considered as SISO detectors since they generate soft estimates (i.e., the APPs) of the transmitted data as a byproduct of the estimation procedure and can also incorporate the data APRPs. BEM-based estimators, however, also make use of channel statistics, whereas EM-based estimators do not, that is, they operate in a blind fashion. Since blind detection techniques can be substantially outperformed by their counterparts exploiting channel statistics, this offers a strong motivation for preferring BEM-based strategies to EM-based ones when such statistical information are available. To further clarify these ideas, we derive now the BEM estimator of  , given  ID . the joint pdf ( , , ) f ri can be factored as:

( , , ) ( , , ) ( , ). ( ). ( ) f f f f f  r i r d a r d a d a  (38)
as the data D are independent of the channel parameters A. 41) into (31) and dropping the unrelevant terms produces, after some manipulations:

1 2 2 0 1 ( , ) Pr( , , ) ( , , ) log ( ) kk
N BEM k k k k k k kd N Q d r g d a f                 a a r a a ( 42
)
where  denotes the set of c L M possible channel state vectors. We define now the estimate vector

0 1 1 [ ] [ [ ], [ ],..., [ ]] T L k a k a k a k   a
generated, at the kth iteration, by the BEM estimation algorithm based on ( , ) BEM Q  aa (42). Such an algorithm operates as follows. First, ( , [ ])

Qk aa is evaluated (E step). The next estimate [START_REF] Moon | The expectation-maximization algorithm[END_REF] k  a corresponds to the maximum of ( , [ ]) Qk aa with respect to a. Then, taking the gradient of (42) with respect to a and setting it to zero produces the recursive relation.

 

1 * * * 2 [ 1] 0 [ 1] 1 Pr( , , [ ]) 2 Re ( ( , , ) ) ( , , ) 1 ( ) 0 (
) kk N k k k k k k k k k k kd N k d k g d r g d f f                     a aa a a a
r a a a a a (43) expressing a set of nonlinear equations for evaluating [ 1] k  a , given [] k a (M-step). It is worth noting that complexity of solving (43) depends on the type of functional dependence of (.) k g on a and on the inner structure of log f(a). We now explain why the estimator based on (43) can be also interpreted as a SISO algorithm. First of all, we note that the contribution from Pr( ) l d (coming from (39)), being independent of a, has been dropped in ( , ) (42). The contribution from the APRPs of the channel symbols, however, has not really disappeared since such probabilities are used in the evaluation of the APPs   ( , , kk Pd   ra . This means that, in its (k+1)th iteration, the BEMbased estimation algorithm requires the evaluation of the new APPs starting from the available APRPs and the last estimate [] k a of channel parameters. Generally speaking, on channels with memory, these APPs can be evaluated by means of a forward-backward recursive procedure operating on the trellis diagram of the channel states [START_REF] Kaleh | Joint parameter estimation and symbol detection for linear or nonlinear unknown channels[END_REF][START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate[END_REF][START_REF] Chang | On receiver structures for channels having memory[END_REF] ( ,, )

BEM Q  aa
kk k k k k kk kk f r f r P f f r                      aa ra r a a (44)
Following [START_REF] Kaleh | Joint parameter estimation and symbol detection for linear or nonlinear unknown channels[END_REF][START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate[END_REF][START_REF] Chang | On receiver structures for channels having memory[END_REF] it can be proved that

k k k k k k k k k k f r f r                 aa ( 45
)
where 1 , ,..., d ra can be delivered to soft decoding stages to improve the error performance of a digital receiver. Finally, we note that substantial simplifications of the BEM-based procedure based on (43) can be found when the communication channel does not have memory, that is, 1 c L  , since in this case the forward-backward procedure is no more required.

T l j j j l r r r     r , 1 0 ( ) ( , ) k k k k f       ra ,   1 1 1 1 1 ( , ) N k k k k f          
k k k k k k k k k k k k S fr                          a (46) 2 1 2 1 1 2 2 1 1 2 2 1 ( , ) ( ) ( ). ( , , ) Pr( ) k k k k k k k k k k k k S fr                                a where ( , ) ij S  is the subset of states i  such that the transition ij    is admissible. The initial conditions     0 0 0 0 Pr( );        and     1; N N N       need

Example of application: A BEM-based SISO algorithm for space-time block coded systems

Here we focus on a space-time block coded system employing N t transmit and N R receive antennas.The set of channel symbols transmitted during the nth block is denoted by the L  N

t matrix , [ ] [ [ ]] li n s n  S (with l = 1,2,…,L, i = 1,2,…,N T )
, where L is the overall duration of the block in channel symbols and , [] li sn is the channel symbol feeding the ith antenna in the symbol interval ( . ) l n L  . In the following we assume that the multiple channels involved in the communication system are (a) affected by frequency-flat Rayleigh fading and (b) quasi-static, that is, channel variations within each block are negligible, whereas changes from block to block are taken into account. Then the path gain , [] ij an (with i = 1,2,…,N T and j = 1,2,…,N R ) from the ith transmit to the jth receive antenna during the nth block is a complex Gaussian random process with zero mean and correlation function

  * ,, [ ] [ ]. [ ] a i j i j R m E a n m a n  (with [0] 1 a R  ).
Moreover, the gain processes  

, [] ij an are independent (rich scatterer environment). Let , [] lj rn denote the received signal sample taken at the output of the jth receive antenna in the (l + n.L)th symbol interval, with j = 1,…,N R and l = 1,…,L. A at the kth iteration, the next estimate ( 1) k A is evaluated as

  solving the resulting simplified equation that follows:

  a)-(7-b) of our iterative solution can also be derived by means of the EM algorithm[START_REF] Feder | Parameter estimation of superimposed signals using the em algorithm[END_REF][START_REF] Georghiades | Sequence estimation in the presence of random parameters via the EM algorithm[END_REF][START_REF] Xie | Two EM-type channel estimation algorithm for ofdm with transmitter diversity[END_REF]. Consider r as the "incomplete" observation and ( , )T T T  z r aas the "complete" observation. The EM algorithm states that the sequence () ˆn b defined by:

(



  a posteriori probability (APP) of the kth channel symbol k a conditioned on the observation r and on the estimate ( the M possible values taken in the constellation  . Equation (14) can then be rearranged as:

((

  symbol. They are a sort of "weighted average" over all the constellation points according to the respective symbol APPs. Note that thanks to (15-a) and (15-b), these a posteriori average values other words, due to the particular structure of the digital data-modulated signal, the implementation of the iterative ML estimation algorithm only requires the evaluation of the marginal a posteriori symbol probabilities (

  of random channel parameters independent of D and with known statistical properties,   k N is an AWGN sequence with variance 2 N  , and



  is the set of all the M N possible data sequences of length N, of the channel symbol vector d. If we define the channel state vector f r d a in (38) can be expressed as:

  kth sample r k depends on d through the couple   , kk d  only, and the random variables   k R , conditioned on D and A, are independent. Moreover, the conditional pdf ( , ) f  ir in (31) is given by: a is the probability of the event   l  dd, given  Rr and   Aa . Substituting (39) and (40) into (38) and substituting (38) and (

  indications illustrated in the previous application, we set  and   ,  C R S in applying the BEM technique. Then the auxiliary function is: , given R and   AA . Starting from (51), the following BEM-based recursive channel estimator can be derived. Given the channel estimate() k

  important to note that (a) P does not depend on the index of the receive antenna; (b) the inverse of P does not need to be recomputed as long as the channel statistics do not change; (c) (54) can be simplified factoring C A as: K iterations the BEM algorithm stops producing a channel estimate which can be processed exactly like in the previous application.

  and which can be derived as follows. To begin, we note that the couple ( , )

									kk d	uniquely identifies a
	transition	1 kk  ( , 	)	in the channel state, so that	( , k P d	k 	1   , ) ( , , ) k k P    r a r a . Applying
	the Bayes' rule to the evaluation of	( , kk P 	1 	, )  ra gives
				( , ,	11 )
				1
								1
								,	1

  Then the

										LN 	received
										R
	signal matrix	lj , ( ) [ [ ]] n r n  R	is given by:
										[ ] n R	[ ] [ ] n n  S A	W	[ ] n	(49)
	Here [] n  S	, where	 	 S m mM , 1,..., 		is an M-ary alphabet of unitary matrices
	() m S	H	S	m		T I , where I N	n is the n  n identity matrix. Moreover,	ij , [ ] [ [ ]] n a n  A	and
	W	lj , [ ] [ [ ]] n w n 	are the N	T  N	R fading matrix and the L  N R noise matrix, respectively. The
	lj elements , [] wn of W[n] are independent Gaussian random variables, all having zero mean
	and variance 2 w  	0 N 2.	.
	A set of N consecutive vectors (49) (with n = 0,…,N-1) can be grouped as
	[ [0], [1],..., [ H H H  N R R R R	1]] H	, with
										( ).  R D S A W	(50)
	where			[ [0], [1],..., [ H H H  N A A A A	1]] H	and	[	[0],	[1],...,	[	1]]


Measuring and Modeling Multipath TCP

Viet-Hoang Tran, Ramin Sadre, Olivier Bonaventure ICTEAM, Université catholique de Louvain, Louvain-la-Neuve, Belgium {tranviet,ramin.sadre,olivier.bonaventure}@uclouvain.be Abstract. Multipath TCP, a major extension to regular TCP, allows TCP clients to utilize multiple paths to improve the transfer rate and connection robustness. Providing these benefits without requiring to upgrade network infrastructure nor applications, Multipath TCP is becoming more popular. Notably Apple iOS 7 now supports it for SIRI. However, there is still lack of a complete understanding of Multipath TCP in practice. How much can a user benefit from Multipath TCP in different scenarios? Which factors affect the performance of Multipath TCP? How well can we predict the behavior of Multipath TCP in a specific environment? Our research aims to answer these questions by large-scale measurements and model-based analysis. The answers will be an important input for designers and developers to further improve Multipath TCP.

Keywords: multipath, MPTCP, traffic measurement, modeling

Background

To be able to use several network paths for a single connection is a long-desired feature, since it would bring several benefits including higher transfer rate and better robustness. However, this is not possible with TCP -the dominating reliable protocol in today's Internet. As an extension for TCP, Multipath TCP (MPTCP) is rapidly adopted by both academia and industry. At the time of writing, MPTCP implementations exist on several operating systems, including Linux [START_REF] Paasch | Multipath TCP implementation in the Linux kernel[END_REF], Apple iOS and MacOS [START_REF] Apple | iOS: Multipath TCP Support in iOS 7[END_REF], FreeBSD [START_REF] Williams | FreeBSD kernel patch for Multipath TCP[END_REF], Solaris [START_REF] Eardley | Survey of MPTCP Implementations[END_REF] and Citrix. A notable use case of MPTCP is to enable WiFi/3G offload on mobile devices [START_REF] Paasch | Exploring Mobile/WiFi Handover with Multipath TCP[END_REF][START_REF] Chen | A Measurement-based Study of Multipath TCP Performance over Wireless Networks[END_REF][START_REF] Deng | LTE, or Both?: Measuring Multi-Homed Wireless Internet Performance[END_REF]. On recent iPhones and iPads, Apple has deployed and enabled MPTCP by default for its voice recognition application (SIRI) [START_REF] Apple | iOS: Multipath TCP Support in iOS 7[END_REF] in order to reduce end-toend delays. It could also be used in datacenters to exploit multiple paths between hosts [START_REF] Raiciu | Improving Datacenter Performance and Robustness with Multipath TCP[END_REF]. Before MPTCP, Stream Control Transmission Protocol (SCTP) [START_REF] Stewart | Stream Control Transmission Protocol[END_REF] was designed with multi-homing in mind and supports concurrent multipath extensions [START_REF] Iyengar | Concurrent Multipath Transfer Using SCTP Multihoming over Independent End-to-end Paths[END_REF]. However, SCTP is still not widely used since it requires developers to change their applications and many networking devices like NATs/Firewalls do not understand SCTP and block its traffic. Instead, Multipath TCP was designed with backward-compatible goals in mind: it provides network applications the same API as regular TCP, for that TCP applications can use MPTCP without any modification. Behind the scene, it uses several subflows which appear to network infrastructure as separated regular TCP connections. Detailed explanations of MPTCP can be found in [START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF].

Motivation and Research Problems

Given the quick adoption and the potential applications of MPTCP, it is important to know how reliable MPTCP is and how much performance we can gain from using it in practice. A thorough understanding of MPTCP behavior and performance now becomes critical. We have identified three major questions that need to be answered: This can be split into more specific questions: whether MPTCP always behaves correctly, and how well the performance of MPTCP is. SCTP has been implemented in many operating systems, but its usage is very limited since it is incompatible with conventional TCP. Learned from the painfully slow adoption/deployment of SCTP, MPTCP was designed to work with conventional applications and network infrastructure. For example, MPTCP should fall back to regular TCP when proper operation over multiple paths is not possible. Until now, there is little knowledge about the correct behavior of MPTCP in such situations over the global Internet. In terms of performance, the fact that MPTCP uses several paths does not mean it will automatically gain the sum of goodput over all paths. Moreover, the perceived delay to the user is also important to investigate. 3. How to predict the behavior of MPTCP before deploying it in a specific environment? While MPTCP has potential to bring several benefits to a wide range of devices, network operators or service providers need to anticipate the benefits and the risks from deploying MPTCP on a large scale.

Generally, in order to answer the above questions, we can evaluate MPTCP through analysis, simulation, emulation [START_REF] Paasch | On the Benefits of Applying Experimental Design to Improve Multipath TCP[END_REF], or real-world measurement. There are several existing efforts. Passive measurement is done by collecting the available information from the network, for example in [START_REF] Hesmans | A First Look at Real Multipath TCP Traffic[END_REF], while active measurement is done by sending particular packets through networks and getting the necessary metrics [START_REF] Chen | A Measurement-based Study of Multipath TCP Performance over Wireless Networks[END_REF][START_REF] Deng | LTE, or Both?: Measuring Multi-Homed Wireless Internet Performance[END_REF]. There are also works toward modeling and analysis. For example, Arzani et al. [START_REF] Arzani | Deconstructing MPTCP Performance[END_REF] present a simple model for MPTCP behavior for a simple 2path topology. However, to predict MPTCP behavior in a real, heterogeneous environment is still a big challenge.

Research Directions

We plan to answer research questions 1 and 2 by performing measurements. A first step was done in [START_REF] Hesmans | A First Look at Real Multipath TCP Traffic[END_REF] where we collected and analyzed the MPTCP network traffic on a public Internet server for one week. This server hosts multipathtcp.org site to which everyone interested in MPTCP can access, download kernel and do testing with MPTCP enabled. In order to gain a more general insight into the usage and behavior of MPTCP in practice, we need to conduct measurements with the following considerations in mind:

1. Large-scale measurement: Previous works, which mostly focused on active measurement, only tested MPTCP with a few hosts. We envisage to perform active and passive measurements on a large number and wide variety of hosts. Our current measurement [START_REF] Hesmans | A First Look at Real Multipath TCP Traffic[END_REF] on multipath-tcp.org have users accessed from around the world, using a single or multiple network interfaces. Since the popularity of MPTCP is increasing, we have now for the first time the opportunity to observe MPTCP's behavior at large scale. 2. Dealing with a wide variety of MPTCP implementations: We want to develop techniques to identify the specific MPTCP implementation used by a host by passive measurements. This identification is an essential step in determining whether a particular observed behavior is due to the MPTCP protocol or due to a specific implementation.

3. Avoiding bias: Until recently, MPTCP was mainly used by people interested in this new technology. In order to avoid such kind of bias (and others, such as on the used operating system) in our measurements, we need to analyze passive measurement results to know more about the users of MPTCP.

To answer research question 3, we plan to build models of MPTCP behavior that can be applied to different network and host configurations. A first step could be to extend the work in [START_REF] Arzani | Deconstructing MPTCP Performance[END_REF] to more complex topologies and other schedulers. We expect that a general model will be hard to achieve. Instead, we will use the outcomes of our measurement activities to define and parametrize the most typical or interesting usage scenarios.

Conclusion

This paper presents the need for a thorough research of MPTCP behavior and usage in practice, and gives an overview on the challenges and directions of our research. We believe our work will bring a more comprehensive understanding of MPTCP protocol, implementations and traffic. This knowledge will be a valuable input for MPTCP designer to further improve the protocol. For the users, the work will give a more clear view on the benefit of using MPTCP and foster the widespread of MPTCP usage in practice.

Fig. 1 .

 1 Fig. 1. Our methodology

Acknowledgments. This work has been carried out in the context of the MET-RICS project -an Initial Training Network (ITN) which is supported by the European Commission.


Daniel Dönni

Sperb Guilherme

Christos Machado

Burkhard Tsiaras

Stiller

Schengen Routing: A Compliance Analysis

Keywords: Schengen Routing, Geo-location, Compliance checks 1

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

Introduction

The affair involving Edward Snowden and the National Security Agency (NSA) in 2013 demonstrated that wiretapping large amounts of Internet traffic data was not only possible, but also applied on a regular basis by various intelligence agencies in violation of privacy laws [START_REF] Landau | Making Sense from Snowden: What's Significant in the NSA Surveillance Revelations[END_REF]. However, the controversy only came into broader political debate by the time it was alleged that several European state heads had become victims of the wiretapping activities themselves [START_REF] Blau | NSA Surveillance Sparks Talk of National Internets[END_REF].

In the context of the political and technical debate that followed, the idea of Schengen Routing demonstrated to be a possible amendment to protect communications across Europe. The term Schengen refers to the treaty targeted at reducing border controls and implementing a harmonized legal framework [START_REF]The Schengen Area[END_REF]. Those countries, who signed the Schengen Treaty, form the Schengen Area. Table 1 shows the current Schengen members. It is important to highlight that the Schengen Area is not equivalent to the European Union (EU), since some countries belonging to the EU are not part of Schengen (e.g., United Kingdom), while Schengen also comprises non-EU countries (e.g., Switzerland).

Schengen Routing refers to the practice of routing Internet traffic between hosts located in the Schengen Area, not leaving the borders of countries part of the Schengen Treaty. Such Internet traffic not leaving the Schengen Area is more difficult to be wiretapped by non-Schengen intelligence agencies, since the Internet traffic remains still unencrypted. However, this traffic remains still vulnerable to wiretapping activities that may occur within Schengen [START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF].

An implementation of Schengen routing requires the reconfiguration of routing tables and the renegotiation of transit and peering agreements. The effort required depends significantly on the degree to which current routing already complies with Schengen routing or not. However, there is no previous work available, which measured a Schengen routing compliance through active measurements by analyzing TCP, ICMP, and UDP traffic. Thus, this paper answers the following question: What is the Schengen routing compliance or non-compliance percentage of current traffic among Schengen countries based on the observation of active measurements?

For that a large number of traceroute measurements was executed by applying RIPE Atlas [START_REF]RIPE ATLAS, atlas.ripe.net[END_REF] probes located in Autonomous Systems (AS) within Schengen to a well-known host in Switzerland, being part of the Schengen Area. ASes were chosen as the unit of analysis, because ASes are collections of network devices managed by a single administrative authority that can decide to cooperate with government agencies or not. IP addresses of nodes along a network path can be determined by using the traceroute tool. By means of a database, such as GeoLite [START_REF]Maxmind: GeoLite Legacy Downloadable Databases[END_REF], IP addresses obtained can be related to ASes and countries and, thus, placed in-or outside Schengen. Next to these measurements, a tool termed chkroute has been developed, allowing end-users to find out whether specific routes are Schengen-compliant.

This paper is structured as follows. Section 2 presents related work. The approach applied and evaluations performed are described in Sections 3 and 4, respectively. Section 5 presents the chkroute tool developed. Finally, Section 6 summarizes the work, draws conclusions, and outlines future steps.

The most detailed work analyzing routes leaving the Schengen Area was performed by [START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF]. Publically accessible BGP routing tables were obtained and, based on BGP routing entries, a graph of ASes was generated. Based on these graphs, traffic routes were established and analyzed to assess whether traffic between two peers within the Schengen Area would leave the area, thus, pointing on non-compliant Schengen Area routes. It was assumed that an AS belongs to a particular country, if the majority of its allocated Internet Protocol (IP) address space is bound to that country. Therefore, if an AS hosts IP addresses used in countries X, Y, and Z, but more than 50% is allocated to country X, the AS is considered to be located in country X. Such an assumption simplifies the full process of binding ASes to particular countries. However, it may present non-realistic results, since some ASes can present logical connections to several countries that not necessarily reflect the true country of origin of such an AS [START_REF] Zhang | Quantifying the Pitfalls of Traceroute in AS Connectivity Inference, 11th Passive and Active Measurement Conference[END_REF]. Those results show that, e.g., in Belgium, Switzerland, and Spain, more than one third of available routes are operating via ASes located outside the respective country. It is further found that the number of routes leaving the Schengen Area substantially varies among countries, e.g., 0% in Iceland and 35.38% in Belgium.

Another approach analyzed the content of BGP routing tables [START_REF] Hyun | Traceroute and BGP AS Path Incongruities[END_REF]. The respective outcomes are beneficial due to 3 reasons:

1. BGP looking glasses are servers running specific software designed to retrieve routing information. These servers are found in a considerable number of strategic ASes around the globe. 2. Evaluating BGP routing tables is a passive and, thus, less intrusive approach to form an AS graph. 3. BGP routing tables present a wider view of routing possibilities within each AS.

The major disadvantage of this approach is the lack of certainty that a packet will follow the inferred AS graph to a specific destination as the information may be incomplete or out of date. Therefore, active measurements involving tools such as, e.g., traceroute, are employed to discover Internet routes that are being used in practice for particular protocols and traffic [START_REF] Bourgeau | Monitoring Network Topology Dynamism of Large-scale Traceroute-based Measurements[END_REF]. Moreover, traceroute measurements are able to (1) reveal multiple routers within an AS and not only an AS-level graph representation, and (2) provide a real time result of the current network hops from source to destination. Thus, Paris traceroute [START_REF] Augustin | Avoiding Traceroute Anomalies with Paris Traceroute[END_REF] provides a more realistic routing map compared to the classic traceroute tool, solving problems caused by the current vast deployment of load balancers in the Internet. Paris traceroute addresses per-flow load balancers, varying header fields, such as the TCP/ICMP sequence number, the UDP checksum, and the ICMP identifier. The chkroute tool uses Paris traceroute to collect routing information (i.e., IP addresses of network hops) from the source to the destination, and uses the GeoLite database [START_REF]Maxmind: GeoLite Legacy Downloadable Databases[END_REF] to map IP address ranges to ASes. Table 2 summarizes major characteristics of chkroute and [START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF] to analyze Schengen Routing compliance. A major disadvantage of Schengen routing is that Internet traffic remains unencrypted. As a consequence, it is still vulnerable to wiretapping activities from within Schengen. A wide-spread use of end-to-end encryption would resolve this issue [START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF].

Approach

To measure Schengen routing compliance, a larger-scale measurement has been performed. RIPE Atlas [START_REF]RIPE ATLAS, atlas.ripe.net[END_REF] was chosen as a measurement platform due to its high AS coverage. ASes were selected for anlysis, because they appear as units controlled by a single administrative entity defining routing policies that has the capability to coopreate with intelligence agencies or not.

Test-bed Selection

To perform real-life measurements at a larger scale, a suitable test-bed is needed. Test-beds had to meet two requirements to be taken into consideration:

1. The test-bed had to be able to run traceroute measurements to retrieve IP addresses of nodes along a routing path. 2. The test-bed had to provide a high AS coverage in the Schengen Area.

Several test-beds could have been used to perform larger-scale measurements: Planet-Lab [15], EMANICSLab [8], Bismark [START_REF] Sundaresan | BISmark: A Testbed for Deploying Measurements and Applications in Broadband Access Networks[END_REF], and RIPE Atlas [START_REF]RIPE ATLAS, atlas.ripe.net[END_REF].

On one hand, Planet-Lab [15] and EMANICSLab [8] provide administrative access to the machines and, therefore, allow for full control over all aspects of the experiment. On the other hand, the number of ASes currently covered by these test-beds in Europe is lower when compared to RIPE Atlas: EMANICSLab provide nodes in 11 different ASes, while Planet-Lab provides nodes in 69 ASes. In contrast, RIPE Atlas provides 1306 ASes in the Schengen Area alone. Since Planet-Lab and EMANICSLab nodes are predominantly located in academic and research networks, such a distribution may not necessarily be representative for assessing Schengen routing compliance in the Schengen Internet as a whole [START_REF] Banerjee | The Interdomain Connectivity of PlanetLab Nodes, 5th Passive and Active Network Measurement Conference[END_REF].

The project Bismark [START_REF] Sundaresan | BISmark: A Testbed for Deploying Measurements and Applications in Broadband Access Networks[END_REF] allows researchers to perform measurements from home routers equipped with a modified openWRT firmware [14]. The project cannot be used to study Schengen compliance, since there are only 178 routers globally available, and even less within Schengen as of 2014 [START_REF] Sundaresan | BISmark: A Testbed for Deploying Measurements and Applications in Broadband Access Networks[END_REF].

RIPE Atlas is a measurement infrastructure initiated and coordinated by RIPE NCC [START_REF]RIPE ATLAS, atlas.ripe.net[END_REF]. According to RIPE's website, "RIPE NCC is building the largest measurement infrastructure ever made" [START_REF]RIPE ATLAS, atlas.ripe.net[END_REF]. The RIPE Atlas measurement infrastructure is based on a large number of low-cost measurement nodes given away for free to volunteers willing to host those probes in their private, institutional, or public networks. In exchange for hosting a probe, volunteers get access to measurement statistics and obtain credits that can be traded for running user-defined measurements on the infrastructure. The RIPE Atlas measurement infrastructure provides the best AS coverage by a substantial margin (1306 different ASes in Schengen alone) and was, therefore, chosen for the Schengen routing compliance analysis.

AS Selection

To determine to what extent traffic complies with Schengen Routing, a list of ASes in the Schengen Area had to be selected. Maxmind provides a free geolocation database named GeoLite [START_REF]Maxmind: GeoLite Legacy Downloadable Databases[END_REF], which maps IP address ranges to ASes and countries. The respective information is provided in two separate files. The first file contains IP address ranges in a long representation along with an AS number (e.g., 5 10 AS1). The second file contains IP address ranges in a long representation along with a country code (e.g., 5 10 CH). Based on this information, the number of IP addresses per AS and country was calculated (e.g., AS1 has 10 -5 + 1 = 6 IP addresses in CH (Switzerland)). These AS and country ranges did not always match and had to be divided into matching subranges in these cases. The logic for calculating the number of IP addresses per country remained the same. ASes were included in the measurement effort, if they had at least one IP address in a Schengen country. The resulting number of ASes in the Schengen Area was 9967 (cf. Table 3).

Measurement Execution

All traceroute measurements were executed using the RIPE Atlas measurement infrastructure. RIPE Atlas allows to specify an AS number as a measurement source and selects a suitable probe with an IP address within the AS automatically. The target IP address of all traceroute measurements was a machine located within Schengen at the premises of University of Zurich, Switzerland (within AS 559). Measurement requests were submitted for all 9967 ASes determined in Section 3.2 for the ICMP, TCP, and UDP protocol in turn. For each protocol, RIPE Atlas performed three traceroute measurements automatically. These measurements were limited to one target host and three traceroute measurements per protocol because the number of measurements that can be performed on RIPE Atlas is limited by the credit earned by the respective volunteer.

Results Processing

All results obtained from these measurements were processed in several steps (see Table 3).

1. Measurement requests were submitted for 9967 ASes, out of which 8661 ASes were not covered by RIPE Atlas. They could, therefore, not be taken into consideration. 2. RIPE Atlas could not find suitable probing devices in all ASes covered. These ASes could not be taken into consideration. 3. Some measurements failed or produced invalid results (e.g., error messages rather than measurement data) and were excluded.

ASes may have IP address ranges advertised in several countries, especially in

ASes with large number of IP address subnets. Because RIPE Atlas chooses IP addresses within the AS at its discrection, an IP address outside the Schengen Area may be selected. Measurements executed from probes having IP addresses located outside the Schengen Area were excluded.

After this results processing, 1132 TCP, 1131 UDP, and 1125 ICMP valid measurements remained for an evaluation. The unprocessed traceroute files obtained from RIPE Atlas measurements have been made publically available [START_REF] Dönni | Traceroute Measurements in Schengen Area[END_REF].

Evaluation

These results obtained were classified with respect to Schengen routing compliance as follows:

1. Measurements containing at least one IP address located outside the Schengen Area were classified as "Non-compliant" (NC). 2. Measurements containing only IP addresses inside the Schengen Area were classified as "Compliant" (C).

3. Measurements containing IP addresses for which no country information was available or for which traceroute did not produce an IP address were classified as "Unknown" (U), if all other IP addresses were located within Schengen and "Non-Compliant" otherwise

To determine the geographic location of an IP address, Maxmind's GeoLite database [START_REF]Maxmind: GeoLite Legacy Downloadable Databases[END_REF] was used, the same database as was used for the AS selection process described in Section 3.2. Figure 1 provides an overview of those results found. Light gray shades represent higher Schengen routing compliance levels while dark gray shades stand for lower compliance levels. 4. The "R" column ranks the Schengen countries -represented by their ISO code -according to the relative amount of compliant TCP routes. TCP was chosen for ranking, since it is the most frequently used transport protocol in the Internet as of today. The "ASes" column represents the number of ASes for which traceroute measurements have been performed. "T" represents the total number of measurements that were performed for the respective country and protocol. "C", "NC", and "U" show the amount of routes that were compliant, non-compliant, and unknown, respectively. For each of these categories the absolute and relative values are provided.

Results Analysis

This section discusses the results presented in Table 4, providing insight into compliant, non-compliant, and unknown routes. Overall compliance levels range from 34.5% in the TCP case, to 37.4% in the UDP, and 39.7% in the ICMP case. The variation among countries is substantial, though, it ranges from 0% (TCP), 0% (UDP) and 0% (ICMP) in the case of Malta (MT) to 80% (TCP), 75% (UDP), and 80% (ICMP) in the case of Liechtenstein (LI). These results show that no country is fully compliant with Schengen routing for those active measurement results.

Overall non-compliance levels range from 33.8% in the TCP case to 38.7% in the UDP and 42.3% in the ICMP case. As it happens for the compliance level, the variation among countries is considerable, it ranges from 0% (TCP) and 20% (ICMP) in the case of Liechtenstein (LI) and 19.4% (UDP) in the case of Switzerland (CH) to 81.8% (TCP), 81.8% (UDP), and 84.8% (ICMP) in the case of Estonia (EE).

The relative amount of unknown routes ranges from 31.7% in the TCP case to 23.9% in the UDP and 17.9% in the ICMP case. The variation among countries is less pronounced for unknown routes compared to compliant and non-compliant routes, in the TCP case results range from 18.2% in Estonia (EE) to 50% in Italy (IT), in the UDP case they range from 0% in Liechtenstein (LI) to 42.4% in Italy (IT), and in the ICMP case results range from 0% in Liechtenstein (LI) to 41.1% in Italy (IT).

The core finding is that compliance levels vary significantly among individual countries and range from a very low to a very high compliance. As a consequence, overall values are of limited use. The second finding is that there is no significant variation among transport protocols with respect to the relative amount of compliant, non-compliant, and unknown routes.

Comparative Analysis

While the work [START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF] used a passive approach based on publically available BGP routing table information, countries were ranked according to a Schengen routing compliance score, which represents the relative amount of routes that do not comply with Schengen routing [START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF]. Although the geo-location information is taken from Maxmind's GeoLite database [START_REF]Maxmind: GeoLite Legacy Downloadable Databases[END_REF] in both cases, the comparison of both sets of results obtained are compared and shown in Table 5. The relative amount of non-compliant routes obtained using active measurements in the chkroute approach exceeds in almost all cases the amount obtained using the model based on BGP routing table data. An analysis discussing the reasons resulting in those differences found between [START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF] and the chkroute approach is omitted at this point, because the routing data used to produce results in [START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF] is not available.

Design and Implementation of the chkroute Tool

While those results presented are useful to obtain a general understanding of compliance levels in each of the individual Schengen countries, end-users are more interested to learn whether specific routes are compliant with Schengen Routing or not. Therefore, chkroute was designed and prototyped. The tool chkroute assesses whether a specific route complies to Schengen Routing or not and is available at [START_REF] Dönni | chkroute utility[END_REF]. The tool's architecture consists out of the 3 components depicted in Figure 2. The client desires to verify a route. The target host or IP address represents the endpoint of the route. The geo-location server stores location and compliance information about IP addresses. The compliance checks for routes are performed in four steps.

1. The client runs traceroute to the target host. 2. The client collects responses from hops along the path. 3. The client submits hops to the geo-location server. 4. The geo-location server analyzes these hops and sends country and compliance information back to the client, which prints the result.

A sample run of chkroute is shown in Figure 3. The chkroute command is executed from a client at University of Zurich towards a server of the University of Federal Armed Forces in Munich. Both hosts are located in Schengen. The output produces a hop count, an IP address, the country code, Schengen routing compliance information (Yes ("Y"), No ("N"), and Unknown ("Unknown")), and the AS number. The sample output shows that this network traffic remains inside the Schengen Area until hop 7, leaves the Schengen Area for hops 8 to 11, and it returns at hop 12. Hop 13 is unknown. To ease the readability of this result, all hops are color-coded: green is for compliant, red for non-compliant, and yellow for unknown.

Summary, Conclusion, and Future Work

This paper presented key results of a larger-scale measurement conducted to determine the extent to which current routing is Schengen-compliant in Schengen countries. Based on 3388 TCP, UDP, and ICMP traceroute measurements run from RIPE Atlas probes located in over 1100 ASes in the Schengen Area it was found that compliance levels vary substantially among countries and range from 0% (TCP), 0% (UDP) and 0% (ICMP) in the case of Malta to 80% (TCP), 75% (UDP), and 80% (ICMP) in the case of Liechtenstein. The overall compliance levels range from 34.5% (TCP) to 37.4% (UDP) and 39.7% (ICMP).

Based on these measurements performed, this paper concludes that Schengen Routing compliance is not achieved in any of the Schengen countries, contradicting the claim that Schengen routing already was a factual reality today, as it has been stated by the Association of the German Internet Industry [START_REF]Computerwoche: Internet-Verband ECO Beklagt Scheindiskussion um "Schengen-Routing[END_REF]. Therefore, intelligence agencies still can perform potential wiretapping activities outside the Schengen jurisdiction on traffic originating within and destined to the Schengen Area.

This work and chkroute especially with the data set collected only analyze traffic in the forward direction. The reverse path may not necessarily be the same [START_REF] He | On Routing Asymmetry in the Internet[END_REF]. Hence, future work will address the reverse path, too. Furthermore, as only routes originating in Schengen countries targeted at a single node in Switzerland have been analyzed, results may differ, if a target node in another Fig. 3. chkroute output country was chosen. In particular, routes originating in a Schengen country A may be more or less likely than those originating in another Schengen country B to traverse a non-Schengen country depending on the location of the target node. Finally, an additional extension to this work is to analyze traffic for individual countries in more detail as well as to provide details with respect to countries that cause routes to be non-compliant with Schengen routing. It is also essential to identify those Schengen countries that are exit and entry points for traffic out of the Schengen Area and to examine the reason why this is the case.

Fig. 1 .

 1 Fig. 1. Schengen routing compliance levels

Fig. 2 .

 2 Fig. 2. The chkroute architecture

Table 1 .

 1 Schengen members as of January 2015

	Country Code	Country Name	Country Code	Country Name
	AT	Austria	IT	Italy
	BE	Belgium	LI	Liechtenstein
	CH	Switzerland	LT	Lithuania
	CZ	Czech Republic	LU	Luxemburg
	DE	Germany	LV	Latvia
	DK	Denmark	MT	Malta
	EE	Estonia	NL	Netherlands
	ES	Spain	NO	Norway
	FI	Finland	PL	Poland
	FR	France	PT	Portugal
	GR	Greece	SE	Sweden
	HU	Hungary	SI	Slovenia
	IS	Island	SK	Slovakia

Table 2 .

 2 Characteristics comparison of approaches analyzing Schengen Routing compliance

			Characteristics
	Approaches	Based on	Based on	Uses	Provide
		Active Mea-	Passive Mea-	GeoLite	Compliance
		surements	surements	Database	in Real Time
	[16]	no	yes	yes	no
	chkroute	no	yes	yes	yes

Table 3 .

 3 Number of ASes after results processing (T: TCP, U: UDP, I: ICMP)

	Original Not No Probes		Failed/Error	Outside Schengen Remaining
		Covered T	U	I	T	U	I	T	U	I	T	U	I
	9967	8661 44 47 50 25 24 25 105 104 106	1132 1131 1125

Table 4 .

 4 Schengen Routing compliance analysis

		C C (%) NC NC (%) U U (%)	78 33.3% 117 50.0% 39 16.7%	17 29.8% 33 57.9% 7 12.3%	12 30.8% 19 48.7% 8 20.5%	69 39.0% 69 39.0% 39 22.0%	45 21.7% 77 37.2% 85 41.1%	21 17.5% 62 51.7% 37 30.8%	12 16.7% 46 63.9% 14 19.4%	3 16.7% 9 50.0% 6 33.3%	3 7.7% 33 84.6% 3 7.7%	14 17.9% 58 74.4% 6 7.7%	16 12.7% 83 65.9% 27 21.4%	6 12.5% 39 81.3% 3 6.3%	3 7.7% 31 79.5% 5 12.8%	3 3.8% 51 65.4% 24 30.8%	0 0.0% 28 84.8% 5 15.2%	0 0.0% 5 55.6% 4 44.4%
	TCP UDP ICMP	R ISO ASes T C C (%) NC NC (%) U U (%) ASes T T C C (%) NC NC (%) U U (%) ASes	11 PL 78 234 81 34.6% 96 41.0% 57 24.4% 78 234 78 234 73 31.2% 108 46.2% 53 22.6%	12 LU 19 57 18 31.6% 27 47.4% 12 21.1% 19 57 19 57 15 26.3% 30 52.6% 12 21.1%	13 SK 13 39 12 30.8% 13 33.3% 14 35.9% 13 39 13 39 12 30.8% 16 41.0% 11 28.2%	14 SE 58 174 41 23.6% 53 30.5% 80 46.0% 59 177 58 174 72 41.4% 63 36.2% 39 22.4%	15 IT 70 210 39 18.6% 66 31.4% 105 50.0% 69 207 70 210 43 20.5% 78 37.1% 89 42.4%	16 NO 41 123 21 17.1% 51 41.5% 51 41.5% 40 120 41 123 17 13.8% 65 52.8% 41 33.3%	17 GR 24 72 12 16.7% 44 61.1% 16 22.2% 24 72 24 72 12 16.7% 40 55.6% 20 27.8%	IS 6 18 3 16.7% 7 38.9% 8 44.4% 6 18 6 18 3 16.7% 9 50.0% 6 33.3%	19 LV 13 39 6 15.4% 24 61.5% 9 23.1% 13 39 13 39 3 7.7% 29 74.4% 7 17.9%	20 BE 27 81 12 14.8% 40 49.4% 29 35.8% 26 78 27 81 9 11.1% 52 64.2% 20 24.7%	21 ES 43 129 12 9.3% 56 43.4% 61 47.3% 42 126 43 129 14 10.9% 73 56.6% 42 32.6%	22 SI 16 48 4 8.3% 28 58.3% 16 33.3% 48 16 15 45 6 13.3% 35 77.8% 4 8.9%	23 PT 13 39 2 5.1% 26 66.7% 11 28.2% 39 13 13 39 3 7.7% 28 71.8% 8 20.5%	24 FI 25 75 3 4.0% 42 56.0% 30 40.0% 78 26 26 78 3 3.8% 45 57.7% 30 38.5%	25 EE 11 33 0 0.0% 27 81.8% 6 18.2% 33 11 11 33 0 0.0% 27 81.8% 6 18.2%	MT 3 9 0 0.0% 6 66.7% 3 33.3% 9 3 3 9 0 0.0% 5 55.6% 4 44.4%	Total 1132 3396 1171 34.5% 1148 33.8% 1077 31.7% 1131 3393 1268 37.4% 1314 38.7% 811 23.9%

Table 5 .

 5 Non-compliant routes according to Pohlmann et al.[START_REF] Pohlmann | Secure Communications and Digital Sovereignty in Europe[END_REF] vs. chkroute

	Country Code Country	Pohlmann et al. [16]	chkroute
	BE	Belgium	35.38%	49.4%
	LI	Liechtenstein	29.41%	0.0%
	CH	Switzerland	23.48%	15.2%
	ES	Spain	21.27%	43.4%
	LU	Luxembourg	21.15%	47.4%
	FR	France	19.13%	26.4%
	MT	Malta	17.86%	66.7%
	FI	Finland	16.58%	56.0%
	CZ	CzechRepublic	16.31%	31.3%
	SE	Sweden	14.92%	30.5%
	NL	Netherlands	13.07%	19.3%
	DE	Germany	12.26%	32.5%
	NO	Norway	10.31%	41.5%
	GR	Greece	8.67%	61.1%
	EE	Estonia	6.78%	81.8%
	SK	Slovakia	6.25%	33.3%
	LT	Lithuania	5.50%	36.4%
	IT	Italy	3.70%	31.4%
	AT	Austria	3.23%	25.0%
	DK	Denmark	1.75%	26.3%
	PL	Poland	1.43%	41.0%
	PT	Portugal	1.39%	66.7%
	LV	Latvia	1.34%	61.5%
	SI	Slovenia	1.15%	58.3%
	HU	Hungary	0.49%	38.3%
	IS	Iceland	0.00%	38.9%

Acknowledgments

This work was partially supported 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.