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 indi- vidual message. Processor Sharing (PS) is a de facto standard of fairness but pro- vides 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 communicationwhere fairness means that no message is delivered later than under PS. First, we introduce a slack sys- tem 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 algo- rithm does not assure minimal average delay attainable with fairness. Our analysis also reveals lower bounds on worst-case inefficiency of fair algorithms. We con- duct 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 pro- vide much smaller average delay than PS.
['Sergey Gorinsky', 'Eric J. Friedman', 'Shane G. Henderson', 'Christoph Jechlitschek']
Efficient Fair Algorithms for Message Communication