Described are computer-based methods and apparatuses, including computer program products, for statistical multiplexing of compressed video streams. A deadline of a packet of a compressed video stream is computed based on a program clock reference value of the packet. A plurality of packets, which includes the packet, is sorted based on deadlines corresponding to the packets. A next packet from the sorted plurality of packets is selected, the next packet having a corresponding deadline nearest to a system clock time. The next packet is transmitted.