Technical reports


List of technical reports of year 2015

Frangioni, Antonio and Galli, Laura and Stea, Giovanni
Delay-constrained Routing Problems: Accurate Scheduling Models and Admission Control
January 8, 2016
UnipiEprints view

It has been recently shown that the problem of routing a new packet flow in a computer network subject to a constraint on the worst-case end-to-end delay of its packets can be formulated as a Mixed-Integer Second-Order Cone Program (MI-SOCP), and solved with general-purpose tools on instances of realistic size in time compatible with real-time use. However, that result was obtained for only one of the classes of schedulers in use in today's networks, namely Strictly Rate-Proportional ones. Furthermore, that result relies on assuming that each link is "fully loaded", so that the reserved rate of the flow coincides with its guaranteed rate. These assumptions entail both simple latency expressions, and the fact that flows are isolated from each other as far as their end-to-end delay is concerned; that is, admitting a new flow does not increase the end-to-end delay of the existing ones. However, other classes of scheduling algorithms commonly found in current networks both yield more complex latency formulae and do not enforce strict flow independence. Furthermore, the delay actually depends on the guaranteed rate of the flow, which can be significantly larger than the reserved rate if the network is less loaded. In this paper we extend the result to other classes of schedulers and to a more accurate representation of the latency, showing that, despite the increase in complexity, the problem is still efficiently solvable, even when admission control needs to be factored in, for realistic instances, provided that the right modeling choices are made.

Frangioni, Antonio and Galli, Laura and Stea, Giovanni
QoS Routing with worst-case delay constraints: models, algorithms and performance analysis
December 28, 2015
UnipiEprints view

In a network where weighted fair-queueing schedulers are used at each link, worst-case end-to-end delays can be inferred from per-link rate reservations. Therefore, it is also possible to compute resource-constrained paths that meet target delay constraints, and optimize some key performance metrics (e.g., minimize the overall reserved rate, maximize the remaining capacity at bottleneck links, etc.). Despite the large amount of literature on QoS routing appeared since the mid '90s, few papers so far have discussed solving such path computation problem at optimality in general settings. In this paper, we formulate and solve the optimal path computation and resource allocation problem assuming different types of weighted fair-queueing schedulers in the network. We show that, depending on the scheduling algorithm, routing a new flow may or may not affect the performance of existing flows; hence, explicit admission control constraints may be required to ensure that existing flows still meet their deadline afterwards. Yet, for the relevant schedulers proposed in the literature the problem can be formulated as a Mixed-Integer Second-Order Cone problem (MI-SOCP), and can be solved at optimality in split-second times even in fairly large networks.

Bigi, Giancarlo and Pappalardo, Massimo and Passacantando, Mauro
Optimization tools for solving equilibrium problems with nonsmooth data
September 29, 2015
UnipiEprints view

The paper deals with the gap function approach for equilibrium problems with locally Lipschitz data. The gap function inherits the locally Lipschitz continuity of the data. Hence, the connections between its generalized directional derivatives, monotonicity conditions on the equilibrium bifunction and descent properties can be analysed. In turn, this analysis leads to devise two descent methods. Finally, the results of preliminary numerical tests arereported.

Brogi, Antonio and Canciani, Andrea and Soldani, Jacopo
Modelling the behaviour of management operations in TOSCA
July 29, 2015
UnipiEprints view

Managing complex applications over heterogeneous clouds is one of the emerging problems in the cloud era. The OASIS Topology and Orchestration Specification for Cloud Applications (TOSCA) aims at solving this problem by providing a language to describe and manage complex cloud applications in a portable and vendor-agnostic way. TOSCA permits to define an application as an orchestration of components, whose types can specify states, requirements, capabilities and management operations --- but not how they interact with each other. In [1][2], we already discussed a simple extension of TOSCA that permits describing the behaviour of a component's management operations and their relations with its states, requirements, and capabilities. The objective of this short report is to show how to enrich the TOSCA modelling language to provide such extension.

Del Corso, Gianna M. and Menchi, Ornella and Romani, Francesco
Krylov subspace methods for solving linear systems
June 3, 2015
UnipiEprints view

Download (507Kb)

Mukala, Patrick and Cerone, Antonio and Turini, Franco
An Exploration of Learning Processes as Process Maps in FLOSS Repositories
May 13, 2015
UnipiEprints view

