Packet forwarding in Software-Defined Networks (SDN) using OpenFlow [5] relies on a centralized network controller to enforce network policies expressed as forwarding rules. Rules are deployed as sets of entries into the tables of network devices. Deploying them onto heterogeneous set of devices is strongly bounded by the respective table constraints (size, lookup time, etc.) and forwarding pipelines. Hence, it is important to minimize the overall number of entries in order to both reduce resource consumption and speed up the search. In this work, we present a compression mechanism for rules of diverging origins that minimizes the number of entries. Since it exploits the semantics of rules and entries, our compiler fits a heterogeneous landscape of network devices. We evaluated implementations of our compiler for both software and hardware switches on a realistic test bed.

Packet forwarding in Software-Defined Networks (SDN) relies on a centralised network controller which enforces network policies expressed as forwarding rules. Rules are deployed as sets of entries into network device tables. With heterogeneous devices, deployment is strongly bounded by the respective table constraints (size, lookup time, etc.) and forwarding pipelines. Hence, minimising the overall number of entries is paramount in reducing resource consumption and speeding up the search. Moreover, since multiple control plane applications can deploy own rules, conflicts may occur. To avoid those and ensure overall correctness, a rule validation mechanism is required. Here, we present a compilation mechanism for rules of diverging origins that minimises the number of entries. Since it exploits the semantics of rules and entries, our compiler fits a heterogeneous landscape of network devices. We evaluated compiler implementations on both software and hardware switches using a realistic testbed. Experimental results show a reduction in both produced table entries and forwarding delay.

Openflow is a key step in abstracting network functions by separating the control and the forwarding plane. However, even with continuous innovation and evolution of the protocol, its adoption on forwarding device targets remains laborious and time consuming. In this paper, we present a semantic-based approach to packet forwarding design that tailors flow classification to the underlying switch device. Its key idea consist in streamlining flow classification through rule compiling and thus to optimize forwarding operations and improve switch resources usage. The compiling itself exploits a rule grouping gleaned through Frequent Pattern Mining and Network Calculus in optimizing flow classification w.r.t. the switch pipelined architecture.

The management of the configuration of network devices is a complex process, due to both the number of devices and parameters to take into consideration, and most importantly to the widely varying ways in which such parameters can be queried and modified on each device. Each equipment vendor provides its own command-line interface or management protocol where parameters are structured in a different way, and even multiple equipments from the same vendor may need to be interacted with differently. In this paper, we present a generic data model for configuration information of network devices that takes into account vendor and version heterogeneity. Ultimately, a configuration query engine will allow a user to pinpoint a specific, abstract configuration parameter, and be given the proper sequence of commands to query that parameter on a device of given vendor and operating system version.

Formal concept analysis (FCA) is a knowledge discovery approach aimed at extracting conceptual hierarchies from data. Due to the exhaustiveness of its output, a typical FCA-based solution would filter large parts thereof using an ad-hoc quality criterion. In this paper, we present an FCA-based solution to an optimization problem from network traffic control that is akin to information retrieval (queries set up to measure specific traffic, i.e., packet flows). The goal is to minimize the number of counters used to answer a given query set. Our solution explores a contextual substructure of the (flows x flow descriptors) lattice, that we called the projection subsemilattice: The optimal set of counters is shown to correspond to a class of concepts from the semilattice. We present an effective computing method and provide empirical evidence of its performances on realistic network settings.

Openflow is a step towards a more flexible data plane. In Openflow-based deployments, packet forwarding model relies on a set of pipelined tables. However, supporting multiple hardware tables is challenging while having serious limitations. In this paper, we investigate a novel approach to packet forwarding design that tailors Openflow forwarding paths according to the underlying hardware. Its main goal is to provide an optimal mapping of entries to physical search structures. To that end, conceptual abstractions are used in devising a semantically rich and high-performance packet forwarding.

