The total implementation complexity of packet schedulers which aim at approximating the Generalized Processor Sharing (GPS) policy is the combination of the complexity of their system-potential function and the complexity involved in sorting the timestamps in order to select the packet with minimum timestamp for transmission. Given that several scheduling algorithms which use a system-potential function of O(1) complexity have been introduced (among them, the Minimum-Delay Self-Clocked Fair Queuing (MD-SCFQ) algorithm achieves optimal delay and excellent fairness properties), the major contribution to the total complexity comes from the task of sorting the timestamps every time a packet is transmitted or received, which is common to all GPS-related schedulers. A method and an apparatus, called the Logarithmic Calendar Queue (LCQ), is disclosed which can achieve a dramatic reduction of the implementation complexity of sorting the timestamps in a GPS-related scheduler, at the cost of very small and controllable degradation of the guaranteed delay bounds. This is achieved by using a plurality of calendar subqueues, each subqueue associated with different granularity for the representation of timestamp values.