Efficient fair algorithms for message communication |
| |
| Authors: | Sergey Gorinsky Eric J Friedman Shane Henderson Christoph Jechlitschek |
| |
| Affiliation: | 1. Washington University, Department of Computer Science and Engineering, Bryan Hall, 1 Brookings Drive, St. Louis, MO 63130, USA;2. Cornell University, School of Operations Research and Information Engineering, Rhodes Hall, Ithaca, NY 14853, USA;3. Intel GmbH, Dornacher Strasse 1, 85622 Munich, Germany;1. University of Bradford, UK;2. Loughborough University, UK;3. University of Plymouth, UK;1. Department of Computing and Software, McMaster University, Canada;2. VERIMAG UMR 5104, Université Joseph Fourier, Grenoble, France;3. LIP6 UMR 7606, UPMC Sorbonne Universités, Paris, France;1. School of Electrical Engineering and Computer Science, Center for Computation and Technology, Louisiana State University, Baton Rouge, LA, USA;2. Department of Computer Science, Troy University, Troy, AL, USA;1. University of Freiburg, Abteilung für Netzökonomie, Wettbewerbsökonomie und Verkehrswissenschaft, Platz der Alten Synagoge, 79085 Freiburg im Breisgau, Germany;2. Technical University of Berlin, Germany;3. Massachusetts Institute of Technology, Computer Science and Artificial Intelligence Laboratory (CSAIL), Cambridge, MA, United States;1. ICE-TCS, School of Computer Science, Reykjavik University, Iceland;2. TDS Group, Massachusetts Institute of Technology, USA |
| |
| Abstract: | A computer network serves distributed applications by communicating messages between their remote ends. Many such applications desire minimal delay for their messages. Beside this efficiency objective, allocation of the network capacity is also subject to the fairness constraint of not shutting off communication for any individual message. Processor Sharing (PS) is a de facto standard of fairness but provides significantly higher average delay than Shortest Remaining Processing Time (SRPT), which is an optimally efficient but unfair algorithm. In this paper, we explore efficient fair algorithms for message communication where fairness means that no message is delivered later than under PS. First, we introduce a slack system to characterize fair algorithms completely and develop efficient fair algorithms called Pessimistic Fair Sojourn Protocol (PFSP), Optimistic Fair Sojourn Protocol (OFSP), and Shortest Fair Sojourn (SFS). Then, we prove that a fair online algorithm does not assure minimal average delay attainable with fairness. Our analysis also reveals lower bounds on worst-case inefficiency of fair algorithms. We conduct extensive simulations for various distributions of message sizes and arrival times. During either temporary overload or steady-state operation, SFS and other newly proposed fair algorithms support SRPT-like efficiency and consistently provide much smaller average delay than PS. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