Delivering high performance when several virtual nodes share the same physical resources requires finding the optimal resource allocation between them. In the context of Software Defined Network (SDN) and Network Virtualization, data plane requires the design of a new and more flexible flow packet processing. Virtual nodes involves several packet processing functions such as search operations in different data structures, processing the packets by modifying their respective contents and buffering them. Each packet processing requires a set of shared resources. If there is a conflict for a given resources, resource reassignment strategy is needed to ensure the continuity of the processing and solve resource congestion in accordance with the available hardware resources. In this paper, we propose a resource allocation strategy to share fairly the network processor resources. It is based on network calculus model and game theory algorithms. This strategy maps dynamically the suitable resources according to virtual nodes processing. In our implementation, we focus on packet processing tasks in regard to OpenFlow forwarding model within several processors to reassign resources.

Configuration validation is the process of automatically assessing whether the various configuration parameters of a network's devices are set to appropriate values according to a set of formal constraints given beforehand. Virtually all automated validation solutions presented to date assume a centralized and complete knowledge of the network's configuration to perform their analysis. We present an algorithm that automatically performs this evaluation, while still requiring the need for a centralized point of verification, this algorithm can analyze the constraints to evaluate, and reduce the amount of data that needs to be transferred to that central location, pushing as much of the evaluation of each constraint locally on each device.

Server virtualization is usually used to consolidate multiple virtual machines in the same physical server for power consumption and cost reduction purposes. On the other hand, several virtual machines' killer applications are delay sensitive since they interact with the user in real time such as IP telephony signalling, thin clients and video. Therefore, server virtualization can be exploited to run VMs on servers that provide the lowest delay to their users. In this paper, we consider the case of a virtualized IP Multimedia Subsystems. As a first optimization objective, assigning VMs to lowest delay servers will consolidate them in very few servers serving high density regions. However, it will create overloaded hot spot servers. Thus, in order to provide a globally higher number of VMs to servers mappings, we allow delay-sensitive applications to tolerate a delay up to a given threshold. Consequently, we will be able to provide an option to optimize a second objective that consists of load balancing over a higher number of servers. We show that this optimization problem is NP complete. We formulate the problem using a weighted bipartite matching graph and then we solve it using a modified Hungarian method. Results show that our proposed algorithms provide near-optimal solutions in short time.

In a recent effort to push forward the powerful concept of software defined networks, OpenFlow has gained a lot of popularity as a practical approach to split the data and the control planes by standardizing an open interface that allow remote software controllers to dictate the forwarding behavior of network devices. The latest flexible version 1.1 of OpenFlow is limited to software forwarding plane implementations. In order to deliver high performance, we implement an OpenFlow v1.1 hardware forwarding plane based on network processors. Delivering the optimal performance requires finding the optimal mapping of OpenFlow tasks to hardware resources which is already known as an NP-hard combinatorial problem. In our work, we propose a performance model that helps choose a better mapping without the burden of implementing and comparing all possible mappings on network processor. Our model assumes that the performance bottleneck of the hardware forwarding pipeline comes from the lookup tasks. This is generally the case of OpenFlow lookup tasks based on more than 14 tuple headers and requiring high latency external memories in order to provide a large number of possible flow entries. Our model, validated using real hardware implementations comparisons, shows that the lookup tasks that use the same external memories in the same pipeline are not worth parallelizing. In fact, mapping them to different parallel processing elements will only increase the response time of the lookup memory which will slow down the forwarding pipeline.

Configuration information in network devices is stored in an internal data structure that can be accessed through various means. However, the exact organization of the parameters, and therefore the actual way of reaching them, does not necessarily reflect a semantically sound view of the configuration operations in all situations. In this paper, we propose the use of configuration dependency rules to provide a semantic virtualization of the parameters. We show how this virtualization can be superimposed with minimal interference over current configuration protocols, taking Netconf as an example.

Configuration Logic (CL) is a formal language that allows a network engineer to express constraints in terms of the actual parameters found in the configuration of network devices. There exists an efficient algorithm that can automatically check a pool of devices for conformance to a set of CL constraints; moreover, this algorithm can point to the part of the configuration responsible for the error when a constraint is violated. A CL validation engine has been integrated into a network management tool called ValidMaker. We show on a simple use case scenario based on Virtual Local Area Networks how representative formal constraints can be expressed with CL and efficiently validated with ValidMaker.

