Search

Packet classification is a critical component in network appliances. Software Defined Networking and cloud computing update the rulesets frequently for flexible policy configuration. Tuple Space Search (TSS), implemented in Open vSwitch (OVS), achieves fast rule updating at the sacrifice of the classification rate. In TSS, each tuple is managed by a hash table and classifying a packet needs to go through all hash tables. Merging tuples can reduce the number of hash tables, but inevitably increases the hash conflicts that may even worsen the classification performance in some cases. No existing algorithm meets the need of both fast packet classification and online rule updating. In this paper, we propose Convolutional Neural Network (CNN)-based Range Partition (CRP) to achieve fast packet classification and online update simultaneously. CRP exploits CNN-based image recognition to quickly partition tuples into range spaces upon the change of ruleset distribution, which reduces hash operations while avoiding rule overlapping caused by hashing many rules to the same location of the hash table. Experimental results demonstrate that CRP achieves 3.2x classification speed and 4.2x update speed on average compared with state-of-the-art algorithms. We also implement CRP in OVS. The throughput of CRP-OVS is 10x that of native OVS.

Program execution on a multicore platform, even a homogeneous one, does not guarantee performance gains. The key is in letting each of the cores contribute to the overall computation for the maximum amount of time. For anything but trivial problem settings, and especially for heterogeneous platforms like ones made of CPU and GPU cores, this calls for some form of load balancing, i.e., explicit or implicit workload shifts between the cores, so that idle times are eliminated to the maximum degree possible. In this chapter we examine the two generic categories of load balancing algorithms: static which can be considered pro-active, meaning that they pre-calculate load assignments without expensive communications taking place, and dynamic which can be considered re-active as they can adapt to changes in the execution environment. The chapter is concluded by two cases studies that show how both static and dynamic load balancing can be used to evenly distribute the work between the nodes of a heterogeneous platform, that combines both CPU and GPU nodes.

In the 5G-envisioned Internet of vehicles (IoV), a significant volume of data is exchanged through networks between intelligent transport systems (ITS) and clouds or fogs. With the introduction of Software-Defined Networking (SDN), the problems mentioned above are resolved by high-speed flow-based processing of data in network systems. To classify flows of packets in the SDN network, high throughput packet classification systems are needed. Although software packet classifiers are cheaper and more flexible than hardware classifiers, they could only deliver limited performance. A key idea to resolve this problem is parallelizing packet classification on graphical processing units (GPUs). In this paper, we study parallel forms of Tuple Space Search and Pruned Tuple Space Search algorithms for the flow classification suitable for GPUs using CUDA (Compute Unified Device Architecture). The key idea behind the offered methodology is to transfer the stream of packets from host memory to the global memory of the CUDA device, then assigning each of them to a classifier thread. To evaluate the proposed method, the GPU-based versions of the algorithms were implemented on two different CUDA devices, and two different CPU-based implementations of the algorithms were used as references. Experimental results showed that GPU computing enhances the performance of Pruned Tuple Space Search remarkably more than Tuple Space Search. Moreover, results evinced the computational efficiency of the proposed method for parallelizing packet classification algorithms.

The categorisation of network packets according to multiple parameters such as sender and receiver addresses is called packet classification. Packet classification lies at the core of Software-Defined Networking (SDN)-based network applications. Due to the increasing speed of network traffic, there is an urgent need for packet classification at higher speeds. Although it is possible to accelerate packet classification algorithms through hardware implementation, this solution imposes high costs and offers limited development capacity. On the other hand, current software methods to solve this problem are relatively slow. A practical solution to this problem is to parallelise packet classification using multi-core processors. In this study, the Thread, parallel patterns library (PPL), open multi-processing (OpenMP), and threading building blocks (TBB) libraries are examined and implemented to parallelise three packet classification algorithms, i.e. tuple space search, tuple pruning search, and hierarchical tree. According to the results, the type of algorithm and rulesets may influence the performance of parallelisation libraries. In general, the TBB-based method shows the best performance among parallelisation libraries due to using a theft mechanism and can accelerate the classification process up to 8.3 times on a system with a quad-core processor.

Software switches are being deployed in SDN to enable a wide spectrum of non-traditional applications. The popular Open vSwitch uses a variant of Tuple Space Search (TSS) for packet classifications. Although it has good performance on rule updates, it is less efficient than decision trees on lookups. In this paper, we propose a two-stage framework consisting of heterogeneous algorithms to adaptively exploit different characteristics of the rule sets at different scales. In the first stage, partial decision trees are constructed from several rule subsets grouped with respect to their small fields . This grouping eliminates rule replications at large scales, thereby enabling very efficient pre-cuttings. The second stage handles packet classification at small scales for non-leaf terminal nodes , where rule replications within each subspace may lead to inefficient cuttings. A salient fact is that small space means long address prefixes or less nesting levels of ranges, both indicating a very limited tuple space. To exploit this favorable property, we employ a TSS-based algorithm for these subsets following tree constructions. Experimental results show that our work has comparable update performance to TSS in Open vSwitch, while achieving almost an order-of-magnitude improvement on classification performance over TSS.

