A scheduler and method for use in packet communication systems apply a generalized discrete-rate scheduling technique which removes the limitation of the linear increase in sorting complexity with the number of supported service rates. The set of supported service rates may be increased without increasing the number of timestamps that need to be sorted. Conversely, the generalized discrete-rate scheduler supports a given number of service rates using a smaller number of rate FIFO queues, thus further reducing complexity. Such improved performance is achieved by splitting, for scheduling purposes only, a connection or session into multiple sub-connections or sub-sessions. The technique can be applied to per-connection-timestamp and no-per-connection-timestamp discrete-rate schedulers, as well as to any other discrete-rate scheduler.