A system, method and apparatus for transmitting a packetized video stream over a network comprising receiving a frame of a video stream having a plurality of partitions of varying sizes, the plurality of partitions having an ordered sequence, identifying one or more of the plurality of partitions having a size that is less than a predetermined maximum, and allocating the identified one or more of the plurality of partitions into a plurality of packets in a manner that: (a) results in each packet having a size that is less than the predetermined maximum; (b) minimizes a cost value that is based at least in part on the difference between the size of the smallest packet and the size of the largest packet; and (c) maintains the allocated partitions in the ordered sequence. After allocation, the packets are transmitted over the network.