Packet classification is one of the core components in Software Defined Network (SDN) systems, e.g., Open vSwitch. However, the current packet classification algorithm Tuple Space Search (TSS), which is implemented in SDN systems, has low lookup speed and can be attacked. Although some algorithms that support incremental updates are proposed to improve the lookup speed, e.g., TupleMerge and PartitionSort, but are not general and scalable to apply in SDN systems and replace TSS. In this paper, we propose a general, scalable, and high-performance packet classification algorithm MultilayerTuple. MultilayerTuple reduces the number of tuples by splitting the prefix lengths of rules into ranges in each layer, then creates the next layer to replace the long rule chain recursively. The experimental results demonstrate that compared to TSS, TupleMerge, and PartitionSort, MultilayerTuple achieves 21.8x, 2.1x, 2.2x lookup speed and 2.3x, 12.3x, 8.5x update speed. Furthermore, we have implemented MultilayerTuple in the OpenFlow table and MegaFlow cache of Open vSwitch, and it achieves 16.0x and 10.2x lookup speed than TSS. Especially when TSE attack happens, MultilayerTuple can effectively defend against it.

The frequent rule updating in Software Defined Networking and cloud computing requires the packet classification algorithm to perform fast packet matching and flow table updating simultaneously. The existing algorithms, e.g. decision-tree-based or hash-based, achieve fast packet classification at the sacrifice of the rule updating or vice versa. We propose the Dynamic Adaptive Tuple (DynamicTuple) for both fast packet classification and rule updating simultaneously. DynamicTuple builds a performance model of tuple based packet classification and exploits dynamic programming to find the appropriate tuple formulation to minimize the lookup time. When the rules keep updating, DynamicTuple can retain the proper tuples and rebuild the improper tuples, thus the tuple in DynamicTuple is dynamic adaptive. The experimental results demonstrate that DynamicTuple achieves 33.1x, 5.6x, 5.7x classification speed and 2.9x, 11.0x, 8.5x updating speed compared to Tuple Space Search, TupleMerge, PartitionSort. By implementing DynamicTuple, the OpenFlow table of Open vSwitch achieves 26.6x classification speed.

Actors collaborate via message exchanges to reach a common goal. Experience has shown, however, that pure message-based communication is limiting and forces developers to use design patterns. The recently introduced dataspace actor model borrows ideas from the tuple space realm. It offers a tightly controlled, shared storage facility for groups of actors. In this model, actors assert facts that they wish to share and interests in such assertions. The dataspace notifies interested parties of changes to the set of assertions that they are interested in. Although it is straightforward to add the dataspace model to untyped languages, adding a typed interface is both necessary and challenging. Without restrictions on exchanged data, a faulty actor may propagate erroneous data through a malformed assertion, causing an otherwise well-behaved actor to crash—violating the key principle of failure isolation. A properly designed type system can prevent this scenario and rule out other kinds of uncooperative actors. This paper presents the first structural type system for the dataspace model of actors; it does not address the question of behavioral types for assertion-oriented protocols.

Software Defined Networks (SDN) emerged as a new paradigm for network management, defining an architecture the physically decouples the control and data planes. An SDN architecture based on a central controller does not scale and neither is fault-tolerant since it presents a single point of failure. Distributed SDN controllers based on an eventually consistent model for the network state also bring serious drawbacks: a complex programming model for network applications; and it can lead to network anomalies. Consequently, solutions considering a consistent model for the network state are emerging. In these approaches, the distributed controllers use a consistent and fault-tolerant data store that keeps relevant network and applications state. Unfortunately, these approaches do not consider security requirements for the SDN. This work aims to design, implement and evaluate a secure and consistent model for the control plane based on DepSpace, a secure tuple space implementation used to coordinate distributed processes. Experimental results show the practical feasibility of the proposed architecture.

Efficient and highly available packet classification is fundamental for various security primitives. In this paper, we evaluate whether the de facto Tuple Space Search (TSS) packet classification algorithm used in popular software networking stacks such as the Open vSwitch is robust against low-rate denial-of-service attacks. We present the Tuple Space Explosion (TSE) attack that exploits the fundamental space/time complexity of the TSS algorithm.\ud \ud TSE can degrade the switch performance to 12% of its full capacity with a very low packet rate (0.7 Mbps) when the target only has simple policies such as, "allow some, but drop others". Worse, an adversary with additional partial knowledge of these policies can virtually bring down the target with the same low attack rate. Interestingly, TSE does not generate any specific traffic patterns but only requires arbitrary headers and payloads which makes it particularly hard to detect.\ud \ud Due to the fundamental complexity characteristics of TSS, unfortunately, there seems to be no complete mitigation to the problem. As a long-term solution, we suggest the use of other algorithms (e.g., HaRP) that are not vulnerable to the TSE attack. As a short-term countermeasure, we propose MFCGuard that carefully manages the tuple space and keeps packet classification fast.

Rainfall is a smart contract programming model that allows mutually distrusting parties to manage assets on a distributed ledger. The model consists of a tuple space of authorized facts, and a set of production rules. Rules match on authorized facts, gaining their authority, and produce new facts with a subset of the gained authority. Rainfall allows assets such as crypto currencies to be defined in user code, rather than being baked directly into the ledger framework. Our authorization model also provides a natural privacy model, where not all rules or facts need to be revealed to all parties.