In today's networks, a node usually has a static role that cannot be easily changed without an expensive upgrade. In MPLS architecture, despite the flexible forwarding data plane not tied to a single forwarding technology, each MPLS node has to be dedicated for a specific role depending on its position in the edge or the core of the MPLS network domain. This paper proposes an approach to address the flexibility of an MPLS node to play multiple roles for different MPLS domains built on top of an underlying OpenFlow-enabled physical network. The pipelined approach through tables introduced in the version 1.1 and later of the OpenFlow specification allows the change of the packet processing behavior by just updating the memory structures - such as the TCAM and hash tables. It exploits the power of the OpenFlow rules-based paradigm to demonstrate the high level programmability to achieve the deossification of an MPLS infrastructure. In order to validate our proposal, we have implemented our approach over a 100Gbps switch box built on network processors and tested it with three applications to evaluate its flexibility. The results show that the local software to hardware update of a Label Switched Path (LSP) can be made in 2.2ms, in average, and the deployment of a Label Switched Router (LSR) application with 400 labels takes only 392.5ms.

Vehicular Ad hoc Networks (VANETs) are a special type of Mobile Ad hoc Networks (MANETs), made by vehicles communicating among themselves, and by vehicles communicating to devices located in the margins of roads and highways. The main characteristic of a VANET is the high speed of network nodes – that can go up to 200 km/h –, and that impacts directly on the ability the network has to deliver data, given we might have a network formed for just a small amount of time. It has been shown in several works that ant-based routing can be successfully applied to both wired and wireless networks. This work proposes Ant Colony Optimization (ACO) procedures that take advantage of information available in vehicular networks – such as the vehicles' position and speed –, in order to design an ant-based algorithm that performs well in the dynamics of such networks. The authors have also adapted the Dynamic MANET On-demand (DYMO) routing protocol to make use of the ACO procedures proposed in this paper, and the resulting bio-inspired protocol, MAR-DYMO, had its performance evaluated in an urban scenario and compared against a few other routing protocols. The obtained results suggest that making use of environmental information can make ACO algorithms more suitable for routing in vehicular ad hoc networks.

Virtualization gives different types of Mobile Virtual Network Operators (MVNO) the possibility to deploy their components more rapidly and at a lower cost. In this paper, we propose five scenarios for the virtualization of the IP Multimedia Subsystem (IMS) components and compare them to the non virtualized one. To assess the service quality of the signaling system in our proposed virtualized scenarios, we consider three signaling procedures, namely registration, voice session, and data session. This study investigates the delay for each signaling procedure as a performance metric. By applying a Markovian generic model to our scenarios, we calculate the pre-established performance metrics. Based on the comparison of the delays of each virtualized scenario with those of the non-virtualized one, we then evaluate the utility function, by which we mean the improvement or degradation of virtualized delays. Finally, we deduce the best scenario that ensures a good service quality for each MVNO type. The main results show that the virtualized Proxy Call Session Control Function (P-CSCF) represents the most efficient scenario for the MVNO voice type, while the scenario in which all CSCF components are virtualized provides the best results for the data type.

Most works that extend workflow validation beyond syntactical checking consider constraints on the sequence of messages exchanged between services. These constraints are expressed only in terms of message names and abstract away their actual data content. We provide examples of real-world “data-aware” Web service constraints where the sequence of messages and their content are interdependent. To this end, we present {\rm CTL}\hbox{-}{\rm FO}^+, an extension over Computation Tree Logic that includes first-order quantification on message content in addition to temporal operators. We show how {\rm CTL}\hbox{-}{\rm FO}^+ is adequate for expressing data-aware constraints, give a sound and complete model checking algorithm for {\rm CTL}\hbox{-}{\rm FO}^+, and establish its complexity to be PSPACE-complete. A “naive” translation of {\rm CTL}\hbox{-}{\rm FO}^+ into CTL leads to a serious exponential blowup of the problem that prevents existing validation tools to be used. We provide an alternate translation of {\rm CTL}\hbox{-}{\rm FO}^+ into CTL, where the construction of the workflow model depends on the property to validate. We show experimentally how this translation is significantly more efficient for complex formulas and makes model checking of data-aware temporal properties on real-world Web service workflows tractable using off-the-shelf tools.