Evidence suggests that Free/Libre Open Source Software (FLOSS) environ-ments provide unlimited learning opportunities. Community members engage in a number of activities both during their interaction with their peers and while mak-ing use of the tools available in these environments. A number of studies docu-ment the existence of learning processes in FLOSS through the analysis of sur-veys and questionnaires filled by FLOSS project participants. At the same time, the interest in understanding the dynamics of the FLOSS phenomenon, its popu-larity and success resulted in the development of tools and techniques for extract-ing and analyzing data from different FLOSS data sources. This new field is called Mining Software Repositories (MSR). In spite of these efforts, there is limited work aiming to provide empirical evidence of learning processes directly from FLOSS repositories. In this paper, we seek to trigger such an initiative by proposing an approach based on Process Mining to trace learning behaviors from FLOSS participants’ trails of activities, as recorded in FLOSS repositories, and visualize them as pro-cess maps. Process maps provide a pictorial representation of real behavior as it is recorded in FLOSS data. Our aim is to provide critical evidence that boosts the understanding of learning behavior in FLOSS communities by analyzing the rel-evant repositories. In order to accomplish this, we propose an effective approach that comprises first the mining of FLOSS repositories in order to generate Event logs, and then the generation of process maps, equipped with relevant statistical data interpreting and indicating the value of process discovery from these reposi-tories.

Soldani, Jacopo and Binz, Tobias and Breitenbücher, Uwe and Leymann, Frank and Brogi, Antonio
TOSCA-MART: A Method for Adapting and Reusing Cloud Applications
April 3, 2015
UnipiEprints view

To fully appreciate cloud computing powers, design and development of cloud applications should be eased and supported. The OASIS TOSCA standard enables developers to design and develop cloud applications by specifying their topologies as orchestrations of typed nodes and relationships.However, building such application topologies often results in reinventing the wheel multiple times when similar solutions are manually created for different applications by different developers having the same requirements. Thus, the reusability of existing TOSCA solutions is crucial to ease and support design and development processes. In this paper, we tackle this issue. We introduce TOSCA-MART, a method that enables deriving valid implementations for custom components from a repository of complete and validated cloud applications. The method enables developers to specify individual components in their application topologies, and illustrates how to match, adapt, and reuse existing (fragments of) applications to implement these components while fulfilling all their compliance requirements. We also characterize and validate TOSCA-MART by means of a prototypical implementation based on an open source toolchain and a case study.

Bartoloni, Leonardo and Brogi, Antonio and Ibrahim, Ahmad
Predicting the QoS of service orchestrations
March 13, 2015
UnipiEprints view

The ability to a priori predict the QoS of a service orchestration is of pivotal importance both for the design of service compositions and for the definition of their SLAs. In this paper we present an algorithm to probabilistically predict the QoS of WS-BPEL service orchestrations. Our algorithm employs Monte Carlo simulations and it improves previous approaches by coping with complex dependency structures, unbound loops, fault handling, and unresponded service invocations. A proof-of-concept implementation of the algorithm in F# is described.

van Ackooij, Wim and Frangioni, Antonio and de Oliveira, Welington
Inexact stabilized Benders' decomposition approaches to chance-constrained problems with finite support
February 26, 2015
UnipiEprints view

Motivated by a class of chance-constrained optimization problems, we explore modifications of the (generalized) Benders' decomposition approach. The chance-constrained problems we consider involve a random variable with an underlying discrete distribution, are convex in the decision variable, but their probabilistic constraint is neither separable nor linear. The variants of Benders' approach we propose exploit advances in cutting-plane procedures developed for the convex case. Specifically, the approach is stabilized in the two ways; via a proximal term/trust region in the L1 norm, or via a level constraint. Furthermore, the approaches can use inexact oracles, in particular informative on-demand inexact ones. The simultaneous use of the two features requires a nontrivial convergence analysis; we provide it under what would seem to be the weakest possible assumptions on the handling of the two parameters controlling the oracle (target and accuracy), strengthening earlier know results. Numerical performance of the approaches are assessed on a class of hybrid robust and chance-constrained conic problems. The numerical results show that the approach has potential, especially for instances that are difficult to solve with standard techniques.



NOTE. Starting January 2015 Technical reports can be inserted in the Open Access repository UnipiEprints.
Once published, they will be visible also in these pages. The old TR service is no longer maintained.

Data imported from UnipiEprints