A method of scheduling packet data delivery by a communication network node uses knowledge of the incoming delays and corresponding delay budgets associated with the packet data to be scheduled. For example, a wireless communication network base station may serve a plurality of users via a time-multiplexed packet data channel, and may schedule the delivery of packet data targeted to individual ones of those users based on determining the allowable scheduling delays for the incoming packet data it receives for those users. The allowable scheduling delays for packet data received on a given data connection may be determined based on the incoming delays associated with that packet data and the corresponding end-to-end delay budget defined for that packet data. The incoming delays may be calculated from packet time information, e.g., timestamps, and/or may be estimated based on call type, network type, network distances/locations, network conditions, etc.