Most works that extend workflow validation beyond syntactical checking consider constraints on the sequence of messages exchanged between services. However, these constraints are expressed only in terms of message names and abstract away their actual data content. Using the context of the User-controlled Lightpath initiative (UCLP) hosted by the CANARIE consortium, we provide examples of real- world "data-aware" web service constraints where the sequence of messages and their content are interdependent. We present CTL-FO+, an extension over Computation Tree Logic that includes first-order quantification on state variables in addition to temporal operators. We show how CTL- FO+is adequate for expressing data-aware constraints, give a complete model checking algorithm for CTL-FO+and establish its complexity to be PSPACE-complete. This makes using CTL-FO+for validating workflow properties no harder than using the Linear Temporal Logic (LTL) already used by some web service tools. Finally, we show how the modelling of data-aware properties is an increase in expressiveness that cannot be efficiently simulated by these tools.

The development of networking and client/server systems over the Internet had led to many collaborative work software applications. To extend the graphic design collaborative platforms focused on 3D artistic characters, the Articiel project is based on the Articiel collaborative platform that is a client-server application on the World Wide Web(WWW) based on a SOA architecture. This platform is including the essential functionalities needed by communities of distantly located artists to create and modify 3D characters or graphic animations. The Articiel platform collaborative functionalities are: messaging, agenda, storing and retrieving artists' projects and contributions. Previous work has proved the usability of the Articiel platform by the programming of a Maya plugin who was calling the platform functionalities through its Web services. The aim of this paper is to show a new contribution algorithm and the technical innovations resulting of the plugin conversion from Maya to Blender.

Querying and efficiently validating properties on labelled tree structures has become an important part of research in numerous domains. In this paper, we show how a fragment of XPath called configuration logic (CL) can be embedded into computation tree logic. This framework embeds into CTL a larger subset of XPath than previous work and in particular allows universally and existentially quantified variables in formulas. Finally, we show how the variable binding mechanism of CL can be seen as a branching-time equivalent of the "freeze" quantifier

This paper presents a new structure-preserving method of sampling self-similar traffic with direct applications to network monitoring and resource provisioning. Predicting the bandwidth required by upcoming traffic plays a key role for providing an efficient and intelligent resource provisioning, especially in the context of IP over WDM. To achieve this, we are proposing a periodic sampling method (called maximum-based sampling) that picks one measurement during a sampling interval of size T. Mathematical analysis and simulation results demonstrate that the proposed maximum-based sampling method preserves the self-similarity property of the original traffic over many time scales. The LMMSE (linear minimum mean square error) prediction method is used for traffic forecast. The numerical results show that the accuracy of traffic prediction performed on the proposed sampled process remains stable for different sampling interval size T.

We introduce a logical formalism for describing properties of configurations of computing systems. This logic of trees allows quantification on node labels, which are modalities containing variables. We explain the motivation behind our formalism and give both a classical semantics and a new equivalent one based on partial functions on variables.

There is a growing need for e2e lightpaths for high volume data transferring applications such as GridFTP and SAN. They wish to dynamically deploy lightpaths over multiple management domains. Research, sponsored by Canarie Incorporated, is underway to enable "customer-empowered networks" and to experiment them with the Canadian research network CA*Net4. New signaling and control approaches using Web services have been proposed. One difficulty is that each domain must retain the control of their optical network infrastructure and ensure proper allocation of optical resources. Hence, it is important that the signaling takes into account the management constraints imposed by the different domains. This paper presents a policy-based approach for user-controlled lightpath provisioning. The work builds on the research around the new signaling approaches for realizing customer-empowered networks. We present an architecture based on Web Services allowing users or Grid applications to establish e2e lightpaths over multiple autonomous systems. To tackle the problem of admission control and to address the resource allocation issue, we developed policy restricted signaling which allows customers to reserve lightpaths over multiple domains while ensuring that management rules of each domain are enforced. The signaling has been implemented and the experiment on a small network composed of Cisco equipment proves the viability of our approach.

