NDLI: Exact GPS Simulation and Optimal Fair Scheduling With Logarithmic Complexity

Content Provider	IEEE Xplore Digital Library
Author	Valente, P.
Copyright Year	1993
Abstract	Generalized processor sharing (GPS) is a fluid scheduling policy providing perfect fairness over both constant-rate and variable-rate links. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one maximum packet size. To the best of our knowledge, the only packet scheduler guaranteeing the minimum deviation is worst-case fair weighted fair queueing , which requires on-line GPS simulation. Existing algorithms to perform GPS simulation have worst-case computational complexity per packet transmission (being the number of competing flows). Hence, has been charged for complexity too. However it has been proven that the lower bound complexity to guarantee deviation is, yet a scheduler achieving such a result has remained elusive so far. In this paper, we present L-GPS, an algorithm that performs exact GPS simulation with worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. We also present , an implementation of based on L-GPS. has complexity with small constants, and, since it achieves the minimum possible deviation, it does match the aforementioned complexity lower bound. Furthermore, both L-GPS and comply with constant-rate as well as variable-rate links. We assess the effectiveness of both algorithms by simulating real-world scenarios.
Sponsorship	IEEE Computer Society IEEE Communications Society Association for Computing Machinery (ACM)
Starting Page	1454
Ending Page	1466
Page Count	13
File Size	733816
File Format	PDF
ISSN	10636692
Volume Number	15
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-12-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Global Positioning System Scheduling algorithm Processor scheduling Computational modeling Computational complexity Tree data structures tree data structures Complexity theory scheduling
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Electrical and Electronic Engineering Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Exact GPS simulation and optimal fair scheduling with logarithmic complexity

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

Efficient fair queueing algorithms for packet-switched networks

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

On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms

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

On the computational complexity of maintaining GPS clock in packet scheduling

Approximation of Generalized Processor Sharing With Interleaved Stratified Timer Wheels

1Exact GPS Simulation and Optimal Fair Scheduling with Logarithmic Complexity

Exact GPS Simulation and Optimal Fair Scheduling With Logarithmic Complexity

Similar Documents

Exact GPS simulation and optimal fair scheduling with logarithmic complexity

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

Efficient fair queueing algorithms for packet-switched networks

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

On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms

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

On the computational complexity of maintaining GPS clock in packet scheduling

Approximation of Generalized Processor Sharing With Interleaved Stratified Timer Wheels

1Exact GPS Simulation and Optimal Fair Scheduling with Logarithmic Complexity

Exact GPS Simulation and Optimal Fair Scheduling With Logarithmic Complexity