To support fast rule updates in SDN, the Open vSwitch implements Priority Sorting Tuple Space Search (PSTSS) for its packet classifications. Although it has good performance on rule updates, it has a performance concern on table lookups. In contrast, decision tree methods are being actively investigated for high throughput, but they are not able to support fast updates because of rule replications. CutSplit, the state-of-the-art decision tree scheme, provides a novel rule update mechanism by avoiding tree reconstructions. However, its average update time is still two orders of magnitude larger than PSTSS. Meanwhile, existing decision trees are not only unbalanced but also depth unbounded, making them difficult to be optimized on FPGA. In this paper, we present a new decision tree scheme called TabTree, which achieves high performance on both lookups and updates. By mapping rules into tree nodes dynamically, a very limited number of balanced trees with bounded depths can be generated without the trouble of rule replications. Experimental results show that, TabTree has comparable update performance to PSTSS, but it outperforms PSTSS significantly in terms of number of memory accesses for packet classification. Additionally, TabTree is more practical for implementations on FPGA.

To support fast rule updates in SDN, the Open vSwitch uses a variant of Tuple Space Search (TSS) for flow table lookups, which is less efficient than decision trees on packet classifications. In this poster, we present our latest work on building fast flow table engine in Open vSwitch, which achieves high-speed table lookups and fast rule updates simultaneously. By mapping rules into tree nodes dynamically, a very limited TSS-assisted balanced trees can be generated without the trouble of rule replications. Preliminary experimental results show that using ClassBench, our work has comparable update performance to the TSS algorithm in Open vSwitch, while achieving almost an order-of-magnitude improvement on lookup performance over TSS on average.

