About myself...
I was born on the 10th
Semptember, 1973 in Cassino (FR). I
graduated (cum laude) in Computer Engineering at University of Pisa
on October 2000 with a thesis developed at the Information
Engineering Department on the
development of a packet Fair Queueing algorithm for the FreeBSD
kernel.
I worked at the at the Information Engineering Department
of the University of Pisa as a PhD student from 2001 to the end of
2004. I received my PhD on May 2005, with a thesis on scheduling
algorithms for QoS provisioning.
Starting from September 2006, I am an Assistant professor (Ricercatore) at the
Department of Computer Science of the University of Modena.
So far my research and development activity has been mainly focused on CPU,
network and disk scheduling algorithms for QoS provisioning. I am working on Multiprocessor scheduling too. Since the early months of 2007 I also began working on Bioinformatics algorithms (motif search).
Here is a short CV.
Publications and related stuff
Click here for just the list of
pubblications, with all bibliographic details and in reverse
chronological order.
Packet scheduling
- P. Valente, “Providing Near-Optimal Fair-Queueing Guarantees at Round-Robin Amortized Cost”, Proceedings of the
22nd International Conference on Computer Communication and Networks (ICCCN), 2013,
Extended version, Work in progress.
This paper contains a simple solution for reducing the
amortized execution time of fair-queueing packet schedulers, in
particular of the ones with a higher computational cost than a Deficit
Round Robin (DRR). This solution also enables the modified scheduler
to handle seamlessly both leaves and internal nodes in a hierarchical
setting.
In the document I also describe Quick Fair Queueing Plus (QFQ+), a
new scheduler obtained by applying the modification scheme to the QFQ
packet scheduler. According to my experimental results, and exactly
in the scenarios where fair-queueing schedulers provide better service
guarantees than round-robin ones, the execution time of QFQ+ is even
lower than that of DRR.
QFQ+ replaced QFQ in mainline Linux from 3.7. All the stuff related to QFQ+ can be found here.
- M. Casoni, A. Paganelli, P. Valente, “A Modular Architecture
for QoS Provisioning over Wireless Links”, Proceedings of the
Eighth Workshop on Performance Analysis and Enhancement of Wireless
Networks
(PAEWN-2013).
For space limitations the paper does not contain either the
proofs of the properties of the architecture or our simulation
results. This extended version
of the paper contains the former and should soon contain the latter as
well.
- L.Rizzo, P. Valente,
Analysis of Fair Queueing Schedulers in Real Systems, Technical Report, Work in progress.
According to the literature, packet-scheduler guarantees are always computed
assuming that the number of bits
transmitted by the communication link is known at any time instant,
and that the scheduler is directly attached to the communication link
with no interposed buffering.
Both assumptions are unfortunately unrealistic. In this paper we compute the actual guarantees provided by fair-queueing schedulers and simple round-robin schedulers in presence of buffers and without exact knowledge of the number of bits transmitted.
- F.Checconi, P. Valente, and L.Rizzo,
“QFQ: Efficient Packet Scheduling with Tight Guarantees”, IEEE/ACM Transactions on Networking, PP, Issue 99, October 2012, DOI=10.1109/TNET.2012.2215881.Version with small fixes (details about the changes here).
This is a very low-cost scheduler that closely approximates the worst-case-optimal service of WF2Q+.
I drafted QFQ a few years ago, and Fabio reworked and fixed it in many critical points later on (Fabio also wrote the first implementation for the Linux kernel). You can find a brief description of QFQ here. As shown there, QFQ is now one of the packet schedulers in FreeBSD.
As for Linux, QFQ can be found in mainline from 3.0 to 3.6 (see, e.g., this thread for the steps that brought QFQ first into net-next-2.6). Starting from 3.7, it has been replaced by QFQ+.
- M. Leoncini, P. Santi, P. Valente, “An STDMA-based framework for QoS provisioning in wireless mesh networks”, Proceedings of IEEE MASS 2008, October 2008.
Click here to download an extended version of this paper.
- P. Valente, “Exact
GPS simulation with logarithmic complexity, and its application to an
optimally fair scheduler”, Proceedings of
SIGCOMM’04, pages 269-280, August 2004.
Some bugs have been fixed in the (pseudo-)code of both L-GPS and
L-WF2Q. The
most important ones have been found and fixed by Ming-I
Hsieh. A hopefully bug-free version of the algorithms can be found in the following journal version of the paper.
- P. Valente, “Exact GPS simulation with logarithmic complexity, and its application to an optimally fair scheduler“, IEEE/ACM Transactions on Networking (ToN), February 2008.
Extended and improved version of my SIGCOMM paper about L-GPS and L-WF2Q. Click here to download the new paper.
- P. Valente, "Extending WF2Q+ to support a dynamic traffic mix", Proceedings of AAA-IDEA'05, June 2005.
An updated version of the paper is available: with respect to the previous version, it contains some considerations about constraining or not constraining the maximum value of the sum of the weights of the flows.
You can find an implementation of Time-driven Removal (TdR) -- the
simple extension for WF2Q+ defined in the paper -- in the code
of the BFQ and Hybrid disk schedulers listed below.
Disk scheduling
- P. Valente, M. Andreolini,
“Improving Application Responsiveness
with the BFQ Disk I/O Scheduler”, Proceedings of the 5th
Annual International Systems and Storage Conference (SYSTOR '12). ACM, New York, NY, USA, DOI=10.1145/2367589.2367590 http://doi.acm.org/10.1145/2367589.2367590.
Click here for an extended version of the paper and here for the slides of the presentation given at SYSTOR'12.
Budget Fair Queueing (BFQ) is a production-quality,
proportional share disk scheduler with a relatively large user base.
Part of its success is due to a set of simple heuristics that we
added to the original algorithm about one year ago. These
heuristics are the main focus of this paper.
See the next paper for further details.
- P. Valente, F. Checconi,
“High Throughput Disk Scheduling with Fair Bandwidth Distribution”, IEEE Transactions on Computers, vol. 59, no. 9, pp. 1172-1186, September 2010, doi:10.1109/TC.2010.105.
Click here for an extended version of the paper.
This is the initial paper describing Budget Fair Queueing (BFQ), a disk scheduler that I have defined and implemented under Linux with Fabio Checconi.
You can find here
all the stuff related to BFQ (short description, technical reports, patches, a benchmark suite for measuring various performance indexes of a disk scheduler, experimental results and so on).
- L. Rizzo, P. Valente,
“Hybrid: achieving deterministic fairness and high throughput
in disk scheduling”, Proceedings of CCCT’04, August
2004.
Hybrid has been also implemented by Luigi Rizzo and Emiliano
Mennucci in the project "Pluggable disk
scheduler for FreeBSD", which has been selected for funding from
the Google "Summer of Code" program
While implementing Hybrid on Linux and working on an improved version of the paper with Fabio Checconi, we bumped into the loss of the expected guarantees in case of synchronous disk requests. Unfortunately, the same problem is shared by all the disk schedulers we read about in the literature. To preserve service guarantees and to get a high throughput also in presence of synchrnous requests we defined the above mentioned BFQ scheduler.
Real-time systems
- Paolo Valente, Giuseppe Lipari, "An Upper Bound to the Lateness
of Soft Real-time Tasks Scheduled by EDF on Multiprocessors", Proceedings of RTSS'05, December 2005.
A bug has been found in one of the proofs (credits: UmaMaheswari C. Devi), and we prepared a backup Technical Report, containing only a subset of the sane proofs of the published paper. You can find this TR and other related stuff here.
- Luigi Palopoli, Tommaso Cucinotta, Luca Marzario, Antonio Mancina, Paolo Valente, "A unified framework for managing different resources with QoS guarantees", Proceedings of OSPERT'05, July 2005.
Bioinformatics
-
M. Federico, P. Valente, M. Leoncini, M. Montangero, R. Cavicchioli, "An Efficient Algorithm for Planted Structured Motif Extraction", Proc. Int. Workshop COMPBIO '09, Breaking Frontiers of Computational Biology, May 2009.
After the pubblication of this paper, we have continued working on this algorithm, and, in general, on comparing the performance of a 2-stage approach against the one of single-stage
algorithms. In terms of available code, the results of this work are: 1) an
improved version of the original 2-stage motif-finding tool, which we have
named SISMA, and 2) a program
suite for executing experiments, computing statistics and
generating plots.
Especially, from within the suite SISMA can be either easily
invoked manually (first-stage tools and supporting scripts are already in
place), or automatically run on randomly-generated
instances of the planted (structured) motif problem. The suite
also includes the original implementations of RISOTTO and EXMOTIF. In this
respect, for each run of experiments, it is possible to decide what set of
tools to execute
(and compare against each other in terms of execution time and set
of motifs found).
The suite can be downloaded here
(authentication required, please ask me for credentials by email).
Teaching
Last updated: May 10 2013.
Paolo Valente (paolo DOT valente AT unimore DOT it)
