Paolo Valente

Assistant Professor of Computer Science Dipartimento di Scienze Fisiche, Informatiche e Matematiche Università di Modena e Reggio Emilia Via Campi 213/b - 41125 Modena (Italy) tel: Da assegnare - fax: +39 059 205 5235 paolo dot valente at unimore dot it

About myself...

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 search).

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 chronological order.

Packet scheduling

• P. Valente, “Reducing the execution time of fair-queueing packet schedulers”, Computer Communications, Volume 47, 1 July 2014, Pages 16-33, ISSN 0140-3664, http://dx.doi.org/10.1016/j.comcom.2014.04.009. (http://www.sciencedirect.com/science/article/pii/S0140366414001455)
• 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 Networks (PAEWN-2013).
  
  
• 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 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.
  

Storage 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

• Computer Programming I course (in Italian), held in the Laurea in Informatica degree at the Department of Physics, Computer Science and Mathematics - Modena - Italy

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 .