A challenging aspect of The Internet of Things (IoT) is to provide an architecture that can handle the range of IoT elements ranging from Cloud-based applications to constrained nodes in Wireless Sensor Networks (WSNs). Such an architecture must be scalable, allow seamless operation across networks and devices with little human intervention. This paper describes a set of abstractions and an architecture for the flow of data from sensors to applications supported by a Distributed Hash Table (DHT) and our novel Holistic Peer to Peer (HPP) Application Layer protocol to handle node ids, capabilities, services and sensor data. We show that this architecture can operate in a constrained node by presenting a `C' implementation running on the Contiki3.0 OS and consider the effectiveness of its use of a DHT and its abstractions.

Preprint de: A. Pérez-Vereda, C. Canal, E. Pimentel. Modelling Digital Avatars: a tuple space approach, Science of Computer Programming, vol. 203, Elsevier, 2020, DOI: https://doi.org/10.1016/j.scico.2020.102583. The development of the Internet of Things (IoT) came with the manufacturing of a huge amount of smart things equipped with sensors for making them aware of their environment, and with network connection for allowing remote interaction with them. However, most smart things still lack enough autonomy and context-awareness, hindering them from being people-friendly and actually useful for their users' everyday tasks. IoT devices should take advantage of their sensors and smartness to react automatically to the needs of their users and to provide seamless interactions with them. Within this field, the authors work on the design of Digital Avatars, a mobile computing framework for dynamically programming interactions among smart devices. The framework is based on the virtual profile of the user, which is inferred, stored, and shared by their smartphone. The profile provides a personalized context for running scripts which interact with IoT devices. This way, smartphones become a digital avatar of the user, capable of acting as a personal and seamless interface with their IoT environment. In this work, we present a formalization of Digital Avatars by means of a Linda-based approach with multiple shared tuple spaces. By means of a case study, we show how properties of the systems can be proved, and we briefly describe an implementation of both the Digital Avatars framework and the case study.

Packet classification is one of the essential functionalities of Internet routers in providing quality of service. Since the arrival rate of input packets can be tens-of-millions per second, wirespeed packet classification has become one of the most challenging tasks. While traditional packet classification only reports a single matching result, new network applications require multiple matching results. Ternary content-addressable memory (TCAM) has been adopted to solve the multi-match classification problem due to its ability to perform fast parallel matching. However, TCAM has a fundamental issue: high power dissipation. Since TCAM is designed for a single match, the applicability of TCAM to multi-match classification is limited. In this paper, we propose a cost- and energy-efficient multi-match classification architecture that combines TCAM with a tuple space search algorithm. The proposed solution uses two small TCAM modules and requires a single-cycle TCAM lookup, two SRAM accesses, and several Bloom filter query cycles for multimatch classifications.

Many-field packet classification is a challenging function of the devices in software-defined networking. In this paper, we propose a new algorithm, which partitions a ruleset in a simple way based on non-wildcard portions of the rules. A portion can be a field or a sub-field. The algorithm uses hash tables as the base data structure. In a partition, all the members have a common non-wildcard portion, which is used as the hash key. It means that only a portion of the rules and headers is used for hashing. It simplifies using the hash table for packet classification, which deals with the ternary vectors. The proposed algorithm supports fast updating as a required feature for most of today’s networks. Extensive simulations are conducted to evaluate the algorithm and compare it with well-known algorithms. Results show that the proposed algorithm has a 196% higher throughput and 81% faster update than Tuple Space Search as the base classification algorithm of OpenVSwitch.

In Network Function Virtualization (NFV), various Virtual Network Functions (VNFs) are placed on general-purpose servers. To efficiently operate the NFV system, the placement of VNFs to servers, resource allocation to each VNF, and flow routes are determined carefully and adaptively to handle environmental fluctuations. Our research group has proposed a construction method of service space in virtualized network system, based on biochemical-inspired tuple space model. In this paper, we apply the method to an NFV system to adaptively configure and control VNFs in a distributed manner. We also describe the implementation design of the proposed method, based on the standardization activities to achieve Service Function Chaining. We finally present an application scenario of the proposed method to confirm the effectiveness of the implementation design of the proposed method.

Smart-home systems exhibit "smartness" in home automation systems for contributing to the well-being of house holders. Such systems require support of coordination of its autonomous components in order to achieve its objectives.Due to the inherent advantages of the tuple space model, it becomes the popular choice for coordination in the existing smart-home systems. However, failure resiliency in tuple space coordination has not been investigated in these systems. In fact, these systems consider stable and reliable underlying networks for correct working. Other generalized works on failure handling in the tuple space model address device/network failures with reliability and ordering assumptions, which become impractical for smart-home systems. This paper mitigates such shortcomings by proposing failure-resilient tuple space coordination for smart-home systems, which addresses both device and network failures at the same time in a realistic environment. A hierarchical system architecture is also proposed, where the failure-resilient tuple space coordination is realized. Consequently, robustness of smart-home systems has improved while maintaining system performances. Many cases of single/multiple device and network failures are thoroughly examined to validate correct working of the proposed architecture, which is further compared with its related works to substantiate its improvements.

International audience; Major challenges in the software development of distributed systems are rooted in the complex nature of coordination. Assertions are a practical programming mechanism to improve the quality of software in general by monitoring it at runtime. Most approaches today limit assertions to statements about local states whereas coordination requires reasoning about distributed states. The Peer Model is an event-based coordination programming model that relies on known foundations like shared tuple spaces, Actor Model, and Petri Nets. We extend it with distributed runtime invariant assertions that are specified and implemented using its own coordination mechanisms. This lifts the concept of runtime assertions to the level of coordination modeling. The concept is demonstrated by means of an example from the railway domain.

Packet classification is one of the core functions in present-day networking applications. Various classification algorithms have been developed, including tuple space search (TSS) which is used in the Open vSwitch due to its flexibility and scalability. In order to solve the problem of excessive memory access to the vast rule-set stored off-chip, many algorithms adopt bloom filter (BF) to reduce unnecessary accesses. However, deteriorated false positive and increased collisions at high load ratio may still be a problem. Here in this paper a new tuple pruning based packet classification algorithm is proposed that can achieve much reduced off-chip access per-lookup even at high load by adopting a better compact structure on-chip and Cuckoo hash off-chip. At the same time, we can accelerate the classification rate further by optimizing the search sequence of tuples making it more likely to find the matching rules earlier. Experimental results show that with the proposed mechanism the off-chip table lookup time is only 1/3 to 1/4 of the baseline BF- based scheme.

Coordination languages have been proved very suitable for modeling and programming service-oriented applications. In particular, those based on tuple spaces offer an elegant way of making different components of such applications interact smoothly through the deposit and retrieval of tuples in a shared space. However, in their basic form, these languages only allow one tuple to be put at a time and, when more than one tuple matches a required one, the selection is made non-deterministically. This is obviously too weak to capture popularity or quality measures, which are nevertheless central in service-oriented applications. To that end, we propose an extension of a Linda-like language aiming at promoting the notion of density and, based on De Boer and Palamidessi's notion of modular embedding, study its expressiveness. We prove accordingly that it strictly increases the expressiveness of Linda while keeping the same implementation efficiency. We also compare it with languages based on multiset rewriting, such as Gamma, and establish that, although it is less expressive, it benefits from a much more efficient scheme. Finally we study the hierarchy of the sublanguages induced by considering subsets of tuple primitives and prove that it follows that of the Linda family of languages. We propose an extension of a Linda-like language promoting the notion of density.Based on De Boer and Palamidessi's notion of modular embedding, we study its expressiveness.We prove that it strictly increases the expressiveness of Linda.We prove that it is less expressive than languages based on multi-set rewriting.We study the hierarchy of the sublanguages induced by subsets of tuple primitives.

Security policies are important for protecting digitalized information, control resource access and maintain secure data storage. This work presents the development of a policy language to transparently incorporate aggregate programming and privacy models for distributed data. We use tuple spaces as a convenient abstraction for storage and coordination. The language has been designed to accommodate well-known models such as k-anonymity and \((\varepsilon ,\delta )\)-differential privacy, as well as to provide generic user-defined policies. The formal semantics of the policy language and its enforcement mechanism is presented in a manner that abstracts away from a specific tuple space coordination language. To showcase our approach, an open-source software library has been developed in the Go programming language and applied to a typical coordination pattern used in aggregate programming applications.

We review some results regarding specification, programming and verification of different classes of distributed systems which stemmed from the research of the Concurrency and Mobility Group at University of Firenze. More specifically, we examine the distinguishing features of network-aware programming, service-oriented computing, autonomic computing, and collective adaptive systems programming. We then present an overview of four different languages, namely Klaim, Cows, Scel and AbC. For each language, we discuss design choices, present syntax and semantics, show how the different formalisms can be used to model and program a travel booking scenario, and describe programming environments and verification techniques., In Press

Data availability is a key aspect of modern distributed systems. We discuss an extension of coordination languages based on tuple spaces with programming abstractions for sharing data and guaranteeing availability with different consistency guarantees. Data can be spread over the system according to user-specified replica placement strategies and user-specified consistency requirements. The framework takes care then of low-level management of the replicas, so that the programmer can just focus on the business logic of the application. We advocate that the proposed programming primitives are beneficial for data-oriented applications where different kinds of data may have different needs in terms of availability and consistency.

Packet classification provides a way to discriminate packets and enables many differentiated functionalities. In this chapter, we present how packet classification is accomplished by expressing rules in a classfier. We list the key performance requirements of a packet classification algorithm as the number of memory accesses it needs and the amount of storage it occupies. We then present a number of algorithms that are extensions of trie based algorithms used for IP address lookup. We also outline various approaches for classifying a packet in an arbitrary number of dimensions: divide and conquer, cross-producting, tuple space, and decision tree. We then describe algorithms using each approach. Finally, we conclude the chapter with a discussion of hardware solutions using TCAMs.

Software switch has emerged as a critical component in software defined networking and network virtualization areas. Open vSwitch (OvS) is a widely used software switch which uses tuple space search algorithm for packet classification, and an exact match cache (EMC) for caching most frequently used flows. In this paper, we propose two new optimizations for OvS to further improve its performance and scalability. First aims to completely remove the sequential search overhead of the tuple space search layer of OvS, and second is a dynamic cache insertion optimization for the EMC to improve EMC effectiveness. We show that the optimizations can improve OvS's throughput by up to 3.5X for millions of active flows.

Conceptually, tuple spaces are shared memory objects that provide operations to store and retrieve ordered sets of data, called tuples. Tuples stored in a tuple space are accessed by the contents of their fields, working as an associative memory. Although there are some proposals for secure tuple spaces, accessing tuples through field contents makes these systems susceptible to attacks that could impair user and data privacy, since servers must access tuple data. In order to deal with these limitations and provide privacy in the tuple space model, this paper proposes some extensions to DepSpace, a tuple space system that implements dependability and security properties through a set of mechanisms that are not enough to ensure privacy. The resulting system provides privacy and, at the same time, allows tuple selection/matches similar to the traditional insecure model, i.e., it does not constraint the matching possibilities. The main problem to be addressed is that servers must select tuples based on their contents without knowing them. The proposed solution uses robust cryptographic schemes, as order-preserving encryption and homomorphic encryption, to provide this functionality without revealing the tuple contents. An analysis concerning security aspects of DepSpace is presented, as well as the benefits of the proposed solutions. A set of experiments, executed with an implementation of the proposed protocols, shows the feasibility of the proposed solutions and shed some light on both the behavior of the system and the costs to provide privacy in the tuple spaces model.

With the fast development of Software Defined Networking (SDN) and network virtualization, software-based network virtual switches have emerged as a critical component to provide network services to VMs. Among virtual switches, Open vSwitch (OvS) is an open source virtual switch implementation commonly used and well-studied. Using Data Plane Development Kit (DPDK) with OvS to bypass the OS kernel and process packets in userspace provides tremendous performance benefits on general purpose platforms. Integrated GPUs, residing on the same die with the CPU on general purpose platforms, offering many advanced features such as on-chip interconnect CPU-GPU communication, and sharing physical/virtual memory, become a promising additional compute resource to further accelerate the OvS process. In this paper, we design and implement an inline GPU assisted OvS architecture, via offloading the expensive tuple space search to GPU and balancing switching processing between CPU and GPU. We evaluated the performance on an Intel® Xeon® processor of the E3-1575M v5 product family (code-name Skylake) with an integrated GT4e GPU. The results show that our proposed architecture improved the OvS throughput by 3x, compared to the optimized CPU-only OvS-DPDK implementation.

Highly dynamic distributed applications often require flexible coordination among several autonomous components. Space-based middleware provides a suitable, data-driven coordination paradigm for such scenarios, where distributed peers exchange data and commands in a scalable and decoupled way using shared tuple spaces. In its basic form, such a middleware supports access to a data storage and (blocking) queries on the stored tuples. However, in many cases the injection of additional server-side logic would ease the development of complex applications, as the semantics of the tuple space can be adapted to domain-specific requirements.This paper introduces reactive programming features for XVSM, a space-based middleware that enhances the tuple space concept with powerful coordination mechanisms. We present a comprehensive extension mechanism that supports the execution of application logic in reaction to composite and time-based events. As an example for the feasibility of the approach, we provide a bootstrapped solution for a leasing mechanism that manages the lifetime of data in the space.

Packet classification is an important part of many networking devices, such as routers and firewalls. Software-defined networks require online packet classification where classifiers receive a mixed stream of packets to classify and rules to update and both operations must be completed as efficiently as possible without knowledge of future operations. This rules out many classifiers, such as HyperCuts, HyperSplit, and their derivatives, which do not support fast updates. We build upon Tuple Space Search, the packet classifier used by Open vSwitch, to create TupleMerge. TupleMerge improves upon Tuple Space Search by combining hash tables which contain rules with similar characteristics. This greatly reduces classification time by producing fewer tables. We compared TupleMerge to PartitionSort, the current state-of-the-art online packet classifier, on rulelists generated by ClassBench. TupleMerge outperforms PartitionSort at both classifying packets and rule update. Specifically, on average, it is 34.2% faster at classifying packets and 30% faster at updating rules than PS.

none 4 no Available online 20 September 2016 Rollback is a fundamental technique for ensuring reliability of systems, allowing one, in case of troubles, to recover a past system state. However, the definition of rollback in a concurrent/distributed scenario is quite tricky. We propose an approach based on the notion of causal-consistent reversibility: any given past action can be undone, provided that all the actions caused by it are undone as well. Given that, we define a rollback as the minimal causal-consistent sequence of backward steps able to undo a given action. We define the semantics of such a rollback operator, and show that it satisfies the above specification. The approach that we present is quite general, but we instantiate it in the case of μKlaim, a formal coordination language based on distributed tuple spaces. We remark that this is the first definition of causal-consistent rollback in a shared-memory setting. We illustrate the use of rollback in μKlaim on a simple, but realistic, application scenario. open Giachino, Elena; Lanese, Ivan; Mezzina, Claudio Antares; Tiezzi, Francesco Giachino, Elena; Lanese, Ivan; Mezzina, Claudio Antares; Tiezzi, Francesco

Workflows have been successfully applied to express the decomposition of complex scientific applications. This has motivated many initiatives that have been developing scientific workflow tools. However the existing tools still lack adequate support to important aspects namely, decoupling the enactment engine from workflow tasks specification, decentralizing the control of workflow activities, and allowing their tasks to run autonomous in distributed infrastructures, for instance on Clouds. Furthermore many workflow tools only support the execution of Direct Acyclic Graphs (DAG) without the concept of iterations, where activities are executed millions of iterations during long periods of time and supporting dynamic workflow reconfigurations after certain iteration. We present the AWARD (Autonomic Workflow Activities Reconfigurable and Dynamic) model of computation, based on the Process Networks model, where the workflow activities (AWA) are autonomic processes with independent control that can run in parallel on distributed infrastructures, e. g. on Clouds. Each AWA executes a Task developed as a Java class that implements a generic interface allowing end-users to code their applications without concerns for low-level details. The data-driven coordination of AWA interactions is based on a shared tuple space that also enables support to dynamic workflow reconfiguration and monitoring of the execution of workflows. We describe how AWARD supports dynamic reconfiguration and discuss typical workflow reconfiguration scenarios. For evaluation we describe experimental results of AWARD workflow executions in several application scenarios, mapped to a small dedicated cluster and the Amazon (Elastic Computing EC2) Cloud.

Extracting tuples from HTML pages has been an important issue in various web applications. Commercial tuple extraction systems have enjoyed some success to extract tuples by regarding HTML pages as tree structures and exploiting XPath queries to find attributes of tuples in the HTML pages. However, such systems would be vulnerable to small changes on the web pages. In this paper, we propose a robust tuple extraction system which utilizes spatial relationships among elements rather than the XPath queries. Spatial information (e.g., 2-D coordinates) of elements are maintained in the DOM tree when a web page is rendered in a browser. Our system regards elements in the rendered page as spatial objects in the 2-D space and executes spatial joins to extract target elements. Since humans also identify an element in a web page by its relative spatial location, our system extracting elements by their spatial relationships could possibly be as robust as manual extraction. To specify and execute spatial joins, we propose a new query language, RAQuery, based on topological relationships between any spatial objects in the 2-D space. We then propose spatial join algorithms that efficiently process the RAQuery using novel notions of group match and prunable relation group. We next propose a tuple construction algorithm to build tuples from the extracted elements obtained by the spatial joins, which can construct tuples even when there are no boundary HTML elements specified for the tuples in the web page. Extensive experimental results using real HTML pages confirm that our solutions are far more robust than existing tuple extraction systems without sacrificing performance.

Packet classification is one of the main core functions of networking. With the advent of Software-Defined Networking, packet classification has become more challenging by introducing many-field rulesets. In this paper, we propose an algorithm, Clustering-Based Packet Classification (CBPC), which divides ruleset into some clusters using a new hybrid clustering method, based on an innovative bit-level view. Those rules that have more common wildcard and non-wildcard bit positions are put into the same cluster. Each cluster uses common non-wildcard positions of its rules to produce keys for a hash table insertion and query stages. This makes possible to use hash tables without involving difficulties with inserting and querying ternary vectors, because our algorithm converts it to simple binary operations. In fact, we ignore a portion of information of the rules in key production for the hash tables. It overcomes the problem of extending wildcards to all of the possible values. It is true that some information is lost but it is covered by full matching at the hash table entries. We propose two versions for CBPC, online and offline. The online version supports update, which is an important requirement for today's packet classification algorithms. The proposed algorithm is evaluated and compared with some well-known and state-of-the-art algorithms by extensive simulations. The results show that Online-CBPC achieves 197% higher throughput and 64% faster update than Tuple Space Search, OpenVSwitch standard algorithm, while using almost the same amount of memory.

Mechanisms for distributed coordination are used in the development of many distributed systems and, generally, are implemented on top of coordination infrastructures, such as tuple spaces. Although tuple spaces provide the coordination functionalities, a recent study showed that extensibility is fundamental for performance. The main idea behind extensibility is to allow the servers, supporting the coordination infrastructure, to access and process coordination information. Consequently, it is not necessary to move information from servers to clients or to reprocess requests due to concurrency. Unfortunately, existing proposals for extensible distributed coordination do not provide security and privacy once servers access data in plaintext. This work uses robust cryptographic schemes recently integrated into DepSpace , a tuple space implementation, to propose secure protocols for coordination with and without extensions. Experiments compare the proposed solutions and consider also the proposed protocols without security and privacy, showing that extensible coordination significantly improves system performance even using costly cryptographic operations.

In Ambient Intelligence environments machines proactively and transparently work on behalf of humans. The nature of these machines and the communication protocols they use is multifarious. Therefore, the applications running on top of them remarkably demand interoperability. The Triple Space Computing (TSC) paradigm addresses that problem by sharing information represented in a semantic format through a common virtual space. As long as application developers use standard ontologies, different applications using the same spaces will interact automatically. The focus of this paper is to present Otsopack, a fully distributed TSC middleware designed to meet the needs of mobile and resource constrained devices. Otsopack defines a simple HTTP interface for the TSC operations. This interface focuses on simplicity and modularity, so that two implementations that support different modules can still interact. To assess the middleware we provide time and load measurements, and we analyze two independent implementations.

In this paper we introduce a new Platform-as-a-Service cloud environment that combines the LINDA coordination language, an in-memory key-value store, with functional programming to facilitate efficient execution of tenant plugins and applications. In the implementation a tuple space plays a central role in introducing deterministic services for basic parallel programming, including message passing, persistent infinite message pools and transactions. Redis, a key-value store, serves as the in-memory tuple space that glues together parallel constructs (i.e. skeletons) of formerly monolithic business applications to form an elastic distributed application. Although functional programming languages have adopted new runtime technology to achieve parallel execu- tion, which is mostly focused on threads, it rarely offers an obvious way to match functions to threads. We find that the LINDA tuple space and its coordination model offers a general purpose paradigm to tackle synchronisation issues that ties into both domains of computing clouds: computation through supporting common skeletons and big data (analytics) through serving as an in-memory data grid.

Data analytics applications handle large data sets subject to multiple processing phases, some of which can execute in parallel on clusters, grids or clouds. Such applications can benefit from using MapReduce model, only requiring the end-user to define the application algorithms for input data processing and the map and reduce functions, but this poses a need to install/configure specific frameworks such as Apache Hadoop or Elastic MapReduce in Amazon Cloud. In order to provide more flexibility in defining and adjusting the application configurations, as well as in the specification of the composition of the application phases and their orchestration, the authors describe an approach for supporting MapReduce stages as sub-workflows in the AWARD framework (Autonomic Workflow Activities Reconfigurable and Dynamic). The authors discuss how a text mining application is represented as a complex workflow with multiple phases, where individual workflow nodes support MapReduce computations. Access to intermediate data produced during the MapReduce computations is supported by a data sharing abstraction. The authors describe two implementations of this abstraction, one based on a shared tuple space and another based on an in-memory distributed key/value store. The authors describe the implementation of the framework, a set of developed tools, and our experimentation with the execution of the text mining algorithm over multiple Amazon EC2 (Elastic Compute Cloud) instances, and report on the speed-up and size-up results obtained up to 20 EC2 instances and for different corpus sizes, up to 97 million words.

International audience; Disconnected mobile ad hoc networks (or D-MANETs) are partially or intermittently connected wireless networks, in which continuous end-to-end connectivity between mobile nodes is not guaranteed. The ability to self- form and self-manage brings great opportunities for D-MANETs, but developing distributed applications capable of running in such networks remains a major challenge. A middleware system is thus needed between network level and application level in order to ease application development, and help developers take advantage of the unique features of D-MANETs. In this paper, we introduce a peer-to-peer JavaSpaces implementation that we specifically designed for D-MANETs, and with which pre-existing or new JavaSpaces-based applications can be easily deployed in such networks.

The tuple space abstraction provides an easy-to-use programming paradigm for distributed applications. Intuitively, it behaves like a distributed shared memory, where applications write and read entries (tuples). When deployed over a wide area network, the tuple space needs to efficiently cope with faults of links and nodes. Erasure coding techniques are increasingly popular to deal with such catastrophic events, in particular due to their storage efficiency with respect to replication. When a client writes a tuple into the system, this is first striped into k blocks and encoded into \(n > k\) blocks, in a fault-redundant manner. Then, any k out of the n blocks are sufficient to reconstruct and read the tuple. This paper presents several strategies to place those blocks across the set of nodes of a wide area network, that all together form the tuple space. We present the performance trade-offs of different placement strategies by means of simulations and a Python implementation of a distributed tuple space. Our results reveal important differences in the efficiency of the different strategies, for example in terms of block fetching latency, and that having some knowledge of the underlying network graph topology is highly beneficial.

The paper presents MorphicLib, a new partial homomorphic cryptography library written in Java that can be used to implement a wide-range of applications. The paper shows the use of the library with the HomomorphicSpace coordination service. This service is a tuple space that stores encrypted tuples but still supports operations like returning tuples with values within a certain range.

With an increasing number of service providers in the cloud market, the competition between these is also increasing. Each provider attempts to attract customers by providing a high quality service with lowest possible cost and at the same time trying to make profit. Often, cloud resources are advertised and brokered in a spot market style, i.e., traded for immediate delivery. This paper proposes an architecture for a brokerage model specifically for multi-cloud resource spot markets that integrates the resource brokerage function across several cloud providers. We use a tuple space architecture to facilitate coordination. This architecture supports specifically multiple cloud providers selling unused resources in the spot market. To support the matching process by finding the best match between customer requirements and providers, offers are matched with regard the lowest possible cost available for the customer in the market at the time of the request. The key role of this architecture is to provide the coordination techniques built on a tuple space, adapted to the cloud spot market.

Smart spaces provide a shared view of dynamic resources and context-aware services within a distributed application. Smart-M3 is an open-source platform that implements the smart space concept. It inherits the tuplespace and publish/subscribe asynchronous communication models, and agents (Smart-M3 knowledge processors, KPs) cooperate sharing the common smart space. A Smart-M3 semantic information broker (SIB) maintains the smart space in low-level ontological terms of triples. Smart Space Access Protocol (SSAP) is used for session management and triple governance transactions. This paper considers the session between KP and SIB in the Smart-M3 applications. First, SSAP session will be studied. Second, a new SmartSlog session scheme will be introduced. It operates with such ontological concepts as a class, a property, and an individual and extends the capabilities of SSAP session. New session scheme is based on SSAP session and can manipulates with many SSAP sessions by combining them in one session. All data are shared between SSAP sessions and it allows to work with different smart spaces as with one on KP side. The new session scheme is partially implemented in SmartSlog ontology library.

In recent years, plenty of research has been done related to the methods of composition of web services. Notwithstanding much effort, it seems that this technology has a long way till it attains perfection. In this research, providing a suggestive model, we performed service orchestration semi-centrally. To do this, we need to group web services. We created groups or clusters of web services and put services in appropriate groups, by this way, the number of control flow and data flow notifications decreases considerably. For each group a controller and a Tuple space is considered and the controller is responsible for invoking services of that group Simulation results show that service orchestration can be influential in decreasing the amount of traffic, especially in composite services with a high level of communication in their component services. In addition, a decrease in the level of distribution in service orchestration can improve capability of execution monitoring and failure compensation.

The content aware (CA) packet classification and processing at network level is a new approach leading to significant increase of delivery quality of the multimedia traffic in Internet. This paper presents a solution for a new multi-dimensional packet classifier of an edge router, based on content - related new fields embedded in the data packets. The technique is applicable to content aware networks. The classification algorithm is using three new packet fields named Virtual Content Aware Network (VCAN), Service Type (STYPE), and U (unicast/multicast) which are part of the Content Awareness Transport Information (CATI) header. A CATI header is inserted into the transmitted data packets at the Service/Content Provider server side, in accordance with the media service definition, and enables the content awareness features at a new overlay Content Aware Network layer. The functionality of the CATI header within the classification process is then analyzed. Two possibilities are considered: the adaptation of the Lucent Bit vector algorithm and, respectively, of the tuple space search, in order to respond to the suggested multi-fields classifier. The results are very promising and they prove that theoretical model of inserting new packet fields for content aware classification can be implemented and can work in a real time classifier.

In this paper, a method for fast processing of data stream tuples in parallel execution of continuous queries over a multiprocessing environment is proposed. A copy of the query plan is assigned to each of processing units in the multiprocessing environment. Dynamic and continuous routing of input data stream tuples among the graph constructed by these copies (called the Query Mega Graph) for each input tuple determines that, after getting processed by each processing unit (e.g., processor), to which next processor it should be forwarded. Selection of the proper next processor is performed such that the destination processor imposes the minimum tuple latency to the corresponding tuple, among all of the alternative processors. The tuple latency is derived from processing, buffering and communication time delay which varies in different practical parallel systems. Parallel system architectures that would be suitable as the desired multiprocessing environment for employing the proposed Dynamic Tuple Routing (DTR) method are considered and analyzed. Also, practical challenges and issues for the proper parallel underlying system are discussed. Implementation of the desired parallel system on multi-core systems is provided and used for evaluating the proposed DTR method. Evaluation results show that the proposed DTR method outperforms similar method such as the Eddies in terms of tuple latency, throughput and tuple loss.

Gamma Calculus is an inherently parallel, high-level programming model, which allows simple programming molecules to interact, creating a complex system with minimum of coding. Gamma calculus modeled programs were written on top of IBM’s TSpaces middleware, which is Java-based and uses a “Tuple Space” based model for communication, similar to that in Gamma. A parser was written in C++ to translate the Gamma syntax. This was implemented on UHD’s grid cluster (grid.uhd.edu), and in an effort to increase performance and scalability, existing Gamma programs are being transferred to Nvidia’s CUDA architecture. General Purpose GPU computing is well suited to run Gamma programs, as GPU’s excel at running the same operation on a large data set, potentially offering a large speedup.