Kent Inge

Fagerland Simonsen

Lars Michael Kristensen

Implementing the WebSocket Protocol based on Formal Modelling and Automated Code Generation

Model-based software engineering offers several attractive benefits for the implementation of protocols, including automated code generation for different platforms from design-level models. In earlier work, we have proposed a template-based approach using Coloured Petri Net formal models with pragmatic annotations for automated code generation of protocol software. The contribution of this paper is an application of the approach as implemented in the PetriCode tool to obtain protocol software implementing the IETF WebSocket protocol. This demonstrates the scalability of our approach to real protocols. Furthermore, we perform formal verification of the CPN model prior to code generation, and test the implementation for interoperability against the Autobahn WebSocket test-suite resulting in 97% and 99% success rate for the client and server implementation, respectively. The tests show that the cause of test failures were mostly due to local and trivial errors in newly written code-generation templates, and not related to the overall logical operation of the protocol as specified by the CPN model.

Introduction

The vast majority of software systems today can be characterised as concurrent and distributed systems as their operation inherently relies on protocols executed between independently scheduled software components and applications. The engineering of correct protocols can be a challenging task due to their complex behaviour which may result in subtle errors if not carefully designed. Furthermore, ensuring interoperability between independently made implementations is also challenging due to ambiguous protocol specifications. The use of formal modelling in combination with verification and model checking provides a prominent approach to the development of reliable protocol implementations.

Coloured Petri Nets (CPNs) [START_REF] Jensen | Coloured Petri Nets and CPN Tools for modelling and validation of concurrent systems[END_REF] is formal language combining Petri Nets with a programming language to obtain a modelling language that scales to large systems. In CPNs, Petri Nets provide the primitives for modelling concurrency and synchronisation while the Standard ML programming language provides the primitives for modelling data and data manipulation. CPNs have been successfully applied for the modelling and verification of many protocols, including Internet protocols such as the TCP, DCCP, and DYMO protocols [START_REF] Billington | A Coloured Petri Net Approach to Protocol Verification[END_REF][START_REF] Kristensen | Applications of Coloured Petri Nets for Functional Validation of Protocol Designs[END_REF]. Formal modelling and verification have been useful in gaining insight into the operation of the protocols considered and have resulted in improved protocol specifications. However, earlier work has not fully leveraged the investment in modelling by also taking the step to automated code generation as a way to obtain an implementation of the protocol under consideration.

In earlier work [START_REF] Simonsen | Generating Protocol Software from CPN Models Annotated with Pragmatics[END_REF], we have proposed the PetriCode approach and developed a supporting software tool [START_REF] Simonsen | PetriCode: A Tool for Template-based Code Generation from CPN Models[END_REF] for automatically generating protocol implementations based on CPN models. The basic idea of the approach is to enforce particular modelling patterns and annotate the CPN models with code generation pragmatics. The pragmatics are bound to code generation templates and used to direct the model-to-text transformation that generates the protocol implementation. As part of earlier work, we have demonstrated the use of the PetriCode approach on small protocols. In addition, we have shown that our approach supports code generation for multiple platforms, and that it leads to code that is readable and also upwards and downwards compatible with other software [START_REF] Simonsen | An Evaluation of Automated Code Generation with the Petri-Code Approach[END_REF].

The main contribution of this paper is to demonstrate that our approach and tool scale to support an industrial-sized protocol by automatically generating code for the WebSocket [START_REF] Fette | The websocket protocol[END_REF] protocol for the Groovy [START_REF] Groovy | Project Web Site[END_REF] platform. The WebSocket protocol is a relatively new protocol currently under development by the IETF. The WebSocket protocol makes it possible to upgrade an HTTP connection to an efficient message-based full-duplex connection. The WebSocket protocol address the performance problems of the HTTP protocol caused by the requestresponse interaction model and verbose headers. This is done by allowing HTTP to upgrade to a WebSocket connection in which a session is kept alive and messages may be transmitted in both directions freely with much lower overhead than with HTTP. WebSocket has already become a popular protocol for several web-based applications where bi-directional communication with low latency is needed such as games and media streaming services. The contributions of this paper include showing how we have been able to model the WebSocket protocol following the PetriCode modelling conventions, and to verify the model through state space exploration. Furthermore, we demonstrate in this paper that the generated code is interoperable with other WebSocket implementations, and we test the our implementation using the Autobahn WebSocket test-suite [START_REF]Autobahn-Testsuite[END_REF].

Outline. Section 2 presents the CPN model of the WebSocket protocol. In Sect. 3 we show how state space exploration was used to verify the operation of the model focusing on the proper establishment and termination of WebSocket connections. Section 4 describes the procedure to generate an implementation of the WebSocket protocol from the CPN model using the PetriCode tool. In Sect. 5, we present the results from testing the generated code by showing that it is interoperable with other WebSocket implementations and by employing the Autobahn WebSocket test-suite. Finally, in Sect. 6 we provide a discussion of related work, and sum up the conclusions and directions for future work. Due to space limitations, we refer to [START_REF] Jensen | Coloured Petri Nets and CPN Tools for modelling and validation of concurrent systems[END_REF] for a detailed introduction to CPN concepts.

The CPN model of the WebSocket protocol follows the structure imposed by our code generation approach, and consists of a set of modules hierarchically organised into three levels: the protocol systems level, the principal level, and the service level. In the following, we present representative parts of the CPN model which was constructed using CPN Tools [START_REF]Home Page[END_REF].

Figure 1 shows the top-level module of the CPN model constituting the protocol system level. The protocol system consists of a Client and a Server principal as modelled by the two accordingly named substitution transitions drawn as rectangles with a double-lined border. These two substitution transitions are annotated with the principal code generation pragmatic to denote that they represent protocol principals. The Channel substitution transition annotated with the channel pragmatic represents the channel connecting the two principals. The two substitution transitions are connected by places (drawn as ellipses) modelling send and receive buffers for the client and server. The rectangular tags attached to the substitution transitions specify the name of the submodule which refines the compound behaviour represented by the substitution transition.

