Approximation of Generalized Processor Sharing with Interleaved Stratified Timer Wheels

Martin Karsten

This paper presents Interleaved Stratified Timer Wheels as a novel priority queue data structure for traffic shaping and scheduling in packet-switched networks. The data structure is used to construct an efficient packet approximation of General Processor Sharing (GPS). This scheduler is the first of its kind by combining all desirable properties without any residual catch. In contrast to previous work, the scheduler presented here has constant and near-optimal delay and fairness properties, and can be implemented with O(1) algorithmic complexity, and has a low absolute execution overhead. The paper presents the priority queue data structure and the basic scheduling algorithm, along with several versions with different cost-performance trade-offs. A generalized analytical model for rate-controlled rounded timestamp schedulers is developed and used to assess the scheduling properties of the different scheduler versions. Some illustrative simulation results are presented to reaffirm those properties.

IEEE/ACM Transactions on Networking 18(3):708-721, June 2010

Technical Report / Preprint (DOI)

Errata

• The function getBucket() is described as taking a rounded slot as an argument. However, in some of the given code (e.g. scan() in Fig. 5), the slot number is not rounded before calling getBucket(). In reality, it is more efficient to pass the current slot number and level to getBucket(), since performing the first two steps of Eq. (48) - subtraction and division - are sufficient to compute the bucket number.
• In function ISTW::scan(), the code

  	if ( !frontbits )
  		return search( slot );
  

  needs to be replaced with

  	if ( !frontbits )
  		return NULL;
  

Important Copyright Notice:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.