One of the primary goals of the CA*net 4 network is to provide end users with the ability, on a peer-to-peer basis, to provision, manage, and control the routing of their own lightpaths across the network without the need to signal or request services from any central network management authority or server. A novel approach to such end-user management and control of lightpaths is described, which uses Web services architecture and grid technology.

The simple network management protocol (SNMP) was introduced in 1988. The initial version (SNMPv1) is still widely implemented, deployed, and used. SNMPv3 is now in its final stages of standardization. SNMPv3 allows new capabilities for open, interoperable, and secure management on the Internet environment. SNMPv3 builds on SNMPv1 and v2 to include methods for security (authentication, encryption, and privacy), and a new administrative framework. From a practical perspective, the SNMPv3 architecture must allow the evolution of the system to consider different versions of SNMP, different applications, and different security models. We present an implementation model for SNMPv3 that keeps the simplicity of SNMPv1, while at the same time making it possible to evolve the framework to address different security needs and different configurations. The implementation model is an abstract view of the implementation that represents the building blocks required for any realization of agents, platform, proxies, etc. We explain how the model with a modular approach can allow interoperability with other SNMP applications. The model uses the interfaces as defined by the RFC to achieve the architectural goals (extensibility, reusability, etc.) and to simplify the module construction. An implementation was done at UQAM and it uses Java to create the modular reusable components.

Two important achievements in the network management area motivated the work presented in this paper. The first one is the wide acceptance of the policy concept and its introduction as a means for driving management procedures. The second concerns the capabilities brought by the version 3 of the SNMP protocol for configurable and secure network management. The deployment of SNMPv3 at equipment level allows henceforth concretizing the policy-driven management, refining enterprise policies and enforcing them down the managed network resources. This paper aims at integrating the policy concept into the SNMPv3 framework. It proposes a set of rules to map authorization policies to the VACM (view based access control model) standardized as part of the SNMPv3 management framework. Policy attributes are maintained in a configuration database local to the SNMPv3 entity and a new application is incorporated into the SNMPv3 entity to perform the mapping. This will ultimately allow manager and management applications to enforce enterprise authorization policies independently of the security model(s) implemented by SNMPv3 entities.

The Simple Network Management Protocol (SNMP) was introduced in 1988 and is still widely implemented, deployed, and used. SNMPv3 is now in its final stages of standardization. From a practical perspective, we need to consider how telecommunication systems can be extended to consider different versions of SNMP, different applications and different security models. We present an object-oriented implementation of SNMPv3 to create a flexible product architecture. This architecture allows one to easily interface with other modules as required. We also describe network object models and relationships required for the architecture. The implementation uses Java to create modular reusable components. We explain how the architecture using a modular approach can allow interoperability with other SNMP applications. Also, the systems can possibly connect via an API bus to CORBA, JMAPI or WBEM.

The Internet has become a widespread technology for providing public data, voice, video and multimedia services internationally. This paper presents a measurement methodology for evaluating quality of Internet service given by an ISP (Internet Service Provider), including a framework for defining the context and parameters for such measurement. The originality of this methodology lies principally in its reliance on sampling techniques and on its use of distributed applications to carry out measurement. The nature of the Internet places particular constraints on the amount and nature of data that can be collected, making statistical sampling necessary to answer certain types of questions. This paper addresses a number of methodological issues that arise when applying sampling techniques to the problem of measuring Internet service quality. This methodology is currently being implemented and tested by a major Canadian ISP.

The Simple Network Management Protocol (SNMP) was introduced in 1988 and is still widely implemented, deployed, and used. SNMPv3 is now in its final stages of standardization. From a practical perspective, we need to consider how telecommunication systems can be extended to consider different versions of SNMP, different applications and different security models. We will present an object-oriented implementation of SNMPv3 to create a flexible product architecture. This architecture allows to easily interface with other modules as required. We also describe network object models and relationships required for the architecture. The implementation uses Java to create modular reusable components. We explain how the architecture using a modular approach can allow interoperability with other SNMP applications. Also, the systems can possibly connect via an API bus to CORBA, JMAPI or WBEM.