Ngoc Do

Cheng-Hsin Hsu

Nalini Venkatasubramanian

CrowdMAC: A Crowdsourcing System for Mobile Access

Keywords: Crowdsourcing, wireless networks, resource allocation optimization

Staggering growth levels in the number of mobile devices and amount of mobile Internet usage has caused network providers to move away from unlimited data plans to less flexible charging models. As a result, users are being required to pay more for short accesses or underutilize a longer-term data plan. In this paper, we propose CrowdMAC, a crowdsourcing approach in which mobile users create a marketplace for mobile Internet access. Mobile users with residue capacity in their data plans share their access with other nearby mobile users for a small fee. CrowdMAC is implemented as a middleware framework with incentivebased mechanisms for admission control, service selection, and mobility management. CrowdMAC is implemented and evaluated on a testbed of Android phones and in the well known Qualnet simulator. Our evaluation results show that CrowdMAC: (i) effectively exercises the trade-off between revenue and transfer delay, (ii) adequately satisfies user-specified (delay) quality levels, and (iii) properly adapts to device mobility and achieves performance very close to the ideal case (upper bound).

Introduction

Recent years have witnessed a dramatic increase in the number of mobile Internet users due to the tremendous popularity of smartphones and tablets; market forecasts point out that although only 13.3% worldwide cellular users have smartphones in 2011, the ratio is expected to reach 31.0% by 2016 [START_REF][END_REF]. In some regions, the number of smartphone users actually has exceeded that of feature phone users at the time of writing. For example, more than 46% of U.S. adults own smartphones in early 2012 [START_REF]46% of American adults are smartphone owners[END_REF], in Japan the smartphone penetration rate exceeds 95%. A key use of smartphones is to gain access to the Internet. Market reports place the number of mobile Internet users at 1.2 billion worldwide; the National Communications Commission of Taiwan reports that 68% of cellphone users opt for data plans [3]. The staggering number of data plan users forces cellular service providers to deploy costly infrastructure and purchase expensive spectrum, so as to maintain quality-of-service. The resultant traffic surge has also backfired at the mobile users, as the cellular service providers have moved away from unlimited data plans to tiered services [START_REF]Why Verizon dropped its unlimited data plan (and what you can do about it[END_REF], and may consider timedependent pricing [START_REF] Joe-Wong | Time-dependent broadband pricing: Feasibility and benefits[END_REF], which in turn may increase user's monthly bill.

Existing data plans often require 1-to 3-year contracts, and may not have too many options in terms of monthly traffic quotas. This results in low quota utilization, e.g., the worldwide average unused data quota is as high as 61% [START_REF][END_REF]. Studies indicate that 48.6% of AT&T data plan users incur very low monthly traffic (lower than the least expensive 300-MB data plan), and 81% of these users have a residue quota of more than 100 MBs every month [START_REF]Nearly half of AT&T subscribers would pay less by switching to a metered plan[END_REF]. The aforementioned statistics reveal that: (i) light mobile Internet users may find the contracts and relatively high data plan quotas less appealing, and (ii) other mobile Internet users may have residue data plan quotas. We argue that these two types of users could form a virtual community or marketplace, similar to My Virtual Neighbor [START_REF]My virtual neighbor[END_REF], and share the resources with each other.

In this paper, we present CrowdMAC, a crowdsourcing solution for providing on-demand mobile Internet access. Crowdsourcing refers to open platforms, that enable "loose sharing of resources between undefined publics" that may be human or online. Crowdsourcing platforms often incorporate human participation [START_REF] Franklin | CrowdDB: Answering queries with crowdsourcing[END_REF] allowing entities to outsource tasks to individuals and gain information from the collective processing. In CrowdMAC, mobile users in need of Internet access (or network connectivity in general) leverage the ability of other nearby users to provide access to the resource -i.e., mobile Internet. In particular, light mobile Internet users may completely avoid data plans, and hire other mobile Internet users with residue resources (e.g., data plan quotas, battery) to transfer data to/from the Internet for them. The hired mobile Internet users are referred to as mobile Access Points (mobile APs), and the hiring mobile Internet users are referred to as mobile devices throughout this paper. The mobile devices and mobile APs communicate with each other via short-range wireless networks, such as WiFi ad hoc, WiFi Direct [START_REF]Wi-Fi certified Wi-Fi Direct: Personal, portable Wi-Fi that goes with you anywhere[END_REF] and Bluetooth, and hence do not incur significant traffic overhead over the cellular networks. This kind of sharing is called tethering, and is widely used among mobile devices belonging to the same user. Some cellular service providers, including Verizon Wireless, Clearwire, and Sprint sell dedicated mobile gateways [START_REF] Yeh | Capacity and coverage enhancement in heterogeneous networks[END_REF], which essentially are mobile APs. Cooperative use of multiple access networks (Cellular, WiFi, Bluetooth, and etc.) is becoming increasingly feasible; enabling rich mobile applications using such hybrid access networks is a current topic of research [START_REF] Balasubramanian | Augmenting mobile 3G using WiFi[END_REF][START_REF] Bhatia | ICAM: Integrated cellular and ad hoc multicast[END_REF][START_REF] Do | Massive live video distribution over hybrid cellular and ad hoc networks[END_REF][START_REF] Han | Mobile data offloading through opportunistic communications and social participation[END_REF][START_REF] Keller | MicroCast: cooperative video streaming on smartphones[END_REF][START_REF] Luo | The design and evaluation of unified cellular and ad-hoc networks[END_REF].

Matching mobile devices with nearby mobile APs is not an easy task -the following challenges arise in creating a meaningful incentive-based design that ensures robust data transfer despite dynamics of mobile users and connectivities.

1. How does a mobile AP make an admit/reject decision upon receiving a request from a mobile device? Admitting a larger number of requests brings higher revenues, but causes buffer overflow and a longer end-to-end delay for file transfer. Higher delays may turn users away from the system. 2. How does a mobile device select a mobile AP and a corresponding service (Cellular or WiFi network)? Services charge different fees and provide different qualities of service. 3. How do mobile devices and mobile APs deal with uncertain channel conditions caused by mobility? The system has to solve the situation where a mobile device is moving out of its range before its file is completely transferred to the mobile AP. Similarly, a mobile AP's direct Internet access link may be disconnected due to mobility. 4. How does the system handle the associated security issues and legal implications of sharing mobile access? How does this scheme fit into the ISP/network provider ecosystem? In this paper, we focus on the mechanisms to enable crowdsourced mobile access to the Internet where mobile APs with direct access are able to offer connectivity to mobile devices without easy direct access (i.e., challenges 1, 2 and 3). In particular, CrowdMAC implements incentive-based mechanisms for admission control, service selection and mobility handling in a distributed middleware framework described in Section 2. The proposed mechanisms are implemented directly on off-the-shelf Android devices and require no changes to the underlying network boxes such as cellular base stations and WiFi Hotspots. Challenge 4 (i.e., security and integration with ISPs/providers) is a topic of future work; we discuss our views on this in Section 7.

CrowdMAC: Architecture and Approach

In this section, we describe the design principles and architecture of the Crowd-MAC crowdsourcing system that enables mobile devices to hire mobile APs to upload and download data.

Hardware and Network Architecture

Fig. 1 illustrates the hardware components in the proposed system architecture that include the following parties.

-Mobile Device: A device wishes to upload/download a file, but currently does not have a last connection to the Internet. -Mobile AP: A mobile AP is also a mobile device which possesses a last connection(s) to the Internet via cellular base stations or WiFi Hotspots. We assume that mobile APs possess data plans with network service providers, and are thus able to send/receive control messages to/from the Internet. In our proposed system, a mobile AP is willing to transfer data for a mobile device for fees. In Fig. Note that although C in Fig. 1 has a last connection, it may access the Internet through mobile AP D at times of poor connectivity. Nonetheless, we assume that a smartphone can be either a mobile device or a mobile AP, but not both simultaneously in this paper.

Software Architecture

CrowdMAC is envisioned as a distributed middleware system that resides on mobile devices, mobile APs, and the network proxy/broker. A mobile AP may provide concurrently multiple services, each for a last connection. Fig. 2 depicts the key software components/modules in CrowdMAC: (i) AAA Module, (ii) Control Plane Module, (iii) Data Plane Module, and (iv) Connection Manager. Fig. 2 also illustrates the operational workflow of a CrowdMAC session. Without loss of generality, we illustrate the system workflow using a data upload scenario, and minor modifications required for a download session. AAA Module: This module maintains information about users in the system and their mobile access sessions via databases at the proxy/broker. Mobile devices and mobile APs register themselves with the proxy/broker and provide identity information stored in database User. During operation, logs are maintained about the amount of data transferred by mobile APs for mobile devices and the corresponding monetary fees in database Billing. Our initial implementation uses a prepaid option. Mobile devices (i.e., users) make a monetary deposit to their account before they can use services provided by mobile APs. Prior to transferring data for a mobile device, the mobile AP accesses the proxy/broker to verify if the mobile device is able to cover the fees for the transfer.

Control Plane Module:

The control plane modules at different nodes cooperate to establish and maintain connectivity between a mobile device that requests access and the mobile APs that enable this access for a fee. When a mobile device wishes to use a service provided by a mobile AP, it first establishes a connection to the mobile AP through a discovery process in the Control Plane. Mobile devices and mobile APs discover one another as follows. When a user has a file to upload, the Control Plane at the mobile device executes a service scan by broadcasting a one-hop message with the size of the file. The Control Plane at the surrounding mobile APs respond to the scan message with the corresponding fees to transfer the file to the Internet. The price of each service is a function of the last connection cost and the local resource consumption dependent on the data amount transferred. It can be manually set by the mobile AP owner. Once the mobile device finds a list of services, it will select a service in the list and send a request containing its identity stored in its AAA to the corresponding mobile AP to use the service. If there is no service found, the mobile device will wait for some time before repeating the scan process. Upon receiving a request from the mobile device, the Control Plane communicates with the proxy/broker through the AAA component to authenticate the user. The identity information provided in the user request is used to verify the mobile device's balance at the billing server. If the balance cannot cover the fees, the request is rejected. Otherwise, the Control Plane goes further one more step. It makes a decision if it should admit or reject the request by running an admission control algorithm, MAPA, and then replies the decision to the requesting mobile device.

Data Plane Module: If the mobile device requesting service receives an admit response, its Control Plane triggers its Data Plane to start transferring data. Otherwise, it will remove the service out of the list, and choose another service to send the request. In the case of an admitted upload request, the mobile device reads the file and begins transmitting data packets to the Data Plane at the mobile AP. The Data Plane at the mobile AP maintains a FIFO Queue to buffer the receiving packets and transmits the buffered packets to the proxy/broker over its last connection. The proxy/broker then transmits the packets to the Internet. Once the whole file is successfully uploaded, the Data Plane at the mobile AP sends a confirmation back to the mobile device.

Connection Manager: This component manages network interfaces available on the device. It notifies the Control Plane and the Data Plane the availability of surround mobile devices and APs and the breakage of connections.

CrowdMAC Admission Control

We next present an admission control algorithm, called MAPA (Mobile AP Admission control) that allows a service to admit or reject requests from mobile devices based on the characteristics of the incoming requests, their potential to generate increased revenue for the service and the current set of ongoing commitments made by the service. Key design criteria of the admission control algorithm include: (a) maximizing long term revenue (measured as average revenue over time); (b) ensuring overall stability of the system (implying no buffer overflows at the service); and (c) providing a distributed and practical implementation.

We characterize the problem and develop an algorithm to enable admission control decision using a Lyapunov optimization framework. The Lyapunov approach is well suited to creating an operational framework for the mobile access crowdsourcing problem in this paper since it provides: (a) a meaningful theoretical underpinning for stability analysis of the dynamic execution environment and (b) the inherent queuing theoretic based modeling that is well suited to the network transmission problem. Using Lyapunov framework for designing admission control algorithms has been studied in [START_REF] Huang | The optimality of two prices: Maximizing revenue in a stochastic communication system[END_REF][START_REF] Lotfinezhad | Optimal control of constrained cognitive radio networks with dynamic population size[END_REF] for cellular base stations and WiFi Hotspots where resources are not an issue. Our problem considered here is much more challenging because mobile APs are resource constrained, and thus ensuring stability of CrowdMAC must consider this fact.

Basic Models and Problem Formulation

Consider a network consisting of a set of mobile APs M , a set of mobile devices D, and a set of wireless links L. Let us also assume that time is divided into slots of t units and requests are made by mobile devices to mobile APs for wireless services in a specific time slot. The following terminologies are used in developing the problem.

Services. Each mobile AP m provides a set of services S m -which in our case represents disparate last hop connections. Let S be a set of all services in the network. When mobile device d wishes to upload a file to the Internet, it selects a service s m provided by mobile AP m and waits for an accept or reject decision from s m .

Monetary costs. Mobile device d, who wishes to upload/download a file with size f d through a service, must pay a price or cost, which is a function of f d . In this paper, this is the revenue earned by the service and we consider this as monetary cost. If d selects service s m provided by mobile AP m, d will be charged a cost denoted by C(s m , f d ). Typically, C(s m , f d ) incorporates two subcosts: (a) a local resource consumption cost, C r (s m , f d ), that captures the cost incurred due to use of resources at m , and (b) a provider cost, C p (s m , f d ), paid by the mobile AP to the network provider (e.g., telco) for covering the data plan cost of s m 's last connection 4 . Hence,

C(s m , f d ) = C r (s m , f d ) + C p (s m , f d ).
The exact choice of the cost function is immaterial to our admission control technique. Our system works well with any non-decreasing concave function C(s m , f d ). For example, energy consumption, a dominating portion of the local resource cost for mobile devices, C r (s m , f d ), can be modeled as a non-decreasing concave function of the amount of transmitted data [START_REF] Balasubramanian | Energy consumption in mobile phones: A measurement study and implications for network applications[END_REF]. Similarly, a mobile AP m with a 200 MB, $10 data plan may employ a linear function such as

C p (s m , f d ) = 10f d
200 (1024) 2 to represent the provider cost. Workload arrival and departure. A mobile AP m may have many mobile devices requesting to use its services for file upload/download. We assume that each mobile device has only one file to upload/download at a time, and the maximum file size is F max . A mobile device approaches m when it wants to use m's services, and departs when it completes the transmission or moves out of m's range. Let R sm (t) denote the set of mobile devices requesting to use service s m provided by m in time slot t, and A sm (t) denote the total workload requested from service s m in time slot t. That is, A sm (t) = d∈Rs m (t) f d . Assume that A sm (t) ≤ A max ∀s m , t, where A max is the maximum possible workload at any mobile AP. We assume that mobile device arrival rate to m is i.i.d over time slot. Every time slot, s m admits a set of mobile devices r sm (t) ∈ R sm (t) with an admitted workload of a sm (t) ≤ A sm (t). The time average data amount admitted to s m is defined: āsm lim t→∞

1 t t-1 τ =0 E{a sm (τ )}.
If a mobile device moves out of m's range and has not completed transmission of the file, it finds another mobile AP to upload the remaining file. We let g sm (t) be the residual data that was not sent via s m due to disconnections between the mobile AP and mobile devices. Assume that g sm (t) ≤ g max ∀s m , t. The time average residual data not sent via s m is: ḡsm lim

t→∞ 1 t t-1 τ =0 E{g sm (τ )}.
Network capacity. For each link l in L, let µ l (t) and θ l (t) denote the amount of data transferred through link l and the maximum capacity of link l at time slot t. Thus, µ l (t) ≤ θ l (t). Value θ l (t) depends on channel quality while µ l (t) depends on the available data for transfer and θ l (t). We assume that channel quality is i.i.d over time slots. We denote θ max as the maximum channel capacity under any quality channel, i.e., θ l (t) ≤ θ max ∀l, t.

We denote µ out sm (t) as the amount of data transmitted out of service s m in time slot t. µ out sm (t) = µ l (t) if l is s m 's last connection for the upload case, or µ out sm (t) = d∈Γs m (t) µ m-d (t) for the download case where Γ sm (t) denote a set of mobile devices that s m is serving. The time average outgoing data amount from s m is defined as: μout

sm lim t→∞ 1 t t-1 τ =0 E{µ out sm (τ )}.
We define the total incoming data amount to s m at time slot t as µ in sm (t) = d∈Γs m (t) µ d-m (t) for the upload case, or µ in sm (t) = µ l (t) where l is the last connection for the download case. We denote ϑ max as the maximum incoming data amount to any service at any time slot, i.e., µ in sm (t) ≤ ϑ max ∀s m , t. The time average incoming data amount at s m is defined as: μin sm (t) lim

t→∞ 1 t t-1 τ =0 E{µ in sm (τ )}. Problem formulation.
Given a set of mobile devices R sm (t) arriving at service s m and requesting to use service s m with workload A sm (t), s m determines a set of mobile devices r sm (t) to be admitted for using the service such that:

max: Csm = lim t→∞ 1 t t-1 τ =0 d∈rs m (τ ) E{C(s m , f d )}; (1a) st: μin sm ≤ μout sm ; (1b) āsm ≤ ḡsm + μin sm . (1c)
Objective function (1a) indicates that s m attempts to maximize the time average revenue while maintaining its system's stability over time as shown in constraint (1b). Constraint (1c) is to ensure that admitted data will be transmitted to s m unless the mobile device leaves the range of the mobile AP.

Our Proposed Admission Control Algorithm -MAPA

To solve the problem (1a)-(1c), we design an admission control algorithm using the Lyapunov framework. To ensure the two constraints (1b) and (1c), we maintain a real queue and a virtual queue for each service s m in S presented below.

Real queue and the system stability -Constraint (1b): Data transmitted to/from mobile devices from/to s m is stored at a queue before it can be transmitted further. Each service has one real queue to store request data; let Q sm (t) denote the queue backlog, which is the number of bytes in that queue, at the beginning of time slot t for service s m . The queue backlog's evolution is expressed as:

Q sm (t + 1) max(Q sm (t) -µ out sm (t) + µ in sm (t), 0). ( 2
)
We define stability of our system as finite average queue backlog:

Qsm lim t→∞ sup 1 t t-1 τ =0 E{Q sm (τ )} < ∞. (3)
Notice that if (3) is maintained then constraint (1b) is satisfied. In real implementations, the real queue at mobile devices can be ignored, as a mobile device may read files on-demand rather than prefetching them into memory.

Virtual queue and the admitted data -Constraint (1c): To satisfy constraint (1c) without breaking the Lyapunov framework, we employ the concept of a virtual queue that captures the projected load over time based on requests admitted by the service. Each service s m maintains a virtual queue U sm (t) that is just a software counter, i.e. does not hold actual data packets. U sm (0) is set to 0 and U sm (t) evolves over time as follows:

U sm (t + 1) max(U sm (t) -g sm (t) -µ in sm (t) + a sm (t), 0). ( 4
)
Lemma 1 If the virtual queue is stable, i.e.,

Ūsm lim

t→∞

sup 1 t t-1 τ =0 E{U sm (τ )} < ∞. ( 5
)
then constraint (1c) is satisfied. 5We define a revenue weight V that works as a control parameter providing a trade-off between revenue and stability. By employing the Lyapunov framework with the real queue, the virtual queue, and parameter V , we translate the original problem (1a)-(1c) to another optimization problem that can be solved by 3 tasks presented in the following algorithm.

The MAPA algorithm, summarized in Algorithm 1, solves the problem in a distributed manner, and can be directly deployed on off-the-shelf devices without requiring modifications of the existing softwares at cellular base stations and WiFi Hotspots. It works as follows. Every time slot, every service s m performs three tasks: (1) determining which mobile devices requesting to use s m will be admitted; (2) determining if mobile devices that s m is serving should transmit data to s m 's real queue or not; and (3) transmitting data out of the real queue Q sm (t) whenever the queue is not empty.

To do task (1), service s m needs to solve the problem (6a)-(6b). It does that by going through every mobile device d in R sm (t), and calculates

e d = V C(s m , f d ) -U sm (t)f d . If e d ≥ 0, then d is admitted. Otherwise, d is rejected. Therefore, the procedure's complexity is O(n).
Service s m performs task (2) to control congestion. In the case of admitted upload requests, every time slot, if s m observes that the real queue backlog is larger than the virtual queue backlog, s m broadcasts a STOP message to Algorithm 1 Admission Control and Transmission Schedule request mobile devices not to transmit data in the current time slot. In the case of admitted download requests, the service generates threads to download data packets from the Internet and put the packets into the real queue. At the beginning of a time slot, if there is congestion at the real queue, the service stops the threads from downloading during the time slot.

Performance Analysis for the MAPA Algorithm

Let's denote C * sm as the maximum time average revenue of the problem (1a)-(1c) achieved by some stationary randomized algorithm. We first show that MAPA achieves a time average revenue C arbitrarily close to C * sm . Theorem 1 (Revenue lower bound) Our MAPA algorithm achieves a lower bound of the time average revenue:

Csm = lim T →∞ 1 T T -1 τ =0 d∈rs m (τ ) E{C(s m , f d )} ≥ C * sm - β V , where (7)
β = 1 2 [max(θ max , ϑ max ) 2 + max(g max + ϑ max , A max ) 2 ]. (8)
Next, we show there is a trade-off O(1/V, V) between the achieved revenue and the quality-of-services in the MAPA algorithm.

Theorem 2 (Worst case bounds on real and virtual queues) MAPA provides worst case bounds of the service's real and virtual queue size: The above two theorems illustrate the trade-off between the time average revenue and the worst case queue bounds. If service s m increases its time average revenue O(1/V), then the size of both real and virtual queues increases O(V). For example, when queue sizes reach infinity, s m achieves the time average revenue arbitrarily close to the optimal value. However, note that a large queue size may lead to high end-to-end delay. The following lemma shows that MAPA leads to a linear relationship between the end-to-end delay and the backlogs of the real and virtual queues.

U sm (t) ≤ V y * sm + A max = U * sm ; Q sm (t) ≤ V y * sm + A max + ϑ max = Q * sm , (9
Lemma 2 (Relating queue size and delay) Let's denote the current backlogs of the real and virtual queues as Q o sm and U o sm , respectively. Assume that the incoming and outgoing data rates µ in sm and µ out sm of service s m are unchanged over time slots. The MAPA algorithm achieves the worst case delay T to send all data in the real and virtual queues to the Internet:

T = t + T slots, where (10)
t = max(0, ⌈ Q o sm -U o sm µ out sm ⌉); Qo sm = max(0, Q o sm -tµ out sm ); (11)
T =          ⌈ Qo sm +U o sm µ out sm ⌉ if µ in sm ≥ µ out sm ; ⌈ Qo sm µ out sm + U o sm µ in sm ⌉ + 2 if 2µ in sm > µ out sm > µ in sm ; ⌈ U o sm µ in sm ⌉ if µ out sm ≥ Cµ in sm (C ≥ 2). (12)
Selection of parameter V : We have shown that V controls the trade-off between time average revenue and the delay. Two heuristics to select V are:

-Bounding memory consumption: Let M * be memory bound at a service. Per Theorem 2, we have Q * sm = V y * sm + A max + ϑ max ≤ M * , which enables us to pick a V value satisfying the memory bound.

-Delay quality: The delay quality is a quality-of-service metric for a service to deliver all data currently admitted in the virtual queue and buffered in the real queue to the Internet. Let T sm be the bounded delay quality, service s m wishes to offer. If T sm is small, the amount of data admitted and buffered is small. That leads to a short transfer delay to deliver data to the Internet and a low revenue for the service. According to Lemma 2, T sm is the upper bound of T . In the worst case, we have Q o sm = Q * sm and U o sm = U * sm . We set the minimum data rate incoming to s m to be µ in sm and the minimum outgoing data rate from the service to be µ out sm . Plugging Q * sm , U * sm , µ out sm and µ in sm into Lemma 2, we estimate V by ( 9) such that T is bounded by T sm .

Handling Mobile Device and Mobile AP Mobility

Due to mobility, connections between mobile devices and services as well as last connection may be lost. Fundamental to our approach is the ability to monitor the liveness of a link. For a service provided by the mobile AP, once it detects the disconnection, it removes the mobile device from the list of the devices it is serving, updates the virtual queue, and drops the mobile device's packets out of the real queue. For the mobile device, it stops using that service, and scans for another service. Advanced technologies such as WiFi Direct [START_REF]Wi-Fi certified Wi-Fi Direct: Personal, portable Wi-Fi that goes with you anywhere[END_REF] on Android OS 4.0.4 support APIs to detect the disconnection quickly. For other network technologies, we broadcast HELLO messages to detect the breakage. In addition to liveness monitoring, CrowdMAC incorporates the following techniques to support continuity of upload/download under mobility conditions. Technique 1 -File Segmentation for easy management and recovery: We divide each large file into smaller sized chunks and transmit each chunk independently. This is to reduce the transfer time and consequently enable successful delivery of chunks, despite connectivity changes. Once chunks have been sent, missing packets and chunks are retransmitted.

Technique 2 -Service Selection and Mobility Awareness: When multiple mobile APs are available, a mobile device can choose one from them using one of the following strategies:

1. Cost Based Service Selection: The mobile device simply chooses the service with the lowest cost. 2. Delay Quality Based Service Selection: The mobile device picks the service with the best delay quality (as defined in Section 3.3).

Mobility Based Service Selection:

The mobile device chooses a service based on reliability of the link from itself to the service. We assume that mobile devices and APs travel using a well known Random Waypoint model. Link reliability is determined by estimating link duration that indicates how long a link is likely to last. The mobile device picks the service with the longest link duration. The duration of link l denoted as δ l (t) can be estimated using existing efforts, such as Qin and Zimmermann [START_REF] Qin | Improving mobile ad-hoc streaming performance through adaptive layer selection with scalable video coding[END_REF] using an analytical model to estimate the link duration based on GPS readings. Technique 3 -Incentives to Constrain Mobility during file transfer: We employ charging schemes to motivate mobile devices and mobile APs to constrain mobility during file transfer. In file download scenarios, consider a situation in which a mobile device d requests to download a file f d . The file has been downloaded in the real queue, but just part of that has been sent to the mobile device because the mobile device moves out of the service's range. This is unfairness to the mobile AP because it had to pay for the Internet access cost C p (s m , f d ) to download the file. To address this issue, the mobile AP divides the file into multiple smaller chunks. Each time when the service starts downloading a chunk c d , the mobile device will be charged a fee C p (s m , c d ). Once the mobile device fully receives the whole chunk from the service, it pays the remaining fee C r (s m , c d ). If the service fails to download the chunk, it returns C p (s m , c d ) to the mobile device. Note that if the service does not receive a confirmation of receiving a chunk from the mobile device, it will not download the next chunk. With this mechanism, both sides, the mobile device and the service, have motivation to maintain the link stability until the whole chunk is successfully downloaded. In file upload scenarios, incentive provision is simpler. Fees are charged on what the service uploads through the broker/proxy. While the mobile device is motivated to keep the link stable to complete the transfer, the mobile AP is incentivized to keep the last connection stable to earn the revenue.

Testbed Implementation: A Proof-of-Concept

Our Testbed and Settings. We implement our middleware on an Android based testbed which consists of a Linux server and multiple Android smartphones located in the University of California, Irvine. An interesting thing is our implementation does not depend on synchronized timers among mobile devices and mobile APs. The admission control procedure in Algorithm 1 runs once for each request, rather than in every single time slot. That is, whenever a mobile device has a file to transfer, it sends a request to a mobile AP. That mobile AP then invokes the MAPA algorithm right away, and immediately sends back the accept/reject decision. Also, the transmission scheduling procedure in Algorithm 1 keeps track of the backlogs of virtual and real queues on mobile APs. Once a mobile AP sends a STOP message, the corresponding mobile device stops transmitting data to that mobile AP. Since MAPA does not require synchronized timers, it can be readily implemented in the CrowdMAC system. We deploy our system on multiple types of Android phones: a Samsung Galaxy SII as a mobile AP connecting to the T-Mobile network, and four mobile devices including Google Nexus, Nexus S, HTC Nexus One and Motorola Atrix. The phones run Android OS versions from 2.3.6 to 4.0.4. They are placed in a labroom with no mobility and connect to each other over a WiFi peer-to-peer network using WiFi Tether [START_REF]Android WiFi tether[END_REF]. The mobile AP is equipped with a data plan of $30 for 5 GB, and it charges $5 per GB for local resource consumption. The T-Mobile network is measured to have bandwidth between 311 and 748 Kbps throughout our experiments. In each experiment, each mobile device uploads 50 equal-sized files. For each file, a mobile device sends a request to the mobile AP and waits for its decision. If the request is rejected, the mobile device waits for 2 secs before it resends the request. The mobile device skips the current file if the its request is rejected for 5 times. Fig. 3 presents our system's GUI and the phones in an experiment.

Experimental Results. We consider two metrics (i) Revenue, which is the total revenue generated by the service in each experiment, and (ii) Transfer delay, which is the average per-file transfer time, from the instant a request is admitted to the instant when the last packet is transferred.

Reliable transfer. We repeat the experiments with various parameter V ∈ [0, 1500], and we consider two file sizes: 512 KB and 1 MB. Across all experiments, we find that all the admitted requests lead to successful file uploads. This confirms that the proposed CrowdMAC system and MAPA algorithm do work.

Trade-off between revenue and transfer delay. Fig. 4 presents the revenue and transfer delay under different V . This figure shows that smaller V leads to fewer admitted requests, and thus lower revenue. Furthermore, fewer admitted requests means lighter-loaded networks, and thus shorter transfer delay. For example, with V = 10, the mobile AP only admits half of the 512 KB files at the end; while with V = 1000, the mobile AP admits all the requests. Fig. 4 shows the effectiveness of V : the MAPA algorithm supports wide ranges of revenues and transfer delays.

User-specified delay quality level. We next evaluate the V selection heuristic proposed in Sec. 3.3. We consider the heuristic that maps a delay quality level, between 45 and 135, to a suitable V value. Fig. 5 presents the revenue and transfer delay achieved by various delay quality levels. We make two observations. First, higher delay quality level leads to more admitted requests, which in turn results in high revenue and transfer delay. Second, Fig. 5(b) reveals that the average transfer delay is always smaller than the delay quality level specified by the user throughout our experiments.

Simulation Based Evaluation

Settings

We implement our middleware system in Qualnet 5.02 [START_REF]Qualnet network simulator[END_REF]. In simulations, we use WiMAX to simulate last connections from mobile APs to the Internet and use IEEE 802.11 in ad hoc mode to simulate links among mobile devices and mobile APs. We configure the WiMAX range to cover all mobile APs, and we set the 802.11 range to be 120 m. Two-Ray model is used as the propagation model and UDP is used as the transport protocol in our simulations. Simulation time is set long enough such that all files can be completely transferred.

We follow the current data plan prices of T-Mobile [START_REF]T-Mobile data plan[END_REF] to design the cost functions. We define three cost functions: cent/KB ($5 for 1 GB) where x is the amount of transferred data in KB. S 1 and S 2 cover the Internet access cost, and S 3 covers the local resource consumption cost. Each mobile AP may decide to employ one of the cost functions, or adapt a linear combination of two of them.

In Section 5, we examine our system with networks with a single service. In this section, we investigate our system's performance with more than one service, so as to exercise two different service selection strategies. In addition to the two metrics described earlier, we consider metrics: (i) Profit : the total monetary cost (C r ) charged by a service for its local resource consumption after each simulation, (ii) Cost : the total cost paid by a mobile device on average for each file, (iii) Endto-end delay: the average delay per file from the instant a mobile device scans services to the instant when the last packet reaches destination; (iv) Number of interruptions: the average number of disconnections during each file transfer, and (v) Overhead : the ratio between the total traffic amount and the total file size. We ran each simulation five times with different random seeds, and plotted the averages of the results obtained in all runs. If not otherwise specified, we consider all mobile devices to select the service based on the cost. By default, we use the same V value for all mobile APs. In the following two sections, we consider the static and mobile scenarios, respectively.

Evaluation under Static Scenarios

We configure a network with a WiMAX base station, two mobile APs, and seven mobile devices. Each mobile AP offers a service, and we call them service A and B, respectively. Service A employs a more expensive cost function of S 1 + S 3 , and B employs a cheaper cost function of S 2 + S 3 . All mobile devices are in the range of both mobile APs. In each simulation, every mobile device sequentially transfers 50 equal-sized files. We conduct each simulation with two file sizes: 512 KB and 1 MB. Due to the space limitations, we present the results with 512 KB files if not otherwise specified.

Generality of the MAPA algorithm. We compare MAPA against two baseline algorithms: ALL and ONE. In ALL, a service always accepts request from mobile devices no matter how much workload it is carrying on. Hence, it aims to maximize its revenue. In ONE, a service always rejects request unless it is serving no request. Thus, ONE is designed for service to provide best service quality to one request. Different from ALL and ONE, MAPA employs a parameter V . We vary V ∈ [0, 2000], and repeat the simulations with MAPA. We find that ALL and ONE achieve similar revenue, profit, and end-to-end delay as MAPA with V = 10 and V = 2000, respectively. Hence, MAPA is a general algorithm for diverse quality-of-service needs.

Trade-off between revenue and transfer delay. We plot the resulting profit and transfer delay in Fig. 6. Fig. 6(a) shows that, with a small V , service A achieves higher revenue due to its higher Internet access cost. This in turn leads to higher workload and longer transfer delay as illustrated in Fig. 6(b). With a larger V , service B achieves higher revenue because its maximum workload is raised. With V > 1000, service B accepts all requests and achieves the highest possible revenue, at the expense of long transfer delay. Fig. 6 reveals the trade-off between revenue and transfer delay.

V 's implication on profit. Fig. 6(a) reveals that service B makes higher profit than A when V ∈ [100,2000]. This can be attributed to B's lower Internet access cost. In fact, with V ∈ [100, 600], service B makes higher profit even when A achieves high revenue. With V ∈ [0, 100], service A makes higher profit, because B has saturated its maximum workload. Service A has a larger maximum workload due to its higher cost.

User-specified delay quality level. We consider the heuristic, presented in Sec. 3.3, which maps a delay quality level to a suitable V value. We vary the delay quality level of B from 45 to 172 secs. Service A sets its delay quality level to be half of B's. Fig. 7 presents the simulation results, in which x-axis is the delay quality level of service B. This figure shows that when the delay quality level of B ≤ 60 secs, mobile devices completely avoid service A. This is because the delay quality level for A is too short for 512 KB files. Once the delay quality is large enough, service A starts to receive requests, and its revenue and profit increase. At the delay quality of 75 secs (i.e., 150 secs on the x-axis), service A accepts all requests. That leads to the saturated revenue and transfer delay at service A as shown in Figs. [START_REF]My virtual neighbor[END_REF]. We make another observation: the transfer delay is always lower than the delay quality level specified by the users in our simulations. This reveals the effectiveness of our heuristic.

Evaluation under Mobility Scenarios

Mobile users may move around when they are participating in CrowdMAC. To evaluate the performance of our system under user mobility, we set up a 700×700 m 2 network with 40 devices. Among these devices, there are Fig. 8 shows that No Segmentation pays the highest cost up to 42 cents to download the files, i.e., 16 cents higher than Ideal, at the speed of 18 m/s. It is because the increase of the speed leads to a higher link breakage frequency and a higher amount of data which is downloaded to the real queue yet transferred to the mobile device. The Segmentation technique significantly improves the performance. Segmentation leads to the cost close to Ideal, only 1 cent higher to download 25 MB at the high speed of 18 m/s. Segmentation + Prediction even reduces the cost more, approximately equal to Ideal at that speed.

Fig. 9 shows that the end-to-end delay of No Segmentation is approximately twice higher than that of Segmentation. Segmentation + Prediction further reduces the end-to-end delay to 2 secs shorter than that of Segmentation. The higher end-to-end delay can be attributed to more link breakages due to the mobility. We plot the number of interruptions in Fig. 10, which confirms our conjecture. Last, Fig. 11 reports the relative overhead achieved by different techniques. This figure clearly shows that CrowdMAC produces negligible traffic overhead. It also reveals the effectiveness of File Segmentation.

Impact of the incentive mobility. We have shown that CrowdMAC works well even when mobile devices follow a random mobility model. Next we consider a more realistic mobility model, denoted as Incentive Mobility Model. In this model, the mobile devices, after selecting services, try to keep the links between themselves and the services stable, rather than moving fast and causing link breakage. This is done in order to ensure continuity for ongoing services that have already been charged. Mobile devices that are not transferring files follow the Random Waypoint model. We plot the system performance under the Incentive Mobility Model in Figs. 8-11, labelled by Incentive. CrowdMAC achieves much better performance under this realistic mobility model. In particular, Incentive: (i) achieves the same minimum cost as Ideal, (ii) more than 10 secs shorter end-to-end delay than Segmentation + Prediction, and (iii) never suffers from interruptions.

Related Work and Concluding Remarks

Modern mobile phones have been extended to incorporate multiple networking interfaces beyond traditional cellular and WLAN capabilities; this enables them to form opportunistic networks using technologies such as WiFi Direct [START_REF]Wi-Fi certified Wi-Fi Direct: Personal, portable Wi-Fi that goes with you anywhere[END_REF], WiFi Tether [START_REF]Android WiFi tether[END_REF] and Bluetooth. Opportunistic networks complement infrastructure networks with new capabilities to support throughput enhancement [START_REF] Bhatia | ICAM: Integrated cellular and ad hoc multicast[END_REF][START_REF] Luo | The design and evaluation of unified cellular and ad-hoc networks[END_REF] and peer-to-peer cellular traffic offloading [START_REF] Do | Massive live video distribution over hybrid cellular and ad hoc networks[END_REF][START_REF] Han | Mobile data offloading through opportunistic communications and social participation[END_REF][START_REF] Keller | MicroCast: cooperative video streaming on smartphones[END_REF]. Efforts have explored techniques to enhance throughput for mobile devices that suffer from low cellular data rates by selecting proxies that are in fact mobile devices with high cellular link rates [START_REF] Bhatia | ICAM: Integrated cellular and ad hoc multicast[END_REF][START_REF] Luo | The design and evaluation of unified cellular and ad-hoc networks[END_REF]. Recent research has also proposed solutions [START_REF] Do | Massive live video distribution over hybrid cellular and ad hoc networks[END_REF][START_REF] Han | Mobile data offloading through opportunistic communications and social participation[END_REF][START_REF] Keller | MicroCast: cooperative video streaming on smartphones[END_REF] for mobile devices to cooperatively disseminate data. For example, in [START_REF] Do | Massive live video distribution over hybrid cellular and ad hoc networks[END_REF][START_REF] Keller | MicroCast: cooperative video streaming on smartphones[END_REF], nearby mobile devices cooperate to stream live videos; in these schemes, selected mobile devices are scheduled to receive part of videos over cellular networks and relay the received data to other mobile phones over WiFi peer-to-peer networks.

To our best knowledge, CrowdMAC is the first effort to developing a crowdsourcing system to motivate mobile users for sharing Internet access. We showed how to design and implement a middleware framework that incorporates a Lyapunov based admission control algorithm for mobile APs to serve multiple requesting mobile devices optimally and stably, strategies for mobile devices to select mobile APs appropriately, and techniques for handling device and AP mobility. CrowdMAC has been implemented and evaluated on a testbed of diverse Android phones with varying capabilities indicating feasibility of the approach. Our experimental and simulation results show that CrowdMAC: (i) effectively exercises the trade-off between revenue and transfer delay, (ii) adequately satisfies user-specified (delay) quality level, and (iii) properly adapts to device mobility and achieves performance very close to the ideal case (upper bound).

Future Work: The Lyapunov based approach in this paper lends itself well to a practical implementation. One can also consider an alternate game theoretic formulation that models the interaction between mobile devices and mobile APs as a multiparty game. The ability to embed the game theoretic approach into a real system in a dynamic setting is challenging -this is our future work.

To realize a broader and wide-scale deployment of our crowdsourcing scheme, our future work will also address two key concerns. The first concern is that of security. Mechanisms are required to protect a users' file as it passes through arbitrary (and potentially untrusted) nodes, networks and middle-boxes; this includes protection from DOS attacks and from malicious services. How to leverage cryptographic techniques to provide such end-to-end security is our current aim. The second concern is the need for a tighter integration of the proposed scheme into the ISP/provider ecosystem so as to mesh with the business objectives of telcos and service providers. Creating localized networks to support data exchange is becoming a commodity technology. We believe that the ability to crowdsource/share local wireless access can offer a new perspective that may change the scale and scope of mobile data delivery just as VoIP has changed the landscape of telephony today.

Fig. 1 .

 1 Fig. 1. Network architecture of the proposed system.

Fig. 2 .

 2 Fig. 2. Components and workflow (upload case) in the middleware system.

  ) where y sm is a service based function with respect tof d (f d ≤ F max ) defined as y sm = C(sm,f d )f d and y * sm is the maximum value of y sm , Q * sm and U * sm indicate the maximum queue backlog of s m 's real queue and virtual queue.

Fig. 3 .

 3 Fig. 3. Our Android based testbed: (a) a screenshot of our system on a mobile device and (b) an experiment with 5 different types of mobile phones.

( 1 )Fig. 4 .Fig. 6 .

 146 Fig. 4. Diverse Parameter V : (a) revenue and (b) transfer delay.

Fig. 7 .

 7 Fig. 7. Diverse delay quality level: (a) revenue and profit, and (b) transfer delay.

Fig. 11 .

 11 Fig. 11. Traffic overhead of our system.

1 .

 1 Admission Control Procedure : Every time slot t, service sm selects a set of mobile devices rs m (t) from Rs m (t) such that the following maximization condition is satisfied: Transmission Schedule for Incoming Data: Every time slot t, sm schedules transmission for incoming data such that if Qs m (t) -Us m (t) > 0, it does not allow mobile devices to transmit data to the service as well as download data from the Internet. 3. Transmission Schedule for Outgoing Data: Every time slot t, sm always transmits data out of the service if its real queue has data to send.

	max:	(V C(sm, f d ) -Us m (t)f d );	(6a)
	d∈rs m (t)
	st: rs m (t) ∈ Rs m (t).	(6b)
	2.

  8 stationary mobile APs connecting to a WiMAX base station and offering Internet access services. The other mobile devices travel with Random Waypoint model unless otherwise specified and download 50 files with a size of 512 KB. A mobile device downloads only one file each time, and starts the next download 30 secs after it finishes the previous one. Mobile APs are randomly placed in the network such that they cover about 65% of the network area. Some mobile APs are placed overlapped such that a mobile device can have a chance to discover more than one mobile AP. We configure all mobile APs to use the same cost functions S 2 and S 3 . Unless otherwise specified, mobile devices select service using cost based strategy.Impact of techniques handling mobility. We repeat the simulations with different mobility handling techniques, and plot the results in Figs.8-11. The considered techniques are:1. Ideal : The expected cost under no exceptions, such as link breakages. This is the minimum cost a mobile device could possibly pay. 2. No Segmentation: No specific technique is applied. Each file is transferred in its entirety. 3. Segmentation: The performance achieved by using technique File Segmentation for handling mobility. 4. Segmentation + Prediction: The performance of the combination of two techniques: File Segmentation and Mobility based Service Selection.

Multiple proxies/brokers can be used to scale the system. Proxies/brokers can be offered by: (i) a service provider, (ii) an alliance of multiple providers, or (iii) a third-party company.

For simplicity, we consider the provider cost also includes cost paid for the proxy/broker provider.

The proofs of our lemmas and theorems throughout this paper are omitted without breaking the flow, due to the space limitations.

⋆ N. Do and N. Venkatasubramanian are partially supported by National Science Foundation, grants #1059436 and #1057928. ⋆⋆ C. Hsu is partially supported by the National Science Council (NSC) of Taiwan, grant #100-2218-E-007-015-MY2.


Joseph Sventek
email: joseph.sventek@glasgow.ac.uk

Alexandros Koliousis
email: alexandros.koliousis@glasgow.ac.uk

Unification of Publish/Subscribe Systems and Stream Databases The Impact on Complex Event Processing

Keywords: complex event processing, user-defined functions, streams, automata, publish, subscribe, cache

There is increasing demand for complex event processing of ever-expanding volumes of data in an ever-growing number of application domains. Traditional complex event processing technologies, based upon either stream database management systems or publish/subscribe systems, are adept at handling many of these applications. However, a growing number of hybrid complex event detection scenarios require features of both technologies. This paper describes a unification of publish/subscribe and stream database concepts to tackle all complex event processing scenarios, with particular emphasis upon hybrid scenarios. The paper describes the architecture for this unified system, the automaton programming language that it supports, and the runtime system that animates automata. Several examples of automata that exploit the system's unified nature are discussed. Raw automata performance is characterised, and its relative performance against Cayuga with respect to stock trend analysis is presented.

Introduction

There is increasing demand for complex event processing of ever-expanding volumes of data in an ever-growing number of application domains. This explosive growth is fueled by a number of trends in the industry: the availability of inexpensive wireless sensor nodes, the rapid penetration of smart phones in the mobile telephony market, and the growth in availability and sophistication of cloud computing resources. The data deluge resulting from the convergence of these trends dictates that we develop ever more functional and performant complex event processing systems in order to mine the data for information of business or personal importance.

Complex event processing is traditionally achieved using two different technologies: stream database management systems, in which one is able to look backward in time via select statements, and publish/subscribe systems, in which one is able to look forward in time via subscriptions to notifications. Some event processing scenarios naturally fall into one or the other of these categories; increasingly, there are a number of hybrid scenarios in which both capabilities are required -i.e. the ability to process received notifications is dependent upon access to global and local state representing historical and/or active policy information that is crucial to the correct processing of the data.

This paper describes a unification of publish/subscribe and stream database concepts to address these hybrid scenarios. At the same time, the resulting system should also handle scenarios for which the unified nature is not required. The keystone of this unified system is a topic-based, publish/subscribe cache (henceforth, the Cache). Topics are organised in memory as either appendonly stream tables or static relational tables. Ad hoc select queries, enhanced with time windows, can be presented to the cache at any time. An imperative programming language -viz., the Glasgow Automaton Programming Language (GAPL) -is used to program automata to detect complex event patterns over the cached streams and relations. When registered against the cache, each automaton subscribes to chosen topics and receives each event inserted into those topics through the publish/subscribe infrastructure for further processing. Automata can also access (modify) the relational tables, publish new tuples into stream tables, and send events to external processes.

The remainder of the paper is organised as follows. Firstly, we describe related work to place our system in context ( §2). This is followed by a discussion of the Cache architecture ( §3), the automaton programming language ( §4), and the automaton execution model ( §5). We then proceed with an evaluation of the system's performance from a number of perspectives, including a performance comparison against Cayuga for several, relevant stock analysis queries ( §6). The paper concludes with a discussion of the impact that such a unified system has on future complex event processing ( §7), and future work ( §8).

Related work

Codd's relational model structures data into a mathematical object, a relational database, where new information can be extracted using algebraic operators such as projection, selection, union, or join [START_REF] Codd | A relational model of data for large shared data banks[END_REF]. The ordering of columns (attributes) and rows (tuples) in a relational database is immaterial. On the other hand, data streams are modelled as append-only databases supporting continuous queries for which the relative temporal ordering of tuples is significant.

The continuous semantics of queries were first defined in Tapestry, a database system for mail and bulletin board messages [START_REF] Terry | Continuous queries over append-only databases[END_REF]. Roughly speaking, a continuous query is a monotonic query -or, equivalently, a non-blocking query [START_REF] Law | Query languages and data models for database sequences and data streams[END_REF] -that yields incremental results over a sliding time window whose duration is defined by the current execution time and the last timestamp observed in the previous result set. Fig. 1 shows a variant of the basic continuous query execution model, as proposed in Tapestry. This model inspired the first generation of interactions with the Cache, where continuous queries over network flow streams were used to produce real-time visualisations of home networking traffic [START_REF] Sventek | An Information Plane Architecture Supporting Home Network Management[END_REF]. Fig. 1 Fig. 1. The continuous query execution model [START_REF] Terry | Continuous queries over append-only databases[END_REF] (left); and its equivalent Glasgow automaton (right). Our [since τ ] extension to select (line 5) guarantees to return all tuples that have been inserted into table T in the last t seconds. On the other hand, the automaton reacts upon every insertion of a tuple e to table T, populating a time-based sliding window S of duration t (lines [START_REF] Cormode | Finding the frequent items in streams of data[END_REF][START_REF] Zeitler | Massive scale-out of expensive continuous queries[END_REF]. Every t seconds, the automaton sends this window to its registering process (line 26).

an equivalent implementation of the continuous query model in GAPL, as an introductory example to our automata and the unified nature of the Cache. The nature of this unification, as well as our language features, will become apparent in the subsequent sections.

Since TQL, Tapestry's query language, numerous variants of SQL, the language of Codd's relations, have been introduced in the literature, capturing those continuous semantics. CQL, for instance, the continuous query language of the STREAM data management system [START_REF] Arasu | The CQL continuous query language: semantic foundations and query execution[END_REF], provides users with a comprehensive list of time-or count-based sliding window operators to express non-monotonic relations over stream attributes -in other words, stateful relations. Thus, it became apparent to us that the use of sliding windows in stream processing is two-fold. Apart from producing incremental results, sliding windows are also used to maintain the intermediate state necessary for order-agnostic operators -mainly, aggregation and join.

Closely related to this work are user-defined aggregate functions, e.g. like those provisioned in Aurora's SQuAl [START_REF] Abadi | Aurora: a new model and architecture for data stream management[END_REF]. A user-defined aggregate function consists of three parts: an initialization function that defines (local) state, opening a window within which the computation takes place; an iteration function that updates state; and a termination function that returns state, when the window closes. User-defined aggregates have been proven to be a sufficient extension to SQL for modeling complex patterns over data streams as finite state machines [START_REF] Law | Query languages and data models for database sequences and data streams[END_REF]. At this point, two further analogies can be drawn between user-defined functions and Glasgow automata.

First, an automaton can not only update local state, but also append tuples to other streams, locally (via a publish command) or remotely (via a send command). Second, in contrast to other event query languages, state need not necessarily be local: using associations, an automaton can modify relational tables, whose current state is immediately available to the rest of the system. Non-deterministic finite state automata, a computational model used in the event query languages of Cayuga [START_REF] Demers | Towards expressive publish/subscribe systems[END_REF][START_REF] Brenna | Cayuga: a high-performance event processing engine[END_REF] and SASE [START_REF] Agrawal | Efficient pattern matching over event streams[END_REF][START_REF] Wu | High-performance complex event processing over streams[END_REF][START_REF] Gyllstrom | On supporting kleene closure over event streams[END_REF], further extend the notion of user-defined aggregates by expressing complex patterns as composites of ordered sequences of events. The FOLD operator of Cayuga, for example, iterates over an a priori unknown sequence of events until a terminating predicate is satisfied, maintaining aggregate statistics in the process; or, the skip till next match operator of SASE maintains intermediate state in arrays in order to express Kleene closures, an operator that has recently received considerable attention in complex event detection [START_REF] Mozafari | From regular expressions to nested words: unifying languages and query execution for relational and XML sequences[END_REF]. For non-deterministic finite automata, the complexity of a pattern lies in determining what comes "next" in event processing [START_REF] White | What is "next" in event processing?[END_REF]. But apart from folding (or skipping) events, it is hard to specify patterns with branching in a Cayuga or SASE automaton. Indeed, a stream has to be replicated and each branch of the pattern must be represented as a different automaton. Finally, it is not always possible to express nested patterns, e.g. a query that uses the local state maintained by another.

The Cache was first used as a stream database of network flows and related policies that govern a home network. Network monitoring and management scenarios have been featured heavily in stream database research. The Tribeca query language [START_REF] Sullivan | Tribeca: a system for managing large databases of network traffic[END_REF], for example, supported demultiplexing and multiplexing of packet streams. The demultiplexing of streams, while similar to the group by SQL operator, enables processing of sub-streams beyond mere aggregate statistics using pipes to transform streams at several stages. The importance of multiplexing (merging) network streams has also been stressed in Gigascope, a high-performance network monitoring tool [START_REF] Cranor | Gigascope: a stream database for network applications[END_REF]. Gigascope has a two-level query architecture to process packets on high-speed links. High performance is achieved by pushing low-level queries (e.g., protocol filtering or aggregation) closer to the physical network interface. High-level queries then perform more complex tasks.

A number of packet stream processing algorithms focus on the frequency of certain flow attributes, e.g. the throughput to (from) an IP address or a transport port. The problem has been formally characterized as mining the frequent items in data streams [START_REF] Cormode | Finding the frequent items in streams of data[END_REF], and its applications to network monitoring include finding the heaviest bandwidth consumers (heavy-hitters), or finding the heaviest connection initiators (super-spreaders) [START_REF] Sekar | Revisiting the case for a minimalist approach for network flow monitoring[END_REF]. These algorithms are expressible, as we will demonstrate, in GAPL. Finally, modern traffic analysis tools also query the implicit structure of flows in a traffic mix, in an attempt to match application labels to the underlying flow patterns, and vice versa. Thus, flow monitoring queries are not just mere counters of some traffic volume metric, e.g. of the number of bytes or packets. Besides identifying frequent items, patterns of temporally correlated flows are used for classification or intrusion detection and are usually expressed as sequences of events [START_REF] Kandula | What's going on?: learning communication rules in edge networks[END_REF].

The Topic-based Publish/Subscribe Cache

There are many situations in which detection of interesting events requires the ability to receive raw events as they occur and the ability to query, as well as modify, global state. In many deployment scenarios, these actions need to be done in real-time. This section describes a topic-based publish/subscribe cache that facilitates such real-time processing.

A working system consists of our centralised Cache and a varying number of applications that use it; the applications and the Cache interact through a custom RPC mechanism. There are three distinct roles that applications can assume with respect to this system:

populate tables with raw events via insert commands; retrieve data from tables periodically via select commands; and/or register interest to be notified when complex event patterns are detected.

The Cache supports the usual SQL commands for creating tables and inserting tuples into tables. The Cache supports two types of tables, ephemeral tables, append-only streams for which the primary key is the time of insertion, and persistent tables, time-varying relations for which the primary key is the first defined field of the table schema. Tuples inserted into ephemeral tables are stored in a circular memory buffer,1 while tuples inserted into persistent tables are stored in the heap. For persistent tables, an on duplicate key update modifier to the insert command is used to update, rather than append, a row in the heap, while maintaining the temporal order of events. Thus, when retrieving tuples from the Cache, the default order for either table type is the time of insertion, unless overridden by an order by modifier.

For monitoring applications, the selection operator has been augmented with appropriate time and count window extensions to reflect the continuous nature of the events. Thus, apart from typical order by and group by operators, ad hoc select queries over cached streams can use time interval expressions that narrow the scope of results to a particular time period, e.g. select * from table [since τ ], where τ is the timestamp of the last retrieved tuple. Typically, monitoring applications submit such queries periodically.

The third role of applications, viz. reaction applications, is enabled by the unification of this stream database view of events with a publish/subscribe infrastructure, achieved as follows. Every table created in the Cache, whether ephemeral or persistent, corresponds to a publish/subscribe topic with the same name. Whenever a tuple is inserted into a table, that tuple is published as an event to its associated topic. Applications can register automata (i.e., complex event patterns) against the database. As new tuples are inserted into a table, all automata that have subscribed to that topic will receive events for processing. If, while processing an event, an automaton determines that it has detected a pattern of interest, it may send information about the complex event to the application that registered the automaton. Additionally, during normal processing of events, an automaton may publish (append, insert, or update) a new tuple into another table in the Cache, whether ephemeral or persistent. This unity allows for complex patterns to be presented as materialised views in the stream database and, vice versa, materialised views to be used to derive complex patterns. A typical reaction application (e.g., a policy management engine) registers one or more automata with the Cache. [START_REF] Sventek | An Information Plane Architecture Supporting Home Network Management[END_REF] The automaton programming language 4.1 Language design principles Support for complex event pattern matching, requiring both consumption of raw publish/subscribe events and access to static relations, dictated the following features of the Glasgow Automaton Programming Language:

the ability to subscribe to one or more topic streams over which raw events are conveyed; the ability to publish raw or derived events to other publish/subscribe topics; the ability to store local state across many event deliveries to an automaton; the ability to query one or more persistent tables to access and/or modify static, global relations; and the ability to send information about complex event occurrences back to an automaton's registering application.

Furthermore, one requires a small set of basic data types, a small set of aggregate data structures, and a small set of control constructs to store and filter events locally. The basic data types are described in Table 1. The language also defines a minimal set of aggregate types, e.g. a sequence, a map, or a window, and types required to manipulate these aggregate types, e.g. an iterator over a window.

Every aggregate type is instantiated with a constructor. Note that a sequence instance can contain heterogeneous basic type instances, while each map or window instance is bound to a particular type, basic or aggregate. In fact, the ability to instantiate windows of sequences or maps of sequences enables the creation of ephemeral or persistent tables, respectively, that are truly local within the context of an automaton thread. Finally, the language supports if then else and while constructs. It also supports a typical set of operators for arithmetic, conditional expressions, and assignment. Overall, the C-like syntax for GAPL was chosen to facilitate the coding of commonly-used stream processing algorithms (cf. §6.4), while enabling highperformance filtering of events.

General form for an automaton

In its general form, an automaton program consists of subscriptions, associations, declarations, an initialization clause, and a behavior clause -in that order.

Each automaton source starts with binding a local variable to each publish/subscribe topic to which it wishes to be subscribed. Every time an event is delivered on any subscribed topic, the bound local variable refers to the last received event over that topic. Attribute values are assigned automatically to variables with names and types being determined by the corresponding table schema. These variables are accessed using the dot notation. For example, variable e.x holds the value of attribute x of event e. The Cache provides a built-in topic, Timer, which delivers a tuple every second consisting simply of a timestamp data type attribute. 2 All other topics must have been created earlier by create table calls made by applications (or during Cache initialization, from a configuration file). An automaton must always subscribe to at least one topic.

Associations are used to bind a local map variable to a persistent table in the Cache. The automaton can then access and modify tuples in the associated persistent table through calls to lookup() and insert() methods on that map variable, respectively. Subsequent declarations in an automaton enable the programmer to declare additional local variables needed for processing.

The initialization clause of an automaton is executed once, after successful compilation. It is usually used to initialise local variables, but therein a programmer can perform any actions supported by the language. The behavior clause, on the other hand, is executed each time an event is delivered to any of the subscribed topics.

Example hybrid automaton

This section describes an automaton that implements a hybrid application scenario, one in which the the processing of events depends upon access to global persistent policy state, taken from the current deployments of the Cache -i.e., as part of a home network router [START_REF] Sventek | An Information Plane Architecture Supporting Home Network Management[END_REF]. Households occupied by multiple, sometimes unrelated adults (e.g., students sharing a flat) often opt for broadband plans with rapidly escalating charges if a per month bandwidth allowance is exceeded. These households wish to control bandwidth consumption as it nears the monthly allowance. Additionally, it is often the case that a single member of the household is usually the cause of exceeding the monthly allowance; therefore, there is a desire to track the usage of a subset of the members of the household.

The three tables used to demonstrate this functionality are shown in Fig. 2. Table Flows is an ephemeral table populated with periodic aggregate statistics of home networking traffic (i.e., per flow number of bytes and number of packets accumulated every second). The other two tables are persistent. The Allowances table is populated with a monthly download byte-limit per monitored IP address using a network management utility; and the Usage table records accumulated bandwidth usage, reset to zero by a network management utility at an appropriate frequency.

Fig. 3 shows an automaton that tracks the bandwidth usage per monitored IP address, generating a notification to the registering application (i.e., a policybased management system) when a limit has been exceeded. The automaton subscribes to Flows events; and associates maps a and b with tables Allowances and Usage, respectively. Upon receipt of each Flows event, it does the following:

it generates an identifier ip from the flow's destination address; if no entry for ip is found in Allowances, it stops processing; otherwise, it looks up an allowance for this ip address; if there is an entry for ip in table Usage, it fetches the accumulated usage; otherwise, it sets usage n to zero; it increments n by the number of bytes in the Flows tuple; if ip's limit is exceeded, it sends an event to the registering application; and it updates the usage for this IP address in the Cache.

Automaton execution model

When an application registers an automaton against the Cache, it provides the source code for the automaton along with data required for the Cache to create an RPC channel back to the registering application (i.e., a host, a port, and a service name). The source code is then compiled into instructions for a stack machine. If a compilation error is detected, information about the error is communicated back to the registering application, and the RPC channel is closed. Upon successful compilation, a new Pthread is created to animate the automaton, and an identifier is returned instead; this identifier can be used by the registering application to manage the automaton at a later time (e.g., to unregister it).

When the Pthread is created, the byte code sequences resulting from the compilation of the initialization and behavior clauses are bound to an instance of a stack machine interpreter. The initialization sequence is executed once and the thread then enters a continuous loop, awaiting an event on one of its subscribed topics (a tuple insertion); the runtime system guarantees that tuples are delivered to an automaton in strict time-of-insertion order. Upon receipt of an event, the behavior sequence is executed. If an automaton executes a send in the behavior sequence, an RPC call, containing the send() arguments, is made to the registering application. If the automaton executes a publish in the behavior sequence, a tuple is inserted into the table (topic) specified in the publish() arguments, potentially triggering other automata to execute. The default Pthread scheduling algorithm is used by the Cache and appropriate conditional critical regions are used to guarantee safe execution amongst multiple automata threads.

The runtime implements an aggressive garbage collection policy as soon as it knows that heap allocated storage is no longer in use; the delete procedure can be optionally invoked by code to advise when storage is no longer in use.

Optimizations enabled by the execution model

Many complex event processing systems based upon the stream database model require the creation of multiple temporary event streams for their operators to perform the requisite aggregations and disaggregations demanded by a pattern matching logic. This leads to a very large number of operators that must be scheduled, and a very large number of additional tuples that need to be delivered to a directed acyclic graph of operators that represent the query. The imperative structure of GAPL, together with the ability to declare and manipulate an automaton's local state, enable combinations of multiple operators into a single automaton, thus reducing the scheduling stress on the Cache. The following example, documented fully in [START_REF] Koliousis | DEBS Grand Challenge: Glasgow automata illustrated[END_REF], demonstrates this effect. The DEBS 2012 Grand Challenge posed two complex queries with regards to monitoring manufacturing equipment. Here we discuss the first query, illustrated in Fig. 4. The query consists of fifteen operators (circles), generating nine intermediate streams (squares). Operators 1 and 4 compute a state transition by correlating consecutive events inserted into the initial stream 0; once a pattern is detected by either of them, events are published to operator 7. In turn, operator 7 looks for events in stream 5 followed by events in stream 8. Since this logic is sequential, GAPL allows us to combine these three operators together, in one automaton. Also, operators 10 and 11 have different functionality but they maintain the same state, a 24-hour sliding window over stream 58. If these operators were to be treated separately, then the same window would be maintained twice. Since their logic is independent, this duplication can also be avoided by merging them in one automaton. The other ten operators simply replicate the aforementioned functionality but on different attributes. In fact, our final solution merged all fifteen operators into a single automaton -i.e. one execution thread -avoiding the use of intermediate streams all together. By doing so, the throughput increased by 57% and the execution time decreased significantly, as opposed to having one automaton per operator [START_REF] Koliousis | DEBS Grand Challenge: Glasgow automata illustrated[END_REF].

Multi-query optimizations

Sharing derived events amongst Glasgow automata is currently a programmer's task and it is achieved by explicitly publishing these events to intermediate streams that are, in turn, accessible by other automata running in the context of the Cache; it is not an automated process. Managing these events programmatically, using basic or aggregate data type instances, is one of the key features that enable high-performance event filtering.

A limitation, however, of user-defined optimisations is that multiple automata registrations are not open to multi-query optimisations possible in other query engines. Cayuga, for example, merges equivalent automaton states into a directed acyclic graph using YFilters [START_REF] Diao | Path sharing and predicate evaluation for high-performance XML filtering[END_REF][START_REF] Demers | Towards expressive publish/subscribe systems[END_REF], whose edges represent static or dynamic predicates that determine state transitions. This trade-off, where on one hand scaling to thousands of queries requires multi-query optimisations, while on the other hand high performance and expressiveness requires user-defined optimisations, is an open research question; we explore it by investigating the use of GAPL as an intermediate language between the two approaches.

Evaluation

Experiments are run on two AMD Athlon 64 dual core 2.7GHz processors with 4GB of RAM running Ubuntu Linux 2.6 and Windows 7, respectively. The Cache is implemented as a multi-threaded process. Its main thread handles RPC requests (e.g., tuple insertions, automaton registrations) from other processes serially; new threads are created upon each successful automaton compilation. The remainder of this section documents the performance of automata in this environment.

Cost of Built-in functions

Automata are interpreted programs, thus it is important to characterise the costs of invoking built-in functions in the language. The automaton template in Fig. 5 was used to measure the execution costs to invoke a representative set of the built-in functions supported by the language. The built-in specific declarations (line 60), initialization (line 63), and invocation (line 70) were incorporated into the template as appropriate. The print function was used to display the results on standard output; the number printed is the number of microseconds required for each invocation of the built-in under test. Each automaton was executed for two minutes on an unloaded machine.

Fig. 6 shows the minimum, 25-th, 50-th, 75-th percentiles, and maximum of execution times recorded for each built-in. 3 Several things are apparent from this data: the average cost of basic built-in functions (e.g. insert, lookup) is ∼ 3µs; identifier generation, which requires access to the heap and copying of strings, is about twice as expensive as a basic built-in; publishing an event to another topic is about three times the basic built-in cost; and sending an event to an external process takes ∼ 200µs.

Performance at Scale

As the number of simultaneously subscribed automata increases, one expects the scheduling delay for each automaton to increase. Thus, it is important to understand how the Cache performs as the number of automata and also the frequency of tuple insertion scale up.

To stress the system, we vary the number of automata that subscribe to the Flows topic (cf. §4.3). Independently, we vary the frequency of tuple insertion into the Flows table. An important measure of the ability for the system to handle the increased scale is the delay between when a tuple is inserted into the table/topic, and when each subscribed automaton processes the event. This is measured using the automaton in Fig. 7. For each automaton, a different value is assigned to id (line 85); the subsequent log generated by the automaton is analysed for mean and standard deviation of the average delay observed across all automata, as well as for minimum and maximum delays observed (lines 91-93). The independent parameters for the experimental runs are the number of automata simultaneously subscribed and the cycle period of tuple insertion into Flows, ∆t.

Fig. 8 displays the measured delay parameters for ∆t = 8ms. It is clear that the average delay grows linearly as the number of automata scales from one to eight. Note that, in the deployments to date, the typical number of flow tuples inserted are approximately 100 events/second; ∆t = 8ms corresponds to an insertion rate of 125 tuples/second. It is also important to note that it is quite uncommon in our experience to have several automata subscribed to high frequency topics like Flows. Fig. 9 shows the measured delay parameters for four automata as ∆t scales from 4ms to 64ms (insertion rates of 250 events/second to 16 events/second). The average and variance of the delay remain essentially constant across this range of packet insertion rates. Thus, the system scales well with number of automata and frequency of tuple insertion. The linear growth in average and standard deviation of delay with number of automata is consistent with scheduling increasing numbers of Pthreads. The constancy of average and variance against insertion frequency indicates that there is plenty of execution capacity in the Cache for the loads presented.

Performance at stress

Another important measure of the capacity of the system is the maximal rate at which it can absorb and generate RPC requests and responses. To measure this, we executed the automaton of Fig. 10 to measure one-way and two-way stress performance, with a single application performing insert calls into a Test table as rapidly as possible. Note that to measure two-way stress performance, simply uncomment line 117 in the automaton. The performance as the number of integer fields in the Test table schema varies from 1 to 16 is shown in Fig. 11. Fig. 12 shows the performance as the number of characters in a schema consisting of a single varchar field varies from 1 to 10,000. The RPC system performs fragmentation/reassembly at 1024-byte boundaries, so the drop with buffer size is to be expected.

Finding frequent items

This section evaluates the implementation of the "frequent" algorithm, a onepass algorithm for finding the top-k items in a data stream [START_REF] Cormode | Finding the frequent items in streams of data[END_REF], as a Glasgow automaton (Fig. 13). The algorithm stores k-1 out of n items, according to their popularity; after processing n events, the approximate result set will contain at least those items that have occurred n/k times. The input data to the automaton are 264, 745 out-going HTTP requests (appended to an ephemeral table Urls) to 5,572 unique hosts, as logged by a router running in a small office environment at the University of Glasgow. Fig. 14 shows the Zipfian frequency distribution of the data set, where hosts are ranked by their popularity, a well-known characteristic of Web traffic.

An alternative approach is to introduce the algorithm as a built-in procedure in the language, a de facto approach in traditional query languages. Indeed, there might be situations where, despite the efficient code generated from the GAPL compiler, an interpreted solution may be insufficiently performant.

To demonstrate this, we also implemented the frequent algorithm as a builtin function in the language and evaluated the two approaches -namely, the automaton of Fig. 13 and the automaton of Fig. 16. From an algorithmic perspective, the execution time of these automata is dominated by O(1) operations (e.g. inserting into T) and O(k) operations (e.g., iterating over T). As k increases, the number of O(1) operations increases, and the O(k) operations become more expensive. Thus, it is expected that as k increases, the mean execution time (µ) will decrease and the standard deviation (σ) will increase. Fig. 15 shows the coefficient of variation (σ/µ) for both the imperative and the built-in implementation of the frequent algorithm.

Comparison with Cayuga

This section evaluates the performance of the Cache against the Cayuga query engine [START_REF] Demers | Towards expressive publish/subscribe systems[END_REF]. Most of the examples in the Cayuga distribution, as well as the data sets provided, are related to complex event processing for stock market investors. We evaluate three exemplar Cayuga queries against equivalent implementations in GAPL. The dataset used contains 112,635 anonymised stock events whose schema consists of a timestamp, an identifier as a company's name, and a price.

The first query is an example of a basic built-in operator that simply publishes incoming events to another stream. In the Cayuga Event Language (CEL), the query is:

SELECT * FROM Stock PUBLISH T
The equivalent Glasgow automaton is one that subscribes to stream Stock and publishes an event to another stream T with the same schema. I.e., subscribe s to Stock; behavior { publish('T', s); }

The second query is an example of a Cayuga automaton with multiple states that detects a double-top formation in the price chart of any stock -this is a well-known pattern amongst trade analysts, also known as an M-shaped pattern. Fig. 17, for example, shows one of the M-shaped patterns found in the data set. The CEL query that detects such patterns is illustrated in Fig. 18. Certain details of the query have been omitted, while others have been simplified; we summarise its functionality in the following. 4Starting from the innermost expression (lines 174-176), Cayuga correlates two consecutive Stock events for the same company until the price rebounds. The engine then attaches a new automaton instance to the next query state, continuously iterating over an a priori unknown number of Stock events for the same company, as long as its price monotonically increases. This is achieved by the inner FOLD operator (line 177). Cayuga proceeds outwards in the query, transiting to the next Cayuga automaton state, looking for a monotonic decrease in that stock's price, and so on, spawning new automaton instances along the way and storing valleys and peaks of a given stock's price in attributes A to F of the resulting schema. Our implementation (simplified) is shown in Fig. 19. The automaton maintains booleans A to F, together with their associated price values (a to f), in a map of sequences; each entry represents a small state machine for a given stock. Once all states A to F for a stock are true, then the M-shaped pattern has been detected. Depending on the current stock price, the algorithm backtracks to previous states or proceeds to the next (ascending or descending price runs) accordingly. Note here that our solution is algorithmic, using the if then else constructs of GAPL.

The final query is an example use of the FOLD operator to perform aggregate computations across multiple iterations. The CEL query has the form:

266 SELECT * FROM ( SELECT *, 1 AS counter FROM Stock ) FOLD {$1.Name = $2.Name, $.Price < $2.Price, $.counter + 1 AS counter} Stock 270 PUBLISH T
The desired behaviour is to detect continuous runs of increasing prices for each stock, and to display the sequence of events that constituted each run. This has been implemented using the two Glasgow automata illustrated in Fig. 20. The automaton on the left maintains a map entry (a sequence) for a given company (s.id) as long as its price is monotonically increasing. At the end of each run, i.e., when the stock's price decreases, the sequence contains the current lowest price, the start time, the length of the run, and current highest price, and the end time. In order to also display the sequence of events that constitute each run, we publish to another topic, Folded, and implement a custom state management system -with states create, change, and remove -in the automaton on the right. Fig. 21 shows the results from comparing the execution time of the three CEL queries with their equivalent implementations in the automaton programming language. The Cayuga engine best compiles in Microsoft's Visual Studio, thus the experiments were run on a Windows platform. The Cayuga execution times are the elapsed time after all events have been loaded into memory and until all events have been processed. The Cache was never provisioned for post-hoc analysis of in-memory data: all events are processed in real-time. For a fair comparison, we derive our timings by first appending all events in a window, and then iterate over the window and execute the queries.

For the first query, the performance improvement against Cayuga is an order of magnitude. This strengthens the argument of the efficacy of the automaton execution model and the efficient unification of the publish/subscribe infrastructure with the data stream management code. For the second query, the automaton detects the pattern twice as fast as Cayuga. This is another example of the ability to implement multiple state machines under a single execution thread, which contributes to this performance enhancement. Finally, for the third query, our implementation is dramatically faster (×50) than Cayuga's equivalent.

The impact on complex event processing

We have proposed an algorithmic, imperative approach to complex event processing. The first impact of this work is Turing completeness, something that was proposed from a theoretical basis in [START_REF] Law | Query languages and data models for database sequences and data streams[END_REF]. Some event languages have a solid background in event calculi and result in one-line expressions that are compact implementations, but are not open to user optimizations -apart from physical query execution plans. For example, there is a large body of complex event language research on Kleene closures [START_REF] Agrawal | Efficient pattern matching over event streams[END_REF]. Although not explicitly documented here, we have implemented SASE's Kleene closure operator (e.g., based on partition contiguity) with a map of windows in GAPL.

Our experiences thus far are that the imperative programming style of GAPL enables it to be used in many domains: home network management [START_REF] Sventek | An Information Plane Architecture Supporting Home Network Management[END_REF], industrial applications [START_REF] Koliousis | DEBS Grand Challenge: Glasgow automata illustrated[END_REF], and, given the present comparisons to Cayuga, stocks. In addition to its expressiveness, this imperative model has been shown more performant than a declarative event language (CEL). Thus, it may be viewed as an intermediate language between SQL-like queries (logical query plans) and their execution interpretation (physical query plans).

Conclusions

It is clear that the automaton language, as integrated into the Cache, provides a very high-performance complex event processing capability. It can be criticized for its imperative, C-like structure, in terms of usability by individuals wanting to deploy their own automata. We have started to investigate compilation of stream expressions for complex event patterns, such as Cayuga's, into equivalent automata. An alternative approach is to compile stream expressions directly into instructions for the stack machine that underlies the Cache.

In comparing with Cayuga, we have determined that we need to be able to create streams on the fly. This will enable exploration of the dynamic demultiplexing of streams, as lately discussed in [START_REF] Zeitler | Massive scale-out of expensive continuous queries[END_REF]. We continue our comparative endeavours with the Linear Road Benchmark [START_REF] Arasu | Linear road: a stream data management benchmark[END_REF].

Fig. 4 .

 4 Fig. 4. The DEBS 2012 Grand Challenge query.

Fig. 5 .

 5 Fig. 5. Built-in cost template automaton.

Fig. 6 .

 6 Fig.6. The execution cost of built-in functions.

Fig. 7 .Fig. 8 .Fig. 9 .

 789 Fig. 7. Performance at scale template automaton.

Fig. 10 .Fig. 11 .Fig. 12 .

 101112 Fig. 10. Performance at stress template automaton.

Fig. 13 .

 13 Fig.13. The frequent algorithm[START_REF] Cormode | Finding the frequent items in streams of data[END_REF].

Fig. 14 .Fig. 15 .Fig. 16 .

 141516 Fig. 14. Number of requests per Web page ordered by popularity

Fig. 17 .

 17 Fig. 17. An M-shaped pattern in the dataset illustrated.

Fig. 21 .

 21 Fig. 21. Benchmarking against Cayuga.

  also shows

	# Let T be a table with attribute x.	11 subscribe e to T; # A new tuple e of T.
	Set τ = -∞	subscribe p to Timer;
	Set S = ∅	window S;
	FOREVER DO	int period, τ ;
	S = {select x from T [since τ ]}	initialization {
	# Each tuple j in S has a timestamp tj .	16	S = Window(sequence, SECS, t);
	τ = arg max j∈S tj		period = t;
	Return results to user		τ = 0;
	Sleep for some period of time, t sec.	}
	ENDLOOP	behavior {
			if (currentTopic() == 'T')
		22	append(S, Sequence(e.x), e.tstamp);
			else { # The current topic is Timer.
			τ += 1;
			if (τ % period == 0) {
		26	send(S); # Return results.
			S = Window(sequence, SECS, t);
			}
			}
		30 }

Table 1 .

 1 Description of data types.

	Type	Basics
	int	64-bit integer
	real	Double-precision floating point
	tstamp	64-bit unsigned integer (nsec since the epoch)
	bool	True or false
	string	Variable-length UTF-8 character array
	Type	Aggregates
	sequence	Ordered set of heterogeneous basic data type instances
	map	Map from an identifier to an instance of the bound type
	window	Collection of bound type instances, constrained either to a
		fixed number of items or a fixed time interval
	identifier	Key used in maps
	iterator	Used to iterate over all instances in a map (keys) or window
		(data values)

This is the reason that the component is called the Cache.

This is an example of punctuation-carrying heartbeat functionality[START_REF] Johnson | A heartbeat mechanism and its application in Gigascope[END_REF].

The overhead of the while loop was subtracted from the values produced by the automaton.

The complete queries summarised in Figures18 and 19are available at www.dcs.gla.ac.uk/∼koliousa/middleware.html.

; s = Sequence(f.price1, f.time1, f.count, f.price2, f.time2); append(w, s); insert(m, id, w); } else if (f.command == 'change') { w = lookup(m, id); s = Sequence(f.price1, f.time1, f.count, f.price2, f.time2); append(w, s); } else { # Removed from map stocks. w = lookup(m, id); i = Iterator(w); while (hasNext(i)) { s = next(i); publish('T', s); } remove(m, id); } 265 } Fig. 20. Detecting sequences of increasing stock prices.