Generalized Processor Sharing (GPS) is a fluid scheduling policy providing perfect fairness. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one packet size. To the best of our knowledge, the only packet scheduler guaranteeing such minimum deviation is Worst-case Fair Weighted Fair Queueing (WF2Q), that requires on-line GPS simulation. Existing algorithms to perform GPS simulation have O(N) complexity per packet transmission (Nbeing the number of competing flows). Hence WF2Q has been charged for O(N) complexity too. Schedulers with lower complexity have been devised, but at the price of at least O(N) deviation from the GPS service, which has been shown to be detrimental for real-time adaptive applications and feedback based applications. Furthermore, it has been proven that the lower bound complexity to guarantee O(1) deviation is Omega(log N), yet a scheduler achieving such result has remained elusive so far.In this paper we present an algorithm that performs exact GPS simulation with O(log N) worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. In particular, using our algorithm within WF2Q, we achieve the minimum deviation from the GPS service with O(log N) complexity, thus matching the aforementioned lower bound. Furthermore, we assess the effectiveness of the proposed solution by simulating real-world scenarios.

Exact GPS simulation with logarithmic complexity, and its application to an optimally fair scheduler / Valente, Paolo. - STAMPA. - 34:4(2004), pp. 269-280. ((Intervento presentato al convegno ACM/SIGCOMM 2004 Conference on Computer Communications tenutosi a Portland, OR nel AUG 30-SEP 03, 2004 [10.1145/1030194.1015497].

Exact GPS simulation with logarithmic complexity, and its application to an optimally fair scheduler

VALENTE, Paolo
2004

Abstract

Generalized Processor Sharing (GPS) is a fluid scheduling policy providing perfect fairness. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one packet size. To the best of our knowledge, the only packet scheduler guaranteeing such minimum deviation is Worst-case Fair Weighted Fair Queueing (WF2Q), that requires on-line GPS simulation. Existing algorithms to perform GPS simulation have O(N) complexity per packet transmission (Nbeing the number of competing flows). Hence WF2Q has been charged for O(N) complexity too. Schedulers with lower complexity have been devised, but at the price of at least O(N) deviation from the GPS service, which has been shown to be detrimental for real-time adaptive applications and feedback based applications. Furthermore, it has been proven that the lower bound complexity to guarantee O(1) deviation is Omega(log N), yet a scheduler achieving such result has remained elusive so far.In this paper we present an algorithm that performs exact GPS simulation with O(log N) worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. In particular, using our algorithm within WF2Q, we achieve the minimum deviation from the GPS service with O(log N) complexity, thus matching the aforementioned lower bound. Furthermore, we assess the effectiveness of the proposed solution by simulating real-world scenarios.
ACM/SIGCOMM 2004 Conference on Computer Communications
Portland, OR
AUG 30-SEP 03, 2004
34
269
280
Valente, Paolo
Exact GPS simulation with logarithmic complexity, and its application to an optimally fair scheduler / Valente, Paolo. - STAMPA. - 34:4(2004), pp. 269-280. ((Intervento presentato al convegno ACM/SIGCOMM 2004 Conference on Computer Communications tenutosi a Portland, OR nel AUG 30-SEP 03, 2004 [10.1145/1030194.1015497].
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/587900
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 6
social impact