So far my research and development activity has been mainly focused on
CPU, network and disk scheduling algorithms for QoS provisioning. In
particular, I am working on multiprocessor scheduling too. I have
worked a little bit also on Bioinformatics algorithms (motif
I am also the founder of the AlgoDev
group. It consists basically of volunteer developers, and its main
goal is to implement, in the form of open-source software projects,
selected algorithms among those devised as a part of the research
activity of the Algorithmic Research Group.
Finally, here is a short CV.
Publications and related stuff
Click here for just the list of
pubblications, with all bibliographic details and in reverse
- P. Valente, “Reducing the execution time of fair-queueing
packet schedulers”, Computer Communications, Volume 47, 1 July
2014, Pages 16-33, ISSN 0140-3664,
- 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.
- Pre-print version of the first
of the two papers. (which is in its turn an extended version
of the conference paper).
These journal and conference papers 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.8. 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
- 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.7 (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
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.
- 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
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.
- 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.
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
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).
Thesis, apprenticeship, internship and contribution proposals
You can find here current
proposals for thesis or apprenticeship activities and, in general,
for contributions to ongoing projects. Unfortunately, as of now
the page is only in Italian .
Last updated: March 5 2015.
Paolo Valente (paolo DOT valente AT unimore DOT it)