A method, apparatus and computer program product for non-uniform per-packet priority marking for use with adaptive protocols is presented. A packet is received at a first network device, the packet assigned to a priority band. A priority is determined for the packet between a lowest priority of the priority band and a highest priority of the priority band, the priority for the packet selected based on a target distribution of priorities within the priority band, the target distribution comprising a distribution selected to achieve a desired capacity relationship among groups of packets assigned to different priority bands. The selected priority is assigned to the packet.