The Client principal level module is depicted in Fig. 2. It is the submodule associated with the Client substitution transition in Fig. 1. The principal level makes explicit the services offered by the principal by means of the service and internal pragmatics attached to substitution transitions. The service pragmatic is used to denote substitution transitions where the attached submodule represents a service that is intended to be used by the application employing the protocol. Substitution transitions annotated with internal represent services that are used internally in the protocol principal. It can be seen that the client has six external and two internal services. A principal level module also models the internal state of the principal via places annotated with the state pragmatic, and captures the life-cycle of the principal via places annotated with the LCV pragmatic. The life-cycle determines the possible orders in which the services can be invoked. Initially, the only LCV -annotated place that contains a token is the READY place (top) which enables the OpenConnection service. After the OpenConnection service has completed, there will be a token on the OPEN place, and all the external services (except OpenConnection) will be enabled allowing the employing application to send and receive messages, send The MessageBroker module which is the submodule of the MessageBroker substitution transition is shown in Fig. 3. The MessageBroker is an example of an internal service. It is responsible for dispatching the incoming messages into the appropriate buffer represented in the module by places annotated with the state pragmatics. There is one such buffer for each of the message types: the inBuffer keeps text and binary messages, the pingpongBuffer keeps ping and pong messages, the closeBuffer keeps the closing messages while the fragments place keeps frames of messages that have not yet been completely received. The messages are dispatched by inspecting the type of the messages. The Message-Broker internal service is enabled when the WebSocket connection is in an OPEN state and the module captures the control flow in dispatching received messages as indicated by the places annotated with an Id pragmatic. The execution of the service starts at the transition ReceiveDataFrame. Then it enters a loop starting at place wait receive. At the transition receive a new frame is received. This is modelled as a single operation to keep the model at a high level of abstraction. This means that the details of actually receiving a message must be encoded in the code generation template associated with the receive pragmatic. If the frame is the last frame of a fragmented message, the entire message is reconstructed. Next, there is a branch in the model based on the Fin and Op-Code fields in the frame. The message is dispatched to either the inBuffer (data), PingPongBuffer, closeBuffer, or nonFinal. After the message or frame has been dispatched, the branches merge before the next iteration.

) > 0] [] [] [] frames1 frames2 frames3 1 1`() 1 1`[] 1 1`[] 1 1`[] 1 1`()
The getMessage service shown in Fig. 4 returns the next message in the buffer. This service will be used to illustrate code generation in Sect. 4. This is an example of a service with only a single transition. The transition is annotated with the service , getMessage and return pragmatics. This models that the service is first entered, then the getMessage operation is performed, and the service terminates. The transition getMessage is only enabled when there is at least one message in the message buffer as modelled by the place inBuffer.

1 1`[] 1 1`[] 1 1`() 1 1`[]
The complete CPN model consists of 19 modules. Each of the two principals have eight sub-modules which all correspond to the external and internal services in the protocol. In total, the model consists of 136 places and 84 transitions. This reflects the complexity of the protocol, but also the high-level nature of the model which has been important in keeping the number of elements manageable.

CPNs have a formal semantics which makes it possible to conduct model simulation and model checking (verification) prior to code generation. This is a major advantage of an approach based on a formal modelling language as this can be used to eliminate design errors prior to code generation and testing of the generated protocol implementation. CPN Tools used for construction of the WebSocket CPN model supports model checking of behavioural properties by means of state space exploration. The basic idea of state space exploration is to explore all the reachable states of the model to determine whether a model satisfies a given property or not. This means that state space exploration will exhaustively explore (test) all the possible executions of the CPN model. As the CPN model specifies the behaviour of both the client and the server, the state space exploration exercises the client against all the possible behaviours of the server and visa versa.

Our aim has been to apply state space exploration of the CPN model as a first test to eliminate possible errors in the logical specification of the WebSocket protocol. For this, we adopted a lightweight approach where we consider the following behavioural properties P0, P1 and P2 of the CPN model: P0 From the initial state it is possible to reach states in which the WebSocket connection has been opened (i.e., both the client and the server are in the open state). In the model this means that the places names OPEN in the Client and the Server modules each have one token and none of the other places other places modelling the life-cycle of the principals have a token.

It should be noted that we cannot establish that the WebSocket connection will eventually be opened since the server side may initiate a close before the client side is in the open state. P1 All terminal states (i.e., states without enabled transitions) correspond to states in which the WebSocket connection has been properly closed (i.e., both the client and the server are in the closed state). In the model this means that the places named CLOSED in the Client and Server modules each have one token and that none of the other places modelling the life-cycle of the principals have a token. P2 From any reachable state, it is always possible to reach a state in which the WebSocket connection has been properly closed. This means that independently of how messages are exchanged, it is always possible to properly close the WebSocket connection.

In order to check that in all terminal states both the client and the server are in the closed state, we wrote a simple query in the Standard ML language using functions that are built into CPN Tools. The query can be seen in Listing 1.1.

The functions server open and client open are predicates for the client and server that take a state as argument and return true if and only if the principal is in an open state, i.e., the place OPEN has one token, and all the other LCV places have no tokens. The functions server close and client close are similar for the case of closed. The predicates are used to obtain the predicates isProperOpen and isProperClosed that characterises properly open and closed states, respectively. The property P0 is checked using the query function PredAllNodes which returns all states satisfying a given predicate (in this case IsProperOpen). It is then checked whether the resulting list of states is non-empty. For establishing P1, we check that all terminal states in the state space which are returned by the built-in query function ListTerminalStates satisfies the IsProperClosed predicate. Finally, P2 is checked using the query function HomeSpace which checks if the list of nodes provided constitute a home space, i.e, constitute a set of states where at least one of the states can always be reached. Table 1 summarises the results from the verification. We have considered three possible configurations of the model. One where the client sends data to the server; one where the server sends data to the client; and one where both the client and the server sends data. The table lists the number of Nodes and Arcs in the state space, the amount of Time used to generate the state space, and the number of Terminal States. For all configurations, we were able to establish the properties P0, P1 and P2 which provides confidence in the correctness of the model. During the verification process, several minor modelling errors were identified and fixed. For example, this lead to the inclusion of the clearBuffers transition (see Fig. 2) which was added to properly clean up message buffers and reduce the number of terminal states.

The major drawback with state space exploration techniques is the state explosion problem which means that the state space in many cases grows too large to be handled with the available computing power. It is interesting to observe that the size of the state space for the model described in Sect. 2 is relatively small for the configurations considered. This shows how our modelling approach makes it possible to construct models at a high-level of abstraction so that it is feasible to fully verify even industrial-sized protocols.

Automated Code Generation

In this section we describe the code generation process for the WebSocket protocol targeting the Groovy platform and illustrate it with examples of code generation templates and code snippets. Groovy is also the implementation language of the PetriCode tool [START_REF] Simonsen | PetriCode: A Tool for Template-based Code Generation from CPN Models[END_REF] and has been chosen because it has several features that makes it easy to implement and debug templates including dynamic typing, closures and iterators.

The automatic code generation process, as implemented in the PetriCode tool, starts with a CPN model annotated with pragmatics. The model is first transformed into an intermediary representation in the form of an abstract template tree (ATT). The ATT reflects the hierarchical structure of the CPN model down to the service level. On the service level, the ATT contains blocks that are derived from the control flow path specified by the Id pragmatics of the service level modules. The next step in the code generation process is to traverse the ATT and emit code for each node by applying code generation templates bound to the pragmatics of a node. Pragmatics are bound to templates using template bindings which are defined in a domain specific language (DSL). When this is done, the code is stitched together using special markers in the generated code. The details are described in [START_REF] Simonsen | Generating Protocol Software from CPN Models Annotated with Pragmatics[END_REF][START_REF] Simonsen | PetriCode: A Tool for Template-based Code Generation from CPN Models[END_REF]. Our approach makes it possible to produce code for several platforms and programming languages. This is achieved by using different sets of code generating templates and binding them as appropriate to code generation pragmatics through the use of the DSL.

When the code generator, on its traversal through the ATT, encounters a node annotated with a principal pragmatic it executes the associated templates which, in the Groovy platform, defines a class. Then the traversal continues to the child nodes of the principal. When the generation traverses child nodes of a principal and encounters a node containing a service or internal pragmatic it executes the service template. The code generation for the principal is completed by replacing a special tag, %%yield%% with the result for the service template for all underlying services. The generated code of the client with declaration and method bodies omitted is shown in Listing 1.2. As can be seen when comparing with Fig 2, there is one method defined for each external and internal service. This comprises the API for the WebSocket client implementation with all the callable methods and their signature.

The template for the service pragmatic is shown in Listing 1.3. Lines 1-2 define a new method and its signature. The lines 3-12 set up preconditions (if Listing 1.2. The generated code for the services in the client. applicable) based on the manipulation of places at the service level that are annotated with the LCV pragmatic. The next two lines are place-holder tags that show where declarations and the method body will be inserted respectively. Finally, post-conditions are set and the method body ends in line 20. Listing 1.4 shows the template for the getMessage pragmatic used on the transition in Fig. 4. The template takes two parameters. The name of variable to set the next message to, and the name of the buffer to retrieve the next message from. First, the template checks to see if the buffer is not empty. If it is not empty, the first message is retrieved from the buffer. Then the payload is translated into a String or a byte array depending on the message type and the variable given in the first parameter to the pragmatic is set to the payload of the message. If the buffer is empty the variable given in the first parameter to the pragmatic is set to null.

The generated code for the getMessage service is shown in 1.5. Lines 1-4 and 21 are generated by the service template. The rest of the code, except from the return line, follows the template for getMessage where the first and second Listing 1.4. The template for the getMessage pragmatic. parameters have been replaced with inBuffer and message respectively since those are the two parameters given to the pragmatic in Fig. 4.

1 if(${params[1]} != null && ${params[1]}.size() > 0){ 2 ${params[0]} = ${params[1]}.remove(0) 3
In order to generate code for the WebSocket protocol, we reused 10 templates from the library of templates provided by PetriCode. In addition, 22 new templates were needed, including two templates that override existing templates. New templates were needed because the WebSocket protocol has many features we have not encountered with earlier examples, such as receiving and interpreting binary messages, and validating handshakes and frames.

Testing the Generated WebSocket Implementation

We validated the operation and interoperability of the generated code in two ways. First, we created test drivers for the generated WebSocket implementation to connect to the example chat server and client [START_REF] Gupta | Chat Sever using WebSocket in GlassFish 4[END_REF] that comes with the GlassFish Listing 1.6. The code for the client runner. Application Server [START_REF]GlassFish Application Server[END_REF]. Secondly, we submitted the generated implementation to the Autobahn Testsuite [START_REF]Autobahn-Testsuite[END_REF] version 0.5.51 .

Chat Application. The code for the chat client using the generated API (cf. Listing 1.2) is shown in Listing 1.6. The chat client uses the generated WebSocket protocol as an API given the signatures of the principal level. The client begins by creating a Client object from the generated code and opens a WebSocket connection to the server. Then, a thread is started to receive messages which polls the client object for new messages and prints any received messages to the console. After the message receiving thread is started, the client sends a message notifying the server that the client has joined the chat. Finally, the client enters an infinite loop that listens to the console for messages and sends any messages to the server. The server is implemented in a similar way using the generated Server class as the server-side WebSocket API.

Listing 1.6 demonstrates that our approach is upwards compatible, i.e., that the services of the generated code can easily be used by third party software. A key feature that provides this is that we include the API in the model as the services at the principal level of the CPN model.

Figure 5 shows the chat client (upper right) and server (lower right) running together with the web-based chat client from [START_REF] Gupta | Chat Sever using WebSocket in GlassFish 4[END_REF]. The web-based client has only been modified to connect to the server using the generated API by changing a hard-coded server address. We also tested that the chat client is able to connect and communicate with a chat-server from [START_REF] Gupta | Chat Sever using WebSocket in GlassFish 4[END_REF]. When running the Autobahn test-suite several problems with the implementation were discovered. Most of the problems were simple oversights in the code generation templates that were easily fixed once they were identified. An example of the trivial problems that were not evident when running the chat application was that the HTTP header lines were terminated with LF instead of the mandated CRLF. However, one change to the CPN model was necessary. This was related to fragmented messages where we added a buffer for temporarily storing frames of unfinished messages and a transition to distributing non-final frames. This was necessary because a WebSocket endpoint should be able to handle control messages intermingled with fragmented messages. The new elements, which can be seen in Fig. 3, are the place fragments, the transition nonFinal, and the arcs connected to those two elements.

A summary of the result for the final Autobahn tests can be seen in Table 2. The Autobahn test suite contains 301 tests cases for the client and server. For the client, 10 test cases fail and for the server, 4 test cases fail. The extra test cases that fail on the client concern performance with large messages. The test cases that fail for both the server and client are UTF-8 parser errors. This is because the Java implementation of UTF-8 parsers is more lenient than the Autobahn test-suite expects. Therefore, we had to create our UTF-8 validator which fails to identify some UTF-8 errors. In this paper we have shown that the PetriCode code generation approach can be applied to industrial sized protocols as exemplified by the WebSocket protocol.

Obtaining the implementation was achieved with limited effort even though quite a few new templates were created. We have found that the template provides an effective way to force the code to be modular. This means that the templates can be developed in a certain degree of isolation, giving the developer the opportunity to concentrate on getting a single template right at a time. Therefore, even though many templates are created for only a single protocol, this is an efficient way to prototype protocols based on a CPN model. Compared to previous examples, the WebSocket model had many more services. This makes the principal level somewhat harder to read and suggests that some kind of mechanism of grouping the services in several layers might be advantageous. At the service level, the models are approximately the same size as in previous examples. The readability of the service level modules can also be controlled by offloading behaviour to pragmatics such as we do for the receive pragmatic in the message broker. All in all, the WebSocket model shows that we can make code generation models for real protocols without necessarily losing descriptiveness.

We have also showed that the code generation model can be verified by state space exploration. This highlights a major advantage of using CPN models which are directly executable. This allows us to perform analysis on high-level models and thereby keep the state spaces small. Although the verification presented only considers basic connection establishment and termination properties, other more elaborate properties including liveness properties can be checked using similar techniques. We are also working on using the sweep-line method, and advanced state space exploration method, to alleviate the state space explosion problem. Finally, we have validated the automatically generated WebSocket implementation both by applying it to a well-known example in the form of the example chat application which is distributed with the GlassFish Application server and also by using the Autobahn test-suite which thoroughly tests most aspects of WebSocket protocol implementations.

To the best of our knowledge there does not exist any examples of using model-based techniques for generating an implementation of the WebSocket protocol in the literature. However, there exists a few examples for other industrial sized protocols. In [START_REF] Kristensen | Automatic Structure-Based Code Generation from Coloured Petri Nets: A Proof of Concept[END_REF] PP-CPNs, another class of Petri Nets, was used to generate code for the DYMO routing protocol for the Erlang platform. In our approach, we have a more flexible code generation approach through pragmatics that allows us to create new custom templates for new situations. Another approach to code generation is exemplified by the RENEW tool [START_REF] Kummer | An Extensible Editor and Simulation Engine for Petri Nets: Renew[END_REF]. RENEW uses a simulation based approach where the implementation is a simulation of the underlying Petri Net. The direct use of simulation code makes it harder to meaningfully inspect the generated programs.

Other formalisms such the Specification and Description Language (SDL) has also been used as a starting point for code generation. For example, an early warning system for earthquake was developed using SDL in combination with UML [START_REF] Fischer | Model-based Development of Self-organizing Earthquake Early Warning Systems[END_REF][START_REF] Brumbulli | SDL Code Generation for Network Simulators[END_REF]. Both simulation and prototype code were generated using C++ as the target language. Our approach differs from the above mentioned approaches by the flexibility in abstraction level because of our pragmatics, by being platform independent by simply substituting templates and by the fact that we model the API explicitly at the service level and thereby easy interoperability with third-party software. Our approach also allows us to model the service interface, which is not available to the same degree in PP-CPNs and Renew. Another approach to generating software for reactive systems from UML models is the SPACE method [START_REF] Alexander Kraemer | Compositional Service Engineering with Arctis[END_REF] and its tool Arctis. This approach employs collaborations to compose services. The collaborations are then transformed into state machines that are executed together with Java snippets which are bound to actions of the collaborations. This approach relies on the state machines to either be translated to code or executed directly by some other tool. This is in contrast to our approach where we generate code directly instead of going through other formalisms and tools. MACE [START_REF] Killian | Mace: language support for building distributed systems[END_REF] is a textual state-transition language that is used to create distributes systems. It uses a compiler to compile the textual statetransition language into C++ code. This means that MACE is not as platform independent as our template-based approach is. In MetaEdit+ [START_REF] Tolvanen | Metaedit+: domain-specific modeling for full code generation demonstrated[END_REF], models are mapped to some underlying formalism on which analysis is then performed. This tends to produce larger state space sizes compared with our approaches where the model is executable and allows verification at a high level of abstraction.

In the future we will apply more advanced state-space techniques, such as the sweep-line method, in order to do a more through verification of the model with larger and more complex configurations. Furthermore, we will investigate how errors in code generated by PetriCode can be traced back to the relevant pragmatics and model elements.

Fig. 2 .

 2 Fig. 2. The Client principal module

  : '(data data) (pingpong pingpong) (close close) (nonFinal nonFinal))>> <<callInternal(RecievePingPong)>> [IsPingFrame(frame) orelse IsPongFrame(frame)] close <<dist(closeBuffer)>> <<callInternal(ServerClose)>> [IsCloseFrame frame] iterate receive <<recieve(ch, message)>> <<mergeMessages(message, fragments,ClientClose)>> <<getOpCode(message, opCode)>> <<validateMsg(message, fragments,ClientClose)

Fig. 3 .

 3 Fig. 3. The MessageBroker internal service

Fig. 4 .

 4 Fig. 4. The getMessage service

Listing 1 . 1 .

 11 The queries used to verify properties P0-P2.fun client_open (n) = (State.Client'CLOSED 1 n) = [] andalso (State.Client'OPEN 1 n) = [()] andalso (State.Client'READY 1 n) = []; fun server_open (n) = (State.Server'CLOSED 1 n) = [] andalso (State.Server'OPEN 1 n) = [()] andalso (State.Server'Idle 1 n) = [] andalso (State.Server'READY 1 n) = []; fun client_closed (n) = (State.Client'CLOSED 1 n) = [()] andalso (State.Client'OPEN 1 n) = [] andalso (State.Client'READY 1 n) = []; fun server_pred (n) = (State.Server'CLOSED 1 n) = [()] andalso (State.Server'OPEN 1 n) = [] andalso (State.Server'Idle 1 n) = [] andalso (State.Server'READY 1 n) = []; fun IsProperOpen(n) = server_open(n) andalso client_open(n); fun IsProperClosed(n) = server_closed(n) andalsoclient_closed(n); PredAllNodes(IsProperOpen) <> [] ( * property P0 * ) List.all IsProperClosed (ListTerminalStates()); ( * property P1 * ) HomeSpace(ListTerminalStates()); ( * property P2 * )

  byte[] bArr = new byte[${params[0]}.payLoad.size()] 4 for(int i = 0; i < bArr.length; i++){ 5 bArr[i] = ${params[0]}.payLoad.get(i) 6 } 7 if(${params[0]}.opCode == 1){ 8 ${params[0]} = new String(bArr) 9 }else if(${params[0]}.opCode == 2) { 10 ${params[0]} = bArr 11 } 12 }else{ 13 ${params[0]} = null 14 } 15 %%VARS: ${params[0]}, ${params[1]}%% Listing 1.5. The generated code for the getMessage service in the client.

Fig. 5 .

 5 Fig. 5. Chat server and client using the generated API (right) and a web-based chat client connected to the same server (left)

Table 1 .

 1 Results of verification of the WebSocket CPN model

	Client Messages	Server messages	Nodes	Arcs Time (secs) Terminal states
	yes	no	2747	9,544	1	2
	no	yes	2867	9,956	2	2
	yes	yes	39189 177,238	246	4

Table 2 .

 2 Results for the Autobahn tests

	Tests	Server Passed Client Passed
	1. Framing (text and binary messages)	16/16	16/16
	2. Pings/Pongs	11/11	11/11
	3. Reserved bits	7/7	7/7
	4. Opcodes	10/10	10/10
	5. Fragmentation	20/20	20/20
	6. UTF-8 handling	137/141	137/141
	7. Close handling	38/38	38/38
	9. Limits/Performance	54/54	48/54
	10. Auto-Fragmentation	1/1	1/1
	6 Conclusions and Related Work

The test results can be seen at http://t.k1s.org/wsreport


Andreas Benzing

Boris Koldehofe

Kurt Rothermel

Bandwidth-Minimized Distribution of Measurements in Global Sensor Networks

Keywords: Data Streams, Global Sensor Networks, Optimization

Global sensor networks (GSN) allow applications to integrate huge amounts of data using real-time streams from virtually anywhere. Queries to a GSN offer many degrees of freedom, e.g. the resolution and the geographic origin of data, and scaling optimization of data streams to many applications is highly challenging. Existing solutions hence either limit the flexibility with additional constraints or ignore the characteristics of sensor streams where data points are produced synchronously. In this paper, we present a new approach to bandwidth-minimized distribution of real-time sensor streams in a GSN. Using a distributed index structure, we partition queries for bandwidth management and quickly identify overlapping queries. Based on this information, our relay strategy determines an optimized distribution structure which minimizes traffic while being adaptive to changing conditions. Simulations show that total traffic and user perceived delay can be reduced by more than 50%.

Introduction

The deployment of wired and wireless sensor networks is making rapid progress all around the globe. Sensors are installed in virtually all areas of everyday life and a huge amount of real-time data has become available. For example, the CeNSE project by HP [START_REF] Hartwell | Cense: A central nervous system for the earth[END_REF] envisions one trillion sensors to enervate the entire Earth. To globally enable scalable access to this data, broker networks providing high bandwidth data streams need to be established and managed using appropriate middleware solutions. Previous approaches focused on extending methods from local to global sensor networks [START_REF] Ahmad | Colr-tree: Communication-efficient spatio-temporal indexing for a sensor data web portal[END_REF][START_REF] Iwanicki | Using area hierarchy for multi-resolution storage and search in large wireless sensor networks[END_REF]. By utilizing in-network aggregation or lossy compression, a significant reduction of sensor data can be achieved. However, the gain of these methods comes at the cost of reduced precision to which many critical applications are highly sensitive. For example, the simulations for the dispersion of pollutants require precise wind data. Numerical errors due to compression artifacts can lead to highly disturbed results.

A promising alternative to reducing precision is to avoid sending information multiple times over a physical network link. The main problem then is to find an optimized and dynamically adapting dissemination structure for a large number of requests in the complex Internet. Group communication middleware such as application layer multicast [START_REF] Yeo | A survey of application level multicast techniques[END_REF] or publish/subscribe [START_REF] Eugster | The many faces of publish/subscribe[END_REF] tackle the complexity of the problem by reducing the number of requests which need to be served by a broker. In multicast, communication is limited to a fixed number of channels, prohibitively restricting the expressiveness of queries. Publish/subscribe offers high expressiveness for queries and scalability is achieved by merging similar subscriptions from different subscribers to avoid redundant transmissions. However, since the bandwidth requirements of an individual subscription are unknown, this solution misses optimization potential for high-bandwidth sensor streams.

Contrary, for global sensor streams, measurements are generated for every point at discrete time steps. Knowledge on the spatial and temporal resolutionas specified, for example, in scientific simulations -allows for exact determination of the data to expect from any given query. This poses a great so far unused potential to minimize bandwidth usage of a global sensing system.

Towards this end, we present the Global Sensor Grid Middleware (GSGM). The GSGM provides a new method to precisely query and scalably deliver realtime sensor data streams. The query interface allows for a flexible specification of geographic regions and resolutions of data of interest. Our main contribution is a new underlay-adaptive stream management algorithm to minimize traffic by exploiting the predictable network load of each query. Redundant parts of queries are quickly identified using a distributed index structure. Identical portions of data streams are merged and sent to dynamically established relay points where the data is distributed towards client nodes based on local knowledge.

The paper is structured as follows: Section 2 introduces the system model followed by a problem formalization in Section 3. The detailed description of our approach is provided in Section 4. Evaluation results are presented in Section 5. Related work is provided in Section 6 and Section 7 concludes the paper.

System Model

System Components The GSG is built up of brokers, which gather data from sensor networks, and clients. The sensor networks expose coordinates of their nodes and send raw sensor measurements to brokers where they are pre-processed and distributed to interested clients as shown in Figure 1. In doing so clients can pose a query to a broker, identifying the type of sensor, the spatial region, and spatial as well as temporal resolution. The brokers in turn identify the relevant data and establish a continuous sensor stream to the clients. In order to access the sensor data provided by a sensor network, we assume the sensor networks provide specific interfaces to the GSGM. These interfaces allow querying sensor data at varying temporal dimensions as well as coordinates in a global coordinate system. Note, however, that the GSGM is not concerned with managing the internals of the sensor network and how the sensor network is established.

To uniformly manage the sensors and sensor networks connected to the brokers, the GSGM manages a global coordinate system which comprises the world of all possible sensor coordinates. This world is partitioned into disjoint geographic regions, each managed by a single broker denoted the gateway of said region. This way each sensor is associated with exactly one region. However, a broker may serve as gateway for multiple regions. The gateways perform preprocessing of the raw sensor data to integrate sensor data into the global coordinate system and being able to offer sensor data at full resolution (cf. [START_REF] Balazinska | Data management in the worldwide sensor web[END_REF]). Additional brokers in the GSG support the distribution of sensor streams. We refer to brokers that forward sensor data on behalf of gateways as relays. Note that also gateways may serve as relays on behalf of other gateways. Gateways or relays, which send data to a client, form the end of a data stream inside the GSG and hence called target brokers of that client. The number of brokers as well as the assignment of gateways to regions is manually fixed by the operator of the Global Sensor Grid. This choice determines the number of queries as well as the performance characteristics that can be supported by the GSGM. However, the brokers will autonomously optimize the network resources used depending on the client requests for sensor data.

Query Model Building on our previous work [START_REF] Benzing | Efficient support for multi-resolution queries in global sensor networks[END_REF] we introduce the query model for the GSGM. A query to the GSGM is bound to one data type and includes the region of the data requested. Optionally, clients can specify the time of the beginning and duration of the data stream. Each query q is therefore given by a tuple q = (R q , t q , d q ) where R q specifies the geographical extent and resolution of the query. t q and d q denote the optional start time and duration of the query. If the latter two are not specified, the resulting data stream will start as soon as possible and run until the client fails or cancels the query.

Besides the geographical area of interest, the query region contains the requested resolution. This way, clients can directly query a grid of data points as required for the simulation at hand. The region of query q is represented by R q = (x min , x max , y min , y max , res x , res y , res t ), where x min and x max describe the lower and upper bound of the latitude. y min and y max limit the longitude correspondingly. Note that the system is not limited to geographic coordinates but can process any 2D coordinates. The last three values res x , res y , and res t specify the spatial and temporal resolution of the query as a fraction of the maximum available data. A value of res x = 0.3 therefore returns 3 out of 10 data points equally distributed over the corresponding axis. Similarly, only a subset of updates is transmitted for each data point if res y < 1 or res t < 1.

Cost Model The primary goal of the GSGM is to minimize the bandwidth used for distributing data. The bandwidth used by each data stream is proportional to the amount of data per update and the update frequency. On the one hand, the amount of data is given by the geographical extent of the area and the spatial resolution. On the other hand, the frequency depends on the temporal resolution. For a data stream serving a query q the corresponding total size |q| is therefore given by: |q| = (x max -x min ) × (y max -y min ) × res x × res y × res t While the size of a query determines the bandwidth required to send the data from a broker, the load on the network depends on how data is distributed in the network. To serve a query q, the corresponding data stream s q uses a set L sq of underlay links, which depends on the chosen path in the network. The number of underlay links for this path is consequently denoted by |L sq |. The overall cost c(s q ) can now be calculated as the product of the number of links and the bandwidth which is identical for each link: |L sq | × |q|. Note that the delay of a link is not taken into account as it does not affect the load.

Sensor Stream Distribution Problem

Recall that the bandwidth usage of the GSGM is driven by the overall number of underlay hops over which a given sensor datum is forwarded. To achieve minimal bandwidth usage it is therefore important to i) exploit the overlap between distinct sensor streams to reduce the amount of sensor data which is forwarded, ii) carefully choose the brokers which contribute in relaying to ensure short underlay paths. These goals conflict in general since longer underlay paths are required to share an underlay link between multiple streams.

We focus on two interconnected sub-problems to find a distribution structure with minimized bandwidth usage. The first sub-problem is to efficiently identify intersections between distinct queries. For each intersection, the data covered by the overlapping region must be sent to multiple clients. Solving the problem allows us to identify a set of k non-overlapping sensor streams from a single gateway to possibly multiple clients. The second task, and main problem addressed in this paper, is to reduce the bandwidth required for each stream by finding a minimal cost distribution graph. Clearly, both problems are in general hard to solve: First, the amount of possible intersections grows quickly with the number of queries in the system. Second, the path distribution problem can be reduced to the Minimal-Steiner-Tree-Problem (MST) [START_REF] Dreyfus | The steiner problem in graphs[END_REF] which is known to be NP-hard.

Proof. We can formulate this optimization problem similar to the MST w.r.t. each intersection. In the generic version of the problem, we are given a graph G = (V, E), one source node s ∈ V , and a set R ⊆ V of required nodes. The sought-after Steiner Tree is the graph which connects s to all nodes in R using nodes in V \ R as Steiner Points, i.e. relays, with minimal sum of edge weights.

To formulate our stream distribution problem for a single intersection, let V = {b i } i∈{1,...,n} be the set of brokers, b s be the source broker which provides the data, and R be the target brokers to which the clients are connected. Since a direct connection between any broker b i ∈ V can be established using IP-routing, The solution to this problem is the desired tree which provides the connectivity at minimal cost.

Even though multiple approaches to the MST exist, finding the exact solution to the presented problem is infeasible in a real-world GSG for multiple reasons. First of all, the MST is an NP-hard problem and has to be solved for a very large graph, i.e. the Internet with all its links. A restriction to all direct connections between brokers still involves a an extremely large graph. Second, a solution is needed for every intersection, resulting in numerous instances of the problem. Finally, the topology of the Internet is not known. This knowledge gap is broadened by the continuously changing network conditions caused by other applications using the Internet. In the remainder of this paper, we therefore present a new approach to solving the sensor stream distribution problem.

Sensor Stream Organization

In this section, we describe our new approach to approximate a solution to the sensor stream distribution problem and show how data streams in the GSG are organized to minimize bandwidth consumption. An example is given in Figure 2 The approach is divided into four main parts: query processing, management of network information, relay selection algorithm, and merging algorithm.

Query Processing

The query processing framework builds on our previous work [START_REF] Benzing | Efficient support for multi-resolution queries in global sensor networks[END_REF] and provides three functions: i) find the gateway for a given query, ii) identify the overlap of distinct queries, and iii) determine which queries to serve with incoming or locally generated data. We use the GBD-Tree [START_REF] Ohsawa | A new tree type data structure with homogeneous nodes suitable for a very large spatial database[END_REF] which is able to index very large, high dimensional spatial data sets. In our case, each broker maintains a GBD-tree to store queries according to their regions as well as gateways by the regions they serve. This way, a broker can determine which parts of a query can be served locally and where to forward other parts.

Each region in the GBD-Tree is labeled by a binary string called a DZ expression as illustrated in Figure 3. The DZ expression exposes two important properties: First, the shorter a DZ expression, the larger is the extent of the region. In particular, the empty DZ expression corresponds to the entire coordinate space of the GSGM. Second, if the DZ expression of region r is the prefix of another region r then r is fully contained in r. For example, regions 010 and 011 both reside completely inside region 01. The mapping of DZ expressions to a region can be efficiently achieved by means of recursive spatial decomposition. To determine the gateways for a query, the region of a query is converted to a set of DZ expressions according to the illustrated spatial decomposition scheme. As the tree is traversed top-down, the nodes will eventually contain information about the gateway on which the sensor data for the corresponding region is located. Similarly, for locally generated data or an incoming stream, the queries which are served by that stream can be found. By traversing the tree in a bottom-up fashion, we can aggregate information about overlapping queries as detailed in Section 2. Note that we only used two-dimensions in the example for clarity. The scheme supports various spatial and temporal dimensions. As queries are dynamically relayed to remote brokers, additional state is maintained by the GSGM. For each incoming relay stream, the path from the corresponding gateway to the local broker is stored in the index structure to prevent circular relaying. Each query is additionally annotated with the corresponding target broker to allow for efficient processing on the relay broker.

Neighborhood Maintenance Direct connections, i.e. IP routing without any relay points in between, provide fast routing of queries and low delay in responses. However, for increasing load, multiple streams might carry redundant data over the same underlay link. These similar data streams are therefore merged and only a single stream will be forwarded to a selected relay point. As described in Section 3, selecting a relay point requires information about the underlying network.

Each broker maintains a local view on the network, to infer the structure of the underlying topology. This view contains a limited number of topographically close brokers, called local neighborhood and additional information about each of these brokers. Initially, all the brokers from the information about the region assignment are added to the neighborhood. The neighborhood is then continuously updated with new candidates during query routing and neighborhood maintenance itself. When a broker learns about another, from the region assignment or through an update, the remote broker is added to the neighborhood and delay measurements to the new broker are initiated. The delay is used to estimate the topological distance to each of the remote brokers which a broker uses to decide which remote brokers to keep in the neighborhood. Close brokers are kept in the neighborhood while brokers with higher delay are removed from the neighborhood and measurements to them are stopped. However, to adapt to changing network conditions, the brokers which are currently not in the neighborhood are periodically measured. No additional topology information, e.g. data from network oracles, is used by the middleware.

To assess the network location of a remote broker, the local view contains additional information. After a broker is added to the local neighborhood, the neighborhood of that new broker is requested together with the respective measurements. This way, each broker can check the network from the point of view of any of the brokers in its neighborhood, resulting in a two-hop view. Brokers in the remote neighborhood that were previously unknown are considered for the local neighborhood as previously described.

Relay Selection In this section, we describe our approach to relay selection which serves as the basis for merging data streams. Relay selection is executed locally on each broker to determine where to send relay data streams and which clients to serve directly. In the following, we first introduce our notion of data stream similarity to provide an intuitive optimization goal. We then work towards our strategy for selecting relay candidates accordingly.

Basic Principles Merging overlapping data streams will only reduce the bandwidth consumption if they share at least part of an underlay path. Although the query index allows us to efficiently identify overlapping queries, we do not yet know whether the corresponding streams share any links in the underlay path. We approach this problem by introducing a similarity metric to provide an intuition about the problem at hand and a qualitative measure whether or not it is worth merging two streams.

For the GSGM, the similarity of two overlapping data streams is determined by the fraction of underlay links which they have in common in relation to the total path length. Formally, given two data streams s 1 and s 2 which carry the same data on paths p 1 and p 2 respectively, where |p i | denotes the length of path i and l i,j denotes the j th link on path i, the similarity is given by:

sim(p 1 , p 2 ) = l 1,k =l 2,l 2 (|p 1 | + |p 2 |)
If the paths are identical, |p 1 | = |p 2 | links will be summed up, resulting in a similarity of one. If the paths have no links in common, the similarity is zero.

Note that calculating the exact value of similarity requires knowledge of the entire underlay network. However, as described previously, the network graph is neither known, nor can it be measured exactly. Instead of first calculating the similarity, we therefore directly approach the relay selection problem in the GSGM. Relay selection is executed locally for each known target broker since their number is small compared to the large count of intersections. A solution to the problem ensures two properties: a) the network stretch is minimized, i.e. the path including the relay is as short as possible, while b) the probability of selecting the same relay for similar streams is maximized. The path segment from the originating broker to the selected relay can then be merged, i.e. served by a single stream, to reduce the load on the network.

Analysis of Simple Relay Strategies

The simplest relay strategy is to forward data streams directly to a client's target broker. We refer to this as direct relay strategy. Since the target broker is chosen by location close to the client in our setup, the introduction of the relay will result in a small network stretch. At the same time the strategy allows to remove all redundant transmissions with respect to clients which have overlapping queries and the same target broker.

Clearly, selecting additional relays between a gateway and the target brokers will increase the chance of multiple overlapping streams on the same relay link. At the same time, however, additional relays increase network stretch resulting in additionally used underlay links and higher overall bandwidth usage. In general, relying on the local neighborhood allows us to limit the stretch introduced by each additional relay. Furthermore, limiting the set of relay candidates increases the chance to find a common relay point for overlapping data streams. This basic reasoning results in a simple greedy strategy, closest to destination. To establish the relay path, the gateway will initially identify the relay which is topologically closest to the client. Each established relay broker, will then do the same until the target broker has been reached and the data is forwarded to the clients. While this greedy approach achieves low network stretch, its drawback is the large number of different relays chosen. As a result, the merging algorithm can only join streams which already have a very high similarity and the traffic reduction properties of this approach are sub-optimal.

To exploit lower similarity of data streams by having more relays, the closest to source strategy selects the relay based on the distance to the originating broker. First, the neighbors are sorted by increasing distance to the originating broker. Then, the first candidate which is closer to the target broker is chosen as relay. Note that this strategy is very fast, independent of the size of the neighborhood. As a result, the data streams are routed over a relatively large number of hops. While this provides the possibility to merge small common path segments, the network stretch grows very quickly. Combined Strategy for Minimized Usage We conclude the previous analysis with the relay selection strategy used in the GSGM. Rather than selecting a position relative to the source or target of a data stream, the relay is chosen closest to the path between the two. The pseudo code for the strategy is given in Algorithm 1. Before the relay selection is started, the brokers in the neighborhood are sorted with increasing distance to the source broker. For each candidate we first check whether it is closer to the target broker than the direct connection to avoid detours. Then we estimate the network stretch each suitable relay candidate. The broker with the least estimated distance to the direct path is kept as the result of the relay selection. If no suitable relay broker is found in the local neighborhood, the target broker is selected as relay.

We gain in two aspects towards our goal. First, the distance to the next relay is limited not only by the neighborhood but by selecting closer brokers with higher priority. This allows for an increased number of relays compared to the greedy closest to destination strategy. Since we ensure that relays are located in the direction to the respective targets, similar streams will be merged with high probability. Second, the network stretch is limited as the relay nodes lie close to the direct path towards the target brokers. By selecting the relays with possibly low network stretch, we limit the number of underlay links used in the path. Data is therefore delivered with low delay and bandwidth usage is reduced.

Merging Algorithm

The relay selection provides a relay for each target broker and therefore for each data stream. Based on the selection, each broker has to locally select which streams to merge towards each relay. The goal of the merging operation is to find possibly large intersections for relaying to merge as many streams as possible. A basic approach for this operation is to find large queries which carry a superset of data of smaller queries. The query index provides the foundation for quickly identifying this containment of distinct queries. Our novel merging algorithm furthermore exploits the structure to split queries in order to increase the overlap and therefore increase efficiency and flexibility. A parameter thereby limits extreme fragmentation to ensure a low overhead.

The selection and adaption of regions works in two main steps. First, additional information in the index is gathered. A query q is contained in the sub-tree marked by node n if the region assigned to n covers the region of q denoted by R q ≤ R n . In addition, we use the result of the relay selection to group queries by their relay candidate. For a target broker t q of query q the relay is given by relay(t q ) = r. The set of queries for a node n and relay r is now given by Q n,r = {q : R q ≤ R n ∧ relay(t q ) = r}. The total size of queries per node n and relay broker r can then be described by the total size of queries in Q n,r :

size(n, r) = q∈Qn,r |q|
Recall that the size of queries is proportional to the bandwidth required by them. By calculating size(n, r) for all nodes and relay candidates, we annotate the index with the size of queries per relay candidate in each node. Note that this operation can be computed very efficiently as query sizes can be aggregated by a bottom-up traversal of the index.

In the second step, the query index is traversed top-down for nodes containing at least one query by recursively calling mergeStreams as described in Algorithm 2. If a node contains more than one query which can be relayed by the same broker, a new relay is established, the corresponding region is added to R. All matching queries in the sub-tree, including any existing relay streams, are merged into that relay, i.e. added to the set Q of queries to forward. If there is only a single query for the currently considered relay and size(n, relay) > R n + ∆, the query is split and the two parts are added to the two corresponding child Algorithm 2: Stream Merging Algorithm nodes; the process then continues on each of the two child nodes. ∆ is a system parameter which controls how small queries are split to limit fragmentation.

To establish the relay data stream, all affected queries are forwarded to the relay. A copy of the queries is kept locally for future merging attempts. Once all queries have been sent to the relay broker, the source broker signals the relay broker the end of the relay step. The single data stream containing the requested region is then sent to the relay broker and the relay broker starts relaying queries.

Evaluation

The GSGM has been implemented using the OMNeT++ network simulator [START_REF] Varga | Omnet++[END_REF] with the inet framework for IP-traffic simulation. A realistic topology was generated using the tools of ReaSE [START_REF] Gamer | Realistic simulation environments for IP-based networks[END_REF]. The topology consists of seven autonomous systems, two of which are set up as transit domains. The AS themselves have a hierarchical structure, based on up to three core routers on the top level which are fully connected. The second level consists of up to three gateway routers per core which are connected to the edge routers on the third level. Client nodes are connected to the edge routers using asymmetric DSL. Brokers are placed depending on the scenario. The network setup included 577 clients and an average of 48 brokers where the brokers where directly connected to routers on different levels. Clients generated queries in uniformly distributed time intervals between 30s and 300s. Each query lasted between 60s and 250s. The total simulated time span was 20 minutes. The queried regions were distributed around a single point with exponentially decreasing probability of larger distance to simulate peak load on a region. Since the location of brokers in the networks is crucial for the performance of the overall system we varied the broker placement. For the core placement, Brokers are either placed in data centers at the core of the network and connected to gateway and core routers or placed at the edge to simulate sensor gateways executing the GSGM. The full placement comprises brokers distributed randomly among all routers. We measured the data transmitted by core and gateway routers only since the links to brokers are dedicated to the GSG and the links to clients cannot be optimized.

All evaluations include the native operation (OFF). As benchmark setups, we chose to add the simple strategies in Section 4, including DIRECT relay only, closest to destination (CTD), and closest to source (CTS). In the farthest from source (FFS) strategy a relay is selected farthest from the source broker. By prioritizing the distance to source, the strategies result in higher network stretch and therefore diversity in paths for load balancing. Our newly developed closest to path strategy is abbreviated CTP. The numbers attached to the label show the corresponding neighborhood size, where applicable. Overall, all relay selection strategies perform well considering the total traffic used by the system. Note that by selecting a relay closest to the path (CTP) and restricting the neighborhood, the data transmission is reduced most in all runs. The reduced bandwidth usage of our system has a positive effect on the quality of service. In a high bandwidth streaming system, the user perceived delay is significantly caused by queuing. By distributing fewer data on a single broker and leveraging more relay nodes, a larger neighborhood is beneficial for reducing the client perceived delay. However, the additional processing and propagation delay leads to increased client perceived delay for many overlay hops. For direct relaying, the many outgoing data streams on the gateway broker lead to increased queuing delay, while the prohibitively large network stretch of the farthest from source strategy increases propagation delay even for small neighborhood sizes. The trade-off can be seen in Figure 4 which also shows that closest to path (CTP) also performs best for this metric. To investigate capacity improvement, queries were added to the system for a single gateway broker distributed over five minutes. We measured the degradation in QoS over time to show the gain in overall scalability. As Figure 5 shows, the system is able to serve all queries with stream merging enabled whereas without the delay quickly becomes prohibitively high. Note that the size of client queries is limited in all cases by the bandwidth of links to the client to avoid any effects from queuing delay and packet drops on the last mile.

Related Work

From an architectural point of view, the GSGM is related to the OGC sensor web enablement (SWE) framework [START_REF] Reed | OGC R sensor web enablement: Overview and high level achhitecture[END_REF]. However, the main goal of the SWE is to contact single sensors rather than providing data streams for scientific simulations. While DataCutter [START_REF] Beynon | Distributed processing of very large datasets with datacutter[END_REF] provides an interface similar to the GSGM and extended filter functionality, it is not optimized for real-time data.

In the field of data reduction in networks, three categories have been addressed so far: The first category, application layer multicast [START_REF] Kurian | A survey on the design, applications, and enhancements of application-layer overlay networks[END_REF][START_REF] Yeo | A survey of application level multicast techniques[END_REF] has been proposed to handle redundant queries for identical data. These systems are tailored for channel-based communication, where a limited number of channels needs to be served to a high number of clients. Consequently, they rely on the expensive detailed generation of a distribution tree. However, the content of sensor data streams is determined by individual queries rather than channels. Although extensions have been proposed to map queries to channels [START_REF] Boukerche | Dynamic grid-based multicast group assignment in data distribution management[END_REF], the resulting false positives incur prohibitively high load on the network. Content-based pub/sub systems [START_REF] Eugster | The many faces of publish/subscribe[END_REF] as the second category aim to establish a containment relationship between the data sources and sinks, i.e. sensors and clients. They provide a flexible subscription interface which is capable of handling arbitrary queries. Pub/sub systems typically use clustering [START_REF] Tariq | Distributed spectral cluster management: a method for building dynamic publish/subscribe systems[END_REF] or merging [START_REF] Bianchi | Euro-Par '07, chap. Content-Based Publish/Subscribe Using Distributed R-Trees[END_REF][START_REF] Jayaram | Parametric subscriptions for content-based publish/subscribe networks[END_REF] of subscriptions to reduce the processing overhead at the cost of increased bandwidth usage. Recent approaches also consider the physical structure of the network [START_REF] Tariq | Efficient content-based routing with network topology inference[END_REF]. However, events occur rarely compared to sensor data which is sent out in high volume for all queried regions. Therefore, these approaches are not suitable to serve arbitrarily intersecting queries for sensor data and their resulting high bandwidth data streams. A third related category, stream processing systems [START_REF] Abadi | The design of the borealis stream processing engine[END_REF][START_REF] Gibbons | Irisnet: An architecture for a worldwide sensor web[END_REF][START_REF] Pietzuch | Network-aware operator placement for stream-processing systems[END_REF][START_REF] Rizou | Fulfilling end-to-end latency constraints in large-scale streaming environments[END_REF][START_REF] Srivastava | Operator placement for in-network stream query processing[END_REF], move processing tasks to optimize application performance and minimize network usage. Based on the underlying assumption that some of the processing tasks which can be moved reduce the bandwidth, these tasks are placed closer to the data sources. The remaining tasks are placed in a way to minimize the amount of data that is currently in transit on the network. However, the goal of these systems is to optimize latency in presence of complex interaction graphs rather than to minimize total bandwidth usage.

Conclusion

In this paper we presented our approach to minimize bandwidth usage for measurement distribution in a Global Sensor Grid. Using a distributed index, we partitioned queries for bandwidth management and could efficiently identify intersections between queries. Based on this knowledge, our relay strategy built an optimized distribution structure for data streams. Redundant streams are thereby joined by our new merging algorithm. The approach has been evaluated on an Internet like network topology. The results show that our optimized relay strategy yields at least 33% reduction in overall traffic. Furthermore, our approach can fully exploit brokers placed in the core of the network, achieving a total reduction of traffic of over 50%. The evaluations also show the positive effects on user perceived delay. In the future, we aim to combine the relay strategy with a clustering algorithm to better control the distribution structure.

Figure 1 .

 1 Figure 1. Naive operation of the GSG with a separate data stream per client.

Figure 2 .

 2 Figure2. Merged data streams using a relay broker in the network. A single data stream is sent over the relay to the target broker which then serves both clients.

Figure 3 .

 3 Figure 3. Example for DZ expressions generated by spatial indexing.

Figure 4 .

 4 Figure 4. Average user perceived delay for core placed brokers.

Figure 5 .

 5 Figure 5. Client perceived delay with increased load over time for core placed brokers.

  Data: n: Index Node, relay: Relay Broker Result: Q: Set of Queries to Forward, R: Set of Regions to Stream to Relay

	if getQueries(n, relay) == 0 ∧ size(n, relay) > 2∆ then
	for child ∈ getChildren(n) do
	mergeStreams(child, relay);
	end
	end
	if getQueries(n, relay) >= 2 then
	Q = Q ∪ getU nassigned(n, relay);
	R = R ∪ getRegion(n);
	else
	if size(n, relay) > Rn + ∆ then
	pushT oChildren(getQueries(n, relay));
	for child ∈ getChildren(n) do
	mergeStreams(child, relay);
	end
	end
	end

Acknowledgments The authors A.B. and K.R. would like to thank the German Research Foundation (DFG) for financial support of the project within the Cluster of Excellence in Simulation Technology (EXC 310/1) at the University of Stuttgart.


Alessio Mansutti
email: alessio.mansutti@gmail.com

Marino Miculan

Marco Peressotti
email: marco.peressotti@uniud.it

Multi-agent systems design and prototyping with bigraphical reactive systems

Several frameworks and methodologies have been proposed to ease the design of Multi Agent Systems (MAS), but the vast majority of them is tightly tied to specific implementation platforms. In this paper, we outline a methodology for MAS design and prototyping in the more abstract framework of Bigraphical Reactive Systems (BRS). In our approach, components and elements of the application domain are modelled as bigraphs, and their dynamics as graph rewriting rules. Desiderata can be encoded by means of type systems or logical formulae. Then, the BDI agents (i.e., their beliefs, desires and intentions) are identified and extracted from the BRS. This yield a prototype which can be run as distributed bigraphical system, evolving by means of distributed transactional rewritings triggered by cooperating agents depending on their internal intentions and beliefs. This methodology allows the designer to benefit from the results and tools from the theory of BRS, especially in the requirement analysis and validation phases. Among other results, we mention behavioural equivalences, temporal/spatial logics, visual tools for editing, for simulation and for model checking, etc. Moreover, bigraphs can be naturally composed, thus allowing for modular design of MAS.

1 Bigraphical reactive systems Bigraphical Reactive Systems (BRSs) [START_REF] Milner | The Space and Motion of Communicating Agents[END_REF] are a flexible and expressive metamodel for ubiquitous computation. System states are represented by bigraphs, which are compositional data structures describing at once both the locations and the logical connections of (possibly nested) components of a system (see Figure 1). Like graph rewriting, the dynamic behaviour of a system is defined by a set of (parametric) reaction rules, which can modify a bigraph by replacing a redex with a reactum, possibly changing agents' positions and connections.

BRSs have been successfully applied to the formalization of a broad variety of domain-specific calculi and models, from traditional programming languages to process calculi for concurrency and mobility, from context-aware systems to webservice orchestration languages; a non exhaustive list is [START_REF] Bacci | Bigraphical models for protein and membrane interactions[END_REF][START_REF] Birkedal | Bigraphical models of context-aware systems[END_REF][START_REF] Hildebrandt | Formalising business process execution with bigraphs and reactive xml[END_REF][START_REF] Zhang | A bigraphical model of WSBPEL[END_REF]. Very recently bigraphs have been used in structure-aware agent-based computing for modelling Work partially supported by MIUR PRIN project 2010LHT4KM, CINA. the structure of the (physical) world where the agents operates (e.g., drones, robots, etc.) [START_REF] Pereira | Bigactors-a model for structure-aware computation[END_REF]. Another inspiring recent development is a formal connection between ontologies and a particular class of BRS recovering inference and (nonmonotone) reasoning as graphs rewrites and reachability tests.

Beside their normative and expressive power, BRSs are appealing because they provide a range of interesting general results and tools, which can be readily instantiated with the specific model under scrutiny: simulation tools, systematic construction of compositional bisimulations [START_REF] Milner | The Space and Motion of Communicating Agents[END_REF], graphical editors [START_REF] Faithfull | Big Red: A development environment for bigraphs[END_REF], general model checkers [START_REF] Perrone | A model checker for bigraphs[END_REF], modular composition [START_REF] Perrone | Bigraphical refinement[END_REF], stochastic extensions [START_REF] Krivine | Stochastic bigraphs[END_REF], etc.

The key point of BRSs is that "the model should consist in some sort of reconfigurable space". Agents may interact in this space, even if they are spatially separated. This means that two agents may be adjacent in two ways: they may be at the same (abstract) place, or they may be connected by a link. This leads to the definition of bigraphs as an enriched hyper-graph combining two independent graphical structures over the same set of nodes: a hierarchy of places called place graph , and a hyper-graph of connections called link graph [START_REF] Milner | The Space and Motion of Communicating Agents[END_REF]Def. 2.3]. Each node in a bigraph is decorated with a type called control specifying additional properties such as the number of available link endpoints (ports). The set of available controls is called signature and is often denoted as Σ. We refer the reader to [START_REF] Milner | The Space and Motion of Communicating Agents[END_REF] for a precise and extensive presentation of BRS.

Figure 1 shows how a place graph and a link graph are merged yielding a bigraph. In particular, it portrays the state of a system composed by interconnected cars. These cars can move across an abstract topology described by a graph of locations; each location is presented as a (rectangle-shaped) node whose sub-nodes represent the cars at each location (car-shaped), the antenna coverage (triangle-shaped), and location interconnections (circle-shaped). Finally, a cross-shaped node is used to mark the destination of cars linked to it.

x y z t w

x y z t w R Fig. 2. Applying a parametric rewriting rule.

The dynamic behaviour of a system is described in terms of reactions of the form a a where a, a are bigraphs of the given BRS. Reactions are defined by parametric rewriting rules i.e. pairs of bigraphs (R L , R R ) equipped with a function from the sites (parameters) of R R to those of R L called instantiation rule. An example is provided in Figure 2 where the rewriting rule R (on the left) is applied to the bigraph in Figure 1 (yielding the bigraph on the right); the instantiation map is denoted by red arrows, keeping track of which nodes are created or deleted in the process (this extra information is functional to the results presented in this paper and is not required by the bigraphical framework).

BRS usually include a sorting discipline for ruling out spurious (i.e. non wellformed) states. In their general form, sortings are judgements over bigraph and reactions and can be used to model additional properties such as desiderata for the systems e.g. "a car reaches its destination" as will be discussed later.

From BRS to MAS

The first step for translating a specification given as a BRS (optionally enriched with properties and desiderata) to a MAS is to distinguish between subjects and objects in the domain model, i.e. which entities can perform actions and which cannot. This distinction is not necessarily unique and is intrinsically part of the specification; in fact, many approaches found in literature assume similar distinctions, although usually tailored to specific implementations (e.g. by means of specific classes in the ontology modelling the problem domain [START_REF] Bernon | A study of some multi-agent meta-models[END_REF][START_REF] Ribino | Ontology and goal model in designing BDI multi-agent systems[END_REF]).

Subjects and objects may be defined as specific configurations of portions of the bigraph, but a simpler characterization can be done in the signatures, i.e. by partitioning Σ into the set of subject (Σ s ) and the set of object (Σ o ) controls. This solution prevents ambiguities (e.g. arising from overlapping configurations) and simplifies the mapping between agents and their BRS specification. Controls can be either active or passive: reactions can take place only within an active context (i.e. a context obtained by nesting only active controls). A subject can be temporary inhibited by a passive context, like, for instance, a virtualized machine that is halted by its supervisor in response to some suspicious behaviour.

A bigraph in the BRS is a model of the global state of the system and hence it is natural to read nodes decorated with subject controls as BDI agents in the prototype MAS. Then, bigraphical reactions model agent reconfigurations where node creation/destruction translates in agent creation/termination accordingly to the instantiation map. An example of reconfiguration induced by a bigraphical rewrite is illustrated in Figure 3 where the signature Σ is defined as the union of Σ s = {2:0, :2} and Σ o = { :1}. Each bigraph is mapped into a family of agents hierarchically organised mirroring the place graph structure (which represents strong relations e.g. spatial or administrative ones); hence agents are aware of their parent and children along this hierarchy. Object nodes are collapsed in the internal state of the agent associated to their nearest ancestor. This mapping is consistent with the forest structure of place graphs, the idea that ancestors represent the environment and object the passive entities carrying data. From this perspective, circular nodes in Figure 3 can be read as sandboxes used by square agents to wrap and host foreign (triangular) ones.

The mapping induced by Σ s and Σ o defines a partition of the place graph assigning to each agent a portion of the global state. This portion corresponds to the public image of the agent's internal state (public state) and strong consistency is assumed only for this information (whereas other approaches assume a shared consistent state [START_REF] Pereira | Bigactors-a model for structure-aware computation[END_REF], as in the case of blackboard systems). A similar approach is adopted for the link graph however, hyper-edges are intrinsically "less-local" than place dependencies and it is very common for an hyper-edge to span over several nodes, e.g. in the case of a shared communication medium like a network. Therefore, assuming that agents sharing a hyper-edge are consistently aware of each other may be very demanding. To mitigate this shortcoming, consistency (and hence agent public states) is limited to the hyper-edge handles (i.e. the name associated to a hyper-edge). This solution can be read as if agents were linked only through some mediating proxy (middleware). However, the use of handles does not preclude the presence of (full) hyper-edges in agent beliefs since these are not required to be consistent (differently from public states). Links and handles are pictured in Figure 3 as green thick lines and diamonds.

Agent beliefs are the view that an agent has of the system i.e. a bigraph which is not guaranteed to be consistent with the global state. The only part of it that can be safely assumed to be consistent is the agent public state, i.e., the portion of the global bigraph mapped into the agent and its neighbouring agents. Note that a system-wide snapshot of public states always yields a consistent view of the global state represented by means of a bigraph (from the specification BRS). Inconsistencies may appear only between agents beliefs but are readily addressed by means of logical timestamps thanks to the mapping between BRS and MAS states. In practice, each agent will maintain an internal counter that is incremented at every update of its public state and attaches this value to its public state, hence effectively implementing logical timestampssince bigraphs are uniquely partitioned and assigned to agents by the aforemen-tioned mapping. This simple mechanism offers a way to locally resolve conflicts between cooperating agents and their beliefs. (Terminated agents are handled by death certificates as usual.)

A cornerstone in the theory of bigraphs is the concept of idempotent pushouts1 (IPO) [START_REF] Milner | The Space and Motion of Communicating Agents[END_REF]Def. 4.4]. IPOs characterize the minimal contexts enabling a given reaction. The advantages of IPOs for our purposes are twofold: first, these minimal contexts can be used as minimal hypothesis during planning tasks; secondly the bound on the context simplifies distributed rewritings. In fact, an agent interested in performing some action can check its beliefs or actual context against those obtained from the IPO construction and negotiate the rewrite with the agents involved. The operation can be refined by locks or push/pull notification with the agent neighbourhood. Moreover, IPOs guarantee that reconfiguration operations will involve only the minimal number of agents.

In general, reactions of BRS are non-deterministic, but can be easily restricted by suitable sortings (over states and executions), e.g. by requiring or forbidding specific occurrences [START_REF] Bacci | On the decidability of bigraphical sorting[END_REF], type systems [START_REF] Elsborg | Type systems for bigraphs[END_REF] and modal logics [START_REF] Conforti | Spatial logics for bigraphs[END_REF]. The same tools and techniques are used to decorate a BRS MAS specification with (global) properties and desiderata. The presence of deadlocks highlights conflicts between desires/goals and (non-confluent) non-determinism may be the symptom of an incomplete specification. However, in some cases, non-determinism may be desirable (e.g. to express events from outside the system) and therefore has to be supported by the model.

Structural properties and desiderata

In this Section we describe how properties and desiderata for a given BRS specification can be expressed by means of spatial and temporal logics. In particular, "spatiality" and "temporality" are used to characterize the states and transitions of the given BRS respectively. This is achieved by combining a temporal logic such as CTL (computational tree logic) on top of BiLog, a spatial logic for bigraphs [START_REF] Conforti | Spatial logics for bigraphs[END_REF]: BiLog formulae are seen as the atomic predicates of CTL. Although more complex combinations are possible (even spatial-temporal logics precisely designed for BRS), this rather simple stratification already yields a great expressive power. Moreover, this stratification allows us to readily adapt model checking algorithms for CTL by extending them with BiLog ones. In the following, we elaborate the BRS of "interconnected cars" introduced in the previous Sections and present how structural properties and desiderata are modelled in this spatial-temporal logic for bigraphs.

The first structural property we discuss requires that "cars always reach their destination". This requirement is captured by the formula:

AF[Car c,x | Target x ] (1)
where BiLog sub-formula enclosed by the square brackets is satisfied only by those states where the car node is next to the target it is connected with. The AF operator is the CTL "all-future" temporal operator and states that, for every path starting from the current state, the BiLog predicate eventually holds. For instance, (1) holds for the bigraph in Figure 1 but not for any state where the car is spatially disconnected from its target (hence (1) effectively rules out "bad initial states"). Likewise, we can model the requirement "cars are always connected to some antenna wherever there is one" as follows:

AG([(id 1,x | / y ) ⊗ Zone(Car y,x )] ∨ [Car a,x | Connection a,c ]) (2)
In other words, a car is disconnected only if it is in a zone covered by no antenna.

Predicates ( 1) and ( 2) can be thought as temporal-structural requirements about the system; on the other hand, we can use the same logic to express desires, e.g., the desire "there exists a route such that the car is never disconnected" (at least until the target is reached) is expressed by:

E([Car c,x | Connection a,c ] U [Car c,x | Target x ]) (3)
which combines [START_REF] Bacci | On the decidability of bigraphical sorting[END_REF] with a stronger version of (2). A predicate expressing a desire, like (3), may not be valid for a whole BRS, but this does not means that unsafe states are reached. In fact, agents will try to find suitable paths (i.e., by careful planning) accordingly to their desires and chosen goals.

Discussions and future work

In this paper we have outlined a methodology for modelling and simulating MAS as distributed BRS. The idea follows the direction of recent and interesting results where information is presented as suitable BRSs or used as a shared topological abstraction for agents [START_REF] Pereira | Bigactors-a model for structure-aware computation[END_REF]. Building upon the solid theory of bigraphs, this methodology offers a rapid prototyping tool aiding the designer in the requirement analysis and validation phases. Among the several theoretical results and practical tools offered by the BRS framework, we mention behavioural equivalences, temporal/spatial logics, visual tools for editing, for simulation and for model checking, etc. Moreover, bigraphs can be naturally composed, thus allowing for modular design of MAS. Overall, this methodology paves the way for cross-fertilizing transfer of results between MAS and BRS. The use of bigraphs is eased by the support to attached properties offered by recent tools like BigRED and LibBig2 . This feature allows bigraph components to be decorated with additional informations in the form of (typed) properties. In particular, LibBig supports property-aware matchings/rewritings, whose solutions are optimal w.r.t. property-based costs; this allows the designer to easily model and test in a declarative style cost-based policies (e.g. picking up the antennas with the strongest signal, or finding a shortest path).

The development of a distributed runtime for BRS is in its early stages and would surely benefit from tools and results developed for MAS. For instance, protocols and techniques like speculative reasoning [START_REF] Ma | Speculative abductive reasoning for hierarchical agent systems[END_REF] could be applied to compute distributed bigraphical reactions more efficiently and possibly ported to other bigraphical tools (in particular, model checkers).

We plan to investigate the connection between distributed matchings and the attribute-based agent-communication at the core of the language for autonomic systems SCEL [START_REF] De Nicola | A formal approach to autonomic systems programming: the SCEL language[END_REF]. In both cases interactions are based on the public state (the interface in SCEL lingo). Another topic to be investigated is the extraction of a MAS from an (enriched) BRS; this construction resembles bigraphical refinements [START_REF] Perrone | Bigraphical refinement[END_REF], suggesting the possibility to apply results from the field of (bigraphical) language engineering to the approach presented in this paper.

Fig. 1 .

 1 Fig. 1. Forming a bigraph from a place graph and a link graph.

Fig. 3 .

 3 Fig. 3. The MAS induced by a BRS over Σs = {2:0, :2} and Σo = { :1}.

IPO are connected to the concept of borrowed context extensively used in the theory of graph rewriting systems; actually both are instance of GRPO.

A Java library for extensible BRSs is available at http://mads.dimi.uniud.it/.